（计算机软件与理论专业论文）ad+hoc中具有qos的分簇路由协议研究.pdf

l a b s t r a c t i i i i iiiii i r l r li i ri l li ii y 17 3 3 8 9 2 a dh o ci san e wa n dd e v e l o p i n gn e t w o r kt e c h n o l o g y i nc u r r e n tw i r e l e s s c o m m u n i c a t i o n sf i e l d a n di ti sp a i dm o r ea t t e n t i o ni n r e c e n ty e a r sb e c a u s eo fi t s p r a c t i c a b i l i t ya n df l e x i b i l i t y r o u t i n g , a sa m o m e n t o u sp a r to fa dh o c ，h a sb e e nah o t s p o t f o rc o m m u n i t y a n dt h er o u t i n gp r o t o c o l sh a v es w i t c h e df r o mp l a n a rs t r u c t u r et oc l u s t e r s t r u c t u r eg r a d u a l l yd u et ot h ee n l a r g e m e n to ft h es i z eo fn e t w o r k b u tt h ec u r r e n tc l u s t e r s t r u c t u r er o u t i n ga l g o r i t h m sd on o tm a k ee x t e n s i v eu s eo ft h ea d v a n t a g e so fc l u s t e r s t r u c t u r ea n dt h a tc o u l dn o ti m p r o v et h er o u t ed i s c o v e r ye f f i c i e n c ya n dr e d u c et h ec o s to f f l o o d i n g a d d i t i o n a l l y , w i t ht h ed e v e l o p m e n to fm u l t i m e d i aa p p l i c a t i o n s ，t h en e t w o r k u s e r sa n dm a n ya p p l i c a t i o n sr e q u i r eab e t t e rq o s ，w h i c hm a k e st h er e s e a r c ho fr o u t i n g p r o t o c o l sm o r ec o m p l i c a t e d t h et h e s i sf i r s t l yg i v e sas h o r ti n t r o d u c t i o nt oa dh o ca n dt h e nb ya n a l y s i sa n d c o m p a r i s o no f f a m i l i a rc l u s t e ra l g o r i t h m s ，t h et h e s i sp r e s e n t s a n i m p r o v e d c l u s t e r a l g o r i t h mb a s e do nt h eh i g h e s td e g r e ec l u s t e ra l g o r i t h m t h ea l g o r i t h mo p t i m i z e st h e s e l e c t i n gf o r mo ft h ec l u s t e rh e a da n dg a t e w a ya n do p e r a t e sw i t hf a s tc o n v e r g e n c ea n d l o wc o s t s e c o n d l y , t h et h e s i sf o c u s e so nt h ea n a l y s i so fd i f f e r e n tk i n do fr o u t i n gp r o t o c o l s ，a n d p r e s e n t sah y b r i dc l u s t e rr o u t i n ga l g o r i t h mb a s e d o nt h ei m p r o v e dh i g h e s td e g r e ec l u s t e r a l g o r i t h m t h ea l g o r i t h mm a k e sf u l lu s e o ft h ea d v a n t a g e so fc l u s t e rs t r u c t u r ea n dr e d u c e s t h ec o s to ft h er o u t ed i s c o v e r ya n db yw h i c ht h ea l g o r i t h mc a ni m p r o v et h er o u t e d i s c o v e r ye f f i c i e n c ya n d a v o i dt h eb r o a d c a s ts t o r m t h i r d l y , t h et h e s i sd e s c r i b e st h eo o sr o u t i n g i nd e t a i l ，a n dt h eb a n d w i d t hi ss e l e c t e d a st h eq o sc r i t e r i a ，w h i c hm a k e st h ep r e v i o u sa l g o r i t h mq o sf e a t u r e d t h ea l g o r i t h mc a n m e e tt h eb a n d w i d t hr e q u i r e m e n ta n dg u a r a n t e es e r v i c eq u a l i t y a tl a s tp a r to ft h et h e s i s ，t h et h e s i ss i m u l a t e sa l la l g o r i t h m sm e n t i o n e da n da n a l y z e s t h e i rp e r f o r m a n c e sr e s p e c t i v e l y k e yw o r d s ：a dh o cn e t w o r k ；c l u s t e rr o u t i n g ；q o sr o u t i n g 目录 第一章绪论l 1 1 研究背景及意义1 1 2 国内外研究现状1 1 3 研究内容及解决的问题2 1 4 论文的结构与章节安排3 第二章h dh o e 网络概述5 2 1a dh o e 网络的定义及特点5 2 2h dh o e 网络的节点及拓扑结构7 2 3a dh o e 网络的路由技术1 0 2 4a dh o e 网络的q o s 服务质量保证1 1 2 5 本章小结1 2 第三章h dh o e 网络的分簇算法及改进1 3 3 1 分簇算法的概述1 3 3 1 1 相关定义和说明1 4 3 1 2 基本概念和目标1 5 3 1 3 分簇算法性能评价准则1 6 3 2 常见的分簇算法1 7 3 2 1 最高节点度分簇算法1 7 3 2 2 最小i d 分簇算法1 8 3 2 3 最低节点移动性分簇算法1 8 3 2 4 基于地理位置的分簇算法1 9 3 3 对最高节点度分簇算法的改进2 0 3 3 1 改进的算法思想的概述2 0 3 3 2 分簇形成阶段2 0 3 3 3 分簇链接阶段2 2 3 4 本章小结2 3 第四章h dh o e 网络的路由协议及改进2 5 4 1h dh o e 网络路由协议的设计条件与基本要求2 5 4 2h dh o c 网络路由协议的分类2 6 4 2 1 先验式路由协议和反应式路由协议2 6 4 2 2 平面式路由协议和分簇式路由协议2 9 4 3 路由算法性能的评价标准3 l 4 4 基于改进的分簇算法的混合式分簇路由算法3 1 4 4 1 算法思想概述3 l 4 4 2 路由发现过程3 2 4 4 3 路由维护过程3 4 4 4 4 路由算法分析3 5 4 5 本章小结3 6 第五章h dh o e 网络具有o o s 的路由协议及具体方案的提出3 7 5 1 服务质量o o s 的概念3 7 5 2q o s 路由概述3 7 5 2 1q o s 路由的概念和目标3 7 5 2 2q o s 路由尺度的选择3 8 5 2 3q o s 路由问题的难点和所面临的困难3 9 5 2 4 常见的o o s 路由协议3 9 5 3 具有q o s 的混合式分簇路由算法方案4 l 5 3 1 指标的选取和计算方法4 l 5 3 2 算法描述4 l 5 3 3 算法分析4 2 5 4 本章小结4 3 第六章仿真实验及性能分析4 5 6 1n s 一2 仿真坏境4 5 6 2 对改进的最高节点度分簇算法的仿真4 5 6 2 1 实验场景设置以及性能指标的选取1 5 6 2 2 实验结果以及性能分析4 6 6 3 对混合式分簇路由算法的仿真4 7 6 3 1 实验场景设置以及性能指标的选取4 7 6 3 2 实验结果以及性能分析，1 8 6 4 对具有q o s 的混合式分簇路由算法的仿真，1 9 6 4 1 实验场景设置以及性能指标的选取，1 9 6 4 2 实验结果以及性能分析5 0 6 5 本章小结5 2 第七章总结与展望5 3 参考文献5 5 攻读学位期间的研究成果5 9 致谢6 l 学位论文独创性声明6 3 学位论文知识产权权属声明6 3 第一章绪论 1 1 研究背景及意义 第一章绪论 a dh o e 无线自组网是当前无线通信领域一种新的、正在发展的网络技术。它可 以在没有常规的基础设施支持下提供方便灵活的通信，拓宽了移动通信的应用领域， 具有广阔的发展前景。在军事应用领域、发生了水灾地震等重大灾难后固定通信网 络设施无法正常工作或全部损毁的地区，以及处于偏远野外地区无法依赖固定网络 设施进行通信时，a dh o c 自组织网络技术因其不依赖于任何固定网络设施又能快 速布设的特点发挥了重要的作用。它是这些场合下通信最佳甚至唯一的选择，能够 在这些特殊和恶劣的环境下提供通信支持，对抢险救灾等工作具有重大的意义。 目前a dh o c 网络的路由协议划分为平面式路由协议和分簇式路由协议两大类。 在平面式路由协议中，各个节点地位平等，并且每一个节点都需要知道到达其他所 有节点的路由。维护这些动态变化的路由信息需要大量的控制消息，当网络规模增 加到某个程度时，所有的带宽都可能会被路由协议消耗掉乜】，因此网络的可扩充性 较差。而分簇式路由协议通过增加簇的个数和网络的级数来提高网络的容量，大大 减少了由于节点移动对路由算法带来的影响和路由发现过程中的洪泛开销，并能够 加速路由的查找过程，克服平面结构可扩充性差的缺点，网络规模不受限制。但分 簇结构也有缺点：需要簇头选择算法和簇维护机制；簇间的路由不一定是最佳路由； 簇头节点的任务相对较重，可能成为网络的瓶颈等。这些问题都需要在设计分簇路 山算法时特别考虑，需要寻找到最能平衡各种优缺点的分簇路由算法，降低洪泛歹i ： 销，提高效率。 此外，随着网络用户需求的逐渐提高，实时业务或者突发性高的业务不仅要求 能够通信，还要求网络能够提供时延、带宽等方面的保证。因此分簇路由协议应该 具有o o s 特性，通过带有o o s 信息的路由实施有效的控制来防止网络过载，然后寻找 满足o o s 要求的路由在无线网络中实施负载均衡。 采用分簇的策略并且使分簇路由协议具有o o s 特性，才更能顺应a dh o c 网络高 速的发展。 1 2 国内外研究现状 自2 0 世纪7 0 年代美国高级研究计划署( d a r p a ) 资助研究的分组无线网。们项目丌 展以来，国内外的许多研究人员从不同角度提出了一系列的a dh o c 网络路由协议。 比如先验式路由协议( p r o a c t i v ep r o t o c o l s ) ：d s d v 拍3 、w r p 阳1 等；反应式路由协 青岛大学硕十学位论文 议( r e a c t i v ep r o t o c o l s ) ：a o d v 、d s r 8 1 、t o r a 9 1 、a b r 1 0 3 、s s a n 3 等。但它们 大都是平面式路由协议，网络扩展性差，路由时延和耗费大，且不易于进行质量管 理和q o s h 艮务质量保障。 随着网络规模的增大和服务质量管理的要求，对基于分簇的路由协议( c l u s t e r e d p r o t o c o l s ) 又进行了大量的研究。比如，1 9 9 8 年由r a g h u p a t h ys i v a k u m a r 等人提出的 c e d a r ( c o r e e x t r a c t i o nd i s t r i b u t e da dh o cr o u t i n g ) 蜘协议，它的目标是构建一个 稳定的虚拟核心结构，用于可靠有效的扩散路t j 信息；基于群首网关交换的 c g s r ( c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g ) 。协议；山距离矢量路t h i d s r 路 l l 协 义 组合的z r p ( z o n er o u t i n gp r o t o c 0 1 ) 3 协议：基于链路状态的h s r m 义等。这螳协议从 不同程度上降低了路由时延和洪泛开销，控制了分组转发跳数，却未考虑簇的范l l j l 和大小，簇头容易成为瓶颈节点，并且节点移动变化迅速时，簇维护j | ：销犬等问题。 基于这些缺点，又有按需式分簇路由o d c r ( o n - - d e m a n dc l u s t e r i n gr o u t i n g a l g o r i t h m ) 等算法提出，但仍然不能充分地降低簇内和簇i 日j 路由洪泛和时延的丌销， 没有有效地利用混合式路由算法的思想。分簇路由协议的研究，仍需要加强混合式 路由算法的思想，充分降低洪泛开销，适应网络拓扑多变，降低时延，可以考虑引 入路由缓冲等技术。 与此同时，基于q o s 的路由技术也在迅速发展，比如s t a r a 刖协议，l s q o s 1 协议等。大部分的q o s 路由协议都是基于平面式的，或者少数足挂于分区结构的， 而鲜有真j 下意义上基于分簇结构的q o s 路由协议。这些协议没订特别考虑铃点能 责 的约束，路由耗费过大，并且建立的链路不十分稳定，效率较低，将q o s 路 l i 的研 究建立在分簇结构的基础上是十分必要的。 1 3 研究内容及解决的问题 本论文将研究具有q o s 的混合式分簇路由协议。针对当日玎已存在的分簇路f l 协 议和o o s 技术，提出洪泛丌销更低，路由发现效率更高且能提供o o s 质量管理保障 的路由协议方案。具体研究的内容及解决的问题如下： ( 1 ) 针对分簇维护花费大等问题，分析各种现有的分簇算法，对比优缺点，提 出合理的改进的解决方案，使簇的个数和范围适中，缩短构造簇的等待时问以及降 低因节点移动频繁而引入的分簇维护花费。 ( 2 ) 针对当前路由协议没有充分利用分簇结构优点的问题，分析研究各种现有 的路由协议，在使用改进的分簇算法的基础上，提出一种混合式分簇路t - h 铭法。簇 内各节点使用先验式路由，簇间各节点使用反应式路由，并且管重姓凋缩小路山控 制消息传播的范围，降低路由发现过程的洪泛丌销，提高路由发现的效率，缓解无 线带宽低的缺陷。 2 第一章绪论 ( 3 ) 针对当前用户需求及网络业务不仅要求能够通信，同时要求网络能够提供 时延、带宽等方面的保证的问题，分析现有的各种q o s 路由技术，总结q o s 指标选 取方式以及单约束条件q o s 路由的解决方法，进而提出一种具有q o s 的混合式分簇 路由方案。该方案能够保证服务的质量，适应高速网络的变化，并且能大大地降低 洪泛开销。 1 4 论文的结构与章节安排 论文的结构与章节安排如下： 第一章简要介绍了论文研究背景和意义，国内外关于各种路由技术的研究现状 以及论文的研究内容和解决的主要问题。 第二章主要对a dh o c 网络进行了概述。对它的定义、特点、网络拓扑结构以 及路由协议和q o s 等关键技术进行了简要的介绍。 第三章主要介绍了a dh o e 网络分簇算法的基本概念，对各种常见的分簇算法 进行比较并提出了一种改进的最高节点度分簇算法。 、 第四章主要介绍了各种a dh o c 网络路由协议及其各自的优缺点，在第三章提 出的改进的分簇算法的基础上，提出了一种混合式分簇路由算法。 第五章介绍了服务质量q o s 的概念、q o s 路由发展的现状以及其面临的问题。 使第四章的研究成果具有q o s 特性，形成一种具有q o s 的混合式分簇路由协议方案。 第六章分别对已提出的分簇算法，混合式分簇路由算法以及具有q o s 的混合式 分簇路由算法进行了仿真，并对其性能进行了分析。 第七章对全文进行总结，并对其发展方向进行了展望。 3 第二章a dh o c 网络概述 第二章a dh o c 网络概述 2 1a dh o c 网络的定义及特点 “a dh o c 一词源于拉丁语，英语含义为“f o rt h es p e c i f i cp u r p o s eo n l y ”，翻译 成中文的意思是“临时的，特别的 。它是一种特殊的无线移动通讯网，一个无中心 的多跳临时性自治系统，不需要任何预先的网络基础设施的支持 ，因此它又被称 为自组织网络( s e l f - o r g a n i z e dn e t w o r k ) 、多跳无线网( m u l t i h o pw i r e l e s sn e t w o r k ) 或无固定设施的网络( i n f r a s t r u c t u r el e s sn e t w o r k ) 。网络中的节点都是带有无线收发 装置的可移动终端，具有路由和报文转发的功能，并可以自主地通过无线连接构成 任意的网络拓扑。这种网络既可以独立工作，也可以接入i n t e m e t 或蜂窝无线网络， 但不适于作为中间承载网络。 a dh o e 网络同时具有移动通信网络和计算机网络的特点，主要特点州有： ( 1 ) 组网独立性：a dh o e 网络的通信可以在任何时刻、任何地点、无需依赖f 任何预先架设的网络基础设施，这也是它区别于常规无线网络最大的特点。 ( 2 ) 无中心：a dh o c 网络中所有节点地位平等，没有严格的控制中心，并且可 以随时加入和离开网络。整个网络的运行不依靠于任何一点，具有很强的抗毁性。 任何节点的故障都不会成为网络运行的瓶颈。 ( 3 ) 自组织：a dh o c 网络没有严格的控制中心，因此所有节点必须通过分层的 网络协议和分布式算法协调各自的行为。a dh o e 网络正是由于其尤中心和自组织的 特点，才可以实现快速自动组网。 ( 4 ) 多跳路由：由于无线电信号传播范围有限，当与目的节点的通信距离超过氍 点信号传播范围时，就需要经过中间节点转发，要求多跳通信。同时，使用多跳路 由可以降低对节点发射功率的要求。 ( 5 ) 动态拓扑：a dh o e 网络中的节点具有任意移动性。它们可以随时加入或者 离开网络，改变网络的拓扑结构，并且这种改变的方式和速度都难以预测。 ( 6 ) 特殊的无线信道特征：无线信道本身所能提供的网络带宽要比有线信道低的 多，并且质量较差。a dh o e 网络采用无线传输技术，竞争共享无线信道产生的冲突、 噪音、信道之间干扰以及信号衰减等因素，使得移动终端实际获得的带宽远小于理 论上的最大带宽。 ( 7 ) 移动终端的局限性：移动终端一般靠电池供电，并且不能配备太多的发送接 收器。这使得它能源受限，处理能力较低，以及不能j 1 ：展功能复杂的业务。 ( 8 ) 安全性差：a dh o c 网络采用无线信道和分布式控制等技术，使得它更容易 遭到各种网络攻击，网络安全问题复杂。有线网络巾的许多安全策略和机制不弭适 5 青岛人学硕+ 学何论文 用，需要特别设计。 这些特点使得a dh o c 网络在体系结构、协议设计等方面与传统有线网络以及无 线网络有着显著的区别。表2 1 列出了a dh o c 网络与现有无线网络的区别。 表2 1a dh o c 网络与现有无线网络的主要区别 j 一 a dh o c 网络现有无线网络 比较的内容 无线网络结构多跳，无中心单跳。有中心 拓扑结构动态建立、火i 变化l 捌定 有无基础设施支持无有 路由选择和维护凼难容易 生存时间短 k 配置速度快慢 安全性和服务质量较芹较好 网络健壮性高低 中继设备无线1 ，点用i 无线骨干网基站和有线骨干网 研究重点协议的所有层物理层和链路层 中继+ i 了点的特点无线1 ，点通常只有一部收发信机，、卜基站有多部收发信机，全舣i ： 舣i ：方式l ：作，不易实现全网同步 方式通信，有专川硬件，易r 实现全列同步 无线1 了点的控制管理由无线l y 点奉身负，通常采j j 分布由肇站集中负责，无线1 ，点必 式方式通信，再通过基站与目的1 ，点须先与基站 通信 a dh o c 网络的应用广泛，它的许多优良特性使它在民用和军事通信领域占据一 席之地提供了有力的保证。主要应月j 可以旷i 纳为以下几类引： ( 1 ) 军事应用：a dh o c 网络技术的主要应用领域是军事应用领域。它特有的无 需架设网络设施、可快速展丌和抗毁性强等特点使得a dh o c 网络成为数字化战场通 信的首选技术。据报道，在伊拉克战争中，移动a dh o c 网络就得到了有效的应用。 ( 2 ) 紧急场合：当发生了地震、水灾或遭受到其他灾难打击后，固定的通信网络 设施可能全部损毁或无法证常工作，a dh o c 网络町以在这些恶劣和特殊的环境下提 供支持，对抢险救灾有二推常重要的意义。 ( 3 ) 偏远野外：a dh o e 网络技术具有单独组网能力和自组织的特点，是当处于 偏远野外地区无法依赖固定或预设的网络没施进i r 通信时的最佳选择。比如边远矿 6 第二章h dh o c 网络概述 山作业、野外科考队、边远地区执行任务分队的通信等。 ( 4 ) 传感器网络：传感器网络在许多应用场合下只能使用无线通信技术，因为受 节点体积和节能等因素的影响，传感器的发射功率不可能很大，a dh o c 网络实现的 多跳通信是其非常实用的解决方法。 ( 5 ) 商业应用：a dh o c 网络技术可以组建移动医疗监护系统、家庭无线网络、 开展移动和可携带计算等。 2 2h dh o t ：网络的节点及拓扑结构 a dh o t z 网络的节点既具备普通移动终端的功能，又具备路由器报文转发的功能。 因此，网络中移动的终端节点可分为主机、路由器和电台三部分。其中电台部分为 信息传输提供无线信道的支持。节点可以分为单主机单电台、单主机多电台、多主 机单电台和多主机多电台几类心劓，如图2 1 所示。 路由器 主机 ( a ) 单土机单电台( b ) 单主机多i 乜台( c ) 多z - 机单多电台 图2 1 a dh o c 网络节点的结构 a dh o c 网络的拓扑结构可以分为两类：平面结构和分级结构汹1 。 平面结构( 又可称为对等式结构) 的a dh o e 网络如图2 2 所示。所有节点地位 完全平等，组成一个对等式网络。它的特点是结构比较简单，原则上不存在网络瓶 颈，网络比较健壮，并且网络中节点的覆盖范围较小，相对安全。通常有多条路径 存在于源节点和目的节点之间，能够较好地实现负载平衡和最优化路由的选择乜。 但是在节点数目很多，尤其是需要节点大量移动的情况下，此种结构的网络很难进 行有效的网络管理和控制。另外，平面式结构网络的可扩充性差，每一个节点都需 要知道到达其它所有节点的路由信息。这些路由信息动态变化，维护时需要大量的 控制消息。当网络规模增大到某种程度时，所有的带宽都可能会被路由协议消耗掉。 因此平面结构只适用于中小规模的a dh o c 网络。 7 青岛人学硕十学位论文 i | i ， | 图2 2 平_ 画网络结构 在分级结构中，a dh o c 网络破划分为若干个簇。每个簇由一个簇头和多个簇成 员构成，并且这些簇头呵以形成商一级的网络。在这高一级的网络中，可以再分簇， 形成更高一级的网络。簇头节点维护到达其他簇头的路由信息，负责簇问数据的转 发，并且管理本簇内所有的簇成员。它既可以预先指定，也可以随时使用分簇算法 选举产生。 分级结构的网络可以根据硬件配胃的不同，分为单频率分级和多频率分级两种。 单频分级网络如图2 3 所示，所订节点使用同一个频率通信。通过网关节点( 同时 位于两个簇头通信范l 圈内的节点) 的支持，实现簇头之问的相互通信。网关节点与 簇头共同形成了高一级的网络，称为虚拟骨干网络( v p n ) 。 ( 一) 簇 簇头 簇成员 网关 i 、一，簇 簇头 簇成员 网关 图2 3 单频分级结构 多频分级网络( 如图2 4 所示) ，不同级采用不同的频率进行通信。低级节点 通信范围较小，而高级节点覆盖范 目大，它同时处于多个级中，需要使用多个不同 频率实现不同级的通信。在图2 4 所示的荫级网络中，每个簇头节点都使用两个频 率。簇头与簇内各成员通信时使用频率l ，簇头与簇头之间通信时使用频率2 。 8 第二章a dh o c 网络概述 频率1 频率2 ( 二) 簇簇头 簇成员 图2 4 多频分级结构 高级 低级 在分级结构的网络中，簇成员不需要维护复杂的路由信息，功能简单，大大减 少了网络中路由控制信息的数量。可以简单地通过增加簇的个数和网络的级数来增 加网络的规模，网络规模不受限制，具有很好的可扩充性。此外，由于可以随时利 用分簇算法选举产生簇头节点，分级结构也具有很强的抗毁性。但分级结构也有它 的缺点。比如：需要簇头选择算法和簇维护机制，增加了计算的复杂性；簇头节点 的任务相对较重，簇间通信均需要通过簇头转发，可能会增加报文时延，并且可能 成为网络的通信瓶颈；簇问的路由不一定是最佳路由。 分级结构在实施资源管理和提供服务质量保障等方面有较大的优势乜鄹，相对于 平面式结构而言，主要体现在下面几个方面： ( 1 ) 分级结构有较好的可扩展性，网络规模不受限制。 ( 2 ) 分级结构通过分簇使路由信息局部化，减少了路由协议的丌销，节省带宽， 提高了系统的吞吐量，并且容易实现网络的局部同步。 ( 3 ) 分级结构中节点的定位比较简单。在平面结构中，若要知道一个节点的位 置，需要在全网中执行路由查询操作。而在分级结构中，只需查询相应的簇头就可 以获得节点的位置信息。 ( 4 ) 分级结构结合了无中心和有中心模式，可以采用两种模式的技术优势。 总之，当a dh o c 网络的规模较小时，可以采用简单的平面式结构；而当网络的 9 青岛人学硕士学位论文 规模较大，或者需要有一定质量服务保障时，应采用分级结构。 2 3a dh o e 网络的路由技术 在a dh o e 网络中，网络拓扑结构变化频繁、网络带宽有限并且移动终端一般使 用单向的无线传输信道，所以传统的用于固定网络的路由协议都不适用于a dh o e 网络。而目前常见的移动通信系统( 蜂窝移动通信系统和无线局域网等) ，在系统的 组织、管理和维护方面也与a dh o e 网络相差较大。在蜂窝移动通信系统啪1 中，移动 节点之i 日j 路由的选择及建立是通过固定的网络设备( 如交换机) 完成的，基站主要 通过完成射频信号的发送和接收，网络结构比较稳定。但a dh o c 网络中不存在这样 的固定设备，节点问路由选择完全由移动节点完成，频繁的网络拓扑变化在很大程 度上影响路由选择。在无线局域网中，移动节点配有无线局域网网卡，通过无线接 入点链接到固定网络中，从网络层的角度看，无线局域网是一个单跳的网络，而a d h o c 网络是一个多跳的网络。综上分析，a dh o c 网络与传统的移动通信网络在路由 选择方面也有很大的差异，因此必须要重新研究设计出针对a dh o c 网络具体特点的 路由协议，从而解决路由选择问题。 i e t fm a n e t 乜订小组在r f c 2 5 0 1 中提出：a dh o e 网络的特点要求路由协议必须 采用分布式操作，能够尽量支持单向链路，同时应避免路由环路现象。此外，考虑 到无线节点的特性，路山协议还应该尽量简单，能够支持节点的休眠操作以节省电 源，能够给提供安全性保护。目前提出的a dh o e 网络路由协议按照发现路由的驱动 模式的不同，可以分为先验式路由协议( 又称为表驱动路由协议) 和反应式路由协 议。8 1 ( 又称为按需路由坍议) ，如图2 5 所示。 ： ， c g s rt o r a 图2 5a dh o e 路由协议按驱动方式的分类 先验式路由协议( p r o a c t i v ep r o t o c o l s ) 试图维护网络中从各个节点到所有其余节 1 0 第二章a dh o c 网络概述 点的最新路由信息。每个节点都维护一张包含到其他节点的路由表，当网络拓扑结 构发生变化时，节点实时地通过交互信息来更新网络路由信息表，所有路由信息保 持一致。源节点发送报文时，可以立即从所维护的路由表中找到到达目的节点的路 由信息。路由信息的更新一般采用“时间驱动 和“事件驱动 两种方式。先验式 路由协议通常是对现有的有线路由协议进行修改，从而适应a dh o e 无线网络的要 求。已提出的该类协议主要有w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 、d s d v ( d e s t i n a t i o n s e q u e n c ev e c t o r ) 、c g s r ( c l u s t e rh e a d g a t e w a ys w i t c hr o u t i n g ) 、s t a r a ( s y s t e ma n d t r a f f i cd e p e n d e n ta d a p t i v er o u t i n ga l g o r i t h m ) 等。 反应式路由协议( r e a c t i v ep r o t o c o l s ) 只有在需要时才进行路由发现，节点不需 要维护及时准确的路由信息，缓解了先验式路由协议由于周期性交换更新信息带来 的开销和扩展问题。源节点发送报文时，首先经过路由发现阶段，以洪泛方式广播 路由请求包，找到合适的路由后再发送报文，并且该路由信息将一直被维护，直到 此目的节点不可达或者不再被需要时为止。反应式路由协议开销较小，但是数据报 传送的时延大，不适合应用于实时性场合。已提出的该类协议主要有d s r ( d y n a m i c s o u r c er o u t i n g ) 、t o r a ( t e m p o r a r yo r d e r e d r o u t i n ga l g o r i t h m ) 、a o d v ( a dh o e o nd e m a n dd i s t a n c ev e c t o r ) 、l a r 1 ( l o c a t i o na i d e dr o u t i n g ) 路由协议等。 混合式路由协议是在先验式路由协议和反应式路由协议的基础上而提出的。它 结合了两种路由协议的优点，同时避免了各自的不足，既减少了寻求路由的时延， 又减少了路由控制信息的丌销。典型的协议有z r p ( z o n er o u t i n gp r o t o c 0 1 ) 和c e d a r ( c o r ee x t r a c t i o nd i s t r i b u t e da dh o er o u t i n g ) 协议。 2 4a dh o e 网络的o o s 服务质量保证 q o s 通常是指用户对通信系统提供的服务的满意程度，是一个系统的非功能化 特征。它的目标是获得更加确定的通信行为，能够更加安全可靠地保护网络承载的 信息，并更加高效地使用网络资源。一般采用两种策略来保障网络的q o s ：一是提 供足够的网络资源来避免资源竞争，方法较为保守；二是对特定分组进行标记并提 供不同的优先级别，从而确保某些特定业务的服务质量，比如i e t f 提出的区分服务 模型( d i f f s e r v ) 和综合服务模型( i n t e r s e r v ) 。但是这些服务模型并没有考虑无线 移动的网络环境，而现有的无线网络中一般只有具有基础设施的单跳蜂窝模型具备 q o s 保障机制，它也无法直接在多跳、拓扑动念变化的移动a dh o e 网络中应用。 为给a dh o c 网络中的各种业务提供相应的服务质量保证，就必须要求设计和研究新 的q o s 保障机制心引。 现已提出的较为常见的a dh o c 网络q o s 保证方法有以下几种： ( 1 ) 动态服务质量保证机制：动态服务质量保证机制是一种基于资源预留的、服 l 】 青岛大学硕士学位论文 从综合服务模型( i n t e r s e r v ) 的方法。资源预留请求规定了一个预约请求范围，网 络节点实体通过对此请求范围进行判断和决定，从而灵活地提供服务。各种网络实 体在预约请求范围( 从能接受的最小服务级别到能得到的最大服务质量等级) 内根 据网络的资源状况进行动态的自适应调整，提供一种在动态环境下灵活的q o s 保障 方法。 ( 2 ) 支持q o s 的信道接入协议：支持q o s 信道接入协议的目标是在a dh o c 网络 中，各个节点能在尽量不影响其他节点的前提下，共享媒体，并且实现自身的q o s 要求。 ( 3 ) 具有q o s 能力的中间适配机制：采用带有中间适配件的网络框架来动态地 适应网络性能的变化是a dh o c 网络提供的另外一种q o s 保障的策略。它考虑了网 络的性能和端到端的资源状况，向具体应用提供了用于重新配置资源的有用信息， 使得整个系统获得最优的q o s 保障等级。 ( 4 ) o o s 路由：首先通过带有q o s 信息的路由进行有效的控制，用以防止网络的 过载，然后寻找满足q o s 要求的路由，提供足够的路由资源信息，为管理控制机制 提供支持，最终完成全网资源的有效利用。q o s 路由协议可以基于各种现有的路由 算法来构造，每个节点在其路由表中增加相应的q o s 信息( 如带宽和时延) 字段， 在计算最短路径的同时计算各种q o s 信息，并根据计算后的q o s 信息来决定是否接 纳新的连接请求。 与固定有线网络相比，a dh o c 网络的q o s 保障问题更加复杂和难以实现。 2 5 本章小结 本章主要对a dh o c 网络进行了简要的概述。首先介绍了a dh o c 网络的定义及 特点，然后从网络拓扑方面分析了a dh o c 网络的体系结构，最后对a dh o c 网络路 由协议的现状和分类以及a dh o c 网络的q o s 服务质量保障进行了说明。 1 2 第二章a dh o e 网络的分簇算法及改进 第三章a dh o e 网络的分簇算法及改进 3 1 分簇算法的概述 在一般的应用中，a dh o c 网络可以采用平面结构或分级结构，但是在网络规模 较大并需要提供一定的o o s 支持时，通常需要采用分级结构。分级结构的网络具有 较好的网络可扩展性，网络规模不受限制，节点定位比平面结构简单，并且路由和 控制丌销较小。a dh o c 网络常常通过分簇的方法来构造分级结构。如图3 1 所示。 网络中的节点被划分成若干个簇，每个簇由一个簇头和多个簇成员( 普通节点) 组 成，簇头和网关( 或分布式网关) 形成高一级的虚拟骨干网。 一、 、一一，簇 簇头 簇成员 图3 1 分级网络结构 干网) 在分级结构中，簇头的任务相对较重，它需要维护到达其他簇头的路由，并且 要负责管理和协调簇内的节点，有可能成为网络的瓶颈，因此在分簇算法中最关键 的就是簇头的选举。不同的分簇算法，簇头选举规则不同，具有不同的优化目标， 包括最小化簇头、最小化簇计算和维护丌销、最大化节点生存时间、和最大化簇稳 定性等。分簇算法的选择依赖于应用的需求、网络的环境和节点的特征。采用不同 的分簇算法对网络性能将有很大的影响。 1 3 青岛人学硕士学位论文 3 1 1 相关定义和说明 a dh o c 网络的拓扑结构可以用g = ( 啦) 表示，即它可以看作是由网络中各移动 节点与链路构成的图。其中，v 表示节点的集合，e 表示边的集合。如果节点z 与y 是可以互相通信的一跳邻居节点，则节点工和y 之间存在边0 ，) ，) 。 说明1 ：节点i d 是一个能够排序的字符串，它用来唯一标识一个节点，例如节 点的m a c 地址可以作为其i d 。 定义1 ：簇头( c h ) 是按照某种规则或分簇算法选举出来的负责管理和协调其所在 簇内的所有成员的节点。一个簇只有一个簇头节点，其他节点均称为簇成员。 说明2 ：一个簇的簇头节点数目应该唯一。当簇内的拓扑结构稳定后，簇头节点 可以在较短的时间内掌握其所有簇内成员节点的信息。 定义2 ：节点工和y 之间的最小跳数被定义为两节点之间的距离d ( x ，) ，) 。当节点 z 和y 可以直接通信时，d ( x ，y ) = l ；否则d ( x ，y ) 1 ，倘若节点工和y 经过其它任何节 点的转发也不能彼此通信，那么d ( x ，) ，) = 。 定义3 ：对于具有簇头h 的簇g 而言，称簇g 为七跳有头簇，当且仅当簇内的 任何节点x 到簇头h 的距离最多为七跳，即m a x d ( x 力) 歹g - - k ；对于不选举簇头i l 的簇c ，而吉，称簇g 为k 跳无头簇，当且仅当簇内任何两个节点x 和y 的距离不超 过k 跳，即m a x d ( x , y ) , x , y c ! 或。k = l 的无头簇内任何两个节点都可以直接通信， 称其为全连通簇。 定义4 ：一个节点x 的簇集合用f j 表示，它是指包含节点石的所有簇的集合， 即f 工= g k g 。称节点x 为交叠节点，当且仅当f j 的基数 f j i 2 ，即它同时属于 两个或两个以上的簇。若交叠节点工同时位于两个( 或两个以上) 簇头的通信范围 内，则称工为网关节点。例如，图3 2 中交叠节点是节点5 、6 、7 和8 ，而网关节点 只有节点5 和8 ，并且万5 = 占8 - 2 。 定义5 ：分布式网关节点是属于不同的簇但彼此位于通信范围之内的节点，也被 称为中继器，如图3 2 中的节点l o 和1 4 。一个分布式网关节点通过一跳距离可达的 簇( 包括自己所在簇) 的数目成为分布式网关节点的阶数d ( d 苫2 ) 。 定义6 ：节点度被定义为一个节点的一跳邻居节点的数目。如节点七的度数 n o ( k ) = 0 w c l l l 。当七的节点度n d (