
گيرند عبارتند از: پوشش کل شبکه, تعداد بهينه نودهاي فعال در شبکه, دقت مشاهده يا صحت اندازه گيري حسگرها, صحت انتقال اطلاعات در طول ارسال, انتقال اطلاعات درکوتاهترين زمان, قابليت اطمينان انتقال اطلاعات, طول عمر شبکه و ميزان مصرف انرژي در شبکه.
ما در ادامه اين پايان نامه قصد داريم با استفاده ازتکنيک هوشمند آتوماتاهاي يادگير- که در بخش بعد معرفي مي گردد- به تعدادي از اين پارامترهاي کيفيت سرويس پرداخته وسعي نماييم آنها را بهبود بخشيم. بدين منظوردر فصل دوم, با استفاده از آتوماتاهاي يادگير سعي مي نماييم مسئله پوشش محيط در شبكه هاي حسگر را با استفاده از غير فعال نمودن نودهاي غير ضروري و فعال نگه داشتن بهينه نودها حل نماييم. تا در مصرف انرژي صرفه جويي به عمل آمده و عمر شبکه افزايش يابد و بدين ترتيب به چند پارامتر کيفيت سرويس در شبکه هاي حسگر به طور همزمان توجه مي گردد. در فصل سوم به مسئله خوشه بندي در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهاي يادگير, شبکه هاي حسگر به گونه اي خوشه بندي مي شوند که انرژي به صورت يکنواخت در شبکه بمصرف رسيده وعمر شبکه افزايش يابد. بنابراين در اين روش خوشه بندي معيارهاي کيفيت سرويس انرژي و طول عمر شبکه مد نظر قرار مي گيرند. در فصل چهارم با استفاده از آتوماتاهاي يادگير يک روش تجميع داده هاي جمع آوري شده محيط حسگري پيشنهاد مي گردد که با شناسايي نودهاي واقع در يک محيط يکسان وغير فعال نمودن نودهاي غير ضروري و حذف داده هاي افزونه در مصرف انرژي شبکه صرفه جويي به عمل آورده و عمر شبکه را افزايش مي دهد ولذا به معيارهاي انرژي شبکه ,طول عمر و تعداد نودهاي فعال توجه مي گردد.
1-3- آتوماتاي يادگير
فرآيند يادگيري موجودات زنده يکي از موضوعات تحقيقاتي جديد بشمار ميآيد. اين تحقيقات به دو دسته کلي تقسيم ميشوند. دسته نخست به شناخت اصول يادگيري موجودات زنده و مراحل آن ميپردازند و دسته دوم بدنبال ارائه يک متدولوژي براي قرار دادن اين اصول در يک ماشين ميباشند. يادگيري بصورت تغييرات ايجادشده در کارايي يک سيستم بر اساس تجربههاي گذشته تعريف ميشود[15]. يک ويژگي مهم سيستمهاي يادگير، توانايي بهبود کارايي خود با گذشت زمان است. به بيان رياضي ميتوان اينطور عنوان کرد که هدف يک سيستم يادگير، بهينهسازي وظيفهاي است که کاملا شناخته شده نيست[16]. بنابراين يک رويکرد به اين مسأله، کاهش اهداف سيستم يادگير به يک مسأله بهينهسازي است که بر روي مجموعهاي از پارامترها تعريف ميشود و هدف آن پيدا کردن مجموعه پارامترهاي بهينه ميباشد.
در بسياري از مسائل مطرح شده، اطلاعي از پاسخهاي صحيح مسأله ( که يادگيري با نظارت19 به آنها نياز دارد) در دست نيست. بهمين علت استفاده از يک روش يادگيري بنام يادگيري تقويتي20 مورد توجه قرار گرفته است. يادگيري تقويتي نه زيرمجموعه شبکههاي عصبي است و نه انتخابي بجاي آنها محسوب ميشود. بلکه رويکردي متعامد21 براي حل مسائل متفاوت و مشکلتر بشمار ميرود. يادگيري تقويتي، از ترکيب برنامهنويسي پويا و يادگيري نظارتي براي دستيابي به يک سيستم قدرتمند يادگيري ماشين استفاده ميکند. در يادگيري تقويتي هدفي براي عامل يادگير مشخص ميشود تا به آن دست يابد. آنگاه عامل مذکور ياد ميگيرد که چگونه با آزمايشهاي صحيح و خطا با محيط خود، به هدف تعيين شده برسد[17].
در يادگيري تقويتي يک عامل يادگيرنده در طي يادگيري با فعل و انفعالات22 مکرر با محيط، به يک سياست کنترل بهينه ميرسد. کارايي اين فعل و انفعالات با محيط بوسيله بيشينه(کمينه) بودن پاداش (جريمه) عددي که از محيط گرفته ميشود، ارزيابي ميگردد. علاوه بر اين روشهاي يادگيري تقويتي، اولاً استفاده از يادگيري به روشي ساده، سيستماتيک و واقعي براي رسيدن به يک جواب تقريباً بهينه را بيان ميکنند(پيدا کردن اين جواب بهينه با استفاده از روشهاي سنتي بسيار مشکل است). ثانياً، دانشي که در طي فرآيند يادگيري بدست ميآيد، در يک مکانيزم نمايش دانش مانند شبکه عصبي يا جدول مراجعه ذخيره ميشود که از طريق آن ميتوان با محاسبات اندک و با کارايي بالايي عمل تخصيص کانال را انجام داد. ثالثاً، از آنجايي که اين روش يادگيري در محيطي بلادرنگ در حال انجام است، ميتوان آنرا همزمان با فعاليت محيط (مانند شبکه سلولي) انجام داد. که در اين حالت با تمام رخدادهاي پيشبيني نشده بصورت يک تجربه جديد برخورد ميشود که ميتوان از آنها براي بهبود کيفيت يادگيري استفاده کرد[18].
مزيت اصلي يادگيري تقويتي نسبت به ساير روشهاي يادگيري عدم نياز به هيچگونه اطلاعاتي از محيط (بجز سيگنال تقويتي) [15]. يکي از روشهاي يادگيري تقويتي، اتوماتاي يادگير تصادفي23 است. اتوماتاي تصادفي بدون هيچگونه اطلاعاتي درباره عمل بهينه (يعني با در نظر گرفتن احتمال يکسان براي تماميعملهاي خود در آغاز کار) سعي در يافتن پاسخ مسأله دارد. يک عمل اتوماتا بصورت تصادفي انتخاب شده و در محيط اِعمال ميگردد. سپس پاسخ محيط دريافت شده و احتمال عملها بر طبق الگوريتم يادگيري بِروز ميشوند و روال فوق تکرار ميگردد. اتوماتاي تصادفي که بصورت فوق در جهت افزايش کارايي خود عمل کند، يک اتوماتاي يادگير تصادفي گفته ميشود. در ادامه اين فصل به معرفي اتوماتاي يادگير تصادفي ميپردازيم.
يک اتوماتاي يادگير را ميتوان بصورت يک شئ مجرد که داراي تعداد متناهي عمل است، در نظر گرفت. اتوماتاي يادگير با انتخاب يک عمل از مجموعه عملهاي خود و اِعمال آن بر محيط، عمل ميکند. عمل مذکور توسط يک محيط تصادفي ارزيابي ميشود و اتوماتا از پاسخ محيط براي انتخاب عمل بعدي خود استفاده ميکند. در طي اين فرآيند اتوماتا ياد ميگيرد که عمل بهينه را انتخاب نمايد. نحوه استفاده از پاسخ محيط به عمل انتخابي اتوماتا که در جهت انتخاب عمل بعدي اتوماتا استفاده ميشود، توسط الگوريتم يادگيري اتوماتا مشخص ميگردد. در بخش بعد جزئيات قسمتهاي يک اتوماتاي با ساختار متغير24 معرفي ميشود.
1-3-1- آتوماتاي يادگير
يک اتوماتاي يادگير از دو قسمت اصلي تشکيل شده است:
1- يک اتوماتاي تصادفي با تعداد محدودي عمل و يک محيط تصادفي که اتوماتا با آن در ارتباط است.
2- الگوريتم يادگيري که اتوماتا با استفاده از آن عمل بهينه را ياد ميگيرد.
1-3-1-1- آتوماتاي تصادفي
يک اتوماتاي تصادفي بصورت پنجتايي تعريف ميشود که تعداد عملهاي اتوماتا، مجموعه عملهاي اتوماتا، مجموعه وروديهاي اتوماتا، تابع توليد وضعيت جديد، تابع خروجي که وضعيت فعلي را به خروجي بعدي نگاشت ميکند و مجموعه وضعيتهاي داخلي اتوماتا در لحظه n، ميباشند.
مجموعه شامل خروجيهاي (عملهاي) اتوماتا است که اتوماتا در هر گام يک عمل از r عمل اين مجموعه را براي اِعمال بر محيط انتخاب مينمايد. مجموعه وروديها () وروديهاي اتوماتا را مشخص ميکند. توابع F و G وضعيت فعلي ورودي را به خروجي بعدي (عمل بعدي) اتوماتا نگاشت ميکنند. اگر نگاشتهاي F و G قطعي باشند، اتوماتا يک اتوماتاي قطعي25 ناميده ميشود. در حالتيکه نگاشتهاي F و G تصادفي باشند، اتوماتا يک اتوماتاي تصادفي ناميده ميشود.
اتوماتاي يادگير به دو گروه اتوماتاي با ساختار ثابت26 و اتوماتاي با ساختار متغير27 تقسيم بندي ميگردند. در اتوماتاي تصادفي با ساختار ثابت احتمال عملهاي اتوماتا ثابت هستند. درحاليکه در اتوماتاي تصادفي با ساختار متغير احتمالات عملهاي اتوماتا در هر تکرار بِروز ميشوند. در اتوماتاي يادگير با ساختار متغير، تغيير احتمالهاي عملها بر اساس الگوريتم يادگيري انجام ميشود. همچنين در اتوماتاي يادگير با ساختار متغير، وضعيت داخلي اتوماتا توسط احتمالات عملهاي اتوماتا بازنمايي ميشوند. در واقع اتوماتا بصورت يک state-output automata در نظر گرفته ميشود که خروجي آن معادل با وضعيت داخلي آن ميباشد. وضعيت داخلي اتوماتا در لحظه n ، با بردار احتمال عملهاي اتوماتا28 P(n) که در زير آمده است، نشان داده ميشود:
(1-1)
بطوريکه
در آغاز فعاليت اتوماتا، احتمال عملهاي آن با هم برابر و مساوي ميباشند (که r تعداد عملهاي اتوماتا ميباشد).
1-3-1-2- محيط
محيط را ميتوان توسط سهتايي نشان داد که در آن مجموعه وروديهاي محيط، مجموعه خروجيهاي محيط و مجموعه احتمالهاي جريمه ميباشند.
ورودي محيط يکي از r عمل انتخاب شده اتوماتا است. خروجي(پاسخ) محيط به هر عمل i توسط مشخص ميشود. اگر يک پاسخ دودويي باشد، محيط مدلP29 ناميده ميشود. در چنين محيطي بعنوان پاسخ نامطلوب30 يا شکست31 و بعنوان پاسخ مطلوب32 يا موفقيت در نظر گرفته ميشوند. در محيط مدلQ33، شامل تعداد محدودي از مقادير قرار گرفته در بازه [1،0] ميباشد. درحاليکه در محيط مدلS34 مقادير يک متغير تصادفي در بازه [1،0] ميباشد ( ). مجموعه C احتمالات جريمه (شکست) پاسخهاي محيط را مشخص ميکند و بصورت زير تعريف ميشود:
(1-2)
که احتمال اينکه عمل پاسخ نامطلوبي از محيط دريافت کند را نشان ميدهد. مقادير ها نامشخص هستند و فرض ميشود که ها يک مينيمم يکتا دارند. بهمين صورت ميتوان محيط را توسط مجموعه احتمالات پاداش(موفقيت) نشان داد که در اين حالت نشاندهنده احتمال دريافت پاسخ مطلوب به عمل ميباشد. در محيطهاي ايستا35 مقادير احتمال جريمه (ها) ثابت هستند. درحاليکه در محيطهاي غير ايستا36 احتمالات جريمه در طول زمان تغيير ميکند.
شکل1-4: اتوماتاي يادگير تصادفي
ارتباط اتوماتاي تصادفي با محيط درشکل نشان داده شده است. از اين مجموعه به همراه الگوريتم يادگيري تحت عنوان اتوماتاي يادگير تصادفي37 نام برده ميشود. به همين ترتيب اتوماتاي يادگير تصادفي را ميتوان با چهارتايي نشان داد که تعداد عملهاي اتوماتا، مجموعه عملهاي اتوماتا، مجموعه وروديهاي اتوماتا، بردار احتمال عملهاي اتوماتا و الگوريتم يادگيري ميباشد.
1-3-2- معيارهاي رفتار اتوماتاي يادگير
براي اندازهگيري کارايي اتوماتاي يادگير تصادفي، شاخصهاي معيني تعريف شدهاند که امکان مقايسه روشهاي مختلف يادگيري را فراهم ميآورند[15]. يک اتوماتاي شانسي محض بصورت اتوماتايي تعريف ميشود که عملهاي آن هميشه احتمال يکساني براي انتخاب شدن داشته باشند. بنابراين يک اتوماتاي يادگير بايد از يک اتوماتاي شانسي محض بهتر عمل کند.
همانطور که ذکر شد، محيط توسط احتمالات جريمه نشان داده ميشود که احتمال جريمه متناظر با عمل است. مقدار بصورت ميانگين جريمههاي دريافت شده توسط اتوماتا (براي يک بردار عمل مفروض) تعريف و بر اساس رابطه (1-3) محاسبه ميشود.
(1-3)
براي يک اتوماتاي شانسي محض ميانگين جريمهها M(n) يک عدد ثابت است که طبق رابطه (1-4) بدست ميآيد:
(1-4)
بنابراين اتوماتايي که بخواهد بهتر از اتوماتاي شانسي محض عمل کند، بايد ميانگين جريمههاي کمتري از داشته باشد. از آنجايي که يک متغير تصادفي است، اميد رياضي () با مقايسه ميشود. بنابراين تعاريف زير را خواهيم داشت.
تعريف1- يک اتوماتاي يادگير expedient گفته ميشود، اگر:
(1-5)
تعريف2- يک اتوماتاي يادگير بهينه38 گفته ميشود، اگر:
(1-6)
که . در حاليکه بهينه بودن اتوماتا يک ويژگي مطلوب در محيطي ايستا بشمار ميرود، در عمل ممکن است يک کارايي زيربهينه39 مورد نياز باشد. يک محيط واقعي معمولاً متغير است و در نتيجه عمل بهينه در زمان تغيير ميکند. در چنين حالتي و از آنجايي که الگوريتم بر روي هيچ حالت خاصي متوقف نميماند، يک آتوماتاي نيمه-بهينه مناسبتر ميباشد. بنابراين تعريف زير را نيز خواهيم داشت:
تعريف3- يک اتوماتاي يادگيرگفته ميشود، اگر:
(1-7)
تعريف4- يک اتوماتاي يادگير Absolutely Expedient گفته ميشود[19]، اگر:
(1-8)
Expediency بندرت نشان ميدهد که اتوماتاي يادگير بهتر از اتوماتاي شانسي محض عمل
