薛琰1， 孟利民2
（1. 浙江工業大學 信息工程學院，浙江 杭州 3100232. 浙江省通信網技術應用研究重點實驗室，浙江 杭州 310023）
摘要：近年來，網絡編碼技術理論飛速發展，為提高無線網絡傳輸的吞吐率和可靠性提供了新的啟發點。首先介紹了網絡編碼理論的發展現狀和線性網絡編碼理論，然后構建了無線網絡重傳模型，對原有的網絡編碼無線廣播重傳（NCWBR）算法和改進型網絡編碼無線廣播重傳（ENCWBR）算法進行了MATLAB仿真，證明了ENCWBR算法在高丟包率的條件下確實可以很好地控制重傳次數。
關鍵詞：網絡編碼；無線網絡；重傳次數
0引言
廣播是無線網絡通信的一種常見模式，但是由于無線信道較有線信道更為惡劣，重傳是必要的。傳統的重傳方式比較浪費網絡資源，比如自動重發請求（Automatic Repeat Request ，ARQ）模式，對于每一個丟失的包都要一一重傳。所以有必要探索新的重傳方式。
在2000年，AHLSWEDE R等人［１］首次提出了網絡編碼的概念，由此改變了人們對于網絡傳輸中中間節點的觀念，即中間節點不僅可以扮演存儲轉發的角色，還可以對數據包進行計算和編碼［2］。網絡編碼是通信領域的重大突破，核心觀點是中間節點集成路由和編碼的功能。使用網絡編碼可以有效地改善無線網絡的吞吐率，并實現最大流傳輸［3］。
KOETTER R討論了一種網絡編碼的代數方法［4］；呂玉萍等人［5］說明了運用網絡編碼在無線網絡中優化傳輸效率的方法；陳娟等人［6］提出一種有效減少重傳次數的改進ARQ技術；王練等人［7］總結了無線網絡重傳方案的多種方法；KATTI S等人［8］通過使用完全機會編碼來構建無線Mesh網絡減小重傳次數； 肖瀟等人［9］提出NCWBR算法使用XOR方法來組合丟失的數據包，并通過中心節點向接收節點廣播組合包，但是當同一個節點在組合包中有多于一個的丟失包時，將會造成解碼速率的降低。本文根據Yao Xukun等人提出的網絡編碼高效率多播解碼（Efficient Multipacket Decoding Network Coding， EMDNC）方法改進了原有NCWBR方法［10］，經過MATLAB仿真表明，這種方法確實會減少重傳次數，在對實時性要求不高的場景下，會有很好的應用。
1無線網絡模型和問題描述
圖1展示了緩沖矩陣的一個例子，通過接收節點的ACK和NAK反饋而創建。在這個矩陣當中，0代表接收節點成圖1無線網絡的NCWBR例子
功收到數據包，而1代表接收節點接收數據包失敗。通過構建緩沖矩陣可以完全反映這一次傳輸的情況，傳輸模型中包括5個接收節點和10個傳送包，構成一個批次。
NCWBR的步驟如下：中心節點從緩沖矩陣中依次搜索每一行中的第一個1，并把這些包放入編碼包序列來編碼，在編碼完畢后廣播第一個批次的編碼包1⊕2⊕3⊕4⊕5，廣播的編碼包就可以在節點R1、R2、R3、R4、R5與原來存儲的編碼包異或分別解碼。
但如果丟失數據包6和8，當R2接收編碼包6⊕7⊕8⊕9⊕10時，節點R2不能恢復這些丟失包。每當這個情況發生時，網絡需要更多的重傳次數，這樣就會降低網絡的性能。考慮到這種情況，本文提出了一種新的算法，利用每個節點的存儲能力，增加解碼效率。
2ENCWBR方法
（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次。
圖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方法減少了整個網絡的開銷。
3ENCWBR方法的仿真分析
對于一般重傳方法、NCWBR方法和ENCWBR方法，分別使用MATLAB進行建模分析。先構建概率矩陣，設數據包的丟失概率為p=0.2，由此代表緩沖矩陣，再通過編碼包逐步把矩陣變為0矩陣，代表矩陣解碼成功。通過計算發送編碼包的次數來代表重傳的次數。為簡化仿真，不考慮編碼包的丟失。
采用NCWBR方法，MATLAB仿真流程圖如圖4所示。首先尋找每一行的第一個1，尋找完以后放入編碼包進行異或編碼處理，并廣播編碼包，廣播完編碼包以后重傳次數retram就加1，如果不能解碼就重新把緩存矩陣相應位置重置為1，進行迭代，直到矩陣變為0矩陣。
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方法可以很好地控制重傳的次數，提高了解碼效率，在多節點的情況下依舊可以很好地控制重傳次數。
參考文獻
［1］ AHISWEDE R, Cai Ning, LI S Y R, et al. Network Information Flow［C］. IEEE Transactions on Information Theory, 2000,46(4):12041216.
［2］ Zhang Zhenyu, Li Ming, Lou Wenjing.Rcode:network codingbased reliable broadcast in wireless mesh networks［J］. Ad Hoc Networks, 2011, 9(5):788–798.
［3］ 胡平. 一種網絡編碼構造算法研究［J］. 微型機與應用, 2010,29(5):3334.
［4］ KOETTER R, DARD M. An algebraic approach to network coding［C］. IEEE/ACM Transactions on Networking, 2003:782795.
［5］ 呂玉萍. 基于網絡編碼的無線網絡重傳方法研究［D］. 成都：西南交通大學, 2014.
［6］ 陳娟, 張玉明, 鄭學強. 一種有效降低重傳次數的SARQ技術［C］. 2006年全國無線電應用與管理學術會議， 2006.
［7］王練, 雷芳. 基于網絡編碼的無線網絡重傳方案綜述［J］.重慶郵電大學學報（自然科學版）， 2012，24（5）：664668.
［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.
［9］ 肖瀟, 王偉平, 楊路明,等. 基于網絡編碼的無線網絡廣播重傳方法［J］. 通信學報, 2009, 30(9):6975.
［10］ Yao Yukun, Wen Yadi, Ren Zhi, et al. High efficient multipacket decoding approach for network coding in wireless networks［J］. 中國郵電高校學報（英文版）, 2013, 20(1):95100.