5-2-1- الگوريتم كلاستربندي همگن[1]
يك WSN همگن شامل گرههاي يكسان است. الگوريتمهاي كلاستر از روشهاي متنوعي برای یافتن گره مناسب برای سرخوشه بودن و واگذار کردن گرههای عضو كلاسترهای بهينه، استفاده ميكند.
اين الگوريتم ها سپس بر اساس چگونگي تعيين سرخوشه ها و تشكيل كلاسترها دستهبندي می شوند. الگوريتم كلاستربندي مبنی بر سيگنال، ایجاد كلاسترها و تعیین سرخوشه ها را براساس قدرت سيگنال انجام می دهند. الگوريتمهاي كلاستربندي مبنی بر فاصله، تصميم گیری هایشان، براساس فاصلهمی باشد. الگوريتمهاي كلاستربندي براساس همسايگي از ليست همسايگي هر گره براي تصميمات استفاده ميكند.
1-5-2-1- الگوريتمهاي مبنی بر سيگنال[1]
LEACH: سلسله مراتب كلاستربندي سازگار كم- انرژي[1]:يكي از معروفترين این الگوریتم ها می باشد.LEACH يك WSN را چنان مديريت ميكند كه گره ها در يك زمان مشابه به صورت گردشي، توسط چرخش سرخوشه ها ميميرند و انتخاب سرخوشه ها بر اساس انرژی باقیمانده می باشد. اين طول عمر شبكه را زياد ميكند و وقتي شبكه ميميرد انرژي اندكي باقي ميماند.
عمل LEACH به چندین مرحله[2]، تقسيم ميشود. هر مرحلهاز فاز برپایی[3],فاز حالت پایدار، تشكيل شده است. فاز برپایی وقتي است كه گرهها خود را در خوشه ها سازمان دهی ميكند. يك گره تصميم ميگيرد در هر مرحله، مستقل از ندهای دیگر، سرخوشه باشد. گره يك عدد رندوم انتخاب ميكند اگر آن عدد كوچكتر از مقدار آستانه باشد آن گره سركلاستر ميشود. مقدار آستانه براساس درصد پيشنهادي سرخوشه ها براي آن مرحله، تعداد دفعاتي كه گره سركلاستر شده است، و مقادير انرژي باقي مانده در گره می باشد. سرخوشه يك پيغام آگاهی را پخش همگاني ميكند تا نشان دهد كه يك سركلاستر است. يك گره غير سركلاستر به كلاستري ميپيوندد كه قويترين پيغام سيگنال (broadcast) را از آن دريافت كرده است. هر گره يك پيغام به سركلاستر جديدش ميفرستد براي آگاه كردن اينكه به كلاستر پيوسته است. بعد از اينكه كلاسترها تشكيل شدند، سرهاي كلاستر يك زمانبندي انتقال براي گرههاي حاضر خودش براساس TDMA ميسازد. اين به گرههاي عضو اجازه ميدهد تا در زمان هایی غیر از زمان ارسالشان، رادیوی خود را خاموش نمایند تا انرژي بيشتري ذخيره نمایند. ویژگی خوب دیگری که این الگوریتم دارد، این است که سرخوشه ها، داده ها را از اعضای خود گرفته، بسته بندی می کنند و سپس آن را ارسال می کنند. در نتیجه داده کمتری را انتقال می دهند. بعد از يك زمان مشخص، اين مرحله تمام ميشود و مرحله بعدي شروع مي شود كه اجازه ميدهد نقش سركلاستري بين گرهها بچرخد.
LEACH چند اشکال دارد. براي مثال سربار شکل دهی خوشه بزرگ، زیاد می باشد. همه سرخوشه هايايد پيغامهاي آگاه كننده همگاني را به همه گرههايي كه در ارتباط هستند بفرستند.ایراد ديگر آن،این است كه همه سرخوشه ها بايد داده را به ايستگاه اصلي منتقل كند، و در صورتی که فاصله زیادی از آن داشته باشند، انرژي بيشتري مصرف می کنند.
ABEE الگوريتم کلاستر موثر انرژي براساس دسترسي[4]:ABEE يك الگوريتم درخواست- پاسخ[5] است كه از سيستم اول ورود، اول سرويس[6] براي تشكيل كلاستر استفاده ميكند. وقتي يك گره مستقر شد، موقعيت فعلياش را (معمولاً توسط GPS) تعيين ميكند و در حالت بيكار[7] شروع ميكند. گره يك پيغام درخواست را پخش همگاني ميكند و تايمر را شروع ميكند. اگر گره يك جواب از سركلاستر دريافت كند با ارسال يك پيغام به سركلاستر، به آن كلاستر ميپيوندد. اين گره عضو جديد هر جواب ديگر را كه از سرخوشه های دیگر دريافت می كند را ناديده ميگيرد. اگر گرهاي هيچ جوابي از سركلاستر دريافت نكرد، يك پيغام همگاني مي فرستد كه سركلاستر است.
هر گره عضو بصورت دورهاي يك پيغام به سركلاسترش به منظور آگاه كردن سركلاستر از موقعيت فعلياش ميفرستد. گرههاي عضو همچنين اطلاعات سركلاسترشان را بر اساس پخش همگانی پیغام های دوره ای توسط آن ها را نگهداري ميكند.اين اطلاعات برای محاسبه فاصله هر گره تا سرخوشه اش می باشد. از آنجاييكه همه سرهاي كلاستر بصورت دورهاي پيغامهاي همگاني درباره موقعيت جاري خودشان ميفرستند، گرههاي عضو همچنين پيغامهاي همگاني سرهاي كلاستري ديگری را که در محدوده رادیویی آن ها می باشد را ميشنوند.اگر گره، پیغامی را از سرخوشه ای دریافت کند كه از سركلاستر فعلي خودش نزديكتر باشد، يك پيغام به سر كلاستر فعلي خود برای ترک کلاستر فعلی اش ميفرستد. سپس يك پيغام به سركلاستر نزديكتر ميفرستد تا به آن كلاستر بپیوندد. اين به گرههاي عضو اجازه ميدهد كه فاصله بين سركلاسترهايشان را كمينه كنند و انرژي را با انتقال داده به گره نزديكتر ذخيره كنند.
يك راه ديگر ذخيره كردن انرژي كمينه كردن تعداد كلاسترها است. اگر يك كلاستر يك پيغام از سركلاستر ديگر دريافت كند و فاصله بين دو سر كلاستر كمتر از مقدار آستانه باشد بعد 2 تا كلاستر با هم ادغام ميشوند و تعداد كلاسترها كم ميشود.
ABEE سعي دارد تا انرژي موجود در شبكه را موازنه كند به اين صورت كه نقش سركلاستر بصورت دورهاي بين گرهها بچرخد. سركلاستر جديد با در نظر گرفتن کل کلاستر به عنوان یک entity، و نسبت مساوی هر ند برای ایجاد آن، انتخاب ميشود.
اين عمل با جمعآوري همه اطلاعات مکانی توسط سركلاستر از گرههاي عضو با ارسال دوره ای اطلاعات مکانی به سرخوشه هاانجام مي شود. سپس سركلاستر از اطلاعات مکانی براي انتخاب گره اي كه به مركز انبوهي كلاستر، نزدیک تر استبرای سرخوشه شدن بعدی استفاده ميكند.
مزيت ديگر ABEE اين است كه سركلاستر دادههاي گرههاي عضو را قبل از ارسال آن به ايستگاه اصلي تركيب ميكند. دو عيب مهم و اصلي دارد. اول اینکه ABEE نياز دارد كه همه گرهها اطلاعات مکانی خود را بدانند و معمولاً نياز است هر گره دستگاه GPS داشته باشد. دوم اینکهبرای انتخاب سركلاسترها، انرژي باقيمانده گره هامورد توجه نمی باشد. به اين معناست كه گره مشابه ممكن است هميشه به عنوان سركلاستر انتخاب شود يعني انرژی اين گره، زودتر از بقیه ندهای ناحیه اش، تمام می شود و باعث کم شدن طول عمر شبکه می شود.
/224224
[1]Low-Energy Adaptive Clustering Hierarchy
[2]round
[3]setup
[4]Access-Based Energy Efficient Cluster Algorithm
[5]request-response
[6]first-come-first-serve
[7]idle state
[8]Distance-Based Algorithms
[1]Signal-Based Algorithms
[1]Homogeneous Clustering Algorithms