دانلود مقاله چالش ها و الگوریتم های تعادل باردر رایانش ابری با تکیه بر الگوریتم کلونی مورچگان ( ACO )

بخشی از مقاله

چکیده

رایانش ابری به سرعت درحال رشد است. دررایانش ابری، منابع، اطلاعات، نرم افزارودیگر دستگاه های به اشتراک
گذاشته شده بسته به نیازمشتری درزمان خاص ارائه می شوند.رایانش ابری شامل مجازی سازی، رایانش توزیع

شده، پلت فرم، زیرساخت ها، نرم افزار و خدمات مبتنی بر وب می باشد. تعادل باریک مسئله چالش برانگیزدرمحیط ابری است. تعادل بار یک فرایند توزیع شده است که در آن بار در میان گره های مختلف سیستم توزیع شده تا باعث استفاده بهترازمنابع شده وازوضعیتی که در آن برخی از گره ها با بار زیاد وبرخی بیکار و یا کم بارگذاری شده باشد اجتناب شود. دراین مقاله الگوریتم های مختلف بر اساس الگوریتم کلونی مورچگان (ACO)
برای حفظ تعادل بار گره بررسی شده و نمای کلی از آخرین الگوریتمها در محیط پردازش ابری مورد بحث و

بررسی و مقایسه قرارخواهد گرفت.
کلمات کلیدی: رایانش ابری،تعادل بار،کلونی مورچگان
.1 مقدمه

با توسعه سریع فن آوری های پردازش و ذخیره سازی و موفقیت اینترنت ،منابع کامپیوتری ارزانتر ،قوی تر و در دسترس تر از قبل شدند. این روند تکنولوژیکی تحقق جدیدی از مدل رایانش به نام رایانش ابری را فعال کرده است که در آن منابع (به عنوان

مثال، CPU و و دستگاه های ذخیره سازی) به عنوان خدماتی ارائه شده است که می تواند توسط کاربران از طریق اینترنت در مد

مبتنی بر تقاضا اجاره داده شده و منتشر شود. در یک محیط رایانش ابری، نقش سنتی ارائه دهنده خدمات به دو بخش تقسیم بندی
می شود:.1 ارائه دهندگان زیرساخت ها که سیستم عامل ابر را مدیریت کرده و منابع رابر اساس مدل قیمت گذاری مبتنی بر

استفاده اجاره می دهند و.2 ارائه دهندگان خدمات، که منابع را از یک یا بسیاری از ارائه دهندگان زیرساخت برای خدمت به
کاربران نهایی اجاره می کنند. [8] به طور کلی رایانش ابری عبارتند از تعدادی سرور توزیع شده ارائه خدمات به مشتری مبتنی بر

درخواست در یک شبکه با مقیاس پذیری و قابلیت اطمینان.
محققان از رفتار اجتماعی حشرات الهام گرفتند.در عمل مورچه ها به تعدادی از تکنیک های شناخته شده بهینه سازی معروف به

کلونی مورچه( 2(ACO الهام بخشیدند.ACO از رفتار جستجوگر مورچه های واقعی الهام می گیرد .[11] الگوریتم ACO الگوریتم

1 کارشناس ارشد مهندسی فناوری اطلاعات از دانشگاه تربیت مدرس تهران

2 Ant colony optimization

1

جستجوی تصادفی است. این الگوریتم کلنی رفتار مورچه در طبیعت در جستجوی غذا و ارتباط با دیگر مورچه ها از طریق

فرومون به جای گذاشته در مسیر را در بر می گیرد. بسیاری از محققان برای حل مشکل بهینه سازی ازACO استفاده می کنند .[7]
تعادل باردر ابر مکانیزمی است که بار کاری را به صورت پویا در میان تمام گره توزیع می کند.با رسیدن به بالا بودن نسبت رضایت کاربر و بهره برداری از منابع مطمئن شوید که هیچ گره ای حاوی بار زیاد نیست. در این مقاله "بهینه سازی کلونی مورچه ها برای تعادل بار موثر در رایانش ابری را پیشنهاد می شود". بقیه این مقاله به شرح زیر است: بخش 2 طبقه بندی رایانش ابری

را توصیف می کند. بخش 3 تعادل بار را توصیف می کند. در بخش چهارم بهینه سازی کلونی مورچه توصیف می شود. بخش 5
تجزیه و تحلیل مقایسه ای از الگوریتم های مختلف ACO را توصیف می کند. در نهایت بخش ششم نتیجه گیری مقاله است.

.2 طبقه بندی ازرایانش ابری

1,2معماری ابر - شکل 1 معماری ابررا نشان می دهد . معماری ابر نرم افزار های کاربردی را با استفاده سرویس های مبتنی بر تقاضا قابل دسترس از طریق اینترنت طراحی می کند.

Software- as- a- service(SaaS)

Platform- as- a- service(PaaS)
توسعه اجرای برنامه های کاربردی ابر

Infrastructure-as-a-service(IaaS)×
×مجازی سازی ،شبکه های ذخیره سازی به عنوان سرویس

Hardware-as-a-service×

شکل:1معماری ابر

بر اساس تعریف NIST از محاسبات ابری دو نوع ابر وجود دارد .
2,2مدل استقرار-3که اشاره به مکان و مدیریت زیر ساختهای ابر می کند.این مدل چهار نوع می باشد:ابر عمومی4،ابر
خصوصی5،ابر گروهی6،ابر آمیخته7
3,2 مدل سرویس-8 اشاره به انواع خاصی ازسرویس هایی می کند که شما می توانید از طریق آن به پلت فرم ها(بستر های نرم
افزاری)رایانش ابری دسترسی داشته باشید.این مدل شامل سه نوع زیرمی باشد:

1,3,2زیر ساخت به عنوان سرویس. 9IaaS به تامین تقاضا از منابع زیرساختی معمولا از لحاظ VMS اشاره می کند. صاحب ابر کسی که IaaS راارائه می دهد به نام ارائه دهنده IaaSخوانده می شود. نمونه هایی از ارائه دهندگان IaaS شامل

3 Deployment model 4 Public Cloud 5 Private Cloud 6 Community Cloud 7 Hybrid Cloud 8 Service model

9 Infrastructure as a Service

2

[13] Amazon EC2،.[16] Flexiscale [14] ,GoGridسرویسهای زیرساخت ابری یا زیرساخت به عنوان سرویس

(IaaS)زیرساخت رایانه را که عموماً یک بستر مجازی است را به صورت سرویس ارائه میدهند. کاربران به جای خرید سختافزار و نرمافزار و فضای مرکز داده (دیتا سنتر) ویا تجهیزات شبکه، همه این زیر ساختها را به صورت یک سرویس
کاملاً برونسپاری 10شده میخرند. صورتحساب سرویسمعمولاً بر اساس مدل رایانش همگانی (Utility Computing) و

میزان منابع مصرف شده صادر میشود و بنابر این هزینه منعکس کننده میزان فعالیت است. این شیوه در واقع تکامل یافته مدل عرضه سرورهای خصوصی مجازی است.
.2,3,2بستر به عنوان سرویس.11 PaaS اشاره به ارائه منابع لایه پلت فرم، از جمله پشتیبانی از سیستم عامل و چارچوب توسعه

نرم افزار دارد. نمونه هایی از ارائه دهندگان PaaS شامل [17] Google App Engine ،Microsoft Windows Azure [20] ،[18] Force.com می باشد.

.3,3,2نرم افزار به عنوان سرویس. سرویسهای برنامه کاربردی ابری یا نرمافزار به عنوان سرویس(12(SaaS ، نرمافزار را به صورت سرویس روی اینترنت تحویل میدهند و بدین وسیله نیاز به نصب نرمافزار روی رایانههای مشتریان را ازبین میبرند و نگهداری و پشتیبانی را ساده تر میسازد .نمونه هایی از ارائه دهندگان SaaS شامل [18] Salesforce.com ،Rack space [15] ،[19] SAP Business By Design می باشد.

به طور خاص، پنج ویژگی اساسی ازرایانش ابری عبارتند از :[5]

4,2 خود خدمتی مبتنی بر تقاضا.13مصرف کنندگان با نیاز فوری در یک زمان خاص می توانداز منابع کامپیوتری مانند زمان CPU، CPU، ذخیره سازی شبکه، استفاده از نرم افزار، و غیره به یک مد خودکار(یعنی به راحتی و خودخدمتی)سودبرده بدون آن که

نیازبه متوسل شدن به ارائه دهنده این منابع باشد.به عبارت بهتر مشتری میتواند امکانات رایانشی همچون فضای ذخیرهسازی در شبکه را به هنگام نیاز از هر سرویس دهندهای به طور خودکار بهدست آورد.
5,2 دسترسی گسترده شبکه14 امکانات روی شبکه در دسترس هستند و میتوان با سازوکارهای استاندارد به آنها دست یافت. این
سازوکارها از بسترهای ناهمگون و متفاوت (گوشیهای موبایل، لپتاپها وPDA ها) پشتیبانی میکنند .هنگامی که ما به

دسترسی به شبکه گسترده رایانش ابری اشاره می کنیم، منظور ما منابعی به میزبانی ابر است که باید در دسترس هر دستگاه محاسباتی بدون در نظر گرفتن نوع و مکان اتصال به اینترنت، قرار بگیرد. از 5 ویژگی اساسی رایانش ابری، بیشتر دسترسی به

شبکه گسترده مورد بحث قرار دارد. دلیل آن هم این است که زمانی که شما در مورد ابر خصوصی فکر می کنید، اولین مورد برای

10 Outsource 11 Platform as a Service 12 Software as a Service 13 On-demand self-service 14 Broad network access

3

استقرار ابر خصوصی، حفاظت از اطلاعات با ارزش خود به دور از دسترسی بسیاری از مردم در اینترنت است. به نظر می رسد در

دیدگاه بسیاری از افراد، broad network accessدر ابر عمومی نسبت به ابر خصوصی کاربردی تر باشد. با این حال، شما می توانید دیدگاه متفاوت تری نسبت به broad network access داشته باشید.

.6,2 جمع کردن منابع.15منابع رایانشی فراهمکننده جمعآوری شدهاند تا با به کارگیری مدل »چند مشتری« به چندین کاربر خدمترسانی کنند. این کار به وسیله منابع فیزیکی یا مجازی مختلف که به شکلی پویا و بنابر درخواست مشتری واگذار و پس

گرفته میشوند صورت میگیرد. در اینجا حالتی از عدم وابستگی به مکان وجود دارد که در آن مشتری معمولا کنترل یا دانشی

درباره محل دقیق منابع فراهم شده ندارد ولی ممکن است در سطوح بالاتر انتزاعی بتواند محل را تعیین کند، مثل: کشور، استان یا

مرکز داده. برای نمونه منابع شامل فضای ذخیرهسازی، توان پردازشی، حافظه، پهنای باند شبکه و ماشینهای مجازی میشود. [5] 7,2 انعطافپذیری بالقوه.16میتوان امکانات را به سرعت و با انعطاف، در بعضی موارد به صورت خودکار، به دست آورد تا به سرعت گسترش داده شده(از دید مقیاس) یا در جا آزاد شوند و خیلی سریع به مقیاس کوچکتری دست یابند. از دید مشتری امکاناتی که برای به دست آمدن در دسترس هستند اغلب نامحدود به نظر میآیند و میتوانند به هر مقدار و در هر زمان خریداری شوند.[5]

8,2 پرداخت در قبال استفاده.17هر چند منابع کامپیوتری توسط مصرف کنندگان متعدد (یعنی با دسترسی چندگانه)با هم مخلوط و به اشتراک گذاشته شده اند ،اما زیرساخت های ابر قادراست ازمکانیسم های مناسب استفاده کند.[ 5]سیستمهای ابری منابع را خودکار کنترل و بهینه میکنند. این کار با بهکارگیری توانایی اندازهگیری در سطحی که مناسب نوع سرویس یا منبع مورد استفاده

است (مانند: فضای ذخیرهسازی، توان پردازشی، پهنای باند و شمار کاربران فعال) انجام میشود. میزان استفاده از منابع میتواند به شکلی شفاف هم برای مشتری و هم برای فراهمکننده تحت نظر گرفته شود، کنترل شده و گزارش داده شود.
.3تعادل بار18
مسئله تعادل بار در رایانش ابری یک چالش جدید است. همیشه یک راه حل توزیع شده مورد نیاز است. از آنجا که همیشه در

عمل امکان پذیر ومقرون به صرف نیست ک یک تا تعداد بیشتری سرویس دهنده برای پاسخ به در خواستهای مورد نیاز بیکار نگه

داریم . کارها نمی توانند به سرور مناسب اختصاص داده شده، و تعادل بار موثربه صورت جداگانه برای مشتریان در ساختار ابر بسیار پیچیده است و اجزاء در سراسر یک منطقه گسترده حضور دارند.تعادل بار، روند تخصیص دوباره کل بار به گره های

منحصر به فرد یک سیستم جمعی به منظور بهره برداری موثر از منابع، بهبود بخشیدن به زمان پاسخ یک کار و به طور همزمان

حذف وضعیتی است که در آن تعدادی از گره ها به شدت بار شده اند در حالی که تعدادی دیگر بار کمی دارند، می باشد.

15 Resource pooling 16 Rapid elasticity 17 Measured Service 18 Load balancing

4

الگوریتم های تعادل بار به دو دسته ایستا و پویا تقسیم بندی می شوند. الگوریتم های استاتیک بیشتر برای محیط های همگن و

پایدار مناسب می باشد و می تواند نتایج بسیار خوبی در این محیط ها تولید نماید. با این حال، آنها معمولا انعطاف پذیرنبوده و نمی توانند خود را با تغییرات پویای ویژگی ها در زمان اجرا تطبیق دهند . الگوریتم پویا انعطاف پذیر تر بوده و انواع مختلف

ویژگی ها در سیستم را در هر دو حالت یعنی در قبل و در طول زمان اجرا در نظر می گیرند.[1] تعادل بار فرایندی است که عملکرد سیستم را از طریق توزیع مجدد بار در میان پردازنده ها بهبود می دهد.[2]

.1,3معیارهای تعادل بار در ابر

تکنیکهای تعادل بار موجود در ابر، پارامترهای مختلف را در نظر می گیرد.[6]

• سربار مرتبط-هنگامی که یک الگوریتم تعادل بار اجرا می شود مقدار سربار درگیر را تعیین می کند. این شامل سربار

مقرر برای بهبود وظایف، ارتباطات میان پردازنده ها و پردازشها می شود. این مقدار باید به حداقل برسد تا تکنیک تعادل

بار به طور کارآمد عمل نماید.

شکل .2انواع تعادل بار

• توان عملیاتی: برای محاسبه وظایفی که اجرای آنها به پایان رسیده، استفاده می شود. این مقدار باید برای بهبود کارایی

سیستم بالا باشد.

• کارایی: برای کنترل بهره وری سیستم استفاده می شود. این معیار باید هزینه های معقول را بهبود بخشد. به عنوان مثال،

زمان پاسخ وظایف را کاهش دهد در حالی که تأخیرها را قابل قبول نگه دارد.

• بهره برداری از منابع: برای کنترل بهره برداری از منابع استفاده می شود. این مقدار باید برای تعادل بار کارآمد بهینه شود.

• مقیاس پذیری: توانایی یک الگوریتم برای اجرای تعادل بار برای یک سیستم با تعداد متناهی گره است. این معیار باید بهبود داده شود.

5

• زمان پاسخ: مقدار زمان گرفته شده برای پاسخ دادن، توسط یک الگوریتم تعادل بار خاص در یک سیستم توزیع شده

است. این پارامتر باید به حداقل رسانده شود.

• تحمل خطا: توانایی یک الگوریتم برای اجرای یکنواخت تعادل بار در موارد خرابی اتصال است. تعادل بار باید یک

تکنیک تحمل خطای خوب باشد.

• زمان مهاجرت: زمانی برای مهاجرت کارها یا منابع از یک گره به دیگری است. این زمان برای افزایش کارایی سیستم

باید به حداقل رسانده شود.[6]

.4الگوریتم کلونی مورچگان

Dorigo M. الگوریتم مورچه ها را بر اساس رفتار مورچه ها در سال 1996 پیشنهاد داده است. [7] [11]، این الگوریتم یک

الگوریتم فراابتکاری جدید برای حل مسائل بهینه سازی ترکیبی است.این الگوریتم در ابتدا به عنوان یک راه حل چند عامله (Multi Agent)برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد. الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها

حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء

از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. در طبیعت ، کلونی مورچه ها بدون اینکه اطلاع سراسری از مسیرها داشته باشند ، معمولا کوتا هترین مسیر لانـه تـا محـل غـذا را پیـدا مـی کند. زمانیکه مورچه راه می رود، از خود فرمون ترشح می کند وردپایی به جای می گذارد

. مورچهها برای انتخاب مسیر ، مسیری را بـر میگزینندکه دارای فرومون بیشتری است.

شکل.3چگونگی یافتن کوتاهترین مسیر توسط مورچه ها

در شکل A.1، مورچهها به نقطهای میرسند که بایستی تصمیم بگیرند که آیا به راست بروند یا به چپ. از آنجایی که هیچ سرنخی

وجود ندارد که کدام بهتر است، مورچهها یکی را بصورت تصادفی بر می گزینند. در شکل B.1 و C.1 با فرض اینکه مورچهها

6

دارای سرعت یکسانی هستند، مسیری که دارای طول کمتری می باشد پس از مدتی توسط مورچههای بیشتری طی می شود و

بنابراین میزان فرومون بیشتری روی آن مسیر بجای گذاشته میشود.در D.1، مورچه در نقطه تصمیم گیری مسیری را که دارای فرومون بیشتری است را با احتمال بالاتر انتخاب می کند. بدین گونه کلونی مورچهها پس از مدتی کوتاهترین مسیر را پیدا می کند.

علاوه بر این فرومون بجای گذاشته شده با نرخ معینی بخار میشود و به همین دلیل مسیری که کمتر مورد تردد مورچهها واقع می شود پس از مدتی فرومونش را از دست می دهد. لذا اگر در محیط تغییری حاصل شود(مثلا مسیری مسدود شود)، مورچهها می

توانند مسیر بهینه دیگری را بیابند.ACO [11]از کلنی مورچه هایی الهام گرفته شده که با هم به رفتار جستجوگری کار می کنند.

در واقع مورچه ها الهام بخش بسیاری از محققان برای کارهایشان می باشد و روش مورچه ها توسط بسیاری محققان برای حل

مشکلات در زمینه های مختلف به کار رفته است.این رو ش معروف به روش ACO می باشد.[9]

.5تجزیه و تحلیل مقایسه ای از انواع :ACO

در این بخش در مورد مقایسه الگوریتم های مختلف کلونی مورچگان بحث می کنیم. روش های مختلفی برای تعادل بار وجود
داردکه با توجه به برخی شرایط مناسب بوده اما همه آنها نتایج خود رادارند، که در بین آنها بعضی از الگوریتم ها مناسب برای

ماهیت استاتیک و برخی مناسب برای ماهیت پویا می باشند. این الگوریتم ها به شیوه ای غیر متمرکز کار می کنند.جدول 1 مزایا ومعایب الگوریتم ها و شرح مختصری از آنها را نشان می دهد.به عنوان نمونه حالات اولین الگوریتم برای سه سطح رایانش ابری[10]،به طورموثر کار می کند و باعث استفاده بهتر از منابع شده اما،سربار بیشتری را در طول زمان اجرا می دهد.در یک زمانبندی کار در ابر بر اساس تعادل بار 19LBACO [7] ACO (بهینه سازی تعادل بار مورچگان) پیشنهاد می شودو برای پیدا کردن تخصیص منابع به صورت مطلوب برای هر وظیفه به صورت پویا مورد استفاده قرار می گیرد.در این الگوریتم مقایسه با الگوریتم های عمومی ACO و الگوریتم FCFS انجام می شود.در نتیجه گره ها به صورت پویا متعادل می شوند. علاوه بر

این،وظایف دو به دومستقل است یعنی هیچ محدودیت اولویت بین کار وجود نداشته ومتمرکز است و این برای سیستم ابر واقع

گرایانه نیست. اشکال اصلی این روش ناهمگنی های سیستم است.مشکل ناهمگنی سیستم در تکنیکی که از مکانیزم تعادل بار بر اسا س کلونی مورچه و تئوری شبکه های پیچیده استفاده می کنند حذف شده است.[12]این روش یک مقیاس پذیری خوب از گره ها را فراهم کرده و تحمل خطای سیستم را بهتر می کند.عملا سربار را در طول زمان اجرا افزایش داده و زمان پاسخ نامناسب

می باشد.یک مورچه به یک حالت بن بست به علت عدم هماهنگی با مورچه ها برخورد می کند.در رایانش ابری طرح ابتکاری

استفاده ازتغییر یا اصلاح در چارچوب الگوریتم ACO است[4] و این محدوده را به حداقل می رساند (توان عملیاتی از سیستم
محاسبات ناهمگن).این تغییر الگوریتم درگیر در فرمول بروزرسانی فرمون عمومی است.این تغییر استفاده از منابع را بهتر کرده اما

تحمل سیستم در برابر خطا را بهبود نمی دهد.هدف اولیه در هر تعادل بار بهترشدن استفاده از منابع است. تعادل بار در گره ها ازبهینه سازی ACO استفاده می کند.[9]این بهترین حالت برای تعادل بار موثر می باشد. زیرا در کار قبلی مورچه می تواند تنها در

یک جهت حرکت کند .[12] اما در این الگوریتم یک مورچه می تواند حرکت در هر دو جهت رو به جلو و درجهت عقب داشته باشد. از جمله یک مورچه مواد غذایی رابا حرکت رو به جلو و بازگشت به لانه را با حرکت رو به عقب می یابد.این برای تعادل

19 Load Balancing Ant Colony Optimization

7

سرعت گره مفید است. این الگوریتم سریع کار می کند به دلیل این که یک مورچه می تواند به صورت همزمان در هر دو جهت

برای تعادل گره حرکت کند. این الگوریتم باعث استفاده بهتر از منابع می شود. اما این الگوریتم [9] بر روی پارامتر محدودی مانند
سرعت، سربار شبکه و تحمل خطا کار می کند.این الگوریتم از قدرت بیشتری برخوردار است و مسائل مرتبط با انرژی را در نظر نمی گیرد.هزینه های عملیاتی متعدد در نظر گرفته نمی شود زیرا ممکن است باعث عملکرد ضعیف نتیجه شود.