زمانبندی کارها در محاسبات ابری با روش SFLA

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

الگوریتم SFL یک  الگوریتم  ممتیک  متاهیوریستک   است  که  با  این -هدف  طراحی  شده  است  که  راه حل بهینه ی  سراسری  را  از  طریق  جستجوی هیوریستکِ  مطلع  که  بوسیله ی  یک  تابع  هیوریستیک  انجام  می شود، بیابد. این الگوریتم  مبتنی   بر  تکامل  مم هایی  که  توسط  افراد  تعاملی  حمل  می شوند  ومبادله ی  سراسریِ اطلاعات  میان  جمعیت  است .روش های زیادی برای زمانبندی کارها وجود دارد که می توان از الگوریتم های مختلف استفاده نمود.

اما ایده اصلی در این پژوهش این است که زمانبندی وظایف در ابر را با الگوریتم جهش قورباغه shuffled frog leaping algorithm پیاده سازی نمائیم و زمانبندی آن را بهبود بخشیم و مکسپان اش(زمان تکمیل کل انجام کار را مکسپان می گوییم) را کاهش دهیم و با دو ااگوریتم ACO و FCFS مقایسه شود. و در نهایت به این نتیجه رسیدیم که الگوریتم جهش قورباغه نسبت به الگوریتمACOو FCFS سرعت و دقت بیش تری دارد و حاوی مکسپان کمتری می باشد. که قابل ذکر است که برای هر تعداد کار ده بار اجرا شده و میانگین گرفتیم و در نهایت به این نتیجه رسیدیم که الگوریتم جهش قورباغه از لحاظ مکسپان  بهتر عمل می کند.

فهرست مطالب
چکیده    1
فصل اول: کلیات پژوهش    3
۱-۱ مقدمه تعریف    4
۱-۳سابقه وضرورت انجام تحقیق    6
۱-۴ هدف ها    10
۱-۵ جنبه نوآوری تحقیق    10
۱-۶ مراحل انجام تحقیق    10
۱-۷ ساختارپایان نامه    11

فصل دوم:مقدمه ای بر رایانش ابری    12
۲-۱ مقدمه    12
۲-۲ تعریف رایانش ابری    13
۲-۳ سیر تکامل محاسبات    14
۲-۴ عناصر زیربنایی محاسبات    16
۲-۴-۱ محاسبات گرید    16
۲-۴-۲ مجازی سازی    17
۲-۴-۳ وب ۲    17
۲-۴-۴ معماری مبتنی بر سرویس(SOA)    18
۲-۵ سرویس‌های محاسبات ابری    18
۲-۵-۱نرم‌افزار به عنوان سرویس (SaaS)    19
۲-۵-۲   پلتفرم به عنوان سرویس(PaaS)    19
۲-۵-۳ زیر ساخت به عنوان سرویس(IaaS)    19
۲-۶  لایه ماشین مجازی    20
۲-۶-۱  ماشین‌های مجازی    20
۲-۶-۲   ناظر ماشین مجازی    20
۲-۷   لایه مرکز داده    20
۲-۷-۱  سخت افزار    21
۲-۸   مدل های پیاده سازی محاسبات ابری    21
۲-۸-۱  ابر خصوصی    21
۲-۸-۲  ابر عمومی    22
۲-۸-۳  ابر گروهی    22
۲-۸-۴ ابر آمیخته    23
۲-۹ مقدمه ای بر شبیه سازی    23
۲-۱۰ برخی نرم افزارهای شبیه سازی شبکه های محاسباتی    25
۲-۱۰-۱ کلودسیم    25
۲-۱۰-۲ کلود آنالایز    25
۲-۱۰-۳ کلود ریپورتر    25
۲-۱۰-۴ اپ تی آرسیم    25
۲-۱۰-۵ گریدسیم    26
۲-۱۱ آشنایی با ابزار کلودسیم    26
۲-۱۱-۱ کاربردهای کلودسیم    27
۲-۱۱-۲ معماری کلودسیم    28
۲-۱۱-۲-۱ لایه کد کاربر    29
۲-۱۱-۲-۲ لایه کلودسیم    29
۲-۱۱-۲-۳ لایه هسته کلودسیم    30
۲-۱۲ مدل های تخصیص ماشین های مجازی    30
۲-۱۳ کلاس های موجود در کلودسیم    30
۲-۱۴ کلاس پهنای باند    31
۲-۱۵ کلاس کلودلت یا تکه ابر    33
۲-۱۶ کلاس تکه ابر زمانبند    34
۲-۱۷ کلاس مرکز داده    35
۲-۱۸ کلاس مرکز داده واسط    35
۲- ۱۹ کلاس میزبان    35
۲-۲۰ کلاس توپولوژی شبکه    36
۲-۲۱ کلاس ماشین مجازی    36
۲-۲۲ جمع بندی    36

فصل ۳: روش تحقیق 
۳-۱  مقدمه    38
۳-۲  الگوریتم موازنه بار فرصت طلبانه(OLB)    39
۳-۳  الگوریتم زمان اجرا کمینه(MET)    40
۳-۴  الگوریتم زمان اتمام کمینه(MCT)1    40
۳-۵  الگوریتم Min-Min    41
۳-۶  الگوریتم GA    41
۳-۷ الگوریتم گرمایشی(SA)    42
۳-۸  الگوریتم Tabu    43
۳-۹  الگوریتم بهترین درصد (KPB)K    43
۳-۱۰  الگوریتم بهینه سازی اجتماع ذرات(PSO)    44
۳-۱۱  الگوریتم بهینه سازی کلونی مورچگان(ACO)    44
۳-۱۲ الگوریتم ترکیبی جهش قورباغه    48
۳-۱۳مقایسه الگوریتم های اکتشافی    52
۳-۱۴  نتیجه گیری    56

فصل ۴: روش پیشنهادی    57
۴-۱  مقدمه    57
۴-۲بهبود در زمان بندی الگوریتم جهش قورباغه    58
۴-۳ تفاوت در نتایج حاصل از الگوریتم جهش قورباغه و الگوریتمهای دیگر    58
۴-۴ ارائه روش پیشنهادی:    59
۴-۵ جمع بندی:    60

فصل پنجم:آزمایش ها و ارزیابی نتایج    62
۵-۱ مقدمه    62
۵-۲ محیط پیاده سازی و اجرا    63
۵-۲-۱ پارامترها و مقادیر مورد استفاده    64

فصل ششم ۸۰
نتیجه گیری و پیشنهادات    80
۶-۱  مقدمه    80
۶-۲ نتایج حاصل از تحقیق    80
۶-۳ پیشنهادها    81
مراجع:    82
واژه نامه    88

فهرست جدول ها
جدول ۲-۱٫انواع متغیرها و پارامترهای کلاسBw    21
جدول ۲-۲٫متدها و متغیرهای کلاس Cloudlet    22
جدول  3-1.مقایسه الگوریتم های زمانبندی    34
جدول ۵-۱٫پارامترهای استفاده شده در الگوریتم Aco    41
جدول ۵-۲٫پارامترهای استفاده شده در الگوریتم Sfla    41
جدول ۵-۳٫پارامترهای استفاده شده در کلودسیم    42
جدول ۵-۴٫زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۵۰ تسک    43
جدول ۵-۵٫ زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۱۰۰ تسک    43
جدول ۵-۶٫ زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۲۰۰ تسک    44
جدول ۵-۷٫ زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۳۰۰ تسک    45
جدول ۵-۸٫ زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۴۰۰ تسک    45
جدول ۵-۹٫ زمان اجرا هر الگوریتم در محیط ابر با ۱۰ بار اجرا و ۵۰۰ تسک    46
جدول ۵-۱۰٫ کدهای نوشته شده در این پروژه    48
    

فهرست شکل ها
شکل ۲-۱٫ تعریف NISTدر محاسبات ابری    9
شکل ۲-۲٫ سیر تکامل محاسبات    10
شکل ۲-۳٫ معماری جدید CLOUDSIM    19
شکل ۳-۱٫ نمایش مراحل یافتن کوتاهترین مسیر توسط مورچه ها    29
شکل ۳-۲٫ شبه کد الگوریتم کلونی مورچه    30
شکل ۳-۳٫ فلوجارت الگوریتم کلونی مورچه    31
شکل۳-۴٫ فلوچارت الگوریتم Sce-Ua    33
شکل ۵-۱٫ نمودار Aco    47
شکل ۵-۲٫ نمودار Sfla    47
شکل ۵-۳٫ میانگین makespan  از الگوریتم های Sfla، Acoو Fcfs    51