Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Efficient scalable sensor node placement algorithm for fixed target coverage applications of wireless sensor networks

© The Institution of Engineering and Technology
Received 28/08/2016, Accepted 09/01/2017, Revised 09/12/2016, Published 12/01/2017

Large applications of sensor networks, such as environmental risk monitoring, require the deployment of hundreds or even thousands of nodes. This study proposes and implements a novel stochastic physics-based optimisation algorithm that is both efficient (guarantees full target coverage with a reduced number of sensors) and scalable (meaning that it can be executed for very large-scale problems in a reasonable computation time). The algorithm employs ‘virtual sensors’ which move, merge, recombine, and ‘explode’ during the course of the algorithm, where the process of merging and recombining virtual sensors reduces the number of actual sensors while maintaining full coverage. The parameters which control sensor merging and explosion are varied during the algorithm to perform the same function as an annealing schedule in simulated annealing. Simulation results illustrate the rapidity and the effectiveness of the proposed method.

Inspec keywords: sensor placement; wireless sensor networks; simulated annealing

Other keywords: wireless sensor networks; simulated annealing; fixed target coverage applications; environmental risk monitoring; virtual sensors; annealing schedule; stochastic physics-based optimisation algorithm; scalable sensor node placement algorithm

Subjects: Optimisation techniques; Wireless sensor networks

References

    1. 1)
      • 21. Ke, W., Liu, B., Tsai, M.: ‘Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is np-complete’, IEEE Trans. Comput., 2007, 56, (5), pp. 710–715.
    2. 2)
      • 35. Jia, J., Chen, J., Chang, G., et al: ‘Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm’, Comput. Math. Appl., 2009, 57, (11-12), pp. 1756–1766.
    3. 3)
      • 38. Weisstein, E.W.: ‘Fractal Dimension’. http://mathworld.wolfram.com/FractalDimension.html, accessed 5 December 2016.
    4. 4)
      • 25. Chakrabarty, K., Iyengar, S., Qi, H., et al: ‘Grid coverage for surveillance and target location in distributed sensor networks’, IEEE Trans. Comput., 2002, 51, (12), pp. 1448–1453.
    5. 5)
      • 10. Mini, S., Udgata, S.K., Sabat, S.L.: ‘Sensor deployment and scheduling for target coverage problem in wireless sensor networks’, IEEE Sens. J., 2014, 14, (3), pp. 636–644.
    6. 6)
      • 16. Gu, Y., Liu, H., Zhao, B.: ‘Target coverage with QoS requirements in wireless sensor networks’. Proc. Intelligent Pervasive Computing, October 2007, pp. 35–38.
    7. 7)
      • 22. Xu, H., Zhu, J., Wang, B.: ‘On the deployment of a connected sensor network for confident information coverage’, Sensors (Basel), 2015, 15, (5), pp. 11277–11294.
    8. 8)
      • 23. Altnel, K., Aras, N., Gney, E., et al: ‘Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks’, Comput. Netw., 2008, 52, (12), pp. 2419–2431.
    9. 9)
      • 12. Yoon, Y., Kim, Y.-H.: ‘An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks’, IEEE Trans. Cybern., 2013, 43, (5), pp. 1473–1483.
    10. 10)
      • 32. Seo, J.-H., Kim, Y.-H., Ryou, H.-B., et al: ‘Optimal sensor deployment for wireless surveillance sensor networks by a hybrid steady-state genetic algorithm’, IEICE Trans. Commun., 2008, E91-B, (11), pp. 3534–3543.
    11. 11)
      • 7. Liu, X.: ‘A deployment strategy for multiple types of requirements in wireless sensor networks’, IEEE Trans. Cyber., 2015, 45, (10), pp. 2364–2376.
    12. 12)
      • 14. Chang, C.-Y., Chang, C.-T., Chen, Y.-C., et al: ‘Obstacle-resistant deployment algorithms for wireless sensor networks’, IEEE Trans. Veh. Technol., 2009, 58, (6), pp. 2925–2941.
    13. 13)
      • 2. Zonouz, E.A., Xing, L., Vokkarane, M.V., et al: ‘Hybrid wireless sensor networks: a reliability, cost and energy-aware approach’, IET Wirel. Sens. Syst., 2016, 6, (2), pp. 42–48.
    14. 14)
      • 26. Wang, J., Zhong, N.: ‘Efficient point coverage in wireless sensor networks’, J. Comb. Optim., 2006, 11, (3), pp. 291–304.
    15. 15)
      • 9. Deif, D.S., Gadallah, Y.: ‘Classification of wireless sensor networks deployment techniques’, IEEE Commun. Surv. Tutor., 2014, 16, (2), pp. 834–855.
    16. 16)
      • 1. Contreras, W., Ziavras, S.: ‘Wireless sensor network-based pattern matching technique for the circumvention of environmental and stimuli-related variability in structural health monitoring’, IET Wirel. Sens. Syst., 2016, 6, (1), pp. 26–33.
    17. 17)
      • 37. Kershner, R.: ‘The number of circles covering a set’, Am. J. Math., 1939, 61, (3), pp. 665–671.
    18. 18)
      • 30. Banimelhem, O., Mowafi, M., Aljoby, W.: ‘Genetic algorithm based node deployment in hybrid wireless sensor networks’, Commun. Netw., 2013, 5, (4), pp. 273–279.
    19. 19)
      • 8. Wang, B.: ‘Coverage problems in sensor networks: survey’, ACM Comput. Surv., 2011, 43, (4), pp. 32:1–32:53.
    20. 20)
      • 29. Lin, F., Chiu, P.: ‘A near-optimal sensor placement algorithm to achieve complete coverage-discrimination in sensor networks’, IEEE Commun. Lett., 2005, 9, (1), pp. 43–45.
    21. 21)
      • 24. Xu, X., Sahni, S.: ‘Approximation algorithms for sensor deployment’, IEEE Trans. Comput., 2007, 56, (12), pp. 1681–1695.
    22. 22)
      • 27. Zou, Y., Chakrabarty, K.: ‘Sensor deployment and target localization based on virtual forces’. Proc. IEEE Infocom Conf., March 2007, pp. 1293–1303.
    23. 23)
      • 15. Chaudhary, M., Pujari, A.K.: ‘Q-coverage problem in wireless sensor networks’. Proc. Int. Conf. Distributed Computing and Networking, India, January 2009, pp. 325–330.
    24. 24)
      • 28. Dhillon, S.S., Chakrabarty, K.: ‘Sensor placement for effective coverage and surveillance in distributed sensor networks’. Proc. IEEE Wireless Communication and Networking Conf., New Orleans, LA, USA, March 2003, pp. 1609–1614.
    25. 25)
      • 39. Welzl, E.: ‘Smallest enclosing disks (balls and ellipsoids)’, in Maurer, H. (ED.): ‘New results and new trends in computer sciences’, 1991, vol. 555, pp. 359–370.
    26. 26)
      • 33. Wu, Q., Rao, N.S.V., Du, X., et al: ‘On efficient deployment of sensors on planar grid’, Comput. Commun., 2007, 30, (14-15), pp. 2721–2734.
    27. 27)
      • 13. Bartolini, N., Calamoneri, T., Fusco, E.G., et al: ‘Push & pull: autonomous deployment of mobile sensors for a complete coverage’, Wirel. Netw., 2010, 16, (3), pp. 607–625.
    28. 28)
      • 36. Tonye, E., Tsague, W., Bateki, R.: ‘Réalisation dd'un capteur de pollution et rapatriement des donnes vers un SIG web’ (University of Yaounde I, National Advanced School of Engineering, Yaounde, Cameroon, 2015), pp. 1–75.
    29. 29)
      • 6. Carrapetta, J.: ‘Haze watch: design of a wireless sensor board for measuring air pollution’ (University of New South Wales, Sydney, Australia, 2010), pp. 1–67.
    30. 30)
      • 3. Ali, A., Ikpehai, A., Adebisi, B., et al: ‘Location prediction optimisation in WSNs using Kriging interpolation’, IET Wirel. Sens. Syst., 2016, 6, (3), pp. 74–81.
    31. 31)
      • 11. Erdelj, M., Mitton, N., Razafindralambo, T.: ‘Robust wireless sensor network deployment’, Discrete Math. Theor. Comput. Sci., 2016, 17, (3), pp. 105–130.
    32. 32)
      • 17. Cardei, M., Thai, M.T., Li, Y., et al: ‘Energy-efficient target coverage in wireless sensor networks’. Proc. 24th Annual Joint Conf. IEEE INFOCOM, March 2005, pp. 1976–1984.
    33. 33)
      • 31. Kalayci, T.E., Ugur, A.: ‘Genetic algorithm-based sensor deployment with area priority’, Cybern. Syst., 2011, 42, (8), pp. 605–620.
    34. 34)
      • 20. Deng, X., Wang, B., Wang, C., et al: ‘Barrier coverage in wireless sensor networks with adjustable sensing ranges’, Int. J. Ad Hoc Ubiquitous Comput., 2014, 15, (1/2/3), pp. 121–132.
    35. 35)
      • 19. Chen, J., Wang, B., Liu, W.: ‘Constructing perimeter barrier coverage with bistatic radar sensors’, J. Netw. Comput. Appl., 2015, 57, pp. 129–141, http://dx.doi.org/10.1016/j.jnca.2015.07.015, accessed 13 June 2016.
    36. 36)
      • 18. Wu, Y., Cardei, M.: ‘Distributed algorithms for barrier coverage via sensor rotation in wireless sensor networks’, J. Comb. Opt., 2016, pp. 1–22, doi:10.1007/s10878-016-0055-3.
    37. 37)
      • 4. Aguiar, E.F.K., Roig, H.L., Mancini, L.H., et al: ‘Low-cost sensors calibration for monitoring air quality in the federal district-Brazil’, J. Environ. Prot., 2015, 6, (2), pp. 173–189.
    38. 38)
      • 5. Sivaraman, V., Carrapetta, J., Hu, K., et al: ‘Hazewatch: a participatory sensor system for monitoring air pollution in Sydney’. Proc. 38th Annual IEEE Conf. on Local Computer Networks-Workshops, Sydney, Australia, 2013, pp. 56–64.
    39. 39)
      • 34. Zhao, C., Yu, Z., Chen, P.: ‘Optimal deployment of nodes based on genetic algorithm in heterogeneous sensor networks’. Proc. IEEE Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom), September 2007, pp. 2743–2746.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-wss.2016.0076
Loading

Related content

content/journals/10.1049/iet-wss.2016.0076
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address