Coverage of Continuous Regions in Euclidean Space Using Homogeneous Resources with Application to the Allocation of the Phased Array Radar Systems

摘要

Air surveillance of United States territory is an essential Department of Defense function. In the event of an incoming aerial attack on North America, the DoD, Department of Homeland Security, and Federal Aviation Administration surveillance capabilities are critical to discovering and tracking the threat so that it can be eliminated. Many of the currently used surveillance radar will reach the end of their design life within ten to twenty years. By replacing the current radar network with a single integrated network of Multifunction Phased Array Radar (MPAR) units, surveillance capabilities can be enhanced and life cycle cost can be reduced. The problem of determining the location of required MPAR units to provide sufficient air surveillance of a given area is a large problem that could require a prohibitively long time to solve. By representing the area of surveillance as a polygon and the MPAR units as guards with a defined circle of detection, this problem as well as similar surveillance or coverage problems can be expressed with easily adjustable parameters. The problem of covering the interior and exterior of a polygon region with a minimal number of guards with homogeneous capabilities is not well researched. There are no methods for determining the minimal number of guards required to cover the interior and exterior of a polygon at a desired coverage level less than 100 percent. This paper describes an iterative method for determining a small number and location of guards required to cover a convex polygon both fully and at a specified percentage coverage less than 100 percent. Results are presented to show that the developed methodology produces a smaller number of required MPAR units using less time than a comparable method presented in the literature. A goodness measure of the method is presented with respect to a lower bound for over 1000 test ca.