پروتکل های مسیریابی در WSNها (شبکه های سنسوری بی سیم)-(4) - پروتکل های مسیریابی مبتنی بر مکان

خوشه های ثابت انتخاب شده اند تا مساوی و مربع باشند. انتخاب اندازه ی مربع وابسته به انرژی انتقال و جهت ارتباط می باشد. اگر سیگنال فاصله a = r/22 را طی کند، انتخاب به گونه ای که بین دو سنسور در خوشه افقی و یا عمودی مجاور هم که بتوانند به طور مستقیم با هم ارتباط برقرار کنند ، وقوع یک ارتباط افقی و عمودی تضمین می شود. برای اینکه ارتباط مورب رخ دهد، سیگنال باید در فاصله ی b = r/2Ö2 گسترده شوند. بحث درباره نحوه قوانین زمانبندی گره ها است به صورتی که به عنوان سرخوشه ها عمل کنند است. یک لیدر می تواند از گره های سنسور در خوشه خودش بخواهد تا فعال شوند و در صورتی که یک شی را حس کردند شروع به جمع اوری داده کنند. سپس لیدر برای دریافت داده خام از دیگر گره ها در خوشه خودش و ارسال ان به ایستگاه اصلی مسئول است. نویسنده فرض می کند که گره های سنسور می توانند مکانشان را با استفاده از کارت های GPS بدانند که با تکنولوژی حاضر قابل تصور نیست.GAF سعی می کند تااتصال شبکه را با یک گره نماینده که همیشه در حالت فعال برای هر ناحیه در شبکه مجازی خودش است، حفظ کند. نتایج شبیه سازی نشان می دهد که GAF حداقل به خوبی یک پروتکل مسیریابی شبکه های موردی(AD-HOC) در مورد تاخیر و اتلاف بسته کار می کند و طول عمر شبکه را با ذخیره سازی انرژی افزایش می دهد. گرچه GAFیک پروتکل مبتنی بر مکان است، ممکن است به عنوان یک پروتکل سلسله مراتبی نیز مطرح شود که خوشه ها بر اساس مکان جغرافیایی باشند. برای هر ناحیه، یک گره نماینده به عنوان لیدر برای انتفال داده به گره های دیگر عمل می کند. گره لیدر، هیچ تراکم یا ترکیب را مثل دیگر پروتکل های مسیریابی سلسله مراتبی بحث شده انجام نمی دهند.
پروتکلGEAR (مسیریابی جغرافیایی و آگاه از انرژی)
این مسیریابی در مورد استفاه از اطلاعات جغرافیایی در حین انتشار پرس و جوها به نواحی مناسب است. پروتکل GEAR، با استفاده از اگاهی از انرژی و با اطلاع از انتخاب هوشمند همسایه از لحاظ جغرافیایی، عمل مسیر دهی یک بسته به ناحیه ی مقصد را انجام می دهد. هدف اصلی محدود کردن تعداد Interest ها در انتشار مستقیم فقط با توجه به یک ناحیه مشخص نسبت به ارسال Interest ها به همه شبکه است. با انجام این کار، GEAR می تواند انرژی بیشتری را نسبت به انتشار مستقیم ذخیره کند.
هر گره در GEAR هزینه براوردی و هزینه ی یادگیری رسیدن به مقصد از طریق همسایه هایش را نگهداری می کند. هزینه براوردی ترکیبی از انرژی باقیمانده و فاصله با مقصد است. هزینه یادگیری پالایش هزینه ی براوردی است که برای مسیریابی اطراف حفره های موجود در شبکه محاسبه می شود. یک حفره زمانی ایجاد می شود که یک گره هیچ همسایه نزدیکتر به ناحیه مقصد نسبت به خودش ندارد. اگر هیچ حفره ای نباشد هزینه براوردی برابر است با هزینه یادگیری. هزینه یادگیری یک گام به عقب منتشر می شود، در هر زمان یک بسته به مقصد می رسد به خاطر اینکه برپایی مسیر برای بسته بعدی تنظیم خواهد شد.
دو فاز در الگوریتم وجود دارد:
1. ارسال بسته ها به سمت ناحیه هدف: به محض دریافت یک بسته، یک گره همسایه هایش را بررسی میکند، اگر بیش از یک همسایه بود که نسبت به خودش به ناحیه هدف نزدیک تر بود متوجه می شود. اگر بیش از یک همسایه وجود داشت، نزدیک ترین همسایه به ناحیه هدف به عنوان گام بعدی انتخاب می شود. اگر همه انها فاصله شان نسبت به خود گره بیشتر است بدین معنی است که یک حفره در شبکه موجود است. در این حالت، یکی از همسایه ها برای ارسال بسته بر اساس تابع هزینه براوردی انتخاب می شود. سپس این انتخاب می تواند بر طبق هزینه یادگیریدر طول ارسال بسته ها انتخاب شود.
2. ارسال بسته ها داخل ناحیه: اگر بسته به ناحیه رسید، می تواند در ان ناحیه با ارسال جغرافیایی بازگشتی و یا سیل اسا به طور محدود شده، منتشر شود. سیل اسای محدود شده وقتی سنسورها به صورت متراکم گسترش یافته اند خوب است. در شبکه های با چگالی بالا، سیل اسای جغرافیایی بازگشتی بهره وری انرژی بیشتری نسبت به سیل اسای محدود شده دارد. در این حالت، ناحیه به چهار زیر ناحیه تقسیم شده و چهار کپی از بسته ایجاد می-شود. فرایند انشعاب (چند دسته ای شدن) و ارسال تا زمانی که ناحیه هایی فقط با یک گره ایجاد شود ادامه پیدا می کند.
GEAR با یک پروتکل غیر آگاه از انرژی( غیر EAR) مقایسه شده،GPSR ، که یکی از روش های قبل در مسیریابی جغرافیایی است و از گراف مسطح برای حل مشکل حفره استفاده کرد. در GPSR، بسته ها برای پیدا کردن مسیر خود گراف مسطح را دنبال می کنند. اگرچه GPSR تعداد حالات یک گره که باید حفظ کند را کاهش می دهد، برای شبکه های عمومی ویژه ی موبایل(تلفن همراه) طراحی شده است و نیاز به یک سرویس مکان یابی برای نقشه ی مکانی و شناسه ی گره دارد. GEAR نه تنها مصرف انرژی برای تنظیم را کاهش می دهد، بلکه از نظر تحویل(دلیوری) بسته بهتر از GPSR عمل می کند. نتایج شبیه سازی نشان می دهد که توزیع ترافیک متغییر، GEAR 70 الی 80 درصد از بسته ها را بیشتر از GPSR را تحویل می دهد. برای جفت ترافیک یکنواخت GEAR 25 الی 35 درصد بیشتر از GPSR بسته تحویل می دهد.
MFR ، DIR و GEDIR : این پروتکل ها فاصله عمومی، پیشرفت کار و روش مبتنی بر جهت را رسیدگی می کنند. مسئله ی اصلی جهت رو به جلو و رو به عقب آن است. گره ی مبدا و یا هر گره ی میانی توسط یکی از همسایگان خود با توجه به یک معیار خاص انتخاب می شوند. روشهای مسیریابی که متعلق به این دسته هستند، MFR(ارسال به اندازه ی شعاع)، GEDIR(مسیریابی فاصله جغرافیایی) که نوعی از الگوریتم های حریصانه است، روش حریصانه ی دوگامی، روش حریصانه ی متناوب و DIR(روش مسیریابی قطب نما) می باشند. GEDIR یک الگوریتم حریصانه است که همیشه بسته ها را به همسایه ی راس جاری که فاصله ی آن به مقصد حداقل است، حرکت می دهد. این الگوریتم زمانیکه بسته دو بار پی در پی از همان یال عبور کند شکست می خورد. در اغلب مواقع، MFR و روش های حریصانه مسیر یکسانی به مقصد دارند. در روش DIR، بهترین همسایه نزدیک ترین مسیر(مانند زاویه) به مقصد است. این است که همسایه با حداقل فاصله ی زاویه ای خط فرضی که به گره ی فعلی وصل است و مقصد انتخاب می شود. در MFR، بهترین همسایه ی A ضرب نقطه ای را به حداقل می رساند، که S گره ی مبدا و D گره ی مقصد می باشد. و نشان دهنده ی فاصله ی اقلیدسی بین دو گره ی S و D است. روش دیگر می توان به حداکثر رساندن ضرب نقطه ای باشد. هر روش ارسال پیام در یک گره را با بازگشت پیام به گره ی قبلی برای انتخاب بهترین مسیر متوقف می سازد. GEDIR و MFR حلقه آزاد هستند، در حالی که DIR ممکن است حلقه ایجاد کند مگر اینکه ترافیک گذشته حفظ شود و یا یک زمان مهر (time-stamp) اجرا شود. یک مطالعه ی مقایسه بین این الگوریتم ها نشان داد که این سه الگوریتم عمومی عملکرد قابل مقایسه ای از نظر نرخ تحویل و تاخیر متوسط دارد. علاوه براین، شبیه سازی نشان داد که گره ها در MFR و روش های حریصانه در بیش از 99 درصد از موارد همسایه ی ارسال مشابه ای انتخاب می کنند و تمام مسیرهای انتخاب شده در بیشتر موارد یکسان است.
GOAFR(مسیریابی صورت دیگر تطبیقی حریصانه ):
یک الگوریتم مسیریابی موردی(AD-HOC) هندسی مرکب ازمسیریابی حریصانه و صورت(Face) است. در حال حاضر ما به طور خلاصه نکات کلیدی از GOAFR را بررسی می کنیم. الگوریتم حریصانه ی GOAFR همیشه برای مسیریابی نزدیکترین همسایه ی یک گره را بر می گزیند تا بعدی باشد. با این وجود، به آسانی میتوان آن را در برخی از مینیمم محلی گیر انداخت(به عنوان مثال، هیچ همسایه به یک گره نزدیکتر ازگره ی فعلی نیست). OFR نوع دیگر FR است. الگوریتم FR اولین تضمین موفقیت است، اگر مبدا و مقصد به هم متصل باشد. اما، بدترین مورد هزینه ی FR با اندازه ی شبکه از نظر تعداد گره متناسب است. اولین الگوریتمی است که می تواند با بهترین مسیر در بدترین مورد AFR رقابت کند. علاوه براین، با یک استدلال ضعیف، AFR نشان داده که بدترین حالت مطلوب مجانبی است. اما AFR یک مورد کارا ی متوسط نیست. OFR از ساختار گرافهای مسطح بهره گیری می کند. به عنوان مثال، پیام از گره ی S به گره ی T با گردش در یک سری از مرزهای Face حرکت می کند. هدف این است که بهترین گره را با استفاده از سطوح هندسی در مرز پیدا کند (به عنوان مثال، نزدیک ترین گره به مقصد T). هنگامی که به پایان رسید، الگوریتم به S بهترین گره در مرز بر می گردد. الگوریتم ساده حریصانه در شبکه های متراکم به خوبی عمل می کند، اما برای بسیاری از پیکربندی(شکل) ساده با شکست مواجه می شود. در آن نشان داده شده است که GOAFR می تواند هم به بدترین حالت مطلوب و هم به کارایی متوسط دست یابد. بر اساس نتایج شبیه سازی GOAFR، راه های مختلفی برای بهبود بیشتر عملکرد حالت کارای متوسط وجود دارد. همچنین نسان داده شده که GOAFR بهتر از الگوریتم های برجسته ی دیگر مانند GPSR و AFR عمل کرد.
SPAN(محدوده): یکی دیگر از الگوریتم های مبتنی بر مکان به نام SPAN ، بعضی از گره را به عنوان تطبیق کننده بر اساس موقعیت خود انتخاب می کند. تطبیق کننده برای ارسال پیام از یک backbone (ستون فقرات) استفاده می کند. اگر دو همسایه ی یک گره ی غیر تطبیق کننده نتواند به طور مستقیم و یا از طریق یک یا دو تطبیق کننده (قابل دسترسی دوگامی) به یکدیگر برسند ، یک گره باید به تطبیق کننده تبدیل شود. تطبیق کننده ی جدید و موجود لزوما همسایه نیست، که بدلیل نیاز به حفظ موقعیت دو یا سه گامی همسایه در الگوریتم پیچیده ی SPAN ، باعث می شود کارایی انرژی طراحی را کمتر شود.

استفاده از مطالب این مقاله با ذکر منبع راسخون بلامانع می باشد.