基于位置輔助的自適應(yīng)廣播AODV路由協(xié)議

李友良，陳桂芬，羅寶翔

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

移動(dòng)自組織組網(wǎng)絡(luò)MANET屬于無線移動(dòng)通信網(wǎng)絡(luò)的一種［1］，它不具備相應(yīng)的預(yù)設(shè)基礎(chǔ)設(shè)施，且是由眾多配備無線收發(fā)信裝置的移動(dòng)終端所構(gòu)成。由于在該網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)能夠自由移動(dòng)，開放性較強(qiáng)，所以這種網(wǎng)絡(luò)能夠用于基礎(chǔ)設(shè)施不可用和無法部署網(wǎng)絡(luò)的環(huán)境，如災(zāi)難恢復(fù)、會(huì)議中的臨時(shí)信息共享、軍事應(yīng)用、數(shù)據(jù)共享和緊急情況［2］。

AODV（Ad Hoc On-Demand Distance Vector）按需距離矢量路由協(xié)議是自組網(wǎng)中的一種被廣泛應(yīng)用的路由協(xié)議，只有存在通信需要時(shí)，它才會(huì)開始探尋到目的節(jié)點(diǎn)的路由［3］。即，網(wǎng)絡(luò)內(nèi)一節(jié)點(diǎn)A需要將數(shù)據(jù)傳輸?shù)搅硪还?jié)點(diǎn)B，但沒有已知到節(jié)點(diǎn)B的路徑。節(jié)點(diǎn)A需要向它通信范圍內(nèi)的所有節(jié)點(diǎn)廣播路由請求分組（RREQ），接收到RREQ的節(jié)點(diǎn)在網(wǎng)絡(luò)內(nèi)繼續(xù)轉(zhuǎn)發(fā)工作，直至節(jié)點(diǎn)B或已知到節(jié)點(diǎn)B路徑的節(jié)點(diǎn)接收到RREQ，生成路由應(yīng)答分組（RREP）并單播回源節(jié)點(diǎn)［4］。RREP消息到達(dá)源節(jié)點(diǎn)表明路由發(fā)現(xiàn)過程已經(jīng)結(jié)束，此時(shí)使用單播傳輸將數(shù)據(jù)包轉(zhuǎn)發(fā)到目的地。由于協(xié)議采用洪泛廣播的方式來探尋路由，并且選擇路由的依據(jù)只是依照路由跳數(shù)和延時(shí)長短，這在很大程度上提高了網(wǎng)絡(luò)中節(jié)點(diǎn)間彼此通信的能量開銷，降低了最佳路由的建立概率［5］。近年來，隨著GLONASS、GPS、北斗等定位系統(tǒng)的發(fā)展，許多研究人員通過定位技術(shù)使網(wǎng)絡(luò)中各節(jié)點(diǎn)能夠方便地獲得自己的地理位置信息。借助地理位置信息，研究數(shù)據(jù)轉(zhuǎn)發(fā)方案，能夠使節(jié)點(diǎn)在探尋路由時(shí)減少過度的洪泛，增大探尋路由的效率［6］。

地理 AODV［7］（GeoAODV）是 AODV 協(xié)議的另一種改進(jìn)，與LAR協(xié)議類似，它將尋找域限制在可能包含到目的地路由的網(wǎng)絡(luò)部分［8］。不過，區(qū)別于LAR的地方是，GeoAODV并不假設(shè)目標(biāo)坐標(biāo)對發(fā)起路由發(fā)現(xiàn)過程的節(jié)點(diǎn)有效。GeoAODV依靠一個(gè)分布式進(jìn)程在網(wǎng)絡(luò)節(jié)點(diǎn)之間共享位置坐標(biāo)。此外，GeoAODV定義的搜索區(qū)域不同于LAR，它可以動(dòng)態(tài)調(diào)整當(dāng)RREQ消息遍歷網(wǎng)絡(luò)時(shí)的搜索區(qū)域。它只通過仿真經(jīng)驗(yàn)在不同節(jié)點(diǎn)密度情況下預(yù)設(shè)廣播角度，在節(jié)點(diǎn)密度不均勻且拓?fù)淇焖僮兓那闆r下適應(yīng)度不高［9］。

LAODV協(xié)議［10］提出了最大前程策略的思想，它根據(jù)節(jié)點(diǎn)間的投影長度提出前程值的變量，在節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ時(shí)根據(jù)前程值選取優(yōu)先轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)以建立數(shù)據(jù)傳輸?shù)淖疃搪窂?。由于?jié)點(diǎn)的前程值為衡量中繼節(jié)點(diǎn)優(yōu)先值的唯一變量，根據(jù)最大前程策略所建立的路由可能并不是最佳路由。且在節(jié)點(diǎn)密度低的環(huán)境下，按照前程策略選取中繼節(jié)點(diǎn)容易出現(xiàn)路由空洞，節(jié)點(diǎn)需要多次重啟路由發(fā)現(xiàn)過程，就會(huì)導(dǎo)致路由可建立概率減小［11］。

針對以上路由協(xié)議在不同節(jié)點(diǎn)密度的適應(yīng)度不強(qiáng)的缺點(diǎn)，本文提出了一種根據(jù)節(jié)點(diǎn)密度自適應(yīng)調(diào)整廣播范圍的位置輔助路由協(xié)議（AbAODV），協(xié)議通過網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間定期交互的Hello報(bào)文獲得網(wǎng)絡(luò)中各節(jié)點(diǎn)的所處位置信息［12］，并考慮到相應(yīng)時(shí)間內(nèi)節(jié)點(diǎn)的位置變化提出最大誤差值?；谇俺讨档乃枷胩岢鲎畲髢?yōu)選區(qū)域，根據(jù)節(jié)點(diǎn)密度自適應(yīng)調(diào)整廣播角度來篩選中繼節(jié)點(diǎn)，最后通過節(jié)點(diǎn)廣播概率公式建立最優(yōu)路由。能夠在避免路由空洞情況下減少消息的冗余，減輕網(wǎng)絡(luò)負(fù)載，提高協(xié)議效能。

1 AbAODV協(xié)議設(shè)計(jì)

AbAODV是借助定位技術(shù)所設(shè)計(jì)的按需距離矢量路由協(xié)議，需要在路由請求分組RREQ和網(wǎng)絡(luò)中定期交互的Hello報(bào)文中添加當(dāng)前節(jié)點(diǎn)的地理位置信息，以幫助建立最佳路由。

1.1 節(jié)點(diǎn)的偏移誤差

在某一網(wǎng)絡(luò)拓?fù)渲?，若源?jié)點(diǎn)I向目的節(jié)點(diǎn)D轉(zhuǎn)發(fā)消息，已知節(jié)點(diǎn)D的位置信息，但在轉(zhuǎn)發(fā)過程中D點(diǎn)位置會(huì)隨轉(zhuǎn)發(fā)時(shí)間和路由尋找時(shí)間產(chǎn)生變化。這里考慮網(wǎng)絡(luò)中最惡劣的情況［13］，為了避免錯(cuò)過最佳轉(zhuǎn)發(fā)的中繼節(jié)點(diǎn)，提出了目的節(jié)點(diǎn)位置最大誤差值：

式中，Tr為一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)路由消息所需的時(shí)間；H為當(dāng)前網(wǎng)絡(luò)路由允許建立的最大跳數(shù)；Ti為節(jié)點(diǎn)周期性交互Hello消息的間隔時(shí)間；Vmax為節(jié)點(diǎn)最大移動(dòng)速度。節(jié)點(diǎn)偏移模型如圖1所示。

圖1 節(jié)點(diǎn)偏移模型

圖中，線段ID為源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最近距離，D'為誤差時(shí)間內(nèi)節(jié)點(diǎn)豎向最大偏移位置。α為誤差偏移角且滿足：

1.2 前向優(yōu)選區(qū)域

旨在尋找網(wǎng)絡(luò)內(nèi)兩節(jié)點(diǎn)間通信的最短路徑，LAODV協(xié)議引入了最大前程策略［10］在路由發(fā)現(xiàn)階段：將轉(zhuǎn)發(fā)數(shù)據(jù)的臨節(jié)點(diǎn)在上一跳節(jié)點(diǎn)到目的節(jié)點(diǎn)的線段上的投影長度定義為前程值。如圖2所示，Y1、Y2為源節(jié)點(diǎn)I的兩個(gè)鄰居節(jié)點(diǎn)，則Y1、Y2的前程值分別為K1、K2。

圖2 最大前程策略

由于以前程值作為路由建立的依據(jù)具有局限性，所以AbAODV協(xié)議基于最大前程策略，提出了節(jié)點(diǎn)前向優(yōu)選區(qū)域以進(jìn)行節(jié)點(diǎn)密度的判斷，節(jié)點(diǎn)的前向優(yōu)選區(qū)域如圖3所示。

圖3 節(jié)點(diǎn)前向優(yōu)選區(qū)域

陰影部分扇形為源節(jié)點(diǎn)I關(guān)于目的節(jié)點(diǎn)D的前向優(yōu)選區(qū)域，它由兩個(gè)以I為圓心，節(jié)點(diǎn)I的通信半徑r為半徑的半圓重疊而成。兩個(gè)半圓分別被線段ID'，ID″平均分割，圓心角為π +2α。陰影區(qū)域的面積S為：

在該區(qū)域內(nèi)，源節(jié)點(diǎn)I、鄰居節(jié)點(diǎn)Y和目的節(jié)點(diǎn)D的位置信息能夠借助定位系統(tǒng)獲得，假設(shè)它們 的 經(jīng) 緯 度 坐 標(biāo) 分 別 為(xIE,yIN )，(xYE,yYN )，(xDE,yDN )，則 節(jié) 點(diǎn) 間 的 距 離 ：

通過計(jì)算節(jié)點(diǎn)間的距離，可以得到節(jié)點(diǎn)Y在線段ID上的投影值KY：

通過計(jì)算投影值，可以得到鄰居節(jié)點(diǎn)Y的關(guān)于源節(jié)點(diǎn)I和目的節(jié)點(diǎn)D的投影角度β：

若β≤0.5π+α，則可判定節(jié)點(diǎn)Y處于節(jié)點(diǎn)I的前向優(yōu)選區(qū)域內(nèi)。

1.3 概率廣播公式

通過計(jì)算所有位于自身通信范圍內(nèi)的鄰居節(jié)點(diǎn)的投影角度，當(dāng)前節(jié)點(diǎn)就可以得到位于自己前向優(yōu)選區(qū)域內(nèi)的鄰居節(jié)點(diǎn)數(shù)量，從而計(jì)算當(dāng)前節(jié)點(diǎn)的前向優(yōu)選區(qū)域內(nèi)節(jié)點(diǎn)密度的大小。由于移動(dòng)自組織網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化，前向優(yōu)選區(qū)域內(nèi)的節(jié)點(diǎn)密度也在不斷變化。為了以較少代價(jià)選取有效的鄰居節(jié)點(diǎn)，需要以前向優(yōu)選區(qū)域圓心角度和前向優(yōu)選區(qū)域節(jié)點(diǎn)密度大小為衡量值，設(shè)計(jì)自適應(yīng)廣播角度θ和廣播概率期望值Pe：

式中，Nh為處于當(dāng)前節(jié)點(diǎn)前向優(yōu)選區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)量；Ne為參與廣播的鄰居節(jié)點(diǎn)數(shù)的期望值。Ne在仿真中的取值由仿真環(huán)境決定（如節(jié)點(diǎn)通信范圍、節(jié)點(diǎn)個(gè)數(shù)、仿真區(qū)域大?。?。結(jié)合最短路徑問題，根據(jù)自適應(yīng)廣播角度值和廣播概率期望值，設(shè)計(jì)中繼節(jié)點(diǎn)的廣播概率公式：

由中繼節(jié)點(diǎn)的廣播概率P與廣播概率期望值Pe相比較，可作為該節(jié)點(diǎn)是否能夠參與本次路由建立的依據(jù)。

1.4 AbAODV協(xié)議描述

基于前向優(yōu)選區(qū)域和廣播概率公式，以選取最優(yōu)路徑為目的，AbAODV的路由建立過程如圖4所示。

圖4 AbAODV路由建立過程

（1）網(wǎng)絡(luò)中源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送消息，源節(jié)點(diǎn)首先進(jìn)行路由請求RREQ的準(zhǔn)備工作：通過兩節(jié)點(diǎn)的位置信息找到前向優(yōu)選區(qū)域并計(jì)算廣播角度θ和廣播概率期望值Pe，結(jié)果記入RREQ并對其進(jìn)行轉(zhuǎn)發(fā)。

（2）接收到RREQ的鄰居節(jié)點(diǎn)首先判斷自己是否為目的節(jié)點(diǎn)，如果是，則回復(fù)路由應(yīng)答RREP，否則進(jìn)行以下判斷：是否已接收過該消息，若是則直接丟棄RREQ，否則進(jìn)行下一步。

（3）計(jì)算本節(jié)點(diǎn)關(guān)于上一跳節(jié)點(diǎn)的投影角度β，若β小于θ，則進(jìn)行下一步計(jì)算，否則丟棄RREQ。

（4）計(jì)算廣播概率P，若P不大于Pe，丟棄RREQ，否則繼續(xù)進(jìn)行RREQ的準(zhǔn)備工作，直至目的節(jié)點(diǎn)接收到RREQ，并回復(fù)路由應(yīng)答RREP以建立路由。

AbAODV的節(jié)點(diǎn)的自適應(yīng)廣播如圖5所示。

圖5 AbAODV節(jié)點(diǎn)的自適應(yīng)廣播

節(jié)點(diǎn)I向節(jié)點(diǎn)D發(fā)送RREQ消息，根據(jù)網(wǎng)絡(luò)中各區(qū)域節(jié)點(diǎn)密度的差異和目的節(jié)點(diǎn)D的位置信息，中繼節(jié)點(diǎn)能夠自適應(yīng)的調(diào)整廣播范圍并篩選最佳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

2 仿真與結(jié)果分析

為了對比分析AbAODV、AODV、LAODV、Geo?AODV協(xié)議的性能，借助NS-2仿真軟件對它們在不同節(jié)點(diǎn)密度下的數(shù)據(jù)分組投遞率、路由發(fā)起頻率、端到端傳輸時(shí)延、歸一化路由開銷、平均吞吐量等方面進(jìn)行比較，從而確定AbAODV協(xié)議的可行性。

2.1 仿真環(huán)境設(shè)置

仿真取1 000×1 000 m2的區(qū)域，節(jié)點(diǎn)的運(yùn)動(dòng)模型為Random Waypoint，移動(dòng)速度在0～ 20 m/s之間，分組發(fā)送速度為5個(gè)/s，數(shù)據(jù)包大小為512 Byte，業(yè)務(wù)類型為CBR，傳輸層協(xié)議為UDP，仿真時(shí)間為 400 s，在節(jié)點(diǎn)數(shù)為 50，75，100，125，150個(gè)的情況下分別運(yùn)行40次取平均值。

表1 仿真參數(shù)

2.2 仿真分析

圖6顯示了四種路由協(xié)議在節(jié)點(diǎn)密度變化的運(yùn)動(dòng)環(huán)境中分組投遞率的具體效果。仿真結(jié)果顯示，節(jié)點(diǎn)密度相對較低的情況下，四種路由協(xié)議的分組投遞率均處于較高水平，但隨著節(jié)點(diǎn)密度的提升，AbAODV的分組投遞率下降趨勢較為緩慢，這是由于AbAODV路由協(xié)議在LAODV的前向區(qū)域的基礎(chǔ)上引入誤差值理念改進(jìn)為前向優(yōu)選區(qū)域，降低了節(jié)點(diǎn)移動(dòng)誤差，在GeoAODV的廣播角度調(diào)整的基礎(chǔ)上基于節(jié)點(diǎn)密度的變化提出自適應(yīng)的廣播角度，減少了分組重發(fā)，所以其分組投遞率在不同節(jié)點(diǎn)密度下都能有較好的表現(xiàn)。相比于AODV協(xié)議，AbAODV協(xié)議的分組投遞率平均提高了11.5%，相比于LAODV協(xié)議平均提高了2.3%，相比于GeoAODV協(xié)議平均提高了4.7%。

圖6 分組投遞率仿真圖

圖7顯示了四種路由協(xié)議在節(jié)點(diǎn)密度變化的運(yùn)動(dòng)環(huán)境中路由發(fā)起頻率的具體效果。仿真結(jié)果代表著四種路由協(xié)議在單位時(shí)間內(nèi)啟動(dòng)路由發(fā)現(xiàn)的頻率，能夠反映出協(xié)議在路由發(fā)現(xiàn)階段的工作效率。圖中可知，AODV協(xié)議的路由發(fā)起頻率最高，且AbAODV協(xié)議的路由發(fā)起頻率最低，這是因?yàn)锳bAODV協(xié)議考慮到網(wǎng)絡(luò)拓?fù)淇焖僮兓奶攸c(diǎn)，提出目的節(jié)點(diǎn)位置最大誤差值以應(yīng)對網(wǎng)絡(luò)中出現(xiàn)的惡劣情況，減少了鏈路斷裂的概率，提高了路由建立的有效性。相比于AODV協(xié)議，AbAODV協(xié)議的路由發(fā)起頻率平均減少了19.1%，相比于LAODV協(xié)議平均減少了10.6%，相比于GeoAODV協(xié)議平均提升了12.6%。

圖7 路由發(fā)起頻率仿真圖

圖8顯示了四種路由協(xié)議在節(jié)點(diǎn)密度變化的運(yùn)動(dòng)環(huán)境中路由開銷的具體效果。隨著節(jié)點(diǎn)密度的提高，路由協(xié)議需要管理的節(jié)點(diǎn)不斷增多，所以在相互通信時(shí)需要轉(zhuǎn)發(fā)更多的控制消息。仿真結(jié)果顯示，節(jié)點(diǎn)密度相對較低的情況下，由于LAODV、GeoAODV協(xié)議較容易出現(xiàn)路由空洞，節(jié)點(diǎn)需要轉(zhuǎn)發(fā)更多的RREQ消息來發(fā)現(xiàn)路由，所以其路由開銷相對于傳統(tǒng)的AODV路由協(xié)議表現(xiàn)較差，不過隨著節(jié)點(diǎn)密度的提升，由于LAODV、GeoAODV均以限制廣播范圍，減少路由冗余為目的，所以其在節(jié)點(diǎn)密度適中條件下路由開銷較低，且由于AbAODV路由協(xié)議相對于兩者的改進(jìn)，其在節(jié)點(diǎn)密度過高的條件下路由開銷也處于較優(yōu)水平。其中，相比于AODV協(xié)議，AbAODV協(xié)議的路由開銷平均減少了54.1%，相比于LAODV協(xié)議平均減少了34.3%，相比于Geo?AODV協(xié)議平均減少了39.1%。

圖8 歸一化路由開銷仿真圖

圖9顯示了四種路由協(xié)議在節(jié)點(diǎn)密度變化的運(yùn)動(dòng)環(huán)境中端到端時(shí)延的具體效果，由于GeoAODV路由協(xié)議在開始最小廣播角度傳輸失敗后會(huì)多次的擴(kuò)大其路由廣播角度，所以其時(shí)延表現(xiàn)較差，由于LAODV和AbAODV在傳統(tǒng)的AODV路由協(xié)議基礎(chǔ)上都考慮了最短路徑的問題，且AbAODV在數(shù)據(jù)轉(zhuǎn)發(fā)過程中能夠根據(jù)轉(zhuǎn)發(fā)時(shí)間預(yù)估節(jié)點(diǎn)的偏移誤差，減少了鏈路斷裂的可能性，所以其端到端時(shí)延表現(xiàn)更加出色。相比于AODV協(xié)議，AbAODV協(xié)議的端到端傳輸時(shí)延平均減少了47.7%，相比于LAODV協(xié)議平均減少了35.3%，相比于GeoAODV協(xié)議平均減少了50.1%。

圖9 端到端傳輸時(shí)延仿真圖

圖10顯示了四種路由協(xié)議在節(jié)點(diǎn)密度變化的運(yùn)動(dòng)環(huán)境中平均吞吐量的具體效果。由于節(jié)點(diǎn)密度的提高會(huì)使節(jié)點(diǎn)間對于信道資源的競爭更加劇烈，這導(dǎo)致了四種協(xié)議的平均吞吐量都呈下降趨勢。圖中可知，AODV協(xié)議的平均吞吐量最低，AbAODV協(xié)議的平均吞吐量最高，這是因?yàn)锳bAODV在計(jì)算廣播RREQ概率時(shí)考慮了節(jié)點(diǎn)移動(dòng)誤差和節(jié)點(diǎn)密度，能夠增加RREQ到達(dá)目的節(jié)點(diǎn)的成功率。相比于AODV協(xié)議，AbAODV協(xié)議的平均吞吐量平均提升了85.1%，相比于LAODV協(xié)議平均提升了31.2%，相比于GeoAODV協(xié)議平均提升了43.4%。

圖10 平均吞吐量仿真圖

3 結(jié)論

本文通過對傳統(tǒng)的AODV路由協(xié)議其洪泛廣播方式所存在的不足進(jìn)行分析，尋找借助地理位置信息來達(dá)到限制網(wǎng)絡(luò)廣播的洪泛，從而減少過多冗余的路由消息和中繼節(jié)點(diǎn)的數(shù)量、提高路由性能的方法。并借助相關(guān)文獻(xiàn)搜集同類型的改進(jìn)AODV路由協(xié)議的先進(jìn)思想和存在的不足加以總結(jié)。根據(jù)節(jié)點(diǎn)的運(yùn)動(dòng)情況考慮到節(jié)點(diǎn)移動(dòng)誤差值，并基于LAODV路由協(xié)議前程值的思想提出前向優(yōu)選區(qū)域，基于GeoAODV路由協(xié)議限制廣播角度的思想提出概率廣播公式，最終達(dá)到根據(jù)節(jié)點(diǎn)密度自適應(yīng)調(diào)整廣播角度來篩選中繼節(jié)點(diǎn)，AbAODV通過節(jié)點(diǎn)廣播概率公式建立最優(yōu)路由。能夠在避免路由空洞情況下減少消息的冗余，減輕網(wǎng)絡(luò)負(fù)載，提高協(xié)議效能。通過仿真分析，在不同節(jié)點(diǎn)密度的情況下，AbAODV協(xié)議都有很好的性能表現(xiàn)。