فصل 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)

* نحوه انتخاب والدين
واحد انتخاب کننده به منظور انتخاب دو والد(کروموزوم) براي عمليات برش2 مي باشد. در روش انتخاب از الگوريتم انتخاب رقابتي استفاده شده است. اين روش از ترکيب چند رقابت کوچک تر ميان واحد ها به وجود مي ايد.
3-7- متا زمان بند ها 3به منظور زمان بندي برنامه هاي موازي در حراج هاي دوطرفه در شبکه‌اي هاي جهاني


پاسخی بگذارید