جایگذاری کنترل‌کننده‌ها در شبکه‌های نرم‌افزار محور با استفاده از یک الگوریتم فراابتکاری گسسته بر پایه‌ی ژنتیک

الموضوعات : مجله فناوری اطلاعات در طراحی مهندسی

مهناز خجند ¹ , کامبیز مجیدزاده ² , محمد مصدری ³ , یوسف فرهنگ ⁴

1 - دانشگاه آزاد اسلامی واحد ارومیه
2 - دانشکده فنی مهندسی، دانشگاه آزاد اسلامی واحد ارومیه، ارومیه، ایران
3 - Computer Engineering Department, Islamic Azad University
4 - دانشکده فنی مهندسی، دانشگاه آزاد اسلامی واحد خوی، خوی، ایران

تاريخ الإرسال : 13 الجمعة , محرم, 1446 تاريخ التأكيد : 22 الإثنين , صفر, 1446 تاريخ الإصدار : 10 الأربعاء , صفر, 1446

الکلمات المفتاحية: شبکه های نرم افزار محور, مسئله قرارگیری کنترل‌کننده, الگوریتم های فراابتکاری, الگوریتم بهینه‌سازی مبتنی بر تضاد نخبگان , الگوریتم ژنتیک.,

ملخص المقالة :

شبکه‌های نرم‌افزارمحور (SDN) شامل جداسازی صفحه کنترل از صفحه داده است. در SDN کنترل شبکه توسط موجودیتی به نام کنترل‌‌کننده که در صفحه کنترل قرار دارد تعیین می‌شود. تعیین تعداد و مکان بهینه کنترل‌کننده‌ها در صفحه کنترل به عنوان مسأله‌ی جایگذاری کنترل‌‌کننده‌ها (CPP) شناخته می‌شود. در این مقاله CPP با استفاده از Kmean نظارت نشده (U-kmeans ) و الگوریتم بهینه‌ساز گله اسب (HOA) حل شده است. الگوریتم U-kmeans سوییچ‌ها را خوشه‌بندی می‌کند و تعداد کنترل‌گرها را تعیین می‌کند. از آنجا که مسأله CPP گسسته است، الگوریتم HOA از اپراتورهای ژنتیکی استفاده می‌کند که HOA بهبود یافته (MHOA) نام دارد. مرحله‌‌ی بعدی این مقاله، شامل یافتن مکان بهینه‌ی هر کنترل‌کننده در داخل خوشه خود با استفاده از MHOA است. برای بهبود نرخ همگرایی، MHOA از استراتژی یادگیری مبتنی بر مخالفت نخبگان (EOBL) استفاده می‌کند. نتایج نشان می‌دهد که روش پیشنهادی در مقایسه با سایر الگوریتم‌های مطرح شده از نظر تأخیر انتها به انتها، عدم توازن بار و مصرف انرژی عملکرد بهتری دارد. روش پیشنهادی با کاهش عدم توازن بار 9.66٪، تأخیر انتها به انتها 19.65٪ و میانگین مصرف انرژی 8.43٪ بهبود یافته است.

المصادر:

[1] G. Ramya and R. Manoharan, "Enhanced optimal placements of multi-controllers in SDN," Journal of Ambient Intelligence and Humanized Computing, vol. 12, pp. 8187-8204, 2021.#
[2] A. Shirmarz and A. Ghaffari, "Performance issues and solutions in SDN-based data center: a survey," The Journal of Supercomputing, vol. 76, no. 10, pp. 7545-7593, 2020. #
[3] W. Xia, Y. Wen, C. H. Foh, D. Niyato, and H. Xie, "A survey on software-defined networking," IEEE Communications Surveys & Tutorials, vol. 17, no. 1, pp. 27-51, 2014. #
[4] D. Kreutz, F. M. Ramos, P. E. Verissimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, "Software-defined networking: A comprehensive survey," Proceedings of the IEEE, vol. 103, no. 1, pp. 14-76, 2014. #
[5] T. Jafarian, M. Masdari, A. Ghaffari, and K. Majidzadeh, "SADM-SDNC: security anomaly detection and mitigation in software-defined networking using C-support vector classification," Computing, vol. 103, pp. 641-673, 2021. #
[6] T. Jafarian, M. Masdari, A. Ghaffari, and K. Majidzadeh, "A survey and classification of the security anomaly detection mechanisms in software defined networks," Cluster Computing, vol. 24, pp. 1235-1253, 2021. #
[7] G. D’Angelo and F. Palmieri, "A co-evolutionary genetic algorithm for robust and balanced controller placement in software-defined networks," Journal of Network and Computer Applications, vol. 212, p. 103583, 2023. #
[8] A. Shirmarz and A. Ghaffari, "An adaptive greedy flow routing algorithm for performance improvement in software‐defined network," International Journal of Numerical Modelling: Electronic Networks, Devices and Fields, vol. 33, no. 1, p. e2676, 2020. #
[9] K. Benzekki, A. El Fergougui, and A. Elbelrhiti Elalaoui, "Software‐defined networking (SDN): a survey," Security and communication networks, vol. 9, no. 18, pp. 5803-5833, 2016. #
[10] A. A. Ateya et al., "Chaotic salp swarm algorithm for SDN multi-controller networks," Engineering Science and Technology, an International Journal, vol. 22, no. 4, pp. 1001-1012, 2019. #
[11] A. Shirmarz and A. Ghaffari, "Automatic software defined network (SDN) performance management using TOPSIS decision-making algorithm," Journal of Grid Computing, vol. 19, pp. 1-21, 2021. #
[12] A. Shirmarz and A. Ghaffari, "An autonomic software defined network (SDN) architecture with performance improvement considering," Journal of Information Systems and Telecommunication (JIST), vol. 8, no. 30, pp. 121-129, 2020. #
[13] K. P. Sinaga and M.-S. Yang, "Unsupervised K-means clustering algorithm," IEEE access, vol. 8, pp. 80716-80727, 2020. #
[14] N. Firouz, M. Masdari, A. B. Sangar, and K. Majidzadeh, "A hybrid multi-objective algorithm for imbalanced controller placement in software-defined networks," Journal of Network and Systems Management, vol. 30, no. 3, p. 51, 2022. #
[15] A. Mohammadi-Balani, M. D. Nayeri, A. Azar, and M. Taghizadeh-Yazdi, "Golden eagle optimizer: A nature-inspired metaheuristic algorithm," Computers & Industrial Engineering, vol. 152, p. 107050, 2021. #
[16] K. S. Sahoo, D. Puthal, M. S. Obaidat, A. Sarkar, S. K. Mishra, and B. Sahoo, "On the placement of controllers in software-defined-WAN using meta-heuristic approach," Journal of Systems and Software, vol. 145, pp. 180-194, 2018. #
[17] A. Ghaffari, "Designing a wireless sensor network for ocean status notification system," Indian Journal of Science and Technology, vol. 7, no. 6, p. 809, 2014. #
[18] N. McKeown et al., "OpenFlow: enabling innovation in campus networks," ACM SIGCOMM computer communication review, vol. 38, no. 2, pp. 69-74, 2008. #
[19] S. Torkamani-Azar and M. Jahanshahi, "A new GSO based method for SDN controller placement," Computer Communications, vol. 163, pp. 91-108, 2020. #
[20] B. R. Killi and S. V. Rao, "Poly-stable matching based scalable controller placement with balancing constraints in SDN," Computer Communications, vol. 154, pp. 82-91, 2020. #
[21] A. Jalili, M. Keshtgari, and R. Akbari, "Optimal controller placement in large scale software defined networks based on modified NSGA-II," Applied Intelligence, vol. 48, pp. 2809-2823, 2018. #
[22] C. Gao, H. Wang, F. Zhu, L. Zhai, and S. Yi, "A particle swarm optimization algorithm for controller placement problem in software defined network," in Algorithms and Architectures for Parallel Processing: 15th International Conference, ICA3PP 2015, Zhangjiajie, China, November 18-20, 2015, Proceedings, Part III 15, 2015: Springer, pp. 44-54. #
[23] K. Kanodia, S. Mohanty, K. Kurroliya, and B. Sahoo, "CCPGWO: A meta-heuristic strategy for link failure aware placement of controller in SDN," in 2020 International Conference on Inventive Computation Technologies (ICICT), 2020: IEEE, pp. 859-863. #
[24] S. Rahman et al., "Virtualized controller placement for multi-domain optical transport networks using machine learning," Photonic Network Communications, vol. 40, pp. 126-136, 2020. #
[25] A. Ksentini, M. Bagaa, T. Taleb, and I. Balasingham, "On using bargaining game for optimal placement of SDN controllers," in 2016 IEEE International Conference on Communications (ICC), 2016: IEEE, pp. 1-6. #
[26] P. Yi, T. Hu, Y. Hu, J. Lan, Z. Zhang, and Z. Li, "SQHCP: secure-aware and QoS-guaranteed heterogeneous controller placement for software-defined networking," Computer Networks, vol. 185, p. 107740, 2021. #
[27] N. Firouz, M. Masdari, A. B. Sangar, and K. Majidzadeh, "A novel controller placement algorithm based on network portioning concept and a hybrid discrete optimization algorithm for multi-controller software-defined networks," Cluster Computing, vol. 24, pp. 2511-2544, 2021. #
[28] Y. Hu, T. Luo, N. C. Beaulieu, and C. Deng, "The energy-aware controller placement problem in software defined networks," IEEE Communications Letters, vol. 21, no. 4, pp. 741-744, 2016. #
[29] L. Wei, C. Chang, Y. Liu, and Y. Wang, "Energy-Efficient Controller Placement in Software-Defined Satellite-Terrestrial Integrated Network," Remote Sensing, vol. 14, no. 21, p. 5561, 2022. #
[30] C. Li, K. Jiang, and Y. Luo, "Dynamic placement of multiple controllers based on SDN and allocation of computational resources based on heuristic ant colony algorithm," Knowledge-Based Systems, vol. 241, p. 108330, 2022. #
[31] R. R. Mostafa, M. A. Gaheen, M. Abd ElAziz, M. A. Al-Betar, and A. A. Ewees, "An improved gorilla troops optimizer for global optimization problems and feature selection," Knowledge-Based Systems, vol. 269, p. 110462, 2023. #
[32] F. MiarNaeimi, G. Azizyan, and M. Rashki, "Horse herd optimization algorithm: A nature-inspired algorithm for high-dimensional optimization problems," Knowledge-Based Systems, vol. 213, p. 106711, 2021. #
[33] B. Heller, R. Sherwood, and N. McKeown, "The controller placement problem," ACM SIGCOMM Computer Communication Review, vol. 42, no. 4, pp. 473-478, 2012. #
[34] D. Hock, M. Hartmann, S. Gebert, M. Jarschel, T. Zinner, and P. Tran-Gia, "Pareto-optimal resilient controller placement in SDN-based core networks," in Proceedings of the 2013 25th international teletraffic congress (ITC), 2013: IEEE, pp. 1-9. #
[35] M. Khojand, K. Majidzadeh, M. Masdari, and Y. Farhang, "Controller placement in SDN using game theory and a discrete hybrid metaheuristic algorithm," The Journal of Supercomputing, pp. 1-49, 2023. #
[36] Z. C. Dagdia and M. Mirchev, "When Evolutionary Computing Meets Astro-and Geoinformatics," in Knowledge Discovery in Big Data from Astronomy and Earth Observation: Elsevier, 2020, pp. 283-306. #
[37] S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, "The internet topology zoo," IEEE Journal on Selected Areas in Communications, vol. 29, no. 9, pp. 1765-1775, 2011. #
[38] M. A. Bagha, K. Majidzadeh, M. Masdari, and Y. Farhang, "Improving delay in SDNs by metaheuristic controller placement," International Journal of Industrial Electronics Control & Optimization, vol. 5, no. 3, 2022. #

نص كامل:



	دوره هفدهم، شماره بهار و تابستان 1403   مجله فناوری اطلاعات در طراحی مهندسی Information Technology in Engineering Design http://sanad.iau.ir/journal/ited
جای‌گذاری کنترل‌کننده‌ها در شبکه‌های تعریف شده‌ی نرم‌افزار با استفاده از یک الگوریتم فراابتکاری بر پایه‌ی ژنتیک مهناز خجند(1)     کامبیز مجیدزاده*(2)    محمد مصدری(3)      یوسف فرهنگ(4)   (1)       دانشکده فنی مهندسی، دانشگاه آزاد اسلامی، واحد ارومیه، ارومیه، ایران  (2)       دانشکده فنی مهندسی، دانشگاه آزاد اسلامی، واحد ارومیه، ارومیه، ایران* (3)       دانشکده فنی مهندسی، دانشگاه آزاد اسلامی، واحد ارومیه، ارومیه، ایران (4)       دانشکده فنی مهندسی، دانشگاه آزاد اسلامی، واحد خوی، خوی، ایران  (تاریخ دریافت :29/04/1403     تاریخ پذیرش:05/06/1403)
چکیده شبکه‌های نرم‌افزارمحور شامل جداسازی صفحه کنترل از صفحه داده است. در شبکه‌های نرم‌افزارمحور کنترل شبکه توسط موجودیتی به نام کنترل‌‌کننده که در صفحه کنترل قرار دارد، تعیین می‌شود. تعیین تعداد و مکان بهینه کنترل‌کننده‌ها در صفحه کنترل به عنوان مسئله‌ی جای‌گذاری کنترل‌‌کننده‌ها شناخته می‌شود. در این مقاله در دو فاز مسئله‌ی جای‌گذاری کنترل‌کننده‌ها با استفاده از خوشه‌بندی و الگوریتم بهینه‌ساز گله اسب (HOA) حل شده است. در فاز اول تعداد کنترل‌کننده‌ها با استفاده از خوشه‌بندی تعیین ‌می‌شود. الگوریتم استفاده‌شده برای خوشه‌بندی ورژنی از K-means می‌باشد که علاوه بر خوشه‌بندی سوئیچ‌ها، تعداد کنترل‌کننده‌ها را نیز تعیین می‌کند. در فاز دوم برای تعیین مکان بهینه کنترل‌کننده در داخل هر خوشه از الگوریتم فراابتکاری گله اسب استفاده می‌شود. در اینجا برای بالا بردن قدرت اکتشاف و بهره‌برداری الگوریتم گله اسب و همین‌طور بهبود همگرایی و سرعت آن از عملگرهای ژنتیک و استراتژی تضاد نخبگان استفاده شده است که الگوریتم گله اسب بهبود یافته (MHOA) نام‌گذاری می‌شود. نتایج نشان می‌دهد که روش پیشنهادی در مقایسه با سایر الگوریتم‌های مطرح شده از نظر تأخیر انتها به انتها، عدم توازن بار و مصرف انرژی عملکرد بهتری دارد. روش پیشنهادی با کاهش 9.66٪ عدم توازن بار، 19.65٪ تأخیر انتها به انتها و 8.43٪  میانگین مصرف انرژی به نتایج بهتری نسبت به الگوریتم‌های دیگر دست یافته است.   کلمات کلیدی: شبکه تعریف‌شده توسط نرم‌افزار، مسئله قرارگیری کنترل‌کننده، الگوریتم های فراابتکاری، الگوریتم بهینه‌سازی مبتنی بر تضاد نخبگان، الگوریتم ژنتیک *عهده‌دار مکاتبات:                  کامبیز مجیدزاده         نشانی: دانشکده فنی مهندسی، دانشگاه آزاد اسلامی، واحد ارومیه ارومیه، ایران  پست الکترونیکی: [e-mail]

 

1-       مقدمه

در حال حاضر، با توجه به افزایش تعداد کاربران، حجم بالای داده‌ها، پیچیدگی و ترافیک داده‌ها، شبکه‌های سنتی قادر به پاسخگویی نبوده و با چالش‌های بسیاری از لحاظ مدیریت و پاسخ‌دهی روبه‌رو هستند[1-4] . در راستای پاسخ به چالش‌های مطرح‌شده، معماری شبکه‌های نرم‌افزارمحور¹ به عنوان یک راه‌حل پیشنهاد شده است. شبکه‌های نرم‌افزارمحور یک معماری شبکه است که مدیریت (صفحه کنترل) را از پردازش داده (صفحه داده) جدا می‌کند و در نتیجه بهبود مدیریت شبکه‌های گسترده را فراهم می‌سازد. شکل ۱ نشان‌دهنده معماری شبکه‌های نرم‌افزارمحور است که شامل سه لایه‌ی داده، کنترل و برنامه می‌باشد. ارتباط بین این لایه‌ها از طریق رابط‌های جنوبی و شمالی صورت می‌گیرد. همچنین، رابط‌های شرقی و غربی نیز پروتکل ارتباطی بین کنترل‌کننده‌های مختلف در شبکه را تعریف می‌کنند[5,6] . صفحه داده می‌تواند با اختصاص وظایف مسیریابی و سیگنال‌دهی به یک موجودیت جداگانه به نام کنترل‌کننده که در صفحه کنترل قرار دارد، امکان ارسال سریع داده‌ها را داشته باشد. استفاده از فقط یک کنترل‌کننده ممکن است منجر به ایجاد محدودیت‌هایی در شبکه شود، زیرا آن کنترل‌کننده به عنوان یک گلوگاه عمل کرده و بار کاری کل شبکه بر روی آن تمرکز می‌یابد؛ بنابراین، اگر کنترل‌کننده از کار افتد، کل شبکه با شکست مواجه خواهد شد. از این‌رو، داشتن چندین کنترل‌کننده در صفحه‌ی کنترل بسیار حیاتی است. این کنترل‌کننده‌ها در سراسر شبکه توزیع می‌شوند و باعث کاهش تاخیر در شبکه، افزایش قابلیت اطمینان، بهبود زمان پاسخ و تعادل بار می‌شوند. هر سوئیچ به حداقل یک کنترل‌کننده اختصاص می‌یابد و هر کنترل‌کننده مسئول مدیریت یک مجموعه از سوئیچ‌ها[7,8]  است.

 تعیین تعداد و موقعیت بهینه کنترل‌کننده‌ها و اختصاص سوئیچ‌ها به آن‌ها مسئله‌ی جای‌گذاری کنترل‌کننده‌ها² نامیده می‌شود. حل بهینه‌ی مسئله‌ی جای‌گذاری کنترل‌کننده‌ها برای عملکرد شبکه بسیار حیاتی است زیرا تعداد و موقعیت کنترل‌کننده‌ها باید قابل تطبیق با تغییرات اندازه و بار شبکه باشد، به‌طوری‌که بتواند باعث بهبود کارآیی شبکه از لحاظ تاخیر، مصرف انرژی، توزیع یکنواخت ترافیک شبکه و قابلیت اعتماد شود. با این حال، مسئله‌ی جای‌گذاری کنترل‌کننده‌ها مسئله‌ای پیچیده است و حل آن آسان نمی‌باشد و به عنوان یک مسئله‌ی ان-پی سخت³ شناخته می‌شود [9,10].

 

 

شکل 1: معماری پیشنهاد شده برای SDN

 

در فاز اولیه‌ی این مقاله، ورژنی از  K-means برای حل مسئله‌ی جای‌گذاری کنترل‌کننده‌ها استفاده شده است. K-means به دلیل سرعت، پیچیدگی کم و کارایی آن‌ها یکی از روش‌های پرطرفدار در خوشه‌بندی است. یکی از محدودیت‌های اساسی K-means نیاز به مشخص کردن تعداد خوشه‌ها به عنوان ورودی الگوریتم است. روش استفاده شده در این مقاله ورژنی از K-means است که نیاز به تعیین تعداد خوشه‌ها از قبل ندارد و با تعیین خودکار تعداد بهینه‌ی خوشه‌ها، K-means را گسترش می‌دهد [11,12]. این الگوریتم می‌تواند به عنوان یک گزینه ایده‌آل برای خوشه‌بندی و یافتن تعداد کنترل‌کننده‌ها در مسئله جای‌گذاری کنترل‌کننده‌ها استفاده شود. در این مرحله، گره‌ها با در نظر گرفتن مکان گره‌ها و ترافیک شبکه خوشه‌بندی می‌شوند. تعداد کنترل‌کننده‌ها برابر با تعداد خوشه‌های تعیین‌شده می‌باشد و به عنوان ورودی فاز بعدی مقاله است. در فاز دوم، یک الگوریتم فراابتکاری به نام الگوریتم بهینه‌سازی اسب بهبودیافته (MHOA) برای یافتن مکان کنترل‌کننده در داخل هر خوشه معرفی می‌شود. تکنیک‌های فراابتکاری روش‌هایی هستند که برای جست‌وجو، از یک زیرمجموعه‌ی خاص از فضای جست‌وجو به صورت کارآمد استفاده می‌کنند تا به راه‌حل‌های نزدیک به بهینه برسند. این روش‌ها در حل مسائل پیچیده و ان-پی سخت مانند مسئله جای‌گذاری کنترل‌کننده‌ها بسیار کارآمد هستند [13,14]. الگوریتم MHOA ورژن بهبود یافته‌ی الگوریتم بهینه‌ساز گله اسب⁴ است [15]. الگوریتم گله اسب در حل بسیاری از مسائل دنیای واقعی به خوبی عمل می‌کند. با این حال، در برخی مسائل پیچیده ممکن است که در بهینه‌ی محلی گیر کند و دچار پایان زودهنگام شود. MHOA برای افزایش قدرت اکتشاف⁵ و بهره‌وری⁶ و بهبود همگرایی، از استراتژی تضاد نخبگان⁷ و عملگرهای ‌ژنتیک استفاده می‌کند. در ادامه از MHOA برای حل مسئله جای‌گذاری کنترل‌کننده‌ها استفاده می‌شود. برای ارزیابی الگوریتم پیشنهادی، از مجموعه داده‌ی اینترنتی توپولوژی زو⁸ استفاده شده است. این مطالعه نشان می‌دهد که الگوریتم MHOA در مقایسه با دیگر روش‌های فراابتکاری به‌طور موثری باعث بهبود تأخیر انتها به انتها، مصرف انرژی و تعادل بار می‌گردد.

خلاصه‌ی کارهای انجام شده در این مقاله به شرح زیر است:

·       پیدا کردن تعداد کنترل‌کننده‌ها.

·       بهبود الگوریتم گله اسب با استفاده از استراتژی تضاد نخبگان و استفاده از عملگرهای ژنتیک(MHOA).

·        استفاده از MHOA برای حل مسئله‌ی جای‌گذاری کنترل‌کننده‌ها.

·        ارزیابی قابلیت مقیاس‌پذیری MHOA برای قرار دادن کنترل‌کننده‌ها در دو شبکه‌ با اندازه‌ی متفاوت از مجموعه داده‌ی توپولوژی زو.

·       مقایسه‌ی نتایج الگوریتم پیشنهادی با نتایج الگوریتم‌های فراابتکاری دیگر از لحاظ تاخیر انتها به انتها، مصرف انرژی و تعادل بار.

بخش 2 این مقاله، خلاصه‌ای از مطالعات قبلی انجام‌شده در این حوزه را ارائه داده و فصل 3 الگوریتم‌های استفاده‌شده در این مقاله، به‌عنوان مثال  HOAو K-means  بهبودیافته توضیح داده شده و با معرفی MHOA به چگونگی حل CPP می‌پردازد. بخش 4 نحوه‌ی ارزیابی کار را نشان می‌دهد و درنهایت، در بخش 6 خلاصه‌ای از نتایج به‌دست آمده از مقاله ارائه می‌شود.

 

2-       کارهای گذشته

در این بخش، ما برخی از کارهای انجام شده در حوزه CPP با استفاده از روش‌های فراابتکاری را معرفی می‌کنیم. مسئله‌ی جای‌گذاری کنترل‌کننده به‌صورت پویا برای نخستین بار توسط [16] مورد مطالعه قرار گرفت. نویسندگان مسئله‌ی "جای‌گذاری کنترل‌کننده به‌صورت پویا" را به عنوان یک برنامه‌ی خطی عدد صحیح تعریف کردند و دو الگوریتم ترکیبی برای حل آن در موارد بزرگ‌تر پیشنهاد دادند. با این حال، آن‌ها اعتبارپذیری را در نظر نگرفتند و تنها بر کاهش زمان راه‌اندازی جریان و هزینه ارتباطات تمرکز کردند. نویسندگان در [17] یک استراتژی جدید برای قرار دادن کنترل‌کننده‌های SDN در شبکه با استفاده از مسئله‌ی کوله‌پشتی 0-1 و الگوریتم بهینه‌سازی مار گارتنر معرفی کردند. آزمایشات آن‌ها نشان داد که این روش به‌طور مؤثری تأخیرها را هم در WAN و هم در SDN کاهش می‌دهد. این رویکرد گرچه توانست استفاده از منابع شبکه و خدمات‌رسانی به مشتریان را بهبود بخشد، ولی باید توجه کرد که اجرای آن ممکن است نیازمند منابع محاسباتی قابل توجهی باشد که ممکن است محدودیت‌هایی در محیط‌های شبکه داشته باشد. علاوه‌ بر این، در این مقاله به مسئله مقیاس‌پذیری پرداخته نشده است.

کیلی و همکاران در [18]، یک الگوریتم قرارگیری کنترل‌کننده ارائه کردند که با استفاده از تطبیق پلی-پایدار، توانایی مدیریت شبکه‌های بزرگ را داشت و سوئیچ‌ها را بین کنترل‌کننده‌ها توزیع می‌کرد. این الگوریتم عواملی مانند تاخیر و بار را در نظر گرفته بود تا سوئیچ‌های باقی‌مانده را تخصیص دهد. این الگوریتم در مقایسه با الگوریتم‌های موجود، از نظر توازن بار و کاهش تاخیر، عملکرد بهتری داشت. قابلیت مقیاس‌پذیری و کارآمدی این الگوریتم در شبکه‌های    WAN  بر روی سه شبکه ISP واقعی با مقیاس متوسط و بزرگ آزمایش شد. در این مقاله، تأثیر قرارگیری کنترل‌کننده بر محدودیت‌های در دسترسی و زمان همگرایی شبکه‌های SD-WAN مشخص نشده است.

نویسندگان در [19]، یک تکنیک به نام MHNSGA-II پیشنهاد دادند که عوامل مختلفی مانند تاخیر، قابلیت اطمینان و زمان محاسبه را در نظر می‌گرفت. آن‌ها روشی جدید برای ایجاد راه‌حل‌های اولیه پیشنهاد دادند که امکان بررسی مناطق مختلف در فضای راه‌حل را فراهم کرده و کیفیت راه‌حل را افزایش می‌دهد. با این حال، در این کار فرض شد که توپولوژی شبکه و ترافیک ثابت و شناخته شده است، که ممکن است در شرایط واقعی صحت نداشته باشد. در [20]، یک الگوریتم جدید برای حل مسئله‌ی CPP معرفی شده است. آن‌ها از رویکرد فراابتکاری بهینه‌سازی گروه ذرات (PSO) استفاده کردند و تاخیر سرتاسری را به عنوان یک معیار برای حل مسئله مورد بررسی قرار دادند. این الگوریتم با وجود اینکه به‌طور موثری تاخیر انتشار را کاهش داد، اثر بار ترافیک پایدار بر روی کنترل‌کننده‌ها را نادیده گرفت.

در مقاله [21]، نویسندگان از الگوریتم بهینه‌سازی گرگ خاکستری (GWO) برای حل CPP استفاده کردند (CCPGWO). در این کار ظرفیت کنترل‌کننده‌ها نیز در نظرگرفته شد. هدف این پژوهش یافتن بهترین مکان و عملکرد برای کنترل‌کننده‌ها در یک شبکه بود. نتایج نشان دادند که CCPGWO  در کمینه کردن تاخیر بدترین حالت، اجتناب از نقاط بهینه محلی و دستیابی به نتایجی که نزدیک به بهینه جهانی هستند، موفق بوده است. در این مقاله فرض شده است که هر گره در شبکه قابلیت OpenFlow را دارد، ولی این شرایط همیشه در واقعیت صدق نمی‌کند. در مقاله‌ی [22]، نویسندگان با در نظر گرفتن عواملی مانند انواع مختلف کنترل‌کننده، منابع محدود در موقعیت‌های لبه و ضرورت کاهش تاخیر، یک روش جدید برای قرارگیری کنترل‌کننده‌ها در شبکه‌های انتقال نوری ارائه کردند. آن‌ها همچنین یک روش بر پایه‌ی روش‌های یادگیری ماشین، برای کمک به پیش‌بینی مکان‌های بهینه معرفی کردند. این رویکرد دارای چندین مزیت مانند کاهش تاخیر، بهبود عملکرد و صرفه‌جویی در هزینه بود. با این حال، قابلیت اعمال این مطالعه محدود به شبکه‌های انتقال چند دامنه است، که باعث کاهش قابلیت استفاده گسترده‌ی آن می‌شود. علاوه بر این، پیاده‌سازی و مدیریت این چارچوب ممکن است نیاز به منابع قابل توجه و دانش تخصصی داشته باشد. در مقاله[23] ، کاسنتین و همکاران با استفاده از تئوری بازی توانستند بین تعادل بار در شبکه و تاخیر توازن برقرار کنند. آن‌ها فرض کردند که توپولوژی شبکه پیش‌تعیین شده است، که این ممکن است همیشه در سناریوهای واقعی صحیح نباشد.

نویسندگان در [24]، پروژه SQHCP را برای حل مسئله‌ی CPP ارائه دادند، که هدف قرار دادن کنترلرهای نامتجانس به صورت امن و با اطمینان از کیفیت بود. آن‌ها نیازهای امنیت و کیفیت سرویس و در عین حال خطاهای لایه کنترل و تضمین استفاده متعادل از کنترلرها را در نظر گرفتند. با این حال ، پیاده‌سازی این رویکرد ممکن است نسبت به روش‌های موجود منابع و پیچیدگی بیشتری را مورد نیاز داشته باشد. در [1]، رامایا و همکاران یک تکنیک نوآورانه بر اساس نظریه گراف ارائه دادند تا تعداد لازم کنترلرها را تعیین کنند. آن‌ها از الگوریتم جست‌وجوی تابو یکپارچه پارتو برای شناسایی بهترین مکان برای این کنترلرها استفاده کردند. آن‌ها همچنین یک روش فراابتکاری برای مدیریت سناریوهای پویا مانند خرابی‌های پیوند و عدم تعادل بار بر روی کنترل‌کننده‌ها ارائه دادند. در [25]، نویسندگان الگوریتم بهینه‌سازی نوآورانه‌ای به نام PHCPA معرفی کردند که از الگوریتم‌های بهینه‌سازی الهام‌گرفته از طبیعت و تقسیم‌بندی شبکه برای بهبود عملکرد شبکه استفاده می‌کرد. هدف آن‌ها بهینه‌سازی موقعیت چندین کنترلر در SDN بود؛ به‌طوری که، حداقل تاخیر بین سوئیچ‌ها و کنترلرها را کاهش دهد. با این حال، این الگوریتم نیاز به زمان CPU و فضای ذخیره‌سازی بیشتری نسبت به الگوریتم‌های جایگزین داشت. در [8]، پژوهشگران یک الگوریتم ژنتیک تکاملی را برای حل مسئله‌ی CPP معرفی کردند. آن‌ها در این تحقیق، تخصیص بهینه سوئیچ‌ها ، توازن بار و جلوگیری از خرابی‌ها را در نظر گرفته و در عین حال از اعمال تغییرات در نصب کنترل‌کننده‌ها و جریان ترافیک خودداری کردند. با این حال، پیاده‌سازی این راه‌حل ممکن است برای شبکه‌هایی با مقیاس بزرگ، منابع محاسباتی قابل توجهی را مطالبه کند.

در [26]، نویسندگان برای بهبود عملکرد و کارآیی انرژی در شبکه‌های ماهواره‌ای (STIN)، قرار دادن استراتژیک کنترل‌کننده‌های  SDN را ارائه دادند و مزایای استفاده از SDN  در STIN را مانند پوشش جهانی و اتصال پایدار برجسته ساختند. آن‌ها الگوریتم MSAP  را معرفی کردند که در مقایسه با الگوریتم‌های دیگر در مورد تأخیر متوسط ​​هنگام استقرار چندین کنترل‌کننده در STIN عملکرد بهتری داشت. در [27]، نویسندگان الگوریتم ژنتیک جدیدی به نام IGCPA را برای حل مسئله‌ی CPP معرفی کردند. آن‌ها بر اهمیت در نظر گرفتن مصرف انرژی در هنگام انتخاب مکان کنترل‌کننده تأکید کردند و مزایای این کار را توضیح دادند. با این حال، پیچیدگی محاسباتی مدل BIP ممکن است آن را برای شبکه‌های بسیار بزرگ مناسب نکند. در [28]، نویسندگان بررسی‌هایی در مورد قرار دادن پویای چندین کنترل‌کننده و توزیع منابع محاسباتی از طریق الگوریتم‌های فرابتکاری مورچه انجام دادند. این رویکرد به سیستم امکان تطبیق با شرایط متغیر را می‌دهد و عملکرد شبکه را با تسهیل انتقال داده سریع‌تر کرده و موجب کاهش تأخیر و بهبود کارایی کلی شبکه می‌شود. با این حال، پیاده سازی این سیستم ممکن است نیاز به منابع محاسباتی قابل توجه، افزایش هزینه و پیچیدگی داشته باشد و خطر شکست در کنترل‌کننده‌های متمرکز را به همراه داشته باشد.

 

منافع	کمبودها	الگوریتم	مراجع
مدیریت شرایط پویای شبکه، کاهش تاخیر	نادیده گرفتن تعادل بار، نادیده گرفتن هزینه	جست‌وجوی ممنوعه پترو(PITS)	[1]
نگاشت سوئیچ به کنترل کننده ها، افزایش تغادل بار، کاهش تاخیر	نیاز به منابع محاسباتی بیشتر	جست‌وجوی تکاملی، الگوریتم ژنتیک	[8]
کاهش پیچیدگی زمانی، کاهش تاخیر	نادیده گرفتن مقیاس پذیری، نیاز به منابع محاسباتی بیشتر	کوله پشتی 0-1، مار گارتنر	[17]
بهبود تعادل بار، کاهش تاخیر	نادیده گرفتن دسترس پذیری	الگوریتم شبیه‌ساز حرارت	[18]
بهبود قابلیت اطمینان و تاخیر در شبکه	در نظر گرفتن شبکه به صورت استاتیک	الگوریتم ژنتیک رتبه بندی نامغلوب	[19]
افزایش تعادل بار و کاهش تاخیر در شبکه	عدم مطرح نحوه گسسته سازی الگوریتم	ازدحام ذرات	[20]
افزایش قابلیت اطمینان	عدم در نظر گرفتن تعادل بار و هزینه	گرگ خاکستری	[21]
افزایش تعادل بار و کاهش تاخیر	در نظر گرفتن شبکه به صورت استاتیک	تئوری بازی	[23]
افزایش تعادل بار و کاهش تاخیر	پیچیدگی بالا	الگوریتم ژنتیک	[24]
کاهش تاخیر	نیاز به زمان محاسباتی بالا	الگوریتم سفره ماهی، بهینه ساز عنکبوت	[25]
کاهش مصرف انرژی	مناسب نبودن برای شبکه‌های بسیار بزرگ.	الگوریتم ژنتیک	[27]
کاهش مصرف انرژی	عدم در نظر گرفتن تعادل بار و هزینه	شبیه ساز حرارت بهبود یافته	[26]
افزایش کارایی شبکه و افزایش تعادل بار	نیاز به زمان محاسباتی بالا	شبیه ساز حرارت	[28]

 

جدول1: مروری بر کارهای انجام شده در حوزه‌ SDN

 

3-       شرح مسئله

در این قسمت توضیح مختصری از روش‌های استفاده شده در این مقاله آورده شده است.

3-1- روش K-means بهبودیافته

الگوریتم K-means یک روش خوشه‌بندی محبوب است که هدف آن بیشینه‌سازی شباهت درون خوشه‌ها و افزایش اختلاف میان آن‌ها می‌باشد. این روش‌ با اینکه در زیرمجموعه‌ی روش‌های یادگیری بدون نظارت قرار دارد، اما لازم است که تعداد خوشه‌ها از قبل مشخص شوند. الگوریتم K-means بهبودیافته، نسخه‌ای اصلاح‌شده از الگوریتم K-means، است که نیاز به پیش‌فرض‌ها و انتخاب پارامتر ندارد و می‌تواند به طور خودکار تعداد بهینه‌ی خوشه‌ها را نیز تعیین کند [11]. این الگوریتم از مفهوم آنتروپی استفاده می‌کند. در این هنگام   مجموعه داده‌هایی است که باید خوشه‌بندی شوند و  مراکز خوشه می‌باشند. فرض کنید  که در آن   یک متغیر دودویی،  ، است. همان‌طور که در رابطه (1) نشان داده شده است اگر  باشد،   تعیین می‌کند که آیا داده‌ی  به خوشه k ام تعلق دارد یا نه.

 

الگوریتم K-means بهبود یافته از مفهوم آنتروپی استفاده می کند تا الگوریتم خوشه بندی K-means را بدون نیاز به مقداردهی اولیه استفاده کرده و به‌طور خودکار تعداد خوشه ها را تعیین کند. همانطور که در رابطه (2) نشان داده شده است،  تابع هدف را تعیین می‌کند.

(1)

 

در اینجا  فاصله اقلیدسی بین نقطه داده  و مرکز خوشه  است. مقدار  احتمال تعلق یک نقطه داده به خوشه k ام است. این احتمال بر اساس رابطه (3) به‌روزرسانی می‌شود.

(2)

 

مقدار  به عنوان  تعریف شده است، و  بر اساس رابطه (4) به‌دست می‌آید.

(3)

 

تا زمانی‌که مقدار c به یک مقدار پایدار برسد، مقادیر α،  β و γ در هر تکرار به‌طور پیوسته به‌روز می‌شوند.

 

3-2- الگوریتم بهینه‌سازی گله اسب

الگوریتم بهینه‌سازی گله اسب(HOA)  یک الگوریتم فراابتکاری‌ است که برای حل مسائل بهینه‌سازی با تعداد زیادی متغیر طراحی شده است. این الگوریتم الهام خود را از رفتار گله‌های اسب گرفته و رفتارهای اجتماعی آن‌ها در مراحل مختلف زندگی را تقلید می‌کند. این رفتار شامل چرا، سلسله مراتب، اجتماعیت، تقلید، مکانیزم دفاع و گردشگری است [15]. رویکرد الگوریتم شامل حرکت اسب‌ها در هر تکرار است که توسط رابطه‌ی (5) تعیین می‌شود.

(4)

 

در HOA، موقعیت هر اسب به عنوان  نمایش داده می‌شود که  مربوط به بازه‌ی سنی اسب است و  نشان‌دهنده‌ی تکرار کنونی است. بردار سرعت یک اسب به عنوان   نشان داده می‌شود. طول عمر اسب‌ها در حدود 30-25 است و گروه‌های سنی مختلف، رفتارهای متمایزی را نشان می‌دهند. اسب‌ها در بازه‌ی سنی 0 تا 5 سال به عنوان ، در بازه‌ی سنی 5 تا 10 سال به عنوان ، 10 تا 15 سال به عنوان  و بیش از 15 سال با عنوان   دسته‌بندی می‌شوند. برای تعیین سن اسب‌ها، یک ماتریس جمعیت موجود تولید و مرتب می‌شود. 10% برتر به عنوان اسب‌های ، %20 بعدی به عنوان اسب‌های ، %30 به عنوان اسب‌های  و بقیه‌ 40% به عنوان اسب‌های  مشخص می‌شوند. از روش‌های ریاضی برای شبیه‌سازی رفتار اسب‌ها و محاسبه بردارهای سرعت آن‌ها استفاده می‌شود. حرکت اسب‌ها در هر چرخه الگوریتم با استفاده از رابطه (6) که الگوهای رفتار مذکور را در نظر می‌گیرد، توصیف می‌شود.

(5)

(6)

3-3- استراتژی تضاد نخبگان استراتژی تضاد نخبگان9، یک رویکرد نوآورانه در یادگیری ماشین است که الهام خود را از استراتژی مبتنی بر مخالف10 می‌گیرد [29]. این مفهوم روشی مبتنی بر نخبه‌گرایی و جهت مخالف آن در همان زمان است. در این روش به منظور افزایش احتمال کشف مناطقی که پتانسیل بیش‌تری برای بهینه بودن دارند، ابتدا مناطق و حدس‌های بهینه از بین جمعیت اولیه شناخته‌شده و سپس برای اکتشاف بیش‌تر و عبور از بهینه‌های محلی نقاط کاملا مخالف آن‌ها نیز انتخاب می‌شوند. در این روش می‌توانیم به سمت جهت مخالف هدایت شویم که ما را به سمت نزدیک‌تر شدن به راه‌حل بهینه ناشناخته هدایت می‌کند. لازم به ذکر است که نقطه مخالف از طریق انعکاس نقطه محاسبه‌‌شده از طریق نقطه‌ مرکزی به‌دست می‌آید. پس اگر x یک عدد حقیقی باشد که در بازه‌ی  قرار دارد، عکس آن،  توسط رابطه‌ (7) تعریف می‌شود. رابطه (7) در بعدهای بالاتر به‌صورت رابطه‌ی (2) تعریف می‌شود. فرض کنید  یک نقطه در فضای D بعدی باشد و متغیر  به‌صورت  تعریف شود، معکوس  توسط   به صورت رابطه‌ی (8) تعریف می‌شود. (7)     3-4- فرموله‌سازی مسئله تمرکز اصلی راه‌حل‌های پیشنهاد‌شده برای مسئله جای‌گذاری کنترل‌کننده‌ها، در تعداد کنترل‌کننده‌ها و محل قرارگیری آن‌ها است [16]. در این کار شبکه نرم‌افزارمحور به صورت یک گراف   نشان داده می‌شود، به‌طوری که  مجموعه‌ی گره‌ها و  یال‌های بین این گره‌ها در یک شبکه هستند. یال  یک ارتباط دوطرفه بین گره‌های  و  است. هر یال دارای وزنی است که نمایانگر پهنای باند ارتباط است. مجموعه‌ی  کنترل‌کننده‌های شبکه را نشان می‌دهد. در شبکه‌های نرم‌افزارمحور، چندین معیار معمولاً برای ارزیابی کارایی سیستم استفاده می‌شود. در این مقاله، برخی از این معیارها به شرح زیر تعریف شده‌اند. 3-4-1- متوسط تاخیر انتشار نحوه‌ی محاسبه‌ی متوسط تأخیر انتشار در شبکه‌ی نرم افزارمحور، توسط رابطه (9) تعریف می‌شود [30]. این رابطه از مجموع میانگین زمانی انتشار اطلاعات بین کنترل‌کننده‌ها و میانگین زمانی انتشار اطلاعات از سوئیچ‌ها به کنترل‌کننده‌ها به‌دست می‌آید. میانگین زمان انتشار اطلاعات بین کنترل‌کننده‌ها با  و میانگین زمان انتشار اطلاعات از سوئیچ‌ها به کنترل‌کننده‌ها با  نشان داده می‌شود، که در ادامه هر یک توضیح داده شده است. کوتاه‌ترین مسیر بین سوئیچ s،   و کنترل‌کننده‌ی c،  توسط  نمایش داده می‌شود و کوتاه‌ترین مسیر بین کنترل‌کننده‌ها ی  و  به صورت   نمایش داده می‌شود. کوتاه‌ترین مسیر بین دو گره  و  از طریق فاصله‌ی اقلیدسی بر طبق رابطه‌ی (10) به‌دست می‌آید [31]. (8)     الف) تأخیر انتشار بین کنترل‌کننده‌ها تاخیر بین کنترل‌کننده‌ها اهمیت بسیاری دارد زیرا ارتباط بین کنترل‌کننده‌ها برای رسیدن به همگامی بین اجزای شبکه ضروری است. تاخیر بین کنترل‌کننده‌ها می‌تواند به عملکرد شبکه تأثیر بگذارد، زیرا اگر جداول مسیریابی یا اطلاعات کنترلی به موقع به‌روزرسانی نشوند، کنترل‌کننده‌ها ممکن است تصمیمات نادرستی بگیرند. در صورت وجود تاخیر بین کنترل‌کننده‌ها، که توسط دورترین کنترل‌کننده محدود شده است، ممکن است به عملکرد شبکه آسیب وارد شود [32]. متوسط تأخیر بین کنترل‌کننده‌ها در شبکه نرم‌افزارمحور را می‌توان با استفاده از رابطه‌ی (11) به‌دست آورد  [33]. (9)   (10)     ب) تأخیرانتشار بین سوئیچ تا کنترل‌کننده  معادله (12) میانگین تأخیر سوئیچ به کنترل‌کننده را در سیستم‌های شبکه نرم افزارمحور نشان می‌دهد که در آن  کوتاه‌ترین مسیر از سوئیچ  تا کنترل‌کننده  است که با فاصله اقلیدسی محاسبه می‌شود [33].  (11)     3-4-2- عدم تعادل بار هر کنترل‌کننده در شبکه مسئول مدیریت مجموعه‌ای از سوئیچ‌ها است. اما وقتی که سوئیچ‌ها به نزدیک‌ترین کنترل‌کننده اختصاص داده می‌شوند، توزیع بار بر روی کنترل‌کننده‌ها نامتوازن می‌شود. به این معنی که برخی از کنترل‌کننده‌ها به شدت دچار بار کاری زیاد بوده، در حالی که از برخی دیگر به‌طور کامل استفاده نمی‌شود. به عبارت دیگر، عدم تعادل بار بین دو کنترل‌کننده توسط تفاوت در تعداد سوئیچ های اختصاص داده شده به هر کنترل‌کننده تعیین می‌شود. عدم تعادل بار بروی یک کنترل‌کننده با تعداد عناصری که به آن ارسال می‌شوند تعیین می‌شود که با نماد  نشان داده شده است. در این زمینه، عدم تعادل بار یک کنترل‌کننده با استفاده از رابطه (13) محاسبه می‌شود که s تعداد گره‌هایی است که قادر به ارتباط با کنترل‌کننده هستند [34].  (12)     3-4-3- مصرف انرژی در این مقاله، مصرف انرژی شبکه، طبق رابطه (14) تعریف شده است. در این رابطه،  مصرف انرژی کنترل‌کننده‌ی  را وقتی که روشن است، نشان می‌دهد.  مصرف انرژی پویای کنترل‌کننده  است که بر اساس بار کاری کنترل‌کننده در هر لحظه تغییر می‌کند و  تعداد سوییچ‌های تحت کنترل  را نشان می‌دهد.  یک مقدار تعریف‌شده توسط کاربر است.  مجموع مصرف انرژی بین کنترل‌کننده و سوییچ‌های تحت کنترل آن را نمایش می‌دهد. در حالی که  پهنای باند یال بین کنترل‌کننده  و سوییچ  است. (13)   (14)         4-       بیان مسئله پیدا کردن تعداد بهینه کنترل کننده ها کنترل‌کننده پیدا کردن مکان بهینه‌ی کنترل‌کننده   هدف این مقاله حل مسئله CPP با پیدا کردن تعداد و مکان بهینه‌ی کنترل‌کننده‌ها و در عین حال بهبود عملکرد شبکه و دستیابی به اهدافی مانند کاهش تأخیر انتها به انتها، کاهش مصرف انرژی و بهینه‌سازی تعادل بار است. مسئله‌ی CPP به عنوان یک مسئله‌ی NP-hard معرفی شده است. روش‌های فراابتکاری یک گزینه مناسب برای حل مسائل پیچیده و NP-hard مانند CPP هستند که با بررسی بخش کوچکی از فضای جست‌وجو می‌توانند راه‌حل نزدیک به بهینه را پیدا کنند. با این حال، این روش‌ها ممکن است پیچیده و زمان‌بر باشند. از طرف دیگر در مورد مسائل خوشه‌بندی، K-means و روش‌های چندمعیاری مشابه، اغلب به دلیل سرعت، سادگی و کارآمدی می‌تواند گزینه مناسبی باشند. به همین دلیل در این مقاله در فاز اول برای یافتن تعداد کنترل‌کننده‌ها و خوشه‌بندی از نسخه‌ی بهبود‌یافته‌یK-mean  استفاده شده است که می‌تواند با پیدا کردن تعداد مناسب خوشه‌ها بر اساس فاصله اقلیدسی گره‌ها، عمل خوشه‌بندی را انجام دهد. در این مقاله با تغییر تابع هدف در این الگوریتم علاوه بر فاصله اقلیدسی گره‌ها، ترافیک شبکه نیز در نظر گرفته می‌شود. در فاز دوم مقاله، الگوریتمی بر پایه‌ی ژنتیک به نام الگوریتم گله اسب بهبودیافته(MHOA)  تعریف می‌شود  و از آن برای پیدا کردن مکان کنترل‌کننده در هر خوشه استفاده می‌شود. MHOA ورژن بهبودیافته‌ی الگوریتم گله اسب (HOA) است. HOA یکی از الگوریتم‌های اخیرا پیشنهاد شده است که در حل بسیاری از مسائل دنیای واقعی به خوبی عمل می‌کند. با این حال، در برخی مسائل پیچیده ممکن است که در بهینه‌ی محلی گیر کند. MHOA تا حدی زیاد می‌تواند این مشکلات ر ا حل کند.‌  استفاده از یک جمعیت اولیه تصادفی در HOA منجر به بی‌ثباتی در عملکرد آن می شود. اگر بتوانیم جمعیت اولیه را به گونه‌ای انتخاب کنیم که تنوع بیشتری داشته باشند مشکل بهینه محلی تا حد زیادی می‌تواند حل شود و سرعت همگرایی الگوریتم و توانایی آن برای رسیدن به راه‌حل جهانی بهینه را افزایش می‌یابد. استفاده از استراتژی تضاد نخبگان می تواند به عنوان نقطه شروع مفیدی برای فرآیند جست‌وجو عمل کند و به‌طور بالقوه عملکرد کلی الگوریتم را افزایش دهد. در ابتدا، الگوریتم یک جمعیت اولیه را انتخاب می کند و برازندگی هر راه‌حل را ارزیابی می کند. سپس استراتژی EOLB برای انتخاب N جمعیت اعمال می شود به‌طوری که بهترین جمعیت انتخاب شده و برای اکتشاف بالاتر دقیقا نقطه‌ی مقابل این افراد نیز انتخاب می‌شود. این کار باعث بالا رفتن قدرت اکتشاف الگوریتم می‌گردد. MHOA از استراتژی EOBL برای اکتشاف بیشتر استفاده می‌کند. استفاده از عملگرهای ژنتیک قدرت اکتشاف و بهره‌برداری الگوریتم را بالا می‌برد و باعث همگرایی بهتر و سرعت بیشتر الگوریتم می‌شود. در فاز بعدی مقاله از الگوریتم MHOA برای پیدا کردن مکان کنترل‌کننده در داخل هر خوشه استفاده می‌شود. هر گره در داخل خوشه می‌تواند به عنوان کنترل‌کننده در نظر گرفته می‌شود. در این سناریو فرض شده است که هر سوئیچ فقط می‌تواند به یک کنترل‌کننده متصل شود و دو کنترل‌کننده با مختصات یکسان در شبکه وجود ندارند. در ادامه، جزئیات بیشتری در مورد نحوه انجام کار ارائه می‌شود. شکل 2 ساختار این مقاله را نشان می‌دهد.   شکل 2: ساختار کلی مقاله   4-1- پیدا کردن تعداد کنترل‌کننده‌ها با استفاده از K-means بهبودیافته   هر چه‌قدر تعداد کنترل‌کننده‌ها زیاد باشد شبکه در حالت ایده‌آل‌تری قرار خواهد گرفت. با این حال، استفاده از کنترل‌کننده‌ هزینه‌بر بوده و از طرف دیگر بیشتر از یک تعداد مشخص عملا تاثیر چندانی بر کارایی شبکه نخواهد داشت. تعداد کم کنترل‌کننده‌ها نیز می‌تواند به‌طور منفی بر کیفیت شبکه تأثیر بگذارد و منجر به ازدحام در شبکه شود. بنابراین تعیین تعداد بهینه‌ی ‌کنترل‌کننده‌ها در شبکه حیاتی است. در این مقاله برای تعیین تعداد کنترل‌کننده‌ها از الگوریتم K-means بهبود یافته و مفهوم خوشه‌بندی استفاده می‌کنیم. دراین نسخه از K-means نیازی به وارد کردن تعداد خوشه‌ها به عنوان ورودی نیست و تعداد خوشه‌ها نیز در حین اجرای الگوریتم تعیین می‌شود. در هر خوشه یک کنترل‌کننده برای کنترل سوئیچ‌های خوشه قرار می‌گیرد. تعداد کنترل‌کننده‌ها برابر با تعداد خوشه‌ها است. در این فاز علاوه بر تعیین تعداد کنترل‌کننده‌ها، سوئیچ‌های تحت کنترل یک کنترل‌کننده نیز تعیین می‌شوند. بهتر است که سوئیچ‌های نزدیک به هم و سوئیچ‌هایی که بیشتر با هم در ارتباط هستند تحت نظارت یک کنترل‌کننده باشند تا مجبور به بارگذاری اطلاعات شبکه بر روی کنترل‌کننده‌های متفاوت نباشیم. بنابراین سوئیچ‌های نزدیک به هم را در یک خوشه قرار می‌دهیم تا تحت نظارت یک کنترل‌کننده واحد باشند. از طرف دیگر اگر تعداد سوئیچ‌های یک خوشه و میزان پیام‌های ارسالی در یک شبکه زیاد باشد باعث ازدحام در آن کنترل‌کننده خواهد شد. بنابراین زمانی که ترافیک در شبکه زیاد باشد باید تعداد خوشه‌ها افزایش یابد تا ترافیک بین کنترل‌کننده‌ها تقسیم شود. از طرف دیگر، اگر بار شبکه کاهش یابد، توصیه می شود تعداد کنترل‌کننده‌ها کاهش یابد تا از هزینه‌های غیرضروری جلوگیری شود. در ابتدا حداکثر تعداد کنترل‌کننده‌های موجود به تعداد سوئیچ‌ها، به عنوان ورودی به الگوریتم K-means بهبودیافته داده می‌شود. تعداد خوشه‌ها تعیین‌کننده‌‌ی تعداد کنترل‌کننده‌هاست. الگوریتم اصلی به گونه‌ای تعریف شده است که فقط از فاصله اقلیدسی برای خوشه‌بندی استفاده می‌کند. ما در این مقاله علاوه بر فاصله اقلیدسی، ترافیک شبکه را نیز در نظر گرفته‌ایم. در اینجا، برای خوشه‌بندی سوئیچ‌ها از فاصله اقلیدسی آن‌ها و ترافیک شبکه استفاده می‌کنیم. احتمال اختصاص یک سوئیچ به خوشه‌ی k_ام توسط  نمایش داده می‌شود. برای هر سوئیچ ، یک آرایه به نام  در نظر گرفته می‌شود که طول آن برابر با تعداد کنترل‌کننده‌هاست،. هر سلول از  احتمال نگاشت سوئیچ  به یک کنترل‌کننده  را نشان می‌دهد. ابتدا، مقدار  به  تنظیم می‌شود که c تعداد کل کنترل‌کننده‌هاست که در ابتدا به تعداد سوئیچ‌ها در نظر گرفته شده است. زمانی که  برابر با  است، یعنی احتمال تخصیص آن سوئیچ به هر یک از کنترل‌کننده‌ها برابر است که نشان‌دهنده‌ی عدم وجود اطلاعات قابل دسترس در مورد  است. در هر تکرار،  بر اساس معادله (3) محاسبه می‌شود. برای در نظر گرفتن ترافیک هر خوشه علاوه بر فاصله‌ی اقلیدسی هر سوئیچ، رابطه‌ی 1 به صورت رابطه (15) تعریف می‌شود. به طوریکه  میزان بار در خوشه‌ی  و  نشان دهنده‌ متوسط بار شبکه می‌باشد.   مقادیر  بر اساس بار کنترل‌کننده به‌روزرسانی می‌شوند. حداکثر باری که یک کنترل‌کننده می‌تواند مدیریت کند، مربوط به ویژگی فیزیکی آن کنترل‌کننده است که از قبل مشخص است. زمانی که بار یک کنترل‌کننده به حداکثر نزدیک می‌شود، کنترل‌کننده در وضعیت بحرانی قرار می‌گیرد و کارایی آن کاهش می‌یابد. در چنین مواردی، توصیه می‌شود تا کنترل‌کننده‌های بیشتری به شبکه اضافه شوند تا بار متعادل شود. بنابراین، احتمال انتخاب این کنترل‌کننده برای همه گره‌ها کاهش می‌یابد در حالی که احتمال کنترل‌کننده‌های دیگر بر روی گره‌ها با مقدار مشابه افزایش می‌یابد. اگر بار بر روی یک کنترل‌کننده خیلی کم باشد، بهتر است که آن را غیرفعال شود. در این صورت، سوئیچ‌های متصل به این کنترل‌کننده باید مجدداً به یک کنترل‌کننده دیگر اختصاص یابند. بر اساس این اطلاعات، برخی از کنترل‌کننده‌ها روشن شده و دیگری خاموش می‌شوند. پس از به‌روزرسانی بردارهای احتمال، سوئیچ‌ها از روش چرخ رولت برای انتخاب کنترل‌کننده مناسب استفاده می‌کنند. در این مرحله، تعداد کنترل‌کننده‌ها تعیین می‌شود و سوئیچ‌های تحت کنترل هر کنترل‌کننده تعیین می‌شوند.   4-2- تعیین مکان کنترل‌کننده‌ها در این مرحله باید مکان بهینه‌ی کنترل‌کننده در هر خوشه تعیین شود. برای این کار تعداد کنترل‌کننده‌ها و مختصات سوئیچ‌های هر خوشه که در فاز اول تعیین شد به عنوان ورودی به این فاز انتقال یافته و مورد استفاده قرار می‌گیرند. خروجی مختصات مکانی کنترل‌کننده‌ها می‌باشد. مکان هر یک از سوئیچ‌ها می‌تواند به عنوان مکان یک کنترل‌کننده باشد. از آن‌جایی‌که یافتن مکان بهینه کنترل‌کننده یک مسئله ان-پی سخت است ما برای حل آن از یک الگوریتم فراابتکاری به نام MHOA استفاده می‌کنیم که ورژن بهبودیافته‌ی الگوریتم گله اسب می‌باشد. شکل 3 نحوه عمل MHOA ر ا نشان می‌دهد. ابتدا بعد از تولید جمعیت اولیه با استفاده از تابع ارزیابی مقدار برازندگی هر فرد جمعیت برآورد می‌شود. سپس براساس استراتژی تضاد نخبگان بهترین جمعیت انتخاب شده و برای اکتشاف بالاتر دقیقا نقطه‌ی مقابل این افراد نیز انتخاب می‌شود. این کار باعث بالا رفتن قدرت اکتشاف الگوریتم می‌گردد. MHOA، از عملگرهای ژنتیک برای اکتشاف و بهره‌برداری بیشتر و بهبود همگرایی و سرعت الگوریتم استفاده می‌کند. در MHOA ابتدا دو عدد تصادفی  و  بین 0 و 1 تولید می‌شوند. چون الگوریتم HOA، خود الگوریتمی قدرتمند می‌باشد، برای برخورداری از مزایای آن زمانی که  بزرگتر از 0.5  از HOA استفاده می‌شود. اگرکوچک‌تر از 0.5 و  بزرگ‌تر از 0.5 باشد از عملگرهای ساده‌ی ژنتیک شامل عملگر برش11 و جهش12 استفاده می‌شود. اگر کوچک‌تر از 0.5 و  کوچک‌تر از 0.5 باشد از HOA بهبودیافته استفاده می‌شود که در ادامه کامل شرح داده شده است. در استفاده از عملگرهای ژنتیک باید در نظر داشت که در HOA اسب‌های جوان، تاکید بیشتری بر روی اکتشاف وجود دارد، در حالی ‌که اسب‌های مسن تمایل به بهره‌برداری بیشتر دارند. بنابراین، برای اسب‌های جوان‌تر بیش‌تر از عملگرهای ژنتیکی که جست‌وجوی سراسری را ترویج می‌کنند، مانند جهش و ترکیب استفاده می‌شود. برای اسب‌های مسن بیشتر از عملگرهایی که تغییرات وابسته به والدین دارند و برای جست‌وجوی محلی مناسب‌تر هستند، استفاده می‌شود. عملگر کپی13 شامل کپی کردن یک قسمت از یک راه‌حل و الصاق آن در یک راه‌حل دیگر است. تعداد سلول‌های کپی شده می‌تواند درصد مشخصی از کل تعداد کنترل‌کننده‌ها باشد. عملگر جهش14، یک بخش تصادفی از راه‌حل را تغییر می‌دهد. تعداد سلول‌های تغییر داده شده توسط ضرب تعداد کنترل‌کننده‌ها در یک عدد تصادفی بین ۰ و ۱ تعیین می‌شود. عملگر برش تک‌نقطه‌ای15، یک نقطه‌برش و دو والد را انتخاب می‌کند. اطلاعات در یکی از طرفین نقطه برش بین والدین معاوضه می‌شود و دو فرزند جدید تولید می‌شوند. در عملگر برش دو‌نقطه‌ای16 دو نقطه‌ی برش و دو والد انتخاب می‌شوند و اطلاعات بین این نقاط در دو والد معاوضه می‌شوند.     شکل 3: نحوه عملکرد الگوریتم MHOA   در عملگر برش یکنواخت17 یک بردار برش شامل مقادیر دودویی به صورت تصادفی تولید می‌شود که تعیین می‌کند کدام سلول‌ها بین والدین جابه‌جا شوند. در عملگر تعویض18، دو والد انتخاب شده و ژن‌های آن به صورت تصادفی معاوضه می‌شوند. در این عملگر، تعداد ژن‌های معاوضه شده درصدی از کل تعداد کنترل‌کننده‌ها است[35-37].    (15)   Cross-over point     4 3 7 1 8 2     4 3 9 6 3 11     5 1 9 6 3 11     5 1 7 1 8 2   (د)     7 9 6 20 8 3   7 9 7 20 5 1     12 4 7 6 5 1     12 4 6 6 8 3   Random cross-over vector     0 0 1 0 1 1   (ج) Cross-over point       4 3 7 1 8 2     4 3 9 1 8 2     5 1 9 6 3 11     5 1 7 6 3 11         4 3 7 1 8 2     4 3 9 6 3 2     5 1 9 6 3 11     5 1 7 1 8 11     (الف) ((ب   (ی) 7 1 12 20 10 17   7 2 12 20 9 20   (و) 22 2 12 20 10 17   22 2 12 20 10 17     7 9 14 17 11 3   7 2 14 17 10 3       شکل 4: نحوه عملکرد عملگرهای ژنتیک. (الف) برش یکنواخت. (ب) برش تک نقطه‌ای. (ج) برش دونقطه‌ای. (د) تعویض. (و) عملگر جهش. (ی)عملگر کپی   در ادامه رفتارهای اسب‌ها با استفاده از عملگرهای ژنتیک در MHOA به روزرسانی شده‌اند. مقداریک عدد تصادفی بین 0 و 1 می‌باشد. برای اسب‌هایی که بیش از ۱۵ سال هستند، نحوه‌ی رفتار اسب‌ها بر اساس رابطه‌ی (16) تعیین می‌شود. اسب‌های مسن‌تر بیشتر رفتار چرا و دفاع را از خود نشان می‌دهند.   اسب‌هایی که 10 تا 15 سال سن دارند، بردار سرعت خود را با استفاده از رابطه (17) تعیین می‌کنند. بر اساس این رابطه، اگر مقدار r بیشتر از 75/0 باشد، از عملگر برش تک‌نقطه‌ای استفاده می‌شود. اگر مقدار r بین 25/0 و 5/0 باشد، از یک برش یکنواخت و اگر مقدار r کمتر از 5/0 باشد، از عملگر برش دو‌نقطه‌ای استفاده می‌شود. اسب‌ها در گروه  رفتارهای چرا، تقلید سلسله‌مراتبی، مکانیزم دفاع و اجتماعیت را نشان می‌دهند.   (16)     اسب‌های گروه گاما رفتارهای مختلفی مانند چرا، تقلید سلسله‌مراتبی، مکانیزم دفاع و اجتماعیت را نشان می‌دهند. با توجه به رفتار آن‌ها می‌توان فهمید که این گروه اسب‌ها هم تمایل به اکتشاف و هم بهره‌برداری دارند. رابطه (18) بردار سرعت را برای این اسب‌ها تعیین می‌کند. اگر مقدار  بیشتر از 0.75 باشد، عملیات جهش روی بردار رفتار تقلید انجام می‌شود. اگر مقدار r بین 5/0 و 75/0 باشد، عملیات جابه‌جایی روی بردارهای سلسله‌مراتبی و اجتماعیت انجام می‌شود. به‌طور مشابه، اگر مقدار r بین 25/0 و 5/0 باشد، یک برش دونقطه‌ای و جهش بر روی بردارهای مکانیزم دفاع و رفتارهای چرا انجام خواهد شد. (17)     برای اسب‌های جوان زیر 5 سال در گروه δ، به صورت رابطه (19) پیش می‌رویم. اسب های گروه δ تمایل بیشتری به اکتشاف دارند، به همین دلیل از عملگرهایی استفاده می‌کنیم که می‌توانند امکان کاوش را در این اسب ها افزایش دهند. فلوچارت نحوه‌ی بهبود HOA با عملگرهای ژنتیک در شکل 2 نشان داده شده است. (18)     (19)   شکل 5: نحوه بهبود الگوریتم HOA با عملگرهای ژنتیک   4-2-1- تابع ارزیابی هدف اصلی این مقاله شناسایی تعداد بهینه کنترل‌کننده‌های شبکه نرم‌افزار محور و موثرترین تخصیص سوئیچ‌های توزیع‌شده به این کنترل‌کننده‌ها است. این کار برای کاهش تاخیر انتها به انتها، به حداقل رساندن عدم تعادل شبکه و کاهش مصرف انرژی انجام می‌شود. در این زمینه، تابع تناسب با رابطه‌های (20) و (21) تعریف می‌شود. در اینجا، تابع  یک تابع غیر خطی از تعداد کنترل‌کننده‌های مستقر  است.   نشان‌دهنده‌ی متوسط تأخیر سرتاسری،  نشان‌دهنده‌ی بدترین تأخیر سرتاسری بوده و همچنین میانگین درجه عدم تعادل بار با   و بدترین درجه عدم تعادل بار  در نظر گرفته شده‌اند. علاوه بر این، میانگین مصرف انرژی به صورت  و بدترین مصرف انرژی به صورت  در شبکه تعریف شده‌اند. این مقادیر بر اساس روابط ارائه شده در بخش 3 محاسبه می شوند. 4-2-2- پیچیدگی محاسباتی برای ارزیابی کارایی یک الگوریتم هنگام حل مسائل بهینه‌سازی، محاسبه پیچیدگی محاسباتی بسیار مفید است. پیچیدگی محاسباتی کل MHOA می‌تواند به صورت رابطه‌ی (21) بیان شود. که  تعداد جمعیت بعد مسئله و  حداکثر تعداد تکرار را نشان می‌دهند. چون نصف جمعیت توسط الگوریتم اسب اجرا می‌شوند، پیچیدگی الگوریتم در این قسمت به صورت  تعریف می شود. از طرف دیگر  جمعیت فقط از الگوریتم ژنتیک و  از الگوریتم اسب بر پایه‌ی ژنتیک استفاده می‌کنند. رابطه (22) پیچیدگی محاسباتی MHOA را نشان می‌دهد. (20)   (21)     5-       تنظیمات شبیه‌سازی برای شبیه‌سازی این کار از یک سیستم دارای یک پردازنده Intel Core i7 با سرعت 80/2 گیگاهرتز، 16 گیگابایت رم و سیستم عامل ویندوز ده 64 بیتی استفاده است. الگوریتم‌ها در متلب 2016 پیاده‌سازی شده و به صورت موازی 4۰ بار اجرا شده‌اند. برای ارزیابی نتایج استفاده‌شده از دیتاست واقعی توپولوژی زو [38] استفاده شده است. برای ارزیابی مقیاس‌پذیری الگوریتم پیشنهادی از سه شبکه‌ی Arnet، Bics و Colt  که از لحاظ اندازه و توپولوژی کاملا متفاوت هستند، استفاده شده است. Aarnet، یک شبکه کوچک است که در لایه IP با 19 گره و 24 یال استرالیا را تحت پوشش خود قرار داده است. Bics شبکه‌ای متوسط در سطح اروپا بوده و دارای 46 گره و 85 یال می‌باشد. شبکه‌ی Colt، یک شبکه بزرگ است که در سراسر اروپا گسترده شده است و شامل 149 گره و 191 پیوند در سطح IP است. نتایج نشان می‌دهند که MHOA در هر دو شبکه نسبت به الگوریتم‌های دیگر بهتر عمل کرده است. پارامترهای شبیه‌سازی در جدول 2 نشان داده شده است، و جدول 3 پارامترهای استفاده شده در MHOA را نشان می‌دهد. در این تحقیق برای پیاده سازی شبکه‌ی پویا، ترافیک شبکه با بسته‌های با سایز متفاوت ایجاد شده است و برای هر بسته در ابتدای کار مشخص شده است که چه تایمی وارد شبکه خواهد شد. در هر راند بررسی می‌شود که کدام بسته‌ها باید در شبکه باشند و بر اساس تعداد و اندازه‌ی بسته‌ها ترافیک تعیین می‌شود. (22)     مقادیر پارامترها 100 تا 200 بایت سایز بسته 12 بیشینه تعدادکنترل‌کننده‌ها 40 بیشینه تکرار 50 سایز جمعیت تصادفی(0-250) ترافیک جدول2:پارامترهای شبیه‌سازی   [1] 1 Software Defined Networks (SDN) [2] 2 Controller Placement Problem [3] 3 NP-hard [4] 1 Horse Herd Optimization Algorithm [5] 1 Exploration [6] 2 Exploitation [7] 3 Elite Opposition-Based Learning [8] 4 Internet Topology ZOO [9] 1 Elite Opposition-Based Learning (EOBL)  [10] Opposition-Based Learning (OBL) 2  [11] 1 crossover [12] 2 mutation [13] 3 Duplicate [14] 4 Mutation [15] 5 One-point crossover [16] 1 Two-point crossover [17] 2 Uniform cross-over [18] 3 Swap