A Hybrid Algorithm for Q-coverage Problem in Under Provisioned Directional Sensor Networks

Subject Areas : Computer Engineering

Babak Mahmoudi ¹ , Homayoon Motameni ² , Hosein Mohamadi ³

1 -
2 -
3 -

Received: 2025-04-14 Accepted : 2025-06-01 Published : 2025-06-25

Keywords: Coverage, Genetics Algorithm, Tabu Search,

Abstract :

In the context of emerging technologies like the Internet of Things (IoT) and home automation, researchers are increasingly exploring the use of Wireless Sensor Networks (WSNs). One of the primary functions of these sensors is coverage, which refers to how effectively they can monitor targets within a given environment. In many applications, it is essential that each target is covered by at least one sensor; this is known as "Simple Coverage." In other cases, multiple sensors may be required to cover a single target, a situation referred to as "Multiple Coverage." When the number of sensors covering a target can vary, it is termed "Q-coverage." When there are not enough sensors in an environment, achieving balanced coverage becomes critical. To address this challenge, current research presents a hybrid algorithm that combines genetic algorithms and Tabu Search as a promising solution for monitoring targets in such under-provisioned environments. To evaluate the effectiveness of this proposed algorithm, several experiments were conducted, and the results were compared with those obtained from a genetic algorithm introduced in recent studies.

References:

[1] Ajam, Leila, Ali Nodehi, and Hosein Mohamadi. "A Genetic-based algorithm to solve priority-based target coverage problem in directional sensor networks." Journal of Applied Dynamic Systems and Control 4.1 (2021): 89-96.‏
[2] N. Mottaki, H. Motameni, H. Mohamadi, Multi-objective optimization for coverage aware sensor node scheduling in directional sensor networks, J. Appl. Dyn. Syst. Control (2021) 43–52.
[3] L. Ajam, A. Nodehi and H. Mohamadi, "A new approach to solving target coverage problem in wireless sensor networks using an effective hybrid genetic algorithm and tabu search", J. Intell. Fuzzy Syst., vol. 42, no. 6, pp. 6245-6255, 2022.
[4] Mottaki NA, Motameni H, Mohamadi H (2022) A genetic algorithm-based approach for solving the target Q-coverage problem in over and under provisioned directional sensor networks. Phys Commun 54:101719. https:// doi. org/ 10. 1016/j. phycom. 2022. 101719.
[5] Mottaki, Nemat allah, Homayun Motameni, and Hosein Mohamadi. "An effective hybrid genetic algorithm and tabu search for maximizing network lifetime using coverage sets scheduling in wireless sensor networks." The Journal of Supercomputing 79.3 (2023): 3277-3297.‏
[6] Jing Ai, et al., Coverage by directional sensors in randomly deployed wireless sensor networks, J. Comb. Optim. 11 (1) (2006) 21–41.
[7] H. Mohamadi, et al., Heuristic methods to maximize network lifetime indirectional sensor networks with adjustable sensing ranges, 46 (2014)26–35.
[8] A. Alibeiki, et al., A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges, 52(2019) 1–12.
[9] Manju, et al., Target K-coverage problem in wireless sensor networks, 23(2) (2020) 651–659.
[10] A. Javan Bakht, H. Motameni, H. Mohamadi, A learning automata-based algorithm for solving the target K-coverage problem in directional sensor networks with adjustable sensing ranges, Phys. Commun. 42 (2020)101156.
[11] S.M.B. Malek, et al., On balanced K-coverage in visual sensor networks, 72(2016) 72–86.
[12] A. Javan Bakht, et al., A learning automata-based algorithm to solve imbalanced K-coverage in visual sensor networks, J. Intell. Fuzzy Systems39 (3) (2020) 2817–2829.
[13] A. Alibeiki, et al., A new genetic-based approach for solving K-coverage problem in directional sensor networks, 154 (2021) 16–26.
[14] Y. Gu, et al., Qos-aware target coverage in wireless sensor networks, 9 (12)(2009) 1645–1659.
[15] M. Chaudhary, A.K. Pujari, Q-coverage problem in wireless sensor networks, in: International Conference on Distributed Computing and Networking, Springer, 2009.
[16] D. Arivudainambi, et al., Energy efficient sensor scheduling for Q-coverage problem, in: 2017 IEEE 22nd International Workshop on Computer Aided Modeling and Design of Communication Links and Networks, CAMAD, IEEE,2017.
[17] A. Al Zishan, et al., Maximizing heterogeneous coverage in over and under provisioned visual sensor networks, 124 (2018) 44–62.
[18] S. Sivanandam, S. Deepa, Genetic algorithms, in: Introduction to Genetic Algorithms, Springer, 2008, pp. 15–37.
[19] R. Asorey-Cacheda, et al., A survey on non-linear optimization problems in wireless sensor networks, 82 (2017) 1–20.
[20]D.E. Goldberg, Genetic Algorithms, Pearson Education India, 2006.
[21] Prajapati V, p et al Tabu Search Algorithm (TSA): A Comprehensive Survey. In:2020 3rd International Conference on emerging technologies in computer engineering: Machine Learning and Internet of Things (ICETCE), https:// doi. org/10. 1109/ICETC E48199. 2020. 091743.