基于遗传算法和后代校正的WSN覆盖和连通性优化方案

何常胜， 赵小河， 陈 安

(1.韶关学院 韶州师范分院 计算机系，广东 韶关 512009)(2.广东工业大学 实验教学部，广东 广州 510006)



基于遗传算法和后代校正的WSN覆盖和连通性优化方案

何常胜1*， 赵小河1， 陈 安2

(1.韶关学院 韶州师范分院 计算机系，广东 韶关 512009)(2.广东工业大学 实验教学部，广东 广州 510006)

针对无线传感器网络(WSN)区域覆盖中传感器部署的覆盖性和连通性问题，提出一种基于改进型遗传算法的WSN覆盖和连通性优化方案.首先，将传感器位置编码成染色体.然后，通过遗传算法的交叉和变异操作进化染色体，获得新的解.最后，融入后代校正操作，以避免遗传算法获得的不可行解，最终获得传感器布置的最优方案.实验结果表明，该方案在不同的覆盖范围和通信范围下，能够利用最小数量的传感器实现区域k-覆盖并保持连通性，有效降低了部署成本.

无线传感器网络；k-覆盖；连通性；遗传算法；后代校正操作

本文提出一种基于融合后代校正操作的遗传算法(GA)的传感器k-覆盖部署方案，在任何Rcom/Rcov下，都能够以最小数量的传感器实现区域全覆盖和连通性.与现有经典几何部署模式相比，本文方案使用的传感器数量最小，有效降低了部署成本.

1 问题描述

本文研究的目的是使用最小数量的传感器实现一个二维传感区域的完全覆盖，同时传感器之间需要建立有效的连接，以使每个传感器可以通过中继路由到达基站.假设传感区域为M×N的网格模型，相邻两点之间的距离为1个测量单元.位于(i,j)的传感器的传感范围为Rcov，通信范围为Rcom，其中Rcom≥Rcov.

2 提出的优化方案

本文提出一种改进型遗传算法，并以此对WSN覆盖和连通性进行优化.遗传算法中，通常具有以下三个主要步骤：初始种群、交叉操作和变异操作.此外，还需要指明三个必要的参数：交叉率、突变率和停止条件.然而，在交叉操作后，会出现不符合连通性约束的解[7]，这时就需要执行本文提出的后代校正操作，使交叉后代满足约束.

2.1 初始种群

在遗传算法中，初始种群为一组具有Np个初始解决方案组成.这里解决方案又称为染色体或个体，其包含有限数量的基因[8].本文中的一个染色体包含一张2K个或M×N个基因的表，其中，K表示网络中的传感器数量.第一种染色体类型中，K个基因中的每个基因p包含传感器位置(i,j)的行i，基因K+p包含传感器位置(i,j)的列j.第二种染色体类型中，基因p表示网格位置(i,j)和一个二进制数，当(i,j)放置传感器时，该二进制数为1，否则为0.本文使用第一种染色体编码形式，因为它使用较少的内存，染色体表示如图2所示.表1描述了染色体生成算法步骤.

图3给出了一个宽度为5、长度为10的测量单元，Rcov、Rcom都为2个测量单元的网格网络染色体解决方案构造的过程.图3中，第一次随机选择的传感器位置为(i,j)=(2,2).子集F为不包含基站位置且可以与(2,2)通信的未选择位置的集合，即F={(1,2)；(1,3)；(2,1)；(2,3)；(2,4)；(3,1)；(3,2)；(3,3)；(4,2)}，如图3(a)所示.对应于位置(2,2)，从F中选择出能够覆盖最大数目的未覆盖点的传感器位置(3,5)，并更新W={(2,2)}和F，那么此时F={(1,2)；(1,3)；(2,1)；(2,3)；(2,4)；(3,1)；(3,2)；(3,3)；(4,2)；(3,4)；(3,5)；(4,3)；(4,4)；(5,3)}，如图3(b)所示.重复该过程，直到获得一个能够实现覆盖整个网格网络和连通性的完整解决方案.

2.2 交叉操作

本文交叉操作阶段，至少产生一个新的后代解决方案.在交叉步骤中，首先要选择两个父母.之后，新的后代解决方案从第一个父母继承一些基因，并保留第二个父母的剩余基因[9].遗传算法中父母基因的选择过程如下：首先按照适应度值升序排列染色体.然后，选择第一个父母，并随机地从剩余的30个染色体中选择另一个父母.接着，选择第二个父母，并随机地从剩余的30个染色体中选择另一个父母，直到选择到第30个父母为止.在每对父母(pi,pj)选择后，在[1，…，N-1]中选择一个随机整数k.新的后代解决方案从第一个父母继承第一个基因(对应于网格中M×k位置的传感器).之后，将剩余的基因(对应于网格中M×(N-k)位置的传感器)加入到第二个父母的后代中.当后代解决方案同时满足连通性和完整覆盖后，交叉操作停止.

当后代解决方案不满足任何一个约束时，执行本文提出的一种校正操作，移动传感器到未连接传感器旁边，使未连接传感器能够通过该中间传感器与整个网络连接，表2描述了后代校正算法步骤.图4描述了选择两个父母进行交叉操作的步骤， 图5描述了校正后代解决方案的例子.

表1 染色体产生算法Tab.1 Theflowofchromosomegenerationalgorithm表2 后代校正算法流程Tab.2 TheflowofoffspringcorrectionalgorithmW≠∅:所选的传感器位置集合F:未被选择且可以与W中的传感器进行通信的位置集合随机选择的传感器位置(i,j)≠(l,w)while(未达到全覆盖),执行循环 a:确定F b:选择F中能够覆盖最大数目未覆盖位置的传感器位置(s,t) c:W=W∪(s,t)Endwhile1:while(未满足完整覆盖),执行循环选择一个能够覆盖最大数目的未覆盖位置的传感器位置(i,j)Endwhile2:while(未满足连通性约束),执行循环选择未连接的传感器位置(i,j)选择与(i,j)最近的传感器位置(k,t)通过添加必要的传感器将(i,j)与(k,t)相连Endwhile

2.3 变异操作

变异操作为从种群中选择一个染色体，对基因进行一个小的修改.GA中的变异操作的主要目的是获取一个局部最优解，并多元化下一代[10]. 在本文的算法中，设置变异率为个体基因数量的5%.从种群中随机选择染色体进行变异操作，对所选的个体执行以下轻微修改：首先，添加染色体方案中一些已连接的传感器；然后，对于每个可以连接到所添加传感器的传感器，验证其是否可以被移除.所选染色体中添加的传感器总数为染色体基因总数的5%.

3 实验及分析

利用NS2仿真器构建不同大小的WSN环境，在intel i 7-3720QM CPU 2.60 GHz的计算机平台上实现.设定网格网络的宽度M和长度N的取值范围分别为{9，12，14}和{9，12，14}.覆盖范围Rcov和通信范围Rcom从集合{2，3，4}中选取.设定基站位置为(1,1).

3.1 与常规部署模型的比较

设置网络网格大小为14×14，进行实验，将本文部署方案与4种常规的传感器部署模式：六边形模式(Hex)、正方形模式(Squ)、三角形模式(Tri)和菱形模式(Rho)进行比较.在常规部署模式中，本文使用节点覆盖区域最大化来划分部署区域，分别获得4种模式覆盖区域所需的最小节点数量.图6描述了常规六边形覆盖模式(Hex)示例，其中角落的未覆盖区域会通过增加2个传感器来实现全覆盖.

图7给出了本文方案和常规4种部署模式，在不同的传感和通信范围下覆盖14×14网格网络所需的最小传感器数量.从图7可以观察到，本文方案获得的解决方案所需的传感器数量总体小于常规部署模式，其中在(Rcom,Rcov)=(2,3)和(2,4)时，所需传感器数量与一些模式相同.综上所述，对于测试的绝大多数(Rcom,Rcov)，在实现全覆盖和连通性所需传感器数量方面，本文提出的GA覆盖方案优于一些常规的部署方式.

3.2 与智能算法的比较

将本文采用的改进型GA算法与蚁群优化(ACO)算法进行比较.对于本文GA算法，设定染色体规模为60条，交叉率为50%，突变率为5%.在不同覆盖范围和通信范围下的对比结果如表3所示.可以看出，本文方案获得的解优于传统ACO方案，这是因为本文采用了后代校正算法，优化了传统GA算法获得的不可行解，保证后代的可行性.

表3 两种算法所需最小传感器数量的对比结果

4 结束语

本文提出一种改进型GA算法，用于WSN中传感器部署的优化.相比于传统的临界网格覆盖问题，本文添加传感器之间连通性的约束.仿真结果表明，本文方案在不同的通信和传感半径下，实现区域全覆盖和连通性所需的最小传感器数量优于一些常规部署模式.

在今后的工作中，将考虑网络中存在多种可调通信和覆盖半径的传感器，通过合理调整传感器的通信半径来实现以最小传感器数量覆盖整个网络，并均衡节点能耗、最大化网络寿命.

[1] 张鹏, 马小南. 基于路由协议的无线传感器网络源位置隐私保护探究[J]. 湘潭大学自然科学学报, 2014, 36(1):110-114.

[2] KE W C, LIU B H, TSAI M J. The critical-square-grid coverage problem in wireless sensor networks is NP-Complete[J]. Computer Networks, 2011, 55(9): 2 209-2 220.

[3] LEE J W, LEE J J. Ant-colony-based scheduling algorithm for energy-efficient coverage of WSN[J]. Sensors Journal IEEE, 2012, 12(10): 3 036-3 046.

[4] AMMARI H M, DAS S K. Centralized and clusteredk-coverage protocols for wireless sensor networks[J]. Computers Transactions on IEEE, 2011, 61(1): 118-133.

[5] WOEHRLE M, BROCKHOFF D, HOHM T, et al. Investigating coverage and connectivity trade-offs in wireless sensor networks: The benefits of MOEAs[J]. Multiple Criteria Decision Making for Sustainable Energy & Transportation Systems, 2010, 63(4): 211-221.

[6] KHASTEH S H, SHOURAKI S B, HAJIABDORAHIM N, et al. A new approach for integrated coverage and connectivity in wireless sensor networks[J]. Computer Communications, 2012, 36(1): 113-120.

[7] 单曦靓，孙 燕. 基于遗传算法的WSN移动信标定位及路径求取[J]. 计算机工程与应用, 2011, 46(30): 95-97.

[8] JIA J, CHEN J, CHANG G, et al. Find the maximumk-disjoint coverage sets in WSN using genetic algorithm[J]. International Journal of Modelling Identification & Control, 2010, 9(4): 251-259.

[9] 孙泽宇, 邢萧飞. WSN中一种规则区域最优覆盖与连通算法研究[J]. 计算机科学, 2011, 38(5): 79-82.

[10] INDHUMATHI S, VENKATESAN D. Improving coverage deployment for dynamic nodes using genetic algorithm in wireless sensor networks[J]. Indian Journal of Science & Technology, 2015, 8(16): 362-370.

责任编辑：龙顺潮

WSN Coverage and Connectivity Optimization Scheme Based on Genetic Algorithm and Offspring Correction

HEChang-sheng1*,ZHAOXiao-he1,CHENAn2

(1.Department of Computing, Shaozhou Normal Branch of Shaoguan University, Shaoguan 512009; 2.Department of Experiment Teaching, Guangdong University of Technology, Guangzhou 510006 China)

For the issues that the coverage and connectivity of sensor deployment in wireless sensor networks (WSN), a WSN coverage and connectivity optimization scheme based on improved genetic algorithm is proposed. First, the location of the sensor is encoded as chromosome. Then, the crossover and mutation operator of genetic algorithm are evolved to obtain a new solution. Finally, the offspring correction operator is used to avoid the genetic algorithm to obtain the infeasible solution. At last, the optimal scheme of sensor placement is obtained. Experimental results show that the proposed scheme can achieve regionalk-coverage and maintain connectivity with the minimum number of sensors under different coverage and communication range, effectively reduce the deployment cost.

wireless sensor networks;k-coverage; connectivity; genetic algorithm；offspring correction operator

2016-02-05

韶关学院校级科研项目(SZSF20120301)

何常胜(1976-)，男，广东 韶关人，讲师.E-mail:hechangssgn@126.com

TP393

A

1000-5900(2016)02-0089-05