薛琰1， 孟利民2

　?。?. 浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 3100232. 浙江省通信網(wǎng)技術(shù)應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310023）

　　摘要：近年來(lái)，網(wǎng)絡(luò)編碼技術(shù)理論飛速發(fā)展，為提高無(wú)線網(wǎng)絡(luò)傳輸?shù)耐掏侣屎涂煽啃蕴峁┝诵碌膯l(fā)點(diǎn)。首先介紹了網(wǎng)絡(luò)編碼理論的發(fā)展現(xiàn)狀和線性網(wǎng)絡(luò)編碼理論，然后構(gòu)建了無(wú)線網(wǎng)絡(luò)重傳模型，對(duì)原有的網(wǎng)絡(luò)編碼無(wú)線廣播重傳（NCWBR）算法和改進(jìn)型網(wǎng)絡(luò)編碼無(wú)線廣播重傳（ENCWBR）算法進(jìn)行了MATLAB仿真，證明了ENCWBR算法在高丟包率的條件下確實(shí)可以很好地控制重傳次數(shù)。

　　關(guān)鍵詞：網(wǎng)絡(luò)編碼；無(wú)線網(wǎng)絡(luò)；重傳次數(shù)

0引言

　　廣播是無(wú)線網(wǎng)絡(luò)通信的一種常見(jiàn)模式，但是由于無(wú)線信道較有線信道更為惡劣，重傳是必要的。傳統(tǒng)的重傳方式比較浪費(fèi)網(wǎng)絡(luò)資源，比如自動(dòng)重發(fā)請(qǐng)求（Automatic Repeat Request ，ARQ）模式，對(duì)于每一個(gè)丟失的包都要一一重傳。所以有必要探索新的重傳方式。

　　在2000年，AHLSWEDE R等人［１］首次提出了網(wǎng)絡(luò)編碼的概念，由此改變了人們對(duì)于網(wǎng)絡(luò)傳輸中中間節(jié)點(diǎn)的觀念，即中間節(jié)點(diǎn)不僅可以扮演存儲(chǔ)轉(zhuǎn)發(fā)的角色，還可以對(duì)數(shù)據(jù)包進(jìn)行計(jì)算和編碼［2］。網(wǎng)絡(luò)編碼是通信領(lǐng)域的重大突破，核心觀點(diǎn)是中間節(jié)點(diǎn)集成路由和編碼的功能。使用網(wǎng)絡(luò)編碼可以有效地改善無(wú)線網(wǎng)絡(luò)的吞吐率，并實(shí)現(xiàn)最大流傳輸［3］。

　　KOETTER R討論了一種網(wǎng)絡(luò)編碼的代數(shù)方法［4］；呂玉萍等人［5］說(shuō)明了運(yùn)用網(wǎng)絡(luò)編碼在無(wú)線網(wǎng)絡(luò)中優(yōu)化傳輸效率的方法；陳娟等人［6］提出一種有效減少重傳次數(shù)的改進(jìn)ARQ技術(shù)；王練等人［7］總結(jié)了無(wú)線網(wǎng)絡(luò)重傳方案的多種方法；KATTI S等人［8］通過(guò)使用完全機(jī)會(huì)編碼來(lái)構(gòu)建無(wú)線Mesh網(wǎng)絡(luò)減小重傳次數(shù)； 肖瀟等人［9］提出NCWBR算法使用XOR方法來(lái)組合丟失的數(shù)據(jù)包，并通過(guò)中心節(jié)點(diǎn)向接收節(jié)點(diǎn)廣播組合包，但是當(dāng)同一個(gè)節(jié)點(diǎn)在組合包中有多于一個(gè)的丟失包時(shí)，將會(huì)造成解碼速率的降低。本文根據(jù)Yao Xukun等人提出的網(wǎng)絡(luò)編碼高效率多播解碼（Efficient Multipacket Decoding Network Coding， EMDNC）方法改進(jìn)了原有NCWBR方法［10］，經(jīng)過(guò)MATLAB仿真表明，這種方法確實(shí)會(huì)減少重傳次數(shù)，在對(duì)實(shí)時(shí)性要求不高的場(chǎng)景下，會(huì)有很好的應(yīng)用。

　　1無(wú)線網(wǎng)絡(luò)模型和問(wèn)題描述

　　圖1展示了緩沖矩陣的一個(gè)例子，通過(guò)接收節(jié)點(diǎn)的ACK和NAK反饋而創(chuàng)建。在這個(gè)矩陣當(dāng)中，0代表接收節(jié)點(diǎn)成圖1無(wú)線網(wǎng)絡(luò)的NCWBR例子

　　功收到數(shù)據(jù)包，而1代表接收節(jié)點(diǎn)接收數(shù)據(jù)包失敗。通過(guò)構(gòu)建緩沖矩陣可以完全反映這一次傳輸?shù)那闆r，傳輸模型中包括5個(gè)接收節(jié)點(diǎn)和10個(gè)傳送包，構(gòu)成一個(gè)批次。

　　NCWBR的步驟如下：中心節(jié)點(diǎn)從緩沖矩陣中依次搜索每一行中的第一個(gè)1，并把這些包放入編碼包序列來(lái)編碼，在編碼完畢后廣播第一個(gè)批次的編碼包1⊕2⊕3⊕4⊕5，廣播的編碼包就可以在節(jié)點(diǎn)R1、R2、R3、R4、R5與原來(lái)存儲(chǔ)的編碼包異或分別解碼。

　　但如果丟失數(shù)據(jù)包6和8，當(dāng)R2接收編碼包6⊕7⊕8⊕9⊕10時(shí)，節(jié)點(diǎn)R2不能恢復(fù)這些丟失包。每當(dāng)這個(gè)情況發(fā)生時(shí)，網(wǎng)絡(luò)需要更多的重傳次數(shù)，這樣就會(huì)降低網(wǎng)絡(luò)的性能?？紤]到這種情況，本文提出了一種新的算法，利用每個(gè)節(jié)點(diǎn)的存儲(chǔ)能力，增加解碼效率。

2ENCWBR方法

　?。?）依次尋找緩存矩陣每一行中首個(gè)為1的數(shù)據(jù)包。

　　（2）將數(shù)據(jù)包放入編碼序列，把相應(yīng)的位置重置為0。

　?。?）使用網(wǎng)絡(luò)編碼異或在編碼序列中的數(shù)據(jù)包，然后廣播編碼包，依次發(fā)送第一個(gè)批次的編碼包、第二個(gè)批次的編碼包，直到緩沖矩陣更新為0。

　?。?）接收節(jié)點(diǎn)接收到所有的編碼包以后，利用所有的編碼包進(jìn)行解碼，如果不能解碼，則反饋給中心節(jié)點(diǎn)，中心節(jié)點(diǎn)重新更新緩沖矩陣，跳到步驟（1）。

　　圖2展示了使用NCWBR的例子。中間節(jié)點(diǎn)廣播編碼包的組合1⊕2⊕3⊕4⊕5、1⊕6⊕7、3⊕8⊕9⊕10、4⊕11，然后單獨(dú)傳輸數(shù)據(jù)包9?？偣残枰獋鬏?次。

　　圖3展示了ENCWBR的例子，中心節(jié)點(diǎn)廣播第一個(gè)編碼組合包1⊕2⊕3⊕4⊕5，這個(gè)編碼組合包不能在節(jié)點(diǎn)R1進(jìn)行解碼，R1將這個(gè)編碼包放入緩存當(dāng)中。然后R1收到第二個(gè)編碼包3⊕6⊕7，依然把它放入緩存當(dāng)中，再接收第三個(gè)編碼4⊕8⊕9⊕10放入緩存中，最后重傳編碼包9⊕11，把4個(gè)編碼包聯(lián)立起來(lái)構(gòu)成一個(gè)異或方程組，就可以解每個(gè)數(shù)據(jù)包，所以總共需要4次重傳。實(shí)際上ENCWBR利用了緩沖節(jié)點(diǎn)的存儲(chǔ)能力，通過(guò)后續(xù)到達(dá)的包進(jìn)行解碼。使用ENCWBR方法時(shí)，不管接收節(jié)點(diǎn)是否成功解碼相應(yīng)的數(shù)據(jù)包，都不需要給中心節(jié)點(diǎn)傳送NAK，所以ENCWBR方法減少了整個(gè)網(wǎng)絡(luò)的開(kāi)銷(xiāo)。

3ENCWBR方法的仿真分析

　　對(duì)于一般重傳方法、NCWBR方法和ENCWBR方法，分別使用MATLAB進(jìn)行建模分析。先構(gòu)建概率矩陣，設(shè)數(shù)據(jù)包的丟失概率為p=0.2，由此代表緩沖矩陣，再通過(guò)編碼包逐步把矩陣變?yōu)?矩陣，代表矩陣解碼成功。通過(guò)計(jì)算發(fā)送編碼包的次數(shù)來(lái)代表重傳的次數(shù)。為簡(jiǎn)化仿真，不考慮編碼包的丟失。

　　采用NCWBR方法，MATLAB仿真流程圖如圖4所示。首先尋找每一行的第一個(gè)1，尋找完以后放入編碼包進(jìn)行異或編碼處理，并廣播編碼包，廣播完編碼包以后重傳次數(shù)retram就加1，如果不能解碼就重新把緩存矩陣相應(yīng)位置重置為1，進(jìn)行迭代，直到矩陣變?yōu)?矩陣。

　　ENCWBR的MATLAB仿真圖如圖5所示。在ENCWBR方法中一次性發(fā)送全部的編碼包，等接收點(diǎn)接收全部編碼包以后再判定是否可以解碼。然后反饋解碼情況，更新緩沖矩陣以后，再次編碼并發(fā)送編碼包，直到數(shù)據(jù)包全被解碼完畢。如圖5所示，先輸入緩沖矩陣，尋找編碼包，找到每一行的第一個(gè)1，放入編碼包，并把相應(yīng)地位置置0，相應(yīng)地重傳計(jì)數(shù)值retram加1，如此構(gòu)建多個(gè)編碼包，當(dāng)全部發(fā)送且接收節(jié)點(diǎn)接收全部編碼包以后判定是否可以解碼。給出相應(yīng)的反饋，更新緩沖矩陣，進(jìn)行迭代，直到矩陣變?yōu)?。

4結(jié)論

　　分別將數(shù)據(jù)包丟失概率p設(shè)置為0.02和0.2。如圖6所示，在數(shù)據(jù)包丟失概率p=0.02的情況下，由于丟失的數(shù)據(jù)包比較分散，ARQ對(duì)每一個(gè)數(shù)據(jù)包都要重傳，因此重傳次數(shù)較大，而NCWBR和ENCWBR能夠?qū)?shù)據(jù)包進(jìn)行編碼，所以降低了重傳次數(shù)，且當(dāng)數(shù)據(jù)包丟失概率較小時(shí)，NCWBR和ENCWBR都能解碼成功，兩者差別不大。而當(dāng)數(shù)據(jù)包丟失概率p=0.2的情況下，如圖7所示，當(dāng)節(jié)點(diǎn)較少時(shí)，NCWBR可以很好地控制重傳次數(shù)，要優(yōu)于傳統(tǒng)的一般ARQ，但當(dāng)節(jié)點(diǎn)數(shù)目增多時(shí)，由于NCWBR中不能解碼的節(jié)點(diǎn)的數(shù)量增多，造成編碼機(jī)會(huì)的浪費(fèi)，其重傳次數(shù)甚至大于一般ARQ，而ENCWBR方法可以很好地控制重傳的次數(shù)，提高了解碼效率，在多節(jié)點(diǎn)的情況下依舊可以很好地控制重傳次數(shù)。

　　參考文獻(xiàn)

　?。?］ AHISWEDE R, Cai Ning, LI S Y R, et al. Network Information Flow［C］. IEEE Transactions on Information Theory, 2000,46(4):12041216.

　?。?］ Zhang Zhenyu, Li Ming, Lou Wenjing.Rcode:network codingbased reliable broadcast in wireless mesh networks［J］. Ad Hoc Networks, 2011, 9(5):788–798.

　　［3］ 胡平. 一種網(wǎng)絡(luò)編碼構(gòu)造算法研究［J］. 微型機(jī)與應(yīng)用, 2010,29(5):3334.

　?。?］ KOETTER R, DARD M. An algebraic approach to network coding［C］. IEEE/ACM Transactions on Networking, 2003:782795.

　　［5］ 呂玉萍. 基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)重傳方法研究［D］. 成都：西南交通大學(xué), 2014.

　?。?］ 陳娟, 張玉明, 鄭學(xué)強(qiáng). 一種有效降低重傳次數(shù)的SARQ技術(shù)［C］. 2006年全國(guó)無(wú)線電應(yīng)用與管理學(xué)術(shù)會(huì)議， 2006.

　?。?］王練, 雷芳. 基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)重傳方案綜述［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012，24（5）：664668.

　?。?］ KATTI S, RAHUL H, HU W, et al. XORs in the air: practical wireless network coding［J］. IEEE/ACM Transactions on Networking , 2008, 16(3):497  510.

　?。?］ 肖瀟, 王偉平, 楊路明,等. 基于網(wǎng)絡(luò)編碼的無(wú)線網(wǎng)絡(luò)廣播重傳方法［J］. 通信學(xué)報(bào), 2009, 30(9):6975.

　?。?0］ Yao Yukun, Wen Yadi, Ren Zhi, et al. High efficient multipacket decoding approach for network coding in wireless networks［J］. 中國(guó)郵電高校學(xué)報(bào)（英文版）, 2013, 20(1):95100.