جایگذاری گره در شبکه حسگر بیسیم دارای زیرناحیه های هدف

الگوریتم جایگذاری گره در یک شبکه حسگر بیسیم برای تعیین تعداد و مکان گره های حسگر بکار می رود که برای پوشش یک ناحیهنیاز هستند. ما در این پژوهش، یک مساله جدید در جایگذاری حسگر به نام CTAC را تعریف کرده ایم که هدف آن پوشش فضای شبکه به کمک کمترین تعداد گره در حالتی است که زیرناحیه های هدفی با شکل های دلخواه و یا نامنظم در آن جای گرفته اند که به پوشش دوگانه نیاز دارند. نخست، یک الگوریتم به نام findBestCTAC طراحی کردیم که با جستجوی همه حالت های جایگذاری به بهترین پاسخ می رسد ولی پیچیدگی زمانی آن از مرتبه نمایی است. سپس الگوریتمی به نام solveCTAC را برای یافتن یک پاسخ تقریبی برای مساله CTAC طراحی کرده ایم که مساله اصلی را به چند زیرمساله می شکند و هر زیرمساله را جداگانه حل می کند. پیچیدگی زمانی solveCTAC از مرتبه چندجمله ای است. همچنین، یک نرمافزار برای اجرای این الگوریتم پیاده سازی کرده ایم که الگوریتم را اجرا کرده و نتیجه جایگذاری را به صورت گرافیکی نمایش می دهد. ارزیابی هایی که به کمک این نرم افزار انجام شده اند،نشان میدهند که الگوریتم solveCTAC از دید تعداد حسگرهای مورد نیاز همانند الگوریتم findBestCTAC رفتار می کند ولی به زمان اجرای بسیار کوچکتری در مقایسه با الگوریتم findBestCTAC نیاز دارد.

Keywords:

شبکه حسگر , جایگذاری گره , پوشش , بهینه سازی