一種基于網(wǎng)絡(luò)編碼的重傳算法研究*

吳陽(yáng)陽(yáng)，魏辰, 王久鵬

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

在由多個(gè)發(fā)送方多個(gè)接收方組成的單跳無(wú)線網(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ā)送一個(gè)編碼度為N的編碼分組。編碼分組由源節(jié)點(diǎn)在直傳和第一次重傳中都傳輸失敗的那個(gè)數(shù)據(jù)分組和網(wǎng)絡(luò)中其它N-1個(gè)節(jié)點(diǎn)丟失的N-1個(gè)數(shù)據(jù)分組編碼組合而成。如果相應(yīng)的目的節(jié)點(diǎn)還不能通過(guò)解碼這個(gè)編碼分組得到該數(shù)據(jù)分組，則源節(jié)點(diǎn)不在重傳該數(shù)據(jù)分組，該丟失的數(shù)據(jù)分組可以通過(guò)網(wǎng)絡(luò)中其它節(jié)點(diǎn)發(fā)送到該目的節(jié)點(diǎn)的編碼分組來(lái)恢復(fù)，但是該丟失的數(shù)據(jù)分組在編碼分組中的最大傳輸次數(shù)不超過(guò)M次。下面我們給出RMBNC算法的具體實(shí)現(xiàn)過(guò)程。

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

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

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

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

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

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

3.2 RMBNC算法的性能評(píng)估

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

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

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

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

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

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

其中， 表示節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組時(shí)，達(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ī)會(huì)，但3次傳輸都失敗。M表示節(jié)點(diǎn)丟失的數(shù)據(jù)分組在編碼分組中的最大重傳次數(shù)。

4 仿真分析

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

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

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

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

圖4 編碼度N為變量時(shí)，分組丟失率對(duì)比

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

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

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

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

5 總結(jié)和展望

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

[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)無(wú)線廣播重傳策略研究[J]. 計(jì)算機(jī)應(yīng)用, 2008,28(4):849-852.

[6] 熊志強(qiáng), 黃佳慶, 劉威, 楊宗凱. 無(wú)線網(wǎng)絡(luò)編碼綜述[J]. 計(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.