传感器网络空间关键字近似Top-k查询算法

上海交通大学学报（自然版） ›› 2014, Vol. 48 ›› Issue (10): 1457-1460.

• 自动化技术、计算机技术 • 上一篇下一篇

传感器网络空间关键字近似Top-k查询算法

邹志文，李桥，寇爱军

(江苏大学计算机科学与通信工程学院，江苏镇江 212013)

收稿日期:2014-01-03 出版日期:2014-10-28 发布日期:2014-10-28
基金资助:
国家科技型中小企业技术创新基金(13C26213201857)，江苏省科技型企业技术创新基金(BC2012210)

Approximate Top-k Query Algorithm for Spatial Keyword in Sensor Networks

ZOU Zhiwen，LI Qiao，KOU Aijun

（School of Computer Science and Communication Engineering, Jiangsu University, Zhenjiang 212013, Jiangsu, China）

Received:2014-01-03 Online:2014-10-28 Published:2014-10-28

摘要/Abstract

摘要：

摘要：提出了一种基于节点剪枝的Top-k査询算法.定义集合支配区域与剪枝规则，根据用户查询位置的变动，按照给定的剪切规则，对传感器网络节点进行剪枝处理，将符合规则的节点预先筛除，运用统计学抽样理论，设计了空间关键字近似Top-k查询算法.在2个真实数据集上进行验证.实验结果表明，该算法能够满足传感器网络环境中用户的需求，并且相比于边界距离增量算法（IBD）与基于改进的MW-Voronoi区域的空间关键字查询算法（MSK-uvr），其网络通信开销较低.

关键词: 空间关键字查询, Top-k, 传感器网络, 支配区域

Abstract:

Abstract： In this paper, a Top-k query algorithm based on node pruning rules was proposed. The concept of a set dominate region and pruning rules were defineded. As the position of users change in the dynamic set dominate region, the nodes of wireless sensor networks were pruned which conformed to pruning rules. The statistical sampling theory was used to design an approximate Top-k query algorithm based on spatial keyword. Experiments on two real datasets were made to validate the effect of the algorithm. The results show that the algorithm meets the needs of users in sensor network environment and it has an advantage of low energy consumption compared to the incremental border distance (IBD) algorithm and query algorithm of spatial keyword based upgraded MWVoronoi region (MSK-uvr).

Key words: spatial keyword query, Top-k, sensor networks, dominated region

中图分类号:

TP 301.6

邹志文，李桥，寇爱军. 传感器网络空间关键字近似Top-k查询算法[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1457-1460.

ZOU Zhiwen，LI Qiao，KOU Aijun. Approximate Top-k Query Algorithm for Spatial Keyword in Sensor Networks[J]. Journal of Shanghai Jiaotong University, 2014, 48(10): 1457-1460.

参考文献

［1］Alotaibi E, Mukherjee B. A survey on routing algorithms for wireless Adhoc and mesh networks［J］. Computer Networks, 2012, 56(2):940965.

［2］Tumuluru V, Wang P, Niyato D. Channel status prediction for cognitive radio networks［J］. Wireless Communications and Mobile Computing, 2010, 10:113.

［3］De Domenico A, Strinati E, Di Benedetto M. A survey on MAC strategies for cognitive radio networks［J］. IEEE Communications Surveys & Tutorials, 2012, 14(1): 2144.

［4］Felipe I D, Hristidis V, Rishe N. Keyword search on spatial databases［C］∥Proceedings of IEEE 24th International Conference on Data Engineering ICDE. Cancun:IEEE,2008: 656665.

［5］Wu D, Yiu M L, Jensen C S, et al. Efficient continuously moving topk spatial keyword query processing［C］∥Proceedings of the 27th International Conference on Data Engineering. Hannover:IEEE, 2011: 541552.

［6］LIU Y, LI J Z, GAO H, et al. Enabling εapproximate querying in sensor networks［J］. VLDB Endowment, 2009, 2(1):169180.

［7］CHENG Siyao, LI Jianzhong. Sampling based (ε,δ)approximate aggregation algorithm in sensor networks［C］∥Proceedings of the 29th IEEE International Conference on Distributed Computing Systems. Montreal: IEEE, 2009:273280.

［8］毕冉，李建中，程思瑶. 无线传感器网络(ε,δ)近似Topk查询算法［J］.通信学报, 2011, 32(8):4554.

BI Ran, LI Jianzhong, CHENG Siyao. (ε, δ)approximate Topk query processing algorithm in wireless sensor networks［J］. Journal on Communications，2011，32（8）：4554.

［9］赵亮，景宁，陈荦，等. 面向多核多线程的移动对象连续k近邻查询［J］.软件学报, 2011, 22(8):18051815.

ZHAO Liang, JING Ning, CHEN Luo,et al.Continuous k nearest neighbor queries over moving objects based on multicore and multithreading［J］. Journal of Software, 2011, 22(8):18051815.

[1]	张颖，乔运龙,张海洋. 基于虚拟力和果蝇优化算法混合控制水声传感器网络部署策略[J]. 上海交通大学学报（自然版）, 2017, 51(6): 715-721.
[2]	张颖，季常刚，李俊甫. 一种基于能量和距离的多级能量异构传感器网络路由算法[J]. 上海交通大学学报（自然版）, 2014, 48(07): 953-958.
[3]	师超1,仇洪冰1，2,王俊义2,李晓艳1. 基于Gossip算法的无线传感器网络时间同步[J]. 上海交通大学学报（自然版）, 2014, 48(03): 351-356.
[4]	周桂寅, 何晨, 蒋铃鸽. 认知无线传感器网络中基于网络特性的单天线媒体接入控制协议[J]. 上海交通大学学报（自然版）, 2012, 46(11): 1729-1735.
[5]	周南润1, 2, 江琼希1, 龚黎华1. 基于中国剩余定理和LU矩阵的传感器网络密钥预分配方案[J]. 上海交通大学学报（自然版）, 2012, 46(11): 1800-1805.
[6]	肖榕, 蒋铃鸽, 何晨. 一种无线传感器网络中基于信道可靠性的多信道MAC协议 [J]. 上海交通大学学报（自然版）, 2012, 46(09): 1382-1386.
[7]	温蜜1, 刘秀树2, 李婧1, 王勇1. 一种带验证和撤销的组密钥分发方案 [J]. 上海交通大学学报（自然版）, 2012, 46(02): 264-268.
[8]	谭冲1, 邹君妮1, 汪敏1, 熊红凯2. 分布式无线传感器网络的速率分配和网络成本联合优化[J]. 上海交通大学学报（自然版）, 2011, 45(07): 1021-1030.
[9]	王林, 张国忠, 朱华勇, 沈林成. 面向移动传感器网络的自适应一致性融合估计方法[J]. 上海交通大学学报（自然版）, 2011, 45(03): 383-0387.
[10]	程真，李腊元. 一种基于地理位置的无线传感器网络服务质量路由算法[J]. 上海交通大学学报（自然版）, 2010, 44(03): 413-0417.

传感器网络空间关键字近似Top-k查询算法

Approximate Top-k Query Algorithm for Spatial Keyword in Sensor Networks

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价