2010届通信工程专业毕业设计（论文）
整体的开销。
4.2.1 路由表的建立、更新和数据转发之间的关系
路由表的建立是在组网阶段进行的操作，在路由表建立这段时间内，并没有路由表更新和数据转发的参与，因为节点所维持的路由表中还不包括到达网络内部所有可能到达的目的节点的路由，这样即使有数据转发的参与，也会转发失败。只有当路由表建立完成后，建立、更新和转发这三个操做都会进行，没有先后顺序，只要有新的节点加入，就会进行路由表的建立，当拓扑结构发生变化或节点链路状态发生变化，就会进行路由表的更新，在建立和更新的同时，将伴随着数据的转发。 4.2.2 路由表的建立
组网阶段或有新节点加入时，节点通过广播来告诉其他节点自己的存在，邻居节点收到这个广播包后就将信息插入到路由表，并立即发送新的路由表，这样，经过一段时间后，每个节点就可以建立一个完整的路由表，表中包括了到网络内部所有可能的目的节点的路由。路由表中包含如下信息：目的节点地址、下一跳节点地址、路由跳数、目的节点的序列号以及路由建立时间、路由稳定时间、稳定数据指针。 4.2.3 路由表的更新
无线传感器网络节点之间主要是传播路由更新分组来更新路由表。每个节点周期性地在全网广播路由更新分组，把完整的路由信息发送给邻居节点。不管网络拓扑有没有改变，这种周期性的广播都会发生。除了周期性的广播外，当网络结构发生变化时，比如链路断开、节点失效或有新的节点加入，都需要立即维护路由，这时各节点马上广播路由更新分组，邻居节点接到该分组，确认是新的路由信息就将其路由跳数加1后再发送，该过程一直持续，直到每个节点都收到该分组的一个拷贝。对于过期路由，每个路由表项都有一个序列号。节点广播路由更新分组时，将自己的序列号加偶数再发出去。邻居节点收到更新分组后，首先来比较一下序列号，如果新分组的序列号大于路由表中相应目的节点的序列号，则删除旧的信息，添加这条新的信息，如果相等，就比较路由跳数，选择路由跳数小的，否则，忽略此更新分组，保留原路由表。
路由更新分组可以采用两种形式。第一种是完全更新(Ful1 Dump)，它包含该节点的所有路由表项，需要适配多个网络协议数据单元(NPDU)，在节点移动速度不高的网
23
张志超： DSDV路由协议分析与仿真
络中，这种数据包很少被发送。另一种是较小的增量更新数据包，用来转发那些最新的完全更新后有变化的信息，即两次广播之间，如果有更新信息则用小增量数据包传送。链路断开时路由表同样需要维护。可以通过两个方面来检测链路中断，一种是通过硬件检测，另外还可以通过时间推断，即节点在过了一段时间还没收到前一节点的信息就推断出链路中断，并用跳数为无限大来描述断开的链路。此时，检测出链路断开的节点后就发一个更新分组，这个信息有一个新的序列号，此序列号是原不可达节点的序列号加个奇数，跳数为无限大。这会引起路由表的刷新，只有当再次收到丢失节点的信息后新的路由才会重新建立起来。 4.2.4 数据包的转发
在DSDV中，数据包转发时根据路由表选择路由。每个节点的路由表包括了传感器网中每个其它节点的地址和对应于目的节点的下一跳地址。如图4.1所示:节点1要和节点5通信，节点1查表后得知下一跳为节点2，就把数据包发给节点2,节点2收到数据包时先查表，表上显示:目的为节点5的下一跳是节点4，节点2就把数据包传送到节点4。同理，节点4收到数据包后查表，下一跳是节点5，这样就把数据包送到了目的节点5。整个数据包转发过程是:源节点1一>节点2一>节点4一>目的节点5。
图4.1 DSDV中数据包转发过程
4.3 DSDV相关的关键技术
4.3.1 避免路由环路
DSDV路由协议是由Bellman-Ford(DBF)改进得到的，而DBF算法会导致路由环
24
2010届通信工程专业毕业设计（论文）
路的形成。什么是路由环路呢？路由环路形成的基本原因是在分布式条件下，节点可能会使用一个过期的消息选择路由。
DSDV协议通过采用序列号机制避免路由环路的形成[13]。考虑一个无线传感器网络是由N个节点形成的，假设系统已处于稳定状态，也就是说所有节点的路由表中的路由均为最短路径。在这种情况下，到目的节点的下一跳节点引出一棵以目的节点为根的树。因此，根据网络中所有节点的路由表可构造N棵树，每一棵树都以目的节点为根。以下讨论中，将以目的节点x为例来说明由节点i和边(i，pix)所确定的有向图G(x)的变化。其中pix是到目的节点x的路径中节点i的一下跳节点。DSDV协议保证在任何情况下，G(x)是无环路的，即G(x)由一些无交叉的有向树组成。组成G(x)的树的根是x或是以NULL为下一跳的节点。由于节点x的任意性，只要说明到达x的路由是无环路的，就可推断：根据DSDV的路由表得到的路由在任何条件下都是无环路的。
从无环路状态开始，每当节点i改变下一跳节点时，就可能形成环路。需要考虑两种情况：
(1) 节点i探测到它与其下一跳节点间的链路中断时，节点i就将pix重置为NULL。显然，这种情况下不可能产生包含i的环路。
(2) 节点i从它的一个邻节点k收到一条到x的路由，序列号为可skx，量度为m。考虑是否选择它来替换当前经过pix的路由。用skx表示存储在节点i的序列号的值，dix为节点i到目的节点x的距离量度。根据DSDV选择路由的原则，可知只有在下列两种情况下，节点i才选择k作为下一跳节点来替换pix：
① 从邻节点k收到的路由有更新的序列号，即skx ② skx=six，但从邻节点k收到的路由到x的距离更短，即m 在第①种情况下，节点i选k作为新的下一跳节点，不可能产生环路，这是因为节点i只有从当前下一跳节点收到序列号six后，才将six传向其邻节点。因此，存储在下一跳的序列号的值总是大于或等于存储在节点i的序列号，即从节点i出发，沿到目的节点x的路径上，存储在所经过的节点的序列号构成一个非减序列。现在假设节点i因选择k作下一跳而形成环路，这意味着skx 第②情况下的无环路性质可由Jaffe[14]和Moss定理[3] [15]证明，该定理表明，静态的或递减的链路加权距离矢量算法总能保持无环路路径。 25 张志超： DSDV路由协议分析与仿真 4.3.2 减少路由波动 在DSDV协议中，在序列号相同的情况下，如果节点收到跳数为m的路由后立即发送更新分组，在随后得到跳数为n的路由且m 下面以图4.2来说明实际网络中路由表波动问题是如何产生的。如图4-2所示，假设移动节点MH2有一条路由经12跳到达MH9，节点MH6经11跳可到MH9，且MH4先收到MH2发送的路由更新分组，经过10s后又收到MH6发送的路由更新分组。如果MH4在收到任何新的路由更新分组后就立即更新自己的路由表，并广播更新分组，则在图4.2中所示的情况下，在短短10s的时间中，MH4的路由表就更新两次，并且在网络中发送了太多的更新分组。当有许多移动节点不规则地发送更新分组，或者移动节点独立工作，且发射间隔迥然不同时，路由波动问题就经常发生。 MH4WSN节点群1MH2MH6WSN节点群2MH9图4.2 路由波动问题示例 在DSDV协议中采取触发更新和稳定时间机制来解决此类问题。当节点收到新的路由信息时，可分为两种情况：一是链路失败、有新的路由或是路由度量无穷大；二是调整已存在的路由。对于第一种情况需要立即发送路由更新分组，这就是所谓的触发更新；而对于第二种情况需要等待一段时间再发送更新分组，等待时间由稳定时间决定。所谓稳定时间是指第一次收到到此目的节点的路由的时间和收到到此目的节点的最佳路由的时间的间隔。每个节点都保存目的节点、上次稳定时间、平均稳定时间信息。对每一个目的节点，平均稳定时间是最近的稳定时间的加权平均值。因为越新的稳定时间越能反映最新的网络情况，因此，在做加权平均时，最新的稳定时间的权系数应该是最大的。算法[16]如公式(4.1)： 2ST?ASTn?1ASTn?3式中，ASTn?1表示上次的平均稳定时间； 26 式(4.1) 2010届通信工程专业毕业设计（论文） ST表示最新的稳定时间； ASnT表示这次的平均稳定时间。 为了避免波动，节点可以等待两倍的平均稳定时间后才发送更新分组。但为了尽快对拓扑变化作出响应，等待时间不能太长，因此需设置等待时间最大值。任何等待时间已超过最大值的路由就可以认为是稳定的，如果该路由被修改过，则当路由稳定后需要发送更新分组。 4.3.3 定时器 在DSDV协议中，有三种重要的定时器：路由条目生存时间定时器、周期广播定时器与稳定时间相关的定时器。 在路由表中，每个路由条目都有相应的生存时间，如果在生存时间内该条目未被更新就删除，并认为与此路由相关的下一跳节点不可达，那么路由表条目每一次更新后就把该定时器归零。每个节点有周期广播定时器，在接收到来自邻节点的路由更新分组时，并不马上转发，而是等到周期广播定时器超时才转发(在触发更新时，不需要等待)。在节点中，还有用于计算稳定时间的计时器。 DSDV协议中，网络中的每个节点以同样的周期广播控制分组。如果所有节点在同一时间发送控制分组，就会引起控制包的冲突和网络拥塞。为了防止节点同步发送控制分组，每个节点在发送更新分组前，可以随机地延迟一段时间再发送。 4.3.4 序列号机制 DSDV协议采用了序列号机制避免了路由环路问题。在网络中，每个目的节点都维护自己的序列号。当节点的邻列表变化时，就将本节点的序列号增加2，节点维护的序列号总是偶数。路由表条目中也保存序列号，当节点检测出链路断开时发送一个更新分组，该分组中有一个新的序列号，此序列号是在原不可达节点的序列号基础上加1。当网络拓扑结构发生改变时，为防止节点和邻居节点产生的序列号冲突，节点总是产生偶数号码给自己，而邻居节点总是产生奇数号码。 4.4 本章小结 本章第一节着重介绍了DSDV路由协议的工作原理和运动机制，并通过实例阐述了DSDV路由协议的数据包转发过程。DSDV路由协议是一种基于表驱动的主动路由 27