（系统工程专业论文）无线传感器数据库中KNN查询算法研究.pdf

中文摘要 有效的查询特定节点q 的k 个最近邻居节点( 即k n n 查询) 是当前无线传 感器数据库空间查询算法的热点之。目前具有代表性的k n n 查询算法主要有 g r t ( g e o r o u t i n gt r e e ) 和1 w q e ( i t i n e r a r y - b a s e dw i n d o wq u e r ye x e c u t i o n ) 查 询算法，前者是基于索引结构的查询算法，后者是非基于索引结构的查询算法。 本文即是在这些思想的引导下展开的，主要研究内容如下： 1 ) 系统阐述了无线传感器技术的发展及k n n 查询算法的主要内容，对基 于索引结构的g r t 和非基于索引结构的i w q e 算法进行详细的介绍。 2 ) 基于索引结构和非基于索引结构的查询算法，提出了混合索引结构的 k n n 查询算法。混合索引结构查询算法的核心思想是利用g p s r 等非索引结构 的位置路由算法转发查询请求至查询点q ，q 收到查询请求后根据k 估计出所需 要查询的半径大小，最后利用基于r t r e e 结构的索引查询算法收集查询半径内 的兴趣节点信息。并在此基础上，对查询半径的估计算法做出了改进，进而提出 一种适用于动态拓扑网络结构的k n n 启发式查询算法。 3 ) 对所提出的算法进行了大量的仿真。仿真结果显示混合索引结构融合了 两种索引结构的优点，达到了降低能耗和提高查询精度的目的。 关键词：无线传感器空间查询k n n 索引结构 a b s t r a c t e f f i c i e n ts e a r c hf o rkn e a r e s tn e i g h b o r st ot h eg i v e np o i n tq ( c a l l e dk n ns e a r c h ) i s a ni m p o r t a n ts p a t i a lq u e r yp r o b l e mi nw i r e l e s ss e n s o rn e t w o r k ( w s n ) r e c e n t l y , t h e t w oo u t s t a n d i n ga l g o r i t h m so fk n ns e a r c ha r eg r t ( g e o r o u t i n gt r e e ) a n dt h e i w q e ( i t i n e r a r y - b a s e dw i n d o wq u e r ye x e c u t i o n ) t h ef o r m e ri sb a s e d o i lt h ei n d e x s n 眦t i u ea n d 也el a t t e ri sn o tb a s e do nt 1 1 ei n d e xs t r u c t u r e t h i st h e s i si sb a s e do nt h e a b o v ei d e a s ，a n dt h em a i nc o n t e n t sa l ea sf o l l o w s ： l1t h ed e v e l o p m e n to fw s n t e c h n o l o g ya n dt h em a i nc o n t e n t so fk n nq u e r y a l g o r i t h ma r es y s t e m a t i c a l l yd i s c u s s e d t h er e s e a r c h e so nt h eg r ta l g o r i t h mb a s e d o ni n d e xs 觚c 扭l r ea n dr w q ea l g o r i t h mb a s e do i ln o n i n d e xa r ei n t r o d u c e di nd e t a i l 2 ) b a s e do nt h e s et w oa l g o r i t h m s ，w ei n t r o d u c eak n nq u e r ya l g o r i t h mw h i c hi s b a s e d0 1 1t h eh y b r i di n d e xs n l l c t l l i - e t h ec o r ei d e ao ft h eh y b r i di n d e xs t r u c t u r ei sa s f o l l o w s ：f i r s t ，t h eq u e r yp a c k a g ei st r a n s f e r r e dt ot h eg i v e np o i n tpu s i n gt h eg p s r g e o g r a p h i cr o u t i n ga l g o r i t h mw h i c hi sn o tb a s e d o nt h ei n d e xs 饥l e t u r e ；s e c o n d , a f t e r r e c e i v i n gt h eq u e r yp a c k a g e ，t h ep o i n tq e s t i m a t et h es e a r c h r a d i u sb a s e do nt h e n u m b e rk ：f i n a l l y , t h ei n t e r e s t i n gd a t aw i t h i nt h es e a r c hr a d i u si sr e t r i e v e du s i n gt h e r - t r e es 仃u c t u r es e a r c ha p p r o a c h w ea l s op r e s e n tak i n do fr a d i u se s t i m a t i o n a l g o r i t h mt oo p t i m i z eq u e r yr a d i u sa n dah e u r i s t i ck n nq u e r ya l g o r i t h mf o rd y n a m i c t o p o l o g ys t r u c t u r ei nm o b i l ew s na p p l i c a t i o t i s 3 ) w ep r o v i d ea ne x t e n s i v ep e r f o r m a n c ee v a l u a t i o no ft h i sa l g o r i t h m ，a n dt h e s i m u l a t i o nr e s u l t ss h o wt h a th y b r i di n d e xs 仇l c t u r ey i e l d sag o o dt r a d e o f fb e t w e e n i n d e xs t r u c t u r ea n dn o n i n d e xs t r u c t u r e , a c h i e v i n gl o we n e r g yc o n s u m p t i o na n dh i g h q u e r ya c c u r a c y 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 p a t i a lq e u r y , k n n ，i n d e xs t r u c t u r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁鲞基堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：鸯，才疑 签字日期：2 。p 7 年6 月2e t 学位论文版权使用授权书 本学位论文作者完全了解墨盗盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：净，才茭 导师签名： 签字目期：2 0 d9 年6 月2 曰签字日期：治、3，墩 乔孑哆 天津大学硕士学位论文 1 1 课题背景 第一章引言 无线传感器网络是集通信，传感器，嵌入式开发等传统技术于一体的网络信 息技术。在美国商业周刊和m r r 技术评论预测未来技术发展的报告中，无线传 感器网络被分别列为2 l 世纪最有影响的2 l 项技术和改变世界的1 0 大技术之一。 最早在美国自然科学基金委员会的推动下，加州大学伯克力分校、麻省理工学院、 康奈尔大学、加州大学洛杉矶分校等学校开始了传感器网络的基础理论和关键技 术的研究；英国、日本、意大利、德国等国家的一些大学和研究机构也纷纷开展 了该领域的研究工作；我国的一些科研院所从2 0 0 0 年起也开始了对传感器网络 的研究圳，影响力较大的有哈尔滨工业大学、清华大学、北京交通大学、浙江大 学、东北大学等。 1 1 1 无线传感器数据库技术研究现状 虽然传感器网络在形式和应用上存在着差异，但均可被看作一个分布式数据 库，并为终端用户提供有效的数据服务。在服务器端，用户发出查询请求，传感 器网络通过相应的路由技术、数据融合技术将用户感兴趣的数据发送给终端用户。 在无线传感器网络系统中，节点技术、基础设施技术、通信协议、数据管理及系 统应用等是目前国内外研究的重点。对于用户，他们最关心的是如何得到有用的 感知数据，因此，传感器网络数据查询处理理论的研究成为其中至关重要的一项 内容。 就传感器网络数据查询处理技术而言，康奈尔大学开发了感知数据查询技术 的c o u g a r 系纠舶。c o u g a r 系统将传感器网络的节点划分为簇，每个簇包含多个 节点，其中一个作为簇首。c o u g a r 系统使用定向扩散路由算法在传感器网络中 传输数据，信息交换的格式为x m l 。 加州大学伯克力分校研究了传感器网络的数据查询技术，提出了实现可动态 调整的连续查询的处理方法，应用数据库技术实现了传感器网络上的数据聚集函 数，提出了在低能源、分布式无线传感器网络环境下实现聚集函数的方法，并研 制了一个感知数据库系统t i n y d b t 3 1 ，该系统虽然在能够对多个查询结果中实施 共享操作，但未从真正意义上实现多查询处理。 第一章引言 加州大学洛杉矶分校采用层次索引和基于小波交换的技术，开发出 d i m e n s i o n s 系统 4 1 。它的设计目标是实现灵活的空域和时域结合的查询。这种查 询的灵活性在于用户可对传感器网络中的数据进行空域和时域的多分辨率的查 询。 国内的哈尔滨工业大学和黑龙江大学在传感器数据管理系统方面展开了研 究工作，提出了以数据为中心的传感器网络的数据模型及系列低能耗的信息查询 算法。对于数据查询过程中存在的具体问题，如查询转发、数据融合和路由协议、 能耗模型、数据采集等研究，虽然国内外专家学者已进行大量的研究工作，但这 些研究尚处于起步阶段，仍存在以下一些问题： 1 ) 虽然上述研究工作取得了一定的进展，且有一定的应用领域，但这些系统都 不是从根本意义上针对传感器数据库空间查询算法而设计的，查询过程未能 很好地解决能量消耗过多的问题。 2 ) 尚未建立针对空间查询的框架体系，在该体系下，应明确系统的主要目标， 如查询准确率、系统响应时间、系统能耗等。 3 )目前的研究工作大多考虑到能量最小化，但是对于节点能量的反馈机制和节 点能量的均衡化方面没有做进一步研究。 4 ) 对查询、融合和路由技术应当统一考虑，建立三者一体的关联机制，对查询 任务的融合和查询数据的融合及查询分发的路由和数据反馈路由结合起来， 形成一个整体。 5 ) 就查询转发而言，在空间查询中，由于查询转发过程中涉及节点空间位置， 所以应建立相应的空间位置路由转发路由体系。 1 1 2 州查询算法研究现状 k n n ( kn e a r e s tn o g h b o r ) 算法属于一种重要的空间数据查询处理算法， 在无线传感器中用于查找指定节点的最近( e u c l i d i a n 距离) k 个邻节点。 目前的k n n 算法主要假设无线传感器节点被部署在一个二维的固定区域内， 并且节点一旦初始化后，往往不再移动或者移动不频繁。在这个区域内，任意节 点都可以通过其它节点自带的g p s 或其它定位技术获得其它节点的位置信息， 并利用该信息通过g p s r 路由算法传播查询信息和收集查询结果。 当前的k n n 算法主要可分为两大类：基于索引结构的k n n 查询算法和非 基于索引结构的k n n 查询算法 基于索引结构的k n n 查询算法：思想主要受g u t t m a n 提出的动态空间查询 的索引结构算法r t r e e t 5 】的启发。r t r e e 是最早用于空间查询的重要算法之一。 r t r e e 解决了古典数据库索引结构算法如哈希表等不能用于多维数据库查询的 天津大学硕士学位论文 问题。1 9 9 5 年，n r o u s s o p o u l o s t 6 】等人基于r - t r e e 的分支定界法 ( b r a n c h a n d b o u n d ) 实现了对指定节点的k 个最近邻节点的查找。m d e m i r b a s 和j w i n t e l 在这基础上发展了适用于无线传感器的全局结构k n n 算法，分别为 p t r e e 7 】和g r t t 8 】( g e o r o u t i n gt r e e ) 。除了r - t r e e 结构，还有基于网格结构的全 局k n n 算法，如j i n g h u a z h u 提出的c ，k n n ( c o n t i n u o u sk - n n ) 【9 】。网格结构 要在节点部署前，进行预先的结构设计，结构在节点开始工作后，不能动态去改 变，稳定性不高，因此没有动态索引结构应用广泛。全局结构k n n 算法不足之 处在于需要较大的存储空间和能耗去建立和维护整个网络的结构。 非基于索引结构的k n n 查询算法是利用r a n g e w i n d o w 查询算法来解决 k n n 问题。它的主要思想是通过估计查询半径，然后对查询半径进行 r a n g e w i n d o w 查询。对于r a n g e w i n d o w 查询，既可采用有结构的方式，也可 以采用无结构的方式，如j w i n t e l 提出的k p t ( 目州p e r i m e t e rt r e e ) 8 】算法就 是利用有结构的方式进行查询。而无结构则对传感器节点采用预定义的查询处理 和数据收集路线的方法，预定义的方式可以有效的减少非k n n 节点集的数据收 集与处理，从而降低网络整体能耗。相关的算法有d i k n n ( d e n s i t y - a w a r ei t i n e r a r y k n n ) 【1 0 1 i k n n ( i t i n e r a r y - b a s e d ) 1 11 , p c i k n n ( p a r a l l e lc o n c e n t r i c c i r c l ei t i n e r a r i e s k n n ) b 2 。非基于索引结构查询的不足在于无法有效的估计出查询半径。如何 有效准确地估计出查询半径对整个查询结果准确性的提高和能耗的降低有着至 关重要的作用。对于当前查询半径估计算法如文献【8 】【】贝0 对能耗过高，而【1 0 】【1 2 】中 的算法则基于节点密度。 1 2 研究工作介绍 随着后p c 时代的来临，普适计算的发展势头迅猛。无线传感器数据库是由 大量小型具有数据采集功能、可无线通信的低成本传感器节点组成的网络，这种 网络系统可以被广泛地应用于国防军事、国家安全、环境监测、智能家居、医疗 卫生、反恐救灾等领域，将会给普适计算技术带来革命性的变革。 无线传感器数据库作为一个全新的研究领域，在基础研究和应用研究方面对 科技工作者提出大量具有挑战性的课题，其中一个重要的研究课题就是无线传感 器数据库的空间查询算法。空间查询算法指通过一定的查询技术收集分布地存储 于传感器数据库中各个节点的数据。如何保证把结果准确、快速地收集上来是当 前研究的基本条件，如何在准确和快速地收集结果的同时，使查询消耗的能量最 小化则是研究的热点。到目前为止，在对无线传感器技术应用的同时，对无线传 感器网络空间查询算法的研究还处于起步阶段。 第一章引言 k n n 查询算法作为空间查询算法的一种，是无线传感器数据库查询技术的。 重要研究方向之一。但是当前大多k n n 算法，仍有许多需要改进的地方。如非 基于索引结构k n n 查询算法中的k b t 算法、d i n n 、i w q e ( i t i n e r a r y - b a s e d w i n d o wq u e r ye x e c u t i o n ) ，i k n n ，p c i k n n 算法等都是基于预估计的查询半径， 进行结构化或无结构的查询，查询半径的精确性直接影响着k n n 处理查询处理 的性能。而当前的半径估计算法有着结果不够精确或耗能过大等问题，仍待解决。 d i n n 和p c i k n n 根据网络的拓扑信息，第一次采用了基于网络节点密度的算法 来估计查询半径，该算法作为首次应用于无线传感器数据库k n n 查询算法的半 径估计上的方法，对当前的研究工作具有启发性作用，但是该算法还是存在一些 不如人意之处，如其估计出来的半径往往小于实际的查询半径，该半径无法包含 所需的结果，会对查询精度造成影响。此外，该半径的估计对网络拓扑信息不敏 感，没有根据多次的查询结果对估计方法进行调整，鲁棒性不强。本研究拟设计 一种基于网络拓扑信息的查询半径估计算法。该算法会根据网络拓扑结构来选择 最优的算法来估计查询半径，从而使结果达到最优。 另外，根据当前的基于索引结构和非基于索引结构的k n n 查询算法，对于 动态拓扑结构的无线传感器数据库，当前的k n n 算法并没有考虑节点的速度对 查询精度和能耗的影响，也没有提出具有针对性的解决方案。本课题拟针对动态 拓扑结构的传感器数据库，提出一种混合性索引结构的查询算法，使其能适应于 具有移动节点的传感器数据库的空间查询。 第三，如何在不影响传感器数据库整体能耗的情况下，提出一种查询时间更 短、查询结果更精确的查询算法也是本文研究的重点。 1 3 论文结构组织 本文结构组织安排如下： 本章介绍了无线传感器数据库技术和k n n 查询算法的研究现状，并针对当 前研究情况的不足，提出了本文拟研究的方向。 第二章介绍了无线传感器的概念和特点，指出当前正在研究的关键技术。对 于其中关键的技术一无线传感器数据库信息查询算法作出详细的介绍。 第三章首先介绍了k n n 查询算法的基本知识，并对当前k n n 查询算法研 究情况进行探讨，并分别描述了基于索引结构和非基于索引结构的k n n 查询算 法。对于非基于索引结构的k n n 查询算法存在的一些不足，如查询半径估计不 够准确，查询与收集阶段算法不易实现等问题，利用网络密度和混合索引结构分 别给出相应的解决方案。至此，就当前k n n 算法无法适用于动态拓扑结构的传 天津大学硕士学位论文 感器数据库等问题，提出一种启发性查询算法。 第四章主要为本文所提出的算法进行评价分析。首先，介绍了所进行仿真的 环境和工具，然后对所需要进行仿真比较的各个指标进行说明。最后，根据各个 不同指标将所提出的算法与当前主流的算法进行比较和分析。 第五章为本论文的工作进行了总结与展望，指出了查询时延长、查询结果不 准确和查询能耗大等诸多所需解决的问题及未来发展的方向，尤其是动态拓扑网 络的不确定性，将成为下一步研究的重点，也是传感器数据能否商业化的重要一 步。 第二章无线传感器数据库中k n n 查询算法研究 第二章无线传感器数据库及空间查询算法的介绍 2 1 无线传感器概念 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 是由大量的传感器节点以 自组网的形式构成的无线网络，其目的是协同地感知、采集和处理网络覆盖区域 中感知对象的信息，这些信息通过蓝牙、射频、红外等无线途径，以多跳的方式 传送到汇聚节点，由汇聚节点同步到互联网与卫星供用户终端检索。如图2 1 1 所示。 图2 1 1 无线传感器网络结构i ”i 汇聚节点( p r o c e s s i n gn o d e ) ：具有较强处理能力、存储能力和通信能力， 可以是具有足够能量供给的传感器基站，也可以是带有无线通信接口的网关，主 要负责无线传感器网络与外部网站的通信连接、数据转发等工作，一般通过c o m 、 u s b 、t c p i p 与外界通信。 无线传感器节点( w i r e l e s ss e n s o rn o d e ) ：相对汇聚节点，处理、存储、通信 能力较弱，能量有限，由传感节点、处理单元、无线收发单元和电源单元等几部 分组成，如图2 1 2 ，主要负责信息采集、节点通信、路由选择等工作。 天津大学硕士学位论文 肾惨军唑_ 产- - 磊a 寸逦擎 能量单元 _ 千 定位系统自供电系统；移动系统 l 。j l ，一，； l a d c - - a n a l o g - t o - d i g i t a lc o n v e r t o l - 模拟数字转换器 图2 1 2 无线传感器网络结构i i 传感器模块用于感知、采集覆盖区域内的信息，并将其转换成数字信号，它 由传感器和模拟数字转换器组成。常用的传感器有温度传感器、光传感器、加速 度传感器、声音传感器、磁力传感器等。根据感兴趣对象的监测对象不同，一个 传感器节点可以配置一个或多个特定的传感器单元：处理器模块用于控制整个传 感器节点的操作，存储和处理自己采集的数据以及其它节点发送来的数据，处理 器模块还需要一个微型嵌入式操作系统，典型的有美国加州大学伯克利分校开发 的t i n y o s 【1 5 】；收发模块用于与邻节点进行通信，收发采集的数据。常用的收发 模块有蓝牙、红外、射频等。能量单元为无线传感器节点提供正常运行所必需的 能量，通常采用微型电池。此外，无线传感器节点还可以选择其它辅助模块，如 定位系统、自供电系统、移动系统等。 2 2 无线传感器网络特点 无线传感器网络主要有以下特点【16 】： 1 ) 分布式。节点间组成的网络是一个分布式的p 2 p 对等网络。网络中没有 严格的控制节点，任意节点的加入或退出都不会影响整个网络的运行，具有很强 的鲁棒性和抗毁性。 2 ) 节点密度大。覆盖区域内的无线传感器节点通常分布的比较密集，利用 节点间的高度连通性来保证网络鲁棒性和抗毁性。 3 ) 数据融合。由于节点密度较高，节点间采集的信息有较大的冗余度，网 络内常使用数据融合方法来减少相同数据的转发，进而降低网络通信负载和能量 消耗。 4 ) 自组织。节点的部署和网络的初始化是一个无人工干预的过程，这要求 节点可以在任何时刻、任何地方快速展开并迅速组网，自我配置和管理。 第二章无线传感器数据库中k n n 查询算法研究 5 ) 节点能力有限。无线传感器节点能力有限主要包括电源能量有限，计算 和存储能力有限及通信能力有限。计算能力和通信能力有限是由于电源能量有限 所造成的，这是因为节点主要采用电池供电，一旦电源耗尽，节点就失去工作能 力，所以节点要求采用低功率的处理器和短距离的信号发射通信模块。 6 ) 多跳性。由于节点通信半径有限，通常只能与它的邻居节点通信，如果 要与通信半径以外的节点通信时，则需要通过中间节点转发，这要求节点既要担 当信息采集的终端角色，也需担当数据转发的路由角色。 由于无线传感器自身的特性，传统的无线通信标准无法满足无线传感器网络 低功耗、低价格、低速率的要求。于是，z i g b e e 联盟与i e e e 8 0 2 1 5 4 工作组决 定合作共同制定一种适合无线传感器网络的通信标准，该协议标准最终被命名为 “z i g b e e ”。z i g b e e 协议栈模型如图2 2 1 所示。 - _ 广_ 应用层 l 堕苎望兰ll 塞竺 用户 传输层传输控制 z i g b e e 联盟 网络层路由 数据链路层厂气菇_ i，。、一j 一 i e e e8 0 2 1 5 4 物理层声、光、电、磁 图2 2 1z i g b e e 协议栈模型1 1 6 i 2 3 无线传感器网络关键技术 无线传感器网络作为当今信息领域新的研究热点，涉及多学科交叉，有许多 关键技术需要去研究和解决，下面仅列举部分与本文相关的关键技术1 1 3 j 6 】。 1 ) 数据查询。无线传感器网络的最终目的是收集在特定区域内用户感兴趣 的信息。如何准确有效地收集兴趣信息是当前研究的热点之一。数据管理包含网 内信息处理和数据管理。 在网内信息处理方面，主要研究数据融合、数据压缩和协作信号信息处理等 模型和算法。数据融合主要是去除冗余数据，尽量减少数据传送量，同时将多份 数据整合起来，抽取较单个节点更为有效准确的信息，最终优化查询结果，降低 能耗，达到延长网络生命周期的目的旧。数据压缩主要用于汇聚节点的邻节点， 天津大学硕士学位论文 邻节点在发送数据到汇聚节点前对数据进行压缩，汇聚节点收到数据后再进行解 压缩处理，这样的目的是降低邻节点的存储空间和减少通信量，有效解决邻节点 能耗过大的问题【1 8 】。协作信号信息处理致力于节点间的协作。通过选择合适的路 由节点，平衡节点和网络动作过程中的信息收益和资源代价【1 9 】。 数据管理包括数据模式、数据存储、数据索引和数据查询。数据模式是对数 据的建模组织方式。目前的传感器网络数据模式主要是在传统的关系模式和时间 序列模式的基础上提出来的。一些研究将感知数据视为分布式数据库，另外一些 研究则采用时间序列模式。本文主要基于前者的研究。数据存储就是存放数据的 方法。数据存储需要根据查询的需求来设计。当前的传感器网络中主要采用两种 数据存储方法。一是本地存储，即将数据存储在本地节点内。另一种是以数据为 中心的存储方法。即将数据存放在特定节点内，如簇首内。数据索引就是根据查 询要求，对传感器节点采取索引结构的方法。常见的索引方法有层次索引、一维 索引和多维索引。数据查询是数据管理中最重要的方法，它是由全局处理器和节 点中的局部处理器共同执行的分布式处理技术。当终端用户提交一个查询时，全 局处理器将查询分成一系列的子查询，根据数据索引方法提交给相应节点由局部 处理器执行，并由特定节点将数据聚集，最终返回给用户。 2 ) 定位技术。在无线传感器网络中，位置信息对传感器网络的监测活动至 关重要，没有位置信息的节点所监测到的信息往往是没有意义的。因此，确定节 点位置是传感器网络最基本的功能之一，对无线传感器网络广泛性应用有着关键 性的作用。 全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) 是目前应用最广泛的定位系 统。通过卫星进节点进行定位具有精度高、实用性好等优点。但由于其在价格、 功耗上的制约使其不易运用于大规模的无线传感器网络。因此，如何确定一种低 功耗、低成本的定位算法成为了当前无线传感器网络研究的热点之一。 当前的定位算法可以归类为： 基于测距的定位算法和测距无关的定位算法。前者主要根据测量得到的 距离和角度信息进行位置计算，如基于到达角度的a p s 算法( a dh o c p o s i t i o n i n gs y s t e m ) 【2 0 】。后者指利用节点连通性和多跳性等方法来估计 节点距离和角度并完成位置计算，如b u l u s u 等人提出的质心算法 ( c e n t r o i da l g o r i t h m ) 1 2 1 。 基于导标节点( b e a c o n b a s e d ) 的定位算法和无导标节点的定位算法。 前者以导标节点( 一般由装备g p s 设备担任) 作为定位的参考点，节点定 位后产生绝对位置坐标，常见的算法有质心算法；后者以节点自身作为 参考点，将邻节点纳入自己的坐标系中，最后产生整体相对坐标系统， 第二章无线传感器数据库中k n n 查询算法研究 典型的算法有a b c ( a s s u m 叫o nb a s e dc o o r d i n a t e s ) 2 2 1 。 3 ) 开发与应用1 1 3 】。传感器开发应在为系统的应用开发提供有效的软件开发 平台和软件工具，需要解决的问题包括传感器网络程序设计语言，传感器网络程 序设计方法学，传感器网络软件开发环境和工具，传感器网络软件测试工具的研 究，面向应用的系统服务，基于感知数据的理解、决策和举动的理论与技术。应 用主要研究是各种传感器网络应用系统的开发和多任务之间的协调，如医疗系统 c o d e b l u e 2 3 ，环境监控g r e a t ed u c ki s l a n d 2 4 ，智能系统s m a r tk i n d e r g a r t e n 2 扪。 2 4 空间查询算法 2 4 1 无线传感器数据库 因为分布于覆盖区域内的每个传感器节点都有独自数据存储的功能，所以整 个无线传感器网络系统可被看作一个分布式的数据库。把无线传感器网络当作分 布式数据库来研究的目的是把传感器网络中的数据逻辑视图( 命名、访问、操作) 从物理网络分离出来，使终端用户只需发出简单的查询语言，如s q l ，传感器 网络就能通过相应的路由技术将用户感兴趣的数据传回终端。 由于传感器网络自身的特性，无线传感器数据库跟传统的分布式数据有着显 著的差异。首先，传感器网络极其不稳定，节点可能会失效，通信数据包可能会 丢失。在传统分布式数据库中，数据的查询处理不必关心网络的细节，在传感器 数据库中，数据的查询处理与传感器网络紧密相关，需要各个节点的相互配合。 其次，传感器节点产生的测量值多数具有误差。这些误差主要来自节点和信 号的干扰，通常基于离散概率函数。所以，在无线传感器网络中，r a n g e 查询， n e a r e s tn e i g h b o r 查询和a p p r o x i m a t e 查询比精确查询更合适f 1 3 瑚】。 第三，传感器节点的通信能力、处理存储能力、能量有限。传感器数据的查 询应以低能耗为主，减少传输的数据量，从而延长传感器网络的生命周期。 目前具有代表性的无线传感器数据系统主要有t i n y d b ，c o u g a r 2 7 1 ， d i m e n s i o n s 。本文主要介绍t i n y d b 系统。 t i n y d b t 】系统是加州大学伯克利分校开发的传感器网络数据管理系统，它 为用户提供一个类s q l 的应用程序接 2 1 。t m v d b 系统主要由客户端、服务器和 传感器网络组成。如2 4 1 1 图所示。 天津大学硕士学位论文 * 8 圈2 4 1 1t i n y d b 系统结构图 传感器网络软件安装于监测区域内的节点里，它能识别t i n y d b 服务器发送 过来的查询命夸，并返回指定节点所收集的信息。服务器软件把所收集上来的节 点信息存储于自带的数据库内。客户端a p i 主要负责解析自定义的s q l 类型语 言并提供应用程序开发接口。 t m y d b 采用路由树机制收集* 趣信息。网络中每个传感器节点都维护一个 邻居节点表t 并选择离根节点网络距离最小的邻节点作为父节点，查询请求是从 根结点向叶子节点运级传播的，而数据由叶节点向根点向上运级传播。如图 2 4 12 所示。 第 层 第 层 第 层 第 凹 一_ 警_ 叠_ 啊 时f 目 圈2 4 12t i u y d b 数据采集” 监听和接收 采集币i 处 传送数据 厂i 一 树晌淋噬 第二章无线传感器数据库中k n n 查询算法研究 2 4 2 空间查询算法 由于传感器节点通常部署于三维的监测空间感知和采集信息，这些节点可以 通过定位设备，如g p s ，或其它定位算法来获得自身位置信息，所以，传感器数 据库可以看作是一个空阔数据库。空间查询算法泛指针对节点位置信息面发起的 查询算法。当前，基于传感器数据库研究的空间查询算法有r a n g e 查询( 查找指 定范围区域内的节点) ，k n n ( 查找指定节点的k 个最近邻节点) 等。 r a n g e 查询在传感器数据库中运用的特别广泛。如在火灾监控中，消防队员 可以通过传感器节点判断是否每层楼的温度都高于1 0 0 度。现在并没有有效的查 询机制支持r a n g e 查询。t i n y d b 技术r a n g e 查询，但由于t i n y d b 路由树机制对 监测区域进行洪泛( f l o o d i n g ) 查询，这样的查询方法不仅会造成过多能量的浪 费，而且还会引起串音，增加丢包率，影响查询速度和查询精度。 k n n 查询是空间查询的热点之一。在火灾监控中，消防队员可以通过k n n 查找离自己最近的k 个未着火的安全门。k n n 查询比r a n g e 查询更为复杂，因 为在r a n g e 查询中，节点不需要去考虑其它节点的情况。而对于k n n ，节点必 须知道其它节点的情况，才能确定自己是否是k 个邻节点之一。k n n 查询是空 间查询的关键技术之一。它很容易扩展为其它重要的n n 查询算法。如： c n n ( c o n s t r a i n e dn e a r e s tn e i g h b o r ) 【2 9 1 。与k n n 查询不同的是，c n n 只关 心特定条件内的最近邻节点。如，查找指定节点东南方向的最近邻节点。c n n 查询算法可以看作是k n n 与r a n g e 查询算法的结合。 r k n n ( r e v e r s ekn e a r e s tn e i g h b o r ) 。r k n n 与k n n 正好相反，r k n n 查询 用于查找出给定节点集中特定节点，使其它节点为所找特定节点的k 个最近邻 节点。r k n n 查询算法可以运用于查找基站或簇首最合适的位置。 2 5 本章小结 本章主要对无线传感器网络作了全面的介绍，详细阐述了无线传感器网络 与传统网络架构的不同和并针对无线传感器网络提出的关键技术。 在如何有效收集无线传感器网络信息这个问题上，本文引入了无线传感器 数据库这一概念，并列出当前基于无线传感器网络数据库空间查询算法的热门 研究方向。在接下来的章节，将要针对当前主要的空间查询算法k n n 查询进行 更深入的研究，这些研究有当前k n n 查询算法前沿的研究，也有自己针对k n n 查询算法的一些改进和优化。 天津大学硕士学位论文 3 1 基本概念 第三章混合索引结构的k n n 查询 k n n 查询算法是最重要的空间查询算法之一【3 0 】【3 1 】【】【1 0 】【3 1 】【1 2 1 。k n n 可以定义 如下： 定义( k n e a r e s tn e i g h b o r ) 1 i 】。对于一个特定的传感器节点集s ( is i - n ) 和特定的物理位置节点( 用口表示) ，找出k 个节点的传感器节点子集 s ( st cs ，庭，使对于v 行l s 和v n 2 s - s ，满足d i s t ( n l ，q ) 5 时，确定节点d 到目标节点的距离为所估计的查询半径，所以， 图中所得查询半径为d i s t ( d ，h ) 。但是，n e i g h b o r c l a s s 2 不能保证所估计的查 询半径是否足够大，以至能把与目标节点最近的k 个邻节点都包含进来。 3 3 3 查询半径内的查询与收集阶段 节点在所估计的k n n 查询半径内传播查询请求采集信息。查询半径内的节 点在收到查询请求后，便根据查询请求返回自己采集的信息。当查询半径内所有 节点都己收到查询请求时，整个k n n 查询停止。 第三章混合索引结构的k n n 查询 o o o o o o 半径区域 o 僦o o o ( a ) 树结构查询( b ) 簇结构查询( c ) i w q e 查询 图3 3 3 1 查询与收集阶段方法 区域 。 查询与收集阶段方法有基于索引结构的查询和非基于索引结构的查询。基于 索引结构的查询有树查询方法，如图3 3 3 ，l ( a ) 和簇结构查询方法，如图3 3 3 1 ( b ) 。基于索引结构的查询需要大量空间和计算能力去维护索引结构，不适用于 动态拓扑结构的查询。非基于索引结构的查询方法如洪泛查询，虽然不需要去维 护索引结构，适合性也很强，但会消耗过多的能量。 文献 3 4 1 中，提出来i w q e ( i t i n e r a r y b a s e dw i n d o wq u e r ye x e c u t i o n ) 方法来 采集估计半径内的信息。它假设查询半径为二维的矩阵，查询方法为快照查询， 即只采集一次样本信息。为了减少对多余节点的访问，i w q e 采用了位置路由算 法( g e o - r o u t i n g ，如g p s r ) 。在查询半径内，它选择部分节点作为查询节点，即 主要用于传输查询请求，当查询节点收到查询请求时，节点向自己的通信区域邻 节点广播该请求，邻节点收到请求后，立刻返回所采集的信息。返回信息的节点 被称为数据节点。当查询节点收到它所有数据节点的信息后，便将信息与查询请 求发送到下一跳查询节点。 图3 3 3 2i w q e 查询路由实际路线与理想路线对比 天津大学硕士学位论文 在实际的传感器数据库中，由于传感器网络的动态拓扑性，i w q e 查询的实际路 线往往与理想路线有差别，如图3 3 3 2 所示，实际路线如果过度偏离理想路线， 不但可能会导致查询失控，无法停止于所估计的查询半径内，达不到降低能耗的 目标，而且会影响查询结果。为了避免实际路线与理想路线带来负面的影响，查 询路由必须解决好查询路由半径和查询路由线路这两个问题。在i w q e 中，查询 压 路由半径为旦天，如图3 2 3 3 ，相关推理与证明查阅文献 3 4 1 1 3 s 】。 路线宽度= 塑胄 2 图3 3 3 3i w q e 查询路由半径 查询路线结构有文献【3 4 】中i w q e 使用的线性查询路线，并行查询路线和混合 查询路线，如图3 3 3 4 所示。 l ( a ) 线性查询路线( b ) 并行查询路线( c ) 混合查询路线 图3 3 3 4 查询路线结构 此外，还有文献1 1 提出的螺旋形查询结构和p c i k n n f l 2 1 采用并行周轴查询结 构。由前文可知，查询路线结构安排对k n n 查询算法性能有显著的影响。过长 的查询路线结构容易引起查询迟延和能耗过多。因此，多个线程同步查询路线是 当前非基于索引结构k n n 算法的研究关键。 第三章混合索引结构的k n n 查询 3 4 基于网络密度混合索引结构的k n n 查询算法 本节根据基于索引结构k n n 查询算法和非基于索引结构的k n n 查询算法， 提出基于网络密度混合索引结构的k n n 查询算法。在路由阶段利用非基于索引 结构对查询请求进行转发，在查询半径估计阶段，提出一种基于传感器网络密度 的半径估计优化算法，并对路由阶段做出修改，使其适用于基于网络密度的半径 估计算法。在查询与收集阶段，根据r t r e e 结构，提出基于索引结构查询与收 集算法。下文为所改进算法的详细描述。 3 4 1 基于网络密度非索引的路由阶段 基于网络密度的路由阶段主要利用非基于索引结构中的位置路由算法将查 询请求转发到特定节点q 中，除此，该阶段还需要为查询半径估计阶段收集所需 的信息，供其使用。这是因为在不依靠索引结构的条件下，估计出k n n 的查询 半径是非基于索引结构的k n n 查询算法的关键与难点。本文提出的半径估计算 法基于传感器网络的密度，大量仿真结果显示，对于节点均匀分布的传感器网络， 基于密度的估计方法能取得更优网络性能。 该阶段的基于算法思想如下，节点收到查询请求后，查询自己的邻节点是否 存在有比自己与特定节点q 欧氏距离更小的节点，如果存在，便向该邻居节点转 发请求，如果没有便以左手定理转发查询请求，同时计算自己的邻节点数和当前 的跳数，并将自己的邻居节点数与所收到的累加起来，与查询请求一起发送给下 一个节点。当特定节点q 收到查询请求时，可得网络密度为 ，、 节点数所收到的邻居节点数 覆瓢百赢砭菊丽。 3 4 2 基于网络密度k n n 半径估计阶段 特定节点q 收到七个最近邻节点的查询请求后，由基于密度的查询半径