1、 硕 士 学 位 论 文 中文题目： WSN 中基于几何学的分布式轮廓查询方法研究 Research on the Geometry-Based Distributed Skyline 英文题目： Query Method in WSN 论文作者： 指导教师： 专 业： 计算机软件与理论 完成时间： 摘 要 I 摘 要 近年来，环境污染、空气质量问题得到日益关注，结合实际情况，实现无线传感器网络的价值越来越得到人们的关注。 基于无线传感器网络的轮廓查询策略已经 得到 广泛应用 ，尤其 在环境检测等领域 的查询 ， 而 这些 应用 领域多数涉及到空间距离问题。由于空间位置的多维性，给一般的轮廓查
2、询策略在属性计算方面带来巨大的计算代价。为提高传感器能量的高效利用，对基于空间距离上的轮廓查询需要新的解决策略 ，为此本文提出一种基于几何学的分布式轮廓查询 方法 （ GDSky）。 本文首先采用几何学的方法将整个查询区域 划分 ，以便在 各个子区域之间可以进行区域间支配关系的判定 ，本文采用 基于凸包顶点的轮廓区域削减 方法，可以 快速查找 到 与特定查询区域相关的空间轮廓数据，减少了节点间比较次数 。提出了基于三角剖分法的区域划分策略，该方法是将用户指定的查询区域划分为若干个子区域，使得查询在各个子区域间可以进行分布式进行。设计了一种子区域内分簇的策略，对一个子区域内的数据分簇，以进行轮廓
3、的并行查询，节省时间。为了 遍历 到 所有相邻的传感器检 测地点， 削减掉在空间距离上被支配的节点，本文提出了 基于数据节点树的分布式查询策略 ，并利用非空间的轮廓查询方法，对已获得空间轮廓的非空间属性进行一般轮廓查询，与此同时，对剩余的未找到的空间轮廓数据进行空间轮廓查询 ， 从而实现并行执行。最后，本文还 提出 了 子区域间削减 策略，可以削减掉被支配的一个子区域内所有节点，以及 子区域内部削减策略 ，可以削减掉一个子区域内某些被支配的节点，减少网络中数据的传输消耗 。 大量仿真实验的结果表明， 本文提出的 GDSky 方法 可以 较快速的查询到 距离查询地点较近且污染力较大的地点， 可以
4、高效减少 数据间支配比较次数，降低传感器节点的能量 消耗 ，提高查询效率 。 关键词 ： 无线传感器网络 ， 环境监测 ， 分布式轮廓查询 ， 凸包 ， 削减Abstract III ABSTRACT In recent years, environmental pollution and the quality problem of the air get the increasing attention. According to the actual situation, to realize the value of the wireless sensor network gets m
5、ore and more concern. The skyline query strategies in wireless sensor networks have been widely used in the field of environmental detection, and these areas mostly are related to the spatial distance problem. Since the multi-dimensional of the spatial position, it brings the enormous computational
6、cost for the general skyline query strategy with the aspect of the attribute calculation. In order to improve the efficient use of sensor energy, it needs a new query strategy to solve the skyline query on the spatial distance. This paper proposes a method of the geometry-based distributed skyline q
7、uery (GDSky). The specific work is as follows. This paper uses the method of the geometry-based region partition to divide the whole query region into several sub-regions, so that it can determine the dominance relationship between sub-regions. This paper proposes a method of cut of the skyline area
8、 based on the convex hull vertices, which can quickly find the spatial skyline data with respect of a specific query area, and reduce the comparison times between nodes. This paper adopts the regional partition based on the triangulation method which divides the query region into several sub-regions
9、. So it can carry out a distributed query in each sub-region. The paper also designs the clustering strategy in one sub-region, which can cluster on the data within a sub-region in order to query the skyline in parallel and save time. Besides, in order to traverse all the neighbor sensor detective l
10、ocations, and cut the nodes which are dominated on the spatial distance. the paper also proposes the distributed query strategy based on the data node tree. To carry out the general skyline query on the non-spatial properties of the obtained spatial skyline， the paper also puts forward the non-spati
11、al skyline query method. At the same time, the strategy conducts the spatial skyline query on the remaining spatial skyline data so as to realize the parallel execution. This paper presents the cut strategy among the sub-regional, which can cut all dominated nodes in one sub-region. And Abstract IV
12、also puts forward the cut strategy in a sub-region, which can cut some dominated nodes in a sub-region and reduce the data communication in the network. Simulation results show that the method GDSky proposed in this paper can quickly find the places which are near to the query locations and have the
13、 larger pollution energy. The method also can efficiently reduce the times of comparison between data, improve the query efficiency, and reduce the energy consumption of sensor node. Key Words: wireless sensor network, environmental monitoring, distributed skyline query, convex hull, cutting node 目
14、录 V 目 录 第 1 章 引 言 . 1 1.1 研究背景 . 1 1.1.1 环境质量监测概述 . 1 1.1.2 环境监测特点及需求 . 2 1.2 研究现状 . 5 1.2.1 无线传感器网络在环境监测中的应用 . 5 1.2.2 无线传感器网络的查询特点 . 6 1.3 问 题的提出 . 8 第 2 章 轮廓查询 .10 2.1 轮廓查询 . 11 2.2 典型的轮廓查询方法 . 12 2.2.1 基于非空间的轮廓查询 方法 . 12 2.2.2 基于空间的轮廓查询方法 . 13 2.3 本章小节 . 15 第 3 章 基于几何学的空间轮廓查询 .17 3.1 基于传感器部署的 区域
15、划分 . 17 3.1.1 Voronoi 图 . 18 3.1.2 Delaunay 图 . 18 3.1.3 区域划分策略 . 19 3.2 基于凸包顶点的轮廓区域削减 . 20 3.2.1 凸包 . 21 3.2.2 空间 轮廓区域的削减 方法 . 23 3.3 空间 轮廓区域的削减 方法过程 . 28 目 录 VI 3.4 本章小节 . 29 第 4 章 分布式轮廓查询 .30 4.1 区域划分 . 30 4.1.1 基于三角剖分法的区域划分 . 30 4.1.2 子区域内分簇 . 32 4.2 分布式区域查询 . 34 4.2.1 子区域内并行查询 . 34 4.2.2 区域间查询结
16、果合并 . 38 4.3 基于几何学的分布式轮廓查询方法 . 40 4.4 本章小节 . 41 第 5 章 实验与分析 .43 5.1 实验环境配置 . 43 5.1.1 实验环境及方案 . 43 5.1.2 实验数据集 . 43 5.2 实验结果与分析 . 44 5.3 本章小结 . 49 第 6 章 总结与展望 .50 6.1 总结 . 50 6.2 展望 . 51 致 谢 .52 参考文献 .53 攻读学位期间发表的学术论文及参加科研情况 .56 图表目录 VII 图 表 目 录 图目录 图 1-1 某城市内居民区及其附近概况图 . 4 图 2-1 Skyline 选择宾馆例子 . 11
17、 图 2-2 节点间支配关系 . 14 图 3-1 查询区域示意图 . 17 图 3-2 Voronoi图 . 18 图 3-3 Delaunay 图 . 19 图 3-4 基于 Voronoi图的区域划分 . 19 图 3-5 查询区域划分后抽象图 . 20 图 3-6 凸包示意图 . 21 图 3-7 基于凸包顶点的轮廓区域的确定 . 24 图 3-8 轮廓区域 削减结果 . 25 图 3-9 传感器节点中地理信息 . 27 图 3-10 单调函数排序示意图 . 27 图 3-11 空间轮廓区域的削减过程 . 28 图 4-1 一个简单多边形 的 一 种 三角剖分 . 31 图 4-2 查
18、询区域 三角剖分示意图 . 32 图 4-3 分簇结构 . 33 图 4-4 子区域内分簇 . 33 图 4-5 数据节点树 T . 35 图 4-6 子区域内轮廓数据回收 . 37 图 4-7 各子区域内轮廓查询结果 . 37 图 4-8 子区域的削减 . 39 图 4-9 轮廓查询最终结果 . 40 图 5-1 数据节点数与支配比较次数 . 44 图 5-2 查询节点数与支配比较次数 . 45 图表目录 VIII 图 5-3 传感器能量消耗 . 46 图 5-4 查询节点数与响应时间 . 47 图 5-5 执行效率百分比 . 48 图 5-6 数据节点数 与 合并 时间 . 48 表目录
19、表 4-1 数据元组的格式 . 38 表 4-2 簇头节点 S1 的数据表 . 40 表 4-3 簇头节点 S1的数据表 . 40 表 5-1 实验参数 . 44第 1 章 引 言 1 第 1 章 引 言 1.1 研究背景 随着全球各个国家对环境保护问题的日益关注，人类有必要将智慧投入到环境保护问题上，当“雾霾”一词走进人类的生活当中，人类更加意识到科学发展才是硬道理，有些地方的发展是以环境质量为代价来获得经济的快速发展，这样的发展方式并非是科学有效的。我国已经出台了多项方针政策来应对环保问题，而更加科学、创新的新思想新技术是解决实 际问题的关键所在。 1.1.1 环境质量监测概述 近些年越来
20、越多的环境污染问题受到关注，如空气质量 1，水资源污染，电力设备辐射，噪声污染等。就空气质量检测情况来说， 从上世纪开始，欧美等发达国家和地区的研究者就对空气质量监测网络进行了大量研究，他们对于的设计标准就是快速便捷、灵活有效、针对性强。为了满足城镇化发展的需求，我国也出台了大量的方针政策来完善环境空气质量监测方法，但是，仍然缺乏满足特殊条件的监控条件更为细致的创新方法，对于监测网络设计方面的研究有待发展，尤其是针对特殊人群要求的监测网络的设计，更 应该投入更多的科学研究。 1) 国外情况 在 美国 ，按照行政级别分为国家级的监测站以及各州及地方监测站，通常对各种污染物的监测是分开的 2。这种监测方法存在一些特点，首先是监测的范围较广，环境监控中心通常是将监测站设置在大型城市及周边地区，从而来监测该地区的空气质量水平；其次是监测站的数量少，由于美国人口稀少，通常将监测站设置于大城市周边，这是因为大城市通常是污染较为严重的地区，通过这种方法就可以了解到整个州的空气污染情况。再次，为了保证污染物的能够得到充分扩散，监测点通常需要安放在距离污染源有一定距离的位置。 在 欧 洲 地区 ， 通常将监测站设置在大城市的附近，监测的是整个地区的平均空气质量水平 ，根据具体的实际情况，采用不同的设计原则来规划监测站的
