عنوان کامل پایان نامه :زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم

تکه هایی از این پایان نامه :

1-1   مطالعه پیشینه کار

مطالعه برروی زمانبندی در شبکه‌های مبتنی بر تکنولوژی TDMA سال‌های زیادی می باشد که مورد توجه بوده و نتایج فراوانی ارائه شده می باشد. الگوریتم‌های زمانبندی ارائه شده در بعضی از این کارها، از روش‌های رنگ آمیزی گراف برای یافتن زمانبندی با مینیمم طول فریم، بهره گیری می‌نمایند. [12، 11، 10، 9، 8، 7، 6، 5] در این روش‌ها، شبکه بی‌سیم به شکل یک گراف تداخل مدل شده می باشد. رئوس این گراف لینک‌ها هستند. همچنین لبه­های گراف وجود تداخل مابین لینک‌هایی که در دو سر یک لبه هستند را نشان می دهند. دو لینک باهم تداخل دارند اگر ارسال همزمان آنها باعث تداخل بسته‌های ارسالی آنها گردد. اگر در رنگ‌آمیزی رئوس گراف تداخل، رنگ‌ها به عنوان پنجره‌های زمانی در نظر گرفته شوند، حاصل یک زمانبندی TDMA­ عاری از تداخل می باشد. یک رنگ‌آمیزی با مینیمم رنگ مورد نیاز، معادل یک زمانبندی با مینیمم طول می باشد که گذردهی  سیستم را ماکزیمم می‌نماید.

در [7]، الگوریتمی با زمان چند جمله‌ای ارائه شده می باشد که می‌تواند یک زمانبندی با مینیمم طول را برای اختصاص پهنای باند درخواستی فراهم آورد. نویسندگان مقاله فرض کرده‌اند که تنها تداخلی که در شبکه هست مابین لینک‌هایی می باشد که یک گره‌‌‌ مشترک دارند (تداخل نوع اول[1]). پس با این فرض شرایط زمانبندی بدون تداخل را تعریف کرده‌اند. الگوریتم‌های زمانبندی مبتنی بر رنگ­آمیزی لبه در گراف همبندی، الگوریتم­های تطبیقی[2] گفته می­شوند. یک تطبیق، مجموعه­ای مستقل از لبه­های گراف می باشد. دو لبه مستقل هستند اگر یک راس مشترک نداشته باشند. اگر تداخل نوع اول را بایک گراف تداخل مدل کنیم، که در آن لینک‌ها رئوس و تداخل میان لینک‌ها لبه‌های گراف هستند، تطبیق در گراف همبندی متناظر با یک مجموعه مستقل رئوس در گراف تداخل می‌باشد.

در [10، 9] فرض شده می باشد که تداخل نوع دوم را می‌توان در شبکه حذف نمود و زمانبندی را با رنگ آمیزی نسخه چند لبه‌ای[3] از گراف همبندی، انجام داد. تعداد لبه‌های مابین دو گره‌‌‌، متناسب با نرخ ارسال درخواستی میان آن دو گره‌‌‌ می باشد. باانجام عملیات لازم می‌توان تداخل نوع دوم را از زمانبندی به دست آمده با رنگ‌آمیزی لبه حذف نمود [12] ، اما در این روش بایستی تمام لینک‌ها نرخ یکسانی داشته باشند. اگر برای لینک‌هایی که دو گام یا بیشتر باهم فاصله دارند، رنگ‌های متفاوتی در نظر گرفته گردد، می‌توان روش رنگ‌آمیزی لبه را به گونه‌ای توسعه داد که تداخل نوع دوم را نیز مد نظر قرار دهد [11]. این روش تخمینی از تداخل نوع دوم ارائه می‌دهد. تعیین دقیق تداخل نوع دوم باتوجه به گراف تداخل شبکه صورت می‌گیرد [5].

  1. Primary Interference
  2. Matching
  3. شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید

  4. Multi-edged

 متن فوق بخش هایی از این پایان نامه بود

می توانید به لینک پایین صفحه مراجعه نمایید: