基于遗传算法和蚁群算法的LEACH改进协议

徐 巍，钟宇超，余成成

(湖北工业大学 机械工程学院，湖北 武汉 430068)

0 引言

在无线传感器网络中,无线传感器节点一般由电池供电,但是电池的电量有限且不便于更换,无线传感器网络节点的工作寿命受到很大限制[1],因此如何降低无线传感器网络的能量损耗是该领域的研究重点[2-3]。

低功耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy,LEACH)型协议是一种能够延长无线传感器网络生命周期的经典分簇路由协议[4],但是该协议选举簇头节点随机性太强,可能选出较差的簇头节点,而且传输路径较采取单跳模式会消耗大量能量。目前已有许多学者针对上述问题提出了一些新的改进算法。池涛等[5]采用K-means聚类算法进行分簇,将簇内的节点基于所在的位置进行分层,簇头节点根据节点所处层次和剩余能量进行选举,可以延长网络运行时间,但前层节点死亡过早会造成网络的节点能耗不均衡。Heinzelman等[6]在LEACH协议的基础上提出了LEACH-C协议,解决了节点根据随机数决定是否当选为簇头节点的问题,并确定了每轮的簇头节点数量,提高了簇头选举的合理性,但并没有减少传输数据阶段的能量损耗。杜永文等[7]根据节点剩余能量和节点的位置用模糊算法选举簇头节点,并在数据传输阶段采用多跳传输模式。Kulik等[8]提出了一种定向扩散的路由协议,外部节点会根据基站发出的信息选择合适的方向进行数据传输。王波等[9]通过节点的剩余能量、当前节点未成为簇头节点的轮数来选举簇头节点。苗俊先等[10]提出一种非均匀的分簇路由算法,引入双簇头机制,并采用单跳和多跳相结合的方式进行数据传输。喻小惠等[11]改进了状态转移函数,使节点更容易选择周边节点密集度较高的节点作为下一跳,但是没有考虑方向,若朝反方向移动反而会增大传输路径。

综合考虑上述情况,本文在簇头选举和数据传输阶段都进行改进。在分簇阶段用遗传算法选出剩余能量多、距离基站距离近及周围节点多的节点作为簇头节点,并在没有节点死亡的情况下进行簇内选举簇头;在数据传输阶段,综合考虑路径上节点的剩余能量和节点的位置2个因素,用蚁群算法得到最佳传输路径,最终通过仿真实验可以证明本文改进算法的网络生命周期得到了显著延长。

1 LEACH协议分析

1.1 LEACH协议介绍

LEACH协议是周期性的分簇路由协议,每轮循环分为簇头选举阶段和数据传输阶段。每一轮开始前,所有节点都会取一个[0,1]的随机数,如果该节点的随机值小于这一轮的阈值T(n),则该节点被选为这一轮的簇头[12];否则该节点为普通节点。阈值T(n)可表示为:

(1)

式中:p为簇头节点在网络中所占的比例,r为已经循环的轮数,G为这一轮循环之前还未当选簇头的节点集合。

簇头节点产生后,簇头节点把自己成为簇头节点的消息向周边广播,普通节点根据信号的强弱选择想要加入的簇头节点,并给该簇头节点发送加入请求,当簇头接收到普通节点的请求后,采用TDMA的方式为其分配一个传输数据的时隙。分簇完成后,普通节点把数据发送给该簇的簇头节点,簇头对数据进行融合压缩处理后,采用单跳的方式把数据转发给基站。

1.2 LEACH协议的不足

1.2.1 传统LEACH协议的不足

①簇头节点的选举具有随机性,能量较低的节点被选为簇头节点后,该节点会因消耗过多能量而死亡,进而影响整个网络的节点分布。

②如果普通节点到簇头节点的距离比该普通节点到基站之间的距离更远,普通节点先把数据传输给簇头节点,簇头节点再转发给基站会消耗更多的能量。

③簇头节点与基站采取的是单跳的传输方式,如果簇头节点与基站相距较远,超出了阈值d0,采用多路径衰减模型进行传输会消耗簇头节点大量能量,导致其死亡。

1.2.2 现有LEACH改进协议的不足

目前已有许多针对传统LEACH协议的不足之处进行改进的算法,但这些算法存在一定的缺陷。

①采用簇内分层模型会导致整个网络的能量消耗不均。前层节点的能量消耗较大,会过早耗尽能量而死亡,进而影响网络节点的分布。

②只是对簇头选举的阈值函数进行改进,簇头与基站的传输方式依然为单跳模式,传输距离过大会增大簇头节点的能耗,最终会导致优化效果不佳。

③优化传输路径一般只考虑了路径的剩余能量和路径的长度,如果忽略传输的方向,传输距离反而会因此增加。

2 系统模型

2.1 网络模型

本文对无线传感器网络节点做出以下假设[13]:

①每个节点都是独一无二的且带有编号;

②所有节点的初始能量和功能完全一样,彼此之间能正常通信且都具有成为簇头节点的资格;

③整个网络处在静态环境下,节点的位置随机分布且不会发生任何改变;

④基站的计算和处理能力非常强大,且拥有无限的能量供给;

⑤节点可以根据信号的强度计算传输距离。

2.2 能耗模型

LEACH协议使用的是一阶无线电模型,发送端节点与接收端节点之间的距离会影响传输数据阶段的能量消耗,设发送端节点与接收端节点之间的距离为d,数据包大小为lbit,发送单位比特电路所消耗的能量为Eelec,自由空间信道模型及多路径衰减模型下的放大器的功率放大倍数分别为εfs与εamp。能耗模型示意如图1所示。

图1 能耗模型Fig.1 Energy consumption model

发送电路消耗的能量为:

(2)

接收电路消耗的能量为:

Erx(l)=lEelec,

(3)

式中:d0为数据传输距离的一个阈值,如果2个节点的传输距离大于d0时,则采用多路径衰减模型进行传输,否则将采用自由空间信道模型进行传输[14-15]。d0可以直接计算得到:

(4)

3 LEACH协议的改进

针对以上LEACH协议的不足之处,本文分别对簇头的选举和数据传输路径进行优化改进。

3.1 基于遗传算法选举簇头节点

LEACH协议中,簇头节点会比普通节点消耗更多能量,能量较少的节点无法完成簇头节点需要完成的工作,因此需要选出最合适的节点担任簇头节点。为了防止剩余能量不足或者距离基站较远的节点被选举为簇头节点,本文采用遗传算法来优化簇头节点的选举。

3.1.1 编码方式

本文采用二进制的编码方式对网络节点进行编码,即由二进制数0和1组成的字符串来表示,这种编码方式简单易于操作[16]。网络中所有节点都有唯一的节点编号,在遗传算法中这些编号随意排列组成多条染色体。每个节点编号对应的位置表示该节点的状态,如图2所示,数字0代表普通节点,数字1代表簇头节点。

图2 染色体示意Fig.2 Chromosome diagram

3.1.2 适应度函数选取

本文把节点的能量、所在位置以及周边节点数量3个因素列入簇头节点选举的条件,并根据这3个因素设计出适应度函数,计算所有节点的适应度函数值,适应度函数值高的节点被选为簇头节点。

首先考虑能量因子,让剩余能量更多的节点选为簇头节点。设节点i的剩余能量为Ei,网络中节点剩余能量的最大值和最小值分别为Emax和Emin。本文衡量节点剩余能量的计算如下:

(5)

然后考虑位置因子,让离基站更近的节点成为簇头节点。令簇头节点i与基站之间的距离为di,节点到基站距离的最小值和最大值分别为dmin和dmax,本文衡量节点位置的计算如下:

(6)

最后考虑邻居节点密度因子,让周边节点数目多的节点成为簇头节点。网络中共有n个节点,节点i在一定的半径内含有的邻居节点的数目为ni。衡量节点邻居节点密度的计算如下:

(7)

节点的能量因子、位置因子以及邻居节点密度因子的权重系数分别用fE、fD、fN表示,权重系数的取值为[0,1],且满足α、β、γ的取值之和为1,适应度函数的计算如下:

Fit_function=αfE+βfD+γfN。

(8)

若节点的剩余能量越多、位置距基站越近且周边邻居节点数目众多,则该节点的适应度函数值就越大,该节点成为簇头节点的概率越大。

3.1.3 选择操作

本文采用比例选择方法和精英选择方法相结合的选择方式[17],计算出所有节点的适应度函数值。为了避免遗传算法出现早熟现象,把适应度函数值排在前20%的节点作为精英个体并遗传给下一代;其他节点进行交叉和变异操作。

3.1.4 交叉和变异

本文采用两点交叉方式,随机选择2条染色体进行交叉操作,计算生成的子染色体的适应度函数并与父染色体进行比较,适应度函数值大的遗传至下一代;适应度函数值较小的染色体进行变异处理,变异后再计算其适应度函数。如果多次迭代后满足:

(9)

则算法停止计算,其中ε0为一个任意小的正数,本文设为10-5。适应度函数最大的个体为最优解,并把其值加入下一轮运算,加快算法的收敛性。

将适应度函数数值高的节点作为最初始的簇头节点,并完成分簇,下一轮的簇头节点将在已划分好的簇中进行簇内选举。

3.1.5 优化簇头阈值函数

若直接采用LEACH协议的簇头选举阈值函数进行簇内簇头选举,通过遗传算法形成的初始簇群将会受到破坏,因此本文对LEACH协议的簇头阈值选举函数进行改进,把遗传算法的适应度函数加入到阈值函数中,改进后的簇头阈值函数为:

(10)

式中:popt为最佳簇头的选举概率。

(11)

多次进行簇内选举簇头会造成各个簇群的剩余能量不平衡,因此本文在基于遗传算法的簇内簇头选举阶段提出一种簇群重新划分机制:若有节点出现死亡现象,则在下一轮簇头选举阶段之前,重新用遗传算法进行簇头选举并划分新的簇群。

3.2 基于蚁群算法寻找最佳传输路径

由于LEACH协议在簇头与基站进行数据传输阶段统一采用单跳模式,这会导致距离基站较远的簇头节点在该阶段消耗过多能量并死亡,因此本文采用蚁群算法寻找簇头节点到基站的最佳传输路径。

3.2.1 蚂蚁的转移概率

(12)

式中:τij(t)为节点i到节点j路径上的信息素量,其权重为α1,权重越大,蚂蚁更可能选择之前已经探索过的路径;ηij为启发函数,其权重为β1,权重越大,蚁群就更容易选择最短的路径;Jk(i)为第k只蚂蚁下一跳的所有节点集合,节点u为蚂蚁的下一跳为节点,τiu(t)、ηiu(t)分别为节点i到节点u路径上的信息素和启发函数[18]。

3.2.2 改进信息素因子

为了使整个网络的能耗相对均衡,需要让蚂蚁进行均衡分流,从而得到最优解,因此本文信息素的更新方式加入了能量因素。

(13)

(14)

3.2.3 改进启发函数

由于启发函数ηij(t)的值只取决于2个节点之间的距离,如果蚂蚁选择一个离基站更远的节点作为下一跳节点,传输路径反而增大了。因此本文加入第三个节点u对启发函数进行改进,3个节点的位置关系如图3所示。节点i、j、u之间的距离分别为dij,、diu、duj,改进后的启发函数为:

(15)

图3 节点位置关系Fig.3 Node location relationship

若节点i、j之间的中间跳点u距离直线ij更近,ηij(t)的值就更大,蚂蚁选择节点u作为下一跳的概率更大。

3.3 算法流程

本文改进算法流程如图4所示。首先对网络参数进行初始化;然后在簇建立阶段使用遗传算法得到最佳簇头节点并划分簇群,当算法进行下一轮时,若没有节点死亡,则采取簇内选取簇头节点,否则再次进行遗传算法重新得到新的簇头群;最后在数据传输阶段采用蚁群算法寻找最佳传输路径,簇头节点将其簇群普通节点采集到的数据融合整理后转发至基站,发送完成之后开始下一轮,直至程序运行到设定的轮数,算法结束。

图4 改进算法流程Fig.4 Improved algorithm flowchart

4 算法仿真与分析

4.1 仿真环境

为检验本文改进算法的可行性,用Matlab软件对LEACH、LEACH-C和本文改进算法分别进行仿真实验,仿真数据如表1所示。

表1 仿真数据Tab.1 Simulation data

4.2 仿真结果与分析

图5为改进算法程序后期节点死亡情况。由于簇头选举时考虑了簇头节点与基站的距离因素,因此靠近基站的节点更容易被选为簇头节点。簇头节点消耗的能量要远大于普通节点,更容易优先死亡,所以程序后期时,靠近基站的节点基本上已经死亡。

图5 程序后期节点死亡情况Fig.5 Node death situation in the later stage of the program

图6为LEACH、LEACH-C以及本文算法在相同环境下的节点死亡情况。可以看出,LEACH与LEACH-C在分别在第750轮和第850轮左右时出现节点死亡,且分别在第1 300轮和第1 400轮左右时全部节点死亡。而本文算法在第1 400轮左右时才出现节点死亡且在第1 550轮左右时节点全部死亡,可见本文算法的节点耗能更加平均、节点不容易过早死亡,而且网络的生命周期也得到了延长。

图6 网络节点死亡数目比较Fig.6 Comparison of the number of death network node

由于节点是随机分布的,整个网络的生命周期会因此受到影响,为了避免单次仿真的偶然性,进行多次实验并记录每次实验中第一个死亡节点出现的轮数。图7为3种算法多次仿真实验得到的第一节点死亡的轮数,可以看出,本文算法出现第一个节点死亡的时间远晚于另外2种算法,再次验证了本文算法的能耗更加均衡、节点不容易过早死亡。

图7 第一死亡节点出现的轮数Fig.7 Number of rounds in which the first death node occurs

图8为3种算法在相同环境下的能耗情况。可以看出,本文算法的能耗曲线一直位于LEACH、LEACH-C能耗曲线的上方,LEACH协议与LEACH-C协议分别在第1 300轮和第1 400轮左右耗尽能量,但本文算法的能量维持到第1 600轮左右才耗尽。由此可见本文算法的网络总能量消耗速度更慢、网络的生命周期更长。

图8 网络总能量消耗比较Fig.8 Comparison of total network energy consumption

图9为3种算法第一个节点死亡、最后一个节点死亡、节点平均生命周期及首尾2节点死亡间隔的轮数对比图。可以看出,LEACH和LEACH-C的首尾2个节点死亡相隔了550轮左右,而本文算法只经历了141轮,远小于LEACH和LEACH-C协议经历的轮数,说明改进算法的网络能耗更均衡、所有节点的死亡时间更接近。

图9 节点死亡情况比较Fig.9 Comparison of death node situations

5 结束语

本文主要研究无线传感器网络中的节点能耗问题,希望在随机分布的网络区域内能够选出最合适的簇头节点并找到最节能的传输路径。由于LEACH路由协议在选举簇头节点和数据传输2个地方都有一定的缺陷,因此本文针对该缺陷进行一定改进:用遗传算法解决簇头节点选择不当的问题,随后用蚁群算法解决数据传输阶段能量消耗过大的问题。通过仿真实验,可以验证改进后的LEACH协议能够更好地使网络能耗更均匀,网络的生命周期更长。