吳 慧， 侯 嘉

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

0 引言

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

1 算法參數(shù)介紹

1.1 速率的計(jì)算

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

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

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

1.2 節(jié)點(diǎn)丟包率的計(jì)算

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

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

1.3 能量消耗的計(jì)算

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

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

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

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

2 協(xié)議描述

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

2.1 路由選擇策略

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

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

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

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

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

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

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

2.3 路由更新

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

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

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

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

4 結(jié)語(yǔ)

本文研究了一種滿足QoS需求的能量有效的多路徑多速率路由算法EAMM，該算法中的節(jié)點(diǎn)能綜合考慮地理位置、延遲時(shí)間、丟包率和剩余能量信息，選擇符合要求的若干條路徑，滿足數(shù)據(jù)傳輸?shù)目煽啃院蛯?shí)時(shí)性要求，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。仿真結(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] 梁榮堅(jiān),蔡茂國(guó),張立海.Adhoc網(wǎng)絡(luò)中基于鏈路穩(wěn)定度的QoS路由協(xié)議[J].計(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é)報(bào),2010,39(04):603-606.

[7] 劉軍,彭宇揚(yáng),彭自成.MANET實(shí)時(shí)傳輸?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.