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 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)
      • W. Contreras , S. Ziavras .
        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.
        . IET Wirel. Sens. Syst. , 1 , 26 - 33
    2. 2)
      • E.A. Zonouz , L. Xing , M.V. Vokkarane .
        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.
        . IET Wirel. Sens. Syst. , 2 , 42 - 48
    3. 3)
      • A. Ali , A. Ikpehai , B. Adebisi .
        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.
        . IET Wirel. Sens. Syst. , 3 , 74 - 81
    4. 4)
      • E.F.K. Aguiar , H.L. Roig , L.H. Mancini .
        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.
        . J. Environ. Prot. , 2 , 173 - 189
    5. 5)
      • V. Sivaraman , J. Carrapetta , K. Hu .
        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.
        . Proc. 38th Annual IEEE Conf. on Local Computer Networks-Workshops , 56 - 64
    6. 6)
      • J. Carrapetta . (2010)
        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)
      • X. Liu .
        7. Liu, X.: ‘A deployment strategy for multiple types of requirements in wireless sensor networks’, IEEE Trans. Cyber., 2015, 45, (10), pp. 23642376.
        . IEEE Trans. Cyber. , 10 , 2364 - 2376
    8. 8)
      • B. Wang .
        8. Wang, B.: ‘Coverage problems in sensor networks: survey’, ACM Comput. Surv., 2011, 43, (4), pp. 32:132:53.
        . ACM Comput. Surv. , 4 , 32:1 - 32:53
    9. 9)
      • D.S. Deif , Y. Gadallah .
        9. Deif, D.S., Gadallah, Y.: ‘Classification of wireless sensor networks deployment techniques’, IEEE Commun. Surv. Tutor., 2014, 16, (2), pp. 834855.
        . IEEE Commun. Surv. Tutor. , 2 , 834 - 855
    10. 10)
      • S. Mini , S.K. Udgata , S.L. Sabat .
        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.
        . IEEE Sens. J. , 3 , 636 - 644
    11. 11)
      • M. Erdelj , N. Mitton , T. Razafindralambo .
        11. Erdelj, M., Mitton, N., Razafindralambo, T.: ‘Robust wireless sensor network deployment’, Discrete Math. Theor. Comput. Sci., 2016, 17, (3), pp. 105130.
        . Discrete Math. Theor. Comput. Sci. , 3 , 105 - 130
    12. 12)
      • Y. Yoon , Y.-H. Kim .
        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.
        . IEEE Trans. Cybern. , 5 , 1473 - 1483
    13. 13)
      • N. Bartolini , T. Calamoneri , E.G. Fusco .
        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.
        . Wirel. Netw. , 3 , 607 - 625
    14. 14)
      • C.-Y. Chang , C.-T. Chang , Y.-C. Chen .
        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.
        . IEEE Trans. Veh. Technol. , 6 , 2925 - 2941
    15. 15)
      • M. Chaudhary , A.K. Pujari .
        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.
        . Proc. Int. Conf. Distributed Computing and Networking , 325 - 330
    16. 16)
      • Y. Gu , H. Liu , B. Zhao .
        16. Gu, Y., Liu, H., Zhao, B.: ‘Target coverage with QoS requirements in wireless sensor networks’. Proc. Intelligent Pervasive Computing, October 2007, pp. 3538.
        . Proc. Intelligent Pervasive Computing , 35 - 38
    17. 17)
      • M. Cardei , M.T. Thai , Y. Li .
        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.
        . Proc. 24th Annual Joint Conf. IEEE INFOCOM , 1976 - 1984
    18. 18)
      • Y. Wu , M. Cardei .
        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.
        . J. Comb. Opt. , 1 - 22
    19. 19)
      • J. Chen , B. Wang , W. Liu .
        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.
        . J. Netw. Comput. Appl. , 129 - 141
    20. 20)
      • X. Deng , B. Wang , C. Wang .
        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.
        . Int. J. Ad Hoc Ubiquitous Comput. , 121 - 132
    21. 21)
      • W. Ke , B. Liu , M. Tsai .
        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.
        . IEEE Trans. Comput. , 5 , 710 - 715
    22. 22)
      • H. Xu , J. Zhu , B. Wang .
        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.
        . Sensors (Basel) , 5 , 11277 - 11294
    23. 23)
      • K. Altnel , N. Aras , E. Gney .
        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.
        . Comput. Netw. , 12 , 2419 - 2431
    24. 24)
      • X. Xu , S. Sahni .
        24. Xu, X., Sahni, S.: ‘Approximation algorithms for sensor deployment’, IEEE Trans. Comput., 2007, 56, (12), pp. 16811695.
        . IEEE Trans. Comput. , 12 , 1681 - 1695
    25. 25)
      • K. Chakrabarty , S. Iyengar , H. Qi .
        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.
        . IEEE Trans. Comput. , 12 , 1448 - 1453
    26. 26)
      • J. Wang , N. Zhong .
        26. Wang, J., Zhong, N.: ‘Efficient point coverage in wireless sensor networks’, J. Comb. Optim., 2006, 11, (3), pp. 291304.
        . J. Comb. Optim. , 3 , 291 - 304
    27. 27)
      • Y. Zou , K. Chakrabarty .
        27. Zou, Y., Chakrabarty, K.: ‘Sensor deployment and target localization based on virtual forces’. Proc. IEEE Infocom Conf., March 2007, pp. 12931303.
        . Proc. IEEE Infocom Conf. , 1293 - 1303
    28. 28)
      • S.S. Dhillon , K. Chakrabarty .
        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.
        . Proc. IEEE Wireless Communication and Networking Conf. , 1609 - 1614
    29. 29)
      • F. Lin , P. Chiu .
        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.
        . IEEE Commun. Lett. , 1 , 43 - 45
    30. 30)
      • O. Banimelhem , M. Mowafi , W. Aljoby .
        30. Banimelhem, O., Mowafi, M., Aljoby, W.: ‘Genetic algorithm based node deployment in hybrid wireless sensor networks’, Commun. Netw., 2013, 5, (4), pp. 273279.
        . Commun. Netw. , 4 , 273 - 279
    31. 31)
      • T.E. Kalayci , A. Ugur .
        31. Kalayci, T.E., Ugur, A.: ‘Genetic algorithm-based sensor deployment with area priority’, Cybern. Syst., 2011, 42, (8), pp. 605620.
        . Cybern. Syst. , 8 , 605 - 620
    32. 32)
      • J.-H. Seo , Y.-H. Kim , H.-B. Ryou .
        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.
        . IEICE Trans. Commun. , 11 , 3534 - 3543
    33. 33)
      • Q. Wu , N.S.V. Rao , X. Du .
        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.
        . Comput. Commun. , 2721 - 2734
    34. 34)
      • C. Zhao , Z. Yu , P. Chen .
        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.
        . Proc. IEEE Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom) , 2743 - 2746
    35. 35)
      • J. Jia , J. Chen , G. Chang .
        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.
        . Comput. Math. Appl. , 1756 - 1766
    36. 36)
      • E. Tonye , W. Tsague , R. Bateki . (2015)
        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)
      • R. Kershner .
        37. Kershner, R.: ‘The number of circles covering a set’, Am. J. Math., 1939, 61, (3), pp. 665671.
        . Am. J. Math. , 3 , 665 - 671
    38. 38)
      • E.W. Weisstein .
        38. Weisstein, E.W.: ‘Fractal Dimension’. http://mathworld.wolfram.com/FractalDimension.html, accessed 5 December 2016.
        .
    39. 39)
      • E. Welzl . (1991)
        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