论文标题
如何唤醒您的邻居：无线电网络中安全且几乎最佳的通用节能
How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks
论文作者
论文摘要
最近的工作表明，有时可以通过在不需要的情况下自适应降低无线电接收器的能量来显着减少某些无线电网络算法的能量。尽管过去的工作重点是以这种方式修改特定的网络算法，但我们现在询问一个问题，即是否可以以通用的方式解决此问题，将算法视为一种黑匣子。 我们能够以肯定的方式回答这个问题，并提出了一种新的一般方法，以修改任意无线电网络算法以节省能源。以时间复杂性的增加，我们可以证明能量使用的程度几乎是一定类别的通用算法，因此我们可以将能量使用量减少。 作为一个应用程序，我们表明我们的算法将无线电网络中广度优先搜索的能源成本从$ 2^{o（\ sqrt {\ log n}）} $的最佳限制中降低到$ \ mathrm {polylog}（polylog}（n）$，其中$ n是$ n $ n $ n $ n $ n $ n $ n $ 我们算法中的一个关键成分是基于在多个尺度上完成的添加剂伏诺伊分解的分层聚类。在无线电网络中有关能源感知计算的其他最新工作中，已经使用了类似的聚类算法，但是我们认为此处介绍的特定方法可能具有独立的兴趣。
Recent work has shown that it is sometimes feasible to significantly reduce the energy usage of some radio-network algorithms by adaptively powering down the radio receiver when it is not needed. Although past work has focused on modifying specific network algorithms in this way, we now ask the question of whether this problem can be solved in a generic way, treating the algorithm as a kind of black box. We are able to answer this question in the affirmative, presenting a new general way to modify arbitrary radio-network algorithms in an attempt to save energy. At the expense of a small increase in the time complexity, we can provably reduce the energy usage to an extent that is provably nearly optimal within a certain class of general-purpose algorithms. As an application, we show that our algorithm reduces the energy cost of breadth-first search in radio networks from the previous best bound of $2^{O(\sqrt{\log n})}$ to $\mathrm{polylog}(n)$, where $n$ is the number of nodes in the network A key ingredient in our algorithm is hierarchical clustering based on additive Voronoi decomposition done at multiple scales. Similar clustering algorithms have been used in other recent work on energy-aware computation in radio networks, but we believe the specific approach presented here may be of independent interest.
