فهرست مطالب

عنوان                                                                            صفحه

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