帶時(shí)間窗的無線可充電傳感器網(wǎng)絡(luò)多目標(biāo)路徑規(guī)劃算法

魏振春，傅 宇，馬仲軍，呂增威，石 雷，張本宏

（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）

1 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）在軍事、環(huán)境監(jiān)測(cè)、醫(yī)療監(jiān)管、智能家庭等領(lǐng)域都有廣泛應(yīng)用.目前的無線傳感器網(wǎng)絡(luò)普遍采用多跳拓?fù)洌?］，該拓?fù)浜苋菀讓?dǎo)致網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)死亡，從而造成能量空洞問題［2］.

為了解決能量空洞問題，前人做了大量的相關(guān)研究.主要研究方向包括：（1）環(huán)境能量收集；（2）傳感器節(jié)點(diǎn)節(jié)能控制；（3）無線設(shè)備能源補(bǔ)充.環(huán)境能量收集這種方法極度依賴環(huán)境，穩(wěn)定性要求較高，并且能量轉(zhuǎn)換率不高.傳感器節(jié)點(diǎn)節(jié)能控制主要是通過改造節(jié)點(diǎn)的硬件構(gòu)造和優(yōu)化能源分配［3］來延長節(jié)點(diǎn)壽命，但這仍然是一種較為被動(dòng)的方案，還是無法從根本上解決節(jié)點(diǎn)能量不足的問題.隨著Kurs 等人［4］提出強(qiáng)耦合磁共振充電技術(shù)，越來越多的人開始研究無線可充電傳感器網(wǎng)絡(luò)（Wireless Rechargeable Sensor Networks，WRSNs）.與傳統(tǒng)能量收集方案相比，WRSNs 可以很好地保持節(jié)點(diǎn)活躍性，并且更加靈活地控制節(jié)點(diǎn)的能量補(bǔ)充過程，極大地提高網(wǎng)絡(luò)壽命［5］.

目前針對(duì)WRSN 的研究大都是采用周期性充電方案.周期性充電是讓無線充電設(shè)備（Wireless Charging Equipment，WCE）在每個(gè)充電調(diào)度內(nèi)按照固定的充電順序、充電時(shí)間對(duì)節(jié)點(diǎn)進(jìn)行充電.周期性充電方案效率較低，加重了WCE 的工作負(fù)擔(dān).按需充電是依據(jù)節(jié)點(diǎn)的充電需求對(duì)節(jié)點(diǎn)進(jìn)行充電，有利于提高充電效率，降低WCE 的負(fù)擔(dān).但按需充電可能導(dǎo)致部分節(jié)點(diǎn)充電有較大的等待時(shí)延.另外，現(xiàn)有的WRSN 充電規(guī)劃方案往往只考慮單一的優(yōu)化目標(biāo)，沒有考慮網(wǎng)絡(luò)的整體性能.針對(duì)以上問題，本文基于時(shí)間窗模型，提出了一種多目標(biāo)充電路徑規(guī)劃方案，主要貢獻(xiàn)包括以下幾方面：

（1）引入時(shí)間窗模型，通過懲罰函數(shù)盡可能保證在合適時(shí)間對(duì)節(jié)點(diǎn)進(jìn)行充電，避免按需充電的方式使部分節(jié)點(diǎn)充電等待時(shí)間過長；

（2）設(shè)計(jì)最大化WCE 能量利用率和最小化懲罰函數(shù)值的多目標(biāo)路徑規(guī)劃方案，提高網(wǎng)絡(luò)的整體性能；

（3）基于多目標(biāo)連續(xù)煙花算法，提出多目標(biāo)離散煙花算法求解多目標(biāo)路徑規(guī)劃問題.

2 相關(guān)工作

WRSN出現(xiàn)以前，學(xué)者們對(duì)傳感器節(jié)點(diǎn)能量補(bǔ)充的研究也做出了重大努力.Jiang 等人［6］提出利用光伏電力系統(tǒng)對(duì)網(wǎng)絡(luò)中的超低功率無線傳感器節(jié)點(diǎn)進(jìn)行充電，來確保網(wǎng)絡(luò)的可持續(xù)運(yùn)行.Kansal 等人［7］則在前者的基礎(chǔ)上增加了能源管理策略，進(jìn)一步提高了網(wǎng)絡(luò)的穩(wěn)定性.Han等人［8］研究了隨機(jī)環(huán)境下冗余部署的無線可充電傳感器網(wǎng)絡(luò)，提出了一種運(yùn)行狀態(tài)調(diào)度算法，但是這種算法極度依賴環(huán)境.隨著傳感器網(wǎng)絡(luò)的發(fā)展，節(jié)點(diǎn)耗電量逐漸增加，傳統(tǒng)的能量補(bǔ)充方式已經(jīng)很難適用于不斷發(fā)展的能量需求.

Lin等人［9］指出傳感器節(jié)點(diǎn)接收能量還與節(jié)點(diǎn)和充電器的定向角度相關(guān)，并提出基于磁共振耦合的周期性充電規(guī)劃，該充電規(guī)劃可以無限延長傳感器網(wǎng)絡(luò)周期壽命.文獻(xiàn)［10］通過六邊形網(wǎng)格劃分區(qū)域，提出一種基于節(jié)點(diǎn)分層的均衡式路由策略，設(shè)計(jì)了一種移動(dòng)無線射頻小車充電時(shí)間分配的高效算法.Fu 等人［11］則將充電區(qū)域進(jìn)行圓形區(qū)域劃分，引入元啟發(fā)式算法規(guī)劃充電路徑，并通過動(dòng)態(tài)調(diào)整充電功率，最小化充電總延遲，最后證明了該方案比傳統(tǒng)充電方案具有更低的搜索復(fù)雜度.然而周期性充電方案并不適合劃分區(qū)域的動(dòng)態(tài)變化網(wǎng)絡(luò).還有一些周期性充電方案在充電的同時(shí)進(jìn)行數(shù)據(jù)收集.Sha等人［12］在網(wǎng)絡(luò)模型中考慮了移動(dòng)充電車輛和移動(dòng)數(shù)據(jù)收集車輛兩種移動(dòng)設(shè)備，設(shè)計(jì)了一種分布式的周期性充電方案，將最大化充電收益作為優(yōu)化目標(biāo)，并提出了PDESM 算法求解問題.Wu 等人［13］在設(shè)計(jì)移動(dòng)設(shè)備給傳感器網(wǎng)絡(luò)無線充電的同時(shí)，考慮了多個(gè)傳感器節(jié)點(diǎn)進(jìn)行協(xié)作數(shù)據(jù)收集任務(wù)時(shí)的充電低效情況，提出了一種近似算法，以最大化整個(gè)網(wǎng)絡(luò)的任務(wù)執(zhí)行效用.隨著人工智能算法的興起，文獻(xiàn)［14，15］將強(qiáng)化學(xué)習(xí)算法引入無線周期性充電路徑規(guī)劃領(lǐng)域來解決路徑優(yōu)化問題.

按需充電不同于傳統(tǒng)周期性充電規(guī)劃，WCE 會(huì)根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)能量情況以及數(shù)據(jù)收集需求進(jìn)行動(dòng)態(tài)調(diào)整規(guī)劃線路，以最大化網(wǎng)絡(luò)效用.Lin 等人［16］設(shè)計(jì)了一種基于時(shí)間和距離優(yōu)先級(jí)混合聚類充電算法（HCCA），通過構(gòu)建基于最小連通支配集的骨干網(wǎng)絡(luò)，利用k-means 聚類算法將節(jié)點(diǎn)分簇，證明可以有效減少充電時(shí)延，提高網(wǎng)絡(luò)性能.Lin 等人［17］考慮充電請(qǐng)求過程中時(shí)間約束和空間約束的不平衡問題，設(shè)置雙重警告閾值，通過調(diào)整不同節(jié)點(diǎn)的充電優(yōu)先級(jí)且支持搶先調(diào)度的方法最小化平均等待時(shí)間.Dai等人［18］設(shè)計(jì)了聯(lián)合充電和調(diào)度方案，以最大限度地提高隨機(jī)事件的監(jiān)控質(zhì)量，并將充電規(guī)劃問題描述為CHASE-R問題，利用近似算法得到了較好的效果.文獻(xiàn)［19］提出了一種基于多節(jié)點(diǎn)充電模型的按需順帶充電方案，該方案在對(duì)請(qǐng)求節(jié)點(diǎn)充電時(shí)考慮對(duì)非請(qǐng)求節(jié)點(diǎn)順帶充電，最后仿真結(jié)果證明該按需充電的方案可以提高充電能效.但以上按需充電方案考慮的都是單目標(biāo)優(yōu)化，忽略了網(wǎng)絡(luò)的整體性能.

3 系統(tǒng)模型

3.1 問題描述

WCE 在網(wǎng)絡(luò)游走過程中一方面進(jìn)行能量補(bǔ)充，另一方面負(fù)責(zé)通訊，因此需要綜合考慮以下兩點(diǎn).

（1）WCE 在同一個(gè)充電回路內(nèi)僅訪問網(wǎng)絡(luò)內(nèi)任何一個(gè)傳感器節(jié)點(diǎn)一次，而且WCE 攜帶的行駛能量足以完成一個(gè)Hamilton 回路的行駛.WCE 行駛完一個(gè)Hamilton回路后，返回服務(wù)站進(jìn)行能量補(bǔ)充和數(shù)據(jù)上傳.

（2）WCE 在對(duì)傳感器節(jié)點(diǎn)進(jìn)行能量補(bǔ)充時(shí)，并非當(dāng)節(jié)點(diǎn)能量低于節(jié)點(diǎn)充電容量最大值時(shí)就立刻對(duì)節(jié)點(diǎn)進(jìn)行充電，而是依據(jù)充電能量上限和充電能量下限給出充電時(shí)間窗，只有在時(shí)間窗內(nèi)充電時(shí)才不會(huì)產(chǎn)生懲罰值.

針對(duì)以上兩點(diǎn)，本文研究傳感器網(wǎng)絡(luò)中采用無線能量補(bǔ)充的充電路徑規(guī)劃問題，確定WCE 的充電路徑以及在每個(gè)傳感器節(jié)點(diǎn)處的充電時(shí)間，使得網(wǎng)絡(luò)獲得的整體性能最佳.

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

如圖1 所示，無線可充電傳感器網(wǎng)絡(luò)隨機(jī)部署在二維區(qū)域內(nèi)，其中包含：n個(gè)無線傳感器節(jié)點(diǎn)、1個(gè)固定Sink 基站B、1 個(gè)固定的充電服務(wù)站S、1 個(gè)移動(dòng)充電設(shè)備WCE.WCE 在網(wǎng)絡(luò)中移動(dòng)，對(duì)傳感器節(jié)點(diǎn)進(jìn)行能量補(bǔ)充.傳感器節(jié)點(diǎn)的集合記為Π={s1，s2，…，si，…，sn，i∈Z}，其中si為第i個(gè)傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)既能進(jìn)行數(shù)據(jù)收發(fā)，也能接收無線充電設(shè)備的能量補(bǔ)充，并且每個(gè)傳感器節(jié)點(diǎn)的電池最大容量均為Emax.假設(shè)網(wǎng)絡(luò)初始時(shí)刻所有傳感器節(jié)點(diǎn)的電量均為最大值，當(dāng)傳感器節(jié)點(diǎn)的電量低于Emin時(shí)不能夠正常工作.本網(wǎng)絡(luò)模型中，WCE 從服務(wù)站S出發(fā)，平均以速度v在網(wǎng)絡(luò)中移動(dòng)，途經(jīng)部分傳感器節(jié)點(diǎn)并對(duì)節(jié)點(diǎn)進(jìn)行充電，充電的功率為U，最后回到服務(wù)站補(bǔ)充能量并等待下一個(gè)充電任務(wù)開始.需要說明的是，WCE 攜帶的能量分為兩部分，一部分為行駛能量，另一部分為用于為節(jié)點(diǎn)充電的能量，移動(dòng)能量和充電能量的最大容量分別為EM和EC.

圖1 網(wǎng)絡(luò)模型示意圖

本文所用到的相關(guān)符號(hào)見表1.

表1 本文的符號(hào)及含義

4 充電模型與充電規(guī)劃

4.1 WCE的能量模型及充電模型

系統(tǒng)充電流程時(shí)間組成如圖2所示.

圖2 系統(tǒng)充電流程時(shí)間組成示意圖

定義1充電輪.若在一段時(shí)間內(nèi)，WCE 從服務(wù)站S出發(fā)經(jīng)過部分傳感器節(jié)點(diǎn)并為這些節(jié)點(diǎn)補(bǔ)充電量后回到服務(wù)站，且這段時(shí)間內(nèi)任意時(shí)刻WCE 所經(jīng)過的傳感器節(jié)點(diǎn)剩余能量均大于Emin，稱這段時(shí)間為一個(gè)充電輪，記為Rq(q∈Z).

定義2充電間隔.WCE 完成一個(gè)充電輪之后，返回到服務(wù)站S，在服務(wù)站S停留的時(shí)間即為充電間隔，也就是駐站時(shí)間，記為lq(q∈Z).

定義3充電調(diào)度.若在一段時(shí)間內(nèi)，網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)均被充電至少一次，稱這段時(shí)間為充電調(diào)度，記為Cp(p∈Z).

WCE 在一個(gè)充電輪內(nèi)遍歷部分所需充電的傳感器節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)僅遍歷一次，此時(shí)WCE 的行駛路徑為一條以服務(wù)站S為起止點(diǎn)的Hamilton回路.

對(duì)于充電能量來說，WCE 以發(fā)射功率U′為傳感器節(jié)點(diǎn)進(jìn)行無線充電.傳感器節(jié)點(diǎn)si滿足

其中，η(d)表示充電效率，Ui表示第i個(gè)傳感器節(jié)點(diǎn)的充電接收功率，α和β為常數(shù).

本文假設(shè)所有節(jié)點(diǎn)的充電接收功率相同，即Ui=Uj=U，i≠j，i，j∈Z.令WCE 在傳感器節(jié)點(diǎn)πj處的充電時(shí)間為τj，WCE 從服務(wù)站出發(fā)經(jīng)過若干傳感器節(jié)點(diǎn)后回到服務(wù)站所經(jīng)過的路徑為Q=(π0，π1，π2，…，πj，…，πm，π0)，該路徑下節(jié)點(diǎn)充電的總時(shí)長為τc，WCE在該路徑上消耗的充電能量可以計(jì)算為

4.2 充電時(shí)間窗與懲罰函數(shù)

圖3 違反充電時(shí)間窗的懲罰函數(shù)

的風(fēng)險(xiǎn).綜合考慮，帶時(shí)間窗充電方式能夠保證網(wǎng)絡(luò)穩(wěn)定且有較高的充電能量利用率，不帶時(shí)間窗的充電方式存在充電能量利用率較低的情況且網(wǎng)絡(luò)不夠穩(wěn)定.

4.3 WCE的充電規(guī)劃

WCE 的充電規(guī)劃包括WCE 在攜帶能量約束下的路徑規(guī)劃和充電時(shí)間規(guī)劃，主要解決3 個(gè)問題：攜帶能量是否充足，按照什么路徑來遍歷傳感器節(jié)點(diǎn)，以及在每個(gè)傳感器節(jié)點(diǎn)處停留多長時(shí)間來為節(jié)點(diǎn)補(bǔ)充能量.

如圖4 所示，WCE 從服務(wù)站S出發(fā)經(jīng)過路徑Q=(π0，π1，π2，…，πj，…，π0)到達(dá)節(jié)點(diǎn)πj(πj∈∏)時(shí)的時(shí)間為tj，在該節(jié)點(diǎn)處停留充電的時(shí)間為τj.

圖4 WCE帶時(shí)間窗的充電規(guī)劃示意圖

假設(shè)WCE以最短回路遍歷所有的傳感器節(jié)點(diǎn)所需的最小行駛時(shí)間為，所需的最小行駛能量E′M為

已知WCE 攜帶的行駛能量和充電能量分別為EM和EC，根據(jù)判定方法，可以得到4 種情況下的充電規(guī)劃示意圖，如圖5所示.

（1）當(dāng)EM＞，EC＞時(shí)，WCE 攜帶的行駛能量和充電能量均充足，如圖5（a）所示.此時(shí)WCE 可以從服務(wù)站出發(fā)經(jīng)過Hamilton 回路遍歷所有傳感器節(jié)點(diǎn)并返回服務(wù)站，而所攜帶的充電能量可以將每個(gè)節(jié)點(diǎn)從當(dāng)前能量補(bǔ)充至Emax.

（2）當(dāng)EM＜，EC＞時(shí)，WCE 攜帶的行駛能量不足，充電能量充足，如圖5（b）所示.此時(shí)WCE 無法一次訪問所有的傳感器節(jié)點(diǎn)，需要多次往返充電服務(wù)站補(bǔ)充行駛能量，一次充電調(diào)度包含多個(gè)充電輪.WCE攜帶的充電能量充足，可以將節(jié)點(diǎn)從當(dāng)前能量補(bǔ)充至Emax.

（3）當(dāng)EM＞，EC＜時(shí)，WCE 攜帶的行駛能量充足，充電能量不足，如圖5（c）所示.此時(shí)WCE 有足夠的行駛能量通過Hamilton 回路遍歷所有傳感器節(jié)點(diǎn)，充電能量不足則不能簡單地采用將節(jié)點(diǎn)從當(dāng)前能量補(bǔ)充至Emax.這種情況下需要將有限的充電能量均衡地分配給各節(jié)點(diǎn).

（4）當(dāng)EM＜，EC＜時(shí)，WCE 攜帶的行駛能量和充電能量均不足，如圖5（d）.這種情況最為復(fù)雜，WCE既沒有充足的能量通過一次Hamilton 回路遍歷所有傳感器節(jié)點(diǎn)，又不能在到達(dá)傳感器節(jié)點(diǎn)的時(shí)候直接將所有節(jié)點(diǎn)的能量補(bǔ)充至Emax，充電能量需要均衡分配給各節(jié)點(diǎn).

圖5 4種情況下的充電規(guī)劃

對(duì)于4種情況下充電時(shí)間的計(jì)算可以分為兩種：充電能量充足時(shí)直接補(bǔ)充節(jié)點(diǎn)能量至Emax和充電能量不足時(shí)的均衡分配.假設(shè)在ti時(shí)刻WCE 到達(dá)節(jié)點(diǎn)si時(shí)節(jié)點(diǎn)的剩余能量為Ei(ti)，補(bǔ)充至Emax所需的時(shí)間τi滿足

4.4 優(yōu)化目標(biāo)

本文要解決的問題是在給定的無線傳感器網(wǎng)絡(luò)的規(guī)模、節(jié)點(diǎn)位置、節(jié)點(diǎn)能耗功率、服務(wù)站位置、WCE攜帶行駛能量和充電能量的上限、節(jié)點(diǎn)的充電時(shí)間窗等前提下，求得WCE 的充電規(guī)劃方案.該規(guī)劃方案既要得到WCE 的行駛路徑，又要得到在每個(gè)節(jié)點(diǎn)處的充電時(shí)間，使得網(wǎng)絡(luò)獲得的整體性能最佳.

WCE離開服務(wù)站時(shí)攜帶一定的行駛能量和充電能量，當(dāng)WCE 經(jīng)過若干傳感器節(jié)點(diǎn)并為這些節(jié)點(diǎn)充電后返回服務(wù)站時(shí)，會(huì)剩余部分能量.本文通過一個(gè)充電調(diào)度內(nèi)WCE 的能量利用率φ來衡量WCE 的充電效能，φ計(jì)算為

其中，L為在一個(gè)充電調(diào)度中包含的充電輪的數(shù)量.

按照模糊時(shí)間窗的定義，一個(gè)充電調(diào)度內(nèi)WCE 違反充電時(shí)間窗的懲罰總和Ω滿足

本文的優(yōu)化目標(biāo)為最大化WCE 的能量利用率φ，最小化WCE的懲罰總和Ω，可以表示為

該優(yōu)化問題的優(yōu)化變量為WCE的充電規(guī)劃路徑以及WCE 在傳感器節(jié)點(diǎn)si時(shí)的充能時(shí)間τi(i∈Z，i≤n)，已知傳感器節(jié)點(diǎn)的數(shù)量n及功率pi，WCE的充電功率U及平均行駛速度v，攜帶的行駛能量EM及行駛功率PM，傳感器節(jié)點(diǎn)充電能量最大值Emax和充電能量最小值Emin，以及每個(gè)傳感器節(jié)點(diǎn)的充電時(shí)間窗上下限.

5 算法設(shè)計(jì)

本文所求解的問題是一個(gè)多目標(biāo)優(yōu)化問題，也是一個(gè)NP-hard問題.為此基于多目標(biāo)連續(xù)煙花算法提出一種多目標(biāo)離散煙花算法（Multi-Objective Discrete Fireworks Algorithm，MODFA）.

5.1 煙花算法

煙花算法是一種受煙花爆炸產(chǎn)生火花，并繼續(xù)分裂爆炸這一過程啟發(fā)而得出的算法.在該算法中煙花代表最優(yōu)化問題解空間中的一個(gè)可行解，煙花爆炸產(chǎn)生一定數(shù)量火花的過程就是從一個(gè)可行解探索更多可行解的過程.煙花算法一般包括以下步驟：

（1）隨機(jī)產(chǎn)生一定數(shù)量的煙花，每個(gè)煙花代表一個(gè)可行解；

（2）依據(jù)優(yōu)化目標(biāo)函數(shù)計(jì)算每個(gè)煙花的適應(yīng)度值，適應(yīng)度值反映煙花的好壞，從而在不同范圍內(nèi)產(chǎn)生不同數(shù)量的火花；

（3）判斷是否滿足終止條件，如果滿足則結(jié)束，否則在產(chǎn)生的火花中選擇部分作為下一代的煙花繼續(xù)迭代.

本文所求的解是一個(gè)充電路徑，所有滿足約束條件的充電路徑都是一個(gè)可行解，由此構(gòu)成的解空間比較大.在較大的解空間中探索出最優(yōu)解存在著收斂速度慢和局部收斂的問題，而煙花算法在每一輪迭代中通過煙花的爆炸操作能夠搜索比其他算法更多的可行解，進(jìn)而加快收斂速度.另外煙花算法可以通過較小適應(yīng)度值的煙花進(jìn)行全局搜索，從而在一定程度上避免了局部收斂的問題.因此本文基于煙花算法的這兩個(gè)優(yōu)勢(shì)提出了多目標(biāo)離散煙花算法求解本文的問題.

5.2 煙花個(gè)體的適應(yīng)度計(jì)算

首先，種群中受xi支配的煙花數(shù)目定義為S(xi)，表示為

其中，?表示Pareto 支配關(guān)系，P表示煙花種群.在煙花個(gè)體適應(yīng)度函數(shù)的設(shè)計(jì)上，本文采用SPEA-II 里的適應(yīng)度計(jì)算方法.每個(gè)煙花個(gè)體的適應(yīng)度函數(shù)F(xi)計(jì)算為

其中，R(xi)表示原始適應(yīng)度函數(shù)，計(jì)算為

原始適應(yīng)度函數(shù)的非支配排序無法區(qū)分兩個(gè)相同原始適應(yīng)度值煙花個(gè)體的優(yōu)劣.因此，在采用非支配排序的基礎(chǔ)上，需要引用密度函數(shù)D(xi)以區(qū)分具有相同原始適應(yīng)度值的煙花個(gè)體，密度函數(shù)計(jì)算為

5.3 煙花爆炸數(shù)目的計(jì)算

為了防止算法陷入局部最優(yōu)解，本算法通過爆炸操作對(duì)算子進(jìn)行變異操作，爆炸數(shù)目由個(gè)體的適應(yīng)度確定，其計(jì)算為

其中，sm表示總爆炸數(shù)目，F(xiàn)max為種群中適應(yīng)度的最大值，為了防止分母為零的情況，分別在分子以及分母上增加了ε.

為防止在爆炸過程中，某些煙花個(gè)體的爆炸數(shù)目過大或者過小，需要對(duì)每個(gè)煙花個(gè)體的爆炸數(shù)目進(jìn)行上限和下限的約束，具體約束為

充電規(guī)劃算法的主要步驟如算法1所示.

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

隨機(jī)在1 000 m×1 000 m 的監(jiān)測(cè)區(qū)域部署不同類型網(wǎng)絡(luò)實(shí)例(Net-i，i=1，2，…，12)，以此來驗(yàn)證算法的性能，其中Net-1至Net-4的傳感器節(jié)點(diǎn)數(shù)為20，Net-5至Net-8 的節(jié)點(diǎn)數(shù)為30，Net-9 至的Net-12 節(jié)點(diǎn)數(shù)為40.服務(wù)站均位于坐標(biāo)(0，0)處，不同規(guī)模網(wǎng)絡(luò)的節(jié)點(diǎn)分布如圖6所示.仿真實(shí)驗(yàn)采用的軟件工具是MATLAB R2017a.仿真設(shè)定節(jié)點(diǎn)充電容量最大值為Emax=10.8KJ，節(jié)點(diǎn)充電容量最小值為Emin=540 J，WCE的行駛速度v和充電功率U分別為5 m/s和10 W.傳感器節(jié)點(diǎn)的初始能量為5～10.8之間的隨機(jī)值，單位為KJ.傳感器節(jié)點(diǎn)的能耗功率為0.01～0.2之間的隨機(jī)值，單位為W.

圖6 3種規(guī)模網(wǎng)絡(luò)的節(jié)點(diǎn)分布

將本文提出的算法MODFA 分別與MOEA/D，NSGA-2 以及SPEA-2 這3 個(gè)解決多目標(biāo)優(yōu)化問題最優(yōu)的算法進(jìn)行對(duì)比.其中MOEA/D 將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為一系列單目標(biāo)優(yōu)化問題，再利用進(jìn)化算法對(duì)這些子問題同時(shí)進(jìn)行優(yōu)化.NSGA-2 是多目標(biāo)遺傳算法之一，它能以較低的時(shí)間復(fù)雜度處理復(fù)雜的多目標(biāo)優(yōu)化問題，克服NSGA 的不足.SPEA-2 是SPEA 的增強(qiáng)版，相對(duì)于SPEA，它能進(jìn)行更加精準(zhǔn)的搜索.圖7 至圖10 展示了不同網(wǎng)絡(luò)實(shí)例下4 種算法的Pareto 前沿圖.

圖7 行駛能量與充電能量均充足情況下的Pareto前沿圖

12 種網(wǎng)絡(luò)實(shí)例中，本文MODFA 算法的Pareto 前沿均優(yōu)于其他基準(zhǔn)算法.MODFA 算法在爆炸操作上采用2-opt和3-opt 的局部優(yōu)化策略，這種策略可以優(yōu)化算法的搜索能力，有利于提高算法的性能.

同時(shí)在3 種不同規(guī)模的網(wǎng)絡(luò)實(shí)例情況下，針對(duì)MODFA 算法、MOEA/D 算法、NSGA-2 算法和SPEA-2 算法分別做了50組性能指標(biāo)對(duì)比實(shí)驗(yàn).如表2所示，指標(biāo)PN 表示Pareto 最優(yōu)解的個(gè)數(shù)；指標(biāo)SP 代表Pareto 最優(yōu)解在解空間中的分布范圍，其值越小表示Pareto最優(yōu)解的分布越均勻；指標(biāo)表示Pareto 最優(yōu)解在其前沿的分布范圍，其值越大表示算法效果越好.指標(biāo)SP 計(jì)算為

表2 四種算法各性能指標(biāo)的比較結(jié)果

圖8 充電能量不足,行駛能量充足情況下的Pareto前沿圖

圖9 行駛能量不足,充電能量充足情況下的Pareto前沿圖

圖10 行駛能量與充電能量均不足情況下的Pareto前沿圖

其中，PS多目標(biāo)離散煙花算法所求得的Pareto最優(yōu)解集.

分析50 組對(duì)比實(shí)驗(yàn)的結(jié)果，MODFA 算法得到的Pareto最優(yōu)解明顯優(yōu)于其他3種算法.圖11通過箱型圖展示了4 種算法在50 組實(shí)驗(yàn)中的性能指標(biāo)，本文的MODFA 算法性能指標(biāo)的離群點(diǎn)統(tǒng)計(jì)以及數(shù)據(jù)的離散程度均優(yōu)于其他3種算法.

圖11 四種算法性能指標(biāo)箱型圖

7 總結(jié)

本文針對(duì)無線可充電傳感器網(wǎng)絡(luò)中WCE行駛和充電能量均充足、僅行駛能量不足、僅充電能量不足以及行駛和充電能量均不足4種情況，在傳統(tǒng)的充電模型中引入時(shí)間窗模型，將單目標(biāo)問題轉(zhuǎn)化為多目標(biāo)問題，提出MODFA 算法對(duì)問題進(jìn)行求解，求得了該多目標(biāo)問題的Pareto 最優(yōu)解.此外對(duì)MODFA 算法、MOEA/D 算法、NSGA-2算法和SPEA-2算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，MODFA 算法所求得的Pareto 最優(yōu)解在分布均勻性和分布范圍等性能上均有較大提升，提高了網(wǎng)絡(luò)的整體性能.