بهینهسازی استقرار مطمئن و انرژی کارای کاربردهای اینترنت اشیا در زیرساخت ابر و مه با استفاده از الگوریتم جستجوی فاخته
الموضوعات :یاسر رمضانپور فومشی 1 , میرسعید حسینی شیروانی 2
1 - دانشگاه آزاد اسلامی واحد بابل،دانشكده مهندسي برق
2 - دانشگاه آزاد اسلامی واحد ساری،دانشكده مهندسي برق
الکلمات المفتاحية: استقرار مطمئن, انرژی کارا, رایانش مه و ابر, کاربردهای اینترنت اشیا, کاربردهای توزیعشده,
ملخص المقالة :
استقرار کاربردهای اینترنت اشیا در زیرساخت مه به عنوان مکمل ابر به طور مؤثری باعث صرفهجویی در استفاده از منابع محاسباتی در زیرساخت ابر میشود. تلاشهای تحقیقاتی اخیر در حال بررسی چگونگی بهرهبرداری بهتر از قابلیتهای مه برای اجرا و پشتیبانی از کاربردهای اینترنت اشیا است. استقرار ناکارامد مؤلفههای کاربردها در مه منجر به اتلاف منابع، پهنای باند و افزایش مصرف انرژی میشود. همچنین توزیع مؤلفههای یک کاربرد روی تعداد حداقل ممکن از گرههای مه به منظور کاهش مصرف انرژی منجر به کاهش سطح قابلیت اطمینان خدمات میشود. در این مقاله یک الگوریتم فراابتکاری ترکیبی بر مبنای الگوریتم جستجوی فاخته برای استقرار ایستای مؤلفههای کاربرد روی زیرساخت مه با هدف مصالحه بین مصرف بهینه انرژی و کاهش اثر نقطه تکی شکست و تقویت قابلیت اطمینان کاربرد در برابر خرابی ارائه میشود. نتایج شبیهسازی نشان میدهد که روش ارائهشده در این مقاله، مصرف انرژی در شبکه مه را کاهش داده و نیازمندیهای كیفیت خدمات کاربرد اینترنت اشیا را با قابلیت اطمینان بالا تأمین میكند.
[1] OpenFog Consortium Architecture Working Group, An OpenFog Architecture Overview, Available: https://www.iiconsortium.org/pdf/OpenFog_Reference_Architecture_2_09_17.pdf, 2017.
[2] S. Azimi, C. Pahl, and M. Hosseini Shirvani, "Particle swarm optimization for performance management in multi-cluster IoT edge architectures," in Proc. 10th Int. Conf. on .Cloud Computing and Services Science, pp. 328-337, Prague, Czech Republic, 7-9 May 2020.
[3] M. Hosseini Shirvani, "A hybrid meta-heuristic algorithm for scientific workflow scheduling in heterogeneous distributed computing systems," Engineering Applications of Artificial Intelligence, vol. 90, Article ID: 103501, Apr. 2019.
[4] H. Hong, P. Tsai, and C. Hsu, "Dynamic module deployment in a fog computing platform," in Proc 18th Asia-Pacific Network Operations and Management Symp., 6 pp., Kanazawa, Japan, 5-7 Oct. 2016.
[5] M. Taneja and A. Davy, "Resource-aware placement of IoT application modules in fog-cloud computing paradigm," in Proc IFIP/IEEE Symp. on Integrated Network and Service Management, pp. 1222-1228, Lisbon, Portugal, 8-12 May 2017.
[6] S. Venticinque and A. Amato, "A methodology for deployment of IoT application in fog," J. of Ambient Intelligence and Humanized Computing, vol. 10, no. 2, pp. 1955-1976, May 2019.
[7] A. Brogi and A. Forti, "QoS-aware deployment of IoT applications through the fog," IEEE Internet of Things J., vol. 4, no. 5, pp. 1185-1192, Oct. 2017.
[8] R. Mahmud, K. Ramamohanarao, and R. Buyya, "Latency-aware application module management for fog computing environments," ACM Trans. on Internet Technology, vol. 19, no. 1, Article No.: 9, pp. 1-21, Feb. 2018.
[9] M. Vogler, J. M. Schleicher, C. Inzinger, and S. Dustdar, "DIANE-dynamic IoT application deployment," in Proc IEEE Int. Conf. on Mobile Services, pp. 298-305, New York, NY, USA, 27 Jun.-2 Jul. 2015.
[10] E. Saurez, K. Hong, D. Lillethun, U. Ramachandran, and B. Ottenwalder, "Incremental deployment and migration of geo-distributed situation awareness applications in the fog," in Proc 10th ACM Int. Conf. on Distributed and Event-based Systems, pp. 258-269, Irvine, CA, USA, 20-24 Jun. 2016.
[11] U. Arora and N. Singh, "IoT application modules placement in heterogeneous fog-cloud," International J. of Information Technology, vol. 13, no. 9, pp. 1975-1982, May 2021.
[12] S. Omer, S. Azizi, M. Shojafar, and R. Tafazolli, "A priority, power and traffic-aware virtual machine placement of IoT applications in cloud data centers," J. of Systems Architecture, vol. 15, Article ID: 101996, May 2021.
[13] I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: a survey," Computer Networks, vol. 47, no. 4, pp. 445-487, 15 Mar. 2005.
[14] J. P. Arcangeli, R. Boujbel, and S. Leriche, "Automatic deployment of distributed software systems: definitions and state of the art," The J. of Systems and Software, vol. 3pp. 198-218, May 2015.
[15] F. Bonomi, R. Milito, P. Natarajan, and J. Zhu, "Fog computing: a platform for Internet of Things and analytics," In: N. Bessis and C. Dobre (eds), Big Data and Internet of Things: A Roadmap for Smart Environments. Studies in Computational Intelligence, vol 546. Springer, Cham, pp. 169-186, 2014.
[16] S. Farzai, M. Hosseini Shirvani, and M. Rabbani, "Multi-objective communication-aware optimization for virtual machine placement in cloud datacenters," Sustainable Computing: Informatics and Systems, vol. 28, Article ID: 100374, Dec. 2020.
[17] X. S. Yang and S. Deb, "Cuckoo search via Le´vy flights," in Proc. of World Congress on Nature & Biologically Inspired Computing, pp. 210-214, Coimbatore, India, 9-11 Dec. 2009.
[18] S. M. Sait, A. Bala, and A. H. El-Maleh, "Cuckoo search based resource optimization of datacenters," Applied Intelligence, vol. 44, no. 3, pp. 489-506, Apr. 2016.
[19] M. Tavana, S. Shahdi-Pashaki, E. Teymourian, F. J. Santos-Arteaga, and M. Komaki, "A discrete cuckoo optimization algorithm for consolidation in cloud computing," Computers & Industrial Engineering, vol. 115, pp. 495-511, Jan. 2017.
[20] M. Hosseini Shirvani and S. Farzai, "Optimal deployment of IoT application components on hybrid fog2cloud infrastructure for reduction of power consumption toward green computing by cuckoo search algorithm," in Proc.of the 1st National Conf. of New Development in Green Studies, Computations, Applications, and Challenges, 10 pp. Noor, Iran, 10-11 Sept.. 2020.
[21] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Advances in Engineering Software, vol. 69?, pp. 46-61, Mar. 2014.
[22] C. G. Martínez, F. J. Rodriguez, and M. Lozano, "Genetic Algorithms," in Handbook of Heuristics, Springer, pp. 431-464, 2018.
[23] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proc. of the IEEE Int. Conf. on Neural Networks, pp. 1942-1948, Perth, Australia, 27 Nov.-1 Dec. 1995.
نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 19، شماره 4، زمستان 1400 233
مقاله پژوهشی
بهینهسازی استقرار مطمئن و انرژی کارای کاربردهای اینترنت اشیا
در زیرساخت ابر و مه با استفاده از الگوریتم جستجوی فاخته
یاسر رمضانپور فومشی و میرسعید حسینی شیروانی
چكیده: استقرار کاربردهای اینترنت اشیا در زیرساخت مه به عنوان مکمل ابر به طور مؤثری باعث صرفهجویی در استفاده از منابع محاسباتی در زیرساخت ابر میشود. تلاشهای تحقیقاتی اخیر در حال بررسی چگونگی بهرهبرداری بهتر از قابلیتهای مه برای اجرا و پشتیبانی از کاربردهای اینترنت اشیا است. استقرار ناکارامد مؤلفههای کاربردها در مه منجر به اتلاف منابع، پهنای باند و افزایش مصرف انرژی میشود. همچنین توزیع مؤلفههای یک کاربرد روی تعداد حداقل ممکن از گرههای مه به منظور کاهش مصرف انرژی منجر به کاهش سطح قابلیت اطمینان خدمات میشود. در این مقاله یک الگوریتم فراابتکاری ترکیبی بر مبنای الگوریتم جستجوی فاخته برای استقرار ایستای مؤلفههای کاربرد روی زیرساخت مه با هدف مصالحه بین مصرف بهینه انرژی و کاهش اثر نقطه تکی شکست و تقویت قابلیت اطمینان کاربرد در برابر خرابی ارائه میشود. نتایج شبیهسازی نشان میدهد که روش ارائهشده در این مقاله، مصرف انرژی در شبکه مه را کاهش داده و نیازمندیهای كیفیت خدمات کاربرد اینترنت اشیا را با قابلیت اطمینان بالا تأمین میكند.
کلیدواژه: استقرار مطمئن، انرژی کارا، رایانش مه و ابر، کاربردهای اینترنت اشیا، کاربردهای توزیعشده.
1- مقدمه
رایانش مه2 با پشتیبانی از استفاده یکپارچه منابع لبه و ابر3، محل قرارگیری کاربردهای4 اینترنت اشیا 5(IoT) را در نزدیکی منبع داده تسهیل میکند. استقرار6 کاربردها در لبه، منجر به کاهش بار شبکه و تضمین تحویل به موقع خدمات میشود. استقرار، مدیریت و به روز رسانی کاربردها در چنین محیط لایهای چالشهای جدیدی ایجاد میکند. شبکه مه در مقیاس وسیع، شامل تعداد انبوهی گره ناهمگن7 با منابع رایانشی8 (پردازش، حافظه، ذخیرهسازی و ...) مجزا است. بارهای کاری9 روی هر یک از گرههای شبکه پویا میباشد و هر کاربرد، نیازمندیهای خاص خود را از قبیل منابع محاسباتی، حساسیت به تأخیر و حفظ حریم خصوصی دارد. بنابراین برای استقرار مؤلفههای10 کاربرد در گرههای مه باید نیازمندیهای کاربرد و امکانات نرمافزاری، سختافزاری، پهنای باند و تأخیر بین گرههای شبکه مه در نظر گرفته شود [1].
استقرار مؤلفههای یک کاربرد روی حداقل گرهها در شبکه مه منجر به کاهش مصرف انرژی و استفاده بهینه از منابع رایانشی و همچنین کاهش تأخیر بین مؤلفههای کاربرد میشود، اما این طرح استقرار منجر به تقویت پدیده نقطه تکی شکست11 میگردد. هنگامی که یک گره مه حاوی کلیه مؤلفههای یک کاربرد دچار آسیب شود، عملکرد کاربرد مختل شده و از کار میافتد. لذا پدیده نقطه تکی شکست روی قابلیت اطمینان12 کاربرد مشتری تأثیر منفی میگذارد و در نتیجه باید راهکاری برای استقرار مناسب مؤلفهها برای ارائه خدمات مطمئن اتخاذ نمود.
در استقرار یک کاربرد با تعداد مؤلفههای اندک در شبکه مه، حالتهای متعددی وجود دارد. با افزایش تعداد مؤلفهها و گرههای مه با توجه به ماهیت ناهمگن آنها، کشف راه حل بهینه استقرار دشوارتر شده و استخراج آن برای کاربر انسانی غیر ممکن میشود. موضوع استقرار مؤلفهها، یک مسأله ان پی سخت13 است که در آن راه حل دقیق در زمان چندجملهای وجود ندارد [2] و [3]. در سالهای اخیر، تحقیقاتی در رابطه با توزیع مؤلفهها در زیرساخت ابر و مه انجام شده است. هونگ و همکاران، یک بستر14 رایانش مه یکپارچه برای استقرار پویای مؤلفهها روی گرههای مه پیشنهاد دادهاند، به طوری که در این روش برای مقابله با نقطی تکی شکست، مؤلفهها روی بیش از یک گره توزیع میشوند [4]. یک رویکرد توزیع مؤلفههای کاربردهای اینترنت اشیا، با توجه به حساسیت به تأخیر
و استفاده کارامد از منابع شبکه توسط تانجا و همکاران ارائه شده است [5]. روشی برای حل مسأله جایابی خدمات مه شامل نگاشت بهینه بین کاربردهای اینترنت اشیا و منابع محاسباتی با توجه به تأمین نیازمندیهای کیفیت خدمات کاربرد توسط محققین ارائه گردیده است. در این روش، نیازمندی کاربرد به حسگرها مورد توجه قرار نگرفته است [6]. بروگی و همکاران، یک مدل عمومی و قابل توسعه برای توصیف استقرار آگاه از کیفیت خدمات15 کاربردهای اینترنت اشیا در شبکه مه پیشنهاد دادهاند [7]. پژوهشگران برای جایابی و هدایت مؤلفهها، سازماندهی غیر متمرکز
را پیشنهاد کردهاند که این روش بر چالشهای نظارت متمرکز مانند
سربار مدیریت کاربرد، نقطه تکی شکست، ارتباطات افزونه و تأخیر در تصمیمگیری غلبه میکند [8]. در روش پیشنهادی این مقاله، یک الگوریتم انرژی کارا16 برای استقرار مطمئن مؤلفههای کاربرد در شبکه مه و ابر ارائه میشود. این روش در سناریوهایی مانند سیستم هشدار سرقت، سیستم اطفای حریق، مراقبت از سالمندان و غیره کاربرد دارد. در این سناریوها، قابلیت اطمینان و اتکا به سیستم برای مشتری از اهمیت زیادی برخوردار است. از دید مهندسی نرمافزار، ایجاد پروژه دارای دو فاز طراحی و زمان اجراست. تمرکز مقاله حاضر بر روی فاز طراحی در راستای ایجاد طرح استقرار ایستای مؤلفههای کاربرد روی زیرساخت مه بر اساس پروفایل کیفیت خدمات درخواستی کاربران است. بنابراین سهم اصلی این مقاله به شرح زیر خلاصه میشود:
1) برای مصرف بهینه انرژی، زیرشبکههای مشکامل17 از شبکه مه استخراج میشود. از بین آنها مناسبترین زیرشبکه انتخاب گردیده و مؤلفههای کاربرد روی گرههای زیرشبکه انتخابی با توجه به منابع گرهها و ترافیک ارتباطی بین مؤلفهها توزیع میشود که برای این منظور دو الگوریتم ابتکاری18 ارائه میگردد.
2) برای کاهش اثر نقطه تكی شكست در استقرار مؤلفههای یک كاربرد و تأمین قابلیت اطمینان و اتکای مشتری به کاربرد، حداقل تعداد گرههای مه مورد نیاز برای استقرار مؤلفههای یک كاربرد به تعداد گرههای زیرشبکه مشکامل انتخابی محدود میشود.
3) یک الگوریتم استقرار مؤلفهها بر اساس الگوریتم فراابتكاری ترکیبی19 با رویکرد بهینهسازی مصرف انرژی و تأمین قابلیت اطمینان کاربرد کاربر طراحی میشود.
روش پیشنهادی در سناریوهای مختلف ارزیابی شده و نتایج به دست آمده از شبیهسازی، نشاندهنده برتری قابل توجه روش پیشنهادی در برابر سایر رویکردها است.
در ادامه، مقاله به شرح زیر سازماندهی شده است: بخش 2 به مروری بر کارهای مرتبط اختصاص دارد. مدلها و چارچوبهای پیشنهادی سیستم در بخش 3 قرار گرفته است. بیان مسئله در بخش 4 تشریح و الگوریتم پیشنهادی در بخش 5 ارائه میشود. کار پیشنهادی در بخش 6 شبیهسازی شده و مورد ارزیابی قرار میگیرد. در آخر، بخش 7 به نتیجهگیری و تحقیقات آینده اشاره دارد.
2- مروری بر کارهای گذشته
در این بخش، کارهای انجامشده در سالهای اخیر در زمینه استقرار کاربردها در زیرساخت مه و ابر مرور میشود.
هونگ و همکاران، یک بستر برای توزیع پویای مؤلفهها در زیرشبکه مه پیشنهاد دادهاند. در روش پیشنهادی، تقاضاها به یک سرویسدهنده ارسال و سپس در پایگاه داده ذخیره میشود. هر تقاضا به چندین مؤلفه تقسیم شده و با استفاده از داكر20 یا کانتینر21 بستهبندی میگردد. یک الگوریتم ابتکاری برای استخراج طرح استقرار مؤلفهها اجرا و طرح به دست آمده برای توزیع مؤلفهها به بستر مه ارسال میشود. هدف اصلی، دستیابی حداکثری به تولید طرحهای استقرار موفق برای کاربردهای کاربران میباشد [4].
یک الگوریتم آگاه از شبکه22 برای استفاده بهینه از منابع توسط تانجا و همکاران پیشنهاد شده است. این الگوریتم، گرههای مه را بر اساس ظرفیت و مؤلفههای کاربرد را بر اساس نیازهای موجود مرتب میکند، سپس در صورت تأمین شرطها، نگاشت مؤلفههای کاربرد به گرههای مه انجام میشود. بدین ترتیب مؤلفهها بر اساس انتظار منبع اولویتبندی میشوند. روش پیشنهادی نشان میدهد که استفاده ترکیبی از ابر و مه
در مقایسه با استفاده تنها از ابر برای ارائه خدمات به مؤلفهها، باعث کمینهسازی تأخیر انتهابهانتها23 میشود [5].
ونتیسینکو و همکاران، روشی را برای پشتیبانی از توسعهدهنده برای حل مسأله جایابی خدمات مه ارائه دادهاند. در این روش، نگاشت بهینه بین کاربردهای اینترنت اشیا و منابع محاسباتی با توجه به نیازمندیهای کیفیت خدمات کاربرد استخراج میشود. در روش پیشنهادی، بهترین پیکربندی استقرار در زمینه انرژی هوشمند ارائه میگردد. برای پاسخگویی به نیازمندیهای کیفیت خدمات کاربرد، مهلتهای زمانی و توان عملیاتی بایستی حفظ شود [6].
در دسترس بودن مدلهای مناسب زیرساختها و کاربردهای مه، برای موفقیت استقرارهای خودکار آگاه از کیفیت خدمات بر روی زنجیره ابر تا اشیا بسیار مهم است. اکثر ابزارهای پیشرفته برای استقرار خودکار نرمافزار توزیعشده24، در استخراج طرحهای استقرار مطلوب از ویژگیهای غیر عملیاتی پشتیبانی نمیکنند. بدین ترتیب یک مدل ساده و کلی برای پشتیبانی از استقرار آگاه از کیفیت خدمات کاربردهای چندمؤلفهای اینترنت اشیا در زیرساختهای مه توسط بروگی و همکاران ارائه شد. این مدل، کیفیت سیستمهای عملیاتی زیرساختهای موجود (تأخیر و پهنای باند)، تعامل بین مؤلفههای نرمافزار، اشیا و سیاستهای تجاری را توصیف میکند. الگوریتمهایی نیز برای استقرار مطلوب مؤلفههای کاربرد در زیرساخت مه ارائه شده است [7].
محمود و همکاران، مدیریت آگاه از تأخیر25 مؤلفههای کاربرد را در رایانش مه پیشنهاد دادهاند. در روش پیشنهادی، تأخیر در دسترسی به خدمات، زمان تحویل خدمات و تأخیر در ارتباطات داخلی در نظر گرفته میشود. هدف از کار، تضمین مهلت تحویل خدمات و استفاده بهینه از منابع در مه میباشد. برای بهینهسازی تعداد گرههای مه میزبان مؤلفهها، از روش هدایت و تخصیص مجدد مؤلفههای کاربرد استفاده میشود.
در این مقاله، استفاده از سازماندهی غیر متمرکز برای غلبه بر محدودیتهایی مثل سربار مدیریت کاربرد، نقطه تکی شکست، ارتباطات افزونه و تأخیر در تصمیمگیری برای جایابی و هدایت مؤلفهها پیشنهاد میشود [8].
یک چارچوب برای تولید توپولوژی استقرار بهینه کاربردهای ابری اینترنت اشیا، متناسب با زیرساختهای فیزیکی موجود، توسط وگلر و همکاران پیشنهاد گردیده است. برای انعطافپذیری کاربردهایی که توپولوژی استقرار آنها با گذشت زمان تکامل مییابد، جدایی مؤلفهها لازم
جدول 1: خلاصه مروری بر کارهای گذشته.
مقالهها | اهداف استقرار | |||||
توزیعشده | قابلیت اطمینان | آگاه از منابع | آگاه از ترافیک | انرژی کارا | ||
[4] | P | O | P | O | P | |
[5] | P | O | P | O | P | |
[6] | P | O | P | O | O | |
[8] | P | O | P | O | P | |
[9] | P | O | P | O | P | |
[10] | P | O | O | O | O | |
[11] | P | O | P | O | O | |
[12] | P | O | P | P | P | |
مقاله پیشنهادی | P | P | P | P | P |
است. تغییرات در توپولوژیهای استقرار کاربرد میتواند به خاطر نیاز استقرار کاربرد جدید، تغییر در زیرساختهای فیزیکی در لبه شبکه (به عنوان مثال، حذف/ اضافهکردن حسگرها یا دروازهها)، تغییرات محیطی مانند تغییر الگوهای درخواست مشتری یا تغییرات تکاملی در منطق تجارت کاربرد در طول چرخه عمر آن نیز باشد. در تولید توپولوژی استقرار، پارامترهایی نظیر زمان مورد نیاز برای استقرار، زمان و پهنای باند مورد نیاز برای اجرای کاربرد و بهرهبرداری از دستگاههای لبه26 ارزیابی شده است [9].
سوارز و همکاران، یک زیرساخت برنامهنویسی توزیعشده برای زنجیره محاسباتی گرههای مه و ابر تحت عنوان فاگلِت27 ارائه دادهاند. فاگلِت به طور خودکار منابع محاسباتی مه را در سلسلهمراتب شبکه کشف میکند و مؤلفههای کاربرد را بر روی گرههای مه متناسب با نیازمندی تأخیر هر مؤلفه مستقر مینماید. همچنین از چند کاربرد کنار هم روی هر گره
مه پشتیبانی کرده و ایپیآیهای 28(API) ارتباطی را برای مؤلفههای توزیعشده کاربرد در گرههای مختلف در سلسلهمراتب شبکه فراهم میکند. به کمک این ایپیآیها، مؤلفهها شرایط و وضعیت کاربرد را با هم تبادل میکنند. زیرساخت پیشنهادی به منظور انتزاع دادههای وابسته به مکان
و زمان و برای ذخیره و بازیابی دادههای تولیدشده در گرههای محلی
نیز ایپیآیهایی را فراهم میکند. در این مقاله برای اجرا، مدیریت و مهاجرت29 مؤلفهها بین گرههای مه و نیازهای محاسباتی کاربرد الگوریتمهایی ارائه شده است [10].
ارورا و همکاران یک الگوریتم برای جایابی مؤلفههای ناهمگن کاربردها در زیرساخت مه ارائه کردهاند. در این الگوریتم ابتدا مؤلفهها بر اساس اندازه مرتب شده و سپس مؤلفههای کوچکتر در یک توپولوژی سلسلهمراتبی در گرههای میزبان جایابی میشوند. در فرایند جایابی، وابستگی بین مؤلفهها، پارامتر قابلیت اطمینان کاربر به کاربرد، مصرف انرژی و تأخیر کل کاربرد در نظر گرفته نمیشود [11].
یک رویکرد آگاه از ترافیک و انرژی مبتنی بر اولویت برای جایابی ماشینهای مجازی کاربردهای اینترنت اشیا در زیرساخت ابری توسط اومر و همکاران ارائه شد. در این روش، ماشینهای مجازی کاربردها در یک توپولوژی Fat Tree در گرههای میزبان در ابر جایابی میشوند. در این
شکل 1: معماری مبتنی بر مش.
مقاله، قابلیت اطمینان کاربر به کاربرد در نظر گرفته نمیشود. همچنین رویکرد ارائهشده برای توزیع مؤلفههای کاربرد در لبه شبکه قابل استفاده نیست [12]. در جدول 1 مقایسه تحقیقات پیشین برای استقرار کاربردهای اینترنت اشیا در زیرساخت مه و ابر ارائه گردیده است.
در مقالات بررسیشده برای توزیع مؤلفهها، معیارهای نقطه تکی شکست و همچنین مصرف منابع شبکه مانند پهنای در نظر گرفته نمیشود. لازم به ذکر است که در نظر گرفتن پارامترهای مذکور، در فرایند توزیع مناسب مؤلفهها تأثیر بسزایی دارد. جنبه منحصر به فرد کار ما در مقایسه با کارهای موجود، تقویت قابلیت اطمینان کاربرد کاربر از جنبه تحملپذیری در برابر خطا و استقرار آگاه از ترافیک30 کاربردها روی گرههای مه میباشد.
3- مدل سیستم
در این بخش مدلی مبتنی بر مه به منظور استقرار مؤلفههای کاربرد ارائه میشود و همچنین یک چارچوب31 برای مدیریت مؤلفهها پیشنهاد میگردد. در آخر، مسأله استقرار مؤلفههای کاربرد روی گره مه تشریح میشود. متغیرها و پارامترهای ورودی استفادهشده در مدل و مفاهیم آنها در جدول 2 ارائه گردیده است.
3-1 چارچوب سیستم
مدل سیستم هدف در شکل 1 ارائه گردیده است و با توجه به شکل، از یک سازماندهنده32 بر بالای مه استفاده میشود. یکی از مسئولیتهای سازماندهنده، استخراج زیرشبکههای مشکامل از گرههای مه میباشد. معماری ارتباطی گرهها در هر زیرشبکه، شبیه معماری شبکه مش بیسیم است [13]. الگوی رایانشی در هر شبکه مشکامل با شبکه مش سنتی متفاوت است. از شبکه مش گرههای مه (سوئیچها و سرویسدهندههای مه) برای عملیات توزیعشده در داخل شبکه استفاده میگردد. پس از استخراج مشهای کامل، از بین آنها زیرشبکه مناسب انتخاب شده و سازماندهنده با توجه به ویژگی مؤلفههای کاربرد در مورد استقرار آنها در
جدول 2: علایم مورد استفاده در مدل سیستم.
علامت | تعریف |
| شبکه مه |
| یک زیرشبکه با مش كامل از گرههای مه |
| تعداد گرههای مه در یک |
| گره مه |
| شناسه گره مه |
| مشخصه سختافزاری گره مه |
| مشخصه نرمافزاری گره مه |
| ظرفیت محاسباتی، حافظه و ذخیرهسازی گره مه |
| ظرفیت نرمافزاری |
| ظرفیت حسگر |
| گره عضو |
| حسگرهای گره مه |
| پهنای باند پیوند |
| تأخیر پیوند |
| پهنای باند بین گره و |
| تأخیر پیوند ارتباطی بین گره و |
| فاصله گره مه و |
| کاربرد کاربر |
| حداقل گرههای مورد نیاز برای میزبانی مؤلفههای یک کاربرد |
| تعداد مؤلفههای کاربرد |
| لیست مؤلفههای کاربرد |
| مشخصات مؤلفه از کاربرد |
| سختافزار مورد نیاز مؤلفه |
| نرمافزار مورد نیاز مؤلفه |
| مؤلفههای کاربرد ، مستقر در گره |
| پهنای باند مطلوب بین مؤلفه و |
| تأخیر مطلوب بین مؤلفه و |
| منابع سختافزاری درخواستی مؤلفههای کاربرد |
| منابع نرمافزاری درخواستی مؤلفههای کاربرد |
| منابع حسگر درخواستی مؤلفههای کاربرد |
| ترافیک بین مؤلفه و |
| اگر مؤلفه روی گره مه باشد برابر با 1 و در غیر این صورت 0 است. |
| اگر گره مه فعال باشد برابر با 1 و در غیر این صورت 0 است. |
مشکامل انتخابی تصمیمگیری میکند. این سازماندهنده به صورت مفهومی متمرکز بوده و میتوان به منظور تحملپذیری در برابر خطا آن را به صورت توزیعشده پیادهسازی کرد تا از نقطه تکی شکست جلوگیری شود. اولویت اصلی در چارچوب پیشنهادی، استخراج طرح استقرار با توجه به مشهای کامل انتخابی و توزیع مؤلفهها بر مبنای طرح میباشد. در توزیع مؤلفهها، تنها آنهایی برای استقرار به زیرساخت ابر منتقل میشوند که حساس به تأخیر نبوده و به صورت دورهای برای پردازش اطلاعات با آنها ارتباط برقرار میشود.
به منظور مدیریت و استقرار مناسب مؤلفههای کاربرد در گرههای
مه با توجه به کارایی سیستم، از یک چارچوب برنامهریز استقرار33
در سازماندهنده مه استفاده میشود. همان طور که در شکل 2 نشان داده
شکل 2: چارچوب مدیریت مؤلفههای کاربرد.
شده است، قسمت برنامهریزی شامل مدیر مؤلفههای کاربرد و همچنین ماژولهایی34 است که در مدیریت مؤلفهها کمک میکنند. در کنار برنامهریز استقرار، ماژولهایی برای ذخیره و بازیابی اطلاعات شبکه و سایر منابع زیرشبکههای مشکامل مه قرار دارد. اطلاعات گردآوری شده، توسط ماژول برنامهریز استقرار برای مدیریت مؤلفههای کاربرد و ارائه یک طرح استقرار مطلوب استفاده میشود. در ادامه جزئیات مربوط به این مؤلفهها در چارچوب پیشنهادی تشریح میگردند:
1) مدیر مؤلفههایکاربرد: ماژول اصلی است که از سایر ماژولهای موجود در چارچوب برای تصمیمگیری در مورد نحوه استقرار مؤلفههای كاربرد در گرههای مه یا ابر استفاده میکند. در یک كاربرد چندمؤلفهای، به خاطر وابستگی مؤلفهها به هم، تصمیمگیری برای استقرار بر اساس عوامل متعددی مانند قابلیت دسترسی به منابع، ساختار شبکه، نیازمندیهای کیفیت خدمات برای كاربرد، توزیع بار و غیره صورت میگیرد. استقرار مؤلفهها میتواند بر اساس اهدافی مثل کاهش مصرف انرژی، کمینهسازی ارتباطات شبکه و همچنین کاهش تأخیر کلی در كاربرد انجام شود.
2) اطلاعات منابع مؤلفهها: نیازهای پردازشی و حافظه مورد نیاز مؤلفههای کاربرد را از تقاضای ارسالی توسط کاربران استخراج میکند و سپس برای اتخاذ تصمیمهای استقرار در اختیار مدیر مؤلفههای کاربرد قرار میدهد.
3) اطلاعات ارتباطی مؤلفهها: ارتباطات سهم عمدهای در مصرف منابع گرههای مه مورد استفاده در اینترنت اشیا دارند. مدیریت مؤلفههای کاربرد در گرههای مه شامل بهینهسازی توأم منابع محاسباتی، حافظه و ارتباطات میباشد. این ماژول، اطلاعات ارتباطی مؤلفههای کاربرد را از تقاضای ارسالی توسط کاربران استخراج میکند و در اختیار مدیر مؤلفههای کاربرد قرار میدهد.
4) کشف منابع زیرشبکههای مشکامل: بر مبنای اطلاعات دریافتی از مدیر مؤلفههای کاربرد، مخزن اطلاعات زیرشبکههای مشکامل
را پایش میکند و اطلاعات مشهای کامل مطلوب برای استقرار مؤلفهها را به مدیر مؤلفههای کاربرد ارسال میکند.
5) مدیر زیرشبکههای مشکامل: با توجه به اطلاعات دریافتی از مه، زیرشبکههای مشکامل از گرههای مه را استخراج کرده و اطلاعات این زیرشبکهها را در مخزن اطلاعات ذخیره میکند. همچنین با
شکل 3: مشخصات یک زیرشبکه مشکامل و گرههای عضو.
نظارت دورهای بر زیرساخت مه، وضعیت مشهای کامل موجود در مخزن را اعتبارسنجی مینماید.
3-2 مدل مه
در این مقاله فرض میشود که شبکهای متشکل از گره مه با
توان پردازشی و انرژی ناهمگن داریم که قابلیت ذخیرهسازی و اجرای مؤلفههای كاربرد را دارند. گرههای مه در شبکه مفروض، عضو یک یا چند زیرشبكه مشکامل میباشند. هر یک از گرههای مه به صورت مستقیم یا غیر مستقیم، از طریق اتصالات بیسیم یا باسیم به انواعی از گرههای حسگر دسترسی دارند. یک گره مه با استفاده از یک بردار نشان داده میشود که در این بردار شناسه گره در شبکه مه، شناسه در مشکامل، سختافزار، نرمافزار و لیست حسگرهای در دسترس گره مه میباشند. مؤلفههایی که در گرههای یک مشکامل توزیع میشوند، به قابلیتهای نرمافزاری و حسگرهای سایر گرههای مه در همان مشکامل دسترسی دارند. لینک ارتباطی35 بین گرههای مه را میتوان با استفاده از بردار نشان داد. در این بردار، میزان تأخیر و پهنای باند پیوند میباشد. شکل 3 جزئیات یک مشکامل را نشان میدهد.
مدل شبکه ارتباطی: شبکه ارتباطی در یک زیرشبکه مشکامل با استفاده از یک گراف مدل میشود. در این گراف یک مجموعه از گرههای مه و فاصله بین و میباشد. در هر زیرشبکه مشکامل اگر باشد، آن گاه است و در غیر این صورت خواهد بود. در (1) شبکه ارتباطی و ماتریس فاصله گرههای مه نشان داده شده است
(1)
شکل 4: مشخصات مؤلفههای کاربرد.
3-3 مدل کاربرد
در سالهای اخیر با توجه به تغییر ماهیت خواستههای کاربران و انتظارهای جدید از خدمات مبتنی بر اینترنت، نوع طراحی کاربردهایی که دادههای کاربر را در مقیاس گسترده پردازش میکنند نیز متناسب با تقاضا تغییر کرده و برای تأمین نیازهای کاربران از ساختار چندمؤلفهای برخوردار است [14]. این مؤلفهها به هم وابسته بوده و برای تأمین خواسته مشتری با هم همکاری میکنند. برای مثال یک کاربرد اینترنت اشیای ساده مراقبت از سالمندان را در نظر بگیرید که توسط یک شرکت ارائه خدمات سلامت هوشمند به مشتریان خود ارائه شده است. این کاربرد از سه مؤلفه مرکز کنترل برای تفسیر داده جمعآوری شده و کنترل دستی سیستم، مدیر وضعیت برای نظارت بر وضعیت افراد سالخورده و ناتوان و اطلاعرسانی فوری به نزدیکترین مرکز درمانی در صورت بروز مشکلات جسمی و روحی و ماشین یادگیری برای ثبت تاریخچه اطلاعات افراد و تخمین وضعیت سلامتی آینده آنها تشکیل
شده است. مؤلفه حساس به تأخیر نبوده و میتوان آن را در ابر یا مراکز داده در زیرساخت مه مستقر کرد.
منابع سختافزاری و قابلیتهای نرمافزاری مورد نیاز هر مؤلفه در شکل 4 آمده و ارتباط بین مؤلفهها از طریق پیوندهایی به تصویر کشیده شده است. برای مدیریت به موقع وضعیت سالمندان، مؤلفه باید به حسگرهای مورد نیاز (حسگرهای کنترل وضعیت جسمانی) و یک محرک فعالکننده مکانیزمهای عملیات مقدماتی و اطلاعرسانی به مراکز درمانی، دسترسی پیدا کند و این باید در عرض 10 میلیثانیه از محل استقرار تا محل نصب حسگر و محرک اتفاق بیفتد. توجه داشته باشید که انتظار میرود گرههای مه یا ابر بتوانند از طریق ایپیآیهای ارائهشده توسط لایه میانافزار مه، از راه دور به اشیای موجود در گرههای همسایه دسترسی داشته باشند [15].
مسألهای كه برای استقرار مؤلفههای کاربرد فوق بایستی حل شود این است كه چگونه میتوان این مؤلفه را به گونهای مستقر كرد كه منابع مورد نیاز آنها برآورده شود. حتی برای این مثال ساده، باید طرحهای متعدد استقرار برای استخراج یک نگاشت مطلوب برای مؤلفههای این کاربرد، ارزیابی شود. زیرا بر اساس منابع موجود، بیش از یک مؤلفه میتواند در یک گره مستقر شود و تعیین استقرارهای مطلوب با رشد زیرساختها و تعداد مؤلفههای كاربرد، از حد توان کاربر انسانی خارج شده و لازم است از الگوریتمهای جستجوی هوشمند استفاده گردد.
در این مقاله فرض میشود که تعداد كاربرد اینترنت اشیا داریم و هر كاربرد با استفاده از یک بردار نشان داده میشود. هر كاربرد چندین مؤلفه دارد که و به ترتیب تعداد و لیست مؤلفههای كاربرد میباشد و هر مؤلفه با استفاده از یک بردار نشان داده میشود (شکل 4). در بردار هر مؤلفه، شناسه مؤلفه، سختافزار مورد نیاز، نرمافزار مورد نیاز و لیست حسگرهای مورد نیاز است که توسط گره مه میزبان مؤلفه بایستی تأمین گردد.
کاربرد کاربر با استفاده از یک گراف مدل میشود که در این گراف، مؤلفههای کاربرد و ترافیک ارسالی بین و میباشد. در (2) ماتریس ترافیک بین مؤلفههای کاربرد نشان داده شده است
(2) اندیس درایه 1و 3 ماتریس تغییر کرد
3-4 مدل قابلیت اطمینان
استقرار مؤلفههای یک کاربرد روی حداقل تعداد گرهها در مه، منجر به دستیابی حداکثری به اهدافی مانند کاهش مصرف انرژی و استفاده بهینه از منابع رایانشی میشود، اما یکی از چالشهای پیش رو تقویت پدیده نقطه تکی شکست برای کاربردهای کاربر میباشد. لذا برای این که
هم اهداف مالکان رایانش مه در دستیابی به اهداف بهینه تأمین شود و همچنین درجه آسیبپذیری کاربردها در توزیع متمرکز در زیرساخت مه نیز کمتر گردد، یک حد آستانه برای تعداد گرههای مه برای توزیع مؤلفههای کاربرد در نظر گرفته میشود. بدین منظور، حداقل تعداد گرهها برای توزیع مؤلفهها برابر با تعداد گرهها در زیرشبکه مشکامل انتخابی است. در صورت عدم تحقق با کمترین فاصله نسبت به تعداد گرههای زیرشبکه مشکامل، فرایند توزیع مؤلفهها انجام میشود.
3-5 مدل استقرار
برای استقرار مؤلفهها از مشهای کامل استخراجشده، متناسب با نیازهای کاربرد یک مشکامل انتخاب میشود. گرههای مه در یک مشکامل، منابع مورد نیاز مؤلفهها (تأخیر، پهنای باند و حسگرها) را تأمین میکنند. فرض ما در مدل پیشنهادی بر این است که حسگرها یا نرمافزارهای مورد نیاز مؤلفههای کاربرد به صورت اشتراکی توسط گرههای مه در یک زیرشبکه مشکامل در دسترس خواهند بود.
در فرایند توزیع مؤلفههای کاربرد روی گرههای مه بایستی منابع محاسباتی، فاصله گرههای مه و پارامترهای کیفیت خدمات مورد نیاز مؤلفههای کاربرد در نظر گرفته شود. به منظور کاهش بار ترافیک بایستی ماتریس فاصله بین گرههای مه در گراف شبکه و همچنین ماتریس ترافیک بین مؤلفههای یک کاربرد را نیز محاسبه کرد. باید توجه داشت که پیوند ارتباطی بین گرههای مه و به لحاظ تأخیر و پهنای باند، ظرفیت ثابتی دارد و بنابراین نرخ ترافیک مؤلفههای کاربردها با ظرفیت پیوند بین گرههای مه محدود میشود، لذا داریم
(3)
در عبارت فوق، و به ترتیب پهنای باند و تأخیر مطلوب بین مؤلفههای و و و به ترتیب پهنای باند و تأخیر پیوند ارتباطی بین گرههای مه و است. یک متغیر دودویی برای تعیین وضعیت استقرار مؤلفههای کاربرد روی گره مه تعریف میکنیم، اگر مؤلفه روی گره قرار گیرد، برابر با 1 و در غیر این صورت 0 خواهد شد. یک مؤلفه زمانی میتواند روی یک گره مه واقع شود که گره مه فعال باشد، یعنی و در نتیجه داریم
(4)
همچنین باید توجه داشت که کل منابع سختافزاری مورد نیاز مؤلفههای مستقر در گره مه فراتر از ظرفیت آن گره نباشد و بنابراین داریم
(5)
در عبارت فوق برابر با ظرفیت محاسباتی، حافظه و ذخیرهسازی گره مه و برابر با منابع محاسباتی، حافظه و ذخیرهسازی درخواستی مؤلفههای کاربرد میباشد. از آنجایی که فرض بر این است که منابع نرمافزاری در گرههای مه یک زیرشبکه مشکامل، در دسترس همه گرههای زیرمجموعه آن قرار دارد، داریم
(6)
در عبارت فوق برابر با ظرفیت منابع نرمافزاری زیرشبکه مشکامل و برابر با منابع نرمافزاری درخواستی مؤلفههای کاربرد میباشد. همچنین داریم
(7)
در عبارت فوق برابر با حسگرهای در دسترس از طریق زیرشبکه مشکامل انتخابی و برابر با منابع حسگر درخواستی مؤلفههای کاربرد میباشد. هر یک از مؤلفهها فقط روی یکی از گرههای مه اجرا میشوند، لذا داریم
(8)
4- بیان مسأله
به طور کلی، چندین عامل بر روی کل مصرف انرژی سیستم مورد مطالعه تأثیر میگذارد، مانند بارهای محاسباتی، فناوری ارتباطات، میزان ترافیک تبادلشده، فاصله بین هر جفت گره مه و غیره. برای محاسبه مصرف انرژی هر گره مه، مصرف انرژی مربوط به اجرای هر یک از مؤلفههای روی گره مه و توان مصرفی برای تبادل اطلاعات بین گرههای مه در نظر گرفته شده است. مصرف انرژی هر گره مه به طور مستقیم
به استفاده از منابع آن بستگی دارد و بنابراین میانگین استفاده از منابع نرمالشده از یک گره مه با استفاده از (9) محاسبه میشود
(9)
در معادله فوق، ضرایب و دارای مقادیر حقیقی هستند، به طوری که ، و است. از این ضرایب برای تعیین اهمیت منابع ترکیبشده در کل مصرف انرژی استفاده میشود. از
شکل 5: بلاک دیاگرام الگوریتم پیشنهادی.
آنجایی که بخش عمدهای از مصرف انرژی مربوط به واحدهای پردازشی است، در این مقاله، و در نظر گرفته شده است [16]. بنابراین مصرف انرژی مربوط به هر گره میزبان مؤلفههای مختلف با استفاده از (10) محاسبه میشود
(10)
در (10)، از پارامترهای و برای تعیین حداقل و حداکثر مصرف انرژی هر گره پردازشی به ترتیب در کمترین و بالاترین شرایط بهرهبرداری و از متغیر دودویی برای اشاره به فعال یا غیر فعال بودن گره پردازش استفاده میشود. همچنین مصرف انرژی حاصل از انتقال داده از طریق پیوندهای ارتباطی با استفاده از (11) انجام میگردد
(11)
در عبارت فوق انرژی انتقال داده در گره مه و ترافیک مؤلفههای وابسته میباشد. با توجه به رابطه فوق، انرژی انتقال زمانی
در محاسبات استفاده میشود که مؤلفههای وابسته و در دو گره متفاوت مه مستقر باشند. در نهایت انرژی مصرفی کل در یک گره مه که حاصلجمع انرژی انتقال و انرژی مصرفی منابع محاسباتی است، از رابطه زیر به دست میآید
(12)
مدل پیشنهادی بهینهسازی برای کمینهسازی مصرف انرژی شبکه مه در استقرار مؤلفهها به صورت زیر فرموله میشود
(13)
محدودیتها
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
5- الگوریتم پیشنهادی
جستجوی فاخته36 یک الگوریتم هوش ازدحامی37 است که میتوان در مسایل بهینهسازی دنیای واقعی از آن استفاده کرد. با استفاده از این الگوریتم میتوان فضای جستجوی مسأله را کاهش داد و به راه حل بهینه تقریبی در زمان کوتاهتر دست یافت. در این مقاله، ما از جستجوی فاخته برای حل مسأله استقرار مؤلفههای کاربرد استفاده میکنیم. تأثیر و کارامدی این الگوریتم در [17] نشان داده شده است. در جستجوی فاخته برای بهینهسازی از سه قانون زیر استفاده میشود:
- هر فاخته هر بار یك تخم میگذارد و آن را در لانهای که به طور تصادفی انتخاب شده است قرار میدهد.
- بهترین لانهها با کیفیت بالای تخمها (راه حلها) به نسلهای بعدی منتقل میشوند.
- تعداد لانههای میزبان موجود ثابت است و یک میزبان میتواند تخم بیگانهای را با احتمال کشف کند. در این حالت، پرنده میزبان میتواند تخم را دور بیندازد یا لانه را رها کند تا لانهای کاملاً جدید در مکان جدید ایجاد کند.
از نظر ریاضی، اولین قانون برای تولید یک راه حل جدید میتواند به طور تصادفی یا از طریق گام تصادفی38 یا پرواز لوی39 انجام شود. همزمان، یک جایگشت تصادفی محلی مانند تقاطع40 روی راه حلها انجام میشود. قانون دوم مبتنی بر نخبهگرایی41 است تا بهترین راه حلها به نسل بعدی منتقل شود و انتخاب اینچنین بهترینها به اطمینان از همگرایی مناسب الگوریتم کمک میکند. قاعده سوم را میتوان جهش42 (عملگر برداری از طریق ترکیب پرواز لوی و کیفیت تفاضل راه حلها) در نظر گرفت تا بدترین راه حلها با یك احتمال حذف و راه حلهای جدیدی با توجه به شباهت راه حلها با راه حل دیگر تولید شود. شکل 5 بلاک دیاگرام الگوریتم پیشنهادی را نشان میدهد. این الگوریتم، دادههای مسئله استقرار
شکل 6: مثالی از الگوی کدگذاری مؤلفههای کاربرد.
Algorithm 1. The Proposed CSA | |
| Input Parameters: Parameters for Application And Fog network: componentsDataset, Fog Network Dataset, Fog nodes and component delay and bandwidth matrix; |
| Parameters for CS; PopSize: number of solution in Population, MaxIteration, Pa: Discovery Rate; N : Number of Fog Nodes; M: Number of Components |
| Output: Optimal Solution |
1: | i = 1; |
2: | Fog_DS = Initial Fog Data Structure using Datasets; |
3: | Full_Meshs = call Algorithm2 for Exploit FullMeshs; |
4: | Candidate_Full_Meshes = call Algorithm3 for Find desired Full Meshs; |
5: | Solutionsi = initial Random Population (PopSize, componentsDataset, Candidate_Full_Meshes); |
6: | Update Fog_DS using Solutionsi information; |
7: | call Algorithm4 for Repair infeasible Solutions in Solutionsi; |
8: | call Algorithm7 for Calculate Solutions cost in Solutionsi; |
9: | Sorting Solutions in Solutionsi Based upon Costs; |
10: | While i ≤ Max Iteration do |
11: | Fog_DS = Initial Fog Data Structure using Datasets; |
12: | Solutionsnew = call Algorithm5; |
13: | call Algorithm4 for Repair infeasible Solutions in Solutionsnew; |
14: | call Algorithm7 for Calculate Solutions cost in Solutionsnew; |
15: | Sorting Solutions in Solutionsnew Based upon Costs; |
16: | call Algorithm6 for discovery worse Solutions in Solutionsnew with probability Pa; |
17: | call Algorithm7 for Update Solutions cost in Solutionsnew; |
18: | Update Fog_DS using Solutionsnew information; |
19: | Solutionstemp = merge Solutionsnew and Solutionsi; |
20: | Sorting Solutionstemp Based upon Costs; |
21: | Solutionsi+1 = first Population Size in Solutionstemp |
22: | i = i+1; |
23: | End While |
| Return Optimal Solution; |
شکل 7: الگوریتم جستجوی فاخته سفارشیشده.
مؤلفههای کاربرد شامل اطلاعات منابع درخواستی مؤلفههای کاربرد، ارتباطات مؤلفهها، پیکربندی زیرساخت شبکه مه، تعداد اعضای جمعیت و حداکثر تعداد تکرار را به عنوان پارامترهای ورودی دریافت میکند و سپس یک طرح استقرار بهینه را به عنوان خروجی ارائه میدهد.
در ادامه این بخش الگوی کدگذاری، جستجوی فاخته سفارشیشده، پیشپردازش، عملگرها و تابع شایستگی43 تشریح میگردد.
5-1 الگوی کدگذاری
یکی از مهمترین مؤلفههای الگوریتم فاخته لانه میباشد و کدگذاری لانه روی کارایی الگوریتم تأثیر میگذارد. الگوهای کدگذاری متفاوتی برای مسألههای مختلف استفاده شده است. هر لانه یک راه حل ممکن برای مسأله ما در استقرار مؤلفههای کاربرد در گرههای مه میباشد. یک لانه شامل تخم فاخته است که هر کدام بیانگر یک مؤلفه کاربرد
Algorithm 2. Fullmesh Subnetworks Exploitation | |
| Input Parameters: Fog Network Communication Matrix (i×j) As Fog_Net, where i and j = 1,...,n and n is number of fog nodes |
| Output: Full_Meshs is vertical array of fullmesh subnetworks |
| Initialization: define Full_Meshs = {}; define Fog_Net = upper triangular (Fog_Net); |
1: | While the termination criteria not met do |
2: | If Full_Meshs is empty then |
3: | k = 0; |
4: | For Each Fognodei in Fog_Net do |
5: | For Each Fognodej = Fognodei+1 in Fog_Net do |
6: | If Fognodej connected to Fognodei in Fog_Net then |
7: | k = k+1; |
8: | Full_Meshs [row k] = [Fognodei, Fognodej]; |
9: | End If |
10: | End For Each |
11: | End For Each |
12: | Else |
13: | For Each Fognodei do |
14: | For Each k = all row of Full_Meshs do |
15: | Current_row = Full_Meshs [row k]; |
16: | If Fognodei Not in Current_row and Fognodei connected to all node in Current_row in Fog_Net then |
17: | Full_Meshs [row k] = [Full_Meshs [row k], Fognodei]; |
18: | End If |
19: | End For Each |
20: | End For Each |
21: | End If |
22: | remove duplicate rows in Full_Meshs; |
23: | End While |
| Return Full_Meshs |
شکل 8: الگوریتم استخراج زیرشبکههای مشکامل.
هستند. مقدار تخصیص داده شده به هر تخم، یک عدد صحیح بین 1 و میباشد که گره مه محل استقرار مؤلفهها را نشان میدهد. شکل 6 مثالی از الگوی کدگذاری مؤلفههای کاربرد در گرههای مه و زیستگاه مربوط را نشان میدهد.
5-2 الگوریتم جستجوی فاخته سفارشیشده
شبهکد کلی الگوریتم جستجوی فاخته برای حل مسأله استقرار مؤلفهها در زیرشبکه مه در شکل 7 ارائه شده است.
الگوریتم 1 در شکل 7 مشخصات مسأله را به عنوان ورودی دریافت کرده و راه حل بهینه را بر طبق تابع هدف مسأله ارائه میدهد. این الگوریتم با تعداد اجرای خاتمه مییابد. قبل از اجرای حلقه اصلی برنامه که بین خطوط 10 تا 23 میباشد، مراحل پیشپردازش انجام میشود. الگوریتمهای 2 و 3 در شکلهای 8 و 9 که در بخش 5-3 بیان شده است، برای استخراج زیرشبکههای مشکامل اجرا میشوند. سپس در حلقه اصلی، دو بخش اجرا میگردد. راه حلهای جدید در الگوریتم 5 بر اساس توزیع پرواز لِوی انجام میشود. الگوریتم 4 در شکل 10 راه حلهای غیر ممکن را اصلاح میکند. سپس برای به روز رسانی درصد از راه حلهای کمارزشتر بر مبنای تابع هدف، الگوریتم 6 در شکل 13 فراخوانی میشود. برای انجام این کار، ما درصد را بر اساس بدترین رتبه راه حلها انتخاب میکنیم. سپس الگوریتم 6 در شکل 13 آنها را با اجرای رویه گام تصادفی به روز رسانی میکند. مقادیر شایستگی با استفاده از الگوریتم 7 در شکل 14 برای به روز رسانی راه حلها محاسبه میگردد. بعد از اجرای آخرین دور حلقه تکرار، راه حل بهینه برگردانده میشود.
Algorithm 3. Find Candidate Fullmesh Subnetworks | |
| Input Parameters: define fn = (1,...,n) is fog node list; define Appcmp = (1,...,m) is Application components list; define FN_BW = array (n×n) is bandwidth between fog nodes; define FN_Latency = array (n×n) is Latency between fog nodes; define Appcmp_BW = array (m×m) is bandwidth between components; define Appcmp_Latency = array (m×m) is Latency between components; define AppcmpDataset is Application components resource requirements; define FNDataset is Fog nodes resources; define Full_Meshs is Full Meshs list (Algorithm2 output); |
| Output: Candidate_Full_Meshs |
1: | For each Full_Meshs as rowi do |
2: | Latency_BW_status = Check_Latency_BW (Appcmp_Latency, Appcmp_BW, rowi, FNDataset, FN_BW, FN_Latency); //constrain 15 |
3: | HR_status = HR_chk (AppcmpDataset, FNDataset, rowi); //constrain 16 |
4: | SR_status = SR_chk (AppcmpDataset, FNDataset, rowi); //constrain 17 |
5: | S_status = S_chk (AppcmpDataset, FNDataset, rowi); //constrain 18 |
6: | If Latency_BW_status & HR_status & SR_status & S_status are true then |
7: | Candidate_Full_Meshs = [Candidate_Full_Meshs; rowi]; |
8: | End if |
9: | End For |
| Return Candidate_Full_Meshs; |
شکل 9: الگوریتم استخراج زیرشبکههای مشکامل کاندیدا.
Algorithm 4. Repair Infeasible Solutions | |
| Input Parameters: define Fog_Data_Structure is Fog nodes status in each solution; define Full_Mesh is Candidate Nodes taken from Algorithm 3; define Appcmp = (1,...,m) is Application component list; define AppcmpDataset is Application component Specification; define Solutions is all solution in a population; |
| Output: Feasible Solutions and Fog_Data_Structure |
1: | For Each Solutions As solution do |
2: | For Each Fog node in solution as sourceFN do |
3: | If sourceFN Resource overload is true then |
4: | violation = true; |
5: | While violation is true do |
6: | find Appcmp with minimum dependency to other component on sourceFN and migrate it to other fog node in Full_Mesh with enough resource. Candidate Appcmp has maximum dependency to components on destination Fog node; |
7: | Update solution; |
8: | Update Fog_Data_Structure; |
9: | If sourceFN resource overload is false then |
10: | violation = false; |
11: | End If |
12: | End While |
13: | End If |
14: | End For Each |
15: | End For Each |
| Return Solutions and Fog_Data_Structure; |
شکل 10: الگوریتم ترمیم راه حلهای غیر ممکن.
5-3 پیشپردازش
در مرحله پیشپردازش با استفاده از الگوریتم 2 در شکل 8 مجموعهای از زیرشبکههای مشکامل در شبکه مه برای استقرار مؤلفهها انتخاب میشوند. استخراج این زیرشبکهها چندین مزیت دارد: مزیت اول کاهش
شکل 11: مثالی از مسیر حرکت پرواز لِوی.
Algorithm 5. Elitism | |
| Input Parameters: define Solutions is current Population of Solutions; Define best is best solution in current population; |
| Output: Solutionsnew is Next generation of population; |
1: | For Each solution in Solutions as s do |
2: | Snew = combined s and best using random walk or levy flight; |
3: | Boundary_update (Snew); |
4: | Solutionsnew = [Solutionsnew, Snew]; |
5: | End For Each |
| Return Solutionsnew; |
شکل 12: الگوریتم نخبهگرایی.
Algorithm 6. Discovery Inferior Solutions and Update | |
| Input Parameters: define Solutionsnew is new Population of Solutions; define Pa is Discovery Rate |
| Output: updated Solutionsnew; /* A solution is an interchange with a nest in cuckoo search context */ |
1: | Worse_solutons = a fraction of Solutions based upon Pa Probability; |
2: | For Each Worse_solutons in Solutionsnew as ws do |
3: | wsnew = modify ws using random walk (); |
4: | Boundary_update (wsnew); |
5: | Replace ws in Solutionsnew with wsnew |
6: | End For Each |
| Return updated Solutionsnew; |
شکل 13: الگوریتم کشف و اصلاح راه حلهای بدتر.
Algorithm 7. Fitness Function | |
| Input Parameters: define Solutions is a Population; |
| Output: Updated each solution in Solutions with solution cost |
1: | For Each solution in Solutions as solutioni do |
2: | Energy = calculate computing and network resource |
| energy consumption of all fog node in solutioni; |
3: | solutioni Cost in Solutions = Energy; |
4: | End For Each |
| Return Updated Solutions; |
شکل 14: الگوریتم تابع شایستگی.
فضای جستجو برای استخراج طرح بهینه استقرار است و مزیت دوم تأمین اشتراکی حسگرها و نرمافزارهای مورد نیاز مؤلفهها توسط زیرشبکههای مشکامل میباشد که همارز مسئله Clique در تئوری گراف است.
در الگوریتم 2 در شکل 8، در ابتدای ورود به شرط در خطوط 3 تا 11 ابتدا همه گرههایی که به هم متصل هستند استخراج شده و هر دوتایی در یک سطر از آرایه ذخیره میشود. در خطوط 13 تا 20 در حلقه هر گره مه با سطرهایی از که در آن وجود ندارد، مقایسه میشود و اگر به همه گرههای موجود در آن متصل است به لیست گره سطر جاری اضافه میشود. در خط 22 سطرهای تکراری از حذف میشوند. این روند تا پایان شرط ادامه یافته و در نهایت آرایه که شامل مجموعهای از زیرشبکههای مشکامل است، برگردانده میشود. شرط خاتمه الگوریتم 2 در شکل 8، تعداد کلیکهای مطلوب با اندازه است و به عبارت دیگر، حلقه اصلی بار تکرار میشود. از آنجایی كه دستورات مؤثر الگوریتم 2 در شکل 8 در حلقه قرار دارند، پیچیدگی
زمانی از مرتبه میباشد كه است. پس از استخراج مشهای کامل، با توجه به شرطهای (14) تا (18) در بخش 4 با استفاده از الگوریتم 3 در شکل 9، تعدادی از مشهای کامل برای استقرار مؤلفهها انتخاب میشوند.
در خط 2 از الگوریتم 3 در شکل 9 اگر منابع مورد نیاز در پهنای باند و تأخیر برای همه مؤلفههای کاربرد توسط زیرشبکه مشکامل جاری تأمین شود، برابر با میشود. همچنین در خطوط 3 تا 5 اگر منابع سختافزار، نرمافزار و حسگر توسط مشکامل جاری تأمین شود، مقادیر ، و برابر با خواهند شد. در خط 6 و 7، اگر همه منابع توسط مشکامل جاری تأمین شود، زیرشبکه مشکامل مورد نظر در لیست مشهای کامل انتخابی قرار خواهد گرفت. پیچیدگی زمانی الگوریتم 3 در شکل 9 از مرتبه است، به این دلیل که کار اصلی در حلقه بین خطهای 1 تا 9 انجام میشود.
5-4 مرحله آغازین
در تولید نسل اول الگوریتم پیشنهادی، جمعیت اولیه به طور تصادفی تولید میشود. به منظور کاهش زمان محاسبه اجرای الگوریتم فاخته، میتوان دامنه مقادیر هر تخم را بر اساس طرح کدگذاری توصیفشده در بخش 5-1 از پیش تعیین کرد. توجه داشته باشید که در تولید راه حلها ممکن است بخشی از راه حلها محدودیتهای ذکرشده را نقض کنند
و به راه حل غیر ممکن تبدیل شوند. در الگوریتم پیشنهادی برای بهرهبرداری حداکثری از جمعیت تولیدشده، راه حلهای غیر ممکن را به کمک الگوریتم 4 در شکل 10 ترمیم کرده و از آنها در یافتن راه حل بهینه نهایی استفاده میکنیم.
پیچیدگی الگوریتم 4 در شکل 10 از مرتبه است، زیرا حلقههای تودرتو مؤثرترین دستورات در این الگوریتم میباشند.
5-5 نخبهگرایی
برای تولید نسل بعدی راه حلها از مکانیزم نخبهگرایی استفاده میشود تا بهترین راه حلها به نسل بعدی منتقل شود و چنین انتخابی از بهترینها به اطمینان از همگرایی صحیح الگوریتم کمک میکند. در
خط 2 الگوریتم 5 در شکل 12، از ترکیب هر یک از راه حلها و بهترین44 راه حل از جمعیت فعلی با استفاده از پرواز لوی [17]، راه حل جدید به دست میآید. شکل 11 نمونهای از مسیر حرکت پرواز لِوی با توزیع یکنواخت را نشان میدهد.
در خط 2، الگوریتم 5 در شکل 12 با استفاده از توزیع لِوی، عدد را به عنوان شماره تصادفی یک لانه بر اساس (22) تولید میکند
(22)
که متغیر یک متغیر یکنواخت در بازه است و پارامتر با استفاده از (23) به دست میآید
(23)
در عبارت فوق پارامتر شماره نسل است [18]. بعد از آن، خط 3 راه حلهای به دست آمده را بر طبق کرانههای دامنه مسأله به روز رسانی میکند. به عبارت دیگر، در ابتدا از مفهوم پرواز لوی پیوسته جهت پیمایش فضای جستجو استفاده میشود و سپس مقادیر پیوسته محاسبهگردیده به نزدیکترین گره مه معتبر گسستهسازی میشوند. در خط 4، راه حل جدید به دست آمده به لیست راه حلهای جدید اضافه میشود و بدین ترتیب راه حلهای نسل بعدی تولید میگردد. پیچیدگی الگوریتم 5 در شکل 12 به خاطر تنها حلقه آن از مرتبه است.
5-6 کشف راه حلهای بدتر
در این فرایند، کسری از راه حلهای بدتر کشف و اصلاح میشوند که این عمل مشابه جهش نسل میباشد [17] تا [20]. در خط 1 از الگوریتم 6 در شکل 13، تعدادی از راه حلها با احتمال از جمعیت جدید استخراج میشوند. در خط 3 از حلقه با استفاده از گام تصادفی، راه حلهای استخراجشده اصلاح میشوند، در خط 4 مقادیر نامعتبر در راه حل به دست آمده، به روز رسانی میشوند و در نهایت در خط 5، راه حلهای اصلاحشده در جایگزین میگردند.
پیچیدگی زمانی الگوریتم 6 در شکل 13 است، بنابراین از مرتبه میباشد زیرا تنها یک حلقه در الگوریتم وجود دارد و همچنین است.
5-7 تابع شایستگی
به طور کلی، یکی از موضوعات مهم، نحوه ارزیابی عملکرد هر راه حل در جمعیت است. از آنجا که هر راه حل متناسب با یک طرح استقرار مؤلفه است، تابع هدف (13)، یعنی میزان مصرف انرژی در طرح استقرار مؤلفهها بر اساس اطلاعات دریافتی از راه حل با استفاده از تابع پیشنهادی در الگوریتم 7 در شکل 14 محاسبه میشود.
واضح است که پیچیدگی زمانی الگوریتم 7 در شکل 14 به دلیل استفاده از تنها حلقه تکرار از مرتبه است.
6- شبیهسازی و ارزیابی
برای بررسی کارایی الگوریتم جستجوی فاخته پیشنهادی در استخراج طرح استقرار بهینه مؤلفههای کاربرد در زیرساخت مه، یک سری آزمایشها طراحی و انجام میشود. ما از معیار ارزیابی مصرف انرژی برای ارزیابی رویکرد پیشنهادی استفاده کردیم. به طور کلی عوامل مختلفی روی مصرف انرژی گرههای مه تأثیر میگذارند. این عوامل شامل حجم محاسبات، تکنولوژی ارتباطی، میزان ترافیک تبادلی، فاصله گرهها از هم و غیره میباشد. برای محاسبه انرژی مصرفی یک گره مه، انرژی مصرفی حاصل از پردازش مؤلفههای کاربرد روی گره و همچنین انرژی مصرفی به خاطر انتقال اطلاعات بین گرههای مه در نظر گرفته میشود. ما نتایج به دست آمده از طریق الگوریتم پیشنهادی را با الگوریتمهای فراابتکاری گرگ خاکستری [21]، ژنتیک [22] و ازدحام ذرات [23] مقایسه میکنیم.
جدول 3: سناریوهای شبیهسازی.
سناریوها | 1 | 2 | 3 | 4 |
گرههای مه | 10 | 15 | 20 | 25 |
مؤلفهها | 20 | 25 | 30 | 40 |
جدول 4: منابع گرههای مه.
گرههای مه | 1 | 2 | 3 | 4 | 5 |
CPU (GHz) | 02/1 | 15/1 | 38/1 | 46/1 | 06/1 |
اندازه حافظه (GB) | 3/1 | 6/1 | 2/1 | 4/1 | 3/1 |
آستانه مصرف CPU | 98/0 | 93/0 | 96/0 | 94/0 | 92/0 |
آستانه مصرف حافظه | 00/1 | 99/0 | 91/0 | 92/0 | 98/0 |
حداقل مصرف انرژی | 94 | 82 | 99 | 81 | 91 |
حداکثر مصرف انرژی | 133 | 132 | 133 | 147 | 142 |
حسگرها | 1 | 2/1 | 2/1 | 2 | 0 |
نرمافزارها | 0 | 2/1 | 2 | 0 | 2/1 |
انرژی انتقال | 2/0 | 2/0 | 2/0 | 1/0 | 1/0 |
جدول 5: پهنای باند بین گرههای مه.
گرههای مه | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 98/0 | 80/0 | 89/0 | 97/0 |
2 | 84/0 | 1 | 82/0 | 94/0 | 92/0 |
3 | 93/0 | 94/0 | 1 | 97/0 | 0 |
4 | 88/0 | 92/0 | 91/0 | 1 | 1 |
5 | 92/0 | 99/0 | 0 | 90/0 | 1 |
جدول 6: تأخیر بین گرههای مه.
گرههای مه | 1 | 2 | 3 | 4 | 5 |
1 | 0 | 17/0 | 19/0 | 10/0 | 10/0 |
2 | 12/0 | 0 | 10/0 | 11/0 | 18/0 |
3 | 18/0 | 14/0 | 0 | 12/0 | 1 |
4 | 16/0 | 19/0 | 14/0 | 0 | 14/0 |
5 | 11/0 | 14/0 | 1 | 16/0 | 0 |
6-1 تنظیمات شبیهسازی
برای ارزیابی چارچوب پیشنهادی، 4 سناریو اجرا شد. در هر سناریو تعداد مؤلفهها و تعداد گرههای مه تغییر مییابد. جزئیات سناریوها در جدول 3 نشان داده شده است. ما همه آزمایشها را روی کامپیوتری با پردازنده اینتل با دو هسته فیزیکی، نرخ کلاک 53/2 گیگاهرتز و چهار پردازنده منطقی و 8 گیگابایت حافظه انجام دادیم.
به منظور ارزیابی قابلیت الگوریتم پیشنهادی در ارائه طرح بهینه استقرار مؤلفههای کاربرد، فرض بر این است که گرههای مه از نظر قابلیت پردازش، ظرفیت ذخیرهسازی، پهنای باند و تأخیر ناهمگن هستند. برای نمایش بهتر، نمونهای از اطلاعات مجموعه داده45 شبکه مه با 5 گره در جدول 4 تا 6 نشان داده شده است. همان طور که در جدول 4 مشاهده میشود، منابع محاسباتی، آستانه مصرف CPU و حافظه و همچنین حداقل و حداکثر مصرف انرژی، نوع حسگرها و نرمافزارهای پشتیبانیشده و انرژی انتقال برای هر گره، متفاوت در نظر گرفته شده است. مقدار 0 در
جدول 7: منابع مورد نیاز مؤلفههای کاربرد.
مؤلفهها | 1 | 2 | 3 | 4 | 5 |
CPU | 15/0 | 19/0 | 24/0 | 26/0 | 29/0 |
حافظه | 2/0 | 2/0 | 1/0 | 2/0 | 1/0 |
حسگرها | 1 | 0 | 1 | 0 | 2 |
نرمافزارها | 0 | 1 | 0 | 2/1 | 1 |
جدول 8: پهنای باند مورد نیاز مؤلفههای کاربرد.
مؤلفهها | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 0 | 0 | 0 | 0 |
2 | 0 | 1 | 33/0 | 0 | 32/0 |
3 | 0 | 0 | 1 | 31/0 | 20/0 |
4 | 0 | 0 | 0 | 1 | 39/0 |
5 | 0 | 0 | 0 | 0 | 1 |
جدول 9: تأخیر مورد نیاز مؤلفههای کاربرد.
مؤلفهها | 1 | 2 | 3 | 4 | 5 |
1 | 0 | 1 | 1 | 1 | 1 |
2 | 0 | 0 | 20/0 | 1 | 28/0 |
3 | 0 | 0 | 0 | 24/0 | 21/0 |
4 | 0 | 0 | 0 | 0 | 20/0 |
5 | 0 | 0 | 0 | 0 | 0 |
جدول 10: پارامترهای فاخته، گرگ خاکستری، ژنتیک و ازدحام ذرات.
الگوریتمها | پارامترها | اندازه جمعیت | حداکثر تکرار | |
جستجوی فاخته |
| 25/0 | 100 | 100 |
گرگ خاکستری | برگرفته از [21] | |||
ژنتیک |
| 7/0 | ||
| 4/0 | |||
ازدحام ذرات |
| 1 | ||
| 5/1 | |||
| 2 |
حسگرها و نرمافزارهای جدول 4 به معنای عدم پشتیبانی از نرمافزار و حسگرها میباشد و مقادیر 1 و 2، نوع حسگرها و نرمافزارهای قابل پشتیبانی را نشان میدهد. در جدول 5 و 6 پهنای باند و تأخیر در ارتباط مستقیم بین گرهها آمده و مقادیر این جداول، اعدادی نرمال بین 0 و 1 در نظر گرفته شده است. پهنای باند 0 به معنای عدم ارتباط بین گره و و پهنای باند 1 به معنای این است که گره همان گره میباشد. در جدول 6، تأخیر 1 بین دو گره به معنای عدم ارتباط بین دو گره و تأخیر 0 به معنای یکسانبودن دو گره است.
نمونهای از مشخصات مؤلفههای کاربرد شامل CPU، حافظه، نوع حسگر و نرمافزار مورد نیاز، همچنین ارتباطات و تأخیر بین آنها در جداول 7، 8 و 9 (مشابه جداول 4، 5 و 6) نشان داده شده است.
لازم به ذکر است با توجه به این که بنچمارکی46 در ادبیات در این حوزه تحقیق منتشر نشده است، مجموعه داده با محدوده مقادیر مشابه جداول 4 تا 9 را تولید کردیم. این مقادیر، توان پردازش و ظرفیت ذخیرهسازی گرهها مه بر اساس معماریها و سیستمهای محاسباتی گرههای مه
شکل 15: عملکرد الگوریتمها در تابع هدف TPC با افزایش تکرار.
شکل 16: نرخ بهینه مصرف انرژی در پایان شبیهسازی.
جدول 11: زمان اجرای شبیهسازی.
جستجوی فاخته | s 92/187 | ژنتیک | s 12/213 |
گرگ خاکستری | s 34/186 | ازدحام ذرات | s 93/186 |
فعلی مانند دستیارهای دیجیتال شخصی، تلفنهای هوشمند، رایانههای داخلی و غیره انتخاب شدهاند. پارامترهای الگوریتمهای جستجوی فاخته، گرگ خاکستری، ژنتیک و ازدحام ذرات در جدول 10 ارائه شده است. در این جدول، نرخ اکتشاف راه حلها در جستجوی فاخته، و نرخ تقاطع و جهش در الگوریتم ژنتیک و پارامترهای ، و به ترتیب ضرایب اینرسی، یادگیری محلی و یادگیری سراسری میباشند.
6-2 نتایج شبیهسازی
برای مقایسه عملکرد الگوریتمها از نمودارهای وضعیت تابع هدف در تکرار الگوریتمها، نرخ کمینه مصرف انرژی و همچنین زمان سپریشده استفاده گردیده است. گرهها در شبکه مه به صورت تصادفی و با توزیع نرمال پراکنده شدهاند. نقشه توزیع گرههای شبکه مه در هر سناریو شبیهسازی نمایش داده میشود و همچنین در نقشه شبکه مه گرههای میزبان مؤلفههای کاربرد با رنگ قرمز نشان داده میشوند.
سناریوی اول: شبکهای با 10 گره مه و 20 مؤلفه
با توجه به شکل 15 در مراحل اولیه اجرای شبیهسازی، راه حلهای
به دست آمده توسط الگوریتمهای گرگ خاکستری و ازدحام ذرات در رقابت با روش پیشنهادی میباشند، اما با افزایش مراحل تکرار راه حلهای به دست آمده توسط الگوریتم جستجوی فاخته بر نتایج سایر الگوریتمها غلبه میکند.
شکل 17: نقشه گرههای مه.
شکل 18: عملکرد الگوریتمها در تابع هدف TPC با افزایش تکرار.
در پایان شبیهسازی، راه حل بهینه به دست آمده با توجه به تابع هدف (معادله (13)) توسط الگوریتم جستجوی فاخته و ازدحام ذرات در مقایسه با ژنتیک و گرگ خاکستری، نتایج بهتری را نشان میدهد (شکل 16).
زیرشبکه مشکامل انتخابی توسط الگوریتم پیشنهادی برای توزیع مؤلفهها شامل گرههای 3، 4، 5، 8 و 9 میباشد. در شکل 17 موقعیت این گرهها در نقشه شبکه مه نشان داده شده است. زمان اجرای شبیهسازی در جدول 11 آمده و در مقایسه با زمان اجرای سایر الگوریتمها، روش پیشنهادی از زمان سپریشده مطلوبی برخوردار است.
سناریوی دوم: شبکهای با 15 گره مه و 25 مؤلفه
در این سناریو راه حلهای به دست آمده توسط جستجوی فاخته در مراحل اولیه اجرا با توجه به (13) از مقدار مطلوبی برخوردار است و با توجه به محدودیت فضای جستجو به زیرشبکه مشکامل، تا پایان شبیهسازی تغییر زیادی در نتیجه حاصلشده رخ نمیدهد (شکل 18).
در پایان شبیهسازی، راه حل بهینه به دست آمده توسط الگوریتم
گرگ خاکستری، ازدحام ذرات و ژنتیک در تابع هدف (13) نتایج نزدیک به هم را نشان میدهد. با این حال با توجه به شکل 19، برتری روش پیشنهادی در ارائه راه حلی با تابع هدف کمینه، نسبت به سایر راه حلها مشاهده میشود.
در شکل 20 موقعیت گرههای مشکامل انتخابی در نقشه شبکه نشان داده شده است. با توجه به نقشه و فاصله توزیع گرههای مه، چندین زمان اجرای شبیهسازی در جدول 12 آمده است. در این سناریو نیز در مقایسه با زمان اجرای سایر الگوریتمها، روش پیشنهادی از زمان سپریشده مطلوبی برخوردار است.
شکل 19: نرخ بهینه مصرف انرژی در پایان شبیهسازی.
شکل 20: نقشه گرههای مه.
جدول 12: زمان اجرای شبیهسازی.
جستجوی فاخته | s 68/212 | ژنتیک | s 45/263 |
گرگ خاکستری | s 96/216 | ازدحام ذرات | s 87/213 |
جدول 13: زمان اجرای شبیهسازی.
جستجوی فاخته | s 94/269 | ژنتیک | s 51/219 |
گرگ خاکستری | s 09/277 | ازدحام ذرات | s 77/276 |
سناریوی سوم: شبکهای با 20 گره مه و 30 مؤلفه
در نمودار شکل 21 برتری الگوریتم ژنتیك نسبت به روش پیشنهادی در بخشی از مراحل تكرار مشاهده میشود اما در نهایت، روش پیشنهادی در مقایسه با ژنتیك و سایر الگوریتمها، هدف ما را در (13) تأمین میكند.
در پایان شبیهسازی، راه حل بهینه به دست آمده با توجه به تابع هدف (13) توسط الگوریتم جستجوی فاخته پیشنهادی و ژنتیك در مقایسه با ازدحام ذرات و گرگ خاکستری، نتایج بهتری را نشان میدهد (شکل 22).
با افزایش تعداد گرهها در مه، تعداد مشهای كامل قابل استخراج برای توزیع مؤلفهها افزایش مییابد، اما با توجه به ماهیت ناهمگن گرهها و مؤلفههای كاربرد، مشهای كامل كاندیدا برای توزیع مؤلفهها محدود میباشد. زیرشبکه مشکامل انتخابی توسط الگوریتم پیشنهادی
برای توزیع مؤلفهها شامل گرههای 4، 6، 13، 14، 17 و 19 میباشد. در شکل 23 موقعیت گرههای مشکامل انتخابی در نقشه شبکه نشان داده
شکل 21: عملکرد الگوریتمها در تابع هدف TPC با افزایش تکرار.
شکل 22: نرخ بهینه مصرف انرژی در پایان شبیهسازی.
جدول 14: زمان اجرای شبیهسازی.
جستجوی فاخته | s 65/369 | ژنتیک | s 13/457 |
گرگ خاکستری | s 50/418 | ازدحام ذرات | s 54/392 |
شده است. زمان اجرای شبیهسازی در جدول 13 آمده و در مقایسه با زمان اجرای سایر الگوریتمها، روش پیشنهادی از زمان سپریشده مطلوبی برخوردار است.
سناریوی چهارم: شبکهای با 25 گره مه و 40 مؤلفه
در شکل 24 رقابت نزدیك الگوریتمها در استخراج راه حلهایی با مقدار كمینه در تابع هدف مشاهده میشود، اما در نهایت در
مراحل پایانی، تكرار روش پیشنهادی بر سایر الگوریتمها با اختلاف كم غلبه میكند.
راه حل بهینه به دست آمده با توجه به تابع هدف (13)، اختلاف پایین روش پیشنهادی و الگوریتمهای ازدحام ذرات و گرگ خاكستری را در پایان شبیهسازی نشان میدهد (شکل 25).
زیرشبکه مشکامل انتخابی توسط الگوریتم پیشنهادی برای توزیع مؤلفهها شامل گرههای 2، 4، 9، 10، 11، 13، 14، 17، 20 و 22 میباشد. در شکل 26 موقعیت گرههای مشکامل انتخابی در نقشه شبکه نشان داده شده است.
زمان اجرای شبیهسازی در جدول 14 نشان داده شده که در مقایسه با زمان اجرای سایر روشها، الگوریتم پیشنهادی از زمان سپریشده مطلوبی برخوردار است.
شکل 23: نقشه گرههای مه.
شکل 24: عملکرد الگوریتمها در تابع هدف TPC با افزایش تکرار.
جدول 14: زمان اجرای شبیهسازی.
جستجوی فاخته | s 65/369 | ژنتیک | s 13/457 |
گرگ خاکستری | s 50/418 | ازدحام ذرات | s 54/392 |
در آخر، روش پیشنهادی در میانگین مقادیر بهینه به دست آمده برای تابع هدف (13) یعنی ، در کل سناریوهای شبیهسازی شده 23% بهتر از گرگ خاکستری، 28% بهتر از ژنتیک و 18% بهتر از ازدحام ذرات عملکرد داشته است.
6-3 پیچیدگی زمانی
با محاسبه پیچیدگی زمانی همه الگوریتمهای فرعی، اکنون پیچیدگی زمان الگوریتم 1 به راحتی قابل محاسبه است. مرحله پیشپردازش به میزان طول میکشد که از مرتبه است. همچنین حلقه اصلی بار تکرار میشود. برای حلقه اصلی، زمان اجرا داریم. اگر را کوچکتر از در نظر بگیریم، پیچیدگی زمانی الگوریتم 1 از مرتبه است که نسبتاً قابل قبول میباشد.
7- نتیجهگیری و کار آینده
در این مقاله، ما بر روی مسئله استقرار مطمئن مؤلفههای کاربرد در محیط مه و ابر تمرکز کردیم. برای حل مسأله استقرار در محاسبات مه، یک مدل ارائه دادیم و از معیار ارزیابی مصرف انرژی در این مطالعه استفاده نمودیم.
شکل 25: نرخ بهینه مصرف انرژی در پایان شبیهسازی.
شکل 26: نقشه گرههای مه.
برای رفع چالش استقرار مؤلفههای کاربرد، یک الگوریتم فراابتکاری سفارشی مبتنی بر فاخته ارائه دادهایم. مجموعهای از آزمونهای شبیهسازی را انجام داده و نتایج به دست آمده را با گرگ خاکستری، ژنتیک و ازدحام ذرات مقایسه کردیم. با بررسی کلی آزمایشها مشخص شد که روش پیشنهادی بر سایر الگوریتمها برتری دارد، زیرا در تمام آزمایشها، راه حلهای به دست آمده توسط الگوریتم پیشنهادی از نظر مصرف انرژی بر راه حل سایر الگوریتمها غلبه میکند.
در آینده، ما رویکرد استقرار پویای مؤلفههای کاربرد را بررسی خواهیم کرد. علاوه بر این در استقرار کاربردهای کاربر، پهنای باند مصرفی، تأخیر کلی کاربرد و هزینه پرداختی برای تأمین منابع مه و نوع کاربرد کاربر نیز در نظر گرفته خواهد شد.
مراجع
[1] OpenFog Consortium Architecture Working Group, An OpenFog Architecture Overview, Available: https://www.iiconsortium.org/pdf/OpenFog_Reference_Architecture_2_09_17.pdf, 2017.
[2] S. Azimi, C. Pahl, and M. Hosseini Shirvani, "Particle swarm optimization for performance management in multi-cluster IoT edge architectures," in Proc. 10th Int. Conf. on .Cloud Computing and Services Science, pp. 328-337, Prague, Czech Republic, 7-9 May 2020.
[3] M. Hosseini Shirvani, "A hybrid meta-heuristic algorithm for scientific workflow scheduling in heterogeneous distributed computing systems," Engineering Applications of Artificial Intelligence, vol. 90, Article ID: 103501, Apr. 2019.
[4] H. Hong, P. Tsai, and C. Hsu, "Dynamic module deployment in a fog computing platform," in Proc 18th Asia-Pacific Network Operations and Management Symp., 6 pp., Kanazawa, Japan, 5-7 Oct. 2016.
[5] M. Taneja and A. Davy, "Resource-aware placement of IoT application modules in fog-cloud computing paradigm," in Proc IFIP/IEEE Symp. on Integrated Network and Service Management, pp. 1222-1228, Lisbon, Portugal, 8-12 May 2017.
[6] S. Venticinque and A. Amato, "A methodology for deployment of IoT application in fog," J. of Ambient Intelligence and Humanized Computing, vol. 10, no. 2, pp. 1955-1976, May 2019.
[7] A. Brogi and A. Forti, "QoS-aware deployment of IoT applications through the fog," IEEE Internet of Things J., vol. 4, no. 5, pp. 1185-1192, Oct. 2017.
[8] R. Mahmud, K. Ramamohanarao, and R. Buyya, "Latency-aware application module management for fog computing environments," ACM Trans. on Internet Technology, vol. 19, no. 1, Article No.: 9, pp. 1-21, Feb. 2018.
[9] M. Vogler, J. M. Schleicher, C. Inzinger, and S. Dustdar, "DIANE-dynamic IoT application deployment," in Proc IEEE Int. Conf. on Mobile Services, pp. 298-305, New York, NY, USA, 27 Jun.-2 Jul. 2015.
[10] E. Saurez, K. Hong, D. Lillethun, U. Ramachandran, and B. Ottenwalder, "Incremental deployment and migration of geo-distributed situation awareness applications in the fog," in Proc 10th ACM Int. Conf. on Distributed and Event-based Systems, pp. 258-269, Irvine, CA, USA, 20-24 Jun. 2016.
[11] U. Arora and N. Singh, "IoT application modules placement in heterogeneous fog-cloud," International J. of Information Technology, vol. 13, no. 9, pp. 1975-1982, May 2021.
[12] S. Omer, S. Azizi, M. Shojafar, and R. Tafazolli, "A priority, power and traffic-aware virtual machine placement of IoT applications in cloud data centers," J. of Systems Architecture, vol. 15, Article ID: 101996, May 2021.
[13] I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: a survey," Computer Networks, vol. 47, no. 4, pp. 445-487, 15 Mar. 2005.
[14] J. P. Arcangeli, R. Boujbel, and S. Leriche, "Automatic deployment of distributed software systems: definitions and state of the art," The J. of Systems and Software, vol. 3pp. 198-218, May 2015.
[15] F. Bonomi, R. Milito, P. Natarajan, and J. Zhu, "Fog computing: a platform for Internet of Things and analytics," In: N. Bessis and C. Dobre (eds), Big Data and Internet of Things: A Roadmap for Smart Environments. Studies in Computational Intelligence, vol 546. Springer, Cham, pp. 169-186, 2014.
[16] S. Farzai, M. Hosseini Shirvani, and M. Rabbani, "Multi-objective communication-aware optimization for virtual machine placement
in cloud datacenters," Sustainable Computing: Informatics and Systems, vol. 28, Article ID: 100374, Dec. 2020.
[17] X. S. Yang and S. Deb, "Cuckoo search via Le´vy flights," in Proc. of World Congress on Nature & Biologically Inspired Computing, pp. 210-214, Coimbatore, India, 9-11 Dec. 2009.
[18] S. M. Sait, A. Bala, and A. H. El-Maleh, "Cuckoo search based resource optimization of datacenters," Applied Intelligence, vol. 44, no. 3, pp. 489-506, Apr. 2016.
[19] M. Tavana, S. Shahdi-Pashaki, E. Teymourian, F. J. Santos-Arteaga, and M. Komaki, "A discrete cuckoo optimization algorithm for consolidation in cloud computing," Computers & Industrial Engineering, vol. 115, pp. 495-511, Jan. 2017.
[20] M. Hosseini Shirvani and S. Farzai, "Optimal deployment of IoT application components on hybrid fog2cloud infrastructure for reduction of power consumption toward green computing by cuckoo search algorithm," in Proc.of the 1st National Conf. of New Development in Green Studies, Computations, Applications, and Challenges, 10 pp. Noor, Iran, 10-11 Sept.. 2020.
[21] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Advances in Engineering Software, vol. 69?, pp. 46-61, Mar. 2014.
[22] C. G. Martínez, F. J. Rodriguez, and M. Lozano, "Genetic Algorithms," in Handbook of Heuristics, Springer, pp. 431-464, 2018.
[23] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proc. of the IEEE Int. Conf. on Neural Networks, pp. 1942-1948, Perth, Australia, 27 Nov.-1 Dec. 1995.
یاسر رمضانپور در سال 1383 مدرک کارشناسی مهندسی کامپیوتر گرایش نرمافزار خود را از دانشگاه آزاد اسلامی واحد ساری و در سال 1387 مدرک کارشناسی ارشد مهندسی فناوری اطلاعات گرایش شبکههای کامپیوتری خود را از دانشگاه آزاد اسلامی واحد قزوین دریافت نمود. پس از آن در سال 1394 به دوره دکترای مهندسی کامپیوتر سیستمهای نرمافزاری در دانشگاه آزاد اسلامی واحد بابل وارد گردید و در سال 1400 موفق به اخذ درجه دکترا در مهندسی کامپیوتر از دانشگاه مذکور گردید. ایشان از سال 1389 عضو هیأت علمی دانشکده فنی و مهندسی دانشگاه آزاد اسلامی واحد قائمشهر میباشد. زمينههاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند رایانش ابری، اینترنت اشیاء، مديريت شبكههاي كامپيوتری، امنیت شبکه و مهندسی نرمافزار ميباشد.
میرسعید حسینی شیروانی تحصيلات خود را در مقاطع كارشناسي (مهندسی کامپیوتر گرایش نرمافزار)، كارشناسي ارشد (مهندسی کامپیوتر گرایش نرمافزار) و دکتری (مهندسی کامپیوتر با گرایش سیستمهای نرم افزاری) بهترتيب در سالهاي 1379، 1383 و 1396 از دانشگاههای تهران به پايان رسانده است و هماكنون استادیار دانشكده مهندسي كامپيوتر دانشگاه آزاد اسلامی واحد ساری ميباشد. نامبرده به عنوان عضو هيأت علمی تمام وقت در دانشگاه آزاد واحد ساری مشغول به فعالیت های آموزشی و پژوهشی میباشد. در ضمن، ایشان دارای سابقهی تدریس در سایر موسسات دولتی و آزاد نظیر دانشگاه صنعتی نوشیروانی بابل، دانشگاه مازندران بابلسر،دانشگاههای آزاد واحدهای بابل، آمل و قائمشهر میباشند. زمينههاي تحقيقاتي مورد علاقه ايشان عبارتند از: رایانش ابری، رایانش مه، اینترنت اشیاء، شبکههای حسگر بیسیم، سیستمهای توزیع شده، الگوريتمهاي موازي، محاسبات نرم هوش مصنوعی و یادگیری ماشین.
[1] این مقاله در تاریخ 29 آبان ماه 1399 دریافت و در تاریخ 13 مهر ماه 1400 بازنگری شد.
یاسر رمضانپور فومشی، دانشكده مهندسی كامپیوتر، واحد بابل، دانشگاه آزاد اسلامی، بابل، ایران، (email: yaser.ramzanpoor@gmail.com).
میرسعید حسینی شیروانی (نویسنده مسئول)، دانشكده مهندسی كامپیوتر،
واحد ساری، دانشگاه آزاد اسلامی، ساری، ایران،
(email: mirsaeid_hosseini@iausari.ac.ir).
[2] . Fog Computing
[3] . Cloud
[4] . Application
[5] . Internet of Things
[6] . Deployment
[7] . Heterogeneous
[8] . Computing Resource
[9] . Workload
[10] . Component
[11] . Single Point of Failure
[12] . Reliability
[13] . NP-Hard
[14] . Platform
[15] . QoS-Aware
[16] . Energy Efficient
[17] . Full Mesh
[18] . Heuristic Algorithm
[19] . Meta-Heuristic Algorithm
[20] . Docker
[21] . Container
[22] . Network-Aware
[23] . End to End Delay
[24] . Distributed
[25] . Latency-Aware
[26] . Edge Device
[27] . Foglet
[28] . Application Programming Interface
[29] . Migration
[30] . Traffic Aware
[31] . Framework
[32] . Organizer
[33] . Deployment Planner
[34] . Module
[35] . Communication Link
[36] . Cuckoo Search
[37] . Swarm Intelligence
[38] . Random Walk
[39] . Levy Flight
[40] . Crossover
[41] . Elitism
[42] . Mutation
[43] . Fitness Function
[44] . Best
[45] . Data Set
[46] . Benchmark