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

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室, 400065, 重慶)

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

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

(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室, 400065, 重慶)

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

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

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

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

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

1.1 機(jī)會(huì)網(wǎng)絡(luò)模型

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

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

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

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

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

1.2 能量模型

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

(1)

ERX=kEelec

(2)

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

1.3 節(jié)點(diǎn)發(fā)射功率等級(jí)

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

(3)

1.4 RSSI測(cè)距模型

本文采用地面反射雙線模型,用PS表示節(jié)點(diǎn)S的發(fā)射信號(hào)強(qiáng)度,用PR表示節(jié)點(diǎn)R的接收信號(hào)強(qiáng)度,則2個(gè)節(jié)點(diǎn)之間的距離為

(4)

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

2 ERAPC算法

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

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

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

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

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

(5)

式中:P是已知的節(jié)點(diǎn)的固定發(fā)射功率;P1是接收的Hello消息的信號(hào)強(qiáng)度值。

(3)節(jié)點(diǎn)A收到SV,記此時(shí)為時(shí)刻t1,節(jié)點(diǎn)A用式(4)根據(jù)接收信號(hào)強(qiáng)度估算出此時(shí)A、B之間的距離

(6)

式中:P2是接收的SV消息的信號(hào)強(qiáng)度值。

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

dACK=dAB1+Tmax(Vmax+Vmine)+

(7)

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

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

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

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

(5)節(jié)點(diǎn)B收到節(jié)點(diǎn)A發(fā)送過(guò)來(lái)的RV消息后,記此時(shí)刻為t22,再將自己有無(wú)其他鄰居節(jié)點(diǎn)的信息裝入對(duì)RV消息的ACK幀中并以固定功率發(fā)送ACK幀,并根據(jù)接收信號(hào)強(qiáng)度估算出此時(shí)A、B之間的距離

(8)

式中:P3是接收的RV消息的信號(hào)強(qiáng)度。

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

ddataB1=dAB22+Tmax(Vmax+Vmine)+

(9)

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

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

(10)

(11)

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

(12)

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

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

節(jié)點(diǎn)A收到對(duì)RV消息的ACK確認(rèn)幀后,記此時(shí)為時(shí)刻t2;節(jié)點(diǎn)A根據(jù)接收信號(hào)強(qiáng)度估算出A、B之間的距離

(13)

式中:PACK是接收的ACK確認(rèn)幀的信號(hào)強(qiáng)度。

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

ddata1=dAB2+Tmax(Vmax+Vmine)+

(14)

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

(15)

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

(16)

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

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

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

3 ERAPC算法的能耗分析

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

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

(17)

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

(18)

得出2個(gè)節(jié)點(diǎn)相遇后的平均距離為

(19)

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

(20)

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

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

(21)

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

(22)

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

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

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

(23)

節(jié)點(diǎn)的到達(dá)數(shù)滿足泊松分布

(24)

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

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

(25)

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

(26)

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

(27)

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

(28)

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

證畢。

4 仿真分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

本文針對(duì)基于功率控制的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能路由算法存在的節(jié)能效果不足和控制開銷偏大等問(wèn)題,提出一種自適應(yīng)動(dòng)態(tài)功率控制的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能高效路由算法ERAPC。新算法重新設(shè)計(jì)了節(jié)點(diǎn)的自適應(yīng)動(dòng)態(tài)發(fā)射功率調(diào)節(jié)機(jī)制,調(diào)整了用于測(cè)距的消息種類,有條件地等待2個(gè)節(jié)點(diǎn)靠近后再用更小的功率發(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中一種基于接觸時(shí)間的休眠機(jī)制 [J]. 計(jì)算機(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é)點(diǎn)跨層感知的機(jī)會(huì)網(wǎng)絡(luò)高效低時(shí)延路由算法 [J]. 通信學(xué)報(bào), 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—),女,碩士,講師;任智(通信作者),男,教授。

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

時(shí)間: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