（计算机应用技术专业论文）无线传感器网络中近似窗口查询技术的研究.pdf

东北大学硕士学位论文摘要 无线传感器网络中近似窗口查询技术的研究 摘要 随着传感技术、通信技术和计算机技术的飞速发展以及微型机电系统的日益成熟与 ，完善，无线传感器网络已广泛应用到许多领域。然而，大多数无线传感器的应用受到能 量有限性的限制。窗口查询是无线传感器网络中一种典型的空间查询，要求返回指定地 理区域内传感器节点的感知数据。不断地检测查询窗口内的数据变化情况需要消耗大量 的能量。基于此，重点研究了窗口内数据的近似查询技术，提出了能量有效的近似窗口 查询技术。 回顾了无线传感器网络中已有的窗口查询技术，分析了无线传感器网络中窗口查询 和连续查询的特点，给出了近似窗口查询的形式化定义。近似窗口查询的处理过程可分 为三个阶段：寻找从查询发出者到查询窗口之间的路径；查询窗口内查询的处理；查询 结果的返回。针对不同的阶段提出相应的解决方法，第一、三阶段采用地理路由协议 ( g p s 鼬，第二阶段为核心阶段。提出了基于全连通簇划分的方法c a w e ( c l i q u e - b a s e d a p p r o x i m a t ew i n d o wq u e r ye x e c u t i o n ) 。在c a w e 中，先将查询窗口内的传感器节点划 分成基于感知数据的全连通簇，为节省能耗，查询执行时只有每个全连通簇的代表节点 在工作。该方法的优点在于，每个全连通簇中的节点可以轮换做代表，使得传感器节点 能量消耗均衡，采用三色方法将查询窗口内全连通簇之间路径的建立和全连通簇代表节 点的选取合并为一个过程，可以大大减少能耗。 实验和分析证明，本文提出的基于全连通簇划分的方法c a w e 在完成近似窗口查 询的同时，能够尽可能地减少无线传感器网络节点的能量消耗，延长网络的生命周期。 关键词：无线传感器网络；窗口查询；查询窗口；全连通簇；代表节点 一i i 东北大学硕士学位论文a b s t r a c t s t u d yo na p p r o x i m a t ew i n d o wq u e r yt e c h n i q u e s i nw 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 w i r e l e s ss a l s o rn e t w o r kt e c h n i q u e sh a v eb e e np r o m o t e db yt h ed e v e l o p m e n to fs e l l s o r t e c h n i q u e ，w i r e l e s sc o m m u n i c a t i o nt e c h n i q u e ，m i c r oe l e c t r o n i ct e c h n o l o g ya n di n c r e a s i n g m a t u r i t yo fm i c r oe l e c t r o n i cm e c h a n i s ms y s t e m w s nh a sb e e ns u c c e s s f u l l yu s e di nv a r i o u s a p p l i c a t i o na r e a sa n di th a sab r i g h tf u t u r ef o ri t se x t e n s i v eu s e h o w e v e lm o s ta p p l i c a t i o n so f w i r e l e s ss e n s o rn e t w o r k sa r el a r g e l yl i m i t e db yf m i t eb a r e r ye n e r g y w i n d o wq u e r yi sa t y p i c a ls p a t i a lq u e r y , w h i c hr e q u e s t st h a tw i r e l e s ss e n s o rn e t w o r k sm u s tr e t u r ns e n s o rd a t ai n t h es p e c i a ls e n s o rf i e l d i nw i r e l e s ss e n s o rn e t w o r k s ，b e c a u s eo fc o n t i n u a ld e t e c t i n gt h ed a t a a n dt r a n s m i t t i n gg r e a ta m o u n to fd a t a , i ti sn e c e s s a r yt oc o s tt o om u c he n e r g y b a s e do nt h i s c o n s i d e r a t i o n , t h ep r o c e s s i n gt e c h n i q u ef o ra p p r o x i m a t eq u e r i e si nq u e r yw i n d o wi ss t u d i e d a n de n e r g ye f f i c i e n tp r o c e s s i n gt e c h n i q u e sa r ep r o p o s e d t h ee x i s t i n gp r o c e s s i n g t e c h n i q u e so fw i n d o wq u e r i e sa r er e v i e w e d t h ef e a t u r e so f w i n d o wq u e r i e sa sw e l la sc o n t i n u o u sq u e r yi nw i r e l e s ss e u s o rn e t w o r k sa r ea n a l y z e d t h e n a p p r o x i m a t ew i n d o wq u e r i e sa r ef o r m a l l yd e f i n e d t h ep r o c e s s i n go fa p p r o x i m a t ew i n d o w q u e r yc a l lb ed i v i d e di n t ot h r e em a i np h a s e s ：r o u t i n gt h eq u e r yf r o mt h eq u e r yo r i g i n a t o r n o d et oq u e r yw i n d o w , p r o c e s s i n gt h eq u e r yi nt h eq u e r yw i n d o w , a n d r e t u r n i n gt h eq u e r y r e s u l t s e a c hp h a s ei si n v e s t i g a t e di nt h i st h e s i sa n dc o r r e s p o n d i n gs o l u t i o ni sp r o p o s e d i nt h e f i r s tp h a s ea n dt h et l l i r dp h a s e 。g p s ri s a d o p t e dt od i s c o v e rt h ep a t ha st h es f m e 嬲t h e p r e v i o u sa p p r o a c h e s i nt h es e c o n dp h a s e ，c a w e ( c l i q u e b a s e da p p r o x i m a t ew i n d o wq u e r y e x e c u t i o n ) i sp r o p o s e d i nc a w e ，a l ls e n s o rn o d e si nq u e r yw i n d o wa r ep a r t i t i o n e di n t o s o m ec l i q u e sa n das m a l ln u m b e ro fn o d e s ，w h i c ha r et h er e p r e s e n t a t i v en o d e so fc l i q u e sa r e v i s i t e dt oa n s w e rt h eq u e r i e s s e n s o rn o d e so fe v e r yc l i q u ea r ea l t e r n a t et ob et h e r e p r e s e n t a t i v en o d e st ob a l a n c et h ee n e r g yc o n s u m p t i o n t h r e ec o l o r sa l g o r i t h mi su s e dt o d i s c o v e rr o u t i n gb e t w e e nc l i q u e s ，i nw h i c hd i s c o v e r i n gt h es h o r t e s tp a t h sa m o n g c l i q u e sa n d c h o o s i n gt h er e p r e s e n t a t i v en o d e so f c l i q u e sa r ec o m b i n e di n t oo n es i n g l es t a g e e x t e n s i v ee x p e r i m e n t ss h o wt h a tt h ep r o p o s e dc a w ec a nr e d u c ee n e r g yc o n s u m p t i o n a n dl e n g t h e nl i f e t i m ea sl o n ga sp o s s i b l ew h i l ea p p r o x i m a t ew i n d o wq u e r i e sa r ep r o c e s s e d 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 ；w i n d o wq u e r y ；q u e r yw i n d o w ；c l i q u e i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位敝储签名：阂磊绎 签字日期：妒p 码 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名： 签字日期： 同斜 嗣一一j 3 j 导师签名：杨腹刍 签字日期。川o i 2 j 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早三有t 匕 随着传感技术、微系统技术、数字电路、无线通信的飞速发展，无线传感器网络技 术己在许多应用领域获得越来越广泛和深入的应用，如军事、医疗、环境、交通等。然 而，由于无线传感器网络一般布置在一些难以到达的区域进行环境监测，并且大部分的 传感器设备都是由电池供电，监测环境的特殊性使得给其更换电源是不太现实的，这使 得无线传感器的应用受到了很大的限制。在连续窗目查询的执行中，数据的传输是最消 耗能量的，为了减少能量的消耗，必须尽可能地减少数据的传输量。 1 1 研究背景 无线传感器网络是由大量静止或移动的传感器节点以自组织和多路的方式构成的 无线网络，其目的是协作地感知、采集、处理、传输网络覆盖地理区域内感知对象地检 测信息，报告给观察者“埘。传感器、感知对象和观察者是传感器网络的3 个基本要素。 图1 1 为传感器网络的体系结构，这种网络通常由传感器节点( s e n s o rn o d e ) 、接收发送 器( s i n k ) 、i n t e m e t 或通信卫星、任务管理节点等构成1 3 l 。 u s c r 图1 1 无线传感器网络的体系结构 f i g 1 1a r c h i t e c t u r eo f w i r e l e s s n $ o rn e w , w o r k 随着数字电路、无线通信等技术的发展，无线传感器网络技术已在许多应用领域获 得越来越广泛和深入的应用，如军事、医疗、建筑、环境等。在军事方面，由于传感器 节点可以散布于恶劣的环境，因而战场上可以利用传感器网络监控敌、我军兵力、装备 和物资，监视冲突区，侦察敌方地形和布防，定位攻击目标，评估损失，侦察和探测核、生 物和化学攻击。传感器网络已经成为军事c 4 i s r t ( c o m m a n d ，c o n t r o l ，c o m m u n i c a t i o n , c o m p u t i n g ，i n t e l l i g e n c e ，s u r v e i l l a n c e ，r e c o n n a i s s a n c ea n dt a r g e t i n g ) 系统必不可少的一部 分【4 】。在建筑方面，传感器网络用来监控建筑物的安全状态。在c i t r i s ( c e n t e ro f 一1 一 东北大学硕士学位论文第一章绪论 i n f o r m a t i o n t e c h n o l o g y r e s e a r c h i n t h e i n t e r e s t o f s o c i e t y ) 计划中，美国加州大学伯克利 分校的环境工程和计算机科学家们采用传感器网络，让大楼、桥梁和其他建筑物能够自 身感觉并意识到它们本身的状况，并自动按照优先级把信息传到相关部门，从而可以让 人们方便的了解到建筑物的安全情况。在环保方面，随着人们对于环境的日益关注，环 境科学所涉及的范围越来越广泛，主要包括跟踪候鸟和昆虫的迁移，分析环境变化对农 作物的影响，监测海洋、大气和土壤的成分等。还可以用于行星探测、气象和地理研究、 洪水监测等【5 1 。传感器节点随机密布在森林之中，监测森林环境。传感器网络也可以应 用在精细农业中，以监测农作物中的害虫、土壤的酸碱度和施肥状况等。在大洋海岸分 布一些传感器，专家们就可以根据传感器节点感知的数据及时地分析海岸的情况，减少 海啸造成的人员伤亡和财产损失。此外，在动物栖息地、灾难拯救、医疗系统、仓库管 理、交互式博物馆、交互式玩具、城市车辆监测和跟踪系统【印】等众多领域，无线传感器 网络都孕育出全新的设计和应用模式。 无线传感器网络是以数据为中心的网络，无线传感器网络所有应用也都是以数据为 中心的。在无线传感器网络中，用户感兴趣的是传感器产生的数据，而不是传感器本身， 并且用户使用传感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给 某个确定的传感器节点。网络在获得指定事件的信息后汇报给用户。如用户不会提出这 样的查询：“从4 节点到嚣节点的连接是如何实现的? ”，他们经常会提出如下的查询； “网络覆盖区域中哪些地区出现毒气? ”。由于传感器节点不需要地址之类的标识。观察 者不会提出查询：“地址为2 7 的传感器的温度是多少? ”，他们感兴趣的查询是，“某个 她理位置的湿度是多少? ”。 传感器节点的感知数据一般具有时间关联性和空间关联性【8 。时间关联是指节点在 当前时刻和下一时刻的数据值存在着定量的函数关系。通常，传感器节点感知的数据的 时间关联性与其所在感知区域的物理条件有关，物理条件所具备的时间连续性使得传感 器节点在连续采样观测中所感知到的数据具有一定的时间关联性。空间关联是指一定空 间范围内的节点的数据值之间存在着定量的函数关系。在无线传感器网络的应用中，一 般多个传感器节点就会共同地感知某个事件的发生。由于网络拓扑中节点的分布密度很 高，空间位置上接近的节点所感知的数据就会具备一定的相关性，这种相关性会随着中 间间隔节点个数的增加、节点间距离的增加而降低。 然而，传感器网络的应用却由于其自身特点受到很大的限制，传感器节点的电源能 量、存储计算能力、存储能力及传感器网络的带宽都十分有限，尤其是电源能量的影响， 一2 一 东北大学硕士学位论文第一章绪论 成为无线传感器网络发展的瓶颈。在传感器网络中，在每个传感器节点上执行多种操作： 感知数据、查询、计算、通信、传输数据等等。其中，传输信息消耗的能量比普通的本 地操作更耗费能量，无线传感器传输1 位信息所需要的能量足以执行3 0 0 0 条计算指令1 2 j 。 因此，如何有效的利用传感器网络的电能，提高能量的使用效率，是无线传感器网络方 向研究的巨大挑战。很多专家人士致力于这方面的研究，提出了很多能量有效的网络路 由协议【l o - 2 3 1 、数据查询处理方法 2 4 - 3 4 】和数据收集技术【3 5 1 。 无线传感器网络的主要具有以下特点； ( 1 ) 资源有限性。无线传感器网络中的传感器节点一般都是由电池供电，而传感器 节点的生命期要求比较长，所以能效问题是传感器网络的核心问题，传感器网络中的任 何技术和算法都要以能效为前提。除此之外，传感器节点的计算能力、存储能力都十分 有限，相对普通的计算机来说非常的弱，这就决定了在节点的操作系统设计中，协议和 有关算法也都要相对的精简。 ( 2 ) 自组织性。传感器节点通过分级协议和分布式算法协调自己的行为，自动的组 织成一个独立的网络。但由于传感器节点的通信能力有限，通信范围一般为几十到几百 米，那么远距离的节点之间通信需要中间节点进行路由，所以无线传感器网络是一个多 跳的自组织网络。并且网络中的所有节点都是平等的。 ( 3 ) 网络动态性。无线传感器网络具有一定的动态性，网络中的传感器、感知对象 和观察者这三要素都可能具有移动性，并且经常有新节点加入或己有节点失效，因此， 网络的拓扑结构会经常动态变化，传感器、感知对象和观察者三者之间的路径也随之变 化，这就要求传感器网络系统要能够适应这种变化，具有动态的系统可重构性。 ( 4 ) 大规模性。为了获取精确信息，在检测区域通常部署大量传感器加节点，传感 器节点数量可能达到成千上万，甚至更多。传感器网络的大规模性存在两种情况：一种 是高密度分布，传感器节点部署很密集，在一个面积不是很大的空间内，密集部署了大 量的传感器节点；另一种是低密度分布，传感器节点分布在很大的地理区域内，如在原 始大森林采用传感器网络进行森林防火和环境检测，需要部署大量的传感器节点。 1 2 问题的提出 查询是用户获得传感器网络数据的重要途径，通过查询和分析网络中的感知数据可 以检测感知区域内环境的变化情况。无线传感器网络数据的查询方式主要有历史查询、 快照查询和连续查询等。用户可以根据自己的需求采用不同的查询方式来获得感兴趣的 3 东北大学硕士学位论文 第一章绪论 数据信息。 从无线传感器网路的应用来看，无线传感器网络一般覆盖的感知区域的范围比较广 阔，但查询用户有时并不关心整个感知区域的数据，他们感兴趣的是感知区域内某一具 体地理范围内的数据情况，如图1 2 所示，区域4 和区域b 为整个感知区域中两个具体 的地理区域，若用户想查询它们的物理属性，则会有这样的查询“区域a 内的平均湿度 是多少? ”、“区域曰内的最高温度是多少? ”等，类似这样的查询称为窗口查询。窗口 查询是无线传感器网络中一种比较典型的空间查询，要求返回指定地理区域内传感器节 点的感知数据。窗口查询在传感器网络的应用中具有非常重要的作用。 图1 2 窗口查询 f i g 1 2w i n d o wq u e r i e s 窗1 3 查询分为两种：快照窗口查询和连续窗口查询。快照窗口查询是对查询窗口在 某一给定时间点的查询，例如：“列出区域4 当前的空气压强值”。连续窗口查询关注在 某一段时间间隔内查询窗口内传感器网络数据的变化情况，例如：“每1 0 秒检测一次区 域x 内的平均压强是多少，持续3 个月”。对于这种连续窗口查询，由于要不断地检测 查询窗口内的数据变化情况，如果要把所有的数据都传给用户，需要消耗很多的能量， 因为对于传感器节点来说，传输数据是最消耗能量的，所以对于对查询精度要求不高的 用户来说，他们希望牺牲查询结果的精度来换取网络生命周期的延长以达到对环境的长 期监控，他们会给出查询误差，在误差范围内的查询结果都是有意义的，例如：。每分 钟检测一次区域d 内的最高温度是多少，误差为d ，持续6 个月”，这种查询称为近似 窗口查询。 然而，无线传感器网络中连续窗口查询的原始处理需要连续不断的传输数据，非常 消耗能量。并且若采用网络生成结构，又会引发很多查询窗1 3 外的传感器节点参与到查 询处理中来，导致很多不必要的能量消耗。为了减少网络的能量消耗，延长网络的生命 一4 东北大学硕士学位论文第一章绪论 周期，提高网络能量的利用效率，设计能量有效的连续窗口查询的处理技术非常必要。 1 3 本文工作 本文分析了无线传感器网络和连续窗口查询的特点，找出问题的关键，将连续窗口 查询的处理过程分为三个阶段：第一、寻找从查询发出者到查询窗口之间的路径。第二、 查询窗口内查询的处理。第三、查询结果的返回。然后分别针对不同的阶段提出相应的 解决方法，第一、三阶段采用地理路由协议( g p s r 【3 6 1 ) ，第二阶段采用本文提出的基于全 连通簇划分的方法c a w e ( c l i q u e - b a s e da p p r o x i m a t ew m d o wq u e r ye x e c u t i o n ) 。 在c a l e 中，查询窗口内感知数据满足用户给定误差范围d 且在传输范围r 内的 传感器节点划分为一个全连通簇，同一个全连通簇内的任意两个传感器节点的感知数据 都满足6 关系，设数据为巧、乃，则l 巧乃1 茎j 。每个全连通簇选择一个代表节点回答 查询。由于同一个全连通簇内的任意两个传感器节点的数据都满足j 关系，全连通簇内 的节点可以轮换做代表，而不需要重新划分全连通簇。从而减少了节点能量消耗和时间 延迟，延长网络的生命周期，提高查询效率。采用三色方法鲫寻找查询窗口内全连通簇 之间的最短路径，根据选择的路由进行查询广播和数据收集。 由于无线传感网络是一种动态网络，其网络拓扑也是动态的，并且随着时间和环境 的变化传感器节点的感知数据可能也会变化，这样可能导致查询窗口内全连通簇的变 化，甚至导致路由的变化，为了提高c a w e 的健壮性，本文给出了c a w e 的动态维护， 让其更有效的工作。 1 4 本文的组织结构 本文的组织结构如下： 第一章为引言，主要介绍了无线传感器网络的概念、典型体系结构、应用、主要特 点，根据无线传感器的应用特点引出了本文研究的问题，并对本文的主要工作进行了描 述，阐明该研究的现实意义。 第二章为相关工作，首先介绍了无线传感器网络中能量有效的路由策略，包括低功 耗自适应聚类路由算法、定向扩散路由算法、谣传路由算法和基于地理位置信息的路由 算法；然后介绍了能量有效的查询处理技术，包括基于树结构的查询处理技术、基于多 路的查询处理技术、树和多路径相结合的查询处理技术、近似查询处理技术、以及快照 窗口查询的处理技术。其中，近似查询处理技术又包括基于线性模型的查询处理技术和 基于概率模型的查询处理技术，快照窗口查询的处理技术包括基于传感器网络结构的查 一5 一 东北大学硕士学位论文第一章绪论 询处理技术和独立于传感器网络结构的查询处理技术，并讨论了它们的性能及应用于本 文处理闯题中的局限性。 第三章首先对本文关注的问题进行了详细了定义，详细介绍了各种窗口查询的提出 及定义。并根据连续窗口查询的特点和实际应用提出了近似窗口查询，给出了近似窗口 查询形式化定义及其实际意义。详细介绍了本文历提出的近似窗口查询的处理技 c a w e ，介绍了查询窗口内全连通簇的划分，全连通簇中代表节点的选取，全连通簇之 间路由的建立，以及查询的传播和数据收集。 第四章主要介绍了查询窗口内全连通簇和全连通簇之间路由的动态维护。为了使 c a w e 方法有效的工作，本文提出了c a w e 方法的动态维护策略。 第五章通过实验对c a w e 方法进行分析、验证和总结。与基于树结构的查询技术 和基于簇划分的查询技术从不同角度进行了对比，证明了c a w e 方法的合理性和有效 性。 第六章是结论，对本文所做的工作进行了总结，并阐述了进一步的研究内容。 6 一 东北大学硕士学位论文 第二章相关工作 第二章相关工作 为了解决无线传感器网络的能量利用效率问题，很多专家人士提出了很多能量有效 的无线传感器网络路由协议【1 睨3 1 、数据处理技术 2 4 。4 1 和数据收集技术1 3 5 1 。能量有效的近 似窗口查询的处理技术也是为了提高无线传感器网络能量的利用率，尽可能减少传感器 节点的能量消耗，并使每个节点的能量消耗平均，最大限度的延长无线传感器网络的生 命周期。本章重点介绍与本文研究内容相关的无线传感器网络路由协议和数据查询的处 理技术。 一 2 1 无线传感器网络中能量有效的路由策略 在无线传感器网络中，传感器节点的能量资源、计算能力、存储能力和带宽都非常 有限，而且无线传感器网络通常由大量密集的传感器节点构成，这就决定了无线传感器 网络协议的各层设计都必须以能源有效性为首要的设计条件，路由协议的研究已经成为 无线传感器网络研究的热点问题之一。目前，很多专家人士致力于这方面的研究，他们 根据不同的传感器网络的特点，提出了许多新的不同的能量有效的路由协议，然而，这 些路由协议并不完美，仍需要进一步的改进完善。 无线传感器网络是以数据为中心的网络，无线传感器网络中的大量节点是随机部署 的，节点一般不会有全局的唯一标识，并且用户关注的是所检测区域的感知数据，而不 是具体哪个节点获取信息。传感器网络通常包含多个传感器节点到少数汇聚节点的数据 流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发路 径。数据的通信不再依赖特定的节点，而是依赖于网络中的数据，减少了网络中大量传 送的重复冗余数据，降低了不必要的开销，从而延长网络生命周期。 2 1 1 协商路由协议 协商路由协议s p i n ( 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 ) 1 1 , 1 2 系列路由协 议是以数据为中心的自适应路由协议，通过协商机制来解决洪泛算法中的“内爆”和“重 叠”问题 1 3 】。传感器节点仅广播采集数据的描述信息。也即是元数据( m e t a - d a t a ) 。当有相 应的请求时，才有目的地发送数据信息。s p i n 系列路由协议中有3 种用于通信的消息类 型：a d v 、r e q 和d a t a 。传感器节点用a d v 宣布有数据发送，a d v 消息中包含要发送 数据的元数据；当一个传感器节点想要实际的感知数据时，它会发送一个r e q 消息来请 求数据信息；d a t a 消息用于封装数据，d a t a 消息包含真实的感知数据，这些数据由元 一7 一 东北大学硕士学位论文第二章相关工作 数据作为报头。s p i n 系列路由协议有4 种不同的形式： 1 s p i n p p , 采用点到点的通信模式，并假定两节点问的通信不受其他节点的干扰， 分组不会丢失，功率没有任何限制。要发送的数据节点通过a d v 向它的相邻节点广播消 息，感兴趣的节点通过r e q 发送请求，数据源向请求节点发送数据。接收到数据的节 点再向它们的相邻节点广播a d v ，如此重复，使所有节点都有机会接收到任何数据。 2 s p i n e c ：在s p i n - p p 的基础上考虑了节点的功耗，只有能够顺利完成所有任务 且能量不低于设定阈值的节点才可参与数据交换。 3 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 b c 的完善，主要考虑如何恢复无线链路引入的分组差错与 丢失。记录a d v 消息的相关状态，如果在确定时间间隔内接收不到请求数据，则发送重 传请求，重传请求的次数有一定的限制。 s p i n 算法中，每个节点只知道其单跳邻居节点，从而可以使网络的拓扑改变局部 化。s p i n 算法在能量耗损和数据冗余方面要比洪泛算法低3 5 。但是，其数据广播方式 无法保证数据的有效传输。例如，如果希望得到的数据目的节点与拥有数据的源节点距 离较远，丽二者之间的节点对该数据的期望较小，那么，该数据将无法到达目的节点。 所以，s p i n 算法不适用于诸如气象信息搜集等，需要周期性传输可靠数据包的应用。 另一方面，由于该协议中每一个节点只向其单跳节点发送信息，所以s p i n 算法适用于大 型无线网络的路由建立。 2 1 2 低功耗自适应聚类路由算法 低功耗自适应聚类路由算法( 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 ) 【1 4 】 是由m i t 的c h a n d r a k a s a n 等人为无线传感器网络设计的能量有效的路由算法，它是一种 比较典型的层次式路由协议。然而，由于它提出的比较早，方法比较基础，性能上还有 很多不足，所以后来很多研究人员在l e a c h 的基础上，又提出了的一些性能较好的层 次式路由协议。如t e e n ( t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o rn e t w o r kp r o t o c 0 1 ) i 蝤】、 h e e d ( h y b r i d , e n e r g y - e f f i c i e n t , d i s t r i b u t e dc l u s t e r i n ga p p r o a c h ) 1 “、e e c s ( e n e r g ye f f i c i e n t c l u s t e r i n gs c h e m e ) 1 7 等，使之更有效的适用于无线传感器网络。 l e a c h 算法分为两个阶段操作，即簇的初始化阶段( s e t - u pp h a s e ) 和稳定工作阶段 一8 一 东北大学硕士学位论文 第二章相关工作 ( r e a d yp h a s e ) 。为了使能量消耗最少化，稳定工作阶段持续的时间比簇的初始化阶段长。 簇的初始化阶段和稳定工作阶段总共持续的时间称为一“轮”，在此定义了“轮”( r o u n d ) 的概念。在簇初始化阶段，l e a c h 算法随机地选择一个传感器节点做为簇头节点 ( c l u s t e rh e a dn o d e ) ，随机性确保簇头节点与基站之间的高能量消耗平均分配给所有传感 器节点。 在初始化阶段，簇头节点的建立过程如下：节点从0 到l 的随机数中任意选择一个数 值，若当前轮中这个数值小于设定的阀值丁和砂，则该节点成为簇头节点，z p 砂表示如公 式( 2 1 ) 所示。 ，( 功=一k 若刀u 。n - k r m o d ( n k ) 。 ( 2 1 ) 0否则 s i “ 东北大学硕士学位论文 第二章相关工作 l e a c h 路由算法能够保证每个传感器节点等概率地担任簇头，从而使得网络中各 节点能量的消耗相对均衡。与一般的多跳路由协议和静态聚类算法相比，l e a c h 可以 将网络生命周期延长约1 5 。但是l e a c h 假设所有的节点都能直接与簇头节点和终端 节点通讯，采用连续数据发送模式和单跳路径选择模式，如图2 1 所示，因此不适用于需 要监测面积范围大的应用，而且动态分簇带来了拓扑变换和大量广播这样的额外开销， 所以e s t r i n 等人针对大规模的无线传感器网络提出了层次聚类路由协议( h i e r a r c h i c a l c l u s t e r i n gp r o t o c 0 1 ) 1 蜘。 2 1 3 定向扩散路由算法 定向扩散路由算法( d i r e c t o dd i f f u s i o n ) 1 蚣0 】是一种以数据为中心的路由协议。定向扩 散路由算法是以数据为中心的路由协议发展过程的里程碑，其他的以数据为中心的路由 协议基本上都是基于定向扩散改进或者采用类似的关键思想提出的。该算法与已有的路 由协议有着截然不同的实现机制，其突出特点是引入“梯度”来描述网络中间节点与该 方向继续搜索获得匹配数据的可能性。定向扩散路由算法的主要思想是对网络中的数据 用一组属性( 对象的名称，数据发送间隔时间，持续时间，位置区域) 来命名它发出的 查询信息，基于数据进行通信。定向扩散路由也是一种基于查询的路由机制。当接收发 送器对某事件发出查询命令时就开始一个新的定向扩散过程，它由查询扩散、初始梯度 建立和数据传送三个阶段构成，如图2 2 所示。 黼妨薮妨 数三0 髫 ooo ( a ) 传播兴趣( ”建立梯度( c ) 加强路径与发送数据 ( a ) p r o p a g a t ei n t e r e s t0 ) s e tu pg r a d i e n t，( c ) p a t hr e i n f o r c 2a n ds e n dd a t a 图2 2 定向扩散路由机制 f i g 2 2d i r e c t e dd i f f u s i o n 定向扩散路由的主要过程：接收发送器通过兴趣消息( i n t e r e s t ) 发出查询任务，采用 洪泛方式传播兴趣消息到整个区域或部分区域内的所有传感器节点。兴趣消息用来表示 查询的任务，表达网络用户对监测区域内感兴趣的信息，如检测区域内的温度、湿度和 光亮度等环境信息。在兴趣消息传播的过程中，兴趣消息通过广播逐级扩散，收到兴趣 消息的节点缓存信息，并进行局部数据聚集。最终，兴趣消息遍历全网，找到所有匹配 的目标数据。实际上，初始梯度的建立和兴趣消息的扩散是同时进行的，当节点从邻接 一1 0 东北大学硕士学位论文 第二章相关工作 点接收到兴趣消息时，若当前查询缓存没有相同查询记录，则加入新记录，记录中包含 了邻接点指定的数据发送率也就是“梯度( g r a d i e m ) 。协议逐跳地在每个传感器节点上建 立反向的从数据源到接收发送器的数据传输梯度( g r a d i e n t ) 。传感器节点将采集到的数据 沿着梯度方向传送到接收发送器。 定向扩散路由采用相邻节点间通信的方式来避免维护全局拓扑，采用查询驱动数据 传送模式和局部数据聚集而减少网络数据流，因此是一种高能量有效性的协议。但是， 定向扩散路由在路由建立时需要一个兴趣消息的洪泛传播，能量和时间的开销都比较 大，不太适用于需要连续数据传送的应用( 如环境监测等) ，并且数据命名只能针对于 特定的应用预先进行。 2 1 4 谣传路由算法 谣传路由算法( r u m o r r o u t i n g ) 2 1 】是基于定向扩散路由的一种改进，它适用于节点分 布密度比较大的无线传感器网络。在以数据为中心能量有限的传感器网络中，数据本身 非常重要。谣传路由是基于为节省能量而选择一条非最佳的路径的想法提出的。它互补 地运用了查询洪泛广播式与事件广播式两种典型方式的特点，当查询数和事件数的比例 关系位于两种方式之间时，这种路由算法就很有效。其主要思想是每一个代理消息在网 络上都试图以最短路径进行传播。如果一个代理消息经过的路径上包含有其它事件的信 息，它就会将这个事件也记录到自己的事件列表中。如果代理消息发现路径上节点的事 件列表中针对某一事件的路由距离比自己事件列表中路由距离短，它就会将自己事件列 表中的相应的距离信息更新为较短的那一个。代理消息记录下目前已经经过的节点，当 它每到达一个新节点时，它还会将该节点的所有邻居节点记录下来。这样一来，在代理 消息选择下一跳经过的节点时，它就会首先从自己记录中不存在的节点中进行选择，这 样不但可以避免的路由中的环路现象( 环路会增加能量损失) ，还可以让代理消息获得 一条较直的路径。 虽然谣传路由可以根据不同查询数事件数的比率关系进行参数的适当调试，但是它 仅仅在事件数目较小时能达到很好的性能。当事件数日很大而同时接收发送器对这些事 件的查询请求较少时，维持代理消息和每一个传感器节点事件列表的消耗是很大的，这 使得谣传路由的解决方案变得不可行。另外，谣传路由受算法中使用到的不同参数( 例 如t t l 值、代理消息的数目等) 影响，所以如何得到最佳的参数非常关键，而参数的 选择只能通过不断调适才能确定。 东北大学硕士学位论文第二章相关工作 2 1 5 基于地理位置信息的路由协议 基于地理位置信息的路由算 f 去g e a r ( g e o g r a p h i ea n de n e r g ya w a r er o u t i n g ) t 2 2 1 根据 事件区域的地理位置信息，建立接收发送器到事件区域的优化路径，避免了泛洪传播方 式，从而减少了路由建立的开销。 g e a r 路由协议假设已知事件区域的位置信息，每个节点知道自己的位置信息和剩 余能量信息。那么可以利用这些信息，把在整个网络中扩散的信息传送到适当的位置区 域中。g e a r 采用了查询驱动数据传送模式。它传送数据分组到目标域中所有的节点的 过程包括两个阶段：目标域数据传送和域内数据传送。在目标域数据传送阶段，当节点 接收到数据分组，它将邻接点同目标域的距离和它自己与目标域的距离相比较，若存在 更小距离，则选择最小距离的邻接点作为下一跳节点；若不存在更小距离，则认为存在 h o l e ，节点将根据邻居的最小花销来选择下一跳节点。 0o 3 乞 d o l 、 o 、9 ：0 o ，、一一一蜷 一 图2 3 区域内的迭代地理转发 f i g 2 3l t n a t i v ef o r w a r di nf i e l d 在域内数据传送阶段，可通过两种方式让数据在域内扩散：在域内直接洪泛和递归 的目标域数据传送直到目标域剩下唯一的节点，如图2 3 所示。 g e a r 路由协议采用的是一种贪婪算法，它是一个局部最优的算法，适合无线传感 器网络中节点只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，路由过 程中可能遇到路由漏洞，反而降低路由效率。o e a r 路由中假设节点的地理位置固定或 变化不频繁，适用于节点移动性不强的应用环境。 2 2 无线传感器网络中能量有效的查询处理技术 由于无线传感器网络的一个重要特点就是电源能量有限，因此能量的有效利用成为 传感器网络查询处理中的一个核心问题，传感器网络的查询处理也因此与传统数据库的 一1 2 一 东北大学硕士学位论文第二章相关工作 查询处理有着很大的差异。本章主要介绍一些传感器网络数据管理系统中典型的查询处 理，包括基于树结构查询处理技术、基于多路径的查询处理技术、树与多路径相结合的 查询处理技术、近似查询处理技术、快照窗口查询处理技术等与本文研究内容相关的查 询处理技术。 2 2 1 基于树结构的查询处理技术 在无线传感器网络的查询处理中，基于树结构查询处理技术 2 4 1 是一种比较典型的查 询处理技术，典型的无线传感器数据库管理系统1 铀y d b 【3 明和c o u g a r l 4 0 1 中的查询处理 方式都是基于树结构的，图2 4 是一个简单的生成树结构。 基于树结构查询处理技术是指无线传感器网络中的所有传感器节点组成一棵以接 收发送器为根的生成树，查询发出者按照生成树的结构将查询传播到所有的传感器节 点，节点的感知数据根据收到查询的逆路径将数掘返回给查询发出者。在生成树建立的 过程中，每一个节点通过其父亲节点的层数计算自己所在生成树中的层数，也即是父节 点层数加1 。生成树一旦建成，查询的处理分为两个阶段：查询传播和数据收集。在查 询传播阶段，接收发送器将查询一层层的向下传，直到所有的传感器节点都收到查询； 在数据收集阶段，感知数据按照接受查询的逆路径将数据向上传递。为了尽可能地减少 数据的传输量，在数据的收集过程，会采用网内聚集的方式，经常采用的聚集函数有 m 、m a x 、s u m 、c o u n t 、a v e a g e 等。整个网内聚集的过程就是沿着生成树，从 层数最高的叶子节点开始向树根方向进行。 第。层 第l 层 第2 层 图2 4 生成树结构图 f i g 2 4s p a n n i n g t r e e 为了协调父节点与子节点之间数据的发送和接受，每个节点被分配了一个具体的时 隙来完成数据的发送和接受，并且它们都必须保持时间的同步，当第抖l 层的节点发送 一1 3 东北大学硕士学位论文 g - - 章相关工作 数据时，第i 层的节点要在侦听。分配给每个传感器节点的时隙应该足以让一对节点成 功完成数据的传输而不会在传输过程中因时段结束而中止传输，造成数据的传输失败。 所以时隙长短的分配是一个难