Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Routing in Unit Disk Graphs
verfasst von : Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth
Erschienen in: LATIN 2016: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let \(S \subset \mathbb {R}^2\) be a set of n sites. The unit disk graph \({{\mathrm{UD}}}(S)\) on S has vertex set S and an edge between two distinct sites \(s,t \in S\) if and only if s and t have Euclidean distance \(|st| \le 1\).
A routing scheme R for \({{\mathrm{UD}}}(S)\) assigns to each site \(s \in S\) a label \(\ell (s)\) and a routing table \(\rho (s)\). For any two sites \(s, t \in S\), the scheme R must be able to route a packet from s to t in the following way: given a current site r (initially, \(r = s\)), a header h (initially empty), and the target label \(\ell (t)\), the scheme R may consult the current routing table \(\rho (r)\) to compute a new site \(r'\) and a new header \(h'\), where \(r'\) is a neighbor of r. The packet is then routed to \(r'\), and the process is repeated until the packet reaches t. The resulting sequence of sites is called the routing path. The stretch of R is the maximum ratio of the (Euclidean) length of the routing path of R and the shortest path in \({{\mathrm{UD}}}(S)\), over all pairs of sites in S.
For any given \(\varepsilon > 0\), we show how to construct a routing scheme for \({{\mathrm{UD}}}(S)\) with stretch \(1+\varepsilon \) using labels of \(O(\log n)\) bits and routing tables of \(O(\varepsilon ^{-5}\log ^2 n \log ^2 D)\) bits, where D is the (Euclidean) diameter of \({{\mathrm{UD}}}(S)\). The header size is \(O(\log n \log D)\) bits.