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

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

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

پروتکل مسیریابی HSR یا همان Hierarchical State Routing یک پروتکل مسیریابی سلسله مراتبی است که پویایی و دسته بندی سلسله مراتبی چند سطحی توزیع شده با یک مدیریت مکان کارآمد را با هم ترکیب می کند.

تفکیک و دسته بندی کار معمولی در شبکه های بی سیم چند جهشی در هر دو لایه MAC و لایه شبکه است، دسته بندی می تواند کارایی شبکه را زیاد کند. برای مثال در لایه MAC بوسیله استفاده از توزیع مختلف کدها در بین دسته ها تداخل کاهش داده می شود و استفاده مجدد از فضا زیاد می شود. چنانچه تعداد گره ها زیاد شوند، انگیزه بیشتری برای به کار انداختن اجزای لایه شبکه به منظور انجام مسیریابی سلسله مراتبی است در نتیجه سرباره مسیریابی کاهش می یابد.

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

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

دروازه در پروتکل مسیریابی HSR :

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

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

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

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

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

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

مهمترین معیار پایداری می باشد و مشکل بکارگیری ایده سرخوشه این است که گره ها در مقایسه با انتشار بسته ها، بیشتر مشغول انتخاب سرخوشه می باشند، پس تغییرات متناوب سرخوشه اثر بدی روی عملکرد پروتکل مسیریابی خواهد داشت. بنابراین به جای اینکه بعد از هر تغییر در اعضای گروه یک خوشه نیاز به انتخاب مجدد سرخوشه داشته باشیم، استفاده از الگوریتم کمترین تغییرات خوشه یا LCC پیشنهاد می شود.

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

الگوریتم LCC برای تأسیس و نگهداری مسیر هم از کمترین شناسه و هم از بیشترین اتصال استفاده می کند و گره های داخل هر خوشه اطلاعات لینک خود را به گره های دیگر منتشر می کنند. هر گره دارای ID سلسله مراتبی (HID) است که رشته ای از آدرس های MAC از بالا به گره منبع است.

روند خوشه بندی منطقی توسط ارتباط منطقی بین سرخوشه ها صورت می پذیرد و از این رو گره ها دارای آدرس تخصیص یافته <subnet, host> می باشند. گره های منطقی به لینک های منطقی متصل می شوند و به خوشه های سطح پایین تر تونل می زنند و اطلاعات حالت لینک منطقی به سطح پایین تر جریان می یابد. گره های فیزیکی در پایین ترین سطح دارای پیکربندی سلسله مراتبی از شبکه می باشد.

مزیت پروتکل مسیریابی HSR :

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

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

تصویری از نوعی شبکه مبتنی بر خوشه

دسته بندی فیزیکی در الگوریتم سلسله مراتبی :

به طور کلی ، سه نوع از گره ها در یک دسته وجود دارند، بنام های گره سر دسته (مثل گره های ۱ و ۲ و ۳ و ۴ ) ،گره دروازه (مثل گره های ۶ و ۷ و ۸ و ۱۱) و گره داخلی ( مثل ۵ و ۹ و ۱۰).

در شکل زیر گره سردسته مانند یک هماهنگ کننده محلی انتقال در میان دسته، رفتار می کند، ID های نشان داده شده در شکل زیر ( در سطح صفر ) آدرسهای فیزیکی بوده( مثل لایه MAC ) و آنها منحصر به فرد هستند. در پروتکل مسیریابی HSR ، آدرس سلسله مراتبی HID یک گره، از سلسله مراتب بالا تا گره خودش تعریف می شود.

در شکل زیر آدرس سلسله مراتب گره  HID(6)،۶  ( ۶ و ۲ و ۳  ) است و گره ۳ ، عضوی از دسته سلسله مراتب بالا (سطح ۲) و همچنین سر دسته از C1-3 است، گره ۲ عضو C1-3 و یک سر دسته از C0-2 است. گره ۶ یک عضو از C0-2 است و می تواند مستقیم از گره ۲ رسیده بشود.

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

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

مثالی از دسته بندی فیزیکی در الگوریتم سلسله مراتبی

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

خطا!دکمه ریفریش را بزنید
  1. تصویر آواتار کاربر 0
    امیر جوادی شنبه , ۲۴ تیر

    سلام پروتکل HSR رو میشه تو شبیه ساز NS2 استفاده کرد میشه پاسخ بدید؟؟

    • تصویر آواتار کاربر 1
      یعثوب سیفی زادهسه شنبه , ۲۷ تیر

      بله میشه انجام داد در صورت نیاز شبیه سازی پروتکل HSR ما می تونیم براتون انجام بدیم

  2. تصویر آواتار کاربر 223
    Khalid Hamzah Haza Al Hamami دوشنبه , ۱۷ اردیبهشت

    is there any HSR simulation example for NS2?

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

      برای پروتکل HSR در سایت ما فعلا مثالی که با ns2 شبیه سازی شده باشد وجود ندارد اگر سفارش بدید می تونیم براتون انجام بدیم

  3. تصویر آواتار کاربر 223
    Khalid Hamzah Haza Al Hamami دوشنبه , ۱۷ اردیبهشت

    How to order it?

  4. تصویر آواتار کاربر 223
    Khalid Hamzah Haza Al Hamami سه شنبه , ۱۸ اردیبهشت

    do i need any patch to implement HSR protocol in NS 2?