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