A Inter-Cluster Multi-Hop Routing Protocol Improved Based on LEACH Protocol*

CHEN Bingcai，YAO Huazhuo，YANG Mingchuan，LI Baojun，HE Lingchao

(1.Dalian University of Technology，College of Computer Science and Technology，Dalian Liaoning 116024，China; 2.Harbin Engineering University，College of Information And Communication Engineering，Harbin 150001，China; 3.School of Electronic and Information Engineering HIT，Harbin 150006，China)

A Inter-Cluster Multi-Hop Routing Protocol Improved Based on LEACH Protocol*

CHEN Bingcai1*，YAO Huazhuo2，YANG Mingchuan3，LI Baojun2，HE Lingchao2

(1.Dalian University of Technology，College of Computer Science and Technology，Dalian Liaoning 116024，China; 2.Harbin Engineering University，College of Information And Communication Engineering，Harbin 150001，China; 3.School of Electronic and Information Engineering HIT，Harbin 150006，China)

In order to balance energy consumption of wireless sensor networks，and prolong survival time of the networks，this paper studies several routing protocol based on uniform clustering and non-uniform clustering，and propose an inter-cluster multi-hop routing protocol improved based on LEACH protocol.The protocol introduces energy factor and distance factor to correct threshold function for LEACH protocol.In inter-cluster communication process，cluster head nodes communicate with Sink node by multi-hop，which forms an optimal path leads to Sink node among cluster head nodes.The result of experiment shows that，compared to LEACH protocol and EEUC protocol，the new protocol this paper proposed can balance effectively energy consumption of the networks，and prolong the life of wireless sensor networks.

wireless sensor networks;LEACH protocol;non-uniform clustering;multi-hops

作为新兴技术之一，无线传感器网络具有广阔的应用前景，对人们的社会生活产生极大的影响，已经引起世界范围的广泛关注［1］。然而，部署在监测区域内的传感器节点体积小、能量有限且在应用过程中不易更换电池，因此，节能问题一直是无线传感器网络的研究热点。如何均衡网络能量损耗，最大限度地延长网络生命周期亦成为无线传感器网络路由协议的评价标准。从网络拓扑结构来看，路由协议可以划分为平面路由协议和层次路由协议。研究表明，平面路由协议在工作过程中需要维护大量的路由表信息，不太适合大规模无线传感器网络，在某种程度上，层次路由协议解决了这个问题。LEACH协议是最具有代表性的一种层次路由协议，目前，许多层次路由协议都是基于LEACH协议的研究和改进，例如，Heinzelman等人在文献［2］中提出的集中式的簇构造算法LEACH-C以及考虑节点能量的算法LEACH-F［2］。文献［3］提出一种基于粒子群算法(PSO)的LEACHPSOC路由算法，主要思想是利用粒子群算法良好的收敛性和全局优化能力将整个网络区域的分割成多个子区域，然后考虑区域内节点剩余能量的因素进而选举出簇首［3］。文献［4］提出一种基于LEACH的助理簇头分簇算法，该算法根据簇头节点在无线传感器网络中所处的地理位置、剩余能量及簇内成员节点数目，动态决定是否需要在簇内产生助理簇头，这种方法在某种程度上降低了网络中节点的能量消耗，延长了网络的生存时间，但其无法弥补单跳通信所造成的能耗不均衡性问题［4］。上述这些协议都是基于均匀分簇的思想来均衡簇内成员节点的能量消耗问题，忽略了簇间的能量消耗均衡性问题。近年来，有许多学者对非均匀分簇路由协议进行了深入研究，文献［5］中提出一种非均匀分簇的无线传感器网络路由协议——EEUC协议，该协议考虑到靠近Sink节点的簇头由于转发大量数据而负载过重，从而过早耗尽能量而失效的问题，随机选取网络区域内能量较高的节点成为候选簇头，然后，利用非均匀的竞争范围来构造大小不等的簇，使靠近Sink节点的簇的规模小于远离Sink节点的簇，因此，靠近Sink节点的簇头可以为簇间的数据转发预留能量，但是，该协议的簇头选举过程比较繁琐，耗能较大［5］。文献［6］和文献［7］也提出类似于EEUC的非均匀分簇，但这两种算法的簇间通信策略仍有很大的改进的空间［6-7］。本文通过对以上几种协议的优缺点的详细分析，设计了一种基于LEACH协议改进的簇头多跳路由协议—CMRAOL (A Cluster Head Multi-hops Rout-ing Algorithm Improved Based on LEACH Algorithm)。

1 LEACH协议

LEACH协议是低功耗自适应聚类路由协议，主要包含以下三部分:动态地选举簇头、本地协调产生簇群、数据融合技术。LEACH协议定义了“轮”(Round)的概念，每轮包括两个阶段:簇头建立阶段和数据传输阶段［8-9］。簇头建立阶段负责簇头的产生、网络的分簇管理、簇内节点的组织等。数据传输阶段负责对数据的传输，数据融合等。

LEACH协议选择簇头的具体方法如下:在簇头选择过程中，对于一个节点来说，为其选取一个在0到1之间的随机数。如果节点的这个随机数小于这一轮所设定的门限值T(n)，节点n就充当本轮的簇头节点。门限值T(n)定义如式(1):

其中，p是节点成为簇头的期望百分比，r作为当前的轮数，G作为剩1/p轮中未成为簇头的节点集合，符号mod是求模运算符号。由此可知，当选过簇头的节点在接下来的(1/p-r)轮中不可能再被选作簇头，T(n)的值越大，节点当选簇头的概率越大，随着轮数的进行，未充当过簇头的节点被选作簇头的概率就会越来越大。

当节点被选作簇头以后，向外发送簇头广播信息。非簇头节点根据收到的簇头广播信息的信号大小决定要加入哪个簇，然后向决定要加入的簇的簇头发送入簇请求。簇头在收到请求后将该节点加入自己的路由表，并为每个节点设定一个TDMA定时消息，而后通知该簇中所有节点。在数据传输过程中，这些节点按照该TDMA时间表进行数据传输。每隔一个周期，整个网络重新进入簇形成阶段，开始新一轮的簇头选举过程。

2 新协议

LEACH协议是假设所有节点都可以直接与Sink节点通信，采用连续数据发送的模式及单跳路径选择的模式，在大范围监测应用中是不适合的，即使是在小规模网络中，距离Sink节点远的节点由于大功率通信，也会导致生存时间比较短;分布在离Sink节点较远区域的簇头节点与Sink节点进行通信时，将消耗过多能量，簇头可能会快速死亡，将影响传感器网络的生命周期。另外，协议中簇头节点的选择没有考虑节点的剩余能量和节点到Sink节点的距离等因素，有可能导致某些剩余能量小又距离Sink节点较远的节点的能量提早的耗尽;网络的负载平衡度随之下降。由此，本文提出了基于LEACH协议改进的簇头多跳路由协议

2.1 网络模型

所有传感器节点被随机部署在一个正方形区域内，对该传感器网络假设如下:①网络中的所有节点都具有位置感知能力;②节点具有唯一的标识ID，并且均匀地分布在监测区域内;③节点位置固定，能量有限，基站位置固定，能量不受限;④节点可以根据距离的远近来调整发射功率的大小;⑤当传输功率已知，节点可根据接收到的信号强度计算两节点间的距离;⑥每一个节点能与网络中其他任一个节点通信，也能与Sink节点直接通信。

2.2 成簇过程

与LEACH协议相似，网络中的所有节点随机产生一个0～1之间的随机数，如果这个随机数小于阈值T(n)，则会被选作簇头。其中，T(n)的计算方法如式(2):

其中，p为簇头节点数目占总节点数目的比率，为保证协议性能，我们参照LEACH协议中的最优簇头数取值，r作为当前的工作轮数，G表示网络中未成为正式簇头的节点集合，Wb=，A，B为控制因子;Emax(r)为第r轮全网节点剩余能量的最大值，Ei(r)为第r轮节点的当前剩余能量。可以看到，在条件相同的情况下，第r轮节点的当前剩余能量越大，阈值T(n)将会增大，该节点当选为簇头的概率也随之增大;反之，阈值T(n)将会较小，节点被选作簇头的概率随之减小，新协议增大了能量较高的节点被选作簇头的概率。davg为簇头节点到Sink节点的平均距离，。di为当前节点到Sink节点的距离。在相同条件时，di的值越大，当前节点距离Sink节点越远，阈值T(n)将会减小，节点被选作簇头的概率随之减小;di的值越小，当前节点距离Sink节点越近，阈值T(n)将会增大，节点被选作簇头的概率也就随之增大。这样，靠近Sink节点的簇头数会多余远离Sink节点的簇头数目，靠近Sink节点的簇的规模也就小于远离Sink节点的簇的规模，因此，靠近Sink节点的簇头就可以为簇间的数据转发预留能量。

2.3 簇间通信

CMRAOL协议采用与LEACH协议相同的一阶无线电模型，当发送距离较近时(d≤d0)，采用自由空间信道模型;当发送距离较远时(d＞d0)，采用多路径衰减模型［10］。因此，当两个距离为d的节点之间发送l比特数据时，发送端消耗的能量为:

接收端消耗的能量为:

其中，lEelec指信号处理所需的能量，单位为J/bit，εfs与εmp分别指自由空间模型以及多径衰落模型下的能量损耗，单位分别为J/(bit·m2)和J/(bit·m4)。本文中，我们取距离阈值d0为87.7 m。

用图G=(V，E)表示无线传感器网络，其中V= {v1，v2，…，vN}表示传感器节点的集合，则N=|V|表示传感器节点的个数。对任意两个传感器节点vI和vJ，如果vI位于vJ的通信范围内，并且vJ位于vI的通信范围内，则称传感器节点vI和vJ互为邻居节点，用坐标(xI，yI)和(xJ，yJ)分别表示传感器节点vI和vJ的地理位置，用下列式(7)计算传感器节点vI和vJ之间的距离dI，J:

本文假设每个传感器节点的通信半径为R，网络中只有一个Sink节点。则对任意传感器节点vI，其邻居节点集合为:

假设vI选择vJ作为其数据转发节点。为了简化问题分析，假设通信采用自由空间模型，并假设vJ将数据直接传输至Sink节点。则为了传输l比特的数据至Sink节点，vI和vJ消耗的能量如式(8):

由上式可知，d2(vI，vJ)+d2(vJ，DS)决定了网络能量消耗的高低。

在CMRAOL协议中，当节点vJ被选作簇头以后，以较高的发射功率在网络中广播包含其ID、节点的剩余能量Ere和到基站的距离dJ的“CH-State”消息。簇头vI收到来自其他簇头vJ的“CH-State”消息时，则计算两簇头节点间的距离d(vI，vJ)，如果d(vI，vJ)小于传感器节点的通信半径R，则把节点vJ的信息保存在邻居节点集合N(vI)中。如图所示:表1为簇头节点vI的邻居簇头节点vJ的路由信息表。

表1 邻居簇头路由信息表

当传感器节点vI需要将数据发送或转发给下一跳簇头节点时，则下一跳簇头节点只能从vI的邻居节点集合N(vI)内选择。如果d(vI，DS)＞TD_ MAX时(其中，d(vI，DS)为簇头节点vI到Sink节点的距离，TD_MAX为引入的阈值，设置为87.7 m)，则应该使用多跳路由的方式将数据传送给Sink节点。即在N(vI)中选择Wh最大的节点作为下一跳簇头节点。其中，为N(vI)中被选为中继节点vJ的剩余能量，d(vI，vJ)为簇头节点vI与中继簇头节点vJ的距离，d(vJ，DS)为中继节点vJ与Sink节点间的距离，以此类推，当簇头vJ接收到由簇头vI发来的数据后，继续从其邻居列表中选择Wh值最大的簇头节点充当下一跳簇头节点。由Wh权值计算公式可知:d2(vI，vJ)+d2(vJ，DS)的值越小，Ere的值越大，Wh的值就会越大。即簇头节点vI在邻居节点集合N(vI)中搜索距离Sink节点距离小、剩余能量大的邻居簇头节点作为下一跳节点。当d(vI，DS)≤TD_MAX或者邻居节点集合N (vI)为空时，则节点vI直接发送数据到Sink节点。

3 仿真实验及性能分析

3.1 参数设置

仿真参数如下:400个节点随机部署在200 m× 200 m的区域中，Sink节点的坐标为(100，250)，LEACH协议和CMRAOL协议的簇头选择概率p=0.1，而EEUC协议的候选簇头选择概率为p=0.4。节点的初始能量E0=0.5 J，电路能耗Eelec=50 nJ/bit，自由空间信道模型的能耗参数εfs=10pJ/bit/m2，多路衰减信道模型的能耗参数εmp=0.0013 pJ/(bit·m4)，数据融合能耗EDA=5 nJ/bit，控制因子A=0.2，B=0.8，数据包长度l=4 000 bit，控制包长度l1=100 bit［11-13］。

3.2 结果分析

实验采用MATLAB进行仿真，模拟实现了LEACH协议、EEUC协议和CMRAOL协议的性能比较。图1给出了LEACH协议、EEUC协议与CMRAOL协议网络生存周期的比较，以仿真轮数代表时间。LEACH协议、EEUC协议与CMRAOL协议的第1个节点死亡出现的轮数分别为156、164和731，最后一个节点死亡的轮数分别为765、843和951。从图1可以看出，CMRAOL协议相对于EEUC协议和LEACH协议，第1个节点死亡轮数和最后一个节点死亡轮数都相对延长，明显提高了网络生存周期。由于CMRAOL协议采用了优化的簇头选择方法和簇间多跳路由机制，有效地平衡了靠近基站的簇和远离基站的簇之间的数据传输能耗。

图1 网络生存周期比较

LEACH协议、EEUC协议与CMRAOL协议在相同的环境中进行仿真实验，Sink节点最终能够通过传感器网络获取的环境数据多少能够表现出协议性能的优劣。如图2所示，从LEACH协议、EEUC协议与CMRAOL协议仿真结果可知，Sink节点接收到的检测数据包数量分别是:15566、20838和34336。其中CMRAOL协议比LEACH协议高出120.5%，比EEUC协议高出64.7%。这说明CMRAOL协议在相同的检测环境条件下能够采集更多的环境数据，网络的能量利用效率较高。

图2网络发送的总数据

图3 和图4显示了3种协议在能量均衡方面的性能［14-15］。

图3网络节点剩余能量均值的变化曲线

图3 中，CMRAOL协议的网络节点能量均值一直都比LEACH或者EEUC的高，表明CMRAOL协议能够更有效地节约节点的能量。

图4网络节点剩余能量方差的变化曲线

图4 给出了3种协议能量方差随时间变化的比较，相对于EEUC协议和LEACH协议，CMRAOL协议的网络节点能量方差一直很低且变化不大，表明CMRAOL协议能够有效地均衡网络节点能量。从图3和图4可以看出，CMRAOL协议的能量均衡性能最好。

4 结束语

本文在研究LEACH协议基础上，对LEACH协议做了两点改进:①在选择簇头节点时，综合考虑了节点的剩余能量以及节点到Sink节点的距离两方面因素，使得剩余能量大且距离Sink节点较近的节点容易当选为簇头节点，这样有利于均衡整个网络的能耗。②在簇间通信过程中，对簇头节点采用了多跳传输技术，保证了数据尽快的传输到Sink节点，弥补了LEACH协议单跳的不足，从而使网络寿命得到了相应的延长。

本文分别对“网络生存时间”、“网络发送的数据”、“网络节点剩余能量均值”、“网络节点剩余能量方差”四项指标进行了仿真分析。仿真结果表明，相比于LEACH协议和EEUC协议，CMRAOL协议能够提高网络能量利用效率，有效平衡网络负载，延长了网络的生命周期。

［1］马祖长，孙怡宁，梅涛.无线传感器网络综述［J］.通信学报，2004，25(4):114-124.

［2］Heinzelman W R，Chandrakasan A，balakrishnan H.An Application-Specific Protocol Architecture for Wireless Micro-Sensor Networks［J］.IEEE Transaction on Wireless Communications，2002，1(14):660 -670.

［3］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26(1):116-121.

［4］龙际珍，陈沅涛，邓冬梅，等.基于LEACH协议的助理簇头分簇算法［J］.计算机工程，2011，37(7):103-105.

［5］Li CF，Ye M，Chen GH，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］//Proc of the IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems.Washington，2005:597-604.

［6］洪薇，胡健，龚代圣，等.一种基于层次的无线传感器网络非均匀分簇路由协议［J］.计算机与现代化，2012:80-84.

［7］薛晓亮.基于LEACH协议的WSN多跳非均匀分簇路由算法研究［D］.华东理工大学信息学院，2010.

［8］孙利民，叶驰，廖勇.传感器网络的路由机制［J］.计算机科学，2004，31(1):54-57.

［9］莫宵雁.无线传感器网络分簇式路由协议的研究和设计［D］.浙江大学信息学院，2006.

［10］郑希，基于LEACH的无线传感器网络路由协议能耗性能的研究及优化［D］.上海:上海交通大学计算机科学与工程系，2009.

［11］刘铁流，巫咏群.基于能量优化的无线传感器网络分簇路由算法研究［J］.传感技术学报，2011，24(5):764-770.

［12］李岩，张曦煌，李彦中.基于LEACH协议的簇头多跳(LEACHM)算法［J］.计算机工程与设计，2007，28(17):4158-4160.

［13］余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法［J］.电子学报，2008，36(7):1309-1313.

［14］刘园莉，李腊元，卢迪.节能的无线传感器网络分簇路由协议的研究［J］.传感技术学报，2010，23(12):1792-1797.

［15］李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27-36.

陈炳才(1978-)，男，福建漳平人，工学博士，副教授，研究生导师，主要研究方向为无线传感器网络、卫星通信网络，cbc9@qq.com;

么华卓(1987-)，女，黑龙江哈尔滨人，硕士研究生，主要研究方向为无线传感器网络路由协议。

一种基于LEACH协议改进的簇间多跳路由协议*

陈炳才1*，么华卓2，杨明川3，李宝君2，赫凌超2
(1.大连理工大学计算机科学与技术学院，大连116024;2.哈尔滨工程大学信息与通信工程学院，哈尔滨150001; 3.哈尔滨工业大学电子与信息工程学院，哈尔滨150006)

为了均衡无线传感器网络的能量消耗，延长网络的生存时间，在研究几种基于均匀分簇和非均匀分簇的路由协议基础上，提出一种基于LEACH协议改进的簇间多跳路由协议。该协议引入能量因子和距离因子修正了LEACH协议的阈值函数。在簇间通信过程，簇头节点与Sink节点之间采用多跳通信方式，簇头与簇头之间形成一条通向Sink节点的优化路径。实验结果表明，相比于LEACH协议和EEUC协议，本文提出的新协议能够有效的均衡网络的能量消耗，延长无线传感器网络的寿命。

无线传感器网络;LEACH协议;非均匀分簇;多跳

TP393

A

1004－1699(2014)03－0373－05

2013-10-21修改日期:2014-02-28

C:6150P

10.3969/j.issn.1004－1699.2014.03.019

项目来源:国家自然科学基金项目(60902014);国家自然科学基金项目(61101126)