张志超： DSDV路由协议分析与仿真
2.2.3 协议栈
无线传感器网络作为一种网络，它的协议栈也包括物理层、数据链路层、网络层、传输层和应用层，这与互联网协议栈的五层协议相对应。另外，协议栈还包括能量管理平台、移动管理平台和任务管理平台[10]。如图2.3所示
任务管理平台移动管理平台能量管理平台应 用 层传 输 层网 络 层数据链路层物 理 层
图2.3 无线传感器网络协议栈
2.3 路由协议的分类
目前，无线传感器网中路由协议的最常见分类方式是按路由发现策略，将路由协议按驱动方式分为按需驱动路由和表驱动两种类型，如图2.4和图2.5所示。
按需驱动路由协议AODVDSRTORAABRSSR图2.4 按需驱动路由协议
表驱动路由协议DSDVGSRWRPHSRZHLSCGSRFSR图2.5表驱动路由协议
8
2010届通信工程专业毕业设计（论文）
2.3.1 按需驱动路由协议
按需驱动路由协议(On Demand Routing)，又称为反应式路由，是一种当需要时才查找路由的路由选择方式。节点并不保存及时准确的路由信息。当源节点要向目的节点发送报文时，源节点在网络中发起路由查找过程，找到相应的路由后，才开始发送报文，为了提高效率，节点可以将找到的路由保存在缓存中供后续发送使用。
图2.4是现有的部分反应式路由协议。AODV(Ad hoc On Demand Distance Vector)是DSDV的改进，但它并不维持一张路由表，而是根据需要创建路由，以减少广播数。当有数据包需要传送时，为了寻找路径，源节点广播路由请求分组，邻近节点收到广播后再向其它邻近点广播(但丢弃收到的重复路由请求分组)，直到到达目的地或者到达已有最新路由的中间节点。路由请求分组采用序列号编码以避免环路，并保证中间节点只回应最新的信息。
当节点转发一个路由请求分组到其邻近节点时，在本地只对第一次出现的请求分组进行复制，以便为后续的路由回应分组构造反向路径，但它只是适合对称链路的网络。
若源节点移动时，路由表必须重新初始化；若中间节点移动，其邻近点会发现链路的失效，并将链路失效的信息通告给其上行邻近点，直到源节点收到该信息，然后根据需要重新构造路由。事实上它是DSR和DSDV的结合，它借用了DSR的路由发现和路由维护机制，利用了DSDV的逐跳(hop-by-hop)路由、序列编号和周期更新的机制。
DSR(Dynamic Source Routing)是一种源路由协议，每个分组的分组头中包含了源到目的的整条路由信息。它采用路由缓存技术，用于存储源路由信息，当发现新的路由时则修改路由缓存内容。在此协议运行过程中，包括非常重要的两个方面:路由发现和路由维护。
当有数据包要发送时，源节点先检查缓存中是否有到达信宿的路由信息，若有一个非过期的路由，则可直接采用，否则就广播一个路由请求分组进行路由初始化；路由请求分组中含有源/目的地址和一个唯一的标识符，中间节点收到后，判断其是否有到目的节点的路由，若没有，则将其地址附加到分组的路由记录中，再转发给邻近点。为了限制路由请求分组的传播数目，只有当收到的分组信息是最新的且路由记录中没有节点地址时，节点才处理之。在收到的路由请求分组的路由记录中已包含源节点到此节点的节点序列，当目的节点进行应答时，它将路由记录信息从路由请求分组中复制到应答分组中，若是中间节点的应答，则将缓存中到目的节点的路由附加到路由请
9
张志超： DSDV路由协议分析与仿真
求分组后，再放入应答分组中。在返回应答过程中，先检查路由缓存中是否有到源节点的路由，若网络链路是对称的，则可采用反向解析获得，否则，节点必须发起新的路由发现过程去获得到信源的路由。
在路由维护机制中，DSR采用两种分组:路由差错分组和路由的确认。当数据链路出现致命的传播问题时；会产生一个路由差错分组，节点收到此分组后，从其路由缓存中删除出错的路由跳数，所有包括此出错跳数的路由都将被截去此段。确认分组用于识别链路的正确运行。
TORA(Temporally Ordered Routing Algorithm)是一种源初始化按需路由选择协议，它采用链路反转的分布式算法，具有高度自适应、高效率和较好的扩充性，比较适合高度动态移动、多跳的无线网络。其主要特点是控制报文定位在最靠近拓扑变化的一小部分节点处，因此节点只保留邻近点的路由信息。该算法中路由不一定是最优的，常常使用次优路由以减少发现路由的开销。TORA包括三个基本模块:路由的创建、路由的维护和路由的删除。
TORA算法的原理可以用水从高山上流下的过程来比喻，水道代表节点之间的链路，水道的转接处代表节点，水流代表分组，每个节点有一个相对于目的节点的高度，用做计算路由的度量。如果节点A到节点B的链路中断，就给A一个比其邻近节点都高的高度值，这样水流(分组)就从A回流(这个过程称为反转)，通过其它节点流向目的节点。
ABR(Associativity Based Routing)采用新的方法解决无线路由问题，避免了回路、死锁和重复分组等缺陷。它定义了一种新的路由制式，称为联合稳定度，用于描述两个节点在时间和空间的连接稳定性，节点的联合稳定度高，说明节点处于低移动状态，反之处于较高移动状态。ABR的实质就是发现长期有效的路由。
在ABR中，根据节点的联合稳定度选择路由，每个节点周期性地产生信号(Beacon)以表示它的存在，当邻近节点收到一个Beacon，就修改它的相关表，若收到来自相同节点的信号，则增加与此节点的相关度。
ABR协议由三部分组成:路由发现、路由重构(RRC)和路由删除。路由发现采用广播查询和等待应答的循环方式(BQ-REPLY)，源首先广播一个BQ报文，各节点只转发一次BQ包，当中间节点收到BQ报文后，将其地址和相关标记值附加到此报文中，后续节点删除其上行节点的邻近点联合稳定标记实体，只保留与其自身和上行节点有关的实体。到达目的节点的每个分组包含有各路径节点的联合稳定标记值，这样目的节点通过检查各节点的联合稳定标记值，选择最佳路由。当多条路由有相同联合稳定标记值时，则选择具有最小跳数的路径。一旦路径选定，目的节点沿着被选定的各路径
10
2010届通信工程专业毕业设计（论文）
发送一个应答分组。有应答分组经过的路径为有效路径，其它路径保持非激活状态，因此可避免重复分组到达目的节点，RRC包括局部路由发现、无效路由的删除、有效路径的修改和新路由的发现等，它视不同节点的移动而定。若是源节点移动，将引起一个新的BQ-REPLY处理，因为ABR是源路由协议，路由通知报文(RN)用于删除与下行节点相关的路由实体。当目的节点移动时，其直接上行节点删除此路由。本地查询处理LQ(H)，(H为上行节点到目的节点的跳数)用于初始确定该节点是否仍然可达。若目的节点收到LQ分组，则选择最佳局部路由并应答；否则初始节点超时并返回到下一个上行节点，RN报文发送给下一个上行节点去删除无效路由并通知它进行LQ(H)处理，当这样的处理导致路径回退超时一半时，则LQ处理不再继续，源节点初始化一个新的BQ处理。当所发现的路由不再需要时，源节点广播一个路由删除(RD)报文通知各节点从路由表中删除此路由实体。这里，RD报文采用全广播方式。
SSR(Signal Stability Routing)协议选择路由的标准是利用节点之间信号的强度和节点位置的稳定度。SSR可分为两个相关协议:动态路由DRP和静态路由协议SRP。DRP的任务是负责维持信号的稳定度表与路由表，信号稳定度表记录相邻节点信号强度，通过周期性的与链路层交换信息得到。SRP负责分组的发送和处理。利用DRP建立的路由表完成。若没有现成的路由，则重新启动路由寻找过程。 2.3.2 表驱动路由协议
表驱动(Table driven)路由协议又被称为先应式路由协议，是一种基于表格的路由协议。在这种路由协议中，每个节点维护一张或多张表格，这些表格包含到达网络中所有其它节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护一致、及时、准确的路由信息。不同的表驱动路由协议的区别在于拓扑更新消息在网络中传播的方式和需要存储的表的类型。表驱动路由协议不断的检测网络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即取得到达目的节点的路由。
图2.5是现有的部分表驱动路由协议。DSDV(Destination Sequenced Distance Vctor)路由协议是一种无环路距离向量路由协议，它是传统的Belllnan Ford路由协议的改进。在DSDV中，每个移动节点都需要维护一张路由表。路由表表项包括目的节点、跳数和目的地序号，其中目的地序号由目的节点分配，主要用来判别路由是否过时，并可防止路由环路的产生。每个节点必须周期性与邻节点换路由信息，当然也可以根据路
11
张志超： DSDV路由协议分析与仿真
由表的改变来触发路由更新。路由表更新有两方式:一种是全部更新(Full dump)，即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；另一种方式是部分更新(Inceremental update)，更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在DSDV只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最优路由(如跳数最短)。NS2实现DSDV路由协议的具体策略如下:一个没有找到路由的分组到达节点后首先被缓存，同时节点发送路由查询消息，直到收到接收端的路由响应消息。当缓存溢出时，新来的分组将被丢弃。分组到达目的点后将直接由地址解析复用器送到相应的端口，而后由端口将分组送到目的地。
CGSR(Clusrtered Gateway Switch Routing)与DSDV类似，但是CGSR并不是一个大的平面网络。CGSR分配指定了簇首节点和网关节点，其中簇首节点用来控制一组节点和网关节点，网关节点是两个簇之间的节点。当一个节点要发送分组时，这个分组首先到达该发送节点的簇首节点，然后簇首节点把这个分组通过网关节点转发给另一个簇首节点。不断重复这个过程直到分组到达目的节点。因此，每个节点都必须有其簇首成员的路由表。当一个节点不在任何簇的范围内时或是2个或多个簇首节点在彼此的范围内时，就产生一个新的簇首节点。虽然CGSR用DSDV作为其底层的协议，但是由于在CGSR中寻路是通过簇首节点和网关节点来完成的，所以它比DSDV更有效。此外在CGSR中还可以采用启发式的方法如优先级令牌的调度、网关编码调度和通路预约等来改善其性能。
WRP(Wireless Routingn Protocols)是另一种表驱动路由协议，在网络中的节点中保存路由信息。每个节点在路由表中保存的信息如下:距离、路由、链路开销和重传消息的列表(MRL)。MRL记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新消息的更新列表等信息。这就使得节点可以决定何时发送更新消息以及发送给哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上游节点。然后邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。WRP的优点就是当一个节点试图执行路径计划算法时，可以通过目的节点的上游节点所保存的信息和邻节点所保存的信息来限制算法，使得算法收敛得更快并避免路由当中的环路。由于WRP需要保存4个路由表，所以比大多数的协议需要更大的内存。WRP还依赖于周期性的Hello消息，也要占用带宽。
GSR(Global State Routing)全局状态路由协议，其工作原理与DSDV类似，采用链路状态路由算法，但避免了路由报文的泛洪。它包括一个邻近节点表、网络拓扑表、下一跳路由表和距离表。当链路的状态发生变化时，通过比较报文与本地路由表中的信宿路由序列号大小，决定网络拓扑表的修改，若路由表发生变化则广播给其它节点。
12