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

曾利军

(湖南工学院 计算机与信息科学学院，湖南 衡阳421002)

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]为：表示数据在 j维的权重。用户需求top-k查询指的是在数据D中来查询F的函数值最大K个点。同多数研究相同，只需要去考虑典型线性凸函数。该单调函数要满足以下条件：若 xj≤xj′，则 F（x1，x2，...，xm）≤F（x1′，x2′，...，xm′）。如数据维度是 2，对应 di四元组表示为＜di.x1，di.x2，di.id，di.t＞，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查询算法

由于传感器网络不能进行大规模的通信，通过sink节点的连续分发进行滤波器更新难以实现。同时滤波器在过滤数据需要来设置其数据过期时间，如果数据过期时间不设置，则需要设置区域的节点数设为counts，FLsink设为节点更新滤波器，设为节点数据传送到sink平均路径的长度。.N则为更新滤波器所引起的额外开销。如果数据过期需要更新一个滤波器，更新算法如下所示：

输入表示为sink节点有效支配图（DG），输出表示为非top-k的结果节点集合（NS）以及counts

（1）loop：If Sink 所接收的新数据 data 或者支配图（DG）的数据过期then

（2）更新区域中Sink的数据DG

（3）计算更新后支配图（DG）的 FLsink

（4）If FLsink配的新数据 data then

（5）counts← counts+1；NS ← NS∪{i}

（6）end if

（8）Sink 给集合（NS）各个节点发布 FLsink

（9）count← 0；NS ← φ

（10）end if

（11）end if

（12）end loop

改进后的数据节点处理模块，当数据节点接收到滤波器的数据集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）.