一种基于LEACH路由协议的改进算法

蔡悦洁，胡方明

(西安电子科技大学电子工程学院，陕西西安 710071)

一种基于LEACH路由协议的改进算法

蔡悦洁，胡方明

(西安电子科技大学电子工程学院，陕西西安 710071)

无线传感器网络的生存时间受传感器节点软硬件条件的限制，改进传感器网络路由协议是延长网络生存时间的有效途径。LEACH协议是最早提出的经典分层路由协议，文中基于LEACH协议提出改进，应用K－medoids算法改进LEACH协议的簇首分簇机制，并通过Matlab仿真实验，证实了改进后的LEACH算法在均衡化网络能耗，延长网络的生命周期方面具有优越性。

无线传感器网络;路由协议;LEACH;K－medoids

随着通信、传感器和嵌入式计算技术的快速发展，具有通信、感知和数据计算处理能力的微型传感器节点得到广泛应用。由这些传感器节点构成的无线传感器网络(Wireless Sensor Network，WSN)在军事、医疗健康、环境监测、深空探测等领域有广阔的应用前景，已经引起了人们的关注［1－5］。

由于无线传感器网络中传感器节点受其自身软硬件条件的限制，其能源有限，计算、存储和通信能力较弱，同时存在节点死亡而退出网络以及新节点加入扩展网络使得无线传感器网络的拓扑结构处于动态变化中的情况，因此急需深入研究无线传感器网络路由协议，从而延长无线传感器网络的生命周期［6－7］。

无线传感器网络的路由协议主要功能是寻找源节点和目的节点之间的优化路径，实现数据分组沿着优化路径正确转发。按照网络的逻辑结构分类，路由协议可以分为平面路由协议和分层路由协议。平面路由中各个节点都将数据传送到Sink节点，所有节点都具有相同的地位和功能，节点之间相互协作共同完成感知和数据处理任务。分层路由协议引入分层管理机制，网络节点通常按照不同的分簇算法分成相应的簇(Cluster)。每个簇由一个簇首(Cluster Head)和多个簇成员(Cluster Member)组成，多个簇首节点形成更高一级的网络，在高一级网络中，又可以分簇，再次形成更高一级的网络，直至最高级。LEACH协议就是最为典型的一种分层路由协议，针对LEACH协议的成簇方式引入一种K－中心点算法来改进LEACH算法的成簇机制，从而降低网络成簇阶段的能耗［8］。

1 LEACH协议

1.1 算法描述

LEACH协议将无线传感器网络中的节点分成若干个簇，通过随机选择簇首节点，平均分担网络的能量负载来实现降低网络能耗、延长网络生命周期。LEACH定义了“轮”(Round)的概念，协议分为多轮，每一轮由簇准备阶段和稳定阶段组成，簇准备阶段和稳定的时间总和称为一轮［9－10］。

在簇准备阶段，LEACH协议采用完全分布式机制产生簇头，设定一阈值T(n)，每个传感器节点从0～1随机数中任意选择一个值，若当前轮中这个随机数值小于设定的阈值T(n)，那么这个节点就当选为簇头，阈值T(n)按式(1)计算。

其中，p是网络中簇首所占比例;r是当前轮数;G是在最后1/p轮中没有成为簇首节点集合;n指某一节点;T(n)实际上是在第r轮尚未做过簇首的节点当选为簇首的平均概率。

节点被选为簇首节点后，会主动向网络发送广播信息。其他节点根据接收到的信息选择合适的发送簇首作为自己的簇首，并加入这个簇首的簇，节点选择簇首的原则是选取信号强度最大的簇首加入。之后簇首节点建立TDMA调度，保证了簇内节点只在相应的时隙发送数据，减少了数据传输时的冲突。

在稳定阶段，成员节点在自己的时隙里将数据发送给簇首节点，簇首节点对收集的数据进行融合，并将结果发送给Sink节点。之后重新选举簇首节点进入新一轮循环。

1.2 LEACH协议的优缺点

LEACH协议的优点:随机选取簇首节点，将能量消耗平均分配到所有节点，网络负载比较均衡，仿真表明，相比于一般的平面路由协议，LEACH协议可以将网络生命周期延长15%;由于采用层次结构，簇首节点形成高一层的网络，使得节点路径的选择及路由信息的储存都非常的简单直接，节点不需要储存大量路由信息，对于节点的要求降低;LEACH中采用的成簇技术使网络具有较好的扩展性，同时簇首节点的轮流选择使网络具有较强的健壮性。

LEACH协议的缺陷:LEACH协议簇首的选取是随机的，无法控制簇首在网络中分布的位置，建簇时可能出现一些不合理的分簇方案，出现簇首分布过于集中或者分布于网络边缘，各个簇中节点数量不均衡，簇首与簇内节点的通信距离过远，从而造成不必要的能量消耗;LEACH协议节点当选为簇首节点的概率均等，这可能会使一部分能量少的节点被选为簇首，能量低的节点担任簇首节点时，将导致节点能量会过快地耗尽自身能量而影响网络的正常运行;LEACH协议要求网络中的节点与Sink节点能够直接通信，这就限制了网络的扩展性，使其不适用于大型网络。因为对于大型网络中里簇首节点较远的成员节点和离Sink节点较远的簇首节点而言，通信所造成的能耗将远远大于其他节点，这就影响了网络的生命周期，降低网络性能。

针对LEACH协议的簇首选取机制存在的缺陷，引入K－medoids算法改进簇首选取过程。

2 K－medoids算法改进LEACH协议

K－medoids算法属于划分方法中一种常见的聚类算法，围绕中心点的划分PAM(Partitioning Around Medoids)是最早提出的K－中心点算法之一［11］。当存在噪声和孤立点时，算法仍具有较好的健壮性和鲁棒性。

K－medoids算法先给每个簇随机选择一个初始代表对象。剩余的对象根据与其代表对象的距离分配给最近的一个簇，然后反复用非代表对象来替换代表对象，以改进聚类的质量。聚类质量用一个代价函数来估算，该函数度量一个非代表对象是否是当前一个代表对象的适合的代替者，如果是就进行替换，否则不替换［12－15］。

为判定一个非代表对象Orandom是否为当前代表对象Oi合适的替代者，对于每个非中心点对象P，每当重新分配时，平方误差对代价函数有影响。

平均误差公式

替代的总代价是所有非中心点对象所产生的代价之和。如果总代价是负的，那么实际的平方误差将减小，即替换后的簇内差异会变小，Oi可以被Orandom替代。如果总代价总是正的或者为零，那么就表示算法不能产生一个有效的替换，即此时算法收敛。

算法描述:输入，结果簇的数目k，包含n个对象的数据库。输出，k个簇，使得所有对象与其最近中心点的相异度总和取得最小。

(1)选择、优化初始中心点并作初步划分。选择中心点，在n个对象中随意选择k个对象作为初始的中心点;初始划分，以当前中心点对其他对象进行初始划分;微调，在划分得的各簇中对中心点进行微调。继续划分，以当前中心点对其他对象进行划分。

(2)执行增量中心候选集K－medoids算法。主要有两步:1)轮换中心并计算代价。2)实施中心替换。该阶段算法流程如图1 所示［17－18］。

通过初始中心的调整，使更多的中心点都有可能是最后聚类结果对应的中心点，收敛速度快。

K－medoids算法能在付出较小内存代价的前提下有效处理大数据集，适合大量样本的情况，适用于LEACH协议分簇选举簇首的要求。

另外，由于在每轮分簇选簇首节点时都采用K－medoids算法，从初始点到结束所需迭代的次数较多，这样在选择簇首节点时会消耗过多的能量来调整簇首的位置，所以需要合理地设定每一次使用K－medoids算法迭代的次数，使簇首在尽量少的调整次数中被调整到理想的位置［19－20］。

图1 执行增量中心候选集K－medoids算法流程

3 Matlab仿真

本文使用Matlab分别对传统LEACH算法和引入K－medoids算法改进后的LEACH算法进行仿真。

3.1 簇首分簇仿真比较

仿真环境:

(1)100个随机分布的节点和一个固定的Sink节点，Sink 节点坐标为(0，0)。

(2)网络平面区域:100×200，等价于50 m×100 m。

(3)网络分簇:6个簇。

(4)每个无线传感器节点的初始能量:2 J。

(5)仿真次数:10次。

图2为其中一次传统LEACH协议通过随机选取簇首节点的仿真图，图中最小的簇仅含有7个节点，最大的簇含有29个节点。经多次仿真发现传统LEACH协议的分簇不均衡，关键是同一个簇中不同的成员节点到簇首的距离相差很大。

图3是采用K－medoids算法分簇选举簇首的一张示意图，其中包含节点最多的簇有24个节点，包含节点最少的簇有12个节点。经多次仿真发现，相比于传统的LEACH协议随机选举簇首分簇的方法，采用了K－medoids算法改进后整个网络划分相对而言更均衡，同时，大部分节点到簇首的距离更接近平均值。

图2 传统LEACH协议分簇产生簇首的示意图

图3 采用K－medoids算法分簇产生簇首的示意图

3.2 改进前后节点存活数目的比较

网络中每轮存活的节点数目反映了无线传感器网络性能的优劣。存活的节点数目越多，网络覆盖区域就越广，下一轮参与选举簇首的节点就越多，也延长了网络的生命周期。下面是传统LEACH协议和改进LEACH协议在节点存活数目上的比较。

参数:节点数目NodeNums=100;仿真区域AreaR=100;节点数据传输半径 NodeTranR=10;仿真时间MaxInteral=200 s;簇首节点的百分比Pch=0.05，即100个节点的网络形成5个簇首划分为5个簇节点每次发送的数据量Kbit=2 000 kbit。

图4 节点存活数目对比

由图4可见，改进型LEACH协议在同一时间点的节点存活数目明显比传统LEACH多，并且节点存活时间相对而言更长。所以优化后的网络簇首选择方案能提网络的性能，延长网络的生命周期。

4 结束语

在LEACH协议的基础上，引入K－medoids改进传统LEACH算法的簇首分簇机制，均衡化网络的能量损耗，从而延长无线传感器网络的生命周期。

［1］李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展［J］.软件学报，2003，14(10):1717 －1727.

［2］司海飞，杨忠，王珺.无线传感器网络研究现状与应用［J］.机电工程，2011，28(1):16 －20.

［3］叶湘滨，陈利虎，胡罡.无线传感器网络在环境监测中的应用［J］.计算机测量与控制，2004，12(11).

［4］李翔，谭敏生，李攀.浅析无线传感器网络在医疗系统中的应用［J］.工业控制计算机，2011，24(4).

［5］卿利，朱清新，王明文.异构传感器网络的分布式能量有效成簇算法［J］.软件学报，2006，43(5):51－58.

［6］TERRY J.Ten emerging technologies that will change the world［J］.Technology Review，2003，106(1):22 －49.

［7］MHATRE V，ROSENBERG C.Design guidelines for wireless sensor networks communication clusetering and aggregation［J］.Ad － hoc Networks Journal Elsevier Science，2004，2(1):45－63.

［8］ROYER E M，TOH C K.A review of current routing protocols for Ad hoc networks［J］.IEEE Personal Communications，1996，6(2):45 －55.

［9］WENDI B HEINZELMAN，ANANTHA P CHANDRAKASAN，HARI BALAKRISHNAN.An application specific protocol architecture for wireless microsensor networks ［J］.IEEE Transactions on Wirel Ess Communications，2002，1(4):660－670.

［10］WENDI B HEINZELMAN，ANANTHA P CHANDRAKASAN，HARI BALAKRISHNAN.Energy efficient communication protocols for wireless microsensor networks［C］.the Hawaii International Conference on System Sciences，2000.

［11］HAN Jiawei，KAMBER M.数据挖掘概念与技术［M］.2版.北京:机械工业出版社，2008.

［12］吕振，白婷婷，马兴朋，等.浅谈无线传感器网络路由协议［J］.微计算机信息，2010，26(10):98 －100.

［13］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14(7):1282 －1291.

［14］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［15］PERILLO M，CHENG Z，HEINZLEMAN W.An analysis of strategies for mitigating the sensor network hot spot problem［C］.Proc.of Collaboratecom，2005.

［16］NISHIMURA C E，CONLON D M.IUSS dual use:Monitoring whales and earthquakes using SOSUS ［J］.Mar Technol.Soc.J，1994，27(4):13 －21.

［17］夏宁霞，苏一丹，覃希.一种高效的K－medoids聚类算法［J］.计算机应用研究，2010，27(12):4517 －4519

［18］李钢.无线传感器网络路由协议的研究与仿真［D］.北京:北京邮电大学，2008.

［19］李岩.无线网络路由协议的研究——基于LEACH的无线传感网络路由协议研究［D］.无锡:江南大学，2008.

［20］陈耀典.无线传感器网络LEACH分簇路由协议的改进与仿真［D］.广州:中山大学，2010.

An Improved Algorithm of Routing Protocol Based on LEACH

CAI Yuejie，HU Fangming
(School of Electronic Engineering，Xidian University，Xi'an 710071，China)

Due to the limitation of software and hardware of the sensor node，lifetime of Wireless sensor network(WSN)is limited，and the research of WSN routing protocol is one of the most effective ways to extend the network lifetime.LEACH protocol is a classical cluster routing protocol.This paper proposes an improvement based on LEACH protocol，applying K-medoids algorithms to improve the mechanism of the selection of cluster head.Simulation results have confirmed that the improved LEACH protocol is superior in extending network lifetime and equalizing energy wastage.

wireless sensor network;routing protocol;LEACH;K-medoids

TP212.9

A

1007－7820(2012)08－128－04

2012-01-17

中央高校基本科研业务费专项基金资助(K50510020034)

蔡悦洁(1986—)，男，硕士研究生。研究方向:无线传感器网络。