一种基于LEACH协议的改进路由算法

王飞飞++丁亚飞

摘 要：针对无线传感器网络中LEACH协议的簇首选择与簇间数据传输存在的问题，提出了一种改进的路由算法，该算法在簇首选举时以节点剩余能量作为依据，采用了新的阈值公式，在数据传输时建立临时路由表、构建簇间多跳路由。仿真结果表明：改进后的算法可有效地延长网络内节点的存活时间，从而延长网络的生存周期。

关键词：无线传感器网络 簇首 数据传输 多跳路由

中图分类号：TN929.5 文献标识码：A 文章编号：1672-3791（2016）12（a）-0023-02

无线传感器网络（WSNs）是由部署在监测区域内的大量传感器节点构成的自组织系统，综合了传感器技术、分布式信息处理技术和无线通信技术，主要通过各节点实时地监测与采集覆盖区域内的各种数据信息，然后进行处理和传输[1]。WSNs最先应用于军事与国防领域，随着技术的发展与普及，逐渐应用于自然灾害、智能家居、生物医疗与智慧居家养老等领域，市场发展前景较好。但是因传感器节点一般采取电池供电，在能量方面具有一定的局限性。而节点的能耗主要产生于数据采集与传输，由平面路由到分簇路由，许多研究者对数据传输采用的路由协议在不断地进行研究与改进[2-4]。该文在对经典路由协议LEACH[5]分析研究基础上，针对其簇首节点选举时未考虑剩余能量与簇首和基站通信采用的单跳路由问题，提出了基于能量和簇间多跳路由的改进算法，有效地均衡了节点能耗，延长了网络生存周期。

1 LEACH协议分析

1.1 传输能耗模型

设定传感器网络数据传输时采用文献[5]中的无线通信模型，节点发送与接收kbit数据所消耗的能量计算公式中，d是信号传输的距离，根据d值的大小决定信息传输时采用自由空间信道模型还是多径衰减模型，当d值超过临界值86.2时，能耗消耗比较大，因此在分簇路由协议中，在成簇与构建簇间路由时，尽量控制可通信节点之间的距离。

1.2 LEACH协议描述

LEACH协议是最具有代表性的分簇路由协议，后期许多路由协议都是在对它研究基础上所产生的，如LEACH-C、LEACH-F。LEACH协议主要由簇首选举、簇的产生、数据融合、数据传输等组成，并在其中引入了轮的概念，每轮包括簇的建立和数据传输两个阶段。

在LEACH协议中，簇首的选择具有随机性，具体步骤如下：监测区域中的传感器节点，产生一个介于0、1之间的随机数，如果该随机数小于此轮所设定的阈值T（n），该节点就被选定为该轮的簇首，阈值越大，节点当选为簇首的概率越大，节点被选为簇首后，发送簇首广播信息，非簇首节可能收到多个广播信息，其根据信号强弱决定要加入的簇，并向该簇首发送请求，簇首收到请求后产生TDMA定时消息并通知簇内各节点，成簇后，簇首接收该簇内各节点发送的信息并进行数据融合后直接发送至基站。

1.3 存在问题

LEACH协议中，簇首选择时没有充分考虑到节点的剩余能量，其阈值产生公式虽然一定程度上保证了各节点成为簇首的概率相同，但是并不能保证成为簇首节点的当前能量。另外，各簇首节点与基站直接通信，如果簇首距离基站在通信范围内，会采用自由空间通信模式，否则将采用多路径衰减模式，导致该部分簇首节点能量消耗过快。因此，为了解决上述问题，该文在LEACH协议基础上提出了新的改进算法，着重解决其在簇首选择时的能量与簇首数据传输问题。

2 改进算法

该算法主要在簇首选举与数据传输两个方面进行了研究与改进，具体如下。

2.1 簇首选举

每轮工作时，节点向簇首传递数据时携带节点当前剩余能量，当所有数据发送至基站后，由基站计算当前网络的平均剩余能量Eave，并以广播的形式发送给每个节点，在簇首选举时，节点首先将自己的当前能量Eleft与Eave进行比较，如果大于等于Eave，则根据新的阈值计算公式判断是否当选为簇首，如果Eleft小于Eave，则退出竞争。

同时，在产生阈值时引入网络中的最优簇首个数，该数确定采用文献[5]中的簇首计算公式，将此数应用到LEACH协议阈值计算公式中，可得到新的计算公式（1）。

（1）

2.2 簇间多跳路由

无线传感器网络中簇建立后，簇内节点将采集的数据传输给簇首，簇首经过数据融合后将数据发送至基站，在LEACH协议中无论距离远近，簇首均直接与基站相连，导致部分节点能量消耗过快，因此簇间路由的创建至关重要。该算法采用簇首多跳路由传输的方法，即簇首选择自己周围合适的簇首作为中转节点，从而减少能量的损耗，具体如下。

在成簇阶段，簇首发送广播信息，信息中携带自己当前剩余能量以及自己的坐标位置，非簇首节点根据此信息选择合适的簇加入，而簇首节点则根据信息，选择合适的簇首加入临时路由表，路由表建立方法如下：

假设Si节点的坐标为（x1，y1），Sj节点的坐标为（x2，y2），基站BS的坐标为（x，y），数据由Si经Sj发送至BS，由式（1）可知，能耗与数据传输距离相关，即当

d=d2（Si，Sj）+ d2（Sj，BS） （2）

的值较小时，才能达到节能的目的，式（2）中，d2（Si，Sj）为Si到Sj的距离的平方。

同時考虑到节点进行数据传输时所需要的能量较多，在选择下一跳节点时除了相互间距离还需将节点的当前能量作为参考因素，因此在路由表中添加4个满足条件的节点，进行数据传输时选择Eleft/d值最大的节点作为中转节点。

3 仿真说明与分析

为了将改进后的算法与已有算法进行比较，该文利用OMNET++进行仿真模拟，对网络内同一时间的节点存活个数进行比较，验证改进算法的性能。仿真环境：设定在一个200 m×200 m的区域内，有400个传感器节点，节点在监测区域内随机分布，基站BS的坐标预先设置（x=50，y=250）；节点初始能量相同，均为0.5J，数据包大小为4 000 bit。

改进后的算法在某一时间点节点存活数较多，且整体存活时间较长，原因在于节点在成簇时选择距离较近的簇首加入，减少了非簇首节点的能耗，而在簇首选择中转节点时，综合考虑了能量与距离因素，也减少了簇首节点的能耗，从而延长了整个网络的生命周期。

4 结语

在无线传感器网络中，分簇路由协议占据着重要的地位，它的性能直接影响到整个网络的工作效率与生存周期，因此，该文在对经典LEACH路由协议分析研究的基础上，针对其能量与数据传输方面存在的问题，通过新的阈值公式改变原有的簇首选举方法，结合节点当前剩余能量建立临时路由表，构建簇首间数据传输的多跳路由，改进后的算法使簇首选举更合理，数据传输更加有效。分析显示，经过改进的算法在均衡网络节点能耗与延长生命周期方面有了明显的提高。

参考文献

[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].清华大学出版社，2005.

[2] 李芳芳，王靖.一种基于LEACH协议的无线传感器网络路由算法[J].传感技术学报，2012，25（10）：1445-1451.

[3] 陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法[J].传感技术学报，2013，26（1）：116-121.

[4] 严斌亨，陈任秋，刘军.能量优化的无线传感器网络LEACH算法[J].传感器与微系统，2016，35（7）：120-122.

[5] Heinzelman WB，Chandrakasan AP，Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.