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

r e s e a r c ha n dd e s i g no fe 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 g a l g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r k s c a n d i d a t e ：x i n gf e i a d v i s o r ：a s s o c i a t ep r o f w a n gx i a o d o n g at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t s f o rt h ep r o f e s s i o n a ld e g r e eo fm a s t e ro fe n gin e e r i n g i nc o m p u t e rt e c h n o l o g y 一 一一 g r a d u a t es c h o o lo fn a t i o n a lu n i v e r s i t yo fd e f e n s e t e c h n o l o g y c h a n g s h a ，h u n a n ，p r c h i n a m a r c h ，2 0 1 0 舢7删9 黼9燃 舢1舢y 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：玉堡佳盛墨圆缝整能金箧整由簋洼盟窥曼遮i 学位论文作者签名： 壁垒 日期：函胗年7 月乡日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：歪堡佳盛墨圜缝茔能金筮整由篡洼盟塞生遮! 土 学位论文作者签名： 叠堡 作者指导教师签名：羔垒查： 日期：函归年多月乡日 日期：j p 扣年6 月岁日 国防科学技术大学研究生院工程硕士学位论文 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 无线传感器网络概述l 1 1 。1 无线传感器网络概念l 1 1 2 无线传感器网络体系结构1 1 1 3 无线传感器网络特点2 1 2 无线传感器网络的发展历史与研究现状3 1 2 1 无线传感器网络发展历史3 1 - 2 2 无线传感网络研究现状4 1 3 本文研究主要内容4 1 4 论文的组织结构5 第二章相关研究工作6 2 1 无线传输能量模型6 2 2 无线传感节点能耗分析j 一6 2 3 可接收信号强度指示7 2 3 1 可接收信号强度指示原理7 2 3 2 无线信号传播模型8 2 4 无线传感网络分簇算法分析1 0 2 4 1 分簇路由算法概述1 0 2 4 2 分簇路由算法评价指标1 3 2 4 3 现有分簇路由算法分析1 4 2 4 4 典型分簇路由算法对比总结1 9 2 5 本章小结2 1 第三章基于负载特征信息的簇首轮换机制算法一2 2 3 1 算法设计思想2 2 3 2 网络模型与相关定义2 3 3 2 1 网络模型2 3 3 2 2 相关定义2 3 3 3 算法实现与分析2 4 3 3 1 算法实现2 4 第1 页 国防科学技术大学研究生院工程硕士学位论文 3 3 2 算法分析2 7 3 4 本章小结2 8 第四章基于r s s i 值的无线传感网络梯度分簇路由算法一2 9 4 1 算法设计目标2 9 4 2 算法设计思想3 0 4 2 1 层次与簇的建立3 l 4 2 2 簇内节点单跳通信3 2 4 2 3 路由树的生成3 2 4 2 4 簇首的动态轮换3 3 4 3网络模型与相关定义3 4 4 3 1 网络模型3 4 4 3 2 相关定义3 4 4 4 算法实现与分析3 6 4 4 。1 梯度标识3 6 4 4 2 簇的建立3 6 4 4 3 梯度路由树建立3 8 4 4 4 系统稳定运行4 0 4 4 5 簇首轮换4 l 4 4 6 算法分析4 2 4 5 本章小结4 4 第五章算法模拟与分析一4 5 5 1n s 2 模拟工具简介4 5 5 2n s 2 模拟建模一4 6 5 2 - 1n s 2 中消息类型模型一4 6 5 2 2n s 2 中普通节点模型4 6 5 2 3n s 2 中簇首节点模型4 7 5 2 4n s 2 中基站b s 模型4 9 5 2 5n s 2 中模拟整体流程4 9 5 - 3 性能评价指标5 0 5 4 基于负载特征信息的簇首轮换机制算法模拟与分析5 l 5 4 1 模拟场景5 1 5 4 2 模拟数据分析5l 5 5 基于r s s i 值强度的梯度分簇路由算法模拟与分析5 3 5 5 1 模拟场景5 3 第页 国防科学技术大学研究生院工程硕十学位论文 5 5 2 模拟数据分析5 3 5 6 本章小结5 6 第六章总结与展望5 7 6 1 论文总结5 7 6 2 未来工作展望5 8 致谢5 9 参考文献6 0 作者在学期间取得的学术成果6 4 第页 国防科学技术大学研究生院工程硕士学位论文 表目录 表2 1 p a s sl o s s 指数的几种典型值9 表2 2 分簇路由算法性能对比2 0 表2 3 分簇路由算法各阶段能耗对比2 0 表3 1 节点状态信息表t a b l e m 。m b e r 示例2 5 表3 2 基于负载特征信息的簇首轮换机制实现伪代码2 6 表4 1 梯度路由树建立过程实现伪代码3 9 表5 1 簇首轮换模拟场景参数5 1 表5 2 分簇路由算法模拟场景参数5 3 第1 v 页 国防科学技术大学研究牛院工程硕士学位论文 图目录 图1 1传感器网络体系结构图1 图1 2 传感器节点体系结构图2 图2 1 一阶无线传输能量模型6 图2 2 传感器节点能耗示意图7 图2 3 无线传感器网络分层体系结构图。1 l 图2 4 无线传感器网络多跳分簇路由结构图1 l 图2 5 簇生成算法的流程图1 2 图2 6l e a c h 的组织结构图15 图2 7 聚类分层路由树图1 9 图3 1l e a c h f 簇首轮换机制示意图2 2 图3 2 固定聚类分簇算法簇首轮换机制示意图2 3 图3 3 节点能耗与通信量关系2 4 图3 4 基于负载特征信息的簇首轮换机制示意图一2 5 图3 5 基于负载特征信息轮换机制流程图2 6 图4 1多层非均匀分簇示意图一3l 图4 2 路由树示意图一3 3 图4 3 簇首动态轮换示意图3 3 图4 4 节点状态转换示意图一3 5 图4 5 簇的形成流程图。3 7 图4 6 梯度路由树建立流程图3 9 图4 7 网络结构示意图一4 1 图4 8 系统运行流程图一4 2 图4 9 分析模型4 3 图5 1n s 2 结构图。4 5 图5 2 普通节点流程图4 7 图5 3 簇首节点流程图一4 8 图5 4b s 工作流程图4 9 图5 5 模拟整体流程图5 0 图5 6网络生命周期一5 2 图5 7 数据总量与总能耗的关系一5 3 图5 8 节点剩余能量比较5 4 图5 9网络总能量消耗比较一5 5 第v 页 国防科学技术大学研究生院工程硕士学位论文 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 是结合了传感器技术、通信技 术及计算机技术的产物。该网络能够通过传感器节点之间的协作实时地监测、感 知和采集网络区域内各种环境或被监测对象的信息，并对这些信息进行处理，传 送到需要这些信息的用户，在我们感知的物理世界和逻辑信息世界之间建立起一 条信息纽带。 w s n 的巨大应用价值，已经引起了许多国家军事部门、工业界和学术界的关 注，并广泛应用于军事、工业过程控制、国家安全、环境监测等领域。无线传感 器网络是由许多具有低功率无线收发装置的传感器节点组成，由于其节点的电池 能量有限，因此节点的通信应有效地利用能量，以延长网络的生命周期。 本文正是以此为研究背景，分析和比较了文献中提出的多种无线传感器网络 分簇路由协议，借鉴其优秀的思想，提出了一种基于负载特征信息的簇首轮换机 制算法和一种基于r s s i 值的无线传感器网络梯度分簇路由算法( r s s ib a s e d g r a d i e n tc l u s t e r i n ga l g o r i t h m ，r g c ) 。 基于负载特征信息的簇首轮换机制算法主要针对目前簇首节点轮换机制中存 在的通信过程复杂、能耗高等不足，以减少簇首轮换时节点通信量为出发点，结 合传感器节点能耗分析，对簇工作过程中节点的通信次数以节点负载的概念进行 量化，实现了簇首节点根据成员节点通信负载特征信息自主选择具有最低能耗的 节点担任新一轮簇首的功能。这种方式对比于其他很多算法中需要大多数节点都 参与的簇首轮换过程，有效的减少簇首轮换时节点问通信量，降低轮换的复杂度 和能耗，延长了整个网络的生命周期。 基于r s s i 值的无线传感器网络梯度分簇路由算法主要针对无线传感网络在数 据收集模式下的节点负载不均衡问题。算法通过让各节点接收b s 的统一广播信 息，根据信息中的r s s i 值及预设的梯度空间，标识自身所在的区间，以此建立梯 度，形成大小不同的层次结构，有效地缓解了“热区 问题的出现；同时在不同 梯度与相同梯度的簇首节点间建立树状梯度路由结构，通过节点间的多跳传输， 减少与b s 直接通信的远距离簇首节点，因而减少了网络开销；算法的簇首轮换采 用本文提出的基于负载特征信息的簇首轮换机制，降低了算法复杂度，减少节点 通信量及全网能量开销。 最后，利用n s 2 模拟工具对上述两种算法进行了模拟。实验结果显示，本文 提出的基于负载特征信息的簇首轮换机制算法及基于r s s i 值的梯度分簇路由算法 在有效减少节点通信量、降低系统能耗、延长网络生命周期和提高数据精度上达 到了预期目标，效果较明显。 第i 页 国防科学技术大学研究生院工程硕士学位论文 关键词：无线传感器网络，负载特征信息，可接收信号强度，梯度，分簇 第i i 页 国防科学技术大学研究生院工程硕士学位论文 a b s t r a c t w i r e l e s ss e n s o r n e t w o r k ( w s n ) c o m b i n e s o f s e n s o r , c o m p u t i n g a n d c o m m u n i c a t i o nt e c h n o l o g y ，a n dc a l lb eu s e df o r s e n s i n g ，t e s t i n g ，c o l l e c t i n ga n d p r o c e s s i n gi n f o r m a t i o no rm o n i t o r e do b j e c t s al i n ki s e s t a b i l i s h e db e t w e e no u r p e r c e p t i o no ft h ep h y s i c a lw o r l da n dt h el o g i cw o r l dt h r o u g hw s n t h ea p p l i c a t i o n so fw s nh a sc a u s e dm a n yc o u n 打i e si nt h ew o r l do ft h em i l i t a r y d e p a r t m e n t s i n d u s t r ya n da c a d e m i ae x t e n s i v ea t t e n t i o n b e c a u s eo ft h et r e m e n d o u s v a l u e ，i th a sb e e nw i d e l yu s e di nm i l i t a r y ，i n d u s t r i a lp r o c e s sc o n t r o l ，n a t i o n a ls e c u r i t y ， e n v i r o n m e n t a lm o n i t o r i n ga n do t h e rf i e l d s w s nc o n s i s t so fa1 a r g en u m b e ro fs m a l l s e n s o r sw i t hl o w - p o w e rt r a n s c e i v e r s i n c ean e t w o r kc o n s i s t so fs e n s o r sw i t hl i m i t e d b a t t e r ye n e r g y ，t h em e t h o df o rd a t ag a t h e r i n ga n dr o u t i n gm u s tb ee n e r g ye f f i c i e n ti n o r d e rt op r o l o n gt h el i f e t i m eo ft h en e t w o r k b e g i n i n gw i t ht h i sb a s i ci d e a , w ea n a l y z e da n dc o m p a r e ds o m er o u t i n gp r o t o c o l s t l l a tw e r ep r o p o s eb yo v e r s e ar e s e a r c h e r s a n dt h e np r e s e n tt h el o a dc h a r a c t e r i s t i c s b a s e dc l u s t e rh e a dr e n e w i n gm e t h o da n dt h er s s ib a s e dg r a d i e n tc l u s t e r i n g ( r g c ) a l g o r i t h m t h es c h e m eo fl o a dc h a r a c t e r i s t i c sb a s e dc l u s t e rh e a dr e n e w i n g ，w h i c he x p l o i t s n o d el o a dt oq u a n t i f y 仃a n s m i s s i o nt i m e so fn o d e si np r o c e s so fc l u s t e rr u n n i n g a i m sa t r e d u c i n gc o m m u n i c a t i o nt i m e so fn o d e sd u r i n gc l u s t e rh e a dr e n e w i n gt oo v e r c o m et h e s o m ed r a w b a c k si ne x i s t i n gs c h e m e so fc l u s t e rh e a ds e l e c t i o n ，s u c ha sc o m p l i c a t i o no f c o m m u n i c a t i o np r o c e s s ，h i g he n e r g yc o s t ，e t c a c c o r d i n gt ot h ee n e r g yc o s ta n a l y s i so f n o d e s t h es c h e m ep r o p o s e di nt h i sp a p e ri m p l e m e n t st h ef u n c t i o nt h a tt h ec u r r e n t c l u s t e rh e a ds e l e c t st h el o w e s te n e r g yc o s tn o d ea st h en e x tc l u s t e rh e a da u t o n o m o u s l y b a s e do nt h ec o m m u n i c a t i o nl o a dc h a r a c t e r i s t i c so fi n t r a - c l u s t e rn o d e s t om i n i m i z et h e a m o u n to fc o m m u n i c a t i o no fn o d e sd u r i n gc l u s t e rh e a dr e n e w i n g ，r e d u c er e n e w c o m p l e x i t ya n de n e r g yc o s t , a n dp r o l o n gt h el i f et i m eo f t h ew h o l en e t w o r k s t h er g ca l g o r i t h md e s i g n e df o rw i r e l e s ss e n s o rn e t w o r kr e s o l v e st h ep r o b l e mo f l o a du n b a l a n c eo fn o d e si nc o n s i d e r a t i o nf o rt h es p e c i f i cm o d eo fd a t ac o l l e c t i o ni n w i r e l e s ss e n s o rn e t w o r k t h i sa l g o r i t h mb u i l d sg r a d i e n tz o n eb ye x p l o i t i n gb st o b r o a d c a s tu n i f o r m l y ，a n de a c hn o d ec o n s t r u c t sg r a d i e n ti na s s i g n e dz o n et of o r m g r a d a t i o ns t r u c t u r eb yr s s io fr e c e i v e dm e s s a g e s t h ec o n s t r u c t i o no fg r a d i e n tr o u t i n g t r e ei sb a s e do nt w od i f f e r e n tg r o u n d s ：c l u s t e rh e a d sw i t ht h es a m eg r a d i e n to rn o t ，a n d t h ec l u s t e rh e a dr e n e wb a s e do nl o a dc h a r a c t e r i s t i c sr e d u c e sn o d e sc o m m u n i c a t i o n , a l g o r i t h mc o m p l e x i t ya n ds y s t e me n e r g yc o s t i nt h ee n d , t h ea l g o r i t h mp r o p o s e di nt h ep a p e ri ss i m u l a t e db yn s 一2s i m u l a t o r t h er e s u l t so fs i m u l a t i o ns h o w st h a tt h es c h e m eo fl o a dc h a r a c t e r i s t i c sb a s e dc l u s t e r h e a dr e n e w i n ga n dt h er s s i - b a s e d g r a d i e n tc l u s t e r i n ga l g o r i t h m a r e c a p a b l e o f 第i i i 页 国防科学技术大学研究牛院工程硕士学位论文 r e d u c i n gn o d e sc o m m u n i c a t i o na n ds y s t e me n e r g yc o s te f f e c t i v e l y t h ep e r f o r m a n c eo f p r o l o n g i n gn e t w o r kl i f ea n di m p r o v i n gd a t aa c c u r a c yi so p t i m i z e do b v i o u s l y k e yw o r d ：w i r e l e s ss e n s o rn e t w o r k , l o a dc h a r a c t e r i s t i c ，r s s i ， g r a d i e n t , c l u s t e r i n g 第i v 页 国防科学技术大学研究生院工程硕士学位论文 第一章绪论 1 1 无线传感器网络概述 1 1 1 无线传感器网络概念 随着通信技术、嵌入式计算及传感器技术的发展和日益成熟，无线传感器网 络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 技术引起了人们广泛关注。 无线传感器网络是由部署在监测区域内的大量廉价微型传感器节点组成，通 过无线通信方式形成一个多跳的自组织网络系统，其目的是协作地感知、采集和 处理网络覆盖区域中感知对象的信息，并发送给观察者【1 1 。 1 1 2 无线传感器网络体系结构 无线传感器网络中通常包括传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 和 管理节点。传感器节点监测的数据沿着其他传感器节点逐跳地进行传输，经过多 跳后路由到汇聚节点，最后通过互联网或卫星到达管理节点。用户通过管理节点 对传感器网络进行配置和管理，发布监测任务以及收集监测数据 2 1 。其网络结构如 图1 1 所示。 监测区域 传感器节点 图1 1 传感器网络体系结构图 传感器节点是一个微型的嵌入式系统，它的处理、存储和通信能力都相对较 弱，通常只携带能量有限的电池供叫3 1 。从网络功能上看，每个传感器节点都兼顾 终端和路由器双重功能，除了进行本地信息收集和数据处理外，还要对其他节点 转发来的数据进行存储、管理和融合等处理。传感器节点由传感器模块、处理器 模块、无线通信模块和能量供应模块四部份组成，如图1 2 所示。 第l 页 国防科学技术大学研究生院工程硕士学位论文 1 1 3 无线传感器网络特点 图1 2 传感器节点体系结构图 无线传感器网络的主要特点如下【4 1 ： 大规模性 为了获取精确信息，在监测区域通常部署大量传感器节点。大规模性包括两 方面含义：一方面是传感器节点分布在很大的地理区域内；另一方面，传感器节 点部署一般比较密集。 自组织性 在传感器网络应用中，通常情况下传感器节点被放置在没有基础结构的地方。 传感器节点的位置不能预先精确设定，节点之间的相邻关系预先也不知道，这样 就要求传感器节点具有自组织能力，能够自动进行配置和管理，通过拓扑控制机 制和网络协议自动形成转发监测数据的多跳无线网络系统。 动态性 因为环境因素或电能耗尽造成传感器节点出现故障或失效；传感器网络的拓 扑结构会随时间而动态改变；环境条件变化也可能造成无线通信链路带宽变化， 甚至时断时续等。这就要求传感器网络系统要能够适应各种变化，具有动态的系 统可重构性。 可靠性 由于监测区域环境的限制以及传感器节点数目巨大，不可能人工“照顾 每 个传感器节点，网络的维护十分困难甚至不可维护；传感器网络的通信保密性和 安全性也十分重要，要防止监测数据被盗取和获取伪造的监测信息。因此，传感 器网络的软硬件必须具有较好的鲁棒性和容错性。 应用相关性 第2 页 国防科学技术大学研究牛院工程硕士学位论文 对于不一的传感器网络应用虽然存在一些共性问题，但在开发传感器网络应 用中，更关心传感器网络的差异。只有让系统更贴近应用，才能设计和实现最符 合应用需求的目标系统。针对每一个具体应用来研究传感器网络技术，这是传感 器网络设计不同于传统网络的显著特征。 1 2 无线传感器网络的发展历史与研究现状 1 2 1 无线传感器网络发展历史 无线传感器网络最初来源于美国国防高级研究计划署( d e f e n s ea d v a n c e d r e s e a r c hp r o j e c t sa g e n c y ，d a r p a ) 的一个研究项引5 】【6 】【丌。广泛研究起始于2 0 世 纪9 0 年代末期。1 9 9 8 年以来，由美国国防部支持的关于无线自组织传感器网络的 项目屡屡在论文中出现。美国国防部和各军事部门都对传感器网络给予了高度重 视，设立了一系列的军事传感器网络研究项目。美国英特尔公司、微软公司等信 息工业界巨头也都开始了传感器网络方面的研究工作，纷纷设立或启动相应的行 动计划。例如：i n t e l 公司在2 0 0 2 年制订了基于微型传感器网络的新型计算发展规 划；n s f 在2 0 0 3 年制定了传感器网络研究计划；美国d u s tn e t w o r k s 和c r o s s b o w t e c h n o l o g i e s 等公司的“智能尘埃”、“m o t e ”项目己进入应用测试；日本、英国、 意大利、巴西等国家也都展开了针对传感器网络的研究工作。但是，目前大部分 研究尚处于起步阶段，少数投入实用的商业产品距离实际需求也还相差甚远。为 了加快其实用化进程，国外建设了很多演示系统，相关的理论研究成果也很多 8 1 1 9 1 f 1 0 1 ，其中比较重要的研究计划有：p i c o r a d i o f l l l 、w i n s 12 1 、s m a r td u s t 13 1 、 u a m p s t l 4 1 、s c a d d s 【1 5 1 等。 近年来，我国政府和专家学者也开始关注传感器网络的发展。在我国，现代 意义的无线传感器网络及其应用研究几乎是与发达国家同步启动，首次正式出现 于1 9 9 9 年中国科学院的“信息与自动化领域研究报告 中，把传感器网络作为该 领域提出的五个重大项目之一。2 0 0 1 年上海微系统所成立微系统研究与发展中心， 在无线传感器网络方向上相继部署了若干重大研究项目。2 0 0 4 年末，8 6 3 计划信 息获取与处理技术主题年会上，与会的专家学者普遍认为传感器网络已经成为信 息获取领域的发展重点。在中国国家自然科学基金、国家“8 6 3 计划基金的支持 下，国内的一些研究机构包括中国科学技术大学、清华大学、中科院计算机所以 及合肥智能所等单位，也开始开展无线传感器网络领域的研究。可以预计，无线 传感器网络的发展和广泛应用，将对人们的社会生活和产业变革带来极大的影响 和产生巨大的推动【l6 1 。 第3 页 国防科学技术大学研究生院r t 程硕十学位论文 1 2 2 无线传感网络研究现状 目前为止，传感器网络的研究大致经过了两个阶段。第一阶段主要偏重利用 m e m s 技术设计小型化的节点设备，其代表性的研究项目有w i n s 和s m md u s t 等。传感器网络研究的第二个阶段是对于网络本身问题的关注和研究，这也是当 前的研究热点【1 7 】。除了网络自身的问题以外，还有许多关键问题也引起了研究者 广泛的兴趣，比如传感器节点的定位问题【1 引，动态功率管理【1 9 1 ，时钟同步【2 0 1 ，软、 硬件的没计和制造【2 1 】等。从网络分层模型的角度分析，每一层都有需要结合传感 器网络的特点进行细致的研究，就已有研究而言，主要集中在网络层口2 1 1 2 3 1 1 2 4 1 和链 路层2 5 1 1 2 6 1 1 2 7 1 。其中，网络层协议负责路由发现与维护，是无线传感器网络的重要 因素，一个网络设计的成功与否，路由协议非常关键。 在无线传感器网络的研究初期，人们一度认为成熟的i n m e t 技术加上a dh o c 路由机制对传感嚣网络的设计是足够充分的，但深入的研究表明，传感器网络有 着与传统网络明显不同的技术要求。前者以数据为中心，后者以传输数据为目的。 为了适应广泛的应用程序，传统网络的设计遵循着“端到端 的思想，强调将一 切与功能相关的处理都放在网络的端系统上，中间节点仅仅负责数据分组的转发， 对于传感器网络，这未必是一种合理的选择。一些为自组织的a dh o e 网络设计的 协议和算法未必适合传感器网络的特点和应用的要求。所以，无线传感器网络协 议和算法上与传统网络有很大的不同，这也是当前无线传感器网络研究的关键技 术之一。 1 3 本文研究主要内容 本文所研究的内容是如何更高效地使用传感器节点能量以最大化网络生命周 期。将网络分簇是降低能耗、延长网络生命周期的一个非常重要的方法【2 8 1 。分簇 不仅可以提高网络的可扩展性，而且将整个网络划分为簇可以避免信道冲突，有 效提高信道利用率。同样避免每个节点都与基站( b 弱es t a t i o n ，b s ) 通信带来的能量 开销，普通节点只需要与簇首节点进行通信，这对数据通信占能耗绝大部分的无 线传感器网络来说，可以明显减少能耗。虽然将网络分簇有着诸多的优点，但是 同样也带来一些问题，比如能耗均衡的问题。在多跳的分簇网络中，簇首之间的 多跳通信使得距离b s 近的簇首不仅要承担本簇内的数据收集工作，还要处理来自 其它簇首的转发数据，造成簇首节点的能量过早耗尽，因此离b s 越近的节点能量 消耗就越快；簇首轮换时采取节点之间能量比较，通信量较大，节点能耗相应较 高，造成整个网络生命周期缩短。本文针对多跳分簇路由算法中存在的上述问题， 完成了以下四个方面的工作： 第4 页 国防科学技术大学研究生院工程硕士学位论文 1 重点研究无线传感器网络中几种具有代表性的分簇路由协议，并对各种协 议进行比较，分析存在的不足。 2 针对目前簇首轮换机制中存在的节点间通信量大，能量消耗高等不足设计 了一种基于负载特征信息的簇首轮换机制。 3 以均衡节点能耗、降低网络能量开销、有效延长网络生命周期为目标，针 对目前分簇路由协议在层次划分、成簇算法、数据传输方式存在的不足，设计了 一种基于r s s i 值划分梯度进行分簇的能量高效分簇路由算法r g c ，并对算法进行 理论分析。 4 利用n s 2 模拟工具对所提出的两种算法进行模拟，并与基于固定聚类算法 的簇首轮换机制和c h tl e a c h 分簇路由算法及l e a c h 协议进行比较，验证所 提出算法的可行性及有效性，并得出相关结论。 1 4 论文的组织结构 第一章为绪论，首先简要介绍无线传感器网络的基本概念，无线传感器网络 的体系结构、特点、发展历史和研究现状，最后介绍本文所做的工作。 第二章为相关研究工作，介绍与本课题相关的研究工作，包括无线传输下的 能量模型、无线传感器节点能耗问题、基于r s s i 的研究工作以及分簇式路由协议 的特点和性能优势；描述了在无线传感器网络中基于分簇的路由协议应该满足的 几个目标，分析现有的几种典型协议存在的不足，为提出新的分簇路由算法奠定 了基础。 第三章为基于负载特征信息的簇首轮换机制，首先介绍算法的设计思想，对 负载特征信息及相关内容进行定义，重点阐述基于负载特征信息的簇首轮换机制 算法的实现，并对算法进行理论分析。 第四章为基于r s s i 值的无线传感器网络梯度分簇算法，首先介绍算法的设计 思想，对以r s s i 值为基础建立梯度的过程及相关内容进行定义，重点阐述基于 r s s i 值的无线传感器网络梯度分簇路由算法具体实现的过程，并对算法进行理论 分析。 第五章为算法模拟与结果分析，首先介绍n s 2 模拟工具，然后利用n s 2 对本 文提出的基于负载特征信息的簇首轮换机制及基于r s s i 值的梯度分簇路由算法进 行模拟，并对模拟结果进行分析和比较，以评价算法的性能。 第六章总结与展望，对本文所做工作进行总结，并指出需要进一步研究的问 题。 第5 页 国防科学技术大学研究牛院工程硕士学位论文 第二章相关研究工作 2 1 无线传输能量模型 由于无线传感器网络路由算法的设计首要考虑的因素是能量问题，所以路由 算法的设计与信道能量消耗模型息息相关。如图2 1 所示，信道能量消耗通常采用 一阶无线传输能量模型( f i r s to r d e r r a d i om o d e l ) ，该模型有如下几个明显特征： ( 1 ) 该模型中网络中所有传感器节点完全相同，并且能量有限。 ( 2 ) b s ( b a s es t a t i o n ) 位置固定并且离网络中的传感器节点较远。 ( 3 ) 无线电信号在各个方向上消耗的能量相同。 图2 1一阶无线传输能量模型 在这种模式中，传感器节点发送k b i t 数据所消耗的能量为： e t x ( 尼，d ) = 一妇( 庀) + - a m p ( 后，d ) = k x ( e 泐+ 乞唧d 7 ) 式( 2 1 ) 传感器节点接收k b i t 数据所消耗的能量为： ( k ) = e 加x k 式( 2 2 ) 其中r 是信道传输能量衰减指数，e 唧是信号放大器的放大倍数，e e k 是发送 电路和接受电路消耗的能量，信号传输距离为d 。在计算通信所消耗的能量时，采 用两种能量衰减模型，分别称为自由空间模型( f r e es p a c e ) 署n 多路径衰减模型 ( m u l t i - p a t hf a d i n g ) 。信号在无线信道传输中的能量消耗与距离d r 成正比，在短距离 无线传输时d - - d o ，r = 4 ，d 0 为一个距离常数，根据发送 节点和接收节点之间的距离，发送节点可以使用不同的能耗模型计算发送数据所 需要的能量。 2 2 无线传感节点能耗分析 节能对传感器网络十分重要，包括减少单个节点的能耗和最大化整个网络的 第6 页 国防科学技术大学研究牛院工程硕士学位论文 生存期，这土要涉及到传感器节点。传感器节点消耗能量模块包括感知模块、数 据处理模块和无线通信模块。随着集成电路工艺的进步，数据处理和感知模块的 功耗变得很低。图2 2 所示是d e b o r a he s t r i n 在m o b i c o m2 0 0 2 会议上的特邀报告 t z 9 1 ( w i r e l e s ss e n s o rn e t w o r k , p m ：s e n s o rn e t w o r kp r o t o c o l s ) 中所述传感器节点各 部分能量消耗的情况，从图中可知传感器节点的绝大部分能量消耗在无线模块( 8 0 以上) 。无线通信模块可以处于发送、接收、空闲或睡眠四种状态。发送状态下 能量消耗最大，空闲状态和接受状态的能量消耗接近，略少于发送状态能量消耗， 睡眠状态下能量消耗最少。从图2 2 中可以看出，节点发送和接收数据越多，能耗 就越大，所以在设计中应尽可能的对通信模块进行优化，减少通信中信息的传输 量，避免不必要的通信【3 们。 功率( w 1 5 l o ， 无线顿- i i i i i 一一! 感知处理 ! 发送接收空闲睡眠 国防科学技术大学研究生院工程硕士学位论文 ( x l ，y 2 ) 、( x 2 ，y 2 ) 、( x 3 ，y 3 ) 。对于节点( x 。，y 。) 的任意一个邻居节点( x i ，y i ) ( i _ l ，2