王 倩
(1.昆明理工大學信息工程與自動化學院,云南 昆明 650500;2.昆明理工大學云南省計算機技術(shù)應(yīng)用重點實驗室,云南 昆明 650500)
無線可充電傳感器網(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ò)壽命。
本文的網(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ò)中停靠時才對傳感器進行充電行為。
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 在移動過程中任意時刻的電量,可以保證其返回基站。
以優(yōu)化MC 移動距離為目標,為MC 確定合適的充電駐點位置,實現(xiàn)全覆蓋的同時充電駐點數(shù)最少。確定候選充電駐點位置的具體步驟如下:
1)以每個傳感器為圓心,充電距離為Cr半徑作圓,求出圓與圓之間的交點。
2)當兩圓之間存在兩個交點時,基于向心法則選擇距離基站位置較近的交點,將其加入候選充電駐點集合U。
3)當兩圓之間只有一個交點時,則將該點加入候選充電駐點集合U。
4)若存在獨立的圓,即不與其他圓相交,則將該圓圓心加入候選充電駐點集合U。
如圖2 所示,以傳感器節(jié)點為圓心作圓,黑色菱形即為候選充電駐點位置。由于此方法得出的充電駐點數(shù)量較大,不利于求解最短充電路徑,接下來將基于選址問題中的帶權(quán)集合覆蓋問題,求得最優(yōu)充電駐點集。
圖2 確定候選充電駐點
考慮到駐點選取問題與選址問題的相似性,將駐點選取問題抽象成帶權(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.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
本文構(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ù)定義
為了有效地評估本文提出的MSRL 算法,將與以下3 種算法進行實驗性能比較分析,其方法介紹如下所示:
1)TSCA[13]:始終選擇最先發(fā)出充電請求的駐點位置。
2)NJNP[14]:選擇發(fā)出充電請求距離最近的駐點位置。
3)GOCS[8]:是一種一對多充電算法,根據(jù)剩余能量、貢獻價值、歐氏距離等計算出充電權(quán)重,搶占式的按需充電。
基于Pytorch 深度強化學習框架對MSRL 算法的神經(jīng)網(wǎng)絡(luò)部分進行訓練,設(shè)置1 200 個訓練周期,其中從MC 任務(wù)開始直到返回基站為一個周期。算法的收斂性訓練結(jié)果如圖5 所示,展示了算法周期獎勵回報曲線。在智能體自探索階段,被設(shè)置為一個較大的數(shù)值,以確保較高的探索可能性。隨著訓練周期的增加,經(jīng)驗的逐步累積,逐漸降低其探索率,減少至0.1 時不再明顯變化,直到完全收斂。
圖5 訓練過程中周期獎勵回報收斂曲線
本組實驗考慮各算法在不同節(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é)點死亡變化趨勢
網(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ò)生存時間變化趨勢
網(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é)點的平均剩余能量變化趨勢
本文設(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)選取駐點位置來進一步地降低充電代價作為研究方法。
注:本文通訊作者為王倩。