何常胜， 赵小河， 陈 安

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



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

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

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

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

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

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

1 问题描述

本文研究的目的是使用最小数量的传感器实现一个二维传感区域的完全覆盖，同时传感器之间需要建立有效的连接，以使每个传感器可以通过中继路由到达基站.假设传感区域为M×N的网格模型，相邻两点之间的距离……