مقدمه

در طی سالهای اخیر، شبکه های ارتباطی بسیار مورد توجه بوده اند و این بدلیل رشد بی سابقه شـبکه اینترنت در دهه های اخیر است که در واقع آنرا تبدیل به زیربنای ارتباطات کـرده اسـت و مـی تـوان گفـت دلیل اصلی موفقیت اینترنت فن آوری راهگزینی بسته ای بدون اتصالش است. این خاصیت سادگی، انعطـا فپذیری، پایداری و درستی ساختار لایه شبکه را بهمراه دارد.این دقیقا ًبر خلاف شبکه های ارتباطی مبتنی بر اتصال است که نیاز دارند تابرای برقراری ارتباط یک اتصال(مداری)از پیش رزرو شده بین فرستنده و گیرنـده درنظر گرفته شود. موفقیت اینترنت محقق هـا را ترغیـب کـرد تـا رویـای محاسـبات جهـانی UbiquitousComputingرا درک کنند. در واقع محاسبات جهانی جامعه ای از کاربران را ایجاد کرده است که توان خـود را در کاربردهایی مانند وب جهان گستر(WWW) ، تجارت الکترونیکی ، آمـوزش از راه دو ر و…. بکـار مـی برند. مشخصه مشترکی که تمام این کاربردها دارند توانایی ارسال صدا و تصویر به دیگـران تحـت الزامهـای کیفیت خدمات QoS) ) است. کاربران تمام این خدمات را همانگونه که در سایر وسایل سیار وجـود دارد بـر روی کامپیوترشان نیز می خواهند، و این نیازها برآورده نمی شود مگر اینکه منابع شبکه بطور مناسبی بکـار برده شوند. بهره برداری مناسب از منابع محدود شبکه بوسیله بهینه کردن عملکرد شبکه های مبتنی بـر IPمیسر می شود که آن نیز مستلزم ایجاد استراتژی های مسیریابی کارآمد و قابل اعتمـاد اسـت . یکـی از چـا لش های موجود در این زمینه طراحی پروتکل های مسیر یابی است که بتوانند چندین مسـیر مناسـب بـین فرستنده و گیرنده را کشف کنند .در حال حاضـر الگوریتمهـای مسـیریابی پویـا و وفقـی گونـاگونی توسـط محققان سراسر جهان با الهام از طبیعت طراحی شده اند. از آنجمله می توان به الگوریتم های کلونی مورچه اشاره کرد.
ایده ی اصلی این مجموعه از الگوریتم ها، بر جا ماندن مـاده ی ف رومـون بـه عنـوان ردپـا در دنیـای مورچه های واقعی می باشند. مورچه ها از ماده ی فرومون به عنوان یـک وسـیله ی ارتبـاطی اسـتفاده مـی کنند. در واقع الگوریتم های بهینه یابی مورچگان بر مبنای ارتباط غیـر مسـتقیم مجموعـه ای از مورچگـان مصنوعی به وسیله ی فرومون مصنوعی بنا نهاده شده اند که در این میان ماده ی فرومون وظیفـه ی انتقـال تجربه ی مورجه ها به یکدیگر بدون ارتباط مستقیم مورجه ها با هم را به عهده دارد.
الگوریتم های مورچه نمونه های موفقی از سیستم های هوش جمعی هستند و از TSP سنتی تا مسیریابی در شبکه های ارتباطی راه دور را دربرمی گیرند. الگوریتم های مورچه، سیستم های چندعامله ای هستند که هر عامل، یک مورچه مصنوعی است. در واقع دانشمندان با الهام گرفتن از مورچه ها عمل پیچیده مسیریابی را با عاملهای ساده ای که با پیمایش شبکه، اطلاعات مسیر یابی را جمع آوری می کنند ،انجام می دهند. هر گره در شبکه براساس اطلاعات محدودی که از وضعیت شبکه دارد بسته های داده را به سمت مقصدشان هدایت می کند.الگوریتمهای مسیر یابی مبتنی بر عامل در مقابل تغییرات شبکه بهره برداری تطبیقی و کارآمد منابع شبکه را جهت ارضا کردن نیازهای توازن بار و مدیریت خطا در شبکه فراهم می کنند.
در این سمینار ابتدا به بیان مسئله پرداخته شده سپس به مقدمه ای بر بهینه سازی کلونی مورچگان می پردازیم و بعد از آن مروری بر نحوه مسیر یابی در شبکه های کامپیوتری خواهیم داشت و در ادامه نیز به بررسی روش والگوریتم های بهینه سازی کلونی مورچگان در مسیریابی شبکه های دیتاگرام پرداخته می شود و در آخر نتیجه گیری آورده شده است.

مروری بر مسیر یابی در شبکه دیتا گرام و کاربرد ACOدر مسیر یابی وبهینه سازی آن با الگوریتم کلونی مورچه گان

مروری بر مسیر یابی در شبکه دیتا گرام و کاربرد ACOدر مسیر یابی وبهینه سازی آن با الگوریتم کلونی مورچه گان

فهرست مطالب

چکیده……………………………………………………………………………………………………………………………..1

مقدمه……………………………………………………………………………………………………………………………..2

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

فصل اول: کلیات

-١)هدف
مسئله مسیر یابی در شبکه یک مسئله مهم و مشکل است ، مهم از این جهت که تـأثیر بسـزایی بـر کـارایی شبکه دارد و مشکل به این خاطر که ممکن است خصوصیات شبکه مانند بار ترافیکـی و هـم بنـدی شـبکه هـر لحظه تغییر کند.این ویژگیهای شبکه بعلاوه توزیع شدگی فیزیکی مسئله در یک شبکه واقعی است که الگوریتم های ACO را یک روش مناسب برای حل مسأله مسیر یابی می سازد . مسأله پیدا کردن مسیرهایی با کمترین هزینه در شبکه ها بخصوص وفتی که ترافیک شبکه یا هم بندی آن هـر لحظـه در حـال تغییـر اسـت از جملـه مسائلی است که بسیار مورد توجه محققان بوده است. توانایی مورچه ها در یافتن کوتاهترین مسیر باعث ایجـاد انعطاف در حل هرگونه مسئله بهینه سازی می شوند. مثلا در گراف شهرهای مسـئله فروشـنده دوره گـرد، اگـر یکی از یالها (یا گره ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجـه بـه شـرایط جدید پیدا کند. استفاده از بهینه سازی کلونی مورچه(ACO) به این منظور دارای برتری نسـبت بـه سـایر روش هاست که با طبیعت دینامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پر ترافیک شـود یـا حتی مسیر یابی از کار بیفتد و بدلیل انعطاف پذیری که ACO در برابر این تغییـرات دارد همـواره بهتـرین راه حل بعدی را در دسترس قرار می دهد.
١-٢)پیشینه تحقیق
بهینه سازی ترکیبی شاخه ای از بهینه سازی در ریاضیات کاربردی و علوم کـامپیوتر اسـت کـه بـین هـوش مصنوعی، ریاضی و مهندسی نرم افزار، مشترک است. مجموعه الگوریتم های بهینـه یـابی مورچگـان (ACO)جزو جدیدترین رویکرد های ابتکاری جهت حل مسائل بهینه یابی ترکیبی می باشند
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچـه هاسـت .ایـن مطالعـات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زنـدگی مـی کننـد و رفتـار آنهـا بیشـتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه هـا، رفتـار آنهـا برای یافتن غذا و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه است. ایـن نـوع رفتـار مورچه ها دارای نوعی هوشمندی جمعی است که اخیرا مورد توجه دانشمندان قرار گرفته است. الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یـ ک راه حـل چنـد عاملـه بـرای مسـائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائـه شـد.در سـالهای اخیـر در زمینه بکار گیری بهینه سازی کلونی مورچه در مسیر یابی در شبکه های ارتباطی تحقیقات گسترده ای صـورت گرفته و حاصل آن طراحی الگوریتمهایی است که از نظر کارایی در مقابسه با الگوریتم های مسـیر یـابی سـنتی بهتر عمل می کنند.

1-1)هدف……………………………………………………………………………………………………………………………5
1-2)پیشینه تحقیق………………………………………………………………………………………………………………..5

فصل دوم: بهینه سازی در کلونی مورچه

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

2-1) مقدمه…………………………………………………………………………………………………………………………7
2-2)هوش جمعی…………………………………………………………………………………………………………………9
2-2- 1) مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟………………………………………………………..10
2-3)روشفراابتکاری ACO………………….ا…………………………………………………………………………………….13
2-3-1)رفتارمورچه ها………………………………………………………………………………………………………………14
2-4-ساختارالگوریتم ACO…ا……………………………………………………………………………………………………..15
2-5)کاربردهای ACO……ا………………………………………………………………………………………………………..17

فصل سوم : مروری بر مسیر یابی در شبکه دیتا گرام

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

1 مسیریابی در زیر شبکه دیتاگرام

1 مسیریابی در زیر شبکه دیتاگرام

1)مقدمه……………………………………………………………………………………………………………………….19
3-2)سرویسهایاتصالگراوبدون اتصال…………………………………………………………………………………………….20
3-3)زیرشبکهدیتا گرام…………………………………………………………………………………………………………….20
3-4)زیرشبکهمدار مجازی…………………………………………………………………………………………………………22
3-5)مقایسهزیرشبکهدیتاگرامومدار مجازی……………………………………………………………………………………..24
3-6)الگوریتمهایمسیر یابی……………………………………………………………………………………………………….24
3-6-2)الگوریتم دایکسترا(Dijkstra) …………………………………………………………………………………………….٢٧
3-6-3)الگوریتمهای DV…………………………………………………………………………………………………………..٣٠
3-6-4)مسیریابی سلسله مراتبی ……………………………………………………………………………………………٣٣

فصل چهارم : کاربرد ACOدر مسیر یابی

امروزه از ACO در بسیاری از کاربردها استفاده می شودکه از آن جمله می توان به مسئله مسیریابی در شبکه اشاره کرد. خصوصیات شبکه مانند بار ترافیکی و هم بندی شبکه هر لحظه ممکن است تغییر کند، این ویژگیهای شبکه بعلاوه توزیع شدگی فیزیکی مسئله در یک شبکه واقعی است که الگوریتم های ACO را یک روش مناسب برای حل مسأله مسیر یابی می سازد . مسأله پیدا کردن مسیرهایی با کمترین هزینه در شبکه ها بخصوص وقتی که ترافیک شبکه یا هم بندی آن هر لحظه در حال تغییر است از جمله مسائلی است که بسیار مورد توجه محققان در زمینه ACO قرار دارد.
روشی بنامAnt Colony Routering)ACR )پیشنهاد شده که بر اساس ایده کلونی مورچه به بهینه سازی جداول می پردازد و در واقع به هر مسیری با توجه به بهینگی آن امتیاز می دهد. استفاده از ACR به این منظور دارای برتری نسبت به سایر روش هاست که با طبیعت دینامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پر ترافیک شود یا حتی مسیر یابی از کار افتاده باشد و بدلیل انعطاف پذیری کهACOدر برابر این تغییرات دارد همواره بهترین راه حل بعدی را در دسترس قرار می دهد.
الگوریتمهای زیادی دراین زمینه در شبکه ای راهگزینی بسته ای و مداری ارائه شده که در این بخش بعد از بررسی مسئله مسیر یابی در ACO به بیان روشهای ارائه شده در شبکه های راهگزینی بسته ای پرداخته می

1)مقدمه………………………………………………………………………………………………………………………35
4-2)ساختارمورچهبرایمدلکردن مسئله مسیر یابی………………………………………………………………………….36
4-3)روشACOدرمقابلروشهایمسیریابی سنتی……………………………………………………………………………..38
4-4)دیدگاههایمختلفجهتکاهشدادن رکود…………………………………………………………………………………….42
4-4-1)کنترل فرومون…………………………………………………………………………………………………………….44
4-4-2)کنترلهوشمند فرومون…………………………………………………………………………………………………..44
4-4-3)ترشحفروموندارای امتیاز………………………………………………………………………………………………45
4-4-4)بررسیومقایسهروشهایمقابلهبا رکود………………………………………………………………………………..46
4-5)الگوریتمهایمسیر یابی……………………………………………………………………………………………………25
4-5)الگوریتمهایمسیریابی ACOا……………………………………………………………………………………………..48
4-5-1)الگوریتم AntNet……ا………………………………………………………………………………………………….48
4-5- 4)الگوریتم کنترل مبتنی برمورچه (Ant-Based Control…ا…………………………………………………………58
4-5- 5)الگوریتم بهینه سازی کلونی مورچه چند گانه (MACO……ا…………………………………………………….59

فصل پنجم : نتیجه گیری و پیشنهادات

5-1)نتیجه گیری………………………………………………………………………………………………………………..64
5-2)پیشنهادات…………………………………………………………………………………………………………………64

منابعوماخذ………………………………………………………………………………………………………………………65

چکیده انگلیسی………………………………………………………………………………………………………………..68

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

فهرست اشکال

شکل2-1:رفتارواقعیمورچهها……………………………………………………………………………………………………..12

شکل2-2:شبهکدمربوطبهالگوریتمACO…ا……………………………………………………………………………………….17

شکل3-1مسیریابیدرزیرشبکهدیتاگرام……………………………………………………………………………………………21

شکل3-2مسیریابیدرمدارمجازی…………………………………………………………………………………………………..24

شکل3-3)چارالگوریتمدایکسترا…………………………………………………………………………………………………….29

شکل3-4:مثالیازالگوریتمDijestra..ا……………………………………………………………………………………………….30

شکل3-5:جدولمسیریابیمربوطبهروترG…ا………………………………………………………………………………………….31

شکل3-6جدولمسیریابینمونهبرای بررسی مشکل الگوریتمهایDV…ا…………………………………………………………..32

شکل3-7:مقایسه جدول مسیر یابی الگوریتم DVبا سلسله مراتبی در شبکه بزرگ………………………………………….33

شکل4-1:شماکلیازکاربرد ACOدر مسیریابی در شبکه…………………………………………………………………………….36

شکل4-2:نحوهمسیریابیدرشبکهتوسطمورچههایمصنوعی………………………………………………………………………..38

شکل4-3:شبکهساده…………………………………………………………………………………………………………………39
شکل4-4:مثالیازمکانیزمتبخیر…………………………………………………………………………………………………………43

شکل4-5:مثالیازمکانیزمپیری…………………………………………………………………………………………………………43

شکل4-6:مثالیازرهیافتفرومونامتیازدار………………………………………………………………………………………………..46

شکل4-7:ساختارمورچهمصنوعی……………………………………………………………………………………………………50

شکل4-8:کدالگوریتمAntNet….ا……………………………………………………………………………………………………..53

شکل4-9مثالیازAntNet……ا…………………………………………………………………………………………………………..54

شکل4-10:نتایجشبیهسازیدرNSFnet………ا………………………………………………………………………………………..55

شکل4-11:نتایجشبیهسازیدرشبکهNTT…………ا…………………………………………………………………………………..55

شکل4-12:مقایسهAntN -COبا الگوریتمهای مسیر یابی دیگر……………………………………………………………………..57

فهرست جداول

جدول ٣-١: مقایسھ زیر شبکھ دیتا گرام و مد ار مجازی……………………………………………………………………………..۵٢

جدول۴- ١: مقایسھ الگوریتمھای مسیر یابی سنتی با روش ACO………………………………………………………………..١۴

 

Abstract
Although an ant is a simple creature, collectively a colony of ants performs useful tasks such as finding the shortest path to a food source and sharing this information with other ants by depositing pheromone. In the field of ant colony optimization (ACO), models of collective intelligence of ants are transformed into useful optimization techniques that find applications in computer networking. In a distributed problem solving paradigm, a society of ants (each contributing some information) collaborate to solve a larger problem. In recent years, Ant-based algorithms were used to solve classical routing problems such as: Traveling Salesman Problem, Vehicle Routing Problem, Quadratic Assignment Problem, connection-oriented /connectionless routing, sequential ordering, graph coloring and shortest common supersequence.
This report introduces the general idea of Ant-based algorithms with a focus on Ant Colony Optimization (ACO), and their features, strengths, weaknesses and applications in network routing. In this work we focus on the problem of routing in datagram-like networks with irregular topology, the most remarkable example of such networks being the Internet,and the problem-solving paradigm of ACO is explicated and compared to traditional routing algorithms along the issues of routing information, routing overhead and adaptivity. Also this report provides a comparison and critique of the state-of-the-art approaches for mitigating stagnation (a major problem in many ACO algorithms),and compares major research in applying ACO in routing and load-balancing,at last open problems will be discussed.


 


مقطع : کارشناسی ارشد

قیمت 25 هزار تومان

خرید فایل pdf به همراه فایلword

قیمت:35هزار تومان