Minimizing receivers under link coverage model for device-free surveillance

Device free localization can detect and locate human presence nearby via many wireless links. For a wireless link, human presence nearby affects the wireless transmission of the link. From Received Signal Strength (RSS) readings of the receiver, we can detect human presence around. This actually provides us a link-centric ‘sensing’ model, different from the traditional node-centric sensing model (e.g., disk model). Based on the new link coverage model, we investigate the target coverage problem with the minimum number of receivers, i.e., how to deploy least receivers to cover all targets when senders are pre-deployed. By transforming DOMINATING SET to LINK COVER, we prove that the minimum link cover problem (MLC) is NP-hard. Then we give two algorithms with guaranteed performance bounds. For density constrained MLC, we propose a polynomial time approximation scheme (PTAS). Finally, extensive simulations demonstrate the effectiveness of our proposed algorithms.