（通信与信息系统专业论文）无线传感器网络节点移动技术的研究.pdf

本学位论 授权北京交通 并采用影印、 家有关部门或 ( 保密的 学位论文 签字r 期 中图分类号：t p 3 1 9 u d c - 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 无线传感器网络节点移动技术的研究 r e s e a r c ho nm o b i l en o d ei nw i r e l e s ss e n s o rn e t w o r k s 作者姓名：郭英慧 导师姓名：刘云 学位类别：工学 学号：0 8 1 2 0 1 2 0 职称：教授 学位级别：硕士 学科专业：通信与信息系统研究方向：计算机网与信息系统 北京交通大学 2 0 1 0 年6 月 致谢 时光飞逝，转眼间两年的硕士生活即将结束。能够在计算机网络与信息系统 实验室这个和谐融洽、学习气氛浓厚的大家庭中完成我的学业，不仅是我学业中 的收获，更是我人生中的财富； 首先要衷心感谢我的导师刘云教授，本论文是在刘云教授的悉心指导下完成 的。刘云老师不仅使我树立了远大的学术目标、掌握了基本的研究方法，还使我 明白了许多待人接物与为人处世的道理。刘云教授广阔的科学视野和渊博的学术 造诣是我学习的榜样，时刻激励我在专业领域学习钻研。刘云教授严谨的治学态 度和平易近人、务实勤勉的人格品质更加对我影响深远，她不仅教会我怎样做学 问，更教会我怎样做人。本论文从选题到完成，每一步都是在刘云老师的具体指 导下完成的，倾注了刘云老师大量的心血。在此，谨向刘云老师表示崇高的敬意 和衷心的感谢! 我还要感谢实验室张振江老师，两年来，张老师无论是在学习还是科研上都 给了我诸多的指导，特别是在无线传感器网络的学习中，对我的帮助更加巨大。 通过张老师的指导，我对无线传感器网络有了更加深刻的认识和理解，也更加热 爱这个领域。在论文完成阶段，张老师提出了许多宝贵意见，使我受益匪浅，在 此表示衷心的感谢。 孟嗣仪老师虽然不是我的直接导师，但她依然对我的科研工作和论文都提出 了许多的宝贵意见，感谢她两年来对我的帮助和教育。 在两年的学习期间，我得到了陈本锡、张树魁、熊菲等师兄的关心和帮助， 在此表示深深的感谢。还要感谢程子栋、牛青青和仲丽媛等同学，他们在生活中 和学习上以及我的学位论文完成过程中都给予我无私的帮助。祝愿他们都能在未 来的生活中工作顺利、身体健康。 衷心感谢家人对我的养育和支持，是他们的支持使我能完成我的学业。 最后，感谢在百忙之中评阅论文的各位专家、老师，感谢所有关心、支持和 帮助过我的人! 中文摘要 摘要：无线传感器网络在军事、工业、民用等诸多方面拥有广泛的应用前景，是目 前的研究热点之一。无线传感器网络的突出特点是在固定区域内静态节点随机散 布，节点数据通过多跳方式进行传输。带来的突出问题是网络中越靠近汇聚节点 ( s i n k ) 的周边节点能量消耗越快，最终因为靠近s i n k 的周边节点能量失效导致 整个无线传感器网络处于瘫痪状态。 本文在系统分析了当前主要传感器网络路由协议的基础上，总结了目前通用 路由协议算法存在的问题。通过在无线传感器网络中应用节点移动技术，试图设 计一种基于移动节点的无线传感器网络路由算法，实现网络生命周期的延长和系 统安全性保证。 本论文的研究内容和创新工作主要体现在以下几方面： 1 在无线传感器网络中应用节点移动技术，同时证明利用节点移动技术节约 网络能量具有可行性。 2 设计了可控移动节点路由算法，该算法包含重要节点与移动节点通信法则、 移动节点速度控制算法和网络安全法则。 3 在重要节点与移动节点通信法则中，从节能角度考虑提出了将平面路由和 层次路由有机结合的无线传感器网络响应式混合路由模型；从数据可靠性角度考 虑引入了区分服务的概念。 4 从网络安全方面考虑，设计了改进扩充口令算法，对传输数据进行加密设 置，有效防止外来节点窃听。 5 在研究后期，采用了基于t i n y o s 的应用仿真平台t o s s i m ，将可控移动节 点路由算法与运行l e a c h 协议和d d 协议的静态网络进行了性能仿真对比。分析 结果表明可控移动节点路由算法有效地减少了节点的能量消耗，达到了延长网络 生命周期的目的， 关键词：无线传感器网络；移动节点；能量有效性；区分服务；网络安全 分类号：t p 3 1 9 a b s t r a c t 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 ) a r ea p p e a l i n gt or e s e a r c h e r sd u et o t h e i rw i d er a n g eo fa p p l i c a t i o np o t e n t i a li nm i l i t a r y , i n d u s t r y , h o m en e t w o r k sa n ds o o n a n dw s nh a v eb e e np r o p o s e dt od e l i v e ri n s i t uo b s e r v a t i o no fe v e n t sa n d e n v i r o n m e n t so v e rl o n gp e r i o do ft i m e al a r g en u m b e ro fs m a l la n ds i m p l es e n s o r d e v i c e sc o m m u n i c a t eo v e rs h o r tr a n g ew i r e l e s si n t e r f a c e st od e l i v e ro b s e r v a t i o n so v e r m u l t i p l eh o p st oc e n t r a ll o c a t i o n sc a l l e ds i n k as i g n i f i c a n tp o r t i o no ft h ee n e r g y e x p e n d i t u r ei sa t t r i b u t e dt oc o m m u n i c a t i o n sa n d ，i np a r t i c u l a r , t h en o d e sc l o s et ot h e s e n s o rn e t w o r kg a t e w a y su s e df o rd a t ac o l l e c t i o nt y p i c a l l ys u f f e ral a r g eo v e r h e a da s t h e s en o d e sm u s tr e l a yd a t af r o mt h er e m a i n i n gn e t w o r k i fa l lt h ep r o c e s s e dd a t am u s t t r a v e r s et h e s en o d e st or e a c ht h eg a t e w a y , t h en e t w o r kw i l lb ei n v a l i df o rt h ed e p l e t i o n o ft h e s en o d e s a f t e rs y s t e m a t i c a l l yr e v i e w i n gt h er o u t i n gp r o t o c o l sf o rw s n ，t h i sd i s s e r t a t i o n s u m m a r i z e st h ee x i s t i n gp r o b l e m so fr o u t i n gp r o t o c o l s a n dw ed i s c u s san e t w o r k i n f r a s t r u c t u r eb a s e do nt h eu s eo f c o n t r o l l a b l y m o b i l en o d et or e d u c et h e c o m m u n i c a t i o ne n e r g yc o n s u m p t i o na tt h ee n e r g yc o n s t r a i n e dn o d e sa n d ，t h u s ，i n c r e a s e u s e f u ln e t w o r kl i f e t i m e b e s i d e s ，s o m ea t t e n t i o ni sp a i dt os e c u r i t y t h em a i nc o n t r i b u t i o na n di n n o v a t i o no ft h i sp a p e ra r ea sf o l l o w s ： 1 t h ep a p e ri n c l u d e st h em o b i l en o d ei nw s na n dp r o v e st h ef e a s i b i l i t yf o ru s i n g am o b i l en o d et oi n c r e a s et h el i f e t i m eo ft h en e t w o r kb yr e d u c i n gt h er e l a y i n go fd a t a 2 c o n t r o l l e dm o b i l en o d er o u t i n ga l g o r i t h m ( c m n r a ) i sd e s i g n e d ，w h i c h i n c l u d e si m p o r t a n tn o d ea n dm o b i l en o d ec o m m u n i c a t i o na l g o r i t h m ，m o t i o nc o n t r o l a l g o r i t h ma n d n e t w o r ks e c u r i t ya l g o r i t h m 3 f o rt h ea s p e c to fe n e r g ye f f i c i e n t ，ah y b r i dr o u t i n gm o d e lu s i n gi ni m p o r t a n t n o d ea n dm o b i l en o d ec o m m u n i c a t i o na l g o r i t h mi si n t r o d u c e di nt h ep a p e r ，a n dt h i s m o d e ls e a m l e s s l yc o m b i n e sp l a n er o u t i n ga n dh i e r a r c h i c a lr o u t i n g ；a i m i n ga tr e l i a b l e d a t ad e l i v e r yo fw s n ，t h i sa r t i c l ei n t r o d u c e sd i f f e r e n t i a t e ds e r v i c e s ( d i f f s e r v ) 4 a ni m p r o v e ds e c u r et h r e e p a r t yk e ye x c h a n g ep r o t o c o li sp r o p o s e dc o n s i d e r i n g s e c u r i t y , w h i c hc a ne n c r y p tt h et r a n s m i s s i o nd a t aa n dp r e v e n ta t t a c ko fe x t e r n a ln o d e s 5 i nt h ee n do ft h ep a p e r , t h ea n a l y s i si sc a r r i e do nt oc m n r a u s i n gt o s s i m b a s e do nt i n y o s c m n r ai sc o m p a r e dt ol e a c h p r o t o c o la n dd dp r o t o c o lw h i c h a r ea l s ot h ee f f e c t i v ea l g o r i t h mi nw i r e l e s ss e n s o rn e t w o r k s s i m u l a t i o nr e s u l t ss h o w t h a ta sw e l la ss a v i n ge n e r g yo fn o d e s ，c m n r ai sa b l et ob a l a n c ee n e r g yd i s s i p a t i o n a n dp r o l o n gt h el i f e t i m eo fw s n s i g n i f i c a n t l y k e y w o r d s ：w i r e l e s ss e n s o r n e t w o r k s ；m o b i l en o d e ；e n e r g ye f f i c i e n t ； d i f f e r e n t i a t e ds e r v i c e s ；s e c u r i t y c i a s s n o ：t p 3 1 9 v 目录 中文摘要i i i a b s t r a c t ：i 、， 1j i l 言1 1 1研究背景1 1 2研究目的和意义2 1 3论文的组织结构2 2 无线传感器网络路由协议的分析。4 2 1 无线传感器网络路由协议设计需求。4 2 2典型无线传感器网络路由协议的比较和分析5 2 2 1 平面路由协议5 2 2 2 层次式路由协议7 2 2 3 基于位置信息的路由协议1 0 2 2 4 基于o o s 的路由协议。1 1 2 2 5 路由协议性能综述1 3 2 3本章小节1 4 3基于移动节点网络的可行性分析及应用方案选择1 5 3 1基于移动节点网络的可行性分析与证明1 5 3 1 1 网络节能性分析1 5 3 1 2 节点传输数据速率分析1 9 3 2基于移动节点网络的方案选择2 0 3 2 1 基于基站移动的解决方案一2 0 3 2 2 基于移动节点收集数据的解决方案2 1 3 2 3 基于移动节点群聚集合的解决方案2 2 3 3本章小节2 3 4关键算法及实现2 4 4 1重要节点与移动节点通信法则的建立2 4 4 1 1 重要节点选举2 5 4 1 2 簇内信息建立2 8 4 1 3 重要节点与移动节点通信算法实现3 0 4 1 4 重要节点与移动节点通信法则仿真3 5 4 2移动节点速度控制法则的建立3 8 参考文献5 3 作者简历5 6 独创性声明5 7 学位论文数据集5 8 1 引言 1 1研究背景 无线传感器网络是当今国内外备受关注的、由多学科高度交叉的新兴前沿研 究领域。它综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分 布式信息处理技术等，能够实时监测、感知和采集网络分布区域内的各种环境或 监测对象的信息，并对这些信息进行处理，获得详尽而准确的信息后，传送到需 要这些信息的用户。随着传感器技术的发展，各种传感器必将渗透到人类生活环 境的各个角落，为人们提供一种全新的获取信息、处理信息的途径。这些具有数 据采集、数据处理和通信能力的微小结点通过自组织的方式构成网络，采集、测 量、传输和处理人类关心的各种信息，应用到我们生活和工作的各个方面，将为人 类的生活提供更加便捷的服务。 无线传感器网络具有十分广阔的应用前景，在军事国防、工农业、城市管理、 生物医疗、环境监测、抢险救灾、防恐反恐、危险区域远程控制等许多领域都有 重要的科研价值和巨大的实用价值，它已经引起了世界许多国家军事界、学术界 和工业界的高度重视，并被公认为是对2 1 世纪产生巨大影响的技术之一i 。 无线传感器网络作为新兴的研究学科，有许多关键问题需要进一步解决，如 分布式信息处理、定位算法、路由技术等，其中路由技术对无线传感器网络的性 能好坏有着举足轻重的作用。但是无线传感器网络中的路由协议又与其它网络中 的路由协议特点和设计目标有着巨大的区别。 无线传感器网络的路由协议是无线传感器网络中一个关键的支撑技术。无线 传感器网络中节点资源极端受限、大规模网络的随机散布以及网络拓扑的动态性 都给路由选择与优化问题的研究带来了前所未有的挑战。节点移动技术的引入， 为解决传统无线传感器网络节点能量有限和网络拓扑动态变化的难题带来了可行 性方案。利用移动节点与网络中的重要节点进行数据传送或者对能量消耗殆尽的 重要节点进行替代，提高网络覆盖比例，更好地均衡网络内节点能量，从而延长 了整个网络的生存周期1 2 - 3 i 。 q 1 2 研究目的和意义 本研究旨在设计一种能够利用节点的移动特性有效解决无线传感器网络中能 量有限和数据传输安全的路由协议。无线传感器网络的静态节点随机散布在固定 区域内，通过多跳方式进行节点数据的传输。这样的模式带来的二个明显问题是 网络中会出现越靠近汇聚节点( s i n k ) 的节点能量消耗越快现象。靠近汇聚节点 s i n k 的节点能量消耗过快，可能导致网络中其他数据节点会因为无法通过这些节 点进行数据中继而最终无法与s i n k 取得联系，致使网络不能正常运行。因此，本 文的路由设计不仅关心单个节点的能量消耗，更关心整个网络的能耗，从而达到 延长整个网络生存周期的目的。 同时，无线传感器网络作为任务型的网络，路由协议的设计不仅要考虑数据 传输时网络的节能问题，路由协议也要考虑网络安全性，保证数据传输的安全可 靠。由于无线传感器网络采用无线信道、节点能量有限、分布式控制等问题，促 使它更容易受到各种网络攻击。传统的安全技术占用较多的资源，不能直接应用 于能量受限的无线传感器网络，所以也使无线传感器网络的安全问题成为路由设 计过程中的挑战。 本文重点研究解决无线传感器网络的能量有效性和安全性问题，使得无线传 感器网络可以持续稳定高效工作，使无线传感器网络有更加广阔的应用前景和发 展空问。 1 3论文的组织结构 第一章引言。本章介绍了本文的课题研究背景，阐述了本课题的研究目的和 意义，然后说明了全文结构。 第二章无线传感器网络路由协议的分析。本章详细介绍了无线传感器网络中 四种典型的路由协议，并对几种通用的路由协议进行了综合评述。 第三章基于移动节点网络的可行性分析及应用方案选择。本章对无线传感器 网络应用移动节点节约网络能量的可行性进行了分析。从网络节能和节点数据传 输速率两方面与传统无线传感器网络进行了分析和比较，并进行仿真；同时对应 用移动节点的可行性方案进行了分析。 第四章关键算法及实现。本章提出了可控移动节点路由算法。首先建立重要 节点与移动节点的通信法则，并进行仿真分析；然后对移动节点速度控制算法进 行阐述，并提出移动节点移动速度与节点缓存选取之间的关系；最后对改进扩充 口令协议的算法和应用进行了说明，并验证改进扩充口令协议在保证网络安全性 2 方面的作用。 第五章总结及展望。对全文进行总结并介绍了课题今后进一步的改进和发展 方向。 2无线传感器网络路由协议的分析 2 1无线传感器网络路由协议设计需求 无线传感器网络的重要任务就是将感知的数据传输到特定的接收节点，而数 据传输离不开路由协议。在无线传感器网络路由协议的设计过程中，路由协议的 作用是将数据从源节点通过网络转发到目的节点，其中包括寻找源节点和目的节 点之间的优化路径和将数据分组沿着优化路径正确转发两方面的内容。因此在无 线传感器网络路由协议的设计过程中，主要考虑以下因素： 1 节能 通常无线传感器网络节点采用有限的电池供电，因此能量受限是无线传感器 网络的主要特征。实施有效的节能策略是延长无线传感器网络生存时间的重要手 段。因此，依靠能量的高效运用来延长系统的生命周期是路由协议设计过程中首 要考虑的问题。 2 传输延迟 路由协议的主要任务是寻找源节点到目的节点间通信延时小的路径。在传感 器网络的很多应用中，用户需要的是传感器所产生的数据，及时的数据传输对用 户有着巨大的意义。 3 容错性 在无线传感器网络中，能量限制、环境干扰和频繁变化的拓扑结构等因素可 能导致传感器节点的损坏。路由协议的容错性( 或称健壮性) 可以保证部分传感 器节点的损坏不会影n 1 6 j n 全局任务。网络容错性可以通过数据复制的方式实现， 然而数据复制本身会消耗节点能量，因此要均衡数据复制和能量问的关系。 4 服务质量 无线传感器网络的应用环境千差万别，在不同的要求下对网络性能的要求也 不同。无线传感器网络不仅要考虑到如何在拓扑结构和信道状态频繁变化的环境 中实现服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) ，还要对如何在降低能耗和保证 q o s 间达到平衡等问题进行深入的研究。 5 安全性 路由协议通过多跳方式传输数据，没有保护的路由信息容易受到多种形式的 攻击。目前的路由很少考虑安全问题，无线传感器网络本身在安全方面的弱点和 应用环境的多样性使得它的安全机制面临很大挑战。 4 2 2典型无线传感器网络路由协议的比较和分析 2 2 1平面路由协议 平面结构是指网络中各节点在路由功能上地位相同，没有引入分层管理机制。 平面结构路由的优点是网络中没有特殊的节点，网络流量均匀地分散在网络中， 路由算法易于实现；缺点是可扩展性小，在一定程度上限制了网络的规模。典型 的路由协议有定向扩散协议( d i r e c t e dd i f f u s i o n ，简称d d 协议) 、信息协商传感 器协议( s e n s o rp r o t o c o lf o ri n f o r m a t i o nv i an e g o t i a t i o n ，简称s p i n 协议) 等。 1 定向扩散协议 在参考文献【4 1 中，i n t a n a g o n w i w a t 等人提出了应用于无线传感器网络的定向 扩散协议。该协议是一种以数据为中心的平面结构协议，且能够同时承载多个应 用。d d 协议的最大特点是首次提出了网络梯度的概念，并与数据融合算法相结合， 能够用较小的成本完成数据搜索的功能。 定向扩散算法的主要思想是对网络中的数据用一组属性对来命名，并基于数 据进行通信。其突出特点是引入了梯度来描述网络中间节点在某方向继续搜索以 获得匹配数据的可能性。 为建立路由，汇聚节点( s i n k 节点) 向所有传感器节点发送查询请求兴趣信 息( i n t e r e s t ) ，兴趣信息i n t e r e s t 包括属性列表、上报间隔、持续时间、地理区域 等信息。沿途节点按需对各兴趣信息i n t e r e s t 进行缓存与合并，并根据兴趣信息 i n t e r e s t 设计、创建包含数据上报率、下一跳等信息的梯度( g r a d i e n t ) ，从而建立 多条指向s i n k 节点的路径。兴趣信息i n t e r e s t 中的地理区域内节点则按要求启动监 测任务，并周期性地上报数据。源节点采集的数据首先在本地采用汇聚融合技术 进行整合，然后在传感器网络中传输。s i n k 节点可在数据传输过程中通过对某条 路径发送上报间隔更小或更大的兴趣信息i n t e r e s t ，以增强或减弱数据上报率【5 j 。 该协议采用邻节点间通信方式来避免维护全局拓扑，并采用查询驱动数据传 送模式和局部数据聚集来减少网络数据流，因而是一种高能效的协议。它的缺点 是在需要连续传送数据的应用中( 如环境监测等) 不能很好的应用，其数据命名 只能针对于特定的应用预先进行，同时初始查询的扩散开销也较大。图2 - 1 表示了 定向扩散协议的路由建立过程。 d d 协议是以数据为中心的路由协议，所有通信都局限在邻居节点之间，每个 节点都具有收集数据，进行数据聚集和缓存数据的功能，这种特性减少了网络数 据流也降低了数据传输延迟。d d 协议路径创建灵活，且路径恢复的局部算法设计 使得系统对于网络的动态拓扑具有更强的适应性。按需驱动数据的传送模式和不 5 需要维护全局网络拓扑结构，使得d d 协议成为一种高能源有效性的协议。 ( i ) 兴趣扩散 ( b ) 梯度建立 oo s o u r c e s i n k o 一 oo ( c ) 路径加强 图2 1 定向扩散路由机制 f i g 2 - 1d i r e c t e dd i f f u s i o nr o u t i n gm e c h a n i s m 2 信息协商传感器协议 s p i n 协议是一种以数据为中心的自适应通信路由协议。其目标是通过使用节 点间的协商制度和资源自适应机制，解决定向扩散算法存在的不足。 s p i n 协议有三种数据包类型：a d v 、r e d 和d a t a 。节点用a d v 宣布有数 据要发送，用r e q 请求接收数据，用d a t a 封装数据。节点产生或收到数据后， 为避免盲目传播，用包含元数据的a d v 消息向邻节点通告，需要数据的邻节点用 r e q 消息提出请求，数据通过d a t a 消息发送到请求节点。以此类推，d a t a 数 据包可被传输到远方汇聚节点或基站。 s p i n 协议的优点是：a d v 消息减轻了内爆问题；通过数据命名解决了交叠问 题；节点根据自身资源和应用信息决定是否进行a d v 通告，避免了资源利用盲目 问题。s p i n 协议的缺点是在传输新数据的过程中，直接向邻居节点广播a d v 数 据包，而没有考虑其所有邻居节点出于自身能量的原因而不愿转发新数据，从而 导致新数据无法传输，出现“数据盲点”，进而影响整个网络信息的收集。 s p i n 协议有4 种不同的形式：s p i n p p 、s p i n e c 、s p i n b c 、s p i n r l 。 ( 1 ) s p i n p p 采用点对点的通信，并假定两节点问的通信不受其他节点干扰，分组不会丢 失，功率没有任何限制，如图2 2 所示。在发送d a t a 数据包之前，传感器节点首先 向邻居节点广播a d v 数据包，对方在收到a d v 后如果有意愿接收该d a t a 数据包， 那么就向传感器节点发送一个r e q 数据包，接着向传感器节点发送d a t a 数据包。 以此类推，d a r a 数据包可被传输到远方汇聚节点。 ( 2 ) s p i n e c s p i n e c 在s p i n p p 协议的设计基础上考虑了节点的功耗，只有顺利完成所有 任务且能量不低于设定阈值的节点才可参与数据交换。 ( 3 ) s p i n b c s p i n b c 设计了广播信道，使所有在有效半径内的节点可以同时完成数据交 换。为了防止产生重复的r e q 请求，节点在听到a d v 消息以后，设定一个随机定时 器来控制r e q 请求的发送，其他节点听到该请求后主动放弃请求权利。 ( 4 ) s p i n r l 。 s p i n r l 是对s p i n b c 协议的完善，主要考虑如何纠正无线链路引入的分组差 错与丢失，记录a d v 消息的相关状态。如果在确定时间间隔内接收不到请求数据， 则发送重传请求，重传请求的次数有一定的限制【倒。 o o a v o o 弹一 o 跸。 o o r e q o o ( b ) o 蕊r e q p o o ( e ) 图2 2s p i n 路由机制 f i g 2 - 2s p i nr o u t i n gm e c h a n i s m 2 2 2 层次式路由协议 o o d a t a o 呻一 o 瓷d a t a 静o o ( f ) 层次路由( 也称为以分簇为基础的路由) 用于满足传感器节点的低能耗和高 效率通信。在层次路由中，高能量节点可用于数据转发、数据融合、路由维护等 高耗能场合；低能量节点用于事件检测和局部路由维护等低耗能场合。层次路由 将不同的应用按照节点不同的能力合理分配，使节点能充分发挥各自优势，达到 有效提高整个网络生命周期的目的。 层次路由协议采用簇的概念对节点进行层次划分。若干个相邻节点构成一个 簇，每一个簇有一个簇首。簇与簇之问可以通过网关通信，网关可以是簇首也可 以是其它簇成员。网关之间的连接构成上层骨干网，所有簇问通信都通过骨干网 7 转发。低能量自适应分簇路由协议( 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 ，简 称l e a c h 协议) 就是一个基于分簇思想的无线传感器网络层次路由算法。 在无线传感器网络中l e a c h 协议是第一个提出的层次式路由协议，其后的大 部分层次式路由协议都是在它的基础上发展而来的。l e a c h 协议运用了数据压缩 技术和分层动态路由技术，通过随机设置某些节点为“簇头节点 来均衡网络内 部负载，防止簇头节点过快死亡；通过数据融合技术来减少发送的数据量；通过 l e a c h 路由协议的核心思想是：通过等概率地随机循环选择簇头，将整个网 络的能量负载平均分配到每个传感器节点，从而达到降低网络能量损耗、延长网 值，那么这个节点就成为簇头节点。丁( ，1 ) 值按以下公式计算，该算法可保证在1 p m ，l 市： 协1 ) 在簇头节点选定后，该簇头节点对网络中所有节点进行广播，广播数据包含 有该节点成为簇头节点的信息。传感器节点收到广播数据包后，根据接收到的各 个簇头节点广播信号强度，选择信号强度最大的簇头节点加入，向其发送成为其 成员的数据包。簇形成后，簇内的所有节点按照时分复用方式向簇头发送数据。 一旦处于数据通信阶段，簇头节点开始接收簇内各节点采集的数据，然后采用数 据融合和数据压缩等技术进行汇聚，将整合后的数据传输给网关节点。在持续工作 一段时间之后，网络重新进入启动阶段，进行下轮的簇头选取工作并重新建立 l e a c h 协议具有减少冗余和均衡网络负载的能力，但它也存在缺陷。首先， 簇头节点除完成直接与s i n k 节点通信的功能外，还要完成簇的维护、数据融合等 8 复杂任务，能量消耗很大。在实际大规模的网络应用中，可能出现被选择的簇头 节点距离s i n k 节点通信较远，无法进行通信。另外网络需要始终处于工作状态， 不断的选择簇头和维护簇，浪费了网络的能量。 图2 - 3u a c h 算法对簇的划分 f i g 2 - 3d i v i d i n gi n t oc l u s t e r so fl e a c h 2 低功耗传感器收集信息协议 低功耗传感器收集信息协议【8 】( p o w e r - e 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 n s y s t e m ，简称p e g a s i s 协议) 是基于“链”的协议，是在l e a c h 协议基础上发 展而来的。p e g a s i s 协议的主要思想是每个节点通过贪婪算法选择与自己最邻近 的节点通信，所有这些节点轮流与s i n k 节点通信，在整个网络中就形成了“链” 状的传输路径。p e g a s i s 协议的路由建立过程如图2 - 4 所示。 ( 1 ) 节点都知道其它节点的位置信息，利用贪婪算法，选择和自己距离最近 的邻居节点进行通信，形成“链”。 ( 2 ) 节点从邻居节点接收数据，然后向另一边的邻居节点发送数据。数据从 一个节点传到另一个节点( 在此过程中进行数据融合) ，最终传到一个链首节点。 ( 3 ) 由于网络中的节点都具有直接和基站通信的能力，链首节点将接收的信 息进行数据融合后传送给s i n k 节点。 ( 4 ) 链中节点在每轮通信中轮流作链首节点，这样每个节点每一轮的平均能 9 耗就降低了。 p e g a s i s 算法仅选择一个节点与s i n k 通信，通过利用数据融合技术减少了数 据发送和接收的次数，有效地延长了网络生命周期。但链中远距离的节点会引入 过多的延迟，单一的链首可能会成为瓶颈。 图2 _ 4 p e g a s i s 协议 f i g 2 - 4p e g a s i sp r o t o c o l 2 2 3基于位置信息的路由协议 这类路由协议通常需要知道目的节点的位置，把节点位置信息作为路由选择 的依据，从而不必为了找到目标节点向整个网络进行广播。典型的协议有基于地 理位置的能量感知路由【9 】( g e o g r a p h i ca n de n e r g ya w a r er o u t i n g ，简称g e a r 协 议) 。 1 基于地理位置的能量感知路由 g e a r 算法提出既然传感器网络中的数据经常包含了位置属性信息，那么可 以利用这一信息，把在整个网络中扩散的信息传送到适当的位置区域中。g e a r 协议根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路 径。g e a r 协议假设已知事件区域的位置信息，且每个节点均知道自己的位置信 息和剩余能量信息。另外，节点通过一个简单h e l l o 消息交换机制就可获得所有邻 居节点的位置信息和剩余能量信息。 g p e r 协议包含与邻节点建立路由和与非邻节点建立路由两种路由模式。 与邻节点建立路由的过程是从源节点传输范围内的所有节点中确定最好的下 跳节点。如果距离源节点位置较近，则采用直接发送的方式，不经过中间节点 进行转发；如果在距离源节点较远的位置上，则选择中间节点进行多跳转发。在 选择中间节点时，不仅考虑哪个邻节点距离目标节点较近，同时也考虑通过哪些 1 0 中间节点来传输数据到目标节点可以节省能量。 与非邻节点建立路由用来与非源节点传输范围内的节点建立路由，它依赖于 第一种模式，并且通过动态调整子目标节点来实现。 动态调整子目标节点主要用来不断地对路径进行调整，以获得高能效的路由。 在与邻节点建立路由的过程中，源节点已经建立了一条本地优化的最小能量消耗 路径到达它的子目标节点。下一跳节点也利用自己的能量状况和它的邻节点信息 找出一个新的子目标节点。以此类推，不断调整子目标节点直到到达目的节点。 这样的方式可以有效地避免因局部的判断错误导致严重背离目标节点的后果，在 转发节点处能够及时有效地纠正1 1 0 j 。 同样g e a r 协议也采用了查询驱动数据传送模式。g e a r 路由协议中查询消 息传播分为两个阶段： 首先，基站或汇聚节点发出查询消息指令，根据事件区域地理位置消息将查 询指令传输到区域内距基站或汇聚节点最近的节点。然后，该节点将查询命令传 播到区域内其他所有节点。采集的数据就沿查询命令的反向路径传送到基站或 汇聚节点。由基站或汇聚节点发出查询消息指令传送方式有所不同。 ( 1 ) 查询命令传送到事件区域：本阶段，节点根据地理位置信息在邻居节点 中选择到事件区域路由代价最小的节点作为下一跳节点。若出现路由空洞，即节 点的所有邻居节点到事件区域的代价都比自己大，数据无法传输，则节点选择邻 居节点中代价最小的节点作为下一跳节点。 ( 2 ) 查询命令在事件区域内传播：在查询命令到达事件区域后，可以通过泛 洪方式和迭代地理转发策略两种方式来传播查询命令。 g e a r 协议将网络中扩散的信息局限到适当的位置区域中，减少了中间节点 的数量，避免了扩散传播，从而降低了路由建立和数据传送的能源开销，节省能 源，从而更有效的提高了网络的生命周期。 g e a r 协议适用于移动性较小的传感器网络应用环境。由于缺乏足够的拓扑 信息，路由过程中可能遇到路由空洞，反而降低了路由效率，因此g e a r 协议只 适用于节点移动性不强的应用环境。g e a r 协议依赖节点的全球定位系统( g l o b a l p o s i t i o n i n gs y s t e m ，简称g p s ) 定位信息，网络成本较高。 2 2 4 基于q o s 的路由协议 基于服务质量的路由协议的目标是在实现路由功能的同时满足一些网络服务 质量( q o s ) 要求。这类路由协议在建立无线传感器网络路由路径的同时，考虑端 对端的时延和可靠性等要求。典型的协议有有序分配路由协议( s e q u e n t i a l a s s i g n m e n tr o u t i n g ，简称s a r 协议) 和无状态实时端对端路由协议( s t a t e l e s s p r o t o c o lf o rr e a l t i m ee n d t o e n dg u a r a n t e e s ，简称s p e e d 协议) 等。 1 有序分配路由 s a r 协议是第一个具有q o s 思想的路由协议，它是1 9 9 9 年k a t a y o u ns o h r a b i 1 1 j 等人在一个研究项目中提出的路由协议。它采用基于路由驱动的多路径方式实现 网络节点的节能和健壮性，是一种类似于有线网络的带有q o s 路由的算法。在选 择路径时，该协议充分考虑了网络功耗、o o s 和分组优先权等特殊要求。s a r 协 议采用局部路径恢复和多路径备份策略，避免节点失效或链路失效时进行路由重 计算带来的过多开销。 s a r 协议在每个节点与s i n k 节点间生成多条路径，s i n k 节点需要维护多个树 结构，每个树以落在s i n k 节点有效传输半径内为根向外生长，枝干的选择需要满 足一定的q o s 要求并要有一定的能量储备，这一处理使大多数传感器节点可能同 时属于多个树，可任选其一将采集数据回传到s i n k 节点i l 引。 s a r 协议具有较好的节能性，但该算法没有考虑均衡节点的能耗问题，不具 备能量感知功能。s a r 协议的特点是路由决策不仅要考虑到每条路径的能量，还 要涉及到端到端的延迟需求和待发送数据包的优先级。与只考虑路径能量消耗的 最小能量度量协议相比，s a r 协议的能量消耗较少。该算法的缺点是不适用于大 型的和拓扑频繁变化的网络。 2 无状态实时端对端路由协议 s p e e d 协议1 1 3 】是一种专门为无线传感器网络设计的实时通信协议，提供端对 端软实时，并保证无线传感器网络q o s 的路由协议，在一定程度上实现了端到端的 传输速率保证、网络拥塞控制以及负载平衡机制。 s p e e d 协议的设计目标是通过一个期望的传输速度贯穿全网来支持软实时通 信服务，以此达到端到端的传输时延与源节点和目的节点的距离成正比例的目 标。s p e e d 协议中的每个节点记录所有相邻节点的地理位置信息和转发速度，并 设定一个速度门限。当节点接收到一个数据包时，根据这个数据包的目的位置把 相邻节点中距离目的位置比该节点近的所有节点划分为转发节点候选集合。然后 把转发节点候选集合中转发速度高于速度门限的节点划分为转发节点集合，在这 个集合中转发速度越高的节点被选为转发节点的可能性越大。如果没有节点属于 这个集合，则利用反馈机制更新路由。这样就保证传输的实时性，避免了堵塞。 同时，因为传输延时越小的区域传输负荷越小，这样就分担了整个网络的传输负 荷，从而分担了每个节点的能量消耗【1 4 j 。 s p e e d 协议主要由以下4 个部分组成： ( 1 ) 延迟估计机制：根据a c k 报文时间戳，在相邻节点之间交换通信延迟， 1 2 以得到网络负载情况，判断网络是否发生拥塞； ( 2 ) 相应算法：节点利用局部地理信息和传输速率信息选择下一跳的节点； ( 3 ) 邻居反馈策略：通过邻居反馈机制保证网络传输畅通； ( 4 ) 反向压力路由变更机制：通过反向压力路由变更机制避免拥塞和路由 空洞。 s p e e d 协议是一个空分的、基于网络流的无线传感器网络协议，s p e e d 协议 使用反馈机制来使m a c 层性能达到最优；对于需要更新路由的分组，则采用临近 反馈循环机制。s p e e d 协议能满足端到端延迟和预定传输速度，消耗的总传输能 量较少