پروتکل های مسیریابی در WSNها (شبکه های سنسوری بی سیم)-(4) - پروتکل های مسیریابی مبتنی بر مکان
در این نوع مسیریابی گره های سنسور به وسیله مکانشان ادرس دهی شده اند. فاصله بین گره های همسایه می تواند بر اساس شدت سیگنال های ورودی تخمین زده شود. هماهنگی نسبی گره های همسایه می تواند با تبادل این قبیل
مترجم: حبیب الله علیخانی
منبع:راسخون
منبع:راسخون
ساختار شبکه های اساسی می تواند نقش مهمی در عملیات پروتکل مسیر یابی در WSN را ایفا کند. در این بخش ما جزئیات بسیاری از پروتکل هایی که در این دسته قرار می گیرند را بررسی می کنیم.
پروتکل های مسیریابی بر اساس ساختار شبکه در زیر به سه دسته تقسیم شده :
1. مسیریابی مسطح یا یکدست(flat-based)
2. مسیریابی سلسله مراتبی (hierarchical-based)
در این نوع مسیریابی گره های سنسور به وسیله مکانشان ادرس دهی شده اند. فاصله بین گره های همسایه می تواند بر اساس شدت سیگنال های ورودی تخمین زده شود. هماهنگی نسبی گره های همسایه می تواند با تبادل این قبیل اطلاعات بین همسایه ها به دست اید. متناوبا، مکان گره ها ممکن است به طور مستقیم با ارتباط با یک ماهواره با استفاده از GPS، در صورتی که گره ها به یک دریافت کننده GPSکم مصرف مجهز شده باشند در دسترس باشد. برای ذخیره انرژی، بعضی از طرح های مبتنی بر مکان-یابی می خواهند که گره ها در صورتی که فعالیتی ندارند به خواب روند. ذخیره سازی انرژی بیشتر می تواند با گره های خوابیده بیشتر در شبکه تا حد ممکن به دست اید . مشکل طراحی زمانبندی پریود خواب برای هر گره در روش مبتنی بر مکان آدرس دهی شده است. در ادامه ی این بخش، ما بسیاری پروتکل های مسیریابی مبتنی بر مکان یا جغرافیایی را بررسی می کنیم.
GAF یک الگوریتم مسیریابی اگاه از انرژی و متنی بر مکان است که در اصل برای شبکه های موردی(AD-HOC) موبایل(تلفن همراه) طراحی شده است، ولی برای شبکه های سنسور هم به خوبی قابل کاربرد است. ناحیه شبکه در ابتدا به نواحی ثابت تقسیم می شود و به صورت شبکه مجازی در می اید. داخل هر ناحیه، گره ها با هم برای انجام کارهای مختلف همکاری می کنند. برای مثال، گره ها یک سنسور را برای بیدار ماندن برای یک دوره مشخص از زمان انتخاب می کنند و سپس انها به خواب می روند. این گره مسئول نظارت و گزارش داده به ایستگاه اصلی از طرف گره های موجود در ناحیه خواهد بود. از این رو با خاموش کردن گره های غیرضروری در شبکه بدون اینکه روی میزان صحت مسیریابی تاثیر بگذارد میزان مصرف انرژی را کاهش می دهند. هر گره از GPS نشان دهنده مکان خودش برای اینکه خودش را به یک نقطه در شبکه مجازی ارتباط دهد استفاده می کند. گره های مرتبط با همان نقطه در شبکه در هزینه مسیریابی بسته معادل فرض شده اند. پروتکلGAF در واقع می تواند طول عمر شبکه را افزایش دهد، در نتیجه تعداد گره ها افزایش می یابد. این هم ارزی در نگهداشتن برخی از گره های واقع در منطقه ی خاصی از شبکه در وضعیت خواب(به منظور صرفه جویی) انرژی بهره برداری شده است. سه حالت در GAF تعریف شده است.اکتشافی(Discovery)، برای تعیین همسایه ها در شبکه؛ فعال(active)، بازتاب مشارکت در مسیریابی؛ خواب(sleep)، زمانیکه رادیو خاموش است؛ برای متحرک بودن، هر گره در شبکه زمان خروج از شبکه را برآورد می کند و آن را به همسایه اش ارسال کند. همسایه های خوابیده زمان خوابشان را برای صحت مسیریابی به صورت دقیق تنظیم می کنند. قبل از اینکه زمان خروج گره های فعال به اتمام رسد، گره های خوابیده بیدار شده و یکی از انها فعال می شود.GAF هم برای گره های غیرمتحرک (GAF اولیه) و هم برای گره های متحرک (GAF سازگار با تحرک) پیاده سازی شده است. تصویر زیر نمونه ای از منطقه بندی ثابت را نشان می دهد که می تواند در شبکه های سنسوری استفاده شود.
این مسیریابی در مورد استفاه از اطلاعات جغرافیایی در حین انتشار پرس و جوها به نواحی مناسب است. پروتکل 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 درصد از موارد همسایه ی ارسال مشابه ای انتخاب می کنند و تمام مسیرهای انتخاب شده در بیشتر موارد یکسان است.
یک الگوریتم مسیریابی موردی(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 ، باعث می شود کارایی انرژی طراحی را کمتر شود.
/ج
تازه های مقالات
ارسال نظر
در ارسال نظر شما خطایی رخ داده است
کاربر گرامی، ضمن تشکر از شما نظر شما با موفقیت ثبت گردید. و پس از تائید در فهرست نظرات نمایش داده می شود
نام :
ایمیل :
نظرات کاربران
{{Fullname}} {{Creationdate}}
{{Body}}