Minimal Problems and Applications in TOA and TDOA Localization

Sammanfattning: The central problem of this thesis is locating several sources and simultaneously locating the positions of the sensors. The measurements captured by the sensors are time of arrival (TOA), time difference of arrival (TDOA), unsynchronized TDOA, or received signal strength indication (RSSI), all a variation of distance measurement between sensors and sources. Signals can be either sound or radio for TOA, TDOA, and unsynchronized TDOA, and radio for RSSI. To be able to simultaneously locate sensors and sources open up for many on-the-fly applications not needing a calibrated rig of sensors. By doing sensor calibration, the methods in this thesis also opens up for using much previous research in the field of TOA and TDOA localization, which has mostly dealt with locating sources from known positions of the sensors. In this thesis, several minimal problems for uncalibrated sensor network localization are studied and solved. A problem is minimal if it only needs the smallest necessary number of measurements to estimate the model parameters, thus neither making the model parameters over- nor underdetermined. Apart from revealing understanding and theoretical aspects of the problem, studying minimal problems also have interesting applications when dealing with larger measurement sets containing severe outliers. This thesis utilizes the random sample consensus method (RANSAC), that uses the minimal algorithms developed in this thesis, to do localization of the sensors and sources and simultaneously weed out outliers in the measurements. The set of inliers and parameters are then used in non-linear optimization schemes to refine the parameters. Experiments show that for experiments with sound, microphone and sound sources can be located with centimeter precision. For solving the minimal problems, techniques from linear algebra and multivariate polynomial solving are utilized. This thesis further investigates simultaneous localization of cell phone users and mapping of the radio environment in multi-floor environments, using RSSI measurements and pressure sensors. Nonlinear optimization and filtering techniques are used to do parameter estimation, and results in two buildings with several floors indicates that these methods can be deployed with errors in the range of 10-20m horizontally, with >95% accuracy in floor detection.