基于WSNs的部分覆蓋應用的節點喚醒機制*

劉直良,宋三華

(黃淮學院信息工程學院,河南 駐馬店 463000)

近期,無線傳感網絡WSNs(Wireless Sensor Network)已受到廣泛關注,且在多個領域內使用,如環境監測、健康醫療以及戰場勘測[1-2]。由于WSNs由低能的傳感節點構成,無線網絡性能和感測系統壽命是許多典型應用的關鍵。因此,優化能量消耗,提高網絡壽命是WSNs的應用基礎。

節點活動時期調度策略是提高節點能效的有效手段。即在滿足覆蓋要求時,將冗余節點步入休眠狀態,進而降低能耗。此外,WSNs的全覆蓋應用要求監測區域100%的覆蓋,而一些其他應用只需要求部分覆蓋。這就是所謂的部分覆蓋問題[3-5]。例如,當WSNs應用于監測環境的濕度或溫度時,只需90%覆蓋。因此,通過部分覆蓋調度策略可延長網絡壽命,如圖1所示。

圖1 部分覆蓋等級

圖1描述了四級等級的部分覆蓋(80%、50%、60%、90%)。將監測區域劃分4個部分,每個部分的覆蓋要求不同。其中B2要求90%覆蓋,說明此區域是關鍵區域,而A2區域只需50%覆蓋。如果能夠控制傳感節點的位置的話,可以在B2區域內部署多些傳感節點,而在A2區域內部署少些節點,這樣可以減少成本。然而,不幸的是,通常是很難控制傳感節點位置。

為此,本文分析了WSNs的部分覆蓋問題,并針對部分覆蓋應用,提出基于學習自動機的節點休眠機制PCLA。PCLA機制充分利用學習自動機的優勢去分配節點的活動和休眠狀態,進而延長網絡壽命。具體而言,先喚醒部分節點和學習網絡覆蓋圖,構成主干網,然后這些節點激活鄰居節點,進而滿足網絡覆蓋和連通要求。實驗數據表明,提出的PCLA機制能夠有效地滿足部分覆蓋要求。

1 預備工作

1.1 網絡模型

假定WSNs可由一個無向連通圖表示,且命名為覆蓋圖CG(Coverage Graph)CG=(V,E),其中V={S0,S1,…,SN}為節點集。每個節點能夠感測發生在它感測范圍內的事件。假定節點的感測半徑和通信半徑分別表示為Rs和Rc,而E表示節點間的通信鏈路集[6]。對于每一對節點Si和Sj,如果Si和Sj均在彼此的通信范圍內,則邊(Si,Sj)∈E。此外,傳感節點Si的感測區域表示為γi,其為以節點Si為中心以Rs為半徑的圓。因此,節點Si的覆蓋函數Ci(x,y)可定義為:

(1)

1.2 能量模型

引用圖2所示的能效模型。向節點傳輸q比特的消息,且傳輸距離為d時,所消耗的能量表示為:

(2)

式中:Eelec、Efrris、Etworay均為傳輸能耗參數[7]。而dco的定義如式(3)所示:

(3)

式中:λ為波長、l為系統損耗。ht、hr分別表示發射天線和接收天線的增益系數。

相應地,對于接收q比特的數據包所消耗的能量:

ERX(q)=qEelec

(4)

圖2 無線電能量消耗模型

1.3 學習自動機概述

學習自動機并不是遵循預定的規則,而是依據環境變化自適應調整。學習過程的結果就是調整。學習自動機LA(Learning Automata)就是從可行的動作集內選擇最優的動作[8]。具體而言,學習自動機內含有若干個可操作的動作集。一旦某個動作被選中,并應用于環境,則產生一個增強信號。作用于環境后的響應作為反饋,并更新動作概率矢量。通過不斷的迭代,學習自動機就能夠選擇最優的動作。學習自動機與環境的相互作用示意圖如圖3所示,其中a(n)表示動作集,而β(n)表示輸出集(增強信號)。

圖3 學習自動機作用于隨機環境的示意圖

2 PCLA機制

提出PCLA機制的目的在于以最少的活動節點滿足網絡覆蓋要求。首先激活并建立節點集,并由這些節點構成主干網絡,同時保證這些節點間的連通。然后,檢測部分覆蓋是否滿足,如果不滿足,就激活部分節點,進而滿足部分覆蓋。PCLA機制由學習階段和部分覆蓋階段兩階段組成。

2.1 學習階段

學習階段的目的在于激活部分節點構成主干網。首先,在網絡內廣播HELLO消息,其包含了Ps、Pth和Tk信息。其中Ps表示監測區域所要求的覆蓋比例。而Pth為門限值,表示LA所選擇動作概率的最大值。Tk表示迭代算法的執行次數。一旦接收了此消息,每個節點就獲取這些參數,并建立CG。

令Ψ為PCLA機制建立的節點集,并不斷地進行迭代更新。對于每個節點,每個動作αi就是將節點Si添加到Ψ。而動作概率矢量p(n)初始定義為:

(5)

式中:pi(n)表示節點Si的動作概率矢量,而r表示動作集數,在數值上其等于初始階段的鄰居節點數。例如,如果節點Si有5個鄰居節點,則節點Si的動作概率矢量初始地設置為{0.2,0.2,0.2,0.2,0.2}。

初始階段完成后,就先隨機地選擇一個節點(假定是節點Si)加入Ψ。節點Si為了形成動作集,先向其鄰居傳播DISCOVERY消息。一旦接收到此消息,節點就向Si回復消息。因此,節點Si就依據所接收到的回復消息構成動作集。動作集尺寸的大小取決于節點度和網絡密度。

值得注意的是:隨機選擇的節點可能位于不同覆蓋等級區域。如果選擇的節點位于覆蓋等級要求低的區域,則只需在Ψ中添加少量節點就可滿足覆蓋要求。反之,若選擇的節點位于覆蓋等級要求高的區域,則需要添加更多的節點,才能滿足覆蓋要求。詳情見3.2節中的算法1。

當節點Si完成了動作集后,再依據它的鄰居節點的動作概率矢量p(n),選擇一個節點加入Ψ,而沒有被選中的節點歸納為Γ集。當某一個鄰居節點被選中,并加入Ψ后,該節點又重復上述過程,并從非Γ集中選擇它的鄰居節點加入Ψ。此過程一直重復,直到滿足Ψ∪Γ=V。若滿足Ψ∪Γ=V,則說明在CG內的每一個節點要么屬于Ψ要么屬于Γ。

如果沒有動作可選(例如,所選節點的所有鄰居節點已經包含在Ψ或Γ,并且Ψ∪Γ≠V)。在這種情況下,選擇過程需暫停,并重新地隨機選擇一個節點,重新開始上述過程,直到Ψ∪Γ=V。

一旦構成了節點集,就開始評估Ψ的適應性(suitability)。在每一輪n,集Ψ內的節點數與門限值Tn進行比較。如果|Ψ|

在前者情況中,集Ψ每個節點向它的活動鄰居節點廣播REWARD消息,再依據式(6)更新動作概率矢量:

(6)

式中:pj(n)表示動作pi(n)的概率。

相反,在后者情況中,就向Ψ集內的活動節點廣播懲罰PENALTY消息。一旦收到PENALTY消息,所選動作的概率固定,同時依據式(4)更新動作概率矢量:

(7)

式中:r表示動作數。

更新后,就檢測是否滿足式(8)的條件。如果滿足,就結束學習過程[9]。

(8)

師：說的很好，他在描述這6個面的時候，注意到了從這6個面的形狀、大小和位置關系的角度去描述．那12條棱和8個頂點呢？

圖4描述了自動學習過程,監測區域內部署了16個傳感節點。在最初,隨機選擇節點S7加入Ψ,然后節點S7就依據動作概率矢量,選擇一個鄰居節點(S6)加入Ψ。此過程一直重復,直到區域內的所有節點要么在Ψ集內,要么在Γ集內。從圖4可知,節點S10、S15在第1輪周期內被選擇加入Ψ集內。

因此,集|Ψ|的基數等于4。然后計算Ψ集的節點的剩余能量EΨ。如果EΨ大于當前門限值En,就發送REWARD消息,否則就發送PENALTY消息。一旦收到REWARD消息或PENALTY消息,就依據式(3)或式(4)更新動作概率矢量。

圖4 學習階段

2.2 部分覆蓋階段

學習階段結束后,PCLA機制就檢測是否滿足部分覆蓋PCO(Partial Coverage)。如果滿足PCO條件,就取消FormPartialCoverage()函數的執行。此函數就是激活集Γ的節點去滿足PCO的要求,同時估計由集Γ活動節點所能覆蓋的元(覆蓋的單位區域)數[7]。具體而言,如果節點能夠覆蓋一個元,且沒有其他鄰居節點覆蓋此元,該節點就被激活。因此,就向該節點發送激活ACTIVATION消息。FormPartialCoverage()函數的偽代碼如算法1所示。

圖5 算法1的偽代碼

此外,圖6描述了PCLA機制中的PCO示例。以圖4為例,假定學習階段所提供的節點集不能滿足覆蓋要求[10],因此,需要添加節點去實現PCO。從圖6可知,激活了傳感節點S4和S12。

圖6 PCO示例

3 性能仿真

3.1 仿真參數及性能指標

為了更好地分析PCLA性能,選擇文獻[11]所提出的CDS機制和文獻[12]所提出的DFS機制作為比較,并進行同步仿真。

3.2 實驗1

圖7 平均區域覆蓋度D?對節點工作率的影響

從圖7可知,隨著平均區域覆蓋度D?的增加,節點工作率φ呈下降趨勢。與CDS和DFS算法相比,提出的PCLA機制的工作率φ得到有效地下降,這有利于網絡能效的提高。這要歸功于PCLA機制盡可能選擇少數節點組建主干網絡,降低了節點的工作時間。此外,也注意到,當D?=1.5上升至D?=5時,工作率φ得到顯著地下降。

3.3 實驗2

本次實驗分析Ps對活動節點數的影響,且Ps從0.6至0.9變化,實驗數據如圖8所示。

圖8 活動節點數

正如所期望的,3個機制的活動節點數隨Ps的增加而上升。原因在于:Ps越大,越需要更多的節點監測興趣區域。此外,與CDS和DFS相比,提出的PCLA機制的活動節點數得到有效控制,且隨著Ps的增加,優勢越明顯。

圖9 網絡壽命隨Dθ的變化情況

3.4 實驗3

最后,分析各機制的網絡壽命。其中網絡壽命是指從部署網絡的時間至網絡覆蓋首次未滿足要求的時間,實驗數據如圖9、圖10所示。

從圖9、圖10可知,PCLA機制的網絡壽命高于CDS和DFS,且比CDS提高的幅度從15%至52%變化。而比DFS的網絡壽命提搞了約34%至86%。從這些數據說明,提出的PCLA機制通過自動學習算法優化了節點休眠時間,減少了活動節點數,進而提高了網絡壽命。

圖10 網絡壽命隨PS的變化情況

4 總結

針對WSNs的部分覆蓋問題,提出基于學習自動機的節點喚醒機制PCLA。PCLA機制先利用學習自動機建立主干網,然后基于部分覆蓋要求,喚醒部分節點,進而滿足覆蓋要求。實驗數據表明,提出的PCLA機制能夠有效地減少活動節點數,并降低能耗,進而延長網絡壽命。

參考文獻:

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 陳東海,李長庚. 基于簇頭功能分化的無線傳感器網絡成簇算法[J]. 傳感技術學報,2015,28(2):244-248.

[3] 沈艷霞,薛小松. 無線傳感網絡移動信標節點路徑優化策略[J]. 傳感器與微系統,2012,31(12):42-46.

[4] Zhao F,Liu J. Collaborative Signal and Information Processing:An Information Directed Approach[J]. Processing IEEE,2013,91(8):1199-1209.

[5] Botta A,de Donato W,Persico V,et al. On the Integration of Cloud Computing and Internet of Things[C]//Proceedings of the IEEE International Conference on Future Internet of Things and Cloud(Fi Cloud),2014:23-30.

[6] Qianqian Y,Shibo H,Junkun L,et al. Energy-Efficient Probabilistic Area Coverage in Wireless Sensor Networks[J]. IEEE Trans Veh Technol,2015,64(1):367-377.

[7] Botta A,de Donato W,Persico V,et al. Integration of Cloud Computing and Internet of Things:A Survey[J]. Future Gener Comput Syst,2016,3(56):684-700.

[8] Mostafaei H,Montieri A,Persico V,et al. An Efficient Partial Coverage Algorithm for Wireless Sensor Networks[C]//2016 IEEE Symposium on Computers and Communication(ISCC)(ISCC2016),Messina,Italy,2016:501-506.

[9] Mostafaei H,Shojafar M. A New Meta-Heuristic Algorithm for Maximizing Lifetime of Wireless Sensor Networks[J]. Wirel Pers Commun,2015,82(2):723-742.

[10] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[11] Donghyun K,Yiwei W,Yingshu L,et al. 2009. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J]. IEEE Trans Parallel Distrib Syst,2016,20(2):147-157.

[12] Wu Y,Ai C,Gao S,et al. p-Percent Coverage in Wireless Sensor Networks,vol.5258 of Lecture Notes in Computer Science[J]. Springer Berlin Heidelberg,2014,3(6):200-211.