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

در شبکه¬هاي حسگر بي¬سيم، پوشش و کیفیت تشخیص یکی از جنبه¬های کیفیت سرویس می¬باشد و مسئله آرایش مناسب گره¬ها از آن جهت که سطح بهتری از پوشش را فراهم می¬سازد، برای ما حائز اهمیت می¬باشد.با توجه به اینکه تشخیص¬ گره-های حسگر آمیخته با خطا می¬باشد، از مدل تشخیص احتمالی برای آرایش گره¬های حسگر، استفاده می¬نماییم که واقعی¬تر است. در این مسئله محیط به شکل گرید می¬باشد و احتمال تشخیص برای تک¬تک نقاط گرید باید بالاتر از حد آستانه مورد انتظار باشد. همچنين فرض مي¬كنيم كه سطح پوشش مورد نیاز در نقاط مختلف، متفاوت می¬باشد. راه¬حل پيشنهادي به صورت يك مسئله بهينه¬سازي چند هدفه ارائه شده است كه مي¬كوشد تا در نقاط مختلف به سطح پوشش مورد انتظار دست يابيم و در عين حال تعداد گره¬هاي حسگر به كار رفته در محيط را كاهش دهيم. مسئله آرايش گره¬هاي حسگر يك مسئله NP-hardمي¬باشد. اندازه فضاي راه¬حل محدود و در عين حال بسيار گسترده (2^(n^2 )) مي¬باشد.مي¬توان از طريق روش¬هايي مانند برنامه¬ريزي خطي به جواب بهينه دست يافت، ولي كاربرد اين روش¬ها در چنين فضاي گسترده¬اي، عملا غير ممكن مي¬باشد. براي غلبه بر پيچيدگي زماني از الگوريتم رقابت استعماري گسسته دودويي به منظور آرايش گره¬هاي حسگر در محيط حسي استفاده مي¬نماييم. شبیه¬سازی¬ها نشان می¬دهد که الگوریتم پیشنهادی در مقایسه با الگوریتم¬های ارائه شده در کارهای مرتبط از کارایی بهتری برخوردار بوده و با تعداد گره¬های حسگر کمتری در زمانی مناسب به سطح پوشش مورد نظر دست می¬یابد.