（信息与通信工程专业论文）无线传感器网络中面向节能的多查询优化研究.pdf

一 il 原创性声明 l i i 1lii i ii ii1 1 1i iiil y 1718 7 4 0 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名： 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：蛐 导师签名逊日期：盖坐年上月监日 r e s e a r c ho ne n e r g ye f f i c i e n tm u l t i p l eq u e r i e so p t i m i z a t i o ni n w i r e l e s ss e n s o rn e t w o r k s s p e c i a l t y ：i n f o r m a t i o na n dc o m m u n i c a t i o ne n g i n e e r i n g m a s t e rd e g r e ec a n d i d a t e ： s u p e r v i s o r ：a s s o c i a t ep r o f z h e n gj i n s c h o o lo fi n f o r m a t i o ns c i e n c ea n d e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y , c h a n g s h ah u n a np r c m a y 2 0 1 0 摘要 无线传感器网络是由大量的传感器节点通过自组织形成的一个无线 网络，能够对大范围区域进行有效监测，并对监测数据进行处理，将其传 送到需要这些信息的用户。由于无线传感器网络中的节点都是通过电池供 电，一旦能量用完就会失效。因此，如何能量高效地对无线传感器网络中 的多查询进行优化，降低网络节点的能耗是本论文的研究重点。 本论文分析了现有的无线传感器网络内部多查询处理技术，提出了基 于关联度的多查询优化算法( a s s o c i a t i o nd e g r e e b a s e dm u l t i p l eq u e r i e s o p t i m i z a t i o na l g o r i t h m ，a d m q o ) 。提出了关联度的概念，用来衡量节点间 的数据相关性，节点通过计算与候选父亲节点之间关联度选择父节点，使 得查询重叠区域的节点聚集到同一组中。对于相同的查询数据，组中的节 点可以一次性传输而不必多次重复传输，从而有效地减少网络数据的传输 量。模拟分析表明，该算法有效地减少了网络中的数据传输量。 本论文利用多个查询问存在查询数据重叠的现象，提出了基于查询重 写的多查询优化算法( q u e r yr e w r i t i n g b a s e dm u l t i p l eq u e r i e so p t i m i z a t i o n a l g o r i t h m ，q r m q o ) 。在基站处对前一周期用户提交的查询进行解析、重 写，使得多个查询问共享查询数据，从而减少了分发到网络中的查询数量， 进而减少了网络的传输数据量。模拟结果表明，该算法充分减少了网络中 的数据传输量，达到了节能的目的。 由于传感器节点的能量主要消耗在传输数据上，所以减少节点数据传 输量可以有效延长网络生命期。本论文提出的多查询算法利用共享机制实 现多个查询问的数据共享，有效地减少了网络中的数据传输量，这对于无 线传感器网络中的相关研究具有一定的参考价值。 关键词：无线传感网络，多查询优化，关联度，查询重写，节能 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 s ) a r ef o r m e db yal a r g en u m b e ro fn o d e s t h r o u g hm u t u a lc o o p e r a t i o n ，w h i c hc a nc a r r yo u te f f e c t i v em o n i t o r i n go na w i d er a n g eo fr e g i o n s ，p r o c e s st h em o n i t o r i n gd a t aa n dt r a n s f e rt h ed a t at o u s e r sw h on e e di t a san o d ei ss u p p l i e db yb a t t e r i e s t h en o d ew i l lb ei n v a l i d i fi t se n e r g yi se x h a u s t e d t h e r e f o r e ，w ef o c u so no p t i m i z i n gm u l t i p l eq u e r i e s e n e r g ye f f i c i e n t l yt or e d u c ee n e r g yc o n s u m p t i o no fs e n s o rn o d e s t h i st h e s i sa n a l y z e sm u l t i p l eq u e r i e si n n e t w o r kp r o c e s s i n gt e c h n o l o g i e s i nw s n s a s s o c i a t i o nd e g r e e b a s e dm u l t i p l eq u e r i e so p t i m i z a t i o na l g o r i t h m ( a d m q o ) i sp r o p o s e d i na d m q oa l g o r i t h m ，t h ec o n c e p to fa s s o c i a t i o n d e g r e ei sp r o p o s e d ，w h i c hi su s e dt om e a s u r et h ed a t ao fn o d e sc o r r e l a t i o n n o d e sc h o o s ep a r e n tn o d eb yc a l c u l a t i n ga s s o c i a t i o nd e g r e e sb e t w e e nn o d e s a n dc a n d i d a t ep a r e n tn o d e s ，a n dn o d e sc o v e r e db yo v e r l a p p i n gr e g i o n so f q u e r i e sc l u s t e ri n t oag r o u p a st h es a m ev a l u e sw i l lb et r a n s f e r r e do n c e i n s t e a do fb e i n gt r a n s f e r r e dr e p e a t e d l y , t h en u m b e ro fd a t at r a n s m i t t e dc a nb e e f f i c i e n t l yr e d u c e d p e r f o r m a n c ea n a l y s i sa n ds i m u l a t i o nr e s u l t ss h o wt h a tt h e p r o p o s e da l g o r i t h m c a nr e d u c et h ea m o u n to ft r a n s m i s s i o nl o a di nw s n s i nt h i st h e s i s ，q u e r y r e w r i t i n g b a s e dm u l t i p l eq u e r i e so p t i m i z a t i o n a l g o r i t h m ( q r m q o ) i sa l s op r o p o s e d ，d u et ot h ef a c tt h a tv a l u e so fq u e r i e s a r ea l w a y se x i s t i n go v e r l a p i nt h eb a s es t a t i o n ，q u e r i e ss u b m i t t e d b yu s e r si n t h e p r e v i o u sp e r i o da r er e w r i t t e ni n t oa no p t i m i z e ds e tt h a ts h a r e st h e c o m m o n a l i t y a n de l i m i n a t e st h er e d u n d a n c ya m o n g q u e r i e si nt h eo r i g i n a ls e t , c o n s e q u e n t l y , t h en u m b e ro fq u e r i e ss e n di n t ot h en e t w o r ki sr e d u c e d ，a n dt h e a m o u n to fd a t at r a n s m i t t e df r o ms e n s o rn o d e st ot h eb a s es t a t i o ni sa l s o r e d u c e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a nd e c r e a s et h e n u m b e ro fd a t at r a n s m i t t e di nw s n s a st h ee n e r g yo fs e n s o rn o d e sm a i n l yi sc o n s u m e di nt r a n s m i t t i n gd a t a ， r e d u c i n gt h ea m o u n to fd a t at r a n s m i t t e dc a ne x t e n dt h en e t w o r kl i f e t i m e t h e p r o p o s e dt w os c h e m e se f f i c i e n t l yt a k ea d v a n t a g eo ft h ew o r ks h a r i n g m e c h a n i s ma m o n gm u l t i p l eq u e r i e s ，a n de f f e c t i v e l yr e d u c et h ea m o u n to f t r a n s m i s s i o nl o a d i ti sv a l u a b l et ot h er e l a t e dr e s e a r c hi nw i r e l e s ss e n s o r n e t w o r k s 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 ，m u l t i p l eq u e r i e so p t i m i z a t i o n ， a s s o c i a t i o nd e g r e e ，q u e r yr e w r i t i n g ，e n e r g ye f f i c i e n c y h 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 无线传感器网络概述1 1 1 1 无线传感器网络结构；1 1 1 2 无线传感器网络的特点。2 1 1 3 无线传感器网络的应用4 1 2 无线传感器网络中的数据管理6 1 3 本课题研究的主要内容9 1 4 论文结构1 0 第二章查询处理机制的分析与研究1l 2 1 查询处理的体系结构1 1 2 2 查询执行流程l2 2 3 数据模型和查询语言1 4 2 3 1 数据模型1 4 2 3 2 查询语言1 5 2 4 查询的分类1 7 2 5 查询处理方式。l9 2 5 1 集中式查询处理方式1 9 2 5 2 分布式查询处理方式1 9 2 6 多查询处理技术存在的主要问题2 0 2 7 本章小结2 0 第三章基于关联度的多查询优化算法_ 。2 2 3 1 网络模型假设及问题分析2 2 3 1 1 模型假设2 2 3 1 2 问题分析2 2 3 2 基于关联度的多查询优化算法2 3 3 2 1 基本概念2 3 3 2 2 算法描述。2 4 3 3 模拟实验与结果分析2 7 3 3 1 模拟实验2 7 3 3 2 结果分析2 8 3 4 本章小结。2 9 第四章基于查询重写的多查询优化算法3 0 4 1 无线传感器网络模型及假设3 0 4 2 问题分析3 0 4 3 基于查询重写的多查询优化算法3 3 4 3 1 查询分解3 3 4 3 2 构造候选查询集3 3 i l l 4 3 3 查询重写的可行性分析3 4 4 3 4 查询重写3 5 4 4 算法举例3 7 4 5 模拟实验与结果分析3 8 4 5 1 模拟实验3 8 4 5 2 结果分析4 0 4 6 本章小结4 1 第五章总结与展望“4 2 5 1 研究工作总结4 2 5 2 研究工作展望4 2 参考文献4 4 j i 【谢51 攻读学位期间主要的研究成果5 2 i v 中南大学硕士学位论文第一章绪论 第一章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 就是大量的微型传感器节点 组成，传感器节点部署在监测区域内，价格低廉，并通过无线通信的方式组成一个具 有多跳和自组织特点的网络系统。无线传感器网络通过综合应用嵌入式技术、传感器 技术、无线通信技术以及分布式的信息处理等技术，使得网络中的传感器节点( s e n s o r ) 能够协作地对监测区域内的各种环境以及监测对象进行实时性的监测，并感知和采集 信息，然后将相关信息进行处理后传送给相应的用户。在2 1 世纪，传感器网络是最重 要的网络之一，它将会在人们的日常生活中发挥重要的作用。在无线传感器网络中能 量是其考虑的最重要因素，目前国内外主要针对w s n s 资源有限的特点做了一系列研 究，并就如何能量高效地进行网络部署、拓扑控制、路由、安全、数据管理等研究出 许多协议和算法。为了方便用户，使其在使用w s n s 的时候就如同在传统的数据库管 理系统上操作一样，需要做大量的底层数据管理工作，其中，查询处理是重要的工作 之一，能量高效地查询处理方法能够提供高效地用户反馈、通过能量有效而提升网络 的生命周期。 1 1 无线传感器网络概述 1 1 1 无线传感器网络结构 无线传感器网络是由大量具有通信和计算能力的微型传感器节点密集布撒在环 境复杂的监控区域，并通过节点间的无线通信从而形成的一个自组织网络系统。其中， 传感器节点的结构【2 1 如图1 1 所示，它一般由数据采集模块( 包括传感器和模数转换 模块) 、数据处理模块( 包括c p u 、存储器等) 、无线通信模块以及电源四部分组成。 图1 - 1 传感器节点结构图 中南大学硕士学位论文第一章绪论 传感器节点在网络中除了用作数据采集外还要负责进行数据转发，即起到路由器 的作用。如图1 2 所示，各类集成化的微型无线传感器节点任意散落在被监测区域， 节点之间通过自组织的形式形成网络，协作地感知网络覆盖的地理区域中各种环境或 检测对象的属性信息，然后节点通过多跳的方式将监测信息发送到基站，从而将监测 数据传送到总控制中心进行集中处理，并发送给用户终端，用户通过这些数据获知网 络覆盖区域内的各种信息，包括光照强度、噪声、湿度、压力、土壤成分、温度、移 动物体的方向、速度和大小等信息。i n t e m e t 通过构造逻辑的信息世界改变了现实社 会中人们的沟通方式，而无线传感器网络将通过融合逻辑上的信息世界与客观上的物 理世界改变人与物质世界的交互方式，从而大大扩展了现有网络的功能和提高了人类 认知世界的能力。 1 1 2 无线传感器网络的特点 图1 - 2 传感器网络结构图 传感器网络虽然与传统无线网络有相似之处，但同时也存在很大的差别。传感器 网络的首要设计目标是能量的高效利用，而传统无线网络的首要设计目标是提高服务 质量和高效带宽利用，其次才考虑节约能量。除此之外，无线传感器网络还具有以下 一些特点【3 5 】： ( 1 ) 大规模网络 w s n s 的大规模有两方面的含义，一个是指传感器节点部署在很大的地理区域内， 如监控森林火灾时被放置在原始大森林，或监测建筑物状态时被部署在大范围的厂房 区域。第二个是指传感器节点是大量的甚至成千上万的、密集部署的。大规模带来了 一些优点，大量的节点产生的冗余给网络带来可靠性和强容错性。由于节点本身可能 由于感应模块的问题导致感应的数据是错误的数据，这时可以通过分析邻居节点的数 据，取平均值或者选择统计出现次数最多的数据为最后的确认数据来满足数据可靠、 2 中南大学硕士学位论文 第一章绪论 精确的要求。传感器节点也可能由于能量耗尽等原因而导致节点失效，这时可以唤醒 处于睡眠状态的邻居节点来代替自己的工作，从而满足网络的容错性。 ( 2 ) 能量有限的网络 在无线传感器网络中，传感器节点的能量有限。由于传感器节点由电池供电，且 体积微小，所以电池存储的能量有限，也因此传感器节点容易因电池耗尽而失效。由 于电源能量约束，使得无线传感器网络的应用没有普及发展。电池的发展远远滞后与 传感器节点的计算能力，这是因为在无线传感器网络中，传感器节点传输数据要比执 行计算更消耗能量，节点传输l b i t 信息所消耗的能量相当于执行3 0 0 0 条计算指令【4 1 。在 有限能量的条件下，如何提高网络通信效率，减少不必要的数据转发，完成数据融合 和查询优化是我们必须要解决的问题之一。比如在火灾监测场景下，人员无法达到， 此时就不能采取人工充电的方式解决能量问题，能量依然是无线传感器网络的最核心 问题。 ( 3 ) 通信能力、存储计算能力有限的网络 无线传感器网络中的传感器节点工作的环境比较复杂，往往会受到高山、障碍物 等地势地貌以及风雨雷电等自然环境的影响，并且由于传感器之间通信的带宽窄而且 常常发生变化，造成传感器节点之间的通信时断时续，经常需要对数据进行重新传输， 如何在较为恶劣的通信环境下优质高效地将感知数据传输到基站并对其进行处理是 解决无线传感器网络应用的关键问题之一。 在无线传感器网络中，传感器节点进行无线通信时，能量消耗公式为： e = k d ” 公式( 1 一1 ) 其中，参数n 的限制条件为2 ( n ( 4 。n 的取值受到诸多因素的制约，当网络环境中 地势起伏较大时，节点通信时由于障碍物较多，所以干扰比较大，此时1 1 的取值就比 较大。在实际应用中，综合各种因素n 的取值通常为3 ，即传感器节点通信能耗正比于 通信距离的三次方。由于节点的能量消耗随着通信距离的增加而快速增大，因此在网 络通信连通度允许的范围内应该尽量减少节点间的通信距离。在无线传感器网络中， 一般将网络节点的无线通信半径设置在1 0 0 m 的以下。 在无线传感器网络中，传感器节点需要对周围的环境或对象进行监测并采集相关 数据同时还要对数据进行一定程度的处理然后将其传输到基站。但是由于传感器节点 中的嵌入式处理器和存储器的计算和存储能力有限，所以在实际应用中需要对网络数 据进行分布式处理以充分利用传感器节点的处理和存储能力，这也是无线传感器网络 的特点之一。 ( 4 ) 动态性的网络 传感器节点会因能量耗尽而失效；网络布撒时由于地势地貌或各种因素的破 坏造成网络内的“洞，从而导致网络布撒的不均匀；在网络运行期间，由于风力， 3 中南大学硕士学位论文第一章绪论 河流冲刷以及人和动物的破坏可能会造成网络节点的移动，从而造成网络节点的非预 期的移动；为满足应用需要而增加新的网络节点造成的网络拓扑改变，也同样反映 了网络的动态性。以上四个情况均在一定程度上对网络的动态性产生了影响。 ( 5 ) 自组性的网络 由于无线传感器网络监测环境的复杂性和网络部署方式的随机性的特点，传感器 节点必须具备自组织性才能构建出一个统一的网络，从而在网络运行期间，根据网络 拓扑的变化自适应地调整监测状态完成对监测数据的采集、处理和传输，并最终完成 网络的监测任务。 ( 6 ) 应用相关的网络 在选择w s n s 时，对不同的应用需求，用户感兴趣的数据、对网络硬件要求等都 可能不同，加者传感器节点本身资源的有限性，某个w s n s 模型不可能也没必要设计 成一个通用的网络，只有让网络更贴近应用，才能做出更高效的目标系统。于是，在 我们研究设计各种算法、协议的时候，做到与实际应用相结合是一个明智的选择。 ( 7 ) 以数据为中心的网络 相对于i n t e m e t ，无线传感器网络把数据作为网络的中心【4 】。用户想得到的不是传 感器网络的拓扑构造及其硬件设施而是传感器网络所监测到的数据。对无线传感器网 络来说，用户所需要的是传感器节点监测到的周围环境或监测对象的属性数据，对于 具体的传感器本身的状态，用户并不关心。用户常常会向基站提交的查询是：“网络 中a 的平均温度是多少? ，而不是，“a 区域的还剩下多少个传感器节点? 。用户从 不会向基站提交这样的查询：“网络中b 区域中的节点m 是通过哪条路径将数据传输到 基站的? 1 1 3 无线传感器网络的应用 当前无线传感器网络的应用领域主要在以下几个方面【6 l ： ( 1 ) 军事应用。由于传感器网络能够实现快速布撒传感器节点具备自组织性且网 络的容错性较高，在军事战场中有着广阔的发展前景。通过无线传感器网络能够实时 的监控敌我双方的兵力部署、武器装备的运转情况以及对地形地貌实施有效地侦查， 甚至还可以了解战场上士兵的健康状况，对敌方重要的军事实施目标定位，从而进行 精确打击。同时，由于传感器节点能够适应恶劣的环境所以，无线传感器网络还可以 用于核攻击和生物化学攻击的监测。在战争中，无线传感器网络通过飞机或者其他手 段部署到敌方阵地内部或周边，从而近距离监测和收集敌方阵地的情报提供给军事决 策者使用。 + ( 2 ) 环境应用。随着生活水平的提高，人们越来越关注生态环境的变化，对生态 环境的研究也日益深入。由于无线传感器网络具有部署快速、自组织、容错性高等特 4 中南大学硕士学位论文第一章绪论 点，因此被广泛用于气象监测、洪水监控、森林火险预警、地理研究、火山探测、洋 流监测以及城市小气候环境的监测等。无线传感器网络的出现也可以用来提高农业耕 作方式，使其更加精细化，如无线传感器网络可以用来监测农场中土壤的酸碱度、空 气湿度、农作物的灌溉程度以及田地中害虫的危害范围等。此外，无线传感器网络还 可以用来跟踪研究动物迁徙、种群聚集和海洋深处的生物种群等方面。 ( 3 ) 医疗健康。利用传感器节点可以进行无线通信的特点，无线传感器网络被用 来实时监测医院或家庭中的老年痴呆症患者、重病人士和幼d , j l 童的日常起居，从而 大大方便了医院监护人员以及父母的工作量，同时提高了工作效率。在远程医疗中， 无线传感器网络还可以为远在千里之外的医生准确地提供病者的各种生理信息，从而 为患者提供更好的医疗服务。这也是最近几年的研究热点物联网实际应用的一部分。 ( 4 ) 空间探索。鉴于外太空恶劣的生存条件以及饮食起居等各方面的难题，即使 是宇航员也不能长期生存，而传感器则具有不怕辐射能适应恶劣环境的优势，如果解 决好能源问题，传感器节点可以较长时间对太空进行监测和收集相关数据。科学家利 用无线传感器网络返回的数据进行计算，可以了解很多天体的运行轨道以及验证宇宙 中负粒子的是否存在。 ( 5 ) 智能家居。通过将传感器节点嵌入到墙壁、家具、家电甚至在镜子上，并且 将这些传感器节点互联起来形成网络，构造出人们梦寐以求的智能家居系统，无线传 感器网络能为人们提供更加舒适和便利地生活。如果将家中无线传感器网络再和 i n t e m e t 连接起来，人们就可以随时随地了解家中情况，还可以对家中电器进行远程 控制，例如，可以在外出回家前打开浴室中的热水器，卧室里的空调，甚至还可以提 前在微波炉里烤面包，电饭煲里煮饭，电视机里录节目，这样回到家的时候人们就可 以享受到舒适的室温，美妙的晚餐，收看已经录制好的电视节目。同样，人们可以在 上班或外出时监测家中的各个角落，给家中宠物添加零食，给家中的绿色植物加水以 及防止家中财物被盗窃。相信这样的智能家居生活在不久的将来就能够逐渐进入到人 们的日常生活中。 ( 6 ) 其它用途。由于传感器节点具有自组织性、微型化、且能够很好地适应各种 环境的特点，无线传感器网络可以应用到很多领域中。例如对高速公路的重点路段的 路面破坏情况进行监测；对我国正在大力建立的告诉铁路的桥梁、隧道、轨道进行监 控，可以有效防止特重大事故的发生；城市的公共交通情况往往很糟糕，可以对各个 路段实施监控，疏导交通，提高路段利用率；在矿井的关键层面设置传感器，通过无 线传感器网络对矿井的地质状况、渗水的程度、瓦斯的浓度进行实时监控，从而挽回 人们生命国家财产的重大损失，提高生产安全性；在核发电厂的关键区域部署无线传 感器网络，不间断地监控辐射浓度，达到一定阀值就报警，从而提高核电工作人员的 人体健康状况。 虽然无线传感器网络现在的应用还不广泛，但随着传感器电池容量的提升以及芯 5 中南大学硕士学位论文 第一章绪论 片技术的飞速发展，传感器节点的使用寿命和计算能力将会越来越高，其生产成本将 会更加低廉，在未来无线传感器网络将为在人们生活的各个方面发挥越来越大的作 用。 1 2 无线传感器网络中的数据管理 无线传感器网络是一个具有节点众多、网络拓扑随时间变化并且产生大量数据的 网络，对于用户来说，它就是一个大型的分布式数据库，用户是通过数据的准确性、 结果返回间隔、网络生命期等因素来评价网络的性能7 1 。为了得到理想的网络性能， 需要分别在数据链路层、路由层、应用层对数据进行处理，在数据收集、数据存储、 数据查询、数据融合等过程中以减少网络能量消耗为目标对网络实施优化【8 。由于无 线传感器网络的数据量巨大，对其数据进行管理是必须的。对数据进行有效地管理可 以让网络对用户透明，用户只需向基站提交查询请求，无线传感器网络通过数据管理 系统的在后台对用户查询请求进行处理，然后把结果返回给用户，从而实现了网络对 用户的透明。与传统数据库不同的是无线传感器网络采用分布式的处理方式来对其数 据进行处理。 无线传感器网络的特点是以数据为中心，这主要是由网络的应用性质决定的： 无线传感器网络最终的目的是为用户提供其感兴趣的数据；由于无线传感器网络的 数据量巨大，这就需要对节点采集到的数据进行分析、挖掘、聚集、融合等操作； 无线传感器网络在具体应用中需要借助各种网络数据的处理技术【l o l 。 由于无线传感器网络以数据为中心，所以它的设计方法与i n t e m e t 等其他计算机网 络的设计方法不相同。在无线传感器网络中，节点感知数据的处理是其中心环节。这 就要求传感器网络必须紧密联系数据库技术和网络技术，对数据进行物理和逻辑两个 层面上进行处理，从而使得用户在使用网络时感觉不到网络的存在，并且用户使用无 线传感器网络时的操作和传统数据库的操作具有连续性和继承性。同时由于无线传感 器网络数据量大且由分布在监测区域内的节点产生，所以传统数据库中的数据查询、 分析、挖掘、聚集、优化和融合等技术需要在传感器网络中重新定义，而如何在无线 传感器网络中实现对感知数据有效地处理就成为其网络管理的主要内容。 用户在使用无线传感器网络时，感兴趣的是网络所监测到的数据，对于网络的硬 件设施用户则不会关注。所以，无线传感器网络能否为用户提供有效服务的关键是网 络能否对感知数据进行有效地管理和处理。如何能够使用户方便地访问网络数据是无 线传感器网络中重要的研究内容之一。在最初的无线传感器网络中，用户需要通过编 制大量的代码来访问传感器网络的数据管理系统，但对于普通用户来说，这是很困难 的。为了实现访问传感器网络的简单化，同时方便用户操作，国内外有关机构做了大 6 中南大学硕士学位论文第一章绪论 量的研究工作。当前，加州大学伯克利分校提出的t i n y d b 系统【1 2 b 】和康奈尔大学提出 的c o u g a r 系统【1 0 , 1 1 】在传感器网络数据管理系统最具有代表性，下面我们分别介绍一 下这两个系统。 t i n y d b 系统是由加州伯克利分校开发的传感器网络数据管理系统，为网络用户 提供了一个简单、方便易用和类s q l 的应用接口。主要有三个部分：客户端、t i n y d b s e v e r 和传感器网络。t i n y d b 系统的客户端a p i 安装了基于j a v a 的应用程序，这样，用 户可以像使用传统的关系数据库系统一样使用t i n y d b 系统查询网络中的数据，而不必 关注网络的实现细节，从而使得传感器网络对用户透明，大大改善了用户的使用体验。 同时，当用户提出查询时，t i n y d b 系统从网络中收集相关数据，并通过传感器节点的 调度对查询进行分布式处理，最后将查询结果返回给用户。在传感器网络中，每一个 传感器节点都安装t t i n y d bq p 软件，同时只要节点加装t t i n y d bq p 软件都能够动 态的加入到网络中。t i n y d b 系统主要有以下五个主要特点： ( 1 ) 元数据管理。在t i n y d b 系统中，有丰富的元数据及其管理功能，还有一系列 的相应的管理元数据的命令。同时，t i n y d b 还具有一个专门描述传感器读数类型以及 网路内部软硬件参数的元数据目录。 ( 2 ) 说明性查询语言。为了方便用户的使用，t i n y d b 系统提供了与s q l 相似的说 明性查询语言。用户通过这种描述性的语言来提交查询请求而不必指明如何在网络当 中获取所需数据。这样，用户可以方便地使用说明性地查询语言来编写应用程序，极 大地提高了用户查询数据的效率。 ( 3 ) 网络拓扑管理。当传感器网络发生变化时，t i n y d b 系统通过跟踪管理来维护 网络的路由表，并且确保网络中的节点能够可靠同时高效地将数据传输到基站。 ( 4 ) 多查询。在t i n y d b 系统中，在相同节点集上可以同时进行多个查询，并且每 个查询感知属性的访问类型、查询周期等都可以不相同。为了提高查询处理的速度和 效率，t i n y d - b 系统还能够在多个查询中有效地进行共享操作。 ( 5 ) 可扩展性。由于无线传感器网络是一个动态网络，所p a t i n y d b 系统提供了网 络的扩展功能，如果需要对网络扩展，只需简单地将标准t i n y d b 系统代码安装到新加 入的节点中就可以了。 c o u g a r 系统是康奈尔大学开发，主要有三个部分：( 1 ) 图形用户界面g u i ；( 2 ) 客 户前端系统( f r o n t e n d ) ( 3 ) 查询代理( q u e r y p r o x y ) 。用户通过g u i 向传感器玩那个 罗提交查询请求。客户前端系统( f r o n t e n d ) 用于担当传感器网络与用户之间的网关， 它运行在选定的节点上，是一个功能强大的查询代理，可以直接连接至o i n t e m e t 或其他 现实世界的网络中。同时，f r o n t e n d 也是g u i 和查询代理之间的界面，它们之间使用 t c p i p 数据包进行通信。查询代理则是一个小型的传感器网络数据查询处理软件，运 行在所有传感器节点上。在网络内部，c o u g a r 系统采用定向扩散( d i r e c t e dd i f f u s i o n ) 路由算法进行通信，并且采用x m l 的信息交换格式。 7 中南大学硕士学位论文 第一章绪论 以上两种系统都是基于将传感器网络表示为数据库的思想，通过向使用者提供类 似于s q l 的高级数据查询语言实现了分布式条件下的无线传感器网络的数据管理，。 虽然与传统方法相比，以上系统所使用的方法已经有了很大改进，但还是无法满足使 用者对数据查询处理的需要，这就需要针对网络使用者的需求，有针对性地对传感器 数据查询处理技术进行更加深入的研究。 同时，无线传感器网络同样与传统数据库也有所不同【1 4 , 1 5 】。 ( 1 ) 网络支撑不同。前者由于支撑为能量、功能有限的传感器节点，所以查询等 须于传感器节点紧密结合，相互配合。而后者大多时候是基于i n t e r n c t ，不考虑细节。 ( 2 ) 传感器网络每个传感器节点产生的是连续的无限的数据流，而传统的数据库 系统处理不了这种情况。 ( 3 ) 传感器节点由于感应模块的原因，可能感应的数据具有不同程度的误差，感 应结果是近似的，所以网络需要根据不同的要求来处理这种误差。 ( 4 ) 传感器节点能量有限。传感器网络数据管理系统需要尽量减少其能量消耗， 从而延长传感器网络的生命周期。由于通信的能量消耗远远大于计算的能量消耗，所 以需要在传输数据之前尽量进行数据的网内处理或本地计算以尽量减少传输的数据 量，节省能量。 ( 5 ) 查询类型有所不同。前者有如精确查询、连续查询、快照查询、近似查询、 多维查询、时空查询、历史查询等不同于应用相关的查询类型。 ( 6 ) 传统的数据库系统的查询处理技术不适合传感器网络。 ( 7 ) 传感器网络产生的数据量极其庞大，难以全部保存到存储器中，同时传感器 网络通信带宽、节点处理能力和能量有限，所以无线传感器网络中数据需要分布式存 储和计算。 无线传感器网络的数据管理中数据存储技术主要有以下三种 1 6 , 1 8 ： ( 1 ) 外部存储方法。感知数据经过传感器节点得简单的过滤后全部被传送到基站。 这种存储方法的优点是感知数据可以长期存储在基站，同时基站可以对这些数据做一 些复杂的运算和查询，查询历史数据的速度比较快。但这种方式也有很明显的缺点， 节点需要将所感知的所有数据都上传到基站，这要耗费节点大量的能量，而且靠近基 站的节点会因频繁地转发数据而耗尽能量失效。外部数据存储方式只有在网络的用户 访问感知数据的频率远高于产生这些数据的频率时才具有可用性。 ( 2 ) 本地存储方法。将节点的感知数据都存储分别存储在相应传感器节点上的方 法称为本地存储方法。由于数据都存储在产生这些数据的节点中，所以不需要节点进 行传输而消耗能量，为传感器节点节省了传输能耗。但是，当用户提出查询请求时， 网络的数据管理系统需要消耗大量能量和时间对相应数据进行查询。尤其是当用户频 繁地提出查询请求时，本地存储方法将比外部存储更加耗能。 ( 3 ) 数据中心存储方法。将数据按照一定规则分布式或分类地存储在相应节点中 8 中南大学硕士学位论文第一章绪论 的方法称为以数据为中心的存储方法，这种方法的网络能耗在上面介绍的两种存储方 法之间。如表卜1 所示，其中n 为网络中的传感器节点个数，o ( n ) 是网络中广播信息的 时间，d ( i ) 是两个节点之间互相传输单位数据的时间，眈为网络中节点监测的感 知数据的个数，岛为q 个查询返回的感知数据的个数，q 为用户向基站提交的查询的 个数。 表1 1 无线传感器网络中三种存储方式的开销比较 传感器网络如何向用户提供灵活有效地数据存储方法和与之相应的索引技术从 而支持以数据为中心的处理方式是传感器网络的研究重点之一【1 9 2 0 1 。当前，相关研究 人员已经基于感知数据的分布式存储思想提出了一些研究成果，效果较为理想。典型 的方法包括地理散列函数方案( g e o g r a p h i c a lh a s ht a b l e ) 和层次索引结构方案 ( m u l t i d i m e n s i o n a lr a n g ei n d e x ) 两种方法【9 2 。 1 3 本课题研究的主要内容 无线传感器网络是以数据为中心的网络，核心是网络查询的优化与处理【4 】。在实际 应用中，同一时间段内可能会有多个查询提交到基站并分发到网络中，这样必然会增 大无线传感器节点的数据采集频率和传输数据量，增加节点的能量消耗，降低网络的 生命期。因此，需要能量高效地对多查询进行优化处理。由于在无线传感器网络中， 传感器节点传输数据要比执行计算更消耗能量，减少网络传输数据量可以有效减少传 感器网络的能源消耗。因此，能量消耗是评价多查询处理算法优劣性的关键指标。所 以多查询优化的算法应最小化从源节点到基站的传输数据，从而降低节点能量消耗， 高延长网络的生命期。 本论文的研究的具体内容包括： ( 1 ) 在无线传感器网络内部对多查询进行优化处理，当多个查询分发到网络中时， 网络节点的数据采集频率和数据发送量必然会增大，从而导致网络内部需要发送的数 据量不断增加。因此，如何利用节点的本地计算能力对多查询数据进行网内处理以减 少网络的数据传输量是本论文研究的重点之一。 ( 2 ) 在基站处对多查询进行优化处理，基站相对于传感器节点来说通常具有更加 9 中南大学硕士学位论文第一章绪论 充足的能量和处理能力以及存储容量。当多个用户同时向基站处提出多个查询时，由 于多个查询问往往具有查询数据重叠现象，如何利用查询间的这些特点在基站处对查 询进行解析，从中提取出多个查询问的重叠数据信息，从而对其进行重写处理以实现 多个查询问的数据共享，是另一个值得研究的方面。 1 4 论文结构 本论文共分为五章，其组织结构如下： 第一章是绪论部分，其中主要介绍了无线传感器网络的基本内容，概述了无线传 感器网络结构、特点、应用以及数据管理，总领全文。 第二章详细介绍了无线传感器网络中查询处理的体系结构，并对现有的查询类型 和查询处理技术进行了分类介绍，分析了无线传感器网络查询处理的研究现状以及目 前无线传感器网络中查询处理技术所存在的问题，为文章的后续内容做铺垫。 在第三章中，介绍了本课题的研究重点无线传感器网络中基于关联度的多查 询优化。针对现有无线传感器网络内部的多查询的现象，分析了当前针对多查询的网 内处理技术的优