آگوست 6

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

های زمان بندی مش 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) خلاصه‌ای از روش‌های مختلف بر اساس چهارچوب ارائه شده در زیر بخش قبل



همه حقوق محفوظ است

Posted آگوست 6, 2018 by 92 in category "مقالات

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

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