http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Wireless Sensor Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • 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. 2633.
    2. 2)
      • 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. 4248.
    3. 3)
      • 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. 7481.
    4. 4)
      • 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. 173189.
    5. 5)
      • 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. 5664.
    6. 6)
      • 6. Carrapetta, J.: ‘Haze watch: design of a wireless sensor board for measuring air pollution’ (University of New South Wales, Sydney, Australia, 2010), pp. 167.
    7. 7)
      • 7. Liu, X.: ‘A deployment strategy for multiple types of requirements in wireless sensor networks’, IEEE Trans. Cyber., 2015, 45, (10), pp. 23642376.
    8. 8)
      • 8. Wang, B.: ‘Coverage problems in sensor networks: survey’, ACM Comput. Surv., 2011, 43, (4), pp. 32:132:53.
    9. 9)
      • 9. Deif, D.S., Gadallah, Y.: ‘Classification of wireless sensor networks deployment techniques’, IEEE Commun. Surv. Tutor., 2014, 16, (2), pp. 834855.
    10. 10)
      • 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. 636644.
    11. 11)
      • 11. Erdelj, M., Mitton, N., Razafindralambo, T.: ‘Robust wireless sensor network deployment’, Discrete Math. Theor. Comput. Sci., 2016, 17, (3), pp. 105130.
    12. 12)
      • 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. 14731483.
    13. 13)
      • 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. 607625.
    14. 14)
      • 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. 29252941.
    15. 15)
      • 15. Chaudhary, M., Pujari, A.K.: ‘Q-coverage problem in wireless sensor networks’. Proc. Int. Conf. Distributed Computing and Networking, India, January 2009, pp. 325330.
    16. 16)
      • 16. Gu, Y., Liu, H., Zhao, B.: ‘Target coverage with QoS requirements in wireless sensor networks’. Proc. Intelligent Pervasive Computing, October 2007, pp. 3538.
    17. 17)
      • 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. 19761984.
    18. 18)
      • 18. Wu, Y., Cardei, M.: ‘Distributed algorithms for barrier coverage via sensor rotation in wireless sensor networks’, J. Comb. Opt., 2016, pp. 122, doi:10.1007/s10878-016-0055-3.
    19. 19)
      • 19. Chen, J., Wang, B., Liu, W.: ‘Constructing perimeter barrier coverage with bistatic radar sensors’, J. Netw. Comput. Appl., 2015, 57, pp. 129141, http://dx.doi.org/10.1016/j.jnca.2015.07.015, accessed 13 June 2016.
    20. 20)
      • 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. 121132.
    21. 21)
      • 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. 710715.
    22. 22)
      • 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. 1127711294.
    23. 23)
      • 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. 24192431.
    24. 24)
      • 24. Xu, X., Sahni, S.: ‘Approximation algorithms for sensor deployment’, IEEE Trans. Comput., 2007, 56, (12), pp. 16811695.
    25. 25)
      • 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. 14481453.
    26. 26)
      • 26. Wang, J., Zhong, N.: ‘Efficient point coverage in wireless sensor networks’, J. Comb. Optim., 2006, 11, (3), pp. 291304.
    27. 27)
      • 27. Zou, Y., Chakrabarty, K.: ‘Sensor deployment and target localization based on virtual forces’. Proc. IEEE Infocom Conf., March 2007, pp. 12931303.
    28. 28)
      • 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. 16091614.
    29. 29)
      • 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. 4345.
    30. 30)
      • 30. Banimelhem, O., Mowafi, M., Aljoby, W.: ‘Genetic algorithm based node deployment in hybrid wireless sensor networks’, Commun. Netw., 2013, 5, (4), pp. 273279.
    31. 31)
      • 31. Kalayci, T.E., Ugur, A.: ‘Genetic algorithm-based sensor deployment with area priority’, Cybern. Syst., 2011, 42, (8), pp. 605620.
    32. 32)
      • 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. 35343543.
    33. 33)
      • 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. 27212734.
    34. 34)
      • 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. 27432746.
    35. 35)
      • 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. 17561766.
    36. 36)
      • 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. 175.
    37. 37)
      • 37. Kershner, R.: ‘The number of circles covering a set’, Am. J. Math., 1939, 61, (3), pp. 665671.
    38. 38)
      • 38. Weisstein, E.W.: ‘Fractal Dimension’. http://mathworld.wolfram.com/FractalDimension.html, accessed 5 December 2016.
    39. 39)
      • 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. 359370.
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
This is a required field
Please enter a valid email address