吳陽陽，魏辰, 王久鵬

（重慶郵電大學(xué)，重慶 400065）

網(wǎng)絡(luò)編碼理論最早是由香港中文大學(xué)的Ahlswede[1]教授等人在2000年首先提出的，其核心思想是允許網(wǎng)絡(luò)的中間節(jié)點(diǎn)對各條信道上收到的信息進(jìn)行線性或者非線性的處理，而傳統(tǒng)網(wǎng)絡(luò)中的中間節(jié)點(diǎn)只對收到的數(shù)據(jù)進(jìn)行存儲轉(zhuǎn)發(fā)。通過允許中間節(jié)點(diǎn)處理數(shù)據(jù)，網(wǎng)絡(luò)編碼可以達(dá)到由最大流最小割定理得到的網(wǎng)絡(luò)最大傳輸容量，由于無線網(wǎng)絡(luò)的廣播特性非常適合網(wǎng)絡(luò)編碼的思想，因此將網(wǎng)絡(luò)編碼用于無線網(wǎng)絡(luò)中已經(jīng)成為當(dāng)前的一個研究熱點(diǎn)。

目前，網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的應(yīng)用研究主要側(cè)重在幾個方面改善系統(tǒng)吞吐量，提高能量利用效率、保證無線鏈路傳輸?shù)目煽啃院桶踩?。由于無線網(wǎng)絡(luò)的傳輸信道受噪聲，多徑衰落等影響較大，節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組，可能要經(jīng)過多次重傳才能實(shí)現(xiàn)可靠傳輸，而多次重傳會導(dǎo)致節(jié)點(diǎn)的能耗增加，帶寬利用率降低。將網(wǎng)絡(luò)編碼與ARQ結(jié)合的重傳機(jī)制能夠在一個時隙能廣播發(fā)送由多個丟失數(shù)據(jù)分組編碼得到的編碼分組，而丟分組節(jié)點(diǎn)可以通過接收編碼分組來解碼得到丟失的數(shù)據(jù)分組。也就是說一個時隙內(nèi)傳輸一個編碼分組可以得到多個丟失的數(shù)據(jù)分組，因此傳輸效率可以得到極大提升。

1 相關(guān)工作

我們以經(jīng)典的蝴蝶網(wǎng)絡(luò)為模型，說明網(wǎng)絡(luò)編碼應(yīng)用于無線網(wǎng)絡(luò)中時，網(wǎng)絡(luò)性能的提升。在圖1所示的蝴蝶網(wǎng)絡(luò)中，S是源節(jié)點(diǎn)，R1和R2是兩個目的節(jié)點(diǎn)，假設(shè)各條鏈路都無時延和差錯，每條邊的容量都為1。在圖1（a）中，由最大流最小割定理知，信源節(jié)點(diǎn)S到目的節(jié)點(diǎn)R1和R2的最大傳播速率不可能超過2。然而,如果允許網(wǎng)絡(luò)中的中間節(jié)點(diǎn)對進(jìn)入節(jié)點(diǎn)的數(shù)據(jù)分組進(jìn)行編碼,如圖1（b）所示,則可以同時將數(shù)據(jù)分組P1和數(shù)據(jù)分組P2發(fā)送到目的節(jié)點(diǎn)R1和R2。因?yàn)楫?dāng)目的節(jié)點(diǎn)R1接收到數(shù)據(jù)分組P1和編碼分組P1P2時,可以將P1與P1P2進(jìn)行異或運(yùn)算恢復(fù)出P2。同理,在目的節(jié)點(diǎn)R2可以恢復(fù)出P1。我們可以看到，在蝴蝶網(wǎng)絡(luò)中利用網(wǎng)絡(luò)編碼，可以使網(wǎng)絡(luò)的傳輸效率得到明顯提升。

圖1 采用編碼的具有兩個目的節(jié)點(diǎn)的蝴蝶網(wǎng)

網(wǎng)絡(luò)編碼應(yīng)用于數(shù)據(jù)分組的丟失重傳是無線網(wǎng)絡(luò)的發(fā)展趨勢。在文獻(xiàn)[2]中，作者提出了一些網(wǎng)絡(luò)編碼的應(yīng)用方案，應(yīng)用于一個發(fā)送方多個接收方單跳無線網(wǎng)絡(luò)中，可以有效減少廣播重傳的次數(shù)，主要思想是允許發(fā)送方以特定的方法編碼和重傳丟失的數(shù)據(jù)分組，以使多個接收方能夠在一次重傳中恢復(fù)丟失的數(shù)據(jù)分組。文獻(xiàn)[3]中，H.WU等提出了一種基于廣播重傳的網(wǎng)絡(luò)編碼機(jī)制 (CoRET，Coding-based RE Transmission），應(yīng)用于移動通信網(wǎng)絡(luò)的廣播服務(wù)，以提高重傳效率和重傳的可靠性。在文獻(xiàn)[3]中，肖瀟提出了一種基于網(wǎng)絡(luò)編碼的無線廣播重方法NCWBR (Network Coding Wireless Broadcasting Retransmission)，NCWBR的基本思想是節(jié)點(diǎn)利用反饋的分組丟失信息,對需要重傳的多個數(shù)據(jù)分組進(jìn)行編碼組合，然后把編碼分組廣播重傳，該重傳策略可以有效減少重傳次數(shù)，提高重傳效率。

現(xiàn)有的研究中，在重傳中應(yīng)用網(wǎng)絡(luò)編碼，都是基于一個發(fā)送方多個接收方的網(wǎng)絡(luò)情景，而在多個發(fā)送方多個接收方的單跳網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)編碼卻還沒有得到充分研究，本文提出一種應(yīng)用于多個發(fā)送方多個接收方無線網(wǎng)絡(luò)中的重傳算法RMBNC（Retransmission Mechanism Based on Network Coding）。

2 網(wǎng)絡(luò)編碼在MSMR單跳無線網(wǎng)絡(luò)中的應(yīng)用

我們通過圖2來說明在多個發(fā)送方多個接收方的單跳無線網(wǎng)絡(luò)中，網(wǎng)絡(luò)編碼應(yīng)用于數(shù)據(jù)分組的重傳時，網(wǎng)絡(luò)性能的提升。圖中所示網(wǎng)絡(luò)模型為隨機(jī)網(wǎng)絡(luò)拓?fù)?，含?個節(jié)點(diǎn)，每個節(jié)點(diǎn)既可以是發(fā)送方也可以是接收方，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)公平競爭傳輸信道，每個節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組可以直接傳輸?shù)侥康墓?jié)點(diǎn)，因此網(wǎng)絡(luò)中不存在中繼節(jié)點(diǎn)。從圖中可以看出，節(jié)點(diǎn)1發(fā)送給目的節(jié)點(diǎn)3的數(shù)據(jù)分組P1傳輸失敗，節(jié)點(diǎn)2發(fā)送給目的節(jié)點(diǎn)4的數(shù)據(jù)分組P2也傳輸失敗，但是目的節(jié)點(diǎn)3偵聽到了節(jié)點(diǎn)2發(fā)送的數(shù)據(jù)分組P2，目的節(jié)點(diǎn)4偵聽到了節(jié)點(diǎn)1發(fā)送的數(shù)據(jù)分組P1，因此當(dāng)節(jié)點(diǎn)2在重傳時發(fā)送一個編碼分組P1P2時，目的節(jié)點(diǎn)3和目的節(jié)點(diǎn)4分別可以通過解碼編碼分組恢復(fù)丟失的數(shù)據(jù)分組P1和P2。簡而言之，在一個時隙內(nèi)，通過重傳一個編碼度為2的編碼包，得到了兩個數(shù)據(jù)分組，因此，在重傳中使用了網(wǎng)絡(luò)編碼的重傳機(jī)制，與傳統(tǒng)的ARQ機(jī)制相比有明顯的效率提升。

圖2 網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的應(yīng)用

顯然，在重傳中使用網(wǎng)絡(luò)編碼可以提升網(wǎng)絡(luò)性能，但是節(jié)點(diǎn)在重傳中傳輸?shù)木幋a分組應(yīng)該使用多大的編碼度N，即編碼分組由多少個丟失的數(shù)據(jù)分組編碼組合而成，我們還需要進(jìn)行分析。編碼度N越大，目的節(jié)點(diǎn)通過解碼編碼分組恢復(fù)丟失數(shù)據(jù)分組的概率就越小，因?yàn)槟康墓?jié)點(diǎn)需要存儲更多的副本分組，才能解碼。為此我們在所提出的RMBNC算法中研究了編碼度N對重傳效率的影響。另外，網(wǎng)絡(luò)中的節(jié)點(diǎn)個數(shù)對網(wǎng)絡(luò)性能也有明顯的影響，節(jié)點(diǎn)個數(shù)越多，數(shù)據(jù)分組的碰撞概率就越多，節(jié)點(diǎn)傳輸數(shù)據(jù)分組時丟失的概率也就會越大，因此我們需要研究節(jié)點(diǎn)個數(shù)對所提出算法的影響。

3 RMBNC算法在MSMR單跳無線網(wǎng)絡(luò)中的應(yīng)用

3.1 RMBNC算法的具體實(shí)現(xiàn)

在由多個發(fā)送方多個接收方組成的單跳無線網(wǎng)絡(luò)中，由于所有的數(shù)據(jù)分組都能由發(fā)送方直接傳輸給接收方，所以不存在中繼節(jié)點(diǎn)，網(wǎng)絡(luò)編碼不能用在直傳中，但是可以應(yīng)用于重傳中。RMBNC算法的基本思想是，源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組直傳失敗后，在第一次重傳中，源節(jié)點(diǎn)繼續(xù)發(fā)送該數(shù)據(jù)分組，當(dāng)該數(shù)據(jù)分組又一次傳輸失敗后，在第二次重傳中，源節(jié)點(diǎn)發(fā)送一個編碼度為N的編碼分組。編碼分組由源節(jié)點(diǎn)在直傳和第一次重傳中都傳輸失敗的那個數(shù)據(jù)分組和網(wǎng)絡(luò)中其它N-1個節(jié)點(diǎn)丟失的N-1個數(shù)據(jù)分組編碼組合而成。如果相應(yīng)的目的節(jié)點(diǎn)還不能通過解碼這個編碼分組得到該數(shù)據(jù)分組，則源節(jié)點(diǎn)不在重傳該數(shù)據(jù)分組，該丟失的數(shù)據(jù)分組可以通過網(wǎng)絡(luò)中其它節(jié)點(diǎn)發(fā)送到該目的節(jié)點(diǎn)的編碼分組來恢復(fù)，但是該丟失的數(shù)據(jù)分組在編碼分組中的最大傳輸次數(shù)不超過M次。下面我們給出RMBNC算法的具體實(shí)現(xiàn)過程。

S1源節(jié)點(diǎn)偵聽到信道空閑時，發(fā)送一個RTS，等待目的節(jié)點(diǎn)回復(fù)CTS。

S2收到目的節(jié)點(diǎn)發(fā)來的CTS，發(fā)送數(shù)據(jù)分組到目的節(jié)點(diǎn)。

S3當(dāng)源節(jié)點(diǎn)收到目的節(jié)點(diǎn)發(fā)送的ACK時，傳輸結(jié)束，當(dāng)收到NACK時，執(zhí)行第一次重傳。

S4第一次重傳時，當(dāng)源節(jié)點(diǎn)收到目的節(jié)點(diǎn)發(fā)送的ACK時，傳輸結(jié)束，當(dāng)收到NACK時，執(zhí)行第二次重傳。

S5第二次重傳時，節(jié)點(diǎn)發(fā)送一個編碼度為N的編碼分組。源節(jié)點(diǎn)收到ACK，傳輸結(jié)束，收到NACK，傳輸結(jié)束，不在執(zhí)行重傳。

為了在第二次重傳中使用網(wǎng)絡(luò)編碼發(fā)送編碼分組，每個節(jié)點(diǎn)必須保存一個表用來存儲網(wǎng)絡(luò)中丟失的數(shù)據(jù)分組，這個表用來記錄丟失數(shù)據(jù)分組的源地址，目的地址和數(shù)據(jù)分組的IP號，我們可以把這個表叫做NCTable。節(jié)點(diǎn)根據(jù)收到的ACK和NACK，更新NCTable表，當(dāng)某一個丟失的數(shù)據(jù)分組通過節(jié)點(diǎn)解碼編碼分組得到時，其它節(jié)點(diǎn)根據(jù)其發(fā)送的ACK，移除表中關(guān)于該數(shù)據(jù)分組的信息。

3.2 RMBNC算法的性能評估

我們通過飽和吞吐量和分組丟失率來評估RMBNC算法的性能，并與IEEE 802.11標(biāo)準(zhǔn)對比。

3.2.1 RMBNC算法的飽和吞吐量分析

與IEEE 802.11標(biāo)準(zhǔn)相比，RMBNC算法在第二次重傳中發(fā)送一個編碼度為N的編碼分組，網(wǎng)絡(luò)中的其它節(jié)點(diǎn)可以通過解碼編碼分組得到丟失的數(shù)據(jù)分組。這樣使得N個節(jié)點(diǎn)最多能通過一次傳輸?shù)玫絅個丟失數(shù)據(jù)分組，系統(tǒng)吞吐量會得到明顯提升，我們使用下面的公式來計算RMBNC算法的飽和吞吐量：

其中，ps表示數(shù)據(jù)分組成功傳輸?shù)母怕?，L表示數(shù)據(jù)分組的長度，p0表示節(jié)點(diǎn)具有N-1個用于解碼的副本分組的概率，pe表示傳輸出錯的概率。K表示發(fā)送數(shù)據(jù)分組時允許的最大沖突次數(shù)。PI，PS，PC，PE分別信道空閑的概率，傳輸成功的概率，碰撞概率，傳輸失敗概率，TI，TS，TC，TE分別表示信道空閑的時間，傳輸成功的時間，碰撞的時間，傳輸失敗的時間。

3.2.2 RMBNC算法的分組丟失率分析

與IEEE 802.11相比，本文所提出的RMBNC算法在分組丟失率性能上面的優(yōu)勢體現(xiàn)在節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組在直傳，第一次重傳，第二次重傳都失敗后，仍然可以通過網(wǎng)絡(luò)中其它節(jié)點(diǎn)在第二次重傳時發(fā)送的編碼分組來解碼得到丟失的數(shù)據(jù)分組。因此，RMBNC算法的分組丟失率會明顯的小于IEEE 802.11。我們通過下面的公式來計算RMBNC算法分組丟失率。

其中， 表示節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組時，達(dá)到最大沖突次數(shù)而丟分組， 表示節(jié)點(diǎn)因沖突次數(shù)達(dá)到K-1次，只有一次數(shù)據(jù)分組傳輸且傳輸失敗， 表示節(jié)點(diǎn)因沖突次數(shù)達(dá)到K-2次，只有二次數(shù)據(jù)分組傳輸，且兩次傳輸都失敗， 表示節(jié)點(diǎn)有3次傳輸機(jī)會，但3次傳輸都失敗。M表示節(jié)點(diǎn)丟失的數(shù)據(jù)分組在編碼分組中的最大重傳次數(shù)。

4 仿真分析

為驗(yàn)證RMBNC算法的優(yōu)越性能，我們使用飽和吞吐量和分組丟失率來評估網(wǎng)絡(luò)性能，并使用IEEE 802.11 MAC協(xié)議作為對比來分析RMBNC算法的性能。仿真中使用的參數(shù)如下所示pe=0.1，K=10，M=5，L=1 000 byte。

在圖3中，我們選擇50個節(jié)點(diǎn)作為仿真中網(wǎng)絡(luò)節(jié)點(diǎn)的個數(shù)，通過仿真分析了編碼度N對網(wǎng)絡(luò)吞吐量的影響。從圖中可以看出，RMBNC算法的吞吐量遠(yuǎn)遠(yuǎn)超過IEEE 802.11標(biāo)準(zhǔn)，在N=2時，RMBNC算法的吞吐量達(dá)到最大值。但是隨著N的增加，網(wǎng)絡(luò)吞吐量會逐漸的降低，因此RMBNC算法的編碼度N的選擇不能過大。

在圖4中，我們分析了編碼度對分組丟失率的影響。從圖中可以看出，RMBNC算法的分組丟失率明顯小于IEEE 802.11標(biāo)準(zhǔn)，但隨著編碼度N的增加，分組丟失率會逐漸的增大。仿真結(jié)果表明，RMBNC算法中，編碼度N的選擇要適中。

圖3 編碼度N為變量時，網(wǎng)絡(luò)吞吐量對比

圖4 編碼度N為變量時，分組丟失率對比

圖5中，我們選取的編碼度N為3，通過仿真分析節(jié)點(diǎn)個數(shù)對網(wǎng)絡(luò)吞吐量的影響。從圖中可以看出，RMBNC算法的飽和吞吐量遠(yuǎn)遠(yuǎn)高于IEEE 802.11。網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù)n對RMBNC算法飽和吞吐量有重要的影響，隨著n的增加，網(wǎng)絡(luò)吞吐量會逐漸的降低。

圖6中，我們可以看到，節(jié)點(diǎn)個數(shù)n對分組丟失率有很大的影響。隨著n的增加，分組丟失率迅速增大，但從圖中我們可以看到RMBNC算法在分組丟失率性能上依然優(yōu)于IEEE 802.11標(biāo)準(zhǔn)。

圖5 節(jié)點(diǎn)個數(shù)n為變量時，網(wǎng)絡(luò)吞吐量對比

圖6 節(jié)點(diǎn)個數(shù)為變量時，分組丟失率性能對比

5 總結(jié)和展望

本文提出了將網(wǎng)絡(luò)編碼應(yīng)用于多個發(fā)送方多個接收方單跳無線網(wǎng)絡(luò)中的算法RMBNC,并對算法進(jìn)行了理論推導(dǎo)和仿真分析。通過飽和吞吐量和分組丟失率這兩個性能指標(biāo)與IEEE 802.11標(biāo)準(zhǔn)進(jìn)行分析對比，仿真結(jié)果表明本文所提出算法的有效性。在接下來的工作中，我們將對影響RMBNC算法的其它因素進(jìn)行分析，并推導(dǎo)出該算法與IEEE 802.11標(biāo)準(zhǔn)在開銷，時延方面的性能對比。

[1] Ahlswede R, Cai N, Li S-Y, Yeung R. network information flow[J]. IEEE Transactions on Information Theory, vol. 46, no. 4,pp.1204-1216, July 2000.

[2] Nguyen D, Tran T, Nguyen T, Bose B. Wireless broadcast using network coding[J]. IEEE Transactions on Vehicular Technology,2009,58(4):914-925.

[3] Wu1 H, Zheng J. Efficient network coding-based multicast retransmission mechanism for mobile communication networks[J]. IET Communications, 2012(6):187-193.

[4] Xiao X, Yang L-M, Wang Wi-P, Zhang S. A wireless broadcasting,retransmission approach based on network coding”.IEEE International Conference on Circuits and Systems for Communications[C].2008,782-786,DOI:10.1109/ICCSC.2008.171,Published by: IEEE Communication Society.

[5] 肖瀟, 楊路明, 蒲保興. 基于網(wǎng)絡(luò)編碼的多節(jié)點(diǎn)無線廣播重傳策略研究[J]. 計算機(jī)應(yīng)用, 2008,28(4):849-852.

[6] 熊志強(qiáng), 黃佳慶, 劉威, 楊宗凱. 無線網(wǎng)絡(luò)編碼綜述[J]. 計算機(jī)科學(xué), 2007,34(3),6-10.

[7] IEEE Standard for Information Technology-Telecommunications and Information Exchange between Systems-Local and Metropolitan area Networks-Specific Requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[S]. IEEE Computer Society, 12 June 2007.

[8] Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000,18(3):535-547.