（计算机应用技术专业论文）无线自组网簇结构与协作研究.pdf

大连理丁人学硕十学位论文 摘要 随着无线移动通信和移动终端技术的高速发展，无线自组网作为一种新型多跳自组 织网络逐渐成为研究的热点。无线自组网快速灵活的特性也给网络组网方式和运行维护 带来了新的挑战。在网络规模较大，网络中节点较多时，为了增强网络性能和便于网络 管理将网络划分为簇。稳定高效的分簇结构作为保障网络性能的有效组网方式是无线自 组网的重要研究课题。协作问题产生的原因是由于无线自组网需要邻居节点协作中继转 发数据包的通信方式与节点由于电量等因素限制而趋于不转发其它节点数据包的行为 之间的矛盾。由于无线自组网的民用推广，协作研究也备受关注。 首先分析了无线自组网的特点，网络结构以及与分簇相关的m a c 接入方式。结合 无线自组网的特点，引出分簇结构和协作的研究并对现有典型分簇算法和协作模型做了 介绍。 其次给出了一种基于簇首和储备簇首的双簇首的分簇算法。在簇首选举后，再选举 储备簇首。储备簇首作为簇首的接替节点，在簇首不再胜任时成为原簇的新一任簇首。 仿真结果显示，由于减少了节点移动对簇结构的影响，延长了簇生存时间，增强了簇的 稳定性。 随后在分簇的基础上，给出了一种以节点唯一标识权值比较实现优化网关支配集的 策略。优化后两相交簇问仅存在唯一网关，两相邻簇间存在唯一一对网关。仿真结果表 明，在保证网络连通的情况下，可以有效的减少重播包的比率和广播延时。 最后给出了基于离散型h o p f i e l d 神经网络的无线自组网簇内协作监督模型。以簇为 单位对骨干节点日j 的协作进行监管。该模型首先使用层次分析方法确定节点行为评估参 数的权重，然后根据权重将所有的神经元分成若干组，每组神经元对应一个评估指标， 其所包含的神经元的数量正比于所对应评价指标的权重，接着使用记忆代表节点行为分 类处理方案的h o p f i e l d 神经网络模型对节点行为进行监督。实例计算验证了簇内协作监 督模型的可行性。 关键词：无线自组网；分簇算法；网关优化；网络协作 大连理一i ：大学硕士学位论文 t h er e s e a r c ho nc l u s t e ra n dc o o p e r a t i o ni nw i r e l e s sa dh o cn e t w o r k a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n ti nw i r e l e s sm o b i l ec o m m u n i c a t i o n , w i r e l e s sa dh o c n e t w o r kb e i n gan e wm u l t i h o p sa n ds e l f - o r g a n i z e dn e t w o r ki sb e c o m i n gt h er e s e a r c hf o c u s a n dt h en e t w o r k sf l e x i b l ef e a t u r e sb r i n gt h en e wc h a l l e n g eo nn e t w o r l d n 2 i no r d e rt o p r o m o t et h en e t w o r kp e r f o r m a n c e n e t w o r ki sd i v i d e di n t oc l u s t e r s s t a b l ea n de 伍c i e n t c l u s t e r i n gs t r u c t u r ea sa l le f f i c i e n tn e t w o r k i n gm e t h o do fp r o m o t i n gn e t w o r kp e r f o r m a n c ei s a ni m p o r t a n tr e s e a r c hs u b j e c ti na dh o en e t w o r k i na d d i t i o n t h ea dh o cn e t w o r kn e e d st h e n e i g h b o rn o d e s c o o p e r a t i o nt of o r w a r dp a c k e t s ，b u ti ti sc o n t r a r yt ot h ep e r s o n a lb e n e f i t ，s u c h a sp o w e r a sc i v i l i a na p p l i c a t i o no f a dh o en e t w o r k ，t h ec o o p e r a t i o nr e s e a r c hi sc o n c e r n e d f i r s t t h ea dh o cn e t w o r k sf e a t u r e , n e t w o r kt o p o l o g ya n dm a ca c c e s sm o d ea r e i n t r o d u c e d t h e n , t h et y p i c a lc l u s t e r i n ga l g o r i t h mi nc l u s t e r i n gs t r u c t u r ea n dc o o p e r a t i o n m o d e li nc o o p e r a t i o nr e s e a r c ha r ei n t r o d u c e d s e c o n d ad u a l c l u s t e r - h e a dc l u s t e r i n ga l g o r i t h mi sp r e s e n t e d a t i e rt h ec l u s t e r - h e a di s f o r m e d t h er e s e r v e dc l u s t e r - h e a di ss e l e c t e d n 峙r e s e r v e dc l u s t e r h e a di ss u b s t i t u t eo f c l u s t e r - h e a d w t 璩nt h ec l u s t e r - h e a di sn o tf i ti i si o b t h er e s e r v e dc l u s t e r - h e a db e c o m et h e n e wc l u s t e r - h e a d s i m u l a t i o ns h o w st h ea l g o r i t h mr e d u c e st h em o b i l i t yi n f l u e n c e st oc l u s t e r s t r u c t u r ea n dp r o m o t e st h ec l u s t e rs t a b i l i t y t h e na r e ra n a l y z i n gt h ec l u s t e r i n g , am e t h o do fo p t i m i z i n gg a t e w a yd o m i n a t i n gs e tb y c o m p a r i n gt h ee x c l u s i v ei do fe a c hn o d ei sp r e s e n t e d t h eo p t i m i z a t i o nm e t h o dg a l le n s u r e o n l yo n eg a t e w a yb e t w e e nt w oi n t e r s e c t e dc l u s t e r sa n do n l yo n ep a i rg a t e w a y sb e t w e e nt w o a d j a c e n tc l u s t e r s s i m u l a t i o nr e s u l ts h o w s ，t h em e t h o dc a ns a v et h eb r o a d c a s tp a c k , t qa n d r e d u c eb r o a d c a s td e l a ye f f e c t i v e l yi nt h ee a s eo fg u a r a n t e e i n gt h en e t w o r kc o n n e c t i v i t y f i n a l l y ，ac o o p e r a t i o nm o n i t o r i n gm o d e lb a s i n go nd i s c r e t eh o p f i e l dn e u r a ln e t w o r k si s p r e s e n t e d 1 1 1 em o d e lw o r k si nc l u s t e ru n i ta n dm o n i t o r st h eb a c k b o n en o d e s t h ea n a l y t i c h i e r a r c h yp r o c e s si sp r e s e n t e dt oo b t a i nn o d ea c t i o ni n d e xw e i g h t a l ln e u r o n si nt h en e u r a i n e t w o r ka r ed i v i d e di n t og r o u p sa c c o r d i n gt oa c t i o ni n d e xw e i g h t t h en e u r o n sn u m b e r si n e a c hg r o u pi sp r o p o r t i o n a lt ot h ee v a l u a t i o ni n d e xw e i g h t t h e nt h ed i s c r e t eh o p f i e l dn e u r a l n e t w o r kw i t ht h em e m o r yo fa c t i o nc l a s sa n dr e l e v a n tt r e a t m e n tc a nm o n i t o rt h en o d e s c o o p e r a t i o n 1 1 1 ee x a m p l ec a l c u l a t i o ns h o w st h em o d e l sf e a s i b i l i t y k e yw o r d s ：w i r e l e s sa 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 ；g a t e w a yo p t i m i z a t i o n ； n e t w o r kc o o p e r a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特另c l d l ：l 以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：丝盆圣日期：趁盟：厶五 大连理t 大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 奉学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：丛登 导师签名： 弛z 年l 月l f t 大近理工人学硕十学仿论文 1 绪论 随着无线移动通信和移动终端技术的高速发展，无线自组网作为一种可以满足在某 些特殊工作环境下，比如所在的工作场地没有可利用的设备，或者由于某种因素的限制 ( 如费用、安全等) 不能使用已建立好的网络通信基础设施，用户之间又存在信息交流和 协作工作需求的新的组网方式出现。 无线自组网( w i r e l e s sa dh o cn e t w o r k ) 是一种无基础设施的移动网络。无线自组网 由一组带有无线通信收发装置的移动终端节点组成，是一个多跳的无中心网络，可以在 任何时刻、任何地点快速构建起一个移动通信网络，并且不需要现有信息基础网络设施 的支持，网络中的每个终端可以自由移动，地位相等。与其它具有固定设施的通信网络 相比，a dh o e 网络具有如下特征f 1 1 ：( 1 ) 网络的自组织性；( 2 ) 动态变化的网络拓扑结 构；( 3 ) 有限的无线传输带宽；( 4 ) 移动终端的局限性；( 5 ) 安全性差；( 6 ) 分布式的网 络；( 7 ) 网络可扩展性不强；( 8 ) 存在单向无线信道。 1 1 研究课题的提出 自组网的特性为网络实现技术提出了新的问题和挑战【2 j 。 首先，a dh o e 网络中的设备都在移动，网络拓扑高度变化。由于常规路由协议需 要花费较长时l 日j 才能达到算法收敛状态，而此时拓扑结构可能在达到收敛状态之前又发 生了变化，后果是在花费了很高的代价却得到陈旧的网络路由信息。所以在a dh o e 网 络中，路由算法应具有快速收敛性，减少路由查找的开销，并同时能够感知节点移动将 造成的链路状况变化，以进行动态路由维护，增强网络稳定性。 其次，由于a dh o e 网络使用无线传输技术作为底层通信手段，与有线信道相比， 带宽窄。为了节约有限的带宽，a dh o e 设计实现的原则是要尽量减少节点间交互的信 息量，减少控制信息带来的附加丌销。 再次，a dh o e 网络中没有了蜂窝通信系统中类似基站的节点，数据分组可能在任 何两个移动节点间直接传送，或者经过中间节点的转发。这给网络管理提出了新的要求， 不仅要对网络设备和用户进行管理，还要有相应的机制解决移动性管理、服务管理、节 点定位及地址配置等特殊问题。 最后，作为移动终端的a dh o e 网络节点一般采用电池供电，与普通网络设备使用 电源线供电有着显著差异。为了延长电池的使用时问，在网络协议的设计中，要考虑尽 量节约电池能量；同时要防止网络中的节点为了节省能量使用而不参与网络协作的行 为。 无线白组网簇结构与协作研究 1 2 国内外研究状况 9 0 年代以来，a dh o c 网络的研究在世界范围内已经从无线通信领域中的一个小分 支逐渐扩大到相对较独立的领域。目前，无论在国际上，还是在区域上( 欧洲和亚洲等 地区) ，周期性的a dh o c 网络学术会议日益增多。总结国内外研究现状，a dh o c 网络 成果主要在以下几个方面： ( 1 ) m a c 协议。m a c 协议主要解决如何在相互竞争的用户之间分配无线信道，即 无线节点如何接入无线信道来发射数据帧的问题。通常，可以将m a c 协议分为两大类 p j ：随机接入( 如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 l 标准委员会就选择一种随机接入方案( 即c s m a c a ) 协议作为其标准的m a c 协议的基础。但是在需要保证服务质量的场合，采用受控接入 的协议可能更加适合。例如，i e e e8 0 2 1 1 的p c f 能够比较好地支持对时延敏感的业务。 i e e e8 0 2 1 1 的m a c 协议本身是针对单跳的w l a n 设计的，并没有针对多跳网络进行 优化。当应用于多跳a dh o c 网络时，当前的i e e e8 0 2 11m a c 协议存在许多问题，因 此为a dh o c 网络改进甚至设计新的m a c 协议仍然是一个热点问题。 ( 2 ) 分簇。a dh o c 网络一般有两种结构：平面结构和分级结构 4 1 。在分级结构中， 网络被划分为簇，簇根据是否存在簇首分为无簇首的簇和有簇首的簇。在有簇首的簇中， 簇由簇首，网关和成员节点组成。簇内节点的身份动态变化，节点仍然自动组网。簇首 负责簇间数据的转发、协调和管理，使簇内各节点合理工作，簇首由分簇算法选举产生。 簇首与现有蜂窝移动系统中的基站的主要区别在于它一般没有专用的硬件，本身也是一 个移动节点，并且是动态选择的。大量研究结果表明【5 叫，分簇可以有效地使用多信道， 提高系统容量；减少控制信息的交换开销，增强对节点的控制管理；实现网络的局部同 步；为多媒体业务提供服务质量路由；支持拥有大规模节点的无线网络。目前，分簇算 法大致可以分为两种：主动分簇算法，如最小i d 分簇算法，加权分簇算法和被动分簇 算法。 ( 3 ) 路由。由于a d h o c 网络通常是一种多跳网络，开发良好的路由协议是建立a d h o c 网络的首要问题，也是主要的研究热点和难点。传统的用于有线网络的距离向量协 议( 如r i p ) 和链路状态路由协议( 如o s p f ) 并不适用于拓扑结构高度动态变化的a dh o c 网络。目前针对a dh o e 网络提出的路由协议可以分为表驱动( t a b l e d r i v e n ) 路由和按需路 g g ( d e m a n d b a s e d ) 两大类i lo j 。表驱动路由协议又称为先应式( p r o a c t i v e ) 路由协议，它的目 的是为网络中的每一个节点维护到所有其它节点的一致和最新的路由信息，因而要求每 大连理t 大学硕十学竹论文 个节点维护一个或多个路由表柬保存这些信息。当网络拓扑发生变化( 事件驱动) 时，相 关的节点在整个网络中发布更新信息，来确保路由信息的一致性。此外，即使网络拓扑 没有发生变，每个节点也需要周期性地( 时间驱动) 广播它的路由表。表驱动路由协议的 优点是它减少了节点获得路由的延迟，使源节点能够立即判断目的节点的可达性，缺点 是消费了较多的网络资源，此外它完全浪费了一些资源来建立和重建那些根本没有被使 用的路由。主要的表驱动路由协议有d s d v l l l l 0 按需路由协议又称为需求驱动( d e m a n d d r i v e n ) 或反应式( r e a c t i v e ) 路由协议。当采用这种路由协议时，源节点只有在需要建立一 条到达目的节点的路由时，才产生一个路由发现过程来建立相应的路由。建立了路由后， 源节点产生一个路由维护过程来维护该路由，直到到目的端的每一条路由都不可达或者 不再需要该路由时。按需路由的优点是不需要花费资源来维护无用的路由，但路由发现 过程的费用比较昂贵，而且源节点事先无法预测能否发现到目的节点的路由，此外发现 路由的延迟与表驱动路由协议中确定的查表时间相比，也是不可预测的。主要的按需路 由协议有d s r l l2 1 ，a o d v | 13 1 ，t o r a h 1 。在这些路由协议中，目前研究的最为深入的是 d s d v 、d s r 、a o d v 、t o r a 。它们在一些著名的网络仿真软件中都已经被完整的实现 【1 5 】，并且d s r 路由协议已经在配置有i e e e8 0 2 1 lw a v e l a n 无线网卡的膝上电脑中实 际实现。此外，许多研究人员还开发了一些多播路由协议i l ”。 ( 4 ) t c p 。传统上，t c p 是针对有线网络设计的，同时也是针对这种网络进行参数 调整和优化的。当应用于多跳无线a dh o e 网络时，t c p 连接存在严重的不稳定性和不 公平性问题【1 7 ，1 8 1 ，其主要原因一方面是i e e e8 0 2 1 lm a c 协议不适用于多跳a df l o c 网 络，另一方面t c p 的拥塞控制机制本身也不适用于这种网络。在有线网络中信道的比 特差错率很低，拥塞避免的基本假设成立。但是在多跳a dh o c 网络中，造成分组丢失 的主要原因有四神：无线信道的高误码率、节点的移动性、信道接入冲突和缓存溢出。 针对不同原因，t c p 应该采用不同的措施来保证连接的性能。但是，当的t c p 的拥塞 控制机制不能对这四种原因进行有效地区分，以便采取相应的解决措施，而是在出现分 组丢失时一律调用拥塞避免算法，因而使得多跳a dh o c 网络中t c p 的性能非常差。 ( 5 ) 服务质量q o s 。q o s 是指当源端向目的端发送分组流时，网络向用户保证提供 满足预先定义的服务性约束，如端到端的延迟、带宽、分组丢失率和延迟抖动等。为了 提供q o s 保证，首要的任务就是在源和目的节点间寻找具有必要资源来满足q o s 要求 的路由，其次对于特定的流，一旦路由被选择后，必须为该流预留必要的网络资源。网 络能够提供q o s 的能力取决于网络中的所有组成部分，包括传输链路、m a c 层、网络 层等。在a dh o c 网络中提供q o s 保证是一个非常复杂的问题，主要包括三个重要的组 成部分：q o sm a c 协议、q o s 路由和资源预留的信令1 19 。2 0 1 。q o sm a c 协议解决信道竞 无线白组网簇结构与协作研究 争的问题，支持可靠的单播通信和为实时业务提供资源预留，如g a m a p r 协议1 2 ”和 b b 竞争机制【2 2 1 。q o s 路由是指在给定的资源约束下，能够发现和维护满足q o s 要求的 路由l 强州，而q o s 信令为q o s 路由确定的路径提供实际的接纳控制、调度以及资源预 约服务 2 5 l 。这三个组成部分之问需要相互合作，以提供用户要求的q o s 服务。 ( 6 ) 能量节省问题。能量节省问题涉及到无线网络中的各个层。在每层上都有相应 的技术方案【2 6 1 。在硬件层次上，可以采用低功率的c p u 和显示器；在物理层，可以调 整节点的发射功率来减少网络的能量消费：在m a c 层，主要措施为减少数据发送的冲 突，避免重传，和使节点进入睡眠状态；在网络层，采用功率控制路由算法，而不是以 最短跳数和最小延迟作为路由度量；在操作系统层次上，可以采用低能量消费的c p u 调 度算法和磁盘管理算法。 ( 7 ) 安全性问题。a dh o e 网络的特点为网络设计带来了新的安全性挑战。信道和节 点的弱点、缺乏基础设施和动态改变的拓扑使得在a dh o c 网络中提供安全性保证成为 一个巨大的难题。具体地说，a dh o e 网络存在以下的安全性问题【2 ”： 无线链路比有线链路通常更加容易受到信息和物理攻击。这些攻击包括被动窃 听和主动假冒、信息重放和信息破坏。 节点在敌方环境( 如战场) 漫游时缺乏物理保护，容易落入攻击节点的控制中，也 容易受到已经泄密的内部节点的攻击。 a dh o e 网络的拓扑和成员经常改变，节点问的信任关系经常变化。a dh o c 网络 中不存在基础设旌，使节点不能获得值得信任的第三方的证书的帮助。如何在节点间建 立信任关系成为a dh o c 网络安全性研究的中心问题。 a dh o c 网络包含成百上千个节点，要求所采用的安全机制应该具有扩展性，以 便应用于这些大开! 网络。 安全性问题同样是一个跨层的问题。在m a c 层，i e e e8 0 2 1 1 标准提供了w e p 方 案，它支持数据加密和完整性。但是w e p 方案存在大量的设计缺陷和弱点，因此i e e e 8 0 2 1 l 工作组不得不专门成立8 0 2 。1 l i 工作组来设计新的安全方案。在网络层，为解决 恶意的节点修改路由信息、制造假信息或伪装成其它节点等安全性问题提出了大量的解 决方案【2 ”0 1 ，如s r p 、a r a n 、s e a d 等。 ( 8 ) 节点间协作。由于无线自组网终端节点的电量有限，每个节点较为其他节点提 供服务而更趋向于仅接受其它节点的服务，这种“自私”行为与a dh o e 网络需要节点 问协作的组网方式相悖。目前的解决方案大致可以分为三类：基于游戏理论【3 1 ，3 2 】，基于 虚拟货 3 3 , 3 4 】和基于信誉【3 5 l 的理论模型。这些模型都是通过一定的规则，刺激节点间的 协作来实现网络通信。 人连理r 大学硕十学位论文 1 3 本文的主要工作 本文的主要工作包括如下几个部分： ，记为( f ，力ge 。本文主要讨论2 跳成簇一个2 跳成簇及相关 的问题可以描述如下。 定义3 1 给定一个无向连通图g = ( e e ) ，顶点集瞒足下列条件多个子集k ，j k ， 称为簇： ( 1 ) 【j k = v ； 三l ( 2 ) 由k 生成的导出子图g 【巧】是连通的： ( 3 ) 每个簇存在簇首c q ； ( 4 ) 设簇酋c h , 形，且x v ( x c h , ) ，则x 与c h , 闻的距离c l ( x ，c h , ) r ，“和v 之间的通信依赖于其他节点进行转发。 簇是按照分簇算法形成的节点集合。分簇算法考虑分簇时的侧重点各有不同，当网 络中的簇不能满足分簇规则后，就需要簇的重构。在以簇首作为簇存在标志的簇结构中， 簇结构的变化可以概括为两类：簇首自身的原因导致簇不能满足分簇规则，侧如，簇酋 的电量不足，不能继续执行簇首职能；其他节点对簇首的影响，例如，新加入节点根据 分簇规则对簇首的影响，以及由于节点移动，不同簇首相遇时的竞争。簇的重构会导致 簇中路由信息的更新。频繁的簇重构将急剧增加网络的开销。从上面的分析来看，解决 大迮理f 人学硕十学傍论文 这一问题，可以从三个方面来考虑。首先要保证分簇算法选择的簇首有较好的稳定性： 其次分簇算法应尽量减少簇重构影响的节点范围；最后可以通过一种预应机制，对可能 发生的簇结构变化作出反应。基于此思想，给出了一种基于双簇首的分簇算法。 3 2 双簇首分簇算法 在双簇首分簇机制中，簇内同时存在两个簇首，主簇首( 简称簇首) 和储备簇首。主 簇首等同于常见分簇算法中的簇首，负责簇内通信的管理。储备簇首作为簇首的替补节 点，以一定的规则随时准备接替簇首。基于上述三个方面的考虑，在选举簇首时应保证 算法的快速收敛并且减少其它节点对簇首状态的影响；此外，当簇首不再胜任时，通过 储备簇首来接替充当新的簇首并且使簇首转换的影响局部化。 现有的分簇算法大致可以分为两类：基于值或权值的，如最小i d 算法，最大连通 度算法，权值算法等；和基于消息的分簇算法，如被动分簇算法。最小i d 算法的收敛 速度相对较快，但簇首间容易发生“链式效应”，如图3 1 所示，当簇首l 向簇首3 移 动时，根据最小i d 做簇首的原则，簇首3 成为普通节点并导致簇的重构，节点4 成为 新的簇首，但节点4 确影响了以节点5 为簇首的簇，依次影响了整个网络的拓扑结构。 图3 1 链式效应 f i g 3 1c h a i ne f f e c t 和最小i d 算法相比，被动分簇采用的f d w 规则同样具有较快的收敛速度，也避免 了“链式效应”。f d w 规则规定第一个没有收到簇首消息并成功发送数据的初始节点 成为簇首。此方法可以在没有完整邻居信息的条件下进行网络分簇。但f d w 规则对新 加入已成簇的网络的初始节点处理不够完善，容易造成簇的重构。例如当有新节点加入 无线自组网簇结构与协f f 研究 网络后，如果新节点成功发送数据，根据f d w 规则将成为新的簇首，这将导致现有簇 结构的重构，降低了簇结构的稳定性。 如果把无线自组网视为无向连通图，并假设网络终端的通信范围相同。那么从职能 上看，在簇内最接近簇首的节点是连通度除簇首外的节点中最大的节点，具有此属性的 节点在接替簇首时能使簇变化的影响局部化。但是，由于节点的移动和节点进入和退出 网络，无法通过连通度来实现簇内变化的局部化，因此需要寻找能够代表簇内较多节点 的簇标志节点来充当储备簇首。 在簇都形成后，簇首和储备簇首之间需要协调工作，判断两节点的转换时刻，并通 知其它节点改变相应的信息。 综上，整个分簇算法分为两部分：簇首选举算法和簇维持算法。 3 2 1 簇首选举算法 网络中的节点有六种状态可能：初始态( r n m a l ) 、准簇首( c h r e a d y ) 、簇首( c h ) 、 储备簇首( a c h ) 、网关( g w ) 、成员( m b ) 。准簇首状态为过渡状态。簇首选举算法描述 为： 初始，节点进入网络都处于初始态，节点在本地执行如下步骤； ( 1 ) 每个初始态节点进入网络后广播w h o i s c h 消息询问谁是簇首节点，若存在簇首 节点，则簇首节点以i a m c h 消息通知初始态节点更新状态，其他状念的节点不响应此 消息；在没有簇首节点回应时，初始态节点进入准簇首状态，准备做簇首： ( 2 ) 成功广播i a m c h 消息的准簇首节点成为簇首，其他节点在收到消息后更新状 态：存在于多个簇内的节点或能够和多个簇内节点通信的节点成为网关，其他节点成为 成员节点； 在存在簇首的簇结构中，簇首是否存在决定着簇是否存在。这里扩充簇的存在标志 节点，同时以簇内的簇首、网关节点和部分成员节点作为簇存在的标志。节点包含标志 节点数计算如式( 3 1 ) 所示。 虬融= 簇首+ a 网关数+ p 成员节点数( 3 1 ) 其中，n 和卢是节点的重要性权值，o t + p = 1 ，o p ，即网关节点的重要性要大于成员 节点，节点邻居中的网关数量越多，标志节点数值就越大。据此，储备簇首的选择描述 如下： ( 3 ) 簇首形成后，进入邻居信息收集过程。簇内，簇首的同簇邻居数最多，其中标 志节点也最多。选同簇邻居内标志节点数最大的能够证明簇生存的非簇首节点为储备簇 首，当有多个节点满足储备簇首条件时，取最小i d 者。满足条件的节点簇内广播i a m a c h 大近理i ：人学硕七学何论文 消息，通知簇内其他节点更新储备簇首的信息。当节点发现自己的同簇邻居中标志节点 数较储备簇首多时，则申请成为新的储备簇首，原储备簇首更新状态。储备簇首不满足 条件时，更新状态。 簇首形成后，网络拓扑基本建立，可以进行正常的通信。储备簇首的选取仅是邻居 节点间交换相关信息的副产品，基本不影响正常的通信。储备簇首是簇内标志节点数仅 次于簇首的节点，这基本保证了储备簇首可以覆盖簇内大部分节点，当需要簇首变换时， 需要重构的节点也是局部节点。 3 2 2 簇维持算法 由于节点的加入和离开，以及节点的移动等都会导致簇拓扑结构的变化。为了减少 簇重构造成的网络开销，引入储备簇首，作为簇首的替代节点。当簇首由于电量，移动 等因素不能继续胜任时，储备簇首可以立刻进入簇首状态，履行簇首责任。这样就减少 了簇首重选的开销，延长了簇结构的生存时间。原簇首无法继续胜任因素大致可以分为 两类：属性因素，如电量不足和行为因素，如相对于簇内节点的移动。对于前者簇首 可以主动通知储备簇首进行职位交接；在后者中，节点的移动是对簇结构影响最大的因 素，也是讨论的重点。通过g p s 可以对簇首节点行为进行预测【4 6 4 7 1 ，此技术能够判断 簇首节点相对于簇内节点是否移动到簇边界。考虑到无线自组网内节点有限的电量与组 网费用，这里给出一种基于簇首和储备簇首邻居节点中标志节点个数比较的方法，对簇 首移动性进行预测。 储备簇首在地理位置上近似趋于簇标志节点的中心，相对于储备簇首的移动芦视为 相对于簇的移动。簇首是否在偏离簇可以根据储备簇首来近似判断。当簇首邻居中的标 志节点数相对于储备簇首的标志节点数在减少时，视簇首在偏离簇。当簇首的邻居节点 中不存在储备簇首时( 区别于簇首选举阶段时类似状念) ，视簇首已离开原簇。簇首偏离 簇的趋势计算如式( 3 2 ) 所示。 占= 旦吐( 3 2 ) 其中，和? a e h 分别为簇首和储备簇首邻居节点中标志节点的个数。 当节点静止，簇首完全偏离初始形成的簇时，原簇内依然属于当| j i 簇的通信覆盖内 的区域面积，等于两个圆心都在对方圆周上的半径为，筋日交圆，相交区域的面积如式 ( 3 3 ) 所示。 。 ，： s = 2r 7 ( 2 巧一，) 出= 要胛2 一半，2 ( 3 3 ) 无线白组网簇结构与协作研究 s 与圆面积8 - = - z r r 2 的比值五z 2 5 6 ，所以艿( 1 ，五) ，认为当簇首偏离簇内2 3 的标 志节点时，即万 2 时，簇首就偏离了原簇。 簇维持算法描述如下： ( 1 ) 新节点加入进入初始态，执行簇首选举算法步骤( 1 ) ； ( 2 ) 如果节点的邻居中既没有簇首时，节点进入初始态，执行簇首选举算法( 1 ) ； ( 3 ) 当簇首不再存在时，储备簇首自动成为簇首；同时簇首也可以主动通知储备簇 酋接任成为新的簇首； ( 4 ) 当6 大于2 时，簇首通知储备簇首成为新簇首，原簇首更新状态； ( 5 ) 多个簇首相遇，较大6 值的簇首通知储备簇首成为新的簇首并更新状态；若6 值 相等，则保留最小i d 的簇首； ( 6 ) 在( 3 ) 、( 4 ) 、( 5 ) 中若没有储备簇首时，需要簇重构，簇内其他节点自动成为初始 态节点，重新执行簇首选举算法； ( 7 ) 簇首的变更，簇内节点需要更新自己的邻居信息。 3 3 算法性能分析 在簇首选举过程中，根据改进的f d w 规则，初始念节点首先判断自中是否存在簇 首，代价为o ( 1 ) ；若无簇首，第一个成功发送数据包的初始节点成为簇首，代价仍为o ( 1 ) ； 储备簇首的选举需要收集邻居信息，代价为d ( ) ，a 为簇内平均邻居节点数。簇维持 算法在最差情况时是重新执行簇首选举算法，代价为d ( ) ；当储备簇首接替簇首时， 相应节点需要改变当前簇首的信息，代价为d ( 1 ) ；同时需要重新选择储备簇首，由于节 点已经收集了邻居信息，代价为o ( 1 ) 。所以分簇算法的总代价为o ( ) 。 算法的优点可以概括为： ( 1 ) 簇首选举算法的收敛时间较短； ( 2 ) 在簇首形成时，不需要收集邻居节点的信息，也就不需要在算法执行过程中节 点静止的假设： ( 3 ) 储备簇首选举不影响正常网络通信； ( 4 ) 当簇首不再胜任时，由储备簇首接任，而不需要重构簇。 缺点不足： ( 1 ) 储备簇首是根据邻居信息动态变化的，标志节点的计算增加了节点负担： ( 2 ) 标志节点的选取和簇偏离趋势的选取需要进一步完善。 1 8 大连理1 = 大学硕十学f 书论文 3 4 仿真 仿真实验的内容包括三个方面：一是验证算法的可行性，主要考察簇首选择算法的 正确性、储备簇首选举的正确性和簇内两簇首问交接的合理性；二是考察分簇算法是否 能够增强簇结构的稳定性，主要通过簇的生存时间来衡量，通过对网络内若干簇进行采 样并计算平均生存时间，比较不同速度下簇生存时问的差异，判断速度对簇结构的影响； 三是考察分簇算法对簇结构的稳定性的相对增强程度，主要通过和现有经典分簇算法进 行比较，在相同环境下，比较双簇首分簇算法和选择的经典分簇算法在增强簇的稳定性 上的差异，并对结构进行分析。 仿真环境配置为：网络地理范围5 0 0 m x 5 0 0 m ，运行时日j1 2 0 s ，网络中各节点通信 范围半径为1 5 0 m ，移动速度5m s 至1 5 m s ，采用随机移动模型，节点总数为2 0 0 。取 网关和成员节点标志节点计算的权重分别为口= o 6 ，= o 4 。当簇首偏离簇的趋势万 2 时，即簇首较储备簇首少一半的标志节点时，储备簇首替代簇首。和双簇首分簇算法进 行比较的经典分簇算法选为最小i d 分簇算法和被动分簇算法，并在移动速度为q o n e s 时对簇的生存时间进行比较。 表3 1 是初始成簇后簇首和储备簇首同簇邻居数的比较，表中簇编号以簇首的耐号 来标识。可以看到两节点的同簇邻居数基本一致，由于初始簇形成，簇内的节点都是标 志节点，结果显示储备簇首的标志节点数基本和簇首一致。簇形成后，算法执行与理论 结果一致。 表3 1 簇首和储备簇首邻居数比较 t a b 3 1n e i g h b o rn u m b e r sc o m p a r i s o nb e t w e e nc ha n da c h 簇编号0 12561 0 1 93 75 4 c l l4 13 85 93 34 45 95 04 l3 9 a c h3 42 45 73 24 45 54 32 94 l 图3 2 是仿真过程中，网络拓扑结构的截图。在图3 2 中，大圆圈是簇首节点的通 信覆盖区域。储备簇首作为簇内标志节点最多的节点之一，从地理位置应位于标志节点 较集中的区域，图中的储备簇首节点和簇首的相对位置也说明了这一点。图中存在储备 簇首与簇首发生偏离的情况，这是由于储备簇首根掘标志节点数来选取的，即储备簇首 距离标志节点较近。图3 2 显示，在簇的维持阶段，双簇首分簇算法的执行结果也是正 确的。 1 9 无线白组网簇刍! i 构与协作研究 图3 2 网络拓扑截图 f i g 3 2n e t w o r kt o p o l o g y 图3 3 是速度分别为5 m s 、1 0 m s 和1 5 m s 情况下簇平均生存时日j 的5 次采样结果 比较。图中可以明显看到，在不同速度下，簇的平均生存时间基本趋于一致。这说明由 于储备簇首作为簇首的替代节点，当簇首由于移动等因素将要导致簇消亡时，储备簇首 继续了簇首的职能，减少了由于移动性对簇结构的影响。 s 鲫呻帕s e n “h 哪出“ 幽3 3 簇平均生存时间采样比较 f i g 3 3c l u s t e rl i v i n gt i m ec o m p a r i s o n 大连理1 ：人学硕十 付论文 表3 2 是不同速度下，平均簇重构次数和储备簇首替代簇首次数的比较。根据维持 算法，在簇首不能继续胜任时，需要由储备簇首接替。储备簇首作为邻居中标志节点较 多的节点，替代原簇首成为新的簇首，其邻居节点不需要执行簇首选举算法，仅需要更 新簇首信息。而其他原簇内节点或者加入其他簇，或者进入初始状念重新执行簇首选举 算法。因此，算法减少了节点速度对簇结构的影响。 表3 2 平均簇重构次数与储备簇首替代次数比较 t a b 3 2a v e r a g er e c l u s t e r i n gt i m e sa n da c h - r e l a yc o m p a r i s o n 图3 4 是双簇首分簇算法( d c h ) 和最小i d 分簇算法( l i d ) 、被动分簇算法( p c ) 簇平 均生存时间采样比较。由于l i d 算法在簇首选举上有失公平，簇变化频率较快，簇稳定 性较差。p c 算法避免了l i d 算法可能产生的链式效应，增强了簇的稳定性。双簇首分 簇算法在簇首选举上使用改进的f d w 规则，在簇首选择上具有p c 算法的优点，同时 增加了仞始态节点对网络中是否存在簇首的判断，较少了新节点对现有簇结构的影响， 并通过标志节点的判断，使用储备簇首接替簇首来延长簇生存时间，进一步增强了簇的 稳定性。 翱嗍g & 硎概m 晰 图3 4 不同分簇算法簇平均生存时间采样比较 f i g 3 4c l u s t e rl i v i n gt i m ec o m p a r i s o no f d i f f e r e n tc l u s t e r i n ga l g o r i t h m 无线白组网簇结构与协作研究 仿真结果表明，通过储备簇首和簇首标志节点个数比较，对簇首行为进行简单预测， 在发现簇首不再胜任时，由储备簇首接替成为新一任的簇首，减少了不必要的簇重构， 延长了簇的生存时间，加强了簇的稳定性。 大迕理t 大学硕十学位论文 4 网关支配集优化策略 4 1 问题的提出 无线自组网是一种多跳自组织网络，可以用无向图g r _ ( 杉e ) 来表示，v 是节点的集 合，e 是边的集合，这里假设g 是连通的。由于无线自组网自身存在能量和带宽上的限 制，为了提高网络性能，一种办法就是将网络划分为簇。在有簇首的分簇结构中，簇由 簇首、网关和成员节点组成。簇首作为簇存在标志，负责协调和管理簇内成员问的通信； 网关是能连接多个簇的节点，负责簇问的信息转发。 广播操作将一个节点发送的消息传送给网络中所有其它节点。当前尚无一种专门为 自组网设计的广播协议，最直接的广播途径是“洪泛”( f l o o d i n g ) 。一般来说，白组网中 的洪泛用于找一条到达目的地的可行路由或者广播路由信息以及网络拓扑变化信息等。 几种路由算法：d s r ，a b r 等依靠洪泛获得路由信息。无线自组网的路由高度依赖于网 络的节点密度。仿真结论表明1 8 】，在稀疏网络中，协议以洪泛方式执行效果较为理想。 然而，分析表明，在高密度的无线自组网中，无控制的洪泛会带来如下的广播风暴 ( b r o a d c a s ts t o r m ) f 3 题：( 1 ) 产生大量的重复消息，使得网络带宽被浪费；( 2 ) 由于共享 传输介质造成大量碰撞，降低消息的