一种基于LEACH的无线传感器网络改进路由算法

李建奇, 曹斌芳, 王 立, 任艳惠

(1. 湖南文理学院 电气与信息工程学院, 湖南 常德, 415000; 2. 湖南文理学院 物理与电子科学学院, 湖南 常德, 415000)

一种基于LEACH的无线传感器网络改进路由算法

李建奇1, 曹斌芳2, 王 立1, 任艳惠1

(1. 湖南文理学院 电气与信息工程学院, 湖南 常德, 415000; 2. 湖南文理学院 物理与电子科学学院, 湖南 常德, 415000)

延长网络的生命周期是无线传感器网络研究中的重要问题, 针对经典 LEACH路由算法分簇机制中存在的不足, 提出了一种改进LEACH算法. 该算法分簇机制综合考虑了节点的状态以及分簇机制带来的开销, 它通过计算每轮网络能量消耗速度来动态调整分簇的策略以减少了分簇机制产生的开销. 改进协议将每轮分为簇的建立、簇间路由的形成、簇头簇内的调整和数据的稳定传输阶段4个阶段. 仿真结果表明该算法提高了网络的能量效率, 延长了网络的生存周期.

无线传感器网络; 分簇; 能量效率

由于无线传感器网络(WSN)中采集节点一般采用电池供电, 同时节点更换不便, 在确定的数据通信任务条件下, 网络的生存周期与网内节点的能耗密切相关, 因此优化网络的整体能耗效率, 延长网络寿命的路由协议是无线传感网络的一个重要研究内容[1-2].

Heinzelman等于2000年提出的LEACH(Low Energy Adaptive Clustering Hierarchy)算法是比较具有代表性的层次型路由算法, 是WSN中最早和广泛应用的分层路由协议[3]. 很多路由协议都是基于LEACH协议基础改进而来的[3-4]. LEACH协议在选择簇头时主要考虑的各节点平均承担簇头工作, 当多个簇头与基站直接通信, 特别是当随机性产生的次优簇头节点位于距离网关较远的时候, 传输数据将无谓消耗额外的能量, 可能导致该节点提前死亡, 并加大了网络单位数据流的能量消耗. 研究人员针对LEACH协议的不足提出了结合剩余能量、地理位置和节点密度等多种改进方法[5-10]. 但是文献[5-10]研究剩余能量主要是与自身的初始节点之间的关系和节点与网关节点距离之间的关系等多个因素. 这些改进算法在优化簇的选举的同时, 也带来了不同程度分簇开销, 本文针对这类情况提出了一种改进型LEACH算法, 综合考虑簇结构优化和分簇活动开销, 最后通过MATLAB仿真验证本文算法的有效性.

1 WSN网络模型

本文算法针对的传感器网络具有以下性质:

a) N个传感器节点随机的分布在M×M的区域当中, 节点一旦配置完成即保持静止不动, 也不再人工维护, 每个节点结构功能相同, 并且具有相同的初始能量, 并且具有功率控制功能;

b) 网关位于传感器监测区域以外的固定一点, 因为WSN应用的场合均是常规监测手段难以达到的区域, 将网关置于监测区域之外是合理的假定, 网关节点功率可以覆盖整个监控区域;

c) 节点之间通信链路是对称的, 每个节点总有监测数据需要发送, 可以与一定范围内的节点通信;

d) 相邻监测区域内的数据具有相关性, 可以进行数据融合;

e) 每个节点都有足够的计算能力支持不同的MAC协议和数据处理;

f) 每个节点均采用全向天线;

g) 节点消耗能量模型采用文献[6]中所提出的模型:

其中式(1)中, d为传输距离, ETx(k, d) 表示传感器节点发送kbit 数据通过距离d时的能耗, 由发射电路耗损和功率放大耗损两部分构成. 功率放大耗损根据发送者和接收者之间的距离分别采用自由空间模型和多路径衰减模型. Eelec为发射电路的耗损能量. εfs和εmp分别表示两种信道模型下功率放大所需能量. 式(2)表示接收kbit数据的能量耗损, 仅由电路耗损引起. 式(3)为将接收到的n个节点发送过来的n×kbit数据与本身的kbit数据融合, 融合成kbit数据再发送出去.

2 经典LEACH路由协议

LEACH协议按周期运行, 分成若干轮(Round). 每一轮分为簇的建立阶段和稳定通信阶段. 簇的建立阶段是簇首的形成阶段. 在簇的建立阶段, 每个节点生成一个介于0和1之间的随机数, 如果这个数小于这一“轮”所设定的阈值 T(n), 那么这个节点就成为簇首, 这个阈值通常需要根据网络中节点的数目按经验值来给定.

其中p为节点中成为簇头节点的百分数, r是当前的轮数, G是在前r轮中未被选为簇头的节点集合. 簇首的节点向网络广播分簇信息, 告知其他节点相关簇首信息. 其他节点接收到消息后,根据信号强度来选择它要加入的簇. 各簇群中的节点通过TDMA(时分复用技术)方式与簇首进行通信.

以 LEACH 算法的思想为基础, 针对 LEACH存在的不足, 研究人员提出了很多的改进算法, 例如LEACH-C (LEACH-Centralized), LEACH-EA (Energy Average)等算法[4-5]. LEACH-C算法是由基站基于整个网络信息集中挑选簇头, 每个节点把自身地理位置和当前能量报告给基站, 基站根据所有节点的报告信息计算出平均能量, 低于平均能量的节点不能成为候选簇头, 基站根据所有成员节点到簇头的距离平方和最小的原则, 从剩余候选节点中选出合适数量和最优地理位置的簇头集合, 最后由基站将簇头集合以及簇的结构广播出去.

3 改进的LEACH协议

针对一个静态固定网络频繁产生的全网分簇活动, 实际上加大网络的总体能量消耗. 除掉由硬件差异造成的节点间能耗差异后, 较优的网络分簇结构由节点所处地理位置分簇的是相对确定的, 而其他改进算法要求 WSN网络内节点频繁通信带来的数据通信能耗相当可观, 因此对于整个网络分簇与簇头的选举是可以进行优化的. WSN网络一旦出现了死亡节点后, 往往意味着部分区域可能无法监控的情况, 因此尽可能延长网络所有节点而非生存周期是很有必要的.

本文在结合历史簇头选举、簇头的剩余能量、网络平均能量节点的位置, 同时修改的分簇和簇头选举机制, 提出了一种改进协议, 以使WSN更加能量效率更高. 新的协议把整个数据传输分为多轮, 每轮又分为簇的建立、簇间多跳路由的形成、簇头簇内的调整和数据的稳定传输阶段共4个阶段, 这4个阶段循环往复.

3.1 簇的建立

首先每轮由网关发出分簇广播, 该信息包含网络中所有簇头的剩余能量的平均值 Eav(平均值 Eav通过各个簇头节点报告的各簇的平均能量计算得到), 凡是剩余能量低于 Eav的节点定义为低能量节点, 这类节点不参与簇头竞争. 每个节点接收该网关的启动信息后, 并根据接收到的信号强度, 计算出自己到网关节点的距离, 记为dnw. 每个非低能量节点自身产生一个介于0~1之间的随机数, 将该数与门限值T(n)作比较,若该数小于 T(n)则该节点将成为临时簇头节点, 若该数大于 T(n)则该节点暂时成为普通节点, 门限值 T(n)由式(5)决定, 其中, En是节点n的当前剩余能量, Enav是上一次簇内网络节点的平均能量(可近似为本轮竞争范围内节点的平均能量). Neighbor_num表示节点的邻近节点数目, CH_Times表示节点在以前轮数中被选为簇头节点的次数. 簇头选举算法应当让高剩余能量和低能量消耗功率的节点优先当选.

簇首节点选出之后, 广播自己当选簇首的信号, 周围节点根据信号强度, 选择所属簇首, 然后发送一个请求加入信息, 此信息除了包含簇首节点ID以及自己的ID号以外,还需要包含自己的剩余能量状态、本节点距离簇头的距离和本节点距离网关的距离.

3.2 网络路由的形成

簇建立之后, 每个簇首向网络广播自身信号中包含自身的ID等信号, 每个簇首接收到其它簇首广播的强度信号, 确定出近似距离信息并记录下来, 然后所有簇首节点把这些距离信息发送给基站,同时还要发送自己的剩余能量状况. 基站接收到这些信息后采用文献[10]算法, 规划出全网链路拓扑, 同时记录下剩余能量不足的簇首. 接下来把网络链路数据结构广播给所有簇首节点. 这样簇首间的主干网络形成. 簇间的链路多跳路由如图1所示.

图1 网络簇头路由拓扑结

3.3 簇头簇内的调整

每一轮完成本簇的数据采集、融合、数据发送和数据转发后, 簇头节点在本簇的相邻节点中选择最近和最高剩余节点选择下一轮的簇头节点, 在本簇内广播簇头节点的转移. 簇头的内部调整的轮数参数IR初始设置为1轮, 前100轮该参数固定不变, 随后该参数随着整个轮数的变化而变化, 网关根据网络前100轮中计算每轮的平均能耗. 当接下来的轮数中, 一旦该轮的能耗较低, 那么该指数根据与平均能耗的偏离来确定, 当轮耗大于平均能量IR设置为1轮; 即马上启动分簇, 若轮耗较低则增大该参数最大值为5, 因为中前期各节点性能良好, 那些在充当簇头节点而能量消耗少, 应该更多的承担簇头工作. 当网络整体平均能量降低到初始能量的一半的时候为的内部调整的次数固定为 1, 因为在中后期节点的能量将较大的下降,所以动态的成簇机制有助于整个网络的生存时间. 也就是第一次启动分簇后 10轮内将不再进行全网的分簇, 只在簇内部调整. 这在一个静态网络中大大减少不必要的竞争成簇, 有效地提高能量的利用效率.

调整策略根据公式TCn=(Dnw/Dav+En/Eav), n属于本簇内节点, TC值最大的节点称为下一轮簇头. Dnw是节点n距离网关的距离, Dav是上一次簇内网络节点的距离网络的平均距离(可以近似看为本轮竞争范围内节点的平均距离), 因为是距离网关节点的距离实际上在发送一定数量数据的前提下代表了节点能量的消耗速率. 在相同条件下选择高能量节点和距离网关近的节点充当簇头, 有利于网络整体能耗的降低.

3.4 数据传输阶段

数据的簇内传输与LEACH中的方法是一样的, 每个簇内节点根据TDMA表, 在自己的时隙内向簇首传输数据. 簇首接收完簇内成员的数据并进行融合后, 开始按收到的路由链路传输, 每个簇首节点接收到上一级节点的数据后进行数据融合, 然后再发送给下一跳节点. 数据传输采用了带反馈的超时重发机制,簇头节点发送数据后等待接收方反馈确认信息后再清除该数据, 若超时定时器超时则重发该数据, 簇头节点的变化也通过反馈的确认信息进行捎带. 在这个过程中, 每个中继簇头节点若在规定时间片内未接收到上一级簇首节点的数据, 则将节点异常信息融合后直接传输自己的数据.

4 改进算法分析与仿真实验

本文采用MATLAB对LEACH协议和改进后的算法进行了仿真和比较, 假设100个节点随机分布在100 m×100 m的监控区域中, 其中基站位置为(0 m, 0 m). 节点初始能量为0.5 J, Eelec= 50 nJ/bit, εfs= 10 pJ/bit/m2, εamp= 0.001 3 pJ/bit/m4, 数据融合EGx= 5 nJ/bit/signal, 仿真最大轮数为5 000轮, 仿真50次取平均值进行对比并画图.

图2描述了网络活动节点数与工作轮数直接的关系. 从图2可以明显看出改进算法的与LEACH标准协议相比能够极大的延长WSN网络的工作时间. 图3描述了网络节点每100轮能量消耗之间的关系,可以清楚看出来网络节点的能耗降低, 主要是由于节点合理的承担了充当簇头的轮数, 分簇在选择中较为合理. 图4描述了各节点的剩余能耗的方差分布图, 从图4可以看出, 节点的直接的剩余能耗得到了更好的均衡.在经典的 LEACH协议中, 每个节点选择所属簇首的时候只是考虑了与簇首的距离, 而没有考虑簇首的剩余能量情况. 这可能导致当选簇首的低能量节点快速死亡, 进而缩短整个网络的生命周期. 改进算法在簇建立阶段, 通过能量比较和寻找替代簇首, 均衡了能量消耗, 同时新增的能量比较算法很简单, TDMA的计算分配与LEACH 相比基本不增加能量开销,故整体上增加的延迟与能耗开销很小.

图2 WSN节点死亡数与工作轮数的关系

图3 网络能量每百轮消耗曲线

图4 网络节点能量方差每百轮消耗曲线

5 小结

本文提出的改进的算法分簇时结合节点剩余能量与网络平均剩余能量的比值, 根据网络平均剩余能量筛选非低能量节点作为候选簇头, 再综合考虑剩余能量、网络平均能量、节点与簇头和节点与网关之间距离等信息来产生的.同时分析了分簇机制本身带来开销影响, 提出了一种动态簇内局部簇头轮流承担的策略. 改进算法进一步均衡了对WSN整体进行能耗均衡, 延长了WSN的寿命.

参考文献:

[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Commun, 2002, 40(8): 102-114.

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

[3] Heinzelman W, Chandrakasan A, Balakrisham H. Energy-efficient Communication Protocol for Wireless Microsensor Networks[A]. Proceedings of the 33rd Annual Hawaii Int’l Conf. on System Sciences[C]. IEEE Computer Society, 2000: 3005-3014.

[4] Heinzelman W B, Chandrakasan A P, Balakrisham H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communication, 2002, 1(4): 660-670.

[5] Raghavendra C S, Sivalingam K M, Znati T F. Wireless Sensor Networks[M]. Kluwer: Academic Publishers, 2004: 78-83.

[6] Akyildiz I F, Kasimoglu I H. Wireless sensor and actor networks: research challenges[J]. Ad Hoc Networks, 2004, 2: 351-367.

[7] Karl H, Willig,A. Protocols and Architectures for Wireless Sensor Networks[M]. Wiley, 2005: 110-118.

[8] Younis O, Krunz M, Ramasubramanian S. Node clustering in wireless sensor networks: recent developments and deployment challenges Network[J]. IEEE, 2006, 20(5): 20-25.

[9] 朱丁丁, 金心宇, 张昱. 基于能量优先分簇算法的WSN分层路由协议[J]. 传感器学报, 2009, 22(4): 579-585.

[10] 胡钢, 谢冬梅, 吴元忠. 无线传感器网络路由协议LEACH的研究与改进[J]. 传感器学报, 2007, 20(6): 1391-1396.

[11] 杨菊英, 吕光宏. 无线传感器网络分层路由协议研究[J]. 计算机技术与发展, 2008, 18(6): 115-118.

[12] 廖明华, 张华, 王东. 基于LEACH协议的簇头选举改进算法[J]. 计算机工程, 2011, 37(7): 112-114.

[13] 徐鹏飞, 陈志刚. 无线传感器网络的连通成簇算法[J]. 小型微型计算机系统, 2008, 29(11): 2041-2045.

[14] 林楠, 史苇杭. 无线传感器LEACH算法的优化及仿真[J]. 计算机仿真, 2011, 28(1): 178-181, 241.

[15] MohanedAl-Obaidy, AladdinAyesh, AlaaF.Sheta. Optimizing the communication distance of an ad hoc wireless sensor networks by genetic algorithms[J]. ArtifIntell Rev, 2008, 29: 183-194.

(责任编校： 刘刚毅)

An improved cluster routing algorthm for wireless sensor network

LI Jian-qi1, CAO Bin-fang2, WANG Li1, REN Yan-hui1
(1. Department of Electronic Engineering, Hunan University of Arts and Science, Changde 415000, China; 2. Department of Physics and Electronics, Hunan University of Arts and Science, Changde 415000, China)

Wireless sensor networks require robust wireless communication protocols that are energy efficient and provide low latency. This paper analyzes the traditional LEACH protocol and proposed a modified algorithm. clustering considers the state of node and energy cost speed, it is calculating the energy consumption of each hundred round of the network, dynamically adjust the clustering strategies to reduce the whole cost. New algorithm includes clustering, cluster routing ,cluster-head local adjustment and data transfer. Network data transfer by single hop or multi-hop. Simulation results show that improved algorithm can effectively reduce the energy consumption and extend the network life.

wireless sensor network(WSN); clustering; energy-efficient

TN 393

1672-6146(2012)02-0051-05

10.3969/j.issn.1672-6146.2012.02.013

2011-12-19

湖南省科技计划项目经费资助(2010SK3052)

李建奇(1980-), 男, 副教授, 硕士, 主要研究方向为无线传感器网络. E-mail: li_jianqi@126.com