一种基于帝企鹅差分算法的WSN覆盖优化

唐菁敏，曲文博，苏慧慧，郑锦文

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

无 线 传 感 器 网 络 （Wireless Sensor Network，WSN）[1]是一种分布式网络，在能量供应和通信能力上具有一定局限性. 网络覆盖是网络获知物理环境信息的能力[2-3]，为了将传感器节点覆盖在整个任务区并优化整体网络服务质量，因此覆盖优化成为研究热点[4]. 在覆盖优化方面的算法研究近几年主要分为两大方向，一种是静态覆盖的算法，如自适应休眠（Probing Environment and Adaptive Sleeping,PEAS）算法[5]、Ditian算法[6]和地理密度控制(Optimal Geographical Density Control, OGDC)算法[7]等；另一方面是动态覆盖，主要有虚拟力算法、计算几何算法和智能优化算法.

PEAS[5]通过相邻节点来检测自身节点的工作状态，减少工作节点数目从而节约能量，但是网络的稳定性和节点能量的均衡程度并不理想. Ditian算法[6]属于分布式算法的一种，根据节点之间的几何关系来判断该节点是否冗余，在保证网络正常连通的情况下，冗余节点可以处于休眠状态，降低能耗，但是没有把周围节点对其带来的贡献考虑在内，因此准确性会降低. OGDC算法[7]覆盖率不理想，容易陷入局部最优. 智能优化算法方向的研究也有很多，博弈算法的覆盖控制[8]针对节点冗余造成的能量效率低下问题，提出了网络覆盖率和节点剩余能量组合的收益函数，保证了网络生命周期和覆盖率，但在实现完全覆盖、改进局部最优方面仍需要改善. 解决覆盖优化问题方面，布谷鸟搜索算法[9]和人工蜂群算法[10]等都有待提高. 近期提出的群体智能优化算法蚁狮算法[11]改善了局部最优的不足之处，相比于其他群智能优化算法，算法在应用解决覆盖问题时其有收敛快、节点存活时间长的优点.

本文针对优化覆盖率，基于群体智能的帝企鹅优化算法[12]提出了帝企鹅改进差分算法（Emperor Penguin Difference Algorithm，EPDEA）. EPDEA 根据帝企鹅冬季取暖的集群行为，首先确定帝企鹅集群过程中所围成的边界范围；其次根据集群过程中不同的梯度位置取暖环境的温度是不同的，定义集群不同梯度的温度；最后，计算随机的帝企鹅与集群中心帝企鹅的距离，由于集群过程中帝企鹅的位置不断变化，函数不断地对集群中心的帝企鹅位置进行更新，更新过程中结合差分进化算法，在经过变异、交叉、选择之后，对最优位置的帝企鹅更新，避免陷入局部最优.

1 节点与覆盖模型

WSN中假设传感节点的感知半径为R′，节点集合定义为Z= {z1,z2,···,zi,···,zN}，zi的位置坐标为(xj,yj),i=1,2,···,N，分布在边长为R六边形区域内，为了方便计算，将监测区域离散化为边长为S的六边形的覆盖网格，每个网格点的几何中心点即覆盖优化目标的位置. 其集合为Qj=(xj,yj),j∈{1,2,3,···,M}，其中为覆盖区域的面积[13]，节点zi与网格中心点Qj的距离定义为

当R′≤V(zi,Qj) 时，目标点被传感器节点检测到概率为p(zi,Qj)=0，此时认定Qj已经被网络覆盖.

当R′−Re＜V(zi,Qj)＜R′时，目标点被传感器节点检测到概率为

其中，Re为节点感知误差，λ 为感知衰减系数，此时认定Qj未被网络覆盖.

当R′−Re＞V(zi,Qj) 时，目标点被传感器节点检测到概率为p(zi,Qj)=1，此时认定Qj未被网络覆盖.

当目标点被多个传感器感知，此时对目标点来说联合检测概率为

所有传感器节点对待检测区域的覆盖率可以表示为

式（4）便是WSN覆盖模型的优化目标. 若待测区域中两个节点的距离小于等于感知半径，此时的通信路径默认为有且仅有一条. 保证不同的节点i，j之间连通，需定义通信路径数量Ti,j≥ 1，同时要保(证所)有节点位置要处于待测的六边形面积中，即ZQj∈M.

综上所述目标函数可以表达为

2 差分进化算法

变异算子是差分算法(Difference Algorithm,DE)算法的主要算子[14]，是将个体种群进行交叉、变异、选择产生后代个体，如果后代的个体优于父代的个体将会进行替换，在进化的过程中涉及的参数主要有种群规模NP，变异缩放因子F，以及交叉因子CR.

2.1 变异操作DE在经过差分方式后完成个体的变异，在当前种群中随机选取两个不相同的个体，将他们向量差分缩放后和另外的待变异个体进行向量运算生成新的变异种群，个体Xit的变异个体函数

2.2 交叉操作交叉操作是根据交叉因子CR， 将变异个体和父代个体带入式（7）得到试验新个体

其中，jrand是在 [1 ,D]内随机选择的整数.

2.3 选择操作DE 算 法的选择操作采用的是“贪婪”选择策略，即在父代个体和实验品个体之间选择适应度更优的个体作为下一代的种群个体，以迭代进入下一轮的操作.

3 帝企鹅算法

目前，关于帝企鹅算法在国内外研究较少，在文献[12]中对该算法进行了分析，并且与常见的粒子群算法、萤火虫算法进行了对比分析. 帝企鹅从事各种活动，如狩猎、群体觅食，是群居性动物[15].每当恶劣的气候来临，它们会挤在一起防风御寒.帝企鹅在南极极端冬季期间主要以集群的方式互相取暖来度过−40 ℃的冬季. 为了保证每只企鹅都能取暖，因此每只企鹅都在平等地做出贡献，同时它们的社交行为极为团结以及分工明确. 集群的行为[12]可归纳如下.

3.1 确定集群边界范围设定在帝企鹅蜷缩取暖的过程中所选择的位置范围在多边形的网格范围内，帝企鹅在聚集的过程中至少与两只以上的帝企鹅相邻，邻居的选择是随机的；而在帝企鹅集群过程中范围的边界是不规则的多边形，因此用围绕住帝企鹅集群的风的梯度来表示整体集群的边界，在此定义风速 γ和其梯度 α、 β ，集群边界 µ ，可表示为

3.2 计算集群层次周围的温度南极严酷的外界环境使得帝企鹅在迁徙过程中面对寒冷天气会采取集群取暖来保持温度. 若当前聚集半径d＞0.5时，其温度W=0；当d＜0.5 时，其温度W=1. 温度梯度曲线可以描述为

其中，tmax为最大迭代次数，x为当前迭代次数，温度W的表达式

3.3 计算帝企鹅间的距离在集群范围内帝企鹅间的距离表示为该个体与集群中心帝企鹅的距离，集群距离公式如下：

其中，Lep代表帝企鹅距中心距离；x表示当前迭代数；Γ 和I用于帝企鹅体积设置的影响向量因子，避免个体间的冲突；Obest(x) 为x轮最优解；Oep(x)表示当前帝企鹅的位置向量；F() 定义帝企鹅的主体社会地位，负责区别最优个体与普通个体. 向量Γ 和I计算如下：

其中 ，Bmove是移动步长参数，这里Bmove的值设置为2.5，Pacc通过比较与最优的差异来定义多边形网格精度，而 Ra n dom([0,1]) 是一个随机函数. 函数F(Γ)计算如下：

其中， ξ 和 φ 是控制参数，其值分别在（2,3）（1.5,2）的范围内能得出更好的结果.

3.4 帝企鹅位置更新帝企鹅集群中的个体通过向集群中心帝企鹅Q的方向移动更新位置信息，其位置更新如下：

其中，Oep(x+1) 代表皇帝企鹅的下一个更新位置.在迭代过程中，一旦移动者重新定位，帝企鹅的上述参数将被重新计算.

4 基于 EPDEA 的 WSN 覆盖优化

本文算法在对帝企鹅集群过程中不断对中心帝企鹅位置的寻找定位，再在定位后的集群中心帝企鹅进行差分变异中的变异交叉选择，对最优个体的位置的准确度有很大的提升，算法优化结束后输出搜索到的适应度值最优的一个解，计算目标函数中的覆盖率最大值，得到传感器节点的优化方案.EPDEA覆盖优化流程图如图1所示.

图 1 EPDEA 覆盖优化流程图Fig. 1 EPDEA coverage optimization flowchart

针对WSN的覆盖优化，EPDEA的具体步骤如下：

步骤 1初始化帝企鹅种群参数

步骤 2根据目标函数（5）计算搜索个体适应度；

步骤 3根据式（8）（9）确定集群边界；

步骤 4根据式（10）计算帝企鹅温度曲线；

步骤 5根据（12）～（16）更新帝企鹅与集群中心的距离；

步骤 6根据式（17）进行搜索个体位置更新；

步骤 7根据差分进化算法中公式（6）、（7）对搜索个体进行变异、交叉、选择；

步骤 8判断是否到达终止条件，否则返回步骤3.

5 实验仿真

5.1 仿真环境仿真情况将针对节点数N=25和N=50的两种情况下分别进行分析.

传感器节点数为N=25时，将传感器节点离散分布在蜂窝六边形中，六边形边长S=18 m，此时每个传感器的感知半径R′=4 m；传感器节点数为N=50时，将传感器节点离散分布在蜂窝六边形中，六边形边长S=24 m，此时每个传感器的感知半径与上述情况相同R′=4 m. 如图 2 (a)、2(b)分别为传感器节点数为N=25和N=50时的初始节点分布.

图 2 初始节点分布情况Fig. 2 The distribution of initial nodes

5.2 算法覆盖率对比EPDEA 在 测试区域 W SN的覆盖优化中相关参数设置如下：F∈[0.5,1],φ∈[2,2.5],tmax= 100. 图 3 (a)、3(b)分别是传感器节点数为N=25和N=50的情况下EPDEA运行后的结果，明显达到了覆盖优化的目的.

图 3 优化后节点分布情况Fig. 3 Nodes distribution after optimization

5.3 算法性能分析将 E PDEA 与 参考文献 [ 12]所提算法的覆盖优化率进行比较. 本文所采取的待测区域为六边形，以六边形的重心为坐标轴原心位置建立坐标轴，在此情况下给出不同传感器节点的位置坐标. 经过仿真对比，本文所提出的EPDEA在传感器节点数N=25的情况下，边长S=24 m，此时的待测面积为节点的分布密度约为3%，所提算法的覆盖率达到97%. 参考文献[12]中待测区域面积为50 m×50 m的正方形面积，节点数为45时的分布密度为2.8%，如图4所示，此时的覆盖率与未改进的情况下覆盖率接近重叠，当节点数达到45时，本文所提算法所达到的节点覆盖率接近98%，可见本文所提出的EPDEA中在这种情况下略占优势. 从图5的收敛程度也可以看出EPDEA的明显优势，当迭代次数为38时EPDEA已开始收敛，IGWO算法则在迭代次数80时才接近收敛状态，凸显出EPDEA一定的优势.

图 4 节点数量与覆盖率变化图Fig. 4 Change in number of nodes and coverage

图 5 平均适应度收敛曲线图Fig. 5 Convergence curve of average fitness

6 结束语

针对目前WSN中覆盖优化时遇到局部最优、精度不高和收敛速度慢的问题，提出EPDEA. 在检测区域的设置方面，六边形[16]的形状相对三角形、正方形来讲，检测到的网络特殊节点分布的可能性增大，对问题的研究的提高了多样性，一定程度上加强了算法全局搜索的能力. 该算法后期将帝企鹅集群现象中中心帝企鹅的最优位置作为与目标函数对应的解决方向，针对帝企鹅在集群现象中的受风力等不确定的因素影响边界范围，使得最后求出的最优解精准度提高. 关于该新算法的稳定性以及适用的多场景性将是下一步研究方向.