بخشی از مقاله
خلاصه
در شبکههای تحملپذیرتأخیر، بخشهای مختلف مسیر بین مبدأ و مقصد پیام، در طول زمان تشکیل شده و در اغلب موارد هنگامی که یک بخش از مسیر تکمیل میگردد، بخشهای قبلی کاملا شکسته و قطع شدهاند، لذا استفاده از الگوریتمهای مسیریابی سنتی که به وجود یک مسیر انتها به انتها بین مبدأ و مقصد وابسته هستند، برای ما امکانپذیر نخواهد بود. در این مقاله، یک روش مسیریابی گروه محور ارائه گردیده که با استفاده از اطلاعاتی که به سادگی در دسترس هستند و با تکیه بر تناوب تکرار رویاروئیها به مسیریابی بهینه پیامها در شبکه میپردازد.
شبیه سازیها نشان دادند که الگوریتم پیشنهادی در محیطهایی که تعداد گرهها در مقایسه با برد مخابراتی آنها زیاد است، از تمامی الگوریتمهای تک کپی رقیب که در مقایسه حضور داشتند، بهتر عمل مینماید. گرچه الگوریتم پیشنهادی ثابت نمود که در تمامی شرایط، احتمال تحویل پیام در آن، بیش از روشهای تک کپی دیگر است، اما از آنجایی که موفقیت چشمگیر الگوریتم، علاوه بر ایده خوبی که در آن به کار رفته است، به خرج محاسبات و حافظه بوده است، لذا استفاده از آن در محیطهای خلوت و یا در شبکههایی که ظهور و حذف گرهها با سرعت زیادی انجام میشود، پیشنهاد نمیگردد.
.1 مقدمه
شبکههای تحملپذیر تأخیر، یکی از الگوهای مخابراتی رو به رشد در شبکههای متحرک بیسیم هستند. آنها معمولا به عنوان شبکههای متحرکی تعریف میشوند که توزیع جغرافیایی گرهها در آن تنک بوده و ارتباطات از طریق دست به دست نمودن اطلاعات، زمانی که دو گره در برد میدان الکترومغناطیسی یکدیگر قرار میگیرند، انجام میشوند. در چند سال اخیر، روشهای گوناگونی برای مسیریابی در اینگونه شبکهها پیشنهاد شده است.
الگوریتمهای موجود، هر یک به نحوی سعی در بهبود پارامترهای مسیریابی مانند تأخیر پیام، نرخ تحویل، هزینه ارسال، مصرف بافر و... داشتهاند اما در اغلب آنها یا به دلیل انتخاب معیارهای ساده، با تأخیر زیاد و نسبت تحویل کم مواجه میشویم ویا بواسطه داشتن احتیاج به اطلاعات زیاد در مسیریابی، دچار سربار زیاد در شبکه و محدودیت در پیاده سازی آنها میگردیم. در این مقاله الگوریتمی به نام "مسیریاب تخمینگر تناوب" ارائه میگردد که تلاش دارد تا مسیریابی بهینهای را به کمک اطلاعاتی که به سادگی در دسترس هستند انجام دهد و مسائل مطرح شده در بالا را حل و یا تأثیر منفی آنها را حتیالامکان کاهش دهد. الگوریتم مسیریابی پیشنهادی، از دو مرحله تشکیل شده است :مرحله اول شامل تشکیل ماتریس مجاورت - گراف رویارویی - و گروهبندی گرهها در آن و مرحله دوم، مربوط به انجام مسیریابی بهینه برای انتخاب گره حامل بعدی میباشد.[1]
.2 کارهای پیشین
تحقیقات زیادی به منظور ارائه مسیریابی مناسب در شبکهها، با توجه به رفتار متناوب گره و لینک، انجام گرفته است. نتیجه این تحقیقات ارائه تعداد زیادی راه حل است که به حل مشکلات مربوط به مسیریابی در سناریوهای خاص کمک میکنند. روشهای مسیریابی در شبکههای تحملپذیر تأخیر بر اساس معیارهای مختلف قابل دستهبندی هستند، به طور عمده این گروهبندیها بر اساس محتوا و تعداد کپیها صورت میگیرد. روشهای مسیریابی، بر اساس معیار محتوا در سه گروه زیر طبقهبندی میشوند:
- روشهای بیخبر از محتوا: پروتکلهای مسیریابی موجود در مجموعه روشهای بیخبر از محتوا از شیوه مبتنی بر سیلآسا برای مسیریابی پیامها استفاده میکنند. در این شیوه، مبدأ پیام را به همه لینکهای خروجی خود میفرستد و هر گرهای که آن را دریافت میکند، دوباره آن را به همه لینکهای خروجی خود، بجز لینکی که پیام را از آن دریافت کرده است، میفرستد. به این ترتیب، هر پیام ممکن است از مسیرهای متفاوت و در زمانهای مختلف به مقصد برسد. مزیت شیوه مبتنی بر سیلآسا این است که پیدا کردن مسیر در آن به سهولت انجام میشود و به همین دلیل بهترین کارایی را در انتقال انتها به انتها دارند. با این وجود انتشار سیلآسا باعث ایجاد تعداد بسیار زیادی پیام در کانالهای ارتباطی میشود که خود دلیلی برای ایجاد ازدحام در شبکه است.
- روشهای مبتنی بر جابجایی : پروتکلهای مسیریابی موجود در مجموعه روشهای مبتنی بر جابجایی از برخی اطلاعات محتوای گرهها شامل الگوی حرکتی گرهها و پیشینه اتصال آنها و ... برای تصمیمگیری در مورد ارسال داده استفاده میکنند. جابجایی گرهها روی کارایی مسیریابی پیامها در شبکههای فرصت طلبانه تأثیر بسزایی دارد.
- روشهای مبتنی بر محتوا : تفاوت اصلی میان روشهای مبتنی بر جابجایی و روشهای مبتنی بر محتوا این است که در روشهای مبتنی بر جابجایی، اطلاعات محتوا درباره الگوی جابجایی گرهها در شبکه، اطلاعاتی درباره خود گرهها یا پیشینه برخوردهای میان آنها، از ابتدای شروع به کار شبکه است. در حالی که در روشهای مبتنی بر محتوا فقط از اینگونه اطلاعات استفاده نمیشود، بلکه جنبه اجتماعی گرهها را نیز بهعنوان عامل مهمی در مسیریابی پیامها، مورد توجه قرار میدهند. توجه به جنبه اجتماعی گرهها به این علت است که در بسیاری از موارد جابجایی گرهها به علت تصمیمگیری حامل آن است. بنابراین روابط اجتماعی حاملها، نقش مهمی در چگونگی برخورد آنها با هم بازی میکند.
مزیت این مجموعه روشها در این است که از مجموعه روشهای مبتنی بر جابجایی کلیتر هستند و در نتیجه با هر مجموعه از اطلاعات محتوا میتوان از آنها بهره برد و به آسانی میتوان بهترین اطلاعات محتوا را برای مسیریابی در هر محیط و شرایط خاص انتخاب نمود .[2] چگونگی پذیرش مقاله به اطلاع مولف رابط خواهد رسید. با اینحال آخرین وضعیت مقالات در هر لحظه از طریق تارنمای کنفرانس قابل پیگیری میباشد. در صورت پذیرش، لازم است مولفین مقاله، اصلاحات خواسته شده داوران را در نسخه نهایی و در مدت زمان خواسته شده اعمال نموده و نسخه نهایی را از طریق تارنمای کنفرانس ارسال نمایند. از دیدگاهی دیگر که بر مبنای تعداد کپیها در شبکه صورت میگیرد به سه دسته تقسیم م شوند:[3]
- روشهای تک کپی: که به بهبود استفاده از منابع شبکه کمک میکنند .[4]
- روشهای اپیدمیک: که به افزایشاحتمال تحویل پیام کمک میکنند.[5]
- روشهای احتمالگرا: که به یافتن یک توازن بهینه، بین دو دسته قبلی کمک میکنند.[6]
.3 الگوریتم پیشنهادی
بهتر است به جای اینکه هر لبه فقط با یک عدد مشخص گردد، یک بردار به آن اختصاص داده شود. در هر درایه بردار، تعداد، تاریخ -زمان، میانگین و واریانس دیدار آن دو گره ثبت میگردد. بنابراین با بررسی هر بردار میتوان به روندی از رویاروییهای دو گره در یک دوره تناوب که ممکن است ساعتی، روزانه، ماهانه و حتی سالانه باشد- رسید. هرگاه دو گره در مجاورت هم قرار میگیرند، شروع به داد و ستد این گراف مینمایند.
هر گره با دریافت این گراف، شروع به بهروزرسانی دادههای گراف خود مینماید. با توجه به اینکه رویاروییها، به صورت تاریخ-زمان ثبت شدهاند، به روزرسانی گرافهای ذخیرهشده از روی گرافهای دریافتی، کار سادهای خواهد بود. با بررسی این بردار میتوان به معیارهای متنوعی جهت تصمیمگیری پیرامون انتخاب گرههای تکرارکننده، دست یافت. مثلا با بررسی تاریخ -زمانها، تناوب دیدارها مشخص خواهد شد؛ یا با شمارش رویاروییها، احتمال رویارویی یک گره با گره مقصد، تخمین زده میشود.
.1,3 پیچیدگی محاسباتی و حجم حافظه مورد نیاز
در بررسی پیچیدگی هر الگوریتم، دو عامل مورد توجه قرار میگیرد. اول اینکه میزان حافظه مورد نیاز، برای نگهداری اطلاعات لازم برای پردازش چقدر است و دوم اینکه برای تصمیمگیری یا تولید خروجیها، چقدر محاسبات ریاضیاتی نیاز خواهد بود. اگر یک شبکه با مجموعهی n گره در نظر گرفته شود و با فرض اینکه تمامی گرهها از احوال هم مطلع باشند، آنگاه نیاز است که گراف رویارویی G در حافظه هر گره نگهداری شود.
در بدترین حالت، تمامی درایههای ماتریس مجاورت گراف G دارای اطلاعات هستند، به بیان دیگر، تمامی گرهها حداقل یک بار با یکدیگر دیدار کردهاند یا میکنند. در این صورت برای نگهداری گراف G نیاز به n2 ساختار داده خواهد بود که هر ساختار داده نیز حاوی اطلاعات لازم برای تحلیلهای مورد نیاز خواهد بود. در ادامه با بررسی مفروضات و محاسبات لازم بر روی دادههای الگوریتم، به تشریح ساختارهای داده مورد نیاز پرداخته میشود.
