AODV中穩(wěn)定兼能量感知的路由改進(jìn)協(xié)議

劉期建，鄭 濤

（中國民用航空飛行學(xué)院 計算機(jī)學(xué)院，四川 廣漢618307）

0 引 言

前人對MANET 已經(jīng)提出了多種路由協(xié)議，基于路由發(fā)現(xiàn)原則，將其分為先應(yīng)式和反應(yīng)式［1］。反應(yīng)式或按需路由協(xié)議僅當(dāng)需要發(fā)送某個數(shù)據(jù)包時，才使用廣播查詢應(yīng)答（PREQ－RREP）過程來確定路由。大多數(shù)協(xié)議采用最小跳數(shù)作為路由選擇度量。前人發(fā)現(xiàn)最短路徑路具有較短的壽命，尤其在高密度自組織網(wǎng)絡(luò)中，即使由于邊緣效應(yīng)導(dǎo)致了低移動性［2］。然而，它們都沒有解決在數(shù)據(jù)傳輸過程中如何降低鏈路斷開的問題。在大多數(shù)按需路由算法中，它需要一定的時間來檢測鏈路故障，然后啟動路由恢復(fù)過程［3，4］，這會消耗大量資源，如帶寬、能量等，還引入額外的延遲。由于再次進(jìn)行路由發(fā)現(xiàn)，網(wǎng)絡(luò)的效率大大降低。

本文提出一種 “先接后斷”機(jī)制，來增強(qiáng)RSEAAODV 中的路由維護(hù)性。當(dāng)存在移動性、能量消耗和擁塞等任何可能導(dǎo)致鏈路中斷的原因時，可通過跨層法找到一個數(shù)據(jù)傳輸?shù)奶娲窂?。仿真結(jié)果表明，在高負(fù)載和高動態(tài)環(huán)境下，本文所提方法的性能優(yōu)于RSEA 和LAER。

1 相關(guān)研究

文獻(xiàn) ［5］將鏈路穩(wěn)定性定義為鏈路的穩(wěn)定程度和通信持續(xù)的時間長短的一個度量。信號強(qiáng)度是一個用于評估鏈路穩(wěn)定性的參數(shù)。文獻(xiàn) ［6］中提出一種跨層法和節(jié)點(diǎn)移動性預(yù)測改進(jìn)路由協(xié)議，實(shí)現(xiàn)基于跨層調(diào)解和節(jié)點(diǎn)位置預(yù)測的穩(wěn)定性路由。文獻(xiàn) ［7］提出了利用圖論的方法實(shí)現(xiàn)網(wǎng)絡(luò)的重連接以此實(shí)現(xiàn)穩(wěn)定路由。這些協(xié)議在不同程度上實(shí)現(xiàn)了穩(wěn)定路由，但各有適用的范圍。

文獻(xiàn) ［8］中N.Sharma根據(jù)接收到的信號強(qiáng)度計算出鏈路穩(wěn)定性和路由穩(wěn)定性，進(jìn)而提出RSQR，其基于閾值，將鏈路分為穩(wěn)定鏈路和不穩(wěn)定鏈路。

文獻(xiàn) ［9］提出EBL，作者認(rèn)為鏈路穩(wěn)定性和剩余電池容量都很重要。EBL不僅提高了能量利用率，而且減少了網(wǎng)絡(luò)的分割。文獻(xiàn) ［10］提出LAER，它們將鏈路穩(wěn)定性和能量流失率的聯(lián)合指標(biāo)考慮進(jìn)路由發(fā)現(xiàn)之中，從而減少了控制開銷，以及平衡了流量負(fù)載。

借助備份路由，AODV－BR［12］在不可預(yù)知的鏈接中斷時，實(shí)現(xiàn)了路由的快速恢復(fù)，其是通過監(jiān)測數(shù)據(jù)包和RREP包來更新。在高度密集的網(wǎng)絡(luò)中這會導(dǎo)致很高的控制信息開銷和碰撞。

2 問題的描述

MANET 的拓?fù)浣Y(jié)構(gòu)表示為無向圖G ＝（V，E），其中V 是節(jié)點(diǎn)集合，E 是節(jié)點(diǎn)連接的邊的集合。令P（u，v）＝｛P0，P1，P2，...，Pn｝，其中每個Pi是一個u和v間的可行路徑。考慮到路由穩(wěn)定性和剩余能量，從源到目的節(jié)點(diǎn)選擇最優(yōu)路徑的問題可描述為

其中

并且Ri＞EThr1，qi＜QThresh。

其中Ri和Fi分別是節(jié)點(diǎn)的剩余能量和全部容量。

對目標(biāo)的每個指標(biāo)提供重要度因子w1和w2，上面的最優(yōu)化可轉(zhuǎn)換成一個單目標(biāo)問題，表示如下

最大化目標(biāo)的和，表示如下

三級節(jié)點(diǎn)。三級節(jié)點(diǎn)主要是對水域附近資源點(diǎn)的介紹以及交通指引，安全提示，珍惜動植物，特殊地質(zhì)地貌景觀，文化景觀、歷史遺跡的介紹性解說和警告性解說。比如對于黃鞠灌溉工程的資源點(diǎn)介紹等。

3 所提的改進(jìn)路由協(xié)議

本節(jié) 主 要 討 論RSEA－RM （route stability and energy aware routing with route maintenance）路由的具體步驟，其主要包括路由發(fā)現(xiàn)、路由選擇及路由維護(hù)。

3.1 路由發(fā)現(xiàn)

當(dāng)節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包到某個目的節(jié)點(diǎn)時，它會搜索路由緩存中的路由。如果到達(dá)目的節(jié)點(diǎn)D 的路由不可達(dá)時，源節(jié)點(diǎn)S會將其路由請求RREQ 廣播發(fā)送給鄰居節(jié)點(diǎn)。當(dāng)收到RREQ 數(shù)據(jù)包后，中間節(jié)點(diǎn)檢測其強(qiáng)度，這樣它就接收了節(jié)點(diǎn)的數(shù)據(jù)包和剩余能量。如果信號強(qiáng)度和剩余能量超過了閾值，節(jié)點(diǎn)檢查其負(fù)載指標(biāo)，否則它將會丟棄該路由請求。如果隊列長度超過QThresh值，那么路由請求數(shù)據(jù)包將會丟失，以避免接下來的數(shù)據(jù)傳輸擁塞。如果信號強(qiáng)度超過SThrl，那么LS 就設(shè)置為1。如果信號強(qiáng)度在SThr1 和SThr2 之間，那么LS 就根據(jù)分化的信號強(qiáng)度（differentiated signal strength，DSS）計算得到。

借助計算累計路徑穩(wěn)定性 （accumulated path stability，APST）和累計能量 （accumulated energy，AE）函數(shù)，并且在發(fā)往鄰居節(jié)點(diǎn)前，在RREQ 數(shù)據(jù)包的頭段進(jìn)行更新。計算的穩(wěn)定值也將會在鄰居信息表中更新。然后路由請求就帶著更新的APST 和AE值轉(zhuǎn)發(fā)到它的鄰居節(jié)點(diǎn)了。

3.2 路由選擇

當(dāng)目的地節(jié)點(diǎn)收到第一個RREQ，它就將計時器Δt啟動t秒。根據(jù)目標(biāo)函數(shù) （式5）、路由請求中收到的APST和AEC值來計算路徑的可靠性。它存儲了包含在路由緩存中的可靠性值的所有的RREQ。在定時器超時后，它找出了具有最小目標(biāo)值的路徑，然后將RREP 發(fā)送給它。在計時器Δt完成計時后，將丟棄到達(dá)的路由請求。

算法1：目標(biāo)節(jié)點(diǎn)執(zhí)行

3.3 路由維護(hù)

“先接后斷”機(jī)制如算法2所示，對于因移動性、能量流失和擁塞引起的鏈路中斷，其能迅速適應(yīng)。每隔t1秒執(zhí)行一次，以監(jiān)測路由建立的狀態(tài)，其中t1值根據(jù)節(jié)點(diǎn)的移動性設(shè)置。

如果中間節(jié)點(diǎn)處于電池電量嚴(yán)重不足的狀態(tài)或者接收的信號包非常微弱，那么它將會創(chuàng)建一個TTL 設(shè)置為1的HLP分組，然后將其發(fā)送給鄰居節(jié)點(diǎn)。鄰居節(jié)點(diǎn)接收到HLP數(shù)據(jù)包后，根據(jù)HLP 數(shù)據(jù)包的描述，在其目的節(jié)點(diǎn)路由表中檢查路由的可用性。如果路由可用，那么它將路由返回給該節(jié)點(diǎn)發(fā)送的HLP數(shù)據(jù)包中的下游節(jié)點(diǎn)。下游節(jié)點(diǎn)收到路由后，更新路由表。數(shù)據(jù)包在新的路由中進(jìn)行傳輸，防止由于鏈路中斷導(dǎo)致的數(shù)據(jù)包丟失。

如果具有電量不足的節(jié)點(diǎn)為目的節(jié)點(diǎn)時，那么它會給源節(jié)點(diǎn)發(fā)送停止傳輸?shù)闹甘?，以避免可能的?shù)據(jù)包丟失和資源浪費(fèi)。同樣也檢查接口隊列長度是否超過了QThresh，以避免擁塞。

如果計時器計時完成后，即超時，還沒有可以替代的單跳節(jié)點(diǎn)路由，那么該節(jié)點(diǎn)會向源節(jié)點(diǎn)發(fā)送路由更改請求（route change request，RCR）。源節(jié)點(diǎn)接收到RCR 后，會進(jìn)行目的節(jié)點(diǎn)的路由發(fā)現(xiàn)，在現(xiàn)有路由的鏈路中斷前找出一個替代路由。與此同時，鄰居節(jié)點(diǎn)的路由表將隨著路由改變而更新。如果總能量將要流失的節(jié)點(diǎn)是源節(jié)點(diǎn)，它則繼續(xù)傳輸數(shù)據(jù)直到總能量流失結(jié)束。

如果在局部路由修復(fù)過程中，存在去往目的節(jié)點(diǎn)的替代路由，該機(jī)制將迅速適應(yīng)網(wǎng)絡(luò)的變化。這樣就增加數(shù)據(jù)包傳輸率，并且減少了丟包數(shù)量和延時的發(fā)生。避免數(shù)據(jù)包傳輸?shù)讲豢捎玫闹虚g節(jié)點(diǎn)，減少了資源浪費(fèi)。

算法2：路由維護(hù)

4 實(shí)驗(yàn)結(jié)果及分析

4.1 性能指標(biāo)

歸一化控制開銷 （normalized control overhead，NCO）指的是傳輸?shù)目刂瓢c目的節(jié)點(diǎn)接收到的控制包的比值；數(shù)據(jù)包傳輸率 （packet delivery ratio，PDR）指的是目的節(jié)點(diǎn)接收到的數(shù)據(jù)包數(shù)量與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)量的比值；節(jié)點(diǎn)剩余能量方差：該指標(biāo)計算了節(jié)點(diǎn)間能量使用的分布；端到端延遲：是衡量數(shù)據(jù)包到達(dá)目的地平均時間的指標(biāo)。

4.2 模擬參數(shù)

本文在仿真工具NS2［12］上進(jìn)行模擬。模擬環(huán)境參數(shù)如表1所示。其中，節(jié)點(diǎn)數(shù)50，拓?fù)浯笮?000m×500m，流數(shù)為10，節(jié)點(diǎn)的傳輸范圍為250 m，每個數(shù)據(jù)包大小為512字節(jié)。

表1 模擬參數(shù)

4.3 仿真結(jié)果分析

針對多個不同的移動速度0，5，10，15和20，進(jìn)行了一組廣泛的模擬。運(yùn)行10次模擬，給出所得結(jié)果的平均值作為性能指標(biāo)的數(shù)值。

圖1可以觀察到由于鏈路中斷和路由修復(fù)過程引起的NCO 隨著移動性的增加而增加。在較低移動性時，所提方法、RSEA 和LAER 的 NCO 分 別 為5.1%、5.4% 和6.3%。在高移動性時，所提方法、RSEA 和LAER 的NCO 分別為22.8%、26.2%和31.3%。RSEA 在高速動態(tài)環(huán)境中，顯示出更好的性能。因?yàn)?“先接后斷”和局部路由修復(fù)機(jī)制，這導(dǎo)致了相對其它兩種協(xié)議更少的控制開銷。更早地預(yù)測鏈路中斷，數(shù)據(jù)傳輸能夠在原路由鏈路中斷前切換到替代路由。

從圖2可觀察到，在所有3個協(xié)議中，PDR 隨著速度的增加而降低。降低的原因是速度提高時頻繁的鏈路中斷和路由的再次尋找。在高速移動性時，所提方法、RSEA和LAER 的PDR 分別為94.7%，93.8%和91.3%。所提方法相對于RSEA 來說PDA 增加了1%，這是因?yàn)樗Y(jié)合了 “先接后斷”路由維護(hù)機(jī)制，這大大減少了由于不可預(yù)測的鏈路中斷導(dǎo)致的數(shù)據(jù)包丟失的數(shù)量。

剩余節(jié)點(diǎn)能量的方差如圖3所示。該參數(shù)表征了協(xié)議的負(fù)載平衡能力。觀察到，隨著移動性的增加，由于頻繁的路由轉(zhuǎn)換，節(jié)點(diǎn)剩余能量方差逐漸減小。低移動時，所提方法、RSEA 和LAER 的能量方差百分比分別為18.8%，19.2%和21.54%。高 移 動 性 時，所 提 方 法、RSEA 和LAER 的能量方差百分比分別為7.8%，8.3%和11.3%。

如圖4所示，3個協(xié)議的端對端延遲隨移動性的增加而增加，這是由于頻繁的路徑中斷的緣故。高移動性時，所提方法、RSEA 和LAER 的平均端對端延遲分別為0.18s，0.21s和0.32s。所提方法延遲最低的原因是避免了由于節(jié)點(diǎn)移動性和電池能量流失引起的鏈路中斷。RSEA 協(xié)議中結(jié)合了 “先接后斷”路由維護(hù)機(jī)制，可以很快適應(yīng)網(wǎng)絡(luò)的變化。在高速移動性時，所提方法性能上比RSEA 高出14%。

圖1 控制開銷與節(jié)點(diǎn)移動性的關(guān)系

圖2 PDR 與節(jié)點(diǎn)移動性的關(guān)系

圖3 能量方差與節(jié)點(diǎn)移動性的關(guān)系

圖4 端對端延遲與節(jié)點(diǎn)移動性的關(guān)系

5 結(jié)束語

本文主要討論RSEA－RM 路由的具體步驟，其主要包括路由發(fā)現(xiàn)、路由選擇及路由維護(hù)，通過實(shí)驗(yàn)將該協(xié)議與其它類似路由協(xié)議如RSEA 及LAER 在NS2上，在多種情形下進(jìn)行多次模擬和對比，實(shí)驗(yàn)結(jié)果表明，所提方案通過預(yù)先警報顯著提高了數(shù)據(jù)包傳輸率，減少了由不可預(yù)測鏈路中斷引起的控制開銷和延遲。它與LAER 相比，也減少了節(jié)點(diǎn)能量方差，增加了網(wǎng)絡(luò)分區(qū)的時間。在高速動態(tài)網(wǎng)絡(luò)中，它表現(xiàn)出更優(yōu)越的性能。在移動性較低的情況下，所改進(jìn)方法與LAER 相比，延遲略高。今后，在不同節(jié)點(diǎn)密度、流量和移動模型中，所提協(xié)議將會是研究的一部分。

［1］ZHANG Guoyin，LI Jun.Mobile peer－to－peer network ［J］.Journal of Software，2013，24 （1）：139－152 （in Chinese）.［張國印，李軍.移動對等網(wǎng)絡(luò)覆蓋網(wǎng) ［J］.軟件學(xué)報，2013，24 （1）：139－152.］

［2］LU Yang，TIAN Yiming，WEI Zhen，et al.Complex－network effects of multi－radio wireless ad hoc networks ［J］.Journal of Applied Science，2012，30 （2）：111－115 （in Chinese）.［陸陽，田一鳴，魏臻，等.多射頻無線ad hoc網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)效應(yīng) ［J］.應(yīng)用科學(xué)學(xué)報，2012，30 （2）：111－115.］

［3］Minhas UF，Zhang J，Tran T，et al.Towards expanded trust management for agents in vehicular ad－h(huán)oc networks［J］.International Journal of Computational Intelligence Theory and Practice，2010，5 （1）：3－15.

［4］Morteza Maleki，Karthik，Pedram.Power－aware source routing protocol for mobile ad hoc networks ［C］／／ISLPED，2008.

［5］LIU Rong，WANG Dong，LI Xiaohong.Based on the remaining time to live link stability routing protocol in mobile ad hoc network ［J］.Engineering and Computer Science，2012，34（12）：9－15 （in Chinese）.［劉榮，王東，李曉鴻.移動ad hoc網(wǎng)絡(luò)中基于剩余生存時間的鏈路穩(wěn)定性路由協(xié)議 ［J］.計算機(jī)工程與科學(xué)，2012，34 （12）：9－15.］

［6］Noppakum Y，Phongsak K.AODV improvement for vehicular networks with cross layer technique and mobility prediction ［J］.Intelligent Signal processing and Communication Systems，2011，8 （2）：89－95.

［7］Panichpapiboon S，F(xiàn)errari G，Tonguz OK.Connectivity of ad hoc wireless networks：An alternative to graph－theoretic approaches［J］.Wireless Networks，2010，16 （3）：793－811.

［8］Nityananda Sharm，Sukumar Nandi.Route stability based QoS routing in mobile ad hoc networks［J］.Wireless Personal Com－munications，2010，54 （1）：203－224.

［9］Park GW，Lee S.A routing protocol for extent network lifetime through the residual battery and link stability in MANET［C］／／Applied Computing Conference，2008.

［10］Jinchang L，Maode M.Cross－layer QoS support framework and holistic opportunistic scheduling for QoS in single carrier WiMAX system ［J］.Journal of Network and Computer Applications，2011，34 （2）：765－773.

［11］Nityananda S，Sukumar N.Route stability based QoS routing in mobile ad hoc networks［J］.Wireless Personal Communications，2010，54 （1）：203－224.

［12］Geng Y，He J，Pahlavan K.Modeling the effect of human body on TOA based indoor human tracking ［J］.International Journal of Wireless Information Networks，2013，20 （4），306－317.