آگوست 6

شکل ‏54- روش ادغام دونقطه‌ای 85
شکل ‏55- مثالی از جهش و نحوه‌ی کارکرد آن 86
شکل ‏56- کد برنامه مجازی الگوریتم ژنتیک ساده و فلوچارت آن 87
شکل ‏57- توپولوژی شبکه-خطوط ممتد: مسیر ارسال- خط چین بین گره‌‌‌ 2و1 تداخل نوع اول- 88
شکل ‏58 – یک کروموزوم برای جواب مسئله شکل (5-7) 88
شکل ‏59- کروموزومی دیگر برای جواب مسئله شکل (5-7) 88
شکل ‏510- نمونه‌ای از کروموزوم ناسالم در عمل ترکیب کنترل نشده 89
شکل ‏511- کروموزوم حاصل از عملگر جهش 90
شکل ‏512 دیاگرام الگوریتم پیشنهادی 91
شکل ‏513- نمایش فضای پویش تک بعدی و دوبعدی 92
شکل ‏514- نمایش گسترش شبکه به ترتیب برای افزایش تعداد رله های شبکه از 1 تا 3 93
شکل ‏515- نمودار سمت چپ : توپولوژی شبکه سمت راست- : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 6.12 تک بعدی 1.14 (ثانیه) 94
شکل ‏516نمودار سمت چپ : توپولوژی شبکه سمت راست- : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 91.51 تک بعدی: 4.56 (ثانیه) 94
شکل ‏517- نمودار سمت چپ : توپولوژی شبکه سمت راست- : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 321.56 تک بعدی 7.89 (ثانیه) 95
شکل ‏518- مراحل تفسیر کروموزوم تک بعدی 96
شکل ‏519 توپولوژی شبکه در سناریو 1- خطوط آبی : مسیر ارسال- خطوطو قرمز: تداخل ارسال 99
شکل ‏520 تلاش الگوریتم LA-GA برای یافتن جواب‌های بهتر در سناریو 1 100
شکل ‏521 توپولوژی شبکه در سناریو 2 خطوط آبی : مسیر ارسال- خطوطو قرمز: تداخل ارسال 100
شکل ‏522 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط تأخیر مجاز در سناریو 2 101
شکل ‏523 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط تأخیر مجاز ارسال در سناریو 2 102
شکل ‏524 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 2 102
شکل ‏525 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 2 103
شکل ‏526 – توپولوژی شبکه در سناریو 3 خطوط آبی : مسیر ارسال- خطوط قرمز: تداخل ارسال 103
شکل ‏527 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط تأخیر مجاز در سناریو 3 104
شکل ‏528 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط تأخیر مجاز ارسال در سناریو 3 104
شکل ‏529 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 3 105
شکل ‏530 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 3 105
شکل ‏531- توپولوژی شبکه در سناریو 4 خطوط آبی : مسیر ارسال- خطوط قرمز: تداخل ارسال 106
شکل ‏532 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط تأخیر مجاز در سناریو 4 106
شکل ‏533 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط تأخیر مجاز ارسال در سناریو 4 107
شکل ‏534 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 4 107
شکل ‏535 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 4 108
شکل ‏536 توپولوژی شبکه در سناریو 5 خطوط آبی : مسیر ارسال- خطوط قرمز: تداخل ارسال 109
شکل ‏537 درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط تأخیر مجاز در سناریو 5 109
شکل ‏538 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط تأخیر مجاز ارسال در سناریو 5 110
شکل ‏539- درصد درخواست با تأخیر انتها به انتهای تضمین شده با افرایش متوسط پهنای باند در سناریو 5 110
شکل ‏540 متوسط تأخیر ارسال سایر گره‌‌‌های شبکه با افرایش متوسط پهنای باند در سناریو 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
جدول 52 پارامترهای مورد استفاده در شبیه سازی 097
جدول ‏13- پارامترهای مورد استفاده در شبیه سازی (الگوریتم ژنتیک) 098
جدول ‏14-در خواست گره‌‌‌های شبکه-N:شماره گره‌‌‌،B: پهنای باند درخواستی ،D: تأخیر مجاز ارسال 099
شبکه‌های مش بی‌سیم یکی از تکنولوژی‌های مورد توجه برای ایجاد شبکه‌های بی‌سیم نسل بعد هستند. زیرا این شبکه‌ها می‌توانند به دلیل افت مسیر کمتر و نیز کاهش اثر عامل سایه افکنی، که ناشی از خصوصیت چند گامی بودن آنهاست، محدوده تحت پوشش وسیع و ظرفیت بالایی را با مصرف توان کم و هزینه پایین در اختیار کاربران قرار دهند. در مقابل این مزایا، این شبکه‌ها با مشکل عدم توسعه پذیری آسان مواجه‌ هستند. زیرا ترافیکی که توسط چند واسط رله می‌شود به عرض باند بیشتر نیاز دارد، دچار تأخیر بیشتر شده و لذا کیفیت سرویس کاهش می‌یابد. بزرگتر کردن فاصله رله‌ها به منظور کاهش تعداد آن‌ها نیز باعث کاهش سرعت لینک‌ها خواهد شد. افزایش تعداد کاربران شبکه نیز منجر به برخورد‌های بیشتر و درنتیجه کاهش بیشتر گذردهی می‌گردد. افزایش ناحیه تحت پوشش شبکه نیز به دلیل احتیاج به رله‌های بیشتر افت گذردهی و افزایش تأخیر را در پی خواهد داشت.بنابراین کارایی مناسب در یک شبکه مش باید از طریق حل یک مسئله بهینه‌سازی که عوامل مؤثر(نظیر تأخیر، گذردهی و …) در آن گنجانده شده باشد دست آید. حل این نوع مسئله در سال‌های اخیر به عنوان یک مسئله NP-Hard توجه زیادی را در حوزه مسائل مربوط به شبکه‌های بی‌سیم مش به خود معطوف کرده است.
در این پایان نامه الگوریتم جدیدی به منظور بهبود زمانبندی متمرکز و تخصیص بهینه پنجره‌های زمانی به گره‌‌‌های شبکه با در نظرگرفتن قابلیت استفاده مجدد از فضای فرکانسی، بارویکرد تضمین تأخیر انتها به انتهای کاربر ارائه شده است. الگوریتم پیشنهادی در این تحقیق برای حل تقریبی مسئله بهینه‌سازی زمان‌بندی، برپایه‌ی الگوریتم ژنتیک است. الگوریتم پیشنهادی قابلیت تطبیق پذیری با پارامتر‌های مختلف(نظیر بازدهی، عدالت و …) بر اساس خواسته‌ی اپراتور را داراست. نتایچ حاصل از پیاده‌سازی موید بهبود نتایج نسبت به روش‌های پیشین است.
مقدمه، چشم انداز شبکه‌های مش بی‌سیم
رواج بیش از حد اینترنت دردنیای ارتباطی امروز به گونه ای بوده است که ساختارهای دستیابی سیم دار پر سرعت
پاسخگوی نیاز بسیاری از مناطق نیستند .تعداد مراکز سرویس دهنده خدمات پر سرعت اینترنت امروزی به نسبت تقاضا بسیار کم است. کابل کشی خطوط پر سرعت برای تمامی این سرویس دهندگان بسیار پر هزینه و زمان بر است . امروزه تکنولوژی‌های[a1] جدیدی معرفی شده است تا جایگزین این شبکه های سیم دار شوند. این شبکه های جایگزین ، شبکه‌های بی‌سیم پر سرعت هستند که امکان دسترسی سریع به اینترنت در مواقعی که ساختار شبکه سیم دار به دلیل حجم بالای متقاضی و یا قدیمی بودن شبکه ها ، قادر به پاسخگویی به نیاز کاربران نیست را فراهم می‌آورند و هزینه‌های اضافی مرتبط به روز رسانی ساختار کابل کشی‌ها را از بین می‌برند. سیستم های بی‌سیم سنتی اغلب برای اهداف تجاری درمحل هایی که سرعت و دقت بالا نیاز است استفاده می‌شوند و در موارد شخصی و یا خانه‌ها می‌بایست تکنولوژی ارزان را به کار گرفت. هم اکنون پیشرفت های تکنیکی این امکان را فراهم ساخته اند و فرصت های بسیاری را برای سرویس دهندگان اینترنت ایجاد کرده اند. شبکه‌های مش بی‌سیم 1 (WMN) یکی از فناوری‌های کلیدی و تأثیرگذار طی دهه پیش رو است که نقش بسیار [a2]مهمی‌ در نسل‌های آتی شبکه‌های بی‌سیم و سیار ایفا خواهند کرد. به کمک این شبکه‌ها رؤیایی که از دیرباز در ذهن بسیاری از کاربران گوناگون انواع شبکه‌ها در سرتاسر دنیا بوده به تحقق نزدیک‌تر می‌شود؛ و این رویا چیزی نیست جز اتصال به شبکه در هر زمان ، هر لحظه، با نهایت سادگی و کمترین هزینه.
این شبکه‌ها شامل مسیریاب‌های مش [a3]و نیز کاربران مش می‌شوند که در آن مسیریاب‌های مش کمترین تحرک ممکن را دارند و ستون فقرات WMN را شکل می‌دهند. آنها دسترسی به شبکه را هم برای کاربران مش و هم برای کاربران عادی فراهم می‌آورند.
شکل ‏11- شبکه‌ی مش بی‌سیم
شبکه مش بی سیم کاملا منطبق بر ساختار شبکه سیم دار است و هر فرستنده امکان دسترسی کاربران متصل به آن
را به اینترنت فراهم می‌کند و به صورت جزئی از ساختار شبکه عمل خواهد کرد. ترافیک شبکه از بین چندین [a4]رله
گذر خواهد کرد و امکان اتصال ایستگاه‌های مختلف را حتی اگر خارج از محدوده شبکه باشند، فراهم می آورد. شبکه‌های مش بی‌سیم انعطاف پذیرترین و کم هزینه ترین روش برای گسترش سرویس‌های پر سرعت اینترنت هستند که به صورت عمده در مصارف شخصی قابل استفاده اند.
هر رله‌ی بی‌سیم در این شبکه به عنوان عنصری از ساختار شبکه است و می‌تواند اطلاعات را از شبکه مش بی‌سیم به مقصد برساند. این نوع شبکه مشکلات وجود موانع در حیطه محیط رادیویی را از بین می‌برد و بسیار ارزان و راحت، شبکه را قابل گسترش می‌کند، زیرا در این ساختار هر رله فقط نیاز به برقراری ارتباط با رله مجاور خود دارد . ترافیک شبکه‌ای در صورت بروز هر مانع ، می‌تواند به سمت رله دیگر تغییر جهت می‌دهد، البته بدون آنکه نیازی به هر گونه تغییر در محل رادیوی مر کزی برای ارتباط بامکان های جغرافیایی دور دست باشد .
از آنجائیکه منطقه تحت پوشش هر نقطه دسترسی می‌تواند در اطراف موانع گسترش یابد، بنابراین تعداد نقاط دسترسی کاهش می یابد.
شبکه های مش بی‌سیم، دارای تکنولوژی ارزان قابل گسترش و برای دسترسی پر سرعت در محدوده های جغرافیایی دور دست مناسب هستند . RoofNet[a5] نمونه ای از این شبکه هاست. این شبکه معمولا شامل تعدادی نقاط دسترسی بی‌سیم است که درپنجره ها و پشت بام منازل نصب می شود و بسترهای اطلاعاتی کامپیوترهای خانگی توسط سیم به آنتن ها انتقال می‌یابد و از یک آنتن به آنتن دیگر منتقل می شود تا به یک دروازه2 اینترنتی برسد[a6].
در شبکه‌های مش بی‌سیم ترافیک هر SS3 توسط رله‌های شبکه برای انتقال به اینترنت یا شبکه خارجی دیگر به سمت BS4 هدایت می‌شود (شکل (1-2)).
شکل ‏12- انتقال ترافیک 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 به بعد عموماً شرکت‌های خصوصی هستند، به دنبال برطرف کردن نیازهای متنوع مشتریان خود باشند. اگر سرویس دهندگان اینترنت در شبکه‌های بی‌سیم بتوانند سرویسی باکیفیت ارائه کنند روزبه روز کاربردهای جدیدتری به وجود می آید و شبکه کاربران بیشتری پیدا می‌کند که این امر به نوبه ی خود سرویس دهندگان را از لحاظ اقتصادی در موقعیت بهتری قرار می‌دهد تا بتوانند سرویس هایی ارزان تر و با کیفیت بهتر ارائه کنند.
تعریف مسئله
در مسئله زمان‌بندی[a14] جهت ارسال بسته‌ها بین گره‌‌‌های درخواست کننده به BS از طریق رله‌ها در شبکه‌های مش بی‌سیم با رویکرد تضمین تأخیر انتها به انتها نیاز به درخواست و تخصیص پنجره‌های زمانی است. پنجره‌های زمانی به دو بخش با مدیریت متمرکز و مدیریت توزیع شده تقسیم می‌شوند. در مکانیزم متمرکز، که برای هدایت ترافیک اینترنت SS ها از طریق BS بکار برده می‌شود، BS مسئول زمانبندی ارسال‌ها در کل شبکه است. لذا زمانبندی در سطح شبکه انجام می‌شود. از آنجا که در این مکانیزم تمام بسته‌های کنترلی و دیتا از BS عبور می‌کنند، زمانبندی بصورت متمرکز و با قابلیت اطمینان بالا می‌باشد. با این حال تاخیر برپایی اتصال‌ها زیاد است. در مکانیزم توزیع شده، که برای ارتباط بین گره‌‌‌ها و هدایت ترافیک اینترانت(در داخل شبکه مش)استفاده می‌شود، ارسال‌ها به شکل کاملا توزیع شده و بدون نیاز به تعامل با BS زمانبندی می‌شوند. از آنجا که در این مکانیزم تصمیم گیری‌ها توسط گره‌‌‌ها بطور محلی و با توجه به بار ترافیکی و شرایط کانال فیزیکی گره‌‌‌ها صورت می‌گیرد، مکانیزم توزیع شده نسبت به مکانیزم متمرکز پویاتر، ولی پیچیده‌تر و دارای سربار بیشتر است. از آنجا که ترافیک اینترنت، عمده ترافیک شبکه را تشکیل می‌دهد، مکانیزم زمانبندی متمرکز، مکانیزم غالب می باشد.
[4] کارایی زمانبندی‌های متمرکز و توزیع شده در شبکه مش بی سیم را با هم مقایسه کرده است. نتیجه مطالعات نویسندگان نشان می‌دهد که برای ترافیک دراز مدت و پایدار به/ از BS، زمانبندی متمرکز نسبت به زمانبندی توزیع شده سربار کمتری دارد.
در بحث زمان‌بندی ارسال‌ها در شبکه‌های مش بی‌سیم با دو موضوع روبرو هستیم:
تعیین زمان ارسال پیغام‌های کنترلی
اختصاص پنجره‌های زمانی در زیر فریم دیتا به گره‌‌‌های شبکه برای حمل ترافیک کاربران
در استانداردهای مختلف الگوریتم زمانبندی برای ارسال پیغام‌های کنترلی مشخص شده است. ولی[a15] در ارتباط با زمانبندی ارسال دیتا، اگرچه نحوه سیگنالینگ و ساختار پیغام‌ها مشخص شده است، جزئیات الگوریتم زمانبندی و



همه حقوق محفوظ است

Posted آگوست 6, 2018 by 92 in category "مقالات

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *