论文标题
在没有动态标头的单位磁盘图中路由
Routing in Unit Disk Graphs without Dynamic Headers
论文作者
论文摘要
令$ v \ subset \ mathbb {r}^2 $是飞机上的$ n $站点。 $ v $的单位磁盘图$ dg（v）$ of $ v $是带有顶点套装$ v $的图形，其中两个站点$ v $和$ w $相邻，并且仅当其欧几里得距离最多是$ 1 $。我们为$ DG（v）$开发了一个紧凑的路由方案。路由方案通过将标签$ l（v）$分配给$ v $中的每个站点$ v $，预处理$ dg（v）$。之后，对于任何两个站点$ s $和$ t $，该计划必须能够将数据包从$ s $到$ t $进行路由如下：鉴于当前顶点$ r $（最初，$ r = s $）的标签，以及目标顶点$ t $的标签，该方案确定了邻居$ r $ r $的邻居$ r $。然后，将数据包转发至$ r'$，并且该过程一直持续到数据包达到所需的目标$ t $。源$ s $和目标$ t $之间的最终路径称为$ s $和$ t $的路由路径。路由方案的拉伸是路由路径的总欧几里得长度的最大比率，以及$ dg（v）$的最短路径的最大比率，在$ s之间，$ 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$).过去，已经提出了几种单位磁盘图的路由方案。我们的方案是第一个实现多同源标签尺寸和任意延伸的方案，而无需在数据包中存储任何其他信息。
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.
