基于學習機的WSNs柵欄覆蓋構建算法*

劉紹剛

(滇西科技師范學院信息工程學院,云南 臨滄 677000)

無線傳感網絡WSNs(Wireless Sensor Networks)已廣泛應用于多類領域。而柵欄覆蓋(Barrier Coverage)是應用于邊界監測或戰場勘察的一種覆蓋模型[1]。所謂柵欄覆蓋是指將傳感節點部署于狹長的帶狀區域,并由傳感節點對移動目標進行檢測的技術。例如,在邊境監測應用中,利用柵欄覆蓋檢測非法入境者[2];在林業保護應用中,利用柵欄覆蓋,可檢測火勢蔓延數據。

與點覆蓋、區域覆蓋等傳統覆蓋不同,柵欄覆蓋是部署于狹長區域,并不需要傳感節點覆蓋整個部署區域[3],但需要由多個傳感節點協作形成橫穿部署區域的柵欄,如圖1所示。在L×W的狹長部署區域(L>W)內,存在三條柵欄,它們橫穿整個部署區域[4]。

圖1 柵欄覆蓋示例

每條橫穿部署區域的柵欄也稱為穿越路徑CP(Crossing Path)。穿越路徑是一條由多個節點協作構成的路徑,且橫穿區域。因此,如何構建CP是柵欄覆蓋的基礎。此外,由于WSNs中傳感節點屬于微型設備,存在能量受限問題。一旦節點能量耗盡,就形成覆蓋空洞區域。因此,構建CP就是以最小的傳感節點數構建成橫穿部署區域的柵欄。節點數越小,能耗也就越小,覆蓋時間也就越長。

目前,國內外研究人員對柵欄覆蓋問題進行了不少的研究。在國外,文獻[5]采用休眠/喚醒機制處理柵欄覆蓋問題,通過休眠/喚醒機制擴延網絡壽命和目標檢測質量。而文獻[6]研究了二維和三維WSNs區域的柵欄覆蓋問題,并推導的分布式算法,證實了可形成最優節點集覆蓋邊界。同時引用自修復算法。此外,文獻[7]引用拉格朗日松弛技術分析了柵欄覆蓋的成本問題,并提出兩類啟發式算法解決柵欄覆蓋問題。

而國內研究學者對柵欄覆蓋問題也進行了較深入研究。例如,文獻[4]提出分區強的k-柵欄覆蓋算法。將檢測區劃分多算法子區,并引用匈牙利算法優化覆蓋集。但是此算法并沒有關注算法的能效問題,類似地,文獻[8]提出概率柵欄覆蓋算法,并利用虛擬半徑確定形成概率柵欄的目標位置。而文獻[1]提出基于粒子群的有向傳感網絡的柵欄覆蓋增強算法,其將多維求解問題轉化一維,降低了算法復雜度。然而該算法是針對有向傳感網絡。

為此,考慮到柵欄覆蓋的復雜性以及學習機的特性,提出基于學習機的柵欄覆蓋算法BCLA(Barrier Coverage based on Learning Automata)。BCLA算法利用學習機建立節點動作概率矢量,并選擇具有最大概率的節點構建柵欄。實驗數據表明,提出的BCLA算法在限定節點數的條件下,增加了構建的柵欄數。

圖2 不同節點的感測和通信示意圖

1 約束條件

假定N個節點隨機分布于L×W的部署區域A。節點的感測半徑、通信半徑分別為Rs、Cs,且感測范圍和通信范圍均為圓形,如圖2所示。不失一般性,假定Cs≥2Rs。

引用二值感測模型BSM(Binary Sensing Model)[9]。如果目標位于節點si的感測范圍內,則節點si檢測該目標的概率為1,否則為零,如式(1)所示:

(1)

式中:d(si,P)表示節點si(xi,yi)與目標P(x,y)間歐式距離,其定義如式(2)所示:

(2)

引用圖論(Coverage Graph,CG)表示網絡拓撲結構。令G=(V,E),其中V為頂點(節點)集,且V={s1,s2,…,s|V|}。而E為邊集,且E={e1,e2,…,e|E|},其中|V|、|E|分別表示頂點數、邊數。此外,考慮兩個虛擬的傳感節點,其分別在網絡的左、右邊界,并將它們分別稱為源節點S和目的節點T。如圖3所示,圖3顯示了兩條穿越路徑的網絡,左、右兩邊分別為虛擬的源節點和目的節點。所謂穿越路徑CP(Crossing Path)是橫穿整個部署區域的路線,入侵者若想竄入區域,至少被該路線的某一個節點發現。

然而,為了加強對部署區域的防護,增強柵欄覆蓋性能,在部署區域僅構建一條CP是不夠的,通常部署k條CP,這也稱為k-柵欄覆蓋。在k-柵欄覆蓋中,當入侵者竄入部署區域,至少被位于不同CP的k個傳感節點所感知。圖3顯示了2-柵欄覆蓋(k=2)情況。

本文需要解決的問題就是如何構建CP,進而實現k-柵欄覆蓋。

圖3 k-柵欄覆蓋(k=2)

2 學習機概述

學習自動機LA(Learning Automata)是利用與環境不斷的交互,調整自己行為的學習算法。即依據環境條件,從可選的動作集中選擇最優的動作。所謂最優動作是指能得到環境獎勵概率最大的動作。此外,本文引用的主要變量標識如表1所示。

表1 變量標識符

LA屬迭代算法,其目的在于從動作集中選擇最優的動作[10]。LA與環境相互作者的示意圖如圖4所示。

圖4 LA工作模型

利用組E={α,β,c}描述環境,其中α={α1,α2,…,αr}為有限動作集,而β={β1,β2,…,βr}為輸出集,其受環境加強信號控制。c={c1,c2,…,cr}為懲罰概率集,且c中每一個元素ci與動作集α中的αi一一對應。

而本文引用文獻[11]的變量-結構學習機。因此,可利用式(3)表述學習過程:

p(n+1)=T[p(n),α(n),β(n)]

(3)

式中:T為學習函數。而p(n+1)、p(n)分別表示在第n+1、n輪的選擇動作α(n)的概率。

令α(k)表示LA在第k輪所選擇的動作,而p(k)表示選擇此動作集的概率。當環境給出的是增強信號,即懲罰因子β(n)=0,就依據式(4)對概率p值進行更新:

(4)

若給出的減弱信號(需進行懲罰),對依據式(5)對概率p值進行更新:

(5)

式中:pi(n)、pj(n)分別表示選擇動作i、j的概率。而r是動作集數。而式(4)和(5)中的a和b分別表示獎勵和懲罰因子。

3 BCLA算法

BCLA算法主要由初始階段、學習階段和監測階段組成,其中監測階段用于構建柵欄。

3.1 初始階段

最初,每個節點廣播通告消息,其包含節點位置和ID號。一旦接收來自鄰居節點發送的通告消息,節點就將此發送節點作為鄰居節點,并記錄此節點的ID。假定節點si收到了M條通告消息,則節點si共有M個鄰居節點,且用Ni={s1,…,sM}表示節點si的鄰居集。

圖5 網絡拓撲示例

值得注意的是,這是動作概率的初始值。在學習階段,會通過對環境的學習,更新動作概率值。

3.2 學習階段

學習階段完成對動作概率值的更新。首先,源節點先依據動作概率矢量P選擇下一跳節點。選擇原則:從P中選擇最大動作概率加入CP,用ψCP表示已加入CP的節點集,最初ψCP=φ。如果動作概率相同,則首先將比自己橫坐標小的節點的動作暫停(不選擇),然后,再從剩余的動作集中隨機選擇[13]。由于柵欄覆蓋是在狹長區域,則可以只利用橫坐標信息選擇節點。

仍以圖5為例,節點4共有5個動作(5個鄰居節點),且初始動作概率均為0.2,即P4={0.2,0.2,0.2,0.2,0.2}。而節點1、2、5的橫坐標均小于節點4的橫坐標。因此,節點4只可能從6、7這兩個節點中隨機選擇一個節點。

一旦選定了節點,就向其發送動作消息A_Mes。接收到A_Mes消息,則先計算將自己加入CP后,ψCP內所有節點的平均剩余能量。具體而言,節點si向節點sj發送了A_Mes消息,則節點sj先計算自己和ψCP內所有節點的剩余能量的均值Eave:

(6)

如果Eave大于Emin,且|ψCP|+1小于Cmin,即滿足式(7),則節點sj向就節點si獎勵R_Mes消息:

(7)

式中:Emin、Cmin為系統參數,且分別表示最已選節點的最小剩余能量、已選節點的最少節點數。

一旦收到R_Mes消息,節點si就對節點sj的所對應的概率值進行獎勵[14]。相應地,對其他動作集進行懲罰,即依據式(4)進行更新概率矢量。因此,節點sj的動作概率值就被增加,相比之下,其他動作集的概率值就減少了。

若不滿足式(7),則就發送懲罰消息P_Mes消息。一旦收到P_Mes消息,節點si就式(5)更新概率,即對節點sj懲罰,相比之下,就是對其他動作集進行嘉獎,它們的概率值就增加了。以節點si和節點sj為例,上述過程如圖6所示。

圖6 動作概率更新過程示例

從上述過程可知,BCLA算法通過學習自動機選擇最優節點構建CP,具體而言。節點依據自己鄰居節點數,計算初始動作概率矢量,然后再計算反饋信號,即利用式(6)計算剩余能量,然后再利用學習機,進行懲罰或獎勵,即利用式(7)判斷。最終對動作概率矢量進行更新。對應圖4,可得出圖7,其顯示了BCLA算法如何利用學習機選擇節點。

圖7 基于LA的BCLA算法

3.3 構建CP階段

完成了學習階段后,每個節點已保存了動作概率矢量。因此,每個節點就選擇具有最大動作集的節點作為CP的下一個節點。然后,向使已選擇的節點發送活動狀態消息Act_Mes,一旦接收了該消息,節點就保持活動狀態,而其他未被選中的節點處于休眠狀態,這有利于保存能量,提高能量效率。換而言之,構建CP過程,就是激活節點狀態的過程。只有在CP內的節點,才保持活動狀態。圖8顯示了節點活動狀態過程。

圖8 節點活動狀態流程

4 性能仿真

為了更好地分析BCLA算法的性能,利用NS-2.34軟件建立仿真平臺[15]。N個傳感節點分布于200 m×150 m部署區域內。仿真參數如表2所示。

表2 仿真參數

同時,選擇文獻[16]的不相交路徑DPA(Disjoint Path Algorithm)和文獻[17]所提出的最大強柵欄算法MSBA(Maximizing Strong Barriers Algorithm)算法作為參照,并分析它們所建立的柵欄數的性能。在同等條件下,柵欄數越多,性能越好。此外,考慮到數據的隨機性,每次實驗獨立重復30次,取平均值作為最終的實驗數據。

圖9 節點數對柵欄數的變化

4.1 實驗1

本次實驗分析節點數N對柵欄數的影響,其中實驗條件:節點的感測半徑Rs=30,N從100至400變化,且步長為50,實驗數據如圖9所示。

從圖9可知,節點數N的增加,增加了柵欄數。這與預期的相吻合:節點數越多,可選擇加入穿越路徑的節點了就越多。與DPA、MSBA算法相比,BCLA算法的能夠建立更多的柵欄數。例如,當N=400時,BCLA算法的柵欄數比DPA算法提高了近65%。而與MSBA算法相比,提出的BCLA算法的所建立的柵欄數平均提高了8%。這主要是因為MSBA算法是利用EdmondsKarp算法[18]建立柵欄數,而BCLA算法采用分布式算法,且每個節點利用LA進行學習,實現了以最少的節點數構建一條CP。

4.2 實驗2

本次實驗分析節點的感測半徑Rs對柵欄數的影響,其中實驗條件:節點數N=300,Rs從15至40變化,步長為5,實驗數據如圖10所示。

圖10 感測半徑Rs對柵欄數的影響

從圖10可知,感測半徑Rs的增加,有利于柵欄數的建立,原因在于:感測半徑越大,構建一條CP的所需節點數也就越少。在總的節點數不變的情況下,就能夠建立更多的柵欄數。與DPA和MSBA算法相比,提出的BCLA算法的柵欄數得到提高。當Rs=40時,BCLA算法的柵欄數比DPA提高了近63%。

從上述的仿真數據可知,提出BCLA能夠以最少的節點數構建柵欄數,原因在于:BCLA算法充分利用了學習機對環境的自適應能力,能夠應對環境變化,進而優化了柵欄數。

4.3 實驗3

本次實驗分析算法的復雜度,并選擇時間復雜度指標反映算法的復雜度。假定BCLA算法中部署的節點數為N、邊數為E。BCLA算法、DPA和MSBA算法的時間復雜度如表3所示,其中K表示在學習階段的迭代次數,V表示頂點數。

表3 時間復雜度

從表3可知,DPA算法的時間復雜度為O(KE),最低,而BCLA算法的復雜度達到O(V2E2N)。MSBA算法的時間復雜度為O(V5E5)。從這些數據可知,提出的BCLA算法的時間復雜度高于DBA算法,但是低于MSBA算法。

5 總結

柵欄覆蓋已廣泛應用于邊界檢測。通過建立柵欄可有效地檢測邊界入侵者。而如何利用節點構建柵欄是實現柵欄覆蓋的關鍵。本文提出基于學習機的柵欄構建算法。該算法充分學習機對環境學習能力,利用環境的反饋信號對動作集進行增強或減弱,進而選擇最合適的節點構建柵欄。實驗數據表明,提出的BCLA算法能夠有效地構建柵欄,增加可建柵欄數。

后期,將研究節點能耗問題。即在滿足柵欄覆蓋要求的條件下,如何降低網絡能耗,使得每條柵欄覆蓋壽命能得到最大化,這將是后期研究工作的重點。此外,BLCH算法目的在于:利用有限的節點數,構建更多的柵欄數,用于檢測入侵者。在實際應用中,可采用輪換機制,即多條柵欄輪流工作,進而降低網絡能耗。這也是后期的工作重點。