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

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

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

1 引 言

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

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

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

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

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

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

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

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

對無線傳感器和移動充電設(shè)備做如下假設(shè):

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

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

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

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

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

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

2.2 耗電模型

(1)

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

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

(2)

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

(3)

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

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

(4)

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

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

(5)

2.3 問題描述

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

(6)

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

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

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

3.1 問題分析

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

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

3.2 充電路徑規(guī)劃

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

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

線圈上的每個點(diǎn)都受到兩個力的作用.一個是來自節(jié)點(diǎn)的引力,這個力使得點(diǎn)朝著距離自己最近的城市靠近;第二個是來自鄰居點(diǎn)的張力,使得它向鄰居節(jié)點(diǎn)靠近,從而使得整個線圈長度最短.這樣,每個城市都與線圈上一個點(diǎn)的集合關(guān)聯(lián)起來.城市與節(jié)點(diǎn)集合關(guān)聯(lián)的緊密程度由城市與節(jié)點(diǎn)之間的距離決定,并且這種關(guān)聯(lián)程度隨著算法的迭代而變化.一開始,每個城市對點(diǎn)的作用都是相同的,隨著算法的迭代,距離點(diǎn)較遠(yuǎn)的城市的作用力逐漸減小,距離點(diǎn)較近的點(diǎn)的作用力逐漸增強(qiáng).這種逐漸增強(qiá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對點(diǎn)j的影響,通常是城市i和點(diǎn)j之間距離|xi-yj|以及K的函數(shù),這個函數(shù)可以被標(biāo)準(zhǔn)化表示為:

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

(8)

其中,φ(d,K)是關(guān)于d的正向有界函數(shù),當(dāng)d>K時趨近于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ǎ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ī)劃具體過程為:

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

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

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

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

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

剩余存活時間預(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)剩余存活時間成正比,分子部分為節(jié)點(diǎn)剩余能量;由于節(jié)點(diǎn)發(fā)送能耗與距離的二次方成正比,與節(jié)點(diǎn)剩余存活時間成反比,分母部分第一項(xiàng)為節(jié)點(diǎn)發(fā)送能耗的預(yù)估值;由于節(jié)點(diǎn)接收能耗與距離成正比,分母第二項(xiàng)為節(jié)點(diǎn)接收能耗的預(yù)估值.

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

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

步驟2.初始化k=1;

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

步驟4.將網(wǎng)絡(luò)中所有節(jié)點(diǎn)按照路徑權(quán)重升序排序,選取前k個節(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.移動充電設(shè)備遍歷路徑上的每個節(jié)點(diǎn),并對其進(jìn)行無線充電;

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

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

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

(14)

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

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

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

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

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

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

(15)

(16)

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

3.3 算法流程

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

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

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

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

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

圖3 實(shí)驗(yàn)仿真場景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,移動充電設(shè)備運(yùn)行速度V=5m/s,移動充電設(shè)備電量B=500kJ,移動充電設(shè)備行走耗電功率ηtsp=10w,移動充電設(shè)備無線充電能耗功率ηc=10w,無線充電功率U=0.02W,無線充電設(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ò)的多移動充電設(shè)備充電路徑規(guī)劃算法.運(yùn)行algorithm算法得出,在300m×300m、200個節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)中,最少使用5臺移動充電設(shè)備、k取5的時候,網(wǎng)絡(luò)可持續(xù)運(yùn)行.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

運(yùn)行時間充電設(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可知,移動充電設(shè)備的行走能耗遠(yuǎn)大于無線充電能耗,因此,其主要耗電來自行走能量消耗.再看移動充電設(shè)備的充電路徑長度,均在500米到1300米之間,且移動充電設(shè)備的剩余能量足夠其從維護(hù)站出發(fā),遍歷每個節(jié)點(diǎn)后重新回到維護(hù)站.由此說明本文提出的容量受限的多移動設(shè)備充電路徑調(diào)度算法符合移動充電設(shè)備的能量約束.

為了驗(yàn)證本文所提算法能夠減少移動充電設(shè)備數(shù)量,對所需移動充電設(shè)備數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)增多的情況進(jìn)行了仿真,并與文獻(xiàn)[11]提出的Enhanced MinMCP算法做了對比,結(jié)果如圖9所示.圖9的仿真參數(shù)為[11]:被監(jiān)測區(qū)域大小為5km×5km,傳感器節(jié)點(diǎn)最大電量Emax=10.8kJ,傳感器節(jié)點(diǎn)最低工作電量Emin=0.05Emax=540J,所有節(jié)點(diǎn)耗電功率相同為200mW,移動充電設(shè)備運(yùn)行速度V=5m/s,移動充電設(shè)備電量B=500kJ,移動充電設(shè)備行走耗電功率ηp=100w,移動充電設(shè)備無線充電能耗功率ηc=110w,無線充電功率U=5W,無線充電設(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)個數(shù),縱坐標(biāo)為維持網(wǎng)絡(luò)持續(xù)運(yùn)行所需的移動充電設(shè)備數(shù).由圖9可知,在被檢測區(qū)域大小不變的 情況下,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多,兩種算法所需的移動充電設(shè)備數(shù)量都增大,但是本文算法所需的移動充電設(shè)備數(shù)量始終少于或等于Enhanced MinMCP算法所需的移動充電設(shè)備數(shù).這是因?yàn)?在被檢測區(qū)域大小不變的情況下,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多,移動充電設(shè)備需要為更多的節(jié)點(diǎn)充電,因此需要的移動充電設(shè)備數(shù)量增多.另外,Enhanced MinMCP算法需要固定分區(qū),并不能夠按需靈活調(diào)整移動充電設(shè)備覆蓋的節(jié)點(diǎn),而本文所提算法不分區(qū),完全根據(jù)整個網(wǎng)絡(luò)中節(jié)點(diǎn)的需求進(jìn)行路徑規(guī)劃,能夠充分利用移動充電設(shè)備,減少移動充電設(shè)備數(shù).

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

5 總 結(jié)

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

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