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

چکیده

چکیده امروزه استفاده از شبکه های بی سیم به شکل گسترده ای رو به تزاید است.یکی از انواع این شبکه ها، شبکه های موبایل تک کاره (Mobile ad hoc networks)است. شبکه موبایل Ad hoc به عنوان شبکه های با عمر کوتاه شناخته می شود. توپولوژی بسیار پویا، در دسترس بودن پهنای باند محدود،محدودیت های انرژی و عدم وجود زیرساخت، مسیریابی در این نوع شبکه ها را به چالش کشیده است،بدین جهت یافتن مسیر بهینه در این شبکه ها یک مسئله بسیار مهم به شمار می اید. الگوریتم های الهام گرفته از طبیعت (ازدحام هوش) مانند الگوریتم های بهینه سازی لانه مورچه و همچنین الگوریتم ژنتیک در چند سال اخیر برای حل مسئله مسیریابی شبکه های اختصاصی موبایل معرفی شده اند. در این پروژه سعی کردیم مجموعه فعالیت های انجام شده برای یافتن مسیر بهینه در شبکه های موبایل با استفاده از خواص الگوریتم ژنتیک و الگوریتم لانه مورچه ای را مورد بررسی و ارزیابی قرار داده و روشی بهینه در این زمینه را بیابیم

تعداد صفحات 162 WORD

فهرست

فصل اول.. 1

مقدمه ای بر شبکه های بی سیم موبایل.. 1

1-1-مقدمه ای بر شبکه های بی سیم.. 2

1-2 تقسیم بندی شبکه های بی سیم بر اساس محدوده فرکانس.... 5

1-2-1- شبکه های مادون قرمز. 5

1-2-2-شبکه های لیزری.. 5

1-2-3- شبکه های Wi – Fi6

1-2-4-شبکه های WiMAX.. 6

الف)شبکه بی سیم دارای ساختار. 7

1-3-شبکه های بیسیم Ad Ho. 7

1-3-1-مزایای شبکه ی ad hoc. 9

1-3-2-خصوصیت های شبکه Ad hoc. 13

1-4-شبکه های موبایل Ad hoc یا Mobile ad hoc networks) MANET)15

شبکه های موبایل نسل یک شبکه هایAMPS. 15

شبکه های موبایل نسل 2 شبکه هایGSMو EDGE.. 15

نسل کنونی شبکه های مخابرات سیار سلولی.. 16

مقایسه فنی شبکه های تلفن همراه(نسل سوم و چهارم)16

1-4-1-ساختار شبکه های MANET. 16

1-4-2-خصوصیات MANET. 18

1-4-3-کاربردهای شبکه hoc Mobile ad. 19

1-4-4-معایب MANET. 21

فصل دوم مسیریابی در شبکه های موبایل.. 23

2-1-مقدمه ای بر مسیریابی.. 24

2-2-مسیریابی در شبکه های Ad hoc. 24

2_3_پروتکل های مسیریابی در شبکه های Mobile Ad hoc. 27

2-3-1-الگوریتم های فعال (Table driven Pro active)28

2-3-2-الگوریتم های واکنشگر (On demand Reactive)31

2-3-3-الگوریتم های ترکیبی (Hybrid)34

2-3-4-مسیریابی سلسله مراتبی.. 35

2-3-5-مسیریابی مسطح.. 36

نتیجه گیری.. 37

فصل سوم بررسی الگوریتم های مسیریابی.. 38

مقدمه. 39

3-1-دیدگاه های الگوریتم های مسیریابی.. 39

3-2-نحوه ی مسیریابی بصورت استاتیک... 41

3-3-انواع پروتکل ها42

3-3-1-پروتکل های Distance Vector43

3-3-2-پروتکل های IP Link State. 44

3-3-3-پروتکل OSPF. 44

3-4 الگوریتم های مسیریابی.. 46

3-4-1-مسیریابی مبتنی بر کیفیت سرویس( QOS)46

3-4-2-مسیریابی چند منظوره. 46

3-4-3-مسیریابی چند مسیری.. 48

3-4-4-مسیریابی هوشمند. 49

نتیجه گیری.. 52

فصل چهارم مسیریابی در شبکه های موبایل بر اساس الگوریتم لانه مورچه. 54

4-1-مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟. 56

4_2_الگوریتم پایه لانه مورچه ای.. 57

4-4-چرا الگوریتم تخمین بهینه لانه مورچه ای برای شبکه های ad-hoc مناسبند؟. 61

4-5-بررسی الگوریتم های مسیریابی مبتنی بر مورچه ها برای MANETs. 62

4-6-الگوریتم های مسیریابی تخت... 62

4-6-1- الگوریتم مسیریابی مبتنی بر لانه مورچه. 62

4-6-2-موریانه. 77

4-6-3-الگوریتم مسیریابی اورژانس احتمالاتی(PERA )78

4-6-4-الگوریتم مسیریابی فوری ویژه:(EARA )79

4-6-5-مورچه AODV.. 81

4-7-پروتکل های مسیریابی سلسله مراتبی.. 82

4-7-1-مسیریابی مبتنی بر مورچه متحرک (MABR )82

4-7-2- SDRاتخاذ شده. 83

4-7-3-HOPENT. 84

4-8-الگوریتم ردیابی مورچه برای شبکه های اختصاصی موبایل.. 86

4-8-1-فهرست یا جدول پیشنهادی مسیریابی.. 87

4-8-2-مورچه ها88

4-8-3- کشف مسیر. 89

4-8-4-حفظ مسیر. 92

4-9-1-مروری بر پروتکل TARC.. 92

4-9-2- پروتکل TRAC.. 94

4-9-3-شبیه‌سازی.. 98

فصل پنجم مسیریابی شبکه های موبایل بر اساس الگوریتم ژنتیک... 102

مقدمه. 103

5-1-الگوریتم ژنتیک... 104

5-2:مسیریابی QoS در MANET بر اساس الگوریتم ژنتیک... 109

5-2-1:QoS در MANET. 109

5-2-2-نقش GA در مسیریابی QoS در MANET. 113

5-2-3-شبیه‌سازی و نتایج.. 117

5-3-1-مشکلات مسیر حرکتی SP. 124

5-3-4-مطالعه تجربی.. 131

5-3-5-نتایج و بررسی های تجربی اساسی.. 133

فصل ششم ارزیابی و نتیجه گیری.. 143

نتیجه گیری.. 144

منابع.. 146

فهرست اشکال و جداول

شکل1-2:تجهیزات قابل حمل در شبکه های Ad hoc‌. 8

شکل1-3:نحوه ارتباط گره ها در یک حوزه ارتباطی شکل1-4:ارتباط گرهa3با خارج از حوزه ارتباطی.. 9

شکل 1-5:چگونگی ارتباط بین دو ایستگاه. 10

شکل 1-6:شناسایی گره ها توسط ایستگاه ها11

شکل 1-7:ارسال داده توسط یک ایستگاه به سمت مقصد. 12

1شکل1-8:ایجادمسیر جدید پس از حذف یک ایستگاه میانی.. 12

شکل 1-9:نمونه ای از یک ارتباط multi hop. 13

جدول 2-1:انواع پروتکل های مسیریابی درMANET. 28

شکل 2-1:مثالی از یک دسته بندی.. 36

شکل 4-7:فلوچارت یک fant67

شکل4-8 :تصویری از چگونگی ایجاد حلقه. 68

Fجدول 4-1:مدخل نود. 69

شکل4-9:فلوچارت یک Bant70

نمودار 4-1: مقایسه چهار پروتکل توسط کسری از بسته های تحویل داده موفق به عنوان یک تابعی از زمان مکث. شبیه سازی با 10 اتصال CBR.73

نمودار 4-2:نرخ تحویل ارا با فاصله اطمینان 0.05=α. 73

نمودار 4-3:مقایسه 4پروتکل به وسیله کسری از موفقیت ارسال بیت و بیت مورد نیاز. 74

نمودار 4-4:سربار ara.فاصله اطمینان با =0.05α.شبیه سازی با 10 اتصال CBRو فاصله اطمینان 10 شبیه سازی را اجرا می کند.75

نمودار 4-5:مقایسه 4 پروتکل توسط تعدادی ازبسته های مسیریابی مورد نیاز.شبیه سازی با 10 اتصال CBR 76

نمودار 4-6: سربار ARAدر بسته.با فاصله اطمینان با =0.05α.شبیه سازی با 10 اتصال CBRو فاصله اطمینان 10 شبیه سازی را اجرا می کند.77

تصویر 4-10:مثالی از ساختار مقیاس بندی (درجه بندی)شده. 88

شکل 4-11: مراحل پروتکل TARC: (الف) مرحله جستجوی مسیر (ب) مرحله به روز رسانی مقدار فرومون (ج) مرحله تحویل 94

نمودار 4-7: پروتکل TRACبا تعداد مورچه‌های مختلف 1،3،5. 99

شکل 5-1:نمایی از یک کروموزوم. 105

شکل 5-2:مثالی از یک MANET. 110

جدول 5-1:لیستی از گره های مجاور. 111

جدول 5-2:فرمت بیکن.. 112

شکل5-3:پشته پروتکل برای MN(گره های موبایل) و FN(گره های واسط) در MANET. 113

شکل5-4:طراحی مدل GAبر اساس مسیریابی QoS. 114

شکل5-5:مثالی از نقش ماژول GA.. 116

جدول 5-3:پارامترهای شبیه سازی.. 118

شکل5-7:شبیه سازی GAبر اساس مسیریابی QOSبرای 3 گره.119

شکل 5-8:شبه کدی برایEIGAوHIGAکه در ان نخبه گرایی از یک اندازه استفاده می کند.131