宋志强, 周献中, 陈春林

(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-)，男，江苏张家港人，博士研究生，副教授，主要研究方向为无线传感器网络、群智能系统任务规划与优化调度。