聯(lián)合充電和數(shù)據(jù)收集的WCE多目標(biāo)路徑規(guī)劃算法

魏振春，孫仁浩，呂增威，韓江洪，石雷，徐俊逸

?

聯(lián)合充電和數(shù)據(jù)收集的WCE多目標(biāo)路徑規(guī)劃算法

魏振春1,2,3，孫仁浩1，呂增威1，韓江洪1,2,3，石雷1,2,3，徐俊逸1

（1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009；2. 安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，安徽 合肥 230009； 3. 工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009）

在無線可充電傳感器網(wǎng)絡(luò)中的可移動(dòng)的無線充電設(shè)備（WCE，wireless charging equipment）自身攜帶的能量有限的情況下，設(shè)計(jì)了WCE的充電策略和數(shù)據(jù)收集策略，并在此基礎(chǔ)上以最大化WCE總能量的利用率和最小化網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延為目標(biāo)建立了聯(lián)合充電和數(shù)據(jù)收集的WCE多目標(biāo)路徑規(guī)劃模型，提出了一種基于精英策略的多目標(biāo)蟻群優(yōu)化算法，改進(jìn)了螞蟻狀態(tài)轉(zhuǎn)移策略和信息素更新策略，求得了該多目標(biāo)問題的Pareto最優(yōu)解集。以20個(gè)傳感器節(jié)點(diǎn)為例，通過仿真實(shí)驗(yàn)分析了蟻群系統(tǒng)參數(shù)對(duì)ES-MOAC算法的影響，50組對(duì)比實(shí)驗(yàn)表明ES-MOAC算法在求解該問題上得到的能量利用率的平均值比NSGA-II算法增加了4.53%，網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延的平均值比NSGA-II算法縮短了5.12%。

無線可充電傳感器網(wǎng)絡(luò)；聯(lián)合充電和數(shù)據(jù)收集；路徑規(guī)劃；多目標(biāo)蟻群優(yōu)化算法

1 引言

數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)（WSN, wireless sensor network）的核心任務(wù)，而能量問題是該領(lǐng)域研究的熱點(diǎn)問題之一。傳統(tǒng)的WSN中傳感器節(jié)點(diǎn)數(shù)據(jù)傳輸以多跳的方式會(huì)造成“能量空洞”問題[1-2]，距離固定基站較近的傳感器節(jié)點(diǎn)承擔(dān)更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，具有更大的通信負(fù)載，以至于這些節(jié)點(diǎn)因能耗過大而過早死亡，“能量空洞”問題一直是無線傳感器網(wǎng)絡(luò)研究領(lǐng)域中的關(guān)鍵問題。目前，解決該問題的方法主要有3種：1) 采用節(jié)流的思想，即引入移動(dòng)sink節(jié)點(diǎn)節(jié)省傳感器節(jié)點(diǎn)的能量消耗；2) 采用開源的思想，即利用可移動(dòng)的充電設(shè)備為傳感器節(jié)點(diǎn)補(bǔ)充能量；3) 則是結(jié)合節(jié)流和開源的思想，利用可移動(dòng)的無線充電設(shè)備為節(jié)點(diǎn)補(bǔ)充能量，同時(shí)可以收集節(jié)點(diǎn)數(shù)據(jù)。

從節(jié)流的角度來考慮，引入移動(dòng)sink節(jié)點(diǎn)在WSN中游走，移動(dòng)收集傳感器節(jié)點(diǎn)的數(shù)據(jù)，降低了節(jié)點(diǎn)數(shù)據(jù)傳輸過程中的通信負(fù)載，可以有效避免“能量空洞”問題，延長(zhǎng)了網(wǎng)絡(luò)的壽命。文獻(xiàn)[3]提出了一種基于移動(dòng)sink節(jié)點(diǎn)的WSN數(shù)據(jù)采集方案，利用量子遺傳算法求解出遍歷所有采集點(diǎn)的最短回路，均衡了網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的負(fù)載，延長(zhǎng)了網(wǎng)絡(luò)的壽命。文獻(xiàn)[4]設(shè)計(jì)了一種時(shí)延受限的移動(dòng)sink節(jié)點(diǎn)數(shù)據(jù)收集算法，在有限的時(shí)間內(nèi)利用sink節(jié)點(diǎn)的移動(dòng)性來提升WSN的數(shù)據(jù)收集性能，提高了網(wǎng)絡(luò)數(shù)據(jù)的采集量，降低了部分節(jié)點(diǎn)的能耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期。文獻(xiàn)[5]提出了一種基于樹的節(jié)能策略，以減少帶有移動(dòng)sink節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)的能耗，利用移動(dòng)sink節(jié)點(diǎn)收集傳感器節(jié)點(diǎn)的數(shù)據(jù)，平衡了網(wǎng)絡(luò)負(fù)載，降低了傳感器節(jié)點(diǎn)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的壽命。文獻(xiàn)[6]針對(duì)野外環(huán)境下大規(guī)模的無線傳感器網(wǎng)絡(luò)，提出了一種用于移動(dòng)sink節(jié)點(diǎn)的數(shù)據(jù)收集策略以避免靠近固定sink的傳感器節(jié)點(diǎn)比其他節(jié)點(diǎn)能量消耗的更快，有效地解決了“能量空洞”問題，延長(zhǎng)了網(wǎng)絡(luò)的壽命。

從開源角度來考慮，無線充電技術(shù)[7]的引入利用可移動(dòng)的WCE在WSN中游走，通過無線充電的方式為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)補(bǔ)充能量，這種網(wǎng)絡(luò)稱為無線可充電傳感器網(wǎng)絡(luò)（WRSN, wireless rechargeable sensor network）[8]，利用WCE保證網(wǎng)絡(luò)中的節(jié)點(diǎn)不會(huì)因能耗問題而死亡，避免了WSN中的“能量空洞”問題，延長(zhǎng)了網(wǎng)絡(luò)的壽命。文獻(xiàn)[9]認(rèn)為WCE自身攜帶的能量是無限的，證明了WCE采用最短哈密爾頓回路的方式為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)充電可使網(wǎng)絡(luò)生命周期無限延長(zhǎng)，同時(shí)能夠獲得最大的駐站比。文獻(xiàn)[10-11]假設(shè)WCE自身攜帶的能量是無限的，采用按需充電方式為傳感器節(jié)點(diǎn)補(bǔ)充能量，選擇以“最近工作優(yōu)先”為模型，用排隊(duì)論方法求解該充電路徑規(guī)劃問題，保證網(wǎng)絡(luò)不會(huì)因?yàn)楣?jié)點(diǎn)能量不足而停止工作。文獻(xiàn)[12]在WCE自身攜帶能量有限的情況下，提出了一種網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)剩余生命時(shí)間均衡化的充電策略，研究WCE的行駛路徑以及為傳感器節(jié)點(diǎn)充電的時(shí)間，以最小化WCE總能耗的開銷為目標(biāo)，盡量延長(zhǎng)網(wǎng)絡(luò)的壽命。文獻(xiàn)[13]在文獻(xiàn)[12]的基礎(chǔ)上，設(shè)計(jì)了一種WCE能量受限的WRSN周期性充電規(guī)劃策略，在最大化充電周期的同時(shí)最小化WCE總能量的消耗，以保證網(wǎng)絡(luò)永久性地工作下去，利用混沌粒子群算法求解優(yōu)化問題得到WCE充電路徑以及在節(jié)點(diǎn)處的充電時(shí)間。

結(jié)合節(jié)流和開源兩個(gè)角度考慮，目前學(xué)者在這方面的研究還比較少，主要是利用WCE在網(wǎng)絡(luò)中游走為節(jié)點(diǎn)補(bǔ)充能量和收集節(jié)點(diǎn)數(shù)據(jù)，延長(zhǎng)網(wǎng)絡(luò)的壽命，提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)男阅?。文獻(xiàn)[14]利用WCE為節(jié)點(diǎn)補(bǔ)充能量以及收集節(jié)點(diǎn)數(shù)據(jù)，以最大化設(shè)備駐站時(shí)間比為目標(biāo)，保證了網(wǎng)絡(luò)永久運(yùn)作，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)男阅?。文獻(xiàn)[15]提出了一種聯(lián)合移動(dòng)充電和數(shù)據(jù)收集的框架，研究WCE在網(wǎng)絡(luò)中游走的路徑以及充電和數(shù)據(jù)收集的策略，在保證網(wǎng)絡(luò)壽命的前提下，提高網(wǎng)絡(luò)的性能。文獻(xiàn)[16]采用一個(gè)可移動(dòng)的無線充電設(shè)備、多個(gè)數(shù)據(jù)收集裝置為節(jié)點(diǎn)充電以及收集數(shù)據(jù)，提出了基于充電補(bǔ)給和數(shù)據(jù)收集的設(shè)備調(diào)度策略，以平衡網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，降低網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)难訒r(shí)。文獻(xiàn)[17]將可移動(dòng)的WCE既作為移動(dòng)充電設(shè)備，又作為移動(dòng)sink，在為節(jié)點(diǎn)充電的同時(shí)收集數(shù)據(jù)，由移動(dòng)設(shè)備收集數(shù)據(jù)帶回到基站附近再上傳，以最大化傳感器網(wǎng)絡(luò)效用值為目標(biāo)，提出了一種分布式算法，在保證網(wǎng)絡(luò)數(shù)據(jù)正常傳輸?shù)那疤嵯卤M量延長(zhǎng)網(wǎng)絡(luò)的壽命。文獻(xiàn)[18]提出了WCE可為節(jié)點(diǎn)充電以及收集數(shù)據(jù)，在保證數(shù)據(jù)正常傳輸?shù)耐瑫r(shí)，避免固定基站帶來的節(jié)點(diǎn)剩余能量不均衡問題，延長(zhǎng)了網(wǎng)絡(luò)的壽命。在上述的研究中學(xué)者只考慮單目標(biāo)的情況，有些是考慮如何在保證網(wǎng)絡(luò)永久運(yùn)作的前提下提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)男阅埽行┦强紤]如何在保證網(wǎng)絡(luò)數(shù)據(jù)傳輸性能的約束下延長(zhǎng)網(wǎng)絡(luò)壽命，并沒有將兩者綜合考慮。

在前人研究的基礎(chǔ)上，本文研究在聯(lián)合移動(dòng)充電和數(shù)據(jù)收集策略下的WCE多目標(biāo)路經(jīng)規(guī)劃問題，WCE在其攜帶行駛能量和充電能量均有限的情況下，既為傳感器節(jié)點(diǎn)補(bǔ)充能量又收集節(jié)點(diǎn)數(shù)據(jù)，因此，WCE行駛路徑的選擇以及在節(jié)點(diǎn)處充電時(shí)間的多少不僅影響網(wǎng)絡(luò)的壽命，同時(shí)還影響網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)男阅?，這是一個(gè)多目標(biāo)問題。針對(duì)該問題，本文建立了多目標(biāo)WCE路徑規(guī)劃模型，提出了基于精英策略的多目標(biāo)蟻群優(yōu)化算法（ES-MOAC, multi-objective ant colony optimization algorithm based on elitist strategy），最終求得該問題的Pareto最優(yōu)解集。本文的貢獻(xiàn)如下。

1) 首次建立了聯(lián)合移動(dòng)充電和數(shù)據(jù)收集策略下的以最大化WCE總能量的利用率和最小化網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延為目標(biāo)的WCE路徑規(guī)劃模型，分析了WCE行駛路徑的選擇以及在節(jié)點(diǎn)處的充電時(shí)間對(duì)上述2個(gè)目標(biāo)的影響。

2) 首次通過多目標(biāo)優(yōu)化算法解決WCE路徑規(guī)劃問題，提出了一種基于精英策略的多目標(biāo)蟻群優(yōu)化算法，設(shè)計(jì)了螞蟻狀態(tài)轉(zhuǎn)移策略和信息素更新策略。

2 網(wǎng)絡(luò)結(jié)構(gòu)和問題描述

2.1 WRSN的結(jié)構(gòu)

在一個(gè)被監(jiān)測(cè)區(qū)域D內(nèi)部署有無線可充電傳感器網(wǎng)絡(luò)，該網(wǎng)絡(luò)具有如下性質(zhì)。

4) 網(wǎng)絡(luò)中有一個(gè)服務(wù)站S，該服務(wù)站S是WCE在執(zhí)行完充電和數(shù)據(jù)收集任務(wù)后，為其提供能量補(bǔ)給和停留的場(chǎng)所。

具有上述性質(zhì)的無線可充電傳感器網(wǎng)絡(luò)模型如圖1所示。

圖1 帶有移動(dòng)WCE的無線可充電傳感器網(wǎng)絡(luò)示意

2.2 問題的描述

本文研究的問題是聯(lián)合充電和數(shù)據(jù)收集下的WCE多目標(biāo)路徑規(guī)劃問題，其中，WCE的初始行駛能量和充電能量是分開且有限的，因此在設(shè)計(jì)WCE的路徑規(guī)劃時(shí)需要考慮以下幾點(diǎn)。

1) 由于WCE的行駛能量是有限的，而且網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)分布是稀疏的，WCE不一定能在一個(gè)哈密爾頓回路中遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)，如何設(shè)計(jì)和規(guī)劃WCE的行駛路徑使其遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)是本文研究的問題之一。

2) 由于WCE的充電能量是有限的，WCE不能保證網(wǎng)絡(luò)永久運(yùn)作，設(shè)計(jì)什么樣的充電策略以延長(zhǎng)網(wǎng)絡(luò)的壽命是十分重要的。

3) 考慮到WCE不僅為節(jié)點(diǎn)充電，還對(duì)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)收集，因此，WCE的行駛路徑的選擇以及WCE在節(jié)點(diǎn)處充電時(shí)間的多少既影響網(wǎng)絡(luò)的壽命，又影響網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男阅?，這是一個(gè)多目標(biāo)問題。

在建立和分析WCE多目標(biāo)路徑規(guī)劃模型之前，先給出以下2個(gè)定義。

圖2 WCE在一個(gè)工作周期內(nèi)經(jīng)過多個(gè)工作輪的行駛路徑示意

由于WCE在服務(wù)站S中的能量補(bǔ)給是通過更換電池實(shí)現(xiàn)的，可以瞬時(shí)完成，故WCE在服務(wù)站S進(jìn)行能量補(bǔ)給的時(shí)間可以忽略不計(jì)。因此，一個(gè)工作周期僅由若干個(gè)工作輪組成。

3 模型的建立

3.1 WCE的行駛路徑和工作周期

3.2 WCE的充電模型

3.3 WCE的充電策略

為了盡量延長(zhǎng)網(wǎng)絡(luò)的壽命，本文設(shè)計(jì)了一種能量均衡化的充電策略。該策略利用WCE選擇合適的節(jié)點(diǎn)進(jìn)行充電，均衡網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的剩余生命時(shí)間，使節(jié)點(diǎn)的剩余生命時(shí)間不為0且方差最小，方差最小意味著節(jié)點(diǎn)的剩余生命時(shí)間趨于某個(gè)值，平均剩余生命時(shí)間均衡化。

3.4 WCE的數(shù)據(jù)收集策略

WCE在網(wǎng)絡(luò)中不僅為傳感器節(jié)點(diǎn)補(bǔ)充能量，還可以收集節(jié)點(diǎn)數(shù)據(jù)，所以在WCE的路徑規(guī)劃的過程中還要考慮網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)臅r(shí)延，盡量降低其時(shí)延，保證網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)男阅堋?/p>

3.5 多目標(biāo)優(yōu)化問題模型

根據(jù)上面的描述可知WCE工作的時(shí)間軸如圖3所示，其中，包括WCE的駐站時(shí)間和工作周期。

圖3 WCE為WRSN服務(wù)的時(shí)間軸的示意

s.t.式(2), 式(4), 式(6)~式(8), 式(13)~式(16), 式(18)

4 基于精英策略的多目標(biāo)蟻群優(yōu)化算法

在WCE充電策略和數(shù)據(jù)收集策略的條件下，本文提出的多目標(biāo)優(yōu)化問題模型實(shí)際上是求解WCE的路徑規(guī)劃，即WCE的行駛路徑以及WCE在節(jié)點(diǎn)處的充電時(shí)間，這是一個(gè)NP-hard問題。根據(jù)文獻(xiàn)[12]可知，蟻群算法模擬了自然界中螞蟻的覓食行為，是尋找最優(yōu)路徑的一種元啟發(fā)式優(yōu)化算法，相比于粒子群算法、遺傳算法等優(yōu)化算法，蟻群算法更適合解決路徑規(guī)劃問題。因此，本文采用蟻群優(yōu)化算法進(jìn)行求解，提出了一種基于精英策略的多目標(biāo)蟻群優(yōu)化算法ES-MOAC。

在ES-MOAC算法的設(shè)計(jì)中需要對(duì)螞蟻狀態(tài)轉(zhuǎn)移策略和信息素更新策略進(jìn)行設(shè)計(jì)。在螞蟻狀態(tài)轉(zhuǎn)移策略的設(shè)計(jì)中，當(dāng)符合判斷條件時(shí)，算法采用考慮信息素濃度、節(jié)點(diǎn)之間的距離以及節(jié)點(diǎn)的剩余生命時(shí)間等因素影響下確定螞蟻狀態(tài)轉(zhuǎn)移策略；否則采用隨機(jī)性螞蟻狀態(tài)轉(zhuǎn)移策略隨機(jī)選擇一個(gè)未被訪問的傳感器節(jié)點(diǎn)，避免了ES-MOAC算法陷入局部最優(yōu)。在信息素更新策略設(shè)計(jì)中，采用全局信息素更新策略，本輪的信息素是根據(jù)上一輪的信息素?fù)]發(fā)之后殘留的信息素和計(jì)算多目標(biāo)優(yōu)化問題求得的Pareto解集對(duì)應(yīng)的精英螞蟻在路徑上產(chǎn)生新的信息素進(jìn)行更改的，該策略是一種改進(jìn)的精英策略，對(duì)于求得本問題的Pareto最優(yōu)解集以及WCE行駛路徑的選擇具有引導(dǎo)作用。

4.1 螞蟻狀態(tài)轉(zhuǎn)移策略

4.2 信息素更新策略

4.3 算法描述

基于上述改進(jìn)的螞蟻狀態(tài)轉(zhuǎn)移策略和信息素更新策略，在一個(gè)工作周期內(nèi)，利用基于精英策略的多目標(biāo)蟻群優(yōu)化算法可以求得本文多目標(biāo)路徑規(guī)劃問題的Pareto最優(yōu)解集和每個(gè)解對(duì)應(yīng)的WCE的行駛路徑以及WCE在節(jié)點(diǎn)處的充電時(shí)間，ES-MOAC算法的具體步驟如下。

算法1 ES-MOAC算法

輸入 網(wǎng)絡(luò)基本參數(shù), 充電系統(tǒng)和螞蟻系統(tǒng)相關(guān)參數(shù)。

輸出 Pareto最優(yōu)解集和每個(gè)解對(duì)應(yīng)WCE的行駛路徑以及WCE在傳感器節(jié)點(diǎn)處的充電時(shí)間。

9) end

10) 根據(jù)信息素更新策略對(duì)應(yīng)的式(20)和式(21)對(duì)信息素濃度進(jìn)行更新。

12) end

5 仿真實(shí)驗(yàn)

5.1 螞蟻系統(tǒng)參數(shù)對(duì)ES-MOAC算法的影響

實(shí)驗(yàn)結(jié)果表明，算法至少執(zhí)行120次之后，Pareto最優(yōu)解的個(gè)數(shù)的平均值才趨于某一個(gè)定值，曲線開始收斂。螞蟻個(gè)數(shù)大于或等于15時(shí)，螞蟻個(gè)數(shù)對(duì)本算法的結(jié)果影響很小。

圖4 不同螞蟻個(gè)數(shù)下本文算法Pareto最優(yōu)解的個(gè)數(shù)隨迭代次數(shù)的影響

圖5 螞蟻狀態(tài)轉(zhuǎn)移策略中選擇因子q0的取值對(duì)本算法的影響

5.2 ES-MOAC算法求解本問題的結(jié)果與分析

表1 20個(gè)傳感器節(jié)點(diǎn)的位置坐標(biāo)

圖6 信息素更新策略中信息素?fù)]發(fā)系數(shù)的取值對(duì)本算法的影響

從圖7中可以看出，ES-MOAC算法求解本問題能很好地逼近Pareto前沿，當(dāng)算法迭代150次時(shí)，能夠得到本問題的Pareto前沿。其中，WCE總能量的利用率最高和網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延最低這2個(gè)解對(duì)應(yīng)的WCE在一個(gè)工作周期的多輪能量開銷如表2和表3所示，0代表的是服務(wù)站S。對(duì)比表2和表3可知，在一個(gè)周期內(nèi)網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延最低的解對(duì)應(yīng)的工作輪數(shù)小于WCE總能量的利用率最高的解的工作輪數(shù)，這意味著WCE在路上的行駛時(shí)間較少，網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延較低。WCE總能量的利用率最高的解的工作輪數(shù)雖然較高，能量的開銷大，一個(gè)工作周期花費(fèi)的時(shí)間長(zhǎng)，但為了均衡化網(wǎng)絡(luò)中節(jié)點(diǎn)的能量，充電能量的開銷較多，總能量的利用率高。

圖7 ES-MOAC算法求解本問題在不同迭代次數(shù)下的Pareto前沿

表2 WCE完成一個(gè)工作周期的多輪能量開銷（WCE總能量的利用率最高的解）

表3 WCE完成一個(gè)工作周期的多輪能量開銷（數(shù)據(jù)傳輸?shù)钠骄鶗r(shí)延最低的解）

5.3 ES-MOAC算法與NSGA-II算法的比較

圖8 ES-MOAC算法和NSGA-II算法的Pareto前沿對(duì)比

在多目標(biāo)優(yōu)化分析中，除了分析算法的收斂性，還需要對(duì)算法的多樣性進(jìn)行分析，算法多樣性的分析主要考慮以下幾個(gè)指標(biāo)。

表4 20個(gè)節(jié)點(diǎn)下ES-MOAC算法和NSGA-II算法計(jì)算結(jié)果比較

圖9 ES-MOAC算法和NSGA-II算法關(guān)于指標(biāo)統(tǒng)計(jì)值的盒狀圖

表5 50個(gè)節(jié)點(diǎn)下ES-MOAC算法和NSGA-II算法計(jì)算結(jié)果比較

6 結(jié)束語

在WCE的行駛能量和充電能量分開且有限的非理想情況下，本文首次提出了聯(lián)合充電和數(shù)據(jù)收集的多目標(biāo)路徑規(guī)劃模型，在保證了網(wǎng)絡(luò)中能量均衡化以及盡量延長(zhǎng)網(wǎng)絡(luò)壽命的前提下，本文給出了WCE充電路徑的構(gòu)造規(guī)則，以最大化WCE總能量的利用率為目標(biāo)，同時(shí)，WCE可以收集節(jié)點(diǎn)數(shù)據(jù)，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均數(shù)據(jù)傳輸時(shí)延作為另一個(gè)優(yōu)化目標(biāo)，提高網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男阅?。本文提出了一種基于精英策略的多目標(biāo)蟻群算法ES-MOAC，設(shè)計(jì)了算法的螞蟻狀態(tài)轉(zhuǎn)移策略和信息素更新策略，求得了該問題的Pareto最優(yōu)解集。通過實(shí)驗(yàn)分析了螞蟻系統(tǒng)中最大迭代次數(shù)、螞蟻個(gè)數(shù)、螞蟻狀態(tài)轉(zhuǎn)移策略中選擇因子和信息素更新策略中信息素?fù)]發(fā)系數(shù)等參數(shù)對(duì)本算法的影響。進(jìn)行實(shí)驗(yàn)仿真，針對(duì)ES-MOAC算法求解本問題的結(jié)果進(jìn)行分析，驗(yàn)證了模型的正確性。在同等條件下，本文針對(duì)ES-MOAC算法與NSGA-II算法做了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明了本文算法的優(yōu)越性。

本文研究的無線可充電傳感器網(wǎng)絡(luò)覆蓋范圍內(nèi)只存在單個(gè)可移動(dòng)的WCE。然而，在某些特殊環(huán)境下，單個(gè)WCE無法完成任務(wù)時(shí)，如何安排和調(diào)度多個(gè)WCE協(xié)同工作還有待進(jìn)一步研究。另外，該網(wǎng)絡(luò)中可能存在瓶頸節(jié)點(diǎn)，瓶頸節(jié)點(diǎn)的存在并不利于網(wǎng)絡(luò)的穩(wěn)定工作，能否通過提高WCE對(duì)這種節(jié)點(diǎn)進(jìn)行能量補(bǔ)充的頻率從而消除瓶頸節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響，也亟待研究。

[1] LIAN J, NAIK K, AGNEW G B. Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J]. International Journal of Distributed Sensor Networks, 2006, 2(2): 121-145.

[2] OLARIU S, STOJMENOVIC I. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting[C]//IEEE International Conference on Computer Communications. 2006: 2505-2516.

[3] 郭劍, 孫力娟, 許文君, 等. 基于移動(dòng)sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案[J]. 通信學(xué)報(bào), 2012, 33(9): 176-184.

GUO J, SUN L J, XU W J, et al. Mobile sink-based data collection scheme for wireless sensor networks[J]. Journal on Communications, 2012, 33(9): 176-184.

[4] 盧先領(lǐng), 王瑩瑩. 時(shí)延受限的移動(dòng)sink數(shù)據(jù)收集算法[J]. 通信學(xué)報(bào), 2014, 35(10): 107-116.

LU X L, WANG Y Y. Data collection algorithm for mobile sink in delay-constrained network[J]. Journal on Communications, 2014, 35(10): 107-116.

[5] CHANG J Y, SHEN T H. An efficient tree-based power saving scheme for wireless sensor networks with mobile sink[J]. IEEE Sensors Journal, 2016, 16(20): 7545-7557.

[6] IWATA M, TANG S H, OBANA S. Sink-based centralized transmission scheduling by using asymmetric communication and wake-up radio[C]//IEEE Wireless Communications and Networking Conference. 2017: 1-6.

[7] XIE L G, SHI Y, HOU Y T, et al. Wireless power transfer and applications to sensor networks[J]. Wireless Communications, 2013, 20(4): 140-145.

[8] YANG Y Y, WANG C. Wireless rechargeable sensor networks[M]. Heidelberg: Springer-Verlag, 2015.

[9] SHI Y, XIE L G, HOU Y T, et al. On renewable sensor networks with wireless energy transfer[C]//IEEE International Conference on Computer Communications. 2012: 1350-1358.

[10] HE L, GU Y, PAN J P, et al. On-demand charging in wireless sensor networks: theories and applications[C]//International Conference on Mobile Ad-Hoc and Sensor Systems. 2013: 28-36.

[11] HE L, KONG L H, GU Y, et al. Evaluating the on-demand mobile charging in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(9): 1861-1875.

[12] XU J Y, YUAN X H, WEI Z C, et al. A wireless sensor network recharging strategy by balancing lifespan of sensor nodes[C]//IEEE Wireless Communications and Networking Conference. 2017: 1-6.

[13] 陳花, 魏振春, 韓江洪, 等. 無線充電設(shè)備能量受限的WRSNs周期性充電規(guī)劃[J]. 電子測(cè)量與儀器學(xué)報(bào), 2017, 31(7): 1031-1039.

CHENG H, WEI Z C, HAN J H, et al. Periodic charging strategy of energy-constrained wireless charging equipment in WRSNs[J]. Journal of Electronic Measurement and Instrumentation, 2017, 31(7): 1031-1039.

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

DING X, HAN J H, SHI L, et al. Problem of the dynamic topology architecture of rechargeable wireless sensor networks[J]. Journal on Communications, 2015, 36(1): 133-145.

[15]XIE L, SHI Y, HOU Y T, et al. A mobile platform for wireless charging and data collection in sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(8): 1521-1533.

[16] WANG C, LI J, YE F, et al. A mobile data gathering framework for wireless rechargeable sensor networks with vehicle movement costs and capacity constraints[J]. IEEE Transactions on Computers, 2016, 65(8): 2411-2427.

[17] GUO S T, WANG C, YANG Y Y. Mobile data gathering with wireless energy replenishment in rechargeable sensor networks[C]//IEEE International Conference on Computer Communications. 2013: 1932-1940.

[18]ZHAO M, LI J, YANG Y Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(12): 2689-2705.

[19]DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

Path planning algorithm for WCE with joint energy replenishment and data collection based on multi-objective optimization

WEI Zhenchun1,2,3, SUN Renhao1, LYU Zengwei1, HAN Jianghong1,2,3, SHI Lei1,2,3, XU Junyi1

1. School of Computer and Information, Hefei University of Technology, Hefei 230009, China 2. Engineering Research Center of Safety-Critical Industry Measure and Control Technology of Ministry of Education, Hefei 230009, China 3. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei 230009, China

Considering limited energy of the wireless charging equipment (WCE) in wireless rechargeable sensor network, an energy replenishment strategy and a data collection strategy are designed. On the basis of these, a path planning model for WCE with functions of joint energy replenishment and data collection based on multi-objective optimization is constructed with two optimization objectives, maximizing the total energy utility of WCE and minimizing the average delay of data transmission of all the sensor nodes in the network. To deal with it, a multi-objective ant colony optimization algorithm based on elitist strategy was proposed, where the state transition strategy and the pheromone updating strategy were improved. Then, the Pareto set was obtained in terms of this multi-objective optimization problem. The parameter setting of ant colony algorithm’s effects on the proposed algorithm were analyzed under 20 sensor nodes. 50 groups of contrastive experiments show that the average number of energy utilization obtained by ES-MOAC algorithm is 4.53% higher than that of NSGA-II algorithm. The average number of average delay of all node data transmission obtained by ES-MOAC algorithm is 5.12% lower than that of NSGA-II algorithm.

wireless rechargeable sensor network, joint energy replenishment and data collection, path planning, multi-objective ant colony optimization algorithm

TP393

A

10.11959/j.issn.1000?436x.2018216

魏振春（1978?），男，寧夏青銅峽人，博士，合肥工業(yè)大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)槲锫?lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)、智能計(jì)算。

孫仁浩（1992?），男，吉林扶余人，合肥工業(yè)大學(xué)碩士生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、智能優(yōu)化算法。

呂增威（1989?），男，山東煙臺(tái)人，合肥工業(yè)大學(xué)博士生，主要研究方向?yàn)槲锫?lián)網(wǎng)、智能計(jì)算、機(jī)器學(xué)習(xí)。

韓江洪（1954?），男，江蘇南京人，合肥工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)控制、物聯(lián)網(wǎng)、無線網(wǎng)絡(luò)。

石雷（1980?），男，安徽合肥人，博士，合肥工業(yè)大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)闊o線網(wǎng)絡(luò)、干擾管理。

徐俊逸（1990?），男，江蘇常州人，合肥工業(yè)大學(xué)博士生，主要研究方向?yàn)槲锫?lián)網(wǎng)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化。

2017?11?06；

2018?08?22

石雷，thunder10@163.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61502142, No.61501161, No.61370088）

The National Natural Science Foundation of China (No.61502142, No.61501161, No.61370088)