شکل۲-۱٫ ساختار کلی سیستم ۹
شکل۲-۲٫ نحوه نگاشت روش کلونی مورچگان در پردازش شبکه ای ۱۰
شکل ۲-۳- شبه کد الگوریتم ژنتیک ۱۱_Toc390192787
شکل۳-۱. ساختار یک سیستم مبتنی بر عامل برای مدیریت منابع ۱۴
شکل۳-۲٫ ساختار درختی به منظور مدیریت منابع ۱۵
شکل ۳-۳٫ نمایش سناریو کلی برای زمان بندی کارها به صورت چند عامله در پردازش شبکه ای ۱۷
شکل ۳-۴٫ نحوه زمان بندی در روش FIFO ………………………………………………………………………………………………19
شکل۳-۵٫ نمونه ای از واحدها(نشان دهنده هشت درخواست می باشد). ۲۰
شکل ۳-۶٫ شمایی از رابطه میان متا زمان بند و کاربر و زمان بند های محلی موجود در سایت ۲۳
شکل۳-۷٫ ساختار کلی متا زمان بند……………………………………………………………………………………………………………..۲۴
شکل۳-۸٫ مقایسه حالت های ضربی و جمعی در فاکتور ارزیابی ۲۶
شکل ۳-۹٫ساختار خانه های صف ۲۸
شکل ۳-۱۰٫ الگوریتم کلی روش زمانبندی ارائه شده ۳۰
شکل۳-۱۱رابط استفاده شده در روش پیشنهادی …………………………………………………………………………………………..۳۴
شکل۳-۱۲ .شبه کد روش ۳۶
شکل۴-۱٫ ساختار کلی مدل حراج منابع ۳۹
شکل۴-۲٫ نمونه ای از الگوریتم پیشنهادی ۴۱
شکل۴-۳٫ مربوط به یک جراج دو طرفه نمایش داده شده ۴۳
شکل۴-۴٫ ساختار کلی نرم افزار GridSim ۴۶
چکیده
در این پایان نامه به ارائه یک روش جدید در پردازش شبکه ای با الگوریتم مورچگان پرداخته‌ایم. مدلی که در فضای شبکه ای استفاده کردیم حراج دو طرفه پیوسته می باشد. این مدل ها به دلیل سادگی و پویایی خود امروزه در بسیاری از الگوریتم های مورد استفاده برای کنترل منابع و زمان بندی کارها مورد استفاده قرار می گیرند. بسیاری از این مدل ها در زمان پاسخ گویی خود هنگام مدیریت منابع دچار ضعف می باشند. در مدل حراج, حراج کنندگان قیمت های مورد نظر خریداران را اعلام می کنند و خریداری که قیمت مناسب را اعلام کرده باشد منبع را بدست می گیرد. این مساله خود باعث می شود که زمان پاسخ گویی به دلیل درخواست خریداران افزایش یابد. در این پایان نامه ما روش جدیدی را به وسیله الگوریتم ژنتیک در سناریو حراج دو طرفه ارائه کردیم. در این روش با هوشمند سازی منابع, بسته های درخواست پیشنهادی[۱] را به سمتی سوق دادیم هر کدام از این محیط های شبکه ای را می توان به صورت یک سیستم توزیع شده در نظر گرفت که با شبکه های دیگر تعامل ندارد و حجم زیادی از داده را پوشش می دهد. یکی از فواید این روش نسبت به روش کلاسترینگ این است که منابع می تواند از لحاظ جغرافیایی در نقاط پراکنده و به صورت غیر متقارن قرار گیرد. با توجه به توزیع مجموعه های داده، انتخاب مجموعه منابع محاسباتی و منابع حاوی داده باید بطور مناسب صورت پذیرفته به گونه ای که سربار ناشی از انتقال این مجموعه ها روی گرید کمینه شود. در این تحقیق، مساله زمانبندی برنامه های نیازمند داده مورد توجه قرار می گیرد. با توجه به اینکه زمانبندی بهینه مستلزم انتخاب مجموعه منابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به این معنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابع خاموش باشند
پیاده سازی های صورت گرفته در نرم افزار شبیه سازی GridSim مورد بررسی قرار گرفت و نتایج نشان داد که این روش جدید باعث بهبود زمان پردازش و کم شدن تعداد مراحل حراج می شود.
واژه های کلیدی: الگوریتم، شبکه، نرم افزار،call for proposal
-
- مقدمه
مقدمه
هدف اصلی این پایان نامه بهبود بازدهی در پردازش شبکه ای به وسیله الگوریتم مورچگان می باشد. این فصل با طرح مساله اصلی پردازش شبکه ای اغاز می شود و اهمیت آن شرح داده می شود. استفاده از الگوریتم مورچگان در بسیاری از مسایل باعث بهبود بازدهی و کاهش زمان پردازش شده است. این امر زمینه ای را فراهم می آورد تا از این الگوریتم در پردازشبکه ای نیز استفاده شود.
پردازش شبکه ای
پردازش شبکه ای به مجموعه ای از منابع که از چند نقطه مختلف برای انجام یک هدف اقدام به کار می کنند گویند. هر کدام از این محیط های شبکه ای را می توان به صورت یک سیستم توزیع شده در نظر گرفت که با شبکه ای های دیگر تعامل ندارد و حجم زیادی از داده را پوشش می دهد. یکی از فواید این روش نسبت به روش کلاسترینگ این است که منابع می تواند از لحاظ جغرافیایی در نقاط پراکنده و به صورت غیر متقارن قرار گیرد. . با توجه به توزیع مجموعه های داده، انتخاب مجموعه منابع محاسباتی و منابع حاوی داده باید بطور مناسب صورت پذیرفته به گونه ای که سربار ناشی از انتقال این مجموعه ها روی گرید کمینه شود. در این تحقیق، مساله زمانبندی برنامه های نیازمند داده مورد توجه قرار می گیرد. با توجه به اینکه زمانبندی بهینه مستلزم انتخاب مجموعه منابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به این معنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابع خاموش باشند . همچنین در این پردازش ها ممکن است از لحاظ سخت افزاری و نرم افزاری با هم تفاوت داشته باشند.
پردازش شبکه ای دارای معماری های مختلفی می باشد که می توان به موارد زیر اشاره کرد :
-
- GT2
-
- OGSA
-
- GT3
الگوریتم مورچگان
الگوریتم مورچگان یک الگوریتم هیوریستیک با یک جستجوی محلی بهینه می باشد که برای مسایل ترکیبی مورد استفاده می گیرد. این روش از رفتار طبیعی مورچگان الهام گرفته است. در طبیعت مورچگان با ماده ای که از خود ترشع می کنند راه را به بقیه مورچگان نشان می دهند. در بسیاری از پژوهش ها از روش کلونی مورچگان برای حل مسایل NPسخت استفاده می شود. از این روش برای حل مسایلی مانند فروشنده دوره گرد, رنگ امیزی گراف و مسیر یابی استفاده می شود.
شکل۱-۱٫ نحوه حرکت مورچگان در طبیعت
شکل ۱-۲٫ نمونه گراف حاصل از الگوریتم مورچگان
اجتماع مورچگان به مجموعه ای از مورچه های هوشمند گفته می شود که به صورت گروهی رفتار می کنند. این اجتماع در محیط جستجو می کنند تا جواب بهینه را پیدا کنند.
در مساله زمان بندی در محیط های شبکه ای, هر کدام از این کارها به منزله یک مورچه در نظر گرفته می شود. هر کدام از این مورچه ها به دنبال منابع مورد نظر خود حرکت می کنند.
در زیر شبه کد اجتماع مورچگان نشان داده شده است:
Procedure ACO
begin
Initialize the pheromone
while stopping criterion not satisfied do repeat for each ant do Chose next node by applying the state transition rate end for until every ant has build a solution Update the pheromone end while end
روش های متفاوتی برای اجتماع مورچگان وجود دارد که می توان به موارد زیر اشاره کرد :
