張世豪

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

隨著現(xiàn)代微電子技術(shù)與自組織網(wǎng)絡(luò)的發(fā)展，無線傳感器網(wǎng)絡(luò)受到了廣泛的關(guān)注。傳感器網(wǎng)絡(luò)已成為收集數(shù)據(jù)與信息的主要手段之一?，F(xiàn)如今，無線傳感器網(wǎng)絡(luò)的應(yīng)用已隨處可見，例如城市設(shè)施監(jiān)測(cè)、海洋水質(zhì)監(jiān)測(cè)、軍事監(jiān)控、橋梁檢測(cè)和消防監(jiān)測(cè)，等等。而監(jiān)測(cè)數(shù)據(jù)的獲取是依靠環(huán)境中部署的大量無線傳感器節(jié)點(diǎn)來實(shí)現(xiàn)的。為了保證傳感器網(wǎng)絡(luò)的檢測(cè)質(zhì)量，需要節(jié)點(diǎn)之間保持連通性和覆蓋性，者對(duì)無線傳感器節(jié)點(diǎn)的電池提出了較高要求。

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

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

在一個(gè)無線傳感器網(wǎng)絡(luò)中，包含一座基站（BS）和N 個(gè)傳感器節(jié)點(diǎn)。我們派遣一輛無線充電車從BS 出發(fā)為傳感器節(jié)點(diǎn)進(jìn)行充電。我們定義當(dāng)傳感器的剩余能量re小于閾值時(shí)，傳感器節(jié)點(diǎn)生成充電請(qǐng)求，以此來引導(dǎo)充電車選擇?？课恢貌?gòu)造路徑。假定傳感器節(jié)點(diǎn)和充電車的總電池容量分別被定義為bsensor和Bcar。此外，我們定義無線充電車的充電半徑為r，當(dāng)充電車與傳感器節(jié)點(diǎn)之間的距離d小于半徑r時(shí)，便能對(duì)其進(jìn)行充電。傳感器節(jié)點(diǎn)與無線充電車當(dāng)前坐標(biāo)之間的距離計(jì)算采用歐幾里得公式，如公式（1）：

其中xsensor和ysensor代表節(jié)點(diǎn)的坐標(biāo)信息，xcar和ycar代表當(dāng)前充電車的坐標(biāo)位置。

與其他一些研究策略[5]不同。我們不僅將無線充電車調(diào)度到傳感器上停止，還可以根據(jù)充電半徑的形成一些相交點(diǎn)上?？?，使得有更多備選的?？课恢每晒┻x擇。同時(shí)，由于在無線能量的傳輸過程中存在能量損耗，所以我們引入了一個(gè)恒定的衰減率λ，傳感器實(shí)際獲取的能量為無線充電車原始發(fā)射能量的λ倍。具體的充電模型如圖1 所示。

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

2 問題描述

本文在一個(gè)無線傳感器網(wǎng)絡(luò)中研究了調(diào)度一輛無線充電車為N 個(gè)傳感器節(jié)點(diǎn)補(bǔ)充能量并規(guī)劃和構(gòu)成充電路徑的問題，使得無線充電車在完成一個(gè)充電周期后，形成一條完整充電回路。同時(shí)，無線充電車不僅限于被?？坑趥鞲衅魃?，且能?？吭诔潆姲霃较嘟粓A的交點(diǎn)之上。由于備選?？奎c(diǎn)數(shù)量的增加導(dǎo)致加大了計(jì)算復(fù)雜度，因此為了提高網(wǎng)絡(luò)性能、降低計(jì)算難度，我們提出一種基于強(qiáng)化學(xué)習(xí)的學(xué)習(xí)算法來解決該問題。

3 強(qiáng)化學(xué)習(xí)算法

本節(jié)首先介紹一些必要的強(qiáng)化學(xué)習(xí)（RL）背景。其次，引出在本文無線傳感器網(wǎng)絡(luò)場(chǎng)景下的RL 模型。隨后再提出我們基于RL 的充電調(diào)度算法。

3.1 RL背景

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

3.2 RL模型

RL 模型最關(guān)鍵的三部分分別為動(dòng)作、狀態(tài)和獎(jiǎng)勵(lì)。在我們的網(wǎng)絡(luò)模型中，我們定義首先定義動(dòng)作為所有備選的?？奎c(diǎn)，即不僅包含了所有傳感器的坐標(biāo)，還囊括了所有傳感器的在充電半徑下的相交圓的交點(diǎn)坐標(biāo)。其次，定義狀態(tài)定義為所有傳感器的剩余能量，這樣定義是因?yàn)榭梢杂兄跓o線充電車根據(jù)所有傳感器節(jié)點(diǎn)的剩余能量判斷應(yīng)為哪些傳感器進(jìn)行充電。最后，我們定義了一個(gè)獎(jiǎng)勵(lì)函數(shù)來代表每次執(zhí)行動(dòng)作后，環(huán)境反饋給智能體的一個(gè)信號(hào)量，獎(jiǎng)勵(lì)函數(shù)被形式化表示為如下：

其中K表示充電車?？课恢锰幊潆姺秶鷥?nèi)所包含的所有傳感器節(jié)點(diǎn)的集合，而k表示集合中所屬的第k個(gè)傳感器節(jié)點(diǎn)。rek表示第k 個(gè)傳感器節(jié)點(diǎn)的剩余壽命。而DN表示網(wǎng)絡(luò)環(huán)境中死亡節(jié)點(diǎn)的數(shù)量。此外，α為一個(gè)參數(shù)因子，在實(shí)驗(yàn)中我們?cè)O(shè)置α為100。我們將死亡節(jié)點(diǎn)的數(shù)量作為懲罰值使得智能體會(huì)盡可能選擇避免節(jié)點(diǎn)死亡的情況的行動(dòng)策略。

3.3 基于RL的充電調(diào)度算法描述

我們基于RL 的Deep Q Network[6]來實(shí)現(xiàn)充電調(diào)度算法。學(xué)習(xí)算法采用雙重網(wǎng)絡(luò)結(jié)構(gòu)來進(jìn)行訓(xùn)練，即包含評(píng)估網(wǎng)絡(luò)和現(xiàn)實(shí)網(wǎng)絡(luò)兩個(gè)網(wǎng)絡(luò)。我們將智能體的狀態(tài)信息作為評(píng)估網(wǎng)絡(luò)的輸入，網(wǎng)絡(luò)的輸出為傳感器網(wǎng)絡(luò)中所有的備選?？奎c(diǎn)。網(wǎng)絡(luò)輸出值的大小衡量了選擇該停靠點(diǎn)帶來的收益，也即獎(jiǎng)勵(lì)值。現(xiàn)實(shí)網(wǎng)絡(luò)具有與評(píng)估網(wǎng)絡(luò)相同的網(wǎng)絡(luò)結(jié)構(gòu)，用于計(jì)算損失函數(shù)和神經(jīng)網(wǎng)絡(luò)權(quán)重的更新。采用雙網(wǎng)絡(luò)結(jié)構(gòu)能夠增加強(qiáng)化學(xué)習(xí)算法的穩(wěn)定性。此外，我們定義損失函數(shù)為現(xiàn)實(shí)網(wǎng)絡(luò)與評(píng)估網(wǎng)絡(luò)輸出值的均方差。通過不斷地循環(huán)學(xué)習(xí)，最終達(dá)成無線充電車一輪的充電任務(wù)。具體算法過程如圖2 所示。

圖2 學(xué)習(xí)算法過程圖

4 實(shí)驗(yàn)?zāi)M

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

在本節(jié)中，我們對(duì)所提出的算法進(jìn)行仿真實(shí)驗(yàn)并對(duì)模擬結(jié)果進(jìn)行對(duì)比。我們?cè)O(shè)置無線傳感器網(wǎng)絡(luò)的大小為100m×100m。在仿真模擬的網(wǎng)絡(luò)環(huán)境中隨機(jī)部署120-160 個(gè)傳感器節(jié)點(diǎn)，并將基站（BS）設(shè)置在網(wǎng)絡(luò)環(huán)境的中心，即無線充電車從網(wǎng)絡(luò)中心出發(fā)為傳感器節(jié)點(diǎn)提供能量補(bǔ)充服務(wù)。每一個(gè)傳感器節(jié)點(diǎn)與充電車的最大電池容量bsensor和Bcar分別為6KJ 和10KJ。因傳感器節(jié)點(diǎn)隨機(jī)初始化，所以節(jié)點(diǎn)初始電量的范圍是最大容量的0.2-0.9 倍之間，而傳感器的能量消耗速率隨機(jī)初始化為0.1J/s-0.2J/s。同時(shí)，無線充電車的充電半徑被設(shè)置為10m，充電能量消耗和移動(dòng)能量 消耗分別為15W 和50J/m。

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

其中g(shù)i是在第i 個(gè)節(jié)點(diǎn)計(jì)算獲得的收益，Gainj是在第j 個(gè)節(jié)點(diǎn)處獲得的總收益，即鄰居節(jié)點(diǎn)集合內(nèi)所有節(jié)點(diǎn)收益的總和。rei是第i 個(gè)傳感器節(jié)點(diǎn)的剩余電池電量。m表示在第j 節(jié)點(diǎn)處共有m 個(gè)數(shù)量的鄰居節(jié)點(diǎn)。

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

4.2 結(jié)果與分析

我們從兩個(gè)方面來衡量?jī)蓚€(gè)算法的性能，即死亡節(jié)點(diǎn)的數(shù)量（DN）和能量使用效率（EUR）。DN 表示當(dāng)無線充電車完成運(yùn)行一個(gè)充電周期后，所有電池耗盡的傳感器節(jié)點(diǎn)的數(shù)量，即我們稱為死亡節(jié)點(diǎn)數(shù)量。EUR 表示充電車真正用于為傳感器傳輸?shù)哪芰空伎偰芰肯牡谋壤Ｄ芰勘壤挠?jì)算公式表示為：

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

圖3 死亡節(jié)點(diǎn)數(shù)量變化情況

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

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

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

5 結(jié)語

本文區(qū)別于傳統(tǒng)的充電方法算法，采用基于RL 的充電策略為無線充電車構(gòu)造充電路徑，實(shí)現(xiàn)為傳感器節(jié)點(diǎn)提供及時(shí)的充電服務(wù)。通過實(shí)驗(yàn)對(duì)比，在死亡節(jié)點(diǎn)數(shù)量和能量利用效率兩個(gè)方面顯示了我們算法的優(yōu)越性和有效性。