（计算机应用技术专业论文）基于sensor+net的联机分析处理.pdf

中文摘要 中文摘要 随着无线通信技术、微型传感器技术和嵌入式计算技术的飞速发展 和不断成熟，具有感知能力、无线通信能力和一定计算能力的低功耗微 型传感器在世界范围内出现，对这种传感器以及山这种传感器组成的传 感器网络( s e n s o rn e t ) 的应用研究也逐渐成为学术界和工业界关注的 焦点。这种传感器可以通过组成网络实时地监测并获取环境的信息。 本文根掘传感器数据往往与空间属性相关的特点，定义了传感器网 络上的o l a p 分析操作( s o l a p ) 。本文研究了在传感器网络上实现s o l a p 的关键技术。在传感器网络中，节点需要被组织成适当的拓扑结构以便 实现有效的路由。本文使用了基于树的路由方法，并设计了一个求路出 树深度的算法，分析了这个算法的理论代价，并利用试验验证了分析结 果并给出了这个算法的参数取值的影响。s o l a p 中的d r i l l d o w n 和r o l l u p 操作只需要下发到网络的一部分节点。如果网络中的所有节点都进行数 据传输，将会造成节点能量的不必要浪费。针对这个问题，本文提出了 一个索引结构来引导操作请求的下发，利用试验，给出了这个结构的效 率。聚集计算是s o l a p 中的关键计算。如果使用集中式计算方法节点的 能量丌销会很大，同时还会造成大量数据丢失。本文使用了网内聚集的 方法进行聚集计算，并提出了自己的聚集计算时间调度方法。实验证明， 本文提出的策略在传输成功率上较之传统网内聚集方法提高很大。本文 提出了一个多粒度部分解的存储结构及其上的上滚和下钻操作来存储和 处理聚集部分解，并给山了上滚和下钻操作的代价。利用以上方法，本文 实现了一个s o l a p 原型系统。 关键词：传感器网络，o l a es o l a r 路由树，网内聚集，时阳j 调度 黑龙江大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fp r o c e s s o r , m e m o r ya n dr a d i ot e c h n o l o g y ， n e t w o r k sc o m p o s e do fc h e a pn o d e sc a p a b l eo fs e n s i n g ，c o m m u n i c a t i o na n d c o m p u t a t i o nh a v eb e c o m ep o s s i b l e t h ed e p l o y m e n to fs u c hn e t w o r k sc a l l p r o v i d eal a r g e d a t as o u r c ef o rt h em o n i t o r i n go fp h y s i c a lw o r l d m o s t e x i s t i n gs y s t e m sf o rc o l l e c t i n ga n dp r o c e s s i n gs u c hs e n s o rd a t ao n l yp r o v i d e s i m p l eq u e r yo p e r a t i o n s ，w h i c hm a yn o tb es u f f i c i e m f o ru s e r st o g e t i n f o r m a t i o nt h a tt h e yw a n tf r o mt h es e n s o rd a t a i nt h i sp a p e r , t h eo n l i n ea n a l y t i c a lp r o c e s s i n g ( o l a p ) o p e r a t i o n ，w h i c h h a sb e e nw i d e l yu s e di nt r a d i t i o n a ld a t aw a r e h o u s es y s t e m ，i si n v i t e di n t ot h e s e n s o rn e t w o r ka san e ww a yf o ru s e r st oq u e r ya n da n a l y s i ss p a t i a lr e l a t e d s t a t i s t i c a lr e s u l to fe n v i r o n m e n t a ld a t as u c ha st e m p e r a t u r ea n dh u m i d i t y t h e d e f i n i t i o no ft h eo p e r a t i o no ns e n s o rn e t w o r kc a l l e ds o l a pi sp r o v i d e di n t h i s p a p e r t oi m p l e m e n tt h eo p e r a t i o no ns e n s o rn e t w o r k ，m a n yp r o b l e m s s h o u l db es t u d i e d f i r s to fa l l ，t h en e t w o r ks h o u l db eo r g a n i z e dp r o p e r l yt o f o r mar o u t i n gs t r u c t u r es ot h a tt h ed a t ac a nb ee f f e c t i v e l ys e n tt nt h el a s e r i n t h i sp a p e rt h en e t w o r ki so r g a n i z e dt oam u t i n gt r e et oa c c o m p l i s hi t a n a l g o r i t h mf o rc o m p u t i n gt h ed e p t ho f t h e t r e ei sp r o v i d e d b e c a u s eo p e r m i o n s f o rs o l a ps u c ha sd r i l l d o w na n dr o l l u po n l yn e e dt ob es e n tt oap a r to ft h e w h o l en e t w o r k ，i ti sc o s t l yf o ra l lt h en o d e si nt h en e t w o r kt op a r t i c i p a t ei n t r a n s m i t t i n gt h eo p e r a t i o n i nt h i sp a p e r ，am u l t i - g r a n u l a r i t yi n d e xi sp r o v i d e d t od e a lw i t ht h i sp r o b l e m t h em o s ti m p o r t a n tc o m p u t a t i o np r o c e s s i n gf o r s o l a pi st h ea g g r e g a t i o no ft h es e n s o rd a t a i fi ti sd o n eb yac e n t r a l i z e d 外文摘要 w a y , t o om u c hd a t ah a v et ob et r a n s m i t t e db ye a c hn o d ei nt h en e t w o r ka n d t h i sw o u l dc o s ts ot h ee n e r g yc o n s t r a i n e ds e n s o rn o d e si nt h en e t w o r ks o m u c he n e r g yw h a ti sm o r e t h i sw o u l dc a u s ec om u c hd a t at ob el o s tt h r o u g h t h et r a n s m i s s i o n i n n e t w o r ka g g r e g a t i o ni so b v i o u s l yag o o dc h o i c et om a k e t h i sc o m p u t a t i o ne f f i c i e n t i nt h i sp a p e r ，an e wt i m es c h e d u l i n gm e t h o df o r i n n e t w o r ka g g r e g a t i o ni sp r o v i d e d o p e r a t i o n sf o rs o l a ps h o u l db es e n t p r o p e r l y t ot h et oc e r t a i nn o d e sj u s ta st h en e t w o r ki sc o r n p u t i n gt o a c c o m p l i s ht h i s ，at i m es c h e d u l i n gp r o c e s sf o rt r a n s m i t t i n gt h eo p e r a t i o n si s p r o v i d e di nt h i sw o r k f o rn o d e st os t o r em u l t i g r a n u l a r i t yp a r t i a lr e s u l t so f t h ei n n e t w o r ka g g r e g a t i o n ，ad a t as t r u c t u r ei sp r o v i d e d t h eo p e r a t i o n so nt h e s t r u c t u r et oa c c o m p l i s hd r i l l d o w na n dr o l l u pa r ea l s os h o w e d u s i n gt h e m e t h o da b o v e ，ap r o t o t y p ef o rs o l a pi sa l s oi m p l e m e n t e d k e y w o r d s ：s e n s o rn e t w o r k ，o l a rs o l a p , r o u t i n gt r e e ，i n n e t w o r k a g g r e g a t i o n ，t i m es c h e d u l i n g 1 1 1 第1 章引言 第1 章引言 1 1 研究背景 随着无线通信技术、微型传感器技术和嵌入式计算技术的飞速发展 和不断成熟，具有感知能力、无线通信能力和一定计算能力的低功耗微 型传感器在世界范围内出现，对这种传感器以及由这种传感器组成的传 感器网络( s e n s o rn e t ) 的应用研究也逐渐成为学术界和工业界关注的 焦点= 。”。这种传感器可以通过组成网络来相互协作，实时地监测并获 取环境的信息，传送到需要的用户”1 。通过这种网络，人们还可以与真 实的物理环境发生交互。可以说，传感器网络这一技术将使人类的生活 方式发生革命性的变化。但传感器网络的应用也受到很多限制。首先， 传感器网络是a dh o c 形式的m ，它的路由方法与传统的网络路由方法有 很大不同。另外，传感器节点自身携带的能量十分有限，其传输能力和 运算能力也十分有限。这些限制给要求长寿命，高准确性的传感器网 络数据处理应用提出了挑战。 1 1 1 传感器网络的网络环境 传感器网络是由多个具有感知能力，有限计算能力和有限数据传输 能力的传感器节点所组成的。每个节点一般出感知部件，处理部件，传 输部件，电源部件，存储部件和软件等及部分组成( 如图1 1 ) 。 幽】l 传感器的鲴成 黑龙江大学硕士学位论文 根据应用的不同，传感器网络的缸点方式也有所不同。对于需要采集 某些特定位置的环境信息的应用，传感器需要被布置在特定的位置。 在另外一些环境下，传感器会被随机的放置在监测区域上。不论哪一种 方式，网络中的各节点都需要通过自组织的多条路由与外界进行联系。 图1 2 和图1 3 分别给出了两种典型的传感器网络结构“j 。图1 2 中的 传感器网络由传感器节点、接收发送器( s i n k ) 、i n t e r n e t 或通信卫星、 任务管理节点等部分构成。传感器节点散布在指定的感知区域内，每个节 点都可以收集数据，并通过“多跳”路由方式把数据传送到s i n k 。s i n k 也可以用同样的方式将信息发送给各节点。s i n k 直接与i n t e r n e t 或通 信卫星相连，通过i n t e r n e t 或通信卫星实现任务管理节点( 即观察者) 与 传感器之间的通信”1 。在图1 3 中的传感器网络中，数据通过基站转送 到有线网络网络节点分为3 类：基站节点( b a s es t a t i o nn o d e s ) 、固定 节点( f i x e dn o d e ) 和应用节点( a p p l i c a t j o 1n o d e ) 。基站节点担任无线 传感器网络和有线网络的网关。固定节点通过多跳路由方式与基站进行 数据通信。应用节点是可移动或者固定的节点。 图i 2 一种典刑的传感器网络结构 第1 章引言 幽13 另一种骢碳的传感器网络结构 上面这两种网络结构中，在同一个s jn k 或基站点下的传感器节点都 是能力相同的节点。这种结构的问题在于当网络规模很大时，信息传输 的延迟很大，无法保证相应速度。图14 给出了一种异构的网络组织形 式r 。在这种结构中，网络中加入了一些传输能力很强的节点，这些节点 在其它节点看来是对等的，唯一的差别是传输能力更强。这使得网络中 形成了一些“高速公路“( h i i g h w a y ) 。使用这种结构，网络中数据传输的 质量会得到很大提高”。 dh o co e n 8 0 rn 瞳w o mw i t hah b a n d w i 晰he 0 21 1m e s hc f v 刚1 a yr i d w o 昨 b a s e do r li n t e lx s c a 呛田t e c h n o l o g , , | 垫ll4 一种具有高性能i 点的异构网络 从传感器网络的结构，可以看到传感器网络中只需要有限的基；硭i ( b a s e s t a t i o nn o d e s ) 或接收发送器( s i n k 、与外界进行联系。其内部的节点是以a d 黑龙江大学硕士学位论文 h o c 形式存在的。这就给网络的布点和使用带来了很大的灵活性。这种 灵活性使得它在军事和民用等多个方面都显示出了很大的应用前景。 1 1 2 传感器网络的特点 由于受到技术、成本等因素的制约，传感器是一种能力受限的设备。 图1 5 中展示的是一种典型的传感器节点b e r k e e ym o t e s ，图1 6 是它的 各项性能指标的列表“! 。从图中可以看到传感器节点的能力是十分有限 的，这使得传感器网络具有以下的个特点”“。 r n1 1 m 喃d i 替 ( 。九ik r e q u e m y| m h ， r h ， r p t 1 1 1 m l h m a n 1 孙k b r a d i nf v 肿 r a d i * j m u l ”n “j 1 1 m ，日i m h 4 ：m r i d m 【1 1 u 廿m l l 4 0 k h z h 脚f 帅0 i 4 d b i 川tl n c ia 4 5 j i 阱 i l a s h n l w l l 、5 i ：k i j；l ：k n n 3 曲w cr l m ol l m ! 孙h v l “ d 鼎a dr _ i “i l 、：孙h v 1 n ，n2 5 6h i k 、 图1 ，5 b e r k e l e ym o t e s 幽i6b e r k e l e ym o t e s 的技术指标 首先，传感器网络节点的计算能力受到很大限制。由于使用嵌入式处 理器，其主频受到很大限制，其计算能力比较低。传感器节点中的存储 器一般使用嵌入式处理其中的存储器和片外的f l a s hr a m 。这种存储器的 配置使得传感器节点的数据存储能力较弱。这也制约了传感器节点的计 算能力。 传感器节点的第二个特点是数据传输能力受收到限制。传感器节点使 用的无线传输部件一般为单片r f 芯片，其传输距离一般在几十米。如果 使用高强度的发射信号也只能达至i j y l 百米，在这种状态下数据传输的能 量消耗会很大。由于这种芯片发出的无线信号强度有限，其容易受到障 碍物，电子噪声等因素的干扰。 第l 章s i 言 影响传感器网络性能的另个重要因素是传感器网络节t i 的能量限 制。传感器网络节点中消耗能量的主要部件是无线数据传输部件和处理 器。其中，无线数掘传输部件的能量消耗占主耍位置。传感器传输l 位信 息所需要的电能足以执行3 0 0 0 条计算指令“。传感器网络节点需要使用 微型电源提供能量。这种电源能够提供的电量比较低，而且这种情况在 短期内无法通过替代技术来改变。1 。 传感器网络的节点所产生的是流式数据，其数据量很大。这与传感器 节点的有限的计算能力、存储能力和数据传输能力形成了矛盾。因此， 这个特点对传感器网络的影响很大。 传感器网络的以上几个特点给传感器网络的应用带来了很大的挑战。 以上这些问题中尤其突出的是能量受限和产生数据量大的特点。传感器 能量受限的问题在未来的一段时间内是很难解决的1 ”。由于无线传输所 消耗的能量很大，当网络需要传输的数据量很大时，网络的生命周期会 被大大的缩短。这使得产生数据量大的问题变得更加严重。由此也可以 看出，在尽可能满足用户需求的情况下，减少传感器网络中节点的能量 开销和延长网络的生命周期，对提高传感器网络的性能是至关重要的。 这也使得能量开销和生命周期，成为了两个衡量传感器网络性能的重要 参数。 1 1 3 传感器网络的应用 出于传感器网络的成本低，布设起来相对于有线网络更加自由快捷， 其应用前景是非常广阔的。根据f r e e d o n i ao r o u p 萃u f r o s t s u lliv a n 的数据”“，无线传感器硬件的市场有望以每年2 0 的速度递增。 现在已经有很多研究人员m ”3 将传感器网络放置在实际环境下使 用。这些应用主要可以分监测( m o n i t o r jn g ) 和跟踪( t r a c k jn g ) 两种”。 黑龙江大学硕士学位论文 在监测的应用中”“1 ，传感器节点测出自己周围的环境信息并将其 发送给用户。在这个过程中，传感器节点可能会互相交换信息以提高数 据的正确程度。 网络中传输的数掘量旦超过网络中各节点所能承受的限度，就会 有大量的数据被丢弃，从而导致结果的证确程度降低。这种情况下大量 的节点将以很高的频率传输数据，从而使得节点能量的过快损耗。其结 果是网络生命周期的下降。因此，在监测的应用中，尽量降低网络中节 点传输的数据量，是提高结果精度和延长网络生命周期的关键问题。 在跟踪的应用中“叭”1 ，传感器网络中各节点协同工作，对处于其监 测范围的物体进行跟踪，并将物体的位置信息传送给网络外的用户。用 户还可以利用传感器网络的跟踪功能预测物体下一个可能出现的位置。 利用传感器网络进行跟踪，首先要解决的是如何对物体进行定位的问题。 对物体进行定位需要三个以上的节点协同工作，并互相交换信息”。在 对物体进行跟踪的过程中，如果所有的传感器节点都实时地对物体进行 探测会导致大量的能量浪费。解决这一问题的方法是每一时刻只使用网 络中节点的部分对物体进行探测，其它节点则处于休眠状态。实现这 种方式的关键在于尽可能f 确地预测节点在下一时刻的位置并唤醒相应 的传感器节点“”1 。 传感器网络数据可以使用集中式和分靠式两种方式进行处理“。在 使用集中式处理方式传感器网络系统中，每个传感器只进行路由、数据 采集和数据传输，所有的数据都被传送到一台高性能的处理器上进行处 理。在使用分布式处理方式的系统中，传感器节点除了进行在集中式系 统中所作的工作外，还要协同地进行数据的处理。 集中式处理方式将传感器传输的数掂集中进行处理。其优点足数据 处理能力强，可以使用大部分流数据的处理方法对其进行处理。j 。 第1 章引言 其缺点是网络传输的数据罱大，数 _ | ：l ：丢失严币网络节j s 、能晕损 人， 网络的尘命周期较短。 分和式处理方式中，传感器节点在传输数据的同日_ j 对数掘进行些 处理和运算。传感器节点通过对网络中的多个数据的运算形成一个部分 解进行传输，从而减少了网络中传输的数据量“- 。这种方法的难点 在于如何协调各节点的工作时间，使得各节点可以协调一致进行数掘处 理。 早期的传感器网络的应用都是由研究人员根据特定的应用对传感器 网络编写相应的程序“。使用这种方法，使用者必须投入大量的 精力对传感器节点的软件进行设计。这对使用者来说十分不方便。为解 决这一问题，数据库的概念被引入到了传感器网络中。1 。 在传感器网络数掘库中传感器节点中的信息被作为一个关系。关 系中的属性是传感器节点中的描述信息和感知信息。传感器网络数据库 使用d e c l a r a t i v eq u e r y 的查询方式”1 。利用这种查询方式，用户只需 要使用类似s q l 的查询语言进行提出自己的查询要求，不需要了解查询 的实现细节。 综上所述，用户使用传感器网络的目的在于利用传感器的数掘处理 和传输功能获得所需要的信息。从这个意义上讲，传感器网络所研究的 所有问题，都是以如何有效利用传感器网络中有限的计算和通信资源尽 可能的处理传感器所得到的数据，从而向用户提供有效的信息这一问题 为核心的。这个问题也自然成为了传感器网络研究的核心问题。 1 2 国内外的研究现状 由于传感器网络的巨大应用日u 景，其研究f 逐步受到各国研究人员 的重视。美国的加州大学伯克力分校、康奈尔大学等学校丌始了传感器 黑龙江大学硕士学位论文 i i i | i i i i i i i i i i b l l ；i i i i i i i i i 暑 网络的基础理论和关键技术的研究。其他一些发达国家的大学和研究机 构也纷纷丌展了该领域的研究工作。我国的哈尔滨工业大学和黑龙江大 学也开始了对传感器网络的研究。学术界已经丌展了一些感知数据查询 处理技术的研究，取得了一些初步研究结果。 康奈尔大学在感知数掘查询处理技术方面丌展了较多的研究工作 ”“”。他们研制了一个测试感知数据查询技术性能的c o u g a r 系统。探 索了把传感器网络表示为数据库的思想，探讨了如何把分布式查询处理 技术应用于感知数据查询的处理。 加州大学伯克力分校研究了传感器网络的数据查询技术，应用数据 库技术实现了传感器网络上的数掘聚集函数，提出了在低能源、分布式无 线传感器网络环境下实现聚集函数的方法，并研制了个感知数据库系 统t i n y d b “2 4 6 1 8 a 南加州大学还研究了传感器网络上的聚集函数的计算 方法，提出了节省能源的计算聚集的树构造算法并通过实验证明了无线 通信机制对聚集计算的性能有很大的影响“。 哈尔滨工业大学和黑龙江大学在传感器数据管理系统方面开展了研 究工作，提出了以数据为中心的传感器网络的数据模型，设计了一系列的 能源有效的感知数据操作算法和感知数据查询处理技术，并研制了个 传感器网络数据管理系统”! “。 现有的传感器网络的数据操作方法比较简单，无法满足应用的需要， 因此本文提出了基于传感器网络的联机分析处理操作。 联机分析处理是传统数据仓库中的一种十分重要的操作类型一“。在 传统的数据流系统上也有所研究。企业的决策者可以利用这种操作通 过不同的角度，不同的粒度对历史数掘进行分析，从而为企业的决策提 供依据。使用者在分析过程中使用下钻( d r i l l d o w n ) 和上滚( r o l lu p ) 第1 苹引言 作对数掘进行不同粒度的查询。为满足实时眭要求，数掘仓库中使用了 事先根扼用户的要求计算并存储一个c u b e 的方法。 在现实世界中，很多度帚与区域有着密切的关系。例如，拄 01 k 城f h 中空气中污染物的含量高于非工业城市；室内取暖系统出现故障的区域 比没有故障的区域温度低等等。如何获得区域中某属性的统计信息是传 统的空间数据库研究的问题。在传感器网络的研究中，去获取和利用 区域中的属性信息也是一个重要的研究领域。”。 在某些应用中，人们需要监测的区域范围是具有层次结构的。例如， 一座建筑的供暖系统的一部分出现问题可能只影响建筑的某一层的某一 边的某个房间。在这种情况下，如果通过监测建筑中各房问的温度来发 现这个故障，势必会使网络中的数据传输量很大，从而使网络的寿命变 短。如果换一种方式，开始时只监测各层楼的某个适当的温度统计值。 当出现故障时，异常会反映到相应楼层的统计值上。这时可以通过进行 一个下钻操作看一下是这层楼的哪一边出现的问题。接下来在出现异常 的那一边继续作一个下钻操作来确定故障点的位置。如果使用网内聚集 ( i n n e t w o r ka g g r e g a t i o n ) ”w 这种分布式处理方式，后一种方法所需要 传输的数据量会被大大减少。在这种背景下，本文提出了基于传感器网 络的联机分析处理( s o l a p ) 操作来满足这类监控应用的需要。 要满足以上应用的要求，首先要对基于传感器网络的o l a p 分析操作 进行确切的定义。要实现这样的操作，需要解决传感器网络的组织问题， 以有效的将传感器网络组织成合适的拓扑结构，保证数据的传输。在此 基础上，需要实现有效的聚集算法以进行聚集计算。这种数据的查询分 析方式需要进行一系列操作，因此需要有效的操作请求处理方法对这些 操作进行处理。 黑龙江大学硕士学位论文 基于传感器网络的联机分析处理与传统的联机分析处理的差异，在 于处理的数据的不同和处理的方法的不同。基于传感器的联机分析处理 处理的是实时数据，而且数据只具有层次这个粒度。处理方式采用实时 计算而非预先计算。 据笔者所知，对传感器网络上的o l a p 分析的研究现在还基本处在空 白阶段。明确提出如何在传感器网络上进 j t o l a p 操作的文章，笔者还没 有见到。本文在这方面做出了一定的研究与尝试。 1 _ 3 本文的贡献 本文将联机分析处理这种传统的数据仓库中的数据查询分析方式引 入到传感器网络中。针对传感器网络中数据的地理分布特点和动态变化 特点提出了传感器网络中的o l a p 分析操作的定义，并研究了实现这以操 作的关键技术。 由于传感器网络的资源限制集中式计算方法不适于实现传感器网 络上的o l a p 分析操作。为有效地进行聚集运算，本文使用的网内聚集的 方法，为进一步提高网内聚集的数据传输成功率，本文提出了自己的聚 集时间调度策略。实验证明，本文提出的策略在传输成功率上较之传统 方法提高很大。本文的聚集计算是基于路由树的，树的深度是聚集计算 的一个重要参数。为得到路由树深度这个重要参数，本文提出了一个求 路由树深度的算法，分析了这个算法的理论代价，并利用试验验证了分 析结果并给出了这个算法的参数取值的影响。 为有效地处理操作请求，本文提出了基于传感器网络的o l a p 分析 的操作请求处理方法。联机分析处理操作的操作请求需要在聚集计算的 同时进行下发。这种情况下，操作请求会因聚集计算时间调度过程中关 第1 章 吾 闭网络数掘传输部件的原因而丢失。针刈这以问题，本文提出丁操作清 求下发的时间调度算法。为保证数掘的有效下发，本文提出了网络数据 下发索引结构。利用试验，本文给出了这个结构的效率。出于在计算过 程中，网络中节点要存储多粒度的聚集部分解。本文提 了一个多粒度 部分解存储结构束解决这个问题。在这个结构上，设训了打i 11d o w n 和 r o l u p 的操作算法并给出了其代价。 使用以上提出的方法，本文实现了一个基于传感器网络的联机分析 处理原型系统s o l a p s 。本系统提供s u m ，c o u n t ，姒x ，m i n 四种聚集函数， 能够完成具有一个层次属性结构的传感器网络的联机分析处理操作。 1 4 论文结构 本文主要分为六个部分。 第一章引言。介绍了本文的研究背景、传感器网络上的联机分析处 理的意义、国内外的研究现状、本文的贡献，阐明了本文的研究意义和 学术价值。 第二章背景知识。给出了基于传感器网络的联机分析处理的定义和 s o l a p 分析语言。 第三章传感器网络的联机分析处理系统。介绍了实现s o l a p 操作的 技术问题和本文提出的s o l a p 系统( s o l a p s ) 的系统结构。 第四章s o l a p s 的聚集运算。介绍了网内聚集计算的原理和时间调度 方法。给出了本文设计的时间调度时序。由于聚集计算依赖于基于树的 路由方法，本章另外介绍了网络的路由树组织方法和路出树深度求解算 法。 第五章s o l a p s 的操作请求处理策略。介绍了系统的操作请求处理策 黑龙江大学硕士学位论文 略。本章首先给出了操作请求的下发策略，给出了路由树上的层次索引 结构和操作请求的下发词度策略。本章接着给出了本文设计的多粒度数 据存储结构及在其上r o l l u p 和d r i l i d o w n 操作。本章还给出了系统的操 作请求处理的实现方法。 第六章s o l a p s 原型系统的实现。介绍了本文实现的s o l a p s 原型系 统。本章介绍了实现该系统所使用的模拟平台和系统的结构。 最后，给出了本文的结论、不足之处和未来的工作。 第2 章基丁1 传感器网络的联机分析处理系统 第2 章基于传感器网络的联机分析处理系统 2 1s o l a p 的定义 传感器网络节点中依应用的不同，通常会使用很多描述节点位置的 信息。这些信息被用来描述传感器节点采集的感知数据。基于传感器网 络的联机分析处理操作，就是耍利刷描述信息之问的包含笑系进行分层 的聚集，从而达到减少监测操作能量消耗的目的。 设传感器网络的节点上存在一个 立置描述f 割息的属性序列a 、k ， i _ ( a ) 表示属性a ，所覆盖的空| _ 白j 区域，b ，为属性i 的第j 个属性值，n 为属性i 的属性值数。若a 有k 个属性，9 l i _ l 有f ( a ：) 2 u 显( 8 。) ，其中 = 1 r ( b 。) = “，l ，k ) ，其中r 为良所表示的不重叠的独立区域，s ( r ) 为 r ，的尺寸。区域r 与r ( b ，) 的n 操作定义为与r ( b 。) 中各区域的交。如果 由一个不空，则结果不为空。 定义1 若属性序列a 一a 满足以下条件则称这个序列存在层次结 构a 一 一 a 。 1 r ( a ；) 一- = r ( a 0 。 2 v f ，女，r ( b 。) f 1 r ( b ) = m a 3 ， v i ，歹，k ，t t t ，v _ 足( 邑) ，t 蠢( 丑珊) s ( t ) s ( r 2 ) 。 4 v i l ，- 一i ，ls i l i ，t ，l i i 1sk 脚，u r ( 占h - b 机) = i _ ( 彳i ) 。 5 v i l i ，一j 女，_ 1 了所使得j ，r ( b ，) a ，n r ( b b “) 中 r n r ( b h 毛。) 中且著，n r ( b b 机) 中则只存在唯一的 黑龙江大学硕士学位论文 r r ( b h b 肌) 使得r n r 中。 层次结构具有如下三个性质： 性质1 设有层次结构a 一 一 a 。则a ! 一 一 a 。成立。 证明：由定义1 易知凡一 一 a 符合条件1 至4 。只需证明其符合 条件5 。假设a z 一 一 a 。不符合条件5 。则ji ：i 。，j ：j 。，j m 使得 jr ，r er ( e “m ) a r n r ( b 2 一鼠。) 巾a ，n r ( b 2 b “) o 。 则必存在旦h ，b 1 ，使得r n r ( 曰h b 2 。b ，。) o a ，n r ( b u , b 2 ) 中。这与a 一一 一 a 。成立矛盾。 性质2 设有层次结构a i - ) 一 a 。则对任意i a 成立。这个 性质可以使用与性质l 类似的方法证明。 性质3 设有层次结构a 一 一 a 。则对任意i j ，a , - a ，不成立。 证明：由性质2 知，a j - ) a ，成立。则满足条件5 。设r r ( b 。) ，由于 f ( a 。) = r ( a ) ，必存在唯一的r ，b + 使得rnr o 。由条件3 知s ( r ) s ( n ) 。再由条件5 可知， 。易知必存在r ! r ( b 。) 满足屯c _ 。即rnr o ，nnr 。o 。即a i - a ，不满足条件 5 。因此a i - a ，不成立。 对具有这种层次结构的属性序列，传统的数据仓库中的。h 滚( r o l 】 u p ) 和下钻( d r i l ld o w n ) 操作是实用的畔】。由以上定义可以将传感器网络 上的联机分析处理定义如下： 定义2 基于传感器网络的联机分析处理操作，是对传感器网络中某 个具有次结构的属性序列上进行的最高层次上的某个度量的某种聚集操 作，和在这个序列上的系列上滚和下钻操作的操作序列。 第2 章基丁传惑器网络的雌机分忻处理系统 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i ；i i i i i i i i i i i i i ii i i i i i i 传感器描述属性的层次结构描述了各属往所表示的空间区域的一种 相互包含关系，即在层次结构中层次较高的属性的各属性值按层次顺序 的组合所确定空问区域由使用下一层属性的各值对这个序列进行扩展所 确定的各空间区域所组成。下耐通过个例子对其作进一步说明。 设传感器节点中有两个属性a ，a ! ，其各属性值的定义如图2 】。从 图中可以看出属性a ，a j 存在层次结构属性a i - a ? 。在这个层次结构卜作 o l a p 分析首先要算出a ，层次上0 ，l ，2 ，3 这四个区域卜j 的某个度量的某种 聚集值。若对这个层次上的0 区域进行下转，则网络中需要计算a ! 属性 在a 的0 区域上的0 ，1 ，2 ，3 这四个区域的这个度量的聚集值和a ，上的另 外三个区域的聚集值。在这个状态下，若对& 的0 区域进行上操作，则 网络的计算退回a l 层进行计算( 如图2 2 ) 。 dl 23 0 l o l 2 3 23 0 1 0l 23 2 3 ( a ) a ，的属性值分稍( b ) a ：的属性值分却 图2 1a 1 和a 。的属性分布 oi 23 蕾i l ld o w a0 一 属性名n m e a s u r e 聚集函数名( 聚集属性) 2d r i l l d o w n 游标名i w h e r e 属性l = 属性值条件a n d a n d 属性i = 属性值条件 3r o i l u p 游标名i w h e r e 属性1 = 属性值条件a n d a n d 属性净属性值条件 d e f i n e 语句用来定义用户的分析路径。其中的游标名是用户自己定 义的一个路径旬柄( h a n d l e ) ，用户可以利用这个出标名来进行后续的上 滚和下钻操作。h i e r a c h y 子句用来定义用户要分析的属性层次结构。 m e a s u r e 子句用来确定用户所要分析的度量属性如光、温度、声强等等， 聚集函数使用户需要的统计方式如s u m 、a v e r a g e 、m a x 、m i n 等。 d r i l l d o w n 语句用来下发用户的下钻操作。在使用下钻操作时，用 户首先要给出要下钻的游标名。这个游标名必须是由d e f i n e 语句定义过 的。语句中的i 表示用户要下钻到的层次数。下钻时用户还需要给出爱 进行下钻的区域位置。因此在w h e r e 予句中必须给出层次中前i 层的属 性的取值。 r o l l u p 语句与d r i l i d o w n 中各部分表示的意义是相同的，只是 r o l l u p 操作要求所操作的区域已经被下钻。 第2 章塾j 传感器刚络的戕机分惭处理糸统 i i i i i ii i i i i j ；i i 在2 1 巾提到的联机分析处理操作的例子i u 以用以卜的语句表示。 这罩假设用户要查询温度的平均值。 1d e f if l ec u r s o r s a m p 】e q u r s o r hie r a c h ya , - 扎m e a s u r e a v g ( t e m p ) 2d r ill d o w ns a m p l _ e c u v s n r1 w h 。r ea = 0 3 r o l l u ps a m p l o c u i c s o r lw h e r pa = 0 2 3s o l a p 的处理技术 为有效地处理来自用户的联机分析处理请求，大量的技术问题必须被 考虑。在这一节将列举并介绍这些问题。 1 传感器网络中的路由技术 传感器网络是以a dh o c 形式进行组织的。每个节点都要作为路由器 参与数据的传输。早期的a dh o c 路由算法是针对具有较高能力的节点在 移动中进行点对点通信而设计的。“3 “、刚。这些算法主要考虑如何解决移 动环境中的通信问题，对节约能量的问题考虑得很少。由于这些路由算 法要花费很高的代价去维护路由信息，因此大部分不适于被应用在节点 为固定点或移动速度很低，节点能量限制很大的传感器网络中。 为解决将传感器网络中的采样数据进行分布式散列存储的需要”。” ，研究人员在传感器网络中引入了无线a dh o c 网络中的基于地理信息的 路由方法1 。这类方法适合节点进行点对点的通信。但这种方法的个 潜在问题是信息可能需要通过网络中所有的节点才能到达目的地。另外， 这种方法要求节点实时刷新周围节点的位置信息，其能量消耗比较大。 因此这种方法不适用于多点协同进行计算并向s i n k 发送结果的应用。 另外一种比较适用于传感器网络的路由协议是基于树的路出协议 。1 。这种方式的优点是易于控制各节点之间进行协同工作，适合于网络 黑龙江大学硕士学位论文 节点多到一的传输方式。其缺点是对网络的节点失效比较敏感，树的重 构代价比较大。 由用户发出的请求有时值需要传输到网络中的一部分节点。如果将 这种信息对整个网络进行广播必然造成某些节点的不必要的能量损耗。 其解决方法是为属性建立分销式索引，引导数掘的传输方向“。1 。 m a c 层协议对传感器网络通信中的能量消耗也是一个很重要的因素。 传统的8 0 2 1 l 协议面向的是能力较强的节点，对能量限制较大的传感器 节点是不适合的。这个原因导致了专门针对传感器网络的m a c 协议的出 现呜1 。这些协议的特点是让网络中的节点周期性地打开和关闭无线通信 部件，以减少节点能量的消耗。针对特定的计算方式，通过将计算过程 与通信控制相结台，可以更好地节省节点的能量0 1 。 2 联机分析处理的聚集计算技术 联机分析处理中主要的计算技术用束有效地计算出各区域的聚集 值。最简单的方法是将所有的数据集中到一个能力很强的服务器上，利 用现有的数据库系统或数据仓库系统进行计算。这种方法的缺点是网络 中传输的数据量很大。这会导致网络中节点的能量被大量消耗。不仅如 此，网络中大量的数据传输会导致冲突的增加，从而导致计算准确性的 下降。t i n y d b 中使用了一种网内聚集( i n n e t w o r ka g g r e g a t i o n ) 的方 式进行聚集计算”1 。这种方式利用了计算的特点对计算过程进行调度， 更为有效的节省了传感器节点的能量。 3 操作请求处理技术 处理s o l a p 的操作请求需要通过有教的操作处理技术来完成。其中 包括有效地将操作请求下发到相应节点，有效地处理操作请求及有效地 存储聚集的中阳j 结果等多项内容。 联机分析处理要求传感器网络能够有效地将用户一系列的 第2 章基丁传感器网络的暇机分柑干处删系统 d r j d o w n 和r o l 【p 操作下发到网络中相应的一绸节点。这种操作需要 尽量减少下发过程中的数据丢失，将查询尽量准确的下发到相应的节点。 另外，由于这些操作可能会影响网络中l f 在进行的计算，因此对这些操 作的下发也需要进行相应的调度。 参与联机分析处理的节点可能需要计算多个区域的聚集部分值。这 些值需要设计有效的存储结构进行存储。在这种结构之上必须设计有效 的操作方式以便d r j1 l d o w n 和f 0 1 u p 操作的实现。 4 时问同步 为实