一种基于平均剩余能量的无线传感器网络分簇路由算法

鄢丽娟，张彦虎

(广东松山职业技术学院计算机系，广东 韶关 512126)

0 引 言

无线传感器网络是由数量庞大的传感器节点以自组织、多跳的工作模式组建的网络[1-2]。随着“互联网+”、物联网和智慧城市的引入,无线传感器网络技术在各个领域已得到了充分的肯定和应用[3]。现如今，无线传感器网络已广泛应用于许多生活领域中，基本涵盖了国防军事、预报救灾、环境监测、医疗监护、智能家居等多个领域[4-5]，具有非常广泛而巨大的市场应用前景。无线传感器网络中存在的节点能量受限问题，对网络性能和网络寿命产生严重影响。设计稳定且低能耗的无线路由协议对保障网络通信、延长网络寿命具有重要的意义[6-7]。

文献[8]提出了一种基于最优传输距离和K-means聚类的WSN分簇算法；文献[9]提出了节点路由选择与基站全局调节相结合的双层规划的跨层能耗均衡路由协议；文献[10]提出了簇的能耗均衡的概念，但是仅以固定簇为单位，缺少整体网络概念，限制了其应用；文献[11]提出了一种综合考虑单个节点传输能耗和总传输能耗的路径规划算法；文献[12]提出了一种在保证能耗均衡的基础上基于蚁群算法的无线传感器路由改进算法。

本文从能量优化的角度，针对LEACH协议分簇算法成簇机制导致的能耗不均衡问题，提出基于平均剩余能量的分簇路由算法LEACH-BAE。在簇头选举机制上，引入全域网络节点平均剩余能量的概念[13]，以平均剩余能量为主要参数，选举合适的簇头，提出由基站在对全域节点情况了解的基础上分析得出最佳簇头位置及簇头数量，可均衡网络能耗，延长网络的生存周期。

1 LEACH算法

LEACH(低功耗自适应聚簇分层协议)[14]是一种经典、成熟的层次路由协议算法，此算法最早由Heinzelman提出[15]。其基本思想是采用轮流当簇头的方式，每一轮主要的工作就是成簇和稳定通信[16-17]。该算法的核心思路是减少节点与基站的直接通信的能耗，通过分层按簇进行数据融合提高数据处理效率，降低网络能量损耗，延长整个网络的生存时间[18]。

1)成簇。

在成簇阶段，算法要实现2个功能：簇头选举和成员加入。其中簇头选举是整个算法的核心关键。在成簇过程中，每个节点首先按照预期的网络簇头百分比和其担任过簇头的次数，综合设置出一个阈值T(n)，然后各个节点随机产生一个[0，1]范围之间的数，并与T(n)相比较，若某节点产生的随机数小于预设的阈值T(n)，则该节点当选簇头并同时向网内节点广播自己成为簇头的消息[19-20]，阈值T(n)计算公式如下：

(1)

其中，p为预期的簇头百分比(簇头节点占所有节点的比例值)，r为当前轮数，G表示第r轮之前从没有当选过簇头的节点集合，假如某节点在此轮(r轮)前已多次担任了簇头工作，则将T(n)重置为0，这样避免出现一些节点连续担任簇头的情况，实现了将能耗均衡分摊到每个节点的目标。

簇头选举完成后，其他非簇头成员节点根据接收到的广播信号强度，选择信号强度最大的簇头发送请求加入簇。

2)稳定通信。

稳定通信阶段主要工作是数据传输。构建成簇之后，簇内节点将各自采集到的数据传给簇头节点，然后簇头节点进行融合处理接收数据，再将融合的数据结果转发给基站，完成该轮数据传输任务后，重回成簇阶段进入下一轮工作。

LEACH算法有很多优点，比如，每个节点公平竞选簇头，每一轮由不同的节点担任簇头，较好地均衡了网络负载；簇头对接收到的各个簇内节点数据会进行数据融合处理，再转发给基站，可以极大地精减冗余数据。但是，该算法同时存在一定的不足：

①簇头分布不均匀[21]。LEACH协议采用随机方式产生簇头节点，可能会导致若干个簇头距离太近甚至簇头大面积集中在一个区域内的情况，2个簇头间隔太近或若干个簇头集中在一个区域，会导致普通节点与簇头节点通信的距离增加，从而造成区域内能量消耗增大，簇头节点数量分布不均匀的情况。

②无线传感器网络节点能量消耗不均衡。LEACH协议强调，网络中每个节点在每一轮中都会轮流做一次簇头，成功地将能量消耗分散在所有节点上，有利于整个网络能量的节约，但是，这种均衡的做法未考虑到节点距离基站的远近对能量消耗的影响。距离基站越远的地方，节点因为需要将信息传输到更远的地方，其能量消耗相对距离簇头或基站较近的节点而言，耗损也更快，即节点距离基站的远近直接影响着其能量消耗的快慢。如果机械地使每个节点均匀轮流做簇头，对距离较远的节点而言，显然是不公平的。

2 LEACH-BAE算法

针对上述LEACH协议的不足，本文提出一种改进的基于平均剩余能量的路由算法LEACH-BAE(Low Energy Adaptive Clustering Hierarchy-Base on Average Energy)。本算法在原LEACH协议的基础上做适当的改进，使其所产生的簇头能更均匀地分布在全无线传感器网络范围之内，同时，簇头选举过程是在基站对全域网络内节点信息掌握的基础上产生，簇头的产生过程是基于全域能量消耗均衡的意图作为主要指标进行衡量，即每次簇头的产生要基于均衡全域网络节点能量而进行，要避免甚至杜绝出现剩余能量低于全域节点平均剩余能量的节点做簇头，防止因节点过早死亡而致使全域网络过早瘫痪或消亡的情况。

为了能确保簇头算法的正常运行，本文对普通节点和簇头节点的数据结构分别规划如表1、表2所示。

表1 普通节点数据结构

表2 簇头节点数据结构

为了能实现第一次网络通信，需要在全域网络范围内产生部分簇头，使其收集全域网络节点信息、传输控制指令及传输部分数据，此时，簇头的产生采用传统LEACH协议簇头的产生方式，各节点产生一个随机数，当随机数小于T(n)时，该节点为簇头，否则为普通节点。初始簇头节点产生之后，向全域广播自己成为簇头，附近节点加入该簇，组成网络。将全域网络中所有节点的基本信息收集后发给基站，其中包括各节点的坐标、剩余能量等，基站获取到全域节点信息之后，运行分析程序，根据全域网络节点的实际分布情况，进行簇头的分派。

2.1 最优簇头数量的确认

假定全域网络的长和宽分别是wd、ht，一跳的距离为j1，且假定3个变量的单位统一，如图1所示。为了避免簇头扎堆产生，令新簇头不会产生在所有已产生簇头的j1范围之内。

图1 节点一跳间距示意图

如果在阴影区域内出现簇头A，则在以A为原点，j1为半径的区域内，不会产生第二个簇头节点，其他的簇头必定产生在该区域以外的位置，据此，只需求得完全覆盖整个网络区域需要多少个圆形阴影图形就可获得最优簇头数量，即可以通过公式(2)计算求得最优簇头数量：

(2)

对式(2)结果向下取整后得到的CNum即为最优簇头的数量，wd、ht分别为网络区域的长和宽，j1为一跳的距离。

2.2 平均剩余能量

为了确保所选举的簇头节点的剩余能量大于全域节点的平均剩余能量EAvall，需要先求出EAvall的值，其运算过程为：

(3)

其中,ECi为节点Si的剩余能量，n为全网无线传感器节点的数量。

2.3 簇头选举

2.3.1 首轮簇头选举

采用LEACH算法原理选举首轮簇头，初始簇头将全域网络节点的基本信息传输给基站，为基站进一步分析网络节点的实际情况做准备，为全域网络节点与基站建立一条通道和桥梁。

2.3.2 LEACH-BAE协议簇头选举

LEACH-BAE协议中除初始簇头节点之外，其余的簇头都是由基站根据全域网络节点的实际情况进行分派的，在选择簇头时，使用的主要参数为全域网络节点的剩余能量均值EAvall。

簇头选举实现的主要伪码见算法1。

算法1簇头选举算法。

for k从1执行到n

获取随机数i;

if(节点S(i)的剩余能量>平均剩余能量EAvall)

if(簇头数量为0)

该节点S(i)为簇头节点

else

计算该节点到第一个簇头节点C(1)的距离mdis;

for c从簇头1执行到目前簇头的个数

计算节点S(i)到簇头C(c)的距离temp_dis;

if(temp_dis

则mdis的值设置为temp_dis;

end

end

if(mdis的值大于系统设定的dis)

该节点S(i)为簇头节点;

end

end

k++;

end

if(簇头数量为0>CNum)

break;

end

end

在算法1中，n为全区域内节点的数量，S(i)为普通节点，C(c)为簇头节点，CNum为最优簇头数量，EAvall为全域节点平均剩余能量。此算法循环n次，即全域网络内所有节点都有机会被抽取到作为备选簇头节点，在算法中，依次做了簇头数量是否达到最优簇头、剩余能量是否达到要求、与已产生的簇头节点的间距是否符合要求等。

2.4 节点成簇阶段

若各普通节点在接收到初始簇头信息进行对比之后，发现自己不是簇头节点，则获取基站分配给自己的簇头节点号C(i)、需要调整的发送频率等信息，并在LEACH-BAE协议簇头节点产生后，向周围簇头节点发出加入请求，确保该节点的簇头能接收到加入簇头C(i)的信息。

若节点对比后发现自己是簇头节点，则接收基站发送的含有簇成员等信息的数据包，并设置自己为簇头节点。

簇头节点接收到普通节点的加入请求之后，将该节点标志为已加入，同时依据已接收的基站数据包中的簇成员信息，检查属于本簇的节点是否已全部加入，如果是，为所有簇成员分配时间片区并发送给簇成员，然后关闭组网，并向所有成员节点发送组网成功并退出组网的通知，进入数据传输环节。

2.5 数据传输阶段

各普通节点在指定的时间片区发送收集的数据及自己的剩余能量等信息；簇头节点接收数据并对数据融合处理后，将所收集的簇内节点数据信息及各节点的能量剩余情况发送给基站；基站定期定时对全域的实际情况进行分析，计算出全域平均剩余能量，并分析实际情况指定簇头及其簇成员，然后将信息发送给当前簇头节点并要求重新组网；簇头节点接收到重新组网的指令及新簇头节点等信息后，向全域广播相关信息，并进入下一轮的组网重构。

3 仿真实验及分析

本文在MATLAB R2016模拟仿真平台上，基于算法在M×M区域的平面上进行模拟实验，设M的值为100 m。使用模拟软件在该区域内随机产生100个节点，部分关键参数设置为：节点的初始能量为0.02 J，数据包大小为4000 bit，控制包为32 bit，基站位于平面的中心位置；对LEACH-BAE协议和LEACH协议分别作了100次的实验，对该100次的实验数据进行对比分析。

1)簇头数量。

通过100次实验，每次运行1000轮，随机抽取，得到250轮和1000轮以内的2张簇头数量对比图，如图2和图3所示，通过图形分析能直观地得出：LEACH协议产生的簇头数量波动幅度比较大，到后期会频繁出现簇头为1的情况；LEACH-BAE协议生成的簇头相对比较稳定，前期因使用随机产生簇头法生成簇头，产生的簇头数量比较多，后期系统会自动平衡各种因素，将簇头的数量控制在合适的范围之内，同时，随着存活节点的减少，簇头节点的数量也会很明显有规律地进行适当调整，达到更好节约能量的目的。其中LEACH方差为3.94，LEACH-BAE协议方差为2.36。在选举的簇头数量方面，LEACH-BAE协议的效果要优于LEACH协议的算法。

图2 250轮簇头数量动态对比图

图3 1000轮簇头数量动态对比图

2)成簇情况。

原LEACH协议簇头布局与LEACH-BAE协议簇头布局对比：

在原LEACH协议中，因为在簇头产生过程中，对未做过簇头的节点采用随机方式产生，可能会出现若干个簇头节点集中在一起扎堆的情况，如图4所示。因为簇头节点要承担与基站的通信，其能量消耗相对而言要比普通节点高很多，在图4所示的2个圆形框选区域里产生分布的几个簇头距离太近，而个别节点的通信距离又太远，造成全域节点能量消耗过快，有进一步提升改进的空间。

图4 LEACH协议簇头产生过于集中现象

在LEACH-BAE协议算法中，在簇头产生的过程中加入了一个限定条件，即符合做簇头条件且被系统选中拟产生的新簇头，需要跟已经确定为新一轮簇头的所有节点做数据分析，如果该节点与已确定的簇头列表中的任何一个簇头的距离小于设定值dic，则该节点不能做簇头。在这种条件下，系统中产生的所有簇头节点，一定不会有若干个节点扎堆出现的情况，在一定程度上避免了过多的能量消耗，降低了全域网络节点的能量耗损，增加了节点的存活时间。修正后的簇头布局如图5所示。

图5 LEACH-BAE协议簇头分布优化效果图

3)剩余能量。

本文对LEACH和LEACH-BAE协议所做的100次1000轮的测试中，将能被100整除轮次的剩余能量进行记录，然后求100次的平均值，对比发现如图6：LEACH-BAE协议相比LEACH协议，LEACH-BAE协议全域平均剩余能量要大于LEACH，其中前600轮次，LEACH-BAE协议的领先程度更多，600轮次之后，两者的剩余能量差距逐渐减少，都趋向于0。

图6 平均剩余能量对比折线图

4)基站接收数据对比。

基站的接收数据对比如图7所示，在前420轮，LEACH-BAE与LEACH发送的数据量基本相同，420轮之后，LEACH-BAE向基站发送的数据量保持高速增长的势态，而LEACH算法的增长速度明显放缓，说明改进算法LEACH-BAE的网络吞吐量更大，其数据通信能力更强。

图7 基站接收数据对比

4 结束语

LEACH-BAE算法对LEACH协议的簇头选举方式和簇间数据到达基站的传输方式实施了一定的改进，引入了全域网络节点平均剩余能量的概念，并且在簇头选举的过程中，只有大于平均剩余能量，才有机会成为簇头，虽然在算法中未考虑每个节点的公平性，但从整体而言，它能更好、更有效地将重负荷的簇头节点的工作均衡地布置给更合适的节点，使整个网络能量的耗散更加均衡，尽可能地使更多的节点生存更长的时间。通过仿真实验对比，改进的LEACH-BAE算法在均衡全无线传感器网络节点能量消耗及延长网络生存周期等方面具有较明显的优势。