基于AODV的無線Mesh網(wǎng)絡路由協(xié)議優(yōu)化設計

胡伏湘

(長沙商貿(mào)旅游職業(yè)技術學院信息系，中國 長沙　410116)

基于AODV的無線Mesh網(wǎng)絡路由協(xié)議優(yōu)化設計

胡伏湘*

(長沙商貿(mào)旅游職業(yè)技術學院信息系，中國 長沙410116)

摘要無線Mesh網(wǎng)絡(WMN)融合了WLAN和Ad hoc網(wǎng)絡的優(yōu)勢，具有高速、多跳和自組織的特點，廣泛用于會場、醫(yī)院和車站等場合.由于其開放性和無線鏈路，導致路由協(xié)議效率不高．針對Ad hoc單跳路由的缺陷，從WMN的體系結構入手，提出了設計原則和方法，并在AODV的基礎上，通過修改數(shù)據(jù)包的格式，優(yōu)化設計了相應的網(wǎng)絡協(xié)議，并給出了相應的路由算法，然后選擇時延和負載兩個核心指標，在OPNET平臺上進行了仿真實現(xiàn)，結果表明，15個節(jié)點組成的WMN和4個節(jié)點的網(wǎng)絡相比，其關鍵指標值優(yōu)勢明顯，說明這種算法更加適合于規(guī)模較大的網(wǎng)絡．

關鍵詞無線Mesh網(wǎng)絡；路由協(xié)議；AODV；數(shù)據(jù)包；OPNET

Optimization Design of Routing Protocol of

Wireless Mesh Network Based on Aodv

HUFu-xiang*

(Department of Information, Changsha Commerce and Tourism College, Changsha 410116, China)

AbstractCombining the merits of WLAN and the Ad hoc network, Wireless Mesh Network(WMN) has the characteristics of high speed, multi-hop, self-organization, and can be widely used in the venue, hospital, station, etc. However, the routing protocol is low efficiency due to its openness and wireless link. Aiming at overcoming defects of the single hop routing of Ad hoc, this paper puts forward the design principles and basic methods, which starts from the architecture of WMN. On the basis of AODV, optimization design of the network protocol and the corresponding algorithm are presented by modifying the packet format. Finally, the protocols are simulated on the OPNET platform using two key indexes of delay and load. The results show that the MWN with 15 nodes is superior comparing with 4 modes. Therefore, the algorithm is more suitable for larger networks.

Key wordsWireless Mesh Network; routing protocol; AODV; package; OPNET

無線Mesh網(wǎng)絡(Wireless Mesh Network-WMN)是一種基于IP協(xié)議的無線寬帶接入技術，它融合了WLAN和Ad hoc兩者的優(yōu)勢，支持多點對多點的網(wǎng)狀通信模式，具有自動組網(wǎng)、自動修復、多跳級聯(lián)和節(jié)點自我管理等智能優(yōu)勢以及移動性、寬帶寬和無線定位的特點，是一種高速率、大容量和寬覆蓋范圍的網(wǎng)絡，是解決最后1km無線寬帶接入瓶頸問題的理想方案．任意無線設備節(jié)點在接入此網(wǎng)絡后，既能發(fā)送和接收信號，又具備路由轉發(fā)功能，即充當路由器，能同時與一個或多個對等節(jié)點直接通信.其最大好處在于：如果鄰近的AP由于流量過大而導致?lián)砣?，?shù)據(jù)可以自動重新路由到一個通信流量較小的相鄰節(jié)點傳輸，直到送達最終目的地，即多跳訪問.因而被廣泛應用于會場、醫(yī)院、機場、學校和小區(qū)等各種場合[1-2]．

WMN最初源于軍事領域，應用在戰(zhàn)場上的移動網(wǎng)絡需要極高的數(shù)據(jù)速率、極低的被檢出概率和防外來干擾的能力.隨著802.11局域網(wǎng)技術的深入研究，無線Mesh技術逐步成為業(yè)界和研究的焦點，并沿不同的分支演進．其路由技術的核心主要是兩個方面[3]，路由協(xié)議和路由算法.路由判據(jù)、路由容錯、負載均衡、多徑路由、跨層信息交互、QoS、多信道等都是路由設計要考慮的因素．

文獻[4]以動態(tài)源路由協(xié)議DSR為基礎，提出了一種新的安全增強的多徑DSR路由協(xié)議SE-DSR，通過多徑路由發(fā)現(xiàn)機制為協(xié)議提供負載均衡和路由容錯能力，采用雙向路徑信任評估和單向證書鏈驗證為協(xié)議提供安全保障，通過犧牲存儲縮短了網(wǎng)絡延時．文獻[5]利用蟻群算法求解跨域跨層跨節(jié)點的QoS自適應體系架構模型，設計了雙層規(guī)劃模型的蟻群優(yōu)化路由算法．文獻[6]提出了多信道無線Mesh網(wǎng)絡路由度量CLIDH概念，設計了跨層多信道路由協(xié)議CMAODV，提高了網(wǎng)絡資源利用率．文獻[7]通過分布式免干擾的鏈路調(diào)度機制，根據(jù)帶寬要求為鏈路分配時槽數(shù)，保證帶寬鏈路流，增加了通信連接成功概率．文獻[8]提出了面向吞吐量效率的機會主義路由算法，通過引入傳輸時間因素，在轉發(fā)節(jié)點數(shù)量與鏈路穩(wěn)定度之間取得平衡，提高了網(wǎng)絡性能．文獻[9]分析了在路由算法設計時，鏈路質(zhì)量、期望傳輸次數(shù)、每一跳的往返時間等相關參數(shù)對網(wǎng)絡性能的影響，提出了基于加權累計期望傳輸次數(shù)的路由度數(shù)指標，較好地解決了信道相互影響的問題．

無線Mesh網(wǎng)絡兼容現(xiàn)有任何IEEE802.11的無線網(wǎng)絡通信協(xié)議，并且在802.11s,802.15,802.16d/e,802.20等標準中對Mesh組網(wǎng)技術作了一定的規(guī)范．學術界已經(jīng)取得了一定的研究成果，并有相關產(chǎn)品投入市場，但作為一種新型網(wǎng)絡架構，國際上尚未形成非常成熟的標準.我國參與IEEE802標準開發(fā)的很少，影響了它的迅速推廣，還有許多問題值得進一步探索，特別是路由算法的設計還有很大的研究空間，成為其推廣應用的瓶頸．

1無線Mesh網(wǎng)絡體系結構

WMN包括無線骨干網(wǎng)和無線移動接入兩部分，前者由無線 Mesh 路由器組成，節(jié)點位置相對固定，提供無線回程功能，移動性較少，而無線移動接入部分則是由用戶節(jié)點連接接入點 AP和無線用戶終端節(jié)點組成．近端用戶節(jié)點可以直接關聯(lián)接入點，而距離骨干網(wǎng)節(jié)點較遠的用戶，可以通過其他用戶節(jié)點中繼后連入WMN，用戶節(jié)點通過自組織、自配置互聯(lián)．其體系結構如圖1所示.

圖1　無線Mesh網(wǎng)絡的體系結構Fig.1　Architecture of wireless mesh network

無線Mesh網(wǎng)絡的節(jié)點通常包括3類：客戶端(移動終端)節(jié)點，路由節(jié)點和網(wǎng)關節(jié)點，它是一個可靠而冗余的無線網(wǎng)絡．當一個節(jié)點發(fā)生故障，其他節(jié)點可以通過一個或者多個中間節(jié)點互相連接后通訊，節(jié)點的接入和撤出都容易實現(xiàn)．

2無線Mesh網(wǎng)絡路由協(xié)議設計的原則與方法

無線Mesh網(wǎng)絡是WLAN和Ad hoc自組織網(wǎng)絡技術的結合，其路由算法可以通過繼承并進行改造而實現(xiàn)[10-11]．

2.1　無線Mesh網(wǎng)絡的路由協(xié)議類型

無線Mesh網(wǎng)絡路由協(xié)議主要分為4類[12]：(1)先驗式路由，即每一個節(jié)點平時維護一張路由表，預先存儲了目標節(jié)點的IP地址及下一跳的位置信息，在發(fā)送數(shù)據(jù)時直接調(diào)用表的相關記錄，節(jié)點間通過周期性交換路由信息更新表的內(nèi)容；(2)反應式路由，即后驗式，只有當向目的節(jié)點發(fā)送包時，源節(jié)點才在網(wǎng)絡中發(fā)起路由查找過程，找到相應的路由信息后記錄到路由表；(3)混合式路由，包括先驗式路由協(xié)議和反應式路由協(xié)議兩部分；(4)機會路由，利用無線網(wǎng)絡的廣播特性，每次數(shù)據(jù)包總是轉發(fā)給一組節(jié)點，這些節(jié)點根據(jù)它們到目標節(jié)點的度量(Metric)確定其優(yōu)先級，然后選擇優(yōu)先級最高的節(jié)點再次轉發(fā)數(shù)據(jù)包給另外一組節(jié)點，如此重復轉發(fā)直到目的節(jié)點．

2.2　無線Mesh網(wǎng)絡路由協(xié)議的設計原則

Ad hoc網(wǎng)絡采用最小跳數(shù)優(yōu)先的路由協(xié)議.無線Mesh網(wǎng)絡僅依靠跳數(shù)還遠遠不夠，還要綜合考慮線路狀況等多種度量指標，以滿足網(wǎng)絡的健壯性和容錯性并使其能夠在鏈路失效時快速恢復，并通過流量統(tǒng)計進行負載均衡，以充分利用系統(tǒng)資源．

在設計無線Mesh網(wǎng)絡路由協(xié)議時，重點考慮4個原則[13-14]：(1)路由判據(jù)，反映鏈路的優(yōu)劣，良好的路由判據(jù)提供負載均衡，方便確定最佳路由，是影響無線Mesh網(wǎng)絡路由協(xié)議性能的核心指標；(2)避免環(huán)路，從發(fā)送端到接收端采用單一方向，避免因循環(huán)轉發(fā)產(chǎn)生回路而出現(xiàn)的擁塞和死鎖；(3)機會平等，在信道競爭和數(shù)據(jù)傳輸過程中，各節(jié)點在分配網(wǎng)絡資源時均能具有相同概率；(4)QoS保障，根據(jù)實時鏈路質(zhì)量及帶寬選擇路徑，使QoS 需求最大化，保證服務質(zhì)量．

2.3　無線Mesh網(wǎng)絡路由協(xié)議的設計方法

無線Mesh網(wǎng)絡路由協(xié)議的設計方法主要包括兩種：一種是借鑒Ad hoc網(wǎng)絡的路由協(xié)議，結合自身特點，改造或優(yōu)化原有的路由協(xié)議，最大程度地提高網(wǎng)絡性能，這種方法較為常見；另一種是設計全新的路由協(xié)議，一般適用于制造廠商，研發(fā)周期長，消耗大，是研究者改進的基礎．

3AODV路由協(xié)議的優(yōu)化設計

3.1　AODV工作原理[11，15]

AODV協(xié)議(Ad hoc On-Demand Distance Vector Routing),即按需距離矢量路由，是一種基于目標的反應式路由協(xié)議[16]，其基本數(shù)據(jù)包包括路由請求RREQ，路由應答RREP，路由錯誤RERR.當某節(jié)點給其他節(jié)點傳送信息時，若沒有現(xiàn)成路由，則以多播形式發(fā)出路由請求報文RREQ.RREQ報文攜帶發(fā)起節(jié)點和目標節(jié)點的IP地址，鄰近節(jié)點收到RREQ以后，判斷目標節(jié)點是否就是它本身．如果是，則向發(fā)送方回送路由響應RREP;如果不是，則在自己的路由表中查找是否有達到目標節(jié)點的路由.如果有，則向發(fā)送節(jié)點返回RREP，否則繼續(xù)將RREQ轉發(fā)到下一節(jié)點進行查找．AODV采用定期廣播HELLO報文的方式維護路由，一旦發(fā)現(xiàn)某一處鏈路處于斷開狀態(tài)，則發(fā)送錯誤信息報文ERROR通知那些由于鏈路斷裂而不可到達的節(jié)點刪除相關記錄或者進行路由修復．RREQ的格式如圖2所示．

01234567PacketType:數(shù)據(jù)包類型,RREQ的值用1表示Reserved:保留,當前值為0,擴展或升級用HopCount:源節(jié)點到目的節(jié)點所經(jīng)過的跳數(shù),初值為0RREQID:路由請求消息標識,RREQ的唯一標識DestinationIP:目標節(jié)點IP地址DestinationSequenceNumber:目標節(jié)點序列號SourceIP:源節(jié)點IP地址SourceSequenceNumber:源序列號,表示源節(jié)點反向路由的新舊程度

圖2RREQ包格式

Fig.2Package format of FREQ

AODV路由維護過程：若因為源節(jié)點的移動而導致路由失效，則源節(jié)點重新發(fā)起路由發(fā)現(xiàn)過程；如果是目標節(jié)點或者中間節(jié)點的移動而引起的路由中斷，則該鏈路的上游節(jié)點會主動發(fā)送一個RRER分組到使用該鏈路的各個相鄰節(jié)點，此報文被發(fā)送到所有使用該鏈路的源節(jié)點，同時跳計數(shù)器設置為無窮大，表示不可達，各源節(jié)點需要重新發(fā)起路由發(fā)現(xiàn)過程；當目標節(jié)點檢測到與它相連的鏈路發(fā)生錯誤時，則不會產(chǎn)生主動路由響應報文，而與路徑無關的其他任何節(jié)點的移動都不會影響尋徑，也不需要路由維護．

3.2　AOVD的改進

RREP數(shù)據(jù)包中包含了一個保留字段Reserved，是系統(tǒng)升級擴展而預留的字段，設置為全0．為了充分利用AODV的按需距離矢量策略，可以將這個字段替換為某個評判標準，即一個計算值，通過此字段，當前節(jié)點即可以在RREQ報文中攜帶到達目的節(jié)點的判定信息，作為路由轉發(fā)的判據(jù)值，從而確定下一跳所在的位置．同時，各節(jié)點的數(shù)據(jù)包中需要記錄到達目標節(jié)點的第一跳的地址，用于確定下一跳的路徑是已有路徑還是新建路徑，可以通過增加一個字段Next Hop IP附加在RREQ擴展信息中，表示從源節(jié)點發(fā)送到目標節(jié)點路徑的下一跳．在不影響原有結構的基礎上改進RREQ格式包結構，如圖3所示.

01234567PacketTypeEvaluatingResult:評判值,是路徑轉發(fā)或選擇的依據(jù)NextHopIP:從源點開始的下一跳的IP地址……(與原字段相同)

圖3改進后的RREQ包格式

Fig.3Improved package format of FREQ

在圖3包格式中，最重要的指標是判據(jù)值，AODV采用了最小路由優(yōu)先的判據(jù)標準，但沒有充分考慮丟包率、信道干擾和傳輸速度等因素帶來的影響，其結果必定存在一定的偏差．將期望傳輸次數(shù)、加權期望傳輸次數(shù)以及鏈路干擾等因素作為綜合判定的依據(jù)，得到的結論更加全面．

假定正向丟包率和反向丟包率分別用Rf和Rr表示，則包傳輸出錯的概率P為

P=1-(1-Rf)*(1-Rr).

(1)

若傳輸失敗，則自動啟動重傳機制，這樣經(jīng)過反復重傳后總是可以達到目標節(jié)點，由此求出從源節(jié)點到目標節(jié)點的期望傳輸次數(shù)ETX為

ETX=1/(1-P).

(2)

ETT=ETX*(S/B).

(3)

由于其他鏈路和節(jié)點對當前鏈路存在干擾，影響傳輸性能，在判據(jù)中加入影響因子α，α是可調(diào)節(jié)數(shù)，其范圍為[0,1]，初值可設為0.5，用S1表示對當前鏈路存在干擾的鏈路集合，S2表示對當前鏈路存在干擾的節(jié)點集合，則當前鏈路的判據(jù)IC可以改進為

(4)

其中m表示對當前鏈路造成干擾的鏈路數(shù)，最后得到綜合判據(jù)SCS為

(5)

這種判據(jù)將鏈路長度，傳輸質(zhì)量，丟包率和信道干擾等因子考慮進來，其判斷結果更加全面客觀．

3.3　算法設計

當發(fā)送節(jié)點需要向接收節(jié)點傳送數(shù)據(jù)時，發(fā)送方先檢查自己所維護的路由表，確定是否有直達目標節(jié)點的路徑．如果存在這樣的路徑，則按照判據(jù)計算此路徑的評價值Vnow，并與原值Vold比較.若Vnow>Vold，表示相鄰節(jié)點采用了不同信道傳輸并且干擾較小，則選擇此路徑進行數(shù)據(jù)傳輸；否則仍然采用原路徑傳輸．如果節(jié)點維護的路由表中沒有直達目標點的路徑，則發(fā)送方節(jié)點重新發(fā)起路由請求建立路徑．假定有兩個節(jié)點S和D，則從源點S到目標點D是最合適路徑的條件為：對于任意節(jié)點W(S和D除外)，由S到D的評判值V不小于S到W及D到W的評判值的最大值．即，V(S,D)>=max{V(S,W),V(W,D)}.

其路由發(fā)現(xiàn)算法如下：

算法的執(zhí)行過程：初始狀態(tài)路由表為空，節(jié)點集合為S，進入路由發(fā)現(xiàn)過程；如果從源節(jié)點到目標節(jié)點的跳數(shù)超過生存時間，則放棄此次操作重新查找；反之則向網(wǎng)絡廣播RREQ，獲取下一跳的位置，并計算其評判值，如果下一跳已經(jīng)出現(xiàn)在路由表中，需要比較當前評判值與路由表中的值，取其較小者作為當前的路徑加入路由表，按此過程繼續(xù)尋找下一跳，直到找到目標節(jié)點為止．

4性能分析

OPNET是一個網(wǎng)絡仿真技術軟件包，能夠準確的分析復雜網(wǎng)絡的性能和行為．此處用OPNET為仿真軟件，選取最主要的兩個性能參數(shù)：端到端的時延、負載作為評價標準，搭建1 000*1 000 m的開闊環(huán)境，15個無線節(jié)點(含一個根節(jié)點)隨機分布，數(shù)據(jù)包為1 kb，所有節(jié)點均以2 m/s速度隨機移動，數(shù)據(jù)傳輸率為1 Mbps，節(jié)點功率為0.001 W，仿真時間設置為30 min，同時選取4個節(jié)點的簡單情況作為參照．仿真結果如圖4和圖5所示.

圖4反映的是在30 m不同的場景范圍內(nèi)，其時延秒數(shù)的變化情況．可以看出，當場景只有4個節(jié)點時，平均時延較高，而15個節(jié)點時平均時延低，大于10 m范圍后趨向穩(wěn)定，時延為0.001 4 s．圖5表示了不同的場景范圍內(nèi)，網(wǎng)絡的負載情況(bps)，可以清晰地顯示，15個節(jié)點比4個節(jié)點場景的平均負載低，10 m范圍以后，負載趨向穩(wěn)定．由此得出結論，當節(jié)點數(shù)較多時優(yōu)化后的AOVD協(xié)議選擇最佳路徑進行數(shù)據(jù)傳輸，其網(wǎng)絡時延和網(wǎng)絡負載性能指標均高于節(jié)點較少的情況，表明本協(xié)議適合于節(jié)點較多的大型場景，比原來的AODV協(xié)議具有更實用的優(yōu)勢．

5結語

本文按照無線Mesh網(wǎng)絡體系結構的特點，探討了其路由協(xié)議的常用設計方法和原則，在AODV的基礎上進行了優(yōu)化設計，并在仿真平臺上對其時延及負載等性能進行了對比分析．雖然路由選擇在網(wǎng)絡層實現(xiàn)，但如果充分利用來自于MAC的數(shù)據(jù)進行跨層次設計，并充分考慮各種影響因子設定綜合判據(jù)標準，無疑能夠更好地完善路由性能，而本文并未對這些內(nèi)容做詳細的研究，有待今后進一步研究．

參考文獻：

[1]沈呈,陸一飛,夏勤.基于綜合判據(jù)的無線Mesh網(wǎng)路由協(xié)議[J].計算機學報, 2010,33(12):2300-2311.

[2]DAN A O, FANG X M, MA Z J. Key technology and applications of wireless mesh networks[J].Telecom Eng, 2005,2:16-22.

[3]王曉翔.無線Mesh網(wǎng)絡路由技術研究[D].重慶：重慶大學, 2012.

[4]李每虎,郭淵博.SE-DSR:一種安全增強的Mesh網(wǎng)絡多徑動態(tài)源路由協(xié)議[J]. 計算機工程與科學, 2012,34(5):17-23.

[5]張千里.基于蟻群的Mesh網(wǎng)絡路由算法模型的設計[J].赤峰學院學報, 2012,34(9):28-29.

[6]劉宴兵,吳濤,先興平.多信道無線Mesh網(wǎng)絡路由機制[J].小型微型計算機系統(tǒng), 2012,33(2):319-324.

[7]項慨,曾園園.多信道無線網(wǎng)狀網(wǎng)帶寬有效的路由機制設計[J].計算機應用研究, 2012,29(8):3081-3084.

[8]趙傳強.基于機會路由與多路徑路由的無線Mesh網(wǎng)絡關鍵技術研究[D].北京：北京郵電大學, 2010.

[9]GUNGOR V C, LAMBERTET F. Routing metrics and protocols for wireless mesh networks[J].IEEE Network, 2008,2(22):6-12.

[10]王夢瑩.無線Mesh網(wǎng)絡路由技術的改進研究[D].南京：南京郵電大學, 2013.

[11]PERKINS C E, ROYER E M. Ad hoc On-Demand Distance Vector (AODV) Routing[C]//Mobile Comput Syst Appl. Proceedings. WMCSA ′99. Second IEEE Workshop. New Orleans, LA, 1999.

[12]杜輝.無線Mesh網(wǎng)絡路由協(xié)議研究[D]. 武漢：武漢科技大學, 2010.

[13]張維,丁恩杰,趙亮.無線Mesh網(wǎng)絡中基于負載平衡的自適應擁塞控制路由策略[J].煤炭技術, 2012,31(8):177-179.

[14]陳建華.無線Mesh網(wǎng)絡路由協(xié)議研究[D].南京：南京信息工程大學, 2009.

[15]LI P, SCALABRINO N, FANG Y G,etal. How to effectively use multiple channels in wireless mesh networks[J]. IEEE Trans Para Distri Syst, 2009,20(11):1641-1652.

[16]REN W, YEUGD Y, JIN H. TCP performance evaluation over AODV and DSDV in RW and SN mobility models[J]. J Zhejiang Univ Sci A, 2006,7(10):1683-1689.

(編輯胡文杰)

*通訊作者,E-mail：hfx_888@163.com

基金項目：湖南省科技計劃資助項目(2014GK3032)；湖南省教育廳科研資助項目(13C1050)

收稿日期：2014-09-24

中圖分類號TP393

文獻標識碼A

文章編號1000-2537(2015)03-0085-06

DOI:10.7612/j.issn.1000-2537.2015.03.016