龚晓霞，王建新
摘 要：由于移动自组网中的节点可以任意的运动，导致网络中传输路径的频繁断裂，大量的重路由操作降低了网络性能，并占用了有限的网络资源。而基于预测的路由协议能够有效地减少网络拓扑结构的变化对于路由操作的影响。文章主要讨论了目前已经提出的几种节点运动预测方案，以及基于预测的路由协议，并提出了进一步的研究方向。
关键词：移动自组网；运动预测；路由协议；传输路径
1 引 言
移动自组网是一种新型的特殊网络，他不依赖于存在的固定网络设施，能够快速展开自治的、多跳的网络结构，他由一组带有无线收发装置的节点组成。网络中的每个节点能够快速运动，并且同时具有主机和路由器的功能。对于原本不存在基干网的区域或基干网已被破坏的区域，或虽存在基干网但并不方便使用的区域，传统的无线通信网已经不再适应，但移动自组网却能满足这些特殊情况下的通信需求，迅速建立一个新网络以实现数据传输，他可被广泛应用于军事、救灾等各种需要临时建立通讯网络的场合。
移动自组网中由于没有用于路由的固定网络设施，并且使用无线传输技术，具有带宽有限、通讯质量低等特点，同时无线传输的范围受到节点能源的限制、频道的影响以及频繁的重用。同时由于网络中的每个节点都可以相互独立的自由运动，这样在路由过程中已经建立的数据传输路径经常由于节点运动而断裂。当某个路径在使用过程中断裂时，就需要建立新的路由，找到相应可用的路径来恢复数据传输。这些重路由操作极大地消耗了移动自组网有限的网络资源和节点的电力能源，也容易造成网络的拥塞，同时重路由所带来的传输延时，极大地影响了对网络应用的服务质量，从而降低了网络的运行性能。所以在这样的网络中选择一条最可靠、最优的路径，最大限度地减少重路由操作，减少网络拓扑结构的动态变化对路由操作的影响，具有非常重要的意义。
为了减少网络拓扑结构的变化带来的重路由操作，寻找一条最为稳定的路径就成了关键，而路径的稳定性依赖于组成这一路径的所有链路的稳定性，所以为了确定路径的稳定性，首先要确定各个链路的稳定性。如何利用节点现有的运动信息预测节点在将来某个时刻的运动状况就成了预测链路稳定性的关键。假设某一传输路径P＝｛L1，L2，…，Lk｝是由L1，L2，…，Lk k条链路组成，f(Li)表示链路Li的稳定性，F(P)表示传输路径P的稳定性，则：
F(P)＝f(L1)f(L2)…f(Lk)
在通常情况下，节点的运动类似于人的运动，或者是按照一定的规律，一定的模式运动，或者是随机运动。同时每个节点可以保存各自运动的历史记录，以及当前的运动状况，根据节点的运动历史记录和节点性，提高数据传输的可靠性，并减少重路由的发生。
2 预测模型
链路预测包含2个阶段：
(1)节点运动状态信息的获取。在进行链路预测前，通过信息获取协议取得节点运动的状态，例如节点位置、节点运动速度、节点运动方向等。
(2)运用链路预测方法进行链路状态计算。链路预测的前提是节点的运动基本符合某种运动模型，对于完全随机的运动是无法预测的。
目前已经提出的关于链路预测的策略主要有4种：链路可用性模型、传输链路保持连接时间的预测模型、基于预测的链路可用性估测模型以及节点位置预测模型。
2．1 链路可用性模型
链路可用性模型［1］建立在随机行走模型(Random Walk - based Mobility Model)的基础上，该运动模型具有以下特点：每个节点的运动都由一系列随机长度的运动间隔(Mobility Epochs)组成，在每个运动间隔上节点的运动速度vni和方向θni都保持不变。在时间t上，运动间隔的数目N(t)是一个独立的随机过程。
节点n的运动用＜λn，μn，σn＞来表示：运动间隔的长度Tni服从λn－1的IID的指数分布；速度服从均值为μn，方差为σn的IID的随机分布；方向θin是在［0，2π］上的IID的均匀分布；运动间隔的长度与vin和θin无关联；节点运动不相关联，链路的断裂相互独立。
在该运动模型的基础上，可得到单个节点n的运动在一段时间t上的运动距离D(t)的规律，然后可预测得到D(t)小于节点通信距离r的概率。考虑2个节点的联合运动，将其转化成一个节点相对于另一个节点的运动，则可以得到一个节点相对另一个节点在一段运动时间t上的运动距离Dm，n(t)的变化规律，并依据他的变化来预测他小于r的概率。
假设节点的传输范围是半径为r的圆，考虑某链路L(m，n)，假设在t0时刻可用，则在t0＋t时刻该链路可用的概率表示为链路可用性。根据最初的状态和m，n的位置，链路可用性的预测分为2种情况：节点激活状态(Node activation)，即t0时刻m在n的范围之内活动；链路激活状态(Link activation)，即t0时刻m运动到距离n的r边缘。定义Z为一个节点按随机方向到达另一节点的r边缘所需运动的距离。所以链路可用性可以表示为：
以上2种情况下，可以分别预测出链路的可用性。
2．2 链路保持连接时间的预测
在某时刻节点i，j之间可直接通信，节点的传输范围为r。节点i：位置(xi，yi)，速度vi，方向θi；节点j：位置(xj，yj)，速度vj，方向θj。假设节点的运动状态保持不变的情况下，计算2个节点之间的距离，若小于节点通讯的范围则可以保持连接，以此来预测节点i，j 保持连接的时间LET(Link Expiration Time)［2］为：
2．3 节点位置的预测
根据节点运动状态信息中是否包含运动方向θ，分为两种情况进行预测［3］。
(1)若运动状态信息中包含运动方向θ
某节点n在t时刻，运动速度为v，运动方向为θ，位置为(x，y)，若假设节点的运动状态保持不变，则可以预测节点n在将来某时刻tp的位置为(xp，yp)：
(2)若节点运动状态信息中不包含运动方向θ
由于某节点n没有运动方向信息，则需要用到最近两次更新信息表所保存的运动信息来预测节点n在未来某时刻tp的位置(xp，yp)。假设节点的运动状态在最近的两次更新之后运动方向没有发生变化，则可以根据两次的运动情况预测节点的位置：
t1时刻：节点n的位置为(x1，y1)；
t2时刻：节点n的位置为(x2，y2)，速度为v，t2＞t1；
分别为最近两次从目的节点n到相应源节点的最新信息。则：
2．4 基于预测的链路可用性模型
基于预测的链路可用性模型［4］的基本思想是，一个节点首先预测一个连续时间区间Tp(Tp为假设在2个节点的运动都不变的情况下，目前可用的链路从t0开始可持续的时间)，然后再考虑t0与t0＋Tp之间，在2个节点运动可能发生变化的情况下，预测该链路持续到t0＋Tp的概率L(Tp)：首先假设运动间隔(某节点保持运动状态不变的时间区间)的长度服从λ－1的指数分布，即E(x)p｛Epoch length≤x｝，且各节09点的运动无关联。
考虑2个节点的运动是否发生变化，可得到L(Tp)＝L1(Tp)＋L2(Tp)，其中L1(Tp)表示在2个节点运动均不发生变化的情况下，链路在t0＋Tp时刻仍可用的概率，L2(Tp)表示2个节点中任一节点运动状态发生变化情况下，链路在t0＋Tp时刻仍然可用的概率。根据E(x)的概率分布规律可以分别预测出L1(Tp)和L2(Tp)的概率，即可得到链路保持到t0＋Tp仍然保持连接的概率。
3 基于预测的路由协议
一种新的移动自组网的组织结构─基于运动框架模型的自适应分簇算法应用了链路可用性的预测方案。他使用链路可用性的预测方案将网络中的节点进行自适应分簇，给定参数(a，t)，一个簇内的节点在当前时刻t0是可以相互到达的，在t0＋t时刻相互之间的链路可靠性要大于或等于a，根据这一条件来自动调整簇内的节点。路由时分为2种情况，簇内的节点按照通常的表路由，查找路由表中存在的路径进行数据传输。如果是一个节点要向另一个簇中的节点发送数据，则采用按需路由，发送路由请求，直到目的节点所在簇的任意节点接收到请求，即可返回源节点，建立传输路径。这种路由协议由于采用了链路的可用性来作为分簇的判断参数，极大地增加了簇内节点之间的稳定性。并且根据相近节点数据传输更加频繁的实际应用情况，这一算法极大地提高了数据传输的可靠性，并减少了路由开销。
具有移动预测的距离矢量协议DV-MP和QRMP采用了也采用了RET(Route Expiation Time)作为在路由表中选择路由的决定参数，首先他预测各个链路保持连接的时间LET(Link Expiation Time)，一条路径的RET则由这条路径上所有链路的LET的最小值来确定。目的节点在确定建立路径时，总是选择具有最大的RET路径，这就保证了源节点在传输数据时总是在最稳定的路径上进行，以最大限度地减少由于运动引起路径断裂所造成的传输失败，极大地提高了数据传输的可靠性。
在多播路由协议ODMRP(On -Demand Multicast Routing Protocol)中也采用了该预测方案，一个多播的接收节点对路径的选择是基于路径的稳定性的，也就是具有最大的RET的路径。为了选择这样的一条路径，接收节点必须从接收到第一个表(Join Table)开始，等待适当的时间，以获得所有可能的RET和路由信息，然后选择最稳定的路径。
在移动自组网中用于实时数据流(如图形和声音)路由的协议─FORP(the Flow Oriented Routing Protocol)，也采用了预测LET的策略，其基本思想是首先预测路径上每一跳的LET，然后根据这条路径上最小的LET确定RET。在移动性很高的环境中，FORP能在吞吐量降低到最小的情况下，有效地保持较小的延迟，同时他还能够最大限度地减少控制信息的开销，并且采用了预测链路存活时间的方法，选择最稳定的路径保证实时数据流的可靠性。因此FORP适用于移动自组网中的实时IPv6流的传输。
在应用了节点位置预测的属于源路由的QoS路由策略中，在这类路由算法中，任一个节点n都具有网络中每个节点的信息。节点n上保存的状态信息由更新信息表(update table)和路由信息表(routetable)组成。当一个更新的信息到达节点n时，首先检查路由表中的所有路由是否已经断裂，或将要断裂。无论哪种情况，都要重新计算路由。由于使用了基于更新信息的节点位置预测，可以预测出某个路径上的所有临近节点是否会相互运动到各自的传输范围之外。所以，重路由的操作可以在路由真正断裂之前开始，在路由即将断裂之前重新建立新的路由。这样采用节点位置预测之后，重路由操作在路由断裂之前就已经完成，极大地减少了由于路由断裂带来的数据丢失，可以有效地提高服务质量，减少了在传输过程中由于路径断裂所造成的不良影响。
4 进一步的研究方向
在移动自组网中节点可以相互独立的自由运动，但是网络中任何节点的运动都是服从于应用的需要，这就决定了节点的运动是和具体应用相关的，而且具有一定的运动特性，与人类的运动相似，总是具有一定的规律性和目的性，建立在一定的运动规律之上。
首先在分析节点运动规律的基础之上，抽象出对节点运动的描述，即用一组参数描述节点的运动规律，能够描述其重要的运动特点，以便对节点的运动进行预测。如果可以用数学模型对节点的运动进行精确的描述，在该数学模型的基础上建立预测机制，进行网络链路连接状态的预测。或者在节点运动历史信息的基础上，预测节点在将来某一时刻的运动状态。然后在运动描述的基础上建立对运动节点的预测，这就突破了节点运动必须符合某种运动模型的限制，有效地扩大了预测机制的使用范围，同时尽量提高预测的准确性。最后把对于节点的预测机制运用到路由协议之中，以达到减少重路由操作，提高网络的运行性能的目的。
进一步的研究工作包括：基于具体应用的预测模型的建立和分析；节点运动数学模型的建立和分析；网络链路信息获取与预测机制的关系；基于预测的网络通信协议等。
5 结 语
文章讨论了现有的几种关于节点运动的预测方案，以及基于这些预测机制的路由协议。基于预测的路由协议能够有效地减少网络拓扑结构变化导致的重路由操作，提高移动自组网中传输路径的稳定性，为移动自组网的应用提供了进一步的保障，而基于应用的节点运动的预测是下一步工作的重点。
参考文献
［1］Bruce McDonald A ，Taieb Znati ．A path availability model for wireless Ad - hoc networks ．In Proceedings of IEEE Wireless Communications and Networking Conference 1999(WCNC′99)，New Orleans ，LA，September 21-24，1999．
［2］William S ，SungJu Le ，Mario Gerla ．Mobility prediction and routing in Ad- hocwireless networks ．International Journal of Network Management，2001，11：3-30．
［3］Shah H ，Nahrstedt K ．Predictive locationbased QoS routing in mobile Ad-hoc Networks．In Proceedings of IEEE International Conference on Communications(ICC2002)，NewYork，NY，April 2002．
［4］Shengming Jiang ，He D J ，Rao JQ．Aprediction－based link availabilityestimation for mobile Ad-hoc networks ．IEEE INFOCOM 2001．
摘自 现代电子技术
|