自適應(yīng)動態(tài)功率控制的機會網(wǎng)絡(luò)節(jié)能高效路由算法

李季碧,李賓,任智,陳前斌

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室, 400065, 重慶)

自適應(yīng)動態(tài)功率控制的機會網(wǎng)絡(luò)節(jié)能高效路由算法

李季碧,李賓,任智,陳前斌

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室, 400065, 重慶)

針對機會網(wǎng)絡(luò)中基于跨層設(shè)計的能量高效路由算法(ERBC)存在的未考慮節(jié)點運動、部分數(shù)據(jù)消息傳輸時能耗偏大、矢量消息交換過程有冗余控制開銷的問題,提出一種自適應(yīng)動態(tài)功率控制的節(jié)能路由算法(ERAPC)加以解決。ERAPC算法通過拓展確認字符(ACK)幀的使用改進了基于接收信號強度指示值(RSSI)的節(jié)點測距機制,將功率控制的范圍從部分數(shù)據(jù)消息擴展到全部,以減少節(jié)點能耗;通過等待收發(fā)節(jié)點盡可能靠近后才傳送數(shù)據(jù),進一步減小節(jié)點能量消耗;通過提出一種更簡捷的矢量消息交換新機制,減少網(wǎng)絡(luò)控制開銷。仿真結(jié)果表明,與ERBC算法相比,ERAPC算法的比特能耗至少降低了27.27%,控制開銷則減小了11.87%以上。

機會網(wǎng)絡(luò);路由算法;節(jié)能;功率控制;開銷

路由技術(shù)是機會網(wǎng)絡(luò)體系結(jié)構(gòu)中的重要組成部分,對數(shù)據(jù)傳輸和網(wǎng)絡(luò)整體性能有關(guān)鍵性的影響作用,因此目前受到較多關(guān)注[1-4]。節(jié)能路由算法的研究重點旨在減少數(shù)據(jù)傳輸過程中節(jié)點的能量消耗。機會網(wǎng)絡(luò)中的節(jié)點多依靠電池供電,攜帶的能量有限,而在復(fù)雜的無線環(huán)境下電池的更換往往較為困難,這使得人們開始重視對機會網(wǎng)絡(luò)節(jié)能路由算法[5]的研究。

目前,根據(jù)節(jié)能策略的不同,可將機會網(wǎng)絡(luò)節(jié)能路由算法分為間接節(jié)能和直接節(jié)能路由算法2大類。典型的間接節(jié)能的路由算法包括文獻[6]提出的短期到達率估計算法(short-term arrival rate estimation, STAR)和文獻[7]提出的n-Epidemic路由算法等,該類路由算法通過減少控制消息或數(shù)據(jù)發(fā)送次數(shù)來達到節(jié)能效果。直接節(jié)能的典型路由算法又可分為2類:一類如文獻[8]提出的基于接觸時間的休眠機制(sleep scheme based on contact time, SSCT),該類算法旨在通過讓節(jié)點適當(dāng)?shù)匦菝邅磉_到減少能耗的目的;另一類采用功率控制的思路,如文獻[9]提出的基于跨層設(shè)計的能量高效路由算法(energy-efficient routing algorithm based on cross-layer design, ERBC),該類算法使用接收信號強度指示值(received signal strength indication, RSSI)等技術(shù)調(diào)整節(jié)點發(fā)射功率,通過減少發(fā)送功率達到節(jié)能的目的。ERBC算法是一種代表性的采用功率控制、具有直接節(jié)能效果的路由算法,但在研究中發(fā)現(xiàn)ERBC算法在原理方面仍然存在以下不足:①在傳輸數(shù)據(jù)時只進行一次功率調(diào)整,在節(jié)點移動的情況下存在功率控制不準確的問題,影響節(jié)能效果和傳送成功率;②在2個節(jié)點相互傳送數(shù)據(jù)時只有一個節(jié)點能進行功率控制,導(dǎo)致部分數(shù)據(jù)消息傳輸能耗偏大;③在節(jié)點測距時忽略了媒體介入控制(media access control, MAC)層確認(acknowledgement, ACK)幀的使用,使得用于測距的消息種類和數(shù)量有限,導(dǎo)致測距開銷偏大;④在矢量交換過程中存在冗余的矢量消息。本文為解決目前機會網(wǎng)絡(luò)中具有代表性的節(jié)能路由算法ERBC所存在的上述4個問題,提出一種新的自適應(yīng)動態(tài)功率控制的節(jié)能高效路由算法——ERAPC。

1 模型及相關(guān)技術(shù)描述

1.1 機會網(wǎng)絡(luò)模型

機會網(wǎng)絡(luò)的數(shù)學(xué)模型為G=(V,E),其中V表示所有節(jié)點的集合,V={v1,v2,…,vn}(n表示網(wǎng)絡(luò)節(jié)點數(shù),vn代表第n個網(wǎng)絡(luò)節(jié)點),E表示所有鏈路的集合且E=?∪{e1,e2,…,ek}(ek為網(wǎng)絡(luò)中第k條鏈路)。

當(dāng)機會網(wǎng)絡(luò)中2個節(jié)點相互進入對方的通信范圍時,它們之間會生成1條鏈路,用{ei,(tsi,tei)}表示該鏈路,其中1≤i≤n(n-1),tsi、tei分別表示該鏈路的生成時間和終止時間,且tsi

根據(jù)上述機會網(wǎng)絡(luò)路由模型,數(shù)據(jù)消息從源節(jié)點S傳輸至目的節(jié)點D的過程示意圖如圖1所示。

圖1 機會網(wǎng)絡(luò)數(shù)據(jù)消息傳輸示意圖

在t1時刻存在節(jié)點S到B的通信鏈路,記為{e1,(ts1,te1)},則S將攜帶的數(shù)據(jù)消息傳輸給節(jié)點B;在t2時刻存在節(jié)點B到C的通信鏈路,記為{e2,(ts2,te2)},則B將攜帶的數(shù)據(jù)消息傳輸給節(jié)點C;在t3時刻存在節(jié)點C到D的通信鏈路,記為{e3,(ts3,te3)},則C將攜帶的數(shù)據(jù)消息傳輸給節(jié)點D?？梢?上述情形滿足相鄰2條鏈路中前一條鏈路的生成時間均小于后一條鏈路的終止時間。

1.2 能量模型

本文采用的節(jié)點能量消耗模型如下[11]

(1)

ERX=kEelec

(2)

式中:k為比特數(shù);d為節(jié)點間距離;Eelec為發(fā)送和接收單位比特信息的損耗常量;εfs、εamp分別是這2種模型中功率放大電路的功耗系數(shù)。式(1)為節(jié)點發(fā)送信息能耗,式(2)為節(jié)點接收信息能耗。

1.3 節(jié)點發(fā)射功率等級

將節(jié)點的固定發(fā)射功率P設(shè)置為最高等級,把發(fā)射功率從0到P平均分為n等份,每一個發(fā)射功率等級對應(yīng)一個相應(yīng)的通信范圍。假設(shè)每個節(jié)點的通信范圍是一個半徑為R的圓形區(qū)域,將該圓形區(qū)域以半徑R為基準分為n份,則發(fā)射功率等級y與距離d的對應(yīng)關(guān)系為

(3)

1.4 RSSI測距模型

本文采用地面反射雙線模型,用PS表示節(jié)點S的發(fā)射信號強度,用PR表示節(jié)點R的接收信號強度,則2個節(jié)點之間的距離為

(4)

式中:c為傳播影響因子,它是由天線增益和具體的無線信號傳播環(huán)境等因素決定的一個常數(shù)。

2 ERAPC算法

本文ERAPC算法在功率控制過程中引入ACK幀的使用,節(jié)點在發(fā)送數(shù)據(jù)消息時通過RSSI測距多次調(diào)整節(jié)點的發(fā)射功率;自節(jié)點利用MAC層的ACK幀的保留位捎帶“有無其他鄰居”信息給它節(jié)點,有條件地等待2個節(jié)點靠近后再進行消息傳遞;提出在2個節(jié)點相遇初期只進行一次摘要矢量(summary vector, SV)和請求矢量(request vector, RV)交互的矢量交換機制。

ERAPC算法的主要操作步驟如下。

設(shè)節(jié)點A、B相互進入對方的通信范圍并且都有數(shù)據(jù)要發(fā)送給對方;并且假設(shè)B收到A周期性廣播的探尋(Hello)消息,記此時為T=0時刻。A、B根據(jù)ERAPC算法進行操作的步驟如下。

(1)節(jié)點A以固定功率周期性廣播Hello消息(其他節(jié)點也進行此操作)。

(2)節(jié)點B收到A廣播的Hello消息,記該時刻為t11,節(jié)點B以固定功率向A單播SV消息,并且用式(4)根據(jù)接收信號強度估算出此時A、B之間的距離

(5)

式中:P是已知的節(jié)點的固定發(fā)射功率;P1是接收的Hello消息的信號強度值。

(3)節(jié)點A收到SV,記此時為時刻t1,節(jié)點A用式(4)根據(jù)接收信號強度估算出此時A、B之間的距離

(6)

式中:P2是接收的SV消息的信號強度值。

節(jié)點A根據(jù)計算出來的dAB1,計算發(fā)送ACK幀的傳輸距離。為了保證對方節(jié)點B一定能夠收到節(jié)點A發(fā)送的ACK確認幀,假定B以最大速度與本節(jié)點A作相反方向的運動的極端情況,則此時估算出來的節(jié)點A發(fā)送ACK確認幀的傳輸距離為

dACK=dAB1+Tmax(Vmax+Vmine)+

(7)

式中:Tmax為節(jié)點的最大處理時延;Vmax為網(wǎng)絡(luò)中所有節(jié)點的最大移動速度;Vmine為節(jié)點自身的移動速度;LACK為ACK確認幀的長度,LSV為SV消息的長度;B為帶寬;此處忽略傳播時延。

為了告知對方節(jié)點B是否可以等待兩節(jié)點靠近后再進行數(shù)據(jù)消息傳遞,本節(jié)點A采用跨層信息共享機制,如圖2所示,節(jié)點A將自己有無其他鄰居節(jié)點的信息裝入ACK幀中,選取IEEE802.11標準[12]規(guī)定的ACK幀的Frame Control域中的保留字段To DS記錄鄰居節(jié)點情況信息:當(dāng)本節(jié)點A周圍有其他鄰居節(jié)點存在時則將該字段置“1”,否則置“0”。節(jié)點A裝填好ACK幀的鄰居信息后,節(jié)點A根據(jù)估算出來的傳輸距離dACK作如下判斷:若dACK

圖2 節(jié)點跨層信息共享示意圖

(4)節(jié)點A發(fā)送完ACK幀后,以固定功率向B發(fā)送其請求矢量RV。

(5)節(jié)點B收到節(jié)點A發(fā)送過來的RV消息后,記此時刻為t22,再將自己有無其他鄰居節(jié)點的信息裝入對RV消息的ACK幀中并以固定功率發(fā)送ACK幀,并根據(jù)接收信號強度估算出此時A、B之間的距離

(8)

式中:P3是接收的RV消息的信號強度。

節(jié)點B計算出dAB22后,作如下判斷。①若dAB11≤dAB22,表明2個節(jié)點有相互遠離或者保持相對靜止的趨勢并且短時間內(nèi)保持該趨勢不變,此時節(jié)點B根據(jù)計算出來的距離dAB22,假設(shè)節(jié)點A以最大速度作相反方向運動的極端情況,估算出來的發(fā)送dataB1數(shù)據(jù)消息的傳輸距離為

ddataB1=dAB22+Tmax(Vmax+Vmine)+

(9)

式中:Vmine為節(jié)點自身的移動速度;LdataB1為dataB1數(shù)據(jù)消息的長度。節(jié)點B根據(jù)計算出來的ddataB1去選擇適當(dāng)?shù)陌l(fā)射功率等級即可。

節(jié)點B以發(fā)送dataB1數(shù)據(jù)消息的發(fā)射功率等級去發(fā)送節(jié)點B剩下的需要發(fā)送的數(shù)據(jù),直到等待時間Twait2后再進行功率自適應(yīng)調(diào)整。為了保證在等待時間Twait2內(nèi)節(jié)點使用同一發(fā)射功率等級發(fā)送消息時對方節(jié)點一定能夠收到,假設(shè)對方節(jié)點以最大速度與本節(jié)點作相反方向運動,此時計算出來的等待時間Twait2最小

(10)

(11)

式中:VB(t)為節(jié)點B的運動速度;Vmax為節(jié)點的最大運動速度;R為節(jié)點以最高發(fā)射功率等級發(fā)送消息時的通信半徑范圍;mod表示取余數(shù)操作;n是總的功率等級數(shù);d0為2個相鄰的發(fā)射功率等級對應(yīng)的通信范圍之差。等待時間Twait2后,節(jié)點B發(fā)送數(shù)據(jù)消息的功率自適應(yīng)調(diào)整過程跟前面所述的一樣。②若dAB11>dAB22,表明2個節(jié)點有相互靠近運動的趨勢并且短時間內(nèi)保持該趨勢不變;如果節(jié)點A有其他鄰居節(jié)點存在,則節(jié)點B根據(jù)式(9)估算功率等級,然后發(fā)送dataB1數(shù)據(jù)消息;如果節(jié)點A沒有其他鄰居節(jié)點,則節(jié)點B等待2個節(jié)點靠近至最小發(fā)射功率等級所對應(yīng)的通信范圍后,再進行跨層功率調(diào)整以發(fā)送數(shù)據(jù)。設(shè)等待時間為tB,則有

(12)

如果節(jié)點在等待時間內(nèi)的運動方向沒有發(fā)生突變(遠離或者靜止),則等待時間tB后,節(jié)點以最小的發(fā)射功率等級發(fā)送dataB1數(shù)據(jù)消息;如果節(jié)點在等待時間內(nèi)的運動方向發(fā)生突變,則節(jié)點立即根據(jù)式(9)估算功率等級,然后發(fā)送dataB1數(shù)據(jù)消息;如果沒有數(shù)據(jù)要發(fā)送給對方節(jié)點,則節(jié)點立即根據(jù)dAB22估算功率等級,然后單播發(fā)送Hello消息給對方節(jié)點,下一個Hello消息延遲到正常的發(fā)送時刻發(fā)送,并且節(jié)點跨層泛聽Hello消息,即在MAC層判斷數(shù)據(jù)段的長度是否等于Hello消息的長度,如果是的話,則不管在MAC層是單播還是廣播都上傳到網(wǎng)絡(luò)層,這樣可避免Hello消息丟失。

(6)節(jié)點A、B交換數(shù)據(jù)消息。在此過程中,發(fā)送數(shù)據(jù)消息用估算功率,發(fā)送ACK幀用固定功率。

節(jié)點A收到對RV消息的ACK確認幀后,記此時為時刻t2;節(jié)點A根據(jù)接收信號強度估算出A、B之間的距離

(13)

式中:PACK是接收的ACK確認幀的信號強度。

節(jié)點A計算出來dAB2后,作如下判斷。①若dAB1≤dAB2,則表明2個節(jié)點有相互遠離或者保持相對靜止的趨勢,此時假設(shè)節(jié)點B以最大速度作相反方向運動的極端情況,估算出來的發(fā)送data1數(shù)據(jù)消息的傳輸距離為

ddata1=dAB2+Tmax(Vmax+Vmine)+

(14)

式中:Vmine為節(jié)點自身的移動速度;Ldata1為data1數(shù)據(jù)消息的長度;LACK為MAC層ACK幀的長度。節(jié)點A計算出來ddata1后,根據(jù)ddata1選擇適當(dāng)?shù)陌l(fā)射功率等級發(fā)送數(shù)據(jù)data1。節(jié)點A以發(fā)送data1數(shù)據(jù)消息的發(fā)射功率等級去發(fā)送節(jié)點A剩下的需要發(fā)送的數(shù)據(jù),直到等待時間Twait后再進行功率自適應(yīng)調(diào)整。對于等待時間Twait的計算,與步驟(5)中所述的一樣

(15)

式中VA(t)為節(jié)點A的運動速度。等待時間Twait后,節(jié)點A發(fā)送數(shù)據(jù)消息的功率自適應(yīng)調(diào)整過程跟前面所述的一樣。②若dAB1>dAB2,則表明2個節(jié)點有相互靠近運動的趨勢:如果節(jié)點B有其他鄰居節(jié)點存在,則節(jié)點A使用發(fā)送對SV消息的ACK確認幀的發(fā)射功率等級去發(fā)送data1數(shù)據(jù)消息;如果節(jié)點B沒有其他鄰居節(jié)點存在,則節(jié)點A等待2個節(jié)點靠近至最小發(fā)射功率等級所對應(yīng)的通信范圍后再進行跨層功率調(diào)整發(fā)送數(shù)據(jù)。假設(shè)等待時間為tA,則有

(16)

如果節(jié)點在等待時間內(nèi)的運動方向沒有發(fā)生突變(遠離或者靜止),則節(jié)點在等待時間tA后,以最小的發(fā)射功率等級發(fā)送data1數(shù)據(jù)消息;如果節(jié)點在等待時間內(nèi)的運動方向發(fā)生突變,則節(jié)點立即根據(jù)式(14)估算出來的發(fā)射功率等級去發(fā)送data1;如果沒有數(shù)據(jù)要發(fā)送給對方節(jié)點,則節(jié)點立即根據(jù)dAB2估算功率等級,然后單播發(fā)送Hello消息給對方節(jié)點,具體操作與步驟(5)中所述的相同。

節(jié)點A和B收到對方發(fā)來的數(shù)據(jù)消息后,都以固定功率發(fā)送對應(yīng)的ACK幀。在2個節(jié)點隨機爭用信道發(fā)送數(shù)據(jù)消息的過程中,如果出現(xiàn)其中一個節(jié)點在等待時間Twait或者Twait2內(nèi)一直沒有機會發(fā)送自己緩存的數(shù)據(jù)消息,則在等待時間Twait或者Twait2后,節(jié)點有機會發(fā)送數(shù)據(jù)消息時,該節(jié)點將以固定功率去發(fā)送自己將要發(fā)送的第一個數(shù)據(jù)消息,之后的功率自適應(yīng)調(diào)整過程與前面所述的一樣。

此外,在ERAPC算法中,節(jié)點也采用數(shù)據(jù)消息有條件地廣播策略,即當(dāng)條件{有多個鄰居節(jié)點}∩{鄰居中無目的節(jié)點}∩{有多個鄰居節(jié)點同時需要接收該數(shù)據(jù)消息}同時滿足時,當(dāng)前節(jié)點對該數(shù)據(jù)消息進行廣播。并且規(guī)定,此時當(dāng)前節(jié)點選擇的發(fā)射功率等級必須要保證需要接收數(shù)據(jù)消息的多個鄰居節(jié)點一定能夠接收到該數(shù)據(jù)消息。

3 ERAPC算法的能耗分析

定理1ERAPC算法相比于固定發(fā)射功率的能耗平均減少0.56εfsr2(r為節(jié)點以固定發(fā)射功率等級發(fā)送數(shù)據(jù)消息時的通信半徑)。

證明設(shè)網(wǎng)絡(luò)中的任意一個節(jié)點位于通信半徑為r的圓形區(qū)域中心,鄰居節(jié)點可以位于該圓形區(qū)域的任一點,x表示2個節(jié)點相遇后的距離,則x的分布函數(shù)為

(17)

得出上述分布函數(shù)的概率密度函數(shù)為

(18)

得出2個節(jié)點相遇后的平均距離為

(19)

根據(jù)式(1)可知,節(jié)點以固定發(fā)射功率發(fā)送1bit信息所需的發(fā)送能耗為ETX1=Eelec+εfsr2

(20)

式中:εfs為功率放大電路的功耗系數(shù)。

節(jié)點以估算功率發(fā)送1bit信息的平均發(fā)送能耗為

(21)

故得出節(jié)點以固定發(fā)射功率發(fā)送1bit信息和以估算功率發(fā)送1bit信息的能耗差為

(22)

由此可知,相比于以固定發(fā)射功率發(fā)送消息時的情況,ERAPC算法每發(fā)送1bit信息,平均可減少大概0.56εfsr2J的發(fā)射能耗,從而命題得證。

證明假設(shè)在一個L×W的矩形區(qū)域中,每個采樣時刻t所對應(yīng)的網(wǎng)絡(luò)可表示為一個簡單無向圖Gp(r)(V,E,t),其中V表示場景中所有的節(jié)點,其網(wǎng)絡(luò)規(guī)模為N=|V|,p(r)表示當(dāng)通信半徑為r時場景中任意2個節(jié)點存在無線通信鏈路的概率,當(dāng)且僅當(dāng)|vj-vi|≦r時,2個節(jié)點{vj,vi}互為鄰居,即組成鏈路集合E,則由條件可知,場景中節(jié)點的度為

λ=πr2(N/L)W-1

(23)

節(jié)點的到達數(shù)滿足泊松分布

(24)

假設(shè)2個節(jié)點相遇后,相互之間進行消息交互的概率為a,則平均每個節(jié)點與其相遇節(jié)點進行消息交互的次數(shù)Y服從強度為λa的泊松分布,則得出總的節(jié)點相遇并進行信息交互的次數(shù)為λaN。

根據(jù)算法原理可知,在ERAPC算法中所有發(fā)送的數(shù)據(jù)消息都能以估算功率發(fā)送,而在ERBC算法中,只能有一半的數(shù)據(jù)消息以估算功率發(fā)送,則相比于ERBC算法,ERAPC算法平均可減少的數(shù)據(jù)消息發(fā)送能耗為

(25)

ERAPC算法在每次節(jié)點相遇時減少了一個RV消息和一個SV消息的發(fā)送,并且減少的這個RV消息和SV消息在ERBC算法中都是以估算功率發(fā)送的,因此相比于ERBC算法,ERAPC平均減少的總的控制消息發(fā)送能耗為

(26)

另外,在ERBC算法中,節(jié)點每次以固定發(fā)射功率發(fā)送ACK確認幀,而在ERAPC算法中,節(jié)點在每次相遇交互消息時,可以以估算功率發(fā)送ACK確認幀,則ERAPC算法平均可減少的ACK確認幀的發(fā)送能耗為

(27)

綜上,即得出在相同的網(wǎng)絡(luò)條件下,ERAPC算法比ERBC算法平均減少的發(fā)射能耗為

(28)

顯然,PEERPC>0,即ERAPC算法的能耗相對更小。

證畢。

4 仿真分析

使用仿真軟件平臺OPNET Modeler 14.5進行仿真。參考經(jīng)典的Epidemic算法[13]和ERBC算法在驗證過程中采用的仿真參數(shù)設(shè)置,同時考慮目前常用的IEEE802.11a標準定義的指標,對主要仿真參數(shù)的設(shè)置如表1所示。

根據(jù)節(jié)點初始通信范圍的不同,設(shè)置了5個不同的仿真場景,在每個仿真場景中都將節(jié)點的發(fā)射功率等級設(shè)置為8級。節(jié)點的不同初始通信范圍所對應(yīng)的8個功率等級通信范圍如表2所示。

在每個仿真場景下分別運行ERAPC、Epidemic、n-Epidemic和ERBC算法,并分別統(tǒng)計這4個算法在不同仿真場景下的節(jié)點比特能耗、歸一化控制開銷、網(wǎng)絡(luò)壽命和數(shù)據(jù)消息傳送成功率,每組實驗分別進行5次,實驗結(jié)果取平均值。所得到的實驗結(jié)果如圖3～圖6所示。

表1 仿真參數(shù)設(shè)置

表2 能量等級對應(yīng)的通信范圍

圖3顯示了在不同的仿真場景下1bit數(shù)據(jù)消息從源節(jié)點成功送達目的節(jié)點所消耗的平均能量。從圖3中可以看出,隨著節(jié)點通信范圍的擴大,統(tǒng)計出的節(jié)點比特能耗增大,這是因為節(jié)點通信范圍的擴大使得節(jié)點之間的接觸機會增多,節(jié)點之間交互次數(shù)增多,節(jié)點能耗增大的緣故。Epidemic算法和n-Epidemic算法因為沒有使用發(fā)射功率自適應(yīng)調(diào)整策略,故其節(jié)點比特能耗較大。

圖3 4種算法的節(jié)點比特能耗比較

此外,相比于ERBC算法,新算法ERAPC的節(jié)點比特能耗最多減少了31.92%。這是由于以下2個原因造成的:一是新算法ERAPC優(yōu)化了功率自適應(yīng)調(diào)整過程的節(jié)能策略,有條件地等待2個節(jié)點靠近后再進行跨層功率調(diào)整發(fā)送數(shù)據(jù)消息,增加了估算等待時間Twait,在節(jié)點發(fā)送消息時多次動態(tài)調(diào)整節(jié)點發(fā)射功率,使得新算法減少了能量浪費現(xiàn)象;二是新算法ERAPC減少了RV消息和SV消息的發(fā)送個數(shù),從而減少了節(jié)點發(fā)送多余消息造成的能量消耗。

實驗中的統(tǒng)計量歸一化控制開銷是所有節(jié)點發(fā)出的控制消息包含的比特數(shù)與所有節(jié)點發(fā)送的控制消息和到達目的節(jié)點的數(shù)據(jù)消息包含的比特數(shù)之和的比值。圖4為4種算法的歸一化控制開銷比較。由圖4可見,本文ERAPC算法的歸一化控制開銷在每個場景中均低于ERBC、Epidemic和n-Epidemic算法,這主要是因為ERAPC算法減少了控制消息SV和RV的發(fā)送個數(shù)。

圖4 4種算法的歸一化控制開銷比較

圖5 4種算法的網(wǎng)絡(luò)壽命比較

圖5顯示的是不同仿真場景下節(jié)點網(wǎng)絡(luò)壽命比較情況。由圖5可見,隨著節(jié)點通信范圍的擴大,第一個節(jié)點死亡的時間越來越早,這是因為隨著節(jié)點通信范圍的擴大,節(jié)點間的接觸機會增多,消息交互頻繁程度加大,這使得節(jié)點的能量消耗增大,進而導(dǎo)致節(jié)點容易過快死亡。另外,如圖5中所示,使用了ERAPC算法的網(wǎng)絡(luò)壽命要長于另外3種算法的網(wǎng)絡(luò)壽命,這是因為ERAPC減少了RV消息和SV消息的發(fā)送,有效地減少了節(jié)點的發(fā)射能量消耗,從而延長了網(wǎng)絡(luò)壽命。

圖6顯示的是不同的仿真場景中成功接收的數(shù)據(jù)消息數(shù)占發(fā)送數(shù)據(jù)消息總數(shù)的百分比的比較情況。由圖6可見,隨著節(jié)點通信范圍的擴大,數(shù)據(jù)消息傳送成功率出現(xiàn)了一定程度的降低,這是因為隨著節(jié)點通信范圍的擴大,節(jié)點間的接觸機會增多,會出現(xiàn)導(dǎo)致部分節(jié)點的能量消耗過快而死亡的情況,進而造成數(shù)據(jù)消息傳送成功率的降低。另外,ERAPC算法的數(shù)據(jù)消息傳送成功率要高于另外3種算法,這是因為ERAPC算法比其他3種算法更加節(jié)能的緣故。

圖6 4種算法的數(shù)據(jù)消息傳送成功率比較

5 結(jié) 論

本文針對基于功率控制的機會網(wǎng)絡(luò)節(jié)能路由算法存在的節(jié)能效果不足和控制開銷偏大等問題,提出一種自適應(yīng)動態(tài)功率控制的機會網(wǎng)絡(luò)節(jié)能高效路由算法ERAPC。新算法重新設(shè)計了節(jié)點的自適應(yīng)動態(tài)發(fā)射功率調(diào)節(jié)機制,調(diào)整了用于測距的消息種類,有條件地等待2個節(jié)點靠近后再用更小的功率發(fā)送數(shù)據(jù)消息,并且減少了RV和SV消息的冗余發(fā)送。仿真結(jié)果表明,與ERBC算法相比,ERAPC算法至少降低了27.27%的數(shù)據(jù)傳輸能耗和11.87%的控制開銷。

[1] POONGUZHARSELVI B, VETRISELVI V. Survey on routing algorithms in opportunistic networks [C]∥Proceedings of International Conference on Computer Communication and Informatics. Piscataway, NJ, USA: IEEE, 2013: 1-5.

[2] CAO Y, SUN Z, WANG N, et al. Converge-and-diverge: a geographic routing for delay/disruption-tolerant networks using a delegation replication approach [J]. IEEE Transactions on Vehicular Technology, 2013, 62(5): 2339-2343.

[3] NIU J, GUO J, CAI Q, et al. Predict and spread: an efficient routing algorithm for opportunistic networking [C]∥Proceedings of 2011IEEE Wireless Communications and Networking Conference. Piscataway, NJ, USA: IEEE, 2011: 498-503.

[4] LIU H, CHEN Y. A moving scope aware routing approach for opportunistic networks [C]∥Proceedings of 2010International Conference on Wireless Communications and Signal Processing. Piscataway, NJ, USA: IEEE, 2010: 1-5.

[5] CHOI B J, SHEN X. Adaptive asynchronous sleep scheduling protocols for delay tolerant networks [J]. IEEE Transactions on Mobile Computing, 2011, 10(9): 1283-1296.

[6] WANG W, MOTANI M, SRINIVASAN V. Opportunistic energy-efficient contact probing in delay-tolerant applications [J]. IEEE/ACM Transactions on Network, 2009, 17(5): 1592-1605.

[7] LU X, HUI P. An energy-efficient n-epidemic routing protocol for delay tolerant networks [C]∥Proceedings of the 5th International Conference on Networking, Architecture, and Storage. Piscataway, NJ, USA: IEEE, 2010: 341-347.

[8] 付凱, 夏靖波, 尹波. DTN中一種基于接觸時間的休眠機制 [J]. 計算機科學(xué), 2013, 40(2): 87-90. FU Kai, XIA Jingbo, YIN Bo. Sleep scheme based on contact time in DTN [J]. Computer Science, 2013, 40(2): 87-90.

[9] YAO Y K, ZHENG W X, REN Z. An energy-efficient routing algorithm for disruption tolerant networks [C]∥Proceedings of the 2012 2nd International Conference on Computer and Information Application, Paris, France: Atlantis Press, 2012: 895-898.

[10]任智, 索建偉, 陳紅. 基于相遇節(jié)點跨層感知的機會網(wǎng)絡(luò)高效低時延路由算法 [J]. 通信學(xué)報, 2013(10): 1-8. REN Zhi, SUO Jianwei, CHEN Hong. Efficient low-delay routing algorithm for opportunistic networks based on cross-layer sensing of encountered nodes [J]. Journal on Communications, 2013(10): 1-8.

[11]HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

[12]GU D, ZHANG J. Qos enhancement in IEEE 802.11wireless local area networks [J]. IEEE Communications Magazine, 2003, 41(6): 120-124.

[13]VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks, CS-2000-06 [R]. Durham, NC, USA: Duke University, 2000.

(編輯 劉楊)

AnEfficientEnergy-SavingRoutingAlgorithmforOpportunisticNetworkswithDynamicallyAdaptivePowerControl

LI Jibi,LI Bin,REN Zhi,CHEN Qianbin

(Key Laboratory of Mobile Communications Technology of Chongqing, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

An efficient energy-saving routing algorithm with dynamically adaptive power control(ERAPC) is proposed to address the problems that there exist large energy consumption for transmitting partial data packets, no consideration of node’s mobility and high control overhead in vector exchange mechanism lying in the energy-efficient routing algorithm based on cross-layer design (ERBC). The ERAPC extends the usage of acknowledgement (ACK) frames to improve the RSSI-based ranging mechanism, to enlarge the range of power control to all data messages and to reduce nodal energy consumption. Until the sender and the receiver move as close as possible, the data messages are sent out to lower the transmit power further; and an efficient new mechanism of exchanging vectors is presented in ERAPC to decrease the control overhead. Simulation results and comparison with the ERBC algorithm show that the energy consumption of each bit in the ERAPC is reduced by at least 27.27% and the control overhead is reduced by at least 11.87%, respectively.

opportunistic networks; routing algorithm; energy-saving; power control; overhead

2014-07-31。

李季碧(1975—),女,碩士,講師;任智(通信作者),男,教授。

國家自然科學(xué)基金資助項目(61379159);教育部長江學(xué)者和創(chuàng)新團隊發(fā)展計劃資助項目(IRT1299);重慶市自然科學(xué)基金資助項目(cstc2012jjA40051)。

時間:2014-09-22

10.7652/xjtuxb201412008

TP393.04

:A

:0253-987X(2014)12-0049-08

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140922.1520.004.html