حل مسئله خوشه بندی حسگرها با استفاده از یک الگوریتم جستجوی گرانشی گسسته

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

Keywords:

مسئله مجموعه پوشش های جدا از هم , الگوریتم جستجوی گرانشی گسسته , الگوریتمهای فرا ابتکاری , مسائل بهینهسازی گسسته