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

有泛洪式算法（Flooding）[7]、动态源路由算法(DSR)[2]、低功耗自适应聚类路由算法（LEACH）[8，11]、GEAR算法[9]和定向扩散算法（Direct Diffusion）[10，12，13，14]。这些路由算法各有其优势也有缺陷，而且针对不同的具体应用表现出来的性能也大不一样，但是他们提供了几种不同的思考方向，对后来的很多路由算法提供了借鉴。接下来将简单对他们进行介绍。

1、 泛洪式算法（Flooding）

泛洪式算法是一种传统的洪泛式路由技术，它不需要维护网络的拓扑结构和路由计算，接收到消息的节点以广播形式转发数据包给所有的邻节点，这个过程重复执行，直到数据包到达目的地或者已经达到预先设定的最大跳数。

对于自组织的传感器网络，泛洪路由是一种较直接简单的实现方法，但存在消息的"内爆"（implosion）和"重叠"（overlap）以及"资源盲点"（resource blindness）的特点。

2、动态源路由算法(DSR)

动态源路由算法(Dynamic Source Routing protocol)[2]是按需建立

路由的一种自适应算法。当某个传感器节点采集到数据后，调用路由选取机制，从它的邻居节点中选取一个信道较好、能量充沛或者致汇聚节点（sink节点）距离最近的节点作为其转发节点。其他节点收到这样的数据包后运行同样的算法，从其邻居节点中找出一个最佳转发节点进行转发，直到数据包被发送到目的地。这种算法简单，要维护的数据结构简单，路由维护开销小，但是它路由选择时只考虑眼前最优，没有考虑网络负载，容易导致部分节点提前失效；单路径发送可靠性低，路由的选取具有盲目性，容易走向网络空洞。

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]是