LEACH协议簇头

《单片机原理与接口技术》期中论文

论文题目 LEACH协议簇头

选择算法的改进

姓 名 学 号

学 院 电气工程学院 专业班级 2008级通信工程

1

目 录

引言 ................................................ 4 1 LEACH协议 .......................................... 4 1.1 LEACH 协议介绍 .................................................................... 4 1.2 LEACH 协议的能量损耗模型 ................................................ 6 1.3 LEACH 的不足在于： ............................................................ 6 1.4 LEACH 协议的优化 ................................................................ 6 1.4.1 基本思想 ...................................................................... 6 1.4.2改进细节 ....................................................................... 7 2 簇头选择算法的改进LEACH-H ........................... 8 2.1簇头初选 ................................................................................. 8 2.2簇头调整过程 ......................................................................... 9 3仿真结果 ........................................... 11 4仿真分析 ........................................... 11 5结束语 ............................................. 13 参考文献 ........................................... 15

2

EACH协议簇头选择算法的改进

专业： 通信工程 姓名： 马进虎

摘要 LEACH 协议存在簇头节点个数和位置分布不稳定的现象。在

改进的LEACH-H 协议在簇头节点的选举过程中, 充分考虑了簇头节点剩余能量因素, 设定了簇头的能量阀值, 防止了低能量的节点成为簇头。在此基础上引进簇头调整过程, 该过程通过排除紧密邻居簇头和增加必要的簇头, 在一定程度上解决了LEACH 协议存在的问题,从而达到均衡网络能量消耗, 延长生存期的目的。网络仿真证明了新算法的可行性，具有更高的能量使用率和更长的生存时间。

关键词WSN; LEACH; 簇头选择; LEACH—M

Abstract In LEACH , the number and the locations of

cluster-heads are both unstable. In order to avoid low energy cluster-head , inthe process of cluster-head electing , LEACH-H takes remaining energy into consideration , designs energy threshold of cluster-head. Acluster-head adjusting phase is devised , which can eliminate close neighbor cluster-heads and necessarily add cluster-heads. This phase willsolve the above problems to a certain extent , attain the load equilibrium and further lengthen the network lifetime. The simulation results showthat the new algorithm is feasible，higher energy usage and longer survival time.

Key words WSN; LEACH; selecting cluster-heads ; LEACH-M

3

引言

LEACH(Low-Energy Adaptive Clustering Hierarchy)协议是无线传感器网络层次型自适应成簇路由协议。它将传感器网络节点划分成“簇”,并引入了“轮”的概念,各节点独立地按照概率随机决定自己是否做“簇头”,通过周期性的簇头选举和网络重组过程,避免了簇头节点能耗过大,平衡了网络负载,大大节约了通信过程中的能量消耗。另外,簇头节点在处理数据的时候用到了数据融合技术和数据压缩技术,使得传输的数据量大大减小。因而与一般的多跳协议或者静态成簇算法相比,LEACH 可以将网络的生命周期延长15 % 。然而,LEACH 选簇首的方法常常呈现不稳定状态,即在一次实现中会出现簇首个数远远偏离期望值和分布位置集中在网络覆盖区域一侧的现象。本文对簇头选择算法进行改进,提出了新的协议LEACH—H。

1 LEACH协议

1.1 LEACH 协议介绍

LEACH 协议的每一轮可分成簇建立和稳定数据传输2个阶段。在簇建立阶段,各节点自主地运行簇头选举算法以确定自己是否成为簇头节点。成为簇头的节点向周围节点广播信息,其他节点根据接收到的广播信息的强度来选择它所要加入的簇,并告知相应的簇头。在稳定数据传输阶段,簇内节点把数据发送给簇头,簇头进行数据融合并把结果以一跳通信方式发送给sink 节点。簇头需要完成数据融合、与

4

汇聚节点通信等任务,能量消耗较大。因此,每一轮结束要按照上述方法重新选择簇头,以平均分担中继通信业务来均衡能量消耗。 LEACH的簇头选举算法是分布式的算法,没有任何中心节点控制选举或对选举进行协调。每个节点独立自主地决定是否成为簇头。选举时,节点产生一个0～1 之间的随机数,若该随机数小于阀值T( n) ,则发布自己是簇头的公告消息。

T( n) 的公式为:

式中, p 为簇头节点在传感器网络所有节点中所占百分比的期望值; r 为当前选举的轮数; G 是在最近1/ p 轮中没有当选过簇头的节点集合。通过该算法,每个节点都会在1/ p 轮中当选一次簇头节点。通过研究发现LEACH 选簇首的方法无论从数量上还是分布的位置上都常常呈现不稳定状态。当簇首个数太少时,失去分层的意义;当簇首个数太多时,由于簇首要直接与远端的sink 节点通信,发射功率较大,会导致整个网络能耗过大;簇首位置过偏会导致部分节点簇内通信半径过大,能耗不均匀,这都会影响网络寿命,使得网络的负载平衡程度下降。研究发现,上述现象的发生源于每次簇首选举的过程完全依赖于各节点产生随机数的过程,由于随机数产生的不稳定性导致了簇首状态的不稳定性。

5

1.2 LEACH 协议的能量损耗模型

发生电路 发送放大器 接收电路

图1 LEACH 协议的能量损耗模型

LEACH 协议的能量损耗模型主要有接收机和发射机两部分组成。 发射机：发生电路发送放大器组成。 接收机主要是接收电路。 1.3 LEACH 的不足在于：

（1）各节点自行随机决定是否成为簇头，导致簇头在某一区域特别集中，某一区域又特别稀疏。

（2）LEACH 假定所有节点初始能量相同，但实际上这点未必成立。即使成立，由于消耗不均，运行一段时间后剩余能量也会不一致。

（3）簇头的选择没有考虑节点的剩余能量，有可能导致某些节点的能量提早耗尽。

（4）EACH 选簇首的方法无论从数量上还是分布的位置上都常常呈现不稳定状态。 1.4 LEACH 协议的优化 1.4.1 基本思想

6

针对不足，对LEACH 进行改进。首先，为系统内节点添加定位装置（ 如GPS）， 使每个节点都有唯一的节点标识符node_id，接着以监测区域中心为质点，选定一起始半径，以2/kopt为定长进行等角度分区（kopt为网络最优簇头数），将整个区域分成多个均匀的子区域，避免了簇头分布不均。此外，给每个子区域制定唯一的区域标识符area_id，使每个节点清楚自己的归属。改进算法依旧采用“轮”的概念，每轮分为初始化和稳定工作两个阶段。簇头的选择由节点剩余能量决定，每轮过后计算每个节点的剩余能量，区内节点把自身带有的node_id、area_id 和标示本身能量的信息传输给它的邻节点，这样同区域内的每个节点都相互知道其它节点的相关信息，比较同区域内其它节点的剩余能量，能量最高的为本轮簇头，如一轮中出现相同剩余能量的节点，且能量都为最高，则按节点的标识符选定簇头。 1.4.2改进细节

（1）初始化最大节点数P，Eini（节点初始能量），Eres（节点剩余能量），节点初始能量与节点初始剩余能量相等，E0（剩余能量的阈值，小于此阈值，节点将不能选为簇头），Eelec（发送和接收电路消耗的能量），￡fs（信号放大器的通信功耗），每个数据包的大小。

（2）子区域划分，计算节点能量的消耗和剩余能量，确定簇头。操作如下：

① 在特定网络区域中随机部署所有节点， 确定节点的标识符和坐标。

7

② 划分kopt个子区域，指定每个子区域的标识符。划分子区域的前提在于最优簇头数的确定。当分布区域确定后，假设有N 个节点均匀分布在M×M 区域内，如簇头数为k 个，则每个簇内平均节点数为N/k。当Sink 点距离节点分布区域较远时，能量按距离的四次方衰减。

③ 计算节点能量的消耗和剩余能量，确定簇头。

2 簇头选择算法的改进LEACH—H

采用无文献[4 ]中的计算方法来计算在一定条件下最优簇头节点个数k ,其公式如下:

式中, N 为传感器节点总数;λ控制包与数据包的长度比;εf s与εamp为常数; dtoBS为节点到基站距离的期望值; M 为检测区域边长; m 为压缩比,即簇头节点最多可把m 个长度为L 的数据包压缩为一个长度L的数据包。在簇头选举过程中,借鉴文献[5 ] ,LEACH2H 协议引入簇头竞争调整过程,通过该过程的执行,可以在很大程度上均衡簇头节点的分布, 并提高网络的可靠性。 2.1簇头初选

只有剩余能量大于阀值的节点才有资格成为簇头,能量阀值

的计算公式如下:

8

式中, r 为当前运行轮次; n 为无线传感器网络的预期运行轮次; E0 为节点初始能量; Eth为第r 轮的簇头节点能量门限。

通过引入能量门限,防止了低能量的节点成为簇头,这就避

免了因为簇头死亡造成的重选举开销和数据丢失。 2.2簇头调整过程

节点根据簇头选举规则成为备选簇头后,就向其通信范围内

的节点发送广播包,广播包中含有自己的ID 号和剩余能量数据项,每个备选簇头节点根据收到的广播报文构建自己的邻居簇头表, 该表包括邻居节点ID、邻居节点剩余能量Er 、被选作为簇头的次数Cch 、是否是紧密节点Nclose四个数据项。首先,备选簇头节点将广播报文中的邻居节点ID 号、邻居节点剩余能量写入邻居簇头表, 初始化Cch = 0 ,根据接收信号强度估算与邻居节点的距离,若距离小于指定距离D , 则该节点和它是紧密节点。

式中, M 为传感器网络覆盖区域的边长(假设为正方形) ; K 为簇头节点数; < 为调整因子。D 的取值是为保证均匀分布的K 个簇刚好覆盖整个观测区域。非簇头节点收到广播报文,则将该簇头节点加入自己的备选簇头集合中。然后,传感器节点进入以下的流程:

①备选簇头节点计算自己的紧密邻居节点个数n 。若n = 0 , 则转④; 若n > 0 , 则根据下式计算其紧密邻居节点的当选权重:

9

式中, Enode为节点初始能量; x , y 为引入的权重因子,且x 、y ∈[0 ,1 ] 。其余符号意义同上。通过计算可得到每个节点的当选权重。选出其中权重最大的节点将其ID 号填入取消簇头数据包中。取消簇头数据包由类型Type 、本节点ID、最大权重节点ID、节点紧密邻居个数v 四个数据项组成。然后,节点在(0 , T1) 时间区间,随机退避一段时间后,将数据包发送出去,这是取消自己作为簇头节点的声明。

②收到声明的非簇头节点将数据包声明取消的节点从自己的备选簇头集合中删除。收到声明的簇头节点则更新自己的邻居簇头表,即将该节点从邻居簇头表中删除,同时将声明中最大权重节点的Cch值加1。查看自己的当前紧密邻居节点数z ,若z = 0 ,或者z > 0 但v = 1 ,则转④;否则,转①,继续执行竞争过程。所不同的是,随机退避的时间限制在( T′, T1 ) 的区间内, T′为当前时间。

③在时刻T1 到来时, 非簇头节点检查自己的备选簇头节点集合,若该集合为空,说明需补充簇头节点。此时非簇头节点在( T1 , T2) 区间内随机选择一个时刻广播自己当选簇头节点的通告, 若在退避等待过程中收到其他节点的通告,则放弃发送,将该节点加入自己的备选簇头集合中。

④在时刻T2 ,簇头节点的选择工作已经完成。各非簇头节点在其备选簇头节点集合中,按下列公式找出权重最大者作为自己的簇头节点:

式中, d ( node , CH) 为该节点到簇头节点的距离, 可以通过分析

10

信号强度得到; Dn - ch为一常数, 是允许的节点到簇头距离的最大值;θ、δ为权重因子,满足θ+δ= 1 ,且θ、δ∈[0 ,1 ] ,具体取值根据应用环境决定,通常δ的取值要大于θ。其余符号的意义同上;⑤以后的过程与LEACH 协议一样。

3仿真结果

图2 仿真结果

4仿真分析

本文采用NS2仿真工具建立了网络仿真模型,对改进算法和LEACH 路由算法进行了仿真和性能比较[6 ] 。模拟将100 个节点随机分布在(100 3 100)的空中,sink 节点的位置为(0 ,0) 。所有的节点都是静止的。带宽设置为1 Mbps , 消息的长度为500 byte ,发送与接收的时延均为25 s ,每个节点的初始能量相同,为2J 。指标主要有3 个:簇头数量方差、簇分布的均匀程度以及网络的生存期。其中簇头数量方差用前500 轮的统计数据,簇分布的均匀度用最小簇的直径与最大

11

簇的直径之比来表示。

仿真结果显示,LEACH 协议的簇头数方差为1186 ,LEACH-H 的簇头数方差为1103 ,簇头个数的稳定性有了很大改善。LEACH-H 协议的簇分布均匀度值平均为0181 ,而LEACH 协议的仅为0175 ,这表明簇的分布更趋均匀。图1显示了2 种协议的网络生命周期。从中可以看出,第一个节点死亡时间LEACH-H协议要晚于LEACH,全部节点死亡时LEACH-H比LEACH 多运行了23轮。这说明,新协议均衡簇头节点数量、平衡簇头节点分布的过程,虽然造成了一定的能量消耗,但是由于可以使能量损耗更加均匀的分布到所有的节点中,避免了单个节点因能量损耗过大而过早死亡,从而延长了网络的生存期。本文的仿真场景仅包含100个节点,当WSN网络规模更大时,网络的性能提升会更好。

: 网络仿真性能评价指标为网络生存时间和Sink 节点接收数据

总量与能耗，网络生存时间指网络中所有节点经数轮数据传输后，剩余节点个数的比率。如网络生存时间图所示，随着轮数的增加，改进后的算法较之传统LEACH 剩余的节点数更多，持续的时间更长，节点的死亡时间延迟了近20％，原因在于传统LEACH运行一段时间后，网内节点的剩余能量会不均衡，而改进后的协议能使簇内节点的能耗均衡， 避免了盲节点的过早出现，延长了网络生存时间。

12

网络生存时间图

传统LEACH的单位比特能耗要低，即消耗相同量的能量改进后的LEACH协议比传统LEACH 有能力发送更多的数据。这是由于每次都会选择簇内剩余能量高的节点作为簇头节点，从而增加了向Sink 节点发送数据的数量。

5结束语

本文针对LEACH 簇头选择算法的不足,在簇头的选举过程中充分考虑簇头能量因素并引进簇头调整过程。仿真试验结果表明,新的算法在簇头节点数量的稳定性和簇头节点位置分布均匀性方面都有很大改进,从而均衡了网络的能量消耗,延长了生存期。

同时，传统LEACH 协议采用先定簇头后分簇的算法，导致簇头分布不均、信息采集不完全的问题。文中提出了先根据最优簇头数进行网内区域划分，然后通过剩余能量感知选择簇头的算法，对传统LEACH 簇头选择算法进行了改进。理论分析和模拟实验结果表明，该算法能够合理的均匀分布簇头，平衡网络负载，使网络具有更大的数

13

据传输量和更长的生存时间。图3 Sink 节点接收数据总量与能耗本文作者创新点：文中提出了先根据最优簇头数进行网内区域划分，然后通过剩余能量感知选择簇头的算法，对传统LEACH 簇头选择算法进行了改进。

14

参考文献

[1 ] LINDSEY S ,RAGHAVENDRA C S. PEGASIS: Power Efficient Gathering in Sensor Information Systems[C] . Proceedings of the IEEE Aerospace Conference ,Big Sky ,Montana ,2002 : 542 -571. [2 ] HEINZELMAN W R ,CHANDRAKASAN A ,BALAKRISHNANH.Energy2 Efficient Communication Protocol for Wireless Microsensor Networks [ C ] . Proceedings of the 33rd HawaiiInternational Conference on System Sciences ,2000 :1 - 10.[3 ] 孙利民,叶驰,廖 勇. 传感器网络的路由机制[J ] .计算机科学,2004 ,31 :542 - 571.

[4 ] 王声荣.无线传感器网络LEACH 协议的研究与改进[D] .济南:山东大学硕士学位论文,2008 :27 - 32.

[5 ] 张 悦. 无线传感器网络LEACH 协议群首算法的改进[J ] .微计算机信息,2006 ,26 (4 - 1) :183 - 185.

[6 ] 何美红,徐成谦,张东良. 基于NS2 的LEACH 协议仿真与分析[J ] . 电子测量技术,2009 ,32 (1) :40 - 42.

[7]王殊, 阎毓杰等.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社, 2007. 77。

[8]张悦.无线传感器网络LEACH 协议群首算法的改进[J].微计算机信息, 2006, 4-1:183-185。

15

本文来源：https://www.bwwdw.com/article/tz57.html