Coverage problem with uncertain properties in wireless sensor networks: A survey

The coverage problem, as a fundamental problem for almost all types of applications in wireless sensor networks (WSNs), has been studied for over a decade. Because of its simplicity and ease of analysis, full coverage is widely adopted in many theoretical studies. However, a full coverage requirement can be relaxed into a partial one to avoid the overuse of sensors. Moreover, sometimes full coverage is not the best way to represent some real-world applications because of its strong restrictions and its deterministic characteristics. From this view, a better way is to introduce uncertainty into coverage problems. By analyzing the characteristics of partial or probabilistic coverage problems, and comparing them with full coverage problems, this survey is helpful to establish an overview of non-deterministic coverage problems, denoted as coverage problems with uncertain properties. This survey then sketches a general research framework to solve such problems. According to the framework, we first introduce a series of basic concepts of coverage problems with uncertain properties and then summarize the relevant models, such as detection models, network models, and deployment models. Based on these models, we discuss three main objectives, namely, to maximize coverage quality, to maximize network lifetime, and to minimize the number of sensors. Next, we illustrate several solution strategies for these three objectives, such as deployment, scheduling or selection, and movement or adjustment. Then, we classify the solutions (algorithms) from different aspects, i.e., traditional and heuristic, approximation, distributed and centralized, and random algorithms. In addition, the theoretical analysis for algorithms and the platforms for simulating the numerical experiments are also summarized. Finally, we discuss future challenges and directions for research of coverage problems with uncertain properties.