مسیریابی چند بخشی با تعادل بار (مقاله ترجمه شده)

چکیده

با گسترش روزافزون خدمات چندرسانه ای و کاربردهای ارتباطی گروهی، نیاز به مسیریابی چند بخشی برای پاسخ به درخواست های چند بخشی در شبکه های مش بی سیم بیشتر از قبل احساس می شود. یکی از چالش های اصلی در شبکه های مش بی سیم چند رادیویی چند کانالی استفاده ی کارا از ظرفیت کانال ها و همچنین تعادل بار در شبکه است.در این مقاله، ما یک الگوریتم برای ایجاد یک درخت چند بخشی پیشنهاد کردیم، یعنی مسیریابی چند بخشی تعادلی بار با الگوریتم ژنتیک (LM-GA). هدف از این الگوریتم ایجاد یک درخت چند بخشی برای دوره های درخواست شده در شبکه های مش بی سیم چند کانالی چند رادیویی (MCMR WMN ها) در رابطه با تعادل بار در کانال ها از طریق به حداقل رساندن حداکثر مقدار استفاده از کانال ها است. نتایج کارایی LM-GA در توزیع بار در کانال های شبکه با پیدا کردن راه حل های نزدیک بهینه و همچنین افزایش عملکرد شبکه ضمن اجتناب از ایجاد گلوگاه ها نشان می دهند.

مقدمه

در طی تکامل شبکه های مختلف بی سیم در نسل بعدی برای ارائه خدمات بهتر، یک تکنولوژی کلیدی پدید آمده است که به عنوان شبکه های مش بی سیم شناخته می شود(WMN ها). این شبکه ها به دلیل هزینه پایین، تعمیر و نگهداری راحت، قابلیت اطمینان و استواری آنها محبوب و معروف هستند [1]. در WMN ها بسته ها از گره منبع به گره مقصد در یک روش چند هوبی ارسال می شوند. گره ها شامل روترهای مش و کلاینت های مش هستند. کلاینت های مش دستگاه های کاربر نهایی نامیده می شوند و در عین حال روترها نقش نقطه دسترسی گذر را برای تبادل اطلاعات بین کلاینتها یا کلاینت ها- اینترنت ایفا می کنند. برخی از روترهای مش دسترسی مستقیم به شبکه های سیمی دارند و به عنوان دروازه برای گره های دیگر به منظور دسترسی به اینترنت عمل می کنند.

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

کارهای مرتبط

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

مدل سیستم و توصیف مشکل

در این بخش،ما مدل شبکه، مدل تداخل و مشکلی را که حل خواهد شد، توضیح می دهیم.

الف. شبکه و مدل تداخل MCMR WMN شامل n روتر ثابت مش و هر روتر به چند کارت شبکه نیمه دوپلکس مجهز است.

هر کارت شبکه با یکی از کانال های غیر همپوشانی k تطبیق می شود و امکان تغییر کانال وجود ندارد. نمایش گراف برای مدلسازی شبکه استفاده شده است. در این نمایش، (G = (V، Eگراف شبکه ای را نشان می دهد که در ان Vمجموعه ای از روتر ها است، ماتریس Eنشان دهنده ارتباط بین گره ها و مقادیر آنها نشان دهنده کانال اختصاص یافته به لینک ها است.

مسیر یابی چند بخشی متعادل بار با الگوریتم ژنتیک

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

نمایش جمعیت

در این مقاله هر فرد (کروموزوم) به عنوان یک مسیر از منبع به یکی از مقصد های چندپخشی تعریف می شود. یک دنباله از اعداد صحیح برای نشان دادن روترها استفاده می شود. برای مثال در شکل 3 مسیر بین گره منبع (گره 14) و گره مقصد (گره 2) در یک توالی از {14، 10، 11، 7، 3، 2} نشان داده می شود.

تجزیه و تحلیل عملکرد و نتایج مدل سازی

در این بخش ما در مورد عملکرد الگوریتم LM-GA بر اساس معیارهای زیر بحث خواهیم کرد.

واریانس استفاده از کانال ها

انحراف استاندارد استفاده از گره ها (SDNU)

میانگین تاخیر انتها به انتها

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

عملکرد LM-GA با الگوریتم LMTR [3 و SPT با استفاده از شبیه سازی در MATLABمقایسه می شود. در اینجا شبکه مش بیسیم چند کاناله چند رادیویی همراه با 16 روتر مش در یک توپولوژی شبکه در نظر گرفته می شود. در این توپولوژی روترها در فاصله 100 متر از یکدیگر قرار دارند. محدوده انتقال و محدوده تداخل به ترتیب 120 و 200 متر در نظر گرفته می شوند.

سناریو # 1

در اینجا یک شبکه ثابت 4 × 4 در نظر گرفته شد. الگوریتم های LM-GA، LMTR و SPT ده بار برای 100 دوره اجرا شدند. نتایج مقایسه به طور جداگانه برای هر معیار مطرح شده در بخش قبلی به شرح زیر ارائه شده است:

همانطور که در شکل 5 (a)، (b) نشان داده شده است، نتایج الگوریتم LM-GA که با استفاده از الگوریتم ژنتیک فراشناختی به دست آمده، نشان دهنده بهبود در استفاده هر دو کانال و انحراف معیار عوامل کاربرد درمقایسه با نتایج الگوریتم های SPT و LMTR است. به عبارت دیگر،کانال ها در الگوریتم LM GA بیشتر متعادل هستند. بنابراین، همانطور که نتایج نشان می دهد یک یا چند کانال در اضافه بار اولی به پایان نمی رسد و آنها غیر قابل دسترس نمی شوند.گاهی اوقات این تعادل مستلزم انتخاب مسیرهای طولانی تر است و بنابراین، همانطور که نمودار در شکل 5 (c) نشان می دهد، متوسط تاخیر انتها به انتها کمی افزایش یافته است.

نتیجه گیری

این مقاله به حل مساله مسیر یابی چند بخشی با درنظر گرفتن توازن بار در لینک MCMR WMN تمرکز دارد. به منظور جلوگیری از ایجاد تنگنا و اضافه بار در یک یا چند کانال، حداکثر استفاده از کانال برای توزیع متعادل بار در کانال های شبکه به حداقل رسیده است. برای تحقق این هدف، الگوریتم فراشناختی ژنتیکی به کار گرفته شد.

نتایج شبیه سازی نشان می دهد که در هر دو سناریو که از الگوریتم LM-GA استفاده می شود، واریانس استفاده از کانال ها کمتر از زمان استفاده از الگوریتم های LMTR و SPT است. حتی هنگامی که اندازه شبکه افزایش می یابد، واریانس بر این اساس کاهش می یابد. به عبارت دیگر، بار توزیع شده بین کانال ها متعادل تر است و ظرفیت کانال ها تقریبا به طور مساوی استفاده می شود. بنابراین، حداکثر استفاده از کانال کاهش می یابد و ظرفیت کانال بیشتری برای دوره های آینده در دسترس خواهد بود.

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

این مقاله ISI در سال 2017 در نشریه Thesai و در مجله بین المللی علوم کامپیوتر پیشرفته و برنامه های کاربردی، توسط گروه مهندسی کامپیوتر منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله مسیریابی چند بخشی با تعادل بار در سایت ای ترجمه مراجعه نمایید.