基于深度Q學習的無線傳感器網(wǎng)絡目標覆蓋問題算法

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

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

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

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

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

圖1 強化學習原理示意圖Fig.1 Schematic diagram of reinforcementlearning principle

1 深度Q學習原理

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

(5)

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

2.1 網(wǎng)絡模型

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

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

2.2 傳感器模型

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

(6)

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

2.3 能量模型

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

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

2.4 目標覆蓋問題

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

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

(7)

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

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

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

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

冗余可行解集會額外消耗傳感器能量,嚴重影響網(wǎng)絡生命周期.例如,傳感器p3所在的冗余可行解集{p1,p3,p5}激活,影響另一個可行解集{p2,p3}的激活時長,導致網(wǎng)絡生命周期縮短.

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

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

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

目標覆蓋問題建模為

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

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

3 算法設計

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

3.1 算法建模

深度Q學習算法需要對狀態(tài)空間、智能體的動作空間和環(huán)境給予的獎勵函數(shù)進行定義.

3.1.1 狀態(tài)

無線傳感器網(wǎng)絡的狀態(tài)通過無線傳感器節(jié)點狀態(tài)和目標覆蓋狀態(tài)進行描述,t時刻無線傳感器網(wǎng)絡狀態(tài)可表示為

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

(11)

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

(12)

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

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

tcj=tcj+1, ?tj∈ci;

(13)

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

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

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

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

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

(14)

目標覆蓋更新公式為

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

(15)

3.1.2 動作

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

(16)

3.1.3 獎勵

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

(17)

3.2 網(wǎng)絡結構及算法流程

(18)

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

(19)

圖3 深度Q學習算法網(wǎng)絡結構Fig.3 Network structure of deep Q learning algorithm

算法1目標覆蓋問題的深度Q學習算法.

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

輸出: 累計獎勵和網(wǎng)絡生命周期;

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

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

步驟4) 進入構造可行解集循環(huán);

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

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

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

步驟8) 更新累計獎勵;

步驟9) 根據(jù)式(18)預測動作價值;

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

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

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

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

4 仿真實驗

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

4.1 算法收斂性驗證

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

4.2 與其他目標覆蓋算法的對比

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

圖4 獎勵收斂曲線Fig.4 Convergence curves of rewards

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

4.3 傳感器節(jié)點感應半徑對網(wǎng)絡生命周期的影響

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

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

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

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

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

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

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

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