Large infrastructure networks (e.g. for transportation and power
distribution) require constant monitoring for failures, congestion, and other
adversarial events. However, assigning a sensor to every link in the network is
often infeasible due to placement and maintenance costs. Instead, sensors can
be placed only on a few key links, and machine learning algorithms can be
leveraged for the inference of missing measurements (e.g. traffic counts, power
flows) across the network. This paper investigates the sensor placement problem
for networks. We first formalize the problem under a flow conservation
assumption and show that it is NP-hard to place a fixed set of sensors
optimally. Next, we propose an efficient and adaptive greedy heuristic for
sensor placement that scales to large networks. Our experiments, using datasets
from real-world application domains, show that the proposed approach enables
more accurate inference than existing alternatives from the literature. We
demonstrate that considering even imperfect or incomplete ground-truth
estimates can vastly improve the prediction error, especially when a small
number of sensors is available.

研究了基于流量守恒假设下的传感器放置问题，提出了一种高效自适应的贪心启发式算法，并通过实验结果证明该方法能够比现有方法更准确地推断出网络中缺失的测量值，尤其在只有少量传感器可用时，考虑不完全或不准确的基准估计结果能够大大提高预测误差。