基于注意力機制和策略梯度的多MC充電調度*

王藝均，馮 勇，李英娜，付曉東，錢 謙

(昆明理工大學云南省計算機技術應用重點實驗室，云南 昆明 650500)

無線傳感器網絡(WSN)被廣泛應用于物聯網的各個場景[1-2]，但由于傳感器節點采用電池供電，有限的電池容量使傳感器無法長時間有效工作，阻礙了WSN的大規模部署。無線能量傳輸[3]的迅速發展為解決WSN中節點的能量限制問題提供了新思路，使得無線可充電傳感器網絡(WRSN)[4]應運而生。其中配備有諧振線圈的可移動充電裝置(Mobile Charger，MC)用于將能量無線傳輸到傳感器節點，使WSN的生存時間不再受限于傳感器的電池容量。理想情況下，WRSN的工作時間可以達到無限長。而在WRSN中如何高效地調度MC為節點補充能量是當前的最大挑戰，受到了國內外學者的廣泛研究。

為保證傳感器節點長期有效地工作，要求充電方案盡可能地提高MC充電效率和降低節點失效率。在充電過程中MC的能量消耗包括三個部分:①有效能量，即為傳感器節點補充的能量；②機械能，即MC移動過程的能量損耗；以及③無線傳輸過程的能量損耗[5]。充電效率定義為有效能量與總能量之比。其中如何減少MC移動過程的能量損耗是提高整體充電效率的關鍵。當傳感器節點未及時得到能量補充時會因缺電而饑餓失效，從而可能造成傳感器網絡數據鏈路斷開等嚴重后果。因此，為了提高充電效率和降低節點失效率，需要合理調度MC為整個傳感器網絡補充能量。對于大規模無線傳感器網絡，單個MC顯然不能有效應對大量的充電需求，而多個MC的調度問題進一步涉及MCs之間的協調[6]。

目前的WRSN充電調度方案可以分為周期性充電策略和按需充電策略。周期性充電策略需要求出一條覆蓋所有傳感器節點的充電回路，MCs沿著預定軌跡周期性完成充電任務。文獻[7]通過求解基于節點能耗的旅行商問題(Traveling Salesman Problems，TSP)來實現MC充電效率最大化。文獻[8]在考慮MC能量有限的情況下建立以最小化MCs能耗率為優化目標的優化模型，采用混沌粒子群算法獲得MCs的充電路徑和充電策略。文獻[9]聯合考慮了充電軌跡和基站定位問題，解決了MCs充電周期與節點生存壽命不匹配的難題。但周期性充電策略無法應對節點能耗波動較大的場景，仍然存在一定局限性。

按需充電策略中傳感器節點根據自身剩余能量發送充電請求，MC根據節點的實時需求執行充電任務。文獻[10]考慮充電請求的影響設計了雙重警告閾值來確定充電請求的調度優先級，并設計了雙重搶占機制處理網絡的動態特性。文獻[11]綜合考慮節點充電過程中的時間和空間因素，使用改進的引力搜索算法按需規劃節點被服務的順序。文獻[12]提出一種基于非均勻分簇的實時充電算法，通過研究簇內節點的能量狀態和充電截止時間來決定簇頭的選舉和輪換。文獻[13]將多MCs的協調問題表述為整數線性規劃，并設計了一種分解方法來求解，以最小化計算時間。為了最小化MC數量，文獻[14]提出了叫做shuttling的新概念，在理論上實現了MC個數最小化。文獻[15]根據節點剩余生存時間將其分組，保證每次調度只對剩余能量較低的節點進行充電。按需充電模式能更好地適應節點能耗動態變化的環境，文獻[16]考慮每個MC同時向多個節點傳輸能量以減少充電延遲。然而現有按需充電模式下多MC的充電調度工作并沒有從整體上考慮充電路徑的優化，這可能帶來MCs不必要移動，從而增加充電成本。

通過對現有工作的分析，可知周期性充電模式不能很好地適應節點能耗的動態特性，按需模式沒有充分考慮充電路徑的優化和充電策略的公平性。現有多MC充電規劃研究大多僅考慮單一性能指標，并未考慮到MCs承擔充電任務的均衡性，使MCs的充電任務均衡一方面可以提高MCs整體充電效率，減少MC數量；另一方面可以避免單個MC負載較重而造成節點饑餓失效的問題，提升整個網絡的生存時間。并且WRSN中的充電調度被證明是NP-hard問題，對于NP-hard問題沒有可用于監督學習的最優標簽。目前已有的研究工作大多基于傳統的優化方法，如枚舉策略、近似算法和啟發式算法等。傳統方法對于NP-hard問題一般不容易得到滿足實際需求的最優方案，很難適應復雜多變的環境，甚至把問題過于簡單化。因此充電調度工作仍需進一步優化。

對于以上種種限制，本文基于前人研究，融合周期性充電和按需充電模式的優點，在多MC充電調度的基礎上聯合考慮均衡MCs充電負載以及最大化MCs充電效率的問題，并引入注意力機制和強化學習中的策略梯度對充電調度問題進行求解。

本文的主要貢獻如下:(1)聯合考慮WRSN充電規劃中MCs充電負載均衡化和MCs充電效率最大化，提出一種新的充電調度方法APCS。(2)引入注意力機制和策略梯度對充電調度問題進行求解，通過獎勵反饋來評估一組充電序列的質量，為動態WRSN提供即時的全局充電方案。(3)建立仿真環境并與現有充電方案進行對比，證明了本文方案的有效性。

1 網絡模型與問題定義

本節首先對WRSN網絡模型和充電模型展開介紹，然后提出MCs按需充電調度問題。

1.1 網絡模型

給定一個WRSN模型如圖1所示，整個移動能量補給系統部署在二維平面區域內，不考慮障礙物的影響，由三類成員組成:一個基站(BS)、n個傳感器節點和m個移動充電設備(MC)。其中傳感器節點和基站固定不動且位置已知，基站作為最終的數據采集器不受能量限制，MCs和傳感器節點電池容量有限，MC是一種具有自主移動、計算和通信能力的設備，例如智能小車或移動機器人，并帶有無線能量傳輸裝置為傳感器節點補充能量，其自身可通過BS快速更換電池[17]。

圖1 WRSN網絡模型

以下根據三類成員描述模型假設和相關定義，表1中列出了其余部分使用的主要符號。

表1 主要參數符號

①基站設定:本文設定只有一個基站，可根據實際情況位于網絡中任意合適的位置，BS負責數據的收集存儲并持續為MCs補充能量。

②傳感器節點設定:n個傳感器節點表示為集合N＝{s1，s2，…，sn}，其根據數據采集頻率和數據傳輸速率預測其自身剩余能量，對于每個節點si(1≤i≤n)，其能量主要用于數據的發送和接收，根據文獻[18]我們采用如下能耗模型:

式中:fi，j(1≤j≤n+1)是節點si到sj的數據流，當j＝n+1時表示si到BS的數據流，ci，j表示傳輸數據時的功耗。

式中:di，j為節點si到sj的距離，β1表示無距離能耗系數，γ為信號衰減系數，ρ是節點接收1 kbyte/s數據的能耗，因此節點si接收數據的總功耗為:

si向其他節點發送數據的總功耗為:

因此在t時刻節點的剩余能量計算如下:

并且傳感器節點的能量需求為:

③MCs設定:在WRSN區域中MCs的規格相同，并以Vm的速度移動，能耗為Em，通過遠距離通信(如4G/5G通信技術)直接受基站BS調度。并可通過GPS等定位技術實時獲取自身位置，MC只有在到達某個節點位置時為其單獨補充能量，充電功率為qc，MC攜帶電池的最大容量為Em，在t時刻MCs剩余能量的計算公式為:

式中:Li，i+1為MC從當前節點移動到下一節點的距離，當MC剩余能量小于下一待充電節點能量需求與自身行駛消耗能量之和時停止為節點補充能量，從當前位置返回基站充電，與節點充電過程相比MC自身補充能量時間忽略不計。

1.2 問題定義

本文將WRSN運行時間劃分為多個連續的工作周期，節點充滿電后的生命周期為幾周或幾個月，而網絡可以在幾天內完成一輪電量補充。當傳感器能量降至設定閾值以下時主動向基站發送充電請求消息，請求消息通過多跳方式傳送到基站，MCs接受BS調度為節點補充能量。

由于各個傳感器節點能耗率不同，要使MCs總移動距離最短、充電效率最高，MCs需要協作完成充電任務。首先對WRSN中的傳感器節點進行合理劃分，每個MC負責不同的節點。本文將充電任務的分配過程抽象為多旅行商問題(MTSP)，MCs和傳感器節點分別對應于旅行商和城市。我們提出一種融合注意力機制和策略梯度的充電調度算法。旨在WRSN中傳感器節點滿足位置和充電器能量約束的基礎上，求解最大化充電效率問題。

如前所述，整個充電調度的目標是最大化充電效率和最小化節點失效率。本文需要解決的問題如下:①為MCs劃分合理的充電路徑，盡可能使充電效率最高。②均衡每個MC的充電負載，最小化MTSP中的最長子路徑，高效調度MC，減少節點失效率。

2 多MC按需充電策略

在本文設置的傳感器網絡中有m個MC共同協作完成充電任務，在初始階段MCs位于BS，當服務池中存在待充電節點時MC將為其規劃充電路徑。每個MC采用點對點充電模式，即同時只能為一個傳感器節點充電且每個傳感器節點在一輪充電調度中僅被充電一次。本節對多MC按需充電調度策略進行分步驟詳細介紹。

2.1 構建充電回路

對于整個WRSN的充電調度，首先構建充電回路為MCs劃分充電任務，使得MCs能夠覆蓋所有傳感器。以BS為起點為傳感器節點集合N＝{s1，s2，…sn}劃分m個最短哈密頓回路，每個MC負責一條回路中的傳感器節點，在每條充電回路中按順序為節點重新編號。

圖2顯示了WRSN其中一條充電回路，其可以表示為Charging Circuit1＝BS，n1，n2，…，n8每個MC負責一條充電回路。構建這樣m條充電回路的問題為多旅行商問題(MTSP)。

圖2 傳感器劃分-以一個MC為例

對于編號為k的MC對應的充電規劃來說，在t＝0時刻MCk從BS出發，遍歷一系列傳感器節點，形成集合，其中，nk為MCk一輪充電的傳感器個數。在充電完成后MC沿充電路徑回到BS為自身補充能量.設Rk為MCk對應的一次充電回路，ski為該充電回路中的傳感器節點，均表示為基站BS。

MCk在充電回路k中的總移動距離為:

假設MCk到達充電回路中的傳感器節點ski后立即為其補充能量至Emax。則MCk為節點ski的充電時間為:

則MCk在充電回路中執行一輪充電任務所花費的時間為:

如圖3所示，在每個充電周期中各個MC服務的充電回路不同，完成一輪充電任務的時間也不同。最先完成充電任務的MC與最后完成的時間差為:

圖3 多MC充電調度

為了最大化MCs能量利用率的同時均衡MC之間的充電負載，構建充電回路的優化目標為:

式中:目標值f1表示MCk在一次充電回合中移動能量損耗與總能量消耗之比，即充電效率。f2表示MCs執行充電任務花費的時間的方差，用來衡量MC之間充電負載的均衡性。

2.2 充電序列規劃

上一充電周期內節點發送的充電請求Q存儲在充電服務池P中，在當前周期開始前每個MC根據服務池中的請求信息為自身規劃充電序列，MC從BS出發按照充電回路中的節點順序依次訪問待充電節點。

定義1最優充電序列為MC從BS出發遍歷所有待充電節點至少一次后并返回BS的最短路徑。

引理1根據文獻[19]的證明，從最短充電回路中刪除任意n(0≤n＜N)個節點得到具有N-n個節點組成的最短充電路徑，即最短充電回路的子路徑也是最短充電回路。

在一輪充電回合中以圖4為例，刪除不需要充電的節點重新構造最優充電序列。MC按順序為待充電節點{n1，n5，n6，n8}進行能量補充。

圖4 充電序列重新規劃-以一個MC為例

3 基于注意力機制和策略梯度的求解框架

本文在研究WRSN中多MC協同充電調度的問題中，構建一種基于注意力機制與分布式策略網絡組成的體系結構，從而為MCs的充電調度生成近似最優的解決方案，并引入策略梯度訓練模型。首先將為MCs分配傳感器節點的過程定義在圖G中，策略首先總結圖G的狀態，然后將每個傳感器節點分配到指定的MC，通過這種方式將多MC充電調度問題轉化為m個單MC調度問題，為每個MC構建充電回路。首先利用圖神經網絡嵌入圖G，然后設計一組分布式策略網絡進行傳感器節點到MC的分配。本節對求解框架展開詳細介紹。

3.1 圖嵌入

首先將圖定義為節點和邊的集合，為了解決圖數據難以高效輸入機器學習算法的問題，通過圖嵌入將圖中高維稠密矩陣映射為低維稠密向量。根據文獻[20]我們采用組合消息傳遞神經網絡(Combined Message Passing Neural Network，CMPNN)框架，通過相鄰連接節點的消息傳遞為每個傳感器節點u計算p維特征嵌入fu。在基于CMPNN框架的圖神經網絡中，節點嵌入的更新過程如下:

式中:relu(z)＝max{0，z}應用于其輸入元素，N(u)表示節點u所有的相鄰節點，θe為所有邊的共享參數，θ1，θ2為所有節點的共享參數。

3.2 注意力機制

結合注意力機制[21]的分布式策略網絡能夠分析嵌入的圖，之后由策略梯度做出為MC分配不同傳感器節點的決策。策略網絡的設計分為兩個階段，第一個階段中每個MC使用全局信息和圖中節點嵌入構造自身嵌入。第二個階段，采用注意力機制進行MC嵌入和節點的分配，每個節點使用全局嵌入為自身分配一個MC，并使用策略梯度對分配模型進行訓練。

圖5 注意力機制模型

式中dk和dv為key和value的維度，然后計算MCa關聯的query與所有節點的匹配程度:

對于注意力權重wai∈[0，1]:

由權重wai構造MC嵌入:

對于將MC分配給節點i的策略過程，我們首先計算每個MC對于節點i的相關度。對于MCa:

式中:d′k是新keys的維度；θak′和θaq′為神經網絡參數，用于將嵌入映射到d′k維。在求出u′ai后，使用tanh將結果限制在[-C，C](C＝10)，從而求出impai。

每個節點都必須分配到一個MC，其對該節點的相關度決定哪個MC訪問該節點，通過Softmax函數對相關度進行歸一化，得到MC訪問某個節點的概率。

據統計，核電站人因失誤類型可分為5類[13]：1) 未發現報警或征兆；2) 對事故征兆或時間判斷失誤；3) 操作失誤；4) 工作人員交流差錯；5) 組織管理不當。其中第1類失誤與操作界面設計的優劣有著直接的關系，故本文從第1類失誤類型出發,將其作為出錯因子，建立基于報警發現的評價體系。

算法1為傳感器節點到MC的分配過程，其中path是為MC分配的充電回路，f是節點特征，m和n分別為傳感器節點和MC數量。在開始時保存節點分配的集合D為空，即未給任何節點分配MC，執行算法1將為D賦值，通過OR-tools計算最長子路徑的長度作為獎勵值。

算法1 節點分配

3.3 策略梯度

本文將為MCs分配傳感器節點的過程抽象為Markov過程，具體而言，在求解時通過參數為θ的網絡模型選擇下一個加入充電回路的傳感器節點，最終生成充電回路path。為了評估模型中的參數θ，采用策略梯度進行訓練使得預期獎勵最大化。

分布式策略網絡將根據已分配路徑path做出決策，在分配過程中傳感器節點具有以下兩種狀態:

狀態1:傳感器節點已被分配給MC。

狀態2:傳感器節點尚未被分配。

例如，當前對應于MCa的策略網絡，在一個節點被分配到MCa時，該節點輸入到策略網絡的特征為(1，0)；若當前節點被分配給其他MC，則特征為(0，1)；節點未被分配時特征為(0，0)。

式中:θ*表示最優策略，D是訓練集；λ為分配給MCa的節點；Rλ是分配λ后獲得的獎勵；πθ是賦值在θ上的分布:

為了達成該訓練目標，本文采用策略梯度算法對參數θ進行訓練，求得最優策略θ*，即在完成節點到MC分配的同時，最小化MC的最長充電子回路，在完成傳感器節點到MC分配過程的同時，使得每個MC的充電負載盡可能達到均衡。訓練過程中使用OR-tools快速計算一組較小規模的TSP，并返回所有MC的最大行程長度的負數作為任務的獎勵。

在完成節點到MC的分配后，每個MC負責相應的傳感器節點，此時求解m條充電回路的問題被簡化為若干個與MC相關的TSP。本文采用Google的優化工具OR-tools求解與每個MC相關的TSP。在完成m條充電回路的劃分后按照2.2節的充電序列規劃方法為節點進行按需能量補充。

算法2 策略梯度

4 仿真與性能分析

仿真實驗使用Python語言搭配Pytorch框架模擬WRSN的能量補充過程，并與不同的充電方案進行對比驗證APCS的性能。我們根據對實際應用場景的考慮和大量現有文獻的參考，相關實驗默認參數的設置如表2所示。在實際充電調度中，WRSN中需要MC的數量受多種因素影響，包括傳感器節點數量、傳感器節點能耗率、MC電池容量和MC充電效率等多種因素。我們在實驗中設定MC的數量m＝5，傳感器節點數量n＝50，75，100，125，150，175，200，來模擬小規模傳感器網絡和大規模傳感器網絡中的充電調度，并在(0，1)2的區域內隨機生成n個傳感器節點的坐標作為訓練數據。以此來驗證所提方案的有效性。

表2 實驗默認參數

對比算法設置為遺傳算法(Genetic Algorithm，GA)、貪婪算法(Greedy Algorithm，GA)、典型的單MC按需充電方案Nearest-Job-Next with Preemption(NJNP)[22]和多MC方案Distance and Energy-Oriented Charging Scheduling(DECS)[23]。

遺傳算法:采用遺傳算法求解多MC充電回路劃分過程。

NJNP:MC選擇空間上最近的傳感器節點作為下一個要充電的傳感器。

DECS:綜合考慮節點剩余能量和節點與MC之間距離，在協作模式下為MCs規劃最短充電路徑。

4.1 充電子回路長度

評估各個MC充電負載是否均衡的一個指標為最長充電子回路的長度。為了評估該指標，我們在不同的學習率下對模型進行27 000次迭代，進而驗證學習率對APCS算法的影響，實驗結果如圖6所示。

從圖6可以看出，學習率為5e-5時取得了較快的收斂速度，但結果并未達到最佳。學習率為1e-5時APCS在10 000次迭代后開始收斂，取得了更好的效果。最長充電子回路越短，說明WRSN中各個充電子回路長度越均衡，每個充電周期內ΔTk越小，即各個MC之間充電負載越均衡。

圖6 最長充電子回路

4.2 對比仿真

節點失效率定義為能量耗盡的失效節點數與所有請求充電的節點數之比，節點失效率是評價充電策略性能的重要指標之一，失效節點比率越小，說明充電策略效率越高，對待充電節點的響應越公平。

分析圖7(a)可得，隨著網絡規模的增加，五種充電策略的節點失效率都呈現增大趨勢。這是由于請求節點數量的增加，MC對待充電節點的響應變慢從而導致來不及得到能量補充的節點饑餓失效。但本文提出的充電方案APCS中的節點失效率始終低于其他四種方案，在節點數量為200時，APCS的結果比GA、Greedy、NJNP和DECS充電方案分別降低了33.3%、70%、61.5%、39.3%。

如圖7(b)所示，實驗表明在Eth為0.6-0.7Es時節點失效率最低，在超過0.7Es時失效率上升，這是由于Eth過高導致請求充電的節點數量大大增加，MC無法及時響應所有待充電節點。在Eth為0.3-0.8Es之間的APCS都取得了比其他方法更好的效果。

圖7 不同情況下的節點失效率

每個MC的充電效率定義為傳感器節點獲得的能量與總能量之比。提高充電效率的一種有效途徑是減少能量補充過程中消耗的機械能，即MC移動能耗。如圖8(a)所示，隨著節點數量的增加，五種充電方法的MC平均移動距離都呈現增大趨勢，但APCS始終優于其余方法。從圖8(b)可以看出，在閾值Eth的變化下APCS同樣取得了比其余方法更好的結果。在Eth大于0.7Es時MC移動距離增加是由于閾值過大請求充電節點數量太多導致MC更頻繁的移動。

圖8 不同情況下的MC平均移動距離

5 結論

本文針對大規模WRSN中單個MC服務能力不足和多MC調度中充電負載不均衡的問題，研究了多MC充電調度優化問題。提出了融合注意力機制和強化學習中策略梯度的充電調度方案APCS。首先APCS以提高充電效率、減少節點失效率為目標，采用注意力機制和策略梯度完成傳感器節點到MC的分配，每個MC負責相應的傳感器節點，再通過OR-tools求解與每個MC相關的TSP，為其規劃充電路徑。在仿真實驗中，我們通過分析最長充電子回路的長度、節點失效率和MC平均移動距離來評估所提方法的性能。大量仿真結果表明，APCS能夠顯著降低節點失效比率并提高充電效率。