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

word
133
8 MB
31349
1392
کارشناسی ارشد
قیمت: ۱۷,۲۹۰ تومان
دانلود فایل
  • خلاصه
  • فهرست و منابع
  • خلاصه پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم

    پایان نامه کارشناسی ارشد مهندسی برق- مخابرات

    چکیده

     

    شبکه‌های مش بی‌سیم یکی از تکنولوژی‌های مورد توجه برای ایجاد شبکه‌های بی‌سیم نسل بعد هستند. زیرا این شبکه‌ها می‌توانند به دلیل افت مسیر کمتر و نیز کاهش اثر عامل سایه افکنی، که ناشی از خصوصیت چند گامی بودن آنهاست، محدوده تحت پوشش وسیع و ظرفیت بالایی را با مصرف توان کم و هزینه پایین در اختیار کاربران قرار دهند. در مقابل این مزایا، این شبکه‌ها با مشکل عدم توسعه پذیری آسان مواجه‌ هستند. زیرا ترافیکی که توسط چند واسط رله می‌شود به عرض باند بیشتر نیاز دارد، دچار تأخیر بیشتر شده و لذا کیفیت سرویس کاهش می‌یابد. بزرگتر کردن فاصله رله‌ها به منظور کاهش تعداد آن‌ها نیز باعث کاهش سرعت لینک‌ها خواهد شد. افزایش تعداد کاربران شبکه نیز منجر به برخورد‌های بیشتر و درنتیجه کاهش بیشتر گذردهی می‌گردد. افزایش ناحیه تحت پوشش شبکه نیز به دلیل احتیاج به رله‌های بیشتر افت گذردهی و افزایش تأخیر را در پی خواهد داشت.بنابراین کارایی مناسب در یک شبکه مش باید از طریق حل یک مسئله بهینه‌سازی که عوامل مؤثر(نظیر تأخیر، گذردهی و ...) در آن گنجانده شده باشد دست آید. حل این نوع مسئله در سال‌های اخیر به عنوان یک مسئله NP-Hard توجه زیادی را در  حوزه مسائل مربوط به شبکه‌های بی‌سیم مش به خود معطوف کرده است.

    در این پایان نامه الگوریتم جدیدی به منظور بهبود زمانبندی متمرکز  و تخصیص بهینه پنجره‌های زمانی به گره‌‌‌های شبکه با در نظرگرفتن قابلیت استفاده مجدد از فضای فرکانسی، بارویکرد تضمین تأخیر انتها به انتهای کاربر ارائه شده است. الگوریتم پیشنهادی در این تحقیق برای حل تقریبی مسئله بهینه‌سازی زمان‌بندی، برپایه‌ی الگوریتم ژنتیک است. الگوریتم پیشنهادی  قابلیت تطبیق پذیری با پارامتر‌های مختلف(نظیر بازدهی، عدالت و ...) بر اساس خواسته‌ی اپراتور را داراست. نتایچ حاصل از پیاده‌سازی موید بهبود نتایج نسبت به روش‌های پیشین است.

    1-1   مقدمه، چشم انداز شبکه‌های مش بی‌سیم

    رواج بیش از حد اینترنت دردنیای ارتباطی امروز به گونه ای بوده است که ساختارهای دستیابی سیم دار پر سرعت

    پاسخگوی نیاز بسیاری از مناطق نیستند .تعداد مراکز سرویس دهنده خدمات پر سرعت اینترنت امروزی به نسبت تقاضا بسیار کم است. کابل کشی خطوط پر سرعت برای تمامی این سرویس دهندگان بسیار پر هزینه و زمان بر است . امروزه تکنولوژی‌های[a1]  جدیدی معرفی شده است تا جایگزین این شبکه های سیم دار شوند. این شبکه های جایگزین ، شبکه‌های بی‌سیم پر سرعت هستند که امکان دسترسی سریع به اینترنت در مواقعی که ساختار شبکه سیم دار به دلیل حجم بالای متقاضی و یا قدیمی بودن شبکه ها ، قادر به پاسخگویی به نیاز کاربران نیست را فراهم می‌آورند و هزینه‌های اضافی مرتبط به روز رسانی ساختار کابل کشی‌ها را از بین می‌برند. سیستم های بی‌سیم سنتی اغلب برای اهداف تجاری درمحل هایی که سرعت و دقت بالا نیاز است استفاده می‌شوند و در موارد شخصی و یا خانه‌ها می‌بایست تکنولوژی ارزان را به کار گرفت. هم اکنون پیشرفت های تکنیکی این امکان را فراهم ساخته اند و فرصت های بسیاری را برای سرویس دهندگان اینترنت ایجاد کرده اند. شبکه‌های مش بی‌سیم [1] (WMN) یکی از فناوری‌های کلیدی و تأثیرگذار طی دهه پیش رو است که نقش بسیار [a2] مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رؤیایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان ، هر لحظه، با نهایت سادگی و کمترین هزینه.

     

     

    این شبکه‌ها شامل مسیریاب‌های مش [a3] و نیز کاربران مش می‌شوند که در آن مسیریاب‌های مش کمترین تحرک ممکن را دارند و ستون فقرات WMN را شکل می‌دهند. آنها دسترسی به شبکه را هم برای کاربران مش و هم برای کاربران عادی فراهم می‌آورند.

    شکل  ‏1‑1-  شبکه‌ی مش بی‌سیم

      شبکه مش بی سیم کاملا منطبق بر ساختار شبکه سیم دار است و هر فرستنده امکان دسترسی کاربران متصل به آن

    را به اینترنت فراهم می‌کند و به صورت جزئی از ساختار شبکه عمل خواهد کرد. ترافیک شبکه از بین چندین [a4] رله

    گذر خواهد کرد و امکان اتصال ایستگاه‌های مختلف را حتی اگر خارج از محدوده شبکه باشند، فراهم می آورد. شبکه‌های مش  بی‌سیم انعطاف پذیرترین و کم هزینه ترین روش برای گسترش سرویس‌های پر سرعت اینترنت هستند که به صورت عمده در مصارف شخصی قابل استفاده اند.

    هر رله‌ی بی‌سیم در این شبکه به عنوان عنصری از ساختار شبکه است و می‌تواند اطلاعات را از شبکه مش بی‌سیم به مقصد برساند. این نوع شبکه مشکلات وجود موانع در حیطه محیط رادیویی را از بین می‌برد و بسیار ارزان و راحت، شبکه را قابل گسترش می‌کند، زیرا در این ساختار هر رله فقط نیاز به برقراری ارتباط با رله مجاور خود دارد . ترافیک شبکه‌ای در صورت بروز هر مانع ، می‌تواند به سمت رله دیگر تغییر جهت می‌دهد، البته بدون آنکه نیازی به هر گونه تغییر در محل رادیوی مر کزی برای ارتباط بامکان های جغرافیایی دور دست باشد .

    از آنجائیکه منطقه تحت پوشش هر نقطه دسترسی می‌تواند در اطراف موانع گسترش یابد، بنابراین تعداد نقاط دسترسی کاهش می یابد.

      شبکه های مش بی‌سیم، دارای تکنولوژی ارزان قابل گسترش و برای دسترسی پر سرعت در محدوده های جغرافیایی دور دست مناسب هستند . RoofNet[a5]  نمونه ای از این شبکه هاست. این شبکه معمولا شامل تعدادی نقاط دسترسی بی‌سیم است که درپنجره ها و پشت بام منازل نصب می شود و بسترهای اطلاعاتی کامپیوترهای خانگی توسط سیم به آنتن ها انتقال می‌یابد و از یک آنتن به آنتن دیگر منتقل می شود تا به یک دروازه[2] اینترنتی برسد[a6] .

    در شبکه‌های مش بی‌سیم  ترافیک هر SS[3] توسط رله‌های شبکه برای انتقال به اینترنت یا شبکه خارجی دیگر به سمت BS[4] هدایت می‌شود (شکل (1-2)).

    شکل  ‏1‑2- انتقال ترافیک SS به BS از طریق[a7]  رله‌ها

    یکی از استاندارد‌های پرکاربرد رایج که از شبکه‌های مش بی‌سیم در ساختار خود پشتیبانی می‌کند[a8]   استاندارد 802.16 با نام تجاری WiMAX[5]  است. این استاندارد  پروتکل کنترل دسترسی به رسانه انتقال را برای شبکه‌های بی‌سیم شهری تعریف می‌کند. در این استاندارد تمهیداتی برای پشتیبانی از کیفیت سرویس، در حد و اندازه‌های کیفیت شبکه‌های دسترسی کابل کشی شده، اندیشیده شده است.  به کمک مد مش استاندارد 802.16،  می‌توان به سرعت اتصال‌های بی‌سیم[a9]  قابل اطمینانی با سطح پوشش بسیار بیشتر از شعاع قابل دسترس در لایه فیزیکی فراهم آورد. لذا مد مش استاندارد 802.16 با MAC مبتنی بر تکنولوژی TDMA راه‌حل مناسبی برای پیاده‌سازی شبکه‌های مش بی‌سیم است. شبکه‌های مش بی‌سیم، شبکه‌های چندگامی ثابتی هستند که به منظور فراهم آوردن  دسترسی بی‌سیم در ناحیه‌ی جغرافیایی وسیعی بکار گرفته می‌شوند[1و2و3]. چالش اصلی در این شبکه‌ها ارائه کیفیت سرویس بالا برای کاربران آنها است. استاندارد 802.16 با معرفی یک MAC جدید که از تکنولوژی TDMA استفاده می‌نماید، قابلیت ارائه کیفیت سرویس را برای این شبکه‌ها ارائه می‌کند.

    1-2   ضرورت تضمین کیفیت سرویس، چالش اصلی در شبکه‌های مش بی‌سیم

    رشد سریع شبکه‌های بی‌سیم هم زمان با ایجاد سرویس‌های جدید، موضوعات تحقیقاتی بسیار متنوعی را در این شبکه‌ها مطرح کرده است. در این بین، بسیاری از این مسایل به تضمین کیفیت سرویس مربوط می‌شود. یک پارچه

    شدن شبکه‌ها‌ی انتقال داده، صوت و تصویر نیاز به [a10] سرویس‌های متنوعی را موجب می‌شود. در چنین محیطی و برای ایجاد یک شبکه‌ی مناسب که در آن انتظارات کاربران به نحوی رضایت بخش تأمین شود، کنترل رفتار شبکه به منظور تضمین کیفیت سرویس کاربران مختلف اهمیت ویژه‌ای می‌یابد. نکته ی مهمی که در این حال نباید دور از ذهن بماند، بهره وری اجزا و منابع شبکه است. درغیر این صورت قیمت و پیچیدگی تجهیزات لازم برای ارائه‌ی سرویس قابل قبول نخواهد بود.

    در سال های اولیه، اینترنت بیشتر برای ردوبدل کردن اطلاعات بین پژوهشگران شبکه استفاده می‌شد.در آن زمان [a11] پست الکترونیک،ارسال فایل  [6]و دسترسی به شبکه از راه دور [7] اصلی ترین کاربرد های اینترنت بودند. گسترش تقاضا باعث تغییرات عمده‌ای در به کار گیری شبکه ی اینترنت شد. کاربردهای جدید مثل کنفرانس های گروهی صوتی تصویری، مراکز قوی جست و جو در شبکه، تماس تلفنی اینترنتی و تجارت الکترونیکی نیاز به تضمین کیفیت سرویس را گریز ناپذیر کرده است.

    در حال حاضر ارائه ی سرویس در شبکه ی اینترنت به صورت "بهترین[a12]  تلاش[8] "صورت می گیرد که در آن تضمینی برای کیفیت سرویس ارائه شده وجود ندارد. هنگامی که یک کاربر به شبکه دسترسی پیدا می‌کند، ممکن است برخی از قسمت‌های شبکه به دلیل عدم زمان‌بندی مناسب در استفاده از منابع آن قدر پرترافیک باشند که ترافیک منتقل نشود و یا آن قدر تأخیر داشته باشد که عملاً نیاز کاربر را برآورده نکند. خصوصیات سرویس مورد بحث به قرار زیر است:

    شبکه هیچ نوع ترافیکی را به هنگام برقراری ارتباط به علت کمبود منابع لازم جهت ارائه‌ی سرویس رد نمی کند.

    ترافیک تمام کاربران می[a13]  تواند به صورت کاملاً مشابه در شبکه منتقل می شود.

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

    در چنین شبکه‌ای تا زمانی که تأخیر خیلی برای کاربر مهم نباشد مشکلی ایجاد نمی‌شود(مثل سرویس پست الکترونیکی) اما به محض درخواست یک سرویس برخط[9] ، تأخیر و اتلاف داده مهم می‌شود و اگر سرویس به صورت بلادرنگ  [10]ارائه شود کاربر در لحظات پرترافیک ممکن است قادر به ادامه‌ی ارتباط نباشد و یا حتی خود ترجیح دهد ارتباط را قطع کند و در زمان مناسب‌تری شانس خود را امتحان کند.  طبیعی است که سرویس دهندگان اینترنت که از دهه ی 90 به بعد عموماً شرکت‌های خصوصی هستند، به دنبال برطرف کردن نیازهای متنوع مشتریان خود باشند. اگر سرویس دهندگان اینترنت در شبکه‌های بی‌سیم بتوانند سرویسی باکیفیت ارائه کنند روزبه روز کاربردهای جدیدتری به وجود می آید و شبکه کاربران بیشتری پیدا می‌کند که این امر به نوبه ی خود سرویس دهندگان را از لحاظ اقتصادی در موقعیت بهتری قرار می‌دهد تا بتوانند سرویس هایی ارزان تر و با کیفیت بهتر ارائه کنند.

     

    1-3   تعریف مسئله

    در مسئله زمان‌بندی[a14]  جهت ارسال بسته‌ها بین گره‌‌‌های درخواست کننده  به BS  از طریق رله‌ها در شبکه‌های مش بی‌سیم با رویکرد تضمین تأخیر انتها به انتها نیاز به درخواست و تخصیص پنجره‌های زمانی است. پنجره‌های زمانی به دو بخش با مدیریت متمرکز و مدیریت توزیع شده تقسیم می‌شوند. در مکانیزم متمرکز، که برای هدایت ترافیک اینترنت SS ها از طریق BS بکار برده می‌شود،  BS مسئول زمانبندی ارسال‌ها در کل شبکه است. لذا زمانبندی در سطح شبکه انجام می‌شود. از آنجا که در این مکانیزم تمام بسته‌های کنترلی و دیتا از BS عبور می‌کنند، زمانبندی بصورت متمرکز و با قابلیت اطمینان بالا می‌باشد. با این حال تاخیر برپایی اتصال‌ها زیاد است. در مکانیزم توزیع شده، که برای ارتباط بین گره‌‌‌ها  و هدایت ترافیک اینترانت(در داخل شبکه مش)استفاده می‌شود، ارسال‌ها به شکل کاملا توزیع شده و بدون نیاز به تعامل با BS زمانبندی می‌شوند. از آنجا که در این مکانیزم تصمیم گیری‌ها توسط گره‌‌‌ها بطور محلی و با توجه به بار ترافیکی و شرایط کانال فیزیکی گره‌‌‌ها صورت می‌گیرد، مکانیزم توزیع شده نسبت به مکانیزم متمرکز پویاتر، ولی پیچیده‌تر و دارای سربار بیشتر است. از آنجا که ترافیک اینترنت، عمده ترافیک شبکه را تشکیل می‌دهد، مکانیزم زمانبندی متمرکز، مکانیزم غالب می باشد.

    [4] کارایی زمانبندی‌های متمرکز و توزیع شده در شبکه مش بی سیم را با هم مقایسه کرده است. نتیجه مطالعات نویسندگان نشان می‌دهد که برای ترافیک دراز مدت و پایدار به/ از BS،  زمانبندی متمرکز نسبت به زمانبندی توزیع شده سربار کمتری دارد.

    در بحث زمان‌بندی ارسال‌ها در شبکه‌های مش بی‌سیم با دو موضوع روبرو هستیم:

    تعیین زمان ارسال پیغام‌های کنترلی

    اختصاص پنجره‌های زمانی در زیر فریم دیتا به گره‌‌‌های شبکه برای حمل ترافیک کاربران

    در استانداردهای مختلف الگوریتم زمانبندی برای ارسال پیغام‌های کنترلی مشخص شده است. ولی[a15]  در ارتباط با زمانبندی ارسال دیتا، اگرچه نحوه سیگنالینگ و ساختار پیغام‌ها مشخص شده است، جزئیات الگوریتم زمانبندی و نحوه دسترسی کارا[a16]  ی گره‌‌‌ها به کانال و رزرو پنجره‌های زمانی در[a17]  زیر فریم دیتا در متن استاندارد نیامده و به زمان پیاده‌سازی استاندارد موکول شده است. در این پایان نامه تمرکز بر روی جنبه دوم یعنی اختصاص پنجره‌های زمانی در زیر فریم دیتا با مدیریت متمرکز می باشد.

    فرض کنیم درخواست پهنای باند انتها به انتهای گره‌‌‌ها توسط BS جمع‌آوری شده است. بر این اساس BS باید پنجره‌های زمانی بخش متمرکز زیرفریم دیتا در یک یا چند فریم را، به لینک‌ هایی که ارسال‌ها بر روی آنها انجام خواهد شد[a18] ، تخصیص دهد. هدف آن است که:

     تعداد پذیرش گره‌‌‌ با درخواست‌های انتها به انتهای ارسال در شبکه به/از BS با درنظرگرفتن سررسید[11] بیشینه باشد.

    1-4   بررسی پیشینه کار

                    مطالعه برروی زمانبندی در شبکه‌های مبتنی بر تکنولوژی 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] تحقیق و مطالعه ی ارزشمندی است که در زمینه تضمین تأخیر انتها به انتها صورت گرفته است.تلاش‌های قبلی در راستای ارائه خدمات سرویس صرفا تلاشی برای بهبود متوسط کل تأخیر شبکه بوده و تضمینی در ارائه خدمات سرویس انتها به انتهای کاربر ارائه ‌نکرده اند.

    1-5   فصول بعدی این نوشتار

     

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

    1-6   جمع‌بندی

    شبکه‌های مش بی‌سیم یکی از فناوری‌های کلیدی و تاثیرگذار طی دهه پیش رو هستند و نقش بسیار مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رویایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان و هر لحظه و با نهایت سادگی و کمترین هزینه.

    شبکه‌ی مش بی‌سیم برای پاسخگویی به نیازهای روزافزون کاربران باید بتواند سطوح مختلفی از کیفیت سرویس را ارائه و با برقراری آن کیفیت‌ها را تضمین کند .منابع شبکه می‌بایست به نحوی سازمان دهی و مدیریت شود که بتواند بهره‌‌‌وری و بازدهی بالایی داشته باشد، به نحوی که احتمال عدول از شرایط تضمین شده برای سرویس و هم چنین هزینه های لازم کمینه شود. هدف اصلی این پژوهش، ارائه‌ی پیشنهادی برای تضمین کیفیت سرویس در شبکه‌های مش بی‌سیم است. سعی بر آن است الگوریتم پیشنهادی  ضمن دارا بودن شرایط مقیاس پذیری و نیز قابلیت استفاده در کنار سایر الگوریتم های موجود؛ تضمین خوب، قابل قبول و  تا حد ممکن دقیقی را برای پارامتر تأخیر فراهم آورد. با توجه به این که تضمین کیفیت سرویس به صورت انتها به انتها عمدتا مبتنی بر زمان‌بندی مناسب  رله‌ها و گره‌‌‌ها  با  BS   در تخصیص و  رزرو کردن کانال در مسیر بین مبدا تا مقصد است، در این پژوهش تلاش شد برپایه‌ی  الگوریتم‌های بهینه سازی ژنتیک، قابلیت تضمین انتها به انتهای کیفیت سرویس در شبکه‌های  مش بی‌سیم را فراهم آوریم.

     

    2-    فصل دوم
    شبکه‌های مش بی‌سیم

     

     

     

     

     

     

     

     

     

     

     

    2-1   چشم‌انداز

    شبکه‌های مش بی‌سیم [20] (WMN) یکی از فناوری‌های کلیدی و تاثیرگذار طی دهه پیش رو هستند و نقش بسیار مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد و بر اساس  پیش‌بینی آقای Akyildiz شبکه‌های مش بی‌سیم  در دهه آینده تمامی‌شبکه‌های بی‌سیم را تحت تاثیر خود قرارخواهد داد و به جایگزینی مناسب برای آن‌ها تبدیل خواهد شد [3و22]. به کمک این شبکه‌ها رویایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان و هر لحظه و با نهایت سادگی و کمترین هزینه.

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    شکل  ‏2‑1- شبکه‌ بی‌سیم مش[a26] 

    با این تفاسیر شبکه‌های WMN نقش بسیار مهمی‌در نسل بعدی اینترنت ایفا می‌کنند. توانایی خود-سازماندهی[21] این شبکه‌ها به طرز چشمگیری پیچیدگی استقرار، حفظ و نگهداری شبکه را کاهش داده و در نتیجه ضمن بالا بودن قابلیت اطمینان و بهبود بخشیدن به ظرفیت شبکه، هزینه‌های متصور را نیز کاهش می‌دهد.

    این شبکه‌ها مشتمل[a27]  بر مسیریاب‌های مش و نیز کاربران مش می‌شوند که در آن مسیریاب‌های مش کمترین تحرک ممکن را دارند و  ستون فقرات WMN را شکل می‌دهند. آنها دسترسی به شبکه را هم برای کاربران مش و هم برای کاربران عادی فراهم می‌آورند.

     

    شکل  ‏2‑2- کاربران مش (چهار عکس سمت راست) و مسیریاب‌های مش (دو عکس سمت چپ)[3]

    در شکل (2-3) نمونه ای از شبکه مش بی‌سیم پیاده سازی شده در دانشگاه جورجیا نمایش داده شده است. این شبکه مش که BWN-Mesh نامیده شده است در واقع یک شبکه backhaul مش متشکل از 15 گره‌‌‌ بر اساس استاندارد IEEE 802.11b/g است. هدف از این پیاده سازی انتقال ترافیک  شبکه برای دسترسی به اینترنت است.

    Mobile ad Hoc Networks

    Mesh Backhaul

    Mobile ad Hoc Networks

    IEEE 802.11 WLAN

    Internet Testbed

    Internet Backhaul

    Wireless Sensor

    Mesh Router

    Mesh Router

    Getaway

    Ethernet

    Sensor Network

    Mesh Router

    Client

    Client

    شکل  ‏2‑3- شبکه مش BWN-Mesh تست شده در دانشگاه جورجیا[3]

    ادغام شبکه‌های WMN با دیگر شبکه‌ها مانند اینترنت، IEEE802.16، IEEE802.15، IEEE802.11، شبکه‌های حسگر و ... از طریق دروازه‌ها و پُل‌های موجود در مسیریاب‎های مش امکان‌پذیر است[22]. کاربران مش هم می‌توانند ثابت و یا متحرک باشند و به خودی خود یا در کنار مسیریاب‎های مش یک شبکه کاربر مش تشکیل دهند. انتظار می‌رود شبکه‌های WMN ، محدودیت‌های شبکه‌های Ad-Hoc، WLANها، WPANها و WMANها را برطرف کرده و کارکرد آنها را بهبود بخشند.

    برخلاف شبکه‌های سلولی که از کار افتادگی یک ایستگاه پایه (BS)[22] در شبکه، سبب قطع شدن ارتباط در محدوده جغرافیایی بزرگی می‌شود؛ در WMN‌ها اگر حتی درکار تعدادی از گره‌های[23] شبکه اختلال پیش بیاید، مابقی شبکه کماکان ارتباط خود را حفظ کرده و انتقال ترافیک توسط سایر گره‌ها صورت می‌پذیرد.[23]

    یکی از مهمترین کاربردهای شبکه‌های  WMN، ایجاد زیرساخت بی‌سیم برای دسترسی به اینترنت در مناطقی است که زیرساخت[24] سیمی‌(فیبر نوری، زوج سیم، کابل کواکسیال و ...) وجود ندارد و یا از لحاظ اقتصادی به صرفه نیست. در این مناطق از این تکنولوژی که پیاده‌سازی بسیار ارزان‌تر و سریع‌تری نسبت به همتای سیمی‌خود دارد، استفاده می‌شود[22 و23] همچنین با گسترش[a28]  شبکه‌های Ad-Hoc، WMN‌ها تبدیل به یک توپولوژی مهم در تکمیل زیرساخت شبکه‌های بی‌سیم شده اند.

    آزمایشها و تجربیات به دست آمده از مطالعات و پیاده سازی این شبکه‌ها، نوید دهنده تحولی بزرگ در شبکه‌های بی‌سیم آتی است. از اینرو استفاده از این تکنولوژی با توجه به توزیع و پراکندگی شهرها و روستاها در کشورمان بسیار راهگشا و مفید به نظر می‌رسد.

     علی رغم این که این شبکه‌ها براساس فن آوری‌های کنونی قابل پیاده سازی هستند، ولی نمونه‌های ساخته شده مختلف نشان می‌دهند که عملکرد این شبکه‌ها پایین تر از انتظارات می‌باشد لذا طراحی مجدد لایه‌های مختلف WMN‌ها از اهمیت خاصی برخوردار می‌باشد[a29] [23]. به عنوان مثال یکی از این مشکلات که در این پایان نامه نیز بدان اشاره خواهد شد بحث زمان‌بندی ارسال گره‌‌‌های شبکه است که هنوز به عنوان یک موضوع تحقیقاتی پویا نظر محققان را در این زمان به خود جلب کرده است.

    طراحی مسیریاب‌های مش قابل انعطاف جهت ایجاد یک شبکه زیرساخت قابل اعتماد که مسیریابی ترافیک در کل شبکه را به نحوی مناسب انجام دهند، از اهمیت زیادی برخوردار است لذا ارائه روش‌ها و پروتکل‌هایی جهت رویارویی با ترافیک‌های محلی و گذری در مسیریاب‌های مش حائز اهمیت خواهد بود.[2 ]

    2-2   توپولوژی شبکه

    2-2-1               توپولوژی نقطه به نقطه[25] (PTP)

                    شبکه نقطه به نقطه از یک یا چند لینک ثابت تشکیل می‌شود و در این حالت معمولا آنتن‌های گیرنده و فرستنده با سمت گرایی بالا مورد استفاده قرار می‌گیردشکل(2-4[a30] ).

     

     

     

     

     

     

     

     

    شکل  ‏2‑4- توپولوژی شبکه نقطه به نقطه[23]

    2-2-2               توپولوژی نقطه به چند نقطه[26] (PMP)

    در حالت نقطه به چند نقطه ایستگاه مبنا(BS)، نقش مهمی‌در هماهنگ کردن و برقراری ارتباطات دارد و ایستگاه‌های مشترک[27][a31]  (SS) باید قبل از این که با SS‌های دیگر تبادل داده داشته باشند تحت مدیریت ایستگاه مبنا ابتدا با BS ارتباط برقرار کنند و از طریق BS با SS دیگر تبادل داده کنند. این توپولوژی شبیه معماری شبکه‌های سلولی است[23] .شکل (2-5).

     

     

     

     

     

     

     

     

     

    شکل ‏2‑5 توپولوژی شبکه نقطه به چند نقطه[2]

    2-2-3               توپولوژی مش

    این توپولوژی به طور کلی هم به صورت حلقه و هم به صورت ساختارهای شاخه ای پیاده‌سازی می‌شود. مزیت عمده این مدل این است که شبکه مش مسیرهای غیرمستقیم برای اتصال کاربرانی را فراهم می‌کند که ممکن است دچار فقدان دید مستقیم[28] نسبت به  BS باشند. از این طریق تعداد کاربران متصل به شبکه را افزایش می‌دهد. لذا ترافیک هر کاربر[a32]  باید در بعضی مواقع از طریق چندین گره مسیردهی شود. در این توپولوژی ممکن است به گذردهی کمتری نسبت به شبکه‌های PMP دست یابیم. زیرا در شبکه‌های PMP فقط یک گام[29] برای اتصال SS به BS وجود دارد ولی در عوض پوشش بیشتری در شبکه‌های مش خواهیم داشت.

    در این توپولوژی برخلاف حالت PMP در ارتباط SSها تفکیک واضحی میان لینک فروسو[a33] [30] و لینک فراسو[31] وجود ندارد و هرSS می‌تواند به صورت مستقیم با دیگر گره‌های همسایه اش بدون کمک BS ارتباط برقرار کند. در این توپولوژی عموما یک یا چند گره نقش BS را دارند و تشکیل زیرساخت شبکه بی‌سیم را داده و شبکه مش را به شبکه‌های[a34]  دیگر مانند اینترنت متصل می‌کنند. همان طور که ملاحظه می‌کنید در این توپولوژی برخلاف دو حالت قبل بین BS و SS مقصد، چند گام می‌تواند قرار بگیرد. در بخش بعد شبکه‌های بی‌سیم چندگامی‌را معرفی می‌کنیم[24].

     

    1.       Wireless Mesh Networks

    [2] .Gateway

    1.       Subscriber Station

    2.       Base Station

    3.       The Worldwide interoperability for Microwave Access

    1.       File Transfer Protocol (FTP)

    2.       Telnet

    3.       Best Effort

    4.       Online

    5.       Real Time

    [11]. deadline

    1.       Primary Interference

    2.       Matching

    3.       Multi-edged

    [15].  Burst

    [16].  Heuristic

    [17].  Spatial Reuse

    [18].  Cross-Layer

    [19].  Guard Symbol

    1.       Wireless Mesh Networks

    1.       Self-Healing To Enable Quick Deployment

    1.       Base Station

    2.       Node

    3.       Infrastructure

    1.       Point To Point

    2.       Point To MultiPoint

    [27] .   Subscriber

    1.       Line of sight

    2.         Hop

    3.         Downlink

    4.       Uplink

     [a1]نظر شما اعمال شده است و ویرایش انجام شده است

     [a2]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a3]نظر شما اعمال شد

     [a4]نظر شما اعمال شد

     [a5]نظر شما اعمال شد کمله درست نوشته شد

     [a6]زیر نویس اصلاح شد

     [a7]منبع را پیدا نکردم – از اینترنت استفاده شده است

     [a8]نظر شما اعمال شد

     [a9]نظر شما اعمال شد

     [a10]نظر شما اعمال شد

     [a11]نظر شما اعمال شده است و متن اصلاح شده است.

     [a12]نظر شما اعمال شده است و متن اصلاح شده است.

     [a13]نظر شما اعمال شده است و متن اصلاح شده است.

     [a14]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a15]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a16]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a17]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a18]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a19]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a20]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a21]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a22]مدل مسئله در ادامه تشریح شده است

     [a23]جمله اصلاح شد.

     [a24]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a25]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a26]مرجع اینترنت بود که نتواستم سایت دقیق را پیدا کنم

     [a27]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a28]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a29]منبع در آخر جلمه است.

     [a30]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a31]با اجازه شما من مشترک را بیشتر دوست داشتم

     [a32]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a33]نظر شما اعمال شده است و کلمه اصلاح شده است.

     [a34]نظر شما اعمال شده است و کلمه اصلاح شده است.

    Link Scheduling With Hard QoS Guarantee

    In Wireless Mesh Networks

     

     

     

     

     

    Date of Submission: 2013/05/19

     

    Department of Electrical and Computer Engineering

    Isfahan University of Technology, Isfahan, Iran

     

     

    Abstract

    Wireless mesh network (WMN), is promising technology for next generation networks, because it can provide extended coverage range, power consumption reduction and increased throughput simultaneously. Multi hop concept of this networks leads to less path loss and shadowing effect and so coverage range can be extended. Also these networks need little cabling engineering and this make their setup cheaper. But one of these networks’ problems is scalability issue, because relayed traffic needs more bandwidth and has less QoS (delay and jitter).

    Increasing hop distances in order to reduce the number of hops decreases links’ rates. Also more users equals to more collisions which is equivalent to throughput degradation. Coverage range extension leads to less QoS and throughput, because it needs more hops.

    According these facts, acceptable performance of a WMN is equivalent to solving an optimization problem which takes into account mentioned factors concurrently. This is hot topic research as a NP-hard problem in WMNs nowadays. Scheduling plays an important role in providing QoS support to multimedia communications in WMNs.

    In this thesis a novel algorithm based on Genetic algorithm with Spatial Reuse for improving centralized scheduling and optimal time slot allocation in Wireless Mesh Networks is presented. The proposed algorithm considers hard QoS, spatial reuse for efficient use, complete interference model and the impact of node positions in topology.

    Simulation results show that the proposed scheduling algorithms with hard QoS quarantine condition can provide QoS support in terms of end-to-end delay and throughput for different traffic type

    Keywords:

    WMN, Link scheduling, QoS, NP_Hard,

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

    فهرست:

    عنوان                                                                                                                                                                   صفحه

     فهرست مطالب.. یک

    فهرست اشکال پنج

    فهرست جداول هفت

    چکیده. 1

    1-                    فصل اول مقدمه......................................................................................................................... 2

    1-1مقدمه، چشم انداز شبکه‌های مش بی‌سیم...................................................................................................... 2

    1-2ضرورت تضمین کیفیت سرویس، چالش اصلی در شبکه‌های مش بی‌سیم............................................... 4

    1-3تعریف مسئله……………………......................……………………....................................... 6

    1-4بررسی پیشینه کار............................................................................................................................................. 7

    1-5 فصول بعدی این نوشتار................................................................................................................................... 9

    1-6جمع‌بندی.................................................................. ............................................................................................... 9

                      2-فصل دوم شبکه‌های مش بی‌سیم.................................................................................................... 11

    2-1چشم‌انداز................................................................ ............................................................................................... 11

    2-2توپولوژی شبکه........................................................ ............................................................................................. 14

    2-2-1توپولوژی نقطه به نقطه (PTP) ..................................................... .................................................................. 14

    2-2-2توپولوژی نقطه به چند نقطه (PMP) ........................................................................................................... 14

    2-2-3توپولوژی مش................................................... ............................................................................................... 15

    2-3شبکه‌های بی‌سیم چندگامی.......................................................................................................................... 16

    2-4معماری شبکه‌های مش بی‌سیم...................................................................................................................... 17

    2-4-1شبکه‌های  مش بی‌سیم به عنوان شبکه‌ی زیر ساخت....................................................................................... 17

    2-4-2شبکه‌های مش بی‌سیم کاربران.............................. ........................................................................................... 18

    2-4-3شبکه‌های مش بی‌سیم ترکیبی............................. ............................................................................................ 19

    2-5مقایسه شبکه‌های مش بی‌سیم  و Ad-hoc    ...............................................................................................19

    یک

    2-6مسائل مربوط به لایه‌های شبکه و زمینه‌های باز تحقیقاتی..................................................................................... 21

    2-6-1لایه فیزیکی............................................................ ......................................................................................... 21

    2-6-2لایه‌ی دسترسی در شبکه‌های مش بی‌سیم................................................................................................... 23

    2-6-3MAC تک کاناله.............................................. ............................................................................................. 24

    2-6-4MAC چندکاناله.............................................. .............................................................................................. 25

    2-6-5لایه شبکه............................................................. ............................................................................................. 28

    2-6-6لایه انتقال........................................................... ............................................................................................... 30

    2-6-7لایه کاربرد................................................... ................................................................................................... 31

    2-7مدیریت شبکه....................................................... ................................................................................................ 32

    2-8طراحی بین لایه ای.............................................. ................................................................................................. 33

    2-9 کاربردهای WMN.............................................. ............................................................................................... 33

    2-9-1شبکه‌ی خانگی باند وسیع......................................................................................................................... 33

    2-9-2شبکه کردن اجتماعات و همسایگی ها......................................................................................................... 34

    2-9-3شبکه کردن شرکت های تجاری............................................................................................................... 35

    2-9-4شبکه های شهری.......................................... .................................................................................................. 36

    2-9-5سایر شبکه‌ها....................... .............................................................................................................................. 37

    2-9-6 چند مثال موردی از شبکه‌های WMN....................................................................................................... 38

    2-10جمع‌بندی............................................................... ............................................................................................. 39

             3-فصل سوم زمان‌بندی متمرکز در شبکه‌های مش بی‌سیم................................................................................... 41

    3-1مقدمه..................................................................... ................................................................................................ 41

    3-2لایه فیزیکی استاندارد IEEE 802.16........................................................................................................... 42

    3-2-1مدولاسیون دیجیتال............................................ ............................................................................................. 46

    3-3لایه MAC استاندارد  IEEE 802.16.......................................................................................................... 48

    3-3-1 تطبیق لینک..................................................... ............................................................................................... 49

    3-4عملکرد مد مش  در MAC استاندارد IEEE 802.16....................................................................................... 50

    دو

    3-4-1 ساختار فریم در مد مش استاندارد IEEE 802.16....................................................................................... 51

    3-4-2زیرفریم کنترلی....................................................... ........................................................................................ 52

    3-4-3زیرفریم دیتا....................................................... .............................................................................................. 54

    3-4-4نحوه ورود یک گره‌‌‌ به شبکه.............................. ............................................................................................. 56

    3-5الگوی زمانبندی مبتنی بر استاندارد IEEE 802.16........................................................................................... 57

    3-5-1زمان‌بندی متمرکز................................... ....... ................................................................................................ 59

    3-6جمع بندی............................................................................................................................................................... 60

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

    4-1مقدمه................................................................... ................................................................................................. 61

    4-2نیازمند‌های  طراحی الگوریتم های زمانبندی..................................................................................................... 62

    4-2-1تداخل میان لینکهای بی‌سیم.................................. ........................................................................................... 62

    4-2-2سربار.................................................................. ............................................................................................... 64

    4-2-3تأخیر................................................................ ................................................................................................ 65

    4-2-4استفاده مجدد فرکانسی.................................... ................................................................................................ 66

    4-3دسته‌بندی الگوریتم‌های زمان‌بندی................................................................................................................. 68

    4-4معرفی الگوریتم‌های زمان‌بندی با رویکرهای‌مختلف........................................................................................... 70

    4-5نتیجه‌گیری............................................................. ............................................................................................... 76

    5-                 فصل پنجم الگوریتم پیشنهادی بر پایه‌ی الگوریتم ژنتیک....................................................................... 78

    5-1مقدمه....................................................................... .............................................................................................. 78

    5-2الگوریتم ژنتیک................................................... ................................................................................................ 79

    5-2-1تاریخچه.............................................................. ............................................................................................. 79

    5-2-2ساختار الگوریتم‏های ژنتیکی............................................................................................................................ 80

    5-2-3عملگرهای الگوریتم  ژنتیک.......................... ................................................................................................ 82

    5-2-4کدگذاری و همگرایی الگوریتم ژنتیک....................................................................................................... 86

    5-3الگوریتم پیشنهادی............................................. .................................................................................................. 87

    سه

    5-4شبیه سازی............................................................ ................................................................................................ 96

    5-4-1محیط شبیه سازی............................... ......................................................................................................... 96

    5-4-2نتایج حاصل از شبیه‌سازی................................... ............................................................................................. 98

    5-5جمع بندی.......................................................... ...................................................................................  111 Error! Bookmark not defined.

           فصل ششم نتیجه‌گیری و پیشنهادات...........................................................................................................112

                 مراجع......................................................................................................................................................................114

    منبع:

    [1]   IEEE 802. 16-2004, IEEE standard for local and metropolitan area networks part 16: air interface for fixed broadband wireless access systems, Oct. 1, 2004.

    [2]   IEEE 802. 16-2005, IEEE Standard for Local and Metropolitan Area Networks – Part 16: Air Interface for Fixed Broadband Wireless Access Systems for Mobile Users, December 2005. M. S. Kuran, T. Tugcu / Computer Networks 51 (2007) 3013–3046 3043.

    [3]    I.F.Akyildiz, X.Wang, “A survey on wireless mesh networks”, IEEE Communication Magazine, Vol. 43, Issue 9, pp. 23-30, Sept 2005.

    [4]   S.Redana, and M.Lott, “Performance Analysis of IEEE 802. 16a in Mesh Mode”, IST SUMMIT, France, June 2004.

    [5]    S.Ramanathan, “A unified framework and algorithm for channel assignment in wireless networks”, Wireless Networks, vol. 5, Issue 2, pp. 81–94, March 1999.

    [6]    S.Ramanathan, L.Lloyd, “Scheduling algorithms for multihop radio networks”, IEEE/ACM Transactions on Networking, vol. 1, Issue 2, pp. 166–177, April 1993.

    [7]    B.Hajek, G.Sasaki, “Link scheduling in polynomial time”, IEEE Transactions on Information Theory, vol. 34, Issue 5, pp. 910–917, September 1988.

    [8]   T.Salonidis, L.Tassiulas, “Distributed dynamic scheduling for end to end rate guarantees in wireless ad hoc networks”, ACM MobiHoc, pp. 145–156, 2005.

    [9]   M.Kodialam, T.Nandagopal, “Characterizing achievable rates in multihop wireless networks: The joint routing and scheduling problem”, ACM MobiCom, 2003.

    [10]           M.Kodialam, T.Nandagopal, “Characterizing achievable rates in multihop wireless mesh networks with orthogonal channels”, IEEE/ACM Transactions on Networking, vol. 13, Issue 4, pp. 868–880, 2005.

    [11]           G.Sharma, R.Mazumdar, N.Shroff, “On the complexity of scheduling in wireless networks”, ACM Mobicom, 2006.

    [12]           S.Gandham, M.Dawande, and R.Prakash, “Link scheduling in sensor networks: Distributed edge coloring revisited”, IEEE INFOCOM, 2005.

    [13]           N.Bayer, B.Xu, V.Rakocevic, J.Habermann, “Improving the Performance of the Distributed Scheduler in IEEE 802. 16 Mesh Networks”, IEEE VTC, pp. 1193-1197, 2007.

    [14]           H.Wei, S.Ganguly, R.Izmailov, and Z.Haas, “Interference- aware IEEE 802. 16

            WiMax mesh networks”, IEEE VTC, vol. 5, pp. 3102- 3106, , 2005.

    [15]           J.Tao, F.Liu, Zh.Zeng, and Zh.Lin, “Throughput Enhancement in WiMax Mesh Networks Using Concurrent Transmission”, IEEE WiMob, Vol. 2, pp. 871 –874, 2005.

    [16]           Y.Cao, Zh Liu, Y.Yang, “A Centralized Scheduling Algorithm based on Multi-path Routing in WiMAX Mesh Network”, IEEE WiCOM, 2006.

    [17]           B.Han, W.Jia, and L.Lin, “Performance evaluation of scheduling in IEEE 802. 16 based wireless mesh networks”, ACM Computer Communications, vol. 30, Issue 4, pp. 782-792, 2007.

     

    [18]           F.Jin, A.Arora, J.Hwang, A .Choi, “Routing and Packet Scheduling for Throughput Maximization in IEEE 802. 16 Mesh Networks”, IEEE Broadnets, 2007.

    [19]           P.Du, W.Jia, L.Huang, W.Lu, “Centralized Scheduling and Channel Assignment in Multi-Channel Single-Transceiver WiMax Mesh Network”, IEEE WCNC, pp. 1734-1739, 2007.

    [20]           D.Kim and A.Ganz, “Fair and efficient multihop scheduling algorithm for IEEE 802. 16 BWA systems”, IEEE Broadnets, Vol. 2, pp. 833 - 839, 2005.

    [21]           C.Hong, A.Chun Pang, “Link Scheduling with QoS Guarantee for Wireless Relay Networks”, IEEE Transactions on Networking, 2008.

    [22]           F.I.Akyildiz, X.Wang and W.Wang, “Wireless mesh networks: a survey”. Computer Networks Journal (Elsevier), 47(4), 445–487 2005.

    [23]           Y.Zhang, J.Luo, and H.Honglin, “Wireless Mesh Networking Architecture, Protocols and standards”, pages 4-7, 14-15,428-429,568-590, 2007 by Taylor & Francis Group, LLC.

    [24]           A.Tzamaloukas, l.Garcia, “A Receiver Initiated Collision Avoidance Protocol for Multi Channel Networks”. In Proceeding of INFOCOM, 1997.

    [25]           N.Bayer, D.Sivchenko, B.Xu, V.Rakocevic, J.Habermann, “Transmission Timing of Signaling message IN IEEE 802. 16 Based on mesh network”, European wireless Athens, Greece, Apr 2-5, 2006.

    [26]           B.Raman, and K.chebrolv, “Design and Evaluation of a new MAC Protocol for Long Distance 802. 11 Mesh Network”, in proc, ACM, 2005.

    [27]           T. J.Tsai, H.Tseng, and A. C.Pang,”A New MAC Protocol for Wi-Fi Mesh Network”, in Proc IEEE AINA06, 2006.

    [28]           D.Couto, D.Aguayo, J.Bicket, and R.Morris, “A high-throughput path metric for multi-hop wireless routing”, in MobiCom 03: Processing of the 9th Annual International conference on mobile computing and networking, ACM press, pp.134-146, New York,2003,.

    [29]           R.Draves, J.Padhye, B.Zill, “Routing in multi-radio, Multi-hop wireless Mesh Networks”, Processing of ACM MobiCom, pp.114-128, 2004.

    [30]           H.Fery,  “Scalable Geographic Routing Algorithms for Wireless Ad-Hoc Networks ”, IEEE Networks MAG, Vol 18, No. 4, July/Aug 2004, Pages:18-22

    [31]           Z.Fu,  X.Meng,  and S.lu,  “A transport Protocol for supporting Multimedia Streaming in Mobile Adhoc Networks”, IEEE JSAC, vol. 21, no. 10. DEC,2003.

    [32]           J.Bicket, D.Aguayo, S.Biswas, and R.Morris, “Architecture and evaluation of an unplanned 802. 11b mesh network”, In MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking, pages 31–42, New York, NY, USA, 2005. ACM Press.

    [33]           A.Benjamin, A.Chambers, “The grid roofnet: a rooftop ad hoc wireless network” Master’s thesis, Massachusetts Institute of Technology, May 2002.

    [34]           V.Navda, A.Kashyap, S.Das, “Design and Evaluation of iMesh: an Infrastructure-mode Wireless Mesh Network”, In 6th IEEE WoWMoM Symposium,, June 2005.

    [35]           A.Elan,  and H.Balakrishnan,  “An Evaluation of the Metricom Ricochet Wireless Network”, Class report, Dept.of Electrical Engineering and Computer Science, University of California at Berkeley, May 1996..

    [36]           OPNET TECHNOLOGIES, INC., “Introduction to WiMAX: Technology Tutorials”, OPNETWORK, Washington, 2007.

    [37]           B.Fong, N.Ansari, A.C.M.Fong, G. Y.Hong, and B.Predrag “On the scalability of fixed broadband wireless access network deployment”, IEEE communications Magazine, vol. 42, Issue 9, pp. 12-18, 2004.

     

    [38]           P.Djukic, and S.Valaee, “TDMA delay aware link scheduling for multi-hop wireless networks”, IEEE Transactions on Networking, 2007.

    [39]           L.Nuaymi and M.Loutfi. “WiMAX : Technology for Broadband Wireless Access”,. John Wiley & Sons, 2007.

    [40]           Sh.Cheng, Ph.Lin, D.Huang, Sh.Yang, “A study on distributed/centralized scheduling for wireless mesh network”, IEEE IWCMC, pp. 599-604, 2006.

    [41]           H.Zandi, and Y.Fang, “Impact of routing metrics on path capacity in multi-rate and multi-hop wireless ad-hoc networks”, in ICNP, 2006.

    [42]           S.Ramanthan, and E. L.Lioyd, “Scheduling algorithms for multichip radio networks”, IEEE/ACM transaction on networking, vol. 1, no 2, pp.166-177, Apr. 1993.

    [43]           Y.Qian, B.Shafaq, L.Chaudhry, and K.Ratan, “Resource Management in WiMAX Networks.” In Yang Xiao (editor(s)), WiMax/MobileFi: Advanced Research and Technology, pp 337-408. Auerbach Publications, CRC Press. Dec, 2007. 

    [44]           S.Hung-Yu Wei, R.Ganguly, Z.Izmailov, and J.Haas, “Interference-aware ieee 802. 16 wimax mesh networks”, In Vehicular Technology Conference, 2005.

    [45]           H.Shetiya, and V.Sharma, “Algorithms for routing and centralized scheduling to provide QoS in IEEE 802. 16 mesh networks”, In WMuNeP ’05: Proceedings of the 1st ACM workshop on Wireless multimedia networking and performance modeling, 2005.

    [46]           N.Krishna, M.Ramachandran, E.Belding, K.Almeroth, and M.Buddhikot, “Interference-aware channel assignment in multi-radio wireless mesh networks”, In INFOCOM, 2006.

    [47]           G.Ashutosh, and K.Abhay, “Link scheduling algorithms for wireless mesh networks”, In IEEE communications survey and tutorials, second issue, 2011.

    [48]           Du.Peng, J.Weijia, H.Liusheng, and W.Lu, “Centralized scheduling and channel assignment in multi-channel single-transceiver WiMAX mesh network”, In Wireless Communications and Networking Conference, WCNC, 2007.

    [49]           S.Ergen, and P.Varaiya, “TDMA scheduling algorithms for wireless sensor networks”, Wireless Networks, 2009.

    [50]           M.Alicherry, R.Bhatia, and E.Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks”, In MOBICOM, 2005.

    [51]           D.Ghosh, A.Gupta, and P.Mohapatra, “Admission control and interference-aware scheduling in multi-hop WiMAX networks”, In Mobile Adhoc and Sensor Systems, 2007.

    [52]           P.Djukic, and S.Valaee, “Delay aware link scheduling for multi-hop TDMA wireless networks”, IEEE/ACM Transactions on Networking, 2009.

    [53]           G.Narlikar, G.Wilfong, and L.Zhang, “Designing multihop wireless backhaul networks with delay guarantees”, In INFOCOM, 2006.

    [54]           Sahoo, A.  and Goyal, P. “A scheduling and call admission control algorithm for WiMAX mesh network with strict QoS guarantee”, In Comsnet, 2010.

    [55]           V.Gabale, A.Chiplunkar, B.Raman, and P.Dutta, “Delaycheck: Supporting voice over multi-hop multichannel wireless mesh”, In COMSNETS, 2011.

    [56]           A.Raniwala, K.Gopalan, and T.Chiueh, “Centralized channel assignment and routing algorithms for multichannel wireless mesh networks”, SIGMOBILE Mob. Comput. Commun. Rev. , 8(2):50–65, 2004.

    [57]           A. S.Kashyap, S. R.Ganguly, and S.Banerjee, “Voip on wireless meshes: Models, algorithms and evaluation”, In INFOCOM, 2007.

    [58]           P.Dutta, S.Jaiswal, and R.Rastogi, “Routing and channel allocation in rural wireless mesh networks”, In INFOCOM, 2007.

     

    [59]           B.Raman, and K.Chebrolu,” Design and evaluation of a new mac protocol for long-distance 802. 11 mesh networks”, In MOBICOM, 2005.

    [60]           P.Dutta, S.Jaiswal, D.Panigrahi, and R.Rastogi, “A new channel assignment mechanism for rural wireless mesh networks”, In INFOCOM Mini-Conference, 2008.

    [61]           L. Y.Tseng, and S.Yang, “Genetic algorithms for clustering, feature selection and classification”, IEEE Int. Conference on Neural Networks, pp. 1612-1616, 1997.

    [62]           J.Bala, H.Vafaie, K.De jong, and H.Wechslev, “Hybrid learning using genetic algorithms and decision trees for pattern classification”, IJCAI conference, Montreal, 1995.

    [63]           W.Siedlecki, and J.Sklansky, “A note on genetic algorithms for large scale pattern selection”, Pattern Recognition Letters, vol. 10,335-347, 1989.

    [64]           H.Vafaie,  and K.De Jong, “Robust feature selection algorithms” , Proc. of the fifth conference on tools for artificial intelligence, Boston, MA: IEEE Computer Society Press. , pp. 356-363, 1993.

    [65]           H.Vafaie  and K.De Jong,  “Genetic algorithms as a tool for feature selection in machine learning”, Proc. of the 4th Int. conference on tools with artificial intelligence, pp. 200-204 Arlington, VA, 1992.

    [66]           H.Vafaie, and I.Imam, “Feature selection methods: genetic algorithms vs. greedy-like search”, Proc. of the Int. conference on fuzzy and intelligent control systems, 1994.

    [67]           Fogel, D. B.  “What is Evolutionary Computation?” IEEE Spectrum, Feb 2000, pp. 26-32

    [68]           R. L.Haupt,  and S.Ellen Haupt, “Practical Genetic Algorithm” USA, Wiley, 2004

    [69]           F.Marki, M.Vogel, and M.Fischer, “Process Plan Optimization using a Genetic   Algorithm", PATAT 2006, pp. 528–531. ISBN 80-210-3726-1. 2006

    [70]           R.Perzina, “Solving the University Timetabling Problem with Optimized Enrolment of Students by a Parallel Self-adaptive Genetic Algorithm”, PATAT, pp. 264–280. 2006

    [71]           P.Y.Kong, H.Wang, Y.Ge, C.K.Tham, and Y.C.Liang, “PMP tree and hybrid PMP-mesh for multi-hop relay networks,” IEEE C802.16j-06/008r2, May 2006.

    [72]            H.Kang,  Y.Sun, R.Taori, Y.Lee, P.Wang, A.Chindapol,  H.Lee, Y.Takatani, H.Lee, A.Zhang, K.Zhang, F.Ren, K.Saito, K.Teo, K.Saito, K.Teo, P.Zhu, B.Kwak , “Proposed technical requirements guideline for IEEE 802. 16 Relay TG”, IEEE 802. 16j-06/016r1, Oct. 2006.

    [73]            M.Naden, D.Kitchener, W.Tong, P.Zhu, G.Senarnath, H.  D.Steer, D.Yu, and G. -Q.Wang, “Metrics for multihop systems”, IEEE C802. 16j-06/014r1, May 2006.

    [74]           I. K.Fu, W. H.Sheen, C. L.Hsiao, and C.C.Tseng, “Reverse link performance of relay-based cellular systems in Manhattan-like scenario”, IEEE C80216mmr-06/004r1, Jan. 2006.

    [75]           J.Cho, M.Lee, H.Kang, S.Lee, J.  P.Joo, Y.So, S.Kim, D.Hong, J.Choe, B.Shin, and H.Choi, “On the throughput enhancement of fixed relay concept in Manhattan-like urban environments”, IEEE C802. 16mmr-06/003, Jan. 2006.

    [76]            I.Guvenc, M.R.Jeong, F.Watanabe, and C. C.Chong, “Technical comments to P802. 16j baseline document: 6. 3. 23. 3 - use of ARQ in MBS,” IEEE C802. 16j-07/578r1, Nov. 2007.

    [77]           N. L.Johnson, and S.Kotz, “Continuous Univariate Distributions”. New York: John Wiley & Sons, 1970.

    ع.علیرضا مهدی ، "مقدمه­ای بر الگوریتم ژنتیک و کاربردهای آن" ،  انتشارات ناقوس، 1386.

     

    ا.مسعودیان، "طراحی جدول زمانبندی خودکار با استفاده از الگوریتم های ژنتیک" ، پایان­نامه کارشناسی،  دانشگاه اصفهان، 1386.

    م.عباس کیا ، "الگوریتم های فرا اکتشافی جستجو، الگوریتم های ژنتیک"، پایان نامه کارشناسی ، 1388.

     

    ن.سادات مویدیان ،"تئوری یکپارچه مسیریابی،کنترل نرخ ورودی، زمان‌بندی و تخصیص کانال در شبکه‌های بی‌سیم"، پایان نامه دکتری، دانشگاه صنعتی اصفهان، 88.

    م.صالحی،" بهبود زمانبندی متمرکز به منظور تخصیص بهینه پنجره های خرد در شبکه های مش IEEE 802.16" ، پایان نامه کارشناسی ارشد،دانشگاه صنعتی امیرکبیر،  بهمن1386

    م.حسین الوندی ، "بهبود گذردهی و تامین QOS در شبکه‌های WiMax مش و شبیه سازی آن" ، پایان نامه کارشناسی ارشد ، دانشگاه صنعتی امیرکبیر، تیر 1388.

    ا.رستمی، "بررسی و ارائه راهکار جدید برای زمان‌بندی توزیع شده در شبکه‌های بی‌سیم مش IEEE 802.16.d" ، پایان نامه کارشناسی ارشد ، دانشگاه خواجه نصیرالدین طوسی،آذر 89.

    ش.خوشنواز،"بهبود الگوریتم زمان‌بندی در شبکه‌های WiMax"، پایان نامه کارشناسی ارشد،دانشگاه صنعتی سهند ، اردیبهشت 90.

    س.ضیایی امیری ،"طراحی MAC با پارامترهای QOS بهبود یافته در شبکه‌های مش بی‌سیم "، پایان نامه کارشناسی ارشد، دانشگاه تبریز، زمستان 89.

    ف.حمیدی سپهر،"ارزیابی تحلیلی تاثیر MAC بر روی ظرفیت برون دهی در شبکه‌های بی‌سیم مش "، پایان نامه کارشناسی ارشد، دانشگاه صنعتی شریف ، مرداد 87.

    ح.نورخیز محجوب ، "بهینه سازی گذردهی در شبکه‌های مش بی‌سیم"، پایان نامه کارشناسی ارشد، دانشگاه تهران، مهرماه 87.

    س.میرزایی ،"ارزیابی روش‌های افزایش گذردهی با استفاده از تکنیک‌های تخصیص کانال در شبکه‌های مش بی‌سیم"، پایان نامه کارشناسی ارشد، دانشگاه یزد، مهرماه 89.

    م.کرابی ،"ارائه راه حل جدید مبتنی بر الگوریتم‌های  ژنتیک برای حل مسئله چند پخشی در اینترنت  بر اساس پارامترهای QOS " ، پایان نامه کارشناسی ارشد، دانشگاه علم و صنعت ، اسفند  82.

     



تحقیق در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, مقاله در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, پروژه دانشجویی در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, پروپوزال در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, تز دکترا در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, تحقیقات دانشجویی درباره پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, مقالات دانشجویی درباره پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, پروژه درباره پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, گزارش سمینار در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, پروژه دانشجویی در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, تحقیق دانش آموزی در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, مقاله دانش آموزی در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم, رساله دکترا در مورد پایان نامه زمان‌بندی تخصیص لینک با رویکرد تامین خدمات سرویس در شبکه‌های مش بی‌سیم

ثبت سفارش
تعداد
عنوان محصول
بانک دانلود پایان نامه رسا تسیس