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

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

کاربران بیشتری پیدا می‌کند که این امر به نوبه ی خود سرویس دهندگان را از لحاظ اقتصادی در موقعیت بهتری قرار می‌دهد تا بتوانند سرویس هایی ارزان تر و با کیفیت بهتر ارائه کنند.

تعريف مسئله
در مسئله زمان‌بندی[a14] جهت ارسال بسته‌ها بين گره‌‌‌های درخواست کننده به BS از طریق رله‌ها در شبکه‌های مش بی‌سیم با رویکرد تضمین تأخیر انتها به انتها نياز به درخواست و تخصيص پنجره‌هاي زماني است. پنجره‌هاي زماني به دو بخش با مديريت متمرکز و مديريت توزيع شده تقسيم مي‌شوند. در مکانيزم متمرکز، که براي هدايت ترافيک اينترنت SS ها از طريق BS بکار برده مي‌شود، BS مسئول زمانبندي ارسال‌ها در کل شبکه است. لذا زمانبندي در سطح شبکه انجام مي‌شود. از آنجا که در اين مکانيزم تمام بسته‌هاي کنترلي و ديتا از BS عبور مي‌کنند، زمانبندي بصورت متمرکز و با قابليت اطمينان بالا مي‌باشد. با اين حال تاخير برپايي اتصال‌ها زياد است. در مکانيزم توزيع شده، که براي ارتباط بين گره‌‌‌ها و هدايت ترافيک اينترانت(در داخل شبکه مش)استفاده مي‌شود، ارسال‌ها به شکل کاملا توزيع شده و بدون نياز به تعامل با BS زمانبندي مي‌شوند. از آنجا که در اين مکانيزم تصميم گيري‌ها توسط گره‌‌‌ها بطور محلي و با توجه به بار ترافيکي و شرايط کانال فيزيکي گره‌‌‌ها صورت مي‌گيرد، مکانيزم توزيع شده نسبت به مکانيزم متمرکز پویاتر، ولي پيچيده‌تر و داراي سربار بيشتر است. از آنجا که ترافيک اينترنت، عمده ترافيک شبکه را تشکيل مي‌دهد، مکانيزم زمانبندي متمرکز، مکانيزم غالب مي باشد.
[4] کارايي زمانبندي‌هاي متمرکز و توزيع شده در شبکه مش بی سیم را با هم مقايسه کرده است. نتيجه مطالعات نويسندگان نشان مي‌دهد که براي ترافيک دراز مدت و پايدار به/ از BS، زمانبندي متمرکز نسبت به زمانبندي توزيع شده سربار کمتري دارد.
در بحث زمان‌بندي ارسال‌ها در شبکه‌های مش بی‌سیم با دو موضوع روبرو هستيم:
تعيين زمان ارسال پيغام‌هاي کنترلي
اختصاص پنجره‌هاي زماني در زير فريم ديتا به گره‌‌‌هاي شبکه براي حمل ترافيک کاربران
در استانداردهای مختلف الگوريتم زمانبندي براي ارسال پيغام‌هاي کنترلي مشخص شده است. ولی[a15] در ارتباط با زمانبندي ارسال ديتا، اگرچه نحوه سيگنالينگ و ساختار پيغام‌ها مشخص شده است، جزئيات الگوريتم زمانبندي و نحوه دسترسي کارا[a16] ی گره‌‌‌ها به کانال و رزرو پنجره‌هاي زماني در[a17] زير فريم ديتا در متن استاندارد نيامده و به زمان پياده‌سازي استاندارد موکول شده است. در اين پايان نامه تمرکز بر روي جنبه دوم يعني اختصاص پنجره‌هاي زماني در زير فريم ديتا با مديريت متمرکز مي باشد.
فرض کنيم درخواست پهناي باند انتها به انتهاي گره‌‌‌ها توسط BS جمع‌آوري شده است. بر اين اساس BS بايد پنجره‌هاي زماني بخش متمرکز زيرفريم ديتا در يک يا چند فريم را، به لينک‌ هايي که ارسال‌ها بر روي آنها انجام خواهد شد[a18]، تخصيص دهد. هدف آن است که:
تعداد پذیرش گره‌‌‌ با درخواست‌های انتها به انتهای ارسال در شبکه به/از BS با درنظرگرفتن سررسید11 بیشینه باشد.
بررسی پیشینه کار
مطالعه برروی زمانبندی در شبکه‌های مبتنی بر تکنولوژی TDMA سال‌های زیادی است که مورد توجه بوده و نتایج فراوانی[a19] ارائه شده است. الگوریتم‌های زمانبندی ارائه شده در برخی از[a20] این کارها، از روش‌های رنگ آمیزی گراف برای یافتن زمانبندی با مینیمم طول فریم، استفاده می‌نمایند. [12، 11، 10، 9، 8، 7، 6، 5] در این روش‌ها، شبکه بی‌سیم به شکل یک گراف تداخل مدل شده است. رئوس این گراف لینک‌ها هستند. همچنین لبههای گراف وجود تداخل مابین لینک‌هایی که در دو سر یک لبه هستند را نشان می دهند. دو لینک باهم تداخل دارند اگر ارسال همزمان آنها باعث تداخل بسته‌های ارسالی آنها شود. اگر در رنگ‌آمیزی رئوس گراف تداخل، رنگ‌ها به عنوان پنجره‌های زمانی در نظر گرفته شوند، حاصل یک زمانبندی TDMA عاری از تداخل است. یک رنگ‌آمیزی با مینیمم رنگ مورد نیاز، معادل یک زمانبندی با مینیمم طول است که گذردهی سیستم را ماکزیمم می‌نماید.
در [7]، الگوریتمی با زمان چند جمله‌ای ارائه شده است که می‌تواند یک زمانبندی با مینیمم طول را برای اختصاص پهنای باند درخواستی فراهم آورد. نویسندگان مقاله فرض کرده‌اند که تنها تداخلی که[a21] در شبکه وجود دارد مابین لینک‌هایی است که یک گره‌‌‌ مشترک دارند (تداخل نوع اول12). بنابراین با این فرض شرایط زمانبندی بدون تداخل را تعریف کرده‌اند. الگوریتم‌های زمانبندی مبتنی بر رنگآمیزی لبه در گراف همبندی، الگوریتمهای تطبیقی13 گفته میشوند. یک تطبیق، مجموعهای مستقل از لبههای گراف است. دو لبه مستقل هستند اگر یک راس مشترک نداشته باشند. اگر تداخل نوع اول را بایک گراف تداخل مدل کنیم، که در آن لینک‌ها رئوس و تداخل میان لینک‌ها لبه‌های گراف هستند، تطبیق در گراف همبندی متناظر با یک مجموعه مستقل رئوس در گراف تداخل می‌باشد.
در [10، 9] فرض شده است که تداخل نوع دوم را می‌توان در شبکه حذف کرد و زمانبندی را با رنگ آمیزی نسخه چند لبه‌ای14 از گراف همبندی، انجام داد. تعداد لبه‌های مابین دو گره‌‌‌، متناسب با نرخ ارسال درخواستی میان آن دو گره‌‌‌ است. باانجام عملیات لازم می‌توان تداخل نوع دوم را از زمانبندی به دست آمده با رنگ‌آمیزی لبه حذف کرد [12] ، ولی در این روش باید تمام لینک‌ها نرخ یکسانی داشته باشند. اگر برای لینک‌هایی که دو گام یا بیشتر باهم فاصله دارند، رنگ‌های متفاوتی در نظر گرفته شود، می‌توان روش رنگ‌آمیزی لبه را به گونه‌ای توسعه داد که تداخل نوع دوم را نیز مد نظر قرار دهد [11]. این روش تخمینی از تداخل نوع دوم ارائه می‌دهد. تعیین دقیق تداخل نوع دوم باتوجه به گراف تداخل شبکه صورت می‌گیرد [5].
با این حال بسیاری از الگوریتم‌هایی که برای زمانبندی TDMA ارائه شده است، قابل اعمال به مدل مسئله [a22]مورد بحث نیستند. دو دلیل اصلی برای این ادعا وجود دارد. اول اینکه، در بسیاری از این کارها [10، 9، 8، 7] مدل تداخل بکار برده شده ناقص بوده و تمام تداخل‌هایی که ممکن است در شبکه‌های بی‌سیم مبتنی بر TDMA به وجود بیاید را در نظر نگرفته‌اند. بلکه تنها تداخل مابین لینک‌هایی که یک گره‌‌‌ مشترک دارند، در نظر گرفته شده است. این[a23] امکان وجود دارد که با تخصیص فرکانس‌های متعامد به لینک‌هایی که دچار تداخل نوع دوم هستند، این تداخل را حذف کرد. با این حال، تخصیص این فرکانس کار آسانی نیست [14، 13] همچنین استانداردهای موجود موضوع فرکانس‌های چندگانه را به طور کامل روشن نکرده اند. این بدان معنا است که ارائه هر راه حلی که از فرکانس‌های مختلف استفاده می‌نماید، نیاز به تکمیل استاندارد دارد.
دومین دلیل این است که مطالعات صورت گرفته تضمین تأخیر انتها به انتها و سربار ارسال را نادیده گرفته‌اند. در روشهای رنگ آمیزی [10، 9، 8، 7] قبل از رنگآمیزی لینکها، به پنجرههای زمانی در فریم رنگ‌های متفاوتی تخصیص داده میشود. پس از رنگآمیزی، هر لینک مجموعهای از رنگهایی را در اختیار دارد که با رنگهای مورد استفاده توسط لینکهایی که با آنها تداخل دارد متفات است. از آنجا که رنگها متناظر با پنجرههای زمانی هستند، تخصیص پنجرههای زمانی نیز بدون تداخل میباشد. با این حال این روش به لینکها این اجازه را میدهد که چندین بار در یک فریم بدون درنظرگفتن کیفیت سرویس اقدام به ارسال کنند. برای مثال اگر به یک لینک دو رنگ برای ارسال تخصیص داده شده باشد و این رنگ متناظر با پنجرههای زمانی پشت سرهم نباشند، این لینک دوبار در فریم اقدام به ارسال هجمه[a24]15های دیتای خود می نماید. به عنوان مثال در استاندارد 802.16 با ارسال دوم، لینک حداقل پهنای باندی به اندازه 28.8 kbps را در مدولاسیون و کدینگ BPSK-1/2 از دست می‌دهد. در
مدولاسیون و کدینگ 64QAM-3/4، این میزان برای فریمی با طول 10ms، 259kbps است. الگوریتمهای مکاشفه‌ای16 متعددی نیز به طور مشخص برای شبکههای مش بی‌سیم ارائه شده است. البته کارهای انجام شده در زمینه زمانبندی توزیع شده با درنظر گرفتن تضمین تأخیر انتها به انتها بسیار محدود بوده [13] و الگوریتمهای موجود تلاشی در جهت ارائه بازدهی بیشتر هستند. الگوریتم‌های ارائه شده در مراجع [20، 19، 18، 17، 16، 15، 14] راهکارهایی را برای زمانبندی متمرکز ارائه می‌کنند که در مدل تداخل خود، تداخل نوع دوم را در نظر گرفته و از مزایای استفاده مجدد از فضای فرکانسی17 نیز در زمانبندی بهره میبرند. در [14] و [15] به منظور افزایش کارایی زمان‌بندی طرح لایه متقابل18 آگاه از تداخلی[a25] مورد مطالعه قرارگرفته است. در این مطالعات، مسیریابی براساس یک چارچوب درختی است که در کنار آن از یک زمانبند آگاه از تداخل استفاده میشود. در [16] نیز طراحی لایه متقابل دیگری میان لایههای شبکه (مسیریابی) و MAC (زمانبندی) معرفی شده است، که به مسئله تشکیل درخت مسیریابی و زمانبندی به طور همزمان پرداخته است. در[19] مسئله زمانبندی متمرکز و تخصیص کانال برای حالتی که از چند کانال دیتا برای ارسال استفاده می‌شود، مورد توجه قرار گرفته است. اگرچه این الگوریتمها استفاده مجدد از فضای فرکانسی را بکار میبرند ولی با این حال از آنجا که به هر گره‌‌‌ اجازه داده می‌شود که در یک فریم چندین بار ارسال کند، سربار سوئیچینگ بین گره‌‌‌ها، جهت ارسال و دریافت به علت وجود سمبل‌های محافظ19 بین پنجرههای زمانی گره‌‌‌های مختلف، در نظر گرفته نشده است. در مقابل [20] زمانبندی لینکها در فریم را به یکبار محدود میکند. این فرض نیز از بکارگیری موثر استفاده مجدد از فضای فرکانسی، جلوگیری میکند. مقاله [21] تحقیق و مطالعه ی ارزشمندی است که در زمینه تضمین تأخیر انتها به انتها صورت گرفته است.تلاش‌های قبلی در راستای ارائه خدمات سرویس صرفا تلاشی برای بهبود متوسط کل تأخیر شبکه بوده و تضمینی در ارائه خدمات سرویس انتها به انتهای کاربر ارائه ‌نکرده اند.
فصول بعدی این نوشتار

ساختار پایان نامه بدین شکل تدوین یافته است: در ادامه در فصل 2 شبکه‌های مش بی‌سیم با رویکردهای مختلفی مورد بحث و چالش قرار گرفته است. در فصل 3، مشخصات فني استاندارد 802.16 به عنوان یک نمونه شبکه‌مش بی‌سیم پرکاربرد در زمان نگارش این پایان نامه تشريح شده است. در اين فصل به بررسي لايه‌هاي فيزيکي و MAC توصيف شده توسط استاندارد 802.16 پرداخته و در ادامه جزئيات عملکرد مد مش استاندارد تشريح شده است. مفاهيمي که در اين راستا آورده شده است، از جمله ساختار فريم در مد مش، بسته‌هاي کنترلي و نحوه ورود گره‌‌‌هاي تازه وارد به شبکه، پيش زمينه‌اي براي شروع بحث زمانبندي در مد مش استاندارد هستند. در فصل 4 با مروری بر تحقیقات قبلی این زمینه سعی بر آن است کارهای قبلی که در زمینه‌ی زمان‌بندی انجام شده است در قالب چهارچوب پیشنهادی ارائه، دسته بندی و مقایسه شوند. فصل 5 الگوريتم جديدي را براي بهبود زمانبندي متمرکز در مد مش استاندارد 802.16 ارائه مي‌کند. در اين فصل ابتدا فلسفه‌ي طراحي الگوريتم پيشنهادي و نحوه پياده‌سازي آن برپایه الگوریتم ژنتیک تشريح شده و سپس با تعريف انواع سناريوها و شرایط شبيه‌سازي به ارائه نتايج حاصل از شبيه‌سازي و مقايسه الگوريتم پيشنهادي با الگوريتم‌هاي موجود، بر اساس معيارهاي ارزيابي، پرداخته شده است. در نهایت در فصل ۶ نيز جمع‌بندي مطالب و کارهاي پيشرو بیان شده است.
جمع‌بندی
شبکه‌های مش بی‌سیم یکی از فناوری‌های کلیدی و تاثیرگذار طی دهه پیش رو هستند و نقش بسیار مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رویایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان و هر لحظه و با نهایت سادگی و کمترین هزینه.
شبکه‌ی مش بی‌سیم برای پاسخگویی به نیازهای روزافزون کاربران باید بتواند سطوح مختلفی از کیفیت سرویس را ارائه و با برقراری آن کیفیت‌ها را تضمین کند .منابع شبکه

پایان نامه
Previous Entries دانلود پایان نامه با موضوع تجارت الکترونیکی، انتظارات کاربران، تجارت الکترونیک Next Entries دانلود پایان نامه با موضوع جمع آوری اطلاعات، قابلیت اطمینان