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

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

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

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

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

۱- global , precomputed routing :

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

۲- on-demand routing :

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

۳- location base routing :

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

۴- flooding :

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

 

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

 

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

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

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

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

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

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

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

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

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


مشاهده ویدئو در این باره

خوشحال خواهیم شد اگر نظر خودتون رو درباره این مطلب ثبت کنید

خطا!دکمه ریفریش را بزنید
  1. تصویر آواتار کاربر 0
    صحراب ملکی جمعه , ۳۰ تیر

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

  2. تصویر آواتار کاربر 0
    ادنان سعیدی سه شنبه , ۷ شهریور

    ببخشید سوال من اینه که پروتکل هایی پشتیبانی شده در NS2 به صورت پیش فرض کدام ها هستن ؟

    • تصویر آواتار کاربر 1
      یعثوب سیفی زادهجمعه , ۳۱ شهریور

      نرم افزار NS2 پروتکل های مختلفی رو ساپورت می کنه که چند مورد از اونا AODV , DSR , DSDV , AOMDV , TORA هستند.

  3. تصویر آواتار کاربر 0
    جواد فلاحیان سه شنبه , ۲۸ شهریور

    سلام موضوع پروژه من روش های جديد مسير يابی در ادهاک هستش اما نميدونم دقيقا چيارو بايد توضيح بدم.

    • تصویر آواتار کاربر 1
      یعثوب سیفی زادهجمعه , ۳۱ شهریور

      می تونید مقاله هایی که سال چاپ اونا جدید هست رو از اینترنت دانلود و روی پروتکل هایی که ارائه شده تحقیق کنید. به این شکل کارتون با به روزترین پروتکل ها حل میشه.