（通信与信息系统专业论文）移动ad+hoc网络中虚拟骨干网技术的研究.pdf

北京邮电大学博士学位论文牛文摘要 中文摘要 近几年来，移动a dh o e 网络在国际国内得到了显著的重视，a dh o e 网络具 备无需基础设施、l 临时组网、动态网络拓扑和自组织的优点。使得其非常适合于 在会议、学术交流、灾难救援和恢复、家庭网络和战场军事指挥等环境使用。论 文主要对a d h o e 虚拟骨干网技术中的关键问题进行了研究，这些问题可以归纳为 以下三个方面的内容：1 ) a d h o e 虚拟骨干网的构建；2 ) a d h o e 虚拟骨干网的移 -1 动性管理；3 ) 基于虚拟骨干网的a dh o e 路由协议。 第2 章对a d h o e 虚拟骨干网技术进行了概述，介绍了用于构建虚拟骨干网的 单位圆图( u d g ) 模型下c d s 算法的理论基础；分析了无线m a c 协议的原理和 应用；对现有的c d s 算法和a dh o c 路由协议进行了综述和分析；提出了一种新 型的基于虚拟骨干网技术的a dh o e 网络体系结构。 第3 章集中讨论了虚拟骨干网的构建算法，提出了一种新的费率优先的分布 式近似m c d s 查找算法，并通过实例和仿真结果验证了该算法的优点；提出了一 种基于现有c d s 算法的增强的主节点负载均衡c d s 算法，通过仿真比较验证了 该算法对于改善a d h o c 虚拟骨干网负载均衡起到了显著效果。 第4 章集中讨论了虚拟骨干网的移动性管理，提出了一种基于虚拟骨干网节 点打开关闭的c d s 节点增加和删除算法；并基于节点打开关闭提出了一种虚拟 骨干网节点移动c d s 算法。通过仿真结果说明了算法的可实现性和效果。 第5 章主要介绍了虚拟骨干网的路由协议，提出了一种适用于a d h o c v b 的 虚拟骨干网分布式a dh o e 路由协议( v b d a r ) ，并将该协议与经典的a dh o c 路 由协议进行了仿真比较和分析；提出了一种基于a d h o e v b 的q o s 路由体系结构， 并对该体系结构进行了阐述和说明。 第6 章介绍了a d h o c v b 技术与移动i p 和m p l s 技术的结合，为a d h o e 虚拟 骨干网技术的进一步研究指明了方向。 1 【关键词】移动a d h o e 网络，虚拟骨干网，连接主节点集，路由协议，服务质量 北京邮电大学博士学位论文a b s t r a c t a b s t r a c t t h er e s e a r c ho nm a n e t ( m o b i l ea dh o cn e t w o r k s ) s h o w sm o r es i g n i f i c a n ti n r e s e n ty e a r s m o b i l ea dh o en e t w o r k sh a st h ef e a t u r e so fn of i x e d i n f r a s t r u c t u r e ， t e m p o r a r i l yn e t w o r k i n g ，d y n a m i ct o p o l o g ya n ds e l f - o r g a n i z a t i o n i tc a l lb ed e p l o y e d f o rc o n f e r e n c e ，a c a d e m i c ，d i s a s t e rr e l i e fa n dr e s c u e ，r o o fn e t w o r k sa n db a t t l e f i e l d s t h i st h e s i sm a i n l yd i s c u s s e st h ek e yt e c h n o l o g i e si nv i r t u a lb a c k b o n e b a s e da dh o e n e t w o r k s ，a n di tc a r lb ed e v i d e di n t ot h r e ep a r t s ：c o n s t r u c t i o na n dm o b i l i t yo fv i r t u a l b a c k b o n e ，v i r t u a lb a c k b o n eb a s e d a dh o c r o u t i n gp r o t o c o l s i n t r o d u c t i o n & v i r t u a lb a c k b o n e b a s e da dh o c r o u t i n gi sg i v e ni nc h a p t e r2 t h i s c h a p t e r i n t r o d u c e dt h e t h e o r y o fc d sa l g o r i t h m sb eu s e dt o b u i l d i n g v i r t u a l b a c k b o n e - b a s e dn e t w o r k si nu d g , a n a l y z e dt h ep r i n c i p l ea n d a p p l i c a t i o no f w i r e l e s s m a c p r o t o c o l s ，s u m m a r i z e de x i s t e dc d sa l g o r i t h m sa n da dh o cr o u t i n gp r o t o c o l s ， a n d p r o v i d e da n e wa r c h i t e c t u r eo fv i r t u a lb a c k b o n e b a s e da dh o cn e t w o r k s c h a p t e r 3 m a i n l y d i s c u s s e dt h ec o n s t r u c t i o n a l g o r i t h m s o fa dh o cv i r t u a l b a c k b o n e ，p r o v i d e dan e wc o s tp r i o r i t yd i s t r i b u t e da p p r o x i m a t ec d sa l g o r i t h ma n d s h o w e di ti su s e f u lb ye x a m p l e sa n d s i m u l a t i o n s p r o v i d e da ne n h a n c e dl o a d b a l a n c e d c d s a l g o r i t h mb a s e d0 ne x i s t i n gc d sa l g o r i t h m sa n ds h o w e dt h a tt h ep e r f o r m a n c eo f l o a d b a l a n c ei ss i g n i f i c a n t l yi m p r o v e d b y s i m u l a t i o n c h a p t e r 4 m a i n l y d i s c u s s e dt h e m o b i l i t y o fv i r t u a l b a c k b o n e ，p r o v i d e d a o p e n c l o s ec d sa l g o r i t h ma n dam o v i n gc d sa l g o r i t h mb a s e do nt h ef o r m e r t h e s e a l g o r i t h m sc a nb ei m p l e m e n t e da n dt h e r e s u l ti sv e r yg o o di ns i m u l a t i o n c h a p t e r5 i n t r o d u c e dt h ev i r t u a lb a c k b o n e b a s e dr o u t i n gp r o t o c o l s ，p r o v i d e da v i r t u a lb a c k o n eb a s e dd i s t r i b u t e da dh o c r o u t i n g ( v b d a r ) ，a n dc o m p a r e d w i t hc l a s s i c a dh o ep r o t o c o l s ，p r o v i d e daq o s r o u t i n ga r c h i t e c u r ea n dg i v e n t h ed e t a i l s c h a p t e r6i n t r o d u c e dt h ec o m b i n a t i o no fm o b i l ei p , m p l sa n da d h o cv i r t u a l b a c k b o n eb a s e d r o u t i n g ，i ts h o w s t h ef u t u r er e s e a r c h e so f a dh o cv i r t u a lb a c k b o n e k e y w o r d s 】m a n e t , v i r t u a lb a c k b o n e ，c d s ，r o u t i n gp r o t o c o l ，q o s i i i 北京邮电大学博士学位论文第1 章绪论 第1 章绪论 本章主要介绍了论文的研究背景、创新点和论文的组织结构。1 1 简单介绍了移动a d h o c 网络的定义、典型特征及其应用，以及a dh 6 c 虚 拟骨干网( a d h o cv i r t u a lb a c k b o n e ，a d h o e v b ) 技术的起源、研究意义和 发展前景；1 2 主要介绍了论文中具有挑战性的研究内容，并逐一列攀 了论文研究的创新点；1 3 阐述了论文的组织结构，介绍了各章节的主 要内容，可以清晰了解论文的总体思想。 1 1 研究背景及意义 现代通信技术的持续快速发展为未来通信勾画出这样一个神奇的画面：在建 筑物顶上；在飞机、轮船和汽车上：在电视、冰箱、空调、洗衣机等家用电器上； 在机场、车站、餐厅、影院；在我们每个人的手中，只要拥有任何一种无线通信 设备，无论它们是被固定在某个地方，还是在不断的移动、随时地打开或关闭， 都能自动和谐地组成一个移动通信网络，一切控制尽在掌中! 而创造这一切的将 是当前通信和计算机领域的研究热点无线移动a dh o c 网络技术、3 g 移动通信技 术、w l a n 技术、i p v 6 技术、移动m p l s 技术、移动i p 技术。未来的通信世界 取决于这些技术的发展、实现和相互融合。本文选择了无线移动a dh o c 网络技术 作为主要研究方向，并针对无线移动a dh o c 网络中的虚拟骨干网技术进行全面和 深入的研究。 无线移动a dh o c 网络是由无线移动节点组成的具有任意和临时眭网络拓扑 的动态白组织网络系统，每个节点可以作为主机和路由器使用。j o h n s o n 和m a l t z ， d s r ( a dh o c 动态源路由) 协议草案 1 】的作者，给出了无线移动a dh d c 网络的 定义：a na dh o cn e t w o r k i sac o l l e c t i o no f w i r e l e s sm o b i l eh o s t f o r m 啦a t e m p o r a r y n e t w o r kw i t h o u tt h ea i do f a n yc e n t r a l i z e da d m i n i s t r a t i o no rs t a n d a r ds u p p o r ts e r v i c e s r e g u l a r l ya v a i l a b l eo nt h e w i d ea r e an e t w o r kt ow h i c ht h eh o s t sm a yn o r m a l l yb e c o n h e c t e d ( a dh o c 网络就是由一组无线移动主机组成的临时| 生网络，该网络不需 要任何中央基础设施的管理，也不需要借助传统的将网络上的主机连接在一起的 广域网上可用的标准网络支持服务即可独立运行) 。 第1 章绪论北京邮电大学博士学位沦文 蔓曼皇皇曼皇罾曼皇蔓鼍e 曼蔓皇曼曼! 暑皇皇皇曼置鼍量曼曼兰曼皇暑! 曼置e 曼曼皇宝刍暑曼苎粤鼍鼍| 暑曼蔓些器望! 兰二一：；! ! a dh o c 网络的起源可以追溯到1 9 6 8 年的a l o h a 网络和1 9 7 3 年d a r p a 开 始研究的分组无线电网络 2 3 】。i e e e 在开发i e e e 8 0 2 1 1 标准【4 时，将分组无线 电网络改称为a dh o e 网络。a dh o e 来源于拉丁语，字面上的意思是“为特定目 的或场合的”。i e e e 希望a d h o c 网络成为为特定且的两临时组建并短期存在的曼譬 络。1 9 9 7 年，i e t f 正式成立了移动a d h o e 网络m a n e t ( m o b i l e a d h o e n ( 撕o l i 、 工作组，专门负责具有多个网络节点的移动a i dh o e 网络的路由算法的研埔祁开 发，并制定相应的标准。m a n e t 工作组的工作成绩斐然，已经制定了多个i n t e m e t 草案标准【1 【5 9 】。到2 0 0 3 年7 月，a o d v 协议草案已正式成为r f c 3 5 6 1 ，见参 考文献 1 0 。 移动a dh o c 网络近几年来在国际国内得到了显著的重视，a dh o c 网络具备 以下优点：1 ) 无需基站，可以快速组网：2 ) 临时性，网络的快速构建和擞除：3 ) 动态网络拓扑，任意网络节点的临时加入退出和随意移动：4 ) 自组织，不需要 中央控制。移动a dh o c 网络的这些特性使得其非常适合于不其备有线骨干嘲环境 下的应用。比如会议、学术交流、运动场、治安管理、家庭网络、灾难救援神恢 复、战场军事指挥等。 尽管移动a dh o e 网络的构想具有很多优点，但在实际应用中还存在很多j ；：足 之处【1 1 】： 1 )无线资源稀缺，包括带宽、电源和计算能力，在移动a dh o c 网络中，节点 通过带宽有限的共享信道进行通信，电池的能量也很宝贵，因此网络带宽和 电源等资源受限，此外，移动节点往往采用体积和功耗较小的处理芯片，；乜 制约了节点的计算能力； 2 )网络动态变化，a d h o e 网络最典型的特征就是网络节点可以随意移动，任总 打开或关闭，节点的这种移动性可能会导致频繁和无法预料的拓扑变化，网 络的快速和频繁变化使得节点之间的定位和网络路由协议变得非常复杂、难 以实现，还会大大增加额外的网络拓扑控制消息； 3 )缺乏中央管理，与有线网络或蜂窝网络不同，移动a dh o c 网络4 - ，没有0 翠 的骨干基础设施或中央管理系统，在移动节点大量增加时，分布式计7 翠莉管 理菲常困难。在现有a dh o c 路由协议中，所有节点都必须负责路盘计算鞠 路由信息的维护； 2 北京邮电大学博士学位论文第1 章绪论 综上所述，传统a d h o e 网络中基于全网扩散机制( 用于拓扑更新或路由请求) 的路由协议会产生广播风暴 t 2 1 ，大大降低网络资源的有效利用率，不仅会频繁 占用有限的网络带宽，耗费电池能量，还会严重影响移动节点的处理和转发能力。 因此，要想在获得a dh o c 网络优点的同时，尽量避免其不足之处，个典型的解 决方案就构建a dh o c 虚拟骨干网。 a dh o c 虚拟骨干网1 3 与有线网络中的核心网的功能一样，可以实现网络数 据的交换和路由功能。与传统a dh o e 网络的概念不同，a dh o e 虚拟骨干网由少 数节点组成，虚拟骨干网并不是主要用来实现数据的交换和转发，而是主要负责 a dh o c 网络路由的计算和维护。如果我们将路由数据包强制在网络的一小部分节 点上，则由于全局扩散导致的协议开销将会显著减少。这就是移动a dh o c 网络中 虚拟骨干网路由的基本思路。a d h o e 网络中虚拟骨干网技术的核心就是选取网络 的近似最小连接主节点集( c d s ) 构建虚拟骨干网，并通过骨干节点建立a dh o c 全网路由并响应网络的动态拓扑变化。 1 2 论文的创新点 论文主要对a dh o c 虚拟骨干网技术中的关键问题进行了研究，这些问题可以 归纳为以下三个方面的内容：1 ) a d h o e 虚拟骨干网的构建；2 ) a d h o c 虚拟骨干 网的移动性管理；3 ) 基于虚拟骨干网的a dh o c 路由协议。解决了以上三个方面 的问题，就可以实现基于a dh o e 虚拟骨干网体系结构的新一代无线移动通信系 统。论文的研究内容正是围绕这三个方面的问题展开的，并在前人研究成果的基 础上提出了自己的新观点、新算法和新解决方案： 在a dh o c 虚拟骨干网的构建方面： 1 ) 提出了一种新的费率优先分布式近似m c d s 查找算法，该算法用于a d h o e 虚拟骨干网的构建。算法的近似系数为8 ，消息复杂度为o ( n ) ，时间 复杂度为o ( n ) 。与几种经典的分布式近似m c d s 查找算法相比，该算 法性能在现有算法中较优，并且费率最低； 2 )提出了一种增强的主节点负载均衡c d s 算法。现有c d s 算法的一个共 同目标是最小化主节点的数量，而不考虑每个主节点可以承载的子节点 数，结果导致部分主节点承载过多的子节点。该算法可以动态分布式调 3 一 第1 章绪论 北京邮电大学博士学位论文 整每个主节点承载的子节点，避免负载过于集中，而且算法的实现简单 有效； 在a dh o e 虚拟骨干网的移动性管理方面： 3 )针对移动节点的开关特性，提出丁种新的简单有效的节点打开c d s 算法，并在其基础上进一步提出了种节点关闭c d s 算法。该算法是经 典a dh o c 虚拟骨干网构建算法的有效扩充，可以实现网络节点的灵活加 入和删除，而且算法与c d s 构建算法密切结合，为解决a dh o e 网络的 移动性管理问题打下了坚实的基础； 4 )针对移动节点的移动特性，提出了一种基于节点开关的节点移动算法。 考虑到a dh o c 网络节点的移动可以抽象为节点在移动的起始位置关闭 和在移动终点的打开。基于这种思想，我们可以通过节点开关算法简单 便捷地解决复杂的a dh o c 网络节点的移动性问题： 在a dh o c 虚拟骨干网路由协议方面： 5 )提出了一种适用于移动a dh o c 网络的基于虚拟骨干网的分布式路由协 议( v b d a r ) ，该协议以构成虚拟骨干网的节点作为路由和交换节点， 在少数骨干节点上运行d s r 或a o d v 等经典路由协议，由于执行路由 计算和维护的节点大大减少，该协议能很大程度减少路由信息在网络中 的传播，提高网络容量利用率，路由性能得到很大的提高； 6 ) 提出了一种v b d a r q o s 路由体系结构。该体系结构建立在a d h o c 虚拟 骨干网技术的基础上，利用骨干节点实现网络的q o s 特性，可以减少全 网节点都进行q o s 计算的复杂程度，并降低冗余消息的传递，该体系结 构能较好的解决a dh o e 网络中的q o s 问题； 在a dh o c 虚拟骨干网技术的扩展应用方面： 7 )在对a dh o c 虚拟骨干网体系结构进行深入研究的基础上，提出了移动i p 技术与a dh o c 虚拟骨干网技术、m p l s 技术与a dh o e 虚拟骨干网技术 结合应用的新思路。为a d h o c 虚拟骨干网技术未来的发展指明了新的方 向，并为a d b o c v b 技术的进一步研究奠定了基础； 4 北京邮电大学博士学位论文第1 章绪论 1 3 论文的组织结构 论文的其余部分安排如下： 第2 章对a dh o e 虚拟骨干网技术进行了概述，首先介绍了用于构建虚拟骨干 网的单位圆图( u d g ) 模型下c d s 算法的理论基础；接着分析了无线m a c 协议 中的隐终端和暴露终端问题，介绍了m a c a w 协议中本地广播和信标( 单播) 的 原理和使用；然后对现有的c d s 算法和a dh o e 路由协议进行了综述和分析；最 后提出了一种新型的基于虚拟骨干网技术的a d h o e 网络体系结构，在对此体系结 构进行分析的基础上提出了我们需要研究和解决的问题。 第3 章集中讨论了虚拟骨干网的构建算法，首先提出了一种新的费率优先的 分布式近似m c d s 查找算法，对该算法进行了详细的说明，并通过实例和仿真结 果验证了该算法的优点；然后针对现有c d s 算法的不足之处，提出了一种基于现 有c d s 算法的增强的主节点负载均衡c d s 算法，并对该算法进行了仿真和比较， 验证了该算法对于改善a d h o e 虚拟骨于网负载均衡所起到的显著效果。最后对虚 拟骨干网构建算法现有的研究成果和不足之处进行了分析，并提出了这个方面未 来的研究方向。 第4 章集中讨论了虚拟骨干网的移动性管理，首先提出了基于虚拟骨干网节 点打开关闭的c d s 节点增加和删除算法，并给出了算法描述和实例，通过仿真 结果说明该算法的可实现性和效果：然后基于节点开关算法提出了虚拟骨干网节 点移动c d s 算法；最后对虚拟骨干网的移动性管理的现有解决方案的研究成果和 不足之处进行了分析，并提出了这个方面未来的研究方向。 第5 章主要介绍了虚拟骨干网的路由协议，首先提出了一种适用于a d h o c v b 的虚拟骨干网分布式a dh o e 路由协议( v b d a r ) ，并将该协议与经典的a dh o c 路由协议进行了仿真e e 较和分析；然后给出了一种基于a d h o c v b 的q o s 路由体 系结构，并对该体系结构进行了阐述和说明；最后对现有的a d h o c v b 路由协议 的现有研究成果和不足指出进行了分析，并提出了这个方面未来的研究方向。 第6 章介绍了基于a d h o c v b 技术与其他技术的结合应用，主要提出了 a d h o c v b 技术与移动i p 的结合，以及a d h o c v b 技术与m p l s 技术的结合。为 a dh o e 虚拟骨干网技术的进一步研究指明了方向。 5 - 第1 章绪论 北京邮电大学博士学位论文 最后是结束语，介绍了论文的选题过程，研究经历和论文的主要内容，并给 出了自己对攻读博士学位的一些心得。 1 4 本章参考文献 【l 】jb r o c h ，d ，bj o h n s o n ，a n dd a m a l t z ，“t h ed y n a m i cs o u r c er o u t i n gp r o t o c o lf o rm o b i l ea d h o cn e t w o r k s ”，i n t e r n e td r a f td m f t - i e f f - m a n e t - d s r - 0 7 t x t , f e b 2 0 0 2 【2 j o h nj u b i na n dj a n e td t o m o w t h ed a r p a p a c k e tr a d i on e t w o r kp r o t o c o l s ”，p r o c e e d i n g s 0 ，旃ei e e e , 7 5 ( 1 ) ：2 1 - 3 2 ，j a n u a r y1 9 8 7 3 1j , m m c q u i l l a n ，i r i c h e r , a n de c r o s e n , “t h en e wr o u t i n ga l g o r i t h mf o ra r p a n e t ”，1 e e e z r a n s f l c t i o n so nc o m m u n i c a t i o n s ，2 8 ( 5 ) ：7 11 - 7 1 9 ，1 9 8 0 【4 i e e es t d 8 0 2 11 - 1 9 9 7 ，“w i r e l e s sl a nm e d i u ma c c e s sc o n t r o l ( m a c ) a n dp h y s i c a ll a y e r ( p h y ) s p e c i f i c a t i o n s ”，i e e e , i n e ，n e w y o r ku s a ，1 9 9 7 5 1m g e r l a ，x h o n ga n dgp e i ，“f i s h e y es t a t er o u t i n gp r o t o c o l ( f s r ) f o ra dh o cn e t w o r k s ”， i n t e r n e td r 妒d r a f t l e t f - m a n e t f s r - 0 3 t x t ，r u n 2 0 0 2 【6 m g e r l a , x ，h o n ga n dgp e i ，“l a n d m a r kr o u t i n gp r o t o c o l ( l a n m a r ) f o rl a r g es c a l ea d h o cn e t w o r k s “i n t e r n e td r 舒d r a f t - i e i f - m a n e t - l a n m a r - 0 5 t x l , n o v 2 0 0 2 7 】rgo g i e lm gl e w i s ，e l t e m p l i na n db b e l l u r , “t o p o l o g yd i s s e m i n a t i o nb a s e do n r e v e r s e - p a t hf o r w a r d i n g ( t b r p f ) ”- ，i n t e r n e td r 妒d r a f f - i e f f - m a n e t - t b r p f - 0 6 骶，n o v 2 0 6 2 8 】z j h a s s ，m ，r p e a r l m a na n dps a m a r , “t h eb o r d e r c a s tr e s o l u t i o np r o t o c o l ( b r p ) f o ra d h o cn e t w o r k s ”，i n t e r n e t d r a f ld r a f t - l o t f - m a n e t - z o n e - b r p 一0 2 t x t , j u l 2 0 0 2 9 z j h a s s ，m r p e a r l m a na n dp s a m a r , t h ez o n er o u t i n gp r o t o c o l ( z r p ) f o ra dh o c n e t w o r k s ”，i n t e r n e t | d 哪d r a f t i e t f - m a n e t - z o n e z r p - 0 4 t x t ，j u t 2 0 0 2 1 0 】c p e r k i n s ，e b e l d i n g - r o y e ra n ds d a s ，“a dh o co n - d e m a n dd i s t a n c ev e c t o r ( a o d v ) r o u t i n g ”，i e t f r e q u e s t f o r c o m m e n t s ：r f c 3 5 6 1 ，l u l 2 0 0 3 1 l 】s c o r s o na n dj m a c k e r , “m o b i l ea dh o cn e t w o r k i n g ( m a n e t ) ：r o u t i n gp r o t o c o l p e r f o r m a n c ei s s u e sa n de v a l u a t i o nc o n s i d e r a t i o n s ”，i e t fr e q u e s tf o rc o m m e n t s ：r f c 2 5 0 1 ， j a n 1 9 9 9 i 2 】s 一kn i ，y c t s e n g ，y - s c h e na n dj 一只s h e u ，“t h eb r o a d c a s t s t o r mp r o b l e mi nam o b i l ea d h o en e t w o r k ! ，p r o c m o b i c o m , s e a t t l e ，a u g 1 9 9 9 ，p p 1 5 1 - 1 6 2 ( 1 3 b d o s ，e s i v a k u m a r , a n d v i b h a r g h a v a n ， r o u t i n g i na d - h o cn e t w o r k su s i n gav i f f u a l b a c k b o n e ”，p r o c e e d i n g so f 6 t hi n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t e rc o m m u n i c a t i o n sa n d n e t w o r k s ( f c 3 n 9 7 ) ，p a g e s1 - 2 0 ，s e p t 1 9 9 7 6 北京邮电大学博士学位论文第2 章a dh o e 虚拟骨干网技术概述 i i 第2 章a dh o e 虚拟骨干网技术概述 本章对a dh o c 虚拟骨干网( a d h o c v b ) 技术的基本理论和体系结构 进行概述，并介绍前人的研究成果，对其进行分析和总结。本章主要分为 以下四个部分：2 1 主要介绍a d h o c v b 的理论基础，也就是单位圆图 ( u d g ) 模型下的主节点集的基本概念和基本定理：2 2 对现有连接主 节点集( c d s ) 算法进行了综述，简要介绍各种c d s 算法的基本原理和 思路，并分析其优点和不足之处；2 3 分析了a dh o c 网络的m a c 协议 存在的问题，介绍了无线多址接入冲突避免协议( m a c a w ) 的基本原理； 2 4 对现有a d h o e 路由协议进行了综述，对这些路由协议进行了分类， 并分别说明其特点；2 5 根据以上分析和总结提出了基于a d h o c v b 的 一种新型的a dh o c 网络体系结构，并指出了该体系结构中需要进一步研 究和解决的问题。 2 1 单位圆图( u d g ) 理论基础 尽管移动a d h o c 网络的特点是没有物理的骨干基础设施，但是可以通过单位 圆图( u n i t - d i s k g r a p h ，u d g ) 模型 1 】【2 】中的连接主节点集( c o n n e c t e d d o m i n a t i n g s e t ，c d s ) 中的节点来组成虚拟骨干网【3 】。我们假定移动a dh o c 网络中的所有 节点都分布在2 维平面，并且每个节点的最大传输范围都是相同的。这种移动a d h o e 网络的拓扑可以建立u d g 模型，该模型中两个节点之间有且仅有一条边。 u d g 模型的数学定义为g ( v e ) 。 在u d g 模型中，对于给定的图g ( v ，e ) ，c d s 就是一个连接的子图g ( v ，e ) ， 且v v 集合中的每个节点与v 中的某些节点相连，e 是由v 中的任意两个节 点之间的所有连接组成的集合，这样，通过c d s 节点集v 和边集合v ；就可以 连接u d g 中的所有节点。因此，从原理上讲，这种模型可以很好的实现基于c d s 的虚拟骨干网的构想。在理想情况下，c d s 集合中的节点数越小越好，但是，在 u d g 中寻找一个最小连接主节点( m c d s ) 是一个n p 困难问题 i 】【4 】 5 】 6 】。此 外，移动a dh o c 网络中任何节点都可能会在无法预料的情况下改变状态，从而导 致局部网络拓扑变化，因此c d s 查找算法的结构应该是分布式的。 ，一 第2 章a d h o e 虚拟骨干网技术概述北京邮电大学博士学位论文 2 1 1 单位圆图( u d g ) 的定义 传统的单位圆图( u d g ) 理论中给出了一种基于相交模型的单位圆图定义， 该理论致力于解决u d g 中一些经典的n p 困难问题包括：最大独立子集( m i s ) 【7 】、最大节点覆盖( m v c ) 8 】【9 】、最小着色( m c ) 【i 0 1 1 1 1 和最小主节点集( m d s ) 1 】等问题。为了便于a dh o e 网络建模，我们基于相交模型提出了一种临近模型 的单位圆图定义，主要研究最大独立子集( m i s ) 和最小连接主节点集( m c d s ) 问题。下面分别给出两种模型的单位圆图定义 1 】 2 】。 2 1 1 1 相交模型( i n t e r s e c t i o n ) 定义2 1 ：ag r a p h i sa u n i t d i s k g r a p h i f a n d o n l y i f i t s v e r t i c e sc a l lb ep u t i n o n e t o o n e c o r r e s p o n d e n c ew i t he q u i s i z e d c i r c l e si na p l a n ei ns u c h aw a yt h a tt w o v e r t i c e sa r ej o i n e db ya l l e d g ei fa n do n l y i ft h ec o r r e s p o n d i n gc i r c l e s i n t e r s e c t i ti sa s s u m e dt h a t t a n g e n t c i r c l e si n t e r s e c t ，w i t h o u tl o s so f g e n e r a l i t y , t h er a d i u so f e a c h c i r c l e i sa s s u m e d t ob e1 ( 假定以二维平面图 中的每个节点都有以该节点为中心的等半径的圆一一对应，当且仅当相 应的圆相交或相切时，图中的两个节点可以通过边相连，这样的图被称 为单位圆图( u d g ) 。不失一般性，每个圆的半径假定为单位1 ) 。 ，7 一一、j，7 、j 、，7 7 r = i 、一，7 图2 1移动a dh o c 网络中相交模型的单位圆图 在相交模型中，假定每个圆的半径为单位1 。可以得出，当且仅当两个单位 圆的中心距离不大于2 时，中心节点相连。也就是说，如果以a d h o c 网络节点的 传输距离的一半( r 2 ) 为单位1 ，则任意两个网络节点之间的距离小于等于2 时， 这两个节点可以相互通信。 8 北京邮电大学博士学位论文第2 章a dh o e 虚拟骨干网投术概述 2 1 1 2 临近模型( p r o x i m i t y ) 定义2 2 ：n o d e so f g r a p ha l ei no n e t o o n ec o r r e s p o n d e n c ew i t ha s e to f p o i n t si nt h e p l a n e ，a n dt w ov e r t i c e sa r ej o i n e db ya ne d g ei fa n do n l yi ft h ed i s t a n c e b e t w e e nt h ec o r r e s p o n d i n g p o i n t si sa tm o s ts o m es p e c i f i e db o u n d ( 单位圆 图( u d g ) 中的节点与平面中的点一一对应，当且仅当相应节点之间 的距离小于等于指定的边界值时，两个节点通过边相互连接，边界值为 单位1 ) 。 ，一一一、，一、 图2 2 移动a dh o c 网络中临近模型的单位圆图 在临近模型中，假定每个圆的半径为单位l 。可以得出，当且仅当两个单位 圆的中心距离不大于l 时，中心节点相连。也就是说，如果以a dh o c 网络节点的 传输距离r 为单位i ，则任意两个网络节点之间的距离小于等于1 时，这两个节 点可以相互通信。该模型可以更好的表现移动节点的传输距离与单位圆图中单位 半径之间的关系，因此，如无特殊说明，论文后面部分提到的单位圆图( u d g ) 均为临近模型的单位圆图。 2 1 1 3 移动a dh o c 网络的u d g 模型 在u d g 中，可以用g t ( ve ) 表示网络拓扑，v 表示节点集，e 表示边集。每 个节点都有一个唯一的标识( d ) 。当且仅当两个节点之闯的距离小于等于单位 距离时，我们称这两个节点为邻居。尽管在实际a d h o c 网络中，两个节点之间除 距离之外还有很多因素决定了两个节点之问能否直接通信。但是在a dh 虚拟骨 干网理论研究中，我们假定距离为给定节点之间能否直接通信的唯一条件。 在a d h o c 网络u d g 模型中，节点发出的消息可以被其所有邻居节点接收到。 节点的传输可以是对所有邻居节点的本地广播( b r o a d c a s t ) ，或者是专门针对某个 9 、心b7- ，一凄一 、v一迅裂v 戆 第2 章a d h o c 虚拟骨干网技术概述北京邮电大学博士学位论文 目的节点的单播( 也叫信标，b e a c o n ) 。在相同的传输范围内，同时只能有一个节 点发送数据。我们的研究只限于移动a dh o c 网络的异步系统模型，也就是说，每 个节点维护一个集合，该集合中包含其所有邻居节点的i d 。该集合通过节点周期 性的广播。h e l l o 信号来维护，从而建立全网拓扑。节点不需要保存其邻居节点 的位置信息，因此不需要使用全球定位系统t0 p s ) 或传感设备。消息的收发由 a dh o c 网络的m a c 层协议 1 2 1 负责处理和调度，由于数据传输是异步的，因此 不需要在所有节点之间建立同步时钟。在理论研究中，我们可以假定传输不出现 冲突。我们还假定数据包将按照发送的相同顺序被接收，假定u d g 模型下的连 接为恒定连接，如无特殊说明，不会异常中断。 2 1 2u d g 模型的主节点集( d s ) 定义2 3 ：考察u d g g = ( v ，e ) 的一个子集v ，v 包含在v 中，且v - - v 中的每个 节点都连接到v 中的某个节点上。则子集v 为集合v 的主节点集。 在单位圆图中，主节点集( d o m i n a t i n gs e t ，d s ) 的定义 1 】如上，也就是说， 通过主节点集v ，可以连接u d g 节点集v 中的所有节点。通常，我们将v 中的 节点称为主节点( 或父节点) ，v v ，中的节点称为从节点( 或予节点) 。移动a d h o c 网络u d g 模型中的d s 问题主要包含以下内容： 任意主节点集( a r b i t r a r yd o m i n a t i n gs e t , a d s ) 最大独立子集( m a x i m u mi n d e p e n d e n ts e t ，m i s ) t r i v i a l n o n t r i v i a l 连接主节点集( c o n n e c t e dd o m i n a t i n gs e t ，c d s ) 最小连接主节点集( m ：, n i m u mc o n n e c t e dd o m i n a t i n gs e t ，m c d s ) 所谓a d s ，就是满足u d g 模型d s 定义的任意集合，a d s 包含其他几种集 合。最大独立子集( m i s ) 是指d s 集合中的节点之间相互独立，也就是说，任 意两个d s 节点都不相连。而连接主节点集