基于混沌遗传算法的无线传感器网络改进LEACH算法

李 蛟, 胡黄水, 赵宏伟, 鲁晓帆

(1. 吉林大学 图书馆, 长春 130012； 2. 吉林建筑科技学院 计算机科学与工程学院, 长春 130114；3. 吉林大学 计算机科学与技术学院, 长春 130012)

无线传感器网络(wireless sensor networks, WSNs)是实际应用中最基本的信息采集技术之一, 其通过内置各种传感器节点测量周围环境中的热、 红外、 声纳和地震等信号. 由于无线传感器网络节点能量等资源有限, 因此如何节约能量以延长网络生命周期是无线传感器网络面临的重要挑战, 而分簇是一种有效的方法[1]. LEACH(low energy adaptive clustering hierarchy)是面向无线传感器网络的最早分簇协议[2], 算法复杂度低, 能量效率和可扩展性相比分布式方法更好. 但基于概率随机选举簇头CH(cluster head)、 成员CM(cluster member)仅根据接收信号强度大小加入簇以及忽略簇头节点剩余能量、 单跳等将导致LEACH簇头、 能耗、 负载分布不均衡, 从而缩短网络的生命周期[3]. 于是, 出现了很多改进LEACH算法以提高其性能[4]. 为避免LEACH协议簇头选取不合理导致能耗增大, 文献[5-6]考虑利用节点剩余能量以及节点分布密度修正LEACH阈值函数, 分别提出了改进的LEACH算法LEACH-N和LEACH-C, 并根据节点分布密度调整节点传输功率, 从而均衡网络能量消耗. 但减小节点传输功率将增加网络簇数, 降低数据融合率并增加传输数据量, 从而增大网络能耗. 且簇头选举不考虑节点位置, 易使位于簇边缘的节点被选为簇头, 增大簇内通信能耗. 因此, 文献[7]提出了一种改进的LEACH算法NEWLEACH, 其在定义阈值函数时, 不仅考虑节点的剩余能量, 同时考虑节点到簇中心距离以及节点到基站距离, 使剩余能量多、 位置更佳的节点成为簇头的概率更大. 但其并未考虑节点负载情况, 且不能处理簇头选举过程的不确定因素. 而通常模糊逻辑对网络中存在大量不确定性时仍能产生较好的结果[8], 于是文献[9]提出了一种基于模糊C-均值(FCM)的改进LEACH算法, 其采用FCM划分区域, 每个区域为一个簇, 将剩余能量大的节点作为簇头. 但FCM初始时随机选取节点成为簇头导致收敛速度慢, 形成的簇中心也并不准确[10], 此外未考虑节点间距离以及簇头与基站间距离将导致距离远的节点出现早死现象.

上述LEACH改进算法都能在一定程度上提高LEACH的性能, 但很难获得全局最优解. 而遗传算法具有良好的全局搜索能力, 因此文献[11-12]采用遗传算法选举簇头, 并根据适应度值修改交叉和变异概率因子, 从而均衡网络能量消耗. 但适应度函数仅考虑剩余能量, 易产生分布不均的簇, 尤其是传统遗传算法收敛速度慢, 容易陷入局部最优. 而混沌遗传算法具有避免搜索过程局部优化、 随机性和遍历性等优点[13]. 因此本文提出一种基于混沌遗传算法的改进LEACH算法CGA-LEACH(an improved LEACH algorithm for wireless sensor network based on chaotic genetic algorithm)最小化网络能耗, 延长网络生命周期. 为实现该目标, CGA-LEACH构建了考量能量和负载的适应度函数, 基于该函数值进行混沌遗传选择、 交叉和变异操作, 找到最优簇头及其相应的簇成员, 从而形成优化的簇结构. 从能量效率以及生命周期方面对CGA-LEACH与其他相关算法进行仿真分析的结果验证了算法性能.

1 网络模型

在CGA-LEACH中, 将n个具有唯一ID能量受限的节点随机部署在目标感知区域. 与LEACH和文献[11-12]相同, 簇被用于组织网络中的节点, 每个簇中选出一个节点作为簇头管理簇, 其他节点作为成员节点. 所有成员节点都只能与其簇头进行通信, 簇头接收各成员节点信息, 融合后直接发送给基站. 一旦完成部署, 节点和基站都保持静止, 所有节点具有相同的初始能量, 基站能量无限, 节点间距离可通过接收信号强度计算, 节点间通信采用双向链路. 为计算节点能量消耗, 采用一阶无线电模型, 即节点i发送l位数据到节点j, 其消耗的能量为

(1)

ERij=l×Eelec,

(2)

簇头融合l位数据消耗的能量为

EDA=l×EpDb,

(3)

其中EpDb表示融合单位数据消耗的能量.

2 CGA-LEACH设计

CGA-LEACH采用混沌遗传搜索最优簇头, 一个可能解用实数编码的染色体(也称为个体)表示, 所有染色体构成初始种群. 在每个染色体中, 由节点ID表示的每个基因代表对应节点的簇头, 如图1所示. 图1中第一行为普通节点ID, 第二行为每个普通节点对应的簇头节点ID. 由图1可见, 染色体不仅能表示每个成员的簇头, 同时也能表示每个簇头包含的簇成员, 这样可减少大量成簇报文, 从而降低能耗. 此外, 由于Logistic混沌映射具有对初值敏感、 良好的随机序列生成、 能遍历混沌区域所有状态点以及不可预测等特点, 因此被用于生成染色体基因, 表示为

图1 CGA-LEACH中的染色体表示Fig.1 Representation of chromosome in CGA-LEACH

(4)

其中:μ是控制参数, 且当μ>3.57,zi≠0.25,0.5,0.75时, 系统进入混沌状态, 与文献[12]相同,μ=4;b为基因最大值,b=n.为避免产生不合理的染色体并提高收敛速度, 仅选择位于节点通信范围内且剩余能量大于平均邻居剩余能量的节点作为簇头, 即

(5)

其中:H={h1,h2,…,hi,…,hk}为簇头节点集,dihi表示节点i与其簇头hi之间的距离,dmax表示所有节点最大通信范围,Ereshi表示簇头节点hi的剩余能量,Eresj表示节点j的剩余能量,nMi为节点i的邻居节点数.如图1所示, 网络由10个节点构成, 簇头数k=4, 簇成员总数m=6, 随机选择簇头H={3,5,8,9}, 则簇成员CM={1,2,4,6,7,10}, 基于式(4)和式(5)随机生成一个染色体, 可得节点1和4的簇头为节点3, 节点2和7的簇头为节点5, 节点6的簇头为节点8, 节点10的簇头为节点9.同时可知, 簇头3的成员有{1,4}, 簇头5的成员有{2,7}, 簇头8的成员有{6}, 簇头9的成员有{10}.以此类推, 直到产生所需的初始种群.然后构建适应度函数评价每个个体的质量, 由于CGA-LEACH主要目标是最小化网络能耗及均衡网络负载, 因此适应度函数考量网络能耗和负载.网络的总能耗为

(6)

其中ETiBS表示簇头i与基站之间的通信能耗.则第p个个体的总能耗归一化表示为

(7)

其中netEmin,netEmax分别为种群中个体最小和最大总能耗.此外, 网络负载均衡用簇头单位数据所需剩余能量表示, 即

(8)

则个体的负载均衡归一化表示为

(9)

其中ltoEmin,ltoEmax分别为簇头中负载均衡最大和最小值.于是, 适应度函数可定义为

(10)

由式(10)可见, 适应度越大的个体越接近最优解, 即此时的网络能耗越小且负载越均衡.CGA-LEACH以能耗最低和负载均衡为目标, 并通过混沌遗传算法搜索其最优解, 与LEACH等未考虑网络能耗的协议相比, 网络能耗更低. 采用适应度函数计算初始种群中每个个体的适应度函数值, 并按从小到大排列. 遗传选择采用与文献[11-12]中类似的精英选择而不是传统的轮盘赌选择方法, 适应度函数值大的为精英个体, 直接选至下一代, 其中精英个体占比为10%, 其他依次与由式(4)随机生成的个体比较适应度函数值大小, 适应度函数值大的进入交叉操作, 这样既保证了种群的多样性又加速了算法收敛. 之后对种群采用单点交叉操作, 如图2所示.

图2 CGA-LEACH中的单点交叉操作Fig.2 Single-point crossover operation in CGA-LEACH

如果生成的子个体大于其父个体的适应度函数值, 则直接进入变异操作. 否则与由式(4)随机生成的个体比较适应度函数值大小, 适应度函数值大的进入交叉操作. 同理, 当变异产生的子个体小于其父个体的适应度函数值时, 也与由式(4)随机生成的个体比较适应度函数值大小, 适应度函数值大的进入下一代. 依此迭代运行遗传操作, 直到达到最大迭代次数或找到最优解, 此时找到了最优簇头以及各簇头对应的成员, 其流程如图3所示.

图3 簇头搜索流程Fig.3 Flow chart of cluster head search

3 仿真分析

为验证CGA-LEACH的性能, 在MATLAB环境下对其进行仿真测试, 并与LEACH[2]以及文献[12]中提出的RPBGK进行比较分析. 网络中100个节点随机分布在100 m×100 m的目标区域, 基站位于中心(50 m,50 m), 仿真参数设置列于表1.

表1 仿真参数

首先对网络的能量消耗进行测试, 结果如图4所示. 由图4可见, LEACH的能量消耗最高, 其次是RPBGK, CGA-LEACH的能耗最低. 因为LEACH采用随机成簇导致分簇不均匀, 一些簇头远离基站, 消耗较高. RPBGK通过遗传K-means算法进行分簇并采用改进的簇头选举方法, 通过多跳方式与基站通信, 从而降低了网络能量消耗, 但RPBGK会产生多个较远簇头向某个离基站较近的簇头转发数据的现象, 从而使离基站较近的簇头负担过重而导致能量消耗不均匀. CGA-LEACH考量了网络能耗和负载均衡构建适应度函数, 生成了均匀的簇, 避免了RPBGK中能耗不均匀现象发生, 而且CGA-LEACH相对减少了成簇控制报文, 从而降低了网络能量消耗. 因此, CGA-LEACH具有最高的能量效率.

图4 网络能量消耗Fig.4 Network energy consumption

由于节点能量资源有限, 作为层次型的无线传感器网络, 簇头在每一阶段都需要比普通节点消耗更多的能量. 因此, 簇头的能量消耗偏差是网络性能的重要评价指标, 其表明了网络的能耗均衡性. 不同算法簇头的能量消耗偏差如图5所示. 由图5可见: RPBGK采用遗传K-means成簇, 比LEACH随机成簇更均匀, 因此其能量消耗偏差比LEACH更好； 而CGA-LEACH 在网络运行中考虑了簇头的负载, 使每个簇的能量消耗相对均衡, 因此相比LEACH和RPBGK算法, CGA-LEACH具有最低的簇头能耗偏差, 分别比RPBGK和LEACH平均降低了40.54%,50%. 因此CGA-LEACH在提高簇头节点的能量效率方面也具有优势.

图5 簇头的能量消耗偏差Fig.5 Energy consumption deviation of cluster heads

图6为CGA-LEACH,RPBGK和LEACH之间的存活节点个数随着轮数增加的变化. 由图6可见: LEACH的存活节点个数在648轮后迅速下降, 在1 194轮后仅剩1个节点; RPBGK的存活节点个数在201轮后开始下降, 在2 268轮网络的所有节点全部死亡; 而CGA-LEACH的存活节点个数在361轮后开始缓慢下降, 直至3 465轮所有节点全部死亡. 这是因为CGA-LEACH考量了网络能耗和负载两个指标构造新的适应度函数, 从而找到了能耗最低和负载最均衡的簇, 延长了网络的生命周期.

图6 网络的存活节点数Fig.6 Number of surviving nodes in network

综上所述, CGA-LEACH基于遗传算法的全局搜索能力形成网络能量最小的簇, 单个实数编码的染色体既能表达选择的簇头, 又能确定各簇头对应的成员, 减少了成簇阶段大量的控制报文数, 降低了网络能耗. 本文构建的适应度函数既考虑了网络能耗又考虑了簇头负载, 使形成的簇分布更均匀. 混沌计算既用于初始化种群, 又融入遗传选择、 交叉和变异操作, 在丰富种群多样性的同时提高了算法收敛速度和避免算法陷入局部最优. 从能量消耗、 负载均衡以及网络的存活节点个数方面对算法进行仿真分析的结果表明, CGA-LEACH能有效提高网络能量效率, 延长网络生命周期.