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

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

?

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

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

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

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

大學計算機科學與教育軟件學院,510006,廣州;5.鄭州大學軟件與應用科技學院,450001,鄭州)

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

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

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

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

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

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

1 預備知識

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

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

(1)

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

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

(2)

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

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

(3)

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

證明 如圖1所示,設陰影面積為S1,扇形OACB面積為S2,三角形面積為S3。因為所求覆蓋面積最大,所以3個傳感器節(jié)點相交于一點B,由對稱性及圓心角所對同弦定理可知,陰影中心弦是圓O內(nèi)接正六邊形的一條邊長,即扇形OACB為圓O的1/6,弦所對的圓心角為π/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é)點無縫對接示意圖

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

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

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

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

P1=πr2/area(S)

(7)

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

(8)

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

R0)2exp(-x2/2)dx

(9)

經(jīng)計算得

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

(10)

化簡式(10)可得

(11)

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

(12)

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

(13)

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

(14)

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

(15)

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

2.2 冗余覆蓋

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

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

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

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

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

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

證明 以圖2為例加以證明。由假設條件可知,傳感器節(jié)點均為同構(gòu)節(jié)點,通信半徑R與感知半徑r的比例關(guān)系為R=λr,λ是比例系數(shù),設∠BCE=α,點B與點C之間的距離l為隨機變量,由概率密度函數(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)可知,對于任意冗余節(jié)點的冗余覆蓋率可表示為

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

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

(19)

當n個冗余節(jié)點進行有效覆蓋時,其冗余覆蓋率為

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

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

(20)

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

2.3 OCCAJS算法實現(xiàn)

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

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

3 體系評估

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

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

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

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

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

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

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

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

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

實驗2 不同仿真規(guī)模下本文算法與文獻[6]所提出的ECTA算法在網(wǎng)絡生存周期與算法運行時間上進行比對實驗。

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

圖10 兩種算法的運行時間對比

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

4 結(jié) 論

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

今后的工作重點是研究如何實現(xiàn)對邊界區(qū)域的有效覆蓋以及對多個移動目標節(jié)點的有效覆蓋。

[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)絡中最小化通信開銷的近似監(jiān)測算法 [J]. 計算機學報, 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)絡具有跟蹤質(zhì)量保證的節(jié)點選擇算法 [J]. 計算機學報, 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)絡基于參數(shù)可調(diào)增強型覆蓋算法 [J]. 電子學報, 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)絡連通性覆蓋協(xié)議 [J]. 電子學報, 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] 何欣, 桂小林, 安健. 面向目標覆蓋的無線傳感器網(wǎng)絡確定性部署方法 [J]. 西安交通大學學報, 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)絡覆蓋保持協(xié)議 [J]. 軟件學報, 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]. 軟件學報, 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]魏全瑞, 劉俊, 韓九強. 改進的無線傳感器網(wǎng)絡無偏距離估計與節(jié)點定位算法 [J]. 西安交通大學學報, 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)文獻鏈接]

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

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

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

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

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

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

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

王換招,董貝,羅韓梅,等.基于k-覆蓋保證的異構(gòu)傳感器網(wǎng)絡節(jié)點調(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—),男,副教授,博士生;李傳鋒(通信作者),男,博士,副教授。

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

時間: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