基于特征点集GABC算法的WSN覆盖优化

侯义飞，杨 勇

(河南工业大学电气工程学院，河南 郑州 450001)

0 引 言

网络覆盖是无线传感器网络(Wireless Sensor Networks, WSN)技术研究中的一个基本研究问题，其反应了WSN对物理世界的监测能力[1]，而覆盖率是衡量网络覆盖质量的重要标准之一。在实际应用中，应当使目标区域的覆盖最大化，尽量使其做到覆盖无死角[2]。通常，传感器节点都是随机抛洒在监测区域内的，容易造成传感器节点分布不均匀，导致覆盖效果不理想。通过覆盖优化算法对初始部署的节点位置进行调整，可以取得很好的覆盖效果[3]。目前，移动节点覆盖算法有虚拟力算法[4]与群体智能算法等。

近年来，有许多学者将群体智能算法成功应用到WSN覆盖控制中[5-6]。文献[7]将人工鱼群算法应用到WSN覆盖领域中，虽然网络覆盖有所提高，但是算法收敛速度较慢。文献[8]将粒子群算法应用到WSN覆盖优化中，有效提高了网络的覆盖率，但容易陷入局部最优。人工蜂群算法是一种新兴的群智能算法，结构简单，参数少，有着分层协作机制等优点，被广泛应用于WSN覆盖优化问题中[9-10]。文献[11]提出了一种改进人工蜂群算法，改进侦查蜂搜索公式，加快算法收敛速度。文献[12]利用分层机制改善人工蜂群算法的性能，但算法进行局部搜索时需要大量迭代，使搜索速度变慢。文献[13]利用基于反向学习策略的人工蜂群算法优化部署移动传感器节点，可以减少算法的迭代次数，但是容易陷入局部最优解。

为了提高WSN的覆盖性能和网络的覆盖率，并且在求解覆盖率时可以减少计算量，本文将特征点集和全局最优解引入人工蜂群算法中，提出一种基于特征点集全局最优解人工蜂群算法(Gbest-guided Artificial Bee Colony, GABC)，并将其应用到WSN网络覆盖领域。通过仿真实验，重点对比了标准ABC (Artificial Bee Colony)算法和GABC算法在网络覆盖上的性能。

1 网络模型建立

1.1 节点感知模型

为了使节点监测更接近实际的情况，本文选取的节点感知模型为概率感知模型[14]：

(1)

其中：m是区域内任意一点；si是第i个传感器节点；d(si,m)表示si与点m的欧氏距离；Rs是感知半径，Re(0≤Re≤Rs)是传感器监测的一种不确定程度；α1、α2、β1、β2是传感器节点本身相关的参数；λ1=Re-Rs+d(si,m),λ2=Re+Rs-d(si,m)。

网络中多个传感器同时监测到同一点m的联合覆盖概率可以用下式表示：

(2)

其中，S表示传感器节点集合。

1.2 相关定义与定理

如图1所示，m1、m2是相距为L的2个被监测点，区域内N个传感器节点对m1和m2的联合覆盖率分别是ρ1和ρ2。当N=1时，在以m1为圆心、m1A为半径的圆周上任意部署传感器节点，传感器节点监测到点m1的覆盖率均为ρ1。

图1 定理1示意图

定理1[15]如图1所示，当N=1且节点在A处，A为m1、m2连线上与圆m1相交距m2更远的那一点，ρ2取最小值ρ2min。

定理2[16]假设点m是区域内任意一点，如果其覆盖率满足ρ=f1(ε,L)时，在以点m为圆心，L为半径的区域内的点的覆盖率都大于等于ε。其中，ε为概率阈值。

(3)

通过定理1和定理2可以得到区域的特征，可以分析特征点集来等价分析整个区域的性能。通过分析传感器节点对特征点的覆盖就可以知道传感器节点对整个区域的覆盖情况。

2 基于特征点集全局最优解人工蜂群算法

2.1 人工蜂群算法

人工蜂群算法是Karaboga等人[17]根据蜜蜂的采蜜行为提出的一种群体智能算法。它与粒子群算法和遗传算法相比较具有结构简单、参数少等优点，有着广泛的应用。人工蜂群算法将蜂群分为雇佣蜂、跟随蜂和侦查蜂[18]。雇佣蜂和跟随蜂的任务是在蜂巢附近寻找优质蜜源，而侦查蜂的任务是观察是否陷入局部最优解。雇佣蜂的个数和跟随蜂的个数与蜜源的数量SN相等，算法在D维空间中搜索。每个蜜源的位置表示问题的一个可能解，用适应度函数对每个蜜源进行评价[19-21]。

雇佣蜂和跟随蜂按照公式(4)寻找新蜜源：

(4)

其中：i∈{1,2,…,SN};j∈{1,2,…,D};rij是区间[-1,1]上的随机数；k∈{1,2,…,SN}，且k≠i。

在蜜源初始化或每个蜜源被分配给每个雇佣蜂后，蜜源的优劣由适应度来评价，用公式(5)来计算每个解的适应度。若求解最大值问题，则可取目标函数作为适应度函数。

(5)

其中，Fi为第i个蜜源的适应值，fi为第i个个体对于优化问题的目标函数。

标准ABC算法采用贪婪选择策略保留优秀个体的解，每个蜜源被选择的概率为：

(6)

跟随蜂选择雇佣蜂所搜索的解，然后跟随蜂通过公式(6)来计算蜜源被保留下来的选择概率，保留雇佣蜂阶段较好的解，用来提高解的质量。

如果搜索次数到达limit值后，蜜源的质量没有得到提升，雇佣蜂就会放弃对该蜜源的搜索，角色转变为侦察蜂。加入侦查蜂步骤的目的是为了避免人工蜂群算法陷入局部最优解。侦查蜂将随机生成新的蜜源用来代替原来的蜜源，计算如下[22]：

(7)

2.2 全局最优解人工蜂群算法

在人工蜂群算法中，雇佣蜂和跟随蜂都会随机产生新的解，算法容易出现收敛速度慢和早熟的问题。因此，人工蜂群算法有很大的改进和提高空间。

受粒子群算法的启发[23]，为了提高人工蜂群算法的开发能力，利用全局最优解[24]来引导候选解的产生，将公式(4)的搜索方程修改为：

(8)

其中：i∈{1,2,…,SN};j∈{1,2,…,D};rij是区间[-1,1]上的随机数，控制领域范围；k∈{1,2,…,SN}，且k≠i;xgj是蜂群当前最优解的第j维值；ψij是[0,C]间的随机数，C为正数，C取1.5。

通过加入全局最优项，GABC算法在搜索最优解的时候，可以朝着最优解的方向迅速靠拢，使算法很快找到最优解，加快算法的收敛速度和避免算法出现早熟现象。

2.3 特征点集的GABC算法优化无线传感网

2.3.1 特征点选取

图2 特征点的示意图

2.3.2 网络覆盖的优化目标函数

GABC算法求解网络覆盖率用的是基于网格点来求解的，要想得到接近实际的覆盖率，需要将网络划分成稠密的网格点。其中，网格点的数量远远大于特征点的个数，这样会导致计算量很大。因此，利用特征点集来求解网络中的覆盖率，可以有效地减少计算量。本文用特征点集优化覆盖公式(9)求解最大覆盖率。

Maximizeρ

(9)

其中：ROI是被监测区域；M是特征点数量；N是传感器节点数量；m是区域内任意一点；pj是第j个特征点；d(m,pj)是区域内任一点m到特征点pj的距离；FPS是特征点集(Feature Point Set)；ρi,pj是第i个传感器节点对特征点pj的覆盖率；ρpj是所有节点对pj的联合覆盖率；ρ是所有pj的覆盖率ρpj中的最小值；第1个条件表示区域内任一点都至少被一个特征点包络。

将无线传感器网络性能指标中的所有特征点的覆盖率最小值作为适应度值，因此，无线传感器网络的适应度函数的计算方法为：

ρ=min{[ρpj]M×1}

(10)

无线传感器网络覆盖优化，最终的目的是使网络的覆盖率最大，也就是说，求解适应度函数ρ的最大值。

2.3.3 算法整体流程

将GABC算法应用到无线传感器网络领域，用来提高网络的覆盖率。其中种群中每个个体就是传感器节点的位置，适应度值代表网络覆盖率。适应度函数为公式(10)，其目的就是让公式(10)取得最大值的最佳位置。算法的具体实现步骤为：

Step1初始化参数：目标区域大小、将区域划分成的若干特征点、传感器节点个数、感知半径Rs的大小、蜜源数量SN、总的蜜蜂数量BN，其中雇佣蜂的数量和观察蜂的数量相等且均为BN/2。设置最大迭代次数MaxCycle，迭代次数iter=0，最大领域开采度limit，随机生成BN/2个蜜源位置，设置一只侦查蜂。

Step2对每个随机生成的SN个初始解，根据公式(9)与公式(10)计算每个蜜源的覆盖率。

Step3选出传感器节点最优位置。

Step4在雇佣蜂阶段，雇佣蜂按照公式(8)在邻域内搜索新的解，并对新解计算覆盖率。然后对边界进行处理，使其不超过监测区域的边界。

Step5比较新产生的解的覆盖率与原来解的覆盖率的大小，取较高的覆盖率，并记录此时解的位置。

Step6在跟随蜂阶段，跟随蜂按照公式(6)计算选择概率Pi。跟随蜂根据选择概率选择较好的蜜源，并按照公式(8)在蜜源邻域内寻找新的解，同样计算比较新旧解的覆盖率大小，取较高的一个，并记录此时解的位置。

Step7如果一个蜜源的位置经过limit次均未更新，则该位置的雇佣蜂变为侦查蜂，按照公式(7)随机产生新解。

Step8记录到目前为止的最优解的位置。

Step9判断iter与MaxCycle的大小，如果iter≤MaxCycle，则跳转至Step4，否则算法终止运行，输出最优解。

3 仿真实验与分析

3.1 无线传感网覆盖优化仿真实验设置

假设监测区域为100 m×100 m的平面区域，每个传感器的监测半径Rs=10 m,Re=3 m，传感器节点选用公式(1)的概率感知模型。其中，α1=β1=β2=1,α2=0。算法在Windows 10操作系统、MATLAB2014b仿真平台上实现。算法最大迭代次数为300次，limit值为100，蜜源数SN为30，维数D为传感器节点的个数。覆盖阈值ε=0.9500，最大特征点距MFPD≤8.0704，取整数8。

3.2 无线传感网覆盖优化性能比较

取传感器节点个数为30个时，用2种算法分别对网络中节点进行优化。GABC算法和ABC算法分别运行10次，取每次运行的覆盖率的平均值绘制成曲线图，如图3所示，最终得到算法部署后的传感器节点分布图。30个传感器节点在ABC算法和GABC算法优化的每个特征点的覆盖率对比图，如图4所示。

图3 节点平均覆盖率变化曲线

从图3可以看出，与ABC算法相比，GABC算法明显地能够提高网络的覆盖率。

图4 2种算法优化特征点覆盖率对比图

从图4可以看出，GABC算法传感器节点对每个特征点的覆盖率绝大多数都比较高，ABC算法得到的每个特征点覆盖率整体上要劣于GABC算法。研究对特征点的覆盖可以等效研究对整个区域的覆盖，2种算法对特征点的覆盖可以反映出，GABC算法比ABC算法可以提高网络的覆盖率。

30个传感器节点随机初始分布图如5所示。用ABC算法部署传感器节点后，网络中节点分布图如图6所示。用GABC算法部署传感器节点后节点分布图如图7所示。从最终分布图可以看出，GABC算法可以使传感器节点分布得更均匀进而提高网络的覆盖率。

图5 随机部署节点分布

图6 ABC算法部署后节点分布

图7 GABC算法部署后节点分布

由于研究网络中传感器节点对特征点的覆盖相当于研究网络中传感器节点对整个区域的覆盖情况，这样可以减少对覆盖率的计算量，因此，可以通过研究传感器节点对特征点的覆盖率，反应出传感器节点对整个网络的覆盖率。在30、50、70个传感器节点，GABC算法和ABC算法重复运行10次，对所有特征点覆盖率的统计结果如表1所示。

表1 随机试验下覆盖率的统计结果分析

从表1中不同节点数量下对网络中所有特征点的覆盖率统计的结果，可以看出，GABC算法对特征点的覆盖率都好于ABC算法。从均值和标准差可以看出，GABC算法在覆盖性能和稳定性都比标准ABC算法更好，说明GABC算法可以有效提高网络的覆盖率。

4 结束语

本文通过对特征点集概念的研究，将传统的区域覆盖问题转化成对特征点的覆盖问题，提出了一种基于特征点集的GABC算法来优化WSN问题。该算法减少了求解覆盖率的计算量，改善了ABC算法容易陷入局部最优解的不足，最后通过仿真实验表明基于特征点集的GABC算法可以有效提高网络的覆盖率。今后将对特征点集的选取方式是否对覆盖率有所影响进行进一步的研究。