A Genetic-based Algorithm to Solve Priority-based ‎Target Coverage Problem in Directional Sensor ‎Networks

Document Type : Original Article

Authors

1 Department of Computer Engineering, Gorgan Branch, Islamic Azad University, Gorgan, Iran

2 Department of Computer Engineering, Azadshahr Branch, Islamic Azad University, Azadshahr, Iran

Abstract

The Directional Sensor Networks (DSNs) have recently drawn considerable attention with respect to their extensive applications in various situations. In this regard, covering a set of targets in a specific region while maximizing network lifetime is considered as a major problem related to the DSN, which is resulted from limitation in sensing angle and battery power of directional sensors. The problem gets more challenging when the targets have different coverage quality requirements. In the present study, this problem is referred to as Priority-based Target Coverage (PTC) that has been proved to be an NP-complete problem. In this regard, a genetic-based algorithm along with a repair operator is developed, which is able to select a proper subset of directional sensors for providing the coverage quality requirements for all targets. In order to evaluate the performance of the proposed algorithm, several experiments were performed and the results were compared to those of another algorithms already introduced to literature.

Keywords


[1] M. Amac Guvensan, A. GokhanYavuz, "On coverage issues in directional sensor networks: A survey", Ad Hoc Networks, 9 (2011) 1238-1255.
[2] J. Ai, A.A. Abouzeid, "Coverage by directional sensors in randomly deployed wireless sensor networks", Journal of Combinatorial Optimization, 11 (2006)21-41.
[3] H. Mohamadi, A.S. Ismail, S. Salleh, A. Nodhei, "Learning automata-based algorithms for finding cover sets in wireless sensor networks", The Journal of Supercomputing, 66 (2013) 1533-1552.
[4] H. Mohamadi, A.S. Ismail, S. Salleh," Solving target coverage problem using cover sets in wireless sensor networks based on learning automata", Wireless Personal Communications, 75 (2014) 447-463.
[5] Y. Cai, W. Lou, M. Li, X.-Y. Li, "Energy efficient target-oriented scheduling in directional sensor networks", IEEE Trans. Comput., 58 (2009) 1259-1274.
[6] H. Mohamadi, A.S.B.H. Ismail, S. Salleh, "A learning automata-based algorithm for solving coverage problem in directional sensor networks", Computing,95 (2013) 1-24.
[7] H. Mohamadi, A.S. Ismail, S. Salleh, A. Nodehi, "Learning automata-based algorithms for solving the target coverage problem in directional sensor networks", Wireless Personal Communications, 73 (2013) 1309-1330.
[8] H. Mohamadi, A.S. Ismail, S. Salleh, "Utilizing distributed learning automatato solve the connected target coverage problem in directional sensor networks", Sensors and Actuators A: Physical, 198 (2013) 21-30.
[9] H. Mohamadi, S. Salleh, A.S. Ismail, S. Marouf, "Scheduling algorithms for extending directional sensor network lifetime", Wireless Networks, 21 (2015)611-623.
[10] H. Mohamadi, S. Salleh, M.N. Razali, S. Marouf, "A new learning automata based approach for maximizing network lifetime in wireless sensor networks with adjustable sensing ranges", Neurocomputing, 153 (2015) 11-19.
[11] H. Mohamadi, S. Salleh, M.N. Razali, Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges", J. Netw. Comput. Appl., 46 (2014) 26-35.
[12] A. Alibeiki, H. Motameni, H. Mohamadi, "A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges", Journal of Pervasive and Mobile Computing, 52 (2019), 1-12.
[13] M.N. Razali, S. Salleh, H. Mohamadi, "Solving priority-based target coverage problem in directional sensor networks with adjustable sensing ranges", Wireless Personal Communications, 95 (2017) 847-872.
[14] H. Mohamadi, S. Salleh, A.S. Ismail, "A learning automata-based solution to the priority-based target coverage problem in directional sensor networks", Wirel. Pers. Commun., 79 (2014) 2323-2338.
[15] J. Wang, C. Niu, R. Shen, "Priority-based target coverage in directional sensor networks using a genetic algorithm", Computers and Mathematics with Applications, 57 (11-12) (2009) 1915-1922.
[16] Y. Huiqiang, L. Deying, C. Hong, "Coverage quality based target-oriented scheduling in directional sensor networks", In: Proceedings of international Conference on Communications, 2010, pp. 1-5.
[17] D.E. Goldberg, "Genetic algorithms in search", optimization and machine learning", Addison-Wesley Longman Publishing Co., Inc.1989.
[18] C. Zhu, C. Zheng, L. Shu, G. Han, "A survey on coverage and connectivity issues in wireless sensor networks", J. Netw. Comput. Appl., 35 (2012) 619-632.