بخشی از مقاله
چکیده
در محیطهای توزیع شده با توجه به اینکه عاملها دید کوچکی از سیستم دارند، همکاری نقش× مهمی دارد. در این سیستمها، عاملها فقط از سرویسها یا منابعی که×خودشان و همسایههای مستقیمشان ارائه می کنند، اطلاع دارند. بنابراین آنها برای رسیدن به هدف مورد نظرشان، نیازمند همکاری همسایههای مستقیم خود هستند. با این حال، عاملهای غیرهمکاری وجود دارند که برای اجتناب از صرف هزینه، از پاسخ دادن به درخواستهای عاملهای دیگر خودداری میکنند.
در نتیجه ی زیاد شدن این عاملها بازده سیستم کاهش مییابد. بنابراین، در این مقاله برای ترویج همکاری، روشی جدید ارائه شده است. در روش پیشنهادی، عامل دریافت کنندهی درخواست رفتار غالب در همسایگی خود را تقلید میکند. اگر عدم همکاری تقلید شود، ارتباط با آن قطع و با عامل دیگر بر اساس منطق فازی برقرار میشود. ارتباط جدید با عاملهایی که در گذشته همکارتر و به هدف نزدیکتراند، برقرار میشود.
بنابراین با گذشت زمان رفتار همکارانه غالب شده و توسط عاملهای غیرهمکار تقلید میشود. به این ترتیب همکاری در کل سیستم ترویج مییابد. نتایج نشان میدهد حتی در شرایطی که تعداد غیرهمکار از همکارها بیشتراند، روش پیشنهادی میتواند موجب ترویج همکاری شده و زمان و هزینهی کمتری صرف رسیدن به هدف میشود. ×
-1 مقدمه
در سیستم های توزیع شده ، برای رسیدن به عملکردی که منافع را برای همهی عاملها ارائه کند، همکاری تمام آنها ضروری است. سناریوهایی وجود دارند که همکاری در آنها الزامی است، برای مثال به اشتراک گذاری فایل در سیستمهای نظیر به نظیر .در این سیستمها اگر عاملهای خودخواه تصمیم به همکاری نداشته باشند به عملکرد کل سیستم آسیب میرسانند. مدلهای تکاملی فرهنگی ژنتیکی وجود دارند که تایید میکنند فرصت طلبی در استفاده از دیگران همکاری را تضعیف و اغلب از بین می برد
این مشکلات همکاری به عنوان معضلات اجتماعی ٍشناخته شدهاند. ترویج همکاری در سناریوهایی از این نوع، باعث شده که این زمینه به موضوع مورد توجهی تبدیل شود
همچنین در سیستمهای چند عاملهَ، عاملها به منظور ارسال درخواستهایی برای تعیین محل سرویسها و یا منابع مورد نیازشان نیازمند همکاری همسایههای خود هستند. با توجه به هزینه بر بودن ارسال درخواست، عاملهای خودخواه در همکاری شرکت نمیکنند.×بنابراین اگر مکانیزمی برای مقابله با این عاملها وجود نداشته باشد، عملکرد کل سیستم می تواند به خطر بیافتد.×بنابراین در MAS، وجود مکانیزمهایی جهت تسهیل در ترویج همکاری ضروری است.
در این راستا مقالههایی وجود دارد که تاثیر ساختار شبکه در ترویج همکاری را تحلیل می کنند. همچنین تحقیقاتی صورت گرفته که در آنها چگونگی پارامترهای ساختاری، برای نمونه تاثیر کلاسترینگ یا توزیع درجه، در ترویج و حفظ همکاری بررسی شده است
همچنین تعدادی پژوهش علاوه بر ساختار شبکه، چگونگی تغییرات محلی در ساختار شبکهای رفتارهای دسته جمعی را در نظر گرفتهاند. میدانیم که ساختار به عنوان یک ویژگی مهم در مدلهای همکاری [8] است. بنابراین ارائه مکانیزمی که عاملها بتوانند با گذشت زمان ساختار محلی خود را در شبکه تغییر دهند موثر است. این قابلیت انعطافپذیری اجتماعی [9] نامیده می شود.
در [13] مدلی مبتنی بر بازی معمای زندانی ×[11]در یک شبکهی ادهاک، ارائه شده است. در این مقاله عاملها در مراحل مختلف با استفاده از یک استراتژی تقلید با در نظر گرفتن سود همسایههایشان، رفتارشان را به روز رسانی میکنند. همچنین در [12] به منظور ترویج همکاری، مکانیزمی مبتنی بر اطلاع و برچسبهای متن عاملها ارائه شده است. علاوه بر این، عاملها میتوانند اتصالاتشان را با عاملهایی که همکار نیستند بشکنند و با عاملهای دیگر که می توانند همکاری را بهبود دهند ارتباط برقرار کنند. رویکردهای دیگری وجود دارد که با استفاده از تکنیکهای جایگذاری و مشاهدهی جزئی تسهیل همکاری را ترویج میکنند
همچنین در [14] برای ترویج همکاری در شبکههای نظیر به نظیر از مشوق و مکانیزم زمانبندی مبتنی بر اعتبارات با یک توپولوژی دو سطحی طراحی شده است، و برای انواع مختلف شبکههای محاسباتی اشتراکی، قابل اجرا است.×در برخی از مقالهها از استراتژی مجازات برای ترویج همکاری استفاده کردهاند. برای نمونه در [15] با مجازات عامل-های غیرهمکار، موجب حفظ همکاری در سیستم شده است. همچنین برای ترویج همکاری در فرایند کشف سرویس توزیع شده، از ترکیب تغییر ساختار و مکانیزمهای تشویق استفاده شده است.
در این راستا، در این مقاله، مکانیزمی برای تسهیل در ظهور همکاری پیشنهاد شده است. در این روش عاملها در مراحل مختلف با استفاده از یک استراتژی تقلید با در نظر گرفتن رفتار غالب در همسایگیشان، رفتارشان را به روز رسانی می کنند. در روش پیشنهادی اگر عامل دریافت کنندهی درخواست عدمهمکاری را تقلید کند، ارتباط با آن قطع و با عامل دیگر برقرار میشود.
انتخاب عامل جدید با کمک منطق فازی صورت میگیرد. به این صورت که هر اندازه فاصلهی عامل به هدف مورد نظر نزدیکتر و سابقهی همکاری او در گذشته بیشتر بوده باشد احتمال انتخاب آن بیشتر خواهد بود. اعمال این استراتژی باعث میشود ارتباط با عاملهای غیرهمکار قطع و احتمال برقراری ارتباط با عاملهای همکار بیشتر میشود.
بدین ترتیب رفتار غالب در همسایگی هر عامل همکارانه شده و او نیز همکاری را تقلید خواهد کرد. به این ترتیب در کل سیستم همکاری ترویج پیدا میکند. در نتیجهی کاهش تعداد عاملهای غیرهمکار، طول مسیر رسیدن به هدف و پیامهای تولید شده کاهش مییابد. درنتیجه زمان و هزینهی کمتری صرف فرایند رسیدن به هدف مورد نظر میشود. نتایج نشان میدهد حتی در شرایطی که تعداد عامل-های غیرهمکار بیشتر باشند، روش پیشنهادی می تواند موجب ترویج همکاری شود.
بخشهای بعدی این مقاله به صورت زیر ارائه شده است. در بخش 2، طرح مسئله و در بخش 3 روش پیشنهادی مطرح خواهد شد. بخش 4 نتیجه-ی آزمایشهای انجام شده و در انتها نتیجه گیری ارائه شده است.
-2 طرح مسئله
در سیستمهای توزیع شده فرایند رسیدن به عامل هدف متکی بر همکاری عاملها است. این فرایند زمانی شروع میشود که یک عامل نیازمند پیدا کردن یک عامل است که ارائه کننده ی یک سرویس یا منبع خاص مورد نیاز اوست. فرایند برقراری ارتباط با عاملهای همسایه جهت رسیدن به عامل هدف با ارسال درخواستهای از طرف عامل مبدا آغاز میشود. در طول این فرایند، در ابتدا عامل مبدا درخواستهای را برای یکی از همسایههایش ارسال میکند. اگر عامل دریافت کنندهی درخواست غیرهمکار باشد، درخواست دریافتی را رد میکند. بنابراین عامل مبدا مجبور به ارسال درخواست به همسایههای دیگر خواهد شد. در این فرایند با ارسال هر درخواست تعداد درخواستهای ایجاد شده در سیستم یک واحد افزایش مییابد. روند ارسال درخواست تا رسیدن به عامل هدف ادامه پیدا میکند.
در فرایند رسیدن به هدف، اگر تعداد عاملهایی که تصمیم به عدم-همکاری میگیرند افزایش یابد طول مسیر و پیامهای تولید شده افزایش می-یابد. همچنین تعداد جستجوهایی که پایان موفقیت آمیز دارند کاهش مییابد در نتیجه بازده سیستم پایین خواهد آمد. بدترین حالت زمانی است که طول یک مسیر نزدیک به زمان خاتمه است و هدف مورد نظر پیدا نشده باشد. به همین دلیل، مهم است که به دنبال ارائهی مکانیزمی باشیم که قادر به مقابله با عاملهای غیرهمکار باشد .این مکانیزم باید همکاری را در سیستم، به منظور تضمین عملکرد مناسب سیستم، ترویج و حفظ کند
با توجه به اینکه ساختار به عنوان یک ویژگی مهم در مدلهای همکاری [9] است. بنابراین ارائه مکانیزمی که عاملها بتوانند با گذشت زمان ساختار محلی خود را در شبکه تغییر دهند میتواند موثر باشد.
-3 روش پیشنهادی
در طول فرایند رسیدن به عامل هدف، در ابتدا عامل مبدا درخواستی را برای یکی از همسایههایش که به هدف نزدیکتر است ارسال میکند. اگر عامل غیرهمکار باشد، درخواست دریافتی را رد میکند. در روش پیشنهادی عاملها براساس میزان سودمندیی که عاملهای دیگر میتوانند برایشان فراهم کنند، قادر به تغییر روابط خود با آنها هستند. بنابراین با توجه به سودمند نبودن این لینک برای عامل مبدا تغییر ساختار صورت میگیرد. به این صورت که ارتباط را با این عامل قطع میکند و با عامل دیگر یک لینک جدید برقرار میکند.
اما در روش پیشنهادی در صورتی قطع ارتباط با عامل غیرهمکار صورت میگیرد، که تعداد دفعات عدمهمکاری در عامل دریافت کنندهی درخواست به مقدار آستانهی از پیش تعریف شدهای برسد؟ بنابراین اگر یک عامل همکار به دلیل بالا بودن بار کاری در یک لحظه خاص نتواند درخواست دریافتی را ارسال کند، غیرهمکار در نظر گرفته نمی شود و به آن فرصت بیشتری داده میشود.×اما اگر تعداد دفعات عدمهمکاری بیش از حد آستانه شود، تغییر اتصال صورت گرفته و عامل مورد نظر از مجموعه همسایههای عامل مبدا حذف میشود. در ادامه با توجه به اینکه هر عامل سعی در حفظ تعداد اتصالات خود دارد، با عامل دیگر ارتباطی جدید برقرار میکند. به طور کلی فرایند قطع
ارتباط با عاملهای غیرهمکار و برقراری اتصال جدید با عاملهای دیگر موجب از وجهه افتادن عاملهای غیرهمکار میشود.
اما ایدهی دیگر در این مقاله، مربوط به تصمیم گیری همکاری یا عدم همکاری عاملهای دریافت کنندهی درخواست میباشد. ایدهی ارائه شده به این ترتیب است که عامل دریافت کنندهی درخواست با ارزیابی رفتار همسایه-هایش عمل میکند. به این صورت که عامل مورد نظر رفتار همسایههای مستقیم خود را مورد بررسی قرار داده و برآیند رفتاری آنها را تقلید میکند. به این ترتیب که اگر بیشتر عاملهایی که در همسایگی او قرار دارند همکار باشند، خود نیز تصمیم به همکاری می گیرد و در غیر این صورت او نیز غیرهمکار شده و درخواست دریافتی را رد میکند. در نتیجهی عدم همکاری عامل جاری و با توجه به اینکه در اینجا فرض می شود هر عامل همیشه یک اتصال جدید را میپذیرد، عامل مبدا یک ارتباط جدید برقرار میکند.
در این راستا، معیارهای مختلفی برای ایجاد یک اتصال جدید با عامل دیگر در شبکه وجود دارد. برای نمونه معیار ایجاد یک اتصال با همسایهی همسایه که در [8] ارائه شده است. در بسیاری از پژوهشها نیز اتصال جدید به طور تصادفی صورت میگیرد
اما ×در روش پیشنهادی به طور هوشمندانه، دو معیار برای ایجاد یک اتصال جدید با عامل دیگر در نظر گرفته میشود. یک معیار سابقهی عامل و معیار دیگر میزان فاصلهی عامل از عامل هدف است. برای آنکه بتوان این دو معیار جهت انتخاب اتصال جدید همزمان مورد توجه قرار گیرند، از منطق فازی استفاده میشود. منطق این سیستم فازی بر این اساس است که هر اندازه فاصلهی عامل به هدف مورد نظر نزدیکتر و سابقهی همکاری او در گذشته بیشتر بوده باشد، احتمال انتخاب آن بیشتر خواهد بود. بنابراین در اینجا یک سیستم فازی با دو ورودی و یک خروجی داریم. ورودی اول میزان فاصلهی عامل از عامل هدف و ورودی دوم سابقهی همکاری عامل است. خروجی این سیستم فازی اولویت داده شده به عامل جاری میباشد. شکل ورودیها و خروجی این سیستم فازی در شکلهای 1 تا 3 آورده شدهاند.
در این راستا 9 قانون تعریف میشود که بر این اصل استواراند و در جدول - 1 - آورده شدهاند. نحوهی تنظیم این قوانین به این شکل است که هر اندازه فاصلهی عامل از هدف کمتر و سابقهی همکاری او در گذشته بیشتر بوده باشد، اولویت انتخاب آن بیشتر خواهد بود.
جدول :1قوانین سیستم فازی
غیرفازیساز مورد استفاده در این سیستم میانگین مراکز، موتور استنتاج ممدانی و نوع توابع عضویت آن گوسی میباشد.
شکل: 1 ورودی اول - میزان فاصلهی عامل مورد نظر از عامل هدف -
شکل :2 ورودی دوم - میزان همکاری عامل -
شکل :3 خروجی - میزان اولویت -
برای نشان دادن این روش، نتیجهی اعمال آن روی یک شبکهی ساده در شکل - 4 - آورده شده است. در این سناریو، a عامل مبدا و s عامل هدف است. در اینجا سابقهی عاملها در یک ماتریس نگهداری میشود. به این صورت که هر همکاری با نمرهی - +1 - و عدمهمکاری با نمرهی - -1 - نشان داده میشود و مجموع رفتارهای عامل در گذشته، بیانگر سابقهی همکاری آن است.
در این مثال نیز، عددهای داخل پرانتز کنار عاملها نشان دهندهی میزان همکاری آنها در گذشته میباشد. عامل a فرایند ارسال پیام خود به s را، با ارسال درخواستهای به عامل b آغاز میکند. عامل b به محض دریافت درخواست رفتار همسایههایش را بررسی میکند و با توجه به اینکه رفتار غالب عدم همکاری است او نیز تصمیم به عدم همکاری میگیرد.
با فرض اینکه در این مرحله تعداد فرصتهای داده شده به عامل ×bاز حد آستانه گذشته است، عامل a تصمیم به قطع ارتباط با b و برقراری ارتباط جدید میگیرد. عامل a جهت برقراری ارتباط جدید عاملهای دیگر را مورد بررسی قرار میدهد. بنابراین، عاملی که به هدف نزدیکتر و دارای سابقهی همکاری بیشتری است را به عنوان لینک جدید انتخاب میشود.
