论文部分内容阅读
传感器以及传感器网络技术正在快速进步,一系列新型的信息查询技术也随之产生。top-k主导查询要求返回一组数据中主导其他数据个数最多的k个数据。对于异常事件检测、动物行为变化监测等传感器网络应用,top-k主导查询非常重要。top-k主导查询结合了skyline查询和top-k查询的优点,不仅有效控制了返回数据的数目,而且不依赖于用户偏好:top-k主导查询对于任何用户返回相同的结果。 传感器采集的数据往往具有多维分量、数量庞大,上传全部数据到源节点将耗费巨大的通信开销。因此,我们必须设计高效的算法,以尽可能减小top-k主导查询的总通信开销。同时,集中式算法不适用于传感器网络环境,这增大了设计算法的难度。最后,即使总通信开销得到有效控制,如果某个节点的通信量远大于其他节点(我们称该节点为瓶颈节点),也会极大地减小传感器网络的使用寿命,所以我们设计的算法必须尽可能减小瓶颈节点的通信开销。 本文是第一个致力于解决多维传感器数据top-k主导查询问题的工作。我们提出了三种有效算法,首先,我们提出了直观的简单算法,它在得到的top-k查询结果的基础上进行;然后,我们基于二等分空间划分策略(BinarySpacePartitioning,BSP)提出了基础算法;最后,我们利用传感器数据具有时间相关性和空间相关性的特点,提出了改进算法。接着,我们为简单算法和基础算法给出通信开销分析和瓶颈分析。为了展现算法的效果,我们在IntelBerkeley实验室数据集和三种合成数据集的基础上进行了多组仿真实验;我们以将所有数据发送到源节点的精确算法作为参考,实验结果显示,与精确算法相比,简单算法、基础算法和相应的改进算法都有效减少了总的通信开销,并且基本不存在瓶颈问题。