Static Optimal Sensor Selection via Linear Integer Programming: The Orthogonal Case
Static Optimal Sensor Selection via Linear Integer Programming: The Orthogonal Case
复制标题
通过线性整数规划进行静态最佳传感器选择：正交情况
DOI：
--
复制
发表时间：
2017
影响因子：
3.9
通讯作者：
T. Başar
中科院分区：
文献类型：
--
作者：
Jun Moon;T. Başar
我们考虑静态最优传感器选择问题，我们在 <inline-formula><tex-math notation="LaTeX">$s$ </tex-math></inline-formula> 可能的传感器中选择 <inline-formula> <tex-math notation="LaTeX">$d$</tex-math></inline-formula> 传感器与 <inline-formula><tex-math notation="LaTeX">$d < s$</tex-math> </内联公式>。假设 <inline-formula><tex-math notation="LaTeX">$s$</tex-math> </inline-formula> 传感器彼此正交，我们将最优传感器选择问题视为线性整数程序 (LIP)，对应于线性最小二乘估计误差协方差迹的最小化。我们证明，尽管一般的 LIP 是<italic>NP-hard</italic>，但我们的问题可以作为线性程序在多项式时间内求解；因此，没有必要寻求次优解决方案。这是由于关联的积分凸多面体约束集及其总单模性属性。我们提供仿真结果来证明具有正交性条件以及附加传感器选择约束的相应问题的多项式时间可解性。
We consider the static optimal sensor selection problem, where we optimally select <inline-formula> <tex-math notation="LaTeX">$d$</tex-math></inline-formula> sensors among <inline-formula><tex-math notation="LaTeX">$s$ </tex-math></inline-formula> possible sensors with <inline-formula><tex-math notation="LaTeX">$d < s$</tex-math> </inline-formula>. Under the assumption that the <inline-formula><tex-math notation="LaTeX">$s$</tex-math> </inline-formula> sensors are mutually orthogonal to each other, we cast the optimal sensor selection problem as a linear integer program (LIP) that corresponds to minimization of the trace of the linear least-squares estimation error covariance. We show that even though general LIPs are <italic>NP-hard</italic>, our problem can be solved in polynomial time as a linear program; hence, it is not necessary to go for suboptimal solutions. This is due to the associated integral convex polyhedron constraint set followed by its total unimodularity property. We provide simulation results to demonstrate polynomial-time solvability of the corresponding problem with the orthogonality condition as well as additional sensor selection constraints.