نمونه پایاننامه نرم افزار

نمونه پایان نامه نرم افزار: راهنمای جامع برای دانشجویان

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

مطالعه نمونه های موفق پایان نامه در رشته نرم افزار می تواند راهنمای ارزشمندی برای دانشجویان باشد. این نمونه ها به دانشجویان کمک می کنند تا با ساختار و محتوای مورد انتظار در یک پایان نامه نرم افزار آشنا شده و ایده های بهتری برای نگارش پایان نامه خود کسب کنند.

در ادامه به بررسی برخی از نکات کلیدی در انتخاب و مطالعه نمونه پایان نامه نرم افزار می پردازیم:

• مرتبط بودن با موضوع مورد نظر: در هنگام انتخاب نمونه پایان نامه، به دنبال نمونه هایی باشید که با موضوع تحقیقاتی شما مرتبط باشند. مطالعه نمونه های مرتبط به شما کمک می کند تا با چالش ها و راه حل های متداول در حوزه تحقیقاتی خود آشنا شوید.
• کیفیت و اعتبار منبع: از منابع معتبر و شناخته شده برای یافتن نمونه پایان نامه استفاده کنید. وب سایت های دانشگاه ها، کتابخانه های دیجیتال و پایگاه های اطلاعات علمی از جمله منابع معتبر برای یافتن نمونه پایان نامه نرم افزار هستند.
• بررسی ساختار و محتوا: به دقت ساختار و محتوای نمونه پایان نامه را بررسی کنید. به این نکته توجه داشته باشید که تمام نمونه پایان نامه ها بی نقص نیستند و ممکن است دارای ضعف هایی نیز باشند. بنابراین باید با ذهنی انتقادی نمونه پایان نامه ها را مطالعه کنید و از نقاط قوت آنها برای بهبود کار خود استفاده کنید.
• توجه به نوآوری و خلاقیت: به دنبال نمونه هایی باشید که در آنها از روش های نوآورانه و خلاقانه برای حل مسائل استفاده شده باشد. مطالعه این نمونه ها می تواند به شما در ایده پردازی و بهبود کیفیت تحقیقات خود کمک کند.

علاوه بر موارد فوق، دانشجویان می توانند از طرق زیر نیز برای یافتن نمونه پایان نامه نرم افزار استفاده کنند:

• استادان راهنما: از استادان راهنمای خود برای معرفی نمونه پایان نامه های مربوط به موضوع تحقیقاتی خود بپرسید.
• کتابخانه ها: کتابخانه های دانشگاه ها و مراکز آموزشی معمولاً مجموعه از پایان نامه های دانشجویی را در زمینه های مختلف نرم افزار در اختیار دانشجویان قرار می دهند.
• پایگاه های اطلاعات علمی: پایگاه های اطلاعات علمی مانند SID و IranMeena نیز شامل مجموعه از پایان نامه های دانشجویی در زمینه های مختلف هستند.

در پایان توصیه می شود که دانشجویان نرم افزار در کنار مطالعه نمونه پایان نامه ها، از مشاوره و راهنمایی استادان راهنما و متخصصان این رشته نیز بهره مند شوند تا بتوانند پایان نامه ای با کیفیت بالا و مطابق با استانداردهای علمی به دانشگاه خود ارائه دهند.

در اینجا به عنوان نمونه به معرفی چند موضوع برای پایان نامه نرم افزار می پردازیم:

• طراحی و پیاده سازی یک سیستم پیشنهاد محصول بر پایه یادگیری ماشین
• تجزیه و تحلیل بزرگ داده در زمینه مراقبت های بهداشتی
• توسعه یک برنامه کاربردی موبایل برای مدیریت پروژه
• ارزیابی عملکرد الگوریتم های فشرده سازی تصاویر
• بررسی مسائل امنیتی در شبکه های بی سیم

نمونه پایاننامه نرم افزار

چکيده 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- شبكه هاي حسگر بي سيم
شبكه هاي حسگر بي سيم جهت جمع آوري اطلاعات در مناطقي كه كاربر نمي تواند حضورداشته باشد، مورد استفاده قرار مي گيرند. در يك شبكه حسگر، حسگرها به صورت جداگانه مقادير محلي را نمونه برداري (اندازه گيري) مي كنند و اين اطلاعات را درصورت لزوم براي حسگرهاي ديگر و در نهايت براي مشاهده گر اصلي ارسال مي نمايند. عملكرد شبكه اين است كه گزارش پديده هايي راكه اتفاق مي افتد به مشاهده گري بدهد كه لازم نيست از ساختار شبكه و حسگرها به صورت جداگانه و ارتباط آنها چيزي بداند. اين شبکه ها مستقل و خودگردان بوده وبدون دخالت انسان کار مي کنند. معمولا تمامي گره¬ها همسان مي-باشند و عملاً با همکاري با يكديگر، هدف كلي شبكه را برآورده مي‌سازند. هدف اصلي در شبکه¬هاي حسگر بي¬سيم نظارت و کنترل شرايط و تغييرات جوي، فيزيکي و يا شيميائي در محيطي با محدوده معين، مي-باشد[1, 2]. شبکه¬ حسگر بي¬سيم نوع خاصي از شبکه¬هاي موردي است. مبحث شبکه هاي حسگر بي سيم يکي از موضوعات جديد در زمينه مهندسي شبکه و فناوري اطلاعات مي باشد.
پيشرفتهاي اخير در طراحي و ساخت تراشه هاي تجاري اين امكان را به وجود آورده است كه عمل پردازش سيگنال و حس كنندگي در يك تراشه يعني حسگر شبكه بي سيم آموزش انجام گردد، كه شامل سيستم هاي ميكروالكترومكانيكي (MEMS) مانند حسگرها، محرک ها و قطعات راديويي RF مي باشد.
حسگرهاي بي سيم كوچكي توليد شده است كه قابليت جمع ‌آوري داده از فاصله چند صد متر و ارسال داده بين حسگرهاي بي سيم به مركز اصلي را دارا مي باشد و با اين تكنولوژي اطلاعات دما – نوسانات، صدا، نور، رطوبت، و مغناطيس قابل جمع آوري مي باشد كه اين حسگرهاي بي سيم با هزينه كم و اندازه اي کوچک قابل نصب در شبكه هاي حسگر بي سيم مي باشد. اما كوچك شدن حسگرهاي بي سيم داراي معايبي نيز مي باشد. تكنولوژي نيمه هادي باعث بوجود آمدن پردازنده هاي سريع با حافظه بالا شده است اما تغذيه اين مدارات هنوز هم يك مشكل اساسي است كه محدود به استفاده از باطري گرديده است. بخش منبع تغذيه يک بخش مهم و محدود است که در صورتيکه از باطري در اين شبکه ها استفاده شود، تعويض باطري ها در حالتي که تعداد نودهاي شبکه زياد باشد کاري سخت و دشوار خواهد بود و نودها به منظور ذخيره و صرفه جويي در مصرف انرژي مجبور به استفاده از ارتباطات برد کوتاه خواهند شد. تفاوت يك حسگر بي سيم كارا و يك حسگر بي سيم كه داراي كارايي كم از نظر انرژي است در عملكرد آنها در ساعت ها نسبت به هفته ها مي باشد. افزايش اندازه شبكه WSN باعث پيچيدگي مسيريابي وارسال اطلاعات به مركز اصلي مي باشد. اما همچنان مسيريابي و پردازش نياز به انرژي دارند. بنابراين يكي از نكات كليدي در توسعه و ارائه الگوريتمهاي مسيريابي جديد، كاهش و صرفه جويي در انرژي مصرفي است. بخش هاي مختلف شبکه هاي حسگر بي سيم بايد شبيه سازي و مدلسازي گردند تا کارآيي آنها مورد بررسي واقع شود. براي اينکار شبکه هاي حسگر بي سيم به گرافهايي نگاشت مي شوند که در اين گرافها هر گره مطابق با يک نود در شبکه بوده و هر لبه بيانگر يک پيوند يا کانال ارتباطي بين دو نود در شبکه خواهد بود.اگر ارتباط بين نودها در شبکه دو جهته باشد گراف نگاشت شده بدون جهت خواهد بود و اگر ارتباط بين نود ها در شبکه نا متقارن باشد در آن صورت گراف نگاشت يافته جهتدار خواهد بود. البته مدل ارتباطي بين نودها در شبکه مي تواند يک به يک يا يک به همه باشد. فراهم آوردن يک مدل عملي براي حسگرها کار پيچيده و دشواري مي باشد که اين به خاطر تنوع در انواع حسگرها هم از نظر ساختاري و هم از نظر اصول و اساس کار آنها مي باشد. شبكه هاي حسگر داراي ويژگيهايي منحصر به فرد هستند كه اين امر باعث شده است تا پروتكل هاي خاصي براي آنها در نظر گرفته شود.
در شبكه هاي بي سيم حسگر معمولا فقط يك يا دو ايستگاه پايه‌ وجود دارد و تعداد زيادي نودهاي حسگر در محيط پخش گرديده اند. به علت محدوديت برد اين حسگرها و انرژي باطري خيلي از نودها قادر به ارتباط مستقيم با ايستگاه پايه‌ نمي باشند. اما با تكيه بر نودهاي نظير خود و نودهاي حسگر ديگر، به ارتباط با ايستگاه پايه‌ مي پردازد كه در شبكه هاي MANET نيز اين عمل توسط نودهاي معمولي آموزش انجام مي شود.
معماري ارتباطات شبکه¬هاي حسگر بي¬سيم در شکل 1-1 ديده مي¬شود[1]. در شبکه¬هاي حسگر بي-سيم، تعداد زيادي گره با امکانات مخابره، پردازش، حس کردن محيط و … در محيطي با چهارچوب معين پراکنده شده¬اند. رويداد اتفاق افتاده و يا سوالات پرسيده شده از سوي گره مرکزي و ماموريت محوله به هر گره موجب مي¬شود، ارتباطاتي بين گره¬ها برقرار شود. اطلاعات رد و بدل شده مي‌تواند گزارشي از وضيعت محدوده اي كه زير نظر گره¬هاي حسگر مي¬باشد به گره مرکزي و يا درخواستي از سمت گره مرکزي به سمت گره¬هاي حسگر باشد. گره مرکزي به عنوان درگاه ارتباطي شبکه حسگر با ساير سيستم¬ها و شبکه¬هاي مخابراتي، در واقع گيرنده نهايي گزارش از گره¬هاي حسگر مي¬باشد و بعد از آموزش انجام يکسري پردازش¬ها، اطلاعات پردازش شده را به کاربر ارسال مي¬کند (با استفاده از يک رسانه ارتباطاتي مانند اينترنت، ماهواره و …). از سوي ديگر، درخواست¬هاي کاربر نيز توسط اين گره به شبکه انتقال مي¬يابد.

شکل ‏1 1 : معماري ارتباطات شبکه¬هاي حسگر بي¬سيم
يك گره حسگر مي‌تواند يكي از دو نقش توليد كننده داده‌ها و يا رله كننده داده‌هاي توليد شده توسط ساير گره‌ها را بر عهده بگيرد. عموماً در شبكه‌هاي حسگر، اغلب گره‌ها هر دو نقش را به صورت توأم ايفا مي‌كنند. برپايي و طراحي ساختار و معماري ارتباطات بين گره¬هاي شبکه نيازمند رعايت فاکتورهاي مختلف و زيادي از جمله تحمل¬پذيري خطا، مقياس پذيري، هزينه توليد، محيط عمليات، توپولوژي شبکه حسگر، محدوديت¬هاي سخت افزاري، ابزار و رسانه ارتباط، انرژي مصرفي و … مي¬باشد. جهت آشنايي بيشتر با شبکه هاي حسگر بي سيم به پيوست اول مراجعه گردد.
1-1-1- مسائل مطرح در شبکه هاي حسگر بي سيم
عوامل متعددي در طراحي شبکه¬هاي حسگر موثر است و موضوعات بسياري در اين زمينه مطرح است که بررسي تمام آنها در اين نوشتار نمي¬گنجد از اين رو تنها به ذکر برخي از آنها بطور خلاصه اکتفا مي¬کنيم.
1-مسيريابي: ماهيت اصلي شبکه¬هاي حسگر به اين صورت است که کارهايي که آموزش انجام مي¬دهند بايد به صورت محلي باشد چرا که هر گره تنها مي¬تواند با همسايه¬هاي خود ارتباط برقرار کند و اطلاعات کلي و سراسري از شبکه چندان در دسترس نيست (جمع¬آوري اين اطلاعات هزينه و زمان زيادي را مصرف مي-کند). اطلاعات بدست آمده توسط گره¬ها، بايد با استفاده از تکنيک¬هاي مسيريابي، به نحوي به گره مرکزي ارسال گردد.
2- تنگناهاي سخت¬افزاري: هرگره ضمن اينكه بايد كل اجزاء لازم را داشته باشد بايد بحد كافي كوچك، سبك و كم حجم نيز باشد. در عين حال هر گره بايد انرژي مصرفي بسيار كم و قيمت تمام شده پايين داشته و با شرايط محيطي سازگار باشد. اينها همه محدوديت¬هايي است كه كار طراحي و ساخت گره‌هاي حسگر را با چالش مواجه مي¬كند. ارائه طرح¬هاي سخت¬افزاري سبک و کم حجم در مورد هر يک از اجزاي گره بخصوص قسمت ارتباط بي¬سيم و حسگرها از جمله موضوعات تحقيقاتي است که جاي کار بسيار دارد. پيشرفت فن¬آوري ساخت مدارات مجتمع با فشردگي بالا و مصرف پايين، نقش بسزايي در كاهش تنگناهاي سخت¬افزاري داشته است.
3- تحمل¬پذيري خطا و قابليت اطمينان : هر گره ممكن است خراب شود يا در اثر رويدادهاي محيطي مثل تصادف يا انفجار بكلي نابود شود يا در اثر تمام شدن منبع انرژي از كار بيفتد. منظور از تحمل‌پذيري يا قابليت اطمينان اين است كه خرابي گره¬ها نبايد عملكرد كلي شبكه را تحت تاثير قرار دهد. در واقع مي¬خواهيم با استفاده از اجزاي غير قابل اطمينان يك شبكه قابل اطمينان بسازيم.
4- توپولوژي: توپولوژي شبکه يکي از مفاهيم اوليه در شبکه¬هاي حسگر است که ديگر موارد نظير مسيريابي و … بر روي آن تعريف مي¬شود. ساختارهاي زيادي در توپولوژي مطرح است که بر اساس اولويت¬هاي مختلف و در شرايط متفاوت يکي بر ديگري برتري دارد. از جمله مواردي که در انتخاب يک ساختار تاثير مي¬گذارد مي¬توان به مصرف انرژي کمتر، تنک بودن ساختار، کم بودن درجه گره، تحمل¬پذيري خطا و تداخل اشاره کرد.
5- مقياس¬پذيري : شبكه بايد هم از نظر تعداد گره و هم از نظر ميزان پراكندگي گره¬ها مقياس¬پذير باشد. بعبارت ديگر شبكه حسگر از طرفي بايد بتواند با تعداد صدها، هزارها و حتي ميليون¬ها گره كار كند و از طرف ديگر، چگالي توزيع متفاوت گره¬ها را نيز پشتيباني كند. در بسياري كاربردها توزيع گره¬ها تصادفي صورت مي¬گيرد و امكان توزيع با چگالي مشخص و يكنواخت وجود ندارد يا گره¬ها در اثر عوامل محيطي جابجا مي¬شوند. بنابراين چگالي بايد بتواند از چند عدد تا چند صد گره تغيير كند. موضوع مقياس¬پذيري به روش¬ها نيز مربوط مي¬شود برخي روش¬ها ممكن است مقياس¬پذير نباشند يعني در يك چگالي با تعداد محدود از گره كار كند. در مقابل برخي روش¬ها مقياس¬پذير هستند.
6- شرايط محيطي: طيف وسيعي از كاربرد¬هاي شبكه¬هاي حسگر مربوط به محيط¬هايي مي¬شود كه انسان نمي¬تواند در آن حضور داشته باشد. مانند محيط¬هاي آلوده از نظر شيميايي، ميكروبي، هسته¬اي و يا مطالعات در كف اقيانوس¬ها و فضا و يا محيط¬هاي نظامي به علت حضور دشمن و يا در جنگل و زيستگاه جانوران كه حضور انسان باعث فرار آنها مي¬شود. در هر مورد، شرايط محيطي بايد در طراحي گره¬ها در نظر گرفته شود مثلا در دريا و محيط¬هاي مرطوب گره حسگر در محفظه¬اي كه رطوبت را منتقل نكند قرار مي‌گيرد.
7- رسانه ارتباطي: در شبكه¬هاي حسگر ارتباط گره¬ها بصورت بي¬سيم و از طريق رسانه راديويي، مادون قرمز، يا رسانه‌هاي نوري صورت مي¬گيرد. در رسانه راديويي که بيشتر مورد استفاده قرار مي¬گيرد از باندهاي مختلف صنعتي، علمي و پزشکي که در اکثر کشورها آزاد است استفاده مي¬شود. تعيين فرکانس در اين رسانه با توجه به برخي محدوديت¬هاي سخت¬افزاري، کارائي آنتن و مصرف انرژي است. به خاطر لزوم ديد مستقيم بين فرستنده و گيرنده، رسانه مادون قرمز چندان مورد استفاده شبکه¬هاي حسگر نيست هرچند ساختن آنها ارزان و آسان است. اخيرا، رسانه نوري به عنوان رسانه ارتباطي مورد توجه قرار گرفته است. از جمله اين توجهات مي¬توان به استفاده از آن در ذره غيار هوشمند اشاره کرد[3]. انتخاب رسانه ارتباطي از بين اين سه رسانه (راديويي، مادون قرمز و نوري) با توجه به محدوديت¬ها و ويژگي¬هاي کاربرد مورد نظر از مسائل مطرح در طراحي شبکه¬هاي حسگر است.
8- افزايش طول¬عمر شبكه: طول¬عمر گره¬ها بعلت محدوديت انرژي منبع تغذيه كوتاه است. علاوه بر آن در برخي مواقع، موقعيت ويژة يك گره در شبكه مشكل را تشديد مي¬كند. مثلاً گره¬اي كه در فاصله يك قدمي گره مرکزي قرار دارد از يك طرف بخاطر بار كاري زياد خيلي زود انرژي خود را از دست مي¬دهد و از طرفي از كار افتادن آن باعث قطع ارتباط گره مرکزي با كل شبكه و در نتيجه موجب از كار افتادن شبكه مي¬شود. مشكل تخليه زود هنگام انرژي در مورد گره¬هاي نواحي كم تراكم در توزيع غير يكنواخت گره¬ها نيز صدق مي¬كند در اينگونه موارد داشتن يك مديريت انرژي در داخل گره¬ها و ارائه راه¬حل¬هاي انرژي¬آگاه بطوري كه از گره¬هاي بحراني كمترين استفاده را بكند مناسب خواهد بود. با توجه به مطالب بيان شده تمام الگوريتم¬ها و تکنيک¬هاي مورد استفاده در شبکه¬هاي حسگر به انرژي بعنوان يک محدوديت جدي نگاه مي-کنند و سعي مي¬کنند با آگاهي از سطح انرژي مصرفي عمل کنند تا کمترين انرژي مصرف گردد و در نتيجه افزايش طول¬عمر شبکه حسگر را به دنبال داشته باشد.
1-1-2- پوشش محيط در شبكه هاي حسگر بي سيم
يكي از مسائل مهمي كه در بحث شبكه هاي حسگر بي سيم مطرح است مسئله پوشش حسگري شبكه است. اين مسئله ازاين سوال اساسي ناشي مي گردد «حسگر ها چگونه استقرار يابند كه تمام محيط فيزيكي مورد نظر را پوشش دهند ؟» هدف مسئله پوشش اين است كه هر مكان در محيط فيزيكي مورد نظر در دامنه حسگري حداقل يك حسگر قرار بگيرد. از آنجاييكه شبكه حسگر شامل نودهاي بسيار زيادي است براي پخش نودها درمحيط نمي توان مكان نودها را از قبل مشخص كرد. ونودها را به صورت دستي در محيط قرار داد بلكه نودها به صورت تصادفي در محيط پخش مي گردند. بنابراين براي اينكه كل محيط به صورت كامل پوشش داده شود، تعداد حسگر هايي كه در محيط پخش مي گردند بيش از تعداد حسگرهايي است كه اگر به صورت قطعي پخش مي شدند كل محيط را پوشش مي دادند. يعني براي اينكه محيط به صورت كامل پوشش داده شود حسگرها به صورت متراكم توزيع مي گردند. مسئله ديگري كه اينجا بايد مد نظر قرار گيرد مصرف انرژي در حسگرها است. از آنجاييكه انرژي حسگرها، از طريق باطري تامين مي گردد وبه دليل تعداد زياد حسگرها ودر دسترس نبودن محيط، امكان تعويض يا شارژ مجدد باطري حسگرها وجود ندارد با تخليه باطري يك حسگر در حقيقت عمر حسگر به اتمام مي رسد وپس از، از بين رفتن تعدادي از حسگرها ونقض مسئله پوشش واتصال شبكه، عمر شبكه حسگر به اتمام مي رسد.
با در نظر گرفتن دو موضوع مطرح شده توزيع متراكم حسگرها جهت تضمين پوشش شبكه ومصرف انرژي مي توان راهكاري ارائه داد كه در عين تضمين پوشش شبكه مصرف انرژي شبكه را كاهش داده وعمر شبكه را افزايش دهد.
بدين صورت كه تعدادي از نودهاي شبكه كه با غير فعال شدن آنها به پوشش محيط توسط شبكه لطمه وارد نمي شود را غير فعال مي نماييم ودر مواقع لزوم آنها را فعال مي كنيم بدين ترتيب مصرف انرژي كلي شبكه كاهش يافته وعمر شبكه افزايش مي يابد.
1-1-3- خوشه بندي در شبکه هاي حسگر بي سيم
زمان حيات نودهاي حسگر در شبکه حسگر بي سيم، زمان حيات شبکه را مشخص مي کند که در کاربردهاي حسگري از اهميت ويژه اي برخوردار است. زمان حيات نودها مستقيما به مصرف انرژي در آنها مربوط مي گردد. ما در شبکه هاي حسگر مايليم که تعداد زيادي از حسگرها را براي دستيابي به يک هدف راه اندازي کنيم. همه اطلاعات جمع آوري شده بوسيله حسگرها بايد به يک مرکز جمع آوري کننده اطلاعات منتقل شوند. فواصل طولاني تر انرژي بيشتري درارسال اطلاعات مصرف مي کنند.
در ارسال مستقيم، هر حسگر مستقيماً اطلاعات را به مرکز مي فرستد. شبکه هاي ارسال مستقيم براي طراحي بسيار ساده و سر راست مي باشند. اما به دليل فاصله زياد حسگرها از مرکز، انرژي زيادي مصرف مي کنند. در مقابل طراحي هايي که فواصل ارتباطي را کوتاهتر مي کنند، مي توانند دوره حيات شبکه را طولاني تر کنند. بدليل تراكم بالاي گره¬هاي حسگر در واحد سطح و در نتيجه نزديکي آنها با يکديگر، ارتباط¬هاي چندگامي در اين گونه شبكه¬ها مفيدتر و مقرون به صرفه¬تر از ارتباط¬هاي تك¬گامي هستند. اما با توجه به انرژي محدود هر يک از حسگرها و اينکه بيشترِ انرژي آنها صرف ايجاد ارتباط با حسگرهاي ديگر مي¬شود، استفاده از ارتباط¬هاي چندگامي نيز باعث مصرف زياد انرژي در حسگرها و در نتيجه کاهش عمر شبکة حسگر مي¬گردد.
به کار گيري خوشه ها براي ارسال اطلاعات به يک ايستگاه پايه با ملزوم کردن تنها تعداد کمي گره براي ارسال از فواصل دور به ايستگاه اصلي مزاياي فواصل ارسال کوتاه را براي اکثر گره ها افزايش مي دهد. خوشه بندي کردن به اين صورت است که شبکه را به يک تعداد خوشه هاي مستقل قسمت بندي مي کنيم كه هر کدام يک سر خوشه دارند که همه اطلاعات را از گره هاي داخل خوشه اش جمع آوري مي کند. اين سر خوشه ها سپس اطلاعات را فشرده مي کنند و(در ارتباطات تک گامي) مستقيماً و يا (در ارتباطات چند گامي) به صورت گام به گام با تعداد گامهاي کمتر و صرفا با استفاده از نودهاي سرخوشه به مرکز اصلي ارسال مي کنند. خوشه بندي کردن مي تواند به ميزان زيادي هزينه هاي ارتباطي اکثر گره ها را کاهش دهد. زيرا آنها تنها لازم است اطلاعات را به نزديک ترين سر خوشه برسانند، به جاي اينکه آنها را مستقيماً به مرکز اصلي که ممکن است خيلي دور باشد بفرستند.
1-1-4- تجميع داده ها در شبكه هاي حسگر
انرژي در شبكه حسگر يك فاكتور حياتي است. کاهش مصرف انرژي و افزايش طول عمر سيستم در شبکه هاي حسگر يکي از معيارهاي کيفيت سرويس در اين سيستمها است. معمولا يك نود مركزي كه سينك ناميده مي شود, مقصد تمام بسته هاي اطلاعاتي در شبكه مي باشد. در بعضي از كاربردها تمام نودها توانايي ارتباط مستقيم با نود سينك را دارند. اما براي ارسال اطلاعات به فواصل طولاني انرژي زيادي صرف مي گردد. بنابراين, در بيشتر موارد نودها از طريق همسايگانشان, با نود سينك ارتباط برقرار مي نمايند. در اين حالت هر نود بايد بداند كه كداميك از همسايگانش بهتر مي تواند بسته ها را به نود سينك ارسال نمايد.
تاكنون الگوريتمهاي مسيريابي زيادي براي شبكه هاي حسگر ارائه گرديده است. در تعدادي از اين الگوريتمها هر نود ممكن است بيش از يك مسير تا نود سينك داشته باشد كه بر اساس يك سري معيارها, يكي از مسيرها انتخاب مي گردد. و معيارهاي مختلف مثل فاصله تا نود سينك, بار ترافيكي و انرژي مصرفي در طول مسير جهت انتخاب مسير مناسب استفاده مي گردند. از آنجاييكه انرژي يك منبع حياتي است, ميزان مصرف انرژي در طول مسير مي تواند معياري مناسب براي اين هدف باشد. صرفه جويي در مصرف انرژي به دو شيوه مي تواند مد نظر قرار گيرد. يك روش, محاسبه مصرف انرژي براي هر مسير به صورت جداگانه و سپس انتخاب مسير با مينيمم انرژي مي باشد. مشكل اين روش, نياز به انرژي محاسباتي براي هر مسير مي باشد. روش ديگر استفاده از تكنيك تجميع داده ها است. در تكنيك تجميع داده ها, بسته هاي اطلاعاتي بهم مرتبط, در نودهاي مياني با هم تركيب شده و يك بسته را تشكيل مي دهند. و اين بسته به نود سينك ارسال مي گردد. در استفاده از اين شيوه, مسيري انتخاب مي گردد كه بسته هاي مرتبط بيشتري داشته باشد. در اين روش تعداد بسته هايي كه در شبكه ارسال مي يابند كاهش خواهند يافت و بنابراين انرژي كمتري مصرف خواهد شد.
1-2- کيفيت سرويس در شبکه هاي حسگر بي سيم
هر چند که در زمينه جنبه هاي مهم شبکه هاي حسگر مثل طراحي پروتکل و معماري، بهينه سازي مصرف انرژي و مکانيابي تحقيقات زيادي صورت گرفته است، در مورد کيفيت سرويس در اين شبکه ها هنوز به اندازه کافي کار نشده است[4]. اين موضوع مهمي است زيرا کيفيت سرويس در شبکه هاي حسگر بي سيم نسبت به شبکه هاي سنتي بسيار متفاوت است، تا آنجا که به طور کامل نمي توان کيفيت سرويس در اين شبکه ها را تشريح نمود. کيفيت سرويس يک اصطلاح با معاني و ديدگاههاي مختلف مي باشد[5]. انجمن هاي فني مختلف ممکن است تفاسير و نظرات متفاوتي در مورد کيفيت سرويس داشته باشند. در انجمن هاي کاربردي، کيفيت سرويس عموما به کيفيت مشاهده شده توسط کاربر ارجاع مي گردد در حالي که در انجمن هاي شبکه اي کيفيت سرويس به عنوان کيفيتي که شبکه به کاربران و برنامه هاي کاربردي مي دهد مورد ارزيابي قرار مي گيرد. به عنوان مثال [6]RFC 2386 کيفيت سرويس را به عنوان يک مجموعه از نيازمنديهاي سرويس که بايد در زمان انتقال يک بسته از مبدأ به مقصدش به آنها رسيد در نظر مي گيرد. در اين سناريو، کيفيت سرويس به ضمانت اينترنت جهت برآوردن مجموعه اي از خواص سرويسي مناسب براي کاربران يا برنامه هاي کاربردي انتها به انتها بر حسب تأخير، لرزش، پهناي باند و فقدان بسته ها اتلاق مي گردد. اين دو نگاه به کيفيت سرويس مي توانند به وسيله يک مدل ساده که درشکل ‏1 2, به تصوير کشيده شده است، نشان داده شوند[5]. در اين مدل کاربران يا برنامه هاي کاربردي نگران چگونگي مديريت منابع شان توسط شبکه جهت دستيابي به کيفيت سرويس نيستند. آنها صرفاً به سرويسهايي که به برنامه هاي کاربردي ارائه مي شود توجه دارند. از ديد شبکه، هدف شبکه تأمين کيفيت سرويس با ماکزيمم به کارگيري منابع شبکه است. جهت رسيدن به اين هدف، شبکه بايد نيازمنديهاي برنامه هاي کاربردي را تحليل نموده و مکانيزمهاي مختلف کيفيت سرويس در شبکه را به کار گيرد.

شکل ‏1 2: يك مدل ساده از QoS
نيازمنديهاي کيفيت سرويس در شبکه هاي داده اي سنتي اساساً از افزايش محبوبيت برنامه هاي کاربردي چند رسانه اي که احتياج به پهناي باند بالا دارند، نتيجه مي گردد. برنامه هاي کاربردي چندرسانه اي مختلف بر حسب پارامترهاي کيفيت سرويس انتها به انتها نيازمنديهاي کيفيت سرويس مختلفي دارند. بعضي ازشبکه ها به سرويسهايي بهتر از سرويسهاي بهترين تلاش نياز دارند. مثل سرويسهاي تضمين شده(کيفيت سرويس سخت ) و بعضي از شبکه ها احتياج به کيفيت سرويس نرم دارند. محققان, مکانيزمها و الگوريتمهاي زيادي در لايه هاي مختلف پروتکلها با استفاده از مقدار حداکثر پهناي باند جهت رسيدن به کيفيت سرويس ارائه دادند. به خاطر ويژگيهاي خاص شبکه ها، انواع مختلف شبکه ها ممکن است جهت برآوردن پارامترهاي مختلف کيفيت سرويس به صورت همزمان با محدوديتهايي مواجهه گردند. به عنوان مثال، محدوديت پهناي باند و توپولوژي پوياي شبکه هاي موردي موبايل ممکن است کيفيت سرويس در اين شبکه ها را با مشکلاتي روبرو سازد. به هر حال نيازمنديهاي کيفيت سرويس در برنامه هاي کاربردي شبکه هاي حسگر بي سيم ممکن است بسيار متفاوت از شبکه هاي سنتي باشد و پارامترهاي کيفيت سرويس در شبکه هاي سنتي به هيچ عنوان جهت تشريح کيفيت سرويس در شبکه هاي حسگر کافي نيستند.
1-2-1- کيفيت سرويس در شبکه هاي داده اي سنتي
دستيابي به کيفيت سرويس در شبکه هاي سيمي عموماً با استفاده از تأمين منابع فراوان و مهندسي ترافيک به دست مي آيد] 7 ،8 [. در روش تأمين منابع فراوان، ما منابع زيادي را به شبکه اضافه مي کنيم به طوري که بتواند سرويسهاي مناسبي را به برنامه هاي کاربردي چندرسانه اي ارائه دهد. اين روش به سادگي قابل اعمال است. اما تمام کاربران را در يک کلاس سرويس يکسان قرار مي دهد. بنابراين ممکن است در زمان اوج ترافيک، سرويس مناسب ارائه داده نشود. در روش مبتني بر مهندسي ترافيک، کاربران يا برنامه هاي کاربردي را درکلاسهاي سرويسي مختلف گروه بندي کرده و به هر کلاس يک اولويت نسبت مي دهيم. در روش مهندسي ترافيک، دو شيوه جهت رسيدن به کيفيت سرويس استفاده شده اند: مبتني بر رزرو و بدون رزرو. در روش مبتني بر رزرو، منابع شبکه برطبق درخواست کيفيت سرويس برنامه کاربردي و سياست مديريتي و پهناي باند تخصيص مي يابند. اين روش درITM و مدل Interserv اينترنت استفاده شده است. در روش بدون رزرو، هيچ رزروي لازم نيست و کيفيت سرويس از طريق استراتژي هايي مثل کنترل پذيرش، کلاسهاي ترافيک، مديريت سياست و مکانيزمهاي صف بندي بدست مي آيد. در استراتژي کنترل پذيرش اگر يک نود بتواند به شبکه دسترسي يابد، تضمين مي گردد که نود اجازه دسترسي پيدا کند. در تکنيک مديريت سياست، نظارت مي گردد که هيچ نودي از نوع سرويسهايي که که قبلاً به او تخصيص داده شده است عدول ننمايد. کلاسهاي ترافيکي، بسته هاي داده اي را در اولويتهاي مختلف قرار مي دهند و در نودهاي مياني براساس اين اولويتها رفتار متفاوتي بر روي بسته ها آموزش انجام مي گيرد. مکانيزمهاي صف بندي در هنگام ازدحام بسته هاي با اولويت پايين را حذف مي کنند.
شبکه هاي بي سيم مبتني بر زيرساخت، مثل شبکه هاي محلي بي سيم(WLAN) و شبکه هاي بي سيم پخشي، گسترش يافته شبکه هاي سيمي هستند. به گونه اي که ارتباطات را براي کاربران سيار نيز ممکن مي سازند. همه ميزبانهاي سيار در يک سلول ارتباطي مي توانند با يک گام به ايستگاه پايه دسترسي داشته باشند. در اين شبکه ها نيازمنديهاي کيفيت سرويس مربوط به کمبود پهناي باند و پيچيدگي سياربودن کاربر در آخرين گام بي سيم مي باشد. بنابراين مي توان معماري کيفيت سرويس بکاررفته در شبکه هاي سيمي را با پروتکل MAC بي سيم مجتمع نمود. پروتکلهاي MAC بي سيم ممکن است ترافيک داده اي کلاسهاي مختلف را با در نظرگرفتن اولويتهاي دسترسي تأمين نمايند. به گونه اي که کيفيت سرويس کلي شبکه پشتيباني گردد.
شبکه هاي بي سيم موردي، مي توانند سيستم هاي خودکار يا توسعه يک سيستم بي سيم موردي به اينترنت باشند. به عنوان يک سيستم خودکار، آنها پروتکلهاي مسيريابي مختص به خود را دارند. و به عنوان توسعه بي سيم موردي به اينترنت لازم است که يک دستيابي متصل به اينترنت داشته باشند. متأسفانه به دليل محدوديت پهناي باند و توپولوژي پوياي شبکه، مکانيزمهاي کيفيت سرويس در شبکه هاي سيمي نمي تواند مستقيماٌ در يک شبکه موردي استفاده شود[9]. در اين زمينه لازم است که ما عملکرد کيفيت سرويس را به طور پيچيده، با منابع موجود محدود، در محيطهاي پويا پياده سازي نماييم. پشتيباني از کيفيت سرويس در شبکه هاي موردي شامل مدل کيفيت سرويس، رزرو منابع کيفيت سرويس و کنترل دستيابي به کيفيت سرويس مي باشد. يک مدل کيفيت سرويس، معماري و نحوه برخورد عملکردي اجزاء کيفيت سرويس را مشخص مي نمايد. براي مثال در شبکه اي که لازم است فقط سرويسهاي مختلف تأمين گردد، سيگنالدهي براي هر حالت جريان لازم نيست. سيگنال دهي کيفيت سرويس عملکردي است که به وسيله مدل کيفيت سرويس مشخص مي شود. و به عنوان يک مرکز کنترل در سيستم پشتيباني از کيفيت سرويس عمل مي کند. و رفتار مسيريابي کيفيت سرويس، MAC کيفيت سرويس و بقيه مؤلفه ها را هماهنگ مي نمايند. فرايند مسيريابي کيفيت سرويس، مسيري با منابع کافي را جستجو مي نمايد. اما منابع را رزرو نمي کند.
بدون لحاظ نمودن کيفيت سرويس در مسيريابي، سيگنال دهي کيفيت سرويس هنوز مي تواند آموزش انجام شود. اما فرآيند رزرو منابع صورت نمي گيرد . همه مؤلفه هاي کيفيت سرويس لايه بالا به هم وابسته اند وبا پروتکل MAC کيفيت سرويس لايه پاييني همکاري دارند. جزييات اين تکنيکها در[7, 9, 10] موجود است. طبق بحث بالا ما مي توانيم پشتيباني از کيفيت سرويس در شبکه هاي داده اي سنتي را به اين صورت خلاصه نماييم: آنها نيازمنديهاي کيفيت سرويس مشترکي دارند که از کاربردهاي چند رسانه اي محتاج به پهناي باند نشات گرفته مي شوند و جهت ارزيابي مکانيزم هاي کيفيت سرويس پارامترهاي کيفيت سرويس انتها به انتها در اين شبکه استخراج گرديدند.
1-2-1-1- سرويس‌هاي يكپارچه و RSVP
مدل سرويس‌هاي يكپارچه دو نوع سرويس ديگر را علاوه بر سرويس Best Effort ارائه مي‌كند:
– سرويس‌هاي تضمين شده براي كاربردهايي كه نياز به تأخير ثابت در مبادلة اطلاعات دارند.
– سرويس‌هاي كنترل شده كه گونة مطمئن‌تري از سرويس Best Effort مي‌باشند.
فلسفة اين سرويس اين است كه مسيرياب‌ها بايد قادر باشند قبل از ارائة سرويس منابع مورد نياز را براي جريان بسته‌ها رزرو كنند. يك‌سري پروتكل مانند RSVP از مبادلة سيگنال‌ها براي رزرو كردن منابع استفاده مي‌كنند. اين فرايند در شكل 1-3 بيان شده است. فرستنده يك پيغام PATH براي گيرنده مي‌فرستد كه در آن خصوصيات ترافيك مشخص شده است. هر مسيرياب سر راه اين پيغام را به مسيرياب بعدي مي‌فرستد. به‌محض اينكه بسته به گيرنده رسيد گيرنده يك پيغام RESV در پاسخ ارسال مي‌كند و از طريق آن از مسيرياب‌ها منابع مورد نياز براي جريان بسته‌ها را تقاضا مي‌كند. هركدام از مسيرياب‌ها مي‌توانند اين درخواست را قبول يا رد كنند. اگر اين درخواست در هر نقطه از مسير از طرف يك مسيرياب رد شود يك پيغام خطا براي گيرنده فرستاده مي‌شود و فرايند فرستادن سيگنال متوقف مي‌شود. اگر اين درخواست توسط تمام مسيرياب‌ها قبول شود پهناي‌باند و فضاي بافر مورد نياز براي جريان بسته‌ها رزرو شده و اطلاعات مربوط به وضعيت جريان در تمام مسيرياب‌ها ذخيره مي‌شود.

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

سرويس‌هاي يكپارچه از چهار جزء تشكيل شده اند: پروتكل فرستادن سيگنال (مانند RSVP)، روتين كنترل پذيرش، دسته‌بندي بسته‌ها و زمان‌بندي آنها. كاربردهايي كه از سرويس‌هاي يكپارچه استفاده مي‌كنند در ابتدا بايد مسير و منابع مورد نياز براي بسته‌ها را رزرو كنند و سپس شروع به فرستادن بسته‌ها نمايند. هنگامي كه يك مسيرياب بسته‌اي دريافت مي‌كند كلاس بندي MF روي آن آموزش انجام مي‌دهد و بسته را در يك صف خاص قرار مي‌دهد. زمان‌بند نيز بر حسب نيازمندي‌هاي آن كلاس خاص سر زمان مناسب بسته را مي‌فرستد.
سرويس‌هاي يكپارچه داراي معايب زير مي‌باشند:
– با زياد شدن ترافيك حجم فضايي كه اطلاعات وضعيت جريان‌هاي بسته‌ها در مسيرياب ذخيره مي‌شود و نيز بار پردازشي مسيرياب افزايش مي‌يابد. به همين دليل اين ساختار مناسب شبكه‌هاي با ترافيك بالا مانند شبكه‌هاي core نمي‌باشد.
– هر چهار جزء سرويس‌هاي يكپارچه (پروتكل فرستادن سيگنال، كنترل پذيرش، كلاس بندي MF و زمان‌بندي) بايد در مسيرياب‌ها پياده‌سازي شده باشد.
– اين سرويس بايد يك‌باره و روي تمامي مسيرياب‌ها پياده‌سازي شود چون عدم پشتيباني حتي يك مسيرياب در ميان مسير منجر به شكست فرايند فرستادن سيگنال‌ها و رزرو كردن منابع مي‌شود.
1-2-1-2- سرويس‌هاي تفكيك شده
سرآيند بسته‌هاي IPv4 داراي يك بايت بنام TOS مي‌باشد. كاربردها مي‌توانند سه بيت از آن را براي مشخص كردن يك‌سري پارامتر مانند نياز بسته به تاخير كوتاه، گذردهي بالا يا نرخ پايين گم شدن بسته‌ها مقداردهي كنند. با مقداردهي متفاوت اين بيت‌ها مي‌توان كلاس‌هاي متفاوتي از بسته‌ها را ايجاد كرد. بنابراين سرويس‌هاي تفكيك شده فقط اولويت‌گذاري نسبي بين بسته‌ها برقرار مي‌كند. براي اينكه يك مشتري بتواند از سرويس‌هاي تفكيك شده استفاده كند بايد با ISP يك قرارداد SLA داشته باشد كه در آن كلاس‌هاي مختلف سرويس و ماكزيمم ترافيك مجاز براي هر كلاس مشخص شده است. SLA مي‌تواند ايستا يا پويا باشد. در مدل ايستا مشتري در هر لحظه قادر به استفاده از سرويس مي‌باشد ولي در مدل پويا مشتري بايد در ابتدا از پروتكل‌هايي مانند RSVP براي فرستادن يك‌سري سيگنال استفاده كرده تقاضاي استفاده از سرويس بكند و در صورت موافقت مي‌تواند از سرويس استفاده كند.
با استفاده از تكنيك‌هاي كلاس‌بندي بسته‌ها، Policing، Shaping، و زمان‌بندي، سرويس‌هاي مختلفي توسط اين مدل قابل ارائه مي‌باشد:
– سرويس premium براي كاربردهايي كه نياز به تاخير كوتاه در مبادلة اطلاعات دارند.
– سرويس تضمين شده براي كاربردهايي كه درجه اطمينان بالاتري نسبت به سرويس Best Effort لازم دارند.
– سرويس olympic كه در سه كلاس طلايي، نقره‌اي و برنزي ارائه مي‌شود و كيفيت آن از طلايي به برنزي كمتر مي‌شود.
دقت داشته باشيد كه مدل سرويس‌هاي تفكيك شده فقط بيت‌هاي DS و PHB را مقداردهي مي‌كند و اين به ISP بستگي دارد كه چه نوع سرويسي به آن كلاس خاص ارائه كند.
مدل سرويس‌هاي تفكيك شده از چند نظر با سرويس‌هاي يكپارچه تفاوت دارد. اول اينكه فقط تعداد محدودي از كلاس‌هاي سرويس توسط فيلد DS مشخص مي‌شود. دوم اينكه عمليات‌هاي پيچيدة كلاس بندي، Policing، Shaping و علامت‌گذاري بسته‌ها فقط در نقاط مرزي شبكه آموزش انجام مي‌شود. مسيرياب‌هاي core بايد تا حد ممكن ساده باشند و بسته‌ها را با سرعت زياد منتقل كنند و به همين علت عمليات پيچيده روي بسته‌ها آموزش انجام نمي‌دهند. مسيرياب‌هاي مرزي كه به خطوط كاربران متصل هستند مي‌توانند كلاس‌بندي، Policing، Shaping و زمان‌بندي روي بسته‌ها آموزش انجام دهند، چون خط ارتباطي كاربران معمولاً كند است و آموزش انجام عمليات پيچيده تأثيري بر روي سرعت ندارد. مسيرياب مرزي كه ارتباط خارجي شبكه ISP را فراهم مي‌كند بايد بسته‌ها را با سرعت زياد منتقل كند و نيز اعمال پيچيده روي بسته‌ها آموزش انجام دهد؛ به همين علت بايد يك مسيرياب مجهز و نسبتاً سريع باشد. از آنجا كه بسته‌هاي مدل سرويس‌هاي تفكيك شده توسط مسيرياب‌هايي كه اين سرويس را ارائه نمي‌كنند به‌عنوان بسته‌هاي عادي در نظر گرفته مي‌شوند وجود چنين مسيرياب‌هايي در ميان مسير مشكلي براي سرويس بوجود نمي‌آورد، لذا پياده‌سازي تدريجي اين سرويس بر روي شبكه امكان پذير است.
1-2-1-3- MPLS
MPLS يك روش براي مسيريابي است كه بين لاية فيزيكي و لاية شبكه كار مي‌كند. هر بستة MPLS يك سرآيند 20 بيتي دارد كه 3 بيت از آن براي مشخص كردن COS بكار مي‌رود. سرآيند MPLS بين سرآيند لاية فيزيكي و لاية شبكه كد مي‌شود. پروتكل لاية شبكه مي‌تواند IP يا هر پروتكل ديگري باشد. يك مسيرياب با قابليت MPLS كه LSR نام دارد هنگام فرستادن بسته‌ها از برچسبي كه در سرآيند بسته وجود دارد استفاده مي‌كند. MPLS از يك پروتكل (LDP ) براي توزيع كردن برچسب‌ها جهت ايجاد مسيرهاي LSP استفاده مي‌كند. در نتيجة اين عمل جدول‌هايي مشابه جدول مسيريابي در مسيرياب‌ها ايجاد مي‌شود كه كليدهاي آن را همين برچسب‌ها تشكيل مي‌دهند و هر ركورد اين جدول نحوة فرستادن بسته‌هاي داراي يك برچسب خاص را مشخص مي‌كند. بسته‌ها در مسيرياب‌هاي ورودي كلاس‌بندي شده و سرآيند MPLS به آنها اضافه مي‌شود كه شامل يك برچسب مي‌باشد، در بقية مسير بسته‌ها براساس همين برچسب‌ها منتقل مي‌شوند و نيازي به آموزش انجام عمليات‌هاي پيچيده بر روي آنها نمي‌باشد، در مسيرياب‌هاي خروجي نيز اين برچسب‌ها پاك مي‌شوند. همين باعث مي‌شود كلاس‌بندي و منتقل كردن بسته‌ها به سرعت آموزش انجام شود. از MPLS مي‌توان براي تونل زدن نيز استفاده كرد. با استفاده از برچسب يك بسته كه در مسيرياب‌هاي ورودي تنظيم مي‌شود مي‌توان مسير كامل بسته را بدون اينكه نيازي به مشخص كردن مسيرياب‌هاي سر راه باشد محاسبه كرد. اين دو خصوصيت MPLS آن را به يك ابزار مناسب در مهندسي ترافيك تبديل مي‌كند.
1-2-1-4- مهندسي ترافيك
روش‌هايي مانند سرويس‌هاي تفكيك شده و سرويس‌هاي يكپارچه فقط در بار ترافيكي بالا تأثير محسوسي روي ترافيك ايجاد مي‌كنند و در بار ترافيكي پايين عملاً هيچ تفاوتي بين آنها و سرويس Best Effort وجود ندارد. بنابراين در در وحلة اول و قبل از استفاده از هركدام از اين مكانيزم‌ها بايد با پيكربندي و تنظيم صحيح پارامترهاي شبكه جلوي تراكم بسته‌ها را گرفت. البته هيچكدام از اين دو به تنهايي كافي نمي‌باشد بلكه اين دو مكمل يكديگر هستند. بايد تا جاي ممكن از بروز تراكم بسته‌ها جلوگيري كرد و در صورت بروز تراكم نيز بايد مكانيزم‌هاي مناسب جهت كنترل جريان بسته‌ها تعبيه شده‌باشد.
تراكم بسته‌ها ممكن است به علت عدم دسترسي به منابع يا در نتيجه توزيع نامتعادل بار روي شبكه بوجود آيد. در حالت اول تنها راه حل ارتقاء تجهيزات يا افزايش ميزان پهناي‌باند است. در حالت دوم بعضي قسمت‌هاي شبكه متحمل بار سنگيني مي‌شوند در صورتي‌كه بعضي قسمت‌هاي ديگر بار خيلي سبكي دارند. اين مشكل ممكن است در نتيجه استفاده از پروتكل‌هاي مسيريابي پويا مانند RIP، OSPF يا IS-IS بوجود آيد چون اين پروتكل‌ها نزديكترين مسير را براي فرستادن بسته‌ها انتخاب مي‌كنند. در نتيجه هميشته كوتاهترين مسيرها بين دو نقطه پرترافيك همواره داراي بار سنگين ترافيكي هستند درحاليكه بقية مسيرها داراي بار سبكتري مي‌باشند. گزينه‌هايي مانند ECMP در پروتكل‌هاي OSPF و IS-IS در توزيع بار بين چند مسير كوتاه مفيد است، ولي اگر فقط يك مسير كوتاه وجود داشته باشد ECMP نمي‌تواند كمكي به حل مشكل بكند. در شبكه‌هاي كوچك مدير شبكه ممكن است بتواند جدول‌هاي مسيريابي را با توجه به بار شبكه دستي تنظيم كند ولي اين كار براي شبكه‌هاي بزرگ تقريباً غيرممكن است.
مهندسي ترافيك فرايند تنظيم ترافيك است بگونه‌اي كه جلوي تراكم ناشي از توزيع نامتوازن بسته‌ها گرفته شود. Constraint Based Routing يك ابزار مفيد براي خودكار كردن اين فرايند مي‌باشد. در اين روش براي انتخاب بهترين مسير فقط توپولوژي شبكه در نظر گرفته نمي‌شود بلكه وضعيت منابع، وضعيت خطوط ارتباطي، محدوديت‌هاي موجود براي جريان بسته‌ها و سياست‌هاي ديگري كه توسط مدير شبكه تعيين شده در نظر گرفته مي‌شود. بنابراين در اين روش ممكن است يك مسير طولاني بهتر از يك مسير كوتاه تشخيص داده شود و در نتيجه ترافيك بطور متوازن روي شبكه توزيع شود. اين روش علي‌رغم مزاياي ذكر شده داراي معايبي نيز مي‌باشد كه در زير آمده است:
– ميزان ارتباط و تبادل اطلاعات بين مسيرياب‌ها را افزايش مي‌دهد.
– اندازه جدول مسيريابي را افزايش مي‌دهد.
– انتخاب مسيرهاي طولاني منجر به استفاده بيشتر از منابع مي‌گردد.
– فرايند به روز آوردن جدول‌هاي مسيريابي مشكل است.
1-2-2- کيفيت سرويس در شبکه هاي حسگر بي سيم
همانگونه که قبلا عنوان گرديد، شبکه هاي حسگر بي سيم عضوي جديد از خانواده شبکه هاي داده اي بي سيم با يک سري ويژگيها و نيازمنديهاي خاص مي باشند از آنجايي که زمينه کاربرد اين شبکه ها بسيار وسيع مي باشد نيازمنديهاي کيفيت سرويس آنها متفاوت مي باشد. براي ما اين امکان وجود ندارد که آنها را به صورت جداگانه مورد تحليل قرار دهيم و همچنين نمي توان يک راه حل يکسان که تمام کاربردها را پشتيباني کند پيشنهاد داد.
کميته هاي مختلف, کيفيت سرويس در شبکه هاي حسگر را به گونه هاي متفاوتي تعريف مي کنند. به عنوان مثال در کاربردهاي تشخيص يک رويداد و يا رديابي هدف، خطا در تشخيص يا اطلاعات اشتباه در نتيجه يک رويداد فيزيکي ممکن است دلايل متعددي داشته باشد که مي تواند در نتيجه استقرار و مديريت شبکه باشد يعني مکاني که رويداد اتفاق مي افتد بوسيله هيچ حسگر فعالي پوشش داده نشود. ما مي توانيم پوشش محيط يا تعداد نودهاي فعال را بعنوان پارامترهايي براي ارزيابي کيفيت سرويس در شبکه هاي حسگر بي سيم در نظر بگيريم. علاوه بر اين خطاي بالا مي تواند در نتيجه عملکرد محدود حسگرها باشد. مثل دقت مشاهده پايين يا نرخ گزارش پايين حسگرها. بنابراين مي توان دقت مشاهده يا خطاهاي اندازه گيري را بعنوان پارامترهاي ارزيابي کيفيت سرويس انتخاب کرد. همچنين ممکن است خطا در نتيجه از دست رفتن اطلاعات در طول انتفال صورت گيرد. ما مي توانيم بعضي از پارامترهاي مرتبط با انتقال اطلاعات را در محاسبه کيفيت سرويس استفاده نماييم. به هر حال نمي توان جنبه هاي کيفيت سرويس را به طور مطلق به صورت جداگانه در نظر گرفت و نيازمنديهاي عمومي يک کاربرد مي تواند شامل همه پارامترها باشد. ما در اينجا دو نماي کلي از کيفيت سرويس در شبکه هاي حسگر بي سيم را شرح مي دهيم:
الف) کيفيت سرويس مبتني بر کاربرد :
از اين ديدگاه ما مي توانيم پارامترهاي کيفيت سرويس را پوشش شبکه [11] ، نمايش [12] ، خطاهاي اندازه گيري و تعداد بهينه حسگرهاي فعال [13] در نظر بگيريم. به طور خلاصه برنامه هاي کاربردي نيازمنديهاي خاص را در استقرار حسگرهاي فعال، دقت اندازه گيري حسگرها و نظاير آن به شبکه حسگر تحميل مي کنند که مستقيما مربوط به کيفيت کاربرد مي باشد.
ب) کيفيت سرويس شبکه:
از اين ديدگاه ما در نظر مي گيريم که چطور شبکه ارتباطي در لايه هاي پايين مي تواند داده هاي حسگر با محدوديت کيفيت سرويس را تحويل نمايد. به گونه اي که ازمنابع شبکه بصورت کارا استفاده کند. اگر چه ما نمي توانيم هر کاربرد ممکن در شبکه حسگر را تحليل نماييم، مي توان هر گروه از کاربردها را تحليل نمود که اين گروهها بر اساس مدلهاي تحويل داده کلاسبندي شده اند. به گونه اي که بيشتر کاربردها در هر گروه نيازمندي هاي شبکه اي مشترکي دارند. از نظر کيفيت سرويس به کاربردهايي که بصورت واقعي آموزش انجام مي شود توجهي نداريم و صرفا در نظر مي گيريم که چطور داده ها به نود سينک تحويل مي شود. بطور عمومي سه مدل جمع آوري داده پايه اي وجود دارد: مبتني بر رويداد ، مبتني بر پرس و جو و مدلهاي تحويل پيوسته [14].
2- مبتني بر رويداد:
بيشتر کاربردهاي مبتني بر رويداد در شبکه هاي حسگر بي سيم محاوره اي و بلا درنگ و به صورت انتها به انتها عمل مي کنند. در اين کاربردها بايد يک سري رويداد که در محيط رخ مي دهند در کوتاهترين زمان و با قابليت اطمينان بالا تشخيص داده شوند. در اين مدل چند نکته مهم بايد مد نظر قرار گيرند. اولا اينکه در اينجا خود کاربردها انتها به انتها نيستند يعني يک انتهاي کاربرد نود سينک قرار دارد و انتهاي ديگر يک نود حسگر تنها نيست بلکه يک گروه از نودهاي حسگر در محيط است که تحت تاثير رويداد قرار مي گيرند. ثانيا جريان داده ها از اين حسگرها به ميزان زيادي شبيه هم است و بنابراين افزونگي زيادي خواهد داشت. و نکته آخر اينکه در پاسخ به اين رويدادها ممکن است لازم باشد که اعمال بر روي حسگرها يا عمل کننده ها با سرعت و با اطمينان بالا توزيع گردند. اين حسگرها و عمل کننده ها ممکن است همان حسگرهايي که رويدادها را تشخيص داده اند نباشند. کاربردهايي از شبکه حسگر که به کشف رويداد و تخمين يا ارسال سيگنال نياز دارند، از اين مدل جمع آوري داده تبعيت مي کنند مثل حسگري و پاسخ در يک سيستم تشخيص اضطراري آزادشدن مواد شيميايي در يک ساختمان.
2- مبتني بر پرس و جو:
بيشتر کاربردهاي مبتني بر پرس وجو در شبکه هاي حسگر بي سيم محاوره اي و تاخير ناشي از پرس و جو را مي پذيرند و در ضمن انتها به انتها نيستند براي صرفه جويي در مصرف انرژي پرس وجوها مي توانند مبتني بر در خواست ارسال گردند. اين مدل جمع آوري داده، شبيه مدل مبتني بر رويداد است. با اين تفاوت که در اين مدل داده به وسيله نود سينک از حسگرها جمع آوري مي گردد در حالي که در مدل مبتني بر رويداد، داده توسط حسگرها بر روي نود سينک قرار مي گيرد. در اين مدل نيز کاربردها لازم دارند که داده هاي مناسب را با سرعت و مطمئن دريافت نمايند. نکاتي که در مدل مبتني بر رويداد ذکر گرديد براي اين مدل نيز با اهميتند. توجه داشته باشيد که يک پرس وجو مي تواند به منظور مديريت و يا پيکر بندي دوباره نودهاي حسگر مورد استفاده قرار گيرد. به عنوان مثال اگر نود سينک بخواهد نرم افزار بر روي نودهاي حسگر را بهبود بخشد يا نرخ ارسال ماموريت يک نود را تغيير دهد، مي تواند يک فرمان براي اعمال اين تغييرات ارسال نمايد.
در يک جمع بندي به اين نتيجه مي رسيم که پارامترهاي کيفيت سرويس در شبکه هاي حسگر بي سيم, بسته به کاربرد شبکه انواع متفاوتي مي توانند داشته باشند. بعضي از اين پارامترها که در ارزيابي کيفيت سرويس مورد استفاده قرار مي گيرند عبارتند از: پوشش کل شبکه, تعداد بهينه نودهاي فعال در شبکه, دقت مشاهده يا صحت اندازه گيري حسگرها, صحت انتقال اطلاعات در طول ارسال, انتقال اطلاعات درکوتاهترين زمان, قابليت اطمينان انتقال اطلاعات, طول عمر شبکه و ميزان مصرف انرژي در شبکه.
ما در ادامه اين پايان نامه قصد داريم با استفاده ازتکنيک هوشمند آتوماتاهاي يادگير- که در بخش بعد معرفي مي گردد- به تعدادي از اين پارامترهاي کيفيت سرويس پرداخته وسعي نماييم آنها را بهبود بخشيم. بدين منظوردر فصل دوم, با استفاده از آتوماتاهاي يادگير سعي مي نماييم مسئله پوشش محيط در شبكه هاي حسگر را با استفاده از غير فعال نمودن نودهاي غير ضروري و فعال نگه داشتن بهينه نودها حل نماييم. تا در مصرف انرژي صرفه جويي به عمل آمده و عمر شبکه افزايش يابد و بدين ترتيب به چند پارامتر کيفيت سرويس در شبکه هاي حسگر به طور همزمان توجه مي گردد. در فصل سوم به مسئله خوشه بندي در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهاي يادگير, شبکه هاي حسگر به گونه اي خوشه بندي مي شوند که انرژي به صورت يکنواخت در شبکه بمصرف رسيده وعمر شبکه افزايش يابد. بنابراين در اين روش خوشه بندي معيارهاي کيفيت سرويس انرژي و طول عمر شبکه مد نظر قرار مي گيرند. در فصل چهارم با استفاده از آتوماتاهاي يادگير يک روش تجميع داده هاي جمع آوري شده محيط حسگري پيشنهاد مي گردد که با شناسايي نودهاي واقع در يک محيط يکسان وغير فعال نمودن نودهاي غير ضروري و حذف داده هاي افزونه در مصرف انرژي شبکه صرفه جويي به عمل آورده و عمر شبکه را افزايش مي دهد ولذا به معيارهاي انرژي شبکه ,طول عمر و تعداد نودهاي فعال توجه مي گردد.
1-3- آتوماتاي يادگير
فرآيند يادگيري موجودات زنده يکي از موضوعات تحقيقاتي جديد بشمار مي‌آيد. اين تحقيقات به دو دسته کلي تقسيم مي‌شوند. دسته نخست به شناخت اصول يادگيري موجودات زنده و مراحل آن مي‌پردازند و دسته دوم بدنبال ارائه يک متدولوژي براي قرار دادن اين اصول در يک ماشين مي‌باشند. يادگيري بصورت تغييرات ايجادشده در کارايي يک سيستم بر اساس تجربه‌هاي گذشته تعريف مي‌شود‎[15]. يک ويژگي مهم سيستمهاي يادگير، توانايي بهبود کارايي خود با گذشت زمان است. به بيان رياضي مي‌توان اينطور عنوان کرد که هدف يک سيستم يادگير، بهينه‌سازي وظيفه‌اي است که کاملا شناخته شده نيست‎[16]. بنابراين يک رويکرد به اين مسأله، کاهش اهداف سيستم يادگير به يک مسأله بهينه‌سازي است که بر روي مجموعه‌اي از پارامترها تعريف مي‌شود و هدف آن پيدا کردن مجموعه پارامترهاي بهينه مي‌باشد.
در بسياري از مسائل مطرح شده، اطلاعي از پاسخهاي صحيح مسأله ( که يادگيري با نظارت به آنها نياز دارد) در دست نيست. بهمين علت استفاده از يک روش يادگيري بنام يادگيري تقويتي مورد توجه قرار گرفته است. يادگيري تقويتي نه زيرمجموعه شبکه‌هاي عصبي است و نه انتخابي بجاي آنها محسوب مي‌شود. بلکه رويکردي متعامد براي حل مسائل متفاوت و مشکلتر بشمار مي‌رود. يادگيري تقويتي، از ترکيب برنامه‌نويسي پويا و يادگيري نظارتي براي دستيابي به يک سيستم قدرتمند يادگيري ماشين استفاده مي‌کند. در يادگيري تقويتي هدفي براي عامل يادگير مشخص مي‌شود تا به آن دست يابد. آنگاه عامل مذکور ياد مي‌گيرد که چگونه با آزمايشهاي صحيح و خطا با محيط خود، به هدف تعيين شده برسد‎[17].
در يادگيري تقويتي يک عامل يادگيرنده در طي يادگيري با فعل و انفعالات مکرر با محيط، به يک سياست کنترل بهينه مي‌رسد. کارايي اين فعل و انفعالات با محيط بوسيله بيشينه‌(کمينه) بودن پاداش (جريمه) عددي که از محيط گرفته مي‌شود، ارزيابي مي‌گردد. علاوه بر اين روش‌هاي يادگيري تقويتي، اولاً استفاده از يادگيري به روشي ساده، سيستماتيک و واقعي براي رسيدن به يک جواب تقريباً بهينه را بيان مي‌کنند(پيدا کردن اين جواب بهينه با استفاده از روشهاي سنتي بسيار مشکل است). ثانياً، دانشي که در طي فرآيند يادگيري بدست مي‌آيد، در يک مکانيزم نمايش دانش مانند شبکه عصبي يا جدول مراجعه ذخيره مي‌شود که از طريق آن مي‌توان با محاسبات اندک و با کارايي بالايي عمل تخصيص کانال را آموزش انجام داد. ثالثاً، از آنجايي که اين روش يادگيري در محيطي بلادرنگ در حال آموزش انجام است، مي‌توان آنرا همزمان با فعاليت محيط (مانند شبکه سلولي) آموزش انجام داد. که در اين حالت با تمام رخدادهاي پيش‌بيني نشده بصورت يک تجربه جديد برخورد مي‌شود که مي‌توان از آنها براي بهبود کيفيت يادگيري استفاده کرد‎[18].
مزيت اصلي يادگيري تقويتي نسبت به ساير روشهاي يادگيري عدم نياز به هيچگونه اطلاعاتي از محيط (بجز سيگنال تقويتي) ‎[15]. يکي از روشهاي يادگيري تقويتي، اتوماتاي يادگير تصادفي است. اتوماتاي تصادفي بدون هيچگونه اطلاعاتي درباره عمل بهينه (يعني با در نظر گرفتن احتمال يکسان براي تمامي‌عملهاي خود در آغاز کار) سعي در يافتن پاسخ مسأله دارد. يک عمل اتوماتا بصورت تصادفي انتخاب شده و در محيط اِعمال مي‌گردد. سپس پاسخ محيط دريافت شده و احتمال عملها بر طبق الگوريتم يادگيري بِروز مي‌شوند و روال فوق تکرار مي‌گردد. اتوماتاي تصادفي که بصورت فوق در جهت افزايش کارايي خود عمل کند، يک اتوماتاي يادگير تصادفي گفته مي‌شود. در ادامه اين فصل به معرفي اتوماتاي يادگير تصادفي مي‌پردازيم.
يک اتوماتاي يادگير را مي‌توان بصورت يک شئ مجرد که داراي تعداد متناهي عمل است، در نظر گرفت. اتوماتاي يادگير با انتخاب يک عمل از مجموعه عملهاي خود و اِعمال آن بر محيط، عمل مي‌کند. عمل مذکور توسط يک محيط تصادفي ارزيابي مي‌شود و اتوماتا از پاسخ محيط براي انتخاب عمل بعدي خود استفاده مي‌کند. در طي اين فرآيند اتوماتا ياد مي‌گيرد که عمل بهينه را انتخاب نمايد. نحوه استفاده از پاسخ محيط به عمل انتخابي اتوماتا که در جهت انتخاب عمل بعدي اتوماتا استفاده مي‌شود، توسط الگوريتم يادگيري اتوماتا مشخص مي‌گردد. در بخش بعد جزئيات قسمتهاي يک اتوماتاي با ساختار متغير معرفي مي‌شود.
1-3-1- آتوماتاي يادگير
يک اتوماتاي يادگير از دو قسمت اصلي تشکيل شده است:
1- يک اتوماتاي تصادفي با تعداد محدودي عمل و يک محيط تصادفي که اتوماتا با آن در ارتباط است.
2- الگوريتم يادگيري که اتوماتا با استفاده از آن عمل بهينه را ياد مي‌گيرد.
1-3-1-1- آتوماتاي تصادفي
يک اتوماتاي تصادفي بصورت پنج‌تايي تعريف مي‌شود که تعداد عملهاي اتوماتا، مجموعه عملهاي اتوماتا، مجموعه وروديهاي اتوماتا، تابع توليد وضعيت جديد، تابع خروجي که وضعيت فعلي را به خروجي بعدي نگاشت مي‌کند و مجموعه وضعيتهاي داخلي اتوماتا در لحظه n، مي‌باشند.
مجموعه شامل خروجيهاي (عملهاي) اتوماتا است که اتوماتا در هر گام يک عمل از r عمل اين مجموعه را براي اِعمال بر محيط انتخاب مي‌نمايد. مجموعه ورودي‌ها ( ) وروديهاي اتوماتا را مشخص مي‌کند. توابع F و G وضعيت فعلي ورودي را به خروجي بعدي (عمل بعدي) اتوماتا نگاشت مي‌کنند. اگر نگاشتهاي F و G قطعي باشند، اتوماتا يک اتوماتاي قطعي ناميده مي‌شود. در حالتيکه نگاشتهاي F و G تصادفي باشند، اتوماتا يک اتوماتاي تصادفي ناميده مي‌شود.
اتوماتاي يادگير به دو گروه اتوماتاي با ساختار ثابت و اتوماتاي با ساختار متغير تقسيم بندي مي‌گردند. در اتوماتاي تصادفي با ساختار ثابت احتمال عملهاي اتوماتا ثابت هستند. درحاليکه در اتوماتاي تصادفي با ساختار متغير احتمالات عملهاي اتوماتا در هر تکرار بِروز مي‌شوند. در اتوماتاي يادگير با ساختار متغير، تغيير احتمالهاي عملها بر اساس الگوريتم يادگيري آموزش انجام مي‌شود. همچنين در اتوماتاي يادگير با ساختار متغير، وضعيت داخلي اتوماتا توسط احتمالات عملهاي اتوماتا بازنمايي مي‌شوند. در واقع اتوماتا بصورت يک state-output automata در نظر گرفته مي‌شود که خروجي آن معادل با وضعيت داخلي آن مي‌باشد. وضعيت داخلي اتوماتا در لحظه n ، با بردار احتمال عملهاي اتوماتا P(n) که در زير آمده است، نشان داده مي‌شود:
(‏1 1)

بطوريکه

در آغاز فعاليت اتوماتا، احتمال عملهاي آن با هم برابر و مساوي مي‌باشند (که r تعداد عملهاي اتوماتا مي‌باشد).
1-3-1-2- محيط
محيط را مي‌توان توسط سه‌تايي نشان داد که در آن مجموعه وروديهاي محيط، مجموعه خروجيهاي محيط و مجموعه احتمالهاي جريمه مي‌باشند.
ورودي محيط يکي از r عمل انتخاب شده اتوماتا است. خروجي(پاسخ) محيط به هر عمل i توسط مشخص مي‌شود. اگر يک پاسخ دودويي باشد، محيط مدلP ناميده مي‌شود. در چنين محيطي بعنوان پاسخ نامطلوب يا شکست و بعنوان پاسخ مطلوب يا موفقيت در نظر گرفته مي‌شوند. در محيط مدلQ ، شامل تعداد محدودي از مقادير قرار گرفته در بازه [1،0] مي‌باشد. درحاليکه در محيط مدلS مقادير يک متغير تصادفي در بازه [1،0] مي‌باشد ( ). مجموعه C احتمالات جريمه (شکست) پاسخهاي محيط را مشخص مي‌کند و بصورت زير تعريف مي‌شود:
(‏1 2)

که احتمال اينکه عمل پاسخ نامطلوبي از محيط دريافت کند را نشان مي‌دهد. مقادير ها نامشخص هستند و فرض مي‌شود که ها يک مينيمم يکتا دارند. بهمين صورت مي‌توان محيط را توسط مجموعه احتمالات پاداش(موفقيت) نشان داد که در اين حالت نشان‌دهنده احتمال دريافت پاسخ مطلوب به عمل مي‌باشد. در محيطهاي ايستا مقادير احتمال جريمه ( ها) ثابت هستند. درحاليکه در محيطهاي غير ايستا احتمالات جريمه در طول زمان تغيير مي‌کند.

شکل‏1 4: اتوماتاي يادگير تصادفي
ارتباط اتوماتاي تصادفي با محيط درشکل نشان داده شده است. از اين مجموعه به همراه الگوريتم يادگيري تحت عنوان اتوماتاي يادگير تصادفي نام برده مي‌شود. به همين ترتيب اتوماتاي يادگير تصادفي را مي‌توان با چهارتايي نشان داد که تعداد عملهاي اتوماتا، مجموعه عملهاي اتوماتا، مجموعه وروديهاي اتوماتا، بردار احتمال عملهاي اتوماتا و الگوريتم يادگيري مي‌باشد.
1-3-2- معيار‌هاي رفتار اتوماتاي يادگير
براي اندازه‌گيري کارايي اتوماتاي يادگير تصادفي، شاخصهاي معيني تعريف شده‌اند که امکان مقايسه روشهاي مختلف يادگيري را فراهم مي‌آورند‎[15]. يک اتوماتاي شانسي محض بصورت اتوماتايي تعريف مي‌شود که عملهاي آن هميشه احتمال يکساني براي انتخاب شدن داشته باشند. بنابراين يک اتوماتاي يادگير بايد از يک اتوماتاي شانسي محض بهتر عمل کند.
همانطور که ذکر شد، محيط توسط احتمالات جريمه نشان داده مي‌شود که احتمال جريمه متناظر با عمل است. مقدار بصورت ميانگين جريمه‌هاي دريافت شده توسط اتوماتا (براي يک بردار عمل مفروض) تعريف و بر اساس رابطه (1-3) محاسبه مي‌شود.
(‏1 3)

براي يک اتوماتاي شانسي محض ميانگين جريمه‌‌ها M(n) يک عدد ثابت است که طبق رابطه (1-4) بدست مي‌آيد:
(‏1 4)

بنابراين اتوماتايي که بخواهد بهتر از اتوماتاي شانسي محض عمل کند، بايد ميانگين جريمه‌هاي کمتري از داشته باشد. از آنجايي که يک متغير تصادفي است، اميد رياضي ( ) با مقايسه مي‌شود. بنابراين تعاريف زير را خواهيم داشت.
تعريف1- يک اتوماتاي يادگير expedient گفته مي‌شود، اگر:
(‏1 5)

تعريف2- يک اتوماتاي يادگير بهينه گفته مي‌شود، اگر:
(‏1 6)

که . در حاليکه بهينه بودن اتوماتا يک ويژگي مطلوب در محيطي ايستا بشمار مي‌رود، در عمل ممکن است يک کارايي زيربهينه مورد نياز باشد. يک محيط واقعي معمولاً متغير است و در نتيجه عمل بهينه در زمان تغيير مي‌کند. در چنين حالتي و از آنجايي که الگوريتم بر روي هيچ حالت خاصي متوقف نمي‌ماند، يک آتوماتاي نيمه-بهينه مناسب‌تر مي‌باشد. بنابراين تعريف زير را نيز خواهيم داشت:
تعريف3- يک اتوماتاي يادگير گفته مي‌شود، اگر:
(‏1 7)

تعريف4- يک اتوماتاي يادگير Absolutely Expedient گفته مي‌شود‎[19]، اگر:
(‏1 8)

Expediency بندرت نشان مي‌دهد که اتوماتاي يادگير بهتر از اتوماتاي شانسي محض عمل مي‌کند. بنابراين بهينه بودن شاخص مناسب‌تري براي مقايسه روشهاي مختلف يادگيري مي‌باشد. بهينه‌بودن اطمينان مي‌دهد که عملي که توسط اتوماتا انتخاب مي‌شود، عملي بهينه باشد. در محيطهاي واقعي بعلت متغير بودن محيط رفتار زير‌بهينه ارجحيت دارد‎[20].
1-3-3- الگوريتمهاي يادگيري
1-3-3-1- الگوريتمهاي يادگيري استاندارد
همانطور که در بخش ‏1-3-1-2- نشان داده شد، الگوريتم يادگيري T بصورت نشان داده مي‌شود. اگر T يک عملگر خطي باشد، الگوريتم يادگيري تقويتي، خطي ناميده مي‌شود. در غير اينصورت الگوريتم يادگيري غيرخطي ناميده مي‌شود. ايده اصلي تمام الگوريتمهاي يادگيري بصورت زير است:
اگر اتوماتاي يادگير در تکرار nاُم، يک عمل خود مانند را انتخاب کند و يک پاسخ مطلوب از محيط دريافت نمايد، (احتمال عمل ) افزايش و احتمال ساير عملها کاهش مي‌يابد. بالعکس، در صورت نامطلوب بودن پاسخ دريافتي از محيط، احتمال عمل کاهش و احتمال ساير عملهاي اتوماتا افزايش مي‌يابد. در هر حال، تغييرات به گونه اي صورت مي‌گيرد تا حاصل جمع ها همواره ثابت و مساوي يک باقي بماند. تغيير احتمال عملها بصورت زير مي‌باشد.
الف- پاسخ مطلوب از محيط
(‏1 9)
ب- پاسخ نامطلوب از محيط
(‏1 10)
توابع و دو تابع غير منفي هستند که بترتيب توابع پاداش و جريمه ناميده مي‌شوند. همانطور که در روابط فوق مشاهده مي‌شود، اين روابط صحت رابطه را حفظ مي‌کنند. از آنجايي که الگوريتمهاي يادگيري خطي از لحاظ رياضي ساده‌تر مي‌باشند، بررسي‌هاي زيادي بر روي آنها آموزش انجام شده است. در يک الگوريتم يادگيري تقويتي خطي (در اتوماتايي با چند عمل) توابع و بصورت زير تعريف شده‌اند‎[15]:
(‏1 11)
(‏1 12)
که r تعداد عملهاي اتوماتا، a پارامتر پاداش و b پارامتر جريمه مي‌باشند. با استفاده از رابطه (1-13) و (1-14) شکل عمومي‌الگوريتم يادگيري بصورت زير است.‌ اگر در گام nاُم عمل انتخاب شده باشد، سپس در گام 1+nاُم خواهيم داشت :
الف- پاسخ مطلوب از محيط

(‏1 13)
ب- پاسخ نامطلوب از محيط

(‏1 14)
با توجه به مقادير a و b در روابط فوق، سه حالت را مي‌توان در نظر گرفت. اگر مقادير a و b برابرباشند، اتوماتاي يادگير ناميده مي‌شود. زمانيکه b مساوي با صفر باشد اتوماتاي يادگير ناميده مي‌شود. اگر b<<a باشد، اتوماتاي يادگير ناميده مي‌شود. اتوماتاي رفتاري expedient از خود نشان مي‌دهد. در حاليکه دو اتوماتاي و رفتاري زيربهينه دارند. روشهاي بروز رساني غير خطي نيز معرفي شده‌اند ([19,21,22]) که بهبود محسوسي نسبت به روشهاي خطي فوق نشان نمي‌دهند.
يک عامل تعيين کننده که استفاده از اتوماتاي يادگير تصادفي را در حل مسائل محدود مي‌کند، نرخ همگرايي کند اتوماتاي يادگير است. اين عامل با افزايش تعداد عملهاي اتوماتا تشديد مي‌شود. هرچند استفاده از برخي از روشهاي يادگيري غيرخطي باعث افزايش سرعت همگرايي اتوماتا مي‌گردد.
1-3-3-2- الگوريتمهاي يادگيري مدلS
در محيطهاي S پاسخ محيط به عملهاي اتوماتاي يادگير، يک متغير تصادفي در بازه [1،0] مي‌باشد. بنابراين خروجي محيط (ورودي اتوماتا) بصورت زير تغيير مي‌کند:
(‏1 15)

از آنجاييکه پاسخ محيط از نوع S يک متغير تصادفي در بازه [1،0] است، استفاده از مدلS براي سيستمهاي يادگير نياز به اطلاعات اوليه‌اي از کران بالا و پايين شاخصهاي کارايي سيستم دارد تا بتواند پاسخهاي محيط را در مقياس [1،0] تنظيم نمايد. کارايي مناسب مدلS در ‎[23] نشان داده شده است. در ‎[24] يک الگوريتم غير خطي اما بهينه براي يک اتوماتا با دو عمل در محيط مدل S معرفي شده است. يک روش زيربهينه براي يک اتوماتا با چند عمل در محيط مدل S نيز در ‎[25] معرفي شده است.
• الگوريتم
در محيط مدلP محيط توسط احتمال جريمه‌ها تعريف مي‌شود. براي هر عمل مانند ، محيط پاسخي با يک مقدار تصادفي به اتوماتا مي‌دهد که ورودي اتوماتا را تشکيل مي‌دهد. در مدل P، پاسخ با احتمال برابر 1 (پاسخ نامطلوب) و با احتمال -1 صفر(پاسخ مطلوب) در نظر گرفته مي‌شود. اما در محيط مدلS، محيط بصورت زير تعريف مي‌شود:
(‏1 16)

که
مقدار ميانگين پاسخ براي عمل مي‌باشد و در واقع ها بعنوان شدت جريمه‌ها محسوب مي‌شوند. فرض کنيد در گام nاُم عمل انتخاب شده باشد و پاسخ محيط به آن بوده باشد. در چنين حالتي احتمال عملهاي اتوماتاي بصورت زير بروز مي‌شوند‎[15]:
(‏1 17)
که a پارامتر يادگيري و 1<a<0 مي‌باشد.
• الگوريتم
الگوريتم يادگيري تقويتي اتوماتاي يادگير در مدل بصورت زير بردار احتمالات عملهاي اتوماتا را بروز مي‌کند‎[15]. در اتوماتايي با r عمل، اگر در تکرار nاُم عمل انتخاب شده باشد و پاسخ محيط به آن باشد، بردار احتمالهاي اتوماتا طبق رابطه(18-1) بروز مي‌شود.
(‏1 18)
• الگوريتم
اتوماتاي يادگيري با r عمل و پارامتر پاداش a و پارامتر جريمه b، بصورت زير بردار عملهاي خود را بروز مي‌کند. اگر در تکرار nاُم عمل انتخاب شده باشد و پاسخ محيط به آن باشد، بردار احتمالهاي اتوماتا طبق رابطه(19-1) بروز مي‌شود.
(‏1 19)
1-3-4- آتوماتاي يادگير با عملهاي متغير
اتوماتاي يادگير داراي تعداد عمل ثابتي مي‌باشد اما در بعضي از کاربردها نياز به اتوماتايي با تعداد عمل متغير مي‌باشد‎[26]. اين اتوماتا در لحظه n عمل خود را فقط از يک زير مجموعه غير تهي ( ) از عملها که عملهاي فعال ناميده مي‌شوند، انتخاب مي‌کند. انتخاب مجموعه توسط يک عامل خارجي و بصورت تصادفي آموزش انجام مي‌شود. نحوه فعاليت اين اتوماتا بصورت زير است. براي انتخاب يک عمل در زمان ، ابتدا مجموع احتمال عملهاي فعال خود ( ) را محاسبه مي‌کند و سپس بردار را مطابق رابطه(20-1) محاسبه مي‌کند. آنگاه اتوماتا يک عمل از مجموعه عمل‌هاي فعال خود را بصورت تصادفي و مطابق بردار احتمال انتخاب کرده و بر محيط اعمال مي‌کند. اگر عمل انتخاب شده باشد، پس از دريافت پاسخ محيط، اتوماتا بردار احتمال عملهاي خود در صورت دريافت پاداش بر اساس رابطه (21-1) و در صورت دريافت جريمه طبق رابطه (22-1) بِروز مي‌کند(در محيط مدلP)‎[26].

(‏1 20)

الف- پاسخ مطلوب از محيط
(‏1 21)

ب- پاسخ نامطلوب از محيط
(‏1 22)

سپس اتوماتا بردار احتمال عملها را با استفاده از بردار و بصورت زير بِروز مي‌کند:
(‏1 23)
1-4- آتوماتاي يادگير سلولي
1-4-1- آتوماتاي سلولي
آتوماتاي سلولي (CA)در اواخر دهه 1940 توسط ون‌نيومن مطرح و پس از او توسط رياضيداني بنام اولام به عنوان مدلي براي بررسي رفتار سيستم‌هاي پيچيده پيشنهاد شد. اتوماتاي سلولي در حقيقت سيستم‌هاي ديناميکي گسسته‌اي هستند که رفتارشان کاملاً بر اساس ارتباط محلي استوار است. اتوماتاي سلولي چندين بار و هر بار تحت نام مختلفي ابداع شده است. از ديدگاه رياضيات محض آنها را مي‌توان شاخه‌اي از ديناميک توپولوژيکي و از ديدگاه مهندسي برق، آرايه‌هاي تکرار شونده دانست .
در اتوماتاي سلولي، فضا بصورت يک شبکه تعريف مي‌گردد که به هر خانه آن يک سلول گفته مي‌شود. زمان بصورت گسسته پيش مي‌رود و قوانين آن بصورت سرتاسري است که از طريق آن در هر مرحله هر سلول، وضعيت جديد خود را با در نظر گرفتن همسايه‌هاي مجاور خود بدست مي‌آورد. اتوماتاي سلولي را مي‌توان به عنوان سيستم‌هاي محاسباتي نيز در نظر گرفت که اطلاعات کد شده در خودشان را پردازش مي‌کنند. همچنين يک اتوماتاي سلولي بهمراه واحد کنترل آن را مي‌توان بعنوان يک ماشين SIMD تعبير نمود .قوانين اتوماتاي سلولي، نحوه تأثير پذيرفتن سلول از سلولهاي همسايه خود را مشخص مي‌کند. يک سلول را همسايه سلول ديگر گوئيم هرگاه بتواند آن را در يک مرحله و براساس قانون حاکم تحت تأثير قرار دهد. مي‌توان در بعضي شرايط براي سلولهاي واقع در مرزها، سلولهاي مرز(هاي) مقابل را بعنوان همسايه در نظرگرفت. در صورتيکه همسايگي بدين صورت در نظر گرفته شود، wrap around و درغير اينصورت محدود شده گفته مي‌شود. در بدست آوردن وضعيت کنوني سلول علاوه بر وضعيت قبلي سلولهاي همسايه، مي‌توان وضعيت قبلي خود سلول را نيز دخالت داد. معمولاً قوانين اتوماتاي سلولي توسط کاربر طراحي مي‌شوند. البته براي جستجو در فضاي قوانين راههاي متفاوتي مانند راه‌حلهاي مبتني بر الگوريتمهاي ژنتيک نيز ارائه شده اند. تعريف رسمي‌اتوماتاي سلولي به صورت زير است.
تعريف 5- اتوماتاي سلولي d بعدي يک چندتايي است به طوريکه:
– يک شبکه از d تايي‌هاي مرتب از اعداد صحيح مي‌باشد. اين شبکه مي‌تواند يک شبکه متناهي، نيمه متناهي يا نامتناهي باشد.
– يک مجموعه متناهي از حالتها مي‌باشد.
– ، ، يک زير مجموعه متناهي از مي‌باشد که بردار همسايگي خوانده مي‌شود. بردار همسايگي، موقعيت نسبي همسايگان را براي هر سلول u در شبکه سلولي به صورت زير مشخص مي‌کند:
(‏1 24)

تابع دو شرط زير را ارضا مي‌کند:
(‏1 25)
براي نمونه در شکل، به ترتيب همسايگي ون‌نيومن، و مور، ، در فضاي دو بعدي مي‌باشند نشان داده شده‌اند.
– قانون محلي CA مي‌باشد که به سه دسته تقسيم مي‌شود:
1- قانون عمومي : در اين قانون مقدار يک سلول در مرحله بعدي، به مقدار تک تک سلولهاي همسايه در حالت فعلي وابسته است.
2- قانون کلي : در اين قانون مقدار يک سلول در مرحله بعدي، به تعداد سلولهاي همسايه که در حالتهاي مختلف مي‌باشند، وابسته است. در اين نوع قانون برخلاف قانون عمومي، توجه اي به تک تک سلولها نمي‌شود.
3- قانون کلي خارجي : تنها تفاوتي که اين قانون با قوانين کلي دارد در اين است که در تعيين حالت بعدي سلول، حالت فعلي نيز موثر است.

شکل‏1 5: (الف) همسايگي مور – (ب) همسايگي ون نيومن براي اتوماتاي سلولي
ويژگي‌هاي اساسي اتوماتاي سلولي عبارتند از:
آ- فضايي گسسته دارند.
ب-‌ زمان بصورت گسسته پيش‌ مي‌رود.
پ- هر سلولي تعداد محدودي از وضعيتهاي ممکن را اختيار مي‌کند.
ت- تمام سلولها يکسان مي باشند.
ث- عمل بروز در آوردن سلولها بصورت همگام مي‌باشد.
ج- قوانين تصادفي نبوده و بطور قطعي اعمال مي‌شوند.
چ- قانون در هر سايت فقط بستگي به مقادير همسايه‌هاي اطراف آن دارد.
ح- قانون براي مقدار جديد هر سايت فقط بستگي به مقادير تعداد محدودي از مراحل قبل دارد.
براي پيچيده‌تر کردن مدل، مي‌توان تغييرات زير را برآن اعمال نمود:
آ- افزايش تعداد ابعاد محيط
ب- افزايش تعداد وضعيت‌هاي هر سلول
پ- افزايش طول همسايگي
ت- متغير نمودن همسايگي در طي زمان
ث- متغير نمودن قانون در طي زمان
ج- تغيير در شرايط مرزي
چ- تبديل قانون اتوماتاي سلولي از حالت قطعي به حالت احتمالي
ح- استفاده از شبکه‌هاي با توپولوژي‌هاي متفاوت مانند شبکه‌هاي مثلثي و شش ضلعي
در مدلسازي سيستم‌هاي فيزيکي و بيولوژيکي،‌گاهي لازم است که قوانين را بصورت احتمالي در نظر بگيريم. رفتار احتمالي را مي‌توان به عنوان نويز در سيستم تعبير نمود. همچنين با وجود اينکه سلولها را بصورت گسسته در نظر گرفته‌ايم، تعداد بسيار زيادي از آنها ممکن است رفتار پيوسته‌اي را از خود نشان دهند.
يکي از اشکالات اتوماتاي سلولي، تعيين فرم قطعي قوانين مورد نياز براي يک کاربرد خاص است. براي مثال تشخيص اين که براي رسيدن به يک هدف خاص در سمت دوم قانون چه حالتي قرار گيرد، سخت مي‌باشد. از طرفي تمام قوانين مطرح شده در اتوماتاي سلولي مجاز نمي‌باشند و بررسي خود اين شرط نيز در بعضي موارد طاقت فرساست. دليل ديگر نامناسب بودن اين اتوماتاي سلولي، محدوديت آن به مدل کردن سيستمهايي قطعي مي‌باشد. از طرفي اغلب سيستمهايي که توسط اين ابزار مدل مي‌شوند، سيستمهاي پيچيده‌اي هستند که دو ويژگي عمده در آنها به چشم مي‌خورد. يکي نويزهايي که در سيستم وارد مي‌شود و دوم عدم قطعيت و احتمالي بودن سيستم. بدين ترتيب براي چنين سيستم هايي وضع قوانين به صورت قطعي، منطقي به نظر نمي‌رسد.
راه حلهاي متفاوتي در برخورد با اين مشکلات به نظر مي‌رسد. يکي از اين راه حلها احتمالاتي کردن قوانين مي‌باشند. به اين ترتيب که تمام قانونهاي امکان‌پذير را در نظر بگيريم و براي فعال شدن آنها احتمالي در نظر بگيريم. اما مشکلي که باز گريبان‌گير ما خواهد شد آن است که شناسايي همين احتمالها در سيستمهاي ناشناخته عملي نمي‌باشد. پس بايد به سمتي حرکت کنيم که به نحوي خود ابزار با گذشت زمان بتواند قوانين مناسب را استخراج کند. بدين منظور چندين رهيافت را مي‌توان مورد بررسي قرار داد.
رهيافت اول آنست که تمام مجموعه قوانين را براي اتوماتاي سلولي توليد کنيم و سپس با استفاده از روشهاي مکاشفه‌اي مانند الگوريتمهاي ژنتيکي به جستجو برروي اين مجموعه قوانين بپردازيم. بدين ترتيب که هر سلول با توجه به وضعيت خود در جهان سلولي، مجموعه‌اي از قوانين را مورد پذيرش قرار دهد. البته اين کار اصل همگني را براي اتوماتاي سلولي از بين خواهد برد. در صورتيکه بخواهيم همچنان پايبند اصل همگني باشيم، مي‌توانيم الگوريتم جستجو را براي کل ابزار پياده‌سازي کنيم و قانونهاي پذيرفته شده را براي همه سلولها بکار ببريم. مشکلي که اين مدل ايجاد خواهد کرد اينست که در مواردي که فضاي جستجو بسيار بزرگ است، همگرايي اتوماتاي سلولي بسيار کند خواهد بود و از طرفي براي بسياري از کاربردها اين مدل توجيه کننده نمي‌باشد. همين طور ممکن است نتوانيم مبناي خوبي براي همگرا شدن سيستم بيابيم.
رهيافتي که در برابر تمام ايده هاي گذشته به ذهن مي‌رسد، اين است که به گونه‌اي، هوشمندي را به سلولهاي اتوماتاي سلولي بيافزاييم و بدين وسيله، تحمل مدل در برابر فرآيندهاي احتمالي و ايجاد نويز در سيستم را افزايش دهيم. به اين ترتيب، استفاده از الگوريتمهاي يادگيري ماشين در ساختار سلول مي‌تواند به منظور حل مشکلات مفيد واقع شود.
1-4-2- آتوماتاي يادگير سلولي (CLA)
آتوماتاي يادگير سلولي، يک مدل رياضي براي سيستمهايي با اجزاي ساده‌ است، بطوريکه رفتار هر جزء بر اساس رفتار همسايگانش و نيز تجربيات گذشته‌اش تعيين و اصلاح مي‌شود. اجزاء ساده تشکيل دهنده اين مدل، از طريق کنش و واکنش با يکديگر رفتار پيچيده‌اي از خود نشان مي‌دهند، بنابراين از آن مي‌توان در مدل‌سازي بسياري از مسائل بهره برد. اين مدل اولين بار در ‎[27] معرفي شد و سپس فعاليتهايي جهت بررسي کاربردهاي گوناگون آن [28,29,30,31,32] صورت گرفت. سرآموزش انجام در ‎[33] بيگي و ميبدي، اين مدل را بصورت رياضي مورد تحليل قرار داده و رفتار همگرايي آن را مطالعه نمودند که نتيجه قضاياي مهمي در باب قابليت همگرايي اين مدل به پاسخ بهينه محلي خود، مي‌باشد.
هر اتوماتاي يادگير سلولي، از يک اتوماتاي سلولي تشکيل شده است که هر سلول آن به يک يا چند اتوماتاي يادگير مجهز مي‌باشد که حالت اين سلول را مشخص مي‌سازد. مانند اتوماتاي سلولي، قانون محلي در محيط حاکم است و اين قانون تعيين مي‌کند که آيا عمل انتخاب شده توسط يک اتوماتا در سلول بايد پاداش داده شود ويا اينکه جريمه شود. دادن پاداش و يا جريمه باعث بروز درآورده شدن ساختار اتوماتاي يادگير سلولي بمنظور نيل به يک هدف مشخص مي‌گردد. ايده اصلي اتوماتاي يادگير سلولي، که زير مجموعه اي از اتوماتاي يادگير سلولي تصادفي محسوب مي‌شود، استفاده از اتوماتاي يادگير براي محاسبه احتمال انتقال حالت در اتوماتاي سلولي تصادفي مي‌باشد. اتوماتاي يادگير سلولي را مي‌توان به دو دسته غيرهمگام و همگام تقسيم کرد. در مدل همگام، تمام سلولها با يک ساعت سراسري هماهنگ شده و به طور همزمان اجرا مي‌شوند.
تعريف ‏1-1- اتوماتاي يادگير سلولي: اتوماتاي يادگير سلولي d-بعدي يک چندتايي است به طوريکه:
– يک شبکه از d-تايي‌هاي مرتب از اعداد صحيح مي‌باشد. اين شبکه مي‌تواند يک شبکه متناهي، نيمه متناهي يا متناهي باشد.
– يک مجموعه متناهي از حالتها مي‌باشد.
– A، يک مجموعه از اتوماتاهاي يادگير(LA) است که هر اتوماتاي يادگير به يک سلول نسبت داده مي‌شود.
– يک زير مجموعه متناهي از مي‌باشد که بردار همسايگي خوانده مي‌شود.
– قانون محلي CLA مي‌باشد، بطوريکه مجموعه مقاديري است که مي‌تواند به عنوان سيگنال تقويتي پذيرفته شود.
تعريف 6- پيکربندي : پيکربندي اتوماتاي يادگير سلولي در زمان k، يک ماتريس مي‌باشد که بردار احتمال اتوماتاي يادگير سلول iام مي‌باشد.
اعمال قانون محلي حاکم بر اتوماتاي يادگير سلولي به هر سلول سبب مي‌شود تا پيکربندي فعلي اتوماتاي سلولي به يک پيکربندي ديگر تبديل شود.
تعريف 7- پيکربندي قطعي و احتمالاتي: يک پيکربندي را در صورتي که بردار احتمال هر کدام از اتوماتاها يک بردار يکه باشد، يک پيکربندي قطعي مي‌گوييم. در غير اين صورت آن را احتمالاتي مي‌گوييم.
تعريف 8- رفتار عمومي : رفتار عمومي‌اتوماتاي يادگير سلولي نگاشت مي‌باشد که رفتار ديناميکي اتوماتاي يادگير سلولي را توصيف مي‌کند. K همان مجموعه فضاي پيکربندي اتوماتاي يادگير سلولي است.
تعريف 9- تکامل : تکامل اتوماتاي يادگير سلولي، دنباله اي از پيکربنديهاي متوالي مي‌باشد. به طوريکه:
(‏1 26)

تعريف 10- اتوماتاي يادگير سلولي يکنواخت : اتوماتاي يادگير سلولي را يکنواخت مي‌گوييم، اگر براي تمام سلولها، تابع همسايگي، قانون محلي و اتوماتاهاي يادگير يکسان باشند.
تعريف 11- حالت عمومي: حالت اتوماتاي يادگير سلولي يک نگاشت مي‌باشد که به هر الگوي تشکيل شده توسط اتوماتاي يادگير سلولي عددي را نسبت مي‌دهد. و به صورت زير قابل محاسبه است:
(‏1 27)

که نمايش عدد در مبناي m، N تعداد سلولهاي اتوماتاي يادگير سلولي و ترتيب مشخصي از سلولها مي‌باشد. براي مثال براي يک اتوماتاي يادگير سلولي خطي با 5 سلول و هر سلول با دو حالت 0 و 1 که در حال حاضر الگوي را توليد کرده باشد، حالت مي‌باشد به اين ترتيب آشکار است که تعداد حالاتي که يک اتوماتاي يادگير سلولي مي‌تواند داشته باشد، ، است.
تعريف 12- اعداد ولفرام : با فرض اينکه و در هر سلول يک اتوماتاي يادگير با عمل قرار گرفته باشد، براي توصيف يک قانون خاص مي‌توانيم از روش بازنمايي قانون با استفاده از اعداد ولفرام -که در بازنمايي قوانين در اتوماتاي سلولي استفاده مي‌شود- استفاده کنيم. ابتدا تمام عضو دامنه قانون را به صورت خطي مرتب مي‌کنيم. سپس دنباله‌اي از نتايج مربوط به هر کدام را، بازنمايي يک عدد در مبناي در نظر مي‌گيريم. به اين ترتيب عدد ولفرام قانون مورد نظر معادل دهدهي آن است. براي مثال براي يک اتوماتاي يادگير سلولي خطي با و ، قانون شکل قانون شماره 2(00110110)=54 است.
000 001 010 011 100 101 110 111
0 1 1 0 1 1 0 0
شکل ‏1 6: قانون 54
1-4-3- آتوماتاي يادگير سلولي نامنظم (ICLA)
يک آتوماتاي يادگير سلولي نامنظم (ICLA) يک آتوماتاي يادگير سلولي (CLA) است که محدوديت ساختار مستطيلي گريد درCLA را ندارد(شکل 1-7). کاربردهاي زيادي هستند که نمي توانند با گريد هاي مستطيلي مدل شوند مثل شبکه هاي حسگر بي سيم ،سيستمهاي ايمني مصنوعي ، کاربردهاي مربوط به گراف و … . يک ICLA به صورت يک گراف بدون جهت تعريف مي گردد که هر گره گراف يک سلول را مشخص مي کند که به يک آتوماتاي يادگير مجهز است. آتوماتاي يادگير واقع در يک سلول مشخص، وضعيتش را بر اساس بردار احتمالات اعمالش تعيين مي کند.
شبيه CLA قانوني وجود دارد که ICLA تحت آن عمل مي کند. قانون CLA و اعمال انتخاب شده به وسيله آتوماتاهاي يادگير همسايه در هر آتوماتاي يادگير، سيگنال تقويتي آن آتوماتا را مشخص مي کند. آتوماتاهاي يادگير همسايه هر آتوماتاي يادگير، محيط محلي سلول را تشکيل مي دهد. محيط محلي يک سلول ايستا نيست. زيرا بردار احتمالات اعمال آتوماتاهاي يادگير همسايه در طول تکامل ICLA تغيير مي کند.

شکل‏1 7: آتوماتاي يادگير سلولي نامنظم
1-5- اهداف پايان نامه و ساختار آن
همانگونه که عنوان گرديد، هر چند که در زمينه شبکه هاي تحقيقات زيادي صورت گرفته است، در مورد کيفيت سرويس در اين شبکه ها هنوز به اندازه کافي کار نشده است. از طرفي کيفيت سرويس در شبکه هاي حسگر بي سيم نسبت به شبکه هاي سنتي بسيار متفاوت است. تا آنجا که به طور کامل نمي توان کيفيت سرويس در اين شبکه ها را تشريح نمود. و بسته به کاربرد آنها، پارامترهاي متعددي مد نظر قرار مي گيرند. بعضي از پارامترهايي که در ارزيابي کيفيت سرويس مورد استفاده قرار مي گيرند عبارتند از: پوشش کل شبکه, تعداد بهينه نودهاي فعال در شبکه, طول عمر شبکه و ميزان مصرف انرژي در شبکه.
ويژگي¬هاي اتوماتاي يادگير نشان مي¬دهد که اتوماتاي يادگير توانايي حل مناسب مسائل مختلف مطرح در شبکه¬هاي حسگر را دارد. از جمله ويژگي¬هاي مطرح اتوماتاي يادگير مي¬توان به کارسازبودن اتوماتاي يادگير در محيط¬هاي توزيع‌شده و چند عامله با ارتباطات محدود و اطلاعات ناقص و ساده بودن ساختار اتوماتاي يادگير اشاره کرد.
هدف از اين پايان¬نامه استفاده از تكنيك اتوماتاهاي يادگير جهت بهبود پارامترهاي کيفيت سرويس در شبكه ها ي حسگر مي باشد. در اين پايان نامه تعدادي از مسائل اساسي شبكه ها ي حسگر بي سيم مطرح گرديده و با هدف بهبود پارامترهاي کيفيت سرويس اين مسائل با استفاده از آتوماتاهاي يادگيرسلولي حل گرديده اند.
اين پايان‌نامه حاوي 5 فصل و 4 ضميمه است.
در فصل دوم، مسئله پوشش محيط در شبكه هاي حسگر با استفاده از غير فعال نمودن نودهاي غير ضروري و فعال نگه داشتن بهينه نودها حل مي گردد. تا در مصرف انرژي صرفه جويي به عمل آمده و عمر شبکه افزايش يابد و بدين ترتيب به چند پارامتر کيفيت سرويس در شبکه هاي حسگر به طور همزمان توجه مي گردد. روش ارائه شده مبتني بر اتوماتاي يادگير سلولي است.
در فصل سوم، به مسئله خوشه بندي در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهاي يادگير سلولي, شبکه هاي حسگر به گونه اي خوشه بندي مي شوند که انرژي به صورت يکنواخت در شبکه بمصرف رسيده وعمر شبکه افزايش يابد. بنابراين در اين روش خوشه بندي معيارهاي کيفيت سرويس انرژي و طول عمر شبکه مد نظر قرار مي گيرند.
در فصل چهارم با استفاده از آتوماتاهاي يادگير يک روش تجميع داده هاي جمع آوري شده محيط حسگري پيشنهاد مي گردد که با شناسايي نودهاي واقع در يک محيط يکسان وغير فعال نمودن نودهاي غير ضروري و حذف داده هاي افزونه در مصرف انرژي شبکه صرفه جويي به عمل آورده و عمر شبکه را افزايش مي دهد ولذا به معيارهاي انرژي شبکه ,طول عمر و تعداد نودهاي فعال توجه مي گردد.
در فصل پنجم يک نتيجه گيري کلي ارائه مي‌شود.
در پيوستهاي اول و دوم مطالب تکميلي راجع به شبکه هاي حسگر بي سيم و آتوماتاي يادگير سلولي آورده شده است. در پيوست سوم نرم افزارشبيه ساز J-Sim تشريح شده و نحوه پياده سازي الگوريتمهاي پيشنهادي با آن توضيح داده شده است.

• نمونه پایاننامه