Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

10.6 SENSOR SELF-DEPLOYMENT

Sensor self-deployment is an active research subject that is continuously drawing large amount of attention. In the literature, it has been modeled and solved using different techniques. At the time of this writing, there exist eight different self-deployment approaches as listed below:

• Virtual Force (Vector-Based) Approach. Sensors move according to a movement vector computed using the relative position of their neighbors.
• Voronoi-Based Approach. Sensors adjust their location to reduce uncovered local area in its Voronoi polygon possibly in multiple rounds.
• Load Balancing Approach. The number of sensors in the regions of a partitioned sensor field is balanced through multiple rounds of scans.
• Stochastic Approach. Sensors spread out through random walk.
• Point-Coverage Approach. The area coverage problem is converted to a point-coverage problem over certain geographic graph.
• Incremental Approach. Sensors are deployed incrementally, that is, one at a time, based on the information gathered from previously deployed sensors.
• Maximum-Flow Approach. Sensors deployment is modeled as minimum-cost, maximum-flow problem from source regions to whole regions in ROI.
• Genetic-Algorithm Approach. Sensor movement plan is generated by multiround selection and reproduction simulating genes and nature selection.

In the above list, the first five are distributed or localized approaches. The rest are centralized approaches with requirement for a global view of the network. ...