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

7.7 BICONNECTED ROBOT TEAM MOVEMENT FOR SENSOR DEPLOYMENT

We consider here, the problem of deploying static sensors around a POI using a fleet of mobile robots able to carry them. We describe the solution proposed in Li (2009). Here, the number of mobile robots is considered arbitrary (and limited), and each one is initially supplied with an arbitrary number of sensors. The problem is then to deploy collaboratively the sensors so that their topology forms a triangle tessellation around the POI. The choice of a triangle tessellation is motivated by its interesting geometrical properties that create a near-optimal coverage by the sensors while making them biconnected as a by-product. The main concern is to ensure that the robot network also remains biconnected during the deployment, while minimizing the sum of their moves.

The principal steps of the proposed protocol are as follows. At the beginning, the robots are randomly scattered in the region. They first run an auxiliary protocol such as greedy-rotation-greedy (see Li et al., 2007 or Chapter 10) to gather around the POI in several concentric hexagonal layers that form a triangle tessellation at the local scale. Let us first assume that the number of robots is such that the outermost layer is complete (as with the seven-robots hexagon depicted in the middle of Fig. 7.8). Each robot starts by dropping one sensor at its position; then the whole group of robots shifts in one direction, and starts a circular (or more precisely, a ...