苏ICP备112451047180号-6
基于物联网的大数据top-k查询算法实现
摘 要 随着传感器技术、无线通信等技术的迅速发展，物联网已成为继计算机、互联网及移动通信网后的新的信息产业浪潮。无处不在的数据感知促使基于物联网的数据大量产生，在物联网大数据背景下，数据高效处理和信息检索成为主要研究重点和热点。
作为一个重要的数据处理及信息检索类型，top-k查询在物联网背景中（尤其是在无线传感网领域中）具有非常广泛的应用，如环境污染监测、智能交通、目标跟踪等。然而，在新兴的物联网中，由于大量用户可以直接在物理世界中搜索信息，因此给top-k查询处理带来了许多新的挑战。一方面，从用户的角度来看，用户可以请求不同的信息集，具有不同的优先级和不同的时间。因此，top-k搜索不仅应该是多维度的，而且还要跨越时域。另一方面，从系统的角度来看，数据采集通常由小型传感装置进行。与在网络空间中搜索的数据中心不同，这些设备通常资源受限，系统效率至关重要。
针对以上两大挑战，本文设计了了一个同时满足用户及系统两方面需求的多维top-k查询算法。其主要思想在于先由各节点将自身潜在top-k感知数据点发送给上层节点，由上层节点进行数据融合，再将融合结果发送给其父节点直至基站，最后根据用户不同查询偏好，由基站查找真实top-k结果。在整个过程中，本文分别基于支配图、最短路径树对单节点、多节点进行高效的数据查询和融合。特别地，为进一步减少连续top-k查询带来的巨大通信开销，本文基于过滤思想设计了有效的filter构建算法。
最后，基于随机生成的数据集，我们对本文提出的top-k查询算法进行仿真分析。实验中主要从网络能量消耗、查询时间及网络寿命三方面进行性能评估，结果表明，本文算法能量消耗在传感器节点可承受范围内，查询时间较短，网络寿命较长。
关键词 top-k查询 多维top-k算法 支配图 最短路径树 能源效率
Realization of top-k query algorithm based on large data of Internet of Things
ABSTRACT With the rapid development of sensor technology and wireless communication technology, the Internet of things has become a new wave of information industry after the computer, Internet and mobile communication network. Ubiquitous data perception has led to a large number of data generated on the Internet of things. In the context of Internet of things, data processing and information retrieval have become the main research focus and hot spot.
As an important type of data processing and information retrieval, queries on Top-k networking in the background (especially in the field of wireless sensor network) has a very wide range of applications, such as environmental monitoring, intelligent transportation, target tracking etc.. However, in the emerging Internet of things, because a large number of users can search information directly in the physical world, it brings many new challenges to Top-k query processing. On the one hand, from the user's point of view, users can request different sets of information with different priorities and different times. Therefore, Top-k search should not only be multi-dimensional, but also cross the time domain. On the other hand, from a system point of view, data acquisition is usually performed by a small sensing device. Unlike data centers searched in cyberspace, these devices are often resource constrained and system efficiency critical.
In view of the above two challenges, this paper designs a multi-dimensional Top-k query algorithm which can meet the needs of users and systems in two aspects. The main idea is that each node will be sent by their own potential Top-k perception data points to the upper node, the data fusion from the upper node, then the fusion result is sent to the parent node until the base station, finally according to different user preference query, search results by the base station top-k. In the whole process, based on dominating graph and shortest path tree, efficient data query and fusion for single node and multiple node are carried out. In particular, in order to further reduce the huge communication overhead caused by continuous Top-k queries, this paper designs an efficient filter construction algorithm based on filtering idea.
Finally, based on the randomly generated data sets, we analyze and simulate the Top-k query algorithm proposed in this paper. The experiment mainly from the network energy consumption, query time and network lifetime three aspects of performance evaluation, the results show that the proposed energy consumption of sensor nodes in the affordable range, the query time is short, the network lifetime is longer.
Keywords Top-k query multi-dimensional top-k algorithm energy efficiency dominating graph shortest path tree energy efficiency
第一章 绪论 1
1.1研究背景与意义 1
1.2国内外研究现状 2
1.3本文研究内容 3
1.4论文的结构 3
第二章 问题定义及查询框架 5
2.1问题定义 5
2.2整体查询框架 5
2.3本章小结 7
第三章 基于支配图的多维连续top-k查询 8
3.1支配图的构建 8
3.2 单节点本地top-k查询 9
3.3基于SPT的多节点top-k数据融合 11
3.4.高效的连续top-k查询 14
3.5本章小结 15
第四章 仿真实验与性能评估 16
4.1 实验场景及参数设定 16
4.2 实验结果与分析 17
4.2.1通信开销 17
4.2.2查询时间 19
4.2.3网络寿命 20
4.3 本章小结 21
结 论 23
致谢 24
参考文献 25
第一章 绪论
1.1研究背景与意义
随着物联网近来的发展，使得用户不仅可以在网络空间中搜索信息，同样可应用在物理世界。可以想象，在不久的将来，人们将能够根据自己的喜好，在森林中享受各种时间的温度，湿度，光线，烟雾。在环境监测、智能交通等众多物联网数据感知领域有着广泛及实际的应用。 如火灾监测及防范（温度和烟雾浓度）。这些应用要求从系统设计中要求一个关键功能，效率高的多维top-k查询算法。
Top-k查询是能从海量数据中返回最符合用户需求的前k个结果，消除信息过载带来的负面影响。Top-k查询处理一直是各种研究领域的重要任务，其中从最大（或最低）的数据点从大数据集中检索出来。我们在上述应用中面临的独特挑战来自两个方面。首先，从客户的角度来看，可能会有大量不同的用户。他们每个人都有自己的喜好;他们不仅在数据的不同维度上放置不同的权重，而且在不同的数据时段。这种多维性已经为1D （一维）top-k查询开发了许多不适合或低效的算法。
多维top-k查询是感知节点集成多个传感器，满足用户对多个属性的不同查询偏好。
使用多维传感器数据，它们必须构成与用户请求数量一样多的查询，因为每个用户可以分配一组代表他自己的偏好的权重，这导致巨大的通信开销。第二，从系统的角度来看，传感设备是分布式的，通常资源有限。特别是对于能量限制传感器节点，通信应该是紧密优化的。因此，在数据库社区开发的大多数集中式方案，如在这里不能应用。例如，普通节点没有关于用户偏好的信息，并且如果提取了所有传感器数据，则可能招致大量的通信。
为此，我们开发了一个基于显性图（DG图）的框架。 DG图是一种分层数据结构，用于在多方面建立不同数据点之间的关系。为了在分布式传感器网络中成功应用DG图，我们面临着许多挑战。在服务器中使用给定的查询函数提取top-k结果，这是一个纯粹的集中操作。在分布式传感器网络中，传感器网络中连续多维顶k查询的处理。
Top-k查询处理一直是各种研究领域的重要任务，其中从最大（或最低）的数据点从大数据集中检索出来。我们在上述应用中面临的独特挑战来自两个方面。
首先，从客户的角度来看， 感知数据往往是多维而非单维，同时用户查询偏好不同，如何解决用户不同偏好下多维数据top-k查询，因此可能会有大量不同的用户。他们每个人都有自己的喜好;他们不仅在数据的不同维度上放置不同的权重，而且在不同的数据时段。这种多维性已经为1D top-k查询开发了许多不适合或低效的算法。使用多维传感器数据，它们必须构成与用户请求数量一样多的查询，因为每个用户可以分配一组代表他自己的偏好的权重，这导致巨大的通信开销。
第二，从系统的角度来看，传感设备是分布式的，通常资源有限。特别是对于能量限制传感器节点，通信应该是紧密优化的。因此，在数据库社区开发的大多数集中式方案，如[1]在这里不能应用。例如，普通节点没有关于用户偏好的信息，并且如果提取了所有传感器数据，则可能招致大量的通信。
1.2国内外研究现状
作为物联网的一个重要组成部分，无线传感器网络及其中的top-k查询受到了国内外研究者的广泛关注。总的来说，现有的top-k查询技术，无论是单维的[2]还是多维的，主要从两方面进行研究：网络底层逻辑树（又称路由树）和高效的top-k查询算法。
文献[3]以最短路径树为网络底层路由树，在此基础上，提出基于范围FILA算法。最短路径树的构建原则如下：以基站（sink）为根节点，保证其他网络节点到基站的路径最短。在查询过程中，基于最短路径，叶子节点可将其感知数据发送给中间汇聚节点融合，再按最短路径发送至上层节点，直至基站。在下一轮查询中，基于上轮查询结果，基站可为每个节点设置一个数据范围，只有在此范围内的数据才发送给基站。这样能进一步减少连续查询带来的巨大通信开销。然而，这种查询算法以牺牲查询准确度为代价，来提高查询效率。
Balijeet等[4]依赖于最小连通支配集构建出支配集树DST，主要选择邻居节点多，即度数大的节点作为支配节点，使中间汇聚节点的个数达到最少。基于DST，作者进一步提出一种精确的一维top-k查询方法EXTOK。在连续查询过程中，为每个节点设置阈值来抑制下一轮非top-k数据的传输。类似的，邬等人[5]也基于最小连通支配集，综合考虑节点初始能量、度数以及与邻节点通信开销三个因素来选择支配节点，构建最优支撑树OST。在每轮查询中，各节点以地理位置ID号轮流担任基站，此方法有效均衡了节点的能量开销。
利用感知数据的空间相关性，文献建立了一种偏序树POT[6]用于一维top-k查询。其主要是在网络中选择较高感知值的节点（即“热点”），根据这些热点建立底层拓扑结构，从而减少冗余的数据发送。然而，此方法不适用于均匀的数据分布网络，且其性能受热点分布密切相关。此外，Tang等人[7]还构建了层次网格索引树HGIT，基于层将网络中的节点分为两类：簇头节点和普通节点。同样的思想也出现在文献[8]中。
以上研究重点考虑了如何将各传感器节点数据高效地发送至基站，而忽视了对感知数据自身的处理。在许多实际的应用场景中，感知数据并非简单的一维，而是多维的，且用户查询偏好不同。如何高效的处理多维数据的top-k查询还需进一步研究。
1.3本文研究内容
本文主要基于无线传感器网络中的多维感知数据，针对系统及用户两方面不同查询需求，研究高效地连续多维top-k查询方法。其具体研究内容如下：
1.单节点多维数据处理：在多维top-k查询过程中，需要根据用户具体偏好（即查询函数）计算得到综合值，在此基础上再进行比较。然而，在传感器网络中，只有基站sink知道用户的具体查询偏好，各传感器节点无法在本地精确地计算top-k值。因此，需要将各节点潜在的top-k数据点发送给基站进行集中查询，如何查找各节点潜在的top-k数据点是本阶段主要研究内容。
2.多节点间数据融合（汇聚）：各节点在本地查找到潜在top-k数据点后，需要发送至上层节点进行数据汇聚，直至发送给基站。此阶段关键问题是建立高效的底层逻辑拓扑结构（即路由树），按某一树的结构汇聚感知数据能有效减少整个网络的通信开销。
3.连续top-k查询处理：若每次查询均按1、2步骤进行，将会给整个网络带来较大的计算开销。考虑传感器节点感知数据在一段连续时间内变化较小，本文主要基于上一轮查询结果，结合数据过滤的思想，设计有效的过滤值来处理连续top-k查询。
4.仿真实验和性能分析：利用java或Matlab等编程软件模拟整个top-k查询过程，并从能量消耗、查询时间、网络寿命三方面验证算法有效性。
1.4论文的结构
本文主要分为五章，其主要内容概要如下：
第一章：绪论。主要介绍了本课题的研究背景，概述了top-k在物联网大数据查询中的必要性和必然性。然后给出了现有top-k查询中两大关键问题在国内外的研究现状，最后简要阐述了本文的主要研究内容及主要工作。
第二章：问题定义及整体查询框架。主要对多维top-k查询进行了形式化定义，并介绍了本文多维top-k查询的整体框架。
第三章：基于支配图的多维连续top-k查询。分别从单节点数据处理及多节点数据融合出发，介绍了支配图及最短路径树的构建过程。在此基础上，设计了单节点潜在top-k提取算法及多节点top-k数据融合算法，最后构建filter来处理连续top-k查询问题。
第四章：仿真实验与性能评估。通过java软件模拟，来测试本算法的性能。软件产生随机节点的方法来模拟top-k查询算法过程，并进行多次重复。记录整合数据，记录分析能量开销、查询时间及网络寿命。
第五章：结论。对本文研究内容进行总结，并提出未来的发展及研究方向。
结 论
Top-k查询一直是计算机科学领域的一个关键问题，如数据处理和信息检索。在新兴的网络物理系统中，可以有大量用户直接在物理世界中搜索信息，为top-k查询处理带来了许多新的挑战。
从客户的角度来看，用户可以请求不同的信息集，具有不同的优先级和不同的时间。因此，top-k搜索不仅应该是多维度的，而且还要跨越时域。从系统的角度来看，数据采集通常由小型传感装置进行。与在网络空间中搜索的数据中心不同，这些设备通常资源受限，系统效率至关重要。
本文设计了了一个同时满足用户及系统两方面需求的多维top-k查询算法。其主要思想在于先由各节点将自身潜在top-k感知数据点发送给上层节点，由上层节点进行数据融合，再将融合结果发送给其父节点直至基站，最后根据用户不同查询偏好，由基站查找真实top-k结果。在整个过程中，本文分别基于支配图、最短路径树对单节点、多节点进行高效的数据查询和融合。特别地，为进一步减少连续top-k查询带来的巨大通信开销，本文基于过滤思想设计了有效的filter构建算法。
在仿真结果中，我们对本文提出的多维top-k查询算法分别从通信开销、查询时间、网络寿命这三个方面进行分析，具体分析了网络节点数目N和用户数据点查询个数k对此三个参数的影响。
参考文献
[1]L. Zou and L. Chen, “Dominant Graph: An Efficient Indexing Structure to Answer Top-k Queries,” Proc. IEEE 24th Int’l Conf. Data Eng. (ICDE ’08), 2008.
[2]Hsieh M H, Lin K W, Tseng V S. A hybrid scheme for energy-efficient object tracking in sensor networks [J]. Knowledge and Information Systems, 2013, 36(2): 359-384.
[3]Wu M, Xu J, Tang X, et al. Top-k monitoring in wireless sensor networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(7): 962-976.
[4]Malhotra B, Nascimento M A, Nikolaidis I. Exact top-k queries in wireless sensor networks [J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(10): 1513-1525.
[5]邬海琴, 王良民. 基于连通支配集的无线传感网Top-k查询最优支撑树研究[J]. 电子学报, 2017, 45(1):119-127.
[6]Cho Y H, Son J, Chung Y D. POT: an efficient top-k monitoring method for spatially correlated sensor readings [A]. Proceedings of the ACM 5th Workshop on Data Management for Sensor Networks [C]. Auckland, New Zealand: Association for Computing Machinery, 2008. 8-13.
[7]Tang J, Wang Z, Sun Y, et al. Top-k Queries in wireless sensor networks leveraging hierarchical grid index [A]. Proceedings of IEEE Eighth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS) [C]. Birmingham: IEEE, 2014. 381-386.
[8]Ye M, Liu X, Lee W C, et al. Probabilistic top-k query processing in distributed sensor networks [A]. Proceedings of IEEE 26th International Conference on Data Engineering (ICDE) [C]. Long Beach, CA: IEEE, 2010. 585-588.
[9]莫尚丰, 陈丁洁, 陈红, 等. 无线传感器网络中 top-k连接查询处理[J]. 计算机学报, 2013, 36(3): 557-570.
[10]W. Chen, J. Hou, and L. Sha, “Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks,” IEEE Trans. Mobile Computing, vol. 3, no. 3, pp. 258-271, July-Aug. 2004.
[11]Das A, Mandal C, Reade C, et al. An improved greedy construction of minimum connected dominating sets in wireless networks [A]. Wireless Communications and Networking Conference (WCNC) [C]. Cancun, Quintana: IEEE, 2011. 790-795.
[12]P. Cao and Z. Wang, “Efficient Top-k Query Calculation in Distributed Networks,” Proc. 23rd Ann. ACM Symp. Principles of Distributed Computing (PODC ’04), 2004.
[13]胡婷. 传感网中 Top-k 查询处理优化算法研究[D]. 湖南师范大学, 2014.
[14]B. Chen, W. Liang, and J.X. Yu, “Online Time Interval Top-k Queries in Wireless Sensor Networks,” Proc. Int’l Conf. Mobile Data Management (MDM), 2010.
[15]J. Cheng, H. Jiang, J. Liu, W. Liu, and C. Wang, “On Efficient Processing of Continuous Historical Top-k Queries in Wireless Sensor Networks,” IEEE Trans. Vehicular Technology,
[16]谢树春, 尹洁, 刘绍焕,等. 基于正六边形格网的最短路径算法[J]. 测绘科学, 2008, 33(1):106-108.
[17]Wang H, Guan Z T, Yang T T, et al. Top-k query framework in wireless sensor networks for smart grid [J]. China Communications, 2014, 11(6): 89-98.
[18]Sathyan T, Hedley M. Fast and Accurate Cooperative Tracking in Wireless Networks[J]. IEEE Transactions on Mobile Computing, 2013, 12(9):1801-1813.
[19]Peng X. An efficient massive data retrieval algorithm based on modified Top-k query[C]//2015 Seventh International Conference on Measuring Technology and Mechatronics Automation. IEEE, 2015: 102-105
[20]Yao L, Sheng Q Z, Ngu A H H, et al. Things of Interest Recommendation by Leveraging Heterogeneous Relations in the Internet of Things[J]. Acm Transactions on Internet Technology, 2016, 16(2):9.
[21]Kim D, Wu Y, Li Y, et al. Constructing minimum connected dominating sets with bounded diameters in wireless networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(2): 147-157.
[22]Tan H O, Korpeoglu I, Stojmenovic I. Computing localized power-efficient data aggregation trees for sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(3): 489-500.
[23]Jiang H, Cheng J, Wang D, et al. Continuous multi-dimensional top-k query processing in sensor networks [A]. IEEE Proceedings on INFOCOM [C]. Shanghai: IEEE, 2011. 793-801.