کلاستربندی در شبکه‌های حسگر بی‌سیم

Figure 1. Output of simulation of the single level clustering algorithm

هر سنسور در شبکه با احتمال p یک گرة سرگروه (Clusterhead) می‌شود و خودش را در محدودة فرکانسی‌اش تبلیغ می‌کند. به این گره‌های سرگروه، سرگروه‌های داوطلب می‌گویند. این تبلیغات برای گره‌هایی که در k پرش از گرة تبلیغ کننده قرار دارند، forward می‌شود. هر سنسوری که این تبلیغ بدستش برسد و خودش نیز سرگروه نباشد، به نزدیکترین کلاسترِ متعلق به سرگروه می‌پیوندد. هر سنسوری که سرگروه نبوده و عضو هیچ کلاستری هم نباشد، خودش یک سرگروه می‌شود. به این گره‌های سرگروه، گره‌های سرگروهِ اجباری گفته می‌شود. زیرا هر تبلیغ به اندازة k پرش به گره‌های دیگر ارسال می‌شود و ممکن است در محدوده زمانی t این تبلیغ به دست گره‌ای خاص نرسیده باشد. پس می‌توان نتیجه گرفت که این گره در k پرش گره‌های سرگروه داوطلب وجود ندارد از این رو خودش به صورت اجباری تبدیل به گرة سرگروه می‌شود [1].

[1]    S. Bandyopadhyay, E. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003