基于強化學習的充電調度策略研究

張世豪

（四川大學計算機學院，成都610065）

0 引言

隨著現代微電子技術與自組織網絡的發展，無線傳感器網絡受到了廣泛的關注。傳感器網絡已成為收集數據與信息的主要手段之一。現如今，無線傳感器網絡的應用已隨處可見，例如城市設施監測、海洋水質監測、軍事監控、橋梁檢測和消防監測，等等。而監測數據的獲取是依靠環境中部署的大量無線傳感器節點來實現的。為了保證傳感器網絡的檢測質量，需要節點之間保持連通性和覆蓋性，者對無線傳感器節點的電池提出了較高要求。

然而，無線傳感器節點因體積有限，導致只能采使用小型電池模塊進行供電。因此，電池容量的大小限制了其工作時長，從而也限制了整個網絡的運行壽命。如何設計一種長期運行的傳感器網絡演變成了當下需要考慮與解決的基本問題。目前，已提出的充電技術有節能計算[1]、環境能量收集計算[2]和人工更換電池方案[3]，但是這些技術都存在一定缺陷，例如：節能技術只能減緩能量消耗，能量收集技術依賴于環境造成并不能穩定供能，而人工更換電池方案會消耗大量的人力物力造成成本較高。因此，亟需一種新的充電方式來延長網絡的壽命。幸運的是，得益于Kurs 等人[4]在無線能量傳輸技術上的突破，使得無線能量傳輸技術逐漸成為解決傳感器能量有限的有前途的方法。在這種技術下，我們通常使用一輛帶有能量發射裝置的無線充電車，來為傳感器節點傳輸能量。這種方式可以主動地對需要充電的傳感器補充能量以滿足應用場景的需求。基于此，如何調度無線充電車構造充電路徑并為傳感器節點提供充電服務成為我們需要研究的重點。

1 網絡模型

在一個無線傳感器網絡中，包含一座基站（BS）和N 個傳感器節點。我們派遣一輛無線充電車從BS 出發為傳感器節點進行充電。我們定義當傳感器的剩余能量re小于閾值時，傳感器節點生成充電請求，以此來引導充電車選擇停靠位置并構造路徑。假定傳感器節點和充電車的總電池容量分別被定義為bsensor和Bcar。此外，我們定義無線充電車的充電半徑為r，當充電車與傳感器節點之間的距離d小于半徑r時，便能對其進行充電。傳感器節點與無線充電車當前坐標之間的距離計算采用歐幾里得公式，如公式（1）：

其中xsensor和ysensor代表節點的坐標信息，xcar和ycar代表當前充電車的坐標位置。

與其他一些研究策略[5]不同。我們不僅將無線充電車調度到傳感器上停止，還可以根據充電半徑的形成一些相交點上停靠，使得有更多備選的停靠位置可供選擇。同時，由于在無線能量的傳輸過程中存在能量損耗，所以我們引入了一個恒定的衰減率λ，傳感器實際獲取的能量為無線充電車原始發射能量的λ倍。具體的充電模型如圖1 所示。

圖1 網絡模型圖

2 問題描述

本文在一個無線傳感器網絡中研究了調度一輛無線充電車為N 個傳感器節點補充能量并規劃和構成充電路徑的問題，使得無線充電車在完成一個充電周期后，形成一條完整充電回路。同時，無線充電車不僅限于被停靠于傳感器上，且能停靠在充電半徑相交圓的交點之上。由于備選停靠點數量的增加導致加大了計算復雜度，因此為了提高網絡性能、降低計算難度，我們提出一種基于強化學習的學習算法來解決該問題。

3 強化學習算法

本節首先介紹一些必要的強化學習（RL）背景。其次，引出在本文無線傳感器網絡場景下的RL 模型。隨后再提出我們基于RL 的充電調度算法。

3.1 RL背景

RL 主要包含兩個主體：一個是Agent，通常也被稱作為智能體，而另一個是Environment，即外部環境。RL 的本質是一種交互式學習，其特征是相較于傳統算法，其不僅會考慮短期收益情況，而且還會將長期收益考慮在內。智能體的學習與訓練過程需要狀態、動作和獎勵三個部分來支撐和引導。主要流程為智能體根據當前環境狀態選擇某個充電的動作，網絡環境根據該動作反饋一定的獎勵值給智能體。若獎勵值為正，則會引導智能體繼續傾向于執行正獎勵相關的動作策略；若獎勵值為負，則智能體會自主學習和判斷，以在后續步驟中盡可能避免執行帶來負面結果的動作。

3.2 RL模型

RL 模型最關鍵的三部分分別為動作、狀態和獎勵。在我們的網絡模型中，我們定義首先定義動作為所有備選的停靠點，即不僅包含了所有傳感器的坐標，還囊括了所有傳感器的在充電半徑下的相交圓的交點坐標。其次，定義狀態定義為所有傳感器的剩余能量，這樣定義是因為可以有助于無線充電車根據所有傳感器節點的剩余能量判斷應為哪些傳感器進行充電。最后，我們定義了一個獎勵函數來代表每次執行動作后，環境反饋給智能體的一個信號量，獎勵函數被形式化表示為如下：

其中K表示充電車停靠位置處充電范圍內所包含的所有傳感器節點的集合，而k表示集合中所屬的第k個傳感器節點。rek表示第k 個傳感器節點的剩余壽命。而DN表示網絡環境中死亡節點的數量。此外，α為一個參數因子，在實驗中我們設置α為100。我們將死亡節點的數量作為懲罰值使得智能體會盡可能選擇避免節點死亡的情況的行動策略。

3.3 基于RL的充電調度算法描述

我們基于RL 的Deep Q Network[6]來實現充電調度算法。學習算法采用雙重網絡結構來進行訓練，即包含評估網絡和現實網絡兩個網絡。我們將智能體的狀態信息作為評估網絡的輸入，網絡的輸出為傳感器網絡中所有的備選停靠點。網絡輸出值的大小衡量了選擇該停靠點帶來的收益，也即獎勵值。現實網絡具有與評估網絡相同的網絡結構，用于計算損失函數和神經網絡權重的更新。采用雙網絡結構能夠增加強化學習算法的穩定性。此外，我們定義損失函數為現實網絡與評估網絡輸出值的均方差。通過不斷地循環學習，最終達成無線充電車一輪的充電任務。具體算法過程如圖2 所示。

圖2 學習算法過程圖

4 實驗模擬

4.1 實驗環境設置

在本節中，我們對所提出的算法進行仿真實驗并對模擬結果進行對比。我們設置無線傳感器網絡的大小為100m×100m。在仿真模擬的網絡環境中隨機部署120-160 個傳感器節點，并將基站（BS）設置在網絡環境的中心，即無線充電車從網絡中心出發為傳感器節點提供能量補充服務。每一個傳感器節點與充電車的最大電池容量bsensor和Bcar分別為6KJ 和10KJ。因傳感器節點隨機初始化，所以節點初始電量的范圍是最大容量的0.2-0.9 倍之間，而傳感器的能量消耗速率隨機初始化為0.1J/s-0.2J/s。同時，無線充電車的充電半徑被設置為10m，充電能量消耗和移動能量 消耗分別為15W 和50J/m。

我們將我們所提出的基于RL 的充電算法（RLC）與基于貪婪策略的充電算法（GC）進行了對比。在GC中，無線充電車僅能停在傳感器節點上，并同時對充電半徑范圍內的所有節點進行充電。GC 的充電策略首先是尋找每個傳感器節點的鄰居節點，即以某節點為中心，充電半徑范圍內的所有節點都屬于該節點的鄰居節點，并將其劃分到同一個鄰居節點集合中。其次，再計算為每個鄰居集合充電能獲得的最大充電收益，充電收益的計算公式如下：

其中gi是在第i 個節點計算獲得的收益，Gainj是在第j 個節點處獲得的總收益，即鄰居節點集合內所有節點收益的總和。rei是第i 個傳感器節點的剩余電池電量。m表示在第j 節點處共有m 個數量的鄰居節點。

由于GC 算法的目的在于實現獲取收益的最大化，因此每次充電策略都是貪婪選擇的選擇鄰居集合充電收益最大的所在傳感器的位置。

4.2 結果與分析

我們從兩個方面來衡量兩個算法的性能，即死亡節點的數量（DN）和能量使用效率（EUR）。DN 表示當無線充電車完成運行一個充電周期后，所有電池耗盡的傳感器節點的數量，即我們稱為死亡節點數量。EUR 表示充電車真正用于為傳感器傳輸的能量占總能量消耗的比例。能量比例的計算公式表示為：

其中Et為無線充電路徑上消耗的能量，Ec為所有傳感器實際接收到的能量，El為能量傳輸過程中的損耗量。同時，在仿真實驗中設置損耗率λ為0.5。

圖3 死亡節點數量變化情況

圖4 能量利用效率變化情況

模擬結果如圖3 和圖4 所示。在圖3 中，我們可以看到，RLC 的死亡傳感器節點在網絡環境部署120-160 個傳感器的情況下皆少于GC 的數量。這是因為GC 每次都是行動策略都是貪婪的選擇即刻能獲得最大充電收益的傳感器位置，并同時對范圍內所有節點進行充電。這種算法僅考慮短期收益。而我們基于RL 的算法，由于RL 的特性，不僅會考慮當前充電步驟的充電收益，還會把對未來充電步驟的影響考慮在內。并且，我們將死亡節點的數量作為懲罰值加入到我們的獎勵函數中，如公式（2），導致RLC 的充電策略會傾向于選擇造成死亡節點更少的停靠點。此外，我們不僅僅能夠選在在傳感器坐標上停靠，而且能夠根據圓的幾何關系，將充電范圍形成的相交圓之間的交點作為備選停靠點之一。

圖4 表示了能量的利用效率情況。我們可以清楚的看到，RLC 的EUR 皆高于0.48，而GC 的EUR 卻都低于0.46。這是由于RLC 策略下的充電車有更多的充電停靠點可以選擇，使其有更多的機會選擇到路徑較少且充電覆蓋范圍內包含傳感器節點數量更多的停靠點。因此，綜上分析，我們的算法能夠擁有更好的網絡性能，帶來更少的死亡節點和更高的能量使用效率。

5 結語

本文區別于傳統的充電方法算法，采用基于RL 的充電策略為無線充電車構造充電路徑，實現為傳感器節點提供及時的充電服務。通過實驗對比，在死亡節點數量和能量利用效率兩個方面顯示了我們算法的優越性和有效性。