انجمن کامپیوتر ایران

در اين مقاله، یک الگوريتم با ويژگي‌های خود-پاياسازی و محدودسازی خطا برای ساخت مجموعه غالب مینیمال به منظور خوشه‌بندی در شبکه‌های حسگر بی‌سیم، پيشنهاد می‌شود. الگوریتم‌های مشابه يا به‌کلی از ويژگی محدودسازی خطا بی‌بهره‌اند و یا چون اساساً با دید کاربردی خاصی طراحی نشده‌اند، با محيط عملياتی شبکه‌های حسگر تناسب ندارند. الگوریتم پیشنهادی قابلیت تنظیم وابستگی گره‌ها به سرخوشه را دارد؛ از پيکربندی‌های تک‌خطايي با پيچيدگی زمانی و مکانی O(1) ترميم می‌شود و تحت سیاست زمانبندی توزيعی ناعادلانه کار می‌کند که بیشترین مشابهت با معماری شبکه‌های حسگر را دارد. ساخت مجموعه غالب مینیمال، چون عدم مجاورت گره‌های سرخوشه را الزامی نمی‌کند، تعداد تغییر حالت کمتری تا پیکربندی مجاز نیاز دارد و ساختار خوشه‌های حاصل از آن نیز بهینه‌تر است. کاهش تعداد پيام‌های بروزرسانی، ایجاد ساختار خوشه‌بندی کارآمدتر و پايدارسازی با حداقل تغيير در ساختار توپولوژيکی از ویژگی‌های اساسی الگوريتم می‌باشند. نتایج حاصل از شبیه‌سازی نشان خواهد داد که صرف نظر از تعداد و تراکم گره‌ها، روش پيشنهادی علاوه بر ترمیم سريع در مقابل خطاهاي مقياس کوچک، زمانِ رسيدن به پايداري با شروع از پيکربندي دل‌خواه اوليه را نيز نسبت به روش‌هاي قبلي بهبود می‌دهد.