无线传感器网络中自适应数据存储与kNN查询处理研究

论文摘要

无线传感器网络（简称WSNs）由于其潜在、广阔的应用前景成为微电子、通信、网络与数据库等领域的研究热点。它集感知、计算和无线通信为一体,将各类微型传感器产生的感知数据处理后传送至用户。对于用户而言,其所关心的是感知数据,而不是传感器节点本身及其构成的网络。因此,数据存储和查询处理是无线传感器网络研究中首要解决的问题。目前学术界在这方面已取得了不少研究成果,但仍存在着诸多有待研究和解决的问题。本文围绕无线传感器网络以数据为中心这一主线,对无线传感器网络中的自适应数据存储和基于值的kNN查询处理进行了研究。无线传感器网络中的自适应数据存储主要研究如何确定感知数据的存储位置并将数据存储于此,以便查询请求高效节能地访问到相关数据。本质上这是一个信息中介过程:生产者（即收集感知数据并将数据注入到网络中的传感器节点）将感知数据按照某种策略存储在特定位置,而消费者（查询请求发起点,可能是基站、用户或传感器节点）将查询请求路由到相关数据的存储节点,后者将满足查询条件的结果返回给消费者。无线传感器网络中基于值的kNN查询处理主要研究如何在传感器网络中查找出与给定查询值最接近的k个值。这要求在异构、不可靠的传感器网络中实现高效、可靠的网内查询处理,并且能够充分利用节点有限的资源,实时地为用户返回给定查询值的最近邻。本文主要贡献如下:1.提出了无线传感器网络中面向单一存储节点的自适应数据存储策略。现有的工作要么只考虑生产者和消费者的地理位置,要么只考虑数据速率,很少将二者有机结合起来,并且数据存储的位置没有自适应地动态变化来减少存取过程中的能量消耗。本文依据生产者和消费者的数据速率及地理位置来动态地调整数据的存储位置,以减少数据存取时的能量消耗。将网络中的数据存取依据生产者和消费者的关系建模为“一对一”模型（一个生产者,一个消费者）、“多对一”模型（多个生产者,一个消费者）和“多对多”模型（多个生产者,多个消费者）。基于上述模型提出了两种利用数据速率和地理位置来确定数据存储位置的方法:一种是求解全局最优数据存储位置的方法（ODS）;另一种是求解局部最优存储位置的方法（NDS）。此外,用整型规划给出最优数据传输模式（ODTS）。实验结果显示:相对ODS而言,NDS大大减少了计算复杂性,只需要ODS 5%的计算代价就能在70%的情况下达到相同的效果,而且访问延迟几乎相同。2.研究了无线传感器网络中面向多个存储节点的自适应数据存储,给出了树状拓扑结构网络中数据存储节点的最优位置,提出了一种面向网状拓扑结构的基于聚类的分布式自适应数据存储策略（CBDS）,并实现了三种基于聚类的数据存储算法。与现有的工作相比,我们首次利用聚类技术在无线传感器网络中实现了分布式数据存储,其核心旨在减少数据存储过程中的能量消耗,延长网络的生命周期。首先,结合数据速率和地理位置信息分析了数据存储的相关代价,将集中式存储、本地存储和分布式存储归结为统一的存储模型。其次,对在树状拓扑结构中如何依据数据速率选择数据存储位置进行了理论分析。再次,在网状拓扑结构中,通过引入传感器节点图、数据存储节点图及有效划分等概念,将数据存储节点选择问题转化为传感器节点聚类问题,继而提出了一种基于聚类的分布式数据存储策略（CBDS）,实现了三种基于聚类的数据存储方法。大量实验结果显示:较于以前的数据存储策略,CBDS极大地减少了能量消耗,延长了网络的生命周期,同时也降低了访问延迟。3.研究了无线传感器网络中基于值的kNN查询处理,提出了快照型和连续型kNN查询的计算方法。此前相关工作绝大多数集中于基于位置的kNN查询处理,尚未对快照型基于值的kNN查询提出有效的解决办法。本文在描述无线传感器网络中kNN查询的基础上,提出了h-kNN、f-kNN和c-kNN三种基于值的kNN查询处理方法。针对快照型kNN查询,提出了一种值空间映射方法h-kNN,其利用值关系保持的哈希函数,将值相近的数据存储在相同或相邻的节点,以便查询时对查询值也采用同样映射后在小范围内搜寻即可获得结果。针对连续型kNN查询,提出了f-kNN和c-kNN两种计算方法。f-kNN是基于过滤器的计算方法,其通过在每个节点设置过滤器使得对结果毫无贡献的数据不进行传送;c-kNN是基于聚类的计算方法,其依据感知数据的时空相关性并利用聚类方法将值相近且位置相邻的感知数据存储在某些固定节点以便查询。实验结果显示:无论在何种分布的数据上,h-kNN、f-kNN或c-kNN三种方法所消耗的能量均少于基本方法（Naive）。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 无线传感器网络简介
• 1.1.2 无线传感器网络中数据存储与查询处理
• 1.1.3 无线传感器网络中数据存储与查询处理面临的挑战
• 1.1.4 无线传感器网络中数据存储与查询处理性能评价
• 1.2 本文工作
• 1.2.1 面向单一存储节点的自适应数据存储
• 1.2.2 面向多个存储节点的自适应数据存储
• 1.2.3 基于值的kNN查询处理
• 1.3 本文结构
• 第二章 相关工作
• 2.1 无线传感器网络中的数据存储
• 2.1.1 集中式存储
• 2.1.2 本地存储
• 2.1.3 分布式存储
• 2.1.4 传感器网络数据库
• 2.1.5 近似代价分析
• 2.2 无线传感器网络分布式数据存储技术
• 2.2.1 分布式数据存储分类
• 2.2.2 分布式数据存储分析
• 2.2.3 分布式数据存储总结
• 2.3 无线传感器网络中查询处理
• 2.3.1 查询处理概述
• 2.3.2 查询的表示方法和分类
• 2.3.3 查询处理模型
• 2.3.4 查询处理过程及优化
• 2.3.5 查询处理总结
• 2.4 小结
• 第三章 面向单一存储节点的自适应数据存储
• 3.1 引言
• 3.2 问题描述
• 3.2.1 预备知识
• 3.2.2 问题描述
• 3.3 数据存储模型
• 3.3.1 "一对一"模型
• 3.3.2 "多对一"模型
• 3.3.3 "多对多"模型
• 3.3.3.1 线形拓扑结构
• 3.3.3.2 格状拓扑结构
• 3.3.3.3 网状拓扑结构
• 3.4 存储方法
• 3.4.1 最优数据存储（ODS）
• 3.4.1.1 线形网络中最优数据存储（ODS-Linear）
• 3.4.1.2 格状网络中最优数据存储（ODS-Grid）
• 3.4.1.3 网状网络中最优数据存储（ODS-Mesh）
• 3.4.2 近似最优数据存储（NDS）
• 3.4.3 最优数据传输模式（ODTS）
• 3.5 实验和结果分析
• 3.5.1 简单情形
• 3.5.2 一般情形
• 3.6 小结
• 第四章 面向多个存储节点的自适应数据存储
• 4.1 引言
• 4.2 问题描述
• 4.2.1 问题描述
• 4.2.2 代价模型
• 4.3 树状拓扑结构中数据存储模型
• 4.3.1 数据存储模型
• 4.3.2 理论分析
• 4.4 网状拓扑结构中数据存储模型
• 4.4.1 数据存储模型
• 4.4.2 存储方法
• 4.4.2.1 基于聚类的数据存储方法一（CBDS-Ⅰ）
• 4.4.2.2 基于聚类的数据存储方法二（CBDS-Ⅱ）
• 4.4.2.3 基于聚类的数据存储方法三（CBDS-Ⅲ）
• 4.5 实验和结果分析
• 4.6 小结
• 第五章 基于值的kNN查询处理
• 5.1 引言
• 5.2 问题描述
• 5.3 快照型kNN查询处理
• 5.3.1 基本的kNN计算方法（Naive）
• 5.3.2 基于值映射的计算方法（h-kNN）
• 5.3.2.1 基本原理
• 5.3.2.2 数据存储
• 5.3.2.3 查询处理
• 5.4 连续型kNN查询处理
• 5.4.1 基于过滤器的计算方法（f-kNN）
• 5.4.1.1 基本原理
• 5.4.1.2 过滤器设置
• 5.4.1.3 查询处理
• 5.4.2 基于聚类的计算方法（c-kNN）
• 5.4.2.1 基本原理
• 5.4.2.2 数据存储
• 5.4.2.3 查询处理
• 5.5 实验和结果分析
• 5.5.1 快照型kNN查询
• 5.5.2 连续型kNN查询
• 5.6 小结
• 第六章 总结与展望
• 6.1 本文工作总结
• 6.2 未来工作展望
• 参考文献
• 发表/录用论文
• 已投稿论文
• 博士期间参与的科研项目
• 致谢