فهرست مطالب عنوان صفحهچکیده1فصل اول:کلیات پژوهش21-1 مقدمهتعریف31-3سابقهوضرورت انجام تحقیق41-4 هدف ها61-5 جنبه نوآوری تحقیق71-6 مراحلانجامتحقیق71-7 ساختارپایان نامه7فصل دوم:مقدمهای بر رایانش ابری82-1 مقدمه82-2 تعریف رایانش ابری82-3 سیر تکامل محاسبات102-4 عناصر زیربنایی محاسبات122-4-1 محاسبات گرید122-4-2 مجازی سازی122-4-3 وب 2122-4-4 معماری مبتنی بر سرویس(SOA)132-5 سرویسهای محاسبات ابری132-5-1نرمافزار به عنوان سرویس (SaaS)132-5-2 پلتفرم به عنوان سرویس(PaaS)132-5-3 زیر ساخت به عنوان سرویس(IaaS)142-6 لایه ماشین مجازی142-6-1 ماشین‌های مجازی142-6-2 ناظر ماشین مجازی142-7 لایه مرکز داده142-7-1 سخت افزار152-8 مدلهای پیاده سازی محاسبات ابری152-8-1 ابر خصوصی152-8-2 ابر عمومی152-8-3 ابر گروهی162-8-4 ابر آمیخته162-9 مقدمهای بر شبیه سازی162-10 برخی نرم افزارهای شبیه سازی شبکه های محاسباتی172-10-1 کلودسیم172-10-2 کلود آنالایز182-10-3 کلود ریپورتر182-10-4 اپ تی آرسیم182-10-5 گریدسیم182-11 آشنایی با ابزار کلودسیم182-11-1 کاربردهای کلودسیم192-11-2 معماری کلودسیم192-11-2-1 لایه کد کاربر202-11-2-2 لایه کلودسیم212-11-2-3 لایه هسته کلودسیم212-12 مدل های تخصیص ماشین های مجازی212-13 کلاس های موجود در کلودسیم222-14 کلاس پهنای باند222-15 کلاس کلودلت یا تکه ابر232-16 کلاس تکه ابر زمانبند252-17 کلاس مرکز داده252-18 کلاس مرکز داده واسط252- 19 کلاس میزبان252-20 کلاس توپولوژی شبکه262-21 کلاس ماشین مجازی262-22 جمعبندی263-1 مقدمه273-2 الگوریتم موازنه بار فرصت طلبانه(OLB)283-3 الگوریتم زمان اجرا کمینه(MET)283-4 الگوریتم زمان اتمام کمینه(MCT)1283-5 الگوریتم Min-Min293-6 الگوریتم GA293-7 الگوریتم گرمایشی(SA)303-8 الگوریتم Tabu303-9 الگوریتم بهترین درصد (KPB)K313-10 الگوریتم بهینه سازی اجتماع ذرات(PSO)313-11 الگوریتم بهینه سازی کلونی مورچگان(ACO)313-12 الگوریتم ترکیبی جهش قورباغه343-13مقایسه الگوریتم های اکتشافی373-14 نتیجه گیری40فصل 4: روش پیشنهادی414-1 مقدمه414-2بهبوددر زمانبندیالگوریتمجهشقورباغه414-3 تفاوت در نتایج حاصل از الگوریتم جهش قورباغه و الگوریتمهای دیگر424-4 ارائه روش پیشنهادی:424-5 جمع بندی:43فصل پنجم:آزمایش ها و ارزیابی نتایج445-1 مقدمه445-2 محیط پیاده سازی و اجرا455-2-1 پارامترها و مقادیر مورد استفاده45فصل ششم60نتیجه گیری و پیشنهادات606-1 مقدمه606-2 نتایج حاصل از تحقیق606-3 پیشنهادها61مراجع:62واژه نامه68 فهرست جدولهاعنوان صفحهجدول 2-1.انواع متغیرها و پارامترهای کلاسBw.......... 21جدول 2-2.متدها و متغیرهای کلاس Cloudlet................ 22جدول 3-1.مقایسه الگوریتمهای زمانبندی.............. 34جدول 5-1.پارامترهای استفاده شده در الگوریتم Aco.... 41جدول 5-2.پارامترهای استفاده شده در الگوریتم Sfla.... 41جدول 5-3.پارامترهای استفاده شده در کلودسیم......... 42جدول 5-4.زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 50 تسک.................................................. 43جدول 5-5. زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 100 تسک............................................... 43جدول 5-6. زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 200 تسک............................................... 44جدول 5-7. زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 300 تسک............................................... 45جدول 5-8. زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 400 تسک............................................... 45جدول 5-9. زمان اجرا هر الگوریتم در محیط ابر با 10 بار اجرا و 500 تسک............................................... 46جدول 5-10. کدهای نوشته شده در این پروژه............ 48 فهرست شکلهاعنوان صفحهشکل 2-1. تعریف NISTدر محاسبات ابری................... 9شکل 2-2. سیر تکامل محاسبات......................... 10شکل 2-3. معماری جدید CLOUDSIM....................... 19شکل 3-1. نمایش مراحل یافتن کوتاهترین مسیر توسط مورچهها29شکل 3-2. شبه کد الگوریتم کلونی مورچه............... 30شکل 3-3. فلوجارت الگوریتم کلونی مورچه.............. 31شکل3-4. فلوچارت الگوریتم Sce-Ua...................... 33شکل 5-1. نمودار Aco................................. 47شکل 5-2. نمودار Sfla................................. 47شکل 5-3. میانگین makespan از الگوریتمهای Sfla، Acoو Fcfs. 51 فهرست کلمات اختصاری:الگوریتم کلونی مورچهAnt Colony OptimazitionAcoواسط الگوریتم کلونی مورچه Ant Colony Optimazition BrokerAco Brokerپهنای باندBandwidthBwتکامل مجتمع رقابتیCompetitive Complex EvolutionCceمرکز دادهData CenterDcاولین ورودی اولین خروجیFirst Come First ServiceFcfsواسط اولین ورودی اولین خروجیFirst Come First Service BrokerFcfsBrokerالگوریتم ژنتیکGenetic AlgorithmGaسخت افزار به عنوان سرویسHardware As A ServiceHaasزیر ساخت به عنوان سرویسInfrastructure as a ServiceIaasالگوریتم بهترین درصدk-Persent BestKpbالگوریتم زمان اتمام کمینهMinimum Completion TimeMctحداقل زمان تکمیل مورد انتظارMinimum Expected Completion TimesMectالگوریتم زمان اجرا کمینهMinimum Execution TimeMetالگوریتم مینیمم-ماکسیمم Min-Max AlgorithmMin-Maxالگوریتم مینیمم-مینیممMin-Min AlgorithmMin-Minچند میلیون دستور در ثانیهMilion Instructure Per SecondMipsموسسه فناوری و استانداردNational Of Standards And TechnologyNistالگوریتم موازنه بار فرصت طلبانهOpportunistic Load BalancingOlbسکو به عنوان سرویس Platform As A ServicePaasعناصر پردازشیProcess ElementPeبهینه سازی گروه ذراتParticle Swarm OptimizationPsoالگوریتم گرمایشیSimulated AnnealingSaنرم افزار به عنوان سرویسSoftware As A ServiceSaasتکامل مجتمع قورباغهShuffled Complex EvalutionSceجهش قورباغهShuffled Frog LeapingSflالگوریتم جهش قورباغهShuffled Frog Leaping AlgorithmSflaواسط الگوریتم جهش قورباغهShuffled Frog Leaping Algorithm BrokerSflaBrokerمعماری مبتنی بر سرویسService Oriented ArchitectureSoaبر پایهی اینترنتInternet-BaseTcp/ipماشین مجازیVirtual MachineVmناظر ماشین مجازیVirtual Machine MonitorVmm چکیده:امروزه با پیشرفت تکنولوژی و همه گیر شدن سیستمهای کامپیوتری ، سیستمهای رایانش ابری به شدت رو به توسعه و ترویج هستند که با توجه به این حجم عظیم انتقال اطلاعات در بستر اینترنت نیاز مبرمی به مکانیزم هایی داریم تا در کوتاهترین زمان، به تمامی سرویسها پاسخ دهند و کارهای قابل انجام را به بهترین شکل به انجام رسانند. از الگوریتمهایی که در زمانبندی کار در محیط های ابری استفاده شده است می توان به FCFS و RR اشاره کرد که جزو قدیمیترین و پایدارترین الگوریتمها دراین زمینه می باشند. از طرف دیگر ، در سالهای اخیر با ظهور علوم جدیدی همچون هوش مصنوعی، محاسبات نرم، یادگیری ماشین و غیره ، متخصصین حوزهی فناوری اطلاعات در تلاشند تا الگوریتمهای کلاسیک را با الگوریتمهای نوظهور تلفیق کنند و یا از الگوریتمهای هوشمند به عنوان یک جایگزین بهره بگیرند.اخیرا ، در حوزهی زمانبندی کارها در محیط ابر از الگوریتمهای هوشمندی همچون ژنتیک، PSO ، کلونی مورچگان، شبیهسازی تبرید و غیره استفاده شده است که نتایج حاصله نشان دهندهی بهبود در زمان کل اجرای کارها بوده است. در این پژوهش سعی بر این است تا از الگوریتم جهش قورباغه جهت کاهش زمان کارها در زمانبندی در محیط ابر بهره گرفته شود تا بهبودی در الگوریتمهای زمان بندی نسبت به کارهای قبلی به دست آید. پیادهسازی آزمایشات و شبیهسازی ها به زبان جاوا و با کمک کتابخانه CloudSim انجام شده است. نتایج حاصله از انجام پیادهسازیها و آزمایشات انجام گرفته در این پایاننامه نشاندهنده بهبود زمان اجرای کارها در محیط ابر میباشد که در این تحقیق با الگوریتم های FCFS و ACO مقایسه شده است. واژههای کلیدی:پردازش ابر، محیط ابر ، زمانبندی، کلونی مورچه، جهش قورباغه فصل اول: 1-1 مقدمهرایانش ابری با عنوان یکی از مشهورترین و داغترین موضوعات در زمینه فناوری اطلاعات پدیدار گردید. امروزه کاربران اینترنت به وسیله ابزارهای الکترونیکی بسیار سبکی به سرویسهای آن دسترسی دارند،در چنین حالتی کاربران نیازهای خود را که ممکن است نیازمند پردازش سنگینی باشدبر حسب تقاضا درخواست می کنند و بدون توجه به محل سرویس و چگونگی ارائه آن،به مشاهده نتایج بازگردانده شده می پردازند. رایانش ابری بر پایه tcp/ip وبر پایه اینترنت [1]بوده و شامل پردازندهها،حافظههای عظیم،شبکه انتقال داده سریع و معماری سیستمهای قابل اعتماد می باشد و بدون پروتکلهای استاندارد حاکم بر شبکه نمی توان موجودیتی به این فناوری بخشید. سرویسهای این تکنولوژی به 3 دسته عمده تقسیم می شود: زیر ساخت به عنوان سرویس[2]،سکو به عنوان سرویس[3] و نرمافزار به عنوان سرویس[4] می باشند. رایانش ابری به 5 لایه ،مشتری، کاربردی، سکو، زیرساخت و سرورها تقسیم می شوند. تحمل خطای فوق العاده این فناوری، وفق پذیری آن را با زیرساخت شبکه افزایش می دهد. ویژگی کاربرد آسان آن، تمام پیچیدگی سرویسها را مخفی کرده و کاربران را با رابطی ساده به مرکز داده متصل میکند. مجازیسازی و امنیت بالا نیز از خصوصیات دیگر این تکنولوژی می باشند et al., 2009).Dikaiakos). در سالهای اخیر، الگوریتمهای بهینه سازی به خصوص الگوریتمهای هوش جمعی در تمامی علوم به خوبی به کار گرفته شدهاند و نسبت به الگوریتمهای کلاسیک کارایی بسیار بالایی داشته اند.از طرفی الگوریتمهای زمان بندکار،الارغم حالت توزیع پذیری که دارند در محیطهای ابری فاقد این هوش می باشند.در این تحقیق سعی بر این است تا با الگوریتم قورباغه دقت و سرعت زمانبندی کارها را در محیط ابری بهبود بخشیم. وبا مقایسه دو الگوریتم مورچه و قورباغه بررسی شود که کدام الگوریتم از نظر بهینه سازی زمان تکمیل کل کارها بهتر عمل می کند. تعریفطبق تعريف موسسه ملي استاندارد و فناوري،رايانش ابري مدلی است براي فراهم کردن دسترسي آسان بر اساس تقاضا کاربر از طريق شبکه به مجموعهاي از منابع رايانشي قابل تغيير و پيکربندي(مثل سرورها، شبکه ها، فضاي ذخيرهسازي، برنامههاي کاربردي و سرويسها) که اين دسترسي بتواند با کمترين نياز به مديريت منابع و يا نياز به دخالت مستقيم فراهم کننده سرويس به سرعت فراهم شده يا آزاد گردد. به دليل طبيعت پوياي منابع و همچنين درخواستهاي مختلف کاربران در فناوري ابري براي افزايش کارايي، نياز به انتخاب يک الگوريتم زمانبندی درست و کارآمد مي باشد..(Chang et al.,2010)الگوریتمهایبهینهسازی الهام گرفته از طبیعت،به عنوان روشهای هوشمند بهینهسازی در کنار روشهای کلاسیک موفقیت خوبی از خود نشان دادهاند.از جمله این روشها می توان به الگوریتمهای قورباغه، وبهینهسازی کلونی مورچهها (بر مبنای حرکت بهینه مورچهها)اشاره نمود.در این راستا،در تحقیق حاضر از میان الگوریتمهای تقریبی مختلف،دو الگوریتم قورباغه و بهینهسازی کلونی مورچهها در مساله زمانبندی کار در محیط ابر جهت مقایسه انتخاب گردیدند.هر دو الگوریتم کلونی مورچگان و جهش قورباغه مبتنی بر جمعیت هستند و مهمترین مزیت آنها نسبت به روشهای قطعی، سرعت حل مساله خصوصا در مسایلی که با حجم زیادی از داده روبرو است میباشد (Misevicius et al.,2013).الگوریتم جهش قورباغه یکی از الگوریتمهای الهام گرفته از طبیعت است که توسط لنزی و یوسف توسعه داده شد، این الگوریتم برای جستجوی محلی میان زیر گروههای قورباغه از روش نموممتیک استفاده می کند (Eusuff et al.,2006) (Huynh,2008).در الگوریتم قورباغه ([5]SFLA) نه تنها در جستجوی محلی بلکه در جستجوی سراسری نیز پیامها مبادله میشوند.بدین ترتیب جستجوی محلی و سراسری به خوبی در این الگوریتم ترکیب میشوند.الگوریتم ژنتیک(GA) و بهینهسازی گروه ذرات(PSO)الگوریتم جهش ترکیبی قورباغه یک الگوریتم بهینهسازی مبتنی بر کولونی است.SFLA قابلیت بالایی برای جستجوی سراسری دارد و پیادهسازی آن آسان است.الگوریتم کلونی مورچهها از هوشجمعی بهره برده و از مهمترین مزایای هوش جمعی می توان به عدم وجود کنترل متمرکز، تعاملات توزیع شده موجودات، سرعت انتقال و کارکرد موازی اشاره نمود.نکتهی دیگر که حائز اهمیت میباشد، توانایی سازگاری مورچهها با تغییرات محیط پیرامونش میباشد. به عنوان مثال زمانی که کوتاهترین مسیر به دلیل وجود یک مانع بسته شده باشد، مورچهها کوتاهترین مسیر جدیدی را پیدا میکنند(Dorigo et al.,2006).هدف اصلي الگوريتمهاي زمانبندي به حداقل رساندن Makespanاست که همان مينيمم ساختن زمان تکميل کل کارها مي باشد. در اين تحقیق سعي شده است زمانبندی وظایف براساس الگوریتم جهش قورباغه در محیط ابر ارائه شود وبا مقايسه دو الگوريتم قورباغه و الگوریتم کلونی مورچه بررسي شود که کدام الگوريتم از نظر بهينهسازي زمان تکميل کل کارها بهينه تر عمل مي کند.