چکیده
امروزه استفاده از شبکه های بی سیم به شکل گسترده ای رو به تزاید است.یکی از انواع این شبکه ها، شبکه های موبایل تک کاره (Mobile ad hoc networks)است. شبکه موبایل Ad hoc به عنوان شبکه های با عمر کوتاه شناخته می شود. توپولوژی بسیار پویا، در دسترس بودن پهنای باند محدود،محدودیت های انرژی و عدم وجود زیرساخت، مسیریابی در این نوع شبکه ها را به چالش کشیده است،بدین جهت یافتن مسیر بهینه در این شبکه ها یک مسئله بسیار مهم به شمار می اید. الگوریتم های الهام گرفته از طبیعت (ازدحام هوش) مانند الگوریتم های بهینه سازی لانه مورچه و همچنین الگوریتم ژنتیک در چند سال اخیر برای حل مسئله مسیریابی شبکه های اختصاصی موبایل معرفی شده اند. در این پروژه سعی کردیم مجموعه فعالیت های انجام شده برای یافتن مسیر بهینه در شبکه های موبایل با استفاده از خواص الگوریتم ژنتیک و الگوریتم لانه مورچه ای را مورد بررسی و ارزیابی قرار داده و روشی بهینه در این زمینه را بیابیم.
واژه های کلیدی:
شبکه های موبایل Ad hoc ،الگوریتم ژنتیک،الگوریتم لانه مورچه ای
مقدمه ای بر شبکه های بی سیم
یک شبکه ی بی سیم به مجموعه ای از کامپیوترها و تجهیزات متصل به یکدیگر امکان می دهد تا بدون انکه به صورت فیزیکی به شبکه ای متصل باشند با یکدیگر ارتباط برقرار کنند. در این شبکه برخلاف شبکه های سیمی کابل وجود ندارد.
یکی از مشکلاتی که در زمینه طراحی نصب و پیاده سازی انواع شبکه های کامپیتری وجود دارد مشکل کابل و کابل کشی است.اما استفاده از کابل های شبکه معایبی دارند که از مهمترین انها عبارتند از:[1]
- تغییر شکل ظاهری محیط: استفاده از کابل های شبکه باعث می شود تا شکل ظاهری محیط تغییر کند.
- برد موثر کابل:هر کابل شبکه برد موثر ویژه خود را دارد که اگر از ان بیشتر شود قادر به ارسال اطلاعات نیست.
- صدمات فیزیکی کابل:کابل شبکه نسبت به صدمات فیزیکی بسیار حساس است.
- هزینه های اضافی:استفاده از شبکه های کابلی موجب می شود تا هر کامبیوتر متصل به یک شبکه از یک کابل برای متصل شدن به ان استفاده کند.
شبکه های بیسیم به جای استفاده از کابل از امواج رادیویی استفاده می کنند و نسبت به شبکه های کابلی مزایا و ومعایبی دارند.مهمترین مزایای شبکه های بیسیم عبارتند از:
- نداشتن مشکلات شبکه های کابلی:در شبکه های بی سیم دیگر از مشکلات ذکر شده در شبکه های کابلی خبری نیست.
- مناسب برای دستگاههای سیار:یکی از مزیت های شبکه ی بی سیم،استفاده از ان برای دستگاههای هستند.
- قابلیت گسترش:افزودن یک کامپیوتر یا دستگاه جدید به شبکه های بی سیم بسیار اسان تر از شبکه های کابلی است.
مقدمه ای بر مسیریابی
از بررسی و قضاوت در مورد تحقیقاتی که هم اکنون صورت می پذیرد می توان به این نتیجه رسید که مسیریابی در اینترنت جزء اکثر مواردی است که رغبت بدان هم چنان تنزل نیافته است. مخصوصا مسیریابی مبتنی بر کیفیت سرویس (QOS) در سالهای اخیرگواه صحت این ادعاست.
در طول دهه اخیر، اینترنت از پروژه های تحقیقاتی ارتباطات که دنیای ما را برای همیشه دچار تحول ساخته اند، فراتر رفته است.پیام های فوری، تلفنی ip، فیلم و موسیقی های درخواستی، بانکداری؛ تنها بخشی از کاربرد های فراوانی هستند که زندگی ما را راحت تر کرده اند. اما تکنولوژی و فناوری که ما را قادر به استفاده از این امکانات می کند شبکه های کامپیوتری و نحوه ی ارتباط بین این شبکه ها می باشد.
اینترنت که بزرگترین ابزار برای ارائه خدمات فوق می باشد از چندین هزار شبکه کوچک تشکیل شده است که برای برقراری ارتباط و تبادل اطلاعات بین این شبکه ها به یک شبکه گسترده دیگر نیاز دارد که backbone نامیده می شود، و دارای device های مختلف از جمله router است، نحوه ی رد و بدل شدن پیام ها بین router ها اساس کار این backbone می باشد، ما به دلیل اهمیتی که این تکنیک ارسال و دریافت پیام از یک نتقطه به نقطه دیگر دارد روش های مختلف انجام این کار را بررسی می کنیم و در نهایت بهترین و مناسب ترین روش انجام کار را به صورت کامل معرفی خواهیم کرد.
اساس آغاز یک پروژه نظریه فکر یا خواسته ای است که توسط شخص یا اشخاص یا سازمانی مطرح می شود. هدف از انجام این پروژه تحلیل و چگونگی کار پروتکل های مسیر یابی و مقایسه آنها و بررسی پروتکل OSPF به طور کامل و ارائه تکنیک های هوش مصنوعی برای بهبود کارایی این پروتکل است..
یکی از زمینه هایی که مسیریابی در ان بسیار مهم و کلیدی است مسیریابی در شبکه های بی سیم سیارمی باشد،بدین منظور در این فصل به بررسی پروتکلهای مسیریابی در شبکه های موبایل می- پردازیم.
فهرست مطالب
عنوان شماره صفحه
فصل اول
مقدمه ای بر شبکه های بی سیم موبایل
1-1-مقدمه ای بر شبکه های بی سیم.. 2
1-2-تقسیم بندی شبکه های بی سیم بر اساس محدوده فرکانس.... 4
1-2-1- شبکه های مادون قرمز. 4
1-2-2-شبکه های لیزری.. 5
1-2-3- شبکه های Wi – Fi 5
1-2-4-شبکه های WiMAX.. 5
1-3-شبکه های بیسیم Ad Ho. 6
1-3-1-مزایای شبکه ی ad hoc. 8
1-3-2-خصوصیت های شبکه Ad hoc. 11
1-4-شبکه های موبایل Ad hoc یا MANET. 12
1-4-1-ساختار شبکه های MANET. 14
1-4-2-خصوصیات MANET. 15
1-4-3-کاربردهای شبکه hoc Mobile ad. 16
1-4-4-معایب MANET. 17
1-5- نتیجه گیری.. 18
فصل دوم
مسیریابی در شبکه های موبایل
2-1-مقدمه ای بر مسیریابی.. 20
2-2-مسیریابی در شبکه های Ad hoc. 20
2-3-پروتکل های مسیریابی در شبکه های Mobile Ad hoc. 22
2-3-1-الگوریتم های فعال 23
2-3-2-الگوریتم های واکنشگر 25
2-3-3-الگوریتم های ترکیبی 27
2-3-4-مسیریابی سلسله مراتبی.. 28
2-4- نتیجه گیری.. 29
فصل سوم
بررسی الگوریتم های مسیریابی
مقدمه. 31
3-1-دیدگاه های الگوریتم های مسیریابی.. 31
3-2-نحوه ی مسیریابی بصورت استاتیک... 32
3-3-انواع پروتکل ها 33
3-3-1-پروتکل های Distance Vector 34
3-3-2-پروتکل های IP Link State. 35
3-3-3-پروتکل OSPF. 35
3-4-الگوریتم های مسیریابی.. 36
3-4-1-مسیریابی مبتنی بر کیفیت سرویس( QOS) 36
3-4-2-مسیریابی چند منظوره. 37
3-4-4-مسیریابی هوشمند. 39
3-5- نتیجه گیری.. 42
فصل چهارم
مسیریابی در شبکه های موبایل بر اساس الگوریتم لانه مورچه
مقدمه. 44
4-2-الگوریتم پایه لانه مورچه ای.. 47
4-3- الگوریتم ساده لانه مورچه ای.. 49
4-4-چرا الگوریتم تخمین بهینه لانه مورچه ای برای شبکه های ad-hoc مناسب هستند؟. 50
4-5-بررسی الگوریتم های مسیریابی مبتنی بر مورچه ها برای MANETs. 51
4-6-الگوریتم های مسیریابی تخت... 51
4-6-1- الگوریتم مسیریابی مبتنی بر لانه مورچه. 52
4-6-2- موریانه. 64
4-6-3-الگوریتم مسیریابی اورژانس احتمالاتی(PERA ) 65
4-6-4-الگوریتم مسیریابی فوری ویژه(EARA ) 66
4-6-5-مورچه AODV.. 67
4-7-پروتکل های مسیریابی سلسله مراتبی.. 67
4-7-1-مسیریابی مبتنی بر مورچه متحرک (MABR ) 68
4-7-2- SDRاتخاذ شده. 69
4-7-3-HOPENT. 69
4-8-الگوریتم ردیابی مورچه برای شبکه های اختصاصی موبایل.. 71
4-8-1-فهرست یا جدول پیشنهادی مسیریابی.. 72
4-8-2-مورچه ها 73
4-8-3- کشف مسیر. 73
4-8-4-حفظ مسیر. 75
4-9-محدوده مسیریابی بر اساس پروتکل مسیریابی لانه مورچه ای (TRAC) برای شبکه های موبایل. 76
4-9-1-مروری بر پروتکل TARC.. 76
4-9-2- پروتکل TRAC.. 77
4-9-3-شبیه‌سازی.. 80
4-10- نتیجه گیری.. 81
فصل پنجم
مسیریابی شبکه های موبایل بر اساس الگوریتم ژنتیک
مقدمه. 84
5-1-الگوریتم ژنتیک... 85
چگونگی کارکرد ان.. 87
5-2:مسیریابی QoS در MANET بر اساس الگوریتم ژنتیک... 89
5-2-1 QoS در MANET. 89
5-2-2-نقش GA در مسیریابی QoS در MANET. 91
5-2-3-شبیه‌سازی و نتایج.. 94
5-3:مشکلات کوتاهترین مسیر حرکتی در MANET بر اساس الگوریتم ژنتیک... 99
5-3-1-مشکلات مسیر حرکتی SP. 99
5-3-2-الگوریتم ژنتیکی تخصصی برای مشکلات SP. 100
5-3-3-الگوریتمهای ژنتیکی به همراه برنامه ریزی مهاجرتی.. 103
5-3-4-مطالعه تجربی.. 105
5-3-5-نتایج و بررسی های تجربی اساسی.. 106
5-4- نتیجه گیری.. 114
فصل ششم
ارزیابی و نتیجه گیری
پیوست ها 118
منابع.. 121
Abstract 116
پروژه ارزیابی الگوریتم های هوشمند در مسیریابی شبکه های موبایل
