无线传感器网络中路由算法的研究

leixiaofeng

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


其中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所示。


其中路径优化能力指的是在选路的过程中能不能根据路径参数进行路径的优化选择，从多条路径中选出一条或几条较好的数据传输路径。
路由容错性能是指路由算法的鲁棒性，数据通过该路由算法确定的路径到达目的地的可靠性。比如当某个传感器节点失效时，路由算法可以通过路径修补绕过该点，当网络里信道间误码率较高或传感器节点所处的环境影响信号传输时能够保证数据的安全传输等等。
数据传输方式是指信息在传感器网络里是通过直接的点对点传输还是通过中间节点，以接力棒的形式进行数据传输。
网络生命周期指的是所布置的无线传感器网络能够进行有效工作的时间，如果网络中某些节点由于过度使用而提前失效，致使其他节点不能进行组网而破坏了网络的联通性，这样虽然其他节点本身能够采集并发送数据，但是由于网络联通性被破坏，数据不能到达目的节点。网络生命周期是传感器网络里非常周要的一个指标。
数据发送模式指的是数据是主动发送的还是通过其他节点的要求来发送的。主动发送的数据是根据本地的设定的采样频率连续发送的，当传感器采集到数据便打包发送；通过其他节点的要求来发送的模式一般是指汇聚节点根据需要向目的监测区域发送查询命令，通知目的区域发送某种类型的数据，目的区域节点接到命令后，开启数据采集功能，根据命令中要求的频率进行采样并发送。
数据/查询缓存是指路由算法是否设置缓冲池用来为那些已经发送的数据在本地保留副本以便数据包丢失后进行重传，或者用来缓存那些接收到的查询命令等控制信息。数据/查询缓存的使用一方面可以用于保证数据的可靠性或优化路径，但是另一方面它增加了维护路由的开销，设计路由要均衡利弊选择使用。
数据聚集指的是在数据包发到目的地之前是否都发到某一个中间节点进行一些必要的处理，比如某个监测区域监测到的数据先发往一个控制节点进行数据融合，进行一些必要的数据过滤或者对数据进行求平均值等必要的计算，然后再发往目的地，这样可以减少网络通信量。资源有效性是指监测区域收集的数据与汇聚节点实际想得到的数据是否一致，监测区域收集数据的频率和发送时延是否满足要求。
分层是指无线传感器网络中的节点之间功能的划分，如果传感器网络中各个节点的功能一样，都是即可以采集数据又可以控制路由选择，那么这种路由是不分层的，又叫平面路由；如果节点收集到数据后要发往一个专门的控制节点进行选路，那个专门的节点又称为簇头，这种路由机制属于分层的路由，又叫做层次路由。
   

§2.3路由协议接入方式
       前面说过无线传感器网络不同于一般的Ad Hoc网络，它在资源、传输方式以及应用对象方面有自己的特点。无线传感器网络的路由协议与传感器网络的特点对应，是与应用紧密相连的。前面提到的几个应用分别应用的场合也不尽相同，每种协议都有自己独特的优势和缺点。这就要求对于不同的应用能够进行自由的切换路由，路由能够进行方便的更替。现在一些应用于无线传感器网络的系统中有一些对路由层做了封装，以配置文件的形式可以动态的链入，比如：加州大学伯克利分校研究的tinyos系统把路由层以组件的形式实现，提供给上层接口进行调用。组建可以自由的更换，只要提供的接口一致，给上层应用的开发提供了极大的方便，路由层的加入也很方便。Jennic公司研制的bos系统类似于tinyos，相当于tinyos简化版，传感器网络中各部分也是以API接口的形式提供给应用层调用。这些系统的共同之处是为方便应用，把下层包括路由层封装起来，以API接口的形式提供功能调用。下面以tinyos中路由层的调用方式[3]来说明无线传感器网络中路由层的自由变更方式。
       如图2-3所示，AM模块用于连接发送模块，和下面的mac层、物理层通信，调用下层功能完成信息的收发功能。路由模块MultiHopRouter利用AM层的收发接口完成路由选择、路径优化等功能，提供给上层收发接口和Intercept接口，其中Intercept接口用于那些收到的不是发给本地节点的信息。其中AM模块（Active Message）用专门的组件封装好，提供基本的数据的发送和接收功能。路由层架设在AM层之上，提供路由功能，在路由层之上是传输层，由于并没有在系统中实现，所以用虚线表示。路由层之上实际上是应用层，实现的路由都提供这些接口，上层应用在使用时直接调用这些接口，根本不关心具体的实现。这样封装有利于路由层的灵活替换，只要提供相同的接口，就可以很方便的连入应用程序。


传感器网络可能需要在相同的监测区域内完成不同的任务，如果为每种任务部署专门的传感器网络将增加传感器网络的成本。因此，为了完成任务，传感器网络需要根据应用环境和网络条件自主选择适用的路由协议，并在各个路由协议之间自主切换。灵活的路由自主切换为应用提供了方便，节省了成本，但是为路由协议的开发增加了约束条件，加大了开发难度，提出新的挑战。