（信息与通信工程专业论文）无线传感器网络分簇路由协议研究.pdf

原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：! 塾堕终日期：二业l 年月1 日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 期：型盟年月4 日 如 是设计 基础上 络中能 针 对变换 高参数集合的可区分性。在成簇阶段，节点将簇头剩余能量、簇头与 节点和簇头与基站的传输能耗等参数利用本文模型进行相对变换，再 利用变换后的参数计算簇头适宜度作为成员节点的入簇依据，并通过 簇头的反馈信息控制簇的规模，形成优化的簇结构，使得网络节点负 载更均衡。通过仿真实验验证了算法的有效性。 为节省节点在数据传输过程中的能量，均衡节点间的能耗，提出 一种基于非均匀簇的混合多跳路由协议。先根据簇头与基站的距离调 整簇规模的大小，在数据传输过程中，源簇头节点通过转发权值函数 选择中继节点，转发权值由距离因子和惩罚因子共同决定，距离因子 综合考虑了源簇头节点的当前剩余能量、单跳距离和下一跳节点的剩 余能量，用以降低链路通信代价，惩罚因子可以降低剩余能量较少的 簇头节点成为中继节点的概率，用以均衡节点能耗。通过选择转发权 值较小的中继节点可以达到均衡节点负载和提高能量利用率的目的。 通过仿真实验验证了算法的有效性。 关键词无线传感器网络，能耗均衡，分簇算法，路由协议 a bs t r a c t c o n s e r v a t i o no fe n e r g y c o n s u m p t i o na n dp r o l o n go fn e t w o r k l i f e t i m ea r et h ev i t a la i m so fd e s i g nw s n a i m i n ga ti n c r e a s i n ge n e r g y u s a g ee f f i c i e n c ya n db a l a n c i n ge n e r g yc o n s u m p t i o n ，t h i sp a p e rf o c u s e so n d e v e l o p i n gac l u s t e r i n ga l g o r i t h ma n dal a y e r e dr o u t i n gp r o t o c o lt o i m p r o v ee n e r g ye f f i c i e n c y t os o l v et h el o a db a l a n c ep r o b l e m ，ac l u s t e r i n gh i e r a r c h ya r i t h m e t i c b a s e do nr e l a t i v et r a n s f o r m a t i o n ( r t c h ) i sp r o p o s e d f i r s t l y , r e l a t i v e t r a n s f o r m a t i o nm o d e lt oi m p r o v et h ed i s t i n c t i o no ft h ep a r a m e t e r si s p r e s e n t e d d u r i n gt h es t a g et of o r mc l u s t e r s ，t h ep a r a m e t e r s ，s u c ha sr e s t e n e r g yo fc l u s t e rh e a d ，t r a n s p o r te n e r g yc o s tf r o mi t s e l ft oc l u s t e rh e a d a n dt h ec o s tf r o mc l u s t e rh e a dt os i n kn o d e ，a r et r a n s f o r m e db yt h em o d e l d e s i g n e di nt h i sp a p e r t h en o d e ss e l e c tt h eo p t i m u mc l u s t e rh e a dt h r o u g h c a l c u l a t i n g 1 1 1 ee x t e n to fc l u s t e rc a nb ec o n t r o l l e dt h r o u g ht h ef e e d b a c k i n f o r m a t i o nf r o mc l u s t e rh e a d p e r f o r m a n c eo ft h ep r o p o s e dr t c hi s e v a l u a t e dt h r o u g hn s 2s i m u l a t i o na n dt h er e s u l t ss h o wt h a ti ti se f f e c t i v e t os a v et h ee n e r g yc o n s u m p t i o ni nd a t at r a n s m i s s i o na n dt om a k e t h ee n e r g yc o n s u m p t i o no fn o d e sb a l a n c e d ，am u l t i h o pr o u t i n ga l g o r i t h m b a s e do nu n e v e nc l u s t e r i n g ( m r u c ) i sp r o p o s e d f i r s t l y , a d j u s tt h es i z eo f c l u s t e r sa c c o r d i n gt ot h ed i s t a n c eb e t w e e nc l u s t e rh e a da n ds i n kn o d e d u r i n gt h ed a t at r a n s m i s s i o n ，t h er e l a yn o d ei sc h o s e nw i t ht h es o u r c e n o d et r a n s m i t t i n gw e i g h t sf u n c t i o n ，w h i c hi sd e c i d e db yd i s t a n c ea n d p u n i s h m e n te s s e n t i a l s 1 1 1 ed i s t a n c ee s s e n t i a l ，c o n s i d e r i n gt h er e s i d u a l e n e r g ya n dt h es i n g l e h o pd i s t a n c eo f t h es o u r c ec l u s t e rh e a d ，a n dt h er e l a y n o d e sr e s i d u a le n e r g y , i su s e dt or e d u c e e n e r g yc o n s u m p t i o n ；t h e p u n i s h m e n te s s e n t i a l ，w h i c hc a nr e d u c et h ep r o b a b i l i t yt h a tt h ec l u s t e r h e a dw i t hl o wr e s i d u a le n e r g yt u m si n t or e l a yn o d e ，i su s e dt ob a l a n c et h e n o d e sc o n s u m p t i o n p e r f o r m a n c eo ft h ep r o p o s e dm r u ci se v a l u a t e d t h r o u g hn s 2 s i m u l a t i o na n dt h er e s u l t ss h o wt h a ti ti se f f e c t i v e k e yw o r d s w s n ，e n e r g yc o n s u m p t i o nb a l a n c e ，c l u s t e r i n ga l g o r i t h m ， r o u t i n gp r o t o c o l 目录 摘要i a b s l r a c t i l 目 录i 第一章绪论一1 1 1 课题背景及研究意义1 1 2 国内外研究现状3 1 3 论文研究内容一5 1 4 论文组织结构6 第二章w s n 中分簇算法和路由问题的研究与分析7 2 1w s n 体系结构和能耗问题7 2 1 1 传感器结构和能耗特点7 2 1 2w s n 体系结构和能耗特点8 2 1 3 能耗特点对设计网络协议的需求9 2 2 无线传感器网络分簇算法分析l o 2 2 1 分簇网络的特点与优势1 0 2 2 2 经典分簇算法的分析和比较11 2 2 3 分簇算法的设计需求和难点探讨1 6 2 3 无线传感器网络路由协议分析17 2 3 1 路由协议的特点。1 7 2 3 2 经典路由协议的分析和比较18 2 3 3 路由协议的设计需求和难点探讨一2 0 2 4w s n 分簇算法和路由协议的设计思路2 l 2 5 本章小结2 1 第三章一种应用相对变换的w s n 分簇算法( r t c h ) 一2 2 3 1r t c h 的模型设计2 2 3 1 1 网络模型与假设2 2 3 1 2 能量模型的推导计算2 3 3 2r t c h 分簇算法实现方案2 4 3 2 1 相对变换模型的建立2 5 3 2 2r t c h 中最优簇头数目的确定一2 6 3 2 3 相对变换模型下的动态成簇过程2 7 3 2 4r t c h 分簇算法的执行过程2 9 3 3r t c h 算法仿真与结果分析3 1 3 3 1n s 2 网络模拟器31 3 3 2 仿真参数和评价标准3 2 3 3 3 仿真结果及分析3 3 3 4 本章小结3 4 第四章基于非均匀簇的混合多跳路由协议( m r u c ) 3 5 4 1 分簇路由问题描述一3 5 4 1 1 能耗均衡问题3 5 4 1 2 路由设计目标3 6 4 2m r u c 路由方案设计3 8 4 2 1c m c h 层簇规模的动态调整3 8 4 2 2c h b s 层中继节点的确定3 9 4 3m r u c 路由算法实现4 2 4 3 1c m c h 层非均匀簇的形成4 2 4 3 2c h b s 混合多跳路由选择4 3 4 3 3m r u c 算法分析一4 5 4 4 算法仿真与结果分析4 6 4 4 1 仿真参数和评价标准4 6 4 4 2 仿真结果及分析4 8 4 5 本章小结。5 0 第五章总结与展望5 1 5 1 总结5 1 5 2 展望5 2 参考文献5 3 致谢5 9 攻读学位期间的主要研究成果6 0 i v 硕+ 学位论文 第一章 2 0 世纪9 0 年代以来，随着半导体技术、微电子技术、计算机技术以及通信 技术的飞速发展，国内外的研究机构和知名企业纷纷开始了对无线传感器网络的 研究和应用。无线传感器网络以其获取和感知物理世界信息的超强能力，成为了 当今世界学术界及工业界的研究热点之一，具有广泛的应用前景。传感器节点的 能量、存储、计算和通信能力等资源严重受限，决定了高效利用节点能量以延长 网络的生存时间是研究无线传感器网络首要解决的关键问题之一。本文着重分析 和研究无线传感器的分簇算法和路由协议两种关键技术，旨在提高网络能量的利 用率、均衡节点能耗和最大化网络生存时间。 1 1 课题背景及研究意义 无线传感器网络( w s n ，w i r e l e s ss e n s o rn e t w o r k ) 是近二十年来得到迅速发 展和普遍重视的新型网络技术【l j ，作为一种新的获取感知物理世界信息的方式和 信息处理模式，它的出现对现代科学发展产生了极其深刻的影响，也显著地提高 了人们认识世界和感知世界的能力。 w s n 由大量的微型传感器节点组成，节点随机地部署在监测区域内，通过 多跳的无线通信方式组成一个自组织的网络系统。节点的主要任务是采集监测区 域内的信息并将信息发送给用户1 2 j 。与传统的网络技术不同，w s n 技术将现代 无线通信技术、嵌入式技术、微型传感器技术和网络技术有机地融合为一体，有 效提高了数据获取的方式和效率，扩展了网络现有的功能和人类认识世界的能 力。w s n 在国家安全、环境监测、医疗监护、家庭自动化、运输和许多其他领 域都具有极高的应用价值和广阔的应用前景，成为当前业界研究的热点之一【3 4 j 。 美国商业周刊的未来技术版将w s n 列为本世纪最有影响力的2 1 项技术之 首【5 j ；m i t 技术评论将w s n 列为改变世界的十大技术之m 6 1 。 对于无线传感器网络来说，它与传统的固定网络差别很大，与移动自组网也 不尽相同。无线传感器网络具有规模大、部署随机、应用环境复杂、网络拓扑经 常变化等特点，其中，w s n 的规模大包含两方面的含义：一方面是传感器节点 分布在面积很大的地理区域内；另一方面，在特定区域内，节点分布较为密集， 节点数量大。这些特点使得网络维护起来十分困难，甚至是不可维护的。 w s n 的主要功能是感知并获取客观物理世界的信息，并将信息发送到用户。 硕士学位论文 第一章绪论 用户只关心某个区域的检测数据，而不会去关心具体是哪个节点的观测数据。因 此，不同的应用场景对w s n 的要求也不同，其硬件平台、软件系统和网络协议 必然会有很大差别。只有让系统更贴近应用，才能做出更高效的目标系统。 组成w s n 的传感器节点是一种微型的嵌入式设备，一般由电池供电，使用 过程中由于节点数量众多且环境复杂，很难给电池充电或更换电池，一旦电池能 量耗尽，该节点将失去作用。因此，节点能量有限是阻碍w s n 开展应用的严重 障碍。因此如何高效利用w s n 的节点能量是研究w s n 的重要课题之一。 对于传感器节点来说，无线通信的能量消耗随着通信距离的增大以指数倍速 率迅速递增【7 1 ，而且通信范围只有几十到几百米。因此，应在在满足网络连通的 前提下尽量减少单跳通信距离，节点之间的数据传输应尽量采用多跳路由的传输 机制，以降低整个网络的功耗【8 】。但是传感器节点的计算能力、存储能力以及通 信能力十分有限，所以在采用支持多跳路由的网络类型时，花费在路由建立和路 由表的维护等方面的内存开销以及计算成本不能太高，维护网络路由的开销不能 太大，而且相应的功耗必须在允许的范围之t 9 j 。 但应用于传统网络的路由协议，节点建立和维护路由信息的丌销比较大，会 给能量有限的传感器节点造成过重的资源损耗【i o l ，使得节点因为能量耗尽而失 效，影响网络的生存时间。因此传统的路由协议不能满足w s n 低功耗的需求， 设计一种能量利用效率高且具有可扩展性的网络拓扑和路由协议就成为了w s n 研究的迫切而又重要技术之一。 现阶段，对于网络层路由协议的研究是无线传感器网络研究的重要方面之 一。为了使得w s n 的使用寿命最大化，国内外很多知名专家和学者提出了许多 新的网络拓扑和路由协议方案。很多网络设计方案中都选用了基于分簇的网络结 构【1 1 1 ，这种结构具有便于扩展、拓扑管理方便、路由相对简单、能量利用率高等 优点，适合大规模网络，因此研究分簇网络和路由协议，对于延长无线传感器网 络的生命周期具有重要的意义l l2 1 。 w s n 中基于分簇的路由协议还存在以下挑战：如何产生优化的簇头数量； 如何确定簇规模的大小；如何消除由于不同位置的节点当选簇头而造成的网络能 耗不均的情况；如何在保证数据可靠传输的前提下，尽量降低多跳路由的维护开 销和算法复杂度等等。 综上所述，w s n 有别于传统网络，现有的网络结构和路由协议已经不能满 足w s n 的性能需求和服务质量需求，设计新的w s n 网络结构和路由算法来保 证网络中总能耗最小化、网络节点负载均衡化以及通信能力最优化已成为当今的 研究热点及重点技术之一。 2 硕士学位论文 第一章绪论 1 2 国内外研究现状 无线传感器网络的巨大应用价值和广阔应用前景，已引起工业界、学术界和 世界上许多国家军事部门的极大关注。当今学术界和产业界十分看好w s n 的学 术价值和应用前景，国际上许多著名的研究机构和知名企业纷纷从不同层次和不 同角度对w s n 进行研究和开发。 国外对无线传感器网络的研究起步较早，可以追溯到1 9 7 8 年由美国国防部 高级研究计划署( d 心) 发起的分布式传感器网络研讨会。而后的1 9 9 6 年美 国又开始了d a r p a 低功率无线集成微传感器研究计划【l 引，接着19 9 8 年又启动 了s e n s l t 研究计划，这一计划中有2 5 个研究机构资助了2 9 个研究项目。 其中一些较大的研究项目包括：加州大学和罗克韦尔科学中心联合启动的无 线综合网络传感项目( w i n s ) ，该项目几乎覆盖了w s n 设计中的所有方面，且 研究成果已经商业化1 1 4 j ；美国加州大学伯克利分校的p i c o r a d i o 计划【”】，主要研 究基于信道选择、冲突避免的m a c 层协议f 1 6 1 ；麻省理工学院的g a m p s 计划【1 7 1 ， 该计划强调低功耗的必要性，研究出低功耗自适应分簇路由协议；还有诸多其他 的研究计划如s m a r td u s t l l 8 l 等等。在民用领域，美国交通部1 9 9 5 年提出了“国 家智能交通系统项目规划 ，该计划致力于集成先进的数字通信技术、传感器技 术、智能控制技术以及计算机处理技术，并应用到地面交通管理系统，建立一个 全方位大范围的综合交通管理系统，预计到2 0 2 5 年该系统能够全面投入使用。 在国内方面，对于w s n 的研究和应用工作虽然还处于起步阶段，但我国政 府高度重视和支持对w s n 的研究，相继启动了很多研究项目。一些科研机构和 大学已经相继开展了在无线传感器网络方面的研究工作，研究范围涵盖了无线传 感器结点的硬件设计、操作系统、网络路由技术、节能技术、覆盖控制技术等， 并初步取得了一些研究成果。 另外，任何一种技术的快速持续发展都需要成功实现标准化。w s n 各层通 信协议的标准化工作也在进行中，z i g b e e 联盟开发了i e e e8 0 2 1 5 4 低速率无线 个域网标准i 侈l ，i e e e 成立了i e e e1 4 5 1 5 无线传感器工作组1 2 0 1 ，标准化工作将 会提高w s n 的实用性，使得w s n 的市场规模化，从而促进w s n 的应用。 综上所述，对于w s n 的研究，国外已处于理论和技术的标准化研究阶段， 甚至有的已进行市场原型产品的设计和开发并投入使用；而国内，相应的研究活 动相对还较少，研究范围也主要在部分高校和研究所。从整体上看，国内的研究 水平落后于国外，但由于w s n 是一门新兴的技术，国内与国际的差距并不大， 及时深入开展对w s n 的研究，对国家的社会和经济发展具有重大的战略意义。 设计w s n 首要考虑的是节点能量有限的问题。国内外专家和学者从不同角 硕士学位论文 第一章绪论 度不同层次提出了很多解决办法，例如物理层提出利用电荷恢复效应延长电池寿 命；为了降低设备功耗，可控制信道选择的方法等。本文主要研究分簇网络中节 点通信能耗的特点，因为对于没有任何逻辑结构的扁平网络，所有节点必须协同 控制网络，链路的建立、节点的加入或失效等都会对网络造成很大的能量开销， 而对于分簇网络来说，每个簇只有簇头负责与外部通信，路由相对简单，可有效 降低通信开销。下面分析这方面的研究成果： w s n 分簇结构的研究主要集中在如何选择簇头、如何成簇、如何在簇间和 簇内进行数据传输三个方面【2 l 】，这三个方面紧密联系而又相互独立。 w s n 中最经典的分簇算法是l e a c h 2 2 1 ，由h e i n z e l m a n 等人提出，算法中 的分簇思想对后来发展的众多分簇路由协议具有重要影响。l e a c h 致力于解决 簇头能耗问题，但无法消除可能发生在随机簇头产生过程中的网络分裂问题。 在l e a c h 的基础上，l e a c h d c h s1 2 3 】考虑了节点剩余能量和阈值对簇头 选择的影响，改进阈值计算方法，使分簇更合理。h e e d 2 4 】利用节点间的交互信 息动态产生簇头，分簇速度快且簇的分布更均匀。l e a c h c 【2 5 l 和l e a c h f 【2 5 j 由基站根据全局信息挑选簇头，簇头的数量和位置较为合理且减少了成簇开销， 但网络扩展性差，簇间信号干扰大。e c m r 2 6 】是采取预先指定簇头的方式，且指 定簇头的初始能量不受限制。c e f l 2 7 】设计了隶属函数，采用重心法基于模糊逻 辑挑选簇头，适合中等规模网络。d a e a 2 8 】是三层的分簇协议，依据地理位置划 分簇，该算法可以节省能量但是增加了时延，不适合大规模网络。h y e n a s l 2 9 j 算法不需要每轮重新成簇，节省了部分成簇开销。另外还有基于地理位置的成簇 算法p e g a s i s 3 0 】、具有反馈机制的自适应分布式成簇算法a c e 3 1 l 等等。 另外，考虑到簇内和簇间通信代价，很多算法提出了非均匀分簇的思想。 e e c s l 3 2 j 通过设计通信代价函数成簇，使得远离基站的簇规模较小，以减少簇内 通信能量消耗来均衡节点问的能耗；在此基础上，l i 等人提出了另外一种非均 匀分簇算法e e u c l 3 3 1 ，算法中靠近基站的簇规模较小，节约簇内通信能量消耗用 于转发远离基站的簇头数据，达到均衡节点能耗的目的；s o r o 【3 4 j 等人将网络划分 为非均匀的圆环，设计不同的成簇半径，形成非均匀分簇模型；文献1 3 5 根据节 点位置改变簇头竞争半径，使得靠近基站的簇规模较小，以节约簇内通信能量用 于转发簇间数据，但该算法簇头分布比较随机，不能保证簇的最优化。文献 3 6 】 根据每一轮的能耗和每个簇的总能量，通过不断调整簇规模形成生存时间相等的 簇，网络能耗较均衡，但控制开销大，成簇速度慢，扩展性差。 学术界对于w s n 路由协议的研究也有了很多成果，路由协议可运用多种策 略实现，并且根据不同的分类依据1 3 7 ，3 引，路由协议的分类也不同。 洪泛协议和闲谈协测3 9 l 是两个较为经典的、可应用到w s n 中的传统路由协 4 硕士学位论文第一章绪论 议，不需要维护路由信息，简单但扩展性差；s p i n 4 0 l 是第一个基于数据的路由 协议；d d 4 1 协议是基于数据的查询驱动路由协议，采用查询驱动机制建立路由， 健壮性好而且减少了数据通信量，但存在较大开销时延；g p s r a j 是基于位置的 路由算法，网络节点知道自身地理位置并被统一编址，采用贪心算法使各节点尽 量沿直线转发数据；其他平面路由协议还有m m o r 【4 3 1 ，g e a r 4 4 1 ，s a r 4 5 1 等。 l e a c h 是第一个分簇路由协议，不适合大型网络。t e e n 4 6 1 通过减少数据 的发送次数在精度要求和系统能耗间平衡，可减少网络通信量，但存在数据时延 和信号干扰；a p t e e n 4 7 结合l e a c h 和t e e n ，通过修改l e a c h 的t d m a 时 隙，提高数据的响应效率。t t d d 4 8 】采用构造格状网的方法，使用代理机制，解 决多基站及基站移动的问题，能延长网络时间但格状网的维护开销大。 文献【4 9 】根据传输链路总能耗最小( m t e ) 选择下一跳路由；文献【5 0 】根据 传输链路中中继节点的剩余能量最大( m r e ) 选择下一跳路由；文献【5 1 】提出基 于节点能量负载均衡的路由协议，通过单个节点能量利用率达到最大化，提高网 络能量利用率；文献【5 2 】提出单链路和多链路两种数据传送机制，在传输速率和 通信代价方面进行均衡；文献 5 3 】提出一种能量有效的多播路由算法，根据局部 信息基于贪婪算法来构建多播树，使得中继节点数量最小，从而最小化网络能耗； 李等人【5 4 】在非均匀分簇算法e e u c 的基础上，采用簇内单跳、簇间多跳的通信 方式，均衡长距离节点的通信能耗。 综上所述，设计w s n 分簇结构和路由协议时，能量利用率是衡量算法好坏 的重要依据之一。但是如何在单个节点的能耗和整个网络的总能耗之间取得均衡 以及在减少算法的控制开销和降低传输能耗之间取得均衡等方面还存在很多问 题。因此，设计既能够提高网络能量利用率又能够均衡各个节点能耗的分簇结构 和路由协议是w s n 研究中迫切而又重要的课题之一。 1 3 论文研究内容 本文主要研究无线传感器网络分簇路由协议，为了高效均衡地利用网络能 量，论文从分簇结构的优化和路由选择两方面提出解决方案。主要研究工作包括 以下方面： 1 无线传感器网络中分簇算法和路由协议的特点和能耗分析 详细分析无线传感器网络的体系结构和能量消耗特点，总结出分簇网络的特 点和优势，然后分析w s n 路由协议的特点、设计要求和性能指标，得出分簇算 法和路由协议的设计需求和难点，确定分簇算法和路由协议的设计思路。 2 研究应用相对变换的无线传感器网络分簇算法 5 效延长网络的生存时间。 4 对论文提出的算法进行性能评估 从理论上对提出的应用相对变换的w s n 分簇算法和基于非均匀簇的混合多 跳路由协议进行性能分析，并采用n s 2 仿真平台对算法进行验证。 1 4 论文组织结构 本论文共分为五章，后续章节安 t 女t j 下： 第二章w s n 中分簇算法和路由问题的研究与分析介绍无线传感器网络的 体系结构和能量消耗特点；阐述w s n 中分簇网络的特点和优势；分析w s n 路 由协议的特点、设计要求和性能指标，得出分簇算法和路由协议的设计需求和难 点，确定本文研究的方向和思路。 第三章基于相对变换的无线传感器网络分簇算法针对l e a c h 路由协议中 簇头节点能耗不均衡的问题，在成簇算法方面进行改进。并对改进后算法的性能 进行分析，最后通过仿真实验证明算法的优越性。 第四章基于非均匀簇结构的混合多跳路由协议针对多跳路由协议中存在 的热点和盲区问题，在非均匀分簇的基础上提出一种新的簇问多跳路由选择算 法，并对改进算法进行仿真验证。 第五章总结与展望对论文所作的工作进行总结，并对以后需要进一步研究 的工作进行展望。 6 硕士学位论文 第二章w s n 中分簇算法和路由问题的研究与分析 第二章w s n 中分簇算法和路由问题的研究与分析 设计无线传感器网络时，在网络层需考虑两个相互关联的问题：网络的结构 和数据在网络中的路由。对于分簇结构的网络，每个簇中只选出一个节点负责与 外部通信，路由相对简单，可有效降低通信开销。数据在网络中传输时，针对不 同的应用环境和不同的网络结构，可以根据不同的代价函数选择不同的路由解决 方案。因此，研究w s n 分簇算法和路由问题具有重要的意义和价值。 2 1w s n 体系结构和能耗问题 本节着重分析传感器节点的能耗特点和w s n 的能耗特点，然后据此研究设 计w s n 网络协议时需要解决的问题和达到的目标。 2 1 1 传感器结构和能耗特点 传感器节点一般由五部分组成，如图2 1 所示。控制器用于处理相关数据， 可执行代码；存储器分为不同类型，分别用于存储数据和程序；传感器用于观测 或控制环境；通信设备用于在无线信道上进行消息的发送和接收；电源一般采用 电池供电。这些部件在尽可能在保持低功耗与完成任务之间取得折中。 图2 - 1 传感器节点硬件组成 各部分的能量消耗【5 5 j 如下图2 2 所示，能量消耗主要集中在处理器模块、无 线通信模块和无线传感器模块，其中，通信模块的无线收发器包括发送、接收、 空闲和休眠四种工作模式。从图中可以看出，传感器节点的能量绝大部分用于通 信模块中的数据处理和传输，而传感器模块中用于保持连续监测状态以及监测和 报告事件所消耗的能量很小，几乎可以忽略。 7 的研究与分析 接收。理论 这些能耗基 本上是固定的。发送数据的消耗的能量主要用于两方面：一是电子元件进行必要 的频率合成和转换以及滤波等，这部分能量基本上是固定的；一是用于产生射频 信号，其与调制方式和发送距离有关，由发射功率决定。 传感器节点的体积小、电池容量小，对其充电又较复杂且不稳定，而感知、 计算和通信等功能对能量的需求较大，所以必须严格控制节点的功耗。为了充分 利用传感器节点的能量，应针对具体应用，动态调整节点的发送功率，在保证可 靠通信的前提下，尽可能地降低通信能耗。 2 1 2w s n 体系结构和能耗特点 无线传感器网络由传感器节点、汇聚节点( s i n kn o d e ，或基站) 和管理节点 组成，可构成多种类型的体系结构，如图2 3 所示。传感器节点一般通过人工、 机械、飞行器空投等方式随机地分布于监测区域，且布置好后基本固定不动，以 自组织的方式构成无线网络。 一一一、 图2 3 无线传感器网络体系结构 传感器节点负责采集监测区域的数据，在网络功能上，每个节点都具有传统 8 硕士学位论文第二章w s n 中分簇算法和路由问题的研究与分析 网络的终端和路由器双重功能，不仅要采集监测信息和数据处理，还应能够存储、 融合及转发其他节点信息，同时还要与其它节点协作完成特定任务。 s i n k 节点负责汇聚采集数据并通过因特网或其他链路将监测数据传输到远 程终端用户，一般位于监测区域外。s i n k 节点具有较强的处理信息、存储和通信 能力，它是连接w s n 与i n t e m e t 等外部网络的纽带，可将不同网络协议相互转 换，同时向传感器节点发送控制命令，并把传感器节点采集的信息转发到外部网 络上。 在w s n 中，传感器节点采用单跳或多跳中继传输的方式将数据传送到s i n k 节点，对于长距离单跳传输数据的节点来说，将造成较大的传输能耗；对于承担 中继转发任务的节点来说，将造成额外的通信负载和能耗，这会导致网络中部分 节点由于能量消耗过快而提前失效，影响网络性能和生存时间。 因此，在设计网络协议时，应充分考虑到数据传输过程中，由于节点的分布 不同而造成的节点通信负载和能耗不均的情况，降低由于节点负载的不均衡问题 对网络性能和生存时间造成的影响。 2 1 3 能耗特点对设计网络协议的需求 提高w s n 的能量利用率，不仅需要均衡单个节点的能量消耗，防止单点失 效对网络性能造成影响，又要降低网络的总体能耗，延长网络生存周期，所以设 计网络协议时，需在满足具体应用的前提下，注意以下方面： 首先，必须明确w s n 是以数据为中心的网络，用户只关注节点监测到的数 据而非节点识别，这样在网络设计时就可以只采用直接近邻的局部信息，以便有 效利用网络的能量。 其次，为了减少网络的能耗，需在保证网络性能的前提下，尽量减少无线信 道中传输的数据量以及尽量降低节点的发送功率。若需要实现长距离数据传输， 必须限制使用较大的发送功率，考虑将某些节点作为中继节点使用，这样可有效 降低传输过程中的总能耗。因此，多跳通信将会成为w s n 网络设计的一个必要 条件。而路由可以决定多跳通信中数据的传输路径，因此路由协议的设计将对单 个节点的通信负载和能量消耗方面起到至关重要的作用。在路由协议的设计过程 中，不仅需要关注链路上总的能量消耗问题，还要注意单个节点的能量消耗均衡 问题，这样才能有效延长网络的生存时间。 第三，为了尽可能的延长网络生存时间，节能操作也是一项关键技术。由于 传感器节点的能量有限，充分合理地利用节点能量是需要研究的根本问题之一。 研究的方面包括如何动态调整节点的发送功率来保证节点问数据传输的高效性； 如何有效判定路由请求消息；如何避免节点能量消耗的不均衡问题等。 9 硕士学位论文 第二章w s n 中分簇算法和路由问题的研究与分析 第四，由于传感器节点的计算和处理等能力受限，应设法使得节点在协议处 理过程中只累积直接相邻的节点信息，即只获取局部网络信息。将局部性原理与 有效协议设计结合起来，也是一个需要研究和注意的问题。 最后，为了有效延长网络生存时间，还要充分利用权衡关系。对于复杂算法 的最优化问题近似求解，在计算能耗和近似解之间采取一种组合方法以便最佳分 配功耗。另外，要在整个网络的较长生存周期和单个节点的有效时间之间进行折 中，这在提高能量效率方面也是非常有用的。 2 2 无线传感器网络分簇算法分析 网络层的设计对网络性能的好坏有着重要的影响，而分簇网络体系结构以其 拓扑管理方便、数据融合简单、能量利用率高等优点，逐渐得到了最为广泛的关 注和应用。因此，研究分簇算法对于提高w s n 的性能具有重要的意义。 2 2 1 分簇网络的特点与优势 网络层的路由选择对w s n 的性能好坏有着重要的影响，从网络的拓扑角 度，路由协议可分为平面路由协议和分簇路由协议两类。采用平面路由协议的网 络，所有传感器节点地位平等，所有节点通过相互协同生成路由，通信丌销大。 采用分簇路由协议的网络，每个簇只选出一个节点负责与外部通信，路由相对简 单，可有效降低通信开销。本文重点研究w s n 分簇的体系结构及路由协议，所 以重点介绍分簇网络结构的特点和优势。 采用分簇结构的网络可根据某种关联划分为不同的簇( c l u s t e r ) ，每个簇包 括一个簇头节点( c l u s t e rh e a d ，c h ) 和多个簇内成员节点( c l u s t e rm e m b e r , c m ) ， 而且高一级网络中的c m 是低一级网络中的c h ，如图2 _ 4 所示。 图2 1 4 分簇网络的拓扑结构图 l o u s t e rm e m b e r 硕十学位论文 第二章w s n 中分簇算法和路由问题的研究与分析 在分簇网络中，c h 和c m 在数据采集和传送过程中需要承担不同的任务和 角色。c m 的任务是将将监测数据传送给所属簇的c h ；c h 用于管理和控制本簇 内的c m 、协调c m 之间的工作、收集c m 的监测数据并进行初步融合，然后发 送到s i n k 节点( 基站) 。在大规模网络中，部分c h 节点还需充当多跳传输的中 继节点的角色，以降低长距离通信时的网络能耗。 分簇网络与平面网络相比，具有非常大的优势【5 6 1 ，主要体现在以下方面： 首先，分簇结构是基于某种策略选举产生的，网络结构较为稳定，可有效降 低网络拓扑结构的变化对网络协议造成的影响； 其次，簇头节点将簇内成员节点的监测数据先融合再转发，减少了无线通信 链路上的数据量，并通过减少参与路由的节点数量，降低通信开销和链路维护开 销，从而达到节约网络能量的目的； 再次，分簇结构便于管理，s i n k 节点通过簇头节点可以方便有效地向网络中 的成员节点发送命令，适合采用分布式算法，具有较好的扩展性，适合大规模网 络。这是平面结构的网络不能有效实现的。 2 2 2 经典分簇算法的分析和比较 分簇路由协议大致可分为三个阶段：选举簇头、成簇及簇间数据传输。其中， 合理的选举簇头算法是形成优质簇的基础，簇结构可在一定程度上决定簇间数据 传输的方式。已有的w s n 分簇路由算法大都是围绕如何选取簇头、如何成簇、 如何传输数据这三方面来设计的。 根据不同的分簇策略，国内外研究人员已研究出许多优秀的算法和协议，有 的协议设计了从选举簇头到数据传输的完整算法，有的协议只针对某一阶段提出 了新的思路。总得来说，无论在哪个阶段采用何种算法，都是围绕网络能量的高 效利用束设计和实现的。本节只关注簇结构的形成，因此着重从选举簇头和成簇 两方面分析现有的分簇路由协议。 1 簇头选举 簇头选择可基于节点的剩余能量、簇头到基站的距离、簇头分布位置以及簇 内通信代价等，簇头选举算法大致可分为集中式和分布式两种类型。分布式算法 主要包括l e a c h 和h e e d 等，集中式算法有l e a c h c 、l e a c h f 和c e f l 等。 l e a c h ( 1 0 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 ) 低能量自适应分簇协议t 2 2 1 是w s n 中最为经典的一种分簇协议。l e a c h 协议的每一轮都划分为两个阶段： 在簇的建立阶段，以一定的概率随机选择簇头，所有节点都生成一个随机数a e ( 0 - 1 ) ，若口 即砂，则该节点向周围节点广播它是簇头的消息。删的计算如公 式( 2 1 ) 所示： 硕+ 学位论文第二章w s n 中分簇算法和路由问题的研究与分析 丁( 刀) ：t p 丽硼，? ( 2 1 ) 【0 ， 拧芒g 其中：p 是网络中的最优簇头比( 即p = k n ，k 是理论上的最优簇头数，门为 网络中的节点总数) ；，是当前轮数；g 是在最后的1 勿轮中未当选过簇头的节点 集合。 每轮循环开始时，从节点集g 中选举出n p 个簇头节点。所以在第，轮循环 开始，g 中的每个节点成为簇头的概率为p ( 1 - p * ( r m o d l p ) ) 。这个概率随着循环 次数的增大而增大，使得在i p - 1 次循环中，所有从未当选过簇头的节点的概率 为l ，这保证了在l 勿循环中，每个节点成为簇头的机会都只有一次。在第l 勿+ 1 次循环中，整个过程重新开始。簇头的轮换机制将簇头的额外丌销平均分配到所 有节点上，从而达到均衡节点能量消耗的目的。 选举出簇头后，其他节点根据接收信号的强弱选择簇头加入，成簇之后进入 稳定运行阶段，簇内节点持续采集监测数据，并根据簇头分配的时隙向簇头发送 数据，簇头接收到数据后进行数据融合，去除冗余信息，再将数据发送到s i n k 节点，这种工作模式有利于减小网络中的数据传输量。 l e a c h 只是随机选取簇头，对节点的剩余能量没有限制，所以不能保证节 点的负载均衡。l e a c h d c h s 2 3 1 在计算丌矽时，将能量因素考虑进去，提出新 的闽值计算方法，如公式( 2 - 2 ) 所示： i j l 1 枣e n c u r ， 胛g 丁( 甩) = 1 - p r m o d (