路径矢量路由协议 基于DSR的移动自组网多路径路由协议的研究与分析
时间：2019-04-11 03:21:53 来源：柠檬阅读网 本文已影响 人 
摘要：DSR动态源路由协议是一种典型的按需路由协议，它只在有需求的时候才启动路由发现过程，也是目前移动自组网网络的一种主要路由协议。本文阐述了DSR的工作原理并分析了多种基于DSR的移动自组网的多路径路由协议的工作原理与特点。
关键词：DSR协议；移动自组网；动态源路由协议；路由发现
中图分类号：TN929.5 文献标识码：A 文章编号：1007-9599 (2012) 08-0000-02
一、DSR路由协议的定义
动态源路由协议DSR(Dynamic Source Routing Protocol)是一个典型的最早的按需路由协议，非常适合应用在AD HOC网络中。它由两个部分组成：路由发现以及路由维护过程。路由发现过程负责搜寻可能的传播路径，而路由维护过程则维持着已有路由。
二、基于DSR的多路径路由协议
（一）多路径路由的相关概念及特点
什么是多路径路由，即指在源节点和目的节点之间存在着多条可用路径。能够在源节点和目的节点之间确定多条路径的算法，称之为多路径路由算法。多径路由算法可以形成多条路由，并确认其中一条路由为主要路由，其他一条或多条路由为备份路由。执行多路径路由算法的网络即为多路径路由网络。由于多路径路由算法的特点，多路径路由网络与运行单路径路由算法的网路相比，具有分配通信量、平衡网络负载的特点，同时更加稳定、容错能力更强，并且能实现均衡负载。
目前基于DSR的多路径路由协议主要有MSR协议、SMR协议等。本文主要是介绍MSR协议与SMR协议。
（二）MSR(Mu-tipathSoureeRouting)协议
MSR是基于DSR协议的一种多路径路由协议，和DSR协议相比，降低了分组发送延迟，提高整个网络的吞吐率。在路由发现阶段，MSR协议以延迟作为路径规格的度量。并使用主动探测(Probing)的方式和带权重的循环调度(WeightedRoundRobin)算法，来确定多条可能路径。通过多条路径的负载均衡来改善节点的通信质量。MSR是一种按需的，源路由的协议，它只在节点之间需要通信的时候才发起路由发现过程，源路由可以充分发挥多径路由的优点，降低多径通信和计算的复杂性，并通过主动探测的结果来进行合理的分配，达到实现拥塞控制的目的。
MSR采用特定节点对范围上的独立路径算法，MSR独立路径算法的具体步骤如下：
1.设置一个极限跳数，即源节点与目的节点之间最大的节点数。
2.将小于最大跳数的路径构造为成一个有向图。
3.通过采用Dijkstra算法，尝试在有向图中寻找从源节点到目的节点的最短路径，若路径存在，则将该路径加入到多路径表中，同时将图中该路径的中间节点删除，路径数加1否则结束程序。通过独立路径算法获得的若干条最短的独立路径，可以防止了在节点点发生拥塞，实现多路径的负载平衡，并且不会增大数据包的传输延迟，保证良好的数据传输效率。
（三）SMR（Split Multipath Routing）路由协议
除了MSR算法，SMR-分裂多路由算法分裂多路由算法也是基于DSR路由算法的。在该算法中，中间节点可以接受从重复的从源节点发送过来具有相同RREQ ID的RREQ包，而在DSR算法中，这是不允许的，DSR算法的这种机制极大的降低了寻找最大不相关多路由的可能性。
1.SMR算法的路由发现过程
在SMR算法的路由发现过程中，中间节点接收重复的RREQ包(即从同一个源节点发来的具有相同RREQ ID的RREQ包)并筛选，如果该RREQ包是从不同的前一节点发送过来并且该RREQ包中路径的跳数小于或等于先前收到的RREQ包中的跳数，则接受这个RREQ，并进行处理，然后转发，反之，则将这个RREQ丢弃。
SMR算法在选择路由的过程中，目的节点首先选择最早收到的RREQ中的路径作为主路由，然后设定一个计时器，在计时器未清零的情况继续接收RREQ包，并从中选定一条与主路径不相关性最大的一条路径作为备选路由。但是这种机制导致必须要发送大量的RREQ包，这极大地增加网络的负担，而且最后形成的主路由与备选路由之间仍然存在着路径重叠的现象。
2.SMR算法中的路由维护
在无线网络中，特别是AD HOC网络，节点的移动性非常大，网络的拓扑结构可能会经常变化，链路因节点的移动、网络拥塞等原因可能会断链。因此在多路径路由算法中，路由维护过程是非常重要的，因为它关系到如何快速的恢复中断的路由。在SMR协议中，当一个节点如果判定与下一个传输节点失去了联系，则会朝路由上行方向发送一个路由错误分组(RERR)分组。在RRER分组中包含了到达源节点的路由、断链的紧邻上行节点和紧邻下行节点的信息。当源节点接收到RERR分组后，根据RRER分组中所携带的信息更新路由表，将和该条中断链路有关的路由全部删除。如果路由表中，还有有效路由，则源节点将使用该有效路由继续传递数据分组。
当一条路由中断以后并且被源节点知晓，源节点可以采取以下两种策略中的一种重新寻找路由。
(1)只要任何一条路由发生了中断，则开始路由发现过程；
(2)当主路由与备份路由全部发生了中断，才开始路由发现过程。
第一种方案由于需要重建路由，因此其控制开销要高于第二种方案，但是保证在任何时候都能提供多条路由，具有较强的抗路由中断能力。
三、基于DSR的多路径路由协议存在的问题
目前，在对移动自组网络的研究中，基于DSR的多径路由研究是一个热点，并且取得了很大的进展，但是仍然存在这一些问题。主要表现在以下几个方面：
（一）流量的并行传输问题：如何权衡多条路径之间的使用比率，实现负载均衡，以提高网络资源的利用率和信息传输流量。
（二）路由协议适应移动自组网络环境问题：移动自组网由于其特性，网络状态不稳定，路由协议如何适应不同节点移动速度、数据传输率和端到端延时的变化。 （三）可靠性问题：并行多路径涉及数据分组的分配和可能的分割和重组，这就存在分割优化问题。多路径并行传输还会引入报文传输乱序问题，需要提供差错控制和顺序控制，提高多路径并行传输的可靠性。
（四）路由可扩展性问题：移动自组网的应用越来越广发，规模也越来越大，如何提高路由的可扩展性。
（五）QoS支持问题：虽然在网络拓扑结构变化较小的情况下，TBP提出了基于令牌方式的多路径QoS支持来适应，但支持高速动态网络QoS多路径路由仍是该领域所面临的一个挑战。
（六）能量的控制问题：如何减少开销，如何节约能量。总之，移动自组网的基于DSR的多径路由协议应考虑到如下因素：分布式运行、QoS保证、组播功能、无环路由、按需进行协议操作、对单向信道的支持、节能策略、可扩展性、安全性和可靠性等。
参考文献：
[1]Broch J, Maltz D A, Johnson D B. A Performance Comparison of Multi-Hop Wireless Ad Hoc Newwork Routing Protocols. In: Proc of the 4th International Conference on Mobile Computing and Networking. Texas: Dallas,USA, ACM Press, 1998: 85-87
[2]Hu Y C, David B. Johnson.Implicit Source Routing in On-Demand Ad Hoc NetworkRouting. In：Proc of the 2nd Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), California,USA, ACM Press, 2001:1-10
[3]孙宝林,李腊元.Qos动态多播路由协议.小型微型计算机系统,2005,26(11):1877-1880
[4]Karnp. MACA: A New Channel Access Method for Packet Radio. ARRL/CRRL Amateur Radio9th Computer Networking Conference,1990,(8):1558-1567
[作者简介]
李悦（1977-），男（汉族），湖南长沙人，长沙师范学校讲师，从事计算机网络
湖南省普通高等学校科学研究项目 《基于DSR的AD HOC网络多路径路由协议的研究》 主持：李悦 研究年限：2011-2013 基金编号11C0098
