引言

　　无线传感器网络（Wireless Sensor Network ,简称WSN）是监视远程环境的有力工具之一，它的基本功能是收集并返回传感器节点所在监测区域的信息。由于工作环境和自身构造的限制，传感器节点一般是电池供电，并且节点的更换和充电也较难实现。因此，降低节点能耗，延长网络生命周期是无线传感器网络传输机制的一个主要研究目标。

　　网络数据传输离不开路由协议，路由协议对网络的整体性能有重要影响，因此，作为无线传感器网络技术之一的路由协议一直是研究的热点。

　　路由算法在路由协议中起着至关重要的作用，无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点，其中，LEACH算法是比较具有代表性的层次型路由算法。

　　本文在LEACH 算法的基础上，介绍一种改进的路由算法，改进算法的成簇方式相对固定，减少了构造簇的能量消耗。簇形成之后，在簇头间构造生成树，簇间通过多跳方式通信，降低了簇头节点之间长距离通信的能耗。

　　2 LEACH 算法

　　2. 1 LEACH 算法描述

　　LEACH （Low2Energy Adaptive ClusteringHierarchy）算法是由MIT 的Heinzelman 等人提出的一种低功耗自适应分簇算法。其基本思想是以循环的方式随机选择簇头节点，将整个网络的能量负载均匀分配到网络中的每个传感器节点，从而达到降低网络能耗，提高网络生存周期的目的。

　　LEACH 在运行过程中不断地循环执行簇的重构。算法操作使用了“轮”的概念，每一轮由初始化和稳定的工作两个阶段组成。在初始化阶段，每个节点产生一个0～1之间的随机数，如果某个节点产生的随机数小于所设的阈值T（n），则该节点发布自己是簇头的消息，T（n）的计算公式设为：

　　其中，p是簇头占所有节点的百分比，即节点当选簇头的概率；r表示目前进行的轮数；G代表近1/p轮中还没有当选过簇头的节点集合。

　　非簇头节点根据接收信号的强弱来选择加入到哪个簇，并通知相应的簇头。在稳定阶段，簇内的节点通过TDMA 方式与簇头进行通信，簇头节点接收簇内其它节点发送的数据，并将这些数据进行融合，然后发送给基站。

　　2. 2 LEACH算法的不足及其改进算法

　　在LEACH算法中，每一轮循环都要重新构造簇，而构造簇的能量开销比较大。其次，远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量，造成网络分割。另外，LEACH算法没有考虑簇头节点当前的能量状况，如果能量很低的节点当选为簇头节点，那么将会加速该节点的死亡，影响整个网络的生命周期。

　　以LEACH算法的思想为基础，针对LEACH存在的不足，研究人员提出了很多的改进算法，例如LEACH2C（LEACH2Cent ralized）， LEACH2EA（Energy Average）等算法。LEACH2C算法是由基站基于整个网络信息集中挑选簇头，每个节点把自身地理位置和当前能量给基站，基站根据所有节点的信息计算出平均能量，低于平均能量的节点不能成为候选簇头，基站根据所有成员节点到簇头的距离平方和的原则，从剩余候选节点中选出合适数量和地理位置的簇头集合，由基站将簇头集合以及簇的结构广播出去。

　　基于LEACH2C的思想，针对LEACH 的不足，提出了可有效解决网络能耗不均衡问题，延长网络生命周期的LEACH2EA（Energy Average ） 算法。

　　LEACH2EA算法的簇头选择综合考虑了节点的当前能量和每轮结束后的节点平均能量，比较适用于长时间运行且规模较大的网络。

　　3 改进的算法

　　3. 1 改进算法的基本思想

　　本文的改进算法也按轮的机制运行，但是与LEACH不同的是，改进后的算法不必每一轮都重新构建簇。

　　改进算法运行到第N轮，当N为奇数时，新算法采用与LEACH2EA相同的机制选择簇头，这样产生的簇头在新算法中称为活动簇头，活动簇头选定后，该活动簇头发布自己是簇头的消息，非簇头节点根据接收信号的强弱来选择加入哪个簇，并通知相应的活动簇头，完成簇的建立。簇建立之后，簇内节点通过单跳通信方式直接向其簇头节点传送数据。当N为偶数时，原来的簇固定不变。如果此时活动簇头节点能量低于某一个门限值时，则在原簇内重新选择簇头节点，以簇内剩余能量多的节点为新的簇头节点，这样产生的簇头在新算法中称为固定簇头。为降低簇头（包括活动簇头和固定簇头）节点的通信代价，在簇头间构造树形路由，簇头间以多跳方式通信。

　　3. 2 改进算法的描述

　　3. 2. 1 簇的建立和簇内通信

　　改进算法第N轮的开始，首先判断N是奇数还是偶数。当N是奇数时，就需要重新构建簇，此时，采用与LEACH2EA相同的簇头选择机制。活动簇头选择过程如下：每个节点产生一个0～1之间的随机数，如果这个数小于阈值T（n），则该节点向周围节点广播它是簇头的消息，参照LEACH2EA 的阈值计算公式T（n）可表示为：

　　其中，p是簇头占所有节点的百分比，即节点当选簇头的概率；r代表目前进行的轮数；G表示近1/p轮中还未当选过簇头的节点集合； En2current表示节点的当前能量；Eaver表示每一轮结束后节点的平均能量。

　　节点当选为活动簇头后，该活动簇头广播自己是簇头的消息，非簇头节点根据接收信号的强弱来选择加入哪个簇，并通知相应的活动簇头，完成簇的建立。活动簇头接收到所有的加入信息后，就产生一个TDMA定时信息表，给簇中每个非簇头成员节点分配传送数据的时间片，成员节点只能在其特定的时间片内与簇头节点进行通信。算法执行首轮时，簇的建立与此种情况相同。

　　当N是偶数时，则原来的簇固定不变。如果活动簇头节点能量低于某一个规定的门限值，则在原簇内重新选择簇头节点，以簇内剩余能量多的节点为簇头节点，这样产生的簇头称为固定簇头。

　　固定簇头与簇内成员的通信方式和活动簇头一样。

　　当节点持续采集监测数据时，在其相应时间片，使用能量传给簇头节点。节点不发送数据时，关闭节点以节约能量。簇头节点必须保持其接收器一直打开，以接收簇内不同节点的数据，然后进行数据融合。

　　3. 2. 2 簇头间树形路由的构建与簇间通信

　　假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。如果用连通网的顶点来表示城市，边表示两城市之间的线路，赋予边的权值代表相应的代价，需要考虑如何在节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网，要选择一棵生成树，使总的代价少，这就是构造连通网的代价生成树（Minimum Cost Spanning Tree） 问题（简称为生成树问题）。考虑将此问题中的城市与无线传感器网络中的簇头节点相对应，可以在簇头节点之间构造生成树，降低簇头节点间的通信代价。

　　prim算法构造生成树的过程：假设N =（V ,{ E}）为连通网，V表示网中顶点的集合，E表示边的集合，U是V的一非空子集，TE为生成树中边的集合。首先，从集合V中取一个顶点V0加入集合U中，这时U={ V 0 }, 集合TE={ },接着重复执行以下操作：从V0出发，在集合V中寻找与U中顶点相邻顶点中权值的边的另一顶点V1,然后将V1并入U中，并将该边加入集合TE中，直到U=V为止。这时TE中有n-1条边，T =（U ,TE）为N的生成树。

　　利用prim算法构造生成树的原理在簇头间构造树形路由，改进过程如下：

　　1） 选出的簇头节点将自己的剩余能量和到基站的距离加入到广播数据包中进行广播，根据其剩余能量和到基站的距离关系参数Ped ,选取Ped 的簇头节点作为树根节点。Ped 的定义公式：

　　其中，i是传感器节点编号，Ey（i）是节点i 的剩余能量，De（i）是节点i 到基站的距离。

　　2） 利用prim算法构造生成树原理，树根节点选择下一跳中有效簇头节点作为其子节点，该子节点以树根节点为父节点，同时向下一跳簇头节点继续搜索。若该子节点搜索成功，则继续执行路由算法，若没有搜索到有效簇头节点，则返回该根节点继续搜索。

　　3） 重复2），直到所有节点加入到树中，构成树形网络路由。

　　簇头节点通过树网络路由，以多跳方式通信，作为树根节点的簇头将数据传给基站。簇头间的树形路由如图1所示。

　　4 算法的仿真分析

　　采用Matlab仿真工具，对LEACH算法、LEACH2EA算法和改进的算法进行仿真比较。仿真场景假设有100个传感器节点组成，节点随机分布在一个介于（x=0 ,y=0） 与（x=100,y=100）的区域内，每个节点都拥有相同的初始能量E0=0.5J,仿真模型参照文献。

　　如图2 所示，前1000 轮中，LEACH和LEACH2EA 算法的节点存活数比较接近，改进算法相对来说比前两种算法更优越。

　　网络生命周期是衡量网络质量的一个重要标志，图3 显示了当节点死亡率为1%,50%,100%时所经过的轮数。从图中可以看出新算法的通信轮数高于LEACH和LEACH2EA算法，表明改进之后得到的新算法降低了能耗，延长了网络的生存时间。

　　5 结语

　　LEACH算法是一种经典的层次型路由算法，它利用簇头轮换机制将能量消耗较均匀地分摊到了整个网络。在LEACH 的基础上提出了一种改进的路由算法，改进算法的簇相对固定，在一定程度上避免了频繁分簇造成的能量浪费，降低了整个网络的能耗。簇头节点接收簇中其它节点发送的数据，并将这些数据进行融合，通过树形路由，以多跳方式进行通信，降低了簇头节点的通信代价。仿真结果表明，该算法进一步降低了网络中的能量消耗，有效延长了网络生命周期。

　　本文在基于网络数据传输可以进行数据融合的前提下，对LEACH 算法进行了改进，但改进算法没有考虑具体的数据融合方法。下一步的工作，将在本文算法的基础上研究如何提高数据融合与传输的效率和可靠性。