4-3- نحوه پیاده سازی روش های ارایه شده47
4-4- کلاس حراج کننده50
4-5- کلاس مربوط به کاربر52
4-6- کلاس EXAMPLEAUCTION.JAVA54
4-7- کلاس مربوط به منابع حراج (AUCTIONRESOURCE.JAVA)55
فصل 5: نتیجه گیری و پیشنهادات58
منابع74
فهرست اشکال
شکل1-1. نحوه حرکت مورچگان در طبیعت4
شکل 1-2. نمونه گراف حاصل از الگوریتم مورچگان4
شکل2-1. ساختار کلی سیستم9
شکل2-2. نحوه نگاشت روش کلونی مورچگان در پردازش شبکه ای10
شکل 2-3- شبه کد الگوریتم ژنتیک11
شکل3-1. ساختار یک سیستم مبتنی بر عامل برای مدیریت منابع 14
شکل3-2. ساختار درختی به منظور مدیریت منابع15
شکل 3-3. نمایش سناریو کلی برای زمان بندی کارها به صورت چند عامله در پردازش شبکه ای17
شکل 3-4. نحوه زمان بندی در روش FIFO ………………………………………………………………………………………………19
شکل3-5. نمونه ای از واحدها(نشان دهنده هشت درخواست می باشد).20
شکل 3-6. شمایی از رابطه میان متا زمان بند و کاربر و زمان بند های محلی موجود در سایت23
شکل3-7. ساختار کلی متا زمان بند……………………………………………………………………………………………………………..24
شکل3-8. مقایسه حالت های ضربی و جمعی در فاکتور ارزیابی26
شکل 3-9.ساختار خانه های صف28
شکل 3-10. الگوریتم کلی روش زمانبندی ارائه شده30
شکل3-11رابط استفاده شده در روش پیشنهادی …………………………………………………………………………………………..34
شکل3-12 .شبه کد روش36
شکل4-1. ساختار کلی مدل حراج منابع39
شکل4-2. نمونه ای از الگوریتم پیشنهادی41
شکل4-3. مربوط به یک جراج دو طرفه نمایش داده شده43

شکل4-4. ساختار کلی نرم افزار GridSim46
چکیده
در این پایان نامه به ارایه یک روش جدید در پردازش شبکه ای با الگوریتم مورچگان پرداخته‌ایم. مدلی که در فضای شبکه ای استفاده کردیم حراج دو طرفه پیوسته می باشد. این مدل ها به دلیل سادگی و پویایی خود امروزه در بسیاری از الگوریتم های مورد استفاده برای کنترل منابع و زمان بندی کارها مورد استفاده قرار می گیرند. بسیاری از این مدل ها در زمان پاسخ گویی خود هنگام مدیریت منابع دچار ضعف می باشند. در مدل حراج, حراج کنندگان قیمت های مورد نظر خریداران را اعلام می کنند و خریداری که قیمت مناسب را اعلام کرده باشد منبع را بدست می گیرد. این مساله خود باعث می شود که زمان پاسخ گویی به دلیل درخواست خریداران افزایش یابد. در این پایان نامه ما روش جدیدی را به وسیله الگوریتم ژنتیک در سناریو حراج دو طرفه ارایه کردیم. در این روش با هوشمند سازی منابع, بسته های درخواست پیشنهادی1 را به سمتی سوق دادیم هر کدام از این محیط های شبکه ای را می توان به صورت یک سیستم توزیع شده در نظر گرفت که با شبکه های دیگر تعامل ندارد و حجم زیادی از داده را پوشش می دهد. یکی از فواید این روش نسبت به روش کلاسترینگ این است که منابع می تواند از لحاظ جغرافیایی در نقاط پراکنده و به صورت غیر متقارن قرار گیرد. با توجه به توزیع مجموعه های داده، انتخاب مجموعه منابع محاسباتی و منابع حاوی داده باید بطور مناسب صورت پذیرفته به گونه ای که سربار ناشی از انتقال این مجموعه ها روی گرید کمینه شود. در این تحقیق، مساله زمانبندی برنامه های نیازمند داده مورد توجه قرار می گیرد. با توجه به اینکه زمانبندی بهینه مستلزم انتخاب مجموعه منابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به این معنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابع خاموش باشند
پیاده سازی های صورت گرفته در نرم افزار شبیه سازی GridSim مورد بررسی قرار گرفت و نتایج نشان داد که این روش جدید باعث بهبود زمان پردازش و کم شدن تعداد مراحل حراج می شود.
واژه های کلیدی: الگوریتم، شبکه، نرم افزار،call for proposal
فصل 1:
مقدمه
1-1- مقدمه
هدف اصلی این پایان نامه بهبود بازدهی در پردازش شبکه ای به وسیله الگوریتم مورچگان می باشد. این فصل با طرح مساله اصلی پردازش شبکه ای اغاز می شود و اهمیت آن شرح داده می شود. استفاده از الگوریتم مورچگان در بسیاری از مسایل باعث بهبود بازدهی و کاهش زمان پردازش شده است. این امر زمینه ای را فراهم می آورد تا از این الگوریتم در پردازشبکه ای نیز استفاده شود.
1-2- پردازش شبکه ای
پردازش شبکه ای به مجموعه ای از منابع که از چند نقطه مختلف برای انجام یک هدف اقدام به کار می کنند گویند. هر کدام از این محیط های شبکه ای را می توان به صورت یک سیستم توزیع شده در نظر گرفت که با شبکه ای های دیگر تعامل ندارد و حجم زیادی از داده را پوشش می دهد. یکی از فواید این روش نسبت به روش کلاسترینگ این است که منابع می تواند از لحاظ جغرافیایی در نقاط پراکنده و به صورت غیر متقارن قرار گیرد. . با توجه به توزیع مجموعه های داده، انتخاب مجموعه منابع محاسباتی و منابع حاوی داده باید بطور مناسب صورت پذیرفته به گونه ای که سربار ناشی از انتقال این مجموعه ها روی گرید کمینه شود. در این تحقیق، مساله زمانبندی برنامه های نیازمند داده مورد توجه قرار می گیرد. با توجه به اینکه زمانبندی بهینه مستلزم انتخاب مجموعه منابع مناسب می باشد. در پردازش های شبکه ای ,محیط ها پویا می باشند به این معنا که ممکن است در یک زمان منابع روشن باشد و در زمانی دیگر همان منابع خاموش باشند . همچنین در این پردازش ها ممکن است از لحاظ سخت افزاری و نرم افزاری با هم تفاوت داشته باشند.
پردازش شبکه ای دارای معماری های مختلفی می باشد که می توان به موارد زیر اشاره کرد :
* GT2
* OGSA
* GT3
1-3- الگوریتم مورچگان
الگوریتم مورچگان یک الگوریتم هیوریستیک با یک جستجوی محلی بهینه می باشد که برای مسایل ترکیبی مورد استفاده می گیرد. این روش از رفتار طبیعی مورچگان الهام گرفته است. در طبیعت مورچگان با ماده ای که از خود ترشع می کنند راه را به بقیه مورچگان نشان می دهند. در بسیاری از پژوهش ها از روش کلونی مورچگان برای حل مسایل NPسخت استفاده می شود. از این روش برای حل مسایلی مانند فروشنده دوره گرد, رنگ امیزی گراف و مسیر یابی استفاده می شود.
شکل1-1. نحوه حرکت مورچگان در طبیعت
شکل 1-2. نمونه گراف حاصل از الگوریتم مورچگان
اجتماع مورچگان به مجموعه ای از مورچه های هوشمند گفته می شود که به صورت گروهی رفتار می کنند. این اجتماع در محیط جستجو می کنند تا جواب بهینه را پیدا کنند.
در مساله زمان بندی در محیط های شبکه ای, هر کدام از این کارها به منزله یک مورچه در نظر گرفته می شود. هر کدام از این مورچه ها به دنبال منابع مورد نظر خود حرکت می کنند.
در زیر شبه کد اجتماع مورچگان نشان داده شده است:
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
روش های متفاوتی برای اجتماع مورچگان وجود دارد که می توان به موارد زیر اشاره کرد :
* Max-Min Ant System
* Rank-based Ant System
* Fast Ant System
* Elitist Ant System
1-4- چالش های پردازش شبکه ای
از چالش مهم در پردازش های شبکه ای می توان به نحوه اولویت بندی و زمان بندی به پردازه ها اشاره کرد. مساله زمان بندی در پردازش های شبکه ای از سه بخش تشکیل می شود :
1. پیدا کردن منابع که شامل منابعی است قابلیت استفاده را دارند
2. جمع اوری اطلاعات درباره این منابع و انتخاب بهترین مجموعه از منابع
3. کارها در این مرحله انجام می شود
مرحله پیدا کردن مجموعه بهترین منابع یکی از مسایل NP-Complete می باشد. در زمان بندی کارها دو هدف عمده وجود دارد :
1. بیشترین میزان کارایی را سیستم داشته باشد
2. بیشترین خروجی را داشته باشد
برای هدف اول, باید روشی ارایه شود که زمان پردازش را کاهش دهد و برای هدف دوم, باید روشی ارایه شود که زمان بندی را به مجموعه ای از کارهای مستقل از هم تقسیم کند. این کار باعث می شود که ظرفیت انجام کار سیستم در واحد زمان افزایش یابد.
برای حل این مشکل روش های متفاوتی ارایه شده است. یکی از این روش ها نگاشت این مساله به مساله فروشنده دوره گرد می باشد. در این روش مسیر هایی که منابع نسبت به هم دارند مهم می باشد. در پردازش شبکه ای به دلیل اینکه منابع در فواصل متفاوت و غیر متقارن نسبت به هم قرار دارند به همین دلیل در مواردی این روش می تواند مفید عمل کند.
در ادامه این پژوهش مطالب به صورت زیر ارائه گردیده است.
در فصل دوم به پیش زمینه های مربوطه پرداخته ایم و کلیات روش های زمانبندی به مورچه، ژنتیک و حراج پرداخته شده است.
در فصل سوم مهمترین الگوریتم ها و روشهای پیاده سازی شده در بستر? الگوریتم های زمان بندی ارائه گردیده است.
در فصل چهارم به ارائه روش پیشنهادی می پردازیم و نتایج شبیه سازی روش پیشنهادی (Acdanp) با روش قبلی مورد ارزیابی و مقایسه قرار می گیرد.
در فصل پنجم به ارائه پیشنهادات و کارهای آتی می پردازیم. ضمناً در پیوست الف کد سورس نوشته شده در محیطی Gridsim آورده شده است.
فصل 2:
پیش زمینه تحقیق
2-1- مروری بر الگوریتم های و روش ها
در این بخش به مروری بر کارهای انجام شده در پردازش های شبکه ای می پردازیم. ابتدا به توضیح در مورد روش های اولیه مانند Dynamic level schedulingو سپس به روش های اخیر استفاده شده در این زمینه می پردازیم.
2-2- زمان بندی چندسطحی پویا
در این روش هدف انتخاب بهترین دوتایی زیرکار و ماشین برای زمان بندی می باشد[1]. برای انجام عمل بیان شده یک مدل خاص ارایه شده است. هدف کلی در این روش,کاهش زمان پردازش برنامه می باشد. در محیط های پردازش شبکه ای, الگوریتم های زمان بندی دیگر بر روی زیر کارهای یک برنامه که در میزبان محاسبه گر یا سازمان مجازی اجرا می شود تاکید ندارند . هدف اصلی, زمان بندی به صورتی است که تمامی برنامه های ورودی بتوانند از توان موجود استفاده کنند.
در مقاله [2]با اضافه کردن هیوریستیک به روش ذکر شده,سعی در افزایش کارایی سیستم داشته اند.
2-3- اختصاص سریعترین پردازنده به بزرگترین کار
الگوریتم زمان بندی FPLTF [3]کارها را بر اساس منابعی که در سیستم برای انجام ان وجود تعیین می شود. این روش به دو پارامتر سرعت پردازنده و منابع و حجم کار بستگی دارد. در این روش بزرگترین کار به سریع ترین منبع تعلق می گیرد. اگر تعداد زیادی از کارهای با حجم زیاد وجود داشته باشد, انگاه این روش دارای کارایی بسیار پایین می باشد.
روش FPLTF پویا[4] با توجه به روش استاتیک FPLTF توسعه یافته است. در این روش بالاترین اولویت را به بزرگترین کار داده می شود. در این روش باید داده هایی که برای پردازش لازم است تخمین زده شود.
2-4- صف کارها با تکرار(WQR)
این روش بر مبنای روش WQ می باشد. این روش پردازنده های سریع تر را به کارهایی که حجم زیادی دارند تعلق می گیرد[5]. روش زمان بندی که در این روش استفاده می شود FCFSو رندوم می باشد. WQRکارها را به منظور انتقال به منابع قابل دسترس تکرار می کند. میزان تکرار کارها می تواند توسط کاربر انتخاب شود. هنگامی که یکی از این تکرار ها تمام شد, الگوریتم زمان بندی تکرار بقیه کارها را قطع می کند. یکی از مشکلات این روش زمان زیادی است که برای اختصاص منابع برای عملیات تکرار صورت می گیرد.
2-5- الگوریتم اجتماع مورچگان تعادلی(BACO)
ایده اصلی این روش از روش اجتماع مورچگان گرفته شده است[3]. هدف اصلی این روش کاهش زمان پردازش و میزان بار هر کدام از منابع است. این روش میزان چگالی فرمون را بر اساس وضعیت منابع تغییر می دهد. این کار با به روز رسانی فرمون به صورت محلی و کلی انجام می شود. در این روش با کوتاه کردن زمان پایان کارها, در عین حال که سیستم را در حال تعادلی پردازش نگه می دارد. معماری این زمان بندی پردازش شبکه ای به صورت زیر می باشد. چهار مورد از اجزا به صورت زیر می باشد: پورتال, سرور اطلاعات, الگوریتم زمان بندی کارها و منابع مورد نیاز پردازش. این پورتال به منظور یک رابط برای انجام کارها برای کاربرها استفاده می شود. (در شکل 2-1- ساختار کلی سیستم آمده است)
شکل2-1. ساختار کلی سیستم
سرور اطلاعات به وسیله سرویس شبکه هواشناسی(NWS)[6]اطلاعات در مورد منابع را جمع اوری می کند. پردازهNWSدر بازه های زمانی معین داده ها را به سرور های داده بازمی گرداند. الگوریتم زمان بندی نیز به وسیله روش BACOانجام می شود. در روش BACOیک مورچه یک کار در پردازش شبکه ای می باشد.فرمون یک مسیر, هزینه استفاده از منبع در پردازش می باشد.
شکل 2-2 نشان دهنده نگاشت انجام شده بین سیستم اجتماع مورچگان و پردازش شبکه‌ای می‌باشد.
شکل2-2. نحوه نگاشت روش کلونی مورچگان در پردازش شبکه ای
مقدار فرمول مربوط به هر منبع از رابطه (2-1) بدست می آید :
(2-1)
همچنین در این روش از فرمون کلی برای مشاهده تغییرات وضعیت شبکه و منابع استفاده می شود.
2-6- روش الگوریتم ژنتیک در پردازش شبکه ای
این روش ابتدا در مقاله (Braun et al.,2001)مورد بررسی قرار گرفت.علاوه بر این روش نیز کارهای بسیاری در زمینه ژنتیک الگوریتم در پردازش شبکه ای استفاده شده است.[7, 8, 9] در این روش کارها به صورت کروموزوم در نظر گرفته می شود. هر کدام از این کروموزوم ها می تواند جواب مساله مورد نظر باشد. هر کروموزوم لیستی از nعنصر می باشد که مکان i در این لیست نشان دهنده کار iام می باشد. همچنین مقدار هر کدام از این عناصر بین 1 تا m می باشد که نشان دهنده پردازنده اختصاص یافته به این کار می باشد. مراحل اصلی این الگوریتم به صورت زیر می باشد:
1. در ابتدا یک جمعیت با تعداد مشخصی از کروموزوم ها تولید می شود.
2. یک تابع ارزیابی در این مرحله کروموزوم ها ارزش دهی می کند.
3. در این مرحله دوباره به تولید جمعیتی می پردازیم با این تفاوت که کروموزوم هایی که دارای ارزش بیشتری هستند انتخاب می شوند. همچنین از دو عمل کراس اور و ترکیب برای ایجاد واگرایی در جمعیت نیز استفاده می شود.
4. تا زمانی که جواب مورد نظر بدست نیامده است دوباره از مرحله 2الگوریتم تکرار می شود.
در زیر شبه کد مربوط به ژنتیک الگوریتم نشان داده شده است.
begin
Initialization: Generate the inpopulation P(t=0) of n individuals
Fitness: Evaluate the fitness of each individual of the population. Evaluate (P(t))
While (not termination condition) do
Selection: Select a subset of m pairs from P(t). Let P1(t) = Select (P(t)).
Crossover: With probability pc , cross each of the m chosen pairs.
Let P2(t) = Cross (P1(t)) be the set of offsprings.
Mutation: With probability pm , nutate each offsprings in P2(t).
Let P3(t) = Mutate (P2(t)).

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

Fitness: Evaluate the fitness of each offspring. Evaluate (P3(t)).
Replacement: Create a new generation from individuals in P(t) and P3(t).
Let P(t+1) = Replace(P(t),P3(t)) ; t = t + 1.
fwhile
return Best found solution;
end
شکل 2-3- شبه کد الگوریتم ژنتیک
آخر فصل سوم یک جدول مقایسه ای شامل روشهای مطرح شده ویژگیهای مزایای و معایب آنها درج می شود مثلاً کاربرد در پردازش شبکه ای کاربرد در سیستم Clint serverو هزینه پردازشی مثلاً پیچیدگی محاسباتی
فصل 3:
پیشینه تحقیق
3-1- یک سیستم مبتنی بر عامل برای مدیریت منابع( ARMS)
یکی از مسایل مورد بحث در پردازش شبکه ای مدیریت منابع می باشد. مقیاس پذیری و قابلیت سازگاری در سیستم ها نیز از موارد مهم در طراحی سیستم ها می باشد. در این پژوهش یک سیستم مبتنی بر عامل برای مدیریت منابع در پردازش شبکه ای ارایه شده است. در این روش یک سلسله مراتبی از عامل ها برای ایجاد قابلیت سازگاری و مقیاس پذیری استفاده شده است[10]. در این روش عامل ها قابلیت انتقال اطلاعات و تعامل با یکدیگر را دارا می باشند.
شکل3-1. ساختار یک سیستم مبتنی بر عامل برای مدیریت منابع( ARMS) [10]
ساختار عامل ها در ARMSدر شکل 3-1 نشان داده شده است. هر لایه دارای ماژول های متفاوت و متعدد می باشد. در این شکل همچنین سه کار مهم توسط عامل ها انجام می شود :
1. اگاهی دادن برای انجام دادن یک سرویس
2. یافتن سرویس ها
3. اجرای برنامه
لایه ارتباط در این معماری وظیفه برقراری ارتباط با عامل ها را بر عهده دارد. این لایه مانند یک واسط میانی بین عامل ها و محیط خارج عمل می کند. در این لایه عامل اطلاعات در مورد اعلان های سرویس و یافتن منابع نیز انجام می شود.
چهار عامل برای قرار دادن یک عامل در یک لایه وجود دارد :
1. کنترل کننده ACT
2. موتور ارزیابی PACE
3. الگوریتم زمان بندی
4. زوج یاب
در شکل 3-2 نحوه مدیریت منابع توسط عمل ها نشان داده شده است.
شکل3-2. ساختار درختی به منظور مدیریت منابع
3-2- روش پیوندی مورچگان به منظور زمان بندی کارهای مستقل در محیط های ناهمگن پردازشی
این روش از ترکیب الگوریتم اجتماع مورچگان و جستجوی های محلی و تابو تشکیل شده است[11]. هر مورچه در این روش جواب خود را با توجه به اطلاعات ذخیره شده در دنباله فرمون و تابع هیوریستیک خود بدست می آورد. هر مورچه کار خود را در ابتدا بدون زمان بندی و با پردازنده به انجام کارها می پردازد. یک کار مانند j به صورت احتمالی برای زمان بندی با توجه به رابطه(3-1) قابل انتخاب می باشد :

(3-1)
در این رابطه ? پارامتری است که برای تعریف میزان ارتباط اطلاعات فرمون استفاده می شود. ? نیز تعریف گر وزن ارتباطی با اطلاعات هیوریستیک می باشد. کاری که با توجه به فرمول بالا انتخاب می شود, به لیست کارها اضافه می شود. این عمل تا زمانی که تمامی کارها زمان بندی نشده اند ادامه پیدا می کند. در بسیاری از پژوهش ها مساله ترکیب الگوریتم اجتماع مورچگان و الگوریتم های جستجوی محلی مطرح شده است. الگوریتم های جستجوی محلی در بسیاری از شرایط باعث افزایش کارایی سیستم می شوند. جستجو های محلی به سرعت و با تاثیر به سزایایی جواب ها را بهبود می دهند. یکی از این الگوریتم ها , الگوریتم تابو می باشد. در این روش سعی بر این شده است که از مکان هایی که باعث مشکل مینیمم محلی می شود دوری شود. این عمل با در دست داشتن لیستی به نام تابو لیست که نقاط قبلی که دیده شده است در ان وجود دارد صورت می گیرد. علاوه بر موارد ذکر شده, جستجوی تابو نتایج خوبی را در کنار روش اجتماع مورچگان نشان داده است.
پارامتر موثری که جستجوی تابو در الگوریتم مورچگان دارد nTrial می باشد. nTrial تعداد ازمایش های انجام شده در فاز جستجوی تابو است. نتایج نشان داده است که تعداد ازمایش با اندازه 1000این اجازه را می دهد تا این الگوریتم جستجو بهترین نتیجه را داشته باشد.
روش دیگری نیز در مقاله [12] با ترکیب الگوریتم ژنتیک و جستجوی محلی ارایه شده است.
3-3- در اختیار گرفتن منابع در پردازش شبکه ای به وسیله الگوریتم یادگیری تقویتی
روش یادگیری تقویتی در بهبود بسیاری از مسایل در پردازش شبکه ای استفاده شده است[13,14]. یکی از مسایل مهم در پردازش شبکه ای نحوه در اختیار گرفتن منابع مانند پردازنده, پهنای باند شبکه و غیره به صورت مفید و سودمند می باشد. با توجه به این نکته که وجود یک کنترل کننده مرکزی نمی تواند سودمند باشد و منابع به صورت پویا در شبکه حضور دارند یا ندارند. به همین کنترل در این سیستم ها را به صورت توزیع شده قرار می دهند. در این روش یک سیستم به صورت مجموعه زیادی از عامل های ناهمگون یادگیرنده در نظر گرفته می شود. همچنین این عامل ها در صورت نیاز منابع خود را نیز با یکدیگر به اشتراک می گذارند. در این پژوهش برای سادگی مساله تنها منبع مورد نیاز برای پردازش را پردازنده درنظر گرفته است[15].
منابع بر اساس سرعت پردازش شان شناخته می شوند. همچنین در این سیستم قابلیت اجرای چند کار را با هم دارد. در شکل 3-3 ساختار کلی سیستم نشان داده شده است.
شکل 3-3. نمایش سناریو کلی برای زمان بندی کارها به صورت چند عامله در پردازش شبکه ای
هر عامل دارای یک مقدار Qمی باشد که بیانگر کارایی ان در گذشته بوده است. در ابتدا عامل ها به صورت رندوم و غیر قطعی کارهای خود را انتخاب می کنند. سپس برای هر کار جدید, عامل ها بر اساس الگوریتم حریصانه, منبعی که بیش ترین Q را دارد انتخاب می کنند. تابع ارزیابی مقدار Q به در رابطه 3-2 می باشد :
(3-2)
قابل ذکر است که سیاستی که بر روی انتخاب منابع قرار دارد نیز بسیار تاثیر گذار است. اگر در این سیستم منابعی که دارای حافظه زیاد باشند در اولویت باشند انگاه ممکن است که کارایی سیستم نسبت به حالتی که سرعت پردازنده مهم است کمتر باشد.
3-4- روش‌تجربی مورچگان به وسیله تخصیص منابع با روش‌اشتراک‌زمانی در پردازش شبکه‌ای
مراحل اصلی در این روش[16] به شرح زیر است:
1- برای هر منبع جدیدی که در سرور های اطلاعاتی قرار می گیرد فرمول آن با رابطه (3-3) حساب می شود(با فرض اینکه تعداد کارها A و این مجموعه کارها در لیستی به نام T قرار داشته باشد. تعداد منابع نیز برابر است با Q) :
Ip(0) = (N*M) + Communication speed (3-3)
که Ip (0) مقدار اولیه فرمون می باشد. N تعداد عناصر پردازنده است. M نرخ پردازشی عناصر پردازنده است.
1- مراحل 3 تا 6 را تکرار کن تا مجموعه Tبرابر با تهی شود.
2- انتخاب کار t از مجموعه کارهای T
3- مشخص کردن منبع Rj برای کار t که دارای احتمال بالاتر برای انجام می باشد. احتمال انتخاب این منابع از رابطه (3-4) محاسبه می شود :
(3-4)
در این فرمول j و r منابع در دسترس می باشند.
rc هزینه استفاده از منابع می باشد.
Cp(t)اشاره به مقدار فرمون منبع دارد.
4- زمان بندی کار t برای منبع Rj و حذف ان از لیست T
5- به روز رسانی فرمون. برای هر منبع rj یک فرمون با توجه به رابطه 3-5 زیر اختصاص می یابد :
CpjNew = pd*Cpjold + ?j (3-5)
?j = -c C =میزان دشواری کار
3-5- پیک روش حراج دو طرفه پیوسته به منظور در اختیار گذاشتن منابع در پردازش شبکه‌ای
در این روش دو عامل مهم وجود دارد. منابع که به عنوان فراهم کنندگان در نظر گرفته می شوند و همچنین کاربرها هم عامل های خریدکننده می باشند[17]. هر کدام از عامل های فراهم اورنده منبع بر اساس دو عامل هزینه لازم را پیشنهاد می دهند :
* حجم کار
* توان پردازشی
عامل های خریدکننده نیز بر اساس دو عامل زیر هزینه ای را که می خواهند پرداخت کنند ارزیابی می کنند :
* زمان باقی مانده برای دادن پیشنهاد
* تعداد منابع باقی مانده
عناصر اصلی این مساله تعداد منابع (m), تعداد کاربر(k)و تعداد کارها(n) است.
مالکان منابع در این روش قابلیت همکاری با یکدیگر را دارند. در هر زمان نیز تنها می توانند یک کار را انجام بدهند و از روش First In First Outبه منظور بررسی درخواست ها استفاده می کند.
در شکل 3-4 چگونگی زمان بندی در این روش نمایش داده شده است.
شکل 3-4. نحوه زمان بندی در روش FIFO
رابطه (3-6) برای محاسبه مقدار پیشنهادی کاربر مورد استفاده قرار می گیرد :
(3-6)

? بین مقدار 0.01 و 100 می باشد. rmin حداقل هزینه مورد نظر برای در اختیار گرفتن منبع, Nti تعداد منابع باقی مانده در زمان t برای کار Ji و همچنین این نکته قابل ذکر است که در این فرمول اگر 1>? مشتری ها کمترین هزینه را نشان می دهند تا تعداد منابع به صفر گرایش پیدا کند و به ازای 1<? مشتری ها (خریدار) پیشنهاد های خود را با هزینه نزدیک به i? ارایه می دهند.
3-6- ترکیبی از الگوریتم های ژنتیک به منظور حل مساله یافتن برنده حراج در حراج دو طرفه
فرض کنید که یک حراج کننده یک مجموعه ای از عناصر را می خواهد به فروش بگذارد. خرید کنندگان برای مجموعه این عناصر درخواست خود را ارسال می کنند. حراج کنندگان نیز با در نظر گرفتن قوانین و محدودیت ها عناصر را در اختیار خریداران قرار می دهند.
در این روش[18] بخش های مرتبط با الگوریتم ژنتیک به صورت زیر فرض و پیاده سازی شده اند :
* نحوه نشان دادن هر کدام از واحد ها(کروموزوم ها)
یک کروموزوم به وسیله یک وکتور باینری با اندازه تعداد درخواست ها مشخص می شود. اگر هر عضو کروموزوم یک باشد به این معنا است که قبول شده است و اگر برابر با صفر باشد یعنی با این درخواست موافقت صورت نگرفته است. شکل 3-5 نشان دهنده یکی از این واحد ها می باشد:
11010110شکل3-5. نمونه ای از واحدها(نشان دهنده هشت درخواست می باشد).
* تابع ارزیابی
ارزیابی هر کدام از این واحد ها از طریق جمع هزینه های درخواست هایی که برنده شده اند حاصل می گردد. رابطه (3-7) بیان گر همین مطلب می باشد :
(3-7)

* نحوه انتخاب والدین

دسته بندی : پایان نامه ها

پاسخ دهید