بخشی از مقاله
خلاصه
توازن بار یکی از مهمترین جنبهها در محیطهای ابری و توزیع شده است و نوعی مسئله بهینهسازی است که در آن بهرهوری و تخصیص عادلانه و کارآمد منابع را تضمین کرده و منجر به رضایت کاربر میگردد. هر چند توازن بار در سالهای اخیر، زمینه تحقیقات گستردهای از محققان بوده است لیکن هنوز هم نیاز به مطالعه و تحقیق بیشتر دارد. در این مقاله نحوه انجام توازن بار در محیط ابری با استفاده از الگوریتم ژنتیک، مورد بررسی قرار گرفته است. الگوریتم ژنتیک به دو صورت: الف - استاندارد، با جمعیت اولیه تصادفی و ب - تغییر یافته، با جمعیت اولیه مبتنی بر الگوریتم روند-رابین در نظر گرفته شده است؛ با در نظر گرفتن تعداد 13 ابر، مسئله توازن بار ابری مورد بررسی قرار گرفته شد و مشاهده گردید که الگوریتم ژنتیک تغییر یافته دارای زمان اجرای اتمام کمتری نسبت به سایر الگوریتمهای مورد بررسی در این مقاله است.
کلمات کلیدی: رایانش ابری، توازن بار، بهینه سازی، الگوریتم ژنتیک.
.1 مقدمه
رایانش ابری یکی از موضوعات پیشرو در علوم مهندسی کامپیوتر است. هر چند رایانش ابری موضوع جدیدی نبوده و پیداش آن به حدود نیم قرن قبل باز میگردد با این حال در دهه اخیر رشد چشمگیری داشته است که این امر نشان دهنده اهمیت آن میباشد .[1] رایانش ابری دارای جنبههای مختلف و چالشهای گوناگونی میباشد که برای فائق آمدن بر آنها محققان مختلف از سراسر دنیا در حال تلاش میباشند .[2] یکی از جنبههای مهم در مبحث رایانش ابری، تعادل بار است. تعادل بار بهصورت سادهای به معنای استفاده از منابع ابر به بهترین شکل ممکن است بهگونهای که از تمامی منابع ابر بهصورت عادلانهای استفاده گردد ضمن اینکه زمان انتظار، مصرف انرژی، بهرهوری کل ابر و... کل سیستم ابر بهینه گردد.
ازاینرو جهت انجام تعادل بار لازم است یک فرآیند بهینهسازی انجام شود .[4] [3] در واقع مسئله چگونگی انجام تعادل بار در محاسبات ابری یک مسئله بهینهسازی میباشد. در شکل 1 شکل شماتیک توازن بار در رایانش ابری آورده شده است. توازن بارمعمولاً در دو سطح الف - تخصیص منابع1 و ب - زمانبندی وظایف 2 انجام میگیرد .[6] [5] در شکل 1 ، شکل یک ابر به صورت شماتیکی آورده شده است در این ابر معماری ارتباط کاربران، دیتاسنترها و متوازن کننده بار نشان داده شده است.الگوریتم ژنتیک یک الگوریتم فرا ابتکاری شناخته شده و پرکاربرد در زمینههای مختلف است که الهام گرفته شده از طبیعت ژنتیک در جانداران است و بسیاری از جنبههای آن منطبق بر رفتار ژنهای واقعی است .[7]
الگوریتمهای فرا ابتکاری، یکی از انواع الگوریتمهای بهینهسازی تقریبی هستند که دارای راهکارهایی برای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده ای از مسائل را دارند .[8] این الگوریتم اولین با توسط هلند1 و همکارانش در سال 1975 و در دانشگاه میشیگان ارائه شد .[9] الگوریتم ژنتیک در مقایسه با الگوریتمهای رایج بهینهسازی دارای برتریهایی میباشد که از آن جمله میتوان به عدم نیار به محاسبه مشتقات و مشتقپذبر بودن تابع هدف، توانایی تلفیق با سایر روشهای بهینهسازی و نیز امکان استفاده از آن در مسائل بهینهسازی دشوار و پیچیده اشاره کرد .[10]
از آنجا که مسئله توازن بار در رایانش ابری در واقع یک مسئله بهینهسازی است از این رو الگوریتم ژنتیک نیز به صورت گستردهای توسط محققان مختلف برای توازن بار استفاده شده است [18] [17] [16] [15] [14] [13] [12] [11] .[21] [20] [19] در شکل 2، فلوچارت الگوریتم ژنتیک آورده شده است. همانطور که ملاحظه میگردد این الگوریتم دارای سه عملگر انتخاب، تلفیق و جهش است که با استفاده از آنها جمعیت جدید را ایجاد می کند. در الگوریتم ژنتیک استاندارد2 - SGA - جمعیت اولیه به صورت تصادفی ایجاد میگردد در صورتی که در الگوریتم ژنتیک تغییر یافته - MGA - 3 برای توازن بار معمولاً جمعیت اولیه بر اساس یکی از الگوریتمهای کلاسیک توازن بار استفاده میگردد که در این تحقیق از الگوریتم روند-رابین - RR - 4 برای ایجاد جمعیت اولیه در MGA استفاده شده است. برای این منظور در این مقاله ابتدا، روش انجام توازن بار در رایانش ابری توسط MGA آورده شده است سپس برای بررسی این الگوریتم توازن بار تعداد 13 ابر در نظر گرفته شده و MGA با SGA و نیز دو الگوریتم کلاسیک RR و FCFS5 مقایسه شده و نتایج حاصله آورده شده است.
.2 روش انجام کار
هدف از توازن بار در ابر در این مطالعه چگونگی اختصاص ماشینهای مجازی به هر وظیفه است. با فرض آنکه تعداد وظایف ورودی به ابر m باشد بایستی به همین تعداد ماشین مجازی انتخاب و اختصاص داده شود به گونه ای که زمان اجرای کل وظایف بر روی ماشینهای مجازی مینیمم گردد. از آنجا که در الگوریتم ژنتیک هر کروموزوم میتواند پاسخ نهایی بهینه سازی باشد با توجه به شکل 2، هر کروموزم بایستی شماره m ماشین مجازی را در خود ذخیره کند . تعداد کل ماشینهای مجازی میتواند از تعداد وظایف ورودی به ابر کمتر باشد در این صورت از یک ماشین مجازی ممکن است برای اجرای چند وظیفه استفاده گردد.
در صورتی که تعداد بیتهای لازم برای ذخیره شماره هر ماشین مجازی b باشد - به هر بیت یک ژن میگویند - ، در این صورت طول هر رشته کروموزوم - SIZE - برابر با:
که این امر در شکل 3 نشان داده شده است. همچنین با توجه به شکل 4 یک جمعیت متشکل از n کروموزوم است. در شکل 4 فلوچارت الگوریتم ژنتیک آورده شده است. در این فلوچارت جمعیت اولیه SGA به صورت تصادفی ایجاد میگردد ولی در MGA این جمعیت اولیه به صورت "مناسبی" ایجاد میگردد تا باعث افزایش عملکرد و سرعت همگرایی الگوریتم گردد. در این تحقیق برای الگوریتم ژنتیک تغییر یافته از جمعیت اولیهای که توسط الگوریتم کلاسیک RR ایجاد شده، استفاده شده است. در هر دو الگوریتم SGA و MGA، جمعیت جدید با استفاده از سه عملگر انتخاب، تلفیق و جهش ایجاد میگردد. در این مطالعه برای عملگر انتخاب از Tournament selection، برای عملگر تلفیق از تلفیق یک نقطهای و برای جهش از جهش بیتی هر ژن با یک احتمال ثابت استفاده شده است. در این تحقیق از الگوریتم ژنتیک نخبهگرا استفاده شده
