虚拟力导向群聚智能优化的无线传感器网络覆盖策略*

关志艳，耿 岩

(山西大学 商务学院 信息学院，山西 太原030001)

0 引 言

覆盖是网络获取物理环境信息的能力，为了有效获取整个任务区域信息，所有节点应能够覆盖整个任务区域［1］。文献［2］使用Delaunay 三角化和Voronoi 图来决定最佳性能覆盖和最坏性能覆盖，文献［3］提出了三种算法来定位移动节点，通过移动节点来填补覆盖漏洞。Zou Yi等人［4］提出了一种虚拟力算法，初始节点随机部署后，利用虚拟人工势场产生的作用力寻求节点的受力平衡来自动完善网络覆盖性能，该算法近年来得到广泛关注。文献［5］提出了一种基于节能的虚拟力算法，建立了一个多目标非线性规划模型来改善节点分布。以上基于虚拟力算法的移动无线传感器网络(WSNs)的覆盖方案大多是在基于同构节点的基础上，若在既有固定节点又有移动节点的网络中，固定节点对移动节点的虚拟力可能会限制无线传感器网络的全局优化。

针对以上研究的不足，本文结合虚拟力算法和群聚智能思想，提出了一种虚拟力导向群聚智能优化的异构移动网络覆盖策略。把调整后距离阈值的虚拟力作用于群聚智能算法的速度和位置的更新过程中，使微粒向扩大覆盖率和目标检测率的方向进化，仿真实验表明:虚拟力导向群聚智能策略能有效地实现异构无线传感器网络节点布局优化，提高网络覆盖率，且收敛速度快。

1 问题与假设

假设检测区域A 为二维平面，有两种不同类型的传感器节点，一类称为普通节点，一类称为骨干节点。普通节点携带能量少，计算能量和存储空间有限，主要任务是感知、转发数据，感知半径为rs，位置坐标为(x，y)，根据算法移动位置坐标。骨干节点能量不受限制，通信能力强，位置坐标固定，构成一个可靠的转发骨干网。而普通节点则通过多跳路由与骨干网相连，从而简化本模型中关于连通的问题，即区域A 中任一节点都至少有一条转发连通路径，全网连通。所有节点可通过GPS 或某些定位算法准确获得自身位置信息。移动节点根据本文算法能准确完成位置迁移，但移动距离不超过传感器节点最大移动距离。

无线传感器网络覆盖研究中，最重要的一个评价覆盖的标准是网络覆盖率，但目前大部分文献研究的都是整个区域的网络覆盖率，而不是单个节点的有效覆盖率。本文讨论了针对节点的有效覆盖率的计算。

定理1 在三角点阵的节点排列中，节点的有效覆盖率最大，为82.7%。

三角点阵分布是获取节点数量最优的部署方式［6］，分布中任意两个直接相邻位置点的距离满足，如图1 所示，图中节点Si，其有效覆盖率为Ci=Di/Ai，Di为节点Si的非重叠面积，Ai为节点Si的感知圆形面积，在三角点阵分布中，节点的有效覆盖率是最大的

图1 三角点阵分布Fig 1 Triangular lattice distribution

2 虚拟力导向群聚智能优化策略基本原理

2.1 虚拟力算法基本原理

虚拟力算法假设传感器节点、障碍物和热点区域均可对传感器节点施加引力或斥力。在无线移动网络中，各节点根据其所受合力的大小和方向移动，多次循环达到布局优化。因为本文研究环境是由骨干节点与普通节点组成的移动传感器网络，虚拟力主要是骨干节点对普通节点的热点引力和普通节点间的引斥力，先分析其受力公式如下:

1)移动节点受到周围节点的引力、斥力

其中，k1，k2分别为虚拟力的引力系数和斥力系数，m为节点质量，dij为节点间距离，dth为调整传感节点间作用力的距离阈值，文献［7］通过分析节点最佳布局情况下，dth=，本文也采用此距离阈值，γ1，γ2为引力增益系数和斥力增益系数，αij为两个节点间的方位角。

2)移动节点受到热点区域的引力

设骨干节点对普通节点的引力等效于来自热点区域Hotpotw 引力作用，则引力可表示成

其中，k3为节点受到热点区域的引力系数，dihot为节点与热点区域中心的距离，γ3为增益系数。一个节点所受力既有来自邻居节点的引斥力，也有来自热点骨干节点的引力，最终受力是所有在其作用力的合力

完成虚拟力分析后，设定受力阈值，各节点将原位置更新为新位置，文献［8］详细讨论了坐标更新计算方法。但值得注意的是，节点通过虚拟力移动位置，移动之后的疏密程度dth起了很大的作用，实际要找到最合适的dth，需要在实验中不断测试靠经验取值。如图2 所示，在50 m×50 m 的监测区域内，部署rs=5 的节点，部署60 个rs=5 的普通节点，16 个固定位置的骨干节点，骨干节点均匀分布，采用虚拟力算法进行普通节点适度移动，经过40 次循环后的结果如图2(b)所示，由于骨干节点对普通节点的引力，节点主要分布于固定节点附近或朝着节点密集的区域集中，这样无法实现全局优化。

图2 虚拟力作用前后对比图Fig 2 Comparison diagram before and after VFA

2.2 虚拟力导向群聚智能优化过程

群聚智能的研究始于意大利学者Dorigo 开发的蚁群算法。Kenmedy J 等人［8］通过观察鸟群的协作觅食，开发出粒子群算法。就优化而言，群聚智能已包括蚁群优化(ACO)算法和粒子群优化(PSO)算法。本文侧重于应用PSO，将每个传感器节点看做空间中的一个没有质量的微粒，在搜索空间中以一定的速度飞行，这个速度依据其本身和同伴的飞行经验进行动态调整。文献［9］详细讨论了群聚智能算法中，节点微粒的最佳位置与速度，取决于节点初始随机产生的位置与速度和进化公式。由于虚拟力算法能有效指导移动节点的分布过程，群聚智能优化策略又有很强的全局优化能力，因此，本文在群聚智能算法的进化公式中加入虚拟力的影响，其进化公式如下

其中，粒子群规模为m，vij(t)为第t 代微粒i 在第j 维的速度，w(t)为惯性权重，c1，c2为加速常数，c3为用来调节虚拟力影响的加速因子，rand()，Rand()，fj(t)为3 个在［0，1］范围内变化的随机函数，随迭代次数增加应逐渐减小，pi为微粒i 经历的最佳位置，Pg为群体中所有微粒经历的最佳位置的索引号，w(t)的计算公式为

其中，max Number 为截止代数，t 为迭代次数。由于本文是在二维空间的基础上进行研究，当j=1 即表示横向，j=2 即表示纵向，节点微粒i 的第j 维元素在虚拟力作用下的距离Vij(t)为其中，max Step 为传感器节点最大移动距离，为作用在节点微粒i 上的虚拟力节点微粒i 在x 轴、y 轴上的虚拟力分量，Fth为虚拟力阈值。

3 算法仿真与性能分析

假设在边长为50 m 的正方形监测区域内布置两种传感器节点，一种固定骨干节点，数量为16 个，组成骨干转发网，连通涵盖覆盖;一种是普通节点rs=4，据文献［8］三角点阵分布下达到理想无缝覆盖所需节点最少数量为n=60，实验初始60 个普通节点随机分布，节点分别在虚拟力算法、群聚智能算法及虚拟力导向群聚智能优化策略的作用下，进行位置更新。虚拟力算法的参数为k1=1，k2=10，k3=2，γ1=－1，γ2=γ3=1，m=1 kg，L=4 m，dth=7.46 m，max Step=4 m。群聚智能算法的参数为c1=c2=c3=1，max Number=100，微粒的速度区间［vminvmax］=k［xminxmax］=0.2×［0 50］=［0 10］。

本文所讨论的三种算法，由于涉及大量节点，三种算法分别作用于每个节点上，因此将每个节点上相关的二项式运算转换为矩阵来表达。如图3 所示，图3(a)为60 个节点随机分布图，图3(b)为在虚拟力算法作用后节点分布情况，通过实验发现固定节点对普通节点的热点引力限制了节点的移动，使节点出现局部堆积的现象，在这部分实验中削减了热点引力系数，缓解了局部节点堆积，网络的平均有效覆盖率达到80.12%。图3(c)为节点经过群聚智能算法后节点的分布效果，全局优化效果不明显，网络的平均覆盖度达到83.62%。图3(d)为节点经过虚拟力导向群聚智能优化后的分布效果，区域的覆盖盲区范围减少，说明两种算法结合对网络均匀覆盖起到有效的作用，网络覆盖率达到89.33%。

图3 三种算法分布对比图Fig 3 Distribution comparison of three algorithms

若从节点的平均移动距离来分析算法的收敛速度，当经过多次循环后节点的平均移动距离趋于0，就说明节点的移动已非常小，算法达到收敛。如图4 所示，经过实验比较，其中虚拟力导向群聚智能优化策略收敛速度最快，当循环迭代约至15 代时节点平均移动距离已稳定，而群聚智能算法需要迭代至30 代左右节点分布稳定，虚拟力算法循环至40 次左右节点分布稳定，所以，虚拟力导向群聚智能优化策略收敛性最好。

图4 算法收敛性比较Fig 4 Comparison of convergence of algorithm

4 结束语

虚拟力导向群聚智能优化的传感网络覆盖策略在原群聚智能算法位置进化公式中加入虚拟力影响因子，来提高网络覆盖率并加快算法收敛。通过大量实验验证，在随机部署节点后分别应用三种算法，结果表明:虚拟力导向群聚智能优化策略的网络覆盖率最高，且收敛也最快。但是由于本实验环境部署的节点数量是理想状态下所需最少节点，在网络覆盖率方面没有达到很高，且节点初始部署情况和公式应用中参数的设置对实验结果都有一定的影响。

［1］ Kumar S，Lai T H，Arora A.Barrier coverage with wireless sensor［C］∥Proceedings of the 11th Annual International Conference on Mobile Computing and Networking，New York:ACM，2005:284－298.

［2］ Meguerdichian S，Koushanfar F，Potkonjak E，et al.Coverage problem in wireless Ad Hoc sensor networks［C］∥Proceedings of the 20th Annual Joint Conference of the IEEE Communications Societies，New York:IEEE，2001:1380－1387.

［3］ Wang G L，Gao G H，Porta F L.Movement－assisted sensor deployment［J］.IEEE Transations on Mobile Computing，2006，5(6):640－652.

［4］ Zou Yi，Chakrabarty K.Sensor deployment and target localization in distributed sensor networks［J］.ACM Trans on Embedded Computing Systems，2004，3(1):6191.

［5］ 田一鸣，陆 阳，魏 臻，等.无线传感器网络虚拟力覆盖控制及节能优化研究［J］.电子测量与仪器学报，2009，23(11):65－71.

［6］ 刘丽萍，王 智，孙优贤.无线传感器网络部署及其覆盖问题研究［J］.信息学报，2006，28(9):17521757.

［7］ 关志艳，冯秀芳.基于虚拟力的异构节点网络覆盖增强算法［J］.计算机工程，2009，5(5):103－107.

［8］ Kennedy J，Eberhart R.Particle swarm optization［C］∥Proc of IEEE Int’l Conf on Neural Networks，Perth，1995:1942－1948.

［9］ 李 明，石为人.虚拟力导向查分算法的异构移动网络覆盖策略［J］.仪器仪表学报，2011，32(5):1043－1049.