A survey on relay placement with runtime and approximation guarantees

We discuss aspects and variants of the fundamental problem of relay placement: given a set of immobile terminals in the Euclidean plane, place a number of relays with limited viewing range such that the result is a low-cost communication infrastructure between the terminals. We first consider the problem from a global point of view. The problem here is similar to forming discrete Steiner tree structures. Then we investigate local variants of the problem, assuming mobile relays that must decide where to move based only on information from their local environment. We give a local algorithm for the general problem, but we show that no local algorithm can achieve good approximation factors for the number of relays. The following two restricted variants each address different aspects of locality. First we provide each relay with knowledge of two fixed neighbors, such that the relays form a chain between two terminals. The goal here is to let the relays move to the line segment between the terminals as fast as possible. Then we focus on the aspect of neighbors that are not fixed, but which may change over time. In return, we relax the objective function from geometric structures to just forming a single point. The goal in all our local formation problems is to use relays that are as limited as possible with respect to memory, sensing capabilities and so on.We focus on algorithms for which we can prove performance guarantees such as upper bounds on the required runtime, maximum traveled distances of the relays and approximation factors for the solution.