基于線性網絡編碼重傳算法的MATLAB仿真分析*

薛　琰，孟利民（.浙江工業大學信息工程學院，浙江杭州3003 .浙江省通信網技術應用研究重點實驗室，浙江杭州3003）

?

基于線性網絡編碼重傳算法的MATLAB仿真分析*

薛琰1，孟利民2
（1.浙江工業大學信息工程學院，浙江杭州310023 2.浙江省通信網技術應用研究重點實驗室，浙江杭州310023）

摘 要：近年來，網絡編碼技術理論飛速發展，為提高無線網絡傳輸的吞吐率和可靠性提供了新的啟發點。首先介紹了網絡編碼理論的發展現狀和線性網絡編碼理論，然后構建了無線網絡重傳模型，對原有的網絡編碼無線廣播重傳（NCWBR）算法和改進型網絡編碼無線廣播重傳（ENCWBR）算法進行了MATLAB仿真，證明了ENCWBR算法在高丟包率的條件下確實可以很好地控制重傳次數。

關鍵詞：網絡編碼；無線網絡；重傳次數

0　引言

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

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

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

1　無線網絡模型和問題描述

圖1展示了緩沖矩陣的一個例子，通過接收節點的ACK和NAK反饋而創建。在這個矩陣當中，0代表接收節點成功收到數據包，而1代表接收節點接收數據包失敗。通過構建緩沖矩陣可以完全反映這一次傳輸的情況，傳輸模型中包括5個接收節點和10個傳送包，構成一個批次。

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

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

圖1　無線網絡的NCWBR例子

2　ENCWBR方法

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

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

圖2展示了使用NCWBR的例子。中間節點廣播編碼包的組合1⊕2⊕3⊕4⊕5、1⊕6⊕7、3⊕8⊕9⊕10、4⊕11，然后單獨傳輸數據包9。總共需要傳輸5次。

圖2　無線網絡的NCWBR例子

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

圖3　無線網絡ENCWBR例子

3　ENCWBR方法的仿真分析

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

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

圖4　ENCWBR的仿真流程圖

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

4　結論

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

圖5　ENCWBR的仿真流程圖

圖6　p=0.02的情況下三者的重傳次數

圖7　p=0.2的情況下三者的重傳次數

參考文獻

［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］胡平.一種網絡編碼構造算法研究［J］.微型機與應用，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］呂玉萍.基于網絡編碼的無線網絡重傳方法研究［D］.成都：西南交通大學，2014.

［6］陳娟，張玉明，鄭學強.一種有效降低重傳次數的S-ARQ技術［C］.2006年全國無線電應用與管理學術會議，2006.

［7］王練，雷芳.基于網絡編碼的無線網絡重傳方案綜述［J］.重慶郵電大學學報（自然科學版），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］肖瀟，王偉平，楊路明，等.基于網絡編碼的無線網絡廣播重傳方法［J］.通信學報，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］.中國郵電高校學報（英文版），2013，20（1）：95-100.

薛琰（1989 -），男，碩士研究生，主要研究方向：線性網絡編碼。

孟利民（1963 -），女，博士，教授，主要研究方向：無線通信與網絡，智能信息系統，網絡管理，多媒體數字通信與網絡。

引用格式：薛琰，孟利民.基于線性網絡編碼重傳算法的MATLAB仿真分析［J］.微型機與應用，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）

*基金項目：國家自然科學基金項目（61372087）

中圖分類號：TN934

文獻標識碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.023