無線網絡中基于網絡編碼的路由算法

沈嘯

摘 要：網絡編碼為無線網絡帶來了更高的可靠性，二者的結合已經引起了很多研究學者的關注，無線網絡中基于網絡編碼的路由算法更是值得探討和研究的問題，本文在網絡編碼的基礎上分別對網絡編碼的多路徑路由算法和編碼感知的路由算法進行了分析和研究，以期實現提高無線傳輸效率的目標。

關鍵詞：無線網絡；網絡編碼；多路徑路由；編碼感知

隨著信息技術的迅速發展以及移動通訊技術應用的日益廣泛，無線網絡的覆蓋范圍擴張明顯，如何提高無線傳輸效率，已經成為研究學者關注的重要問題之一，網絡編碼的提出則讓人們看到了最大限度利用網絡資源的有效路徑，網絡編碼技術被認為是解決無線傳輸問題的重要手段，現就無線網絡中基于網絡編碼的路由算法問題進行研究，有其重要的理論指導意義。

1 網絡編碼技術概述

網絡編碼（Network Coding）是一種融合了路由與編碼的信息交換技術，其核心思想是在網絡各節點上對收集的信息進行線性或非線性處理，進而傳送到下游節點，與傳統通信網絡傳送數據的不同在于，中間節點在此過程中扮演的是編碼器的角色，而不是轉發器的角色。網絡編碼技術顛覆了傳統的數據傳輸方式，作為一種新的編碼算法，網絡編碼技術能夠將現有的網絡吞吐量提高一倍，為改變當前基于路由的網絡架構帶來了希望。根據最大流-最小割定理，傳統的多播路由并不能達到數據傳輸流值的上界，而通過網絡編碼則可以達到多播路由傳輸的最大流界，從而提高無線傳輸效率[1]。

2 基于網絡編碼的多路徑路由算法

2.1 MPBNC多路徑路由算法設計

MPBNC是一種基于網絡編碼的多路徑路由算法，主要利用多路徑上存在的可能性編碼，在路由發現階段從目的節點向源節點返回多條路徑，并從中選擇編碼機會較多的路徑，進而根據編碼機會的多少來對流量進行分割。在路徑發現階段，多路徑路由可以根據節點之間的關聯性來劃分為三個種類：鏈路不相交、節點不相交以及相交多路徑。鏈路不相交路徑指的是路徑間沒有共用的路徑，節點不相交路徑指的是路徑間沒有共同節點和共用路徑，相交多路徑則是指路徑間既有共同節點也有共用路徑。MPBNC多路徑路由的發現過程分為四個階段，分別是產生路由請求分組、處理路由請求分組和處理路由響應分組，整個階段結束后，源節點就會從多路徑中選取最優路徑傳輸數據，即具有編碼機會的路徑在單位時間內能夠傳輸更多的數據，分配更多的流量。

2.2 MPBNC多路徑路由仿真及性能分析

為了測試MPBNC的效率，可以通過NS2仿真模型來實現，NS2是一款開放源代碼的網絡協議模擬軟件，同時也是一款非常出色的分析各種網絡協議的仿真工具，這里所說的網絡協議包括了計算機網絡協議、衛星網絡協議、無線網絡協議以及應用層協議。NS2中的構件由分別在C++和Otcl中相關聯的兩個類來實現，這種仿真模型能夠增強整個構件庫的組合性和擴展性。網絡編碼的優點在于能夠提高網絡吞吐量，仿真的目的就是從網絡吞吐量上評估MPBNC多路徑路的性能，MPBNC算法按照編碼機會的多少在返回路徑中對流量進行分割，因此能夠傳輸更多的數據，其網絡吞吐量自然就會提高[2]。

3 基于編碼感知的無線網絡單路徑路由算法

3.1 NCASR單路徑路由算法設計

NCASR是一種基于編碼感知的無線網絡單路徑路由算法，通過設置適用于多個數據包的編碼增益公式，在路由發現階段從源節點和目的節點之間的傳輸路徑上選擇編碼機會較多的最優路徑進行數據傳輸。這種路由模式實際上是將網絡編碼技術與網絡層的路由有機地結合在一起，以此來實現逼近網絡容量理論傳輸極限的可能。無線網絡的路由選取應根據一定的度量標準來找到一條最優的路徑，該度量標準即為路由判據，常用的路由判據主要有跳數、每跳往返時間、平均傳輸次數、平均傳輸時間等，路由判據的選取應考慮到無線網絡傳輸路徑的真實特性，只有以此為度量標準，才能找到最優路徑，從而提高網絡吞吐量以及無線傳輸效率。NCASR單路徑路由的發現過程分為四個階段，分別是產生路由請求分組、更新分組信息、回復分組信息、計算編碼增益、選取最大的編碼增益值，整個階段結束后，源節點就會從多路徑中選取最優路徑傳輸數據，即具有編碼機會的路徑在單位時間內能夠傳輸更多的數據，分配更多流量。

3.2 NCASR單路徑路由仿真及性能分析

為了測試NCASR的效率，同樣可以通過NS2仿真模型來實現，仿真參數類型主要包括無線信號傳輸模型、網絡接口、MAC層協議、接口隊列、鏈路層、節點傳輸半徑等類型，仿真模型主要從網絡吞吐量來評估NCASR算法的性能。NCASR算法與傳統的COPE算法在不同發送速率下的平均吞吐量是不同的，當網絡符合增加到一定值時（通常是55kdps），二者所反映的吞吐量就會出現明顯的差異，隨著數據流的不斷增加，NCASR能夠主動尋找更多的編碼機會的路由，因此，NCASR平均吞吐量的增量將持續大于COPE。由此可見，NCASR能夠將編碼增益作為路由的選擇判據，并以此為依據選擇最小代價的路徑去傳輸最大限量的網絡容量，從而提高無線傳輸效率[3]。

4 結論

為了提高網絡吞吐量，提高無線網絡的性能，網絡編碼以及基于網絡編碼的路由算法應運而生，實踐證明，無線網絡中基于網絡編碼的路由算法能夠減少數據包傳輸的次數，從而提高無線傳輸效率。

[參考文獻]

[1]田賢忠.無線網絡中基于網絡編碼的路由算法[D].浙江工業大學.2013.

[2]王歡.無線網絡環境下基于網絡編碼的路由技術研究[D].中國科學技術大學.2011.

[3]陳貴海，李宏興，韓松，鐘子飛，陳明達.多跳無線網絡中基于網絡編碼的多路徑路由[J].軟件學報.2010，13（8）：19-20.