目標點的完全覆蓋問題

在n個感測器(位置已知)的感測網路中, 要如何選取最少數目的感測器,使得所有m個目標點(位置已知)皆可以被感測器覆蓋(cover), 已被證明是NP-complete問題. 參見下面這篇論文.

Mihaela Cardei and Ding-Zhu Du, "Improving Wireless Sensor Network Lifetime through Power Aware Organization," Wireless Networks 11, pp. 333–340, 2005.