مقاله روش جدید مسیر یابی با رویکرد چند مسیرگی در شبکه های MANET

بخشی از مقاله

چکیده -

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

کلید واژه- MANET، موازنه بار ،AOMDV ، DND-AOMDV

-1 مقدمه

شبکه موردی سیار - - MANET، شامل مجموعهای از گره-های موبایل است که هیچ کنترل متمرکزی ندارد و ممکن است توپولوژی پویا داشته باشد. بعلاوه، هر گره منابع محدودی همچون باتری، قدرت پردازش و حافظه. در شبکههای موردی سیار، گرههای سیار با روش چند پرشی با هم در ارتباطاند. به این معنا که یک گره سیار، بسته را با گذر از گرههای میانی به مقصد میفرستد. درواقع، وجود هر گره برای شبکه بهطور یکسان مهم است. در غیر این صورت، ممکن است بر عملکرد کلی شبکه تأثیر بگذارد. بنابراین، یک پروتکل مسیریابی مؤثر برای شبکه سیار موردی بسیار لازم است.[1] مسیریابی درواقع پیدا کردن مسیر بین دو گره مبدأ و مقصد طبق عوامل مشخص میباشد. در شبکههای موردی سیار که شبکههای نوظهوری هستند، روشهای زیادی برای مسیریابی توسط متخصصان شبکه ارائه شده است.

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

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

پروتکلهای مسیریابی چند راهه مسیرها را شناسایی می-کنند و میتوانند بیشتر از یک مسیر را به سمت مقصد انتخاب کنند. این پروتکلها برای انجام موازنه بار در شبکه بسیار مناسب هستند. ازجمله پروتکلهای مسیریابی چند راهه، پروتکل مسیریابی AOMDV است که نسخهی تغییر یافته و گسترش داده شدهی پروتکل مسیریابی AODV است.[3] در ادامه در مورد پروتکل AOMDV جزئیات بیشتری گفته خواهد شد. پروتکلهای مسیریابی چند راهه بیشتر برای شبکههای بزرگ با تعداد نودهای زیاد مورد استفاده قرار میگیرند و معمولاً برای شبکههای کوچک مناسب نیستند.[4] در این مقاله روش جدیدی پیشنهاد شده تا تأخیر ایجاد شده توسط AOMDV در شبکه را کاهش و گذردهی شبکه را افزایش دهد. اگرچه این روش پیشنهادی با استفاده از اطلاعات همسایگی در موقعیتی همچون تحرک زیاد گرهها و شکست مسیر عملکرد خوبی از خود نشان میدهد ولی در کاهش دادن سربار ایجاد شده در مسیریابی موفقیت چشمگیری به دست نیاورده است. در تحقیقات انجام شده در این مقاله نشان خواهیم داد که روش پیشنهادی عملکرد بهتری را در معیارهایی چون throughput و end-to-end delay داشته باشد.

-2 پروتکل مسیریابی AODV و AOMDV

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

AOMDV یک گسترش چند مسیری بر رویهی تک مسیری یعنی [6] AODV است. این الگوریتم بر پایه بردار-فاصله میباشد و از رویکرد مسیریابی پرش به پرش استفاده میکند. بعلاوه AOMDV با استفاده از فرایند کشف مسیر به روش برحسب تقاضا اقدام به پیدا کردن مسیر میکند. هدف از الگوریتم AOMDV توسعه AODV برای محاسبه مسیرهای مجزا و بدون حلقه، در یک فرآیند کشف مسیر است. مهمترین تفاوت AOMDV و AODV در تعداد مسیرهایی است که در هر فرایند کشف مسیر یافت میشود. در AOMDV با انتشار بسته RREQ از گره مبدأ به سمت گره مقصد، چندین مسیر معکوس در گرههای میانی و گره مقصد ایجاد میشوند. با بازگشت بستههای RREP چندگانه از طریق این مسیرهای معکوس، مسیرهای روبهجلوی چندگانه از گره مبدأ به سمت گره مقصد نیز ایجاد میشوند. باید توجه داشت که AOMDV با فراهم آوردن مسیرهای جایگزین در گرههای میانی، تکرار فرآیند کشف مسیر را کاهش داده است. برخلاف AODV، هر زمان که شکست لینک رخ داد، لازم نیست AOMDV کشف مسیر را دوباره آغاز کند بلکه از مسیر بعدی موجود در جدول مسیریابی خود برای ارسال بستههای داده استفاده میکند.

-3 مروری بر کارهای انجام شده

یکی از ویژگیها و مشخصات بارز MANETها [6] قابلیت تحرک همراه با محدوده متغیر انتقال، قابلیت پردازش متغیر و توانایی آنها در پیوستن به شبکه و ترک آن بهطور دلخواه است. در چنین موقعیتهایی، وظیفهی یک روش مسیریابی تحویل موفق و مؤثر بستههای داده از مبدأ به مقصد است که بدون حضور توپولوژی شناختهشده و وجود یک گره کنترل-کننده مرکزی بر پیچیدگی آن افزوده میشود. پروتکلهای AODV و AOMDV از جمله روشهایی هستند که برای این نوع شبکهها بسیار مورد استفاده قرار میگیرند.

هنگامیکه تعداد گرههای موجود در شبکه که هرکدام دارای حرکت هستند، و یا سرعت حرکت گرههای موجود در شبکه، افزایش یابد، پروتکلهای مسیریابی AODV و AOMDV، کارایی قبلی خود را نخواهند داشت و نمیتوانند از پس این افزایش پیچیدگی شبکه برآیند. بنابراین نیاز به یک روش مسیریابی داریم تا در موقعیتهایی چون افزایش تعداد گرهها در شبکه و همچنین در سرعتهای بالای گرهها، دچار خطای کمتری شده و بستههای داده را بهطور مطمئن به مقصد مورد نظر برساند. بهاینترتیب کارایی کلی شبکه در این شرایط حفظ خواهد شد. روشهای زیادی برای بهبود مسیریابی در شبکه پیشنهاد شدند مانند روش مسیریابی [7] AODV- AP که نویسندگان در آن تلاش کردند تا سربار را، با پروتکل مسیریابی و لایه MAC، کاهش دهند. در این مقاله پیشنهاد شد که سربار می-تواند بهشدت کاهش پیدا کند اگر گرهها از موقعیت مکانی و حرکت یکدیگر آگاه شوند. نویسندگان این مقاله تلاش کردند تا کارایی AODV را با استفاده از اطلاعات مکانی افزایش دهند.

AODV - [9] [8] AODV-ABR با مسیریابی پویای پشتیبان - یک روش مسیریابی بر اساس پروتکل مسیریابی AODV است. این روش از پیامهای RREP در AODV برای ایجاد یک ساختار مش استفاده میکند و چندین مسیر بعدی را پیشنهاد میدهد. نویسندگان در >7@ >10@ NDMR تلاش میکنند تا پروتکل AODV را با استفاده از ویژگی انباشتگی مسیر موجود در DSR گسترش دهند بهطوریکه تمام مسیر برای کاهش سربار در RREQ انباشته میشود. هرگاه یک گره بستهای را در NDMR دریافت میکند، انباشتگی مسیر آن را در RREQ بررسی میکند و سپس تعداد پرشها از منبع به خودش را محاسبه میکند و سرانجام تعداد را به عنوان کمترین تعداد پرش در جدول ورودی مسیر برگشت خود ثبت میکند. در [11] تلاش شده تا با توسعهی پروتکل مسیریابی AODV، گذردهی شبکه افزایش یابد. در این مقاله با بهرهگیری از معیار تعداد همسایههادر گرهها، از پخش سیلآسای پیام درخواست مسیر RREQ جلوگیری شده که در نهایت سبب افزایش عملکرد مسیریابی در شبکه شده است.

-4 روش پیشنهادی

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

در این مقاله برای جلوگیری از قرار گرفتن این نوع گرهها در انتخاب مسیر از مبدأ به مقصد که باعث به وجود آمدن ازدحام در شبکه میشوند، الگوریتمی ارائه شده است که با در نظر گرفتن همسایه های هر گره، گرههایی را در مرحلهی کشف مسیر انتخاب میکند که از نظر چگالی همسایهها در مناطق خلوتتر شبکه قرار دارند. این پروتکل پیشنهادی، پروتکل AOMDV مبتنی بر چگالی پویای همسایهها نام دارد که به اختصار Dynamic Neighbor-Density - DND-AOMDV - AOMDV معرفی شده است. در این روش پیشنهادی، چگالی همسایگی یک گره میانی به عنوان معیاری برای تصمیم گیری در ارسال RREQ در گره میانی در نظر گرفته شده است. به این معنی که، اگر تعداد گرههای موجود در همسایگی زیاد باشد، احتمال اینکه هر گره بخواهد انتقالی داشته باشد کاهش مییابد.

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

1.    اگر   باشد سپس پیام RREQ ارسال شود.

2.    اگر   نباشد سپس احتمال ارسال پیام RREQ برای گره iام یا  که  نام دارد محاسبه میشود.

3.    در این مرحله   که عدد تصادفی با توزیع یکنواخت بین صفر و یک است تولید میشود.

4.    برای    احتمال   به صورت زیر محاسبه میشود:

5.    در این مرحله R که عددی تصادفی با توزیع یکنواخت بین صفر و یک است تولید میشود.

6.    اگر   باشد سپس پیام RREQ ارسال شود.

7.    اگر   نباشد سپس از بسته چشم پوشی شده و بسته دور انداخته شود.