ABSTRACT
CONTENTS 17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 17.2 Event Detection Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
17.2.1 Binary Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 17.2.2 Probabilistic Detection Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480 17.2.3 Tracking Detection Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
17.3 Deployment Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 17.3.1 Number of Deployed Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 17.3.2 Coverage and K -Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 17.3.3 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 17.3.4 Detection Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 17.3.5 Network Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
17.4 Sensor Network Deployment Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 17.4.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 17.4.2 Uniform Deployment Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
17.4.2.1 Uniform Random Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 17.4.2.2 Regular Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
17.4.3 Nonuniform Deployment Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 17.4.3.1 Optimal Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 17.4.3.2 Distribution-Based Random Deployment . . . . . . . . . . . . . . . . . . . . 486 17.4.3.3 Max-Avg-Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 17.4.3.4 Max-Min-Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
17.4.3.5 Min-Miss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490 17.4.3.6 Diff-Deploy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 17.4.3.7 Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 17.4.3.8 Differentiated Sensor Deployment Based on Tabu
Search Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 17.4.4 Deployment Strategies Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
17.5 Conclusion and Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
In this chapter, we provide a deep overview of the different wireless sensor networks’ (WSNs’) uniform and nonuniform deployment strategies proposed in the literature. Generally, the observed area is characterized by the geographical irregularity of the sensed events. We expose the sensor deterministic and probabilistic event detection models, and the different metrics for WSN evaluation. Thereafter, we formalize the generalized WSN deployment problem, which is a multi-objectives problem and known to be NP-hard. We describe all the exact and heuristic algorithms found in the literature. We implement all the WSN deployment strategies and we compare them in terms of (1) number of sensors deployed, (2) event detection confidence, (3) network connectivity, and (4) computation complexity.
