A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks
A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks
复制标题
大规模传感器网络中近乎最优传感器调度的随机贪婪算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
U. Topcu
中科院分区：
文献类型：
--
作者：
Abolfazl Hashemi;Mahsa Ghasemi;H. Vikalo;U. Topcu
研究了资源受限线性动态系统中的传感器调度问题，其目标是从一个大网络中选择一小部分传感器来执行状态估计任务。我们将这一问题表述为均匀矩阵约束下单调集合函数的最大值问题。我们提出了一种随机贪婪算法，它比最先进的方法要快得多。通过引入曲率的概念来量化函数与子模的接近程度，我们分析了所提出算法的性能，并根据最优MSE找到了使用所选传感器的估计器的期望均方误差（MSE）的界。此外，我们推导了曲率的概率界，其中测量值是有界$\ell_{2}$范数的随机向量。仿真结果证明了随机贪心算法与贪心和半定规划松弛方法的有效性。
We study the problem of scheduling sensors in a resource-constrained linear dynamical system, where the objective is to select a small subset of sensors from a large network to perform the state estimation task. We formulate this problem as the maximization of a monotone set function under a uniform matroid constraint. We propose a randomized greedy algorithm that is significantly faster than state-of-the-art methods. By introducing the notion of curvature which quantifies how close a function is to being submodular, we analyze the performance of the proposed algorithm and find a bound on the expected mean square error (MSE) of the estimator that uses the selected sensors in terms of the optimal MSE. Moreover, we derive a probabilistic bound on the curvature for the scenario where the measurements are i.i.d. random vectors with bounded $\ell_{2}$-norm. Simulation results demonstrate efficacy of the randomized greedy algorithm in a comparison with greedy and semidefinite programming relaxation methods.