基于向前式编码策略的无线传感器网络寿命优化遗传算法

摘要

本发明公开了一种基于向前式编码策略的无线传感器网络寿命优化遗传算法。在传统遗传算法的基础上引入向前式编码策略，并将杂交基因遗传运算与三种调度转换方式相结合，使无线传感器网络中的全覆盖子网络数量能够随着运算质量的提高而不断增加，从而达到优化无线传感器网络的寿命的目的。向前式编码策略能够反映出最优的调度方案的结构特征，并能够为调度方案的进一步优化提供指引。基于这种编码策略的三种调度转换策略与遗传算法相结合，能够通过调度冗余传感器，使那些不能完全覆盖的传感器子网络完善成为一个全覆盖的网络，同时又不会影响到其它已满足全覆盖的子网络的覆盖率。

主权项

一种基于向前式编码策略的无线传感器网络寿命优化遗传算法，其特征是：把向前式编码策略引入遗传算法的染色体表达中，使染色体中除了值最大的基因外，其它拥有相同值的基因能各自形成一个全覆盖的传感器子网络，并包括以下步骤和操作：(1)基于向前式编码策略，对种群中的染色体进行初始化，规定拥有相同调度号码，且其数值小于该染色体中基因的最大序号的传感器，各自能组成独立的全覆盖传感器子网络，而具有最大基因值的传感器是否也能成构成全覆盖子网络，则取决于这些传感器对监控区域的覆盖率；(2)染色体Ci的适应度值评估采用如下函数进行计算fi＝ω1ci+ω2pci+1其中ci(ci≥1)表示全覆盖子网络的总数量，pci+1(pci+1∈[0，1))表示第ci+1个子网络的覆盖率(该子网络为非全覆盖)，i＝1，2，...，m，参数ω1与ω2分别代表对ci与pci+1值的权重调整参数；(3)杂交和选择创造新种群，首先在种群C1，C2，...，Cm中随机选择两条染色体Ci和Cj，然后在这两条染色体中以同样的概率按均匀杂交的方式选择基因并将其合成为一个新的子代染色体Ck，新生成的子代染色体Ck将接受种群评估步骤中的公式进行评估，只有不比父代差的子代染色体才会被加入新的种群内，否则该子代染色体将会被比其更优的父代所替代，这个杂交过程重复m次之后，产生新种群Cm+1，Cm+2，...，C2m；(4)每Gm代进行一次变异，在当前种群中的最优染色体Ci中，如果它的最大基因值对应的子网络是非全覆盖的，那么这个非全覆盖子网络中的每个基因gij将以变异率μ进行变异，在非全覆盖的子网络中被选中的基因gij对应的传感器随机变异到另一个全覆盖子网络中；(5)混合调度转换操作对每个染色体依次进行，首先在每一条染色体Ci(i＝m+1，m+2，...，2m)中，随机选取染色体中的一个基因，如果该基因对应的传感器是所属子网络中的冗余传感器，那么将其安排到另一个随机选择出来的全覆盖子网络中；如果该冗余传感器的随机调度数值与选择出的子网络数值相同，那么该冗余传感器将被安排入非全覆盖子网络中，即基因值取值为非全覆盖子网络对应的序号，每个染色体执行混合调度转换K2次；(6)向前调度转换操作对每个染色体依次进行，在每一条染色体Ci(i＝m+1，m+2，...，2m)中，选取K1个基因，如果基因所代表的传感器是冗余的，则将它们调度到Si，ci+1子网络(即未全覆盖子网络)中；(7)关键调度转换操作对每个染色体依次进行，检查每一条染色体中的非全覆盖子网络是否已经覆盖关键区域，如果没有，就从全覆盖子网络中随机选择一个能够覆盖该关键区域的冗余传感器，并将其调度到非全覆盖子网络中；(8)评估种群，如果优化达到停止条件，则终止整个算法并得到最优解；否则，返回第(3)步继续优化种群。