薛琰1,， 孟利民2

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

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

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

0引言

　　廣播是無線網(wǎng)絡(luò)通信的一種常見模式，但是由于無線信道較有線信道更為惡劣，重傳是必要的,。傳統(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ǎng)絡(luò)的吞吐率,，并實(shí)現(xiàn)最大流傳輸［3］。

　　KOETTER R討論了一種網(wǎng)絡(luò)編碼的代數(shù)方法［4］,；呂玉萍等人［5］說明了運(yùn)用網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中優(yōu)化傳輸效率的方法,；陳娟等人［6］提出一種有效減少重傳次數(shù)的改進(jìn)ARQ技術(shù)；王練等人［7］總結(jié)了無線網(wǎng)絡(luò)重傳方案的多種方法,；KATTI S等人［8］通過使用完全機(jī)會(huì)編碼來構(gòu)建無線Mesh網(wǎng)絡(luò)減小重傳次數(shù),； 肖瀟等人［9］提出NCWBR算法使用XOR方法來組合丟失的數(shù)據(jù)包，并通過中心節(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)過MATLAB仿真表明，這種方法確實(shí)會(huì)減少重傳次數(shù),，在對(duì)實(shí)時(shí)性要求不高的場(chǎng)景下,，會(huì)有很好的應(yīng)用。

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

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

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

　　NCWBR的步驟如下：中心節(jié)點(diǎn)從緩沖矩陣中依次搜索每一行中的第一個(gè)1，并把這些包放入編碼包序列來編碼,，在編碼完畢后廣播第一個(gè)批次的編碼包1⊕2⊕3⊕4⊕5,，廣播的編碼包就可以在節(jié)點(diǎn)R1、R2,、R3,、R4、R5與原來存儲(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,。

　　（3）使用網(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,。總共需要傳輸5次,。

　　圖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)立起來構(gòu)成一個(gè)異或方程組,，就可以解每個(gè)數(shù)據(jù)包,，所以總共需要4次重傳。實(shí)際上ENCWBR利用了緩沖節(jié)點(diǎn)的存儲(chǔ)能力,，通過后續(xù)到達(dá)的包進(jìn)行解碼,。使用ENCWBR方法時(shí)，不管接收節(jié)點(diǎn)是否成功解碼相應(yīng)的數(shù)據(jù)包,，都不需要給中心節(jié)點(diǎn)傳送NAK,，所以ENCWBR方法減少了整個(gè)網(wǎng)絡(luò)的開銷。

3ENCWBR方法的仿真分析

　　對(duì)于一般重傳方法,、NCWBR方法和ENCWBR方法,，分別使用MATLAB進(jìn)行建模分析。先構(gòu)建概率矩陣,，設(shè)數(shù)據(jù)包的丟失概率為p=0.2,，由此代表緩沖矩陣，再通過編碼包逐步把矩陣變?yōu)?矩陣,，代表矩陣解碼成功,。通過計(jì)算發(fā)送編碼包的次數(shù)來代表重傳的次數(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)

　　［1］ 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.

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

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

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

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

　?。?］王練, 雷芳. 基于網(wǎng)絡(luò)編碼的無線網(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ǎng)絡(luò)廣播重傳方法［J］. 通信學(xué)報(bào), 2009, 30(9):6975.

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