改进人工蜂群算法的WSN覆盖连通优化

张 浩，龙道银，覃 涛，王 霄,3，杨 靖,3+

(1.贵州大学 电气工程学院，贵州 贵阳 550025；2.中国电建集团贵州工程有限公司 创新事业部， 贵州 贵阳 550025；3.贵州省科技厅 互联网+协同智能制造重点实验室，贵州 贵阳 550025)

0 引 言

无线传感网络(wireless sensor network，WSN)通过节点间的相互协作，可向用户提供实时的监测数据，目前已被广泛应用在多个领域[1,2]。节点部署是影响WSN性能的重要环节，其中区域覆盖率和连通性是节点部署中的两个重要指标。

当前，群体智能算法在WSN部署优化中得到广泛应用[3-11]。文献[3]提出了基于蚁狮算法的节点覆盖优化策略，利用自适应收缩边界对算法进行改进，提高了网络的覆盖率。文献[4]提出了一种基于粒子群算法的覆盖控制策略，考虑了网络的覆盖率与能耗，但覆盖率不够理想。文献[5]提出了一种基于生物地理学优化算法的覆盖连通策略，能有效获得位置较好的节点部署位置，但算法的复杂度过高。文献[6]提出一种基于花朵授粉算法的节点覆盖优化，但节点均匀度不够理想。文献[7]利用多策略改进的灰狼算法去提升监测区域的覆盖率，但存在明显的覆盖空洞。文献[8]提出了一种基于改进鲸鱼优化算法的节点覆盖策略，但算法的复杂度过高。文献[9]将贝叶斯算法的预测思想引入到人工蜂群算法中，提高了不同监测区域的覆盖率。文献[10]利用改进的虚拟力算法增强了无线传感网络的覆盖率，同时利用Delaunay三角检测覆盖空洞并进行修复，但网络的能耗较大。文献[11]提出了一种节点多目标安全连通部署优化算法，但部分区域的覆盖率不够理想。

针对上述问题，为有效兼顾网络的覆盖率及连通性，提出了一种基于精英解引导下动态混合搜索人工蜂群算法(dynamic hybrid search based artificial bee colony algorithm，DHSABC)的节点部署策略。将节点的部署过程类比为蜂群寻找最优蜜源的过程，在相同实验条件下，与其它文献中的算法进行仿真对比，验证改进后算法在节点部署上的有效性。

1 问题模型分析

假设在面积为M×L m2的WSN监测区域内，随机抛撒了n个同构传感器节点，其中节点集合为S={S1,S2,…Si…,Sn}，Si位置坐标为 (xi,yi)，i=1,2,…,n， 节点的感知半径均为Rs，通信半径均为Rc。为简化计算，将该监测区域离散化为m×l个单位正方形区域，每个子区域的中心坐标就是节点的覆盖目标中心点的坐标集合为Cj=(xj,yj)，j∈{1,2,…,m×l}。 若中心点Cj与任意一个节点距离小于或等于感知半径Rs，则认定Cj被节点覆盖，节点Si与中心点Cj的间距定义为

(1)

节点感知模型为布尔感知模型，中心点Cj=(xj,yj) 被节点Si感知的概率p(Si,Cj) 定义为

(2)

中心点Cj被所有节点联合感知概率定义为

(3)

该区域的覆盖率Cov为感知节点集合S所对应的联合感知概率之和与区域内中心点总数的比值，定义为

(4)

Cov越大表示对区域的覆盖率越高，对区域监测的性能越好，故可以得到第一个目标函数为

(5)

在无线传感网络中节点覆盖问题中，还应该考虑节点之间的连通性，为了保证网络连通的可靠性，每个节点至少应与两个或两个以上的节点能够连通。假设两个节点之间的距离在通信半径以内，则认定两节点间能够连通，故节点Si与节点Sj之间的连通性p(Si,Sj) (i≠j) 可定义为

(6)

无线传感器网络中的节点连通度是指在网络中节点一跳范围之内能够与其通信的相邻节点的数量与网络中节点总数量二次方的比值。网络连通度越大，网络中存在的可能通路就越多，网络的连通性能越好。故可以得到节点部署的第二个目标函数[11]为

(7)

因此，以区域覆盖率和节点连通度定义的目标函数为

(8)

其中，α为限制的区域覆盖率，p(Si,Sj)≥2表示每个感知节点至少可以与两个及两个以上的节点形成通路，当节点的其中一条通路断开时，节点的信息可由其它通路传输，可保证网络的稳定性，经过多次实验，本文中ω1与ω2的取值分别为0.8和0.2。

2 人工蜂群算法

人工蜂群算法[12]由土耳其学者Karaboga为优化代数问题而提出。根据蜜蜂在活动中扮演的角色，将其归纳为观察蜂、雇佣蜂以及侦查蜂3种类型。蜂群中主要有3个关键要素：食物源、被雇佣的蜜蜂和未被雇佣的蜜蜂；最基本的行为模型是寻找适应度最高的蜜源，ABC算法的实现过程主要由下面几个阶段组成。

初始化阶段：按照式(9)随机生成初始种群SN，即SN个具有D维变量的解

xi,j=xmin,j+rand(0,1)(xmax,j-xmin,j)

(9)

式中：i=1,2,…,SN，j=1,2,…,D，xmax,j和xmin,j为搜索空间的上界和下界。每个解xi,j代表一个D维向量。

雇佣蜂阶段：雇佣蜂通过式(10)产生一个新的蜜源vi,j， 并按照式(8)和式(11)计算新蜜源的适应度，若新蜜源优于原位置xi,j， 则替换掉原来的蜜源。当全部雇佣蜂在完成搜索后，将保留下来的食物源信息与观察蜂进行分享

vi,j=xi,j+φi,j(xi,j-xk,j)

(10)

(11)

式中：k,j是随机选择的下标，且有k∈{1,2,…SN}，j∈(1,2,…,D)，k不等于i，φi,j为[-1,1]之间的随机数。

观察蜂阶段：观察蜂根据式(12)计算每个食物源被选择的概率，然后通过轮盘赌机制选择一个食物源，采用与式(10)相同的搜索策略，并且与原食物源进行比较，择优保留

(12)

侦查蜂阶段：如果一个食物源在循环limit代后仍没有得到更新，表示该食物源对应的侦查蜂可能陷入局部最优，此时将该食物源所对应的雇佣蜂转换为侦查蜂，并按照式(9)随机生成新解。

3 改进的人工蜂群算法-DHSABC

基本人工蜂群算法的探索与开发性能受到了其搜索策略的限制[13]。在算法初期，雇佣蜂阶段应侧重探索能力，在算法初期应该在更大的区域进行探索，更有可能发现最优解；随着迭代次数逐渐增大，较小的变异步长有益于算法迅速收敛，并在最优蜜源附近进行搜索。观察蜂阶段可根据雇佣蜂阶段产生的精英解信息来调整自己的搜索策略，有利于快速找到最优解。

为了提升人工蜂群算法的性能，达到探索与开发能力的平衡，提出了精英解引导下的动态混合搜索策略，使算法能更好地适用于WSN部署问题。在算法初始化阶段引入Tent映射，以提高种群的多样性；在雇佣蜂阶段，提出了基于柯西分布与正态分布的混合搜索策略，同时引入动态权重系数k1、k2，用来平衡算法的探索能力与开发能力；观察蜂在添加动态混合搜索策略的同时引入雇佣蜂阶段的精英解信息，使观察蜂在精英解周围进行开发。

3.1 Tent混沌映射

初始化种群的优劣性会影响到算法的求解精度，多样性好的初始化种群会提升算法的性能。混沌映射的随机性和遍历性能丰富初始化种群的多样性，有利于算法跳出局部最优，增强全局寻优的能力。其中Tent映射作为一种经典的混沌模型，已经被验证了在算法性能提升上的有效性[14]。故本文取Tent映射去初始化种群，假设种群规模为 {1,2,…i…,SN}， 算法的空间维数为 {1,2,…j…,D}， 经过多次测试，文中选取的Tent混沌映射函数如下

(13)

取Tent混沌序列的初始值z(0)=0.47， 种群的规模SN=10，空间维数D=160，图1为Tent映射在[0,1]之间的分布直方图，每个区间值的个数都集中在30～35之间，数值在每个区间上的分布相对均匀。

将式(13)产生的混沌序列映射到解空间后得到初始化种群，种群个体xi,j如下

xi,j=xmin,j+zi,j(xmax,j-xmin,j)

(14)

其中，i=1,2,…,SN，j=1,2,…,D，xmax,j和xmin,j为搜索空间的上界和下界，zi,j为混沌值，将混沌值引入到搜索空间中，能产生更加均匀的初始种群，有利于算法搜索到更优的解。

3.2 基于动态混合变异的搜索策略

在初始人工蜂群算法中，雇佣蜂的食物源由式(10)产生 ，φi,j在[-1,1]之间随机选择，连续性较差，易错过最优解，为此提出一种动态混合搜索策略，如式(15)所示

(15)

式中：k,j是随机选择的下标且满足k∈{1,2,…,SN}, 其中k不等于i，j∈(1,2,…,D)，β是调节系数，T为最大迭代次数，t为当前迭代次数，C(0,1) 为服从标准柯西分布的变异因子，N(0,1) 为服从正态分布的变异因子。

图2为正态分布和柯西分布的概率密度函数对比图。

由图2可知，标准柯西分布相对于正态分布来说形状更加的平缓且逼近0的过程中更加的平滑，在原点附近的分布相对于正态分布更小，数值变化连续性强，所以柯西分布的变异尺度要大于正态分布。在算法前期，动态权重系数k1随着迭代次数的增加而降低，柯西分布具有更大的变异步长且权重系数较大，搜索的区域更加广泛，利于算法跳出局部最优；在算法后期，正态分布变异尺度较小且动态权重k2随着迭代次数的增大而增大，以保证蜂群在最优蜜源附近搜索。

3.3 精英解引导的搜索策略

在基本人工蜂群算法中，观察蜂的搜索方式存在一定的缺陷，即没有利用到观察蜂所搜索到的精英解信息[15]，将雇佣蜂阶段所获得的精英解信息用来引导观察蜂的搜索，从而提高算法的开发能力。对其蜜源的搜索方式进行调整，具体如式(16)所示

(16)

式中：xbest,j是从雇佣蜂中选择的精英解，hi,j是观察蜂搜索的起点，考虑到使用精英解会降低算法的探索能力，所以将雇佣蜂中的精英解与原始解和的1/2作为搜索的起始点，引入精英解的同时也保留原始选择的蜜源。从而在增强算法开发能力的同时也维持算法的探索能力。

4 基于DHSABC算法的覆盖优化设计

4.1 DHSABC覆盖优化算法步骤

本文将蜂群寻找最佳蜜源的过程类比为寻找最佳的节点部署的过程，每一个蜜源代表一个节点覆盖方案，基于DHSABC的节点覆盖优化算法步骤如下所示。

输入：WSN监测区域、节点数目及位置和DHSABC算法相关参数。

输出：最优节点位置、覆盖率及连通度。

(1)按式 (13) 和式 (14) 初始化种群, 其中每个个体代表一种部署方案

(2)t=1 and limit=1

(3)while(t

(4)根据式 (15) 计算新解vi,j

(5)根据式 (8) 和式 (11) 计算新解vi,j覆盖率、 连通度及对应的适应度

(6)ifF(vi,j)

(7)根据适应度值得到精英解xbest,j

(8)按照式 (12) 计算选择概率

(9)跟随蜂根据概率选择蜜源。 按照式 (16) 搜索蜜源

(10)按照式 (8) 和式 (11) 计算覆盖率与连通度，并得到对应的适应度

(11)ifF(vi,j)

(12)if limit>50， 则按照式 (13) 和式 (14) 产生新的食物源

(13)t=t+1

(14)End while

4.2 DHSABC算法时间复杂度分析

在不同节点数目下对DHSABC算法与ABC算法的运行时间做了对比分析，结果见表1。

表1 不同节点数目下的运行时间

由表1可知，在节点数目为60、70、80、90、100的时候，DHSABC算法的运行时间都小于ABC算法，运行时间平均减少了1.95 s，改进后的算法相对于ABC算法来说具备更高的求解效率。

5 仿真实验与分析

5.1 相关参数设置

为验证DHSABC算法在无线传感器网络节点部署问题中的有效性，选取不同文献中的算法进行对比实验，具体的算法见表2，实验参数的设置与相应文献一致。

表2 对比算法

仿真实验环境：Win10操作系统，AMD Ryzen5 2500U with Radeon Vega Mobile Gfx @2.00 Ghz主频，8 G内存，MATLAB 2016a，DHSABC算法参数见表3。

表3 算法参数设置

5.2 网络覆盖率

5.2.1 DHSABC算法的覆盖率分析

为了验证DHSABC算法对ABC算法性能上的提升，将改进后的算法与ABC算法、PSO算法、GABC算法在相同的实验条件下进行比较，实验参数设置见表4。

表4 实验1参数设置

表5给出了ABC算法、PSO算法、GABC 算法、DHSABC算法运行10次后的平均覆盖率。

表5 不同算法下的节点覆盖率

由表5可知，DHSABC具有最高的覆盖率，其中DHSABC算法相对于GABC算法在覆盖率上提高了5.07%，相对于ABC算法提升了8.2%，相对于PSO算法提升了14.33%。

节点采取随机部署的形式，节点初始覆盖如图3(a)所示，监测区域内存在着明显的覆盖空洞，利用ABC算法对节点部署进行优化，优化后实验结果如图3(b)所示，节点的分布相对均匀，监测区域内的覆盖率得到了有效的提升，但仍然存在部分覆盖空洞；GABC算法下的节点覆盖如图3(c)所示，从图中可以看出某些区域内节点的冗余度过高；基于DHSABC算法的无线传感网络部署效果如图3(d)所示，从图中可以看出某些区域内节点的冗余度过高；相比于上述两种算法覆盖更加均匀。

图4是ABC、GABC与DHSABC算法的节点覆盖率收敛曲线图。

由图4可知，DHSABC算法在相同的迭代次数下覆盖率几乎都优于ABC和GABC算法，说明引入精英解信息和混沌初始种群增强了算法的寻优能力，在相同迭代次数下具备更高的覆盖率。迭代次数达到400代以后，ABC与DHSABC算法都趋于收敛，但ABC算法的覆盖率仅维持在90%附近，而DHSABC算法通过采用动态混合策略，能跳出局部最优，搜索到更好的解，在400代时覆盖率达到了98%，相对于ABC算法提升了8%左右。

5.2.2 与IGWO、MS-ALO算法对比

实验参数设置与文献[3]和文献[7]相同，具体参数见表6。

表7为节点初始部署、ABC算法、MS-ALO算法、IGWO算法、DHSABC算法的覆盖率对比。

由表7可知，本文提出的算法覆盖率达到96.58%，相对于ABC算法、IGWO算法、MS-ALO算法，覆盖率分别提升了5.12%、2.3%、0.13%，对区域的覆盖的空洞更少，说明改进后的算法具有更强的寻优能力。

图5(a)和图5(b)分别是ABC算法和DHSABC算法优化后的节点覆盖情况。

对比图5(a)与图5(b)，可以看出DHSABC算法下节点的分布更加均匀，具有更高的覆盖率。

表6 实验2参数设置

表7 实验2优化结果对比

5.2.3 与BPABC、IWOA算法对比

实验参数设置与文献[8]和文献[9]相同，具体参数见表8。

表9为ABC算法、IWOA算法、BPABC算法、DHSABC算法的覆盖率对比；图6(a)和图6(b)分别是DHSABC算法在节点数为60和43优化后的节点覆盖图。

从表9可知，在同等的实验条件下，DHSABC算法的覆盖率达到99.90%，覆盖效果如图6(a)所示，相对于ABC算法、BPABC算法、IWOA算法，覆盖率分别提升了4.76%、2.56%、0.69%。

表8 实验3参数设置

表9 实验3优化结果对比

经多次实验验证，DHSABC算法只需43个节点，就能达到BPABC算法60个节点时的所达到的覆盖率，覆盖效果如图6(b)所示，从图中可以看出节点分布相对均匀，因此在适当降低覆盖率的要求下，DHSABC可有效降低节点的冗余度。

5.2.4 算法在不同节点数目下的覆盖率对比

部署节点数量过多会导致网络中的冗余度增加，部署代价提高。在相同的节点数目下，网络的覆盖率越高，对监测区域的覆盖效果更好，本文分析对比了4种算法在不同节点数目下的覆盖率，如图7所示。

从图7可知，在相同节点数量的情况下，DHSABC算法相比于其它几种算法都具有更高的覆盖率，节点分布更加均匀，说明了改进后的人工蜂群算法增强了算法的寻优能力，提升了传感器网络的覆盖率。

5.3 节点连通度

5.3.1 连通度分析

将改进后的算法与ABC算法、PSO算法、GABC算法在相同的实验条件下比较连通度，实验参数设置与表4相同。

为降低数据随机性对实验分析的影响，将是ABC算法、PSO算法、GABC 算法、DHSABC算法在相同条件运行20次后的平均连通度进行对比，结果见表10。

表10 不同算法下的节点连通度

由表10可知，DHSABC具有最高的连通度，其中DHSABC算法相对于ABC算法在连通度上提高了0.0068，相对于GABC算法提升了0.0051，相对于PSO算法提升了0.0145。

节点采取随机部署的形式，节点的初始状态如图8(a)所示，由图可知监测区域内节点冗余度过高，节点之间的连通效果不理想；利用ABC算法对节点部署进行优化，实验结果如图8(b)所示，相对于图8(a)来说，节点分布更加的均匀，但仍然有部分节点处于单连通状态；图8(c)是GABC算法下的节点连通度，相对于ABC算法来说，具备更高的连通性，但依然有较大的提升空间；基于DHSABC算法的节点连通状态如图8(d)所示，节点的分布较好，且每个节点都至少可以与两个或两个以上的节点连接。综上，DHSABC算法改善了ABC、GABC算法下网络连通性弱的不足。

图9是ABC、GABC、DHSABC算法的连通度收敛曲线图。

从图9可知，初始状态时节点分布比较集中，所以连通度很高，但此时的节点冗余度也很高，随着迭代的进行，节点逐渐分散，连通度出现下降趋势后由于算法收敛又趋于稳定。其中DHSABC算法在相同的迭代次数下的连通度几乎都优于ABC算法与GABC算法，说明改进后的算法具备更强的寻优能力，节点之间的连通性更好；且从收敛曲线可以看出，由于在雇佣蜂阶段引入了精英解信息，DHSABC算法的曲线更加稳定。

5.3.2 不同节点数下的连通数目对比

在相同的节点数目下，网络中的连通数目越多，网络的稳定性更好，图10是4种算法在不同节点数下的连通数目对比。

由图10可知，DHSABC算法相对于其它几种算法具有更高的节点连通数目，网络具有更好的连通性。在一定范围内，每增加5个节点，网络中节点的可连接数目会增加19个左右，因此在对节点连通度有需求时，通过预测出所需的传感器节点，在节点预测值附近初始化种群的维度，可提高部署的效率。

6 结束语

针对WSN覆盖中的覆盖率与节点连通度优化问题，提出了一种基于改进人工蜂群算法的节点部署策略，通过构建基于节点的连通度和网络覆盖率的目标函数来引导蜂群搜索最优蜜源。首先，针对人工蜂群算法寻优能力较差的不足，利用Tent映射初始化种群，并将动态混合搜索策略引入到雇佣蜂和观察蜂阶段，增强蜂群对搜索空间的遍历性和寻优能力；其次，在观察蜂阶段将精英解和原始解的1/2作为搜索的起点，以平衡算法的全局探索与开发能力；最后将改进后的算法应用到WSN节点部署问题中。仿真结果表明，相对于其它算法，改进后的人工蜂群算法能达到更高的覆盖率和节点连通度。