Minimizing mobile sensor movements to form a line K-coverage

In wireless sensor networks and social networks, distributed nodes usually form a network with coverage ability for a lot of applications, such as the intrusion detection. In this paper, a new kind of coverage problem with mobile sensors is addressed, named Line K-Coverage. It guarantees that any intruder trajectory line cutting across a region of interest will be detected by at least K sensors. For energy efficiency, we aim to schedule an efficient sensor movement to satisfy the line K-coverage while minimizing the total sensor movements, which is named as LK-MinMovs problem. We firstly construct two time-efficient heuristics named LK-KM and LK-KM+ based on the famous Hungarian algorithm. By sacrificing optimality a little bit, these two algorithms have better time efficiency. Then we propose a pioneering layer-based algorithm LLK-MinMovs to solve LK-MinMovs in polynomial time. Here, we assume that all sensors are initially located in a closed region. We validate its correctness by theoretical analysis. Later, the more general situation are considered that all sensors are allowed to locate outside of the region. We improve LLK-MinMovs algorithm to the general version: GenLLK-MinMovs. More importantly, our GenLLK-MinMovs fixes a critical flaw for MinSum algorithm which was proposed by previous literature to solve line 1-coverage problem. We show the flaw using a counter example. Finally, we validate the efficiency of all our designs by numerical experiments and compare them under different experiment settings.