چكيدهسیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. محاسبات ابری مدلی توزیع شده با مقیاس بزرگ است که مجموعه مقیاس پذیر و مجازی شده از قدرت محاسباتی مدیریت شده، فضای ذخیره سازی و سرویس‌ها را از طریق اینترنت در اختیار مشتریان قرار میدهد.مسئله تخصیص منابع در رایانش ابری و زمانبندی هر یک از کارهای کاربر بر روی ماشین های مجازی موجود، يک مسئلهNP-Completeمي باشد که تاکنون الگوريتم‌هاي بسياري جهت حل آن ارائه گرديده است. ولی هیچ یک از این الگوریتم ها قادر به برآورده ساختن نیازمندیهای مرتبط با سرعت و دقت در محیطهای رایایش ابری نیستند. در اين پژوهش، روشی ترکیبی از الگوریتم رقابت استعماری و جستجوی محلی، برای حل این مسئله پيشنهاد گردیده است. این الگوریتم با ایجاد یک امپراتوری اولیه سعی در بهبود سازی پاسخ های ممکن، از طریق اعمال مراحل الگوریتم رقابت استعماری دارد. جهت جلوگیری از همگرایی زودرس، الگوریتم رقابت استعماری با یک الگوریتم جستجوی محلی ترکیب شده است. الگوریتم ترکیبی پیشنهادی از یک مکانیسم تشخیص همگرایی مبتنی بر ضریب شباهت استفاده کرده و در زمانهایی که روش رقابت استعماری دچار همگرایی زودرس می شود، روش جستجوی محلی را اجرا می کند.کيفيت جوابها وکارايي الگوریتم پیشنهادی با کارايي الگوريتمهای دور رابین، کلونی مورچگان و ژنتیک، مقايسه گرديد.نتایج : نتایج بدست آمده، نشان میدهد که الگوريتم پيشنهادي از نظر کيفيت زمان اجرا از دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سریعتر عمل می کند. علاوه بر این، الگوریتم پیشنهادی از نظر کیفیت جوابها، از بقيه الگوريتم‌هاي مقايسه شده بهتر عمل می کند. مقدمه:در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای و سیستم‌های آنالیز می‌باشد. در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری ، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hard محسوب می‌شود [Yu12، Garey76].مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09] و الگوریتم ژنتیک [Javier07] اشاره کرد.الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون[1] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت.در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری "زنده ماندن شایسته‌ترین"[2]داروین ایده گرفته است [Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی[3] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم[4]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.بر این اساس، در این مقاله، روشی مبتنی بر الگوریتم رقابت استعماری [Atashpaz07] جهت حل مسئله زمانبندی کار ارائه می شود. این الگوریتم در کلاس الگوریتم های ابتکاری مبتنی بر جمعیت طبقه بندی می شود و در نتیجه مشکلات روشهای سیستماتیک سنتی را ندارد. علاوه بر این، در روش پیشنهادی، از جستجوی محلی جهت جلوگیری از گرفتار شدن الگوریتم در بهینه های محلی استفاده شده است و به همین دلیل ، این الگوریتم در شرایط بهینه های محلی، رفتار هوشمندانه تری را نسبت به الگوریتم ژنتیک از خود نشان می دهد. علاوه بر این، الگوریتم پیشنهادی نیاز به سخت افزار خاصی جهت اجرا شدن ندارد و از نظر زمانی می تواند بسیار بهتر از الگوریتم کلونی مورچگان عمل کند.رقابت استعماریشکل 2-8 فلوچارت الگوريتم رقابت استعماری را نشان مي‌دهد [Atashpaz07]. همانند ديگر الگوريتم‌هاي تکاملي، اين الگوريتم، نيز با تعدادي جمعيت اوليه تصادفي که هر کدام از آنها يک "کشور" ناميده مي‌شوند؛ شروع مي‌شود. تعدادي از بهترين عناصر جمعيت (معادل نخبه‌ها در الگوريتم ژنتيک) به عنوان امپرياليست[5]انتخاب مي‌شوند. باقيمانده جمعيت نيز به عنوان مستعمره[6]، در نظر گرفته مي‌شوند. استعمارگران بسته به قدرتشان، اين مستعمرات را با يک روند خاص که در ادامه مي‌آيد؛ به سمت خود مي‌کشند. قدرت کل هر امپراطوري، به هر دو بخش تشکيل دهنده آن يعني کشور امپرياليست (به عنوان هسته مرکزي) و مستعمرات آن، بستگي دارد. در حالت رياضي، اين وابستگي با تعريف قدرت امپراطوري به صورت مجموع قدرت کشور امپرياليست، به اضافه در صدي از ميانگين قدرت مستعمرات آن، مدل شده است.با شکل‌گيري امپراطوري‌هاي اوليه، رقابت امپرياليستي ميان آنها شروع مي‌شود. هر امپراطوري‌اي که نتواند در رقابت استعماري، موفق عمل کرده و بر قدرت خود بيفزايد (و يا حداقل از کاهش نفوذش جلوگيري کند)، از صحنه رقابت استعماري، حذف خواهد شد. بنابراين بقاي يک امپراطوري، وابسته به قدرت آن در جذب مستعمرات امپراطوري‌هاي رقيب، و به سيطره در آوردن آنها خواهد بود. در نتيجه، در جريان رقابت‌هاي امپرياليستي، به تدريج بر قدرت امپراطوري‌هاي بزرگتر افزوده شده و امپراطوري‌هاي ضعيف‌تر، حذف خواهند شد. امپراطوري‌ها براي افزايش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نيز پيشرفت دهند. با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوري‌ها نزديک‌تر خواهند شد و شاهد يک نوع همگرايي خواهيم بود. حد نهايي رقابت استعماري، زماني است که يک امپراطوري واحد در دنيا داشته باشيم، با مستمراتي که از لحاظ موقعيت، به خود کشور امپرياليست، خيلي نزديک هستند. کلمات کلیدی:تخصیص منابع، رایانش ابری، الگوریتم رقابت استعماری، جستجوی محلی، NP-Complete. فهرست مطالبعنوانصفحهفصل اول: کلیات11-1: مقدمه21-2: بیان مسئله31-3 : پیشینه تحقیق51-4: مروری بر فصل های پایان نامه7فصل دوم: ادبیات تحقیق82-1: مقدمه92-2: محاسبات توری92-2-1: تعریف محاسبات توری102-2-2: معماری محاسبات توری112-2-3: مزایا و خطرات بالقوه محاسبات توری132-2-4: انواع تورها152-2-4-1: تورهای خوشه ای152-2-4-2: تورهای سازمانی172-2-4-3: تورهای سودمندی182-2-4-4: تورهای انجمنی192-3: محاسبات ابری212-3-1: تعاریف محاسبات ابری212-3-2: لایه های سه گانه ابر252-3-2-1: زیرساخت به عنوان سرویس (IaaS)262-3-2-2: بستر به عنوان سرویس (PaaS)272-3-2-2: نرم افزار به عنوان سرویس (SaaS)272-4 الگوریتم رقابت استعماری (ICA)282-4-1 نگاهی به تاریخچه استعمار282-4-2 بهینه سازی بر اساس رقابت استعماری29فصل سوم: پیشینه تحقیق313-1 مقدمه323-2 سیستم مدیریت منابع اکالیپتوس333-3 تخصیص منابع با استفاده از کلونی مورچه ها363-4 تخصیص منابع با استفاده از الگوریتم ژنتیک38فصل چهارم: روش پیشنهادی434-1 مقدمه444-2 ساختار الگوریتم رقابت استعماری پیشنهادی454-2-1: کدگذاری464-2-2: شکل دهی امپراتوری های اولیه474-2-3: مدل سیاست جذب: حرکت مستعمره ها به سمت امپریالیست494-2-4: جابجایی موقعیت مستعمره و امپرالیست524-3: جستجوی محلی534-3-1: مکانیسم کنترل جستجوی محلی54فصل پنجم: پیاده سازی و ارزیابی نتایج565-1 مقدمه575-2: محک های استفاده شده575-3 بررسی پارامترهای مختلف الگوریتم پیشنهادی585-4 مقایسه الگوریتم پیشنهادی با الگوریتم های دیگر615-4-1 مقایسه زمان های اجرا615-4-2 مقایسه کیفیت پاسخها62فصل ششم: نتیجه گیری و کارهای آتی646-1: مطالعات آتی65منابع66 فصل اول:کلیات 1-1 مقدمهسیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای[7]، محاسبات توری[8]و اخیراً رایانش ابری[9].در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای[10] و سیستم‌های آنالیز می‌باشد سود استفاده از محاسبات ابری در سال 2008، برای کاربردهای تجاری را سه تا چهار برابر سیستم‌های غیر ابری تخمین زده شده بود[Stanoevska10].فاستر و همکارانش[11][Foster08]محاسبات ابری را به صورت زیر تعریف می‌کند:" محاسبات ابری مدلی توزیع شده با مقیاس بزرگ است که مجموعه مقیاس پذیر و مجازی شده از قدرت محاسباتی مدیریت شده،فضای ذخیره سازی و سرویس‌ها را از طریق اینترنت در اختیار مشتریان قرار میدهد."در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی[12]شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی[13] عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری[14]، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hardمحسوب می‌شود [Yu12، Garey76]. جواب‌های بهینه این مسئله، مطلوب بسیاری از کارخانه‌های تولیدی و نیز شرکت‌های خدماتی می‌باشند. در بخش دوم این فصل مسئله تخصیص و زمانبندی منابع رایانش ابری تعریف می شود. در بخش سوم، خلاصه ای از پیشنه تحقیق بیان شده و توصیفی از روش پیشنهادی آورده شده است. بخش چهارم به مروری بر فصل های مختلف این پایان نامه تخصیص داده شده است. 1-2 بیان مسئلهساختار کلی منابع یک ابر در شکل 1-1 آورده شده است.شکل 1-1: ساختار کلی منابع ابرسخت افزار فیزیکی ابر (منابع زیرساخت)ماشین های مجازیVM2 VM2VM1زمانبندهسته ابرواسط ابر بر اساس این شکل، یک ابر از تعدادی سخت افزار (پردازنده، حافظه و ...) تشکیل شده است که این منابع لزوماً دارای ساختار همگنی نیستند. برای دسترسی و استفاده آسان کاربر، این عدم همگنی و پراکندگی منابع باید مخفی بماند. برای این منظور از ماشین های مجازی استفاده می شود. هر ماشین مجازی تعدادی از منابع را مدیریت کرده و آنها را در قالب یک واحد معرفی می کنند. به عنوان مثال ممکن است حافظه ای که یک ماشین مجازی معرفی می کند 1 گیگابایت باشد که 500 مگابایت آن مربوط به یک موبایل و بقیه مربوط به یک دستگاه پردازشی دیگر باشد. در خواست های مشتریان (که شامل طیف وسیعی از درخواست های پردازشی و ذخیره سازی و ... است) از طریق واسط کاربر به هسته ابر معرفی می شوند. هسته ابر برای انجام این کارها، درخواستی مبنی بر زمانبندی کارهای موجود بر روی ماشین های مجازی صادر می کند. وظیفه زمانبند، یافتن تخصیصی از ماشین های مجازی به کارهای ورودی است به گونه ای نیازهای محاسباتی و حافظه ای تمامی کارها، با کمترین هزینه برآورده شود. به عبارت دیگر، فرض کنید مجموعه درخواست ها (کارها) به صورت از طریق واسط کاربر به هسته معرفی شده باشد. همچنین فرض کنید ماشین های مجازی آزاد به صورت وجود داشته باشند. حال وظیفه زمانبند تخصیص درخواست های ورودی به ماشین های مجازی آزاد است به گونه ای که تابع زیر را حداقل کند [Zhu12,Chen09,Javier07] :که در آنو این مسئله قیود زیر را دارا می باشد:در فرمول (1-1)، هزینه تخصیص درخواست (کار) iام به ماشین jام را مشخص می کند. این هزینه میتواند به طرق مختلفی تعریف شود، ولی مهمترین هزینه ها عبارتند ازهزینه می تواند ترکیبی از این دو پارامتر نیز باشد.1-3 پیشینه تحقیقمطالعات بسیاری در حوزه تخصیص منابع و زمانبندی منابع چه در بستر رایانش ابر و چه در بستر رایانش توری صورت گرفته است. دسته اول از این الگوریتم ها تعمیمی از الگوریتم های زمانبندی سنتی، مانند الگوریتم های دور رابین، دور رابین وزن دار، زمانبندی با حداقل ارتباط، زمانبندی با حداقل ارتباط بهبود یافته، زمانبندی هش مقصد، زمانبندی هش مبدا و غیره، محسوب می شوند. اگر چه الگوریتم ها الگوریتم هایی بسیار پرکاربرد مسائل زمانبندی محسوب می شوند، ولی دارای سه مشکل عمده هستند که استفاده از آنها را در رایانش ابری با مشکل مواجه می کند: اولاً این الگوریتمها، الگوریتمهایی با ساختار سریال هستند و در نتیجه پاسخ هایی که ارائه می دهند، پاسخ های ممکن است و لزوماً پاسخ های بهینه یا نسبتاً بهینه نخواهند بود و در نتیجه معیارهای کیفیت سرویس را به شکل مناسبی برآورده نمی کنند. دوماً این الگوریتمها، الگوریتمهای مبتنی بر جستجوی حریصانه هستند و در نتیجه امکان گرفتار شدن آنها در حلقه های بی نهایت بسیار بالا بوده و در نتیجه ممکن است این الگوریتمها برای یک مسئله خاص نتوانند جواب ممکن را بیابند و سوماً این الگوریتمها قادر به برآورده کردن معیار تعادل بار نبوده و این امکان وجود دارد که درخواست های بسیاری به یک منبع تخصیص داده شوند، در حالی که سایر منابع آزاد باشند.