（通信与信息系统专业论文）一种基于树形骨干网的分簇算法设计.pdf

摘要 摘要 a dh o e 网络是由一系列独立于固定基础设施的移动节点所组成的多跳无线网 络，灵活、快速的组网方式使其成为了当前无线网络研究中的热点之一。由于a d h o c 网络中各节点的自由移动，使得网络的路由选择、q o s 保障面临新的问题， 必须根据网络的规模、扩展性和实时性要求，选择合适的网络拓扑结构和路由算 法，才能最大限度地发挥a dh o e 网络的性能。 近年来，网络规模的扩大和节点移动性的不断增强，使得现有路由协议在路 由效率和负载能力方面无法胜任新的需求，而以分簇方式为代表的分级网络结构 成为解决这一问题的有效手段。针对现有分簇算法在簇首选举规则和网络负载平 衡因素等方面的不足，本文设计了一种新的分簇算法，该算法考虑了影响网络的 多种因素，使用综合权值作为簇首选取的标准，以满足不同的分簇要求，同时用 限制簇规模的方式，提高分簇结构的负载平衡能力。另外，如何组织簇间结构是 本文探讨的又一问题。考虑到树形结构具有无环路、寻径简单的特点，本文采用 树型骨干网建立簇间结构，大幅度降低了路由更新和维护的开销，并使得簇间的 路由更加简单高效。 本文的研究目标是设计一种基于树形骨干网的分簇算法，并分析其基本原理 和网络性能。论文首先对a dh o c 网络的产生背景和发展现状进行了介绍，接着对 a dh o c 网络分簇算法进行概述，并且分析了几种典型分簇算法的原理和算法步骤。 随后，论文介绍了核心树路由协议( i m 心) ，在描述了具体算法之后分析了其特 点和路由性能。在此基础上，提出了一种基于树形骨干网的分簇算法t b b c ，论文 讨论了算法中簇首选举和网关选取等关键问题，设计了算法流程和具体步骤，并 使用o p n e t 仿真验证了算法的性能特点。最后论文进行了总结并提出了今后的研 究方向。 关键字：a dh o c 网络分簇算法核心树路由协议树形骨干网 a b s t r a c t a b s t r a c t a d - h o cn e t w o r ki sa m u l t i - h o pw i r e l e s sn e t w o r kw h i c h i sac o l l e c t i o no fw i r e l e s s n o d e sw i t h o u tt h ea i do fa n ye s t a b l i s h e d i t so n eo ft h eh o t s p o t si nt h er e s e a r c ho f w i r e l e s sn e t w o r ka tp r e s e n tb e c a u s eo fi t sf l e x i b l ea n df a s tn e t w o r ko r g a n i z a t i o n t h e m o b i l i t yo ft h en o d e sb r i n g st h ed i f f i c u l t i e st or o u t i n ga l g o r i t h ma n dq o sg u a r a n t e e t h e r e f o r e ，i ti sn e c e s s a r yt os e l e c ta p p r o p r i a t en e t w o r kt o p o l o g ya r c h i t e c t u r ea n dr o u t e p r o t o c o la c c o r d i n gt on e t w o r ks c a l e , e x p a n s i b i l i t ya n dr e q u e s to fr e a lt i m e t 0e x e r t c a p a b i l i t yo f n e t w o r km o s t i nr e c e n ty e a r s ，a st h es c a l eo fn e t w o r kb e c o m e sl a r g e ra n dn o d e se n h a n c et h e m o b i l i t y , t h ep r e s e n tr o u t ep r o t o c o l sc a n ts a t i s f yt h en e wr e q u i r e m e n to nr o u t i n g e f f i c i e n c ya n dl o a d i n ga b i l i t y h i e r a r c h ya r c h i t e c t u r ew h i c ht a k e sc l u s t e r i n ga l g o r i t h m a sa r e p r e s e n t a t i o ni su s e dt os o l v et h ep r o b l e me f f i c i e n t l y a i ma tt h es h o r t a g eo ft h e p r e s e n tc l u s t e r i n ga l g o r i t h m s0 1 1c l n s t e r h c a ds e l e c t i o na n dn e t w o r kl o a db a l a n c e ，an e w c l u s t e r i n ga l g o r i t h mi sd e s i g n e d , w h i c hc o n s i d e r sl o t so ff a c t o r sa f f e c t i n gt h en e t w o r k , a n dt a k e si n t e g r a t e dw e i g h ta st h es t a n d a r df o rc l u s t e r h e a ds e l e c t i o nt os a t i s f yd i f f e r e n t r e q u e s to fc l u s t e r i n g ，a n dt h es c a l eo fc l u s t e ri sl i m i t e dt oi m p r o v el o a dc a p a b i l i t yo f n e t w o r k b a s e do nc l u s t e r i n g ，t h e r ei sa n o t h e rp r o b l e mo fh o wt oo r g a n z ea r c h i t e c t u r e a l o n gt h ec l u s t e r s c o n s i d e r i n gt h e r ei sn oc i r c l ei nt r e ea r c h i t e c t u r ea n di tc a l lr e a l i z e d s i m p l y , t h et r e e - b a c k b o n ei su s e dt ob u i l da r c h i t e c t u r ea l o n gc l u s t e r s w h i c hc a nr e d u c e t h ec o s to fr o u t eu p d a t ea n dm a i n t e n a n c es i g n i f i c a n t l y , a n dm a k et h er o u t i n ga l o n gt h e c l u s t e rs i m p l e ra n dm o r ee f f i c i e n t n 嵋a i mo ft h i sr e s e a r c hi st op r c s e mac l u s t e r i n ga l g o r i t h mb a s e do nt h e t r e e - b a c k b o n ea n da n a l y z ef u n d a m e n to f t h ea l g o r i t h ma n dt h ei n f e c t i o n0 1 1c a p a b i l i t yo f n e t w o r k n et h e s i sf i r s ti n t r o d u c e st h ea p p e a r a n c ea n dd e v e l o p m e n to fa dh o c t h e n d e s c r i b e st h ec l u s t e r i n ga l g o r i t h ma n da n a l y z e st h ef u n d a m e n ta n dp r o c e d u r e so fs e v e r a l r e p r e s e n t a t i v ec l u s t e r i n ga l g o r i t h m s 髓et h e s i si n t r o d u c e sk e r n e lt r e er o u t i n gp r o t o c o l ( k t r p ) ，a n da f t e rd e s c r i b i n gd e t a i l e da l g o r i t h m i t a n a l y z e st h ec h a r a c t e r i s t i ca n d r o u t i n gc a p a b i l i t y t h e s i sp r e s e n t sac l u s t e r i n ga l g o r i t h mb a s e do nt r e e - b a c k b o n en a m e d t b b c ( t r e eb a c k b o n e b a s e dc l u s t e r i n g ) a n dd i s c u s s e sp r i n c i p l e ss u c h 私s e l e c t i o no f n a b s l l m c t c l u s t e r h e a da n dg a t e w a y , t h e ni td e s i g n sd e t a i l e dp r o c e s sa n dv e r i f i e sp e r f o r m a n c eo f t b b cb yu s i n go p n e ts i m u l a t i o n a tl a s t , t h et h e s i sg i v e sac o n c l u s i o na n dp r e s e n t s t h er e s e a r c hd i r e c t i o n k e y w o r d s ：a dh o en e t w o r k , c l u s t e r i n ga l g o r i t h m ，k t r p , t r e e - b a c k b o n e h i 图目录 图目录 图2 - 1 平面结构的a df l o e 网络5 图2 2 分级结构的a dh o e 网络6 图3 - 1 核心树结构中的相关定义1 8 图3 2 汇聚点的概念说明1 9 图3 - 3a dh o c 网络拓扑示意图一2 0 图4 - 1k t r p 结构示意图2 5 图p 2 分簇算法网络结构演示2 6 图4 - 3 簇树结构示意图2 8 图4 - 4t b b c 网络结构网关示意图3 2 图4 5t b b c 网络的分布式网关3 3 图4 - 6t b b c 算法结构示意图3 6 图4 7t b b c 节点状态转换图3 6 图4 8t b b c 簇生成算法和生成树算法功能演示3 7 图4 - 9 簇生成算法流程图4 0 图4 一1 0 网关选取流程图4 1 图4 1 1 请求加入核心树流程4 2 图4 1 2 处理加入核心树请求4 3 图4 - 1 3 簇维护算法流程图4 4 图4 1 4 簇内成员和簇移动示意图4 6 图4 1 5u p d a t e 报文处理流程4 7 图4 一1 6 生成树维护算法流程4 8 图4 1 7 簇内路由策略示意图4 9 图5 一lo p n e t 的建模机制5 3 图5 2t b b c 进程模型( 簇生成算法和簇维护算法部分) 5 4 图5 3t b b c 节点模型。5 5 图5 - 4 各分簇算法簇首数目仿真比较图5 6 图5 5 各分簇算法节点状态变化仿真比较图5 8 图5 - 6 各分簇算法l b f 仿真比较图5 9 图目录 图5 7t b b c 进程模型( 生成树及其维护算法部分) 。6 l 图5 8t b b c 与k t r p 时延仿真比较6 2 图5 - 9t b b c 与k t r p 路由开销仿真比较6 3 图5 1 0t b b c 与k t r p 吞吐量仿真比较6 4 缩略语 缩略语 a b c a a c c e s sb a s e dc l u s t e r i n ga l g o r i t h m a m r i s a o d v a d - h o cm u l t i e a s tr o u t i n gp r o t o c o lu t i l i z i n g i n c r e a s i n gi dn u m b e r a d - h o eo n - d c m a n dd i s t a n c ev c c t o r a o w s e l f - a d a p t i v eo n - d e m a n dw e i g h t e d 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 d - h o cr _ o u t i n g c h d c a d m a c d s d v d s r d v h i g h d i c i k t r p l b f l o w i d l s c l u s t e rh e a d d i s t r i b u t e dc l u s t e r i n ga l g o r i t h m d i s t r i b u t e dm o b i l i t y - a d a p t i v ec l u s t e r i n g a l g o r i t h m d e s t i n a t i o n - s e q u e n c e dd i s t a n c e - v e c t o r d y n a m i cs o u r c er o u t i n g d i s t a n c cv e c t o r h i g h e s td e g r e e 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 k e r n e lt r e er o u t i n gp r o t o c o l l o a db a l a n c ef a c t o r l o w e s ti d e n t i f i c a t i o n l i n ks t a t e 、，m 基于信道接入的被动分簇算 法 利用递增序号的自组网路由 协议 按需的自组网距离矢量路由 协议 自适应按需启发式算法 核心提取的分布式自组网路 由协议 簇首 分布式分簇算法 分布式移动自适应分簇算法 目的节点排序的距离矢量路 由协议 动态源路由 距离矢量 最大节点度启发式算法 接口控制信息 核心树路由协议 负载平衡因子 最小d 启发式算法 链路状态 缩略语 f a n e t m a o d v m o b i c r w r 甲 s r l t b b c t o r a 拜爿 w r w i 诤 岍 z r p m o b i l ea d - h o en e t w o r k m u l t i c a s ta d - h o co n d e m a n dd i s t a n c e v e c t o rr o u t i n gp r o t o c o l m o b i l i t ym e t r i c r a n d o m km o d e l r a n d o mw a yp o i n tm o d e l s u p e m o d e - b a s e dr e v e r s el a b e l i n g t r e eb a c k b o n e - b a s e dc l u s t e r i n g t e m p o r a l l yo r d e r e dr o u t i n gp r o t o c o l w e i g h t e dm e a s u r e w i r e l e s sr o u t e r w i r e l e s sr o m i n gp r o t o c o l w i r e l e $ sh 0 s t z o n er o u t i n gp r o t o c o l i x 移动自组织网 多播a o d v 协议 最低移动性分簇算法 随机行走模型 随机路点模型 基于超节点的逆向标记路由 协议 基于树形骨干网的分簇算法 临时排序路由算法 节点权重启发式算法 无线路由器 无线路由协议 无线主机 区域路由协议 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：翌查日期：2 。p 7 年6 月jj 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：罗当7 导师签名：苞队阑 日期：捌年6 月j 1 日 第一章引言 第一章引言 在2 1 世纪，全世界已经进入了飞速发展的信息时代，通信成为了信息产业中 发展最为迅速，影响范围最为广泛的行业。近年来，无线移动通信技术得到了飞 速发展和普及。蜂窝移动通信系统、无线局域网( i e e e 8 0 2 1 1 和h i p e r l a n ) 、蓝 牙技术( b l u e t o o t h ) 。家庭无线网( h o m e r f ) 等移动通信新技术也纷纷涌现。这些 技术的出现，极大方便了人们的生活，同时也推动了无线通信技术的发展。 1 1 研究背景 无线通信网络按照其组网控制方式一般分为两类：集中式控制的，即有中心 的。这一类无线网络的运行要依赖预先部署的网络基础设施。典型的例子有：蜂 窝移动通信系统，其依靠基站和移动交换等基础设施的支持；基于接入点( a c c e s s p o i n t ) 和有线骨干网模式工作的无线局域网。但对于某些特殊场合，不可能有这 种预先部署的固定设施可以利用。比如，战场上部队快速展开和推进、发生地震 或水灾后的营救、野外科学考查、偏远山区、临时会议等。在这种情况下，就需 要一种能够临时快速自动组网的移动通信技术。这也形成了另一类无线通信网技 术，即a d h o e 网络通信技术。 1 1 1a dh o e 的特点及应用 “a dh o e ”一词来源于拉丁语，意思是“专用的、特定的”。a dh o c 网络通 常也可以称为“无固定设施网”或“自组织网”。a d h o e 网络是一种特殊的无线移 动通信网络。a dh o e 网络中所有节点的地位平等，无需设置任何中心控制节点， 具有很强的抗毁性。网络中的节点不仅具有普通移动终端所需的功能，而且具有 报文转发能力。当通信的源节点和目的节点不在直接通信范围之内时，它们可以 通告中间节点转发报文通信。有时节点之间的通信可能要经过多个中间节点的转 发，即报文要经过多跳( h o p ) 才能到达目的地，这是a dh o c 网络与其他移动通 信网络的最根本区别。a dh o e 网络的节点通过分层的网络协议和分布式算法相互 协调，实现网络的自动组织和运行。因此它又被成为多跳无线网( m u l t i - h o p w i r e l e s s n e t w o r k ) 、自组织网络( s e l f - o r g a n i z e dn e t w o r k ) 或无固定设施的网络 电子科技大学硕士学位论文 ( i n f r a s t r u e t u r e l e s sn e t w o r k ) 。 与其他传统的通信网络相比，a d h o c 网络具有几个显著的特点： 无中心和自组织性 动态变化的网络拓扑 多跳路由 一移动终端的便携性和终端的局限性 一无线传输特性，安全性差 a dh o c 网络的许多优良性能为它在民用和军事通信领域占据一席之地提供了 有利的依据。首先，网络的自组织性提供了廉价并且快速部署的网络的可能。其 次，多跳和中间节点的转发特性可以在不降低网络覆盖范围的条件下减少每个终 端的发射功率，从而降低了天线和相关发射接收部件的设计难度和成本，从而为 移动终端的小型化、低功耗提供了可能，从共享无线信道的角度来看，a dh o c 网 络降低了信号冲突的几率，提高了信道利用率。从用户的角度上看，低功率的无 线电波产生的电磁辐射较少，对用户身体健康影响较小。另外，网络的鲁棒性和 抗毁性满足了某些特定应用的需求。总的来说，它的应用可以分为以下几类： 一军事应用 传感器网络 紧急、突发场合和临时场合 偏远野外地区 商业应用和个人通信 1 1 2a dh o c 的关键问题 由于a d h o e 网络的特殊性，传统固定网络和蜂窝无线移动通信网中使用的各 种协议和技术无法被直接使用，需要为a dh o c 网络设计专门的协议和技术。为此， 全球的研究人员在这方面开展了大量的研究，重点集中在以下几个方面： 一信道接入技术 一路由协议 一网络体系结构 一广播和多播 _ 传输层服务和安全问题 网络互连技术 2 第一章引言 无线移动自组织网络技术在过去的十多年里已经进行了大量的研究，i e t f 的 m a n e t ( m o b i l ea dh o en e t w o r k i n g ) 工作组目前正致力于无线移动自组织网络 路由算法的研究工作，提出了很多可应用在无线网络上，能够适应网络动态拓扑 变化的路由协议。同时，国内外许多大学和研究机构都在研究该领域。 1 2 课题简介 本文的研究内容基于国家8 6 3 课题“无线移动自组织互联网技术及实验系统 研制”的研究成果，作为对8 6 3 课题方案的继续研究和优化，作者实现了分簇网 络结构和课题中路由协议的结合，设计出了一种基于树形骨干网络的分簇算法。 目前a dh o e 网络的管理主要基于两种结构：平面结构和分层结构。在平面结 构中，网络管理简单，节点间的地位都是平等的，这种结构特点，节点数目少， 网络移动性弱，在此基础上实现的a d - h o e 网络的路由，效率较高。但是随着网络 规模的逐步扩大，节点个数不断增加，每个节点要想维护整个网络的拓扑信息或 选择合适的路由到远端节点将十分困难，那些适用于平面式结构的路由协议不再 适用，大规模的a d h o e 网络由此产生的分层管理，在此基础上进行a d h o e 网络 路由，现已成为无线网络研究的热点之一。 最为常用的分层结构是分簇结构，该结构将网络划分为不同的簇，每个簇由 一个簇头和多个簇成员组成。簇内成员的功能简单，只需维护与簇头通信，而簇 头节点需负责管理和维护本簇节点的簇内与簇间的通信。当簇首节点出现故障时， 可能会影响整个簇的通信，即簇首节点的稳定性和可靠性将在很大程度上决定着 整个系统的稳定性和可靠性，因此簇头的选取非常重要。而且出于a d h o e 网络系 统有限的资源的考虑，簇头和簇的统治域的重新计算的引起的系统消耗要远远的 大于节点的进入和离开簇所引起得系统计算消耗，所以合理的选择簇头，也就是 选择一个稳定性高的簇头，是a dh o e 网络分簇路由的关键问题。而簇与簇之间的 拓扑结构，将会直接影响簇问路由的性能。因为簇间采用不同的拓扑结构，网络 将会使用不同的路由生成和维护方案，这样会产生不同的路由开销和传输时延。 所以，簇间骨干网采用一种高效的拓扑结构是分簇算法的另一个关键问题。 作者针对目前己有的一些分簇算法的缺点，结合它们的优点，提出了一种新 的分簇算法，并且实现簇问的树形骨干网络。这样在实现高效分簇的基础上利用 了先前提出的核心树拓扑结构组织簇间结构，为大规模a d h o e 网络的路由协议设 计提出了一种有效的解决方案。 电子科技大学硕士学位论文 1 3 论文内容简介 在介绍a dh o c 当前发展现状和课题背景后，本文在第二章详细介绍了a dh o e 网络结构和分簇算法的概念，并列举说明了几种典型的分簇算法：最大连通度算 法、最小m 算法和权值算法等，分析了它们的性能和优缺点。 第三章在介绍了a d h o c 路由协议设计的相关概念后，引出一种新的路由算法 核心树路由协议，分析了其算法原理和详细算法步骤，为后面基于树形骨干 网的分簇算法设计奠定基础。 第四章提出了一种新的分簇算法一一基于树形骨干网的分簇算法，着重分析 了其中的关键问题，并且对算法的各部分进行详细说明，最后讨论了紫红的路由 策略。 第五章首先通过仿真对将新的分簇算法和几种典型的分簇算法的性能参数进 行分析，得出新的分簇算法的优势，然后通过仿真研究分簇算法给原来核心树路 由协议带来的性能改善。 第六章对全文进行了总结，并指出了进一步的研究工作。 4 第二章a dh o e 分簇算法概述 第二章a dh o e 分簇算法概述 在a d h o e 中，网络结构直接影响了网络的各种性能指标，现今网络的规模化 使分级结构成为了发展趋势簇结构是当前应用最为广泛的层次结构，最大的特 点是可以提高信道共享率和网络的可扩展性。本章阐述了a dh o e 网络的体系结构 和存在的问题，介绍了与分簇算法相关的些定义和分簇算法的目标，最后分析 了几种常用的分簇算法。 2 1a dh o c 网络结构 a d h o e 网络的拓扑结构分为两种；对等式平面结构( 如图2 - 1 所示) 和分级结构 ( 如图2 - 2 所示) 【。 对等式平面结构采用了完全分布式的控制方式，在这种结构中，所有节点的 功能和地位平等，既是终端又可以做路由器，它们仅仅在性能上有所不同。 图2 - 1 平面结构的a dh o e 网络 这种平面结构最大的优点在于源节点与目的节点之间可以存在多条路径，因 为可以通过多条路径传输业务流，减少拥塞，并且消除可能的瓶颈问题。但是平 面结构最大的缺点在于网络的规模受限，可扩充性差，因为每个节点都要知道到 达其他所有节点的路由信息。当网络规模加大时，维护这些动态变化的路由信息 就需要大量的控制消息，路由维护的开销指数增长而消耗掉有限的带宽。在用户 较多，特别是在移动的情况下，平面结构的a dh o e 网络存在处理能力弱，控制开 销大，路由经常出现中断等缺点，并且随着共享相同网络资源的用户数量的不断 增加，每个用户获得的吞吐量将急剧下降 2 1 。因此，它主要适用于移动性较弱的中 电子科技大学硕士学位论文 小型网络。 分级结构中采用了分层分布式的控制方式，在这种结构中，网络被划分成簇， 每个簇由一个簇首和多个簇成员组成，这些簇首形成了高一级的网络，在高一级 的网络中，又可以分为簇，再次形成更高一级的网络，直至最高级。在分级结构 中，簇首和簇成员的身份可以动态变化，节点可以实现自动组网。簇首类似于集 中式控制的中心控制节点，负责簇间数据的转发、协调和管理，使簇内各节点合 理工作，簇首可以预先指定，也可以由节点使用分簇算法自动选举。但是由于其 特殊地位，簇首可能成为簇内的瓶颈。 ：簇一簇首 网关 簇成员 ( a ) 革信道分级结构 ( b ) 双信道分级结构 图2 - 2 分级结构的a dh o c 网络 分级结构根据硬件的配置不同，又可以分为单信道分级和多信道分级两种。 单信道分级网络( 如图2 2 a 所示) 中只有一个通信频率，所有节点使用同一个频 率通信，为了实现簇首之间的通信，需要网关节点的支持，网关节点同时属于两 6 第二章a dh o e 分簇算法概述 个簇。簇首和网关形成高一级网络，称为虚拟骨干网p 】。而在多信道分级网络( 如 图2 2 b 所示) 中，不同级采用不同的通信频率，低级节点的通信范围较小，而高 级节点要覆盖较大的通信范围。高级节点同时处于多个级中，有多个频率，用不 同的频率实现不同级的通信。 在分级结构的网络中，簇成员的功能比较简单，不需要维护复杂的路由信息， 大大减少网络中路由控制消息的数量，因此具有很好的扩充性；由于簇首节点可 以动态选举产生，因此分级结构也具有很强的抗毁性。其缺点是维护分级结构需 要节点执行复杂的分簇算法，簇首节点也可能成为网络瓶颈，而且簇间业务流通 过簇首寻路，不一定选择了最佳路由。当然，可以通过设计合理的分簇算法来减 少维护簇结构所需的开销，并且可以通过分布式的网关来优化路由，避免簇首成 为瓶颈，簇首可以控制节点的加入和带宽分配。值得一提的是，在分簇结构中， 可以采用先验式和反应式路由相结合的方式来提高路由算法的性能。 综合各种因素，分级结构网络比平面结构更有优势。首先，分级结构有较好 的扩展性，网络规模在很大程度上不受限制，而且由于分簇，路由和控制开销相 对小一些。其次，分级结构通过路由信息的局部化提高了系统的吞吐量。再其次， 分级结构中节点的定位要比平面结构简单得多，因为分级结构中簇首掌握了簇内 成员的位置，路由查询只要在簇首之间进行，而不必象平面结构那样要全网查询。 此外，分级结构容易实现移动性管理和网络的局部同步，可以通过移动性管理来 实现序列寻址，由簇首充当位置管理服务器，简单实现节点定位和寻址。因此， 分级结构和分层分布式的控制方式逐渐成为a dh o c 发展的趋势【2 】 因此，当网络规模较小时，可以采用简单的平面式结构；而当网络的规模增 大并需要提供一定的服务质量保障时，应采用分级网络结构。 2 2a d1 4 0 0 网络分簇的相关概念 2 2 1 分簇算法的重要性 分簇是实现分级结构的一种主要手段。分簇是指在特定范围内的无线节点， 通过共享相同的无线介质组成各级子网的过程。而分簇算法根据一定规则选举簇 首，位于簇首的有效传输范围内的节点组成簇，不同簇之间存在无线链路相连的 节点作为网关节点。簇首负责在簇内维护所有簇成员信息和链路状况信息，与相 邻簇交换簇的信息，并根据这些信息计算路由；网关负责簇之间信息和数据的传 7 电子科技大学硕士学位论文 输。 前面提到，分级结构最大的缺点就是，分簇算法需要消耗节点的能源，生成 和维护分簇信息需要占用网络资源，并且跨簇节点之间不一定是最佳路由。合理 和高效的分簇算法是解决这些问题的关键。高效的分簇算法可以减少生成和维护 簇结构所需的开销；合理的分簇算法可以通过分布式网关来优化路由，分布式网 关可以是簇首，也可以是关键的簇成员，通过分布式网关和簇首形成虚拟的骨干 网络【4 j 【卯，在此基础上进行的路由，要比所有节点一起参与a dh o e 路由大大的节 省路由开销；适当的簇首选举能使移动性管理和网络的局部同步变得更加容易， 因为每个簇内簇首可以控制节点的接入请求并且合理地分配带宽，控制网内的资 源信息、簇成员的网络条件和整个簇的信息安全，甚至通过骨干网络还可以控制 整个网络的信息安全。此外合理的分簇结构还可以使结合先验式和反应式优点的 分级路由协议的性能获得最大限度的提高。 因此，高效和合理的分簇算法可以在很大程度上提高a dh o c 网络的性能和实 用性。 2 2 2 分簇算法的相关定义 本小节介绍一些关于分簇算法的定义，这些定义会在以后的章节遇到。 簇首：通过分簇算法产生的负责整个簇的节点。 网关：用于方便簇之间路由的节点，往往是两个簇在物理上相交的节点。 簇成员：簇首产生后，参与选举该簇首的节点都可以成为这个簇的成员。 结合图论中的相关知识，给出网络拓扑中的相关定义： 定义1 ：a dh o c 的网络拓扑的图论几何可以用无向图g = ( v ，e ) 表示，v 表 示节点的集合，e 表示边的集合。节点x 和y 之间存在边( x ，y ) ，意味着x 和y 是 可以互相通信的邻居节点。 定义2 ：一个簇c ，c v 由一组节点构成，并且对于任何两个节点x ，y c ， 满足d ( x ，y ) 站，h 是一可变的系统参数，同时满足v = u c , 。并且如果c ，n c ，= a ， c 。c ，那么称簇c 。和簇c ，为非交叠簇，反之两者构成交叠簇。 定义3 ：两点之间的距离d ( x ，y ) 是指节点x ，y 之间的最小跳数。 定义4 ：网络的统治集是指由网络中所有的簇首组成的集合，统治集的基数即 为簇头数。如果该集合中任何两个簇首都不是邻居节点，则构成统治无关集。 定义5 ：一个节点的l 跳邻居节点的数目称为该节点的度数。 8 第二章a dh o e 分簇算法概述 定义6 ：对于具有簇首的簇而言，如果簇内的任何节点到簇首的距离为k 跳， 那么称该簇为k 跳有头簇。对于无簇首的促而言，如果簇内任何节点对都可以通 过k 跳互相可达，那么称其为k 跳无头簇。 2 2 3 分簇算法的性能指标 目前，衡量一个分簇算法的优劣主要有以下几个标准：簇结构的稳定性。簇 首节点的数量、负载均衡度以及节电能力等阍。 1 ) 簇结构稳定：由于a dh o e 网络节点的动态特性，簇结构经常会因为节点 的加入、离开和移动、不同簇首相遇时的竞争而发生变化。一个相对稳定的簇界 结构能够有效地降低由于一个相对稳定的簇结构能够有效地降低由于簇的重构而 带来的通信与电能开销，因而维持簇结构的稳定具有重要的意义。 在簇结构中，节点有簇首、簇成员与未决( u n d e c i d e d ) 三种不同状态。而簇结 构的稳定性可用节点状态、变化频率以及簇首节点变化频率度量，分别定义为单位 时间内节点状态变化次数、簇首节点变化次数。变化次数越小，则簇的稳定性就越 高。 2 ) 簇首节点数目适当：在链路容量许可的情况下，适当的簇首节点数目能有 效地提高链路的利用率。但是，由于节点资源限制，簇首不可能服务所有邻居节 点，即簇成员的数量应有一定的限制，否则，簇首节点数目过少会导致单个簇内 的节点数目过多，每个簇内节点的吞吐量下降。如蓝牙协议，其主从结构限制了 每个主节点只能同时服务七个成员节点。 3 ) 负载均衡度好：簇首的负载大小取决于其所支持的节点的多少。维护簇结 构与簇问路由均需要消耗簇首一定的资源，因此不希望出现有的簇首过载、有的 簇首却很轻闲的状况。但是，由于节点经常性地加入、离开和移动，很难使系统 一直维持在良好的负载均衡状态。为了量化簇首负载的均衡程度，文献m 提出了负 载均衡度的概念： l b f ：上( 2 - 1 ) f 5 z ( k j - 一u y 其中，k 为簇首节点的成员节点数，u 为簇首的平均邻居节点数量， u = ( n - n 。) ，n 。，n 为网络中的节点数，n 。为簇首节点的数量。该值越大，则表示负 载均衡度越好。 9 电子科技大学硕士学位论文 4 ) 能量的分布均匀：使网络中节点能量消耗能够趋于均匀、一致的分布，不 会出现某些节点过早的消亡，从而提高网络整体的寿命。 2 3 几种典型分簇算法的介绍 现有分簇算法在分簇过程中大多显式地使用控制信息，即各节点通过周期性 地交换控制信息来选择簇首，但也有些算法隐含地使用控制信息，即在正常的数据 包中嵌入适当的控制信息。按照控制信息的使用方式，可将分簇算法分为主动分 簇算法和被动分簇算法两类。主动分簇算法的特征是需要周期性地交换控毒4 信息 来选择簇首。按照选择簇首的标准，主动分簇算法又分为最小i d 启发式算法、最 大连接度启发式算法、权重启发式算法等。被动分簇的特征是在簇的生成与维护 过程中均不使用专门的邻接信息，而是利用从正常数据包( 例如m a c 帧) 中获取 的邻接信息，或者在数据包中嵌入适当的分簇状态信息，并且采用了“先声明先 赢”的规则，即第一个发出数据包的节点成为簇首，并统治邻接区域的其它节点。 被动分簇最大的有点是不需要显示使用控制信息，节省带宽资源，分簇过程可以 在没有收集到完整的邻居信息的情况下进行，因此在连接改变时不需要一个重构 过程以满足某些分簇规则( 如最小m 或者最大连接度) ，这些优点决定了其巨大 的发展前景嗍【9 】【1 0 1 。被动分簇的概念在文献【1 1 】中有具体说明。下面介绍几种典型的 分簇算法及其优缺点。 2 3 1 最小i d 启发式算法( l o w i d ) 1 ) 算法描述； 最小i d 启发式算法是由g r c l a 和t s a i 提出的一种简单的分簇算法【1 2 1 。每个节 点分配唯一的i d ，相邻节点中具有最小i d 的节点作为簇头，并且在某些特殊情况 下，簇头可以将其职责交付给其簇内具有最小i d 的成员节点。算法工作过程描述 如下：初始时，每个节点周期性地向其l 跳邻居节点广播其d ，每个节点在获取 自己的1 跳节点信息后将自己的d 与其直接邻居进行比较，如果发现自己为m 值最小的节点，则自动成为簇首节点，并向其1 跳邻居广播簇首信息，则收到该 信息的节点都成为簇成员，如果一个节点的l 跳邻居都为簇成员，那么该节点自 动成为簇首节点。如果一个节点处于两个或者多个簇首的发送范围内，则这个节 点成为网关节点。网关节点通常用于簇间的路由。 l o 第二章a dh o c 分簇算法概述 2 ) 算法的优劣性： 这个分簇算法计算量小，实现方便，算法收敛较快。最小算法的簇头更新 的频率较慢，维护簇所需花费的开销较小，并且由于簇和簇内节点的数目较为合 理，网络的吞吐量高于最大连通度启发式算法。 但是它也存在一些缺陷，如它将导致某些节点电池很快耗尽。由于该算法倾向 于选择具有较小d 的节点作为簇首因而所选择的簇首也相对固定，这将使得这些 簇首节点消耗更多的电池能量，因而在一定时间后它将无法继续工作。从而缩短 整个网络的生存时间，并且该算法没有考虑负载平衡等因素。 2 3 2 最大节点度启发式算法( g h d ) 1 ) 算法描述： 该算法由g e r l a 和p e r a k h 最早提出【1 3 1 ，也称基于连通度的分簇( c l u s t e r i n g ) 算法；其中节点的连通度由它与周围节点的距离来确定。每个节点在其发身范围 内向周围节点广播唯一序列号( m ) ，如果它与周围节点的距离小于发射范围( 与 一点的发射功率相对应) ，则它们是l 跳邻居节点。一个节点的1 跳邻居节点的个 数称为它的连通度；具有最大连通度的节点被选作簇首，其周围邻居节点作为该 簇内的一般节点，它们只能与簇首进行通信。 该算法借鉴了i n t c r n e t 中选择路由器的方法，其原理是尽量减少路由器的数目， 因此该算法的目标是产生尽可能少的簇数。节点之间通过交互控制消息知道其邻 居节点的数目，该节点和其相相邻节点中具有最大度的节点被选为簇首，当度数 相同时则选择i d 最小的节点作为簇首，簇首的i 跳邻居节点则成为该簇的普通成 员节点，反复进行以上过程直到所有节点都加入某个簇。 2 ) 算法的优劣性： 该算法的优点在于簇的数目较少，从而减少了网络的平均时延，但是由于簇 的数目较少，信道的空间重用率较低。该算法对簇内的节点数不加以限制，并且 簇内的资源通常用簇内节点按照轮询的方式共享，当簇内节点过多时，由于簇酋 节点的处理能力有限，必然导致数据包的丢失、时延增加以及吞吐量的急剧下降。 此外，当节点移动性较强时，簇首的更新频率急剧上升。这些都是最大连通度算 法固有的缺陷。 电子科技大学硕士学位论文 2 3 3 节点权重启发式算法( w a ) 1 ) 算法描述： b a s a g n i 等人最早提出了两种节点加权算法【1 4 1 ，即分