基于人工势场方法的WSN传感覆盖率提高算法*

王 佳

(上海工程技术大学工程实训中心，上海201620)

近十几年来对无线传感器网络(WSN)的研究方兴未艾。简单地说，WSN就是由一系列小尺寸、多功能的无线传感节点组成的网络，各节点合作感知环境、并进行简单的数据处理和短距离的无线通信[1]。WSN适用于多种工业及商业环境领域，特别是在协作搜索、救援、探测及目标跟踪等任务中能发挥极大的作用。不同的性能指标评价WSN系统的不同方面，传感覆盖率是WSN中重要的性能指标之一，有效的覆盖策略能够大大地提高整个WSN系统的工作效率和使用寿命[1]。

传感覆盖率的概念是针对WSN中传感器的传感效率而提出的，主要用于描述传感节点对所在物理环境的感知情况[2]，其目的是使待测范围内的被监测点尽可能多地被节点覆盖，至少被一个传感节点覆盖，并且尽量使所有监测点均被覆盖。由文献[3]可知，目前的对覆盖率的研究主要分成以下几种方式:区域覆盖，点覆盖以及栅栏覆盖。

对传感节点进行有效的部署能显著提高覆盖率。文献[3]介绍了随机部署和提前计划两种部署方式。提前计划主要适用于环境已知的条件下，但是无线传感网络常应用在环境未知，人不适宜到达的地方，因此该方法的适用范围有限。随机部署适用于自然条件恶劣的环境中，特别是人类不易到达或对人体有害的环境。然而随机部署可能会出现部分区域节点分布过紧密，而某些区域节点相距太远的情况，这导致某些区域被多重测量而部分区域则无法被传感节点覆盖，导致传感覆盖率低。因此，在进行随机部署之后有必要对各节点位置进行调整以提高整个系统的传感覆盖率。文献[4]利用粒子群优化算法提高传感覆盖率。

目前，改善覆盖百分比主要有以下几种方法，一种方法是加强节点的传感和通信范围，这种方法对节点能量储备要求较高，整个网络的成本大幅增加，普通应用环境难以达到该要求;另一种方法是调整节点的布局，使其更加合理。通常情况下后者更易于实现，特别当WSN中部分或全部节点具有移动性时，此方法更具可操作性。

当前，许多研究工作都是围绕固定节点的WSN展开的，当固定的节点感知到其传感范围内的信息后，即将数据通过多跳的方式传输到附近的Sink节点。当节点具有移动性后，数据的传输会变得更加便捷。然而在一个WSN系统中存在过多的移动节点会导致整个系统变得过于复杂，从而容易失控。因此本文中仅将有特殊性能的Sink节点赋予移动性，使其能满足系统的需要，被一般传感节点收集的信息通过多跳的方式传输到Sink节点，其移动性加强了网络对数据处理的能力，减少网络通信压力并增强了整个网络的连通性和传感覆盖率。关于移动传感节点的一些问题不少学者已经展开研究，如文献[5]考虑了带移动Sink节点的WSN网络寿命问题;还有关于节点间通信问题的研究[6]等等。

提高传感覆盖率的有效方法之一是随机布置之后进行有效的位置调整。人工势场广泛应用于各种控制策略中，一般来说具体分为两类，一类是具有吸引能力的势场，另一类是具有排斥能力的势场，他们类似地理形态中的山峰与山谷，在其中运动的物质自然是避开山峰而向山谷移动[7]。本文将人工势场方法用于控制Sink节点移动，主要讨论如何提高覆盖率，即提高被传感节点覆盖的面积与监测的整个面积之比(ROI)，即是利用节点间的相对位置关系产生的力来推动移动节点变换位置从而提高整个网络的传感覆盖率[8]。

本文主要内容安排如下:在第1部分整体概述的前提下，第2部分介绍采用的WSN系统结构;紧接着对系统中各个组成部分间的人工势场及其产生的控制力进行描述，在此基础上给出节点移动的算法，最后第5部分依据本文提出的算法进行仿真研究。

1 系统结构

1.1 WSN系统结构

构建一个良好的系统结构是高效工作的前提，不同的网格划分方法决定了系统的结构。通常根据网格形状的不同大致可分为方形网格和菱形网格(三角形或六边形)两类[9]。本文采用正六边形网格划分方法，此方法在同样的面积中节点数更少;在保证系统的连通性及传感覆盖率等要求的前提下，整个系统能耗较小[10]。如图1所示，传感节点位于正六边形的中心，圆形是该节点的传感范围，其半径是节点传感半径r;虚实线表示的是圆形的内接正六边形，各六边形之间无重叠区域，节点之间通信路径用虚线表示。由几何知识知，任意两个节点之间的通信距离d相等且。图1显示每个节点可以和周围6个邻居节点通过单跳的方式直接通信[11]。

图1 正六边形网格划分的WSN结构

不失一般性地，当节点传感半径为r时，设通信半径为R(R=2r)，每个节点在其传感范围内收集数据，而在通信范围内传递数据。通常在WSN中，发送和接收数据消耗大部分的节点能量，因此寻找有效的通信路径显得十分必要。在正六边形网格划分结构中从一个节点到另一个节点的直线距离为(如图1所示)，虚线所示的三角形即节点间信息传输所走路径，即信息传输过程中单跳距离为。正六边形网格划分方法能较好地保持系统的连通性及传感覆盖率。因此借助此结构每个节点能直接跟周围6个节点进行信息传输(包括发送和接收数据)。

1.2 Coverage传感覆盖率

传感覆盖率的概念在文献[12]中提出，通常传感覆盖率一般定义如下:，其中C为覆盖率，Ai为节点i的有效覆盖的面积，N为节点数，A为待监测的整个区域，ri是节点i的传感半径，因此有。本文也将在此基础上进行研究。

2 人工势场方法

众所周知，异性电荷相吸引，同性电荷相排斥。由于节点间需要保持理想距离，当节点间实际距离小于理想距离时两节点看做同种电荷，相互排斥，当节点实际距离大于理想距离是看做异性电荷，相互吸引以便节点间保持理想距离。因此，在此假设前提条件下，本文将移动Sink节点与周围环境看做电荷间的电场关系，WSN中各节点间的人工势场便可以作如下描述。

2.1 移动Sink节点和普通节点之间的人工势场

在理想的系统结构中，节点的分布情况应如图1所示，因此，在初始随机部署之后可以通过移动Sink节点的位置调节来改善节点分布情况以提高系统传感覆盖率。Sink节点和普通节点之间的人工势场描述如下:

其中VI(xij)是第i个节点和第j个节点之间的势场，称为第i个节点和第j个节点之间的势能函数。xij=xi－xj表示第i个节点和第j个节点之间的距离，αI和βI是正的标量参数，d1是标量，描述节点之间理想距离，d0表示两个节点之间能相互产生斥力或引力的最大距离。

当0＜‖xij‖＜d1时，两个节点视为同种电荷，相互间产生排斥力，而当d1≤‖xij‖≤d0时，相互吸引。根据前文介绍的WSN系统结构知，通过节点之间的排斥或吸引力调节它们之间的相互位置，该势场产生的虚拟力为:

当‖xij‖≥d0时势场为零，即当Sink节点与普通节点保持理想距离d1时，或相互间距离大于d0时，互相没有排斥或吸引力，当小于理想距离时，产生排斥力。距离越小，相互的排斥力就越大;反之，节点之间距离大于理想距离为相互吸引，随着距离的增大吸引力逐渐增大，直到超出传感范围d0，d0可以根据实际情况作出调节，本文仿真中取d0=2R'+2r(R'为Sink节点通信半径)。

2.2 Sink节点间的人工势场

设r'为Sink节点的传感半径，其通信半径R'满足R'=2r'。Sink节点通信能力能达到其管辖区域的全部范围(即半径为R'的圆能覆盖其整个监测区域)，但各个Sink节点之间没有必要重复覆盖，因此，各Sink节点之间保持的理想距离应不小于2R'。

因此，对于移动Sink节点i和j之间的人工势场表示为:

其中VS为Sink节点间的人工势场，xij为第i个Sink节点和第j个Sink节点之间的距离，αs是正的标量参数。该势场产生的虚拟力为:

2.3 Sink节点与边界间的人工势场

这里考虑Sink节点和传感区域边界之间的人工势场，该人工势场定义为:

其中Vo表示节点和边界之间的人工势场，参考电磁场相关知识，κo是一正向量系数，Q为电荷总量，式ril=xi－ol中xi和ol分别为节点及边界线上某点的位置，根据电磁场的理论，该两点之间产生的力为:

fo为Vo对于xi的梯度，则为Sink节点与边界中某点之间的力。根据式(5)、式(6)知

Fo表示整个边界与Sink节点之间产生的力:

在二维空间中沿x轴和y轴的力分别为:

lx和ly分别为边界沿x轴和y轴方向的分量。

势场Vo仅仅存在于边界附近，防止Sink节点随意移动出检测范围，根据WSN系统的特点取距边界距离为r'的带型区域。

势场Vo仅存在于边缘附近以防止Sink节点移出待测区域，根据实际情况，该势场存在的范围可人为地设定，但均不影响以下的理论分析。

同理，当检测区域边缘为为曲线时，进行相应的曲线积分，也能够获得Sink节点和检测边缘之间的人工势场及其产生的力。

3 算法介绍

本文提出的算法希望利用Sink节点的移动来提高传感覆盖率，但如果在wsn网络中太多节点具有移动功能，整个网络结构变得复杂多变，反而不利于网络分析，于是在整个网络中Sink节点所占的比例应当合适，不失一般性地设系统中普通节点和Sink节点的传感半径与通信半径分别满足R=2r以及R'=2r'，则在节点分布理想的WSN系统中，Sink节点的数量与普通节点的数量之比应满足一定的数量关系以便系统更高效地完成任务。

由图2知如果按照正六边形网格划分方法部署节点，理想情况下每个节点的有效覆盖面积为传感范围圆的内接正六边形，其面积为，其中 r为该节点的传感半径。因此，若整个传感网络节点个数为n，则按照理想部署情况分析，其有效检测面积为。而通常为了保证监测数据的全面性及冗余性，因此在实际应用中，检测区域面积S和传感节点数量n需要满足:

图2 Sink节点通信范围

在按正六边形网格划分的WSN系统中，Sink节点的通信半径为2r，如图2所示，若位置理想，可以覆盖7个普通传感节点，若不考虑信息在WSN中传递的作用，即将信息传输的通信压力降到最低，由此可知Sink节点不考虑移动功能的情况下，理想的Sink节点个数应为WSN系统中总节点数的1/8，此外，根据实际系统中Sink节点属性、布置位置及网络通信情况，作一定的调整便能确定Sink节点所占总节点数量比例。

为了提高传感覆盖率的目的，整个系统应该满足以下条件:

①移动Sink节点的数量适当;

②所有的节点处理为单位质点;

③普通节点的传感半径r和通信半径R满足如下关系R=2r;

④Sink节点的传感半径为r'，通信半径为R'(R'=2r')。

为了使网络更加有效，移动Sink节点应具备以下特点:

①Sink节点的移动性;

②对Sink节点提供足够的能量以便其完成移动的任务;

③高可靠性;

④对Sink节点进行定期维护。

基于以上提到的网络条件，为提高WSN的传感覆盖率，由式(1)～式(10)，利用前文介绍的人工势场方法对Sink节点进行重新部署。在随机布置初始位置之后，利用本文介绍的方法使Sink节点移动到无节点覆盖的区域以便与该区域周边的节点进行通信，而Sink节点的移动是通过人工势场产生的力来推动的，如式(1)～式(10)所示。算法步骤如下:

①随机部署所有节点;

②检测并计算所有节点位置;

③每个节点检测其自身邻居的位置(在其通信半径内的节点为其邻居);

④根据式(1)～式(10)，Sink节点计算其承受的综合人工势场;

⑤根据人工势场产生的力使Sink节点移动;

⑥Sink节点是否到达平衡点位置，是，转到步骤7，否则到步骤4;

⑦结束。

4 仿真实例

在大小为100×100的正方形区域中，当采用传感半径r=10，通信半径R=20的传感节点时，由式(11)知共需节点40个左右，首先随机部署这40个节点，其中包括5个移动Sink节点(占节点总数的1/8)，Sink节点传感半径r'=2r=20，在式(1)、式(10)的控制下，Sink节点进行移动，直至平衡位置。在图3和图4中各节点传感半径r=10，通信半径R=20，用实心圆及其圆心分别表示普通节点的传感半径及当前位置，Sink节点传感半径、通信半径及其位置用虚线圆及其圆心表示。Sink节点收集其通信范围内的一般节点信息，并做简单处理。图3为初始随机部署的情况，图4为利用本文提出的人工势场控制方法调节后整个系统的分布情况。从仿真结果能看出来通过Sink节点的移动能有效提高系统传感覆盖率。

图3 随机部署效果

图4 移动Sink节点后的分布情况

由于仿真中节点初始位置是随机的，因此每次仿真结果并不相同，本文经过多次仿真求平均值来进行整体控制效果比较，统计结果如下:

平均覆盖率 Sink节点移动前 Sink节点移动后1 次 62.5% 83.3%10 次 58.7% 82.5%30 次 60.8% 83.9%50 次 61.3% 82.7%

5 总结

人工势场方法具有描述环境能力强的特点，能处理各种不同物体之间的相互关系，因此可以借助此方法控制移动节点到理想位置。本文正是利用此方法对WSN系统中Sink节点进行控制以提高系统的传感覆盖率。采用此方法不必事先预知环境信息，在短时间内能达到满意的控制效果。仿真结果证明了此方法的有效性。

在整个系统中同时存在多个不同的人工势场，因此各势场间的协调性需要通过参数的调整来完成，根据具体实际情况在强调某种势场的情况下兼顾其他势场的影响，最终达到整体协调，改善系统性能的目的。

[1]Ghosh A，Das.Coverage and Connectivity Issues in Wireless Sensor Networks:A survey[J].Pervasive and Mobile Computing，Vol.4，No.3，June 2008:303－334.

[2]Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage Problems in Wireless Ad-Hoc Sensor Networks[J]IEEE Infocom 2001，Vol 3，April 2001:1380－1387.

[3]Cardei M，Wu J.Coverage in Wireless Sensor Networks[M]Handbook of Sensor Networks.CRC Press，United States of America 2005:10－20.

[4]林祝亮，冯远静，俞立，无线传感网络覆盖的粒子进化优化策略研[J].传感技术学报，2009，22(6):873－877.

[5]Denkovski D，Mateska A，Gavrilovska L.Extension of the WSN lifetime through controlled mobility[C]//Seventh International Conference on Wireless On-demand Network System and Services(WONS)，Kranjska Gora，Slovenia，2010:151－156.

[6]Eylemekici，Yaoyao Gu，Doruk Bozdag.Mobility-Based Communication in Wireless Sensor Networks[J].IEEE Communications Magazine，July 2006:56－62.

[7]Naomi Ehrich Leonard，Edward Fiorelli.Virtual leaders，artificial potentials and coordinated control of groups[C]//Proceedings of the 40th IEEE Conference on Decision and Control 2001:2968－2973.

[8]Howard A，Mataric M J，Sukhatme G S.Mobile sensor network deployment using potential fields:A distributed scalable solution to he area coverage problem[C]//International Conference on Distributed Autonomous Robotic Systems(DARS02)，Fukuoka，Japan，June 2002:299－308.

[9]傅质馨，徐志良，黄成，吴晓蓓，无线传感器网络节点部署研究[J].传感器与微系统，2008，27(3):116－120.

[10]赵国炳，陈国定，张奇伟，一种无线传感器网络覆盖优化方法[J].机电工程，2009，26(6):80－82.

[11]王佳，WSN中基于改进蚁群算法的移动Agent路径规划[J].传感技术学报，2011，24(4):609－613.

[12]D.W.Gage.Command control for many-robot systems[C]//AUVS－92，the Nineteenth Annual AUVS Technical Symposium:22－24.