（计算机应用技术专业论文）无线传感器网络能量高效的分簇算法研究.pdf

武汉理工大学硕士学位论文 中文摘要 无线传感器网络就是由部署在监测区域内大量的微型传感器节点通过无线 通信形成的一个自组织网络系统，通过协作感知、收集监测对象的信息发送给 基站。随着无线传感器网络技术的发展，其在很多领域得到广泛的应用。无线 传感器网络与传统网络相比，具有能量有限、自组织等特点，因此研究无线传 感器网络的能量高效问题成为研究的热点问题。 本文首先对无线传感器网络的概念、体系结构、特点以及关键技术做了简 要介绍；介绍了现有的各种无线传感器网络的分簇算法，着重研究和分析了无 线传感器网络分簇算法的优缺点并对其进行了归纳和总结。 无线传感器网络中延长网络生命周期的一个重要方法就是将整个网络分成 簇。在多层分簇的网络中，簇头不仅要处理本簇内节点的数据收集，而且还要 负责对邻近簇头的数据进行转发，使这些节点能量过早的耗尽，造成整个网络 生命周期过早的结束。在解决能耗平衡问题的分簇算法中，很少有算法来考虑 这种“热点”问题，整个网络寿命受到很大的局限。本文针对多层分簇网络中 存在的能耗不平衡问题，提出一个形成不同规模的簇算法e b c a ，让离基站近的 簇头可以更多的参与数据转发，来平衡整个网络的能耗，避免离基站近的簇头 过早的耗尽能量。 最后通过对无线传感器网络仿真平台的对比，选择了o m n e t + + 做仿真实 验。仿真结果显示，本文的算法有效的解决了热点问题，使整个网络的负载更 加平衡。 关键字：无线传感器网络，分簇，热点，能耗平衡，e b c 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 s ( w s n ) c o n s i s to fl a r g en u m b e r so fm i c r os e n s o r n o d e sd i s t r i b u t e di nm o n i t o ra r e a ，t h r o u g hw i r e l e s sc o m m u n i c a t i o n f o r ma s e l f - o r g a n i z i n gn e t w o r k t h en o d ec o l l e c t e dm e s s a g eb yc o l l a b o r a t i v es e n s i n ga n d t r a n s m i t t e dd a t at ot h eb a s es t a t i o n w i t ht h e d e v e l o p m e n to fw i r e l e s s s e n s o r n e t w o r k s ，i th a saw i d er a n g eo fp r a c t i c a la n du s e f u la p p l i c a t i o n s c o m p a r e dw i t ht h e t r a d i t i o n a ln e t w o r k ，w s nh a v el i m i t e de n e r g ya n ds e l f - o r g a n i z i n gc h a r a c t e r i s t i c sa n d s oo n c o n s e q u e n t l y , e n e r g ye f f i c i e n ti nw s ni saf r o n t b u r n e ri s s u e f i r s to fa l l ，i nt h i st h e s i s ，t h ec o n c e p t i o n ，a r c h i t e c t u r e ，c h a r a c t e r i s t i c sa n dk e y t e c h n o l o g i e so fw s n a r ei n t r o d u c e db r i e f l y t h e nw ei n t r o d u c e dav a r i e t yo fe x i s t i n g c l u s t e r i n ga l g o r i t h ma n ds u m m a r i z e dt h ec h a r a c t e r i s t i co fi t e s p e c i a l l yw ea n a l y z e d t h ea d v a n t a g e sa n dd is a d v a n t a g e so ft h e m i nw i r e l e s ss e n s o rn e t w o r k s ，i ti sak e yt e c h n i q u et o o r g a n i z et h en o d e si n t o c l u s t e r s ，w h i c ha i m st om i n i m i z et h ee n e r g yc o n s u m p t i o na n dp r o l o n gt h el i f e t i m eo f n e t w o r k i nm u l t i - c l u s t e rn e t w o r k ，c l u s t e rh e a d sc l o s e rt ot h eb a s es t a t i o na c ta s r o u t e r so fc l u s t e rh e a d sf a r t h e ra w a yf r o mt h eb a s es t a t i o nd u r i n gs e n td a t at ot h eb a s e s t a t i o n s ot h a tt h e s en o d e sr u no u to f e n e r g yp r e m a t u r e l y , c a u s i n gt h ee n t i r en e t w o r k l i f ec y c l ep r e m a t u r et e r m i n a t i o n t h e r ea r em a n yc l u s t e r i n ga l g o r i t h m st os o l v et h e p r o b l e mo fu n b a l a n c e dl o a d ，b u tt h eh o ts p o tp r o b l e mc a nh a r d l yb ec o n s i d e r e d t h e n e t w o r k sl i f e t i m ei sl i m i t e d i nt h i st h e s i s ，w ep r o p o s e dah i e r a r c h i c a le n e r g yb a l a n c e c l u s t e r i n ga l g o r i t h m ( e b c a ) w h i c hi su n e q u a lc l u s t e r i n gs i z et os o l v eh o ts p o t p r o b l e m t h ec l u s t e r sn e a r b yt h eb a s es t a t i o nc a nd e a lw i t hm o r ei n t e r - c l u s t e r c o m m u n i c a t i o n i ta i m st oa v o i dd i e de a r l i e rt h a no t h e rc l u s t e rh e a d s f i n a l l yc o m p a r e dw i t hp o p u l a rt h es i m u l a t i o np l a t f o r m ，w ec h o s et h e0 m n e t + + t od os i m u l a t i o n s i m u l a t i o nr e s u l t ss h o wt h a to u ra l g o r i t h mc a ns o l v et h eh o ts p o t p r o b l e me f f i c i e n t l y t h ew h o l en e t w o r k sl o a di sm o r eb a l a n c e a b l et h a nc o n v e n t i o n a l a l g o r i t h m s k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，c l u s t e r ，h o ts p o t ，e n e r g yc o n s u m p t i o n b a l a n c e ，e b c a 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特另l j j j h 以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谓 意。 研究生( ：枷e tg q 丝z ：互：矽 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存或汇编 本学位论文。同时授权经武汉理工大学认可的国家有关机构或论文数据库 使用或收录本学位论文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生。签名，：j 四导师。签名，：互玺l 日期挚 武汉理工大学硕十学位论文 1 1 研究背景 第1 章绪论 随着微机电系统、无线通信技术、片上系统s o c 、现代微电子技术、纳米 材料、信号处理技术、计算机网络技术的发展，推动了无线传感器网络( w i r e l e s s s e n s o rn e t w o r k s ，w s n ) 技术的产生和发展。无线传感器网络是由大量的传感器 节点组成的，通过无线通信方式构成的一个自组织的网络，共同协作感知和收 集监测区域的信息发送给基站。 无线传感器网络的出现引起了全世界范围的广泛关注。商业周刊将其列位 2 1 世纪最重要的2 1 项技术之一，并预测：无线传感器网络和其他三项信息技术 将会在不远的将来掀起新的产业浪潮；m i t 技术评论将无线传感器网络列为 2 1 世纪改变世界的十大技术之一；( ( i e e es p e c t r u m ) ) 杂志发表一期专集，论述 无线传感器网络的发展和可能的广泛应用。可以预计，无线传感器网络的发展 和广泛应用，将对人们的社会生活和产业变革带来极大的影响和产生巨大的推 训1 1 。 随着无线传感器网络理论和技术的不断成熟，其应用已经由军事国防领域 扩展到环境监测、灾难预警与救助、医疗健康、智能家居、交通管理等诸多领 域。传感器网络综合了传感器技术、嵌入式计算技术、现代网络及无线通信技 术、分布式信息处理技术等，能够通过各类集成化的多功能微型传感器协作地 实时监测、感知和采集各种环境和监测对象的信息，通过嵌入式系统对信息进 行处理，并通过随机自组织无线通信网络以多跳中继方式将所感知信息传送到 用户终端，使人们随时都可以获得丰富的真实可靠的信息，从而最终实现一种 “无处不在的计算”的理念【2 】。无线传感器网络大部分的应用都有共性可循。传 感器节点和基站之间的交互类型有事件检测、定期测量、函数逼近和边缘检测、 跟踪等。上述类型同样也体现了部署选择方面的多样性。例如，按照计划部署 传感器节点，包括机械维护方面的应用以及灾难预警与救助应用等。由飞机部 署的在地面上随机分布的节点，其着陆方向是随机的，这包括了军事方面以及 恶劣环境监测方面的应用。除此之外，传感器节点也可以是移动的，束弥补部 武汉理t 大学硕士学位论文 署过程中的不足。 传感器节点大多由能量十分有限的电池供电，且长期在无人值守的状态下工 作。由于传感器网络中节点个数多、分布区域广、所处环境复杂，通过更换电池 的方式来补充能源是不现实的，必须对无线传感器网络进行能量管理，采用有效 的节能策略降低节点的能耗，延长网络的生存期。这对无线传感器网络技术的发 展有着非常重要的意义。 1 2 国内外的研究现状 无线传感器网络研究起步于2 0 世纪9 0 年代，最早应用于军事领域。无线 传感器网络广阔的应用前景使得对无线传感器网络的研究与开发成为目前信息 领域的一个热点。美国国防部和各军事部门把无线传感器网络作为一个重要的 研究领域。英特尔、微软等一些信息巨头也加入了无线传感器网络研究领域。 美国自然科学基金委员会制定无线传感器网络研究计划，资助加州大学洛杉矶 分校、加州大学伯克利分校、南加州大学等展开无线传感器网络基础理论及相 关技术的研究。与此同时，日本、韩国、英国、意大利、巴西等国家也对传感 器网络也表现出了极大的兴趣，纷纷展丌了该领域的研究工作。 在一份有关我们国家未来2 0 年预见技术的调查报告中，信息领域1 5 7 项技 术课题中有7 项与传感器网络直接相关。2 0 0 6 年初发布的国家中长期科学与 技术发展舰划纲要为信息技术确定了三个自仃沿方向，其中两个与无线传感器 网络研究直接相关，即智能感知技术和自组织网络技术，可以看出对无线传感 器网络的重视程度。我国的中科院软件所、计算所等科研机构，清华大学、北 京邮电大学、华中科技大学等院校在国内较早的开展了无线传感器网络的研究， 现在越来越多的科研院校都加入到了这一研究工作中来。 目前，国内外学者对分簇算法进行了广泛的研究。研究的问题主要集中于 三个方面。首先是簇头选举方法的研究，如文献【3 j 等，在这类分簇算法中采用某 种簇头选择机制使得簇内节点轮流当选为簇头，来延长网络生命周期。根据簇 头产生的方式不同，可以把簇头选举算法分为分布式和集中式两种。分布式算 法完全由节点自主决定是否当选为簇头，不需要基站的控制和整个网络信息的 收集。集中式算法是由基站基于收集到的整个网络的信息来选择簇头；其次是 对分簇结构的研究，如文献【4 】等，采用一定的分簇方法使得分簇结构更加合理， 2 武汉理工大学硕士学位论文 整个网络能耗平衡，进而延长网络生命周期。主要包括两类：均匀分簇结构和 非均匀分簇结构。均匀分簇结构是将整个网络划分为规模相同的簇。非均匀分 簇结构从均衡各簇头的能耗考虑，使距离基站近的节点簇规模比较小，距离基 站远的簇规模比较大，来使靠近基站的簇头能够留出更多的能量来参与数据转 发；第三方面是数据传输方案的研究，如文献【5 1 等，在这些分簇算法中，通过构 建合理的簇内和簇间的结构，缩短传输距离，节约网络能耗。国内对无线传感 器网络分簇算法研究起步较晚，大多是对国外经典分簇算法的某一方面的改进， 却往往忽视了其他方面的性能。关于无线传感器网络分簇算法的研究还不成熟， 存在着许多需要改进的地方。 1 3 主要研究内容 因为无线传感器网络由大量低成本的微型节点组成，能量、带宽、计算、 存储等资源非常有限。如何有效管理和使用这些资源，最大限度地延长网络生 命寿命是无线传感器网络研究所面临的一个关键技术挑战。低功耗几乎成了目 前无线传感器网络研究的一个核心，低功耗的m a c 协议、路由协议、传输协议， 甚至在操作系统中也强调低功耗设计。在无线传感器网络大部分的应用中，如 何降低系统功耗，延长网络生命周期是一个非常关键的问题。 本文所研究的内容也是关于如何使整个网络能量高效、最大化网络生命周 期。将网络分簇是降低能耗、延长网络生命周期的一个非常重要的方法1 6 j 。分簇 不仅可以提高网络的可扩展性，而且将整个网络划分为簇可以避免信道冲突， 有效提高信道的利用率。同样避免了每个节点都与基站通信带来的巨大的能量 丌销，代之以普通节点只需要与簇头节点进行通信，这在无线传感器网络中数 据通信占能耗的绝大部分来说，可以明显的减少能量消耗。 虽然将网络分簇有着诸多的优点，但是同样也带来一些问题比如能耗不平 衡的问题。在多层分簇的网络中，传感器节点将收集的数据传送给簇头，簇头 将数据通过其它簇头中转发送到基站。簇头之间的多跳通信使得离基站近的簇 头不仅要承担本簇内的数掘收集工作，还要处理来自其它簇头的转发数据，造 成这些节点能量过早的耗尽，因此离基站近的节点能量消耗就快，造成整个网 络生命周期过早的结束。在解决能耗平衡问题的分簇算法中，很少有算法来考 虑这个问题，整个网络寿命受到很大的局限。本文针对多层分簇算法中存在的 武汉理丁大学硕+ 学位论文 能耗不平衡的问题，提出一个形成不同规模的簇算法e b c a ( e n e r g yb a l a n c e c l u s t e r i n ga l g o r i t h m s ) ，让离基站近的簇头可以更多的参与数据转发，来平衡整 个网络的能耗，避免离基站近的簇头过早的耗尽能量。仿真结果显示，本文提 出的的算法有效的解决了热点问题，使整个网络的负载更加平衡。 1 4 本文的组织结构 本文共分为六章： 第l 章：绪论，介绍本课题的研究背景，分析国内外无线传感器网络的研 究现状及主要问题，提出本文的研究内容。 第2 章：无线传感器网络概述，介绍无线传感器网络的基本概念，包括无 线传感器网络的体系结构、特征和能耗问题。 第3 章：无线传感器网络分簇算法概述，介绍了分簇算法的概念、模型、 目标以及一些典型的分簇算法。 第4 章：基于能耗平衡的无线传感器网络分簇算法，提出了e b c a 分簇算 法，介绍了算法的网络模型、算法描述以及算法分析。 第5 章：实验和仿真，通过对比三种无线传感器网络的仿真平台，选择了 o m n e t + + 平台做仿真实验，介绍了e b c a 算法仿真场景设置和实验结果分析。 第6 章：总结与展望，在本论文主要工作总结的基础上，对下一步的工作 提出了展望。 4 武汉理工大学硕士学位论文 第2 章无线传感器网络概述 2 1 无线传感器网络体系结构 2 1 1 无线传感器网络的网络结构 图2 1 给出了无线传感器网络典型的网络结构，通常包括传感器节点( s e n s o r n o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点( m a n a g e rn o d e ) 。 图2 1 无线传感器网络的系统架构【7 1 大量传感器节点随机密布于整个监测区域中，通过自组织的方式构成网络。 传感器节点监测到信息后，以多跳中继的方式将监测到的数据传送给汇聚节点， 然后通过互联网或者卫星等途径最终到达用户的管理节剧引。 传感器节点处理能力、存储能力和通信能力相对较弱，通常只与自身通信 范围内的邻居节点交换数据。要访问通信范围以外的节点，必须使用多跳路由【9 1 。 从网络功能上来看，每个传感器节点除了进行本地信息收集和数据处理之外， 还要存储、管理和融合其他节点转发过来的数据，同时与其他节点协作完成一 些特定任务。 汇聚节点通常具有较强的处理能力、存储能力和通信能力。它连接传感器 网络与i n t e r n e t 等外部网络，通过两种协议栈之间的通信协议的转换实现管理节 点与传感器网络之间的通信【l o 】。 武汉理工大学硕+ 学位论文 2 1 2 无线传感器网络通信协议 无线传感器网络通信协议主要包括物理层、数据链路层、网络层、传输层 和应用层。无线传感器网络的物理层负责信号的调制和数据的收发，所采用的 传输介质主要有无线电、红外线、光波等【1 1 】。在传感器网络中，主要的挑战性 工作是确定调制方式和收发机的体系结构，使之具有简单、低成本的特性，并 且能够提供所需要的足够稳健的服务。物理层处于最底层，是整个开放系统的 基础，它的设计对以上各层的跨层优化设计都有重要影响，而跨层优化设计是 无线传感器网络协议研究的主要内容。同时，在整个协议栈中，物理层与硬件 的关联最为密切。 无线传感器网络的数据链路层负责数据成i 帧、帧检测、媒体访问和差错控 制i l2 | 。其中媒体访问协议保证可靠的点对点和点对多点通信；差错控制则保证 源节点发出的信息可以完整无误地到达目标节点。数据链路层研究的重点是介 质访问控制( m e d i a a c c e s sc o n t r o l ，m a c ) 协议，因为它要靠大量节点协同工作 实现某种特定的目标。无线传感器网络的m a c 协议的基本任务是节点共享网络 媒体的接入问题，通常要保证某些特定的性能或应用相关的性能得到满足，例 如，延迟、吞吐量和公平性等。 无线传感器网络的网络层负责路由发现和维护，通常大多数节点无法直接 与网关通信，需要通过中间节点以多跳路由的方式将数据传送至汇聚节点【1 3 】。 其路由协议包括了两个方面的基本功能：一个是路径选择，即寻找源节点和目 的节点间的优化路径；另一个功能是数据转发，即要将数据沿优化路径正确转 发。设计无线传感器网络路由协议需要满足能量高效、减少冗余信息、可扩展 和鲁棒性等要求。 2 2 无线传感器网络的特征 2 2 1 无线传感器网络节点的限制 ( 1 ) 电源能量受限 无线传感器网络的节点体积微小，一般携带能量十分有限的电池，且更换 电池不切实际，所以节点能量受限是整个无线传感器网络设计最关键的约束之 一，直接决定了整个网络的生命周期。 6 武汉理t 大学硕十学位论文 ( 2 ) 通信能力有限 无线通信的能量消耗e 与通信距离d 的关系为e = k d 门，其中参数，2 满足关系 2 n 4 。通常取n 为3 ，即通信能耗与距离的三次方成正比【1 4 l 。随着通信距离的 增加，能耗将成指数级急剧增加。 ( 3 ) 计算和存储能力有限 传感器节点装备了存储器和处理器，体积小、价格低廉和低功耗的要求的 限制导致其携带的处理器能力比较弱，存储器容量比较小，使其不能进行复杂 的计算处理【1 5 】。 2 2 2 无线传感器网络的特点 无线传感器网络与a d h o e 网络有一些相似之处，比如分布式、自组织、拓 扑变化、多跳路由和安全性差方面。除此之外，无线传感器网络还具有以下一 些区别于a d h o c 网络的独有特点： ( 1 ) 规模大、密度高。为了获得尽可能精确的信息，无线传感器网络通常 大量密集的部署在监测区域中，它通过大量冗余节点来保证对监测区域的完全 覆盖，完成整个区域的监测任务。 ( 2 ) 以数据为中心。无线传感器网络与传统的互联网以地址为中心的网络 不同，它是一个以数据为中心的网络。在无线传感器网络中，人们只关心某个 区域的事件或者观测数据，而不关一1 1 , 是那个节点获得的信息【l6 1 。 ( 3 ) 应用相关。无线传感器网络通过节点感知客观世界来获得外界信息。 不同的应用关心不同的数据指标以及信息，因而对整个网络的要求也不相同。 其部署策略、系统要求、通信协议、硬件平台都会有巨大的不同。只有针对具 体的应用来设计网络才可以实现高效、可靠的系统目标。 ( 4 ) 可靠性。无线传感器网络大规模的部署在环境恶劣的无人区域，节点 往往工作在无人值守的状态下，网络和节点的维护变的十分困难。这要求节点 非常坚固、不易损坏，适应各种恶劣环境。无线传感器网络的通信安全现在也 显得非常重要，因此需要传感器节点必须具有较好的鲁棒性和容错性【1 7 】。 7 武汉理工大学硕士学位论文 2 3 无线传感器网络的厶匕f i t ；耗问题 2 3 1 节点能量消耗 节点的功耗主要分布在三个方面：感知、通信和数据处理。感知功耗随着 应用的不同而不同，间歇性信息感知比持续的事物监测消耗的功率要少。事物 监测的复杂程度也在决定功率的消耗当中起着比较重要的作用【1 8 】。在这三个方 面当中，传感器节点在数据通信方面消耗的功率最大，如图2 2 所示。这包括数 据发送和接收能耗。在近距离低发射功率的情况下，发送功耗和接收功耗几乎 相同。在无线收发电路里不仅仅要考虑活动状态的功率消耗也要考虑启动状态 的功率消耗。节点的无线通信单元存在发送、接收、空闲和休h 民四种状态，在 不同的状态有不同的能量消耗【1 9 】。 传感器网络无效功耗损耗的来源主要来自以下4 个方面：( 1 ) 如果m a c 协 议采用竞争方式使用共享的无线信道，节点在发送数据的过程中，可能会引起 多个节点之间发送的数据碰撞。这就需要重传发送的数据，从而消耗节点更多 的能量；( 2 ) 节点接收并处理不相关的数据。这种串音现象造成节点的无线接收 模块和处理器模块消耗更多的能量；( 3 ) 节点在不需要发送数据时，一直保持对 无线信道的空闲侦听，以便接收可能传输给自己的数据。这种过度的空闲侦听 同样会造成节点能量的浪费；( 4 ) 在控制节点之间的信道分配时，如果控制信息 过多，也会消耗较多的网络能量1 2 0 】。 2 3 2 节能策略 2 0 1 5 葛 1 0 2 叶 5 0 ， j 辔信 、 瓣 ，每 厂 厂 f 岔 蘸躐r 犋僖性胛 2 董 萎“、+ 嘲y 图2 - 2 传感器节点能量消耗模型【9 】 8 武汉理工大学硕士学位论文 处理器模块的节能策略主要有一下两种： ( 1 ) 动态功率管理( d y n a m i cp o w e rm a n a g e m e n t d p m ) 动态电源管理的工作原理是，当节点周围没有感兴趣事件发生时，部分模 块处于空闲状态，把这些组件关掉或调到更低能耗状态( 即休眠状态) ，这种事件 驱动能量管理对于提高传感器节点的生存期非常重要。 ( 2 ) 动态电压调节( d y n a m i cv o l t a g es c a l i n g ，d v s ) 动态电压调节的工作原理是，当计算负载较低时，通过降低处理器的工作 电压和操作频率从而降低处理能力，可以节约处理器的功耗。动态电压调节目 标是调节处理器功率和操作频率与工作负载相适应【2 。 通信模块节能方法主要有减少通信流量、采用多跳通信、增加休眠时间等 方法。通过减少通信模块发送和接收的比特数，能降低通信模块的能耗。减少 通信流量的方法有以下几种：( a ) 本地计算和数据融合；( b ) 减少冲突；( c ) 增加错 误检测和校正机制；( d ) 减少控制包的开销和包头长度1 2 2 1 。 2 4 本章小结 在本章中，主要介绍了无线传感器网络方面的基本概念。首先对无线传感 器网络的体系结构进行了描述，详细阐述了网络结构、通信协议。接着对无线 传感器网络的特点进行了叙述，其低功耗、大规模、以数据为中心和应用相关 的特点使得无线传感器网络不同于传统的a d h o c 网络，因此对无线传感器网络 的研究也必须要考虑其自身的这些特点及限制，是现在研究当中面临的挑战。 最后对无线传感器网络最核心的能耗问题以及如何提高能量效率做了重点介 绍。 9 武汉理工大学硕士学位论文 第3 章无线传感器网络分簇算法 3 1 分簇算法概述 无线传感器网络在实际当中应用的范围很广，潜能也很大。然而值得注意 的是在现实应用当中，无线传感器网络的能量高效运行一个非常关键的问题。 无线传感器网络一般部署在无人值守、环境恶劣的地方，由飞机部署大量的节 点，这种实际应用的限制导致节点都是装配不可充电的电池，重新更换电池也 是不切实际的。为了延长无线传感器网络的生命周期，现在研究当中一个普遍 的方法是采用传感器节点的工作和休眠周期的动态调度。此外，采取基于分簇 ( c l u s t e r - b a s e d ) 的网络，使用选择一个簇头( c l u s t e rh e a d ) 的方法来最小化总 的能量消耗，网络中的传感器可以轮换担当簇头的角色，以平衡能耗【2 3 1 。 尽管a d h o e 网络中已经提出很多分簇算法，但是它们的目标主要是在移动 节点如何生成稳定的簇。大部分算法都是主要考虑节点的可达到性和路由的稳 定性，而没有考虑无线传感器网络的网络生命周期和覆盖这两个关键设计目标。 分簇算法的分簇策略随着部署策略和网络结构配置等的不同而变化。一个簇头 可能由簇中节点选举产生或者预先指定。簇头可能是节点其中之一或者是具有 充足能量的节点，簇头是固定的或者可以变化的，簇内节点将收集的信息发，给 簇头，簇头收集簇内信息经过数据融合将数据发送给基站。簇头可能形成第二 级的网络也可能仅仅将数据传送到目的地比如基站或者指挥中心。图3 1 展示了 这利，多层分簇的体系结构。 研究人员一般都把传感器节点分簇来达到网络可扩展性的目标。在支持网 络可扩展性方面，分簇有很多优点。路由建立在簇内降低了单个节点的路由表 的规模；保证通信带宽，因为限制了簇内节点和簇头的交互的范围，避免了节 点之间冗余的信息交换；分簇可以使网络拓扑稳定，从而减少了拓扑保持丌销， 普通节点只需要考虑与簇头之间的连接通信，不受簇头之间通信状态改变的影 响；簇头可以执行最优管理策略束增强网络操作性、延长单个节点电池的寿命 和网络的生命周期：簇头可以调度簇内节点在大部分时间内进入低功耗的休眠 状态来降低能耗，同时，降低了覆盖冗余度和避免了信道的冲突；另外，簇头 1 0 武汉理工大学硕士学位论文 可以对收集的簇内的数据进行数据融合，减少了数据报转发的数目，降低了能 量的消耗。 图3 1 一种多层分簇的体系结构3 7 】 文献上发表了各种各样的分簇算法，不同的算法经常有不同的假设，主要 是因为它们是在不同的应用背景下考虑的。这些设计假设包括( 但并非仅限于 此) ：探测模型、传感区域、传输范围、失效模型、时间同步、位置和距离信息 等。关于网络结构和传感器节点部署策略也有不同的假设。 3 2 簇的网络模型 针对无线传感器网络不同方面的应用，网络的体系结构、设计目标和限制 都有着相应的变化。以下所列的参数使网络分簇的意义更加突出： ( 1 ) 网络动态：无线传感器网络主要由三个部分组成：传感器节点、基站 和被检测事件。绝大部分都假设节点是静止的。在某些应用中，基站或者簇头 是需要移动的。节点的移动对簇的形成带来挑战，簇需要动态变化。另外，监 测任务可以是问歇的或者持续的，这是由具体应用所决定的。监测问歇任务允 许网络工作在被动模式，仅仅在事件发生时才触发数据收集和传输。在大部分 的应用中，持续的事件需要周期性的报告，因此需要有一条稳定的路径将信息 传送到基站。持续性的事件监测使簇比较稳定，但会使簇内的负载不平衡。 武汉理工人学硕+ 学位论文 ( 2 ) 网内数据处理：簇内相邻节点采集的信息往往存在冗余，如果簇头节 点不对收集到的数据进行数据处理，直接将收集到的数据转发给基站，大量重 复冗余数据的传输不仅会浪费通信带宽，而且会使整个网络消耗过多的能量， 降低网络寿命。簇头从簇内节点收集数据的过程中，利用自身的计算和存储能 力处理数据，去除冗余数据，尽量减少数据传输量；同时将来自不同节点的多 份数据结合起来，提取或综合出较单个节点数据采集更为有效、准确的数据信 息，最终达到精确感知目标信号，降低能耗，延长网络生命周期的目的。簇头 不仅担负数据收集的职责，还担负着对收集到的数据进行数据融合的任务。这 限制了对簇头的选择，可能仅仅将簇头的选择限制在一些具有充足能量的特殊 节点上来确保簇头可以完成所需的任务。同时，也可以通过对簇头的节点的轮 转来平衡整个簇的能耗。很明显，这些限制影向了分簇策略。 ( 3 ) 节点部署和性能：节点部署策略的不同也对分簇算法有着重要的影响。 节点部署位置可以是预先指定好或由飞机在监测区域上空随机抛洒的。在节点 位置预先指定好的情况下，节点通过手工放置，数据沿着特定的路径传送到基 站，此时簇也可以被预先分配好或者不进行分簇。在节点被随机部署的情况下， 基站和簇头的位置对能耗和性能的影响非常关键。当节点分布不均匀时，寻找 最优簇成为一个关键问题。在同构无线传感器网络中，即网络中所有节点都一 样，所有节点都有一样的计算能力、通信能力和能量，簇头从部署的节点中选 取。在这种情况下，为了避免簇头能量很快耗尽，簇头仅被赋予特殊的职责， 而不进行感知任务。另外，节点的通信范围和簇头与基站的距离也是需要考虑 的因素。节点的通信范围是有限的，因此有些簇头不能和基站直接通信，即使 一个节点可以直接和基站进行通信，但是最好还是使用多跳路由。因此簇头之 间的通信成为影响分簇策略的一个重要因素。还有，异构传感器节点对簇处理 施加了更多的限制，些节点被指派执行特殊的任务或者有独特的功能，需要 这样特殊的节点保持能量或者将簇头的选择范围在这些节点内。 3 3 分簇算法的设计假设 所有的被凋研的分簇算法都有着下列共同的假设：( 1 ) 每个传感器都有着 有限的能量供应；( 2 ) 传感器网络需要运行很长的时间。以下讨论不同的设计 假设，这些假设反应了不同的网络结构、传感器部署策略和传感器性能。 1 2 武汉理工大学硕士学位论文 ( 1 ) 网络结构：一个传感器网络可以是不分层的，在这种意义上来说，每 个传感器节点都有相同的角色和职能。同时，它也可以是分层的，例如为探测 和跟踪设计的传感器网络，一些传感器被指定为数据融合中心来收集邻近的节 点发出的信息，决定一个物体是否被探测到，并且发送信息到基站。这些网络 是基于簇的，簇头比其它传感器有一个更显著的地位。 ( 2 ) 节点部署策略：许多被调研的算法假设传感器是随机和均匀的分布监 控区域。一些算法虽然没有明显的说出此种假设，但是当持有这种假设的时候 它的性能是最好的。一些文章中对监控区域中的节点分布使用二维泊松分布。 另外，一少部分算法认为所有的节点形成了一个网格。绝大部分被调研的算法 都认为在网络中存在一些冗余的节点，这些传感器可以关闭。文献1 2 4 】中明确的 假设传感器的总的数目远远高于工作着的传感器的数目几个数量级，这样的密 度级是高的。如果两个数目对比是在一个数量级上，则密度是正常的。 ( 3 ) 探测模型：大部分算法都假设只要物体在节点的感知范围之内节点能 够探测到这个物体，也就是说这个探测模型是确定的。然而，一个值得注意的 例外就是在文献【2 5 】中它使用一个概率探测模型，一个物体被探测到的概率是这 个物体和传感器之间的距离的函数。 ( 4 ) 感知区域：经常假设感知区域为一个圆形区域或者一个3 d 球体，此 外，假设节点都有着相同的感知区域。有很多算法将感知区域扩展到凸形区域 和一些不规则的区域。 ( 5 ) 传输范围：很多算法假设一个节点的无线收发机可以改变传输功率等 级，通过一些操作来达到不同的传输功率。一些节点比如m i c a 2m o t e 提供了一 个多级的传输功率。然而，特定的功率级别下实际的传输范围也肯能受其它外 部冈素影响，比如节点所在地的高度和周罔的环境。 ( 6 ) 时间同步：许多算法都假设节点是时间同步的，因此它们能同时被唤 醒丌始新一轮的调度。 ( 7 ) 失效模型：“节点怎么样会失效 是一个非常重要的假设。所有的被 调研的算法假设当电池的能量耗尽节点就会失效。许多分簇算法比如文献【2 4j 中 进一步假设在电池耗尽之前会出乎意料的失灵，例如节点当部署在军事战场的 时候，有可能被坦克破坏。 ( 8 ) 节点机动性：所有的被调研的算法要不就是明显的假设传感器网络是 静态的，要么就对于机动性方面不做假设。事实上，大部分文献【2 6 】认为绝大部 武汉理工大学硕士学位论文 分现实世界的传感器网络包含很少或者没有机动性。 ( 9 ) 位置信息：现有算法当中许多都假设节点自身能确定它的地理位置， 这个位置信息经常用来确定一个节点的感知区域是否和其邻近节点重叠。如果 每个节点的位置是事先确定的并且节点不移动，此时，在节点被部署之前，位 置信息可以硬编码进传感器中。否则，节点则需要装配g p s 设备或者运行一个 定位算法比如文献1 2 7 j 所提。 ( 1 0 ) 距离信息：文献【2 8 】【2 9 】都假设在基于分簇的传感器网络中节点能确定 到它们的簇头的距离。距离信息可以通过相应的位置信息来获得，反之不行。 另外，距离信息也可由接收信号的强弱推断出来。 3 4 分簇算法的基本目标 在不同的应用需求当中，无线传感器网络就有着不同的设计目标或者在这 些目标当中有着不同的优先权。最大化网络寿命在传感器网络当中理所当然的 成为最重要的设计目标，因为传感器需要很长的运行时间。然而，一个传感器 网络的建立就是为了达到某种任务，例如执行感知和传输数据的任务。 因此一种或者多种的服务质量的目标比如说保持监测覆盖区域经常随着最小化 能耗一起考虑。此外，一个设计也可能要考虑许多高级目标比如健壮性、可扩 展性和简单性。文献中分簇算法的目标都各有不同，分簇算法目标一般都是为 了方便的满足应用需要。例如如果一个应用对数据时延是敏感的，簇内和簇间 的连通性、数据路由路径的长度被作为选择簇头和节点分组的标准。分簇算法 普遍的目标有如下几个方面： ( 1 ) 负载平衡：由于簇头担负着数据收集、处理和转发的任务，比簇内普 通节点负载大，要想达到性能的目标，就必须要平衡簇节点之间的能耗，否则 簇头节点将会过早的耗尽能量，使整个簇无法继续工作。因此，分簇算法首要 考虑的目标是，如何使簇内的能耗平衡。当簇头节点是从簇内选举出来时，这 一问题更为关键。在这种情况下，设置相同规模的簇成为延长网络生命周期的 关键，同时簇头节点由簇内节点轮转担任。 ( 2 ) 容错：在许多应用当中，无线传感器网络应用在恶劣的环境下，传感 器节点容易遭受故障和物理破坏。在这种情况下，为了避免丢失重要的感知数 据，容忍簇头节点的失效是必须的。从一个簇头失效中恢复的一般方法是对网 1 4 武汉理工大学硕士学位论文 络簇的重组。然而，重新组簇对节点来说耗费很多能量。因此，现在容错技术 需要考虑这些问题。针对簇头失效问题，配置备份簇头是现在大量文献中采取 的对簇重新恢复的办法。 ( 3 ) 最小簇数目：当簇头节点是特殊的、能量充足时，此目标就比较普遍。 这样的节点比一般节点要贵很多和易受攻击，分簇算法设计者都想尽量少使用 这样的特殊节点，因此要将整个网络分簇的数目最小化。此外，这种特殊节点 可能是笔记本电脑、机器人或者移动的车辆，体积比一般节点要大很多。在很 多具体应用比如军事应用中，节点需要尽量好的隐蔽性，因此需要尽量少用这 样的节点。 ( 4 ) 最大化网络生命周期：因为传感器节点都是能量有限的，网络的生命 周期是一个关键问题，尤其是无线传感器网络应用在恶劣的环境当中时。当簇 头节点比一般节点有充足的能量时，需要考虑使簇内通信的能量消耗最小化， 一个常用办法就是让簇头距离每个簇内节点最近。另一方面，簇头和其他簇内 节点一样具有相同的能量，簇头可以通过轮转等方式来延长生命周期。在簇形 成和路由建立时也需要考虑最大化网络生命周期。自适应簇在这方面比较有优 势。网络生命周期的定义各种各样，因此选择一利咱邑量高效的分簇算法只能最 大化某一类型的网络生命周期。最简单的一种情况就是只要网络中的一个传感 器节点能量耗尽，整个网络的生命周期就到此为止。网络生命周期也可以按从 开始到当一定百分比的传感器的能量耗尽低于某个阈值( 比如9 0 ) 的持续时 间。此外，一种或多种服务质量的量度可以被考虑进去即一个网络被认为是起 作用的当且仅当它的传感区域( 或者连同程度、数据传输率) 高于某个阈值的 时候。 3 5 分簇算法研究 3 5 1l e a c h 算法 - l e a c h ( l o w e n e r g 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 ) 【3 0 1 算法是一种自适应 分簇算法。它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数 据通信阶段。在簇的建立阶段，相邻节点动念的形成簇，随机产生簇头；在数 据通信阶段，簇内节点把数据发送给簇头，簇头进行数据融合并把节点发送给 武汉理_ t 大学硕十学位论文 汇聚节点。由于簇头节点需要完成数据收集、数据融合、与汇聚节点进行通信 等工作，所以能量消耗大。l e a c h 算法能够保证各节点等概率地担任簇头，使 得网络中的节点相对均衡的消耗能量。 簇头节点的选取是l e a c h 算法的关键，具体选举簇头的过程如下：节点产 生一个0 1 之间的随机数，如果这个数小于阈值t ( n ) ，则发布自己是簇头的公 告信息。在每轮循环中，如果节点已经当选过簇头，则把t ( n ) 设置为0 ，这 样该节点不会再次当选为簇头。对于未当选过簇头的节点，则将以t ( n ) 的概率 当选；随着当选过的簇头的节点的数目的增加，剩余节点当选簇头的阈值t ( n ) 随之增大，节点产生小于t ( n ) 的随机数的概率随之增大，所以节点当选簇头 的概率增大。当只剩下一个节点未当选时，t ( n ) = l ，表示这个节点一定当选。 t ( n ) 可表示为 丁- 南支i 邗 公式( 3 1 ) 其中，p 是簇头在所有节点中所占的百分比，r 是选举轮数，r m o d ( 1 p ) 代表这一 轮循环中当选过簇头的节点个数，g 是这一轮循环中未当选过的簇头的节点集 厶 口。 节点当选簇头之后，发布通告消息告知其它节点自己是新簇头。非簇头节 点根据自己与簇头之间的距离来选择加入哪个簇。在每一个节点决定加入哪个 簇之后，必须通知这个簇的簇头，每一个节点传输这一信息给簇头，使用一个 c s m a m a c 协议。在这一阶段，所有的簇头都必须保持接收机是开的。簇头基 于簇内节点的数目，创建一个t d m a 调度告诉每个节点何时可以发送数据，一 旦簇建立并且t d m a 调度固定，数据传输丌始。假设节点一直有数据传输，它 们在分配到的时间段内传送数据给簇头。每一个非簇头节点在没有轮到发送数 据时都关闭无线收发机，这样可以减少能耗。簇头则一直保持无线收发机在丌 的状态，来接收非簇头节点传来的数据。当所有的数据接收完毕之后，簇头则 开始进行数据融合，并将结果直接发送给汇聚节点。 总之，l e a c h 算法通过使传感器和簇头之问的