基于選址機制與深度強化學習的WRSN移動能量補充

王 倩

（1.昆明理工大學信息工程與自動化學院，云南 昆明 650500；2.昆明理工大學云南省計算機技術(shù)應(yīng)用重點實驗室，云南 昆明 650500）

0 引 言

無線可充電傳感器網(wǎng)絡(luò)（Wireless Rechargeable Sensor Network, WRSN）[1]通過配備可移動充電裝置（Mobile Charger, MC）能從根本上解決傳感器能量受限的問題，被廣泛應(yīng)用于戰(zhàn)場監(jiān)測[2]、生態(tài)系統(tǒng)監(jiān)測[3-4]、交通監(jiān)測[5]等信息感知領(lǐng)域，具有傳感器節(jié)點密集且分布范圍廣泛的特點。一對多能量補充技術(shù)通過適當調(diào)整發(fā)送器和接收器線圈的工作頻率[6]，MC 可以同時為多個傳感器充電，從而有效提高能量傳輸效率，更能適應(yīng)規(guī)模較大、節(jié)點數(shù)目眾多WRSN 的應(yīng)用場景。

在WRSN 一對多充電方案中MC 充電駐點的選取以及充電路徑的規(guī)劃是實現(xiàn)高效能量補充的兩個關(guān)鍵因素，目前大多數(shù)相關(guān)研究將其構(gòu)造為組合優(yōu)化問題。文獻[7]將一對多充電問題歸約成覆蓋TSP 問題，首先采用PSO 算法得到MC 充電駐點，然后采用LKH 算法構(gòu)造遍歷這些駐點的最小TSP 回路。文獻[8]提出一種基于加權(quán)啟發(fā)式的充電策略GOCS，計算出充電優(yōu)先級，搶占式按需充電。隨著機器學習的發(fā)展，文獻[9]引入時間窗的概念表示充電需求，基于傳感器的時間窗信息和能量信息，將DQN 引入用于確定MC 的充電路徑?？梢钥吹剑瑢C器學習與充電策略相結(jié)合有利于提高MC 的自主性，實時響應(yīng)充電請求。

由于同時考慮組合優(yōu)化問題的解空間復雜度過大，本文將能量補充問題離散化為駐點選取和路徑規(guī)劃兩個子問題進行求解。針對上述問題，本文提出一種基于選址機制與深度強化學習的一對多充電策略（One-tomany Charging Strategy Based on Reinforcement Learning,MSRL）。本文采用預先設(shè)置駐點的方式對傳感器節(jié)點進行能量分批管理，實現(xiàn)網(wǎng)絡(luò)的全覆蓋。首先將充電駐點選取問題抽象為選址問題中的集合覆蓋問題，通過WSC_RA[10]算法求解出最優(yōu)充電駐點集。在確定駐點位置后，引入充電獎勵，基于Dueling DQN 得到充電調(diào)度的最優(yōu)策略，實時動態(tài)提供充電方案，延長WRSN 網(wǎng)絡(luò)壽命。

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

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

本文的網(wǎng)絡(luò)模型如圖1 所示，在網(wǎng)絡(luò)覆蓋區(qū)域隨機部署N個傳感器節(jié)點V={v1,v2,…,vn}，vi代表第i個傳感器節(jié)點，節(jié)點具有監(jiān)控自身剩余能量、數(shù)據(jù)融合的能力；基站位置固定位于網(wǎng)絡(luò)中心，為MC 供應(yīng)能量且能量不受限。當傳感器剩余能量低于充電閾值時，傳感器節(jié)點會通過多跳通信的方式向基站發(fā)送充電請求，基站再將充電請求轉(zhuǎn)發(fā)給MC。MC 為帶有高容量無線充電電源的移動設(shè)備，具有強大的計算能力和足夠的服務(wù)池來接收充電請求，當收到充電請求后沿著充電路徑訪問充電駐點P={p1,p2,…,pm}，并為覆蓋范圍內(nèi)的傳感器節(jié)點以一對多的方式充電。因此根據(jù)模型假設(shè)和相關(guān)定義，在表1 中列出了主要的參數(shù)符號，此外還進一步給出了充電駐點的定義。

表1 主要參數(shù)符號

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

定義1：充電駐點即MC 預設(shè)停靠位置。MC 在網(wǎng)絡(luò)中停靠時才對傳感器進行充電行為。

1.2 問題描述

WRSN 可持續(xù)穩(wěn)定工作對確保監(jiān)控質(zhì)量至關(guān)重要，為了衡量MC 的充電性能，將一次充電周期結(jié)束后，網(wǎng)絡(luò)中所有傳感器節(jié)點的平均剩余能量定義為網(wǎng)絡(luò)平均剩余能量，如式（1）所示：

與此同時，傳感器節(jié)點失效時無法保證網(wǎng)絡(luò)的連通性，會產(chǎn)生數(shù)據(jù)丟失、網(wǎng)絡(luò)斷開等問題[11]，如何最小化節(jié)點失效數(shù)，是充電方案中要解決的關(guān)鍵問題。因此，本文引入傳感器節(jié)點死亡數(shù)DN作為衡量充電方案性能的主要指標之一，并且假設(shè)t時刻MC 剩余電量為Et，此時距離基站距離為dt。表述受限的組合優(yōu)化問題為：

式中：Et≥c*dt表示限制MC 在移動過程中任意時刻的電量，可以保證其返回基站。

2 MSRL 策略設(shè)計與實現(xiàn)

2.1 確定候選充電駐點集

以優(yōu)化MC 移動距離為目標，為MC 確定合適的充電駐點位置，實現(xiàn)全覆蓋的同時充電駐點數(shù)最少。確定候選充電駐點位置的具體步驟如下：

1）以每個傳感器為圓心，充電距離為Cr半徑作圓，求出圓與圓之間的交點。

2）當兩圓之間存在兩個交點時，基于向心法則選擇距離基站位置較近的交點，將其加入候選充電駐點集合U。

3）當兩圓之間只有一個交點時，則將該點加入候選充電駐點集合U。

4）若存在獨立的圓，即不與其他圓相交，則將該圓圓心加入候選充電駐點集合U。

如圖2 所示，以傳感器節(jié)點為圓心作圓，黑色菱形即為候選充電駐點位置。由于此方法得出的充電駐點數(shù)量較大，不利于求解最短充電路徑，接下來將基于選址問題中的帶權(quán)集合覆蓋問題，求得最優(yōu)充電駐點集。

圖2 確定候選充電駐點

2.2 確定最優(yōu)充電駐點集

考慮到駐點選取問題與選址問題的相似性，將駐點選取問題抽象成帶權(quán)集合覆蓋問題，則是求解滿足覆蓋所有傳感器節(jié)點的前提下，充電駐點總的位置個數(shù)最少且距離最小的問題。對于傳感器節(jié)點集合V={v1,v2,…,vn}，候選充電駐點集合U={u1,u2,…,um}，定義候選充電駐點到基站的距離為權(quán)值。將駐點選取問題轉(zhuǎn)換為求解帶權(quán)集合覆蓋問題，其形式化定義如下：

輸入：V={v1,v2,…,vn}，U={u1,u2,…,um}，W(U) ={w(r1),w(r2),…,w(rm)}(w(ri) > 0,1 ≤i≤m)， 其中ui?V,1 ≤i≤m。

輸出：C?U，∪uk=V，且最小化∑w(uk)，uk∈C。

為確定最優(yōu)駐點集合，本文通過帶權(quán)集合覆蓋問題的一種隨機近似算法WSC_RA，從概率的角度出發(fā)，多次運行求得最優(yōu)覆蓋集合。此外該算法時間復雜度O(n)遠小于解決集合覆蓋問題最常用的貪婪算法，其優(yōu)化結(jié)果如圖3 所示，五角星位置表示最終確定的充電駐點。

圖3 確定最優(yōu)充電駐點

2.3 基于競爭深度Q 網(wǎng)絡(luò)的充電路徑規(guī)劃算法

2.3.1 學習模型

本文基于馬爾科夫模型對文中描述的充電場景進行建模，將無線可充電傳感器網(wǎng)絡(luò)視為強化學習中的環(huán)境，將負責執(zhí)行充電決策的MC 視為智能體。該模型可以由四元組表示，其中S是狀態(tài)空間，A是動作空間，P是狀態(tài)遷移模型，R是即時獎勵[12]，具體建模如下：

1）狀態(tài)空間S：該模型的狀態(tài)由MC 的剩余電量和WRSN 中所有傳感器節(jié)點的狀態(tài)兩部分組成。

式中：EMC表示MC 的剩余電量；Snetwork表示傳感器節(jié)點的狀態(tài)集合；si表示第i個傳感器節(jié)點的狀態(tài)，由兩部分組成，即坐標位置信息(xi,yi)、剩余能量信息rei。

si的表達式如式（5）所示：

2）動作空間A：MC 的基本動作集合A中包含2 種基本動作，如式（6）所示：

當a=m+ 1，表示MC 返回基站進行能量補充；當a=i(i∈{1,2,…,m})，表示MC 移動到第i個充電駐點處進行充電任務(wù)。為避免電池過度充電，只給MC 充電覆蓋范圍內(nèi)低于能量閾值的傳感器充電。

3）即時獎勵：智能體通過即時獎勵的反饋來評價動作的好壞，因此獎勵函數(shù)的設(shè)定對于強化學習至關(guān)重要。在本文中，MC 在t時刻執(zhí)行動作結(jié)束后得到的即時獎勵從三個方面綜合考慮，定義為：

①表示路徑獎勵，用于引導優(yōu)先考慮距離較近的充電駐點，其與MC 從上一個充電駐點移動到當前充電駐點的距離l成反比，如式（8）所示：

②用于懲罰網(wǎng)絡(luò)中的傳感器節(jié)點死亡，如果當前執(zhí)行的動作導致傳感器節(jié)點能量耗盡失效，則給MC一個負獎勵值，見式（9）：

式中：DN 代表一次充電動作結(jié)束后傳感器節(jié)點死亡數(shù)；K代表常數(shù)系數(shù)。

③表示充電獎勵，用于引導優(yōu)先給能量較低的傳感器節(jié)點進行充電，一方面可以避免傳感器節(jié)點死亡，另一方面可以提高MC 的充電效率，見公式（10）：

式中k表示MC 在當前充電駐點時，其充電覆蓋范圍內(nèi)傳感器節(jié)點的數(shù)量。

綜上所述，獎勵函數(shù)可以表示為式（11）：

2.3.2 基于Gradient Bandit 策略采樣

強化學習中通常認為獎勵值越高的動作與環(huán)境交互表現(xiàn)越好，越具有學習價值?；贕radient Bandit 策略采樣，根據(jù)獎勵值進行重要性評估，給每條經(jīng)驗數(shù)據(jù)設(shè)置一個偏好度。當經(jīng)驗獎勵值越高，偏好度越高，經(jīng)驗被選中的概率也就越高；反之亦然。在該方法中，首先將所有經(jīng)驗的偏好度Ht(ei)初始化為0，將經(jīng)驗數(shù)據(jù)的平均獎勵值作為基線，根據(jù)基線設(shè)置各個經(jīng)驗的偏好度。每個時間步t時，當有新的經(jīng)驗數(shù)據(jù)加入經(jīng)驗池，會更新平均立即獎勵值，從而更新偏好度。偏好度Ht(ei)的更新公式見式（12）：

式中：ψ為步長影響因子；ri表示經(jīng)驗池中第i條經(jīng)驗的立即獎勵值；rˉ為平均立即獎勵值；Pt-1(ei)表示第t-1時間步時采樣第i條經(jīng)驗的概率，其計算公式如式（13）所示：

2.3.3 基于競爭深度Q網(wǎng)絡(luò)的充電路徑規(guī)劃算法實現(xiàn)

在WRSN 能量補充場景中，當網(wǎng)絡(luò)中死亡節(jié)點較多時，無論MC 采取何種動作所得到的即時獎勵可能還是很小的，此時下一步的狀態(tài)主要取決于當前狀態(tài)?？紤]到這種情況，將原網(wǎng)絡(luò)的輸出層替換成基于競爭架構(gòu)的兩個全連接層：價值函數(shù)V和動作優(yōu)勢函數(shù)A。其中V表示狀態(tài)環(huán)境本身具有的價值，A表示選擇某個動作額外帶來的價值。為體現(xiàn)動作優(yōu)勢貢獻的唯一性，一般要將動作優(yōu)勢函數(shù)設(shè)置為動作優(yōu)勢減去當前狀態(tài)下所有動作優(yōu)勢的均值，這樣可以保證在該狀態(tài)下各動作的優(yōu)勢函數(shù)相對排序不變，提高算法穩(wěn)定性。Q函數(shù)如公式（14）所示：

式中：S、A分別表示當前狀態(tài)和當前選擇的動作；θ、β、α分別是神經(jīng)網(wǎng)絡(luò)參數(shù)、價值函數(shù)的參數(shù)、動作參數(shù)。本文提出基于競爭深度Q網(wǎng)絡(luò)的充電路徑規(guī)劃算法執(zhí)行框架如圖4 所示，執(zhí)行算法見算法1。

圖4 充電路徑規(guī)劃算法框架

算法1：基于競爭深度Q網(wǎng)絡(luò)的充電路徑規(guī)劃算法

①初始化網(wǎng)絡(luò)參數(shù)

②For each learning episodeedo

③初始化充電環(huán)境，得到初始狀態(tài)s0

④For each time steptdo

⑤根據(jù)ε-greedy 策略選擇動作at，并執(zhí)行獲得相應(yīng)的狀態(tài)st+1與獎勵rt

⑥存儲ei={st,at,rt,st+1}到經(jīng)驗池D和初始化Ht(ei)

⑧通過公式（12）更新偏好度

⑨利用公式（13）計算樣本被采樣的概率

⑩從回放經(jīng)驗池D中根據(jù)采樣概率采樣

?計算Q網(wǎng)絡(luò)標簽

?計算損失函數(shù)loss = (yt-Q(st,at;θ))2，更新參數(shù)

?每C步復制一次參數(shù)，Q'=Q

?End for

?End for

3 實驗與分析

3.1 實驗設(shè)置

本文構(gòu)建了一個無線傳感器網(wǎng)絡(luò)仿真環(huán)境，在100 m×100 m 的二維平面區(qū)域內(nèi)隨機部署90～150 個傳感器節(jié)點，基站位于網(wǎng)絡(luò)中心位置，MC 初始從基站出發(fā)，每充電一輪后回到基站進行能量補充。表2 中列舉出了所有的仿真參數(shù)。

表2 參數(shù)定義

3.2 比較方法

為了有效地評估本文提出的MSRL 算法，將與以下3 種算法進行實驗性能比較分析，其方法介紹如下所示：

1）TSCA[13]：始終選擇最先發(fā)出充電請求的駐點位置。

2）NJNP[14]：選擇發(fā)出充電請求距離最近的駐點位置。

3）GOCS[8]：是一種一對多充電算法，根據(jù)剩余能量、貢獻價值、歐氏距離等計算出充電權(quán)重，搶占式的按需充電。

3.3 MSRL 算法收斂性實驗

基于Pytorch 深度強化學習框架對MSRL 算法的神經(jīng)網(wǎng)絡(luò)部分進行訓練，設(shè)置1 200 個訓練周期，其中從MC 任務(wù)開始直到返回基站為一個周期。算法的收斂性訓練結(jié)果如圖5 所示，展示了算法周期獎勵回報曲線。在智能體自探索階段，被設(shè)置為一個較大的數(shù)值，以確保較高的探索可能性。隨著訓練周期的增加，經(jīng)驗的逐步累積，逐漸降低其探索率，減少至0.1 時不再明顯變化，直到完全收斂。

圖5 訓練過程中周期獎勵回報收斂曲線

3.4 傳感器節(jié)點死亡數(shù)量比較分析實驗

本組實驗考慮各算法在不同節(jié)點數(shù)量和不同充電速率下的網(wǎng)絡(luò)中節(jié)點死亡情況。圖6a）表示充電速率為20 W 時，節(jié)點死亡數(shù)隨著網(wǎng)絡(luò)中傳感器節(jié)點數(shù)量增加的變化曲線圖，可以看出當網(wǎng)絡(luò)中傳感器數(shù)量較少時，需要充電的節(jié)點也較少，MC 可以滿足充電任務(wù)，MSRL 相比其他3 種算法的提升較少；當傳感器數(shù)量較多時，需要充電的節(jié)點也增多，這時MSRL 相較其他3 種算法優(yōu)勢更加明顯。這是由于隨著網(wǎng)絡(luò)中傳感器數(shù)量的增加，網(wǎng)絡(luò)中的充電請求增加，MSRL 算法優(yōu)先引導MC 給能量較低的傳感器節(jié)點進行充電，從而減少節(jié)點死亡數(shù)。而GOCS 算法的引導作用有限，NJNP、TSCA 算法無法優(yōu)先給能量較低的節(jié)點進行充電，節(jié)點死亡數(shù)較高。而通過圖6b）可以發(fā)現(xiàn)，當充電速率與節(jié)點死亡數(shù)呈負相關(guān)時，MSRL 算法依然優(yōu)于其他3 種比較算法。

圖6 網(wǎng)絡(luò)中節(jié)點死亡變化趨勢

3.5 網(wǎng)絡(luò)生存時間比較分析實驗

網(wǎng)絡(luò)生存時間被定義為MC 從基站出發(fā)后，直到網(wǎng)絡(luò)中第一個傳感器死亡的時間，是無線傳感器網(wǎng)絡(luò)的重要衡量標準之一。圖7a）中網(wǎng)絡(luò)生存時間隨著傳感器節(jié)點數(shù)的增加而降低，這是由于隨著節(jié)點數(shù)量增多，網(wǎng)絡(luò)中的充電請求增多。MC 無法應(yīng)對那么多的充電請求，傳感器節(jié)點的等待時間變長，導致節(jié)點能量耗盡而死亡，網(wǎng)絡(luò)生存時間自然降低了。TSCA 優(yōu)先為最先發(fā)出充電請求的傳感器進行充電；GOCS 也對剩余能量較低的傳感器增加其充電優(yōu)先級，故表現(xiàn)較為良好；而MSRL 相比其他三種算法（NJNP、TSCA、GOCS）表現(xiàn)更好，這是因為RL 的探索機制增加了MC 為能量較低的傳感器提供充電服務(wù)的可能性，從而延長了網(wǎng)絡(luò)生存時間，其實驗結(jié)果具體如圖7b）所示。

圖7 網(wǎng)絡(luò)生存時間變化趨勢

3.6 能量消耗情況比較分析實驗

網(wǎng)絡(luò)中所有傳感器節(jié)點的平均剩余能量值如圖8所示。其中通過圖8a）可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)中傳感器數(shù)量的增加，4 種算法的平均剩余能量值均有所下降，但MSRL 算法執(zhí)行的結(jié)果始終優(yōu)于其他3 種算法，這是由于MSRL 可以減少MC 的移動能耗，使更多的能量用于傳感器充電。當網(wǎng)絡(luò)中傳感器數(shù)量為100、充電速率為20 W 時，相比NJNP、TSCA 和GOCS 分別有20.41%、28.71%、10.32%的提升。由此可以看出算法在降低能耗方面效果顯著，可以有效延長網(wǎng)絡(luò)壽命。而圖8b）則展示了網(wǎng)絡(luò)中平均剩余能量值與充電速率的關(guān)系，實驗結(jié)果表明MSRL 方法在同等情況下依舊要優(yōu)于另外3 種比較算法。

圖8 網(wǎng)絡(luò)中傳感器節(jié)點的平均剩余能量變化趨勢

4 結(jié) 論

本文設(shè)計了一種基于選址機制與深度強化學習的一對多充電策略用于解決WRSN 中的能量補充優(yōu)化問題。首先，MSRL 基于選址問題中的帶權(quán)集合覆蓋問題求解出近似最優(yōu)充電駐點集合，實現(xiàn)對傳感器網(wǎng)絡(luò)全覆蓋的同時駐點數(shù)最小；其次，設(shè)計了一種基于競爭Q網(wǎng)絡(luò)的充電路徑規(guī)劃算法動態(tài)地調(diào)整充電路徑。仿真實驗結(jié)果表明，本文提出的MSRL 在降低傳感器節(jié)點死亡數(shù)和延長網(wǎng)絡(luò)壽命等方面都優(yōu)于比較方法。此外，MSRL 策略存在通過預設(shè)駐點導致充電移動距離增加的局限性，因此未來將考慮通過動態(tài)選取駐點位置來進一步地降低充電代價作為研究方法。

注：本文通訊作者為王倩。