面向區域覆蓋的異構傳感器節點部署*

宋志強, 周獻中, 陳春林

(1.南京大學 工程管理學院，江蘇 南京 210008；2.蘇州經貿職業技術學院 機電與信息技術學院，江蘇 蘇州 215009)

面向區域覆蓋的異構傳感器節點部署*

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

(1.南京大學 工程管理學院，江蘇 南京 210008；2.蘇州經貿職業技術學院 機電與信息技術學院，江蘇 蘇州 215009)

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

關鍵詞:無線傳感器網絡； 異構傳感器節點； 區域覆蓋； 覆蓋漏洞修復算法

0引言

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

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

1問題描述

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

S={s1,s2,…,sN}

(1)

被監測區域A長L，寬W。各傳感器節點si可表述為

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

(2)

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

(3)

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

(4)

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

(5)

則區域A中N個靜態傳感器節點的覆蓋面積STotal為N個靜態傳感器節點覆蓋面積的并集，即

(6)

記被監測區域A的面積為SA，則被監測區域A的初始覆蓋率為

(7)

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

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

2覆蓋漏洞修復算法

2.1覆蓋漏洞檢測

定義 取樣直線：在二維平面內沿x軸方向或y軸方向與被監測區域相交的任意直線。

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

圖1　取樣直線Fig 1　Sampling straight line

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

如圖2所示，AB為被監測區域內平行于x軸的一條取樣直線，其直線方程為y=y0。s1,s2,…,sn為n個與該直線相交的感知圓，其傳感器節點坐標分別為(x1,y1)，(x2,y2),…,(xn,yn)。假設由節點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所示，灰色區域Ⅰ,Ⅱ,Ⅲ均為覆蓋漏洞。2.2節設計覆蓋漏洞修復算法，使得傳感器節點能完全覆蓋被監測區域。

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

2.2修補算法

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

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

3仿真實驗

為驗證算法有效性，采用MatlabR2010b仿真，被監測區域A=200m×200m=40 000m2，首先在被監測區域隨機部署40個靜態傳感器節點。

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

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

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

圖6　移動傳感器節點隨靜態傳感器節點變化Fig 6　Mobile sensor nodes change with static sensor nodes

4結論

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

參考文獻:

[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的無線傳感器網絡覆蓋控制優化策略[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]杜曉玉,孫力娟,郭劍,等.異構無線傳感器網絡覆蓋優化算法[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-)，男，江蘇張家港人，博士研究生，副教授，主要研究方向為無線傳感器網絡、群智能系統任務規劃與優化調度。