اين، زمان‌بندی، زمانبندي، گره‌‌‌ها، گره‌‌‌

های زمان بندی مش WiMAX متعدد بررسی می شود.
شکل ‏48- چهارچوب دسته‌بندی برای بررسی الگوریتم‌های زمان‌بندی بر حسب شرایط اولیه
بعد دوم مکانسیم زمان بندی را بر اساس نوع ورودی‌های در نظر گرفته شده طبقه بندی می‌کند. شکل (4-9).
مکانیسم زمان بندی شامل زیرمجموعه ای از ورودی‌ها متشکل از موارد زیر است:
1) تعداد کانال‌های در دسترس برای زمان بندی( تک کاناله و یا چند کاناله)
2) تعداد رادیوهای مدنظر(تک رادیو و یا چند رادیو)
3)نوع درخواست ترافیک در شبکه(بر اساس درخواست گره‌‌‌ ویا نرخ ارسال )
4) شرایط مسئله مسیریابی(مشخص است و یا باید به عنوان یک پارامتر در مسئله درنظر گرفت شود)
5) نوع تداخل(نوع اول و دوم)
6) پارامترهای کیفیت سرویس [a233]
شکل ‏49- چهارچوب دسته‌بندی برای بررسی الگوریتم‌های زمان‌بندی بر حسب ورودی‌ها
بعد سوم مکانسیم زمان‌بندی را بر اساس هدف دسته‌بندی می‌کند. برای مثال هدف می‌تواند به حداکثر رساندن بازدهی شبکه و یا عدالت باشد. اهداف دیگر شامل زمان بندی برای به حداکثر رساندن تعداد جریان های پذیرفته شده، برای رفع الزامات پهنای باند حداقل هر جریان و زمان بندی برای جبران محدودیت هایی تأخیر برای کاربرهای بلادرنگ که از سخت ترین اهداف زمان‌بندی است می‌باشد (شکل4-10).
شکل ‏410- چهارچوب دسته‌بندی برای بررسی الگوریتم‌های زمان‌بندی بر حسب اهداف
چهارمین بعد و مهمترین بعد درباره انتخاب مکانیسم زمان بندی تصمیم می‌گیرد. نوع تکنیک عمدتاً توسط شرایط و هدف مکانیسم زمان‌بندی تعیین‌می‌شود. هرچه هدف متمرکز بر پارامترهای بیشتری باشد، تکنیک زمان بندی دشوارتر خواهدبود. همانطـورکه قبـلاً بیـان شد زمان‌بندی یک مسئــله NP-Hard است. نوعاً سعـی بر آن است مسئــله زمان‌بندی به عنـوان یک مسئله زمان‌بندی خطـی فرمـوله شده و یـا از الـگوریتـم‌هــای مکـاشـفه‌ای استفـاده شود (شکل [a234]4-11).
در بخش بعد، این چهارچوب طبقه بندی به عنوان مرجعی برای طبقه بندی الگوریتم های زمان بندی مختلف استفاده خواهد شد. این کار منجر به مقایسه کارآمد میان تعیین مشکلات مطرح مختلف و مکانیسم‌های زمان‌بندی مربوطه خواهد شد.
شکل ‏411- چهارچوب دسته‌بندی برای بررسی الگوریتم‌های زمان‌بندی بر روش حل مسئله
معرفی الگوریتم‌های زمان‌بندی با رویکرهای‌مختلف
در این بخش بر اساس چهارجوب دسته‌بندی ارائه شده در بخش قبل تعدادی از الگوریتم‌های زمان‌بندی متمرکز در شرایط مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه، نرخ ارسال مشخص گره‌‌‌ها معرفی خواهند[a235] شد. برای شروع، ابتدا الگوریتم استاندارد شبکه‌ی مش بی‌سیم WiMAX معرفی خواهد شد و در ادامه الگوریتم‌های دیگر مورد بررسی قرار گرفته و درنهایت خلاصه ای از الگوریتم‌های مختلف در شرایط مختلف بر اساس چهارچوب ارائه شده در جدولی ارائه خواهند[a236] شد.
الگوريتم زمانبندي استاندارد IEEE 802.16[43]
شرایط: زمان بندی متمرکز، مش مبتنی بر TDMA، آنتن همه جهته، توپولوژی درخت
ورودی: مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه، نرخ ارسال مشخص گره‌‌‌ها
هدف: زمان‌بندی بدون در نظر گرفتن عدالت،[a237] بازدهی و خدمات سرویس
تکنیک: اکتشافی
استاندارد 802.16 از يک مثال براي ارائه ضمني الگوريتمي ساده به منظور تخصيص پنجره‌هاي زماني با مکانيزم متمرکز استفاده مي‌نمايد. اين الگوريتم در گام اول و براي رتبه‌بندي از پيمايش BFS درخت مسيريابي استفاده مي‌کند. اولين لينکي که در پيمايش درخت ملاقات مي شود، کوچکترين رتبه را ميگيرد. به لينک‌هاي بعدي در پيمايش درخت، رتبه‌هاي بزرگتري داده مي شود تا هنگامي که رتبه‌بندي تمام گره‌‌‌ها انجام شود. قابل ذکر است که اين رتبه‌بندي، ترتيب ارسال بهينه‌اي را ايجاد نمي‌کند. همچنين ممکن است تاخير TDMA در برخي مسيرها به شدت زياد باشد. اين تاخير زماني رخ مي‌دهد که در مسير يک بسته لينک خروجي يک گره‌‌‌ قبل از لينک ورودي آن زمانبندي شود. پس از آن به لينک با کوچکترين رتبه به اندازه پنجره‌هاي زماني درخواستي‌اش از ابتداي زير فريم ديتا اختصاص داده مي شود؛ به لينک بعدي، که کوچکترين رتبه را دارد، پنجره‌هاي زماني پس از پنجره‌هايي که به لينک اول تخصيص داده شد، اختصاص مي‌يابد. به اين ترتيب پنجره‌هاي زماني به لينک‌ها تخصيص داده مي‌شود تا هنگاميکه زمانبندي تمام لينک‌ها انجام شود. اگر دو لينک رتبه يکساني داشته باشند، لينک با شناسه کوچکتر زودتر ارسال ميکند. در نهايت اگر تعداد پنجره‌هاي تخصيص داده شده به لينک‌ها بيشتر از تعداد پنجره‌هاي رزرو شده براي زمانبندي متمرکز در زير فريم ديتا باشد، الگوريتم بايد طول ارسال لينک‌ها را به گونه‌اي عادلانه کاهش دهد تا ارسال‌ها در يک زير فريم ديتا جاي گيرند. به اين عمل کاهش تناسبی[a238] گويند. قابل ذکر است که الگوريتم معرفي شده در استاندارد 802.16 استفاده مجدد از فضاي فرکانسي را پشتيباني نمي‌کند. لذا احتمال زيادي دارد که نتيجه زمانبندي از تعداد پنجره‌هاي بخش زمانبندي متمرکز زير فريم ديتا تجاوز کند.برای غلبه بر این مشکل از ایده کاهش تناسبی[a239] استفاده می‌شود. برای کاهش نتاسبی، تعداد پنجرههاي تخصيص داده شده به لينک i از رابطه زیر به دست مي‌آيد. کسر سمت چپ در اين رابطه معادل طول ارسال مورد نياز لينک i بر حسب تعداد سمبل است.
4-1) تعداد پنجره‌های زمان‌بندی متمرکز در زیر فریم دیتا
طول ارسال لینک i
=
تعداد پنجره‌های تخصیص داده شده به لینک i
تعداد کل پنجره‌های مورد نیاز برای زمان‌بندی
طول پنجره‌های زمانی در زیر فریم دیتا
از آنجا که ممکن است حاصل عددي غير صحيح باشد، استاندارد 802.16 چگونگي گرد کردن طول ارسال را مشخص مي‌کند. در ابتدا گره‌‌‌ها را بر اساس افزايش بخش اعشاري طول کاهش يافته ارسال مرتب مي‌کند. پس از آن يک گره‌‌‌ از ابتداي ليست و يک گره‌‌‌ از انتهاي ليست انتخاب مي شود. طول کاهش يافته ارسال گره‌‌‌ ابتداي ليست را به پايين گرد کرده و طول کاهش يافته ارسال گره‌‌‌ انتهاي ليست را به بالا گرد مي‌کند. اين روند تا آنجا ادامه پيدا مي‌کند که تمام طول ارسال‌ها عددي صحيح باشند. مطالعات انجام شده نشان مي‌دهد که کاهش بطور تناسبی، عدالت نسبي را ميان جريانهاي ترافيکي انتها به انتها رعايت مي‌کند. اين نتيجه از آنجا حاصل مي شود که رابطه‌اي خطي مابين پهناي باند گره‌‌‌ و پهناي باند انتها به انتها[a240] وجود دارد.
الگوريتم TTS157[17]
شرایط: زمان بندی متمرکز، مش مبتنی بر TDMA، آنتن همه جهته، توپولوژی درخت.
ورودی: مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه، نرخ ارسال مشخص گره‌‌‌ها.
هدف:رعایت عدالت در گره‌‌‌ها، خدمات سرویس درنظر گرفته نشده است.
الگوريتم TTS پنجره‌هاي زماني را در تکرارهاي مختلف به لينک‌هايي که با يکديگر تداخل ندارند، تخصيص مي‌دهد. به هر SS بر مبناي ترافيک درخواستي آنها، تعداد نشانه‌هاي مشخصي اختصاص داده مي‌شود. هر گره‌‌‌ مي‌تواند به اندازه نشانه‌هاي موجود خود از پنجره‌هاي زماني براي ارسال استفاده نمايد. با اختصاص هر پنجره به يک گره‌‌‌، يکي از تعداد نشانه‌هاي فرستنده آن لينک کاسته شده و يکي به تعداد نشانه‌هاي گيرنده يک گره‌‌‌، يکي از تعداد نشانه‌هاي فرستنده آن لينک کاسته شده و يکي به تعداد نشانه‌هاي گيرنده BS هدايت کند. لذا به اين وسيله مدل ذاتي رله ترافيک در شبکه‌هاي مش در الگوريتم گنجانده شده است. همچنين سعي شـده است به اين وسيـله عدالت در شبـکه رعايت شود و برخي گره‌‌‌ها دچار گرسنـگي نشوند. تعداد نشانـه‌هايي که به گره‌‌‌ i اختصـاص داده مي شود (Tokeni) از رابطه tokeni = tri/g، که در آن g بزرگترین مقسوم علیه مشترک ترافیک ها و tri ترافیک درخواستی هرگره‌‌‌ است محاسبه می‌شود.
اگر سه مرحله زمانبندي در [a241]نظرگرفته[a242] شود، الگوريتم TTS در مرحله رتبه‌بندي چهار سياست مختلف براي انتخاب لينک‌ها در هر پنجره زماني را معرفي کرده است. در زير اين چهارروش آورده شده است.
تصادفي : انتخاب لينک به صورت تصادفي انجام مي شود.
مينيمم تداخل: [a243]لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد SS هاي کمتري را دچار تداخل مينمايد.
تعداد گام کمتر تا BS: لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد گام‌هاي کمتري تا BS دارد.
تعداد گام [a244]بيشتر تا BS: لينکي براي زمانبندي انتخاب مي شود که فرستنده آن، تعداد گام‌هاي بيشتري تا BS دارد.
هنگاميکه که گره‌‌‌ها در شرايط مساوي هستند(تعداد گام‌هايشان تا BS يکسان است يا تداخلي که ايجاد مي‌کنند برابر باشد) گره‌‌‌ي که شناسه کوچکتري دارد، اولويت بيشتري دارد. در نهايت با مقايسه‌هاي صورت گرفته، سياست سوم، انتخاب گره‌‌‌ي که تعداد گام کمتري تا BS دارد، به عنوان سياست برتر معرفي شده است.
در مرحله دوم، به منظور انجام زمانبندي در ابتدا وضعيت تمام لينک‌هايي که تعداد نشانه‌هاي فرستنده بر روي آن لينک غير صفر است، فعال[a245] برچسب مي‌خورد. ساير لينک‌ها نيز بيکار هستند. هدف زمانبندي لينک‌هاي فعال است. لذا در هر پنجره زماني ابتدا يک لينک فعال براي زمانبندي انتخاب شده و در وضعيت زمانبندي شده قرار مي‌گيريد و از تعداد نشانه هاي گره‌‌‌ فرستنده بر روي اين لينک يکي کاسته شده و به نشانه‌هاي گره‌‌‌ گيرنده يکي افزوده مي‌شود. پس از آن تمام لينک‌هاي همسايه که با اين لينک تداخل دارند، مشخص مي‌شوند و برچسب ” تداخل[a246] ” مي‌خورند. سپس از ميان ساير لينکها، با توجه به سياست بکار گرفته شده لينک موجود ديگري براي زمانبندي در اين پنجره زماني انتخاب مي شود. اين کار تا زماني ادامه مي‌يابد که ديگر نتوان لينکي را در اين پنجره زماني با وضعيت موجود انتخاب کرد. پس از آن، زمانبندي لينکها در پنجره زمانبندي بعدي ادامه مي‌يابد تا زمانيکه نشانه‌هاي تمام SS ها صفر شود. در اين الگوريتم کاهش تناسبی[a247] طول ارسال، ديده نشده است.
الگوريتم LA[20]
ورودی: مسیریابی مشخص، رادیو تک کاناله، مدل تداخل اولیه و ثانویه ، نرخ ارسال مشخص گره‌‌‌ها
این الگوریتم از دو فاز تشکيل شده است. به خاطر فاز دوم اين الگوريتم، در اين پايان نامه از LA158 براي ناميدن آن استفاده شده است. در فاز اول که توسط BS اجراء مي شود، ترتيب ارسال گره‌‌‌ها(رتبه‌بندي) مشخص مي‌گردد. BS ترتيب ارسال و پهناي باند تخصيص داده شده به تمامي گره‌‌‌ها را در سطح شبکه پخش مي‌کند. در اين فاز از معياري به نام شاخص رضايت159 استفاده مي‌شود. اين پارامتر ميزان توجهي [a248]به درخواست‌هاي هر گره‌‌‌ در پنجره زماني مشخصي شده را نشان مي‌دهد. در ابتداي هر تکرار، الگوريتم مقدار شاخص رضايت متناظر با هر لينک را با توجه به زمانبندي تعيين مي‌کند. شاخص [a249]رضايت رابطه مستقيم با نسبت نرخ متوسط تخصيصي به گره‌‌‌ i به نرخ عادلانه آن دارد. نرخ عادلانه متناظر با مقدار وزن هر گره‌‌‌ مي باشد. BS اين پارامتر را براي تمام گره‌‌‌ها محاسبه مي‌نمايد. هنگاميکه که BS درخواست پهناي باند را از گره‌‌‌ها دريافت مي‌کند، اين درخواستها را با توجه به ترتيب صعودي شاخص رضايت گره‌‌‌ها، مرتب مي‌کند که این[a250] ترتيب ارسال گره‌‌‌ها را تعيين مي‌‌نماید[a251]. در فاز دوم الگوريتم، گره‌‌‌ها با توجه به درخت مسيريابي شبکه، ترتيب ارسال حاصل از فاز ۱ و پهناي باند مورد نياز ساير گره‌‌‌هاي شبکه، الگوريتم زمانبندي را اجراء مي‌کنند تا با زمانبندي يک يا چندين گره‌‌‌ در هر پنجره زماني، دسترسي همزمان به کانال فراهم آورده شود.
الگوریتم مقیاس بلوک کردن160 [44]
هدف: محاسبه مسیر امکان پذیر، خدمات سرویس درنظر گرفته نشده است.
این روش از پارامتری به عنوان مقیاس بلوک کردن در زمان‌بندی استفاده می‌کند. همانطور که در شکل (4-12) نشان داده شده است مقایس بلوک کردن یک مسیر، مجموع مقادیر گره‌‌‌هایی است که در ارسال یک گره‌‌‌ تداخل ایجاد می‌کند. این بدان معناست[a252] که مقیاس بلوک کردن مشخص می‌کند [a253]که در [a254]صورت پذیرش[a255] در خواست گره‌‌‌، چند ارسال دیگر رد یا بلوک می شوند. بنابراین از تمام مسیرهای ممکن از گره به ریشه، مسیری که منجر به حداقل تداخل هست انتخاب می‌شود. سپس لینک‌ها روی مسیر به شیوه‌ی تکراری براساس بالاترین تقاضای ترافیکی تخصیص نیافته زمان بندی می‌شود. زمان‌بندی لینک ها[a256]، که در شیار مشابه تداخل دارند، تا گام بعد به تأخیر می‌افتد. در عین حال برای به حداکثر رساندن ارسال‌های همزمان، لینک های غیر تداخلی در همان شیار[a257] زمانی زمان بندی می‌شوند.
شکل ‏412-مثالی برای نشان دادن مفهوم مقیاس بلوک کردن b(path)=2+4+3+4=13[44]
الگوریتم زمان‌بندی برپایه تئوری صف [45]
ورودی: مسیریابی مشخص، رادیو تک کاناله، بدون درنظرگرفتن تداخل ثانویه، نرخ ارسال مشخص گره‌‌‌ها
هدف: تعیین مسیریابی، محاسبه مسیر امکان پذیر، در نظر گرفتن خدمات سرویس(پهنای باند)
الگوریتم فوق روشی را با استفاده از تئوری صف در چهارچوب حالت مش IEEE 802.16 پیشنهاد می کند.
درروش پیشنهادی ابتدا بر اساس الگوریتم مسیریابی Dijkstra کوتاهترین مسیر که زمان ارسال مورد انتظار از گره به BS را به حداقل می‌رساند محاسبه می‌شود. سپس به عنوان گام دوم، برای ارائه خدمات QoS بسته های را که نمی‌تواند تضمین کند حذف می‌کند. نویسنده بیان کرده است در این روش میزان حذف بسته‌ها بیشتر از 2% نخواهد بود. به عنوان گام سوم، مطابق با درخواست گره‌‌‌‌ها تعداد شیار[a258] مشخصی برای ارسال در اختیار هر گره‌‌‌ قرار داده می‌شود.برای تخصیص شیار از الگوریتم‌های زمان‌بندی[a259] WRRوWFQ استفاده شده است. البته در این روش استفاده از فضای مجدد فرکانسی در نظر گرفته نشده است و تلاشی که برای ارائه خدمات سرویس در نظر گرفته شده است از دیدگاه شبکه و بر پایه کمینه کردن متوسط تأخیر در کل شبکه است و کماکان مشکل خدمات سرویس از دید کاربر حل نشده است.
الگوریتم زمان‌بندی BFS161 [46]
ورودی: مسیریابی مشخص، رادیو تک کاناله، بدون درنظرگرفتن تداخل ثانویه، نرخ ارسال مشخص گره‌‌‌ها
هدف: در نظر گرفتن خدمات سرویس(متوسط کل تأخیر ارسال گره‌‌‌ها)
در این روش جهت برآورده نمودن خدمات سرویس، متوسط کل تأخیر شبکه بهینه می‌شود. در این روش سعی برآن است زمان ارسال ترافیک رله‌های شبکه به نحوه‌ی زمان‌بندی می‌شود که زمان‌بندی ارسال رله‌های شبکه بر اساس نحوه‌ی ترتیب قرارگیری آن‌ها بین گره‌‌‌ها و BS انجام شود[a260]. علاوه بر این برای کاهش سربار محاسباتی حاصل از پیاده سازی پیشنهاد شده است که رله‌های[a261] با بارترافیکی بالا در اولویت ارسال قرارگیرند.
الگوریتم زمان‌بندی 162DPS-SR [21]
ورودی: مسیریابی مشخص، رادیو تک کاناله، تداخل اولیه و ثانویه، نرخ ارسال مشخص گره‌‌‌ها
هدف: درنظرگرفتن خدمات سرویس از دید کاربر( با تضمین تأخیر انتها به انتهای کاربر)
براساس مطالعات ما تا زمان نگارش این پایان‌نامه، مقاله فوق تنها تحقیق و مطالعه ی عمیق[a262]ی است که در زمینه تضمین تأخیر انتها به انتها صورت گرفته است. تلاش‌های قبلی در راستای ارائه خدمات سرویس صرفا تلاشی برای بهبود متوسط کل تأخیر شبکه بوده و تضمینی در ارائه خدمات سرویس انتها به انتهای کاربر ارائه ‌نکرده اند. الگوریتم DPS-SR که اساس کار مقایسه نتایج در فصل آینده خواهد بود از سه بخش اصلی تشکیل شده است که در ادامه بدان اشاره[a263] می‌شود:
مرتب سازی درخواست‌ کاربران بر اساس زمان سررسید
در این مرحله ابتدا درخواست گره‌‌‌ها بر اساس سررسید هر درخواست مرتب می‌شود(دقت[a264] شود که گره‌‌‌های رله درشبکه از خود ترافیک تولید نکرده و تنها انتقال دهنده ترافیک درخواستی سایر گره‌‌‌ها را بر عهده دارند ). برای این مرتب سازی از روش EDD163 استفاده شده است. در [21] نشان داده شده است EEDیک روش بهینه مرتب‌سازی بر اساس زمان سررسید درخواست‌ها در زمان‌بند است. علاوه بر این این روش در انتخاب مناسب گره‌‌‌ها در فاز بعدی نیز راهگشا خواهد بود.
انتخاب زیرمجموعه‌ای مناسب از درخواست‌ها
بر اساس روش EED درمرحله قبل، زمان ارسال درخواست هر گره‌‌‌ نزدیک به سررسید ارسال خود خواهد بود. در این مرحله با توجه به توپولوژی شبکه، ترافیک و تأخیر تداخل ارسال سایر گره‌‌‌ها در رله‌های شبکه، بر اساس یک الگوریتم خطی و وزن‌دهی که به گره‌‌‌ها داده می‌شود،[a265] زیر مجموعه‌ای[a266] ازدرخواست‌ها برای ارسال انتخاب می‌شوند. ملاک انتخاب ارسال تضمین تأخیر انتها به انتهای درخواست کاربر است. بنابراین دراین مرحله تعدادی از درخواست‌ها [a267]با وجود آنکه بر اساس EDD از اولویت ارسال برخوردار هستند به خاطر عدم تضمین تأخیر انتها به انتها به دلیل ترافیک و تأخیر سایردرخواست‌ها، حذف خواهند شد
تخصیص شیارهای زمانی بر اساس مرحله دوم
بعد از انتخاب زیر مجموعه ای از درخواست‌ها برای ارسال(که [a268]تأخیر ارسال برای این درخواست‌ها تضمین شده است) کانال در اختیار گره‌‌‌ها قرار داده می‌شود. در هر مرحله اگر امکان ارسال همزمان وجود داشته باشد به درخواست سایر گره‌‌‌ها اجازه ارسال داده می‌شود. نشان داده شده[a269] است که درجه سختی مسئله در حالت استفاده مجدد از فضای فرکانسی از O(n3×r2) است. n تعداد درخواست‌ها و r حداکثر تعداد رله در شبکه است.
خلاصه سازی روش‌های مختلف زمان‌بندی بر اساس مدل
در ادامه در جدول(4-1) خلاصه‌ای از روش‌های مختلف بر اساس چهارچوب ارائه شده در زیر بخش قبل

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *