（计算机科学与技术专业论文）无线传感器网络分簇算法研究.pdf

无线传感器啊络分簇算法研究 摘要 无线传感器网络由大量资源，能量、计算能力、存储能力及通信能力受限的 传感器节点组成。目前，无线传感器网络广泛应用于灾难监测，战地侦查，边界 保护以及安全监管等领域。分簇在大型传感器网络中的作用十分重要，将无线传 感器网络节点组织成簇，通过数据融合，可以有效降低数据传输量，减少节点通 信开销，延长网络生存时间。 首先，本文提出了一种基于a c e ( a l g o r i t h m f o rc l u s t e re s t a b l i s h m e n t ) 分簇结 果的优化算法。a c e 是一种具有良好反馈机制的自适应分布式成簇算，a c e 只需 要进行3 轮迭代就可以完成分簇。优化算法由合并未分簇结点和合并冗余簇两个 部分组成。在实验仿真中，我们将优化算法与a c e 和o s o s ( o p t i m a ls e l f o r g a n i z i n gs e n s o rn e t w o r ka l g o r i t h m ) 进行了对比，实验结果证明我们的优化算法 能够有效减少网络中冗余簇的数目，降低簇间重叠。 接下来，本文提出了一种适用于传感器网络的基于权重的层次分簇算法 ( w b c h a ) 。w b c h a 由以下两个模块构成：基于权重的簇形成算法和层次结构的数 据传输协议。基于权重的簇形成算法综合考虑了节点的剩余能量以及潜在专属成 员数目，权重最大的节点将自举为簇头节点。在分簇完成后，通过层次结构的数 据传输协议将网络划分为多层的层次结构，高层的分簇负责收集低层分簇的传感 数据，在进行相应数据融合后将最终的数据发送给基站。在实验仿真中我们比较 了w b c h a 和l e a c h 算法的性能，实验数据证明w b c h a 能够有效降低网络通 信开销，延长网络生命周期。 关键词：分簇；优化算法：权重；层次；无线传感器网络 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k sa r ec o m p o s e do fah u g en u m b e ro fs e n s o rn o d e s ，w h i c h h a v eli m i t e dr e s o u r c e s ，e n e r g y ，m e m o r ya n dc o m p u t a t i o np o w e ra n dc o m m u n i c a t i o n c a p a b i l i t i e s w i r e l e s ss e n s o rn e t w o r k sh a v ew i d e l yu s e di n a p p l i c a t i o n ss u c ha s d i s a s t e rm a n a g e m e n t ，c o m b a tf i e l dr e c o n n a i s s a n c e ，b o r d e rp r o t e c t i o na n ds e c u r i t y s u r v e i l l a n c e c l u s t e r i n gi se s p e c i a l l yi m p o r t a n tf o rs e n s o rn e t w o r ka p p l i c a t i o nw h i c h i sc o m p o s e do ft h o u s a n d so fs e n s o rn o d e s i tr e d u c e se n e r g yd i s s i p a t i o na n dp r o l o n g s t h en e t w o r kl i f e t i m et h r o u g hd a t aa g g r e g a t i o na n d r e d u n d a n c ye l i m i n a t i o n f i r s t ，i nt h i sp a p e r ，w ep r e s e n ta no p t i m i z i n ga l g o r i t h mf o rm i n i m i z i n gt h e c l u s t e ro v e r l a po fa c e ( a l g o r i t h mf o rc l u s t e re s t a b l i s h m e n t ) a c ei sad i s t r i b u t e d c l u s t e r i n ga l g o r i t h mf o rs e n s o rn e t w o r k st h a tu s e st h r e er o u n d so ff e e d b a c kt oi n d u c e t h ef o r m a t i o no fah i g h l ye f f i c i e n tc o v e ro fu n i f o r mc l u s t e r so v e rt h en e t w o r k t h e p r o p o s e ds c h e m ec o n s i s t so ft w oo p t i m i z i n gp r o c e s s e s ：u n c l u s t e r e dn o d em e r g i n ga n d c l u s t e rm e r g i n g w et e s t e dt h ep r o p o s e da l g o r i t h ma n dc o m p a r e di t w i t ha c ea n d o s o s ( o p t i m a ls e l fo r g a n i z i n gs e n s o rn e t w o r ka l g o r i t h m ) ，t h ee x p e r i m e n t sr e s u l t s s h o wt h ep r o p o s e da l g o r i t h mc a n e f f i c i e n t l ye l i m i n a t et h er e d u n d a n tc l u s t e rh e a d sa n d m i n i m i z et h ec l u s t e ro v e r l a p t h e n ，w ep r o p o s e saw e i g h tb a s e dh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m ( w b c h a ) f o rs e n s o rn e t w o r k ，t h ep r o p o s e d c l u s t e r i n ga lg o r i t h mc o n s i s t so ft w om o d u l e s ： w e i g h tb a s e dc l u s t e rf o r m a t i o na l g o r i t h ma n dh i e r a r c h i c a ld a t at r a n s m i s s i o np r o t o c 0 1 t h ec l u s t e rf o r m a t i o na l g o r i t h mt a k e st h em e a nc o u n t so f p o t e n t i a ll o y a lm e m b e r sa n d b a t t e r yp o w e ro fm o b i l en o d e si n t oc o n s i d e r a t i o n ，t h en o d ew i t hh i g h e s tw e i g h tw i l l a n n o u n c ei t s e l fa sc l u s t e rh e a d e r t h ep u r p o s eo fh i e r a r c h i c a ld a t at r a n s m i s s i o n p r o t o c o l i st of o r mam u l t i - t i e rh i e r a r c h i c a lt o p o l o g yi nt h en e t w o r k ，t h eh i g e r l a y e r c l u s t e r sc o l l e c tt h es e n s o rd a t af r o ml o w e rl a y e r ，d os o m ea g g r e g a t i o n ，t h e ns e n dt h e d a t at ot h eb a s es t a t i o n w et e s t e dt h ep r o p o s e da l g o r i t h ma n dc o m p a r e di tw i t h l e a c h ，t h ee x p e r i m e n t sr e s u l t ss h o wt h ep r o p o s e da l g o r i t h mc a ne f f i c i e n t l yr e d u c e s o v e r a l le n e r g yc o n s u m p t i o na n d p r o l o n g sn e t w o r kl i f e t i m e k e yw o r d s ：c l u s t r i n g ；o p t i m i z a t i o n a l g o r i t h m ；w e i g h t ；h i e r a r c h i c a l ；w i r e l e s s s e n s o rn e t w o r k 1 1 1 无线传感器嗍络分簇算法研究 插图索引 图3 1a c e 分簇重叠区域示意图2 0 图3 2 未分簇节点合并示例“2 3 图3 3 冗余簇合并示例2 5 图3 4 不同节点度下网络平均专属成员数目2 6 图3 5 不同迭代次数的分簇结果比较2 6 图3 6 合并过程中出现的冲突2 7 图3 7 基于节点i d 的时间分片示例2 7 图3 8a c e 算法和优化算法的网络拓扑比较2 9 图3 9 成簇结果图3 0 图3 1 0o s o s 和优化算法的优化改进比较3 0 图3 1 1 优化前后不同节点度专属成员数目小于网络均值的簇数目比较3 l 图3 1 2 优化前后不同节点度簇平均专属成员数目与节点度数的比值比较3 1 图4 1 能量模型示意图3 4 图4 2 不同迭代次数的分簇结果比较“3 6 图4 3 边缘节点死亡示意图3 7 图4 4 三层分簇网络结构示意图3 8 图4 5w b c h a 与l e a c h 节点平均能耗对比4 0 图4 6w b c h a 与l e a c h 的剩余有效节点数目对比4 1 图4 7w b c h a 与l e a c h 节点的平均能量利用率比较“4 l v i 硕j 二学位论文 附表索引 表3 1a c e 算法和优化算法的分簇结果比较一2 9 表4 1 实验能量模型参数表3 9 v i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 凋 弓星、日期：弘哆年6 月r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囹。 ( 请在以上相应方框内打“”) 日期：矽年6 月re t 日期：) 哆年6 月j 7 e t 硕上学位论文 1 1 选题背景及意义 第1 章绪论 随着微机电系统、片上系统、无线通信和嵌入式技术的飞速发展，孕育出无 线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) ，并以其低功耗、低成本、分布式 和自组织的特点带来了信息感知的一场变革。无线传感器网络的研究起源于上世 纪9 0 年代，是一种综合了传感器技术、嵌入式计算技术、分布式信息技术、数 据库技术等多种技术的新兴网络。 无线传感器节点是由传感器，数据处理以及无线通信模块组成的，传感器节 点负责侦测网络环境的特定的事件或信号，然后将传感数据传送至网络中的数据 处理节点( 中心节点) 或基站进行处理。传感器网络是由大量传感器节点组成的无 线网络，传感节点可通过飞机布撤或人工布置等方式，大量部署在被感知对象内 部或附近，这些节点通过自组织方式构成无线网络，以协作的方式实时感知、采 集和处理网络覆盖区域中的信息，并通过多跳网络将数据经s i n k 节点链路将整个 区域内的信息传送到基站。 传感器网络和传统的无线a dh o c 自组织网络有很多相似之处。但是，无线a d h o c 网络应用中的一些成熟分簇算法【2 西1 并不能很好的适用于传感器网络，这是由 于和传统的a dh o c 网络相比，无线传感器网络具有以下特征： 1 ) 传感器网络中节点的数目要比a dh o c 网络大得多。为了对一个区域执行监 测，往往需要在监测区域部署大量的传感器节点。 2 ) 传感器节点分布非常密集，通常利用节点之间高度连接性来保证系统的抗 毁性和容错性。 3 ) 由于传感器节点工作的外部环境通常比较恶劣，因此传感器节点非常容易 失效。 4 ) 传感器网络的拓扑经常发生变化。无线传感器网络是一个动态的网络，节 点能够随处移动；一个节点可能会因为电池能量用完或其他故障原因而失效停止 运行；一个节点也可能由于某种需要而被添加到当前网络中。这些都会使网络的 拓扑结构发生变化，因此无线传感器网络具有动态拓扑组织功能。 5 ) 在传感器网络中，节点相互之间通常是通过广播进行通信的，而在a dh o c 网络中，节点间主要依赖端到端的单播通信。 无线传感器纠络分簇算法研究 6 ) 由于受到价格、硬件体积、功耗等的限制，传感器节点的信号处理能力、 计算能力有限，在程序空间和内存空间上与a dh o c 网络中的节点相比较，其功能 更弱。 7 ) 在无线传感器网络中，节点只能同它的邻居直接通信。如果想与其射频覆 盖范围之外的节点进行数据通信，则需要通过中间网络节点进行路由。无线传感 器网络中的多跳路由是由普通网络节点来完成的，没有专门的路由设备 8 ) 传感器节点的能量非常有限。由于受到硬件条件的限制，网络节点通常由 电池供电，电池能量有限。同时，无线传感网络节点通常被放置在恶劣环境或者 无人区域，使用过程中，不能及时给电池充电或更换电池。 9 ) 传感器节点通常没有全局的统一标识i d ，这是由于传感网中节点数目一 般比较多，如果要给每个节点都分配一个统一标识是比较困难的。 在传感器网络中，传感器节点通过搭载不同类型的传感器，可以很好地监控 周边环境的温度，压力，光照条件，湿度等因素【| ”。可以将传感器节点大范围地 散布在特定区域，通过节点间的分工协作，实时监测、感知和采集网络分布区域 内的各种环境或监测对象的数据，并对这些数据进行处理，获得详尽而准确的信 息。无线传感器网络可广泛应用于国防军事、国家安全、环境监测、交通管理、 医疗健康、制造业、反恐抗灾乃至商业和家庭等诸多领域博d ”。 在一些大型传感网应用中，由于传感器节点数目较多，如果每一个节点都频 繁地与其周边节点或者基站进行数据通信，那么势必会出现网络拥塞，传输冲突 几率的提高以及节点能量过早的耗尽等情况。为了降低网络中存在的传输冲突几 率，提高网络的扩展性，延长网络的生存周期，通过特定的分簇算法合理地对网 络中的节点进行分簇就显得尤为重要。 分簇是对网络中的节点进行层次划分，若干地理位置相邻节点构成一个簇， 在每个簇内通过一定的簇头选举机制选举一个簇头节点( c h ) ，簇内的其他节点为 簇成员节点。簇成员节点将采集到的数据直接传送给簇首，而簇头节点将数据融 合后发送到s i n k ，如果簇头节点距离s i n k 比较远，可以通过其它簇头节点进行转 发。在分簇算法中主要包括成簇、簇维护、簇内路由和簇间路由4 个部分。成簇 主要解决如何在动态分布式网络环境下使节点高效地聚集成簇，它是分簇算法的 关键，簇维护解决在节点移动过程中的簇结构维护，其中包括移动节点退出和加 入簇、簇的产生和消亡等功能。簇内和簇问路由主要是从降低能量消耗的角度， 选择最优化的路由。衡量一个分簇算法的优劣主要有以下几个标准，簇结构的稳 定性，簇首节点的数量以及负载均衡度等。 由于传感器节点在功耗、资源、计算和存储能力及通信范围等都受到较大限 制，使得现存的些应用于a dh o c 网络的较为成熟的分簇算法不能直接应用于 2 硕j ：学位论文 传感器网。因此，研究适用于传感器网络的分簇算法就成为了目前传感器网络研 究的热点问题之一。 1 2 研究范围和内容 目前，随着无线传感器网络分簇算法研究的深入，已经有不少学者提出了基 于特定网络结构和特定网络应用的分簇算法。这些分簇算法的研究内容主要包括 以下几个方面： 1 ) 簇头的选取和簇的形成：簇头的选取和簇的形成是分簇算法的重点。簇头 选取应尽量选取具有较大剩余能量和通信能力的节点，从而使簇头能够更好地进 行簇内的管理和簇间信息的交互。 2 ) 簇头的轮换：由于在某些同构网络应用中，簇头节点和成员节点的通信能 力和能量是相同的。而簇头节点又要承担比普通成员节点更多的工作，为了使簇 头节点不会因负载过重而能量过早耗尽，定期地轮换簇头是非常必要的。 3 ) 均衡网络负载：在传感器网络中，由于被探测事件发生和数据传输存在区 域性，从而有可能造成某区域内节点能量过早耗尽。簇头节点相对普通节点能够 承担更多的工作，如何利用分簇来达到网络负载均衡是提高网络数据传输能力一 个有效措施。 4 ) 提高网络容错能力：在很多应用中，w s n s 的工作环境非常恶劣，并且在 某些应用中传感器节点具有移动性，网络中可能存在节点死亡，通信链路失效以 及通信干扰等问题。因此如何在网络中保证数据传输的可靠性以及如何在链路失 效后快速有效地对链路进行修复就成为了分簇算法的研究重点之一。 5 ) 最优成簇数目：在传感器网络中，如何簇的数目过多将会导致簇内以及簇 间通信发生冲突的几率大大增加。因此，通过减少网络中分簇的数量，降低簇间 的重叠，能够有效提高网络的通信质量。 6 ) 延长网络生存周期：由于传感器节点的能量是非常有限的，因此延长传感 器网络的生存周期一直是分簇算法研究的热点内容之一。簇头节点通过特定的管 理和数据通信机制能够有效地降低簇内通信的开销，从而延长网络生命周期。此 外，将网络划分为层次结构也可以有效的降低网络中节点的通信开销。 1 3 本文的工作 本文主要包括以下几方面的工作： 1 ) 分析了由c h a n ，h 和p e r r i g ，a 提出的一种基于e m e r g e n t 算法的分布式成 簇算法a c e 。在a c e 算法中，最后一轮分簇将导致一些专属成员较少的节点被 选举成为簇头节点，因而造成了在这些簇头附近，簇间重叠非常大，这将增加通 无线传感器网络分簇算法研究 信发生冲突的几率。在此基础上，本文提出了一种针对a c e 成簇结果的优化算法。 该算法能够减少网络中存在的冗余簇，大大降低网络中簇间重叠，从而降低了网 络的通信开销。 2 ) 提出了一种基于权重的层次分簇算法，该算法由基于权重的簇形成算法和 层次网络数据传输协议组成，该分簇算法能够有效降低节点通信开销，显著延长 传感器网络的生存周期。 1 4 论文结构 本论文的结构安排如下： 第1 章主要介绍论文的研究背景、研究的必要性、研究范围、研究内容及本 文的工作。 第2 章主要介绍当前在这个领域主要的研究成果和方法，并介绍了当前较成 熟的分簇算法。 第3 章深入分析了a c e 分簇算法，并基于该算法提出一个基于a c e 分簇结 果的优化算法。 第4 章提出了一种基于权重的层次分簇算法。 4 硕1 ：学位论文 2 1 引言 第2 章研究综述 随着微电子技术的发展，w s n s 在民用和军事领域的应用越来越广泛。越来 越多大型传感网应用不断涌现，给传感网络的研究也带来了许多挑战。由于传感 节点的能量和通信能力有限，如何提高传感器节点的利用率以及延长网络的生存 周期一直是传感器网络研究的热点问题之一。通过分簇算法将传感网络中的节点 进行分簇是延长网络生命周期，平衡网络负载的一个非常有效的策略。 网络中的每个分簇都存在有一个管理节点，通常我们称之为簇头节点( c h ) ， 簇内的其它则为簇的成员节点。在分簇中，簇成员将侦测的数据发送给簇头节点， 簇头节点对成员节点采集的数据进行融合后在发送给基站。簇头节点的选取可以 在部署前通过预选取机制选择一部分资源较丰富和通信能力较好的节点作为簇头 节点，也可以在节点部署完成后，节点通过特定簇头选举算法自举为簇头节点。 簇头节点既可以是那些资源比较丰富和通信计算能力较强的节点( 通称存在于异 构网络) ，也可以是和成员节点一样的普通节点( 同构网络) 。簇头节点在网络中扮 演了多种管理角色，如簇头节点可以为簇内成员节点提供路由信息，这样成员节 点仅需要保存少量的路由信息或者无需保存任何路由信息，从而提高了簇成员节 点存储空间的利用率i i 8 】；簇头节点能够参与网络的拓扑控制，从而有效降低网络 拓扑维护的开销【1 9 】；簇头节点可以调度簇内成员的传感侦测行为以及节点何时进 行通信，使得簇内成员在空闲时间能运行于低能耗状态，从而降低成员节点的能 耗【2 0 2 3 1 。簇头节点通过定期收集成员节点的侦测的传感信息，对采集信息进行相 应的数据融合处理，从而降低了网络的通信开销1 2 引。 2 2 研究中遇到的挑战 节点能量有限：无线传感节点的能量比较有限，节点在部署完成后，几乎不 可能再对节点的电池进行充电或更换节点电池。因此与传统的应用于无线a dh o e 网络的分簇算法相比，无线传感网络的分簇算法需要更多地考虑如何降低节点的 通信开销。 网络寿命：由于传感器节点能量非常有限，因此传感网络的寿命就成为了研 究的热点问题。在异构网络中，簇头节点资源较普通节点要丰富，因而簇头节点 能够承担较其成员节点更多的负载，从而减轻普通节点的能耗，延长网络寿命； 而在同构网络中，由于簇头节点就是普通节点，由于簇头节点要承担比成员更多7 无线传感器纠络分簇算泫研究 的任务，因此必须通过簇头轮换机制来定期更换簇头，使簇头不会过早死亡，从 而延长网络的寿命。 成簇数目：在异构网络中，由于簇头节点资源丰富，因此其造价也较高。因 此，在一个异构传感网络应用中，减少成簇数目，可以相应降低网络的造价。降 低网络中簇头节点的数目，可以有效地降低簇问重叠，从而减少因通信冲突带来 的开销。此外，减少成簇数目也可以有效地延长网络寿命。 网络负载：在传感网络中，由于事件发生具有区域性，因此可能会导致某个 区域内节点因通信过于频繁而耗尽有限的能量。由于簇头节点对簇内成员的探测 行为进行调度，在某个事件发生的区域内可能存在多名该簇的成员节点，那么簇 头节点可以根据成员节点的剩余资源来决定让那些剩余资源较丰富的成员节点进 行事件探测，而剩余资源较少的成员则进入低能耗的休眠状态。此外，在数据融 合中，簇头节点可以采集成员节点探测的数据，并进行相应的处理，最后将处理 数据上传至基站，从而避免了成员节点直接与基站进行通信。 容错能力：在一些传感网应用中，由于外部环境比较恶劣，节点可能存在失 效或被俘获的危险。因此，当簇头节点因某种原因失效时，必须提供相应的容错 措施来避免重要数据的丢失。在簇中预置一些候补簇头是一个有效的容错策略。 而在簇内对簇头节点进行轮换也是容错的有效机制，并且该机制还能够平衡簇内 的负载。 网络的连通度：在很多传感网应用中，簇内连通度是网络中非常重要的一个 因素。较好的网络连通度可以保证每个簇头到基站都能够建立一条有效路径，甚 至能够对路径的跳数进行约束控制。提高簇内连通度能够有效地降低网络中的传 输延迟。 簇内以及簇间通信的安全性：在某些传感网应用中，如军事侦察，这些应用 对数据的安全性要求非常高。因此，如何在这类传感网应用中建立安全的簇内以 及簇间的通信链路是在设计分簇算法必须考虑的一个重要问题。 数据通信质量( q o s ) ：目前大多数传感器网络分簇算法主要关注于如何降低 网络的通信开销，延长网络生命周期，很少有分簇算法关注网络中数据通信的质 量( q o s ) 。在许多传感器网络应用中，对数据传输延时和丢包率的要求是非常严格， 因此在给这些应用设计分簇算法时，必须着重考虑网络的q o s 。 2 3 分簇算法概述 2 3 1 分簇算法分类 依据不同的分簇特性，分簇算法可以被划分为不同的类别。常见的分类依据 有： 6 硕士学位论文 依据分簇算法复杂度( 收敛时间) 可将分簇算法划分为：可变收敛时间分簇算 法，如l c a 2 5 1 ，r c c 2 6 1 和c l u b s 2 7 1 ，这些算法的收敛时间为o ( n ) ，其中n 为传 感器节点的数目；常量收敛时间分簇算法，如l e a c h 2 引，f l o c 2 9 1 ，g s 3 【3 0 1 以及基 于特征属性的分簇算法等。 依据分簇算法的方法策略可将分簇算法划分为：集中式分簇算法，由基站参 与分簇的管理；分布式分簇算法，分簇无需基站参与，完全是以分布式的方式在 节点间进行的；混合式分簇算法，结合了集中式分簇算法和分布式分簇算法的优 点。 依据网络中节点的能力不同可划分为：适用于同构网络的分簇算法，即网络 中所有节点能力都是一样的；适用于异构网络的分簇算法，在该类算法中，簇头 节点的资源较丰富，且其通信能力要强于普通传感器节点。 依据簇头选取的策略可划分为：簇头预先选取，簇头是在部署前预先选取好 的，大多出现于异构网络中；簇头随机选取，在网络部署完成后，节点以一定的 随机选取策略自举为簇头节点。 依据成簇后网络拓扑结构可划分为：平面网络结构分簇算法，即网络成簇后 簇与簇之间关系是平等的；层次网络结构分簇算法，在该类算法中，通过分簇将 网络划分为多层结构，上级簇对下级簇进行管理，而顶级簇直接与基站进行交互。 2 3 2 典型的分簇算法介绍 2 3 2 1l e a c h l e a c h ( l o we n e r ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 2 8 1 算法是最早提出来适用 于无线传感器网络的分簇算法之一。在该算法中，网络中存在一个基站负责收集 网络中节点采集的数据，网络中所有的传感器节点都可以直接与基站进行通信。 l e a c h 算法依据接收信号的强弱进行分簇，并且簇头接点通常承担了成员节点 与基站之间的中转路由器。此外，簇头接点还承担了簇内的数据收集和数据融合 任务。 该算法的成簇过程如下：网络周期性地进行簇首选举，每一个周期称为一轮 在簇的建立阶段，节点i 生成一个 0 ，l 】间的随机数r ，如果r f m i n ( t ) ，则a 节点自举为簇头，然后a 将选择一个随机数作为簇i d ，向 其邻近节点广播r e c r u i t 消息，收到该消息的节点随即加入a 簇；f m i n ( t ) 是一个 成簇阀值函数，f m i n ( t ) 的值随着协议运行时间t 的增加而逐渐减小，这样有利于一 开始形成拓扑比较合理的分簇。在分簇进行到最后一轮迭代时，由于成簇阈值较 低，因此可以使那些未被覆盖的节点较为容易地形成簇。 如果a 是簇头节点，则它试图从其所在的簇中找出一个最佳候选簇头( 最佳 候选簇头是指簇内拥有最多专属成员的节点) 。假如b 为a 的最佳候选簇头节点， 那么b 的专属成员既包括了b 的未分簇邻居节点，又包含了a 簇的专属成员。 1 2 硕 ：学位论文 如果b 就是a 本身，则本轮迭代终止，簇结构不变；如果b 为簇内的其他节点， 则a 开始运行迁移算法：a 向b 发出p r o m o t e 消息，b 收到后用a 簇i d 广播 r e c r u i t 消息，收到该消息的所有节点加入b 簇。a 收到b 的r e c r u i t 消息之 后广播a b d i c a t 消息。这样，原来a 簇的节点如果是b 的邻居节点，则从a 迁 移到了b ；不是b 的邻居节点，则退出了该簇。由此完成了从a 到b 的簇的迁移。 当节点a 的一轮迭代开始时，如果a 是已分簇节点，则它什么都不做，随机 等待一段时间后进入下一个迭代周期。 当所有节点都完成迭代算法之后，有可能少量节点没有被覆盖，所以最后还 需要进行一次“c l e a n u p ”迭代，该过程不再发生簇的迁移，所有未被覆盖的节点成 为簇头或者通过邻居节点成为其他簇的多跳成员节点。 a c e 算法具有良好的健壮性，对节点失效和报文丢失反应迅速，生成的簇能 有效减少相互之间的重叠，降低簇间通信干扰的概率，并且成簇收敛速度与网络 规模无关。 2 3 2 8h i e r a r c h i c a lc o n t r o lc l u s t e r i n g h i e r a r c h i c a lc o n t r o lc l u s t e r i n g l 4 0 】算法能够将网络划分为层次的分簇结构。在 该算法中，网络中的每一个节点都有机会发起成簇请求，如果有多个节点同时发 起成簇请求，那么其中i d 最小的节点具有优先权，其它节点必须停止成簇请求。 h i e r a r c h i c a lc o n t r o lc l u s t e r i n g 的成簇过程包含以下两个阶段：树结构建立阶 段以及簇生成阶段。树发现阶段基本上是一个以发起成簇请求节点为根节点的分 布式的广度优先树( b f s ) 的建立过程。网络中的节点a ，每隔p 个单位时间就向其 邻近节点广播一条消息，该消息包含了该节点到根节点的最短距离r ，其单位为 跳数( h o p ) 。a 的邻居节点b 在接收到a 的广播消息后，将检查它到根节点的路 径距离。如果b 到根节点之间没有建立任何路径或者b 通过a 到根节点的距离 要比其先前建立的路径更短的话，那么b 就选取a 作为其父节点并更新其到根节 点的路径以及路径的跳数。随后b 将在网络中进行广播，b 广播的消息包含了发 起广播的节点的i d ，父节点i d ，根结点i d 以及子树的大小。当父节点接收到子 节点广播的信息后，父节点将检查子节点的子树大小是否发生了改变。如果发生 了改变，那么父节点也相应更新其子树大小。 在成簇阶段中，如果一个节点的子树大小超过参数k ，那么该节点就依据其 子树开始成簇过程，其中参数k 通过控制子树的大小来控制最终的成簇结果。如 果其子树的大小小于2 k ，那么整个子树就行成一个单一的分簇，该节点就成为簇 头。否则，子树中的节点将形成多个分簇。 该成簇算法能够很好的适应网络环境多变的情况，如网络中存在节点移动的 情况。 无线传感器嘲络分簇算法研究 2 3 2 9m o c a m o c a 4 1 】是一种随机分布式多跳重叠分簇算法，在该算法中，y o u s s e f 等主 张应该在相邻的分簇之间保留一定大小的重叠区域，从而能够为簇间通信，拓扑 发现，节点的定位以及簇头失效后簇的自我修复等应用提供便利。在m o c a 算法 分簇完成后，网络中的节点要么是簇头节点，要么是成员节点，且节点与其相邻 近分簇的簇头节点之间的距离( 单位：跳数) 不大于k ，k 通常被称为分簇的半径。 该算法的具体分簇过程如下：在算法刚开始运行时，网络中的每个节点都有 p 的概率自举为簇头节点。当节点a 自举为簇头节点后，节点a 将向在其通信范 围内的邻居节点广播它的节点i d 。邻居节点b 在收到簇头a 的广播消息后，首 先检查广播数据包经过的跳数，如果跳数小于k ，那么b 将数据包的跳数加1 ， 然后将该数据包继续广播出去。因此距簇头a k 跳距离之内的所有节点都能够接 收到簇头a 所发送的广播消息，并且节点可能同时收到多个簇头发送的广播消息。 随后，所有接收到簇头广播的节点都将向簇头a 节点发送入簇请求，入簇请求消 息包含了该节点所有已知的簇头节点的i d s ，因此在簇头节点a 在接收该节点发 送的请求消息后，簇头节点a 可以通过消息中所包含的簇头节点个数判定消息发 送节点是否为边界节点。若消息内包含的簇头个数大于1 ，就说明这个节点是一 个边界节点，即该节点位于多个簇相互重叠的区域。 在m o c a 中，网络中成簇的数目以及簇间的重叠大小是通过p 来控制，因此 该算法使得网络具有非常好的扩展性。并且由于簇之间的具有一定的重叠区域， 该算法的容错能力也较好。 2 3 ，2 1 0c l u b s 在文献 2 7 】中，n a g p a l 和c o o r e r 提出了一种分布式的分簇算法c l u b s 。该 算法充分利用了局部广播来进行分簇，该算法的收敛时间与网络中局部节点密度 相关。 c l u b s 分簇算法具有以下几个特性： 网络中的每个节点都必须归属于一个簇头节点。 网络中所有簇的最大直径是一致的。 簇必须支持簇内通信，即簇成员之间可以很方便地进行信息交互。 在该算法中，簇头和其成员节点问的最大距离为2 跳。其分簇的具体过程如 下：在簇头自举阶段，网络中的每个节点产生一个特定范围内的随机整数，然后 节点将逐步地对这个随机整数进行递减操作。若在该整数递减至o 的过程中，该 节点没有受到任何邻居节点的干扰，那么该节点就宣称自己为簇头节点，并向距 其2 跳远的邻近节点广播“r e c r u i t ”信息。当一个邻居节点接收到该信息后，该节 点立刻停止随机数的递减过程，并接受簇头的请求加入该簇。若一个节点已经加 1 4 硕 ：学位论文 入了一个簇，该节点就称为“f o l l o w e r ”。由于c l u b s 允许簇间存在一定的重叠区 域，因此f o l l o w e r 节点在接收到其他簇头发送的r e c r u i t 信息后，还可以加入其它 簇。如果一个节点在进行随机整数递减的过程中，侦测到网络中存在通信冲突， 那么就说明网络中有多个簇头节点正在向它发起入簇请求。因此该节点将停止随 机整数递减的过程，并成为一个f o l l o w e r 节点，并在网络中通信冲突消失后来寻 找合适的分簇加入。 c l u b s 实现方法比较简单，拥有不错的性能表现，能够较好地应用于异步网 络环境。不过c l u b s 也存在其不足之处：在c l u b s 中，若相邻簇的簇头节点彼 此为邻居节点，那么这样的簇就很容易因通信冲突而导致崩溃，最终导致必须重 新选择簇头。 2 3 2 1ll c a b a k e r 和e p h r e m i d e s 提出的l c a ( l i n k e dc l u s t e ra l g o r i t h m ) t 2 5 ，4 2 1 是最早应用于 无线网络的分布式分簇算法之一。该算法着重于如何在移动无线网中建立起高效 的网络拓扑结构，从而能够方便地对网络中的移动节点进行管理。在l c a 中，通 过分簇，将簇头彼此连接形成骨干网络，由于簇头可以和其簇内所有节点直接进 行通信，因此通过骨干网络可以非常方便地对移动节点进行管理。此外骨干网路 还可以大大增加网络的连通度。 在l c a 中，每个节点都分配了一个唯一的i d ，并且节点间时间是同步的， 节点的m e d i u m 访问时基于时间片的，即每个节点都以其i d 对应于一段时间槽， 当该时间槽触发后，对应节点就开始执行l c a 算法。起初，节点将向其周围节点 广播其节点i d ，并随后侦听其他节点发送的广播信息。在初始的i d 广播阶段结 束后，节点开始向周围节点广播其邻居表。在邻居信息广播结束后，所有节点都 将知道其1 跳和2 跳邻居节点。如果节点a 的i d 大于其所有邻居节点的节点i d ， 或者虽然a 的i d 在其通信范围内并不是最大，但是在a 的邻居节点中至少存在 一个节点b ，在节点b 的所有邻居节点中，a 的i d 最大，若满足上述两种情况 的一种，那么a 就自举为簇头节点。 l c a 算法的缺点是它很容易产生冗余簇，因此为了克服l c a 的不足，在文 献 4 3 】中，e p h r e m i d e s 等人提出了一种改进算法l c a 2 ，l c a 2 能够有效地减小 l c a 产生的冗余簇，l c a 2 算法的主要思想是：首先随机的选取节点x ( 节点x 仍 然要满足上述的两个条件中的一个) 为簇头节点，并且x 的邻居节点随即加入x 簇。而后x 簇内i d 最小的节点y 将命名为簇头节点，y 的邻居节点中不与x 节 点相邻的节点随后加入y 簇。这个过程将重复进行至所有节点都加入到一个分簇 中为i 匕。 无线 冬感器陶络分簇算法研究 虽然l c a 和l c a 2 能够很好地对无线移动网络进行支持，且其实现方法都比 较简单，但仍存在以下不足： ( 1 ) 由于l c a 和l c a 2 不是为传感器网络量身定制，它们都没有考虑到传感 器节点能量有限等限制，因此对传感器网络的适用性较差。 ( 2 ) l c a 和l c a 2 的时间复杂度为o ( n ) ，因此不适用于大型网络应用。 ( 3 ) l c a 和l c a 2 的负载平衡只考虑到了簇内通信，因此不适用于真实网络应 用。 ( 4 ) l c a 和l c a 2 均要求节点时间同步，因此这将限制网络应用。 2 3 2 1 2r c c r c c ( r a n d o mc o m p e t i t i o nb a s e dc l u s t e r i n g ) 1 2 6 1 分簇算法最早是基于无线a d h o c 网络，不过r c c 同样也适用于传感器网络。r c c 的主要思想是在网络中形成 稳定的分簇，通过分簇来实现对网络中移动节点的管理。 在r c c 中，簇头节点的选取依据“先入为主”的原则，即只要节点是其通信范 围内第一个广播簇头宣告消息节点，那么该节点就成为簇头节点，其通信范围内 的所有节点就成为它的成员节点。在一个节点成为簇的成员以后，它就无法再成 为簇头节点了。由于网络中节点是移动的，必须定期地对网络中分簇进行维护， 因此网络中的簇头节点必须定期地广播簇头宣告消息。由于广播消息在发送和接 收过程中存在一定的延时，相邻簇头如果同时进行广播，那么很容易造成通信冲 突。为了避免潜在的通信冲突。在r c c 中，簇头节点通过各自的i d 来设置一个 定时器，当定时器触发时，就广播广播簇头宣告消息。由于网络中节点i d 是唯 一的，因此通过节点i d 设置定时器可以保证相邻簇头不会同时进行广播。并且 如果一个簇头节点在等待过程中侦测到有其他簇头正在进行广播，则该簇头节点 将重置其定时器。此外，如果通信冲突发生了。即有两个节点同时宣称自己为簇 头，那么i d 较小的那个节点将胜出。 r c c 对移动无线网络能够很好的支持，特别是那些节点移动比较频繁的应 用，但由于在算法中存在大量的广播通信，因此对于能量有限的传感器网络来说， 适用性较差。 2 3 2 1 3l m s s c l m s s c t 4 4 】是一种混合式分簇算法，即网络的分簇过程是由基站和节点共同参 与的。l m s s c 算法包含两个阶段：簇的生成阶段和簇头选取阶段。 簇的生成阶段：在该阶段，基站根据网络的拓扑结构将网络划分为一定数目 的簇。其具体实现如下：基站首先计算网络中所有未分簇节点与其邻居节点的距 离权重w ，w 的计算公式如下： 1 6 硕士学位论文 形= 圭矗，2 ( 2 3 ) ，i i = l 其中n 为节点的邻居数目，d i 为节点与第i 个邻居之间的距离。基站将挑选出网 络中权重最小的节点，以此节点为中心形成一个分簇，并将该簇内的所有节点从 未分簇节点集合中删除。基站将迭代进行簇生成算法，直至网络中至少有8 0 的 节点已经加入分簇。 簇头选取阶段：在簇的生成阶段结束后，基站将为网络中的每个簇选择一个 合适的簇头节点。基站通过以下两个参数来确定簇头节点：距离参数和能量参数。 其中距离参数包括节点到其所有邻居的距离的平方和该节点到基站的距离的平 方，能量参数即节点的剩余能量( e r i ) 。基站通过以上两个参数来计算节点成为簇 头的权重c h ，c h 的计算公式如下： c h ( 垆既1 1 f 窆d ，2 + d 嬲21i ( 2 4 ) l j = lj 其中n 为节点i 的邻居总数，d j 为节点i 和其邻居节点