基于策略梯度的WRSN 公平能量補(bǔ)充方案

葉健鋒

（昆明理工大學(xué)，云南 昆明 650500）

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network, WSN）已廣泛應(yīng)用于許多領(lǐng)域，如森林火災(zāi)監(jiān)測(cè)、建筑監(jiān)控等[1-3]。一般來說，無線傳感器網(wǎng)絡(luò)由大量的傳感器組成。由于這些傳感器由能量受限的電池供電，網(wǎng)絡(luò)的運(yùn)行時(shí)間通常是有限的，這阻礙了傳感器網(wǎng)絡(luò)的發(fā)展[4-6]。考慮到每個(gè)傳感器的電池容量是有限的，在電池耗盡之前補(bǔ)充傳感器的能量供應(yīng)至關(guān)重要。受益于無線充電技術(shù)的發(fā)展[7]，無線可充電傳感網(wǎng)絡(luò)（Wireless Rechargeable Sensor Network, WRSN）廣受關(guān)注，使用配備無線充電設(shè)備的移動(dòng)車輛為傳感器充電成為解決該問題非常有效的解決方案[8-9]。由于WRSN 中的傳感器節(jié)點(diǎn)失效會(huì)導(dǎo)致數(shù)據(jù)丟失、鏈接斷開甚至網(wǎng)絡(luò)癱瘓等嚴(yán)重問題，如何調(diào)度MC（Mobile Charger）高效地為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)補(bǔ)充能量是WRSN 充電策略的關(guān)鍵問題。

現(xiàn)有的WRSN 能量補(bǔ)充方案一部分提前規(guī)劃出一條充電回路，MC 沿著預(yù)定的軌跡行走，給節(jié)點(diǎn)進(jìn)行能量補(bǔ)充。文獻(xiàn)[10]在能耗不變的情況下，將求解問題轉(zhuǎn)化為求解旅行商問題（Traveling Salesman Problem, TSP），通過最小化MC 的移動(dòng)距離來最大化MC 的充電效率。文獻(xiàn)[11]提出一種帶時(shí)間窗的旅行商問題（Traveling Salesman Problem With Time Window, TSPTW），尋找一條最小移動(dòng)成本路徑作為一個(gè)充電周期，但路徑上的節(jié)點(diǎn)僅訪問一次，這無法應(yīng)對(duì)能耗較高的節(jié)點(diǎn)在一個(gè)充電周期內(nèi)多次打開時(shí)間窗的情況。

另一部分能量補(bǔ)充方案是由MC 根據(jù)網(wǎng)絡(luò)情況實(shí)時(shí)響應(yīng)傳感器充電請(qǐng)求。文獻(xiàn)[12]中提出一種搶占式最近距離優(yōu)先充電策略，這樣能提高M(jìn)C 的能量利用率，但是沒有考慮對(duì)充電請(qǐng)求的公平性，導(dǎo)致某些傳感器因?yàn)殚L(zhǎng)時(shí)間得不到能量補(bǔ)充而失效。文獻(xiàn)[13]將節(jié)點(diǎn)按剩余生存時(shí)間進(jìn)行分組，每次選取剩余生存時(shí)間小的節(jié)點(diǎn)進(jìn)行能量補(bǔ)充，卻沒有考慮MC 在移動(dòng)時(shí)消耗的能量。文獻(xiàn)[14]雖然能盡量避免節(jié)點(diǎn)失效，但是其假設(shè)基礎(chǔ)MC 能量無限大、節(jié)點(diǎn)能耗是不變的，在實(shí)際情況下不存在該情況。

通過分析現(xiàn)有的工作，存在以下問題：

1）因節(jié)點(diǎn)能耗動(dòng)態(tài)變化，而不能很好預(yù)知各節(jié)點(diǎn)剩余生存時(shí)間來規(guī)劃節(jié)點(diǎn)的充電序列；

2）MC 響應(yīng)節(jié)點(diǎn)的充電請(qǐng)求不具有公平性，存在節(jié)點(diǎn)因等待時(shí)間過長(zhǎng)而失效；

3）WRSN 中的MC 充電路線規(guī)劃被證明為NP-hard問題，對(duì)于傳統(tǒng)方法求解NP-hard 很難得到滿足實(shí)際需求的最優(yōu)解。

本文的主要貢獻(xiàn)如下：

1）聯(lián)合考慮節(jié)點(diǎn)能耗動(dòng)態(tài)變化、MC 的充電代價(jià)和失效節(jié)點(diǎn)數(shù), 提出一種新的充電調(diào)度方法PFSS；

2）利用過往的節(jié)點(diǎn)能量記錄對(duì)節(jié)點(diǎn)實(shí)時(shí)能耗進(jìn)行估算；

3）引入一個(gè)新的評(píng)估標(biāo)準(zhǔn)充電權(quán)重來評(píng)估一組充電序列的質(zhì)量，并且參考文獻(xiàn)[15]采用seq2seq 與Attention 結(jié)合的網(wǎng)絡(luò)來求解充電序列，并通過策略梯度對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練；

4）建立仿真環(huán)境并與現(xiàn)有充電方案進(jìn)行對(duì)比，證明了本文方案的有效性。

1 網(wǎng)絡(luò)模型與問題描述

1.1 WRSN 模型

WRSN 模型部署在一個(gè)邊長(zhǎng)為L(zhǎng)的正方形區(qū)域內(nèi)，由三個(gè)部分組成，分別是基站（Base Station, BS）、傳感器節(jié)點(diǎn)和MC。其中：基站在區(qū)域的左下角（0,0）的位置；傳感器隨機(jī)均勻地分布在區(qū)域內(nèi)，傳感器節(jié)點(diǎn)集合S={s1,s2,…,sn}，si表示第i個(gè)傳感器，si= ()為si的二維位置坐標(biāo)傳感器，其最大電量為Es，當(dāng)自身能量下降到預(yù)先設(shè)定閾值η時(shí)，主動(dòng)向基站發(fā)送充電請(qǐng)求，移動(dòng)充電裝置MC，以vm速度移動(dòng)，攜帶的可充電電池最大容量為Cm。

1.2 節(jié)點(diǎn)模型

根據(jù)文獻(xiàn)[16]物理模型，傳感節(jié)點(diǎn)能耗主要由兩個(gè)方面組成：

發(fā)送能耗：發(fā)送電路和功率放大器；

接收能耗：接收電路。

能耗模型如下：

式中：E(k,d)表示距離為d的兩個(gè)傳感器發(fā)送kbit 數(shù)據(jù)時(shí)消耗的能量；Eelect表示發(fā)送或者接收1 bit 數(shù)據(jù)的能耗；Emp表示功率放大器能耗，Emp又分為Efs、Emf兩種情況，分別表示在自由空間和多徑衰落模型中每平方米內(nèi)處理1 bit數(shù)據(jù)消耗的能量，分別表示如下：

門限距離為do，具體如公式（3）所示：

則：

在t時(shí)刻第i個(gè)節(jié)點(diǎn)的能耗模型如下：

式中Ej,i(k,d,t)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)之間在t時(shí)刻傳輸kbit 數(shù)據(jù)消耗的能量。因此，在t時(shí)刻節(jié)點(diǎn)i的剩余電量為：

節(jié)點(diǎn)電量需求為：

因此，MC 在t時(shí)刻的剩余電量如式（8）所示：

式中：Em為MC 移動(dòng)每米消耗的能量；di,j表示第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)之間的距離。

2 PFSS 策略設(shè)計(jì)實(shí)現(xiàn)

2.1 節(jié)點(diǎn)能耗估算

采用過往的節(jié)點(diǎn)能耗對(duì)將來節(jié)點(diǎn)能耗進(jìn)行估算，設(shè)網(wǎng)絡(luò)初始時(shí)間為0，時(shí)間間隔為Δ，節(jié)點(diǎn)將當(dāng)前剩余電量(t)發(fā)送給基站，則節(jié)點(diǎn)實(shí)時(shí)能耗pi,t為：

基站收到節(jié)點(diǎn)i的n+ 1 條信息后，對(duì)節(jié)點(diǎn)i能耗進(jìn)行估計(jì)，考慮過往的節(jié)點(diǎn)能量消耗率和估算的實(shí)時(shí)性，采用時(shí)間值作為權(quán)重，權(quán)重越大，表示其值就越新，就越具有更高的參考價(jià)值，更接近實(shí)時(shí)值。

把公式（9）代入公式（10）得：

這樣需要基站保存所有的歷史數(shù)據(jù)，導(dǎo)致基站的存儲(chǔ)代價(jià)會(huì)隨著時(shí)間的推移越來越大，因此改進(jìn)式（11）為：

式中ETn-1表示前n次的時(shí)間總和，表示為：

這樣得到預(yù)測(cè)能量消耗Pi,t，但實(shí)際情況下，預(yù)測(cè)值跟實(shí)際值存在一定的偏差，實(shí)際值pi,t等于預(yù)測(cè)值Pi,t加上偏差值bi,t，則偏差為：

因此，為了更加準(zhǔn)確地估算能量消耗率，也需要對(duì)偏差值進(jìn)行估算，采用基于過往經(jīng)驗(yàn)的方法進(jìn)行預(yù)測(cè)，得到以下公式：

可以看到兩個(gè)估算值與時(shí)間間隔有關(guān)，時(shí)間間隔越小，估算值也就越準(zhǔn)確，若是時(shí)間間隔1 s 就進(jìn)行一次估算，那么其估算值就會(huì)越準(zhǔn)確，這就需要節(jié)點(diǎn)頻繁地發(fā)送自身狀態(tài)給基站，但這會(huì)減低WRSN 的網(wǎng)絡(luò)運(yùn)行時(shí)間，加快節(jié)點(diǎn)的失效，因此時(shí)間間隔不易太短。則估算t時(shí)刻節(jié)點(diǎn)i能耗為：

那么t時(shí)刻節(jié)點(diǎn)i的剩余生存時(shí)間如下：

2.2 充電權(quán)重

設(shè)MC 的一個(gè)充電周期遍歷的節(jié)點(diǎn)集合為C={c0,c1,c2,…,cn+1}，節(jié)點(diǎn)c0,cn+1表示基站,表示各節(jié)點(diǎn)發(fā)出充電請(qǐng)求的時(shí)間，則MC 在一個(gè)充電周期的總移動(dòng)距離為：

式中表示節(jié)點(diǎn)ci-1到ci的距離。

若e表示MC 每秒的充電功率，表示給節(jié)點(diǎn)ci充電前第j個(gè)節(jié)點(diǎn)的剩余電量，則給節(jié)點(diǎn)ci充電的起始時(shí)間為：

因此，節(jié)點(diǎn)ci的相應(yīng)等待時(shí)間為:

為了提高M(jìn)C 的能量利用率，降低節(jié)點(diǎn)的等待時(shí)間，減少節(jié)點(diǎn)的失效率，構(gòu)建充電回路的優(yōu)化目標(biāo)為：

式中Count(< 0)表示節(jié)點(diǎn)剩余生存時(shí)間小于節(jié)點(diǎn)等待時(shí)間的個(gè)數(shù)，即失效節(jié)點(diǎn)數(shù)。

由優(yōu)化目標(biāo)可以看出：構(gòu)建的充電回路MC 移動(dòng)的距離應(yīng)盡可能的少；節(jié)點(diǎn)的等待時(shí)間應(yīng)盡可能的少；節(jié)點(diǎn)的剩余生存時(shí)間應(yīng)盡可能的多，因此定義充電權(quán)重q來衡量一個(gè)充電周期的好壞。

定義1節(jié)點(diǎn)充電權(quán)重：給節(jié)點(diǎn)i在t時(shí)刻的充電權(quán)重qi(t)的定義如式（22）所示：

式中：表示節(jié)點(diǎn)ci-1到ci的距離；表示節(jié)點(diǎn)ci的等待時(shí)間；為節(jié)點(diǎn)ci的剩余生存時(shí)間，并且均為歸一化表示。因此一次充電集合的點(diǎn)構(gòu)成的節(jié)點(diǎn)充電權(quán)重總和為：

定義2最優(yōu)充電序列：為MC 從發(fā)給節(jié)點(diǎn)充電到返回基站過程中充電集合的節(jié)點(diǎn)充電權(quán)重最小。表達(dá)式如下：

保證MC 有足夠的能量回到基站補(bǔ)充能量，因此優(yōu)化目標(biāo)還有如下約束：

2.3 基于策略梯度的求解框架

因?yàn)榍蠼釽RSN 充電序列是一個(gè)NP-hard 問題，并且傳統(tǒng)的求解方法很難求得滿足實(shí)際需求的最優(yōu)解，而采用策略梯度的方法去求解，能夠更好地避免求解陷入到局部最優(yōu)解，因此采用策略梯度的方法對(duì)式（24）進(jìn)行求解，將各個(gè)充電權(quán)重qi(t)可以看作一權(quán)重圖，利用seq2seq 在處理序列模型的優(yōu)勢(shì)，結(jié)合Attention 對(duì)充電序列進(jìn)行求解，具體策略梯度模型如圖1 所示。將其分成兩個(gè)神經(jīng)網(wǎng)絡(luò)，一個(gè)為輸出網(wǎng)絡(luò)，一個(gè)為基線網(wǎng)絡(luò)，通過不斷的訓(xùn)練，利用充電序列的總充電權(quán)重作為評(píng)價(jià)標(biāo)準(zhǔn)，求得最優(yōu)解，具體網(wǎng)絡(luò)結(jié)構(gòu)如圖2 所示。在選擇下一個(gè)充電節(jié)點(diǎn)時(shí)，將各節(jié)點(diǎn)到MC 的距離、等待時(shí)間、剩余生存時(shí)間作為輸入，Encoder 輸出都與Decoder 該時(shí)間步的輸出作點(diǎn)乘得到Attention Score，然后計(jì)算所有Score的概率分布的Attention distribution，在選擇Attention output 時(shí)，輸出神經(jīng)網(wǎng)絡(luò)采用的辦法是選擇前k大的概率分布，然后隨機(jī)選擇一個(gè)作為輸出，k取3，而基線神經(jīng)網(wǎng)絡(luò)采用的是貪婪策略，即選擇概率分布最大的。

圖1 策略梯度模型圖

圖2 seq2seq 結(jié)合Attention

具體MC 的充電流程如下：估算節(jié)點(diǎn)剩余生存時(shí)間，通過節(jié)點(diǎn)到MC 的距離、等待時(shí)間、剩余生存時(shí)間作為網(wǎng)絡(luò)的輸入，然后根據(jù)網(wǎng)絡(luò)選擇要充電的節(jié)點(diǎn)，加入充電回路，獲得該步的充電權(quán)重，當(dāng)MC 能量即將耗盡，返回基站時(shí)，得到最終的充電回路path 和獲得的累積充電權(quán)重，為了能獲取最優(yōu)的參數(shù)θ，采用策略梯度對(duì)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，使得達(dá)到預(yù)期最小化累積權(quán)重，策略梯度偽代碼如下：

算法1：PFSS 算法偽代碼

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

仿真實(shí)驗(yàn)使用Python 語言，使用Pytorch 深度學(xué)習(xí)框架模擬WRSN 的能量補(bǔ)充過程，并且與不同的能量補(bǔ)充方案進(jìn)行比較，驗(yàn)證提出算法的性能，建立100 m×100 m 的區(qū)域，具體參數(shù)參考文獻(xiàn)[17]設(shè)置默認(rèn)值取值范圍，如表1 所示。

表1 仿真參數(shù)表

對(duì)比算法為NJNP[12]算法和DQN[17]算法，分別對(duì)比不同傳感器數(shù)目、MC 的移動(dòng)速度對(duì)網(wǎng)絡(luò)的失效率、充電延遲、充電代價(jià)的影響。

失效率表示在整個(gè)充電周期中，因未能及時(shí)得到能量補(bǔ)充而失效的節(jié)點(diǎn)數(shù)與總的請(qǐng)求節(jié)點(diǎn)數(shù)的比率。

充電延遲表示在整個(gè)充電周期中，從發(fā)出充電請(qǐng)求到響應(yīng)最長(zhǎng)之間的時(shí)間間隔。

充電代價(jià)表示在整個(gè)充電周期中MC 移動(dòng)的距離。

3.1 傳感器數(shù)目對(duì)性能的影響

本組實(shí)驗(yàn)研究傳感器數(shù)目對(duì)算法性能的影響，令其他參數(shù)維持默認(rèn)值，傳感器數(shù)目為30~100 個(gè)，模擬1 000 組數(shù)據(jù)，各個(gè)算法性能變化如圖3 所示。

圖3 傳感器數(shù)目對(duì)性能的影響

如圖3a）和圖3b）所示，各個(gè)算法的失效率和充電延遲隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增多而上升，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，發(fā)送充電請(qǐng)求也增多，MC 的服務(wù)能力是有限的，超出MC 的服務(wù)能力，失效節(jié)點(diǎn)數(shù)量就會(huì)增加，節(jié)點(diǎn)等待的時(shí)間就會(huì)增加，可以看到PFSS 算法的失效率始終低于另外兩種算法，而且充電延遲受節(jié)點(diǎn)數(shù)影響不大，這是因?yàn)楸疚乃惴ǖ某潆姍?quán)重考慮了節(jié)點(diǎn)剩余生存時(shí)間和節(jié)點(diǎn)等待時(shí)間，通過策略梯度進(jìn)行訓(xùn)練，能選擇更加適合需要充電的節(jié)點(diǎn)，避免節(jié)點(diǎn)死亡，降低了最長(zhǎng)充電延遲。

由圖3c）可以看出，PFSS 的充電代價(jià)是最高的，其次是DQN，最好的是NJNP 算法，這是因?yàn)镹JNP 算法選擇的是距離最近的需要充電的節(jié)點(diǎn)，隨著節(jié)點(diǎn)數(shù)的增加，節(jié)點(diǎn)之間的距離越來越近，NJNP 算法在充電代價(jià)上的優(yōu)勢(shì)明顯，而DQN 算法是以失效節(jié)點(diǎn)數(shù)與MC 的移動(dòng)距離作為獎(jiǎng)勵(lì)函數(shù)，其節(jié)點(diǎn)失效率較NJNP 好，充電代價(jià)較PFSS 低，但是其沒有考慮充電延遲，因此其在失效率跟充電延遲方面較PFSS 差。雖然PFSS 的充電代價(jià)較高，但是其以付出充電代價(jià)來換取較低的充電延遲和節(jié)點(diǎn)失效率，并且充電代價(jià)與DQN 算法相差較小，因此PFSS 的充電代價(jià)雖然是三種算法中表現(xiàn)最差的，但與別的算法差距不算大，結(jié)合另外兩個(gè)性能指標(biāo)，PFSS 的充電代價(jià)在可接受的范圍內(nèi)。

3.2 MC 的移動(dòng)速度對(duì)性能的影響

本組實(shí)驗(yàn)研究MC 的移動(dòng)速度對(duì)算法性能的影響，令其他參數(shù)維持默認(rèn)值，MC 的移動(dòng)速度從1~7 m/s 逐漸變化，模擬1 000 組數(shù)據(jù)，各個(gè)算法性能的變化如圖4所示。

圖4 MC 的移動(dòng)速度對(duì)性能的影響

如圖4a）和圖4b）所示，各個(gè)算法的失效率和充電延遲隨著MC 速度增加而下降，這是因?yàn)殡S著MC 速度的增加，從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)消耗的時(shí)間減少，MC 能夠更快地響應(yīng)更多的節(jié)點(diǎn)，因此失效的節(jié)點(diǎn)數(shù)和充電延遲都下降。

如圖4c）所示，各個(gè)算法的充電代價(jià)隨著MC 速度增加而上升，這是因?yàn)殡S著MC 速度的增加，響應(yīng)的節(jié)點(diǎn)數(shù)增加，導(dǎo)致MC 的移動(dòng)距離增大，因此充電代價(jià)隨著充電效率的增加而增加。

4 結(jié) 語

本文提出了一種WRSN 中保證響應(yīng)公平策略，使MC 在節(jié)點(diǎn)能耗動(dòng)態(tài)變化的情況下，MC 能公平響應(yīng)節(jié)點(diǎn)的充電需求，降低節(jié)點(diǎn)等待時(shí)間，降低失效節(jié)點(diǎn)數(shù)，并且盡可能地減少M(fèi)C 的移動(dòng)能耗。利用過往節(jié)點(diǎn)能量記錄對(duì)節(jié)點(diǎn)能耗進(jìn)行估算，將節(jié)點(diǎn)到MC 的距離、等待時(shí)間、剩余生存時(shí)間作為策略網(wǎng)絡(luò)的輸入，采用seq2seq 與Attention 結(jié)合的網(wǎng)絡(luò)結(jié)構(gòu)，輸出應(yīng)該充電的節(jié)點(diǎn)。仿真實(shí)驗(yàn)結(jié)果表明，PFSS 方案能夠有效降低失效節(jié)點(diǎn)的數(shù)量、充電延遲，并且盡可能地降低充電代價(jià)。