（计算机应用技术专业论文）基于图论的移动ad+hoc网络分群算法研究.pdf

c l a s s i f i e di n d e x ：t p 3 9 3 u d c ： d i s s e r t a t i o nf 6 rt h em a s t e rd e g r e ei ne n g i n e e r i n g r e s e a r c ho na dh o cn e t w o r k c l u s t e r i n g a l g o r i t h m sb a s e d o ng r a p h t h e o r y c a n d i d a t e ： s u p e r 、埴s o r ： w a n g h u a i c a i p r o f l id a o q u a n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l 够：c o m p u t e re n g i n e e r i n g d a t eo fo r a le x a m i n a t i o n ：j u n e2 0lo u n i v e r s i 够：q i n g d a ot e c l u l 0 1 0 9 i c a lu n i v e r s i t y 基于图论的 青岛理工大学工学硕士学位论文 目录 摘要i a b s 乜a c t i i i 第1 章绪论l 1 1 研究的背景和意义1 1 2 国内外研究现状1 1 3 应用领域4 1 4 本文内容及其工作5 第2 章移动a dh o c 网络技术6 2 1 移动a dh o c 网络概述6 2 2 移动a dh o c 网络的特点6 2 3 移动a dh o c 网络的结构和协议栈8 2 4 移动a dh o c 网络关键技术1 1 2 5 本章小结1 2 第3 章a dh o c 网络中的分群算法1 3 3 1 移动a dh o c 网络分群概述1 3 3 1 1 移动a dh o c 网络分群的概念13 3 1 2 移动a dh o c 网络分群的标准1 3 3 2 移动a dh o c 网络分群的数学模型1 3 3 2 1 图论理论基础1 4 3 2 2 移动a dh o c 网络的u d g 模型15 3 3 移动a dh o c 网络分群算法16 3 3 1 移动a dh o c 网络分群算法的指标1 6 3 3 2 基于最小连通支配集的分群算法17 3 3 3 分群算法小结3 0 3 4 本章小结31 第4 章移动a dh o c 中一种新型的加权c d s 分群算法3 2 青岛理工大学工学硕士学位论文 4 1 算法的基础3 3 4 2 基于加权的分布式c d s 算法3 4 4 2 1 群首生成算法3 4 4 2 2 网关选取算法3 7 4 3c d s 算法的维护3 9 4 4 本章小结4 1 第5 章算法性能分析与仿真比较4 3 5 1 算法的性能分析4 3 5 2n s 2 网络模拟器4 4 5 3 仿真环境4 7 5 4 仿真实验结果与讨论5 2 5 5 本章小结5 4 第6 章结论与展望5 5 6 1 总结5 5 6 2 展望5 5 参考文献5 7 硕士期间发表的论文6 1 致谢6 2 i i 青岛理工大学工学硕士学位论文 摘要 无线移动a dh o c 网络是由一组带有无线通信收发装置的移动终端节点组成的 具有任意性和临时性的无中心、网络拓扑动态、自组网络系统，每个节点既是主 机又是路由器。移动a dh o c 网络具有自组织、可移动、多跳路由、展开速度快、 抗毁性强、不需要现有信息基础设施的支持等特点。因此被应用于军事通信、传 感器网络、紧急服务与灾难恢复、移动网络等领域。 本文首先研究了移动a dh o c 网络的特点、网络的结构、协议栈及相关问题。 由于移动a dh o c 网络与传统网络有着不同的特性，从而决定了它们的关键技术的 差异性。根据移动a dh o c 网络的结构和特点，着重从它的特有的连通方式研究了 移动a dh o c 网络的拓扑形成算法。a dh o c 网络的两种拓扑结构中平面结构比较 简单，在平面结构中所有节点的地位都是平等的功能也是相同的，原则上不会发 生瓶颈问题，相对比较安全。当网络节点增多时，为了控制开销、提高网络的可 扩展性，一般会选择分级结构，即寻求虚拟骨干网络。a dh o c 网络生成的虚拟骨 干网络一般采用树形和群两种结构。 其次，提出了采用图论的方式生成a dh o c 网络的虚拟骨干网。在无线自组网 中搜索主干节点和群首形成虚拟骨干网的过程类似于图论中的最小连通支配集和 最小支配集问题的求解过程。在连通支配集算法求解的过程中，由于在独立集的 连通阶段中新的支配节点的增加，使得算法在执行过程中造成节点之间环路的生 成，这样就增加了冗余支配节点的生成几率，也增大了主干网的维护成本。本文 采用回馈的思想，限制其环路的出现，从而减少网关节点的数量。 最后，通过n s 2 仿真软件对本文算法模型和a 1z o u b i 支配集构造算法模型进行 ，本文算法在时间复 b i 支配集构造算法。 青岛理工大学工学硕士学位论文 詈= 皇= 暑昌詈暑詈詈= 詈詈詈篁暑墨= 詈詈詈詈詈皇鼍暑詈皇皇皇皇冀詈詈詈詈詈詈詈皇詈詈詈詈葛暑= 暑晕詈詈皇詈昌皇皇鲁皇詈暑昌= 詈詈皇鼍皇晕暑皇寡詈皇暑毒曹暑= 詈皇 a b s t r a c t w i r e l e s sm o b i l ea dh o cn e 锕o r ki sad ) ，n 锄i ca dh o cn e t 、) i r o r kt o p o l o g ) ，s y s t e m ，h i c hi sm a d eu po fag r 0 1 l po fm o b i l et e m i n a ln o d e sw h i c ha r ed e v i c e sw i 也w i r e l e s s c o m m u n i c a t i o n 仃a n s c e i v e r t h es y s t e mi sa r b i 咖a n dw i t l l o u tac e n t r a l ，e a c hn o d eo f t h es v s t e mi sb o t l lah o s ta n dar o u t e r m o b i l ea dh o cn 鲍v o f k sh a v et 1 1 ef o u o w i n g c h a m c t i 耐s t i c s ： s e l f - o r g a i l i z i n g ，m o b i l e ，m u l t i - h o pr o u t i n gs t 叭e d f 瓠ta n ds t i o n g r e s i s t a n c et od e s t m c t i o n ，w i m o u tm es u p p o r to ft h ee x i s t i n gi n f o m a t i o ni n 丘a s m l c t u r e a n ds oo n t 1 1 e r e f o r et h e ya r eu s e di nm i l i t a 巧c o m m u n i c a t i o n s ，s e i l s o rn e 觚o r k s ， 锄e r g e n c ys e r v i c e sa n dd i s a s t e rr e c o v e r y ，m o b i l en e t 、) l ，o r k s ，e t c f i r s t t h ea r t i c l es t u d i e d 也es t r u c t u r e ，t h ec 1 1 a i a c t e r i s t i c so fm o b i l ea dh o c n 咖o r k sa n dk e yt e c l u l o l o 百e sr e l a t e d t h em o b i l ea dh o cn e 觚o r k sa n dt r a d i t i o n a l n e 伽o r k sh a v ed i f 衔e n tc h a r a c t 舐s t i c sw h i c hd e t e m i n et h e i rk e yt e c l l i l o l o g y s d i f 衔e n c e s b a s e do ni t so 、) l ms t m c 彻ea i l dc h a r a c t e r i s t i c so fm o b i l ea dh o c ，f - 0 s i n g o ni t su n i q u em o d ec o n n e c t i v i 够，也ea n i c l em a i l l l yr e s e a r c h e s 也et o p 0 1 0 9 yf o r m a t i o n a l g o r i t h mf o rt h ea dh o cn e t w o r k a dh o cn e t w o r kh a u s 似o1 ( i n d so ft o p 0 1 0 百c a l s 仃u c t u r e s n ep l a n es t m c t u r ei sr e l a t i v e l ys i m p l e i i lt 1 1 ep l a n es t m c 咖，a l lt h en o d e s h a v em es 锄ep o s i t i o na n de q u a l 血n c t i o n a l i t y ，a n dt h eb o t t l e n e c kw i l ln o to c c u r s p r i n c i p l e l y ，s oi ti sr e l a t i v e l ys a f c w i t ht 1 1 ei n c r e a s i n go fm em l m b e ro ft h en o d e si n t h en e 帆o r k h i e r a r c h i c a ls t r i l 曲盯e ：i su s a l l yc h o s e ni no r d e rt 0c o n t r o lc o s t s 锄di n c r e a s e n 酏w o r ks c a l a b i l i t y 。i na n o t h e rw o r d ，i ts e e k sav h t i l a lb a c k b o n en 酏w o r k t h ev i m l a l b a c k b o n e si na dh o cn e t 、v o r kc o m m o n l yh a v e 觚ol ( i n d so fs 仃u c t u r e s 一仃e ea n dg r o u p s e c o n d l y ，t h ep a p e rp r o p o s e dan e wa p p r o a c hu s i i l g 黟a p ht h e o r ) rt og e tv i m l a l b a d 出o n eo fa dh o cn e t w o r k s i i lw i r e l e s sa dh o cg r o u p ，廿l ep r o c e s st os e a r c ht h e 饥m k n o d ea i l dt h ev i m a lb a c k b o n ef o m a t t e dw i t l lt h eh e a dn o d e si ss i m i l a rt os o l v i n g p r o c e s so fm i n i m u mc o m l e 曲e dd o m i n a t i n gs e ta n dm i l l i m u md o m i n a t i n gs e tp f o b l e m i n 伊a p h 廿1 e o 巧a m o n gt h er e s o v i i l gp r o c e s so fc o l u l e 曲e dd o m i i l a t i n gs e ta l g o r i 曲m ，i t w i l le n l e r g es o m en e wc o i l l l e c t e dd o m i n a t i n gs e t sd u 血gt h ec o m l e “o no fi n d 印e n d e n t s e t s ，w h i c hm a yr e s u l t e di nt h ef o m a t i o no f1 0 0 pb e 帆e e i ln o d e s t h i sn o to n l y i n c r e a s e st h ep r o b a b i l i t yo fg e n c r a t i n gr e d u n d a n td o m i n a t en o d e s ，b u ta l s oi n c r c a s e d m a i n t e l l a n c ec o s t so ft h eb a c k b o n e s of e e d b a c ki d e ai su s e dt ol i m i tt l l ee m e r g e n c eo f i t s1 0 0 p ，a n dt h en u m b e r so fg a t e w a yn o d e si sr e d u c e d f i n a l l y ，p e r f o 订i l a n c ec o m p a r i s o ni s 昏v e l lb e 觚e e n o u ra l g o r i m mm o d e la i l d i i i 青岛理工大学工学硕士学位论文 1 1 研究的背景和意义 第1 章绪论 无线移动a dh o c 网络是由一组无线移动终端节点组成的具有任意性和临时 性网络拓扑的动态自组网络系统，网络中所有的移动终端节点都既是主机又是路 由器f 。该网络不需要任何的中央基础设施管理，也不需要借助传统的网络设施， 将网络上的主机连接在一起用广域网上可用的标准网络支持服务即可独立运行 【1 1 。无线移动自组网技术的出现距今已有3 0 年的历史，1 9 6 8 年美国建立了a l o h a 网 2 】，a l h o a 网络协议能够进行路由选择和管理，这为将来无线自组网的路由选 择的发展打下了基础。1 9 7 2 年，受到a l o h a 网络和早期固定分组交换网络开发 成功的启发，美国国防部高级研究计划署( d e f h s ea d v a n c e dr e s e a r e hp r 甸e e t s a g e n c y ，d a r p a ) 提出了开发分组无线网( p a e k e tr a d i on e 铆o r k ，p r n e t ) 3 3 的构 想，研究无线分组交换技术在军事环境下的数据通信中的应用。p r n e t 是一种多 跳网络，网络中的各个节点不需要直接连接，节点之间能够利用接力的方式，在 两个相距很远不能直接通信的节点之间实现直接通信，这样就解决了网络节点之 间的距离瓶颈问题。p r n e t 的成功为移动a dh o c 网络技术的可行性提供了有力 的依据。 随着i e e e8 0 2 。1l 【2 1 标准的开发，i e e e 将p r n e t 网络改名为移动a dh o c 网 络，也叫无线自组网络。1 9 9 7 年，i e t f ( i n t e m e te n 百n e 嘶n gt a s kf o r c e ) 成立了 m a n e t 工作组【3 】， 正t fm a n e t 工作组的成立是为了将移动a dh o c 网络路由 协议引入到当前的i i l t e n l e t 协议栈中。目前，已经完成标准化的路由协议有0 l s r 、 t b r p f 、a o d v 和d s r 等，这极大地推动了移动a dh o c 网络的发展和研究。 1 2 国内外研究现状 自上世纪9 0 年代以来，移动a dh o c 网络的研究已经从无线通信领域中的一个 小分支逐渐扩大到相对较独立的领域。目前，无论在国际上，还是在区域上( 欧洲 和亚洲等地区) ，周期性的a dh o c 网络学术会议日益增多。总结国内外研究现状， a dh o c 网络成果主要在以下几个方面： ( 1 ) 提出新的路由协议 4 ，5 6 1 。a dh o c 路由面临的主要挑战是传统的保存在结点 1 青岛理工大学工学硕士学位论文 中的分布式路由数据库如何适应网络拓扑的动态变化。新协议一般以广播或组播 方式建立网络路由，核心是减少广播风暴。目前，一般普遍得到认可的代表性成 果有d s d v 、w r p 、a o d v 、d s r 、t o r a 和z r p 等。源头性的创新性研究主要集 中在2 0 0 1 年以前，后续的成果多为这些协议的改进，目前，路由协议的研究仍然 是a dh o c 网络成果最集中的部分。不过，从实现的难度来看，这些协议离适用性 还有一定的距离。 ( 2 ) 提出基于a dh o c 网络的媒体接入控制( m a c ) 协议【5 1 。主要是解决隐藏终端 和暴露终端问题，影响比较大的有m a c a 协议，即r t s c t s a c k 方案，控制 信道和数据信道分裂的双信道方案和基于定向天线的m a c 协议，以及一些改进类 的m a c 协议。通常可以将m a c 协议分为两大类：随机接入( 如a l o h a 、c s m a 和 c s m a c d 等) 和受控接入( 如t d m a 和令牌传递方案等) 。a dh o c 网络缺乏基础 设施和节点以对等方式运行的本质使得随机接入协议成为组建a dh o c 网络的自然 选择。事实上，针对a dh o c 网络提出的m a c 协议大多数都是随机接入协议。例如， i e e e8 0 2 1 1 标准委员会就选择一种随机接入方案( 即c s m a c a ) 协议作为其标 准的m a c 协议的基础。但是在需要保证服务质量的场合，采用受控接入协议可能 更加合适。例如，i e e e 8 0 2 11 的p c f 能够比较好的支持对时延敏感的业务。 i e e e 8 0 2 1 1 的m a c 协议本身是针对单跳的w l a n 设计的，并没有针对多跳网络进 行优化。当应用于多跳a dh o c 网络时，当前的i e e 8 0 2 1 1 m a c 协议存在许多问题， 因此为a dh o c 网络改进甚至设计新的m a c 协议仍然是一个热点问题。 ( 3 ) 分群。a dh o c 网络一般有两种结构：平面结构和分级结构【7 。在分级结构 中，网络被划分为群，群根据是否存在群首分为无群首的群和有群首的群。在有 群首的群中，群由群首、网关和群成员节点组成。群内节点的身份动态变化，节 点仍然自动组网。群首负责群问数据的转发、协调和管理，使群内各节点合理工 作，群首由分群算法选举产生，目前对分群算法的研究也取得了不少的成果。群 首与现有蜂窝移动系统中的基站的主要区别在于它一般没有专用的硬件，本身也 是一个移动节点，并且是动态选择的。大量研究结果表明，分群可以有效地使用 多信道，提高系统质量；减少控制信息的交换开销，增强对节点的控制管理；实 现网络的局部同步；为多媒体业务提供服务质量路由；支持大规模的无线网络 刀。 在自组网的网络管理、节能和安全控制等方面的应用也吸引越来越多的研究 人员对分群算法展开深入的研究，其中比较经典的分群算法有最小i d 算法、最大 2上 青岛理工大学工学硕士学位论文 连接度算法、l o w e s t s p e e d 算法【8 1 、基于权值的算法、基于位置预测的算法 9 1 、求 解最大独立集的算法【l o - 1 刀。本文主要利用求解最大独立集来构建无线a dh o c 网络 虚拟主干网的思想来进行研究，并在已有a dh o c 网络的c d s 分群算法的基础上加 入基于回馈的构造策略，避免了由于添加新的连接支配节点导致的环路的生成。 ( 4 ) 能量控制问题【6 】。能量控制问题涉及到无线网络中的每个层，在每层上都 有相应的技术方案圈。在硬件层次上，可以采用低功率的c p u 和显示器；在物理 层，可以通过调整节点的发射功率来减少网络的能量消耗；在m a c 层，主要措施 是减少数据发送的冲突，避免重传，和使节点进入睡眠状态：在网络层，采用功 率控制路由算法，而不是以最短跳数和最小时延作为路由度量；在操作系统层次 上，可以采用低能量消耗的c p u 调度算法和磁盘管理算法【6 】。 ( 5 ) 安全性问题。a dh o c 网络的特点给网络设计带来了新的安全性方面的挑 战。信道和节点的弱点、缺乏基础设施和动态改变的拓扑结构使得在a dh o c 网络 中提供安全性保证非常困难。主要表现在以下几个方面【7 】：无线信道使得a dh o c 网络很容易受到被动窃听、主动入侵、信息阻塞、信息假冒等各种方式的攻击。 并且由于网络中的每个移动节点携带的能源是有限的，节点c p u 的计算能力相对 比较低，无法实现复杂的加密算法，增加了被窃密的几率；当节点在战场上移动 时，由于缺乏足够的保护，很有可能被占领。因此，恶意攻击不仅来自网络之外， 而且可能来自网络本身。为了获得更高的生存能力，a dh o c 网络应该具有分布式 安全结构；由于节点的移动性，a dh o c 网络的拓扑结构和成员处于动态的变化状 态。节点之间的信任关系也在不断变化。因此任何静态配置的安全方案在a dh o c 网络中是不可行的；大型的a dh o c 网路中可能包含百千个节点，因此安全策略应 该具有较好的可扩展性，以适应网络规模日益增大的需要。 ( 6 ) 基于a dh o c 网络的多播，组播协议、t c p 协议、地址分配、分布式法、 q o s ( q u a l 时o f s e r v i c e ) 等方面也有一些研究成果，但各部分的数量相对较少。 国际上目前主要的几个研究机构有： 康奈尔大学的“无线网络实验室”研究方向包括a dh o c 网络重构、m a c 协议、 路由协议、网络安全等。加州大学圣克鲁兹分校j j g a r c i a - n m a a c e v e s 教授所领导 的“计算机通信研究小组”研究方向主要包括无线网络的信道接入等。加州大学 圣巴巴拉分校e l i z a b e t hm b e l d i l l g r o y e r 教授所领导的“移动性管理和联网实验 室”研究方向包括j i a y s t a r 网络路由协议、q o s 、多播协议、地址重构、安全性、 3 青岛理工大学工学硕士学位论文 可伸缩性和适应性等。加州大学洛杉矶分校的“无线自适应移动性实验室”。研 究方向包括a dh o c 网络路由协议、多跳网络q o s 、m a c 协议、多播协议、蓝牙网 络、功率控制等。伊利诺基大学u r b a n a c h a m p a i 弘分校n i t i nv a i d a ”教授所领导的 a dh o c 网络研究小组。研究方向包括a dh o c 网络的定向路由协议、定向m a c 协议、 网络调度等。马里兰大学s a t i s hk t 打p a t h i 教授所领导的“移动计算与多媒体实验 室 研究方向包括j i a y s t a r 网络路由协议、q o s 等。 目前国内研究a dh o c 网络的情况如下：北京邮电大学的丁炜教授领导的通信 网研究中心主要进行m p l s 协议软件和路由软件的开发，西安电子科技大学李建 东教授领导的通信工程学院信息研究所主要研究分组无线网和自组织网络，另外 中南大学、南京邮电大学、解放军理工大学、国防科技大学、中国科学院、中国 科技大学、浙江大学、哈尔滨工业大学等高校在相关研究领域中也取得了良好的 成绩。 1 3 应用领域 对移动a dh o c 网络的研究最早是起于军事应用，军事应用一直是移动a dh o c 网络的主要应用领域，移动a dh o c 网络的自组织、可移动、无需架设网络设施、 多跳路由、展开速度快、抗毁性强等特点正好可以满足战场通信系统高灵活性、 高可靠性、高抗毁性等特殊要求。因此，在军事通信中移动a dh o c 网络技术的地 位始终是不可替代的。从短期来看，军事通信仍将是移动a dh o c 网络技术应用的 最直接领域。 移动a dh o c 网络虽然有很多优势性的特点，但是它不是一种广域网的解决方 案，所以基于这种局限它不能成为主流的移动通信网络，因此对于移动a dh o c 网 络在民事应用上具有很大的环境局限，目前的民用主要有传感器网络，由于传感 器网络只能使用无线通信技术，考虑到节能和体积的因素，传感器的发射功率不 能太大，目前主要用于环境检测和动植物的跟踪、智能家庭( s m 缸h o m e ) 应用方面， 可以协助智障或残障人士。紧急服务用于自然灾害中，紧密通信用于救灾等，在 发生了地震、强热带风暴、泥石流、水灾和遭受其他灾难打击后，固有的通信网 络设施有可能被全部摧毁或无法正常工作，这将对抢险救灾工作带来很大的不便， 这时像移动a dh o c 网络这种不依赖任何固定网络设施又能快速布设的自组织网络 技术就能很好的发挥作用。教育娱乐方面虚拟教室、虚拟会议室、文件的传输和 4 青岛理工大学工学硕士学位论文 信息交流、实现师生互动、机器人宠物、多用户游戏。家庭和企业方面的应用主 要是无线共享、个人局域网等，个人局域网技术不仅可用于实现p d a ( p e r s o n a l d i 百t a la s s i s t 锄t ) 、手机、手提电脑等个人电子通信设备之间的通信，还可以用于 个人局域网之间的多跳通信。 1 4 本文内容及其工作 本文的主要工作如下： 1 对现有的移动a dh o c 网络虚拟主干网构造的的经典分群算法进行了研究， 主要研究了最小i d 算法、最大连接度算法、l o w e s t s p e e d 算法、基于权值的算法、 基于位置预测的算法、求解最大独立集的算法。 2 重点研究了求解最大独立集的算法，对现有的移动a dh o c 网络虚拟主干网 构造技术进行比较，在现有的构造技术的基础上利用图论中最小支配集构造移动 a dh o c 网络虚拟主干网。图论中最大独立集和最小连通支配集问题的求解是一n p 完全问题，本文在按需加权算法的基础上采用图着色的思想去获得其最优解。 3 通过运用n s 2 网络模拟器对算法模型仿真进行性能验证。对仿真结果进行 分析，明确算法的优点和存在的不足。 全文共分为六个章节，具体如下： 第一章简要介绍国内外关于移动a dh o c 网络的研究研究背景和意义以及分 析其当前的研究现状，提出论文的研究内容和主要的解决问题。 第二章主要是对移动a dh o c 网络进行了概述，首先介绍了a dh o c 网络的基 本概念、特点，然后详细阐述了移动a dh o c 网络的体系结构和目前运用的关键技 术。 第三章对移动a dh o c 网络的现有分群算法进行了简单的介绍，主要介绍了在 图论的基础上运用图论的极小支配集( 极大独立集) 理论的算法的运行机理并简 单举例，对不同类型的分群算法进行了相应的归类分析和比较。 第四章提出了一种改进的基于图论的极小支配集理论的新型加权的移动a d h o c 网络分群算法，对算法的基本思想进行描述。 第五章对提出的算法性能进行理论证明，并在n s 2 平台上进行了实验仿真并 对结果进行了分析。 第六章对全文的工作进行了总结，并依其存在的不足对发展方向进行了展望。 s 青岛理工大学工学硕士学位论文 第2 章移动a dh o c 网络技术 2 1 移动a dh o c 网络概述 移动无线自组网a dh o c 也被成为多跳无线网，是一种无基础设施的移动网 络，由一组带有无线通信收发装置的移动终端节点组成是一个多跳的临时性的无 中心网络。可以在任何时刻、任何地点快速构建起一个移动通信网络，并且不需 要现有信息基础设施的支持，网络中的每个终端可以自由移动、地位平等。可以 独立工作，也可以以末端子网的形式接入h l t e m e t 网络或蜂窝无线网络。由于受到 带宽和功率的限制，移动a dh o c 网络一般用于作为中间承载网络，不允许其他信 息穿越本网络，从而大大减少了与现有i i l t e n l e t 网络之间相互操作的路由开销。移 动a dh o c 网络提供的是一种全新的网络构建思想，在实际的应用中，这种网络构 建技术创造了一种全新的网络通信平台。移动a dh 0 c 网络具有高度的自治能力， 可以随时随地铺设和配置，不受现有网络的约束和限制，不需要基站支持，十分 适合军事作战系统、事故的突发现场以及人们希望能迅速共享信息的办公室、会 议等场所。 2 2 移动a dh o c 网络的特点 与传统的通信网络相比较，移动a dh o c 网络主要有以下一些显著特点【1 8 乏1 】： ( 1 ) 网络拓扑的动态性【1 8 】：传统的移动通信网络具有相对固定的基站或a p ， 因而其总体拓扑比较稳定，而移动a d h o c 网络则不同，网络中的无线节点频繁随 机移动变化，因此移动终端间通过无线信道形成的网络拓扑结构也是随时随机发 生变化的，而且变化方式和速度都是不可预测的。因而，移动自组网拓扑是随机 的、动态的，主要原因是：首先，无线节点能随机地移动，造成拓扑的频繁变化； 其次，由于无线节点采用无线信道进行通信，节点之间的链路会因为地理条件的 变化、通信信道的干扰等因素而造成拓扑的变化；再次，无线节点的能量主要靠 电池提供，电池携带的能量是有限的，因而个别节点可能会因为能量消耗的原因 而消失【18 1 。 ( 2 ) 移动终端的自主性1 9 】：在移动a dh o c 网络中，每个移动终端节点都具 6 青岛理工大学工学硕士学位论文 有自组织能力可以同时扮演移动终端和路由器这两个角色，每个终端都承担为其 他终端进行分组转发的义务。移动终端具有灵活、轻便等特点，但是它也具有内 存小、c p u 性能较低等局限性，给自组网环境下的应用程序设计开发带来一定的 难度 1 9 】。 ( 3 ) 网络多跳路由性2 0 】：当数据发送方和接收方的移动终端节点不在单跳范 围内时，必须经由其它单个或多个移动终端节点中继才能完成数据的传输。也就 是说依靠其他移动终端节点协助进行路由，转发其所要发送的信息，这样就形成 了对等节点中的网络多跳路由的特性【2 0 】。如图2 1 所示，节点a 与节点b ，节点 a 与节点c 、节点b 与节点c 、节点b 与节点d 都是一跳节点；而节点a 到节点 d 就需要节点b 或者节点c 和e 中继转发、节点a 到节点e 就需要节点c 中继 转发才可以通信，像节点a 到节点d 、节点a 到节点e 这种情况就是多跳路由通 信。 bd 图2 1a dh o c 网络拓扑 ( 4 ) 移动终端的异构性：组成移动a dh o c 网络的移动终端节点很可能有多 种设备组成，这就要求自组网构建的时候不得不考虑其异构性。 ( 5 ) 有限的无线传输宽带：无线网信道本身的特点比起有线信道它的传输带 宽要差得多。在移动a dh o c 网络中，终端节点通过共享无线信道，以无线方式进 行通信，由于共享信道难以控制和分配，数据传输时常会有碰撞发生，造成冲突， 降低网络的性能。在现实中由于噪声等多种信号干扰因素的存在使得终端的宽带 实际可用值比理论最大值小很多，而且存在单向无线信道【2 0 】。 ( 6 ) 有限的通信距离2 1 】：由于提供终端的能源是电池，使得终端的能源有很 大的局限性因而导致终端节点的发射功率的减小，因而网络中的某节点发出的信 号，其他终端节点节点并不一定能接收到。 7 青岛理工大学工学硕士学位论文 ( 7 ) 网络的扩展性差【捌：现有的i n t 锄e t 网络通常采用域问路由选择( c l a s s l e s s i n t e r d o m a i nr o u t i n g ，c i d r ) 和变长子网掩码( v 耐a b l e l e n g t hs u b n e tm a s k ，v l s m ) 等技术来增强i n t 锄e t 网络的可扩展性。而在无线自组网络中动态变化的拓扑结构 使得具有不同子网地址的移动终端可能同时处于一个a dh o c 网络中，因而现有的 子网技术所带来的可扩展性无法应用到a dh o c 网络环境中 2 2 1 。无线自组网中的各 种协议，如路由的获取、加密密钥的交换、业务定位等造成的附加开销对网络资 源的消耗随节点数增加而急剧增加，使的有限的资源被大量的控制业务浪费，从 而大大限制了网络的可扩展性。 ( 8 ) 安全性能差 1 9 】：移动自组网中的终端节点采用无线传输方式，因而更容 易受到窃听、入侵和拒绝服务等各个层次的攻击，无线节点也容易因为被剥夺“休 眠而导致能量迅速耗尽；恶意的无线节点扮成路由节点时，可能导致数据无法 传送到目的节点而影响通信【l9 1 。网络本身的分布式行为使得传统有线环境中的安 全策略和机制无法在无线自组网中直接应用，一种有效的分布式安全机制将是移 动自组网从理论研究走向实际大规模应用的一个重要因素。 2 3 移动a dh o c 网络的结构和协议栈 移动a dh o c 网络有两种拓扑结构：平面结构( 如图2 2 ) 和层次结构【2 3 】( 如图 2 3 、图2 4 ) 。平面结构中所有的移动终端在路由选择、网络控制等功能控制和地 位都是平等的，因此也称为对等结构。这种网络结构比较健壮，终端节点数小， 相对比较安全。但是当随着节点数量的增多并且在移动，平面结构的处理能力将 大大减弱、控制开销增大、路由终端现象频繁出现，由此可见平面结构只适用于 节点数目较小移动性弱的中小型网络。 图2 2 a d h o c 网络平面结构 8 青岛理工大学工学硕士学位论文 根据网络的应用规模和扩展性，以及应用的可靠性及实时性要求，进行组网 时必须选择合适的网络拓扑结构，才能最大限度地发挥网络的性能。此时人们提 出了层次化的解决方案，在层次结构中，利用分群算法将移动a dh o c 网络划分成 逻辑上的层次结构。分群算法将网络划分成若干个群，每个群由一个群首和多个 普通节点组成。群首之间的通信需要借助于网关或分布式网关完成。群首和网关 形成了高一级的网络，称为虚拟骨干网【2 3 】。层次结构，也叫分级结构，最大优点 是网络的可扩充性好，网络的规模不受限制，路由和控制开销比平面结构小，并 且容易实现移动性管理和网络的局部同步。在面向大规模网络的应用系统中具有 重要应用价值。 层次结构的网络根据硬件配置的不同，又可以分为单频分级和多频分级两种。 单频率分级网络中，所有结点使用同一个频率通信。为了实现群首之间的通信， 要有网关结点的支持( 如图2 3 ) 。而在多频率分组网络中，不同级采用不同的通 信频率。低级节点的通信范围较小，而高级结点要覆盖较大的范围。高级的节点 同时处于多个级中，有多个频率，用不同的频率实现不同级的通信。例如在两级 网络中，群首节点就有两个频率。一个用于不同群之间群首节点的通信。另一个 频率用于本群内群首与群节点的通信。分级网络的每个结点都可以成为群首，所 以需要适当的群首产生算法，算法还要能根据网络拓扑的动态变化重新进行群的 划分( 如图2 4 ) 。 ( 二) 群 l 群首 群成员 图2 3a d h o c 网络单频分级结构 9 网关 青岛理工大学工学硕士学位论文 图2 4a d h o c 网络双频分级结构 平面结构网络相对于层次结构网络简单，网络中所有节点完全对等，原则上 不存在瓶颈，但可扩充性差，而且每一个节点都需要知道其到达网络中其他所有 节点的路由。维护这些动态变化的路由信息需要大量的控制消息，不适用于现在 组建的大规模的移动网络。在层次结构网络中，只需要群首节点维护路由信息， 这样移动网络中路由控制信息的数量就减少了。同时层次结构可以通过增加群的 个数和网络的层数来扩大网络的规模，因此具有良好的可扩充性。由于群首节点 可以随时选举产生，层次结构也具有很强的抗毁性。但维护层次结构需要节点执 行群首选举算法，群首节点可能会成为网络的瓶颈，且群间的路由不一定是最佳 路由。因此，当网络的规模较小时，适合采用简单的平面式结构；而当网络的规 模增大时，则应采用层次结构。 参照h n e n l e t 网经典的o s i ( o p e ns y s t e mi n t e r c o i l i l e c t ) 七层协议模型以及 t c p i p ( t r a n s p o r tc o n t r 0 1p r o t o c o l h l t e m e tp r o t o c 0 1 ) 的体系结构，一般将a dh o c 网络的协议栈划分为5 层，即物理层、数据链路层、网络层、传输层和应用层。 与有线网络相比，a dh o c 网络的工作环境有诸多不同，因此所选的技术也有较大 差异，主要体现在网络的低三层，即物理层、数据链路层和网络层，其中网络层 的差异最大。下面根据移动自组网络的特点，参照o s i 七层协议模型，介绍各层 的功能，其协议栈结构如表2 1 所示 2 4 】。 最底层是一组低功率、高能力、能在运动中工作的物理传输设备，提供无线 传输设备，提供无线传输能力、完成无线信号编码译码、发送和接收等工作，以 支持移动组网。链路层控制对共享无线信道的访问以及对逻辑链路的控制，提供 可靠的无线通信的逻辑链路层，以支持有效的介质访问。网络层是a dh o c 技术的 1 0 青岛理工大学工学硕士学位论文 表2 1a dh o c 网络协议栈 技术及功能层次 应用服务应用层 传输服务传输层 分组转发和路由网络层 链路控制信道接入数据链路层 无线信道物理层 重点，也是它与其他现有网络的主要区别所在，支持网络工作的传输协议、移动 组网算法和动态路由协议。传输层主要完成端到端通信的建立，目前一般是对有 线网中的t c p 肘d p 进行改造，使之适应无线环境；a dh o c 的高层主要包括建立 在a dh o c 之上的无线应用以及接入移动通信核心网的各种业务。 除了这些主要功能外，还有一些可选的功能，包括功率控制和拓扑控制、分 群算法、信令协议、移动管理和位置定位、服务发现、地址自动配置和安全策略 等。此外，为了优化系统性能，应采用跨层的协议栈设计方法，使各个协议层和 功能模块之间能交互信息。例如，物理层及时将信道条件报告给链路层和网络层， 网络层将资源使用信息和业务流性能状况报告给应用层，并且应用层需要将当前 业务的服务要求及时传递给下层协议，然后各层进行相应的调节，选择合适的算 法和机制来优化系统性能。同时考虑到移动a dh o c 网络中能量的局限性各层都需 要采用定的措施来尽可能降低能量的消耗。 2 4 移动a dh o c 网络关键技术 与传统的有线网络相比较，由于移动a dh o c 网络无中心、自组织、多跳路由、 节点的移动性、无线带宽受限、节点电池能量有限等特点给人们在a dh o c 网络的 关