فهرست مطالب

چکیده 9

1-  مقدمه 10

1-1-                     شبكه های حسگر بی سیم 10

1-1-1- مسائل مطرح در شبکه های حسگر بی سیم 13

1-1-2- پوشش محیط در شبكه های حسگر بی سیم 15

1-1-3- خوشه بندی در شبکه های حسگر بی سیم 16

1-1-4- تجمیع داده ها در شبكه های حسگر 17

1-2-                     کیفیت سرویس در شبکه های حسگر بی سیم 18

1-2-1- کیفیت سرویس در شبکه های داده ای سنتی 20

1-2-2- کیفیت سرویس در شبکه های حسگر بی سیم 26

1-3-                     آتوماتای یادگیر 29

1-3-1- آتوماتای یادگیر 31

1-3-2- معیار‌های رفتار اتوماتای یادگیر 34

1-3-3- الگوریتمهای یادگیری 35

1-3-4- آتوماتای یادگیر با عملهای متغیر 39

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 شبیه سازی گردیده اند. نتایج شبیه سازی ها نشان دهنده عملکرد بهتر روش های پیشنهادی نسبت به روش های مشابه می باشد.

 

کلمات کلیدی: شبکه های حسگر بی سیم، آتوماهاتای یادگیر، کیفیت سرویس،  پوشش، خوشه بندی، تجمیع داده ها

 

1-    مقدمه

 

• شبكه های حسگر بی سیم

شبكه های حسگر بی سیم[1] جهت جمع آوری اطلاعات در مناطقی كه كاربر نمی تواند حضورداشته باشد، مورد استفاده قرار می گیرند. در یک شبكه حسگر، حسگرها به صورت جداگانه مقادیر محلی را نمونه برداری (اندازه گیری) می كنند و این اطلاعات را درصورت لزوم برای حسگرهای دیگر و در نهایت برای مشاهده گر اصلی ارسال می نمایند. عملكرد شبكه این است كه گزارش پدیده هایی راكه اتفاق می افتد به مشاهده گری بدهد كه لازم نیست از ساختار شبكه و حسگرها به صورت جداگانه و ارتباط آنها چیزی بداند. این شبکه ها مستقل و خودگردان بوده وبدون دخالت انسان کار می کنند. معمولا تمامی گره­ها همسان می­باشند و عملاً با همکاری با یكدیگر، هدف كلی شبكه را برآورده می‌سازند. هدف اصلی در شبکه­ های حسگر بی­سیم نظارت و کنترل شرایط و تغییرات جوی، فیزیکی و یا شیمیائی در محیطی با محدوده معین، می­باشد[1, 2]. شبکه­ حسگر بی­سیم نوع خاصی از شبکه­ های موردی[2] است.  مبحث شبکه های حسگر بی سیم یکی از موضوعات جدید در زمینه مهندسی شبکه و فناوری اطلاعات می باشد.

پیشرفتهای اخیر در طراحی و ساخت تراشه های تجاری این امكان را به وجود آورده است كه عمل پردازش سیگنال و حس كنندگی در یک تراشه یعنی حسگر شبكه بی سیم انجام گردد، كه شامل سیستم های میكروالكترومكانیكی [3](MEMS) مانند حسگرها، محرک ها[4] و قطعات رادیویی RF می باشد.

حسگرهای بی سیم كوچكی تولید شده است كه قابلیت جمع ‌آوری داده از فاصله چند صد متر و ارسال  داده بین حسگرهای بی سیم به مركز اصلی را دارا می باشد و با این تكنولوژی اطلاعات دما – نوسانات، صدا، نور، رطوبت، و مغناطیس قابل جمع آوری می باشد كه این حسگرهای بی سیم با هزینه كم  و اندازه ای کوچک قابل نصب در شبكه های حسگر بی سیم می باشد. اما كوچك شدن حسگرهای بی سیم دارای معایبی نیز می باشد. تكنولوژی نیمه هادی باعث بوجود آمدن پردازنده های سریع با حافظه بالا شده است اما تغذیه این مدارات هنوز هم یک مشكل اساسی است كه محدود به استفاده از باطری گردیده است. بخش منبع تغذیه یک بخش مهم و محدود است که در صورتیکه از باطری در این شبکه ها استفاده شود، تعویض باطری ها در حالتی که تعداد نودهای شبکه زیاد باشد کاری سخت و دشوار خواهد بود و نودها به منظور ذخیره و صرفه جویی در مصرف انرژی مجبور به استفاده از ارتباطات برد کوتاه خواهند شد. تفاوت یک حسگر بی سیم كارا و یک حسگر بی سیم كه دارای كارایی كم از نظر انرژی است در عملكرد آنها در ساعت ها نسبت به هفته ها می باشد. افزایش اندازه شبكه WSN باعث پیچیدگی مسیریابی وارسال اطلاعات به مركز اصلی می باشد. اما همچنان مسیریابی و پردازش نیاز به انرژی دارند. بنابراین یكی از نكات كلیدی در توسعه و ارائه الگوریتمهای مسیریابی جدید، كاهش و صرفه جویی در انرژی مصرفی است. بخش های مختلف شبکه های حسگر بی سیم باید شبیه سازی و مدلسازی گردند تا کارآیی آنها مورد بررسی واقع شود. برای اینکار شبکه های حسگر بی سیم به گرافهایی نگاشت می شوند که در این گرافها هر گره مطابق با یک نود در شبکه بوده و هر لبه بیانگر یک پیوند  یا کانال ارتباطی بین دو نود در شبکه خواهد بود.اگر ارتباط بین نودها در شبکه دو جهته باشد گراف نگاشت شده بدون جهت خواهد بود و اگر ارتباط بین نود ها در شبکه نا متقارن باشد در آن صورت گراف نگاشت یافته جهتدار خواهد بود. البته مدل ارتباطی بین نودها در شبکه می تواند یک به یک یا یک به همه باشد. فراهم آوردن یک مدل عملی برای حسگرها کار پیچیده و دشواری می باشد که این به خاطر تنوع در انواع حسگرها هم از نظر ساختاری و هم از نظر اصول و اساس کار آنها می باشد. شبكه های حسگر دارای ویژگیهایی منحصر به فرد هستند كه این امر باعث شده است تا پروتكل های خاصی برای آنها در نظر گرفته شود.

در شبكه های بی سیم حسگر معمولا فقط یک یا دو ایستگاه پایه‌ وجود دارد و تعداد زیادی نودهای حسگر در محیط پخش گردیده اند. به علت محدودیت برد این حسگرها و انرژی باطری خیلی از نودها قادر به ارتباط مستقیم با ایستگاه پایه‌ نمی باشند. اما با تكیه بر نودهای نظیر خود و نودهای حسگر دیگر، به ارتباط با ایستگاه پایه‌ می پردازد كه در شبكه های  [5]MANET نیز این عمل توسط نودهای معمولی  انجام می شود.

معماری ارتباطات شبکه­ های حسگر بی­سیم در شکل 1-1 دیده می­ شود[1]. در شبکه­ های حسگر بی­سیم، تعداد زیادی گره با امکانات مخابره، پردازش، حس کردن محیط و … در محیطی با چهارچوب معین پراکنده شده ­اند. رویداد اتفاق