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

موسسه آموزش عالی شهاب دانش
دانشکده مهندسی برق
پایان‌نامه کارشناسی ارشد
گرایش الکترونیک
عنوان
بررسی، شبیهسازی و بهبود الگوریتمهای کاهش مصرف انرژی در شبکههای حسگر بیسیم
نگارش
امیر محمد شفیعی نژاد
استاد راهنما
دکتر حسن طاهری
اسفند 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].کاهش حجم اطلاعات یکی دیگر از راهحلهای ذخیرهسازی انرژی کاهش مقدار اطلاعات ارسالی به سمت گره جمعکننده میباشد. میتوان از دو روش محدود کردن نمونههای غیرضروری و محدود کردن وظایف سنجش هر گره به طور مشترک استفاده کرد. زیرا بدست آوردن و ارسال اطلاعات از نظر مصرف انرژی پرهزینه میباشند.
الف) تجمیع: در طرح تجمیع اطلاعات، گرهها در طول یک مسیر به سمت گره جمعکننده عمل تجمیع اطلاعات را برای کاهش مقدار اطلاعات ارسالی انجام میدهد. علاوه بر این، تجمع اطلاعات با کاهش ترافیک میتواند تأخیر را نیز کاهش دهد. با این حال، روشهای جمعآوری اطلاعات ممکن است دقت اطلاعات جمعآوری شده را کاهش دهد. در واقع، بعد از انجام عملیات تجمیع، اطلاعات نمیتواند توسط جمعکننده بازیابی شود و در نتیجه دقت اطلاعات از دست

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

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

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