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

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

همبندی شبکه
شبکه تحت بررسی شامل تعدادی گره حسگر و عملگر بیسیم است که در سطح محیط مورد نظر به صورت تصادفی یکنواخت پخش شدهاند. محیط تحت بررسی به صورت یک مربع a*a با ابعاد یک شبکه شخصی یا محلی در نظر گرفتهشده است و تعداد گرههای موجود در آن از ۱۰۰ گره تجاوز نمیکند. خواننده باید توجه داشته باشد که با فرض قابلیت مسیریابی سلسله مراتبی در شبکههای حسگر بیسیم، فرض فوق محدودیتی در ابعاد شبکه کلی ایجاد نمیکند. تعداد گرههای جمعکننده در محیط پیاده سازی ۱ در نظر گرفته شده و الگوریتم مسیریابی به نحوی عمل میکند که اطلاعات تولیدی توسط گرهها را به نحو مقتضی به گره جمع کننده ارسال دهد. در نتیجه نوع ترافیک مورد توجه در این رساله نیز از نوع چند نقطه به یک نقطه است. آزمایشهای مختلف در حین شبیهسازی و همچنین استدلالهای منطقی نشانگر این هستند که محل استقرار گره جمعکننده بهتر است نزدیک به مرکز محیط پیادهسازی باشد، زیرا بدین ترتیب امکان تعدیل بار ترافیکی در سراسر شبکه تحت بررسی به نحو مطلوبتری میسر میگردد. برای اینکه مدل شبکه ما قدری به واقعیت نزدیکتر گردد، محل استقرار گره جمعکننده در مربعی به ابعاد و در میانه محیط پیادهسازی اصلی به صورت تصادفی انتخاب میشود. چنین فرضی به لحاظ شرایط پیادهسازی واقعی تا حد زیادی امکانپذیر خواهد بود.
 
چگالی گرهها
هر چقدر چگالی گرهها در یک محدوده مشخص بیشتر باشد، احتمال بروز تصادم بیشتر شده و گرهها نیازمند صرف زمان بیشتری برای دسترسی به کانال فرکانسی هستند. از سوی دیگر چگالی کم گرهها ممکن است به ایجاد حفرههای مسیریابی و نامتصل شدن (تنک شدن) گراف مسیریابی به دلیل فاصله بیش از حد برخی از گرهها گردد.
ما در مقالات موجود معیار مناسب و سرراستی برای کم یا زیاد بودن چگالی در شبکههای حسگر بیسیم پیدا نکردیم. تنها در مرجع [۷۷] اشاره شده که برای پیشگیری از تنک[۴۹] شدن شبکه و ایجاد یک شبکه متصل، بهتر است چگالی شبکه به میزانی باشد که هر گره به طور میانگین حداقل ۵ همسایه در اطراف خود داشته باشد. نتایج حاصل از شبیهسازیها نیز نشانگر درستی نسبی این فرضیه بود به نحوی که در شرایط چگالی کمتر، عملاً بخشی از ترافیک تولیدی به دلیل در اختیار نداشتن مسیری به سمت مقصد تلف میشد. به همین دلیل ما نیز از معیار فوق برای تعیین حداقل چگالی گرهها در مدل شبکه تحت بررسی استفاده میکنیم. بدین ترتیب چگالی گرهها باید به نحوی انتخاب گردد که مرتبه گراف (میانگین تعداد همسایگان گره ها) بین ۵ (حداقل) و ۱۰ (حداکثر) قرار گیرد. نتایج شبیهسازیها حاکی از اتلاف بیش از حد بستهها به دلیل تصادم در گرافهای با مرتبه بیش از ۱۰ میباشد.
 
مدل لینک مخابراتی بیسیم
برای مدل سازی لینک مخابراتی بیسیم که تحت استاندارد IEEE802.15.4 عمل میکند، از مدل متداول دیسک واحد[۵۰] استفاده شده است. در این مدل فرض می شود که گره تنها میتواند با گرههایی که در محیط دایرهای به شعاع رنج مخابراتی آن قرار میگیرند، تبادل داده داشته باشد. بدین ترتیب مجموعه همسایگان گره نیز شامل گرههایی که در این دیسک قرار میگیرند، می باشد.
به منظور مدل سازی لایه فیزیکی و اثر کاهش توان دریافتی ناشی از فاصله گرهها و عوامل محیطی نظیر محو[۵۱] و انعکاس[۵۲] امواج از مدل log-normal shadowing برای محاسبه قدرت سیگنال دریافتی در گره مقصد استفاده شده است. شاخص قدرت سیگنال دریافتی یا RSSI[53] روی لینک (i,j) ناشی از مدل فوق با استفاده از فرمول معروف ۱۲ محاسبه می شود [۷۸].
(۱۲
از سوی دیگر برای تصمیم گیری در خصوص دریافت صحیح یا ناصحیح بسته در لایه فیزیکی نیز از این شاخص استفاده میگردد به نحوی که اگر قدرت سیگنال دریافتی کمتر از حد پایین حساسیت آنتن گیرنده باشد بسته تلف شده و در غیر اینصورت سالم تلقی میگردد.
 
مکانیزم دسترسی به کانال مخابراتی
دسترسی به کانال مخابراتی از طریق پروتکل دسترسی به کانال مخابراتی از طریق پروتکل CSMA با زمانهای انتظار نمایی انجام میپذیرد. به طور ساده در این الگوریتم برای ارسال هر بسته ۴ بار تلاش صورت میپذیرد و در هر بار تلاش در صورت اشغال بودن کانال زمان انتظار به صورت نمایی افزایش مییابد. مدل کانال مخابراتی بیسیم و نحوه دسترسی به کانال با دقت زیاد در نرم افزار شبیهساز استفاده شده پیادهسازی شده تا اثر شرایط محیطی و تأخیر ناشی از دسترسی به کانال و اتلاف بستهها ناشی از انقضای تعداد تلاش برای دسترسی به کانال روی رفتار الگوریتمهای پیشنهادی به خوبی بررسی شود. لازم بذکر است که تمامی گرهها به لحاظ توان آنتن ارسال و دریافت و در نتیجه رنج مخابراتی همگن در نظر گرفته میشوند. البته در بخش‏۴‌.۲‌ یک مکانیزم توسعه رنج مخابراتی نیز برای دستیابی به عملکرد بهتر در مسیریابی پیشنهاد شده است که در همان فصل به طور مفصل مورد بحث قرار گرفته است. با توجه به موارد فوق میتوان گفت که مدل بکار رفته در این رساله به لحاظ تطابق با شرایط پیاده سازی واقعی به نحو مناسبی طراحی شده و از بسیاری از مدلهای استفاده شده در مقالات کاملتر میباشد.
 
تعریف مسأله توزیع ترافیک بهینه
در یک بستر مسیریابی بار متعادل نیاز به مکانیزمی برای توزیع بار ترافیکی مابین والدین موجود میباشد. اهداف ما از توزیع ترافیک در سطح شبکه را میتوان در ۳ بند زیر بیان نمود:
تولید درخت مسیریابی پوشا برای ایجاد امکان شناخت والدین ب

دانلود کامل پایان نامه در سایت pifo.ir موجود است.

القوه توسط فرزندان؛
ایجاد تعادل در نرخ مصرف انرژی گرههای هم مرتبه از طریق متعادلسازی بار ترافیکی تحمیلی به آنها در پروسه انتخاب والد ترجیحی، برای دستیابی به بیشترین طول عمر شبکه؛
افزایش رنج ارتباطی گرههای تک والد به منظور دستیابی به والدین بالقوه بیشتر، در راستای بهبود شرایط دستیابی به تعادل انرژی.
مجموعه راه حل های فوق در کار تحقیقاتی دیگری روی یک بستر مسیریابی چند مسیره مبتنی بر پروتکل RPL توسط نثاری مقدم و همکارانش تحت عنوان پروتکل MRPL ارائه شده است. [۷۹] این رساله با اقتباس راه حل های فوق, سعی در بهبود عمکلرد پروتکل UDDR به عنوان یک الگوریتم مسیریابی تک مسیره و تلفیق آن با پروتکل RPL در بخش تولید گراف اولیه دارد. به عبارت دیگر مکانیزم پیشنهادی در این رساله با استفاده از راهکارهای ارائه شده در [۷۹] نسبت به تولید نسخه توسعه یافته ای از تئوری بازی پیشنهادی در الگوریتم UDDR برای انتخاب والد مورد ترجیح در پروتکل مسیریابی RPL اقدام می کند. چگونگی دستیابی به اهداف فوق در فصل آتی مفصلا تشریح خواهد گردید.

فصل چهارم
الگوریتم مسیریابی درختی با هدف مصرف انرژی متوازن

الگوریتم مسیریابی درختی با هدف مصرف انرژی متوازن

با توسعه کاربردهای جدید طراحی شبکههای پایدار حسگر بیسیم یک مسئله بسیار چالش برانگیز است. از یک طرف، انتظار میرود حسگرها با انرژی محدود به صورت خودکار برای مدت طولانی کار کنند. این در حالی است که جایگزینی باتریهای از کار افتاده ممکن است هزینههای سنگین یا حتی در محیطهای سخت غیر ممکن باشد. از سوی دیگر، بر خلاف شبکههای دیگر، شبکههای حسگر بیسیم برای کاربردهای خاص مقیاس کوچک مانند سیستمهای نظارت پزشکی و مقیاس بزرگ مانند نظارت بر محیطزیست طراحی میشوند. در این زمینه، انبوهی از کار تحقیقاتی به منظور پیشنهاد یک طیف گستردهای از راهحلها برای مشکل صرفهجویی در انرژی انجام شده است. بنابراین، انتخاب راهحلهای کارآمد برای طراحی شبکههای حسگر بیسیم با در نطر گرفتن برنامههای خاص معماری در طراحی شبکههای حسگر بیسیم آسان نیست. در فصل دوم تعدادی از الگوریتمهای مسیریابی که با هدف تأمین توزیع ترافیک به منظور افزایش طول عمر در شبکههای حسگر بیسیم پیشنهاد شدهاند، مورد بررسی و نقاط ضعف آنها به طور مفصل تشریح گردید. از سوی دیگر چارچوب مد نظر برای تضمین توزیع ترافیک در این رساله در فصل سوم مورد بحث قرار گرفته شده است.
در ادامه این فصل یک الگوریتم تشکیل مسیر بار متعادل مبتنی بر پروتکل [۵۴]PBTR که عملاً یک مدل ارتقاء یافته از الگوریتم UDDR معرفی شده در فصل دوم است را پیشنهاد خواهیم نمود. این الگوریتم توزیع ترافیک بهینه برای پیادهسازی محلی و به منظور دستیابی به متعادلسازی بار با استفاده از تابع هدف جدید پیشنهادی که در معادله ۱۳ مطرح شده است. در این روش با در نظر گرفتن قابلیت افزایش نرخ ارتباطات، سعی در متعادلسازی بار موجود در هر گره داشته و به طور همزمان در راستای افزایش طول عمر شبکه حرکت میکند. نتایج عملکرد الگوریتم پیشنهادی PBTR با برخی از الگوریتمهای مشابه و معروف در فصل ۵ مورد مقایسه قرار گرفته شدهاند.
 
فاز ایجاد درخت
روش پیشنهادی برای تولید یک گراف مسیریابی، بر پایه الگوریتم مسیریابی استاندارد شده RPL بنا نهاده شده است. عمومیت و جامعیت الگوریتم RPL و امکانات مختلفی که در این پروتکل برای کشف مسیر، نگهداری مسیر و بروز رسانی آن دیده شده است، ایجاد گراف مسیریابی را با تغییرات کوچکی در مکانیزم اولیه و بدون نیاز به تغییر در اکثر توابع اصلی پروتکل میسر میسازد.
از آنجا که ترافیک مورد توجه در این رساله از نوع چند نقطه به یک نقطه است، مکانیزم مورد توجه ما نیز مکانیزم تشکیل مسیرهای پایین به بالا با استفاده از انتشار بسته های مسیریابی DIO میباشد. برای تولید گراف توسط الگوریتم PBTR، گرهها با توجه به تابع هدف مطرح شده در بخش ۳٫۴ گره والد ترجیحی خود را از میان گرههای والد احتمالی خود انتخاب میکنند. برای ایجاد راحتی در محاسبه رتبه و جلوگیری از ایجاد لوپهای احتمالی از معیار تعداد گام برای محاسبه رتبه گرهها استفاده میکنیم. این روش منجر به ایجاد گراف مسیریابی با مسیرهای هم طول و در هم تنیده خواهد شد. که در آن رتبه هر گره با عمق آن در گراف برابر خواهد بود.
بعد از تشکیل گراف اگر یک گره فرزند در گراف مسیریابی قرار نگرفت و یا در فضای استراتژی خود تنها به یک گره والد دسترسی داشته باشد، رنج ارتباطی خود را برای بدست آوردن حداقل ۲ والد افزایش میدهد. این کار به منظور افزایش توان متعادلسازی بار در بین گرههای والد صورت میگیرد که در بخش بعد مفصلا اشاره شده است. الگوریتم شبه کد ایجاد درخت را نشان میدهد.
جدول ۴‑۱ شبه کد ایجاد الگوریتم درخت مسیریابی

Algorithm 1: Graph generation