基于簇的路由协议比较

王改云, 胡锦艳

(桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004)

基于簇的路由协议比较

王改云, 胡锦艳

(桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004)

摘要:路由协议作为无线传感器网络(WSNs)中的核心技术往往是研究的重点，现今有很多不同的高效路由协议已经提出。在参数选择和方法方面，每种路由协议都不同，都有自己的选取方式。基于簇的路由协议是著名的路由方法之一，在该结构中，簇首节点收集簇中其他节点的信息进行数据融合处理，然后将融合后的信息发送给基站。有必要对一些典型的分簇结构算法进行比较研究。

关键词：无线传感器网络； LEACH； 分簇； 路由协议；比较

0引言

无线传感器网络(WSNs)是由一组低功耗、小型、轻便的传感器节点组成，传感器中的节点相互之间通信，收集周围节点的信息。随着WSNs的发展，使得远程监控变得更加容易、精度变得更高。节点通常部署在事件发生的区域中或者周围，每个节点收集到监控区域的信息，然后进行处理，最后传送给头节点或者基站进行进一步的处理。通常，将节点的执行过程分成三部分：传感、计算和通信。节点都是随机部署在监控区域，网络中的节点必须具有自组织的能力。节点间的协作是这种网络的特点，它们相互协作传递信息到附近的用户。WSNs在各个领域中得到广泛应用，并且应用还在逐步增加,一些主要的应用有：森林火灾检测、停车场、栖息地监测、健康监控、工厂维护、工业自动化、智能家居等[1]。在WSNs中，已经有很多种不同的路由协议提出,其中，分簇算法是一种自主成簇，然后进行簇头选择和数据传输的路由协议。本文主要对现有的一些分簇路由协议进行比较分析。

1WSNs中基于簇的路由算法

1.1LEACH

2000年，MIT学者Heinzelman等人提出了LEACH，这是第一个低功耗、自适应分簇路由算法，为后人的研究奠定了基础。在LEACH协议中，节点动态成簇，然后选择一个节点作为簇首(CH)节点，如图1所示。

图1　LEACH协议Fig 1　LEACH protocol

图1中,黑色节点代表簇首节点，簇首节点负责收集该簇内所有节点的信息，并且进行数据融合然后发送给目的节点，以便进一步的处理。由于簇首节点和其他簇成员节点相比，工作很复杂，消耗的能量较大。LEACH提供相同的概率选择簇首，确保每个节点都有统一的能量消耗。一旦簇首节点选好，就会给每个成员节点分配时隙进行信息传递。一次只能将一个节点信息传输给簇首节点。在该结构中，簇首节点忙于通信，簇成员节点可以关闭通信节约能量。

LEACH算法分成两部分：初始化阶段和稳定阶段。在算法的初始化阶段中，主要是成员节点组织成簇，选举一个节点作为簇首节点。每个节点会产生一个0～1之间的随机数，与式(1)相比较，如果比T(n)小，则当选为簇首节点[2]

(1)

式中p为成为簇首的期望百分比，r为轮数，G为1/p轮还没有当选簇首的节点集合。如果节点i成为簇首节点，广播ANNOUCE消息宣布成为簇首节点的消息。在这个簇内的簇成员节点收到消息后，就会根据信号的强弱来决定将要加入的簇。如果加入就会对簇首节点回复JOIN的消息。当簇首节点收到来自簇成员节点的加入信息后，簇首节点通过时分多址(time division multiple access，TDMA)方式为簇成员节点分配时间槽，建立阶段完成。随后进入稳定阶段，在稳定工作的阶段，簇首节点将收集到的簇内成员的信息传到Sink节点。稳定阶段的时间要比建立阶段的时间长得多[2]。

1.2Energy LEACH和Multihop LEACH

基于参考能量的LEACH算法和LEACH基本上相同，但是参考能量的算法在原有算法上有一个改进，即簇首的选举不是通过阈值随机选取，而是基于节点的最大剩余能量，对阈值进行了修改，这将延长网络生命周期。不同于LEACH算法中每一个节点都有相同的概率成为簇首节点，改进算法中，能量较少的节点不会有机会成为簇首节点[3，4]。

不同于简单的LEACH，多跳LEACH协议，以多跳的方式发送数据到基站。这对总能耗影响很大。通过多跳的方式发送数据时，每个参与节点只花了少量的能量，从而防止了单个节点很快耗尽死亡。除了高效节能之外，多跳LEACH协议能使得网络更持久，适用于大规模网络[4]。

1.3V—LEACH

在双簇首LEACH协议中，一个簇结构对应的不是只有一个簇首节点，有2个，一个担当主簇首，另一个担当副簇首节点。开始时，主簇首负责收集簇中非簇首节点发送的数据，并将其发送到基站，但是一旦主群簇首节点即将死去，副簇首节点需要担负起主簇首节点的责任，同时，下一个副簇首节点会选择出来。这样防止了簇群因节点突然死亡而失去簇首节点，进一步地预防了数据突然停止传输。选举群簇首节点和副簇首节点是将基于最大剩余能量、节点到基站的最短距离和最小的能耗作为参考标准。双簇首协议在簇首和基站之间采取单跳传输，仿真结果表明，双簇首协议在延长网络生命周期方面能比LEACH协议提高49.37 %[5]。

1.4LEACH—R

在LEACH—R协议中，2个节点被选择作为重要节点。在初始化阶段选择簇首和R节点。起初，簇首节点选择是通过式(2)进行的，计算阈值，将节点的能量水平作为重要的参数指标

T(n)=

(2)

式中Eresidual为节点的剩余能量，E0为节点的初始能量，δ为连续的轮数，其间的节点尚未当选簇首直到当前轮，一旦节点被选为簇头，设置该值为0。

当设定好簇首节点，在簇首中选择一个节点称为中继节点(R节点)，通过选定两个参考指标，分别为剩余能量和离基站的距离。R节点的工作职责是获取融合后的数据传递到基站，这样，簇首的数据通过2达跳到基站，只需花费较少的能量，避免了节点过早死亡。R节点是通过λ参数选择的，表示剩余能量和该节点到簇首节点的距离比值。λ的计算公式为[6]

(3)

由式(3)可知，λ和剩余能量呈正比，和距离呈反比[8]。

1.5Cell LEACH

在蜂房结构的LEACH中，每个簇群由7个小单元格组成。每个单元格有一个单元格簇头，而每个蜂房有一个簇首。如图2所示，单元格簇头收集每个单元格里面的数据，然后进行融合，再传递给蜂房的簇首节点。这些簇首节点将来自各个蜂房的单元格里面的数据收集、汇总，进行融合再通过多跳传输给基站。

图2　Cell LEACH协议Fig 2　Cell LEACH protocol

最初，簇首节点和单元格簇头节点的都是随机选取的，因为所有的节点都具有相同的能量，但一轮后不同的节点含有的能量就不一样了。当单元格簇头的剩余能量低于阈值时，它就会向周围的节点发送消息通知它们，该节点就要消亡了。此外，它通知其他的节点，成为一个单元格簇首节点需要的最低能量。然后每个相邻节点将其剩余能量进行比较，把结果告知单元格簇首。基于比较结果，单元格节点将会决定哪些节点以最高的剩余能量获得下一个担当单元格节点的对象。

每个簇首都会在自己的表中保存其他簇首节点的记录，用来计算到基站的最短路径。由于在每一轮簇首节点都会变化，因此，从簇首节点到基站的路径也会变化。

只要网络正常工作，簇和单元格都没有动态变化,簇首和单元格簇首的结构会变化,一旦网络建立，基站就会向簇首发送数据请求信息，它将描绘感兴趣的区域。基站会将请求信息发送给单元格簇首，它们将转发给相应的传感器节点。如果节点有兴趣，并且愿意回应，那么它们会在给定的时间间隙内，把数据一个一个地传给目的节点[7]。

1.6EEE LEACH

通过实现多级聚类方法来使LEACH实现能量高效的扩展。起初，簇和簇首的选择方式是和LEACH协议一样，一旦簇首节点选出，第二层的分簇就开始，紧接着第二层的主簇首节点也选出。如图3所示，主簇首节点接收到来自簇首节点的融合数据信息，进一步压缩，融合传递给基站。通常情况下，主簇首节点比簇首节点少。通过引入主簇首节点，簇首节点的控制开销减少了。仿真结果显示，EEE LEACH在减少能量消耗方面性能优于LEACH[8]。

图3　EEE LEACH 协议Fig 3　EEE LEACH protocol

1.7LEACH Mobile[9]

LEACH Mobile是一个多跳路由协议，重点主要集中在簇中移动节点成员声明上。这个协议假定节点是中心可移动的。和基本LEACH协议一样，它也假设在每一轮有2个阶段，稳定阶段比初始建立阶段长。该协议假定节点总是有数据要发送，簇首节点在合适的时间间隙将数据请求发送到非簇首节点，如果非簇首节点在连续2轮，2个连续的数据请求信息内不回答，不响应，那么，簇首节点就当做该节点已经离开了这个簇，因此，从成员节点中移除，然后簇首节点更新TDMA表。

另一方面，在指定时间里，当移动节点还没有收到从簇首节点发出的任何的请求信息，它就意识到它不再是这个簇的一员，因此，向周围的簇广播加入信息，附近的簇首节点收听到这个信息，然后传递簇首广告信息给该节点。该移动节点将会决定在当前轮，加入哪一个簇。此外，它必须通知这个新的簇更新簇成员的信息表和TDMA计划表。该协议的优点是分组丢失少，但是能耗消耗较高。

1.8ECBR[10]

增强的簇路由(enhanced cluster-based routing，ECBR)协议是一种支持节点的移动性的协议。该协议是一种响应路由协议，它是路由在需要的时候计算。 ECBR的每个周期包括5个阶段：初始化阶段、簇形成阶段、簇头选择阶段、数据传送阶段、再分簇、路由重建阶段。在初始化阶段，节点发送Hello消息单跳发送到基站。问候消息包含节点的ID、目的节点ID、剩余能量、移动系数、离基站的距离。一个节点如果不发送Hello消息则表示不参加数据传输。下一阶段是簇的形成阶段，其中，节点根据DBSCAN(density-based spatial clustering of applications with noise)算法自动成簇。一旦簇建立完毕，基站就会根据剩余能量、移动性和到基站的距离来选择簇首节点。簇首就会分配时间间隙，给簇中的每一个节点，数据传输阶段开始。从源簇首到基站通过最短路径以多跳形式传输。每一轮后，重新分簇，路径也会重新计算，计算方式和前面的一致[10]。

2路由协议比较

上述协议分析比较如表1所示，其对比分析结果比较全面明确了各种路由协议应用与适用的场合。

3结论

路由分簇协议和其他协议相比较具有延长网络寿命的优点，这是由它们特定的分簇结构决定的。本文评述了一些基于簇的路由协议，并对其进行比较，这有助于认识哪些协议适合在哪些应用和场景中进行使用，进而节约整个网络的能量消耗。可以根据一定的参数如感知区域的面积、移动性、网络的寿命等来选择路由协议。例如，当场景中的监控区域很小时，适合采取单跳路由的方法，而对于大面积的检测区域，选择多跳路由协议较好。同样，在选择协议之前对其他的因素也要进行分析比较。明确不同种类的基于簇的路由协议和相应的特点将有助于研究的深入。

参考文献:

[1]袁辉勇,羊四清,李素君.无线传感器网络中基于分层的非均衡分簇算法[J].传感器与微系统,2010，29(2):101-103.

[2]Al-Karaki J N,Kamal A E.Routing techniques in wireless sensor networks:A survey[J].Wireless Communications,IEEE,2004,11(6):6-28.

表1　基于簇的路由协议比较

[3]王雍,杨海波,冯淑娟.无线传感器网络中一种能量有效的分簇算法[J].传感器与微系统,2008,27(12):19-21.

[4]Xiangning F,Yulin S.Improvement on LEACH protocol of wireless sensor networks[C]∥2007 International Conference on Sensor Communication Sensor Technologies and Applications,IEEE,2007:260-264.

[5]Ahlawat A,Malik V.An extended vice-cluster selection approach to improve V LEACH protocol in WSNs[C]∥2013 Third International Conference on Advanced Computing and Communication Technologies(ACCT),IEEE,2013:236-240.

[6]Wang N,Zhu H.An energy efficient algorithm based on LEACH protocol[C]∥2012 International Conference on Computer Science and Electronics Engineering(ICCSEE),IEEE,2012:339-342.

[7]Yektaparast A, Nabavi F H, Sarmast A. An improvement on LEACH protocol(Cell—LEACH)[C]∥2012 14th International Conference on Advanced Communication Technology(ICACT),IEEE,2012:992-996.

[8]Sharma M,Sharma K.An energy efficient extended LEACH(EEELEACH)[C]∥2012 International Conference on Communication Systems and Network Technologies(CSNT),IEEE,2012:377-382.

[9]Kim D S,Chung Y J.Self-organization routing protocol supporting mobile nodes for wireless sensor networks[C]∥The First International Multi-Symposiums on Computer and Computational Sciences,IMSCCS’06,IEEE,2006:622-626.

[10] Anitha R U,Kamalakkannan P.Enhanced cluster-based routing protocol for mobile nodes in wireless sensor networks[C]∥2013 International Conference on Pattern Recognition,Informatics and Mobile Engineering(PRIME),IEEE,2013:187-193.

Comparison of routing protocols based on clustering

WANG Gai-yun， HU Jin-yan

(School of Electronic Engineering and Automation,Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:Wireless sensor networks(WSNs)is consists of nodes which are small in size，low power consumption,low price.Until now,many protocols have been proposed,they are different in many aspects,like parameters selection,approach and so on.Among this,clustering routing protocol is one of the most famous approach,which is the core technology in WSNs that is widely used in environmental,medical and other fields.In clustering structure,the cluster head (CH) node gather information of other nodes in cluster for data fusion,and then transmit them to base station.It’s really necessary to carry out comparative study on some typical clustering structure algorithm.

Key words:WSNs; LEACH; clustering; routing protocols;comparison

DOI:10.13873/J.1000—9787(2016)04—0004—04

收稿日期：2015—07—02

中图分类号：TP 393

文献标识码：A

文章编号：1000—9787(2016)04—0004—04

作者简介:

王改云(1964-)，女，河南郑州人，教授，硕士生导师，主要研究方向为无线通信、智能控制、数据融合。