改进LEACH的传感器网络分簇路由算法

潘继强， 冯永政

(陕西理工大学 数学与计算机科学学院, 陕西 汉中 723000)

随着通讯技术、 信息技术的快速发展, 许多微型传感器节点被部署在一个区域, 采用自组织、 协作方式进行信息和数据的通信, 形成一个无线传感器网络, 对目标的监测信息进行收集, 数据采集的成本低, 在工业、 农业、 军事等领域应用广泛[1-6]. 在无线传感器网络的实际应用中, 通常需要考虑网络的安全性、 数据的通信成本、 数据传输的实时性及网络能耗等问题. 无线传感器网络通常采用无线通信方式, 部署在人无法达到的环境中, 而且传感器节点的电池能量有限, 节点能量一旦消耗完毕, 节点就会在网络失效, 导致数据丢失, 因此节点能耗是无线传感器网络路由算法的关键[7].

无线传感器网络路由算法旨在建立一条通信路由, 将节点、 目标与信息最终使用者联系起来, 在数据传输中一些节点的死亡会影响数据转发, 簇首的死亡会导致整个无线传感器网络过早失效, 缩短生存时间[8]. 目前, 无线传感器网络路由算法主要分为平面型和分层型两类. 平面型的无线传感器网络路由算法中传感器节点的地位对等, 没有簇首, 所有节点处于一个平面, 组网过程简单、 易维护, 由于没有管理节点, 全部传感器节点参与数据传输, 节点能耗大、 能量浪费严重, 当网络拓扑结构发生变化时, 路由算法的动态调整能力差, 因此只适合小规模的无线传感器网络, 无法适应当前大规模无线传感器网络的应用要求[9-11]. 分层型的无线传感器网络路由算法将整个网络划分为多个簇, 每个簇又包括簇首和普通节点, 因此又称为分簇路由算法. 簇内的普通节点信息均要发送到簇首, 簇首对信息进行选择性收集, 并转发到基站, 减少数据转发的次数, 节约节点能量, 可扩展性强, 相对于平面路由算法, 生存时间明显延长, 已成为当前主要的无线传感器网络路由算法[12]. 低功耗自适应分簇(low energy adaptive clustering hierarchy, LEACH)算法是最经典的分簇路由算法， 其以簇为基础, 簇在不断地重建, 一次簇重建称为一轮, 但基本的LEACH算法有许多局限性, 如簇首选择、 能量消耗不均衡等， 因此出现许多改进的LEACH算法, 如LEACH-K算法、 LEACH-R算法等, 相对于LEACH算法, 改进算法的性能有一定的提高, 但仍存在不足, 如网络生存时间短、 簇首死亡过快等[13-15].

针对当前无线传感器网络分簇路由算法的节点能耗不平均、 节点过早死亡等缺陷, 本文提出一种改进LEACH的无线传感器网络分簇路由算法. 先引入簇半径动态调整方式将网络划分为多个不均匀的簇, 再综合簇首的位置和节点剩余能量选择每轮中的簇首, 对数据传输机制进行优化. 仿真测试结果表明, 本文改进LEACH算法的能耗、 网络生存时间、 节点能量利用率等性能均显著优于当前其他分簇路由算法, 具有较高的实际应用价值.

1 系统模型

1.1 网络体系结构

无线传感器网络的基站常位于监测区域外部, 负责将无线传感器网络采集的信息发送给信息最终使用者, 能量不受限制, 具有无限的通信能力. 在整个监测区域内有大量传感器节点, 初始能量相同且能量受限, 在工作过程中由于能耗完毕而不断死亡, 位置一旦部署完后即固定不变, 它们可分为簇首和普通节点, 均有一个编号, 通过单跳或多跳方式将信息发给基站. 无线传感器网络的拓扑结构[16]如图1所示. 一个传感器节点通常包括4个功能模块： 传感、 数据处理、 通信和能量供应. 传感模块主要负责数据的感知和采集, 将模拟信号转换为数字信号； 数据处理模块主要负责数据处理, 如数据融合去冗余； 通信模块主要负责节点之间的信息传输； 能量供应模块主要负责节点的能量管理. 通信模块包括发送、 接收、 空闲和睡眠状态, 所有模块的能量如图2所示. 由图2可见, 节点在感知与数据处理的能量消耗相对较少, 睡眠状态消耗的能量也少, 发送、 接收、 空闲状态下消耗能量较大, 因此降低节点通信的能耗是延长网络生存时间的关键.

图1 无线传感器网络的拓扑结构Fig.1 Topology structure of wireless sensor networks

图2 传感器节点的能量消耗分布Fig.2 Energy consumption distribution of sensor nodes

图3 无线通信模型Fig.3 Wireless communication model

1.2 能耗模型

传感器节点的无线通信模型如图3所示, 包括发送能耗模型和接收能耗模型. 发送能耗主要为信号发射和信号放大电路消耗的能量, 接收能耗主要为信号接收电路消耗的能量[17]. 当信号发射距离为d时, 发送和接收kbit数据的能量消耗计算公式为

其中：Ee表示发射电路能耗；εamp表示信号放大电路能耗；n表示衰减指数.

2 LEACH算法

LEACH算法的步骤如下.

1) 确定簇首和分簇. 每个节点均可成为簇首, 每个节点均产生一个随机数rand( ), 将rand( )与门限阈值T(n)进行比较, 若满足条件rand( )≥T(n), 则该节点即为簇首,T(n)计算公式为

(3)

其中:p为簇首的百分数；r为轮数；G为不是簇首的节点集.

某个节点一旦成为簇首, 就会向整个网络广告消息, 不是簇首的节点会收到多个簇首广播的消息, 加入到接到信号强度最大的簇首所在的簇, 并向簇首发送加入信息, 因为信号强度越大, 表示距离越近, 接发消息的能耗越少.

2) 建立时隙表. 完成分簇后, 簇首根据簇内节点数产生时隙表, 每个节点只能在自己时隙内向簇首发送数据, 否则处于睡眠状态以节约能量.

3) 数据发送. 簇首将接收机处于开启状态, 等待各簇成员节点发送数据, 簇首会对数据进行压缩和融合, 并将数据发送到基站.

图4 LEACH算法的工作流程Fig.4 Workflow of LEACH algorithm

LEACH算法的工作流程如图4所示. 由图4可见, LEACH算法采用随机方式确定簇首, 簇内成员数量差异较大, 簇首的负载不均衡, 导致一些簇首过早死亡, 簇内节点采用单跳方式与簇首进行通信, 能耗大, 对网络生存时间产生不利影响.

3 改进LEACH算法

3.1 “热区”和“非热区”的划分

基站向目标监测区域广播消息, 根据消息将目标监测区域分为多个子区域, 与基站距离近的子区域称为“热区”, 其他区域称为“非热区”. 每个节点根据接收到的信号强度确定自己所在区域, 第i个子区域的上下边界分别为：

(4)

(5)

其中：dmax和dmin分别表示节点与基站的最大和最小距离;m表示子区域的数量.

3.2 簇半径动态调整原则

设簇半径为R, 节点密度为p, 则该簇内的成员节点数为

m=πR2p.

(6)

簇首能量消耗值的计算公式为

Etotal=Erec+Et=(πR2p×k+l)×Ee+b×(Ee+εampd2),

(7)

其中：b表示簇内成员节点的数据量；l表示其他簇首转发的数据量.

由式(7)可知, 簇首能量消耗的大小与簇半径R和节点密度p密切相关.R越大, 表示簇内信息发送量越大, 簇首负载越大; 而p与簇首所在位置相关, 簇首数量越多, 簇首的密度越大, 可在周围找到距离近的簇首转发数据, 降低簇首能耗. 节点竞争半径与簇首位置间的关系[18]为

(8)

其中：d表示簇首与基站的距离;c表示距离对竞争半径的影响程度. 式(8)只考虑了簇首位置, 而未考虑节点的剩余能量, 在综合考虑节点剩余能量的基础上, “热点区”和“非热点区”节点的竞争半径计算公式分别为：

其中：Eres表示传感器节点剩余能量;Eave表示邻居节点的剩余能量平均值;d(si,BS)表示节点si到基站的距离; ΔR表示竞争半径调整值;x和m分别表示所在区域和整个区域的节点数.

在选择簇首前, 所有节点都对自己的竞争半径进行自适应调整, 自动加入相应的簇, 产生多个不均匀的簇, 防止簇首节点由于能量过早消耗完而死亡.

3.3 簇首的选择

首先根据rand( )与门限阈值T(n)间的关系确定候选簇首, 对一个候选簇首si, 如果其收到了成为簇首的消息, 则在其竞争半径内的节点均放弃竞选簇首. 候选簇首确定后, 根据剩余能量的高低对候选簇首进行排序, 选择剩余能量最高者作为簇首.

3.4 数据通信方式

本文对无线网络中的数据通信方式进行优化, 流程如下:

1) 若簇首si位于“热区”内, 则其与基站进行直接通信, 不需要其他簇首节点进行数据转发, 从而节省能量消耗；

2) 若簇首si位于“非热区”内, 则建立一个邻簇首集合, 计算数据通信的代价函数, 选择值最小的节点作为数据转发节点sj, 通过该方式找到一系列的转发节点, 最后将数据发送到基站, 代价函数计算公式为

(11)

4 仿真分析

4.1 网络参数设置

为了测试改进LEACH算法的性能, 采用MATLAB 2014作为仿真软件平台, 无线传感器网络的仿真参数列于表1. 为使改进LEACH算法的仿真测试结果更有说服力, 选择文献[19]的无线传感器网络分簇路由算法进行对比测试.

表1 仿真测试参数设置Table 1 Parameter settings for simulation tests

4.2 网络存活节点数对比

整个无线传感器网络的网络存活节点数变化曲线如图5所示. 由图5可见, 相对文献[19]的网络分簇路由算法, 本文改进LEACH算法的第一个节点死亡时间显著延迟, 这主要是因为改进LEACH算法引入了非均匀分簇方式, 综合了节点位置和剩余能量确定簇首, 并对数据通信方式进行了改进, 可大幅度减少节点的能量消耗, 且减少了簇首负载, 整个网络生存时间延长. 图6为两种算法网络节点死亡百分数对比结果. 由图6可见, 改进LEACH算法的第一个节点死亡、 50%节点死亡及所有节点死亡的时间都延迟了, 这主要是由于整个无线传感器网络节点的利用率得到提高, 延长了节点生命周期.

图5 网络存活节点数变化曲线Fig.5 Change curves of number of network survival nodes

图6 网络节点死亡百分数对比Fig.6 Comparison of death percentage of network nodes

4.3 网络剩余能量对比

随着仿真时间的不断变化, 整个无线传感器网络的剩余能量变化曲线如图7所示. 由图7可见, 文献[19]网络分簇路由算法的剩余能量小, 表明整个无线传感器网络消耗能量较多, 这是因为数据通信消耗的能量大, 而本文改进LEACH算法的剩余能量大, 说明整个无线传感器网络消耗能量少, 能较好地节约网络能量. 当出现第一个死亡节点时, 其他传感器节点的剩余能量分布如图8所示. 由图8可见, 当出现第一个死亡节点时, 文献[19]网络分簇路由算法的剩余能量分布极不平衡, 使节点死亡的速度加快, 而改进LEACH算法的剩余能量分布均衡, 较好地均衡了节点的能耗.

图7 网络剩余能量的变化曲线Fig.7 Change curves of network residual energy

图8 第一个节点死亡时其他节点的剩余能量分布Fig.8 Residual energy distribution of other nodes when the first node died

综上所述, 为了解决当前无线传感器网络分簇路由算法存在的不足, 本文提出了一种改进LEACH的无线传感器网络分簇路由算法, 并采用MATLAB 2014仿真软件进行了仿真测试. 测试结果表明, 改进LEACH算法较好地解决了节点过早死亡的难题, 无线传感器网络的寿命时间得以延长, 较好地平衡了各节点的能量消耗, 整个无线传感器网络的性能显著优于当前其他路由算法设计的无线传感器网络.