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

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

استفاده مجدد فرکانسی به لینک‌هایی که از نظر مکانی به اندازه کافی از هم دور هستند اجازه می‌دهد که به طور هم‌زمان در یک فرکانس مشخص،[a217] بدون این که باهم تداخلی داشته باشند، داده خود را ارسال کنند. این روش کاربرد فراوانی در شبکه‌های سلولی دارد. در این شبکه‌ها سلول‌هایی که به اندازه کافی از هم دورند، به طور هم‌زمان‌ از یک فرکانس برای ارسال استفاده می‌کنند. برای روشن شدن کاربرد این روش در شبکه‌های بی‌سیم مش، شکل (4-5) را در نظر بگیرید. این شکل شامل یک ایستگاه مرکزی و 4 گره‌‌‌ رله می‌‌‌‌‌‌باشد و لینک‌های درخت زمان‌بندی با خطوط ممتد و لینک‌های[a218] ‌تداخلی با خطوط خط چین نمایش داده‌شده‌اند.

شکل ‏45- توپولوژی شبکه‌ی مش نمونه با 4 گره‌‌‌ رله
در این شکل می‌خواهیم نشان دهیم که اگر برای مثال در مسیر فراسو، گره‌‌‌ی از طریق لینک 9 به ایستگاه مشترک 4 ارسال کند، چه لینک‌هایی قادر خواهند بود در همین شیار زمانی به طور هم‌زمان ارسالی بدون رخ دادن تصادم داشته باشند. ابتدا باتوجه به تداخل اولیه و ثانویه، لینک‌هایی که با لینک 9 تداخل دارند را مشخص می‌کنیم.
1، 2، 4، 5،10 I9 =
همانطور که ملاحظه می‌شود[a219]، هنوز لینکهایی در شبکه هستند که میتوانند بدون رخ دادن تصادم به طور همزمان با لینک 9 ارسال کنند. میتوان[a220] از لینکهایی باقیمانده (لینک های 3، 6، 7، 8 و 11)، لینک شماره 11 را انتخاب کرد[a221]. لینکهای متداخل با این لینک عبارتند از: 2، 3، 5، 6، I11 =7
باتوجه به لینکهای متداخل I9 ، I11 مشاهده می‌شود[a222] که هنوز لینک شمارهی 8 قادر خواهد بود در همین شیار زمانی بدون رخ دادن تصادم ارسال کند. لینکهای متداخل این لینک نیز[a223] عبارتند از: 2، 3، 6، I8 =7
باتوجه به اینکه I8 شامل لینکهای 9 و 11 نمیباشد. لذا میتوان گفت لینکهای 8 ، 9 و 11 میتوانند بدون اینکه تداخلی باهم داشته باشند در یک شیار زمانی به طور همزمان ارسال کنند. با توجه به لینکهای متداخل I8، I9، I11 دیگر لینکی در شبکه باقی نمیماند که با لینک های 8، 9 و 11متداخل نباشد، لذا در یک شیار زمانی مشخص تنها[a224] این 3 لینک می توانند بدون تداخل باهم ارسال موفق داشته باشند.
استفاده مجدد فرکانسی نقش بهسزایی در شبکه‌های بی سیم مش ایفا میکند. بهبود گذردهی این راهکار در شبکههای وسیع با تعداد گره‌های بالا بسیار چشم‌گیر است. این روش حتی در شبکه‌های زنجیره‌ای کاربرد فراوان دارد. برای مثال شبکه زنجیره‌ای شکل (4-6) را در نظر بگیرید، این شکل شامل یک ایستگاه مرکزی و 10 ایستگاه مشترک می‌باشد. باتوجه به بحث استفاده مجدد فرکانسی لینک‌هایی که در زیر مشخص شدهاند، می توانند هریک در یک شیار زمانی مشخص ارسال همزمان داشته باشند. (فرض براین است که[a225] کلیه ارسالها در مسیر فراسو صورت گرفته است).
لینک هایی که در فرصت ارسالی اول می‌توانند باهم ارسال کنند: 1، 4، 7، 10
لینک هایی که در فرصت ارسالی دوم می‌توانند باهم ارسال کنند: 2، 5، 8
لینک هایی که در فرصت ارسالی سوم می توانند باهم ارسال کنند: 3، 6، 9
همان‌طور که ملاحظه گردید[a226]، با بکارگیری استفاده مجدد فرکانسی، گذردهی این شبکه به بیش از سه برابر افزایش مییابد. چرا که درصورت عدم بکارگیری، ارسال کلیه لینکها در مسیر فراسو در 10 فرصت ارسالی صورت می‌گرفت. شایان ذکر است کلیه ارسال‌ها[a227] در مسیر فروسو هم[a228] به همین ترتیب در 3 فرصت ارسالی صورت میپذیرد، لذا به طورکلی می توان گفت با این راهکار کلیه ارسالات در مسیر فروسو و فراسو در 6 فرصت ارسالی بدون رخ دادن تصادم انجام می‌پذیرد.

شکل ‏46-توپولوژی شبکه مش زنجیره‌ای شامل ایستگاه مرکزی و گره‌‌‌های رله
دسته‌بندی الگوریتم‌های زمان‌بندی
با توجه به شرایط[a229] مسئله و مجموعه ورودی‌ها، الگوریتم زمان بندی در شبکه های مش بی سیم چندگامی تلاشی در جهت اتخاذ تکنیکی برای اختصاص منابع به لینک های مش برای رسیدن به اهداف خاص است. شکل(4-7) چهارچوب دسته بندی برای زمان بندی در شبکه های مش چندگامی بر اساس 1) شرایط 2) ورودی‌ها 3) اهداف و 4) روش‌ها[a230] را نشان‌می‌دهد.

شکل ‏47-چهارچوب دسته‌بندی برای بررسی الگوریتم‌های زمان‌بندی
بُعد اول، چهارچوب طبقه بندی مکانیسم زمان بندی را بر اساس نوع کنترل زمان بندی، نوع پروتکل دسترسی مسیر، نوع آنتن و نوع پیکربندی شبکه در نظر گرفته شده دسته بندی می کند که در شکل(4-8) نشان داده شده است.
نوع کنترل زمان بندی می‌تواند متمرکز و یا توزیع یافته باشد. نوع پروتکل دسترسی[a231] کانال CSMA یا TDMA است. به خصوص استاندارد مش WiMAX، پروتکل مش چندگامی مبتنی بر TDMA را به کار می‌برد. سپس نوع آنتن می‌تواند همه جهته و یا جهت دار [a232]باشد. پیکربندی شبکه، درخت یا نمودار طبقه بندی پویا درنظر گرفته‌ می‌شود. توپولوژی درخت عمدتاً در مکانیسم های زمان بندی مش 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 بر مبناي ترافيک درخواستي آنها، تعداد نشانه‌هاي مشخصي اختصاص داده مي‌شود. هر گره‌‌‌ مي‌تواند به اندازه

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