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

Abstract

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

CLC Number:

TP 301.6

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.

References

［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]	ZHANG Ying (张颖), LI Peisong (李培嵩), MAO Lin (毛林). Research on Improved Low-Energy Adaptive Clustering Hierarchy Protocol in Wireless Sensor Networks [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(5): 613-619.
[2]	ZHANG Ying,QIAO Yunlong*,ZHANG Haiyang. Coverage Enhancing for Underwater Acoustic Sensor Networks Based on Virtual Force and Fruit Fly Optimization Algorithm [J]. Journal of Shanghai Jiaotong University, 2017, 51(6): 715-721.
[3]	SHI Chao1,QIU Hongbing1，2,WANG Junyi2,LI Xiaoyan1. Time Synchronization for Wireless Sensor Networks Based on Gossip Algorithm [J]. Journal of Shanghai Jiaotong University, 2014, 48(03): 351-356.
[4]	WANG Fang 1 (王芳), WEI Zhe2 (魏哲). Energy-Saving Reputation Method for Wireless Sensor Networks [J]. Journal of shanghai Jiaotong University (Science), 2012, 17(2): 223-227.
[5]	XU Zhi-guang1 (徐志广), ZHU Lei-ji1 (朱磊基), SHI Yu-song1 (施玉松), JIANG hua2 (姜华). Research of Scalability of the Belt-Type Sensor Networks [J]. Journal of shanghai Jiaotong University (Science), 2012, 17(2): 237-240.
[6]	ZHOU Gui-Yin, HE Chen, JIANG Ling-Ge. Single Transceiver and Network Characteristics Based MAC Protocol for Cognitive Radio Wireless Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1729-1735.
[7]	ZHOU 南Run-1, 2 , JIANG Qiong-Xi-1, GONG Li-Hua-1. Key Predistribution Scheme Based on CRT and LU Matrix for Wireless Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1800-1805.
[8]	ZHANG Rui-Hua-1, JIA Zhi-Ping-1, CHENG He-You-2. The Routing Algorithm for WSNs Based on Unequal Clustering and Minimum Energy Consumption [J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1774-1778.
[9]	XIAO Rong, JIANG Ling-Ge, HE Chen. A Channel Reliability Based Multi-channel MAC Protocol in Wireless Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2012, 46(09): 1382-1386.
[10]	CHEN De-Fu, TAO Zheng-Su, ZHU Jian-Ping. An Adaptive and Asynchronous MAC Protocol for Wireless Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2011, 45(10): 1521-1525.
[11]	DENG Han-Lin, LI Lei, HUANG He-Qing, YUAN Xiao-Bing, WANG Ying-Guan. Energy Consumption Analysis and Improvement Strategy for ClusterHead Rotation in Wireless Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2011, 45(03): 321-0326.
[12]	Wang-Lin, ZHANG Guo-Zhong, ZHU Hua-Yong, SHEN Lin-Cheng. Adaptive Consensus Fusion Estimation for Mobile Sensor Networks [J]. Journal of Shanghai Jiaotong University, 2011, 45(03): 383-0387.