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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此在t時(shí)刻節(jié)點(diǎn)的剩余能量計(jì)算如下:

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

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

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

1.2 問(wèn)題定義

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

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

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

2 多MC按需充電策略

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

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

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

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

圖2 傳感器劃分-以一個(gè)MC為例

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

MCk在充電回路k中的總移動(dòng)距離為:

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

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

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

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

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

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

2.2 充電序列規(guī)劃

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

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

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

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

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

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

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

3.1 圖嵌入

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

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

3.2 注意力機(jī)制

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

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

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

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

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

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

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

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

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

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

算法1 節(jié)點(diǎn)分配

3.3 策略梯度

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

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

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

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

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

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

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

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

算法2 策略梯度

4 仿真與性能分析

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

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

對(duì)比算法設(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充電回路劃分過(guò)程。

NJNP:MC選擇空間上最近的傳感器節(jié)點(diǎn)作為下一個(gè)要充電的傳感器。

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

4.1 充電子回路長(zhǎng)度

評(píng)估各個(gè)MC充電負(fù)載是否均衡的一個(gè)指標(biāo)為最長(zhǎng)充電子回路的長(zhǎng)度。為了評(píng)估該指標(biāo)，我們?cè)诓煌膶W(xué)習(xí)率下對(duì)模型進(jìn)行27 000次迭代，進(jìn)而驗(yàn)證學(xué)習(xí)率對(duì)APCS算法的影響，實(shí)驗(yàn)結(jié)果如圖6所示。

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

圖6 最長(zhǎng)充電子回路

4.2 對(duì)比仿真

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

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

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

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

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

圖8 不同情況下的MC平均移動(dòng)距離

5 結(jié)論

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