Wireless Coverage via Dynamic Programming

摘要

Coverage has been one of the most fundamental yet challenging issues in wireless networks and found many applications, such as routing and broadcasting. Given a set of weighted unit disks (coverage areas) and a set of nodes to be covered, we study the minimum weight coverage problem under two specific topologies. The first one assumes that the centers of the disks lie inside a strip while the nodes lie outside of this strip. The second topology assumes that the centers of the disks lie within a unit circle while the nodes lie outside of this circle. For each topology, we present a polynomial-time algorithm to find a disk subset of minimum total weight to cover all nodes. Both of our algorithms relies on dynamic programming.