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

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

1 引言

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

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

3 WONCR方案

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

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

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

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

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

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

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

4 性能分析

4.1 平均傳輸次數(shù)

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

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

4.2 計(jì)算復(fù)雜度

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

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

5 仿真結(jié)果

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

5.1 平均傳輸次數(shù)

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

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

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

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

圖2 各情況下的計(jì)算開(kāi)銷(xiāo)比較

5.2 計(jì)算復(fù)雜度

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

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

由以上仿真可以看出：MWC方案?jìng)鬏斝首罡?，但其?jì)算復(fù)雜度遠(yuǎn)高于其它方案，不適用于能量和計(jì)算資源受限的系統(tǒng)；WONCR在傳輸效率上接近MWC方案，且其計(jì)算開(kāi)銷(xiāo)相對(duì)較低，在傳輸效率和復(fù)雜度之間取得了很好的平衡，具有更高的應(yīng)用價(jià)值。

6 結(jié)束語(yǔ)

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

[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)絡(luò)編碼的無(wú)線廣播重傳方法[J]. 通信學(xué)報(bào), 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)絡(luò)編碼改進(jìn)的廣播重傳策略[J]. 宇航學(xué)報(bào), 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..