劉期建，鄭 濤

（中國民用航空飛行學院 計算機學院，四川 廣漢618307）

0 引 言

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

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

1 相關研究

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

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

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

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

2 問題的描述

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

其中

并且Ri＞EThr1，qi＜QThresh。

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

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

最大化目標的和，表示如下

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

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

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

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

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

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

3.2 路由選擇

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

算法1：目標節(jié)點執(zhí)行

3.3 路由維護

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

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

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

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

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

算法2：路由維護

4 實驗結(jié)果及分析

4.1 性能指標

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

4.2 模擬參數(shù)

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

表1 模擬參數(shù)

4.3 仿真結(jié)果分析

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

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

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

剩余節(jié)點能量的方差如圖3所示。該參數(shù)表征了協(xié)議的負載平衡能力。觀察到，隨著移動性的增加，由于頻繁的路由轉(zhuǎn)換，節(jié)點剩余能量方差逐漸減小。低移動時，所提方法、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é)點移動性和電池能量流失引起的鏈路中斷。RSEA 協(xié)議中結(jié)合了 “先接后斷”路由維護機制，可以很快適應網(wǎng)絡的變化。在高速移動性時，所提方法性能上比RSEA 高出14%。

圖1 控制開銷與節(jié)點移動性的關系

圖2 PDR 與節(jié)點移動性的關系

圖3 能量方差與節(jié)點移動性的關系

圖4 端對端延遲與節(jié)點移動性的關系

5 結(jié)束語

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

［1］ZHANG Guoyin，LI Jun.Mobile peer－to－peer network ［J］.Journal of Software，2013，24 （1）：139－152 （in Chinese）.［張國印，李軍.移動對等網(wǎng)絡覆蓋網(wǎng) ［J］.軟件學報，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)絡的復雜網(wǎng)絡效應 ［J］.應用科學學報，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)絡中基于剩余生存時間的鏈路穩(wěn)定性路由協(xié)議 ［J］.計算機工程與科學，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.