|Table of Contents|

Energy-efficient Spatio-temporal Query Processing Algorithm on Irregular Region over Sensor Network


Research Field:
Publishing date:


Energy-efficient Spatio-temporal Query Processing Algorithm on Irregular Region over Sensor Network
LIU Yu-leiQIN Xiao-linSHEN Jia-jia
College of Information Science & Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016. China
wireless sensor networks query processing spatio-temporal queries irregular query regions
TP301. 9
In order to reduce the energy consumption of irregular spatio-temporal query processing and improve the query success rate,a tree-based algorithm is proposed to process spatio-temporal data collection queries with irregular query regions. It organizes sensor nodes in query regions as a tree. The nodes in the tree send local data to their parents until reaching the root of the tree. An itinerary-based algorithm to process spatio-temporal data aggregation queries with irregular query regions is also proposed here. It collects the data of nodes in the query region and aggregates themalong an itinerary to generate the final query result. Both of them divide the complex and irregular query region into some simple convex polygons in order to reduce the computational complexity of determining whether the nodes are in the query region and ensure that only the nodes in query regions send the sensed data,thus reducing the energy consumption. The experimental results show that the proposed algorithms outperform the existion spatio-temporal query processing algorithms for irregular region query.


[1] 孙利民,李建中,陈渝,等. 无线传感器网络[M]. 北京: 清华大学出版社,2005
[2] Coman A,Nascimento M A,Sander J. A framework for spatio-temporal query processing over wireless sensor networks[A]. Proceedings of the 1st Workshop on Data Management for Sensor Networks,in conjunction with VLDB[C]. New York,USA: ACM Press,2004: 104-110.
[3] Coman A,Sander J,Nascimento M A. An analysis of spatio-temporal query processing in sensor networks [A]. Proceedings of the 1st IEEE International Workshop on Networking Meets Databases in Cooperation with 21st IEEE Conf on Data Engineering[C]. Washington, DC,USA: IEEE Computer Society,2005: 120-125.
[4] Alexandru C,Mario A N,Sander J. Exploiting redundancy in sensor networks for energy efficient processing of spatiotemporal region queries[A]. Proceedings of the 14th ACM Conf Information and Knowledge Management[C]. New York,USA: ACM Press,2005: 187-194.
[5] 刘亮,秦小麟,戴华,等. 能量高效的无线传感器网络时空查询处理算法[J]. 电子学报,2010,38( 1) : 54-59.
[6] 郭龙江,李建中,李桂林. 无线传感器网络环境下时-空查询处理方法[J].软件学报,2006,17( 4) : 794-805.
[7] Madden S,Franklin M J,Hellerstein J M,et al. Tag: A tiny aggregation service for ad-hoc sensor networks [A]. Proceeding of the 5th Symposium on Operating System Design and Implementation[C]. Boston,USA: USENIX Association,2002: 131-146.
[8] Madden S,Franklin M J,Hellerstein J M,et al. Tinydb: An acquisitional query processing system for sensor networks[J]. Transactions on Database System,2005, 30( 1) : 122-173.
[9] Xu Y Q,Lee W C,Xu J L,et al. Processing window queries in wireless sensor networks[A]. Proceedings of the 22nd International Conference on Data Engineering [C]. Washington,DC,USA: IEEE Computer Society,2006: 70-80.
[10] Akyildiz I F,Su W,Sankarasubramaniam Y,et al. Wireless sensor networks: A survey[J]. Computer Networks,2002,38( 4) : 393-422.
[11] 周培德. 计算几何———算法分析与设计[M]. 2 版.北京: 清华大学出版社,2005.
[12] Rappaport T. Wireless communications: Principles and practice[M]. New Jersey: Prentice-Hall Inc,1996.
[13] Chu D,Deshpande A,Hellerstein J M,et al. Approximate data collection in sensor networks using probabilistic Models[A]. Proceedings of the 22nd International Conference on Data Engineering[C]. Washington,DC, USA: IEEE Computer Society,2006: 48-59.
[14] Deshpande A,Guestrin C,Madden S R,et al. Modeldriven data acquisition in sensor networks [A]. Proceedings of the Thirtieth International Conference on Very Large Data Bases[C]. New York,USA: ACM Press,2004: 588-599.


Last Update: 2012-02-28