دانلود ترجمه مقاله الگوریتم تکاملی چند هدفه مبتنی بر مسیریابی QoS – الزویر 2015

الگوریتم تکاملی چند هدفه مبتنی بر مسیریابی QoS در شبکه های بی سیم مش

A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks

چکیده

1- مقدمه

2-کارهای مرتبط

1-2 بهینه سازی یک هدفه در WMN

2- 2 بهینه سازی چند هدفه

1- 2- 2 بهینه سازی چند هدفه در WMN

3- فرمولاسیون مسئله

1- 3 متغیر تصمیم

2-3 توابع هدف

1- 2- 3 تاخیر در ارسال

2- 2- 3 تعداد مورد انتظار ارسال (ETX)

3- 3 محدودیت های مدل

1- 3-3 حفظ جریان

4- الگوریتم تکاملی چند هدفه برای مسئله مسیریابی

1- 4 نمایش کروموزوم

2- 4 تولید جمعیت اولیه

3- 4 کراس اور

4- 4 جهش

5- 4 فاصله ازدحام پویا (DCD)

6- 4 الگوریتم MNSGA-II

7- 4 فرایند تحلیل سلسله مراتبی

5- ارزیابی عملکرد

1- 5 تنظیم پارامترها در MNSGA-II و R-NSGA-II

2- 5 تجزیه و تحلیل عملکرد

1-2- 5 ارزیابی پسین جبهه بهینه پارتو

2- 2- 5 متریک عملکرد

6- نتیجه گیری

چکیده

تقاضای زیاد برای سرویس ها و خدمات بلادرنگ در شبکه های مش بی سیم (WMN)، باعث بروزموضوعات چالش برانگیز زیادی برای تامین کیفیت خدمات (QoS) می گردد. طراحی پروتکل های مسیریابی QoS، که اهداف متعددی را بهینه می سازند، از لحاظ محاسباتی سخت می باشد. این مقاله، با استفاده ازMNSGA-II ، مدل جدیدی برای مسیریابی پیشنهاد می نماید. اهدافی که در اینجا مد نظر قرار داده می شوند، عبارتنداز: به حداقل رساندن تعداد مورد انتظارارسال و تاخیر در ارسال. برای حفظ تنوع در راه حل های غیر غالب، روش فاصله ازدحام پویا (DCD) در NSGA-II پیاده می شود. شبیه سازی در شبیه ساز شبکه 2 (NS-2) انجام شده و با استفاده از متریک های تعداد مورد انتظار ارسال و تاخیر در ارسال، با تغییر تحرک پذیری گره و با افزایش تعداد گره ها، مقایسه هایی صورت می گیرد. مشاهده می شود که MNSGA-II، کارایی را بهبود بخشیده و تاخیر در ارسال (تاخیر ارسال) را برای تعداد متغیری از گره ها و تحرک پذیری بالاتر، به حداقل می رساند. شبیه سازی نشان می دهد که الگوریتم MNSGA-II قطعاً برای حل مسئله مسیریابی چند هدفه مناسب تر می باشد. در اینجا ازروش تصمیم گیری مبتنی بر فرایند تحلیل سلسله مراتبی (AHP) برای تطبیق بهترین راه حل توافقی از مجموعه راه حل های پارتو بدست آمده از طریق MNSGA-II استفاده شده و عملکرد MNSGA-II از لحاظ گستره، با NSGA-II مبتنی بر نقطه مرجع (R-NSGA-II) مقایسه می شود.

6- نتیجه گیری

در این مقاله، الگوریتم MNSGA-II برای مسیریابی در شبکه مش بی سیم پیشنهاد شده است. با توجه به حضور لینک ها یا اتصال بین گره ها، وضعیت مرتبط با شبکه لینک ها مثل تاخیر در ارسال و تعداد مورد انتظار ارسال در لینک ها، جمع آوری و اندازه گیری می شود. این معیارها، میزان تناسب یک لینک را نشان داده و در عین حال راجع به مسیرهای مناسب برای مسیریابی QoS تصمیم گیری می نمایند. با استفاده از این الگوریتم، می توانیم راه حل هایی بدست بیاوریم که تعداد مورد انتظار ارسال و تاخیر در ارسال را به طور همزمان به حداقل می رسانند. با استفاده از رمزگذاری مبتنی بر اولویت، مسیرهای متعددی از مبدا تا مقصد یافت شده است. الگوریتم MNSGA-II برای شبکه های ایستا و تصادفی پیاده می شود. تحت دو سناریو، یکی تغییر تعداد گره ها ودیگری سرعت تحرک پذیری، عملکرد MNSGA-II با R-NSGA-II مقایسه شده ومشاهده می شود که کارایی، بهبود و تاخیر در ارسال به حداقل رسانده می شود. نتایج شبیه سازی نشان می دهد که با استفاده از روش فاصله ازدحام پویا، MNSGA-II در مقایسه با R-NSGA-II، در مدت زمان کوتاهتر راه حل های توزیع شده بهتر و یکنواخت تری عرضه می نماید. از دیدگاه تصمیم گیرنده، از فرایند تحلیل سلسله مراتبی برای تعیین بهترین راه حل توافقی بین مجموعه متناهی از راه حل های پارتو بدست آمده از طریق MNSGA-II استفاده می شود. معیار عملکرد چند هدفه آماری نظیر گستره، عملکرد تنوع MNSGA-II را تائید می نماید. کار آتی بر متریک های چند کانالی/ چند رادیویی مسیریابی تمرکز می نماید که در الگوریتم MNSGA-II کاربرد دارد.

Abstract

The huge demand for real time services in wireless mesh networks (WMN) creates many challenging issues for providing quality of service (QoS). Designing of QoS routing protocols, which optimize the multiple objectives is computationally intractable. This paper proposes a new model for routing in WMN by using Modified Non-dominated Sorting Genetic Algorithm-II (MNSGA-II). The objectives which are considered here are the minimization of expected transmission count and the transmission delay. In order to retain the diversity in the non-dominated solutions, dynamic crowding distance (DCD) procedure is implemented in NSGA-II. The simulation is carried out in Network Simulator 2 (NS-2) and comparison is made using the metrics, expected transmission count and transmission delay by varying node mobility and by increasing number of nodes. It is observed that MNSGA-II improves the throughput and minimizes the transmission delay for varying number of nodes and higher mobility scenarios. The simulation clearly shows that MNSGA-II algorithm is certainly more suitable for solving multiobjective routing problem. A decision-making procedure based on analytic hierarchy process (AHP) has been adopted to find the best compromise solution from the set of Pareto-solutions obtained through MNSGA-II. The performance of MNSGA-II is compared with reference point based NSGA-II (R-NSGA-II) in terms of spread.

6- Conclusion

In this paper, Modified Non-dominated Sorting Genetic Algorithm-II (MNSGA-II) is proposed for routing in wireless mesh network. While considering the presence of links or connectivity between nodes, network-related status of links like transmission delay and expected transmission count in links are collected and measured. These measures offer an indication of how much a link is appropriate while deciding about paths for providing QoS routing. By using this algorithm, we are able to obtain solutions that simultaneously minimize the expected transmission count and the transmission delay. From a given source to destination, multiple paths have been found by using the priority based encoding. MNSGA-II algorithm is implemented for both static and random networks. The performance of MNSGA-II is compared with RNSGA-II under two scenarios namely varying number of nodes and mobility speed and it is observed that it improves the throughput and minimizes the transmission delay. The simulation results show that, MNSGA-II provides better and more uniformly distributed solutions in a shorter time as compared with R-NSGA-II using the dynamic crowding distance method. From a decision maker’s perspective, analytic hierarchy process is used to determine the best compromise solution from the finite set of Pareto-solutions obtained through MNSGA-II. The statistical multiobjective performance measure such as spread is considered to validate the diversity performance of MNSGA-II. Future work will be focused on multiple radio/multiple channel metrics of routing applied to MSNGA-II algorithm.

تصویری از مقاله ترجمه و تایپ شده در نرم افزار ورد

الگوریتم تکاملی چند هدفه مبتنی بر مسیریابی QoS در شبکه های بی سیم مش

A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks