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

?

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

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

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

2　ENCWBR方法

（1）依次尋找緩存矩陣每一行中首個(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?？偣残枰獋鬏?次。

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

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

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

3　ENCWBR方法的仿真分析

對(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)?矩陣。

圖4　ENCWBR的仿真流程圖

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

圖5　ENCWBR的仿真流程圖

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

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

參考文獻(xiàn)

［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］.微型機(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é)強(qiáng).一種有效降低重傳次數(shù)的S-ARQ技術(shù)［C］.2006年全國(guó)無線電應(yīng)用與管理學(xué)術(shù)會(huì)議，2006.

［7］王練，雷芳.基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)重傳方案綜述［J］.重慶郵電大學(xué)學(xué)報(bào)（自然科學(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é)報(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］.中國(guó)郵電高校學(xué)報(bào)（英文版），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］.微型機(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

作者簡(jiǎn)介：

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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（61372087）

中圖分類號(hào)：TN934

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.023