一种基于LEACH的改进型无线传感器网络路由算法

摘要：路由算法是无线传感器网络研究的核心技术之一。在LEACH算法的基础上，提出了一种基于距离和能量考虑选择第二层簇头的两层LEACH算法DE―LEACH，有效避免了低能量且离基站较远的节点与基站直接通信，提高了网络生存时间和数据采集能力。利用事件驱动的方法，减少了发送数据量，进一步延长了网络生存期。
关键词：路由算法；第二层簇头选择；网络生存时间；数据采集能力；数据融合；事件驱动

0 引 言
微电子技术、计算机技术和无线通信等技术的不断发展，使设计低功耗多功能的无线传感器成为可能。无线传感器网络在监测区域内部署大量的廉价低功耗传感器节点，其目的是协作的感知、采集和处理网络覆盖区域中感知对象的信息，并以无线通信的方式通过多跳自组织网络发送给远程基站(BS)。无线传感器网络是未来全球的三大高科技产业之一，具有广阔的应用前景，在军事国防、灾害预警、环境监测、医疗等许多领域都有巨大的应用价值。
作为无线传感器网络核心技术之一，路由协议的性能在很大程度上决定了网络的整体性能，因此，路由算法始终是无线传感器网络研究的热点。根据各个节点在网络中功能的异同，可将路由算法分为平面型和层次型路由。由于平面型路由可扩展性差，且维护动态变化的路由需要大量的控制信息，若部署在人类到达比较困难的地区，维护相对困难。层次型路由算法克服了以上不足，可扩充性好，网络中控制信息相对较少，得到了广泛的应用。LEACH是第一个基于多簇结构的层次型路由协议，其成簇思想在其后很多协议中都被用到，如TEEN等。
在LEACH算法中，各节点根据簇头概率p自主决定在该轮是否充当簇头，一旦成为簇头便通过广播告知整个网络，由于簇头选择是完全自主和随机的，不需要节点间通信协调，因此LEACH算法具有节约能量、实现简单、可扩展性好等特点，便于部署于人们难以到达区域。但是，随机簇头选择不能保证每轮簇头节点的数目和分布，易造成网络内节点能量损耗不均，节点生存期散布较大，到网络生存期后期会形成监控盲点，影响了网络的整体性能。
本文在LEACH的基础上提出了一种两层簇头算法DE―LEACH(Distance―Energy LEACH)，第一层簇头选举机制与LEACH相同，之后从已选出的簇头中根据剩余能量大小和距离基站(BS)的远近折衷考虑选出第二层簇头。第一层簇头采集到的数据经过融合处理后发送到第二层簇头，再由第二层簇头完成二次融合和将监测数据转发到基站的工作。由于第二层簇头选举机制综合考虑了节点剩余能量和其到基站的距离，因此避免了剩余能量较少且距基站较远的第一层簇头与基站间的直接通信。仿真结果表明，DE―LEACH延长了网络首节点死亡时间，缩短了首节点死亡到末节点死亡的时间间隔，同时网络总的数据采集能力得到明显提高。

1 LEACH算法简介
LEACH算法引入了轮的概念，每轮簇头节点进行轮换，以达到分散各节点能量消耗的目的。每一轮包括簇建立和稳定运行两个阶段。为减少管理消耗，稳定运行阶段时间要长于簇建立阶段。
在簇建立阶段，每个节点自主决定是否在本轮充当簇头，具体的选举办法是：由各节点自主生成0～1之间的随机数，若此随机数小于某门限T(n)，则此节点在本轮充当簇头。这种簇头产生的随机性保证了簇头与基站之间较高的通信代价在网内各节点之间得到分摊。
门限T(n)定义为：

其中：p是网络中簇头节点占总节点数的百分比；r是已完成轮数；G是在前1／p轮中没有充当过簇头节点的节点集合。举例来说，第1轮(r=0)，每个节点成为簇头的概率都是p，第1轮的簇头在包括此轮之后的1／p轮中都不再充当簇头节点(即第1～20轮)。此后，由于能够充当簇头节点的节点数目变少了，因此每个节点成为簇头的概率就必须增加以保证每轮簇头数。1／p一1轮过后，没当过簇头的节点充当簇头的概率都是1，都能够成为簇头节点。1／p轮后，所有节点又都可以自主随机决定是否充当簇头节点。在文献中，作者论证了最优簇头节点百分比为p=5％。
一旦簇头选定后，簇头节点会利用CSMA MAC协议对全网所有节点发送广播数据包，其中包含该节点成为簇头的信息。根据网络的对称性原则，其他节点选择接收到信号最强的簇头加入，至此簇建立阶段完成。
在稳定运行阶段，普通节点利用CSMA MAC协议向其簇头发送加入数据包。簇头节点收到加入数据包后，会产生一个TDMA时刻表，为簇内所有节点分配发送时隙，并将此时刻表向各成员广播。此后，簇头节点即开始接收各成员采集到的数据，并将其融合后发送到基站。簇头节点在此阶段保持接收机始终处于开机状态以便接收数据，而普通节点只有在自己发送时打开发射机，其余时刻关闭发射机以节约能量。
相比于平面路由算法，LEACH算法明显减少了能量消耗，并且将能量耗散分摊到整个网络，有效延长了网络生存时间。在文献中，作者的仿真表明LEACH比平面型的Direct communication协议网络生存时间提高了约6倍，比层次型固定簇头协议StaticClusters网络生存时间提高了约10倍。
然而，完全自主随机的簇头选择不能保证每轮簇头节点的数目和分布，存在距离基站较远且能量较少的节点担当簇头的可能性，造成网络内节点能量损耗不均，节点的生存期散布较大，到网络生存期后期会形成监控盲点，影响了网络的整体性能。为了改善这种情况，本文提出了基于距离和能量选择第二层簇头的两层LEACH算法DE―LEACH。