基于能量均衡的最大化覆蓋目標算法*

南書坡,馮乃勤

(1.河南師范大學新聯學院,鄭州 451464;2.河南師范大學計算機與信息工程學院,河南 新鄉 453007)

基于能量均衡的最大化覆蓋目標算法*

南書坡1*,馮乃勤2

(1.河南師范大學新聯學院,鄭州 451464;2.河南師范大學計算機與信息工程學院,河南 新鄉 453007)

目標覆蓋問題是無線傳感網絡WSNs(Wireless sensor networks)最重要的問題之一。每個目標至少被一個傳感節點覆蓋,為此提出基于能量均衡的最大化覆蓋目標EMNL(Energy-balance-based Maximizing Network Lifetime)算法。EMNL算法將所有傳感節點劃分不同的傳感節點覆蓋區SC(Sensor Cover),致使每個SC能夠維持對所有目標監測一個固定時間。通過有選擇性選擇一個SC活動,而其他SC休眠,進而提高能量利用率,延長了網絡壽命。EMNL算法構建了不同不相鄰SC,進而最大化網絡壽命。最后,建立仿真環境,并進行性能仿真。此環境下的數據表明,在EMNL算法有效地擴延生存時間,也提升了覆蓋率。

無線傳感網;能量;目標覆蓋;傳感節點覆蓋區;生存時間

近期,無線傳感網絡 WSNs(Wireless Sensor Networks)受到廣泛關注。WSNs是由大量的微型、能量受限、低功耗的傳感節點組成。這些傳感節點具有感測數據、處理以及存儲功能[1]。將這些傳感節點部署于監測區域,如森林、戰場。這些部署了傳感節點的監測區域稱為興趣區域。在興趣區域內,每個傳感節點試著感測環境數據,然后再將數據傳輸管理中心。

為了實時地、無遺漏地監測環境,就需要保證傳感節點對興趣區域覆蓋率的最大化。然而,由于傳感節點存在硬件故障以及能耗問題,難以保證所有傳感節點能正常工作。一旦傳感節點能耗殆盡,它就無法工作,也無法感測數據,就出現覆蓋空洞。因此,如何提高興趣區域的覆蓋率已成WSNs的研究熱點[2-3]。

依據覆蓋區域面積的不同,可將覆蓋劃分為點覆蓋和區域覆蓋。所謂點覆蓋是指由一個單一的傳感節點覆蓋的區域,而區域覆蓋是由一群傳感節點共同覆蓋的區域。然而,實際上,無論是點覆蓋還是區域覆蓋,均需要維持興趣區域的覆蓋率。

通常,WSNs覆蓋要求是:以有限的能量對興趣區域實施盡可能的連續監控。本文著重關注區域覆蓋問題。將這些需要被覆蓋的區域也稱不目標覆蓋區域,簡稱為目標覆蓋[4-5]。換而言之,以目標覆蓋為本文的研究對象,研究的目的在于對多個目標覆蓋區域進行盡可能長時間的監控。

為了保存節點能量,傳感節點通常具有活動和休眠兩種狀態。在活動狀態時,傳感節點實時監控環境,其將消耗大量能量。而在休眠狀態,傳感節點處于空閑狀態,不消耗能量。

為了保證所有覆蓋目標能夠最大時間地覆蓋,常采用的方法不是保證所有傳感節點均在活動狀態,而是選擇一部分節點能夠覆蓋目標區域。這一部分節點稱為傳感節點覆蓋區SC(Sensor Cover),它們的活動時間稱為生存時間。因此,覆蓋目標問題是就是保證這些SC在固定時間內工作,進而監控興趣區域。所有SC的生存時間就是網絡壽命。

目前,針對目標覆蓋問題已進行了大量的研究工作[6-7]。文獻[8]提出高能效啟發式算法HEEH(High-Energy-Efficient Heuristic)。HEEH算法僅選擇能量最多的傳感節點構成不相鄰的覆蓋集,并最小化SC集,進而消除覆蓋冗余問題。文獻[9-10]也提出利用整數線性規劃ILP(Integer Linear Programming)構建SC集。此外,文獻[11]也提出基于權重的啟發式算法WH(Weight-based Heuristic)。WH算法先選擇剩余能量最高的節點構建SC,然后再優化。

為此,本文針對WSNs的目標覆蓋問題,提出基于能量均衡的最大化覆蓋目標EMNL(Energy-Balance-Based Maximizing Network Lifetime)算法。EMNL算法先將傳感節點劃分不同的傳感節點覆蓋區SC(Sensor Cover),致使每個SC覆蓋所有目標一段時間,進而平衡網絡能耗,提高網絡壽命。實驗數據表明,提出的EMNL算法有效地延長網絡壽命,并增加覆蓋率。

1 約束條件

假定在M×M區域內隨機分布了n個覆蓋目標T={t1,t2,…,tn}。為最大時間地監測這些覆蓋目標,在整個M×M區域內隨機部署m個傳感節點,即S={s1,s2,…,sm}。其中,每個傳感節點的傳輸半徑為Rs。傳感節點si的初始能量為bi。

此外,每個傳感節點存在活動和休眠兩種狀態,它們可彼此切換。在活動狀態,傳感節點感測目標覆蓋區域內的信息,而在休眠狀態,傳感節點不感測信息,進而保存能量。

此外,本文引用的標識符如表1所示。

定義1傳感-目標覆蓋關系矩陣Rm×n矩陣Rm×n中元素Rij的定義如式(1)所示:

(1)

定義2關鍵目標集CTS(Critical Target Set) 在整個覆蓋目標集T內,若一覆蓋目標內所有節點的能量和是最小的,則該覆蓋目標稱為CTS,定義如式(2)所示:

(2)

定義3關鍵節點CS(Critical Sensor) 若節點至少覆蓋了一個CTS,則該傳感節點就稱為CS。

定義4傳感節點覆蓋區SC(Sensor Cover) 對于任意SC區Ck,它是由矩陣R的一系列行組成。致使,對于每一列j,至少在Ck內有一行i滿足Rij=1。

定義5傳感節點覆蓋區SC的生存時間Ck的生存時間等于Ck內節點的最小電池供電時間,定義如式(3)所示:

(3)

定義6網絡壽命L網絡壽命就是所有SC的生存時間之和,定義如式(4)所示:

(4)

式中:|C|為網絡內SC的個數。

為了更好地理解上述定義,舉例說明。假定網絡內存在4個傳感節點s1、s2、s3以及s4,3個覆蓋目標t1、t2、t3。此外,假定每個傳感節點的初始能量均為1(bi=1)它們的矩陣R4×3定義如下:

t1t2t3

(5)

依據R4×3內的元素可知,傳感節點s1覆蓋t2、t3,即s1={t2,t3}。類似地,s2={t1,t2}、s3={t1,t3}、s4={t1,t3}。依據定義2可知,覆蓋目標t2為CTS,因為只有t2只被兩個節點覆蓋,它的生存時間最低僅為2,相應地,傳感節點s1、s2為CS節點。

2 EMNL算法

EMNL算法就是先計算CTS以及SC,然后再用它們構建SC。具體而言,當明確了CTS,就計算覆蓋所有CTS的最小數的SC,而對于剩余未覆蓋目標,就從剩余的傳感節點集中尋找剩余能量最大的傳感節點,然后再從這些節點中選擇具有最大目標覆蓋的節點。EMNL協議的目的就是選擇傳感節點,致使所有目標集都被覆蓋。

首先,利用定義2、定義3計算CTS、SC。這兩個集分別表示為Tcritical、Scritical。然后構建Ck。具體構建步驟如下:

(6)

構建Ck完整過程的偽代碼如圖1所示。

圖1 算法1的偽代碼

算法1中UB表示SC數。網絡內m個傳感節點它們的能量分別為{b1,b2,…,bm}和n個覆蓋目標{t1,t2,…,tm}。而覆蓋目標tj的最大覆蓋時間為Uj,定義如式(7)所示:

(7)

現在,取網絡壽命的上限,因此,UB的定義如式(8)所示:

UB=min{U1,U2,…,Un}

(8)

為了降低能耗,就是降低Ck集數。因此,利用最小化函數最小化Ck數。而最小化函數的偽代碼過程如圖2所示。

圖2 算法2的偽代碼

EMNL協議通過構建多個SC,致使每個SC覆蓋整個目標,同時最大化網絡壽命。仍以式(6)所示的矩陣R4×3為例。依據文獻[8]所采用的算法HEEH僅產生一個CS,即C1={s1,s2},其網絡壽命為1單元。而文獻[11]所采用的算法WH,是選擇最高能量的節點構建SC,它與HEEH算法產生相同的C1={s1,s2}。而EMNL算法產生一個CTS集t2,并且由傳感節點s1、s2覆蓋。最后,EMNL算法產生兩個SC,分別為C1={s1,s3}、C2={s2,s4},并且網絡壽命為2。

3 性能分析

3.1 仿真參數

本小節對EMNL算法進行仿真,分析EMNL算法的性能[12]。考慮200 m×200 m的網絡區域,仿真參數表1所示。在性能分析過程中,選擇平均SC規模、SC的生命周期、剩余能量、網絡覆蓋率作為性能指標。同是選擇HEEH[8]和WH[11]兩個算法作為參照。每次仿真獨立重復100次,取平均值作為最終的實驗數據。

表1 仿真參數

3.2 數值分析

首先,分析了SC的生存時間。圖3顯示了平均SC的生存時間隨節點數的變化情況。依圖3可知,生存時間隨節點數的增加而下降,原因在于:節點數增加,相應地活動節點的比例也越大,最終,導致網絡能耗增加。與HEEH和WH相比,EMNL算法的平均生存時間得到有效地提高。原因在于:EMNL能夠有效構建SC,并平衡網絡能耗,提高能量利用率。

圖3 SC的生存時間

其次,分析了網絡的剩余能量,數值結果如圖4所示。圖4的數據來自于仿真了7 200 s后網絡的剩余能量。依圖4可知,網絡剩余能量隨節點數的增加而呈下降趨勢。與HEEH和WH算法相比,EMNL算法的剩余能量最多。原因在于EMNL算法能夠有效地利用能量,平衡了能耗。

圖4 剩余能量

圖5 覆蓋率

最后,分析了EMNL算法的覆蓋率,實驗數據如圖5所示。從圖5可知,覆蓋率隨節點數增加而上升,原因很簡單:節點越多,覆蓋區域面積越多,最終覆蓋率越高。此外,在節點數較低時,HEEH和WH算法的覆蓋率極低,而EMNL算法達到97%。隨著節點數的增加,HEEH和WH算法的覆蓋率也逐漸升高,但仍低于EMNL算法的覆蓋率。

4 總結

本文針對無線傳感網絡的覆蓋問題,提出EMNL算法。EMNL算法從能量平衡角度,將傳感節點劃分不同的SC。在某一時刻,所有目標只由一個SC覆蓋,而其他SC休眠,進而保存網絡能量,提高網絡壽命。實驗數據也證實,與HEEH和WH算法相比,EMNL算法有效地降低能耗,提高了網絡壽命。

[1] Rehman A,Abbasi A Z,Islam N,et al. A Review of Wireless Sensors and Networks Applications in Agriculture[J]. Compute Stand Interfaces,2014,36(2):263-270.

[2] Li Z,Wang N,Franzen A,et al. Practical Deployment of an In-Field Soil Property Wireless Sensor Network[J]. Compute Stand Interfaces,2014,36(2):278-287.

[3] Alcaraz C,Lopez J. Diagnosis Mechanism for Accurate Monitoring in Critical Infrastructure Protection[J]. Compute Stand Interfaces,2014,36(3):501-512.

[4] 付永生,李善平,周波. 無線傳感網絡中能量均衡的連通支配集算法[J]. 傳感技術學報,2012,23(8):114-1145.

[5] Guha S,Khuller S. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica,2014,20(4):374-387.

[6] Yin B,Shi H,Shang Y. An Efficient Algorithm for Constructing a Connected Dominating Set in Mobile Ad Hoc Networks[J]. Journal of Parallel and Distributed Computing,2011,71(1):27-39.

[7] 張靜,賈春福. 無線傳感器網絡基于權值的極小支配集路由算法[J]. 傳感技術學報,2009,22(12):1784-1788.

[8] Manju A. High-Energy-First Heuristic for Energy Efficient Target Coverage Problem[J]. Int J Ad Hoc Sens Ubiquit Comput,2011,2(11):45-58.

[9] Wu J. Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links[J]. IEEE Trans on Parallel and Distributed Systems,2012,13(9):866-881.

[10] 陳勤,朱韜,張旻. 基于域的分布式最小連通支配集啟發式算法[J]. 計算機系統應用,2011,20(2):201-205.

[11] Mini S,Udgata S K,Sabat S L. Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks[J]. IEEE Sensor Journal,2014,14(3):636-644.

[12] Orhan D,Kayhan E,Savio Tse. Semi-Asynchronous and Distributed Weighted Connected Dominating Set Algorithms for Wireless Sensor Networks[J]. Computer Standards and Interface,2015(42):143-156.

南書坡(1980-),男,漢,河南唐河人,碩士,講師,研究方向為數據挖掘,人工智能。

Energy-Balance-BasedMaximizingNetworkLifetimeAlgorithminWirelessSensorNetworks*

NANShupo1*,FENGNaiqin2

(1.Xinlian College,Henan Normal University,Zhengzhou 451464,China;2.College of Computer and Information Engineering,Henan Normal University,Xinxiang He’nan 453007,China)

Target coverage problem is one of the important problems in wireless sensor network in which each target should be covered by at least one sensor. Therefore,EMNL(Energy-balance-based Maximizing Network Lifetime)algorithm is proposed. In EMNL,All the sensors are organized into different groups called sensor cover in such a way that each cover can monitor all the targets for a fixed duration. By keeping one sensor cover active at a time while others in sleep mode,sensors batteries can be used in efficient way. This helps in prolonging the network lifetime. EMNL algorithm proposes a new energy-efficient heuristic to schedule the sensors in different non-disjoint sensor covers which helps to maximize network lifetime. Finally,we construct simulation and analyze performance of EMNL algorithm. The simulation results show that EMNL algorithm outperforms than other algorithm in term of coverage ratio,and network lifetime.

wireless sensor networks;energy;target coverage;sensor cover;network lifetime

項目來源:河南省教育廳重點科研項目(14B520036)

2017-01-19修改日期:2017-05-24

TP393

:A

:1004-1699(2017)09-1401-04

10.3969/j.issn.1004-1699.2017.09.017