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

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

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

پروتکل مسیریابی DSDV یا همان Destination Sequence Distance Vector یک پروتکل مناسب برای شبکه های ادهاک می باشد. این پروتکل گسترش یافته الگوریتم بردار فاصله کلاسیک یا DBF است.

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

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

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

اعلام مسیر در پروتکل مسیریابی DSDV :

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

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

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

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

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

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

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

بنابراین مسیرهای با معیار بینهایت خیلی زود توسط مسیرهای با معیار محدود، جایگزین می شوند. برای کاهش هزینه های بروزرسانی اطلاعات توپولوژی شبکه، یک گره می تواند دو نوع بسته را انتخاب کند که عبارتند از Full-dump و افزایشی. پیام های Full-dump تمام اطلاعات مسیریابی را از جدول مسیریابی فرستنده به همراه دارد. معمولاً این اطلاعات حتی برای شبکه های کوچک نیز نیاز به چندین بسته دارند. در عوض پیام های افزایشی فقط اطلاعاتی که بعد از آخرین پیام Full-dump تغییرکرده است را با خود دارند و بر طبق قرارداد باید فقط توسط یک بسته ارسال شوند.

وقتی گره ها به ندرت حرکت می کنند، پیام های افزایشی به یک بسته ساده محدود بوده و برای بروزرسانی اطلاعات مسیریابی کافی و مناسب هستند. در این حالت پیام های Full-dump می توانند با فرکانس کمتری ارسال شوند. وقتی گره ها دائماً در حال حرکت هستند، اندازه پیام های بروز کننده افزایشی به پیام های Full-dump نزدیک می شود. در این حالت پیام های Full-dump باید با فرکانس بیشتری ارسال شوند تا بتوان اندازه پیام های بروزکننده افزایشی را کاهش داد.

پروتکل مسیریابی DSDV برای پخش اطلاعات جداول مسیریابی، هم از بروزرسانی دوره ای برای پخش کلیه اطلاعات توپولوژی به صورت پیام های Full-dump و افزایشی و هم از بروز سازی فعال شده برای پخش تغییرات مهم در توپولوژی استفاده می کند.

توپولوژی شبکه ادهاک فرضی :

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

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

در جدول زیر یک ساختار فرضی برای جدول هدایت کننده نگهداری شده در MH4 را نشان می دهد.

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

با فرض اینکه آدرس هر گره MHi باشد، کلیه اعداد ترتیبی به صورت SXXX-MHi نمایش داده می شوند. زمان نصب کمک می کند تا مشخص کنیم که چه زمانی مسیرهای قدیمی را باید حذف کنیم. در جدول بالا می بینیم که کلیه گره ها تقریباً در یک زمان برای MH4 در دسترس می باشند چون برای بیشتر آنها Install-Time یکسان می باشد. جدول زیر ساختار جدول اعلام شده برای MH4 را نشان می دهد.

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

حالا فرض می کنیم که MH1 حرکت می کند و در همسایگی MH8 و MH7 قرار می گیرد و از سایر گره ها ( خصوصاً MH2 ) دور می شود. اعلان مسیر در گره مقصد آغاز می شود و در کل شبکه منتشر می شود. شکل زیر انتشار منطقی را از یک ورودی مسیر، از یک گره مقصد به سایر گره های شبکه را نشان می دهد.

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

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

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

جدول بالا فقط ورودی های MH1 را نشان می دهد و معیار جدیدی را بکار می برد، اما در فاصله زمانی مداخله ، رشته های ترتیبی زیادی دریافت شده اند. این تغییر بندرت بدلیل بزرگ تر بودن شماره ترتیبی اتفاق می افتد. پیام بروزکننده مشابه (مثلاً همان مقصد و با همان شماره ترتیبی) از MH5 و MH7 به ترتیب به MH6 می رسد. MH6 پیام را از MH7 می پذیرد زیرا که معیار بهتری دارد. بروز شدن مسیر اعلام شده افزایشی در MH4 در جدول نشان داده شده است. در این اعلان، اطلاعات ابتدا برای MH4 می رسد، بنابراین MH4 اعلان را انجام می دهد. سپس اطلاعات مربوط به MH1 می رسد چون تنها گره ای است که هر تغییر مهم در مسیر روی این گره اثر می گذارد.

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

میرا کردن نوسانات در پروتکل مسیریابی DSDV :

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

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

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

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

معایب پروتکل مسیریابی DSDV :

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


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

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

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

    سلام می خواستم ببینم از میان پروتکل dsdv و olsr کارکرد کدومشون می تونه بهتر باشه ؟