A new learning automata-based algorithm to solve the target k-coverage problem in wireless sensor networks
Subject Areas : Electrical Engineeringleila ajam 1 , ali Nodehi 2 , Hosein Mohamadi 3
1 - Department of Computer,aliabad katoul Branch, Islamic Azad University,aliabad katoul, Iran.
2 - گروه کامپیوتر، واحد گرگان، دانشگاه آزاد اسلامی، گرگان، ایران
3 - Department of Computer Engineering, Azadshahr Branch, Islamic Azad University, Azadshahr, Iran
Keywords: Wireless sensor networks, Cover set formation, Learning automata, k-coverage,
Abstract :
Recently, a number of algorithms have been proposed to solve the target coverage problem in wireless sensor networks (WSNs). Conventionally, it is assumed that only a single sensor is sufficient for covering a target; though, in real situations, more than one sensor may be required for this purpose. This problem is known as k-coverage problem that its NP-completeness has been already proved. To solve the problem, this paper proposes a learning-automata based algorithm equipped with a pruning rule. The aim of the proposed algorithm is to determine minimum number of sensors in such a way that each target can be monitored for at least k times. The proposed algorithm performance was evaluated through conducting a number of experiments. The experimental results were compared to those of a greedy-based algorithm. As shown by the final results, the learning-automata based algorithm was more successful than the greedy-based one regarding the construction of cover sets with minimum number of sensors.
[1] H. Mohamadi, S. Salleh, M.N. Razali, S. Marouf, A new learning automatabased approach for maximizing network lifetime in wireless sensor networks with adjustable sensing ranges, Neurocomputing, 153 (2015) 11-19.
[2] J. Yick, B. Mukherjee, D. Ghosal, Wireless sensor network survey, Computer Networks, 52 (2008) 2292-2330.
[3] C. Zhu, C. Zheng, L. Shu, G. Han, A survey on coverage and connectivity issues in wireless sensor networks, Journal of Network and Computer Applications, 35 (2012) 619-632.
[4] H. Mohamadi, S. Salleh, M.N. Razali, Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges, Journal of Network and Computer Applications, 46 (2014) 26-35.
[5] M. Cardei, M.T. Thai, L. Yingshu, W. Weili, Energy-efficient target coverage in wireless sensor networks, In Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1976-1984 vol. 1973.
[6] M. Cardei, D.Z. Du, Improving wireless sensor network lifetime through power aware organization, Wireless Network, 11 (2005) 333-340.
[7] D. Zorbas, D. Glynos, P. Kotzanikolaou, C. Douligeris, Solving coverage problems in wireless sensor networks using cover sets, Ad Hoc Networks, 8 (2010) 400-415.
[8] C.K. Ting, C.C. Liao, A memetic algorithm for extending wireless sensor network lifetime, Information Sciences, 180 (2010) 4818-4833.
[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. Mostafaei, M. Meybodi, Maximizing lifetime of target coverage in wireless sensor networks using learning automata, Wireless Pers Commun, 71 (2013) 1461-1477.
[11] H. Mohamadi, A. Ismail, S. Salleh, A. Nodhei, Learning automata-based algorithms for finding cover sets in wireless sensor networks, J Supercomput, 66 (2013) 1533-1552.
[12] H. Mohamadi, A. 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.
[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, Wireless Personal Communications, 79 (2014) 2323-2338.
[15] K. Najim, A.S. Poznyak, Learning automata: theory and applications. New York: Printice-Hall, 1994.
[16] M.A.L. Thathachar, B.R. Harita, Learning automata with changing number of actions, IEEE Trans. Syst. Man Cybern., 17 (1987) 1095-1100.
[17] H. Mohamadi, A.S. Ismail, S. Salleh, A learning automata-based algorithm for solving coverage problem in directional sensor networks, Computing, 95 (2013) 1-24.
[18] H. Mohamadi, A. 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.
[19] H. Mohamadi, A.S. Ismail, S. Salleh, Utilizing distributed learning automata to solve the connected target coverage problem in directional sensor networks, Sensors and Actuators A: Physical, 198 (2013) 21-30.
[20] H.M. Ammari, On the problem of k-coverage in mission-oriented mobile wireless sensor networks, Computer Networks, 56 (2012) 1935-1950.
[21] J. Yu, X. Deng, D. Yu, G. Wang, X. Gu, CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks, AEU – International Journal of Electronics and Communications, 67 (2013) 937-946.
[22] S.K. Gupta, P. Kuila, P.K. Jana, Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks, Computers & Electrical Engineering, 56 (2016) 544-556.
[23] R. Cerulli, R. De Donato, A. Raiconi, Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges, European Journal of Operational Research, 220 (2012) 58-66.
