无线传感器网络LEACH路由协议的研究与改进*

张 雷，刘银平，唐大鹏

(安徽工业大学 计算机学院，安徽 马鞍山 243002)

无线传感器网络WSN(Wireless Sensor Network)是由大量无处不在的、具有无线通信与计算能力的微小传感器节点构成的自组织分布式网络系统，是能根据环境自主完成指定任务的智能系统[1-2]。无线传感器网络在环境恶劣、无人职守、资源受限的环境中显示了很大的应用价值，能够客观有效地获取物理信息，具有十分广阔的应用前景，可应用于军事国防、工农业控制、城市管理、智能家居、生物医疗、环境检测、抢险救灾、防恐反恐、危险区域远程控制等诸多领域[3]。它以数据为中心，具有有限的计算能力、存储能力、无线通信能力和电源供应能力。如何在这样有限的资源环境下获取尽可能多的、有效的感知对象的特征信息，并传输到用户节点进行处理，是目前研究的重点，这些都可以归结为传感器网络的路由问题，即一个好的路由协议应尽可能降低能耗、延长网络生存时间。

无线传感器网络路由协议可以分为平面路由协议和分层路由协议两种[4]。由于平面路由协议需要维护较大的路由表而占据较多的存储空间，并且扩展性差，因而并不适用于大规模网络。分层路由协议可以在一定程度上弥补这些不足。LEACH算法是第一个被提出的具有代表性的分层路由协议，与一般的平面多跳路由算法相比，可将网络生命周期延长15%，以后的各种分层路由算法都是基于LEACH改进而来的。

1 LEACH算法分析

LEACH协议分为两个阶段，即簇建立阶段和数据传输阶段，为了使能耗最少化，数据传输阶段持续的时间要比簇建立阶段长，两个阶段所持续的时间总和称为一轮[5-6]。为平衡网络各节点的能耗，簇头是周期性按轮随机选举的，每轮选举方法是：各节点产生一个[0，1]之间的随机数，如果该数小于T(n)，则该节点为簇头。T(n)的计算公式如下：

式中，p是网络中簇头数与总节点数的百分比，r是当前的选举轮数，G是最近1/p轮不是簇头的节点集。成为簇头的节点在无线信道中广播这一消息，其余节点选择加入信号最强的簇头。节点通过一跳通信将数据传送给簇头，簇头也通过一跳通信将聚合后的数据传送给点，该协议采用随机选举簇头的方式避免簇头过分消耗能量，提高了网络生存时间。

但是这种随机选择簇头的策略必将引起簇头分布的不均匀，每个簇的成员数量也相差很大，再加上各个簇头到基站的距离不同，所以在每轮结束后，节点的能量消耗差异很大。由于LEACH算法在进行簇头选举时没有考虑节点的能量，所以有可能能量低的节点担任簇头。这样，簇头结点很可能在一轮结束前就因为能量消耗完而死亡，使簇内成员的数据在很长时间内不能传送到基站，出现监测漏洞。为了弥补这些不足，本文在LEACH的基础上对簇头选举算法进行了改进，提出了具有最优数目的高能量簇头集算法ONCHL(Leach with the Optimum Number of Cluster Heads)。

2 LEACH改进后的ONCHL算法

在LEACH算法随机选举出簇头集的基础上，ONCHL算法再根据所形成的簇的大小(用簇内节点的数量来衡量)及节点能量选择出簇内具有最优数目的高能量簇头集合，簇内数据的收集融合转发由这些高能量簇头节点共同承担。这就在很大程度上均衡了网络的能量消耗，有利于延长网络的生命周期。

2.1改进的簇头选举算法

由于网络中簇头数的多少将直接影响网络的性能，将应用分簇算法的最优簇头数理论[7]来对LEACH算法进行改进。最优簇头数Kopt：

在传感器节点分布均匀的情况下，每个传感器所占用的面积S=M/N。由基站将这一信息广播给网络中的每一个节点。

首先，根据LEACH算法生成初始簇头，成为簇头的节点广播成为簇头的信息，未成为簇头的节点根据接收到广播信号的强弱来决定加入哪个簇，并且将自己的能量信息发送给该簇簇头。簇头节点根据其成员个数n得到该簇所在区域的大小m：m=n×S，再将n和m代入公式(1)得到本簇应该具有的最优簇头数Ncu。簇头将各成员节点的能量(包括自身能量)做比较，选择出能量最大的前Ncu个节点来共同担任该簇的簇头，并给这Ncu个簇头分配作息时间，使它们轮流担任簇内数据的聚合和转发任务。当一个簇头节点处于工作状态时，其他的Ncu-1个簇头节点休眠。

由Ncu个簇头来分担原来一个簇头的工作量，避免了单个簇头因工作量过大能量消耗快而很早死亡的情况发生。虽然网络在开始时采用LEACH的簇头选举算法产生初始簇头，但最终由簇内能量最大的Ncu个节点来充当簇头，这就均衡了网络的能量消耗，延长了网络的生命周期。

2.2 ONCHL算法执行过程

ONCHL算法执行过程如下：

(1)基站广播包含S的数据包，网络中的所有节点提取并保存S信息，并通过接收信号强度获得到基站的距离dtoBS。

(2)通过LEACH算法形成初始簇头，簇头结点广播成为簇头的消息，未形成簇头的节点根据接收到信号的强弱选择加入一个簇，并将自己的能量信息发送给所加入簇的簇头。

(3)簇头根据接收到的能量信息的个数得到簇内成员数n，再通过简单计算得到本簇所占区域的大小m=n×S。应用公式(2)得到本簇应该具有的最优簇头数 Ncu：

(4)簇头结点将本簇各成员的节点能量以及自身能量做比较，选择出能量最大前Ncu个节来共同担任本簇簇头，并为这些簇头节点安排作息时间表(即工作时隙)。初始簇头将这个簇头以及其工作时隙发送给簇内所有的其他节点。同时初始簇头为簇内普通节点分配工作时隙并将结果广播给本簇其他节点。由于初始簇头节点的能量不一定在能量最大的前Ncu之列，当初始簇头节点能量较小时就退出而成为普通节点，反之则继续担任簇头工作。

(5)簇内普通节点按照时分复用(TDMA)时隙向簇头发送数据。成为簇头的Ncu个节点就在其工作时隙内将簇成员发送来的数进行融合并发送给基站。

(6)当其中的一个簇头因消耗大量能量而不能将数据传送到基站时，就宣告一轮工作结束，并在本簇内启动新一轮簇建立过程。

3算法仿真及结果分析

通过仿真实验在网络生命周期和网络吞吐率方面对LEACH算法和改进后的ONCHL算法进行了比较。其中，将网络生命周期定义为从网络运行到网络中所有节点都死亡的时间；网络吞吐率定义为基站接收到的数据量。

实验仿真系统由100个节点组成，节点随机分布在区域 Area={(x，y)|0≤x≤100，0≤y≤100}内，每个节点的初始能量为0.5 J，一次传送数据包的大小DL=2 000 bit，基站所在位置为(50，175)。采用参考文献[7]所使用的通信能量模型。

ζfs=10 PJ·(bit·m-2)-1(即 Free-space 模型放大倍数)

ζmp=0.001 3 PJ·(bit·m-2)-1(即 Two-ray ground 模 型 放大倍数)

(1)网络生命周期的比较

图1为LEACH算法和ONCHL算法网络生命周期的比较图。可以看出，ONCHL算法的节点生存时间相对LEACH有所提高，第一个节点死亡的时间延长了大约22%，整个网络的生命周期延长了大约35%。由此可见，ONCHL算法能更加均衡地消耗网络的能量，避免了低能量节点过早死亡，有效延长了网络的生命周期。

(2)网络吞吐量的比较

基站接收数据量随网络能耗的变化如图2所示。在相同的能耗下，与LEACH算法相比，改进后的ONCHL算法能够传递更多的数据，说明ONCHL算法具有较高的能量使用效率。这是因为ONCHL算法采用了具有最优簇头数的成簇方式，有效地提高了网络的能量使用效率。

以上实验结果表明，ONCHL算法与LEACH算法相比，无论在延长网络生命周期还是在提高网络吞吐率方面都更好，这主要是因为ONCHL算法在网络中形成了最优有数目的高能量簇头集，能更加均衡地将能量负载分配到每个节点。

本文提出了LEACH算法的改进算法——ONCHL算法。ONCHL算法在LEACH算法的基础上，选举出具有最优数目的簇头集，并在簇头选举中考虑了节点的当前能量。仿真结果表明，ONCHL算法具有更长的网络生命周期和更高的网络吞吐量。

[1]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14(7)：1282-1291.

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

[3]AKYILDIZI F， SU W， SANKARASUBRAMANIAM Y， et al.Wireless sensor networks：a survey[J].Computer Networks， 2002，38(4)：393-422.

[4]李莉，温向明，董树松.无线传感器网络路由协议的研究与展望[J].中国电子科学研究院学报，2006，1(1)：17-21.

[5]胡刚，谢冬梅，吴元中.无线传感器网络路由协议LEACH的研究与改进[J].传感技术学报：自然科学版，2007，20(6)：1391-1396.

[6]刘守军.无线传感器网络LEACH算法的研究[J].武汉理工大学学报，2007，29(10)：43-45.

[7]HEINZELMANWR， CHANDRAKASANA， BALAKR ISHNAN H.An application-specific protocol architecture for wireless micro sensor networks[J].IEEE Transactions on Wireless Communications， 2002，1(4)：660-670.