بهینه سازی چند هدفه در شبکه های حسگر بی سیم سلسله مراتبی با استفاده از روش فراکتشافی

توضیحات

بهینه سازی چند هدفه در شبکه های حسگر بی سیم سلسله مراتبی با استفاده از روش فراکتشافیفهرست مطالب عنوان صفحه چكيده 1 فصل اول کلیات تحقیق 1-1- مقدمه. 2 1-2- بيان مسأله. 2 1-3- اهمیت و ضرورت انجام تحقيق.. 3 1-4- جنبه جديد بودن و نوآوري در تحقيق.. 4 1-5- اهداف مشخص تحقيق.. 4 1-6- نام بهره‏وران. 4 1-7- سؤالات تحقیق.. 4 1-8- فرضيه‏هاي تحقیق.. 4 1-9- ساختار پایان نامه. 5 1-10- جمع بندی.. 5 فصل دوم ادبیات و پیشینه تحقیق 2-1- مقدمه. 6 2-2- مکانیزم های ذخیرهسازی انرژی در شبکههای حسگر بیسیم. 7 2-2-1- بهینهسازی رادیو. 7 2-2-2-کاهش حجم اطلاعات... 10 2-2-3-طرح خواب و بیدار. 12 2-3- مسیریابی با کارایی انرژی.. 14 2-4- راه حل شارژ. 16 2-5- ویژگی های شبکه های حسگر بیسیم از منظر مسیریابی.. 17 2-6- الزامات طراحی الگوریتم های مسیریابی در شبکه های حسگر. 19 2-7- بررسی کاستیهای الگوریتم های مسیریابی موجود. 23 2-8- دستاوردها و نوآوری های این پایان نامه. 27 2-9- الگوریتم های مسیریابی نامبتنی بر ساختار. 29 2-9-1- الگوریتم های جغرافیایی.. 29 2-9-2- الگوریتم های مبتنی بر هوش مصنوعی و تئوری مورچگان. 32 2-9-3- الگوریتم های خوشه بندی.. 35 2-10- الگوریتم های مبتنی بر ساختار. 39 2-10-1- الگوریتمRPL.. 40 2-10-1-2- گراف مسیریابی جهت دار مبتنی بر مقصد (DODAG). 41 2-10-1-3- شناسه های پروتکل.. 42 2-10-1-4 - تشکیل مسیر در گراف... 43 2-1-10-5- معیارهای وزن دهی مسیر در پروتکل RPL.. 43 2-10-1-6- الگوریتم LB_RPL.. 46 2-10-1-7- الگوریتمUDCB.. 47 2-11- الگوریتمUDDR.. 48 2-11-1- فاز انتخاب والد. 50 2-11-1-1- حرکت خودخواهانه. 51 2-11-1-2- بازی مشترک... 51 2-11-1-3- فاز اتصال. 52 2-12- سوابق پژوهش.... 54 2-13-جمع بندی.. 62 فصل سوم روش پیشنهادی 3-1- مقدمه. 63 3-2- مدل شبکه مورد بررسی و تعریف مسأله مسیریابی بهینه. 64 3-2-1- هم بندی شبکه. 64 3-2-2- چگالی گره ها 65 3-3- مدل لینک مخابراتی بیسیم. 66 3-4- مکانیزم دسترسی به کانال مخابراتی.. 67 3-5- تعریف مسأله توزیع ترافیک بهینه. 67 3-6- فاز ایجاد درخت... 68 3-7- بررسی اثر افزایش رنج مخابراتی.. 69 3-8- نحوه انتخاب والد ترجیحی.. 72 3-9- تحلیل پیچیدگی الگوریتم PBLD... 78 3-10- محاسبه مقادير شايستگي.. 79 فصل چهارم شبیه سازی و نتایج 4-1- مقدمه. 86 4-2- چارچوب شبیه سازی و مقایسه نتایج عملکرد. 87 4-2-1- محیط شبیه سازی.. 87 4-2-2- پارامترهای شبیه سازی.. 88 4-2-3- سناریوهای شبیه سازی.. 89 4-4- نتایج شبیه سازی.. 90 4-4-1- عملکرد الگوریتم PBTR با توجه به تعداد گرهها 90 4-4-2- عملکرد الگوریتم PBTR با توجه به تعداد گرههای تولید کننده ترافیک.... 92 4-4-3- عملکرد الگوریتم PBTR با توجه به نرخ تولید ترافیک متغیر. 94 4-4-4- ايجاد همسايگي تصادفي ذرات... 96 4-4-5- بهبود همسايگي ذرات... 96 4-4-6- تشکيل و بهنگام سازي مجموعه مرجع (RSet) 97 4-4-7- متنوع سازي ذرات... 97 4-4-8- جستجوي محلي.. 98 4-4-9- نتايج محاسباتي.. 98 4-4-10- چگونگي ايجاد مسایل نمونه. 99 4-5- مفروضات و پارامترهاي الگوريتمها 101 4-5-1 الگوريتم ژنتيک.... 101 4-5-2- الگوريتم بهينهسازي گروه ذرات بهبوديافته. 101 4-5-3- نتايج عددي.. 102 4-5-4- تحليل حساسيت... 110 4-6- جمع بندی.. 118 فصل پنجم بحث، نتیجه گیری و پیشنهادها 5-1- مقدمه. 119 5-2- جمع‌بندي.. 119 5-3- نتیجه گیری.. 120 5-4- پیشنهادات (کار درآینده ) 122 منابع و مآخذ. 123 اختصارات... 130 فهرست جداول عنوان صفحه جدول 3-1 نتايج حاصل از حل مسایل نمونه با استفاده از LP-IPSO و IPSO... 83 جدول 4‑3 پارامترهای شبیهسازی.. 90 جدول 4-3- چگونگي ايجاد مسایل نمونه. 100 جدول 4-4- نحوه توليد پارامترهاي مسایل نمونه. 100 جدول 4-5- ميانگين مقدار تابع هدف و زمان محاسباتي حل مسایل نمونه تصادفي با ابعاد كوچك.... 103 جدول 4-6- ميانگين مقدار تابع هدف و زمان محاسباتي حل مسایل نمونه تصادفي با ابعاد بزرگ... 105 جدول 4-7- ميزان استواري الگوريتمها در حل مسایل نمونه تصادفي با ابعاد كوچك.... 110 جدول 4-8- ميزان استواري الگوريتمها در حل مسایل نمونه تصادفي با ابعاد بزرگ... 111 جدول 4-9- مقادير پارامترهاي مسأله در حالات مختلف براي تحليل حساسيت... 111 فهرست الگوریتم ها عنوان صفحه الگوریتم 3‑1- شبه کدایجادالگوریتم درخت مسیریابی.. 69 الگوریتم 3‑2 شبه کدالگوریتم افزایش توان ارسالی گره 72 الگوریتم 3-3 نقش گره v به عنوان گره والد. 76 الگوریتم 3-4 نقش گرهuبه عنوان گره فرزند. 77 فهرست اشکال عنوان صفحه شکل2‑1- طبقهبندی مکانیزمهای ذخیرهسازی انرژی.. 7 شکل2‑3- معماری پیشنهادی ارتباطات سه لایه. 38 شکل 3‑1 یک برشی ازشبکه. 70 شکل3‑2 برشی ازشبکه بعدازافزایش رنج مخابراتی.. 71 شكل 3-3 ميزان اختلاف زمان محاسباتي موردنياز براي حل مسایل نمونه با استفاده از LP-IPSO و IPSO 84 شکل 4‑3- نمونهای ازگراف مسیریابی الگوریتمPBTR.. 88 شکل 4‑4- نمودارمیزان طول عمرالگوریتمهادربرابرباتعدادگرهها 91 شکل 4‑5- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرتعدادگرهها 92 شکل 4‑6- نمودارمیزان طول عمرالگوریتمهادربرابرتعدادگرههای تولیدکننده ترافیک.... 93 شکل 4‑7- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرتعدادگرههای تولیدکننده ترافیک.... 94 شکل 4‑8- نمودارمیزان طول عمرالگوریتمهادربرابرنرخ تولیدترافیک توسط گرهها 95 شکل 4‑9- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرنرخ تولیدترافیک توسط گرهها 96 شكل 4-9 نحوه انجام عملگر جهش.... 97 شكل 4-10 تحليل واريانس دو طرفه بر روي نتايج حاصل از حل مسایل با ابعاد كوچك.... 106 شكل 4-11 تحليل واريانس دو طرفه بر روي نتايج حاصل از حل مسایل با ابعاد بزرگ... 106 شكل 4-12 مقايسه زمان محاسباتي الگوريتم پيشنهادي و الگوريتمهاي معيار در حل مسایل با ابعاد كوچك 107 شكل 4-13 مقايسه زمان محاسباتي الگوريتم پيشنهادي و الگوريتمهاي معيار در حل مسایل با ابعاد بزرگ 108 شكل 4-14 تحليل حساسيت نسبت به پارامتر Q... 113 شكل 4-15 تحليل حساسيت نسبت به پارامتر ...... 114 شكل 4-15 تحليل حساسيت نسبت به پارامتر ... 115 شكل 4-16 تحليل حساسيت نسبت به پارامتر ........... 116 شكل 4-17 تحليل حساسيت نسبت به پارامتر ........... 117 فهرست اشکال عنوان صفحه شکل2‑1- طبقهبندی مکانیزمهای ذخیرهسازی انرژی.. 8 شکل2‑3- معماری پیشنهادی ارتباطات سه لایه. 38 شکل 3‑1 یک برشی ازشبکه. 70 شکل3‑2 برشی ازشبکه بعدازافزایش رنج مخابراتی.. 71 شكل 3-3 ميزان اختلاف زمان محاسباتي موردنياز براي حل مسایل نمونه با استفاده از LP-IPSO و IPSO 84 شکل 4‑3- نمونهای ازگراف مسیریابی الگوریتمPBTR.. 88 شکل 4‑4- نمودارمیزان طول عمرالگوریتمهادربرابرباتعدادگرهها 91 شکل 4‑5- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرتعدادگرهها 92 شکل 4‑6- نمودارمیزان طول عمرالگوریتمهادربرابرتعدادگرههای تولیدکننده ترافیک.... 93 شکل 4‑7- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرتعدادگرههای تولیدکننده ترافیک.... 94 شکل 4‑8- نمودارمیزان طول عمرالگوریتمهادربرابرنرخ تولیدترافیک توسط گرهها 95 شکل 4‑9- نموداردرصدسالم رسیدن بستههای ترافیکی دربرابرنرخ تولیدترافیک توسط گرهها 96 شكل 4-9 نحوه انجام عملگر جهش.... 97 شكل 4-10 تحليل واريانس دو طرفه بر روي نتايج حاصل از حل مسایل با ابعاد كوچك.... 106 شكل 4-11 تحليل واريانس دو طرفه بر روي نتايج حاصل از حل مسایل با ابعاد بزرگ... 106 شكل 4-12 مقايسه زمان محاسباتي الگوريتم پيشنهادي و الگوريتمهاي معيار در حل مسایل با ابعاد كوچك 107 شكل 4-13 مقايسه زمان محاسباتي الگوريتم پيشنهادي و الگوريتمهاي معيار در حل مسایل با ابعاد بزرگ 108 شكل 4-14 تحليل حساسيت نسبت به پارامتر Q... 113 شكل 4-15 تحليل حساسيت نسبت به پارامتر ...... 114 شكل 4-15 تحليل حساسيت نسبت به پارامتر ... 115 شكل 4-16 تحليل حساسيت نسبت به پارامتر ........... 116 شكل 4-17 تحليل حساسيت نسبت به پارامتر ........... 117 چكيده امروزه با توجه به مزایای شبکه­های حسگر بی­سیم که همانا پیاده­­سازی ساده و ارزان، مصرف توان پایین و مقیاس­پذیری بالای آنها است، در بسیاری از کاربردها مورد استفاده قرار گرفته­اندطراحی شبکه­های پایدار حسگر بی­سیم یک مسئله بسیار چالش برانگیز است انتظار می­رود حسگرها با انرژی محدود به صورت خودکار برای مدت طولانی کار کننداین در حالی است که جایگزینی باتری­های ازکارافتاده ممکن است با هزینه­های سنگین یا حتی در محیط­های سخت غیر ممکن باشد. از سوی دیگر، بر خلاف شبکه­های دیگر، شبکه­های حسگر بی­سیم برای کاربردهای خاص مقیاس کوچک مانند سیستم­های نظارت پزشکی و مقیاس بزرگ مانند نظارت بر محیط­زیست طراحی می­شوند.در این زمینه، انبوهی از کار تحقیقاتی به منظور پیشنهاد طیف گسترده­ای از راه­حل­ها برای مشکل صرفه جویی در انرژی انجام شده است در این پایان نامه یک الگوریتم فرا اکتشافی مسیریابی برای تولید بهترين مسير مابين گره­هاي حسگر و گره جمع­كننده محلي و با هدف دستيابي به توزيع ترافيك مناسب و درنتيجه ايجاد تعادل در مصرف انرژي گره­هاي مياني طراحی شده است ايجاد چنين تعادلي به افزايش طول عمر شبكه كمك مي­كند و بهبود الگوي مصرف انرژي و در واقع بهینه سازی در شبكه­هاي حسگر بي­سيم با منابع انرژي محدود را به دنبال خواهد داشت از سوی دیگر با استفاده از امکان تغییر رنج گره­ها، سعی می­شود تا امکان توزیع بار در نقاط کم تراکم شبکه نیز افزایش یابدنتايج حاصل از شبيه­سازي­ها نشانگر بهبود 20 درصدي در طول عمر شبكه با استفاده از الگوريتم پيشنهادي در مقايسه با برخي از الگوريتم­هاي مسيريابي حساس به انرژي پيشنهادي در سال­هاي اخير مي­باشد.