Covering a line segment with variable radius discs |
| |
Authors: | Alessandro Agnetis Enrico Grande Pitu B Mirchandani Andrea Pacifici |
| |
Affiliation: | 1. Università di Siena, Dipartimento di Ingegneria dell’Informazione, via Roma 56, 53100 Siena, Italy;2. ATLAS Center, The University of Arizona, Tucson, AZ 85721, USA;3. Università di Roma “Tor Vergata”, Dipartimento di Ingegneria dell’Impresa, via del Politecnico 1, 00133 Roma, Italy |
| |
Abstract: | The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the disc covering problem on a line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing. |
| |
Keywords: | Sensor location Network covering problems Mixed integer nonlinear programming |
本文献已被 ScienceDirect 等数据库收录! |
|