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

、：o 7j at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra p p l i c a t i o nt e c h n o l o g y s t u d yo ht o p - kq u e r yp r o c e s s i n gt e c h n i q u e s i nw i r e l e s s s e n s o rn e t w o r k s s u p e r v i s o r ：a s s o c i a t ep r o c e s s o r y a n gx i a o c h u n n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 ，1j_ 本人声明所呈交的学位 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：知小7 象 签字日期：沙g 工7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：知小屎 导师签名：锡蘸蘼 学位论文作者签名：伽小尿导师签名：易盼廊 签字 e l期 ：沙诣7 7 签字e l 期：伽乎、2 、妒 ，0， 东北大学硕士学位论文摘要 无线传感器网络中t o p k 查询处理技术的研究 摘要 随着传感技术、通信技术和计算机技术的飞速发展以及微型机电系统的日益成熟与 完善，无线传感器网络已广泛应用到许多领域。然而，大多数无线传感器的应用受到能 量有限性的限制。t o p - k 查询是无线传感器网络中一种典型的查询方法，要求返回指定 地理区域内传感器节点中特定k 个对象的感知数据。将传感器网络节点中所有对象的感 知数据进行传递需要消耗大量的能量。基于此，重点研究了传感器网络中t o p k 查询技 术，提出了基于差值的t o p k 查询方法。 回顾了无线传感器网络中已有的t o p k 查询技术，分析了无线传感器网络中t o p - k 连续监控查询和一次快照查询的特点。对于一次快照查询，提出了d i f f e r e n c e b a s e a l g o r i t h m ( d b a ) ，一种有效的在传感器网络中进行t o p k 查询( 例如，找到k 个最大 的聚集值) 的方法。处理过程分为三个阶段：首先通过详细地定义网络中消息的类型及 格式，基站获取一部分对象的部分和及其最大值生成候选对象，然后对候选对象集合中 的对象进行差值划分并进行阈值设置，最后根据收到的消息来完成最终的t o p k 查询。 通过差值划分来设置对象的阈值可以抑制网络中消息和数据的传输，从而减少了网络传 输代价，延长了网络的生命周期。 。 实验和分析证明，基于差值的t o p k 查询方法d b a 在完成t o p k 查询的同时，能 够尽可能地减少无线传感器网络中数据的传输，从而减少了节点的能量消耗，延长网络 的生命周期。 关键词：无线传感器网络，t o p k 查询，差值划分，阈值，消息 一i i -；qj 东北大学硕士 l e s s 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 f m 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 n sh a v eb 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 r , m 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 i n i t eb a t t e r ye n e r g y t o p kq u e r yi sat y p i c a l q 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 nks e n s o rd a t a si nt h es p e c i a l s 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 aa n d t r a n s m i t t i n ga l lo fd a t at os i n k , 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 rt o p - kq u e r i e si nw i r e l e s ss e n s o rn e t w o r ki ss t u d i e d a n de n e r g ye f f i c i e n td i f f e r e n c e - b a s e dt o p - kq u e r ya 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 gt e c h n i q u e so ft o p kq u e r i e sa l er e v i e w e d t h ef e a t u r e so f s n a p s h o tt o p kq u e r i e sa sw e l la sc o n t i n u o u sm o n i t o rq u e r yi nw i r e l e s ss e n s o rn e t w o r k sa r e a n a l y z e d a ss n a p s h o tt o p - kq u e r y , d i f f e r e n c e - b a s e da l g o r i t h ma r ef o r m a l l yp r o p o s e d ，a n e f f e c t i v ea p p r o a c ht op r o c e s st o p - kq u e r y ( e g f i n dt h eko b j e c t s 谢t 1 1t h eh i g h e s ta g g r e g a t i o n v a l u e ) i nw i r e l e s ss e n s o rn e t w o r k s t h ep r o c e s s i n go fd i f f e r e n c e b a s e da l g o r i t h mt o p - k 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 ：f i r s t l y , t h r o u g hd e f i n i n gt h et y p ea n df o r m a to f m e s s a g e s ，g o tt h ep a r t i a ls u ma n dm a xv a l u eo fs o m eo b j e c t sa n dp r o d u c tt h ec a n d i d a t es e t ， t h e np a r t i t i o n e dt h eo b j e c t s d i f f e r e n c ea n ds e t t e dt h eo b j e c t s t h r e s h o l d 1 a s t l y , f i n i s h e dt h e f i n a lt o p kq u e r ya c c o r d i n gt ot h em e s s a g er e c e i v e d d o i n gt h i sc a ns u p p r e s st h et r a n s m i s s i o n o fm e s s a g e sa n dd a t ai nt h ew i r e l e s ss e n s o rn e t w o r k s ，a n dg e tt h ef i n a lr e s u l tu s i n gl e s sc o s t t r a n s m i t t e di nt h ew i r e l e s ss e n s o rn e t w o r k s 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 dd b ac a nr e d u c ee n e r g yc o n s u m p t i o na n d l e n g t h e nl i f e t i m eo f w i r e l e s ss e n s o rn e t w o r kw h i l et o p - kq u e r i e sa l 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 ，t o p - kq u e r y , d i f f e r e n c ep a r t i t i o n , t h r e s h o l d ，m e s s a g e i 一 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 2 问题的提出3 1 3 本文工作4 1 4 组织结构5 第二章相关工作7 2 1 无线传感器网络中能量有效的查询处理技术7 2 1 1 树结构的查询处理技术。7 2 1 2 多路径的查询处理技术9 2 1 3 近似查询处理技术1 0 2 1 4 快照窗口查询处理技术1 2 2 2t o p k 查询处理技术1 4 2 2 1 一次快照t o p k 查询处理技术1 5 2 2 2 连续监控t o p k 查询处理技术1 9 2 3 本章小结2 2 第三章基于差值的t o p k 查询技术2 5 3 1 问题定义2 5 3 1 1 传感器网络的体系结构2 5 3 1 2t o p k 查询定义2 6 3 2 差值的定义2 9 3 3 基于差值的t o p k 查询的基本思想2 9 3 4 消息类型的定义及格式3 0 3 4 1q u e r y 消息的格式3 1 3 4 2t r i g g e r 消息的格式3 1 3 4 3t h r e s h o l d 消息的格式3 2 3 4 4r e p l y 消息的格式。3 3 3 5 差值划分的方式_ 3 4 3 5 1 相关定义3 4 一一 东北大学硕士学位论文 目 录 3 5 2 均匀性划分3 6 3 5 3 适应性划分3 6 3 6 基于差值的t o p - k 查询算法3 6 3 6 1 算法流程图3 6 3 6 2 首次聚集阶段3 7 3 6 3 阈值设置阶段3 8 3 6 4 再次聚集阶段3 8 3 7 本章小结3 9 第四章非叶子节点的消息响应4 1 4 1 非叶子节点对q u e r y 消息的响应4 2 4 2 非叶子节点对t r i g g e r 消息的响应4 2 4 3 非叶子节点对t h r e s h o l d 消息的响应4 3 4 4 非叶子节点对r e p l y 消息的响应4 5 4 5 本章小结4 7 第五章实验与分析4 9 5 1 测试平台与实验数据集4 9 5 1 1 测试：平台4 9 5 1 2 实验数据集4 9 5 2 实验结果与分析4 9 5 2 1 实验衡量标准5 0 5 2 2 数据等级排列的影响5 0 5 2 3 差值划分方式的影响5 3 5 2 4 第二区域长度k 的影响5 4 5 3 本章小结5 5 第六章结论5 7 参考文献5 9 致 射6 3 攻硕期间参加的项目及发表的论文6 5 一v 一 东北大学硕士学位论文第一章绪论 第一章绪论帚一早珀下匕 随着传感技术、微系统技术、数字电路、无线通信的飞速发展，无线传感器网络技 术已在许多应用领域获得越来越广泛和深入的应用，如军事、医疗、环境、交通等。然 而，由于无线传感器网络一般布置在一些难以到达的区域进行环境监测，并且大部分的 传感器设备都是由电池供电，监测环境的特殊性使得给其更换电源是不太现实的，这使 得无线传感器的应用受到了很大的限制。在查询的执行中，数据的传输是最消耗能量的， 为了减少能量的消耗，必须尽可能地减少数据的传输量。 1 1 研究背景 无线传感器网络是由大量静止或移动的传感器节点以自组织和多路的方式构成的 无线网络，其目的是协作地感知、采集、处理、传输网络覆盖地理区域内感知对象地检 测信息，报告给观察者【1 2 1 。传感器、感知对象和观察者是传感器网络的三个基本要素。 这种网络通常由传感器节点( s e n s o rn o d e ) 、接收发送器( s i n k ) 、i n t e m e t 或通信卫星、任务 管理节点等构成【3 】。 随着数字电路、无线通信等技术的发展，无线传感器网络技术已在许多应用领域获 得越来越广泛和深入的应用，如军事、医疗、建筑、环境等。在军事方面，由于传感器 节点可以散布于恶劣的环境，因而战场上可以利用传感器网络监控敌、我军兵力、装备 和物资，监视冲突区，侦察敌方地形和布防，定位攻击目标，评估损失，侦察和探测核、生物和 化学攻击。传感器网络已经成为军事c 4 i s r t 系统必不可少的一部分【4 】。在建筑方面， 传感器网络用来监控建筑物的安全状态。在c i t r i s ( c e n t e ro fi n f o r m a t i o nt e e l m o l o g y r e s e a r c hi nt h ei n t e r e s to f s o c i e t y ) 计划中，美国加州大学伯克利分校的环境工程和计算 机科学家们采用传感器网络，让大楼、桥梁和其他建筑物能够自身感觉并意识到它们本 身的状况，并自动按照优先级把信息传到相关部门，从而可以让人们方便的了解到建筑 物的安全情况。在环保方面，随着人们对于环境的日益关注，环境科学所涉及的范围越来 越广泛，主要包括跟踪候鸟和昆虫的迁移，分析环境变化对农作物的影响，监测海洋、大 气和土壤的成分等。还可以用于行星探测、气象和地理研究、洪水监测等【5 1 。传感器节 点随机密布在森林之中，监测森林环境。传感器网络也可以应用在精细农业中。以监测农 作物中的害虫、土壤的酸碱度和施肥状况等。在大洋海岸分布一些传感器，专家们就可 以根据传感器节点感知的数据及时地分析海岸的情况，减少海啸造成的人员伤亡和财产 一】一 一 传感器节点的感知数据一般具有时间关联性和空间关联性8 。时间关联是指节点在 当前时刻和下一时刻的数据值存在着定量的函数关系。通常，传感器节点感知的数据的 时间关联性与其所在感知区域的物理条件有关，物理条件所具备的时间连续性使得传感 器节点在连续采样观测中所感知到的数据具有一定的时间关联性。空间关联是指一定空 间范围内的节点的数据值之间存在着定量的函数关系。在无线传感器网络的应用中，一 般多个传感器节点就会共同地感知某个事件的发生。由于网络拓扑中节点的分布密度很 高，空间位置上接近的节点所感知的数据就会具备一定的相关性，这种相关性会随着中 间间隔节点个数的增加、节点间距离的增加而降低。 然而，传感器网络的应用却由于其自身特点受到很大的限制，传感器节点的电源能 量、存储计算能力、存储能力及传感器网络的带宽都十分有限，尤其是电源能量的影响， 成为无线传感器网络发展的瓶颈。在传感器网络中，在每个传感器节点上执行多种操作： 感知数据、查询、计算、通信、传输数据等等。其中，传输信息消耗的能量比普通的本 地操作更耗费能量，无线传感器传输1 位信息所需要的能量足以执行3 0 0 0 条计算指令【2 】。 因此，如何有效的利用传感器网络的电能，提高能量的使用效率，是无线传感器网络方 向研究的巨大挑战。 一2 一 东北大学硕士学位论文第一章绪论 无线传感器网络的主要具有以下特点： ( 1 ) 资源有限性。无线传感器网络中的传感器节点一般都是由电池供电，而传感器 节点的生命期要求比较长，所以能效问题是传感器网络的核心问题，传感器网络中的任 何技术和算法都要以能效为前提。除此之外，传感器节点的计算能力、存储能力都十分 有限，相对普通的计算机来说非常的弱，这就决定了在节点的操作系统设计中，协议和 有关算法也都要相对的精简。 ( 2 ) 自组织性。传感器节点通过分级协议和分布式算法协调自己的行为，自动的组 织成一个独立的网络。但由于传感器节点的通信能力有限，通信范围一般为几十到几百 米，那么远距离的节点之间通信需要中间节点进行路由，所以无线传感器网络是一个多 跳的自组织网络。并且网络中的所有节点都是平等的。 ( 3 ) 网络动态性。无线传感器网络具有一定的动态性，网络中的传感器、感知对象 和观察者这三要素都可能具有移动性，并且经常有新节点加入或己有节点失效，因此， 网络的拓扑结构会经常动态变化，传感器、感知对象和观察者三者之间的路径也随之变 化，这就要求传感器网络系统要能够适应这种变化，具有动态的系统可重构性。 ( 4 ) 大规模性。为了获取精确信息，在检测区域通常部署大量传感器加节点，传感 器节点数量可能达到成千上万，甚至更多。传感器网络的大规模性存在两种情况：一种 是高密度分布，传感器节点部署很密集，在一个面积不是很大的空间内，密集部署了大 量的传感器节点；另一种是低密度分布，传感器节点分布在很大的地理区域内，如在原 始大森林采用传感器网络进行森林防火和环境检测，需要部署大量的传感器节点。 1 2 问题的提出 查询是用户获得传感器网络数据的重要途径，通过查询和分析网络中的感知数据可 以检测感知区域内环境的变化情况。无线传感器网络数据的查询方式主要有历史查询、 快照查询和连续查询等。用户可以根据自己的需求采用不同的查询方式来获得感兴趣的 数据信息。 从无线传感器网路的应用来看，无线传感器网络一般覆盖的感知区域的范围比较广 阔，但查询用户有时并不关心整个感知区域的全部数据，他们感兴趣的是感知区域内某 些时刻或者某一范围内的数据情况，若用户想查询它们的物理属性，则会有这样的查询 “区域内的平均湿度最大的前两个时刻是多少? 、“区域内的最高温度是多少? 等， 类似这样的查询称为t o p k 查询。t o p k 查询是无线传感器网络中一种比较典型的查询， 一3 一 东北大学硕士学位论文第一章绪论 要求返回指定地理区域内传感器节点中特定k 个对象的感知数据。t o p - k 查询在传感器 网络的应用中具有非常重要的作用。 t o p - k 查询分为两种：一次快照查询和连续监控查询。一次快照查询是在某一给定 时间点的查询，例如：“列出区域当前的空气压强值。连续监控查询关注在持续对一段 时间段内传感器网络数据的变化情况，例如：“持续检测一次区域内的平均压强 。对于 这种一次快照查询，这将要求所有的传感器节点局部地保存自己的数据，当基站发出一 个t o p - k 查询时，简单的方法是每个传感器节点将自己所有的感知数据传给基站，然后 基站从收集到的感知数据中提取出k 个最大的查询结果。如果要把所有传感器网络节点 中的感知数据都传给基站，需要消耗很多的能量，因为对于传感器节点来说，传输数据 是最消耗能量的，所以对于对t o p k 查询来说，总是希望能传递较少的数据来换取网络 生命周期的延长以达到对环境的长期监控。 然而，无线传感器网络中t o p k 查询的原始处理需要大量的传输数据，非常消耗能 量。为了减少网络的能量消耗，延长网络的生命周期，提高网络能量的利用效率，设计 能量有效的t o p - k 查询的处理技术非常必要。 1 3 本文工作 本文分析了无线传感器网络查询处理的特点，找出问题的关键，将一次快照t o p k 查询的处理过程分为三个阶段：第一、将传感器网络节点中前k 个对象以及接下来部分 对象的范围传递给查询节点( 通常是基站) ，生成候选对象集合。第二、对候选对象集合 中的对象进行差值划分并设置孩子节点的阈值，孩子节点仅仅将大于阈值的对象传递给 查询节点。第三、通过判断候选对象集合中对象的个数来结束查询。然后分别针对不同 的阶段定义了消息的类型以及差值划分并给出了不同的处理方式。 假设传感器网络包含了m 个节点，每个节点中有行个相同的对象。当s i n k 节点或 者基站发出一个查询时，网络中节点将查询转发给其他节点并将最终的结果传回s i n k 节点或者基站。在查询转发的过程中生成一个查询生成树，每个孩子节点按照该查询生 成树将消息传给父亲节点，父亲节点处理后生成消息进一步向上传递，直至到达s i n k 节点或者基站。非叶子节点要利用孩子节点传递过来的消息求出对象的部分和和最大值 ( 称为聚集) ，然后生成消息传给父亲节点，父亲节点计算差值并设置阈值传递给孩子 节点。这些消息存贮在数据包中并在网络中传递，并且在逐层传递的过程中会抑制部分 数据的传递，从而减少了网络的负担。 一4 一 东北大学硕士学位论文第一章绪论 虽然无线传感网络是一种动态网络，其网络拓扑也是动态的，并且随着时间和环境 的变化传感器节点的感知数据可能也会变化，这样可能导致查询结果的变化。由于无线 传感器网络拓扑结构的变化带来的查询结果的变化是本文将来的工作。 1 4 组织结构 本文的组织结构如下： 第一章为引言，主要介绍了无线传感器网络的概念、典型体系结构、应用、主要特 点，根据无线传感器的应用特点引出了本文研究的问题，并对本文的主要工作进行了描 述，阐明该研究的现实意义。 第二章为相关工作，首先介绍了能量有效的查询处理技术，包括树结构的查询处理 技术、多路的查询处理技术、近似查询处理技术、以及快照窗口查询的处理技术。其中， 近似查询处理技术又包括线性模型的查询处理技术和概率模型的查询处理技术，快照窗 口查询的处理技术包括传感器网络结构的查询处理技术和独立于传感器网络结构的查 询处理技术。然后介绍了能量有效的t o p k 查询处理技术，包括一次快照t o p k 查询和 连续监控t o p k 查询。 第三章首先介绍了问题的定义然后提出了基于差值的t o p k 查询技术，介绍了d b a 算法的实现过程，详细给出了消息类型的定义及格式。同时给出了两种差值划分的定义 及计算公式来设置阈值，同时介绍了采用分桶的方式来传递阈值信息。详细介绍了d b a 算法的三个阶段。 第四章主要介绍了非叶子结点对消息的响应，对不同的消息类型给出不同的处理方 式。 第五章通过实验对d b a 方法进行分析、验证和总结。采用采用了对象等级排列相 似以及排列差别很大的两组数据集进行了测试，从数据集等级排列特点，以及额外信息 的长度和差值划分的方式对无线传感器网络中传递数据的字节数以及完成查询的循环 次数的影响证明了d b a 方法的有效性。 第六章是结论，对本文所做的工作进行了总结，并阐述了进一步的研究内容。 一5 一 硕士学位论文 第一章绪论 一6 一 一 东北大学硕士学位论文 第二章相关工作 第二章相关工作 为了解决无线传感器网络的能量利用效率问题，很多专家人士提出了很多能量有效 的查询处理技术。t o p k 查询在确定有意义对象，网络监控以及负载平衡方面都扮演着 很重要的角色。为了能有效地获得最终的查询结果，提出了很多能量有效的t o p k 查询 处理技术。随着无线传感器网络的发展，t o p k 查询逐渐应用到了无线传感器网络中。 利用这些能量有效的查询处理技术来提高无线传感器网络能量的利用率，尽可能减少传 感器节点的能量消耗，并使每个节点的能量消耗平均，最大限度的延长无线传感器网络 的生命周期。本章首先介绍了无线传感器网络中能力有效的查询处理技术，同时介绍与 本文研究内容相关的t o p k 查询处理技术。 2 1 无线传感器网络中能量有效的查询处理技术 由于无线传感器网络的一个重要特点就是电源能量有限，因此能量的有效利用成为 传感器网络查询处理中的一个核心问题，传感器网络的查询处理也因此与传统数据库的 查询处理有着很大的差异。本章主要介绍一些传感器网络数据管理系统中典型的查询处 理，包括基于树结构查询处理技术、基于多路径的查询处理技术、近似查询处理技术、 快照窗口查询处理技术。 2 1 1 树结构的查询处理技术 在无线传感器网络的查询处理中，基于树结构查询处理技术【l o 】是一种比较典型的查 询处理技术，典型的无线传感器数据库管理系统t i n y d b t 川和c o u g a r t l 2 1 中的查询处理 方式都是基于树结构的，图2 1 是一个简单的生成树结构。 基于树结构查询处理技术是指无线传感器网络中的所有传感器节点组成一棵以接 收发送器为根的生成树，查询发出者按照生成树的结构将查询传播到所有的传感器节 点，节点的感知数据根据收到查询的逆路径将数据返回给查询发出者。在生成树建立的 过程中，每一个节点通过其父亲节点的层数计算自己所在生成树中的层数，也即是父节 点层数加l 。生成树一旦建成，查询的处理分为两个阶段：查询传播和数据收集。在查 询传播阶段，接收发送器将查询一层层的向下传，直到所有的传感器节点都收到查询； 在数据收集阶段，感知数据按照接受查询的逆路径将数据向上传递。为了尽可能地减少 数据的传输量，在数据的收集过程，会采用网内聚集的方式，经常采用的聚集函数有 m 、m a x 、s u m 、c o u n t 、a v e a g e 等。整个网内聚集的过程就是沿着生成树，从 一7 一 北大学硕士学位论文g _ - 章相关工作 数最高的叶子节点开始向树根方向进行。 第0 层 第l 层 第2 层 图2 1 无线传感器网络中生成树结构图 f i g 2 1t h es t r u c t u r eo fs p a n n i n gt r e ei nw i r e l e s sn e t w o r k s 为了协调父节点与子节点之间数据的发送和接受，每个节点被分配了一个具体的时 来完成数据的发送和接受，并且它们都必须保持时间的同步，当第什1 层的节点发送 据时，第f 层的节点要在侦听。分配给每个传感器节点的时隙应该足以让一对节点成 完成数据的传输而不会在传输过程中因时段结束而中止传输，造成数据的传输失败。 所以时隙长短的分配是一个难点问题，如果分配的时隙过长，就有可能造成时间的浪费， 并且对于树根来说，要得到查询结果的时间就会很长，那么查询结果的延时也会相当长； 反之，如果分配的时隙过短，会造成传输数据冲突，数据传输失败，查询结果不准确。 为了保证无线传感器网络节点之间数据传输的可靠性，生成树必须能够适应网络的 情况，节点在选择父节点时，需要考虑很多因素，比如节点之间的距离、剩余能量等。 并且传感器节点还要能够实时的处理一些异常情况，比如当一个链路发生问题的时候， 传感器节点应该能够选择一条相对好的通信路由，以确保通信的正常进行，提高生成树 的健壮性。 树结构的生成一个比较典型的方法是根据节点的剩余能量，即节点选择剩余能量最 多的节点作为自己的父节点。建立过程如下：接收发送器发出查询，求网络中节点剩余 能量的最大值，每个节点向邻居节点广播自己所知道的最大能量，通过这种广播的方式， 节点可以知道邻居节点中的能量最大值和最大值所在的节点，节点会将自己作为这个最 大值所在节点的子节点。通过在全网范围内采用这种方式求最大值，会建立起一个基于 剩余能量的多少而建立起来的一棵生成树。这棵树的根部是剩余能量比较多的节点，而 靠近叶子的节点的剩余能量就比较少。这样，网络就可以根据当前节点的剩余能量动态 一8 一 东北大学硕士学位论文第二章相关工作 地调整树的位置和形状，增大网络的寿命。 基于树结构的查询处理最大的优点是数据的收集是向着根节点进行的，不会出现沿 着背向根节点的方向进行的情况，如图2 1 所示。以m a x 查询为例，当父节点接收所 有子节点的传输的感知数据，求出这些数据和本地数据的m a x 值，然后传给上一层节 点，而不是传输所有的感知数据，这样一层层向上传，并在传的过程中进行聚集，其实 每次传的只有一个数据，而不是所有的感知数据，在没有通信错误的情况下，这种基于 树结构的查询处理方法的准确度是1 0 0 。但是在无线传感器网络通信错误率很高或者 数据包丢失率很高的情况下，会对查询结果造成很大的影响。或许层次高的传感器节点 的数据包丢失对查询结果造成的影响不会很大，但层次低的节点数据包丢失就会导致以 该节点为根的整个子树的所有数据的都丢失，这种情况下，可能会造成查询结果的精度 是非常低。所以基于树结构的查询处理技术的可靠性有时不是很好，为了解决这个问题， 提出了基于多路径的查询处理技术。 2 1 2 多路径的查询处理技术 基于多路径的查询处理技术1 3 , 1 4 1 是在树结构的基础上提出的，为了提高数据传输的 可靠性。基于多路径的查询处理技术采用环形拓扑结构，因为这种环的结构会提供很好 的能量利用率。图2 2 是一个多路径的环形拓扑结构图。 多路径的环形拓扑结构的建立过程：首先接收发送器广播一个结构建立消息，任何 接收到这个广播信息的传感器节点将自己的环序号置为1 ，环序号为1 的传感器节点继 续广播该消息，收到消息的传感器节点的环序号为2 ，依次类推。每层的节点都广播消 息，接收到消息且环序号还未确定的传感器节点将自己的环序号置为比广播该信息的传 感器节点的环序号大1 ，这样每个传感器节点都知道了自己的环序号。环序号也即是该 节点所在的层数。 第0 层第1 层 图2 2 多路径结构图 f i g 2 2t h es t r u c t u r eo f m u l t i p a t hg r a p h 9 ， 解传感器网络感知数据的大致情况，所以会提出一些近似查询，例“返回当前感知区域 中的最高温度，误差为r 。那么在这种情况下，不需要传输所有节点的感知数据、节 点的所有感知数据、以及大量相同数据，而只需传递数据的改变量就可以推测出大致的 数据情况，或者通过节点与其临近节点的感知数据的数据关系来计算数据情况，或者通 过传感器节点的历史数据来近似估计实际数据情况等等。于是，许多专家人士就利用一 些统计学上的技术来解决近似查询处理问题，尽量缩减网络的数据传输量，减少传感器 网络的能量消耗。， 2 1 3 1 线性模型的查询处理技术 基于线性模型的查询处理找出传感器网络中传感器节点之间满足的线性模型，然后 利用模型和一些相应的规则把传感器节点分为不同的簇，每个簇由簇头回答查询。快照 查询( s n a p s h o tq u e r i e s ) t ”】是由y a n n i sk o t i d i s 提出的一种比较典型的基于线性模型的查 询处理技术，下面就以快照查询为例介绍基于线性模型的查询处理技术。 快照查询的基本思想是，先计算传感器节点之间的线性模型，然后利用模型和一些 规则把传感器节点分为簇，然后由簇头来回答查询。在模型建立阶段，首先要收集传感 器节点的一些历史数据，然后利用线性回归的方法计算出节点之间线性模型，再把计算 出的线性模型嵌入到传感器节点，这样传感器节点就知道了自己与邻居节点只见到的线 一】0 一 东北大学硕士学位论文第二章相关工作 性关系。在簇的建立和簇头选取阶段，首先每个节点m 都广播一条消息，表明自己要选 取代表，并且消息中包括当前的感知数据款d 。同时每个节点m 也都在接受其邻居节点 广播的消息。收到m 广播的消息的传感器节点m ，通过内嵌的线性模式，计算出x x o ， 然后计算出误差尺度d ，与给定的误差阀值丁相比，如果小于等于lm 将m 加入自己 能代表的节点列表c a n a ln o d e s , o 中。c a n dn o d e o 建立结束之后，每个节点m 都广播自 己的c a n dn o d e s , o ，节点m 从收到的列表中找一个拥有c a n dn o d e s o 最长的节点m 作 为自己的代表节点，然后通知节点m 。最后，利用一些规则完成代表节点的最终选取。 无线传感器网络选取出的代表节点形成了整个无线传感器网络的快照，如图2 3 所 示。通过此方法所得到的查询结果含有一定的误差，一般都是近似结果，所以当用户对 查询结果的精度要求不高时，使用此方法效果很高，速度快，消耗能量少。当然，用户 可以根据对查询结果的要求选择自己使用的查询方法。执行快照查询时，代表节点通过 模式计算出其所代表节点的近似感知数据，其他节点则处于睡眠状态，只有代表节点来 回答查询。这样，只有很少一部分节点参与查询的执行，从而减少了传感器节点的能量 的消耗，延长无线传感器网络的生命周期。 6 7 。、，0 0 、9 0 。 j 0 、 、 。q ，- 。 。 。 。、 0o o0 o ， o o - ：， 。o o 占0 0 + 0 o o 。 o oo o ，0 0，o 、 ，7 ， 0 0 0 0 图2 3 网络快照 o o f i g 2 3n e t w o r ks n a p s h o t 快照查询通常是由一组代表节点和一个误差阈值丁构成，通过这些代表节点的地理 位置以及节点采样值可以得到整个感知区域数据的大致分布情况。并且这种方法还有很 好的健壮性，当代表节点附近的传感器节点坏死或出现临时状况时，那么此时代表节点 可以通过模型来估算出现问题的传感器节点的数据情况。线性模型需要不断地学习来提 高准确度，学习的过程是：在节点的缓存中不断读取新的有价值的数据。新数据的加入 一1 1 东北大学硕士学位论文第二章相关工作 遵循不同的策略，通过计算不同策略的收益值可以判断采用哪种策略比较好。为了确保 节点始终能被另一个节点准确地代表，节点需要周期性的检测代表节点是否称职，如果 发现代表节点能量不足或者坏死，节点会重新发出邀请，重新选择代表节点。 2 1 3 2 概率模型的查询处理技术 在无线传感器网络中，感知数据在传输过程中，有可能受到噪音的干扰，或者是由 于电能的消耗导致的信号减弱，或者受到一些不确定因素的影响，使得数据变得不精确， 有的甚至是非常错误的数据。有的感知数据在传输过程中丢失，例如在美国大鸭岛的一 个传感器网络，研究人员发现有时4 0 的传感器节点产生的温度和湿度值都不正常，那 么如果数据感知系统可以检测到错误的数据，就可以不用传输这些没有意义的数据，从 而节省了能量和带宽。 。 为了解决上述问题，提出了基于概率模型的查询处理技术1 6 捌，可以从概率模型收 集数据，并且可以利用概率模型找出不同属性值之间的关系。概率模型可以用来对传感 器读数进行更好的分析，例如，它们可以帮助解决感知数据值在空间上的不均衡问题， 可以帮助确认提供错误信息的节点，并且可以推断出坏死节点或即将坏死节点的感知数 据。另外，概率模型可以减少传感器节点的数据传输，只有当前概率模型不能够推断出 一个符合精度的数据时，才允许传感器采集数据。 在基于概率模型的查询处理中，查询处理引擎利用概率模型回答关于传感器网络当 前状态的查询。利用概率密度函数p ，x 2 ，x n ) 表示概率模型，是一个某个特定传 感器上的某个属性( 例如，5 号节点上的温度) 。通常每个传感器的某种类型只能对应一 种属性。概率模型还可以处理隐含变量( 不被直接显示出来的变量) ，比如一个节点是 否给出了一个错误的数据。可以利用历史数据采用标准的算法来维护概率模型，同时也 可以利用采集到的传感器节点最新数据来更新概率模型。 2 1 4 快照窗口查询处理技术 窗口查询分为两种：快照窗口查询和连续窗口查询。快照窗口查询是对查询窗口在 某一给定时间点的查询，例如：“列出区域彳当前的空气压强值 ；连续窗口查询关注在 某一段时间间隔内查询窗口内传感器网络数据的变化情况，例如：“每1 0 秒检测一次区 域x 内的平均压强是多少，持续3 个月 。对于快照窗口查询已经提出了一些处理方法 1 4 , 1 6 - 1 9 , 4 0 4 5 1 。这些处理方法可以分为两种：基于传感器网络基本结构和独立于传感器网 络基本结构，如图2 4 所示。基于传感器网络基本结构的查询处理是指查询的执行依赖 传感器网络的结构进行；独立于传感器网络基本结构的查询处理是指查询的执行不依赖 一1 2 东北大学硕士学位论文 第二章相关工作 于传感器网络的结构，即查询的执行不受传感器网络结构的影响。 ( a ) 网络生成结构：树 ( a ) n s i ：t r e e o o o ，漆。 0 o 。 o o ( b ) 窗口生成结构：树 ( b ) w s i ：t r e e 图2 4 窗口查询处理结构 a 0 夕 ? q o ；，g 文 o - ( ) 一7 一 罗 o w u ，。 ( c ) 基于路线的结构 ( c ) i w q e o o f