دانلود پایان نامه با موضوع زمانبندي، استاندارد، لینکهای، پنجره‌هاي

دانلود پایان نامه ارشد

ميدهد.
لازم به ذکر است، زمانبندي تعيين شده در i امين پريود زمانبندي، در پريود زمانبندي i+1 ام بکار برده مي شود. همچنين به خاطر ماهيت متمرکز بودن اين زمانبندي، در اينجا با مشکل ترمينال‌هاي پنهان روبرو نيستيم.
جمع بندی
در اين فصل بطور اجمالي به معرفی استاندارد 802.16 ، آشنايي با مفاهيم اوليه زمانبندي، جزئيات مد مش استاندارد پردخته شد. مد مش استاندارد 802.16 دو روش زمانبندي متمرکز و توزيع شده را براي تخصيص پنجره‌هاي زماني زير فريم ديتا معرفي مي‌نمايد. زمانبندي با مديريت متمرکز، براي ترافيک اينترنت[a188]، يا مديريت توزيع شده براي ترافيک اينترانت، انجام مي شود. از آنجا که ترافيک اينترنت، ترافيک عمده شبکه را تشکيل مي‌دهد، مکانيزم متمرکز، روش غالب زمانبندي در شبکه‌هاي مش مبتني بر استاندارد 802.16 خواهد بود. گره‌‌‌هايي که با مکانيزم متمرکز زمانبندي مي‌شوند، پهناي باندشان به وسيله BS تضمين شده است. تضمين گام به گام پهناي باند در درخت مسيريابي براي مکانيزم متمرکز، امکان تضمين کيفيت سرويس انتها به انتها براي جريان‌هاي ترافيکي را فراهم مي‌آورد. در مقابل گره‌‌‌هايي که با مکانيزم توزيع شده زمانبندي مي‌شوند، رفتار گذرايي دارند و پهناي باند تخصيص داده شده به آنها به گره‌‌‌هاي همسايه بستگي دارد. تعيين مينيمم پنجره‌هاي زماني در زير فريم ديتا که براي زمانبندي متمرکز استفاده مي‌شوند، يکي از موضوعات با اهميت در شبکه‌هاي مش 802.16 است. با تعيين مينيمم اين پنجره‌ها با رویکرد تضمین کیفیت سرویس انتها با انتها، علاوه بر اينکه پهناي باند کافي براي سرويس‌هايي که نياز به تضمين خدمات سرویس انتها با انتها دارند، امکان تخصیص پهناي باند بيشتري براي ترافيک best effort باقي خواهد ماند. لذا هدفي که در اين پايان‌نامه دنبال مي‌شود، ارائه الگوريتمي کارا براي انجام زمانبندي به منظور تخصيص پنجره‌هاي زماني با هدف تضمین کیفیت سرویس انتها به انتها است. در فصل آينده به بررسي الگوريتم‌هايي که در اين زمينه ارائه شده‌اند[a189]، پرداخته مي‌شود.

فصل چهارم
مدل، چالش‌ها و روش‌های زمان‌بندی متمرکز در شبکه‌های مش بی‌سیم

مقدمه
همانطور که در فصل‌هاي گذشته ذکر شد هدف از زمانبندي، اختصاص پنجره‌هاي زماني‌در زير فريم ديتا به گره‌‌‌هاي شبکه به گونه‌اي است که ارسال دو گره‌‌‌ در يک پنجره زماني، باعث ‌بروز تداخل نشود. الگوريتم زمانبندي بکار گرفته شده براي تخصيص پنجره‌هاي زماني زير فريم ديتا به گره‌‌‌های شبکه در استفاده کارا از پنجره‌هاي زماني تاثير بسزا دارد. در[a190] مطالعات قبلي [14،18،12،38] نشان داده شده است که دستيابي به يک تخصيص بهينه، مسئله‌اي NP-Hard است. لذا وقتي تعداد گره‌‌‌های شبکه افزایش می‌یابد، يافتن يک راه‌حل بهينه براي زمانبندي غير ممکن به نظرمی‌رسد. منظور از راه‌حل بهينه، استفاده از کمترين تعداد پنجره‌هاي زماني زير فريم ديتا و تخصيص به گره‌‌‌های شبکه به گونه‌ای که درخواست‌هاي تمام گره‌‌‌های شبکه برآورده[a191] شود. با اين حال تاکنون الگوريتم‌هاي متعددی در این زمینه ارائه شده‌اند.
در اين فصل تلاش بر آن است تا[a192] به اصول کلي طراحي الگوريتم‌هاي زمانبندي متمرکز،مدل و پارامترهاي مد نظر و نیز الگوریتم‌های مختلف با بررسی نقاط ضعف و قوت آن‌ها پرداخته[a193] شود.

نیازمند‌های طراحي الگوريتم هاي زمانبندي
در طراحی یک روش زمان‌بندی، تعیین مدل و پارامترهای ورودی مسئله مشخص کننده اهداف و روش حل مسئله خواهد بود. در ادامه به بررسی مدل و شرایط در نظرگرفته شده در این پایان نامه برای حل مسئله زمان‌بندی اشاره می‌شود.
تداخل میان لینکهای بی‌سیم
تداخل میان لینکهای بی سیم هنگامی رخ می دهد که بسته های ارسالی روی لینکهای مختلف با یکدیگر برخورد داشته باشند و بسته با موفقیت به مقصد نرسد. در این پایان نامه فرض ما بر این است که کلیه فرستندهها و گیرندهها در هرگره، از یک کانال رادیویی برای ارسال و دریافت استفاده میکنند. همچنین تعاریف ما بر اساس مدل تداخل «فاصله143» بیان شده است [42]، به عبارتی دیگر فرض براین است که لینکهای بیسیمی که در رنج ارسال یکدیگر نیستند، باهم تداخل ندارند. هرچند مدلهای واقعیتری نیز ارائه شده است [42]، ولی برای سادگی از مدل فاصله استفاده شده[a194] است.
در شکل (4-1)، پنج نوع تداخل نمایش داده شده است. در تداخل (الف) دو ارسال همزمان[a195] برای یک گیرنده مشترک صورت گرفته است که موجب تصادم بستهها در گیرنده میشود. در حالت (ب)، یک فرستنده قصد ارسال هم زمان به دو گیرنده متفاوت را دارد. در این مورد چون فرستنده[a196] قادر به جداکردن بسته های دو ارسال نمی باشد، امکان چنین ارسالی را ندارد. تداخل در (ج) به این خاطر رخ می دهد که یک گره‌‌‌ قادر به ارسال و دریافت پیام به طور همزمان نمی‌باشد. هرچند با ارسال بر روی لینکهای دوطرفه کامل144 امکان[a197] به حذف این نوع تداخل وجود[a198] دارد[a199]، اما در این پایاننامه فرض شده است[a200] که کلیه ارتباطات برروی لینکهای نیمه دوطرفه145 ارسال می گردد، لذا در ادامه این نوع تداخل را[a201] در کلیه ارتباطات درنظر گرفته می‌شود[a202]. باتوجه به این که این سه نوع تداخل همگی به خاطر ارسال گره هایی هستند که در فاصله یک گامی هم قرار دارند، لذا به این نوع تداخل به اصطلاح تداخل اولیه146 گفته می شود. پس به طور کلی می‌توان گفت تداخل اولیه در یک گره هنگامی رخ می دهد که در یک شیار زمانی ارسال و دریافت به طور همزمان صورت پذیرد و یا در یک لحظه زمانی، بیشتر از یک بسته، ارسال و یا دریافت شود [43].

ج
ب
الف

ه
د
شکل ‏41-انواع تداخل‌های موجود در شبکه‌های بی‌سیم
علاوه بر این سه نوع تداخل که ناشی از ارسال توسط[a203] همسایه مستقیم گره می شود، در شبکه های TDMA یک نوع تداخل دیگر نیز باید در نظر گرفته شود. این نوع تداخل در شکل(4[a204]-1 قسمت [a205]د) نمایش داده شده است. این دو لینک قادر نخواهند بود به طور همزمان ارسال کنند زیرا دراین صورت موجب رخ دادن تصادم در گره همسایه مشترکشان که در رنج ارسالی هر دو فرستنده است، می شود. (در قسمت (د) لینک تداخل با خط چین نشان داده شده است). به این نوع تداخل به اصطلاح تداخل ثانویه گفته می‌شود، زیرا منشأ این نوع تداخل، گرههایی هستند که در فاصله دو گامی هم قرار دارند. به عبارت دیگر تداخل ثانویه هنگامی اتفاق میافتد که گره گیرنده در رنج ارسالی دو فرستنده باشد، اگرچه فرستنده دوم برای گیرنده دیگری ارسال میکند اما با این حال باعث ایجاد تداخل در گیرنده اصلی میشود [43].
از میان این پنج نوع تداخل، تنها چهار نوع اول باید درشبکه های بیسیم TDMA در نظر گرفته شوند، هرچند که تداخل نوع پنجم نیز[a206] در شبکه های بیسیم موجود است. این نوع تداخل در شکل (قسمت ه) نمایش داده شده است. دراین حالت چون دو فرستنده در رنج ارسالی هم قرار دارند نمیتوانند همزمان ارسال کنند. این نوع تداخل در شبکه های مش مطرح در این پایان نامه مشکلی ایجاد نمیکند، اما به عنوان مثال در استاندارد IEEE 802.11 این نوع تداخل وجود دارد. در این شبکهها هنگامی که فرستنده و گیرنده پروسه‌ی دست تکانی147 را برای ارسال پیامهای RTS148 و CTS149 انجام میدهند، فرستنده‌ی دیگری که در رنج ارسالی آن هاست، نمیتواند پیام RTS را در جواب درخواست گره دیگری ارسال کند. در این پایاننامه تداخل نوع پنجم نادیده گرفته شده است، چرا که موضوع بحث ما شبکههای بیسیمی نظیر WiMAX است و این شبکهها مبتنی بر TDMAهستند.
برای روشن شدن مطلب، شکل (4-2) را در نظر بگیرید. دراین شکل گره BS ایستگاه مرکزی و RS ها ایستگاه‌های رله هستند. لینکهای درخت مسیریابی به صورت فلش و مدل تداخل در قالب گرافی به نام گراف تداخل نشان داده شده است. در این توپولوژی اگر گره‌‌‌ 4 بخواهد به[a207] ایستگاه مرکزی در یک شیار زمانی مشخص، در مسیر فراسو ارسال کند، در آن صورت در این شیار زمانی به خاطر تداخل اولیه برروی لینک رله 2 ارسالی نباید صورت پذیرد.

ب
الف
شکل ‏42-درخت زمان‌بندی شبکه مش به همراه گراف تداخل
سربار150
یکی از مسائلی که در تمامی شبکه‌ها باعث به هدررفتن پهنای باند می‌شود، مسئله سربار است. سربار می‌تواند به طرق مختلف به شبکه اعمال شود. برای مثال سربار می تواند ناشی از قطعه قطعه سازی151 زیاد بستهها به وجود آید. به این دلیل[a208] که برای مسائلی چون شناسایی بسته و کنترل خطا در هر بسته از شبکه عموما اطلاعاتی در سرآیند152 و پی‌آیند153 فریم قرار داده می شود، با قطعه قطعه سازی بیش از حد بستهها[a209] بدون اینکه اطلاعات بیشتری[a210] جابجا شود، تنها سرآیندها و پیآیندهای فراوانی که به هربسته اضافه میشوند به شبکه اعمال می‌گردد[a211].
در شبکههای TDMA یکی از روشهایی که باعث کاهش چشمگیر سرآیند می شود این است که زمانبندی ارسال هرگره در یک فریم را پشت سرهم قرار دهیم، به عبارت دیگر اگر قرار است به گره ای 10 شیار زمانی در یک فریم تخصیص داده شود تا دادههای خود را ارسال کند، زمان بندی ارسال این گره را باید به گونهای انجام دهیم که 10 شیار زمانی متوالی به این گره تخصیص یابد.
برای واضح شدن مطلب، برای سربار ناشی از گارد زمانی در استاندارد 802.16 مثالی در فصل سوم بررسی شد. در این استاندارد بین فرصتهای ارسالی هرگره در زیر فریم داده مش، گارد زمانی به طول 2 یا 3 شیار زمانی قرار می‌گیرد.
واضح است که به تعداد دفعات غیرمتوالی که یک گره در فریم ارسال کند، به همان تعداد این سربار به شبکه اعمال میشود که منجر به افت بسزایی در گذردهی شبکه میشود.
تأخیر
تأخیر یکی از مهمترین فاکتورهای کیفیت سرویس است که باید در نحوه‌ی زمان بندی لینکها مورد توجه قرار گیرد. ﻣﻘﺪار زﻣﺎﻧﯽ ﮐﻪ ﺑﻪ ﻃﻮر ﻣﺘﻮﺳﻂ ﻃﻮل ﻣﯽ‌ﮐﺸﺪ ﺗﺎﯾﮏ ﺑﺴﺘﻪ از ﯾﮏ ﻧﻘﻄﻪ ﺷﺒﮑﻪ ﺑﻪ ﻧﻘﻄﻪ دﯾﮕﺮآن ﺑﺮود،ﺗﺎﺧﯿﺮﺑـﺴﺘﻪ را ﻣـﺸﺨﺺﻣﯽ‌ﮐﻨﺪ. ﺗﺎﺧﯿﺮ اﻧﺘﻬﺎ ﺑﻪ اﻧﺘﻬﺎی ﺑﺴﺘﻪ ﺗﻮﺳـﻂ ﭘﺎراﻣﺘﺮﻫـﺎﯾﯽ ﻧﻈﯿـﺮ ﺗﺎﺧﯿﺮﻫـﺪاﯾﺖ[a212] ﭘﯿـﺸﺮو، ﺗـﺎﺧﯿﺮ ﺻـﻒ ﺑﻨـﺪی، ﺗـﺎﺧﯿﺮ اﻧﺘﻘـﺎل وﺗﺎﺧﯿﺮﺳﺮی ﺳﺎزی ، ﻣﺸﺨﺺ ﻣﯽ ﺷﻮد. درﺷﮑﻞ (4-3) ﻣﺜﺎﻟﯽ از ﻧﺤﻮه ﻣﺤﺎﺳﺒﻪ ﺗﺎﺧﯿﺮآورده ﺷﺪه اﺳﺖ.

شکل ‏43- نحوه‌ی محاسبه تأخیر انتها به انتها
ﺗﺎﺧﯿﺮﻫﺪاﯾﺖ ﭘﯿﺸﺮو ﻧﺸﺎن دﻫﻨﺪه ﻣﻘﺪارزﻣﺎﻧﯽ اﺳﺖ ﮐﻪ ﻃﻮل ﻣﯽ ﮐﺸﺪ ﺗﺎﻣﺴﯿﺮﯾﺎب ﺑﺴﺘﻪ را درﯾﺎﻓـﺖ ﻧﻤـﻮده و ﺑـﺮای ﻫـﺪاﯾﺖ آن ازﻃﺮﯾﻖ ﯾﮏ درﮔﺎه ﻣﻨﺎﺳﺐ ﺗﺼﻤﯿﻢ ﮔﯿﺮی ﻧﻤﺎﯾﺪ. ﺑﻪ ﻋﺒﺎرت دﯾﮕﺮ ﺗﺎﺧﯿﺮ ﻫﺪاﯾﺖ ﭘﯿﺸﺮوﻧـﺸﺎن دﻫﻨـﺪه ﺣـﺪاﻗﻞ زﻣـﺎن ﻻزم ﺑـﺮای ﭘﺮدازش وﻫﺪاﯾﺖ ﯾﮏ ﺑﺴﺘﻪ درﻣﺴﯿﺮﯾﺎب ﻣﯽ ﺑﺎﺷﺪ. ﺗﺎﺧﯿﺮﺻﻒ ﺑﻨﺪی ﺑﯿﺎﻧﮕﺮ ﻣﯿﺰان زﻣﺎن اﻧﺘﻈﺎر ﯾﮏ ﺑﺴﺘﻪ در ﺻﻒ، ﻗﺒﻞ از ارﺳﺎل ﺑﻪ درﮔﺎه ﺧﺮوﺟﯽ ﻣﻨﺎﺳﺐ ﻣﯽ‌ﺑﺎﺷﺪ. ﺗﺎﺧﯿﺮ اﻧﺘﻘﺎل ﻧﺸﺎن دﻫﻨﺪه زﻣﺎن ﻻزم ﺑﺮای ﻃﯽ ﮐﺮدن ﮐﺎﻧﺎل ﻓﯿﺰﯾﮑﯽ اﺳﺖ. ﻣﯿﺰان ﺗﺎﺧﯿﺮاﻧﺘﻘﺎل ﺑﺎ فاصله ﻓﯿﺰﯾﮑﯽ بین دو گره‌‌‌ ﻧﺴﺒﺖ ﻣﺴﺘﻘﯿﻢ دارد. در این پایان نامه از تأخیر انتقال فیزیپکی بین دو گره‌‌‌ در ارسال صرف نظر شده است و تأخیر صف‌بندی ارسال بسته‌ها[a213] به عنوان تأخیر اصلی درنظر گرفته شده است.
در شبکههای TDMA همانند شبکههای WiMAX مش تأخیر به این شکل اتفاق میافتد که زمانبندی لینکها در هرفریم به طور مناسب انتخاب نشده باشد. به عبارت دیگر لینکی که بستهها از طریق آن منتقل میشود، زودتر از رسیدن بستهها، برای ارسال زمان بندی شود ویا زمال ارسال بسته به ایستگاه مرکزی(و یا بلعکس) پس از موعد[a214] سررسید154 آن بسته باشد. برای روشن شدن مطلب شکل(4-4) را در نظر بگیرید. مدت زمان ارسال درخواست گره‌‌‌ 6 (رنگ زرد[a215]) به ایستگاه [a216]مرکزی 8 میلی ثانیه طول می‌کشد(ارسال گره‌‌‌ 6 به BS از طریق رله 2 و3) که این زمان از مدت زمان 4.5 میلی ثانیه سررسید بیشتر است و عملا ارسال آن بیهوده و علاوه بر ارسال نادرست منجر به ایجاد تأخیر ارسال برای سایر گره‌‌‌ها می‌شود.

ب
الف
شکل ‏44- زمان‌بندی ارسال نمونه برای 3 گره‌‌‌ با 2 رله
استفاده مجدد فرکانسی155
یکی از مسائلی که باعث تاثیر فراوان در بهبود گذردهی شبکه‌‌ها می شود، استفاده مجدد فرکانسی یا استفاده مجدد فضائی156 است.

پایان نامه
Previous Entries دانلود پایان نامه با موضوع زمانبندي، BS، ترافيک، پهناي Next Entries دانلود پایان نامه با موضوع لينک، پنجره‌هاي، لینکهای، زماني