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

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

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

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

تصویر dsr-routing-protocol-in-mobile-ad-hoc-networks_581 پروتكل مسیریابی DSR در شبکه های ادهاک موبایل

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

پروتكل مسیریابی DSR یا Dynamic Source Routing (مسیریابی منبع پویا) به كلاس پروتكل‌ های مبتنی بر درخواست نیز تعلق داشته و در شبکه های ادهاک مورد استفاده قرار می گیرد.

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

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

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

دو مدل اصلی كاربری تحت پروتكل مسیریابی DSR عبارتند:

1- كشف مسیر پروتكل DSR

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

كشف مسیر مكانیزمی است كه به وسیله آن یك گره به نام S كه می‌خواهد بسته‌ای را به یك مقصد به نام D بفرستد، یك مسیر مرجع را به D دریافت می‌دارد. برای برقراری یك مسیر مرجع S یك درخواست مسیریابی PREQ را به همراه یك ID منحصر به فرد درخواست همه پخش می‌كند كه ممكن است به وسیله میزبان هایش در یك رنج انتقال بی‌سیم دریافت شود.

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

ثبت شماره ترتیبی در هر گره به این منظور می باشد كه اگر بسته مشابه دیگری دریافت شد، آن را به عنوان یك نسخه كپی محسوب كرده و از ارسال آن جلوگیری كند، در ضمن این گره ها شماره گام را هم ذخیره می كنند تا از آن در مسیر برگشت و ارسال پاسخ مقصد به مبدأ استفاده كنند. وقتی كه یك گره یك بسته درخواست مسیر را دریافت كند براساس مراحل ذیل درخواست را مورد پردازش قرار می‌دهد.

1- اگر هر جفت آنها (آدرس آغازگر و ID درخواست) برای این درخواست مسیر در لیست میزبانانی كه اخیراً درخواست‌های دریافت داشته‌اند، وجود داشته باشد، در این صورت، این بسته درخواست مورد پردازش قرار نگرفته و دور انداخته می‌شود.

2- اگر آدرس میزبان ها در بخش ثبت مسیر آن پیام درخواست، وجود داشته باشد، پردازش نمی‌شود و دور انداخته می‌شود.

3- اگر غیر از موارد بالا باشد و اگر گره، همان هدف موردنظر باشد، ثبت مسیر كامل شده و پاسخ مسیر ارسال می‌شود.

4- در غیر اینصورت گره به ثبت مسیر موجود در بسته درخواست مسیر، ضمیمه شده و دوباره همه پخش می‌شود. در شكل 1 نمونه ای از این كشف مسیر آورده شده است.

تصویر dsr-routing-protocol-in-mobile-ad-hoc-networks_581_1 پروتكل مسیریابی DSR در شبکه های ادهاک موبایل

شكل 1 : نمونه ای از كشف مسیر در پروتكل DSR

2- نگهداری مسیر پروتكل DSR

بخش دوم یعنی نگهداری مسیر پس از كشف مسیر آغاز می شود. در خلال این بخش، همه اطلاعات ارسالی از طریق مسیرهای كشف شده قبلی به مقاصد خود فرستاده می شود. در واقع نگهداری مسیر مكانیزمی است كه به وسیله آن یك ارسال‌كننده بسته (s)، تشخیص می‌دهد كه آیا توپولوژی شبكه طوری تغییر كرده است كه دیگر نمی‌تواند از آن مسیر به سمت مقصد D استفاده كند.

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

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

روش های بهینه‌ سازی الگوریتم DSR

استفاده كامل از مسیر پنهان

یكی از این روش‌ های بهینه‌ سازی استفاده كامل از مسیر پنهان است، داده‌های موجود در هر گره میزبان ممكن است به هر ترتیبی ذخیره شده باشند ولی در مسیرهای فعال هر مسیر دارای درختی از مسیرهاست كه از خود آن ریشه می‌گیرد.

یك host هنگامی كه به وجود یك مسیر جدید پی برد می‌تواند به معلومات خود، در حافظه پنهان مسیر خود، اضافه كند. اگر یك host داده دریافتی را به host های دیگر بفرستد این host منتظر دریافت داده‌های مسیر كامل داده تا مقصد می‌ماند.

اگر یك host این مسیر را به host موردنظر برگرداند، این host مسیر را به گره‌های قبلی اطلاع می‌دهد و در نتیجه آن گره‌ها مسیر را در حافظه پنهان خود اضافه می‌كنند، بنابراین همه اطلاعات مسیرهای شبكه به صورت ذاتی همه پخش می‌شوند.

بازتاب مسیرهای كوتاهتر

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

اداره ‌كردن تكه‌ های مختلف شبكه

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

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

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

 

ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

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