基于TinyOS的无线传感器网络LEACH算法的改进

朱　明，刘漫丹

(华东理工大学 信息科学与工程学院，上海 200237)



基于TinyOS的无线传感器网络LEACH算法的改进

朱明，刘漫丹

(华东理工大学 信息科学与工程学院，上海 200237)

LEACH协议是无线传感器网络中最流行的分簇路由协议之一。针对LEACH算法簇分布不均匀以及网络能耗不均衡等问题提出了一种高效节能多跳路由算法。在簇建立阶段，新算法根据网络模型计算出最优簇头间距值，调整节点通信半径以控制簇的大小，形成合理网络拓扑结构；在数据传输阶段，簇头与基站之间采用多跳的通信方式，降低了节点能耗。在TinyOS操作系统下，使用nesC语言设计实现了LEACH-EEMH算法。基于TOSSIM平台的仿真结果表明，新算法较LEACH算法在均衡网络能耗、延长网络寿命方面具有显著优势。

TinyOS系统；无线传感器网络；路由协议；高效节能

无线传感器网络(Wireless Sensor Networks，WSN)由大量的小型传感器节点组成，它可以实时地收集和处理各种环境和对象的信息，并通过卫星或互联网将其发送到用户终端[1]。它使得人们能够在任何时间、地点和环境下实现对物理世界的动态、智能、泛在的感知[2]。

由于节点电池能源有限，计算及存储能力弱，它们的操作系统需具备耗能少且可以适应各类应用环境的特点，TinyOS[3]正是具备了上述特点的WSN操作系统。TinyOS采用组件层次结构，是一个基于事件的系统，现阶段大部分无线传感器网络研究项目都采用TinyOS操作系统，TinyOS已成为WSN研究领域上的标准平台。

WSN路由协议决定了网络的运行效率和执行能力，由于网络资源受限，WSN路由协议算法的研究核心便是降低传感器网络的能耗，提高资源利用率，延长网络寿命[4]。WSN路由协议根据网络结构可分为平面路由协议和分簇路由协议两种类型。平面路由协议网络中各节点功能相同，算法简单，容易实现，但是网络的可扩展性小，应用范围较窄。常见的平面路由协议有SPIN[5]、Flooding Protocol[6]、Directed Diffusion[7]等。分簇路由协议将网络划分为“簇”，每个簇由一个簇头和多个成员节点构成，相比平面路由协议有较好的可扩展性，应用范围广。常见的分簇路由协议有LEACH[8]、TEEN[9]、PEGASIS[10]等。

LEACH(Low Energy Adaptive Clustering Hierarchy)是WSN中具有代表性的分簇路由算法，具有低功耗自适应的特点，LEACH的循环周期使用了“轮”的概念，一轮包括簇建立和数据传输阶段两个部分。簇建立阶段，各节点随机生成一个0～1间的数，若该数小于阈值Tn，则此节点成为簇头，同时广播成为簇头的信息。非簇头节点根据收到簇头广播消息，选择加入离自己最近的簇头成簇。数据传输阶段，簇成员节点将其监测到的数据发送给簇头节点；簇头进行数据融合处理，然后以单跳的方式将数据发送给基站。Tn计算式如

(1)

式中：p是期望的簇头数占网络中总节点数的比例；r是当前轮数；每1/p轮为一个周期，G是最近一个周期内没有成为簇头的节点集合。

LEACH提出了一种簇头轮流当选的机制，初步解决了负载平衡的问题，且采用分布式算法，容易实现，但还是存在一些问题。例如LEACH采用随机选择簇头的方式，不能保证簇的均匀分布，致使簇头的能耗不均衡，网络寿命缩短；且簇头与基站采用单跳通信的方式限制了网络的规模。LEACH-C[11]是LEACH的改进算法，采用集中式的分簇算法选出较优的簇头，使簇分布更加合理；但簇间采用单跳通信，传输距离过远仍会产生大量能耗。

本文针对LEACH算法的不足提出了一种基于簇分布的高效节能多跳路由算法——LEACH-EEMH(EnergyEfficientMulti-Hop)。

1　LEACH-EEMH算法

1.1LEACH-EEMH算法的设计思想

LEACH-EEMH算法的设计思想主要体现在以下几个方面：

1)根据网络能耗最小的原则计算出簇头节点之间最优的间距值，在这个条件的约束获得合理的簇分布，使簇较为均匀地分布在网络中；2)簇头选举首先考虑节点的能量水平，能量多的节点当选本轮簇头；3)为避免频繁的全网动态分簇造成大量能量开销，只在每个周期的首轮进行整个网络的动态分簇，其余时间则采用簇内独立的簇头轮换机制；4)簇头节点和基站之间采用多跳的方式进行通信，以减少网络能耗，延长网络寿命。

1.2能耗模型

LEACH-EEMH算法的能量模型与LEACH相同，采用一阶无线电能耗模型，节点发送kbit的数据到距离d的位置，根据该模型耗能为

(2)

式中：Eelec表示发送或接收1bit数据消耗的能量；εfs和εmp分别表示自由空间模型和多路衰减模型下的功率放大损耗常数。在传输距离小于阈值d0时，功率放大损耗采用自由空间模型，传输距离大于d0时，采用多路衰减模型。节点接收和融合数据k(单位bit)消耗的能量分别为

Erx(k,d)=kEelec

(3)

Efusion(k,d)=kEDA

(4)

式中：EDA是融合1bit数据消耗的能量。

1.3最优簇头间距值求取

簇头节点之间最优的间距值是根据最优簇头数计算得到，下面首先计算最优簇头节点的个数。

假设在M×M的监测区域内随机分布着n个节点，若有k个簇，那么每个簇内平均有n/k个节点。簇头节点的能耗主要包括接收成员节点监测到的数据、簇内数据融合、将整个簇的数据传输到基站这3个部分。由于簇头远离基站，能量损耗可采用多路衰减模型，单个簇头节点的能耗为

(5)

式中：l是数据包大小；dtoBS是簇头到基站的距离。

簇成员节点的能耗主要是将监测到的数据发送给簇头。簇头与成员节点之间的距离较近，采用自由空间模型，单个成员节点的能耗为

(6)

式中：dtoCH是成员节点到簇头的距离。

簇可以看做是以簇头为圆心的圆形区域，每个簇所覆盖的面积平均为M2/k，其成员节点到簇头距离的平方的期望值为

(7)

此时成员节点的能耗为

(8)

每个簇的能耗为

(9)

全网的能耗为

(10)

式中：DtoBS表示基站到网络区域中心的距离。

令Etotal的一阶导数为零，可得使Etotal值最小的k值为

(11)

网络运行中不断会有节点因能量耗尽而死亡，因此kopt的值是变化的。

kopt个簇要覆盖整个面积为M×M的正方形区域，簇头均匀分布，理想的网络拓扑结构如图1所示，以簇头为圆心的圆半径为R，整个监测区域由kopt个小正方形所覆盖，那么

(12)

簇的半径R为

(13)

可得簇头间最小间距D的值为

(14)

由式(14)可知，D会随着kopt的变化而变化。LEACH-EEMH算法中基站每个周期(1/ p 轮)重新计算D值，然后向全网广播该值。

图1　理想的网络拓扑结构

1.4LEACH-EEMH算法的流程

LEACH-EEMH以轮为周期，每轮分为簇建立、簇间路由建立以及数据传输3个阶段，数据传输阶段与LEACH算法相同，这里详细介绍前两个阶段。

1.4.1簇建立阶段

簇建立阶段分为每周期首轮簇建立和非首轮簇建立两种情况。

1) 情况一

每周期首轮簇建立阶段，在簇头选举之前，节点根据自己的能量水平确定一个定时时间，能量大的节点比能量小的节点时间短。

簇头选举工作开始，全网同时进入定时时间的倒计时，能量最大的节点倒计时首先结束，当选第一个簇头。该节点以D为通信半径广播簇头消息，然后增大通信半径向基站发送一条簇头消息。

在定时时间内，若某个节点收到了簇头的广播消息，则立即结束倒计时，放弃成为簇头节点。直到倒计时结束仍然没有收到簇头广播消息的节点，宣布自己成为簇头。

如果基站收到的簇头消息达到了最佳簇头数目，则停止选举簇头的操作。

簇头选举结束，簇头节点增大通信半径广播簇头消息。非簇头节点选择距离最近的簇头节点作为自己的簇头，加入该簇并向簇头节点发送入簇消息，至此每周期的首轮簇建立阶段完成。

2) 情况二

非首轮簇建立阶段不进行全网簇重组，当前轮的簇头由上一轮的簇头节点指定；上一轮的簇头节点在数据传输的最后阶段选择簇内能量最大的节点作为下一轮簇头，新簇头广播成为簇头的消息，非簇头节点入簇。

1.4.2簇间路径建立阶段

每个簇头节点都维护着一个路由表Troute，它是根据其接收的簇头广播消息建立的。当簇头i收到簇头j的广播消息时，比较两簇头到基站的距离值dtoBS。若j的dtoBS值小于i的dtoBS值，将簇头j加入到i的Troute中，反之则不加入。若簇头i的dtoBS值不大于d0或其Troute为空，则选择基站作为下一跳节点。 反之，簇头i从其Troute中选择距离最近的簇头节点作为下一跳节点。

2　LEACH-EEMH协议实现

2.1总体框架

本文采用TinyOS 2.1操作系统和nesC语言实现LEACH-EEMH协议。图2是LEACH-EEMH协议的结构框图，其中实线框表示模块，每个模块实现一种功能；虚线框表示配件，它表示模块的连接关系；箭头代表接口。箭头上方是上层组件，箭头下方是下层组件，上层组件通过接口调用下层组件的功能，下层组件通过接口向上层组件触发事件。LEACH-EEMH协议采用单配件多模块的程序模型，整个协议在一个配件LeacheemhC里实现。配件内包含LeacheemhP，ClusterFormP和ClusterMultiRouteP共3个模块。除此之外还包括TinyOS系统自带的TimerMilliC，AMSenderC，AMReciverC，ActiveMessageC和RandomC等组件。路由层的功能对于上层应用来说是不透明的，LeacheemhC组件为上层提供了与数据传输有关的StdControl，AMSend和Receive接口，接口的相关函数在LeacheemhP模块里实现。

图2　LEACH-EEMH结构框图

2.2主要功能模块

LEACH-EEMH算法的主要功能模块是LeacheemhP,ClusterFormP和ClusterMultiRouteP模块，其中LeacheemhP模块是其他两个模块的管理者，对外界提供开放的功能接口。ClusterFormP是簇建立模块，ClusterMultiRouteP是簇间多跳路径建立模块。

1)LeacheemhP模块

LeacheemhP是LEACH-EEMH协议的核心处理模块。LeacheemhP模块通过调用AMControl接口控制无线通信模块ActiveMessageC的开启与关闭，调用CFControl接口控制ClusterFormP模块完成簇的建立，调用CMRControl接口控制ClusterMultiRouteP模块建立簇间多跳路径。簇间多跳路径建立完成后，LeacheemhP向上触发RouteFormDone事件，开始数据传输。LeacheemhP模块向上层提供了StdControl和AMSend和Receive接口。StdControl是标准控制接口，能够控制路由层功能的开启和关闭。AMSend是主动消息发送接口，AMSend在其发送命令里指定了AM目标地址，它的实质是经过路由层的多跳传输后到达该目标，LEACH-EEMH协议的目标地址是基站。Receive是消息接收接口，提供了接收到消息时触发的事件函数，当基站接收到消息包时会触发Receive接口的事件。

2)ClusterFormP模块

ClusterFormP是簇建立模块，负责完成簇头的选举、簇的形成和维护等工作。向上层提供了CFControl接口，用于控制簇建立的开始与结束，获得簇的信息等。ClusterFormP模块调用AMSenderC组件的AMSend接口和AMReceiveC组件的Receive接口完成簇内路由和数据消息包的发送与接收，调用TimerMilliC组件的Timer接口完成与定时器有关的操作，调用RandomC组件的Random接口获得簇头选举时需要的随机数。

3)ClusterMultiRouteP模块

ClusterMultiRouteP是簇间多跳路径建立模块，负责建立簇头与汇聚节点之间的多跳路径，完成路由的选择工作。向上层提供了CMRControl接口，用于控制簇间多跳路径建立的开始与结束，获得路由信息等。ClusterMultiRouteP模块调用AMSenderC组件的AMSend接口和AMReceiveC组件的Receive接口来完成簇间路由和数据消息包的发送与接收，调用TimerMilliC组件的Timer接口完成一系列与定时器有关的操作。

3　仿真结果与分析

3.1参数设置

本文选用TinyOS操作系统自带的仿真工具TOSSIM(TinyOS simulator)[12]对LEACH-EEMH算法进行仿真，TOSSIM可以支持大规模的网络仿真。100个节点随机分布在100 m×100 m区域内，基站的坐标为(50，175)，其他参数如表1所示。

表1仿真参数

参数含义参数值Einit节点初始能量2JEelec单位数据发送/接收能耗50nJ/bitεfs自由空间系数10(pJ·bit-1·m-2)εmp多路衰减系数0.0013(pJ·bit-1·m-4)EDA簇头数据融合能耗5nJ/bitd0信道模型距离阈值87mpdata数据包长度4000bit

3.2结果与分析

本文采用网络生存时间和负载平衡程度这两个性能评价指标，对比LEACH-EEMH，LEACH-C和LEACH算法，仿真结果如图3、图4所示。

图3　网络生存时间仿真结果

图4　网络负载平衡因子仿真结果

由图3可知， LEACH算法第一个节点死亡的时间约是240轮，最后一个节点死亡的时间约为510轮；LEACH-C算法第一个节点死亡的时间约是290轮，最后一个节点死亡的时间约为560轮；LEACH-EEMH算法第一个节点死亡的时间约是300轮，最后一个节点死亡的时间约为610轮。经计算得到，LEACH-C第一个节点死亡时间比LEACH延长了21%，网络生存时间比LEACH延长了9.8%；而LEACH-EEMH的一个节点死亡时间比LEACH延长了25%，网络生存时间比LEACH延长了20%。LEACH-EEMH算法的网络生存周期明显高于LEACH和LEACH-C算法，因此LEACH-EEMH算法在减少网络能耗，延长网络生存时间方面具有较好的性能。

图4对比了3种算法的负载平衡程度，负载平衡因子越大，网络的负载平衡度越好，网络寿命越长。从图4可知，LEACH的负载平衡因子最大值约为0.023 5，最小值约为0.012 5；LEACH-C的负载平衡因子最大值约为0.025 5，最小值约为0.019 5；LEACH-EEMH的负载平衡因子最大值约为0.028 0，最小值约为0.022 5，且波动较小。表明LEACH-EEMH在平衡网络负载方面具有较好的性能，这是因为LEACH-EEMH算法的簇头数量最优，且设置了簇头的最小间距使簇头分布较为均匀，更好地均衡了网络负载。

4　结论

本文选取经典的LEACH路由算法作为研究原型，针对其不足提出了LEACH-EEMH算法，并将该算法在TinyOS操作系统上实现。TOSSIM仿真结果表明LEACH-EEMH算法能有效节省能量，均衡网络负载，延长网络生存周期。但LEACH-EEMH算法也有不足之处，该协议在设计时着重考虑能耗问题，忽略了时延、丢包率、安全因素等情况，今后还需对此做进一步的研究。

[1]YICK J，MUKHERJEE B，GHOSAL D. Wireless sensor network survey[J]. Computer networks，2008，52(12)：2292-2330.

[2]孙利民.无线传感器网络[M].北京：清华大学出版社有限公司，2005.

[3]LEVIS P，MADDEN S，POLASTRE J，et al. TinyOS：an operating system for sensor networks[M]. Ambient intelligence：Springer Berlin Heidelberg，2005.

[4]XIANGNING F，YULIN S. Improvement on LEACH protocol of wireless sensor network[C]// International Conference on Sensor Technologies and Applications. [S.l.]：IEEE，2007：260-264.

[5]KULIK J，HEINZELMAN W，BALAKRISHNAN H. Negotiation-based protocols for disseminating information in wireless sensor networks[J].Wireless networks，2002，8(2/3)：169-185.

[6]FARIVAR R，FAZELI M，MIREMADI S G. Directed flooding：a fault-tolerant routing protocol for wireless sensor networks[C]// Proceedings of Systems communications. [S.l.]：IEEE，2005：395-399.

[7]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al. Directed diffusion for wireless sensor networking[J]. IEEE/ACM transactions on networking，2003，11(1)：2-16.

[8]邹虹，彭国龙.一种基于 LEACH 改进的均匀分簇路由算法[J].电视技术，2013，37(3)：133-136.

[9]MANJESHWAR A，AGRAWAL D. TEEN：a protocol for enhanced efficiency in WSNs[C]//Proc. the First International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing. [S.l.]：IEEE，2001：2009-2015.

[10]JUNG S M，HAN Y J，CHUNG T M. The concentric clustering scheme for efficient energy consumption in the PEGASIS[C]// Proc. the 9th International Conference on Advanced Communication Technology. [S.l.]：IEEE，2007：260-265.

[11]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transactions on wireless communications，2002，1(4)：660-670.

[12]LEVIS P，LEE N，WELSH M，et al. TOSSIM：accurate and scalable simulation of entire TinyOS applications[C]//Proceedings of the 1st international conference on Embedded networked sensor systems. [S.l.]：ACM，2003：126-137.

朱明(1990— )，女，硕士生，主研无线传感器网络；

刘漫丹(1973— )，女，教授，博士生导师，主要研究方向为无线传感器网络、智能优化计算等。

责任编辑：许盈

Improvement of LEACH algorithm based on TinyOS for wireless sensor network

ZHU Ming, LIU Mandan

(SchoolofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

LEACH protocol is one of the most popular clustering routing protocols in wireless sensor networks. To deal with the unbalanced clustering and energy consumption problems exist of LEACH algorithm, an energy efficient multi-hop routing algorithm is proposed. In the clustering stage, the new algorithm calculates the optimal cluster head distance value, adjust the node communication radius to control the size of the cluster, thus forming a reasonable network topology structure. In the stage of data stable transmission, a multi-hop communication mode is adopted between the cluster head and the base station to reduce the energy cost. Based on TinyOS system, LEACH-EEMH is designed and realized with the language nesC. Simulations in TOSSIM platform reveal that, in contrast with LEACH, the new algorithm has obvious advantages in balancing the network energy consumption and prolonging the network lifetime.

TinyOS system; wireless sensor network; routing protocol; energy efficient

TP393

ADOI：10.16280/j.videoe.2016.10.015

中央高校基本科研业务费专项(WH1213010)

2015-12-31

文献引用格式：朱明，刘漫丹. 基于TinyOS的无线传感器网络LEACH算法的改进[J].电视技术，2016，40(10)：71-76.

ZHU M，LIU M D. Improvement of LEACH algorithm based on TinyOS for wireless sensor network[J].Video engineering，2016，40(10)：71-76.