本章要介绍的是动态扩展路由协议的总体规划，该路由协议的运行原理以及设计该协议所使用的环境。动态扩展路由算法思想来源于洪泛路由算法、动态源路由和多条路径不相交路由，适用于中小型传感器网络。该路由协议提供较高的可靠性，根据连接参数平衡网络负载，使网络生命周期变长。动态扩展路由是一种主动路由，不支持查询，但是可以在应用层实现数据查询功能；它又是一种平面路由，节点间不存在层次关系，每个节点既是一个数据采集者，同时也可充当一个路由器，具有选路功能。
动态扩展路由协议是在tinyos系统环境下用nesc语言开发的，可应用于crossbow公司的MPR系列节点和宁波中科的gains系列节点。该协议在设计好的第一个阶段用宁波中科的gains3节点做了组网测试，测试其动态组网功能和网络收敛时间，测试效果达到预期要求。后来又经过算法的改进和程序优化，才形成现在的动态扩展路由。
动态扩展路由协议的开发经过了大概8个月的时间，前期准备工作用了将近4个月。该协议是在研究无线传感器网络协议栈的基础上，在tinyos系统下进行开发的。准备工作有：对tinyos系统的熟练掌握，无线传感器网络编程模式的掌握（nesc组件式编程模式），对收发器芯片cc1000协议栈的研究以及仿真工具的掌握和仿真环境的建立。
由于传感器节点本身的计算功能简单，存储能力低，所带电源供电能力不强，收发器芯片发射接受功能不强，这就要求所开发的软件代码精练，算法简洁高效。如果代码过于冗长，就无法放到传感器节点中运行，比如现在应用在节点上比较多的微控制器Atmega128L，主频8MHz,flash空间才128k，数据存储器4k，根本就无法运行常规程序；如果算法过于复杂，不但实现起来困难，而且会增加存储要求和计算要求，对传感器节点本身的要求提高，不适合无线传感器网络里传感器节点价格低廉、功能简单的初衷。这些限制为路由程序的设计增加了很强的限制，路由协议就是要在这些限制下尽量提高传感器网络的效率。下面就从开发环境、协议功能模块、数据定义以及数据包的流程等方面进行讲述动态扩展路由协议的总体设计。
§3.1 开发环境简介
动态扩展路由协议是在tinyos系统环境下进行开发的，该系统可以在linux系统和Cygwin环境下运行，编译出的代码可以直接在Atmel公司的Atmega128L微处理器上运行。
3．1．1 Tinyos 系统简介[1] [4]
Tinyos 系统是加州大学伯克利分校的研究人员经过比较、分析与实践，针对传感器网络的特点设计出来的。目前已经拥有了很多嵌入式操作系统比如Ucos，VxWorks，Linux，WinCE等，这些系统中有基于微内核架构嵌入式操作系统如Ucos和VxWorks，也有基于单体内核架构的嵌入式操作系统如Linux等。但是，由于这些操作系统主要面向嵌入式领域相对复杂的应用，从而其功能也比较复杂，如它们可提供内存动态分配、虚存支持、实时性支持、文件系统支持等，系统代码尺寸相对较大，部分嵌入式系统还提供了对POSIX标准的支持。而传感器网络的硬件资源极为有限，上述操作系统目前很难在这样的硬件资源上正常运行，因此选择tinyos这一为传感器网络量身定做的嵌入式操作系统。
Tinyos是一个开源的针对无线传感器网络开发的嵌入式操作系统。目前它拥有包括tinyos-1.x系列从1.0版本到1.17版本，tinyos-2.x 系列beta2.0版本总共有十八个版本。它拥有组件式的架构，使在其上的开发和实现比较方便快捷；同时使代码的尺寸最小化，适应无线传感器网络内存资源苛刻的要求。Tinyos组件的库函数包括网络协议的支持（新开发的路由协议也是以库文件的形式使用），分布式服务的支持，传感器驱动的支持，以及一些可以在收集数据时使用的应用工具。Tinyos拥有两级调度、轻量级线程技术、主动消息、事件驱动模型以及组件化编程等。轻量级线程和主动消息和并行计算中用于高性能通信的轻量级线程和主动消息差不多，在两级调度模式下，一般的轻量级线程（tinyos中的任务，task）按照先进先出（FIFO）方式进行调度，线程之间不允许抢占；而一些用于硬件处理的线程比如底层收发的线程用async关键字标识，这些线程可以抢占用户的任务——用户的轻量级线程和低优先级的中断处理线程。一些共享的资源比如一些用户定义的共享变量等需要互斥操作利用原子操作（atomic关键字标识）和同步原语（wait、sleep等函数调用）进行访问保护。主动消息是一种基于事件驱动的高性能并行通信方式，这种消息处理方式与tinyos的两级调度方式结合，使通信层传来的通信事件能够得到快速响应，有效的提高CPU的使用率。
Tinyos没有内核，没有内存管理，没有进程管理，也没有虚存支持，之所以这么设计是为了尽量减小代码尺寸，提高代码运行效率。它所支持的nesC（network embedded system C）编程语言是一种C扩展语言，编译过程是先通过ncc编译器编译成C语言格式，然后连接gcc编译器，编译成对应各种单片机的目标代码。由于本协议开发的目标节点是corssbow公司生产的MPR2400（micaz）节点和宁波中科开发的gains3节点，所以最终代码格式是.srec和.hex文件。
3.1.2 Tinyos 中的组件模型
Tinyos中的组件以功能实现划分，把某种功能封装起来以接口的形式提供调用。这样可以实现高效率的模块化，使组件型应用软件的构造变得简单易行。对于嵌入式来说，为了提高可靠性而又不牺牲性能，建立高效的组件模型是必需的。Tinyos系统采用的开发语言nesC是一种C语言的组件化扩展，组件之间以命令/事件接口的形式进行调用或提供服务。以tinyos中提供的ADC接口为例，它提供两个命令一个事件，实现ADC接口的组件提供ADC接口里命令的调用，而使用ADC接口的组件要实现这个接口中事件。简单的说就是你用了别的组件提供的数据收集命令，那么你就要实现因为数据收集好而触发的事件，这个事件一般是对收集好的数据进行一些处理然后发送或者存储。组件之间就是以这种命令/事件的形式相互关联。
interface ADC { async command result_t getData(); async command result_t getContinuousData(); async event result_t dataReady(uint16_t data); } Tinyos中提供了各种功能的组件，以自上向下大的顺序可划分为应用组件、消息处理组件、消息包组件、字节切分组件和比特处理组件。根据软件和硬件以及软硬件的边界结构划分又可以对它划分为：硬件抽象组件、合成组件、高层次组件。一般应用程序的组件结构如图3-1所示。 
Tinyos中组件之间以接口的形式相互关联，这样使组件之间的连接大大简化，提供很高的组件独立性。图3-1所示的是应用程序中组件之间的调用关系，其中向下的箭头表示命令的调用，上层组件调用下层组件接口中的命令，而当下层有相应的事件时又反馈给上层组件，在图中以向上的箭头表示。
按照软硬件的区别和接近程度可把这些组件划分为硬件抽象组件、合成组件和高层次组件，硬件抽象组件将物理硬件映射到Tinyos中的组件模型，比如用于控制mac层收发功能的HPLSpiM组件提供SpiByteFifoC接口，提供操作RFM收发器的收发功能，而这些功能的实现是通过对RFM模块里定义的各个引脚的定义的操作进行映射。这些硬件抽象组件大部分是以嵌入式汇编的形式提供的功能函数组合。硬件抽象组件属于介于软硬件之间的一种边界组件。合成组件是一种提供接口转换，以及不同数据格式进行交互的组件，比如图3-1中的字节切分组件，它将数据以字节为单位与上层组件交互，以位为单位与下层进行交互。高层次组件是指上层的那些完成路由功能，数据处理等功能的组件，组件之间可以协同工作。比如路由控制组件和数据融合组件，在进行发送数据之前对数据进行过滤等处理，然后再选路发送。
3．1．3 Tinyos中的通信模型[15]
Tinyos系统中消息的处理以主动消息的模式进行。在这种消息处理方式中，每个消息都维护着一个对应的应用层处理句柄，当节点有消息到达时，把收到的数据以参数的形式提交上层处理，不同的消息可以对应不同的处理句柄，这一点和系统中的参数化接口结合紧密。比如收到的消息包含的是采集的数据，这条消息将交给上层的数据处理句柄，如果收到的是控制消息，那么交给上层相应的处理句柄进行解包执行相应的操作。在tinyos系统中，主动消息被实现了为AM模块，提供基本的通信原语。因为在无线传感器网络中应用千差万别，所采用的硬件也是各不相同，所以Tinyos不可能提供适合所有需求的通信组件，只能提供最基本的那些，如果应用需要可以加入新的通信组件。
在tinyos中对消息的缓存空间是确定的，因为它所用nesC语言的一个特点就是在编译时确定所有要分配的空间，不支持动态分配内存。
这样设计系统是为了适应传感器节点中限制苛刻的存储空间。消息的发送和接受都采用二级反馈的形式，当发送数据时，调用发送命令send（），立刻返回，把处理器资源交给系统调度，事件sendDone（）可以告诉上层这次发送是否成功，当然这些要靠mac层的反馈；当接受数据时，进行一些判断和处理后，提交上层该缓冲区，无论接收成功或失败，都要返回该缓冲区，因为系统中的缓冲区是固定的，如果不返回很容易使缓冲区耗尽，造成其他任务无法完成，整个系统崩溃。
§3.2 动态扩展路由协议工作过程
动态扩展路由协议主要过程如下：最初网络中的传感器节点除汇聚节点外都用路由锁锁住，不能发送任何消息，汇聚节点洪泛初始化消息，收到消息的传感器节点解开路由锁，并更新本地存储的数据结构，周期性的发送选路信息，运行选路算法，根据链路质量等参数选举最佳转发的下一跳节点，当发送或转发数据包的传感器节点的信道不好（由mac层反馈机制检测出来）时，根据该节点在网络中的深度和该节点的连接数等参数决定是否要进行动态扩展路径，设置保活定时器来维护扩展路径的有效反馈时间，对应动态扩展路径设定近点反馈、远点动态扩张的机制，从时延，信道质量，网络负载平衡，传感器节点在网络中的深度等多方面考虑路由协议的性能，使其在保证较高的可靠性的前提下能均衡网络负载，缩短网络延迟，节约能量开销。该路由协议综合了洪泛、动态源路由以及多条不相交路径等路由算法的优点，根据链路的状态，采用动态扩展路径条数。下面分别就各个方面进行介绍。
设定传感器网络中的每个传感器节点有一个唯一的标识，这个标识分两部分：一个组号groupID，一个节点号ID。每个组里可以有很多个节点，但是每个节点只能同时在一个组里。传感器节点只能和同组内的节点进行通信。根据组号可以对网络划分出很多网格，针对不同的网格进行布置不同的应用任务，进行不同的控制。为了便于于仿真和测试，本协议把这些节点都放在同一个组里，也就是说所有的节点有一个共同的groupID，这不影响本协议的适用范围，改动也很方便。
3．2．1 洪泛过程（网络初始化）
起初节点被编程后，或者被通过网络重编程改变了应用程序，节点复位，路由协议启动并开始运行，首先进行的便是洪泛初始化过程。起初传感器网络中的节点除汇聚节点（sink节点）外都被路由锁 routeLock锁住，被锁住的节点不能发送任何信息，但是能接收。设定网络中的ID号为0的节点为sink节点，网络启动时只有0号节点发送广播信息，如图3-2a所示。Sink广播的信息包括以下几个域：hops——至sink节点的跳数，cost——到sink节点的费用，sourceID——发送此洪泛消息的节点ID号。
当传感器网络中的节点收到该消息后，立即解开路由锁，更新本地至sink节点的跳数hops值，到sink节点的花费值。到sink节点的花费值计算公式为：
其中n为从sink节点到本地节点的最短路径上的节点数（不包括sink节点和本地节点），C值为与传送解锁信息给本地节点的邻居节点之间的连接费用。除了更新hops值和cost值，还要根据hops信息把本地邻居列表划分成两个域：比自己距离sink节点更近的节点域——FCS域（forwarding candidate set）和比自己距离sink节点更远的域——CS域（client set）。FCS域用于选择要把数据包转发给的下一跳邻居节点，CS域是要用本地转发数据的邻居节点集合。收到sink节点的洪泛消息的节点更新本地数据结构后，把收到的洪泛消息继续广播给其邻居节点，并把广播消息中的hops值加1，把sourceID值更新为本地节点ID号，cost值为本地cost值，其过程如图3-2b所示。传感器网络中的节点有可能收到来自不同邻居节点的洪泛消息，它根据至sink节点的跳数、链路质量等信息选择一个较佳的邻居节点，用它传输的信息进行更新本地数据并转发。
从网络启动开始，sink节点就一直处于广播洪泛消息的状态，其他节点收到该类型消息后除了打开路由锁外，路由探测机制启动。当sink节点收到从网络中传过来的数据包时，停止广播洪泛消息，洪泛过程结束。
网络初始化使用洪泛过程可以避免传感器网络选路的盲目性，因为起初根本没有整个网络的全局拓扑信息，不知道sink节点至每个节点的跳数，每个节点也不知道自己的邻居节点的状态和他们在网络中的位置。这样就避免了初期用于探测sink节点信息的大量信息包的发送，传感器节点由于盲目探测而造成的比较大的网络延迟。网络启动时，如果直接动态寻找sink节点建立路径，很有可能做一些南辕北辙的事，绕很长弯路，这样也会浪费很多信息包，造成能量的耗费。利用洪泛过程，sink节点可以高效的把sink节点方位，路径花费等信息告诉网络中的节点，即可以节省很多信息包的传输又可以提高网络的收敛速度。虽然它是以广播的形式传输信息，但是它的运行只是在网络初始化阶段，一旦开始了数据传输就立刻结束，所以不会带来很大的网络负载，而它的效率却是其他方式无法替代的。
3．2．2 路由探测机制
当网络中的传感器节点的路由锁被解开后，路由探测机制便开始启动。节点开始周期性的广播路由信息，路由信息包括本节点用到的转发节点集（不一定是FCS的子集）、路由表的部分信息、本地节点至sink节点跳数hops、经过本地节点的路径数links以及本地节点至sink节点的花费cost值等信息。其中路由表的部分信息是把路由表中部分邻居节点（随机从FCS域和CS域中获取）的链路质量和对应的邻居节点ID号。传感器网络中的信息被分成很多类型，每种类型的信息都有一个确定的类型标识type，根据type值的不同，为每种消息选择处理句柄，这一点和传统Tcp/ip网络中的协议分用相似。
无线传感器网络中的其他节点收到这种类型的路由信息时，首先检查路由锁是否打开，若没有便首先打开路由锁，开启路由探测机制。因为有可能近点的节点由于路由锁解开的较早，已经开始了数据传输而导致洪泛过程已经结束了，而这个时候其他节点转发的洪泛信息还没有到达本地或者没有成功接收，这样路由锁还处在锁定状态。处理完路由锁后，根据路由信息中的hops、links以及cost值等信息更新路由表中对应邻居节点的记录。从路由信息中包含的部分路由表信息（指发该路由消息的节点的路由表信息）中检索是否包含有本地节点的信息，若有则根据其中的记录信息更新链路质量。路由探测机制运作过程如图3-3所示。
图3-3中节点周围环绕的箭头代表广播路由信息，路由机制被触发后便周期性的发送路由信息，使节点的路由表一直反映比较新的网络状况。在图中有部分节点没有广播路由信息，这是因为有可能洪泛消息或路由消息还没有到达，或者他们本身处的位置较偏，没有接收到洪泛消息和路由信息，或者节点本身有其他状况而不能正常工作。路由信息的发送是根据定时器设定的频率定时广播的，根据应用对传感器网络中能量消耗、网络延迟等性能的要求可以动态设定这个频率。通常情况下这个频率f是数据收集频率F与一个网络平衡因子δ(大于1的整数)作用结果。在实际实现的时候通过对代表F的整数进行移位操作来完成对f的动态调整，也就是说δ是2的幂级数。
f＝F<<δ或f＝F>>δ
这样的话f的调整是以指数级进行的，对上层不同应用的需求可以进行快速的反映。
通过上面对路由探测机制的介绍可以看出它的主要目的是为了保持路由表的有效性，为选路要运行的选路算法提供支持参数信息，这些参数越接近实际的网络状态，选路算法选出的路径才能更佳。值得注意的是传感器网络中有一个特殊的节点，它就是sink节点，它是在第一次洪泛广播成功后就开启了路由探测机制，它的路由锁一直是打开的，它的洪泛过程和路由探测过程在一段时间内是并存的。
3．2．3 动态选路过程
当网络中的某些节点有数据要发送时，首先检查路由表，如果有相应的转发节点并且有效则直接使用，开始发送；如果没有，运行选路算法从FCS域中选取一个转发节点，若FCS域中没有符合要求的节点则检查标识可逆向传输距离的变量DIRECT是否为零，若不为零把其减1，从CS域中选取一个最佳转发节点，若DIRECT值为零则退出，本次选路失败。传输中的数据包消息用以下几个域用来唯一标识：
Destaddr: 目的节点地址
Originaddr: 数据源节点地址
Sourceaddr: 发送本条消息的节点地址
S_hops： 发起动态扩展路径的节点至sink节点的跳数
Ext: 本条消息在网络中扩展的路径数
Seqno: 本数据包的序列号
根据前三个可以唯一确定一种数据包消息，而Seqno可以确定这个数据包是否是新的还是已经发过了。当传感器网络中的某个节点收到数据包消息时，根据头三个参数可以确定一条路径，一条路径对应一种数据包消息，由这三个参数可以知道这个数据包是由谁发起的，发到哪里去，经过谁发过来的。当传感器网络中某个节点发送或转发数据包时，由于信道不好可能引起发送失败，数据发送失败次数超过阈值后还是不能成功，则开始动态增加一条路径，多选择一个转发节点进行发送或转发，Ext记录的就是这个数据包信息所占用的路径条数，如图3-4所示。
在图3-4中，节点14是数据源，它有把采集到的数据经过转发节点8发望汇聚节点0。节点8又选择11号节点为下一跳转发节点，节点11通过起初通过1号节点转发，发送失败后（数据重发次数超过门限值）重新运行选路算法，并且增加一条路径，重新选择节点6和节点16作为下一跳转发节点。当然，选路算法根据在路由探测过程探测到的信息作为选路标准，从邻居列表中选择最优的转发节点。经过多条路径传输的数据到达sink节点后，sink节点只处理收到的第一份拷贝，其它重复的数据直接丢弃。
当动态增加后的路径又发送失败时，首先比较本的节点到sink节点的距离hops和到发起动态扩展路径的节点的距离S_hops值。如果距离sink节点更近则检查动态扩展的路径数Ext是否超过了最大路径数MaxPaths值，若超过则放弃这条路径，丢弃数据包；若没有超过该值则返回一个反馈消息，通知动态扩展发起节点该条路径失败。以图3-4为例，若节点11经过节点16转发的路径失败，节点16检测Ext值没有超过MaxPaths值，则反馈给动态扩展发起节点11路径扩展消息。节点11号收集这些反馈消息，如果收集到的失败的路径数等于所建立的路径数，即所有传输路径均失败时，再重新运行动态扩展过程，继续扩展路径，这个扩展——失败——扩展过程一直持续到成功发送或者到最大路径数已经到达MaxPaths值。这里有一个假设：数据发送过来用到的路径是可靠的，无误的，这样返回的路径失败消息准确无误的返回给发起动态路径扩展的节点。
选路过程中主要依靠至sink节点的花费cost、至sink节点的跳数hops以及节点所占用的路径数links。取这些参数或倒数作为参考依据，根据这个W值来选定最佳转发节点。根据式子
W＝file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.gif
对FCS域中邻居节点从小到大进行排队，选取hops值最小的作为转发节点。上式中file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image004.gif和file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image006.gif是比例常数，根据仿真测试效果决定，也可以根据布置的网络特点进行设定。
在tinyos系统中，传感器网络中节点间数据传输的成功与失败靠mac层的提供的反馈信息。当一个节点发送另一个节点进行接收时，发送节点的底层功能接口发送完数据后并不是立刻返回，而是等待接收方返回一个特殊的立即数，这个立即数取0或1。当返回1时，发送成功，返回0则代表发送失败。这个立即数代表了节点间的同步确认消息，而这个消息是在tinyos系统中主动消息的底层实现的，比在网络层和应用层生成确认消息包节省了很多开销，反馈时间也短。
§3.3 动态扩展路由协议总体框架
动态扩展路由协议是在tinyos系统环境下设计并实现的，沿用了它的参数化接口的特性和对封包格式的定义。针对平台的特点，把动态扩展路由协议分为两大部分：前端和后端；另一方面，由于路由协议与应用的紧密相关的特性，留出部分接口让应用层灵活调用。
协议的运作方式如下，前端提供send（）接口函数，在send接口函数里调用后端支持算法里的选路接口函数selectRoute（），selectRoute（）的功能是给要发送的数据包填上包头（比如下一跳地址nextAddr,至sink节点的跳数hops等信息），然后调用mac层（CSMA）提供的底层驱动程序进行发送。至于接收，应用程序可以有更多的选择，路由程序里接收接口事件处理函数receive（）提供简单的转发和过滤功能，应用层可以根据具体的需要重新实现或单独实现这个事件处理部分。
如图3-5所示，应用层可以直接使用AM（Active Message）层的发送和接收功能，例如数据在节点之间以单跳方式传输或广播传输的情况下就可以这么使用，因为这个时候用不着路由功能，这样可以省去不必要的路由维护开销。图中向下和向右的箭头方向是指接口命令的调用，而向上和向左的箭头方向是指触发的事件发生了，反馈给相应的事件处理接口。在tinyos系统中使用了动态消息（AM）通信机制，把无线传感器网络中的消息按照类型进行了分类。应用时可以根据需要定义自己需要的消息类型，而消息类型作为send[type Id]()、receive[type Id]()等参数化接口的参数Id，根据不同的Id调用相应的发送过程和事件处理接口函数。这样应用程序可以同时使用路由层和AM层提供的发送和接收等功能接口，分别用于不同的应用目的。
路由层的前端直接面对应用层提供服务，起到承上启下的作用。它除了提供给应用层基本的发送接收接口外，还提供了像获得缓冲区getBuffer（）、节点在网络中的深度查询getDepth（）等接口。路由前端通过选路接口selectRoute（）以及一些协议控制接口比如：设置路由更新频率setUpdateInterval（）与路由后端进行交互，路由后端通过一些mac层提供的状态控制接口可以直接和mac层通信，进行一些必要的节点状态的调整，比如调整发送距离等。应用层、路由层以及mac层都可以使用一个属于自己的定时器（他们对应的相同的硬件，在tinyos中通过软件方法把他们虚拟化为单独的个体），用于定时触发相应的处理任务。
| 
发表于 2015-3-22 19:36:18
