（计算机应用技术专业论文）ad+hoc网络按需加权分簇算法的改进研究.pdf

华南师范大学硕：l 二学位论文 t h ei m p r o v e m e n tr e s e a r c ho fa dh o co n d e m a n dw e i g h t i n g a b s tr a c t c l u s t e r i n ga l g o r it h m m a j o r ：t e c h n o l o g yo fc o m p u t e rh p p li c a t i o n n a m e ：l uy i n g s u p e r v is o r ：p r o f e s s o ro fx oj u n a dh o cn e t w o r ki ss e l f - o r g a n i z a t i o nn e t w o r kt h a t 谢t h o mi n f r a s t r u c t u r e t h e f l e x i b l ee q u i p p i n ga n ds t r o n gr e s i s t a n c et od e s t r u c t i o nc h a r a c t e r sp u s ha dh o ct h eh o t p o i n ti nw i r e l e s sc o m m u n i c a t i o nr e s e a r c h c l u s t e r i n gh a sb e e ni n t r o d u c e da st h e s o l u t i o n st ot h ed i f f i c u l t i e so ft h es c a l a b i l i t ya n dm a n a g e m e n to ft h ea dh o en e t w o r k w i t ht h eh i e r a r c h i c a ls t r u c t u r e ，t h ec l u s t e rh e a dt a k e sc h a r g eo ft h er o u t i n gn o to n l y b e t w e e nt h en o d e si nt h el o c a lc l u s t e rb u ta l s ob e t w e e nt h en o d e si nt h el o c a lc l u s t e r a n di nt h eo t h e rc l u s t e r s ，t h e r e f o r e ，h o wt os e l e c tt h em o s tr e a s o n a b l en o d e st ob e c l u s t e rh e a d si st h ep i v o t a lp r o b l e mi nc l u s t e r i n ga l g o r i t h m ，n l ep a p e ra n a l y z e sa n dc o m p a r e ss o m et y p i c a lc l u s t e r i n gs c h e m e si na dh o e n e t w o r k s ， a n dt h e np r o p o s e sa n i m p r o v e dw e i g h t e dc l u s t e r i n ga l g o r i t h mb y i n t r o d u c i n gp r e d i c t i o nm o d e l ，w h i c hi sc a l l e di w c a ( i m p r o v e dw e i g h t e dc l u s t e r i n g a l g o r i t h m ) i nt h ec l u s t e r i n ga l g o r i t h m ，t h e r ei st h r e et y p i c a lc h a r a c t e r s ：f i r s t l y , t h e c l u s t e r i n ga l g o r i t h ma d o p t st h ea v e r a g e l i n k e x p i r a t i o nt i m e ( a l e t ) m o b i l i t y p r e d i c t i o nm o d e lt os o l v et h ep r o b l e ma b o u ts e l e c t i n gv a l u e sa b o u tn o d e sm o b i l i t y s e c o n d l y , t h ea l g o r i t h mb r e a k st h er e s t r i c ti nm a n yt r a d i t i o n a lw e i g h t e dc l u s t e r i n g a l g o r i t h m st h a tf i xt h el a r g e s th o p sf r o mc l u s t e rm e m b e r st ot h e i rc l u s t e rh e a d ，b u t d y n a m i c l ya d j u s t s i tb a s e do nn u m b e r so fc l u s t e rm e m b e r s ，w h i c hm a k e ss a l et h e c l u s t e rh e a d sc a l lm a i n t a i ns t a b l ec l u s t e rs t r u c t u r e s t h i r d l y , t h ec l u s t e r i n ga l g o r i t h m w e i g h st h em o b i l i t y , t h ec a p a b i l i t yo fm a n a g e m e n ta n dt h ep o w e r , a n dt h e ns e l e c t st h e m o s ta p p r o p r i a t en o d e sa sc l u s t e rh e a d s b ye x t e n d i n gn e t w o r ks i m u l a t i o n2 ( n s 2 ) a n ds t r u c t u r i n gt h e n e t w o r k e n v i r o n m e n t , w ed e s i g na n di m p l e m e mi w c a f i n a l l yw ec o m p a r ei w c ac l u s t e r i n g a l g o r i t h ma n dw c ac l u s t e r i n ga l g o r i t h m c o m p a r e d 、7 l ，i t l lw c ac l u s t e r i n ga l g o r i t h m ， t h er e s u l t so fs i m u l a t i o ns h o wt h a ti w c ac l u s t e r i n ga l g o r i t h mh a v em o r es t a b l e c l u s t e r s a dh o c 嘲络按需加权分簇算法的改进研究 1 i l f l | | l i i l l i l i | l l | i | | 1 1 1 | l l i i i i | | i 删 y 17 6 817 4 k e yw o r d s ：a dh o cn e t w o r k ；w e i g h t e dc l u s t e r i n ga l g o r i t h m ；m o b i l i t y p r e d i c t i o n ：m u l t i h o p i i i 华南师范人学硕 ：学位论文 目录 中文摘要i a b s t r a c t i i 目录i v 第l 章绪论1 1 1a dh o e 网络概述1 1 2a dh o e 网络特性和技术挑战2 1 3论文的研究内容和组织结构4 1 3 1 论文的研究内容4 1 3 2 论文的组织结构4 第2 章 a dh o e 网络的分簇算法6 2 1a dh o c 网络的分簇概述6 2 1 1a dh o e 网络分簇的优势和开销7 2 1 2 分簇算法的相关定义和设计目标8 2 2典型的a dh o c 网络的分簇算法9 2 3 2 4 第3 章 3 1 3 2 3 3 3 4 第4 章 4 1 2 2 1 简单分簇算法9 2 2 2 基于节点移动性的分簇算法1 1 2 2 3 考虑多因素综合的分簇算法1 2 2 2 4 多跳分簇算法1 4 分簇算法的对比1 4 本章小结1 5 改进的加权分簇算法i w c a 1 6 w c a 分簇算法性能分析1 6 改进的i w c a 分簇算法1 6 3 2 1 移动预测模型1 7 3 2 2 多跳分簇结构1 9 3 2 3 网关节点选择1 9 3 2 4 算法前提假设1 9 3 2 5 算法执行过程2 0 i w c a 分簇算法性能分析2 5 本章小结2 6 i w c a 分簇算法仿真与实现2 7 网络仿真软件n s 2 2 7 4 1 1n s 2 的工作原理眵2 7 4 1 2n s 2 软件仿真过程2 9 4 2i w c a 算法的实现步骤2 9 4 3i w c a 算法的实现3 0 4 3 1i w c a 算法的工作层次3 0 4 3 2 分簇过程中节点需维护的信息3 0 v 华南师范人学硕t - 学位论文 a dh o c 网络按需加权分簇算法的改进研究 第1 章绪论 1 1a dh o c 网络概述 a dh o c 网络的前身是7 0 年代初期的分组无线网( p a c k e tr a d i o n e t w o r k ) ，它最初是为军事通信应用而设计的。但这种特殊的无线通信网 络直到2 0 世纪9 0 年代后期才逐渐被人们所了解和关注。成立于1 9 9 1 年的 i e e e 8 0 2 1 1 标准委员会采用了“a dh o c 网络 一词来描述这种自组织对等 式多跳移动通信网络，a dh o c 网络就此诞生。i e t f 将a dh o c 网络称为m a n e t ( 移动a dh o c 网络) u 。 a dh o c 网络是由一组带有无线收发装置的移动终端组成的一个多跳的 临时性自治系统。网络中的每个移动终端设备都具有路由和报文转发的功 能，可以通过无线连接构成任意的网络拓扑，这种网络不但可以独立工作， 而且也可以与现有的i n t e r n e t 网络或蜂窝无线网络连接通信。考虑到网络 带宽和功率等多方面的限制，a dh o c 网络一般不适于作中间承载网络，它 通常是以末端子网的形式接入固定网络设施。因此，它只允许网络内部节点 的信息传输，而不让其他信息穿越本网络，以减少与现有i n t e r n e t 网络的 路由开销。 a dh o c 网络中，每个移动终端设备都具有路由器和主机两种功能：作 为主机，终端需要运行面向用户的应用程序；作为路由器，终端需要运行相 应的路由协议。在a d 狗o c 网络中，节点间的路由通常由多跳( h o p ) 形式组 成。由于终端的无线传输范围的限制，两个无法直接通信的终端节点往往可 以通过多个中间节点的转发来实现通信。所以，它又称为多跳无线网或自组 织网络。因此，我们通常将它看作是一种特殊形式的移动计算机网络。 图卜1 典型的a dh o c 网络结构 华南师范人学硕上学位论文 如图1 1 所示为典型的a dh o c 网络。图中终端c 和终端g 是无法直接 通信的，但是可以通过路径c b d f g 进行通信。 为了适应这种独特的组网和工作方式，必须为a dh o c 网络单独设计相 应的协议。无论是信道接入协议、路由协议、传输协议等都要根据a dh o c 网络的需要和特点进行改进和调整。除此之外，a dh o c 网络的特殊性也引 出了如分簇、节能、功率控制等的相关问题，这些问题形成了a dh o c 网络 技术研究的原动力和研究方向。 目前，国际上在a dh o c 网络方面研究较为活跃的几个研究机构有： ( 1 ) m a n e t ( m o b i l ea dh o cn e t w o r k ) 。 i n t e r n e t 工程任务组i e t f ，i e t f 于1 9 9 7 年成立了专门的移动工作组 m a n e t ( m o b il ea dh o cn e t w o r k ) ，其主要任务是针对m a n e t 网络开发基于 i p 协议的路由机制并解决与网络层相关的技术问题。1 9 9 9 年1 月，r f c 2 5 0 1 详细给出了m a n e t 的应用场景、特征和性能要求。i e t f 在2 0 0 0 年下半年公 布了一系列的m a n e t 路由草案。 i e e e 通信分会在2 0 0 0 年底成立了专门的m a n e t 技术分委员会。 ( 2 ) 加州大学洛杉矶分校m a r i og e r l a 教授所领导的“无线自适应移 动性实验室 ( t h ew i r e l e s sa d a p t i v em o b i l i t yl a b ) 。研究方向包括a dh o c 网络路由协议、多播协议、多跳网络的服务质量( q o s ) ，m a c 协议、功率控 制、蓝牙网络等。 ( 3 ) 康奈尔大学z y g m u n tj h a s s 教授所领导的“无线网络实验室” ( w i r e l e s sn e t w o r k sl a b o r a t o r y ) 。研究方向包括a dh o c 网络重构、m a c 协议、路由协议、网络安全等。 ( 4 ) 伊利诺基大学u r b a n a c h a m p a i 分校n i t i nv a i d a y a 教授所领导的 a dh o c 网络研究小组。研究方向包括a dh o c 网络的定向m a c 协议、定向路 由协议、网络调度等。 其他比较活跃的机构还包括美国d a r p a 研究协会，美国朗讯通信公司和 贝尔实验室。我国的m a n e t 网络基础理论研究起步较晚，国内学者所发表的 相关研究成果较少，2 0 0 0 年后才开始有少量成果发表。 1 2a dh o e 网络特性和技术挑战 与传统的集中式无线网络相比，a dh o c 网络具有如下一些特性口1 ，这些 特性为a dh o c 网络的管理和实现带来新的挑战： ( 1 ) 无中心性和自组织 a dh o c 网络是一种无中心、无固定基础设施支持的无线网络，各个移 动节点的地位是平等的，自主成网，既作为主机，收发相应的流量，同时也 作为路由器，对路过的流量进行转发。无中心性和自组织性使得a dh o c 网 2 a df l o c 网络按需加收分簇算法的改进研究 络可以实现快速自动组网运行。网络中任意节点出现故障都不会直接影响整 个网络的通信，这和有中心的网络相比具有更强的抗毁性，但是由于整个网 络没有中心，也为网络的路由和管理带来了挑战。 ( 2 ) 多跳路由 a dh o e 网络中，由于每个节点发射功率的限制，节点间的通信范围是 有限的。节点要与其通信范围之外的节点进行通信，需要通过中间节点的多 跳转发实现。正是多跳路由，使得每个节点的发射功率可以比较低，从而达 到节省能耗，延长节点工作时间的目的。 由于节点既充当主机，又充当路由器。因此节点在路由的同时，还需要 考虑移动节点有限的电池电量，以及节点发射功率的差异而导致的非对称路 由等问题。这些特性也为a dh o e 网络的路由协议的设计提出了挑战。 ( 3 ) 动态拓扑 a dh o e 网络中，节点是以任意可能的速度和移动模式进行运动的，而 且可能随时开关机，都会导致网络的拓扑结构以不可预测的方式随时发生变 化。在网络拓扑图中，这些变化主要体现的是节点和链路的数量和分布的变 化。而对于传统的有线网络来说，网络拓扑结构比较稳定。所以，需要开发 专门的路由协议，来适应这种动态拓扑网络的需要。 ( 4 ) 带宽受限 a dh o e 网络采用无线传输技术作为底层通信手段，这就决定了其相对 于有线信道传输方式，具有较低的带宽。与具有稳定物理线路的有线传输方 式相比，无线信道的质量无法得到保证。由于多路访问、多径衰落、噪声和 信号干扰等多种因素，使得移动节点的实际带宽与理论上的最大带宽值存在 一定的差距，而且随时间动态的变化。 如何有效的利用有限的带宽来实现网络节点之间的通信，也成为a d h o e 网络设计中需要解决的一个问题。 ( 5 ) 移动终端的便携性与能量受限 a dh o e 网络中的节点大多具有轻便灵巧、移动性强等特点，如笔记本、 掌上电脑以及车载嵌入式等。这些便携式设备在为用户提供方便快捷的网络 服务的同时也存在着能量受限的问题，如何节省能量的开销，提高能量利用 率，也成为a dh o e 网络设计的一个挑战。 ( 6 ) 网络可扩展性差 由于a dh o e 网络无中心，自组织、动态性大等特点，使得它的可扩展 性较差。随着a dh o e 网络中的节点数目增加，对其进行管理和路由的复杂 性急剧增加，网络的性能也将出现明显下降。分簇策略是解决a dh o e 网络 可扩展性受限问题的方案之一，它将具有相同性质( 如地理位置相近、运动 行为相似等) 的节点聚为一个簇，分而治之，为网络的可扩展性提供了有力 3 华南师范大学硕t ：学位论文 保障。 ( 7 ) 安全问题 由于采用无线信道、有限的电源、分布式控制等原因，a dh o c 网络会 比有线网络更容易受到被动窃听、主动入侵、拒绝服务等安全威胁。另外， a dh o c 网络由于节点自身充当路由器，不存在命名服务器和目录服务器等 网络设施，也不存在网络边界的问题。这就使得它的安全问题变得更加复杂， 传统网络中的许多安全策略和机制不能适用于a dh o c 网络。因此，信道加 密、抗干扰、用户认证、密钥管理、访问控制和其他安全措施都需要重新考 虑。 由于a dh o c 网络的这些特性，使得它无论是在体系结构和网络组织形 式，还是在协议设计等方面都与现有的无线通信系统有着显著的区别。 1 3 论文的研究内容和组织结构 1 3 1 论文的研究内容 当前的a dh o c 网络多采用分级结构，分级结构的构建和维护依赖于网 络环境、应用需要和节点特性，常常采用分簇的方法来构造分级结构，而分 级结构的形成和维护依赖于某种分簇算法。现有的大多数分簇算法中，簇头 的选择往往只考虑单一方面的因素，目前比较好的簇头算法是按需加权分簇 算法w c a ，这种算法在选择簇头时综合考虑多种因素，并根据实际需要和运 作环境做出合理的调整，可以适应不同环境的需求。 本文是在加权分簇算法( w c a ) 基础上，引入节点的移动预测模型。将 节点的链路连接强度作为a dh o c 网络的分簇控制参量，提出了基于移动预 测的i w c a ( i m p r o v e dw e i g h t e dc l u s t e r i n ga l g o r i t h m ) 分簇算法，该算 法的创新点主要有三点：一是设计合理的加权公式选取簇头，算法使用基于 移动预测模型的平均链路保持连接时间作为节点移动性的衡量指标。二是控 制簇成员和簇的规模，允许簇内多跳，这样形成的簇头分布更加均匀合理。 三通过簇维护过程的优化，使得尽量多的节点留在原簇内，簇头担任的平均 时间较长，以提高分簇结构的稳定性。 最后通过对网络仿真工具n s 2 进行扩展，模拟实现i w c a 分簇算法，并 针对分簇算法的性能指标，分析比较了i w c a 分簇算法和w c a 分簇算法的优 缺点。 1 3 2 论文的组织结构 本论文的组织结构如下： 第一章：绪论。介绍了a dh o c 网络的概念、特点及关键技术，以及本 文的研究内容和组织结构。 4 a dh o c 网络按需加权分簇算法的改进研究 第二章：介绍了a dh o c 网络的分簇特点、体系结构、以及分簇的优势 和开销等分簇概况，并对比分析了多种a dh o e 网络分簇算法的机制和优缺 点。 第三章：主要分析w c a 分簇算法及其缺陷，并给出了改进方法，进而提 出了基于移动预测的分簇算法i w c a ，并给出算法的设计思想。 第四章实验仿真，介绍网络仿真器n s 2 ，通过扩展n s 2 ，设计实现i w c a ， 并将其与w c a 算法在簇结构的几个性能指标上进行分析比较，以统计图的形 式体现仿真的结果，说明了i w c a 分簇算法的优缺点。 第五章：总结和展望。总结论文所做工作，分析论文的不足之处并展望 本课题需要进一步研究的工作。 5 华南师范大学硕十学位论文 第2 章a dh o e 网络的分簇算法 2 1a dh o e 网络的分簇概述 由于节点的能力通常相同并可以移动，故不适合于采用集中式控制结 构，特别是在战场环境中，中心控制节点容易被发现而遭到摧毁。因此a dh o e 网络一般采用分布式控制结构。它一般有两种结构：平面结构和分级结构。 平面结构拓扑图，如图2 1 所示，这种网络结构比较简单，它的所有节点的 地位平等，所以又称对等式结构。这种结构原则上不存在瓶颈问题，网络的 健壮性好。此外平面结构中节点的覆盖范围较小，相对比较安全。这种结构 的不足之处是当节点数目较多时，特别是在节点大量移动的情况下，平面结 构网络具有处理能力较弱，控制开销增大，路由经常出现中断等缺点。因此， 平面结构只适用于中小规模的a dh o e 网络。 图2 1 平面结构 分级结构采用分簇的方法，把网络划分为若干个簇，每个簇由一个簇头 和多个簇成员节点组成，这些簇头形成的网络又可以分簇，再次形成高一级 的网络。在分级结构中，簇头节点可以预先指定，也可以由节点使用算法选 举产生。簇头节点负责簇结构的稳定和重组，进行簇间数据转发，实现跨簇 通信等；簇内节点的功能简单，只需要维护与簇头通信。因此簇头的选取非 常重要。 根据不同的硬件配置，分级结构的网络又可以分为单频率分级和多频率 分级两种h 1 。单频分级( 如图2 2 ) 即所有节点都使用一个频率通信。为了 实现簇头之间的通信，需要网关节点( 同时属于两个簇的节点) 的支持。簇 头和网关节点形成了高一级的网络，成为虚拟骨干。 6 a dh o c 网络按需加权分簇算法的改进研究 ij 簇 簇头簇成员网关 图2 - 2 单频分级结构 多频分级网络，即不同级采用不同的通信频率，低级节点的通信范围较 小，而高级节点的通信范围较大。高级节点同时处于多个级中，有多个频率， 用不同的频率实现不同级的通信。如图2 3 所示的两级网络中，簇头节点有 两个频率。频率1 用于簇头与簇成员的通信，而频率2 用于簇头之间的通信。 频率1 一频率2 ( 二) 簇_簇头 簇成员 图2 - 3 多频分级结构 2 1 1a dh o c 网络分簇的优势和开销 可以看出，在a dh o c 网络中引入分簇思想的优势主要包括t ( 1 ) 层次路由的实现与更好的扩展性。处于同一簇中的节点通常被作 为一个自治域，而能力强的节点将被选出来作为簇头，负责进行域间通信， 从而实现了层次路由，为a dh o c 网络的可扩展性提供了可靠保障。 ( 2 ) 更便利、高效的管理。整个网络通过分簇被划分为若干个有限的 区域，分而治之，为a dh o c 网络的管理提供了便利。 ( 3 ) 更强的健壮性与容错能力。由于各个区域之间的独立性，节点的 故障和路由的错误将被局限在一个很小的区域内，从而使得整个网络具有更 强的健壮性和容错能力。 ( 4 ) 更高的信道利用率。不相邻的簇节点之间由于无线电信号不会相 互影响，因此可以使用相同的通信频率，并可以同时进行信息的发送，这使 得网络具有更高的信道利用率。 华南师范大学硕卜学位论文 当然，分簇策略在为a dh o c 网络带来以上的一系列便利条件的同时， 也存在着一定的开销。 在a dh o e 网络中，分簇的开销主要包括以下一些： ( 1 ) 与分簇相关的控制消息的传输。由于移动节点进行分簇的算法是 分布式的，在簇的形成和簇维护过程中，各个节点之间需要通过发送控制消 息进行协同。这些控制消息的传送是需要一定的带宽开销的，此类开销与网 络的动态性相关，网络的动态性越大，控制信息的交换也将越频繁，相应的 开销也越大。 ( 2 ) 簇之间的相互影响。当某个簇出现故障或者崩溃的时候，可能会 影响到邻近的一些簇，导致这些簇中的节点需要重新分簇，而产生开销。此 类开销与分簇策略的设计相关，若在分簇策略的设计中考虑了如何避免簇之 间的相互影响，则可以减小甚至消除此类开销；否则，簇之间的相互影响会 因为网络的局部性故障而导致大范围甚至全局性重新分簇，使得分簇策略难 以在现实环境中部署使用。 ( 3 ) 分簇形成过程中的静态假定。分簇策略一般包括分簇形成和分簇 维护两个过程，在分簇形成过程中，初始化的节点通过交互控制消息而形成 了相应的簇，在分簇维护过程中，已经加入到各个簇中的节点利用控制消息 的交互，实时地对分簇进行维护。所谓分簇形成过程中的静态假定是指，目 前提出的大多数的分簇策略中，都会假定在分簇形成过程中的移动节点是静 止的，只有当分簇形成过程结束，进入分簇维护过程以后，各个节点才开始 移动。这个假定在实际的网络环境中，是不现实的，从而也将产生一定的开 销。 2 1 2 分簇算法的相关定义和设计目标n 1 定义l 系统拓扑g = ( v ，e ) 是由节点和链路构成的图。v 表示节点的 集合，e 表示边的集合。节点x 和y 之间存在边( x ，v ) ，意味着节点x 和 节点y 是可以互相通信的一跳邻居节点。 定义2 两节点问的距离d ( x ，y ) 是指节点x 和y 之间的最小跳数。 定义3 一个簇c fc v 由一组节点构成，并且对于任何两个节点x ，y e ，满足d ( x ，y ) 兰h ，h 是可变的系统参数，同时满足v = k 9 c ，。如果qn c ，= g ，i j ，那么称簇c j 和c ，为非交叠簇，反之两者构成交叠簇。 定义4 一个节点的一跳邻居节点的数目称为该节点的度数。理想的邻 居节点数是指从整个网络的负载平衡角度来考虑，一个簇头节点所能最佳承 载的邻居节点的个数。 定义5 对于具有簇头h 的簇c ：f 而言，如果簇内的任何节点x 到簇头h 8 a dh o c 网络按需加权分簇算法的改进研究 的距离最多为k 跳，那么，称该簇为k 跳，即m a x d ( x ，h ) ，x e ) 至k ，那么 称簇e 为k 跳有头簇。对于不选举簇头的簇c i 而言，如果簇内任何两个节 点x 和y 的距离不超过k 跳，即m a x d ( x ，h ) ，x c j ) 主k ，那么称c ，为k 跳无 头簇。 定义6 如果一个节点同时位于多个簇头的通信范围，则称其为网关节 点。 定义7 通过簇算法产生的负责整个簇的节点，称为簇头节点；簇产生 后，簇内除去簇头节点外的节点都是该簇的簇成员节点；一个节点发送广播 信息，能给予返回确认信息的节点就是它的邻居节点。 定义8 簇头的传播范围为簇统治域；簇成员节点组成的集合称为簇头 统治集，网络的统治集是由网络中所有的簇头组成的集合。 定义9 一个节点从一个簇移动到另一个簇，并使自己的簇头标识发生 变化，这时称该节点为簇间移动；节点广播信息，接收节点没有通过其它中 间节点而直接接收到，这两个节点之间的距离就是卜h o p ( 一跳) 。 在分簇结构中，节点的动态移动，频繁地加入或离开某个簇，都会影响 系统的稳定性。有时甚至会导致簇头的更新和网络的重组，频繁的簇头更新 会引入较大的计算和通信开销，并且严重影响其它网络协议的性能，如分组 调度、路由和资源管理等。所以分簇算法的目标就是构造一个能够覆盖整个 用户节点的、可以较好支持资源管理和路由协议的相互连接的簇的集合。好 的分簇机制应尽量保持网络拓扑稳定，减少重新分簇的频率，并且还应考虑 节点的能量级别、网络的负载平衡和对信道接入协议的支持等因素。 2 2 典型的a dh o c 网络的分簇算法 目前人们对a dh o c 网络中的分簇问题进行了深入的研究，并针对不同 的网络环境和实际应用场景，提出了相当多的分簇策略。这里介绍几种典型 的分簇算法，并对这些算法的性能进行分析和对比。 2 2 1 简单分簇算法 早期提出的分簇算法通常只考虑系统中单一方面的因素进行分簇，如节 点i d 、支持集、节点度数、能量效率等，我们把这类分簇算法称为简单分 簇算法。这类算法由于所需的信息较少，具有计算简单，分簇控制报文较少， 算法收敛较快等特点。但是由于考虑问题单一，算法过于简单，所生成的簇 结构不一定最优，算法的适用范围也很有限。 ( 1 ) 最小i d 分簇算法 g e r l a 等人提出的最小i d 分簇算法【5 ，6 】中，每个移动节点被分配唯一的 9 华南师范大学硕f ：学位论文 i d ，节点利用周期性的“h e l l o ”消息向其周围的邻居节点广播其i d 值，每 个节点比较其和周围一跳邻居节点的i d 值，具有最小i d 的节点成为簇头， 簇头的一跳邻居节点成为该簇头所在簇的成员节点。 该算法的优点是实现简单、收敛较快，簇维护开销较小；缺点是倾向于 选择i d 较小的节点作簇头，这将导致这些节点因为担任簇头职责而消耗更 多的电池能量，从而缩短了整个网络出现分割的时间。 之后l i n 等人提出的一种改进的最小i d 算法【7 1 ，该算法沿用了基于最 小i d 的簇生成机制，对簇维护阶段进行了改进，指出在新节点加入网络时， 以其与各簇之间的位置关系决定其簇从属关系，避免了具有更小d 的节点 加入网络所造成的簇结构维护；当簇中存在通信距离超过两跳的节点对时， 当前簇结构需要维护，算法将在任意节点间通信距离不超过两跳的约束下， 尽可能保留原簇中更多的节点，这样可以使簇结构更加稳定。 ( 2 ) 最高节点度算法【5 8 】 最高节点度算法也称为最大连接度算法。该算法原则上尽量减少路由节 点的数目，以此达到提高网络的控制能力和减少簇数目的目的。每个节点通 过交互控制消息来获知邻居节点数，然后将本节点的度数向邻居节点广播， 从而使每个节点都可获得邻居节点的邻居节点数。该节点和其一跳邻居节点 中具有最大节点度的节点被选为簇头。当节点度相同时，则选择d 最小的 节点作为簇头。簇头的一跳邻居节点成为该簇的成员节点。簇头以及该簇的 成员节点不再参与簇生成过程，重复以上过程，直到所有的节点都加入某个 簇。 该算法的优点在于网络中簇的数目较少，即源、目的节点对之间的平均 跳数较少，从而减少了分组投递时延。其缺点在于，较少的簇数目减少了信 道的空间重用率。该算法中簇内节点数目没有设定上限，而簇的资源通常由 簇内节点按照轮询的方式共享，因此当簇头节点数目过多时，每个节点的吞 吐量将急剧下降，使得系统的性能也随之降低。此外，节点移动性较强时， 簇会变得不稳定，簇头更新频率急剧上升，引入大量维护开销。 ( 3 ) 基于支持集的分簇【9 】 基于支持集的分簇算法中的节点首先利用某种分布式策略，从网络中选 取一个支持集。然后选择支持集中的节点为簇头节点，进行分簇，其它节点 以簇成员的身份就近加入各个分簇。最后支持集中的节点通过路由信息的交 互建立路由表。当某个节点有数据需要发送时，首先检查自己的状态，若是 簇头节点，则会查询路由表，将数据包直接发送。若不是簇头节点，则它将 数据发送给相应的簇头节点，利用簇头节点进行转发。由此，整个支持集形 成了一个骨干网，所有信息通过骨干网进行转发，减少了路由开销，提高了 网络效率和可扩展性，同时在某个支持集节点的基础上，还可以诱导出更高 1 0 a dh o c 网络按需加权分簇算法的改进研究 一级的支持集，从而实现更高一级的分簇和路由，进一步提高网络的效率的 可扩展性。 其代表算法包括：c d s ( c o n n e c t e dd o m i n a t i n gs e t ，连通支持集) 算 法，其基本思想是阳1 ：网络中的每个节点通过分布式策略构造一个连通支持 集，节点以连通支持集为中心进行分簇并且以该连通支持集为骨干网进行通 信。该算法根据网络拓扑的动态变化，采用一些策略实时地控制连通支持集 的规模，达到了控制路由开销的目的。 实验表明该算法对于节点数目较少，移动性较弱的网络有较好的效果。 随着节点数目的增多，移动性的增强，支持集的维护开销也将加大，算法性 能下降；同时维护支持集的连通性也是算法的瓶颈。 2 2 2基于节点移动性的分簇算法 节点移动性是导致簇结构发生变化的重要原因，在分簇算法中考虑节点 移动性是提高簇结构稳定性的一个重要手段。基于节点移动性的分簇算法是 通过将节点移动性作为分簇标准，以提高簇结构或者通信链路的稳定性为目 的的分簇算法。该类算法主要研究的问题是节点移动性的定义、获取和判定 方法；其优点是生成的簇结构较稳定，缺点是增大了分簇信息处理开销。下 面介绍两类典型的基于节点移动性的分簇算法： ( 1 ) 基于节点本地移动性的分簇算法 这类的代表算法是m o b i c 算法n ，基本思想是选取网络中运动相对稳定 的节点作为簇头进行分簇，每个移动节点都会计算自身与邻居节点速度的差 异，差异越小说明该节点的运动相对比较稳定，差异局部最小的节点被选为 簇头。其具体做法是网络中每一个节点利用所连续收到来自同一个源节点 “h e l l o 消息的信号强度差异来计算它与源节点之间的相对移动性。当节 点获得它与所有邻居节点问的相对移动性之后便计算自己的平均本地移动 性，并附加在“h e l l o 报文中广播给自己的邻居节点，作为分簇标准，之 后的簇生成和簇维护机制与最小标识算法类似。 模拟显示该算法提高了簇结构的稳定性，并且它使用无线信号强度来判 断两节点间通信链路的稳定性比基于相对速度和距离的方法能更真实地反 应周围环境对移动性的影响。该算法的不足之处有两点：一是信号强度差异 的计算依赖于信道建模的准确度，而准确描述应用场景的信道条件相当困 难，所以采用这种方法不太实际。二是只有在网络中的节点移动确实具有相 关性的情况下，该策略才能发挥较好的性能，若这种相关性不明显，则策略 的性能也会受到影响。 ( 2 ) 基于位置预测的算法 考虑到网络中节点移动性对分簇算法的影响，同时为了满足实时多媒体 华南师范人学硕j j 学位论文 应用对系统q o s 提出的需求，s i v a v a k e e s a r 等人提出了基于位置预测的 ( 陬，缸，丸) n 2 1 的分簇算法，在分簇算法中引入了对节点移动性加以预 测的机制。 在算法的初始化阶段中，系统将a dh o c 网络覆盖的地理区域划分成为 多个大小相等的静态虚簇，同一虚簇中的节点被分为一簇，每个虚簇的中心 位置对全网所有节点已知。在移动过程中，每个节点不断记录其所经过的虚 簇信息。由于算法中已经定好每个簇的地理范围，所以主要考虑簇首的选择 问题。 算法中采用如下的节点移动性位置预测计算方法：在虚簇k 中的每个节 点i 都根据自己的移动历史信息计算( p mt 岫d 吨) ：其中d ；。表示虚簇k 中节 点i 距虚簇中心的距离；t 让为一持续时间参数；p 。表示节点i 在距离虚簇 中心d ；。位置处停留时间持续t 。的概率。然后将其转化为一个数人作为分簇 的标准，这里人越大，表示节点i 在当前虚簇k 中的移动性越弱。 算法中描述了两种簇头选择的情况：一是当前虚簇中没有簇头或者簇头 突然失效时，虚簇中所有节点将其人值广播到整个虚簇中，然后由具有最大 人值的节点担任簇首，这种泛洪式广播的系统开销较大；二是当前簇头节点 在即将失效时将触发簇头的重新选择，通过在簇中广播簇头更换报文，所有 节点在收到该报文后将自己最新的人值作为响应返回给簇头节点，由簇头选 出a 值最大的节点作为新的簇头。 模拟结果显示，该算法通过选择移动性最弱的节点作为簇头，避免了移 动过程中簇头的频繁更替和簇覆盖区域的显著变化，具有更加稳定的簇结 构。但该算法同样需要定位系统的支持，系统初始化对虚簇的划分也增大了 算法开销。另外，节点移动性预测的准确性以及对该算法的影响也是需要进 一步研究的问题。 2 2 3 考虑多因素综合的分簇算法 以上算法中簇头的选择都只考虑了某个方面的因素，很难满足实际应用 多方面的需求，簇头的选择不够优化。为此，m a i n a kc h a t t e r j e e 等提出的加 权分簇算法w c a l l5 j ( w e i g h t e dc l u s t e r i n ga l g o r i t h m ) 综合考虑多种因素来 为每个节点分配一个权值，用来标识每个节点充当簇头的程度。该算法是一 种按需的分布式分簇算法，它引入了节点度、距离、节点速度以及电池能量 四个因素作为计算权值的系统参数，并对各种决定性参数变量赋以不同权 重，从而可以根据不同的环境适应需求，实现一种优化的选举簇头、划分网 络节点形成簇的策略。 w c a 算法尽量选取邻居节点数目多、移动速度小、电量大、邻居节点 1 2 a dh o c 嘲络按需加权分簇算法的改进研究 与该节点的距离和小的节点担当簇头，从而提高簇的稳定性，平衡整个网络 的负载。它具有以下特点：( 1 ) 簇头的选举不是周期性的，而是按需自适应 进行选举。( 2 ) 根据系统需要选择理想的节点度数选择合适簇头，从而通过 优化簇内的节点数来提高系统吞吐量和优化网络负载。( 3 ) 假设簇头消耗的 能量远大于普通节点，通过限制普通节点的传输范围来节省节点的能量。( 4 ) 为了降低维护开销，算法的更新过程不再是周期性执行的，而是按需更新的。 算法的具体实现过程如下： 第一步：计算每个节点1 ，的所有邻居节点数，即节点v 的度数，用d ，表 示。 第二步：计算节点度数与最优度数之差，用a ，表示。最佳簇成员数用 6 表示。 ，= i 或一万i ( 2 - 1 ) 第三步：对每个节点v ，计算其到所有一跳邻居节点的距离总和，用见 表示。 d v = d i s t ( v ，v ) ( 2 - 2 ) i v n ( ，) 第四步：计算每个节点1 ，从计时到当前时间丁的平均速度，它是用来度 量节点的移动性，用m y 表示。 誓 1 ， 一 必= 毒副一) 2 + ( z 一) 2 ( 2 3 ) 1t = l 在公式( 2 - 3 ) 中，( x t ，e ) ，( x t l ，z 1 ) 分别是节点在时间t 和时 间f - 1 的位置。 第五步：计算节点1 ，作簇头的累积时间只，只可以代表已经消耗的节 点的能量( 假设簇头消耗的能量远远大于普通节点) 。 第六步：计算节点1 ，的权值，用既表示。 = 彩l a ，+ 国2 乜+ 缈3 m ，+ 国4 ( 2 - 4 ) 在公式( 2 - 4 ) 中，q 、国：、( 0 3 和为对应不同参数的权重，满足 q + 哆+ 鸭+ 吼= 1 。 第七步：选择具有最小巩的节点成为簇头。所有已经选择簇头的节点 不再允许进入簇头选择过程。 第八步：重复以上过程，直到所有节点或者成为簇头或者成为簇成员节 点。 w c a 分簇算法选举簇头综合考虑了多方面因素，选举的簇头性能较优， 经过仿真试验证实，形成的簇较稳定，同时网络的负载也较平衡。 1 3 华南师范大学硕：l ：学位论文 综上所述，w e a 是一种性能较优的分簇算法，因此对大规模h dh o e 网 络分层管理的研究可以选择w c a 分簇算法作为切入点。 2 2 4多跳分簇算法 传统的分簇算法大多是单跳，即簇头到簇内成员节点的最大距离为一 跳。而多跳分簇算法将具有相同通信特性的节点限制在一个簇范围内，可以 生成簇半径达k 跳的簇，簇头数减少，簇结构更灵活，提高了无线通信信道 的利用率，降低了报文的传输时延。同时由于簇头和簇成员节点间的距离为 k 跳，多跳分簇算法的报文广播形成了区域的泛洪，增加了管理控制开销； 另外簇头与成员的多跳导致了不直接相连，需要进行簇内的路由信息维护。 总的来说，多跳分簇算法逻辑复杂，系统开销相对较大。 典型的多跳分簇算法有l i n 等提出的移动无线网络自适应分簇算法【7 j ， 自适应分簇方法是以簇为中心的。本算法首先通过最小i d 算法分簇，一个 簇内最多有两跳，簇的大小依赖于发射功率的大小。由于本文主要针对多媒 体等实时传输的应用，对q o s 有较高的要求，为此提出了可