بخشی از مقاله
چکیده
رایانش ابری یک محیط پردازشی توزیعشده بر روی بستر اینترنت، باقابلیت ارائه سرویسهای متنوع است. رایانش ابری سعی در ایجاد یک بستر محاسباتی قوی بر اساس ارائه کیفیت خدمات سرویس بین مشتری و فراهمکنندگان ابر مینماید. در این راستا هزینههای سربار مختلف مثل هزینه سیستمهای پردازشی متنوع و هزینه خرید حافظههای زیاد را کاهش میدهد. بعلاوه میزان بهرهوری مانند استفاده از منابع محاسباتی در دسترس افزایش میدهد. یکی از مسائل رایج در رایانش ابری زمانبندی وظایف برای تخصیص منابع محاسباتی به درخواستها است. وظیفه زمانبند این است که الگوریتمی ارائه دهد که در کمترین زمان به درخواستها پاسخ داده شود.
تحقیقات بسیاری در این حوزه صورت گرفته است و الگوریتمهای متنوعی بهمنظور بهبود در هزینه پاسخدهی به درخواستها بهکارگرفته شده است. ازجملهی این الگوریتمها میتوان به الگوریتمهای کلونی مورچه و ازدحام ذرات اشاره کرد. الگوریتم کلونی مورچه دیر همگرا میشود اماقطعاً به جواب میرسد. الگوریتم ازدحام ذرات بهصورت تصادفی مسیر رسیدن به پاسخ را انتخاب میکند درحالیکه ممکن است به جواب بهینه نرسد. در این تحقیق، از مزایای الگوریتمهای ازدحام ذرات و کلونی مورچه استفادهشده است. برای ارزیابی الگوریتم پیشنهادی از شبیهساز کلودسیم استفادهشده است. نتایج ارزیابی بیانگر این است که الگوریتم ارائهشده، ازنظر زمان پاسخدهی نسبت به استفادهی یکی از الگوریتمهای کلونی مورچه یا ازدحام ذرات، بهینهتر عمل میکند.
-1 مقدمه
اگرچه پردازش ابری بیشتر مفهومی متعلق به قرن 21 است، اما مفهوم و شالودهی آن ریشه درزمانی پیش از دههی 1950 میلادی دارد. روزهایی که مشخصهی آن، اتاقهای سرور بزرگ با رایانههای فوق قوی و غولآسا بود. پیدایش مفهوم رایانش ابری به دهه 1960 میلادی بازمیگردد. در آن زمان پروفسور جان مک کارتی که یکی از بنیانگذاران هوش مصنوعی است، اظهار داشت "رایانش ابری روزی بهعنوان یک صنعت همگانی سازماندهی خواهد شد . - Sajid and Raza, 2013 - " در ادامه در سال 1966 پارک هیل داگلاس در کتابی بهعنوان " مشکل صنعت همگانی رایانه " به مواردی مانند توهم دسترسی نامحدود، ارائه امکانات بهصورت صنعت همگانی بهصورت خصوصی و دولتی و انجمنی اشاره کرد.
رایانش ابری یک روش نوین پردازش است که در آن منابع قابلگسترش و اغلب مجازی شده، بهصورت یک سرویس پردازشی و از طریق شبکههای ارتباطی مانند شبکههای محلی و اینترنت عرضه میشوند .Jadeja el at,2012 - - این سرویس را میتوان به شبکه برقرسانی تشبیه کرد که مشترک بدون نیاز به داشتن اطلاع از نحوهی تولید برق و مکان دقیق تولید آن، تنها بااتصال از طریق یک درگاه، انرژی لازم برای استفاده از وسایل الکتریکی خود را تأمین میکند. یکی از مهمترین مسائل در رایانش ابری، رسیدگی به درخواست کاربران، بهطوریکه آنها از خدمات دهندگان راضی باشند، است.
این وظیفه در رایانش ابری بر عهده زمانبند وظایف است - Choubey el .at,2011 - در این مقاله، با استفاده از دو الگوریتم کلونی مورچه و ازدحام ذرات، یک روش ترکیبی بهمنظور کاهش زمان تکمیل وظایف ارائه گردیده است. این امر باعث افزایش بهرهوری سیستم و استفاده از منابع میشود. در بخش دوم کارهای مرتبط، در بخش سوم زمانبند وظایف در رایانش ابری و دو الگوریتم مورداستفادهی این تحقیق، در رایانش ابری بررسیشده است. در بخش چهارم شرح روش پیشنهادی ارائه دادهشده است. بخش پنجم ارزیابی روش پیشنهادی ارائه دادهشده است و در آخر در بخش ششم نتیجهی کلی بیانشده است.
-2 کارهای مرتبط
تاکنون مطالعات فراوانی درزمینهی زمانبندی انجامشده است که نشان میدهد تسریع در پاسخدهی به درخواستهای کاربر و تخصیص منابع از مهمترین فعالیتها در رایانش ابری است. الگوریتمهای زمانبندی به دو دسته تقسیم میشوند که در ادامه به توضیح آنها می-پردازیم. بعلاوه تعدادی از الگوریتم مانند الگوریتم ژنتیک، Min_Min، ازدحام ذرات و کلونی مورچه که تاکنون مورد استفاده در رایانش ابری قرارگرفتهاند را تعریف میکنیم.
-2-1 انواع الگوریتمهای زمانبندی
الگوریتمهای زمانبندی به دو دستهی ایستا و پویا تقسیم میشوند - Thakur el at,2017 - که در ادامه به توضیح آن پرداخته شده است.
-2-1-1 الگوریتم ایستا
الگوریتمهای ایستا برای محیطهای پایدار و همگن مناسب هستند و منجر به نتایج خوبی در این محیطها میشوند. بااینحال انعطافپذیر نیستند و قادر به سازش با تغییرات پویا به دلیل برخی از ویژگیها نمیباشند. یک نمونه از الگوریتمهای ایستا الگوریتم Min_Min است. هدف این الگوریتم کاهش زمان تکمیل وظایف در جهت متعادلسازی بار با اختصاص زودهنگام وظایف کوچک به منابع با توان حداقل است.
-2-1-2 الگوریتم پویا
الگوریتمهای پویا انعطافپذیر هستند و انواع مختلف ویژگیها در سیستم را، قبل و طی زمان اجرا در نظر میگیرند. این الگوریتمها قادر به سازش در برابر تغییرات بوده و نتایج بهتری را در محیطهای پویا و ناهمگن ارائه میکنند. بااینحال ویژگیهای توزیع، پیچیدهتر و پویاتر هستند، درنتیجه برخی از این الگوریتمها ناکارآمد هستند و موجب افزایش سربار خواهند شد. در ادامه به تاریخچهی الگوریتمهای پویای ژنتیک، کلونی مورچه و ازدحام میپردازیم.
جان هلند در سال 1975 میلادی الگوریتم ژنتیک را بر اساس رفتار طبیعی ذرات تعریف کرد . - D Beasley et al ,1993 - این الگوریتم را در هر مرحله میتوان متوقف کرد و همچنین میتوان بهصورت موازی اجرا کرد. این الگوریتم دارای معایبی نیز هست، ازجمله اینکه الگوریتم ژنتیک، یک جواب خوب پیدا میکند ولی ممکن است جواب بهینه را پیدا نکند، پشتوانه ریاضی ضعیفی دارد و در دو بار اجرای مختلف، جوابهای متفاوتی دریافت میکنیم.
دکتر جیمز کندی و دکتر ایبرهارت مفهوم جدید بهینهسازی ازدحام ذرات را معرفی کردند . - J.Kennedy and R Eberhart,1995 - ازدحام ذرات از دسته الگوریتمهای بهینهسازی است که بر مبنای تولید تصادفی جمعیت اولیه عمل میکنند. این الگوریتم با الگو گیری و شبیهسازی رفتار پرواز دستهجمعی پرندگان یا حرکت دستهجمعی ماهیها بنانهاده شده است. ازدحام ذرات از این لحاظ شبیه الگوریتم ژنتیک عمل میکند که ازدحام ذرات و ژنتیک در یک تکرار، از یک سری نقطه - جمعیت - به یک سری نقاط دیگر رفته و با استفاده از قوانین قطعی و احتمالی ارتقاء مییابند.
یکی از مزیتهای این الگوریتم همکاری ذرات با یکدیگر است و با به اشتراکگذاری اطلاعات بهسرعت همگرا میشوند اما این امکان وجود دارد که به دلیل جمعیت اولیه تصادفی، همه نقاط تحت پوشش قرار نگیرند و در بهترین نقطه همگرا نشوند. با توجه به مطالعات انجامشده، متوجه شدهایم که جمعیت اولیه در الگوریتم ازدحام ذرات بهصورت تصادفی انتخاب میشود، به این دلیل معلوم نیست که این جمعیت در کدام موقعیت قرار گیرند.
مارکو دوریگو - Marco Dorigo,1991 - در ابتدا بهینهسازی مستعمرات مورچه را در سال 1991 در پایاننامه دکترای خود ارائه داد. الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچهها است. این مطالعات نشان داده است که مورچهها حشراتی اجتماعی هستند که در کلونیها زندگی میکنند. علاوه بر این، رفتار آنها بیشتر در جهت بقاء کلونی است. یکی از مهمترین و جالبترین رفتار مورچهها، رفتار آنها برای یافتن غذا و بهویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه است.
این نوع رفتار مورچهها دارای نوعی هوشمندی تودهای است که اخیراً مورد توجه دانشمندان قرارگرفته است. با توجه به الگوریتم مورچه، سرعت جستجو در این الگوریتم در مقایسه با سایر الگوریتمهای بهینهسازی، بهبودیافته است. این الگوریتم برای مسائلی با ساختار دینامیک مناسب است - Sindhu and Mukherji,2011 - و همچنین همگرایی را تضمین میکند اما امکان دارد این همگرایی کند باشد و همچنین نیاز به حافظه بزرگ دارد، زیرا بهجای ذخیره اطلاعات نسل قبل باید اطلاعات کل کلونی را ذخیره کند.
-3 زمانبند وظایف
رایانش ابری، توزیعشده و بهطورکلی ناهمگن است. همچنین هر سازمان استراتژیهای خود را برای مدیریت منابع دارد. بنابراین چگونگی تخصیص منابع به درخواستها برای به حداقل رساندن زمان کلی پاسخدهی مورد توجه قرارگرفته است. این مسئولیت بر عهده زمانبند وظایف است .Tripathy el at, 2014 - - زمانبندی یکی از برجستهترین فعالیتهایی است که در محیط محاسبات ابری اجرا میشود که در ادامه به توضیح آن میپردازیم.
در ابر حجم عظیمی از درخواستها از سوی کاربران دریافت میشود. این وظایف در چندین صف جمعآوریشده و به سمت زمانبند وظایف فرستاده میشوند. زمانبند وظایف مسئول تخصیص این وظایف به ماشینهای مجازی برای اجرا است. در زمانبندی از الگوریتمهایی استفاده میشود تا بتوان با کمترین زمان و هزینه بهترین ماشین مجازی را برای هر وظیفه انتخاب کرد. وظیفه الگوریتم زمانبندی تخصیص n درخواست به m منبع، باهدف کاهش زمان پاسخ است. در این تحقیق، بهمنظور بهبود در زمانبندی رایانش ابری، از دو الگوریتم که از قبل برای زمانبندی استفادهشدهاند، بهره برده و روش جدیدی ارائه دادهمیشود. در ادامه الگوریتمهای مورد نیاز برای الگوریتم پیشنهادی را شرح میدهیم.
-3-1 الگوریتم کلونی مورچه
الگوریتم بهینهسازی کلونی مورچگان مجموعهای مناسب با استفاده از ارتباطات مورچهای برای زمانبندی کارها و در محیط ابر فراهم آورده است. در الگوریتم کلونی مورچه awfeek et al,2013 - - ، مورچهها به فاصله منبع غذا از لانه خود بیتفاوت هستند و سعی دارند کوتاهترین مسیر را پیدا کنند. بعلاوه این قابلیت رادارند که میتوانند با تولید فرومون، کوتاهترین مسیر به غذا را بیابند. همچنین مسیر غذا را توسط فرمون، پیدا میکنند.
مورچههایی که کوتاهترین مسیر را انتخاب میکنند، نسبت به آنهایی که مسیر طولانیتری را انتخاب میکنند، دنبالهی فرمون شدیدتری، ایجاد میکنند. ازآنجاکه فرمون شدیدتر، مورچهها را بهتر جذب میکند، بیشتر و بیشتر، مسیر کوتاهتر را انتخاب میکنند تا آنجاکه همهی مورچهها، کوتاهترین مسیر را یافته و از آن مسیر حرکت میکنند. درنتیجه همانطور که در شکل 1 میبینید، بهمرور مورچههای بیشتری جذب مسیر کوتاهتر میشوند.
