高思華,顧 晗,賀懷清,周 鋼

(1.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300300;2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130012;3.中國(guó)民航信息網(wǎng)絡(luò)股份有限公司 科技管理部,北京 101300)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)[1]因具有部署速度快、網(wǎng)絡(luò)規(guī)模大、自組織性強(qiáng)、網(wǎng)絡(luò)健壯性好等特點(diǎn),已廣泛應(yīng)用于醫(yī)療衛(wèi)生、環(huán)境保護(hù)、軍事偵查等領(lǐng)域.覆蓋質(zhì)量和網(wǎng)絡(luò)生命周期是無線傳感器網(wǎng)絡(luò)最基本、最重要的問題.如何在滿足覆蓋要求下延長(zhǎng)網(wǎng)絡(luò)生命周期被定義為無線傳感器網(wǎng)絡(luò)的覆蓋問題[2].按感知目標(biāo)屬性不同,覆蓋問題可分為目標(biāo)覆蓋、區(qū)域覆蓋和柵欄覆蓋.其中,目標(biāo)覆蓋問題應(yīng)用場(chǎng)景豐富,其求解方法主要分為整數(shù)規(guī)劃方法、基于博弈理論的方法和智能算法.文獻(xiàn)[3]對(duì)多感應(yīng)半徑下無線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問題進(jìn)行研究,通過列生成方法建模求解;文獻(xiàn)[4]通過列生成方法對(duì)無線傳感器網(wǎng)絡(luò)的覆蓋連通問題建模,針對(duì)列生成方法輔助問題求解速度慢的問題,設(shè)計(jì)遺傳算法進(jìn)行替換,有效加快了求解速度;文獻(xiàn)[5]提出了關(guān)鍵目標(biāo)的概念,制定優(yōu)先覆蓋網(wǎng)絡(luò)中被較少傳感器覆蓋目標(biāo)節(jié)點(diǎn)的策略,設(shè)計(jì)混合列生成方法進(jìn)行求解,延長(zhǎng)了網(wǎng)絡(luò)生命周期;文獻(xiàn)[6]針對(duì)視頻傳感器感知范圍受限的特征,提出了一種基于列生成方法的有向傳感器網(wǎng)絡(luò)目標(biāo)覆蓋問題的求解方法;Shahrokhzadeh等[7]將傳感器節(jié)點(diǎn)視為參加博弈的節(jié)點(diǎn),使用非合作博弈模型對(duì)目標(biāo)覆蓋問題建模,證明博弈必然存在Nash均衡;文獻(xiàn)[8]通過博弈模型對(duì)有向傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問題建模,提出節(jié)點(diǎn)感知方向改變策略,設(shè)計(jì)了一種減少覆蓋漏洞的分布式算法進(jìn)行求解.Cardei等[9]最先利用啟發(fā)式算法對(duì)目標(biāo)覆蓋問題進(jìn)行研究,提出休眠調(diào)度策略,僅激活部分傳感器節(jié)點(diǎn)保障目標(biāo)覆蓋質(zhì)量,其他傳感器節(jié)點(diǎn)通過休眠節(jié)約能量,考慮覆蓋目標(biāo)數(shù)量和傳感器節(jié)點(diǎn)剩余能量,通過貪心策略選擇被激活的傳感器;文獻(xiàn)[10]針對(duì)有向傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問題提出主動(dòng)冗余策略,要求每個(gè)目標(biāo)需要被多個(gè)傳感器節(jié)點(diǎn)覆蓋,確保信息不會(huì)丟失,分別利用先驗(yàn)進(jìn)化算法和后驗(yàn)進(jìn)化算法調(diào)整有向傳感器節(jié)點(diǎn)的感應(yīng)角度,在保證所有目標(biāo)均被覆蓋的前提下,盡可能提高冗余覆蓋的目標(biāo)數(shù)量;文獻(xiàn)[11]提出了一種基于分布式算法求解目標(biāo)覆蓋問題的方法,假設(shè)每個(gè)傳感器節(jié)點(diǎn)可以獲取鄰居節(jié)點(diǎn)的工作狀態(tài),幫助改變傳感器節(jié)點(diǎn)被選擇的概率,減少冗余現(xiàn)象發(fā)生,延長(zhǎng)網(wǎng)絡(luò)生命周期;文獻(xiàn)[12]提出了興趣區(qū)(ROI)概念,將目標(biāo)覆蓋問題通過二部圖轉(zhuǎn)化為匹配問題,提出了一種啟發(fā)算法和3種不同的近似優(yōu)化算法,通過選擇興趣值最大的傳感器節(jié)點(diǎn)完成目標(biāo)覆蓋任務(wù).文獻(xiàn)[13]提出了一種改進(jìn)的麻雀搜索算法優(yōu)化無線傳感器網(wǎng)絡(luò)的覆蓋,通過引入佳點(diǎn)集改善初始化策略,避免算法的早熟現(xiàn)象,在麻雀搜索過程加入動(dòng)態(tài)學(xué)習(xí)策略,優(yōu)化算法的尋優(yōu)模式;文獻(xiàn)[14]提出了一種基于學(xué)習(xí)自動(dòng)機(jī)的節(jié)點(diǎn)選擇方法,該方法增加滿足能量限制條件傳感器的激活概率,降低冗余傳感器的選擇概率,通過構(gòu)建更多可行解集延長(zhǎng)網(wǎng)絡(luò)生命周期;文獻(xiàn)[15]提出了一種用遺傳算法求解有向傳感器的K-目標(biāo)覆蓋問題,用每個(gè)染色體表示網(wǎng)絡(luò)中能構(gòu)建的所有解集合,通過交叉、變異等操作逐漸優(yōu)化種群,構(gòu)建更多的可行解集.

整數(shù)規(guī)劃方法和基于博弈理論的方法在求解過程中忽略目標(biāo)覆蓋問題的內(nèi)在特征,通過設(shè)計(jì)大量限制條件尋找最優(yōu)解,易出現(xiàn)收斂速度慢的問題.啟發(fā)式算法與目標(biāo)覆蓋問題的特征緊密聯(lián)系,算法根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)激活最合適的傳感器以覆蓋目標(biāo).該類算法求解速度快,但對(duì)影響無線傳感器網(wǎng)絡(luò)生命周期的原因分析較片面,自我學(xué)習(xí)能力不足,解的質(zhì)量有待提高.進(jìn)化算法解的構(gòu)建較容易,進(jìn)化過程可隱性揭示覆蓋問題的內(nèi)在特征,但初始解的構(gòu)建經(jīng)常依賴貪心算法,易發(fā)生求解速度較慢、陷入局部最優(yōu)等問題.

針對(duì)上述問題,本文提出一種基于深度Q學(xué)習(xí)的傳感器調(diào)度算法.首先,根據(jù)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的能量、是否激活和目標(biāo)節(jié)點(diǎn)的覆蓋情況3個(gè)特征描述當(dāng)前網(wǎng)絡(luò)狀態(tài);其次,智能體通過深度Q學(xué)習(xí)選擇激活的傳感器節(jié)點(diǎn);再次,從傳感器節(jié)點(diǎn)覆蓋目標(biāo)數(shù)量與自身能量消耗的關(guān)系設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù),指導(dǎo)環(huán)境給予智能體瞬時(shí)獎(jiǎng)勵(lì);最后,智能體進(jìn)入新的網(wǎng)絡(luò)狀態(tài).該過程迭代進(jìn)行,直到無法構(gòu)建新的可行解集為止.智能體以獲取最大累計(jì)收益為目標(biāo),不斷學(xué)習(xí)傳感器節(jié)點(diǎn)調(diào)度策略,構(gòu)建更多的可行解集,延長(zhǎng)網(wǎng)絡(luò)生命周期.

圖1 強(qiáng)化學(xué)習(xí)原理示意圖Fig.1 Schematic diagram of reinforcementlearning principle

1 深度Q學(xué)習(xí)原理

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)重要分支.智能體(Agent)在與環(huán)境交互中學(xué)習(xí)動(dòng)作策略π,獲得最大的累計(jì)獎(jiǎng)勵(lì)值.在給定某時(shí)刻t,智能體在狀態(tài)空間S中觀測(cè)當(dāng)前狀態(tài)st,在動(dòng)作空間A中選擇動(dòng)作at與環(huán)境互動(dòng)[16].環(huán)境給予智能體獎(jiǎng)勵(lì)rt,并遷移到新的狀態(tài)st+1.智能體根據(jù)rt逐步學(xué)習(xí)完善策略π.圖1為強(qiáng)化學(xué)習(xí)方法的原理示意圖.

Q學(xué)習(xí)是一種基于價(jià)值的無模型強(qiáng)化學(xué)習(xí)方法.通過動(dòng)作-價(jià)值函數(shù)Qπ(st,at)評(píng)估在當(dāng)前狀態(tài)st下,智能體根據(jù)策略π選擇動(dòng)作at后可獲得累計(jì)獎(jiǎng)勵(lì)Ut的期望值,計(jì)算公式為

Qπ(st,at)=ESt+1,At+1,…,Sn,An[Ut|St=st,At=at],

(1)

其中:Ut為折扣回報(bào);γ∈[0,1]為折扣因子,用公式表示為

Ut=rt+γrt+1+γ2rt+2+…+γn-trn.

(2)

由式(1)可知,Qπ(st,at)依賴于策略π.假設(shè)π*為最佳策略,則Q*(st,at)為最優(yōu)動(dòng)作-價(jià)值函數(shù),此時(shí)Q*(st,at)只依賴于st和at,與π不再相關(guān),即

(3)

Q*(st,at)=maxQπ*(st,at).

(4)

(5)

2 系統(tǒng)模型和問題描述

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

圖2 由5個(gè)傳感器和3個(gè)目標(biāo)組成的網(wǎng)絡(luò)Fig.2 Network consisting of five sensors and three targets

在X×Y的二維空間內(nèi)隨機(jī)部署n個(gè)傳感器節(jié)點(diǎn)覆蓋m個(gè)靜態(tài)目標(biāo).設(shè)P={p1,p2,…,pn}為傳感器節(jié)點(diǎn)集合,T={t1,t2,…,tm}為目標(biāo)節(jié)點(diǎn)集合.本文假設(shè)網(wǎng)絡(luò)中傳感器具有相同的覆蓋能力和初始能量,且節(jié)點(diǎn)部署后位置不再發(fā)生變化.圖2為由5個(gè)傳感器和3個(gè)目標(biāo)組成的網(wǎng)絡(luò).

2.2 傳感器模型

本文傳感器節(jié)點(diǎn)的感知范圍是以傳感器為圓心、半徑為k的圓形區(qū)域.傳感器節(jié)點(diǎn)pi與目標(biāo)節(jié)點(diǎn)tj的覆蓋關(guān)系采用確定性覆蓋模型[19],即pi和tj的覆蓋關(guān)系僅與雙方距離d相關(guān).pi和tj的位置通過二維坐標(biāo)表示,分別為(xi,yi)和(xj,yj).pi和tj的歐氏距離d計(jì)算公式為

(6)

當(dāng)d≤k時(shí),本文記作pi覆蓋tj.ci記錄傳感器節(jié)點(diǎn)pi可覆蓋的目標(biāo)集合.由圖2可見,c1={t1,t2},c2={t1,t3},c3={t2},c4={t3},c5={t3}.

2.3 能量模型

網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有容量為E個(gè)單位的初始能量,其中E>1.傳感器具有兩種狀態(tài),分別為休眠狀態(tài)和激活狀態(tài)[20].處于休眠狀態(tài)的傳感器節(jié)點(diǎn)不消耗能量,也無法覆蓋網(wǎng)絡(luò)中的目標(biāo);處于激活狀態(tài)的傳感器節(jié)點(diǎn)單位時(shí)間內(nèi)消耗1單位能量,對(duì)其覆蓋范圍內(nèi)的目標(biāo)持續(xù)感知.本文假設(shè)傳感器節(jié)點(diǎn)在兩種狀態(tài)轉(zhuǎn)換過程中能量消耗忽略不計(jì).傳感器節(jié)點(diǎn)在能量耗盡后被視為死亡節(jié)點(diǎn),無法被再次激活.

本文各變量含義如下:n為傳感器節(jié)點(diǎn)數(shù)量,P為傳感器節(jié)點(diǎn)集合,pi為第i號(hào)傳感器節(jié)點(diǎn),m為目標(biāo)節(jié)點(diǎn)數(shù)量,T為目標(biāo)節(jié)點(diǎn)集合,tj為第j號(hào)目標(biāo)節(jié)點(diǎn),ci為傳感器節(jié)點(diǎn)pi可覆蓋的目標(biāo)集合,CS為可行解集的集合,csi為第i個(gè)可行解集,actx為可行解集被激活的時(shí)間,L為可行解集的總數(shù),E為傳感器節(jié)點(diǎn)具有的初始能量,eix為pi節(jié)點(diǎn)單位時(shí)間消耗的能量.

2.4 目標(biāo)覆蓋問題

定義1可行解集是P的子集,該子集可覆蓋網(wǎng)絡(luò)中的所有目標(biāo)節(jié)點(diǎn).

可行解集的集合記作CS={cs1,cs2,…,csL},任一可行解集csi應(yīng)滿足以下公式:

(7)

圖2中存在可行解集cs1={p1,p4},cs2={p1,p2,p3}等.

定義2可行解集中單獨(dú)覆蓋目標(biāo)節(jié)點(diǎn)數(shù)為零的傳感器節(jié)點(diǎn)稱為冗余傳感器節(jié)點(diǎn).

冗余傳感器覆蓋的全部目標(biāo)均可由可行解集中其他傳感器節(jié)點(diǎn)覆蓋.如圖2所示,存在可行解集{p1,p3,p5},傳感器節(jié)點(diǎn)p3覆蓋的目標(biāo)t2同時(shí)也被傳感器p1覆蓋.因此,傳感器p3為冗余傳感器節(jié)點(diǎn).

定義3存在冗余傳感器節(jié)點(diǎn)的可行解集稱為冗余可行解集.

冗余可行解集會(huì)額外消耗傳感器能量,嚴(yán)重影響網(wǎng)絡(luò)生命周期.例如,傳感器p3所在的冗余可行解集{p1,p3,p5}激活,影響另一個(gè)可行解集{p2,p3}的激活時(shí)長(zhǎng),導(dǎo)致網(wǎng)絡(luò)生命周期縮短.

定義4不存在冗余傳感器節(jié)點(diǎn)的可行解集稱為非冗余的可行解集.

定義5無線傳感器網(wǎng)絡(luò)持續(xù)覆蓋所有目標(biāo)節(jié)點(diǎn)的時(shí)間長(zhǎng)度稱為網(wǎng)絡(luò)生命周期.

定義6構(gòu)建并調(diào)度無線傳感器網(wǎng)絡(luò)中的可行解集,使得網(wǎng)絡(luò)生命周期最大稱為目標(biāo)覆蓋問題.

目標(biāo)覆蓋問題建模為

其中L表示可行解集的總數(shù),actx表示可行解集被激活的時(shí)間,限制條件(9)表示任意傳感器節(jié)點(diǎn)pi在各可行解集中消耗的能量總和不超過其自身初始能量E,eix表示pi單位時(shí)間消耗的能量,限制條件(10)表示任一可行解集的工作時(shí)間非負(fù).

定理1目標(biāo)覆蓋問題得到最優(yōu)解時(shí),被激活的可行解集可全部為非冗余的可行解集.

3 算法設(shè)計(jì)

本文假設(shè)每個(gè)傳感器節(jié)點(diǎn)單位時(shí)間能耗相同,且每個(gè)可行解集的工作時(shí)間相同.求解目標(biāo)覆蓋問題的核心變?yōu)闃?gòu)建更多數(shù)量的可行解集.構(gòu)建可行解集過程中,當(dāng)前網(wǎng)絡(luò)狀態(tài)只與網(wǎng)絡(luò)的前一個(gè)狀態(tài)和激活的傳感器節(jié)點(diǎn)相關(guān),具有Markov性.狀態(tài)空間無法窮舉,且依次激活休眠節(jié)點(diǎn)符合離散問題特征.因此,本文采用深度Q學(xué)習(xí)算法對(duì)目標(biāo)覆蓋問題建模并求解.

3.1 算法建模

深度Q學(xué)習(xí)算法需要對(duì)狀態(tài)空間、智能體的動(dòng)作空間和環(huán)境給予的獎(jiǎng)勵(lì)函數(shù)進(jìn)行定義.

3.1.1 狀態(tài)

無線傳感器網(wǎng)絡(luò)的狀態(tài)通過無線傳感器節(jié)點(diǎn)狀態(tài)和目標(biāo)覆蓋狀態(tài)進(jìn)行描述,t時(shí)刻無線傳感器網(wǎng)絡(luò)狀態(tài)可表示為

St={state1,state2,…,staten,{tc1,tc2,…,tcm}},

(11)

其中: {tc1,tc2,…,tcm}記錄每個(gè)目標(biāo)被當(dāng)前網(wǎng)絡(luò)激活狀態(tài)下傳感器節(jié)點(diǎn)覆蓋的次數(shù);statei={ei,isActivei}記錄傳感器節(jié)點(diǎn)pi狀態(tài),ei為pi的剩余能量,isActivei表示pi是否被激活,取值為

(12)

初始狀態(tài)下,網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)均處于休眠狀態(tài).將無線傳感器網(wǎng)絡(luò)狀態(tài)St輸入到Q網(wǎng)絡(luò)中,估算出激活每個(gè)傳感器節(jié)點(diǎn)對(duì)應(yīng)的動(dòng)作價(jià)值,并基于此選擇被激活的傳感器節(jié)點(diǎn)pi.狀態(tài)的轉(zhuǎn)移根據(jù)此時(shí)pi的情形可分為以下4種.

1)pi處于休眠狀態(tài),此時(shí)pi從休眠狀態(tài)轉(zhuǎn)為激活狀態(tài),且網(wǎng)絡(luò)中激活的傳感器節(jié)點(diǎn)未構(gòu)成可行解集,即?tcj=0,j∈{1,2,…,m}.St+1中更新statei和目標(biāo)覆蓋情況,即statei={ei-1,1},目標(biāo)覆蓋更新公式為

tcj=tcj+1, ?tj∈ci;

(13)

2)pi處于激活狀態(tài),此時(shí)環(huán)境狀態(tài)St+1=St;

3)pi處于死亡狀態(tài),此時(shí)環(huán)境狀態(tài)St+1=St;

4)pi處于休眠狀態(tài),此時(shí)pi從休眠狀態(tài)轉(zhuǎn)為激活狀態(tài),網(wǎng)絡(luò)中處于激活狀態(tài)的傳感器節(jié)點(diǎn)可構(gòu)成一個(gè)可行解集;St+1首先按情形1)進(jìn)行更新,然后對(duì)所有傳感器節(jié)點(diǎn)狀態(tài)以及目標(biāo)覆蓋情況更新.

傳感器節(jié)點(diǎn)狀態(tài)更新公式為

statei={ei,0}, ?i∈{1,2,…,n}.

(14)

目標(biāo)覆蓋更新公式為

tcj=0, ?j∈{1,2,…,m}.

(15)

3.1.2 動(dòng)作

智能體的動(dòng)作空間表示為A={p1,p2,…,pn}.根據(jù)當(dāng)前無線傳感器網(wǎng)絡(luò)狀態(tài),智能體的動(dòng)作為選擇一個(gè)傳感器節(jié)點(diǎn)并嘗試激活.本文根據(jù)ε-greedy策略選擇出當(dāng)前動(dòng)作at,用公式表示為

(16)

3.1.3 獎(jiǎng)勵(lì)

本文從傳感器節(jié)點(diǎn)覆蓋目標(biāo)數(shù)量和自身能量消耗兩方面設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù).由定理1可知,智能體應(yīng)構(gòu)建非冗余可行解集.因此,環(huán)境應(yīng)對(duì)智能體有助于構(gòu)建非冗余可行解集的動(dòng)作給予獎(jiǎng)勵(lì),對(duì)導(dǎo)致冗余的動(dòng)作進(jìn)行懲罰.具體到每一個(gè)動(dòng)作,傳感器節(jié)點(diǎn)單獨(dú)覆蓋目標(biāo)數(shù)量越多,對(duì)應(yīng)的獎(jiǎng)勵(lì)越多;單獨(dú)覆蓋目標(biāo)數(shù)量相同的情況下,剩余能量越多,對(duì)應(yīng)的獎(jiǎng)勵(lì)越多.冗余傳感器節(jié)點(diǎn)應(yīng)該得到懲罰,且能量越少獲得的懲罰越多.已激活和死亡的傳感器節(jié)點(diǎn)沒有對(duì)構(gòu)成可行解集做出貢獻(xiàn),也沒有能量消耗,故設(shè)置獎(jiǎng)勵(lì)為0.隨著訓(xùn)練的進(jìn)行,智能體會(huì)逐漸學(xué)習(xí)到構(gòu)建更多非冗余可行解集的策略,延長(zhǎng)網(wǎng)絡(luò)生命周期.因此,智能體在時(shí)刻t選擇激活傳感器節(jié)點(diǎn)si后的獎(jiǎng)勵(lì)函數(shù)可表示為

(17)

3.2 網(wǎng)絡(luò)結(jié)構(gòu)及算法流程

(18)

由于yt部分基于事實(shí),因此Q(st,at;ω)應(yīng)向yt靠近.本文采用均方差損失函數(shù)L(ω)訓(xùn)練網(wǎng)絡(luò),計(jì)算公式為

(19)

圖3 深度Q學(xué)習(xí)算法網(wǎng)絡(luò)結(jié)構(gòu)Fig.3 Network structure of deep Q learning algorithm

算法1目標(biāo)覆蓋問題的深度Q學(xué)習(xí)算法.

輸入: 訓(xùn)練輪數(shù)e,同步參數(shù)間隔值C,記憶池容量M,數(shù)據(jù)提取批數(shù)b;

輸出: 累計(jì)獎(jiǎng)勵(lì)和網(wǎng)絡(luò)生命周期;

步驟2) 開始訓(xùn)練循環(huán),初始化累計(jì)獎(jiǎng)勵(lì)和網(wǎng)絡(luò)生命周期為0;

步驟3) 智能體感知環(huán)境得到狀態(tài)st;

步驟4) 進(jìn)入構(gòu)造可行解集循環(huán);

步驟5) 網(wǎng)絡(luò)根據(jù)ε-greedy策略選擇當(dāng)前動(dòng)作at;

步驟6) 獲得瞬時(shí)獎(jiǎng)勵(lì)rt并更新執(zhí)行動(dòng)作at后的環(huán)境狀態(tài)st+1;

步驟7) 將(st,at,rt,st+1)存入記憶池;

步驟8) 更新累計(jì)獎(jiǎng)勵(lì);

步驟9) 根據(jù)式(18)預(yù)測(cè)動(dòng)作價(jià)值;

步驟10) 隨機(jī)選取經(jīng)驗(yàn)池中b批數(shù)據(jù)訓(xùn)練,更新Q網(wǎng)絡(luò)參數(shù)ω;

步驟12) 判斷是否能繼續(xù)構(gòu)成可行解集,若無法構(gòu)建,則跳出循環(huán);

步驟13) 輸出本次得到的累計(jì)獎(jiǎng)勵(lì)和網(wǎng)絡(luò)生命周期;

步驟14) 轉(zhuǎn)至步驟2)開啟下一輪訓(xùn)練,直到訓(xùn)練輪次達(dá)到預(yù)定數(shù)量e后停止訓(xùn)練.

4 仿真實(shí)驗(yàn)

將無線傳感器網(wǎng)絡(luò)布置在80 m×80 m的矩形區(qū)域內(nèi).在該區(qū)域內(nèi)隨機(jī)部署50,100,150個(gè)傳感器節(jié)點(diǎn),隨機(jī)部署10,20,30個(gè)目標(biāo)節(jié)點(diǎn).傳感器節(jié)點(diǎn)的感知半徑為10,20,30,40 m,初始能量為3單位能量.深度Q網(wǎng)絡(luò)共有4層,其中輸入層神經(jīng)元個(gè)數(shù)與狀態(tài)維度相關(guān),中間兩個(gè)全連接層的神經(jīng)元個(gè)數(shù)分別為256個(gè)和128個(gè),輸出層神經(jīng)元個(gè)數(shù)與網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)個(gè)數(shù)相同,實(shí)驗(yàn)采用ReLU激活函數(shù).經(jīng)驗(yàn)池中可存儲(chǔ)5 000條數(shù)據(jù),每次隨機(jī)提取64批數(shù)據(jù)參與訓(xùn)練.當(dāng)經(jīng)驗(yàn)池中數(shù)據(jù)存滿后,新產(chǎn)生的數(shù)據(jù)會(huì)替換原有舊數(shù)據(jù).實(shí)驗(yàn)設(shè)置學(xué)習(xí)過程中的折扣因子為γ=0.9.

4.1 算法收斂性驗(yàn)證

在無線傳感器網(wǎng)絡(luò)中隨機(jī)部署10個(gè)目標(biāo)節(jié)點(diǎn),感知半徑為40 m的傳感器節(jié)點(diǎn)50個(gè).圖4記錄了3 000輪訓(xùn)練中智能體的累計(jì)收益.由圖4可見,智能體在訓(xùn)練初期選擇動(dòng)作較盲目,選擇較多的冗余傳感器、已激活傳感器和死亡傳感器;隨著訓(xùn)練輪數(shù)增加,智能體逐漸學(xué)習(xí)到獲取較多單步獎(jiǎng)勵(lì)的策略,累計(jì)獎(jiǎng)勵(lì)逐漸增加;訓(xùn)練2 500輪后,智能體在每輪訓(xùn)練中獲取的累計(jì)收益逐漸平穩(wěn),算法趨于收斂.

4.2 與其他目標(biāo)覆蓋算法的對(duì)比

在無線傳感器網(wǎng)絡(luò)中隨機(jī)部署10,20,30個(gè)目標(biāo)節(jié)點(diǎn),感知半徑為40 m的傳感器節(jié)點(diǎn)50,100,150個(gè).用本文提出的深度Q學(xué)習(xí)算法、3種貪心策略算法(Greedy1采取的策略為每次選擇覆蓋目標(biāo)數(shù)量最多的傳感器節(jié)點(diǎn);Greedy2算法采取的策略為選擇剩余能量最高的傳感器節(jié)點(diǎn);Greedy3算法采取的策略為選擇覆蓋最多未被覆蓋目標(biāo)的傳感器節(jié)點(diǎn))、最大壽命目標(biāo)覆蓋率算法(MLTC)[21]和自適應(yīng)學(xué)習(xí)自動(dòng)機(jī)算法(ALAA)[14]分別計(jì)算網(wǎng)絡(luò)生命周期,實(shí)驗(yàn)結(jié)果如圖5～圖7所示.由圖5～圖7可見: Greedy1算法和Greedy2算法在傳感器數(shù)量少的情況下,網(wǎng)絡(luò)生命周期與其他算法相差很小,當(dāng)傳感器數(shù)量增加,覆蓋情況復(fù)雜后,兩種算法效果均不佳;Greedy3算法、MLTC算法和ALAA算法結(jié)果較好,但在不同網(wǎng)絡(luò)環(huán)境下穩(wěn)定性有待提高;深度Q學(xué)習(xí)算法的結(jié)果優(yōu)于其他幾種算法,取得了較長(zhǎng)的網(wǎng)絡(luò)生命周期.同時(shí),實(shí)驗(yàn)結(jié)果表明,網(wǎng)絡(luò)生命周期與傳感器節(jié)點(diǎn)數(shù)量呈正相關(guān).

圖4 獎(jiǎng)勵(lì)收斂曲線Fig.4 Convergence curves of rewards

圖5 不同算法目標(biāo)數(shù)為10的網(wǎng)絡(luò)生命周期對(duì)比Fig.5 Comparison of network lifecycles with targetnumber of 10 for different algorithms

4.3 傳感器節(jié)點(diǎn)感應(yīng)半徑對(duì)網(wǎng)絡(luò)生命周期的影響

在無線傳感器網(wǎng)絡(luò)中隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn)和40個(gè)目標(biāo)節(jié)點(diǎn),傳感器節(jié)點(diǎn)的感知半徑分別為10,20,30,40 m.利用上述各算法分別計(jì)算網(wǎng)絡(luò)生命周期,實(shí)驗(yàn)結(jié)果如圖8所示.由圖8可見,當(dāng)感應(yīng)半徑為10 m時(shí),網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)覆蓋的目標(biāo)數(shù)量少,各算法計(jì)算的網(wǎng)絡(luò)生命周期近似.隨著感應(yīng)半徑的增加,每個(gè)傳感器節(jié)點(diǎn)覆蓋的目標(biāo)數(shù)量增加,每個(gè)目標(biāo)節(jié)點(diǎn)可以被更多傳感器節(jié)點(diǎn)覆蓋.因此,雖然各算法計(jì)算的網(wǎng)絡(luò)生命周期存在差異,但均顯示網(wǎng)絡(luò)生命周期與傳感器的感知半徑呈正相關(guān).

4.4 傳感器節(jié)點(diǎn)初始能量對(duì)網(wǎng)絡(luò)生命周期的影響

在無線傳感器網(wǎng)絡(luò)中布置100個(gè)傳感器節(jié)點(diǎn),同時(shí)布置20個(gè)目標(biāo)節(jié)點(diǎn),傳感器節(jié)點(diǎn)感應(yīng)半徑固定為30 m,攜帶的初始能量從3單位能量開始逐級(jí)提高至12單位能量,仿真實(shí)驗(yàn)結(jié)果如圖9所示.由圖9可見,當(dāng)傳感器攜帶能量較少時(shí),各算法網(wǎng)絡(luò)生命周期均較短.隨著攜帶能量的提高,其網(wǎng)絡(luò)生命周期對(duì)應(yīng)延長(zhǎng).因此,實(shí)驗(yàn)表明網(wǎng)絡(luò)生命周期與傳感器初始能量呈正相關(guān).

圖6 不同算法目標(biāo)數(shù)為20的網(wǎng)絡(luò)生命周期對(duì)比Fig.6 Comparison of network lifecycles with targetnumber of 20 for different algorithms

圖7 不同算法目標(biāo)數(shù)為30的網(wǎng)絡(luò)生命周期對(duì)比Fig.7 Comparison of network lifecycles with targetnumber of 30 for different algorithms

圖8 各算法對(duì)不同傳感半徑的網(wǎng)絡(luò)生命周期的影響Fig.8 Effect of each algorithm on network lifecyclewith different sensing radii

圖9 各算法對(duì)不同初始能量的網(wǎng)絡(luò)生命周期的影響Fig.9 Effect of each algorithm on network lifecyclewith different initial energies

綜上所述,針對(duì)求解無線傳感器網(wǎng)絡(luò)目標(biāo)覆蓋問題過程中存在的節(jié)點(diǎn)激活策略機(jī)理不明確、可行解集存在冗余等問題,本文提出了一種基于深度Q學(xué)習(xí)的目標(biāo)覆蓋算法對(duì)無線傳感器網(wǎng)絡(luò)目標(biāo)覆蓋問題進(jìn)行建模并求解.首先,用傳感器節(jié)點(diǎn)的能量、是否激活和目標(biāo)覆蓋情況描述網(wǎng)絡(luò)狀態(tài);其次,將智能體的動(dòng)作作為網(wǎng)絡(luò)中待激活的傳感器節(jié)點(diǎn);最后用智能體的獎(jiǎng)勵(lì)綜合考慮傳感器節(jié)點(diǎn)覆蓋目標(biāo)數(shù)量與自身能量消耗.通過訓(xùn)練,智能體學(xué)習(xí)調(diào)度網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的策略,可減少冗余現(xiàn)象發(fā)生,增加可行解集的數(shù)量.仿真實(shí)驗(yàn)結(jié)果表明,本文算法可合理調(diào)度傳感器節(jié)點(diǎn),延長(zhǎng)網(wǎng)絡(luò)生命周期.