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

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

پروتکل های مسیریابی (Routing protocols) موجود برای شبکه های ادهاک موبایل را به گونه های متفاوتی تقسیم بندی می کنند که در زیر طرح های مسیریابی در شبکه ادهاک را با جزئیات کامل به همراه پروتکل های مسیریابی موجود در آنها ذکر شده است.

طرح های مسیریابی شبکه در چهار گروه پهناور دسته بندی می شود

1- global , precomputed routing

مسیرها از قبل برای همه مقصدها محاسبه می شوند و بوسیله فرآیند به روزکننده به صورت دوره ای، نگهداری می شوند. بیشترین مسیریابی مرسوم شامل مسیریابی DV و مسیریابی LS در این گروه قرار می گیرند.

2- on-demand routing

در این روش همانطور که توضیح داده شد مسیر برای یک مقصد ویژه تنها زمانی که نیاز باشد محاسبه می شود.

3- location base routing

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

4- flooding

فرض می شود کمترین یا بدون اطلاع از ساختار شبکه هستیم. هیچ مسیری بر حسب تقاضا محاسبه نمی شود. در روش flooding یک بسته به تمامی گره هایی که در منطقه تحت پوشش هستند منتشر می شود. این گره ها نیز به انتشار بسته ها پرداخته و عملیات فوروارد تا هنگامی که بسته به مقصد نهایی برسد ادامه پیدا می کند. مزیت این روش مقاومت در برابر تغییرات پیکربندی و سرباره کم پروتکل مسیریابی می باشد. درحقیقت، در شبکه های که حرکت زیادی دارند، این روش تنها راه حل ممکن برای مسیریابی است. کپی های چندگانه که از یک بسته در شبکه حرکت می کند اشکال آن می باشد که عرض باند و توان باتری گره های ارسال کننده را تلف می کند.

طرح های مسیریابی

مسیریابی Global , Precomputed خود می تواند به گروه مسطح و سلسله مراتبی تقسیم می شود، البته در حالت کلی نیز می توان بر اساس ساختار، پروتکل های مسیریابی ادهاک را به این دو دسته تقسیم کرد.

در روشهای مسیریابی مسطح (تخت) هر گره یک جدول مسیریابی با ورودی های برای تمام گره های شبکه ایجاد می کند. تمام گره های شبکه نقش یکسانی در عملیات مسیریابی دارند و هیچ گره ای نقش متمایزی از سایر گره ها به عهده ندارد. در گروه مسیریابی مسطح ، پروتکل های زیادی برای پشتیبانی مسیریابی ادهاک بی سیم سیار پیشنهاد شده است. تعدادی از طرح ها در ادامه طرح های شبکه های سیمی سنتی پیشرفت کرده اند. برای مثال، اساس پروتکل مسیریابی DSDV پرکینز مبنی بر DBF است و پروتکل مسیریابی WRP گارسیا نیز مبنی بر الگوریتم کشف مسیر استوار است که هر دوی این ها مسیریابی بدون حلقه می باشند. روش مسیریابی تخت در صورتی قابل قبول است که تعداد کاربران کم باشد و با افزایش تعداد کاربران، هزینه ها افزایش می یابد، بنابراین الگوریتم های مسیریابی تخت برای شبکه های بزرگ مناسب نیستند.

در شکل 1 ساختارهای تخت و سلسله مراتبی نشان داده شده است.

شکل 1: نمایش ساختارهای تخت و سلسله مراتبی

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

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

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

1- مسیریابی بردار فاصله

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

هر درایه دارای دو بخش است :

1. خط خروجی مناسب برای رسیدن به مقصد مورد نظر
2. تخمینی از زمان یا فاصله رسیدن بدان مقصد

2- مسیریابی حالت لینک

دو مشکل اساسی منجر به زوال مسیریابی بردار فاصله و جایگزینی با مسیریابی حالت لینک شده است. اول اینکه در این الگوریتم معیار تاخیر، طول صف (تعداد بسته های به صف شده منتظر ارسال بر روی یکی از خطوط خروجی مسیریاب) در نظر گرفته می شد و پهنای باند هر یک از خطوط در محاسبات انتخاب بهترین مسیر، دخالت داده نمی شد. در ابتدا تمام خطوط 56kbps بودند لذا پهنای باند خط، مورد مهمی نبود، ولی پس از آنکه برخی از خطوط به سرعت 230kbps و بیشتر ارتقاء یافتند، به حساب نیاوردن پهنای باند، مشکلی عمده به حساب می آمد، البته این امکان وجود داشت که بتوان معیار تاخیر را به پهنای باند تغییر داد و لیکن مشکل دیگری ایجاد می شد و آن هم اینکه، همگرایی الگوریتم بسیار طولانی می شد. به همین دلیل با الگوریتم مسیریابی حالت لینک تعویض شد.

امروزه الگوریتم های متفاوتی از مسیریابی حالت لینک مورد استفاده قرار می گیرد، ایده اصلی و زیر بنای مسیریابی حالت لینک ساده است و می توان آن را در پنج جمله بیان کرد.

هر مسیریاب باید به ترتیب زیر عمل کند :

1. همسایه های خود را شناسایی کرده و آدرس های شبکه را بدست بیاورد.
2. تاخیر هر یک از همسایه های خود را اندازه گیری نماید.
3. بسته ای بسازد و اطلاعاتی که از همسایه کسب کرده، در آن جاسازی کند.
4. این بسته ها را برای تمام مسیریاب های دیگر بفرستد.
5. کوتاه ترین مسیر رسیدن به دیگر مسیریاب ها را محاسبه نماید.

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

شکل 2 پروتکل های مسیریابی تک پخشی موجود و طبقه بندی آنها را نشان می دهد. سر دسته پروتکل مسیریابی تک پخشی وجود دارد:

1. پروتکل های مبتنی بر جدول ( پروتکل‌های جدولی).
2. پروتکل های بنابه درخواست ( پروتکل‌های نیازی).
3. پروتکل های دورگه که تلفیقی از دو نوع قبلی هستند.

شکل 2: دسته بندی پروتکل های مسیریابی تک پخشی

1- پروتکل های مسیریابی تک پخشی مبتنی بر جدول (Table Driven – Proactive) :

• پروتکل مسیریابی DSDV یا (Dynamic Destination-Sequenced Distance-Vector Routing Protocol)
• پروتکل مسیریابی WRP یا (The Wireless Routing Protocol)
• پروتکل مسیریابی GSR یا (Global State Routing)
• پروتکل مسیریابی FSR یا (Fisheye State Routing)
• پروتکل مسیریابی HSR یا (Hierarchical State Routing)
• پروتکل مسیریابی OLSR یا (Optimized link state routing)
• پروتکل مسیریابی CGSR یا (Clusterhead Gateway Switch Routing Protocol)
• پروتکل مسیریابی STAR یا (Source-tree adaptive routing)
• پروتکل مسیریابی MMWN یا (Multimedia support in mobile wireless networks)
• پروتکل مسیریابی TBRPF یا (Topology broadcast reverse path forwarding)
• پروتکل مسیریابی DREAM یا (Distance routing effect algorithm for mobility)

 2- پروتکل های مسیریابی تخت تک پخشی بر اساس نیاز (On Demand – Reactive) :

• پروتکل مسیریابی منبع پویا DSR یا (Dynamic Source Routing)
• پروتکل مسیریابی AODV یا (Ad Hoc On-demand Distance Vector Routing)
• پروتکل  مسیریابی TORA یا (Temporally Ordered Routing Algorithm)
• پروتکل  مسیریابی ABR یا (Associativity Based Routing)
• پروتکل  مسیریابی SSA یا (Signal stability based adaptive routing)
• پروتکل  مسیریابی LMR یا (Lightweight Mobile Routing)
• پروتکل  مسیریابی LAR یا (Location-aided routing)
• پروتکل  مسیریابی CBRP یا (Cluster-based routing protocol)
• پروتکل  مسیریابی RDMAR یا (Relative distance micro-discovery ad hoc routing)
• پروتکل  مسیریابی ARA یا (Ant-colony-based routing algorithm)
• پروتکل  مسیریابی FORP یا (Flow oriented routing protocol)
• پروتکل  مسیریابی ROAM یا (Routing on-demand acyclic multi-path)

 3- پروتکل های مسیریابی دورگه (Hybrid) :

• پروتکل  مسیریابی ZRP یا (Zone Routing Protocol)
• پروتکل  مسیریابی ZHLS یا (Zone based Hierachical Link State Routing Protocol)
• پروتکل  مسیریابی DDR یا (Distributed dynamic routing)

پروتکل های مسیریابی چند پخشی

به الگوریتم های مسیریابی که در ارسال های چند پخشی مورد استفاده قرار می گیرد، مسیریابی چند پخشی گویند. در شبکه‌ های Ad Hoc به دلیل چالش های نگهداری مسیر ارتباطی بین منبع و مقصد در سطح وسیعی مورد بررسی قرار می‌گیرند. حتی زمانیکه برخی از گره‌های عادی قادر به ادامه مشارکت در ارسال بسته ها رو به جلو نیستند، این بسته باید به وسیله گره‌های مسیر دیگری جابجا شوند. پس نتیجه می‌شود که نگهداری مسیرها بین منبع منفرد و چندین مقصد تا اندازه ای مشکل زا است. با توجه به اهمیت روز افزون چند پخشی به عنوان وسیله‌ای برای کاهش استفاده از پهنای باند جهت توزیع حرمی داده‌ها و نیاز مبرم به ذخیره پهنای باند در طول میدان‌های بی‌سیم، طبیعی است که مسیریابی چند پخشی باید تا اندازه‌ای مورد توجه شبکه‌های Ad Hoc قرار گیرد.

شکل 3: دسته بندی پروتکل های مسیریابی چند پخشی

طبقه بندی مسیریابی چند پخشی

همانطور که در شکل 3 دیده می شود سه طبقه‌ بندی از پروتوکل های مسیریابی چند پخشی وجود دارد که هر کدام از این سه دسته خود در یکی از دسته های درختی و یا بر اساس مش قرار می گیرد. پروتکل جدولی همانطور که میدانیم مسیرها را برای همه جهت‌ های ممکن از قبل محاسبه می‌ کند و این اطلاعات را در جدول‌ های مسیریابی ذخیره می‌ نماید. برای نگهداری به روز پایگاه اطلاعاتی، مسیریابی به طور پریودیک در امتداد شبکه توزیع می‌شود.

یک مثال از این مورد CAMP می‌باشد، پروتکل نیازی یا بر پایه نیاز پروتوکل های هستند که مسیرهای را برای میزبان های دیگر بر حسب تقاضا خلق می‌نمایند. این ایده بر پایه مکانیزم درخواستی است که به مقصد می‌ رسد و سپس فاز پاسخ وارد شده و مسیر را می‌سازد. پروتکل ODMRP و پروتکل MAODV مثال های از آن می‌ باشند. پروتکل آخر نیز ، جریان ساده است که در شبکه هر گره دریافت‌ کننده پیام آنرا به لیستی از همسایه‌ های خود ارسال می کند AMRoute مثالی از آنست.

پروتکل های موجود در مسیریابی چند پخشی :

• پروتکل مسیریابی AMRoute یا (Adhoc multicast routing protocols)
• پروتکل مسیریابی MAODV یا (Multicast Ad-hoc On-Demand Vector protocol)
•  پروتکل مسیریابی CAMP یا (Core Assisted Mesh Protocol)
• پروتکل مسیریابی ODMRP یا (On-Demand Multicast Routing Protocol)