MOEAQ : یک الگوریتم مسیریابی چند پخشی QoS Aware برای MANET


MOEAQ : یک الگوریتم مسیریابی چند پخشی QoS Aware برای MANET

چکیده-مسیریابی چندپخشی[1] بعنوان یک مولفه اساسی در شبکه در نظر گرفته می شود بخصوص که کاربردهای بلادرنگ [2] در سال های اخیر بطور فزاینده ای مورد توجه قرار گرفته است. این مقاله یک الگوریتم تکاملی چند هدفه جدید و سریعی را پیشنهاد می کند که MOEAQ نامیده می شود که از این الگوریتم برای حل مساله مسیریابی چندپخشی (MRP) در MANET استفاده می شود. نقاط قوت و محدودیت های شناخته شده مدل چند پخشی برای اولین بار در این مقاله بررسی می شود. بطور خاص، روش “گریدی[3]” و “رقابت داخلی[4]” در MOEAQ ادغام شده اند تا سرعت همگرایی را بالا برده و تنوع جمعیت را حفظ نمایند. اثبات تئوری روش پیشنهادی برای نشان دادن کارایی آن ارائه می شود. سپس،  یک پروتکل بهبود یافته مبتنی بر CBT برای ساده سازی MRP پیشنهاد شده، و در نهایت عملکرد MANET از 20 تا 200 گره با سرویس های مختلف درجه بندی  شده است با استفاده از OPNET ارزیابی می گردد. نتایج آزمایشگاهی (عملی) نشان می دهد که روش پیشنهادی قادر است تا همگرایی سریع تر و متمایز در مسیریابی چندپخشی در MANET و در مقایسه با دیگر پروتکل های مبتی بر الگوریتم ژنتیک[5] شناخته شده در مقالات را ارائه دهد.

 

کلیدواژگان-چند هدفه، الگوریتم تکاملی، MANET، مسیریابی QoS.

 

  1. مقدمه

مسیریابی چندپخشی توجه زیادی را در سال های اخیر به خود معطوف کرده است، چراکه یک مبدا را برای ارسال همزمان پیام ها به چندین مقصد قادر می سازد. تکنولوژی های مخابرات بی سیم[6] و تجهیزات موبایل کاربردهای مهم و مفیدی از شبکه های MANET بسیار پیشرفته را تحقق بخشیده است. مسیریابی چندپخشی نقش حساسی را در انتقال اطلاعات همانند داده های تصویری و دیگر  داده های جریانی بازی می کند. با این وجود، مشکل اصلی طراحی یک پروتکل مسیریابی برای MANET ، شبکه های توپولوژی دینامیکی می باشد که از حرکت های تصادفی گره ها در دامنه انتقال مبدا ناشی می شود. MANET که اساسا متفاوت از شبکه های قدیمی مبتنی بر زیر ساختار است خود‑ترکیبی بوده و مستقیما توسط یک سری از گره های موبایل شکل می گیرد.  در MANET ، تفاوت ساختاری شبکه ها و مقاصد، بهبود استفاده از پهنای باند و انعطاف پذیری سرویس را دشوار می نماید. از اینرو، تحرک میزبان (گره ها) طراحی توزیع چند رسانه ای را بسیار دشوار می نماید.

تاکنون، کارهای مختلفی شامل طراحی الگوریتم مسیریابی چندپخشی انجام شده است. مروری بر کارهای اخیر و راهکارهای فنی کلی مربوط به مخابره چند پخشی توسط Diot، Dabbous و Crowcroft (سال 1997) داده شد. Hanzo و Tafazolli (سال 2007) و Chen و Heinzelman (سال 2007) یک مرور از مسیریابی چندپخشی تحت پاسخ های قیود QoS برای MANET پیشنهاد کردند. بعنوان یک مساله کامل‑NP، برای ایجاد انواع الگوریتم های ابتکاری بمنظور محاسبه مسیرهای نزدیک به بهینه با QoS چندگانه یک موضوع تحقیق است. برای مثال، Wang، Cao، Cheng و Huang (سال 2006) سه روش محاسباتی هوشمند (الگوریتم ژنتیک، سردسازی فلزات و الگوریتم تابو) را برای تشکیل درخت های چند پخشی برای تامین جداگانه مخابره گروهی چندرسانه ای را بررسی کردند؛ الگوریتم های پیشنهادی، هم قید تاخیر سر به سر[7] و هم شرط مبدا شبکه را در نظر می گیرد؛ شبیه سازی عملکرد این سه روش ابتکاری را بر روی یک شبکه مخابراتی چند رسانه ای واقعی کوچک و یک شبکه بطور تصادفی ایجاد شده بزرگ ارزیابی می کند و سپس نتیچه گیری می کند که الگوریتم ژنتیک بهترین عملکرد را بر حسب کیفیت پاسخ نشان می دهد. در سال 2008، Qu، Zhao، Zhang و Shu یک سری قیود نرخ مبتنی بر گره را برای مدلسازی ارتباط تداخل بین گره ها در یک شبکه MANET برای تامین قیود نرخ برای عبور جریان QoSاش تامین می نماید، آن ها نشان دادند که این الگوریتم همیشه می تواند جریان های ممکن را پذیرفته، همچنین استفاده کامل از پهنای باند مبدا داشته باشد. Zahrani، Loomes، Malcolm و Albrecht )2006 و 2008) سردسازی لگاریتمی فلزات (LSA) را بعنوان پیش پردازشی از GA وارد کردند؛ این الگوریتم از عملگر جزئی تولید مثل (PMX) تحت مدل نخبه گرا استفاده می کند و تحلیل منظره[8] برای تخمین عمق مینیمم های محلی عمیق در منظره که با عمل مسیریابی و تابع هدف ایحاد شده ارائه می دهد؛ نتایج آزمایشگاهی (عملی) نشان می دهد که الگوریتم بر روی شبکه های ایجاد شده تصادفی بسیار کارا می باشد. Xu، Li  و Liu (سال 2004) و Ikeda و همکارانش (سال 2006) بر روی تولید یک مسیر قدرتمند برای یافتن پاسخ برای شبکه های داده شده تمرکز کردند؛ الگوریتم ژنتیک پیشنهاد شده و بترتیب اعضای[9] جمعیت توسط درخت ها نشان داده می شوند؛ الگوریتم از یک تولید مثل تک نقطه ای و یک عملگر جهش استفاده می کند که “اتصالات درخت ها” بطور تصادفی انتخاب می شوند، الگوریتم از مدل نخبه گرا استفاده می کند که اعضا  با بالاترین شایستگی در جمعیت برای نسل بعدی بدون تغییر باقی می ماند، نتایج شبیه سازی نشان می دهد که این الگوریتم بطور قابل قبولی در شبکه های کوچک و متوسط سریع می باشد. جدا از ساختار شبکه فوق، Rango، Tropea و Marano (سال 2006) و Mala و Swlvakumar (سال 2006) به طرحی که درخت مبتنی بر هسته (CBT) نامیده شده با الگوریتم ژنتیک اشاره دارند که یک مسیر جدید برای تحقق پروتکل مسیریابی چندپخشی در شبکه های بی سیم  ارائه می دهد با این حال نیاز به زمان اجرای بیشتری دارد.

[1] Multicast routing

[2] Real‑time applications

[3] Greedy

[4] Family competition

[5] GA‑based protocol

[6] Wireless communication technologies

[7] End‑to‑end delay constraint

[8] Landscape analysis

[9] Individuals

 

MOEAQ: A QoS-Aware Multicast Routing algorithm for MANET
Jun Huang a,*, Yanbing Liu b
a Institute of Network Technology Research, Beijing University of Posts and Telecommunications, 100876, PR China
bSchool of Computer Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, PR China
a r t i c l e i n f o
Keywords:
Multi-objective
Evolutionary algorithm
MANET
QoS routing
a b s t r a c t
Multicast routing is regarded as a critical component in networks especially the real-time applications
become increasingly popular in recent years. This paper proposes a novel fast multi-objective evolutionary algorithm called MOEAQ for solving multicast routing problem (MRP) in MANET. The strengths and
limitations of the well-known multicast model are analyzed firstly in this work. Specifically, the ‘‘Greedy”
and ‘‘family competition” approach are integrated into MOEAQ to speed up the convergence and to maintain the diversity of population. The theoretical validations for the proposed method are presented to
show its efficiency. After that, a CBT-based improved protocol is then proposed to simplify the MRP,
and finally, the performance of MANET scaled from 20 to 200 nodes with different types of service is evaluated by OPNET, experimental results show that the proposed method is capable of achieving faster convergence and more preferable for multicast routing in MANET compared with other GA-based protocol
well-known in the literature.
2009 Published by Elsevier Ltd

 

این فایل ورد (word) ترجمه در 23 صفحه و فایل اصلی لاتین pdf مقاله در 9 صفحه به خدمتتون ارائه میشود.

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

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