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

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

الگوريتم در شکل 3-3، نمايش داده شده است. چون همسايه ها يکبار در ابتدا شناسايي مي گردند لازم نيست در هر تکرار الگوريتم همسايه ها را شناسايي کرد. در ضمن نودها به طور خودکار مجموعه همسايگانشان را با ارسال و دريافت پيامهايي شناسايي مي کنند.
هر نود که خودش را به عنوان سرخوشه انتخاب کرد يک پيام cluster_head_msg(Node_id, selection status, cost ) مي فرستد. که اگر مقدار CHprob کمتر از يک باشد، وضعيت نود tentative_CH (سر خوشه آزمايشي ) است و اگر CHprob برابر با يک باشد وضعيت آن final-CH (سرخوشه نهايي) است. اگر يک نود اجراي heed را به اتمام برساند در حالي که سرخوشه اي انتخاب نکرده باشد، خودش سر خوشه نهايي مي شود. در مراحل بعدي اگر سرخوشه اي بيايد که هزينه اش کمتر باشد، يک سر خوشه آزمايشي ممکن است تبديل به يک نود معمولي گردد. توجه کنيد که يک نود مي تواند متواليا خودش را به عنوان سر خوشه انتخاب نمايد اگر انرژي باقيمانده زيادي داشته باشد و هزينه اش کمتر باشد.
I. Initialize
1. Snbr ? {v: v lies within my cluster range}
2. Compute and broadcast cost to
3. CHprob ? max(, pmin)
4. is_final_CH ? FALSE

II. Repeat
1. If ((SCH ? {v: v is a cluster head}) ?)
2. my_ cluster_head ? least_cost(SCH)
3. If my_cluster_head = NodeID
4. If (CHprob = 1)
5. Cluster_head_msg(NodeID,final_CH,cost)
6. is final CH ? TRUE
7. Else
8. Cluster_head_msg(NodeID,tentative_CH,cost)
9. ElseIf (CHprob = 1)
10. Cluster_head_msg(NodeID,final_CH,cost)
11. is_final_CH ? TRUE
12. ElseIf Random(0,1) ? CHprob
13. Cluster_head_msg(NodeID,tentative_CH,cost)
14. CHprevious ? CHprob
15. CHprob ? min(CHprob × 2, 1)
Until CHprevious = 1

III. Finalize
1. If (is_final_ CH = FALSE)
2. If ((SCH ? {v: v is a final cluster head}) ?)
3. my_cluster_head ? least_cost(SCH)
4. join_cluster(cluster_head_ID, NodeID)
5. Else Cluster_head_msg(NodeID, final_CH, cost)
6. Else Cluster_head_msg(NodeID, final_CH, cost)
شکل ‏3-3: شبه كد الگوريتم HEED
3-3- خوشه بندي در شبکه هاي حسگر بي سيم با استفاده از آتوماتاهاي يادگير سلولي
همانطور که در بخشهاي قبلي مشاهده نموديد کارهاي زيادي در زمينه خوشه بندي در شبکه هاي حسگر بي سيم انجام گرفته است. کارهاي انجام گرفته را مي توان در دو گروه خوشه بندي متمرکز و توزيع شده دسته بندي کرد. در الگوريتم هاي خوشه بندي به روش متمرکز نياز به اطلاعات کلي در مورد شبکه است و در ضمن از نظر فضاي ذخيره سازي ،ايجاد ارتباط و ميزان بار محاسباتي سر بار قابل ملاحظه اي توليد مي نمايند. همچنين روشهاي متمرکز قابليت مقياس پذيري شبکه را تحت الشعاع قرار مي دهند و براي شبکه با نودهاي زياد ممکن است در عمل، الگوريتم جوابگو نباشد. بنابراين الگوريتمهاي خوشه بندي متمرکز در شبکه هاي حسگر با نودهاي فراوان قابل قبول نيستند.
جهت حل مسئله به صورت توزيع شده، انتخاب بهينه تعداد سرخوشه ها و نودهايي که بايد سرخوشه شوند، يک مسئله رام نشدني است و در ضمن به دليل تغيير مقدار انرژي نودها و نيز از بين رفتن تعدادي از نودها در طول حيات شبکه، توپولوژي شبکه و نيز نودهاي سرخوشه در طول حيات شبکه بايد تغيير کند. در اين مسئله نيز مثل بقيه مسائل از اين دست که رام نشدني هستند و راه حل مشخصي ندارند، در روشهاي هوشمند نتيجه بهتري حاصل مي گردد. روش هوشمند توزيع شده اي که جهت استفاده در اين مسئله مفيد است، آتوماتاهاي يادگير سلولي مي باشد با استفاده از اين روش کارهاي اندکي نيز صورت گرفته شده است.
در [71] با استفاده از آتوماتاهاي يادگير روشي براي خوشه بندي گره ها معرفي مي گردد که از انرژي باقيماندة گرهها و تعداد همسايگي براي انتخاب گرههاي سرخوشه استفاده مي كند. مشکل اصلي که در اکثر روشهاي قبلي مشاهده مي شود اين است که به کليه فاکتورهاي مورد نياز به طور همزمان توجه نمي گردد و مجبوريم به طور مطلق يک فاکتور را بر ديگري برتري دهيم. مثلا در روشهاي ارائه شده يکي از فاکتورها تعداد همسايه ها و يکي از فاکتورها ميزان انرژي باقيمانده است. اگر يک نود که در يکي از اين فاکتورها نسبت به همسايه اش برتري دارد و در ديگري پايينتر از همسايه اش است، بخواهد پاداش يا جريمه دريافت نمايد، بايد يکي از اين فاکتورها را به ديگري رجحان دهد. ما در ادامه سعي مي نماييم روشي ارائه دهيم که نقايص روشهاي بالا را رفع نموده و خوشه هاي متوازني توليد نموده و طول عمر شبکه را افزايش دهد.
3-3-1- روش خوشه بندي پيشنهادي
در اين بخش قصد داريم يك روش خوشه بندي در شبكه هاي حسگر بي سيم ارائه دهيم كه از تكنيك آتوماتاهاي يادگيرسلولي استفاده مي نمايد. بدين منظور ابتدا مفروضات مسئله بيان گرديده و سپس به تشريح روش و جزئيات الگوريتم مي پردازيم.
3-3-1-1- فرضيات و مدل مسئله
در اين روش ما فرض مي کنيم که تمام نودهاي شبکه حسگر يكسانند و هر نود شبکه دو حالت مي تواند داشته باشد:
1) نود سرخوشه CH 2) نود معمولي CN
نودي كه در وضعيت سرخوشه قرار مي گيرد وظيفه دريافت اطلاعات ديگر نودهاي موجود در شبكه و ارسال آنها به نود سينك را عهده دار مي شود. ميزان مصرف انرژي در حالت سرخوشه نسبت به حالت معمولي بالاترمي باشد. در حالت معمولي نود داده هاي توليد شده در شعاع حسگري خود را جمع آوري نموده و به نود سرخوشه ارسال مي نمايد. نود در اين حالت انرژي كمتري نسبت به حالت CH مصرف مي نمايد.
در روش پيشنهادي معيارهاي اصلي كه مد نظر قرار مي گيرند عبارتند از:
1) ميزان انرژي مصرفي:
مصرف انرژي در شبكه هاي حسگر بي سيم يكي از فاكتورهاي اصلي در اين شبكه ها است كه بر روي كارايي, قابليت اطمينان و طول عمر شبكه تأثير مي گذارد. توجه به مصرف انرژي در شبكه از دو جنبه مورد بررسي قرار مي گيرد:
الف) ميزان انرژي مصرفي در هر نود: بدين صورت که نودهاي با انرژي بالاتر احتمال سرخوشه شدنشان بالاتر مي رود.
ب) مصرف انرژي کلي در شبکه: که منجر به افزايش طول عمر شبکه مي گردد. بدين صورت اعمال مي گردد که خوشه ها بايد اندازه متعادلي داشته باشند و تعداد خوشه ها زياد نباشد.
2) متصل بودن شبکه:
متصل بودن شبکه نيز يكي از موضوعات بحراني در شبكه حسگر مي باشد. جهت متصل بودن شبکه حسگر بايد هر نود معمولي بايد يک نود سرخوشه همسايه داشته باشد که بتواند داده هايش را بدان ارسال نمايد.
3-3-1-2- تشريح روش پيشنهادي
الگوريتم پيشنهادي شامل دو فاز مي باشد فاز خوشه بندي و فاز حالت پايدار كه در فاز خوشه بندي با استفاده از تكنيك آتوماتاهاي يادگير سلولي، نودهاي حسگر يكي از حالتهاي سرخوشه يا معمولي را انتخاب مي كنند و خوشه ها تشكيل شده و هر نوع معمولي سرخوشه خود را شناسايي مي نمايد. سپس فاز حالت پايدار شروع مي گردد كه در فاز حالت پايدار, نودهاي معمولي براساس برنامه زمانبندي كه سرخوشه براي آنها تعيين نموده است داده هاي جمع آوري شده را به سر خوشه ارسال مي دارند و سر خوشه نيز اطلاعات را به نود سينك مي فرستد. در ضمن در فاز حالت پايدار، هر گاه ميزان انرژي نود سر خوشه از حد مشخصي پايين تر بيايد نود سر خوشه يك نود ديگر از خوشه با انرژي بيشتر را به عنوان سرخوشه انتخاب مي كند. تشريح فازهاي مختلف الگوريتم در ادامه آمده است:
* فاز خوشه بندي:‌
همانگونه كه عنوان گرديد در اين فاز خوشه ها بايد شكل گيرند و نودهاي سرخوشه مشخص شوند. تعيين نودهاي سرخوشه در سه مرحله انجام مي گيرد. بنابراين اين فاز خود شامل سه مرحله مي باشد.
در هر مرحله تعدادي از سرخوشه ها تعيين مى گردند در ادامه اين سه مرحله را شرح مي دهيم:
مرحله1
يكي از مهمترين پارمترهاي خوشه بندي تعداد نودهاي سرخوشه مي باشد و قصد داريم كه تعداد نودهاي سرخوشه تا حد امكان كم باشند. اگر نودهايى كه داراي تعداد زيادي همسايه هستند به عنوان سرخوشه انتخاب گردند در كل تعداد سرخوشه ها به ميزان زيادي كاهش خواهد ىافت. بنابراين در مرحله اول خوشه بندى هر نود در پيامي تعداد هسايگا نش را اطلاع نودهاى مجاور مي رساند. سپس هر نودي كه نسبت به تمام نودهاي مجاورش بيشترين تعداد همسايه را دارا باشد خودش را به عنوان سرخوشه انتخاب كرده و به اطلاع هسايگانش نيز مي رساند. نودهايي كه در اين مرحله به عنوان سرخوشه انتخاب مي گردند وارد مراحل يادگيري بعدي نمي شوند و وضعيت انها پايدار مي گردد و در اين مرحله به عنوان سرخوشه انتخاب مي گردند. در ضمن از انجا كه نودهاي همسايه اين نودها حداقل يك نود سرخوشه مجاور دارند لزومي ندارد كه وارد مرحله دوم شوند و در همين مرحله خود را به عنوان نود معمولي انتخاب مي نمايند، و وضعيتشان پايدار مي گردد. معمولا در اين مرحله نودهاي اندکي حائز شرط سرخوشه شدن مي باشند و بنابراين تعداد قابل توجهي از نودها در اين مرحله نه سرخوشه شده اند و نه در همسايگي نودهاي سرخوشه قرار دارند، که وضعيت آنها در اين مرحله ناپايدار است. نودهايي كه در اين مرحله وضعيتشان پايدار نشده است وارد مرحله بعد مي گردند. تا با استفاده از اتوماتاهاي يادگير وضعيتشان تعيين گردد.
مرحله2
در اين مرحله نودهايي كه در مرحله قبل وضعيتشان مشخص نشده است با استفاده از تكنيك آتوماتاهاي يادگيرسلولي نامنظم(ICLA) وضعيتشان را تعيين مي نمايند. جهت استفاده از اين تكنيك متناظر با شبکه حسگريک آتوماتاهاي يادگيرسلولي نامنظم در نظر مي گيريم که هر نودي در شبکه که در مرحله قبل به وضعيت پايدار نرسيده است، معادل است با يک سلول در ICLA . دو سلول در ICLA در صورتي همسايه اند که فاصله نودهاي متناظر کمتر از برد ارتباطي باشد. از آنجا كه هر نود مي تواند يكي از دو حالت سر خوشه و معمولي را دارا باشد، آتوماتاي متناظر مي تواند يكي از دو الفباي CN, CH را براساس بردار احتمالاتش انتخاب نمايد كه انتخاب CH معادل با سر خوشه شدن نود و انتخاب CN معادل با معمولي در نظر گرفته شدن نود مي باشد. در ابتدا احتمال انتخاب هر يك از اين دو عمل برابر با 0.5 مي باشد. در هر دور آتوماتاي هر نود بر اساس احتمال منتسب به هريک از اعمالش ، يکي را به طور تصادفي انتخاب مي کند.
با هر انتخاب ميزان احتمال سر خوشه شدن نود براساس پارامترهاي مختلف كاهش يا افزايش مي يابد. پارامترهايي كه جهت خوشه بندي در نظر گرفته مي شوند، عبارتنداز:
1) ميزان انرژي نود
نود سر خوشه وظيفه جمع آوري اطلاعات از نودهاي خوشه و ارسال آنها به نود سينك را بر عهده دارد. بنابراين در نود سر خوشه انرژي بيشتري مصرف مي گردد. و سعي ما اين است كه نودهايي به عنوان سرخوشه انتخاب گردند كه انرژي بالاتري دارند. بدين منظور از معيار ميزان اختلاف انرژي نود با انرژي ميانگين همسايگانش استفاده مي گردد و جهت نرمال سازي آن را بر انرژي ماكزيمم گره ها تقسيم مي كنيم.
2) تعداد همسايه هاي نود
از آنجا كه ميزان مصرف انرژي در نودهاي سرخوشه زياد مي باشد. در حد امكان بايد نودهاي كمتري را به عنوان سر خوشه انتخاب كرد و بدين منظور بايد نودهايي به عنوان سر خوشه انتخاب گردند كه بيشترين تعداد همسايه را دارا باشند. لذا در صورت انتخاب شدن يك نود به عنوان سر خوشه اگر تعداد همسايگانش بيش از ميانگين تعداد همسايگان نودهاي همسايه اش باشد پاداش دريافت كرده و در غير اين صورت جريمه مي گردد.
3) تعداد نودهاي سرخوشه همسايه
يكي از معيارهاي مهم درخوشه بندي متصل بودن مي باشد بدين معنا كه هر نود بتواند

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