薛琰1,， 孟利民2
（1. 浙江工業(yè)大學(xué) 信息工程學(xué)院,，浙江 杭州 3100232. 浙江省通信網(wǎng)技術(shù)應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室,，浙江 杭州 310023）
摘要：近年來(lái)，網(wǎng)絡(luò)編碼技術(shù)理論飛速發(fā)展,，為提高無(wú)線(xiàn)網(wǎng)絡(luò)傳輸?shù)耐掏侣屎涂煽啃蕴峁┝诵碌膯l(fā)點(diǎn),。首先介紹了網(wǎng)絡(luò)編碼理論的發(fā)展現(xiàn)狀和線(xiàn)性網(wǎng)絡(luò)編碼理論，然后構(gòu)建了無(wú)線(xiàn)網(wǎng)絡(luò)重傳模型,，對(duì)原有的網(wǎng)絡(luò)編碼無(wú)線(xiàn)廣播重傳（NCWBR）算法和改進(jìn)型網(wǎng)絡(luò)編碼無(wú)線(xiàn)廣播重傳（ENCWBR）算法進(jìn)行了MATLAB仿真,，證明了ENCWBR算法在高丟包率的條件下確實(shí)可以很好地控制重傳次數(shù)。
關(guān)鍵詞：網(wǎng)絡(luò)編碼,；無(wú)線(xiàn)網(wǎng)絡(luò),；重傳次數(shù)
0引言
廣播是無(wú)線(xiàn)網(wǎng)絡(luò)通信的一種常見(jiàn)模式，但是由于無(wú)線(xiàn)信道較有線(xiàn)信道更為惡劣,，重傳是必要的,。傳統(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ú)線(xiàn)網(wǎng)絡(luò)的吞吐率,，并實(shí)現(xiàn)最大流傳輸［3］,。
KOETTER R討論了一種網(wǎng)絡(luò)編碼的代數(shù)方法［4］；呂玉萍等人［5］說(shuō)明了運(yùn)用網(wǎng)絡(luò)編碼在無(wú)線(xiàn)網(wǎng)絡(luò)中優(yōu)化傳輸效率的方法,；陳娟等人［6］提出一種有效減少重傳次數(shù)的改進(jìn)ARQ技術(shù),；王練等人［7］總結(jié)了無(wú)線(xiàn)網(wǎng)絡(luò)重傳方案的多種方法；KATTI S等人［8］通過(guò)使用完全機(jī)會(huì)編碼來(lái)構(gòu)建無(wú)線(xiàn)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ú)線(xiàn)網(wǎng)絡(luò)模型和問(wèn)題描述
圖1展示了緩沖矩陣的一個(gè)例子,，通過(guò)接收節(jié)點(diǎn)的ACK和NAK反饋而創(chuàng)建。在這個(gè)矩陣當(dāng)中,，0代表接收節(jié)點(diǎn)成圖1無(wú)線(xiàn)網(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ù)包。
?。?）將數(shù)據(jù)包放入編碼序列,，把相應(yīng)的位置重置為0。
?。?）使用網(wǎng)絡(luò)編碼異或在編碼序列中的數(shù)據(jù)包,，然后廣播編碼包,，依次發(fā)送第一個(gè)批次的編碼包、第二個(gè)批次的編碼包,，直到緩沖矩陣更新為0,。
（4）接收節(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):12041216.
?。?］ Zhang Zhenyu, Li Ming, Lou Wenjing.Rcode:network codingbased 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):3334.
?。?］ KOETTER R, DARD M. An algebraic approach to network coding［C］. IEEE/ACM Transactions on Networking, 2003:782795.
?。?］ 呂玉萍. 基于網(wǎng)絡(luò)編碼的無(wú)線(xiàn)網(wǎng)絡(luò)重傳方法研究［D］. 成都：西南交通大學(xué), 2014.
［6］ 陳娟, 張玉明, 鄭學(xué)強(qiáng). 一種有效降低重傳次數(shù)的SARQ技術(shù)［C］. 2006年全國(guó)無(wú)線(xiàn)電應(yīng)用與管理學(xué)術(shù)會(huì)議,， 2006.
?。?］王練, 雷芳. 基于網(wǎng)絡(luò)編碼的無(wú)線(xiàn)網(wǎng)絡(luò)重傳方案綜述［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012,，24（5）：664668.
［8］ 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ú)線(xiàn)網(wǎng)絡(luò)廣播重傳方法［J］. 通信學(xué)報(bào), 2009, 30(9):6975.
?。?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):95100.