Collaborative Localization Using Wireless Sensor Networks

Xie, Zhiheng, Computer Science - School of Engineering and Applied Science, University of Virginia
Stankovic, John, Department of Computer Science, University of Virginia

Wireless sensor networks (WSN) are now widely used in many applications. Knowing each sensor node's position is always a critical issue for these applications. Without the position information, the sensory data become meaningless, and a number of location based routing protocols would not work.

In the WSN research field, the existing localization solutions can be divided into range-based solutions and range-free solutions. Despite which method is used, the existing solutions suffer from one or more of the following drawbacks: 1) only including homogeneous positioning information; 2) only suitable for static WSNs, but not mobile WSNs; 3) requiring pre-set infrastructures; 4) non-deterministic uncertainty. Another category of mobile node localization methods are from the robotics field. The representatives are simultaneous localization and mapping (SLAM)and the collaborative localization (CL). However, SLAM solution is not suitable for resource constrained WSN because of its iterative dynamic model, high computational complexity and not taking advantage the collaboration between nodes. The existing CL solutions suffer from either inefficiency or the over confidence problem.

This dissertation proposes a unified range-based localization mathematical model, which can be applied to a large scale static WSN, to a large scale WSN with dynamic topology changes, or to a mobile WSN. When designing such a model, the following purposes are addressed: 1) unified representation of various measurement types; 2) suitable for both mobile and static networks; 4) both centralized and decentralized architecture support; 5) providing not only position estimation, but also the quantitative uncertainty (the covariance matrix) of the estimation; 6) efficiency and scalability. The effectiveness and the efficiency of this model are demonstrated by a decentralized and fully self-contained indoor pedestrian localization system.

We first propose the incremental node-voltage analysis (INOVA) localization algorithm, which is used to localize a stationary WSN in a centralized way. INOVA analogizes a WSN to a generalized electrical network, and borrows the node-voltage analysis from the electrical engineering field to reduce the computational complexity by 70 times (comparing with the optimization technique based solution--Best Linear Unbiased Estimator). Since INOVA is fast on updating, it is suitable to localize a large scale static WSN with frequently dynamic changes or a mobile network. By using the same idea, an overlapping subgraph estimator of covariance (OSE-COV) algorithm is proposed. Together with the original overlapping subgraph estimator (OSE) algorithm, it is able to estimate both the positions and the covariance matrices of sensor nodes in a decentralized way. In order to localize mobile nodes in even a more efficient way, the elastic decentralized collaborative localization (EDCL) algorithm is proposed. Different form the above two algorithms, which are theoretically optimal and asymptotically optimal respectively, EDCL is a non-optimal solution. By controlling the marginalization factor Q, which indicates the number of the historical measurements allowed to store in memory, EDCL is able to make the trade-off between the optimality and the resource consumption. Besides the localization theory, we also deduce how to use the quantitative uncertainty for confidence region inference and guiding the anchor selection process.

To demonstrate the effectiveness of the EDCL algorithm, a hybrid pedestrian collaborative localization system is built. The system is fully decentralized self-contained. It consists of three modules, a RSS to distance estimator, a foot-mounted inertial navigation module, and the EDCL filter. The experimental results show that EDCL reduces the error by as much as 49.44% over the inertial-only solution, and the resource consumption is low (with maximum memory usage 760 bytes and average communication cost 33 bytes per message).

PHD (Doctor of Philosophy)
wireless sensor networks, localization, distributed
All rights reserved (no additional license for public reuse)
Issued Date: