Compact and low delay routing labeling scheme for Unit Disk Graphs

作者：Yan Chenyu; Xiang Yang; Dragan Feodor F^*

来源：Computational Geometry-Theory and Applications, 2012, 45(7): 305-325.

DOI：10.1016/j.comgeo.2012.01.015

• Unit disk graphs
• Collective tree spanners
• Routing and distance labeling schemes
• Balanced separators
• Efficient geometric graph algorithms

In this paper, we propose a new compact and low delay routing labeling scheme for Unit Disk Graphs (UDGs) which often model wireless ad hoc networks. We show that one can assign each vertex of an n-vertex UDG G a compact O(log(2)n)-bit label such that, given the label of a source vertex and the label of a destination, it is possible to compute efficiently, based solely on these two labels, a neighbor of the source vertex that heads in the direction of the destination. We prove that this routing labeling scheme has a constant hop route-stretch (= hop delay), i.e., for each two vertices x and y of G, it produces a routing path with h(x, y) hops (edges) such that h(x, y) %26lt;= 3 . d(G) (x, y) + 12, where d(G) (x, y) is the hop distance between x and y in G. To the best of our knowledge, this is the first compact routing scheme for UDGs which not only guaranties delivery but has a low hop delay. Furthermore, our routing labeling scheme has a constant length route-stretch and a constant power route-stretch. %26lt;br%26gt;To obtain this result, we establish a novel balanced separator theorem for UDGs, which mimics the well-known Lipton and Tarjan%26apos;s planar balanced shortest paths separator theorem. We prove that, in any ti-vertex UDG G, one can find two hop-shortest paths P(s, x) and P(s, y) such that the removal of the 3-hop-neighborhood of these paths (i.e., N-G(3)[P(s, x) boolean OR P (s, y)]) from G leaves no connected component with more than 2/3n vertices. This new balanced shortest-paths-3-hop-neighborhood separator theorem allows us to build, for any n-vertex UDG G, a system T(G) of at most 2 log(3/2) n + 2 spanning trees of G such that, for any two vertices x and y of G. there exists a tree T in T(G) with d(T)(x, y) %26lt;= 3 . d(G)(x, y) + 12. That is, the distances in any UDG can be approximately represented by the distances in at most 2 log(3/2) n + 2 of its spanning trees.

• 出版日期2012-8