宋志強, 周獻中, 陳春林

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

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

宋志強1,2, 周獻中1, 陳春林1

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

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

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

0引言

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

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

1問題描述

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

S={s1,s2,…,sN}

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

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

2覆蓋漏洞修復算法

2.1覆蓋漏洞檢測

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

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

圖1　取樣直線Fig 1　Sampling straight line

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

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

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

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

(8)

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

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

2.2修補算法

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

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

3仿真實驗

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

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

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

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

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

4結(jié)論

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

參考文獻:

[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]趙春江,吳華瑞,劉強,等.基于Voronoi的無線傳感器網(wǎng)絡覆蓋控制優(yōu)化策略[J].通信學報,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)絡覆蓋優(yōu)化算法[J].電子與信息學報,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

*基金項目：國家自然科學基金資助項目(61273327)

中圖分類號:TP 393

文獻標識碼:A

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

作者簡介:

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