宋志強(qiáng), 周獻(xiàn)中, 陳春林

(1.南京大學(xué) 工程管理學(xué)院，江蘇 南京 210008；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 機(jī)電與信息技術(shù)學(xué)院，江蘇 蘇州 215009)

面向區(qū)域覆蓋的異構(gòu)傳感器節(jié)點(diǎn)部署*

宋志強(qiáng)1,2, 周獻(xiàn)中1, 陳春林1

(1.南京大學(xué) 工程管理學(xué)院，江蘇 南京 210008；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 機(jī)電與信息技術(shù)學(xué)院，江蘇 蘇州 215009)

摘要:針對異構(gòu)傳感器節(jié)點(diǎn)隨機(jī)部署于被監(jiān)測區(qū)域時容易產(chǎn)生覆蓋漏洞的問題，提出一種基于取樣直線掃描的覆蓋漏洞修復(fù)算法，基于取樣直線掃描，找到覆蓋漏洞；通過移動傳感器節(jié)點(diǎn)修復(fù)覆蓋漏洞。該算法以完全覆蓋被監(jiān)測區(qū)域?yàn)閮?yōu)化目標(biāo)，對于具有相同感知半徑的同構(gòu)傳感器節(jié)點(diǎn)和具有不同感知半徑的異構(gòu)傳感器節(jié)點(diǎn)同樣適用。仿真實(shí)驗(yàn)表明：該算法能有效修復(fù)覆蓋漏洞。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)； 異構(gòu)傳感器節(jié)點(diǎn)； 區(qū)域覆蓋； 覆蓋漏洞修復(fù)算法

0引言

傳感器節(jié)點(diǎn)的部署問題是各類系統(tǒng)應(yīng)用的關(guān)鍵問題之一，有的應(yīng)用場合要求傳感器節(jié)點(diǎn)完全覆蓋被監(jiān)測區(qū)域，以確保被監(jiān)測區(qū)域內(nèi)發(fā)生的事件可以被傳感器及時感知。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的區(qū)域覆蓋問題，主要研究工作集中于同構(gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋問題，即假設(shè)感器節(jié)點(diǎn)的感知半徑是相同的[1～9]。針對環(huán)境安全且規(guī)模較小的場合，文獻(xiàn)[1]利用靜止傳感器節(jié)點(diǎn)，研究確定性部署。文獻(xiàn)[2]首先在區(qū)域內(nèi)密集部署靜態(tài)傳感器節(jié)點(diǎn)，然后通過多目標(biāo)經(jīng)驗(yàn)競爭算法激活最少的傳感器節(jié)點(diǎn)工作，而其它傳感器節(jié)點(diǎn)則處于休眠模式。文獻(xiàn)[3]的研究均基于Voronoi圖，利用Voronoi圖找出覆蓋空洞，采用相應(yīng)的算法修復(fù)空洞。文獻(xiàn)[4～7]利用虛擬力方法來研究移動傳感器節(jié)點(diǎn)的部署問題，其核心思想是通過節(jié)點(diǎn)之間的引力和斥力，引導(dǎo)節(jié)點(diǎn)移動。文獻(xiàn)[8]專門研究了采用虛擬力方法部署移動傳感器節(jié)點(diǎn)的缺陷，并對虛擬力方法作相應(yīng)改進(jìn)?；诋悩?gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋，相關(guān)研究較少，文獻(xiàn)[9]研究了異構(gòu)傳感器節(jié)點(diǎn)的覆蓋問題，但該方法不能保證對區(qū)域的完全覆蓋。在實(shí)際的應(yīng)用中，各傳感器節(jié)點(diǎn)通常是異構(gòu)的，研究異構(gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋更具現(xiàn)實(shí)意義。

移動傳感器節(jié)點(diǎn)由于具備移動特性，比傳統(tǒng)的靜態(tài)傳感器節(jié)點(diǎn)更具應(yīng)用價值。本文首先隨機(jī)部署感知半徑不同的靜態(tài)傳感器節(jié)點(diǎn)，然后利用覆蓋漏洞修復(fù)算法找出覆蓋漏洞，最后通過移動傳感器節(jié)點(diǎn)修復(fù)覆蓋漏洞，使被監(jiān)測區(qū)域達(dá)到完全覆蓋。

1問題描述

考慮N個靜態(tài)傳感器節(jié)點(diǎn)隨機(jī)部署于二維被監(jiān)測區(qū)域A中，N個靜態(tài)傳感器組成的集合可由式(1)表示

S={s1,s2,…,sN}

(1)

被監(jiān)測區(qū)域A長L，寬W。各傳感器節(jié)點(diǎn)si可表述為

si={xi,yi,ri},i=1,2,…,N

(2)

式中(xi,yi)為節(jié)點(diǎn)坐標(biāo)，ri為感知半徑。對于位于區(qū)域A內(nèi)的任意點(diǎn)p(x,y)，將節(jié)點(diǎn)si和點(diǎn)p之間的歐氏距離記為d(p,si)

(3)

各傳感器節(jié)點(diǎn)采用0/1感知模型，即傳感器節(jié)點(diǎn)的感知范圍是以節(jié)點(diǎn)為圓心的圓，如果事件發(fā)生在節(jié)點(diǎn)的感知圓內(nèi)，則感知概率為1，若事件發(fā)生在感知圓外，則感知概率為0,則節(jié)點(diǎn)si對點(diǎn)p的感知概率可表示為

(4)

記節(jié)點(diǎn)si的覆蓋范圍為Si，Si的面積可表示為

(5)

則區(qū)域A中N個靜態(tài)傳感器節(jié)點(diǎn)的覆蓋面積STotal為N個靜態(tài)傳感器節(jié)點(diǎn)覆蓋面積的并集，即

(6)

記被監(jiān)測區(qū)域A的面積為SA，則被監(jiān)測區(qū)域A的初始覆蓋率為

(7)

部署移動傳感器節(jié)點(diǎn)的目的為最大化被監(jiān)測區(qū)域A的覆蓋率，即使得STotal=SA，即完全覆蓋被監(jiān)測區(qū)域，覆蓋率為100 %。

假設(shè)由靜態(tài)傳感器節(jié)點(diǎn)和移動傳感器節(jié)點(diǎn)組成的傳感網(wǎng)具有如下性質(zhì)：1)傳感器節(jié)點(diǎn)可通過GPS或其他方式獲知自身位置，并通過網(wǎng)絡(luò)發(fā)送至監(jiān)測中心，即監(jiān)測中心可知傳感器節(jié)點(diǎn)的位置信息；2)傳感器節(jié)點(diǎn)通信半徑至少是其感知半徑的2倍，即對于任意傳感器節(jié)點(diǎn)si，其通信半徑rci≥2ri；3)移動傳感器節(jié)點(diǎn)能量充足，可移動至指定位置；4)傳感器網(wǎng)絡(luò)保證節(jié)點(diǎn)在其通信半徑范圍內(nèi)的連通性。

2覆蓋漏洞修復(fù)算法

2.1覆蓋漏洞檢測

定義 取樣直線：在二維平面內(nèi)沿x軸方向或y軸方向與被監(jiān)測區(qū)域相交的任意直線。

如圖1所示，水平方向直線與被監(jiān)測區(qū)域交于A,B兩點(diǎn)，垂直方向直線與被監(jiān)測區(qū)域交于C,D兩點(diǎn)，直線AB和CD都是取樣直線。

圖1　取樣直線Fig 1　Sampling straight line

當(dāng)感知圓si的圓心到取樣直線的距離小于其感知半徑時，感知圓和該取樣直線相交，相交的直線段被該圓覆蓋；當(dāng)感知圓si的圓心到取樣直線的距離大于其感知半徑時，感知圓和該取樣直線不相交；當(dāng)感知圓si的圓心到取樣直線的距離等于其感知半徑時，感知圓和該取樣直線相切。

如圖2所示，AB為被監(jiān)測區(qū)域內(nèi)平行于x軸的一條取樣直線，其直線方程為y=y0。s1,s2,…,sn為n個與該直線相交的感知圓，其傳感器節(jié)點(diǎn)坐標(biāo)分別為(x1,y1)，(x2,y2),…,(xn,yn)。假設(shè)由節(jié)點(diǎn)si形成的感知圓和取樣直線AB的兩個交點(diǎn)坐標(biāo)分別為(xi_l,y0),(xi_r,y0)，交點(diǎn)橫坐標(biāo)滿足xi_l

圖2　感知圓與取樣直線相交示意圖Fig 2　Diagram of sensing circles and sampling straight lines intersect

基于上述分析，取樣直線被感知圓完全覆蓋的條件可歸納為

(8)

若不滿足式(8)的條件，則取樣直線未能被感知圓完全覆蓋，即感知圓和取樣直線之間存在覆蓋漏洞。如圖3所示，灰色區(qū)域Ⅰ,Ⅱ,Ⅲ均為覆蓋漏洞。2.2節(jié)設(shè)計(jì)覆蓋漏洞修復(fù)算法，使得傳感器節(jié)點(diǎn)能完全覆蓋被監(jiān)測區(qū)域。

圖3　覆蓋漏洞示意圖Fig 3　Diagram of coverage leak

2.2修補(bǔ)算法

被監(jiān)測區(qū)域A長為L，寬為W，N個靜止無線傳感器節(jié)點(diǎn)s1,s2,…,sn隨機(jī)分布于監(jiān)測區(qū)域A。傳感器節(jié)點(diǎn)si的感知半徑為ri(i=1,2,…,N)，Rmin≤ri≤Rmax，Rmin,Rmax分別為N個節(jié)點(diǎn)感知半徑的最小值和最大值，假設(shè)移動傳感器節(jié)點(diǎn)的感知半徑也在Rmin與Rmax之間。單次覆蓋漏洞修補(bǔ)算法流程圖如圖4所示。

圖4　單次覆蓋漏洞修補(bǔ)算法流程圖Fig 4　Algorithm flow chart of single coverage leak repair algorithm

3仿真實(shí)驗(yàn)

為驗(yàn)證算法有效性，采用MatlabR2010b仿真，被監(jiān)測區(qū)域A=200m×200m=40 000m2，首先在被監(jiān)測區(qū)域隨機(jī)部署40個靜態(tài)傳感器節(jié)點(diǎn)。

靜態(tài)傳感器節(jié)點(diǎn)感知半徑為8～20m的隨機(jī)數(shù)，N=40時，共做100次實(shí)驗(yàn)。算法僅作水平取樣就能完成被監(jiān)測區(qū)域的完全覆蓋，因隨機(jī)部署靜態(tài)傳感器時的初始覆蓋率不同，故無人平臺數(shù)(即移動傳感器節(jié)點(diǎn)數(shù))量在77～87之間變化。在僅改變靜態(tài)傳感器節(jié)點(diǎn)數(shù)量，其余參數(shù)不變的情況下，進(jìn)一步驗(yàn)證算法性能，當(dāng)N分別為60,80,100,120,140,160,180,200時，再分別做100次實(shí)驗(yàn)，仿真實(shí)驗(yàn)時算法僅作水平取樣時，就能完成被監(jiān)測區(qū)域的完成覆蓋，仿真實(shí)驗(yàn)表明算法的有效性，其中N=80時移動傳感器節(jié)點(diǎn)部署前后對照圖如圖5所示。

圖5　覆蓋漏洞修補(bǔ)算法運(yùn)行前后部署對照圖Fig 5　Deployment comparison chart before and after coverage leak repair algorithm running

N從40變化至200時，完成被監(jiān)測區(qū)域完全覆蓋所需的移動傳感器節(jié)點(diǎn)數(shù)量變化情況如圖6所示。從圖6可看出，隨著靜態(tài)傳感器節(jié)點(diǎn)的增加，修補(bǔ)覆蓋漏洞所需的移動傳感器節(jié)點(diǎn)數(shù)量逐漸減少，原因是靜態(tài)傳感器增加后，初始覆蓋率會相應(yīng)提高。具體選擇部署多少靜態(tài)傳感器節(jié)點(diǎn)及移動傳感器節(jié)點(diǎn)，可根據(jù)其價格綜合衡量。

圖6　移動傳感器節(jié)點(diǎn)隨靜態(tài)傳感器節(jié)點(diǎn)變化Fig 6　Mobile sensor nodes change with static sensor nodes

4結(jié)論

針對靜態(tài)傳感器節(jié)點(diǎn)隨機(jī)部署于被監(jiān)測區(qū)域時，容易存在覆蓋漏洞的問題，本文提出一種基于取樣直線掃描的覆蓋漏洞修復(fù)算法。該算法對于同構(gòu)傳感器節(jié)點(diǎn)和具有不同感知半徑的異構(gòu)傳感器節(jié)點(diǎn)同樣適用。算法能夠修補(bǔ)靜態(tài)傳感器節(jié)點(diǎn)部署于被監(jiān)測區(qū)域形成的覆蓋漏洞，使被監(jiān)測區(qū)域達(dá)到完全覆蓋，以保證整個區(qū)域任何地點(diǎn)可能發(fā)生的異常情況均能被傳感器監(jiān)測到，實(shí)現(xiàn)無遺漏地監(jiān)測關(guān)鍵區(qū)域。

參考文獻(xiàn):

[1]KarK,BanerjeeS.Nodeplacementforconnectedcoveragein

sensornetworks[C]∥ModelingandOptimizationinMobile,AdHocandWirelessNetworks，WiOpt’03，2003 :1-2.

[2]EnayatifarR,YousefiM,AbdullahAH,etal.Anovelsensordeploymentapproachusingmulti-objectiveimperialistcompetitivealgorithminwirelesssensornetworks[J].ArabianJournalforScienceandEngineering,2014,39(6):4637-4650.

[3]趙春江,吳華瑞,劉強(qiáng),等.基于Voronoi的無線傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].通信學(xué)報,2013,34(9):115-122.

[4]HuangJ,SunL,WangR,etal.Improvedvirtualpotentialfieldalgorithmbasedonprobabilitymodelinthree-dimensionaldirectionalsensornetworks[J].InternationalJournalofDistributedSensorNetworks,2012,2012:1-9.

[5]SongZ,ZhouX,LiH.Virtualforce-aidedparticleswarmoptimizationfordeploymentofmobilenodesinwirelesssensornetwork-s[C]∥Proceedingsofthe2012InternationalConferenceonElectronics,CommunicationsandControl,IEEEComputerSociety,2012:81-84.

[6]HanYH,KimY,KimWT,etal.Anenergy-efficientself-deploymentwiththecentroid-directedvirtualforceinmobilesensornetworks[J].Simulation,2012,88(10):1152-1165.

[7]NanG,ChenZ,LiM,etal.Distributeddeploymentalgorithmbasedonboundaryexpansionandvirtualforceformobilesensornetworks[J].NeuralNetworkWorld,2014,24(3):309-332.

[8]BartoliniN,BongiovanniG,LaPortaT,etal.Onthevulnerabilitiesofthevirtualforceapproachtomobilesensordeployment[J].IEEETransactionsonMobileComputing,2014,13(11):2592-2605.

[9]杜曉玉,孫力娟,郭劍,等.異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報,2014,36(3):696-702.

Deploymentofheterogeneoussensornodesforregionalcoverage*

SONGZhi-qiang1,2,ZHOUXian-zhong1,CHENChun-lin1

(1.SchoolofEngineeringManagement,NanjingUniversity,Nanjing210008,China;2.SchoolofElectromechanicalandInformationTechnology,SuzhouInstituteofTrade&Commerce,Suzhou215009,China)

Abstract:Aiming at problem that heterogeneous sensor nodes are randomly deployed in monitored area prone to genenate coverage leak,a coverage leak repair algorithm based on sampling straight line scan is proposed.Coverage leak are found based on sampling straight line scan;coverage leak are repaired by mobile sensor nodes.The algorithm treats the completely covered area by sensor nodes as the optimization goal and it is applicable for both homogeneous sensor nodes with the sensing radius of and the perception of the heterogeneous sensor nodes with different sensing radius.Simulation results show that the algorithm can effectively repair coverage leak.

Key words:wireless sensor networks(WSNs); heterogeneous sensor nodes;regional coverage; coverage leak repair algorithm

DOI:10.13873/J.1000—9787(2016)04—0119—04

收稿日期：2015—07—05

*基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61273327)

中圖分類號:TP 393

文獻(xiàn)標(biāo)識碼:A

文章編號:1000—9787(2016)04—0119—04

作者簡介:

宋志強(qiáng)(1977-)，男，江蘇張家港人，博士研究生，副教授，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、群智能系統(tǒng)任務(wù)規(guī)劃與優(yōu)化調(diào)度。