article

Multi-layer Genetic Algorithm for Maximum Disjoint Reliable Set Covers Problem in Wireless Sensor Networks

Authors:

Mayyadah F. Abdulhalim,

Bara'a A. AtteaAuthors Info & Claims

Wireless Personal Communications: An International Journal, Volume 80, Issue 1

Pages 203 - 227

https://doi.org/10.1007/s11277-014-2004-8

Published: 01 January 2015 Publication History

Abstract

Densely deployment of sensors is generally employed in wireless sensor networks to ensure complete target coverage for a long period of time. Many sensors scheduling techniques have been recently proposed for prolonging the network lifetime. Scheduling sensors into a maximum number of disjoint sets has been modeled, in the literature, as disjoint set covers (DSC) problem which is a well-known NP-hard optimization problem. Unlike other attempts which considers only a simple disk sensing model, this paper addresses the problem of finding the maximum number of set covers while considering a more realistic sensing model to handle uncertainty into the sensors' target-coverage reliability. The paper investigates the development of a simple multi-layer genetic algorithm (GA) whose main ingredient is to support selection of a minimum number of sensors to be assigned to maximum number of set covers. With the aid of the remaining unassigned sensors, the reliability of DSCs provided by the GA, can further be enhanced by a post-heuristic step. By identifying the upper bound of number of disjoint set covers, the GA can successively construct covers, each of which is of minimal sensor cost. Performance evaluations on solution quality in terms of both number of set covers and coverage reliability are measured and compared through extensive simulations, showing the effectiveness of the proposed GA.

References

[1]

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability. A guide to the theory of NP-completeness. New York: Freeman.

[2]

Slijepcevic, S., & Potkonjak, M. (2001). Power efficient organization of wireless sensor networks. In Proceedings of the IEEE international conference communications (Vol. 2, pp. 472---476). Finland.

[3]

Cardei, M., Thai, M., Li, Y., & Wu, W. (2005). Energy-efficient target coverage in wireless sensor networks. IEEE INFOCOM 2005, 1976---1984.

[4]

Tian, D., & Georganas, N. D. (2002). A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of the 1st association computing machinery international workshop wireless sensor network applications (pp. 32---41).

[5]

Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., & Gill, C. (2003). Integrated coverage and connectivity configuration in wireless sensor networks. In Proceedings of the 1st international conference embedded network sensor systems (pp. 28---39) Los Angeles, CA.

[6]

Liu, Y., & Liang, W. (2005). Approximate coverage in wireless sensor networks. In Proceedings of the IEEE conference local computation network 30th anniversary (pp. 68---75).

Digital Library

[7]

Gupta, H., Zhou, Z., Das, S. R., & Gu, Q. (2006). Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE/Association Computing Machinery Transactions on Networking, 14(1), 55---67.

Digital Library

[8]

Gupta, H., Zhou, Z., Das, S. R., & Gu, Q. (2006). Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE/Association Computing Machinery Transactions on Networking, 14(1), 55---67.

Digital Library

[9]

Funke, S., Kesselman, A., Kuhn, F., Lotker, Z., & Segal, M. (2007). Improved approximation algorithms for connected sensor cover. Wireless Networks, 13(2), 153---164.

Digital Library

[10]

Zhou, Z., Das, S.R., & Gupta, H. (2009). Variable radii connected sensor cover in sensor networks. IEEE/Association Computing Machinery Transactions on Networking, 5(1), 1---36. Article 8.

[11]

Martins, F. V. C., Carrano, E. G., Wanner, E. F., Takahashi, R. H. C., & Mateus, G. R. (2009). A dynamic multiobjective hybrid approach for designing wireless sensor networks. In Proceedings of the IEEE congress on evolutionary computation (pp. 1145---1152).

[12]

Cardei, M., & Du, D.-Z. (2005). Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 11(3), 333---340.

Digital Library

[13]

Cardei, I., & Cardei, M. (2008). Energy-efficient connected-coverage in wireless sensor networks. International Journal of Sensor Networks, 3(3), 201---210

[14]

He, J., Xiong, N., Xiao, Y., & Pan, Y. (2010). A reliable energy efficient algorithm for target coverage in wireless sensor networks. ICDCSW '10 Proceedings of the 2010 IEEE 30th international conference on distributed computing systems workshops (pp. 180---188).

[15]

Lai, C., Ting, C., & Ko, R. (2007). An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications. In Proceedings of the 2007 congress on evolutionary computation (pp. 3531---3538).

[16]

Hu, X.-M., Zhang, J., Yu, Y., Chung, H. S.-H., Li, Y.-L., Shi, Y.-H., et al. (2010). Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks. IEEE Transactions on Evolutionary Computation, 14(5), 766---781.

Digital Library

[17]

Gil, J.-M., & Han, Y.-H. (2011). A target coverage scheduling scheme based on genetic algorithms in directional sensor networks. Sensors, 11(2), 1888---1906.

[18]

Elfes, A. (1987). Sonar-based real-world mapping and navigation. IEEE Journal of Robotics and Automation, RA-3(3), 249---265.

[19]

Ghosh, A., & Das, S. K. (2006). Coverage and connectivity issues in wireless sensor networks, Chap. 6. In R. Shorey, A. L. Ananda, M. C. Chan, & W. T. Ooi (Eds.), Mobile, wireless, and sensor networks: Technology, applications, and future directions. New York: Wiley.

[20]

Hossain, A., Biswas, P. K., & Chakrabarti, S. (2008). Sensing models and its impact on network coverage in wireless sensor network. IEEE Region 10 Colloquium and the Third ICIIS. Kharagpur, India, Dec. 8---10.

[21]

Huang, C.-F., & Tseng, Y.-C. (2005). The coverage problem in a wireless sensor network. Mobile Networks and Applications, 10(4), 519---528.

Digital Library

[22]

Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. Chichester: Wiley.

[23]

Coello Coello, C. A., Van Veldhuizen, D. A., & Lamont, G. B. (2002). Evolutionary algorithms for solving multi-objective problems. New York: Kluwer.

[24]

Zhang, Q., & Li, H. (2007). MOEA/D: A multi-objective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712---731.

Digital Library

[25]

Coello Coello, C. A., Toscano-Pulido, G., & Salazar-Lechunga, M. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256---279.

Digital Library

Cited By

Varposhti M(2024)Distributed homology-based algorithm for solving Set k-Cover problem in heterogeneous directional sensor networksThe Journal of Supercomputing10.1007/s11227-023-05721-280:5(6946-6964)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11227-023-05721-2
Luo HJiang FLin HYao JLiu JJiang YRen J(2022)Research on energy saving algorithm of field animal monitoring based on cluster sensor networkJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-21218743:1(295-307)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/JIFS-212187
Attea BAbbas MAl-Ani MÖzdemir S(2019)Bio-inspired multi-objective algorithms for connected set K-covers problem in wireless sensor networksSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-03721-623:22(11699-11728)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s00500-018-03721-6
Show More Cited By

Multi-layer Genetic Algorithm for Maximum Disjoint Reliable Set Covers Problem in Wireless Sensor Networks
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Networks
  1. Network types

Recommendations

A survey on energy efficient coverage protocols in wireless sensor networks

A Wireless Sensor Network (WSN) is used to monitor an area for events. Each node in the WSN has a sensing range and a communication range. The sensing coverage of a sensor node is the area determined by the sensing range of the sensor node. Sensing ...
Distributed genetic algorithm for lifetime coverage optimisation in wireless sensor networks

In this paper, a protocol called distributed genetic algorithm for lifetime coverage optimisation (DiGALCO) is suggested to preserve the coverage and enhance the lifetime of a wireless sensor network (WSN). DiGALCO combines three energy-efficient schemes: ...
Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks

Efficient network coverage and connectivity are the requisites for most Wireless Sensor Network (WSN) deployments, particularly those concerned with area monitoring. Due to the resource constraints of the sensor nodes, redundancy of coverage area must ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Wireless Personal Communications: An International Journal

Wireless Personal Communications: An International Journal Volume 80, Issue 1

January 2015

431 pages

ISSN:0929-6212

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Varposhti M(2024)Distributed homology-based algorithm for solving Set k-Cover problem in heterogeneous directional sensor networksThe Journal of Supercomputing10.1007/s11227-023-05721-280:5(6946-6964)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11227-023-05721-2
Luo HJiang FLin HYao JLiu JJiang YRen J(2022)Research on energy saving algorithm of field animal monitoring based on cluster sensor networkJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-21218743:1(295-307)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.3233/JIFS-212187
Attea BAbbas MAl-Ani MÖzdemir S(2019)Bio-inspired multi-objective algorithms for connected set K-covers problem in wireless sensor networksSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-03721-623:22(11699-11728)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s00500-018-03721-6
Luo ZLi JTakadama K(2018)Genetic algorithm based sleep scheduling for maximizing lifetime of wireless sensor networksProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3205769(290-291)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3205769
Xu YZeng ZDing O(2017)An energy efficient hole repair node scheduling algorithm for WSNWireless Networks10.1007/s11276-015-1132-823:1(103-116)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s11276-015-1132-8

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents