劉 創(chuàng)，王 珺，吳 涵

(1.南京郵電大學(xué) 寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.南京郵電大學(xué) 江蘇省無(wú)線通信重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

無(wú)線可充電傳感器網(wǎng)絡(luò)的移動(dòng)充電問(wèn)題研究

劉 創(chuàng)1,2，王 珺1,2，吳 涵1,2

(1.南京郵電大學(xué) 寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.南京郵電大學(xué) 江蘇省無(wú)線通信重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

能量問(wèn)題一直是無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)研究的關(guān)鍵之一。WSN中節(jié)點(diǎn)能量由容量有限電池提供，當(dāng)節(jié)點(diǎn)能量狀態(tài)較低時(shí)需要及時(shí)進(jìn)行更換以確保整個(gè)網(wǎng)絡(luò)的有效性，在復(fù)雜網(wǎng)絡(luò)環(huán)境下人為地進(jìn)行電池更換難以實(shí)現(xiàn)。無(wú)線傳輸技術(shù)的出現(xiàn)有效解決了這一難題。因此采用攜帶高電容量的移動(dòng)節(jié)點(diǎn)，通過(guò)無(wú)線傳輸?shù)姆绞浇o普通節(jié)點(diǎn)進(jìn)行能量補(bǔ)充的無(wú)線可充電傳感器網(wǎng)絡(luò)(Wireless Rechargeable Sensor Network，WRSN)成為當(dāng)前研究的熱點(diǎn)。用移動(dòng)電池車攜帶可進(jìn)行無(wú)線能量傳輸?shù)母吣芰侩姵匮b置進(jìn)入傳感器網(wǎng)絡(luò)中，通過(guò)達(dá)到某一項(xiàng)性能的最優(yōu)制定對(duì)應(yīng)的移動(dòng)充電策略，對(duì)低能量的節(jié)點(diǎn)進(jìn)行能量補(bǔ)充。進(jìn)一步的研究發(fā)展可以根據(jù)實(shí)際的網(wǎng)絡(luò)場(chǎng)景，在充分考慮各項(xiàng)約束的提前下提出綜合的最優(yōu)移動(dòng)充電策略。

無(wú)線傳感器網(wǎng)絡(luò)；無(wú)線能量傳輸；移動(dòng)充電；網(wǎng)絡(luò)生命期

1 概 述

在無(wú)線傳感器網(wǎng)絡(luò)中,傳感節(jié)點(diǎn)的能量一般由電量有限的一次性電池來(lái)提供，這樣將嚴(yán)重制約整個(gè)網(wǎng)絡(luò)的持續(xù)工作時(shí)間。為了保證WSN能夠盡可能長(zhǎng)時(shí)間的正常工作，必須定期對(duì)節(jié)點(diǎn)電池進(jìn)行更換，避免因節(jié)點(diǎn)失效而導(dǎo)致網(wǎng)絡(luò)生命期縮短。但是對(duì)于有特殊環(huán)境要求的應(yīng)用，如火山監(jiān)測(cè)系統(tǒng)、野外科考等，人為地對(duì)傳感節(jié)點(diǎn)電池進(jìn)行定期更換變得難以實(shí)現(xiàn)。從WSN自身能量的節(jié)約和均衡出發(fā)，針對(duì)傳感器節(jié)點(diǎn)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和組網(wǎng)方式展開(kāi)研究，通過(guò)研究WSN的能量管理策略[1-2]、路由MAC層協(xié)議算法[3-4]及跨層協(xié)議[5-6](cross-layer protocol)，平衡各傳感器節(jié)點(diǎn)間的業(yè)務(wù)量，降低節(jié)點(diǎn)能耗，提高WSN的生命期。但該類方案只是盡可能延長(zhǎng)節(jié)點(diǎn)電池壽命，不能從本質(zhì)上解決能量限制的問(wèn)題。通過(guò)從自然環(huán)境中獲取環(huán)保能源(如太陽(yáng)能、風(fēng)能、震動(dòng))以補(bǔ)充傳感器節(jié)點(diǎn)的能量。Cammarano等[7]提出一種準(zhǔn)確的太陽(yáng)能和風(fēng)能采集預(yù)測(cè)模型來(lái)幫助節(jié)點(diǎn)獲取能量。Voigt等[8]提出太陽(yáng)能感知路由，在路由設(shè)計(jì)中考慮了自然能量獲取。但是能量采集技術(shù)的操作過(guò)高地依賴周圍環(huán)境，而環(huán)境的不可控性導(dǎo)致實(shí)際使用的有效性較低，而且能量采集的裝置體積也遠(yuǎn)比傳感節(jié)點(diǎn)大得多。

2007年，Kurs等[9]率先闡述了通過(guò)強(qiáng)耦合磁共振方式進(jìn)行無(wú)線能量傳輸(Wireless Energy Transfer，WET)的可行性，讓無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)入到了一個(gè)全新的局面。

無(wú)線能量傳輸技術(shù)主要有三個(gè)方面的優(yōu)勢(shì)：

(1)不需要供電的源設(shè)備和被充電的終端設(shè)備進(jìn)行有線或者是接觸式連接；

(2)源設(shè)備對(duì)端設(shè)備充電時(shí)不固定方位，也不需要在可視范圍；

(3)相比從環(huán)境獲取能量的不可預(yù)測(cè)性，通過(guò)強(qiáng)耦合磁共振方式獲取能量是穩(wěn)定且可控的。

借助無(wú)線能量傳輸技術(shù)，通過(guò)能量補(bǔ)充設(shè)備為傳感器節(jié)點(diǎn)定期充電是一種解決WSN能量問(wèn)題的新的開(kāi)源方案，實(shí)際操作以承載高容量電池車/機(jī)器人作為移動(dòng)充電器(Mobile Charger，MC)定期提供能量的移動(dòng)充電節(jié)點(diǎn)。這種方式的研究重點(diǎn)主要集中在充電過(guò)程決策方面，目前國(guó)內(nèi)外已經(jīng)取得了一些研究成果。

2 WSN網(wǎng)絡(luò)模型

無(wú)線傳感器網(wǎng)絡(luò)中，部署著一個(gè)固定位置的基站BS/Sink(用v0表示)，N個(gè)隨機(jī)均勻分布在檢測(cè)區(qū)域的傳感器節(jié)點(diǎn)，各傳感節(jié)點(diǎn)的通信半徑均為r。傳感器節(jié)點(diǎn)的位置一旦確定，便不再改變。任意兩節(jié)點(diǎn)間的距離在其通信半徑內(nèi)，則稱兩節(jié)點(diǎn)間存在鏈路，可直接進(jìn)行通信。因此，無(wú)線傳感器網(wǎng)絡(luò)可用無(wú)向連通圖G=(V,E)來(lái)表示，其中V={v0,v1,…,vN}是N個(gè)傳感器節(jié)點(diǎn)與基站的集合，E是鏈路集合。節(jié)點(diǎn)實(shí)時(shí)地進(jìn)行監(jiān)測(cè)并產(chǎn)生感知數(shù)據(jù)，通過(guò)多跳傳輸?shù)姆绞綄?shù)據(jù)傳輸至基站。傳感節(jié)點(diǎn)不僅充當(dāng)感知器，而且可能作為中間傳遞節(jié)點(diǎn)將接收到的其余節(jié)點(diǎn)的數(shù)據(jù)傳輸至鄰近節(jié)點(diǎn)或者基站。

3 WSN移動(dòng)充電模型

無(wú)線傳感器網(wǎng)絡(luò)中，傳感節(jié)點(diǎn)攜帶有存儲(chǔ)容量有限且有無(wú)線能量接收裝置的可充電電池，節(jié)點(diǎn)的最大存儲(chǔ)能量為Emax，能量低于Emin時(shí)節(jié)點(diǎn)將失效。為了確保WSN中的節(jié)點(diǎn)都能夠維持有效的電量水平從而持續(xù)進(jìn)行工作，提出在網(wǎng)絡(luò)中引入移動(dòng)的充電設(shè)備，根據(jù)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)能量狀態(tài)，控制充電設(shè)備的移動(dòng)和充電行為，及時(shí)為低能量的節(jié)點(diǎn)補(bǔ)充能量。一般采用移動(dòng)電池車(也稱移動(dòng)充電器MC)，以恒定速度V運(yùn)動(dòng)到亟需充電的節(jié)點(diǎn)附近，并通過(guò)WET方式為一定范圍內(nèi)的一個(gè)或者多個(gè)節(jié)點(diǎn)進(jìn)行無(wú)線充電。節(jié)點(diǎn)接收到的能量多少取決于MC充電時(shí)的輸出功率以及MC與節(jié)點(diǎn)的距離(傳輸效率)。移動(dòng)設(shè)備攜帶的能量至多為B，既要提供自身的移動(dòng)，又需傳輸至網(wǎng)絡(luò)節(jié)點(diǎn)。最初移動(dòng)電池車攜帶滿能量從其維護(hù)站出發(fā)，根據(jù)網(wǎng)絡(luò)的能量狀態(tài)制定不同的充電策略。為了確保整個(gè)充電過(guò)程的持續(xù)性，移動(dòng)電池車必須在其攜帶的能量低于零之前回到維護(hù)站，進(jìn)行自身能量的補(bǔ)充。根據(jù)網(wǎng)絡(luò)規(guī)模大小、節(jié)點(diǎn)部署密度和移動(dòng)充電設(shè)備攜帶總能量的多少，可有效選取多個(gè)移動(dòng)充電器，以便能及時(shí)對(duì)網(wǎng)絡(luò)中所有的低能量傳感節(jié)點(diǎn)進(jìn)行能量補(bǔ)充。

圖1 WSN的移動(dòng)充電模型

為了確保整個(gè)網(wǎng)絡(luò)能持續(xù)有效地進(jìn)行監(jiān)測(cè)，必須根據(jù)網(wǎng)絡(luò)的各種約束情況制定合理的移動(dòng)充電方案，及時(shí)做出最佳的充電決策，對(duì)節(jié)點(diǎn)進(jìn)行能量補(bǔ)給。當(dāng)出現(xiàn)多個(gè)任務(wù)沖突時(shí)要進(jìn)行合理的調(diào)度，使得網(wǎng)絡(luò)性能受到的影響最小?，F(xiàn)有的研究工作都致力于構(gòu)建合理的充電模型和調(diào)度方案，以最大限度地利用能量資源，最好地保證網(wǎng)絡(luò)的性能。

4 移動(dòng)充電方案的研究

在傳感器網(wǎng)絡(luò)中采用移動(dòng)充電設(shè)備，通過(guò)無(wú)線傳輸?shù)姆绞綖楣?jié)點(diǎn)進(jìn)行能量補(bǔ)充，能有效解決傳統(tǒng)的節(jié)點(diǎn)電池更換不及時(shí)造成的失效問(wèn)題?，F(xiàn)有的研究方案都是以優(yōu)化單一目標(biāo)，如駐站時(shí)間比、吞吐量等等，構(gòu)造充電方案的非線性抽象模型或者規(guī)約到經(jīng)典問(wèn)題進(jìn)行求解。對(duì)不同的優(yōu)化目標(biāo)，充電模型也不一樣，下文出現(xiàn)的移動(dòng)充電節(jié)點(diǎn)均是指移動(dòng)充電設(shè)備。接下來(lái)將從單移動(dòng)節(jié)點(diǎn)的周期性遍歷充電、不考慮數(shù)據(jù)路由的移動(dòng)節(jié)點(diǎn)的充電、多移動(dòng)節(jié)點(diǎn)的充電和移動(dòng)充電節(jié)點(diǎn)兼具收集數(shù)據(jù)四個(gè)方面進(jìn)行對(duì)比研究。

4.1 單移動(dòng)節(jié)點(diǎn)的周期性充電方案

在周期性場(chǎng)景中，均以最大化駐站空閑時(shí)間比為目標(biāo)，移動(dòng)充電設(shè)備均從服務(wù)站(即維護(hù)站)出發(fā)，完成充電活動(dòng)后回到服務(wù)站。

4.1.1 時(shí)不變充電方案

時(shí)不變是指?jìng)鞲衅鞴?jié)點(diǎn)單位時(shí)間收發(fā)數(shù)據(jù)流量不隨時(shí)間而改變。文獻(xiàn)[10]最先提出對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行固定周期T的遍歷充電模型。如圖2所示，移動(dòng)無(wú)線充電設(shè)備(WirelessChargingVehicle，WCV)從服務(wù)站出發(fā)，依次為網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行點(diǎn)對(duì)點(diǎn)的無(wú)線充電，最終又回到服務(wù)站。

圖2 周期性遍歷節(jié)點(diǎn)模型

充電周期定義為：

(1)

其中：TP為WCV在一輪充電中移動(dòng)消耗的總時(shí)間；Ti為任意節(jié)點(diǎn)i的充電時(shí)間；Tvac表示駐站空閑時(shí)間，即在服務(wù)站休整自補(bǔ)給的時(shí)間，研究目標(biāo)是最大化駐站時(shí)間比Tvac/T。

(2)

則節(jié)點(diǎn)i單位時(shí)間的能量消耗pi為：

(3)

其中：ρ為接收單位數(shù)據(jù)的能耗；Cij為節(jié)點(diǎn)i發(fā)送單位數(shù)據(jù)至節(jié)點(diǎn)j的能耗；CiB為單位數(shù)據(jù)直接傳送至基站的能耗(Cij與CiB均與距離有關(guān))。

普通節(jié)點(diǎn)的最大電池容量均為Emax，電量低于Emin時(shí)節(jié)點(diǎn)失效。為了使網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都能正常工作，在任意時(shí)刻t節(jié)點(diǎn)的剩余能量ei(t)≥Emin，即：

Emax-(T-Ti)·pi≥Emin(i∈N)

(4)

為了保持節(jié)點(diǎn)工作的持續(xù)性及周期性，必須滿足在一個(gè)周期中節(jié)點(diǎn)能量消耗等于其在每個(gè)周期中的充電量，即：

T·pi=Ti·U(i∈N)

(5)

初始時(shí)刻節(jié)點(diǎn)的能量均Emax，為了達(dá)到第一可持續(xù)周期之前，必須要構(gòu)建周期性場(chǎng)景，即初始過(guò)渡周期。穩(wěn)定后的周期性充電均是第一可持續(xù)周期的重復(fù)。文獻(xiàn)[10]有效證明了最大化移動(dòng)充電器的駐站空閑時(shí)間就是使移動(dòng)時(shí)間盡可能少，從而得出遍歷所有節(jié)點(diǎn)的路徑最短問(wèn)題其實(shí)就是經(jīng)典的TSP問(wèn)題，因此式(1)可轉(zhuǎn)化為

(6)

最終問(wèn)題轉(zhuǎn)化為在約束公式(2)-(6)下求最大化駐站時(shí)間比。通過(guò)引入輔助變量并松弛約束條件，最終將周期性充電問(wèn)題轉(zhuǎn)化成線性規(guī)劃問(wèn)題，利用求解工具求得了近似最優(yōu)解。

在文獻(xiàn)[11]中，WCV可以同時(shí)為多個(gè)節(jié)點(diǎn)進(jìn)行充電，其可充電范圍為D(表示傳感節(jié)點(diǎn)在充電時(shí)的功率接收速率不低于門(mén)限值時(shí)與WCV的最大距離)，并以基站為中心將整個(gè)網(wǎng)絡(luò)區(qū)域劃分成邊長(zhǎng)為D的正六邊形小區(qū)，如圖3所示。WCV周期性地遍歷訪問(wèn)所有存在節(jié)點(diǎn)的小區(qū)中心位置，給區(qū)內(nèi)所有節(jié)點(diǎn)同時(shí)進(jìn)行充電至滿。顯然，當(dāng)WCV在小區(qū)中心進(jìn)行充電服務(wù)時(shí)，小區(qū)內(nèi)的節(jié)點(diǎn)能量達(dá)到Emax的時(shí)間是不同的，先充電至飽和的節(jié)點(diǎn)會(huì)在該狀態(tài)持續(xù)一段時(shí)間，直到區(qū)內(nèi)其余節(jié)點(diǎn)能量都被充到Emax。

圖3 周期性的小區(qū)充電網(wǎng)絡(luò)模型

文獻(xiàn)[10-11]假定單位時(shí)間節(jié)點(diǎn)收發(fā)數(shù)據(jù)量都保持恒定，沒(méi)有考慮網(wǎng)絡(luò)的動(dòng)態(tài)特性，也沒(méi)有對(duì)移動(dòng)設(shè)備的電容量進(jìn)行限制，因?yàn)閃CV所攜帶的能量不可能是無(wú)限的。此外，討論的都是網(wǎng)絡(luò)規(guī)模較小的情況，對(duì)網(wǎng)絡(luò)規(guī)模較大時(shí)，僅由一個(gè)WCV為所有節(jié)點(diǎn)進(jìn)行周期性遍歷的充電方案是不現(xiàn)實(shí)的，因?yàn)楣?jié)點(diǎn)的充電時(shí)間和WCV移動(dòng)的時(shí)間都將大大增加，可能會(huì)導(dǎo)致不到一個(gè)周期就有節(jié)點(diǎn)會(huì)死亡。

4.1.2 時(shí)變充電方案

文獻(xiàn)[12]中的網(wǎng)絡(luò)與充電模型同文獻(xiàn)[10]，不同于文獻(xiàn)[10-11]中假設(shè)的節(jié)點(diǎn)單位時(shí)間接收和發(fā)送的數(shù)據(jù)在整個(gè)充電過(guò)程中都保持不變，文獻(xiàn)[12]研究的是節(jié)點(diǎn)接收和發(fā)送的數(shù)據(jù)隨時(shí)間變化的周期性遍歷網(wǎng)絡(luò)節(jié)點(diǎn)的充電方案，即時(shí)變充電場(chǎng)景。因此有：

(7)

此時(shí)，單位時(shí)間節(jié)點(diǎn)的能量消耗也隨時(shí)間改變：

(8)

其網(wǎng)絡(luò)模型與充電模型同文獻(xiàn)[10]，最終問(wèn)題轉(zhuǎn)化為連續(xù)時(shí)變優(yōu)化問(wèn)題，求解時(shí)將一般充電周期中WCE(WirelessChargingEquipment)工作狀態(tài)分成三類：行走狀態(tài)、充電狀態(tài)和駐站狀態(tài)。WCE與節(jié)點(diǎn)交互的N次充電活動(dòng)分別對(duì)應(yīng)N個(gè)階段，而WCE與節(jié)點(diǎn)無(wú)交互的行走或駐站成為N+1階段，形成離散N+1階段模型來(lái)求解優(yōu)化問(wèn)題。

文獻(xiàn)[13]的周期性充電場(chǎng)景中，WCE不僅作為能量補(bǔ)給設(shè)備，同時(shí)兼任數(shù)據(jù)采集設(shè)備，在數(shù)據(jù)路由的時(shí)變特性基礎(chǔ)上，研究網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)鋯?wèn)題。傳感數(shù)據(jù)經(jīng)過(guò)多跳方式傳輸至BS或WCE。WCE在為節(jié)點(diǎn)充電的同時(shí)從該節(jié)點(diǎn)處獲取數(shù)據(jù)信息，將充電節(jié)點(diǎn)看成是數(shù)據(jù)采集子網(wǎng)的簇頭，由于WCE是遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)，因此簇頭節(jié)點(diǎn)是動(dòng)態(tài)變化的，子網(wǎng)絡(luò)的劃分也是不固定的，也就是動(dòng)態(tài)拓?fù)淝樾巍?/p>

文獻(xiàn)[13]有效利用了WCE移動(dòng)的優(yōu)勢(shì)，讓其承擔(dān)一部分?jǐn)?shù)據(jù)采集工作，從而避免充電節(jié)點(diǎn)或其臨近節(jié)點(diǎn)因多跳傳輸至基站而消耗更多的能量，而且遍歷所有節(jié)點(diǎn)充電也就是所有節(jié)點(diǎn)均會(huì)擔(dān)任子網(wǎng)簇頭節(jié)點(diǎn)，可以有效均衡能耗。但是由于WCE在網(wǎng)絡(luò)中移動(dòng)和充電耗時(shí)較長(zhǎng)，相比起直接傳輸至基站的那部分?jǐn)?shù)據(jù)，WCE接收的數(shù)據(jù)帶回到維護(hù)站會(huì)有較大的延遲，不適用于有實(shí)時(shí)性要求的網(wǎng)絡(luò)。此外，文獻(xiàn)[12-13]都沒(méi)有對(duì)移動(dòng)設(shè)備所攜帶的能量加以限制。

4.2 未考慮數(shù)據(jù)路由的單移動(dòng)節(jié)點(diǎn)充電方案

文獻(xiàn)[10-13]在制定充電方案的同時(shí)，充分考慮了感知數(shù)據(jù)產(chǎn)生并進(jìn)行數(shù)據(jù)傳輸?shù)哪芰肯倪^(guò)程，而文獻(xiàn)[14]在未考慮該過(guò)程的情況下，研究在不同約束下分別獲得最大化充電吞吐量的單一優(yōu)化充電方案。

文獻(xiàn)[14]提出了以最大化充電吞吐量為目標(biāo)的充電策略，充電吞吐量是指在一次充電活動(dòng)中被充電的節(jié)點(diǎn)個(gè)數(shù)。限制移動(dòng)充電器MC(Mobile Charger)在網(wǎng)絡(luò)中進(jìn)行一輪充電的時(shí)間限制為T(mén)(即T時(shí)間內(nèi)必須重返基站)，由于時(shí)間限制可能來(lái)不及給所有節(jié)點(diǎn)進(jìn)行能量補(bǔ)充，所以必須找到在這個(gè)時(shí)間里能夠?yàn)槠胀ü?jié)點(diǎn)進(jìn)行充電的節(jié)點(diǎn)數(shù)目盡可能多的充電策略。當(dāng)節(jié)點(diǎn)的剩余能量低于門(mén)限值時(shí)，向BS/MC發(fā)送充電請(qǐng)求，BS根據(jù)網(wǎng)絡(luò)狀態(tài)派遣MC(從BS出發(fā))對(duì)發(fā)送充電請(qǐng)求的節(jié)點(diǎn)進(jìn)行點(diǎn)對(duì)點(diǎn)充電，當(dāng)MC在進(jìn)行充電時(shí)，仍會(huì)接收到新的充電請(qǐng)求，MC給每個(gè)節(jié)點(diǎn)充電時(shí)間固定為C。網(wǎng)絡(luò)模型用帶權(quán)重的有向圖G(V,E)表示，發(fā)送充電請(qǐng)求的節(jié)點(diǎn)隊(duì)列Qc，被充電的節(jié)點(diǎn)集合Vc。該問(wèn)題是NP難的，可以通過(guò)一個(gè)經(jīng)典的問(wèn)題——定向運(yùn)動(dòng)問(wèn)題歸約得到，其定義如下：

在歐氏平面給定n個(gè)節(jié)點(diǎn)，標(biāo)號(hào)從1到n，每個(gè)節(jié)點(diǎn)都有個(gè)分?jǐn)?shù)(score)，找到一條以1為起點(diǎn)、n為終點(diǎn)的最大分?jǐn)?shù)路徑，路徑長(zhǎng)度預(yù)算(或者持續(xù)時(shí)間)不大于給定值。

帶時(shí)間窗的定向運(yùn)動(dòng)問(wèn)題：給定有向弧權(quán)重圖G=(V',A',l')，l'(u,v)表示弧長(zhǎng)(u,v)∈A'，任意節(jié)點(diǎn)v'∈V'有一個(gè)時(shí)間窗[R(v'),D(v')]，其中R(v')≤D(v')表示訪問(wèn)節(jié)點(diǎn)v'的時(shí)刻必須位于這個(gè)區(qū)間。任意兩個(gè)節(jié)點(diǎn)s,t∈V'有整數(shù)預(yù)算值B>0，找到一條s-t游走長(zhǎng)度至多為B但是覆蓋的頂點(diǎn)數(shù)最多的路徑。

對(duì)于該問(wèn)題，可利用已有的迭代貪婪算法求解。文獻(xiàn)[15]證明了移動(dòng)充電的離線充電方案可以從帶時(shí)間窗的定向運(yùn)動(dòng)問(wèn)題歸約得到。方法如下：

將任一個(gè)發(fā)送充電請(qǐng)求的節(jié)點(diǎn)v∈V分裂成兩個(gè)端點(diǎn)v',v″，將該節(jié)點(diǎn)v的充電時(shí)間轉(zhuǎn)化為l(v',v″)=C，對(duì)v'與v″的時(shí)間約束分別為[ri,T],[ri+C,T](ri是節(jié)點(diǎn)i發(fā)送充電請(qǐng)求的時(shí)刻)，構(gòu)建基站與其余節(jié)點(diǎn)(若其他節(jié)點(diǎn)進(jìn)行了分裂，則用時(shí)間窗更小的那個(gè)端點(diǎn))到v'的弧，同時(shí)從v″到基站和其余節(jié)點(diǎn)(進(jìn)行了分裂，則用時(shí)間窗較大的端點(diǎn))的弧。

顯然，離線充電方案轉(zhuǎn)化成了帶時(shí)間窗的定向運(yùn)動(dòng)問(wèn)題，只是運(yùn)動(dòng)的起點(diǎn)和終點(diǎn)均為基站，文中提出了猜測(cè)充電序列中間節(jié)點(diǎn)的方式，迭代地進(jìn)行求解。

文獻(xiàn)[14]考慮了節(jié)點(diǎn)的異構(gòu)特性，即每個(gè)節(jié)點(diǎn)的能耗速率不同且維持各自的值不變，由于充電的請(qǐng)求提前知道，但不可能在一輪充電中滿足所有請(qǐng)求，算法是最大化充電吞吐量，而沒(méi)有考慮節(jié)點(diǎn)剩余生存時(shí)間，有可能造成達(dá)到最大的充電吐吞量的路徑?jīng)]有覆蓋剩余時(shí)間最少的節(jié)點(diǎn)的情形。另外，由于節(jié)點(diǎn)充電時(shí)的剩余能量不可能是相同的，因此充電時(shí)間不可能是常數(shù)C。

4.3 協(xié)作式充電方案

文獻(xiàn)[15-16]開(kāi)始研究有多個(gè)移動(dòng)充電器時(shí)的協(xié)作式調(diào)度充電方案。不同于文獻(xiàn)[10-14]，協(xié)作式充電對(duì)MC的能量進(jìn)行了限定。文獻(xiàn)[15]中首次提出MC不僅可以為傳感節(jié)點(diǎn)充電，還可與其他MC互相充電。移動(dòng)充電器從基站攜帶滿電量出發(fā)，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行充電后，最終回到BS進(jìn)行能量補(bǔ)給，準(zhǔn)備下一輪的充電，研究基于一維線性部署網(wǎng)絡(luò)。N個(gè)傳感節(jié)點(diǎn)的電池容量均為b，任意節(jié)點(diǎn)i單位時(shí)間耗電量為ri且保持不變，則節(jié)點(diǎn)的再充電周期為τi=b/ri。將網(wǎng)絡(luò)的調(diào)度周期定義為所有的傳感器節(jié)點(diǎn)都被充滿電的兩個(gè)連續(xù)的時(shí)間點(diǎn)之間的間隔。目標(biāo)是最大化MC給網(wǎng)絡(luò)中所有節(jié)點(diǎn)總的充電量Epayload與MC自身移動(dòng)耗能Eoverhead的比值：

ration=Epayload/Eoverhead

在節(jié)點(diǎn)能耗速率一致，MC的個(gè)數(shù)為k的情況下，Zhang等用實(shí)例證明在移動(dòng)節(jié)點(diǎn)數(shù)目固定、總能量一致的情況下，移動(dòng)充電器之間相互協(xié)作的充電方式相對(duì)于無(wú)協(xié)作的方式覆蓋充電的節(jié)點(diǎn)更多[15]。如圖4(a)所示：每個(gè)節(jié)點(diǎn)充電量由一個(gè)MC提供，且移動(dòng)充電器MCi給Li+1到Li之間的節(jié)點(diǎn)充電，MCi在Li給MCi-1,MCi-2,…,MC1充滿電，MCi剛好有足夠的能量返回BS。Zhang等針對(duì)協(xié)作式充電方式提出了PushWait算法(見(jiàn)圖4(b))：MCi給Li+1到Li之間的節(jié)點(diǎn)充電，且MCi在Li給MCi-1,MCi-2,…,MC1充滿電，然后在Li等待其他i-1個(gè)MC都回到Li，再平均分配自己的能量給所有的MC(包括自身)，確保所有的MC都能返回BS。MCi在Li+1充滿電，最后返回到Li+1能量剛好為0。在相同條件下，PushWait算法的協(xié)作式充電方式是最優(yōu)的。

(a)協(xié)同方式

(b)PushWait方式

文獻(xiàn)[15]雖然有效地考慮了MC的能量限制，但是忽略了充電時(shí)間，實(shí)際也并未考慮MC移動(dòng)時(shí)間與節(jié)點(diǎn)充電量及節(jié)點(diǎn)能量消耗量之間的具體聯(lián)系。此外，沒(méi)有考慮傳輸?shù)哪芰繐p耗，而且僅考慮了單一的線性一維網(wǎng)絡(luò)場(chǎng)景。在文獻(xiàn)[15]的研究成果基礎(chǔ)上，文獻(xiàn)[16]中充電模型突破1-D的約束，研究2-D網(wǎng)絡(luò)并充分考慮了能量傳輸時(shí)的損耗以及節(jié)點(diǎn)不同的再充電周期，結(jié)合單約束情形下各個(gè)子算法的優(yōu)勢(shì)，提出了綜合性能最佳的HηClusterCharing(β)算法。

協(xié)作式的充電方式提出移動(dòng)充電器可以互相充電，并沒(méi)有實(shí)際的理論作指導(dǎo)。在同一充電時(shí)刻，一個(gè)充電器可能同時(shí)給不同組的節(jié)點(diǎn)進(jìn)行能量補(bǔ)充，沒(méi)有考慮到充電器到達(dá)不同節(jié)點(diǎn)經(jīng)過(guò)的路程不一樣，所花費(fèi)的時(shí)間不一樣。同樣也忽略了充電時(shí)間，沒(méi)有考慮數(shù)據(jù)路由對(duì)節(jié)點(diǎn)能量消耗帶來(lái)的影響。

4.4 移動(dòng)設(shè)備兼具數(shù)據(jù)收集的方案

文獻(xiàn)[17]采用稱之為SenCar的兼具移動(dòng)充電和數(shù)據(jù)收集的多功能移動(dòng)設(shè)備，既充當(dāng)數(shù)據(jù)收集器又充當(dāng)充電器，網(wǎng)絡(luò)所有的數(shù)據(jù)都經(jīng)過(guò)SenCar傳回靜態(tài)基站，模型如圖5所示。

圖5 集合移動(dòng)能量補(bǔ)充和移動(dòng)數(shù)據(jù)收集模型

移動(dòng)節(jié)點(diǎn)在網(wǎng)絡(luò)中預(yù)先用離線算法，在SenCar進(jìn)行一輪充電活動(dòng)移動(dòng)的總距離不超過(guò)給定值Ltsp的約束下選定的停留點(diǎn)(anchorpoint，特定的節(jié)點(diǎn)位置)進(jìn)行充電服務(wù)，并確定停留點(diǎn)的訪問(wèn)順序。在停留點(diǎn)進(jìn)行充電的同時(shí)，SenCar收集l跳范圍內(nèi)的節(jié)點(diǎn)數(shù)據(jù)(l的選擇會(huì)影響傳感節(jié)點(diǎn)的能量消耗速率，必須確保所有的停留點(diǎn)能覆蓋網(wǎng)絡(luò)所有的傳感節(jié)點(diǎn))。Guo等[17]在充電時(shí)變過(guò)程、節(jié)點(diǎn)間存在鏈路時(shí)的鏈路容量的約束以及SenCar在網(wǎng)絡(luò)中充電的總時(shí)間不超過(guò)定值T的條件下，試圖找到最優(yōu)的數(shù)據(jù)產(chǎn)生和上傳速率，每個(gè)節(jié)點(diǎn)最佳的數(shù)據(jù)傳輸?shù)穆窂桨才欧桨?，以及移?dòng)收集器在每個(gè)停留點(diǎn)的最佳停留時(shí)間，并提出一個(gè)分布式的自適應(yīng)解決方案，使得整個(gè)網(wǎng)絡(luò)的有效性最大。

利用SenCar進(jìn)行數(shù)據(jù)收集相比文獻(xiàn)[10-12]的直接多跳傳輸至基站的方式，能夠節(jié)約更多的能量，有效避免了固定基站的周圍節(jié)點(diǎn)能量過(guò)度消耗而死亡的危險(xiǎn)，但是SenCar收集數(shù)據(jù)的延遲會(huì)增加，不適合于對(duì)實(shí)時(shí)性要求較高的網(wǎng)絡(luò)，另外在選擇停留點(diǎn)時(shí)考慮離線算法，不能很好地代表整個(gè)網(wǎng)絡(luò)的實(shí)時(shí)情況。

5 結(jié)束語(yǔ)

無(wú)線傳輸技術(shù)的出現(xiàn)開(kāi)創(chuàng)了WSN網(wǎng)絡(luò)研究的新局面，通過(guò)在WSN中引入移動(dòng)充電節(jié)點(diǎn)進(jìn)行無(wú)線的能量補(bǔ)充，有效解決了WSN的節(jié)點(diǎn)能量限制的問(wèn)題，目前的研究也取得了一定的成果。

文中對(duì)現(xiàn)有的移動(dòng)充電策略研究工作，從多個(gè)角度出發(fā)進(jìn)行了分類對(duì)比分析。針對(duì)當(dāng)前研究在松優(yōu)化條件下只考慮某單一性能最優(yōu)的局限，進(jìn)一步的研究工作可從以下幾個(gè)方面展開(kāi)：

(1)已有的研究大多基于離線的方式，在MC從出發(fā)去充電時(shí)就已經(jīng)計(jì)算好了移動(dòng)的路徑和經(jīng)過(guò)的節(jié)點(diǎn)，可以考慮在線請(qǐng)求情況，及時(shí)地對(duì)低能量節(jié)點(diǎn)進(jìn)行充電。

(2)綜合考慮多方面的約束因子：如節(jié)點(diǎn)的異構(gòu)特性，MC的能量限制，接收、發(fā)送和產(chǎn)生數(shù)據(jù)的能量耗消，通信開(kāi)銷，MC的運(yùn)動(dòng)時(shí)間以及充電時(shí)間等等，更加接近真實(shí)的網(wǎng)絡(luò)環(huán)境。

(3)構(gòu)建通用的充電策略架構(gòu)：可以根據(jù)網(wǎng)絡(luò)規(guī)模選定參與充電的節(jié)點(diǎn)數(shù)是單個(gè)還是多個(gè)，以怎樣的方式充，是在線還是離線，是適合移動(dòng)基站綁定還是固定基站，是同時(shí)充電還是在充電的同時(shí)兼具收集數(shù)據(jù)。充分考慮網(wǎng)絡(luò)對(duì)實(shí)時(shí)性的要求以及網(wǎng)絡(luò)屬性，選擇相應(yīng)的最佳方案。

[1]WangQ,YangW.Energyconsumptionmodelforpowermanagementinwirelesssensornetworks[C]//Procof4thannualIEEEcommunicationssocietyconferenceonsensor,meshandadhoccommunicationsandnetworks.[s.l.]:IEEE,2007:142-151.

[2]SalvadoriF,deCamposM,SausenPS,etal.Monitoringinindustrialsystemsusingwirelesssensornetworkwithdynamicpowermanagement[J].IEEETransactionsonInstrumentationandMeasurement,2009,58(9):3104-3111.

[3] 楊 寧,田 輝,黃 平,等.基于博弈理論的無(wú)線傳感器網(wǎng)絡(luò)分布式節(jié)能路由算法[J].電子與信息學(xué)報(bào),2008,30(5):1230-1233.

[4]SazakN,ErturkI,KoklukayaE,etal.AnenergyefficientMACprotocolforclusterbasedeventdrivenWSNapplications[C]//Procofinternationalconferenceonsoftware,telecommunicationsandcomputernetworks.[s.l.]:[s.n.],2010:76-81.

[5]AkyildizIF,VuranMC,AkanOB.Across-layerprotocolforwirelesssensornetworks[C]//Procof40thannualconferenceoninformationsciencesandsystems.[s.l.]:[s.n.],2006:1102-1107.

[6]VuranMC,AkyildizIF.XLP:across-layerprotocolforefficientcommunicationinwirelesssensornetworks[J].IEEETransactionsonMobileComputing,2010,9(11):1578-1591.

[7]CammaranoA,PetrioliC,SpenzaD.Pro-energy:anovelenergypredictionmodelforsolarandwindenergy-harvestingwirelesssensornetworks[C]//ProcofIEEE9thinternationalconferenceonmobileadhocandsensorsystems.[s.l.]:IEEE,2012:75-83.

[8]VoigtT,RitterH,SchillerJ.Utilizingsolarpowerinwirelesssensornetworks[C]//Proceedingsof28thannualIEEEinternationalconferenceonlocalcomputernetworks.[s.l.]:IEEE,2003:416-422.

[9]KursA,KaralisA,MoffattR,etal.Wirelesspowertransferviastronglycoupledmagneticresonances[J].Science,2007,317(5834):83-86.

[10]ShiYi,XieLiguang,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer[C]//ProceedingsofIEEE.Shanghai:IEEE,2011:1350-1358.

[11]XieL,ShiY,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer:themulti-nodecase[C]//Procof9thannualIEEEcommunicationssocietyconferenceonsensor,meshandadhoccommunicationsandnetworks.[s.l.]:IEEE,2012:10-18.

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

[13] 丁 煦，韓江洪，石 雷,等.可充電無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)鋯?wèn)題研究[J].通信學(xué)報(bào)，2015，36(1):129-141.

[14]RenXiaojiang,LiangWeifa,XuWenzheng.Maximizingchargingthroughputinrechargeablesensornetworks[C]//Procof23rdinternationalconferenceoncomputercommunicationandnetworks.Shanghai:IEEE,2014:1-8.

[15]ZhangS,WuJ,LuS.Collaborativemobilechargingforsensornetworks[C]//ProcofIEEE9thinternationalconferenceonmobileadhocandsensorsystems.[s.l.]:IEEE,2012:84-92.

[16]ZhangS,WuJ,LuS.Collaborativemobilecharging[J].IEEETransactionsonComputers,2013,64(3):654-667.

[17]GuoSongtao,WangCong,YangYuanyuan.Jointmobiledatagatheringandenergyprovisioninginwirelessrechargeablesensornetworks[J].IEEETransactionsonMobileComputing,2014,13(12):2836-2852.

Research on Mobile Charging Issues on Wireless Rechargeable Sensor Networks

LIU Chuang1,2，WANG Jun1,2，WU Han1,2

(1.Key Lab of Broadband Wireless Communication and Sensor Network Technology of MOE,NJUPT,Nanjing 210003,China;2.Jiangsu Key Lab of Wireless Communication of NJUPT,Nanjing 210003,China)

Energy is a key issue in wireless sensor networks.The energy of nodes is provided by limited battery energy.It is necessary to replace battery to make sure the availability of networks when the node nearly uses up its power.But the location of nodes is unreachable on complicated network environment.As a newly emerged technology,wireless transfer effectively addresses this problem.Therefore,it focuses on adopting a mobile node with high capacity of energy and using wireless transfer technique to recharge low energy nodes on WRSN.A mobile vehicle is used to carry the fully charged battery with high capacity,which can recharge general nodes by wireless energy transfer,and most charging strategies only achieve the optimal with a certain goal.Aiming at the limitation of traditional charging strategies,future research and development should be based on the real network environment,taking multiple constrains into consideration,then coming up with the comprehensive optimal mobile charging solution.

WSN;wireless energy transfer;mobile charging;network lifetime

2015-06-16

2015-09-17

時(shí)間：2016-02-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401234)

劉 創(chuàng)(1990-)，女，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；王 珺，副教授，研究方向?yàn)閷拵ЬW(wǎng)絡(luò)技術(shù)、傳感器網(wǎng)絡(luò)以及網(wǎng)絡(luò)安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1634.046.html

TP393

A

1673-629X(2016)03-0162-06

10.3969/j.issn.1673-629X.2016.03.038