The information available to connectivity-based positioning algorithms is the radio range of sensor devices and the position estimates of neighbors and neighbors of neighbors. This information creates special graph theoretic structures which impose new constraints on the positions of sensor devices. The new constraints sometimes lead to a feasible set of positions with disconnected regions. These properties can be used to reduce the set of feasible positions for a node. In this paper, a new fully distributed positioning algorithm, called Orbit, which exploits these properties is presented for mobile sensor networks. The algorithm uses additional constraints and trims disconnected regions. These new constraints are generated through cooperation between neighbors. The performance of Orbit is examined for many communication and mobility models, including a probabilistic communication model generated from radio experiments. Computer simulation experiments demonstrate that Orbit outperforms a recently proposed positioning algorithm in terms of positional accuracy under different models with a wide range of parameter values. Orbit is implemented on resource limited sensor devices. This implementation demonstrates the feasibility of the algorithm for sensor devices. The algorithm is tested on deployments of the sensor devices in a field and the results are comparable to those from the simulation experiments.

In this paper we present a new positioning algorithm, called Orbit, for mobile sensor networks. The algorithm runs in a fully distributed manner at all nodes. The information available to the algorithm is the radio range of the sensors and, the latest location estimates of neighbours and neighbours of neighbours. The algorithm has several novel aspects. First, we use geometric structures and results from unit disk graphs to impose tighter constraints on sensor positions. Second, we separate the set of possible positions of a node into connected subsets and possibly eliminate some subsets. Using simulations and data from radio experiments, we demonstrate that Orbit outperforms a recently proposed positioning algorithm WMCL-B in terms of positional accuracy for several communication and mobility models with a wide range of parameter values.