薛琰1， 孟利民2

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

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

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

0引言

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

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

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

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

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

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

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

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

2ENCWBR方法

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

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

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

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

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

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

3ENCWBR方法的仿真分析

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

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

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

4結(jié)論

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

　　參考文獻

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

　　［2］ 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］. 微型機與應(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.

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

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

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

　　［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ǎng)絡(luò)廣播重傳方法［J］. 通信學(xué)報, 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］. 中國郵電高校學(xué)報（英文版）, 2013, 20(1):95100.