Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas

Adil Erzin, Natalya Lagutkina, Nika Ioramishvili

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

In the problem of barrier monitoring using mobile sensors with circular coverage areas, it is required to move the sensors onto some line (barrier) so that each barrier point belongs to the coverage area of at least one sensor. One of the criteria for the effectiveness of coverage is the minimum of the total length of the paths traveled by sensors. If we give up the requirement to move the sensors onto the barrier, then the problem (which is NP-hard) will not be easier. But at the same time, the value of the objective function can be reduced significantly. In this paper, we propose a new pseudo-polynomial algorithm which in the case of equal disks builds an optimal solution in the metric and a -approximate solution in the Euclidean metric. This algorithm is an efficient implementation of the dynamic programming method in which at the stage of preliminary calculations for each sensor it is possible to find a finite number of analytical functions equal to the minimal length of the path traveled by the sensor depending on the positions of the circle and the barrier. The conducted numerical experiment showed that if we remove the requirement to move the sensors onto the barrier, then the value of the objective function may decrease several times.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
РедакторыNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
ИздательSpringer Gabler
Страницы342-354
Число страниц13
ISBN (печатное издание)9783030386283
DOI
СостояниеОпубликовано - 1 янв 2020
Событие13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Греция
Продолжительность: 27 мая 201931 мая 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11968 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция13th International Conference on Learning and Intelligent Optimization, LION 13
СтранаГреция
ГородChania
Период27.05.201931.05.2019

Fingerprint Подробные сведения о темах исследования «Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать