基于改进遗传算法的无线网络覆盖算法

刘静静，郑倩倩

（1.郑州大学　信息工程学院，河南　郑州　450000；2.郑州澍青医学高等专科学校，河南　郑州　450000）

基于改进遗传算法的无线网络覆盖算法

刘静静1，2，郑倩倩2

（1.郑州大学信息工程学院，河南郑州450000；2.郑州澍青医学高等专科学校，河南郑州450000）

考虑到传统的遗传算法在对无线传感网络覆盖进行优化时，存在起始阶段计算速度快，后期局部寻找最优解能力弱，不能充分使用系统反馈路径信息，使得算法会因冗余迭代而导致陷入局部最优解，影响优化效率和覆盖率等问题，将蚁群算法融合到遗传算法中，对遗传算法进行改进。通过不同覆盖范围和节点的三个实例进行优化效果分析，可知在小面积的覆盖范围内，以及节点个数较少时，该文研究的改进方法与传统优化方法的覆盖率和完成时间差别不大，但是随着覆盖范围的增大，节点个数的增加，该文研究的改进方法完成时间明显缩短，覆盖率明显增大，相比传统优化方法具有更大的优势。

遗传算法；蚁群算法；无线传感网络；覆盖优化

无线传感网络已经广泛地应用于各行各业中，网络由多个传感节点通过树形、星形等拓扑结构连接，各个节点之间相互连接，实现对现场数据地监测、控制等功能，如何针对不同的应用场合和条件，优化调节传感节点的个数和位置，使得无线传感网络覆盖率最大，是无线传感网络研究的热点问题之一，有利于提高无线传感网络的服务质量［1⁃5］。

1　无线传感网络覆盖问题模型

将无线传感网络覆盖区域看作二维平面，在这个二维平面上设置有N个感知半径和通信半径分别为r和R的无线传感节点。设定各个无线传感节点用表示，是节点的二维坐标，则无线传感网络中传感节点集合表示为。以Ccover表示测量目标传感节点集合，则目标节点p联合检测概率表示为：

将无线传感网络覆盖率定位表示为：

有效工作的网络节点率表示为：

式中：S1表示无线网络传感器总节点数量；S2表示有效的传感器节点数量。

定义η为能量均衡系数，对无线传感网络的能耗均衡问题进行考虑，能量均衡系数η能够对无线网络能耗均衡度进行反映，η越大，则表示该无线传感网络的能耗越不均匀。能量均衡系数η表示为：

式中：k为有效节点个数；Ei为第i节点的能量剩余量。

无线传感网络覆盖优化问题需要将覆盖率、能量均衡以及工作状态无线节点个数三方面进行综合考量。故无线传感网络覆盖优化问题的数学模型可表示为［6⁃7］：

式中：w1，w2，w3为权值，三者之和等于1。

2　改进遗传算法

传统的遗传算法（GA）特点是：起始阶段计算速度快，后期局部寻找最忧解能力弱，不能充分使用系统反馈路径信息，使得算法会因冗余迭代而导致陷入局部最优解［8⁃9］。有人提出将另外一种群智能算法——蚁群算法与遗传算法进行结合，改进遗传算法现有问题。目前常用的混合方法仅对两种算法进行简单叠加，没有对两种算法转换时机进行考虑，没有做到真正的融合，因此改进后，遗传算法性能提升不大［10］。本文改进方法是首先改进蚁群算法初始信息素较低的问题。之后在遗传算法和蚁群算法之间的切换使用动态转移法，而不是静态转移法。动态控制适应度函数方法为：

使用动态挥发系数方法对算法后期的信息素进行更新，使用信息素以及适应度值对遗传算法的交叉变异概率进行动态调整，使用信息素和启发信息对遗传算法的交叉变异位置进行调整。构造新的搜索机制，蚂蚁按照下面方式选择节点：

式中：allowedk表示蚂蚁下次运行的取点；q是0～1的随机数；是边（i，j）的信息素含量；是在第i个节点，第k个蚂蚁选取第j个节点的概率；q1和q2由用户设定；如果进化次数达到设定值，或者连续若干代的个体平均适应值和信息素含量低于设定的阈值，都可终止优化算法，设定两个终止条件目的是为了提高算法进化的质量［11⁃13］。具体算法流程如下：

步骤1：依据实际优化任务要求对目标函数和适应度函数进行确定。

步骤2：使用遗传算法生成优化解，数量为nGA组。

步骤3：使用信息素转换方法将遗传算法生成的优化解转换为蚁群算法的初始信息素。

步骤4：将蚁群算法基本参数进行初始化，随机地在N个节点布置M个蚂蚁。

步骤5：使用由蚂蚁状态转移规则建立的搜索方法，将N个节点一一遍历，形成一个完整路径。

步骤6：求出每条路径的信息素含量和适应度值。执行选择操作，若达到终止条件，则直接进入步骤10，否则进行下一步骤。

步骤7：通过交叉变异操作得到M条路径。

步骤8：根据路径的适应度值和信息素含量对已经得到的M+U条路径进行重新排序，选取排名前M条路径。

步骤9：更新信息素，并回到步骤5。

步骤10：得到了最优的路径，完成了算法的改进和优化任务。

3　实例分析

本文以一个覆盖区域为100 m×100m正方形区域为研究对象，进行实例分析，设定无线传感节点个数为200，通信和感知半径为3 m和1.5 m，使用软硬件平台为Matlab R2014，Windows 7for 64，酷睿I5 4590处理器，内存为4 GB DDR3 1 600×2，初始的无线传感节点分布如图1所示。

图1　初始的无线传感节点分布

使用常规遗传算法优化无线传感网络覆盖方法与本文研究的改进型遗传算法优化无线传感网络覆盖方法进行对比，不同算法下覆盖率以及能耗率随着节点个数改变而变化曲线如图2所示。

图2　不同算法下覆盖率及能耗率

通过对比两种算法下覆盖率以及能耗率随着节点个数改变而变化曲线可知，本文改进方法的平均覆盖率和能量消耗率相比常规遗传优化算法分别提高了6.2%，以及降低了5.7%。说明本文研究方法对于网络覆盖率和能耗降低有较好的优化效果。下面通过三种实验方法，对覆盖优化算法的效率进行分析。三种实验方案如表1所示。实验结果如图3所示［14⁃15］。

表1　实验方案

进行三种实验方案结果对比可知，在小面积的覆盖范围内，以及节点个数较少时，本文研究的改进方法与传统优化方法的覆盖率和完成时间差别不大，但是随着覆盖范围的增大，节点个数的增加，本文研究的改进方法完成时间明显缩短，覆盖率明显增大，相比传统优化方法具有更大的优势。

4　结　论

本文通过研究一种改进遗传对无线传感网络节点覆盖进行优化。

通过实例分析得出结论：

（1）在小面积的覆盖范围内以及节点个数较少时，本文研究的改进方法与传统优化方法的覆盖率和完成时间差别不大，但是随着覆盖范围的增大，节点个数的增加，本文研究的改进方法完成时间明显缩短，覆盖率明显增大；

（2）在覆盖区域为100 m×100 m正方形，节点数为100的实例中，本文研究改进方法的平均覆盖率和能量消耗率相比常规遗传优化算法分别提高了6.2%，以及降低了5.7%。说明本文研究方法对于网络覆盖率和能耗降低有较好的优化效果。

图3　覆盖优化算法的效率实验结果

［1］万佳.基于多种群并行粒子群优化算法研究［D］.南昌：南昌大学，2012.

［2］李志武.人工鱼群算法的改进及在无线传感器网络覆盖优化的应用［D］.长沙：湖南大学，2012.

［3］周少龙.基于节点协同调度的海事传感网络覆盖控制研究［D］.武汉：武汉理工大学，2014.

［4］周利民.基于鱼群算法的无线传感器网络覆盖优化研究［D］.长沙：湖南大学，2010.

［5］宋苏鸣.基于改进人工蜂群算法的无线传感器网络覆盖优化策略［D］.西安：西安电子科技大学，2014.

［6］陈锋.大规模无线传感器网络覆盖优化研究［D］.重庆：重庆大学，2014.

［7］傅彬.基于改进人工鱼群算法在无线传感网络覆盖优化中的研究［J］.计算机系统应用，2015（12）：223⁃227.

［8］乔阳.基于改进遗传算法的图像分割方法［D］.成都：电子科技大学，2013.

［9］林周泉.基于改进遗传算法的电力系统无功优化［D］.衡阳：南华大学，2013.

［10］张可.无线移动自组织及传感器网络中若干问题的研究［D］.成都：电子科技大学，2010.

［11］黄发良，苏毅娟.基于GA与PSO混合优化的Web文档聚类算法［J］.小型微型计算机系统，2013，34（7）：1531⁃1533.

［12］曹道友.基于改进遗传算法的应用研究［D］.合肥：安徽大学，2010.

［13］陈振同.基于改进遗传算法的车间调度问题研究与应用［D］.大连：大连理工大学，2007.

［14］孙莉.基于一种差分鱼群算法在WSN覆盖应用的研究［J］.科技通报，2015（9）：187⁃191.

［15］王明亮，闵新力，薛君志.基于改进人工鱼群算法的WSN覆盖优化策略［J］.微电子学与计算机，2015（6）：78⁃81.

Wireless network coverage algorithm based on improved genetic algorithm

LIU Jingjing1，2，ZHENG Qianqian2
（1.School of Information Engineering，Zhengzhou University，Zhengzhou 450000，China；2.Zhengzhou Shuqing Medical College，Zhengzhou 450000，China）

Since in optimization process of wireless sensor network coverage，the traditional genetic algorithm has fast calcu⁃lation speed in initial stage，but its local optimization capacity in the later period is weak，and it can not fully use the system feedback path information，which make the algorithm fall into the local optimal solution due to redundancy iteration，and influ⁃ence the optimization efficiency and coverage rate，in this paper，the ant colony algorithm is fused into genetic algorithm to im⁃prove genetic algorithm.The optimization effectiveness analysis is conducted by means of three examples of different coverage scale and node，by which a fact that there is no large d8ifference between the improved method and the traditional optimization method in the aspects of coverage rate and completion time when coverage area is small and node number is less is found out，but the improved method’s completion time is shortened obviously，and coverage rate is increased significantly with increase of the coverage scope and the increase of the node number.Therefore，compared with the traditional optimization method，the im⁃proved method has much better superiority.

genetic algorithm；ant colony algorithm；wireless sensor network；coverage optimization

TN915⁃34；TP301.6

A

1004⁃373X（2016）18⁃0009⁃03

10.16652/j.issn.1004⁃373x.2016.18.003

刘静静（1982—），女，河南郑州人，讲师，在读硕士研究生。主要研究方向为计算机网络、数据挖掘、现代教育技术。郑倩倩（1979—），女，河南商丘人，讲师，硕士。主要研究方向为计算机技术。

2016⁃01⁃18

河南省科技厅项目：基于流量倾斜分类的网络调度算法（豫科鉴委字［2014］第2144号）