3.4.2　基于分簇的路由协议

基于分簇的路由协议即将监测区域内的节点按照一定的算法划分为若干个小区域，每个小区域称为簇，在每个小区域中选择一个节点作为簇头，负责组织簇内成员的通信。通常情况下，簇内成员只与簇头进行通信。簇头负责接收簇内成员的数据并进行数据融合，然后发送给基站节点，这样减少了向基站节点传送的数据量，从而达到节省能量的目的。分簇路由协议相对于平面路由协议来说有更好的可扩展性，能满足大型无线传感器网络的需求。

1.LEACH路由

LEACH（Low Energy Adaptive Clustering Hierarchy，低功耗自适应集簇分层型路由）由美国麻省理工学院Henizelman等人于2000年提出，是最早的分簇路由协议，许多后续的其他分簇路由算法都是基于LEACH改进的。

LEACH的基本思想是：周期性地循环随机选择簇头节点，簇头节点接收簇内节点的数据后，将数据融合转发给基站节点，从而将整个网络的能量负载均衡分配到每个传感器节点上，以实现最大化网络生存时间、降低网络能耗的目的。LEACH的分簇结构图如图3-4所示。

LEACH协议是周期性进行的，一个周期称为一轮。每一轮分为簇的建立、稳定的数据传输。一般来说，数据传输的时间远远长于簇建立的时间，以减少成簇的消耗。

（1）簇的建立

簇的建立过程又分为两步，第一步是簇头选举；第二步是簇的形成。

簇头选举：簇头节点的选举采用随机方式，意味着网络中的每个节点均可被选举为簇头（以相同概率），这对均衡网络能耗起到了一定的作用。具体过程如下：每个节点生成一个0～1之间的随机数，若该随机数小于本轮循环的阈值T（n），则该节点就当选为本轮的簇头。使用T（n）作为阈值，可以保证节点在近1/p轮内一定当选为簇头。T（n）的计算公式如式（3-1）所示：

式中，p是簇头节点占全部节点的百分比；r是当前轮数；G是前1/p轮中还未被选举为簇头的节点集合。

在本轮中，若某节点已经作为簇头节点，则将T（n）赋值0，该节点不会再次被选为簇头。随着r的增大，T（n）越来越大，产生的随机数小于T（n）的概率也越来越大，还未当选过簇头的节点成为簇头的概率也随着增加。

簇的形成：当簇头节点全部选举完成后，它们会通过广播方式告知整个网络它们是本轮的簇头节点。其他节点收到信息后，根据收到信号的强弱来决定加入哪个簇（加入离它最近的簇），并向相应的簇头发送加入信息。簇头节点收到这些信息后，就可以确定本簇的成员。基于簇的规模，簇头节点创建一个TDMA时隙表并广播给簇内成员，告诉它们什么时候开始传输数据，让其分别在对应的时间内传输，这样就可以保证簇内成员传输数据时不会发生冲突，完成簇的建立。

（2）稳定的数据传输

若簇内节点要发送数据，则在簇头分配的时间内发送数据给簇头，不进行数据传输的节点则关闭无线信号，自动休眠，以减少节点能耗。当簇头节点收到簇内所有节点传输的数据后，进行数据融合，再发送给基站。数据融合的目的是去除冗余数据，减少传输量，降低传输能耗。当算法执行了一段时间后，网络重新启动，进入下一轮的簇头选举、成簇和稳定的数据传输阶段。

LEACH协议的优点：采用分簇的思想将网络划分为多个簇，每个簇自治管理，簇头负责收集簇内成员的数据，并对接收的所有数据进行融合，消除冗余，减少传输给基站节点的数据量，从而减少节点能耗。整个过程十分简单，不需要维护复杂的路由信息，减少了路由控制的代价；LEACH协议随机选举簇头节点，并且每隔一定时间后重新选举簇头，这样能量消耗可以平均分配到每个节点上，避免某些节点长期担当簇头节点因能量消耗过快而过早死亡，从而延长整个网络的生存时间。

LEACH协议的缺点：随机选举簇头的机制虽能保证每个节点都能以相同概率当选为簇头，但未考虑节点的剩余能量，有可能还没有当选簇头时能量就很低，在当选簇头后因能量快速耗尽而死亡，导致网络异常；也有可能某个节点虽然当选过簇头，但剩余能量仍然很高，而LEACH算法不允许其再次当选为簇头；簇头和基站节点的通信采用一跳方式，当两者距离很远时，传输数据会消耗簇头大量能量，加速节点死亡，从而缩短网络生存时间；在成簇阶段，没有充分考虑簇的规模，导致有些簇过大从而使得簇头节点负担过重，影响整个网络的生存时间。

2.TEEN路由

无线传感器网络路由协议按路由发现策略可分为主动路由和被动路由。主动路由协议持续监测周围的物质现象，并且以恒定的速率主动发送监测数据；被动路由协议只是在被观测变量发生变化时才传送数据。被动型无线传感器网络路由协议相比主动型路由协议更适合对时间敏感度的应用。

阈值敏感的高能效无线传感器网络路由（Threshold sensitive Energy Efficient Sensor Network Protocol，TEEN）是在LEACH协议的基础上发展来的。TEEN是第一个针对被动型无线传感器网络的分簇路由协议，主要思想是将网络划分为一个簇头节点和多个簇成员。簇头节点负责簇内成员的管理，并且完成簇内信息的收集和融合工作，同时还负责簇内信息数据的转发，如图3-5所示。

TEEN的工作方式和LEACH的工作方式基本相同，只不过在每次重新选择簇组建簇区域之后，簇头节点需要向簇内成员广播以下三个参数。

①特征值：用户所关心数据的物理参数。

②硬门限（Hard Threshold，HT）：监测数据特征值的绝对门限值。当节点监测的数据特征值超过这个门限，才启动发射机向簇头节点报告这个数值。

③软门限（Soft Threshold，ST）：监测到特征值的小范围变化门限，从而触发节点启动发射机向簇头节点报告数据。

在TEEN中定义了硬软两个门限值，以确定是否需要发射监测数据。具体工作过程是：①节点持续不断地感应外界从而获取数据。②如果感知数据的特征值第一次超过了它的硬门限，节点就会启动发射机发送该感应数据，这个特征值也被存储在节点的外部变量中，称为感应值（Sensed value，SV）。③当且仅当以下两个条件都成立时，节点才会启动下一次数据发送：a.当前感应到的特征值大于硬门限值；b.当前感应到的特征值与SV的差值大于等于软门限值。④SV设置的值为每次节点发送完当前感应的特征值数据。直到一个周期过去，新的簇形成，重新设置硬门限值。

硬门限是根据用户对感兴趣的范围设定的，这样做减少了不必要的数据传输次数。如果感兴趣的数据和先前数据变化不大，就不必向簇头节点报告，这就是设置软门限的意义所在，也降低了不必要的数据传输次数。其次，软门限的数值也可以随时变动，完全取决于用户的需要。设置较小的软门限使网络数据更加精确，但代价是增大了传输过程的能量消耗，因此，在工作时，要根据实际情况选择软门限。通过调节软门限的大小，可以在监测精度和系统能耗之间取得合理的平衡，这样就可以监测一些突发事件和热点地区，减小网络内信息包的数量。

TEEN协议的优点如下：

①通过设置硬阈值和软阈值两个参数，TEEN可以大大减少数据传输的次数，比LEACH节约能量。

②由于软阈值可以改变，监控者可以设置不同的软阈值来达到平衡监测准确性与系统节能指标。

③随着簇头节点的变化，用户可以根据需要重新设定2个参数的值，从而控制数据传输的次数。

④协议适合于需要实时感知的应用环境中。

TEEN的缺点是不适用于需要周期性采集的数据的应用系统中，这是因为如果网络中的节点没有收到相关的阈值，节点就不会与汇聚点通信，用户也就完全得不到网络中的任何数据。

3.PEGASIS路由

传感信息系统的能耗有效聚集路由（Power Efficient Gathering in Sensor Information System，PEGASIS）是在LEACH基础上建立的路由协议，是为了避免LEACH协议中由于频繁更换簇头而导致的数据通信耗用较多的资源和能量的情况而改进的。尽管采用了动态选举簇头的思想，但网络中所有节点只形成一个簇，称之为链。链中的传感器节点只需要与它相连最近的邻居通信，各个传感器节点轮流成为链首，采集的数据在链中以点到点的方式传送、融合，最终由链首送到基站节点，如图3-6所示。

在一个工作轮中，节点N2被选为链首（簇头），链首节点向周围节点传播链首标志信息，收到链首标志信息的节点N0将采集的信息传给节点N1；节点N1将收集到的N0节点数据和本身采集的数据进行融合处理后，再将数据传给链首；节点N3、N4和链首节点N2间的数据传输类似。

PEGASIS协议减少了LEACH簇重新产生的能量消耗，并且通过数据融合技术降低了节点的能量消耗，与LEACH协议相比，PEGASIS协议延长了网络生存周期大约2倍。PEGASIS协议与LEACH协议相比在以下几个方面节省能量：

①在传感器节点进行本地数据通信阶段，PEGASIS协议的算法中，每个节点只需要和自己距离最近的邻居节点通信。在LEACH协议算法中，每个非簇头节点都要直接与所在簇的簇头节点通信。因此PEGASIS协议算法减少了每轮通信的各个节点的通信距离，从而减少了每个节点消耗的能量。

②在PEGASIS协议算法中，链首节点最多只能接收两个邻居节点的数据以及向基站发送网络的数据。在LEACH协议的算法中，簇头节点除了向基站发送数据之外，还要接收所在簇的所有非簇头节点的数据，簇头节点接收的数据量远远大于PEGASIS协议中链首节点接收的数据量。因此在LEACH的协议中，簇头节点的能量消耗很快，不利于均衡节点的能量消耗。

③在每一轮通信的过程中，PEGASIS协议中只有一个链首节点与基站进行通信，而在LEACH协议中有许多簇头节点与基站进行通信。基站的位置是远离网络的，使网络中各个簇头节点的能量消耗过快，不利于节约能量。因此PEGASIS协议的网络生命周期比LEACH协议的网络生命周期长。