دانلود پایان نامه ارشد با موضوع يادگيري، ناميده، b

دانلود پایان نامه ارشد

مي‌کند. بنابراين بهينه بودن40 شاخص مناسب‌تري براي مقايسه روشهاي مختلف يادگيري مي‌باشد. بهينه‌بودن اطمينان مي‌دهد که عملي که توسط اتوماتا انتخاب مي‌شود، عملي بهينه باشد. در محيطهاي واقعي بعلت متغير بودن محيط رفتار زير‌بهينه ارجحيت دارد‎[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 برابرباشند، اتوماتاي يادگير 41 ناميده مي‌شود. زمانيکه b مساوي با صفر باشد اتوماتاي يادگير 42 ناميده مي‌شود. اگر b يک عامل تعيين کننده که استفاده از اتوماتاي يادگير تصادفي را در حل مسائل محدود مي‌کند، نرخ همگرايي کند اتوماتاي يادگير است. اين عامل با افزايش تعداد عملهاي اتوماتا تشديد مي‌شود. هرچند استفاده از برخي از روشهاي يادگيري غيرخطي باعث افزايش سرعت همگرايي اتوماتا مي‌گردد.
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 * الگوريتم
الگوريتم يادگيري تقويتي اتوماتاي يادگير در مدل بصورت زير بردار احتمالات عملهاي اتوماتا را بروز مي‌کند‎[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- آتوماتاي سلولي
آتوماتاي سلولي44 (CA)در اواخر دهه 1940 توسط ون‌نيومن45 مطرح و پس از او توسط رياضيداني بنام اولام46 به عنوان مدلي براي بررسي رفتار سيستم‌هاي پيچيده پيشنهاد شد. اتوماتاي سلولي در حقيقت سيستم‌هاي ديناميکي گسسته‌اي هستند که رفتارشان کاملاً بر اساس ارتباط محلي استوار است. اتوماتاي سلولي چندين بار و هر بار تحت نام مختلفي ابداع شده است. از ديدگاه رياضيات محض آنها را مي‌توان شاخه‌اي از ديناميک توپولوژيکي47 و از ديدگاه مهندسي برق، آرايه‌هاي تکرار شونده48 دانست .
در اتوماتاي سلولي، فضا بصورت يک شبکه تعريف مي‌گردد که به هر خانه آن يک سلول گفته مي‌شود. زمان بصورت گسسته پيش مي‌رود و قوانين آن بصورت سرتاسري است که از طريق آن در هر مرحله هر سلول، وضعيت جديد خود را با در نظر گرفتن همسايه‌هاي مجاور خود بدست مي‌آورد. اتوماتاي سلولي را مي‌توان به عنوان سيستم‌هاي محاسباتي نيز در نظر گرفت که اطلاعات کد شده در خودشان را پردازش مي‌کنند. همچنين يک اتوماتاي سلولي بهمراه واحد کنترل آن را مي‌توان بعنوان يک ماشين SIMD49 تعبير نمود .قوانين اتوماتاي سلولي، نحوه تأثير پذيرفتن سلول از سلولهاي همسايه خود را مشخص مي‌کند. يک سلول را همسايه سلول ديگر گوئيم هرگاه بتواند آن را در يک مرحله و براساس قانون حاکم تحت تأثير قرار دهد. مي‌توان در بعضي شرايط براي سلولهاي واقع در مرزها، سلولهاي مرز(هاي) مقابل را بعنوان همسايه در نظرگرفت. در صورتيکه همسايگي بدين صورت در نظر گرفته شود، wrap around و درغير اينصورت محدود شده50 گفته مي‌شود. در بدست آوردن وضعيت کنوني سلول علاوه بر وضعيت قبلي سلولهاي همسايه، مي‌توان وضعيت قبلي خود سلول را نيز دخالت داد. معمولاً قوانين اتوماتاي سلولي توسط کاربر طراحي مي‌شوند. البته براي جستجو در فضاي قوانين راههاي متفاوتي مانند راه‌حلهاي مبتني بر الگوريتمهاي ژنتيک نيز ارائه شده اند. تعريف رسمي‌اتوماتاي سلولي به صورت زير است.
تعريف 5- اتوماتاي سلولي d بعدي يک چندتايي است به طوريکه:
– يک شبکه از d تايي‌هاي مرتب از اعداد صحيح مي‌باشد. اين شبکه مي‌تواند يک شبکه متناهي، نيمه متناهي يا نامتناهي باشد.
– يک مجموعه متناهي از حالتها مي‌باشد.
-،، يک زير مجموعه متناهي از مي‌باشد که بردار همسايگي خوانده مي‌شود. بردار همسايگي، موقعيت نسبي همسايگان را براي هر سلول u در شبکه سلولي به صورت زير مشخص مي‌کند:
(‏1-24)

تابع دو شرط زير را ارضا مي‌کند:
(‏1-25)

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

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

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

که نمايش عدد در مبناي m، N تعداد سلولهاي اتوماتاي يادگير سلولي و ترتيب مشخصي از سلولها مي‌باشد. براي مثال براي يک اتوماتاي يادگير سلولي خطي با 5 سلول و هر سلول با دو حالت 0 و 1 که در حال حاضر الگوي را توليد کرده باشد، حالت مي‌باشد به اين ترتيب آشکار است که تعداد حالاتي که يک اتوماتاي يادگير سلولي مي‌تواند داشته باشد،، است.
تعريف 12- اعداد ولفرام61: با فرض اينکه و در هر سلول يک اتوماتاي يادگير با عمل قرار گرفته باشد، براي توصيف يک قانون خاص مي‌توانيم از روش بازنمايي قانون با استفاده از اعداد ولفرام -که در بازنمايي قوانين در اتوماتاي سلولي استفاده مي‌شود- استفاده کنيم. ابتدا تمام عضو دامنه قانون را به صورت خطي مرتب مي‌کنيم. سپس دنباله‌اي از نتايج مربوط به هر کدام را، بازنمايي يک عدد در مبناي در نظر مي‌گيريم. به اين ترتيب عدد ولفرام قانون مورد نظر معادل دهدهي آن است. براي مثال براي يک اتوماتاي يادگير سلولي خطي با و، قانون شکل قانون شماره 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- آتوماتاي يادگير سلولي نامنظم62 (ICLA)
يک آتوماتاي يادگير سلولي نامنظم (ICLA) يک آتوماتاي يادگير سلولي (CLA) است که محدوديت ساختار مستطيلي گريد درCLA را ندارد(شکل 1-7). کاربردهاي زيادي هستند که نمي توانند با گريد هاي مستطيلي مدل شوند مثل شبکه هاي حسگر بي سيم ،سيستمهاي ايمني مصنوعي ، کاربردهاي مربوط به گراف و … . يک ICLA به صورت يک گراف بدون جهت تعريف مي گردد که هر گره گراف يک سلول را مشخص مي کند که به يک آتوماتاي يادگير مجهز است. آتوماتاي يادگير واقع در يک سلول مشخص، وضعيتش را بر اساس بردار احتمالات اعمالش تعيين مي کند.
شبيه CLA قانوني وجود دارد که ICLA تحت آن عمل مي کند. قانون CLA و اعمال انتخاب شده به وسيله آتوماتاهاي يادگير همسايه در هر آتوماتاي يادگير، سيگنال تقويتي آن آتوماتا را مشخص مي کند. آتوماتاهاي يادگير همسايه هر آتوماتاي يادگير، محيط محلي سلول را تشکيل مي دهد. محيط محلي يک سلول ايستا نيست. زيرا بردار احتمالات اعمال آتوماتاهاي يادگير همسايه در طول تکامل ICLA تغيير مي کند.

شکل‏1-7: آتوماتاي يادگير سلولي نامنظم
1-5- اهداف پايان نامه و ساختار آن
همانگونه که عنوان گرديد، هر چند که در زمينه شبکه هاي تحقيقات زيادي صورت گرفته است، در مورد کيفيت سرويس در اين شبکه ها هنوز به اندازه کافي کار نشده است. از طرفي کيفيت سرويس در شبکه هاي حسگر بي سيم نسبت به شبکه هاي سنتي بسيار متفاوت است. تا آنجا که به طور کامل نمي توان کيفيت سرويس در اين شبکه ها را تشريح نمود. و بسته به کاربرد آنها، پارامترهاي متعددي مد نظر قرار مي گيرند. بعضي از پارامترهايي که در ارزيابي کيفيت سرويس مورد استفاده قرار مي گيرند عبارتند از: پوشش کل شبکه, تعداد بهينه نودهاي فعال در شبکه, طول عمر شبکه و ميزان مصرف انرژي در شبکه.
ويژگيهاي اتوماتاي يادگير نشان ميدهد که اتوماتاي يادگير توانايي حل مناسب مسائل مختلف مطرح در شبکههاي حسگر را دارد. از جمله ويژگيهاي مطرح اتوماتاي يادگير ميتوان به کارسازبودن اتوماتاي يادگير در محيطهاي توزيع‌شده و چند عامله با ارتباطات محدود و اطلاعات ناقص و ساده بودن ساختار اتوماتاي يادگير اشاره کرد.
هدف از اين پاياننامه استفاده از تكنيك اتوماتاهاي يادگير جهت بهبود پارامترهاي کيفيت سرويس در شبكه ها ي حسگر مي باشد. در اين پايان نامه تعدادي از مسائل اساسي شبكه ها ي حسگر بي سيم مطرح گرديده و با هدف بهبود پارامترهاي کيفيت سرويس اين مسائل با استفاده از آتوماتاهاي يادگيرسلولي حل گرديده اند.
اين پايان‌نامه حاوي 5 فصل و 4 ضميمه است.
در فصل دوم، مسئله پوشش محيط در شبكه هاي حسگر با استفاده از غير فعال نمودن نودهاي غير ضروري و فعال نگه داشتن بهينه نودها حل مي گردد. تا در مصرف انرژي صرفه جويي به عمل آمده و عمر شبکه افزايش يابد و بدين ترتيب به چند پارامتر کيفيت سرويس در شبکه هاي حسگر به طور همزمان توجه مي گردد. روش ارائه شده مبتني بر اتوماتاي يادگير سلولي است.
در فصل سوم، به مسئله خوشه بندي در شبکه حسگر پرداخته شده و با استفاده از آتوماتاهاي يادگير سلولي, شبکه هاي حسگر به گونه اي خوشه بندي مي شوند که انرژي به صورت يکنواخت در شبکه بمصرف رسيده وعمر شبکه افزايش يابد. بنابراين در اين روش خوشه بندي معيارهاي کيفيت سرويس انرژي و طول عمر شبکه مد نظر قرار مي گيرند.
در فصل چهارم با استفاده از آتوماتاهاي يادگير يک روش تجميع داده هاي جمع آوري شده محيط حسگري پيشنهاد مي گردد که با شناسايي نودهاي واقع در يک محيط يکسان وغير فعال نمودن نودهاي غير ضروري و حذف داده هاي افزونه در مصرف انرژي شبکه صرفه جويي به عمل آورده و عمر شبکه را افزايش مي دهد ولذا به معيارهاي انرژي شبکه ,طول عمر و تعداد نودهاي فعال توجه مي گردد.
در فصل پنجم يک نتيجه گيري کلي ارائه مي‌شود.
در پيوستهاي اول و دوم مطالب تکميلي راجع به شبکه هاي حسگر بي سيم و آتوماتاي يادگير سلولي آورده شده است. در پيوست سوم نرم افزارشبيه ساز J-Sim تشريح شده و نحوه پياده سازي الگوريتمهاي پيشنهادي با آن توضيح داده شده است.
2-
پوشش محيط در شبكه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگيرسلولي
2-1- مقدمه
شبكه هاي حسگر بي سيم که دامنه كاربردهاي بالقوه وسيعي دارند در فصل اول معرفي گرديدند. اين شبكه ها امكان نظارت وتراكنش بامحيط هايي كه كاربر نمي تواند مستقيما حضور داشته باشد را فراهم مي آورند هدف استقرار اين شبكه ها، جمع آوري داده هاي مناسب براي پردازش وگزارش گيري مي باشد. اين حسگرها به صورت تصادفي در محيط پخش شده واطلاعات را از محيط جمع آوري كرده وبا ارتباطات راديويي وبه صورت گام به گام به ايستگاه پايه منتقل مي نمايند.
يكي از مسائل مهمي كه در بحث شبكه هاي حسگر بي سيم مطرح است مسئله پوشش حسگري شبكه است اين مسئله ازاين سوال اساسي ناشي مي گردد “حسگر ها چگونه استقرار يابند كه تمام محيط فيزيكي مورد نظر را پوشش دهند ؟” مسئله پوشش يكي ازمعيارهاي كيفيت سرويس (QOS) در شبكه هاي حسگر بي سيم مي باشد. هدف مسئله پوشش اين است كه هر مكان در محيط فيزيكي مورد نظر در دامنه حسگري حداقل يك حسگر قرار بگيرد. از آنجاييكه شبكه حسگر شامل نودهاي بسيار زيادي است براي پخش نودها درمحيط نمي توان مكان نودها را از قبل مشخص كرد. ونودها را به صورت دستي در محيط قرار داد بلكه نودها به صورت تصادفي در محيط پخش مي گردند . بنابراين براي اينكه كل محيط به صورت كامل پوشش داده شود تعداد حسگر هايي كه در محيط پخش مي گردند بيش از تعداد حسگرهايي است كه اگر به صورت قطعي پخش مي شدند كل محيط را پوشش مي دادند. يعني براي اينكه محيط به صورت كامل پوشش داده شود حسگرها به صورت متراكم توزيع مي گردند. مسئله ديگري كه اينجا بايد مد نظر قرار گيرد مصرف انرژي در حسگرها است. از آنجاييكه انرژي حسگرها، از طريق باطري تامين مي گردد وبه دليل تعداد زياد حسگرها ودر دسترس نبودن محيط، امكان تعويض يا شارژ مجدد باطري حسگرها وجود ندارد با تخليه باطري يك حسگر در حقيقت عمر حسگر به اتمام مي رسد وپس از، از بين رفتن تعدادي از حسگرها ونقض مسئله پوشش واتصال شبكه، عمر شبكه حسگر به اتمام مي رسد. عمر شبكه حسگر نيز يكي از معيارهاي كيفيت سرويس در شبكه هاي حسگر است كه بايد تا حد امكان عمر شبكه طولاني تر شود.
با در نظر گرفتن دو موضوع مطرح شده توزيع متراكم حسگرها جهت تضمين پوشش شبكه ومصرف انرژي مي توان راهكاري ارائه داد كه در عين تضمين پوشش شبكه مصرف انرژي شبكه را كاهش داده وعمر شبكه را افزايش دهد. يعني دو معيار كيفيت سرويس مطرح شده را برآورده نمايد.
بدين صورت كه تعدادي از نودهاي شبكه كه با غير فعال شدن آنها به پوشش محيط توسط شبكه لطمه وارد نمي شود را غير فعال مي نماييم ودر مواقع لزوم آنها را فعال مي كنيم بدين ترتيب مصرف انرژي كلي شبكه كاهش يافته وعمر شبكه افزايش مي يابد.
2-1-1- اشكال مختلف طراحي
يك گروه مهم از شبكه هاي حسگر بي سيم كه شبكه هاي حسگر بي سيم موردي ناميده مي شوند، به صورت تصادفي استقرار مي يابند. يعني مكان نودها از قبل مشخص نيست، استقرار تصادفي نودها زماني انجام مي گيرد كه نتوان نودها را به صورت منفرد در محيط قرار داد مانند استقرار شبكه در محيط هاي جنگي وسوانح طبيعي. ويژگي هاي شبكه هاي حسگر بي سيم منابع محدود، شبكه هاي متراكم وبزرگ وتوپولوژي پويا است و معمولا حسگرهايي كه در محيط قرار مي گيرند بيش از حد نياز براي پوشش كل شبكه هستند (در مقايسه با پخش حسگرها به صورت بهينه ) اندازه يك شبكه ممكن است به صدها يا حتي هزاران نود حسگر برسد . اگر حسگرها بتوانند به طور دقيق هر جا كه لازم است قرار گيرند به شيوه قطعي استقرار يافته اند. يك حسگر مي تواند در يكي از چهار حالت انتقال،‌دريافت، بيكار يا خواب (غير فعال) باشد . حالت بيكار زماني است كه حسگر درحال ارسال يا دريافت نيست وحالت خواب حا لتي است كه امواج راديويي حسگر خاموش باشند ، آنچنانچه در [34] ذكر شده است مصرف انرژي حسگر WIVS Rockwell براي حالت هاي ارسال، دريافت ،‌بي كار و خواب برابر با 0.7w و0.03w,0.34w,0.36w مي باشد در حالي كه انرژي در حالت حسگري 0.02w مي باشد.
الگوريتمهاي پوششي پيشنهاد شده يا به صورت متمركز يا توزيع شده ومحلي هستند. در الگوريتم هاي توزيع شده فرايند تصميم گيري به صورت توزيع شده صورت مي گيرد. دراين الگوريتم ها هر نود به صورت محلي وصرفا براساس اطلاعات خودش وهمسايگانش تصميم گيري مي كند. ولي درروش هاي متمركز فرايند تصميم گيري در ايستگاه مركزي وبراساس اطلاعات كليه نودهاي موجود صورت مي گيرد. از آنجاييكه شبكه هاي حسگر بي سيم يك توپولوژي پويا دارند ولازم است كه تعداد زيادي از نودها مورد بررسي قرار گيرند، الگوريتم هاي پوشش بايد به صورت محلي وتوزيع شده طراحي گردند تا معماري شبكه والگوريتم، مقياس پذير وقابل گسترش باشند.
بامداخله مفهوم پوشش وبراساس موردي كه بايد پوشش داده شود (ناحيه يا نقاط گسسته) وبراساس طراحي هاي مختلف مسائل مختلفي مي تواند مد نظر قرار گيرد.
* روش استقرار حسگر
قطعي در مقابل تصادفي، ‌درمحيط هاي مساعد وقابل دسترسي ممكن است بتوان از روش استقرار قطعي حسگرها استفاده كرد درحاليكه در محيط هاي نامساعد، جنگي وكاربردهاي از راه دور وزماني كه تعداد حسگرها زيادند استقرار حسگرها به صورت تصادفي صورت مي گيرد.
* برد حسگري وبرد ارتباطي
برد حسگري در حسگرهاي شبكه حسگر مي تواند برابر با برد ارتباطي باشد ويا متفاوت با آن باشد كه در مسائل مطرح شده در زمينه پوشش بايد اين موضوع مد نظر قرار گيرد.
* ويژگي هاي الگوريتم
متمركز در برابر توزيع شده/ محلي.
* هدف مسئله
هدف مسئله پوشش مي تواند حداكثر كردن عمر شبكه باشد يا به حداقل رساندن تعداد حسگرهاي فعال.
2-2- دسته بندي مسائل پوشش در شبکه هاي حسگر
ما به طور كلي برروي مسئله پوشش در شبكه هاي حسگر ايستا کار مي كنيم بدين معنا كه فرض براين است که از وقتي كه نودهاي حسگر در محيط مستقر مي شوند حركت نمي كنند وجايشان ثابت است. در ضمن منطقه حسگري، ديسكي است به مركزيت حسگر وشعاع برد حسگري ومنطقه ارتباطي هر حسگر، ديسكي است به مركزيت حسگر وشعاع برد ارتباطي حسگر. بيشتر مسائلي كه دراين زمينه مطرح شده اند بدين صورت دسته بندي مي گردند[35]: پوشش ناحيه اي، پوشش نقطه اي وپوشش مرزي كه در ادامه مورد بحث قرار مي گيرند:
2-2-1- پوشش ناحيه اي
بيشتر مسائل مطالعه شده در زمينه پوشش، مسائل پوشش ناحيه اي هستند كه دراين مسائل هدف اصلي شبكه حسگر اين است كه يك ناحيه يا يك منطقه را تحت پوشش حسگري حسگرهايش قرار دهد.
شکل 2-1 مثالي از توزيع تصادفي حسگرها جهت پوشش يك ناحيه مربع شكل را نشان مي دهد. همان گونه كه مشاهده مي كنيد اگر فقط نودهاي به رنگ سياه فعال بمانند. كل ناحيه را پوشش مي دهند. وبقيه نودها مي توانند غير فعال گردند. هدف اصلي مسئله پوشش ناحيه اي شبكه حسگر اين است كه شبكه، محيط را به گونه اي پوشش دهد كه مصرف انرژي حسگرهاي شبكه به صورت كارا باشد. مصرف كاراي انرژي يكي از دغدغه هاي اصلي در شبكه هاي حسگر بي سيم است كه داراي منابع انرژي محدودند. مكانيزم هايي كه از مصرف زياد انرژي در شبكه هاي حسگر جلوگيري مي كنند، باعث افزايش طول عمر شبكه مي شوند. طول عمر شبكه به طور كلي فاصله زماني در نظر گرفته مي شود كه شبكه مي تواند عمليات حسگري وانتقال داده ها به ايستگاه پايه را انجام دهد. در طول حيات شبكه بعضي از نودها ممكن است از بين بروند (به دليل خرابيهاي فيزيكي يا تخليه منبع انرژي ) يا نودهاي اضافي در شبكه استقرار يابند. مكانيزم موثري كه اغلب مورد استفاده قرار مي گيرد، زمانبندي فعاليت نودهاي حسگر وقرار دادن نودهاي اضافي درحالت غير فعال تا زمان ممكن، مي باشد ، جهت طراحي چنين مكانيزمي ما بايد به سوالات زير پاسخ دهيم :
* نود بر اساس چه قواعدي بايد لزوم فعال يا غير فعال شدن خود را تشخيص دهد؟
* در چه زماني نودها بايد چنين تصميمي بگيرند؟
* چه مدت بايد يك نود درحالت غير فعال بماند؟

شکل‏2-1 : پوشش ناحيه اي
در ادامه به تعدادي ازمكانيزمهايي كه بدين منظور مورد استفاده قرار گرفته اند اشاره مي شود: در كارهاي [36] و[37] جمعيت زيادي از حسگرها، به صورت تصادفي جهت مشاهده محيط استقرار مي يابند وهدف اين است كه به يك طراحي با مصرف انرژي به صورت كارا كه پوشش شبكه را نيز حفظ مي كند برسيم. از آنجاييكه تعداد نودهاي مستقر در محيط بيش از تعداد مورد نياز جهت مشاهده محيط در حالت بهينه است، راه حل پيشنهادي اين است كه نودها به مجموعه هاي متصل تقسيم گردند. وزماني كه يك مجموعه از حسگرها فعالند، بقيه حسگرها بايد درحالت غير فعال قرار گيرند. هدف روش اين است كه حداكثر تعداد مجموعه هاي منفصل را بيابد كه اين مطلب مستقيما برروي طول عمر شبكه تاثير مي گذارد. راه حل هاي ارائه شده در اين دو كار به صورت متمركز عمل مي كنند. در [36] محيط به صورت مجموعه اي از ميادين مدل مي گردد به طوري كه نقاط هر ميدان به وسيله مجموعه يكساني از حسگرها تحت پوشش قرار مي گيرند. الگوريتم [36] پوشش هاي منفصل را با انتخاب حسگرهايي كه عنصر بحراني (ميداني كه به وسيله مينيمم تعداد حسگرها پوشش داده مي شود) را پوشش مي دهند وبا اولويت دادن به حسگرهايي كه تعداد ميدان هاي پوشش داده نشده بيشتري را پوشش مي دهند يا ميدان هايي را پوشش مي دهند كه حسگرهاي كمتري آنها را پوشش مي دهند به مسئله پوشش مي پردازد. وحسگرهايي كه ميدان هاي پوشش داده شده را پوشش نمي دهند، به صورت پي در پي محاسبه مي كند. در [37] مجموعه هاي منفصل به صورت مجموعه هاي كنترلي منفصل مدل مي گردند محاسبه ماكزيمم تعداد مجموعه هاي كنترلي منفصل يك مسئله NP-Complete است و براي حل آن الگوريتم رنگ آميزي گراف پيشنهاد شده است. شبيه سازيها نشان داده اند كه مجموعه هاي محاسبه شده بين 5/1 تا 2 برابر بيش از مجموعه هاي بدست آمده توسط الگوريتم [36] بوده است با كمتر از 5 درصد فقدان پوشش شبكه.
مكانيزم پوشش مبتني بر زمان بندي نود ديگري در [38] پيشنهاد شده است. اين پروتكل به صورت توزيع شده ومحلي عمل مي كند. دراين پروتكل با استفاده از يك قاعده، تشخيص داده مي شود كه آيا ناحيه حسگري نود در ناحيه حسگري همسايگانش قرار مي گيرد ياخير. راه حل تشخيص اينكه آيا پوشش يك نود به وسيله همسايگانش پشتيباني مي گردد، در چندين حالت ارائه گرديده است: زماني كه نودها دامنه حسگري يكسان دارند وموقعيتشان را مي دانند، زماني كه نودها دامنه حسگري يكسان دارندومي توانند اطلاعات جهتي نود همسايه را بدست آورند. وزماني كه نودها دامنه حسگري متفاوتي دارند. شماي زمانبندي نود به دورهايي تقسيم مي گرد به طوري كه هر نود يك فاز زمان بندي دارد وسپس يك فاز حسگري. در فاز زمان بندي نود بايد شايستگي غير فعال شدن را تشخيص دهد. نودهاي انتخاب شده براي غير فعال شدن واحد هاي ارتباطي وحسگري خود راغير فعال مي كنند. درحالي كه بقيه نودها در فازحسگري عمل حسگري را انجام مي دهند. جهت بدست آوردن اطلاعات همسايگان، هر نود در شروع هر دور، يك پيام اعلان موقعيت شامل شماره شناسايي ومكان نود به صورت پخشي ارسال مي نمايد. اگر يك نود وپشتيبانش به طورهمزمان قاعده شايستگي را اجرا نمايند، ممكن است به طور همزمان تصميم به غير فعال شدن بگيرند كه باعث ايجاد نقاط كور در ناحيه مي شود.
براي اينكه اين مشكل پيش نيايد بدين صورت عمل مي شود كه هر نود ارزيابي را بعد از يك زمان تصادفي شروع مي كند واگر تصميم گرفت كه غير فعال گردد يك پيام به همسايگانش ارسال مي كند وسپس مدت زماني مشخص منتظر مي ماند واگر پيام بروزرساني از همسايگانش دريافت نكرد غير فعال مي گردد. اين تحقيق مكانيزم هاي همزماني رابه صورت تفصيل مشخص نكرده است. اين كار به صورت يك توسعه بر پروتكل خوشه بندي LEACH [39] پياده سازي شده است ونتايج شبيه سازي افزايش 7/1 برابري در ميانگين زمان حيات سيستم را نشان مي دهد.
در [40] يك راه حل زمان بندي نود مبتني بر كاوش، براي مسئله پوشش با مصرف كاراي انرژي پيشنهاد شده است. در اينجا حسگرها دامنه حسگري يكساني دارند. قاعده تشخيص شايستگي نود جهت غير فعال شدن براساس يك مكانيزم کاوش طرح ريزي شده است. حسگر يك پيام كاوش PRB با برد R ارسال مي كند. هر نود كه اين پيام را دريافت كند با يك پيام PRB-RPY پاسخ مي دهد. اگر حداقل يك پاسخ دريافت شود، نود به حالت غير فعال مي رود. برد كاوش براساس چگالي مطلوب نود (تعداد نودها به واحد ناحيه) يا براساس افزونگي مطلوب پوشش تعيين مي گردد. درحالي که زمان فعال براساس زمان تناوب حسگري تحمل پذير مشخص مي شود. اين پروتكل، توزيع شده محلي است پيچيدگي آن پايين است اما پوشش ناحيه را به طور كامل تضمين نمي كند.
در [41] مسئله پوشش به عنوان يك مسئله تصميم گيري مدل شده است، بدين صورت كه يك مجموعه از حسگرها در يك محيط هدف پخش شده اند. مسئله اين است كه تشخيص داده شود كه آيا محيط k-پوششي هست يا خير. بدين معنا كه هر نقطه از محيط هدف بوسيله حداقل k حسگر تحت پوشش قرار مي گيرد يا خير؟ به طوري كه K يك پارامتر داده شده است. بدين منظور هر حسگر محيط حسگري اش را بررسي مي كند تا مشخص كند كه آيا تمام ناحيه اش -kپوششي است؟ با جمع آوري اطلاعات تمام حسگرها يك جواب درست بدست مي آيد.
2-2-2- پوشش نقطه اي
در مسئله پوشش نقطه اي هدف اين است كه يك مجموعه از نقاط پوشش داده شوند. شکل‏2-2, مثالي را نشان مي دهد كه در آن يك مجموعه از حسگرها به صورت تصادفي در يك محيط مربع شكل پخش شده اند تا يك مجموعه از نقاط را پوشش دهند. نودهاي نشان داده شده به رنگ سياه از مجموعه نودها مي توانند اين نقاط را پوشش دهند. در اين مسئله لازم نيست كه كل محيط تحت پوشش قرار گيرد.

شکل‏2-2: پوشش نقطه اي
در ادامه روشي جهت حل اين مشكل از مسئله پوشش ارائه گرديده است:
سناريوي پوشش نقطه اي ارائه شده در ]42[ كاربرد نظامي دارد. در اين سناريو تعداد محدودي نقطه با مكانهاي مشخص در محيط در نظر گرفته مي شوند كه بايد پوشش داده شوند. و تعداد زيادي حسگر به صورت تصادفي در محيط قرار دارند. هدف اين است كه هر نقطه (هدف) بايد به وسيله حداقل يك حسگر مشاهده گردد. با اين فرض كه هر حسگر مي تواند تمام اهداف واقع در برد حسگري اش را مشاهده نمايد.
يك روش براي افزايش عمر شبكه در چنين محيطي اين است كه كل حسگرها به مجموعه هاي منفصلي تقسيم مي گردند. به طوري كه هر مجموعه به طور كامل همه اهداف را پوشش دهد. اين مجموعه ها به صورت متوالي فعال مي گردند. به طوري كه در هر زمان فقط يك مجموعه فعال باشد. هدف اين روش اين است كه حداكثر تعداد چنين مجموعه هاي منفصلي را بيابد تا فاصله زماني بين هر دو زمان فعاليت يك نود زياد شود. يك راه حل براي اين مسئله در ]42[ ارائه شده است. نويسنده ثابت كرده است كه مسئله پوشش مجموعه هاي منفصل يك مسئله NP-complete است و يك الگوريتم اكتشافي كارا جهت محاسبه مجموعه ها با استفاده از يك شكل برنامه نويسي صحيح مختلط پيشنهاد مي دهد.
2-2-3- پوشش مرزي
در پوشش مرزي هدف به حداقل رساندن احتمال نفوذ شناسايي نشده از طريق مرز شبكه حسگر مي باشد.

شکل، يك مسئله پوشش در حالت كلي را نشان مي دهد كه نقاط شروع و پايان مسير از خطوط مرزي پايين و بالا انتخاب شده اند انتخاب مسير به هدف مسئله بستگي دارد. يك مدل از مسئله پوشش مرزي در ادامه تشريح مي گردد:
مسئله پوشش مرزي ارائه شده در ]43[ بدين صورت ارائه گرديده است:
يک ميدان با تعدادي حسگر و دو نقطه ابتدايي و انتهايي داده شده اند و يک عامل بايد در اين ميدان از نقطه ابتدايي تا نقطه انتهايي جابجا گردد. مسئله پيدا کردن مسير نفوذ ماکزيمم(MBP) و مسير پشتيباني ماکزيمم(MSP) عامل مي باشد. MBP ميانگين بدترين مورد است و اين خاصيت را داراست که براي هر نقطه روي اين مسير فاصله تا نزديکترين حسگر بيشينه است. و MSP برعکس اين خاصيت را دارد که براي هر نقطه روي اين مسير، فاصله تا نزديکترين حسگر کمينه است. اين مدل نودهاي حسگر را همگن در نظر گرفته و فرض مي کند که نودها موقعيت خود را مي دانند(مثلا با استفاده از GPS). و حساسيت حسگري نودها با افزايش فاصله کم مي شود. نويسندگان يک راه حل متمرکز براي اين مسئله پيشنهاد داده اند. بر اين اساس که MBP بر روي خطوط نمودار voronoi و MSP را بر روي خطوط مثلثي Delaunay قرار مي دهند. الگوريتم پيشنهادي با تشکيل نمودار voronoi (يا نمودار مثلثي Delaunay) شروع مي گردد. و سپس به هر قسمت وزني معادل با فاصله تا نزديکترين حسگر(يا معادل با طول قسمت) تخصيص مي دهد و بعد از جستجوي دودويي يا جستجوي اول-سطح براي محاسبه مسير استفاده مي نمايد.

شکل ‏2-3: پوشش مرزي
2-3- روش پوشش CCP63
در اينجا به عنوان نمونه يکي از کارهاي انجام گرفته در زمينه پوشش در شبکه هاي حسگر بي سيم که يکي از بهترين روشهاي پوشش مي باشد معرفي مي گردد.
2-3-1- فرضيات مسئله
در روش [44]CCP هدف اين است که محيط مورد نظر درجه پوشش Ks را دارا باشد. بدين معنا که هر نقطه در محيط بايد توسط حداقل Ks نود فعال پوشش داده شود. در ضمن بيشترين تعداد نودهاي ممکن، غير فعال گردند. هر چه درجه پوشش شبکه در محيط بالاتر باشد، دقت حسگري محيط بالاتر بوده و در برابر خرابي نودها قابليت اطمينان بيشتري خواهد داشت. از طرفي درجه پوشش بالاتر موجب فعال ماندن تعداد نودهاي بيشتري شده و عمر شبکه کاهش مي يابد. فرضيات زير در مسئله مد نظر قرار گرفته شده اند:
* هر نود v يک ناحيه حسگري S(v) دارد. که هر نقطه در اين ناحيه به وسيله نود v پوشش داده مي شود.
* ناحيه حسگري هر نود به صورت يک دايره است.
* ناحيه حسگري تمام نودها شعاعي يکسان و برابر با Rs دارد که ناحيه حسگري نود v را C(v,Rs) مي ناميم.
* هر دو نود v و u در صورتي که در شعاع ارتباطي(Rc) يکديگر قرار داشته باشند يعني باشد، مي توانند مستقيما بايکديگر ارتباط برقرار نمايند.
* هر نود موقعيت جغرافيايي دقيقش را ميداند.
2-3-2- تشريح روش
در CCP هر نود اطلاعاتي مثل موقعيت جغرافيايي و وضعيت خود را به نودهاي همسايه ارسال مي دارد. و هرنود بر اساس اطلاعاتي که از نودهاي همسايه بدست مي آورند و با استفاده از الگوريتم شايستگي وضعيت مناسب خودش را محاسبه مي کند که آيا بايد به حالت فعال درآيد يا غيرفعال شود. الگوريتم شايستگي نودها بدين صورت مي باشد: هر نود مختصات نقاط تقاطع محيط دايره حسگري نودهاي همسايه، يا نقاط تقاطع محيط دايره حسگري نودها با مرزهاي محيط، که در ناحيه حسگري اين نود قرار دارند را بدست مي آورد. سپس به ازاي تمام نودها، چک مي شود که آيا اين نقاط در دايره حسگري حداقل Ks نود حسگر فعال قرار دارند يا خير؟ اگر تمام اين نقاط حائز چنين شرطي بودند، در آن صورت اين نود، افزونه است. در غير اين صورت اين نود شايسته فعال شدن مي باشد. شبه کد الگوريتم در شکل 2-4 نشان داده شده است.

شکل‏2-4: شبه کد الگوريتم شايستگي در CCP
بر اساس الگوريتم شايستگي نودهاي حسگر مي توانند بين حالات متفاوتي تغيير وضعيت دهند. هر نود مي تواند در يکي از حالات فعال، خواب و گوش دادن باشد. در حالت خواب، نود، اجزاي راديويي اش را خاموش مي نمايد تا در مصرف انرژي، صرفه جويي به عمل آيد. هر نودي که در حالت خواب قرار دارد، در فواصل زماني مشخص، به حالت گوش دادن مي رود تا پيامهاي همسايگان را دريافت نموده و بر اساس آن وضعيت شايستگي اش را مجدداّ با استفاده از الگوريتم شايستگي چک کند. در حالت فعال نود محيطش را حس مي کند. و با نودهاي ديگر ارتباط برقرار مي نمايد. اگر چگالي نودها در محيط نيز افزايش يابد، و نودي خودش را افزونه تشخيص دهد، به حالت خواب تغيير وضعيت مي دهد.
از آنجاييکه هر نود بر اساس اطلاعات محلي و به صورت مستقل وضعيتش را چک مي کند، ممکن است بين تغيير وضعيتها در يک همسايگي تداخلاتي پيش آيد. به عنوان مثال زماني که يک نود فعال مي ميرد، ممکن است، به طور همزمان چند تا ازنودهاي خواب همسايه، خود را شايسته فعال شدن تشخيص داده و فعال گردند و پوشش غيرضروري بيش از حدي ايجاد گردد. براي اينکه اين مشکل پيش نيايد، از دو حالت گذراي پيوستن64 و عقب نشستن65 استفاده مي گردد.
اگر نود غيرفعالي خودش را شايسته تشخيص دهد، بلا فاصله فعال نمي گردد. بلکه به حالت “پيوستن” مي رود. و تا مدت زمان مشخصي در اين حالت باقي مي ماند. و در انتهاي اين بازه زماني دوباره الگوريتم شايستگي را اجرا مي نمايد. و اگر مجددا خود را شايسته يافت به حالت فعال مي رود. و در غير اين صورت به حالت خواب برمي گردد. هر نود جهت انتقال از حالت فعال به حالت خواب نيز به همين صورت، ابتدا وارد حالت گذراي “عقب نشيني” مي شود. چرخه حالات نودهاي حسگر در روش CCP در شکل 2-5 نمايش داده شده است.

شکل‏2-5 : نمودار تغيير حالات نودها در CCP
2-4- حل مسئله پوشش(k-پوششي ) با استفاده از آتوماتاهاي يادگير
همانطور كه در بخش 2-2 ملاحظه نموديد كارهاي مختلفي در زمينه پوشش در شبكه هاي حسگر بي سيم كه يكي از معيارهاي كيفيت سرويس در اين شبكه ها است انجام گرفته است. الگوريتم هاي ارائه شده در اين زمينه به دو دسته كلي تقسيم مي گردند:
1) ‌الگوريتم هاي متمركز 2) الگوريتم هاي توزيع شده و محلي
به دليل ماهيت توزيع شدگي شبكه هاي حسگر بي سيم و تعداد زياد نودها، الگوريتم هاي متمركز براي حل مسئله پوشش كارايي چنداني ندارند. حل اين مسئله با استفاده از الگوريتم هاي متمركز باعث افزايش حجم ارتباطات بين نودها و در نتيجه كاهش سريع انرژي نودها، مخصوصاً نودهاي نزديكتر به ايستگاه پايه مي گردد كه اين امر خود از عمر شبكه مي كاهد. از طرفي مسئله پوشش در حالت متمركز يك مسئله NP-complete مي باشد كه به دليل زياد بودن تعداد نودها اجراي الگوريتم بسيار زمانبر خواهد بود. مسئله ديگري كه وجود دارد اين است كه شبكه هاي حسگر بي سيم وضعيت پويايي دارند و در طول حيات شبكه بعضي از نودها ممكن است به دليل صدمات فيزيكي يا تخليه انرژي از بين بروند و يا ممكن است نودهاي جديدي به شبكه افزوده شوند. در استفاده از الگوريتم هاي متمركز، هر تغيير در شبكه بايد به اطلاع ايستگاه مركزي رسيده و با هر تغيير، الگوريتم بايد مجدداً اجرا گردد كه هم حجم محاسبات و هم حجم ارتباطات زياد مي شود.
بنابراين مسئله پوشش در شبكه هاي حسگر بايد به صورت محلي و توزيع شده حل گردد. امامشكل اساسي كه در الگوريتم هاي توزيع شده ارائه شده در اين زمينه وجود دارد اين است كه نودهاي حسگر به صورت محلي و همزمان و براساس نودهاي فعال همسايه تصميم مي گيرند كه فعال باشند يا غير فعال گردند و در همين زمان، وضعيت نودهاي همسايه مشخص نيست و آنها نيز در حال تصميم گيري براساس وضعيت نودهاي همسايه خود هستند. بنابراين هر نود جهت تصميم گيري اطلاعات كافي (وضيعت نودهاي همسايه) در اختيار ندارد. راه حلي كه در بعضي از الگوريتم هاي توزيع شده پيشنهاد گرديده است، اين است كه نودها به صورت همزمان تصميم گيري نكنند، بلكه با فواصل زماني تصادفي نسبت به مبدا زمان، الگوريتم خود را اجرا نمايند. در اين حالت به دليل تعداد زياد نودها و تصادفي بودن زمان اجراي الگوريتم در نودها، تداخلات و همزماني هايي پيش مي آيد كه باعث بروز مشكل قبل مي گردد. در ضمن اگر جهت كاهش تعداد تداخلات بازه انتخاب زمان را طولاني در نظر بگيريم زمان همگرايي الگوريتم افزايش مي يابد.
از طرفي در روشهاي ارائه شده مسئله انرژي مد نظر قرار نگرفته است. و بنابراين ممكن است نودهايي فعال نگه داشته شوند كه انرژي كمي داشته باشند كه باعث مي گردد اين نودها سريع از بين بروند.
راه حلي كه ما جهت رفع اين مشكلات و ارائه الگوريتم هاي توزيع شده كارا براي حل مسئله پوشش در شبكه هاي حسگر بي سيم، پيشنهاد مي دهيم، استفاده از روشهاي هوشمندي است كه به صورت توزيع شده عمل مي نمايند. روش هوشمندي كه با شكل و صورت اين مسئله كاملاً سازگار است و مي تواند در حل اين مسئله به ما كمك كند، استفاده از اتوماتاهاي يادگير سلولي مي باشد. در اين روش در حالت كلي، هر نود به صورت يك ماشين يادگير عمل مي كند. كه براساس وضعيتي كه انتخاب مي كند (فعال يا غيرفعال) از محيط و شبكه پاداش دريافت نموده يا جريمه مي گردد و بدين ترتيب به مرور زمان وضعيت مناسب خود را ياد مي گيرد. ما در فصل اول اتوماتاهاي يادگير سلولي را معرفي نموده ايم. در ادامه به ارائه راهكارهايي جهت حل مسئله پوشش در شبكه هاي حسگر بي سيم با استفاده از اتوماتاهاي يادگير مي پردازيم.
در ضمن مسئله پوششي که مد نظر ماست، مسئله k-پوششي يا پوشش با درجه k است. بدين معنا که قصد داريم هر نقطه از شبکه حداقل توسط k نود حسگر فعال تحت پوشش قرار گيرد. اين مسئله، کلي تر از مسئله پوشش ساده است. مسئله پوشش ساده يک مسئله k-پوششي با مقدار k برابر با يک مي باشد.
2-4-1- فرضيات و مدل مسئله
در اين مسئله هدف اين است كه شبكه حسگر محيطش را به گونه اي پوشش دهد كه انرژي شبكه به صورت كارا مصرف گردد. و به صورت كلي قصد داريم كه اهداف زير براورده گردند:
– كاهش مصرف انرژي كلي شبكه
– كاهش مصرف انرژي هر نود به تنهايي
– كاهش سربار ارتباطي ارسال داده ها
– حفظ پوشش كلي شبكه
rs برابر با برد حسگري هر حسگر مي باشد و rc را برابر با برد ارتباطي در نظر مي گيريم و فرض مي كنيم كه rc>=2rs . بدين معنا كه نودها مي توانند مستقيماً با نودهايي كه فاصله آنها تا اين نود به اندازه دو برابر برد حسگري است، ارتباط برقرار نماييد. اگر اين شرط برقرار باشد، در صورتي که درجه پوشش محيط يک باشد شبکه قطعا متصل نيز خواهد بود[44]. يعني تمام نودها مي توانند با نود سينک ارتباط برقرار نمايند. در اكثر حسگرهاي واقعي اين وضعيت برقرار است براي مثال [45]MICAII برد ارتباطي حدود هزار متر دارد در حالي كه برد حسگري آن حدود صد متر مي باشد. نودهايي كه در فاصله ارتباطي يك نود قرار دارند و نود مي تواند مستقيماً با آنها اطلاعات مبادله نمايد، تحت عنوان نودهاي همسايه اين نود در نظر گرفته مي شوند. فرض بعدي اين است كه هر نود موقعيت خودش را مي داند كه مي تواند موقعيتش را با استفاده از سيستم GPS با انرژي پايين بدست آورده باشد [46] يا با استفاده از روشهاي مكان يابي كه براي شبكه هاي حسگر طراحي شده است[47,48,49,50].
در ضمن محيط به صورت دو بعدي در نظر گرفته مي شود و نودهاي حسگر به صورت تصادفي در محيط پخش شده اند و ناحيه حسگري هر نود حسگر برابر با ديسكي به مركزيت نود و شعاع rs در نظر گرفته شده و ناحيه ارتباطي آن ديسكي به مركزيت نود و شعاع rc مي باشد.
فرض بعدي كه در نظر گرفته شده است اين است كه تمام نودهاي محيط همسان هستند يعني rs، تمام نودها يكسان بوده و rc آنها نيز مثل هم مي باشد.
در اين روش ما فرض مي کنيم که هر نود مي تواند دو وضعيت فعال وغير فعال داشته باشد. زماني که نود غير فعال است مصرف انرژي اش به حداقل مي رسد. هدف ما اين است که تعداد نودهاي غير فعال در هر زمان را حداکثر نماييم ودر عين حال مسئله پوشش شبکه نيز تضمين شده باشد. بدين منظور هر نود جهت غير فعال شدن بايد بررسي کند که آيا ناحيه حسگري اش توسط k نود فعال همسايه به طور کامل تحت پوشش قرار گرفته است يا خير؟
اگر ناحيه حسگري يک نود توسط k نود فعال همسايه اش قابل پوشش باشد ما اين نود را نود افزونه مي ناميم . افزونه بودن يک نود را با استفاده از روشي که ادامه توضيح داده مي شود، مشخص مي کنيم.
2-4-2- روش تشخيص افزونه بودن نود حسگر
با توجه به فرضيات مسئله هر نود مختصات و موقعيت خود را مي داند و مي تواند مختصات خود را به همسايگانش نيز ارسال نمايد. بنابراين هر نود حسگر مختصات خود وهمسايگانش را دارد. همانگونه كه درشکل 2-6, مشاهده مي نماييد, نودهايي كه در برد ارتباطي(rc) يك نود قرار داشته باشند همسايه آن به حساب مي آيند. حال جهت محاسبه اينکه آيا همسايگان اين نود مي توانند ناحيه تحت پوشش اين نود را پوشش دهند يا خير، ما ناحيه حسگري اين نود را به صورت يک محيط گريدي مجازي در نظر مي گيريم. مثلا به صورت يک مربع گريدي که محاط بر ديسک حسگري نود باشد (شکل 2-7). در مورد اينکه اندازه واحدهاي گريد چقدر در نظر گرفته شود در بخشهاي بعدي بحث خواهد شد. اکنون جهت اينکه تضمين گردد ناحيه حسگري اين نود، توسط حداقل k نود همسايه پوشش داده مي شود, کافيست که هر نقطه گريدي واقع در ناحيه حسگري اين نود حداقل توسط k حسگر همسايه پوشش داده شود. اگر مختصات نودهاي همسايه را داشته باشيم، براي اينکه وجود يک نقطه گريدي در برد حسگري يک نود حسگر مورد بررسي قرار گيرد، بايد فاصله نقطه گريدي تا محل نود مورد نظر كمتر از برد حسگري نود باشد.

شکل ‏2-6: نود حسگر موقعيت خود و همسايگانش را مي داند

شکل ‏2-7: مربع گريدي دربرگيرنده ديسك حسگري نود حسگر
فرض که نود مورد بررسي h همسايه داشته باشد وتعداد نقاط گريدي واقع در محيط حسگري آن n تا باشند. در اين صورت بايد فاصله هر نقطه گريدي را تا هر يك از همسايگان بدست آورد، تا مشخص گردد كه آيا اين نقطه در برد حسگري همسايگان نود قرار مي گيرد يا خير. با kامين جواب مثبت بررسي متوقف مي گردد. در اين صورت اين نقطه حداقل توسط k تا از همسايه ها پوشش داده مي شود. اگر اين نقطه در ناحيه حسگري k تا از نودهاي همسايه قرار نگيرد، بررسي بقيه نقاط لازم نيست و اين نود يک نود افزونه نخواهد بود. چون حداقل يک نقطه در ناحيه حسگري اش وجود دارد که توسط همسايگانش پوشش داده نمي شود.
ولي اگر هر کدام از n نقطه بررسي شده، در ناحيه حسگري حداقل k نود همسايه قرار گيرند، اين نود يک نود افزونه تلقي مي گردد.
2-4-2-1- انتخاب شکل گريد به صورت مناسب
در حالت پايه ما شکل گريد را به صورت مربعي محاط بر دايره ناحيه حسگري نود درنظر گرفتيم(شکل 2-7). در اين حالت تعدادي از نقاط واقع در ناحيه گريدي خارج از ناحيه حسگري هستند(شکل 2-8) و تعداد نقاطي که مورد بررسي قرار مي گيرند بيش از ميزان نياز مي باشد. در ضمن در الگوريتم يک شرط اضافه بايد چک گردد که مشخص شود آيا نقطه مورد بررسي در ناحيه حسگري نود وجود دارد يا خير. جهت کاهش تعداد نقاط مورد بررسي وبرداشتن شرط اضافه، مي توانيم ناحيه گريدي را دقيقا منطبق بر ناحيه حسگري نود در نظر بگيريم. در اين حالت ناحيه گريدي به صورت دواير متحدالمرکز و تو در تو در نظر گرفته مي شود ونقاط گريدي بر روي محيط دواير قرار مي گيرند.

شکل‏2-8 : تعدادي از نقاط مربع گريدي افزونه بوده و درون ديسك حسگري قرار نمي گيرند
شکل گريد مورد بحث در 9-2نشان داده شده است.

شکل‏2-9 : انتخاب شكل گريد به صورت شعاعي و بر روي دواير متحدالمركز
2-4-2-2- تعيين اندازه گريد به صورت مناسب
انتخاب اندازه گريد(L) در کارايي اين الگوريتم تأثير بسزايي دارد اگر اندازه گريد خيلي کوچک در نظر گرفته شود تعداد نقاط گريدي زياد شده و محاسبات در نود افزايش مي يابد که باعث مي گردد انرژي نود سريعتر تخليه شود. از طرفي چون در اين روش به جاي تضمين پوشش در گريد، تضمين پوشش در نقاط گريدي صورت مي گيرد، اگر اندازه گريد بزرگ در نظر گرفته شود امکان دارد حفره هايي در ناحيه حسگري وجود داشته باشد که هيچ نقطه گريدي در آنها قرار نگيرد و بنابراين اين حفره هاي حسگري با کمک اين الگوريتم شناسايي نگردند. در بسياري از کاربردهاي شبکه هاي حسگر بي سيم هدف شناسايي اشيايي در محيط است. در اين گونه موارد حد بالاي اندازه گيري را مي توان بدين صورت مشخص کرد. که اندازه L بايد کوچکتر از اندازه اشيايي باشد که قرار است شناسايي گردند به طوري که اين اشياه در شکاف بين نقاط گريد قرار نگيرند. حتي در کاربردهايي که هدف شناسايي اشياء نيست هم موارد زيادي وجود دارد که وجود حفره هاي حسگري با ابعاد محدود ومشخص تأثير منفي در عملکرد شبکه حسگر نمي گذارد مثلا اگر در يک شبکه حسگر وظيفه حسگرها محاسبه ميزان دماي محيط باشد و اگر بدانيم که اختلاف دما بين دو نقطه با فاصله حداکثر d قابل چشم پوشي است مي توانيم در اين محيط اندازه L را حداکثر برابر با d در نظر بگيريم . ولي اگر لازم باشد که محيط به طور کامل و پيوسته تحت پوشش قرار گيرد بدين صورت عمل مي کنيم [51]:
هر نود حسگر يک ناحيه حسگري واقعي دارد که شعاع آن به اندازه rs مي باشد. ما براي هر حسگر ، يک ناحيه حسگري محافظه کار نيز در نظر مي گيريم که ديسکي است هم مرکز با ناحيه حسگري واقعي وشعاع آن کوچکتر از rs مي باشد. با استفاده از شکل 2-10, به سادگي مي توان متوجه شد که براي اينکه ناحيه هدف به طور کامل به وسيله ناحيه حسگري واقعي نود ها تحت پوشش قرار گيرد بايد اولا هر نقطه گريدي در درون ناحيه حسگري محافظه کار حداقل يک نود قرار گيرد و ثانيا تفاوت بين شعاع حسگري واقعي و شعاع حسگري محافظه کار بايد بزرگتر از باشد.
در اين صورت، مسئله پوشش کل ناحيه هدف با نواحي حسگري واقعي به پوشش نقاط گريدي توسط نواحي حسگري محافظه کار تبديل مي شود. اگر از اين روش استفاده کنيم بايد اندازه گريد(L) را کوچکتر از انتخاب کرد تا پوشش کامل تضمين گردد.

شکل‏2-10 : تعيين اندازه گريد به صورت مناسب
2-4-2-3- ارائه راه حل با استفاده از آتوماتاهاي يادگير سلولي
جهت حل مسئله پوشش شبکه، ما از آتوماتاهاي يادگيرسلولي نامنظم(ICLA) استفاده مي کنيم. بدين ترتيب که متناظر با شبکه حسگريک آتوماتاهاي يادگيرسلولي نامنظم در نظر مي گيريم که هر نود در شبکه معادل است با يک سلول در ICLA . و دو سلول a و b در ICLA در صورتي همسايه اند که فاصله نودهاي متناظر کمتر از برد ارتباطي باشد. آتوماتاي يادگير در هر سلول دو عمل a0 و a1 دارد که انتخاب a0 به معناي غير فعال شدن نود و انتخاب a1 به معناي فعال شدن آن مي باشد. در ابتدا هر دو عمل آتوماتا احتمال برابر دارند. يعني احتمال غير فعال يا فعال شدن نود برابر با 0.5 مي باشد در هر دور آتوماتاي هر نود بر اساس احتمال منتسب به هريک از اعمالش ، يکي را به طور تصادفي انتخاب مي کند. اين انتخاب نشان مي دهد که در دور جاري ، نود مزبور بايد فعال يا غير فعال باشد. و از آنجاييکه ما قصد داريم که در حد امکان انرژي در شبکه به صورت يکنواخت مصرف گردد ميزان انرژي باقيمانده نود ها را نيز مدنظر قرار مي دهيم و سعي مي کنيم که نودهاي با انرژي بيشتر فعال نگه داشته شوند. هر گاه آتوماتاي يادگيرنده عمل فعال يا غير فعال بودن را انتخاب کرد ، نود حسگر وضعيتش (چه فعال وچه غير فعال) را به اطلاع همسايگانش مي رساند. در عين حال ميزان انرژي باقيمانده اش را نيز به همسايگانش اطلاع مي دهد. پس از گذشت فاصله زماني کوتاهي ، هر نود از وضعيت همسايگانش و ميزان انرژي باقيمانده انها مطلع بوده وهمسايگان فعالش را مي شناسد. حال زمان آن رسيده که هر نود عمل خود را مورد ارزيابي قرار دهد وبر اساس آن آتوماتاي يادگير واقع در نود، پاداش دريافت کرده ويا جريمه شود. بدين منظور نود مورد نظر بايد الگوريتم تشخيص

پایان نامه
Previous Entries دانلود پایان نامه ارشد با موضوع انتقال اطلاعات، فعال نمودن Next Entries دانلود پایان نامه ارشد با موضوع انرژي، نودهاي، ميانگين