（计算机应用技术专业论文）无线传感器网络分布式节能路由算法.pdf

浙江工业大学硕士学位论文 无线传感器网络分布式节能路由算法 摘要 近年来，随着嵌入式计算、传感器和现代通信等技术的飞速发展和日益成熟，使得由 各种低成本、低能耗、多功能的微型传感器组成的无线传感器网络被广泛应用于国防军事、 环境监测、抗灾救灾等领域。由于无线传感器网络中的节点一般采用电池供电，并且通常 部署于恶劣甚至危险的环境中，对它们进行电源补充非常困难，因此，设计能量有效的路 由算法以延长网络生存时间是无线传感器网络研究领域的一个重要课题。 基于簇的路由( c l u s t e r - b a s e dr o u t i n g ) 是无线传感器网络中一种重要的能量有效的路 由协议。在现有基于簇的路由协议中，簇头节点与基站( s i n k 节点) 之间存在两种通信模式： 单跳和多跳。在这两种通信模式下，簇头节点间长距离通信以及与s i n k 节点临近的节点转 发其它节点数据消耗能量过大等因素，会造成“能量洞问题 ( e n e r g yh o l ep r o b l e m ) ，从而 使得这些能量空洞区域不能继续执行监测任务，导致网络过早死亡，从而浪费大量剩余能 量。为了克服与缓解能量洞问题，本文提出了一种新的基于簇的路由协议基于网格的 隔层传输的路由算法g r a c t ( g r i d b a s e dr o u t i n ga l g o r i t h mw i t hc r o s s 1 e v e lt r a n s m i s s i o n ) 。 g r a c t 有以下优点：( 1 ) 将感知区域分成层( 1 e v e l ) 和网格( g r i d ) ，每个网格内的节点通 过竞争的方式选出唯一的簇头节点，降低了选举簇头节点的控制消息开销和处理时间；( 2 ) 采用隔层传输这一特殊的多跳传输模式来均衡簇头节点的能耗，每个簇头节点按比例p 将 其数据分组传给更靠近基站的邻层簇头节点，而将剩余的分组( 即比例卜p ) 传送给隔层簇 头节点。此外，本文为g r a c t 建立了性能分析与优化模型，提出并解决了两个优化问题( 称 之为g r a c t - i 和g r a c t - i i ) 以最小化网络总能耗和最大化网络生存时间。最后，通过仿 真实验验证g r a c t 在节约能耗，延长网络生存时间等方面的效果。本文的研究成果，可 以应用于无线传感器网络。 关键词：无线传感器网络，能量洞，节能，生存时间，分簇路由 浙江工业大学硕士学位论文 d i s t r i b u t e da n de n e r g y - s a v i n gr o u t i n g a l g o r i t h m sf o r w i r e l e s ss e n s o rn e t w o r k s a b s t r a c t r e c e n ta d v a n c e si ne m b e d d e dc o m p u t i n g ，s e n s o rt e c h n o l o g y ，w i r e l e s sc o m m u n i c a t i o n m a k ew i r e l e s ss e n o rn e t w o r k s ( w s n s ) ，w h i c hc o n s i s to fl o w c o s t ，l o w - p o w ，m u l t i f u n c t i o n a l s e n s o rn o d e s ，w i d e l yu s e di nn a t i o n a ld e f e n c ea n dm i l i t a r y ，e n v i r o n m e n tm o n i t o r i n g ，d i s a s t e r r e l i e fa n d m o r e u s u a l l y ，s e n s o rn o d e si naw s n a r ep o w e r e db yb a t t e r i e sa n di ti sv e r yd i f f i c u l t t or e c h a r g eo rr e p l a c eb a t t e r i e so fn o d e sd e p l o y e di nh a r s ho rh o s t i l ee n v i r o n m e n t a sar e s u l t ，i ti s i m p o r t a n ta n dac h a l l e n g et od e s i g ne n e r g y e f f i c i e n tr o u t i n ga l g o r i t h m st oi m p r o v el i f e t i m eo fw s n s c l u s t e r - b a s e dr o u t i n gi se n e r g y e f f i c i e n tf o raw s nt o p r o l o n gi t sl i f e t i m e b a s i c a l l y ， c o m m u n i c a t i o n sb e t w e e nc l u s t e rh e a d sa n dab a s es t a t i o n ( o rs i n k ) u n d e rc l u s t e r i n g r o u t i n g a l g o r i t h m sc a nb ec l a s s i f i e da st w oc a t e g o r i e s ：s i n g l e h o pc o m m u n i c a t i o n ( s h c ) a n dm u l t i h o p c o m m u n i c a t i o n ( m h c ) h o w e v e r ，e i t h e ri ns h co rm h c ，“e n e r g yh o l ep r o b l e m ”，w h i c h p r e v e n t st h es i n kf r o mg a t h e r i n ga l lt h ed a t ap a c k e t sg e n e r a t e db yt h en o d e si nt h ew s na n d l e a d st h ew s nt oe a r l y d e a t h ，c o u l dn o tb ea v o i d e db e c a u s eo fl o n g - h a u lc o m m u n i c a t i o n b e t w e e nn o d e sa n d o v e r l y e x p e n d e de n e r g yu s e db yn o d e sc l o s et ot h es i n kf o rr e l a y i n gp a c k e t s t oo v e r c o m e “e n e r g yh o l ep r o b l e m ”，i nt h i sd i s s e r t a t i o n ，w ep r e s e n tan o v e lr o u t i n ga l g o r i t h m ， r e f e r r e da sg r i d b a s e dr o u t i n ga l g o r i t h mw i t hc r o s s l e v e lt r a n s m i s s i o n ( g r a c t ) t h em a i n a d v a n t a g e so f t h eg r a c ta r ea sf o l l o w s ：( 1 ) t h es e n s i n gf i e l di nt h ew s ni sd i v i d e di n t ol e v e l s a n dt h e ni n t og r i d s ，w i t he a c hp r o d u c i n gac l u s t e rh e a d ( c h ) ，w h i c hr e d u c e st h ec o m p l e x i t yo f c o n t r o lm e s s a g ea n dp r o c e s s i n gt i m ed u r i n ge l e c t i n gc h s ；a n d ( 2 ) as p e c i a lm h c ，i e ，c r o s s l e v e l t r a n s m i s s i o n ，i si n t r o d u c e dt ob a l a n c e de n e r g yc o n s u m p t i o na m o n gn o d e s ，i nw h i c he a c hac hi n al e v e li so n l ya l l o w e dt ot r a n s m i tw i t hr a t i op ( 0 p s l ) o fi t s p a c k e t st ot h ec hi nt h e n e i g h b o r i n gl e v e la n dt r a n s m i tw i t hr a t i o1 - p t oac ht w ol e v e l sa p a r t ( i 。et h el e v e lc r o s s e st h e n e i g h b o r i n gl e v e l ) m o r e o v e r , ao p t i m i z a t i o nm o d e li sp r o p o s e dt oa n a l y z ea n do p t i m i z e p e r f o r m a n c eo fg r a c t e s p e c i a l l y ，t w oo p t i m i z a t i o np r o b l e m s ，r e f e r r e da sg r a c t ia n d g r a c t i ia r ep r e s e n t e dt om i n i m i z et o t a le n e r g yc o s ta n dm a x i m i z et h el i f e t i m eo ft h ew s n ， r e s p e c t i v e l y f i n a l l y ，s i m u l a t i o n sa r ec o n d u c t e dt ov a l i d a t et h ee f f e c t i v e n e s so fg r a c ti n s a v i n ge n e r g ya n dp r o l o n g i n gn e t w o r kl i f e t i m e t h eo u t c o m e sa c h i e v e di nt h ed i s s e r t a t i o nc a r lb e a p p l i e di nw s n s k e yw o r d s ：w s n ，e n e r g yh o l e ，e n e r g ys a v i n g ，l i f e t i m e ，c l u s t e r - b a s e dr o u t i n g i j 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：如五 韦 1 日期：刀年，歹月才日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“、”) 作者签名： 导师签名： 削土i ( 日期：叫年 日期：叫年 1 2 - 月以日 ，二月必日 浙江工业大学硕士学位论文 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 ) 已经引起人们的高度重视，并成为当今国内外学者争相研究的热点之一。w s n 是- - 1 7 交叉 学科，综合了嵌入式计算技术、传感器技术、无线通信技术、分布式数据处理技术等，能 够通过各类集成化的微型传感器协作地实时监测、感知、采集监测区域内各种环境或者对 象的信息，并通过信息处理技术对这些信息进行处理，然后以无线通信和自组织多跳的方 式传送给终端用户【1 】 2 【3 】。w s n 可以使人们在任何时间、任何地点和任何环境下获取大 量详细的物理世界信息，它为物理世界、计算机世界和人类社会三元世界构建了连通桥梁。 w s n 将是一场信息获取革命，将对人类未来的生活方式和生产的各个领域产生巨大影响。 美国商业周刊将无线传感器网络列为全球未来四大高科技产业之一，认为它是2 l 世 纪最具有影响力的2 1 项技术之一。麻省理工新技术评论预测w s n 将是改变世界的十大新 技术之- - 4 。 由于w s n 具有可快速部署、低成本、可自组织、高容错性和隐蔽性强等特点，w s n 在科学研究、环境监测、军事领域、医疗卫生、家庭生活、太空探索等领域具有广阔的应 用前景。特别是在我国，深入研究w s n 并应用之，对国民生活和生产等诸多领域具有深 远的意义。首先，我国是一个农业大国，农作物的优质高产对国家的经济将产生不可估量 的影响。根据实际的农业需求，w s n 以其卓越的优势可以用于农田、耕地和牧场等监测区 域，长期监测温度、湿度、降雨量等气候变化以及收集土壤湿度、酸碱度等等信息，从而 能对气候变化、土壤改变等做出科学预测，帮助人们科学种植，抵抗洪涝、害虫等灾害， 提高农作物的产量。其次，我国幅员辽阔，物种种类繁多，环境和生态问题严峻。除了用 于追踪珍稀物种外，w s n 也可以部署于地震、水灾、遭受台风地区，用于灾前预警和灾后 救援、救济等工作，以减少人员伤亡和降低国家财产损失。另外，w s n 也可以应用于我国 工业领域中工作环境危险的行业，比如煤矿、石油钻井、核电厂等。它可以将工作人员从 浙江工业大学硕士学位论文 高危险的工作中解脱出来，提高了事故险情的反应精度和速度。比如，工厂或者煤矿等相 关地点安装传感器节点，监测易燃、易爆、有毒物质，并且指挥员工的行动，以保证他们 人身的安全。 另外，我们注意到，温家宝总理于2 0 0 9 年8 月7 日视察无锡微纳传感网工程技术研 发中心时，指出“在传感网发展中，要早一点谋划未来，早一点攻破核心技术 、“在国家 重大科技专项中，加快推进传感网发展、“尽快建立中国的传感信息中心，或者叫感知 中国中心 。这将进一步推动传感器网络在中国的发展。可以说，传感器网络研发与应 用的春天到来了! 在w s n 实际的应用中，由于节点部署的随机性以及受节点本身能量、计算、存储和 通信能力的限制，传统的路由协议在w s n 中不适用，因此，设计w s n 的路由算法需要另 辟溪径。考虑到降低节点的能量消耗可以延长整个网络的生存时间，对传感器网络的应用， 尤其是对一些无法对节点电池充电或更换电池的传感器网络的应用来说，是至为重要的。 因此，本文致力于研究w s n 的节能路由算法，以降低节点的能耗和延长网络的生存时间。 1 2 国内外研究现状 作为一种新的计算模式，w s n 正在推动科技的发展和社会的进步，由于其广阔的应用 范围和巨大的应用价值，已经引起世界各国军事部门、工业行业和学术界的极大关注【1 】【3 】。 美国国家自然基金会和国防部等均制定和设立一系列的w s n 研究计划和项目，并投巨资 支持相关基础理论的研究。信息工业界巨头公司像英特尔、微软等也设立了相应的w s n 行动计划。美国加州大学、斯坦福大学、麻省理工学院等一些著名学府也很早就加入了 w s n 相关理论研究和具体项目实施。同时，世界上许多其它国家也纷纷对该领域展开研究 工作。近年来，我国也开始重视该领域的技术研究，国家自然科技基金会也资助了许多 w s n 研究项目。于2 0 0 6 年初发布的国家中长期科学技术发展纲要为我国信息技术确 定了三个前沿方向，其中与w s n 研究直接相关的有两个 3 】。 在这些国内外良好氛围和形势的影响下，人们提出了许多路由协议。这些路由协议可 分为以数据为中心的路由协议、基于簇的路由协议、基于地理位置的路由协议、能量感知 的路由协议等种类 5 1 1 6 1 ，其中具有代表性的路由协议包括：s p i n 7 1 是第一个以数据为中 心的路由协议【6 ，该协议以高等级的描述符的方式来命名数据；d i r e c t e dd i f f u s i o n 8 】在以 数据为中心的路由协议中具有里程碑式意义，此协议采用属性值对的方式来命名数据； g p s r 9 是一个典型的基于位置的路由协议，在该协议中，每个节点在产生或者收到数据 一夕一 浙江工业大学硕士学位论文 后利用贪心算法向以欧氏距离计算出离目的节点最近的邻节点转发数据，并且采用“右手 规则”解决了节点空洞问题；s a r 1 0 是基于q o s 的路由协议，在s a r 协议中，节点根据 以离汇聚节点一跳的节点为根创建的生成树反向建立到汇聚节点具有不同q o s 参数的多 条路径，并且在发送数据时，选择其中的一条或者若干条路径进行数据传输；s p e e d 1 1 也是一种基于q o s 的路由协议，该协议提供三种实时的端对端通信，并且可以提供网络拥 塞控制。 在网络层路由协议中，节点与基站通过单跳或者多跳的方式进行通信。因此，许多路 由协议会因长距离通信和数据负载的转发而造成能量洞问题( e n e r g yh o l ep r o b l e m ) 。所谓 能量洞问题就是因为某种或者某些原因节点消耗的能量不均衡，致使某些区域消耗能量过 快的节点过早死亡，使得这些区域成为能量空洞区域。一旦某些区域出现能量洞问题，这 些区域将不能再进行监测任务，w s n 可能会因此而过早死亡，从而浪费大量剩余能量。为 了达到w s n 能源有效性，降低网络节点能耗，延长网络生存时间，如何设计一种分布式 节能路由减轻甚至解决能量洞问题具有重大意义。减轻和解决w s n 路由中能量洞问题的 技术主要有：加入移动s i n k 节点、异构节点部署、非均匀节点部署、数据融合压缩和节点 功率可调等技术 1 2 】。 目前，在国外，学者对能量洞问题解决的研究成果包括：m o h a p a t r a 1 3 阐述的加入移动 s i n k 节点的方法可以灵活控制网络收集什么数据和如何收集感知数据；z h a o 和a m m a r 1 4 提出在网络分割后，可以引入信息摆渡节点( m e s s a g ef e r r y ) 实现不同分割子网内节点的 相互通信。该文阐述了信息摆渡基本设计模式，同时提供一个划分信息摆渡模式种类的框 架。z h a o 1 5 根据节点或者信息摆渡节点发起前摄运动，研究了两种信息摆渡模式，这两 种模式不仅提高了网络传输数据的性能而且降低了节点的能耗。z h a o 和z e g u r a 1 6 研究在 分割网络中使用多个信息摆渡节点，主要集中考虑多个信息摆渡节点路径设计问题，并提 出若干算法来计算信息摆渡节点的路径以满足通信量和时延要求。s t a n i s l a v a 等【1 7 采用基 于两层圆环网络模型的异构节点布置策略来解决能量洞问题。d e t a i n 等【1 8 为节点分布遵 循二维高斯分布的w s n 提供了一个节点覆盖和网络生存时间的分析模型。b h a s k a r 1 9 和 k o n s t a n t i n o s 等【2 0 】提出一些数据融合压缩的模型和技术，并结合相关的数据融合模型，在节 点能量有限的条件下，最大化网络生存时间。e b d p 2 1 和s b t d 2 2 采用节点功率可调技 术，提出混合式的路由方法来均衡每个节点在通信时的能耗，允许节点将数据分组按比例 转发给可能的中继节点。 而在国内，在网络出现分割后，朱艺华等 2 3 提出了一种基于树结构的信息摆渡模式， 该模式在每个分割子网中构建最小加权生成树，将数据汇聚于树根节点，然后通过信息摆 一3 浙江工业大学硕士学位论文 渡节点将数据传送到汇聚节点。吴小兵等 2 4 - 1 正n 了在特定条件下多跳圆环形的w s n 中， 节点的非均匀能耗是不可避免的，并提出如果节点的数目从内层到外层( 除了最外层) 按照 等比数列依次减少，那么网络在生存时间结束时可以达到次均衡的能量消耗，从而减轻能 量洞问题。宋超等 2 5 2 6 采用节点功率可调的技术，在一个基于多层圆环模型下，分析节 点可调的通信范围对网络的能耗和生存时间的影响。作者在将节点的最大通信半径划分若 干等级后，节点选择其中的一个等级为通信半径，然后将节点的通信半径作为决策变量来 优化网络的能耗和生存时间，同时也证明了该优化问题是一个n p 难度的多目标优化问题。 文献【2 6 】通过蚁群算法来解决这一问题。卿利等【2 7 】研究了异构w s n 中分簇算法的节能性 能，并提出一种适合异构w s n 的分布式能量有效的分簇算法。杨晨曦等【2 8 】提出的d t r a ( d i f f i u e n tt r a f f i cr o u t i n g a l g o r i t h m ) 算法采用分流思想，在一个基于节点发出数据分组比 例的优化模型基础上，均衡每个节点的能耗，以达到权衡网络生存时间和数据分组跳数的 目标。沈丹丹等【2 9 】综合考虑网络中节点的剩余能量和节点间传输数据能耗，在基于最短 路径的树的基础上，通过构造两个不同的加权函数，提出“比例权值路由算法”与“和权 值路由算法 两种路由算法来均衡节点的能耗。吴万登等【3 0 】提出了l p e r ( l e a r n i n g - b a s e d p o w e re 伍c i e n tr o u t i n g ) 路由算法，该算法采用蚁群系统来确定节点路由的最佳路径，并 且在确定最佳路径时，使用增强学习来预测邻居节点的能耗，仿真实验结果表明l p e r 能 够在保持节点平均能耗和分组时延相对较低的水平下，优化w s n 的网络时间。卢文伟等 【3 1 1 利用基于网络编码的技术提出的路由算法增强了w s n 的可靠性和节能性能。 基于簇的路由协议是一种能量有效的路由协议，该类协议将网络中的节点划分成若干 个簇( c l u s t e r ) ，每个簇由一个簇头节点和若干簇成员节点组成【3 2 】【3 3 】【3 4 】。目前，基于簇的 路由协议均采用轮制，在每轮稳定通信阶段，簇成员节点发送的数据汇集于所在簇的簇头 节点，然后簇头节点采用数据压缩和融合技术对数据进行处理，之后通过单跳或者多跳将 数据传送给汇聚节点。本文按照簇头节点选举方式的不同，将现有的基于簇的路由算法大 致分为：产生随机数方式，迭代方式，竞争方式，基于层( l e v e l ) $ d 时间方式以及其它基于 簇的路由协议。l e a c h 是第一个基于簇的w s n 路由协议 3 5 1 1 3 6 ，该协议采用轮转簇头 节点角色的方式，将网络中的通信负载均分到网络中的所有节点，从而延长了网络生存时 间。h e e d 3 7 】依据剩余能量和簇内通信代价两个主次参数以迭代的方式选举簇头节点， 使得簇头节点的位置分布均匀，次参数簇内通信代价在一定程度上均衡了簇头节点的能 耗。e e c s 3 8 】、e e c s m 3 9 1 和e e u c 4 0 均以竞争的方式选举簇头节点，在e e c s 和 e e c s ，m 中，簇头节点与基站间采用一跳通信，而e e u c 中簇头节点与基站则采用多跳通 信。除了采用节点的功率调整技术外，e e c s 和e e c s m 分别通过加权函数和簇头节点到 ，4 浙江工业大学硕士学位论文 s i n k 节点的距离形成不同大小的簇，从而均衡簇头节点间的能耗。e e u c 采用一个以节点 到基站距离为变量的函数产生节点的竞争半径，从而控制网络中的成簇大小，使得靠近基 站的簇头节点形成较小的簇，以减小它们簇间通信能耗，从而可以转发更多的外层分组进 而减轻热点问题。e e l t c 4 1 以基于层和时间的方式来选举簇头节点，该协议基于层的思 想将整个网络结构离散化，使得成簇开销小及能够快速建立簇头节点间的多跳路由，且通 过各层不同的宽度形成大小不同的簇来减轻热点问题。e e l t c m 4 2 是e e l t c 改进版本， 与e e l t c 采用启发式的方式来确定每个层的宽度不同，e e l t c m 则是根据相邻层能耗相 等的数学等式进行确定每个层的宽度。 另外一些相关研究，我们在第2 章的“无线传感器网络的路由及能量洞问题 、以及 第3 章“基于簇的路由协议 中予以系统阐述( 请参见第2 章2 2 节及第3 章3 2 节) 。 综上所述，大部分基于簇的路由中会结合数据压缩以及节点功率可调技术，而某些基 于簇的路由就是专门为由异构节点组成的网络而量身设计的。由此可见，基于簇的路由不 仅是无线传感器网络中一种重要的路由协议，同时也是减轻和解决路由能量洞问题的重要 技术之一。因此，本文主要研究基于簇的路由协议，以w s n 能源有效性为目标，提出一 种分布式节能路由协议，从而减轻甚至解决w s n 中的能量洞问题。 1 3 本论文的主要内容及创新之处 针对w s n 的路由协议及其能量洞问题，本文致力于研究使节点均衡消耗能量的路由 算法，提出了一种新的分布式节能路由协议：基于网格的隔层传输的路由算法g r a c t ( g r i d b a s e dr o u t i n ga l g o r i t h mw i t hc r o s s l e v e lt r a n s m i s s i o n ) 。 本文的主要工作及创新之处在于： ( 1 )提出基于层( l e v e l ) 和网格( g r i d ) 的分布式成簇( c l u s t e r ) 方法，使每个网格内 的节点相互竞争成为簇头节点。这种方式将簇头的选举本地化，降低了选举时控 制消息开销和减少了选举的处理时间。 ( 2 )簇头选举结束后，各层簇头采用能量均衡的数据传输模式：将其p 比例的分组传 给更靠近基站的邻层簇头节点，而将剩余的分组( 即按1 - p 比例) 传送给隔层 ( c r o s s 1 e v e l ) 簇头节点。 ( 3 )提出了g r a c t 的网络总能耗和网络生存时间分析模型，并在此模型下提出两个 分别以总能耗和生存时间为目标的规划问题( 即g r a c t - i 和g r a c t - i i ) ，以确定 相应的g r a c t 路由算法的相关参数。 一s 一 浙江工业大学硕士学位论文 ( 4 )运用m a t l a b 工具对g r a c t 做了深入的仿真研究。首先，在分析模型的规划 问题指导下，研究了g r a c t 算法的参数对总能耗和网络生存时间的影响，并确 定g r a c t - i 和g r a c t - i i 相应的最优参数。其次，用g r a c t - i 和g r a c t - i i 与 现今基于簇的路由协议进行性能比较，仿真结果显示g r a c t 能够减轻w s n 路 由的能量洞问题，降低传感器节点的能耗，并达到延长网络生存时间的目标。 本文章节内容安排如下： 第1 章，阐述了w s n 的研究背景与意义，介绍了国内外关于w s n 的研究现状，并描 述了本文的主要研究内容和创新之处。 第2 章，介绍了w s n 的概念包括w s n 的体系结构、协议栈、性能评价标准、特点、 应用，同时也介绍了w s n 的路由协议分类，以及阐述了目前路由存在的能量洞问题及其 解决技术。 第3 章，分类介绍了w s n 中现有的基于簇的路由协议，并总结了它们各方面的性能 比较。 第4 章，提出本文创新的路由算法g r a c t 。其中包括介绍系统模型、阐述簇头节点 选举算法、描述能量均衡簇间通信以及建立模型对g r a c t 的性能进行分析和优化。 第5 章，利用m a t l a b 仿真工具对g r a c t 进行仿真实现，并对仿真结果进行比较 分析，以说明g r a c t 的有效性。 第6 章，总结全文工作，并展望下一步研究工作。 浙江工业大学硕士学位论文 第2 章无线传感器网络及其路由能量洞问题 2 1 无线传感器网络 2 1 1 无线传感器网络的系统结构 w s n 由大量密集布置于感知区域的传感器节点组成。如图2 1 所示，每个传感器节点 包括四个基本单元 2 】：传感单元、处理单元、通信单元和电源。根据不同的应用目的，可 以选择的其他功能单元包括：定位系统、移动系统以及电源自供电系统等等。传感单元包 括传感器和模数转换器( a n a l o gt od i g i t a lc o n v e r t e r ，a d c ) 两个子单元。a d c 将传感器在感 知区域产生的模拟信号转换成数字信号，然后反馈给处理单元。由处理器和存储器组成的 处理单元控制节点如何与其它节点协作地执行感知任务。通信单元将节点连接于网络。为 其它单元提供能源的电源是传感器节点最重要的组件之一，如果电源能源耗尽且不能得到 补充时，就意味着传感器节点死亡。大多数w s n 的路由技术和感知任务要求传感器节点 知道高度精确地理位置，所以传感器节点普遍拥有一个定位系统。有时，节点安上移动系 统使节点具有移动功能来完成指定任务。 图2 - 1 传感器节点的构成【2 】 如图2 2 所示，个典型的w s n 系统结构包括分布式传感器节点( 群) 、汇聚节点( s i n l ( ) 、 互联网或者通信卫星、任务管理节点等部分【l 】。在w s n 中，节点可以通过飞机撒布或者 人工布置等方式，大量密集部署于感知对象内部或者附近( 监测区域) 。这些节点通过自组 一7 一 浙江工业大学硕士学位论文 织的方式组成无线网络，以协作的方式实时监测、感知、采集网络覆盖区域内各种环境或 者对象的信息，并通过多跳网络将数据传给汇聚节点，然后汇聚节点通过互联网或者卫星 等多种通信途径将数据信息反馈给终端用户所在的任务管理节点。同时，终端用户可以通 过任务管理节点对传感器节点进行实时的控制和操纵，对它们进行管理和配置，发布监测 任务和收集感知数据。 监 传感器节点 图2 - 2 无线传感器网络系统结构 1 】 2 1 2 无线传感器网络的协议栈 终端用户 汇聚节点和传感器节点所使用的协议栈如图2 3 所示，它包括物理层、数据链路层、 网络层、传输层、应用层以及能量管理平台、移动管理平台、任务管理平台。各层协议的 功能如下【4 ： ( 1 )物理层：主要负责无线频率的选择、载波频率的产生、信号的发现和调制以及数 据的加密。 ( 2 )数据链路层：主要负责数据流的多路复用、数据成帧、数据帧的发现、媒介访问 及差错控制，从而保证建立可靠的点对点或者点对多点的通信链路。 ( 3 ) 网络层：主要负责路由发现和维护。 ( 4 )传输层：主要负责维护w s n 中数据流的传输控制，其是保证通信服务质量的重 要部分。 ( 5 )应用层：提供一系列用于监测任务的应用软件及相应协议。包括传感器管理协议、 任务分配和数据广播协议、传感器查询和数据分发协议等。 此外，协议栈中的能量管理平台、移动管理平台、任务管理平台监控传感器网络中能 浙江工业大学硕士学位论文 量的利用、节点的移动和任务的管理，它们使得传感器节点能够能源高效地协同工作，可 以利用节点的移动来转发数据，并且能够执行多任务和资源共享。这些平台的功能包括【5 】： ( 1 ) 能量管理平台：管理节点如何合理、有效地使用有限的能源，从而延长网络的使 用时间。其要求各层协议均要考虑能量的节省，并给操作系统提供能量分配决策。 ( 2 ) 移动管理平台：在若干要求节点可以移动w s n 应用环境中，移动管理平台可以 监测和控制节点移动，维护汇聚节点路由，同时还可以使传感器节点跟踪邻居节 点。 ( 3 )任务管理平台：主要负责平衡和调度某个区域的监测任务，并根据节点剩余能量 合理地分配和协调各个节点任务量的大小。 2 1 3 无线传感器网络的特点 图2 - 3 无线传感器网络协议栈 4 】 w s n 也是一种无线网络，同时它又提供了一种新的监测、感知、采集数据的模式。因 此它与传统的无线网络虽有相似之处，但也存在着许多差别。与传统无线网络相比，w s n 的主要特点如下【1 】： ( 1 )电源有限。由于传感器节点部署于复杂的环境中，使得通过更换电池的方式来 补充能源根本不能实现，所以在w s n 中，传感器节点经常以为电源的耗尽而失 效或者放弃，传感器节点电源能量的约束严重阻碍了w s n 的应用。 ( 2 )通信能力有限。由于传感器节点通信带宽窄且经常变化不定，加上其覆盖范围 又短，特别是在受到高山、建筑物、障碍物等地势地貌以及风雨雷电等自然环 境影响时，传感器节点更是通信间断频繁，长时间处于脱离网络状态进行离线 工作，导致通信失败。 一g一 浙江工业大学硕士学位论文 计算和存储能力有限。虽然传感器节点具有嵌入式处理器和存储器，使得其具 有一定的计算能力，能够处理一些信息工作，但是由于这些处理器和存储器能 力和容量均有限，也使得传感器节点的计算、存储能力十分有限。 传感器节点数量大，分布广泛。传感器节点随机分布于感知区域，并且数量大， 密度高，监测、感知和采集到的数据信息量大，数据冗余度高。 网络拓扑结构变化频繁。w s n 中传感器节点、汇聚节点、任务管理节点可能均 具有移动性，加上经常性的新节点加入和已有节点死亡，使得w s n 的网络拓扑 结构变化频繁。 以数据为中心。w s n 是一种任务型网络，它只关心某个区域某个事件的本身信 息，而不会去关心单个节点观测到的数据，这就是w s n 以数据为中心的特点。 与传统的端到端通信不同，w s n 主要采用广播通信。 2 1 4 无线传感器网络的性能评价 因为w s n 的性能直接影响到其可用性，因此如何评价w s n 的性能也是一个值得深入 研究的课题。以下给出的几点不仅是w s n 的性能评价标准，同时也是w s n 设计的优化目 标 1 】 5 ( 1 )能源有效性：w s n 的能源有效性是指网络在有限的能源条件下能够处理请求的 数量，它是w s n 的重要性能指标。 ( 2 )生命周期：w s n 的生命周期是指从网络启动到不能为终端用户提供需要的信息 为止所持续的时间。有可能当网络中第一个节点死亡时，网络就不能为终端用户 提供其需要的信息；也有可能是网络中若干比例的节点死亡时，网络才不能为终 端用户提供其需要的信息。影响w s n 的生命周期的因素包括硬件因素和软件因 素。 ( 3 )时延时间：w s n 的时延时间是指当终端用户发出请求到其收到回答信息所需要 的时间。时延时间与应用有密切的关系，其直接影响w s n 的可用性和应用范围。 ( 4 )容错性：由于传感器节点经常部署于复杂的环境，当它们因为各种原因失效时， 使得对其进行物理地的维护或者替换成为不可能，这就需要w s n 的软硬件具有 很强的容错性。当网络的软硬件出现故障时，网络能自动调整或者重构纠正错误， 以保证其正常运行。 ( 5 )感知精度：w s n 的感知精度是指终端用户接受到的信息精度。影响其的因素包 一1 n 一 筇 q 分 d 乃c，二-，l，l，l 浙江工业大学硕士学位论文 括传感器节点本身的精度、数据信息处理的方法、各层的网络通信协议等。通常 情况下，我们在设计网络过程中需要对能量消耗、时延时间、感知精度和生命周 期做出权衡，当然优化的目标是在最小能量消耗条件最大限度地降低时延时间、 提高感知精度和延长生命周期。 ( 6 )可扩展性：在传感器节点的数目、网络覆盖的区域范围、生存时间、时延时间和 感知精度等方面可扩展的极限体现了w s n 的可扩展性。 2 1 5 无线传感器网络的应用 由于传感器节点可以随机布置于任意复杂的环境中，w s n 可以使人们在任何时间、地 点和环境条件下获取详细的物理世界信息，除了在绪论中介绍的w s n 的一些应用外，w s n 可以被广泛应用于以下领域 1 】 4 【5 】： ( 1 ) 国防军事。由于w s n 快速部署、自组织、容错的特性，使得其成为一种适合军 事应用的感知技术。这些应用包括：监控友军及军事装备、实时监督战场、侦查 和勘测敌军地形、评估战场损失、发现和侦察核攻击和生化攻击。 ( 2 )环境监测。w s n 因其部署简单、布置密集、低成本和无需现场维护等优点为环 境科学研究提供了方便，因此其可以被广泛应用于：气象学和地理学的研究、森 林火灾和洪涝灾害的发现、监控影响农作物和牲畜的环境状况、大规模的地表监 控和勘探、追踪珍稀动物进行濒危种群的研究等。 ( 3 ) 医疗卫生。w s n 在医疗卫生方面的应用包括：完整的病患追踪、诊断学、医院 的药物管理、检测生理数据和健康状况。 ( 4 )家庭应用。嵌入在家居设备的传感器节点可以通过i n t e r n e t 或者卫星相互作用， 并且与外部网络连接起来。这样人们可以本地或者远程地控制家居设备，从而使 人们享受更加舒适、便捷、个性化的智能家居环境。 ( 5 )其它应用。在太空探索方面，借助于航天器在外星体上撒播些传感器节点可以 实现对星球表面长期的监测；在商务方面，传感器网络可用于物流和供应链的管 理；同时w s n 还可以用于发现偷车贼、管理库房详细清单、追踪和发现车辆等 在蕾 守o 浙江工业大学硕士学位论文 2 2 无线传惑器网络的路由及篚量洞问题 2 2 1无线传感器网络的路由 因为w s n 不同于传统无线网络，因此它们在路由设计目标方面也存在着巨大差别。 传统网络路由设计的主要目标是高效地利用网络带宽和高质量地提供通信服务，这些协议 的主要任务是寻找信源节点和信宿节点间通信时延小的路径，与此同时，提高网络带宽的 利用率，避免通信拥塞和均衡通信流量等。而在无线传感器中，由于节点能量非常有限且 一般得不到补充，所以其路由设计的主要目标就是高效地使用能量，这些协议的主要任务 是在源节点和目的节点间寻找一条优化路径，并在这条路径上正确地对分组进行转发。而 这条优化过的路径能够使得终端用户在延长生命周期、降低通信时延和获取的感知精度上 取得折中【4 】。 网络层路由协议大致可以分为五类：以数据为中心的路由协议、基于簇的路由协议、 基于地理位置的路由协议、能量感知的路由协议和q o s 感知的路由协议等 3 】【6 】。 ( 1 )以数据为中心的路由协议 在以数据为中心的路由协议中，汇聚节点发送查询命令给某个区域，然后等待所选区 域中传感器节点的反馈数据。由于这些数据是对查询命令的回答，所以有必要用基于属性 的命名方式来详细说明数据本身的特征。这类协议的典型代表有：s p i n 7 】、d i r e c t e d d i f f u s i o n 8 、r u m o r 4 3 等。 s p i n 是第一个以数据为中心的路由协议【6 】。该协议以高等级的描述符即抽象的元数 据来命名数据，在每次数据传播前，节点用包含元数据的a d v 消息向邻居通告，需要数 据的邻居节点用r e q 消息提出请求，然后数据通过d a t a 消息发送到请求节点。s p i n 利 用这种数据谈判方式来传送数据可以达到降低网络中冗余数据量和节约节点能量的目的。 d i r e c t e dd i f f u s i o n 在以数据为中心的路由协议中具有里程碑式意义。该协议采用属性值对 的方式来命名数据。在路由建立阶段，汇聚节点首先以洪泛方式发送查询请求，然后沿途 节点根据各个查询请求的进行缓存和合并，并根据它们计算、创建包含数据上报率等信息 的网络梯度，从而建立多跳指向汇聚节点的路径；在数据传输过程中，汇聚节点可以根据 某条路径发送上报时间更小或者具有更大的查询请求来增强或者减弱其数据上报率。 r u m o r 协议是d i r e c t e dd i f f u s i o n 协议的一个变体，主要是为了解决d i r e c t e dd i f f u s i o n 中开 销太大的问题。该协议借鉴欧式平面图上任意两条曲线交叉概率大的思想来建立路径：当 监测区域的节点感知到某个事件后，沿随机路径向外扩散传播携带该事件的代理消息，同 浙江工业大学硕士学位论文 时汇聚节点发送的查询请求也按照随机的路径在节点中进行转发。当这两个消息汇聚于某 一个节点时，路由也就建