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

Standard

Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas. / Erzin, Adil; Lagutkina, Natalya; Ioramishvili, Nika.

Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. ed. / Nikolaos F. Matsatsinis; Yannis Marinakis; Panos Pardalos. Springer Gabler, 2020. p. 342-354 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Erzin, A, Lagutkina, N & Ioramishvili, N 2020, Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas. in NF Matsatsinis, Y Marinakis & P Pardalos (eds), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11968 LNCS, Springer Gabler, pp. 342-354, 13th International Conference on Learning and Intelligent Optimization, LION 13, Chania, Greece, 27.05.2019. https://doi.org/10.1007/978-3-030-38629-0_28

APA

Erzin, A., Lagutkina, N., & Ioramishvili, N. (2020). Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas. In N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Eds.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (pp. 342-354). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_28

Vancouver

Erzin A, Lagutkina N, Ioramishvili N. Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas. In Matsatsinis NF, Marinakis Y, Pardalos P, editors, Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Springer Gabler. 2020. p. 342-354. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38629-0_28

Author

Erzin, Adil ; Lagutkina, Natalya ; Ioramishvili, Nika. / Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas. Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. editor / Nikolaos F. Matsatsinis ; Yannis Marinakis ; Panos Pardalos. Springer Gabler, 2020. pp. 342-354 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{4d0c9ceeb2464e6994c550b6635d107a,

title = "Barrier Covering in 2D Using Mobile Sensors with Circular Coverage Areas",

abstract = "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.",

keywords = "Barrier monitoring, Covering, Mobile sensors",

author = "Adil Erzin and Natalya Lagutkina and Nika Ioramishvili",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-38629-0_28",

language = "English",

isbn = "9783030386283",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Gabler",

pages = "342--354",

editor = "Matsatsinis, {Nikolaos F.} and Yannis Marinakis and Panos Pardalos",

booktitle = "Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers",

address = "Germany",

}

RIS

TY - GEN

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

AU - Erzin, Adil

AU - Lagutkina, Natalya

AU - Ioramishvili, Nika

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Barrier monitoring

KW - Covering

KW - Mobile sensors

UR - http://www.scopus.com/inward/record.url?scp=85078440825&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38629-0_28

DO - 10.1007/978-3-030-38629-0_28

M3 - Conference contribution

AN - SCOPUS:85078440825

SN - 9783030386283

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 342

EP - 354

BT - Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers

A2 - Matsatsinis, Nikolaos F.

A2 - Marinakis, Yannis

A2 - Pardalos, Panos

PB - Springer Gabler

T2 - 13th International Conference on Learning and Intelligent Optimization, LION 13

Y2 - 27 May 2019 through 31 May 2019

ER -

ID: 23905640