改进人工蜂群算法的无线传感器网络覆盖优化

1、改进人工蜂群算法的无线传感器网络覆盖优化： Since the wireless sensor networks coverage belongs to the combinatorial optimization category， theartificial bee colony algorithm is introduced and perfected to improve the coverage rate in the condition of limited node quantity. The global optimal individual feedback is injec

2、ted to improve the convergence rate ， and update the refresh method of investigation bee. The one?dimensional Gaussian mutation method and particle prior knowledge are used fully to make the particles active ， and improve the global search capability of the algorithm. The algorithm with 40 nodes was

3、 carried out with simulation experiment. The experimental results show that the coverage rate of the improved algorithm can reach up to 87.2%， and is increased by 1.6% and 3.87% respectively than that of the improved shuffled frog leaping algorithm and standard artificial bee colony algorithm.Keywor

4、ds： wireless sensor network； artificial beecolony ； global optimization ； one?dimensional Gaussian mutation ； probabilistic measurement model ； coverage optimization0 引 言无线传感器网络 1 具有低功耗和方便组网的优势，在物联 网、智能交通、目标定位和环境探测等领域得到了广泛应用 2?3 。但随着网络中传感器节点数量的不断增加，节点冗余问 题也越加突出，怎样才能低成本投入且高效的利用成为研究热 门，增大网络的覆盖面积成为无线传感

5、器网络应用的关键问题。由于传统算法 4?5 存在节点覆盖程度低的问题，要想实现 全局最优在技术层面还有欠缺， 鉴于无线传感网络的结构与群体 智能算法的特点极其相似， 因此，大量的学者开始使用智能算法 优化无线传感器网络。文献 6 将改进的粒子群算法应用到无线传感网络的自组织 中，有效地提高了节点的覆盖面积；文献 7 根据节点位置信息 建立部署模型，提出一种基于改进混合蛙跳算法；文献 8 将遗 传算法应用于优化无线传感器网络覆盖；文献 9 将萤火虫算法 用于网络覆盖优化。 但这些应用于无线传感网络覆盖问题的群体 智能算法由于本身存在一些缺点，导致其优化的结果不是很理 想。人工蜂群算法 10?11

6、 具有良好的全局性，已经在很多领域 内被证明优于其他一些算法。结合无线传感器网络的结构特点， 把节点的部署看成是蜂群寻找最优蜜源的过程， 将改进人工蜂群 算法应用到无线传感器网络覆盖优化中， 与其他几种算法的比较 实验说明，提出算法得到的效果有明显改善。1 人工蜂群算法及改进方法1.1 人工蜂群算法描述根蜜蜂在活动中扮演的角色， 将其归纳为观察蜂、 采蜜蜂以 及侦查蜂三种类型。 侦查蜂在正常情况下是不存在的， 当采蜜蜂 结束采蜜后自动转化为侦查蜂 12?13 。其搜索步骤为：首先采 蜜蜂选取周围最近的一个蜜源， 然后观察蜂通过信息跟随其中一 只采蜜蜂， 在这个过程中选取出较好的蜜源， 最后采蜜

7、蜂放弃蜜 源，转化为侦查蜂，随机搜索新蜜源。上述过程即为一个优化问题，将每个蜜源的位置看成一个 解。假设蜜源位置表示为总数为其中， 第个蜜源表示为为其收益 度值。观察蜂选取蜜源的概率表示如下 14 ：观察蜂对周边的蜜源进行权衡后， 会选取较好的蜜源， 蜜源 位置更新公式为：式中：为 0 ，1 之间的随机数。如果，那么观察蜂就会更新 位置，否则不变。在更新的同时限定次数加 1，当循环次数达到 限定阈值时，会丢弃该蜜源，转化为侦查蜂，生成位置公式为：1.2 改进的人工蜂群算法 在蜂群算法中，当达到一定次数后适应值仍然没有改进时， 该蜜蜂会变成侦查蜂，然后随机生成新的蜜源位置代替原位置。 采用侦查蜂

8、随机搜索的目的是当算法处于收敛状态， 全部蜜蜂均 汇聚在同一蜜源时，把蜜蜂强制转移，以此保证蜜蜂的活力。但 由于这种策略放弃了原来蜜源的所有信息， 导致算法收敛速度较 慢，为了让蜜蜂既能够保证足够的活力， 同时又可以充分地利用 先验知识，采用一维高斯变异的搜索策略，计算公式如下： 人工蜂群算法采用概率选择蜜源位置进行更新， 所以具有全局搜 索能力， 从而使粒子具有很强的随机性， 即便是加入了收益度值 的判定， 并没有明显提高其收敛速度。 所以又在更新公式中增加 了最优蜜源位置这样就使得其性能更加均衡， 改进算法位置更新 的表达式为：改进人工蜂群算法的步骤如图 1 所示。2 网络覆盖优化的问题无

9、线传感网络覆盖优化的问题可以描述为： 在一个已知大小 的空间内布置多个能够感应与通信的节点， 在保证节点之间连通 性的同时， 采取一定的措施来部署节点， 且尽可能使用较少的节 点达到网络覆盖范围最大化。 其中网络覆盖率是最重要的一个衡 量标准。常用的节点测量有二元测量法和概率测量法两种模型 15 。 由于前者具有本身的局限， 容易导致测量的精度偏低， 故这里通 过概率测量模型研究无线传感器网络覆盖率的问题。 设测量范围 内有个节点，节点用表示，其中且每个节点的属性和参数均相同， 通信半径为感应半径为同时满足在二维空间中研究该问题， 假设节点所处的位置为， 测量范 围内任意点坐标为，所以相对的检

10、测概率可表示如下：式中：是传感节点测量的可靠性参数，且是到的欧氏距离； 为传感器节点属性相关参数，且满足与是输入参数。 通过得到的能够算出测量范围内传感器节点对点的联合检 测概率，可表示如下：式中表示测量范围内的全部节点。 在这里设定的检测阈值为 0.8 ，也就是说，当联合检测概率小于 0.8 时，就可以认为点不 被检测；反之，就认为点可以被检测。假设检测区域为规则矩形，为了计算无线传感器网络覆盖 率，在检测区域上划分个面积相等的小矩形， 然后把小矩形看作 点利用式（ 8）算出所有点的检测概率，同时计算出被检测点的 数量，两者的乘积即为覆盖面积，那么覆盖率可以表示为：3 实验结果及分析 为了验

11、证改进人工蜂群算法在无线传感器网络覆盖中的效 果，使用 Matlab 软件对其进行仿真实验， 并与标准粒子群算法、 标准人工蜂群算法和文献 7 中的改进蛙跳算法进行对比，进而 说明本文提出算法的有效性。3.1 相同节点数量对比实验在边长50 m的正方形区域内，随机部署 40个节点，感应半 径5 m通信半径10 m,传感节点测量的可靠性参数传感器节点 属性相关参数。参与比较算法的迭代次数极限为 500，粒子数为 50。其中， 标准人工蜂群算法和改进人工蜂群算法参数设置一致， 最大采蜜 次数为 50，改进蛙跳算法的迭代次数为 5，粒子群算法参数且从0.50.2线性递减。为了验证提出的改进算法的优越

12、性，将标准粒子群算法（PSO、改进蛙跳算法（GSFLA和标准人工蜂群算法（ABCA 进行比较，得到的结果如表 1 所示。从表 1 得到的结果可以看出， 采用改进人工蜂群算法的无线 传感器网络覆盖率达到了 87.2%，与改进蛙跳算法相比提高了 1.6%，与标准人工蜂群算法相比提高了 3.87%，网络覆盖率得到 了明显的改善。为了从直观上观察覆盖效果， 将上述实验结果输出， 分别得 到 40 个初始节点、改进蛙跳算法、标准人工蜂群算法和改进人 工蜂群算法的直观覆盖效果如图 2图 6 所示。从上面几种算法对应的覆盖图可以看出， 利用智能算法对初 始节点覆盖进行优化后， 大块空白的现象消失， 节点分布

13、趋于均 衡，改进人工蜂群算法的优化效果最佳。3.2 不同节点数量对比实验 为进一步验证改进人工蜂群算法在无线传感器网络覆盖中 的效果，与标准人工蜂群与改进蛙跳算法在不同节点数量下的覆 盖率进行了对比实验，配置参数不变，得到的结果如表 2 所示。从表 2 可以看出， 改进人工蜂群算法不管是在节点数量较多 时，还是在节点数较少时均比其他几种算法能更加有效地提高无 线传感器网络覆盖率。 为方便对比在节点变化情况下算法覆盖优 化效果变化差异，将节点数量与覆盖率的关系变化绘制成曲线图，如图 7 所示。从节点数量与覆盖率关系曲线图中可以看出： 随着无线传感 器节点数量的增多， 网络覆盖率均得到了明显的提升。 节点的利 用率体现在曲线的斜率上， 随着无线传感器节点数量的增多， 均 表现出减弱的趋势， 但是改进人工蜂群算法的下降速率要小于标 准人工蜂群的下降速率， 说明改进人工蜂群算法的全局搜索能力 更强，在同等条件下具有更优的节点利用率， 网络覆盖效果更好。4 结语 结合无线传感器网络的结构特点，引入改进人工蜂群算法， 在更新策略中添加全局最优个体反馈，