无线Mesh网络移动自适应多径路由协议

1、无线Mesh 网络移动自适应网络移动自适应多径路由协议多径路由协议张鹏，廖青北京邮电大学，北京 （100876）E-mail:摘 要： 由于无线Mesh 网络具有高移动性和链路失效率，从而导致整个网络的吞吐率下降和端到端时延的增加。多径路由的提出就是为了减少链路失效造成的路由开销，现有的多径路由协议大多在路由发现过程中预计算多条路由路径，但由于缺乏对备用路由的维护，所以无法支持节点的高移动性。因此，为了解决这个问题，我们提出了一种新型的多径路由协议（MP-AOMDV ），通过引入周期性的路由更新数据包对不同路由路径进行维护，保证了任意时刻最佳路径都能作为用于传输数据的主路由路径。本文中，我们跟

2、现有的两种多径路由协议进行了比较，仿真结果表明MP-AOMDV 对于整个网络的的吞吐率有显著的提高，降低了端到端时延，提高了对节点移动性的的支持。关键词关键词：Mesh 路由 多径路由 AODV中图分类号中图分类号：TN915.041. 引 言无线Mesh 网络是移动Ad-Hoc 网络的一种特殊形态，它具有高节点移动性，低信道带宽和能量约束等特点。在这种条件下，面临的关键问题是如何在动态环境中花费最小并达到尽可能高的吞吐率。目前针对Ad-Hoc 网络所提出单径路由协议分为两种：a 先应式路由协议一个典型的先应式路由协议是目的序号距离向量协议（DSDV ）。它基于传统的距离向量路由机制，同时它也

3、被称为消除了路由环路的Bellman-Ford 路由算法。距离向量算法的主要工作机制是这样的，每个路由器从它的邻居获得路由信息，然后根据这些路由信息计算出到网络其他接点的最短路径。当计算出一个新的路由表时，路由器把这个新的路由表广播给它所有的邻居。这样就可能促使它的邻居邻居重新计算路由表，直到整个网络趋于稳定。DSDV 进行了改进，通过序列号来区分新就路由信息以消除路由环路。每个移动主机都有一个单调递增的序号表，每当主机给他的邻居发送一个路由更新信息的同时就给序号增加一个单位，当旧路由的目的地序号小于新路由或者两者相等但新路由具有较小的花费时，旧路由就被替换掉。b 反应式路由协议反应式路由协议

4、是一种需求驱动的路由协议，这种路由协议仅仅在需要的时候才去发现和建立路由。比较典型的有源主机路由协议（DSR ）和Ad-Hoc 按需距离向量协议（AODV ）等。一个值得注意的问题是，虽然AODV 在建立路由的过程中会发现多条路由路径，但是目的节点只会选择在最优的路径上建立路由，而舍弃其他的路径。在这种情况下，因为没有备用路由，节点的高速移动就会导致路由频繁失效，从而使中间节点产生丢包，由丢包产生的路由发现次数的增加也必将导致端到端的时延和丢包率的增加以及整体吞吐率的降低。目前的一些多径路由协议13试图通过在路由发现过程中缓存多条路由路径来解决这个问题。在这些路由协议的路由建立过程中，预先计算

5、好的多条路径作为备用路由路径被缓存起来，从中选择最佳的路径（一般是跳数，ETT ，ETX 最小的）做为主路由路径，其余作为备用路径，当主路由路径失效时，就使用备用路径。但是，在这些协议中，并不对备用路径进行任何路由维护。由于缺乏对备用路径的维护，我们无法确定主路由路径失效时，备用路由路径是否可用，而采用这样不可靠的路由带来的结果可能会导致新一轮的路由切换或者路由发现过程。这也将影响整个网络的性能。为了解决这个问题，本文中提出了一种新的多径路由协议MP-AOMDV （Mobility Prediction AOMDV ）。在MP-AOMDV 中，我们在每个路由路径上都周期性的发送单播的路由维护数

6、据包对路由路径进行重新验证，同时尽量减少路由维护数据包带来的控制信息开销以提高性能，由于路由维护数据包中还包含了每个路径的状态信息，网络节点可以根据这些状态信息来选择最好的路由路径来进行数据传输而不必等到主路由路径失效时在进行路由路径的切换。因此，在MP-AOMDV 中源节点总是能够在备用路由路径中选择最佳的路由路径发送数据。本文剩余部分组织如下：第二部分介绍多径路由方面的相关工作，第三部分详细介绍MP-AOMDV 协议的细节和流程，第四部分是MP-AOMDV 协议的仿真结果以及和其他协议的比较，最后一部分是总结。2. Mesh 网络中的多径路由协议目前存在的多径路由协议例如AOMDV 3，A

7、ODV-BR 4，都是基于AODV 协议的。在文献3中，通过修改AODV 的路由发现过程，在源节点，目的节点之间计算多条链路独立的路径，目的节点只在这些链路独立路径上返回RREP 包，这样网络中每个节点中都有一个多条路由路径的路由表。如果在通信中某一段链路突然失效了，这条链路的上游节点会迅速切换到其它路由，当这个节点没有备用路由可以切换的时候，它就向它的上游节点发送一个RERR 包。源节点只有在所有路由都失效的情况下才会从新发起一次新的路由请求。这种协议的主要缺点是路由建立之后就不对备用路由路径进行任何得到维护，这样备用路由就无法真实反映网络拓扑的变化，这个问题在节点移动速度较快的时候表现的尤

8、为突出。在文献4中，作者提出了一种新的计算备用路由路径的算法，这种算法要求网络中所有节点都工作混杂模式，每个节点都可以监听自己覆盖范围内其他节点的数据包，当网络中某个链路失效时，失效链路的关联节点就在周围搜索可替代的新的路由路径。虽然这种算法理论上是可行的，但是它是有很大局限性的。首先，它假设每个节点周围都有一些其它节点，这些节点的移动也没有被考虑，并且为失效链路提供替代路由的节点也被假设为静止的。其次，节点工作在混杂模式会大大增加节点的功耗，并且还有数据隐私问题。其它的路由协议如DSR ，由于在路由的发现过程中，就已经产生了多条路由路径，通过缓存这些路由路径可以实现多径路由。主路由路径失效时

9、，源节点就切换备用路由路径进行数据传输。这种算法在节点移动性较强的环境中，工作效率表现不高，因为网络拓扑的变化，备用路由由于缺乏更新，很可能在切换到备用路由之前，这条路由路径已经失效（文献6给出了这种算法的详细分析）。文献5中，作者提出了一种分布式的无回环的路由协议TORA ，这个协议是基于拥塞算法来计算多路由路径，以达到缓解链路的拥塞问题。但是这种算法对控制消息的可靠性和有序性要求过高，不易实现。还有一些多径路由协议，如AMSR(Adaptive Multipath Source Routing是在DSR 协议的基础上进行扩展，通过测量得到的RTT 作为路由判据，把负载分担到多个不同的路径上

10、。而ROAM(Routing On-demand Acyclic Multipath协议是另一种基于拥塞算法的路由协议，但由于在路由发现过程中，节点之间需要一直协商状态信息。这显著增加了网络中的控制信息开销，所以ROAM 更适合在有线或者变化较慢的网络环境。文献9中，作者提出了一种新的按需路由协议SMR(Split Multipath Routing，文中提出了一种计算路径不相关的算法，通过计算源节点到目的节点之间所有的不相关路径，可以避免链路拥塞，并且可以充分利用网络资源。SMR 是基于DSR 协议的另一个版本，也是在路由发现的过程中，预先计算出多条路径，并缓存起来作为备用路由路径。通过对以

11、上的多径路由协议分析，可以看出，大多数的多径路由协议都缺乏对备用路由的维护，因此，我们提出了一种可以验证备用路由信息的新鲜度的方法，这样在切换路由之前，可以确保切换后的路由是正确并且是可靠的。3. MP-AOMDV ：一种具有一种具有节点节点节点移动性预测的自适应路由移动性预测的自适应路由移动性预测的自适应路由协议协议首先介绍一种信号稳定适配协议（SSA ），SSA 试图建立基于信号强度和方位稳定性考虑的生存期比较长的路径。根据数据包侦听到的平均信号强度，每条链路都可以划分为强信号的或者是弱信号的。每台主机都周期性的给它的邻居发送信号来检测其稳定性。这个协议最后将选出一条生存时间最长的路径。在

12、本文提出的协议MP-AOMDV 中，将采用路径信号强度作为路由判据，通过累加一条路径上所有链路的信号强度来决定路由路径。虽然大部分的协议都把跳数作为路由判据，但是在度量路径的稳定和链路的质量上，跳数都无法充分的反映这些信息。一个信号强度很弱的路径，尽管跳数很小但也会导致丢包率的上升，相反，如果采用路径信号强度作为路由判据，因为路径信号强度是包含了路径上每个链路的信号强度信息，综合考虑了整个路径的链路质量和稳定性。假如某一个链路信号强度很弱，也将导致这条路由路径的路径信号强度很低，从而这条的路由路径的优先级也就相应降低。文献13中详细讨论了采用跳数作为路由判决带来的问题。下面，我们将讨论MP-A

13、OMDV 的细节，首先我们将介绍一个关于路径的基本概念。 在多径路由中，路径可以分为节点无关路径（Node-Disjoint ）和链路无关路径（Link-Disjoint ）。节点无关路径指两条路径上除了源节点和目的节点外没有一个节点是相同的。链路无关路径是指两条路径上的链路都各不相同，节点是否相同不受限制。由于节点无关路径比链路无关路径要求要更加严格，因而计算出来的备用路由的数目也比链路无关路径的情况下的少的多。相比之下，计算链路无关路径在大多数的应用场景中显得更为有用，因此，我们主要研究MP-AOMDV 的链路无关路径的多径路由。在MP-AOMDV 中，链路无关路径的发现是基于AOMDV

14、3之上改进的。在MP-AOMDV 的路由发现过程中，当一个中间节点收到多个RREQ 时，它只转发其中最好的那个RREQ 数据包，其余的只作为备用路由信息添加到本地路由表中，同时节点还会根据收到的RREQ 包维护一个上游邻居节点队列。目的节点在收到RREQ 数据包后就会回复一个RREP 数据包，中间节点收到RREP 后，根据上游节点队列，把RREP 数据包转发给上游节点，并把这个上游节点从队列中移除，一直到队列为空就停止转发RREP 数据包。这种转发机制保证了中间节点转发的RREP 包都是在不同的上游链路中。如果上游链路队列序号和下游链路队列序号不一致，那么这条多余的链路也是不会被采纳的，因此每

15、个中间节点都对上游链路和下游链路做了一对一的映射，并保存在一个列表中，基于这种机制，每个节点都维护了一个备用路由表。因为目的节点只根据收到的RREQ 向对应的上游节点发送RREP 包，并且中间节点在转发RREP 数据包时，只向对应的上游邻居转发，因此，源节点发现的这些路由路径都是链路无关的。 跳信息（Heartbeat Message），路径上的每个节点在转发更新包之前都要在更新中加入自己的MP 值（Mobility Prediction metric ）。其中，MP 是通过测量节点和上游节点之间的相对信号强度得出的，算公式如下：minmin P P P MP AB = AB P 是节点A 收到节点B 数据包的信号强度，min P 是能正确接受数据的最低信号强度，MP 反映了单向信号强度的信息。源节点首先初始化更新数据包中的MP 值，路径上的节点在收到更新数据包后，把自己的MP 值累加到数据包中，直到目的节点收到后并返回源节点。所以更新数据包中的MP