توازن بار در گره‌های مه با استفاده از الگوریتم یادگیری تقویتی
محورهای موضوعی : مهندسی برق و کامپیوتر
نیلوفر طهماسبی پویا
1
(دانشگاه یزد)
مهدی آقا صرام
2
(دانشگاه یزد)
کلید واژه: تأخیر, توازن بار, گره مه, یادگیری تقویتی, Q-Learning,
چکیده مقاله :
محاسبات مه، حوزه تحقیقاتی نوظهوری برای ارائه خدمات محاسبات ابری به لبه‌های شبکه است. گره‌های مه جریان داده و درخواست‌های کاربر را در زمان واقعی پردازش می‌کنند. به منظور بهینه‌سازی بهره‌وری منابع و زمان پاسخ و افزایش سرعت و کارایی، وظایف باید به صورت متوازن بین گره‌های مه توزیع شوند، لذا در این مقاله، روشی جدید جهت بهبود توازن بار در محیط محاسبات مه پیشنهاد شده است. در الگوریتم پیشنهادی، هنگامی که وظیفه‌ای از طریق دستگاه‌های موبایل برای گره مه ارسال می‌شود، گره مه با استفاده از یادگیری تقویتی تصمیم می‌گیرد که آن وظیفه را خودش پردازش کند، یا این که پردازش آن را به یکی از گره‌های مه همسایه یا به ابر واگذار نماید. در بخش ارزیابی نشان داده شده که الگوریتم پیشنهادی با توزیع مناسب وظایف بین گره‌ها، تأخیر کمتری را برای اجرای وظایف نسبت به سایر روش‌های مقایسه‌شده به دست آورده است.
Fog computing is an emerging research field for providing cloud computing services to the edges of the network. Fog nodes process data stream and user requests in real-time. In order to optimize resource efficiency and response time, increase speed and performance, tasks must be evenly distributed among the fog nodes. Therefore, in this paper, a new method is proposed to improve the load balancing in the fog computing environment. In the proposed algorithm, when a task is sent to the fog node via mobile devices, the fog node using reinforcement learning decides to process that task itself, or assign it to one of the neighbor fog nodes or cloud for processing. The evaluation shows that the proposed algorithm, with proper distribution of tasks between nodes, has less delay to tasks processing than other compared methods.
[1] I. Martinez, A. S. Hafid, and A. Jarray, "Design, resource management, and evaluation of fog computing systems: a survey," IEEE Internet of Things J., vol. 8, no. 4, pp. 2494-2516, Feb. 2020.
[2] A. Yousefpour, et al., "All one needs to know about fog computing and related edge computing paradigms: a complete survey," J. of Systems Architecture, vol. 98, pp. 289-330, Sept. 2019.
[3] D. Puthal, et al., "Secure authentication and load balancing of distributed edge data centers," J. of Parallel and Distributed Computing, vol. 124, pp. 60-69, Feb. 2019.
[4] N. Khattar, J. Sidhu, and J. Singh, "Toward energy-efficient cloud computing: a survey of dynamic power management and heuristics-based optimization techniques," The J. of Supercomputing, vol. 75, no. 8, pp. 4750-4810, Aug. 2019.
[5] M. Adhikari and T. Amgoth, "Heuristic-based load-balancing algorithm for IaaS cloud," Future Generation Computer Systems, vol. 81, pp. 156-165, Apr. 2018.
[6] S. Rasheed, et al., " A cloud-fog based smart grid model using max-min scheduling algorithm for efficient resource allocation," in Proc. Int. Conf. on Network-Based Information Systems, vol. 22, pp. 273-285, Sept. 2018.
[7] L. Abualigah et al., "Advances in meta-heuristic optimization algorithms in big data text clustering," Electronics, vol. 10, no. 2, Article ID: 101, 2021.
[8] M. Adhikari, S. Nandy, and T. Amgoth, "Meta heuristic-based task deployment mechanism for load balancing in IaaS cloud," J. of Network and Computer Applications, vol. 128, pp. 64-77, Feb. 2019.
[9] L. Shen, J. Li, Y. Wu, Z. Tang, and Y. Wang, "Optimization of artificial bee colony algorithm based load balancing in smart grid cloud," in Proc. of the IEEE Inovative Smart Grid Technologies-Asia, ISGT Asia, pp. 1131-1134, Chengdu, China, 21-24 May 2019.
[10] B. Kruekaew and W. Kimpan, "Multi-objective task scheduling optimization for load balancing in cloud computing environment using hybrid artificial bee colony algorithm with reinforcement learning," IEEE Access, vol. 10, pp. 17803-17818, 2022.
[11] S. R. Deshmukh, S. K. Yadav, and D. N. Kyatanvar, "Load balancing in cloud environs: optimal task scheduling via hybrid algorithm," International J. of Modeling, Simulation, and Scientific Computing, vol. 12, no. 2, Article ID: 2150008, Apr. 2021.
[12] M. M. Golchi, S. Saraeian, and M. Heydari, "A hybrid of firefly and improved particle swarm optimization algorithms for load balancing in cloud environments: performance evaluation," Computer Networks, vol. 162, Article ID: 106860, Oct. 2019.
[13] J. Y. Baek, G. Kaddoum, S. Garg, K. Kaur, and V. Gravel, "Managing fog networks using reinforcement learning based load balancing algorithm," in Proc. of the IEEE Wireless Communications and Networking Conf., WCNC’19, 7 pp., Marrakesh, Morocco, 15-18 Apr. 2019.
[14] X. Xu, S. Fu, Q. Cai, W. Tian, W. Liu, W. Dou, X. Sun, and A. X. Liu, "Dynamic resource allocation for load balancing in fog environment," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 6421607, Apr. 2018.
[15] A. B. Manju and S. Sumathy, "Efficient load balancing algorithm for task preprocessing in fog computing environment," In Smart Intelligent Computing and Applications, Springer, Singapore, vol. 105, pp. 291-298, 2019.
[16] S. Sharma and H. Saini, "A novel four-tier architecture for delay aware scheduling and load balancing in fog environment," Sustainable Computing: Informatics and Systems, vol. 24, Article ID: 100355, Dec. 2019.
[17] F. M. Talaat, M. S. Saraya, A. I. Saleh, H. A. Ali, and S. H. Ali, "A load balancing and optimization strategy (LBOS) using reinforcement learning in fog computing environment," J. of Ambient Intelligence and Humanized Computing, vol. 11, no. 11, pp. 4951-4966, Nov. 2020.
[18] V. Divya and R. L. Sri, "ReTra: reinforcement based traffic load balancer in fog based network," in Proc. of the 10th Int. Conf. on Computing, Communication and Networking Technologies, ICCCNT’19, 6 pp., Kanpur, India, 6-8 Jul. 2019.
[19] H. Lu, C. Gu, F. Luo, W. Ding, and X. Liu, "Optimization of lightweight task offloading strategy for mobile edge computing based on deep reinforcement learning," Future Generation Computer Systems, vol. 102, pp. 847-861, Jan. 2020.
[20] R. Beraldi, C. Canali, R. Lancellotti, and G. P. Mattia, "A random walk based load balancing algorithm for fog computing," in Proc. of the Fifth Int. Conf. on Fog and Mobile Edge Computing, FMEC’20, pp. 46-53, Paris, France 20-23 Apr. 2020.
[21] F. M. Talaat, S. H. Ali, A. I. Saleh, and H. A. Ali, "Effective load balancing strategy (ELBS) for real-time fog computing environment using fuzzy and probabilistic neural networks," J. of Network and Systems Management, vol. 27, no. 4, pp. 883-929, Oct. 2019.
[22] H. Gupta, A. V. Dastjerdi, S. K. Ghosh, and R. Buyya, "iFogSim: a toolkit for modeling and simulation of resource management techniques in the Internet of Things, edge and fog computing environments," Software-Practice and Experience, vol. 47, no. 9, pp. 1275-1296, Sep. 2017.
[23] J. Xie, F. R. Yu, T. Huang, R. Xie, J. Liu, C. Wang, and Y. Liu, "A survey of machine learning techniques applied to software defined networking (SDN): research issues and challenges," IEEE Communications Surveys and Tutorials, vol. 21, no. 1, pp. 393-430, Aug. 2019.
[24] H. Ye, L. Liang, G. Y. Li, J. Kim, L. Lu, and M. Wu, "Machine learning for vehicular networks: recent advances and application examples," IEEE Vehicular Technology Magazine, vol. 13, no. 2, pp. 94-101, Apr. 2018.
[25] R. Sheikhpour, M. A. Sarram, S. Gharaghani, and M. A. Z. Chahooki, "A survey on semi-supervised feature selection methods," Pattern Recognition, vol. 64, pp. 141-158, Apr. 2017.
[26] A. Mebrek, M. Esseghir, and L. Merghem-Boulahia, "Energy-efficient solution based on reinforcement learning approach in fog networks," Proc. of the Fifth 15th Int. Wireless Communications & Mobile Computing Conf., IWCMC’19, pp. 2019-2024, Tangier, Morocco, 24-28 Jun. 2019.
[27] Y. Xu, W. Xu, Z. Wang, J. Lin, and S. Cui, "Load balancing for ultradense networks: a deep reinforcement learning-based approach," IEEE Internet of Things J., vol. 6, no. 6, pp. 9399-9412, Aug. 2019.
[28] R. Mahmud and R. Buyya, "Modeling and Simulation of Fog and Edge Computing Environments Using iFogSim Toolkit," Fog and Edge Computing, pp. 433-465, Jan. 2019.
[29] I. Tellioglu and H. A. Mantar, "A proportional load balancing for wireless sensor networks," in Proc. of the Fifth 3rd Int. Conf. on Sensor Technologies and Applications, pp. 514-519, Athens, Greece, 18-23 Jun. 2009.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 4، زمستان 1401 291
مقاله پژوهشی
توازن بار در گره‌های مه با استفاده از الگوریتم یادگیری تقویتی
نیلوفر طهماسبی‌پویا و مهدی‌آقا صرام
چكیده: محاسبات مه، حوزه تحقیقاتی نوظهوری برای ارائه خدمات محاسبات ابری به لبه‌های شبکه است. گره‌های مه جریان داده و درخواست‌های کاربر را در زمان واقعی پردازش می‌کنند. به منظور بهینه‌سازی بهره‌وری منابع و زمان پاسخ و افزایش سرعت و کارایی، وظایف باید به صورت متوازن بین گره‌های مه توزیع شوند، لذا در این مقاله، روشی جدید جهت بهبود توازن بار در محیط محاسبات مه پیشنهاد شده است. در الگوریتم پیشنهادی، هنگامی که وظیفه‌ای از طریق دستگاه‌های موبایل برای گره مه ارسال می‌شود، گره مه با استفاده از یادگیری تقویتی تصمیم می‌گیرد که آن وظیفه را خودش پردازش کند، یا این که پردازش آن را به یکی از گره‌های مه همسایه یا به ابر واگذار نماید. در بخش ارزیابی نشان داده شده که الگوریتم پیشنهادی با توزیع مناسب وظایف بین گره‌ها، تأخیر کمتری را برای اجرای وظایف نسبت به سایر روش‌های مقایسه‌شده به دست آورده است.
کلیدواژه: تأخیر، توازن بار، گره مه، یادگیری تقویتی، Q-Learning.
1- مقدمه
محاسبات مه2 الگوی محاسباتی توزیع‌شده‌ای است که خدمات ارائه‌شده توسط ابر3 را به لبه4 شبکه گسترش می‌دهد تا مدیریت و برنامه‌ریزی خدمات محاسباتی، شبکه‌ای و ذخیره‌سازی بین مراکز داده و دستگاه‌های نهایی را تسهیل کند. گره‌های مه 5(FN) با قرارگرفتن در لایه بین منابع داده و مرکز داده ابر، جریان داده و درخواست‌های کاربر را در زمان واقعی پردازش می‌کنند و تأخیر و ازدحام شبکه را کاهش می‌دهند [1] و [2]. دستگاه‌های اینترنت اشیا6 معمولاً پردازش وظایف را به نزدیک‌ترین گره مه واگذار می‌کنند. در این صورت ممکن است که بعضی از گره‌های مه وظایف بیشتری را نسبت به سایر گره‌های مه دریافت کنند و به مرور دچار سربار7 شوند. برای جلوگیری از این وضعیت، از روش‌های توازن بار8 برای توزیع یکنواخت وظایف در میان گره‌های مه استفاده می‌شود. گره‌های مه در محیط توزیع‌شده‌ای مستقر شده‌اند. توازن بار در محیط‌های توزیع‌شده به دو دسته توازن بار ایستا و پویا تقسیم می‌شود. در توازن بار ایستا هنگام تصمیم‌گیری برای توازن بار، وضعیت گره مه مقصد در نظر گرفته نمی‌شود. توازن بار ایستا یا به صورت قطعی انجام می‌شود و وظایف به طور دائم به گره مه خاصی تخصیص داده می‌شوند و یا به صورت احتمالی انجام می‌شود که در آن وظایف با احتمال مشخصی به هر گره مه اختصاص داده می‌شوند. اما در توازن بار پویا، وضعیت فعلی گره‌های مه در طول تصمیمات توازن بار در نظر گرفته می‌شود و با توجه به وضعیت آنها، گره مه مقصد انتخاب می‌شود [3]. در این مقاله از روش توازن بار پویا استفاده شده است.
توازن بار بین گره‌های مه نقش مهمی در کاهش تأخیر، زمان پاسخ به کاربر و هزینه دارد و همچنین باعث افزایش بهره‌وری منابع، کارایی، تشخیص رویدادها در زمان واقعی و صرفه‌جویی در مصرف منابع می‌شود. در دهه‌های گذشته، روش‌های مختلفی برای توازن بار ارائه شده که هر یک در وضعیت خاصی از سیستم، نتیجه مناسبی دارند. الگوریتم‌های توازن بار را می‌توان بر اساس نوع الگوریتم مورد استفاده به سه نوع مختلف ابتکاری، فراابتکاری و ترکیبی طبقه‌بندی کرد. انواع الگوریتم‌های ابتکاری به شکل ایستا یا پویا وجود دارند. ابتکاری‌ها شامل محدودیت‌هایی هستند که قصد یافتن بهترین راه حل ممکن برای یک مسأله خاص را دارند. این الگوریتم‌ها به دلیل یافتن راه حل رضایت‌بخش، مفید و در مقایسه با الگوریتم‌های فراابتکاری به آسانی قابل اجرا هستند [4] تا [6]. الگوریتم‌های فراابتکاری ماهیتی پویا دارند و نسبت به الگوریتم‌های ابتکاری، به زمان بیشتری برای اجرا و حل‌کردن راه حل نهایی نیاز دارند، زیرا فضای راه حل آنها می‌تواند بسیار بزرگ باشد و علاوه بر این، فراابتکاری‌ها فرایندهای کاملاً تصادفی هستند. زمان و راه حل آنها تا حد زیادی به ماهیت مسأله، پیکربندی اولیه و روش جستجوی راه حل بستگی دارد [7] تا [9]. الگوریتم‌های ترکیبی، ترکیبی از الگوریتم‌های ابتکاری یا فراابتکاری مختلف هستند که زمان اجرا و نیز هزینه را کاهش می‌دهند و نتیجه مؤثرتری نسبت به الگوریتم‌های دیگر ارائه می‌دهند [10] تا [12].
با این حال، الگوریتم‌های توازن بار رایج به دلیل ماهیت توزیع‌شده و پویایی محاسبات مه، کارایی خود را از دست می‌دهند و به الگوریتمی نیاز است که بتواند در طول زمان با شرایط محیطی تطبیق یابد. به همین منظور در این مقاله، فرایند تصمیم‌گیری مبتنی بر یادگیری تقویتی9 برای یافتن گره مه کم‌بار پیشنهاد شده است. روش پیشنهادی ارائه‌شده به گره مه اجازه می‌دهد تا وظیفه ورودی را با انتخاب یک گره مه همسایه در دسترس، با توجه به ظرفیت منابع، با هدف به حداقل رساندن زمان پردازش و احتمال سربار کلی، واگذار کند. طبق بررسی‌های انجام‌شده در اکثر روش‌های ارائه‌شده برای برقراری توازن بار در محیط مه، برای واگذاری وظایف به گره‌های همسایه، ابتدا باید یک سری محاسبات زمان‌بر برای آگاهی از ظرفیت و موقعیت گره‌های همسایه انجام شود که این امر نیز باعث ایجاد تأخیر در شبکه می‌شود. با این حال در روش پیشنهادی این مقاله، محاسبات اضافی و زمان‌بر حذف می‌شوند و عامل، تنها طبق تجربیاتی که از محیط کسب می‌کند در هر حالت، گره مه مناسب را انتخاب می‌کند و این امر باعث می‌شود که در روش پیشنهادی، تأخیر به شکل قابل توجهی کاهش یابد. در مقایسه با روش‌های سنتی، استفاده از یادگیری تقویتی برای توازن بار، نه تنها بدون در نظر گرفتن هیچ فرضی از مدل شبکه، چارچوب الگوریتم را ساده می‌کند بلکه با پیچیدگی زمانی چندجمله‌ای به سیاست بهینه همگرا می‌شود. نتایج به دست آمده نشان می‌دهند که روش توازن بار پیشنهادی، تأخیر و زمان پاسخ به کاربر را نسبت به روش‌های مقایسه‌شده به شکل قابل توجهی کاهش می‌دهد.
ادامه این مقاله به این صورت سازماندهی شده که در بخش 2 كارهای مرتبط اخیر در زمینه توازن بار در محاسبات مه مورد بررسی قرار می‌گیرد. در بخش 3 مدل سیستم پیشنهادی، الگوریتم یادگیری تقویتی و نحوه محاسبه تأخیر در سیستم پیشنهادی شرح داده می‌شوند. در بخش 4 روش توازن بار پیشنهادی مطرح می‌شود. در بخش 5 به ارزیابی نتایج حاصل از شبیه‌سازی و مقایسه با روش‌های پیشین پرداخته می‌شود. در نهایت در بخش 6 نتیجه‌گیری و پیشنهادهای كارهای آتی ارائه خواهد شد.
2- کارهای پیشین
در محاسبات مه، دستگاه‌های اینترنت اشیا و کاربران موبایل به طور معمول وظایف را به نزدیک‌ترین گره مه واگذار می‌کنند. از آنجایی که این دستگاه‌ها اغلب متحرک هستند، ممکن است گره‌های مه مختلف بسته
به موقعیتی که در شبکه دارند، دارای بارهای متفاوتی باشند. این مسأله موجب عدم توازن در توزیع وظایف بین گره‌های مه می‌شود و ممکن است برخی از گره‌های مه دچار سربار شوند، در حالی که دیگر گره‌های مه بیکار یا کم‌بار هستند. برخی از نویسندگان روش‌هایی را برای رسیدگی به مسأله توازن بار در محیط محاسبات مه ارائه کرده‌اند. این کارها را می‌توان از جنبه‌های مختلفی دسته‌بندی کرد.
2-1 بررسی کارهای پیشین
در اینجا کارهای پیشینی که در آنها برای واگذاری وظایف، گره‌ها نیاز به اطلاع از ظرفیت محاسباتی یکدیگر دارند، بررسی خواهند شد. بیک و همکاران [13]، فرایند تصمیم‌گیری مبتنی بر یادگیری تقویتی را برای یافتن تصمیم بارگذاری بهینه با شرایط مجهول‌بودن مدل پاداش و احتمال گذار پیشنهاد دادند. در فرایند ارائه‌شده، گره‌های مه می‌توانند مقدار بهینه‌ای از وظایف ورودی را به یک گره مه همسایه در دسترس، با توجه به ظرفیت منابع واگذار کنند. هدف از این کار، به حداقل رساندن زمان پردازش و احتمال سربار است. سو و همکاران [14]، روش تخصیص منابع پویا را برای توازن بار در محیط مه پیشنهاد دادند. آنها ابتدا از نظر فنی، چارچوب سیستم محاسبات مه را ارائه دادند و به بررسی عملیات توازن بار روی انواع مختلفی از گره‌های محاسباتی پرداختند. سپس روش تخصیص منابع متناظر را در محیط مه با تخصیص ایستای منابع و انتقال پویای خدمات برای دستیابی به توازن بار در سیستم‌های محاسبات مه طراحی کردند. مانجو و سوماتی [15]، الگوریتم min-min را با در نظر گرفتن منابع شبکه پیشنهاد دادند و آن را در داخل هر خوشه اجرا کردند. هدف از اجرای این الگوریتم، توزیع یکنواخت بار در بین گره‌های مه و کاهش زمان پاسخ است. در صورتی که خوشه دچار سربار شود، عواملی مانند فاصله از خوشه تا گره همسایه، تعداد وظایف منتظر در صف هر خوشه و فاصله از گره خوشه تا نزدیک‌ترین مرکز داده ابر برای ارسال وظیفه در نظر گرفته می‌شود. شرما و سینی [16] برای زمان‌بندی وظایف در گره مه، الگوریتم زمان‌بندی زودترین موعد- اول را پیشنهاد دادند. در این روش، ظرفیت فعلی گره مه با استفاده از شبکه عصبی تخمین زده می‌شود. اگر دستگاه اینترنت اشیا، منبع مورد نیاز را دریافت نکند، وظیفه خود را به ابر ارسال می‌کند. در این مقاله، معماری چهارلایه‌‌ای برای زمان‌بندی وظایف و توازن بار پیشنهاد شده است. لایه اول شامل اینترنت اشیا است که در آن حجم زیادی از داده‌ها هم‌زمان تولید و منتقل می‌شوند. در لایه دوم
با استفاده از