الگوریتم جدید مبتنی بر اتومات یادگیری برای حل مسئله پوشش k هدف در شبکه های حسگر بی سیم
محورهای موضوعی : Electrical Engineering
لیلا عجم
1
(گروه کامپیوتر، واحد علی آباد کتول، دانشگاه آزاد اسلامی، علی آباد کتول، ایران)
ali Nodehi
2
(گروه کامپیوتر، واحد گرگان، دانشگاه آزاد اسلامی، گرگان، ایران)
Hosein Mohamadi
3
(Department of Computer Engineering, Azadshahr Branch, Islamic Azad University, Azadshahr, Iran)
کلید واژه: شبکه های حسگر بی سیم, تشکیل مجموعه پوشش, اتوماتای یادگیری, پوشش kگانه,
چکیده مقاله :
اخیراً تعدادی الگوریتم برای حل مشکل پوشش هدف در شبکه های حسگر بی سیم (WSN) پیشنهاد شده است. به طور معمول، فرض بر این است که تنها یک سنسور برای پوشش یک هدف کافی است. اگرچه در شرایط واقعی ممکن است بیش از یک سنسور برای این منظور مورد نیاز باشد. این مشکل به عنوان مشکل پوشش kگانه شناخته می شود که NP-کامل بودن آن قبلاً ثابت شده است. برای حل مشکل، این مقاله یک الگوریتم مبتنی بر اتومات یادگیری مجهز به یک قانون هرس را پیشنهاد می‌کند. هدف از الگوریتم پیشنهادی تعیین حداقل تعداد حسگرها به گونه ای است که هر هدف حداقل k بار قابل نظارت باشد. عملکرد الگوریتم پیشنهادی از طریق انجام تعدادی آزمایش ارزیابی شد. نتایج تجربی با نتایج یک الگوریتم مبتنی بر حریصانه مقایسه شد. همانطور که در نتایج نهایی نشان داده شد، الگوریتم مبتنی بر اتوماتای یادگیری موفق‌تر از الگوریتم مبتنی بر حریصانه در ساخت مجموعه‌های پوششی با حداقل تعداد سنسور بود.
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.