基于改进遗传算法的无线传感网覆盖优化

胡国龙，贾振红，覃锡忠，曹传玲，牛洪梅

(1.新疆大学 信息科学与工程学院，乌鲁木齐 830046; 2.中国移动通信集团 新疆有限公司，乌鲁木齐 830063)



基于改进遗传算法的无线传感网覆盖优化

胡国龙1，贾振红1，覃锡忠1，曹传玲2，牛洪梅2

(1.新疆大学 信息科学与工程学院，乌鲁木齐 830046; 2.中国移动通信集团 新疆有限公司，乌鲁木齐 830063)

为提高混合无线传感器网络(WSNs)的覆盖率，将改进的遗传算法应用到WSNs覆盖优化中，通过合理调整移动节点的位置来提高网络覆盖率;针对传统群体智能算法易“早熟”，最大迭代次数需试探设定等缺陷，提出了基于多个种群并行优化的改进遗传算法;多个种群之间并不独立，而是通过移民算子相互联系；分别利用人工选择算子与精华种群选择并记录各个种群每一代最优染色体；并利用精华种群中保存的最优染色体设计出新的进化终止条件;仿真结果表明，改进的遗传算法不仅无需设定最大迭代次数而且收敛速度快，更兼有效地提高了WSNs的覆盖率。

无线传感器网络；覆盖；遗传算法；移民算子；人工选择算子

0 引言

无线传感器网络(wireless sensor networks，WSNs)现在已经被大规模应用到军事目标跟踪和监视、人体健康监测、智能家居控制等多个领域[1]。网络覆盖率是研究WSNs所面临的首要问题，同时也是衡量WSNs服务质量的重要指标[2]。近年来，应用群体智能算法来优化WSNs的覆盖成为研究热点[3-6]。文献[3]将标准遗传算法应用到无线传感器网络覆盖优化中，研究结果表明该方法有一定的有效性，但是容易陷入未成熟收敛。文献[4]将种子杂交算子引入粒子群算法中，一定程度上克服了标准粒子群算法易早熟等问题，进一步提高了WSNs的覆盖性能。文献[5]在传统人工鱼群算法中加入公告板记录算子并对人工鱼加入变异算子，来提高算法收敛到最优解的概率，有利于网络覆盖率的提升。文献[6]将差分进化算法与人工蜂群算法相结合来解决差分进化算法后期，种群多样性低，个体陷入局部最优而早熟的现象。上述研究，都不同程度地提高了经典算法的性能以及WSNs的覆盖率。然而以上算法存在共同的缺点：都是单个种群串行搜索寻优，不同控制参数对寻优结果影响很大，而且收敛速度比较低。算法的终止条件最大迭代次数需要人为设定，迭代次数设置太小，不能收敛到最优值；而迭代次数如果设置过大，造成计算资源的浪费。因此，需要能够多个种群并行搜索的算法来减小不同控制参数对寻优结果的影响。同时，充分利用迭代过程中知识的积累，设计更为合理的算法终止条件。针对上述研究存在的问题，本文提出了一种改进的遗传算法进一步优化WSNs的覆盖性能。

1 系统模型

假设传感器网络监测区域为简单的二维平面区域A，P个不可移动节点(固定节点)、Q个可移动节点随机播撒在监测区域A。每个节点都能准确获知自己的位置，并且同一位置节点部署不重复，可移动节点具有自移动功能。固定节点与可移动节点的性能相同，感知半径均为r，通信半径为R。集合S={S1，S2…, Si, …，SP+Q}代表部署的传感器节点集合。节点Si={(xi,yi), r}可以覆盖以(xi,yi)为圆心，以r为半径的区域。将区域A离散化为(M(N)个像素点，当某个像素点(x,y)在Si(i=1, 2,…,P+Q)的覆盖区域内，则称该像素点被节点Si覆盖。本文采用布尔感知模型，则像素点(x,y)被节点Si覆盖的概率计算如下：

(1)

所以节点集的联合测量覆盖率为[7]

(2)

2 遗传算法与改进算法

2.1 标准遗传算法

遗传算法(genetic algorithm,GA)是模仿生物进化过程中自然选择现象的群体智能算法[8]。GA将优化参数进行编码，生成染色体，然后利用选择算子、交叉算子、变异算子来交换染色体携带的信息，通过多次重复上述操作最终获得优化函数所需的最优染色体。具体算法描述如下：

1)种群初始化：随机生成W个长度相同的数组，将每个数组当作一个染色体，W个染色体共同组成一个种群，把该种群作为进化的初始种群。

2)适应度函数：用来评价个体的优劣。本文把节点集的覆盖率PC(S)作为适应度函数，即PC(S)越大，表示该个体在种群中适应性越强。

3)选择算子:在当前种群中选出适应度较高的个体作为父代，使之以较大的概率繁殖下一代；对于当前种群中适应度较低的个体，则使之以较小的概率繁殖下一代。本文采用文献[9]中所提的轮盘赌法确定个体被选中的概率。则第i个体被选择的概率为

(3)

其中，Fi代表第i个个体的适应度，W代表该种群中个体总数。

4)交叉算子：在种群中任选一对染色体，通过交换部分染色体片段，产生新的优秀个体。染色体am与染色体an在第k位上进行交叉的具体方法为[10]

(4)

其中：b在区间[0,1]随机产生。

5)变异算子：在种群中随机挑选一个染色体，通过改变该染色体中的某一位，产生新的染色体。染色体am在第k位上执行变异操作的具体方法为

其中，amax、amin分别为染色体位amk的上界和下界。Z(c)=r2(1-c/Cmax)2，c代表当前进化代数，Cmax代表设定的最大进化代数，r与r2都是在区间[0,1]中随机产生。

2.2 改进的遗传算法

早熟现象是标准遗传算法存在的一个重要缺陷[11]。主要有以下两个原因：(1)交叉概率和变异概率对GA的收敛速度以及寻优结果影响很大。它们分别决定了GA的全局搜索能力和局部搜索能力。不同的概率组合，寻优结果差异非常大。为弥补这一缺点，本文改进算法通过对多个种群设置多组不同组合的交叉概率与变异概率，让其并行协同进化。同时，各个种群之间并不是独立的，而是用移民算子相互联系，最终寻优结果取所有种群协同进化的最优结果。(2)算法终止条件没有理论指导，进化代数设置过小，种群没有充分进化，造成早熟。本文引入人工选择算子和精华种群来设计算法终止依据。具体改进说明如下：

移民算子：在种群协同进化过程中，每隔几代将一个种群中最优的个体转移到相邻种群中，并且淘汰掉接收移民种群中适应度最低的个体。

人工选择算子：选出每个进化代中各个种群最优的个体。

精华种群：由各个种群中被人工选择算子选出的最优个体组成的新种群。精华种群不执行标准遗传算法的任何操作，只简单记录每一代各个种群的最优个体。本文算法终止的条件是精华种群中最优个体保持代数是否达到设定值，这样设计充分利用了种群进化过程中积累的信息，避免不必要的迭代。

本文算法的结构示意图如图1。开始，N个种群并行执行标准遗传算法的基本操作；每进化一代，各个种群通过人工选择算子将最优个体保存到精华种群中；每隔一定代数执行一次移民操作，用源种群的最优个体代替目标种群的最差个体。循环执行以上操作，直到精华种群中最优个体保持代数达到设定值。

图1 改进遗传算法流程图

3 仿真结果与分析

假定WSNs的监控区域为20 m×20 m正方形二维平面区域，并将其离散化为20×20个正方形小栅格。所有传感器节点的感知半径均为2 m(即r=2 m)，通信半径均为4 m(即R=4 m)。传感器的可移动节点个数为20个，通过调整可移动节点的位置来覆盖固定节点留下的空洞。

图2、图3中，实心三角形代表固定节点，以实心三角为圆心的圆域代表固定节点的监测范围；实心正方形代表可移动节点，以实心正方形为圆心的圆域代表可移动节点的监测范围。图2是随机撒点后形成的初始节点覆盖图，初始覆盖率为56.5%。图3为用本文所提算法优化后的节点覆盖分布图，优化后的覆盖率为87.5%。通过图2与图3对比可知，可移动节点通过调整自身位置，覆盖了被监测区域原来比较空旷的位置，使得整个被监测区域的覆盖率提高了31%。说明应用本文算法进行WSNs覆盖优化不仅可行而且有效。

图2 初始节点分布图

图3 本文算法优化后节点分布图

图4 覆盖率对比图

算法的终止条件为精华种群中最优个体最少保持代数为7。从图4可以看出，标准遗传算法和人工鱼群算在迭代100次时覆盖率分别为75.8%、77.3%。而本文所提算法在进化到67代时满足终止条件停止进化，此时的覆盖率高达87.5%。可见，本文算法不仅收敛速率比另外两种算法快，而且能有效克服早熟现象，同时有比较合理的迭代终止条件。

文献[3]与文献[4]都研究了衡量覆盖算法性能的另一个指标RD(RD=覆盖率/平均移动距离)。RD越大，表明算法性能越好。表1给出了不同移动节点比例情况下，文献[3]、文献[4]和本文算法RD指标对比结果。由表1可以看到，本文算法的RD值大于文献[3]和文献[4]所提算法的RD值。说明本文所提算法在WSNs覆盖优化中的性能优于另外两种算法。

表1 RD指标对比

4 结论

本文针对传统群体智能算法单个种群串行寻优容易早熟这一问题，在标准遗传算法的基础上引入多个种群进行改进，通过多个种群并行协同进化不仅收敛速度快而且有效地克服了早熟这一缺陷。同时充分利用了种群进化过程中积累的信息，设计出比是否达到最大迭代次数更为合理的算法终止条件。仿真结果显示，将本文算法应用到混合WSNs覆盖优化问题中，能有效提高网络的覆盖性能。

[1]Joon W L,Ju J L. Ant-Colony-Based Scheduling Algorithm for Energy-Efficient Coverage of WSN[J]. IEEE Sensors Journal, 2012, 12(10): 36-46.

[2] Dimple B, Man J. Maximum Coverage Heuristics (MCH) for Target Coverage Problem in Wireless Sensor Network[A].2014 IEEE International Advance Computing Conference (IACC)[C]. IEEE , 2014:300-305 .

[3] 曾映兰, 陈 静, 郑金华. 基于遗传算法的WSN 覆盖优化方法[J]. 计算机工程与应用 , 2009(11):89-98.

[4] 冯 琳, 冉晓旻, 梅关林. 基于改进粒子群算法的无线传感网络覆盖优化[J]. 太赫兹科学与电子信息学报, 2015(3):486-496.

[5] 王明亮, 闵新力, 薛君志. 基于改进人工鱼群算法的WSN覆盖优化策略[J]. 微电子学与计算机, 2015(6):78-81.

[6] 陈 树, 钱 成. 一种多目标的覆盖优化策略在WSNs 中的应用[J]. 传感器与微系统, 2014(10):151-154.

[7] Zhang Y, Zhang X, Fu W, etal. HDRE: Coverage Hole Detection with Residual Energy in Wireless Sensor Networks[J]. Journal of Communications and Networks , 2014(5):493-501.

[8] 柯 俊， 史文库， 钱 琛，等. 采用遗传算法的复合材料板簧多目标优化方法[J]. 西安交通大学学报,2015(8):1-7.

[9]艾小祥,俞慈君,方 强,等.基于遗传算法的机翼壁板扫描路径优化[J].浙江大学学报,2015(3):448-456.

[10]孙雅庚,郭庆胜,刘远刚,等.顾及格式塔原则的建筑物群移位实数编码遗传算法[J].武汉大学学报,2015(2):269-273.

[11]施荣华,朱炫滋,董 健,等.基于粒子群-遗传混合算法的MIMO雷达布阵优化[J].中南大学学报,2013(11):4499-4505.

Coverage Optimization of Hybrid Wireless Sensor Network Based on Improved Genetic Algorithm

Hu Guolong1, Jia Zhenhong1, Qin Xizhong1,Cao Chuanling2, Niu Hongmei2

(1. School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China;2.Subsidiary Company of China Mobile in Xinjiang, Urumqi 830063, China)

In order to improve the coverage performance,an improved genetic algorithm was applied to coverage optimization of hybrid wireless sensor networks (WSNs).Coverage performance can be improved by changing location of mobile nodes. Traditional intelligence algorithm is liable to fall into the trap of premature and its largest number of iterations is difficult to determine. An improved genetic algorithm is proposed to fill the gaps. Multiple populations can be connected with others by immigration operator. Optimal individual of each population in every generation can be selected by artificial selection operator and recorded by essence of population. A new stopping criterion for iteration is presented according to the recorded information. Simulation shows that our improved genetic algorithm needn't set maximum number of iterations ,has fast convergence rate, and effectively improves coverage performance of WSNs.

wireless sensor network ;coverage;genetic algorithm; immigration operator; artificial selection operator

2015-09-14；

2015-10-26。

中国移动通信集团新疆有限公司研究发展基金项目(XJM2013-2788)。

胡国龙(1990-)，男，河南南阳人，硕士研究生，主要从事传感器网络方向的研究。

贾振红(1964-)，男，河南洛阳人，教授，博士研究生导师，主要从事传感器技术方向的研究。

1671-4598(2016)03-0168-02

10.16526/j.cnki.11-4762/tp.2016.03.045

TP273

A