总第246期2010年第4期计算机与数字工程Computer&Digital EngineeringVol.38No.449基于L EACH的无线传感器网络分簇路由算法3白凤娥 牟汇慧 姜晓荣(太原理工大学计算机与软件学院 太原 030024)摘 要 路由协议是无线传感器网络的重要组成部分之一,而路由算法在路由协议中起着至关重要的作用。
文章在L EACH算法基础上,提出一种改进的路由算法,改进后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。
利用图论中的prim算法,选择每轮中P ed最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。
仿真结果表明,与L EACH算法相比,改进算法降低了能耗,有效延长了网络生存周期。
关键词 无线传感器网络;L EACH算法;分簇;生命周期中图分类号 TP393L EACH2Based Clustering Routing Algorithm for Wireless Sensor NetworksBai Fe ngπe M ou Huihui J ia ng Xiaorong(College of Computer and Software,Taiyuan University of Technology,Taiyuan 030024)Abs t rac t Routing protocol is an important part of wireless sensor network and the routing algorithm plays a crucial role in the routing protocol.Based on L EACH algorithm,this paper presents a novel clustering algorithm in which clusters are relatively fixed and the nodes re2organize themselves into new clusters every other round.It utilizes the Prim algorithm in the graph theory to form tree routing among cluster2head nodes,and selects the cluster2head with the largest P ed as the root node.The cluster heads send data to the root node in a multi2hop manner and the root node then sends the gathered data by the whole network to the base station.Simulation results show that compared with L EACH,the improved algorithm can re2 duce the energy consumption and prolong the lifetime of the network.Ke y Words wireless sensor network,L EACH algorithm,clustering,lifetimeClass Nu m ber TP3931 引言无线传感器网络(Wireless Sensor Network,简称WSN)是监视远程环境的有力工具之一,它的基本功能是收集并返回传感器节点所在监测区域的信息。
由于工作环境和自身构造的限制,传感器节点一般是电池供电,并且节点的更换和充电也较难实现。
因此,降低节点能耗,延长网络生命周期是无线传感器网络传输机制的一个主要研究目标[1]。
网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器网络核心技术之一的路由协议一直是研究的热点。
路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。
层次路由算法是无线传感器网络路由算法的研究重点,其中,L EAC H 算法[2～3]是比较具有代表性的层次型路由算法。
本文在L EAC H算法的基础上,介绍一种改进的路由算法,改进算法的成簇方式相对固定,减少了构造簇的能量消耗。
簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。
3收稿日期:2009年11月2日,修回日期:2009年12月5日作者简介:白凤娥,女,教授,硕士生导师,研究方向:计算机控制与嵌入式系统,无线传感器网络。
牟汇慧,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。
姜晓荣,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。
50 白凤娥等:基于L EACH的无线传感器网络分簇路由算法第38卷2 L EAC H算法2.1 L EAC H算法描述L EACH(Low2Energy Adaptive ClusteringHierarchy)算法是由M IT的Heinzelman等人提出的一种低功耗自适应分簇算法。
其基本思想是以循环的方式随机选择簇头节点,将整个网络的能量负载均匀分配到网络中的每个传感器节点,从而达到降低网络能耗,提高网络生存周期的目的。
L EACH在运行过程中不断地循环执行簇的重构。
算法操作使用了“轮”的概念,每一轮由初始化和稳定的工作两个阶段组成。
在初始化阶段,每个节点产生一个0～1之间的随机数,如果某个节点产生的随机数小于所设的阈值T(n),则该节点发布自己是簇头的消息,T(n)的计算公式设为:T(n)=p1-p3(r mod(1/p)),n∈G0,其它(1)其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r表示目前进行的轮数;G代表最近1/p轮中还没有当选过簇头的节点集合。
非簇头节点根据接收信号的强弱来选择加入到哪个簇,并通知相应的簇头。
在稳定阶段,簇内的节点通过TDMA方式与簇头进行通信,簇头节点接收簇内其它节点发送的数据,并将这些数据进行融合,然后发送给基站。
2.2 L EAC H算法的不足及其改进算法在L EACH算法中,每一轮循环都要重新构造簇,而构造簇的能量开销比较大。
其次,远离汇聚节点的簇头节点可能会由于长距离发送数据而过早耗尽自身能量,造成网络分割。
另外,L EAC H 算法没有考虑簇头节点当前的能量状况,如果能量很低的节点当选为簇头节点,那么将会加速该节点的死亡,影响整个网络的生命周期。
以L EACH算法的思想为基础,针对L EAC H 存在的不足,研究人员提出了很多的改进算法,例如L EACH2C(L EAC H2Cent ralized)[4],L EAC H2 EA(Energy Average)[5]等算法。
L EAC H2C算法是由基站基于整个网络信息集中挑选簇头,每个节点把自身地理位置和当前能量报告给基站,基站根据所有节点的报告信息计算出平均能量,低于平均能量的节点不能成为候选簇头,基站根据所有成员节点到簇头的距离平方和最小的原则,从剩余候选节点中选出合适数量和最优地理位置的簇头集合,最后由基站将簇头集合以及簇的结构广播出去。
基于L EAC H2C的思想,针对L EACH的不足,提出了可有效解决网络能耗不均衡问题,延长网络生命周期的L EAC H2EA(Energy Average)算法。
L EACH2EA算法的簇头选择综合考虑了节点的当前能量和每轮结束后的节点平均能量,比较适用于长时间运行且规模较大的网络。
3 改进的算法3.1 改进算法的基本思想本文的改进算法也按轮的机制运行,但是与L EACH不同的是,改进后的算法不必每一轮都重新构建簇。
改进算法运行到第N轮,当N为奇数时,新算法采用与L EAC H2EA相同的机制选择簇头,这样产生的簇头在新算法中称为活动簇头,活动簇头选定后,该活动簇头发布自己是簇头的消息,非簇头节点根据接收信号的强弱来选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。
簇建立之后,簇内节点通过单跳通信方式直接向其簇头节点传送数据。
当N为偶数时,原来的簇固定不变。
如果此时活动簇头节点能量低于某一个门限值时,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为新的簇头节点,这样产生的簇头在新算法中称为固定簇头。
为降低簇头(包括活动簇头和固定簇头)节点的通信代价,在簇头间构造树形路由,簇头间以多跳方式通信。
3.2 改进算法的描述3.2.1 簇的建立和簇内通信改进算法第N轮的开始,首先判断N是奇数还是偶数。
当N是奇数时,就需要重新构建簇,此时,采用与L EACH2EA相同的簇头选择机制。
活动簇头选择过程如下:每个节点产生一个0～1之间的随机数,如果这个数小于阈值T(n),则该节点向周围节点广播它是簇头的消息,参照L EAC H2 EA的阈值计算公式[6]T(n)可表示为:T(n)=p1-p3(r mod(1/p))3E n2currentE aver,n∈G0,其它(2)其中,p是簇头占所有节点的百分比,即节点当选簇头的概率;r代表目前进行的轮数;G表示最近1/p轮中还未当选过簇头的节点集合;E n2current表示节点的当前能量;E aver表示每一轮结束后节点的平均能量。
节点当选为活动簇头后,该活动簇头广播自己是簇头的消息,非簇头节点根据接收信号的强弱来2010年第4期计算机与数字工程51选择加入哪个簇,并通知相应的活动簇头,完成簇的建立。
活动簇头接收到所有的加入信息后,就产生一个TDMA定时信息表,给簇中每个非簇头成员节点分配传送数据的时间片,成员节点只能在其特定的时间片内与簇头节点进行通信。
算法执行首轮时,簇的建立与此种情况相同。
当N是偶数时,则原来的簇固定不变。
如果活动簇头节点能量低于某一个规定的门限值,则在原簇内重新选择簇头节点,以簇内剩余能量最多的节点为簇头节点,这样产生的簇头称为固定簇头。
固定簇头与簇内成员的通信方式和活动簇头一样。
当节点持续采集监测数据时,在其相应时间片,使用最小能量传给簇头节点。
节点不发送数据时,关闭节点以节约能量。
簇头节点必须保持其接收器一直打开,以接收簇内不同节点的数据,然后进行数据融合。
3.2.2 簇头间树形路由的构建与簇间通信假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。
如果用连通网的顶点来表示城市,边表示两城市之间的线路,赋予边的权值代表相应的代价,需要考虑如何在最节省经费的前提下建立这个通信网。