چکیدهچکیده امروزه استفاده از شبکه های بی سیم به شکل گسترده ای رو به تزاید است.یکی از انواع این شبکه ها، شبکه های موبایل تک کاره (Mobile ad hoc networks)است. شبکه موبایل Ad hoc به عنوان شبکه های با عمر کوتاه شناخته می شود. توپولوژی بسیار پویا، در دسترس بودن پهنای باند محدود،محدودیت های انرژی و عدم وجود زیرساخت، مسیریابی در این نوع شبکه ها را به چالش کشیده است،بدین جهت یافتن مسیر بهینه در این شبکه ها یک مسئله بسیار مهم به شمار می اید. الگوریتم های الهام گرفته از طبیعت (ازدحام هوش) مانند الگوریتم های بهینه سازی لانه مورچه و همچنین الگوریتم ژنتیک در چند سال اخیر برای حل مسئله مسیریابی شبکه های اختصاصی موبایل معرفی شده اند. در این پروژه سعی کردیم مجموعه فعالیت های انجام شده برای یافتن مسیر بهینه در شبکه های موبایل با استفاده از خواص الگوریتم ژنتیک و الگوریتم لانه مورچه ای را مورد بررسی و ارزیابی قرار داده و روشی بهینه در این زمینه را بیابیم تعداد صفحات 162 WORD فهرست فصل اول.. 1مقدمه ای بر شبکه های بی سیم موبایل.. 11-1-مقدمه ای بر شبکه های بی سیم.. 21-2 تقسیم بندی شبکه های بی سیم بر اساس محدوده فرکانس.... 51-2-1- شبکه های مادون قرمز. 51-2-2-شبکه های لیزری.. 51-2-3- شبکه های Wi – Fi61-2-4-شبکه های WiMAX.. 6الف)شبکه بی سیم دارای ساختار. 71-3-شبکه های بیسیم Ad Ho. 71-3-1-مزایای شبکه ی ad hoc. 91-3-2-خصوصیت های شبکه Ad hoc. 131-4-شبکه های موبایل Ad hoc یا Mobile ad hoc networks) MANET)15شبکه های موبایل نسل یک شبکه هایAMPS. 15شبکه های موبایل نسل 2 شبکه هایGSMو EDGE.. 15نسل کنونی شبکه های مخابرات سیار سلولی.. 16مقایسه فنی شبکه های تلفن همراه(نسل سوم و چهارم)161-4-1-ساختار شبکه های MANET. 161-4-2-خصوصیات MANET. 181-4-3-کاربردهای شبکه hoc Mobile ad. 191-4-4-معایب MANET. 21فصل دوم مسیریابی در شبکه های موبایل.. 232-1-مقدمه ای بر مسیریابی.. 242-2-مسیریابی در شبکه های Ad hoc. 242_3_پروتکل های مسیریابی در شبکه های Mobile Ad hoc. 272-3-1-الگوریتم های فعال (Table driven Pro active)282-3-2-الگوریتم های واکنشگر (On demand Reactive)312-3-3-الگوریتم های ترکیبی (Hybrid)342-3-4-مسیریابی سلسله مراتبی.. 352-3-5-مسیریابی مسطح.. 36نتیجه گیری.. 37فصل سوم بررسی الگوریتم های مسیریابی.. 38مقدمه. 393-1-دیدگاه های الگوریتم های مسیریابی.. 393-2-نحوه ی مسیریابی بصورت استاتیک... 413-3-انواع پروتکل ها423-3-1-پروتکل های Distance Vector433-3-2-پروتکل های IP Link State. 443-3-3-پروتکل OSPF. 443-4 الگوریتم های مسیریابی.. 463-4-1-مسیریابی مبتنی بر کیفیت سرویس( QOS)463-4-2-مسیریابی چند منظوره. 463-4-3-مسیریابی چند مسیری.. 483-4-4-مسیریابی هوشمند. 49نتیجه گیری.. 52فصل چهارم مسیریابی در شبکه های موبایل بر اساس الگوریتم لانه مورچه. 544-1-مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟. 564_2_الگوریتم پایه لانه مورچه ای.. 574-4-چرا الگوریتم تخمین بهینه لانه مورچه ای برای شبکه های ad-hoc مناسبند؟. 614-5-بررسی الگوریتم های مسیریابی مبتنی بر مورچه ها برای MANETs. 624-6-الگوریتم های مسیریابی تخت... 624-6-1- الگوریتم مسیریابی مبتنی بر لانه مورچه. 624-6-2-موریانه. 774-6-3-الگوریتم مسیریابی اورژانس احتمالاتی(PERA )784-6-4-الگوریتم مسیریابی فوری ویژه:(EARA )794-6-5-مورچه AODV.. 814-7-پروتکل های مسیریابی سلسله مراتبی.. 824-7-1-مسیریابی مبتنی بر مورچه متحرک (MABR )824-7-2- SDRاتخاذ شده. 834-7-3-HOPENT. 844-8-الگوریتم ردیابی مورچه برای شبکه های اختصاصی موبایل.. 864-8-1-فهرست یا جدول پیشنهادی مسیریابی.. 874-8-2-مورچه ها884-8-3- کشف مسیر. 894-8-4-حفظ مسیر. 924-9-1-مروری بر پروتکل TARC.. 924-9-2- پروتکل TRAC.. 944-9-3-شبیهسازی.. 98فصل پنجم مسیریابی شبکه های موبایل بر اساس الگوریتم ژنتیک... 102مقدمه. 1035-1-الگوریتم ژنتیک... 1045-2:مسیریابی QoS در MANET بر اساس الگوریتم ژنتیک... 1095-2-1:QoS در MANET. 1095-2-2-نقش GA در مسیریابی QoS در MANET. 1135-2-3-شبیهسازی و نتایج.. 1175-3-1-مشکلات مسیر حرکتی SP. 1245-3-4-مطالعه تجربی.. 1315-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:ارسال داده توسط یک ایستگاه به سمت مقصد. 121شکل1-8:ایجادمسیر جدید پس از حذف یک ایستگاه میانی.. 12شکل 1-9:نمونه ای از یک ارتباط multi hop. 13جدول 2-1:انواع پروتکل های مسیریابی درMANET. 28شکل 2-1:مثالی از یک دسته بندی.. 36شکل 4-7:فلوچارت یک fant67شکل4-8 :تصویری از چگونگی ایجاد حلقه. 68Fجدول 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
پایان نامه ارزیابی الگوریتم های هوشمند در مسیریابی شبکه های موبایل
چکیدهچکیده امروزه استفاده از شبکه های بی سیم به شکل گسترده ای رو به تزاید است.یکی از انواع این شبکه ها، شبکه های موبایل تک کاره (Mobile ad hoc networks)است. شبکه موبایل Ad hoc به عنوان شبکه های با عمر کوتاه شناخته می شود. توپولوژی بسیار پویا، در دسترس بودن پهنای باند محدود،محدودیت های انرژی و عدم وجود زیرساخت، مسیریابی در این نوع شبکه ها را به چالش کشیده است،بدین جهت یافتن مسیر بهینه در این شبکه ها یک مسئله بسیار مهم به شمار می اید. الگوریتم های الهام گرفته از طبیعت (ازدحام هوش) مانند الگوریتم های بهینه سازی لانه مورچه و همچنین الگوریتم ژنتیک در چند سال اخیر برای حل مسئله مسیریابی شبکه های اختصاصی موبایل معرفی شده اند. در این پروژه سعی کردیم مجموعه فعالیت های انجام شده برای یافتن مسیر بهینه در شبکه های موبایل با استفاده از خواص الگوریتم ژنتیک و الگوریتم لانه مورچه ای را مورد بررسی و ارزیابی قرار داده و روشی بهینه در این زمینه را بیابیم تعداد صفحات 162 WORD فهرست فصل اول.. 1مقدمه ای بر شبکه های بی سیم موبایل.. 11-1-مقدمه ای بر شبکه های بی سیم.. 21-2 تقسیم بندی شبکه های بی سیم بر اساس محدوده فرکانس.... 51-2-1- شبکه های مادون قرمز. 51-2-2-شبکه های لیزری.. 51-2-3- شبکه های Wi – Fi61-2-4-شبکه های WiMAX.. 6الف)شبکه بی سیم دارای ساختار. 71-3-شبکه های بیسیم Ad Ho. 71-3-1-مزایای شبکه ی ad hoc. 91-3-2-خصوصیت های شبکه Ad hoc. 131-4-شبکه های موبایل Ad hoc یا Mobile ad hoc networks) MANET)15شبکه های موبایل نسل یک شبکه هایAMPS. 15شبکه های موبایل نسل 2 شبکه هایGSMو EDGE.. 15نسل کنونی شبکه های مخابرات سیار سلولی.. 16مقایسه فنی شبکه های تلفن همراه(نسل سوم و چهارم)161-4-1-ساختار شبکه های MANET. 161-4-2-خصوصیات MANET. 181-4-3-کاربردهای شبکه hoc Mobile ad. 191-4-4-معایب MANET. 21فصل دوم مسیریابی در شبکه های موبایل.. 232-1-مقدمه ای بر مسیریابی.. 242-2-مسیریابی در شبکه های Ad hoc. 242_3_پروتکل های مسیریابی در شبکه های Mobile Ad hoc. 272-3-1-الگوریتم های فعال (Table driven Pro active)282-3-2-الگوریتم های واکنشگر (On demand Reactive)312-3-3-الگوریتم های ترکیبی (Hybrid)342-3-4-مسیریابی سلسله مراتبی.. 352-3-5-مسیریابی مسطح.. 36نتیجه گیری.. 37فصل سوم بررسی الگوریتم های مسیریابی.. 38مقدمه. 393-1-دیدگاه های الگوریتم های مسیریابی.. 393-2-نحوه ی مسیریابی بصورت استاتیک... 413-3-انواع پروتکل ها423-3-1-پروتکل های Distance Vector433-3-2-پروتکل های IP Link State. 443-3-3-پروتکل OSPF. 443-4 الگوریتم های مسیریابی.. 463-4-1-مسیریابی مبتنی بر کیفیت سرویس( QOS)463-4-2-مسیریابی چند منظوره. 463-4-3-مسیریابی چند مسیری.. 483-4-4-مسیریابی هوشمند. 49نتیجه گیری.. 52فصل چهارم مسیریابی در شبکه های موبایل بر اساس الگوریتم لانه مورچه. 544-1-مورچه ها چگونه می توانند کوتاهترین مسیر را پیدا کنند؟. 564_2_الگوریتم پایه لانه مورچه ای.. 574-4-چرا الگوریتم تخمین بهینه لانه مورچه ای برای شبکه های ad-hoc مناسبند؟. 614-5-بررسی الگوریتم های مسیریابی مبتنی بر مورچه ها برای MANETs. 624-6-الگوریتم های مسیریابی تخت... 624-6-1- الگوریتم مسیریابی مبتنی بر لانه مورچه. 624-6-2-موریانه. 774-6-3-الگوریتم مسیریابی اورژانس احتمالاتی(PERA )784-6-4-الگوریتم مسیریابی فوری ویژه:(EARA )794-6-5-مورچه AODV.. 814-7-پروتکل های مسیریابی سلسله مراتبی.. 824-7-1-مسیریابی مبتنی بر مورچه متحرک (MABR )824-7-2- SDRاتخاذ شده. 834-7-3-HOPENT. 844-8-الگوریتم ردیابی مورچه برای شبکه های اختصاصی موبایل.. 864-8-1-فهرست یا جدول پیشنهادی مسیریابی.. 874-8-2-مورچه ها884-8-3- کشف مسیر. 894-8-4-حفظ مسیر. 924-9-1-مروری بر پروتکل TARC.. 924-9-2- پروتکل TRAC.. 944-9-3-شبیهسازی.. 98فصل پنجم مسیریابی شبکه های موبایل بر اساس الگوریتم ژنتیک... 102مقدمه. 1035-1-الگوریتم ژنتیک... 1045-2:مسیریابی QoS در MANET بر اساس الگوریتم ژنتیک... 1095-2-1:QoS در MANET. 1095-2-2-نقش GA در مسیریابی QoS در MANET. 1135-2-3-شبیهسازی و نتایج.. 1175-3-1-مشکلات مسیر حرکتی SP. 1245-3-4-مطالعه تجربی.. 1315-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:ارسال داده توسط یک ایستگاه به سمت مقصد. 121شکل1-8:ایجادمسیر جدید پس از حذف یک ایستگاه میانی.. 12شکل 1-9:نمونه ای از یک ارتباط multi hop. 13جدول 2-1:انواع پروتکل های مسیریابی درMANET. 28شکل 2-1:مثالی از یک دسته بندی.. 36شکل 4-7:فلوچارت یک fant67شکل4-8 :تصویری از چگونگی ایجاد حلقه. 68Fجدول 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