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

 

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

 

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

 

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

 

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

 

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

 

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………………………………

 

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

 

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)……………………………..

 

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

 

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

 

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

 

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

 

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

 

 

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

 

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

 

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

 

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

 

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

 

9-  واژه نامه…………………………….. 195

 

مراجع…………………………….. 199

 

چکیده:

 

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

 

1- مقدمه

 

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

 

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

 

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

 

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

 

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

 

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

 

یك گره حسگر می‌تواند یكی از دو نقش تولید كننده داده‌ها و یا رله كننده داده‌های تولید شده توسط سایر گره‌ها را بر عهده بگیرد. عموماً در شبكه‌های حسگر، اغلب گره‌ها هر دو نقش را به صورت توأم ایفا می‌كنند. برپایی و طراحی ساختار و معماری ارتباطات بین گره­های شبکه نیازمند رعایت فاکتورهای مختلف و زیادی از جمله تحمل­پذیری خطا، مقیاس پذیری، هزینه تولید، محیط عملیات، توپولوژی شبکه حسگر، محدودیت­های سخت افزاری، ابزار و رسانه ارتباط، انرژی مصرفی و … می­باشد. جهت آشنایی بیشتر با شبکه های حسگر بی سیم به پیوست اول مراجعه گردد.

 

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

 

عوامل متعددی در طراحی شبکه­های حسگر موثر است و موضوعات بسیاری در این زمینه مطرح است که بررسی تمام آنها در این نوشتار نمی­گنجد از این رو تنها به ذکر برخی از آنها بطور خلاصه اکتفا می­کنیم.

 

1-مسیریابی: ماهیت اصلی شبکه­های حسگر به این صورت است که کارهایی که انجام می­دهند باید به صورت محلی باشد چرا که هر گره تنها می­تواند با همسایه ­های خود ارتباط برقرار کند و اطلاعات کلی و سراسری از شبکه چندان در دسترس نیست (جمع­آوری این اطلاعات هزینه و زمان زیادی را مصرف می­کند). اطلاعات بدست آمده توسط گره ­ها، باید با استفاده از تکنیک­های مسیریابی، به نحوی به گره مرکزی ارسال گردد.

 

2- تنگناهای سخت­ افزاری: هرگره ضمن اینكه باید كل اجزاء لازم را داشته باشد باید بحد كافی كوچك، سبك و كم حجم نیز باشد. در عین حال هر گره باید انرژی مصرفی بسیار كم و قیمت تمام شده پایین داشته و با شرایط محیطی سازگار باشد. اینها همه محدودیت­هایی است كه كار طراحی و ساخت گره‌های حسگر را با چالش مواجه می­كند. ارائه طرح­های سخت­افزاری سبک و کم حجم در مورد هر یک از اجزای گره بخصوص قسمت ارتباط بی­سیم و حسگرها از جمله موضوعات تحقیقاتی است که جای کار بسیار دارد. پیشرفت فن­آوری ساخت مدارات مجتمع با فشردگی بالا و مصرف پایین، نقش بسزایی در كاهش تنگناهای سخت­افزاری داشته است.

 

3- تحمل­پذیری خطا و قابلیت اطمینان[1]: هر گره ممكن است خراب شود یا در اثر رویدادهای محیطی مثل تصادف یا انفجار بكلی نابود شود یا در اثر تمام شدن منبع انرژی از كار بیفتد. منظور از تحمل‌پذیری یا قابلیت اطمینان این است كه خرابی گره­ها نباید عملكرد كلی شبكه را تحت تاثیر قرار دهد. در واقع می­خواهیم با استفاده از اجزای غیر قابل اطمینان یك شبكه قابل اطمینان بسازیم.

 

4- توپولوژی: توپولوژی شبکه یکی از مفاهیم اولیه در شبکه­های حسگر است که دیگر موارد نظیر مسیریابی و … بر روی آن تعریف می­شود. ساختارهای زیادی در توپولوژی مطرح است که بر اساس اولویت­های مختلف و در شرایط متفاوت یکی بر دیگری برتری دارد. از جمله مواردی که در انتخاب یک ساختار تاثیر می­گذارد می­توان به مصرف انرژی کمتر، تنک بودن ساختار، کم بودن درجه گره، تحمل­پذیری خطا و تداخل اشاره کرد.

 

5- مقیاس­پذیری[2]: شبكه باید هم از نظر تعداد گره و هم از نظر میزان پراكندگی گره­ها مقیاس­پذیر باشد. بعبارت دیگر شبكه حسگر از طرفی باید بتواند با تعداد صدها، هزارها و حتی میلیون­ها گره كار كند و از طرف دیگر، چگالی توزیع متفاوت گره­ها را نیز پشتیبانی كند. در بسیاری كاربردها توزیع گره­ها تصادفی صورت می­گیرد و امكان توزیع با چگالی مشخص و یكنواخت وجود ندارد یا گره­ها در اثر عوامل محیطی جابجا می­شوند. بنابراین چگالی باید بتواند از چند عدد تا چند صد گره تغییر كند. موضوع مقیاس­پذیری به روش­ها نیز مربوط می­شود برخی روش­ها ممكن است مقیاس­پذیر نباشند یعنی در یك چگالی با تعداد محدود از گره كار كند. در مقابل برخی روش­ها مقیاس­پذیر هستند.

 

6- شرایط محیطی: طیف وسیعی از كاربرد­های شبكه ­های حسگر مربوط به محیط­هایی می­شود كه انسان نمی­تواند در آن حضور داشته باشد. مانند محیط­های آلوده از نظر شیمیایی، میكروبی، هسته­ای و یا مطالعات در كف اقیانوس­ها و فضا و یا محیط­های نظامی به علت حضور دشمن و یا در جنگل و زیستگاه جانوران كه حضور انسان باعث فرار آنها می­شود. در هر مورد، شرایط محیطی باید در طراحی گره­ها در نظر گرفته شود مثلا در دریا و محیط­های مرطوب گره حسگر در محفظه­ای كه رطوبت را منتقل نكند قرار می‌گیرد.

 

7- رسانه ارتباطی: در شبكه ­های حسگر ارتباط گره­ها بصورت بی­سیم و از طریق رسانه رادیویی، مادون قرمز، یا رسانه‌های نوری صورت می­گیرد. در رسانه رادیویی که بیشتر مورد استفاده قرار می­گیرد از باندهای مختلف صنعتی، علمی و پزشکی که در اکثر کشورها آزاد است استفاده می­شود. تعیین فرکانس در این رسانه با توجه به برخی محدودیت­های سخت­افزاری، کارائی آنتن و مصرف انرژی است. به خاطر لزوم دید مستقیم بین فرستنده و گیرنده، رسانه مادون قرمز چندان مورد استفاده شبکه­ های حسگر نیست هرچند ساختن آنها ارزان و آسان است. اخیرا، رسانه نوری به عنوان رسانه ارتباطی مورد توجه قرار گرفته است. از جمله این توجهات می­توان به استفاده از آن در ذره غیار هوشمند اشاره کرد[3]. انتخاب رسانه ارتباطی از بین این سه رسانه (رادیویی، مادون قرمز و نوری) با توجه به محدودیت­ها و ویژگی­های کاربرد مورد نظر از مسائل مطرح در طراحی شبکه­ های حسگر است.

 

8- افزایش طول­ عمر شبكه: طول­عمر گره­ها بعلت محدودیت انرژی منبع تغذیه كوتاه است. علاوه بر آن در برخی مواقع، موقعیت ویژة یك گره در شبكه مشكل را تشدید می­كند. مثلاً گره­ای كه در فاصله یك قدمی گره مرکزی قرار دارد از یك طرف بخاطر بار كاری زیاد خیلی زود انرژی خود را از دست می­دهد و از طرفی از كار افتادن آن باعث قطع ارتباط گره مرکزی با كل شبكه و در نتیجه موجب از كار افتادن شبكه می­شود. مشكل تخلیه زود هنگام انرژی در مورد گره­های نواحی كم تراكم در توزیع غیر یكنواخت گره­ها نیز صدق می­كند در اینگونه موارد داشتن یك مدیریت انرژی در داخل گره­ها و ارائه راه­حل­های انرژی­آگاه بطوری كه از گره­های بحرانی كمترین استفاده را بكند مناسب خواهد بود. با توجه به مطالب بیان شده تمام الگوریتم­ها و تکنیک­های مورد استفاده در شبکه­های حسگر به انرژی بعنوان یک محدودیت جدی نگاه می­کنند و سعی می­کنند با آگاهی از سطح انرژی مصرفی عمل کنند تا کمترین انرژی مصرف گردد و در نتیجه افزایش طول­عمر شبکه حسگر را به دنبال داشته باشد.