LAPDK: A Novel Dynamic-Programming-Based Algorithm for the LAP-(D, k) Query Problem in Wireless Sensor Networks

doi:10.23940/ijpe.17.04.p21.540550

Abstract

Abstract:

In wireless sensor networks, the LAP-(D, k) query problem can be seen as a special Top-k query problem with the constraint that the Euclidean distance between any two locations corresponding to the data items in the Top-k query results should not be smaller than the given value D. To solve this problem, a novel dynamic-programming-based heuristic algorithm named LAPDK is proposed. LAPDK firstly divides the sensing field into hexagonal cells using some geometry methods. Then, it finds the approximate solution of the LAP-(D, k) query problem based on parts of the data generated by the sensor nodes in some preferential cells using the dynamic programming technique. Finally, it further optimizes the solution based on the sensing data received by the Sink node. Simulation results show that LAPDK not only decreases the energy cost of WSNs but also obtains a better approximation ratio compared to the existing state-of-the-art scheme for the LAP-(D, k) query problem.

Submitted on February 24, 2017; Revised on April 26, 2017; Accepted on May 30, 2017
References: 16

Xingpo Ma, Yanli Li, Ran Li, Yin Li, and Junbin Liang. LAPDK: A Novel Dynamic-Programming-Based Algorithm for the LAP-(D, k) Query Problem in Wireless Sensor Networks [J]. Int J Performability Eng, 2017, 13(4): 540-550.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References 0

	1. P. Naik, N. Telkar, and K. Kotin, “Survey on Wireless Sensor Network with their remaining Challenges”, International Journal of Scientific Research in Science and Technology, vol. 2, no. 6, pp.321-331, 2016
	2. S. Cheng, J. Li, and L. Yu, “Location Aware Peak Value Queries in Sensor Networks”, Proceedings of IEEE INFOCOM, pp.486-494, 2012
	3. A. Jindal, and K. Psounis, “Modeling spatially correlated data in sensor networks”, ACM Transactions on Sensor Networks, vol. 2, no.4, pp. 466-499, 2006
	4. S. Mo, H. Chen, and Y. Li, “Clustering-based routing for top-k querying in wireless sensor networks”, Eurasip Journal on Wireless Communications & Networking, issue 1, pp.1-13, 2011
	5. J. Fu, and Y. Liu, “Random and Directed Walk-Based Top-k Queries in Wireless Sensor Networks”, Sensors, vol.15, no.6, pp.12273-12298, 2015
	6. H. Haiping H, Y. Qi, Q. Xiaolin, and W. Ruchuan, “A filter-based algorithm for optimizing top-k queries in wireless sensor networks”, Journal of Systems Architecture, vol.58, no.2, pp.73-85, 2012
	7. Q. Pan, M. Li, M. Wu, and W. Shu, “Optimization of Accurate Top-k Query in Sensor Networks with Cached Data”, Proceedings of the 7th International Wireless Communications and Mobile Computing Conference (IWCMC) , pp.553 - 558, 2011
	8. B. Chen，W. Liang，J. Yu, “Energy-efficient top-k query evaluation and maintenance in wireless sensor networks”, Wireless Networks, vol.20, no.4, pp.591-610, 2014
	9. D. Choi, and C. Chung, “REQUEST+: A framework for efficient processing of region-based queries in sensor networks”, Information Sciences, vol.248 no.6, pp.151-167, 2013
	10. B. Malhotra, M.Nascimento, and I. Nikolaidis, “Exact Top-k Queries in Wireless Sensor Networks,” IEEE Transactions on Knowledge and Data Engineering, vol.23, no.10, pp.1513-1525, 2011
	11. H. Jiang, J. Cheng, D. Wang, C. Wang, and G. Tan, “Continuous Multi-dimensional Top-k Query Processing in Sensor Networks”, Proceedings of IEEE INFOCOM, pp.793-801, 2011
	12. M. Ye, W. Lee, D. Lee, and X. Liu, “Distributed Processing of Probabilistic Top-k Queries in Wireless Sensor Networks”, IEEE Transactions on Knowledge and Data Engineering, vol.25, no.1, pp.76-91, 2013
	13. S. Tang, X. Mao, and X. Li, “Efficient and fast distributed top-k query protocol in wireless sensor networks”, Proceedings of International Conference on Network Protocols (ICNP) , pp. 99-108, 2011
	14. C. Zhu, L. Yang, L. Shu, and S. Nishio, “Insights of Top-k Query in Duty-Cycled Wireless Sensor Networks”, IEEE Transactions on Industrial Electronics, vol.62, no.2, pp.1317-1328, 2015
	15. H. Wang，Z. Guan，T. Yang，and Y. Xu, “Top-K Query Framework in Wireless Sensor Networks for Smart Grid”, China Communications, vol.11, no.6, pp.89-98, 2014
	16. H. Yetgin, K. Cheung, M. El-Hajjar, and L. Hanzo, “A Survey of Network Lifetime Maximization Techniques”, IEEE Communications Surveys & Tutorials, 2017, DOI: 10.1109/COMST.2017.2650979