有向移动异构传感网分布式部署策略*

余颖华，李　艳，吴德恩，秦宁宁，3*

（1.江南大学物联网工程学院，江苏无锡214122；2.无锡商业职业技术学院物联网技术学院，江苏无锡214153；3.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122）

有向移动异构传感网分布式部署策略*

余颖华1，李艳2，吴德恩1，秦宁宁1，3*

（1.江南大学物联网工程学院，江苏无锡214122；2.无锡商业职业技术学院物联网技术学院，江苏无锡214153；3.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122）

针对移动异构有向传感网的覆盖增强问题，提出了一种基于虚拟全向感知圆的节点分布式部署策略DDS（Distributed Deployment Strategy）。DDS采用等面积虚拟全向感知圆替代有向节点感知扇形，根据不同感知圆之间的位置与半径大小关系为每个有向节点合理构建区域覆盖子区间，最后由该子区间多边形的形心确定节点的候选位置坐标。同时，DDS策略充分利用有向节点的旋转特性，计算节点视角方向使其面向检测区域外侧。节点通过视角调整和合理移动，不断提高网络覆盖率。仿真结果表明，DDS在提高网络覆盖率，增强节点分布均衡性方面具有明显的优势。

有向传感网；虚拟全向感知圆；覆盖子区间；覆盖率

移动传感器网络［1］是由部署在目标区域内的大量移动传感器节点组成的一个多跳自组织网络，被广泛运用于环境感知、军事安全、医疗监控等多个领域。

在现有的移动传感器网络覆盖部署研究中，大量算法主要针对以全向感知模型为基础的传统网络。在全向感知模型中，目标点是否被节点感知仅与二者之间的距离有关，与方向无关，可用于对温度、湿度、浓度等信息采集的场景。然而，对于相机、超声波、视频监控等传感器，节点受自身物理特性的限制，对目标点的感知性能是分方向的，即节点具有固定的感知方向。目前，以有向感知模型为基础的有向网络部署问题，研究成果还相对缺乏。文献［2］较早提出了有向传感器的概念以及有向感知节点的4-维感知模型，开启了直接面向有向传感器网络的研究工作。文献［3］进一步将基本的有向感知模型扩展为视觉方向可调感知模型，提出了一种基于虚拟势场的有向传感器网络覆盖增强算法PFCEA（Potential Field Based Coverage-Enhancing Algorithm）。通过引入感知模型“质心”的概念，将有向传感器网络的覆盖增强问题转化为虚拟势场作用下质心点的均匀分布问题，网络部署成本以及计算复杂度得到了极大降低，但由于算法性能易受节点位置影响，覆盖率提升空间相对有限。Liang等人［4］率先提出有向移动传感器网络的部署问题［5］，针对同构有向可移动节点，分别设计了基于扇形感知模型内切圆圆心和外接圆圆心的两种解决方案，可有效提高网络覆盖率，但忽略了节点感知视角大小对网络部署效果的影响，适用性较差。针对移动异构有向传感器网络，文献［6］提出了一种基于虚拟力［7］的最优部署算法 OPT（Optimized Deployment Algorithm），将节点移动特性和旋转特性相结合，极大提高了网络覆盖效果，但每个节点的受力计算需要全网节点信息，通信能耗大，计算复杂度高。

基于上述分析，针对有向移动异构传感网的覆盖问题［8］，论文提出了一种分布式部署策略DDS。该策略根据有向节点的覆盖特征求其全向虚拟替代感知圆，并依据相邻虚拟替代感知圆的几何空间位置，为每个节点划分覆盖子区域，当且仅当节点的位置更新可提高对自身所在子区域的覆盖面积时，节点才能移动。同时，各个节点根据自身在目标区域的位置调整感知方向，以确保网络中所有节点的感知视角面向检测区域边界。节点通过逐轮移动和旋转，最终使得整个网络覆盖面积最大化。

1　DDS应用前提

1.1感知模型

论文所用有向感知模型［9］是一个以节点位置坐标为圆心，以感知距离为半径的扇形区域［10］。如图1示，有向感知模型可用一个五元组表示。

图1 有向感知模型

图1中，p指代节点的位置坐标（x，y），v表示与扇形中轴线重合的感知方向向量，r表示节点感知半径，α表示节点感知视角大小，β表示节点感知方向角。

1.2网络运行环境

1.3虚拟替代感知圆

在以往有向传感网的部署工作中，常采用全向圆替代有向节点感知扇形，以简化部署过程。随着节点si感知视角αi的大小变化，si感知扇形常用三

种替代感知圆：内切圆（虚实线）、外接圆（实线）、质心圆（虚线）的替代效果如图2所示。

图2　不同感知角度下三种虚拟替代感知圆

由图2可知，当节点感知视角较小时，外接圆和内切圆的替代效果相对较好，质心圆的替代效果最差；而当节点感知角度较大时，质心圆的替代效果变好，而内切圆与外接圆的替代效果相对变差。因此当异构网络节点的感知视角差异较大时，上述三种虚拟感知圆的替代效果均不理想。

求解可得Ri≈ri。

考虑到质心作为物体质量的集中点，是质量分布均匀扇形的几何中心，因选定si扇形的质心Oi作为其替代圆ci的圆心位置。其中质心点Oi的坐标（xOi，yOi）的计算公式如下所示：

此时，以si感知扇形的质心Oi为圆心，以Ri=为半径的圆ci即为节点si的等面积虚拟替代感知圆。当si的感知视角αi分别为，时，ci的替代效果如图3所示。

图3　不同感知角度下ci的替代效果

1.4改进Voronoi图

Voronoi图［11-12］是由一组通过连接两邻点直线的垂直平分线围成的连续多边形组成，多被用于节点感知半径均等的全向传感器网络中。

针对感知半径不均衡的全向传感器网络，文献［13］提出了一种改进Voronoi图划分方法。在平面Ω上任意给定两全向节点 Sm，Sn，坐标分别为pm，pn。以两节点连线的垂线为界对平面Ω进行划分，Sm所得责任半平面内任一点t的坐标p满足如下条件：

其中dm为Sm到分割线的欧氏距离，其取值由Sm，Sn之间的欧氏距离以及二者感知圆半径rm，rn共同决定。由节点Sm与其各个相邻节点间的区间划分线所围成的凸多边形即为Sm所划分到的改进Voronoi多边形。

采用改进Voronoi图划分目标检测区域，结果如图4所示。由图4可知，当节点感知圆完全包含在其他节点的感知范围内时，则该节点将不被分配到覆盖子区间，如节点S6，此时记=Φ。在改进Voronoi图中，节点感知半径差异会造成目标区域内部分小区域不被分割给任何节点，如图中阴影部分。当节点感知半径相同时，每个阴影区域缩减为一个点，改进Voronoi图还原成标准的Voronoi图。

图4　改进Voronoi图分割

2　DDS策略

2.1节点移动策略

为最大化网络区域覆盖面积，论文提出了在DDS指导下的节点部署策略。在DDS作用下，各节点受到其所划分多边形形心引力 CPF（Centroid Pull Force）的作用，迫使节点向多边形形心移动。节点通过逐轮移动，最终均匀分布在目标区域内。

图5　节点所受质心引力

如图5所示，检测区域内节点si的位置坐标pi=（xi，yi），基于式（2）得si虚拟替代感知圆ci的圆心Oi的坐标 pOi=（xOi，yOi）。si覆盖子区间多边形V˜i的形心记为OVi，其坐标。此时si受到来自的引力CPFi的作用，表达式：

设si位于点pi和p′时对的覆盖面积分别为Ai和Ai′，若Ai＞Ai′，则si移动到新位置p′，否则，si保持不动。以此类推，网络节点受改进Voronoi多边形形心的引力作用，向所属覆盖子区间的形心靠拢，不断提高对所对应子区间的覆盖面积，实现整个网络覆盖率的提高。

2.2旋转力矩

有向节点的感应范围已不再是各向均一的圆盘，感知方向的朝向差异也影响覆盖范围，这一点在边界附近的节点覆盖中更加明显。

对网络中任一节点si，文献［6］曾给出了基于节点坐标位置的感知力矩Tib的求解方法，即

图6　节点感知方向旋转前后

对于靠近检测区域边界处的某一节点si，按照式（6）求取旋转力矩Tib，si感知方向按照Tib进行调整后，其虚拟替代感知圆的圆心将位于检测区域外，使得si无法分配到覆盖子区间，从而导致si无法再次移动。而此时si有效感知扇形区域的绝大部分位于检测目标区域外，最终造成网络绝对感知面积不升反降的尴尬，如上图6所示。

为防止节点旋转后其虚拟替代感知圆的圆心脱离检测区域，而最终导致节点移动部署策略失效的状况发生，需对节点旋转力矩Tib进行选择性使用，使用过程如下：

①若节点si到检测区域Ω任意边界线的距离不小于该节点到其虚拟替代感知圆圆心的距离，则节点感知方向旋转Tib。

②若si到边界线的距离小于到其虚拟替代感知圆ci圆心的距离，计算si按Tib旋转后ci的圆心Oi。根据点Oi的分布情况，分两种情况讨论si的旋转方案：

情况1若Oi∈Ω，则si按照Tib进行旋转。

情况2若Oi∉Ω，则节点在本轮次中不做旋转，即Tib=0。

上述修正既保证了绝大部分节点的感知视角面向检测区域外，增大整个区域的覆盖率，同时避免了个别情况下节点旋转角度较大造成其替代感知圆圆心脱离检测区域导致移动策略失效的情况。

2.3DDS步骤

针对目标检测区域Ω内随机部署的一个有向节点集合S ，为实现网络节点对Ω的最大覆盖，DDS策略主要包含两大部分：①各个节点在旋转力矩的作用下进行逐轮逐步旋转；②各个节点受形心引力的作用进行逐轮移动。为避免不必要的能量损耗，当且仅当节点移动后可提高对其所在覆盖子区间的覆盖面积时，节点才能移动，否则节点在本轮次保持原位置。DDS算法实现步骤如下：

DDS策略2-1Ω内N个传感器有向节点S=｛s1，s2，…，sN｝，节点位置坐标｛　｝pi［k］Ni=1，感知半径｛　｝ri［k］Ni=1。初始迭代k=0，最大迭代门限kmax，坐标节点移动标志flag=1，移动系数αi=0.2，每轮移动节点数目sum。2-2　whilek＜kmax&sum≠0 2-3　sum=0 2-4　forsi∈S 2-5　计算感知方向旋转力矩Tib′［k］，并按照Tib′［k］进行旋转2-6　节点感知方向旋转后，计算虚拟替代感知圆ci［k］2-7　end for 2-8　forsi∈S 2-9　flag=0 2-10　广播虚拟替代感知圆信息ci［k］，同时接收邻居节点信息，构造改进Voronoi多边形V˜i［k］2-11　计算si所受形心引力CPFi［k］%基于式（4）2-12　求取si候选位置坐标pi′［k］%基于式（5）2-13　计算si分别位于pi［k］和pi′时对V˜i［k］的覆盖面积A［k］和A′［k］2-14　ifA′［k］＞A［k］，2-15　更新节点si坐标：pi［k+1］←pi′，k←k+1，flag=1 2-16　else　保留si当前坐标：pi［k+1］←pi［k］，k←k+1 2-17　end if 2-18　sum=sum+flag 2-19　end for 2-20　end while

3　仿真实验

3.1仿真环境

为验证DDS策略的有效性，采用MATLAB进行仿真验证，并以文献［6］中的OPT算法作为对比方案。初始状态下，网络所有节点随机分布在检测区域 Ω=4 m×4 m范围内。节点感知半径范围0.4m～0.9m，感知视角范围，节点移动系数αi=0.2，迭代次数上限kmax=100。

3.2算法有效性分析

图7给出了同构和异构网络中，DDS和OPT算法部署的效果图。在图7（a）～7（c）考察了在节点数目 N=40，感知半径 r=0.6，感知视角的同构网络中DDS策略和OPT算法下的部署情况。由图7（b）可知，在OPT算法的部署作用下，节点感知扇形外接圆相对均衡地分布在目标区域内，但由于外接圆面积远大于扇形面积，产生较大的替代失真，网络最终覆盖率为66.30%，节点感知扇形之间存在严重的覆盖冗余，覆盖效果较差。DDS策略采用等面积虚拟感知圆代替感知扇形，当节点感知视角较大时，依旧可以保持较好的替代效果。各节点通过等面积替代圆确定自身移动候选位置，不断趋近自身所在子区间的形心，网络覆盖率由初始条件下的 47.32%最终提升到80.10%，如图7（c）所示。

图7（d）～7（f）比较了在节点数目N=40的异构网络中DDS策略和OPT算法的部署效果。在初始状态下，网络覆盖率为40.98%，如图7（d）。在OPT 和DDS作用下，网络可获得的最终覆盖率分别为61.76%和65.99%，此时网络中大感知视角传感器节点的数目比重变小，但等面积虚拟替代感知圆较外接圆依旧表现出较好的替代优越性。

图7　DDS和OPT作用下的网络覆盖效果其中，（a）～（c）同构，（d）～（f）异构

3.3覆盖率

为了考察异构网络规模大小对算法性能的影响，图8统计了随着节点数目变化，DDS策略和OPT算法作用下网络覆盖率的变化情况。由图中曲线可知，随着节点数目的增加，两种算法中网络覆盖率均逐渐增大，但DDS下的网络覆盖效果始终优于OPT算法，且当节点数目在小于70时，DDS策略的覆盖优越性较明显。这是由于当节点数目极少时，网络节点还不足以覆盖整个目标检测区域，OPT算法采用感知扇形外接圆进行网络部署，大感知视角节点的替代效果较差，致使OPT覆盖效果不佳，而DDS采用替代效果较好的等面积虚拟替代节点感知扇形，其部署优越性得到了处分发挥；而当节点数目较多时，两种算法均已取得较高的覆盖，网络覆盖率上升空间均较为有限。

图8　网络覆盖率随节点数目的变化

3.4能耗

在节点移动和旋转过程中会消耗大量能量，节点移动距离和旋转角度作为衡量算法有效性的两个重要指标，直接反映出算法能耗的大小。图9比较了随节点数目的增大，节点总移动距离和总旋转角度的变化情况。由图9可知，DDS策略和OPT算法下，网络节点的总移动距离和旋转角度数均随节点数的增加而增大。由于DDS策略下节点的每次移动均以能提高对其自身所在覆盖子区间的覆盖面积为前提，避免了部署过程中的无效移动，使得在相同节点数目下，网络节点移动总距离始终低于OPT算法。当节点数目高于70以后，DDS中每个节点分配到的子区间变小，节点通过较少的移动即可达到终止条件，表现为节点移动距离曲线的斜率随节点数目的增加逐渐减小。另外，由于节点每轮次的旋转角度数由其当前坐标决定，当节点位置改变较小时，其旋转角度也相应较小。

图9　总旋转角度和总移动距离随节点数目的变化

3.5节点覆盖效率

节点覆盖效率CE用于反映节点的冗余程度，定义为检测区域的净覆盖面积与所有节点感知面积总和的比值。CE越大，表明节点的利用率越高，节点冗余程度越小［14］。图10统计了DDS和OPT在特定网络节点数目下，节点覆盖效率CE随节点感知视角跨度（网络中节点最大感知视角与最小感知视角的差值）的变化情况。实验曲线表明，无论节点的数目和感知视角跨度如何变化，DDS的节点覆盖效率CE平面始终保持在OPT平面之上，体现出较好的网络覆盖有效性。当节点数目较少且节点感知视角跨度越大时，DDS覆盖效率优越性尤为明显。原因在于：DDS中等面积虚拟替代感知圆对节点视角大小变化具有较好的适应性，使得每个节点可根据自身感知范围大小获得合理的覆盖子区间。节点逐渐向自身所在子区间多边形的形心靠拢，彼此分散开来。同时，节点感知方向均面向边界，相邻节点感知方向一致，为节点相对整齐地排列部署提够了条件，有效避免了节点冗余，增强了网络覆盖。

图10　节点覆盖效率随节点数目和感知视角跨度的变化

4　总结

针对移动异构有向传感器网络，提出了一种基于虚拟替代感知圆的分布式部署策略—DDS。该策略将有向节点的旋转特性与移动特性相结合，采用基于虚拟替代圆的改进Voronoi图为每个节点构造覆盖子区间，最终确定各节点移动候选目标位置，

且所有节点移动以提高覆盖为前提，有效避免了能量浪费。仿真分析表明，DDS具有较优的网络部署效果以及较小的网络能耗，各节点仅通过邻居节点信息自行计算移动位置，避免了全局算法OPT中通信量巨大的缺陷，在大规模网络中尤为适用。

［1］Weiser M.The Computer for the 21st Century［J］.Pervasive Computing，2002，1（1）：19-25.

［2］Ma H D，Liu Y H.On Coverage Problems of Dire-Ctional Sensor Networks［M］.Berlin：Springer，2005.721-731.

［3］陶丹，马华东，刘亮.基于虚拟势场的有向传感器网络覆盖增强算法［J］.软件学报，2007，18（5）：1152-1163.

［4］Liang C K，He M C，Tsai C H.Movement AssistedSensor Deployment in Directional Sensor Networks［C］//Proc of 2010 Sixth International Conference on Mobile Ad-Hoc and Sensor Networks （MSN）.Piscataway：IEEE，2010.226-230.

［5］胡照鹏，张长森.基于矩形分区覆盖的节点确定部署策略［J］.传感器技术学报，2013，26（3）：411-414.

［6］Panditharathne C.Lin T Y，T，Chen K H.Heterogeneous Directional Sensors Self-Deployment Problem in a Bounded Monitoring Area［C］//Proc of Wireless Communications and Networking Conference（WCNC）.Cancun：IEEE，2011.623-628.

［7］Chiu-Kuo Liang，Cheng-Yen Chung，Chuan-Feng Li.A Virtual Force Based Movement Scheme for Area Coverage in Directional Sensor Networks［C］//Proc of 2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing（IIH-MSP）.Kitakyushu：IEEE，2014.718-722.

［8］秦宁宁，余颖华，吴德恩.移动异构传感器网络分布式部署算法［J］.传感技术学报，2016，29（1）：95-102.

［9］陈常超，孙力娟，韩崇，等.有向传感网分块区域p-覆盖节点调度算法研究［J］.传感器技术学报，2015，28（1）：107-114.

［10］王林，刘文远，王琳，等.基于有向传感器网络的强栅栏覆盖优化策略［J］.小型微型计算机系统，2014，35（4）：740-745.

［11］Cortés J，Bullo F.Coordination and geometric optimization via distributed dynamical systems［J］.SIAM Journal on Control and Optimization，2005，44（5）：1543-1574.

［12］Bartolini N，Bongiovanni G，La Porta T，et al.Voronoi-based Deployment of Mobile Sensors in the Face of Adversaries［C］.Proc. of 2014 IEEE International Conference on Communications （ICC）.Sydney：IEEE，2014.532-537.

［13］Stergiopoulos Y，Tzes A.Convex Voronoi Space-Partitioning for Coverage Purposes in Heterogeneous Sensor Networks［C］//Proc. of 2009 IEEE European Control Conference（ECC）.Budapest：IEEE，2009.2361-2366.

［14］方伟，宋鑫宏.基于Voronoi图盲区的无线传感器网络覆盖控制部署策略［J］.物理学报，2014，63（22）：220701（1-10）.

余颖华（1989-）女，江南大学硕士研究生，研究方向为无线传感器网络覆盖，yuyinghuahn@163.com；

李艳（1979-）女，无锡商业职业技术学院讲师，研究方向为电子通信技术，454169095@qq.com；

吴德恩（1988-），男，江南大学硕士研究生，研究方向为无线传感器网络连通性修复，1004995682@qq.com；

秦宁宁（1980-），女，江南大学副教授，研究方向为无线传感器网络覆盖，ningning801108@163.com。

A Distributed Deployment Strategy in Heterogeneous Mobile Directional Sensor Networks*

YU Yinghua1，LI Yan2，WU Deen1，QIN Ningning1，3*
（1.School of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China；
2.Institute of Internet of Things Technology，Wuxi Vocational Institute of Commerce，Wuxi Jiangsu 214153，China；
3.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education，Jiangnan University，Wuxi Jiangsu 214122，China）

Aiming at the coverage enhancement problem of heterogeneous mobile directional sensor networks，a distributed deployment strategy（DDS）based on the virtual omni-directional perception circle is proposed.DDS uses the equal-area virtual omnidirectional sensing circles to replace the sensing sectors of nodes，then structures the regional coverage subinterval for every node depending on the relationship of the positions and radiuses of different sensing circles.Finally，the candidate target location of every node is determined according to the centroid of its subinterval polygon.At the same time，making full use of the rotation of nodes，DDS gets the node's perspective direction to face the outside of the detection area.All nodes adjust their perspective directions and move reasonably to increase the network coverage continuously.The simulation results show DDS has obvious advantages in improving the coverage rate of network and enhancing the distribution balance of nodes.

directionalsensornetworks；virtualomni-directionalperceptioncircle；coveragesubinterval；coveragerate EEACC：6150P

10.3969/j.issn.1004-1699.2016.08.025

TP393

A

1004-1699（2016）08-1273-07

项目来源：江苏省“六大人才高峰”第十一批高层次人才项目（DZXX-026）；2014年国家公派高级研究学者及访问学者（含博士后）项目；国家自然科学基金项目（61304264）；江苏高校优势学科建设工程资助项目；江苏省产学研联合创新资金前瞻性联合研究项目（BY2014023-31）；中央高校基本科研业务费专项资金项目（JUSRP51510）

2015-12-17修改日期：2016-04-15