الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 48000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
دیدگاه مبتنی بر الگوریتم های ژنتیک برای مسیریابی چند پخشی گروهی
نام انگلیسی
A Genetic Algorithms Based Approach for Group
Multicast Routing
تعداد صفحه به فارسی
۳۸
تعداد صفحه به انگلیسی
۹
کلمات کلیدی به فارسی
مسیریابی چند پخشی گروهی، سرویس‌چند پخشی، الگوریتم ژنتیک
کلمات کلیدی به انگلیسی
Group multicast routing; Multicast services;
Genetic Algorithms.
مرجع به فارسی
ژورنال شبکه، دپارتمان مهندسی برق و الکترونیک، دانشگاه کاگلیئری، ایتالیا
مرجع به انگلیسی
JOURNAL OF NETWORKS, Department of Electrical and Electronic Engineering of University of Cagliari, Cagliari, Italy
کشور
ایتالیا
دیدگاه مبتنی بر الگوریتم های ژنتیک برای مسیریابی چند بخشی گروهی
چکیده
در عین آنکه روش ارسال چند بخشی در ارتباطات یک – به – چند به پراتور اجازه می‌دهد تا قویا قابلیت ذخیره سازی منابع شبکه را داشته باشد، این سیستم امر مسیریابی جریان‌های ترافیک، در مقایسه با ارسال تک بخشی، را پیچیده تر می‌سازد. بر این مبنا لازم می‌باشد تا تعداد بسیار زیادی از درخت های احتمالی را مورد توجه و آنالیز قرار داد تا آنکه بتوان نسبت به یافتن مسیرهای مناسب در امر مسیریابی اقدام نمود. جهت مخاطب قرار دادن چنین مشکلی، ما استفاده از الگوریتم های ژنتیک یا ژنی (GA) را پیشنهاد می‌کنیم که به میزان قابل توجهی تعداد راه‌حل‌هایی که می‌بایست مورد ارزیابی قرار گیرند را کاهش می‌دهد. با توجه بدین موضوع، در ابتدا یک رویه ابتکاری، جهت متمایز ساختن مجموعه‌ای از درختان احتمالی برای هر نشست چندبخشی به صورت مجزا، مورد استفاده قرار گرفت. پس از آن، از الگوریتم ژنتیک برای یافتن ترکیب مناسبی از درخت‌ها جهت مطابقت با نیازهای پهنای باند گروهی از نشست های چند بخشی بطور همزمان به کار گرفته شد. تناسب هر راه حل از طریق عبارتی مورد ارزیابی قرار گرفت که وزن هر دو مورد تخصیص پهنای باند شبکه و تاخیر یکسویه را مشخص می‌نماید. تابع هزینه برایند، تحت رهنمود پارامترهای اندکی می‌باشد که می‌توان آن را به آسانی در طی عملیات مهندسی ترافیک تنظیم نمود. یک مجموعه مناسبی از این پارامترها به اپراتور اجازه خواهد داد تا بتواند به خوبی بالانس متناسبی را بین منابع مورد استفاده در شبکه و کیفیت سرویس فراهم آورد. بر این مبنا شبیه‌سازیهایی نیز جهت مقایسه الگوریتم پیشنهادی با راهحلهای جایگزین بر حسب بهره برداری از پهنای باند و تأخیر ارسال انجام شده است.
کلمات کلیدی: مسیریابی چند بخشی گروهی، سرویس‌های چند بخشی، الگوریتم‌های ژنتیک.
الگوریتم ژنتیک مسیریابی چند پخشی گروهی
۱- مقدمه
ارسال چند بخشی داده‌های چند رسانه‌ای به عنوان یک سرویس مهم تلقی می‌شود که بوسیله لایه شبکه فراهم می‌گردد. در حقیقت، چنین سیستمی‌‌به اپراتور اجازه می‌دهد تا بتواند نسبت به صرفه جویی در مقادیر زیادی از منابع شبکه و در موارد بسیار اقدام نماید. یکی از مهمترین رویه های کاربردی که از سیستم ارسال چند بخشی سود می‌برد سیستم استریمینگ ویدئو کلیپ می‌باشد، جائیکه غالباً مقادیر مشابهی از اطلاعات به صورت همزمان به میلیونها کاربر در اینترنت ارسال می‌شود. برنامه کاربردی دیگری که می‌توان از آنها نام برد IPTV می‌باشد، که بوسیله اغلب ارائه دهندگان خدمات ISP در خلال چندین سال اخیر بکار گرفته خواهد شد. در عین حال رویه های کاربردی بسیار دیگری را نیز می‌توان در این زمینه بر شمرد.
یکی از مشکلات مهمی‌که به هنگام پیاده سازی سرویس های چند بخشی وجود دارد طراحی درخت های چند بخشی می‌باشد که بر روی کیفیت کار و رویه های بهره برداری از اینترنت تأثیر گذار خواهد بود. در ابتدا برای مخاطب قرار دادن چنین مشکلی لازم است تا توجه خود را به یک نشست چند بخشی واحد جلب نماییم و بر روی به حداقل رسانی هزینه ارسال هر درخت واحد تمرکز نماییم. بسیاری از الگوریتم های ابتکاری برای حل مورد بدون محدودیت NP-کامل [۱]-[۲]، که تحت عنوان مشکل درخت استاینر نیز خوانده می‌شود، ارائه گردیده اند. تحقیقات دیگری نظیر [۳]-[۵]، این مسئله را با معرفی محدودیت ها یا قیدهای مربوطه بر روی برآیند کیفیت سرویس (QoS) تعمیم داده اند، که غالباً بر حسب تأخیر ارسال انتها ـ به ـ انتها مورد ارزیابی قرار می‌گیرد.
از آنجائیکه در دنیای حقیقی چندین نشست چند بخشی به صورت توأم و همزمان رخ می‌دهند، یک رویه بهینه سازی جدید و پیچیده تر مشکلات را می‌بایست مد نظر قرار داد: یعنی، مشکل مسیریابی چند بخشی گروهی که در مطالعه بهترین ترکیب درخت‌ها، برای حاصل آوردن نشست های همزمان بیشتر، مورد توجه قرار گرفته است. تاکنون، تنها مقاله‌های اندکی در این زمینه انشار یافته‌اند [۶]-[۹]. علی‌الخصوص چن و همکاران [۸] از یک دیدگاه برنامه‌نویسی- عدد صحیح استفاده نمودند که در آن تنها آن دسته از نشست هایی مد نظر قرار گرفته است که دارای نیازهای پهنای باند یکسانی می‌باشند. آنها نسبت به تعریف مشکل فشرده سازی چند بخشی اقدام نمودند که در آن شبکه مربوطه سعی خواهد نمود که به صورت همزمان نسبت به گنجاندن کلیه گروه‌های چندبخشی اقدام نماید و در عین حال از بروز تنگناها و مشکلات بر روی لینک‌هایی که دارای عملکرد بالایی می‌باشند نیز جلوگیری نماید (همانند به حداقل‌رسانی لینک‌های متراکم که در بین گروه های چند بخشی به اشتراک گذاشته شده‌اند). بحداقل‌رسانی تراکم حداکثری با توجه به هزینه افزایش اندازه برخی از درخت های چند بخشی حاصل خواهد شد، موردی که در مقابل بر روی تأخیر نیز تاثیر خواهد داشت. چنین موضوعی از طریق اضافه نمودن یک عبارت پنالتی به تابع هدف فرمولاسیون فشرده سازی بهینه مورد خطاب قرار می‌گیرد. این عبارت به عنوان تابع میزان گسترش یا تغییر حجم از اندازه درخت بهینه، حاصل آمده برای هر نشست چند بخشی، به صورت مستقل از دیگران، یعنی به صورت مجزا یا ایزوله، مد نظر می‌باشد. از آنجائیکه فرمولاسیون برنامه نویسی ریاضی برای مشکل بهینه سازی از نظر محاسباتی سخت می‌باشد، آنها به راه حل های زیر- بهینه ابتکاری رجوع نمودند.
…
این مقاله به شرح ذیل سازماندهی شده است. بخش ۲ تشریح کننده مشکل مسیریابی چند بخشی گروهی می‌باشد. بخش ۳ ارائه دهنده راه حل مبتنی بر الگوریتم ژنتیک پیشنهادی است. بخش ۴ پیچیدگی کلی را مورد تجزیه و تحلیل قرار می‌دهد و بخش آخر نتایج تجربی را مرور خواهد نمود.
الگوریتم ژنتیک مسیریابی چند پخشی گروهی
۲- مشکل مسیریابی چند بخشی گروهی
مشکل مسیریابی چندبخشی گروهی به شرح ذیل تعریف می‌شود: ارائه ترافیک تک‌بخشی شناخته شده به یک شبکه موجود، یافتن ظرفیت لینک بهینه و رویه‌های تخصیص آن جهت جای دادن ترافیک چندبخشی وجود آمده به وسیله گروهی از منابع چندبخشی. رویه بهینه‌شدگی را می‌بایست بر مبنای نوع سرویسهایی که در نشست‌های چند بخشی رد و بدل می‌شوند و همچنین اهداف اپراتور تعریف نمود. با این وجود، کاربرد پهنای باند و تأخیر ارسال به طور گسترده در این مقاله مورد استفاده قرار می‌گیرند.
ما شبکه ارتباطات را با استفاده از یک گراف هدایت شده مدل سازی نمودیم، جائیکه V مجموعه متناهی رئوس (گره‌های شبکه)، وE مجموعه لبه‌های (لینک‌های شبکه)، با ظرفیت و ترافیک زمینه می‌باشند. تعداد گره‌ها و لینکها (یعنی، بزرگی‌های V و E ) بترتیب N وE می‌باشند. اجازه دهید تا S به عنوان زیر مجموعه‌ای ازV باشدکه معرف گروه گره‌های منبع چند بخشی است: ، و . برای هر نشست z، یک گره منبع رویه انتقال به گروه مقصد چند بخشی با نرخ را دنبال می‌نماید. در V شامل شده است و تعداد گره های در نیز به میزان است، با . یک راه حل برای مشکل مسیریابی چند بخشی گروهی به وسیله مجموعه‌ای از درختهای چند بخشی ارائه شده است، جائیکه هر درخت ریشه در داشته و بعنوان مجموعه‌ای از گره‌های برگی می‌باشد. بر این مبنا، ممکن است راه حل‌های بسیاری برای یک مجموعه از نشست های چند بخشی وجود داشته باشد. تنظیم بهینه درختهای وابسته به هدف اپراتور می‌باشد، که غالباً بر مبنای کاربرد شبکه، تأخیر ارسال و کیفیت سرویس هدف خواهد بود. غالباًً تناسب هر یک از راهکارهای احتمالی از طریق تابع هزینه خاص تحت محدودیتها یا قیدهای مشخصی مورد ارزیابی قرار می‌گیرد. در چنین موردی، حل مشکل مسیریابی چند بخشی گروهی مترادف با یافتن مجموعه بهینه‌ای از درخت های توزیع بر مبنای چنین تابع هزینه ای خواهد بود.
الگوریتم ژنتیک مسیریابی چند پخشی گروهی
۳- راه حل پیشنهادی
در راه حل ما، مزیت های الگوریتم های ژنتیک جهت یافتن یک ترکیب مناسب (زیر بهینه) درختهای چندبخشی و به منظور مسیریابی پاکت های داده‌ای بکار گرفته شده است که بوسیله هر منبع Sz تولید شده است. بر این مبنا، کروموزوم بعنوان ترکیب S ژن‌های gz مد نظر خواهد بود، که هر کدام معرف یک درخت چند بخشی احتمالی برای یک نشست خاص می‌باشند. gz یک عدد صحیح می‌باشد که در حقیقت بعنوان شاخص مشخص‌کننده یک درخت چند بخشی در بین مجموعه عرضه شده ای از نشست چند بخشی مطرح می‌باشد. چنین دیدگاهی نیازمند یک محاسبه اولیه نشست های چند بخشی احتمالی برای هر نشست به صورت مجزا یا ایزوله می‌باشد، که به وسیله ترکیب نمودن مسیرهای تک بخشی مشخص می‌گردد. زیر بخش‌های ذیل تشریح کننده این موارد خواهند بود: رویه یافتن مجموعه ای از درخت ها برای هر راه حل چند بخشی به صورت مجزا، تابع هزینه جهت ارزیابی تناسب هر راه حل و کاربرد الگوریتم ژنتیک.
الف. درخت های چند بخشی به صورت ایزوله یا مجزا
راهحلهای بالقوه برای مشکل مسیریابی چند بخشی به صورت مجزا از طریق ترکیب مسیرهای تک بخشی، که هر جفت از منبع ـ مقصد در یک نشست را به هم متصل می‌سازند، مشخص شده‌اند. در ابتدا، چنین مسیرهایی از ویژگی پایین ترین تعداد جهش ها برخوردار بوده که از طریق کاربرد الگوریتم کوتاه ترین مسیر Dijkstra [17] بین هر جفت منبع- مقصد مشخص می‌گردند. دوماً مسیرهای جایگزین از طریق تصحیح کوتاه ترین مسیرها محاسبه می‌شوند. این موارد تحت عنوان مسیرهای اضافه در ذیل پیگیری می‌شوند. از آنجاییکه چنین رویه‌ای به کوتاه ترین مسیرها همچنین برای گره هایی که معرف جفت های منبع- مقصد نمی‌باشند نیز نیاز خواهد داشت، الگوریتم Dijkstra برای هر جفت از گره‌ها در شبکه ها از زمان شروع به کار گرفته می‌شود.
ب. کاربرد الگوریتم های GA
همانند رویه‌های کاربردی بیشمار دیگر الگوریتم های GAارائه شده در این مقاله، جمعیت تحت بررسی به صورت تصادفی مقدار دهی شده و بر این مبنا نسبت به ایجاد یک جمعیت Pاز کروموزوم های اقدام شد، که هر کدام به وسیله ژن‌های S ایجاد می‌شوند. توجه داشته باشید که چنین راه حل‌هایی از طریق اعمال رویه‌های تکامل جمعیتی بواسطه اپراتورهای تقاطع یا کراس‌اور (crossover) و جهشی مشخص گردید. علی الخصوص، مهم ترین بخش تناسب یافته جمعیت انتخاب شده و به طور مستقیم در نسل جدید به کار گرفته شده است، در حالی که بقیه جمعیت به کناری گذاشته شده و جایگزین زیر جمعیت ایجاد شده از طریق اپراتورهای کراس‌اور و جهشی گردیدند. یک اپراتور کراس‌اور (با احتمال CROSS) به منظور تبادل مولفه‌های هر دو رشته مورد استفاده قرار گرفت، در حالی که اپراتور جهش (با احتمال MUT) سعی بر انجام جستجو با استفاده از موارد بهینه محلی دارد. در حالت وجود دو کروموزوم یکسان که برایند عملیات کراس‌اور و جهش می‌باشند، دو مورد منحصر بفرد به صورت تصادفی ایجاد می‌شود. شرط قطع به هنگامی‌ارضا خواهد شد که یا g به تعداد انتخابی تکرارهای (IT) دست یابد و یا آنکه تابع برازندگی دارای ارزش برابری با تکرار های باشد.
ج. ارزیابی
تناسب یا برازندگی کروموزوم به وسیله توابع یا مورد ارزیابی قرار گرفت. اولین تابع به هنگامی مورد استفاده قرار گرفت که حالت بهینگی دارای همبستگی با توزیع یکنواخت ترافیک در طول کل شبکه بوده است. تابع دوم نیز به هنگامی‌به کار گرفته شد که حالت بهینگی منوط به هر دو عامل اشغال منبع شبکه و تاخیر ارسال باشد. تعریف دقیق این توابع هزینه در زیر بخش های ذیل ارائه شده است.
ج-۱٫ مشارکت پهنای باند
تابع هزینه پیشنهادی می‌بایست نسبت به ارزیابی توزیع پهنای باند بر فراز لینک‌های شبکه و بگونه‌ای اقدام نماید که بتواند یکنواخت ترین کارایی منبع را به دست آورد. بدین روش، درختهای پهن با بهره گیری از میانگین پائین لینک را می‌توان حتی در صورتی انتخاب نمود که درخت های کوچکتری وجود داشته باشند، اما آنها باید از نظر بهره‌گیری از لینک میانگین بالاتری را داشته باشند. به علاوه، محدودیتی در خصوص تاخیر کلی ارسال در هر مسیر، در هر نشست چند بخشی، نیز اعمال می‌گردد.
ج-۲٫ مشارکت پهنای باند و تأخیر: سطح DـB
هدف تابع برازش ثانویه مشخص نمودن وزن هر دو کاربرد پهنای باند و تأخیر ارسال یکسویه می‌باشد. این دو مؤلفه ها در ترکیب با یکدیگر در یک تابع هزینه به اپراتور اجازه خواهند داد تا بتواند نسبت به حصول یک وجه المصالحه بهینه بین تأخیر سرویس و کاربرد منبع شبکه اقدام نماید. به طور آشکار هیچ گونه تعریف عمومی در زمینه حالت بهینه در این چارچوب وجود ندارد، چرا که چنین موضوعی وابسته به نظر اپراتور شبکه خواهد بود. بر این مبنا، در اینجا ما یک تابع هزینه پارامتری را تعریف می‌کنیم که فراهم آورنده یک روش ساده جهت ترکیب تأخیر و کاربرد شبکه از طریق مشخص نمودن چندین مورد از پارامترها می‌باشد.
الگوریتم ژنتیک مسیریابی چند پخشی گروهی
۴- آنالیز پیچیدگی
برآیند پیچیدگی زمانی وابسته به تابع هزینه استفاده شده نمی‌باشد و به وسیله تشریح می‌گردد، جائیکه :
۵- رویه های آزمایشی
الف. تنظیمات
در این بخش، ما نتایج پیکربندیهای مختلف شبکه را ارائه می‌نماییم. توپولوژی های شبکه به کار گرفته شدده در این شبیه سازی از طریق یک مدل گراف تصادفی تولید شده است که به وسیله واکسمن [۱۹] پیشنهاد گردید. این رویه تولید در ابتدا به صورت تصادفی اقدام به توزیع گره‌های N در یک شبکه مختصات مربعی خواهد نمود. لینک بین هر دو گره و به وسیله تابع احتمال ، اضافه می‌شود، جائیکه فاصله کارتزین یا دکارتی بین گره های و می‌باشد، بعلاوه l فاصله احتمالی حداقلی بین هر دو گره خواهد بود و پارامتر های و اعداد حقیقی در محدوده ( ۱، ۰) به شمار می‌آیند. توجه داشته باشید که این پارامترها را می‌توان به صورتی مناسب تنظیم نمود تا آنکه بتوان ویژگی مطلوبی را در گراف حاصل شده به دست آورد. در شبیه سازیهای مربوطه، ما نسبت به مشخص نمودن مقادیر گره‌ها اقدام نمودیم: و برای گره‌های N=20. ما تنها از گراف های متصل استفاده کردیم : در صورتی که گراف ایجادی متصل نباشد، این گراف کنار گذاشته خواهد شد.
ب. آنالیز تست
در ابتدا، ما برخی از تست‌ها یا آزمایشات را جهت آنالیز اهمیت پارامترهای الگوریتم ژنتیک انجام دادیم: از نظر محدوده (۳۲،۱۶،۸ ،۶۴) در نوسان بوده و CROSS و MUT نیز در محدوده‌های متفاوت و به ترتیب قرار می‌گیرند. حداکثر تفاوت بر حسب مقدار تابع هزینه نهایی در بین کلیه راه حل ها کمتر از ۲% مشخص شد، که در اغلب موارد می‌توان آن را تحمل کرد بر این مبنا می‌توان ملاحظات ذیل را مد نظر قرار داد: یک اندازه جمعیتی بالا سبب حاصل شدن راه حل های بهتری به بهای زمان پردازش بیشتر خواهد شد، پارامترMUT بر این مبنا به عنوان موردی مساوی با یا بزرگتر از ۱/۰ مشخص گردید تا از تعداد زیاد تکرارها جلوگیری شود.
الگوریتم ژنتیک مسیریابی چند پخشی گروهی
۶- نتیجه گیری
در این مقاله ما کاربرد الگوریتم ژنتیک جهت کاهش پیچیدگی محاسباتی در مسیریابی چند بخشی گروهی را عرضه نمودیم. به علاوه، یک تابع هزینه جدید نیز پیشنهاد گردید که مشخص کننده وزن تخصیص پهنای باند و کیفیت سرویس بر حسب تاخیر یکسویه می‌باشد. عبارت تابع هزینه به گونه ای تدبیر و به کار گرفته شد تا به اپراتورها اجازه دهد تا بتوانند نسبت به پیکر بندی و اعمال یک بالانس مطلوب بین رویه های به کار گیری منابع شبکه و کیفیت سرویس فراهم شده، از طریق تنظیم چندین پارامتر، اقدام نمایند. نتایج تجربی نشان داد که این الگوریتم پیشنهادی اجازه حصول توزیع بهتر ترافیک وابسته به یک نشست را خواهد داد و از ایجاد تنگناهای نامطلوب نیز جلوگیری خواهد نمود.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
