一種能量有效的多徑Ad Hoc網路由算法

吳 慧， 侯 嘉

（蘇州大學 電子信息學院，江蘇 蘇州215006）

0 引言

Ad Hoc網絡多徑路由的可靠性和網絡資源利用率比單徑路由高，國內外的專家學者就 Ad Hoc網絡多徑路由技術提出了不少建設性的方案[1-7]。每種路由協議都有各自的優缺點，很難設計出適合所有應用環境的路由協議，特別是有些應用環境對傳輸不同數據會有不同等級的可靠性和實時性要求，如果將所有數據按照統一的要求進行處理，將會對網絡資源造成極大的浪費，縮短網絡的生存時間。現研究一種能滿足QoS需求的多路徑多速率路由算法EAMM，該算法中的節點能根據數據的可靠性和實時性要求，結合地理位置、延遲時間、丟包率和剩余能量信息選擇符合要求的若干條路徑。仿真結果顯示，該算法在保證各等級可靠性和實時性的數據按照要求傳輸的情況下能均衡網絡的能量消耗，延長網絡的生存時間。

1 算法參數介紹

1.1 速率的計算

首先是利用一種保證網絡傳輸速率在一個全局定義的傳輸速率閾值之上的SPEED[8]協議思想。文中假設數據包的有效期限 treq和可靠性preq已知。源節點s根據數據的有效期限 treq和到目標節點d距離的ls,d計算出最小的傳輸速率：

對于中間節點i，其到達鄰居節點j的速率為：

這里，τi,j是節點i到節點j傳輸延時的估計值。

1.2 節點丟包率的計算

每個節點 i保留的最近一段觀察時間Δt內到鄰居節點j的平均丟包率為：

其中，Nsend為在Δt內節點 i發送的數據包個數，Ndrop為在Δt內鄰居節點j未收到的數據包個數。

1.3 能量消耗的計算

處理一個數據包所需要的時間為：

其中，L(n)表示第n個數據包的長度，B表示帶寬。

發送和接收一個數據包的能量消耗分別為：

節點的剩余能量：

2 協議描述

前提假設：每個節點知道自己和它通信范圍內的相鄰節點的地理位置，并且會周期性地發送位置信息包進行更新。

2.1 路由選擇策略

節點依據到鄰居節點的傳輸速率reqV將鄰居節點分成3種速率等級。源節點根據最小傳輸速率要求req

V將數據包劃分到相應的速率層。此方法可以滿足數據傳輸的實時性要求，但是并不能保證可靠性，還需要采取多路徑機制。

節點i根據到每個鄰居節點j的平均丟包率ei,j，預測出節點i經過鄰居節點j到達目標節點d的概率：

源節點首先從鄰居節點集中選擇到目標節點 s的距離lj,d小于ls,d的若干個節點j，且將源節點s到目標節點d總的到達概率P設為0，然后，每增加一個轉發節點，P就按式(9)更新一次：

當轉發節點個數增加到使得reqP≥P時，就不再增加轉發節點。數據包通過MAC層多播協議轉發給鄰居節點。選取多路徑時并不是路徑越短越好，為了負載的平衡和避開最短路徑上剩余能量很低的節點，只要這條路徑能在reqt內完成數據傳輸即可。同時，由于Ad Hoc網絡節點的能量有限，節省節點的能量和延長整個網絡的生存時間很重要。為此綜合考慮轉發概率和剩余能量E，引入節點穩定性因子：residual

2.2 中間節點處理數據包

中間節點i接收到數據包后，按照以下步驟處理數據包：①判斷該節點不是目標節點且第一次收到該數據包。根據最小傳輸速率要求Vreq將數據包劃分到合適的速率層；②根據公式(8)計算經過鄰居節點j到達目標節點d的概率結合數據包的可靠性要求Preq和公式(9)計算轉發節點個數m；③根據公式(10)計算鄰居節點的穩定性因子Qnode，將滿足要求的鄰居節點按照Qnode由高到低排序，優先選取前m個節點作為轉發節點；④將數據包發送給m個轉發節點。

2.3 路由更新

同樣，由于選擇多個轉發節點時是完全基于本地平均丟包率估計ei,j的，所以中間節點很可能會發現之前的估計信息不準確,需要采取動態補償機制，及時地增加或者減少轉發節點個數。

3 仿真實驗

3.1 仿真環境

在windows操作系統下利用NS-2.31仿真平臺對本算法進行仿真模擬,并和多播路由協議MAODV進行對比。地形設置為1000×1000的平面區域，節點個數50個。節點的傳輸距離為150 m，信道帶寬為2 Mb/s。數據包大小為512 Byte。以恒定的CBR比特流模擬節點的實時業務。仿真結果如下，其中EAMM(a,b)中a表示可靠性，b表示數據有效期限。

由于 EAMM 考慮了數據包的可靠性和實時性要求，在路徑選擇過程中，綜合考慮轉發節點的這兩方面性能，從而建立了具有QoS保證的路徑。從圖1和圖2 可以看出，EAMM算法的數據包投遞率和端到端延遲的性能都優于MAODV。圖1中，當數據的有效期限都設為 0.5，可靠性分別為 0.65和0.8時，后者的數據包投遞率高于前者，說明EAMM算法是有效的。圖2中，當可靠性都設為0.65，有效期限分別為0.5和0.2時，后者的端到端延遲小于前者。圖3表明，隨著數據包發送率的增加，兩種算法的網絡生存時間都逐漸減少，EAMM的網絡生存時間比MAODV長。原因是EAMM選擇剩余能量高的節點傳輸數據，均衡了網絡的能量消耗，延長了網絡的生存時間。圖1、圖2和圖3橫坐標表示的發送率為每個數據包所用時間。

4 結語

本文研究了一種滿足QoS需求的能量有效的多路徑多速率路由算法EAMM，該算法中的節點能綜合考慮地理位置、延遲時間、丟包率和剩余能量信息，選擇符合要求的若干條路徑，滿足數據傳輸的可靠性和實時性要求，延長了網絡的生存時間。仿真結果顯示，與傳統的多播路由協議相比，該算法是有效的自組網多路徑算法。

[1] MARINAL M K,DAS S R. Adhoc on-demand Multipath Distance Vector Routing [J].Wirel Commun Mob Comput,2006(06):969-988.

[2] YU Ming, MALVANKAR A, SU Wei, et al. A Link Availability-based QoS-aware Routing Protocol for Mobile Ad Hoc Sensor Networks[J].Computer Communications, 2007,30(18):3823-3831.

[3] 曾文鋒,戴建輝.能量感知和鏈路穩定度的多徑MANET路由[J].通信技術,2011,44(08):54-57.

[4] 梁榮堅,蔡茂國,張立海.Adhoc網絡中基于鏈路穩定度的QoS路由協議[J].計算機工程與應用,2010, 46(32): 105.

[5] 楊吟君,汪學明.基于AOMDV的多徑路由協議改進及仿真分析[J].通信技術, 2011,44(08):45-47.

[6] 呂建軍,李志蜀,劉勇.Ad hoc網絡穩定的蟻群多路由算法[J].電子科技大學學報,2010,39(04):603-606.

[7] 劉軍,彭宇揚,彭自成.MANET實時傳輸的可靠性研究[J].通信技術,2008,41(05):59-63.

[8] HE T, STANKOVIC J, LU C,et al. SPEED: A Stateless Protocol for Real-Time Commu- nication in Sensor Networks[J]. Proc. IEEE Int. Conf. on Distributed Computing Systems, 2003 (19-22):46-55.