基于注意力機(jī)制和策略梯度的多MC充電調(diào)度*

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

(昆明理工大學(xué)云南省計算機(jī)技術(shù)應(yīng)用重點實驗室，云南 昆明 650500)

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

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

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

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

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

對于以上種種限制，本文基于前人研究，融合周期性充電和按需充電模式的優(yōu)點，在多MC充電調(diào)度的基礎(chǔ)上聯(lián)合考慮均衡MCs充電負(fù)載以及最大化MCs充電效率的問題，并引入注意力機(jī)制和強(qiáng)化學(xué)習(xí)中的策略梯度對充電調(diào)度問題進(jìn)行求解。

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

1 網(wǎng)絡(luò)模型與問題定義

本節(jié)首先對WRSN網(wǎng)絡(luò)模型和充電模型展開介紹，然后提出MCs按需充電調(diào)度問題。

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

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

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

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

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

①基站設(shè)定:本文設(shè)定只有一個基站，可根據(jù)實際情況位于網(wǎng)絡(luò)中任意合適的位置，BS負(fù)責(zé)數(shù)據(jù)的收集存儲并持續(xù)為MCs補(bǔ)充能量。

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

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

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

si向其他節(jié)點發(fā)送數(shù)據(jù)的總功耗為:

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

并且傳感器節(jié)點的能量需求為:

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

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

1.2 問題定義

本文將WRSN運(yùn)行時間劃分為多個連續(xù)的工作周期，節(jié)點充滿電后的生命周期為幾周或幾個月，而網(wǎng)絡(luò)可以在幾天內(nèi)完成一輪電量補(bǔ)充。當(dāng)傳感器能量降至設(shè)定閾值以下時主動向基站發(fā)送充電請求消息，請求消息通過多跳方式傳送到基站，MCs接受BS調(diào)度為節(jié)點補(bǔ)充能量。

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

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

2 多MC按需充電策略

在本文設(shè)置的傳感器網(wǎng)絡(luò)中有m個MC共同協(xié)作完成充電任務(wù)，在初始階段MCs位于BS，當(dāng)服務(wù)池中存在待充電節(jié)點時MC將為其規(guī)劃充電路徑。每個MC采用點對點充電模式，即同時只能為一個傳感器節(jié)點充電且每個傳感器節(jié)點在一輪充電調(diào)度中僅被充電一次。本節(jié)對多MC按需充電調(diào)度策略進(jìn)行分步驟詳細(xì)介紹。

2.1 構(gòu)建充電回路

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

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

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

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

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

假設(shè)MCk到達(dá)充電回路中的傳感器節(jié)點ski后立即為其補(bǔ)充能量至Emax。則MCk為節(jié)點ski的充電時間為:

則MCk在充電回路中執(zhí)行一輪充電任務(wù)所花費(fèi)的時間為:

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

圖3 多MC充電調(diào)度

為了最大化MCs能量利用率的同時均衡MC之間的充電負(fù)載，構(gòu)建充電回路的優(yōu)化目標(biāo)為:

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

2.2 充電序列規(guī)劃

上一充電周期內(nèi)節(jié)點發(fā)送的充電請求Q存儲在充電服務(wù)池P中，在當(dāng)前周期開始前每個MC根據(jù)服務(wù)池中的請求信息為自身規(guī)劃充電序列，MC從BS出發(fā)按照充電回路中的節(jié)點順序依次訪問待充電節(jié)點。

定義1最優(yōu)充電序列為MC從BS出發(fā)遍歷所有待充電節(jié)點至少一次后并返回BS的最短路徑。

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

在一輪充電回合中以圖4為例，刪除不需要充電的節(jié)點重新構(gòu)造最優(yōu)充電序列。MC按順序為待充電節(jié)點{n1，n5，n6，n8}進(jìn)行能量補(bǔ)充。

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

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

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

3.1 圖嵌入

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

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

3.2 注意力機(jī)制

結(jié)合注意力機(jī)制[21]的分布式策略網(wǎng)絡(luò)能夠分析嵌入的圖，之后由策略梯度做出為MC分配不同傳感器節(jié)點的決策。策略網(wǎng)絡(luò)的設(shè)計分為兩個階段，第一個階段中每個MC使用全局信息和圖中節(jié)點嵌入構(gòu)造自身嵌入。第二個階段，采用注意力機(jī)制進(jìn)行MC嵌入和節(jié)點的分配，每個節(jié)點使用全局嵌入為自身分配一個MC，并使用策略梯度對分配模型進(jìn)行訓(xùn)練。

圖5 注意力機(jī)制模型

式中dk和dv為key和value的維度，然后計算MCa關(guān)聯(lián)的query與所有節(jié)點的匹配程度:

對于注意力權(quán)重wai∈[0，1]:

由權(quán)重wai構(gòu)造MC嵌入:

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

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

每個節(jié)點都必須分配到一個MC，其對該節(jié)點的相關(guān)度決定哪個MC訪問該節(jié)點，通過Softmax函數(shù)對相關(guān)度進(jìn)行歸一化，得到MC訪問某個節(jié)點的概率。

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

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

算法1 節(jié)點分配

3.3 策略梯度

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

分布式策略網(wǎng)絡(luò)將根據(jù)已分配路徑path做出決策，在分配過程中傳感器節(jié)點具有以下兩種狀態(tài):

狀態(tài)1:傳感器節(jié)點已被分配給MC。

狀態(tài)2:傳感器節(jié)點尚未被分配。

例如，當(dāng)前對應(yīng)于MCa的策略網(wǎng)絡(luò)，在一個節(jié)點被分配到MCa時，該節(jié)點輸入到策略網(wǎng)絡(luò)的特征為(1，0)；若當(dāng)前節(jié)點被分配給其他MC，則特征為(0，1)；節(jié)點未被分配時特征為(0，0)。

式中:θ*表示最優(yōu)策略，D是訓(xùn)練集；λ為分配給MCa的節(jié)點；Rλ是分配λ后獲得的獎勵；πθ是賦值在θ上的分布:

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

在完成節(jié)點到MC的分配后，每個MC負(fù)責(zé)相應(yīng)的傳感器節(jié)點，此時求解m條充電回路的問題被簡化為若干個與MC相關(guān)的TSP。本文采用Google的優(yōu)化工具OR-tools求解與每個MC相關(guān)的TSP。在完成m條充電回路的劃分后按照2.2節(jié)的充電序列規(guī)劃方法為節(jié)點進(jìn)行按需能量補(bǔ)充。

算法2 策略梯度

4 仿真與性能分析

仿真實驗使用Python語言搭配Pytorch框架模擬WRSN的能量補(bǔ)充過程，并與不同的充電方案進(jìn)行對比驗證APCS的性能。我們根據(jù)對實際應(yīng)用場景的考慮和大量現(xiàn)有文獻(xiàn)的參考，相關(guān)實驗?zāi)J(rèn)參數(shù)的設(shè)置如表2所示。在實際充電調(diào)度中，WRSN中需要MC的數(shù)量受多種因素影響，包括傳感器節(jié)點數(shù)量、傳感器節(jié)點能耗率、MC電池容量和MC充電效率等多種因素。我們在實驗中設(shè)定MC的數(shù)量m＝5，傳感器節(jié)點數(shù)量n＝50，75，100，125，150，175，200，來模擬小規(guī)模傳感器網(wǎng)絡(luò)和大規(guī)模傳感器網(wǎng)絡(luò)中的充電調(diào)度，并在(0，1)2的區(qū)域內(nèi)隨機(jī)生成n個傳感器節(jié)點的坐標(biāo)作為訓(xùn)練數(shù)據(jù)。以此來驗證所提方案的有效性。

表2 實驗?zāi)J(rèn)參數(shù)

對比算法設(shè)置為遺傳算法(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選擇空間上最近的傳感器節(jié)點作為下一個要充電的傳感器。

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

4.1 充電子回路長度

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

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

圖6 最長充電子回路

4.2 對比仿真

節(jié)點失效率定義為能量耗盡的失效節(jié)點數(shù)與所有請求充電的節(jié)點數(shù)之比，節(jié)點失效率是評價充電策略性能的重要指標(biāo)之一，失效節(jié)點比率越小，說明充電策略效率越高，對待充電節(jié)點的響應(yīng)越公平。

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

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

圖7 不同情況下的節(jié)點失效率

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

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

5 結(jié)論

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