一种高效的高维数据流查询方法研究

【摘 要】为了改进无线传感器网络中高维数据的查询扩展、提高数据的查询精度以及减小数据通信量，提出一种高效的高维数据查询处理框架。该框架可利用用户的偏好函数来进行任意查询。并在该框架的基础上提出了改进滤波器算法，该算法通过滤波器避免sink分发所有RSsink数据，从而减少通信量。

【关键词】高维数据；查询扩展；偏好函数；查询精度

0 引言

Top-k查询大量运用在数据库领域，可以从大量数据库中提取到K个数据集或者数据点。目前面临两方面的挑战，许多研究通过数据融合来完成数据查询处理，来减少传送能耗、增长传感器生命期。数据融合技术中，传感器网络最基础的应用为top-k。Silberstein.et.al[1-2]提出了一种线性top-k查询方法，设计了数据查询器。Zeinalipont et.al[3]提出了一种阀值数据查询算法，需查询的各个属性区域设置了一些不同的阀值来减小对基站所传送的无用数据。Wu et.al[4-5]在节点中设置了滤波器来滤除无用的数据。上面的几种算法一定程度上改善了传感器网络数据查询的效率，降低了能耗，关注的却是传感器一维数据集。而传感器网络高维数据的查询在理论研究及实际应用中，同样有着非常重要的意义，如海洋的检测研究，生物学家关注的是光照度、水温等，地质学家却关注水流速度、酸碱度等。需要设计的系统可根据用户的需求及偏好采用多属性的查询方式。而无线传感器网络多维数据查询研究较少。设计传感器的节点能量高效及多用户需求与偏好的连续高维数据的top-k查询为当前要解决的首要问题。

1 问题描述

无线传感器网络中，假设数据集为D={d1，d2.....dn}，di则为m-维数据点即表示为（m+2）个数据元组：di=（di.x1，di.x2，.......，di.xm，di.id，di.t），di.xi表示为数据，di.id表示为数据类ID号，di.t表示所需要的时间。用户需求的查询函数则可以定义[4]为：F（di）=∑■■wj ·di.xj，wj表示数据在j维的权重。用户需求top-k查询指的是在数据D中来查询F的函数值最大K个点。同多数研究相同，只需要去考虑典型线性凸函数。该单调函数要满足以下条件：若xj≤xj′，则F（x1，x2，......，xm）≤F（x1′，x2′，......，xm′）。如数据维度是2，对应di四元组表示为，di.x1，di.x2则为采样值。无线传感器的sink节点需依据用户的每个wj权重来返回查询结果，表示为URS，用户偏好不同，则wj不同，传感器sink节点可能不只返回K个结果。

2 用户高维处理框架

为了高维数据查询扩展的方便、提高数据的查询精度以及减少数据通信量，提出一种用户的高维数据查询处理架构。高维数据查询处理框架如图1，在传统的框架上进行改进，具体的改进有以下几点：

（1）根据用户的偏好不同，来赋值权重K值，优先来响应较大K值的查询请求；

（2）通过增加可选单元，用来进行模糊查询或处理数据老化，与其它设备相连；

（3）支配图接收的数据查询结果同Sink节点查询结果相融合，再传送到节点；

（4）从图1得出，改进的处理框架将不会依赖传感器网络路由，各路由结构都可以采用。

图1中用户数据流先通过无线传感器网络传送，如果Sink节点接收的数据查询结果为RS，则节点通过检测支配图，再与RS相融合，最终传送给数据流目的节点以及与Sink节点的汇合。基站传送数据同时，还会回传TOP-K全局的数据信息给无线传感器网络，也可以在当经过滤波器信息时，传送给全局网络接收，但可能会影响到数据查询的精度以及查询的结果重复，造成数据受限。要进行更好的高维数据查询，需在已有的TOP-K基本数据查询方法上，提出一种新的改进的用户高维数据查询算法。

图1 用户数据高维查询处理结构图

3 改进的用户高维数据TOP-K查询算法

改进后的数据节点处理模块，当数据节点接收到滤波器的数据集FLsink以后，会进行当地滤波器的更新，再从滤波器中去掉过期数据，最后寻找需发送的点（不属于TOP-K的查询结果）。如果FLi为非支配的新数据datai，需将数据传送到父节点，同时在循环中去掉过期的数据。TSi设为节点所发送数据集。

4 总结

在传统的数据查询基础上，设计出一种用户偏好函数无线传感器数据处理框架。通过支配图维护top-k数据查询信息。通过数据支配信息来设定偏好函数，使用户的数据查询更易实现，而非top-k数据查询结果可以通过滤波器来进行数据的过滤处理。本架构还有较好的扩展性，通过在框架的可选单元加入模糊数据查询，用来解决数据的老化。下一步研究异构传感器数据通信的内容。

【参考文献】

[1]Silberstein A，Braynard R，Ellis C，et a1.A SamPling-based Approach to Optimizing Top-k Queries in Sensor Networks[J]. Proceedings of IEEE ICDE，2010.

[2]曾利军，刘卉，彭广.动态传感器网络区域受限的移动sink路径选择研究[J].计算机应用研究，2013，30（6）：1652-1655.

[3]Zeinalipont D，Vagena Z，Gunopulos D，et al. The Threshold Join Algorithm for Top-k Queries in Distributed Sensor Networks[J]. Proceedings of workshop data Management for Sensor Networks（DMSN），2009.

[4]刘卉，李泽军.基于投影矢量的双组播树高效路由数据收集[J].传感技术学报，2013，26（4）：570-576.

[5]Wu M，Xu J Tang X，et al. Top-k Monitoring in Wireless Sensor Networks. IEEE Trans[J]. On Knowledge and Data Engineering（TKDE），2011，19（7）.

[责任编辑：丁艳]

推荐访问： 数据流 高效 方法 研究 查询