基于虚拟力算法的无线传感器网络节点部署方案

刘 琛

（江苏警官学院，江苏 南京 210031）

0 引 言

无线传感器网络[1-3]（Wireless Sensor Network, WSN）是一种由大量传感器节点以自组织和多跳方式构成的无线网络。由于无需固定的通信设施，无线传感器网络灵活性高，在气象监测、抢险救灾、目标跟踪等领域具有重要的应用价值[4-6]。

网络监测质量很大程度上取决于传感器节点的部署[7-9]。一个良好的节点部署方案可以减少网络形成的时间，提高目标区域的覆盖率，并延长网络生存时间。按照传感器节点是否可以移动，无线传感器网络节点部署方案可以分为静态部署和动态部署两类。其中，静态部署又包括确定性部署和随机性部署。确定性部署通常应用于环境已知、比较安全或网络状态相对稳定的区域，部署规模一般较小。而随机部署常应用于环境恶劣或人工无法到达的监控环境中，如战争、洪水、森林火险等灾害监测，部署规模较大。考虑到成本及网络通信等因素，动态部署通过对移动节点位置实施优化，能够在有限的节点数量下实现较高的网络覆盖率，具有十分重要的理论意义与实用价值。本文提出了一种基于虚拟力算法的无线传感器网络动态部署方案，该方案采用布尔探测模型，考虑2种典型的虚拟力，并根据节点密度预先调整距离阈值。仿真实验表明，与随机部署相比，本方案可以有效提高监测区域的覆盖率，减少覆盖空洞与覆盖冗余，具有良好的部署性能。

1 基于虚拟力算法的节点部署方案

虚拟力算法将传感器节点看成电势场中的粒子，节点与节点、节点与覆盖区域之间存在虚拟的电场力作用，受力方向由预先设置的距离阈值决定。传感器节点在虚拟力的作用下不断调整位置信息，直到满足网络覆盖率的要求。文献[10]中的虚拟力模型考虑了3种虚拟力，分别是覆盖区域与节点的吸引力、节点与节点的吸引力以及节点与节点之间的排斥力。由于节点之间既包含吸引力又包含排斥力，因此该算法容易产生局部节点过于密集的问题。为解决上述问题，本文只考虑被监测区域对节点的吸引力以及节点之间的排斥力。首先，当被监测区域未被节点覆盖时，区域对临近节点的吸引力占主导作用，使节点尽快向未被覆盖的区域移动，减少覆盖空洞。其次，对于已被多个临近节点同时覆盖的区域，节点间的排斥力占主导作用，通过移动距离过近的节点来减少覆盖冗余。

1.1 布尔感知模型

本文选用布尔感知模型实现相关功能，即传感器节点以自身坐标为圆心，以感知半径为半径构成其感知范围。感知范围内的区域认为被有效覆盖，感知范围外的区域认为未被覆盖。被监测区域的覆盖率可以表示为传感器节点已覆盖区域的面积As与监测区域总面积A的比值，定义为q=As/A。

1.2 虚拟力模型

被监测区域未被节点覆盖时，区域对临近节点的吸引力占主导作用。这一虚拟力使节点尽快向未被覆盖的区域移动，从而减少覆盖空洞。被监测区域对传感器节点的吸引力可以由公式（1）表示：

式中：ωa为吸引力系数，表征被监测区域的重要程度，对于处处均匀的被监测区域，ωa为常数；dki为被监测区域标识点K(xk, yk)与节点Si(xsi, ysi)的距离；Rc与Rs分别为传感器节点的通信半径与感知半径。根据连通性原理，通信半径与感知半径满足Rc≥2Rs。Rs＜dki表示被监测区域标识点处于节点Si的感知范围外，此时需要移动节点实现覆盖。dki≤Rc表示对于被监测区域标识点而言，只有处于通信半径范围内的传感器节点才会受到标识点的吸引力。这样的设定可以保证被监测区域总是优先考虑临近传感器节点的覆盖，避免传感器节点长距离移动。

对于已被多个临近节点同时覆盖的区域，节点间的排斥力占主导作用。此作用力通过移动距离过近的节点来减少覆盖冗余。传感器节点间的排斥力可以由公式（2）表示：

式中：ωR是排斥力系数，表征节点间排斥的程度；dij为节点Si(xsi, ysi)与节点Sj(xsj, ysj)的距离；dth为预先设定的距离阈值。仅当dij＜dth时，节点Si与节点Sj的感知范围发生重叠，节点间存在排斥力。可以看出，dij决定了节点的聚集程度。相关研究表明[11-12]，dth合适的取值范围为1.7Rs≤dth≤2Rs。

1.3 节点移动位置的计算

节点位置的更新由每一步节点所受虚拟力作用计算得到，可以用公式（3）表示：

式中：Fi是传感器节点Si受到的合力；Fx，Fy是合力分解在x轴和y轴上的分力；(xold, yold)是传感器节点的原坐标；(xnew,ynew)是传感器节点的新坐标；dmax是传感器单次移动的最大距离。

1.4 算法流程

第一步：给定被监测区域范围、节点信息参数以及预期覆盖率指标，初始化模拟环境；

第二步：计算被监测区域的覆盖率，判断是否达到预期指标，未达标转第三步，否则转第五步；

第三步：由公式（1）和公式（2）计算节点所受虚拟力的大小及方向，根据公式（3）计算节点移动位置，并更新节点坐标；

第四步：判断算法是否达到设定的循环次数，若达到转第五步，否则转第三步；

第五步：将节点移动到最终位置并输出结果。

2 仿真结果与讨论

在MATLAB R2014平台上对算法进行仿真实验。被监测区域为100×100，传感器节点数量N为40，节点感知半径Rs为10，通信半径Rc为20，节点单次最大移动步长dmax为0.1，算法迭代次数为100次，节点排斥距离阈值为dth=1.7Rs。

如图1所示，节点首先采用随机抛洒方式部署。图中圆点为传感器节点位置，数字为节点序号，蓝色圆形区域为传感器节点的感知范围，初始覆盖率为70%。

图1 节点初始分布情况

经过算法100次迭代之后，图2给出了调整后的传感器节点在被监测区域的位置分布情况。可以看到，节点已基本覆盖被监测区域，此时覆盖率为91%。

图2 算法运行后节点分布情况

在监测区域和节点感知半径不变的情况下，本文研究了覆盖率随节点个数的变化情况。如图3所示，随着节点个数的增多，覆盖率呈现同步增大趋势。当节点个数超过30之后，覆盖率增幅开始降低。这是由于理论上需要N=A/(πRs2)个节点即可实现覆盖，按照本文采用的参数A=100×100，Rs=10，对应的数值约为32。因此，节点个数小于32时，节点间的重叠部分较小，单位节点覆盖效率较高。当节点个数超过32时，节点间重叠部分逐渐增多，单位节点覆盖效率降低，导致总覆盖率增幅下降。

图3 覆盖率与节点个数的关系

3 结 语

本文针对无线传感器网络节点部署问题，以虚拟力算法思想为基础，提出一种基于虚拟力算法的部署方案。本方案相比于随机部署，可以有效提高覆盖率，减少覆盖盲区与覆盖冗余。