聯(lián)合感知無線傳感網(wǎng)的優(yōu)化覆蓋控制算法

孫澤宇,李傳鋒,邢蕭飛,曹仰杰

(1.洛陽理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,471023,河南洛陽;2.西安交通大學(xué)電子與信息工程學(xué)院,

?

聯(lián)合感知無線傳感網(wǎng)的優(yōu)化覆蓋控制算法

孫澤宇1,2,李傳鋒1,3,邢蕭飛4,曹仰杰5

(1.洛陽理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院,471023,河南洛陽;2.西安交通大學(xué)電子與信息工程學(xué)院,

710049,西安;3.英國貝爾法斯特女王大學(xué)電氣工程與計(jì)算機(jī)學(xué)院,BT95AH,英國貝爾法斯特;4.廣州

大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院,510006,廣州;5.鄭州大學(xué)軟件與應(yīng)用科技學(xué)院,450001,鄭州)

針對(duì)無線傳感器網(wǎng)絡(luò)覆蓋過程中出現(xiàn)大量冗余節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)能量快速消耗的問題,提出了一種聯(lián)合感知優(yōu)化覆蓋控制算法。該算法給出了三節(jié)點(diǎn)聯(lián)合覆蓋時(shí)最大無縫覆蓋率的求解過程。通過概率相關(guān)知識(shí),驗(yàn)證了在監(jiān)測區(qū)域內(nèi)傳感器節(jié)點(diǎn)覆蓋時(shí)傳感器節(jié)點(diǎn)覆蓋質(zhì)量期望值求解方法,以及在與鄰居節(jié)點(diǎn)進(jìn)行覆蓋對(duì)比時(shí)的覆蓋率判定方法;當(dāng)存在冗余覆蓋時(shí),引入比例系數(shù)完成對(duì)任意傳感器節(jié)點(diǎn)處于冗余節(jié)點(diǎn)覆蓋時(shí)的冗余覆蓋度的計(jì)算過程。仿真實(shí)驗(yàn)結(jié)果表明:該算法與其他算法在覆蓋質(zhì)量和網(wǎng)絡(luò)生存周期等方面進(jìn)行對(duì)比,其性能指標(biāo)分別提升了11.02%和13.27%;該算法不僅可以提高網(wǎng)絡(luò)覆蓋質(zhì)量,而且可以有效地抑制節(jié)點(diǎn)能量的快速消耗,從而延長了網(wǎng)絡(luò)生存周期。

無線傳感器網(wǎng)絡(luò);覆蓋質(zhì)量;節(jié)點(diǎn)聯(lián)合;網(wǎng)絡(luò)生存周期

無線傳感器網(wǎng)絡(luò)是由成千上萬個(gè)傳感器節(jié)點(diǎn)通過自組織多跳方式連接的一個(gè)新型網(wǎng)絡(luò)系統(tǒng),可完成對(duì)信息世界與物理世界的有機(jī)統(tǒng)一,實(shí)現(xiàn)數(shù)據(jù)采集、計(jì)算、通信以及存儲(chǔ)等操作[1-2]。隨著信息科技的快速進(jìn)步,無線傳感器網(wǎng)絡(luò)應(yīng)用范圍主要涉及軍事國防、環(huán)境監(jiān)測、災(zāi)難救援、智能家居、衛(wèi)生醫(yī)療、農(nóng)業(yè)生產(chǎn)和交通運(yùn)輸?shù)雀鞣N工程領(lǐng)域[3-4]。

近幾年,國內(nèi)外一些專家學(xué)者對(duì)無線傳感器網(wǎng)絡(luò)的覆蓋問題進(jìn)行了深入而細(xì)致的研究。文獻(xiàn)[5]提出一種增強(qiáng)型覆蓋控制算法(ECCA),給出了對(duì)監(jiān)測區(qū)域進(jìn)行覆蓋時(shí)覆蓋期望值的求解過程,驗(yàn)證了隨機(jī)變量相互獨(dú)立時(shí)各參數(shù)之間的比例函數(shù)關(guān)系,通過對(duì)可調(diào)參數(shù)取值的變化達(dá)到對(duì)整個(gè)監(jiān)測區(qū)域的有效覆蓋。文獻(xiàn)[6]提出了一種能量有效的目標(biāo)覆蓋算法(ETCA)。該算法利用非線性規(guī)劃原理建立網(wǎng)絡(luò)集群,并對(duì)任意集群節(jié)點(diǎn)進(jìn)行能量評(píng)估和計(jì)算,選擇出滿足覆蓋條件的傳感器節(jié)點(diǎn)建立最優(yōu)化覆蓋集,最終在達(dá)到最優(yōu)覆蓋效果的同時(shí)延長網(wǎng)絡(luò)生存周期。文獻(xiàn)[7]提出了一種基于事件概率驅(qū)動(dòng)機(jī)制的覆蓋算法(EPDM)。該算法首先建立傳感器節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)覆蓋網(wǎng)絡(luò)模型,然后通過概率計(jì)算得到傳感器節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間覆蓋比值,最后利用節(jié)點(diǎn)調(diào)度算法完成節(jié)點(diǎn)之間狀態(tài)轉(zhuǎn)換過程,最終達(dá)到延長網(wǎng)絡(luò)生存周期的目的。文獻(xiàn)[8]提出一種基于感知模型的連通覆蓋調(diào)度控制算法(SCA)。該算法利用網(wǎng)絡(luò)連通性建立感知模型,通過節(jié)點(diǎn)性能參數(shù)關(guān)系計(jì)算出選取最少工作節(jié)點(diǎn)集合保證最大覆蓋質(zhì)量,從而達(dá)到最優(yōu)覆蓋效果。

在傳感器節(jié)點(diǎn)隨機(jī)部署[9]過程中,由于事先無法預(yù)知傳感器節(jié)點(diǎn)的具體位置,使得在某監(jiān)測區(qū)域內(nèi)或某個(gè)監(jiān)測點(diǎn)上存在大量傳感器節(jié)點(diǎn)。由于大量傳感器節(jié)點(diǎn)以高密度形式聚集在一起,產(chǎn)生大量的冗余信息,使得通信鏈路出現(xiàn)擁塞現(xiàn)象,抑制了網(wǎng)絡(luò)的可擴(kuò)展性,降低了網(wǎng)絡(luò)服務(wù)質(zhì)量,縮短了整個(gè)網(wǎng)絡(luò)生存周期;同時(shí),對(duì)傳感器節(jié)點(diǎn)而言,無法向匯聚節(jié)點(diǎn)提供正確的數(shù)據(jù)信息,從而導(dǎo)致匯聚節(jié)點(diǎn)所收集的數(shù)據(jù)信息存在著較大偏差和不確定性。

針對(duì)上述問題,本文提出了一種聯(lián)合感知優(yōu)化覆蓋控制算法(optimal coverage control algorithm with joint sensing, OCCAJS),借助于幾何理論相關(guān)知識(shí),給出三節(jié)點(diǎn)聯(lián)合時(shí)最大覆蓋面積的求解方法;在此方法的基礎(chǔ)上,利用概率相關(guān)知識(shí)對(duì)傳感器節(jié)點(diǎn)覆蓋期望值進(jìn)行驗(yàn)證,給出最少傳感器節(jié)點(diǎn)數(shù)的求解方法,同時(shí)也給出了任意傳感器節(jié)點(diǎn)處于冗余節(jié)點(diǎn)覆蓋時(shí)的冗余覆蓋度判定方法。本文主要貢獻(xiàn)體現(xiàn)在以下3點(diǎn):①在對(duì)監(jiān)測區(qū)域進(jìn)行有效覆蓋時(shí),給出節(jié)點(diǎn)聯(lián)合時(shí)三節(jié)點(diǎn)最大無縫覆蓋率的求解方法,計(jì)算了三節(jié)點(diǎn)聯(lián)合覆蓋時(shí)有效最大覆蓋率;②在監(jiān)測區(qū)域內(nèi),隨機(jī)選擇k個(gè)節(jié)點(diǎn)作為研究對(duì)象,以概率理論作為研究基礎(chǔ),通過傳感器節(jié)點(diǎn)感知半徑的特性,給出了k個(gè)節(jié)點(diǎn)聯(lián)合覆蓋時(shí)覆蓋質(zhì)量期望值的求解方法;③通過限定可調(diào)參數(shù)λ的取值范圍,給出任意節(jié)點(diǎn)處于冗余節(jié)點(diǎn)覆蓋下的冗余覆蓋度判定方法。通過仿真實(shí)驗(yàn)與其他算法進(jìn)行對(duì)比,驗(yàn)證了本文OCCAJS算法的有效性和可行性。

1 預(yù)備知識(shí)

所有傳感器節(jié)點(diǎn)隨機(jī)部署在一個(gè)二維監(jiān)測區(qū)域內(nèi),并具有如下性質(zhì):①初始時(shí)刻,所有傳感器節(jié)點(diǎn)均呈現(xiàn)圓盤形,且感知半徑相同,能量相等;②所有傳感器節(jié)點(diǎn)感知半徑服從正態(tài)分布,并遠(yuǎn)小于監(jiān)測區(qū)域的長度,忽略邊界效應(yīng)[10];③通信半徑大于或等于2倍感知半徑,并保持所有傳感器節(jié)點(diǎn)連通;④所有傳感器節(jié)點(diǎn)之間彼此相互獨(dú)立,各自地位相同;⑤所有工作的傳感器節(jié)點(diǎn)均與時(shí)鐘同步,且保證在監(jiān)測區(qū)域內(nèi)節(jié)點(diǎn)密度足夠大[11]。

定義1 有效覆蓋面為所有感知鄰居節(jié)點(diǎn)覆蓋面積與監(jiān)測區(qū)域的交集

(1)

式中:Se為監(jiān)測區(qū)域內(nèi)的有效覆蓋面積;S為監(jiān)測區(qū)域面積;si為任意節(jié)點(diǎn)覆蓋面積。

定義2 網(wǎng)絡(luò)覆蓋率為在監(jiān)測區(qū)域內(nèi),傳感器節(jié)點(diǎn)的有效覆蓋面積與監(jiān)測區(qū)域面積的比值,表達(dá)式為

(2)

網(wǎng)絡(luò)覆蓋率的物理意義主要體現(xiàn)在覆蓋率越大,覆蓋效果越好。

定義3 有效覆蓋面積率為傳感器節(jié)點(diǎn)有效覆蓋面積與傳感器節(jié)點(diǎn)區(qū)域面積的比值

(3)

定理1 三節(jié)點(diǎn)進(jìn)行聯(lián)合無縫對(duì)接時(shí),最大覆蓋面積為Smax=(4π+33/2)r2/2,最大有效覆蓋面積率為94.24%,其中r為傳感器節(jié)點(diǎn)感知半徑,Smax是最大覆蓋面積。

證明 如圖1所示,設(shè)陰影面積為S1,扇形OACB面積為S2,三角形面積為S3。因?yàn)樗蟾采w面積最大,所以3個(gè)傳感器節(jié)點(diǎn)相交于一點(diǎn)B,由對(duì)稱性及圓心角所對(duì)同弦定理可知,陰影中心弦是圓O內(nèi)接正六邊形的一條邊長,即扇形OACB為圓O的1/6,弦所對(duì)的圓心角為π/3,故ΔOAB為等邊三角形,OA=AB=BO=r。

S1=2(S2-S1)=(2π-33/2)r2/6

(4)

Smax=3(πr2-S1)=3((4πr2-33/2r2)/6)=

(4π+33/2)r2/2

(5)

有效覆蓋面積率為

Pe=Smax/(3πr2)=(4π+33/2)/6π=94.24%

(6)

圖1 三節(jié)點(diǎn)無縫對(duì)接示意圖

2 覆蓋質(zhì)量與算法分析

2.1 覆蓋質(zhì)量期望值

在監(jiān)測區(qū)域內(nèi),傳感器節(jié)點(diǎn)要完成對(duì)目標(biāo)節(jié)點(diǎn)數(shù)據(jù)采集、數(shù)據(jù)通信等操作,其行為特征主要體現(xiàn)在隨機(jī)拋擲傳感器節(jié)點(diǎn)分布密度問題,分布密度的優(yōu)劣直接影響覆蓋質(zhì)量,一個(gè)穩(wěn)定網(wǎng)絡(luò)不僅要求有合理的網(wǎng)絡(luò)服務(wù)體系,而且還要具備可行的網(wǎng)絡(luò)覆蓋體系。在滿足一定覆蓋率的前提下,要完成對(duì)監(jiān)測區(qū)域有效覆蓋,就要計(jì)算該監(jiān)測區(qū)域的覆蓋期望值。

證明 根據(jù)定義2可知,任意一個(gè)傳感器節(jié)點(diǎn)在監(jiān)測區(qū)域內(nèi)的覆蓋率為

P1=πr2/area(S)

(7)

由于傳感器節(jié)點(diǎn)感知半徑服從于正態(tài)分布(R0,σ2),R0為均值,σ2為方差,在監(jiān)測區(qū)域內(nèi)任意目標(biāo)節(jié)點(diǎn)被傳感器節(jié)點(diǎn)所覆蓋的覆蓋率為

(8)

令x=(r-R0)/σ,則

R0)2exp(-x2/2)dx

(9)

經(jīng)計(jì)算得

P2=(π/2)1/2(1/area(S))(-σ2xexp)-

(10)

化簡式(10)可得

(11)

由于隨機(jī)分布在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點(diǎn)之間相互獨(dú)立,因此,在監(jiān)測區(qū)域內(nèi)任意目標(biāo)節(jié)點(diǎn)被k個(gè)傳感器節(jié)點(diǎn)所覆蓋的覆蓋期望值為

(12)

證明 設(shè)n為部署在監(jiān)測區(qū)域內(nèi)的最少傳感器節(jié)點(diǎn)數(shù),根據(jù)定理2可知,目標(biāo)節(jié)點(diǎn)被任意一個(gè)傳感器節(jié)點(diǎn)所覆蓋的覆蓋期望值不大于節(jié)點(diǎn)聯(lián)合時(shí)的覆蓋期望值,即

(13)

式(13)兩邊取對(duì)數(shù)可得

(14)

n≤ln(1-πr2/area(S))/ln(1-

(15)

因此,完成對(duì)監(jiān)測區(qū)域有效覆蓋時(shí),所需傳感器節(jié)點(diǎn)數(shù)最小值應(yīng)為

2.2 冗余覆蓋

初始時(shí)刻的傳感器節(jié)點(diǎn)部署是以隨機(jī)形態(tài)、高密度部署方式拋擲在監(jiān)測區(qū)域內(nèi)[12]。由于隨機(jī)性的存在,會(huì)導(dǎo)致監(jiān)測區(qū)域某處產(chǎn)生大量的冗余節(jié)點(diǎn),而大量冗余節(jié)點(diǎn)的存在會(huì)降低網(wǎng)絡(luò)擴(kuò)展性,產(chǎn)生網(wǎng)絡(luò)擁塞、過快消耗網(wǎng)絡(luò)能量等一系列問題。目前,解決上述問題主要有兩種算法,分別是集中優(yōu)化算法和分布式優(yōu)化算法。集中式優(yōu)化覆蓋算法主要應(yīng)用于中小型規(guī)模網(wǎng)絡(luò)體系,其工作原理是,傳感器節(jié)點(diǎn)計(jì)算出本身地理位置信息,對(duì)計(jì)算后的位置信息進(jìn)行融合并上傳至匯聚節(jié)點(diǎn);匯聚節(jié)點(diǎn)對(duì)收集的信息進(jìn)行分析后,關(guān)閉或休眠冗余節(jié)點(diǎn)以達(dá)到抑制網(wǎng)絡(luò)能量消耗。分布式優(yōu)化算法主要應(yīng)用于大規(guī)模部署傳感器網(wǎng)絡(luò),其工作原理是,傳感器節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)交互信息后,通過某種算法求解出各自節(jié)點(diǎn)的冗余度,當(dāng)冗余度超過事先設(shè)定的閾值時(shí),則關(guān)閉或休眠冗余度較高的節(jié)點(diǎn),以達(dá)到節(jié)省網(wǎng)絡(luò)能量的目的。與集中式優(yōu)化算法相比,分布式優(yōu)化算法應(yīng)用范圍更廣,適應(yīng)范圍更大。

定義4 冗余覆蓋節(jié)點(diǎn)。任意兩個(gè)傳感器節(jié)點(diǎn)si、sj互為鄰居節(jié)點(diǎn),兩節(jié)點(diǎn)之間的歐氏距離小于冗余臨界閾值I時(shí),稱為冗余覆蓋節(jié)點(diǎn)。

定義5 冗余覆蓋度。傳感器節(jié)點(diǎn)si與鄰居節(jié)點(diǎn)互為冗余節(jié)點(diǎn)時(shí),傳感器節(jié)點(diǎn)si的感知面積與其鄰居節(jié)點(diǎn)感知面積的比值,稱為冗余覆蓋度。

定理3 對(duì)于隸屬于任意一個(gè)傳感器節(jié)點(diǎn)si的n個(gè)冗余節(jié)點(diǎn),其冗余覆蓋度為

P(n)=1-{1-1/π[π/4-λ(4-λ2)1/2/8+

λ2/2arccos(λ/2)-λ3(4-λ2)1/2/16]}n

證明 以圖2為例加以證明。由假設(shè)條件可知,傳感器節(jié)點(diǎn)均為同構(gòu)節(jié)點(diǎn),通信半徑R與感知半徑r的比例關(guān)系為R=λr,λ是比例系數(shù),設(shè)∠BCE=α,點(diǎn)B與點(diǎn)C之間的距離l為隨機(jī)變量,由概率密度函數(shù)可知

fl(x)=2x/λ2r2, 0≤x≤λr

(16)

兩圓盤相交區(qū)域的面積S4為

S4=(2α-sin2α)r2

(17)

令BC之間距離l=2rcosα,dl=2rsinαdα,其中α∈[arccos(λ/2),π/2],代入概率密度公式,化簡可得

1/π[π/4-λ(4-λ2)1/2/8+λ2/2arccos(λ/2)-

λ3(4-λ2)1/2/16]r2

(18)

由式(18)可知,對(duì)于任意冗余節(jié)點(diǎn)的冗余覆蓋率可表示為

P4=P3/πr2=1/π2[π/4-λ(4-λ2)1/2/8+

λ2/2arccos(λ/2)-λ3(4-λ2)1/2/16]

(19)

當(dāng)n個(gè)冗余節(jié)點(diǎn)進(jìn)行有效覆蓋時(shí),其冗余覆蓋率為

P(n)=1-{1-1/π[π/4-λ(4-λ2)1/2/8+

λ2/2arccos(λ/2)-λ3(4-λ2)1/2/16]}n

(20)

圖2 節(jié)點(diǎn)覆蓋關(guān)聯(lián)示意圖

2.3 OCCAJS算法實(shí)現(xiàn)

定義6 圖連通度。給定無向連通圖G,G=(V,E),傳感器節(jié)點(diǎn)si∈V,其節(jié)點(diǎn)的連通度定義為鄰居節(jié)點(diǎn)數(shù);G連通度指V中節(jié)點(diǎn)連通度最小值。

在傳感器節(jié)點(diǎn)冗余方面,本文借助于分簇原理對(duì)管理員節(jié)點(diǎn)和成員節(jié)點(diǎn)進(jìn)行分類管理。首先建立傳感器節(jié)點(diǎn)冗余連通圖,即節(jié)點(diǎn)集合中所有節(jié)點(diǎn)通過某種定位算法(例如和質(zhì)心定位,RSSI測距定位方法)計(jì)算出本身與鄰居節(jié)點(diǎn)的冗余信息,并將該數(shù)據(jù)信息在本簇內(nèi)進(jìn)行融合,通過通信鏈路發(fā)送給匯聚節(jié)點(diǎn),當(dāng)匯聚節(jié)點(diǎn)接收到該冗余信息后,根據(jù)計(jì)算結(jié)果構(gòu)造冗余關(guān)系連通圖G;當(dāng)傳感器節(jié)點(diǎn)數(shù)增加時(shí),其冗余度也隨之增加。在連通圖G中,當(dāng)傳感器節(jié)點(diǎn)冗余度超過事先設(shè)定的閾值時(shí),將該節(jié)點(diǎn)狀態(tài)轉(zhuǎn)為休眠。在同一時(shí)刻,連通圖G中存在多個(gè)(n>2)高冗余度節(jié)點(diǎn)時(shí),則以節(jié)點(diǎn)能量作為選擇條件,利用排序算法選擇最高能量節(jié)點(diǎn)作為休眠節(jié)點(diǎn),同時(shí)在連通圖G中刪除該節(jié)點(diǎn)以及該節(jié)點(diǎn)所對(duì)應(yīng)的鄰居節(jié)點(diǎn),然后通過迭代算法,逐一找出下一個(gè)高能量節(jié)點(diǎn),直到連通圖G所有傳感器節(jié)點(diǎn)的冗余度均小于閾值為止。在傳感器節(jié)點(diǎn)能耗方面,首先由成員節(jié)點(diǎn)發(fā)送一個(gè)“inf_coverage”信息至匯聚節(jié)點(diǎn),其中“inf_coverage”信息中包含了節(jié)點(diǎn)的位置信息、節(jié)點(diǎn)的ID信息、能量信息等。經(jīng)過一個(gè)或幾個(gè)周期,匯聚節(jié)點(diǎn)收到各個(gè)傳感器節(jié)點(diǎn)發(fā)送來的信息后對(duì)信息進(jìn)行計(jì)算,將節(jié)點(diǎn)能量由高至低依次存儲(chǔ)在鏈表CL中,排序靠前的節(jié)點(diǎn)擁有權(quán)值較高的覆蓋能力。管理節(jié)點(diǎn)依據(jù)目標(biāo)節(jié)點(diǎn)的位置信息在鏈表中尋找符合覆蓋條件的傳感器節(jié)點(diǎn),并發(fā)送一個(gè)“inf_notice”信息啟動(dòng)該傳感器節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行有效覆蓋,其余節(jié)點(diǎn)處于休眠狀態(tài),以達(dá)到節(jié)省網(wǎng)絡(luò)能量開銷的目的。

3 體系評(píng)估

為了進(jìn)一步驗(yàn)證本文算法的有效性和可行性,以Matlab 7.0作為仿真平臺(tái),采用本文算法與文獻(xiàn)[6-8]算法對(duì)網(wǎng)絡(luò)覆蓋率、休眠冗余節(jié)點(diǎn)動(dòng)態(tài)變化以及網(wǎng)絡(luò)生存周期等進(jìn)行兩組仿真實(shí)驗(yàn)對(duì)比。通過改變節(jié)點(diǎn)自身狀態(tài)達(dá)到優(yōu)化節(jié)點(diǎn)部署形態(tài);通過改變傳感器節(jié)點(diǎn)數(shù)達(dá)到對(duì)監(jiān)測區(qū)域的有效覆蓋;在冗余覆蓋過程中,完成了在特定參數(shù)作用下的冗余節(jié)點(diǎn)數(shù)與冗余覆蓋率之間的對(duì)比;最后,在網(wǎng)絡(luò)生存周期與算法運(yùn)行時(shí)間上與文獻(xiàn)[6]ETCA算法對(duì)比,其特性參數(shù)平均高于ETCA算法13.27%,驗(yàn)證了本文算法的穩(wěn)定性。每組實(shí)驗(yàn)數(shù)據(jù)均取50次仿真數(shù)據(jù)的平均值。

實(shí)驗(yàn)1 采用不同規(guī)模仿真平臺(tái),將本文算法與文獻(xiàn)[7-8]算法在覆蓋率和冗余節(jié)點(diǎn)數(shù)上進(jìn)行對(duì)比,結(jié)果如圖3～8所示。

圖3 100 m×100 m區(qū)域傳感器節(jié)點(diǎn)數(shù)與工作節(jié)點(diǎn)數(shù)關(guān)系對(duì)比

圖4 200 m×200 m區(qū)域網(wǎng)絡(luò)覆蓋率變化對(duì)比

圖5 300 m×300 m區(qū)域不同覆蓋率下OCCAJS算法的傳感器節(jié)點(diǎn)數(shù)與工作節(jié)點(diǎn)數(shù)的關(guān)系

圖6 300 m×300 m區(qū)域冗余節(jié)點(diǎn)數(shù)與覆蓋率關(guān)系對(duì)比

圖7 300 m×300 m區(qū)域休眠冗余節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)覆蓋率關(guān)系對(duì)比

圖8 300 m×300 m區(qū)域冗余節(jié)點(diǎn)數(shù)與休眠節(jié)點(diǎn)數(shù)關(guān)系對(duì)比

圖3～8分別給出了在不同網(wǎng)絡(luò)規(guī)模、不同參數(shù)作用下的覆蓋率變化曲線以及冗余節(jié)點(diǎn)數(shù)與覆蓋率變化曲線示意圖。圖3給出了在100 m×100 m仿真區(qū)域,本文OCCAJS算法與SCA算法[8]、EPDM算法[7]在傳感器節(jié)點(diǎn)數(shù)與傳感器工作節(jié)點(diǎn)數(shù)之間關(guān)系的變化曲線。由圖3中可以看出,本文OCCAJS算法在不同參數(shù)作用下所需工作節(jié)點(diǎn)數(shù)較少,而EPDM所需傳感器節(jié)點(diǎn)數(shù)較多,其原因在于:當(dāng)λ=1.2時(shí),其傳感器節(jié)點(diǎn)與鄰居節(jié)點(diǎn)所構(gòu)成的覆蓋面積大于λ=0.8時(shí)的覆蓋面積,而SCA算法與EPDM算法是通過增加傳感器節(jié)點(diǎn)數(shù)達(dá)到對(duì)監(jiān)測區(qū)域的有效覆蓋。圖4以200 m×200 m區(qū)域作為仿真平臺(tái),給出了覆蓋率隨傳感器節(jié)點(diǎn)數(shù)變化曲線,從圖4可以看出,隨著傳感器節(jié)點(diǎn)數(shù)的增加,3種算法的覆蓋率也隨之增加,由于本文OCCAJS算法通過動(dòng)態(tài)參數(shù)λ設(shè)定與調(diào)節(jié)完成對(duì)監(jiān)測區(qū)域的有效覆蓋,因此,在覆蓋初始階段本文算法的覆蓋率要高于其他兩種算法。在傳感器節(jié)點(diǎn)數(shù)為137時(shí),本文算法已達(dá)到有效覆蓋,而SCA算法和EPDM算法在節(jié)點(diǎn)數(shù)為180和199時(shí),才達(dá)到有效覆蓋,與兩種算法平均覆蓋率相比,平均提升了11.02%。圖5～圖8給出了以300 m×300 m區(qū)域作為仿真平臺(tái),對(duì)不同覆蓋率和冗余節(jié)點(diǎn)數(shù)的對(duì)比。由圖5可以看出,在滿足一定覆蓋率的前提下,λ越大其所需傳感器節(jié)點(diǎn)數(shù)就越少,原因同圖3分析相似。圖6給出了冗余傳感器節(jié)點(diǎn)數(shù)與覆蓋率關(guān)系的對(duì)比。由圖6可以看出,隨著冗余節(jié)點(diǎn)數(shù)的增加,其覆蓋率均有所下降,其主要原因是EPDM算法是通過事件概率驅(qū)動(dòng)方式完成對(duì)冗余節(jié)點(diǎn)狀態(tài)的調(diào)度,而SCA算法則是通過節(jié)點(diǎn)之間的接發(fā)信息方式完成冗余節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換。圖7、圖8的分析過程與圖4、圖5相似。

實(shí)驗(yàn)2 不同仿真規(guī)模下本文算法與文獻(xiàn)[6]所提出的ECTA算法在網(wǎng)絡(luò)生存周期與算法運(yùn)行時(shí)間上進(jìn)行比對(duì)實(shí)驗(yàn)。

圖9 200 m×200 m區(qū)域兩種算法的網(wǎng)絡(luò)生存周期對(duì)比

圖10 兩種算法的運(yùn)行時(shí)間對(duì)比

圖9和圖10分別給出了本文算法與ECTA算法在網(wǎng)絡(luò)生存周期和算法運(yùn)行時(shí)間上的對(duì)比。由圖9中可以看出,在初始時(shí)刻,兩種算法的網(wǎng)絡(luò)生存周期基本相等,隨著傳感器節(jié)點(diǎn)數(shù)的增加,兩種算法的網(wǎng)絡(luò)生存周期都有所延長,但ECTA算法采用的是非線性不間斷連續(xù)覆蓋模式完成對(duì)目標(biāo)節(jié)點(diǎn)的監(jiān)測,在能耗方向高于OCCAJS算法,當(dāng)傳感器節(jié)點(diǎn)數(shù)為180時(shí),兩種算法的網(wǎng)絡(luò)生存周期趨于平穩(wěn),本文算法的平均網(wǎng)絡(luò)生存周期比ECTA算法提升了13.27%。圖10給出了傳感器節(jié)點(diǎn)數(shù)與算法運(yùn)行時(shí)間的對(duì)比,由于ECTA算法在節(jié)點(diǎn)能量存儲(chǔ)方式上采用的是鏈表式存儲(chǔ),通過遍歷算法對(duì)整個(gè)鏈表中高能量節(jié)點(diǎn)進(jìn)行排序,讓高能量節(jié)點(diǎn)獲得更高權(quán)限以完成對(duì)目標(biāo)節(jié)點(diǎn)的覆蓋,其算法復(fù)雜度低于本文算法,因此,在算法運(yùn)行時(shí)間上,本文算法的運(yùn)行時(shí)間多于ECTA算法。

4 結(jié) 論

為了更好地解決無線傳感器網(wǎng)絡(luò)覆蓋問題,本文提出一種聯(lián)合感知優(yōu)化覆蓋控制算法。該算法利用幾何理論給出了三圓無縫對(duì)接的最大覆蓋面積的求解方法。在此基礎(chǔ)上,利用概率相關(guān)理論給出監(jiān)測區(qū)域內(nèi)k個(gè)隨機(jī)節(jié)點(diǎn)的覆蓋期望值的求解方法和計(jì)算過程;定理2驗(yàn)證了監(jiān)測區(qū)域有效覆蓋最少節(jié)點(diǎn)數(shù)的求解過程。在冗余節(jié)點(diǎn)覆蓋度方面,本文引入了比例綱量,建立傳感器節(jié)點(diǎn)集合冗余連通圖,證明了傳感器節(jié)點(diǎn)冗余覆蓋度滿足的條件。最后,本文算法與其他算法在覆蓋率、冗余度、網(wǎng)絡(luò)生存周期和算法運(yùn)行時(shí)間上進(jìn)行了一系列仿真實(shí)驗(yàn)對(duì)比,并對(duì)仿真結(jié)果進(jìn)行了分析與說明,驗(yàn)證了本文算法的有效性和可行性。

今后的工作重點(diǎn)是研究如何實(shí)現(xiàn)對(duì)邊界區(qū)域的有效覆蓋以及對(duì)多個(gè)移動(dòng)目標(biāo)節(jié)點(diǎn)的有效覆蓋。

[1] ERDELJ M, LOSCRI V, NATALIZIO E, et al. Multiple point of interest discovery and coverage with mobile wireless sensor [J]. Ad Hoc Networks, 2013, 11(8): 2288-2300.

[2] ZAIRI S, ZOUARI B, NIEL E, et al. Nodes self-scheduling approach for maximizing wireless sensor networks lifetime based on remaining energy [J]. IET Wireless Sensor Systems, 2012, 2(1): 52-62.

[3] 畢冉, 李建中, 高宏. 無線傳感器網(wǎng)絡(luò)中最小化通信開銷的近似監(jiān)測算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(10): 2092-2105. BI Ran, LI Jianzhong, GAO Hong. Approximate monitoring algorithm for minimizing communication cost in wireless sensor networks [J]. Chinese Journal of Computers, 2015, 38(10): 2092-2105.

[4] 任倩倩, 李建中, 王宇. 無線傳感器網(wǎng)絡(luò)具有跟蹤質(zhì)量保證的節(jié)點(diǎn)選擇算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(10): 2007-2014. REN Qianqian, LI Jianzhong, WANG Yu. Tracking quality aware nodes selection algorithms in wireless sensor networks [J]. Chinese Journal of Computers, 2012, 35(10): 2007-2014.

[5] 孫澤宇, 伍衛(wèi)國, 王換招, 等. 無線傳感器網(wǎng)絡(luò)基于參數(shù)可調(diào)增強(qiáng)型覆蓋算法 [J]. 電子學(xué)報(bào), 2015, 43(3): 466-474. SUN Zeyu, WU Weiguo, WANG Huanzhao, et al. An enhanced coverage control algorithm for wireless sensor networks based on adjustable parameters [J]. Acta Electronica Sinica, 2015, 43(3): 466-474.

[6] XING Xiaofei, WANG Guojun, LI Jie. Polytype target coverage scheme for heterogeneous wireless sensor networks using linear programming [J]. Wireless Communications and Mobile Computing, 2012, 14(14): 1397-1408.

[7] SUN Zeyu, WU Weiguo, WANG Huanzhao, et al. A novel coverage algorithm based on event-probability-driven mechanism in wireless sensor network [J]. EURASIP Journal on Wireless Communications and Networking, 2014, 2014(1): 1-17.

[8] 孟凡治, 王換招, 何暉. 基于聯(lián)合感知模型的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議 [J]. 電子學(xué)報(bào), 2011, 39(4): 772-779. MENG Fanzhi, WANG Huanzhao, HE Hui. Connected coverage protocol using cooperative sensing model for wireless sensor networks [J]. Acta Electronica Sinica, 2011, 39(4): 722-779.

[9] 何欣, 桂小林, 安健. 面向目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)確定性部署方法 [J]. 西安交通大學(xué)學(xué)報(bào), 2010, 44(6): 6-9. HE Xin, GUI Xiaolin, AN Jian. A deterministic deployment approach of nodes in wireless sensor networks for target coverage [J]. Journal of Xi’an Jiaotong University, 2010, 44(6): 6-9.

[10]王換招, 孟凡治, 李增智. 高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議 [J]. 軟件學(xué)報(bào), 2010, 21(12): 3124-3137. WANG Huanzhao, MENG Fanzhi, LI Zangzhi. Energy efficient conserving protocol for wireless sensor networks [J]. Journal of Software, 2010, 21(12): 3124-3137.

[11]孫澤宇, 伍衛(wèi)國, 王招換, 等. 概率模型下的一種優(yōu)化覆蓋算法 [J]. 軟件學(xué)報(bào), 2016, 27(5): 1285-1300. SUN Zeyu, WU Weiguo, WANG Huanzhao, et al. Optimized coverage algorithm in probability mode [J]. Journal of Software, 2016, 27(5): 1285-1300.

[12]魏全瑞, 劉俊, 韓九強(qiáng). 改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計(jì)與節(jié)點(diǎn)定位算法 [J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(6): 1-6. WEI Quanrui, LIU Jun, HAN Jiuqiang. An improved DV-hop node locational algorithm based on unbiased estimation for wireless sensor networks [J]. Journal of Xi’an Jiaotong University, 2014, 48(6): 1-6.

[本刊相關(guān)文獻(xiàn)鏈接]

孫澤宇,伍衛(wèi)國,曹仰杰,等.無線傳感器網(wǎng)絡(luò)中能量均衡參數(shù)可控覆蓋算法.2016,50(8):77-83.[doi:10.7652/xjtuxb 201608013]

汪志偉,曹建福,鄭輯光.一種面向分簇?zé)o線傳感器網(wǎng)絡(luò)的多信道跨層協(xié)議.2013,47(6):61-67.[doi:10.7652/xjtuxb 201306011]

李彬,王文杰,殷勤業(yè),等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的節(jié)能路由傳輸.2012,46(6):1-6.[doi:10.7652/xjtuxb201206001]

代亮,許宏科,陳婷.無線傳感器網(wǎng)絡(luò)可分負(fù)載調(diào)度算法.2012,46(6):23-28.[doi:10.7652/xjtuxb201206005]

梁慶偉,姚道遠(yuǎn),鞏思亮.一種保障時(shí)延能量的無線傳感器網(wǎng)絡(luò)路由協(xié)議.2012,46(6):48-52.[doi:10.7652/xjtuxb201206 009]

方維維,錢德沛,劉軼.一種相鄰節(jié)點(diǎn)協(xié)作的無線傳感器網(wǎng)絡(luò)可靠輿方案.2009,43(2):33-37.[doi:10.7652/xjtuxb200902 008]

王換招,孟凡治,李增智.最大化網(wǎng)絡(luò)有效壽命的傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議.2009,43(10):66-70.[doi:10.7652/xjtuxb 200910014]

王換招,董貝,羅韓梅,等.基于k-覆蓋保證的異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度策略.2008,42(8):940-944.[doi:10.7652/xjtuxb 200808003]

(編輯 武紅江)

An Optimal Coverage Control Algorithm with Joint Sensing for Wireless Sensor Networks

SUN Zeyu1,2,LI Chuanfeng1,3,XING Xiaofei4,CAO Yangjie5

(1. School of Computer and Information Engineering, Luoyang Institute of Science and Technology, Luoyang, Henan 471023, China; 2. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 3. School of Electrical Engineering and Computer Science, Queen’s University Belfast, Belfast BT95AH, UK; 4. School of Computer Science and Software Engineering, Guangzhou University, Guangzhou 510006, China;5. School of Software and Application Science Technology, Zhengzhou University, Zhengzhou 450001, China)

An optimal coverage control algorithm with joint sensing (OCCAJS) is proposed to solve the problem of rapid consumption of network energy resulted from the large number of redundant nodes in the process of wireless sensor network coverage. The algorithm presents the solving process of maximal seamless coverage in the case of joint coverage of three nodes. Two methods are given, one calculates the expectations of coverage quality when sensor nodes are covered in the monitoring area and the other determines coverage rate when the expectation of a sensor node is compared with those of neighbor nodes. Moreover, when redundant coverage exists, the calculation process of the coverage rate for any sensor node in redundant coverage is presented by using ratio quotient. Simulation results and comparison with some existing algorithms in coverage quality and network lifetime show that the proposed algorithm improves the average performance about 11.02% and 13.27%,respectively. The proposed algorithm not only improves the coverage quality, but also suppresses the rapid consumption of nodes energy and the network lifetime is prolonged.

wireless sensor network; coverage quality; nodes joint; network lifetime

2016-05-31。

孫澤宇(1977—),男,副教授,博士生;李傳鋒(通信作者),男,博士,副教授。

國家自然科學(xué)基金資助項(xiàng)目(U1304603);河南省科技攻關(guān)重點(diǎn)資助項(xiàng)目(162102210113);河南省教育廳高等學(xué)校重點(diǎn)科研項(xiàng)目(17A520044)。

時(shí)間:2016-07-21

http:∥www.cnki.net/kcms/detail/61.1069.T.20160721.1102.006.html

10.7652/xjtuxb201610013

TP393

A

0253-987X(2016)10-0086-07