基于改進(jìn)的AODV多路徑路由算法建模分析

王潔　李明明　劉建生　熊小峰　樂光學(xué)

摘要：為進(jìn)一步有效地利用網(wǎng)絡(luò)資源，減小網(wǎng)絡(luò)開銷，在AODV路由協(xié)議的基礎(chǔ)上擴(kuò)展多路徑路由協(xié)議，根據(jù)路由信息請求、回復(fù)、保存過程中存在的網(wǎng)絡(luò)能量損失為目標(biāo)函數(shù)，得到基于多路徑選擇的路由算法來建立數(shù)學(xué)模型。通過仿真實(shí)驗(yàn)，對比分析已有經(jīng)典的改進(jìn)路由算法，具有更低網(wǎng)絡(luò)能量損失、平均端到端時(shí)延和較高網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)率。

關(guān)鍵詞：AODV；數(shù)學(xué)建模；數(shù)據(jù)轉(zhuǎn)發(fā)率；端到端時(shí)延

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）07-0052-05

1引言

無線Mesh網(wǎng)絡(luò)（Wireless Mesh Network， WMN），也稱作多跳網(wǎng)絡(luò)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)自動(dòng)組建立子網(wǎng)并維護(hù)網(wǎng)絡(luò)的連通性。對比Ad Hoc網(wǎng)絡(luò)，無線Mesh網(wǎng)絡(luò)更具優(yōu)勢，如表1所示[1]。但是無線Mesh網(wǎng)絡(luò)對路由性能的要求也隨之而升高，如何提高路由協(xié)議的有效性，將成為無線Mesh網(wǎng)絡(luò)路由協(xié)議的主要研究重點(diǎn)之一。

由于無線Mesh網(wǎng)絡(luò)傳播條件的突變，網(wǎng)絡(luò)拓?fù)渖喜豢深A(yù)測的突發(fā)狀況容易導(dǎo)致通信鏈路斷裂[2]。而一旦鏈路發(fā)生斷裂，需要重啟路由或者尋找新的通信鏈路完成通信，以降低路由開銷[3]。針對無線Mesh網(wǎng)絡(luò)的路由不穩(wěn)定性，宋文等人提出了公平感知路由算法，有效解決了目的節(jié)點(diǎn)的擁塞和延時(shí)問題，以網(wǎng)絡(luò)節(jié)點(diǎn)傳輸?shù)膿砣刂茽顟B(tài)作為路由協(xié)議的評價(jià)指標(biāo)，該路由算法基于DSR協(xié)議[4]。而已有的DSR路由協(xié)議僅考慮“最短路徑”忽視了路徑上的業(yè)務(wù)通信量。根據(jù)按需路由機(jī)制對比分析DSR、AODV，其中AODV為主動(dòng)式距離矢量路由協(xié)議（Ad Hoc on-demand distance vector，AODV），在中繼節(jié)點(diǎn)緩存路由請求和響應(yīng)記錄，能夠有效降低協(xié)議的開銷。如何在無線Mesh網(wǎng)絡(luò)中利用AOVD路由協(xié)議思想，降低協(xié)議開銷，成為無線Mesh網(wǎng)絡(luò)路由協(xié)議的研究重點(diǎn)。

傳統(tǒng)的按需距離矢量（Ad Hoc on-demand distance vector，AODV）路由算法主要適用于單路徑路由協(xié)議設(shè)計(jì)中[5]，為了進(jìn)一步優(yōu)化路由協(xié)議，保證網(wǎng)絡(luò)穩(wěn)定性，國內(nèi)外學(xué)者對AODV協(xié)議進(jìn)行改進(jìn)和擴(kuò)展，成果顯著。王忠恒等人提出了AODV-BR協(xié)議，該協(xié)議增強(qiáng)了AODV路由維護(hù)的功能，算法優(yōu)勢在于有效降低網(wǎng)絡(luò)鏈路中斷率和丟包率[1]。洪利等人提出了基于鏈路可用性預(yù)測的AODV路由協(xié)議，該協(xié)議提高了分組的投遞率并降低了分組端到端平均傳輸延時(shí)，提升了路由協(xié)議的可靠性[2]。清華大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室于2008年提出了以信任模型可用性為前提的AODV路由協(xié)議，針對MANET安全機(jī)制，改進(jìn)傳統(tǒng)的AODV協(xié)議，提出ATAODV（Availability trust AODV）路由協(xié)議，該協(xié)議有效降低了丟包率[3]。杜青松等人針對在MANET網(wǎng)絡(luò)環(huán)境下的性能缺陷問題設(shè)計(jì)了優(yōu)化的AODV路由協(xié)議O-AODV協(xié)議，增加了路由冗余度，提高了路由發(fā)現(xiàn)的效率，加快路由的本地修復(fù)能力[5]。王龍峰針對平均隊(duì)列長度來預(yù)測擁塞情況，提出了RAODV路由協(xié)議[9]，該協(xié)議在收斂條件下有效降低了端到端平均時(shí)延和提高數(shù)據(jù)轉(zhuǎn)發(fā)率。如何基于改進(jìn)的AODV路由協(xié)議有效降低無線Mesh網(wǎng)絡(luò)的丟包率，提升數(shù)據(jù)轉(zhuǎn)發(fā)率，以滿足多路徑的無線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)的通信要求，成為本文研究重點(diǎn)。

無線Mesh網(wǎng)絡(luò)中節(jié)點(diǎn)的多路徑路由問題如圖1所示，假設(shè)在某一時(shí)刻路徑1-5-4正在傳輸數(shù)據(jù)包，節(jié)點(diǎn)5的負(fù)載已經(jīng)很大，而此時(shí)節(jié)點(diǎn)2還要與節(jié)點(diǎn)6通信，依據(jù)跳數(shù)最小建立的路徑為2-5-6 ，這將導(dǎo)致網(wǎng)絡(luò)局部擁塞。路徑2-4-6，路徑2-5-6都是依據(jù)最小條數(shù)的路徑，若4和5兩個(gè)節(jié)點(diǎn)的帶寬一樣，此時(shí)依據(jù)路徑的負(fù)載程度可以明顯得出選擇路徑2-4-6比路徑2-5-6好。

多路徑路由協(xié)議，分為多路徑路由協(xié)議、備份路由協(xié)議兩種。其中備份路由協(xié)議為在多條路徑中選取一條路徑作為主路徑，其他路徑作為備份路徑。當(dāng)主路徑不可用時(shí)，則備用路徑代替主路徑來傳輸數(shù)據(jù)包。多路徑路由協(xié)議避免了重啟開啟路由發(fā)現(xiàn)的開銷和路由本地修復(fù)時(shí)間，提升了網(wǎng)絡(luò)穩(wěn)定性?；谠撀酚蓞f(xié)議，盧錫城等人提出了在移動(dòng)自主網(wǎng)絡(luò)中基于簇的QoS多路徑路由協(xié)議（CQMRP， Cluster-based QoS multipath routing protocol），該協(xié)議以局部路由信息的服務(wù)節(jié)點(diǎn)為指標(biāo)，展開服務(wù)質(zhì)量約束評價(jià)，算法有效降低了路由開銷，提升了網(wǎng)絡(luò)的多路徑服務(wù)質(zhì)量[7]。RAODV協(xié)議采用了在多路徑環(huán)境下增加路由跳數(shù)來降低平均時(shí)延[9]。文獻(xiàn)[11]提出了有效避免路由斷裂的ARB-AODV路由算法，該算法對比傳統(tǒng)AODV路由有效提升了數(shù)據(jù)轉(zhuǎn)發(fā)率并降低了網(wǎng)絡(luò)端到端時(shí)延。文獻(xiàn)[13]提出了基于鏈路可用時(shí)間的LAT-AODV路由算法，該路由算法在路由請求方面增加了備用路由的選擇函數(shù)，有效提升了數(shù)據(jù)轉(zhuǎn)發(fā)率和縮短了平均時(shí)延。

本文將基于改進(jìn)的AODV路由協(xié)議設(shè)計(jì)路由協(xié)議，增加路由查找過程，通過分析服務(wù)節(jié)點(diǎn)的網(wǎng)絡(luò)能量損失情況，選擇最優(yōu)路徑，增加多路徑查找功能，防止路由重啟產(chǎn)生的網(wǎng)絡(luò)開銷，以提升網(wǎng)絡(luò)吞吐量。仿真實(shí)驗(yàn)增加網(wǎng)絡(luò)帶寬的冗余度驗(yàn)證算法有效性。

2 AODV路由算法性能分析

2.1 算法性能分析

針對無線Mesh網(wǎng)絡(luò)中的路由發(fā)現(xiàn)過程，首先展開路由信息的分類，包括三種路由信息查詢，路由請求（RREQ）消息去發(fā)現(xiàn)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑，目的節(jié)點(diǎn)收到RREQ（最新的），則向源節(jié)點(diǎn)發(fā)送路由響應(yīng)（RREP），源節(jié)點(diǎn)收到RREP消息后，啟動(dòng)RREQ緩存定時(shí)器，在這段時(shí)間內(nèi)收到的所有不同的RREP進(jìn)行緩存，并對其進(jìn)行排序，確定主路徑，然后通知應(yīng)用層開始發(fā)送數(shù)據(jù)。當(dāng)主路徑擁塞，導(dǎo)致主路徑長時(shí)間未響應(yīng)，則切換優(yōu)先級(jí)高的有效路徑。

2.2 節(jié)點(diǎn)隨機(jī)模型

3 仿真分析

基于文獻(xiàn)[9-13]的路由算法分析結(jié)果，本文選擇ARB-AODV、LAT-AODV、ARB-AODV、AODV四種路由算法作為對比算法。通過對比實(shí)驗(yàn)，分別從網(wǎng)絡(luò)能量損失情況、移動(dòng)數(shù)據(jù)轉(zhuǎn)發(fā)率、網(wǎng)絡(luò)端到端平均時(shí)延來驗(yàn)證本文路由算法的有效性。實(shí)驗(yàn)采用1000mx1000m網(wǎng)絡(luò)拓?fù)?，隨機(jī)選擇40個(gè)節(jié)點(diǎn)，以最大跳數(shù)為20跳，在最大速度為10m/s～50m/s范圍內(nèi)轉(zhuǎn)發(fā)路由信息。

3.1 基于ADOV的多路徑協(xié)議路徑能量損失仿真分析

以網(wǎng)絡(luò)能量損失為路由協(xié)議算法的度量值，對比分析ARB-AODV、LAT-AODV、ARB-AODV協(xié)議，仿真結(jié)果如圖2所示。

實(shí)驗(yàn)結(jié)果表明：

（1）隨著網(wǎng)絡(luò)節(jié)點(diǎn)速度的增加，網(wǎng)絡(luò)能量歸一化值逐漸提升，網(wǎng)絡(luò)能量損失逐漸增加。

（2）當(dāng)節(jié)點(diǎn)移動(dòng)速度低于30m/s時(shí)，網(wǎng)絡(luò)能量損失：LAT-AODV>AODV>ARB-AODV>本文算法；當(dāng)節(jié)點(diǎn)移動(dòng)速度高于30m/s時(shí)，網(wǎng)絡(luò)能量損失：AODV>LAT-AODV>ARB-AODV>=本文算法。

（3）單路徑的路由算法AODV、LAT-AODV、ARB-AODV網(wǎng)絡(luò)能量歸一化值高于多路徑算法，本文路由算法得到的網(wǎng)絡(luò)能量損失低于其他算法。

3.2 基于ADOV的多路徑協(xié)議路徑數(shù)據(jù)轉(zhuǎn)發(fā)率分析

實(shí)驗(yàn)結(jié)果表明：

（1）隨著網(wǎng)絡(luò)節(jié)點(diǎn)速度的提升，網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)率持續(xù)下降。傳統(tǒng)路由算法AODV在節(jié)點(diǎn)速度為30m/s～40m/s時(shí)，數(shù)據(jù)轉(zhuǎn)發(fā)率沒有變化，其他算法數(shù)據(jù)轉(zhuǎn)發(fā)率均穩(wěn)定下降。

（2）在節(jié)點(diǎn)移動(dòng)速度低于40m/s時(shí)，網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)率下降速度：本文算法3.3 基于ADOV的多路徑算法平均時(shí)延分析

實(shí)驗(yàn)結(jié)果表明：

（1）隨著網(wǎng)絡(luò)節(jié)點(diǎn)速度的提升，網(wǎng)絡(luò)平均端到端時(shí)延逐漸升高。傳統(tǒng)路由算法AODV的平均端到端時(shí)延高于其它路由算法。

（2）端到端時(shí)延穩(wěn)定性：本文算法（OURS）>ARB-AODV>LAT-AODV>AODV。

4 結(jié)論

本文基于路由選擇改進(jìn)AODV路由協(xié)議，提出了改進(jìn)的AODV算法的數(shù)學(xué)模型，以網(wǎng)絡(luò)能量損失為目標(biāo)函數(shù)，根據(jù)不同冗余度計(jì)算公式得到的路由選擇結(jié)果，即路由請求并得到回復(fù)的數(shù)據(jù)信息。仿真實(shí)驗(yàn)結(jié)果表明，本文算法較ARB-AODV、LAT-AODV、AODV協(xié)議，具有較低網(wǎng)絡(luò)能量損失、較高數(shù)據(jù)轉(zhuǎn)發(fā)率、較低網(wǎng)絡(luò)平均端到端時(shí)延。本文存在的不足，對于節(jié)點(diǎn)路由信息在轉(zhuǎn)發(fā)過程中存在的冗余度還未進(jìn)行詳細(xì)實(shí)驗(yàn)。

參考文獻(xiàn)：

[1] 王忠恒，張曦煌.移動(dòng)Ad Hoc網(wǎng)絡(luò)AODV路由協(xié)議的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2010，30（2）： 333-336.

[2] 洪利，黃庭培，鄒衛(wèi)霞，等.基于鏈路可用性預(yù)測的AODV路由協(xié)議研究[J].通信學(xué)報(bào)，2008，29（7）：118-123.

[3] 游之洋，龔偉，趙曦濱，等.基于可用性信任模型的AODV路由協(xié)議改進(jìn)[J].清華大學(xué)學(xué)報(bào)，2010，50（5）：735-738.

[4] 宋文，方旭明.無線Mesh網(wǎng)絡(luò)公平感知路由算法設(shè)計(jì)與仿真[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（18）：4320-4325.

[5] 杜青松，朱江，張爾揚(yáng).基于閑時(shí)逆尋和路由學(xué)習(xí)機(jī)制的優(yōu)化AODV路由協(xié)議[J].通信學(xué)報(bào)，2011，32（8）：64-71.

[6] 鄺祝芳，陳志剛，劉蕙.一種認(rèn)知無線Mesh網(wǎng)絡(luò)中負(fù)載均衡的組播路由算法[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：523-531.

[7] 盧錫城，安輝耀，彭宇行，等.大規(guī)模移動(dòng)自主網(wǎng)絡(luò)中基于簇的QoS多路徑路由[J].軟件學(xué)報(bào)，2007，18（7）：1786-1798.

[8] 李國強(qiáng)，勒浩，武穆清.Ad Hoc網(wǎng)絡(luò)中一種新的多徑路由機(jī)制研究[J].信息傳輸與接入技術(shù)，2008，34（1）：22-24.

[9] 王龍峰.RAODV：一種基于擁塞跳數(shù)改進(jìn)的AODV路由協(xié)議[J].計(jì)算機(jī)與現(xiàn)代化，2013，216（8）：133-136.

[10] 張菡.Ad Hoc網(wǎng)絡(luò)中一種改進(jìn)的AODV路由協(xié)議[J].無線互聯(lián)科技，2008：254-258.

[11] 李向麗，荊瑞霞，何一涵.避免路由斷裂的優(yōu)化AODV路由協(xié)議[J].計(jì)算機(jī)應(yīng)用，2014， 34（9）：2468-2471.

[12] 莊雷，孫智軍.一種增加時(shí)限和延遲的AODV協(xié)議改進(jìn)方法[J].微電子學(xué)與計(jì)算機(jī)， 2007，24（8）：180-182.

[13] 周膠，田杰，戴晨鋮，等.戰(zhàn)術(shù)MANET中基于鏈路可用時(shí)間的AODV路由協(xié)議研究[J]. 2013，35（12）：96-101.

[14] GONG XuDong，XIONG Yan，LU Qiwei et al.A Trusted Ad Hoc Routing Protocol Based on Fuzzy Mathematics[J].Chinese Journal of Electronics，2013，22（1）：155-159.