網絡編碼調度算法的研究

摘 要：近年來，網絡編碼作為提高通信系統吞吐量一種手段。在多播的通信網絡，網絡中各個傳送節點結合動態變化的網絡情況，對不同信息流的數據包進行編碼處理，從而減輕局部節點的阻塞，提高了整個通信系統的性能。文章主要工作要體現在典型無線通信網絡中，引入動態網絡編碼調度算法，提高無線通信系統的網絡編碼增益和系統吞吐量；探討在自適應無線通信系統下，如何適當的使用自適應技術，使得動態網絡編碼調度算法的作用發揮到最大。各個節點間的發送端更應選取適合的自適應技術，來提高無線通信系統性能。通過MATLAB仿真顯示，帶有自適應技術的無線網絡，在動態網絡編碼調度算法作用下，對改進系統性能有著更加重要的現實意義。

關鍵詞：網絡編碼；調度算法；自適應；無線通信

中圖分類號：TN91 文獻標識碼： A

1引言

近年來，因為無線通信技術的飛速發展，越來越多的人通過使用無線通信網絡連接到Internet上，如已經廣泛應用的WLan、LTE、Wimax等高速率無線接入技術。雖然無線接入速率提高越來越快，但是隨著移動通信網絡中的用戶數量和服務內容的激增，使得無線通信網絡對吞吐量的要求也在不斷提高。如何保證無線通信系統的吞吐量和提高現有無線頻譜資源的利用率，是提高無線網絡性能的關鍵問題所在，這些嶄新的研究方向已成為當今無線通信重要研究課題之一。

在2000年，Rudolf Ahlswede， Ning Cai和Shuo-Yen Robert Li在文獻?[1]中，三位教授提出了基于信息流的最小割最大理論，用于網絡節點的網絡編碼理論思想，該理論思想是把多播的信息流當做單播的信息流來處理，在網絡節點中進行編碼，最后按照路由信息把編碼好的信息發送出去。在2000年之后，通信界相繼有了很多網絡編碼研究成果被應用于各個方面，例如文獻[2][3]研究了網絡編碼理論思想可以提高網絡吞吐量，文獻[4][5]研究該思想可以用于保證通信網絡各條鏈路的可靠性、安全性和整個網絡的能量利用效率等方面。

在文獻[6]中，通信網絡中應用了網絡編碼理論思想后，網絡傳輸可以逼近網絡容量理論（非信道容量）傳輸極限。此方法已被國際學術界公認為比較可行的，且是解決如何提高網絡吞吐量的重要技術手段之一。 網絡編碼理論思想的創新思路對各個領域的科研理論研究工作有著重大的指導意義，而且在實踐方面的應用也是相當的活躍。

綜上所述，本文通過將網絡編碼理論思想應用到新一代無線通信技術中，使得無線通信網絡獲得更大的系統吞吐量。因為無線網絡中的節點具備對信息進行編碼的能力，通過利用節點的編碼，可提高無線通信網絡的各項通信性能指標。

2 無線網絡的調度算法

從信息傳輸的角度看，圖1在三個時隙就成功實現了信息的互換，與傳統的存儲轉發相比，在時間上節省了一個時隙[9][10]。但是，這樣的處理卻增加了網絡節點處理的復雜度。也就是說，該系統的信息處理的運算量增加了，傳輸的效率得到了提高。信息流f、信息流g代表和信息流h代表流入各個節點的信息。

當得到接收端的隊列信息和信道估計信息后，發送端計算出 和 ，但是該調度算法是否可以應用，還需計算信道的容量C。比較 、 與C間的關系：

當 或 時，說明編碼節點中的隊列結構中的數據包差別較大，需迅速縮小這種差別，但受控于一定的系統功率，我們只能在一定的信道容量下盡可能的提高 或 ；當 時，我們可以按照實際的 或者 發送的同時，也可以通過改變調制方式，增加發送數據的信息量。

在動態網絡編碼調度算法中，該算法以提高系統的吞吐量為目標，從而忽略了無線環境中的信道衰落、BER等因素。在自適應的系統中，該算法充分考慮了無線環境中的各個因素，綜合確定一個實用性強的動態網絡編碼調度算法。

我們選擇無線環境中較為常用的無線鏈路模型（Nakagami信道）作為仿真的無線信道，依據圖3的MATLAB仿真流程圖進行仿真程序的編寫。在TD-LTE的網絡測試中的經驗，當接受信噪比 小于0的時候，說明該信號強度屬于較差的信號；當接收信噪比 時，說明該信號強度屬于中等的信號；當接收信噪比 時，說明該信號的強度屬于優。因此在MATLAB仿真中，我們選取接收信噪比 取值區間為[0，10]，令信道帶寬B=20MHz，確定系統的平均功率 為一個常數，然后求其在不同衰落信道下的信道容量。

從仿真結果圖4中可以看出，在有損信道下，無論通信系統是否采用自適應技術和調度算法，有損信道容量都比無損信道的容量小。收發兩端已知CSI的香農容量都比AWGN信道容量小。在發送端，信息發送速率都不能大于信道的容量，否則就會產生比較大的誤碼率。從仿真的結果看，在較為真實的統計傳輸鏈路模型中，因為信道的容量比理想的無損信道的容量都要小，因而在無線通信網絡中使用動態網絡編碼調度算法非常有必要獲取收發兩端的CSI，因為只有這樣才能更好地應用該動態調度算法，防止在調度過程中產生較大的誤比特率，保證傳輸的服務質量和可靠性。

從圖4中可以看到，在有損信道中，當接收信噪比較低的的情況下， ，有無自適應技術和調度算法的使用情況下，信道的容量都幾乎相等。這就是說明在信道較差的情況下，調度算法的使用對系統性能的改進沒有什么作用。但是采用自適應技術后，在 情況下，信道的容量得到明顯的增加，雖然不至于等于無損信道的容量，但是在使用調度算法進行網絡編碼后，信道容量得到明顯改善。

在平均誤比特率的不變的情況下，用MATLAB編程仿真，可得到在不同衰落的信道和是否采用動態網絡編碼調度算法的情況下的仿真圖4，在相同的時間內，比較其系統吞吐量的情況：在無損信道下，整個系統的系統的吞吐量在任何時間段內都是最大的；在采用自適應技術的有損信道下，整個系統的的吞吐量比無損信道下的吞吐量小，但是在時間t>5s時，采用自適應技術的有損信道的吞吐量開始比無自適應技術的有損信道的吞吐量大；從圖5中可以明顯看出即使采用了編碼調度算法，但是如果沒有自適應技術對抗有損信道的衰落，系統的吞吐量與無損信道或者采用自適應技術的有損信道都相差比較大。

在平均誤比特率的不變的情況下，用MATLAB編程仿真功率控制和速率都可變的MQAM。圖6中三條曲線表示的是采用動態編碼調度策略后，在Nakagami衰落下的平均頻帶利用率。從MATLAB仿真結果可以看出，在相同的BER和信道衰落下，采用連續功率、連續速率自適應的MQAM的動態網絡編碼調度算法的頻譜利用率是最大的；其次就是連續功率、離散速率的算法；最小的情況是離散功率、離散速率的算法。雖然采用連續的自適應動態網絡編碼調度算法，但是在實際應用中會加大通信系統的運算量復雜度和功耗等，大大降低傳輸系統的性能。圖6中可以看出，連續性的自適應調度算法比離散型的調度算法大概造成約1個bit/s/Hz的性能損失，但是在調節的反應速度和系統功耗方面都有較好的表現。

5 總結

綜合各個方面，為了提高整個傳輸系統的性能，我們采用了折中的處理方案，選取離散功率、離散速率的MQAM動態網絡編碼調度算法是最好的選擇。在采用該算法后，無線通信系統的吞吐量得到提高，頻譜利用率得到提高。

參考文獻

[1]Ahlswede R，Cai N， Li S-Y R，et a1. Network information flow[J].IEEE Transactions on Information Theory：2000，46（4）：1204-1216

[2]Bollobas B，Graph Theory. An Introductory Course[M]. New York：Springer-Verlag，1979.

[3]Wu Y N，Chou P A，Kung S Y. Information exchange in wireless networks with network coding and physical-layer broadcast[J]： Microsoft Research，Aug 2006 Technical Report MSR-TR-2004.7-8

[4]Cai N，Yeung RW. Network Coding and Error Correction[J].ITW，Bangalore，2002

[5]Widmer J，Fragouli C，Boudec J-Y L. Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[J]. In：Proc.1 st Workshop on Network Coding Theory and Applications，Riva del Garda，Italy，Apr 2005

[6]楊林，鄭剛. 網絡編碼的研究進展[J]. 計算機研究與發展，2008，45（3）：400-407

[7]Goldsmith A. Wireless communications[M]. Cambridge University Press，2007.

[8]Neely M. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time-Varying Channels[J]，Ph.D. dissertation MIT Cambridge MA， 2003

[9]Li S Y，Yeung R W，et al. Linear network coding[J]. Information Theory，IEEE Transactions on 49（2）： 371-381.

[10]Li S Y，Yeung R W，et al. Linear Network Coding： Theory and Algorithms. Proceedings of the IEEE 2011：372-387.

[11]Sanders P，Egner S，Tolhuizen L. Polynomial time algorithms for network information flow[J]. ACM Symposium on Parallel Algorithms and Architectures；2003：286-294

[12]樊平毅.網絡信息論[M].清華大學出版社.2009 第一版：45

[13]馬祎. 網絡編碼調度的排隊與調度分析[J].清華大學電子工程系；2007.

[14]Rager S T，Ciftcioglu E N，et al. Distributed backpressure protocols with limited state feedback[J]. military communications conference，2011.

[15]Klein T，Viswanathan H. Centralized power control in multihop wireless networks[J]. IEEE Information Theory. Lausanne，Switzerland. Jun-Jul. 2003.