استفاده از کلونی مورچه در مسیریابی در شبکه دیتاگرام
تعداد صفحه :77
نوع فایل PDF
چکیده
با گسترش شبکه های کامپیوتری و پیچیده شدن ارتباطات، مسئله مسیریابی اطلاعات برحسب تغییـرات توپولوژیکی و عموماً ترافیک لحظه ای حائز اهمیت است. وظیفه هر الگوریتم مسـیریابی هـدایت بسـته هـای اطلاعاتی از مبدأ به سمت مقصد با هدف بهینه کردن میانگین زمان تأخیر بسته هـا، بهـره بـرداری ازمنـابع و کارایی شبکه مانند توان عملیاتی می باشد. در سالهای اخیر مسئله مسیریابی وفقی در شـبکه هـای دیتـاگرام باساختارها و توپولوژی های متفاوت بسیار مورد توجه قرار گرفته است و الگوریتمهـای مختلفـی در ایـن زمینـه پیشنهاد شده است که از آن جمله می توان الگوریتم مسیریابی کلونی مورچـه را نـام بـرد . الگـوریتم کلـونی مورچه الهام گرفته شده از مطالعات ومشاهدات بر روی کلونی مورچه هاست. این الگوریتم بر پایه ایـن منطـق بنا نهاده شده که مورچه ها در مسیرخود برای یافتن غذا از خود ماده ای به نام فرومون بر جـای مـی گذارنـد که بستگی به طول مسیر و کیفیت غذای یافته شده دارد بر اثر استشمام بوی فرومون توسط دیگر مورچه هـا آنها نیز جذب مسیر شده و مقدار فرومون را در آن مسیر تقویت می کنند، مسیرهای کوتاهتر از لانـه تـا غـذا فرومون بیشتری گرفته وبدین ترتیب کوتاهترین مسیر توسط مورچه ها انتخاب می شود، از این رفتار توصیف شده مورچه ها برای بهینه سازی جداول مسیریاب ها استفاده شده و به این ترتیـب کوتـاهترین مسـیر بـرای هدایت بسته ها در نظر گرفته می شود.
در سمینار حاضر به بررسی الگوریتم ها ی پیشنهاد شده براساس ایده کلونی کورچه هـا بـرای مسـیریابی بسته های اطلاعاتی در شبکه دیتا گرام پرداخته می شود.
مقدمه
در طی سالهای اخیر، شبکه های ارتباطی بسیار مورد توجه بوده اند و این بدلیل رشد بی سابقه شـبکه اینترنت در دهه های اخیر است که در واقع آنرا تبدیل به زیربنای ارتباطات کـرده اسـت و مـی تـوان گفـت دلیل اصلی موفقیت اینترنت فن آوری راهگزینی بسته ای بدون اتصالش است. این خاصیت سادگی، انعطـاف پذیری، پایداری و درستی ساختار لایه شبکه را بهمراه دارد.این دقیقا ًبر خلاف شبکه های ارتباطی مبتنی بر اتصال است که نیاز دارند تابرای برقراری ارتباط یک اتصال(مداری)از پیش رزرو شده بین فرستنده و گیرنـده درنظر گرفته شود. موفقیت اینترنت محقق هـا را ترغیـب کـرد تـا رویـای محاسـبات جهـانی Ubiquitous Computingرا درک کنند. در واقع محاسبات جهانی جامعه ای از کاربران را ایجاد کرده است که توان خـود ، تجارت الکترونیکی 1 را در کاربردهایی مانند وب جهان گستر آمـوزش از راه دور و…. بکـار مـی برند. مشخصه مشترکی که تمام این کاربردها دارند توانایی ارسال صدا و تصویر به دیگـران تحـت الزامهـای 4 کیفیت خدمات QoS است. کاربران تمام این خدمات را همانگونه که در سایر وسایل سیار وجـود دارد بـر روی کامپیوترشان نیز می خواهند، و این نیازها برآورده نمی شود مگر اینکه منابع شبکه بطور مناسبی کـار برده شوند. بهره برداری مناسب از منابع محدود شبکه بوسیله بهینه کردن عملکرد شبکه های مبتنی بـر IP میسر می شود که آن نیز مستلزم ایجاد استراتژی های مسیریابی کارآمد و قابل اعتمـاد اسـت . یکـی از چـالش های موجود در این زمینه طراحی پروتکل های مسیر ابی است که بتوانند چندین مسـیر مناسـب بـین فرستنده و گیرنده را کشف کنند .در حال حاضـر الگوریتمهـای مسـیریابی پویـا و وفقـی گونـاگونی توسـط محققان سراسر جهان با الهام از طبیعت طراحی شده اند. از آن جمله می توان به الگوریتم های کلونی مورچه اشاره کرد.
5 ایده ی اصلی این مجموعه از الگوریتم ها، بر جا ماندن مـاده ی فر ومـون بـه عنـوان ردپـا در دنیـای مورچه های واقعی می باشند. مورچه ها از ماده ی فرومون به عنوان یـک وسـیله ی ارتبـاطی اسـتفاده مـی کنند. در واقع الگوریتم های بهینه یابی مورچگان بر مبنای ارتباط غیـر مسـتقیم مجموعـه ای از مورچگـان مصنوعی به وسیله ی فرومون مصنوعی بنا نهاده شده اند که در این میان ماده ی فرومون وظیفـه ی انتقـال تجربه ی مورجه ها به یکدیگر بدون ارتباط مستقیم مورجه ها با هم را به عهده دارد. الگوریتم های مورچه نمونه های موفقی از سیستم های هوش جمعی هستند و از TSP سنتی تا مسیریابی در شبکه های ارتباطی راه دور را دربرمی گیرند. الگوریتم های مورچه، سیستم های چندعامله ای هستند که هر عامل، یک مورچه مصنوعی است. در واقع دانشمندان با الهام گرفتن از مورچه ها عمل پیچیده مسیریابی را با عاملهای ساده ای که با پیمایش شبکه، اطلاعات مسیر یابی را جمع آوری می کنند، انجام می دهند. هر گره در شبکه براساس اطلاعات محدودی که از وضعیت شبکه دارد بسته های داده را به سمت مقصدشان هدایت می کند.الگوریتمهای مسیر یابی مبتنی بر عامل در مقابل تغییرات شبکه بهره برداری تطبیقی و کارآمد منابع شبکه را جهت ارضا کردن نیازهای توازن بار و مدیریت خطا در شبکه فراهم می کنند. در این سمینار ابتدا به بیان مسئله پرداخته شده سپس به مقدمه ای بر بهینه سازی کلونی مورچگان می پردازیم و بعد از آن مروری بر نحوه مسیر یابی در شبکه های کامپیوتری خواهیم داشت و در ادامه نیز به بررسی روش والگوریتم های بهینه سازی کلونی مورچگان در مسیریابی شبکه های دیتاگرام پرداخته می شود و در آخر نتیجه گیری آورده شده است.
تعداد صفحه :77
