基于網(wǎng)絡編碼的無線網(wǎng)絡數(shù)據(jù)分發(fā)系統(tǒng)研究

張樂

(廈門工學院計算機與人工智能學院，廈門361021)

0 引言

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

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

1 隨機線性網(wǎng)絡編碼

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

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

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

(1)

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

(2)

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

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

2.1 問題描述

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

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

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

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

m=M/q

(3)

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

2.2 算法設計

為了描述方便，表1給出了相關的定義。

表1 算法中使用的定義

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

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

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

T=(m/K_max)·t

(4)

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

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

初始化：

If(是源節(jié)點)

Ri←m;

Else

Ri←0;

K_max←0;

T_remain←正無窮大

接收處理流程：

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

If(本節(jié)點是客戶節(jié)點且分發(fā)包線性無關){

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←當前計時器剩余時間;

If(T

T替換當前計時器;

}

}

}

Else if(k<0){

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

}

}

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

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

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

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

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

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

3 實驗結果及其分析

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

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

3.1 分發(fā)時延

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

圖1 分發(fā)時延

3.2 分發(fā)成功率

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

圖2 分發(fā)成功率

4 結語

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