一种基于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。

2 基于距离能量选择的两层LEACH算法DE—LEACH
    DE—LEACH算法与LEACH算法一样，分为簇建立阶段与稳定运行阶段。
    在簇建立阶段，首先，各节点仍然利用自身产生的随机数自主决定是否成为簇头并通知网络中所有节点，在此不再赘述。不同之处在于，选出的簇头节点将自己的剩余能量和到基站的距离加入到广播数据包中进行广播。之后，在已选出的第一层簇头中根据其剩余能量和到基站的距离关系参数Th选出第二层簇头。
    Th定义为：

   
其中i是网络中节点编号，En(i)是i节点剩余能量，Dist(i)是i节点到基站的距离。
    具体的选举第二层簇头的策略为：簇头j将自己的Th(i)值与接收、计算出到的其他簇头Th值进行比较，若自己最大，则成为第二层簇头；若比较中发现簇头i节点的Th(i)值最大，则认为i是第二层簇头。这里需要注意的是：
    (1)第二层簇头同时也完成第一层簇头的广播、分配时隙、采集数据和融合的工作；
    (2)各个簇头节点在计算Th值并比较过后，已经能够确认哪个第一层簇头节点同时承担第二层簇头节点职能，因此第二层簇头节点不需要再就自己身份进行广播；又由于各簇头节点已经收到其他簇头节点编号，可按编号顺序进行数据传递，因此第二层簇头节点不需要为第一层簇头节点分配时隙而进行广播；这样就省去了广播开销；
    (3)各个普通节点无需知道谁是第二层簇头，他们只与第一层簇头通信，而第二层簇头同时也承担第一层簇头的功能。
    在稳定运行阶段，普通节点与第一层簇头通信方式与LEACH相同。但数据采集、融合工作完成之后不是将数据包直接发送到基站，而是依据簇头节点编号顺序分时隙由第一层簇头发送到第二层簇头节点。再由第二层簇头节点进行二次融合后，发送至基站。
    LEACH算法假设基站离监控区域较远，若第一层簇头节点均与基站直接通信，则通信能量消耗较大，且易造成网络中各节点剩余能量差距较大的情况，使首末节点死亡时间间隔较长，产生监控盲点。而DE—LEACH算法能够有效推迟首节点死亡时间，缩小首末节点死亡时间间隔，使监控盲点出现时间明显缩短。这样，在所有节点集中死亡后再进行抛撒，无疑在经济上和控制上都将更加高效。
    另外，考虑到传感器节点所采集的数据在较短时间内具有相关性，可以采用事件驱动的方式进一步延长网络生存期。下面将对DE—LEACH与LEACH进行性能上的比较，并仿真分析了加人事件驱动因素后DE—LEACH的生存期改善程度。

3 仿真分析
3．1 DE—LEACH与LEACH性能比较
    利用Matlab工具对LEACH算法和DE—LEACH算法进行仿真比较，主要比较：
    (1)存活节点数随轮次变化曲线；
    (2)数据采集总比特数(二次融合前)随轮次变化曲线。
    仿真中，假设无线传感器网络由100个相同的无线传感器节点组成，随机抛撒在100 m×100 m的区域内，远程基站位于坐标点(x=0，y=一100)。每个节点初始能量为O．5 J，发送和接收电路损耗为Elec=50 nJ／b，数据融合消耗为Eda=5 nJ／b。放大系数为Efs=10 pJ／b／m2(d<d0)，Emp=O．001 3 pJ／b／m4(d>d0)，其中数据包长度为2 000 b，广播包长度
为200 b，总带宽为1 MHz。为简化仿真复杂度，监测区域内通信按自由空间模型取Efs=10 pJ／b／m2，而簇头节点与基站通信由于距离较远(>100 m)，按多径传播模型取Emp=O.001 3 pJ／b／m4。
    根据第二层簇头对收到的第一层簇头数据进行二次融合的融合率不同，这里分完全不融合、50％融合、完全融合分别进行了仿真比较。
    完全不融合，即将第一层簇头发送来的数据包不加处理地组成一个长数据包发送到基站，这时第二层簇头相当于只是完成了数据接收和转发的功能。仿真发现，即使在完全不融合的情况下，DE—LEACH的首节点死亡时间也要比LEACH晚30％，50％节点死亡时间晚15％(如图1)。数据采集总比特数DE—LEACH比LEACH高出12％(如图2)。虽然末节点死亡时间早于LEACH，但网络中存活期非常集中，网络出现大面积监控盲区的时间短，若要保证数据采集的持续性和完整性，对监控区域重新部署节点将比LEACH算法更经济有效。

    50％融合，即将第一层簇头发送来的数据包压缩一半之后发送到基站。各个第一层簇头发送的数据包中仍然含有第一层簇头数据包的包头等基站不需要的冗余信息，可以进行进一步融合。仿真发现，进行50％融合后，DE—LEACH的首节点死亡时间比LEACH晚40％，50％节点死亡时间晚25％(如图3)。数据采集总比特数DE—LEACH比LEACH高出22％(如图4)。

    完全融合，即将第一层簇头发送来的数据包压缩成一个2 000 b的数据包发送到基站。由于融合率较大，不仅要用到数据级融合，特征级融合，还要用到决策级融合。即最后传输到基站的已不是简单的数据，而是第二层簇头节点对采集到的数据进行综合分析后所得到的结果。仿真发现，完全融合后，DE—LEACH的首节点死亡时间比LEACH晚40％，50％节点死亡时间晚30％(如图5)。数据采集总比特数DE—LEACH比LEACH高出28％(如图6)。
    由仿真比较可见，综合考虑了簇头节点到基站的距离以及剩余能量并据此选出第二层簇头的DE—LEACH算法，性能较LEACH有明显的改善。
    DE—LEAcH算法的优点：延长了首节点死亡时间，曲线斜率明显比LEACH大，缩短了首末节点死亡时间间隔，相比于LEACH，节点死亡时间更加集中，监控盲点出现时间短，重新部署传感器节点更加经济高效；数据采集总量明显提高。DE—LEACH算法的不足：由于在原来LEACH算法的簇头与基站之间又增加了一跳路由，网络延迟有所增加。另外，节点的运算能力要有所提高。就仿真来看，要想得到更长的网络生存时间和更高的数据采集量，就要加大数据融合率，这对节点的数据融合能力提出了更高的要求。在实际应用中，需要根据应用对性能和成本的要求进行综合考虑。

3．2 事件驱动型DE—LEACH生存期分析
    针对传感器节点所采集的数据(如温度、压力等)在较短时间内的相关性，可设定一个门限值，当相邻两次所采集数据变化超过此门限值时，节点才向簇头发送数据，并保留后一次数据在该节点存储器中；若变化小于门限值，则不进行发送，仍保留前一次数据以防止数据以渐进的方式变化。门限值可设定为前次采集数据的百分比或具体的数值，视具体情况而定。图7的仿真设定门限值为前次采集数据的10％(完全不融合情况)。

    由图7可见加入事件驱动因素后，网络生存期延长约9％，仿真中为方便采集数据用随机数的方式产生，不具有相关性。当实际应用中的数据具有相关性时，生存期延长将更加明显。另外，门限值的大小可根据需要更改，适应性较强。加入事件驱动的缺点：由于需要存储两次采集的数据进行比较，提高了对传感器节点存储能力的要求。

4 结 语
    路由协议在很大程度上决定了网络的整体性能。因此，作为无线传感器网络核心技术之一，路由协议一直是研究的热点。LEACH算法是一种经典的层次型路由协议，它利用簇头轮换机制有效的将能量消耗较均匀地分摊到整个网络。在LEACH算法的基础上提出了一种基于距离和能量选择第二层簇头的两层改进型LEACH算法DE—LEACH，并简要分析了事件驱动对网络生存期的影响。仿真结果表明，该算法进一步平均了网络中的能量消耗，有效延长了网络生存时间，提高了网络的数据采集能力。
    LEACH算法的实现作了一些假设。其中一点是网络中每个节点当选簇头后都进行全网广播，这样的假设在网络覆盖范围较大的情况下损耗将明显加大，因此在大规模应用中多层多跳路由成为必然的选择。这也将是今后工作继续探讨的方向之一。