بررسی الگوریتم های مسیریابی در شبکه های حسگر بیسیم
امروزه استفاده از شبکه های بی سیم به شکل گسترده ای رو به ازدیاد است.یکی از انواع این شبکه ها، شبکه های موبایل تک کاره (Mobile بیسیم networks)است. شبکه موبایل بیسیم به عنوان شبکه های با عمر کوتاه شناخته می شود. توپولوژی بسیار پویا، در دسترس بودن پهنای باند محدود،محدودیت های انرژی و عدم وجود زیرساخت، مسیریابی در این نوع شبکه ها را به چالش کشیده است،بدین جهت یافتن مسیر بهینه در این شبکه ها یک مسئله بسیار مهم به شمار می اید. الگوریتم های الهام گرفته از طبیعت (ازدحام هوش) مانند الگوریتم های بهینه سازی لانه مورچه و همچنین الگوریتم ژنتیک در چند سال اخیر برای حل مسئله مسیریابی شبکه های بی سیم معرفی شده اند. در این پروژه سعی کردیم مجموعه فعالیت های انجام شده برای یافتن مسیر بهینه در شبکه های بی سیم با استفاده از خواص الگوریتم ژنتیک و الگوریتم لانه مورچه ای را مورد بررسی و ارزیابی قرار داده و روشی بهینه در این زمینه را بیابیم.
فهرست مطالب
فصل اول:کلیات
1-1 مقدمه ای بر شبکه های بی سیم. 2
1-2 تقسیم بندی شبکه های بی سیم بر اساس محدوده فرکانس... 5
1-2-1 شبکه های مادون قرمز. 5
1-2-2 شبکه های لیزری. 5
1-2-3 شبکه های Wi – Fi 5
1-2-4 شبکه های WiMAX.. 6
1-3 شبکه های بیسیم Ad Ho. 7
1-4 مسیریابی هوشمند. 8
فصل دوم:مسیریابی در شبکه های بیسیم
2-1- مقدمه ای بر مسیریابی. 14
2-2- مسیریابی در شبکه های بیسیم. 14
2-3- پروتکل های مسیریابی در شبکه های بیسیم. 17
2-3-1- الگوریتم های فعال (Table driven Pro active) 18
2-3-2- الگوریتم های واکنشگر (On demand Reactive) 20
2-3-3- الگوریتم های ترکیبی (Hybrid) 23
2-3-4- مسیریابی سلسله مراتبی. 24
2-3-5- مسیریابی مسطح. 25
نتیجه گیری. 26
فصل سوم:بررسی الگوریتم های مسیریابی
مقدمه 28
3-1- دیدگاه های الگوریتم های مسیریابی. 28
2-3- نحوه ی مسیریابی بصورت استاتیک... 29
3-3- انواع پروتکل ها 30
3-3-1- پروتکل های Distance Vector 31
3-3-2- پروتکل های IP Link State. 32
3-3-3- پروتکل OSPF. 33
3-4- الگوریتم های مسیریابی. 34
3-4-1- مسیریابی مبتنی بر کیفیت سرویس( QOS) 34
3-4-2- مسیریابی چند منظوره 34
نتیجه گیری. 35
فصل چهارم:ارزیابی الگوریتم مورچگان در شبکه های بی سیم
4-1 مقدمه 38
4-2 پیدا کردن کوتاهترین مسیر توسط مورچه ها 38
4-3 الگوریتم پایه لانه مورچه ای. 39
4-4 ویژگیهای الگوریتم مورچگان : 41
4-5 الگوریتم ساده لانه مورچه ای. 42
4-6 چرا الگوریتم تخمین بهینه لانه مورچه ای برای شبکه های بی سیم مناسبند؟ 43
4-6-1 توپولوژی پویا 43
4-6-2 کار محلی. 43
4-6-3 کیفیت اتصال. 43
4-6-4 پشتیبانی از چند مسیره بودن شبکه 43
4-7 بررسی الگوریتم های مسیریابی مبتنی بر مورچه ها برای MANETs. 43
4-8 الگوریتم های مسیریابی تخت.. 44
4-8-1 الگوریتم مسیریابی مبتنی بر لانه مورچه 44
4-8-2 خصوصیات ARA.. 46
4-9 چگونگی کارکرد الگوریتم. 47
4-9-1 موریانه 51
4-9-2 الگوریتم مسیریابی اورژانس احتمالاتی(PERA ) 52
4-9-3 الگوریتم مسیریابی فوری ویژه:(EARA ) 53
4-9-4 مورچه AODV.. 55
4-10 پروتکل های مسیریابی سلسله مراتبی. 55
4-10-1 مسیریابی مبتنی بر مورچه متحرک (MABR ) 55
4-10-2HOPENT. 58
4-10-3 الگوریتم ردیابی مورچه برای شبکه های اختصاصی بی سیم. 59
4-11 فهرست یا جدول پیشنهادی مسیریابی. 60
4-11-1 مورچه ها 61
4-11-2 کشف مسیر. 62
4-11-3 حفظ مسیر. 64
4-12 محدوده مسیریابی بر اساس پروتکل مسیریابی لانه مورچه ای (TRAC) برای شبکه های بی سیم. 65
4-12-1 مروری بر پروتکل. 65
4-12-2 مروری بر پروتکل TARC.. 65
4-12-3 پروتکل TRAC.. 66
4-12-3-1 مرحله برپایی. 67
4-12-3-2 مرحله جستجوی مسیر. 67
4-12-3-3 مرحله به روز رسانی مقدار فرومون. 68
4-12-3-4 مرحله تحویل. 69
فصل پنجم:ارزیابی عملکرد الگوریتم ژنتیک
5-1- مقدمه 73
5-2- پیشینه 74
5-3- اصطلاحات زیستی. 74
5-4- تشریح کلی الگوریتم ژنتیک... 75
5-5- حل مساله با استفاده از الگوریتم های ژنتیک... 75
5-6- اجزای الگوریتم ژنتیک... 76
5-6-1- جمعیت.. 77
5-6-2- کدگذاری. 78
5-7 مسیریابی QoS در MANET بر اساس الگوریتم ژنتیک... 78
5-7-1:QoS در MANET. 78
5-7-2 نقش GA در مسیریابی QoS در MANET. 81
5-8 مشکلات کوتاهترین مسیر حرکتی در MANET بر اساس الگوریتم ژنتیک... 85
5-8-1 مشکلات مسیر حرکتی SP. 85
5-8-2 الگوریتم ژنتیکی تخصصی برای مشکلات SP. 87
5-8-2-1 نمایش ژنتیکی. 87
5-8-2-2 ارزش دهی اغازی جمعیتی. 87
5-8-2-3 توانایی عملکرد 88
5-8-2-4 برنامه ریزی انتخابی. 88
5-8-2-5 همگذری و جهش... 88
5-8-3 الگوریتمهای ژنتیکی به همراه برنامه ریزی مهاجرتی. 89
5-9 نتیجه گیری. 91
فصل ششم:ارزیابی و نتیجه گیری
6-1 نتیجه گیری. 94
6-2 الگوریتم پیشنهادی: 95
منابع. 96
