FPTAS for barrier covering problem with equal touching circles in 2D
- PDF / 335,232 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 139 Views
FPTAS for barrier covering problem with equal touching circles in 2D Adil Erzin1
· Natalya Lagutkina2
Received: 9 August 2019 / Accepted: 3 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we consider a problem of optimal covering a barrier in the form of a line segment with equal circles distributed in a plane by moving their centers onto the segment or the line containing a segment. We require the neighboring circles in the cover to touch each other. The objective is to minimize the total traveled by circles Euclidian distance. The complexity status of the problem is not known. We propose an O( t A Pε2(n) )–time FPTAS for the problem, where n is the number of circles and t A P (n) is the time complexity of solving an assignment problem which is at most O(n 3 ). Keywords Barrier coverage · Mobile sensors · FPTAS
1 Introduction Wireless sensor network (WSN) consists of autonomous sensors, the operation time of which depends on the capacity of the batteries. The responsibility of the WSN is to collect and transfer data. The time during which the network performs these functions is called a WSN’s lifetime. The energy-efficient functioning of the WSN allows extending the lifetime. One of the critical applications of the WSN is the monitoring of extended objects (borders, roads, pipelines, perimeters of buildings, and others), which are often called the barriers. Monitoring can be carried out using both stationary [7,8,13,19–21] and mobile sensors [2–6,9–11,13,16,17]. The problem of energy efficient covering a line segment with stationary sensors with adjustable circular sensing areas initially located on a segment is considered in [13,20]. In [13], it is proved that such problem is NP-hard.
B
Adil Erzin [email protected] Natalya Lagutkina [email protected]
1
Sobolev Institute of Mathematics, Novosibirsk, Russia
2
Novosibirsk State University, Novosibirsk, Russia
123
A. Erzin, N. Lagutkina
The author of Zhang [20] considered the problem of minimizing the energy consumption for monitoring the barrier by determining the radii of the circles involved in the cover. He considered two settings: when the sensors are on the barrier and when the sensors are in the vicinity of the barrier. He proved that the problem is NP-hard, and proposed an O(n 3 /ε2 )–time FPTAS, where n is the number of sensors, and ε ∈ (0, 1) is the accuracy. The initial arrangement of the sensors in the plane can be arbitrary. If the sensor is mobile, then the energy consumption associated with movement is proportional to the distance traveled by it. Then the problem, which is usually referred to as MinSum, is to move the sensors with a circular sensing area in such a way that each barrier point is in the coverage area of at least one sensor, and the total distance traveled by sensors is minimal [9,11]. In the literature, two main classes of barrier monitoring problems with mobile devices considered. The first class is a one-dimensional (1D) problem, when the sensors are initially on the
Data Loading...
