1-4-                     آتوماتای یادگیر سلولی 40

 

1-4-1- آتوماتای سلولی 40

 

1-4-2- آتوماتای یادگیر سلولی (CLA) 44

 

1-4-3- آتوماتای یادگیر سلولی نامنظم (ICLA) 47

 

1-5-                     اهداف پایان نامه و ساختار آن 48

 

2-  پوشش محیط در شبكه های حسگر بی سیم با استفاده از آتوماتاهای یادگیرسلولی 50

 

2-1-                     مقدمه……………………………. ……………………………. 50

 

2-1-1- اشكال مختلف طراحی 51

 

2-2-                     دسته بندی مسائل پوشش در شبکه های حسگر 52

 

2-2-1- پوشش ناحیه ای 53

 

2-2-2- پوشش نقطه ای 56

 

2-2-3- پوشش مرزی………………………………… ………………………………… 57

 

2-3-                     روش پوشش CCP 59

 

2-3-1- فرضیات مسئله 59

 

2-3-2- تشریح روش………………………………… ………………………………… 59

 

2-4-                     حل مسئله پوشش(k-پوششی ) با استفاده از آتوماتاهای یادگیر 61

 

2-4-1- فرضیات و مدل مسئله 63

 

2-4-2- روش تشخیص افزونه بودن نود حسگر 64

 

2-4-3- شبیه سازی………………………………… ………………………………… 72

 

2-5-                     جمع بندی…………………………. …………………………. 79

 

3-  خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی 80

 

3-1-                     مقدمه……………………………. ……………………………. 80

 

3-2-                     کارهای انجام شده 83

 

3-2-1- پروتکل خوشه بندی LEACH 85

 

3-2-2- پروتکل خوشه بندی HEED 88

 

3-3-                     خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی 93

 

3-3-1- روش خوشه بندی پیشنهادی 94

 

3-3-2- شبیه سازی………………………………… ………………………………… 102

 

3-4-                     جمع بندی…………………………. …………………………. 107

 

4-  تجمیع داده ها در شبكه های حسگر با استفاده از آتوماتاهای یادگیر 108

 

4-1-                     مقدمه……………………………. ……………………………. 108

 

4-2-                     كارهای انجام گرفته 109

 

4-3-                     تجمیع داده ها در شبكه های حسگر با استفاده از آتوماتاهای یادگیر 112

 

4-3-1- بیان مسئله و مفروضات آن 113

 

4-3-2- تشریح روش پیشنهادی 115

 

4-4-                     شبیه سازی………………………… ………………………… 119

 

4-4-1- آزمایش اول……………………………….. ……………………………….. 122

 

4-4-2- آزمایش دوم……………………………….. ……………………………….. 122

 

4-4-3- آزمایش سوم……………………………….. ……………………………….. 123

 

4-5-                     جمع بندی…………………………. …………………………. 125

 

5-  نتیجه گیری 126

 

6-  پیوست اول: شبكه های حسگر بی سیم 127

 

6-1-                     تاریخچه شبكه های حسگر 127

 

6-2-                     ساختار هر گره حسگر 128

 

6-2-1- اجزاء درونی یک گره حسگر 128

 

6-2-2- محدودیتهای سختافزاری یک گره حسگر 130

 

6-3-                     پشته پروتکلی 131

 

6-4-                     مزایای شبکه های حسگر بیسیم 132

 

6-5-                     کاربردهای شبکه های حسگر بیسیم 134

 

7-  پیوست دوم:آتوماتای یادگیرسلولی 138

 

7-1-                     تاریخچه آتوماتای یادگیر 138

 

7-2-                     معیار‌های رفتار اتوماتای یادگیر 139

 

7-3-                     آتوماتای یادگیر با عملهای متغیر 141

 

 

7-4-                     آتوماتای یادگیر تعقیبی 142

 

7-5-                     آتوماتای یادگیر سلولی (CLA) 150

 

7-6-                     آتوماتای یادگیر سلولی باز(OCLA) 151

 

7-7-                     آتوماتای یادگیر سلولی ناهمگام (ACLA) 152

 

8-  پیوست سوم: شرح نرم افزار J-Sim و پیاده سازی الگوریتمهای پیشنهادی با آن 155

 

8-1-                     مقدمه……………………………. ……………………………. 155

 

8-2-                     شبیه ساز J-Sim 158

 

8-2-1- شبیه سازی شبکه های حسگر بی سیم با استفاده از J-sim 158

 

8-2-2- نصب و اجرا……………………………….. ……………………………….. 162

 

8-3-                     پیاده سازی الگوریتم خوشه بندی پیشنهادی 163

 

8-4-                     پیاده سازی الگوریتم پوشش پیشنهادی 185

 

8-5-                     پیاده سازی الگوریتم تجمیع پیشنهادی 190

 

9-  واژه نامه 195

 

مراجع 199

 

فهرست شکلها

 

شکل ‏1‑2: یك مدل ساده از QoS 19

 

شکل ‏1‑3: نحوة عملكرد پروتكل RSVP 22

 

شکل ‏1‑4 : اتوماتای یادگیر تصادفی 33

 

شکل ‏1‑5: (الف) همسایگی مور –  (ب) همسایگی ون نیومن برای اتوماتای سلولی 42

 

شکل ‏1‑6: قانون 54 47

 

شکل ‏1‑7: آتوماتای یادگیر سلولی نامنظم 48

 

شکل ‏2‑11:  محاسبه  MaxIteration مناسب جهت بدست اوردن پوشش كامل در شبكه 74

 

شکل ‏2‑12 :  مقایسه تعداد نودهای فعال در روشهای پوشش با درجه پوشش یك 75

 

شکل ‏2‑13 : مقایسه تعداد نودهای فعال در روشهای پوشش با درجات پوشش 2 و 3 75

 

شکل ‏2‑14 : مقایسه نسبت میانگین انرژی نودهای فعال نسبت به میانگین انرژی نودهای غیرفعال با درجه پوشش یك 76

 

شکل ‏2‑15 : مقایسه نسبت میانگین انرژی نودهای فعال نسبت به میانگین انرژی نودهای غیرفعال با درجه پوشش دو 76

 

شکل ‏2‑16 : مقایسه نسبت میانگین انرژی نودهای فعال نسبت به میانگین انرژی نودهای غیرفعال با درجه پوشش سه 77

 

شکل ‏2‑17 : مقایسه طول عمر شبكه(زمان از بین رفتن اولین نود) در حالتهای مختلف 78

 

شکل ‏2‑18 : مقایسه میزان انرژی مصرفی در الگوریتم پوشش نسبت به كل انرژی مصرفی 79

 

شکل ‏3‑1: ارتباطات تک گامی و چندگامی بدون خوشه بندی 81

 

شکل ‏3‑2: ارتباطات تک گامی و چندگامی با استفاده از خوشه بندی 82

 

شکل ‏3‑3: شبه كد الگوریتم HEED 93

 

شکل ‏3‑4 : مقایسه تعداد خوشه های ایجاد شده در روشهای مختلف خوشه بندی 104

 

شکل ‏3‑5: مقایسه درصد خوشه های خالی ایجاد شده در روشهای مختلف خوشه بندی 105

 

شکل ‏3‑6: مقایسه نرخ میانگین انرژی سرخوشه ها نسبت به میانگین انرژی نودهای معمولی 105

 

شکل ‏3‑7: مقایسه ضریب تغییرات اندازه خوشه ها در روشهای مختلف خوشه بندی 106

 

شکل ‏3‑8: مقایسه طول عمر شبکه در روشهای مختلف خوشه بندی 107

 

شکل ‏4‑1: محیط حسگری با نواحی A تا F و حسگرهای واقع در آنها 115

 

شکل ‏4‑2: حسگرهای H ,F ,G ,E ,C ,A و J در یك ناحیه واقعند و تشكیل یك ائتلاف می دهند 118

 

شکل ‏4‑3: محیط حسگری به 9 ناحیه مختلف با داده های متفاوت تقسیم بندی شده است 120

 

شکل ‏4‑4: محیط حسگری در زمان 250 دقیقه 120

 

شکل ‏4‑5: محیط حسگری در زمان 500 دقیقه 121

 

شکل ‏4‑6: محیط حسگری در زمان 750 دقیقه 121

 

شکل ‏4‑7: مقایسه تعداد كل بسته های دریافتی توسط نود سینك در روشهای مختلف 122

 

شکل ‏4‑8: مقایسه كل انرژی مصرفی توسط نودها در روشهای مختلف 123

 

شکل ‏4‑9: مقایسه طول عمر شبکه در روشهای مختلف تجمیع 124

 

شکل ‏4‑10: مقایسه میزان انرژی مصرفی در الگوریتم تجمیع نسبت به كل انرژی مصرفی 124

 

شکل ‏6‑1 : اجزاء درونی یک گره حسگر 129

 

شکل ‏6‑2 : پشته پروتکلی شبکه های حسگر 131

 

شکل ‏6‑3 : نمونه کاربردهای شبکه های حسگر بیسیم 135

 

شکل ‏8‑1 : محیط شبکه حسگربی سیم 159

 

شکل ‏8‑2 : مدل یک نود حسگربی سیم 159

 

شکل ‏8‑3 : تنظیم jdk در نرم افزار J-Sim 162

 

شکل ‏8‑4 : اجرای نرم افزار J-Sim 163

 

 

 

 

 

چکیده

 

کیفیت سرویس در شبکه های حسگر بی سیم نسبت به شبکه های سنتی بسیار متفاوت است. بعضی از پارامترهایی که در ارزیابی کیفیت سرویس در این شبکه ها مورد استفاده قرار می گیرند عبارتند از: پوشش شبکه, تعداد بهینه نودهای فعال در شبکه, طول عمر شبکه و میزان مصرف انرژی. در این پایان نامه سه مسئله اساسی شبكه ها ی حسگر بی سیم مطرح گردیده و با هدف بهبود پارامترهای کیفیت سرویس، برای این مسائل، راه حلهایی کارا با استفاده از روش هوشمند آتوماتاهای یادگیرسلولی ارائه شده است. ابتدا مسئله پوشش محیط در شبكه های حسگر را با استفاده از غیر فعال نمودن نودهای غیر ضروری و فعال نگه داشتن بهینه نودها حل می گردد، تا در مصرف انرژی صرفه جویی به عمل آمده و عمر شبکه افزایش یابد. سپس به مسئله خوشه بندی در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهای یادگیرسلولی, شبکه های حسگر به گونه ای خوشه بندی می شوند که انرژی به صورت یکنواخت در شبکه بمصرف رسیده وعمر شبکه  افزایش یابد. پس از آن با استفاده از آتوماتاهای یادگیر یک روش تجمیع داده های محیط حسگری پیشنهاد می گردد که در مصرف انرژی شبکه صرفه جویی به عمل آورده و عمر شبکه را افزایش می دهد. همه روشهای ارائه شده با استفاده از نرم افزار J-Sim شبیه سازی گردیده اند. نتایج شبیه سازی ها نشان دهنده عملکرد بهتر روشهای پیشنهادی نسبت به روشهای مشابه می باشد.