無線網(wǎng)絡中基于機會網(wǎng)絡編碼的加權(quán)廣播重傳

茍 亮張更新 孫 偉 謝智東 邊東明

(解放軍理工大學通信工程學院 南京 210007)

1 引言

網(wǎng)絡編碼的概念于2000年首次提出[1]，能夠極大地提高網(wǎng)絡吞吐量，并減小傳輸時延[2,3]。然而，要達到網(wǎng)絡編碼的最大吞吐量是一個NP問題。因此，為了提高傳輸效率，研究者提出了一些將網(wǎng)絡編碼應用到無線組播/廣播網(wǎng)數(shù)據(jù)重傳中的啟發(fā)式方法。其中，機會網(wǎng)絡編碼重傳(Opportunistic Network Coding Retransmission, ONCR)方案只需要進行 XOR操作就可實現(xiàn)編解碼，復雜度較低，因此對ONCR的研究逐步成為主流，取得了很多成果。肖瀟等人[4]給出了一種 NCWBR (Network-Coding-based Wireless Broadcasting Retransmission)方案，該方案能有效減少平均傳輸次數(shù)。文獻[5,6]中提出了兩種更加高效的重傳策略(Improved Network-Coding-based Broadcasting Retransmission,INCBR和Wireless Broadcasting Retransmission based on Opportunistic Network Coding,WBRONC)，在提高重傳效率的同時減小了計算復雜度。然而，以上方法都是基于鏈路狀態(tài)相同的網(wǎng)絡環(huán)境，而對各路徑丟包率不同條件下的ONCR重傳方法研究很少。截止目前，僅文獻[7]提出了一種基于圖論的最大加權(quán)團(Maximum Weig-hted Clique, MWC) 算法。但是，該算法的計算復雜度隨數(shù)據(jù)包數(shù)目、節(jié)點數(shù)目和丟包率呈指數(shù)增長，對節(jié)點能量和處理能力有限，規(guī)模較大的網(wǎng)絡不適用。

在上述研究成果的基礎上，本文對ONCR在鏈路丟包率不同時的無線廣播重傳方法進行了分析研究，以減少傳輸次數(shù)和計算復雜度為目標，提出了一種新的基于機會網(wǎng)絡編碼的加權(quán)廣播重傳(Weighted Opportunistic Network Coding Retransmission WONCR)方案。該方案以構(gòu)建加權(quán)數(shù)據(jù)色分布矩陣(Weighted Packet Distribution Matrix, WPDM )為基礎，采用一種新的數(shù)據(jù)包調(diào)度算法對編碼數(shù)據(jù)包進行選取。為了驗證所提方案的有效性，本文對平均傳輸次數(shù)和計算復雜度進行了分析和仿真，結(jié)果表明該方案傳輸效率高，且計算復雜度較低。

2 系統(tǒng)模型

本文采用通用無線廣播模型，該模型包含一個源節(jié)點S和N個接收節(jié)點，假設源節(jié)點廣播M個原始數(shù)據(jù)包給N個接收節(jié)點。廣播過程分為兩個階段：初始階段和重傳階段。在初始階段，源節(jié)點逐個廣播M個原始數(shù)據(jù)包，接收節(jié)點接收到原始數(shù)據(jù)包后，將每個數(shù)據(jù)包的狀態(tài)信息（成功接收或丟失)反饋給源節(jié)點。在重傳階段，源節(jié)點根據(jù)接收節(jié)點反饋的狀態(tài)信息選擇來自不同接收節(jié)點的丟包進行 XOR編碼，再將編碼包重傳給接收節(jié)點。

假設源節(jié)點 S在廣播數(shù)據(jù)包后，接收節(jié)點 Ri能根據(jù)接收信號信噪比準確估算出鏈路狀態(tài)信息，且狀態(tài)信息在反饋信道中不存在丟失。另外，假設源節(jié)點和各接收節(jié)點之間的信道是相互獨立的，且在廣播一個數(shù)據(jù)包的時隙內(nèi)丟包率不變。

定義1 加權(quán)數(shù)據(jù)包分布矩陣（WPDM)指傳輸過程中，源節(jié)點通過收集各接收節(jié)點反饋的數(shù)據(jù)包狀態(tài)信息和鏈路狀態(tài)信息形成列表。該列表是一個N×M的矩陣，行系數(shù)和列系數(shù)分別表示接收節(jié)點和原始數(shù)據(jù)包，矩陣中的元素用;表示。如果，則表示接收節(jié)點Ri沒有接收到數(shù)據(jù)包Pj，且源節(jié)點和Ri之間的鏈路成功傳輸1個數(shù)據(jù)包的概率為1–pi，其中pi為源節(jié)點和接收節(jié)點Ri之間鏈路的丟包率；如果wi,j=0，則表示Ri已成功接收到數(shù)據(jù)包Pj。表1給出了1個具有6個接收節(jié)點和8個原始數(shù)據(jù)包的WPDM示例。

表1 加權(quán)數(shù)據(jù)包分布矩陣(WPDM)

證明 給定接收節(jié)點 Ri和編碼包kCP ，如果WPDM中對應的所有元素為0，則說明Ri已成功接收參與編碼的所有數(shù)據(jù)包，因而此次重傳對Ri來說收益為0。如果Ri原本缺少這些數(shù)據(jù)包中的2個或2個以上，則不能通過XOR操作從編碼包中解出任何原始數(shù)據(jù)包，其收益也為0。除去這兩種情況，當且僅當其中1個數(shù)據(jù)包丟失的情況下，Ri才有可能解出1個原始數(shù)據(jù)包，即元素中有且僅有一個為1，其它全為0，從而證明式(1)。

定義3 總傳輸增益kG 指在第k次傳輸中發(fā)送編碼數(shù)據(jù)包，成功接收并譯出原始數(shù)據(jù)包的接收節(jié)點數(shù)目的期望值，即

不同的編碼包可以使不同的接收節(jié)點受益，如果每次重傳的編碼包都能使更多的接收節(jié)點受益，即總傳輸增益更大，那么重傳的次數(shù)就會更少，傳輸效率就會更高。因此，本文所描述問題的核心就是如何選擇或調(diào)度原始數(shù)據(jù)包進行編碼，使每次重傳都能讓最多的接收節(jié)點受益。

3 WONCR方案

基于以上模型，本文提出了一種新的啟發(fā)式廣播重傳方案 WONCR，其基本思想是直接通過WPDM選取原始丟包進行編碼，這種方法直觀且效率更高。WONCR方案的實施分5個步驟，其中第3個步驟包括1個數(shù)據(jù)包調(diào)度算法，具體步驟描述如下。

步驟..1 初始傳輸階段，發(fā)送節(jié)點將所有的原始數(shù)據(jù)包廣播給所有接收節(jié)點。

步驟2 在初始傳輸或是在某次重傳結(jié)束之后，對 WPDM 矩陣進行初始化或更新。源節(jié)點首先通過無線信道從每個接收節(jié)點收集相應的數(shù)據(jù)包狀態(tài)信息和鏈路狀態(tài)信息，然后根據(jù)這些狀態(tài)信息形成WPDM。WPDM矩陣形成后，源節(jié)點判斷WPDM是否為全“0”矩陣。如果是，則代表每個接收節(jié)點都收到所有M個數(shù)據(jù)包，整個傳輸過程結(jié)束；如果不是，則轉(zhuǎn)到步驟3繼續(xù)執(zhí)行。

步驟3 在初始化或WPDM更新結(jié)束后，源節(jié)點開始選取第k次傳輸?shù)木幋a數(shù)據(jù)包，調(diào)度過程由一個加權(quán)數(shù)據(jù)包調(diào)度算法具體實施，具體如表2所示。

表2 加權(quán)數(shù)據(jù)包調(diào)度算法

步驟4 根據(jù)步驟3中存儲在數(shù)組T中的數(shù)據(jù)包系數(shù)，源節(jié)點將選取的數(shù)據(jù)包使用 XOR操作進行編碼，并廣播重傳給所有接收節(jié)點，接收節(jié)點再進行解碼。然后，根據(jù)各接收節(jié)點反饋的狀態(tài)信息生成新的WPDM矩陣，如果WPDM矩陣不是全“0”矩陣，則從步驟2開始新一輪的調(diào)度、編碼和重傳。

步驟 5 當所有接收節(jié)點都成功接收到它們需要的數(shù)據(jù)包，即WPDM為全“0”矩陣后，整個傳輸過程結(jié)束。如果源節(jié)點有更多信息需要廣播，則系統(tǒng)將從步驟1開始新一輪的傳輸。

4 性能分析

4.1 平均傳輸次數(shù)

在數(shù)據(jù)包數(shù)目M足夠大時，該結(jié)果可以進一步擴展，即對具有N個接收節(jié)點的系統(tǒng)，其數(shù)據(jù)包傳輸次數(shù)由鏈路丟包率最大的接收節(jié)點所需的傳輸次數(shù)決定，得出系統(tǒng)的理論傳輸次數(shù)為

每個數(shù)據(jù)包平均需要的傳輸次數(shù)為

4.2 計算復雜度

在每次編碼包的選取過程中，WONCR,INCBR和NCWBR 3個調(diào)度方案首先為N個接收節(jié)點確認M個數(shù)據(jù)包的狀態(tài)。如果有接收節(jié)點丟失了數(shù)據(jù)包，那么源節(jié)點將尋找所有可能的2M 個包的組合。因此，算法的時間復雜度為。然而，MWC方案將WPDM中各非0元素轉(zhuǎn)換為鄰接圖的頂點，最多為NM×個頂點，源節(jié)點將尋找所有可能的( )2NM×個組合。因此，其算法時間復雜度為隨著N和M的增加，該方案復雜度比WONCR, INCBR和NCWBR方案要高得多。

表3 4種調(diào)度方案的計算復雜度

5 仿真結(jié)果

為了驗證WONCR方案的有效性，本節(jié)對平均傳輸次數(shù)和計算復雜度進行了仿真實驗。假設鏈路的平均丟包率為ε，源節(jié)點和各接收節(jié)點之間的鏈路丟包率在[εσ-,εσ+]范圍內(nèi)，且均勻分布。通過500次的蒙特卡洛仿真，得出了不同網(wǎng)絡條件下WONCR方案的平均傳輸次數(shù)和計算開銷，并與傳統(tǒng)的 ARQ方案，MWC方案及經(jīng)過加權(quán)修改后的NCWBR方案和INCBR方案進行了比較。

5.1 平均傳輸次數(shù)

根據(jù)式(5)和仿真條件設定，可以得出平均傳輸次數(shù)的理論上界為

圖 1(a)給出了各方案的平均傳輸次數(shù)隨數(shù)據(jù)包數(shù)目變化的情況。從仿真結(jié)果可以看出，MWC,WONCR和 INCBR方案的平均傳輸次數(shù)遠小于ARQ方案，而NCWBR方案的性能介于兩者之間。隨著數(shù)據(jù)包數(shù)目的增加，ARQ方案和NCWBR方案的平均傳輸次數(shù)幾乎不變；而MWC, WONCR和 INCBR方案則隨著數(shù)據(jù)包數(shù)目的增加而逐步減少，并越來越接近理論上界，這是因為數(shù)據(jù)包越多，編碼機會就越多；WONCR方案的性能稍遜于MWC方案，但優(yōu)于INCBR方案。各方案的平均傳輸次數(shù)同接收節(jié)點數(shù)目變化的情況如圖 1(b)所示。同以上結(jié)果類似，MWC, WONCR和INCBR方案的性能要遠好于ARQ和NCWBR方案，4個方案的平均傳輸次數(shù)均隨接收節(jié)點數(shù)目的增加而增多。WONCR方案和MWC方案的平均傳輸次數(shù)隨接收節(jié)點數(shù)目的增加有很小的增大，INCBR方案次之，ARQ方案增加較大但曲線斜率逐步減小，而NCWBR方案則是線性增大，在接收節(jié)點數(shù)目達到50~60時，NCWBR方案的平均傳輸次數(shù)甚至超過了ARQ方案，這是由于NCWBR在選取數(shù)據(jù)包時未對可解性進行判斷，從而導致很多的無效傳輸。圖 1(c)給出了各方案的平均傳輸次數(shù)隨丟包率變化的比較關系。從圖 1(c)中看出，4個方案的平均傳輸次數(shù)均隨丟包率的增大而快速增加，但WONCR和MWC方案的性能遠好于NCWBR和ARQ方案，INCBR次之，MWC方案性能最好。

此外，本文還對各接收節(jié)點鏈路丟包率相同和丟包率差異較大情況下的傳輸性能進行了實驗比較。結(jié)果表明，在丟包率相同情況下, WONCR方案的重傳性能最好，且稍優(yōu)于MWC方案。這是因為MWC方案對選取的數(shù)據(jù)包集合中的每個元素都要求可解，從而喪失了少量的編碼機會，而WONCR方案以傳輸增益最大化為目標，雖然選取的數(shù)據(jù)包對某些接收節(jié)點可能不具有可解性，也可能不是最優(yōu)解，但在MWC方案喪失編碼機會較多的情況下，MWC方案性能將優(yōu)于MWC方案。在各接收節(jié)點丟包率差異較大時, WONCR和MWC方案的性能最佳，INCBR和NCWBR方案次之，ARQ方案最差。

圖1 各情況下的重傳性能比較

圖2 各情況下的計算開銷比較

5.2 計算復雜度

本節(jié)對WONCR, NCWBR, INCBR和MWC 4種方案的計算開銷進行了仿真驗證，使用的仿真計算機CPU為Intel (R) Core (TM)2 2.5 GHz，內(nèi)存為2 GB，仿真實驗軟件為Matlab R2008a。

圖2給出了4種方案計算開銷隨數(shù)據(jù)包數(shù)目，接收節(jié)點數(shù)目及丟包率變化的比較曲線。從仿真曲線可以看出，4種方案的計算開銷均隨數(shù)據(jù)包數(shù)目，接收節(jié)點數(shù)目及丟包率的增大而增大，但WONCR,INCBR和NCWBR方案的處理時間遠小于MWC方案。WONCR和NCWBR方案的計算開銷隨接收節(jié)點數(shù)目增加而線性增大，且曲線斜率不大。從計算開銷的角度來看，這兩種方案更適合于節(jié)點較多的大規(guī)模廣播網(wǎng)絡。

由以上仿真可以看出：MWC方案傳輸效率最高，但其計算復雜度遠高于其它方案，不適用于能量和計算資源受限的系統(tǒng)；WONCR在傳輸效率上接近MWC方案，且其計算開銷相對較低，在傳輸效率和復雜度之間取得了很好的平衡，具有更高的應用價值。

6 結(jié)束語

本文對丟包率不同條件下基于機會網(wǎng)絡編碼的無線廣播重傳方法進行了分析，提出了使用WPDM矩陣進行編碼數(shù)據(jù)包調(diào)度的WONCR方案。分析和仿真結(jié)果表明，該方案具有傳輸效率高，計算復雜度低的特點。WONCR方案可以在保證較高傳輸效率的同時減小節(jié)點的處理負荷，使基于機會網(wǎng)絡編碼的無線廣播重傳性能得到很大提升，能廣泛應用到衛(wèi)星廣播網(wǎng)、無線傳感器網(wǎng)和行星際互聯(lián)網(wǎng)等系統(tǒng)的廣播業(yè)務中，具有很高的應用價值。

[1] Ahlswede R, Ning Cai, Li S-Y R, et al.. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.

[2] Li Zong-peng, Li Bao-chun, and Lau L C. A constant bound on throughput improvement of multicast network coding in undirected networks[J]. IEEE Transactions on Information Theory, 2009, 55(3): 1016-1026.

[3] Traskov D, Heindlmaier M, Médard M, et al.. Scheduling for network-coded multicast[J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1479-1488.

[4] 肖瀟, 王偉平, 楊路明, 等. 基于網(wǎng)絡編碼的無線廣播重傳方法[J]. 通信學報, 2009, 30(9): 69-75.Xiao Xiao, Wang Wei-ping, Yang Lu-ming, et al.. Wireless broadcasting retransmission approach based on network coding[J]. Journal on Communications, 2009, 30(9): 69-75.

[5] 孫偉, 張更新, 邊東明, 等. 衛(wèi)星通信中基于網(wǎng)絡編碼改進的廣播重傳策略[J]. 宇航學報, 2013, 34(2): 231-236.Sun Wei, Zhang Geng-xin, Bian Dong-ming, et al.. An improved network-coding-based broadcasting retransmission scheme in satellite communications[J]. Journal of Astronautics, 2013, 34(2): 231-236.

[6] Gou Liang, Zhang Geng-xin, Sun Wei, et al.. WBRONC:efficient wireless broadcast retransmission based on opportunistic network coding[J]. Frequenz, 2013, 67(3/4):117-125.

[7] Wang Xiu-min, Wang Jiang-ping, and Xu Yin-long. Data dissemination in wireless sensor networks with network coding[J]. EURASIP Journal on Wireless Communications and Networking, 2010, (1): DOI:10.1155/20101465915..