مسیریابی شبکه های کامپیوتری

انواع مسیریابی

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

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

تقسیم بندی های مختلفی در مورد پروتکل های مسیر یابی شبکه های Mobile ad hoc وجود دارد که از این میان می توان به 2 نوع زیر اشاره کرد:
تقسیم بندی اول :

Pro active(Table driven)
Reactive(On demand)
Hybrid(Table driven & On demand)
هر کدام از این انواع خود شامل پروتکل هایی هستند که در زیر اشاره شده است:

تقسیم بندی دوم:

Flat routing protocols
Hierarchal routing approaches
GPS Augmented geographical routing approaches

در اینجا به توضیحاتی در مورد پروتکل های تقسیم بندی اول می پردازیم:

1.Table driven Pro active -
در پروتکلهای از این نوع , node ها مدام در حال جستجوی اطلاعات مسیر یابی جدید درون شبکه هستند به صورتی که حتی با تغییر مکان node ها در صورت نیاز به راحتی می توان مسیر مناسبی را یافته و برای ارسال و دریافت اطلاعات بین هر دو node ی استفاده کرد . به عبارت بهتر می توان گفت که در این شبکه ها مسیر ها از قبل موجود هستند.و به محض آنکه node ی اقدام به ارسال داده به node دیگری کند قادر خواهد بود مسیر موجود را از روی اطلاعات از قبل جمع آوری شده شناسایی کرده و مورد استفاده قرار دهد و لذا تاخیری در این مورد متوجه node نیست.

DSDV این پروتکل بر مبنای الگوریتم کلاسیک Bellman-Ford بنا شده است.در این حالت هر node لیستی از تمام مقصد هاو نیز تعداد hop ها تا هر مقصد را تهیه می کند.هر مدخل لیست با یک عدد شماره گزاری شده است . برای کم کردن حجم ترافیک ناشی از به روز رسانی مسیر ها در شبکه از incremental packets استفاده می شود.تنها مزیت این پروتکل اجتناب از به وجود آمدن حلقه های مسیر یابی در شبکه های شامل مسیر یاب های متحرک است.بدین ترتیب اطلاعات مسیر ها همواره بدون توجه به این که آیا node در حال حاضر نیاز به استفاده از مسیر دارد یا نه فراهم هستند.
معایب پروتکل DSDV نیازمند پارامترهایی از قبیل بازه ی زمانی به روز رسانی اطلاعات و تعداد به روز رسانی های مورد نیاز می باشد.

WRP این پروتکل بر مبنای الگوریتم path-finding بنا شده با این استثنا که مشکل count-to-infinity این الگوریتم را برطرف کرده است. در این پروتکل هر node , 4 جدول تهیه می کند جدول فاصله , جدول مسیر یابی , جدول link-cost و جدولی در مورد پیامهایی که باید دوباره ارسال شوند.تغییرات ایجاد شده در لینکها از طریق ارسال و دریافت پیام میان node های همسایه اطلاع داده می شوند.

CSGR در این نوع پروتکل node ها به دسته ها یا cluster هایی تقسیم بندی می شوند . هر گروه یک cluster head دارد که می تواند گروهی از host ها را کنترل و مدیریت کند.از جمله قابلیت هایی که عمل clustering فراهم می کند می توان به اختصاص پهنای باندو channel access اشاره کرد.این پروتکل از DSDV به عنوان پروتکل مسیریابیی زیر بنایی خود استفاده می کند . نیز در این نوع هر node دو جدول یکی جدول مسیریابیی و دیگری جدول مریوط به عضویت در node های مختلف را فراهم می کند.
معایب node ی که head واقع شده سربار محاسباتی زیادی نسبت به بقیه داردو به دلیل اینکه بیشتر اطلاعات از طریق این head ها برآورده می شونددر صورتی که یکی از node های head دچار مشکل شود کل و یا بخشی از شبکه آسیب می بیند.

STAR این پروتکل نیاز به به روز رسانی متداوم مسیر ها نداشته و هیچ تلاشی برای یافتن مسیر بهینه بین node ها نمی کند.

2.On demand Reactive -
در این نوع پروتکل مسیر ها تنها زمانی کشف می شوند که مبدا اقدام به برقراری ارتباط با node دیگری کند.زمانی که یک node بخواهد با node دیگری ارتباط برقرار کند بایستی فرایند کشف مسیر ( Route Discovery Process ) را در شبکه فراخوانی کند.در این حالت قبل از بر قرار شدن ارتباط , تاخیر قابل توجهی مشاهده می شود.

SSR این پروتکل مسیرها را بر مبنای قدرت و توان سیگنالها بین node ها انتخاب می کند. بنابراین مسیرهایی که انتخاب می شوندد نسبتا قوی تر هستند . می توان این پروتکل را به 2 بخش DRP( Dynamic Routing Protocol) و SRP ( Static Routing Protocol) تقسیم کرد. DRP مسئول تهیه و نگهداری جدول مسیریابی و جدول مربوط به توان سیگنال ها می باشد.SRP نیز packet های رسیده را بررسی می کند تا در صورتی که آدرس node مربوط به خود را داشته باشد آن را به لایه های بالاتر بفرستد و در غیر این صورت به شبکه.

DSR در این نوع , node های موبایل بایستی cache هایی برای مسیر هایی که از وجود آنها مطلع هستند فراهم کنند.دو فاز اصلی برای این پروتکل در نظر گرفته شده است کشف مسیر و به روز رسانی مسیر. فاز کشف مسیر از route request/reply packet ها و فاز به روز رسانی مسیر از acknowledgement ها و error های لینکی استفاده می کند.

TORA بر اساس الگوریتم مسیر یابی توزیع شده بنا شده و برای شبکه های mobile بسیار پویا طراحی شده است.این الگوریتم برای هر جفت از node ها چندین مسیر تعیین می کند و نیازمند clock سنکرون می باشد. 3 عمل اصلی این پروتکل عبارتند از ایجاد مسیر. به روز رسانی مسیر و از بین بردن مسیر.

AODV بر مبنای الگوریتم DSDV بنا شده با این تفاوت که به دلیل مسیریابی تنها در زمان نیاز میزان Broad casting را کاهش می دهد.الگوریتم کشف مسیر تنها زمانی آغاز به کار می کند که مسیری بین 2 node و جود نداشته باشد
RDMAR این نوع از پروتکل فاصله ی بین 2 node را از طریق حلقه های رادیویی و الگوریتم های فاصله یابی محاسبه می کند. این پروتکل محدوده ی جستجوی مسیر را مقدار مشخص و محدودی تایین می کند تا بدین وسیله از ترافیک ناشی از flooding در شبکه کاسته باشد.

3.Hybrid (Pro-active / Reactive)
این مورد با ترکیب دو روش قبلی سعی در کاهش معایب کرده و از ویژگی های خوب هر دو مورد بهره می برد. این پروتکل جدید ترین کلاس پروتکل ها در این راستا می باشد. معروفترین پروتکل از این نوع می توان به ZRP( Zone Routing protocol) اشاره کرد.این پروتکل از ویژگی های نوع Pro active برای مسیریابی node های نزدیک به هم و از ویژگی های نوع Reactive برای مسیر یابی node های دورتر استفاده می کند.

ZRP نوعی از clustering است با این تفاوت که در این پروتکل هر Node خود head بوده و به عنوان عضوی از بقیه ی cluster ها می باشد. به دلیل hybrid بودن کارایی بهتری دارد.

Ad-hoc On-demand Distance Vector Routing Protocol
پروتکل مسیریابی AODV یک پروتکل مسیریابی On-Demand است که در آن همه مسیرها فقط وقتیکه مورد نیاز باشند کشف می شوند و تنها در طول مدتی که مورد استفاده قرار می گیرند نگهداری می شوند.مسیرها در طول یک Flooding کشف می شوند که در طی آن نودهای شبکه در فرآیند جستجوی یک مسیر به سمت مقصد مورد سوال قرار می گیرند.وقتی یک نود با یک مسیر به مقصد کشف می شود آن مسیر به عقب و به نود مبدائی که درخواست مسیر کرده بود گزارش می شود.

AODV برای تحقق اهداف زیر طراحی شده است :

حداقل سربار کنترلی
حداقل سربار پردازشی
قابلیت مسیریابی چندگامی
نگهداری پویای توپولوژی
عاری بودن از حلقه

چون منابع در شبکه های متحرک Ad hoc کمیاب هستند AODV سعی می کند تا سربار کنترلی را با محدود کردن بروزرسانی های متناوب مسیر و همچنین تنها استفاده از پیغام های On-Demand به حداقل برساند.برای به حداقل رساندن سربار پردازشی ٬ پیغام های AODV ساختار ساده ای دارند و نیاز به محاسبات کمی دارند . در یک شبکه Ad hoc منابع ومقصدها ممکن است در خارج از محدوده ارتباطی مستقیم یکدیگر باشندکه این به خاطر محدودیت حوزه ارسال تجهیزات بیسیم است. از اینرو AODV نودها را قادر می سازد بنوانند از کشف مسیرهای چندگامی به سمت مقصد استفاده کنند و این مسیرها را تا وقتی که توپولوژی شبکه به طورمدام تغییر می کند نگهداری کنند . همچنین در برابر حلقه های مسیریابی به شدت مقابله می کنند چون آنها در هر شبکه ای پر هزینه هستنند مخصوصا در یک شبکه بیسیم که ظرفیت سیگنالینگ و توان پردازشی نود محدود است. AODV در هر نود شماره های ترتیبی را برای جلوگیری از حلقه های مسیریابی بکار می برد.

این پروتکل شامل دو فاز می باشد:
1- کشف مسیر
2- نگهداری مسیر

کشف مسیر:

AODV انواع پیغام های زیر را تعریف می کند:

Route Request (RREQ)
Route Reply (RREP)
Route Error (REER)
Route Reply Acknowledgment (RREP-ACK)
وقتی یک نود مبدأ نیاز به یک مسیر به یک نود مقصد داشته باشد و مسیر معتبری در جدول مسیریابی نباشد، نود مبدأ یک بسته درخواست مسیر (RREQ) را به سمت نود مقصد همه پخشی می کند. وقتی هر نود RREQ را دریافت می کند، یک ورودی مسیر برعکس به سمت نود مبدأ را در جدول مسیریابی ایجاد یا بروزرسانی می کند و اگر یک مسیر معتبر در جدول مسیریابی به سمت نود مقصد ، ندارد RREQ را دوباره همه پخشی می کند . وقتی Flooding بسته RREQ از نود مبدأ به نود مقصد برسد، نود مقصد ورودی مسیر برعکس را ایجاد یا بروزرسانی می کند و یک بسته پاسخ مسیر (RREP) را که یک شماره ترتیب افزایش یافته دارد در مسیر برعکس تک پخشی می کند. وقتی RREP به نود مبدأ و در طول مسیر برعکس می رسد، یک مسیر رو به جلو را به سمت مقصد ایجاد یا بروزرسانی کرده و ارتباطات شروع می شود.

مسیریابی شبکه های کامپیوتری

مطالب مشابه :

الگوریتم دایجسترا

دانلود پروژه رایگان الگوریتم دایجسترا با نرم افزار MATLAB

مسیریابی شبکه های کامپیوتری

الگوريتم دايكسترا (Dijkstra's algorithm) چيست؟

دانلود رایگان سورس الگوریتم دیکسترا به زبان ++C

الگوریتم‌های مسیریابی

انواع الگوریتم مسیریابی

انواع الگوریتم search

الگوریتم پریم چگونه کار می کند ؟