（计算机应用技术专业论文）基于新型分簇算法的ad+hoc组合qos路由协议——hiacqostora.pdf

董垂堑型坌篓堡鎏墼些坠堡垒坌堕塑童垫堡 垫茎 摘要 a dh o c 组合q o s 分层路由协议强- a c q o s t o r a ，是一种组合q o s 路由 算法。h i - a c q o s - t o r a 建立在均匀、有效的分簇算法的基础之上，簇内使用蚁群 算法完成多指标的q o s 路由，簇间使用简单、快捷的t o r a 路由算法，从而很好 地保障了分层组合q o s 路由的实现。随着计算机技术的产生和发展，将会对这一问 题进行更加深入的研究。 一个良好的分簇算法是进行分层路由协议研究的关键和前提。在研究了前人所 提出的分簇算法之后，确立了新的分簇算法的设计目标，在满足这一目标的前提下， 褥出了一种新型分簇算法s a c a ，并从理论和初步的实验上证明了s a c a 确实 可以满足这一设计目标。也就是说s a c a 适用于大规模a dh o c 网络，而且即使是 在移动设备高速运动的状态下，s a c a 依然是易于实现的。接下来，在仿真实验中 和现有的分簇算法进行分析比较，证明了s a c a 算法可有效解决均匀分簇、均衡结 点负担、保持簇结构的稳定性等问题，并能够满足大规模高速运动a dh o c 网络的 要求 使用s a c a 确立了分层结构之后，为了能够在大规模a dh o c 网络中实现满足 q o s 要求的分层路由，利用蚁群算法来解决满足时延，延迟抖动、线路带宽、分组 丢失率和费用多个指标的簇内q o s 路由；而在簇问路由方面，则使用尽可能简单的 t o r a 算法。这就是m a c q o s t o r a 。并使之和d s d v 、d s r 、z r p ，t o r a 等 协议比较，简要分析了m a c o 娼t o r a 的性能。在实验环节中，首先，分析了 a dh o e 网络路由协议的评价标准；然后，从控制包的数量、数据包的传送精确度 和跳数三方面与t o r a 、l a y e r e d - t o r a 进行比较分析，最终证明了 h i - a c q o s - t o r a 是一个a dh o c 网络中很有效的分层组合q 0 s 路由算法。 关键字：自组网：路由；服务质量；跳数；分簇算法；分层路由协议；簇内路由； 簇问路由；蚁群算法； 江南大学硕士研究生学位论文 a b s t r a c t c o m b i n a t i o no o s l a y e r e dm u t i n gp r o t o c o l o fa dh o cn e t w o r k - - h i - a c q o s - t o r a , i sac o m b m a t i u nq o sm u t i n ga l g o r i t h m h i - a c q o s - t o r ai sb a s e d o nt h ew e l l - p r o p o r t i o n e da n de f f e c t i v ec l u s t e r i n ga l g o r i t h m i nt h i sr o u t i n ga l g o r i t h m ，t h e p r o b l e mo ft h em u l t i - t a r g e tq o sm u t i n gi nc l u s t e ri sa c h i e v e d ；w h i l ea m o n gc l u s t e r s 。a s i m p l ea n dq u i c km u t i n ga l g o r i t h mi su s e d s oc o m b i n a t i o nq o sl a y e r e d r o u t i n g i s a c c o m p l i s h e d a l o n g w i t hc o m p u t e rt e c h n i q u e se m e r g e n c ea n d d e v e l o p m e n t , t h i sr e s e a r c h w i l lb ef u r t h e rd c e pa n db r o a d t h ep r e m i s ea n dk e yo ft h er e s e a r c ho fl a y e r e dm u t i n gp r o t o c o li sa ne x c e l l e n t c l u s t e r i n ga l g o r i t h m b a s e do nt h ee x i s t i n gc l u s t e r i n ga l g o r i t h m s , an e wc l u s t e r i n g a l g o r i t h md e s i g n i n ga i mi se s t a b l i s h e d s a c a , an e wc l u s t e r i n ga l g o r i t h mi sf o u n d , i n o r d e rt of i tf o rt h a ta i m a c c o r d i n gt ot h e s i m u l a t i o ne x p e r i m e n t ，t h er e s u l t sp r o v et h a tt h i s a l g o r i t h mi sa b l et of i tf o rt h i sd e s i g n i n ga i m t h a ti st os a yt h a ts a c a f i t sf o rl a 唱ea d h o en e t w o r ke v e nw h e nm o b i l ed e v i c e sm o v ea tah i g hs p e e d t h es i m u l a t i o ne x p e r i m e n t s h o w st h a tt h i s a l g o r i t h m i sa b l et os o l v et h e p r o b l e m s , s u c h a s c l u s t e r i n g w e l l - p r o p o r t i o n e d , b a l a n c et h eb u r d e no fn o d e s ，m a i n t a i nt h es t a b i l i t yo fc l u s t e rs t r u c t u r e , a n d 锄m e e tt h er e q u i r e m e n t so ft h el a r g eh i g hs p e e dm o v e m e n ta dh o cn e t w o r k a f t e ru s i n gs a c at oe s t a b l i s ht h eh i e r a r c h i c a ls t r u c t u r e i no r d 盯t os o l v et h el a y e r e d m u t i n gm e tt h eq o sr e q u i r e m e n ti nl a r g ea dh o cn e t w o r k ，u s ea n tc o l o n ya l g o r i t h mi n c l u s t e rr o u t i n g , t h em u l t i t a r g e tq o sr o u t i n gp r o b l e mi ss o l v e dw i t hd e l a y , d e l a yj i t t e r , b a n d w i d t h ，p a c k e tl o s sa n dt h el e a s tc o s tc o n s t r a i n t s a m o n gc l u s t e r sas i m p l ea n dq u i c k r o u t i n ga l g o r i t h mi su s e d 。t h a ti sh i - a c q o s t o r a a n dt h e n , c o m p a r e dw i t hd s d v d s rz r p , t o r a , t h ep e r f o r m a n c e so fh i a c q o s - t o r ai ss i m p l ya n a l y z e d a m o n gt h e e x p e r i m e n ts t a g e ，t h ee s t i m a t e ds t a n d a r d so fa d h o cn e t w o r kr o u t i n g p r o t o c o l si na dh o e n e t w o r ka r eg i v e n f r o mt h et h r e ea s p c c t t h cn u m b e ro fc o n t r o lp a c k a g e s , a c c u r a c yo f p a c k e t , d e l i v e r ya n dh o pc o u n t s - - c o m p a r e dw i t ht o r a a n dl a y e r e d - t o r a i nt h ee n d , h i a c q o s t o r ai sp r o v e di ti sa ne f f e c t i v ec o m b i n a t i o nq o sl a y e r e dr o u t i n gp r o t o c 0 1 k e yw o r d s ：a dh o cn e t w o r k ；r o u t i n g ；o o s ；h o pc o u n t ；c l u s t e r i n ga l g o r i t h m ；l a y e r e d r o u t i n gp r o t o c o l ；r o u t i n gi no u s t e r ；r o u t i n ga m o n go u s t e r s ；a n tc o l o n y a l g o r i t h m ； n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 q 辱6 只 t 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 躲五江 1 1 课题的背景眦i i i 第1 章绪论 随着信息技术的不断发展，人们对移动通信的需求越来越高。近年来，移动通信 技术得到了飞速发展和普及。尽管在短短几十年间。蜂窝移动通信网络系统已经完成 了从第一代向第二代跨越的历史使命，并正在向第三代跃进，但是由于蜂窝移动通信 系统需要集中式控制并且网络的运行是基于预先架设好的网络设施的特点，使得蜂窝 移动通信系统对有些特殊场合来说并不适用，例如，战场上部队的快速展开和推进、 发生地震等灾害后的营救。在这些场合中，不能依赖于任何预先架设的网络设施进行 通信，因为多数预先搭建好的网络基础设施已经在灾害中损坏并失去了本身的价值， 而且基于对健壮性的考虑也不能采取有中心的控制方式。因此，需要一种特殊的通信 系统，这种通信系统不需要基于任何预先架设好的网络设施便可以运行，可实现临时 快速自动组网，具有很强的抗毁性。a dh o e 网络满足了这些要求。 1 1 1a d h o e 简介 a dh o e 网络的前身是分组无线网( p a c k e t r a d i o n e t w o r k ) 。由于军事上的需求对 分组无线网的研究已经进行了2 0 多年。2 0 世纪7 0 年代，美国国防部高级研究计划 局( d a r p a ，d e f e n s ea d v a n c e dr e s e a r c hp r o j e c ta g e n c y ) 资助研究了分组无线网 ( p r n e t , p a c k e tr a d i o ) 的项目，主要研究分组无线网在战场环境下如何进行数据通 信，在研究过程中产生了一种新型的网络架构技术。之后，由于d a r p a 的资助，在 1 9 8 3 年和1 9 9 4 年又进行了两个项目的研究，一个是具有抗毁性的自适应网络 ( s u r a n ，s u r v i v a b l e a d a p t i v en e t w o r k ) ，另一个是全球移动信息系统( g l o m o ，g l o b a l m o b i l ei n f o r m a t i o ns y s t e m s ) 。前者主要研究如何将p r n e t 的成果加以扩展，以适应 大规模的网络，并且可以应对战场上瞬息万变的环境；后者，则是比前者更深层的研 究，主要研究方向是要建立能够满足军事需要的高效、侠捷、高抗毁性的移动通信系 统。1 9 9 1 年5 月，i e e e s 0 2 。l l 标准委员会正式成立，首次用“a dh o e 网络”一词来 描述这种特殊的自组织、对等式、多跳无线移动通信网络。a d h o e 网络也由此产生。 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 ”，意思是“特殊 的、临时的”。由于翻译后的名字很难描述该网络的特点，为了避免引起歧义，就用 a d h o e ”一词来称呼这种特殊的无线网络。 a d h o e 技术汲取了p r n e t 、s u r a n 以及g l o m o 等项目的思想，从而产生的一 江南大学硕士研究生学位论文 种新型的网络架构技术。目前，a dh o e 网络继承和发扬了d a r p a 资助无线分组数 据网的思想，特别是p r n e t ( p a c k e tr a d i o ) 。p r n e t 强调的是在一个广阔的区域实 现多跳的无线通信，基于这种多跳的无线信道特点，p r n e t 面临着诸如介质接入、 寻址、路由、网络初始化和控制等难题。但p r n e t 所倡导的系统自组织 ( s e l f - o r g a n i z i n g ) 特性式的p r n e t 网络系统组建灵活，网络的抗破坏性强。 a dh o e 网络中所有结点的地位平等，无需要设置任何中心控制终端，具有很强 的抗毁性。网络是由一组带无线收发装置的移动终端组成的一个多跳的临时性的自治 系统。网络中的移动终端不仅具有普通移动终端所需要的功能，而且还具有路由和报 文转发功能。可以通过无线连接构成任意的网络拓扑。这种网络可以独立工作，也可 以接入有线网络或蜂窝无线网络。 a dh o e 网络是一种特殊的无线通信网络。其主要特点如下： ( 1 ) a d h o e 网络具有很强的独立组网能力，不需要基站的支持，结点开机后可 以快速、自动组网。 ( 2 ) a dh o c 网络采用了无中心结构，所有结点地位平等，组成一个对等式网络， 其问的结点可以随时加入或者离开网络，任意结点的故障不会影响整个网络的运行。 这一特点决定了，a dh o e 网络具有很强的抗毁性。 ) a dh o e 网络没有严格的控制中心，所有结点通过分层的网络协议和分布式 算法协调各自的行为。无中心和自组织的特点使得a d h o e 网络成为快速自组织网络。 ( 4 ) 由于结点发射功率的限制，结点的覆盖范围是有限的。当要与自身所覆盖 范围之外的结点相互通信时，需要中间结点的转发，即要经过多跳。与普通的网络中 的多跳不同。a dh o e 网络中的多跳路由是由网络中的普通结点共同协作完成的，而 不是由专门的路由设备来完成。相反，如果可以使用多跳路由，结点的发射功率可以 很低，从而达到节省能量的目的。 ， ( 5 ) a d h o e 网络中，所有移动终端能够以任意的速度移动，随时进入或离开网 络，再加上外界环境和天气的变化使得移动终端通过无线信道形成的网络拓扑结构具 有随时变化的可能性，而且其变化速度难以预测。这些变化主要体现在结点和链路的 数量和分布上。所以a dh o c 网络的路由是区别与传统的有线网络和蜂窝网络的路由 的。因此对a dh o e 网络路由的研究也就颇具意义。 1 1 2a dh o e 网络q o s 路由问蹶 q o s 是指网络在传输数据流时要求满足一系列服务请求，这些请求具体可以量化 为传输延迟、丢失率、带宽要求、延时抖动、吞吐量等q o s 指标。随着网络对多媒 体技术和实时技术的支持，越来越要求网络能够提供满足多个指标的q o s 路由，因 此，a dh o e 网络的q o s 路由问题就成为当前研究的热点。 2 r f c 2 3 8 6 是这样定义o o s 路由的：一种基于网络的可用资源和业务流的o o s 要 求来选择路径机制或一种包含各种o o s 参数的动态路由协议。衙两言之，o o s 路由 用来查找满足o o s 要求的路径o o s 要求可以是一维的，也可以是多维的参数。相 应的o o s 路由被称为一维或多维o o s 路由。o o s 参数按照特性可以划分为3 种 可加性参数、可乘性参数和最小化参数。 目前，国内外对a d h o c 网络q o s 路由协议这方面的研究，主要集中在单一指标 下的q o s 路由协议的研究即使是两个或两个以上的多指标的o o s 路由协议，也往 往是基于平面结构的，而不是基于分层结构。而且对于a dh o c 网络中的q o s 路由协 议往往要考虑如下五点实施方匿的困难。 ( 1 ) 动态变化的网络拓扑结构使信息的收集和维护非常困难。在a dh o c 网络 中，链路的状态受结点的移动及周围环境影响较大，尤其是在大规模的网络中，带宽、 时延、等链路参数很难进行即时获取和更新维护 ( 2 ) 由于网络的动态变化，路由信息的汇集、引入具有不准确性，为确保安全 而隐藏存在的路由信息等因素将造成不准确的q o s 路由。 ( 3 ) 由于网络处于动态变化过程中，因此更新频率难以确定 ( 4 ) 计算、存储和通信的开销较高，可扩展性较差 ( 5 ) 基于约束的q o s 路由选择将更加困难。z w a n g l 引曾经证明，当路由选择 的约束条件包含两个或两个以上的可加参数，或者包括可加性参数和( 或) 可乘性参 数的组合时，该路由选择就是n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 完全问题。在这样 的情况下，需要采用启发式算法来寻求次优化解。 因此进行基于分层结构的多指标组合o o s 路由协议的研究，是很有价值的。 在a dh o e 网络中，实施o o s 路由策略涉及以下s 个方面： ( 1 ) 选择合理的o o s 尺度：合理地选择q o s 尺度非常重要，它反映了应用所关 心的网络特性并定义了提供o o s 保障的类型。衡量o o s 的指标很多，包括时延、带 宽、分组丢失率和网络吞吐量等。寻找一条满足多个约束条件的o o s 路径通常是n p 完全问题，所以实现多维o o s 指标的方法一般是不可取的，而应根据实际情况来选 择某一、两个合适的指标。通常选择链路的可用带宽或分组丢失率作为o o s 参数， 因为这两个指标的代价相对较低。 ( 2 ) q o s 路由的计算：结点根据收集的网络状态信息来寻找q o s 路由时，应尽 量减少路由计算的复杂性。通常寻找满足单一约束条件的q o s 路由。但有些场合下 可能需要解多维约束的q o s 路由。此时，可以采用多个q o s 尺度按照某种顺序排列， 首先基于第一个尺度寻找可行路径，然后再根据第二个尺度所得到的可行路径集合中 进行筛选，直到满足所有的q o s 尺度 ( 3 ) q o s 路由维护问题：路由更新的频率和消息的大小应能自适应地调整，以 便在路由开销和准确性上做出合理折衷。一种可行的办法是，判定状态信息的改变是 3 江南大学硬士研究生学位论文 否超过预定门限制，只有当此条件为真时才需要交换信息。并且要尽量维持原有路由， 从而减少计算开销和性能抖动。 ( 4 ) 对现有的a dh o c 路由算法进行改进，使其可以支持特定的o o s 要求：每 个结点可以在路由表中增加相应的o o s 信息，计算最短路径的同时计算出各种o o s 信息，每个结点根据q o s 信息来决定是否接纳新的连接请求。现存的许多算法如 t o r a 、d s r 、a o d v 等都是按需路由算法，利用这一特点并选用最小可用带宽作为 衡量指标，可以大大减少o o s 路由的复杂性。 ( 5 ) 组合o o s 路由算法：在分层结构的a dh o c 网络中，由于网络规模增大， 很难在全局范围内实现q o s 路由。因此，可以考虑使用在簇内和簇问采用不同的o o s 路由算法，即使用一种组合q o s 路由算法。簇内q o s 路由通常应满足：如果存在符 合o o s 要求的可选路径，路由机制应该可以找到该路径。而簇问路由主要关心可靠 性和可扩展性，因此，要尽可能选择适应性好、简单、快捷、信息交换频率不快的算 法 本课题正是采用了组合o o s 路由的思想将现有的a dh o c 路由算法进行改进，来 解决多指标下的o o s 路由问题。 1 2 国内外在q o s 路由问题方面的研究现状1 l 1 2 1 国外的研究现状 由于a dh o c 网络的研究意义重大，所以很多国家的无线通讯技术人员在这方面 展开了大量的研究工作。目前，美国已有很多学校和机构都加入到了对a d h o c 网络 技术的研究中。a dh o c 网络o o s 路由问题也得到了广泛的关注和研究。并取得了一 些研究成果，下面简单介绍一下现有的已有的a dh o c 网络o o s 路由协议的设计目标 和思路。 支持o o s 的a o d v 和d s d v 路由对原始的a o d v 和d s d v 路由算法进行了扩 展，使它们能够计算满足带宽要求的o o s 路由，以此来增加网络的吞吐量并减少分 组的投递时延。这类o o s 路由算法的实现复杂度较低，但是它们只适用于规模较小、 移动性较低的网络，并且不能支持单向信道。 链路状态o o s 路由协议( l s _ o o s ) 对传统的链路状态路由协议进行了扩展，以 分组平均错误率和生存时闻作为路由指标，以便寻找信号接受质量和信道稳定性较好 的路由。 f s r 路由利用了鱼眼睛的特点，即节点的距离越近，它们交换路由信息越多；反 之，交换的路由信息越少。f s r 协议开销较小，具有较好的可扩展性，特别是在移动 性较强并且带宽有限的情况下。 4 s t a r ( s y s t e ma n dt r a f f i cd e p e n d e n t a d a p t i v er o u t i n g ) 协议考虑了无线链路的带 宽和排队时延等因素，它采用路径平均时延作为路由计算指标，并尽量将流量平均分 配给所有的可用路径来减少网络拥塞。 现有的大多数a dh o c 网络的q o s 路由算法都是针对某一个q o s 指标进行设计 的，不同的算法之间不能兼容。以上介绍的q o s 路由算法都没有特别考虑节点的能 量约束这在很多时候不能满足系统的能量效率要求，并会影响网络的整体性能。但 是对a dh o c 网络，设计能量高效的q o s 路由面临很多困难，需要这种考虑节点的能 量耗费和链路的传输功耗，节点使用能量的公平性问题，及如何综合使用功率控制、 动态信道分配和智能电台休眠机制来解决能量耗费问题。能量约束的q o s 路由非常 复杂，减少路由信息交换可以节省节点的能量，但是得到的路由可能不是能量高效的； 采用流量分离的方法可以改善节点能量耗费的公平性，但是得到的路由不一定是资源 高效的。因此，能量约束路由需要在q o s 要求、电池寿命和路由效率之间进行折衷， 它的目标是在能量约束的条件下使通信性能最优，或以最小的能量耗费来满足预定的 通信性能。因此，a d h o c 网络q o s 路由是个很复杂，且又很具有研究意义的问题。 1 2 2 国内的研究现状 由于a d h o c 网络的重要性，所以自2 0 世纪9 0 年代国内的一些大学也开始关注 a dh o e 网络方面的技术，并进行研究。目前国内对a dh o c 网络进行研究的现状比较 零散，缺乏统一的规划和协调，没有相应的官方和民间组织来协调大家的研究工作。 由于a dh o c 网络技术在民间的应用基本是空白，所以a dh o c 网络技术的关注和支 持的力度是很有现的。 目前国内对于a d h o c 网络路由协议的研究主要集中在平面路由协议这一部分。 经过查阅大量文献表明，也有进行a dh o e 网络分层协议的研究，如解放军理工大学 和中国科学院，但都处于分簇算法的研究阶段。如果想实现大规模的a dh o c 网络的 路由，那么研究a dh o c 网络分层协议是要解决问题的关键。 经过一段时间的资料搜集，国内对a d h o c 网络分层q o s 路由协议的研究实属空 白。能查到的仅仅是综述性的资料。 1 3a dh o c 网络q o s 路由问题的研究意义o l g 随着技术的进步和社会的发展，特别是人们对个人通信日益增长的需求，使得 a dh o c 网络的应用范围正逐步扩大，包括在军事和民间等诸多领域的应用。在军事 方面，a dh o c 网络可以支持野外联络、独立战斗群和舰队战斗群通信、无人侦察与 情报传输等；而在民用方面，它支持诸如移动会议、移动网络、个域网络、自然或人 江南大学硕士研究生学位论文 为灾难营救过程中的信息交换以及临时交互式通信组等。在不久的将来，这种技术将 在移动通信的市场上扮演非常重要的角色。 具体在a dh o c 网络分层路由领域，也就是本课题的研究也是颇有意义的。 在分簇算法方面，当a dh o c 网络的规模变大时，为了提供高效的通信支持。必 须构件分层网络，通过分簇算法来实现节点群的划分。由于a dh o c 网络的节点是不 断移动的，网络是动态的，分簇算法必须适应网络拓扑的动态变化，调整节点的归属。 但是，目前对分簇算法而言，还没有一个统一的设计目标。有的算法使分出的簇最小， 有的算法使分得的簇最少，有的更能适应动态变化的网络拓扑。因此，在研究过程中， 必须先要设立分簇算法的目标和考核标准，然后设计满足最终需要的分簇算法。 对于路由协议而言，虽然有大量的研究成果。但这些成果都是基于某种网络拓扑 和应用环境而设计的，或是基于某个约束条件而设计的。a dh o c 网络的路由协议可 分为平面路由协议1 2 】和分层路由协议【2 】。在平面路由协议中，网络结构简单，网络中 的结点都处于平等的地位，它们所具有的功能完全相同，各结点共同协作完成结点间 的通信。随着网络规模的逐步扩大，和a dh o c 网络应用的普及，网络规模、网络拓 扑、组网形式等方面都呈现出一定的多样性，能够满足这种多样性的路由协议还非常 少见。此外，对于实时业务的支持，路由协议要能够提供带一q o s 的路由选择功能， 这牵涉到多约束条件的路由协议，目前仍是一个难点。同时网络中结点的数目也不断 增加，每个结点要想维护整个网络的拓扑信息或是进行远距离结点之间的路由都将十 分困难，因此产生了分层路由协议。在分层路由协议中，网络结点被分成多个簇，源 结点到目的结点的路由又分为簇间路由和簇内路由，所以分层路由协议可有效用于大 规模的a dh o c 网络。但若能够在分层路由过程中找到一条q o s ( q u a l i t yo f s e r v i c e ) 路径，满足用户对线路的带宽、延迟抖动和费用的要求，提供端到端的服务质量保证， 那么这样的路由协议就可在要求很高的网络中得到应用，将比研究单纯的路由协议更 具有实用意义。正是由于这些，才开始了对这一问题的研究。 总而言之，a dh o c 网络虽然出现了很多年，但它仍是一门新兴的网络技术，很 多问题有待进一步解决。随着对a dh o c 网络技术全面关注的程度提高，会有越来越 多的学者对a dh o c 网络中q o s 路由协议进行研究。a dh o c 网络技术一定会得到快 速发展并逐步走向成熟，会在越来越多的场合中得到应用，也必将在相关领域中展现 出其特殊的作用。因此，无论是对军事还是民用，对其研究都颇具意义。 1 4a dh o c 网络分层q o s 路由协议的研究思路 对a dh o c 网络分层q o s 路由协议的研究大致可从以下三个方面进行。 首先，是分簇算法，一个良好的分簇算法是进行分层路由协议研究的关键和前提。 而且如何选取簇头，本身就可以考虑q o s 的特性。如考虑结点度数、结点的传输功 6 董堑型坌堡塞垒墼垒! ! 些堡垒坌堑墼查望堡薹! 至堑垒 率、结点的剩余能量等方面来选举簇头。 其次，是簇内路由和簇间路由。根据所选取的分簇算法来设计合适的簇内和簇问 路由。路由算法的好坏将直接影响到a dh o e 网络的信息传递的效率。 最后，是进行q o s 路由协议的设计，由于q o s 路由协议是不同于一般的路由协 议的，所以仅仅使用简单的路由协议进行改进，或者是将有线网络的q o s 路由协议 应用到a dh o e 网络中的想法基本上是行不通的。所以设计好的a dh o e 网络q o s 路 由协议是很重要的研究方向。 除此之外，还有一些研究的方向，如组合q o s 路由协议、多指标下的q o s 路由 协议等等。但是最基本的还是以上三方面。 根据调查讨论，将此课题的研究思路也按照阻上三个方面进行。 1 5 论文的结构 论文的写作顺序也是课题开展的先后顺序。整篇文章的结构如下： 首先，本课题是在研究分层结构的基础上，建立了一种新型、有效、可自我调节 簇结构的分簇算法s a c a ( s e l f - a d j u s t i n gc l u s t e r i n g a l g o r i t h m ) ，并在理论上给以证明， 这一部分在论文的第二章讲述。在第三章中，通过模拟实验，将s a c a 和其他常用 分簇算法的性能进行比较分析。接着，第四章给出了基于这种新型分簇算法并满足 q o s 要求的新型组合路由算法：h i - a c q o s t o g a ( h i e r a r c h i c a l a n t c o l o n y q u a l i t y o f s e r v i c e t e m p o r a l l y - o r d e r e d r o u t i n g a l g o r i t h m ) 。最后，在第五章中，通过实验证明了 此路由算法的优越性。 1 6 课题的任务 整个研究课题所完成的任务是使移动设备可以自我调节簇结构，且分簇结果很均 匀，能够在簇内使用蚁群算法【9 1 【1 0 1 来解决在多个约菜条件下的q o s 路由，而簇间使 用尽可能简单，信息交换频率不快的路由算法，这种组合q o s 路由协议有期望在较 大规模的网络中实现多指标q o s 路由。经查阅大量资料表明，这样的解决方案并不 多见。 7 江南大学硕士研究生学位论文 第2 章分簇算法_ s a c a a dh o c 网络是由移动结点和它们之间的无线连接组成的临时性无线移动网络， 没有基站和交换中心的支持。a dh o c 在民用、灾难恢复和军用中都发挥着重要作用。 伴随着a dh o e 网络的不断发展，人们在寻求一种能够有效管理大规模a dh o e 网络 的方法。基于分簇结构的分层路由协议，以提高网络的健壮性、可扩展性和有效性为 目的而设计。它首先利用分簇算法将网络分为多个簇，整个路由协议又分为簇间路由 和簇内路由。因此分簇算法的好坏将直接影响到分层路由协议的性能和实用性。本文 是在研究前人的分簇算法的基础上，设计了一种新型分簇算法 s a c a ( s e m a d j u s t i n gc l u s t e r i n g a i g o r i t h m ) 。主要特点是，它不像以往的分簇算法 以一个或某几个指标来进行分簇，而是在保持各个簇的规模基本相同的基础上，从结 点之间的相互关系和结点职能的角度出发来自我调节簇结构。其目的是使s a c a 适 用于大规模a dh o e 网络，有效解决均匀分簇、均衡结点负担、保持簇结构的稳定性 等问题，并且即使是在移动设备高速运动的状态下，这种分簇算法都易于实现。 2 1 基本概念 定义l ：a dh o c 网络的拓扑记为g = ( 啊) 。y 表示结点的集合，表示边的集合。 ( v ，动e e ，表示结点i 和结点之间存在无线连接，并且结点叶和结点v ，互为邻接结 点。 定义2 ：令g = g i ，0 2 ， ) 。g 表示簇i d 为k 的簇。其中簇6 仁( v k , e k ) ， 以= 珞u 圪i u ，其中p 么、硌t 和p k 分别表示簇k 的控制结点( 簇头结点) 、网关 结点和一般簇成员结点。并且g ng ，= o ( 为) ，即簇g 和g 为非交叠簇。 定义3 ：簇g l 是g 的子集合。g ，包括簇头结点和簇内的成员结点。簇头结点 在簇内充当管理者的角色。簇头结点也是簇的成员之一，其结点d 就是簇i d 。簇头 结点控制着簇内结点的数量。形成一个簇需要满足以下两个条件：具有相同簇i d 的 簇成员之间是互连的；簇成员的数量( 1c j l ) 必须介于上界( 和下界( ) 之间。如果簇成 员的数量小于下界厶那么这个簇就要试图和其邻接的簇合并。相反，如果簇成员的 数量大于上界u ，那么这个簇就要分裂为两个簇，其中u ，_ 2 l 。簇的合并与分裂由簇 头进行管理。 定义4 ：如果一个结点的邻接点的簇j d 与自身簇i d 不同，那么就称此结点为网 关。不同簇之间的交流是通过网关来进行的。使用一个状态变量来表明当前结点是簇 头、网关还是簇成员结点，每一个结点的簇i d 和状态变量会随a dh o c 网络拓扑结 构的变化而变化。 董垂錾呈坌堡塞鋈墼笪坚墼堡垒垒垒塑室丝堡篓圣茎坌垄塞彗；耋坠 2 2s a c a 2 2 1s a c & 的设计目标 s a c a 的设计目标： 在保持各个簇的规模基本相同的基础上，从结点之间的楣互关系和结点职能的角 度出发来自我调节簇结构。其目的是使s a c a 适用于大规模a d h o e 网络，有效解决 均匀分簇、均衡结点负担、保持簇结构的稳定性等问题，并且即使是在移动设备高速 运动的状态下，这种分簇算法都易于实现。 2 2 2 结点的行为和状态 为了维持分层结构，每一个结点都执行以下两种行为。 行为i ：结点要定期的用h e l l o 包和其邻接结点交换信息。 行为2 ：如果此结点是簇成员结点，那么它要使用定期通知包( p e r i o d i cn o t i f i c a t i o n p a c k e t ) 向所有的簇成员广播自己的消息。 这两种行为决定结点耽可以检查自己和邻接结点的簇d ，知道自身簇内其他结 点的信息，并判断和改变自身的职能。 结点的状态将是以下五种状态中的一种，它的行为和它的状态有关 n s n ( n o r m a ls t a t en o d e ) 这种状态的结点，既不充当簇头结点又不是网关结 点，而是一般簇成员结点。v i 使用定期通知包广播含有自身结点i di 和簇i dj ( g 中 f 胡。当簇d 为，的结点收到这样的定期通知包时，它们就会认为结点v i 属于簇 为，的簇，并更新结点信息。 c n ( c o n t r o ln o d e ) 这种状态的结点耽是簇头结点。坼广播含有结点i di 和簇 m ，的定期通知包( 其中i = j 3 。含有其所在簇的所有结点的d 。当簇m 为j 的结点 收到这样的定期通知包时，它们就会认为结点是当前簇m 为f 的簇头结点，并更 新结点信息。 b n ( b o r d e rn o d e ) 这种状态的结点是网关与n s n 一样。要以相同的方 式广播定期通知包。假如结点属于簇m 为阿再) 的簇。由于结点要定期的用h e l l o 包和其邻接结点交换信息，这样结点v i 就会收到来自位于不同簇的邻接结点的信息， 根据这一信息决定自己的状态。 b c n ( b o r d e ra n dc o n t r o ln o d e ) 这种状态的结点v l 。兼具网关和簇头结点的角 色 o n ( o r p h a nn o d e ) 这种结点不属于任何簇，是孤立结点。 定义5 ：朋吒是n 的所有邻接结点的集合。n 接收朋晦中的结点发送的h e l l o 包。 9 江南大学硕士研究生学位论文 删j 中的结点通过相互发送h e l l o 包来获得各自的簇d 。 定义6 ：c l u s t e r _ t ( v 1 ) 表示结点v l 在接收到其邻接结点发送的h e o 包并更改簇 前自己的簇i d a u s t e r ( v , ) 指当前的簇。 定义7 ： 耐指结点v i 的所有邻接结点中，结点簇为k 的结点的集合用集 合公式表示为： 髓时= 叶m b a u s t e 啪 m 妒指结点的所有邻接结点中， 公式表示为： 朋略 崎b e 加 辟a 惦t e 口( 啪 任一个结点v l 必定是以上五 种状态的一种，但是结点的状态会 随着结点的移动而发生变化。这种 变化便体现在a - e 五种状态的转 变上。其状态之间的转换如图2 2 1 所示。 发生a 转变的条件： c l u s t e r _ t ( v f ) # c l u s t e r ( v i ) a i = c l u s t e r ( 曲 发生b 转变的条件： c l u s t e r _ x ( v i ) ：c l u s t e r ( v 1 ) a o u s t e r ( 2 2 1 ) 结点簇不为k 的所有结点的集合，用集合 2 2 3 簇i d 的分配和更新 情况l ：若s t a t e ( v i ) = o n ，并且当收到一个来自状态为o n 的结点发送来的妇f f d 包，那么v i 就认为其所有的邻接结点的都是o n ，即 髓吼= 叶h j s t a t c ( d = o n 则令c l u s t e r ( v i ) = i 。 情况2 ：若s t a t c ( v i ) = o n ，并且从其簇为k 的邻接结点那里收到了一个妇，f d 包，那么就认为| v j 6 n n 2 ，则令c l u s t e i ) - - - k 。 情况3 ：j v i a ( c l u s t e r ( v , ) - - k ) a ( i n n , i ) a ( j v j e n n t a ( c l u s t e j ) = m ) ( m k ) ) ， 当v i 收到来自 = f 的h e l l o 包时，就认为彻岈州孵，则令c l u s t 呱碍) ：m ( m k ) 。 2 2 4 簇的合并与分裂 为了保持分层结构的均衡性，每个簇的规模要大致相同。这是由簇的合并与分裂 算法决定的。由于规定了簇的上界u 和下界工的关系是眨牡，所以保证了合并和分 裂算法可以正常运行：并且两个以上的簇的同时合并为一个簇是不允许的。 定义8 ：对于任意簇g f ，它的邻接簇的集合表示为： n g j ： g ，g 知，g m ) ( f i 2 ，j 所o 。设定簇的总个数为r l u m 。 一 1 簇的合并算法 f o “i 卸；i n 啪；i + + ) i f ( 1 g j l l ) 选择g ，的合并对象g i n tj = - l ，m ；l ，m a x = 0 ，m i n = o o ； w h i l e ( g i n g f ) ，如果存在蛾使得j g i + i g d _ u ，那么就要找出簇成员数量最 多的g t + i f ( ( i o ，1 + i g d u ) & ( m i n l g