無線網絡中基于機會網絡編碼的加權廣播重傳

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

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

1 引言

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

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

2 系統模型

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

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

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

表1 加權數據包分布矩陣(WPDM)

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

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

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

3 WONCR方案

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

步驟..1 初始傳輸階段，發送節點將所有的原始數據包廣播給所有接收節點。

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

步驟3 在初始化或WPDM更新結束后，源節點開始選取第k次傳輸的編碼數據包，調度過程由一個加權數據包調度算法具體實施，具體如表2所示。

表2 加權數據包調度算法

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

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

4 性能分析

4.1 平均傳輸次數

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

每個數據包平均需要的傳輸次數為

4.2 計算復雜度

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

表3 4種調度方案的計算復雜度

5 仿真結果

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

5.1 平均傳輸次數

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

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

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

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

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

5.2 計算復雜度

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

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

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

6 結束語

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

[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] 肖瀟, 王偉平, 楊路明, 等. 基于網絡編碼的無線廣播重傳方法[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] 孫偉, 張更新, 邊東明, 等. 衛星通信中基于網絡編碼改進的廣播重傳策略[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..