4.4.2　基于集群结构的路由协议

通俗地说，基于集群结构的路由协议就是一种分层的路由协议，在该思想下，网络被划分为多个簇，每个簇都由一个簇头和许多个簇成员组成，每个簇成员如需跟其余簇的成员通信，要先与簇头通信，通过簇头来与其余簇进行通信。在网络规模比较大的情况下，簇头又可以再次分簇，从而形成一个多层网络。簇头节点的职责就是管理好本簇内节点，完成本簇分布范围内数据的搜集，并负责簇间的通信。分层路由的扩展性非常好，对于大规模的无线传感器应用具有很高的使用价值。下面简单地介绍常用的两种分层路由协议。

1. LEACH路由协议

LEACH（Low Energy Adaptive Clustering Hierarchy）是第一个提出数据聚合的层次型路由协议，采用随机选择簇首的方式来避免簇首过度消耗能量；通过数据聚合有效地减少网络的通信量。LEACH是基于簇（Cluster）的协议，协议随机挑选一些节点作为簇首（Cluster Heads）节点，这些簇首节点负责收集并融合周围节点的数据，然后发送给Sink节点。LEACH路由协议的工作过程是一轮一轮地进行的，每一轮均分为两个阶段。

1）建立阶段（Setup Phase）

随机选择一些节点作为簇首节点，具体方法是：节点n选择一个0～1之间的随机数，并且与T(n)做比较，如果小于T(n)，该节点就成为簇首节点。

式中，p代表簇首节点占总节点数的比例，如p=0.05；r为当前的轮数，G为前1/p次轮回中未被选择作为簇首的节点。

当前一轮的簇首选定后，这些簇首节点就对周围节点进行广播，使用载波侦听多路访问（Carrier Sense Multiple Access，CSMA）MAC协议，并且所有的广播都用相等的能量发送。所有的非簇首节点都要侦听任何簇首节点发来的广播信息，根据接收到的广播能量强弱决定归属于哪个簇首节点管理的簇，并且通知该簇首节点。簇首节点根据加入的节点数量，分配给每个簇内节点一个TDMA时隙。

2）就绪阶段（Steady State Phase）

一旦簇首节点确定下来，TDMA时隙也分配好后，网络就进入了就绪阶段。非簇首节点负责采集数据，如果需要发送数据，就用最小的能耗发送给它的簇首节点，非簇首节点在不属于自己时隙的期间可以进入睡眠状态以节省能耗，而簇首节点则必须始终处于接收状态。所有TDMA时隙都轮过后，簇首节点对接收到的数据进行融合压缩，然后直接发送给Sink节点。

就绪阶段经过一段时间后，网络重新选择簇首节点，进入新的一轮。相对于非簇首节点，簇首节点的能量消耗得非常快，如维护簇、融合压缩数据、直接传送数据给Sink节点等。从理论上讲，所有的节点都有机会成为簇首节点，从而均匀分配了能量消耗，避免网络生命周期过快结束。不同的簇首节点与Sink节点通信时会相互干扰，可采用CDMA接入方式来解决这个问题，即每个簇首节点随机选择一种CDMA码与Sink节点通信。

由于LEACH路由协议每一轮都采用随机选择簇首的机制，使能量消耗均匀分布到每个节点，并且由簇首节点进行数据融合后直接发送给基站，可减少与基站直接通信的节点数量，从而延长网络的生命周期。但是该协议也存在一些问题，如每一轮开始都要重新进行一次簇的建立过程，由此带来的控制和计算开销很大，也相应增加了每个节点的能耗；簇首节点直接与基站通信，在LEACH的无线通信模型中，节点发送消息的能耗模型服从自由空间模型（与距离的2次方成正比），当距离大于一定值时，服从多径衰弱模型（与距离的4次方成正比），所以在基站距离较远的情况下，直接通信的代价很大；由于簇首节点的产生在很大程度上依赖于各个节点生成的随机数，这种通过随机数与计算得到的阈值比较的机制只是从簇首节点数目的期望值是最优的角度考虑的，而簇首节点的分布、相应的簇成员数目、簇的大小都不稳定，当簇首节点位置分布较差时，簇内通信不再满足自由空间模型，且存在簇间信号干扰、负载不平衡等问题，这将导致很大的能量开销；簇首节点的选择在考虑节点当前剩余能量的状况时，需要计算网络全部节点的当前能量总和。

2. TEEN协议

针对LEACH协议所存在的不足，研究人员对LEACH协议进行了一定改进，提出了几种新的算法，典型的是TEEN（Threshold Sensitive Energy Efficient Sensor Network）协议。

1）基本思想

按照应用模式的不同，TEEN协议将无线传感器网络分为主动型（Proactive）和响应型（Reactive）。主动型无线传感器网络持续监测周围的物质现象，并以恒定速率发送监测数据，而响应型无线传感器网络只是在被观测变量发生突变时才传送数据。相比之下，响应型无线传感器网络更适合应用在对时间敏感的应用中。TEEN和LEACH协议的实现机制非常相似，只是前者是响应型的，而后者属于主动型无线传感器网络。在TEEN协议中定义了两个门限的概念。

• 硬门限：当传感器节点收集到的数据高于这个门限值时，节点开始向簇首节点汇报数据；

• 软门限：当节点感应到的数据变化值大于这个门限值时，节点开始向簇首节点汇报数据。

在汇报数据之外的时间里，传感器节点将关闭它们的无线发送模块。TEEN协议采用了和LEACH协议相同的成簇机制，在每次簇重组后，簇首节点除了广播数据属性，还要广播硬门限和软门限的值。该协议的工作过程是：在成簇工作结束后，基站节点通过簇首节点向全网公告了两个门限值；各个传感器节点持续进行监测工作，在传感器节点监测到的数据值大于硬门限值的情况下，传感器节点打开无线发送模块向簇首节点汇报数据，并且把这个监测到的数据缓存为监测值（Sensed Value，SV）；在后续的监测中，如果监测数据大于硬门限值，并且与SV的差值大于或者等于软门限值，传感器节点才向簇首节点汇报数据，同时把监测值更新为当前监测到的新值。

2）主要问题

在重新选择簇首节点的过程中，簇首节点一旦确定，便会重新选择硬门限和软门限这两个参数，设置这两个值能在很大程度上减少数据传送的次数，相比LEACH协议可节省更多的能量，适用于实时应用系统，对突发事件可以快速反应；另外，由于软门限可以改变，监控者通过设置不同的软门限值可以方便地平衡监测准确性与系统的节能指标。随着簇首节点的变化，用户也可以根据需要重新设定硬门限和软门限这两个参数的值，从而控制数据传输的次数，但TEEN协议不适合应用在需要周期性采集的应用系统中，这是因为如果网络中的节点没有收到相关的门限值，那么节点就不会与Sink节点进行通信，用户也就完全得不到网络中的任何数据。

根据TEEN协议的这个不足，APTEEN协议在TEEN协议的基础上提出了一种改进型算法，它能够同时解决LEACH协议的实时性不足问题和TEEN协议不能够周期性发送数据等问题，APTEEN协议是一种结合了响应型和主动性两种算法的混合协议，节点在监测突发事件的时候，采用的就是跟TEEN协议一样的响应性机制，为了改进TEEN协议不能周期性发送数据的不足，APTEEN协议在响应性机制的基础上增加了一个计时器，节点发送完一次数据之后就将计时器清零，当计时器时间到达时如果还没有数据发送，那么协议不管有没有达到软门限或者硬门限的要求都会发送这个数据；并且APTEEN协议还提出了三种查询方式，即对历史数据的查询、对当前网络的一次查询和对某一时间的周期性连续查询。图4.5是TEEN协议和APTEEN协议的时间线。

APTEEN协议可以根据用户需要和应用类型来改变TEEN协议的周期性和相关阈值的设定，既能周期性地采集数据，又能对突发事件做出反应。它最大的特点就是随着簇首节点的确定，簇首节点要向簇内所有成员广播4类参数，包括用户期望获取的一组物理属性，硬门限值和软门限值，采用TDMA方式为簇内每个节点分配的时间片，节点成功发送报告的最长时间周期。运行APTEEN协议的节点在发送数据时会采用与TEEN协议相同的数据发送方式，并且规定如果节点在计数时间内没有发送任何数据，便强迫节点向Sink节点传送数据。

TEEN协议和APTEEN协议的主要缺点体现在：构建多层簇以及设置门限值在实现上较为复杂，基于属性命名的查询机制也会带来额外的开销。