Abstract

We study the problem of positioning multiple sinks, or data collection stops for a mobile sink, in a sensor network field. Given a sensor network represented by a unit disc graph G = ( V, E ), we say a set of points U (sink node locations) is an h -hop covering set for G if every node in G is at most h hops away from some point in U . Placing sink nodes at the points of a covering set guarantees that every sensor node has a short path to some sink node. This can increase network lifetime, reduce the occurrence of errors, and reduce latency. We also study variations of the problem where the sink locations are restricted to be at points of a regular lattice (lattice-based covering set), or at network nodes (graph-based covering set). We give the first polynomial time approximation scheme ( PTAS ) for the h -hop covering set problem, the h -hop lattice-based covering set problem, and the h-hop graph-based covering set problem. We give a new PTAS for the lattice-based disc cover problem, based on a new approach deriving from recent results on dominating sets in unit disc graphs. We show that this gives a (3 + f)-approximation algorithm for the disc cover problem, and gives the first distributed algorithm for this problem. We give a (5 + f)-approximation algorithm for the h -hop covering set problem in unit disc graphs, that does not require a geometric representation of the graph. Finally, we give a (3+f)-approximation algorithm for the h -hop covering set problem for unit disc graphs that runs in time quadratic in the number of nodes in the graph, for any constant f and h . In addition to showing how well a lattice-based approach for a disc cover problem approximates the optimal solution, we prove a geometric theorem that gives an exact relationship between the side of a triangular lattice and the number of lattice discs that are necessary and sufficient to cover an arbitrary disc on the plane.