薛　琰，孟利民（.浙江工業(yè)大學(xué)信息工程學(xué)院，浙江杭州3003 .浙江省通信網(wǎng)技術(shù)應(yīng)用研究重點實驗室，浙江杭州3003）

?

基于線性網(wǎng)絡(luò)編碼重傳算法的MATLAB仿真分析*

薛琰1，孟利民2
（1.浙江工業(yè)大學(xué)信息工程學(xué)院，浙江杭州310023 2.浙江省通信網(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等人［1］首次提出了網(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ò)重傳方案的多種方法；KATTIS等人［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é)點成功收到數(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é)點的存儲能力，增加解碼效率。

圖1　無線網(wǎng)絡(luò)的NCWBR例子

2　ENCWBR方法

（1）依次尋找緩存矩陣每一行中首個為1的數(shù)據(jù)包。（2）將數(shù)據(jù)包放入編碼序列，把相應(yīng)的位置重置為0。（3）使用網(wǎng)絡(luò)編碼異或在編碼序列中的數(shù)據(jù)包，然后廣播編碼包，依次發(fā)送第一個批次的編碼包、第二個批次的編碼包，直到緩沖矩陣更新為0。

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

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

圖2　無線網(wǎng)絡(luò)的NCWBR例子

圖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ò)的開銷。

圖3　無線網(wǎng)絡(luò)ENCWBR例子

3　ENCWBR方法的仿真分析

對于一般重傳方法、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)?矩陣。

圖4　ENCWBR的仿真流程圖

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ù)。

圖5　ENCWBR的仿真流程圖

圖6　p=0.02的情況下三者的重傳次數(shù)

圖7　p=0.2的情況下三者的重傳次數(shù)

參考文獻

［1］AHISWEDE R，Cai Ning，LIS Y R，et al.Network Information Flow［C］. IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

［2］Zhang Zhenyu，LiMing，Lou Wenjing.R-code：network codingbased reliable broadcast in wirelessmesh networks［J］.Ad Hoc Networks，2011，9（5）：788 - 798.

［3］胡平.一種網(wǎng)絡(luò)編碼構(gòu)造算法研究［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.

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

［6］陳娟，張玉明，鄭學(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］KATTIS，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.

［9］肖瀟，王偉平，楊路明，等.基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)廣播重傳方法［J］.通信學(xué)報，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é)報（英文版），2013，20（1）：95-100.

薛琰（1989 -），男，碩士研究生，主要研究方向：線性網(wǎng)絡(luò)編碼。

孟利民（1963 -），女，博士，教授，主要研究方向：無線通信與網(wǎng)絡(luò)，智能信息系統(tǒng)，網(wǎng)絡(luò)管理，多媒體數(shù)字通信與網(wǎng)絡(luò)。

引用格式：薛琰，孟利民.基于線性網(wǎng)絡(luò)編碼重傳算法的MATLAB仿真分析［J］.微型機與應(yīng)用，2016，35（10）：67-69.

The MATLAB simulation of network broadcast retransmission algorithm based on linear network coding

Xue Yan1，Meng Limin2
（1.College of Information Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.Zhejiang Province Key Laboratory of Communication Networks，Hangzhou 310023，China）

Abstrac t：In recent years，network coding technology is developing very quickly.It provides a good inspiration to enhance reliability and throughput rate of wireless network transmission.Firstly，the paper describes the current status of the development of network coding and linear network theory，then constructs the model of wireless network transmission.The paper simulates the network coding wireless broadcast retransmission（NCWBR）algorithm and enhanced network coding wireless broadcast retransmission（ENCWBR），and it proves that ENCWBR does enhance the effectiveness of the wireless network retransmission.

Key w ords：network coding；wireless network；times of retransmission

作者簡介：

收稿日期：（2015-12-22）

*基金項目：國家自然科學(xué)基金項目（61372087）

中圖分類號：TN934

文獻標(biāo)識碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.023