در اغلب مطالعات انجامشده، فرض بر این است که همه گرههای حسگر همگون باشند. به عبارت دیگر، گرههای همگون بایستی ظرفیت یکسانی از لحاظ انجام عملیات محاسباتی، مخابراتی و نیز از لحاظ توان داشته باشند. اما، بسته به کاربرد، گرههای حسگر میتوانند نقشها و یا قابلیتهای متفاوتی داشته باشند. وجود یک مجموعه ناهمگون از حسگرها، ممکن است منجر به تعداد زیادی وجوه فنی مرتبط با مسیریابی داده شود [۱، ۱۰].
برخی از گرهها حسگر ممکن است به علت فقدان توان، صدمات فیزیکی و یا تداخل محیطی دچار خرابی و نقص شوند. یکی از نکاتی که باید در طراحی الگوریتمهای مسیریابی باید توجه کرد آن است که خرابی گرههای حسگر، نباید عملکرد کلی شبکه حسگر را تحت تاثیر قرار دهد]۱۰[. اگر تعداد زیادی از گرهها دچار خرابی و نقص شوند، پروتکلهای مسیریابی بایستی آرایش جدیدی از اتصالات و مسیرها را برای جمعآوری داده از ایستگاههای پایه برای تطبیق یافتن با این مشکلات بسازند که این امر ممکن است نیازمند آن باشد تا به صورت فعالانه، توانهای انتقال و نرخهای سیگنال بر روی اتصالات موجود تنظیم شوند، تا بتوان مصرف انرژی را کاهش داده و یا بستهها را مجدداً از طریق نواحی از شبکه که انرژی بیشتری در آنجا وجود دارد، مسیردهی کرد. بنابراین سطوح مختلفی از افزونگی ممکن است در یک شبکه حسگر که خطا را تحمل میکند، نیاز باشد]۱۲[.
تعداد گرههای حسگری که در یک منطقه آرایش یافتهاند ممکن است بسیار زیاد باشند. انواع طرحهای مسیریابی بایستی قادر به کار کردن با هر تعداد گره حسگر باشند. بهعلاوه، پروتکلهای مسیریابی شبکههای حسگر بایستی به اندازه کافی قابلیت تغییر مقیاس را داشته باشند تا بتوانند به وقایعی که در آن محیطها رخ میدهند، پاسخ دهند. البته تا زمانی که یک واقعه اتفاق بیفتد، اغلب حسگرها میتوانند در حالت خواب باقی بمانند ]۱۲٫[
اغلب ساختارهای شبکه فرض میکنند که گرههای حسگر ایستا میباشند. اما بههرحال گاهی در برخی کاربردها، حرکت گرههای حسگر و یا ایستگاههای پایه، ممکن است لازم باشند. مسیردهی بستهها به گرههایی که در حال حرکت میباشند بسیار چالشبرانگیزتر است. همچنین پدیده و یا حادثهای که حس شده برحسب کاربرد میتواند هم پویا و همایستا باشد. وقایع پویا در اغلب کاربردها نیاز به گزارشدهی متناوب دارند و در نتیجه، ترافیک مشخصی را برای مسیردهی شدن به طرف ایستگاه پایه برقرار میکنند. در شبکههای پویا علاوه بر پهنای باند و مصرف انرژی، پایداری مسیرها از مسائلی است که حتماً باید مورد توجه قرار گیرد ]۱۳[.
تراکم بالای گرهها در شبکههای حسگر بیسیم، از ایزوله شدن گرهها از یکدیگر به صورت کامل، جلوگیری میکند. بنابراین انتظار میرود که گرههای حسگر، شدیداً به هم متصل باشند و یا به عبارت بهتر شدیداً با هم در ارتباط باشند. اما بههرحال این امر، توپولوژی شبکه را از متغیر بودن حفظ نمیکند و نیز اندازه شبکه را از جمعشدگی و کوچک شدن به علت اشتباهات گرههای حسگر، حفظ نخواهد کرد]۱۲[.
در اینگونه شبکهها، هر گره حسگر داخل شبکه یک دید خاص از محیط به دست میآورد. این دیدی که هر گره حسگر از محیط اطرافش به دست میآورد هم از لحاظ دقت و هم از لحاظ محدوده تحت پوشش، محدود است. به عبارت بهتر، هر گره حسگر میتواند یک منطقه فیزیکی محدودی از محیط اطرافش را پوشش دهد. بنابراین پوشش کل منطقه مورد نظر، به وسیله گرههای حسگر، یک مسئله بسیار مهم در طراحی شبکههای حسگر بیسیم است]۱۰[.
برای دانلود متن کامل پایان نامه به سایت azarim.ir مراجعه نمایید. |
انواع مسیریابی در شبکههای حسگر بیسیم
پروتکلهای مسیریابی ارائهشده برای شبکههای حسگر با در نظر گرفتن مواردی همانند محدودیت محاسباتی و انرژی گرهها، گمشدن بستهها در اثر خطاهای به وجود آمده در شبکه و میزان تأخیر ارسال بستهها صورت میگیرد. به طور کلی پروتکلهای ارائهشده را با توجه به ساختار شبکه می توان به سه دسته همسطح، سلسله مراتبی و مبتنی بر موقعیت تقسیمبندی نمود]۱۲[. در پروتکلهای مسیریابی ساختار مسطح، همه گرههای موجود در شبکه نقش یکسانی را ایفا میکنند. از مزایای اینگونه شبکهها می توان به مواردی همانند سربار کم و افزایش قابلیت تحملپذیری در برابر خطا اشاره کرد]۱۴[. دسته دوم، از معروفترین و بهترین روشهایی است که به منظور مسیریابی دادهها در شبکههای حسگر بیسیم پیشنهاد شد. در این روشها، ابتدا همه گرههای داخل شبکه بر اساس روشی خاص خوشهبندی میشوند. در هر خوشه یک گره به عنوان سرگروه انتخاب میشود که برای انتخاب آن در هر روش، معیارهای متفاوتی در نظر گرفته میشود. در اکثر روشهای مبتنی بر خوشه هدف آن است که توزیع مصرف انرژی بین همه گرهها یکنواخت گردد]۱۵[. در دسته سوم، پروتکلهای مسیریابی مبتنی بر موقعیت، در این نوع گرههای موجود در شبکه دارای اطلاعاتی از مکان خود میباشند. که با استفاده از این اطلاعات راهکارهای مؤثری در مسیریابی ارائهشده است که سبب کاهش چشمگیر مصرف انرژی شد]۱۲[.
از سوی دیگر پروتکلهای مسیریابی را میتوان به ۵ دسته مبتنی بر چندمسیره[۱۸]، مبتنی بر پرسوجو[۱۹]، مبتنی بر مذاکره[۲۰]، مبتنی بر کیفیت سرویسدهی[۲۱] و مبتنی بر همسانی[۲۲] تقسیمبندی نمود. همچنین در تقسیمبندی دیگر پروتکلهای مسیریابی را از نظر اینکه مبدأ به چه نحوی مسیر به مقصد را پیدا میکند، میتوان به سه دسته تحت نامهای پروتکلهای واکنشی[۲۳]، غیر واکنشی[۲۴] و ترکیبی[۲۵] تقسیمبندی نمود]۱۲[. در پروتکلهای واکنشی مسیر تنها زمانی کشف میشود که مبدأ اقدام به برقراری ارتباط با گره دیگری بکند. در مقابل در پروتکلهای کنش گرا، همه مسیرهای ممکن پیش از آنکه نیاز باشند کشف خواهند شد. در روش ترکیبی، جهت بهرهمندی از مزایای دو ساختار قبلی از هر دو روش استفاده میشود. همچنین در دهههای اخیر الگوریتمهایی تحت عنوان الگوریتمهای فراابتکاری و الگوریتمهایی بر اساس نظریه بازیها در زمینه مسیریابی ارائهشدهاند که در ادامه به تعدادی از آنها اشاره میکنیم ]۱۰، ۱۶٫[
ساختار شبکه و چگونگی گسترش گرههای حسگر در فضای شبکه از مهمترین عوامل تأثیرگذار در طراحی پروتکلهای مسیریابی شبکههای حسگر میباشند. در ادامه به توضیح دستهبندی ارائهشده در این زمینه و برخی از پروتکلهای ارائهشده خواهیم پرداخت.
در این نوع مسیریابی، تمام گرههای حسگر از لحاظ وظایف و کارکرد یکسان میباشند و هیچکدام دارای وظیفه متفاوتی نسبت به سایرین نمیباشند. معمولاً در این نوع الگوریتمها، از یکی از دو روش زیر جهت مسیریابی استفاده میگردد]۱۲[:
درخواست از طرف حسگرها؛ در این حالت حسگرها، اطلاعات خود را در شبکه پخش میکنند و منتظر درخواست از طرف دریافتکننده میمانند.
درخواست از طرف دریافتکننده اطلاعات؛ در این حالت دریافتکننده اطلاعات، درخواست خود را در شبکه پخش میکند و منتظر جواب میماند.
در ادامه برخی از پروتکلهای ارائهشده در این زمینه را مورد بررسی قرار خواهیم داد.
پروتکل [۲۶] SPIN :
SPIN از خانواده پروتکلهای دادهگرای مبتنی بر مذاکره در شبکههای حسگر بیسیم میباشد. هدف اصلی، انتشار کارای مشاهدات جمعآوری شده توسط حسگرها به سایر گرههای حسگر دیگر در شبکه میباشد. اصل مهم در این خانواده از پروتکلها، مذاکره بر سر داده و وفق پذیری با منابع شبکه است]۱۴،۱۷[. مذاکره بر سر داده یعنی اینکه گرهها محتوای داده را بررسی کرده و یک تم جدید به نام فراداده[۲۷]، دربارهی دادهها تشکیل میدهند که توصیفی از دادهای است که قرار است ارسال شود. گرهها میتوانند دادههای خود را از طریق دسترسی به فراداده انتخاب بکنند و آن را آگهی کنند و بدین ترتیب دادهها فقط به گرههایی که نیازمند آن دادهها هستند ارسال میشود که این امر موجب حذف ترافیک انفجاری و کاهش بستههای تکراری میشود ]۱۸[.
از طرف دیگر استفاده از فراداده، احتمال همپوشانی را نیز از بین میبرد، البته با شرایط که گرهها میتوانند درخواستهایشان را محدود به دادههایی بکنند که دقیقاً لازم دارند. انطباق-منابع[۲۸] یعنی اینکه گرههای شبکه فعالیتهایشان را مطابق با انرژی موجود در منابع تنظیم کننده هر گره میتواند منبع مرتبط به خود را بررسی کرده و سطح انرژی آن را قبل از ارسال و پردازش داده چک کند. هنگامی که سطح انرژی پایین است ممکن است که گره فوق فعالیتهای خاصی را انجام ندهد، از قبیل ارسال بستههای داده و فراداده سه قسمتی اعلان[۲۹]، تقاضا[۳۰] و داده[۳۱]را ارسال کند ]۱۷[.
این ویژگی طول عمر گرهها و در نتیجه شبکه را بالا میبرد. انجام عمل مذاکره توسط سه نوع پیغام انجام میگیرد ]۱۸[:
نوع اول بسته یا پیغام ADV است، که گرهها برای شناساندن داده جدید به سایرین استفاده میکنند. یک گره در شبکه که میخواهد داده خود را ارسال دارد ابتدا بستهی ADV را که حاوی فراداده است، را به سایرین میفرستد.
نوع دوّم بستهی REQ است، که به معنی اعلام نیاز برای دریافت دادهای است که توسط بستهی ADV اعلامشده بود. گرهها بعد از دریافت ADV اگر داده را نیاز داشته باشد بستهی REQ را به گره ارسالکنندهی ADV فرستاده و دادهی خود را طلب میکنند.
نوع سوم بستهی Data است، که منظور دادهی اصلی جمعآوری شده توسط حسگر گره همراه با سرفصل فراداده است. بستهی Data معمولاً بزرگتر از REQ و ADVاست. برطرف کردن عیب انتقال دادهی تکراری در شبکه توسط مفهوم مذاکره، مصرف بیرویهی انرژی را کاهش میدهد.
شکل ۲-۲ مراحل کار پروتکل SPIN را نشان میدهد.
شکل ۲‑۲: نحوه عملکرد پروتکل SPIN ]17[
پروتکل SPIN با ارائه راهکار جدید فرصت مطالعات بیشتری را ایجاد کرد که سبب ایجاد پروتکلهای متعددی شد، در ادامه به برخی از این پروتکلها اشاره مینماییم]۱۷، ۱۸[.
SPIN-BC: این پروتکل برای کانالهای پخش فراگیر طراحی شد.
SPIN-PP: این پروتکل برای ارتباطات نقطهبهنقطه طراحیشده است.
SPIN-EC: این پروتکل مشابه پروتکل SPIN-PP میباشد با این تفاوت که به پارامتر انرژی اهمیت بیشتری میدهد.
SPIN-RL: این پروتکل نیز مشابه پروتکل SPIN-PP میباشد با این تفاوت که مخصوص کانالهای ارتباطی دارای خطا طراحی شده است.
با توجه به نتایج شبیهسازی، پروتکل SPIN نواقص روشهای سیلآسا[۳۲] را برطرف نمود، همچنین سبب افزایش نرخ انتقال اطلاعات نسبت به روشهای سیلآسا شد. دستیابی به این نتایج با استفاده از محلیکردن تغییرات توپولوژی و حذف انتشار تکراری اطلاعات از طریق مفهوم مذاکره امکانپذیر شد]۱۸[. بااینحال ممکن است که در سر راه گرههای میانی، پیغام ADV درست منتشر نشود که این عیب مانع استفاده از این پروتکل در برنامههای کاربردی از قبیل کنترل کردن کشف نفوذ به داخل شبکه و حفاظت از نواحی بحرانی خواهد شد.
پروتکل انتشار هدایتشده[۳۳]:
در ]۱۸[، الگو بسیار اساسی جهت تجمع دادهها در شبکههای حسگر بیسیم با نام انتشار هدایت شده ارائه شد. این پروتکل یکی از پروتکلهای اساسی و مهم از نوع مبتنی بر داده است که پروتکلهای زیادی بر مبنای آن پایهریزی شدهاند.DD یک الگوی داده محور میباشد که کلیه دادههای حس شده توسط گرههای حسگر را با یک جفت زوج مرتب خصیصه نشان میدهد. ایده اصلی به کار گرفتهشده در الگوی داده محوری، دادههای فرستادهشده از منابع مختلف با یکدیگر در جهت حذف اضافات و کاهش تعداد انتقالات ترکیب میشوند که این امر موجب صرفهجویی انرژی و افزایش طول عمر شبکه خواهد شد. حسگرها به طور محلی کار ترکیب دادهها را انجام میدهند و از حجم اطلاعات ارسالی میکاهند.
در DD ابتدا گره چاهک علاقهمندی خود را جهت دریافت داده با یک بسته ارسالی در جهت منابع نشان میدهد. هر گرهای که بسته علاقهمندی گره سینک را دریافت میکند آن را به گرههای همسایه خود ارسال میکند و بدین ترتیب ما بین آنها گرادیان تشکیل میشود. گرادیانها در واقع مسیرهای برگشتی هستند که حسگرهای همسایه بهواسطه آن درخواست را دریافت کردهاند. با ایجاد گرادیانها، بین فرستنده و گیرنده مسیرهای مختلفی ایجاد میشوند. از بین این مسیرها تنها یک مسیر به عنوان مسیر مناسب انتخاب میشود که این انتخاب بر مبنای نرخ دریافت اطلاعات از مسیرهای مختلف است. در شکل ۲-۳ مراحل مسیریابی نشان دادهشده است]۱۲[.
شکل ۲‑۳: نحوه عملکرد پروتکل انتشار هدایتشده ]۱۲[
همه گرههای حسگر به کار برده شده در شبکهی مبتنی بر DD، برنامه-آگاه میباشند. الگوریتم DD با انتخاب مسیر مناسب از طریق ذخیره و پردازش اطلاعات موجب صرفهجویی انرژی در گرههای حسگر میشود. ذخیرهسازی اطلاعات میتواند سبب اثربخشی بهتر، توانمندی و مقیاسپذیری بهتر هماهنگی مابین گرههای حسگر شود.
عملکرد تجمیع اطلاعات در پروتکل DD تحت تأثیر پارامترهایی نظیر تعداد منابع، محل قرارگیری منابع و چگونگی توپولوژی شبکه قرار دارد. برای نشان دادن تأثیر بهتر این پارامترها دو مدل به نامهای شعاع رویداد(ER[34]) و منابع تصادفی(RS[35]) ارائهشده است. در مدل ER یک نقطه در شبکه به عنوان محل وقوع یک رویداد معرفی میشود و همه گرههای قرارگرفته در شعاع S از آن نقطه به عنوان گرههای منبع در نظر گرفته میشوند. تعداد منابع انتخابشده در این مدل با n گره حسگر تقریباً برابر با میباشد. اما در مدل RS، K تا از گرهها به صورت تصادفی به عنوان منبع انتخاب میشوند که برخلاف مدل ER منابع انتخابشده لازم نیست در خوشه و نزدیک به یکدیگر قرار گیرند]۱۹[.
الگوریتم DD در مقایسه با پروتکل SPIN از دو نظر متفاوت میباشد.
از آنکه برخلاف پروتکل SPIN در پروتکل DD در ابتدا دادهها بهوسیلهی گره سینک تقاضا میشد و سپس منابع اطلاعات خود را ارسال مینمودند.
برخلاف پروتکل SPIN که نیازی به نگهداری توپولوژی شبکه ندارد. ارتباطات در پروتکل DD به صورت همسایه-به-همسایه میباشد، که در آن هر گره توانایی ذخیره و تجمیع اطلاعات را دارد]۲۰[.
پروتکل شایعه [۳۶]:
مسیریابی Rumor نسخه تغییریافتهی DD است و به طور عمده جهت کاربردهایی که در آن مسیریابی جغرافیایی عملی نیست در نظر گرفتهشده است. به طور کلی DD با استفاده از پخش فراگیر شروع به تزریق پرسوجو به تمام شبکه در زمانی که هیچ معیار جغرافیایی برای منتشر شدن وجود ندارد میکند. در برخی موارد تنها مقدار کمی از اطلاعات توسط گرهها درخواست میشود، بنابراین استفاده از پخش فراگیر غیرضروری میباشد. روش جایگزین برای سیل رخدادها در صورتی که تعدادی از رخدادها کوچک و تعدادی از پرسوجوها بزرگ باشند ایده اساسی این است به جای اینکه به جهت مشاهده رویداد خاص توسط گرهای، سیل اطلاعات در کل شبکه جاری شود، حادثه اتفاق افتاده بازیابی شود. به منظور عدم وقوع سیل حوادث از طریق شبکه، الگوریتم Rumor بستههایی با نام عامل به کار میگیرد]۴۰[.
هنگامی که یک گره رویدادی را تشخیص میدهد آن رویداد به جدولی به نام جدول رویدادها اضافه میشود و برای آن رویداد عامل تولید میشود عاملها در شبکه به منظور انتشار اطلاعات در مورد رویدادهای محلی به گرههای دور دست حرکت میکنند. هنگامی که یک گره برای رویداد پرسوجو میسازد گرهها برای اطلاع از مسیر حرکت ممکن است به پرسوجو از طریق بازرسی در جدول رویدادها عکسالعمل نشان دهند، لذا نیازی به سیل اطلاعاتی در کل شبکه نیست زیرا باعث کاهش هزینههای ارتباطی میشود. از سوی دیگر Rumor تنها یک مسیر بین منبع و مقصد حفظ میکند، بر خلاف DD که در آن دادهها بین چند مسیر با نرخ پایین مسیریابی میشوند. با توجه به تحقیقات انجامشده، Rumor به صرفهجویی قابلتوجهی در انرژی در مقایسه با زمانی که سیل رویدادها جاری میشود، میرسد]۱۲، ۲۱[.
پروتکل انرژی آگاه[۳۷]: