基于GA和LEACH的WSN引入交通层路径优化算法

李玉霞，徐永鑫，何 磊，张向秀

(1. 电子科技大学自动化工程学院 成都 611731；2. 成都理工大学国土资源部地学空间信息技术重点实验室 成都 610059；3. 电子科技大学光电信息学院 成都 610054；4. 成都信息工程大学软件工程学院 成都 610225)

基于GA和LEACH的WSN引入交通层路径优化算法

李玉霞1,2，徐永鑫3，何 磊4，张向秀3

(1. 电子科技大学自动化工程学院 成都 611731；2. 成都理工大学国土资源部地学空间信息技术重点实验室 成都 610059；3. 电子科技大学光电信息学院 成都 610054；4. 成都信息工程大学软件工程学院 成都 610225)

针对WSN节点中分层分簇路由算法存在能耗不均衡、簇首能耗高的问题，提出了一种基于GA和LEACH的WSN引入交通层路径优化算法。该算法基于ZigBee协议引入了新的拓扑结构，并优化了基于距离和能量因素的阈值函数，从而对WSN进行优化。仿真结果表明，在增加9%整体耗能的前提下，减少了关键簇首95%的通信能耗，有效地提高了WSN能耗均匀性，并延长了WSN 1～3倍的整体工作寿命。

遗传算法; 交通层; 无线传感网络; ZigBee协议

无线传感网络(WSN)是目前国内外的前沿和热门研究方向，在工业监测和控制、家居自动化和安全、军事监控和追踪等方面有着广泛的应用[1]。因WSN节点有效运行的时间有限，所以如何减少能耗是WSN应用和研究中的关键难题。ZigBee是一套常用、自适应、减少能耗的WSN路由协议[2]，它主要使用Cluster-tree协议[3]和AODV(Ad hock on-demand distance vector)协议[4]来构建系统。在Cluster-tree协议中通过分簇选取簇首的方式收集簇内信息，簇首间用ADOV协议相互搜索自适应基站通信。Clustertree的问题在于簇首的能耗远远高于普通节点，使簇首的寿命大大减少，而簇首节点失效将导致该簇上的所有节点与基站失去联系。AODV的缺陷主要有根据自适应路由协议寻找的路径可能不是最优路径、实时性不足、能耗高、系统能耗均匀性差等。

针对上述存在的问题，文献[5]在LEACH协议中考虑了能耗因子，从而有效延长了WSN的运行周期，但没有探讨距离因素。文献[6]研究表明了遗传算法在WSN路径优化中的有效性，找到了优化路径并成功避开了能耗低的节点，但未对具体能耗情况进行深入分析，并且在距离方面也讨论不足。文献[7]在WSN中引入了中间层从而达到了均匀能耗的效果，但是只根据距离因素采用动态路由方式对路径进行构建，一定程度上忽略了能量因素以及拓扑结构的优化研究。本文针对ZigBee的Cluster-tree以及AODV路由协议现有的不足，通过引入新的拓扑和中间节点(下面称为交通层)，及与之匹配的综合考虑能量与距离因素的优化算法，来均匀簇首能耗，从根本上解决簇首能耗大的问题以及WSN整体能耗均匀性问题。

1 GA算法和LEACH算法

1.1 GA算法

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

式中，f(H)为基因模式H的适应度；l为染色体C的位串长度；fav为群体所有染色体的平均适应度；cP为杂交概率；Pm为突变概率。

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

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

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

确定进化参数群体规模M、交叉概率cP、变异概率Pm、进化终止条件。

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

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

式中，

1.2 LEACH算法

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

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

2 WSN引入交通层路径优化算法

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

1) WSN的初始分簇

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

2) WSN选举出簇首

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

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

节点剩余能量的计算为：

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

最终r修正的表达式为：

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

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

3) WSN引入交通层

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

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

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

图2 交通层的拓扑结构

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

图3 共用拓扑结构

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

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

根据WSN簇首在实际运用中簇首工作量的不同，引入一个实时变化的权值η描述各个节点的忙碌程度，其表达式为：式中，RemEng为节点剩余的能量；InitEng为初始总能量。系统会优先对η值较高的簇首进行分配。同理引入μ值对交通层忙碌程度进行描述，有：

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

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

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

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

3 算法仿真结果与分析

图4 仿真程序流程图

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

表1 仿真模拟参数

3.1 可视化分布结果

图5 WSN分布可视化显示

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

3.2 簇首能耗情况

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

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

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

3.3 簇首能耗均匀性情况

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

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

3.4 簇首寿命情况

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

4 结论与探讨

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

本文的研究工作得到了成都市科技局项目(2014-HM01-00122-SF)的资助，在此表示感谢！

[1] HESHAM A, YANG S H. Dynamic cluster head for lifetime efficiency in WSN[J]. International Journal of Automation and Computing, 2009, 6(1): 48-54.

[2] YOUNIS O, FAHMY S. Distributed clustering in Ad-hoc sensor networks: a hybrd, energy-efficient approach[C]// Proc 13th Joint Conf on IEEE Computer and Communications Societies. [S.l.]: IEEE Computer and Communications Societies, 2004.

[3] 李剑, 景博. 自适应遗传算法在多边议题协商中的应用[J]. 北京邮电大学学报, 2008, 31(6): 67-70.

LI Jian, JING Bo. Adaptive genetic algorithm and its application in multi-lateral multi-issue negotiation[J]. Journal of Beijing University of Posts and Telecommunications, 2008, 31(6): 67-70.

[4] SHARMA R, LOBIYAL D K. Proficiency analysis of AODV, DSR and TORA Ad-hoc routing protocols for energy holes problem in wireless sensor networks[J]. Procedia Computer Science, 2015, 57: 1057-1066.

[5] 饶皓, 袁健. 基于节点生存时间的WSN节能路由算法[J].计算机工程, 2012, 38(10): 99-101.

RAO Hao, YUAN Jian. Energy efficient routing algorithm in WSN based on node survival time[J]. Computer Engineering, 2012, 38(10): 99-101.

[6] 雷霖, 李伟峰, 王厚军. 基于遗传算法的无线传感器网络路径优化[J]. 电子科技大学学报, 2009, 38(2): 227-230.

LEI Lin, LI Wei-feng, WANG Hou-jun. Path optimization of wireless sensor network based on genetic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(2): 227-230.

[7] 吕林涛, 范永林. 能量均衡的WSN非均匀分簇路由算法[J]. 计算机工程, 2009, 35(21): 117-119.

LÜ Lin-tao, FAN Yong-lin. Energy-balanced WSN uneven clustering zouting algorithm[J]. Computer Engineering, 2009, 35(21): 117-119.

[8] 杨挺, 孙雨耕, 杨郁, 等. 无线传感器网络中一种节省资源的快速重路由算法[J]. 传感技术学报, 2005, 18(3): 445-448.

YANG Ting, SUN Yu-geng, YANG Yu, et al. A resourceefficient fast rerouting for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2005, 18(3): 445-448.

[9] YI Y K, KIM H. Agent-based geometry optimization with genetic algorithm (GA) for tall apartment’s solar right[J]. Solar Energy, 2015, 113: 236-250.

[10] 陈拥军, 袁慎芳. 无线传感器网络最小能耗拓扑控制研究[J]. 电子科技大学学报, 2012, 41(4): 568-573.

CHEN Yong-jun, YUAN Shen-fang. Minimum energy consumption topology control for wireless sensor networks [J]. Journal of University of Electronic Science and Technology of China. 2012, 41(4): 568-573.

[11] MEDAGLIANI P, MARTALÒ M, FERRARI G. Clustered zigbee networks with data fusion: characterization and performance analysis[J]. Ad Hoc Networks, 2011, 9: 1083-1103.

[12] 王瑞锦, 秦志光, 王佳昊.. 无线传感器网络分簇路由协议分析[J]. 电子科技大学学报, 2013, 42(3): 400-405.

WANG Rui-jin, QIN Zhi-guang, WANG Jia-hao. Analysis of wireless sensor network cluter routing protocol[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(3): 400-405.

编 辑 漆 蓉

Path Optimization Method in Transportation Layer of WSN Based on Genetic Algorithm and LEACH

LI Yu-xia1,2, XU Yong-xin3, HE Lei4, and ZHANG Xiang-xiu3

(1. School of Automation Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. Key Laboratory of Geoscience Spatial Information Technology of Ministry of Land and Resources, Chengdu University of Technology Chengdu 610059; 3. School of Optoelectronic Information, University of Electronic Science and Technology of China Chengdu 610054. 4. College of Software Engineering, Chengdu University of Information Technology Chengdu 610225)

To solve the problems of unbalanced energy consumption and the high energy consumption of header cluster effectively in the wireless sensor networks (WSN), the paper proposes an optimized transportation layer algorithm which is based on the genetic algorithm (GA), low energy adaptive clustering hierarchy (LEACH) algorithm, and ZigBee protocol. The algorithm introduces a new type of topological structure and improves the threshold function based on distance and energy consumption for WSN. The simulation results show that the proposed algorithm can achieve a 95% reduction of communication energy consumption of key cluster head with 9% increase of overall energy consumption, thus effectively improving the uniformity of the energy consumption of WSN, and extending 1～3 times working life of the whole WSN.

genetic algorithm; transportation layer; wireless sensor networks (WSN); ZigBee protocol

TP274.1

A

10.3969/j.issn.1001-0548.2017.03.012

2016 − 03 − 16；

2016 − 12 − 06

国家自然科学基金(60841006, 4157133)；国土资源部地学空间信息技术重点实验室开放基金(KLGSIT2016-08)

李玉霞(1979 − )，女，副教授，主要从事定量遥感及其应用、无人机图像处理、空间信息提取等方面的研究.