無線網(wǎng)絡中基于網(wǎng)絡編碼的路由算法

沈嘯

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

關鍵詞：無線網(wǎng)絡；網(wǎng)絡編碼；多路徑路由；編碼感知

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

1 網(wǎng)絡編碼技術概述

網(wǎng)絡編碼（Network Coding）是一種融合了路由與編碼的信息交換技術，其核心思想是在網(wǎng)絡各節(jié)點上對收集的信息進行線性或非線性處理，進而傳送到下游節(jié)點，與傳統(tǒng)通信網(wǎng)絡傳送數(shù)據(jù)的不同在于，中間節(jié)點在此過程中扮演的是編碼器的角色，而不是轉(zhuǎn)發(fā)器的角色。網(wǎng)絡編碼技術顛覆了傳統(tǒng)的數(shù)據(jù)傳輸方式，作為一種新的編碼算法，網(wǎng)絡編碼技術能夠?qū)F(xiàn)有的網(wǎng)絡吞吐量提高一倍，為改變當前基于路由的網(wǎng)絡架構帶來了希望。根據(jù)最大流-最小割定理，傳統(tǒng)的多播路由并不能達到數(shù)據(jù)傳輸流值的上界，而通過網(wǎng)絡編碼則可以達到多播路由傳輸?shù)淖畲罅鹘纾瑥亩岣邿o線傳輸效率[1]。

2 基于網(wǎng)絡編碼的多路徑路由算法

2.1 MPBNC多路徑路由算法設計

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

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

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

3 基于編碼感知的無線網(wǎng)絡單路徑路由算法

3.1 NCASR單路徑路由算法設計

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

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

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

4 結論

為了提高網(wǎng)絡吞吐量，提高無線網(wǎng)絡的性能，網(wǎng)絡編碼以及基于網(wǎng)絡編碼的路由算法應運而生，實踐證明，無線網(wǎng)絡中基于網(wǎng)絡編碼的路由算法能夠減少數(shù)據(jù)包傳輸?shù)拇螖?shù)，從而提高無線傳輸效率。

[參考文獻]

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

[2]王歡.無線網(wǎng)絡環(huán)境下基于網(wǎng)絡編碼的路由技術研究[D].中國科學技術大學.2011.

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