[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A comparative investigation of deterministic and metaheuristic algorithms for node localization in wireless sensor networks

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

Location-based services in wireless sensor networks demand precise information of locations of sensor nodes. Range-based localization, a problem formulated as a two-dimensional optimization problem, has been addressed in this paper as a multistage exercise using bio-inspired metaheuristics. A modified version of the shuffled frog leaping algorithm (MSFLA) has been developed for accurate sensor localization. The results of MSFLA have been compared with those of geometric trilateration, artificial bee colony and particle swarm optimization algorithms. Dependance of localization accuracies achieved by these algorithms on the environmental noise has been investigated. Simulation results show that MSFLA delivers the estimates of the locations over 30% more accurately than the geometric trilateration method does in noisy environments. However, they involve higher computational expenses. The MSFLA delivers the most accurate localization results; but, it requires the longest computational time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Alrajeh, N. A., Bashir, M., & Shams, B. (2013). Localization techniques in wireless sensor networks. International Journal of Distributed Sensor Networks, 9(6), 304628.

    Article  Google Scholar 

  2. Aspnes, J., Eren, T., Goldenberg, D. K., Morse, A. S., Whiteley, W., Yang, Y. R., et al. (2006). A theory of network localization. IEEE Transactions on Mobile Computing, 5(12), 1663–1678.

    Article  Google Scholar 

  3. Aydin, D. (2015). Composite artificial bee colony algorithms: From component-based analysis to high-performing algorithms. Applied Soft Computing, 32(C), 266–285.

    Article  Google Scholar 

  4. Bahl, P., & Padmanabhan, V. N. (2000). RADAR: An in-building RF-based user location and tracking system. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (pp. 775–784).

  5. Bansal, J. C., Sharma, H., & Jadon, S. S. (2013). Artificial bee colony algorithm: A survey. International Journal of Advanced Intelligence Paradigms, 5, 123–159.

    Article  Google Scholar 

  6. Barati, M., & Farsangi, M. M. (2014). Solving unit commitment problem by a binary shuffled frog leaping algorithm. IET Generation, Transmission Distribution, 8(6), 1050–1060.

    Article  Google Scholar 

  7. Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: From natural to artificial systems. New York, NY: Oxford University Press Inc.

    MATH  Google Scholar 

  8. Boukerche, A., Oliveira, H. A. B. F., Nakamura, E. F., & Loureiro, A. A. F. (2007). Localization systems for wireless sensor networks. IEEE Wireless Communications, 14(6), 6–12.

    Article  Google Scholar 

  9. Bulusu, N., Heidemann, J., & Estrin, D. (2000). GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications, 7(5), 28–34.

    Article  Google Scholar 

  10. Cao, J. (2015). A localization algorithm based on particle swarm optimization and quasi-Newton algorithm for wireless sensor networks. Journal of Communication and Computers, 10(2), 85–90.

    Google Scholar 

  11. Doherty, L., Pister, K., & El Ghaoui, L. (2001). Convex position estimation in wireless sensor networks. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (Vol. 3, pp. 1655–1663).

  12. Eusuff, M., Lansey, K., & Pasha, F. (2006). Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization. Engineering Optimization, 38, 129–154.

    Article  MathSciNet  Google Scholar 

  13. Feng, C., & Zhang, L. H. (2012). A modified shuffled frog leaping algorithm for solving nodes position in wireless sensor network. Proceedings of the International Conference on Machine Learning and Cybernetics, 2, 555–559.

    Google Scholar 

  14. He, K., Jia, M., & Xu, Q. (2016). Optimal sensor deployment for manufacturing process monitoring based on quantitative cause-effect graph. IEEE Transactions on Automation Science and Engineering, 13(2), 963–975.

    Article  Google Scholar 

  15. Hightower, J., & Borriello, G. (2001). Location systems for ubiquitous computing. Computer, 34(8), 57–66.

    Article  Google Scholar 

  16. Hsieh, T. J., Hsiao, H. F., & Yeh, W. C. (2011). Forecasting stock markets using wavelet transforms and recurrent neural networks: An integrated system based on artificial bee colony algorithm. Appllied Soft Computing, 11(2), 2510–2525.

    Article  Google Scholar 

  17. Kar, A. K. (2016). Bio inspired computing—A review of algorithms and scope of applications. Expert Systems with Applications, 59, 20–32.

    Article  Google Scholar 

  18. Karaboga, D., & Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), 459–471.

    Article  MathSciNet  MATH  Google Scholar 

  19. Karaboga, D., & Ozturk, C. (2010). Fuzzy clustering with artificial bee colony algorithm. Scientific Research and Essays, 5(14), 1899–1902.

    Google Scholar 

  20. Karaboga, D., Gorkemli, B., Ozturk, C., & Karaboga, N. (2014). A comprehensive survey: Artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Revolution, 42(1), 21–57.

    Article  Google Scholar 

  21. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942–1948.

    Article  Google Scholar 

  22. Kulkarni, R. V., & Venayagamoorthy, G. K. (2010). Bio-inspired algorithms for autonomous deployment and localization of sensor nodes. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 40(6), 663–675.

    Article  Google Scholar 

  23. Kulkarni, R. V., & Venayagamoorthy, G. K. (2011). Particle swarm optimization in wireless-sensor networks: A brief survey. Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 41(2), 262–267.

    Article  Google Scholar 

  24. Kulkarni, R. V., Venayagamoorthy, G. K., & Cheng, M. X. (2009). Bio-inspired node localization in wireless sensor networks. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (pp. 205–210).

  25. Kulkarni, R. V., Förster, A., & Venayagamoorthy, G. K. (2011). Computational intelligence in wireless sensor networks: A survey. IEEE Communications Surveys and Tutorials, 13(1), 68–96.

    Article  Google Scholar 

  26. Kulkarni, V. R., Desai, V., & Kulkarni, R. V. (2016). Multistage localization in wireless sensor networks using artificial bee colony algorithm. In Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI) (pp. 1–8).

  27. Li, H., Xiong, S., Liu, Y., Kou, J., & Duan, P. (2011). A localization algorithm in wireless sensor networks based on PSO. In Proceedings of the International Conference on Advances in Swarm Intelligence, Part II (pp. 200–206). Berlin: Springer.

  28. Ma, M., Liang, H., Jian, Guo M., Fan, Y., & Yin, Y. (2011). SAR image segmentation based on artificial bee colony algorithm. Appllied Soft Computing, 11(8), 5205–5214.

    Article  Google Scholar 

  29. Mao, G., & Fidan, B. (2009). Localization algorithms and strategies for wireless sensor networks. Hershey, PA: Information Science Reference - Imprint of: IGI Publishing.

    Book  Google Scholar 

  30. Moore, D., Leonard, J., Rus, D., & Teller, S. (2004). Robust distributed network localization with noisy range measurements. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys ’04 (pp. 50–61).

  31. Niculescu, D., & Nath, B. (2001). Ad hoc positioning system (APS). Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), 5, 2926–2931.

    Article  Google Scholar 

  32. Niculescu, D., & Nath, B. (2003). Ad hoc positioning system (APS) using AOA. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (Vol. 3, pp. 1734–1743).

  33. Oliveto, P. S., He, J., & Yao, X. (2007). Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3), 281–293.

    Article  Google Scholar 

  34. Ong, Y.-S., Zhu, N., Lim, M.-H., & Wong, K. W. (2006). Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 36(1), 141–152.

    Article  Google Scholar 

  35. Öztürk, C., Karaboğa, D., & Görkemlı, B. (2012). Artificial bee colony algorithm for dynamic deployment of wireless sensor networks. Turkish Journal of Electrical Engineering & Computer Sciences, 20(2), 255–262.

    Google Scholar 

  36. Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O., Moses, R. L., & Correal, N. S. (2005). Locating the nodes: Cooperative localization in wireless sensor networks. IEEE Signal Processing Magazine, 22(4), 54–69.

    Article  Google Scholar 

  37. Peng, R., & Sichitiu, M. L. (2007). Probabilistic localization for outdoor wireless sensor networks. SIGMOBILE Mobile Compution and Communication Review, 11(1), 53–64.

    Article  Google Scholar 

  38. Priyantha, N. B., Balakrishnan, H., Demaine, E., & Teller, S. (2003). Poster abstract: Anchor-free distributed localization in sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (pp. 340–341).

  39. Savarese, C., Rabaey, J., & Langendoen, K. (2002). Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In Proceedings of the USENIX Technical Annual Conference (pp. 317–327).

  40. Savvides, A., Han, C. C., & Strivastava, M. B. (2001). Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom), New York, NY, USA (pp. 166–179).

  41. Udgata, S. K., Sabat, S. L., & Mini, S. (2009). Sensor deployment in irregular terrain using artificial bee colony algorithm. In World Congress on Nature Biologically Inspired Computing, NaBIC 2009 (pp. 1309–1314).

  42. Vargas Benítez, C. M., & Lopes, H. S. (2010). Parallel artificial bee colony algorithm approaches for protein structure prediction using the 3DHP-SC model. In Intelligent Distributed Computing IV: Proceedings of the 4th International Symposium on Intelligent Distributed Computing, Tangier, Morocco. Berlin: Springer (pp. 255–264).

  43. Yick, J., Mukherjee, B., & Ghosal, D. (2008). Wireless sensor network survey. Computer Networks, 52(12), 2292–2330.

    Article  Google Scholar 

  44. Youssef, M., Youssef, A., Rieger, C., Shankar, U., & Agrawala, A. (2006). Pinpoint: An asynchronous time-based location determination system. In Proceedings of the 4th International Conference on Mobile Systems, Applications and Services (MobiSys) (pp. 165–176). New York, NY: ACM.

  45. Zhao, H., Pei, Z., Jiang, J., Guan, R., Wang, C., & Shi, X. (2010). A hybrid swarm intelligent method based on genetic algorithm and artificial bee colony. In Proceedings of the First International Conference, Advances in Swarm Intelligence (ICSI) (pp. 558–565). Berlin: Springer.

Download references

Acknowledgements

Authors gratefully acknowledge the support received from M. S. Ramaiah University of Applied Sciences, Bengaluru, India, and KLS Gogte Institute of Technology, Belagavi, India.

Author information

Authors and Affiliations

  1. M S Ramaiah University of Applied Sciences, Bengaluru, India

    Vaishali R. Kulkarni & Raghavendra V. Kulkarni

  2. KLS Gogte Institute of Technology, Belagavi, India

    Veena Desai

Authors
  1. Vaishali R. Kulkarni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Veena Desai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raghavendra V. Kulkarni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vaishali R. Kulkarni.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kulkarni, V.R., Desai, V. & Kulkarni, R.V. A comparative investigation of deterministic and metaheuristic algorithms for node localization in wireless sensor networks. Wireless Netw 25, 2789–2803 (2019). https://doi.org/10.1007/s11276-019-01994-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-019-01994-9

Keywords

Search

Navigation