بررسی، شبیه¬سازی و بهبود الگوریتم¬های کاهش مصرف انرژی در شبکه-های حسگر بی¬سیم

موسسه آموزش عالی شهاب دانش
دانشکده مهندسی برق
پایان‌نامه کارشناسی ارشد
گرایش الکترونیک
عنوان
بررسی، شبیهسازی و بهبود الگوریتمهای کاهش مصرف انرژی در شبکههای حسگر بیسیم
نگارش
امیر محمد شفیعی نژاد
استاد راهنما
دکتر حسن طاهری
اسفند 1393
چکیده
امروزه با توجه به مزایای شبکههای حسگر بیسیم که همانا پیادهسازی ساده و ارزان، مصرف توان پایین و مقیاسپذیری بالای آنها است، در بسیاری از کاربردها مورد استفاده قرار گرفتهاند. طراحی شبکههای پایدار حسگر بیسیم یک مسئله بسیار چالش برانگیز است. انتظار میرود حسگرها با انرژی محدود به صورت خودکار برای مدت طولانی کار کنند. این در حالی است که جایگزینی باتریهای از کار افتاده ممکن است با هزینههای سنگین یا حتی در محیطهای سخت غیر ممکن باشد. از سوی دیگر، بر خلاف شبکههای دیگر، شبکههای حسگر بیسیم برای کاربردهای خاص مقیاس کوچک مانند سیستمهای نظارت پزشکی و مقیاس بزرگ مانند نظارت بر محیطزیست طراحی میشوند. در این زمینه، انبوهی از کار تحقیقاتی به منظور پیشنهاد طیف گستردهای از راهحلها برای مشکل صرفه جویی در انرژی انجام شده است.
در این پایان نامه یک الگوریتم مسیریابی برای تولید بهترین مسیر مابین گرههای حسگر و گره جمعکننده محلی و با هدف دستیابی به توزیع ترافیک مناسب و درنتیجه ایجاد تعادل در مصرف انرژی گرههای میانی طراحی شده است. ایجاد چنین تعادلی به افزایش طول عمر شبکه کمک میکند و بهبود الگوی مصرف انرژی در شبکههای حسگر بیسیم با منابع انرژی محدود را به دنبال خواهد داشت. از سوی دیگر با استفاده از امکان تغییر رنج گرهها، سعی میشود تا امکان توزیع بار در نقاط کم تراکم شبکه نیز افزایش یابد. نتایج حاصل از شبیهسازیها نشانگر بهبود 20 درصدی در طول عمر شبکه با استفاده از الگوریتم پیشنهادی در مقایسه با برخی از الگوریتمهای مسیریابی حساس به انرژی پیشنهادی در سالهای اخیر میباشد.
واژه‌های کلیدی:
شبکههای حسگر بیسیم، مسیریابی حساس به انرژی، متعادلسازی نرخ مصرف انرژی
فهرست عناوین صفحه
TOC \o “1-4” \h \z \u1‌ فصل اول مقدمه PAGEREF _Toc415997252 \h 11‌.1‌مکانیزمهای ذخیرهسازی انرژی در شبکههای حسگر بیسیم PAGEREF _Toc415997254 \h 21‌.1‌.1‌بهینهسازی رادیو PAGEREF _Toc415997255 \h 31‌.1‌.2‌کاهش حجم اطلاعات PAGEREF _Toc415997256 \h 61‌.1‌.3‌طرح خواب و بیدار PAGEREF _Toc415997257 \h 71‌.1‌.4‌مسیریابی با کارایی انرژی PAGEREF _Toc415997258 \h 81‌.1‌.5‌راهحل شارژ PAGEREF _Toc415997259 \h 101‌.2‌ویژگیهای شبکههای حسگر بیسیم از منظر مسیریابی PAGEREF _Toc415997260 \h 111‌.3‌الزامات طراحی الگوریتمهای مسیریابی در شبکههای حسگر PAGEREF _Toc415997261 \h 131‌.4‌بررسی کاستیهای الگوریتمهای مسیریابی موجود PAGEREF _Toc415997262 \h 171‌.5‌دستاوردها و نوآوریهای این پایان نامه PAGEREF _Toc415997263 \h 212فصل دوم مروری بر کارهای پیشین PAGEREF _Toc415997264 \h 232‌.1‌الگوریتمهای مسیریابی نامبتنی بر ساختار PAGEREF _Toc415997266 \h 242‌.1‌.1‌الگوریتمهای جغرافیایی PAGEREF _Toc415997267 \h 242‌.1‌.2‌الگوریتمهای مبتنی بر هوش مصنوعی و تئوری مورچگان PAGEREF _Toc415997268 \h 272‌.1‌.3‌الگوریتمهای خوشهبندی PAGEREF _Toc415997269 \h 302‌.2‌الگوریتمهای مبتنی بر ساختار PAGEREF _Toc415997270 \h 342‌.2‌.1‌الگوریتم RPL PAGEREF _Toc415997271 \h 342‌.2‌.1‌.1‌گراف مسیریابی جهت دار مبتنی بر مقصد (DODAG) PAGEREF _Toc415997272 \h 352‌.2‌.1‌.2‌شناسههای پروتکل PAGEREF _Toc415997273 \h 362‌.2‌.1‌.3‌تشکیل مسیر در گراف PAGEREF _Toc415997274 \h 372‌.2‌.1‌.4‌معیارهای وزن دهی مسیر در پروتکل RPL PAGEREF _Toc415997275 \h 382‌.2‌.2‌الگوریتم LB_RPL PAGEREF _Toc415997276 \h 402‌.2‌.3‌الگوریتم UDCB PAGEREF _Toc415997277 \h 412‌.2‌.4‌الگوریتم UDDR PAGEREF _Toc415997278 \h 422‌.2‌.4‌.1‌فاز انتخاب والد PAGEREF _Toc415997279 \h 432‌.2‌.4‌.2‌حرکت خودخواهانه PAGEREF _Toc415997280 \h 442‌.2‌.4‌.3‌بازی مشترک PAGEREF _Toc415997281 \h 442‌.2‌.4‌.4‌فاز اتصال PAGEREF _Toc415997282 \h 453فصل سوم مدل شبکه مورد بررسی و تعریف مسأله مسیریابی بهینه PAGEREF _Toc415997283 \h 473‌.1‌همبندی شبکه PAGEREF _Toc415997285 \h 483‌.2‌چگالی گرهها PAGEREF _Toc415997286 \h 493‌.3‌مدل لینک مخابراتی بیسیم PAGEREF _Toc415997287 \h 493‌.4‌مکانیزم دسترسی به کانال مخابراتی PAGEREF _Toc415997288 \h 503‌.5‌تعریف مسأله توزیع ترافیک بهینه PAGEREF _Toc415997289 \h 514فصل چهارم الگوریتم مسیریابی درختی با هدف مصرف انرژی متوازن PAGEREF _Toc415997290 \h 524‌.1‌فاز ایجاد درخت PAGEREF _Toc415997292 \h 544‌.2‌بررسی اثر افزایش رنج مخابراتی PAGEREF _Toc415997293 \h 554‌.3‌نحوه انتخاب والد ترجیحی PAGEREF _Toc415997294 \h 584‌.4‌تحلیل پیچیدگی الگوریتم PBLD PAGEREF _Toc415997295 \h 645فصل پنجم چارچوب شبیهسازی و مقایسه نتایج عملکرد PAGEREF _Toc415997296 \h 665‌.1‌محیط شبیهسازی PAGEREF _Toc415997298 \h 675‌.2‌پارامترهای شبیهسازی PAGEREF _Toc415997299 \h 685‌.3‌سناریوهای شبیهسازی PAGEREF _Toc415997300 \h 705‌.4‌نتایج شبیهسازی PAGEREF _Toc415997301 \h 705‌.4‌.1‌عملکرد الگوریتم PBTR با توجه به تعداد گرهها PAGEREF _Toc415997302 \h 705‌.4‌.2‌عملکرد الگوریتم PBTR با توجه به تعداد گرههای تولید کننده ترافیک PAGEREF _Toc415997303 \h 725‌.4‌.3‌عملکرد الگوریتم PBTR با توجه به نرخ تولید ترافیک متغییر PAGEREF _Toc415997304 \h 746فصل ششم جمع‌بندی و نتیجه‌گیری PAGEREF _Toc415997305 \h 77منابع و مراجع PAGEREF _Toc415997307 \h 81
فهرست اشکال صفحه
TOC \h \z \c “شکل” شکل11طبقه بندی مکانیزم های ذخیره سازی انرژی PAGEREF _Toc413146363 \h 3شکل21 معماری پیشنهادی ارتباطات سه لایه PAGEREF _Toc413146364 \h 33شکل41یک برش از شبکه PAGEREF _Toc413146365 \h 56شکل 42 برشی از شبکه بعد از افزایش رنج مخابراتی PAGEREF _Toc413146366 \h 57شکل 51 نمونهای از گراف مسیریابی الگوریتم PBTR PAGEREF _Toc413146367 \h 68شکل 52 نمودار میزان طول عمر الگوریتمها در برابر با تعداد گره ها PAGEREF _Toc413146368 \h 71شکل 53 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر تعداد گره ها PAGEREF _Toc413146369 \h 72شکل 54 نمودار میزان طول عمر الگوریتم ها در برابر تعداد گره های تولید کننده ترافیک PAGEREF _Toc413146370 \h 73شکل 55 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر تعداد گره های تولیدکننده ترافیک PAGEREF _Toc413146371 \h 74شکل 56 نمودار میزان طول عمر الگوریتم ها در برابر نرخ تولید ترافیک توسط گره ها PAGEREF _Toc413146372 \h 75شکل 57 نمودار درصد سالم رسیدن بسته های ترافیکی در برابر نرخ نولید ترافیک توسط گره ها PAGEREF _Toc413146373 \h 76
فهرست جداول صفحه
TOC \h \z \c “جدول” جدول ‏41 شبه کد ایجاد الگوریتم درخت مسیریابی PAGEREF _Toc413106303 \h 55جدول ‏42 شبه کد الگوریتم افزایش توان ارسالی گره PAGEREF _Toc413106304 \h 58جدول ‏43 شبه کد الگوریتم نقش گره v به عنوان گره والد PAGEREF _Toc413106305 \h 62جدول ‏44 شبه کد الگوریتم نقش گره u به عنوان گره فرزند PAGEREF _Toc413106306 \h 63جدول ‏51 پارامترهای شبیهسازی PAGEREF _Toc413106307 \h 69
‌فصل اولمقدمهمقدمه مقیاسپذیری، پوشش، زمان تاخیر، کیفیت سرویس، امنیت و تحرک از نیازهای اصلی شبکههای حسگر بیسیم مورد استفاده در برنامههای مختلف کاربردی، از جمله نظارت بر محیطزیست، امنیت عمومی، مراقبتهای پزشکی و کاربردهای نظامی و صنعتی به شمار میروند. در این برنامههای کاربردی، از حسگر انتظار میرود به صورت خودکار برای مدت زمان طولانی، اعم از هفته یا ماه، کار کند. با این حال، این شبکهها با توجه به منابع محدود باتری موجود در حسگرها از محدودیت طول عمر شبکه رنج میبرند.
در چند سال اخیر روشهای متعددی برای صرفهجویی انرژی در شبکههای حسگر بیسیم پیشنهاد شده است و هنوز هم تحقیقات بسیاری در مورد چگونگی بهینهسازی مصرف انرژی برای شبکههای حسگر بیسیم با منابع انرژی محدود در حال انجام است. در بخش بعدی استانداردهای موجود برای افزایش طول عمر شبکههای حسگر بیسیم را با توجه به ذخیرهسازی انرژی بیان میکنیم.
مکانیزمهای ذخیرهسازی انرژی در شبکههای حسگر بیسیم در این بخش، مروری بر روی روشهای عمده موجود برای حل مشکل مصرف انرژی در شبکههای حسگر بیسیم که در مقاله [1] ارائه شده است، انجام میدهیم. یک طبقهبندی از مکانیزمهای پیشنهادی ذخیرهسازی انرژی درREF _Ref412194936 \hشکل11به طور خلاصه آورده شده است.
TOC \h \z \c “شکل”
شکل1SEQ شکل \* ARABIC \s 11طبقهبندی مکانیزمهای ذخیرهسازی انرژی
بهینهسازی رادیو تراکنشهای رادیویی در گرههای حسگر بیشترین نقش در تخلیه انرژی باتری را دارند. محققان با توجه به ماهیت ارتباطات بیسیم، برای کاهش اتلاف انرژی در شبکههای حسگر بیسیم روشهایی را مبتنی بر بهینهسازی پارامترهای رادیویی مانند طرحهای مدولاسیون و کدینگ، کنترل توان ارسالی و آنتنهای جهتدار مطرح کردهاند.
الف) بهینهسازی مدولاسیون: بهینهسازی مدولاسیون با هدف پیدا کردن پارامترهای بهینه مدولاسیون برای به حداقل رساندن انرژی مصرفی رادیو میباشد. پژوهشهای موجود تلاش میکند تا یک تعادلسازی بهینه بین اندازه مجموعه (تعداد کاراکترهایی که استفاده میشود)، نرخ اطلاعات ارسالی (تعداد بیتهای اطلاعات در هر نماد)، زمان ارتباط، فاصله بین گرهها و نویز پیدا کنند [3,2].
ب)طرحهای ارتباطات مشارکتی (چند هاب): به منظور بهبود کیفیت سیگنال دریافت شده با استفاده از همکاری چندین آنتن، که باعث به وجود آمدن یک فرستنده مجازی چند آنتنه میشوند، ارائه شده است. ایده این طرح برگرفته از این واقعیت است که اطلاعات معمولا با توجه به ماهیت پخش از کانال توسط همسایههای یک گره شنیده میشوند. پژوهشهای زیادی در زمینه مقایسه انرژی مصرفی شبکههای SISO (یک ورودی و یک خروجی) و شبکههای مجازی MIMO (چند ورودی و چند خروجی) انجام شده است. نتایج این پژوهشها نشاندهنده صرفهجویی بهتر انرژی و تاخیر انتها به انتهای کمتر در فاصلههای بیشتر از محدوده ارسال گرهها درسیستمهای MIMO حتی با وجود انرژی اضافی سربار مورد نیاز برای راهاندازی این الگوریتمها میباشد [5,4].
پ) کنترل توان ارسال: کنترل توان ارسال (TPC) به منظور افزایش بهرهوری انرژی در لایه فیزیکی با تنظیم توان فرستندههای رادیویی مورد بررسی قرار گرفته شده است. از این رو، یک گره با انرژی باقیمانده بالاتر میتواند توان ارسال خود را افزایش دهد، که این عمل باعث فعال کردن الگوریتم کاهش توان ارسال در گرههای دیگر میشود، در نهایت صرفهجویی انرژی را به همراه دارد. استراتژیTPC نه تنها در انرژی بلکه با کاهش توان ارسال، خطر تداخل را نیز کاهش میدهد. علاوه بر این، گرههای کمتری در ناحیه شنوایی یک گره قرار میگیرند. از سوی دیگر افزایش توان ارسال می توان منجر به توسعه رنج مخابراتی گره شده و تعداد همسایگان آنرا افزایش دهد. این امر میتواند قابلیت توزیع ترافیک را در گرههایی که دارای تعداد همسایه کمی هستند، افزایش داده و منجر به بهبود طول عمر شبکه گردد [7,6].
ت) آنتنهای جهتدار: آنتنهای جهتدار توانایی دریافت سیگنالهای ارسالی را در یک زمان و در یک جهت را دارند. که این امر باعث بهبود محدوده ارسال و انرژی مصرفی میشود. این آنتنها ممکن است نیازمند به تکنیکهای محلی باشند، اما توانایی دریافت چندین ارتباط را به صورت همزمان دارند. به این ترتیب استفاده بیشتری از پهنایباند میشود. بنابراین، این الگوریتم میتواند ظرفیت شبکه و طول عمر را بهبود ببخشد در حالی که بر تاخیر و اتصال نیز میتواند تأثیر گذار باشد. با این حال، برخی از مشکلاتی که مخصوص آنتن جهتدار هستند از جمله تداخل سیگنال، تنظیمات آنتن و مشکلات ناشنوایی باید موقع استفاده از این آنتنها در نظر گرفته شود [8 ,9].
ث) رادیو شناختی با کارایی انرژی :رادیو شناختی (CR) رادیو هوشمندی است که میتواند به صورت پویا کانال ارتباطی خود را در طیفهای بیسیم انتخاب کند و خود را با پارامترهای ارسال و دریافت انطباق دهد. بر اساس تکنولوژی نرمافزار تعریف شده رادیو انتظار میرود که به طور کاملاً خودکار فرستنده و گیرنده خود را متناسب با پارامترهای مورد درخواست شبکه تنظیم مجدد کند، که این امر باعث بهبود در زمینه آگاهی از شبکه میشود. با این حال، مهمترین نیاز رادیو شناختی مصرف انرژی گره با توجه به پیچیدگی آنتن و ویژگیهای جدید در مقایسه با دستگاه های معمولی میباشد. در این راستا، طراحی شبکههای حسگر رادیو شناختی کلیدی برای حل چالش استفاده هوشمند از انرژی باتری میباشد. مطالعات اخیر رادیو شناختی در زمینههای کنترل توان فرستنده، تخصیص کانالها مبتنی بر انرژی باقیمانده، و ترکیب کدینگ شبکه و رادیو شناختی میباشد [11,10].کاهش حجم اطلاعات یکی دیگر از راهحلهای ذخیرهسازی انرژی کاهش مقدار اطلاعات ارسالی به سمت گره جمعکننده میباشد. میتوان از دو روش محدود کردن نمونههای غیرضروری و محدود کردن وظایف سنجش هر گره به طور مشترک استفاده کرد. زیرا بدست آوردن و ارسال اطلاعات از نظر مصرف انرژی پرهزینه میباشند.
الف) تجمیع: در طرح تجمیع اطلاعات، گرهها در طول یک مسیر به سمت گره جمعکننده عمل تجمیع اطلاعات را برای کاهش مقدار اطلاعات ارسالی انجام میدهد. علاوه بر این، تجمع اطلاعات با کاهش ترافیک میتواند تأخیر را نیز کاهش دهد. با این حال، روشهای جمعآوری اطلاعات ممکن است دقت اطلاعات جمعآوری شده را کاهش دهد. در واقع، بعد از انجام عملیات تجمیع، اطلاعات نمیتواند توسط جمعکننده بازیابی شود و در نتیجه دقت اطلاعات از دست میرود [12].
ب) نمونهبرداری توافقی: سنجش نمونههای غیرضروری بر منابع ارتباطات و هزینههای پردازش تاثیر میگذارد. تکنیکهای نمونهبرداری توافقی، نرخ نمونهبرداری در هر حسگر را با توجه به نیازهای برنامههای کاربردی از قبیل پوشش و بدست آوردن اطلاعات دقیق، تنظیم میکند [13].
پ) کدینگ شبکه(NC): کدینگ شبکه(NC) به منظور کاهش ترافیک در سناریوهای پخش با ارسال یک ترکیب خطی از چند بسته به جای یک کپی از هر بسته استفاده میشود. گرههای دریافت کننده نیز میتوانند با استفاده معادلات خطی رمزگشایی بستهها را تفکیک کنند [14].
ت) فشردهسازی اطلاعات: با استفاده از تکنیکهای خاص با قابلیتهای محاسباتی و قدرتهای گرههای بیسیم کدگذاری اطلاعات برای بدست آوردن بارهای ارسالی با بیتهای کمتر انجام میگیرد، که این روش باعث بهروری از انرژی میشود [15].
طرح خواب و بیدار واحدهای رادیو در زمانهای بیکاری، منابع اصلی مصرفکننده انرژی هستند. هدف از طرح خواب و بیدار قرار دادن رادیو در حالت خواب و بیدار با توجه به فعالیت گره در جهت صرفهجویی انرژی میباشد.
الف) برنامه روشن و خاموش شدن دورهای حسگرها: به منظور تغییر حالت واحد رادیو گره وابسته به فعالیتهای شبکه برای به حداقل رساندن زمان گوش دادن در حالت بیکاری طراحی شدهاند. این برنامهها معمولا به سه دسته وابسته به تقاضا، غیرهمزمان و مطابق با برنامه تقسیم میشود. پروتکلهای مبتنی برروشن و خاموش شدن دورهای قطعا باعث بیشتر شدن بهرهوری انرژی میشود اما به شدت افزایش تاخیر ارتباطات را به همراه دارند. همچنین گرهها در این شرایط برای ارسال اطلاعات هنگامی که خود یا گره بعدی در حالت خواب میباشد، رنج میبرند [17,16].
ب) رادیو جانبی بیدار: برای از بین بردن نقاط ضعف برنامه روشن و خاموش شدن دورهای حسگرها، از یک رادیو کم قدرت برای دریافت اطلاعات در زمانیکه یک گره در حالت خواب قرار دارد، استفاده میشود و برای ارسال اطلاعات ترافیکی از یک رادیو پر قدرت استفاده میشود [18].
پ) کنترل توپولوژی : هنگامی که گرههای حسگر بسیار زیادی به منظور حصول اطمینان از پوشش خوب از فضای مورد نظر مستقر میکنند، میتوان بعضی از گرهها را با در نظر گرفتن حفظ عملیات و اتصالات شبکه در حالت غیر فعال قرار دهیم. پروتکلهای کنترل توپولوژی به صورت پویا تعداد گره فعال را با توجه به نیازهای برنامه به منظور بهرهبرداری بیشتر انرژی در شبکه تعیین میکند [20,19].
مسیریابی با کارایی انرژی بار اضافی در مسیریابی به طور جدی میتواند ذخایر انرژی را تحت تأثیر قرار دهد. به طور خاص، در الگوریتمهای چند گام، گرههایی که به جمع کننده نزدیک هستند، انرژی باتری خودشان را سریعتر از بقیه گرهها از دست میدهند، که این امر منجر به فروپاشی شبکه میشود. آنچه که ما در این پایان نامه به دنبال آن هستیم، مکانیزم صرفهجویی انرژی در الگوریتمهای مختلف مسیریابی میباشد. در ادامه برخی از روشهای مسیریابی حساس به انرژی را برای شناخت بیشتر از موضوع این پایان نامه مورد بررسی قرار میدهیم.
الف) روشهای خوشه بندی: تکنیکهایی خوشهبندی به منظور ارتقاء بهرهوری انرژی با استفاده از محدود کردن مصرف انرژی از طریقهای مختلف زیر انجام میشود.
الف) کاهش محدوده ارتباطات در داخل خوشه که نیاز به توان ارسال کمتردارند، (ب) کاهش تعداد ارسال با استفاده از تجمیع اطلاعات توسط سرخوشه، (ج) کاهش انرژی عملیاتهایی مانند هماهنگی و تجمیع در سر خوشه، (د) غیرفعال کردن برخی از گرههای داخل خوشه زمانی که سرخوشه مسئولیت ارسال اطلاعات رابر عهده دارند، (و) به تعادل رساندن مصرف انرژی در بین گرههای موجود در خوشه از طریق چرخش گره سرخوشه پیشنهاد شده است.
علاوه بر بهرهوری انرژی، معماری خوشهبندی، مقیاسپذیری شبکهها را با حفظ شبکه سلسله مراتبی بهبود میبخشد [22,21].
ب) مسیریابی مبتنی بر انرژی: در نظر گرفتن انرژی به عنوان یک معیار در مرحله راهاندازی مسیر یکی دیگر از راهحلهای گسترش طول عمر شبکههای حسگر است. با انجام این الگوریتم، گرههای حسگر در مسیریابی نه تنها بر کوتاهترین مسیر تمرکز دارد بلکه انرژی باقیمانده گام بعدی را نیز در نظر میگیرند [23].
پ) مسیریابی چندمسیره: در حالی که پروتکلهای مسیریابی تک مسیره به طور کلی سادهتر از پروتکلهای مسیریابی چند مسیره هستند، میتوانند انرژی گرهای که به عنوان هاپ بعدی انتخاب کردهاند را به سرعت تخلیه کنند. در مقابل، مسیریابی چند مسیره قادر است توسط انتخاب متناوب گرههای ارسالی انرژی مصرفی را در میان گرهها متعادل کنند. پروتکلهای مسیریابی چند مسیره با ارائه مسیرهای چندگانه، توانایی شبکه برای بازیابی شبکه را بعد از تخلیه انرژی یک گره افزایش میدهد، این در حالی که در مسیریابی تک مسیره، هنگامی که انرژی یک گره به پایان میرسد، یک مسیر جدید باید مجددا محاسبه شود [25,24].
ت) قرار دادن گره رله: الگوریتم مسیریابی میتواند با اضافه کردن چند گره رله از تخلیه زودرس انرژی گرهها در یک منطقه خاص به خاطر فاصله زیاد از گره بعدی اجتناب کرد. این کار به بهبود تعادل انرژی بین گرهها کمک میکند، و از به وجود آمدن حسگر پر مصرف جلوگیری میکند [27,26].
ث) گره جمعکننده متحرک: در معماری شبکه حسگر بیسیمی که از یک ایستگاه پایه ثابت استفاده میکنند، گرههای واقع در نزدیکی ایستگاه پایه سریعتر از دیگر گرهها باتری خود را خالی میکنند و منجر به قطع زودرس در شبکه میشوند. این یک واقعیت است که تمام ترافیک به سمت گره جمعکننده فرستاده میشود و باعث افزایش حجم کار در گرههای نزدیک به گره جمعکننده میگردد. برای افزایش طول عمر شبکه و امکان به تعادل رساندن بار بین گرهها از یک ایستگاه پایه متحرک استفاده میشود که با حرکت در اطراف شبکه به جمعآوری اطلاعات از گرهها میپردازد. تحرک گره جمعکننده باعث بهبود اتصالات در معماری شبکههای پراکنده و افزایش قابلیت اطمینان به دلیل ارتباطات تک گامه میشود. بنابراین زمان رقابت، تصادم و از دست دادن پیام را نیز کاهش میدهد [29,28].
راهحل شارژ مطالعات تحقیقات اخیر در جهت رسیدگی به برداشت انرژی و تکنیکهای شارژ بیسیم میباشد. هدف از ارائه هر دو راهحل، شارژ باتری حسگر بدون دخالت انسان میباشد.
الف) برداشت انرژی: فنآوریهای جدید برای فعال کردن حسگرها برای برداشت انرژی از اطراف محیطزیست خود مانند انرژی خورشیدی، باد و انرژی جنبشی توسعه یافتهاند. در مقایسه با حسگرهای سنتی، حسگرهای قابل شارژ از لحاظ نظری میتواند به طور مداوم برای مدت زمان نامحدودی کار کنند. آنها انرژی محیط را به انرژی الکتریکی تبدیل میکنند و سپس آن را به طور مستقیم مصرف یا برای استفادههای بعدی خود ذخیره میکند [31,30].
ب) شارژ بیسیم: با پیشرفتهای اخیر در ارسال قدرت بیسیم انتظار میرود که شبکههای حسگر بیسیم از پایداری بیشتری بهرهمند شوند. این تکنیک میتواند برای ارسال قدرت بین دستگاهها بدون نیاز به هر گونه تماس بین فرستنده و حسگر مورد استفاده قرار گیرد. شارژ بیسیم در شبکه حسگر بیسیم میتواند به دو روش تابش الکترومغناطیس و جفت رزونانس مغناطیسی به دست آورد. تحقیقات اخیر بر روی به اشتراک گذاشتن انرژی گرهها در بین همسایههای خود تمرکز دارند. بدین ترتیب، پیشبینی میشود که در آینده، هر گره در شبکههای حسگر بیسیم قادر به برداشت انرژی از محیطزیست و ارسال انرژی به گرههای دیگر را دارا باشد، که یک شبکه خود کفا را ارائه میدهد [33,32].
روشن است که تلاشهای بسیاری از طریق انواع مکانیسمهای ذخیرهسازی انرژی به منظور ارتقاء طول عمر شبکههای حسگر بیسیم انجام شده است. این نیز به نظر میرسد که بهرهوری انرژی و برنامههای کاربردی دیگر به شدت وابسته و نیازمند به معیارهای عملکرد مختلف بهینهسازی به طور مشترک هستند.
ویژگیهای شبکههای حسگر بیسیم از منظر مسیریابی با توجه به اینکه در این پایاننامه افزایش طول عمر شبکه با استفاده از روشهای مسیریابی را در نظر گرفته شده است. به همین دلیل، در بخش بعدی برخی از الزامات الگوریتم مسیریابی مورد استفاده در شبکههای حسگر را بیان نمودهایم. پیش از پرداختن به الزامات طراحی پروتکل مسیریابی به ویژگیهای شبکههای حسگر از منظر مسیریابی مختصراً در زیر اشاره میکنیم.
الف) خصوصیات شبکه
* تعداد و چگالی گرهها و قطر شبکه: این خصوصیت بر روی تعداد گزینههای جدولهای مسیریابی
در گرهها و همچنین میزان تأخیر و اتلاف ناشی از گامهای طی شده توسط بسته ها مؤثر است.
* اتصال: به دلیل شرایط محیط فیزیکی ممکن است لینکهای شبکه حالات مختلفی از اتصال را تجربه کنند. این امر لزوم پویایی بالا در الگوریتم مسیریابی و عدم اکتفا به مسیرهای منحصر بفرد را در شبکههای حسگر را آشکار میسازد.
* پویایی: شبکههای حسگر و عملگر بیسیم به دلیل امکان حرکت برخی از گرهها، از همبندی پویا برخوردار هستند و تغییر همبندی اغلب موجب تغییر در مسیر بستهها میشود. علاوه بر حرکت گرهها، ورود گرههای جدید به شبکه یا خروج برخی از گرهها به دلیل خالی شدن باتری نیز میتواند باعث تغییر در همبندی شبکه شود.
* استقرار: محل استقرار گرهها در شبکههای حسگر میتواند به صورت تصادفی مثلاً با پخش کردن گرهها از طریق هواپیما در محیط مورد نظر باشد. علاوه بر این محل استقرار گرههای جمعکننده که نقش دروازه ارتباط به شبکههای دیگر را نیز دارند در عملکرد پروتکل مسیریابی مؤثر است.
* طرحهای ترافیکی: بنا بر کاربرد خاص، طرحهای ترافیکی مختلفی مانند نقطه به نقطه، نقطه به گروه و گروه به نقطه در این شبکهها قابل تصور است.
* کیفیت سرویس: در صورت نیاز کاربردهای مختلف به کیفیت سرویسهای مختلف، ممکن است نیاز به تعریف کلاسهای سرویس چندگانه و استفاده از معیارهای مختلف مسیریابی به صورت توأم داشته باشیم.
ب) خصوصیات گرهها
* سرعت پردازش و حجم حافظه: محدودیتهای موجود روی این پارامترها در ابعاد جداول مسیریابی و چگونگی پردازش آنها تأثیرگذار هستند.
* میزان مصرف توان و منبع انرژی گره: تعداد و محل استقرار گرههای با منبع باتری و گرههای متصل به برق در شبکه، تأثیر مستقیم روی سیاستهای مسیریابی مبتنی بر افزایش طول عمر شبکه خواهد داشت.
* گستره ارسال: گستره ارسال گرهها که وابسته به قدرت سیگنال رادیویی آنهاست میتواند در همبندی شبکه و میزان چگالی گرهها و اتصال آنها به یکدیگر مؤثر باشد.
* بار ترافیکی: میزان بار ترافیکی گرهها میتواند در کیفیت مسیریابی تأثیرگذار باشد. تـقسیم بار بین گرهها میتواند یکی از سیاستهای مهم در مسیریابی بهینه در این گونه شبکهها باشد.
ج) خصوصیات لینکها
* گذردهی: نرخ بیت لینکهای بیسیم در شبکههای مبتنی بر IEEE802.15.4 پایین و حداکثر برابر 250 kbpsاست. البته این نرخ بیت بر اساس شرایط لایه فیزیکی و همچنین میزان تداخل لینکهای مجاور میتواند کمتر از این نیز باشد. ضمناً بازههای خواب و بیداری و یا شرایط ترافیکی حاکم نیزمیتواند نرخ بیت لینکها را کاهش دهد.
* تأخیر: میزان تأخیر ارسال روی یک لینک IEEE802.15.4 بر اثر ایجاد صف در گرهها و همچنین زمان لازم برای رقابت بر سر کانال میتواند افزایش یابد.
* کیفیت اتصال: شبکههای حسگر به دلیل شرایط لایه فیزیکی و مصرف توان پایین، دارای لینکهای نامطمئن هستند. این خصوصیت لینک با فاکتورهایی مانند شاخص قدرت سیگنال دریافتی، شاخص کیفیت اتصال و یا نرخ خطای کانال نشان داده میشود.
الزامات طراحی الگوریتمهای مسیریابی در شبکههای حسگر با در نظر گرفتن ویژگیهایی که در بخش قبل در مورد شبکههای حسگر بیان گردید، الزاماتی در طراحی الگوریتمهای مسیریابی برای این شبکهها قابل تصور است که در ادامه به آنها اشاره خواهیم نمود.
الف) الزامات جهت پشتیبانی از خصوصیات شبکه
1. الگوریتم مسیریابی باید شرایط عدم پاسخگویی گرهها در اثر خواب رفتن تناوبی آنها را در نظر بگیرد. جهت دستیابی به این قابلیت استفاده از اطلاعات لایههای پایینتر میتواند مدنظر قرار گیرد. بنابر کاربرد پیاده شده در شبکه، گرهها با نرخهایی مانند 1 بسته در هر ثانیه یا در هر دقیقه یا بیشتر به تولید بستههای اطلاعاتی میپردازند و لذا در مابقی زمان خود به منظور صرفهجویی در انرژی به خواب میروند. گرههایی که به عنوان هدایتکننده بسته دیگر گرهها عمل میکنند ممکن است به دلیل اتصال به برق، همواره بیدار باشند؛ در غیر اینصورت، زمان خواب آنها باعث افزایش تأخیر بستهها و احتمال از بین رفتن آنها میشود که میتواند به عنوان هزینهای در تابع انتخاب مسیر منعکس شود.
2. الگوریتم مسیریابی با استفاده از اطلاعات لایههای پایینتر در خصوص میزان انرژی باقیمانده گرهها باید در خصوص ایجاد یا بروز رسانی جدولهای مسیریابی اقدام نماید. همچنین شاخص کیفیت لینک نیز باید به عنوان معیاری در انتخاب مسیر مناسب مورد توجه قرار گیرد.
3. الگوریتم مسیریابی باید به نحوی طراحی شود که قابلیت مقیاسپذیری و همچنین صرف کمترین منابع برای بروز رسانی جداول مسیریابی را داشته باشد. شبکههای حسگر و عملگر بیسیم ممکن است از چندین میلیون گره تشکیل شده باشند. در چنین شرایطی گروه بندی گرهها در دستههای 100 تا 10000تایی و استفاده از الگوریتمهای مسیریابی سلسله مراتبی جهت سادهسازی مسیریابی در شبکه و افزایش مقیاسپذیری به عنوان بهترین راهکار شناخته شده است [35,34].
4. استفاده از روشهای تعمیر و بازیابی مسیرها به نحوی که در صورت از بین رفتن بخشی از مسیر، نیاز به تکرار پروسه مسیریابی از مبدأ تا مقصد نباشد. این امر سربار ناشی از بستههای مسیریابی را در شبکه کاهش داده و باعث بهبود گذردهی و تأخیر ارسال بستهها میشود.
5. پشتیبانی از تغییرات همبندی شبکه ناشی از حرکت گرهها یا تغییر شرایط لینکها. به عنوان مثال در شبکههای خانگی زمان لازم برای اعمال تغییرات همبندی و بازسازی مسیرها توسط الگوریتم مسیریابی نباید از 20 ثانیه تجاوز نماید [36]. برخی کاربردها که نیاز به تبادل آنی اطلاعات دارند ممکن است زمان کمتری برای همگرایی الگوریتم مسیریابی را تحمل نمایند. در الگوریتم مسیریابی بکار رفته در شبکههای حسگر به دلیل محدودیت قدرت پردازشی امکان ردیابی مسیر گرههای در حال حرکت جزء الزامات نیست و حرکت گرهها تنها به صورت حذف آنها از یک محل یا گروه و اتصال آنها به یک ایستگاه پایه یا گروه جدید باید به خوبی قابل پشتیبانی باشد.
6. الگوریتمهای مسیریابی در شبکههای حسگر باید طرحهای ترافیکی نقطه به گروه، گروه به نقطه و در برخی مواقع نقطه به نقطه را پشتیبانی نمایند. ترافیک در شبکههای حسگر و عملگر معمولاً از یک نقطه به چند نقطه و یا از چند نقطه به یک نقطه حرکت می کند. برخی کاربردها نیاز به ارتباط نقطه به نقطه نیز دارند ولی ترافیک غالب از دو نوع اول است. طرح ترافیکی خاص، در این گونه شبکهها طراحی الگوریتم مسیریابی را به نسبت شبکههای مسطح که تمامی گرهها میتوانند با یکدیگر تبادل داده داشته باشند سادهتر میسازد.
ب) الزامات جهت پشتیبانی از خصوصیات گره ها
7. الگوریتم مسیریابی باید دارای کد نرمافزاری کم حجم و حالات مسیریابی کمی باشد تا با شرایط حافظه و قدرت پردازش گرهها در شبکههای حسگر قابل پیادهسازی باشد.
8. الگوریتم مسیریابی باید با حداقل بستههای کنترلی لازم بتواند عملیات مسیریابی را مدیریت نماید تا سربار انرژی مصرفی در شبکه به حداقل برسد. با توجه به اینکه بستههای مسیریابی معمولاً چند پخشی هستند سربار انرژی مصرفی توسط آنها نیز بالا خواهد بود. لذا بهینهکردن نرخ ارسال بستههای مسیریابی یکی از فاکتورهای اساسی در طراحی الگوریتم در شبکههای حسگر است.
ج) الزامات جهت پشتیبانی از خصوصیات لینک
9. بستههای مسیریابی حتی المقدور نباید از طول یک فریم لایه پیوند داده تجاوز نمایند تا سربار
ناشی از قطعه قطعه کردن و بازسازی مجدد آنها به حداقل برسد. همچنین با توجه به نامطمئن بودن لینکها در شبکههای حسگر، در صورت قطعه قطعه کردن بستههای کنترلی، احتمال بروز خطا در پروتکل نیز افزایش خواهد یافت.
10. الگوریتم مسیریابی باید نرخ اتلاف بسته قابل تحمل توسط کاربرد پیادهسازی شده در شبکه را با انتخاب مسیرهای مناسب برای بستهها رعایت نماید. به این منظور الگوریتم مسیریابی باید از تغییرات کوتاه مدت و طولانی مدت رخ داده در کیفیت لینکها مطلع شود و با استفاده از تعیین هزینه مسیرها با توجه به شاخص کیفیت لینکها مسیر مناسب را برای داشتن نرخ خطای قابل تحمل انتخاب نماید.
11. الگوریتم مسیریابی باید میزان تأخیر قابل تحمل کاربرد پیادهسازی شده روی شبکه را دانسته و با توجه به میزان تأخیر لینکهای فیزیکی طول مسیر، مسیر مناسب را انتخاب نماید. به عنوان مثال کاربردهای اتوماسیون صنعتی یا اتوماسیون ساختمان ممکن است حداکثر تأخیر قابل تحملی در حد چند ده میلی ثانیه داشته باشند.
12. الگوریتمهای مسیریابی باید در مقابل تغییرات همبندی ناشی از تغییر کیفیت لینکها یا از دست رفتن گرهها مقاوم بوده و در حداقل زمان ممکن که وابسته به کاربرد پیادهسازی شده است، همگرا شوند. علاوه بر لزوم سرعت در همگرایی، الگوریتم مسیریابی باید با اشغال کمترین منابع شبکه همگرا شود تا بند 8 از الزامات فوق را نقض ننماید.
13. الگوریتم مسیریابی باید قادر به پشتیبانی از لینکهای نامتقارن باشد. عدم تقارن لینکها به معنی عدم امکان ارسال دو سویه توسط گرههای دو سر یک لینک است که به دلایل شرایط ناپایدار رادیویی به کرات در شبکههای حسگر اتفاق میافتد.
14. الگوریتم مسیریابی به منظور تأمین امنیت شبکه، باید از مکانیزمهای تصدیق هویت و رمز نگاری در بستههای کنترلی خود پشتیبانی نماید.
15. الگوریتم مسیریابی بهتر است امکان برقراری چندین مسیر بین مبدأ و مقصد را برای ایجاد مسیرهای پشتیبان و همچنین پخش بار در شبکه به منظور دستیابی به کیفیت سرویس مناسب برای کاربردهای حساس به تأخیر یا قابلیت اطمینان داشته باشد.
بررسی کاستیهای الگوریتمهای مسیریابی موجود با توجه به محدودیتهای شدید انرژی در گرههای حسگر بیسیم مسیریابی با استفاده از چندهاب میتواند یک توپولوژی درخت مسیریابی با ذخیرهسازی انرژی برای رساندن اطلاعات به ایستگاه پایه باشد. که در آن گرههای میانی اطلاعات خود را با اطلاعات فرزندان خود تجمیع میکنند و اطلاعات تجمیع شده را به سمت ایستگاه پایه ارسال میکنند [39,38,37]. تجمیع توابع به دو گروه اصلی تجمع کامل و تجمع ناقص تقسیم میشوند برای تجمع کامل، مقدار اطلاعات خروجی ثابت و مستقل از مقدار اطلاعات ورودی است. نمونههایی از این نوع تجمع توابع حداکثر میباشد. تجمع کامل را میتوان به طور کامل در شبکههای حسگر مورد استفاده قرار داد. تابع میانگین یک مثال از تجمع ناقص است، که نیازمند به وجود تمام اطلاعات میباشند [40].
توپولوژی درختهای مسیریابی با ارسال یک پیغام مسیریابی سیلآسا از سمت ایستگاه پایه شروع میشود و توسط گرهها به تمام سطوح درخت ارسال داده میشود. هرگره میتواند تعدادی از این پیغام مسیریابی از گرههایی که میتواند به عنوان والد در نظر بگیرد، دریافت کند. هرگره بعد از اتمام پخش پیغام مسیریابی با توجه به سیاستهای مختلف که برای انتخاب پدر و مادر مانند انتخاب تصادفی، انتخاب بر اساس فاصله و یا بر اساس انتخاب بر اساس کیفیت لینک که در الگوریتم پیاده سازی شده در نظر گرفته شده است، میتواند یک والد از میان والدین احتمالی خود انتخاب کند تا دادههای خود را به سمت آن ارسال کند [42,41].
انتخاب کورکورانه گرههای والد باعث به وجود آمدن توزیع نامتعادل فرزندان در بین والدها میشود. در این حالت بسیار محتمل است که بعضی از والدین فرزندان بیشتری از والدین دیگر داشته باشند و حتی برخی از والدین بدون فرزند بمانند. تعداد فرزندان دلالت بر میزان ترافیک در یک گره خاص به دلیل دریافت، پردازش و ارسال اطلاعات دارد. بالا بودن میزان ترافیک باعث تخلیه سریع انرژی میشود و گرهای که از این مورد رنج میبرد دارای طول عمر کمتری است نسبت به گرههایی که مقدار ترافیک کمتری هستند. با توجه به این موضوع در نظر گرفتن بار موجود بر یک گره در شبکههای متراکم برای از بین بردن تخلیه سریع انرژی و از بین رفتن گره بسیار مهم است [43]. برای حل این مشکل، استفاده از مسیریابی با توزیع مناسب ترافیک در بین گرهها بهترین ومنطقیترین راهکار میباشد. روشها و الگوریتمهای متعددی در خصوص مسیریابی در شبکههای حسگر بیسیم توسط محققان ارائه شده است [44]. لیکن هنوز هم تا رسیدن به یک پروتکل استاندارد در این خصوص فاصله داریم. با توجه به اینکه موضوع مورد بررسی در این پایان نامه مسیریابی بار متعادل با استفاده از معیار انرژی میباشد، تمرکز خود را بر روی روشهای مسیریابی قرار میدهیم. روشهای مسیریابی به لحاظ متعادلسازی بار نیز به سه گروه عمده تقسیم می شوند:
الف) مسیریابی مبتنی بر ساختار؛ که در آنها مسیرهای ارسال اطلاعات از ابتدا تولید و در طول فعالیت شبکه از آنها استفاده می گردد [45].
ب) مسیریابی نامبتنی بر ساختار؛ که به دنبال ایجاد گراف مسیریابی نبوده و مسیرها را بر اساس نیاز شبکه تولید میکنند. نیاز به مسیرهای بیشتر در این روشها با توجه به پهنایباند، تأخیر یا انرژی گرهها تعیین میشود [46].
پ) روشهای مبتنی بر کدینگ؛ که بستهها را قطعه قطعه نموده و قطعات مختلف را با استفاده از روشهای کدینگ به گرههای همجوار ارسال میکنند، گره مقصد با استفاده از مکانیزمهای دیکدسازی بستههای اولیه را بازیابی مینماید. این روشها عمدتاً برای افزایش امنیت مخابراتی استفاده میشوند [47].
از میان روشهای فوق روشهای مبتنی بر ساختار برای کاربردهای مورد نظر ما یعنی جمعآوری دادهها به صورت تناوبی و ساختارمند از گرههایی با مکان مشخص و عمدتاً ثابت، بیشتر کارایی دارند. روشهای نامبتنی بر ساختار برای شبکههای adhoc با گرههای متحرک و ترافیکهای تصادفی و کم حجم مناسبتر هستند. روشهای کدینگ به طور مستقل به توزیع ترافیک نمیپردازند و از سوی دیگر به دلیل نیاز به رسیدن تمامی قطعهها برای بازیابی بستههای اصلی، برای کاربردهای حساس به تأخیر مناسب نیستند.
از آنجا که پروتکل پیشنهادی در این پایان نامه با هدف حرکت به سمت استانداردسازی پروتکلهای مسیریابی در شبکههای حسگر بیسیم طراحی شده است، استفاده از روش ساختارمند برای تولید گراف مسیریابی مورد ترجیح قرار گرفته است و الگوریتم UDDR به عنوان یک روش استاندارد و مبتنی بر ساختار، بهترین گزینه برای قرار گرفتن به عنوان بستر کار ما تشخیص داده شد.
یکی از مسائل مورد توجه و قابل بهبود مشاهده شده در الگوریتمهای مسیریابی، مکانیزم توزیع ترافیک در بین گرهها میباشد. در اکثر الگوریتمهای پیشنهادی توزیع ترافیک که الگوریتمهای صرفاً تجربی هستند با توجه به معیارهای کیفیت سرویس انجام میپذیرد؛ یعنی گرههای مختلف بر اساس معیارهای مسیریابی مختلف ارزیابی شده و ترافیک کلاسهای مختلف به گره با بیشترین سود هدایت میشوند. برای مثال الگوریتم [48] بر اساس فاصله از گره جمع کننده و الگوریتم [49] با استفاده از ترکیب کیفیتهای سرویس تأخیر و قابلیت اطمینان تصمیم به انتخاب گام بعدی خود میکنند.
از سوی دیگر برای ایجاد تعادل بار و جلوگیری از استفاده بیش از حد از برخی گرهها، از ترکیب معیار انرژی گرهها با معیارهای مسیریابی اصلی استفاده میشود تا تعادل بیشتری در بین گرهها صورت بگیرد. این روش به طور واکنشی یک توزیع ترافیک مناسب و تعادلی در مصرف انرژی گرهها ایجاد مینماید. لیکن تعیین ضریب اهمیت انرژی نسبت به معیارهای اصلی، و همچنین ضریب اهمیت معیارهای اصلی نسبت به یکدیگر، در معیار ترکیبی استفاده شده میتواند رفتار این الگوریتم را به شدت تغییر دهد.
دستهای دیگر از الگوریتمهای تجربی توزیع ترافیک که عمدتاً از دسته روشهای مسیریابی نامبتنی بر ساختار نیز هستند، از روشهای هوش حیوانی مانند تئوری مورچه ها [50,51] و یا مبتنی بر هوش مصنوعی مانند منطق فازی [52] و یا روشهای یادگیری ماشین مانند Q-learning [53] استفاده میکنند. اینگونه روشها عمدتاً دچار همگرایی کند به سمت مسیرهای بهینه هستند که باعث اتلاف بخش عمدهای از بستهها در حین عملیات جستجو و یادگیری برای بهترین مسیرها میگردد. از سوی دیگر سربار این الگوریتمها نیز به دلیل ماهیت جستجوگرانه آنها بالا است. به عنوان مثال در الگوریتمهای مبتنی بر تئوری مورچه، نیازمند ارسال مورچهها در تمامی مسیرهای ممکن به منظور یافتن بهترین مسیر هستیم؛ یا در الگوریتم مبتنی بر Q-learning هر گره با استفاده از فیدبکهای انتها به انتهای دریافتی از سمت گره جمع کننده، به تدریج گرههای پیش روی خود را امتیازدهی میکند. این در حالی است که استفاده از روشهای ساختارمند میتواند از همان ابتدا گرههای بهینه را شناسایی و تخمین مناسبی از هزینه گره را برای گرههای در امتداد آن فراهم نماید.
در مقابل این روشهای تجربی، الگوریتمهایی نیز در پی دستیابی به توزیع ترافیک بهینه با استفاده از روشهای خوشهبندی ارائه شدهاند. این الگوریتمها برای حل مسأله متعادلسازی مصرف انرژی با استفاده از جابهجایی نقشها و توزیع گرههایی با انرژی بیشتر به عنوان سرخوشه مورد استفاده قرار میگیرد. روشهای جابهجایی نقشها عمدتاً دارای سربار اطلاعات زیاد میباشند بنابراین انرژی گرهها را تحت تأثیر قرار میدهند [55,54]. همچنین با توجه به توزیع گرهها ممکن است بعضی از گرههای سرخوشه بار ترافیکی بیشتر داشته باشند و بعضی از فرزندان برای ارسال بار به گره سرخوشه مجبور به استفاده از ارتباطات چند هاپ شوند.
راه حل پیشنهادی برای توزیع ترافیک در این پایان نامه از یک مکانیزم ساخت درخت مسیریابی سعی یکسانسازی نرخ مصرف انرژی مابین گرههای هم عمق با متعادل سازی بار در میان آنها میباشد. دستیابی به نرخ مصرف انرژی متعادل مابین گرههای هم عمق، میتواند به بیشترین طول عمر قابل دستیابی در شبکه بیانجامد چون تضمین میکند که هیچ گرهای زودتر از بقیه گرهها انرژی خود را از دست ندهد.
دستاوردها و نوآوریهای این پایان نامه با توجه به مطالب این مقدمه دستاوردهای کلیدی این رساله را به شرح زیر میتوان جمعبندی نمود:
یک الگوریتم مسیریابی متعادلسازی بار مبتنی بر استاندارد UDDR پیشنهاد میگردد که برای دستیابی به متعادلسازی بار در بین گرههای والد مورد استفاده قرار میگیرد. این الگوریتم مسیریابی تولید یک درخت مسیریابی از گرهها به سمت ایستگاه پایه میکند. در الگوریتم پیشنهادی انتخاب والد توسط هر گره، بر مبنای نرخ انرژی مصرفی گرههای بالادستی انجام میپذیرد.
الگوریتم متعادلسازی بار پیشنهادی بر اساس تابع هدف معرفی شده، باعث افزایش طول عمر شبکه و سبک شدن الگوریتم نسبت به روش UDDR میباشد، همچنین قابلیت توسعه رنج در گرهها به منظور دستیابی به توزیع ترافیک مناسبتر برای ساخت یک درخت مسیریابی با بار متعادلتر را نیز در نظر گرفته است.
الگوریتم پیشنهادی قابلیت کارایی در شبکه تخت و همچنین در شبکههایی سلسله مراتبی که توسط خوشهها تقسیمبندی میشوند را دارا میباشد.
مکانیزم مسیریابی پیشنهادی یک مکانیزم کامل، عمومی و بهینه برای توزیع ترافیک در شبکههای حسگر بیسیم ارائه میکند که به دلیل وابستگی به پروتکل استاندارد UDDR میتواند مقبولیت مناسبی برای کاربردهای آینده پیدا کند.
ادامه پایان نامه به شرح زیر می باشد:
در فصل 2 برخی از کارهای مشابه ارائه شده در مقالات به صورت جزئیتر مورد مطالعه قرار میگیرند و نقاط ضعف آنها تشریح خواهد گردید. فصل 3 به تشریح الزامات الگوریتم مسیریابی مناسب از دیدگاه استاندارد شبکههای حسگر میپردازد و علاوه بر آن مدل شبکه تحت بررسی در این پایان نامه را تشریح و تعریف مسأله مسیریابی بهینه را بر اساس مدل پیشنهادی ارائه میکند. در فصل 4 پروتکل PBTR را تشریح میکنیم. فصل 5 چارچوب شبیهسازی و نتایج حاصل از شبیهسازی الگوریتمهای پیشنهادی را در مقایسه با برخی الگوریتمهای مشابه ارائه میدهد و فصل 6 نتایج حاصل و افقهای کاری آینده را جمع بندی خواهد نمود.
فصل دوممروری بر کارهای پیشینمروری بر کارهای پیشین در بخش مقدمه به برخی از رویکردهای موجود در زمینه توزیع بار ترافیک در شبکههای حسگر بیسیم اشاره شد و نقاط ضعف کلی الگوریتمهای ارائه شده به طور مختصر عنوان گردید. در این بخش برخی از الگوریتمهای شاخص، جدید و پر مراجعه در بخش مسیریابی با استفاده از معیار انرژی را با جزئیات بیشتر مورد بررسی قرار میدهیم تا خواننده درک بهتری از پیش زمینه فعالیتهای انجام شده در این موضوع داشته باشد و بهتر بتواند تفاوت روش ارائه شده در این پایاننامه را با روشهای پیشین دریابد. همانطور که در بخش قبل اشاره شد الگوریتمهای مسیریابی بار متعادل را از دو منظر میتوان تحلیل نمود. اول روش و چگونگی یافتن گرههای والد و تولید گرافهای مسیریابی و دوم چگونگی توزیع ترافیک مابین گرهها میباشد. الگوریتمهای ارائه شده در این بخش از هر دو منظر فوق مورد مطالعه قرار گرفتهاند. به دلیل اهمیت الگوریتم UDDR که مبنای اصلی کار این رساله نیز هست این پروتکل را با جزئیات بیشتری تشریح نمودهایم.
الگوریتمهای مسیریابی نامبتنی بر ساختار الگوریتمهای نامبتنی بر ساختار، عمدتاً از روش مسیریابی جستجوگرانه در هر گام استفاده میکنند. در این روش گرههای میانی بدون داشتن شناختی از مسیرهای پیش فرض و بدون استفاده از جدولهای مسیریابی، برای ارسال هر بسته به ارزیابی گرههای همسایه خود میپردازند و بستهها را به سمت گرههایی که اولاً به لحاظ جغرافیایی به گره جمعکننده نزدیکترند و ثانیاً هزینه کمتری را برای ارسال بسته در اختیار قرار میدهند، هدایت میکنند. در زیر چند نمونه از الگوریتمهای نامبتنی بر ساختار را مورد بررسی قرار میدهیم.
الگوریتمهای جغرافیایی الگوریتمهای جغرافیایی مهمترین الگوریتمهای این گروه هستند که با استفاده از پارامترها و
اطلاعات گرههای همسایه به صورت محلی مسیرهای منتهی به گره جمع کننده را جستجو میکنند. باتوجه به توزیع تصادفی گرههای حسگر در محیطهای متفاوت ازلحاظ شرایط محیطی، استفاده از مسیریابی جغرافیایی باعث استفاده مناسب از این شبکهها خواهد شد. مسیریابی جغرافیایی دارای مزایایی از قبیل مقیاسپذیری، مسیریابی براساس اطلاعات محلی و سازگاری با پویایی توپولوژی


بررسی، شبیه¬سازی و بهبود الگوریتم¬های کاهش مصرف انرژی در     شبکه-های حسگر بی¬سیم پایان نامه ها
قیمت: 11200 تومان

این نوشته در پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *