Paper detail

Routing in Unit Disk Graphs without Dynamic Headers

Let $V\subset\mathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact routing scheme for $DG(V)$. The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$. After that, for any two sites $s$ and $t$, the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$) and the label of the target vertex $t$, the scheme determines a neighbor $r'$ of $r$. Then, the packet is forwarded to $r'$, and the process continues until the packet reaches its desired target $t$. The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$, between any two sites $s, t \in V$. We show that for any given $\varepsilon>0$, we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+\varepsilon$ and label size $O(\log D\log^3n/\log\log n)$ (the constant in the $O$-Notation depends on $\varepsilon$). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.