魏 濤，張治國

(河南工程學院 計算機學院，河南 鄭州 451191)

與傳統(tǒng)的WLAN相比，MESH是一個多跳性的網(wǎng)絡，任何無線設備節(jié)點都可以作為無線接入點.無線MESH網(wǎng)絡更加注重網(wǎng)絡的中繼多跳能力，能實現(xiàn)更加靈活的組網(wǎng)方式，數(shù)據(jù)包可以根據(jù)網(wǎng)絡的情況，路由到與其最近的下一個節(jié)點進行，不一定非要通過網(wǎng)絡中的單點傳輸數(shù)據(jù).它與傳統(tǒng)的點到多點的無線接入方式相比有很多優(yōu)點[1].MESH本質(zhì)上屬于移動自組網(wǎng)絡(Ad hoc 網(wǎng)絡)，但與Ad hoc比較，其網(wǎng)絡節(jié)點的移動性較弱，拓撲變化較小.這種組網(wǎng)方式節(jié)省了網(wǎng)絡建設初期的基礎設施投資.另外，無線MESH網(wǎng)絡已作為解決“最后一公里”的網(wǎng)絡接入問題的方案寫入IEEE標準之中.

MESH網(wǎng)絡路由算法一直是研究的熱點和難點.近年來，有許多新的路由協(xié)議方案提出[2].由于MESH網(wǎng)絡本質(zhì)上是一種特殊的Ad hoc網(wǎng)絡，所以部分傳統(tǒng)的Ad hoc網(wǎng)絡路由協(xié)議在MESH中仍然可用，如AODV，DSR，DSDV等路由協(xié)議.本研究首先分析了應用于MESH網(wǎng)絡中的路由協(xié)議，然后在AODV協(xié)議的基礎上提出了一種新的路由算法，即利用多徑路由與在多路徑之間隨機選擇的路由，仿真結(jié)果表明這是一種有效的路由算法.

1 Ad hoc路由協(xié)議分析

應用于Ad hoc網(wǎng)絡的路由協(xié)議大體上可以分為3種類型：(1)先驗式的路由協(xié)議，如基于目的序列號距離矢量(DSDV)協(xié)議；(2)反應式的路由協(xié)議，如AODV，DSR等協(xié)議；(3)混合式的路由協(xié)議，如ZRP[3]協(xié)議，混合式的路由協(xié)議是先驗式路由協(xié)議和反應式路由協(xié)議的組合.

1.1 先驗式路由協(xié)議

先驗式路由協(xié)議也被稱為表驅(qū)動路由選擇協(xié)議，也就是網(wǎng)絡中的每個節(jié)點都需要維護本節(jié)點到其他節(jié)點的路由信息，所有節(jié)點都要定期更新路由表以反映網(wǎng)絡拓撲的變化.如果源節(jié)點要發(fā)送報文，可以立即得到到達目的節(jié)點的路由信息.顯然，先驗式的路由協(xié)議在網(wǎng)絡拓撲變化不大的情況下性能較好，但如果網(wǎng)絡拓撲變化較大，則各節(jié)點需要頻繁地發(fā)送路由檢測信息，從而會占用很多網(wǎng)絡資源，開銷很大.顯然，對于無線網(wǎng)絡而言，由于其拓撲變化較大，單純地使用這種路由協(xié)議并不適合.

1.2 反應式路由協(xié)議

反應式路由協(xié)議也稱為按需要路由，它并不需要網(wǎng)絡中的每個節(jié)點都維護實時準確的路由信息，只在需要發(fā)送數(shù)據(jù)時才做路由探測，找到正確的傳送路徑.這種方式推遲了路由信息的建立，不需要時時探測網(wǎng)絡拓撲的變化，因而占用的網(wǎng)絡資源較小，網(wǎng)絡的利用率也能得到提高.在Ad hoc這種拓撲結(jié)構(gòu)隨時間變化很大的網(wǎng)絡中，應用反應式路由協(xié)議顯然是一種較好的選擇.但由于在進行數(shù)據(jù)傳輸時才尋找路由，所以對單個業(yè)務的傳輸在時延等方面存在缺陷.

1.3 混合式的路由協(xié)議

混合式路由協(xié)議結(jié)合了先驗式路由和反應式路由的優(yōu)點，它的主要思想是網(wǎng)絡內(nèi)的節(jié)點維護一個以自己為中心的簇，在簇內(nèi)使用先驗式路由算法，簇外節(jié)點的路由使用反應式路由算法.但該路由協(xié)議的實施存在困難，如簇的選擇、算法的實現(xiàn)有較大的系統(tǒng)開銷等問題.

2 AODV路由機制

AODV路由協(xié)議是一種反應式的路由協(xié)議，當一個移動節(jié)點要向其他節(jié)點發(fā)送數(shù)據(jù)而本節(jié)點的路由表中不存在到達目的節(jié)點的路由信息時，就會發(fā)起路由發(fā)現(xiàn)過程，通過廣播路由請求(RREQ)信息來查找相應路由[4]，路由請求報文包括源節(jié)點地址、源節(jié)點序號、目的節(jié)點地址、目的節(jié)點序號、上一跳地址、跳數(shù)等信息.每個接收到路由請求報文的節(jié)點會先建立到達源節(jié)點的反向路由信息，然后檢查自己是否是目的節(jié)點.如果是，則通過反向路由信息向源節(jié)點發(fā)送路由響應報文；如果不是，則檢查自己的路由表中是否有到達目的節(jié)點的路由信息，若有，則代替目的節(jié)點向源節(jié)點發(fā)送路由響應報文，路由發(fā)現(xiàn)過程結(jié)束,否則將更新路由請求報文，并將更新后的報文以廣播方式轉(zhuǎn)發(fā)出去，直到目的節(jié)點收到或路由請求報文超時而報錯.在AODV協(xié)議中，如果存在多個到達目的節(jié)點的路徑，源節(jié)就點會根據(jù)路由請求報文中跳數(shù)最小的路徑作為最優(yōu)路徑存儲到路由表中，丟棄其他的路由信息.

在路由維護過程中，每個路由節(jié)點周期性地發(fā)送狀態(tài)通知報文，如果節(jié)點在一定時間內(nèi)沒有收到鄰居節(jié)點發(fā)來的狀態(tài)通知報文，則認為該鄰居節(jié)點不可達，它馬上檢查路由表中被使用的該鄰居節(jié)點的路由信息，并發(fā)送路由失敗報文.AODV協(xié)議不需要維護無用的路由，當網(wǎng)絡拓撲變化時，它能及時地發(fā)現(xiàn)過期、失效的路由.因此,在拓撲結(jié)構(gòu)變化較大的網(wǎng)絡環(huán)境中能達到較好的效果.

3 AODV路由改進設計

無線MESH網(wǎng)絡的通信鏈路不像有線網(wǎng)絡那樣穩(wěn)定，需要MESH路由協(xié)議保證當一條鏈路有問題時能及時找到新的路徑替代，以增強網(wǎng)絡的健壯性.同時，為了公平地共享網(wǎng)絡資源，當某處出現(xiàn)擁塞時，路由協(xié)議要能調(diào)整分組路由到負載較輕的鏈路上.因此,使多路徑路由能夠很好地分配通信量、平衡負載，成為近年來研究的熱點.

圖1 路由請求報文從節(jié)點1轉(zhuǎn)發(fā)到節(jié)點5Fig.1 Route request message from node 1 to node 5 forwarding

在傳統(tǒng)的AODV路由協(xié)議中，只保存了從源節(jié)點到目的節(jié)點的跳數(shù)最小的路徑，顯然如果每個節(jié)點能夠保存多條到達目的節(jié)點的路徑，則當其中的一條路徑不可達時，數(shù)據(jù)包也可通過其他的路徑到達目的節(jié)點，具體實例見圖1.

如圖1所示，雖然存在兩條路徑，即1-2-5和1-3-4-5，但路徑1-3-4-5發(fā)送信息時，所經(jīng)跳數(shù)多，將會被節(jié)點1丟棄.顯然如果節(jié)點2失效，或由于節(jié)點5的移動，超出了節(jié)點2的信號覆蓋范圍，節(jié)點1就需要重新發(fā)起路由探尋過程.同樣在數(shù)據(jù)傳輸中，如果所有的數(shù)據(jù)都經(jīng)1-2-5路徑，發(fā)生擁塞的概率將會比較大.上述問題的產(chǎn)生，主要是因為AODV協(xié)議采用的是單路徑路由，如果采用多路徑路由，則會有效地提高網(wǎng)絡利用率，減少擁塞現(xiàn)象的發(fā)生.

改進后的AODV路由協(xié)議采用多路徑路由，以下簡稱為RAODV.在進行路由探測時，如果發(fā)現(xiàn)多條能夠到達目的節(jié)點的路由，則將保存這多條路徑信息，在進行路由選擇時，將分組轉(zhuǎn)發(fā)分散到這多條路徑上，從而實現(xiàn)負載均衡,提高分組轉(zhuǎn)發(fā)的可靠性.改進后的算法借鑒了隨機早期檢測[5](RED)算法的思想.RED算法是一種主動隊列管理算法，其主要思想是在分組隊列發(fā)生擁塞之前，利用概率判定機制丟掉部分分組來預防可能發(fā)生的擁塞，即分組以概率P被丟棄，概率P的值與當前平均隊列的長度有關.

RAODV協(xié)議在路由探測階段，首先廣播路由請求報文，而后源節(jié)點可能會收到多個路由響應報文，在源節(jié)點中，保存多條路徑，并且保存從源節(jié)點到目的節(jié)點的路由跳數(shù)，用于在轉(zhuǎn)發(fā)分組時確定選擇路徑的概率.在圖1中，節(jié)點1發(fā)出能夠到達節(jié)點5的路由探測報文RREQ，此時會收到兩條路由響應報文，而且有可能節(jié)點3的路由響應報文比節(jié)點2的路由響應報文先到達節(jié)點1，這是因為節(jié)點3中有可能存在有到節(jié)點5的路由信息，而節(jié)點2中還沒有到達節(jié)點5的路由信息，需要節(jié)點2再次進行探測.RAODV將保存這兩條路由信息，當節(jié)點1向節(jié)點5發(fā)送數(shù)據(jù)時，將從這兩條路徑中選擇一條轉(zhuǎn)發(fā)數(shù)據(jù)包，選擇時，跳數(shù)最少的路徑被選中的概率大，因為在無線網(wǎng)絡中，跳數(shù)越少表明數(shù)據(jù)包途經(jīng)的中間節(jié)點數(shù)越少.

分裂式多路徑協(xié)議SMR[6]是基于DSR的多路徑路由協(xié)議，由于在進行路由探測時需要攜帶源節(jié)點到目的節(jié)點的完整路由信息，所以其有效數(shù)據(jù)負載不大；NDMR[7]路由協(xié)議是在AODV協(xié)議和DSR協(xié)議的基礎上改進的多路徑路由，研究重點在于發(fā)現(xiàn)多條獨立的路徑，而要發(fā)現(xiàn)多條獨立的路徑需要的路由請求包較多，因而路由建立的時間較長，路由開銷也較大，在拓撲變化較快的網(wǎng)絡環(huán)境中并不合適.RAODV協(xié)議并不把重點放在建立獨立路徑之上，因為路由開銷不大，在轉(zhuǎn)發(fā)時以隨機方式選擇轉(zhuǎn)發(fā)的路徑即可.具體選擇哪條路徑進行數(shù)據(jù)包轉(zhuǎn)發(fā)可按如下概率來計算：

P=1-(本路徑所經(jīng)跳數(shù))/所有路徑跳數(shù)之和.

(1)

這樣，跳數(shù)越小的路徑，被選中的概率越大.在進行報文發(fā)送時，如果兩條路徑上到達目的節(jié)點的跳數(shù)相同，則它們被選中的概率相同.通過生成的隨機數(shù)與兩個相同的概率值比較，使得數(shù)據(jù)包以相同的可能性在兩條路徑之間傳遞.其他的路徑也有被選中的機會，因為在傳遞數(shù)據(jù)包的時候，從源節(jié)點到目的節(jié)點，不再是從一條路徑傳遞，而是分散在多條路徑上傳遞數(shù)據(jù)包，這樣使單一路徑上出現(xiàn)擁塞的可能性降低，從而可以較好地平衡流量，提高分組傳輸?shù)目煽啃?在路由維護階段，當跳數(shù)最短的路徑失效時，將重新啟動路由發(fā)現(xiàn)過程，而其他路徑失效時不作處理.在AODV.cc文件中，計算發(fā)送數(shù)據(jù)時所選路徑代碼如下：

for (rt=rtable.head(); rt; rt=rtn) //對于每一條路由信息

{intp=1-rt->hops/rtable.counts; //計算每條路由的跳數(shù)

if (random()>p) //以隨機方式選擇路徑

{forward(rt, Packet, No_delay);

break;}}

4 仿真結(jié)果

性能仿真在Linux系統(tǒng)下的NS2[8]平臺進行.50個節(jié)點隨機分布在500 m×500 m的矩形區(qū)域，仿真時間為100 s，傳送CBR業(yè)務，最大移動速度為20 m/s，分別在節(jié)點的停留時間為0 s,20 s,40 s,60 s,80 s,100 s時進行測試.利用工具cbrgen.tcl生成業(yè)務場景文件，利用NS自帶的setdest生成移動場景文件.仿真比較了DSR協(xié)議、AODV協(xié)議及改進的RAODV協(xié)議的端到端平均時延及分組投遞率，如圖2和圖3所示.

節(jié)點移動的速度反映了網(wǎng)絡拓撲變化的快慢.從圖2中可以看到隨著網(wǎng)絡節(jié)點停留時間的延長，端到端的時延有明顯的下降，從圖3中可以看出AODV的分組投遞率略高于DSR，而改進后的RAODV協(xié)議的分組投遞率高于AODV協(xié)議.

圖2 端到端平均時延Fig.2 Average delay of end-to-end

5 結(jié)語

多路徑路由協(xié)議是無線MESH網(wǎng)絡中的一個研究熱點，多路徑路由能很好地平衡通信量、平衡網(wǎng)絡負載，具有加快傳輸速度、減少時延的優(yōu)點.本研究提出了一種改進的AODV協(xié)議，采用多路徑路由機制，以從源節(jié)點到目標節(jié)點跳數(shù)的多少為依據(jù)選擇路徑，從實驗結(jié)果來看，改進后的路由協(xié)議在時延和分組投遞率方面有了改進.

參考文獻：

[1] Akyildiz I F，Wang X D．A survey on wireless mesh network [J].IEEE Communications Magazine,2005,43(9):23-30.

[2] 秦裕斌，陳建華，黃曉．無線MESH網(wǎng)絡技術及其應用[J]．通信技術，2009，42(12)：152-154.

[3] 楊羽.基于ZRP的Ad Hoc網(wǎng)絡路由協(xié)議的優(yōu)化研究[J].遼東學院學報:自然科學版,2009(3):227-231.

[4] 謝世歡，郭偉．實現(xiàn)Ad hoc按需路由協(xié)議的關鍵技術[J]．計算機應用，2006，26(3)：11-13.

[5] Floyd S,Jacobson V.Random early detection gateways for congestion avoidance[J]．ACM/IEEE Transactions on Networking,1993,1(4):397-413．

[6] 李悅,陳翔.基于Ad Hoc網(wǎng)絡的SMR優(yōu)化算法的研究[J].計算機與現(xiàn)代化，2012(5)：21-24．

[7] Li X F，Laurie C．On-demand node-disjoint multipath routing in wireless ad hoc networks[C]∥In 29th Annual IEEE International Conference on Local Computer Networks.Washington:LCN，2004：419-420．

[8] 徐雷鳴,龐博,趙耀．NS與網(wǎng)絡模擬[M]．北京:人民郵電出版社,2003.