دانلود پروژه: یک روش خوشه بندی بهبود یافته با استفاده از الگوریتم ژنتیک به منظور کاهش مصرف انرژی و تاخیر در شبکه های حسگر بی سیم

فهرست مطالب
فصل اول – کلیات تحقیق ……………………………………………………………………………………………………………1
1-1 بيان مسأله اساسي تحقيق………………………………………………………………………………………………………………………………2
1-2 اهمیت و ضرورت تحقیق…………………………………………………………………………………………………………………………..3
1-3 سوالات و فرضیات تحقیق……………………………………………………………………………………………………………………………3
1- 4 اهداف تحقیق…………………………………………………………………………………………………………………………………………..4
1-5 ساختار پایان نامه…………………………………………………………………………………………………………………………………………4
فصل دوم – مفاهیم اولیه …………………………………………………………………………………………………………….5
2-1 شبکه های حسگر بی سیم……………………………………………………………………………………………………………………………..6
2-1-1 ويژگي‌هاي عمومي يك شبكه حسگر…………………………………………………………………………………………………………14
2-1-2 ساختار ارتباطي شبکه‌هاي حسگر………………………………………………………………………………………………………………15
2-1-3 فاکتورهاي طراحي…………………………………………………………………………………………………………………………………..15
2-1-4 معماري سخت افزاري یک گره شبکه حسگر بی سیم………………………………………………………………………………….21
2-1-5 سیستم عامل…………………………………………………………………………………………………………………………………………..25
2-1-6 کاربردها و مزایاي استفاده از شبکه هاي حسگر………………………………………………………………………………………….26
2-1-7 محدودیتهاي سخت افزاري یک گره حسگر……………………………………………………………………………………………….35
2-2 الگوریتمهای تکاملی……………………………………………………………………………………………………………………………………39
2-2-1 ساختار الگوريتم‏هاي ژنتيكي……………………………………………………………………………………………………………………42
2-2-2 عملگرهاي ژنتيكي………………………………………………………………………………………………………………………………….43
2-2-3 روند كلي الگوريتم‏هاي ژنتيكي…………………………………………………………………………………………………………………46
2-2-4 آشنايي با روش‏هاي انتخاب در الگوريتم‏هاي ژنتيكي…………………………………………………………………………………..49
2-2-5 شرط پايان الگوريتم…………………………………………………………………………………………………………………………………58
2-2-6 برخي از كاربرد الگوريتم‏هاي ژنتيكي………………………………………………………………………………………………………….59
2-3 نتیجه گیری…………………………………………………………………………………………………………………………………………………59
فصل سوم – مروری بر کارهای انجام شده ………………………………………………………………………………….60
3-1 ﻣﻔﺎﻫﯿﻢ ﺧﻮﺷﻪﺑﻨﺪي……………………………………………………………………………………………………………………………………….61
3-2 اﻟﮕﻮرﯾﺘﻢﻫﺎي ﺧﻮﺷﻪﺑﻨﺪي بدون استفاده از الگوریتمهای تکاملی………………………………………………………………………….66
3-2-1 اﻟﮕﻮرﯾﺘﻢ LEACH ‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬‬………………………………………………………………………………………………………………………………….67
3-2-2 اﻟﮕﻮرﯾﺘﻢ Centralized)) LEACH-C…………………………………………………………………………………………………….78
3-2-3 الگوریتم Fixed (LEACH-F)………………………………………………………………………………………………………………….79
3-2-4 الگوریتم (Multi Hop) M-LEACH ……………………………………………………………………………………………………….79
-2-5 الگوریتم PEGASIS ………………………………………………………………………………………………………………………………….80
3-2-6 اﻟﮕﻮرﯾﺘﻢ FLOC…………………………………………………………………………………………………………………………………….82
3-3- خوشه بندی بکمک الگوریتمهای تکاملی………………………………………………………………………………………………………86
3-3-1 مقاله جین و همکاران……………………………………………………………………………………………………………………………….86
3-3-2 روش GCA…………………………………………………………………………………………………………………………………………….87
3-3-3 روش شکشوکی و مالیک…………………………………………………………………………………………………………………………..88
3-3-4 روش الگوریتم جستجوی تطبیقی……………………………………………………………………………………………………………….88
2-3-5 روش ERP……………………………………………………………………………………………………………………………………………..89
2-3-6 روش Eaerp………………………………………………………………………………………………………………………………………….89
فصل چهارم – روش پیشنهادی ………………………………………………………………………………………………….91
4-1 تعاریف اولیه………………………………………………………………………………………………………………………………………………..92
4-2 فقدان بسته…………………………………………………………………………………………………………………………………………………..93
4-2-1 بسته های گمشده در شبکه حسگر بیسیم……………………………………………………………………………………………………96
4-2-2 مطالعات اولیه پیرامون تعیین فقدان بسته در شبکه حسگر بیسیم…………………………………………………………………….96
4-2-3 تشریح تنظیمات آزمایشگاهی……………………………………………………………………………………………………………………96
4-3 تاخیر…………………………………………………………………………………………………………………………………………………………99
4-4 شرح روش پیشنهادی………………………………………………………………………………………………………………………………..101
فصل پنجم – پیاده سازی و ارزیابی ……………………………………………………………………………………..110
5-1 مقدمات شبیه سازی………………………………………………………………………………………………………………………………….111
5-2 پارامترهای شبیه سازی………………………………………………………………………………………………………………………………112
5-3- پارامترهای مصرف انرژی……………………………………………………………………………………………………………………….113
5-4- نتایج شبیه سازی……………………………………………………………………………………………………………………………………115
5-4-1- سناریوی اول…………………………………………………………………………………………………………………………………….115
5-4-2 سناریوی دوم………………………………………………………………………………………………………………………………………119
5-4-3 سناریوی سوم……………………………………………………………………………………………………………………………………..122
5-5 جمع بندی………………………………………………………………………………………………………………………………………………125
فصل ششم – نتیجه گیری و پیشنهادها …………………………………………………………………………………127
6-1 نتیجه گیری…………………………………………………………………………………………………………………………………………….128
6-2 کارهای آتی…………………………………………………………………………………………………………………………………………….131
منابع…………………………………………………………………………………………………………………………………………………133

فهرست شکل¬ها
شکل 2-1 شبکه زیر ساخت پایه………………………………………………………………………………………………………………………….9
شکل 2-2 نمونه ای از شبکه های موردی…………………………………………………………………………………….9
شکل 2-3 گره هاي حسگر پراکنده شده در ناحیه حس شونده……………………………………………………….12
شکل 2-4 ساختار کلی و واحدهاي یک گره حسگر…………………………………………………………………..22
شکل 2-5 برخی از کابردهای شبکه حسگر بیسیم……………………………………………………………………….26
شکل 2-6 طبقه بندي و خلاصه اي از کاربردهاي شبکه هاي حسگر بی سیم………………………………….31
شکل 2-7 یک کروموزوم قبل و بعد از اعمال عملگر جهش…………………………………………………………45
شكل 2-8 يك الگوريتم ژنتيكي استاندارد………………………………………………………………………………….47
شکل 2-9 نمودار گردشي الگوريتم‏هاي ژنتيكي…………………………………………………………………………..48
ﺷﮑﻞ3-1 : ﺧﻮﺷﻪﺑﻨﺪي ﺷﺒﮑﻪﻫﺎي حسگر بیسیم…………………………………………………………………………..62
ﺷﮑﻞ3-2: ﺧﻮﺷﻪ ﺑﻨﺪي و اﻧﻮاع گره-ها…………………………………………………………………………………………63
ﺷﮑﻞ3-3 : ﻧﺤﻮه ارﺗﺒﺎط ﺑﯿﻦ اﻋﻀﺎء ﺧﻮﺷﻪ ﺑﺎ سرخوشه………………………………………………………………….64‬‬‬‬‬‬‬
ﺷﮑﻞ3-4: ﻧﻘﺶ دروازه ﻫﺎ دراﯾﺠﺎد ارﺗﺒﺎط ﺑﯿﻦ ﺧﻮﺷﻪ ﻫﺎ……………………………………………………………….66
ﺷﮑﻞ3-5: دو ﻧﻤﻮﻧﻪ از اﺟﺮاي اﻟﮕﻮرﯾﺘﻢ LEACH‬……………………………………………………………………………………………..68‬‬‬‬‬‬‬‬‬‬‬‬‬‬
ﺷﮑﻞ3-6: ﻣﺮاﺣﻞ اﺟﺮاي اﻟﮕﻮرﯾﺘﻢ LEACH‬………………………………………………………………………………………………………69‬‬‬‬‬‬‬‬‬‬‬‬‬‬
ﺷﮑﻞ3-7: مراحل ﺷﮑﻞﮔﯿﺮي ﺧﻮﺷﻪﻫﺎ در اﻟﮕﻮرﯾﺘﻢ LEACH‬………………………………………………………………………..72‬‬‬‬‬‬‬
ﺷﮑﻞ3-8: اﺧﺘﺼﺎص ﻗﺴﻤﺘﻬﺎﯾﯽ ﺑﺮاي ﻫﺮ گره در ﻓﺎز حالت پایداری………………………………………………..73‬‬‬‬‬‬‬
ﺷﮑﻞ 3-9 : مراحل اجرای فاز حالت پایداری الگوریتم LEACH ………………………………………………75
‬ﺷﮑﻞ3-10: ﻧﻤﻮدار ﺗﻌﯿﯿﻦ P (درﺻﺪ سرخوشهﻫﺎ)………………………………………………………………………….‬‬‬‬‬‬‬77‬‬‬‬‬‬‬
ﺷﮑﻞ 3-11: اﺿﺎﻓﻪ ﺷﺪن ﮔﺮه j ………………………………………………………………………………………………….‬83‬‬‬‬‬‬‬
ﺷﮑﻞ 3-12: ﺳﺮﮔﺮوه ﺷﺪن ﮔﺮه j‬…………………………………………………………………………………………………………………………..‬83‬‬‬‬‬‬‬
ﺷﮑﻞ 3-13: ﻋﻀﻮ ﮔﯿﺮي ﮔﺮه j ………………………………………………………………………………………………….‬83‬‬‬‬‬‬‬
ﺷﮑﻞ 3-14: ﺣﺎﻟﺖ ﻫﺎي ﻣﺨﺘﻠﻒ ﺣﺴﮕﺮ……………………………………………………………………………………..85
شکل 4-1 نمونه¬ای از آزمایش انجام شده……………………………………………………………………………………98
شکل 4-2 نمودار گردش جریان طرح پیشنهادی………………………………………………………………………..109
شکل 5-1 : توزیع 300 گره بصورت تصادفی در محیط 200*200……………………………………………..111
شکل 5-2 : توزیع 100 گره بصورت تصادفی در محیط 200*200……………………………………………..112
شکل 5-3 : اجزای مصرف انرژی برای ارسال/دریافت……………………………………………………………….114
شکل 5-4 اولین گره خاموش در روش¬های LEACH، EAERP و پیشنهادی………………………………….116
شکل 5-5 خاموشی نیمی از گره¬ها در روش¬های LEACH، EAERP و پیشنهادی…………………………..117
شکل 5-6 روند مصرف انرژی در سناریوی اول………………………………………………………………………..117
شکل 5-7 روند خاموشی گره¬ها در سناریوی اول………………………………………………………………………118
شکل 5-8 روند تاخیر در دورهای شبکه در سناریوی اول…………………………………………………………..118
شکل 5-9 اولین گره خاموش در روش¬های LEACH، EAERP و پیشنهادی………………………………….119
شکل 5-10 خاموشی نیمی از گره¬ها در روش¬های LEACH، EAERP و پیشنهادی…………………………120
شکل 5-11 روند مصرف انرژی در سناریوی دوم……………………………………………………………………..121
شکل 5-12 روند خاموشی گره¬ها در سناریوی دوم……………………………………………………………………121
شکل 5-13 روند تاخیر در دورهای شبکه در سناریوی دوم………………………………………………………..122
شکل 5-14 اولین گره خاموش در روش¬های LEACH، EAERP و پیشنهادی در سناریوی سوم………123
شکل 5-15 خاموشی نیمی از گره¬ها در روش¬های LEACH، EAERP و پیشنهادی در سناریوی سوم……123
شکل 5-16 روند مصرف انرژی در سناریوی سوم……………………………………………………………………..124
شکل 5-17 روند خاموشی گره¬ها در سناریوی سوم…………………………………………………………………..124
شکل 5-18 روند تاخیر در دورهای شبکه در سناریوی سوم ……………………………………………….125

فهرست جداول
جدول 4-1. تغییرات فقدان بسته¬ی کشف شده بوسیله¬ی فاصله……………………………………………………..99
جدول 5-1. پارامترهای اولیه¬ی شبیه-سازی………………………………………………………………………………..113
جدول 6-1 مقایسه¬ای بین روش پیشنهادی، EAERP و LEACH…………………………………………………129
جدول 6-2 مقایسه¬ی اولین گره¬ی خاموش در روش¬های پیشنهادی، EAERP و LEACH……………….130
جدول 6-3 مقایسه¬ی خاموشی نصف گره¬ها در روش¬های پیشنهادی، EAERP و LEACH……………..130
جدول 6-4 مقایسه¬ی تاخیر در روش¬های پیشنهادی، EAERP و LEACH………………………………131