مقدمه

در طی سالهاي اخیر، شبکه هاي ارتباطی بسیار مورد توجه بوده اند و این بدلیل رشد بی سابقه شـبکه اینترنت در دهه هاي اخیر است که در واقع آنرا تبدیل به زیربناي ارتباطات کـرده اسـت و مـی تـوان گفـت دلیل اصلی موفقیت اینترنت فن آوري راهگزینی بسته اي بدون اتصالش است. این خاصیت سادگی، انعطـا فپذیري، پایداري و درستی ساختار لایه شبکه را بهمراه دارد.این دقیقا ًبر خلاف شبکه هاي ارتباطی مبتنی بر اتصال است که نیاز دارند تابراي برقراري ارتباط یک اتصال(مداري)از پیش رزرو شده بین فرستنده و گیرنـده درنظر گرفته شود. موفقیت اینترنت محقق هـا را ترغیـب کـرد تـا رویـاي محاسـبات جهـانی 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هزار تومان