基于能量优化的三维无线传感器网络覆盖算法*

孙爱晶，朱鑫鑫，王 磊

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

0 引 言

节点部署在无线传感器网络(wireless sensor networks,WSNs)中是十分重要的一环，拥有不可替代的作用，而对于WSNs中的能量问题,路径寻优问题以及定位问题等均有重要的影响。如何能在保证网络的覆盖以及提高网络的连通容错率的同时延长网络的使用寿命在现阶段受到了很多研究者的关注[1]。文献[2]从WSNs算法的部署方式，监测目标以及节点是否移动等方面进行分析对比，并给出了WSNs算法的应用关键点以及未来发展趋势。文献[3]通过对比适于空间镶嵌的几种凸多面体，得出截角八面体在一定条件下的覆盖效果最优。文献[4]提出了一种基于空间镶嵌的三维WSNs覆盖机制，并在覆盖的基础上考虑了漏洞检测与修复的问题。文献[5]对三维曲面进行网格划分后在引入差分进化算法来对传感器节点的位置坐标进行优化。文献[6]提出了利用传感器节点半径可调的机制来完成三维空间的覆盖。文献[7]提出了基于方向梯度的三维表面覆盖连通方法。由于前提环境的设置，只针对三维环境下的表面进行了覆盖。文献[8]提出了基于网格的分布式能量有效k覆盖多连通部署算法。该算法考虑了节点在分布式部署情况下的通信半径问题，但并未应用在三维场景下，在实际应用中仍然存在一定的局限。

针对以上问题，本文提出了一种基于能量优化的三维空间镶嵌WSNs覆盖算法。以截八面体为子单元填充三维空间，将传感器节点部署在子单元的顶点上，并在节点部署时采用休眠与唤醒策略来减小节点的能量消耗，且在休眠与唤醒策略中加入了改进后的人工蜂群算法以改善休眠与唤醒算法中节点的选取问题。

1 问题模型分析

本文以水下WSNs和地下WSNs为研究背景，假设网络在部署时：所有传感器节点在初始阶段的参数一致，拥有相同的特性。目标空间为水下立方体。

1.1 节点感知模型

在二维WSNs网络的覆盖模型中，节点感知模型常使用布尔感知模型。在三维WSNs中，理想状态下希望节点的感知范围可以呈现截角八面体的形状，由于现实因素，在此假设传感器节点的感知模型为球体模型[9]。

定义k覆盖：在水下目标区域中，假定任意某点同时被k个传感器监测到，则表示该区域中任意某点达到k覆盖，可称该区域被k覆盖。

1.2 问题描述

在三维目标空间中进行截角八面体的空间镶嵌，如何在保证目标空间的k覆盖，并在保证k覆盖的条件下，如何对工作中的传感器节点进行协调以减少节点的能量消耗。

2 节点部署

2.1 填充子单元的选取

利用空间镶嵌理论来完成三维WSNs的k覆盖，首先要考虑的就是选取哪一种凸多面体作为填充子单元。在三维目标空间的覆盖中，空间镶嵌方法中存在一种多面体的镶嵌以及多种多面体的混合镶嵌，而多种多面体的混合镶嵌中，不仅多面体的范围难以确定，并且混合多面体的组合十分复杂，会造成计算资源的浪费。由此在本文中研究单一的多面体镶嵌问题。

目前在使用空间镶嵌方法进行空间填充的方向上，当传感器节点部署在凸多面体的形心位置时，截角八面体能够以最少的节点完成网络的全覆盖[10]。

2.2 节点的部署策略

本文中针对三维目标空间采用分层分布式节点部署，如图1。

图1 分布式结构

在目标空间的镶嵌中，采用截角八面体作为填充多面体，将节点部署在填充单元的各个顶点处，由此会产生共用节点。共用节点由外而内按照目标空间镶嵌的维数进行各不相同的标记。内层的节点因感知范围而覆盖到外层节点，所以，对节点进行休眠与唤醒策略以减小能量的消耗。其中，第一层的共用系数标记为1,2,3；第二层标记为3，4；第三层以后标记为4。

本文节点部署的基本思路是：首先根据目标区域计算所需镶嵌子单元个数,如式(1)，将目标空间划分为k层，对每一层的节点进行部署，遍历每一层，直至完成部署

(1)

(2)

文献[11]首先将目标区域网格化，再部署传感器，不仅可以估算覆盖率还可以定位传感器。本文在节点部署时，对此网格化思维进行扩展，将其用于三维空间中，对目标空间进行k覆盖的检测。将目标空间网格化，以节点感知半径为半径进行网格点k覆盖的判断，从而达到目标空间的k覆盖。如果依靠顶点上部署的节点未能达到k覆盖，则在填充子单元内部均匀部署L个节点，以满足k覆盖的要求。如果节点部署大于k值。则首先进行休眠，其次在节点之后的工作中进行有目标的唤醒，以延长目标网络的工作时长。

2.3 节点部署位置

在实现网络全覆盖的情况下，以截八面体作为子单元进行空间填充，并将节点部署在子单元形心位置时，节点能够以最少的数目完成目标空间的覆盖。

当要求网络的覆盖度达到k时，节点如果在形心位置，则需要在子单元内部重新部署k-1只传感器，导致节点个数较多。在保证k覆盖的前提下，本文选择将节点部署在填充单元的顶点上，并将节点采用确定性部署的放置方法来保证节点在能量耗尽前达到全覆盖以及k覆盖。

3 基于人工蜂群的改进休眠与唤醒算法

3.1 改进后的休眠算法

文献[12]提出了一种冗余节点休眠算法(sleeping schedule for redundant sensors，SSRS)。算法根据传感器节点s的邻居节点对s覆盖范围内的任意子单元顶点之外节点进行决定参数的判断。本文中针对目标区域的k覆盖要求对冗余节点的判断进行了改进。

定义1感知强度(SI): 表示某传感器节点对于感知范围内的不同位置的点产生的感知大小，感知大小由近而外递减，对此设定SIsen为感知阈值。当感知强度大于感知阈值时能够被感知到，感知强度小于感知阈值时不能够被感知。

定义2合作感知强度(CSI):假设对于A点有M只传感器可以感知到，感知强度各不相同，对于A点所拥有的感知强度为所有感知强度之和，即为合作感知强度。

定义3感知贡献(SC)：在A点周围的M只传感器中，H点对于A点在所有点中的感知比例即为感知贡献。

定义4决定参数(DP)：假定A点有M只传感器覆盖到，如果M只传感器中的一个节点L点去掉，A点所拥有的合作感知强度CSI>k×SIsen，则L点可以处于休眠状态，将DP值置为1，否则置为0。

节点的休眠思路描述如下：1)首先将所需部署的目标空间分为k层，每一层设定局域估计器，用来接收每层的数据传输。2)计算首层节点的感知贡献，按照感知贡献对除去子单元顶点位置的节点排序进行节点休眠。当节点的感知贡献排序较低且去掉该节点时对整体的覆盖度不产生影响，则对该节点进行休眠。3)更新工作节点的DP值，并进行下一层的节点休眠。4)判断层级是否遍历完成，如果未完成重复步骤(2)至步骤(3)。

3.2 基于改进人工蜂群的唤醒算法

3.2.1 唤醒算法

传感器节点在工作过程中，为了减小能量的消耗，选取合适的传感器节点进行休眠，会造成某些位置无法达到k覆盖，此时采用唤醒算法将合适的节点进行唤醒以达到网络的k覆盖。

为了均衡传感器节点的使用寿命，对传感器节点的能量进行等间隔分段，这种分阶段的算法称为分阶段唤醒策略(phased waking-up strategy，PWS)。假设将节点寿命分为相等的N个阶段，则每段工作时间为T/N。

节点的唤醒策略描述如下：1)将传感器节点的能量值分为N个阶段，当每一次被唤醒时，对应的能量值减1，当N为0时能量耗尽。2)在出现节点的能量消耗需要休眠的时候，此时不能满足k覆盖，随机选择节点唤醒，如果该节点在当前工作阶段未工作，唤醒此节点，否则重新选择节点。3)循环执行步骤(2),直至传感器节点的能量耗尽。

3.2.2 改进后的人工蜂群算法

人工蜂群(ABC)算法不仅在数值优化问题的收敛效果相比较其他几种智能算法效果更好，并且该算法便于理解，过程简单，具有较强的稳健性。但此类算法易陷入局部最优。所以，本文中对该算法将搜索方法以及蜜源更新公式与最坏蜜源解进行改进[13]。

改进1：将轮盘赌方法进行调整

鉴于轮盘赌方法在选择方面会导致种群的多样性降低，从而使收敛过快。借鉴于蚁群算法中的信息素概念。在此处加入灵敏度与信息素。将某个蜜源位置的灵敏度与信息素进行比较，若灵敏度小于信息素，则更新新的蜜源，当灵敏度大于信息素时，保持原有蜜源位置。

改进2：蜜源更新公式的改进

在蜂群算法中，为了减小跟随蜂的搜索区域，避免陷入局部最优，在跟随蜂与引领蜂之间引入相互引力概念。

对于第i只引领蜂与第k只引领蜂之间的相互引力为

(3)

式中G为万有引力常数，F(xi)为第i只引领蜂的适应度值,F(xk)为第k只引领蜂的适应度值。

跟随蜂蜜源的更新公式变为

(4)

式中N为蜜源总数,J为第i只引领蜂或第k只引领蜂的分量。

改进3：最差蜜源的替换

在算法的工作过程中，会有最差蜜源产生，这会降低算法的收敛速度，针对最差蜜源，进行蜜源更新，选取更好的蜜源位置，以提升收敛速率。更新蜜源公式为

x′ij=xijL+xijU

(5)

(6)

3.3 融合后的算法

PWS算法虽然通过对传感器节点的能量进行划分以合理分配节点的生命周期，并且分阶段唤醒中会对除共用节点之外的节点进行随机选取，这容易使网络陷入局部最优的问题，故本文中加入改进后的人工蜂群(IABC)算法对PWS进行优化，即IABCPWS算法,针对唤醒过程中的节点选取进行有目标的选择，能够使在唤醒节点时得到全局最优解。

改进后的步骤如下：1)针对水下三维目标空间，将其划分为k层，并对传感器节点的使用寿命进行同等划分。定义一个能量阈值E，作为节点唤醒的标准。2)比较当前阶段能量阈值与传感器节点的能量，如果小于阈值节点休眠。3)使用改进后的人工蜂群算法在唤醒节点的选取上，选取更优的节点位置以达到k覆盖。4)重复执行步骤(3)，直到节点的能量耗尽。

4 仿真实验与性能评价

4.1 仿真参数设置

假设在300 m×300 m×300 m的立方体区域内部镶嵌截角八面体，并部署传感器节点。仿真参数如表1。

表1 参数设置

4.2 仿真结果分析

图2比较了本文算法中引入人工蜂群算法与原始PWS算法传感器的覆盖率变化。其中横坐标代表了传感器网络工作的阶段，纵坐标代表网络的覆盖率。在初始化阶段，PWS算法由于随机唤醒节点，不考虑所唤醒节点产生多少作用，虽然覆盖率很高，但同时造成节点能量损耗严重。而本文算法在唤醒节点时采用人工蜂群算法进行选择，虽然在初始阶段覆盖率会有不足，但延长了整个网络的工作时长。

图2 覆盖率变化

图3比较了本文算法与原始PWS算法在节点工作的能量变化。其中横坐标代表了传感器网络的工作阶段，纵坐标代表了节点剩余能量。PWS算法的能量呈线性下降，能量消耗极快，对于延长节点的生命周期效果并不好。在引入人工蜂群算法有序的挑选唤醒节点后，可以看到节点的能量下降趋势有明显缓解，并延长了节点以及网络的生命周期。

图3 节点能量变化

5 结 论

本文提出了一种改进的节点休眠与唤醒算法，并将其实现在三维目标空间中，经过比较，延长了三维空间中WSNs的生命周期以及保证了目标空间的k重覆盖。下一步工作将引入WSNs的连通性问题，针对本文模型的连通性算法进行研究。