Self-Deployment of Mobile Sensor Networks on a Ring

Mobile sensors can self-deploy in a purely decentralized and distributed fashion, so as to reach in a finite time a state of static equilibrium in which they uniformly cover the environment. We consider the self-deployment problem in a ring (e.g., a circular rim); in particular we investigate under what conditions the problem is solvable by a collection of identical sensors without a global coordinate system, however capable of determining the location (in their local coordinate system) of the other sensors within a fixed distance (called visibility radius). A self-deployment is exact if within finite time the distance between any two consecutive sensors along the ring is the same, d; it is -approximate if within finite time the distance between two consecutive sensors is between d − and d + . We prove that exact self-deployment is impossible if the sensors do not share a common orientation of the ring. This impossibility result holds even if the sensors have unlimited memory of the past, their visibility radius is unlimited, and all their actions, when active, are instantaneous. We thus consider the problem in an oriented ring. We prove that if the sensors know the desired final distance d, then exact self-deployment is possible. If the desired final distance d is not known, we prove that -approximate self-deployment is possible for any chosen > 0. The proofs of these results are constructive. In each case we present a simple protocol that allows the sensors to achieve the claimed level of self-deployment. These positive results hold even if sensors are oblivious (i.e., have no memory of past actions and computations), asynchronous (i.e., a sensor becomes active at unpredictable times and the duration of its actions is unpredictable), and have limited visibility radius. Our protocols can be employed, without modifications, on the perimeter of any convex region.