曾佑仟,王 茜,張景波,崔志華

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原 030024)

1 引 言

在過(guò)去10年的時(shí)間里,物聯(lián)網(wǎng)技術(shù)發(fā)展迅速.同時(shí),WSNs作為物聯(lián)網(wǎng)的重要組成部分也得到了各領(lǐng)域的廣泛關(guān)注[1-3].WSNs由大量的無(wú)線傳感器節(jié)點(diǎn)通過(guò)自組織或多跳的方式組成.目前,WSNs在許多領(lǐng)域得到了應(yīng)用.如軍事監(jiān)控、醫(yī)療監(jiān)控系統(tǒng)、環(huán)境監(jiān)測(cè)等[4].雖然無(wú)線傳感器節(jié)點(diǎn)具有低功耗、低成本的特點(diǎn),但由于節(jié)點(diǎn)體積小、自身攜帶的能量有限,很難維持傳感器網(wǎng)絡(luò)的長(zhǎng)期通信.同時(shí)在某些惡劣環(huán)境下,無(wú)法更換傳感器節(jié)點(diǎn)的電池.因此,WSNs中節(jié)點(diǎn)能量有限是延長(zhǎng)網(wǎng)絡(luò)生命周期的關(guān)鍵.

為了延長(zhǎng)WSNs的生存期,許多研究者提出了許多不同的策略.一方面,一些研究者采用更高效的路由協(xié)議來(lái)提高WSNs的能量利用率[5].雖然可以節(jié)約一些能源,但不能解決能源供應(yīng)問(wèn)題.另一方面,一些研究者提出通過(guò)收集環(huán)境能量來(lái)延長(zhǎng)傳感器節(jié)點(diǎn)的壽命[6].如波浪能[7]、風(fēng)能、太陽(yáng)能等,這些采集技術(shù)很難為傳感器節(jié)點(diǎn)提供穩(wěn)定持續(xù)的能量,能量轉(zhuǎn)化率非常低.以上兩種方法在一定程度上達(dá)到了延長(zhǎng)網(wǎng)絡(luò)生命周期的目的.然而,他們不能從根本上解決可持續(xù)能源供應(yīng)問(wèn)題.隨著磁共振技術(shù)[8]的出現(xiàn),提出了基于磁諧振耦合技術(shù)的無(wú)線能量傳輸,采用單個(gè)WCV周期性地為節(jié)點(diǎn)[9]提供能量從而形成了WRSNs.該技術(shù)克服了延長(zhǎng)WSNs生命周期的困難,能夠?yàn)楣?jié)點(diǎn)提供穩(wěn)定、可持續(xù)的能量.近年來(lái),WRSNs已成為研究熱點(diǎn).大多數(shù)研究都是基于不同數(shù)量的WCV下的單目標(biāo)或多目標(biāo)充電規(guī)劃.其中充電規(guī)劃主要分為周期性充電和按需充電.

按照固定的時(shí)間間隔并根據(jù)固定的次序?yàn)楣?jié)點(diǎn)補(bǔ)給能量,這種方式被稱為周期性充電.Xie等人[9]提出了一種周期性充電方案,通過(guò)優(yōu)化目標(biāo)使休息時(shí)間與充電周期時(shí)間之比最大化得到了最優(yōu)充電路徑,將充電規(guī)劃問(wèn)題簡(jiǎn)化成TSP問(wèn)題并證明哈密頓循環(huán)就是最短充電路徑.Shi[10]進(jìn)一步優(yōu)化了動(dòng)態(tài)多跳數(shù)據(jù)路由、WCV充電路徑和充電計(jì)劃,使WCV整修時(shí)間與充電周期的比例最大化.Lyu等人[11]提出了利用能量受限移動(dòng)無(wú)線充電設(shè)備的周期充電方案,并采用混合粒子群優(yōu)化遺傳算法優(yōu)化對(duì)接時(shí)間比.為了提高充電效率,提出了單WCV多節(jié)點(diǎn)充電模式.Xie等人[12]提出了一個(gè)一對(duì)多的充電方案,并證明了其近似最優(yōu)解.但是使用這種充電方法將會(huì)造成許多能量的浪費(fèi).雖然周期性充電能夠在一定程度上延續(xù)WRSNs的壽命,但該方案難以滿足實(shí)際的充電需求,在實(shí)際應(yīng)用中會(huì)浪費(fèi)大量不必要的能源.

因此,為了提高充電效率,避免上述周期性充電所存在的問(wèn)題,提出了按需充電策略.只有當(dāng)節(jié)點(diǎn)的能量達(dá)到一定需求閾值時(shí),才被認(rèn)為該節(jié)點(diǎn)需要充電,稱為按需充電.在小規(guī)模場(chǎng)景下,大多數(shù)充電策略都考慮了單WCV到單節(jié)點(diǎn)的充電方式.Kaswan等人[13]提出了一種規(guī)劃充電路徑的線性規(guī)劃(LP)公式和重力搜索算法.Huang等人[14]設(shè)計(jì)了一種新的路徑規(guī)劃方案,稱為基于路徑規(guī)劃的蟻群系統(tǒng)(ACO_PP),并在蟻群算法中引入虛擬電荷節(jié)點(diǎn)來(lái)優(yōu)化移動(dòng)汽車的路徑.Dong等[15]提出了一種基于需求的充電策略,改進(jìn)了聚類和選擇算法進(jìn)行節(jié)點(diǎn)分組和節(jié)點(diǎn)選擇.然后,在文獻(xiàn)[16]中,Zhao等人提出了由充電調(diào)度和充電時(shí)間分配組成的混合模型,并通過(guò)離線算法進(jìn)行優(yōu)化.在文獻(xiàn)[17]中,Wang等人提出了k-覆蓋冗余節(jié)點(diǎn)睡眠調(diào)度算法(KRSS)和面向距離和能量的充電調(diào)度算法(DECS),通過(guò)調(diào)度多輛充電車輛來(lái)減少節(jié)點(diǎn)冗余,防止節(jié)點(diǎn)能量耗盡.雖然結(jié)果表明這些方案是有效的,但利用多輛移動(dòng)充電小車解決小規(guī)模問(wèn)題無(wú)疑是一種資源浪費(fèi).基于以上分析,目前大多數(shù)充電計(jì)劃存在以下弊端.首先,在充電計(jì)劃中,只考慮一個(gè)或兩個(gè)因素作為目標(biāo)函數(shù).其次,充電規(guī)劃大多采用離線方式,且只考慮單個(gè)時(shí)間窗口.未考慮充電過(guò)程中路徑規(guī)劃中加入低能量新節(jié)點(diǎn)的多時(shí)間窗問(wèn)題.因此,為了解決多時(shí)間窗問(wèn)題,延長(zhǎng)WSNs的生存期,本文充分考慮了充電規(guī)劃的死節(jié)點(diǎn)數(shù)、距離、通信延遲時(shí)間和WCV的剩余能量4個(gè)目標(biāo),建立了動(dòng)態(tài)高維多目標(biāo)模型.

同時(shí)為了優(yōu)化動(dòng)態(tài)模型,考慮采用多目標(biāo)進(jìn)化算法[18,19].目前多目標(biāo)進(jìn)化算法已經(jīng)被應(yīng)用于各個(gè)領(lǐng)域.其中,采用了一些優(yōu)化算法對(duì)各種路徑規(guī)劃進(jìn)行優(yōu)化[20-22].Xia等人[23]提出了多目標(biāo)模型,采用改進(jìn)的遺傳算法對(duì)充電路徑進(jìn)行優(yōu)化.在充電方案模型中,本文考慮了死節(jié)點(diǎn)數(shù)、距離、通信延遲時(shí)間和WCV的剩余能量4個(gè)目標(biāo)并提出了高維多目標(biāo)動(dòng)態(tài)路徑規(guī)劃模型.多目標(biāo)優(yōu)化算法雖然可以解決高維多目標(biāo)問(wèn)題,但最優(yōu)解集的多樣性和收斂性較差.因此采用高維多目標(biāo)優(yōu)化算法是必要的.目前,高維多目標(biāo)優(yōu)化算法已經(jīng)得到了深入的發(fā)展和研究[24-26].許多研究人員提出了許多高效的高維多目標(biāo)優(yōu)化算法[27].并在標(biāo)準(zhǔn)測(cè)試集和實(shí)際應(yīng)用中取得了顯著的效果.得到了均衡多樣性和收斂性的最優(yōu)解集[28].其中常用的經(jīng)典算法有:GrEA[29]、NSGA-III[30]、SPEA2[31]、1by1EA[32]等.而與其他進(jìn)化算法相比,SPEA2增強(qiáng)了pareto前沿的選擇壓力,可以篩選出具備更好收斂性和多樣性的解集.采用SPEA2算法對(duì)多目標(biāo)模型進(jìn)行優(yōu)化.而該動(dòng)態(tài)模型考慮了多時(shí)間窗的動(dòng)態(tài)問(wèn)題并且采用整數(shù)序列編碼.因此,本文在SPEA2中引入環(huán)境響應(yīng)機(jī)制和改進(jìn)的交叉和變異方法,以獲得了具有更好多樣性和收斂性的最優(yōu)解集.

本文綜合考慮了充電規(guī)劃中的4個(gè)影響因素作為優(yōu)化目標(biāo),并根據(jù)充電規(guī)劃的動(dòng)態(tài)特性構(gòu)建了動(dòng)態(tài)規(guī)劃模型,并采用改進(jìn)的SPEA2算法優(yōu)化動(dòng)態(tài)模型獲得最優(yōu)充電路徑.通過(guò)仿真實(shí)驗(yàn)結(jié)果證明,提出的方法能夠有效的提高節(jié)點(diǎn)的存活率并延長(zhǎng)WRSNs的生命周期.

2 動(dòng)態(tài)充電規(guī)劃模型與算法優(yōu)化

自WSNs發(fā)展以來(lái),節(jié)點(diǎn)能量的有限性一直是一個(gè)令人困惑的問(wèn)題.解決無(wú)線傳感器節(jié)點(diǎn)能量有限的問(wèn)題是能否延長(zhǎng)WSNs生命周期的關(guān)鍵.隨著磁共振技術(shù)的出現(xiàn),利用WCV為節(jié)點(diǎn)提供能量,形成了WRSNs.如何有效規(guī)劃WCV的充電路徑成為研究熱點(diǎn).許多研究人員提出了多種規(guī)劃的方法,部分研究只考慮了單個(gè)時(shí)間窗的問(wèn)題,而沒(méi)有考慮多個(gè)時(shí)間窗的情況下的路徑規(guī)劃.在WCV充電過(guò)程中,節(jié)點(diǎn)的能量仍是周期性消耗的,并且由于節(jié)點(diǎn)在二維平面上與基站的距離不同,節(jié)點(diǎn)的能量消耗率也不同.當(dāng)達(dá)到需要充電節(jié)點(diǎn)的能量閾值時(shí),向WCV發(fā)送充電請(qǐng)求,將節(jié)點(diǎn)加入充電路徑方案.這個(gè)動(dòng)態(tài)過(guò)程如圖1所示.預(yù)先規(guī)劃和再規(guī)劃的路線分別用實(shí)心箭頭和虛線箭頭表示.

圖1 動(dòng)態(tài)充電規(guī)劃過(guò)程

因此,為適應(yīng)在WCV對(duì)規(guī)劃節(jié)點(diǎn)充電過(guò)程中,由于節(jié)點(diǎn)能量周期性的損耗所導(dǎo)致的新的需充電節(jié)點(diǎn)的出現(xiàn)而引起的環(huán)境變化,建立了動(dòng)態(tài)路徑規(guī)劃模型,將新的節(jié)點(diǎn)加入到充電規(guī)劃中.動(dòng)態(tài)模型由路徑距離、剩余能量、通信延遲時(shí)間和死亡節(jié)點(diǎn)數(shù)4個(gè)目標(biāo)組成.一般情況下,進(jìn)化算法無(wú)法直接優(yōu)化實(shí)際應(yīng)用模型.本文中由于模型具有動(dòng)態(tài)特性,考慮在充電過(guò)程中新節(jié)點(diǎn)加入充電規(guī)劃,這將會(huì)引起決策變量維度的變化導(dǎo)致最優(yōu)解集發(fā)生變化.因此考慮將環(huán)境響應(yīng)機(jī)制和改進(jìn)的進(jìn)化策略引入SPEA2中,以克服動(dòng)態(tài)環(huán)境下多樣性和收斂性的不足.最后利用改進(jìn)的SPEA2優(yōu)化動(dòng)態(tài)模型,以獲得最優(yōu)充電路徑.其中,對(duì)動(dòng)態(tài)模型結(jié)構(gòu)的細(xì)節(jié)和算法優(yōu)化過(guò)程將在后面詳細(xì)的描述.

2.1 動(dòng)態(tài)模型結(jié)構(gòu)

2.1.1 無(wú)線傳感器節(jié)點(diǎn)的能量消耗公式

在無(wú)線傳感器網(wǎng)絡(luò)中,節(jié)點(diǎn)的主要作用是對(duì)環(huán)境變化進(jìn)行監(jiān)測(cè),并將監(jiān)測(cè)數(shù)據(jù)發(fā)送給基站或接收來(lái)自基站或其他人的數(shù)據(jù).而節(jié)點(diǎn)的能耗會(huì)受到各種因素的影響.例如,數(shù)據(jù)的大小、傳輸距離、氣候等.因此,在本文中考慮將數(shù)據(jù)大小和傳輸距離作為影響節(jié)點(diǎn)能耗的主要因素.并將節(jié)點(diǎn)的能耗分為接收數(shù)據(jù)和發(fā)送數(shù)據(jù)兩部分[33].它們由公式(1)和公式(2)表示.

接收數(shù)據(jù)所消耗的能量公式(1)為:

ENrecieve=ENRbit·datac

(1)

其中ENRbit代表接收每bit控制信息數(shù)據(jù)所消耗的能量,其值為50×10-13j/bit.datac是接收控制信息的大小,值為32bits.

公式(2)表示發(fā)送數(shù)據(jù)所消耗的能量如下所示:

(2)

其中ENS代表發(fā)送每bit數(shù)據(jù)所消耗的能量,50×10-13j/bit.ENI是節(jié)點(diǎn)自身能量損耗率,通常設(shè)置為10×10-13j/bit.傳輸數(shù)據(jù)的大小表示為datas.節(jié)點(diǎn)與基站之間的距離用L表示且距離閾值L0設(shè)置為30m.如果節(jié)點(diǎn)與基站之間的距離L在距離閾值L0范圍內(nèi),則節(jié)點(diǎn)能量消耗是正常的;反之如果超出臨界值范圍,則節(jié)點(diǎn)能量損耗將會(huì)加劇.

2.1.2 動(dòng)態(tài)充電規(guī)劃模型

動(dòng)態(tài)模型由4個(gè)目標(biāo)組成.其中,動(dòng)態(tài)模型的動(dòng)態(tài)性主要體現(xiàn)在充電過(guò)程中增加額外的新節(jié)點(diǎn).首先,第1個(gè)目標(biāo)是路徑的總長(zhǎng)度.目標(biāo)的價(jià)值越小越好.具體如公式(3)所示:

Object1:Distance(c(t),t)=

(3)

然后,第2個(gè)目標(biāo)是WCV的剩余能量.目標(biāo)值越大越好.WCV的主要能源消耗是行駛消耗和充電消耗.在充電過(guò)程中,隨著新節(jié)點(diǎn)的加入,汽車的剩余能量會(huì)減少.具體內(nèi)容如式(4)～式(7)所示.

(4)

(5)

eni,t=E0-t·(ENrecieve+ENsend)

(6)

ENmove(c(t))=ECcost·Distance(c(t),t)

(7)

其中ENcar是WCV自身所攜帶的總能量.節(jié)點(diǎn)的初始能量被設(shè)定為E0.ENmove和ENcharge分別代表WCV自身行駛所消耗的能量和為節(jié)點(diǎn)充電所消耗的能量.在t時(shí)刻第i節(jié)點(diǎn)的剩余能量為eni,t,ECcost代表WCV的行駛能量消耗率.

然后第3個(gè)目標(biāo)是充電過(guò)程中死亡節(jié)點(diǎn)的數(shù)量.為了確保延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期,需要減少死節(jié)點(diǎn)的數(shù)量.死亡的節(jié)點(diǎn)越少越好.同時(shí)死節(jié)點(diǎn)的數(shù)量也反映了規(guī)劃路徑的充電效率.具體細(xì)節(jié)如公式(8)和公式(9)所示:

(8)

(9)

其中DSi代表該節(jié)點(diǎn)是否死亡,如果值為1,則節(jié)點(diǎn)死亡;反之,值為0,存活.為了計(jì)算該節(jié)點(diǎn)是否死亡需要用到公式(8),通過(guò)節(jié)點(diǎn)的損耗率以及到達(dá)該節(jié)點(diǎn)所需的時(shí)間來(lái)計(jì)算節(jié)點(diǎn)剩余能量.

最后,第4個(gè)目標(biāo)是通信延遲時(shí)間.當(dāng)無(wú)線傳感器節(jié)點(diǎn)低于數(shù)據(jù)傳輸?shù)哪芰恳?不能完成正常通信時(shí),就會(huì)造成延遲時(shí)間.因此,具體如公式(10)和公式(11)所示:

(10)

(11)

其中DTi為第i個(gè)節(jié)點(diǎn)的通信延遲時(shí)間.Tmove,i表示W(wǎng)CV到達(dá)節(jié)點(diǎn)時(shí)車輛在道路上行駛的總時(shí)間.Tcharge,i表示W(wǎng)CV到達(dá)該節(jié)點(diǎn)時(shí),向通過(guò)的節(jié)點(diǎn)充電所需的總時(shí)間.Tconsume,i表示節(jié)點(diǎn)正常通信的最大時(shí)間.如果Tmove,i+Tcharge,i-Tconsume,i的值小于等于0,則節(jié)點(diǎn)可以保持正常通信,直到小車到達(dá).否則會(huì)造成通信的延誤.

綜上所述,本文對(duì)可充電傳感器網(wǎng)絡(luò)下的動(dòng)態(tài)充電規(guī)劃問(wèn)題,構(gòu)建高維多目標(biāo)動(dòng)態(tài)優(yōu)化模型,具體目標(biāo)如公式(12)所示:

(12)

2.2 高維多目標(biāo)動(dòng)態(tài)路徑規(guī)劃算法

進(jìn)化算法已經(jīng)從單一目標(biāo)擴(kuò)展到多目標(biāo)甚至高維多目標(biāo).其中當(dāng)目標(biāo)個(gè)數(shù)超過(guò)3個(gè)時(shí)被定義為高維多目標(biāo)優(yōu)化問(wèn)題,而現(xiàn)有的多目標(biāo)算法在解決高維多目標(biāo)問(wèn)題時(shí),求解精度不足且算法多樣性和收斂性較差.因此,考慮采用SPEA2高維多目標(biāo)優(yōu)化算法求解上述動(dòng)態(tài)充電模型.在SPEA2中,采用了通過(guò)利用每個(gè)個(gè)體主導(dǎo)的解決方案的數(shù)量和個(gè)體密度信息來(lái)提高種群選擇壓力的適應(yīng)度分配方法,并通過(guò)傳統(tǒng)的交叉和變異算子更新種群.然而在求解動(dòng)態(tài)充電模型時(shí),存在如下問(wèn)題:

1)由于決策變量的維度,即充電節(jié)點(diǎn)的數(shù)量會(huì)發(fā)生變化,SPEA2無(wú)法求解決策變量維數(shù)變化的模型問(wèn)題.

2)由于決策變量采用整數(shù)編碼方式,SPEA2采用傳統(tǒng)交叉和變異方式更新種群將會(huì)導(dǎo)致編碼冗余問(wèn)題.因此本文通過(guò)引入環(huán)境響應(yīng)機(jī)制和改進(jìn)的進(jìn)化策略,提出了改進(jìn)的SPEA2算法.其中環(huán)境響應(yīng)機(jī)制在環(huán)境發(fā)生變化時(shí)利用歷史信息尋找變化的決策空間中的最優(yōu)解來(lái)解決決策變量維度變化問(wèn)題(詳見(jiàn)2.2.1節(jié)).在種群進(jìn)化過(guò)程中,改進(jìn)的進(jìn)化策略不僅能夠解決編碼冗余問(wèn)題,還能夠?yàn)榉N群提供新的搜索方向避免早熟收斂,從而在保證收斂性的前提下,提高種群的多樣性(詳見(jiàn)2.2.2節(jié)).

具體算法流程如算法1偽代碼所示.首先初始化種群及相關(guān)參數(shù),并計(jì)算適應(yīng)度值.然后在算法1步驟4～步驟6中執(zhí)行環(huán)境響應(yīng)機(jī)制.通過(guò)錦標(biāo)賽選擇法選出N個(gè)個(gè)體放入種群P1,并利用步驟8的改進(jìn)的進(jìn)化策略更新種群P1,然后合并種群并選出N個(gè)個(gè)體作為新的父代種群,迭代循環(huán)直到達(dá)到終止條件.

算法1.改進(jìn)的SPEA2算法流程

輸入:種群大小N,最大迭代次數(shù)tmax

輸出:最優(yōu)解集合Pt+1

1.初始化產(chǎn)生種群P0,t=0;

2.計(jì)算每個(gè)個(gè)體i的適應(yīng)值Fi;

3.Whilet≤tmaxdo

4.if環(huán)境變化then

5. 采用環(huán)境響應(yīng)機(jī)制;

6.endif

7. 利用適應(yīng)值Fi和錦標(biāo)賽選擇法從P0中選出N個(gè)個(gè)體放入P1;

8. 利用改進(jìn)的交叉算子和變異算子更新種群P1;

9. 合并種群R=P0∪P1′;

10.fori=1:|R|do

11. 計(jì)算種群R中每個(gè)個(gè)體i的適應(yīng)值Fi′;

12.ifFi′<1then

13. 將滿足條件的個(gè)體放入Pt+1中;

14.endif

15.endfor

16.if|Pt+1|

17.Pt+1=[];

18. 選擇前N個(gè)個(gè)體放入Pt+1中;

19.elseif|Pt+1|>N

20. 利用阻截算子除掉種群Pt+1中冗余的個(gè)體;

21.endif

22.t=t+1;

23.endwhile

24.returnPt+1;

2.2.1 環(huán)境響應(yīng)機(jī)制

在充電過(guò)程中,由于節(jié)點(diǎn)能量周期性損耗,充電路徑上會(huì)增加新的節(jié)點(diǎn),如圖2所示.為了適應(yīng)環(huán)境變化,保證種群的多樣性和收斂性,提出了環(huán)境響應(yīng)機(jī)制.

圖2 交叉算子流程

當(dāng)環(huán)境發(fā)生變化時(shí),一般算法只能重新生成新個(gè)體,浪費(fèi)歷史信息.因此,為了充分利用歷史信息,本文提出了一個(gè)環(huán)境響應(yīng)機(jī)制.當(dāng)檢測(cè)到環(huán)境變化時(shí),保持環(huán)境變化前的最后一代種群,隨機(jī)插入新個(gè)體.該方法可以提高新環(huán)境下種群的多樣性,從而確保能找到全局最優(yōu)解,避免陷入局部最優(yōu)解.具體過(guò)程如算法2偽代碼所示.

算法2.環(huán)境響應(yīng)機(jī)制

Input:種群P={p1,p2,…,pN},種群大小N,新節(jié)點(diǎn)集合C={c1,c2,c3,…,cn},在每個(gè)決策變量中固定節(jié)點(diǎn)數(shù)量fixed(fix1,fix2,…,fixn)

Output:種群P′

1.if環(huán)境變化then

2.P′=[];

3.fori=1:Ndo

4.forj=1:|C|do

5. 從fixi到N的范圍內(nèi),隨機(jī)選擇一個(gè)位置;

6. 將新節(jié)點(diǎn)cj插入pi中并獲得新的個(gè)體pi′;

7.P′=P′←pi′

8.endfor

9.endfor

10.endif

11.returnP′;

2.2.2 改進(jìn)的進(jìn)化策略

在動(dòng)態(tài)模型中,采用整數(shù)序列編碼方法作為決策變量的編碼方式.整數(shù)序列編碼方法雖然解決了路徑編碼問(wèn)題,但也提出了一個(gè)新的問(wèn)題.在SPEA2中,采用真實(shí)雜交和突變的方法更新種群.然而,在本文的動(dòng)態(tài)模型中,決策變量是整數(shù)序列,該序列中的數(shù)字不能是冗余的.因此,本文設(shè)計(jì)了整數(shù)交叉和變異算子.具體介紹如下:

1)基于概率的整數(shù)交叉算子

如果隨機(jī)數(shù)不滿足交叉概率,則跳過(guò)交叉算子.相反,如果它滿足,則執(zhí)行以下操作.首先,從個(gè)體中選擇兩個(gè)組節(jié)點(diǎn),組的大小為兩個(gè)節(jié)點(diǎn).然后,交換兩組數(shù)字的位置.最后,以節(jié)點(diǎn)的剩余能量作為排序的指標(biāo),并用該指標(biāo)對(duì)兩組節(jié)點(diǎn)進(jìn)行排序.具體過(guò)程描述如下:

例如,{10,6,11,2,5,8,3,9,1,7,4}.首先,在尚未充電的節(jié)點(diǎn)中部隨機(jī)選取兩組節(jié)點(diǎn).交換位置后,根據(jù)節(jié)點(diǎn)的剩余能量對(duì)節(jié)點(diǎn)組進(jìn)行排序,獲取新的充電路徑.這種方法有利于快速搜索局部區(qū)域的最優(yōu)解集.原理圖如圖2所示.

2)基于概率的整數(shù)變異算子

如果隨機(jī)數(shù)不滿足變異概率,則跳過(guò)變異算子.相反,如果它滿足,則執(zhí)行以下操作.由于充電路徑為整數(shù)序列,為了保證種群的多樣性,保證新節(jié)點(diǎn)加入時(shí)適應(yīng)新環(huán)境,本文采用了頭尾交換的方式,其余操作符與交叉操作符相似.具體操作如圖3所示.

圖3 變異算子流程

雖然種群是通過(guò)交叉和變異操作來(lái)更新的,但對(duì)某些個(gè)體來(lái)說(shuō),這兩種操作有時(shí)會(huì)被跳過(guò).這些個(gè)體是從親本種群中選擇出來(lái)的.因此,為了避免多樣性的喪失和過(guò)多的重復(fù)個(gè)體,這些個(gè)體被隨機(jī)再生.

3 性能評(píng)估

3.1 仿真環(huán)境設(shè)置和實(shí)驗(yàn)介紹

本文使用數(shù)學(xué)軟件MATLAB R2016b進(jìn)行仿真實(shí)驗(yàn).在尺寸為L(zhǎng)×L的二維空間中構(gòu)造傳感器網(wǎng)絡(luò).無(wú)線傳感器節(jié)點(diǎn)隨機(jī)均勻分布在各節(jié)點(diǎn)之間,如圖4所示.仿真場(chǎng)景如圖1所示,具體參數(shù)設(shè)置如表1所示.

圖4 節(jié)點(diǎn)在無(wú)線傳感器網(wǎng)絡(luò)中的分布

表1 參數(shù)設(shè)置

本文考慮到在WCV充電過(guò)程中,由于節(jié)點(diǎn)依然在周期性的通信且能量根據(jù)公式1和2周期損耗,而導(dǎo)致在原充電規(guī)劃之外,新的需要充電的節(jié)點(diǎn)的產(chǎn)生.且每個(gè)節(jié)點(diǎn)的能量損耗是不同,每個(gè)周期中新加入的節(jié)點(diǎn)數(shù)量是隨機(jī)的.因此,在本次實(shí)驗(yàn)中本文考慮如下3組對(duì)比實(shí)驗(yàn):第1個(gè)是考慮不同進(jìn)化算法與Improved SPEA2的對(duì)比,然后獨(dú)立運(yùn)行30次并每次獨(dú)立運(yùn)行保存10個(gè)周期的實(shí)驗(yàn)結(jié)果,計(jì)算每個(gè)周期的平均目標(biāo)值,并分別從節(jié)點(diǎn)存活率和WCV行駛距離兩個(gè)角度分析,通過(guò)對(duì)比每個(gè)周期下4個(gè)目標(biāo)值分析不同算法性能.第2個(gè)是考慮在不同規(guī)模節(jié)點(diǎn)的情況下,分析了不同算法在不同規(guī)模下對(duì)實(shí)驗(yàn)結(jié)果的影響.第3個(gè)是為了證明提出的動(dòng)態(tài)充電模型的有效性,考慮將動(dòng)態(tài)模型與靜態(tài)模型進(jìn)行比較.下面將對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析.

3.2 性能對(duì)比和分析

3.2.1 性能指標(biāo)

在對(duì)比實(shí)驗(yàn)分析中,采用死節(jié)點(diǎn)數(shù)作為評(píng)價(jià)充電方案效率的主要指標(biāo).為了更直觀地反映充電效率,將該指標(biāo)轉(zhuǎn)化為節(jié)點(diǎn)存活率.同時(shí),該值越大,傳感器網(wǎng)絡(luò)的生存期越長(zhǎng).具體變換公式如下:

(13)

3.2.2 靜態(tài)模型與動(dòng)態(tài)模型之間的對(duì)比

為了證明動(dòng)態(tài)模型的有效性,本文考慮與靜態(tài)模型進(jìn)行對(duì)比,并使用與動(dòng)態(tài)模型相同的目標(biāo)和參數(shù).而靜態(tài)模型與動(dòng)態(tài)模型中沒(méi)有考慮到新節(jié)點(diǎn)出現(xiàn)后的再規(guī)劃過(guò)程.因此通過(guò)對(duì)比在每個(gè)周期下的目標(biāo)值,如圖5所示.它們表明,對(duì)于動(dòng)態(tài)模型和靜態(tài)模型,每個(gè)目標(biāo)值在初始的第1個(gè)循環(huán)中大致相同.這是因?yàn)樵诔跏嫉牡?個(gè)循環(huán)中充電路徑?jīng)]有新增節(jié)點(diǎn).但是,隨著充電規(guī)劃中加入新的節(jié)點(diǎn),動(dòng)態(tài)模型和靜態(tài)模型中各目標(biāo)的值可以明顯區(qū)分.這是因?yàn)楫?dāng)在充電路徑中添加新節(jié)點(diǎn)時(shí),動(dòng)態(tài)模型中會(huì)使用歷史信息對(duì)充電路徑進(jìn)行動(dòng)態(tài)規(guī)劃,而靜態(tài)模型中只有在第1個(gè)規(guī)劃路徑完成后才能對(duì)充電路徑進(jìn)行重新規(guī)劃.因此,隨著新節(jié)點(diǎn)的不斷增加,動(dòng)態(tài)模型與靜態(tài)模型之間的性能差距也越來(lái)越明顯.實(shí)驗(yàn)結(jié)果表明,該方法在動(dòng)態(tài)模型中延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存期和減少死亡節(jié)點(diǎn)方面具有較好的性能.

圖5 動(dòng)態(tài)模型和靜態(tài)模型的性能比較

3.2.3 不同進(jìn)化算法之間的對(duì)比

在對(duì)比實(shí)驗(yàn)分析中,本文采用了ImprovedSPEA2進(jìn)化算法,并將其與GrEA、1by1EA、SGA-III進(jìn)化算法進(jìn)行對(duì)比.然后利用節(jié)點(diǎn)的平均存活率,通信延遲時(shí)間,路徑距離以及WCV剩余能量來(lái)驗(yàn)證算法的性能.實(shí)驗(yàn)對(duì)比結(jié)果如圖6和圖7所示.

圖6 對(duì)應(yīng)于每個(gè)算法存活率最高的個(gè)體的4個(gè)目標(biāo)值

圖7 對(duì)應(yīng)于每個(gè)算法路徑距離最短的個(gè)體4個(gè)目標(biāo)值

一方面,從無(wú)線傳感器網(wǎng)絡(luò)的角度對(duì)延長(zhǎng)節(jié)點(diǎn)生命周期進(jìn)行實(shí)驗(yàn)分析,如圖6所示.在不同算法中選擇每個(gè)周期中存活率最高的個(gè)體進(jìn)行比較.圖6(a)顯示了不同算法提高節(jié)點(diǎn)存活率的性能.由圖6(a)看出,隨著需要充電的節(jié)點(diǎn)不斷加入,ImprovedSPEA2動(dòng)態(tài)規(guī)劃充電路徑的節(jié)點(diǎn)存活率不斷提高.雖然GrEA與ImprovedSPEA2相比可以獲得相當(dāng)?shù)拇婊盥?但SPEA2在整個(gè)過(guò)程中比其他算法具有更高的存活率.圖6(b)為通信延遲時(shí)間,當(dāng)節(jié)點(diǎn)能量達(dá)到一定閾值時(shí),節(jié)點(diǎn)將無(wú)法與基站進(jìn)行數(shù)據(jù)通信.從圖6(b)可以看出,在一開(kāi)始,ImprovedSPEA2和GrEA具有可比性.而在第5個(gè)周期之后,ImprovedSPEA2的延遲時(shí)間相比其他算法更低.這也意味著規(guī)劃的充電路徑是有效的.圖6(c)和圖6(d)表示W(wǎng)CV的距離和剩余能量.由于本文是從節(jié)點(diǎn)生命周期延長(zhǎng)的角度考慮問(wèn)題,因此規(guī)劃的路徑往往會(huì)延長(zhǎng)節(jié)點(diǎn)的生命周期.而多目標(biāo)優(yōu)化會(huì)犧牲一些其他目標(biāo)來(lái)獲得優(yōu)選解.雖然這兩個(gè)目標(biāo)不能得到ImprovedSPEA2的最優(yōu)解,但可以發(fā)現(xiàn)這兩個(gè)目標(biāo)的解集在可接受的范圍內(nèi).因此,ImprovedSPEA2可以通過(guò)優(yōu)化充電路徑,有效延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期,提高WCV的充電效率.

另一方面,從WCV的角度對(duì)提高能源利用率進(jìn)行實(shí)驗(yàn)分析,如圖7所示.在不同算法中選擇距離最短的個(gè)體進(jìn)行比較.從圖7(a)可以看出,與其他算法相比,1by1EA算法可以得到距離最短的最優(yōu)路徑.圖7(a)中最短距離的值優(yōu)于圖7(a)中最短距離的值.但整體生存率低于圖6(a).

因此,多目標(biāo)算法在選擇首選解時(shí)會(huì)影響其他目標(biāo).雖然從圖7(a)中,ImprovedSPEA2的趨勢(shì)處于第2位,但實(shí)驗(yàn)結(jié)果不能從一個(gè)方面進(jìn)行分析.由圖7(b)、(c)、(d)可知,距離最短的個(gè)體對(duì)應(yīng)的其他3個(gè)目標(biāo)值,ImprovedSPEA2的生存率和延遲時(shí)間都優(yōu)于其他算法,剩余能量也處于中等水平.因此,從MCV的角度使用ImprovedSPEA2也得到了不錯(cuò)的實(shí)驗(yàn)結(jié)果.

3.2.4 不同規(guī)模WRSNs下的對(duì)比

在本文中,主要考慮小規(guī)模場(chǎng)景下的路徑規(guī)劃.為了更好地證明動(dòng)態(tài)模型和改進(jìn)后的SPEA2的性能,采用不同規(guī)模的節(jié)點(diǎn)數(shù),包括100節(jié)點(diǎn)、125節(jié)點(diǎn)、150節(jié)點(diǎn)、175節(jié)點(diǎn)、200節(jié)點(diǎn)、225節(jié)點(diǎn)、250節(jié)點(diǎn).實(shí)驗(yàn)結(jié)果如表2所示.

表2 不同規(guī)模下的節(jié)點(diǎn)存活率

通過(guò)分析表2 ,初始節(jié)點(diǎn)存活率隨著節(jié)點(diǎn)規(guī)模數(shù)的增加而降低.但在相同規(guī)模WRSNs下,傳感器節(jié)點(diǎn)的存活率隨著周期的迭代而增加,在第10個(gè)周期可以得到較好的存活率值.在表2中,每個(gè)循環(huán)結(jié)果的最佳值用黑色粗體標(biāo)記.實(shí)驗(yàn)結(jié)果表明,ImprovedSPEA2可以獲得較好的存活率,GrEA也可以獲得與ImprovedSPEA2相差約1%的存活率.然而,最糟糕的是1by1EA,與ImprovedSPEA2的差異約為3%～5%.因此,可以利用ImprovedSPEA2來(lái)規(guī)劃有效的充電路徑.

4 結(jié) 論

為了規(guī)劃有效的充電路徑,延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存期,本文設(shè)計(jì)了一個(gè)以最小化路徑距離、死亡節(jié)點(diǎn)數(shù)量、通信延遲以及最大化WCV剩余能量為目標(biāo)建立了一個(gè)高維多目標(biāo)動(dòng)態(tài)模型.然后,將改進(jìn)的交叉和變異算子以及環(huán)境響應(yīng)機(jī)制引入到SPEA2中,以適應(yīng)編碼模式和變化的環(huán)境.動(dòng)態(tài)模型通過(guò)改進(jìn)的SPEA2進(jìn)行優(yōu)化.通過(guò)動(dòng)態(tài)模型與靜態(tài)模型的對(duì)比實(shí)驗(yàn)結(jié)果表明,動(dòng)態(tài)模型能更有效地提高無(wú)線傳感器網(wǎng)絡(luò)的生命周期.通過(guò)比較不同算法求解動(dòng)態(tài)模型的結(jié)果,改進(jìn)的交叉和變異算子提高了模型的多樣性和收斂性.通過(guò)環(huán)境響應(yīng)機(jī)制,提高了全局搜索的性能,可以更快地適應(yīng)新環(huán)境.同時(shí),為了測(cè)試模型和算法的處理能力,本文考慮在不同規(guī)模WRSNs下進(jìn)行對(duì)比.最后,實(shí)驗(yàn)結(jié)果表明所提出的動(dòng)態(tài)模型以及改進(jìn)的SPEA2能夠有效提高節(jié)點(diǎn)存活率,延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存期.然而目前所提出的方法應(yīng)用在大規(guī)模WRSNs中,單個(gè)WCV難以滿足充電需求,將會(huì)導(dǎo)致諸多節(jié)點(diǎn)難以及時(shí)得到能量補(bǔ)給,因此在未來(lái)工作中將會(huì)考慮采用多個(gè)WCV協(xié)同充電解決大規(guī)模WRSNs問(wèn)題.