A key problem in sensor networks is to decide which sensors to query when, in order to obtain the most useful information (e.g., for performing accurate prediction), subject to constraints (e.g., on power and bandwidth). In many applications the utility function is not known a priori, must be learned from data, and can even change over time. Furthermore for large sensor networks solving a centralized optimization problem to select sensors is not feasible, and thus we seek a fully distributed solution. In this paper, we present Distributed Online Greedy (DOG), an efficient, distributed algorithm for repeatedly selecting sensors online, only receiving feedback about the utility of the selected sensors. We prove very strong theoretical no-regret guarantees that apply whenever the (unknown) utility function satisfies a natural diminishing returns property called submodularity. Our algorithm has extremely low communication requirements, and scales well to large sensor deployments. We extend DOG to allow observation-dependent sensor selection. We empirically demonstrate the effectiveness of our algorithm on several real-world sensing tasks.

本文提出了一种分布式在线贪心（Distributed Online Greedy, DOG）算法，用于从大型传感器网络中选择传感器来获取最有用的信息，算法证明了当效用函数满足自然的递减收益特性（称为次模性）时，可以实现非常强的理论无悔保证。该算法具有极低的通信要求，并可扩展到大型传感器网络中，同时支持基于观测值的传感器选择。在多个真实感知任务中进行了实证研究，证明本算法的有效性。

在线分布式传感器选择