（计算机应用技术专业论文）改进的遗传算法及其在移动ip路由中的研究.pdf

摘要 在移动i p 通信过程中，数据包需要经过网络中多个指定的节点，以保证节点 的移动性；同时移动i p 以其独有的特性和特点要求使用一种不同于固网的路由方 案以保证移动节点的代理切换时延尽可能小。 针对移动i p 中通过多个指定节点的路由问题，提出了一种改进的遗传算法。 使用给出的定点对路由问题可行域中的解进行分段以减小种群的规模和染色体长 度。并使用上述方法将一个复杂的路由问题分解为多个子问题，通过子问题的求 解可以得到通过多个指定节点的最短路由。然后，在随机网络拓扑中对该算法进 行验证，实验表明算法能够有效的求解通过指定多个节点的最短路由问题。 对于移动节点代理切换时延的问题，使用上述算法进行优化。首先，给出了 影响时延的多个因素，并建立了优化模型。然后，为了加快遗传算法的收敛速度 减少算法执行时间引入模拟退火机制对上述算法进行优化。实验表明，引入模拟 退火机制以后遗传算法的收敛时间明显减少。 在上述分析的基础上，用网络仿真工具对使用上述路由算法的移动节点代理 切换进行仿真。仿真结果表明，使用上述算法能够取得一定的优化效果。 关键宇：移动l p ；遗传算法；模拟退火算法；路由；n s 2 ；随机网络拓扑 a b s t r a c t i nt h ep r o c e s so fm o b i l ei pc o m m u n i c a t i o n ，t h ed a t ap a c k a g e sn e e dt op a s sm a n y d e s i g n e dp o i n t sf o re n s u r i n gt h en o d e sm o b i l i t y ；a n dt h em o b i l ei pw i t hp a r t i c u l a r t r a i t sa n df e a t u r e sn e e d sar o u t i n gs c h e m ed i f f e r i n gf r o mt h a to ff i x e dn e t w o r kt o a c h i e v eam i n i m a la g e n ts w i t c hd e l a yo fm o b i l en o d e t os o l v et h er o u t i n gp r o b l e mo fp a s s i n gm a n yd e s i g n e dp o i n t si nm o b i l ei p , a l l i m p r o v e dg e n e t i ca l g o r i t h mi sb r o u g h tf o r w a r d i no r d e rt od e c r e a s e t h es i z eo f p o p u l a t i o na n dt h ec h r o m o s o m e sl e n g t h ，t h es o l u t i o ni nf e a s i b l er e g i o no ft h er o u t i n g p r o b l e mi ss e p a r a t e dt os e v e r a ls e c t i o n sb yd e s i g n e dp o i n t s t h em e t h o di s u s e dt o t r a n s f o r mac o m p l e xr o u t i n gp r o b l e mt os e v e r a ls u bp r o b l e m s ，a n dt h es h o r t e s tr o u t i n g p r o b l e mo fp a s s i n gm a n yd e s i g n e dp o i n t sc a nb es o l v e db ys o l v i n gs u bp r o b l e m s t h i s a l g o r i t h mi sp r o v e db yar a n d o mn e t w o r km o d e l ，a n dt h ee x p e r i m e n t a lr e s u l ts h o w s t h a ti ti se f f e c t i v et os o l v et h ep r o b l e mo fp a s s i n gm a n yd e s i g n e dp o i n t s t h ep r o b l e mo fs w i t c h i n ga g e n to fm o b i l en o d ei so p t i m i z e db yt h ea l g o r i t h m a b o v e f i r s t l y , s e v e r a lf a c t o r st h a ta f f e c tt h es w i t c h i n gd e l a ya r ep r e s e n t e d ，a n dt h e o p t i m i z e dm o d e li sb u i l t t h e nt h em e c h a n i s mo fs i m u l a t e da n n e a l i n g i si m p o r ti nt h e a l g o r i t h ma b o v et o d e c r e a s et h ee x e c u t i o nt i m ea n dq u i c k e n st h ev e l o c i t yo f c o n v e r g e n c e a c c o r d i n gt o t h ee x p e r i m e n t a lr e s u l t s ，t h eg e n e t i ca l g o r i t h mw i t h s i m u l a t e da n n e a l i n gh a sl e s st i m et oc o n v e r g e f r o ma n a l y s e sa b o v e ，t h en e t w o r ks i m u l a t i o nt o o l sa r eu s e dt os i m u l a t et h ea g e n t s s w i t c h i n gp r o c e s so fm o b i l en o d e t h es i m u l a t i o nr e s u l ts h o w st h a tt h ea l g o r i t h m p r o p o s e di sa b l et oa c h i e v ee x c e l l e n tr e s u l tt oac e r t a i ne x t e n t k e yw o r d s ：m o b i l ei p ；g e n e t i ca l g o r i t h m ；s i m u l a t e da n n e a l i n ga l g o r i t h m ； r o u t i n g ；n s 2 ；r a n d o mg r a p hm o d e l ； i i 插图索引 图1 1 全球网络用户发展趋势1 图2 1 移动i p 功能实体和关系5 图2 2 移动i p 数据包转发7 图2 3 移动节点漫游8 图2 4n s 仿真步骤1 1 图2 5 移动i p 仿真实例1 2 图2 6 链路流量变化1 4 图2 7t c p 窗口大小变化1 4 图4 1 移动节点通信路径2 5 图4 2 通过多个指定节点的路径2 6 图4 3 路径表示编码2 7 图4 4 随机遍历抽样法3 0 图4 5 交叉操作3 1 图4 6 变异操作3 2 图4 7 修正操作3 2 图4 83 0 个节点的随机网络图3 6 图4 9b r i t e 随机网络生成器3 7 图4 1 0 两个节点间的最短路径3 7 图4 1 1 改进遗传算法的收敛性3 8 图4 1 2 通过三个指定节点的最短路径3 8 图4 1 3 通过五个节点的最短路径3 9 图5 1 代理切换仿真拓扑结构4 3 图5 2 移动节点代理切换时延4 4 图5 3 n s 仿真单个移动节点4 5 图5 4 模拟退火遗传算法优化路由的收敛性4 8 图5 5 移动节点流量变化5 1 图5 6 丢弃的数据包5 1 图5 7 两个移动节点通信的流量变化一5 2 附表索引 表4 11 0 0 个节点网络拓扑的实验结果4 0 表5 1 路由表5 0 v 1 缩略词表 缩略词英文 中文 g ag e n e t i ca l g o r i t h m 遗传算法 d h c p d y n a m i c h o s tc o n f i g u r a t i o np r o t o c o l 动态主机配置协议 n p cn o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e 完全非确定性多项式 f m f i x e d m o b i l ei n t e g r a t i o n 固网和移动网整合 m m m o b i l em a n a g e m e n t 移动性管理 m n m o b i l en o d e 移动节点 h ah o m ea g e n t 家乡代理 f a f o r e i g na g e n t 外地代理 h n h o m en e t w o r k 家乡链路 f n f o r e i g nn e t w o r k 外地链路 i s 0i n t e r n a t i o n a ls t a n d a r d i z a t i o no r g a n i z a t i o n 国际标准化组织 0 s i o p e ns y s t e mi n t e r c o n n e c t 开放系统互连参考模型 e s e n ds y s t e m 端系统 a s a u t o n o m o u ss y s t e m 自治系统 s p fs h o r t e s tp a t hf i f s t 最短路径优先 n s n e t w o r ks i m u l a t o r网络模拟器 v 玳t v i s u a li n t e r n e k v o r kt e s t b e d 虚拟互连网络实验床 t c lt o o lc o m m a n dl a n g u a g e 工具命令语言 v c g av a r i a n t so fc a n o n i c a lg e n e t i ca l g o r i t h m s 变形遗传算法 s g a s i m p l eg e n e t i ca l g o r i t h m 基本遗传算法 h g a h y b r i dg e n e t i ca l g o r i t h m 混合遗传算法 g e n o c o p g e n e t i ca l g o r i t h mf o rn u m e r i c a l 约束优化的遗传算法 o p t i m i z a t i o nf o rc o n s t r a i n e dp r o b l e m s a g as i m u l a t e da n n e a l i n gg e n e t i ca l g o r i t h m 模拟退火遗传算法 o o s q u i l t yo fs e r v i c e 服务质量 d s d v d e s t i n a t i o n - s e q u e n c e dd i s t a n c e v e c t o r目的序列距离矢量 p p p p o i n tt op o i n tp r o t o c o l 点对点协议 c b rc o n s t a n tb i tr a t e 恒定比特率 v b rv 撕a b l eb i tr a t e 可变比特率 s d h s y n c h r o n o sd i g i t a lh i e r a r c h y 同步数字体系 a n 讧 a s y n c h r o n o u st r a n s f e rm o d e 异步传输模式 d w d md e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g 密集波分复用 r e dr a n d o m e a r l yd i s c a r d 随机早期丢弃 v i l 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 刁 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 日期；如噼a - - 月1 9 - 日 日期姗，年n 占日 1 1 课题的背景及意义 第一章绪论 随着因特网的不断发展壮大和移动通信的普及应用，越来越多的无线设备连 接到i n t e r a c t ，人们对网络的依赖性日渐增加，并希望能够以种更加灵活便利的 方式随时随地访问企业网和i n t e r a c t ，这就要求将目前的有线网络技术和和移动通 信技术结合起来，为人们提供可以承载多媒体业务的宽带无线接入和无缝全球个 人通信”“2 “”。研究表明，2 0 0 2 年后全球将有超过十亿的手机用户连接到i n t e m e t ， 并且该数字将以指数增加。到2 0 0 6 年， 户数将超过固定i n t e r n e t 用户数的总和， 数字电话、p d a 以及其他移动设备的用 图1 i 埘显示了全球网络用户的发展趋势。 随着人们对i n t e m e t 服务需求的日益高涨，移动性已经成为目前i n t e r n e t 研究的最 图1 1 全球网络用户发展趋势 重要问题之一。 然而，最初在设计网络体系结构和协议的时候并没有太多考虑移动性。移动 由于其固有的特性给网络设计带来了困难。首先，必须在不同类型的网络中支持 移动性。其次，当移动节点穿越网络和设备的时候，其应用层提供的服务必须保 持连续性，这对应用层的服务体系结构以及端到端的协议提出了新的要求。另外， 由于移动节点体积小，通常情况下使用电池，所以性能是移动网络中特别是无线 情况下要考虑的主要问题。在这种情况下，如何使网络为移动提供很好的支持是 研究的热点问题。同时如何为移动相关的应用提供准确、高效的路由和寻径是网 络得以连通的基础。 为了解决节点的移动性问题，移动i p 技术”1 应运而生。它有效地解决了移动 节点的安全和用户管理，实现了移动用户的双向访问和基于i p 的权限管理、计费 管理并实现了移动用户对企业资源和互联网资源的透明访问；移动i p 使高速无线 接入技术与移动通信系统的漫游技术在i p 层上相结合，以提供高效的互联网接入 服务。从目前发展的角度来看，移动i p 仍然是在i n t e r n e t 中支持i p 移动性的唯一 解决方案。 1 。2 国内外研究现状 所谓移动i p 技术，是指移动节点在跨网段随意移动和漫游过程中，使用基于 t c p i p 协议的网络时，不用修改移动节点的i p 地址，同时继续享有原网络中的一 切权限”。在传统的网络中，受t c p f l p 协议的限制只能实现在同一坤子网中不 同小区间的越区切换功能，在不同的i p 子网、不同的局域网之间不能进行漫游， 如果使用d h c p ( d y n a m i ch o s tc o n f i g u r a t i o np r o t o c 0 1 ) 解决漫游问题，那么移动 节点的i p 地址是变化的，该方法最直接的缺点是网络上的其他用户不能对它发起 访问。而移动i p 技术可以使移动节点在不同的i p 子网间自由移动，同时在移动 过程中保持对互联网的访问，进而扩展了移动用户的移动范围，使互联网上用户 的交互访问更方便。 第一个移动主机协议由哥伦比亚大学的j o h ni o a n n i d i s 设计，它的主要思想是 使用虚拟移动子网和i pi ni p 技术”1 。同时，s o n y 公司的f u m i ot e r q o k a 设计了另 一种移动主机协议，虚拟i p ( v i p ) ，该协议使用了特殊的路由来标记移动主机的 位置，并定义了新的i p 头选项来递送数据”。在此之后不久，i b m 的c p e r k i n g 和yr e c k t e r 也设计了一种移动主机协议，这种协议利用了现有i p 协议中的可选 功能松散源路由( l o o s e s o u r c e r o u t i n g ) 来支持主机的移动”1 。1 9 9 4 年a m y l e s 和c p e r k i n g 分析了前三种移动主机协议的优缺点，重新设计了一种协议m i p ， 该协议后来发展成为m o b i l e i p 协议。1 9 9 6 年1 0 月，i e t f ( i n t e r n e t 工程任务组) 提出了移动i p 协议标准( 草案) ，主要包括r f c 2 0 0 2 、r f c 2 0 0 3 嘲、r f c 2 0 0 4 嗍、 r f c 2 0 0 5 m 1 和r f c 2 0 0 6 ”等r f c 文档。r f c 2 0 0 2 定义了移动i p 协议；r f c 2 0 0 3 、 r f c 2 0 0 4 和r f c l 7 0 1 ”定义了移动i p 中用到的三种隧道技术；r f c 2 0 0 5 叙述了移 动i p 的应用：r f c 2 0 0 6 定义了移动i p 的管理信息库m i b 。该草案文档一经发表， 立刻引发了全球范围研究移动i p 技术的高潮。美国哥伦比亚大学、纽约大学、卡 耐基梅隆大学、新加坡国立大学、日本科学与技术研究所、瑞典皇家学院以及 f t ps o f t w a r e 、i b m 、m o t o r o l a 、n o k i a 、s u n 、t e l x o n 等公司都成立了相应的工作 组，针对移动i p 进行研究。 我国在此方面也不甘落后，脱胎于西安电子科技大学国家重点实验室的捷通 通信公司承接了作为国家8 6 3 项目之一的移动i p 技术的研究，并成功开发了国内 首台移动i p 服务器f r e e n e tb u i l d e r ，在获得国家级认可后进入了商用通信市 场。 移动i p 不是移动通信技术和因特网技术的简单叠加，也不是无线语音和无线 数据的简单叠加，它是移动通信和i p 技术的深层融合，也是对现有移动通信方式 的深刻变革。它将真正实现语音和数据业务的融合，移动i p 的目标是将无线语音 和无线数据综合到一个技术平台上传输，这一平台就是i p 协议。未来的移动网络 将实现全包交换，包括话音和数据都由i p 包来承载，语音和数据的隔阂将消失。 在i m t - 2 0 0 0 中已明确规定，第三代移动通信系统必须支持移动i p 分组业务。而 i e t f 也正在扩展因特网协议，开发一套用于移动i p 的技术规范。目前针对移动 i p 研究的重点集中在承载不同业务时的性能分析“1 “4 “1 ，以及使用优化路由技术 时的性能分析。 移动通信的i p 化进程将分为三个阶段：首先是移动业务的i p 化；之后是移 动网络的分组化；最后是在第三代移动通信系统中实现全i p 化。随着分组业务量 的急剧增长和i p 技术的完全成熟，所有的业务将会统- - ni p 网络，形成一个真 正的综合业务网络。 遗传算法研究的历史比较短，2 0 世纪6 0 年代末期到7 0 年代初期，主要由美 国m i c h i g a n 大学的j o h nh o l l a n d 与其同事研究并形成了一个比较完整的理论和方 法体系o ”“7 1 ，从解释自然界系统中生物的复杂适应过程入手，模拟生物进化的机 制来构造人工系统模型。1 9 6 8 年至1 9 7 1 年，h o l l a n d 提出了重要的模式理论 ( s c h e m at h e o r e m ) ，建议采用二进制编码，并指出了运用g r a y 码的一些优点， 他研究从生物系统引申出的各种不同的选择和配对策略。1 9 7 5 年h o l l a n d 出版了 经典著作a d a p t a t i o ni nn a t u r ea n d a r t i f i c i a ls y s t e m ”，同时d e j o n g 完成了具有指 导意义的博士论文a na n a z y s i so ft h eb e h a v i o ro fac l a s so fg e n e t i ca d a p t i v e s y s t e m ”，并建立了著名的d e j o n g 五函数测试平台，定义了性能评价标准，并以 函数优化为例，对遗传算法的六种方案的性能及机理进行了详尽的实验和分析。 作为一种优秀的搜索算法，遗传算法具有自组织、自学习、并行性等特点并 在许多领域取得了成功”。而使用遗传算法进行网络路由优化是当前研究的一个 热点问题瑚1 ，m m u n e m o t o ，j i n a g a k i ，m i t s u o 等人分别提出了使用遗传算法进行 路由研究的不同改进方法”2 “2 ”。由于移动i p 技术的兴起，很多学者开始使用遗 传算法进行移动i p 路由技术的研究”4 “2 ”。 1 3 本文的主要工作 本文主要讨论移动i p 中的路由问题，以及如何改进遗传算法使其能够适应于 移动i p 网络中特定的路由优化问题，并讨论了移动i p 通信过程中影响通信质量 的节点切换时延问题。本文的主要工作如下： 1 通过分析现有移动i p 的工作原理和路由方法，阐述了移动i p 环境下特有 的通过多个指定节点的最短路由问题，并提出了一种改进的遗传算法对该问题进 行求解，从而将一个复杂的优化问题划分为多个简单的优化问题。 2 对移动i p 网络中移动节点在进行代理切换时的时延问题进行了分析，并 给出了时延优化的数学模型，并在该模型中加入了通信对端之间节点数目的影响 因素，即时延优化问题不仅受网络时延、带宽的影响而且还要考虑通信对端之间 节点的个数。 3 使用模拟退火的思想对通过多个指定节点最短路由的遗传算法进行改进， 从而加快算法的收敛速度减小陷入局部最优解的概率，并使用改进后的算法对切 换代理的时延进行优化。 在本文中使用网络仿真工具n s 对移动i p 的主要工作方式进行了仿真，并分 析了在仿真过程中出现的移动节点代理切换的时延问题；对于文中提出的通过多 个指定节点最短路由的算法，使用随机网络拓扑生成算法生成网络拓扑结构以验 证该算法的有效性和收敛性；最后对移动i p 中的时延问题进行了重点讨论，并使 用改进的算法对该时延进行优化。 1 4 本文的组织 论文的第一章阐述了移动i p 的研究现状和发展趋势，说明了本论文的主要工 作，并安排了论文的章节。 第二章主要研究了移动i p 技术的基本模型，对移动i p 的运行机制和工作原 理进行了分析，并讨论了移动i p 中使用的路由方案，最后介绍了网络仿真工具 n s 以及如何使用n s 对移动i p 网络进行模拟和性能分析。 基本遗传算法并不能适用于所有的实际问题，第三章讨论了基本遗传算法的 局限性和评价遗传算法的方法以及遗传算法的改进和应用，然后给出了将改进后 遗传算法应用到网络路由中的数学模型。 在第四章中分析了现有求解最短路由的网络模型并对其进行了分解，将一个 复杂的路由问题划分为多个子问题进行求解，并使用一种改进的遗传算法求解移 动i p 网络路由问题中特有的通过多个指定节点的最短路由问题，然后使用随机网 络模型对该算法进行分析。 第五章给出了移动i p 代理切换时延的数学模型，并将模拟退火的思想引入到 过多个指定节点的最短路由遗传算法中，从而克服了遗传算法固有的易陷入局部 最小和早熟的缺点，实验表明该算法能够取得较好的效果，并将该算法用于优化 移动i p 代理切换时延。 4 第二章移动i p 及仿真 随着无线网络技术的发展，传统i p 网络的选路方案和寻址方式己不能满足终 端移动性的需求，因此必须寻找一种能够实现移动网和固网结合，即移动整合 ( f i x e d m o b i l ei n t e g r a t i o n ，f m ) 技术来解决移动性管理( m o b i l em a n a g e m e n t ， m m ) 的问题。移动i p 技术是解决该问题的有效方案，它是实现移动互联网的核 心技术，对它的研究已经成为移动互联网络发展的重点。由i e t f 提出的移动i p 协议能够对互联网络( i p 网络) 中移动主机的动态路由迸行管理，它采用代理和 隧道技术来支持移动节点( m o b i l en o d e ，m n ) 的移动性。m n 使用一个固定的 i p 地址并在跨越不同网段的漫游过程中始终保持它与网络中其他主机的通信不中 断。 2 1 移动l p 概述 2 1 1 移动i p 功能实体 移动i p 定义了三种功能实体：移动主机、 代理和外地代理统称为移动代理( 图2 1 ) 2 8 1 。 访闫井她链路的移动节点 家乡代理和外地代理1 5 脚印1 。家乡 家乡链路上的移动节唐 外地代理 图2 1 移动i p 功能实体和关系 移动节点( m o b i l en o d e ，m n ) 是指一个装有支持漫游功能软件的蜂窝式电话、 p d a 或主机。当它在切换链路时可以不改变i p 地址而仍能保持正在进行的通信； 家乡代理( h o m e a g e n t ，h a ) 是指一个连接到移动节点本地链路的主机或路由器， 5 它保存有移动节点的位置信息，当移动节点离开本地网络时家乡代理能够将发往 移动节点的数据包转发给移动节点；外地代理( f o r e i g n a g e n t ，f a ) 是指移动节点 当前所在的外地链路上的一个主机或路由器，它能够把由本地代理送来的数据包 转发给移动节点。 除了如上三个功能实体外移动i p 还定义了如下名词8 ”： 1 家乡链路( h o m en e t w o r k ，删) ：该链路上的网络前缀与移动节点家乡地 址的网络前缀相同； 2 外地链路( f o r e i g nn e t w o r k ，f n ) ：非移动节点家乡链路的网络链路。 移动节点拥有两个i p 地址，一个为家乡地址，是指“永久”分配给移动节点 的地址，当移动节点切换链路时，家乡地址并不改变。家乡地址的网络部分代表 了移动节点所在的家乡链路。另一个地址称为转交地址( c a r e o fa d d r e s s ) ，它是 移动节点在外地链路上时由外地代理分配的临时i p 地址，该地址标示了移动节点 当前的物理连接位置。转交地址可以是外地代理的i p 地址称为外地代理转交地址 ( f o r e i g n a g e n t c a r e o f a d d r e s s ) ，也可以是暂时分配给移动节点某个端v 1 的i p 地 址称为配置转交地址( c o l l o c a t e dc a r e o f a d d r e s s ) 。 2 1 2 移动i p 的工作原理 移动i p 工作过程主要有如下三个阶段”o ： i 代理发现( a g e n td i s c o v e r y ) ：移动节点发现它的外地代理和家乡代理。 2 注册( r e g i s t r a t i o n ) ：移动节点向代理注册它的当前位置。 3 隧道( t u n n e l i n g ) ：当移动节点漫游到外地链路时，家乡代理和转交地址 ( 移动节点在外地链路上的当前位置) 之间建立双向隧道用来路由数据包。 每个移动节点在“家乡链路”上有唯一的“家乡地址”。与移动节点通信的节 点被称为“通信对端”，通信对端可以是移动的，也可以是静止的。通信对端与移 动节点通信时，通信对端总是把数据包发送到移动节点的家乡地址，而不考虑移 动节点当前的位置情况。在家乡链路上每个移动节点必须有一个“家乡代理”来 维护自己当前的位置信息，这个位置由“转交地址”来确定。移动节点家乡地址 与它当前转交地址的联合称为“移动绑定”，或简称为“绑定”。每当一个移动节 点得到一个新的转交地址时，它必须生成一个新的绑定来向家乡代理注册，以使 家乡代理及时了解移动节点当前的位置信息。一个家乡代理可以同时为多个移动 节点提供服务。 当一个移动节点连接到家乡链路之外的“外地链路”时，可以通过下述两种 方法来获得转交地址。通常情况下移动节点使用“代理发现”协议在外地链路上 发现一个“外地代理”，然后移动节点向这个外地代理进行注册，并使用此外地代 理的i p 地址作为自己的转交地址。外地代理的主要功能是为这个移动节点转发数 据包。另外移动节点也可以通过其他方法( 如d h c p ) 在外地链路上获得一个临 时i p 地址来作为自己的转交地址，在这种情况下移动主机可以作为自己的外地代 理。当移动主机离开家乡链路时，它的家乡代理把发往移动主机的所有数据包转 发到移动主机的当前位置。家乡代理可以使用“代理a r p ”或其他有效方法在家 乡链路上截获发往移动主机的数据包。对于每个截获的数据包，家乡代理使用隧 道技术把它们发送到移动主机的当前转交地址。如果转交地址是外地代理的i p 地 址，那么这个外地代理是隧道的终端，此时外地代理从数据包中移走隧道报头， 并把剩余部分发送到移动主机。如果移动主机使用一个临时地址作为转交地址， 那么数据包将直接通过隧道传送到移动主机( 图2 2 ) 。 通信节点 图2 2 移动i p 数据包转发 2 1 3 移动i p 漫游 移动i p 提供了网络节点移动的透明性，即通信对端不需要知道移动节点的当 前位置，它只是向移动节点的家乡地址发送数据包。同时移动节点也不需要了解 目前所在位置与i p 地址的对应关系。 移动i p 的家乡代理和外地代理都会周期性的发送代理广播消息( a g e n t a d v e r t i s e m e n t ) ，使得该链路上的移动节点可以判定链路上是否有代理存在。如果 有则判定它们的标识和功能是什么。移动到一个新的外地链路上的移动节点也可 以主动发送代理请求消息( a g e n ts o l i c i t a t i o n ) ，促使链路上的所有代理都发送一 个代理广播消息通报有关代理的信息。移动节点通过这些代理的广播消息可以判 断自己是在家乡链路还是在外地链路。当它在家乡链路上时，移动节点就可以像 固定节点一样工作，不再需要移动i p 的其它功能。同时移动节点还可以通过这些 代理广播消息确认自己是否从一个链路移动到了另一个链路( 图2 3 ) 。 7 图2 3 移动节点漫游 2 1 4 移动i p 的数据传送 移动节点的通信对端向移动节点发送的数据包首先被路由到移动节点的家乡 网络，家乡网络中的家乡代理截获此数据包，通过查找注册信息找到移动节点的 当前转交地址，家乡代理通过隧道技术将数据包封装后发往移动节点的转交地址， 拥有转交地址的实体将数据包解封，然后交给移动节点。 在外地链路中的移动节点一般选择外地代理为默认的路由器，移动节点将需 要发送的数据报文直接交给外地代理，由外地代理负责将数据包路由到相应的目 的地。 从上可以看出在移动i p 路由过程中外地代理和家乡代理扮演了主要的角色。 同时移动节点家乡代理和外地代理间的通信也是非常重要的”。 2 1 5 移动i p 路由方案 传统的i p 选路机制适用于固定主机的路由管理，而移动节点的路由是一种动 态路由，因此，移动i p 网络中的移动性管理必须具备对移动节点动态的管理机制。 为此先后提出了三种解决方案：特定主机路由技术、源路由技术和隧道技术，来 解决移动节点的移动性问题。 特定主机路由技术是相对于现有的i p 网络中的网络前缀路由而言的，它在路 由器中为每一个主机建立一个路由表项，根据每一个特定主机的i p 地址对数据包 进行选路。如果移动i p 使用特定主机路由技术解决移动节点的移动性，至少要在 移动节点的家乡网络到移动节点拜访的外地网络之间所有的路由器上建立特定主 机路由。使用特定主机路由的突出缺点就是需要发送大量的路由信息。特定主机 路由的数量取决于移动节点的家乡链路到移动节点访问的外地链路之间路由器的 数目，这些路由器的数量通常可以达到数百个。因而每一个移动节点在移动位置 8 后至少要向数百个节点发送特定主机路由。而且，移动节点往往需要经常改变其 接入因特网的位置，同时切换链路以后必须要发送路由更新消息。在最坏的情况 下，每一次改变链路，移动节点原先路径上的特定主机路由都将被改变。如果链 路的切换很频繁，因特网带宽将被这些路由更新信息消耗掉。而使用隧道技术则 只需改变隧道入口和隧道出口这两个路由器中的路由表项就可以了，因而远远少 于特定主机路由下的路由信息。当移动节点的接入位置发生变化时同样只要更新 这两个节点上的路由信息就可以了，而不用对移动节点的家乡链路到拜访的外地 链路之间所有路由器都发送路由更新消息，从而有效地减少了因特网上的路由更 新消息的数量。 源路由技术使用了在i p 头中定义的一个可选项：l o o s es o u r c ea n dr e c o r d r o u t e 4 ”。这个可选项中列出了一个或者多个中间目的地址，要求数据包在到达最 终目的地址之前必须经过这些中间地址。移动节点要发送一个数据包给通信对端 时需要在数据包的l o o s es o u r c ea n dr e c o r dr o u t e 中加入自己目前所连接的外地 网络的路由器的地址，接收方接收到该数据包后将l o o s es o u r c ea n dr e c o r dr o u t e 选项中的中间地址取出，并按照其相反的方向将数据包按照移动节点选定的路由 送往移动节点。使用源路由技术时i p 数据包需要因特网上所有路由器都进行额外 的处理，即每一台转发数据包的路由器都要判断自己的i p 地址是不是该数据包的 一个中间地址，然后进行相应的处理。实践表明，处理经过的数据包相对于转发 而言速度上相差一个数量级，这样的性能恶化是不能忍受的，而且出于安全性的 考虑防火墙可能会拒绝使用i p 源路由选项的数据包。 隧道是将一个数据包封装在另一个数据包的净荷中进行传送时所经过的路 径。采用隧道技术将发送给移动节点的数据包封装后转发到一个中间节点，然后 由此中间节点解封后再将恢复出来的原始数据包转发到移动节点。在一个隧道中 涉及到两个实体：封装节点和解封节点，通常将封装节点称为隧道的入口，解封 节点称为隧道的出口。在移动i p 中隧道的入口是移动节点的家乡代理，出口是移 动节点的转交地址。任何一个节点只要知道移动节点的家乡地址就可以和它建立 通信连接。移动节点更换了位置以后只要通过注册机制将移动节点的转交地址通 知家乡代理，家乡代理就可以通过隧道将发送给移动节点的数据包转发到移动节 点的转交地址，进而转发到移动节点。 2 2 网络仿真 2 2 1 网络仿真的意义 由于规模、资金和其他一些条件的限制，在真实的网络环境下进行网络实验 是非常困难的。因此，使用数学建模和统计分析的方法模拟现实条件下的网络环 9 境就成为进行网络研究的必要工具9 。通过使用该工具可以获取在特定的网络环 境下网络特性的详细参数。 网络仿真建模主要包括网络建模( 网络设备和通信链路等) 和流量模式建模 两个部分。网络仿真可以模拟网络流量在实际网络中的传输、交换和复用的过程。 通过网络仿真可以获取网络全局性能统计量，网络节点的性能统计量，网络链路 的流量和延迟等，从而可以得到某些业务层的统计数据，又可以得到协议内部的 某些特殊参数的统计结果。网络仿真以其独有的方法为网络的规划设计提供客观， 可靠的定量依据，缩短网络建设周期，提高网络建设中决策的科学性，降低网络 建设的投资风险。现在，研究人员普遍使用仿真技术来预测复杂网络的预期性能， 了解新协议的行为，性能和相互作用，研究新的算法性能。 1 9 9 4 年，n o r o n h a 等人在研究组播路由算法时证明：路由算法在随机生成的 网络拓扑下的仿真性能与实际应用性能基本相同”“。 1 9 9 9 年，e s t r i n 指出：采用建立网络测试模拟系统的方法虽然会丢失一些细 节信息，但它具备更好的灵活性和共享性p 2 0 。 以上的研究无疑为使用仿真工具进行网络性能模拟提供了理论依据。 2 2 2n s 仿真工具 n s ( n e t w o r ks i m u l a t o r ) 9 ”是针对网络研究的离散事件模拟器。n s 在有线和 无线( 本地和卫星) 网络上提供了对t c p 、路由和多播协议的模拟。1 9 8 9 年，n s 是作为一个r e a l 网络模拟器项目开始。1 9 9 5 年，n s 的开发获得了d v r p a 的支 持，通过v i n t ( v i r t u a li n t e r n e t w o r kt e s t b e d ) 项目，由l b l ，x e r o xp a r c 、u c b 和u s c i s t 合作进行。目前n s 的开发由d a r p a 的s a m a n 项目和n s f 的 c o n s e r 项目的支持。n s 具有开放性的结构和良好的可扩充性，并从其他研究者 那里吸收了丰富的模块，包括u c bd a e d e l u s 和c m um o n a r c h 计划以及s u n 微 系统公司获得的无线代码。目前n s 2 0 版已经发布，该模拟器以其强大的网络仿 真性能和源码开放性得到了广泛的应用。 n s 是一个离散型事件仿真器。简单的说，事件规定了系统状态的改变，状态 的修改仅在事件发生时进行。在一个网络仿真器中，典型的事件包括事件到达、 时钟超时等。仿真时钟推进由时间发生量确定。仿真处理过程的速率不直接对应 于实际时间。一个事件处理可能又会产生后续的事件，仿真器就是不停地处理一 个个事件，直到所有的事件都被处理完或某一特定的事件发生为止。 n s 用相关的两个类来实现网络模拟，一个在c + + 中实现，一个在o t c l 中。 这种方式被称为分裂对象模型。构件的主要功能通常在c + + 中实现，o t c l 中类主 要提供c + + 对象面向用户的接口。用户可以通过o t c l 来访问对应c + + 对象的成员 变量和函数。c + + 对象和o t c l 对象之间通过t c l c l 的机制来关联的。这样使n s 1 0 仿真性能更强更灵活。一方面，c + + 是高效的编译执行语言，使用c + + 实现功能 的仿真，可以便仿真过程执行获得较好的性能。另一方面，o t c l 是解释执行的， 用o t c l 进行仿真配置，可以在不必重新编译的情况下随意修改仿真参数和仿真过 程，提高了仿真的效率。局时这种分裂对象模型增强了构件库的可扩展性和可组 合性。n s 中所体现的这些先进的设计思想使得n s 成为了一种实用的网络仿真器。 针对网络仿真，n s 已经做了大量的模型化工作。n s 对网络系统中一些通用 的网络实体已经进行了建模。相对于一般的离散型的仿真器来说，n s 的优势就在 于它有非常丰富的构件库，而且这些对象易于组合，易于扩展。用户可以利用这 些已有的对象，进行少量的扩展，组合出所要研究的网络系统模型，然后进行仿 真。n s 2 中支持移动i p 的仿真研究，同时具有无线通信网络、a dh o