本文重点分析了经典的分簇路由算法低功耗自适应聚类路由协议LEACH（Low Energy Adaptive Clustering Hierarchy），针对LEACH协议在数据通信阶段中，簇首与SINK节点直接通信的问题，引入蚁群算法，提出了带有诊断机制的多跳路由算法MH-LEACH。结果表明，MH-LEACH算法在能量消耗及节点存活数量上有明显优势。

关键词：LEACH协议;蚁群算法;多跳通信

1.1  问题提出

LEACH算法是典型的分簇路由算法，该算法中，簇首与汇聚节点之间、传感器节点与簇首之间都是采用单跳传输来通信，很显然，簇首节点会消耗过多的能量，特别是通信距离比较远（即大规模网络中）时，甚至会因能量耗尽而失效，出现盲点。另外，对于单跳路径选择模式而言，对带宽的需求更高，而节点在无线传感器网络中是共享带宽的方式，这势必会造成汇聚节点的可用带宽减少，即单位时间内接收的数据量减少，另外，在通信阶段采取单跳的方式虽然简单，但是可能会造成节点死亡而出现盲区，所以，本文结合蚁群算法提出多跳多路径的通信方式MH-LEACH算法。

1.2算法的基本思想

成簇阶段采取与LEACH协议相同的方式，在通信阶段使用蚁群算法，以节点的剩余能量作为信息素。而蚁群算法的特点是信息素浓度越大被选择为路径的概率就越大，从而路径上的节点能量消耗也就越大，以至于出现路由空洞。为避免这一问题的出现，要判断下一跳节点是否有足够的能量进行数据融合和发送，若没有，则直接由当前簇首节点将数据传送至sink节点，然后，在剩余簇首节点中再依据蚁群算法选择一条最优路径。

1.3 算法实现

簇首节点将其成员节点发送过来的数据与本节点收集的数据进行融合后，运行蚁群算法，寻找从当前簇首到Sink节点的最优路径，在沿着该路径对数据进行传输和处理的过程中，引入诊断机制判断当前簇首的下一跳节点是否具有足够的能量对数据进行处理，若有，则继续执行算法；否则，当前簇头直接将数据交给汇聚节点。而当前簇首的下一跳节点则作为下一条最优路径的起始节点，在所有未处理的簇首节点中继续执行蚁群算法寻找最优路径。具体步骤如下：

（1）初始化，按LEACH协议随机选择簇首节点，并且每个簇首节点对其成员发送过来的数据进行融合；

（2）运行蚁群算法，寻找当前簇首节点到达SINK节点的最优路径；

（3）沿最优路径传输数据，并判断下一跳簇首节点的能量是否足够将接收到的数据发送至其下一跳节点，若足够大，则继续执行蚁群算；否则，当前节点直接将数据发送至SINK节点；并且从当前簇首节点的下一跳节点开始，执行步骤（2）；

（4）若所有簇首处理完毕，退出；否则执行步骤（3）。

1.4  LEACH与MH-LEACH比较

为更好地分析改进算法MH-LEACH的优势，将LEACH与MH-LEACH的节点能耗进行比较，两个协议中的簇成员节点的能耗是相同的，但簇首节点的能耗是不相同的：LEACH协议中簇首节点接收该簇内所有成员发送的数据，MH-LEACH中因为采取多跳通信，簇首节点还要接收并处理其他簇首发送的数据，所以在数据处理上能耗要相对大些；簇首节点在发送数据时，LEACH 协议中簇首节点直接与汇聚节点通信，通信距离长，而能耗是随通信距离的增加而变大的，MH-LEACH中簇首节点首先考虑将数据发送至其下一个簇首，如果条件不满足才发送至汇聚节点，与汇聚节点直接通信的簇首要远远少于LEACH协议的情况，所以在相同的网络环境下，LEACH协议的能耗要相对大些。

传感器节点的能量消耗主要在通信模块，传输1比特信息到100米的距离所消耗的能量相当于执行3000条计算指令的能耗，而通信中发送的能耗又高于接收的能耗。依据前面的分析可知，在本文的环境下，MH-LEACH协议的能耗要小于LEACH协议的能耗。

目前，很多研究都将蚁群算法与LEACH协议相结合，提出各种通信阶段多跳传输的优化算法，如文献【2】【3】，但这两个算法有一个共同点，即都是多跳单路径传输。依据蚁群算法的特点，信息素浓度越大，选择为路径的概率就越大，从而路径上的节点能量消耗也就越大，以至于出现路由空洞，所以单跳传输的可靠性不能保证。

评价标准：

无线传感器网络的特点使得节点的能量对整个网络有非常大的影响，一旦节点电池能量耗尽，将导致节点失效，甚至会造成路由空洞，导致整个网络瘫痪，因此如何减少能量消耗和延长网络生命周期是无线传感器网络的关键问题。所以本文考查两个指标：总能耗和节点死亡数。

由于评价角度的不同，生存周期的定义还存在很多争议，主要有这样一些观点：第一个节点死亡的时间；最后一个节点死亡的时间；任意两节点间不能通信的时间等，所以，为了更好地检验改进算法的性能，本文采取间接评价生存周期的方式，即衡量网络中节点总能耗。总能耗越少，网络的工作时间就越长，即生存时间长；反之，生存时间也就越短。

节点的死亡数。节点的死亡往往是由于能量耗尽造成的，但是总能耗并不能反应每个节点的情况。所以，在一定程度上，节点的死亡数（生存数）反映了网络负荷的均衡分配。

因此，本文分析了在相同的初始化条件下，LEACH协议与MH-LEACH协议在能量消耗与网络负荷均衡方面的性能差异。

从仿真结果可以看出，MH-LEACH路由算法在400个回合之前节点剩余能量明显高于LEACH路由算法。这是因为在成簇阶段，MH-LEACH协议采取了化区成簇的方式，簇首节点只需要在本区域内广播成为簇首的消息，通信距离远远比LEACH协议中向整个网络广播要短；而且簇内成员节点无需检测广播信号的强弱，也无需加入特定的簇，因为每个节点在初始划分区域阶段就已经有一个簇的归属。在网络运行的后一阶段，MH-LEACH和LEACH两种算法消耗的能量相差不多，主要是因为在簇间路由阶段LEACH采取的是一跳式簇头节点与SINK节点直接通信，能量消耗较大，而MH-LEACH采取了多跳通信，在蚁群算法所寻找的路径中，每经过一个簇头节点，都要检测其下一个簇首节点的剩余能量，以判断其是否有足够的能量对数据进行转发，当进行多个回合之后，各簇首节点能量有限，不足以承担下一个数据的转发和融合，故蚁群算法路由的优势没有得到发挥，而且在构建蚁群路径的过程当中，也消耗了一部分能量，所以二者的总能耗相似。

在整个回合处理的过程当中MH-LEACH协议死亡的节点都要比LEACH协议少，这就说明改进后的路由协议延长了网络的生命周期。

这是因为，LEACH协议随机产生的簇头，并不是均匀分布于网络中，必然会产生距离SINK节点较远的簇头，而这样的簇头直接的与SINK节点进行通信，耗费了大量的能量，加速了节点的死亡。而本文中改进后的MH-LEACH协议中，在通信阶段，簇头在发送数据时，不与SINK直接通信，而是将簇首的剩余能量和簇首间的距离作为信息素，利用蚁群算法，并引入阈值，形成多跳多路径的传输，这样就均衡了网络终结点的能量消耗，从而降低了节点死亡的概率，延长了网络的生存周期。

参考文献

[1]孙利民，叶驰，廖勇. 传感器网络的路由机制. 计算机科学，2004，31：542-571

[2]邬春学，肖丽．基于蚁群算法的低能耗LEACH协议分析．上海理工大学学报，2010，32（1）：99-102

[3]胡彧，王静.基于蚁群算法的LEACH协议研究.传感技术学报，2011，24（5）：747-751

基金项目：基于信息安全的无线传感器网络路由算法分析与优化（编号：20c1078）