張 蕾

(北京建筑大學(xué)計(jì)算機(jī)系,北京 100044)

?

無(wú)線傳感器網(wǎng)絡(luò)中多重覆蓋算法的研究*

張 蕾*

(北京建筑大學(xué)計(jì)算機(jī)系,北京 100044)

在無(wú)線傳感網(wǎng)器絡(luò)中的硬件資源普遍受限的情況下,形成優(yōu)秀的覆蓋控制策略己成為無(wú)線傳感器網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)課題。本文提出了一種能量有效的多重物理覆蓋算法,在保障覆蓋與連通性的前提下,以能量、覆蓋度為衡量指標(biāo),采用調(diào)度機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)輪換活躍與休眠,有效地提高網(wǎng)絡(luò)生存時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明,與目前典型算法相比,提出的算法在網(wǎng)絡(luò)生存時(shí)間、能量消耗與消亡節(jié)點(diǎn)數(shù)上具有顯著的優(yōu)勢(shì)。

無(wú)線傳感器網(wǎng)絡(luò);覆蓋;物理覆蓋;連通性

近年來(lái),隨著現(xiàn)代傳感器技術(shù)、微機(jī)電技術(shù)、無(wú)線通信技術(shù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)的飛速發(fā)展,由這五大技術(shù)相互融合形成的無(wú)線傳感網(wǎng)絡(luò)技術(shù)得到了較快的發(fā)展。由于具有體積小、價(jià)格低廉以及彼此之間可以在近距離內(nèi)進(jìn)行無(wú)線通信等良好特性,無(wú)線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)在國(guó)防軍事、反恐抗災(zāi)、智能家居、環(huán)境監(jiān)測(cè)、地震與氣候預(yù)測(cè)、交通管理、醫(yī)療衛(wèi)生、制造業(yè)等許多方面都具有廣泛應(yīng)用前景,是國(guó)內(nèi)外的熱點(diǎn)研究領(lǐng)域[1-2]。

要實(shí)現(xiàn)對(duì)分布區(qū)域內(nèi)的各種環(huán)境或?qū)ο筮M(jìn)行感知與監(jiān)測(cè),首要的問(wèn)題就是必須對(duì)監(jiān)控區(qū)域進(jìn)行有效的覆蓋控制[3-5]。覆蓋問(wèn)題是任何類(lèi)型的WSN中的基本問(wèn)題。覆蓋定義為對(duì)于監(jiān)控區(qū)域內(nèi)的任何一點(diǎn),都滿足至少在一個(gè)傳感器節(jié)點(diǎn)的感知范圍之內(nèi),則稱(chēng)該區(qū)域被覆蓋。WSN的覆蓋控制問(wèn)題,可以看作是在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、無(wú)線網(wǎng)絡(luò)通信帶寬、網(wǎng)絡(luò)計(jì)算處理能力等資源普遍受限情況下,通過(guò)網(wǎng)絡(luò)傳感器節(jié)點(diǎn)放置以及路由選擇等手段,最終使WSN的各種資源得到優(yōu)化分配,進(jìn)而使感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量得到改善[6-7]。

針對(duì)節(jié)能覆蓋問(wèn)題,目前的研究大多存在無(wú)法保證期望覆蓋度的問(wèn)題,并且網(wǎng)絡(luò)生存時(shí)間不能顯著提高。本文提出了能量有效的多重物理覆蓋算法,主要考慮二維平面監(jiān)控區(qū)域的連通性、能量有效性與覆蓋度問(wèn)題,適合于對(duì)監(jiān)控區(qū)域可靠性高、覆蓋度高、節(jié)點(diǎn)布置隨機(jī)、網(wǎng)絡(luò)密度變化的應(yīng)用場(chǎng)景,解決可靠度要求高的WSN監(jiān)控問(wèn)題,為密度不均勻WSN節(jié)能多重覆蓋提供有效的途徑。

1 WSN覆蓋問(wèn)題概述

覆蓋問(wèn)題是WSN中的一個(gè)基本問(wèn)題,它能反映網(wǎng)絡(luò)提供的“感知”服務(wù)質(zhì)量。覆蓋問(wèn)題的基本意義就是在傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)能量、無(wú)線通信能力、處理器處理能力等資源受到限制的情況下,通過(guò)優(yōu)化傳感器節(jié)點(diǎn)的部署位置或者優(yōu)化路由選擇等方式,達(dá)到傳感器網(wǎng)絡(luò)的資源優(yōu)化配置,增強(qiáng)網(wǎng)絡(luò)的感知能力、監(jiān)測(cè)能力、傳感能力和通信能力[8]。

給定一個(gè)WSN,覆蓋控制可以這樣概括:傳感器節(jié)點(diǎn)之間不同的協(xié)作方式可以產(chǎn)生對(duì)監(jiān)控區(qū)域不同的管理和感知效果。覆蓋控制和實(shí)際應(yīng)用是密切相關(guān)的,國(guó)內(nèi)外針對(duì)覆蓋控制問(wèn)題已經(jīng)展開(kāi)了大量的研究工作。文獻(xiàn)[9]中,節(jié)點(diǎn)采用自調(diào)度方法階段檢查之前執(zhí)行一個(gè)退避機(jī)制,以有效地控制網(wǎng)絡(luò)“活躍”節(jié)點(diǎn)的密度,但這種方法存在的問(wèn)題是無(wú)法保證期望覆蓋度。為了避免因?yàn)楣?jié)點(diǎn)調(diào)度為休眠狀態(tài)而導(dǎo)致的覆蓋區(qū)域盲點(diǎn)問(wèn)題,文獻(xiàn)[10]提出了一種覆蓋有效的調(diào)度方法CPNS(Coverage Preserving Node Scheduling),其思想是在節(jié)點(diǎn)調(diào)度為休眠狀態(tài)之前,可以通過(guò)逐一詢問(wèn)的方式以確保該區(qū)域能有效覆蓋,但不足之處是這種詢問(wèn)方式的通信開(kāi)銷(xiāo)過(guò)大。盡管當(dāng)前這方面的研究較多,但如何對(duì)現(xiàn)有的聯(lián)合優(yōu)化節(jié)能與多重覆蓋兩類(lèi)節(jié)能覆蓋方式的優(yōu)點(diǎn)進(jìn)行有效的結(jié)合,在保障覆蓋與連通性的前提下,以輪換“活躍”和“休眠”節(jié)點(diǎn)的節(jié)能覆蓋方案,不僅是一種有效且有吸引力的方法,而且具有相當(dāng)?shù)奶魬?zhàn)性。

本文針對(duì)多重物理覆蓋問(wèn)題,提出了一種能量有效的多重覆蓋算法MCA(Multiple Coverage Algorithm),實(shí)現(xiàn)覆蓋區(qū)域的盲點(diǎn)消除,延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。MCA通過(guò)對(duì)節(jié)點(diǎn)所覆蓋的范圍進(jìn)行判斷,實(shí)現(xiàn)節(jié)點(diǎn)的合法性檢測(cè)。當(dāng)節(jié)點(diǎn)與其周?chē)墓?jié)點(diǎn)之間滿足一定的覆蓋關(guān)系以及覆蓋度滿足給定的閾值要求時(shí),將保持節(jié)點(diǎn)活躍,否則關(guān)閉該節(jié)點(diǎn);以感知監(jiān)測(cè)方式和協(xié)作交互的方式避免盲點(diǎn)的出現(xiàn);以能量、覆蓋度為衡量指標(biāo),采用一定的調(diào)度機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)輪換活躍與休眠,最大化網(wǎng)絡(luò)生命周期。

2 能量有效的多重覆蓋算法

2.1 定義

對(duì)于監(jiān)控二維區(qū)域E內(nèi)的一系列傳感器節(jié)點(diǎn)的集合C

(1)

|C|=N

(2)

其中N為節(jié)點(diǎn)數(shù)量,每個(gè)節(jié)點(diǎn)ni(i∈[1,N])的位置Li為

Li=(xi,yi)

(3)

節(jié)點(diǎn)ni(i∈[1,N])的感知范圍為Ri,即對(duì)于任何位置Pi,如果其與ni的距離dPi,ni滿足

dPi,ni≤Ri

(4)

則節(jié)點(diǎn)ni能覆蓋該位置并監(jiān)控其信息。

定義1對(duì)于監(jiān)控二維區(qū)域E內(nèi)的任何位置Pi,如果其位于節(jié)點(diǎn)ni的感知范圍內(nèi),即滿足式(4),則稱(chēng)點(diǎn)Pi被節(jié)點(diǎn)ni覆蓋。

定義2對(duì)于監(jiān)控二維區(qū)域E內(nèi)的任何位置Pi,如果其同時(shí)位于節(jié)點(diǎn)集合Ci感知范圍內(nèi),即有

Ci?C

(5)

則稱(chēng)點(diǎn)Pi被節(jié)點(diǎn)集合Cik重覆蓋,k為覆蓋度。

定義3對(duì)于監(jiān)控二維區(qū)域E內(nèi)的任意位置Pi,Pi的覆蓋度為m,給定正整數(shù)K,通過(guò)有效地調(diào)度傳感器節(jié)點(diǎn)集合C內(nèi)的節(jié)點(diǎn)的休眠,使得位置Pi被節(jié)點(diǎn)集合Ci覆蓋,并滿足

Ci?C,|Ci|=k,m>k≥K

(6)

稱(chēng)其為能量有效的K重覆蓋。

顯然,為了使監(jiān)控區(qū)域E內(nèi)的任意位置達(dá)到能量有效的K重覆蓋,首先必須獲取當(dāng)前節(jié)點(diǎn)的覆蓋度k,如果有k>K,則表明當(dāng)前的覆蓋度高于期望值,可以將部分節(jié)點(diǎn)調(diào)度到休眠狀態(tài),節(jié)省能量,并延長(zhǎng)網(wǎng)絡(luò)的生命期,但是由于節(jié)點(diǎn)的休眠,可能造成實(shí)際的覆蓋度低于期望覆蓋度,因此需要判斷并避免調(diào)度后出現(xiàn)覆蓋盲點(diǎn)的問(wèn)題;否則,如果有k>K,需要將部分休眠節(jié)點(diǎn)喚醒,提高覆蓋度。

定義4重疊覆蓋弧段:對(duì)于任意兩個(gè)感知范圍有重疊的節(jié)點(diǎn)ni與nj,sij表示節(jié)點(diǎn)nj感知范圍內(nèi)的邊界弧段位于節(jié)點(diǎn)ni的感知范圍內(nèi)的部分,即為兩個(gè)節(jié)點(diǎn)的重疊覆蓋弧段。如圖1所示,雙實(shí)線為重疊覆蓋弧段sij。

圖1 2個(gè)節(jié)點(diǎn)的重疊覆蓋弧段

定義5節(jié)點(diǎn)nj的鄰居節(jié)點(diǎn)集合Neib(ni),

Neib(ni)={nj|dni,nj≤ri+rj,nj≠ni,?nj∈Π}

(7)

其中dni,nj表示節(jié)點(diǎn)ni與nj的距離。

2.2 算法描述

為了在保證不同應(yīng)用的所需的覆蓋度的前提下實(shí)現(xiàn)節(jié)能的功能,每個(gè)節(jié)點(diǎn)根據(jù)當(dāng)前的覆蓋情況,周期性自適應(yīng)地調(diào)整自己的狀態(tài),調(diào)度到休眠狀態(tài)。為了實(shí)現(xiàn)期望的覆蓋度,提出的能量有效的K重覆蓋算法MCA包括3個(gè)部分:一是節(jié)點(diǎn)合法性檢測(cè)算法。通過(guò)對(duì)節(jié)點(diǎn)所覆蓋的范圍進(jìn)行判斷,當(dāng)節(jié)點(diǎn)與其周?chē)墓?jié)點(diǎn)之間滿足一定的覆蓋關(guān)系以及覆蓋度滿足給定的閾值要求時(shí),將保持節(jié)點(diǎn)活躍,否則關(guān)閉該節(jié)點(diǎn)。二是覆蓋區(qū)域的盲點(diǎn)消除算法。以一定的感知監(jiān)測(cè)方式和協(xié)作交互的方式避免因?yàn)楣?jié)點(diǎn)的關(guān)閉導(dǎo)致感知區(qū)域盲點(diǎn)的出現(xiàn)。三是休眠節(jié)點(diǎn)激活算法。對(duì)當(dāng)前活動(dòng)節(jié)點(diǎn)覆蓋范圍內(nèi)的其他節(jié)點(diǎn),以能量、覆蓋度為衡量指標(biāo),采用一定的調(diào)度機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)輪換活躍與休眠,最大化網(wǎng)絡(luò)生命周期。

2.2.1 節(jié)點(diǎn)合法性檢測(cè)算法

對(duì)節(jié)點(diǎn)進(jìn)行合法性檢測(cè)的目的是在保證監(jiān)控區(qū)域覆蓋度的前提下,盡可能減少當(dāng)前活躍節(jié)點(diǎn)的數(shù)量,實(shí)現(xiàn)能量節(jié)省的功能。考慮到每個(gè)節(jié)點(diǎn)可能處于一下3種模式之一:休眠、活躍與工作狀態(tài),其中工作狀態(tài)的節(jié)點(diǎn)完成監(jiān)控區(qū)域的數(shù)據(jù)感知與數(shù)據(jù)傳輸?shù)墓δ?其他節(jié)點(diǎn)則準(zhǔn)備從休眠模式切換到活躍模式,實(shí)現(xiàn)對(duì)即將消亡的節(jié)點(diǎn)或有故障節(jié)點(diǎn)的替換。

節(jié)點(diǎn)合法性檢測(cè)算法

輸入:傳感器節(jié)點(diǎn)集合C

輸出:調(diào)度為休眠狀態(tài)的節(jié)點(diǎn)集合Cs

begin對(duì)每個(gè)節(jié)點(diǎn)ni

begin對(duì)ni的每個(gè)sij(j∈[1,N(ni)])

查找由鄰居節(jié)點(diǎn)N(ni)∩N(nj)所覆蓋的節(jié)點(diǎn)nj所有的弧段

用升序?qū)λ谢《芜M(jìn)行排序

根據(jù)弧段截?cái)鄐ij,并計(jì)算弧段sij的覆蓋度k

if(k>K)

將ni加入到集合Cs

end

end

2.2.2 盲點(diǎn)消除算法

由于節(jié)點(diǎn)調(diào)度為休眠狀態(tài)后,可能造成部分覆蓋區(qū)域無(wú)法再有效覆蓋的問(wèn)題,即覆蓋出現(xiàn)盲點(diǎn)(Blind Point)。為了避免盲點(diǎn)的產(chǎn)生,在將節(jié)點(diǎn)調(diào)度為休眠狀態(tài)之前,最安全的方法是向該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)發(fā)送詢問(wèn)消息,然后確定是否執(zhí)行調(diào)度,但該方法的缺陷在于開(kāi)銷(xiāo)太大。而采用隨機(jī)等待的檢測(cè)方法存在無(wú)法保證期望的覆蓋度的問(wèn)題。

盲點(diǎn)消除算法

輸入:傳感器節(jié)點(diǎn)集合C,Cs

begin對(duì)每個(gè)節(jié)點(diǎn)ni

begin對(duì)ni的每個(gè)sij(j∈[1,N(ni)])

ifSubsij-|PC(sij)|≤K

將節(jié)點(diǎn)ni加入候選檢測(cè)列表

向鄰居節(jié)點(diǎn)發(fā)送候選檢測(cè)列表及剩余能量

收到信息的節(jié)點(diǎn)檢測(cè)如果位于候選檢測(cè)列表,則發(fā)送確認(rèn)幀,并保持活躍狀態(tài)

發(fā)送節(jié)點(diǎn)收到所有候選列表的確認(rèn)后,根據(jù)確認(rèn)信息實(shí)現(xiàn)相應(yīng)的調(diào)度,并保證無(wú)盲點(diǎn)。

end

end

2.2.3 休眠節(jié)點(diǎn)激活算法

對(duì)于調(diào)度為休眠的節(jié)點(diǎn),必須采用一定的調(diào)度機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)輪換活躍,并根據(jù)網(wǎng)絡(luò)的狀態(tài),實(shí)現(xiàn)節(jié)點(diǎn)替換或保證覆蓋區(qū)域的多重覆蓋,同時(shí)延長(zhǎng)網(wǎng)絡(luò)生命周期。假設(shè)所有節(jié)點(diǎn)已實(shí)現(xiàn)時(shí)鐘同步功能,一個(gè)周期內(nèi)每個(gè)節(jié)點(diǎn)包括調(diào)度與感知兩個(gè)階段。其中調(diào)度階段包括兩部分功能:主動(dòng)期與被動(dòng)期。

當(dāng)節(jié)點(diǎn)處于活躍狀態(tài)時(shí),在每個(gè)周期內(nèi),主動(dòng)期實(shí)現(xiàn)信標(biāo)幀的發(fā)送。如果節(jié)點(diǎn)處于休眠狀態(tài),則在調(diào)度為休眠狀態(tài)時(shí),在主動(dòng)期其發(fā)送的信標(biāo)信息中包含了休眠時(shí)間長(zhǎng)度,以便讓其他節(jié)點(diǎn)知道該節(jié)點(diǎn)仍為有效節(jié)點(diǎn),且已知其可能調(diào)度為活躍狀態(tài)的時(shí)間。

每個(gè)節(jié)點(diǎn)周期性地醒來(lái)接收信標(biāo)幀,通過(guò)接收到信標(biāo)幀,節(jié)點(diǎn)可以被動(dòng)地檢測(cè)覆蓋度。通過(guò)收到的信標(biāo)幀,可以知道一些節(jié)點(diǎn)在其調(diào)度期內(nèi)已經(jīng)有多次沒(méi)有發(fā)送信標(biāo)幀,或覆蓋度低于預(yù)期值K。或者當(dāng)該節(jié)點(diǎn)的能量不夠時(shí),該節(jié)點(diǎn)可以計(jì)算出實(shí)際的覆蓋度k,并確定是否應(yīng)該喚醒其他節(jié)點(diǎn)由休眠狀態(tài)轉(zhuǎn)換到活躍狀態(tài)。

休眠節(jié)點(diǎn)激活算法

輸入:傳感器節(jié)點(diǎn)集合C,Cs

repeat

do對(duì)每個(gè)活躍節(jié)點(diǎn)ni

begin對(duì)ni的每個(gè)sij(j∈[1,N(ni)])

計(jì)算其覆蓋度k

ifk≥K

++j;

else

對(duì)所有sij中覆蓋度小于K的子弧段求和得S

end

對(duì)節(jié)點(diǎn)ni調(diào)度表中的休眠節(jié)點(diǎn),選擇能覆蓋S最多的節(jié)點(diǎn)作為喚醒節(jié)點(diǎn)

until準(zhǔn)備休眠節(jié)點(diǎn)待覆蓋區(qū)域弧段全覆蓋

3 仿真結(jié)果與分析

本文仿真實(shí)驗(yàn)PC硬件配置為Intel 2.8 GHz CPU,內(nèi)存1 GB,硬盤(pán)250 GB,仿真實(shí)驗(yàn)平臺(tái)是OMNeT 3.0[11-12]。

仿真實(shí)驗(yàn)考慮在300 m×300 m的正方形區(qū)域內(nèi)隨機(jī)布置一定數(shù)量的節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)的感知范圍可變。當(dāng)一個(gè)節(jié)點(diǎn)調(diào)度為休眠狀態(tài)時(shí),將通過(guò)提出的MCA算法的調(diào)度過(guò)程,使其所有鄰居節(jié)點(diǎn)獲知該信息。為了驗(yàn)證提出的MCA方法的有效性,與節(jié)點(diǎn)自調(diào)度覆蓋方法NSS以及覆蓋有效的調(diào)度方法CPNS進(jìn)行性能比較。

3.1 覆蓋度性能

為了對(duì)3種算法的覆蓋度性能進(jìn)行比較,以增加布置節(jié)點(diǎn)數(shù)量的方式增加覆蓋區(qū)域的節(jié)點(diǎn)密度,并定義平均覆蓋度為所有節(jié)點(diǎn)覆蓋度之和與節(jié)點(diǎn)數(shù)量的比值;實(shí)際覆蓋度為所有節(jié)點(diǎn)中覆蓋度的最小值。當(dāng)以隨機(jī)方式對(duì)節(jié)點(diǎn)進(jìn)行布置后,分別計(jì)算出上述兩個(gè)覆蓋度?？疾樵谙嗤那闆r下,分別采用3種覆蓋算法進(jìn)行休眠調(diào)度后,網(wǎng)絡(luò)實(shí)際的覆蓋度。仿真結(jié)果如圖2所示。

圖2 不同覆蓋度時(shí)的生存時(shí)間

圖2所示為不同覆蓋度時(shí),提出的MCA算法的生存時(shí)間。其中節(jié)點(diǎn)的能量從500到3 000個(gè)單元隨機(jī)分布。生存時(shí)間指的是只要當(dāng)任意節(jié)點(diǎn)的覆蓋度無(wú)法滿足給定的期望覆蓋度時(shí)的時(shí)間。

從圖中可以看出覆蓋度越高,生存時(shí)間越短,這與時(shí)間情況是吻合的;而且布置的節(jié)點(diǎn)數(shù)量越多,生存時(shí)間越長(zhǎng)。當(dāng)布置節(jié)點(diǎn)數(shù)量從100增加到300個(gè)時(shí),覆蓋度為2之前的生存時(shí)間從380增加到600,增長(zhǎng)率僅為58%;而覆蓋度為1之前的生存時(shí)間從510增加到820,增長(zhǎng)率為61%。這表明,生存時(shí)間并不會(huì)隨網(wǎng)絡(luò)密度的成倍增加而同比增長(zhǎng)。其原因在于,在部分監(jiān)控區(qū)域,只有一部分的節(jié)點(diǎn)符合調(diào)度到休眠狀態(tài)的條件,而部分關(guān)鍵節(jié)點(diǎn)無(wú)法實(shí)現(xiàn)休眠,因此即便增加覆蓋密度,但并不能保障這些節(jié)點(diǎn)節(jié)省能量,因而導(dǎo)致生存時(shí)間無(wú)法大比例增加。

3.2 生存時(shí)間

圖3所示為布置節(jié)點(diǎn)數(shù)量的增加時(shí)3種算法的生存時(shí)間。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)密度將逐漸加大,3種算法生存時(shí)間都隨之增加。但很顯然,NSS算法生存時(shí)間最短,而且隨著節(jié)點(diǎn)密度的增加,其生存時(shí)間增加的趨勢(shì)并不明顯,僅從100個(gè)節(jié)點(diǎn)時(shí)的580個(gè)增加到300個(gè)節(jié)點(diǎn)時(shí)的980個(gè),即節(jié)點(diǎn)密度增加3倍時(shí),生存時(shí)間僅增加了69%。與CPS算法相比,CPNS算法生存時(shí)間具有明顯的優(yōu)勢(shì),隨著節(jié)點(diǎn)密度的增加,其生存時(shí)間從710增加到1 960,比NSS算法長(zhǎng)1倍。提出的MCA算法的性能最優(yōu),其生存時(shí)間最長(zhǎng),且隨著節(jié)點(diǎn)密度的增加,其增加趨勢(shì)顯著,從800增加到3 570,即節(jié)點(diǎn)密度增加3倍時(shí),整個(gè)網(wǎng)絡(luò)的生存時(shí)間增加了3.4倍。其原因在于,NSS由于其存在無(wú)法保證期望覆蓋度的問(wèn)題,總是使大量的冗余節(jié)點(diǎn)處于活躍狀態(tài),因此導(dǎo)致節(jié)點(diǎn)能量消耗迅速。而CPNS則以逐一詢問(wèn)的方式以確保該區(qū)域能有效覆蓋,雖然可以有效的避免節(jié)點(diǎn)的冗余,但其開(kāi)銷(xiāo)較大。而提出的MCA算法不僅通過(guò)合法性檢測(cè)避免冗余節(jié)點(diǎn)的存在,而且以節(jié)點(diǎn)能量剩余為依據(jù),以能量、覆蓋度為衡量指標(biāo),按優(yōu)先級(jí)進(jìn)行休眠調(diào)度,有力地減少了節(jié)點(diǎn)等能耗,因此顯著地延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

綜上所述,本文提出的MCA算法在覆蓋度和網(wǎng)絡(luò)生存時(shí)間等方面都具有良好的性能。

圖3 不同算法的生存時(shí)間

4 總結(jié)

針對(duì)WSN中兼顧能量效率與物理連通性的兩個(gè)關(guān)鍵因素提出了一種能量有效、保證多重覆蓋度的優(yōu)化MCA算法。詳細(xì)給出了能量有效多重覆蓋的問(wèn)題描述,從節(jié)點(diǎn)合法性檢測(cè)、覆蓋區(qū)域的盲點(diǎn)消除與休眠節(jié)點(diǎn)激活3個(gè)方面詳細(xì)給出了算法描述。仿真實(shí)驗(yàn)結(jié)果及與NSS、CPNS算法的比較表明,提出的MCA算法在網(wǎng)絡(luò)密度變化時(shí),有效地保障了物理覆蓋度,延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。

[1] Huang C F,Tseng Y C.A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks[J].Journal of Internet Technology,2005,6(1):1-8

[2]臧哲,齊建東,張曉武,等.基于智能算法的層次型多鏈WSN路由協(xié)議[J].傳感技術(shù)學(xué)報(bào),2013,26(4):558-563

[3]Ke W C,Liu B H,Tsai M J.Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete.IEEE Transactions on Computers,2007,56(5):710-715

[4]Andrea Bottino,Dipartimento di Automatica e Informatica,Corso Duca degli.A Nearly Optimal Sensor Placement Algorithm for Boundary Coverage[J].Pattern Recognition,2008,41(11):3343-3355

[5]任豐原,黃海寧,林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282-1291.

[6]Pyun Sung-Yeop,Cho Dong-Ho.Power-Saving Scheduling for Multiple-Target Coverage in Wireless Sensor Networks[J].IEEE Communications Letters,2009,13(2):130-132

[7]Zhang Chi,Zhang Yanchao,Fang Yuguang.Localized Algorithms for Coverage Boundary Detection in Wireless Sensor Networks[J].Wireless Networks,2009,15(1):3-20

[8]舒堅(jiān),劉琳嵐,董海星,等.機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)收集中的轉(zhuǎn)發(fā)控制[J].傳感技術(shù)學(xué)報(bào),2012,25(1):129-134

[9]Tian D,Georganas N D.Anode Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks[J].Wireless Communications and Mobile Computing,2003,3(2):271-290

[10]Tian D,Georganas N D.A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks[J].ACM Int’l Workshop on Wireless Sensor Networks and Applications,2002

[11]況曉輝,趙剛,郭勇.網(wǎng)絡(luò)模擬器NS2中仿真功能的問(wèn)題分析及改進(jìn)[J].系統(tǒng)仿真學(xué)報(bào),2009,21(2):427-431.

[12]黃化吉,馮穗力,秦麗蛟.NS網(wǎng)絡(luò)模擬和協(xié)議仿真[J].人民郵電出版社,2010

張蕾(1981-),女,博士,北京建筑大學(xué)計(jì)算機(jī)專(zhuān)業(yè)教師,中國(guó)計(jì)算機(jī)學(xué)會(huì)會(huì)員。主要研究泛在業(yè)務(wù)環(huán)境、智能建筑無(wú)線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)資源管理等。2004.9--2009.7在北京郵電大學(xué)泛網(wǎng)無(wú)線通信教育部重點(diǎn)實(shí)驗(yàn)室(博士生導(dǎo)師:張平教授)攻讀博士學(xué)位。作為年青科研業(yè)務(wù)骨干,主持北京高等學(xué)?！扒嗄暧⒉庞?jì)劃”項(xiàng)目、北京市教委面上項(xiàng)目“智能建筑無(wú)線傳感器網(wǎng)絡(luò)能量均衡及安全路由技術(shù)研究”等。近五年內(nèi),在國(guó)內(nèi)外期刊和國(guó)際學(xué)術(shù)會(huì)議上發(fā)表論文30余篇(其中SCI檢索2篇,EI檢索14篇);參編教材2本,lei.zhang@bucea.edu.cn。

ResearchonMultipleCoverageAlgorithminWirelessSensorNetworks*

ZHANGLei*

(School of Computer Science,Beijing University of Civil Engineering and Architecture,Beijing 100044,China)

Coverage has become one of the hottest topics in this field,for the hardware and energy is always limited in wireless sensor networks(WSNs).This paper presents an efficient power multiple coverage algorithm.By measuring energy and coverage degree,it puts redundant sensor nodes to sleep mode to save energy while maintain the sensing field sufficient coverage degree with precondition of coverage and connective of WSN.Detailed simulation results and compared to existing schemes indicate that the proposed algorithm not only guarantees the network coverage degree,but also prolongs the network lifetime.

wireless sensor networks;coverage;physical coverage;connectivity

項(xiàng)目來(lái)源:北京高等學(xué)校“青年英才計(jì)劃”項(xiàng)目(21271413117);智能建筑無(wú)線傳感器網(wǎng)絡(luò)能量均衡及安全路由技術(shù)研究項(xiàng)目(KM201410016007);計(jì)算中心學(xué)生實(shí)踐創(chuàng)新基地建設(shè)研究項(xiàng)目(J12-16)

2014-03-16修改日期:2014-05-04

10.3969/j.issn.1004-1699.2014.06.018

TP212

:A

:1004-1699(2014)06-0802-05