طرح خوشه بندی شبکه های حسگر بی سیم بر اساس مجموعه ی غالب مینیمم و الگوریتم ژنتیک

مساله ی k-مرکز پایه یک مساله از سری مسائل مکان قرارگیری امکانات اساسی است. n راس و تعدادی فاصله داده شده، و بر اساس آنها می خواهیم k امکانات را طوری در رئوس مختلف قرار دهیم که حداکثر فاصله ی یک راس تا امکانات مربوطه اش را حداقل کنیم. این مساله به عنوان یک مساله ی NPسخت شناخته می شود؛ از طرفی دسته بندی گره های حسگر در یک خوشه، مکانیسم مهمی در شبکه های بی سیم چند جهشی برای بدست آوردن مقیاس پذیری، کاهش مصرف انرژی و رسیدن به بهترین کارایی شبکه است. در این مقاله یک روش جدید حل مساله ی k-مرکز، بر اساس مجموعه ی غالب مینیمم و الگوریتم ژنتیک برای شبکه های بی سیم مطرح می کنیم. طی یک ارزیابی از روش پیشنهادی، افزایش در تعداد مراکز مقایسه شده را نسبت به روش مشهور اولین-دورترین گذر و روش های فقط مبتنی بر مجموعه ی غالب نشان می دهیم. نه تنها مجموع فاصله های مراکز تا گره ناظر (سینک) کمتر از دو الگوریتم دیگر است، بلکه روش مطرح شده، تاخیر داده را تقلیل می دهد و طول عمر مراکز را نیز افزایش می دهد.

Keywords:

شبکه های حسگر بی سیم , مساله ی k-مرکز , مجموعه ی غالب مینیمم , الگوریتم ژنتیک