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

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

الگوریتم های مسیریابی متفرقه

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

  • پنجشنبه ۲۹ تیر ۱۳۹۶
  • بازدید ۱,۳۳۵ نفر

تصویر rdmar-routing-protocol-in-mobile-ad-hoc-networks_701 پروتكل مسیریابی RDMAR در شبکه های ادهاک موبایل

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

پروتكل مسیریابی RDMAR یا Relative distance micro-discovery ad hoc routing یکی از پروتکل های مسیریابی شبکه های ادهاک می باشد که جزء پروتکل های تخت تک پخشی بر اساس نیاز می باشد.

عملکرد پروتكل مسیریابی RDMAR

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

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

به عنوان مثال برای هر مقصد J این جدول شامل یک مسیریاب پیش فرض است که گره بعدی که انتظار می رود بتواند با گره J ارتباط برقرار کند، را مشخص می کند. قسمت RD که فاصله نسبی تخمین‌ زده شده بین گره J و گره کنونی را در خود دارد همچنین قسمت TLU نشان‌ دهنده زمانی است که آن گره برای آخرین بار اطلاعات مسیریابی به سمت مقصد J را دریافت کرده است. قسمت RT، زمان باقیمانده پیش از آنکه مسیر نامعتبر شناخته شود را ثبت می کند و یک بخش نشانده مسیر، که نشان می دهد که آیا مسیر منتهی به J، فعال است یا خیر.

 

پروتکل ‌RDMAR از دو الگوریتم اصلی تشکیل شده است :

اولین الگوریتم اکتشاف مسیر بدین صورت عمل می کند که‌ وقتی که یک پیام بدست آمده برای گره مقصد J، وارد گره i می شود و هیچ مسیری در دسترس نیست، گره i یک مرحله کشف مسیر را شروع می کند. در این جا گره i دو راه پیش دارد. یا با یک درخواست مسیر که درون شبکه به صورت وسیع پخش شود که در این حالت بسته های درخواست مسیر در سراسر شبکه همه پخش می شود.

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

این زمان را زمان حرکت  می نامیم و بر اساس این اطلاعات و با فرض یک سرعت متوسط که آن را (MICRO VELOCITY) می نامند و یک رنج انتقال متوسط در آن صورت گره i قادر خواهد بود که فاصله نسبی جدیدش تا مقصد J را بر حسب تعداد واقعی جهش‌ها تخمین بزند بدین منظور گره i انحراف مسیرش از DST را در طول زمان Tmotion محاسبه کرده و نتیجه را با فاصله نسبی قبلی‌اش تصحیح می کند.

نگهداری مسیر در پروتكل مسیریابی RDMAR :‌

یک گره حد واسط به نام i براساس بسته داده‌هایی که دریافت کرده ابتدا سر پیام  مسیریابی را پردازش نموده و سپس بسته را به پرش بعدی خود وارد می کند علاوه بر این گره i یک پیام مربع را می فرستد تا بیازماید که آیا لیک دو جهته می تواند با گره قبلی ایجاد شود یا خیر. بنابر این پروتكل مسیریابی RDMAR مسیرهای دو جهته را فرض نمی کند اما در مقابل گره‌ها امکان برقراری ارتباط دو جهته را بررسی می کنند. اگر گره را به علت عدم دسترسی به هیچ مسیر یا یک خطای فورواد سازی بر اثر قطع ارتباط در مسیر داده‌ها قادر به فوردوارد کردن بسته نباشد، در این صورت گره i اقدام به بازانتقال همان بسته داده ها می کند و این کار را تا حداکثر دفعات ممکن انجام می دهد.

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

مزایای پروتكل مسیریابی RDMAR

  1. عدم نیاز به تکنولوژی موقعیت مانند GPS

معایب پروتكل مسیریابی RDMAR

  1. نداشتن قابلیت مقیاس پذیری در شبکه های بزرگ
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است