（通信与信息系统专业论文）按需自组织路由算法的设计与仿真.pdf

电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 摘要 ( 无线移动自组织互联网络是结合了自组织网络的组网和移动蜂窝通信系统 中移动用户管理的特点的网络体系结构。这种结构的网络即具有自组织网络的组 网灵活而方便的特点，同时也使得移动用户的接入变得更容易。在这一体系结构 中，路由技术是能否实现这一设想的关键技术之一，本文介绍了一种针对无线移 动自组织互联网络而设计的按需组织路由算法，它可以针对无线移动自组织互联 网络的特点完成网路路由自组织和移动用户位置管理等路由功能。 本文从整体的角度介绍了无线移动自组织互联网络的系统体系结构，为自组 织路由算法的设计提供了全局的视野，然后对当前具有代表性的自组织算法做了 简单综述，从中吸取了很多有益的设计思路和经验，对按需自组织路由算法的设 计有很大的帮助。 按需自组织路由算法，顾名思义，是一种按需方式的算法，减少了在网络自 组织时算法对网络资源的消耗。同时它把负责网络路由的自组织和移动用户位置 管理两种独立的功能有机的结合起来，提高了路由算法的效率。本文详细描述了 按需自组织路由算法的操作与设计，并对其进行了仿真，验证了算法的有效性。 关键字：无线移动自组织互联网，路由技术，自组织路由算法，按需方式。 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 a b s t r a c t t h ew i r e l e s sm o b i l es e l f - o r g a n i z i n gn e t w o r k ( w m s n ) d e m o n s t r a t e s an e w k i n do fn e t w o r ka r c h i t e c t u r et h a tc o m b i n e sw i t ht h es e l f o r g a n i z a t i o no fa d h o cn e t w o r k sa n dt h eu s e rm a n a g e m e n to fc e l l u l a rn e t w o r k s t h u s , i tc a nb e e a s i l yd e p l o y e dw i t h o u tt h eu s eo fa n ye x i s t i n gn e t w o r ki n f r a s t r u c t u r ea n d m a k em o b i l eu s e r sm o r ec o n v e n i e n tt oa c c e s si t t h er o u t i n gp r o t o c o li so n eo f t h ek e yt e c h n i q u e st of u l f i l lt h en e t w o r k t h eo n - d e m a n ds e l f - o r g a n i z i n g r o u t i n g ( o s r ) a l g o r i t h mi n t r o d u c e d i nt h i s p a p e r i s d e v e l o p e d f o rt h i s s p e c i f i c e n v i r o n m e n t t h es y s t e mi n f r a s t r u c t u r eo fw m s ni sf i r s t l yd e s c r i b e di nt h i sp a p e rs o t h a tw ec a nu n d e r s t a n dt h ee n v i r o n m e n tt h o r o u g h l y t h e nav a r i e t yo f w i d e - k n o w na dh o c r o u t i n ga l g o r i t h m sa r es u r v e y e d i no r d e rt of i n do u tt h e s t r o n g p o i n ta n dw e a kp o i n to f t h e m ap e r f o r m a n c ec o m p a r i s o nb e t w e e n t h e m g i v e s ac l u et ot h ed e s i g no ft h eo s r a l g o r i t h m m s ta si t sn a m ei m p l i e s , t h eo s ra l g o r i t h mi s ak i n do fo n - d e m a n d d i s t r i b u t e da l g o r i t h m s ，w h i c hg r e a t l yr e d u c et h ec o s to fs e l f - o r g a n i z i n gi n w m s n c o m p a r e dw i t hp r o a c t i v er o u t i n gp r o t o c o l s a l s o i t i n t e g r a t e s t h e f u n c t i o no ff i n d i n gr o u t e sa n dt h eu s e rm a n a g e m e n ti n t oas i n g l ep r o c e s sa n d g i v e sm o r ee f f i c i e n c y i nt h i sp a p e r , w ed e p i c tt h em a n i p u l a t i o no ft h eo s r a l g o r i t h m a t l e n g t h a n da l s oas i m u l a t i o nw o r ko ni t , w h i c hd e m o n s t r a t e st h a t i tw o r k sw e l 】i nw m s n k e y w o r d s ：w m s n , r o u t i n g , o s ra l g o r i t h m ，o n d e m a n d i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：至整日期：3 年；月f 阳 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：董整 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 1 1 课题背景 第一章引言 自从十九世纪末意大利科学家马可尼和俄国科学家波波夫发现电磁波在通 信系统中的应用以来，无线通信经过一百多年来的发展已经成为当今世界通信的 主要方式之一。同时随着电子制造技术和数字处理技术超乎想象的发展，功能强 大并且便于携带的便携式电脑、个人数字助理和手机等电子产品的出现使得移动 用户之间的无线通信成为人们越来越迫切的要求，人们希望可以随时随地得到及 时可靠的数据通信服务。 如今实现移动用户之间的无线数据通信主要有两种模式。一种模式是利用已 有的蜂窝通信系统在传输语音的同时实现数据的无线传输，如现在很流行的 g s m g p r s 和c d m a 等系统【1 】。这种模式可以有效的利用现成的基站等基础 设施，在基站的覆盖范围内可以方便的实现数据的通信。但这种方式存在地主要 问题是移动用户在基站间切换的问题，这要求用户在切换的同时，不能有明显的 延迟和数据丢失。这种模式的另一个问题是它利用了蜂窝移动通信的基站等基础 设施，虽然带来了方便，但也限制了它可以实现有效通信的范围仅仅只能够在其 覆盖范围之内。 另外一种实现的模式则是由所有期望相互通信的移动用户组成一个移动自 组织网络，如图1 1 所示。移动自组织网络( m a n e t ) ，顾名思义它是由多个通 过无线链路连接的移动路由器以及与之相连移动主机组成的自治系统，网络拓扑 灵活而多变k 2 。移动自组织网络具有许多蜂窝系统没有的优点，如可根据需 求随时搭建，具有极大的灵活性和极好的抗毁性等。然而这些优点却也使得如何 实现网络的自组织成为一个非常困难的问题，也是当今许多大学和研究机构正在 研究的一个问题。 图1 1 移动自组织网络( m a n e t ) 电子科技大学硕士学位论文：按需自级织路由算法的设计与仿真 随着便携式笔记本和无线网络设备接口等电子产品的发展和普及，研究移动 自组织网络的条件越来越成熟。国家8 6 3 项目“无线移动自组织互联网技术及实 验系统研制”课题也正是在这一背景下设立的。 1 2 研究目的和意义 由于移动自组织网络具有灵活性大，拓扑变化快等特点，如何实现自组织网 络的路由算法成为自组织网络研究的一个重要课题。互联网工程任务组( i e t f ) 专门成立了移动自组织网络工作组在这一领域进行研究。现今已经有十多种白组 织路由算法提交到了该工作组，但至今仍没有一个协议能够成为正式的标准。 在所有这些已提交的算法中，主流的算法将所有参与自组织网络的节点都放 在平等地位，它们之间既有相互的通信，同时每个节点还承担着组网和为其它节 点中继的义务和责任。这种做法使得算法在维护网络拓扑有相当大的组网开销， 再加上移动网络使用的无线信道带宽较窄且是共享信道的方式，使网络的实际通 信能力受到很大的限制。 联想到无线通信的另一种模式蜂窝系统中的蜂窝概念的引入不仅解决了无 线信道的竞争问题，同时还减少了系统组网的开销，扩大了系统可容纳的用户数 【3 】。因此我们在考虑自组织网络的实现时，也想将网络分为两个层次：第一 层是具有路由和中继功能的路由器；另一层则是普通的用户节点，享受路由器提 供的中继服务，并不参与路由算法和其他节点的报文中继。这样的结构减少了参 加路由计算的节点数，从而减少了组网所需要的开销，同时也增加了网络的可扩 展性。“无线移动自组织互联网技术及实验系统研制”课题正是在移动自组织网 的网络体系结构、组网方式、通信协议、网络性能和移动用户管理等若干关键技 术和实现方法进行探讨，试图在无线移动自组织网络的研究领域闯出一条新路。 本文重点研究无线移动自组织网络的路由算法。 无线自组织网络不需要依赖于事先建设的基础设施( 如基站等) ，因此可以 设置在任意没有基础设施存在的地方。它的这一特点使得网络的建设变得易于把 握，可控性强，对移动用户设备没有特殊要求使得网络的通用性强。因此，网络 也具备了很好的通用性能和对多种应用场合的适应性： 尤其适用于无法建设基础设旋的环境，如事故灾难现场或者瞬息万变的战 场等具有极大的突发性和破坏性的场合。 ：此外，无线自组织网络还可以应用于临时性的组网，如展览会或者博览会 等会议场合。 无线自组织网络也是固定网络的非常有益的补充，成为有限接入的无线延 伸，扩大了无线局域网( w l a n ) 的覆盖范围，适用于校园网、企业网、 机场大厅等公共场合。 2 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 以上这些应用使得无线移动自组织互联网的研究与开发具有十分重要的意 义。而本文所涉及到的路由算法则是能否实现自组织网络的关键技术之一。 1 3 论文章节 本文第一章首先介绍了国家8 6 3 项目“无线移动自组织互联网技术及实验系 统研制”的课题背景，阐述了本课题的研究目的以及意义。第二章详细描述了无 线移动自组织互联网的体系结构，包括网络结构、无线信道及通信方式、通信协 议体系与编址和自组织路由算法几个部分。 从第三章开始本文把主题集中在本课题的路由算法这一关键技术上。第三章 阐述了无线自组织路由算法的现状，对现有的一些自组织算法进行了简要介绍， 并根据国外相关的仿真结果找出对本课题具有重要意义的相关算法和思路。本文 在第四章中叙述了我们根据无线移动自组织互联网的特点设计的按需自组织路 由算法，详细描述了算法的操作过程。第五章的内容包括按需自组织路由算法的 仿真，对其进行基本功能的检验。最后的结论对本文在课题中所做的工作进行一 个全面的总结，并给出下一步需要进行的工作。 1 4 缩略语 a b r a o d v a p a r p c b r p c d m a c e d a r d s d v d s r d w h d w r g p r s g s m g s r h l r i a r p i b s s a s s o c i a t i v i t yb a s e dr o u t i n g a d - h o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g a c c e s sp o i n t a d d r e s sr e s o l u t i o np r o t o c o l c l u s t e rb a s e d r o u t i n g p r o t o c o l c o d ed i v i s i o nm u l t i p l ea c c e s s c o r e - e x t r a c t i o nd i s t r i b u t e da d - h o cr o u t i n g d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e e t o r d y n a m i cs o u r c er o u t i n g d e s t i n a t i o nw i r e l e s sh o s t d e s t i n a t i o nw i r e l e s sr o u t e r g e n e r a lp a c k e tr a d i os e r v i c e g l o b a ls y s t e mf o rm o b i l ec o m m u n i c a t i o n s g l o b a ls t a t er o u t i n g h o m el o c a t i o n r e g i s t e r i n t r a z o n er o u t i n gp r o t o c 0 1 i n d e p e n d e n tb a s i cs e r v i c es e t 皇三型苎查堂堡主堂垡兰苎! 垫笪鱼塑塑堕虫兰堡盟塑盐兰堕塞一 i c i i n t e r f a c ec o n t r o li n f o r m a t i o n i c m pi n t e m e tc o n t r o lm e s s a g e p r o t o c o l i e r p i n t e r z o n er o u t i n gp r o t o c o l i e t f i n t e r a c te n g i n e e r i n gt a s kf o r c e i p i n t e r a c tp r o t o c o l i w r i n t e r m e d i a t ew i r e l e s sr o u t e r m a cm e d i aa c c e s sc o n t r 0 1 m a n e tm o b i l ea d h o cn e t w o r k m d sm i n i m u md o m i n a t es e t m p rm u l t ip o i n tr e l a y o l s r o p t i m i z e d l i n ks t a t er o u t i n g o s r o n d e m a n ds e l f - o r g a n i z i n gr o u t i n g q o sq u a l i t y o fs e r v i c e r e r rr o u t ee r r o r r r e pr o u t e r e p l y r r e q r o u t e r e q u e s t s ks i m u l a t i o nk e r n e l s t ds t a t et r a n s i t i o nd i a g r a m s ，hs o u r c ew i r e l e s sh o s t s w rs o u r c ew i r e l e s sr o u t e r t c pt r a n s m i s s i o nc o n t r o lp r o t o c o l t d m at i m ed i v i s i o nm u l t i p l ea c c e s s t o r a t e m p o r a l l y o r d e r e dr o u t i n g a l g o r i t h m u d pu s e rd a t a g r a mp r o t o c 0 1 v l rv i s i t o r s l o c a t i o nr e g i s t e r v rv i r t u a lr o u t e r v r r pv i r t u a lr o u t e rr e d u n d a n c yp r o t o c o l w a m i sw i r e l e s sa d a p t i v em o b i l ei n f o r m a t i o ns y s t e m w hw i r e l e s sh o s t w l a nw i r e l e s sl o c a la r e an e t w o r k w m s nw i r e l e s sm o b i l e s e l f - o r g a n i z i n gn e t w o r k w rw i r e l e s sr o u t e r z r pz o n er o u t i n gp r o t o c o l 4 第二章无线移动自组织互联网系统总体设计 本课题所要实现的移动自组织网络有两个主要功能目标：既能够满足通用计 算机系统之间相互进行无线通信的需求，同时也能够让接入该网络的计算机使用 互联网业务。为此我们针对移动自组织网络的特点，并且在借鉴了蜂窝式移动通 信系统的组网的思想之后，提出了无线移动自组织互联网的自组织网络体系结构 ( 以下简称“移动互联网”) ，即在无线多跳网络上构建宽带的移动无线i p 网络 的技术体制和方案。 本章从整体的角度介绍了无线移动自组织互联网络的系统体系结构，详细阐 述了无线移动自组织互联网络的网络结构、无线信道设置、移动性假设以及自组 织路由等部分的设计与要求，为路由算法的设计提供了全局的视野。 2 1 网络结构 2 1 1 自组织网络的结构 自组织网络有两种结构：平面结构和分级结构【4 】。如图2 1 所示，左边的 自组织网络是一个平面结构的网络，而右边的则是一个二级结构的自组织网络。 平面结构中，所有节点地位平等，也被称为是对等式结构。与之相对的分级结构 中，网络被划分为多个簇( c l u s t e r ) ，每个簇由一个簇头( c l u s t e r - h e a d e r ) 和多 个簇成员( c l u s t e r - m e m b e r ) 组成。这些簇头组成了一个高一级的网络，而在这 个高一级的网络中又可以分簇，形成更高一级的网络，直至最高级。任意两个不 在一个簇之内的簇成员之间的通信都要通过各自的簇头来中转。 图2 1 平面结构v s 分级结构 平面结构的自组织网络结构简单，无需任何的结构维护过程。源节点和目的 节点之间可以存在多条路径，因此可以使用多条路径实现负荷分担，也可以为不 同的业务类型选择适当的路径，从而实现具有一定质量保证( q o s ) 的路由算法。 由于网络中所有节点是对等的，原则上不存在瓶颈，所以比较健壮。平面结构中 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 节点的覆盖范围比较小，相对较安全。平面结构的最大缺点是网络规模受限。在 平面结构中，每一个节点都需要知道到达其它所有节点的路由。由于节点的移动 性，维护这些动态变化的路由信息需要大量的控制消息。网络规模越大，路由维 护的开销就越大。当网络的规模增加到某个程度时，所有的带宽都可能会被路由 协议消耗掉。所以平面式结构网络的可扩展性较差。 分级结构的最大优点则是可扩展性好，网络的规模不受限制，必要的时候可 以通过增加簇的个数和级数来提高整个网络的容量。分级结构中，簇内成员的功 能相对简单，基本上不需要维护路由，这就大大减少了网络中路由算法对有限的 无线链路带宽的消耗。簇头的功能较为复杂一些，不仅需要维护到达其他节点的 路由信息，还要知道所有节点与簇的关系。但总的说来，在同样规模网络的条件 下分级结构的路由开销要比平面结构的小。如果簇内通信的信息流量在整个网络 的通信量中占较大比例的时候，各簇之间可以互不干扰地进行通信。同时于分级 结构给网络带来了不通的层次结构，可以在簇头实现功能较为复杂的q o s 路由算 法，使网络的流量实现较为均衡的分布，提高整个网络的吞吐量。当然分级结构 也有其缺点存在。首先维护分级结构的簇头选择算法较为复杂，需要仔细设计。 其次簇内的节点与簇外的节点进行通信时必须经过簇头，所得到的路由不一定是 最佳路由。 从上面的比较可以看出，分级结构的自组织网络比起平面结构具有一定的优 势。首先，分级结构有较好的可扩展性。其次，分级结构通过路由信息局部化提 高了系统的吞吐量。分级结构使路由信息局部化，簇内成员无须知道其他簇的拓 扑结构，一个簇的拓扑变化不会被其它簇的节点感知。这减小了路由控制报文的 开销。再次，分级结构中节点的定位要比平面结构简单得多。在平面结构中，想 知道一个节点的位置，需要在全网中执行查询操作。而在分级结构中，簇头知道 自己簇成员的位置，只要查询簇头就可以得到节点的位置信息。还有，分级结构 可通过移动性管理来实现序列寻址。按照节点与簇的关系为节点分配逻辑序列地 址，由簇头充当类似蜂窝移动通信系统中的归属位置寄存器( h l r ) 和访问位置 寄存器( v l r ) 功能的位置管理服务器，就可以简单地实现节点定位和寻址。另 外，分级后网络被分成了相对独立的簇，每个簇都有控制中心。基于有中心的 t d m a 、c d m a 、轮询等技术都可以在分级的网络中使用。基于有中心控制的路 由、移动性管理、网络管理技术也可以移植到移动自组织网络中来。较为典型的 例子如美国的无线自适应移动信息系统( w a m i s ) 项目【5 】，为了实现自组织 网络中多媒体信息的传输，采用了分级结构并使用了t d m a 、c d m a 等信道接入 技术。随着对自组织网络t g q o s 要求的提高，将基于有中心控制的技术结合到自 组织的分布式算法当中将会是较为明智的选择。因此在本课题的设计当中，我们 将移动互联网的网络结构设计成为分级结构。 6 皇! 型垫奎兰堡主兰垒笙茎! 望量鱼墨璺堕宣塞鲨塑堡生兰堕墨 2 1 2 移动互联网的网络结构 我们设计的移动互联网的网络分成两层，由无线路由器和移动用户组成( 见 图2 2 ) 。无线路由器之间相互平等，组成了一个典型的自组织网络作为无线移 动自组织网络体系的骨干网，称为移动互联网的“骨干层”。移动用户则以计算 机( 尤其是便携式计算机) 为主，通过8 0 2 1 1 无线接入技术实现宽带接入到无线 路由器，在无线路由器的覆盖区域内实现通过无线路由器中继的通信。所有的移 动用户则组成了移动互联网的“接入层”。 图2 2 移动互联网的网络结构 无线路由器( w r ) 是移动互联网的网络节点，其地位与前面讨论的分级结 构中的簇头相当。网络的自组织、拓扑构成、中继与路由、用户接入控制和管理、 与有线互联网互连等功能主要由无线路由器来实现。因此具有传统路由器的拓扑 发现和路由功能。但在移动互联网体系结构模型中，无线路由器在概念和原理上 又不完全是一个通常意义上的路由器，更适合于网络的自组织和移动特性。无线 路由器在其周围形成一个无线覆盖的区域，在这个区域内的移动用户可以通过该 无线路由器实现与其他节点的通信。多个无线路由器构成一种蜂窝状的覆盖区 域。无线路由器之间通过无线链路相连，以自组织方式形成如图2 3 所示的骨干 传输网络，为移动用户的通信提供无线路由器之间的路由选择和i p 报文的中继转 发。同时为了给接入的移动用户提供互联网业务的功能，无线路由器所组成的骨 干网还必须通过网关与有线网相连，实现移动互联网与i n t e m e t 的互联。 图2 3 自组织方式构成的i p 骨干网 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 在移动互联网中，我们所设计的移动用户与前面所讨论的分级结构的自组织 网络中的簇成员有一定差别。在现有的自组织网络协议中，无论是平面结构还是 分级结构，每个节点都要参与自组织路由算法的计算。因此所有要加入到自组织 网络中的计算机都必须安装相应的路由软件。而在移动互联网的体系结构当中， 为了减少对用户的修改，增加用户的通用性，将移动用户的节点都设计成为一般 的通用计算机( 即仅安装了通用的t c p f l p 协议体系的计算机) 通过安装标准的无 线局域网网卡接入到无线路由器上。因此移动用户实际上是具有无线移动通信能 力的用户主机，又将其称为无线主机( w h ) 。无线主机不参与网络拓扑的构成， 只是通过无线路由器接入并使用网络提供的可移动的通信服务。同时为了方便用 户的使用，移动用户可以在无线路由器所组成的骨干网覆盖的区域内自由移动， 由无线路由器上的路由算法来解决其在各个路由器之间切换的问题。图2 4 显示 了移动用户在无线路由器覆盖的范围内移动的情景。 图2 4 移动用户的接入与移动 两层体系结构与传统无线网络的a d h o c 组网结构相比，在相同数目的无线节 点情况下大大减少了参与自组织、动态路由算法的无线节点数量，也大大降低了 网络的组网开销，易于网络的扩展和管理。这种两层结构简化了网络内的通信、 路由和管理的复杂性，同时也更适合于移动互联网之间以及与有线互联网之间的 互连互通，使得移动互联网并不独立于现有的有线互联网系统，而是一起协同工 作。 2 2 无线信道及通信方式 基于上述的网络结构，移动互联网体系结构中所使用的无线信道与经典的自 组织网络有所区别。经典的自组织网络使用的无线信道都采用一个共享的无线频 段，相互之间的通信方式也基本相同。而在移动互联网中，无线路由器根据不同 的通信对象，无线信道的设置与通信方式也不一样。 b 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 2 2 1 信道设置 移动互联网使用两个不同频段的无线信道，无线路由器之间的通信使用的信 道称为“网络信道”，无线路由器与移动用户之间使用的信道称为“接入信道”。 因此为了实现路由和中继的功能，每个无线路由器至少配置有两个无线局域网网 卡，一个工作在网络信道( 以下称为“网络网卡”) ，另一个则工作在接入信道 ( 以下称为“接入网卡”) 如图2 5 所示。移动用户的计算机所配置的无线局域 网网卡则工作在接入信道。 将信道分为网络信道与接入信道使得移动用户与无线路由器之间的接入通 信和无线路由器之间的通信可以同时进行且互不干扰，减少了对无线链路的竞 争，扩大了系统的通信容量。另外，把接入通信和网络通信在功能上相互独立， 可以分别进行设计，也便于今后的升级和改进。 图2 5 无线路由器的双信道结构 网络信道由所有无线路由器共享的，并且负责传输不同无线路由器下接入的 移动用户之间的通信数据以及无线路由器用于计算路由的控制报文，因此，网络 信道需要较大的通信容量，必要的时候可以增加网络信道的数量，以提供一定的 传输质量保证。无线路由器的网络网卡配置成为i e e e 8 0 2 1 1 协议中的i b s s 模式 ( 即a d h o e 模式) 【6 】，可以同时与多个临近的无线路由器进行对等的通信。 无线路由器的接入网卡设置成为一个a p ，接纳其无线覆盖范围内的多个移动 用户。此外，无线路由器上的a p 同时还有一定的网络管理功能，可针对移动用 户的计算机的接入作必要的控制和管理。移动用户的计算机上的无线局域网网卡 工作在a p 模式 6 1 ，工作信道为接入信道。当移动用户在移动过程中从一个无 线路由器切换到另一个无线路由器的时候，可以自动的完成接入a p 的更换，从 而在物理层和链路层保证了通信的持续性，使得移动用户具有更大的移动性和自 由度。 9 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 2 2 2 通信方式 根据移动互联网的体系结构，移动用户的无线局域网网卡工作在a p 模式，与 其接入的无线路由器的接入网卡相关联。此时无线路由器的接入网卡扮演着无线 网桥的角色，因此移动用户所有的通信流量都直接发送到其接入的无线路由器， 即使两个移动用户在相互的无线网卡的发射和接受功率覆盖范围之内也无法直 接相互通信，需要经过无线路由器的接入网卡作为网桥中继。在同一个无线路由 器接入的多个移动用户共享一个接入信道，采用d f w m a c 技术共享使用该信道 【6 】。移动用户的主要通信方式包括移动用户之间的相互通信以及移动用户和 互联网中的节点之间的相互通信。 无线路由器在网络信道和接入信道上同样采用竞争方式共享无线带宽。网络 网卡工作在i b s s 模式下，同样采用d f w m a c 技术共享网络信道。接入网卡作为 无线路由器的接入a p ，负责接受和中继与之相关联的移动用户的网络流量。 2 3 通信协议体系与编址 2 3 1 通信协议体系 为了减少对移动用户接入的要求，使得通用计算机也可以方便的连入，并且 可以通过移动互联网使用互联网业务，我们在设计之初就选定了标准的t c p 1 p 协议体系作为移动互联网的通信协议体系。移动用户采用i p 协议接入到无线路由 器。无线路由器之间的数据传输和控制信息等也通过i p 协议传输。如图2 。6 所示。 图2 6 移动互联网的通信协议体系 但由于t c p i p 协议体系是为静态的有线网络设计的，而移动互联网具有移动 i o 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 性强、拓扑变化快等特点，因此这种设计为无线路由器的i p 编址、路由和分组转 发等技术带来了一定的挑战，需要对传统的基于i p 网络的编址机制、路由技术和 分组转发技术等进行修改，对传统的分组寻径思想进行一些革新。 2 3 2 管理域的设计 移动互联网由于其移动性必然采用无线通信方式，而作为无线通信的物理介 质无线电磁波可以穿透建筑物的墙壁等障碍物，因此任何一个处在该无线接口的 电磁波收发覆盖范围内的用户都可以从物理上接入该网络。这种开放式的无线通 信方式为无线网络的组网、管理和安全都带来了一些难题。在我们的设计中移动 互联网并不是任意移动用户都能接入的网络，只有授权的用户才有权限。同样， 并不是任意一个无线路由器都能加入移动互联网参与到网络的自组织和路由等 功能中，只有属于这个移动互联网的无线路由器才能参与合作。从管理的角度考 虑，我们将一个移动互联网设置成一个“管理域”。管理域由网络的管理者划分， 与无线路由器和移动用户的位置和拓扑无关。当网络规模增长时，可以通过增加 并互连多个管理域的方式扩展整个网络。管理域的设计在移动互联网的体系结构 中与i p 编址的设计是密切相关的。 2 3 3 移动互联网的i p 编址 基于t c p i p 协议体系的移动互联网对外部呈现为一个i p 子网，即同属一个管 理域的所有无线路由器和无线主机均采用i p 协议体系的编址技术，其i p 地址前缀 相同。从这个角度来说无线路由器不是一个标准意义上的路由器。这样设计的优 势在于，当一个无线主机从一个无线路由器移动接入到另一个无线路由器下时， 不需要改变i p 地址或采用地址转换技术，即用户在网络内移动通信时i p 地址保持 不变，从而在网络层保证了用户移动中通信的持续性和平等性。因为用户在通信 过程中一旦改变自己的i p 地址，根据i p 协议的定义通信过程必然中断；而采用地 址转换技术虽然不会中断用户的通信，但却隐藏了用户的真实i p 地址，限制了用 户的通信能力，如别人不能主动与该用户通信等。这种设计方案同时将移动互联 网与其它移动互联网或有线互联网之间的互连问题简化为i p 网络间的互连问题。 移动互联网的体系结构中包括两种i p 地址的编址方式：一种地址是互联网中 合法的i p 地址( 简称“全局地址”) ，另一种是内部使用的i p 地址( 简称“内部 地址”) ，见图2 6 。 根据移动互联网设计的要求，移动用户之间以及移动用户与有线互联网之间 必须能够互相访问，因此无线主机使用互联网的全局地址来标识。移动互联网内 的无线主机之间、无线主机与外部互联网之间的寻址方式按标准互联网的i p 寻址 方式来实现。 皇王型茎查兰堡圭兰竺堡奎! 垫墨! 望堡堕虫兰望塑堡生皇堕壅 无线路由器具有至少两种无线网络接口：连接其他无线路由器的网络信道接 口和连接移动用户的接入信道接口。另外，考虑到移动互联网与有线互联网的互 连需求，我们在为无线路由器增加了一个有线的以太网接口作为与有线网的互连 接口。下面就无线路由器的各个接口分别说明其i p 的编址设计。 网络信道接口的i p 编址 无线路由器的网络信道接口连接其它无线路由器，仅与移动互联网内的无线 路由器或管理节点互相通信，提供组网、路由和中继等功能，无线主机和互联网 中的节点并不访问无线路由器的网络信道接口。因此考虑n i p 地址( i p v 4 ) 的使 用效率问题，无线路由器的网络信道接口使用互联网的私有i p 地址内部地址 进行编址。无线路由器之间按标准的i p 寻址方式实现寻址。 接入信道接口的i p 编址 无线路由器通过接入信道接口与无线主机相互通信，使用与无线主机相同的 全局地址进行编址。 在传统的t c p i p 网络体系中，每个主机上都需要设置一个网络缺省网关的i p 地址。当主机与本子网内的主机通信时采用直接交付，即分组直接递交给目的主 机，此时缺省网关并不参与子网内的主机间通信过程。但是当主机与本子网之外 的主机通信时，则需要缺省网关参与进行中继，即分组先递交给缺省网关，由缺 省网关负责寻径并转发至目的主机。在跨子网通信的过程中，一旦改变了缺省网 关的i p 地址，基于t c p i p 协议的通信就必然要中断。因此要保证本系统中无线主 机移动时通信的连续性，除了不能改变无线主机自己的i p 地址外，也不能改变它 的缺省网关地址。在移动互联网体系结构中我们设计的无线主机的缺省网关地址 就是无线路由器的接入信道接口地址。 图2 7 虚拟路由器 但是在一个移动互联网中有多个无线路由器，它们同处在一个i p 子网中；同 电子科技大学硕士学位论文：按需自组织路由算法的设计与仿真 时每个无线路由器连接多个移动用户，而无线主机的移动性又使得其所接入的无 线路由器是不固定的。那么无线主机应该如何设置其缺省网关呢? 移动互联网的 设计中借鉴了以太网中多个路由器热备份技术【7 ，8 】的虚拟路由器( v r ) 概 念，将一个网络中所有无线路由器的接入信道接口映射到一个虚拟路由器接口 上，这个虚拟路由器才是一个标准意义上互连i p 网络的路由器( 见图2 7 ) 。 此时，移动互联网呈现这样一个整体效果：所有的移动主机如同接在一台路 由器的同一个网络接口上，不论接入哪个无线路由器，都用同样的方式与其它无 线主机( 本子网之内或者本子网以外) 实现基于t c p i p 的通信，即将自己的缺省 网关i p 地址设置成虚拟路由器接口的i p 地址。所有无线路由器的接入信道接口地 址对无线主机呈现为统一的一个i p 地址，但无线路由器之间以及无线路由器与管 理节点之间仍然使用其网络信道接口的内部地址以识别和区分不同的无线路由 器。 虚拟路由器接口的虚拟i p 地址作为移动互联网中所有无线主机的缺省网关 地址，参与不同i p 子网络主机问的t c p i p 通信，与无线主机进行全局地址的统一 编址，即与无线主机属于同一个i p 子网。 虚拟路由器除了需要分配一个虚拟i p 地址外，考虑通信过程中的a r p 过程， 我们还要为其分配一个虚拟的m a c 地址。因为每个无线主机都会在a r p 缓存中 将已获得的i p 地址与m a c 地址的映射保存一段时间，如果采用无线路由器接入 信道接口的真实m a c 地址做a r p 地址解析，那么当无线主机从一个无线路由器 移动到另一个无线路由器时仍会根据原来地址映射关系向的原来的无线路由器 发送分组，这就造成了通信的中断。虚拟m a c 地址的设置可以参考v r r p 协议中 虚拟m a c 地址：o o 0 0 - 5 e - 0 0 一0 1 - v r i d ，只是其中的v r i d 不是路由器的地址， 而是管理域的标识号。因为在移动互联网体系结构中管理域内的所有无线路由器 并不是v r r p 协议所中的备份关系，而是协同合作的关系。 有线互连接口的i p 编址 无线路由器的有线互连接口采用以太网技术与有线互联网相连，实现无线主 机与有线互联网的相互访问，因此与互联网上所采用的编址方案相同，在此就不 详细赘述了。 综上所述，无线路由器的网络信道接口地址、接入信道接口地址( v r 地址) 和有线互连接口地址分属三个不同的i p 网络，与各自不通的对象相连，实现了移 动互联网将无线主机与有线互联网相连的设计目标。 2 4 移动性设计 移动互联网比较传统的互联网最主要的特征就是其移动性。但是如果对于网 络中无线节点的移动特性没有一定的假设的话，系统和路由的设计将被迫考虑过 皇兰型堇奎兰堡主堂焦笙兰! 苎煎皂塑堡堕叟竺鎏竺鲨盐量堕壅 一 多且随意性很大的情况而无法实现。因此，我们在移动互联网的设计当中，根据 设计的目标和日常经验对无线主机和无线路由器的移动性做了合理的假设。 由于移动互联网的移动性主要针对用户的移动性，以提供用户最大限度的移 动性为目标来优化网络的设计，因此用户可在整个网络的覆盖范围内自由移动， 移动的频率和速度较快，至少应该可以达到人正常步行的速度。 无线路由器不是固定不动的，它们也可以在一定范围内移动。但是考虑到路 由器的功能主要是为移动用户提供接入和中继服务，因此我们假设无线路由器的 移动频率和速度都要小于移动用户。这种假设在一定程度上保证了移动互联网的 体系结构相对较为稳定，不会发生剧烈的动荡和变化。 2 5 自组织路由 在移动互联网中我们将网络的拓扑结构作如下定义：无线路由器之间相互通 信关系所构成的连接结构，与移动用户的位置无关。对于移动用户，则可以看成 是在网络拓扑结构上的某个节点上接入。按照这种定义，无线路由器的移动，会 造成网络拓扑的变化；而用户移动时，网络拓扑不发生改变，只是用户的接入点 发生了变化。 无线路由器需要及时感知网络拓扑结构的变化，并根据发生的变化对路由进 行调整。移动用户在无线路由器之间的接入点发生切换时，不会造成拓扑结构的 变化，但仍会引起到该用户的路由变化，网络中的节点一般无法感知这种变化， 因而不会对路由做出相应调整。这是传统的m o b i l ei p 技术在处理移动用户切换时 产生三角路由的原因 2 6 】。传统的m o b i l ei p 技术( 包括i p v 6 ) 需要采用家乡 代理和外地代理来处理这种路由。而在移动互联网的设计之初，我们就希望它能 摆脱家乡代理和外地代理的束缚，直接实现自组织路由。 在移动互联网中移动用户的移动虽然不会改变网络拓扑的变化，但是涉及到 其本身的数据传输时，仍然需要考虑路由的变化。因此在移动互联网中，实际上 自组织路由应该包括与无线路由器相关的路由和与无线主机相关的路由两个部 分。在这里我们不妨把与无线主机相关的路由称为“移动路由”，负责记录和计 算目的无线主机的接入位置并转发数据报文；而与无线路由器相关的路由则称为 “动态路由”，负责在无线路由器之间的选择一条最佳路径将需要数据传送到目 的端的无线路由器，如图2 8 所示。 1 4 电子科技丈学硕士学位论文：按箝自组织路由算法的设计与仿真 ，移动路由 _ 动态路由 图2 8 移动路由和网络路由 本文主要研究的是移动互联网的这部分内容，关于自组织路由算法的设计和 操作将在后面的章节中详细论述。 第三章无线自组织网络路由算法现状与分析 在设计移动互联网的自组织路由算法之前，我们应当首先考察一下当前已经 成为标准或者正在研究的各种路由算法的特点与优点，尤其是与本课题有较大相 似之处的移动自组织网络( m a n e t ) 的路由算法。经过分析和对比，我们可以 从中吸取有益的经验和思路，再结合移动互联网体系结构的特点和要求，才能设 计出我们所需要的自组织路由算法。 3 1 路由算法的概述 3 1 1 传统的路由算法 在网络中一个报文可能要经过多个节点的中转才能到达它的目的地，此时就 需要一个路由协议来实现网络中多跳转发的功能。路由协议有两个主要的功能： 在网络拓扑中寻找并选择一条从源到目的的最佳路径；按照所选的路径转发报文 到目的节点。第二个功能在概念上很直观，节点根据定的协议和数据结构( 如 路由表等) 就可以实现转发的功能。因此我们把主要的讨论放在寻路和选路的功 能上。 在传统的有线网络的路由协议中，经典的路由算法包括链路状态协议和距离 矢量协议两种。链路状态