基于改进鱼群算法的无线传感器网络K重覆盖优化策略

秦俭

摘要：为了实现无线传感器网络K重覆盖范围的最大化，延长网络寿命，提出了一种基于改进鱼群算法的无线传感器网络K重覆盖算法，将区域K覆盖率，节点利用率，能耗均衡指标作为优化目标函数，建立数学模型，用混沌鱼群算法求解，自适应人工鱼视野、步长，得到最优覆盖方案。仿真结果表明，该算法比基本人工鱼群算法搜索效率更高，有效的降低了网络成本。

关键词：无线传感器网络；覆盖优化；人工鱼群算法；混沌

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）10-0167-02

无线传感器网络是近几年研究的热点，网络覆盖问题是无线传感器网络的基本问题之一。近年来，国内外专家学者在无线传感器网络覆盖控制方面取得了很多研究成果，智能算法多用于覆盖控制问题中，文献[1]将蚁群算法应用于求解覆盖模型，但在收敛速度方面有些不足。文献[2]采用了遗传算法，时间复杂度较高。文献[3]是将粒子群算法应用于覆盖优化问题，采用了概率感知模型。文献[4]将混沌运动与粒子群算法结合，给出了新型智能算法，覆盖优化效果较好。

本文研究的是无线传感器网络k覆盖问题[5]，提出了一种基于改进鱼群算法的无线传感器网络K重覆盖优化策略，将混沌运动和人工鱼群算法结合，避免了人工鱼群算法容易陷入局部最优的缺点，提高了搜索效率。

1 覆盖优化模型

将监测区域A数字离散化为个像素，在该区域投放参数相同的传感器节点，感知半径为r，节点数目为N。

2 覆盖优化算法

2.1 自适应控制

人工鱼群算法[6]中，公告板显示的人工鱼为最优人工鱼，当前人工鱼与最优人工鱼之间的距离为感知距离v1。与当前人工鱼距离最近的人工鱼称为最近人工鱼，感知距离v2。

在觅食行为中，对于当前人工鱼，算法按照视野v1 和视野v2进行搜索，比较两个视野范围内的目标位置的食物浓度，若均低于当前人工鱼的食物浓度，则继续搜索。若两个目标位置的食物浓度都优于当前位置，或者有一个位置的食物浓度优于当前位置，则该人工鱼向两个位置中最佳的方向移动。移动步长为按感知距离的自适应步长。则当前人工鱼在两个视野范围内进行比较觅食，提高了收敛速度和寻优精度，避免了算法陷入局部最优解。

2.2 混沌搜索[7]

混沌搜索因其具有遍历性的特点，使得搜索过程增强了克服局部极值的能力，提高了全局寻优能力。本文将混沌搜索融入人工鱼群算法中，主要体现在以下两个方面：

1）人工鱼群算法初始化过程是随机的，会出现一部分解群远离最优解的情况，使得收敛速度变慢，效率降低，为了得到较好的初始解群，采用混沌序列进行初始化，择优生成初始群体，在确保初始化位置随机性的基础上，提高了搜索的遍历性。

2）在人工鱼聚群行为和追尾行为后执行一次混沌搜索，更好的提高了算法克服局部极值的能力，提高了搜索效率，得到更优的解。

2.3 改进的人工鱼群算法

1）参数初始化：设置混沌初始化鱼群的各种相关参数。

2）产生初始化解群：在目标区域混沌产生N条人工鱼，从中选出条较优个体作为初始化鱼群，定义初始迭代次数。

3）公告板赋初值：计算初始化鱼群中每条人工鱼对应的区域重覆盖率，并比较大小，将最大的区域重覆盖率作为食物浓度和这条人工鱼记入公告板。

4）行为选择：对各条人工鱼，对其各分量进行一次混沌搜索，如果位置更优，则更新。觅食行为中自适应调整视野和步长，使当前人工鱼在两种视野范围内进行比较觅食。

5）公告板：每条人工鱼执行一次行为后，比较自身食物浓度和公告板的食物浓度，若优于公告板的食物浓度，则更新公告板。

6）判断是否达到结束条件，如果达到结束条件，则算法结束，输出结果，否则转向4）进行下一次优化。

3实验仿真

从表1来看，在设定精度下，从收敛所需要的最少、最多、平均迭代次数来看，改进鱼群算法都明显优于人工鱼群算法，也说明改进鱼群算法的效率明显高于人工鱼群算法。

由图1可知，无线传感器网络K重覆盖率和节点的感应半径呈同方向变化，感应半径增加，则K重覆盖率增大，但是当感应半径达到一定值时，K重覆盖率变化较小，趋近于平稳。因为传感器节点的探测半径越大所消耗的能量也越大，因此在保证所需要的K重覆盖率的前提下，选择最适当的感应半径有利于减少能量消耗，延长传感器网络使用寿命。

4 结论

本文提出了一种基于改进鱼群算法的无线传感器网络重覆盖优化策略，并进行了实验仿真，结果表明，本文算法获得了较高的重覆盖率，算法的迭代次数优于人工鱼群算法，搜索效率更高，有效地实现了无线传感器网络覆盖优化。

参考文献：

[1] 彭丽英.改进的蚁群算法网络节点覆盖优化研究[J].计算机仿真，2011，28（9）：151-153，255.

[2] 殷卫莉，陈巍.遗传算法在无线传感器网络覆盖中仿真研究[J]. 计算机仿真，2010，27（10）：120-123.

[3] 沈海洋.基于遗传PSO的无线传感网络覆盖优化算法研[J].微电子学与计算机，2013，30（3）148-151.

[4] FL Lian，Moyne W，Tilbury D. Network design consideration for distributed control systems[J].Control Systems Technology IEEE Transactions on， 2002，10（2）：297-307.

[5] 刘明，曹建农，郑源，等.无线传感器网络多重覆盖问题分析[J].软件学报，2007，18（1）：127-136.

[6] 李晓磊，邵之江，钱积新. 一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践，2002，22（11）：32-38.

[7] 谭跃.具有混沌局部搜索策略的粒子群优化算法研究[D].长沙：中南大学，2013.