一种基于分层的簇首成链WSN路由协议

王艳红

摘 要：能量有效利用是路由算法首要目标，基于LEACH和PEGASIS算法设计出一种基于分层的簇首成链WSN路由协议（Layer Based Cluster-Chain Routing Protocol for Wireless Sensor Networks），该算法将网络分成层并分成两个阶段运行，第一阶段每层随机选出簇首并将剩余节点按照贪心算法成簇，第二阶段在所有层中选出剩余能量最大一个簇首节点作为Leader节点直接与基站通信，其余簇首节点选择离自己最近的簇首节点多跳传输。并实验表明改进的算法能有效延长网络生命周期，降低数据延迟。

关键字：无线传感器网络；LEACH；PEGASIS；路由协议

中图分类号：TP393 文件标志码：A 文章编号：2095-2163（2015）05-

Cluster-Chain Routing Protocol for Wireless Sensor Networks based Layer

WANG Yanhong

（Nantong Shipping College Management information Department， Nantong Jiangsu 226010，China）

Abstract： Energy effective utilization is the most important goal to routing algorithm . Based on LEACH and PEGASIS algorithm， this paper designs a Routing Protocol on base of hierarchical Cluster heading into Chain （Layer -based Cluster-Chain Routing Protocol for Wireless Sensor Networks）. The algorithm separates network into layers and runs in two stages. In the first phase each layer of the nodes clusters according to the greedy algorithm， and in the second stage it selects the largest residual energy of a cluster head node to communicate directly with the base station as a leader node. The rest of the cluster head nodes choose the nearest cluster head nodes to do multi-hop communication. And the experiment shows that the improved algorithm can effectively prolong the network life cycle and reduce the data latency.

Key words： Wireless Sensor Network （WSN）； LEACH； PEGASIS； Routing Protocol

0引 言

无线传感器网络（Wireless sensor networks ，WSN）是一种特殊的网络，与以往的传统无线网络相比具有鲜明显著的特点。无线传感器网络由成千上万微型传感器节点所组成，无线传感器网络节点由于受到成本的限制，使得节点的感知能力、通信能力和数据处理能力都非常有限[1]。正是无线传感器网络中节点的这些物理特性使得无线传感器网络路由协议在设计时面临着很多挑战。其中，无线传感器网络节点由于电池供电能量有限则可证得当下即是无线传感网络路由协议设计升级时的重点研发因素。基于此，有效利用节点能量、并延长网络生命周期就势将成为路由协议设计中的现实关键研究课题[2-3]。相应地，本文将针对这一领域方向展开如下具体分析研究。

1相关工作

无线传感器网络路由协议根据网络拓扑结构可以将路由协议分成两大类，平面路由和分簇路由。其中的分簇路由将网络分成多个子集，每个子集称为一个簇，由簇首和多个簇内节点组成。由于分簇协议能够平衡节点负载，与平面路由相比分簇协议能够有效地延长网络生命周期。因此，分簇协议是近期学者研究的重点。典型的分簇路由主要有LEACH、PEGASIS、HEED、TEEN等。尤其是LEACH[4]是最早提出的、也是经典的分簇协议之一，LEACH协议采用“轮”机制，每轮分为簇首选举、成簇和数据传输三个阶段，簇首负责收集簇内节点数据并将数据直接传输给基站。相对于一般的平面静态路由协议，LEACH可以将网络生存时间延长近15%。但是LEACH协议仍然表现有明显的不足，例如随机选取簇首导致簇首分布不均匀，簇首与基站直接通信导致通信能耗过大。这些都影响着网络的生命周期，所以大量学者基于LEACH做了很多改进性研究。文献[5，6]主要从簇首的选举进行优化，在LEACH协议中引入竞争机制，保证簇首的分布。文献[7]针对LEACH协议中簇首直接与基站通信的缺点提出了一定改进，在簇首间采用多跳传输通信，降低远离基站簇首节点的通信能耗，从而延长网络生命。文献[8]同样是针对簇首间通信的改进，簇首间以基站为根形成最小生成树多跳通信。

PEGASIS[9]协议是在LEACH基础上改进演变而来的，与LEACH协议不同的是PEGASIS协议将网络看成一个簇，只有一个簇首。PEGASIS协议的主要思想是将全网节点形成一条链，链上随机选出簇首节点，在数据传输阶段链上的普通节点只与自己相邻的节点通信，最后数据汇聚到链上的簇首节点，簇首节点直接将数据发送到基站。由于PEGASIS协议在全网形成一条链，链上的节点只需与相邻的节点通信，如此即显著降低了节点的通信能耗，但在此同时PEGASIS协议却增加了数据传输的时延。

为了有效延长网络生命周期，基于LEACH和PEGASIS协议的众多后续升级算法则相继获得提出。文献[10]提出了簇首成链算法，该算法就是基于LEACH和PEGASIS两种协议的结合改进，在改进的簇首选择机制的基础上，簇首按照PEGASIS协议形成链，算法中采用链式簇首间链式能够平衡簇首的负载，但是并没有考虑链式路由带来的数据延迟。为了解决这个问题，该文设计出了基于分层的簇首成链协议，协议将网络分层，每层中的节点采用贪婪算法形成一条链，每层随机选出簇首，簇首间同样采用链式通信。其后的应用实践表明该协议能够适应大型网络结构、降低能耗、延长网络周期。

2 系统模型

2.1模型假设

假设传感器网络中 N 个传感器节点分布在一定的区域当中，并且具有以下性质：

（1） 节点在监测区域内均匀分布并保持静止不动，所有的节点是同质的，即初始能量、计算能量、存储能力都相同；

（2） 每个节点能够计算自身的剩余能量以及自身的地理位置；

（3） 基站位于传感器监测区域以外的固定一点，基站能量不受限制，物理安全有保证；

（4） 相邻监测区域内的数据具有相关性，可以进行数据融合；

（5） 节点之间通信链路是对称的，例如节点a发送数据到节点v消耗的能量等于节点v发送数据到节点a的能耗。

2.2 能量模型

本协议的能量模型采用LEACH协议中的能量模型[11]。式（1）为发射 bit数据耗损的能量，由发射电路耗损和功率放大耗损两部分构成。功率放大耗损根据发送者和接收者之间的距离（ 表示通信距离， 为其临界值）分别采用自由空间模型和多路径衰减模型。具体地， 为发射电路的耗损能量； 和 分别表示两种信道模型下功率放大所需能量。式（2）为接收 数据的能量耗损，仅由电路耗损引起。

数据发送： （1）

数据接收： （2）

3改进的路由协议

本文结合 LEACH 和 PERASIS 的协议各自的优点，提出一个基于分层的簇首成链的路由协议LCCRP（Layer Based Cluster-Chain Routing Protocol）。LCCRP算法摒弃了LEACH 和PERASIS 各自的缺点，采用了如下的分层思想，即簇内成链传输数据至簇首，数据汇总后再簇首成链传送数据至基站。在此假设一个无线传感器网络的N个节点均匀分布在L（m）×L（m）的区域内。如果N等于100，即可假设每层的节点个数等于10，那么就把区域分成了10层，如图1所示。

图1 100个节点被分成10层

Fig.1 100 nodes are divided into 10 layers

3.1成簇阶段

在这个阶段，每层随机选择一个节点作为簇首，然后簇首节点向层的两端发送消息宣告自己是簇首节点，之后每层的端节点向距离自己最近的邻居节点发送数据，邻居节点接收到数据后、并将数据融合后再转发给自己的邻居节点，直到每层的数据都到达簇首。本文采用类似LEACH协议中的簇首选举机制，簇首选举公式如公式（3）所示。

（3）

簇首选举成功之后，每层节点入簇，和LEACH协议不同的是节点不再根据收到信号强弱加入簇，而是由每层选举出来的簇首向层两端最远距离发送成链的信息，每层距离簇首最远的两个端点则将选择离自己最近的节点作为下一跳，最终每层的节点形成一条链通信。

在此，研究中举例说明了某一层的成簇过程，具体如图2所示。图2中黑色的节点代表随机选出的簇首节点。在开始的时候层两端的节点收到由簇首发来的消息，两端的两个节点就可以把数据以及簇首的消息发送给邻居节点，邻居节点在收到上个节点发来的数据后将自己的数据与之融合再转发给邻居节点，以此类推直至数据都到达簇首。

图2 簇内数据传输过程

Fig.2 Data transmission within a cluster

在每层内节点只须与自己相邻的两个节点通信，减少了节点之间传送数据的平均距离。簇内的节点除了两端的节点都要将数据融合后再转发，减少了数据转发量。当分簇完成之后，进入到第二个阶段，簇间路由的形成。

3.2簇间路由

如上面所述，当所有层的节点将数据发送给每层的簇首之后，即进入到簇间通信的阶段。首先在所有的簇首中选出剩余能量最大的作为簇首链的Leader节点。每个簇首节点向其他簇首节点广播自己的剩余能量消息。每个簇首节点接收到这样消息时对比自己的剩余能量与接收到的节点的剩余能量大小。如果一个簇首节点发现自己的能量比其他的簇首节点都大，就将作为Leader节点并向其他簇首广播。当有两个以上的簇首剩余能量都最大，为了避免冲突，第一个发送广播消息的簇首则当选Leader。每层的簇首同样看成一个簇，Leader节点即是簇首，其他层的簇首节点形成链式多跳通信。Leader节点向离自己最远的两个簇首发送消息，簇首间以贪心算法形成链。簇首节点依次向自己的邻居节点发送数据。邻居节点接收到数据后将数据与自己的数据融合后转发。当所有数据到达簇首的Leader节点后，Leader节点将数据与自己的数据融合后发送给基站。在图3中显示了LCCRP算法的数据传输过程。

图3 LCCRP算法的数据传输过程

Fig.3 Data transmission process of the LCCPR algorithm

3.3数据传输

当簇间路由形成阶段完成之后网络进入数据传输，首先每层的节点收集数据，之后每层的簇首向层内两端节点发送消息，两端的节点接收到簇首发来的消息就将自己的数据按照层内的数据链转发给离自己最近的邻居节点，邻居节点收到上个节点发来的数据并与自己的数据融合后转发至邻居节点依次类推直到层内的数据汇总到簇首，然后簇内节点进入休眠状态。在簇间路由中数据的传输与簇内传输类似，由选出的Leader节点向最远的两个簇首节点发送令牌环，离Leader最远的两个簇首节点将接收到的数据融合后，继而转发给临近层的簇首，直至数据汇聚到Leader节点，Leader节点则与基站直接通信。

3.4改进后的算法过程

LCCRP算法的执行过程如下：

（1）网络分层，由基站将网络均匀分层。

（2）簇首选举，采用类似LEACH协议相同的选举方法选出每层的簇首节点。

（3）各层成链，由选举出的簇首节点向层的两端节点发送成链信号，每层节点采用贪婪算法形成链。

（4）簇间路由，在所有的簇首中选出能量最大的簇首节点作为Leader节点，簇首间的通信同样以Leader节点为簇首们的簇首形成链。最后由Leader节点直接与基站通信。

（5）数据传输，当簇首间路由建立之后，网络进入数据传输，首先每层的簇首节点向链上最远的两端节点发送收集数据的信息包，每层的节点依次将数据转发至本层的簇首节点，之后每层的簇首节点同样通过簇间路由将数据转发至Leader节点，最后由Leader节点将数据直接发送给基站。

4仿真分析

本文采用了 MATLAB 软件对 LCCRP算法，LEACH 算法和 PEGASIS 算法进行了对比，分别从网络生存周期和数据传输时延两方面考虑，评价 LCCRP算法的性能。在范围为100 m×100 m 的区域内有100个传感器节点，设节点的坐标值在（ 0，0） ～（ 100，100）范围内变化，BS 设定于（ 50，-25） 的位置上，节点的初始能量 =1J，发送和接收电路通信耗能 =50nJ/bit，数据融合耗能 =5nJ/bit/ signal， 和 分别为0.001 3 pJ/bit/m^4、10pJ/bit/m^2。

LCCRP 算法改进了已有算法中节点负载不均衡，能量消耗差异等缺点，以延长整个网络生存周期为设计目标，结合LEACH协议和PEGASIS协议，汲取了两者的优点、同时摒弃了各自不足，通过采用簇首间链式多跳通信降低了簇首与基站直接通信的能耗，并且将网络分层结合使得每层的链明显减短，由此而降低了PEGASIS协议将整个网络形成一条链带来的数据延迟。

其中图 4 表示的是 LCCRP 协议与LEACH 协议，PEGASIS 协议平均一轮能量消耗的比较。由于传感器的节点分布，簇头的选择以及成链的随机因素很大。所以每种协议循环计算 50 次取其平均值从而得到结果。在网络中传输通信是网络中最大的能量消耗因素，LEACH协议中所有簇首都与基站直接通信，尤其是远离基站的簇首节点消耗的能量更大，PEGASIS协议通过链式通信能够改进LEACH协议的缺点，每轮能耗明显降低了，改进的协议同样采用PEGASIS的链式通信，所以三种协议相比，LEACH协议中每轮的能耗最大。从图4可以看出LCCRP能量消耗几乎和PEGASIS 协议相同，但只有LEACH协议的20%左右。可以得出改进的协议相比较LEACH协议则能有效演唱网络的生命周期。图5表示三种协议数据延迟对比，从图中可以看到改进的协议数据延迟和LEACH协议相同，只是PEGASIS协议的28%。

图4 三种协议平均能量消耗对比

Fig.4 Comparing the average energy consumption of three protocols

PEGASIS协议理论上的性能是非常好的，但是会带来较大的滞后性，同时链上个别节点的失效，会导致数据采集的整体失败。LCCRP协议将网络分层成链，避免了整个网络形成一条链时数据传输的时延。为了实验的简便，假设一次数据转发计为一个单位的数据延迟。图5表示三种协议数据传输延迟对比情况。LEACH协议每轮的分簇数目不定，所以同样统计50轮分簇数目的平均值来计算延迟，从图中可以看出LCCRP协议的延迟略高于LEACH协议，但只有PEGASIS协议的22%左右。由此可得，改进算法结合上述两个协议的优点不仅有效地降低了能耗，而且保证了必要的实时性。

图5 三种协议延迟比较

Fig.5 Comparing the delay of three protocols

5结束语

论文以平衡网络负载延长网络生命周期为研究目的，提出了一种基于分层的簇首成链路由协议LCCRP，该协议综合了 LEACH 协议和 PERASIS 协议的优点，将网络分为层，并在每层中按照贪心算法成簇，整个网络数据传输分成两个阶段运行，第一阶段每层的节点将数据融合发送给邻居节点直到发送到簇首节点，第二阶段簇首节点选出剩余能量最大一个簇首节点作为Leader节点，并直接与基站通信。簇间通信由簇首选择离自己最近的簇首节点多跳传输。由仿真结果可得，改进的新协议在更大程度上能够优化节点能量，延长网络的生命周期，并且分层的成链操作也可减小数据的传输时延。

参考文献：

[1]程英，高庆德，吴晓朝.无线传感器网络节能路由协议的改进[J].计算机科学，2012， 11（39）：93-95.

[2] LOTF J J， HOSSEINZADEH M， ALGULIEV R M. Hierarchical routing in Wireless Sensor Networks： A survey[C]//Proceedings of 2010 2nd International Conference on Computer Engineering and Technology， Chengdu， China： IEEE， 2010： 650-654.

[3] WAWARE S， SARWADE D N， GANGURDE P. A review of power efficient hierarchical routing protocols in Wireless Sensor Networks[J]. International Journal of Engineering Research and Applications （IJERA）， 2012， 2（2）： 1096-1102.

[4]刘园莉，李腊元，卢迪.节能的无线传感器网络分簇路由协议的研究[J].传感技术学报，2010， 23 （12）： 1792-1797.

[5]张然，覃少华. 基于LEACH的无线传感器网络分簇路由协议[J].计算机工程与设计，2012，33（4）：1333-1335+1336.

[6]姚光顺，温卫敏，张永定，等.改进的无线传感器网络簇首选择策略及其路由算法[J].计算机应用，2013，33（4）：908-911+915.

[7]周冬鑫，金文光，容志能. 基于分层的无线传感网络多跳分簇路由算法[J]. 传感技术学报，2011，24（1）：73-78.

[8]张明才，薛安荣，王伟.基于最小生成树的非均匀分簇路由算法[J].计算机应用， 2012，32（3）. 787-790.

[9] KRISHNAVENI P， SUTHA J. Analysis of routing protocols for wireless sensor networks[J].International Journal of Emerging Technology and Advanced Engineering，2012，2（11）：401-407.

[10]張震，闫连山，潘炜，等.基于LEACH和PEGASIS的簇头成链可靠路由协议研究[J].传感技术学报， 2010， 23（8）： 1173-1178.

[11] LIU Xuxun.A survey on clustering routing protocols in Wireless Sensor Networks [J]. sensors， 2012， 12： 11113-11153.