（应用数学专业论文）无线传感器网络分簇路由协议的研究与设计.pdf

河南大学研究生硕士学位论第1 页 摘要 无线传感器网络是一种能够实时监测、感知、采集和处理各种监测对象信息的 新型网络，作为目前的研究热点在国际上备受关注，其在军事、环境监测和工业 生产等方面的应用前景广阔。但是与传统无线网络相比，也存在各方面的限制， 如节点众多不易管理、节点能量、存储能力有限等，在该类网络中，能量有效是 首要问题，在进行无线传感器网络路由协议的研究和设计时，应以有效的利用能 量，均衡节点能耗，延长网络生存时间为首要目标。 论文在对无线传感器网络路由协议研究基础上，指出分簇路由协议的优势所 在，并且对经典及最新分簇路由协议进行分析总结，最后根据其特点及需求设计 出了新的能量有效的分簇路由协议e e c r p ( e n e r g ye f f i c i e n tc l u s t e r i n gr o u t i n g p r o t o c 0 1 ) 。 本文主要工作如下： 1 对路由协议中的平面路由和分簇路由在性能和特点等方面进行对比分析， 从而得出分簇路由协议的优势所在。 2 对现有分簇路由协议的工作机制进行深入研究，主要对分簇路由协议 l e a c h ，h e e d 与c p r e 等进行详细分析，总结出其优势与存在的缺陷， 并针对缺陷提出改进方案。 3 根据改进方案设计出了一种新的能量有效的分簇路由协议e e c r p 。e e c r p 首先确定簇首数目与簇半径，然后根据节点的剩余能量与节点相对位置选 择簇首：成簇时综合考虑簇首剩余能量与信号强度；在簇间构建最小跳数 动态路由；最后在能量有效的前提下对l e a c h 协议易受到h e l l of l o o d i n g 攻击提出了安全设想。 4 。使用o m n e t - 卜+ 仿真工具对几种协议进行仿真验证。仿真结果表明：e e c r p 在簇首的分布状态、网络负载平衡、网络生存时间、网络能耗与抽样时刻 第1 i 页河南大学研究生硕士学位论文 网络采集数据量各方面性能有了一定提高。 关键词：无线传感器网络：分簇路由；能量有效；e e c r p ；最小跳数路由 河南大学研究生硕士学位论文第1 1 i 页 a bs t r a c t w i r e l e s ss e n s o rn e t w o r k si san e wt y p eo fn e t w o r k ，i tc o u l dr e a l - t i m em o n i t o r , s e n s e ，c o l l e c t ，a n dp r o c e s st h ei n f o r m a t i o no ft h ev a r i o u sd e t e c t e do b j e c t s a sah o ts p o t w h i c hh a sa t t r a c t e di n t e r n a t i o n a la t t e n t i o n ，i th a sav e r yb r o a da p p l i c a t i o np r o s p e c t so n t h em i l i t a r ya f f a i r s ，e n v i r o n m e n t a l m o n i t o r i n g ，i n d u s t r i a lp r o d u c t i o na n ds oo n b u t c o m p a r e dw i t ht r a d i t i o n a lw i r e l e s sn e t w o r k s ，t h e r ea r ev a r i o u sc o n s t r a i n t s ，s u c ha s ：t h e n u m b e ro fn o d e si s l a r g e ，d i f f i c u l tt om a n a g e ，n o d ee n e r g ya n ds t o r a g ec a p a c i t ya r e l i m i t e d ，i ns u c hn e t w o r k s ，e n e r g ye f f i c i e n ti st h em o s ti m p o r t a n ti s s u e s ，h o wt o e f f e c t i v e l ym a k eu s eo fn o d ee n e r g y , b a l a n c et h en o d ee n e r g yc o n s u m p t i o na n dp r o l o n g t h en e t w o r kl i f e t i m ei st h ep r i m a r yo b j e c t i v ew h e nr e s e a r c h i n ga n dd e s i g n i n gt h e w i r e l e s ss e n s o rn e t w o r k sr o u t i n gp r o t o c 0 1 t h ep a p e rp o i n t so u tt h ea d v a n t a g e so fc l u s t e r i n gr o u t i n gp r o t o c o l ，a n a l y s e sa n d s u m su pt h ec l a s s i c a la n dt h el a t e s tc l u s t e r i n gr o u t i n gp r o t o c o l sb a s e do nt h er e s e a r c ho f t h er o u t i n gp r o t o c o lf o rw i r e l e s ss e n s o rn e t w o r k s ，f m a l l ya c c o r d i n gt ot h ec h a r a c t e r i s t i c s a n dn e e d st od e s i g nt h en e we n e r g ye f f i c i e n tc l u s t e r i n gr o u t i n gp r o t o c o le e c r p i nt h i sp a p e r , t h em a i nw o r ki sa sf o l l o w ： f i r s t ，a f t e rc o m p a r i n ga n da n a l y z i n gt h ep e r f o r m a n c ea n dc h a r a c t e r i s t i c so ff i a ta n d c l u s t e r i n gr o u t i n gp r o t o c o l s ，t h ea d v a n t a g e so fc l u s t e r i n gr o u t i n gp r o t o c o la r ep o i n t e d o u tb yp a p e r s e c o n d , t h ew o r k i n gm e c h a n i s mo fe x i s t i n gc l u s t e r i n gr o u t i n gp r o t o c o l sa r ed e e p l y r e s e a r c h e d , t h ep a p e rd e t a i l e da n a l y s e st h ec l u s t e r i n gr o u t i n gp r o t o c o l s ，s u c ha s ：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 , h y b r i de n e r g y e f f i c i e n td i s t r i b u t e dc l u s t e r i n g ， c l u s t e r i n gp r o t o c o lb a s e do nr e s i d u a le n e r g y , a n ds u m su pt h ea d v a n t a g e sa n d d i s a d v a n t a g e s ，b a s e do nt h ed i s a d v a n t a g e st op r o p o s et h ei m p r o v e m e n tp r o g r a m t h i r d , t h ep a p e rd e s i g n san e we n e r g ye f f i c i e n tc l u s t e r i n gr o u t i n gp r o t o c o le e c r p b a s e do nt h ei m p r o v e m e n t p r o g r a m e e c r pd e t e r m i n e st h en u m b e ro fc l u s t e rh e a d sa n d t h er a d i u so fc l u s t e rf w s t l y , t h e ns e l e c tc l u s t e rh e a da c c o r d i n gt ot h er e s i d u a le n e r g yo f 第1v 页河南大学研究生硕士学位论文 e a c hn o d ea n dt h er e l a t i v ep o s i t i o n so fn o d e s ；i na c c o r d a n c ew i t ht h es i g n a lp o w e ra n d t h er e s i d u a le n e r g yo fc l u s t e rh e a dt of o r mc l u s t e r ；f o r mt h em i n i m u mh o pd y n a m i c r o u t i n ga m o n gc l u s t e rh e a d s ；f i n a l l y , u n d e rt h ep r e m i s eo ft h ee n e r g ye f f i c i e n tt h ep a p e r p u tf o r w a r ds e c u r i t yi d e ab a s e do nt h el e a c hp r o t o c o li se a s i l ya t t a c k e db yh e l l o f l o o d i n g f o u r t h ，m a k es i m u l a t i o nv e r i f i c a t i o nf o rp r o t o c o l sw i t hs i m u l a t i o nt o o lo m n e t + + s i m u l a t i o nr e s u l t ss h o wt h a t ：t h ep e r f o r m a n c eo fe e c r pi nt h ed i s t r i b u t i o no fc l u s t e r h e a d s ，n e t w o r kl i f e t i m e ，n e t w o r ke n e r g yc o n s u m p t i o na n dt h ea m o u n to fd a t ag a t h e r e d b yn e t w o r kh a v eb e e ni m p r o v e d k e y w 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 i n gr o u t i n g ；e n e r g ye f f i c i e n t ；e n e r g y e f f i c i e n tc l u s t e r i n gr o u t i n gp r o t o c o l ；m i n i m u m - h o pr o u t i n g 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过酌研元成果，也不包括其他人为获得任何教育、科研机构酌学位或证书而 使用过的材料。与我一同工作的同事对苯研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 釜名：垂垄垄 2 0 叼年6 月7 日 关于学位论文著作权使用授权书 本人经河南大学审核批准授子硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保管、使用学位论克酌要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、奎溷。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的。，可以采取影印j 缩印、扫描和拷贝等复制手 段保存、汇编学住论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学住论文作者) 签名：垂垄妾 2 0 77 年多月f 目 学位论文指导教师签名： 2 0年 月 日 河南大学研究生硕士学位论文第1 页 第l 章绪论 本章主要介绍论文的选题背景、国内外研究现状与研究内容。 1 1 选题背景 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，w s n ) 是由许多廉价、低功耗的 微型传感器节点通过无线通信方式自组织而成的新型网络，网络中的节点功能多、 能耗低，随着各种技术的发展其功能也有了很大进展，可以在很小的传感器节点 内集成数据收集、处理与无线通信等多种功能，大量多功能微型节点的使用增强 了无线传感器网络的功能与应用价值，引起了世界范围内的广泛关注【1 卅。 无线传感器网络与传统网络不同，它综合了传感器技术、嵌入式计算技术、分 布式信息处理技术和无线通信技术等多项前沿技术，主要作用是通过不同节点间 的协作来感知、采集和处理覆盖区域中监测对象的信息，并传输给用户。因其独 特的功能，在环境、医疗、家居和商业等普通领域应用前景良好，在军事、空间 探索和灾难拯救等特殊领域也有独特不可替代的优势【5 】，将会给人类未来的生活方 式和国际关系带来重大影响。 由于能量的有限性，无线传感器网络与传统的无线网络相比，有其独特的设 计目标【撕】。传统无线网络的主要目标是在高度移动的环境中尽可能的提高带宽利 用率，并为客户提供一定的服务质量保证，节点能量消耗为次要问题。而在无线 传感器网络中，大量节点被随机部署在环境非常恶劣的监测区域中，由电池提供 能量，并且无法更换节点的供能设备，节点的能量资源、处理能力、存储空间和 通信带宽都是非常有限的 7 1 ，因此传统的路由协议不适用于无线传感器网络，需要 为其设计新的路由协议，在设计过程中，应以能量的高效利用为首要目标，在现 有条件与满足要求的基础上尽可能延长网络生存时间。目前关于无线传感器网络 已有许多新的协议，但是随着研究的深入；各种协议在具有优点的同时也有着不 第2 页河南大学研究生硕士学位论文 可避免的缺陷，因此关于它的研究仍旧是热点问题。本文在对现有协议研究分析 基础上，充分考虑节点的能量限制问题，设计出一种满足需求、新的能量有效的 无线传感器网络路由协议。 1 2 国内外现状 无线传感器网络作为2 1 世纪最有影响的2 1 项技术和改变世界的1 0 大技术之 一，对它的研究最早起步于2 0 世纪9 0 年代末期，从2 1 世纪开始，传感器网络引 起了学术界、军界和工业界的极大关注，美国和欧洲相继启动了许多关于无线传 感器网络的研究计划，特别是美国通过国家自然基金委员会、国防部等多种渠道 投入巨资支持传感器网络技术的研究，美国几乎所有名校都有研究小组在从事传 感器网络技术的研究。我国的中科院、哈尔滨工业大学、清华大学、西北工业大 学等院校在国内较早开展了传感器网络的研究，2 0 0 4 年起有更多的院校和科研机 构加入到该领域的研究工作中来【8 】。目前，对无线传感器网络路由协议的研究为热 点之一。 在对无线传感器网络路由协议的研究过程中，出现了多种不同的路由协议。 研究人员根据网络逻辑结构将现有路由协议为平面路由和分簇路由【9 】【1 0 1 。平面路由 i l l - 1 6 】中节点的地位和功能相同，节点通过相互之间的协作感知、处理和传输数据， 完成用户发布的监测任务。典型的平面路由协议有f l o o d i n g ，s p i n ，d d ，r u m o r 和 s a r 等。分簇路由【1 7 4 明根据某种分簇算法将网络划分为若干被称为簇的区域，簇 中节点根据功能不同被分为簇首和簇内成员节点两种，簇内成员收集监测区域内 的数据传输给簇首，簇首对接收到的数据进行数据融合等处理后，以单跳或者多 跳方式传送给汇聚节点【4 9 】。与平面路由相比，分簇路由能够有效的利用节点能量， 且易于扩展，因此在无线传感器网络中采用分簇路由较为合适。 由于分簇路由在无线传感器网络中具有诸多优点，研究人员对它的研究一直 在进行 1 7 - 4 8 1 。研究领域主要分为以下三个方面：一、关于分簇结构。可以分为均 匀分簇【2 0 埘1 和非均匀分簇眨5 艺7 1 两个方面，二者目标不同。均匀分簇在保证连通性 河南大学研究生硕士学位论文第3 页 豹前提下，将网络划分为大小大致相等的簇，主要罄标为使各簇节点能耗较为均 衡。而非均匀分簇将传感器网络分为大小不同的簇，主要目标是均衡各簇首的能 量消耗。二、关于簇首选举算法。根据簇首选举方式的不同，可以把簇酋生成算 法分为分布式 2 3 2 9 - 3 2 】帮集中式两种。分蠢式壶节点决定是否充当簇酋，妊 l 姒c h ( l o we 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 ) ，h e e d ( h y b r i de n e r g y - e f f i c i e n t d i s t r i b u t e dc l u s t e r i n g ) 等；集中式簇首选择的决定权在汇聚节点，如l e a c h c 协 议。三、关于数据传输方案潮0 3 粥。在路鸯协议中，可以建立合理的簇结构，构 建簇问路由，减少数据传输距离来减少节点能耗。主要有簇交叠法和构建簇首之 间的多跳路由两种方法。 近麓对分簇路蠢的研究主要是对已有分簇协议的改进。眈较经典的分簇路由 协议有l e a c h ，h e e d 以及p e g a s i s 等；新的有p r o p o s e d ，c p r e ( c l u s t e r i n g p r o t o c o lb a s e do nr e s i d u a le n e r g y ) 等。l e a c h1 1 7 1 协议是在无线传感器网络中提懑 最晕的分簇路由协议，在每轮中动态选举簇蓠，数据传输中簇首对数据进行数据 融合，之后很多分簇路由协议都借鉴了这两种思想。p r o p o s e d 协议【l8 】于2 0 0 7 年提 如，它改进了l e a c h 协议中选择簇首、如何成簇的方法，并对何时传输数据加以 限铡。c p r e 2 2 】于2 0 0 8 年提蠢，它在簇曹选择时弓| 入了节点飘余能量，簇闻采用 多跳路由，簇首传输数据时选择下一跳的依据为节点到汇聚节点距离与其剩余能 量豹毙值。h e e d 3 锈协议在选举簇蕾时各节点通过信患迭代成为簇蕾，在簇蕾选举 与成簇过程中以节点的剩余能量与通信代价为依据，并在后面的研究中引入了簇 间多跳路由机制。p e g a s i s 3 3 】( p o w e re f f i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o ns y s t e m ) 协议是在l e a c h 协议分簇思想的基础上，提出的种特殊的分簇协议，金网仅存 一条通过贪婪算法两形成的链( 帮簇) ，一个簇酋。l e a c h c 箨珏( l e a c h c e n t r a l i z e d ) 在簇首选举时采取集中式的簿法，与分布式算法不同，节点是否成为簇首不是盘 巍蠢决定，焉是鸯汇聚节点掇据节点的剩余畿量与遗瑗位置选取，因此在成簇之 前所有节点需要与犯聚节点巍接通信将自己的相关信息传输过去，能耗较大。 无线传感器网络路由协议的主要目标是减少节点能耗，均衡全网能墓消耗， 第4 页河南大学研究生硕士学位论文 延长网络的生存时间。国内对于无线传感器网络路由协议研究还不成熟，虽然目 前根据对经典协议的研究也提出了许多新的路e l j 协议，但是仍然需要进一步的研 究，进步完善。 1 3 本文研究内容与组织结构 在无线传感器潮络路由中，分簇路由协议楚当前磅究的热点。本文对路由协 议l e a c h 、p e g e s i s 、h e e d 与c p r e 进行研究，分析其工作机制，总结各协议 优缺点，并针对缺陷提出相应改进，根据改进方案形成一种新的基于全局思想的 分簇路由协议e e c r p 。新协议提出了新的簇首选举、簇的形成以及构建簇间路由 进行簇闯数据传输的算法；改进后的算法可以改善簇首在网络内的分布、均衡全 网能量消耗，延长蹰络酌生存时间。为了验证协议的性能，在o m n e t + + 仿真平台 上对本文所提出协议、l e a c h 协议、h e e d 以及c p r e 协议进行仿真，验证所提 出路由协议的可行性及其节能性，并得出结论。 本文的组织结构如下： 第l 章：绪论。介绍了课题的研究背景、国内外研究现状以及本文的主要研 究内容。 第2 章：w s n 路耄协议与最小跳数路皇算法研究。对无线传感器鼹络路杰协 议进行概述，简要分析与传统路由协议的不同，需设计耘的与之相适应；对现有 的路由协议分类并进行性能比较，指出分簇路幽的优势；重点分析研究了分簇路 由协议与最小跳数路由算法，总结其优缺点。 第3 章：能量有效分簇路由协议e e c r p 的设计。根据第2 章的分析，在本章 中提出改进方案，并根据改进形成一种新的能量有效的分簇路由协议e e c r p ，该 协议从整体上对分簇路盘进行考虑，可以较好的选择簇首，形成较为合理的簇结 构，在数据传输时形成多跳路径。 第4 章：e e c r p 协议仿真实验。对仿真工具o m n e t - h 进行简要介绍，并利 用该仿真平台对提出的e e c r p 协议以及l e a c h 、h e e d 、c p r e 协议进行仿真实 河南大学研究生硕士学位论文第5 页 验，最后对仿真结果进行性能分析。 最后，总结与展望。总结论文中所做工作，指出不足之处，提出需要进一步 研究的问题 1 4 本章小结 在本章中，首先简要介绍本论文的选题背景，然后对无线传感器网络及分簇 路由协议的国内外研究现状进行描述，最后是论文的主要研究内容与本文的组织 结构。 第6 页河南大学研究生硕士学位论文 第2 章w s n 路由协议与最小跳数路由算法研究 在无线传感器网络中，各传感器节点需要将采集到的数据通过各种方式传输 到汇聚节点。为了保证节点能够及时且正确地进行数据传输，需要在节点与汇聚 节点之间建立合适的路由，由于传感器节点能量有限，在设计无线传感器网络路 由协议时应严格遵循其设计原则。 2 1 无线传感器网络路由协议 2 1 1 无线传感器网络路由协议概述 网络中的路由协议主要用于在源节点与目的节点间寻找一条合适的路径来转 发数据。其主要作用分为两点：寻找最优路径，沿着得到的路径转发数据分组。 河南大学新闻与传播学院2 0 0 9 届硕士学位论文 类网络的路由协议主要是寻找发送数据时通信时延较小的路径，在此基础上增加 对带宽利用率、网络通信拥塞等问题的考虑；由于传统网络能量比较充足，因此 寻找最优路径是它的主要任务，而能耗问题对其传输数据影响性不大。与传统网 络不同，无线传感器网络中节点数量庞大，能量有限且不易补充，因此该网络的 路由协议应以能量的有效利用为重点；由于各方面因素的限制，节点不能获得全 局拓扑结构信息，路由协议只能在节点提供的有限的信息下形成较合适的路径【8 】； 另外，传感器网络的路由协议与实际应用紧密相关，应用环境不同则路由协议可 能也不同，同时为了减少网络中的通信量与网络能耗，路由协议一般与数据融合 共同使用。由上面的分析可知，无线传感器网络应不能使用传统无线网络的路由 协议，在研究过程中，应根据其具体需求设计专门的路由协议。 2 1 2 无线传感器网络路由协议分类 针对不同的无线传感器网络应甩，研究人员根据其固有的特点与应用需求设 计了不同的路由协议。现有的无线传感器网络路由协议可以根据网络逻辑结构分 河南大学研究生硕士学位论文第7 页 为平面路由协议与分簇路由协议两类。 在平面路由协议中，传送数据的路由由地位平等的节点通过相互之间的信息 反馈来形成。平面路由拓扑结构图如图2 1 所示： 图2 1 平面路由拓扑结构图 在平面路由中，汇聚节点向网络监测区域发布查询消息，接收到查询消息的 节点将采集到的数据通过合适的路径传送给汇聚节点。平面路由的形成较为简单、 可扩展性较好，对拓扑结构的维护开销不大，同时由于网络内各节点地位相同不 易产生瓶颈问题。但是平面路由也存在其缺点：网络中节点等级相同，不存在管 理节点，缺乏对通信资源的优化管理；所有节点通过自组织方式协同工作，向汇 聚节点传输数据，由于节点距离汇聚节点较远，节点间协同进行多跳数据传输， 因此存在时延问题且时延会随着网络规模的增大而增大。平面路由的局限性较大， 不适用于节点数目庞大的大型网络。此类协议的代表有：s p i n 1 1 1 ，d d e l 2 1 ，r u m o r r o u t i n g 13 1 ，f l o o d i n g 1 5 蝽。 分簇路由协议与层次拓扑结构相对应。层次拓扑结构网络通常以簇( 簇由具有 某种关联的网络节点组成) 的形式存在。分簇路由协议拓扑结构图2 2 所示： 分簇路由协议与平面路由不同，在使用该类路由协议的网络中，传感器节点根 据功能不同被分为两类：簇首节点和簇内成员节点( 在特殊的网络路由协议中， 也存在次簇首) 。簇首节点通过簇首选举算法产生，主要管理或控制簇内成员节点， 协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理，并将处理过 的数据转发给其它簇首或者直接传输给汇聚节点，早期的分簇协议一般采用直接 传输方式，近期路由协议大多采用多跳路由。此类协议的代表有：l e a c h 1 7 1 ， 第8 页河南大学研究生硕士学位论文 h e e d t 3 0 1 ，p e g a s i s t 3 3 1 ，t e e ne 3 4 1 ，l e a c h c t 5 1 】等。 s i n k 图2 2 层次拓扑结构图 与平面路由协议相比，分簇路由协议的优点如下( 5 2 】( 5 3 】： 1 簇首节点和簇内成员节点不同，仅接收来自簇内成员节点的数据，对数据 进行融合之后转发出去，分簇路由消除了平面网络中洪泛广播控制信息的 能耗并且由于网络有了层次减少了数据传输和通信量。 2 簇内成员节点仅在簇首节点分配给自己的工作时隙内进行数据传输，在其 他时间内处于休眠状态；簇内成员仅与簇首节点通信，一定程度上避免了 数据的长距离传输，在减少节点能耗同时，减少全网内耗；数据传输给汇 聚节点主要通过在簇首间构建的多跳路由，多跳路由在减少簇首节点能耗 同时，保证了网络区域内数据的通信质量。 3 。分簇路由简化了网络中节点维护的路由信息，从而可以减少网络中控制消 息量的传输。 4 与平面路由相比，分簇路由协议分布式算法的应用可以对系统变化做出快 速反应，能够较好的解决节点位置变化所带来的问题， 由于分簇路由协议与平面路由协议相比具有诸多优点，使之成为目前无线传 感器网络研究的热点和重点。通过对分簇路由的研究可知，分簇路由协议设计的 首要目标是通过高效的分簇算法形成合理的网络结构，通过主动的能量管理阻止 河南大学研究生硕士学位论文第9 页 网络连通性的下降，减少节点能耗，延长网络的生存时间。 2 1 3 路由协议中分簇算法性能评价 分簇路由协议中的分簇算法主要用于将网络分为多个相互连通的簇，在发生 变化时更新簇结构以维护网络的运行。它的目的是将网络通过某种规则进行初始 化，从而获得相互连通、覆盖所有节点的簇结构，簇结构可以随着网络结构的变 化及时做出反应，能够正确地传输收集到的数据。为了减少开销，分簇算法应该 尽量简单高效。 随着对分簇算法研究的深入，国内外在经典分簇协议的基础上提出了许多新的 协议，在比较各种分簇协议的性能时，主要采用以下几种性能指标【5 4 】： 1 网络中簇( 首) 数目c ，它直接反应分簇网络的结构和特性。分簇网络的簇 数目不应过多，也不能过少，应以满足系统要求和减少控制开销为准则。 2 单位时间内簇首构成的统治集更新的次数，说明簇重构的频率。重新分簇 会引起较大的计算和通信开销，该指标在很大程度上决定了分簇算法的性 能。 3 簇重叠度，簇首处理负载的能力取决于它可以支持的节点数量。除了为簇 内节点分配资源外，簇首还需要维护簇间的路由。因此希望网络的负载能 够比较均匀地分配到各个簇，从而提高网络的整体性能。但在无线传感器 网络中优化负载比较网难，为了定量地刻画簇首的负载平衡程度，引入簇 重叠度和网络负载平衡因子l b f 两个参数。簇覆盖内所有节点的数目之 vr 和和网络节点总数的比值作为网络的簇重叠度c i d = 二乎，显然c d 越大， n 处于重叠区域的节点数量越多，c d 小，则处于重叠区域的节点较少。 4 网络负载平衡因子( l b f ) ：簇首的处理负载近似由该簇的大小表示，即簇 的大小的变化可以反映簇首负载分布。l b f 定义为簇内成员数( 不包括簇 第 0 贾海南大学研究生硕士学位论文 首) 的方差豹倒数，酃毛鼯= i 翌一，其中心是簇豹数量，麓是簇f 麴 ( 一一龆) 2 成员节点数，嚣茹监表示赭络中每个簇酋翁平均邻节点数，n 为瓣 露。 络中所有节点麓数霉。显露易见，l b f 越大，鼹络麓负载平衡程度越好， 在最理想的情况下，( 薯一嚣) 愈小，l b f 趋向无穷大。 5 节点充警簇首勰公平指数( 鲑醪) ：该指标说明各个节点充当簇酋靛公平程 度，w 定义为节点担当簇首的时间偏差，即彪w ，- - e t ，- e ( t 剑j ，f v 。 其中，毫表示苇点充当簇首的时闻，嚣( 毫) 篇厂表示节点担当簇蕾的平 均时闻，h f i 表示节点f 充当簇首时闻编离节点携强簇首平均时阉韵程度。 医此h f i 越小，说锈节点充当簇酋的公平性越好，在最好的情况下， 毛= 嚣( ) ，鼠甜= 0 。出于簇首的能量消耗较大，越小，意味着能量消 耗越能均匀的分配到各个节点上，从而可以延长网络的生存时间。 2 2 分簇路豳协议研究 在无线传感器隔络路由协议中，能量有效是关键阀题。本节主要对死种分簇 路畿协议进行分析研究，总结其在工作中的优缺点，并分析其能量的有效槛。 2 。2 1l e a c h 协议分析 l e a c h 协议是无线传感器网络中提磁熬第一个分簇路壶协议。现有的大部分 分簇路由协议都是在它的基础上发展丽来的。 一、协议播述 l e a c h 协议的工作过程是周期性执行的。在该协议溺孛，每轮分戈簇首选择、 簇的形成以及数据传输。首先在簇首选举阶段，簇酋是随机生成的，网络内的节 点动态交互成簇，在数据传输阶段，簇内节点直接传输数据给簇首，簇酋收集数 河南大学研究生硕士学位论文第1 1 页 据并进行融合后直接发送给汇聚节点。具体流程如下： 簇首选择阶段，采取分布式的簇首选举算法，节点是否充当簇首可以由自己 决定。节点成为簇首的概率由网络初始化时设定的簇首数目占总节点数的百分比 决定，如果节点在以前的轮次中已经充当过簇首，则在本轮中不会当选，对于未 充当过簇首的节点，则以t ( n ) 的概率当选。簇首选择的过程如下：节点产生一个0 到1 之间的随机数，如果该随机数小于某个阈值r ( n ) ，那么该节点就成为当前轮 的簇首。阈值r ( n ) 的定义如下： f里 i fn eg 丁( 玎) 2 1 一p r m o d ( 1 p ) 】一( 2 1 ) 【0 o t h e r w i s e 在式( 2 - 1 ) 中，p 是簇首节点占节点总数的百分比，是当前的轮数，g 是在过 去v p 轮中未充当过簇首的节点集合，m o d 是求模运算符。通过此种选择方法，在 v p 轮中每个节点都会充当一次簇首。在每轮循环中，将已经充当过簇首的阈值 丁( ，z ) 置为o ，可以避免某节点多次成为簇首，加速节点能耗。随着时间的增长，当 选过簇首的节点数越来越多，为了保证网络内的簇首个数一定，则没有当选过簇 首的节点的阈值不断增大直到为1 。1 p 轮后，重复以上工作流程，即该工作过程 为周期性的执行。 节点成为簇首后，在网络内广播消息通知其它节点自己为新簇首，簇首节点 忽略该消息，非簇首节点在接收到的多个消息中选择信号强度最强即距离自己最 近的簇首节点加入，并发送加入信息给该簇首。经过一定的时间间隔，簇首接到 所有的加入消息后，就产生一个t d m a 定时消息，并且通知簇中所有成员节点。 为了避免簇之间的信号干扰，不同簇可以采取不同的c d m a 编码，簇首在发送 t d m a 时将c d m a 一同发送，簇内节点收到该消息后，在分配给自己的时隙内传 输数据，而在其它时间关闭通信模块，可以减少节点能量消耗。经过一段时间的 数据传输，簇首节点收齐簇内节点发送的数据后，运行数据融合算法来处理数据， 第12 页河南大学研究生硕士学位论文 并将结果直接发送给汇聚节点。 二、l e a c h 协议的通信模型 在l e a c h 协议中，采用第一顺序无线电模型( f i r s to r d e rr a d i om o d e l ) 【1 7 1 ， l e a c h 协议的通信模型基于以下假设： 1 网络中所有节点相同且能量有限； 2 对于给定的信噪比信道是对称的，即从节点m 发送到节点n 的能耗与从节 点n 发送到m 的能耗相等； 3 s i n k 节点固定，并且在覆盖区域外，离网络较远； 4 无线电信号在各个方向上能耗相同。 通信模型如下： kb i t 数据 e t x ( d ) 弋7 发射电路l信号放大器 j & k + k岛晒。+ k + d 8 d 一一一。r e h v l l 接收电路 l e c l * k! 一- j 图2 。3 第- - l l l 页序无线电模型图 根据上图模型可知，传感器节点发送kb i t 数据所消耗的能量为： e r x ( 七，d ) = e r x - d e c ( j | ) + e r x 一唧( 七，d ) = e e l e c 唪k + 幸k 宰d - ( 2 - 2 ) 传感器节点接收kb i t 数据所消耗的能量为： ( j i ) = 一, j e c ( k ) = k 宰( 2 3 ) 在式( 2 - 2