Best and worst-case coverage problems for arbitrary paths in wireless sensor networks

The best-case and the worst-case coverage were proposed originally for a single source and destination pair in a sensor network. In this paper, we propose a new coverage measure of the sensor network considering arbitrary paths. Surprisingly, this new measure captures both the best-case and the worst-case coverage of the sensor network simultaneously, enabling us to evaluate the given network in a global viewpoint. Accordingly, we pose the evaluation and the deployment problems; the former is to evaluate the new coverage measure of a given sensor network, and the latter is to find an optimal placement of k additional sensor nodes to improve the coverage for a given positive integer k. We present several algorithms solving the problems that are either centralized or localized with theoretical proofs and simulation results, showing that our algorithms are efficient and easy to implement in practice while the quality of outputs is guaranteed by formal proofs. Our algorithms are based on an interesting relation between our new coverage measure and a certain quantity of a point set, called the bottleneck, which has been relatively well studied in other disciplines. In doing so, we prove that a maximal support path can always be found in the minimum spanning tree; this is another contribution of ours.