بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
"الگوریتم های تکاملی و زمانبندی تعادل بار درمحاسبات ابری"
چکیده
اخیرا با توجه به توسعه فناوری اطلاعات و ارتباطات بحث های مانند کاهش هزینه ،کـارایی و افـزایش سـرعت باعـث ایجـاد تحـولی روزافـزون دردنیـای اینترنت شده است . مساله مهمی بعنوان تعادل باردر شبکه ابری مطرح شده است که خود باعث بـالارفتن و افـزایش کـارایی محاسـبات ابـری و انتخـاب مناسب ترین ماشین مجازی برای انجام یک کار خاص می باشد. که تا حد زیادی کارایی را بهبود خواهد بخشـید و بصـورتی متعـادل سـرویس دهـی را انجام می دهد. الگوریتم های که تا بحال برای حل مسئله تعادل بار بکاربرده شده اند، مانند الگوریتم های تکـاملی هـوش مصـنوعی ازجملـه الگـورریتم ژنتیک، کلونی مورچگان،کلونی زنبور عسل و بسیاری دیگر همچون الگوریتم زمانبندی چرخشی (RR)،SHC ، WRR،FIFO هستند که دراین مقالـه به مقایسه بهینه ترین الگوریتم های تکاملی و زمانبندی پرداخته می شود.
واژه های کلیدی: الگوریتم های تکاملی تعادل بار، محاسبات ابری، الگوریتم های زمانبندی، کلونی زنبور عسل ، کلونی مورچگان
-1 مقدمه
اهمیت حیاتی رایانش ابری در توانایی آن برای ارائه خدمات به همه کاربران با کارایی بالا و محاسبات قابل اعتماد است. رایانش ابری یک نوع محاسبات تکاملی توزیع شده به همراه محاسبات توری و چند تکنیک دیگر است. یکی از تفاوت های اصلی بین رایانش ابری و محاسبات خوشه ای استفاده از محاسبات توزیع شده است و محاسبات توری به عنوان واحد پردازش اساسی است. در محاسبات ابری، با استفاده از تکنولوژی مجازی سازی [1]، یک میزبان فیزیکی را می توان به میزبان های متعدد مجازی تبدیل نمود و این میزبان به عنوان یک واحد محاسبات پایه استفاده گردد. تعادل بار بین همه ماشین های مجازی یکی از مهمترین مباحث در محاسبات ابری است. الگوریتم های تکاملی و زمانبندی هرکدام به نوبه خود نقش بسزایی دربهینه سازی و تعادل بار دارند. از الگوریتم های زمانبندی می توان به الگوریتم MM، LB3M و الگوریتم SHC اشاره کرد که این الگوریتم ها در واقع جز الگوریتم های اولیه تعادل بار بودند . [8 ] ما دراین مقاله می خواهیم به مقایسه کارایی آنها و به تشخیص بهینه ترین الگوریتم بپردازیم. در ابتدا مختصری از هریک از الگوریتم های هوش مصنوعی پرداخته می شود و در بخش های بعدی، الگوریتم های هوش مصنوعی که برای حل مسئله تعادل بار استفاده می شوند، تحلیل و مقایسه خواهند شد.
-2 الگوریتم های تکاملی
در این بخش به معرفی الگوریتم های هوش مصنوعی می پردازیم.
-1-2 الگوریتم کلونی زنبور عسل
الگوریتم زنبورعسل اولین بار در سال 2005 توسعه یافت. این الگوریتم برای کارهای بهینه سازی ترکیبی به کار می رود. یک جمعیت زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذائی بهره گیرد . فرآیند جستجوی غذای یک کلونی در طبیعت به وسیله زنبور های پیش آهنگ شروع می شود. زنبورهای پیش آهنگ به طور تصادفی بین گلزارها حرکت می کنند و در این پروسه سعی می کنند کوتاه ترین و بهترین راه را پیدا کنند. برای بازگشت به کندو از نور آفتاب استفاده می کنند. الگوریتم کلونی زنبورهای مصنوعی الهام گرفته از رفتار زنبورها در طبیعت می باشد. مشابه با کلونی زنبورهای طبیعی، این الگوریتم نیز از سه گروه زنبورهای کارگر، تماشاگر و پیش آهنگ تشکیل شده است. انتخاب تصادفی منابع غذایی و همچنین تبادل اطلاعات، تصمیم گیری در مورد منابع غذایی و انتخاب منابع غذایی توسط تماشاگران هریک از زنبورهای کارگر و تماشاگر ممکن است تغییراتی بر روی موقعیت منبع غذایی در حافظه خود ایجاد کنند و شایستگی آن را محاسبه بکنند.
زنبورها دو نوع حرکت که یکی به سمت جلو و دیگری بـه سمت عقب را انجام می دهند. زنبورها پس از پیـدا کـردن راه حل مسئله و یا راه حل جدید دوباره عمل »حرکت بـه سمت عقب« را انجام می دهند. این روند زمانی پایان مـی پذیرد که یک راه حل تقریباً کامل برای مسئله پیدا شـود.
از کلونی زنبورها برای مسائل ترکیبی بهینه سازی استفاده می شود که در هر مرحله به میزانی مسئله حل می شـود. در فرمول (1) هر مرحله شامل یک سری مراحـل از قبـل انتخاب شده است.
-2-2 الگوریتم کلونی مورچگان
آنچه بنیان فکری الگوریتم مورچگان بر آن بنا شده است را می توان بسادگی و در یک جمله بیان نمود: " مورچه ها در بین موانع و محدودیت های موجود در طبیعت همیشه از بین جایگشت های متفاوت برای رسیدن به غذا، بهینه ترین راه را انتخاب می کنند. مطالعات و مشاهدات روی جمعیت مورچه ها نشان داده که مورچه ها موجوداتی اجتماعی هستند. که در اجتماع زندگی می کنند و رفتار آنها بیشتر در جهت بقاء جمعیت تا در جهت بقاء جزئی از آن است . یکی از مهمترین و جالب ترین رفتار آنها یافتن غذا است که به دنبال جستجوی کوتاه ترین مسیر میان منبع غذایی و آشیانه است. این همان الگوی رفتاری است که دانشمندان کامپیوتر از آن برای توسعه الگوریتم ها در حل مسائل بهینه سازی الهام گرفته اند. مورچه ها توانایی دیدن، شنیدن و صدا را ندارند و فقط از حس بویایی استفاده می کنند. مورچه ها از خود موادی را به جا می گذارند که بوی خاصی دارد به این مواد فرمون گفته می شود که مورچه ها فرمون به جا مانده از سایر مورچه ها را حس می کنند و علاوه بر این مورچه ها شدت بوی فرمون را نیز تشخیص می دهند. در انتخاب مسیرهای موجود هر چه شدت فرمون یک مسیر بیشتر باشد احتمال انتخاب آن نیز بالاتر خواهد بود.
-3-2 الگوریتم ژنتیک
الگوریتم ژنتیـک از مجموعـه تکنیکهـای تکـاملی بـر گرفته از طبیعت که کاربرد فراوانی در مسائل بهینه سـازی دارد استفاده می کند.[2] این الگوریتم قابلیت فهم آسان و امکان اسـتفاده بـه صـورت توزیـع شـده و مـوازی را دارد. روشی موثر برای جستجوی هدایت شـده در فضـای پاسـخ بسیار بزرگ برای پیدا کردن جواب بهینه است و وجود یک جواب درآن با گذشت زمان بهبود می یابد. شرایط جمعیت در رسیدن بـه جـواب بسـیار تـأثیر گـذار اسـت. برحسـب جمعیت بالقوه عمل می کند و اصول تنازع بقا را در تولیـد تقریب های بهتر و بهتـر جـواب مسـئله بـه کـار مـی رود. الگوریتم ژنتیک روشی بهینه برای حل مسائل بهینه سازی می باشد و همچنین روشی ساده و سریع اسـت و مـیتوانـد جایگزین روش های دیگر شود. این الگوریتم میتواند مـا را به حل بهینه ای برساند که با روش های دیگر امکـان پـذیر نیست با توجه بـه پارامترهـای تصـادفی حتـی در صـورت استفاده جمعیت اولیه یکسان ممکن است جوابهـا یکسـان نباشد. تابع ارزیابی در این الگوریتم اهمیت زیادی دارد.
-1-3-2 الگوریتم ژنتیک ترکیبی
الگوریتم ژنتیک ترکیبی یک نوع الگوریتم ژنتیک بهبود شده است. الگوریتم ژنتیک و الگوریتم ژنتیک ترکیبی (MAGA) در صورت لزوم کروموزم ها را تغییر می دهند. هر کروموزم در الگوریتم ژنتیک ترکیبی یک عامل در نظر گرفته می شود. همه عوامل در محیط عامل شبکه هستند. در الگوریتم ژنتیک ترکیبی کروموزم ها می توانند یکنواخت نباشند و همچنین چهار نوع عملگر در آن تعریف شده است .[4]
در MAGA عملگرهای ژنتیک در اصل شامل :
عملگر رقابت همسایه1، عملگر متقاطع متعامد همسایه2، عملگر جهش3، و عملگر خود یادگیری.4 در میان این عملگرها، عملگر رقابت همسایه، رقابت در میان همه عوامل را متوجه می شود. عملگر متقاطع متعامد همسایه ایجاد همکاری بین همه عوامل را بر عهده دارد.
عملگر جهش و عملگر خود یادگیری رفتارهای عوامل برای بهره برداری از دانش خود را انجام می دهد. .[5]
جدول 1 تفاوت عملکرد بین الگوریتم ژنتیک سنتی و الگوریتم ژنتیک چند عامل را نشان می دهد.
جدول : 1 تفاوت عملکرد بین الگوریتمهای ژنتیک سنتی و چند عامله
این الگوریتم در ابتدا همه کروموزم ها که در واقع همان عوامل هستند را بصورت یک شبکه دو بعدی مدل سازی می کند.
-3 ابزارهای شبیه سازی
:Cloud Sim -
در ابتدا توسط دانشگاه ملبورن روانه بازار شـد. ایـن شـبیه ساز با Java طراحی شده است ویک نرم افـزار نسـخه بـاز می باشد ،که در محیط های ویندوز ،یـونیکس و لینـوکس نیز قابل اجرا و استفاده می باشـد و ایـن نـرم افـزار دارای کاربردهای مانند مدل سـازی و شـبیه سـازی مراکـز داده، مدل سازی ابرهای فدرال، نمـایش چگـونگی سـاخت یـک فضای ابری و غیره می باشد.
:Cloud Analyst -
یک ابزار مبتنی بر Cloud Sim است ،که برای مدل سازی و آنالیز کردن محیط محاسبات ابری مورد استفاده می گیرد Cloud Analyst بر خلاف سایر نرم افزارها شبیه سازی، که با زبان های برنامه نویسی مختلف کار می کنند یک ابزار شبیه سازی گرافیکی می باشد.
:Cloud Reports -
تمامی مراحل ساخت یک محیط ابری همراه با موجودیت ها و پارامترهای مربوطه به حالت گرافیکی و ویزارد انجام می گیرد. در این شبیه ساز ایجاد گزارش از هر شبیه ساز ی در قالب فایل های Html می باشد. و همچنین با ایجاد فایل هایی با پسوند Crd می توان خروجی این شبیه ساز را به نرم افزار متلب وارد کرد و در آنجا مشاهده نمایید.
-4 روش تعادل بار درهرکدام از الگوریتم ها
در این قسمت به معرفی چند الگوریتم در مساله تعادل بار می×پردازیم.
-1-4 الگوریتم ژنتیک ترکیبی
یکی از مهمترین معیارها برای داشتن یک نتیجه کارآمد در الگوریتم ژنتیک داشتن تابع برازندگی معتبر و بهینه می باشد. این تابع می تواند ما را در یافتن جواب بهینه کمک کند پس تعریف درست این تابع مهم می باشد. یک نمونه تابع بهینه سازی، که در ژنتیک ترکیبی استفاده می شود بصورت زیر است. تابع بهینه سازی با مقدار 20 در زیر نشان داده شده است.
با داشتن این تابع برازندگی و عملگرهای مناسب می توان نتیجه گرفت که الگوریتم ژنتیکی ترکیبی به مراتب بهتر از الگوریتم معمولی با توجه به 4 عملگر پیشنهادی در آن دارد. شکل 2 نتایج آزمایش را با مقایسه مقادیر تابع بهینه با ده بار اجرای متوالی الگوریتم MAGA و الگوریتم GA نشان می دهد.
شکل : 2 تفاوت کارایی
بر اساس شکل2 نتایج بهینه سازی توسط MAGA به مراتب برتر از GA سنتی است. در این بخش آزمایش برای 20 ماشین مجازی ناهمگن و برای 10 میزبان در نظر گرفته شده است. تعداد گروه های کاربر 100 با فاکتور وزن w=0 5 و v=0 5 است. که این فاکتور به ترتیب نشان دهنده استفاده از حافظه اصلی و پردازنده می باشد.
شکل : 3 شبیه سازی نتایج CPU با استفاده از الگوریتم Min_Min
شکل : 4 شبیه سازی نتایج CPU با استفاده از الگوریتم MAGA
شکل : 5 شبیه سازی نتایج حافظه با استفاده از الگوریتم Min_Min
شکل : 6 شبیه سازی نتایج حافظه با استفاده از الگوریتم MAGA
هنگامی که W = 0 5، V = 0 5، الگوریتم ژنتیک ترکیبی یا MAGA یک مزیت قابل توجهی نسبت الگوریتم زمانبندی Min_min در حفظ تعادل بار استفاده از CPU دارد اما در تعادل بار و استفاده از RAM این چنین نیست. تنظیم پارامترهای زمان بندی، نتایج نشان داد که استفاده از تعادل بار پردازنده و حافظه برای الگوریتم ژنتیک MAGA بسیار بهتر از Min_min است و تاثیر کامل تعادل بار را می توان با تنظیم فاکتور وزن به دست آورد. علاوه بر این، الگوریتم زمان بندی MAGA می تواند در میزان شکست تک نقطه ای کوچکتر شود. این نشان می دهد که این روش برای حل استراتژی تعادل بار مبتنی بر محاسبات ابری مجازی، امکان پذیر و موثر است.
-2-4 الگوریتم کلونی زنبورعسل
وظایف محاسباتی در استخر منابع پویا قرار داده می شوند. که ماشین های مجازی آنلاین با توجه به شرایط مختلف از کاربر و یا سیستم به محاسبات ابری می پردازد. سرویس درخواستی کاربران برای کاربردهای گوناگون را می توان در هر مرکز داده ها با هر سرور در ابر انجام داد. مسیریابی درخواست سرویس به سرورهای گوناگون بر اساس سیاست های مدیریت ابر و با توجه به بار از سرورهای انفرادی، تراکم پایگاه داده ها و غیره انجام می شود. در یک سیستم غیر پیشگیرانه اغلب ازسیاست های دو اصل زمانبندی (FIFO) و (WRR) استفاده می شود. در نهایت با درجات مختلف از بارها بر روی هر ماشین مجازی این سیاست انجام می شود.که این ممکن است منجر به اختلاف بین ماشین های مجازی در محاسبات بار به صورت موازی شود. به همین ترتیب این باعث بوجود آمدن مشکلات اضافی از قبیل کاهش زمان پاسخ، کاهش منابع خواهد شد. این نوع شرایط موجب می شود که ما به تکنیک های متعادل کننده بار پویا که حل مشکل عدم تعادل بار بین ماشین های مجازی را انجام می دهد اهمیت زیادی بدهیم. تکنیک های متعادل کننده بار، در کاهش و زمان پاسخ مؤثر هستند
: را می توان به عنوان زمان انجام کار به طورکلی تعریف نمود. ما زمان تکمیل وظیفه (کار ) Ti در ماشین مجازی j به صورت CTIJ از این رو به عنوان تابع زیر تعریف می شود.
زمان پاسخ به مقدار زمان حـذف شـده بـین ارسـال یـک درخواست و پاسخ است که تولید شده است . ایـن کـاهش در زمان انتظار در بهبود پاسخگویی ماشین هـای مجـازی
مفید است.این ماشینهای مجازی
VM 3…' VM m} مجموعه ازماشین مجازی M که باید Nکـار T {T 1, T2 …7N} را پـردازش کننـد. تمـام ماشین ها به صورت مستقل و مـوازی کـار مـی کنـد و بـا عنوان R در مدل مشخص شده اند. ما زمانبدی وظـایف را به صورت مستقل وغیر انحصاری به ماشینهای مجازی می دهیم. وظایف غیر انحصاری بـه عنـوان NPMTN نشـان داده شده است . غیر انحصاری کار به این معنی اسـت کـه پردازش آن وظایف بر روی ماشین مجازی نمی توان دچار | | وقفه شـود. ( فـرض کنیـد کـه شکست رخ نمی دهد. ) ما زمان اتمام کار یـک Ti توسـط را مشخص کردیم . هدف مـا ایـن اسـت کـه زمـان پردازش یک کار Ti می توان روی ماشـین مجـازی j یـا Pij نشان داد.
زمان پردازش همه وظایف در ماشین مجازی j را می توان با فرمول 4 تعریف نمود.[5] به حـداقل رسـاندن max و بدسـت آوردن بـا فرمـول 5 و معادله6 این مفهوم را می رساندکه در زمان حفـظ تعـادل بار کارها به منظور کاهش max وهمچنین زمان پاسخ از یک ماشین مجازی به ماشین مجـازی دیگـر منتقـل مـی شوند. زمان پردازش یک ماشین بر اساس ظرفیت ماشـین مجازی متفاوت است. در صورت انتقال زمان اتمـام کارهـا ممکن است به دلیلی تعادل بار متفاوت داشته باشد.
روش متعادل کردن بار به صورت بهینه با HBB-LB یک روش پویا که نه تنها تعادل بار در عین حال اولیت وظایف در صف انتظار ماشین های مجازی در نظرگرفته می شـود الگوریتم ما گسترش موجود در تکنیک هـای متعـادل بـار پویا و ادغام با مفهوم رفتار زنبور عسل اسـت. بـار گـذاری بیش از حد وظایف (کارها) از ماشین های مجـازی حـذف که مانند زنبور عسل عمل می کنند.پس از ارائه بارگـذاری شده تحت ماشین مجازی آن تعـدادی از وظـایف اولویـت های مختلف و باری از وظایف تخصیص داده شـده بـه آن ماشین مجازی به روزرسانی می شوند. این اطلاعات بـرای انجام دادن کارهای دیگر مفید خواهد بود.
تصمیم تعادل بار پس از پیداکردن حجم کار و انحراف معیار سیستم تصمیم می گیرد به تعادل بار پردازد یا خیر برای این کار دو حالت وجود دارد:
-1پیداکردن که آیا سیستم تعادل بار دارد.
