5-2-3-1 الگوريتمهاي مبنی بر همسايه[1]
TECA الگوريتم كنترل انرژي و توپولوژي[2]:TECA گرهها را با استفاده از اطلاعات همسايه ای با فاصله یک گام از آن، كلاستربندي ميكند. TECA گرهها را به 5 وضعيت تقسيم ميكند: 1- اوليه[3] 2- خواب 3- غير فعال[4] 4- پل 5- سركلاستر
همه گرهها در وضعيت اوليه شروع ميشوند و يك تايمر روشن ميكنند. گرهها در حالت اولیه به انتقالات داده ای دیگرگره ها گوش ميدهند. براساس شنود اين انتقالها يك گره ميتواند يك جدول همسايگي سازد. يك گره كيفيت لینک هر گره در جدول همسايگياش را براساس قدرت سيگنال پيامهاي شنيده شده اندازهگيري ميكند. وقتي تايمر اوليه منقضي شد، ند به حالت غير فعال ميرود. گرهها در حالت غير فعال به شنود پيامها ادامه ميدهند و جدول همسايگي شان را نگهداري ميكنند. Beaconها براي كمك به نگهداري جداول همسايگي استفاده مي شوند.Beaconها پيامهايي هستند كه بصورت دورهاي فرستاده می شوند و شاملID گره، حالت فعلي، انرژي باقي مانده، مقدار timeout و اطلاعات همسايگي با فاصله یک گام می باشند.
هر گرهاي كه هنوز به يك كلاستر اختصاص داده نشده، برای سرخوشه شدن، كانديد ميشود.اين گرههاي كانديد، اعلان همگاني ميكنند كه يك سركلاستر كانديد هستند. گره با يك گام همسايگي با بيشترين انرژي باقيمانده سركلاستر ميشود. همه گرههاي ديگر که در همسایگی تک گامی سرخوشه قرار دارند، به آن كلاستر ميپيوندند. هر سركلاستر يك تایمر روشن ميكند و براي آن دوره سركلاستر باقي ميماند. وقتي اين تايمر منقضي شد، آن گره سعي ميكند تا يك كلاستر پيدا كند كه به آن بپيوندد بنابراين دوباره سركلاستر نمي شود و انرژي ذخيره ميكند. هرگره كه يك سركلاستر نيست گره غير فعال باقي ميماند.
براي حفظ اتصال شبكه TECA از گرههاي پل استفاده ميكند. گرههاي غير فعال يك تايمر را شروع ميكنند و به شنيدن به همسايگانشان ادامه ميدهند. اگر يك گره غير فعال يك پيام همگاني از حداقل 2 سركلاستر بشنود، کاندید پل می شود. انتخاب پل از همه گرههاي كانديد پل يك فرايند پيچيده است كه به هدف كمينه كردن بسته های گم شده بين كلاسترها و تعداد گرههاي پل انتخاب شده انجام می شود. اين فرايند براساس گراف های ساخته شده بين همسايگان 2 گامي هر گره است. هر گراف هزينه های متفاوتی برای هر لینکش دارد و برای هر گراف باید درخت پوشای کمینه، محاسبه شود. اگر گره غير فعال براي گره پل انتخاب نشود، وقتي تايمرش منقضي شود به حالت خواب ميرود و براي يك دوره مشخص ديگر، خواب باقی می ماند. در طول اين زمان، فقط سرهاي كلاستر و گرههاي پل فعال باقي ميمانند.
با استفاده از اطلاعات همسايگي تك گامي، سرهاي كلاستر مجاور حداكثر 3 گام فاصله دارند اما هرگز از نظر جغرافيايي نزديك يكديگر نيستند. نقش سركلاستر و گره پل مي چرخد و برای انتخاب سرخوشه شدن، انرژی باقیمانده ند، درنظر گرفته می شود. اين خصوصيات TECAكمك ميكند طول عمر شبكه زياد شود. يك مزيت TECA نسبت به بقيه الگوريتمهاي كلاستربندي انتخاب گرههاي پل براي حفظ اتصال شبكه است. به هر حال استفاده از گرههاي پل يك اشكال دارد كه نياز به گرههاي بيشتري براي فعال باقي ماندن است كه انرژي بيشتري مصرف ميكند وطول عمر شبكه را كوتاه ميكند.
گردآوری کارای انرژی در سیستم های اطلاعاتی حسگر[5]PEGASIS: PEGASIS براي بهتر كردن كارايی شکل كلاستر در leach به وجود آمده است. ايده كليدي pegasisکمتر مصرف کردن انرژی با داشتن ارتباط هر گره با فقط يك گره همسايه نزديك، می باشد.اين كار با تشکیل زنجیره ای از گره ها در شبکه انجام می شود. زنجير با محاسبات ايستگاه اصلي يا با استفاده از الگوريتم حريصانه تشكيل ميشود. بعد از اينكه زنجير درست شد، هر گره دادههاي خودش رابه گره ديگر زنجيرانتقال ميدهد. گره بعدي اطلاعات را با دادههاي خودش سرهم ميكند، یک پاکت داده می سازد و به گره بعدي زنجيره ميفرستد. رهبر آن مرحله زنجیر، دادههاي سرهم شده نهايي را به ايستگاه اصلي ميفرستد. وقتي این مرحله تمام شد، يك رهبر جديد انتخاب مي شود و مرحله جديد شروع ميشود.
براي كمك به توزيع بار، نقش رهبر بين همه گرهها ميچرخد. فقط گرههايي كه از ايستگاه اصلي دور هستند، نميتوانند به عنوان رهبر انتخاب شوند. اگر داده با فاصله دور انتخاب شود مصرف انرژی بالا می رود و این مخالف با اهداف کاهش انرژی الگوریتم های خوشه بندی می باشد. در این الگوریتم، با توجه به انتقال و دریافت داده توسط تنها یک گره و فاصله کوتاه بین گره ها، انرژی را می توان ذخیره نمود.
يك ایراد مهمpegasis اين است كه هنگام انتخاب رهبر در هر نوبت انرژي باقی مانده را در نظر نميگيرد. همچنين براي تشكيل بهترين زنجيره، لازم است دانش عمومي مثلاً تعداد گرهها و موقعيت هر گره را از شبكه داشته باشيم.
[1]Neighbor-Based Algorithms
[2]Topology and Energy Control Algorithm
[3]initial
[4]passive
[5]Power-Efficient Gathering in Sensor Information Systems