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

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

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

پروتکل مسیریابی AODV یا Ad-hoc On Demand Distance یک پروتکل مسیریابی مبتنی بر تقاضا است که در شبکه های ادهاک جهت مسیریابی مورد استفاده قرار می گیرد.

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

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

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

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

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

شکل ۱: یک شبکه پنج گره ای در یک شبکه ادهاک

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

کشف و برقراری مسیر در پروتکل AODV :

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

بسته RREQ (ROUTE REQUEST) در پروتکل مسیریابی AODV :

در بسته RREQ درخواست موارد ذیل موجود است: آدرس IPی گره مبدأ، شماره ترتیبی جاری مبدأ، Broadcast ID جاری مبدأ، تعداد پرش ها تا مبدأ، آخرین شماره ترتیبی گره مقصد که گره مبدأ از اطلاع دارد.

قالب بسته تقاضای مسیر در شکل ۳ نشان داده شده است. این بسته مشخص می کند چه کسی در جستجوی چه کسی است. بعد از اینکه گره مبدأ بسته RREQ را ساخت، آنرا به تمام همسایگانش می فرستد و آنها نیز هر یک بسته را به همسایگان خود می فرستند و تا جایی این روند ادامه می یابد که بسته یا به گره مقصد برسد و یا به گره دیگری برسد که در حال حاضر مسیری تا گره مقصد دارد. این بسته همچنین شامل یک شماره تقاضا ID است. این شناسه در واقع یک شمارنده محلی است که در هر گره وجود دارد و هرگاه یک بسته تقاضای مسیر منتشر گردید یک واحد به آن اضافه می شود.

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

شکل ۲: جدول کشف مسیر در مسیریابی AODV برای شبکه شکل ۱

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

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

شکل ۳: قالب بسته ROUTE REQUEST

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

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

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

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

شکل ۴: قالب بسته ROUTE REPLY

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

شماره های ترتیب مانند نشانه های زمانی رفتار می کنند. هر زمانی که هر گره پیامی از هر نوع را بیرون می فرستد، شماره ترتیبی اش را افزایش می دهد. هر گره شماره ترتیبی همه گره های دیگر را که با آنها صحبت کرده است را ضبط می کند. یک شماره ترتیبی بزرگتر بر یک مسیر تازه تر(fresher) دلالت می کند. این کار برای گره های دیگر کشف این که کدام اطلاعات دقیق تر است ممکن می سازد. در شکل ۵، گره ۱ در حال ارسال یک RREP برای گره ی ۴ است. گره ۱ توجه می کند که مسیر در RREP یک شماره ترتیبی بزرگ تری نسبت به مسیر داخل لیست مسیریابی اش دارد. سپس گره ی۱ لیستش را با مسیر جدید به روز می کند.

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

شکل ۵: گره ۱ در حال ارسال یک RREP برای گره ی ۴

مدیریت جداول مسیر در پروتکل مسیریابی AODV :

پروتکل AODV نیاز دارد که اطلاعات ذیل را درون هر یک از ورودی های جداول مسیر داشته باشد: آدرس IP ی مقصد، شماره ترتیبی مقصد، تعداد جهش ها تا مقصد، آدرس IP ی گره مجاور برای جهش بعدی در مسیر مورد نظر، مدت زمانی که مسیر معتبر است، لیستی از بقیه همسایه هایی که از این مسیر استفاده می کنند ، بافری برای درخواست ها که اطمینان می دهد، که هر درخواست تنها یک بار بررسی می شود.

نگهداری مسیر در پروتکل مسیریابی AODV :

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

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

برای جلوگیری از این مشکل هر گره در ابتدای ورود به شبکه، حداکثر به اندازه مدت زمان delete-period صبر می کند تا یک بسته RREQ دریافت کند و از روی آن آخرین شماره ترتیبی خود را بروز کند. گره ی مذکور در طی این مدت به بسته های مسیریابی هیچ پاسخی نمی دهد و اگر بسته داده به آن رسید یک پیغام RERR به فرستنده می دهد.

تنها با گره های می توان با آنها ارتباط مستقیم برقرار کرد که همسایه باشند. یک گره ی ردیابی همسایه هایش را بوسیله لیست کردن یک پیغام hello که هر گره در فاصله معین آن را پخش می کند، نگه می دارد. وقتی که یک گره احتیاج به فرستادن یک پیغام برای گره دیگری که همسایه اش نیست را دارد و یک پیغام تقاضای مسیر منتشر می کند. در مثال شکل ۶، گره ۱ قصد ارسال یک پیام برای گره ۳ را دارد. همسایه های گره ۱ گره های ۲ و ۴ هستند. از آنجایی که گره ۱ نمی تواند مستقیما با گره ۳ ارتباط برقرار کند، گره یک RREQ بیرون می فرستد. RREQ بوسیله گره های ۲ و ۴ شنیده می شود.

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

شکل ۶: گره ۱ قصد ارسال یک پیام برای گره ۳ را دارد

زمانی که همسایه های گره ۱ پیغام RREQ را دریافت کردند، آنها ۲ انتخاب دارند، اگر یکی از آنها مقصد هست یک پیغام باز پاسخ برای گره۱ بفرستد یا اگر آنها یک مسیر تا مقصد را می دانند، باید دوباره پیغام RREQ را برای گروه همسایه های خودشان منتشر کنند. اگر گره۱ ، یک پاسخ در یک مدت زمان تنظیم شده از آن زمان دریافت نکرد، آن دوباره سوال را با یک طول عمر طولانی تر و یک شماره ID جدید خواهد فرستاد. همه گره ها از شماره ترتیبی در RREQ برای ضمانت کردن اینکه یک RREQ را دوباره انتشار نمی دهند استفاده می کنند. در مثال شکل ۶ گره ۲ یک مسیر تا گره ۳ دارد و بوسیله فرستادن یک RRER به RREQ پاسخ می دهد، گره ی چهار از طرف دیگر مسیری تا گره ۳ ندارد بنابراین دوباره RREQ را منتشر می کند.

پیغام های خطا در پروتکل مسیریابی AODV :

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

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

شکل ۷: سه رویداد که تحت آن گره شاید یک پیغام RERR برای همسایه هایش منتشر کند

در قسمت ۲ گره، یک RERR که باعث می شود دست کم یکی از مسیرهایش ناتوان بشود دریافت می کند. اگر این اتفاق بیفتد، گره یک RERR شامل همه گره های که غیر قابل دسترس هستند بیرون می فرستد.

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


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

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

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

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

  2. تصویر آواتار کاربر 0
    احسان سه شنبه , ۳۰ آبان

    سلام من کد الگوریتمهای aodv و dsdv رو نیاز دارم با متلب ایا دارین

  3. تصویر آواتار کاربر 0
    حسین یکشنبه , ۲۰ خرداد

    سلام من میخواستم رو پایان نامه ام کار کنم نیاز به مطلب دارم موضوع پایان نامه ارائه الگوریتمی کارا بر اساس الگوریتم AODV در شبکه های موردی بی سیم هستش.