مسیریابی در شبکه پویا با استفاده از الگوریتم ژنتیک و الگوریتم موریانه ای Routing in Dynamic Network using Ants and Genetic Algorithm

1. مقدمه

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

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

2. مسیریابی

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

در طی فرایند ایجاد مسیر، دو نوع از بسته ها مورد استفاده قرار می گیرند که به نام بسته های مسیریابی و بسته های داده می باشند. به بسته های مسیریابی، اولویت بالاتری در مقایسه با بسته های اطلاعاتی داده می شود. هر گره در شبکه بر مبنای ذخیره و ارسال می باشد. عملکرد پیوند از نقطه نظر پهنای باند یا تاخیر پیوند اندازه گیری می شود. توپولوژی شبکه بر مبنای افزایش تعداد گره ها، پیکره بندی یا عیب گره ها تغییر می یابد. این تغییر در توپولوژی می بایست در جدول مسیریابی بازتاب داده شود، که در عوض این کمک را به پروتکل های مسیریابی می کند تا مسیرهای مطلوب را برای حالت کنونی شبکه ایجاد کنند. بعضی از پروتکل ها بر مبنای پروتکل اطلاعات منبع (RIP)، پروتکل مسیریابی دروازه داخلی (IGRP)، اولین و کوتاه ترین مسیر منبع باز (OSPF)، و پروتکل دروازه مرزی (BGP) می باشند.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

3. الگوریتم موریانه ای

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

4. الگوریتم های ژنتیکی

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

4.1 نقطه قوت الگوریتم ژنتیکی

- یکی از مهمترین ویژگی های الگوریتم های ژنتیکی این می باشد که آن ها در ماهیت یکسان می باشند. آن ها به بررسی راه حل در جهات مختلف می پردازند. GA برای حل مشکلات مناسب می باشد به صورتی که فضای راه حل بسیار گسترده بوده و زمان مورد نظر برای جستجوی کامل بسیار زیاد می باشد.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

- GA دارای قابلیت حل مشکلات بدون هیچ اطلاعات قبلی می باشد.

عملکرد GA بر مبنای ارائه کارآمد، ارزیابی تابع تناسب و و پارامترهای دیگر همانند اندازه جمعیت، میزان تقاطع، و جهش و توان انتخاب می باشد.

نشان داده شده است که 55% از بسته ها زمانی که آن ها گره های مشابهی را بیش از یک بار ملاقات می کنند، از دست می روند. به منظور کاهش این مورد، موریانه ها به کاوش در شبکه مستقل از اطلاعات جدول مسیریابی می پردازند. با انجام این کار، وابستگی به جدول مسیریابی می تواند محدود گردد. هدف این کار ایجاد راه حلی برای بسته بندی کردن مشکلات مسیریابی متغیر می باشد.

5. تعریف مسئله

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

این طرح برای ایجاد تمام مسیرهای احتمالی از گره مورد نظر نسبت به تمام گره های دیگر در شبکه مورد استفاده قرار می گیرد. در آغاز مسیر تصادفی n مد نظر قرار می گیرد ( کروموزوم). این n به تعریف اندازه جمعیت می پردازد. این کروموزوم ها به عنوان جمعیت نسل اول فعالیت می کنند. موریانه های بعدی برای هر کروموزوم ایجاد می گردد. این امکان وجود دارد تا به کاوش در شبکه پرداخته و مسیرهایی را برای تمام گره ها در شبکه پیدا کنیم. موریانه های جلویی گره های بعدی را برای ملاقات از ان ها بر مبنای ارزش ژن در موقعیت و تراکم فرمون پیوند، انتخاب می کنند.

5.2 پردازش در هر گره

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

اگر (موریانه جلویی)

(به گره بعدی بر مبنای ارزش جایگاه ژن برسد)

به صورتی که ( پیوند موجود بوده و هیچ حلقه ای ایجادن نگردد) به این ترتیب

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

- موریانه جلویی به گره بعدی فرستاده می شود

به صورت دیگر اگر ( هیچ پیوندی وجود نداشته باشد)

- موریانه عقبی ایجاد شده و محتوای بار موریانه جلویی به موریانه عقبی منتقل می گردد

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

اگر موریانه عقبی

اگر گره موجود گره مبدا باشد

- مسیر ذخیره شده و موریانه عقبی گشته می شود

 

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

به ترتیب دیگر

موریانه عقبی و جلویی در ارتباط با پیوند در صف قرار می گیرد

- جدول مسیریابی بروز می گردد

 

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

موریانه عقبی کشته می شود

 

5.3 ایجاد مسیر بهینه

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

زمانی که گره مبدا تعداد m از موریانه عقبی را دریافت می کند،

1. نسبت هر کروموزوم را محاسبه کنید.

تناسب کروموزوم بر مبنای معادله 1 محاسبه می گردد.

تناسب= تعداد هاپ * 10 – هزینه کل مسیر

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

3. تقاطع را با احتمالات 0.6 اجرا کنید

4. جهش را با احتمال 0.01 اجرا کنید

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

6. اگر شرایط انقضا فسخ نشود، سپس مراحل 1 تا 3 را تکرار کنید. ( شرایط فسخ حاصل می گردد).

- مسیر را برای مدت زمان t ثانیه دخیره کنید

- داده ها را به مقصد از طریق مسیر ارسال کنید

 

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

5.3.1 انتخاب والدین

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

انتخاب رتبه- در انتخاب رتبه هر فرد بر مبنای رتبه اش انتخاب می گردد.

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

متقاطع سازی یا اپراتورهای ادغام شده به ادغام زیرشاخه های دو کروموزوم والد پرداخته و اولادی را ایجاد می کند که شامل بعضی از بخش های مواد ژنتیکی والدین می باشد. متقاطع سازی اساسا به دو نوع می باشد که به نام های متقاطع سازی تک نقطه ای و متقاطع سازی چند نقطه ای می باشد. در متقاطع سازی تک نقطه ای یک بخش سیستم متقاطع وجود دارد و در متقاطع سازی چندنقطه ای بیش از یک محل متقاطع وجود دارد. در متقاطع سازی تک نقطه ای یک نسل متشکل از بخش هایی قبل از بخش متقاطع والد 1 وبخشی بعد از بخش متقاطع والد 2 بوده و نسل دیگر متشکل از بخشی قبل از محل متقاطع والد 2 و بخشی بعد از محل متقاطع والد 1 می باشد. بخش زیر مثال هایی از تقاطع تک قطبی را نشان می دهد. والدین شامل مسیرهایی از مبدا 1 تا مقصد 6 بوده و محل تقاطع 4 می باشد.

از انجایی که این روش ساده می باشد، آن دارای مشکلاتی همانند شکل گیری سیکل ها زمانی که برای مسیریابی مورد استفاده قرار می گیرد می باشد. از مثال های قبلی، فرض کنید که نسل اول 1: 1 2 3 4 3 6 دارای سیکل 1 2 3 4 3 می باشند که مناسب نمی باشد. از این رو نیاز است تا از بعضی از تکنیک های متقاطع چند نقطه ای پیشرفته برای حذف چرخه استفاده کنیم. از بعضی از تکنیک های متقاطع چند نقطه ای پیشرفته عبارتند از تقاطع طراحی شده نسبی (PMX)، تقاطع سیکلی (CX)، و تقاطع منظم (OX) . این مقاله در ارتباط با روش PMX می باشد. در روش PMX دو سایت متقاطع به صورت تصادفی در میان رشته ها انتخاب می گردند. رشته های بین محل های متقاطع موقعیت به موقعیت مبادله می گردند، عوامل دیگر با مرتب سازی اطلاعات مشخص شده که نسبتا توسط هر یک از اولاد تعیین می گردند. PMX به منظور حفظ موقعیت کامل از هر دو والد طراحی می گردد.

در مثال بالا دو نقطه متقاطع در موقعیت 3 و 5 مد نظر قرار می گیرد. محتوای بین دو محل متقاطع اولاد مبادله شده و در نسل قرار می گیرد. عوامل باقیمانده بر این اساس مطرح می گردند. زمانی که نسل ایجاد شد، می بایست تایید گردد. تایید با بررسی کردن کروموزوم ها با تمام مسیرهای احتمالی انجام می گیرد. اگر نسل متعلق به تمام مسیرهای ممکن باشد، به این ترتیب نسبت ان محاسبه شده و به عملیات بعدی کشانده می شود. اگر نسل متعلق به تمام مجموعه مسیرهای احتمالی نباشد، به این ترتیب تقلیل می یابد.

5.3.3 جهش

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

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

زمانی که راه حل بهینه با استفاده از GA ایجاد شد، داده ها در آن مسیر جا به جا می گردند. تغییراتی در توپولوژی شبکه زمانی که بعضی از گره ها به شبکه می پیوندند یا بعضی از گره ها شبکه را ترک می کنند یا بعضی از گره ها عمل نمی کنند، ایجاد می شود. تغییر در شبکه با الگوریتمی در فاصله زمانی (نیاز به دانلود ترجمه) ثانیه آشکار می گردد.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.