متوسط تأخیر مجاز ارسال در سناریو 4 107
شکل 5 34 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 4 107
شکل 5 35 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 4 108
شکل 5 36 توپولوژی شبکه در سناریو 5 خطوط آبی : مسیر ارسال- خطوط قرمز: تداخل ارسال 109
شکل 5 37 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط تأخیر مجاز در سناریو 5 109
شکل 5 38 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط تأخیر مجاز ارسال در سناریو 5 110
شکل 5 39- درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 5 110
شکل 5 40 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 5 111
فهرست جداول
عنوان صفحه
جدول 2-1 مقایسه شبکههای مش بی‌سیم و Ad-hoc 021
جدول 3-1 مشخصات فني اينترفيس هاي فيزيکي مختلف تعريف شده استاندارد 802.16043
جدول 3-2 نرخ ارسال ديتا در استاندارد802.16051
جدول 3-3 تعداد کل سمبل هاي OFDM در فريم مش با توجه به طول فريم و پهناي باند کانال054
جدول 4 -1- خلاصه‌ای از روش‌های مختلف زمان‌بندی بر اساس چهارچوب ارائه شده 076
جدول 5-1 مقایسه الگوریتم ژنتیک دوبعدی و تک بعدی در مسئله زمان‌بندی…………………………………………….95
جدول 5 2 پارامترهاي مورد استفاده در شبيه سازي 097
جدول 1 3- پارامترهاي مورد استفاده در شبيه سازي (الگوریتم ژنتیک) 098
جدول 1 4-در خواست گره‌‌‌های شبکه-N:شماره گره،B: پهنای باند درخواستی ،D: تأخیر مجاز ارسال 099
چکیده
شبکههای مش بی‌سیم یکی از تکنولوژی‌های مورد توجه برای ایجاد شبکههای بی‌سیم نسل بعد هستند. زیرا این شبکه‌ها می‌توانند به دلیل افت مسیر کمتر و نیز کاهش اثر عامل سایه افکنی، که ناشی از خصوصیت چند گامی بودن آنهاست، محدوده تحت پوشش وسیع و ظرفیت بالایی را با مصرف توان کم و هزینه پایین در اختیار کاربران قرار دهند. در مقابل این مزایا، این شبکه‌ها با مشکل عدم توسعه پذیری آسان مواجه هستند. زیرا ترافیکی که توسط چند واسط رله می‌شود به عرض باند بیشتر نیاز دارد، دچار تأخیر بیشتر شده و لذا کیفیت سرویس کاهش می‌یابد. بزرگتر کردن فاصله رله‌ها به منظور کاهش تعداد آنها نیز باعث کاهش سرعت لینک‌ها خواهد شد. افزایش تعداد کاربران شبکه نیز منجر به برخورد‌های بیشتر و درنتیجه کاهش بیشتر گذردهی می‌گردد. افزایش ناحیه تحت پوشش شبکه نیز به دلیل احتیاج به رله‌های بیشتر افت گذردهی و افزایش تأخیر را در پی خواهد داشت.بنابراین کارایی مناسب در یک شبکه مش باید از طریق حل یک مسئله بهینه‌سازی که عوامل مؤثر(نظیر تأخیر، گذردهی و …) در آن گنجانده شده باشد دست آید. حل این نوع مسئله در سال‌های اخیر به عنوان یک مسئله NP-Hard توجه زیادی را در حوزه مسائل مربوط به شبکههای بی‌سیم مش به خود معطوف کرده است.
در اين پايان نامه الگوريتم جديدي به منظور بهبود زمانبندي متمرکز و تخصيص بهينه پنجره‌هاي زماني به گره‌‌‌هاي شبکه با در نظرگرفتن قابليت استفاده مجدد از فضاي فرکانسي، بارویکرد تضمین تأخیر انتها به انتهای کاربر ارائه شده است. الگوریتم پیشنهادی در این تحقیق برای حل تقریبی مسئله بهینه‌سازی زمان‌بندی، برپایه‌ی الگوریتم ژنتیک است. الگوریتم پیشنهادی قابلیت تطبیق پذیری با پارامتر‌های مختلف(نظیر بازدهی، عدالت و …) بر اساس خواسته‌ی اپراتور را داراست. نتایچ حاصل از پیاده‌سازی موید بهبود نتایج نسبت به روش‌های پیشین است.
فصل اول
مقدمه
مقدمه، چشم انداز شبکههای مش بی‌سیم
رواج بيش از حد اينترنت دردنياي ارتباطي امروز به گونه اي بوده است كه ساختارهاي دستيابي سيم دار پر سرعت
پاسخگوي نياز بسياري از مناطق نيستند .تعداد مراكز سرويس دهنده خدمات پر سرعت اينترنت امروزي به نسبت تقاضا بسيار كم است. كابل كشي خطوط پر سرعت براي تمامي اين سرويس دهندگان بسيار پر هزينه و زمان بر است . امروزه تكنولوژي‌های[a1] جديدي معرفي شده است تا جايگزين اين شبكه هاي سيم دار شوند. اين شبكه هاي جايگزين ، شبكه‌هاي بی‌سیم پر سرعت هستند كه امكان دسترسي سريع به اينترنت در مواقعي كه ساختار شبكه سيم دار به دليل حجم بالاي متقاضي و يا قديمي بودن شبكه ها ، قادر به پاسخگويي به نياز كاربران نيست را فراهم مي‌آورند و هزينه‌هاي اضافي مرتبط به روز رساني ساختار كابل كشي‌ها را از بين مي‌برند. سيستم هاي بی‌سیم سنتي اغلب براي اهداف تجاري درمحل هايي كه سرعت و دقت بالا نياز است استفاده مي‌شوند و در موارد شخصي و يا خانه‌ها می‌بایست تكنولوژي ارزان را به كار گرفت. هم اكنون پيشرفت هاي تكنيكي اين امكان را فراهم ساخته اند و فرصت های بسياري را براي سرويس دهندگان اينترنت ايجاد كرده اند. شبکههای مش بی‌سیم 1 (WMN) یکی از فناوری‌های کلیدی و تأثیرگذار طی دهه پیش رو است که نقش بسیار [a2]مهمی در نسل‌های آتی شبکههای بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رؤیایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان ، هر لحظه، با نهایت سادگی و کمترین هزینه.
این شبکه‌ها شامل مسیریاب‌های مش [a3]و نیز کاربران مش می‌شوند که در آن مسیریاب‌های مش کمترین تحرک ممکن را دارند و ستون فقرات WMN را شکل می‌دهند. آنها دسترسی به شبکه را هم برای کاربران مش و هم برای کاربران عادی فراهم می‌آورند.
شکل 1 1- شبکه‌ی مش بی‌سیم
شبكه مش بي سيم كاملا منطبق بر ساختار شبكه سيم دار است و هر فرستنده امكان دسترسي كاربران متصل به آن
را به اينترنت فراهم مي‌كند و به صورت جزئي از ساختار شبكه عمل خواهد کرد. ترافيك شبكه از بين چندين [a4]رله
گذر خواهد كرد و امكان اتصال ايستگاه‌هاي مختلف را حتي اگر خارج از محدوده شبكه باشند، فراهم مي آورد. شبكه‌هاي مش بی‌سیم انعطاف پذيرترين و كم هزينه ترين روش براي گسترش سرويس‌هاي پر سرعت اينترنت هستند كه به صورت عمده در مصارف شخصي قابل استفاده اند.
هر رله‌ی بی‌سیم در اين شبكه به عنوان عنصري از ساختار شبكه است و مي‌تواند اطلاعات را از شبكه مش بی‌سیم به مقصد برساند. اين نوع شبكه مشكلات وجود موانع در حيطه محيط راديويي را از بين مي‌برد و بسيار ارزان و راحت، شبكه را قابل گسترش مي‌كند، زيرا در اين ساختار هر رله فقط نياز به برقراري ارتباط با رله مجاور خود دارد . ترافيك شبكه‌اي در صورت بروز هر مانع ، می‌تواند به سمت رله ديگر تغيير جهت مي‌دهد، البته بدون آنكه نيازي به هر گونه تغيير در محل راديوي مر كزي براي ارتباط بامكان هاي جغرافيايي دور دست باشد .
از آنجائيكه منطقه تحت پوشش هر نقطه دسترسي مي‌تواند در اطراف موانع گسترش يابد، بنابراين تعداد نقاط دسترسي كاهش مي يابد.
شبكه هاي مش بی‌سیم، دارای تکنولوژی ارزان قابل گسترش و براي دسترسي پر سرعت در محدوده هاي جغرافيايي دور دست مناسب هستند . RoofNet[a5] نمونه اي از اين شبكه هاست. اين شبكه معمولا شامل تعدادي نقاط دسترسي بی‌سیم است كه درپنجره ها و پشت بام منازل نصب مي شود و بسترهاي اطلاعاتي كامپيوترهاي خانگي توسط سيم به آنتن ها انتقال مي‌يابد و از يك آنتن به آنتن ديگر منتقل مي شود تا به يك دروازه2 اينترنتي برسد[a6].
در شبکههای مش بی‌سیم ترافیک هر SS3 توسط رله‌های شبکه برای انتقال به اينترنت يا شبکه خارجي ديگر به سمت BS4 هدايت می‌شود (شکل (1-2)).
شکل 1 2- انتقال ترافیک SS به BS از طریق[a7] رله‌ها
یکی از استاندارد‌های پرکاربرد رایج که از شبکههای مش بی‌سیم در ساختار خود پشتیبانی می‌کند[a8] استاندارد 802.16 با نام تجاري WiMAX5 است. این استاندارد پروتکل کنترل دسترسي به رسانه انتقال را براي شبکه‌هاي بی‌سیم شهري تعريف مي‌کند. در اين استاندارد تمهيداتي براي پشتيباني از کيفيت سرويس، در حد و اندازه‌هاي کيفيت شبکه‌هاي دسترسي کابل کشي شده، انديشيده شده است. به کمک مد مش استاندارد 802.16، مي‌توان به سرعت اتصال‌هاي بی‌سیم[a9] قابل اطميناني با سطح پوشش بسيار بيشتر از شعاع قابل دسترس در لايه فيزيکي فراهم آورد. لذا مد مش استاندارد 802.16 با MAC مبتني بر تکنولوژي TDMA راه‌حل مناسبي براي پياده‌سازي شبکه‌هاي مش بی‌سیم است. شبکه‌هاي مش بی‌سیم، شبکه‌هاي چندگامي ثابتي هستند که به منظور فراهم آوردن دسترسي بی‌سیم در ناحيه‌ي جغرافيايي وسيعي بکار گرفته مي‌شوند[1و2و3]. چالش اصلي در اين شبکه‌ها ارائه کيفيت سرويس بالا براي کاربران آنها است. استاندارد 802.16 با معرفي یک MAC جديد که از تکنولوژي TDMA استفاده مي‌نمايد، قابلیت ارائه کيفيت سرويس را براي اين شبکه‌ها ارائه می‌کند.
ضرورت تضمین کیفیت سرویس، چالش اصلی در شبکههای مش بی‌سیم
رشد سریع شبکههای بی‌سیم هم زمان با ایجاد سرویس‌های جدید، موضوعات تحقیقاتی بسیار متنوعی را در این شبکه‌ها مطرح کرده است. در این بین، بسیاری از این مسایل به تضمین کیفیت سرویس مربوط می‌شود. یک پارچه
شدن شبکههای انتقال داده، صوت و تصویر نیاز به [a10]سرویس‌های متنوعی را موجب می‌شود. در چنین محیطی و برای ایجاد یک شبکه‌ی مناسب که در آن انتظارات کاربران به نحوی رضایت بخش تأمین شود، کنترل رفتار شبکه به منظور تضمین کیفیت سرویس کاربران مختلف اهمیت ویژه‌ای می‌یابد. نکته ی مهمی که در این حال نباید دور از ذهن بماند، بهره وری اجزا و منابع شبکه است. درغیر این صورت قیمت و پیچیدگی تجهیزات لازم برای ارائه‌ی سرویس قابل قبول نخواهد بود.
در سال های اولیه، اینترنت بیشتر برای ردوبدل کردن اطلاعات بین پژوهشگران شبکه استفاده می‌شد.در آن زمان [a11]پست الکترونیک،ارسال فایل 6و دسترسی به شبکه از راه دور 7 اصلی ترین کاربرد های اینترنت بودند. گسترش تقاضا باعث تغییرات عمده‌ای در به کار گیری شبکه ی اینترنت شد. کاربردهای جدید مثل کنفرانس های گروهی صوتی تصویری، مراکز قوی جست و جو در شبکه، تماس تلفنی اینترنتی و تجارت الکترونیکی نیاز به تضمین کیفیت سرویس را گریز ناپذیر کرده است.
در حال حاضر ارائه ی سرویس در شبکه ی اینترنت به صورت “بهترین[a12] تلاش8 “صورت می گیرد که در آن تضمینی برای کیفیت سرویس ارائه شده وجود ندارد. هنگامی که یک کاربر به شبکه دسترسی پیدا می‌کند، ممکن است برخی از قسمت‌های شبکه به دلیل عدم زمان‌بندی مناسب در استفاده از منابع آن قدر پرترافیک باشند که ترافیک منتقل نشود و یا آن قدر تأخیر داشته باشد که عملاً نیاز کاربر را برآورده نکند. خصوصیات سرویس مورد بحث به قرار زیر است:
شبکه هیچ نوع ترافیکی را به هنگام برقراری ارتباط به علت کمبود منابع لازم جهت ارائه‌ی سرویس رد نمی کند.
ترافیک تمام کاربران می[a13] تواند به صورت کاملاً مشابه در شبکه منتقل می شود.
شبکه با در نظر گرفتن منابع موجود سعی می‌کند ترافیک کاربر را در حداقل زمان ممکن و سالم به مقصد برساند به عبارت دیگر شبکه تنها تضمین می‌کند که تأخیر و یا اتلاف داده فقط در مواقعی انجام شود که لازم باشد.
در چنین شبکه‌ای تا زمانی که تأخیر خیلی برای کاربر مهم نباشد مشکلی ایجاد نمی‌شود(مثل سرویس پست الکترونیکی) اما به محض درخواست یک سرویس برخط9 ، تأخیر و اتلاف داده مهم می‌شود و اگر سرویس به صورت بلادرنگ 10ارائه شود کاربر در لحظات پرترافیک ممکن است قادر به ادامه‌ی ارتباط نباشد و یا حتی خود ترجیح دهد ارتباط را قطع کند و در زمان مناسب‌تری شانس خود را امتحان کند. طبیعی است که سرویس دهندگان اینترنت که از دهه ی 90 به بعد عموماً شرکت‌های خصوصی هستند، به دنبال برطرف کردن نیازهای متنوع مشتریان خود باشند. اگر سرویس دهندگان اینترنت در شبکههای بی‌سیم بتوانند سرویسی باکیفیت ارائه کنند روزبه روز کاربردهای جدیدتری به وجود می آید و شبکه
