Compact and low delay routing labeling scheme for Unit Disk Graphs

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(log2n)-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)h(x,y) hops (edges) such that h(x,y)⩽3⋅dG(x,y)+12h(x,y)⩽3⋅dG(x,y)+12, where dG(x,y)dG(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.To obtain this result, we establish a novel balanced separator theorem for UDGs, which mimics the well-known Lipton and Tarjanʼs planar balanced shortest paths separator theorem. We prove that, in any n-vertex UDG G  , one can find two hop-shortest paths P(s,x)P(s,x) and P(s,y)P(s,y) such that the removal of the 3-hop-neighborhood of these paths (i.e., NG3[P(s,x)∪P(s,y)]) from G   leaves no connected component with more than 2/3n2/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)T(G) of at most 2log32n+2 spanning trees of G such that, for any two vertices x and y of G, there exists a tree T   in T(G)T(G) with dT(x,y)⩽3⋅dG(x,y)+12dT(x,y)⩽3⋅dG(x,y)+12. That is, the distances in any UDG can be approximately represented by the distances in at most 2log32n+2 of its spanning trees.