1、河南师范大学本科毕业论文设计无线传感器网络路由协议LEACH的研究与改良摘要:无线传感器网络由许多具有低功率无线收发装置的传感器节点成,能够有效地感知、采集和处理网络覆盖区域中的相关信息,并发送给远处的基站进一步处理。由于传感器节点能量有限,路由协议必须尽可能地减少能量消耗,延长网络生命周期。在LEACH算法根底上,提出一种改良的路由算法,改良后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。利用图论中的prim算法,选择每轮中Ped最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。仿真结果说明,与
2、LEACH算法相比,改良算法降低了能耗,有效延长了网络生存周期。关键词:无线传感器网络; LEACH算法; 分簇;生命周期;能量消耗Abstract: W ireless sensor networks consisting of a large number of small sensorswith low-power transceiver can be an effective tool for apperceiving, collecting and computing data in a variety of environment.The collected data mustbe
3、 transmitted to the base station for further processing. Based on LEACH algorithm, this paper presents a novel clustering algorithm in which cluster are relatively fixed and the nodes re-organize themselves into new clusters every other round. It utilizes the Prim algorithm in the graph theory to fo
4、rm tree routing among cluster-head nodes, and selects the cluster-head with the largestPedas the root node. The cluster heads send data to the root node in a multi-hop manner and the root node then sends the gathered data by the whole network to the base station. Simulation results show that compare
5、d with LEACH, the improved algorithm can reduce the energy consumption and prolong the lifetime of the network.Key Words：wireless sensor network, LEACH algorithm, clustering, lifetime, energy consume1、前言无线传感器网络被认为是在一定空间范围内密集分布的由大量体积小、廉价、电池供电的通信器件构成的自组织系统由于无线传感器网络大都需要在无人看管、不更换电池或者几乎不可能更换电池的条件下长时间的工作，
6、如何提高能量的有效利用率并延长网络寿命便成了一个重要问题网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器网络核心技术之一的路由协议一直是研究的热点。路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点,其中,LEACH算法是比拟具有代表性的层次型路由算法。本文在LEACH算法的根底上,介绍一种改良的路由算法,改良算法的成簇方式相对固定,减少了构造簇的能量消耗。簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。2
7、、LEACH 算法2.1算法描述： LEACH协议的操作是按轮进行的,每一轮包含簇建立和稳定运行2个阶段,在簇建立阶段,自适应分簇结构形成,在稳定运行阶段进行数据传输。在簇建立阶段,选取一定数目的节点充当簇头节点。每个节点随机分配一个在0到1之间的数字,成为其标志值。如果节点的标志值小于门限值T(n)的话,该节点就充当本轮的簇头节点。门限T(n)定义如下：T(n)=p/(1-px(rmod(1/p)nGT(n)=0其他式中p为网络中簇头节点所占总节点数目的百分比; r为当前的轮数;G为一个集合,集合中的节点是前1/p轮中没有充当过簇头节点的节点。使用这个门限,每个节点会在1/p轮操作内充当一次
8、簇头节点。等过了1/p轮以后,所有的节点都充当过簇头节点,从而又可以重新充当簇头节点。节点被选为簇头后,就向外发送播送信息;其他节点就根据收到消息的信号强弱,选取信号最强的发送源节点作为自己的簇头节点,参加那个簇,并向簇头发送参加的请求。簇头收到请求后为成员节点设定一个TDMA时隙表。此后的簇稳定阶段,节点在属于自己的时隙里将采集的数据发送给簇头节点,簇头节点将接收到的成员节点的数据进行融合,然后,直接发送给基站。2.2LEACH算法的缺乏及其改良算法在LEACH算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比拟大。其次,远离会聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量,
9、造成网络分割。另外,LEACH算法没有考虑簇头节点当前的能量状况,如果能量很低的节点中选为簇头节点,那么将会加速该节点的死亡,影响整个网络的生命周期。3、改良的算3.1改良算法的根本思想本文的改良算法也按轮的机制运行,但是与LEACH不同的是,改良后的算法不必每一轮都重新构建簇。改良算法运行到第N轮,当N为奇数时,新算法采用与LEACH-EA相同的机制选择簇头,这样产生的簇头在新算法中称为活动簇头,活动簇头选定后,该活动簇头发布自己是簇头的消息,非簇头节点根据接收信号的强弱来选择参加哪个簇,并通知相应的活动簇头,完成簇的建立。簇建立之后,簇内节点通过单跳通信方式直接向其簇头节点传送数据。当N为
10、偶数时,原来的簇固定不变。如果此时活动簇头节点能量低于某一个门限值时,那么在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为新的簇头节点,这样产生的簇头在新算法中称为固定簇头。为降低簇头(包括活动簇头和固定簇头)节点的通信代价,在簇头间构造树形路由,簇头间以多跳方式通信。3.2改良算法的描述1簇的建立和簇内通信改良算法第N轮的开始,首先判断N是奇数还是偶数。当N是奇数时,就需要重新构建簇,此时,采用与LEACH-EA相同的簇头选择机制。活动簇头选择过程如下:每个节点产生一个01之间的随机数,如果这个数小于阈值T(n),那么该节向周围节点播送它是簇头的消息,参照LEACH-EA的阈值计算公式T
11、(n)可表示为:T(n)=p1-px(rmod(1/p)En-currentEaver, nGT(n)=0,其它其中,p是簇头占所有节点的百分比,即节点中选簇头的概率;r代表目前进行的轮数;G表示最近1/p轮中还未中选过簇头的节点集合;En-current表示节点的当前能量;Eaver表示每一轮结束后节点的平均能量。节点中选为活动簇头后,该活动簇头播送自己是簇头的消息,非簇头节点根据接收信号的强弱。选择参加哪个簇,并通知相应的活动簇头,完成簇的建立。活动簇头接收到所有的参加信息后,就产生一个TDMA定时信息表,给簇中每个非簇头成员节点分配传送数据的时间片,成员节点只能在其特定的时间片内与簇头节
12、点进行通信。算法执行首轮时,簇的建立与此种情况相同。当N是偶数时,那么原来的簇固定不变。如果活动簇头节点能量低于某一个规定的门限值,那么在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为簇头节点,这样产生的簇头称为固定簇头。固定簇头与簇内成员的通信方式和活动簇头一样。当节点持续采集监测数据时,在其相应时间片,使用最小能量传给簇头节点。节点不发送数据时,关闭节点以节约能量。簇头节点必须保持其接收器一直翻开,以接收簇内不同节点的数据,然后进行数据融合。3.2.2簇头间树形路由的构建与簇间通信假设要在n个城市之间建立通信联络网,那么连通n个城市只需要n-1条线路。如果用连通网的顶点来表示城市,边表
13、示两城市之间的线路,赋予边的权值代表相应的代价,需要考虑如何在最节省经费的前提下建立这个通信网。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网,要选择一棵生成树,使总的代价最少,这就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree)问题7(简称为最小生成树问题)。考虑将此问题中的城市与无线传感器网络中的簇头节点相对应,可以在簇头节点之间构造最小生成树,降低簇头节点间的通信代价。prim算法构造最小生成树的过程:假设N=(V,E)为连通网,V表示网中顶点的集合,E表示边的集合,U是V的一非空子集,TE为最小生成树中边的集合。首先,从
14、集合V中取一个顶点V0参加集合U中,这时U=V0,集合TE=,接着重复执行以下操作:从V0出发,在集合V中寻找与U中顶点相邻顶点中权值最小的边的另一顶点V1,然后将V1并入U中,并将该边参加集合TE中,直到U=V为止。这时TE中有n-1条边,T=(U,TE)为N的最小生成树。本文参照文献5,利用prim算法构造最小生成树的原理在簇头间构造树形路由,在文献5的根底上进行了改良,过程如下:1)选出的簇头节点将自己的剩余能量和到基站的距离参加到播送数据包中进行播送,根据其剩余能量和到基站的距离关系参数Ped,选取Ped最大的簇头节点作为树根节点。Ped的定义公式:Ped(i)=Ey2(i)De(i)
15、(3)其中,i是传感器节点编号,Ey(i)是节点i的剩余能量,De(i)是节点i到基站的距离。2)利用prim算法构造最小生成树原理,树根节点选择下一跳中最小有效簇头节点作为其子节点,该子节点以树根节点为父节点,同时向下一跳簇头节点继续搜索。假设该子节点搜索成功,那么继续执行路由算法,假设没有搜索到最小有效簇头节点,那么返回该根节点继续搜索。3)重复2),直到所有节点参加到树中,构成树形网络路由。簇头节点通过树网络路由,以多跳方式通信,最后作为树根节点的簇头将数据传给基站。簇头间的树形路由如图1所示。4、算法的仿真分析采用Matlab仿真工具,对LEACH算法、LEACH-EA算法和改良的算法
16、进行仿真比拟。仿真场景假设有100个传感器节点组成,节点随机分布在一个介于(x=0,y=0)与(x=100,y=100)的区域内,每个节点都拥有相同的初始能量E0=0.5J,仿真模型参照文献6。如图2所示,前1000轮中, LEACH和LEACH-EA算法的节点存活数比拟接近,改良算法相对来说比前两种算法更优越。网络生命周期是衡量网络质量的一个重要标志,图3显示了当节点死亡率为1%,50%,100%时所经过的轮数。从图中可以看出新算法的通信轮数高于LEACH和LEACH-EA算法,说明改良之后得到的新算法降低了能耗,延长了网络的生存时间。5、参考文献1Tao Yang,Zheng Yaling.The combination of the optimal number of cluster-heads and energy adaptive cluster-h
