尹 玲，謝志軍

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

1 引言

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

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

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

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

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

2 相關(guān)工作

當(dāng)前關(guān)于WRSNs中MC的充電路徑規(guī)劃的研究工作一般可細(xì)分為4類：?jiǎn)蜯C離線調(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行程，實(shí)現(xiàn)簡(jiǎn)單但靈活性低；在線(On-line)調(diào)度方法則側(cè)重于為節(jié)點(diǎn)按需充電，以較低的充電代價(jià)達(dá)到較高的網(wǎng)絡(luò)效用。

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

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

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

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

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

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

Figure 1 WRSN model with 3 MCs圖1 含有3個(gè)MC的WRSN模型

3.1 問(wèn)題描述

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

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

3.2 解決方案

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

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

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

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

(1)

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

(2)

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

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

對(duì)于整個(gè)WRSN來(lái)說(shuō)，每個(gè)節(jié)點(diǎn)都發(fā)揮著各自的作用，因此要保證節(jié)點(diǎn)存活率δ最高：

maxδ=Nlive/N

(3)

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

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

(4)

其中，α和β是加權(quán)因子，分別表示能量目標(biāo)和存活率目標(biāo)對(duì)于總體目標(biāo)的權(quán)重。由于較高的能量利用率代表了更多的能量用于為節(jié)點(diǎn)充電，更少的能量用于MC移動(dòng)，而MC移動(dòng)較少的路徑就能將更多的能量提供給節(jié)點(diǎn)充電，其實(shí)這2個(gè)目標(biāo)是正相關(guān)的關(guān)系，難以區(qū)分哪一個(gè)目標(biāo)對(duì)整體目標(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交換信息所耗費(fèi)的能量，可忽略不計(jì)。

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

(7)

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

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

(8)

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

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

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

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

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

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

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

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

(9)

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

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

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

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

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

(10)

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

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

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

根據(jù)數(shù)據(jù)點(diǎn)總數(shù)N和指定的簇?cái)?shù)M，可求得每個(gè)簇中應(yīng)包含的數(shù)據(jù)點(diǎn)數(shù)R：

R=N/M

(11)

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

步驟2對(duì)于簇Cmore中的每個(gè)數(shù)據(jù)點(diǎn)xi，計(jì)算：

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

(12)

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

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

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

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

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

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

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

(13)

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

Di=ei/si

(14)

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

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

(15)

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

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

(16)

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

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

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

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

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

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

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

Figure 4 Comparison of node survival rate圖4 節(jié)點(diǎn)存活率對(duì)比

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

Figure 5 Comparison of energy utilization圖5 能量利用率對(duì)比

Figure 6 Comparison of queue length 圖6 隊(duì)列長(zhǎng)度對(duì)比

Figure 7 Comparison of average queue length圖7 平均隊(duì)列長(zhǎng)度對(duì)比

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

Figure 8 Comparison of MC travel path length圖8 MC旅行路徑長(zhǎng)度對(duì)比

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

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