（计算机系统结构专业论文）无线传感器网络中的节点调度算法研究.pdf

摘要 摘要 无线传感器网络是由部署在监测区域内的传感器节点通过无线通信方式形 成的一个多跳自组织网络，具有低功耗、低成本及易于部署的特性，在军事安全、 环境监测、远程医疗等诸多领域有很好的应用前景。构成网络的传感器节点能量 有限，难以满足网络长期稳定运行的应用需求，限制了传感器网络的应用。用能 量有限的节点实现期望的网络生命期，成为传感器网络研究中最关心的问题。目 前最常见也是最直接的解决方法就是节点休眠调度策略：利用网络部署的冗余 性，通过保持冗余节点休眠，节省节点能耗，延长网络系统的生存期。 本文基于i e e e8 0 2 1 lm a c 协议，针对如何在满足应用需求的同时，提高网 络生存期，开展了以下研究工作： 针对目前缺少兼顾网络区域覆盖、网络连通和节点保护的节点调度策略，提 出一种基于分布式节点冗余性判定机制的节点休眠调度策略e c n s 算法。 e c n s 中，节点通过局部通讯获取局部拓扑信息，并利用该信息独立地判定其冗 余性；冗余节点进入休眠状态，其余节点则处于活跃状态，感知并传输数据。通 过关闭冗余节点，e c n s 可以在满足网络覆盖、连通以及节点自我保护的同时， 有效的延长网络生存期。e c n s 可以有效地平衡网络中节点的负载和能耗，具有 分布式的实现方式和低通讯代价及低计算复杂度。通过与分簇式的路由协议 l e a c h 相结合，对e c n s 的性能进行了评估，仿真实验表明，与未使用e c n s 的l e a c h 协议相比，e c n s 可有效降低节点能耗，延长网络生存期。 针对多孤立目标连续监控的传感器网络，本文提出一种分布式的节点休眠调 度策略c t m n s 算法，以提高该类网络的节点能量利用率，延长网络生存期。 该算法可以对网络中多个孤立目标提供连续监控，允许不同的目标有不同的期望 覆盖度。在c t m n s 中，每个传感器节点都关联一个与节点分布和剩余能量相关 的权值，节点可以独立地计算其关联权值大小，并通过局部通信计算权值在临近 节点中的排序，利用节点冗余性判定机制，节点根据排序结果判定其冗余性，冗 余性为真的节点关闭电源处于休眠状态，其余节点进一步利用c t m n s 决定是否 保持活跃，以满足对目标的监控需求。仿真结果表明，c t m n s 可将对目标的有 效监控时间提高到无节点休眠调度策略的目标监控算法的2 7 倍。 关键词：无线传感器网络；节点休眠调度策略；网络生存期；网络覆盖；网络连 通；节点保护；目标监控 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 ki sam u l t i - h o pa dh o en e t w o r kc o n s i s t i n go fal a r g e n u m b e ro fs e n s o r sd e p l o y e di nt h em o n i t o r i n gr e g i o n s e n s o rn e t w o r kh a sp r o m i s i n g p r o s p e c t si nm a n ya r e a ss u c ha sm i l i t a r ym o n i t o r i n g ，e n v i r o n m e n ts u r v e i l l a n c ea n d t e l e m e d i c i n e ，s i n c ei ti se a s yt od e p l o ya n do p e r a t e sw i t hl o wc o s ta n dl o wp o w e r d u e t ot h es e v e r ee n e r g yc o n s t r a i n to ft h es e n s o rn o d e s ，w i r e l e s ss e n s o rn e t w o r kc a n h a r d l ys a t i s f yt h el o n g t e r mo p e r a t i o nd e m a n d h o wt ou s et h er e s o u r c el i m i t e ds e n s o r n o d e st oa c h i e v et h ed e s i r e dn e t w o r kl i f e t i m ei saf u n d a m e n t a lp r o b l e mo fw i r e l e s s s e n s o rn e t w o r k n o d es c h e d u l i n gs c h e m ei st h em o s tf r e q u e n t l yu s e da p p r o a c hi n l i t e r a t u r e ；b yp u t t i n gr e d u n d a n tn o d e si n t os l e e pm o d ea n dk e e p i n go n l yas u b s e to f s e n s o r sa c t i v e ，n o d es c h e d u l i n gs c h e m ec a nr e d u c et h ee n e r g yc o n s u m p t i o na n d p r o l o n gt 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 b a s e do ni e e e8 0 2 11m a c p r o t o c o l ，t h i st h e s i sf o c u s e so ne x t e n d i n gn e t w o r k l i f e t i m ew h i l es a t i s f y i n ga p p l i c a t i o nd e m a n d s p e c i f i c a l l y ，t h ef o l l o w i n gp r o b l e m sa r e s t u d i e di nt h i st h e s i s a ne n e r g ye f f i c i e n tc o v e r a g eb a s e dn o d e s c h e d u l i n ga l g o r i t h me n e r g ya w a r e c o v e r a g eb a s e dn o d es c h e d u l i n gs c h e m e ( e c n s ) i sp r o p o s e dt op r o l o n gn e t w o r k l i f e t i m ew h i l em a i n t a i n i n gn e t w o r k c o v e r a g e ，n e t w o r kc o n n e c t i v i t y a n ds e n s o r s e l f - p r o t e c t i o n e c n se n a b l e se a c hn o d et od e c i d ew h e t h e ri ti se l i g i b l et ot u r no f ft o c o n s e r v ee n e r g yt h r o u g hl o c a li n f o r m a t i o ne x c h a n g ew i t hi t sn e i g h b o r s e c n si s c h a r a c t e r i s t i co fi t sf u l l yd i s t r i b u t e dm a n n e r ，l o wo v e r h e a da n dl o a db a l a n c e t h e c l u s t e r - b a s e dr o u t i n ga l g o r i t h m ，l e a c h ，i si m p l e m e n t e dt oe v a l u a t et h ep e r f o r m a n c e o fe c n s ；s i m u l a t i o nr e s u l t ss h o wt h a te c n sc a ni m p r o v et h en e t w o r kp e r f o r m a n c e w i t hr e s p e c tt oe n e r g yc o n s e r v a t i o n ，l o a db a l a n c ea n dn e t w o r kl i f e t i m e c o n s i d e r i n gt h el a c k o fn o d es c h e d u l i n g a l g o r i t h mb a s e do n c o n t i n u o u s m o n i t o r i n go fi s o l a t e dt a r g e t s ，a n o v e ld i s t r i b u t e dn o d es c h e d u l i n ga l g o r i t h m ， c o n t i n u o u st a r g e tm o n i t o r i n gb a s e dn o d es c h e d u l i n gs c h e m e ( c t m n s ) i sp u t f o r w a r di n t h i st h e s i s t oi m p r o v et h ee n e r g ye f f i c i e n c ya n de x t e n dt h en e t w o r k l i f e t i m ef o ri s o l a t e dt a r g e t sm o n i t o r i n ga p p l i c a t i o n s ，c t m n sa c t i v a t e so n l yas u b s e t o fs e n s o r si nt h en e t w o r kt op r o v i d ed e s i r e dc o v e r a g el e v e lf o rm u l t i p l ei s o l a t e d t a r g e t s i nc t m n s ，e a c hs e n s o ri sa s s o c i a t e dw i t hal o c a t i o n - a n d e n e r g yd e p e n d e n t w e i g h t ，w h i c he v a l u a t e st h es e n s o r ss i g n i f i c a n c ei nt e r m so ft a r g e tm o n i t o r i n g e a c h s e n s o rc a l c u l a t e si t sa s s o c i a t e dw e i g h ti n d i v i d u a l l ya n dd e t e r m i n e si t sr e d u n d a n c y u a b s t r a c t e l i g i b i l i t yt h r o u g hl o c a lc o m m u n i c a t i o nw i t hi t sn e i g h b o r sb a s e do nt h er e d u n d a n c y e l i g i b i l i t yr u l e b yt u r n i n go f fr e d u n d a n tn o d e s ，c t m n sp r o l o n g sn e t w o r kl i f e t i m e w h i l ep r o v i d i n gd i f f e r e n t i a t e dc o v e r a g ef o rm u l t i p l et a r g e t s s i m u l a t i o nr e s u l t ss h o w t h a tc t m n sp r o l o n g st h en e t w o r kl i f e t i m et o2 7t i m e st h a to fn o n s c h e d u l e dt a r g e t m o n i t o r i n gs c h e m e k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k ，n o d es c h e d u l i n gs c h e m e ，n e t w o r kl i f e t i m e ， n e t w o r kc o v e r a g e ，n e t w o r kc o n n e c t i v i t y ，s e n s o rs e l f - p r o t e c t i o n ，t a r g e tm o n i t o r i n g i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：壶1 金鏖签字日期：j 壅孓盟 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 回公开口保密( 年) 作者签名： 委l 座蠹 签字日期：二巫# j 扯 翩躲型进 签字日期： 芈 第一章绪论 第一章绪论 无线传感器网络【l 】是由部署在监测区域内的大量传感器节点通过无线通信方 式形成的一个多跳自组织网络【2 】。近年来嵌入式系统、低功耗无线通信和微电子 机械系统等技术的发展，使得传感器网络在军事安全、环境监测、远程医疗及家 庭智能等诸多领域有巨大的应用前景【l 】【3 】。 传感器节点能量受限【4 】，而且一旦网络部署完成，节点能量补给非常困难p ； 为节约成本，网络部署者往往期望网络部署后可以长期稳定的运行。如何利用能 量有限的节点为网络部署者提供期望的网络生存时间，满足网络正常运行，成为 传感器网络研究中的热点问题【6 1 ；学者们围绕该问题进行了大量研究，涵盖了节 点硬件设计到网络协议设计的各个方面。节点休眠调度策略【2 】是目前使用较多的 方法，其基本思想为：利用传感器网络实际部署中的高度冗余性，提m 基于特定 应用需求的节点冗余性判定策略，仅保持网络中部分节点活跃，从而降低节点能 耗，提高能量利用率，延长网络生存期。 本文对传感器网络的网络特征和关键技术进行分析，指出当前传感器网络中 节点休眠调度策略存在的问题，结合实际网络部署的特点，提出兼顾网络覆盖、 网络连通和节点保护的休眠调度策略e c n s 和基于孤立目标集连续监控的节点 调度策略c t m n s ，并通过仿真实验验证二者在提高网络生存期方面的有效性。 本章首先概述传感器网络的体系结构和网络特点，然后介绍无线传感器网络中的 关键技术，最后给出本论文的研究内容和组织结构。 1 1 无线传感器网络概述 无线传感器网络是由部署在监测区域内的大量廉价微型传感器节点通过无 线通信方式形成的一个多跳自组织网络【2 1 1 7 1 ，网络中的大量节点协作地感知、采 集和处理网络部署区域中用户感兴趣的信息，并将信息发布用户1 7 儿引。 传感器节点低功耗低成本的特点【9 1 、嵌入式系统、低功耗无线通信和微电子 机械系统等技术的发展，以及传感器易于部署、自组织的优势1 1u 1 ，使得传感器网 络成为地理地形类应用、个人家庭类应用和社会环境类应用等多个应用领域的新 兴技术【l l 】，为信息感知和采集技术带来了革命性的变化【l 引。 构成无线传感器网络的每个节点都具有一定的数据感知、数据处理和数据通 讯的能力，节点通过单跳或者多跳的无线路由方式，将数据采集和处理的结果发 送给网络中的汇聚节点【7 】【13 1 。图1 1 描述了无线传感器网络的系统结构【7 】【旧】。网 第一章绪论 络中可以有一个或多个汇聚节点【1 4 】【1 5 】【i6 1 ，通常称为基站。 与普通的传感器节点相比，汇聚节点能量较高，具有比节点更- 一7 t 理 能力和通讯能力。汇聚节点收集节点发送的数据包，进行数据处理，并将处理后 的结果发送给与其相连的互联网或卫星，从而实现用户与传感器节点之间的相互 通信【7 】【1 7 】【1 8 】。 父- - 二二0 - - - _ 节点 甩户 篡谴 图1 1 无线传感器网络系统结构 与传统的无线局域网和a dh o e 自组织网络【2 0 】相比，无线传感器网络有其 独特的性质【2 1 1 f 2 2 】： ( 1 ) 节点资源受限，尤其是能量有限 构成传感器网络的廉价微型传感器节点由电池供电，主要有电池、传感器、 数据处理器、存储器和无线通信模块等部分组成【7 】【2 3 】【2 4 1 ，如图1 2 所示【7 】o 图1 2 传感器节点体系结构 构成传感器节点的电池是节点采集数据、处理数据和收发数据的唯- - 乩n r 。量来 源，而在大多数应用场景下，一旦网络部署完成，很难为节点补给能量【5 j ，这使 得节点能量严重受限，但实际应用中，网络部署者通常期望网络部署后可以有较 长的网络生存期【2 5 1 。在网络运行过程中，因节点能量耗尽造成的节点失效，将导 致部署区域中出现空白覆盖区域或者破坏网络连通性，甚至被网络攻击者利用成 为网络安全性漏洞【2 6 】【2 7 j 。 此外，构成节点的传感模块、数据处理模块、数据存储模块和数据通信模块 都因器件的限制，仅具有有限的能力，导致传感器节点仅有有限的数据采集能力、 有限的存储和处理能力及有限的带宽【2 8 】。具体说来，节点具有一定的传感半型2 9 】 和通讯半径【3 0 1 ，其感知范围和通讯范围通常可以分别定义为以自身为中心以传感 2 第一章绪论 半径和通讯半径为半径的圆形区域，节点只能采集感知范围内的数据，与位于其 通讯范围内的节点进行通讯【2 9 】【3 0 】；节点只能对数据进行简单的处理，存储有限 的数据。 如何利用资源受限的传感器节点，实现网络长期稳定运行的月标，达到网络 覆盖和网络连通等应用需求，成为传感器网络研究的核心问题，也是传感器网络 从理论研究到实际应用必须解决的问题之一。 ( 2 ) 网络动态性 传感器网络中节点能量有限是造成网络动态性的重要原因。网络部署后，节 点因能量耗尽无法执行正常的数据采集、数据处理和数据通讯任务，成为网络中 的失效节点。对部署在恶劣环境中的传感器节点而言，物理环境或人为破坏是造 成节点失效的另一个原因1 2 6 】。为提高网络健壮性，网络部署者可以在网络运行过 程中投放新的传感器节点，或在网络部署阶段，在监控区域中部署一些具有一定 移动能力的移动节点【3 1 p 2 p 3 】或移动汇聚节点【3 4 】【3 5 1 。因此，传感器网络的拓扑结 构呈现出高度的动态性，给网络带来了安全隐患 2 6 】，也为传感器网络的m a c 协 议设计【3 6 】【3 7 】和路由策略【3 】设计带来了巨大的挑战。 ( 3 ) 以数据为中心 传感器网络部署的目标就是收集用户感兴趣的数据，网络中大量的传感器节 点可以认为是数据源，而汇聚节点则是数据传送的目的地【7 】【3 8 1 。以数据为中心的 特点对传感器网络的部署有直接影响，也使得传统网络中以地址标识为中心的端 到端的路由机制不能直接应用于传感器网络，必须为传感器网络设计新的路由策 略【3 9 】f 4 0 】【4 l 】。同时，以数据为中心的特点使得吞吐率、网络延迟等传统网络的性 能评价标准不再适用于传感器网络，目前常以网络系统的生存期、网络覆盖度和 网络连通性【4 2 】【4 3 】【4 4 】等作为传感器网络的性能评估标准。 ( 4 ) 网络冗余性 传感器网络区别于传统无线a dh o c 网络的另一个显著特征是网络的高度冗 余性【4 4 1 。为提高网络的健壮性和可靠性，保证网络系统提交给用户的数据精度， 传感器网络在部署中，多数会采用高密度的部署方式4 】【2 8 】，造成网络的高度冗余 性。高密度的部署方式使得网络中节点间距离较小，造成它们的感知范围有较大 范围的重叠，所采集的数据有高度的相似性和冗余性，冗余的数据包在网络中传 输，将会引起冲突和不必要的传输能耗【4 4 】。对于能量受限的传感器网络，节能是 最重要的。高度冗余的网络中，存在大量冗余节点，如何利用网络部署的冗余性， 在保持网络一定的冗余度以提高网络健壮性和容错性的同时，提高节点能量利用 率，延长网络生存期，是传感器网络研究的热点问题之一。 在传感器网络相关协议设计中，必须考虑传感器网络的特点，以充分利用节 第一章绪论 点能量，提高网络性能。 1 2 无线传感器网络关键技术 构成传感器网络的节点与传统网络中节点的巨大差异，使得传统网络中的 o s i 七层协议对传感器网络不再适用。目前传感器网络协议架构还没有统一的标 准，文献中使用较为广泛的是类似o s i 七层协议的分层协议架构，如图1 3 所示， 该架构包括：物理层、数据链路层、网络层、传输层和应用层【1 2 】【2 8 1 ，其中物理 层、数据链路层和网络层是传感器网络中节点通信需要遵守的协议，传输层则定 义了传感器网络与其他网络互联的接口和标准等问题，应用层则需考虑用户具体 的应用需求。 应用层 o 传输层 0 网络层 n 数据链路层 0 物理层 图1 3 传感器网络分层协议架构 降低能耗、节省能量贯穿于各层协议设计，下面对各层的关键技术和研究现 状进行简单介绍。 ( 1 ) 物理层通信协议的研究集中在传输介质和传输频段的选择、信号的调 制方式和数据收发器的设计等方面【1 2 】。无线电是目前传感器网络使用最多的传输 介质，传统的红外线传输技术也可用于传感器网络【7 】【1 2 1 。针对传感器网络能量受 限的特点，物理层研究的核心问题仍是节省能量，主要的节能技术是采用合理的 调制方式及降低输出功率1 4 5 1 。当传输数据减少时，降低调制等级和传输速度也可 以有效地降低传感器节点的能耗【4 引。 ( 2 ) 数据链路层要保证物理层数据传输的正确性，该层协议的研究主要集 4 第一章绪论 中在m a c 协议。m a c 协议主要负责解决媒体访问、控制并分配无线信道的使 用、减少节点通信冲突，实现通信资源的公平有效的共享【7 儿3 6 】。目前关于m a c 协议已有大量研究，其核心问题是节省节点能量。m a c 协议可以分为【3 6 】【3 7 1 ：确 定性分配的m a c 协议，例如基于t d m a 的m a c 协谢3 6 】；基于随机竞争的m a c 协议，例如i e e e8 0 2 1 l 协议【4 7 1 。 ( 3 ) 网络层是传感器网络多层协议体系结构中研究的热点，通过调用合理 的路由协议，建立能量有效的路径，使得数据顺利地由数据源通过一跳或者多跳 的方式到达数据汇聚点。传感器网络中的路由协议需要考虑的问题包括：传感器 节点采集的原始数据往往有大量冗余；传感器节点的路由是以数据为中心的，节 点按照数据属性寻址【4 0 】【4 1 】：节点的数据处理能力、存储能力和通信能力有限。 基于这些特点，适用于传统的无线网络的路由协议对传感器网络都不再适用，必 须为传感器网络设计新的路由协议。数据融合【4 0 】【4 1 】【4 6 】是传感器网络路由使用的 一种节能技术，考虑到原始数据的冗余性和区域相关性，中间节点不是简单的转 发接收到的数据，而是对数据进行融合，去除冗余数据，仅转发有用的信息，从 而降低通讯能耗，提高能量利用率。 路由协议可分为基于位置的路由协议、平面型的路由协议【3 】【4 8 】和基于层次的 路由协议。基于位置的路由协议假定网络中的每个节点在发送数据前都知道自己 的地理位置和目标节点或邻居节点的地理位置【3 】【4 9 1 ，节点位置信息的精度直接影 响基于位置的路由协议的性能。平面型的路由协议中，网络中所有节点地位平等， 节点协调合作，完成数据的采集和传输任务【4 9 1 。平面型的路由协议大多是基于洪 泛法【3 1 ，其通讯代价和开销比较大【4 8 1 。定向扩散【4 0 】是一种典型的以数据为中心的 平面式的路由协议。 基于分簇 3 1 】【3 8 】【5 2 】、基于树的路由协议【1 3 】【5 0 1 5 1 】和基于链【4 6 】1 5 3 】的路由协议是层 次化的路由协议中最常见的三种。 o 普通节点 簇头节点 图1 4l e a c h 协议形成的分簇结构 l e a c h 协议【5 2 1 是第一个基于分簇的路由通信协议，也是层次化协议的典型 第一章绪论 代表。在l e a c h 中，节点被组织为多个簇，每个簇有一个特殊节点作为簇头。 如图1 4 所示。簇头负责收集簇内成员发送的数据，对数据进行融合并将融合后 的结果发送给数据汇聚点。簇头的选举和簇的划分是分簇协议的重点。 分簇协议中，节点的能耗与节点所处的层次有关，如l e a c h 协议中，簇内 普通节点能耗来自于数据感知和数据发送，簇头节点的能耗则包括数据感知、数 据收集和数据发送三部分，与簇内普通节点相比，簇头节点能耗较高。为延长网 络生存期，分簇协议应保持网络中节点负载平衡，避免簇头节点因能量耗尽成为 失效节点 3 1 3 1 。 移一 节点 基站 图1 5 基于树的路由协议 基于树的分层路由协议可以视为是多路径多跳路由的特殊方式，如图1 5 所 示，节点被组织成一棵以汇聚节点为根的树，叶子节点将数据采集的结果发送给 父节点，内部节点收集孩子节点采集的数据，与其感知结果融合后，发送给父节 点，如此逐层传输，将数据发送给基站。基于树的分层路由中，节点的能耗与其 孩子节点的个数有关，与分簇的路由协议类似，负载平衡是基于树的路由协议必 须解决的问题【5 l 】。 节点 节点 站 图1 6p e g a s i s 中的链式路由 p e g a s i s i 4 6 】是基于链结构的路由协议的典型代表，如图1 6 所示，p e g a s i s 将网络中所有节点组织成一条链，节点与临近节点通信，对其感知结果与收到的 6 第一章绪论 数据进行融合，并将融合后的数据传送给链中的下一跳节点；链中节点通过一个 令牌轮流与基站通信。 此外，同构的传感器网络与异构的网络中，路由协议设计有较大区别。同构 网络中，网络中所有节点都有相同的处理能力、通讯能力、数据采集能力以及初 始能量，节点的特殊性取决于节点部署的位置。为实现同构网络中期望的网络生 存期，必须避免出现过热节点或过度使用处于网络中特殊区域的节点，例如，在 数据传输时，要避免在多次传输中使用同一个或多个中间节点1 5 3 】。异构网络中， 部分节点在处理能力、通讯能力、数据采集能力或初始能量的一个或多个方面比 其他节点更强 s o i l 5 4 j ，在网络协议设计中，应充分利用能力更强的节点，优化网 络性能。异构网络结构比较适用于基于层次的路由协议【5 4 1 。 ( 4 ) 传输层协议需要解决传感器网络与其他网络互联时的问题【l 引。该层协 议设计必须考虑网络互联时，传感器网络资源受限、高度动态性和以数据为中心 的特点带来的问题，保证网络互联的安全性等【5 5 】【5 6 】。 ( 5 ) 应用层协议的设计与具体的应用需求相关，网络覆盖【5 7 】f 5 8 】 5 9 】、网络连 通性1 4 2 】【4 3 】【6 0 】、节点保护【5 9 】【6 1 1 以及网络生存期 6 2 】【6 3 】【删是应用需求最为广泛关注的 几个方面。网络覆盖衡量了网络对感兴趣的数据的采集和处理能力f 5 引，网络连通 保证了数据源到数据汇聚点的通路【5 9 1 ，节点保护反映出网络对传感器节点本身的 覆盖能力【6 。这些应用需求并不是孤立的，网络覆盖、网络连通和节点保护都与 网络生存期有密切关系4 3 1 1 5 8 1 6 0 】；在传感器节点的通讯半径大于二倍的传感半径 时，网络的区域覆盖蕴含网络连通【4 3 】，而节点保护又可视为对网络中孤立点的覆 盖，三者可统一为网络的覆盖问题。 总的说来，能量问题是无线传感器网络通信协议各层的核心问题。要满足期 望的网络生存期，仅靠单层的协议设计和优化是不行的，传感器网络应考虑采用 自适应的跨层协议优化【6 5 】【6 6 1 ，在节点能量受限的情况下，各层相互协作，满足 实际应用对网络高吞吐量、低延迟的要求【6 5 1 。节点休眠调度策略作用于m a c 层 和路由层之间的中间协议，是典型的跨层协议优化机制；其基本思想为：利用实 际网络部署中节点的高度冗余性，提出基于应用需求的节点冗余性判定机制，通 过关闭网络中的冗余节点，保持部分节点活跃以满足应用需求，从而提高网络中 能量的利用率，有效延长网络生存期。节点休眠调度策略应具有较好的普通性， 以适应不同的m a c 协议和路由协议。 需要指出的是，各层协议设计还应满足传感器网络的高可靠性和安全性要 求，用网络的可靠性保证系统的鲁棒性和较长的网络生存期，用安全性保证数据 采集的精度和可信度。传感器网络在部署时，常以较高的节点密度部署，用网络 的高度冗余性换取系统的高可靠性和安全性f 4 4 j ；基于延长网络生存期的设计目 7 第一章绪论 的，节点休眠调度策略会关闭网络中的冗余节点，这将导致网络的可靠性和安全 性降低。如何保持网络处于一定的冗余状态，达到网络生存期和网络可靠性的折 中，是节点休眠调度策略设计的难点之一。 1 3 本文研究内容和研究思路 本文基于i e e e8 0 2 1 1m a c 协议，针对如何在满足应用需求的同时，提高网 络生存期，开展了以下研究工作： ( 1 ) 兼顾网络覆盖、网络连通和节点保护的节点休眠调度策略 传感器网络的高度动态性使得网络的可靠性和安全性受到影响，为节点提供 保护，可以在一定程度上提高网络的健壮性。节点保护即对传感器节点所在位置 提供覆盖，可视为对网络中的孤立点提供覆盖：在缺少节点保护的网络中，仅仅 破坏网络中的部分节点就可以造成网络因为不满足区域覆盖或网络连通而不能 正常运行。 针对目前缺少兼顾网络区域覆盖、网络连通和节点保护的节点调度策略，提 出一种基于分布式节点冗余性判定机制的节点休眠调度策略- e c n s 算法。 e c n s 中，节点通过局部通讯获取局部拓扑信息，计算邻居节点与其感知范围的 重叠区域，利用其感知边界的覆盖度判定感知范围的覆盖度，进而判定节点的冗 余性；e c n s 对冗余节点进行调度，通过设置一个随机的能量相关的休眠计时器， e c n s 关闭部分冗余性为真的节点，保持其余节点处于活跃状态，感知并传输数 据。通过关闭冗余节点，e c n s 可以在满足网络覆盖、连通以及节点自我保护的 同时，有效的延长网络生存期。e c n s 可以有效地平衡网络中节点的负载和能耗， 具有分布式的实现方式和低通讯代价及低计算复杂度。通过与分簇式的路由协议 l e a c h 柏结合，对e c n s 的性能进行了评估，仿真实验表明，与未使用e c n s 的l e a c h 协议相比，e c n s 有效地降低了节点能耗，延长了网络生存期。 ( 2 ) 多目标集连续监控的节点休眠调度策略 目标监控是传感器网络常见的应用场景，环境监控、入侵检测、远程医疗等 诸多应用都可以描述为对特定目标的监控问题。 针对多孤立目标连续监控的传感器网络，本文提出一种分布式的节点休眠调 度策略c t m n s 算法，以提高该类网络的节点能量利用率，延长网络生存期。 该算法可以对多个孤立目标提供连续监控，并为不同的目标提供不同的期望覆盖 度。c t m n s 激活尽可能少的节点满足目标监控的覆盖度需求，最大限度地让节 点处于休眠状态。在c t m n s 中，每个传感器节点都关联一个与节点分布和剩余 能量相关的权值，节点可以独立地计算其关联权值的大小，并通过局部通信计算 8 第一章绪论 权值的排序，依据节点冗余性判定机制，利用权值排序结果，节点可以独立判定 其冗余性，冗余性为真的节点关闭其电源，其余节点进一步利用c t m n s 决定是 否保持活跃，以满足对目标的监控需求。仿真结果表明，c t m n s 可将对目标 的有效监控时间提高到无节点休眠调度策略的目标监控算法的2 7 倍。 1 4 本文的组织结构 本文分为五章，各章节的内容安排如下： 第一章是绪论，首先介绍无线传感器网络的系统结构和网络特点，其次对无 线传感器网络研究中的关键技术和研究现状进行简单介绍，最后给出本论文的研 究内容和组织结构。 第二章首先对节点休眠调度机制的设计难点进行了简单分析和讨论：其次， 分类介绍当前节点休眠调度策略的研究现状；最后介绍本文使用的传感器节点传 输能耗模型。 第三章首先简单介绍网络系统假设和相关定义；接着详细介绍了兼顾网络区 域覆盖、网络连通和节点保护的节点调度策略的设计核一t l , 及其实现步骤，然后讨 论了算法的性能，最后给出仿真实验，验证该策略在节省节点能耗、延长网络生 存期方面的有效性。 第四章首先介绍基于孤立目标连续监控的休眠调度策略的研究意义，然后给 出形式化的问题描述、网络模型和假设条件，其次详细介绍该策略的设计思想和 实现步骤，最后给出仿真结果，评估算法对网络性能的提高。 第五章对全文进行总结，并展望下一步的研究工作。 9 第二章传感器网络节点休眠调度机制的相关i t 作 第二章传感器网络节点休眠调度机制的相关工作 传感器网络与传统网络的最大区别在于构成网络的节点能量严重受限，能维 持的工作时间较短，能量无法得到及时补给，难以满足网络长期稳定运行的应用 需求。为提高网络的健壮性和可靠性，在实际应用中，传感器网络在部署时多会 采取高密度高冗余的部署方式，尤其是针对军事监控、环境监测等应用部署的网 络。 高密度的部署方式使得传感器节点采集的原始数据有较高的区域相关性和 冗余性，导致距离较近的多个数据源产生的数据包同时在网络中传输，引起网络 拥塞和传输冲突；数据汇聚点在接收到距离较近的节点发来的数据包时，也会因 为内容的重复将其丢弃。由此可见，高密度部署的传感器网络中存在大量的能量 浪费，数据融合可通过降低网络中数据包的冗余性，有效提高节点能量利用率， 具体做法为：在数据收集的过程中，中间节点不是简单的转发该数据包，而是对 数据做简单的处理，去除冗余性数据，保存有用信息，从而缩短数据包的长度， 进而降低数据通讯的能耗。 一种更有效更直接的方式是仅仅保持部分节点活跃以捕捉用户感兴趣的数 据，其余节点处于休眠状态，这样由于活跃节点分布相对比较分散。即使不进行 数据融合，也不会有冗余数据到达汇聚节点。活跃节点和休眠节点轮流执行数据 感知和传输任务，可减少网络中传输的数据包，避免网络拥塞，降低通信开销， 从而有效地延长网络生存期。采用该方式的节点休眠调度机制，基于不同的应用 需求设计相应的节点冗余性判定规则，根据冗余性判定结果对节点进行休眠调 度，是可行性较高的延长系统生存期的网络管理策略。 本章首先对节点休眠调度策略的设计难点进行简单讨论，其次介绍传感器网 络的节点休眠调度策略的相关研究工作，接下来介绍节点休眠调度策略中使用的 能量模型，最后给出本章小结。 2 1 节点休眠调度策略的设计难点 考虑到传感器节点资源受限，尤其是能量受限的特点，实际应用中，节点休 眠调度策略应该具备以下特性： ( 1 ) 分布式的实现方式，即网络中的节点可以完全独立地或者仅通过与邻 近节点的局部通信，决定其休眠调度；与集中式的策略相比，分布式的调度策略 更易于实现【2 】，对网络部署密度变化有较好的适应性和可扩展性【4 1 ； 1 0 第二章传感器网络：审点休眠调度机制的相关工作 ( 2 ) 低开销，节点休眠调度策略给节点带来的额外的通信代价和计算代价 必须足够低，尽可能减少节点的能耗； ( 3 ) 完整性，即节点休眠调度策略所激活的节点应该足够满足应用需求【4 1 。 对传感器网络在军事安全、目标监控、环境监测等领域的应用加以分析，可 将应用需求概括为：网络覆盖度、网络连通性和节点保护。 2 1 1 传感器网络中的覆盖问题 传感器网络典型的应用包括目标监控、目标跟踪、查询处理等，这些应用中 最基本的问题是对网络中区域或孤立点的覆盖问题。网络覆盖是评测传感器网络 服务质量( q o s ) 的一项重要指标，它衡量网络的容错能力，以及网络是否具备 捕捉满足实际应用精度和准确度要求的数据的能力1 5 儿5 8 】。 网络覆盖可以分为部分覆盖和全覆盖。部分覆盖相对比较松散，它可以是空 间上的部分覆盖，即仅对网络区域的离散点或部分连续子区域提供满足应用需求 的覆盖，比如对查询应用中，对查询命令指明的子区域提供覆盖：部分覆盖也可 以是时间上的，即不需要对监控区域或离散点保持连续监控，只要在用户指定的 时间段或部分时问内对其提供覆盖即可【6 7 】，时间上部分覆盖的应用包括查询类应 用【5 8 】或者对数据的精确度要求不高的应用。部分覆盖也可以是时问和空间的部分 覆盖，例如对监控目标提供时间上的部分覆盖【6 。7 1 。全覆盖，指网络部署区域中的 每点都处于至少个传感器节点的感知范围内。 一种较直观的可衡量网络覆盖质量的标准是网络覆盖度，覆盖度为k ( k 1 1 的 网络，或称k 覆盖( k 1 ) 的网络，指待监控区域中的每一点或每个待监控的孤立 点都能被至少k ( k 1 1 个节点感知f 4 3 】f 5 7 】f 5 9 1 。k 2 的网络覆盖不仅可以提高数据 精度，保证监控质量，还可以增强系统的容错性【4 3 j 【57 1 。不同的应用需求要求网 络对监控区域提供不同的覆盖度。对监控质量要求较高的应用往往需要网络系统 提供k 2 的覆盖度，例如，军事安全、交通监控等。网络的覆盖度要求可能会 因应用模式的改变或环境变化而变化，例如，为入侵检测部署的网络，在发现入 侵者之前，需要提供较低的覆盖度，而在监测到入侵者后，网络需要提供的覆盖 度随之增高，以更精确地定位和跟踪入侵者【4 3 】，因此，节点体眠调度策略应具有 一定的灵活性，以根据应用需求的变化，对监控区域提供可变的网络覆盖度。 在目标检测和跟踪类应用中，例如，军事监控中的入侵检测，监控目标会沿 着传感器部署区域中的某条路径移动，并尽量远离传感器节点，避免暴露。为评 估传感器网络对监控目标进行检测和跟踪的能力，衡量该类网络的覆盖质量， m e g e r i a n 等人提出了与覆盖度完全不同的衡量标准：w o r s t c a s ec o v e r a g e 和 b e s t c a s ec o v e r a g e 【6 8 1 。 第二章传感器网络节点休眠调度机制的相关工作 与覆盖度的评价标准相比，w o r s t c a s ec o v e r a g e 和b e s t c a s ec o v e r a g e 可以 更有效地评估和量化传感器网络发现目标、跟踪目标的有效性，其具体定义为1 6 8 j ： 对网络中的路径p ，定义路径p 的b r e a c h 值为路径上所有点到网络中传感器节 点的最小距离，使得该距离最大的路径称为网络中的m a x i m a lb r e a c h 路径，对 应的b r e a c h 值则为网络的w o r s t - c a s ec o v e r a g e ；相对应的，定义尸的s u p p o r t 值为路径上所有点到网络中传感器节点的最大距离，使得该距离最小的路径则称 为m a x i m a ls u p p o r t 路径，对应的s u p p o r t 值为网络的b e s t c a s ec o v e r a g e 。目标 在沿着网络中的m a x i m a lb r e a c h 路径移动时，在某一点，到达网络中节点的最 小距离会达到一个最大值，而在沿着m a x i m a ls u p p o r t 路径移动时，会在某一位 置，与网络中所有节点的最大距离达到最小值。 m e g e r i a n 等人进一步提出了w o r s t c a s ec o v e r a g e 和b e s t c a s ec o v e r a g e 的近 似最优时间复杂度的计算方法1 6 8 1 ：通过构造网络对应的v o r o n o i 图和d e l a u n a y 三角，利用贪心策略，求解网络中的m a x i m a lb r e a c h 路径和m a x i m a ls u p p o r t 路 径，进而求得w o r s t c a s ec o v e r a g e 和b e s t c a s ec o v e r a g e 。在评估传感器网络对 目标的检测和跟踪能力时，w o r s t c a s ec o v e r a g e 和b e s t c a s ec o v e r a g e 值越小， 目标在网络中移动时，被节点感知到的概率越高。在网络部署时，基于网络的 w o r s t c a s ec o v e r a g e