无线传感器网络中top-k连接查询处理  

Algorithms for Top-k Join Queries in Wireless Sensor Networks

作　　者：莫尚丰[1,2,3] 陈丁洁[1,2] 陈红[1,2] 李英龙[1,2,3] 李翠平[1,2] 

机构地区：[1]教育部数据工程与知识工程重点实验室(中国人民大学)北京100872 [2]中国人民大学信息学院北京100872 [3]湖南科技大学湖南湘潭411201

出　　处：《计算机学报》2013年第3期557-570,共14页Chinese Journal of Computers

基　　金：核高基国家重大专项项目(2010ZX01042-001-002-002);国家自然科学基金(61070056);国家自然科学基金重点项目(61033010)资助~~

摘　　要：无线传感器网络是物联网核心组成部分之一,数据查询处理是无线传感器网络中很重要的一个研究领域.连接查询能在不同的位置监视相似的网络环境,top-k连接查询能进一步得出组合得分最大(或最小)的k个相似网络环境.top-k连接查询根据得分函数计算匹配结果的组合得分,并报告组合得分结果最大(或最小)的k个匹配节点对.文中提出了基本top-k连接算法BTJQ.该算法首先按照得分属性值从大到小对所有元组排序,然后依次取出元组,产生连接结果.对每个连接结果按照得分函数计算组合得分,如果满足停止条件,则停止取元组,并输出连接结果.在BTJQ基础上,作者提出了集中式top-k连接算法CTJQ和优化的集中式top-k连接算法OCTJQ.针对特定应用场景,作者进一步提出了分布式top-k连接算法DTJQ.最后,在真实数据集上验证了各算法.实验结果表明,文中算法好于经典连接算法SENS-Join.Wireless Sensor Networks （WSNs） Things （IoTs）. Data query processing is a very is one of the core components of the Internet of important research area in Wireless Sensor Net- works. Join queries can monitor similar network environments in different positions. Top-k join queries further obtain k similar network environments which have the maximum （or minimum） combination scores. The top-k join query calculates the combination score of matching tuples according to scoring function and reports the top-k matching tuples which have the maximum （or minimum） combination score. In this paper, we propose a Basic Top-k Join Queries （BTJQ） algorithm. In BTJQ, the base station sorts the tuples based on the score attribute values in descending order. Then the base station gets the tuples from the sorted list in turn and produces the join result and calculates the combination score. If the joinresult meets the stop condition, the base station stops taking tuples and outputs the final top-k join result. Based on the BTJQ, we propose a Centralized Top-k Join Queries （CTJQ） algorithm and Optimize Centralized Top-k Join Queries （OCTJQ） algorithm. For a different scenario, we propose a Distributed Top-k Join Queries （DTJQ） algorithm. Experiments on real-world data set show that our algorithms outper- form the typical algorithm SENS-Join.

关 键 词：无线传感器网络 top—k查询 连接查询 物联网 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]