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

توضیحات

بهینه سازی چند هدفه در شبکه های حسگر بی سیم سلسله مراتبی با استفاده از روش فراکتشافی
فهرست مطالب
عنوان صفحه
چكيده 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 درصدي در طول عمر شبكه با استفاده از الگوريتم پيشنهادي در مقايسه با برخي از الگوريتم­هاي مسيريابي حساس به انرژي پيشنهادي در سال­هاي اخير مي­باشد.