基于遗传算法实现确定性区域覆盖的传感器节点

摘　要：随着传感器技术大量应用于安防、监测等领域，覆盖成为了无线传感器网络的一个基本问题,反映了网络监测和实现目标跟踪的质量效果。本文主要针对传感器节点初始覆盖有约束条件的情况,研究了确定性区域传感器覆盖问题。提出了基于约束遗传算法的覆盖机制。仿真结果表明该算法能快速收敛于最优解,完成有约束条件的传感器初始覆盖,从而实现传感器网络的快速优化覆盖。

关键词：遗传算法； 确定性区域覆盖； 传感器节点部署
1． 引言
无线传感器网络，是由部署在观测环境附近的大量微型低功耗的传感器节点组成的多跳自组织网络系统,目的是实时检测、感知和采集各种对象的信息，WSN广泛应用在军事国防、环境监测、危险区域等监测和办公建筑的环境控制等领域。网络覆盖是其基本问题之一，直接影响着监测结果的准确性和全面性。
　　按照无线传感网节点不同配置方式，可以将WSN的覆盖问题分为确定性覆盖、随机覆盖 。文献范围内的节点表达有效信息，因此定义Nv为基因G的有效长度。
3.2.2 初始种群的选取
　　首先将待覆盖区按照六边形覆盖方法进行全区覆盖，得出方案，然后在W上添加H。显然，圆心处于椭圆中的圆是无效的，我们先除去这类圆。将此种圆分布方案编码，作为种群中的第一个个体V0。种群规模为Sa，对种群中的个体交替应用变异策略和繁殖策略，并对新个体应用相应的约束处理，直道个体总数达到Sa。
3.2.3个体的适应度
   个体的适应度用目标函数定义，则适应度函数为f=-。在此过程中对于不可行个体，即适应度为-个体，保持其适应度?f=-，不重新计算。
3.2.4 选择策略
　　在一次迭代中，对种群中所有个体按照其适应度排序，取位于前50%的个体作为下一次迭代的父代个体，从种群中去除后50%的个体。
3.2.5 繁殖策略
　　在一次繁殖中，个体Vi完全复制其自身，生成一个与其完全相同的个体Vj。全部个体繁殖完成之后，每个个体随机选择一个与其基因不相同的个体与其配对，也就是说Vi不可以选择Vi，进而进行杂交。
3.2.6 杂交策略
　　针对本题的特点，杂交后各个圆的位置不应当有太大的变化，因此采用交换杂交策略。个体Vi和个体Vj进行杂交时，从中Gi随机选择一些结点，则在Gi和Gj的有效长度之内，将这些结点与 Gj中与其下标相同的结点互换。例如Gi随机选择的结果是：3，8，15，则将和Gi[3]和Gj[3]互换，Gi[8]和Gj[8]互换，Gi[15]和Gj[15]互换。随机选择的概率为Pc。
3.2.7变异策略
　　在一次迭代中，对每一个体，要在其基因中随机选择若干结点，改变该点的取值，这个概率即为个体的变异概率，为Pm。改变某结点（xi，yi）的取值的方法是：取一个上的[1,1000]随机数且xi,取一个上的[1,1000]随机数且yi，用(,)替代（xi，yi）。
3.2.8 约束处理
　　不满足约束条件的个体称为不可行个体。对于不可行个体，对其在一定范围内进行修补，如果修补后的个体满足约束，则用修补后的个体替换原个体。如果修补失败，将其适应度调整为-，则该个体将在选择过程中被淘汰。
3.2.9终止条件
　　本算法采取如下两条终止条件：迭代次数限制：迭代次数超过Tf，则算法终止。适应度饱和：如果最近E次的迭代的最优适应度梯度之和小于某一阈值h，则算法终止。即h时，算法终止
3.2.10控制参数选择及结果
本问题的控制参数为：Sa=100,Pc=0.3,Pm=0.005,Tf=10000,h=10-5,在此组控制参数下得到的分布方案如下图所示：
4. 结语
　　本文研究了有约束条件的无线传感器网络区域优化覆盖问题,提出了基于遗传算法的确定性优化覆盖机制,给出了实验结果.结果表明,本文提出的机制能够解决提出的问题。本文不足，只研究了传感器数量较小，覆盖区域内有单个约束区的情况，其他情况还需进一步研究。
参考文献
[1] Yuri B Shtessel,McDuffie J。Sliding mode control of the X-33 vehicle in launch and re-entry mode [R] .Boston:Marshall Space Flight Center,1998
[2]李明,石为人.异构无线传感器网络中基于模拟退火算法的成本最优部署机制[J].传感技术学报,2010,23(6):855-858.
[3] 赵仕俊，张朝晖，无线传感器网络正六边形节点覆盖模型研究。网络与通信，2010，10
1 作者简介：张雅楠（1982-），男，天津市蓟县人，在读工程硕士，学历：本科，研究方向：传感器网络应用，项目管理。