|
LAPDK: A Novel Dynamic-Programming-Based Algorithm for the LAP-(D, k) Query Problem in Wireless Sensor Networks
Volume 13, Number 4, July 2017 - Paper 21 - pp. 540-550
DOI: 10.23940/ijpe.17.04.p21.540550
Xingpo Maa, Yanli Lia, Ran Lia, Yin Lia, Junbin Liangb
aSchool of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, P.R.China
bSchool of Computer and Electronics Information, Guangxi University, Nanning 530004, P.R.China
(Submitted on February 24, 2017; Revised on April 26, 2017; Accepted on May 30, 2017)
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.
References: 16
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
Please note : You will need Adobe Acrobat viewer to view the full articles. |