بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه روشی براي ایجاد توازن بار در محاسبات ابري با استفاده از الگوریتم خفاش
چکیده
محاسبات ابري یکی از تکنولوژي هاي جدید دنیاي فن آوري اطلاعات است . در محاسبات ابري نیازهاي فن آوري اطلاعات کاربران در یک محیط اشتراکی و به شکل سرویس به آن ها ارائه می شود.استفاده از توازن بار امري حیاتی در سرویس دهندگان محاسبات ابري می باشد. توازن با هدف سرویس دهی بهتر،ایجاد تعادل در بین سرویس ها و افزایش سرعت پاسخ دهی سیستم انجام می شود. منظور از بار در توازن بار می تواند بار پردازنده، بار شبکه، تاخیر و میزان حافظه باشد. در زمینه توازن بار الگوریتم هاي متفاوتی ارائه شده است. در این مقاله هدف استفاده الگوریتم خفاش براي ایجاد توازن است. الگوریتم خفاش جزء الگوریتم هاي فراابتکاري است و بر اساس احتمال عمل می کند. الگوریتم پیشنهادي نسبت به الگـوریتم ژنتیک و الگوریتمpso باعث کاهش سرعت پاسخ دهی ماشین هاي مجازي در محاسبات ابري می شود و همچنین به طور بهینه از تمامی منابع موجود بهـره لازم را مـی بـرد. همچنـین الگوریتم خفاش نسبت به الگوریتم pso بازده بهتري دارد و سرعت همگرایی الگوریتم خفاش بهتر از الگوریتم pso می باشد.
کلمات کلیدي:محاسبات ابري، توازن بار، الگوریتم خفاش، زمان پاسخ دهی، سودمندي منابع.
مقدمه
محاسبات ابري یکی از جدیدترین تکنولوژي هایی است که دنیاي فن آوري اطلاعات را متحول کرده است.کاربران ابر می توانند منابع را به صورت اینترنتی بکار برند و یا نگه دارند . از مزایاي محاسبات ابري می توان مقیاس پذیر بودن، مجازي سازي، افزایش ذخیره سازي و کاهش هزینه هارا نام برد. محاسبات ابري داراي مدل هاي مختلفی است که عبارت انداز : ابر عمومی، ابر خصوصی، ابر انجمنی و ابر ترکیبی(Zhang و همکاران .(2010
محاسبات ابري مدلی براي دسترسی به منابع بنابر تقاضاي کاربران استتوسط شبکه انجام می پذیرد و میتواند نیازهایشان را به سرعت فراهم کند و کمترین مدیریت را نیاز داشته باشد. بنابر این تعریف خصوصیات اساسی محاسبات ابري بر اساس واحد بین المللی استاندارد و تکنولوژي ارائه سرویس مبتنی بر تقاضا، دسترسی به شبکه گسترده ، استخر منابع، قابلیت انعطاف پذیري سریع و سرویس اندازگیري می باشد(Ray و.(2012 Sarkar
در محاسبات ابري نیازهاي کاربران به شکل سرویس به آن ها ارائه میشود و کاربران به اندازه اي که از سرویس استفاده میکنند هزینه آن را پرداخت میکنند . سرویس هاي ارائه شده در محاسبات ابري را می توان به انواع مختلفی تقسیم کرد. براي تفکیک سرویس هاي ابر می توان از مدل "XaaS" یا "هر چیزي به عنوان سرویس" استفاده نمود و X میتواند سخت افزار، نرم افزار، داده، سکو و غیره باشد(غیثی Mell ;1391 و.(2011 Grance براي اینکه فراهم آورندگان سرویس بتوانند به طور موثر منابع را در اختیار کاربران قرار دهند از تکنیک توازن بار استفاده میکنند که یکی از چالشهاي محاسبات ابري نیز می باشد(Kansal و.(2012 Chana
توازن بار تکنیکی است که ازدحام موجود بین سرویس دهنده ها و منابع را کنترل می کند و ازدحام راکاهش می دهد. توازن بار با هدف افزایش کـارایی ، کـاهش زمـان پاسـخ و استفاده بهینه از منابع انجام می شود. این عمل با تقسیم بار بین گره هاي موجود در سیستم، باعث یکنواختی بار در بین گره ها می شود و از بیکار ماندن گره ها و بار زیاد بـر روي گـره هاي دیگر جلوگیري می کند(Velte و همکاران.(2012 Alakeel ;2010 در سالهاي اخیر روش هاي مختلفی براي ایجاد توازن بار ارائه شده است. برخی از این الگوریتم ها عبارت اند از:الگوریتم کلونی مورچگان Mishra) و (2012 Jaiswal و بهینه سازي دسته جمعی ذرات Pandey) و همکاران (2010 الگوریتم ژنتیک(Sawant و.(2011 هدف این مقاله استفاده از الگوریتم خفاش در جهت ایجاد توازن بار در سرویس دهنده هاي محاسبات ابري می باشد. الگوریتم خفاش یکی از الگوریتم هاي هوش جمعی است واساس کـار آن رفتـار مکانیـابی از طریق اصوات می باشد(.(2010 Yang رفتار هر خفاش جداگانه و مستقل از دیگر خفاش ها است. بکارگیري این الگوریتم درجهت ایجاد توازن بار نسبت به الگوریتم ژنتیـک و الگـوریتم pso، باعث کاهش زمان پاسخ دهی سیستم و استفاده بهینه از تمامی منابع موجود می شود و بازده بهتر می شود.
در ادامه این مقاله ابتدا مطالعات پیشین توازن بار ارائه شده است.دربخش سوم جزئیات الگوریتم خفاش بیان شده ودر بخش چهارم الگوریتم پیشنهادي و روابط استفاده شده در آن بیان می شود و در بخش پنجم، این الگوریتم با الگوریتم ژنتیک و الگوریتم pso مقایسه شده است و بخش پایانی نیز مربوط به نتیجه گیري و پیشنهادات کارهاي آینده است.
مطالعات پیشین
در سالهاي اخیر روش هاي فرامکاشفه اي براي توازن بار در ابر مورد استفاده قرار گرفته اند. در این بخش برخی از این الگوریتم هاي فرامکاشفه اي بررسی می شود.
الگوریتم زنبور عسل(Randles و همکاران ( 2010 براي هماهنگی سرورهایی که خدمات وب را میزبانی می کنند مورد استفاده قرار می گیرد. زنبورهاي جستجوگر فرستاده می شوند تا منابع مناسب غذا را جستجو کنند؛ هنگامی که منبعی یافت شد، به کندو برمی گردند تا این موضوع را با استفاده از نمایشی که در کندو به عنوان "رقص جنبشی" شناخته می شود اعلام کنند. مناسب بودن منبع غذا ممکن است از کمیت و کیفیت شهدي که زنبور گردآوري کرده، یا فاصله آن تا کندو نتیجه گیري شود که بر اساس رقص جنبشی ایجاد می شود. سرورها نقش زنبورها را دارند و داراي احتمال px یا pr می باشند. الگوریتم زنبور عسل زمانی که گوناگونی افزایش یابد داراي بازده بهتري می باشد. اما در زمانی که اندازه سیستم تغییر کند تغییري نمیکند و بهینه تر عمل نمیکند(Randles و همکاران .(2010
در الگوریتم ژنتیک(غیثی (1391 ابتدا عمل کد گذاري مناسبی بر روي مسئله انجام می شود. سپس تابع برازشی تعریف می شود که به هر راه حل کدگذاري شده ارزشی نسبت می دهد. والدین براي تولید مثل انتخاب میشوند و از توابع تقاطعو جهشاستفاده می کنند تا فرزندان خود را ایجاد کنند. این عمل چندین بار اجرا می شود تا جمعیت فراهم شده ضوابط همگرایی را بوجود آورده باشند. در این صورت تکرار خاتمه می یابد. این الگوریتم سعی در کم کردن زمان پاسخ دهی و صرفه جویی در استفاده از منابع را دارد(غیثی .(1391
الگوریتم ابتکاري بهینهسازي کلونی مورچهها براي ایجاد سرویس بار توزیع شده در معماري محاسبات ابري ارائه شد(.( 2010 Alakeel مکانیزم به روز رسانی فرومون به طور موثر بهبود یافت و تاثیر ابزارها را براي متعادل ساختن بار بهبود داد. برطبق انواع مختلف، مورچهها راههاي فرومون را در زمانی که از لانه به سمت غذا حرکت میکنند ایجاد میکنند. مورچهها این راه را دنبال میکنند. نقطه قوت دنباله نقاطی است که میزان فرومون در آنجا زیاد باشد. از آنجایی که فرومون تبخیر میشود و از بین میرود، در نتیجه این الگوریتم براساس تصادف و احتمال است و این دو عامل نقش عمدهاي در الگوریتم ایفا میکنند(.(2010 Alakeel
الگوریتم خفاش
الگوریتم خفاش در سال (2010 Yang)2010توسط یانگ ارائه شد. در طراحی این الگوریتم از رفتار طبیعی خفاش ها الهام گرفته شده است. خفاشها مکانیابی را از طریق اصوات انجام می دهند. با استفاده از این مکانیزم خفاش ها پالس صدایی بلندي را ساتع می کنند و به صداي آن که از برخورد با اشیاء باز می گردد گوش فرا می دهند . بنـابراین خفـاش هـا بـه ایـن صورت فاصله خود را از اشیاء محاسبه می کنند و این توانایی را دارند تا تفاوت بین مانع و شکار را تشخیص دهند و بتوانند حتی در تاریکی هم شکار کنند. شبه کـد الگـوریتم خفـاش در شکل 1 آمده است. این الگوریتم بر اساس قوانین زیر ارائه شده است(Musikapun و:(2012 Pongcharoen
1. تمام خفاش ها از روش مکانیابی اشیاء با استفاده از اصوات براي تشخیص فاصله استفاده می کنند و اختلاف بین غذا و مانع را در بسیاري از راه هاي جادویی می داند.
2. خفاشBi به طور تصادفی با سرعت viدر مکان xi با فرکانس ثابت fmin پرواز می کند. طول موج مختلف و رسایی A0 تحقیق براي غذا است. آنها به طـور اتوماتیـک طـول موج از پالس ساتع شده شان را تنظیم می کنند و نرخ پالس نشر شده r=[0,1] که به نزدیک بودن هدف بستگی دارد را تنظیم میکند.
3. اگرچه رسایی در بسیاري از روش ها می تواند متفاوت باشد، یانگ فرض کرده است که رسایی از بیشترین A0 تا کمترین مقدار ثابت AMIN تغییر می کند
در پیاده سازي ، از خفاش هاي مجازي استفاده می شود. قوانین بگونهاي تعریف می شود که موقعیتxi و سرعتviو فرکانس خفاش ها بر اساس شرایط موجود در شبه کد در فضاي
جستجوي d بعدي به روز شوند. مکان جدید xit و سرعت جدید vitو فرکانس در مرحله t به صورت زیر بدست می آید(.(2010 Yang
که در آن در فاصله [0,1] تعیین می شود،، مقدار متغیر j برایخفاش i در مرحله زمانی t مشخص می کند. نتیجه fi براي کنترل گام و دامنه حرکت خفاش هـا اسـتفاده مـی
شود. متغییر بهترین مکان عمومی جاري را براي متغییر تصمیم j را بیان می کند، که مقایسه تمام راه حل هاي بهبود یافته توسط m خفاش را بدست می آورد(.(2010 Yang
پیاده روي تصادفی مسیر قراردادي ریاضی است که شامل توالی از مراحل تصادفی می باشد. پیاده روي تصادفی مشاهدات رفتاري فرایندها در رشته هاي مختلف را توضیح می دهد
و بدین گونه مدل بنیادي براي ثبت فعالیت هاي احتمالی بکار برده می شود(.(1905 Pearson
به منظور تغییرپذیري راه حل هاي ممکن ، یانگ پیاده روي تصادفی را پیشنهاد کرد. عمدتا، یک راه حل در بین بهترین راه حل هاي رایج انتخاب می شود، و سپس پیاده روي تصادفی به منظور ایجاد راه حل جدید براي هر خفاش بکار می رود(.(2010 Yang
(4) At میانگین رسایی تمام خفاش ها در زمان t است و جهت و طول پیاده روي تصادفی را بیان می کند.
در الگوریتم خفاش، بلندي صداي Ai و نرخ ساتع شدن پالس در طول تکرارها باید به روز شوند. بلندي صدا در زمانیکه خفاش شکار خود را پیدا می کند کاهش می یابد در حالی که نرخ پالس انتشاري افزایش مییابد. بلندي صدا می تواند هر مقداري در نظر گرفته شود. براي مثال میتوان A0=0 و Amax=100 را انتخاب کرد. براي هر تکرار از الگوریتم، بلندي صدا Ai نرخ ساطع شدن پالس ri بصورت زیر بروز می شود(:(2010 Yang
(5) ,
(6)
که ثوابت هستند . در این مرحله از الگوریتم نرخ ساطع شدن پالس ri(0) و بلندي صداي A(0)اغلب به صورت تصادفی انتخاب میشوند. براي هر مقدار خواهیم داشت:
الگوریتم پیشنهادي
در سیستم هاي محاسبات ابري گره هایی وجود دارند که نیاز کاربران را نسبت به تعدادي سرویس برطرف مینمایند. حال ممکن است بعضی از این گره ها داراي بار زیاد و بعضی دیگر داراي بار کم باشند. این عامل باعث کاهش کارایی سیستم می شود و زمان پاسخ دهی را افزایش می دهد. براي جلوگیري از این کار می توان بار درون هر گره را بین گره هایی که بار کمتري دارند تقسیم کرد و توازن بار بین گره ها را ایجاد کرد و کارایی سیستم را افزایش داد. هدف از ارائه این الگوریتم ایجاد توازن بار در بین ماشینهاي مجازي و کاهش زمان پاسخ دهی می باشد و سیستم بتواند به طور موثر از تمام ماشین هاي مجازي در دسترس استفاده کند. شبه کد الگوریتم پیشنهادي در شکل 2 نشان داده شده است.
با توجه به معادلات بالا و شبه کد پیشنهادي می توان الگوریتم خفاش را در مراحل زیر پیاده سازي کرد.
مرحله :1ابتدا تعداد کل تکرارها ،فرکانس، نرخ انتشار پالس ri و بلندي صدا A0 براي هر خفاش مقدار دهی میشود. مرحله :2 مکان و سرعت هر خفاش به صورت تصادفی در فضاي d بعدي تعیین میشود.
مرحله :3 تابع برازش براي هر خفاش محاسبه میشود. تابع برازش تابعی است که میزان توانایی هر عنصر را نشان میدهد. مرحله :4 با توجه به تابع برازش هر خفاش، بهترین موقعیت خفاش تعیین می شود.
مرحله :5 فرکانس و سرعت و مکان هر خفاش با استفاده از معادلات((1 و (2) و((3 به روز میشود. مرحله :6 اگر نرخ انتشاري از مقدار تصادفی کمتر بود پیاده روي تصادفی براي آن خفاش اعمال میشود .
مرحله: 7 اگر تابع برازش جدید از تابع برازش قبلی کمتر بود مقدار بهترین مکان را با مقدار جدید جایگزین میشود و مقادیر نرخ انتشار پالس و بلندي صدا به روز میشوند. مرحله :8 الگوریتم را در مراحل 5 تا7 تکرار می شود تا تعداد تکرارها به پایان رسد.
در پیاده سازي این الگوریتم مقادیر در نظر گرفته شده اند. در الگوریتم پیشنهادي شرط دوم نادیده گرفته شده است تا بهترین مکان را بدست آورد. شکل 2 الگوریتم
پیشنهادي را نشان میدهد. محدوده فرکانس در الگوریتم خفاش [0,1] در نظر گرفته شده است و نرخ اولیه انتشار پالس به صورت تصادفی براي هر خفاش تعیین شده است.
براي حل هر مسئله ابتدا باید تابع برازش را ابداع کرد که داراي مقدار غیر منفی باشد و این مقدار نشان دهنده شایستگی فردي خفاش است. تابع برازش هر خفاش مستقل از دیگر
خفاشها است. در این پیادهسازي تابع برازش به صورت زیر میباشد و مکان خفاشها در محدوده تعیین شده قرار دارد.
