Username   Password       Forgot your password?  Forgot your username? 


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)


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.Get Free Adobe Reader

This site uses encryption for transmitting your passwords.