DSDV

您的位置：首页>>Ad Hoc移动无线网络>>正文

第4节 主动路由协议

4.4 主动路由协议- DSDV 主动路由协议DSDV

(Destination Sequenced Distance Vector)目的站编号的距离矢量

一种基于Bellman-ford算法的主动路由协议。它被认为是最早的自组网路由协议。 主要特点是采用了序列号机制来区分路由的新旧程度，防止可能发生的路由环路。 缺点是不适应变化速度快的自组网，不支持单向信道。

序列号（Sequence number ）

由目的端产生，用来防止出现路由回路，并确保路由信息是最新的 格式： Dest_NNN 加入时间（Install Time）

路由表项的创建时间，用来删除过期表项 Stable Data

指向一个包含有路由稳定状态信息的表 目的节点地址

最近沉淀时间（last settling time） 平均沉淀时间(average settling time) 用于缓解网络中的路由波动

对于同一个目的地，节点可能接收到来自其它节点的多条路由信息，settling time定义为第一条路由和最佳路由之间的时间间隔 向每个邻居公告自己的路由信息 目的节点地址

Metric：到目的节点的开销，一般为到目的节点的跳数 目的地序列号

其它信息（例如硬件地址等）

设置序列号信息的规则

每次公告增加自己的目的地序列号（只使用偶数值）

如果一个节点不再可达（timeout）,则将该节点的序列号加1（奇数序列号），并且设置metric为∞

1) DSDV主要设计思想

每个节点维护一个路由表，每个路由表项包括：目的地址、到达目的节点的度量值（如最小跳数）、目的节点相关的序列号（由目的节点发出）等，该序列号用以识别路由的新旧，作为路由更新和分组转发的依据。

2）信息通告

各节点周期性的向邻居节点通告其当前的路由表，而不是采用洪泛法。这相当于各节点对收到的其他节点的信息进行处理以后再进行广播通告，从而大大减少通告的信息量。 为了进一步减少路由信息的传输开销，DSDV中使用了两类更新报文: （1）完全转存：将路由表项中的所有信息进行通告 （2）递增更新：仅通告更新信息 DSDV信息通告举例

DSDV信息通告举例-有新的节点加入网络时

3）链路断

如果在相当长的一段时间内不能收到相邻节点的广播消息，可推断出链路断。

（1）在DSDV中，断的链路度量值等于∞;

（2）节点检测路由表，下一跳经过该链路的路由表项的度量值标记为∞，并分配一个新的

序列号。这种情况下的序列号为奇数，以区别目的节点为更新报文分配的序列号

（3）度量值为∞的表项的变化程度足以触发“递增更新”报文的立即发送经过上述过程，在

较短的时间内，该链路的变化将通告到网络的各个节点.

DSDV信息通告举例-链路断

4）路由选择准则

DSDV中路由选择的准则为：序列号新或者度量值小。

将更新信息和节点的路由表对比，选择序列号值大的路由信息，这样就能保证到达目的节点的路由信息是最新的。

当序列号值相等时，选择度量值最佳（例如最小跳数）的路由信息 5）波动抑制

DSDV采取的方法是维护两张表，一是转发表，二是广播表。两张表的操作规则有所区分。广播表以目的节点地址为关键字，表项中设置一个“平均通告时间间隔”字段，该字段是对该表项过去通告时间间隔的加权平均，最近通告的时间加权大。当收到一个新的网络变化通告时，查询广播表的相应表项的“平均通告时间间隔”字段，决定是否进行通告广播。 需要注意的是，收到度量值为∞的通告时，不延迟，立即广播。

在一个单独的表（广播表）中记录每条路由的最近的和平均的SettlingTime Settling Time：第一条路由和最佳路由之间的时间间隔 路由表中的stable data指向该表

A在包含新序列号的第一条路由到达时更新路由表，但是等待一段时间再广播该条路由 等待时间=2*(avg.Settling Time)

可缓解大型网络的路由波动问题，从而避免不必要的公告，节约了带宽

主动路由协议DSDV举例：

主动路由协议DSDV举例：

基于DV算法 简单，易于实现

需要的存储空间小（只须和邻居节点交换路由信息） 确保无路由回路

路由表中的每个表项都带有目的地序列号（由目的节点生成） 对拓扑变化能作出快速反应

路由表有显著变化时立即启动路由公告(Router Advertisement) 但等待不稳定路由的公告,减缓路由波动(damping fluctuations) 先验式（表驱动）路由

节点维护到所有目的地的路由信息 路由信息必须周期性的更新（无休眠节点）

即使网络拓扑无变化也存在着通信开销 维护的路由可能从不使用 DSDV协议的优缺点 优点

简单（基本上与DV算法一致

通过目的地序列号避免了路由循环，解决了DV算法中的计数到无穷问题 无路由发现延时（先验式路由） 缺点

所有节点都必须公告路由，因此不支持休眠（不能直接用于传感器网络） 收敛慢（DV路由的特性）

开销大：大部分的路由信息从不使用

可扩展性是一个主要问题（所有先验式路由都存在的问题）

本文来源：https://www.bwwdw.com/article/e1da.html