張樂(lè)

(廈門(mén)工學(xué)院計(jì)算機(jī)與人工智能學(xué)院，廈門(mén)361021)

0 引言

隨著無(wú)線網(wǎng)絡(luò)技術(shù)的快速發(fā)展，基于無(wú)線傳輸?shù)母鞣N應(yīng)用越來(lái)越豐富。在商場(chǎng)、車站、機(jī)場(chǎng)等人流量大的地方，往往有基于地理位置的信息分發(fā)的需求，例如針對(duì)當(dāng)前位置的無(wú)線廣告分發(fā)。然而，無(wú)線信道往往較為脆弱，尤其是在節(jié)點(diǎn)移動(dòng)且障礙物較多的室內(nèi)場(chǎng)景，往往存在連接傳輸不穩(wěn)定、丟包率較高的情況。

網(wǎng)絡(luò)編碼技術(shù)可以有效提高無(wú)線傳輸?shù)姆€(wěn)定性與效率[1，2]，研究利用網(wǎng)絡(luò)編碼技術(shù)進(jìn)行無(wú)線網(wǎng)絡(luò)的數(shù)據(jù)分發(fā)是重要課題之一。Ho等人[3]提出了一種隨機(jī)線性網(wǎng)絡(luò)編碼(Random Linear Network Coding，RLNC)算法，可以令發(fā)送出去的每一個(gè)數(shù)據(jù)包都攜帶等量的信息，已經(jīng)得到大量的應(yīng)用。Nandan等人[4]提出了一種基于網(wǎng)絡(luò)編碼的位置感知廣告服務(wù)。在車聯(lián)網(wǎng)中也可以利用線性編碼技術(shù)對(duì)數(shù)據(jù)包進(jìn)行編碼發(fā)送[5]，但過(guò)于頻繁的數(shù)據(jù)請(qǐng)求導(dǎo)致下載延遲較大。除了在數(shù)據(jù)包發(fā)送前進(jìn)行編碼以外，還可以加入優(yōu)先級(jí)的技術(shù)，令擁有較多編碼數(shù)據(jù)包的節(jié)點(diǎn)優(yōu)先發(fā)送[6]。李業(yè)等[2]則利用隨機(jī)線性網(wǎng)絡(luò)編碼有效地降低了傳輸?shù)臅r(shí)延。

1 隨機(jī)線性網(wǎng)絡(luò)編碼

對(duì)于不穩(wěn)定的無(wú)線傳輸，網(wǎng)絡(luò)編碼在可靠性和吞吐上都起到十分重要的作用[7]。無(wú)連接的傳輸中往往沒(méi)有確認(rèn)機(jī)制，因此對(duì)于傳輸失敗的情況很難精確重傳，一旦重傳的是已成功發(fā)送的數(shù)據(jù)，對(duì)于無(wú)線帶寬來(lái)說(shuō)是極大的浪費(fèi)。在隨機(jī)線性網(wǎng)絡(luò)編碼中，每一個(gè)編碼包都是唯一的，因此可以解決重傳重復(fù)數(shù)據(jù)的問(wèn)題。經(jīng)過(guò)隨機(jī)線性編碼的數(shù)據(jù)包，所包含的信息量都是均等的，也沒(méi)有先后次序。從信宿節(jié)點(diǎn)來(lái)看，編碼包可認(rèn)為是無(wú)差異的，因此特別適合使用廣播的方式進(jìn)行發(fā)送，有效利用無(wú)線網(wǎng)絡(luò)的空間冗余。要接收完整的一份報(bào)文，信宿節(jié)點(diǎn)并不需要接收特定的數(shù)據(jù)包。信源節(jié)點(diǎn)也不需要重傳某個(gè)丟失的數(shù)據(jù)包，只需要繼續(xù)發(fā)送下一個(gè)編碼包即可，信宿節(jié)點(diǎn)只要接收足夠的線性無(wú)關(guān)的編碼包就可以解碼獲取完整報(bào)文。隨機(jī)線性網(wǎng)絡(luò)編碼的這種特性，十分適合網(wǎng)絡(luò)環(huán)境惡劣、傳輸質(zhì)量較差的無(wú)線分發(fā)場(chǎng)合。

在隨機(jī)線性網(wǎng)絡(luò)編碼策略中，假設(shè)要發(fā)送的信息被分成k個(gè)包pi，那么就可以在有限域上隨機(jī)選取k個(gè)系數(shù)ci進(jìn)行線性組合形成編碼包P=∑cipi，重復(fù)系數(shù)選取并編碼的過(guò)程，就可以根據(jù)需要產(chǎn)生若干編碼包。中間節(jié)點(diǎn)接收到這些編碼包后，先判斷是否線性無(wú)關(guān)，若無(wú)關(guān)則可以保存。同時(shí)，中間節(jié)點(diǎn)仍然可以繼續(xù)隨機(jī)選取系數(shù)進(jìn)行組合重新編碼成一個(gè)編碼包轉(zhuǎn)發(fā)出去。隨機(jī)線性網(wǎng)絡(luò)編碼的全部操作均是基于有限域的線性運(yùn)算，所有編碼系數(shù)均從有限域中獨(dú)立隨機(jī)地選取。只要選取系數(shù)的有限域Fq足夠大，隨機(jī)線性網(wǎng)絡(luò)編碼就能以較高的概率獲得線性無(wú)關(guān)的組合進(jìn)行解碼[8]。實(shí)際應(yīng)用當(dāng)中，q=28就已經(jīng)足夠令各個(gè)節(jié)點(diǎn)產(chǎn)生遠(yuǎn)超k個(gè)線性無(wú)關(guān)的編碼包進(jìn)行解碼。

假設(shè)信源節(jié)點(diǎn)發(fā)出的信息為X=[x1，x2，…，xk]，其中第i個(gè)編碼包的編碼向量為[ci1，ci2，…，cik]，則該編碼包可以表示如下：

(1)

對(duì)于信宿節(jié)點(diǎn)，輸入的信息流可以表示如下：

(2)

其中C是信宿節(jié)點(diǎn)的編碼系數(shù)矩陣。信宿節(jié)點(diǎn)只要接收任意k個(gè)系數(shù)為線性無(wú)關(guān)的編碼包，就可以通過(guò)解線性方程組的方法解碼得出原始數(shù)據(jù)。

2 基于隨機(jī)線性網(wǎng)絡(luò)編碼的數(shù)據(jù)分發(fā)

2.1 問(wèn)題描述

假設(shè)一個(gè)數(shù)據(jù)分發(fā)源節(jié)點(diǎn)S，需要分發(fā)一個(gè)廣告文件給其它客戶節(jié)點(diǎn)，分發(fā)范圍為以S所在坐標(biāo)為圓心，以R為半徑的圓。在分發(fā)區(qū)域內(nèi)，不斷有客戶節(jié)點(diǎn)進(jìn)入與離開(kāi)，若停留超過(guò)一定的時(shí)間，就需要完整接收S正在分發(fā)的廣告文件。整個(gè)系統(tǒng)中需要發(fā)送的數(shù)據(jù)包分為兩類：分發(fā)包和通告包。

分發(fā)包：經(jīng)過(guò)隨機(jī)線性網(wǎng)絡(luò)編碼的廣告文件分發(fā)數(shù)據(jù)包?？捎煞职l(fā)源節(jié)點(diǎn)S廣播發(fā)送，也可由客戶節(jié)點(diǎn)廣播發(fā)送，僅客戶節(jié)點(diǎn)接收。

通告包：各個(gè)客戶節(jié)點(diǎn)進(jìn)入分發(fā)區(qū)域，就通告自己接收分發(fā)包的情況；通告包僅由客戶節(jié)點(diǎn)發(fā)送，分發(fā)源節(jié)點(diǎn)與客戶節(jié)點(diǎn)均可接收。

數(shù)據(jù)分發(fā)源節(jié)點(diǎn)S需要分發(fā)的數(shù)據(jù)包數(shù)量為：

m=M/q

(3)

其中M為需要分發(fā)的廣告文件大小，q為設(shè)定的分發(fā)數(shù)據(jù)包大小，單位均為字節(jié)。

2.2 算法設(shè)計(jì)

為了描述方便，表1給出了相關(guān)的定義。

表1 算法中使用的定義

客戶節(jié)點(diǎn)進(jìn)入分發(fā)區(qū)域后，接收源節(jié)點(diǎn)以及其它鄰居節(jié)點(diǎn)發(fā)送的分發(fā)包。當(dāng)接收到分發(fā)包時(shí)，判斷是否與已接收的分發(fā)包線性無(wú)關(guān)，若無(wú)關(guān)則保存，然后判斷是否滿秩，滿秩則解方程，成功接收被分發(fā)的廣告文件。

客戶節(jié)點(diǎn)Ci進(jìn)入分發(fā)區(qū)域，還需要周期廣播發(fā)送自己的通告包，通告鄰居節(jié)點(diǎn)自己接收的線性無(wú)關(guān)的分發(fā)包數(shù)量Ri。若在下一輪周期發(fā)送前已收到其它鄰居j的通告包且對(duì)方的線性無(wú)關(guān)分發(fā)包更少，即Rj

當(dāng)接收到通告包時(shí)，若本節(jié)點(diǎn)擁有的線性無(wú)關(guān)分發(fā)包更多，則可能需要廣播發(fā)送分發(fā)包。為了避免多個(gè)擁有更多分發(fā)包的節(jié)點(diǎn)同時(shí)發(fā)送產(chǎn)生沖突，在發(fā)送分發(fā)包之前還需要啟動(dòng)一個(gè)定時(shí)器等待，若在定時(shí)器耗盡前收到比自己更多無(wú)關(guān)包的通告，則放棄發(fā)送分發(fā)包，轉(zhuǎn)由擁有更多無(wú)關(guān)分發(fā)包的節(jié)點(diǎn)發(fā)送。定時(shí)器啟動(dòng)設(shè)定時(shí)間T的計(jì)算如下：

T=(m/K_max)·t

(4)

其中t是一個(gè)可調(diào)的計(jì)時(shí)單位。這個(gè)定時(shí)器表明，比鄰居擁有更多線性無(wú)關(guān)分發(fā)包的節(jié)點(diǎn)，定時(shí)器時(shí)間越短，即發(fā)送分發(fā)包的優(yōu)先級(jí)越高。

客戶節(jié)點(diǎn)Ci或源節(jié)點(diǎn)S接收到客戶節(jié)點(diǎn)Cj發(fā)送的通告包的具體處理算法如下：

初始化：

If(是源節(jié)點(diǎn))

Ri←m;

Else

Ri←0;

K_max←0;

T_remain←正無(wú)窮大

接收處理流程：

If(接收的是分發(fā)包){

If(本節(jié)點(diǎn)是客戶節(jié)點(diǎn)且分發(fā)包線性無(wú)關(guān)){

Ri←Ri+1;

If(Ri==m)

解碼，成功接收。

}

}

Else{

k←Ri-Rj

If(k>0){

If(k>K_max){

K_max←k;

T←(m/K_max)*t

T_remain←當(dāng)前計(jì)時(shí)器剩余時(shí)間;

If(T

T替換當(dāng)前計(jì)時(shí)器;

}

}

}

Else if(k<0){

若存在計(jì)時(shí)器，則刪除計(jì)時(shí)器取消發(fā)送。

}

}

算法首先初始化節(jié)點(diǎn)所擁有的線性無(wú)關(guān)分發(fā)包的數(shù)量，若為數(shù)據(jù)源節(jié)點(diǎn)，則擁有的是全部的分發(fā)包數(shù)量，否則初始化為零；接著初始化與鄰居節(jié)點(diǎn)之間的線性無(wú)關(guān)的數(shù)據(jù)包的最大差值為零，分發(fā)包發(fā)送計(jì)時(shí)器的剩余時(shí)間為無(wú)窮大。

接收到分發(fā)包時(shí)，若本節(jié)點(diǎn)是源節(jié)點(diǎn)且接收到的分發(fā)包與已接收的分發(fā)包線性無(wú)關(guān)，則本節(jié)點(diǎn)擁有的線性無(wú)關(guān)分發(fā)包數(shù)量加1，若數(shù)量已達(dá)m個(gè)，則可以成功解碼。

接收到通告包時(shí)，先計(jì)算本節(jié)點(diǎn)i與發(fā)送節(jié)點(diǎn)j之間線性無(wú)關(guān)的分發(fā)包數(shù)量的差值k。分兩種情況：

k>0：這表示對(duì)方已接收的線性無(wú)關(guān)分發(fā)包不如本節(jié)點(diǎn)多。若差值大于之前的最大差值，用當(dāng)前的差值更新為當(dāng)前最大差值，然后根據(jù)當(dāng)前最大差值計(jì)算一個(gè)新的退避時(shí)間T；若T小于當(dāng)前計(jì)時(shí)器剩余時(shí)間T_remain，則用T更新當(dāng)前計(jì)時(shí)器的剩余時(shí)間。

K<0：這表示對(duì)方已接收的線性無(wú)關(guān)分發(fā)包比本節(jié)點(diǎn)更多，可以由對(duì)方先發(fā)送分發(fā)包；因此如果本節(jié)點(diǎn)存在發(fā)送分發(fā)包的計(jì)時(shí)器，刪除計(jì)時(shí)器取消發(fā)送即可。

當(dāng)定時(shí)器到期時(shí)，則在有限域隨機(jī)選取Ri個(gè)系數(shù)，然后重新編碼組合成一個(gè)新的編碼包，重復(fù)選取系數(shù)進(jìn)行編碼的過(guò)程，直到產(chǎn)生新的K_max個(gè)分發(fā)包，然后連續(xù)發(fā)送出去。

3 實(shí)驗(yàn)結(jié)果及其分析

本節(jié)將使用NS-3進(jìn)行仿真實(shí)驗(yàn)與分析，并與傳統(tǒng)分發(fā)方式進(jìn)行比較。在傳統(tǒng)的分發(fā)方式中，數(shù)據(jù)源節(jié)點(diǎn)把待分發(fā)的文件分成同樣大小的數(shù)據(jù)包，并按順序持續(xù)循環(huán)分發(fā)。

仿真實(shí)驗(yàn)場(chǎng)景設(shè)定分發(fā)區(qū)域?yàn)榘霃?0米的圓，所有節(jié)點(diǎn)設(shè)定的最大通信距離是80米，除了數(shù)據(jù)源節(jié)點(diǎn)固定在分發(fā)區(qū)域的圓心外，其他節(jié)點(diǎn)隨機(jī)移動(dòng)，仿真時(shí)間為30秒。在仿真實(shí)驗(yàn)中，分發(fā)包的大小是1400字節(jié)，而通告包的大小是50字節(jié)。實(shí)驗(yàn)分析不同節(jié)點(diǎn)密度和分發(fā)內(nèi)容大小的情況下對(duì)分發(fā)時(shí)延和分發(fā)成功率的影響。其中分發(fā)時(shí)延指客戶節(jié)點(diǎn)發(fā)送第一個(gè)通告包到獲取一份完整的分發(fā)文件所需的時(shí)間，分發(fā)成功率則是整個(gè)場(chǎng)景中獲取完整分發(fā)內(nèi)容的客戶節(jié)點(diǎn)與全部客戶節(jié)點(diǎn)的比率。節(jié)點(diǎn)密度分為低密度100個(gè)節(jié)點(diǎn)，中密度200個(gè)節(jié)點(diǎn)和高密度300個(gè)節(jié)點(diǎn)。

3.1 分發(fā)時(shí)延

如圖1所示，當(dāng)分發(fā)內(nèi)容增多時(shí)，顯然需要更多的時(shí)間，因此接收完整的分發(fā)內(nèi)容的時(shí)延也會(huì)變大。不過(guò)，使用網(wǎng)絡(luò)編碼的分發(fā)方法，時(shí)延增長(zhǎng)速度較慢，而傳統(tǒng)方法則快速增加。在分發(fā)內(nèi)容只有200K字節(jié)的時(shí)候，兩種方法在各種密度場(chǎng)景下的分發(fā)時(shí)延都非常接近。然而，當(dāng)分發(fā)內(nèi)容超過(guò)800K時(shí)，兩種方法的性能差異較為明顯。特別是在1600K字節(jié)時(shí)，即使是高密度的場(chǎng)景，網(wǎng)絡(luò)編碼方法的分發(fā)時(shí)延也只有4.372秒，而傳統(tǒng)方法的分發(fā)時(shí)延為8.71秒，網(wǎng)絡(luò)編碼方法性能提升接近50%。這說(shuō)明在分發(fā)內(nèi)容體積較小的情況下，兩種方法沒(méi)有明顯的差異性，而當(dāng)分發(fā)內(nèi)容體積越大，網(wǎng)絡(luò)編碼分發(fā)的優(yōu)勢(shì)越明顯。這是因?yàn)榫W(wǎng)絡(luò)編碼使得數(shù)據(jù)包之間不存在差異性，丟失或者接收任何一個(gè)數(shù)據(jù)包所影響的信息量是一樣的，而傳統(tǒng)方法中，一旦某個(gè)數(shù)據(jù)包丟失，需要在下一輪循環(huán)中才有機(jī)會(huì)發(fā)送，當(dāng)分發(fā)內(nèi)容體積較大時(shí)，這個(gè)間隔的時(shí)間較長(zhǎng)。另外，從圖上可以看出，因?yàn)榭蛻艄?jié)點(diǎn)只是被動(dòng)接收數(shù)據(jù)，因此不同的節(jié)點(diǎn)密度對(duì)傳統(tǒng)分發(fā)方法的影響并不明顯。由于客戶節(jié)點(diǎn)也需要發(fā)送通告包甚至分發(fā)包，因此節(jié)點(diǎn)密度較大時(shí)，在網(wǎng)絡(luò)編碼的分發(fā)方法中會(huì)引起一些沖突。這種現(xiàn)象導(dǎo)致高密度場(chǎng)景下編碼的時(shí)延比低密度下的時(shí)延有一定的增長(zhǎng)，不過(guò)中等密度下的時(shí)延反而最小，這主要是因?yàn)橹械裙?jié)點(diǎn)密度下，鄰近的一些節(jié)點(diǎn)輔助源節(jié)點(diǎn)發(fā)送分發(fā)包，有效降低了分發(fā)時(shí)延。

圖1 分發(fā)時(shí)延

3.2 分發(fā)成功率

隨著分發(fā)內(nèi)容增大，所需的時(shí)延增加，因此，分發(fā)成功率會(huì)下降，圖2也展示了這種趨勢(shì)。得益于編碼后數(shù)據(jù)包的無(wú)差異性，編碼方法的分發(fā)成功率下降較慢，即使是1600K字節(jié)的分發(fā)內(nèi)容，成功率也超過(guò)了95%，在體積較小時(shí)，更是接近100%。和分發(fā)時(shí)延快速增加相對(duì)應(yīng)，如圖2所示，傳統(tǒng)方法的分發(fā)成功率也隨著分發(fā)內(nèi)容的增大而快速下降。產(chǎn)生這個(gè)現(xiàn)象的主要原因是部分距離數(shù)據(jù)源節(jié)點(diǎn)較遠(yuǎn)的客戶節(jié)點(diǎn)，在傳輸過(guò)程中丟包率較高，而廣播分發(fā)的方式并沒(méi)有針對(duì)某個(gè)丟失的包的重傳，而是整個(gè)分發(fā)內(nèi)容的重復(fù)發(fā)送，這種方式浪費(fèi)了較多的時(shí)間和網(wǎng)絡(luò)帶寬，也較難保證每一個(gè)數(shù)據(jù)包都能成功接收。所以在高密度大體積的情況下，傳統(tǒng)方法的分發(fā)成功率只有81.8%，分發(fā)體積越大，劣勢(shì)越明顯。

圖2 分發(fā)成功率

4 結(jié)語(yǔ)

在需要給大量用戶分發(fā)數(shù)據(jù)的時(shí)候，為了避免連接產(chǎn)生的負(fù)載，往往采用無(wú)連接的廣播方式發(fā)送。但采用無(wú)線網(wǎng)絡(luò)進(jìn)行廣播發(fā)送的時(shí)候，難以對(duì)丟失的數(shù)據(jù)包進(jìn)行精準(zhǔn)重傳。本文提出了基于隨機(jī)線性網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)分發(fā)方法，可以避免丟包引起的重傳，提升了數(shù)據(jù)分發(fā)的效率。本文提出的數(shù)據(jù)分發(fā)方法中，節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包分為編碼包與通告包兩種，通過(guò)通告包的設(shè)計(jì)，可由鄰居節(jié)點(diǎn)輔助發(fā)送已經(jīng)接收到的編碼包的組合，進(jìn)一步降低了分發(fā)的時(shí)延，從而提高了分發(fā)的成功率。通過(guò)仿真實(shí)驗(yàn)與傳統(tǒng)循環(huán)發(fā)送的方法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以在分發(fā)時(shí)延和分發(fā)成功率上都有較大的提升，分發(fā)內(nèi)容體積越大，優(yōu)勢(shì)越明顯。未來(lái)工作可以考慮繼續(xù)改進(jìn)通告包輔助發(fā)送的機(jī)制，并應(yīng)用到多跳長(zhǎng)距離分發(fā)的場(chǎng)景。