一種能量有效的多徑Ad Hoc網(wǎng)路由算法

吳 慧， 侯 嘉

（蘇州大學(xué) 電子信息學(xué)院，江蘇 蘇州215006）

0 引言

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

1 算法參數(shù)介紹

1.1 速率的計算

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

對于中間節(jié)點i，其到達(dá)鄰居節(jié)點j的速率為：

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

1.2 節(jié)點丟包率的計算

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

其中，Nsend為在Δt內(nèi)節(jié)點 i發(fā)送的數(shù)據(jù)包個數(shù)，Ndrop為在Δt內(nèi)鄰居節(jié)點j未收到的數(shù)據(jù)包個數(shù)。

1.3 能量消耗的計算

處理一個數(shù)據(jù)包所需要的時間為：

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

發(fā)送和接收一個數(shù)據(jù)包的能量消耗分別為：

節(jié)點的剩余能量：

2 協(xié)議描述

前提假設(shè)：每個節(jié)點知道自己和它通信范圍內(nèi)的相鄰節(jié)點的地理位置，并且會周期性地發(fā)送位置信息包進(jìn)行更新。

2.1 路由選擇策略

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

V將數(shù)據(jù)包劃分到相應(yīng)的速率層。此方法可以滿足數(shù)據(jù)傳輸?shù)膶崟r性要求，但是并不能保證可靠性，還需要采取多路徑機(jī)制。

節(jié)點i根據(jù)到每個鄰居節(jié)點j的平均丟包率ei,j，預(yù)測出節(jié)點i經(jīng)過鄰居節(jié)點j到達(dá)目標(biāo)節(jié)點d的概率：

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

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

2.2 中間節(jié)點處理數(shù)據(jù)包

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

2.3 路由更新

同樣，由于選擇多個轉(zhuǎn)發(fā)節(jié)點時是完全基于本地平均丟包率估計ei,j的，所以中間節(jié)點很可能會發(fā)現(xiàn)之前的估計信息不準(zhǔn)確,需要采取動態(tài)補(bǔ)償機(jī)制，及時地增加或者減少轉(zhuǎn)發(fā)節(jié)點個數(shù)。

3 仿真實驗

3.1 仿真環(huán)境

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

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

4 結(jié)語

本文研究了一種滿足QoS需求的能量有效的多路徑多速率路由算法EAMM，該算法中的節(jié)點能綜合考慮地理位置、延遲時間、丟包率和剩余能量信息，選擇符合要求的若干條路徑，滿足數(shù)據(jù)傳輸?shù)目煽啃院蛯崟r性要求，延長了網(wǎng)絡(luò)的生存時間。仿真結(jié)果顯示，與傳統(tǒng)的多播路由協(xié)議相比，該算法是有效的自組網(wǎng)多路徑算法。

[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] 曾文鋒,戴建輝.能量感知和鏈路穩(wěn)定度的多徑MANET路由[J].通信技術(shù),2011,44(08):54-57.

[4] 梁榮堅,蔡茂國,張立海.Adhoc網(wǎng)絡(luò)中基于鏈路穩(wěn)定度的QoS路由協(xié)議[J].計算機(jī)工程與應(yīng)用,2010, 46(32): 105.

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

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

[7] 劉軍,彭宇揚,彭自成.MANET實時傳輸?shù)目煽啃匝芯縖J].通信技術(shù),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.