فهرست مطالبچکيده91- مقدمه101-1-شبكه هاي حسگر بيسيم101-1-1-مسائل مطرح در شبکه هاي حسگر بي سيم131-1-2-پوشش محيط در شبكه هاي حسگر بي سيم151-1-3-خوشه بندي در شبکه هاي حسگر بي سيم161-1-4-تجميع داده ها در شبكه هاي حسگر171-2-کيفيت سرويس در شبکه هاي حسگر بي سيم181-2-1-کيفيت سرويس در شبکه هاي داده اي سنتي201-2-2-کيفيت سرويس در شبکه هاي حسگر بي سيم261-3-آتوماتاي يادگير291-3-1-آتوماتاي يادگير311-3-2-معيار‌هاي رفتار اتوماتاي يادگير341-3-3-الگوريتمهاي يادگيري351-3-4-آتوماتاي يادگير با عملهاي متغير391-4-آتوماتاي يادگير سلولي401-4-1-آتوماتاي سلولي401-4-2-آتوماتاي يادگير سلولي (CLA)441-4-3-آتوماتاي يادگير سلولينامنظم (ICLA)471-5-اهداف پايان نامه و ساختار آن482- پوشش محيط در شبكه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگيرسلولي502-1-مقدمه 502-1-1-اشكال مختلف طراحي512-2-دسته بندي مسائل پوشش در شبکه هاي حسگر522-2-1-پوشش ناحيه اي532-2-2-پوشش نقطه اي562-2-3-پوشش مرزي....................................... ....................................... 572-3-روش پوشش CCP592-3-1-فرضيات مسئله592-3-2-تشريح روش....................................... ....................................... 592-4-حل مسئله پوشش(k-پوششي ) با استفاده از آتوماتاهاي يادگير612-4-1-فرضيات و مدل مسئله632-4-2-روش تشخيص افزونه بودن نود حسگر642-4-3-شبيه سازي....................................... ....................................... 722-5-جمع بندي...................................... ...................................... 793- خوشه بندي در شبکه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگير سلولي803-1-مقدمه 803-2-کارهاي انجام شده833-2-1-پروتکل خوشه بندي LEACH853-2-2-پروتکل خوشه بندي HEED883-3-خوشه بندي در شبکه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگير سلولي933-3-1-روش خوشه بندي پيشنهادي943-3-2-شبيه سازي....................................... ....................................... 1023-4-جمع بندي...................................... ...................................... 1074- تجميع داده ها در شبكه هاي حسگر با استفاده از آتوماتاهاي يادگير1084-1-مقدمه 1084-2-كارهاي انجام گرفته1094-3-تجميع داده ها در شبكه هاي حسگر با استفاده از آتوماتاهاي يادگير1124-3-1-بيان مسئله و مفروضات آن1134-3-2-تشريح روش پيشنهادي1154-4-شبيه سازي..................................... ..................................... 1194-4-1-آزمايش اول...................................... ...................................... 1224-4-2-آزمايش دوم...................................... ...................................... 1224-4-3-آزمايش سوم...................................... ...................................... 1234-5-جمع بندي...................................... ...................................... 1255- نتيجه گيري1266- پيوست اول: شبكه هاي حسگر بيسيم1276-1-تاريخچه شبكه هاي حسگر1276-2-ساختار هر گره حسگر1286-2-1-اجزاء دروني يک گره حسگر1286-2-2-محدوديتهاي سختافزاري يک گره حسگر1306-3-پشته پروتکلي1316-4-مزاياي شبکه هاي حسگر بيسيم1326-5-کاربردهاي شبکه هاي حسگر بيسيم1347- پيوست دوم:آتوماتاي يادگيرسلولي1387-1-تاريخچه آتوماتاي يادگير1387-2-معيار‌هاي رفتار اتوماتاي يادگير1397-3-آتوماتاي يادگير با عملهاي متغير1417-4-آتوماتاي يادگير تعقيبي1427-5-آتوماتاي يادگير سلولي (CLA)1507-6-آتوماتاي يادگير سلولي باز(OCLA)1517-7-آتوماتاي يادگير سلولي ناهمگام (ACLA)1528- پيوست سوم: شرح نرم افزار J-Sim و پياده سازي الگوريتمهاي پيشنهادي با آن1558-1-مقدمه 1558-2-شبيه ساز J-Sim1588-2-1-شبيه سازي شبکه هاي حسگر بي سيم با استفاده از J-sim1588-2-2-نصب و اجرا...................................... ...................................... 1628-3-پياده سازي الگوريتم خوشه بندي پيشنهادي1638-4-پياده سازي الگوريتم پوشش پيشنهادي1858-5-پياده سازي الگوريتم تجميع پيشنهادي1909- واژه نامه195مراجع199 فهرست شکلهاشکل 1‑2: يك مدل ساده از QoS19شکل 1‑3: نحوة عملكرد پروتكل RSVP22شکل 1‑4 : اتوماتاي يادگير تصادفي33شکل 1‑5:(الف) همسايگي مور – (ب) همسايگي ون نيومن براي اتوماتاي سلولي42شکل 1‑6:قانون 5447شکل 1‑7: آتوماتاي يادگير سلولينامنظم48شکل 2‑11: محاسبه MaxIteration مناسب جهت بدست اوردن پوشش كامل در شبكه74شکل 2‑12 : مقايسه تعداد نودهاي فعال در روشهاي پوشش با درجه پوشش يك75شکل 2‑13 : مقايسه تعداد نودهاي فعال در روشهاي پوشش با درجات پوشش 2 و 375شکل 2‑14 : مقايسه نسبت ميانگين انرژي نودهاي فعال نسبت به ميانگين انرژي نودهاي غيرفعال با درجه پوشش يك76شکل 2‑15 : مقايسه نسبت ميانگين انرژي نودهاي فعال نسبت به ميانگين انرژي نودهاي غيرفعال با درجه پوشش دو76شکل 2‑16 : مقايسه نسبت ميانگين انرژي نودهاي فعال نسبت به ميانگين انرژي نودهاي غيرفعال با درجه پوشش سه77شکل 2‑17 : مقايسه طول عمر شبكه(زمان از بين رفتن اولين نود) در حالتهاي مختلف78شکل 2‑18 : مقايسه ميزان انرژي مصرفي در الگوريتم پوشش نسبت به كل انرژي مصرفي79شکل 3‑1: ارتباطات تک گامي و چندگامي بدون خوشه بندي81شکل 3‑2:ارتباطات تک گامي و چندگامي با استفاده از خوشه بندي82شکل 3‑3: شبه كد الگوريتم HEED93شکل 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-Sim162شکل 8‑4 :اجراي نرم افزار J-Sim163چکيدهکيفيت سرويس در شبکه هاي حسگر بي سيم نسبت به شبکه هاي سنتي بسيار متفاوت است. بعضي از پارامترهايي که در ارزيابي کيفيت سرويس در اين شبکه ها مورد استفاده قرار مي گيرند عبارتند از: پوشش شبکه, تعداد بهينه نودهاي فعال در شبکه, طول عمر شبکه و ميزان مصرف انرژي.در اين پايان نامه سه مسئله اساسي شبكه ها ي حسگر بي سيم مطرح گرديده و با هدف بهبود پارامترهاي کيفيت سرويس، براي اين مسائل، راه حلهايي کارا با استفاده از روش هوشمند آتوماتاهاي يادگيرسلولي ارائه شده است. ابتدا مسئله پوشش محيط در شبكه هاي حسگر را با استفاده از غير فعال نمودن نودهاي غير ضروري و فعال نگه داشتن بهينه نودها حل مي گردد، تا در مصرف انرژي صرفه جويي به عمل آمده و عمر شبکه افزايش يابد. سپس به مسئله خوشه بندي در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهاي يادگيرسلولي, شبکه هاي حسگر به گونه اي خوشه بندي مي شوند که انرژي به صورت يکنواخت در شبکه بمصرف رسيده وعمر شبکه افزايش يابد. پس از آن با استفاده از آتوماتاهاي يادگير يک روش تجميع داده هاي محيط حسگري پيشنهاد مي گردد که در مصرف انرژي شبکه صرفه جويي به عمل آورده و عمر شبکه را افزايش مي دهد. همه روشهاي ارائه شده با استفاده از نرم افزار J-Sim شبيه سازي گرديده اند. نتايج شبيه سازي ها نشان دهنده عملکرد بهتر روشهاي پيشنهادي نسبت به روشهاي مشابه مي باشد. کلمات کليدي: شبکه هاي حسگر بي سيم،آتوماهاتاي يادگير، کيفيت سرويس، پوشش، خوشه بندي، تجميع داده ها1-1- شبكه هاي حسگر بيسيمشبكه هاي حسگر بيسيم[1]جهت جمع آوري اطلاعات در مناطقي كه كاربر نميتواندحضورداشته باشد، مورد استفاده قرار مي گيرند. در يك شبكه حسگر، حسگرها به صورت جداگانه مقادير محلي را نمونه برداري (اندازه گيري) مي كنند و اين اطلاعات را درصورت لزوم براي حسگرهاي ديگر و در نهايت براي مشاهده گر اصلي ارسال مي نمايند. عملكرد شبكه اين است كه گزارش پديده هايي راكه اتفاق مي افتد به مشاهده گري بدهد كه لازم نيست از ساختار شبكه و حسگرها به صورت جداگانه و ارتباط آنها چيزي بداند. اين شبکه ها مستقل و خودگردان بوده وبدون دخالت انسان کار ميکنند.معمولا تمامي گرهها همسان ميباشند و عملاً با همکاري با يكديگر، هدف كلي شبكه را برآورده مي‌سازند. هدف اصلي در شبکههاي حسگر بيسيم نظارت و کنترل شرايط و تغييرات جوي، فيزيکي و يا شيميائي در محيطي با محدوده معين، ميباشد[1, 2]. شبکه حسگر بيسيم نوع خاصي از شبکههاي موردي[2] است. مبحث شبکه هاي حسگر بي سيم يکي از موضوعات جديد در زمينه مهندسيشبکه و فناوري اطلاعات مي باشد.پيشرفتهاي اخير در طراحي و ساخت تراشه هاي تجاري اين امكان را به وجود آورده است كه عمل پردازش سيگنال و حس كنندگي در يك تراشه يعني حسگر شبكه بي سيم انجام گردد، كه شامل سيستم هاي ميكروالكترومكانيكي [3](MEMS) مانند حسگرها، محرک ها[4] و قطعات راديويي RF مي باشد.حسگرهاي بي سيم كوچكي توليد شده است كه قابليت جمع آوري داده از فاصله چند صد متر و ارسال داده بين حسگرهاي بي سيم به مركز اصلي را دارا مي باشد و با اين تكنولوژي اطلاعات دما - نوسانات، صدا، نور، رطوبت، و مغناطيس قابل جمع آوري مي باشد كه اين حسگرهاي بي سيم با هزينه كم و اندازه اي کوچک قابل نصب در شبكه هاي حسگر بي سيم مي باشد. اما كوچك شدن حسگرهاي بي سيم داراي معايبي نيز مي باشد. تكنولوژي نيمه هادي باعث بوجود آمدن پردازنده هاي سريع با حافظه بالا شده است اما تغذيه اين مدارات هنوز هم يك مشكل اساسي است كه محدود به استفاده از باطري گرديده است. بخش منبع تغذيه يک بخش مهم و محدود است که در صورتيکه از باطري در اين شبکه ها استفاده شود، تعويض باطري ها در حالتيکه تعداد نودهاي شبکه زياد باشد کاري سخت و دشوار خواهد بود و نودها به منظور ذخيره و صرفه جويي در مصرف انرژي مجبور به استفاده از ارتباطات برد کوتاه خواهند شد. تفاوت يك حسگر بي سيم كارا و يك حسگر بي سيم كه داراي كارايي كم از نظر انرژي است در عملكرد آنها در ساعت ها نسبت به هفته ها مي باشد. افزايش اندازه شبكه WSN باعث پيچيدگي مسيريابي وارسال اطلاعات به مركز اصلي مي باشد. اما همچنان مسيريابي و پردازش نياز به انرژي دارند. بنابراين يكي از نكات كليدي در توسعه و ارائه الگوريتمهاي مسيريابي جديد، كاهش و صرفه جويي در انرژي مصرفي است. بخش هاي مختلف شبکه هاي حسگر بي سيم بايد شبيه سازي و مدلسازي گردند تا کارآيي آنها مورد بررسي واقع شود. براي اينکار شبکه هاي حسگر بي سيم به گرافهايي نگاشت مي شوند که در اين گرافها هر گرهمطابق با يک نود در شبکه بوده و هر لبه بيانگر يک پيوند يا کانال ارتباطي بين دو نود در شبکه خواهد بود.اگر ارتباط بين نودها در شبکه دو جهته باشد گراف نگاشت شده بدون جهت خواهد بود و اگر ارتباط بين نود ها در شبکه نا متقارن باشد در آن صورت گراف نگاشت يافته جهتدار خواهد بود. البته مدل ارتباطي بين نودها در شبکه مي تواند يک به يک يا يک به همه باشد. فراهم آوردن يک مدل عملي براي حسگرها کار پيچيده و دشواري مي باشد که اين به خاطر تنوع در انواع حسگرها هم از نظر ساختاري و هم از نظر اصول و اساس کار آنها مي باشد.شبكه هاي حسگر داراي ويژگيهايي منحصر به فرد هستند كه اين امر باعث شده است تا پروتكل هاي خاصي براي آنها در نظر گرفته شود.در شبكه هاي بي سيم حسگر معمولا فقط يك يا دو ايستگاه پايه وجود دارد و تعداد زيادي نودهاي حسگر در محيط پخش گرديده اند. به علت محدوديت برد اين حسگرها و انرژي باطري خيلي از نودها قادر به ارتباط مستقيم با ايستگاه پايه نمي باشند. اما با تكيه بر نودهاي نظير خود و نودهاي حسگر ديگر، به ارتباط با ايستگاه پايه مي پردازد كه در شبكه هاي [5]MANET نيز اين عمل توسط نودهاي معمولي انجام مي شود.معماري ارتباطات شبکههاي حسگر بيسيم در شکل 1-1 ديده ميشود[1]. در شبکههاي حسگر بيسيم، تعداد زيادي گره با امکانات مخابره، پردازش، حس کردن محيط و ... در محيطي با چهارچوب معين پراکنده شدهاند. رويداد اتفاق افتاده و يا سوالات پرسيده شده از سوي گره مرکزي[6] و ماموريت محوله به هر گره موجب ميشود، ارتباطاتي بين گرهها برقرار شود. اطلاعات رد و بدل شده مي‌تواند گزارشي از وضيعت محدوده اي كه زير نظر گرههاي حسگر ميباشد به گره مرکزي و يا درخواستي از سمت گره مرکزي به سمت گرههاي حسگر باشد. گره مرکزي به عنوان درگاه ارتباطي شبکه حسگر با ساير سيستمها و شبکههاي مخابراتي، در واقع گيرنده نهايي گزارش از گرههاي حسگر ميباشد و بعد از انجام يکسري پردازشها، اطلاعات پردازش شده را به کاربر ارسال ميکند (با استفاده از يک رسانه ارتباطاتي مانند اينترنت، ماهواره و ...). از سوي ديگر، درخواستهاي کاربر نيز توسط اين گره به شبکه انتقال مييابد.