Efficient approximation algorithms for offline and online unit disk multiple coverage. (December 2022)

• Record Type: Journal Article
• Authors: Gao, Xuening; Guo, Longkun; Liao, Kewen
• Is Part Of: Computers & electrical engineering. Volume 104:Part B(2022)
• Publication Date: 2022-12
• Subjects: Multiple coverage -- Disk coverage -- Approximation algorithm -- Online algorithm -- Linear runtime; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.108444
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: Multiple coverage with unit disks is a problem widely seen in monitoring applications of wireless sensor networks. In this problem, let T = t 1, t 2, …, t n be a set of targets to be covered (or monitored) which are distributed on the plane. Each target t i ∈ T is required to be covered by f ( t i ) disks for the purpose of energy efficiency or fault tolerance. The objective is to decide where on the plane to place the disks such that all the targets can be covered with a minimum number of disks. The problem does not admit any polynomial time exact solution as its special case of single coverage with unit disks is already N P -hard. In the paper, we present both offline and online approximation results for the problem where in the online setting disks must be placed upon each arrival of targets. We first give an offline 5-approximation algorithm with linear time and space complexity via exploiting efficient data structures. The algorithm can be easily adapted as an online 5-competitive algorithm. Then, we propose an improved offline algorithm attaining 4-approximation. Finally, we devise an efficient online algorithm with a constant average update time and a competitive ratio of 6. Numerical experiments are also carried out to empirically test and compare our proposed approximation algorithms. Graphical abstract: Highlights: Propose a 5-approximation algorithm for offline UDMC with linear time and space complexity. Improve the approximation ratio to 4 with quadratic running time for offline UDMC. Design a 6-competitive algorithm for online UDMC with a constant average update time.