基于能量均衡的最大化覆蓋目標(biāo)算法*

南書(shū)坡,馮乃勤

(1.河南師范大學(xué)新聯(lián)學(xué)院,鄭州 451464;2.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院,河南 新鄉(xiāng) 453007)

基于能量均衡的最大化覆蓋目標(biāo)算法*

南書(shū)坡1*,馮乃勤2

(1.河南師范大學(xué)新聯(lián)學(xué)院,鄭州 451464;2.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院,河南 新鄉(xiāng) 453007)

目標(biāo)覆蓋問(wèn)題是無(wú)線傳感網(wǎng)絡(luò)WSNs(Wireless sensor networks)最重要的問(wèn)題之一。每個(gè)目標(biāo)至少被一個(gè)傳感節(jié)點(diǎn)覆蓋,為此提出基于能量均衡的最大化覆蓋目標(biāo)EMNL(Energy-balance-based Maximizing Network Lifetime)算法。EMNL算法將所有傳感節(jié)點(diǎn)劃分不同的傳感節(jié)點(diǎn)覆蓋區(qū)SC(Sensor Cover),致使每個(gè)SC能夠維持對(duì)所有目標(biāo)監(jiān)測(cè)一個(gè)固定時(shí)間。通過(guò)有選擇性選擇一個(gè)SC活動(dòng),而其他SC休眠,進(jìn)而提高能量利用率,延長(zhǎng)了網(wǎng)絡(luò)壽命。EMNL算法構(gòu)建了不同不相鄰SC,進(jìn)而最大化網(wǎng)絡(luò)壽命。最后,建立仿真環(huán)境,并進(jìn)行性能仿真。此環(huán)境下的數(shù)據(jù)表明,在EMNL算法有效地?cái)U(kuò)延生存時(shí)間,也提升了覆蓋率。

無(wú)線傳感網(wǎng);能量;目標(biāo)覆蓋;傳感節(jié)點(diǎn)覆蓋區(qū);生存時(shí)間

近期,無(wú)線傳感網(wǎng)絡(luò) WSNs(Wireless Sensor Networks)受到廣泛關(guān)注。WSNs是由大量的微型、能量受限、低功耗的傳感節(jié)點(diǎn)組成。這些傳感節(jié)點(diǎn)具有感測(cè)數(shù)據(jù)、處理以及存儲(chǔ)功能[1]。將這些傳感節(jié)點(diǎn)部署于監(jiān)測(cè)區(qū)域,如森林、戰(zhàn)場(chǎng)。這些部署了傳感節(jié)點(diǎn)的監(jiān)測(cè)區(qū)域稱(chēng)為興趣區(qū)域。在興趣區(qū)域內(nèi),每個(gè)傳感節(jié)點(diǎn)試著感測(cè)環(huán)境數(shù)據(jù),然后再將數(shù)據(jù)傳輸管理中心。

為了實(shí)時(shí)地、無(wú)遺漏地監(jiān)測(cè)環(huán)境,就需要保證傳感節(jié)點(diǎn)對(duì)興趣區(qū)域覆蓋率的最大化。然而,由于傳感節(jié)點(diǎn)存在硬件故障以及能耗問(wèn)題,難以保證所有傳感節(jié)點(diǎn)能正常工作。一旦傳感節(jié)點(diǎn)能耗殆盡,它就無(wú)法工作,也無(wú)法感測(cè)數(shù)據(jù),就出現(xiàn)覆蓋空洞。因此,如何提高興趣區(qū)域的覆蓋率已成WSNs的研究熱點(diǎn)[2-3]。

依據(jù)覆蓋區(qū)域面積的不同,可將覆蓋劃分為點(diǎn)覆蓋和區(qū)域覆蓋。所謂點(diǎn)覆蓋是指由一個(gè)單一的傳感節(jié)點(diǎn)覆蓋的區(qū)域,而區(qū)域覆蓋是由一群傳感節(jié)點(diǎn)共同覆蓋的區(qū)域。然而,實(shí)際上,無(wú)論是點(diǎn)覆蓋還是區(qū)域覆蓋,均需要維持興趣區(qū)域的覆蓋率。

通常,WSNs覆蓋要求是:以有限的能量對(duì)興趣區(qū)域?qū)嵤┍M可能的連續(xù)監(jiān)控。本文著重關(guān)注區(qū)域覆蓋問(wèn)題。將這些需要被覆蓋的區(qū)域也稱(chēng)不目標(biāo)覆蓋區(qū)域,簡(jiǎn)稱(chēng)為目標(biāo)覆蓋[4-5]。換而言之,以目標(biāo)覆蓋為本文的研究對(duì)象,研究的目的在于對(duì)多個(gè)目標(biāo)覆蓋區(qū)域進(jìn)行盡可能長(zhǎng)時(shí)間的監(jiān)控。

為了保存節(jié)點(diǎn)能量,傳感節(jié)點(diǎn)通常具有活動(dòng)和休眠兩種狀態(tài)。在活動(dòng)狀態(tài)時(shí),傳感節(jié)點(diǎn)實(shí)時(shí)監(jiān)控環(huán)境,其將消耗大量能量。而在休眠狀態(tài),傳感節(jié)點(diǎn)處于空閑狀態(tài),不消耗能量。

為了保證所有覆蓋目標(biāo)能夠最大時(shí)間地覆蓋,常采用的方法不是保證所有傳感節(jié)點(diǎn)均在活動(dòng)狀態(tài),而是選擇一部分節(jié)點(diǎn)能夠覆蓋目標(biāo)區(qū)域。這一部分節(jié)點(diǎn)稱(chēng)為傳感節(jié)點(diǎn)覆蓋區(qū)SC(Sensor Cover),它們的活動(dòng)時(shí)間稱(chēng)為生存時(shí)間。因此,覆蓋目標(biāo)問(wèn)題是就是保證這些SC在固定時(shí)間內(nèi)工作,進(jìn)而監(jiān)控興趣區(qū)域。所有SC的生存時(shí)間就是網(wǎng)絡(luò)壽命。

目前,針對(duì)目標(biāo)覆蓋問(wèn)題已進(jìn)行了大量的研究工作[6-7]。文獻(xiàn)[8]提出高能效啟發(fā)式算法HEEH(High-Energy-Efficient Heuristic)。HEEH算法僅選擇能量最多的傳感節(jié)點(diǎn)構(gòu)成不相鄰的覆蓋集,并最小化SC集,進(jìn)而消除覆蓋冗余問(wèn)題。文獻(xiàn)[9-10]也提出利用整數(shù)線性規(guī)劃ILP(Integer Linear Programming)構(gòu)建SC集。此外,文獻(xiàn)[11]也提出基于權(quán)重的啟發(fā)式算法WH(Weight-based Heuristic)。WH算法先選擇剩余能量最高的節(jié)點(diǎn)構(gòu)建SC,然后再優(yōu)化。

為此,本文針對(duì)WSNs的目標(biāo)覆蓋問(wèn)題,提出基于能量均衡的最大化覆蓋目標(biāo)EMNL(Energy-Balance-Based Maximizing Network Lifetime)算法。EMNL算法先將傳感節(jié)點(diǎn)劃分不同的傳感節(jié)點(diǎn)覆蓋區(qū)SC(Sensor Cover),致使每個(gè)SC覆蓋所有目標(biāo)一段時(shí)間,進(jìn)而平衡網(wǎng)絡(luò)能耗,提高網(wǎng)絡(luò)壽命。實(shí)驗(yàn)數(shù)據(jù)表明,提出的EMNL算法有效地延長(zhǎng)網(wǎng)絡(luò)壽命,并增加覆蓋率。

1 約束條件

假定在M×M區(qū)域內(nèi)隨機(jī)分布了n個(gè)覆蓋目標(biāo)T={t1,t2,…,tn}。為最大時(shí)間地監(jiān)測(cè)這些覆蓋目標(biāo),在整個(gè)M×M區(qū)域內(nèi)隨機(jī)部署m個(gè)傳感節(jié)點(diǎn),即S={s1,s2,…,sm}。其中,每個(gè)傳感節(jié)點(diǎn)的傳輸半徑為Rs。傳感節(jié)點(diǎn)si的初始能量為bi。

此外,每個(gè)傳感節(jié)點(diǎn)存在活動(dòng)和休眠兩種狀態(tài),它們可彼此切換。在活動(dòng)狀態(tài),傳感節(jié)點(diǎn)感測(cè)目標(biāo)覆蓋區(qū)域內(nèi)的信息,而在休眠狀態(tài),傳感節(jié)點(diǎn)不感測(cè)信息,進(jìn)而保存能量。

此外,本文引用的標(biāo)識(shí)符如表1所示。

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

(1)

定義2關(guān)鍵目標(biāo)集CTS(Critical Target Set) 在整個(gè)覆蓋目標(biāo)集T內(nèi),若一覆蓋目標(biāo)內(nèi)所有節(jié)點(diǎn)的能量和是最小的,則該覆蓋目標(biāo)稱(chēng)為CTS,定義如式(2)所示:

(2)

定義3關(guān)鍵節(jié)點(diǎn)CS(Critical Sensor) 若節(jié)點(diǎn)至少覆蓋了一個(gè)CTS,則該傳感節(jié)點(diǎn)就稱(chēng)為CS。

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

定義5傳感節(jié)點(diǎn)覆蓋區(qū)SC的生存時(shí)間Ck的生存時(shí)間等于Ck內(nèi)節(jié)點(diǎn)的最小電池供電時(shí)間,定義如式(3)所示:

(3)

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

(4)

式中:|C|為網(wǎng)絡(luò)內(nèi)SC的個(gè)數(shù)。

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

t1t2t3

(5)

依據(jù)R4×3內(nèi)的元素可知,傳感節(jié)點(diǎn)s1覆蓋t2、t3,即s1={t2,t3}。類(lèi)似地,s2={t1,t2}、s3={t1,t3}、s4={t1,t3}。依據(jù)定義2可知,覆蓋目標(biāo)t2為CTS,因?yàn)橹挥衪2只被兩個(gè)節(jié)點(diǎn)覆蓋,它的生存時(shí)間最低僅為2,相應(yīng)地,傳感節(jié)點(diǎn)s1、s2為CS節(jié)點(diǎn)。

2 EMNL算法

EMNL算法就是先計(jì)算CTS以及SC,然后再用它們構(gòu)建SC。具體而言,當(dāng)明確了CTS,就計(jì)算覆蓋所有CTS的最小數(shù)的SC,而對(duì)于剩余未覆蓋目標(biāo),就從剩余的傳感節(jié)點(diǎn)集中尋找剩余能量最大的傳感節(jié)點(diǎn),然后再?gòu)倪@些節(jié)點(diǎn)中選擇具有最大目標(biāo)覆蓋的節(jié)點(diǎn)。EMNL協(xié)議的目的就是選擇傳感節(jié)點(diǎn),致使所有目標(biāo)集都被覆蓋。

首先,利用定義2、定義3計(jì)算CTS、SC。這兩個(gè)集分別表示為T(mén)critical、Scritical。然后構(gòu)建Ck。具體構(gòu)建步驟如下:

(6)

構(gòu)建Ck完整過(guò)程的偽代碼如圖1所示。

圖1 算法1的偽代碼

算法1中UB表示SC數(shù)。網(wǎng)絡(luò)內(nèi)m個(gè)傳感節(jié)點(diǎn)它們的能量分別為{b1,b2,…,bm}和n個(gè)覆蓋目標(biāo){t1,t2,…,tm}。而覆蓋目標(biāo)tj的最大覆蓋時(shí)間為Uj,定義如式(7)所示:

(7)

現(xiàn)在,取網(wǎng)絡(luò)壽命的上限,因此,UB的定義如式(8)所示:

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

(8)

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

圖2 算法2的偽代碼

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

3 性能分析

3.1 仿真參數(shù)

本小節(jié)對(duì)EMNL算法進(jìn)行仿真,分析EMNL算法的性能[12]?？紤]200 m×200 m的網(wǎng)絡(luò)區(qū)域,仿真參數(shù)表1所示。在性能分析過(guò)程中,選擇平均SC規(guī)模、SC的生命周期、剩余能量、網(wǎng)絡(luò)覆蓋率作為性能指標(biāo)。同是選擇HEEH[8]和WH[11]兩個(gè)算法作為參照。每次仿真獨(dú)立重復(fù)100次,取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù)。

表1 仿真參數(shù)

3.2 數(shù)值分析

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

圖3 SC的生存時(shí)間

其次,分析了網(wǎng)絡(luò)的剩余能量,數(shù)值結(jié)果如圖4所示。圖4的數(shù)據(jù)來(lái)自于仿真了7 200 s后網(wǎng)絡(luò)的剩余能量。依圖4可知,網(wǎng)絡(luò)剩余能量隨節(jié)點(diǎn)數(shù)的增加而呈下降趨勢(shì)。與HEEH和WH算法相比,EMNL算法的剩余能量最多。原因在于EMNL算法能夠有效地利用能量,平衡了能耗。

圖4 剩余能量

圖5 覆蓋率

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

4 總結(jié)

本文針對(duì)無(wú)線傳感網(wǎng)絡(luò)的覆蓋問(wèn)題,提出EMNL算法。EMNL算法從能量平衡角度,將傳感節(jié)點(diǎn)劃分不同的SC。在某一時(shí)刻,所有目標(biāo)只由一個(gè)SC覆蓋,而其他SC休眠,進(jìn)而保存網(wǎng)絡(luò)能量,提高網(wǎng)絡(luò)壽命。實(shí)驗(yàn)數(shù)據(jù)也證實(shí),與HEEH和WH算法相比,EMNL算法有效地降低能耗,提高了網(wǎng)絡(luò)壽命。

[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] 付永生,李善平,周波. 無(wú)線傳感網(wǎng)絡(luò)中能量均衡的連通支配集算法[J]. 傳感技術(shù)學(xué)報(bào),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] 張靜,賈春福. 無(wú)線傳感器網(wǎng)絡(luò)基于權(quán)值的極小支配集路由算法[J]. 傳感技術(shù)學(xué)報(bào),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] 陳勤,朱韜,張旻. 基于域的分布式最小連通支配集啟發(fā)式算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用,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.

南書(shū)坡(1980-),男,漢,河南唐河人,碩士,講師,研究方向?yàn)閿?shù)據(jù)挖掘,人工智能。

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

項(xiàng)目來(lái)源:河南省教育廳重點(diǎn)科研項(xiàng)目(14B520036)

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

TP393

:A

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

10.3969/j.issn.1004-1699.2017.09.017