论文标题
在线广播范围分配问题
The Online Broadcast Range-Assignment Problem
论文作者
论文摘要
令$ p = \ {p_0，\ ldots，p_ {n-1} \} $为$ \ mathbb {r}^d $中的一组点，在无线网络中建模设备。范围分配将范围$ r（p_i）$分配给每个点$ p_i \ in p $，从而诱导了有向的通信图$ g_r $，其中有一个定向的edge $（p_i，p_i，p_j）$ iff $ \ textrm {dist}表示$ p_i $和$ p_j $之间的距离。范围分配问题是分配传输范围，以便$ g_r $具有一定理想的属性，同时最大程度地减少了分配的成本；在这里，成本由$ \ sum_ {p_i \ in p} r（p_i）^α$给出，对于某些常数$α> 1 $，称为距离功率梯度。 我们介绍了范围分配问题的在线版本，其中$ p_j $一一到达，每个到达时都必须更新范围分配。遵循在线算法中的标准，无法删除提供的资源 - 在我们的情况下，这意味着传输范围永远不会减少。我们要维护的属性是$ g_r $具有植根于第一点$ p_0 $的广播树。我们的结果包括以下内容。 - 对于$ d = 1 $，不存在一种1竞技算法。特别是，对于$α= 2 $，任何在线算法的竞争比率至少为1.57。 - 对于$ d = 1 $和$ d = 2 $，我们分析了两种自然策略：新点$ p_j $到达后，最近的邻居将最接近的点增加到覆盖$ p_j $的范围，并增加了最便宜的增加点的范围，而所产生的成本可以增加$ p_j $是最小的。 - 我们将问题推广到任意度量空间，其中我们提供了$ o（\ log n）$ - 竞争算法。
Let $P=\{p_0,\ldots,p_{n-1}\}$ be a set of points in $\mathbb{R}^d$, modeling devices in a wireless network. A range assignment assigns a range $r(p_i)$ to each point $p_i\in P$, thus inducing a directed communication graph $G_r$ in which there is a directed edge $(p_i,p_j)$ iff $\textrm{dist}(p_i, p_j) \leq r(p_i)$, where $\textrm{dist}(p_i,p_j)$ denotes the distance between $p_i$ and $p_j$. The range-assignment problem is to assign the transmission ranges such that $G_r$ has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by $\sum_{p_i\in P} r(p_i)^α$, for some constant $α>1$ called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points $p_j$ arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away -- in our case this means that the transmission ranges will never decrease. The property we want to maintain is that $G_r$ has a broadcast tree rooted at the first point $p_0$. Our results include the following. - For $d=1$, a 1-competitive algorithm does not exist. In particular, for $α=2$ any online algorithm has competitive ratio at least 1.57. - For $d=1$ and $d=2$, we analyze two natural strategies: Upon the arrival of a new point $p_j$, Nearest-Neighbor increases the range of the nearest point to cover $p_j$ and Cheapest Increase increases the range of the point for which the resulting cost increase to be able to reach $p_j$ is minimal. - We generalize the problem to arbitrary metric spaces, where we present an $O(\log n)$-competitive algorithm.
