a new learning automata-based algorithm to solve the target k-coverage problem in wireless sensor networks

Recently, a number of algorithms have been proposed to solve the target coverage problem in wireless sensor networks (wsns). conventionally, it is assumed that only a single sensor is sufficient for covering a target; though, in real situations, more than one sensor may be required for this purpose. this problem is known as k-coverage problem that its np-completeness has been already proved. to solve the problem, this paper proposes a learning-automata based algorithm equipped with a pruning rule. the aim of the proposed algorithm is to determine minimum number of sensors in such a way that each target can be monitored for at least k times. the proposed algorithm performance was evaluated through conducting a number of experiments. the experimental results were compared to those of a greedy-based algorithm. as shown by the final results, the learning-automata based algorithm was more successful than the greedy-based one regarding the construction of cover sets with minimum number of sensors.

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

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