（通信与信息系统专业论文）移动性ip网络组播理论与技术研究.pdf

北京交通大学博士论文第l 章绪论 1 1引言 第1 章绪论 近年来，随着移动i p 【1 捌技术的逐渐成熟，越来越多的人们开始通过移动l p 设备接入到互联网中，以便在运动的过程中对网络进行访问。相对于没有基础设 施的网络( 如m a n e t ，m o b i l e a d h o c n e t 、o r k 【m 】) 来说，在具有基础设施的网 络中，移动用户的移动形式可以分为个体移动和群体移动两种。在个体移动中， 终端的移动是个体行为，其与网络接入点问的连接是由移动终端进行维护的；而 在群体移动中，根据i e t f n e m o q 里w o r k 丛o b i l i t y ) 【7 定义的框架，其移动终端 和子网组成的移动整体与网络接入点之间的连接是由移动路由器( m r ，m o b i i e r o u t e r ) 来维护的，所以又称之为移动性i p 网络，简称移动网络。但需要指出的 是，在相对集中的移动终端整体移动时，如果各个移动终端还是分别与网络建立 连接，则仍然属于个体移动的范畴。 移动网络的主要应用形式包括唑个人网络( p a n s ，p e r s o n a l a r e a n e 柳o r k s ) 、 部署在交通工具上的传感器或计算机网络、部署在公共运输工具( 如公共汽车、 火车、出租车、飞机和轮船等) 上的接入网络、通过移动路由器接入互联网的 a dh o c 网络和军队的战斗单元接入军事网络等。 互联网络技术领域中的另一+ 个具有革命性的技术是i p 组播技术“。i p 组 播是一种优化使用网络带宽的路由技术，它允许i p 数据流从一个数据源或多个 数据源发送到多个数据接收目的地。采用组播技术，可以避免不必要的数据包复 制，减少骨干网络的数据流量。 移动网络以无线技术为接入手段，具有随时可能改变其附着的网络服务点的 特点，该特点使得对移动网络所处位置的跟踪、保持连接和数据传输持续性等成 为急需解决的关键问题【1 “。这是因为在蜂窝网络中，虽然已经提出了多种有效的 移动性管理方法i l ”，但由于i p 网络具有许多与蜂窝网络不同的特征，因此解决 i p 层面的移动性管理和通信持续性的问题就不能延用蜂窝网络的方法；此外， 目前的2 g 和3 g 系统等无线网络还无法提供对组播机制的有效支持【1 4 1 ，故i p 组 播仍将是支持点到多点和多点到多点应用的有效手段；特别是对于下一代网络来 说，i p 协议将在网络层对各种有线无线技术进行融合，因此i p 组播必须能够适 应移动网络的要求。 研究如何把i p 组播技术与移动网络进行结合对r p 组播提出了新的挑战。目 前使用的i p 组播协议，如d v m r p 【1 5 】、m o s p 一6 1 、p i m s m f l 7 】和c b t 等，都 是在假设组播接收者和发送者的位置固定不变的前提下提出的，它没有考虑节点 北京交通大学博士论文第1 章绪论 在移动中发送和接收组播数据的情况，因此无法解决当节点位置发生改变后如何 还能够对组播数据进行接收的问题。 当前对移动组播的研究主要是针对解决组播接收者以个体方式移动中组播 通信的持续性问题的，并且提出了许多方法。现有的方案如m i p b t 【1 翔、 m i p r s 、m o m 【19 1 、r b m o m 【2 0 】、m o b i c a s t 【2 l 】和m m a 【矧等大多存在着三角 路由、隧道聚集、切换时延过长和丢包过多等问题【2 3 1 。虽然存在问题，但在移动 i p 组播问题的研究上还是进行了许多有益的探索，并且取得了一些重要成果。 关于移动网络组播，目前研究的还比较少。由于移动网络具有整体运动的特 点，当发生接入点切换时，移动网络内部的终端和子网的通信将全部受到影响。 移动网络的这一特点，以及移动网络通过移动路由器与互联网连接的通信方式， 使得用于单个移动终端的移动组播协议根本无法满足终端整体移动的要求。 为了解决上述问题，本论文对移动网络中有关i p 组播的一些关键理论和技 术问题进行了研究。 1 2 论文选题背景与意义 1 2 1 选题背景 i p 组播是2 0 世纪9 0 年代初期发展起来的互联网路由技术，最初是专门针 对点到多点的数据传输设计的。随着无线技术的发展，人们也把对i p 组播的研 究转向了朝着如何支持移动的方向上发展。下面对当前i p 组播、移动i p 组播和 移动网络上的i p 组播的研究内容与发展现状进行简要综述。 ( 1 ) i p 组播 传统的i p 网络是典型的点到点通信模式，因而所用的传输协议是为完成点 到点的通信而开发的。对于点到多点和多点到多点的应用，传统的单播技术会带 来网络资源的急剧消耗、网络拥塞和网络延时等问题。在“固定”的i p 网络中， 解决这一问题的有效技术就是i p 组播技术仉15 砌“五6 1 。 所谓i p 组播( i p m u l t j c a s t ) ，就是指把数据发送给网络上指定的一组接收者 【2 7 】，它与向单个接收者发送数据( 单播：u n i c a s t ) 或向一个给定网络上的全部接 收者发送数据( 广播：b r o a d c a s t ) 的机制不同。在理想的状态下，组播的发送者 只需要对每一个数据包发送一次，所有接收者就能够收到该数据包。而且在每一 条物理链路上最多只有该数据包的。个拷贝被传送【2 。也就是说，在组播中，只 有加入组播组的接收者和处于组播路径上的路由器才能够接收到组播数据。i p 组播通过维护一个组播树，把争个数据流发送给多个接收者，这一机制大大减少 北京交通大学博士论文 第l 章绪论 收或发送过程中的位置的变化。在移动i p 中，组播接收者可能是移动节点，节 点的移动会造成组播树管理和维护的混乱，不但给组播服务带来多余的开销，还 会加重网络的负担。移动给组播协议带来的问题有以下几个主要方面： 目前的i p 组播协议无法适应节点移动性的要求，因为节点的重新加入 加重了组播树维护的负担； 移动i p 本身的切换时间过长，再加上组播加入的时延，无法满足组播 应用的需求； 切换会导致组播数据产生丢包和数据包重复转发的现象； 在基于移动i p 远程加入的组播中，移动节点在子网间的切换会造成组 播树的频繁重构； 基于移动i p 双向隧道的组播协议存在严重的三角路由和隧道聚集问题， 如图1 1 所示。 m n l m _ n 2 h a ：h o m e a g e n t 家乡代理m n ：m o b i l e n o d e 移动节点 a r ：a c c e s sr o u t e r 接入路由器 图l - 1 基于m i p _ b t 移动i p 组播的三角路由和隧道聚集 支持移动用户的接入是互联网发展的必然目标。i e t f 的m o b i l el p 工作组提 出的移动i p 1 技术为这一目标的实现制定了基础性的标准。在移动i p 的基础上， i e t f 提出了针对移动i p 组播的两种基本方案，即m i p - b t ( 双向隧道) 和m i p - r s ( 远程加入) m 。这两种方案在与移动i p 机制兼容的条件下实现了移动i p 组播， 但仍存在着较大的缺陷。由于m i p b t 使用了移动节点与家乡代理之间的隧道来 获得数据，并通过家乡代理加入组播组，由此造成了严重的三角路由问题，特别 是当移动节点远离家乡代理时，组播路由变褥不够优化。此外，当来自同一个子 网的组播接收者进入同一个外地子网时，会分别建立到家乡代理的组播隧道，导 致隧道聚集，从而降低了组播机制在数据传输中的优势。采用m i p r s 机制的移 动节点在每一次改变所附着的网络后，都会重新通过外地网络中的路由器再加入 组播。当节点在子网间切换时，离开并重新加入组播组的行为会造成组播转发树 的更耨，因此这种频繁的切换严重地影响了组播树的稳定性，并会给组播接收者 带来较大的时延，导致较多的数据包的丢失。此外，当组播源是移动节点时， 北京交通大学博士论文 第l 章绪论 ( 3 ) 移动网络 虽然i e t f 的m l pv 4 和m i p v 6 都提供了对移动节点无缝连接性的支持，但 当移动节点组成移动网络时，并非移动网络中的所有节点都能感知链路层的切 换，因而m i pv 4 和m i p v 6 均不能满足这种需求，进一步地，并非移动网络内的 所有节点都支持移动协议【4 4 1 。基于这些原因，i e t f 开始在i p v 6 的基础上对移动 网络进行研究。 i e t f 的n e m o 工作组定义的移动网络是指能够移动并且能够附着在路由结 构中任意点上的一个网段或子网【7 4 5 1 ，其通信模型如图1 2 所示。图中移动网络 节点( m h n ，m o b i l e n e t 、v o r k n o d e ) 和来自其它子网的访问移动节点( v m n ， v i s i t i n gm o b i l en o d e ) 通过移动网络的移动路由器( m r ，m o b i l er o u t e r ) 附着 在固定网络的接入路由器( a r ，a c c e s sr o u t e r ) 上。 h a ：家乡代理 c n ：通信对端 a r ： 接入路由器 m r ：移动路由器 l m n ：本地移动节点 v m n ：访问移动节点 l f n ：本定固定节点 n e s t e dn e t 、v o r k ： 嵌套 图1 2n e m 0 的移动网络协议 n e m o 对移动网络的基本支持协议【7 1 是对移动i p v 6 协议( m i p v 6 ) 】的扩展。 根据该协议，m r 在其附着点上，并不向基础网络发布移动网络的路由，而是通 过与其家乡代理问的双向隧道，由家乡代理向基础网络通告移动网络的聚合信 息，发布移动网络内的v m n 或嵌套子网的网络前缀，m r 则担当了移动网络的 缺省网关。 当移动网络离开家乡链路并附着在一个新的a r 上时，m r 首先向外地链路 请求转交地址( c o a ，c a r c - o f a d d r c s s ) 然后向其家乡代理( h a ，h o m e a g e n t ) 进行绑定更新。h a 响应m r 的绑定更新消息。一旦绑定更新过程完成，h a 与 m r 间就建立起了一条双向隧道，而该隧道的两端分别是h a 的地址和m r 的转 交地址。 北京交通大学博士论文第l 章绪论 变。由于组播路由与单播路由有很大不同，n e m o 基本协议所定义的h a 转发 机制并不适合于对组播数据包进行转发。这是由于组播的数据包是发向一个组播 地址的，而组播地址与移动网络中组播接收者所处网络的地址前缀不相关【5 ，因 此即便是组播数据到达了h a ，h a 也无法通过m r - h a 隧道把数据转发给m r 。 解决这一问题的方法是在h a 与m r 上都部署组播功能，使m r 和h a 可以利用 m r - h a 隧道交换组播路由信息。这样，就能够建立从网络到移动网络内的组播 接收者之间的组播树分支，以使移动网络内的组播接收者可以加入到组播组中。 从组播路由的角度来看，这种方法属于双向隧道( b t ) 的范畴。 文献【5 6 提出了一种在远程加入( r s ) 思想基础上的改进方法，并考虑满足 如下两个方面的要求： 为了加入个组播组，并向移动网络内的接收者转发组播数据，m r 必 须能够发现移动网络内的节点对哪些组播组感兴趣。 移动网络内的组播路由应该是优化的，并且组播数据包只应被路由到组 播接收者所在的网络部分，而不是让组播数据在移动网络内部进行泛洪 ( f l o o d i n g ) 。 为实现上述目标，文献 5 6 】在移动网络内部使用了基于m l d 口o 】组播转发 ( m l d - p r o x y i n g ) 垆”机制的方法。该方法在m r 和移动网络内部的固定路由器 上全都部署m l d p r o x y i n g 功能。这样，组关系信息就能够一跳一跳地从提供组 播服务的路由器向m r 传播，这些信息在每一个路由器上均被聚合。基于m l d 组播转发的机制与组播路由协议不同，它不对组播树的建立算法进行定义，而是 通过显式配置的方法在移动网络内形成一棵以m r 为根的组播树，并在执行代理 服务的节点的上游接口上执行m l d 协议的主机部分算法，在下游接口上执行 m l d 协议的路由器部分算法，图1 4 所示的是该方法的结构图。 北京交通大学博士论文第l 章绪论 研究了移动网络内部的组播路径的优化问题。由于组成移动网络的子网具 有嵌套( n e s t i n g ) 和多连接( m u 擗u p l i n i ( s ) 的特点，而且组播数据的路由方式 也与单播数据的路由方式不同，导致了在移动网络内部进行组播会面临许多困 难。因此，研究如何进行移动网络内部组播的组织方式和路由优化问题是移动网 络组播研究的一个十分重要的方面。在这一部分工作中，本论文首先讨论了移动 网络中单播路由与组播路由的特点与不同；接着讨论了组播对路由的需求；然后 在此基础上给出了一种实现移动网络内部组播和优化组播路由的方法；并结合移 动网络的位置管理、移动检测和移动预测对基于d m a 的移动网络组播进行了整 体描述；最后对该方法进行了分析。 论文的组织结构如下：第2 章提出了一种用于描述移动网络切换行为的迟滞 切换模型，并依据该模型的原则，提出了基于d m a 的移动网络组播方法；第3 章给出了移动网络的非均匀切换检测模型：第4 章建立了基于h m m 基本理论的、 关于移动网络的移动路径预测模型；第5 章给出了移动网络内部组播路由优化的 方法；第6 章对论文的工作进行了总结，并对未来的研究方向进行了展望。 北京交通大学博士论文第2 章基于动态代理选择的组播方法 2 2 迟滞切换模型 针对移动网络组播所面临的问题，本小节提出了一种约束移动网络切换行为 的迟滞切换模型，并在后续小节中给出基于此模型的移动网络组播方法一一基于 动态组播代理( d m a ：d y n a m i cm u h i c a s t a g e n t ) 的移动网络组播方法。需要说明的 是，这里的切换不仅指l p 协议的切换过程，而且还包括移动网络离开和重新加 入组播树的过程，这是一一种广义的切换。d m a 通过动态选择移动网络加入组播 树时的组播代理来使移动网络在附着点发生改变时，可以有选择地进行组播树的 重新加入，增强切换发生的迟滞效应，有效地降低了因移动所造成的组播树重构 的次数，同时还可以对组播路径进行优化。 2 2 1 模型描述 l 、若干概念 在给出迟滞切换模型前，首先对该模型中将要使用的几个概念进行约定： 虚网络( v n ，v i n u a ln e t w o r k ) ：是指相互邻接的若干子网所抽象出来 的虚拟网络，如图2 3 所示的v n l 和v n 2 。 移动节点：指具有移动能力和能够附着在子网上的移动通信实体的抽象 点，包括移动主机和移动网络。这里移动网络也被看作是豁毓型鄄姑i 薹跫稀；蛙鹜藿堡蹬群锰笮委绍酱霞甜释荑藿墓j 口礤倒一峨嚣霪挚嘎 缮霪鹭硬陬 网 络中的m n 不必再分别进行注册更新，从而节省了带宽并降低了更新时 延。 增强了可管理性。m r 提供了一种对蹩个移动网络特征的简单中心管理 点，一日需要对协议进行更新或增加其它的功能时，对m r 的软件和规 则的更新会比对每一个m n 进行更新更加容易和简便 。 北京交通大学博士论文 第2 章基于动态代理选择的组播方法 在上述过程中，s 代表移动节点的状态，w a i t ( t ) 表示状态判决的等待间隔 p v n l 表示来自v n l 的粘滞强度，p v n 2 表示来自v n 2 的粘滞强度。2 2 2 分析与仿真 仿真中假设v n l 的覆盖范围为以路由器r 1 为中心，覆盖半径为r 的圆形区 域。同样，v n 2 为以路由器r 2 为中心，覆盖半径也为r 的圆形区域。对于移动 节点的移动性，采用两种常用的移动模型进行仿真，即随机行走模型【6 1 j 2 1 和 u m t s 标准模型【6 3 。 对仿真中移动节点的随机行走行为的描述为，在时刻f o ，f ，岛，一。，有： ；( f o ) ，；( f i ) ， ；( f 2 ) ，；( 一) ，；( ) 相互独立，且 ；( 0 + f ) 一；( 0 ) 为二维正态分布。 umts标准模型中，设定移动节点的转向概率为以pc=025的概率向左转或向右转，移动节点的直行概率为p a = 0 5 。 仿真结果如图26图21l所示。在图26中，移动节点的运动为随机行 走。图27中，节点按照umts模型描述的方式运动。从结果可以看出，采用 临界值作为切换判别依据的切换方式所发生的切换次数。这里，把后者称为“边界切换方式”。o”鼎搿罗。“。“ 图26随机行走模型下边界切换与迟滞切换的比较柏柏o籁蛙蒜嚣 北京交通犬学博士论文 第2 章基于动态代理选择的缀插方法 发组播请求，由d m a 代替组播请求节点加入组播组。这里为了讨论 d m a 的整体曼程，在移动网终内部氆用了基予m l d p x y l n g 鳃方法， 在第5 章中将盼出一种更为优化的移动网络内部组播的组织方法。 m r 负责从其附着的a r 接收组播数据秘向组播接收者转发数据。 当移动弼络处在家乡链路对，m r 把家多代理作为组搔的一个动态组播 代理d m a ，通过d m a 加入组播组； 当蓼凄耀络蓄次褰开家乡链路势辩差凌一令瑟瓣搂入蠡辩，麴瑟2 ，1 2 中的a r 2 ，m r 请求a r 2 建立剿d m a 的隧道，并使用a r d m a 隧道 接收维援数据。由于移动路由器在附羞点切换露仍然通过d m a 获褥维 播数据，没有产生离开组播树并再次加入组播树的行为，因而没有对组 播树产生影响。 在一定祭释下，移动鹅终麓离琢来酌蛰m a ，势燕薪选择d m a 。重薪选 择d m a 的过程会产生一次对缎播树有影响的切换a 。震新选择d m a 戆条转耱方式蟪在下垂躯小节巾讨论。 在移动网络内部，把路由器与网络连接的两端分别定义为上游端口( m l d 的主规帮分) 稻下游翡翻( 池d 豹路赉器部分) ，翔銎2 1 3 掰示。组攒接孜者 发出的j o j n 消息通过路由器的上游端口发出，并向m r 一跳一一跳地转发，然后 在所经避豹劈耄器土聚合。这秘方法不瓣要在移凌网终内部运行缀撵路凌臻议， 也不需要采用建立组播树的方法来避免转发环路。 氅! ：| 蜘r 羹苷召县提微妇耋蚕释鹭争闭 动网络可以动态地选择为其提供组播 北京交通大学博士论文 第2 章基于动态代理选择的组播方法 移动网络在第一次移动后，通过a r 2 接入网络，并通过a r 2 - d m a 的 隧道接收组播数据； 在第二次移动中，移动网络通蟛娄掣相甄托拈。螯型藉裂箨萋妻：盘塔 荇鍪罄坚l 芝 翥弱竖羹鞫嚣豁鳓托珀力她甄u 1 奶薹萋；警i 薹雾衍萎矍蕃丝赣霪孝 蠹墨雾萼喜事i 爹基誊乏。童善娄磊i 善耋姜羹嘻善差隶耋耄塞：鬟嚣 d 鹏。 ( 24 ) 甲) ( 25 ) 皇斟 ， 其中，足o 表示移动网络i 在一个d m a 上的路径记录门限；堪表示d m a 与移动网络i 的组播源间的平均拓扑距离；口和五是调整k 值的参数，d m 。表示 移动网络所处网络域的最大直径；k 。表示移动网络当前附着的a r j 与d m a 间 的拓扑距离；甲，( ) 表示当移动网络附着在a r j 上，并通过d m a 接收组播数据 时的路径记录增量；h 1 表示不小于x 的最小整数。 式( 2 6 ) 表示：当移动网络的a r 与d m a 间的拓扑距离小于d m a 与组播源 间的平均拓扑距离时，移动网络附着在该a r 上的行为对路径记录长度的贡献是 1 ；当移动网络的a r 与d m a 间的拓扑距离大于d m a 与组播源间的平均拓扑距 离时，移动网络附着在该a r 上的行为对路径记录长度的贡献将大于l 。当路径 记录增量的和不满足( 2 5 ) 式，移动网络将重新选择d m a 。( 2 6 ) 式对路径的恶化 起到了限制作用。 令f 表示移动网络当前附着的a 与d m a 间的拓扑距离在路径记录上产生 的增量，由( 2 5 ) 和( 2 6 ) 式可得： 三 0 岸，( r ， 1 ，2 ，k ，月k ) ( 2 7 ) ( 2 7 ) 式表明，移动网络在经历过 k 个不同的子网后进行d m a 的重新选 择。当移动网络在拓扑上不具有邻接关系的子网间切换时，原d m a 与新a r 间 北京交通大学博士论文 第2 章基于动态代理选择的组播方法 图2 1 6 移动网络在不具有拓扑邻接关系的子网间移动 图2 1 7 显示了口和丑在不同取值时k 与l d s 之间的关系。从图中可以看出， 当l d s 较大时，k 的取值较小，限制移动网络只能在距离d m a 较近的区域移动， 以保证较优化的数据转发路径，发生d m a 重选的几率增大；当l d s 较小时，k 的取值变大，允许移动网络在较大的范围内移动而不发生d m a 重选，由于l d s 较小，数据路径能够保持在较优化的范围内。 5 0 4 5 柏 3 5 3 0 2 5 芏 2 0 1 5 1 0 5 0 一善弑；奈 l 丞k i 05 01 0 01 5 02 0 02 5 0 t o p o i o g yd i 舶眦e 图z 1 7l _ k 曲线 对d m a 的动态选择机制相对于位置固定的组播代理而言，充分利用了网络 资源减弱了d m a 成为网络通信瓶颈的机率；移动网络对隧道状态的维护可以 保证具有相同家乡代理的移动网络附着在同一接入点上并加入同一个组播组时， 仅使用一个d m a 提供的服务，避免了隧道聚集问题。 2 7 北京交通大学博士论文 第2 章基于动态代理选择的组播方法 2 4 数值分析 假设一个移动网络在若干子网组成的网络环境中移动，每一子网中有一个接 入路由器a r ，并可以作为d m a 。由于移动网络只能在具有重叠覆盖区域的邻 接子网间切换，为简化讨论，设网络具有如图2 1 8 所示结构，其中每一个子网 均与m 1 = 7 1 = 6 个子网邻接。 一 一个移动网络从第一个按入点发生一次切换并移动到第二个接入点的概率 由( 2 8 ) 式给出： ：1 1 2 【o ， n 1 其数学期望如( 2 9 ) 式 研】1 2 2 ，n 2 1 。 九= l ( 2 8 ) ( 2 9 ) 设移动网络在发生d m a 重新选择前需经过k 个子网，并且每一次进入新的 子网时的路径记录增量为l 。如果移动网络已经经过2 个不同接入点，在第n 次 移动时切换到第3 个接入点的概率为： 腿，= ( 嘉r 等 其数学期望为： ( 2 1 0 ) 图2 z 1 9 0 0 节点网络中k = 4 时的组播路径长度比较 图2 2 29 0 0 节点网络中k - 5 时的组播路径长度萋 茎j ；lf 醣醮燮娄 璧f + 自畦垂蝥茎尚匿琦鸷蠢桩 中的各个b s s 使用信道的方法进行限制，也就是说， 北京交通大学博士论文 第2 章基于动卷代理选择的组插方法 移动子网与搬播源之闻的路径长度( k = 8f o r 嘣a ) 、n r 一i 两醑 。r 一飘r 西 酗e * n t 强2 。2 9 0 0 繁悫网络孛转8 辩鹣缀搔路径长度彗：较 搏动子网与鳃擗源之嘲瓣路径长度f 黔i of o r 埘麒 1 8 一 1 6 1 4 一j i 湃谭型譬攀妫遂觯| 露1 2 点1 0 出8 。气i l i r 。一一鼍女j l a i el 基8 v 一坩一 4 2 0 -tr -t-，-一一 -ri l471 8 1 3 l s1 9 2 2 2 s2 8 鞋3 43 7 蝣部赔4 5 2 辐5 8 x o v e m e n t 强2 2 59 0 0 节悫弼络中转l o 对静组播路经长度比较 阕2 2 69 0 0 节点两络中k = 1 2 时的级播路径长度比较 旧一 l 北京交通大学博士论文第2 章基于动态代理选择的组擂方法 大时，这一数值也会变得较大。采用平均子网切换次数这一参数可以从另外一个 角度说明d m a 机制所产生的迟滞切换效果。 表2 4 和图2 3 0 给出的是在4 个不同的拓扑上，移动网络进行6 0 次移动后 的路径平均值的数据和曲线。从数据可以看出，d m a 移动网络组播的平均路径 长度大于r sb a s e d 的组播，而小于b tb a s e d 的组播，与前面对路径变化的分析 结果一致。由此可以看出，在不同的网络拓扑结构下，d m a 都能够选择优于 b t a s e d 组播的路径。 表2 4 仿真结果：平均组播路径长度 t 0 p o n o b tb a s e dr sb 髂e dd m a 11 4 ，1 57 7 21 0 18 21 2 5 88 41 0 7 31 1 2 35 7 57 2 3 41 0 14 6 3 36 7 7 t 0 p o l 铂yn 0 图2 3 0 不同拓扑下三种方法的平均组播路径长度比较 图2 3 l 和剧2 3 2 是在动态计算k 值和路径记录增量的条件下的仿真结果， 同时移动网络以没有限定条件的随机行走模型在子网间移动。 仿真结果表明，在没有限定的随机行走模型的条件下，移动网络在拓扑上不 具有邻接关系的子网间切换的频率大大增加，从而导致组播路径变长。但另一方 面，动态的k 值和路径记录增量机制又使得移动网络基于d m a 的组播路径能够 快速从较差的路径上向较为优化的路径过渡。比较移动网络的组播路径平均值可 以看出，基于d m a 的移动网络组播路径要优于b t - b a s e d 的组播路径。 从对仿真结果数据的分析可知，仿真中移动网络在整个拓扑上随机行走的模 式导致了较多在拓扑上不具有邻接关系的子网间切换的发生，这是较为极端的情 况。在实际的网络和移动中，这种情况较少发生。 北京交通大学博士论文 第3 章非均匀商巍摇狮掰莉 雪邕r 嚣廷鬟蠢l ；羹宝l ? 西髓蓉豁目i & * = ：曼m ； 要苍霎塑f 栏基帮殴i 静孽球掣磐蠢的囊霉锫薹目滋； 善“至谢前懈悔堕茎满誊l 菊售艮黾鳍老翱副i 譬 j 薹蚕o n ! 霞h 霪e j ! 委g 瞎矛；鬟割副拦j 萋 鞘琴l 二驯誊# i ￥l 霸鳆蓑丽蘸黜藩囊擎赁塑颡烘嘤蓄剿蚓吲i 鍪蠢誊 q 秘鲥蛾蓉研盹晷翥刖牡止霞誊同时开始网络层的切换过程。 下面给出的是上述检测过程的伪代码。 i n i t i nt i z n l i o n ： s e tc t fr e n t a rp r o b e 4 r o ： s e tc u r m n l pp m b e o ： c k ra 风上口c h e ： s e t p s 。c h ea p s b t f c t l r r e 硪r j ： s e ta & a c h e f c h r m 州j p jf l d g ： c n k m m ej “t m b e m e o ： d e 把c t io n ： s e tp r 。be d pp b e o ： 咎( p m b e dj pi h p s n c h e ) 玎俨m 沁d jp c t l r m n t p ) s e ta 黜s h e 【c u n m j p ln o f k g s e tc w 啤m pp m b e d p i s e ta p s上a c l e f c u r m n t 码f i d g f ， ， e i s ef c l e 口ra p s 口c k ： s e tcu r r e n t rp m b e r o ： s da p sn c l ea p j i s t ( c w m n l r ) ： s e tc u e n ta pp m b e da p ： s da ps 王a c h e ( c v m m p 】f l n 各 t r i g 官er j 3 - k n d o 嚣o ： ， c 8 ll 谢e e 搬- p 渤e m o ： 按照上述检测过程，旦m n 所附着的a p 发生了变化，m n 就能够及时知 道发生了链路层切换，此时不用等待r a 消息的到来就可以开始进行网络层的切 换了。此外，在使用n d c p r 的m n 上，r a 消息也可以触发m n 的网络层切换， 北京交通大学博士论文 第4 章基于h m m 的移动预测 文献【1 3 3 】f 吏用称为“l e z i u p d a t e ”的算法对移动进行预测。其基本思想是通 过预测减小更新机制的开销。它是一种基于时间和移动性的混合更新方法。在移 动用户穿越蜂窝边界时记录蜂窝的标识，并作为移动的历史记录。 文献 1 3 4 】提出了一种切换行为的历史概率模型，并对一个蜂窝内的所有切 换历史进行聚合。通过称为切换事件四元组( 终端离开当前蜂窝的时间，前一蜂 窝的标识，下一蜂窝的标识，移动终端在当前蜂窝中驻留的时间) 的结构，使每 一个蜂窝都建立一个切换估计函数，并进而估计移动终端的下一个蜂窝的位置。 文献 1 3 5 】给出了移动终端的运动预测( m m p ，m o b i l em o t i o np r e d i c t i o n ) 方 法，其中包括规律性模式检测( r p d ，r e g u l a r i 可p 毗e md e t e c t i o n ) 算法和运动 预测( m p a ，m o t i o np r e d i c t i o n a l g o r i t l l m ) 算法。前者用于检测用户的特定移动 模式，后者则用于比较规律性信息与随机信息，并决定用户的最终位置。 文献【1 3 0 的方法是基于人工智能技术的，称为学习自动机( l a ，l e a m i n g a u t o m a t i o n ) 。l a 是一种有限状态自适应系统，它与环境进行持续的交互，并通 过一个基于概率的“试验错误”响应过程来学习选择与适应行为，从而产生对 输入的最好响应。l a 使用包含一步转移概率的状态转移矩阵对环境的输入进行 操作，通过环境反馈信息完成对转移矩阵的调整。在调整策略中，采用了线性奖 惩机制。仿真结果表明，该方法的预测准确率为7 0 8 0 。但该方法的局限 性在于它受到系统反馈调整机制的影响比较大。 文献【1 3 6 】提出了一种基于距离预测的位置管理算法，使用高斯马尔可夫状 态机作为移动模型，并可根据移动用户的当前位置和速度预测用户的下一位置。 文献【1 3 7 和文献 1 3 8 使用了卡尔曼滤波器( k a l m a nf i l t e r m 9 】) 机制对移动 用户的移动性进行预测。其中 1 3 8 】结合位置预测和位置更新来进行w a t m 网络 中的资源预留与分配； 1 3 7 使用预测机制为高速移动用户提供位置管理方法。 【1 3 7 的仿真结果表明，预测方法的使用使得t c p 平均流量提高了3 0 5 0 。 文献1 4 0 1 ( f h r ，f r e q u e n th a n d o f r r e g i o ns e l e c t i o na l g o r i t h m ) 研究了公共 w l a n 系统中用户移动的预测问题。它使用切换事件的目志数据计算a p s 间单 位时间内的切换率，并以此获得a p s 间的链路权值，对移动用户将要进入的a p s 进行选择。f h r 是一种建立在用户通信流模式和用户特征基础上的方法，通过 对用户历史数据的统计进行移动预测。虽然与相应的其它机制结合可以减小 w l a n 中的切换时延，但不是一种具有普遍意义的移动预测方法，而且与用户 在一个a p 内的驻留时间的相关性较强，也影响了它的灵活性。 文献 1 4 1 】研究了a d l o c 网络环境下移动节点的移动性对拓扑结构的影响问 题，提出了计算节点间链路保持时间的算法，并在此基础上研究了面向流的路由 预测和带有预测功能的距离矢量路由。其方法是在移动节点接收信号强度只与传 输距离有关的条件下，如果相邻节点的速度、运动方向和无线覆盖范围已知，则 可通过几何计算的方法来获得两个移动节点能够保持连接的时间。从对该方法的 分析可知，计算结果只具有短时作用，不能算做是真正意义上的移动预测。 文献 1 4 2 给出了一种跟踪单个移动节点的方法，它使用移动节点的移动追 北京交通大学博士论文第4 章基于h m m 的移动预测 踪模式进行预测，是一种基于逻辑移动( 相对于地理移动) 的方法。在该方法中， 它把移动节点的状态分为平稳和转移两种状态，并通过移动追踪模型进行预测， 使用三种类型的匹配关系进行相关性分析，即“状态匹配川“、“速度匹配，j 【“4 j 和“事件匹配”。算法尝试了通过计算当前移动( 刚刚访问过的子网序列) 和过 去移动( 在前一段时间中访问过的子网序列) 之间的相关性对移动节点的下一个 位置进行预测。仿真结果显示，在对两个子网进行预测时，约有8 0 的移动节 点的预测准确率高于7 0 ；而在对一个子网进行预测时，有8 0 的移动节点的 预测准确率高于5 4 。 文献【1 4 3 提出了一种使用h m m 模型进行移动节点未来移动行为预测的方 法。其基本思想是：把一个a p 覆盖范围内的区域划分成多个小的区域，即状态； 选择移动节点的某种可观察特征( 如坐标或信号强度等) 作为观察符号；在移动 节点在该a p 覆盖范围内移动并切换到下一个a p 的过程中，获得移动节点的观 察符号序列，并用观察序列对相应的h m m 进行训练，得到有关于特定a p 的 h m m 参数：在实际的预测过程中，每当移动节点报告观察符号序列，a p 通过 最大似然估计的方法就可得知移动节点将要进入的下个a p 。仿真结果表明， 在适当选择状态数量和观察序列长度的条件下，预测可以达到很高的准确度。本 章中的预测方法也使用h m m 模型进行移动预测。 为了对以上算法有更清晰的认识，表4 1 对上述方法进行了比较。 表4 1 移动预测方法的比较 方法条件性能 p r e d i c t i v em o d e if o r 移动的历史数据在小范围内的固定路径模 i n d o o r1 1 r a c k i n go f 室内小范围的移动式下准确性较高 m o b i l eu s e r s 【1 3 1 】 p r o f i l eb a s e dn e x t c e l l 移动的历史数据典型移动模式下预测准确 p r c d i c t i o na l g o r i t l l m 【1 3 2 】使用切换信息描述移动 性为8 0 ，随机移动模式 下为7 0 l e z i u p d a t e ：1 r a c k 移动的历史数据与q o s 相结合 m o b i l eu s e r sl np c s 穿越蜂窝边界时记录蜂 n a n e 撕o r k s 】 窝标示 p r e d i c t i v ea 1 1 da d 印t i v e 移动的历史数据自适应带宽预留 b 柚d w i d t l lr e s e r v a t i o n建立基于四种信息的蜂n ，a 【1 3 4 窝切换估计函数 m m p ：m o b i l em 0 t i o n 移动历史模式最大预测有效率9 5 p r e d i c t i o n 【1 3 5 规律性模式检测e u p d 和 运动预测m p a 算法 m u l t i u s e rd r i v e np a t h 移动的历史数据准确率为7 0 8 0 。受 p r e d i c t i o na l g o r i t h mf o r 基于概率的“试验一错误”到系统反馈调整机制的影 北京交通大学博士论文 第4 章基于h m m 的移动预测 m o b i l ec o m p u t i n g 【1 3 0 】 响应进行持续的学习 响较大 p r e d i c t i v e d i s t a n c eb a s e d移动的历史数据用户的移动模型为恒定速 m o b i l i t ym a n a g e m e n t 基于距离预测的位置管率流体模型时，通信开销 f 1 3 6 】 理降低8 5 倍 p r e d i c t i v em o b i l ei pf o r 移动的历史数据t c p 平均流量提高3 0 r a p i dm o b i l i 可【1 3 7 】位置预测与位置更新 5 0 f h q u e n th a n d o f r 移动的历史数据切换时延和a p 上的缓存 r e g i o ns e l e c t i o n 切换事件日志用于计算等指标得到了优化 a 1 9 0 r i t h m f h r 1 4 0 】 切换率n f a m o b i l i t yp r e d i c t i o ni n 节点的距离和移动速度数据包转发率o 7 6 ，在没 w i r e l e s sn e t w o r k s 【1 4 l 】 的瞬时值有方向性改变的情况下， 速度、运动方向、无线信转发率o 9 8 号覆盖范围 e x p l i c i tp r o a c t i v e 移动的历史数据对两个子网进行预测，8 0 h 明d o f fw i t hm o t i o n状态匹配、速度匹配和事的节点预测准确率高于 p r c d i c t i o nf o rm o b i l ei p件匹配 7 0 ；对一个子网预测， 【1 4 2 】 8 0 移动节点的预测准确 率高于5 4 l e a m i n gm o v e m e n t 移动的历史数据 5 状态简单拓扑下预测准 p a t t e 】m si nm o b i l e 根据移动节点的位置信确率9 8 ；复杂拓扑下6 7 n e t 、v o r k s j息对模型进行训练，l o 状态下8 2 4 2 h 删模型 瑚m m 模型是一种描述与发生事件序列顺序相关问题的有效模型，也是一种 随机概率模型，已广泛应用于语音识别、手写体文字识别和手势识别等领域。 h h m 模型具有占用存储空间小、分类计算快和分类系统简单等特点。 4 2 1m a r k o v 模型 给定随机变量z 的一个样本序列d = “l 一= t ，z ” ，样本序列d 出现的概率 可以表示为【1 4 4 】： p ( dl 吖) = p ( 爿。，舳，扎，以，_ ) = p ( 。i _ 川，丑，j ：托) p ( 爿川l x 托，：，一) p ( 扎l 丑) p ( _ ) ( 4 1 ) ( 4 2 ) 北京交通大学博士论文第4 章基于f 蝴m 的移动预测 = ，( 点) 兀p ( f 。) 日= 2 对式( 4 3 ) 应用一阶m a r k o v 假设 p ( 靠i k 。一乓，如蔓p ( l 矗) 可得 p ( p | 掰) = p 五) n p ( 矗l ) = 2 浚乓取篷翡凌态窆闻蔻s = 盆，奶，委k ，式( 4 5 ) 霹表汞必： “3 ) ( 4 4 ) ( 4 5 ) ，f 弦；掰= p ( 萎霪) h 尹4 喝| 茸。t 盆) 转。6 ) 其中罗以吗l k ；镌) 称为状态转移概率，记佟 q = p ( 乌i “，q ) ( 4 7 ) 如聚按发生时闯颓謦对d 墩德，式( 4 霸均状淼转移糍率表明，每当过程处于 状态q l ，则在下一时刻处于状态q ，的概率只依赖于当前状态，而与过去的状态 无关，称为过程的无后效性或m a r k o v 惶。 m a r k o v 过程是一个髓机过穰转f ) ，f r ，具有如下性质：农t 时刻处于状 态善“) = q 的条件下，在时刻以后的过程将要到达的状淼的情况与该时刻以前 _ j 霪翟袋楚戆凌态蠢关【缀。m a r 沁v 过程苓蕊戆取簇鹃全体麴凌过耩静获态绽阕。 对于一个状淼空间j 离散并熙参数f 非负的随机过程转( f ) ，f = o ，l ，2 ， ，若 肖： p ( 孝( f + 1 ) 等_ ，i 掌( f ) = f ，掌( f 1 ) = 一，掌( o ) = 姑) = p ( 手( f + 1 ) = l 孝( r ) = f ) ( 4 8 ) 鬟| l 稳这榉装隧极过程藜为m a 呔o v 链。m 8 呔。v 链在鞋载f 懿一步条 孛转移壤率 嘞( f ) = p ( 掌( f + 1 ) = ，i 孝( r ) = f ) 称为时刻f 的状态转移概率，有如下性质： ( f ) o ( 4 9 ) 锡( 0 = l 1 0 ) ， 定义如下矩阵4 为状态转移矩阵： 北京交通大学博士论文 第4 辩基于f m “的移动预测 y = q 仁，：懋( i 唾一q i ) ，七。l ，2 ，m ( 4 5 2 ) 式中协，z = l ，2 ，猡灸鼹察镣芍样本空阀，其稽