遗传算法 (GA) 是一种基于自然选择原理和自然遗传机制的搜索 (寻优) 算法。在GA算法中，染色体某一位置上具有相同位值的染色体的子集合通常称为基因模式 (schemata)。在遗传算法中，模式阶次指基因模式中定义位置 (即为0或l) 的个数，而模式定义长度则为基因模式中两个最外定义位置之间的距离。模式阶次O(H) 和定义长度$\sigma (H)$是量化基因模式。基于此定义，由已知的第n代群体中基因模式H的数目m(H, n)，可得到n+1代群体中基因模式H的期望数下界为：

式中，$f(H)$为基因模式H的适应度；l为染色体C的位串长度；${f_{{\rm{av}}}}$为群体所有染色体的平均适应度；${P_{\rm{c}}}$为杂交概率；${P_{\rm{m}}}$为突变概率。

那么，实现GA算法基本流程为：1) 初始群体的产生；2) 求每一个个体的适应度；3) 根据适者生存的原则，选择优良个体；4) 被选出的优良个体两两配对；5) 通过随机交叉和变异某些染色体的基因，生成下一代群体。按此方法使群体一代代的进化，直到满足进化的终止条件。

具体实现方法：根据具体问题确定可行解域和编码方法，用字符串或数值串表示可行解域的每一个解。选取适应度函数为每一个解的度量依据。适应度函数为非负函数，本文选取GA的适应度函数为：

式中，d为节点间的距离；n为选择的节点个数；$\pi $为编码方法。

确定进化参数群体规模M、交叉概率${P_{\rm{c}}}$、变异概率${P_{\rm{m}}}$、进化终止条件。

本文选用自适应方法选取杂交概率，有:

本文采取自适应方法选取变异概率，有:

式中，

${\alpha _1}, {\alpha _2}, {\alpha _3}, {\alpha _4}$为随机数，且${\alpha _1}, {\alpha _2}, {\alpha _3}, {\alpha _4} \in [0, 1]$。

LEACH算法采用随机方式选取簇首，在LEACH协议中，WSN执行过程是周期的，系统更新一次称为一轮，一轮包括簇的建立和稳定运行阶段。在簇的建立阶段，簇首会换届选举，即对节点n随机选择一个值，若该值小于一个阈值，则节点n成为本轮的簇首节点。阈值的表达式为：

式中，p是簇首节点占总节点的百分比；r是当前轮次。本文根据式 (5) 选举簇首。

通过本文设计的如图 1所示算法流程对WSN引入交通层路径进行算法优化：

图  1  引入交通层的总程序流程图

1) WSN的初始分簇

WSN在工作后首先建立网络，各节点用浮点编码表示^[8]，根据相互距离通过GA算法进行分簇^[9]，得到一个最优的初始簇首情况。

2) WSN选举出簇首

在同一簇的WSN中，本文在LEACH算法中引入能量与距离因素，每一轮中通过一个优化的阈值对同簇的WSN进行选举，选出最合适的簇首。

在LEACH算法中式 (6) 的r为当前轮次，为一固定的值。本文用剩余能量值和与交通层的距离d对r值进行修正。

节点剩余能量的计算为：

式中，RemEng代表节点剩余能量；PktT代表发送数据包数量；TEng代表发送一次数据包所消耗的能量；PktR代表接收数据包的数量；REng代表接收一次数据包需要的能量。

最终r修正的表达式为：

式中，d为簇首与待选交通层的距离。

3) WSN引入交通层

簇首选举完后，簇首收集一轮簇内数据^[10-12]，并对簇首与基站之间建立交通层，即引入中间节点与基站通信。根据簇首节点的实际分布情况，可以利用GA算法对其进行最优的初始化设计，这使路径设计最优化。通过调整交通层的个数，便可以根据需求获得所需的WSN的工作距离，具有很好的适应性。图 2为交通层拓扑图。

图  2  交通层的拓扑结构

根据WSN簇首的分布情况，结合能量和距离因素式 (7) 对不同的情况采用不同的拓扑设计，分别为共用拓扑、平行拓扑以及复合拓扑。

① 共用拓扑：多个簇首节点共享一个交通层与基站进行通信。在工作量较少、信息传输要求较低的区域，这种设计有利于提高资源利用率。② 平行拓扑：单个簇首节点通过特定的交通层与基站进行通信。在工作量较高、信息传输要求较高的区域，这种设计有助于增强WSN传输的实时性。③ 复合拓扑：簇首与交通层之间综合使用共用拓扑和平行拓扑结构，形成一对多、多对一、多对多的复杂结构来满足实际应用中的需求。

网络复杂程度越高，交通层的设计越精细，WSN的性能也就更接近实际的需求。本文利用GA算法对簇首接入交通层的拓扑进行基于能耗与距离情况的实时优化更新，其具体操作方式如图 3所示。

图  3  共用拓扑结构

在每一轮簇的建立阶段之后，要对簇首接入交通层的拓扑形式进行更新，本文对GA算法的初始适应度函数进行了优化，其中初始适应度函数为：

式中，d为簇首与待选交通层的距离。

根据WSN簇首在实际运用中簇首工作量的不同，引入一个实时变化的权值$\eta $描述各个节点的忙碌程度，其表达式为：

式中，RemEng为节点剩余的能量；InitEng为初始总能量。系统会优先对$\eta $值较高的簇首进行分配。同理引入$\mu $值对交通层忙碌程度进行描述，有：

式中，k为交通层中第k个节点；n代表共有n个簇首接入这个节点中；${\eta _i}$对应第i个接入交通层的当前能耗大小。最终GA算法的适应度函数优化为：

由式 (7)、式 (8) 和式 (10) 可知，节点能耗越高，距离交通层越远，被选为簇首的概率越小。

4) 簇首换届交换交通层钥匙

在簇首换届选举之后，上届簇首发送一个数据包给下届簇首告知对应的交通层节点的地址，而本身遗忘交通层地址，这种设计相对于AODV协议的自适应找寻方式的优势在于只需要发送一次数据包便可以完成路径的建立，有效减少了AODV自适应过程的通信能耗和延迟时间。同时这种密匙交换的方法，降低了WSN节点记忆性能要求，可以减少能耗和降低成本。

本文基于MATLAB，首先使用GA算法对WSN的节点进行初始分布的最优化设计，使用LEACH算法选举第一届簇首，然后对没有引入交通层和引入交通层分别进行了仿真和研究，仿真程序流程如图 4所示，并对结果进行了可视化显示。其中对于优化LEACH算法式 (9)，仿真数值由表 1所示。

图  4  仿真程序流程图

WSN分布可视化显示结果如图 5所示，对其耗能情况进行了显示，图中的图例代表了产生的能耗大小。本文发现簇首能量远大于普通节点，簇首内部耗能也不均匀，同时耗能最多的为AODV协议中比较重要的节点。而引入交通层后普通节点和簇首之间能耗差别减小，簇首内部也相对均衡，且分布情况也优于AODV路由协议。

图  5  WSN分布可视化显示

簇首能耗情况在实际应用中尤为关键，本文对每个簇首的能耗进行了跟踪记录，结果如图 6所示。

图  6  各个簇首耗能情况仿真图

仿真数据表明，AODV协议中能耗最多的节点在本文算法仿真结果中减少了约95%的通信能耗，其他关键节点也有较大的减少。少部分节点对整体能耗有9%左右增加。

对比图 6中的仿真结果可知，在AODV协议中，簇首之间的能耗随着时间增加而呈现发散关系，簇首之间耗能也极为不均，关键节点耗能过大。在100轮后，簇首通信能耗的最高和最低值相差10倍。这是AODV协议设计所决定的必然现象，离基站较近簇首的能耗远大于离基站较远簇首的能耗，并且两者随着时间的增加而差距越来越大，使得能耗高的簇首寿命大大降低。

在引入交通层拓扑的优化算法中，簇首只需负责收集簇内节点信息与交通层通信，节省了AODV算法自适应的通信能耗。距离基站的远近对簇首能耗情况不再有影响，能耗均匀性相对AODV协议有了很大程度上的提高。仿真结果显示，簇首之间能耗虽然略有差距，但在100轮内，已无明显的发散现象，发现簇首之间能耗几乎相等，均匀性十分理想。

引入交通层的优化协议相对于AODV协议，簇首提高1~3倍的寿命。在AODV协议中能耗越高的节点，其在引入交通层之后寿命提高得越多。

本文研究通过引入交通层对AODV自适应算法进行优化，利用GA算法完成簇首与交通层的复杂拓扑的实时设计，发现对完全自适应的整体加入复杂实时的固定的优化因素，会将其整体性能向所期望的优化方向转化。本文所研究的新型WSN拓扑结构以及根据能耗与距离因素的分配方法有效提升了WSN总体寿命，减少了大部分WSN簇首的能耗 (往往这些簇首处于比较关键的位置)，对WSN的性能进行了很大的提升。而本文的优化设计不足在于新节点的引入增加了WSN的整体的一定能耗，也使WSN之间的协议关系相对比较复杂。所以在不引入新的节点的情况下，对WSN整体性能进行优化是一个非常有价值的命题，讨论也更加的复杂而有意义。