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

沈嘯

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

關(guān)鍵詞：無(wú)線網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；多路徑路由；編碼感知

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

1 網(wǎng)絡(luò)編碼技術(shù)概述

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

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

2.1 MPBNC多路徑路由算法設(shè)計(jì)

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

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

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

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

3.1 NCASR單路徑路由算法設(shè)計(jì)

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

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

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

4 結(jié)論

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

[參考文獻(xiàn)]

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

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

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