Advances in connectivity-based positioning for mobile wireless sensor networks

A sensor network is a new area of application for computing devices which is developing as a consequence of the progression of the computing revolution. A network is composed of small, resource limited, devices that can take local measurements of phenomena such as temperature, pressure, and humidity. The devices communicate wirelessly.

The positions of sensor devices provide a spatial context for measured phenomena however the positions are not typically known after deployment. Therefore the estimation of each device's position is important. Device mobility makes position estimation especially challenging. In connectivity-based position estimation, the presence, or absence, of direct communication between devices constraints the possible positions of a device.

This dissertation investigates connectivity-based position estimation for systems of mobile devices. The product of this dissertation is a lower bound on the positional error, a new positioning algorithm, and the successful execution of the algorithm on deployments of sensor devices.

The analysis of the positional error of a positioning algorithm for mobile devices is a challenging problem. A lower bound on the expected positional error incurred by any connectivity-based positioning algorithm is derived in this work. An analysis of the impact of past constraints on the lower bound reveals that the benefit of additional constraints from the past diminishes as the constraints age.

A distributed positioning algorithm called Orbit is proposed for stationary and mobile sensor networks. Orbit identifies network structures that are used to impose new constraints on device positions, which reduces positional error. The set of possible positions of a device may form isolated regions which is problematic. Orbit removes some of these isolated regions, which reduces positional error. The performance of Orbit and another recent algorithm are evaluated under different communication and mobility models. A performance analysis demonstrates that Orbit outperforms the other under a variety of parameters.

To verify the Orbit algorithm is amenable to sensor networks it is implemented on resource limited hardware. The result is an autonomous sensor network that is tested in several deployments. The position estimates from the sensor network are comparable to those from the simulation of Orbit.