دانشگاه آزاد اسلامی

واحد تهران جنوب

دانشکده تحصیلات تکمیلی

“M.Sc” پایان نامه برای دریافت درجه کارشناسی ارشد

مهندسی برق – الکترونیک

عنوان:

طراحی و پیاده سازی پروتکل انتخاب مجموعه مسیر منفصل بهینه به کمک شبکه عصبی هاپفیلد

چکیده

یک شبکه متحرک ad-hoc ساختاری دینامیک متشکل از پردازنده های متحرک است که در کنار هم و بدون داشتن زیرساختی ثابت تشکیل شبکه می دهند. گره ها در شبکه ad-hoc هم به عنوان میزبان و هم به عنوان مسیریاب در انتقال بسته ها به همسایگان خود، عمل می کنند. طراحی الگوریتم مسیریابی کارا و منعطف در این نوع شبکه ها به خاطر ساختار پویا و ماهیت شاخه های بی سیم ارتباطی، فرآیندی چالش برانگیز است. مسیریابی چندسویه منفصل را هحلی برای حل این مشکلات است که سبب افزایش قابلیت اطمینان، امنیت و طول عمر شبکه می شود. مجموعه مسیر منفصل م یتواند به صورت مجموعه مسیرهای شاخه – منفصل و یا گره – منفصل باشد. انتخاب مجموعه مسیر منفصل بهینه یک مساله NP-hard می باشد. از طرفی در پژوه شهای بسیاری شبک ههای عصبی بعنوان ابزارهای محاسباتی با قدرت حل مسائل پیچیده مطرح شده اند. در این پایان نامه به ارائه الگوریتم مسیریابی منفصل برای شبکه های ad-hoc متحرک بر پایه شبکه عصبی هاپفیلد به منظور ارتقاء قابلیت اطمینان پرداخته شده است. با استفاده از معیار زمان انقضای شاخه (LET)، معیار قابلیت اطمینان مسیر و مجموعه مسیر معرفی گردیده اند. همچنین با استفاده از مدل هاپفیلد نویزی و نیز تنظیم بهینه پارامترها با استفاده از الگوریتم تجمع ذرات (PSO) عملکرد الگوریتم بهبود داده شده است. الگوریتم مسیریابی پیشنهاد داده شده توانایی محاسبه مجموعه مسیرهای گره و شاخه – منفصل را تنها با یک با فرآیند جستجوی مسیر داراست. توسط شبیه سازی های انجام گرفته مشخص گردیده است که الگوریتم پیشنهادی قابلیت اطمینان را تا 4 و 1/5 برابر به ترتیب نسبت به الگوریتم مسیریابی تک سویه کوتاهترین مسیر و الگوریتم انتخاب مجموعه مسیر پشتیبان منفصل افزایش می دهد.

مقدمه

ابزار شبکه ی سیار و سخت افزارهای شبک هی بی سیم بصورت گسترده ای در دسترس هستند و تلاش گسترده ای برای یکپارچه کردن این عناصر با شبکه های رایج از قبیل شبکه ی اینترنت انجام شده است. هرچند اکثر اوقات، کاربران سیار باید در شرایطی که زیر ساخت سیمی ثابتی وجود ندارد ارتباط برقرار کنند. در چنین شرایطی، مجموعه ای از گرههای سیار با واسط های بی سیم ممکن است یک شبک هی موقت، بدون وجود نقطه دسترسی متمرکز و تحت مدیریتی ثابت، شکل دهند. این نوع شبکه ی بی سیم تحت عنوان شبکه ی سیار Ad-hoc – MANET شناخته شده است. در این شبکه وظایف شبکه مانند پخش بسته های اطلاعاتی، پیدا کردن مسیرها، مونیتورینگ شبکه، ایمن کردن ارتباط و غیره بر عهده گره ها در شبکه است. از چنین شبکه هایی بطور گسترده در کاربردهایی که از اهمیت عملی برخوردارند، درآینده استفاده خواهد شد، مانند: عملیات نجات در سوانح طبیعی، میدانهای جنگ، مخابرات مناطق ویژه مانند زمین های با کاربری ویژه، مناطق روستایی و حادثه دیده.

از آنجایی که گره ها در این شبکه موقعیت ثابتی ندارند و بصورت اختیاری حرکت می کنند، قطعی ارتباط را باید به عنوان رفتار عادی شبکه در نظر بگیریم، زیرا این حالت ممکن است بعد از جابجایی گره یا هنگامی که کاربر دستگاه خود را خاموش می کند، اتفاق بیافتد. اختلال در مسیر مستلزم فرایند بازیابی مسیر میباشد و ممکن است به تاخیرهای بیش از حد طولانی در لایه ی مسیریابی منجر شده و کیفیت خدمات را در کاربردهایی که به تاخیر حساس هستند تحت تاثیر قرار دهد.

یک روش مناسب جهت کاهش این تاثیرات استفاده از مسیرهای متعدد بجای استفاده از تنها یک مسیر است. اما یک سئوال اساسی و تقریباً مشکل مطرح است و آن اینکه از بین تمامی مسیرهای ممکن در شبکه کدام مسیرها را لایه ی مسیر یابی باید انتخاب کند تا به بیشینه قابلیت اطمینان دست پیدا کند؟ وابستگی خطا در بین مسیرهای مجموعه ی انتخابی باید تا حد امکان کوچک باشد. لینک ها و گره های مشترک بین مسیرها، نقاط خطای مشترک هستند که می توانند چندین مسیر در مجموعه و یا حتی تمامی آنها را تحت تأثیر قرار دهند. در نتیجه برای رسیدن به حداکثر قابلیت اطمینان به دنبال مسیرهایی هستیم که لینک یا نور مشترک نداشته باشند که به آنها مسیرهای منفصل می گوییم.

در اینجا هدف پیدا کردن مجموعه مسیرهایی بین مبدأ و مقصد است که احتمال شکست همزمان آنها بسیار کم باشد. دو اصل کلی در این زمینه وجود دارد. اول آنکه هر چه میسر طولانی تر باشد، قابلیت اطمینان آن کمتر است و دوم هر چه تعداد مسیرها در مجموعه مسیر افزایش یابد، قابلیت اطیمنان مجموعه افزایش می یابد. پس مجموعه باید شامل تعداد زیادی مسیر منفصل از هم کوتاه باشد.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید.