وبلاگ

۳-۵- روش‌های پیشنهادی
از آن‌جایی که یکی از مهم‌ترین مسائل در بازی‌های همکارانه، چگونگی تقسیم دارایی کل میان بازیکنان حاضر در بازی است و راهکارهای این‌گونه بازی‌ها می‌توانند سهم هر بازیکن از کل دارایی را تعیین کنند، برای حل مسئله‌ی تخصیص پهنای باند کلی در شبکه‌ی فیبر نوری غیرفعال اترنت میان واحدهای شبکه‌ی نوری، از این راهکارها بهره گرفته‌ایم. بدین معنا که چالش تخصیص پهنای باند در دسترس ترمینال خط نوری به عنوان یک بازی همکارانه‌ی در نظر گرفته شده است. واحدهای شبکه‌ی نوری، بازیکنان این بازی هستند که می‌توانند در جهت به دست آوردن سهم مناسب، به جای رقابت با یکدیگر به طرق مختلف ائتلاف تشکیل داده و با یکدیگر همکاری کنند. در واقع برابر تعداد این واحدها است و ائتلافی که تمامی واحدها در آن عضو باشند، ائتلاف بزرگ نام دارد. منظور از ائتلاف پیروز در روش‌های پیشنهادی، ائتلافی است که به تمامی واحدهای عضو آن، سهمی از پهنای باند تعلق می‌گیرد و در مقابل به اعضای ائتلاف بازنده هیچ سهمی داده نمی‌شود. تابع مشخصه‌ی v نیز در هر کدام از روش‌ها براساس راهکار مورد استفاده، تعریف شده است و معادل سهم پهنای باند ائتلاف است. ماحصل هر کدام از روش‌های ارائه شده، بردار تخصیص است که عنصر معادل سهم واحد شبکه‌ی نوری از کل پهنای باند است. با توجه به توضیحات مطروحه، فرضیات زیر برقرارند:

• • مسئله‌ی تخصیص منبع پهنای باند در شبکه‌ی فیبر نوری غیرفعال اترنت مشابه مسئله‌ی تقسیم دارایی کل میان بازیکنان متقاضی و مدعی آن در بازی‌های همکارانه در نظر گرفته شده است.

• • N تعداد واحدهای شبکه‌ی نوری موجود در شبکه‌ی فیبر نوری غیرفعال اترنت برابر تعداد بازیکنان در بازی همکارانه است.

• • واحدهای شبکه‌ی نوری می‌توانند به طرق مختلف یک ائتلاف تشکیل داده و با هم همکاری کنند.

• • ائتلاف بزرگ ائتلافی است که تمامی واحدهای شبکه‌ی نوری در آن عضو هستند.

• • ائتلاف‌ها ممکن است برنده یا بازنده باشند. به ائتلافی برنده گفته می‌شود که به تمامی اعضای آن، سهمی از پهنای باند تعلق می‌گیرد و این تعریف در مورد ائتلاف‌های بازنده بالعکس است.

• • تابع مشخصه‌ی تعیین کننده‌ی میزان سهم ائتلاف C از پهنای باند است.

• • بردار تخصیص ) به عنوان خروجی هرکدام از روش‌های پیشنهادی، میزان سهم هر واحد شبکه‌ی نوری را از پهنای باند تعیین می‌کند.

۳-۵-۱- روش اول: دیکه
در فرهنگ یونان باستان، Dike نشانه عدالت، انصاف و درستی، روح نظم و قضاوت عادلانه است. از آن جایی که هدف این روش پیشنهادی، تخصیص پهنای باند به گونه‌ای عادلانه و منصفانه میان واحدهاست، این گونه نام‌گذاری شده است. در این روش از الگوی مقدار شپلی برای یافتن سهم هر بازیکن از منفعت کل استفاده می‌کنیم. بدین ترتیب که واحدهای شبکه‌ی نوری بعنوان بازیکنان یک بازی همکارانه در نظر گرفته می‌شوند که به جای رقابت با یکدیگر برای دستیابی به سهم بیش‌تر از منبع پهنای باند، با هم همکاری کرده و ائتلاف تشکیل می‌دهند. گام‌های این روش را می‌توان به شکل زیر در نظر گرفت:
۱- کاربران هر شبکه‌ی نوری درخواست‌های خود برای داده، تصویر، صوت و … را به واحد نوری مربوطه ارسال می‌کنند و درخواست‌ها در بافر این واحد ذخیره می‌گردد. لذا مجموع پهنای باند موردنیاز هر واحد شبکه‌ی نوری برای تامین درخواست‌های کاربران آن واحد، برابر است با معادله (۳-۱۱) :
(۳-۱۱) =
که در آن درخواست پهنای باند (پهنای باند موردنیاز) کاربر است که به واحد ارسال شده است و تعداد کاربران متصل به واحد است. لذا به ازای تمامی واحدهای شبکه‌ی نوری یا همان بازیکن بازی همکارانه خواهیم داشت . باید این نکته را متذکر شد که در صورتی که یک واحد تقاضای پهنای باندی بیش‌تر از کل پهنای باند در دسترس ترمینال را داشته باشد، برابر کل پهنای باند موجود یعنی قرار می‌گیرد.
۲- ترمینال جهت محاسبه‌ی سهم هر واحد از کل پهنای باند در دسترس، براساس تعداد واحدها () و پهنای باند موردنیاز آن‌ها ()، جدولی به نام جدول اتحاد^[۱۴۴] تشکیل می‌دهد. این جدول دارای سطر و ستون است. تعداد تمام اتحادهایی است که واحد می‌توانند تشکیل دهند و از آن‌جایی‌که یکی از اتحادها تهی است، اتحاد تهی از مجموع تعداد اتحادها حذف شده است. ستون‌های جدول اتحاد به ترتیب شامل موارد زیر می‌باشند:
ستون اول: شامل تمامی اتحادها^[۱۴۵]
ستون دوم: شامل تمامی مقادیر یا ارزش اتحادها^[۱۴۶]
ستون سوم تا آخر: سهم مرزی هر کدام از واحدها^[۱۴۷]
۳- پس از تشکیل جدول اتحاد، ترمینال باید تمامی ستون‌های این جدول را به ترتیب نام‌برده پر نماید. ستون اول جدول شامل عدد باینری رقمی است که نشان دهنده‌ی اتحادهای متفاوت میان واحدها می‌باشند بدین ترتیب که رقم اُم از سمت چپ در عدد باینری رقمی نشان دهنده‌ی حضور یا عدم حضور در اتحادِ است. برای مثال اگر ONU₁ در اتحادِ C حضور داشته باشد، رقم اول از سمت چپ یک و در غیر این صورت صفر خواهد بود. به همین ترتیب اگر عضو اتحاد باشد، رقم اُم از سمت چپ یک و در غیر این صورت صفر است. منظور از ائتلاف یا اتحاد‌های متفاوت در این روش، گروه‌های مختلفی از واحدهاست که برای تخصیص پهنای باند کلی در اختیار ترمینال، انتخاب می‌شوند و ائتلاف بزرگ به معنای تخصیص پهنای باند میان تمامی واحدهای موجود در شبکه است.
۴- ستون دوم این جدول نشان ‌دهنده‌ی مقدار اتحاد مربوط به هر اتحاد در ستون اول است، بدین معنا که هر المان از این ستون، مقدار متناظر با اتحادی که در ستون اول با عدد باینری مشخص شده است را براساس واحدهای شرکت کننده در آن اتحاد براساس معادله (۳-۱۲) تعیین می‌کند.
(۳-۱۲)
در واقع تابع مشخصه‌ی بازی همکارانه است. هدف از تعریف تابع مشخصه، تعیین میزان سودی است که هر بازیکن از شرکت در بازی و ائتلاف‌های متفاوت کسب می‌کند. در این روش تابع مشخصه برای هر ائتلاف طبق معادله‌ی (۳-۱۲) برابر است با مجموع پهنای باند موردنیاز واحدهای شرکت کننده در ائتلاف درصورتی که کم‌تر از پهنای باند در اختیار ترمینال باشد و در غیر این صورت، برابر است با کل پهنای باند در دسترس ترمینال.
۵- هرکدام از ستون‌های سوم تا آخر جدول نمایشگر سهم مرزی هرکدام از واحدها به ازای شرکت در هر ائتلاف می‌باشند. جهت محاسبه‌ی المان‌های یکی از این ستون‌ها برای داریم:
الف) به ازای تمام اتحادهایی که در آن‌ها حضور ندارد، سهم مرزی واحد شبکه‌ی نوری i به ازای آن ائتلاف C، مطابق معادله (۳-۱۳) صفر است.
(۳-۱۳)
ب) در صورتی که عضو اتحاد باشد، سهم مرزی آن مطابق رابطه (۳-۱۴) برابر است با قدرمطلق تفاضل مقدار اتحاد مربوطه از مقدار اتحادی که اعضای آن دقیقا همان اعضای اتحاد مربوطه هستند به جز .
(۳-۱۴)
۶- پس از تکمیل تمام ستون‌های جدول اتحاد، ترمینال می‌تواند با بهره گرفتن از المان‌های ستون سهم مرزی هر واحد شبکه‌‌‌‌ی نوری، ONUshare_i را به عنوان سهم آن واحد از پهنای باند در دسترس محاسبه کند. سهم طبق معادله (۳-۱۵) برابر است با میانگینِ ۳ مورد زیر:
الف) : سهم مرزی وقتی خودش به تنهایی یک اتحاد تشکیل می‌دهد.
ب): میانگین سهم مرزی در اتحادهایی که این واحد عضو آن‌هاست و تعداد اعضای اتحاد بین ۲ تا است.
ج) : میزان سهم مرزی در اتحاد بزرگ (اتحادی که تمامی واحدها در آن حضور دارند).
(۳-۱۵)
پس از محاسبه‌ی تمامی عناصر بردار تخصیص ، ترمینال این میزان سهم را به واحدها اطلاع‌رسانی می‌کند تا واحدها بتوانند عمل انتقال داده را آغاز کنند. در انتهای این مرحله میزان پهنای باند موجود برابر صفر است و پس از آزادسازی پهنای باند در اختیار واحدها، این روند از ابتدا اجرا می‌شود. روند اجرای این روش در شکل ۳-۱ بیان شده‌ است و شکل ۳-۲ شبه کد این روش را نمایش می‌دهد.
برای تبیین مفهوم روش پیشنهادی به شکلی ساده‌تر یک شبکه نوری غیرفعال اترنت شامل یک ترمینال و سه واحد شبکه نوری را در نظر بگیرید که کل پهنای باند در دسترس ترمینال Mbps 400 بوده و درخواست هر کدام از واحدها نیز به ترتیب ۱۰۰، ۲۰۰ و ۴۰۰ است. از آن جایی که مجموع پهنای باند موردنیاز واحدها از کل پهنای باند در دسترس ترمینال، بیش‌تر است، چالش تخصیص پهنای باند مطرح می‌شود. پس از ارسال درخواست‌های واحدها به ترمینال توسط پیغام گزارش، ترمینال الگوریتم دیکه را برای تعیین سهم هر واحد از پهنای باند اجرا می‌کند. بدین ترتیب که ابتدا یک جدول اتحاد شامل ۷ سطر و ۵ ستون مطابق جدول ۳-۳ تشکیل می‌دهد. ستون اول این جدول شامل تمامی ائتلاف‌های ممکن به جز ائتلاف تهی برای سه واحد شبکه‌ی نوری به شکل اعداد باینری است، برای مثال ائتلافِ ۱۰۱ به معنای ائتلافی است که واحد اول و سوم در آن عضو هستند یا ائتلاف ۰۰۱ ائتلافی است که تنها سومین واحد، عضو آن است. در این مثال اعداد باینری از ۰۰۱ تا ۱۱۱ نشان دهنده‌ی ائتلاف‌های ممکن برای سه واحد شبکه‌ی نوری است.
پس از تعیین ائتلاف‌ها در ستون دوم جدول، مقدار متناظر با هر ائتلاف، با بهره گرفتن از رابطه (۳-۱۲) محاسبه می‌گردد. برای مثال برای محاسبه‌ی ارزش ائتلاف ۱۰۱، مجموع پهنای باند موردنیاز اعضای این ائتلاف یعنی واحد اول و سوم شبکه محاسبه می‌شود، اگر این حاصل جمع از کل پهنای باند در دسترس ترمینال بیش‌تر باشد، ارزش ائتلاف برابر پهنای باند کل و در غیر این صورت برابر حاصل جمع به دست آمده است که در این مثال، ارزش ائتلاف ۱۰۱، ۴۰۰ است زیرا مجموع درخواست‌های واحدهای اول و سوم، ۶۰۰ و بیش‌تر از کل پهنای باند موجود است. به همین ترتیب ارزش ائتلاف ۰۰۱، ۲۰۰ است. پس از محاسبه‌ی ارزش تمام ائتلاف‌ها، سهم مرزی هر واحد در ستون سوم، چهارم و پنجم توسط روابط (۳-۱۳) و (۳-۱۴) به ازای هر ائتلاف پر می‌شوند. پس از تکمیل جدول با بهره گرفتن از رابطه (۳-۱۵) سهم هر واحد از پهنای باند مشخص شده که در این مثال سهم واحدها از پهنای باند کل به ترتیب برابر با ۵۰، ۱۰۰ و ۲۵۰ است. پس از تعیین سهم همه‌ی واحدها، سهم هر واحد توسط پیغام دروازه به آن اعلام می‌گردد.
جدول ۳-۳- مثالی از روش تخصیص پیشنهادی دیکه