葉健鋒

（昆明理工大學，云南 昆明 650500）

0 引 言

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

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

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

通過分析現有的工作，存在以下問題：

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

2）MC 響應節(jié)點的充電請求不具有公平性，存在節(jié)點因等待時間過長而失效；

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

本文的主要貢獻如下：

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

2）利用過往的節(jié)點能量記錄對節(jié)點實時能耗進行估算；

3）引入一個新的評估標準充電權重來評估一組充電序列的質量，并且參考文獻[15]采用seq2seq 與Attention 結合的網絡來求解充電序列，并通過策略梯度對神經網絡進行訓練；

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

1 網絡模型與問題描述

1.1 WRSN 模型

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

1.2 節(jié)點模型

根據文獻[16]物理模型，傳感節(jié)點能耗主要由兩個方面組成：

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

接收能耗：接收電路。

能耗模型如下：

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

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

則：

在t時刻第i個節(jié)點的能耗模型如下：

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

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

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

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

2 PFSS 策略設計實現

2.1 節(jié)點能耗估算

采用過往的節(jié)點能耗對將來節(jié)點能耗進行估算，設網絡初始時間為0，時間間隔為Δ，節(jié)點將當前剩余電量(t)發(fā)送給基站，則節(jié)點實時能耗pi,t為：

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

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

這樣需要基站保存所有的歷史數據，導致基站的存儲代價會隨著時間的推移越來越大，因此改進式（11）為：

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

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

因此，為了更加準確地估算能量消耗率，也需要對偏差值進行估算，采用基于過往經驗的方法進行預測，得到以下公式：

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

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

2.2 充電權重

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

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

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

因此，節(jié)點ci的相應等待時間為:

為了提高MC 的能量利用率，降低節(jié)點的等待時間，減少節(jié)點的失效率，構建充電回路的優(yōu)化目標為：

式中Count(< 0)表示節(jié)點剩余生存時間小于節(jié)點等待時間的個數，即失效節(jié)點數。

由優(yōu)化目標可以看出：構建的充電回路MC 移動的距離應盡可能的少；節(jié)點的等待時間應盡可能的少；節(jié)點的剩余生存時間應盡可能的多，因此定義充電權重q來衡量一個充電周期的好壞。

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

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

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

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

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

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

圖1 策略梯度模型圖

圖2 seq2seq 結合Attention

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

算法1：PFSS 算法偽代碼

3 仿真實驗

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

表1 仿真參數表

對比算法為NJNP[12]算法和DQN[17]算法，分別對比不同傳感器數目、MC 的移動速度對網絡的失效率、充電延遲、充電代價的影響。

失效率表示在整個充電周期中，因未能及時得到能量補充而失效的節(jié)點數與總的請求節(jié)點數的比率。

充電延遲表示在整個充電周期中，從發(fā)出充電請求到響應最長之間的時間間隔。

充電代價表示在整個充電周期中MC 移動的距離。

3.1 傳感器數目對性能的影響

本組實驗研究傳感器數目對算法性能的影響，令其他參數維持默認值，傳感器數目為30~100 個，模擬1 000 組數據，各個算法性能變化如圖3 所示。

圖3 傳感器數目對性能的影響

如圖3a）和圖3b）所示，各個算法的失效率和充電延遲隨著網絡節(jié)點數量的增多而上升，這是因為隨著節(jié)點數量的增多，發(fā)送充電請求也增多，MC 的服務能力是有限的，超出MC 的服務能力，失效節(jié)點數量就會增加，節(jié)點等待的時間就會增加，可以看到PFSS 算法的失效率始終低于另外兩種算法，而且充電延遲受節(jié)點數影響不大，這是因為本文算法的充電權重考慮了節(jié)點剩余生存時間和節(jié)點等待時間，通過策略梯度進行訓練，能選擇更加適合需要充電的節(jié)點，避免節(jié)點死亡，降低了最長充電延遲。

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

3.2 MC 的移動速度對性能的影響

本組實驗研究MC 的移動速度對算法性能的影響，令其他參數維持默認值，MC 的移動速度從1~7 m/s 逐漸變化，模擬1 000 組數據，各個算法性能的變化如圖4所示。

圖4 MC 的移動速度對性能的影響

如圖4a）和圖4b）所示，各個算法的失效率和充電延遲隨著MC 速度增加而下降，這是因為隨著MC 速度的增加，從一個節(jié)點移動到另一個節(jié)點消耗的時間減少，MC 能夠更快地響應更多的節(jié)點，因此失效的節(jié)點數和充電延遲都下降。

如圖4c）所示，各個算法的充電代價隨著MC 速度增加而上升，這是因為隨著MC 速度的增加，響應的節(jié)點數增加，導致MC 的移動距離增大，因此充電代價隨著充電效率的增加而增加。

4 結 語

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