基于網絡編碼的無線網絡數據分發系統研究

張樂

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

0 引言

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

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

1 隨機線性網絡編碼

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

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

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

(1)

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

(2)

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

2 基于隨機線性網絡編碼的數據分發

2.1 問題描述

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

分發包：經過隨機線性網絡編碼的廣告文件分發數據包。可由分發源節點S廣播發送，也可由客戶節點廣播發送，僅客戶節點接收。

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

數據分發源節點S需要分發的數據包數量為：

m=M/q

(3)

其中M為需要分發的廣告文件大小，q為設定的分發數據包大小，單位均為字節。

2.2 算法設計

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

表1 算法中使用的定義

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

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

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

T=(m/K_max)·t

(4)

其中t是一個可調的計時單位。這個定時器表明，比鄰居擁有更多線性無關分發包的節點，定時器時間越短，即發送分發包的優先級越高。

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

初始化：

If(是源節點)

Ri←m;

Else

Ri←0;

K_max←0;

T_remain←正無窮大

接收處理流程：

If(接收的是分發包){

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

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){

若存在計時器，則刪除計時器取消發送。

}

}

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

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

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

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

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

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

3 實驗結果及其分析

本節將使用NS-3進行仿真實驗與分析，并與傳統分發方式進行比較。在傳統的分發方式中，數據源節點把待分發的文件分成同樣大小的數據包，并按順序持續循環分發。

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

3.1 分發時延

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

圖1 分發時延

3.2 分發成功率

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

圖2 分發成功率

4 結語

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