能量受限的多移動(dòng)設(shè)備無(wú)線充電路徑規(guī)劃方法

徐新黎,崔永婷,皇甫曉潔,陳 琛

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023) E-mail:xxl@zjut.edu.cn

1 引 言

無(wú)線傳感器網(wǎng)絡(luò)已經(jīng)被廣泛應(yīng)用于建筑結(jié)構(gòu)健康監(jiān)測(cè)、科學(xué)探索、環(huán)境監(jiān)測(cè)和目標(biāo)跟蹤等各個(gè)領(lǐng)域.目前大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)都是由電池供電,由于很多情況下不能及時(shí)更換電池,網(wǎng)絡(luò)的壽命受到極大的限制.為了延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期,不少能量采集的方法被提出來(lái),如從周圍環(huán)境中獲取太陽(yáng)能[1]、風(fēng)能[2]和振動(dòng)能量[3]等補(bǔ)充節(jié)點(diǎn)能量.然而,這些能量具有隨時(shí)間變化的性質(zhì),其實(shí)用性仍然非常有限.

近年來(lái)無(wú)線能量傳輸技術(shù)[4]取得重大突破,為解決無(wú)線傳感器網(wǎng)絡(luò)能量問(wèn)題提供了有效方案.利用無(wú)線能量傳輸技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)也稱可充電無(wú)線傳感器網(wǎng)絡(luò)(Rechargeable Wireless Sensor Networks,RWSNs),是指通過(guò)外部電源給節(jié)點(diǎn)無(wú)線供電的傳感器網(wǎng)絡(luò)[5-8].由于無(wú)線能量源的價(jià)格相對(duì)昂貴,大規(guī)模部署能量源為網(wǎng)絡(luò)提供持續(xù)的能量供給成本較高.因此,在保證節(jié)點(diǎn)充電服務(wù)質(zhì)量的前提下,最小化其整體充電成本,成為無(wú)線充電傳感器網(wǎng)絡(luò)發(fā)展與應(yīng)用的關(guān)鍵[5].

目前可充電無(wú)線傳感器網(wǎng)絡(luò)研究中主要是引入一臺(tái)移動(dòng)可充電設(shè)備為傳感器節(jié)點(diǎn)充電,使得網(wǎng)絡(luò)中節(jié)點(diǎn)不會(huì)因?yàn)殡娏亢谋M而死亡[6,7].通常,移動(dòng)充電設(shè)備周期性地訪問(wèn)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn),并且在每個(gè)節(jié)點(diǎn)周圍停留很短一段時(shí)間為節(jié)點(diǎn)無(wú)線充電.研究表明,小規(guī)模網(wǎng)絡(luò)中部署單個(gè)移動(dòng)充電設(shè)備進(jìn)行充電可以保持網(wǎng)絡(luò)壽命.但是,由于單個(gè)移動(dòng)充電設(shè)備在充電功率、移動(dòng)速度和整體能量上的限制,在大規(guī)模網(wǎng)絡(luò)中無(wú)法保證每個(gè)傳感器節(jié)點(diǎn)正常工作.針對(duì)上述問(wèn)題,已有研究者應(yīng)用多個(gè)移動(dòng)充電設(shè)備進(jìn)行充電規(guī)劃.文獻(xiàn)[8]針對(duì)多移動(dòng)充電設(shè)備提出一種協(xié)作充電方案,在一維場(chǎng)景下將一個(gè)移動(dòng)充電設(shè)備同時(shí)作為另一個(gè)移動(dòng)充電設(shè)備的維護(hù)來(lái)進(jìn)行能量接力,減少設(shè)備返回維護(hù)站的次數(shù),從而提升使用效率.其后續(xù)工作通過(guò)構(gòu)造最小權(quán)重哈密爾頓回路的方式拓寬至二維場(chǎng)景[9].但是文獻(xiàn)[8]和文獻(xiàn)[9]都沒(méi)有考慮總的成本問(wèn)題,且充電規(guī)劃方法復(fù)雜度較高.文獻(xiàn)[10]首次提出最小化移動(dòng)充電設(shè)備問(wèn)題(minimum mobile chargers problem,簡(jiǎn)稱 MMCP),在給定無(wú)線可充電傳感器網(wǎng)絡(luò)和MC 的參數(shù)前提下,確定最少移動(dòng)充電設(shè)備(MC)數(shù)量及其充電方案.后續(xù)工作證明了 MMCP 問(wèn)題是NP 問(wèn)題,并將MMCP 問(wèn)題轉(zhuǎn)換成 DVRP (distance-constrained vehicle routing problem) 問(wèn)題,再利用已有的DVRP解決方法給出解決MMCP的近似算法[11],但DVRP只是MMCP的子問(wèn)題[12].為此,文獻(xiàn)[12] 針對(duì)MMCP提出了一種貪心充電方案(GCS).但文獻(xiàn)[10]和文獻(xiàn)[11]都沒(méi)有考慮MC的旅行距離約束.

為保證網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都能持續(xù)工作,考慮MC的成本和旅行距離受限等因素,以最小化無(wú)線充電設(shè)備數(shù)量為目標(biāo),本文提出了一種多個(gè)移動(dòng)設(shè)備無(wú)線充電節(jié)點(diǎn)選擇和路徑規(guī)劃的方案.

2 多移動(dòng)充電設(shè)備無(wú)線充電調(diào)度模型分析

2.1 網(wǎng)絡(luò)模型

考慮一種多移動(dòng)充電設(shè)備的可充電無(wú)線傳感器網(wǎng)絡(luò),圖1為一般應(yīng)用場(chǎng)景模型[11].假設(shè)n個(gè)節(jié)點(diǎn)隨機(jī)分布在被監(jiān)測(cè)區(qū)域內(nèi),節(jié)點(diǎn)之間通過(guò)多跳路由將數(shù)據(jù)發(fā)送給基站.多個(gè)移動(dòng)充電設(shè)備從維護(hù)站出發(fā),遍歷待充電的節(jié)點(diǎn)集,依次為節(jié)點(diǎn)無(wú)線充電后回到維護(hù)站進(jìn)行修整、補(bǔ)充能量.圖1中黑色線段為移動(dòng)充電設(shè)備行走路徑,箭頭方向?yàn)槠湫羞M(jìn)方向.

圖1 多移動(dòng)充電設(shè)備可充電傳感器網(wǎng)絡(luò)模型Fig.1 Rechargeable wireless sensor network model for multi mobile charging devices

對(duì)無(wú)線傳感器和移動(dòng)充電設(shè)備做如下假設(shè):

1)節(jié)點(diǎn)具有唯一標(biāo)識(shí)符,且具有位置感知能力和一定的存儲(chǔ)能力;

2)節(jié)點(diǎn)位置固定,且裝有磁耦合線圈,能接收無(wú)線能量;

3)節(jié)點(diǎn)支持二級(jí)通信功率,且當(dāng)傳輸功率已知,節(jié)點(diǎn)可根據(jù)接收信號(hào)強(qiáng)度計(jì)算兩節(jié)點(diǎn)間距離；

4)網(wǎng)絡(luò)為對(duì)稱網(wǎng)絡(luò),假設(shè)w(i,j)為無(wú)線充電設(shè)備從節(jié)點(diǎn)N(i)運(yùn)行到節(jié)點(diǎn)N(j)花費(fèi)的時(shí)間,則w(i,j)=w(j,i);

5)移動(dòng)充電設(shè)備的電量有限,且行走和無(wú)線充電都需要耗能;

6)移動(dòng)充電設(shè)備循環(huán)移動(dòng),從維護(hù)站出發(fā),沿規(guī)劃的軌跡勻速運(yùn)行一周后回到維護(hù)站補(bǔ)充能量(更換電池或充電)為一個(gè)周期,且所有移動(dòng)充電設(shè)備的充電功率相同.

2.2 耗電模型

(1)

其中,w(i,j)為移動(dòng)充電設(shè)備從節(jié)點(diǎn)i行走到節(jié)點(diǎn)j所花費(fèi)的時(shí)間.

移動(dòng)充電設(shè)備m的一個(gè)完整充電周期τm為:

(2)

在t時(shí)刻,節(jié)點(diǎn)N(i)的耗電功率為pi(t),Cil為節(jié)點(diǎn)N(i)向節(jié)點(diǎn)N(l)發(fā)送數(shù)據(jù)時(shí)的功率參數(shù),CiB為節(jié)點(diǎn)N(i)向基站發(fā)送數(shù)據(jù)時(shí)的功率參數(shù),那么節(jié)點(diǎn)耗電功率為:

(3)

其中,Eelec為發(fā)送電路和接收電路能耗.

要使網(wǎng)絡(luò)持續(xù)運(yùn)行下去,必須滿足網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)電量在任意時(shí)刻不低于工作電量Emin,即:

(4)

其中,U為無(wú)線充電功率,M表示全部移動(dòng)充電設(shè)備的集合.若充電設(shè)備l對(duì)節(jié)點(diǎn)i充電,則dli為1,否則為0.

假設(shè)移動(dòng)充電設(shè)備m的能量容量為B,其行走的能耗功率為ηtsp,給節(jié)點(diǎn)無(wú)線充電時(shí)的能耗功率為ηc.那么,移動(dòng)充電設(shè)備m在整個(gè)路徑中的能耗都不低于B,即:

(5)

2.3 問(wèn)題描述

假設(shè)|M|個(gè)移動(dòng)充電設(shè)備從基站出發(fā),沿規(guī)劃的路徑運(yùn)行,并且以對(duì)經(jīng)過(guò)的節(jié)點(diǎn)充滿電為一個(gè)輪次.那么,對(duì)任意移動(dòng)充電設(shè)備m,其運(yùn)行時(shí)間滿足公式(1)和公式(2),任意時(shí)刻節(jié)點(diǎn)的最低電量滿足公式(4).在穩(wěn)定階段,節(jié)點(diǎn)的耗電量等于節(jié)點(diǎn)通過(guò)無(wú)線充電補(bǔ)充的能量,即:

(6)

綜上,多移動(dòng)充電設(shè)備充電調(diào)度問(wèn)題可以描述為:

OPT-I:minN(i).E≥Emin

3 多移動(dòng)充電設(shè)備無(wú)線充電調(diào)度算法設(shè)計(jì)

3.1 問(wèn)題分析

很多研究已經(jīng)證明單移動(dòng)充電設(shè)備充電規(guī)劃算法在網(wǎng)絡(luò)規(guī)模較小時(shí),能夠使得網(wǎng)絡(luò)持續(xù)工作而其節(jié)點(diǎn)不因?yàn)楹碾娺^(guò)多而死亡.但是隨著網(wǎng)絡(luò)規(guī)模的增大——被監(jiān)測(cè)區(qū)域增大或者網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)增多,算法的適應(yīng)性明顯下降,不能保證網(wǎng)絡(luò)持續(xù)運(yùn)行.由此可見,單移動(dòng)充電設(shè)備充電路徑規(guī)劃算法對(duì)網(wǎng)絡(luò)的壽命和節(jié)點(diǎn)的個(gè)數(shù)、網(wǎng)絡(luò)的大小會(huì)有較強(qiáng)的限制,導(dǎo)致在復(fù)雜場(chǎng)景中的應(yīng)用遇到瓶頸.因此,為了能夠適應(yīng)大規(guī)模網(wǎng)絡(luò)的應(yīng)用,增加移動(dòng)充電設(shè)備個(gè)數(shù)勢(shì)在必行.隨著移動(dòng)充電設(shè)備個(gè)數(shù)的增加,各種新的問(wèn)題也接踵而來(lái).例如,如何為每個(gè)移動(dòng)充電設(shè)備選擇合適的節(jié)點(diǎn)子集進(jìn)行充電,如何規(guī)劃每個(gè)移動(dòng)充電設(shè)備的充電路徑等.

針對(duì)多移動(dòng)充電設(shè)備,本文提出了一種充電節(jié)點(diǎn)選擇和路徑規(guī)劃方案,使其能夠滿足大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的需求,并且在保證大規(guī)模網(wǎng)絡(luò)持續(xù)運(yùn)行的前提下,使得移動(dòng)充電設(shè)備數(shù)最小.

3.2 充電路徑規(guī)劃

多移動(dòng)設(shè)備充電路徑規(guī)劃算法的基本思路是,首先利用集中式算法確定移動(dòng)充電設(shè)備數(shù)和每個(gè)移動(dòng)充電設(shè)備需要覆蓋的傳感器節(jié)點(diǎn)數(shù),然后在運(yùn)行過(guò)程中分布式動(dòng)態(tài)規(guī)劃每個(gè)移動(dòng)充電設(shè)備的充電節(jié)點(diǎn)子集和充電路徑.

由文獻(xiàn)[13]可知,無(wú)線充電設(shè)備遍歷路徑構(gòu)成最短Hamilton回路.采用實(shí)時(shí)性和準(zhǔn)確性都較高的彈性網(wǎng)絡(luò)算法[15,16]來(lái)構(gòu)成Hamilton回路比較合理.求解Hamilton回路是一個(gè)旅行商問(wèn)題(Traveling Salesman Problem,TSP)[15],是指給定N個(gè)城市的坐標(biāo),每個(gè)城市都被遍歷且僅被遍歷一次.彈性網(wǎng)絡(luò)的思想是,將一條TSP路徑看成是線圈上的點(diǎn)到二維平面上點(diǎn)的映射,那么,平面上每個(gè)點(diǎn)都能在線圈上找到一個(gè)或多個(gè)映射.這樣,整個(gè)問(wèn)題就變成了在特殊情況下,尋找?guī)缀慰臻g映射最佳鄰居節(jié)點(diǎn)的問(wèn)題了.彈性網(wǎng)絡(luò)算法就是一個(gè)迭代計(jì)算城市所在平面多點(diǎn)位置的過(guò)程.一開始的時(shí)候,線圈上的點(diǎn)組成一個(gè)很小的圓,并且位于城市所在平面的正中間.接著,線圈逐漸不規(guī)則擴(kuò)大,每個(gè)點(diǎn)都朝著某個(gè)特定的城市移動(dòng).

線圈上的每個(gè)點(diǎn)都受到兩個(gè)力的作用.一個(gè)是來(lái)自節(jié)點(diǎn)的引力,這個(gè)力使得點(diǎn)朝著距離自己最近的城市靠近;第二個(gè)是來(lái)自鄰居點(diǎn)的張力,使得它向鄰居節(jié)點(diǎn)靠近,從而使得整個(gè)線圈長(zhǎng)度最短.這樣,每個(gè)城市都與線圈上一個(gè)點(diǎn)的集合關(guān)聯(lián)起來(lái).城市與節(jié)點(diǎn)集合關(guān)聯(lián)的緊密程度由城市與節(jié)點(diǎn)之間的距離決定,并且這種關(guān)聯(lián)程度隨著算法的迭代而變化.一開始,每個(gè)城市對(duì)點(diǎn)的作用都是相同的,隨著算法的迭代,距離點(diǎn)較遠(yuǎn)的城市的作用力逐漸減小,距離點(diǎn)較近的點(diǎn)的作用力逐漸增強(qiáng).這種逐漸增強(qiáng)的特性收到長(zhǎng)度參數(shù)K的控制.彈性網(wǎng)絡(luò)的迭代公式由下式表示:

(7)

其中,xi為點(diǎn)i的坐標(biāo)向量,yj為點(diǎn)j的坐標(biāo)向量,Δyj點(diǎn)j的偏移量.α和β為常量,分別表示點(diǎn)收到城市和鄰居點(diǎn)的作用力強(qiáng)度.系數(shù)ωij表示城市i對(duì)點(diǎn)j的影響,通常是城市i和點(diǎn)j之間距離|xi-yj|以及K的函數(shù),這個(gè)函數(shù)可以被標(biāo)準(zhǔn)化表示為:

ωij=φ(|xi-yj|,K)/∑kφ(|xi-yk|,K)

(8)

其中,φ(d,K)是關(guān)于d的正向有界函數(shù),當(dāng)d>K時(shí)趨近于0.

這里傳感器網(wǎng)絡(luò)節(jié)點(diǎn)N(i)的坐標(biāo)表示為(N(i).x,N(i).y),彈性網(wǎng)絡(luò)線圈上的點(diǎn)的坐標(biāo)表示為(Y(i).x,Y(i).y).φ(d,K)取高斯函數(shù),則關(guān)于彈性網(wǎng)絡(luò)應(yīng)用與本文無(wú)線傳感器網(wǎng)絡(luò)路徑規(guī)劃的迭代公式為:

(9)

dis(X(i),X(j))=[N(i).x-Y(j).x,N(i).y-Y(j).y]

(10)

ωij=φ(|dis(N(i),Y(j))|,K)
/∑kφ(|dis(N(i),Y(j))|,K)

(11)

φ(d,K)=e-d2/2K2

(12)

其中公式(10)中dis(X(i),X(j))表示矩陣.

基于彈性網(wǎng)絡(luò)算法的充電路徑規(guī)劃具體過(guò)程為:

步驟1.收集各節(jié)點(diǎn)的ID、位置信息和維護(hù)站的位置信息并傳遞給基站;

步驟2.運(yùn)行彈性網(wǎng)絡(luò)算法求得維護(hù)站和全部傳感器節(jié)點(diǎn)之間的TSP回路;

步驟3.調(diào)整回路起始位置為維護(hù)站,獲得充電路徑.

通過(guò)彈性網(wǎng)絡(luò)算法在全部傳感器節(jié)點(diǎn)和維護(hù)站之間形成一條Hamilton回路.移動(dòng)充電設(shè)備從維護(hù)站出發(fā),沿著之前規(guī)劃好的路徑依次遍歷每個(gè)節(jié)點(diǎn),并給節(jié)點(diǎn)充電,最后回到維護(hù)站進(jìn)行修整.盡管彈性網(wǎng)絡(luò)算法實(shí)時(shí)性好、準(zhǔn)確性高,但是由于不同節(jié)點(diǎn)在不同時(shí)刻的能量消耗不同,僅僅是根據(jù)位置信息每輪遍歷全部節(jié)點(diǎn)不能滿足不同節(jié)點(diǎn)對(duì)能量補(bǔ)充的不同需求.因此,本文根據(jù)不同節(jié)點(diǎn)對(duì)能量的不同需求,選擇需求最大的前k個(gè)節(jié)點(diǎn)進(jìn)行無(wú)線充電.

每當(dāng)節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)時(shí),將剩余自身剩余能量和路由表加在報(bào)文頭中發(fā)送給基站,基站保留每個(gè)節(jié)點(diǎn)最近剩余能量和路由表作為路徑調(diào)度的輸入.當(dāng)移動(dòng)充電設(shè)備位于維護(hù)站時(shí)(開始出發(fā)或者運(yùn)行一周后回到維護(hù)站),綜合考慮每個(gè)節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)的耗電功率以及節(jié)點(diǎn)與維護(hù)站的距離,計(jì)算出其路徑權(quán)值權(quán)值,并按該權(quán)值升序排列,選擇路徑權(quán)值最大的前k個(gè)節(jié)點(diǎn)進(jìn)行路徑規(guī)劃,移動(dòng)充電設(shè)備依次遍歷這k個(gè)節(jié)點(diǎn)而不是全網(wǎng)節(jié)點(diǎn).

剩余存活時(shí)間預(yù)估公式為:

(13)

其中,cost(i)為節(jié)點(diǎn)N(i)的路徑權(quán)值,dij為二值參數(shù),若節(jié)點(diǎn)N(j)為節(jié)點(diǎn)N(i)的下一跳路由,則dij為1,否則為0.在公式(13)中,由于節(jié)點(diǎn)剩余能量與節(jié)點(diǎn)剩余存活時(shí)間成正比,分子部分為節(jié)點(diǎn)剩余能量;由于節(jié)點(diǎn)發(fā)送能耗與距離的二次方成正比,與節(jié)點(diǎn)剩余存活時(shí)間成反比,分母部分第一項(xiàng)為節(jié)點(diǎn)發(fā)送能耗的預(yù)估值;由于節(jié)點(diǎn)接收能耗與距離成正比,分母第二項(xiàng)為節(jié)點(diǎn)接收能耗的預(yù)估值.

下面給出algorithm算法以確定移動(dòng)充電設(shè)備總數(shù)m=|M|和每個(gè)移動(dòng)充電設(shè)備需要覆蓋的傳感器節(jié)點(diǎn)個(gè)數(shù)k.algorithm算法的具體步驟是:

步驟1.輸入網(wǎng)絡(luò)中n個(gè)節(jié)點(diǎn)的ID和位置坐標(biāo),初始化m=1;

步驟2.初始化k=1;

步驟3.枚舉m個(gè)移動(dòng)充電設(shè)備,判斷其是否位于維護(hù)站(基站),若是,執(zhí)行步驟4,否則,執(zhí)行步驟5;

步驟4.將網(wǎng)絡(luò)中所有節(jié)點(diǎn)按照路徑權(quán)重升序排序,選取前k個(gè)節(jié)點(diǎn)利用彈性網(wǎng)絡(luò)規(guī)劃充電路徑,并將這些節(jié)點(diǎn)標(biāo)記為已經(jīng)被規(guī)劃的節(jié)點(diǎn).若節(jié)點(diǎn)為未被規(guī)劃節(jié)點(diǎn),則其路徑權(quán)重預(yù)估公式為公式(11)相同,否則應(yīng)加上懲罰系數(shù)f;

步驟5.移動(dòng)充電設(shè)備遍歷路徑上的每個(gè)節(jié)點(diǎn),并對(duì)其進(jìn)行無(wú)線充電;

步驟6.判斷移動(dòng)充電設(shè)備電量是否小于0,若是,則執(zhí)行步驟7.否則,判斷網(wǎng)絡(luò)是否能持續(xù)運(yùn)行,若是,則輸出m值和k值,算法結(jié)束;否則,執(zhí)行步驟7;

步驟7.判斷k是否等于傳感器節(jié)點(diǎn)個(gè)數(shù)n,若是,則m值加1,執(zhí)行步驟2;否則,增加k值,執(zhí)行步驟3;

這里algorithm算法是模擬網(wǎng)絡(luò)的運(yùn)行,此時(shí)移動(dòng)充電設(shè)備并未開始行走充電.另外,algorithm算法中節(jié)點(diǎn)耗電功率根據(jù)下式預(yù)估:

(14)

在確定了移動(dòng)充電設(shè)備個(gè)數(shù)m和每個(gè)移動(dòng)充電設(shè)備需要充電的節(jié)點(diǎn)個(gè)數(shù)k值后,移動(dòng)充電設(shè)備開始運(yùn)行,其軌跡和覆蓋節(jié)點(diǎn)與algorithm算法步驟3至步驟5相似,只是節(jié)點(diǎn)的耗電功率取實(shí)際的耗電功率.

下面分析algorithm算法的時(shí)間復(fù)雜度.在algorithm算法中,主要時(shí)間復(fù)雜度仍舊來(lái)自對(duì)節(jié)點(diǎn)權(quán)重值進(jìn)行排序和每個(gè)移動(dòng)充電設(shè)備路徑規(guī)劃的時(shí)候運(yùn)行彈性網(wǎng)絡(luò)算法.另外,由于網(wǎng)絡(luò)中只有一個(gè)維護(hù)站,其覆蓋規(guī)模決定了移動(dòng)充電設(shè)備的個(gè)數(shù)相對(duì)于節(jié)點(diǎn)個(gè)數(shù)來(lái)說(shuō)是一個(gè)比較小的數(shù)量級(jí),因此algorithm算法中對(duì)m值的遍歷實(shí)際為常數(shù)時(shí)間復(fù)雜度O(1).而由于本文并未給出對(duì)每個(gè)節(jié)點(diǎn)子集包含節(jié)點(diǎn)個(gè)數(shù)k值的理論推導(dǎo),因此對(duì)k的遍歷時(shí)間復(fù)雜度為O(n).因此,algorithm算法的時(shí)間復(fù)雜度為O(1)×O(n)×(O(nlogn)+O(n3))=O(n4).

在上述過(guò)程中,只剩下一個(gè)問(wèn)題還沒(méi)有被確定,即如何判斷網(wǎng)絡(luò)是否能持續(xù)運(yùn)行.文獻(xiàn)[14]定義滿足以下兩個(gè)條件的網(wǎng)絡(luò)為可以持續(xù)運(yùn)行的網(wǎng)絡(luò):

對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn),在無(wú)線充電設(shè)備運(yùn)行周期開始和周期結(jié)束時(shí),都有相同的能量;

對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn),在無(wú)線充電的整個(gè)周期內(nèi),其能量都不低于最低工作能量.

由于,文獻(xiàn)[14]是先將整個(gè)網(wǎng)絡(luò)劃分區(qū)域,然后給每個(gè)區(qū)域分配一臺(tái)無(wú)線充電設(shè)備進(jìn)行供電,這樣,每臺(tái)無(wú)線充電設(shè)備的充電路徑一經(jīng)確定就不再改變.這樣做的好處在于計(jì)算簡(jiǎn)便,而其不足之處也顯而易見,就是不能適應(yīng)實(shí)時(shí)變化的節(jié)點(diǎn)能耗.為了具有更好的實(shí)時(shí)性,本文采用按需降級(jí)服務(wù)策略,每個(gè)周期重新規(guī)劃移動(dòng)充電設(shè)備無(wú)線充電路徑.這樣,移動(dòng)充電設(shè)備的充電軌跡不固定,其運(yùn)行時(shí)間也就不確定,那么對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō),其電量變化就不會(huì)呈現(xiàn)嚴(yán)格的周期性.那么,上述判斷網(wǎng)絡(luò)是否可持續(xù)運(yùn)行的兩個(gè)條件中,條件(2)仍舊適用,但是條件(1)就不適用于本文算法了.為此,我們重新分析節(jié)點(diǎn)能耗.對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)來(lái)說(shuō),若網(wǎng)絡(luò)可以持續(xù)運(yùn)行,則其經(jīng)過(guò)無(wú)線充電獲取的電量必然大于等于其消耗的能量,且在每一時(shí)刻,網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的電量不低于最低工作電量,即網(wǎng)絡(luò)滿足:

(15)

(16)

若一個(gè)無(wú)線傳感器網(wǎng)絡(luò)滿足以上兩個(gè)條件,則這個(gè)網(wǎng)絡(luò)能夠持續(xù)運(yùn)行.

3.3 算法流程

多移動(dòng)充電設(shè)備無(wú)線充電規(guī)劃算法的一般過(guò)程如圖2所示.

圖2 多移動(dòng)充電設(shè)備無(wú)線充電調(diào)度算法流程圖Fig.2 Flow chart of wireless charging scheduling algorithm for multi mobile charging devices

首先收集網(wǎng)絡(luò)中節(jié)點(diǎn)的ID和位置信息,然后運(yùn)行algorithm算法確定需要的移動(dòng)充電設(shè)備數(shù)m和對(duì)應(yīng)的k值,接著每個(gè)移動(dòng)充電設(shè)備判斷自己當(dāng)前位置是否為維護(hù)站,如果不在維護(hù)站,則給當(dāng)前節(jié)點(diǎn)充滿電,標(biāo)記當(dāng)前節(jié)點(diǎn)為未被規(guī)劃節(jié)點(diǎn),并駛向下一個(gè)節(jié)點(diǎn).否則就要進(jìn)行充電路徑規(guī)劃.具體為,首先,按路徑權(quán)重將網(wǎng)絡(luò)中所有節(jié)點(diǎn)升序排序;其次,選排序后路徑權(quán)重值最小的前k個(gè)節(jié)點(diǎn),運(yùn)行基于彈性網(wǎng)絡(luò)的路徑規(guī)劃算法,獲得無(wú)線充電回路,并將充電路徑所要經(jīng)過(guò)的節(jié)點(diǎn)標(biāo)記為已經(jīng)被規(guī)劃節(jié)點(diǎn);最后依次訪問(wèn)k個(gè)點(diǎn)并給節(jié)點(diǎn)充滿電.

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 場(chǎng)景和參數(shù)設(shè)置

實(shí)驗(yàn)仿真場(chǎng)景如圖3所示.200個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在300m×300m的被監(jiān)測(cè)區(qū)域內(nèi),基站(維護(hù)站)位于區(qū)域中間.

圖3 實(shí)驗(yàn)仿真場(chǎng)景Fig.3 Experimental simulation scenario

實(shí)驗(yàn)參數(shù)設(shè)置如下:傳感器節(jié)點(diǎn)最大電量Emax=0.2J,傳感器節(jié)點(diǎn)最低工作電量Emin=0.05J,電路能耗Eelec=50nJ/bit,自由空間模型放大倍數(shù)εfs=10pJ/bit/m2,多路徑衰減模型放大倍數(shù)εmp=0.0013pJ/bit/m4,數(shù)據(jù)融合能耗EDA=5nJ/bit,移動(dòng)充電設(shè)備運(yùn)行速度V=5m/s,移動(dòng)充電設(shè)備電量B=500kJ,移動(dòng)充電設(shè)備行走耗電功率ηtsp=10w,移動(dòng)充電設(shè)備無(wú)線充電能耗功率ηc=10w,無(wú)線充電功率U=0.02W,無(wú)線充電設(shè)備修整時(shí)間τvac=300s,傳感器節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)速率Ri為1～400bit/s的隨機(jī)數(shù),懲罰系數(shù)f=100000.彈性網(wǎng)絡(luò)算法參數(shù)α=0.2,β=2.0,K=0.2.

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)采用MATLAB進(jìn)行仿真,模擬實(shí)現(xiàn)了基于彈性網(wǎng)絡(luò)的多移動(dòng)充電設(shè)備充電路徑規(guī)劃算法.運(yùn)行algorithm算法得出,在300m×300m、200個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)中,最少使用5臺(tái)移動(dòng)充電設(shè)備、k取5的時(shí)候,網(wǎng)絡(luò)可持續(xù)運(yùn)行.

圖4 網(wǎng)絡(luò)總能量隨時(shí)間變化趨勢(shì)Fig.4 Change trend of total energy with time in network

為了驗(yàn)證本文提出的算法是否能保證網(wǎng)絡(luò)持續(xù)運(yùn)行,給出了網(wǎng)絡(luò)總能量隨時(shí)間變化的趨勢(shì),如圖4所示.

圖4中,橫坐標(biāo)為網(wǎng)絡(luò)運(yùn)行時(shí)間,單位為秒;縱坐標(biāo)為網(wǎng)絡(luò)總能量,單位為J.網(wǎng)絡(luò)的總能量最初為40J,剛開始出現(xiàn)較強(qiáng)烈的振動(dòng),隨著時(shí)間的推移,振動(dòng)幅度逐漸減弱,呈現(xiàn)振動(dòng)平穩(wěn)趨勢(shì),穩(wěn)定在26J左右.這說(shuō)明整個(gè)無(wú)線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)無(wú)線充電補(bǔ)充的能量和存儲(chǔ)轉(zhuǎn)發(fā)消耗的能量已經(jīng)保持動(dòng)態(tài)平衡.也就是說(shuō),網(wǎng)絡(luò)已經(jīng)持續(xù)運(yùn)作.

然而,網(wǎng)絡(luò)整體能量保持不變,并不能代表沒(méi)有個(gè)別節(jié)點(diǎn)的能量低于工作能量.為此,找出每個(gè)單位時(shí)間內(nèi)網(wǎng)絡(luò)中能量最小的節(jié)點(diǎn),結(jié)果如圖5所示.

圖5 網(wǎng)絡(luò)中最小能量隨時(shí)間變化趨勢(shì)Fig.5 Change of minimum energy with time in network

圖5中,橫坐標(biāo)是網(wǎng)絡(luò)運(yùn)行時(shí)間,單位是秒;縱坐標(biāo)表示不同時(shí)刻網(wǎng)絡(luò)中最小的能量.由圖5可知,最初網(wǎng)絡(luò)中最小能量是0.2J,為節(jié)點(diǎn)的初始能量.隨著時(shí)間的推移,最小能量先是振蕩減小,之后振蕩并趨于平穩(wěn),保持在0.03J附近.整個(gè)過(guò)程中,最小能量都位于最低工作能量之上,這說(shuō)明,整個(gè)網(wǎng)路運(yùn)行過(guò)程中,并沒(méi)有節(jié)點(diǎn)由于能量過(guò)低而死亡.這是因?yàn)?節(jié)點(diǎn)通過(guò)無(wú)線充電補(bǔ)充的能量和其耗電量保持動(dòng)態(tài)平衡.

圖4表明整個(gè)網(wǎng)絡(luò)的總能量趨于穩(wěn)定,圖5的實(shí)驗(yàn)結(jié)果表明網(wǎng)絡(luò)中所有的節(jié)點(diǎn)在任意時(shí)刻都有不低于最低工作電量的能量.但是,以上兩張圖都是呈現(xiàn)振蕩狀態(tài),還沒(méi)有特別明顯的平穩(wěn)趨勢(shì).為此,我們對(duì)實(shí)驗(yàn)結(jié)果做了平均值處理,以便更直觀其穩(wěn)定趨勢(shì).

圖6 網(wǎng)絡(luò)總能量平均值變化趨勢(shì)Fig.6 Change trend of average total energy average in network

圖6為對(duì)總能量的平均化處理.在圖6中,橫坐標(biāo)為網(wǎng)絡(luò)運(yùn)行時(shí)間,單位為s;縱坐標(biāo)為網(wǎng)絡(luò)中總能量的平均處理后的值,單位為J;曲線表現(xiàn)了網(wǎng)絡(luò)總能量隨時(shí)間變化的趨勢(shì).所謂平均化處理,即在圖6中,曲線上點(diǎn)的值為當(dāng)前時(shí)間開始,向前追溯10000s取得的平均值.這樣做的好處是,去除圖4中由于曲線振動(dòng)而帶來(lái)的曲線走向不確定性.從圖6可知,網(wǎng)絡(luò)總能量迅速穩(wěn)定在26J左右,并且隨著網(wǎng)絡(luò)運(yùn)行時(shí)間的推移,一直保持平穩(wěn).

同樣網(wǎng)絡(luò)中最小能量也做了平均化處理,結(jié)果如圖7所示.在圖7中,橫坐標(biāo)為網(wǎng)絡(luò)運(yùn)行時(shí)間單位為秒;縱坐標(biāo)為網(wǎng)絡(luò)中最小能量的平均化處理值,單位為J;曲線展現(xiàn)了網(wǎng)絡(luò)中最小能量隨網(wǎng)絡(luò)運(yùn)行時(shí)間的變化趨勢(shì).由圖7可知,網(wǎng)絡(luò)最小能量迅速下降后保持穩(wěn)定.且其穩(wěn)定值接近0.03J,高于節(jié)點(diǎn)最低工作電量.由于圖7中曲線并未出現(xiàn)震蕩,因此,我們有充分的理由說(shuō)明,多移動(dòng)充電設(shè)備無(wú)線充電路徑調(diào)度算法能夠及時(shí)給網(wǎng)絡(luò)補(bǔ)充電量,使網(wǎng)絡(luò)中任意節(jié)點(diǎn)的能量在任意時(shí)刻都不低于最低工作電量.

圖7 網(wǎng)絡(luò)最小能量平均值變化趨勢(shì)Fig.7 Change trend of average minimum energy average in network

圖8給出了網(wǎng)絡(luò)運(yùn)行1000s的時(shí),5臺(tái)移動(dòng)充電設(shè)備的軌跡.圖8中,空心方框表示移動(dòng)充電設(shè)備,空心圓點(diǎn)表示傳感器節(jié)點(diǎn),節(jié)點(diǎn)之間的不同實(shí)線或虛線表示不同的運(yùn)行軌跡.圖8可知,多移動(dòng)充電設(shè)備無(wú)線充電路徑規(guī)劃算法求得的路徑,并沒(méi)有分區(qū)效果.這是因?yàn)樵撍惴ㄊ蔷C合考慮節(jié)點(diǎn)的剩余電量、耗電功率和與基站的距離選擇充電節(jié)點(diǎn),并不是簡(jiǎn)單的分區(qū).另外,一些耗電量過(guò)大的節(jié)點(diǎn)會(huì)在同一循環(huán)中受多個(gè)移動(dòng)充電設(shè)備充電(比如1000s時(shí)第183號(hào)節(jié)點(diǎn)同時(shí)在第一和第三臺(tái)移動(dòng)充電設(shè)備的規(guī)劃路徑中,第190號(hào)節(jié)點(diǎn)同時(shí)出現(xiàn)在第一和第四臺(tái)移動(dòng)充電設(shè)備的規(guī)劃路徑中),這一點(diǎn)在分區(qū)特別是固定分區(qū)的網(wǎng)絡(luò)中是不能做到的.

圖8 移動(dòng)充電設(shè)備路徑規(guī)劃圖Fig.8 Planning of mobile charging device path

表1給出了不同時(shí)刻,移動(dòng)充電設(shè)備的路徑總長(zhǎng)度、移動(dòng)消耗能量、充電消耗能量和移動(dòng)充電設(shè)備剩余能量.在表1中,縱向?qū)傩詾榫W(wǎng)絡(luò)運(yùn)行時(shí)間,單位為秒;橫向?qū)傩詾橐苿?dòng)充電設(shè)備編號(hào).表格中數(shù)據(jù)為一四元組,依次為移動(dòng)充電設(shè)備路徑總長(zhǎng)度、移動(dòng)充電設(shè)備從上一個(gè)節(jié)點(diǎn)運(yùn)行到本次節(jié)點(diǎn)行走能耗、移動(dòng)充電設(shè)備給上一個(gè)節(jié)點(diǎn)無(wú)線充電能耗和到達(dá)本次充電節(jié)點(diǎn)時(shí)移動(dòng)充電設(shè)備的剩余能量.其中,路徑長(zhǎng)度單位為米,行走能耗、無(wú)線充電能耗和剩余能量單位為焦耳.

表1 移動(dòng)充電設(shè)備能耗表
Table 1 Energy consumption of mobile charging devices

運(yùn)行時(shí)間充電設(shè)備1充電設(shè)備2充電設(shè)備3充電設(shè)備4充電設(shè)備520s[1218.1,388.58,0,4997857][873.7,251.5,0,49985427][730.0,251.5,0,4998543][830.0,251.5,0,4998543][569.7,251.5,0,4998543]200s[1218.1,267.1,24.4,4991638][873.7,566.6,4.2,4991677][730.0,181.9,0,4991499][830.0,274.6,0,4990500][849.6,251.5,2.9,4998542]400s[702.2,207.6,1.5,4997304][730.0,246.8,5.1,4993871][1002.3,253.9,4.2,4992527][829.9,567.0,3.2,4992073][849.6,289.9,0,4990303]600s[582.6,364.4,4.7,4997183][873.7,556.6,6.0,4991677][830.0,258.9,2.3,4995108][730.0,246.8,3.8,4993871][1218.1,267.1,28.8,4991638]800s[873.7,178.3,6.7,4996213][730.0,488.5,4.1,4995900][830.0,226.6,2.5,4996602][1218.1,558.3,30.9,4994865][640.0,251.5,1.2,4998542]

由表1可知,移動(dòng)充電設(shè)備的行走能耗遠(yuǎn)大于無(wú)線充電能耗,因此,其主要耗電來(lái)自行走能量消耗.再看移動(dòng)充電設(shè)備的充電路徑長(zhǎng)度,均在500米到1300米之間,且移動(dòng)充電設(shè)備的剩余能量足夠其從維護(hù)站出發(fā),遍歷每個(gè)節(jié)點(diǎn)后重新回到維護(hù)站.由此說(shuō)明本文提出的容量受限的多移動(dòng)設(shè)備充電路徑調(diào)度算法符合移動(dòng)充電設(shè)備的能量約束.

為了驗(yàn)證本文所提算法能夠減少移動(dòng)充電設(shè)備數(shù)量,對(duì)所需移動(dòng)充電設(shè)備數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)增多的情況進(jìn)行了仿真,并與文獻(xiàn)[11]提出的Enhanced MinMCP算法做了對(duì)比,結(jié)果如圖9所示.圖9的仿真參數(shù)為[11]:被監(jiān)測(cè)區(qū)域大小為5km×5km,傳感器節(jié)點(diǎn)最大電量Emax=10.8kJ,傳感器節(jié)點(diǎn)最低工作電量Emin=0.05Emax=540J,所有節(jié)點(diǎn)耗電功率相同為200mW,移動(dòng)充電設(shè)備運(yùn)行速度V=5m/s,移動(dòng)充電設(shè)備電量B=500kJ,移動(dòng)充電設(shè)備行走耗電功率ηp=100w,移動(dòng)充電設(shè)備無(wú)線充電能耗功率ηc=110w,無(wú)線充電功率U=5W,無(wú)線充電設(shè)備休整時(shí)間τvac=7200s,懲罰系數(shù)f=100000.彈性網(wǎng)絡(luò)算法參數(shù)α=0.2,β=2.0,K=0.2.

在圖9中,橫坐標(biāo)為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù),縱坐標(biāo)為維持網(wǎng)絡(luò)持續(xù)運(yùn)行所需的移動(dòng)充電設(shè)備數(shù).由圖9可知,在被檢測(cè)區(qū)域大小不變的 情況下,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多,兩種算法所需的移動(dòng)充電設(shè)備數(shù)量都增大,但是本文算法所需的移動(dòng)充電設(shè)備數(shù)量始終少于或等于Enhanced MinMCP算法所需的移動(dòng)充電設(shè)備數(shù).這是因?yàn)?在被檢測(cè)區(qū)域大小不變的情況下,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多,移動(dòng)充電設(shè)備需要為更多的節(jié)點(diǎn)充電,因此需要的移動(dòng)充電設(shè)備數(shù)量增多.另外,Enhanced MinMCP算法需要固定分區(qū),并不能夠按需靈活調(diào)整移動(dòng)充電設(shè)備覆蓋的節(jié)點(diǎn),而本文所提算法不分區(qū),完全根據(jù)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的需求進(jìn)行路徑規(guī)劃,能夠充分利用移動(dòng)充電設(shè)備,減少移動(dòng)充電設(shè)備數(shù).

圖9 兩種算法移動(dòng)充電設(shè)備數(shù)比較Fig.9 Comparison of two algorithms for mobile charging devices

5 總 結(jié)

本文針對(duì)移動(dòng)充電設(shè)備運(yùn)行軌跡不受限的場(chǎng)景提出了一種多移動(dòng)充電設(shè)備無(wú)線充電調(diào)度方法.每個(gè)移動(dòng)充電設(shè)備從維護(hù)站出發(fā),根據(jù)事先規(guī)劃的路徑遍歷子集中的每個(gè)節(jié)點(diǎn),最后回到基站進(jìn)行修整.考慮移動(dòng)充電設(shè)備能量有限,每個(gè)移動(dòng)充電設(shè)備都選擇網(wǎng)絡(luò)中未被規(guī)劃的路徑權(quán)重值最小的前k個(gè)節(jié)點(diǎn)進(jìn)行充電路徑規(guī)劃.先用集中式算法確定移動(dòng)充電設(shè)備數(shù)和每臺(tái)移動(dòng)充電設(shè)備需要充電的節(jié)點(diǎn)數(shù),然后每輪都用彈性網(wǎng)絡(luò)規(guī)劃路徑.仿真結(jié)果證明,提出的方法能夠在保證網(wǎng)絡(luò)持續(xù)運(yùn)行的前提下,減少了所需移動(dòng)設(shè)備數(shù),且對(duì)不同節(jié)點(diǎn)能耗的非均勻無(wú)線傳感器網(wǎng)絡(luò)有較好的適應(yīng)性.另外,在針對(duì)節(jié)點(diǎn)能耗不均衡的情況下,可以采用單獨(dú)設(shè)備對(duì)高能耗節(jié)點(diǎn)進(jìn)行充電,延長(zhǎng)網(wǎng)絡(luò)壽命.

[1] Jiang X,Polastre J,Culler D.Perpetual environmentally powered sensor networks[C].International Symposium on Information,Processing in Sensor Networks,DBLP,2005:463-468.

[2] Park C,Chou P H.Ambimax.Autonomous energy harvesting platform for multi-supply wireless sensor nodes[C].3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks,IEEE,2006,1:168-177.

[3] Kulah H,Najafi K.Energy scavenging from low-frequency vibrations by using frequency up-conversion for wireless sensor applica

tions[J].IEEE Sensors Journal,2008,8(3):261-268.

[4] Fu Ling-kun.Research on energy optimization in wireless rechargeable sensor network-s[D].Hangzhou:Zhejiang University,2015.

[5] He S,Chen J,Jiang F,et al.Energy provisioning in wireless rechargeable sensor networks[J].IEEE Transactions on Mobile Computing,2013,12(10):1931-1942.

[6] Dai H,Wu X,Xu L,et al.Practical scheduling for stochastic event capture in wireless rechargeable sensor networks[C].IEEE Wireless Communications and Networking Conference(WCNC),IEEE,2013:986-991.

[7] Dai H,Xu L,Wu X,et al.Impact of mobility on energy provisioning in wireless rechargeable sensor networks[C].IEEE Wireless Communications and Networking Conference(WCNC),IEEE,2013:962-967.

[8] Zhang S,Wu J,Lu S.Collaborative mobile charging for sensor networks[C].IEEE 9th International Conference on Mobile Adhoc and Sensor Systems (MASS),IEEE,2012:84-92.

[9] Zhang S,Wu J,Lu S.Collaborative mobile charging[J].IEEE Transactions on Computers,2015,3(64):654-667.

[10] Dai H,Wu X,Xu L,et al.Using minimum mobile chargers to keep large-scale wireless rechargeable sensor networks running forever[C].22nd International Conference on Computer Communication and Networks(ICCCN),IEEE,2013:1-7.

[11] Dai H,Wu X,Chen G,et al.Minimizing the number of mobile chargers for large-scale wireless rechargeable sensor networks [J].Computer Communications,2014,46(6):54-65.

[12] Hu C,Wang Y.Minimizing the number of mobile chargers in a large-scale wireless rechargeable sensor network[C].IEEE Wireless Communications and Networking Conference(WCNC),IEEE,2015:1297-1302.

[13] Hang Jiang-hong,Ding Xu,Shi Lei,et al.Research in the time-varying charging and dynamic data routing strategy for rechargeable wireless sensor networks[J].Journal on Communications,2012,33(12):1-10.

[14] Shi Y,Xie L,Hou Y T,et al.On renewable sensor networks with wireless energy transfer[C].Proceedings IEEE International Conference on Computer Communications(INFOCOM),IEEE,2011,2(3):1350-1358.

[15] Durbin R,Willshaw D.An analogue approach to the travelling salesman problem using an elastic net method[J].Nature,1987,326(6114):689-691.

[16] Yi J,Yang G,Zhang Z,et al.An improved elastic net method for traveling salesman problem[J].Neurocomputing,2009,72(4):1329-1335.

[17] Flood M M.The traveling-salesman problem[J].Operations Research,1956,4(1):61-75.

附中文參考文獻(xiàn)：

[4] 傅凌焜.可充電傳感器網(wǎng)絡(luò)能量?jī)?yōu)化研究[D].杭州:浙江大學(xué),2015.

[13] 韓江洪,丁 煦,石 雷,等.無(wú)線傳感器網(wǎng)絡(luò)時(shí)變充電和動(dòng)態(tài)數(shù)據(jù)路由算法研究[J].通信學(xué)報(bào),2012,33(12):1-10.