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

无线传感器网络具有与传统网络不同的特点，它与应用紧密相关。传统网络路由协议不能有效地用于无线传感器网络，因而人们研究了众多的无线传感器网络路由协议。本章对几种典型的无线传感器网络路由协议做一些分析介绍，比较他们的优劣，为后面要设计的路由提供理论基础。

无线传感器网络中信道非常复杂，节点所处的环境无法预测，因此给无线传感器网络带来了很多不确定因素，对无线传感器网络中的路由协议的研究是一项极负挑战性的工作。根据不同的分类标准无线传感器网络中的路由协议可进行多种分类，比如：

1、根据应用要求，传感器网络可分为：能量感知路由、基于查询的路由、地理位置路由和可靠性路由。

无线传感器网络具有与传统网络不同的特点，它与应用紧密相关。传统网络路由协议不能有效地用于无线传感器网络，因而人们研究了众多的无线传感器网络路由协议。本章对几种典型的无线传感器网络路由协议做一些分析介绍，比较他们的优劣，为后面要设计的路由提供理论基础。

§2.1 无线传感器网络路由协议的分类与性能指标

无线传感器网络中信道非常复杂，节点所处的环境无法预测，因此给无线传感器网络带来了很多不确定因素，对无线传感器网络中的路由协议的研究是一项极负挑战性的工作。根据不同的分类标准无线传感器网络中的路由协议可进行多种分类，比如：

1、 根据应用要求，传感器网络可分为：能量感知路由、基于查询的路由、地理位置路由和可靠性路由。

2、 根据数据收集方式又可分为传统的当需要时再建立路径的按需路由机制比如动态源路由(On-Demand Source Routing protocol , DSR)和基于数据驱动的主动路由机制比如定向扩散路由(Directed diffusion, DD)以及后面本文提出混合路由机制——动态扩展多路径路由机制。

3、 根据传输过程中采用的路径的跳数，可分为单路径路由和多路径路由。

4、 根据路由是否考虑Qos约束，可分为保证Qos的路由协议与不保证Qos的路由协议。保证Qos的路由协议是指在路由建立的时候综合考虑时延、误码率等Qos参数，从多条路由中选出一条适合Qos约束的最佳路径。

5、 根据节点路由过程是否有层次结构，节点在选路过程中所起到的作用又可分为平面路由和层次路由。平面路由结构简单，健壮性好，适应传感器节点计算功能不强、存储能力低以及信道复杂多变的特点，但是维护路由的开销大，扩展性不好，数据传输跳数多，适合小型网络。层次路由扩展性好，适合大型网络，但是对于簇的维护开销大，算法复杂，对节点功能要求高。

针对无线传感器网络路由机制的特点，评价一个路由协议设计是否成功，往往采用以下指标：

1、能量的有效利用

节点所带的能源有限，如果过多的使用会使部分节点提前失效，这样容易产生路由空洞，甚至导致某个区域的不可到达。为了维持无线传感器网络最大的生命周期，设计路由不仅要考虑能量消耗少的路径，而且要综合考虑整个网络的生命周期，均衡整个网络中节点能量的消耗，避免出现过度使用某些节点，使其失效以致出现路由空洞。

2、扩展性

在无线传感器网络中，由于布置的节点所处的地理位置环境不

同，节点的生存周期也不尽相同。有时甚至是随即放置节点，比如：

军方应用时，通过飞机向敌方阵地播撒节点，这时节点有的可能会

被撒在障碍物比较多的地方，甚至是直接掉进洞里无法于其他节点

联络，有的可能放在比较潮湿的地方使电池及早失效，有的在

使用过程中由于某种原因引起了位置的移动等等。总而言之，由于节点的失效等原因可能要引起整个网络拓扑的变化，这就要求路由机制能动态的适应这种变化，具有扩展性，随着网络拓扑的变化动态调整路由。

3、可靠性

前面说过无线传感器节点所处的环境非常复杂，而且难以预测，再

加上无线信道非常复杂，数据传输的可靠性就显得非常重要。尤其是某些敏感区域的探测，比如外太空某区域环境的监测，煤矿矿井下的瓦斯的监测等等，这些数据非常宝贵，数据的安全到达要求无线传感器网络的路由机制具有较强的容错能力。

4、时延

传感器网络具有相当多的不确定因素，比如拓扑会动态变化，节点

间的通信链路质量随着网络中信息包发送的数量和节点间的距离动态变化等，这些都对数据成功到达目的地的时间提出了挑战。无线传感器网络路由协议必须能够快速收敛，特别是一些对实时任务对时间有较高的的要求时。在这方面一般都是减小通信开销，提高网络传输的效率。

§2.2现有典型无线传感网络路由算法的介绍与比较

目前对于无线传感网络路由算法的设计，国内外提出了很多解决方案，其中比较具有代表性的有泛洪式算法（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的计算方法如下：