尹 玲，謝志軍

(寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211)

1 引言

無線充電是指利用磁共振耦合原理進(jìn)行充電。移動充電器MC(Mobile Charger)配有高容量電池和發(fā)射線圈，節(jié)點則配備接收線圈，MC移動到節(jié)點附近，將自身電池輸出的直流電DC(Direct Current)通過DC/AC轉(zhuǎn)換器轉(zhuǎn)換為交流電AC(Alternating Current)進(jìn)而在接收線圈附近產(chǎn)生變化的振蕩磁場，節(jié)點以相同的振蕩頻率在接收線圈上接收到交流電，再通過AC/DC轉(zhuǎn)換器將其轉(zhuǎn)換成為其電池充電的直流電。由于節(jié)點的能量消耗率各不相同，如何規(guī)劃MC的行進(jìn)路徑，滿足網(wǎng)絡(luò)中所有節(jié)點實時充電的需求，并使能量利用率達(dá)到最大，是本文要解決的問題。

已經(jīng)有很多研究致力于無線可充電傳感器網(wǎng)絡(luò)WRSNs(Wireless Rechargeable Sensor Networks)中MC的充電路徑規(guī)劃問題，一般可分為單MC充電方式[1 -3]和多MC充電方式[4 -7]。其中，文獻(xiàn)[1]提出了MC預(yù)先行程規(guī)劃與充電關(guān)聯(lián)的問題；文獻(xiàn)[2,3]研究了單MC定向充電方式的時延及成本最小化的問題。單MC充電方式實現(xiàn)簡單，但多MC充電方式肯定能進(jìn)一步提高網(wǎng)絡(luò)性能，文獻(xiàn)[4]設(shè)計了一種啟發(fā)式算法為含有多個MC的WRSNs中節(jié)點周期性充電；文獻(xiàn)[5]則提出了基于不均勻集群的移動充電算法，用于解決節(jié)點能耗不均衡及MC充電效率隨時間變化而衰減的問題。以上工作的研究重點在于合理規(guī)劃充電路徑，以達(dá)到預(yù)期充電效果。還有學(xué)者提出根據(jù)節(jié)點充電請求的緊急程度來規(guī)劃充電路徑，文獻(xiàn)[6,7]就結(jié)合了節(jié)點的時空特征來共同規(guī)劃MC的充電路徑，但制定的策略適合靜態(tài)路由。現(xiàn)有的研究工作還沒有考慮在大型WRSNs中根據(jù)節(jié)點的時空特征來實時規(guī)劃路徑。

本文在現(xiàn)有工作的基礎(chǔ)上提出一種基于時空協(xié)作的多MC充電路徑規(guī)劃方案，與上述研究工作不同的是，本文方案不僅聯(lián)合考慮了節(jié)點的空間位置和充電請求的時間要求，還為MC維持了一個動態(tài)隊列，用于保存MC的局部充電路徑，并能隨時按照充電請求的緊急程度調(diào)整MC的行進(jìn)路徑。本文的主要創(chuàng)新點總結(jié)如下：

(1)為更好地解決大型WRSNs中多MC的路徑規(guī)劃問題，將其形式化為多目標(biāo)聯(lián)合優(yōu)化問題。

(2)創(chuàng)新性地提出一種基于時空協(xié)作的多MC實時充電算法STMA(Space-Time cooperative Multi-MC charging Algorithm)，該算法聯(lián)合考慮了節(jié)點空間位置和截止充電時間，并為每個MC保持一個動態(tài)隊列，用于保存局部充電路由，在MC執(zhí)行充電任務(wù)的同時還能獲取并響應(yīng)緊急節(jié)點充電請求，使得能量消耗快的節(jié)點能及時充上電。

2 相關(guān)工作

當(dāng)前關(guān)于WRSNs中MC的充電路徑規(guī)劃的研究工作一般可細(xì)分為4類：單MC離線調(diào)度(S-off)[1 -3]、單MC在線調(diào)度(S-on)[8 -11]、多MC離線調(diào)度(M-off)[4,5,12]和多MC在線調(diào)度(M-on)[6,7,13]。離線(Off-line)調(diào)度方法指的是預(yù)先規(guī)劃好MC行程，實現(xiàn)簡單但靈活性低；在線(On-line)調(diào)度方法則側(cè)重于為節(jié)點按需充電，以較低的充電代價達(dá)到較高的網(wǎng)絡(luò)效用。

S-off方式指事先規(guī)劃好MC的充電順序和時間以達(dá)到理想的能量效用，如文獻(xiàn)[1-3]中預(yù)先規(guī)劃MC行程，以達(dá)到能量耗費少、充電效率高的目的；S-on方式則選擇為節(jié)點按需充電，文獻(xiàn)[8]針對按需充電架構(gòu)提出一種時空調(diào)度算法，用于及時調(diào)整緊急節(jié)點的充電順序；文獻(xiàn)[9]則從另外一個角度考慮按需充電，通過實時控制MC的行進(jìn)路徑和速度來解決節(jié)點能量補(bǔ)充不均勻的情況；文獻(xiàn)[10]則應(yīng)用了馬爾可夫決策過程來優(yōu)化MC每個時間段內(nèi)行進(jìn)的路徑和待充電的節(jié)點集；文獻(xiàn)[11]針對節(jié)點的能量饑餓問題，提出一種在線充電調(diào)度方法。上述基于單MC的充電方式實現(xiàn)復(fù)雜度小，適用于小型WRSNs。

對于大型WRSNs來說，節(jié)點數(shù)量龐大、能耗率不一，單MC供電的方式難以保證所有節(jié)點實時充電的需求。M-off方式使用多個MC協(xié)同工作，以提高節(jié)點存活率和成功充電率。文獻(xiàn)[4，5]考慮到節(jié)點能耗不均衡和充電效率隨距離衰減的問題，提出了使用多個MC為長期工作的傳感器節(jié)點周期性充電的調(diào)度算法；文獻(xiàn)[12]考慮了時空約束來為MC規(guī)劃充電路徑，但其制定的充電策略適用于靜態(tài)路由。針對以上不足，M-on方式側(cè)重于使用多個MC為節(jié)點按需充電，如在文獻(xiàn)[6,7]中，就結(jié)合了時間和空間要求共同決策M(jìn)C的充電路徑，其中文獻(xiàn)[6]結(jié)合了節(jié)點的空間優(yōu)先級和時間優(yōu)先級制訂了混合優(yōu)先級算法——mTS(Temporal-and Spatial-collaborative charging for multiple WCVs)，但沒有考慮路由的實時更新；而文獻(xiàn)[7]提出的DAZ(Dynamic Active Zone strategy)算法則是把節(jié)點的充電請求分為緊急請求和一般請求，優(yōu)先對緊急請求的節(jié)點充電，但對節(jié)點的充電時限欠缺考慮；文獻(xiàn)[13]提出了基于遺傳算法GA(Genetic Algorithm)的多MC充電調(diào)度算法，同樣是在路由實時更新上欠缺考慮。

本文針對現(xiàn)有工作的不足，結(jié)合時間和空間的要求，考慮了充電路由的實時更新，設(shè)計了一種基于時空協(xié)作的多MC充電路徑規(guī)劃方案。仿真結(jié)果表明，本文提出的方案和目前最新的研究工作相比，具有更高的能量利用率和節(jié)點存活率，并在隊列長度和充電時延方面也有較好的表現(xiàn)，可以很好地擴(kuò)展到大型WRSNs。

3 系統(tǒng)架構(gòu)

本節(jié)首先介紹所提方案的網(wǎng)絡(luò)模型，并給出問題描述和解決方案。

圖1所示的WRSN由大量固定位置的無線可充電節(jié)點、多個MC和1個基站BS(Base Station)組成。節(jié)點、MC和BS都裝備有GPS模塊，其中節(jié)點和MC配備了容量有限的電池，假設(shè)BS具有無限的能量，且位置由人為指定。各節(jié)點負(fù)責(zé)監(jiān)測環(huán)境、收集信息，并與BS保持通信；BS負(fù)責(zé)數(shù)據(jù)融合與處理；MC能夠準(zhǔn)確定位節(jié)點和BS，以完成無線充電任務(wù)。

Figure 1 WRSN model with 3 MCs圖1 含有3個MC的WRSN模型

3.1 問題描述

本文將上述具有實時性要求的WRSN中的多MC充電路徑規(guī)劃問題描述如下：在一個含有若干隨機(jī)部署的無線可充電節(jié)點、1個BS和多個MC的WRSN中，各節(jié)點以不同速率消耗自身能量，并在能量低于閾值的時候發(fā)出充電請求，由BS負(fù)責(zé)接收并根據(jù)節(jié)點所處位置，將充電請求分配到對應(yīng)區(qū)域內(nèi)MC的充電隊列中排隊。MC從BS出發(fā)，根據(jù)充電請求的緊急程度依次為各個節(jié)點補(bǔ)充能量，并在自身能量不足時返回BS。

本文方案的設(shè)計目標(biāo)是為每個MC尋找一條最佳的充電路徑，使得能量消耗快的節(jié)點的充電請求能被提前響應(yīng)，并最大可能保證整個網(wǎng)絡(luò)的節(jié)點存活率和能量利用率最高，同時保持較短的充電隊列長度和充電時延。

3.2 解決方案

為解決上述多個目標(biāo)聯(lián)合優(yōu)化問題，本文首先建立一個多目標(biāo)優(yōu)化模型，并針對目標(biāo)函數(shù)給出約束條件；然后通過將網(wǎng)絡(luò)劃分為多個簇，研究單個簇內(nèi)多目標(biāo)的最優(yōu)實現(xiàn)，進(jìn)而提出有效的充電算法。

首先建立如下多目標(biāo)優(yōu)化模型：

(1)能量目標(biāo)。

由于MC電池容量有限，且一旦出發(fā)，只有當(dāng)能量不足時才能返回BS充電，因此要合理運用有限的能量，使得能量利用率η最高：

(1)

其中，EN是節(jié)點的總電池容量，EC是MC為節(jié)點充電而損耗的能量，EM是MC行駛過程所損耗的能量，EMC是MC的總電池容量。EN、EMC可事先指定，而EC和EM可按式(2)計算：

(2)

其中，N是節(jié)點總數(shù)，q是節(jié)點從MC獲取能量的速率，(EN-ei)/q則表示節(jié)點xi從開始充電到完成充電的時間，ei是節(jié)點xi的當(dāng)前剩余能量，d是MC行駛的距離，EM是MC以速度v行駛距離d所耗費的能量。

(2)存活率目標(biāo)。

對于整個WRSN來說，每個節(jié)點都發(fā)揮著各自的作用，因此要保證節(jié)點存活率δ最高：

maxδ=Nlive/N

(3)

其中，Nlive是正常工作的活節(jié)點數(shù)。

從根本上來說，能量目標(biāo)和存活率目標(biāo)都是為了延長網(wǎng)絡(luò)的生命周期、最大化網(wǎng)絡(luò)效用。因此，本文將上述多目標(biāo)優(yōu)化問題加權(quán)轉(zhuǎn)化為單目標(biāo)優(yōu)化問題：

(4)

其中，α和β是加權(quán)因子，分別表示能量目標(biāo)和存活率目標(biāo)對于總體目標(biāo)的權(quán)重。由于較高的能量利用率代表了更多的能量用于為節(jié)點充電，更少的能量用于MC移動，而MC移動較少的路徑就能將更多的能量提供給節(jié)點充電，其實這2個目標(biāo)是正相關(guān)的關(guān)系，難以區(qū)分哪一個目標(biāo)對整體目標(biāo)影響更大。因此，本文取α=β=0.5，把式(4)擴(kuò)大2倍得到如式(3)所示的目標(biāo)函數(shù)：

(5)

式(5)中的待求量可由式(2)和式(3)求出，確定目標(biāo)函數(shù)后，考慮到能量消耗與能量補(bǔ)充的平衡，有如式(6)所示的能量約束：

EC+EM+γ≤EMC

(6)

其中，γ是MC與BS交換信息所耗費的能量，可忽略不計。

另外，還要保證給節(jié)點充電的時間大于MC移動的時間，因此有如式(7)所示的時間約束：

(7)

其中，dxi,xi+1指的是MC從當(dāng)前充電節(jié)點xi處移動到下一目標(biāo)節(jié)點xi+1處的歐氏距離，v是MC的行駛速度,ti為第i個節(jié)點充電所用時間。

再結(jié)合節(jié)點正常工作時的能量要求，得到如式(8)所示的約束條件：

(8)

針對上述提出的多目標(biāo)優(yōu)化模型，本文設(shè)計了一個兩步走充電策略，目標(biāo)是使得式(5)的值最大：

(1)使用改進(jìn)的聚類算法公平地劃分網(wǎng)絡(luò)為多個簇，每個簇放置1個MC用于處理簇內(nèi)的充電請求，有利于平衡每個MC的充電負(fù)載，極大減少了用于移動消耗的能量，并使得MC的充電隊列維持在一個較低的水平。

(2)對單個簇研究多目標(biāo)的最優(yōu)實現(xiàn)，提出一種基于時空協(xié)作的多MC實時充電算法STMA。其主要思想是BS為每個MC維持一個動態(tài)隊列實時接收節(jié)點的充電請求，MC結(jié)合節(jié)點的空間位置和截止充電時間要求來決策行進(jìn)路徑，并且每完成一個節(jié)點的充電任務(wù)，MC都要從BS處獲取更新的路由信息，及時調(diào)整充電路徑。這種實時的按需充電的策略使得能量消耗快的節(jié)點的充電請求能夠被提前響應(yīng)，提高了節(jié)點的存活率；并且BS維持的動態(tài)隊列有利于MC及時調(diào)整充電路徑，滿足了節(jié)點實時充電的要求，縮短了隊列長度和充電時延。

4 基于改進(jìn)的聚類算法實現(xiàn)均勻分簇

眾所周知，K-means聚類算法實現(xiàn)簡單，聚類效果好，但其聚類結(jié)果與初始質(zhì)心的選擇有關(guān)，完全隨機(jī)地選擇往往會導(dǎo)致聚類結(jié)果陷入局部最優(yōu)且算法收斂慢，因此本文選擇K-means++算法來優(yōu)化初始質(zhì)心的選擇[14]：

步驟1從給定的數(shù)據(jù)點集合中隨機(jī)選擇一個點作為第1個聚類中心。

步驟2對于數(shù)據(jù)點集合中的每一個點xi，計算它與已知聚類中心的歐氏距離：

D(xi)=argmin‖xi-κj‖2,j=1,2,…,M

(9)

其中，κj為第j個聚類中心，M為聚類數(shù)。

步驟3選擇下一個數(shù)據(jù)點作為新的聚類中心，選擇的原則是：D(xi)較大的點被選取成為新聚類中心的概率較大。

步驟4重復(fù)步驟2和步驟3，直到選擇出M個聚類中心。

步驟5利用選出的M個聚類中心作為質(zhì)心再運行K-means算法。

選擇了M個聚類中心后，就要將剩下的每個數(shù)據(jù)點按照與聚類中心的距離分配給這M個簇。K-means算法的目標(biāo)函數(shù)為：

(10)

其中，Cj表示第j個簇，κCj表示簇Cj的中心點，‖x-κCj‖2表示簇Cj中的數(shù)據(jù)點x和對應(yīng)的中心點κCj之間的歐氏距離。

至此，可以得到大小不一的多個簇，為平衡各個MC的負(fù)載，使得任意一個MC不至于過載而導(dǎo)致網(wǎng)絡(luò)性能變差，接下來實現(xiàn)均勻分簇,具體步驟如下所示：

步驟1找到需要重新分配節(jié)點的簇。

根據(jù)數(shù)據(jù)點總數(shù)N和指定的簇數(shù)M，可求得每個簇中應(yīng)包含的數(shù)據(jù)點數(shù)R：

R=N/M

(11)

找出數(shù)據(jù)點數(shù)大于R的簇Cmore和數(shù)據(jù)點數(shù)小于R的簇Cless，對應(yīng)的簇中心分別是κCmore和κCless。

步驟2對于簇Cmore中的每個數(shù)據(jù)點xi，計算：

dxi,xCless=min(dxi,xCmore-dxi,xCless)

(12)

其中，dxi,xCmore表示數(shù)據(jù)點xi與簇中心κCmore之間的歐氏距離，dxi,xCless表示數(shù)據(jù)點xi與簇中心κCless之間的歐氏距離。找出dxi,xCmore-dxi,xCless最小值對應(yīng)的數(shù)據(jù)點xi加入簇Cless中，直到各個簇的數(shù)據(jù)點數(shù)相等。

根據(jù)上述均勻分簇的思想，將WRSN中的節(jié)點作為數(shù)據(jù)點代入，即可得到節(jié)點數(shù)均勻的K個簇。

5 基于時空協(xié)作的多MC實時充電算法(STMA)

將WRSN公平分簇后，每個簇內(nèi)放置1個MC以響應(yīng)來自該簇內(nèi)節(jié)點的充電請求，然后由BS按照節(jié)點的截止充電時間為MC創(chuàng)建局部充電路由，并為每個MC維護(hù)一個動態(tài)隊列。圖2給出了單個簇內(nèi)，從節(jié)點發(fā)出充電請求，到MC響應(yīng)這些請求的簡單示例。

Figure 2 MC charging example in a single cluster圖2 單個簇內(nèi)MC充電示例

最開始，MC停留在BS中，節(jié)點在自身電量低于閾值ε(ε=EN·30%)時，即產(chǎn)生充電請求Request并轉(zhuǎn)發(fā)至BS，充電請求包含自身當(dāng)前位置Pi(x,y)和截止充電時間Di：

Request=(Pi(x,y),Di)

(13)

Di的計算如式(14)所示：

Di=ei/si

(14)

其中，si是節(jié)點xi消耗能量的速率。

BS在接收到Request后，按照Di的大小存入對應(yīng)MC的充電隊列中，D-表示較小的充電截止時間，D+表示較大的充電截止時間。BS根據(jù)收到的Request為MC創(chuàng)建局部路由，MC在開始一次新的充電任務(wù)前都會等待一個響應(yīng)時間τ，以期望BS做出更為有效的路由決策。MC從隊列首部取出一個Request，首先計算最早到達(dá)該節(jié)點的時間Tr，并與節(jié)點的Di比較，再決定是否前往充電：

(15)

如果MC計算發(fā)現(xiàn)來不及趕在Di到期前到達(dá)該節(jié)點，則應(yīng)轉(zhuǎn)發(fā)至相鄰MC請求幫助，判斷是否為相鄰MC可通過計算2個簇中心的距離distance是否是所有簇間距離最短的：

distance=min(dκCj-1,κCj),1

(16)

BS持續(xù)接收節(jié)點的Request并按照其Di將其加入隊列中，當(dāng)收到較小Di值的Request時，意味著對應(yīng)節(jié)點的能量即將耗盡，需要緊急充電，這種緊急節(jié)點的Request就被插入到隊列的首部，使得MC能夠盡快處理這些緊急請求。MC完成隊列中所有待充電節(jié)點的充電任務(wù)，并且還沒有收到新的Request時，就停留在最后一個充電節(jié)點處，等待新的Request。當(dāng)MC發(fā)現(xiàn)自身電量即將低于從當(dāng)前位置返回BS所需能量時，就返回基站為自己充電，期間收到的Request則轉(zhuǎn)發(fā)給相鄰MC，請求代為完成充電任務(wù)。圖3使用流程圖的形式展示了上述的MC路徑規(guī)劃過程。

Figure 3 Flow chart of MC path planning process圖3 MC路徑規(guī)劃過程流程圖

6 仿真與結(jié)果分析

本文使用Python語言來仿真所提的基于時空協(xié)作的多MC充電路徑規(guī)劃算法，并將仿真結(jié)果分別與mTS算法[6]、DAZ算法[7]和遺傳算法GA[15]的結(jié)果進(jìn)行比較，mTS算法與DAZ算法是目前最新且效果最好的關(guān)于大型WRSNs中多MC充電路徑規(guī)劃的算法，雖也考慮了節(jié)點的時空特征規(guī)劃路徑，但在路由實時更新和充電時限方面欠缺考慮，而GA算法則是經(jīng)典的多MC路徑規(guī)劃算法，都具有強(qiáng)烈的對比性。本文仿真了500個節(jié)點隨機(jī)部署在大小為200×200 m2的傳感區(qū)域中，表1所示為由改進(jìn)的聚類算法將WRSNs分為3,4,5個簇的情況，表2所示為實驗參數(shù)的設(shè)置情況。

圖4展示了MC數(shù)量為3時，本文所提的STMA算法與 mTS算法、DAZ算法和GA算法的節(jié)點存活率對比?？梢姴捎肧TMA算法的節(jié)點在前180 min全部存活，隨著程序運行雖有部分節(jié)點死亡，但還是保持了97%以上的節(jié)點存活率。相比之下，mTS和DAZ的性能相對GA算法雖有較大提升，但最終的存活率在93%左右，而不考慮充電緊急程度的GA算法不僅節(jié)點存活率下降較快，且最終存活率下降到了90%以下。

Table 1 Divided cluster size and the number of corresponding nodes表1 劃分的簇大小和對應(yīng)節(jié)點數(shù)

Table 2 Experimental parameter settings表2 實驗參數(shù)設(shè)置

Figure 4 Comparison of node survival rate圖4 節(jié)點存活率對比

圖5描述了當(dāng)MC數(shù)量分別為3，4和5時，STMA算法分別與mTS、DAZ和GA算法的能量利用率對比?？梢婋S著MC數(shù)量的增加，能量利用率也會有小幅提升，這是因為當(dāng)MC數(shù)量增加時，對于單個MC來說，用于移動的能量減少了，但MC的數(shù)量增加，總的用于移動的能量也增加了；MC數(shù)量為5時，STMA相對于mTS、DAZ和GA算法的能量利用率分別提升了7%，11%和14%，可見在相同MC數(shù)量的情況下，本文算法具有最高的能量利用率。圖6是MC數(shù)量為3時，在算法運行過程中，MC中隊列長度的變化情況，可見STMA算法具有較低水平的隊列長度。圖7則分別對比了MC數(shù)量分別為3,4和5時，STMA算法與mTS、DAZ和GA算法的平均隊列長度，隨著MC數(shù)量的增加，幾種算法的平均隊列長度都明顯縮短了，其中STMA算法在MC數(shù)量為3時已經(jīng)有較好的表現(xiàn)，當(dāng)增加MC數(shù)量時，平均隊列長度下降程度相較其他算法較小，說明在較少MC數(shù)量的情況下，本文算法也有較好的表現(xiàn)。

Figure 5 Comparison of energy utilization圖5 能量利用率對比

Figure 6 Comparison of queue length 圖6 隊列長度對比

Figure 7 Comparison of average queue length圖7 平均隊列長度對比

圖8還給出了隨著算法運行，MC旅行路徑的距離變化情況，旅行路徑距離越小，用于MC移動的能量越少，意味著處理同樣大小區(qū)域的充電請求，本文算法能更有效地滿足節(jié)點需求，且充電時延更小，這對于有實時性要求的WRSNs來說，就大大減少了節(jié)點因充電不及時而陷入休眠的情況。

Figure 8 Comparison of MC travel path length圖8 MC旅行路徑長度對比

7 結(jié)束語

本文針對節(jié)點的實時充電需求，研究了基于時空協(xié)作的多MC充電路徑規(guī)劃方案。所提方案的創(chuàng)新之處在于聯(lián)合考慮了節(jié)點的空間位置和截止充電時間，來決策M(jìn)C的充電路徑，并由此提出一種基于時空協(xié)作的多MC實時充電算法(STMA)。該算法規(guī)定一開始基站為MC創(chuàng)建的是局部路徑，而不是靜態(tài)固定策略，有利于當(dāng)新的充電請求到達(dá)時，及時根據(jù)新請求的緊急程度，動態(tài)調(diào)整MC的充電路徑。與其他幾種先進(jìn)充電算法的仿真結(jié)果對比表明，本文算法在節(jié)點存活率、能量利用率和隊列長度等性能指標(biāo)上表現(xiàn)突出，可以勝任大型WRSNs的實時充電工作。對于未來的研究方向，希望能夠沿用機(jī)器學(xué)習(xí)的思想，利用以往的充電請求數(shù)據(jù)作為數(shù)據(jù)集，加以預(yù)測模型，預(yù)測未來的充電路徑。