Paper Info
Title
A survey on relay placement with runtime and approximation guarantees
Abstract
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.
Year
DOI
Venue
2011
10.1016/j.cosrev.2010.09.005
Computer Science Review
Keywords
DocType
Volume
Relay placement,Mobile robots,Local algorithms,Robot formations
Journal
5
Issue
ISSN
Citations 
1
1574-0137
1
PageRank 
References 
Authors
0.36
0
4
Name
Order
Citations
PageRank
Bastian Degener113010.55
Sándor P. Fekete21931179.96
Barbara Kempkes31279.43
Friedhelm Meyer auf der Heide41744238.01