（通信与信息系统专业论文）无线传感器网络路由技术研究与实现.pdf

中文摘要 本文以国家发改委项目伸v 6 无线传感器网络节点为基础，围绕无线传感器网络的 路由技术以及休眠调度问题展开研究。 第一部分介绍了无线传感器网络的起源与发展、网络特点及其应用领域，重点讨论了 无线传感器网络中路由协议和休眠调度算法的设计要素等关键问题，并对现有几种典型无 线传感器网络路由协议和休眠调度算法进行了分析。 第二部分针对无线传感器网络的覆盖性和连通性问题，在假设传感器节点地理位置信 息已知的条件下，设计了一种包含全连通群的建立和维护以及群内节点休眠调度的全新算 法f c c s 。该算法采用保证群内节点彼此一跳可达的全连通群分群方法，以及分布式节能 的休眠调度策略，最大程度上减少传感器网络的能量消耗，延长了网络寿命。仿真结果表 明：该算法具有较好的网络覆盖性，且较为节能。 第三部分根据项目的实际需求，设计了一种基于树型结构网络的能量高效的无线传感 器网络路由协议t r e e s 。该协议构造以s i n k 节点为根的树型结构网络，节点根据有无后续 节点以及休眠后对网络覆盖性的影响来决定是否休眠。仿真性能表明其在保证信息采集的 完整性和传输可靠性的基础上，降低了能耗，延长了网络寿命。 最后两部分着重介绍了“i p v 6 无线传感器网络节点”项目中路由协议st r e e s 的设 计与实现。st r e e s 是t r e e s 的简化协议，它在系统中作为一个模块，通过接口与应用 模块、s i n g l e h o p m a n a g e r 模块、功率控制模块和m a c 模块进行信息交互。目前已在p c 机、m i c a 2 d o t 节点和自主设计节点上完成了对路由模块的测试，与应用模块和下层模块接 口的调试，以及路由模块与其它模块的联调，结果表明：路由模块功能正常。 关键词：无线传感器网络、路由协议、休眠调度、节能、连通性、覆盖性、树型结构网络 第1 页 a b s t r a c t t h i st h e s i si sb a s e do nt h ep r o j e c to ft h en a t i o n a ld e v e l o p m e n ta n dr e f o r m c o m m i s s i o n - - - n o d eo fi p v 6w i r e l e s ss e n s o rn e t w o r k s ，f o c u s i n go nt h er o u t i n gt e c h n o l o g ya n d t h ei s s u e so fs l e e p i n gs c h e d u l ei nw i r e l e s ss e n s o rn e t w o r k s t h ef i r s tp a r to ft h i sa r t i c l eg i v e sa no v e r v i e wo fr e s e a r c ho nw i r e l e s ss e n s o rn e t w o r k s i n c l u d i n gt h eo r i g i n , t h ed e v e l o p m e n t ，t h ec h a r a c t e ra n dt h ea p p l i c a t i o no fw i r e l e s ss e n s o r n e t w o r k s t h ek e yi s s u e so fr o u t i n gp r o t o c o l sa n ds l e e p i n ga l g o r i t h m si nw i r e l e s ss e n s o r n e t w o r k s ，s u c ha st h ef a c t o r sw h i c ha f f e c tt h ed e s i g na r ed i s c u s s e dw i t he m p h a s i s ，a n ds o m e c u r r e n tt y p i c a lr o u t i n gp r o t o c o l sa n ds l e e p i n ga l g o r i t h m sa r ea n a l y z e d i nt h es e c o n dp a r t , a i m i n ga tt h ei s s u eo fs e n s i n gc o v e r a g ea n dc o n n e c t i v i t yi nw i r e l e s s s e n s o rn e t w o r k s ，ac o m p l e t en e wa l g o r i t h mi sp r o p o s e d ，o nt h ep r e m i s eo fs e n s o r s p o s i t i o n a w a r e n ea l g o r i t h ma d o p t sac l u s t e r i n gm e t h o da n dad e c e n t r a l i z e ds l e e p i n gm e t h o dt or e d u c e t h ee n e r g yc o n s u m p t i o no fw i r e l e s ss e n s o rn e t w o r k sa n dt op r o l o n gt h el i f e t i m eo fw i r e l e s s s e n s o rn e t w o r k sf u r t h e s t n 他f u l l yc o n n e c t e dc l u s t e r i n gm e t h o de n s u r e st h a ta l ln o d e si na c l u s t e rc a nc o m m u n i c a t ew i t he a c ho t h e rw i t h i no n eh o p t h er e s u l to fs i m u l a t i o ni n d i c a t e st h a t t h ea l g o r i t h mc a nm a i n t a i ns e n s i n gc o v e r a g ea n dc o n n e c t i v i t yi nw i r e l e s ss e n s o rn e t w o r k s ，w h i l e t h ee n e r g yc o n s u m p t i o no f s e n s o rn e t w o r k si ss m a l l i nt h et h i r dp a r t ，b a s i n go nt h ea c t u a lr e q u i r e m e n t so ft h ep r o j c o t , at r e eb a s e de n e r g y e f f i c i e n tr o u t i n gp r o t o c o lt r e e si sd e s i g n e d t h i sp r o t o c o lc o n s t r u c t sat r e eb a s e dn e t w o r k r o o t e df r o mt h es i n kn o d e ，a n dt h en o d e sd e c i d ew h e t h e rt oa c t i v eo rn o t ，a c c o r d i n gt ot w o q u a l i f i c a t i o n s o n ei si ft h en o d e sh a v ea n yf o u o w i n gn o d e s n 圯o t h e ri st h ee f f e c to nt h e c o v e r a g eo ft h en e t w o r k sw h e nt h en o d e ss l e e p 1 1 l cr e s u l to fs i m u l a t i o ns h o w st h a tt r e e s l o w e r st h ee n e r g yc o n s u m p t i o na s w e l l a sg u a r a n t e e st r a n s m i s s i o na n dc o n s e r v e sn e e d e d c o v e r a g er a t i os ot h a tl e n g t h e n st h en e t w o r kl i f e t i m ee f f e c t i v e l y n el a s tt w op a r t so ft h i sa r t i c l ee m p h a s i z eo nt h ed e s i g na n dt h ei m p l e m e n t a t i o no ft h e r o u t i n gp r o t o c o l 盯r e e s ，w h i c hi sap a r to ft h ep r o j c o tn a m e dn o d eo fi p v 6w i r e l e s ss e n s o r n e t w o r k s i nst r e e ss o m em e c h a n i s mo ft r e e si ss i m p l i f i e d st r e e se x i t sa sam o d u l e i nt h e s y s t e m ，u s i n g i n t e r f a c e st o e x c h a n g e i n f o r m a t i o nw i t h a p p l i c a t i o nm o d u l e ， s i n g l e h o p m a u a g e rm o d u l e p o w e rc o n t r o lm o d u l ea n dm a cm o d u l e 1 1 1 ed e b u g g i n go fr o u t i n g m o d u l eo np c , m i c a 2 d o tn o d ea n ds e l f - d e s i g n e dn o d e ，t h ei n t e r f a c e st e s t i n ga m o n gr o u t i n g m o d u l e ，a p p l i c a t i o nm o d u l ea n dl o w e rl a y e rm o d u l e ，a sw e l la st h es y s t e mt e s t i n gb e t w e e nt h e r o u t i n gm o d u l ea n dt h eo t h e rm o d u l e sh a v eb e e na c c o m p l i s h e d t h et e s t i n gr e s u l t ss h o w st h a t t h er o u t i n gm o d u l ef u n c t i o n sw e l l k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，r o u t i n gp r o t o c o l ，s l e e p i n gs c h e d u l e ，e n e r g y c o n s e r v i n g ，c o v e r a g e ，c o n n e c t i v i t y , t r e eb a s e dn e t w o r k s 第1 i 页 笪星三堡查堂堕兰垡丝苎 表目录 表lo g d c 仿真参数配置1 7 表2 迕e s 仿真参数配鹭2 5 第v i 页 信息工程大学硕j ：学位论文 图目录 图1 无线传感器网络体系结构2 图2 无线传感器网络协议栈2 图3 定向扩散的路由建立过程 图4d e b o r a he s t r i n 提出的传感器节点能量消耗情况 ! ； 6 图5o g d c 中待激活节点的理想位置9 图6g a f 中虚拟网格的划分1 0 图7 激活节点位置关系1 4 图8 群初步构造时的消息交互过程1 5 图9 群间连通方式1 6 图1 0 确定备选网关的消息交互过程1 6 图ll 节点状态转换 图1 2f c c s 仿真性能 图1 3 群树结构网络 图1 4 收到a p l _ c o n n e c t 消息的处理流程 图1 5 等待接收印l _ c o n n e c t 消息的计时器时间到的处理流程 图1 6 收到a p l _ c o n n e c t _ r e p l y 消息的处理流程 。1 7 1 8 。2 l 。2 2 。2 3 图1 7 等待回复计时器时间到的处理流程2 4 图1 8 等待激活消息的计时器时间到的处理流程2 4 图1 9 收到a c t i v em s g 消息的处理流程2 4 图2 0 收到u p d a t e _ e n e r g y 消息的处理流程 图2 1t r e e s 仿真性能 2 5 ：1 6 图2 2 无线传感器应用程序的组件结构实例2 8 图2 3 路由模块与其它模块的主要接口2 9 图2 4t r e e sc o r e 模块收到a p ! c o n n e c t 的处理3 0 图2 5t r e e s _ c o r e 模块收到a p l _ c o n n e c t _ r e p l y 的处理3 1 图2 6 节点等待激活消息计时器超时的处理3 l 图2 7t r e e sp a e k e t f o r w a r d e r 模块对应用层传送分组的处理3 3 图2 8t r e e sp a c k e t f o r w a r d e r 模块对s i n g l e h o p 层传送分组的处理3 4 图2 9p c 机上局部测试拓扑。3 6 图3 0 调试信息输出4 0 图3 1m i c a 2 d o t 节点与m i b 5 1 0 测试板4 0 图3 2m i b 5 1 0 板程序下载赛面4 i 第v i i 页 信息1 = 程大学硕士学位论文 图3 3s i n k 与节点a 的信息交互过程4 2 图3 4m i c a 2 d o t 节点上局部测试拓扑 图3 5s i n k 与节点a 、b 的信息交互过程4 4 图3 6 侦听消息分组 图3 7 自主设计节点 图3 8 程序下载界面 图3 9 侦听消息分组 4 6 4 7 ，4 7 4 7 图4 0t i n y o s 系统消息格式6 0 第v i i i 页 学位论文原创性声明 所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中标注和致谢的相关内容外，论文中不包含其他个人或集体已经公开的研究成 果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文题目：玉缮佳壁墨圆终路由拄苤丑究当塞理 学位论文作者签名：受壹日期：加6 年6 , e l 髟e t 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 学位论文题目： 玉缝焦壁矍圆终堕由撞苤硒塞皇塞理 学位论文作者签名： 作者指导教师签名： 日期：彩莎年易7 1 ；日 日期：彩年手月刍e t 信息1 = 稃大学硕士学位论文 第一章绪论 随着信息技术的飞速发展，特别是近年来微型机电系统技术和低功耗数字集成技术的 日益成熟和完善，无线传感器网络以其获取信息精度高、布署灵活性强、可靠性高、经济 性好等特点，在军事侦察、环境监测，工农业控制与监视、智能建筑、交通管理以及医疗 卫生等诸多领域具有非常广阔的应用前景。目前无线传感器网络已被列为全球未来的三大 高科技产业之一，成为信息技术领域的一个新的研究热点与开发方向，引起了许多国家相 关部门的极大关注。 1 1 无线传感器网络概述 1 1 1 无线传感器网络的起源和发展 无线传感器网络“随铷( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) ，又称传感器网络，是由 大量密集布设的智能传感器节点构成的网络，它采用自组织方式配置节点，节点间通过协 同工作完成感知、数据采集、简单处理并通过多跳通信方式最终将监测区域的信息数据传 送给观察者。 传感器网络的研究起步于2 0 世纪9 0 年代末期，最早从事这方面研究工作的是美国。 美国对传感器网络的研究首先从军事应用方面展开，美国国防部和各军事部门都对传感器 网络给予了高度重视，把传感器网络作为了一个重要研究领域，设立了一系列的军事传感 器网络研究项目。美国自然科学基金委员会也于2 0 0 3 年制定了传感器网络研究计划，投 资巨额，以支持相关基础理论的研究。一些信息工业界巨头如英特尔公司、微软公司等也 很早就开始了传感器网络方面的工作，设立或启动了相应的行动计划。日本、英国、意大 利、巴西等国家也对传感器网络表现出了极大的兴趣，纷纷展开了该领域的研究工作。从 2 0 0 0 年起国际上对传感器网络的研究已取得一些初步性成果，但是这些成果距实际应用的 需求还相距甚远o “啪。 近年来，我国也积极开展了一系列传感器网络方面的研究工作，但是这些工作都还处 在起步阶段。 1 1 2 无线传感器网络的体系结构 无线传感器网络系鲥”“”圳巾“嘲通常包含传感器节点( 即普通节点) 、汇聚节点( s i n k ) 和管理节点。传感器节点兼顾了终端和路由器的双重功能，除了进行本地信息数据采集和 处理外，还要为其它节点回传的采集数据进行转发，同时还能与其它节点协同工作完成一 些特殊任务。汇聚节点既可以是一个能力较强的传感器节点，也可以是没有监测功能只带 有无线通信接口的网关设备，它的功能是将无线传感器网络与外部网络( 如i n t e m e t ) 相连， 实现两种协议栈之间的通信协议转换，同时发布管理节点的监测任务并将收集的数据转发 第1 页 信息工程大学硕士学位论文 到外部网络上。 传感器节点将采集到的数据通过其它节点的多跳转发最终传送给汇聚节点，最后通过 外部网络或者卫星传送到管理节点，用户可通过管理节点发布监测任务和获得监测数据。 图1 无线传感器网络体系结构 1 1 3 无线传感器网络的协议栈 无线传感器网络的协议栈“1 “”邝1 包括五层：物理层、数据链路层、网络层、传输层、 和应用层，与互联网协议栈各层相对应。另外。该协议栈还包括三个平台：能量管理平台、 移动管理平台和任务管理平台。各层协议和平台的功能如下： 物理层提供简单但健壮的信号调制和无线收发技术； 数据链路层负责数据成帧、帧检测，媒体访问和差错控制； 网络层负责路由生成和路由选择： 传输层负责数据流的传输控制； 应用层包括一系列基于监测任务的应用层软件； 能量管理平台管理传感器节点的能量使用； 移动管理平台检测和注册传感器节点的移动，维护到数据汇聚节点的路由； 任务管理平台在给定区域内平衡和调度监测任务。 图2 无线传感器网络协议栈 第2 页 信息工稃大学硕七学位论文 1 1 4 无线传感器网络的特点 无线传感器网络是一种特殊的网络体系结构，与传统的无线网络相比有者许多鲜明的 特点“1 嘲哪嘲； 传感器节点体积小，计算能力有限。 无线传感器网络中的传感器节点具有嵌入式处理器和存储器，这使得传感器节点具备 了一定计算和处理能力，但是由于体积和成本的限制，使得这些设备的能力和容量有限。 通信范围小。 无线传感器网络中，传感器节点通过。多跳”的方式来完成数据的传输，因此传感器 节点的通信范围通常只有几十到几百米。 传感器节点数量多，网络动态性强。 无线传感器网络通常由成千上万的传感器节点，密集布设而成，且多应用于环境恶劣 的场合，经常会有节点失效和新节点加入，网络拓扑变化较为频繁。 业务方向性强。 无线传感器网络的业务主要有薅个方面：一是普通节点( 图1 中所示非s i n k 的普通传感 器节点) 将采集数据向s i n k 回传；二是s i n k 向普通节点发布查询请求。而两个普通节点之间 通常没有通信需求。 数据冗余大。 由于传感器节点布设密集，多个节点在位置上邻近，使得这些节点可能采集到大量相 同或相关的数据。 电源能量有限。 传感器节点通常使用钮扣电池供电，电源能量极为有限，且无线传感器网络通常应用 于环境恶劣的无人区，因此电池不易替换。 1 1 5 无线传感器网络的应用 无线传感器网络可广泛应用于军事、环境、医疗等领域“蛳。 军事应用 无线传感器网络主要应用于军事领域，由于其特有的部署方便、抗毁性强等特点，是 未来数字化战争获取敌方信息的重要技术手段之一。 环境监测 在一些特殊环境的监测方面( 如森林火灾监测) ，采用一些传统的方法无法及时、准 确地获得监测数据信息，而传感器网络就能克服这些缺点。 医疗健康 医生可以通过安装在病人身上的传感器节点，及时掌握病人病情，并进行相应处理， 无线传感器网络为远程医疗提供了便利的条件。 第3 页 信息工稃大学硕士学位论文 1 2 无线传感器网络路由协议研究 1 2 1 无线传感器网络路由协议设计的要求和考虑因素 路由协议的主要任务是通过中间节点转发将数据分组由源节点传送到目的节点。它包 括两方面内容：路由的建立与维护。由于传统无线网络的首要任务是提供高质量的服务以 及合理地利用网络带宽，因此要求路由协议完成移动条件下最优路径的寻找，拥塞避免和 流量均衡等功能，而并未把能耗问题作为考虑的重点。对于无线传感器网络而言能量资源 非常紧张，必须把如何节约能量资源作为首要考虑因素，因此传统无线网络的路由协议不 适用于无线传感器网络，设计无线传感器网络路由协议需要满足的要求“。“1 有： 能量有效性 为最大限度地延长无线传感器网络的寿命，路由协议在进行路径选择时，要把能否节 约节点能耗，能否使网络能耗均衡作为衡量路径好坏的首要标准。 简单性 为减少能耗，无线传感器网络采用了多跳通信模式。然而单个节点的计算、存储和通 信能力十分有限，只能获得局部拓扑信息。不能进行较为复杂的路由计算。 健壮性和容错性 无线传感器网络多应用于恶劣环境，传感器节点经常会因为能量耗尽或环境因素而失 效，加之无线链路自身的不稳定性，要求无线传感器网络具有一定的容错能力。 可扩展性 在无线传感器网络中，由于经常有节点失效和新节点加入，网络拓扑动态变化频繁， 因此路由机制需要具备一定韵可扩展性。 快速收敛性 传感器网路拓扑结构动态变化，节点能量资源和通信带宽有限，只有路由机制快速收 敛，才能适应网络拓扑的变化，减少通信开销，提高消息传输效率。 1 。2 2 无线传感器网络路由协议分类 传感器网络路由协议的分类方法很多，迄今为止国际上尚未有一套统一的标准。目前 按照形成网络拓扑结构的不同可将传感器网络路由协议分为平面式和层次式两类。平面式 路由协议较为简单，网络中所有节点地位平等，但是这种协议的可扩展性较差，为适应网 络动态变化而维护路由时，控制开销较大。层次式路由协议的基本思想是将传感器节点分 群。把通信划分为群内通信和群间通信。由群首节点完成群内通信、数据聚合以及把聚合 后的数据传送给s i n k 节点的任务。这种协议形成的层次式网络结构中，群内成员的分工明 确，不需要维护复杂的路由信息，大大减少了控制开销，同时具有良好的可扩展性，但是 一旦群首节点失效就需要进行群的重构，且保持群问连通性的机制较为复杂。 第4 页 信息工稃大学硕士学位论文 1 2 3 几种典型无线传感器网络路由协议介绍 ( 1 ) 洪泛法( f l o o d i n g ) ” 这是一种经典的路由协议，它无需维护网络拓扑和进行路由计算，只需简单地将收到 的消息以广播形式转发出去即可。该协议虽然简单、实效，但是未考虑到传感器节点的能 源限制，在网络运行过程中，节点将多次收到邻居节点转发的相同消息( “内爆”和“重 叠”现象) ，不利于节能。 ( 2 ) 定向扩散法( d i r e c t e dd i f f u s i o n ) m 帆嘲 该协议是一种基于查询的路由机制，可分为周期的兴趣扩散、梯度建立和路径加强三 个阶段。首先s i n k 节点广播带有查询内容的兴趣消息( i n t e r e s t ) ，其它节点在收到兴趣消 息时建立到s i n k 的梯度( g r a d i e n t ) ，最后节点将根据查询要求采集到的数据沿加强路径传 回s i n k 。定向扩散法是一种较为节能的路由协议，并且能较好地应对网络拓扑的动态变化。 但是这种协议不适合应用于需要连续数据传送的应用中( 如环境监测等) ，且兴趣扩散过 程中能量和时间开销较大。 镑 0o o h ) 咖 oo s i n ko 臀通节点 a ) 兴趣扩散( b ) 梯度建立( c ) 路径加强 图3 定向扩散的路由建立过程 ( 3 ) s p i n ( s e n s o rp r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) “o 】 s p i n 是一种以数据为中心的自适应路由协议，包含三种类型的消息a d v 、r e q 和 d a t a 。节点在发送数据d a t a 之前，先广播带有采集数据属性描述信息的a d v ，邻居节 点收到后若愿意接收该节点发送的d a t a 就向其发送一个r e q ，节点收到r e q 后即可向 该邻居节点发送数据。 s p i n 采用两种机制克服了洪泛法中数据大量重复传送的缺点，能够更加高效地利用能 源，从而延长网络寿命： 协商机制( n e g o t i a t i o n ) ：为了避免“内爆”和“重叠”现象的产生，节点在发送数据 前进行协商，确保只转发有用信息。为协商成功，节点问发送描述采集数据属性的 元数据( r e c t a - d a t a ) ，与整个采集数据相比元数据的长度要短的多。 资源自适应( r e s o u r c e - a d a p t i o n ) ：s p i n 中，每个节点在发送或接收数据前，都必须 查看自身的能量状况，当节点能量较低时，就相应地中断一些操作，减少通信行为。 第5 页 信息工程大学硕十学位论文 ( 4 ) l e a c h ( l o w e n e r g y a d a p t i v e c l u s t c d n g h i e r a r c h y ) l e a c h 是一种典型的层次式路由协议，它将网络的工作时间分成轮，每轮包括构建 期和稳定期。在构建期，完成群首选举及群首和群成员节点间的信息交互；稳定期分成若 干帧，每一帧成员节点在分配给自己的时隙向群首发送数据，群首将数据汇聚后发送给s i n k 节点。一轮结束后，进行群的重构。 该协议中，节点确定自身是否成为群首的方法为：节点选取0 到l 之间的随机数与t ( m 比较，若选取的随机数小，则成为群首。t ( 甩) 的计算方法如下： ip t ( 疗) ：l l - p * r m o d ( 1 p ) 以 ( 式1 ) 【0 其他 其中，尸为群首数占全部节点数的百分比，为当前轮数，r m o d ( 1 p ) 为前1 p 轮中未 当选成群首的节点个数，g 为在前i p 轮中未当选群首的节点集合。 l e a c h 所采用的机制使得网络中因能量耗尽而失效的节点呈随机分布状态，一定程 度上延长了网络的寿命。但是l e a c h 假设群内节点彼此都在一跳通信范围内，极大地限 制了网络的规模，同时动态分群的方式也带来了大量额外的开销。 1 3 无线传感器网络中休眠调度算法研究 传感器节点的体积微小，以电池供电，能量资源和工作能力都十分有限，加之无线传 感器网通常应用于环境复杂的无人区，不可能通过更换电池来补充能量，因此如何高效、 节约地利用传感器节点的能量是无线传感器网需要解决的首要难题，也是在设计各层协议 时必须考虑的首要因素。 2 。 l 1 5 襄- 。 5 0 发送 接收空闲休眠 图4d e b o r a he s t r i n 提出的传感器节点能量消耗情况 传感器节点消耗的能量主要源自三方面：感知、处理和通信，其中通信消耗的能量所 占的比例最大。节点通信时的状态分为四种：发送、接收、空闲和休眠“1 。从图4 中不难 看出休h 民状态时节点消耗的能量最少，且远小于前三种状态时消耗的能量。因此只要让暂 时不需要工作的节点尽快转入休眠，就能大大减少传感器网络的能量消耗。此外，无线传 感器网络中通常布设大量传感器节点，节点密集程度较高，如果所有节点都工作，既会带 第6 页 信息工挣大学硕士学位论文 来不必要的能源浪费，又会在收集数据时存在高度相关和冗余，甚至在传送数掘时还会发 生冲突，因此网络中只需部分节点工作，其余节点都进行休眠。此外，无线传感器网络中 通常布设有大量的传感器节点，拓扑上存在高度冗余，因此可通过只由一部分节点工作的 方法来节能。 综上所述，无线传感器网络中存在的一个重要问题是休眠调度。 1 3 1 休眠调度考虑的因素 在组网期，路由层可根据节点是否满足特定要求来决定其是否需要激活，以分布式休 眠调度形成节点对网络环境地轮流监测，从而延长网络寿命。工作节点在不需要进行收发 操作时，可关闭收发装置转入休眠，从而进一步达到节能的目的。 现有传感器网络路由协议在进行休眠调度时考虑的主要因素有： ( 1 ) 连通性：在无线传感器网络中，由于普通节点之间没有业务需求，因此连通性是 指网络中任意节点是否都至少有一条到s i n k 节点的路由。 任何传感器网络路由协议都必须首先保证连通性，否则，传感器网络就无法正常工作。 早期对休眠调度的研究，主要考虑的就是这方面的因素，节点在不对网络的连通性造成不 良影响的情况下才可以进行休眠。a s c e n t m l 与s p a n “”算法中节点休眠调度的方法都是 基于对网络连通性影响的考虑，两者的不同之处在于：a s c e n t 中节点在确定无邻居节点 需要其进行中继时，即可休眠；而s p a n 中节点在有邻居节点需要其进行中继续时，才可 激活，否则就休眠。 ( 2 ) 覆盖性：是指传感器网络中激活节点所能探测的有效范围以及对其覆盖的重数。 根据对监测区域的覆盏情况又分成两种情况： 完全覆盖：即全部激活节点有效探测范围能够包含整个监测区域。 非完全覆盖：即全部激活节点有效探测范围不能包含部分监测区域。 覆盖性直接决定了传感器网络提供数据的完整性和精确程度。随着研究的深入。越发 的显示出覆盖性对无线传感器网络的重要性。后来出现的一系列休眠调度算法都在考虑覆 盖性的基础之上，研究了覆盖性与连通性之间的联系。p e a s “”算法规定节点从休眠转入激 活状态后，通过与邻居节点交互信息来确定自己的探测范围内是否已存在其它工作节点。 若是，则节点转入休眠；o g d c “”算法则采用一种保证对监测区域完全覆盖的调度机制。 在这两种算法的调度规则下，如果通信距离和感知距离满足一定关系，就能保证工作节点 之间是连通的。 1 3 2 几种休眠调度算法介绍 1 3 2 1 平面式路由协议中的休眠调度算法 ( 1 ) a s c e n t ( a d a p t i v es e l f - c o n f i g u r i n gs e n s o rn e t w o r k st o p o l o g i e s ) a s c e n t 中节点能够根据自身获得的信息( 邻居节点数、邻居节点的分组丢包率、是 第7 页 信息工稃大学硕士学位论文 否收到请求加入消息) 判断对连通性的贡献，从而决定是否加入网络。这种休眠调度方法 考虑的因素为连通性。 休眠调度涉及的关键技术： 节点状态的动态改变： 若节点的邻居激活节点很少，分组丢失率很低，则表明此时业务较少，该节点不 需要激活。 若节点的邻居激活节点少，分组丢失率很高，则表明缺少中继节点，该节点需要 激活。 若节点的邻居激活节点多，分组丢失率高，则表明激活节点过多，分组碰撞严重， 该节点不能激活。 若节点收到了h e l p 消息，则表明有邻居节点需要中继，该节点需要激活。 ( 2 ) p e a s ( p r o b i n ge n v i r o n m e n ta n da d a p t i v es l e e p i n g ) p e a s 认为一个节点感知范围内只要存在一个工作节点，节点就成为冗余节点而不必 激活。这种休眠调度方法实质上考虑的是覆盖性，但它并不能保证休眠节点的感知范围被 其它工作节点完全覆盖。文献【1 6 】中证明了当传感器的通信距离辱和感知距离耳满足 辟2 ( 1 + 压) r p 的关系时，p e a s 能保证工作节点之间的连通性。 休眠调度涉及的关键技术： 基于位置的探测：节点初始时处于休眠状态，随机休眠时间到节点醒来，进入探 测状态，在感知范围内发送探测消息，若收到其它已激活节点的回复，则再次休 眠，休眠时间r 由概率密度函数厂( f ，) = a e 一鸩( 其中z 为探测速率，即节点在感知 范围内发送探测消息的速率) 确定；否则激活，进入工作状态。 自适应休眠：所谓自适应体眠是指通过调整每个节点的探测速率a ，达到使工作节 点获得的所有邻居休眠节点的探测速率之和a 尽量保持在期望速率乃的目的，其 中乃由具体应用中允许的最大监测问隔来决定。 ( 3 ) o g d c ( o p t i m a l g e o g r a p h i c a ld e n s i t y c o n t r 0 1 ) o g d c 试图用最少的激活节点来完全覆盖整个监测区域，当一个节点的探测范围被其 它激活节点完全覆盖时，该节点就可以休眠。o g d c 在进行休眠调度时考虑的也是覆盖性， 文献【1 7 】中指出当传感器节点传输距离不小于感知距离的两倍时，这种休眠调度算法在保 证对监测区域完全覆盖的同时，又保证了工作节点之间的连通性。 第8 页 信息工程大学硕士学位论文 休眠调度涉及的关键技术： 确定激活节点的准则：文献 1 7 】中提出并证明了，在节点的感知范围面积远远小于监 测区域面积，且所有节点感知范围相同的前提下，对监测区域完全覆盖且网络能耗较小的 情况为：在监测区域内至少有两个节点的感知范围相交，且所有交点都被第三个节点的感 知范围包含的条件下( 当网络中节点密度较高时可保证) ，任意三个激活节点构成边长为 3 ( 其中为传感器节点的感知距离) 的等边三角形。 据此给出o g d c 确定激活节点的两条准则： 准则一：若已知一个激活节点位置，则下一个激活节点的理想位置在该激活节点的 3 ，距离处( 见图5 ( a ) ) ： 准则二：若已知两个激活节点位置，则第三个激活节点的理想位置在这两个激活节点 连线中垂线延长线上且与这两个节点圆盘的交点距离处( 见图5 ( b ) ) ( a ) ( b ) 图5o g d c 中待激活节点的理想位置 1 3 2 2 层次式路由协议中的休眠调度算法 层次式路由协议将网络中的节点划分成群，群内节点分为群首和普通节点，一些分群 方法中还可能存在网关节点。群首完成群内通信、数据聚合以及把聚合后的数据向s i n k 节 点传送的任务，因此在整个过程中必须始终激活。在相邻两群群首无法直接通信的情况下， 需要有网关节点进行中继从而保证网络的连通性，因此网关节点也必须始终激活以下介 绍几种层次式路由协议中使用的休眠调度算法。 ( 1 ) g a f ( g e o g r a p h i ca d a p t i v ef i d e l i t y ) 眦9 1 g a f 根据地理位置信息将监测区域划分成虚拟的网格，节点按照各自的地理位置划入 相应的网格，每个网格周期选出一个节点( 即群首) 激活，其它节点进行休眠。这种算法 主要考虑的是网络的连通性，但是它没有考虑到，实际网络中依靠地理位置信息推断节点 之间的连接性，事实上是不准确的。 休眠调度时涉及的关键技术： 第9 页 信息工程大学硕七学位论文 ( 1 ) 等价节点：所谓两个节点等价是指对通信而占，一个节点可以代替另一个节点 对分组进行中继转发。 ( 2 ) 虚拟网格：g a f 根据节点的地理位置信息和通信距离。将监测区域划分成若干 个虚拟网格，正方形网格的边长r 与节点的通信距离r 满足下列关系： r 2 + ( 2 r 2 ) s r 2 j ，睾 ( 式2 ) 这样就保证相邻两个虚拟网格中的任意两个节点可直接通信。因此同一个虚拟网格中 的节点是等价的，只需要有一个激活节点即能保证整个网络的正常工作。 j 一一一4 一一一_ l 一一一l ：o：。o ： ： 1 0 i oi u i l = - iz 手一一一4 一一一+ 图6 g a f 中虚拟网格的划分 ( 2 ) c e c ( c l u s t e r - b a s e de n e r g yc o n s e r v a t i o n ) 删 c e c 不依赖于地理位置信息，它通过直接且自适应地测量网络的连通性来确定冗余节 点，进行休眠调度。但是这种算法未考虑到网络的覆盖性问题。 休眠调度时涉及的关键技术： ( 1 ) 群的构造：该算法将节点组织为有重叠的群。群首和群内任意节点一跳可达。 群内任意两节点至多两跳可达。同时属于两个群的节点为网关节点，既非群首又非网关的 节点为普通节点。 ( 2 ) 群首的选择：节点通过邻居信息交互，得到其它节点的估计寿命( 估计寿命是 指节点以最大速率消耗能量，直到能量耗尽为止，所持续的时间。) 等信息。当节点发现 自己在所有邻居节点中估计寿命最大时，就选择自己为群首。 ( 3 ) 工作网关的选择：群内可以与多个群首直接通信的节点为首要网关：可以与群 首和首要网关直接通信的节点为次要网关。为了减少能耗，如果相邻两群中存在多个网关 节点。就需要关闭一些冗余的网关节点。选择工作网关的规则为：首要网关优先级高于次 要网关：有多个群首邻居的网关节点优先级较高；估计寿命长的网关节点优先级较高。 1 4 课题的背景和主要工作 本课题来源于国家发改委项目母v 6 无线传感器网络节点。该项目的研究目标 为：设计并自主开发无线传感器网络节点的硬件平台，无线传感器网络与c n g i 互联的s i n k 第l o 页 信息工程大学硕士学位论文 节点；设计并自主开发i p v 6 无线传感器节点的网络层协议，m a c 层协议，适应i p v 6 特点 的数据汇聚技术以及适合传感器网络的安全机制，并提出相应的标准化建议；设计并开发 数据处理与监视控制予系统；构建由无线传感器节点、s i n k 节点及数掘处理与监视控制子 系统组成的面向特定应用的示范演示系统。 作者的工作围绕开发i p v 6 无线传感器节点的网络层协议展开。 2 0 0 5 年3 月g 月，深入理解无线传感器网路由协议设计方面的要求、考虑因素以及 关键技术等问题，着重对无线传感器网络中的休眠调度算法进行研究。提出了一种考虑覆 盖性的全连通群休眠调度算法f c c s ，在n s - 2 仿真平台上进行了仿真并与o