无线传感器网络LEACH路由协议的改进

摘要:针对LEACH协议的不足,提出了一种基于k均值聚类的多跳分簇路由算法LEACH-KMCM。经过MATLAB仿真平台的测试,与LEACH协议相比,LEACH-KMCM使得整个网络的生命周期延长,具有较好的能量优化特性。

关键词:WSN;路由协议;簇头;LEACH

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)14-3668-03

Wireless Sensor Network Routing Protocol LEACH Improvement

MA Ge

(School of Information Engineering,Zhengzhou University,Zhengzhou 450044,China)

Abstract: LEACH routing protocol for the lack of a k-means clustering based on the multi-hop routing algorithm clustering LEACH-KMCM.MATLAB simulation platform, after the test, compared with the LEACH routing protocol, LEACH-KMCM the entire network to extend the life cycle, has good properties of energy optimization.

Key words: wireless sensor network; routing protocol; cluster head; LEACH

1 研究背景

无线传感器网络(wireless sensor Network,WSN)是由部署在检测区域内大量廉价的微型传感器节点通过无线通信的方式形成的一个多跳的自组织的网络系统。[1]近年来,随着传感器技术、微电子技术的进步,WSN得到了快速发展.它已经成为计算机科学技术的一个新的研究领域,主要应用在国防军事、救灾、环境监测等领域,被认为是21世纪最重要的技术之一。

目前,路由协议的研究已成为WSN研究的热点之一。与传统网络不同,WSN的路由协议有其自身的特点和设计要求。因此,传统的路由协议并不适用于WSN,必须研究新的能够有效节省和平衡节点能量消耗、延长网络生命周期的路由协议。LEACH协议是针对WSN提出的第一个分层路由协议,其后的分层路由协议大多是在它的基础上发展而来的,但是LEACH协议也存在着不足,具有可行的改进。因此,该文选择LEACH协议作为研究的对象具有良好的典型性。

2 LEACH路由协议的分析

LEACH(Low-Energy Adaptive Clustering Hierarchy)是由MIT的Heinzelman等人为WSN设计的低功耗自适应分层路由算法。[2]LEACH协议中定义了“轮”(round)的概念,每一轮分为簇的建立阶段和稳定阶段。

2.1 簇的建立阶段

在簇的建立阶段,相邻节点动态地形成簇,随机产生簇头节点,可分成以下四个阶段:

1) 簇头节点的选举

节点产生一个0～1之间的随机数,如果产生的随机数小于阀值T(n),则该节点就担任本轮周期的簇头。阀值T(n)可以表示为:

(1)

其中,P是簇头在所有节点中所占的百分比,γ是选举轮数,γ mod(1/P)代表这一轮循环中当选过簇头的节点个数,G是这一轮循环中未当选过簇头的节点集合。

2) 簇头节点的广播

节点当选簇头节点以后,通过广播向网络中其他节点信息告知自己是本轮的新簇头。在整个广播的过程中,簇头节点使用CSMA MAC层协议,运用相同的发射功率信息,非簇头节点的接收器始终处于工作状态,用于接收来自簇头节点的广播消息。

3) 簇的建立

每个非簇头节点根据接收到的簇头节点信息的信号强度选择加入哪个簇,并告知该相应的簇头节点,完成簇的建立。

4) 时隙表的创建

当簇头节点根据簇内节点的数量,将创建一个TDMA时隙表并通知每个非簇头节点何时开始传输数据。

2.2 稳定阶段

在初始状态下,簇头节点一直保持监听状态,簇内节点处于休眠状态。当分配的时隙来到时,簇内节点会自动唤醒并把数据发送给自己的簇头节点。在其它时隙,簇内节点将处于休眠状态.经过一段时间的数据传输,簇头节点收集簇内所有节点发送的数据后,运行数据融合算法将结果直接发送给汇聚节点。

稳定阶段持续一段时间后,网络重新进入簇的建立阶段,进行下一回合的簇的重构,不断循环。

3 LEACH路由协议的改进

针对LEACH协议的以下不足之处,本文提出了一种LEACH的改进算法――基于k均值聚类的多跳分簇路由算法,简称为LEACH-KMCM。

3.1 问题的提出

1) 最优簇头个数的选取

LEACH协议的簇头节点的产生是完全随机的,不能保证每一轮都能得到固定个数的最优的簇,影响了LEACH协议的性能。

2) 簇头节点分布

簇头选举没有考虑节点的具体地理位置,产生的簇头节点可能比较集中或者分布在网络的边缘.簇头节点分布不均匀,簇内通信能耗不平衡,不利于全网负载的均衡,从而严重影响网络的生存周期。

3) 簇头节点的选择依据

簇头节点比非簇头节点所消耗的能量多。如果簇头节点是固定不变的,那么能量较低的节点一旦选作簇头节点,在传输过程中很容易耗尽能量而失效。簇头节点一旦失效,整个簇将无法通信,所有属于这个簇的非簇头节点也将失去和汇聚节点通信的能力。

4) 簇头节点的广播

簇头节点选定后,成为簇头的节点将在整个网络范围内向所有节点广播消息。在网络覆盖区域很大的情况下,簇头节点需要将广播消息发送到相当远的区域,这个过程将消耗簇头节点相当多的能量。另外,网络中的所有非簇头节点都要参与簇的建立,增加了成簇的复杂性。

5) 簇间通信

在LEACH协议中,由于汇聚节点与传感区域相距较远,节点与汇聚节点的通信将是高能耗的。由于LEACH采用单跳通信的方式,簇头节点直接与汇聚节点通信,与汇聚节点通信的节点数目仍然较多,从而加大了能量消耗。

3.2 能量模型

把N个传感器节点随机均匀地部署在一个M×M矩形传感区域内,采用与LEACH协议相同的第一顺序无线电模型,如图2所示。假设WSN具有如下性质:

1) 汇聚节点是唯一的。

2) 传感器网络中所有节点都是同构的,并且节点能量有限,具有相同的初始能量。

3) 传感器节点部署后不再移动。

4) 各个传感器节点具备GPS功能。

5) 无线发射功率可控。

6) 每轮中节点的能量消耗不统一。

3.3 算法描述

LEACH-KMCM算法也按轮(round)进行,每轮分为两个阶段:簇的建立阶段和稳定阶段。同样,为了减少簇的建立阶段带来的额外能耗,稳定阶段的时间远远长于建立阶段的时间。

3.3.1 簇的建立阶段

首轮,LEACH-KMCM算法采用k均值聚类算法,根据指定的最优簇头个数k,将整个网络划分成k个簇,每个节点属于其中一个簇。在每个簇中,簇头节点仅接收本簇内的节点发来的数据,不接收其他簇的节点数据。在整个网络生存周期内,各个节点的NODEID,节点所在的簇CHID一旦确定,将不再改变,直至节点失效。

LEACH-KMCM算法的最优簇头数为:

(2)

其中,N是网络中节点个数,dtoBS是簇头到汇聚节点的距离,εmp为多径衰减信道模型放大指数,εfs是自由空间信道模型放大指数。

如果节点到基站的距离75m≤dtoBS≤185m,代入式(2),则最优簇头个数1

k均值聚类算法以 为参数,把N个对象分为k个簇,以欧式距离作为相似性测度,求对应某一初始簇中心向量最优分类,使簇内具有较高的相似度,而簇间的相似度较低。[4]

从第二轮开始,在各个簇,要尽可能选择离汇聚节点较近、剩余能量值Ecur大的节点担任簇头。普通节点向前一轮的簇头节点报告自身的能量值Ecur。前一轮的簇头节点依据接收到的各节点的Ecur值来决定新一轮的簇头节点。

3.3.2 传输阶段

①簇内数据传输

和LEACH协议一样,在每个簇中非簇头节点和簇头节点采用单跳方式直接通信。

②簇间数据传输

簇形成后,簇头节点将向相邻簇的簇头节点广播自己的状态信息,信息包括节点的NODEID,节点所在的簇CHID及其权值。簇头节点与汇聚节点之间采用基于权值的路由树算法实现多跳通信。在整个网络中距离汇聚节点较近且能量足够的簇头节点将优先成为路由树的根节点。簇头节点沿着路径将收集到的数据进行融合并传送给父节点,逐级传送到根节点,直至到达汇聚节点。

4 仿真实验

4.1 仿真模型和参数设置

仿真实验平台采用MATLAB,假设模拟场景为100个传感器节点随机分布在100×100的正方形区域,汇聚节点位于(50,175)处.仿真模型的参数与Heinzelman分析LEACH协议设置的参数一样。

图3 LEACH协议 图4 LEACH-KMCM算法

图3和图4的实验结果显示:随机产生100个节点,LEACH-KMCM算法比LEACH协议簇的分布更均匀,簇头节点在簇内产生,均衡了网络负载.

4.2 仿真结果性能比较

1) 网络生命周期(如图5)

2) 网络能量消耗(如图6)

图5 网络剩余节点数与轮数变化关系 图6 网络能量消耗与轮数变化关系

图5和图6的实验结果显示:LEACH-KMCM算法有效平衡了簇头的能量消耗,整个网络的能耗减少,将能量的损耗均匀分布到了所有节点中,避免了单个节点过早死亡,提高了网络的生命周期。

5结束语

LEACH-KMCM算法,兼顾簇头节点的合理分布以及数量优化,首轮采用k均值聚类算法将网络划分为固定的k个簇,从第二轮开始,以节点剩余能量的多少为主要依据来选取簇头,在传输阶段,簇内采用单跳方式直接通信,簇间建立路由树以多跳方式通信。仿真结果显示与LEACH协议相比,LEACH-KMCM使得整个网络的生命周期延长,具有较好的能量优化特性。

参考文献:

[1] 孙利民,李建中,陈渝,朱红松.无线传感器网络[M].北京:清华大学出版社,2005.

[2] 于海斌,曾鹏,梁|.智能无线传感器网络系统[M].北京:科学出版社,2006.

[3] Heinzelman W R, Chandrakasan A, Balakrishnan H. An application-specific Protocol architecture for wireless microsensor networks. IEEE Transactions on WirelessConununieations.2002,l(4):60-670.

[4] 安淑芝.数据仓库与数据挖掘[M].北京:清华大学出版社,2005.