无线传感器网络基于节点ID的LEACH改进算法

收稿日期:2009-10-21.

基金项目:国家民委科学研究基金（08YN02）；云南省教育厅科学研究基金（08Y0275）.

作者简介:陈晓敏（1984-），男，硕士研究生.主要研究方向:无线传感器路由算法.

通讯作者:凌永发(1973-），男，博士，教授.主要研究方向:网络算法和自动控制.

摘要: LEACH路由算法是无线传感器网络经典路由算法之一.在LEACH算法的基础上，改进了数据传输链路，建立了一条基于节点ID的树型传输链路.仿真实验表明，改进的路由算法能使第1个节点的死亡时间延迟，能量消耗更加均衡，提高了网络的生存时间.

关键词: 分簇；LEACH算法；树；路由算法

中图分类号:TP393.03

文献标识码:A文章编号:1672-8513(2010)04-0244-04

An Improved LEACH Algorithm Based on Node ID in WSN

CHEN Xiaomin ，ZHU Longhua, LING Yongfa

(School of Electrical and Information Technology, Yunnan University of Nationalities, Kunming 650500, China)

Abstract: LEACH routing algorithm is one of the classic routes in wireless sensor networks. Based on LEACH algorithm，this study improved the data transmission link, and established a tree transmission link based on node ID. Simulation data show that the improved routing algorithm could delay the first node death time, balance energy consumption and improve the network lifetime.

Key words: cluster；LEACH algorithm; tree; routing

[HJ1.6mm]

无线传感器网络（Wireless Sensor Network，WSN）是由大量无处不在的，具有通信与计算能力的微小传感器节点密集布设在无人值守的监控区域而构成的能够根据环境自主完成指定任务的智能测控网络系统［1］,可广泛应用于军事侦查、医疗、环境监测、商业领域以及空间探索和灾难抢险等领域.WSN中, 节点一旦放置就不可轻易更换电池直到节点死亡,所以节点的能耗问题是影响网络寿命的一个重要因素，而且是WSN诸多研究技术中的最重要的问题.在WSN中，85%以上的能量消耗都消耗在数据的发送和接收，合理的路由算法能有效地减少能量的消耗，因此对路由算法的研究尤为重要.其中LEACH(Low Energy Adaptive Clustering Hierarchy)算法是一种经典的WSN路由算法，LEACH协议中，通过随机选择簇头，平均分担网络中的通信业务，它的网络生存时间比一般的平面多跳路由协议和静态分簇算法延长了15%.尽管如此，忽略了真实网络的特性，该算法只考虑了网络节点分布均匀的情形.并且LEACH算法是一种单跳路由方式，定义簇头与基站直接通信，造成离基站远的簇头消耗能量过大，提前死亡，使得节点不能完全覆盖整个网络，采集到的数据将不完整.

1 LEACH算法及其改进

1.1 LEACH算法［2］

LEACH 算法主要通过循环的方式随机选择簇头（Clusterhead），将整个网络的能量负载平均分配到每个传感器节点中，从而达到降低网络能源消耗、提高整个网络的生存时间的目的.LEACH 定义了“轮”（round）的概念，每一轮由分簇构建和簇维持2个阶段组成.在初始化阶段，随机选择节点为簇头，成为簇头的节点向周围广播信息，其他节点根据接收到广播信息的强度来选择它所要加入的簇，并告知相应的簇头.在簇维持阶段，节点将采集到的监测数据，传送到簇头，由簇头对数据进行必要的融合处理之后，发送到终端节点.下一轮工作周期重新选择簇头.

网络中的所有节点产生1个0~1的随机数，如果这个值小于门限值T(n) 的话, 节点就充当本轮的簇头.使用T(n)这个门限, 每个节点会在1/p 作内充当1次簇头.门限T(n) 定义为:

T(n)=p1-p(r mod 1/p)，如果n∈G0,其他[JY](1)

式(1)中，p是簇头占节点总数的百分比，r为当前轮数，G是在最后的1/p轮中未成为簇头的节点集合.

选好簇头以后，簇头广播信息，声明自己已经成为簇头，普通节点选择簇头进行加入.在分簇维持阶段，簇头节点接收来自其分簇内普通节点的数据，并将接收到的数据进行数据融合，最后簇头将数据直接传输到基站.

Lindsey等在LEACH算法的基础上提出了PEGASIS算法［3］，此算法将系统中的所有节点利用贪婪算法构成一个边长之和接近最小的链路.数据的发送和融合从链路上的端节点开始，沿着链路直到指定节点,然后由指定节点将最后融合的数据发送到基站.还有Heinzelman等［4］提出了集中控制式的分簇路由算法LEACH-C与LEACH算法不同的是：LEACH-C算法通过全局信息选择簇头，网络中的所有节点把自身地理位置和剩余的能量信息发送给基站，基站根据接收到的信息计算平均能量，如果节点能量低于平均能量，将不能成为候选簇头，基站根据所有非簇头节点到簇头的距离平方和最小的方法，通过模拟退火算法，从候选节点中选出合适的簇头，最后基站广播选择好的簇头集合以及各簇头所包含的普通节点信息.

根据第1顺序无线电能量模型，发射电路的发射能量：

ETX(l,d)=lEelec+lεfsd2,d＜d0,lEelec+lεmpd4,d≥d0.(2)

式(2)中, d0是一个阀值,l是数据大小，Eelec为电路发射、接收每比特所需的发射能量，d是传输距离，εfs,εmp为不同传输距离的衰减参数.

从上式看出，传输的能耗大约跟距离的二次方到四次方成正比，但是LEACH算法中，簇头通过单跳把数据直接传输给基站，造成离基站比较远的节点较早的消耗完能量而死亡.根据这种情况，提出一种基于节点ID的树型传输链路，簇头通过多跳的方式把数据传输给簇头.

第4期 陈晓敏，朱龙华，凌永发:无线传感器网络基于节点ID的LEACH改进算法

云南民族大学学报（自然科学版） 第19卷

1.2 改进的算法

如图1，将基站设在（0，0），以基站为圆心，R为半径，0≤r

首先，以LEACH算法选举簇头，簇头全网广播，声明自己成为簇头，广播信息包含了自己的ID，普通节点根据接收到的功率强度，选择簇头加入，簇头接收到其他簇头的广播信息，并将其ID记录.第2步以基站为根节点，建立树型数据传输链路.在WSN中，多跳的传输链路一般只知道邻居两者的信息，不知道下一跳簇头是否离基站更近或更远，但是通过节点ID可以很好地解决这个问题.在改进的算法中，簇头广播查询信息，只找比其ID小，且两者ID差最少的簇头作为父节点，不会把数据传输给比其ID大的簇头，造成数据信息离基站更远.如果某个簇头找不到比其更小ID的簇头，则将基站作为父节点.另外，如图1，ID=3区域的簇头，在ID=2区域，找到2个可选父节点，随机选择1个做为父节点.在第1步过程中，簇头根据存储在本地的其他簇头节点的ID，可以很容易得到其父节点和子节点.建立链路以后，普通节点将信息传输给簇头，簇头将接收到的数据信息进行数据融合，最后将融合的数据通过建立好的链路将信息传输给基站.

2 仿真模型建立

2.1 能量消耗模型

本文基于Matlab仿真，将200个节点随机分散部署在二维区域200m×200m内，网络的生存周期有着不同的定义，本文选取了网络中节点的最短生存周期为整个网络的生命周期［5］，即第1个节点的死亡时间为网络的生存时间.每个节点有着以下的性质：

1）所有节点都是同构的，具有数据发送、接收和融合能力；

2）基站在（0，0），R=40m；

3）节点的初始能量为E0=0.5 J；

4）所有节点是静止的.

能量模型选取第1顺序无线电能量模型，如图2所示.

节点要传输l比特数据，发射电路以及功率放大器需要消耗的能量如式（2）所示，d0=εfs/εmp.当d

节点接收l比特数据消耗的能量：ERX(l)=lEelec. （3）

簇头节点进行本地处理和数据融合时，需要的能量：Ein=lEDA.（4）

EDA是每处理1比特数据，需要的能量消耗.

根据文献［6］，能量衰耗模型参数值:Eelec=50nJ/bit，εfs=10pJ/（bit•m2），εmp=0.013pJ/（bit•m4），EDA=5nJ/bit.

2.2 簇成员能耗

节点数为n，簇头选择机制跟LEACH算法一样，根据得到的随机数与门限值T(n)比较，决定是否成为簇头.假设有k个节点成为簇头，那么，k个簇头首先广播1次声明自己被选为簇头，广播信息带有自己的ID，那么簇成员共接收到k次的广播信息，接收信息总能耗kERx_broadcast.簇成员根据接收到的功率，向其中1个簇头发送请求加入分簇的信息，发送信息能耗为ETx_request.而簇头接收到请求后，向簇成员发出同意其加入的信号，簇成员接收此信号的能耗ERx_agree，簇成员加入分簇，此时分簇已经建立.最后簇成员节点把监测到的数据发送给簇头的能耗为ETx_packet.1轮分簇过程中，1个簇成员节点总能耗为：ECluster_member=kERx_broadcast+ETx_request+ERx_agree+ETx_packet.

2.3 簇头能耗

簇头能耗分为簇内能耗和簇间能耗.

2.3.1 簇内能耗

节点在成为簇头时，全范围广播声明成为簇头的能耗为ETx_broadcast，假设剩下的(n-k)个成员节点平均分配到k个分簇内，那么每个簇头接收到n－kk个簇成员请求加入的信息，接收信息的总能耗为n－kkERx_request，而后，簇头向簇成员发送同意其加入分簇的能耗为n－kkETx_agree，等到簇成员加入分簇后，分簇建立完成.簇成员向簇头发送监测到的信息，簇头接收信息，并融合信息，能耗为E(l)=n－kk(ERx_packet+l*EDA).

簇头成簇过程中,1个簇头总的能耗为ECluster_head1=ETx_broadcast+n－kk(ERx_request+ETx_agree+ERx_packet+lEDA).

2.3.2 簇间能耗

[JP2]簇头除了在分簇过程中产生能耗，而且在链路建立过程中也要产生能耗.建立路径过程中，簇头首先根据接收到的ID信息，比较ID差，得到自己的子节点和父节点.而后，某一簇头节点向父节点发送了1次请求加入链路的信息，能耗为ETx_request，父节点接收到后，发送同意信息给它，它接收同意信息的能耗为ERx_agree.同时，它与子节点的交互过程中，接收了1次请求信息ERx_request，和发送了1次同意信息的能耗ETx_agree，此时路径建立完成.数据传输过程中，向父节点发送1次数据包能耗为ETx_packet，接收、处理子节点数据包的能耗E(l)=ERx_packet+lED，簇头在分簇之间总能耗为：[JP3]Ecluster_head2=ETx_request+ERx_agree+ERx_request+ETx_agree+ETx_packet+ERx_packet+lED.[JP]

可得到：1轮循环中，簇头总能耗ECluster_head=ECluster_head1+ECluster_head2.仿真中，节点起始能量为E0=0.5J，当剩余能量少于0，则节点死亡.

3 仿真结果

下面用Matlab对LEACH及改进的算法进行仿真，在仿真过程中，主要以网络生存时间以及剩余能量作为性能评价参数，其中网络生存时间定义为网络中节点的最短死亡时间.首先，200个节点随机分布在200m×200m区域中，如图3所示，基站在（0，0）位置.

[HJ]

改进的算法先根据LEACH算法选择簇头，当产生的随机数小于T(n)这个门限值，则当选为簇头.下一步基站广播，寻找ID最小的簇头作为基站的子节点，继续以找到的子节点作为父节点，寻找跟其ID差最小的簇头作为子节点，直到建立完整的路径.所有的节点完成1次的数据传输作为1轮，继续则要进行重新建立分簇.随着仿真的进行，如图4所示,可以发现改进的算法比LEACH算法延迟了第1个节点的死亡时间.

[JP+2]在LEACH算法中，离基站较远的簇头跟基站直接通信，消耗能量较大，能耗远远超过了改进的算法，使有的节点过早地消耗完能量，停止工作.如图5所示，改进的算法每一轮消耗的总能量比LEACH算法更加均衡，使大多数节点能一直保持工作，到最后才死亡.[JP]

如图6所示，随着仿真的进行，发现改进的算法每轮消耗的能量比LEACH算法更少，导致总的剩余能量更多.

[LL]

4 结语

在LEACH的改进算法中，引入了节点ID，虽然增加了节点的一部分负担，但是针对LEACH传输链路进行改进，从仿真看出，改进的算法能耗比LEACH算法更加均衡，延迟了第1个节点的死亡时间，提高了网络生存时间，从多个方面实现了优化.

[FL)]

参考文献:

［1］于海斌，曾鹏.智能无线传感器网络系统［M］. 北京：科学出版社，2006.

［2］HEINZELMAN W R, CHANDRAKASAN A,BALAKRISHNAN H．Energy-efficient communication protocol for wireless microsensor networks［C］//Proceeding of the 33rd Hawaii International Conference on System Sciences.2000:1-10.

［3］LINDSEY S, RAGHAVENDRA C S. PEGASIS: Power efficient gathering in sensor information systems ［C］∥Proc of the IEEE Aerospace Conf. San Francisco: IEEE Computer Society, 2002:1-6.

［4］HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless micro sensor networks ［J］. IEEE Trans on Wireless Communications, 2002,1(4):660-670.

［5］MA Yong, JAMES H A. System lifetime optimization for heterogeneous sensor networks with a hub-spoke topology［J］. IEEE Transactions on Mobile Computing, 2004,3(3):286-294.

［6］YU Y, ESTRIN D, GOVINDAN R. Geographical and energy-aware routing: a recursive data dissmination protocol for wireless sensor networks ［R ］. UCLA Computer Science Department Technical Report, 2001:1-11.

［7］YU J Y, CHONG P H J. A survey of clustering schemes for mobile Ad hoc networks［J］. IEEE Communications Survey,2005,7(1):32-48.