基于tinyos的无线传感器网络路由协议的研究与实现

3、 低功耗自适应聚类路由算法（LEACH）

LEACH是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应聚类路由算法，它是第一个在无线传感器网络中提出的层次式路由协议。其后的大部分层次式路由协议都是在它的基础上发展而来的。与一般的平面多跳路由协议和静态聚类算法相比，LEACH可以将网络生命周期延长15%，主要通过随机选择聚类首领，平均分担中继通信业务来实现。LEACH定义了“轮”(round)的概念，一轮由初始化和稳定工作两个阶段组成。为了避免额外的处理开销，稳定状态一般持续相对较长的时间。

在初始化阶段，聚类首领是通过下面的机制产生的。传感器节点生成0，1之间的随机数，如果大于阈值T，则选该节点为聚类首领。T的计算方法如下：

其中p为节点中成为聚类首领的百分数，r是当前的轮数。一旦聚类首领被选定，它们便主动向所有节点广播这一消息。依据接收信号的强度，节点选择它所要加入的组，并告知相应的聚类首领。基于时分复用的方式，聚类首领为其中的每个成员分配通信时隙。在稳定工作阶段，节点持续采集监测数据，传与聚类首领，进行必要的融合处理之后，发送到sink节点，这是一种减小通信业务量的合理工作模式。持续一段时间以后，整个网络进入下一轮工作周期，重新选择聚类首领。

采用LEACH 方法使因能量耗尽而失效的节点呈随机分布状态，因而与一般的多跳路由协议和静态聚类算法相比，LEACH 可以将网络生命周期延长15%。但是LEACH 假设所有的节点都能直接与簇头节点和终端节点通讯，采用连续数据发送模式和单跳路径选择模式，因此在需要监测面积范围大的应用中不适用，而且动态分簇带来了拓扑变换和大量广播这样的额外开销。

4、 GEAR算法

GEAR[12]是充分考虑了能源有效性的基于位置的路由协议，它比其他的基于位置的路由协议能更好的应用于无线传感器网络之中。

GEAR 算法提出既然传感器网络中的数据经常包含了位置属性信息，那么可以利用这一信息，把在整个网络中扩散的信息传送到适当的位置区域中。同样GEAR 也采用了查询驱动数据传送模式。它传送数据分组到目标域中所有的节点的过程包括两个阶段：目标区域数据传送和域内数据传送。

在目标区域数据传送阶段，当节点接收到数据分组，它将邻接点同目标域的距离和它自己与目标域的距离相比较，若存在更小距离，则选择最小距离的邻接点作为下一跳节点；若不存在更小距离，则认为存在“hole”，节点将根据邻居的最小花销来选择下一跳节点。

在域内数据传送阶段，可通过两种方式让数据在域内扩散：在域内直接洪泛和递归的目标区域数据传送直到目标域剩下唯一的节点。

GEAR 将网络中扩散的信息局限到适当的位置区域中，减少了中间节点的数量，从而降低了路由建立和数据传送的能源开销，从而更有效的提高了网络的生命周期。缺点是依赖节点的GPS 定位信息，成本较高。

5、定向扩散算法（Direct Diffusion）

Directed Diffusion[10，12，13]是以数据为中心的路由协议发展过程的里程碑。其他的以数据为中心的路由协议都是基于定向扩散改进或者采用类似的关键思想来提出的。

Directed Diffusion 算法的主要思想是对网络中的数据用一组属性对命名，基于数据进行通信。Directed Diffusion 采用查询驱动数据传送模式。当Sink 节点对某事件发出查询命令时就开始一个新的定向扩散过程，它由查询扩散，初始梯度建立和数据传送三个阶段构成（见图2-1 ）。

在查询扩散阶段，Sink 节点采用和目标数据相似的一组属性对（对象的名称，数据发送间隔时间，持续时间，位置区域）来命名它发出的查询信息，并将查询信息通过广播逐级扩散，收到查询信息的节点缓存信息，并进行局部数据聚集，最终查询信息遍历全网，找到所有匹配的目标数据。

初始梯度建立阶段实际上和查询扩散阶段是同时进行的，当节点从邻接点接收到查询信息时，若当前查询缓存没有相同查询记录，则加入新记录，记录中包含了邻接点指定的数据发送率也就是“梯度”。

在数据传送阶段时，Sink 节点会对最先收到新数据的邻接点发送一个加强选择信息（发送具有更大的“梯度”的查询信息），接收到加强选择的邻接点同样加强选择它的最先收到新数据的邻接点，将这个带更大“梯度”值的查询信息进行扩散，这样最后会形成一条“梯度”值最大的路径。目标数据能沿这条加强路径以较高的数据发送率来传送数据，而其他数据发送率停留在较低水平的节点组成的路径可以作为备选路径以增加网络可靠性。

Directed Diffusion 采用邻居节点间通信的方式来避免维护全局拓扑，采用查询驱动数据传送模式和局部数据聚集而减少网络数据流，因此是一种高能源有效性的协议。它的缺点是，在需要连续数据传送的应用中（环境监测等）不能很好的应用；数据命名只能针对于特定的应用预先进行；初始查询的扩散开销大。

6、典型路由算法的性能比较

DSR,LEACH，Directed Diffusion和GEAR协议克服了Flooding协议的一些固有缺陷，它们在设计中充分考虑了能源的有效利用，成倍的提高了整个网络的生命周期。这些协议针对特定的应用而设计，在不同的环境表现出各自的特色和优势，因此不能绝对的判断哪种协议最优。

我们分析了每种协议的特点，对它们的信息处理、路由优化方式和网络体系结构的不同表现给出了一个综合比较，如表1所示。

其中路径优化能力指的是在选路的过程中能不能根据路径参数进行路径的优化选择，从多条路径中选出一条或几条较好的数据传输路径。