Research Abstracts - 2007

Introduction

Location determination, or localization, is essential in many applications, such as autonomous system, sensor network applications, and context-aware applications. There are currently many existing solutions including GPS, inertial sensors, vision sensors, radio sensors, and so on. However, each solution has its own limitation. For example, GPS service is often unavailable indoors, and inertial sensing without the aid of external reference accumulates error as time goes.

Particularly, we consider a situation that each member of a group of users, i.e. people or robots, wants to know positions and motions of entire group members in GPS-denied environment : indoors, underground or underwater, or outdoor regions where sky is occluded. Also, in many of these situations, the use of beacons is impossible, or at least, unrealistic. Instead, we assume that each user has ranging capability to other users with inexpensive devices. Under these assumptions, our goal is to reconstruct a global geometry of moving users and provide a relative global view to users.

This research defines the problem as the network localization problem with time-varying distance information where nodes represent users and edges represent connections between users. Given sequences of range measurements over time, we envision to solve a problem by recovering motion-descriptive parameters from those measurements and then recovering positions and velocities at the same time, rather than solving a problem at each instance.

Approach

Handling the three-dimensional mobile network in which all nodes are moving arbitrarily is a difficult task. Therefore, we introduce simplifying assumptions, which are :

1. All nodes are on the same plane, i.e. the problem is two-dimensional.
2. All nodes are moving with constant velocity.
3. Almost all nodes have sufficient connectivity to be rigidly located in the network.

These assumptions will be relaxed in future works. With these assumptions, our approach consists of the following four phases :

1. Motion Parameters Estimation

For each node pair, motion parameters describing the relative motion of one node to the other are recovered from a sequence of range measurments.

2. Path Estimation

Using motion parameters estimated at phase 1, the algorithm recovers relative positions and velocities of nodes for all possible triplets of nodes

3. Local Cluster Generation

Each of some elected nodes, or all nodes in the network makes a local view which is centerd at itself. In this phase, triangles recovered at phase 2 are used to make local clusters. The origin node of a local cluster fixes a triangle containing itself and stitch other triangles along shared edges up to the maximum ranging radius.

4. Inter-Cluster Alignment

To obtain a global view of the network, the algorithm fixes one cluster and merges other clusters along the spanning tree (figure 1). Because each cluster is localized in its own view, the algorithm finds the best coordinate transformation between two sets of common nodes represented in different coordinates.

Through this process, the algorithm recovers a relative motion estimate of all nodes in the network.

Figure 1. Cluster 2 is merged into cluster 1. Nodes 6,7,10,and 28(in green circle) were not localized in cluster 1 before this step, while other nodes of cluster 2 were common in cluster 1. A similarity transformation is found between common nodes and applied to cluster 2. After then, new nodes are merged into cluster 1.

Progress and Future work

For an evaluation of the algorithm, we assumed the use of ultra-wideband(UWB) radio as a ranging device. We have implemented a simulation and shown that, with high ranging capabilities of UWB radio which can range and communicate with each other within a radius of approximately 30 meters with noise of 3~4 centimeters in line-of-sight conditions, our method can achieve good availability and high accuracy of node positions and velocities.

An example of the localization result output is shown in figure 2. 120 moving nodes are placed randomly in 150m x 150m region. Nodes are assumed to move with constant velocities and ranging noise is modeled as Gaussian. Because the original output is a set of relative positions and velocities to the selected origin node, it is transformed to match ground-truth for comparison. In practice, the user can make use of some additional constraints to determine absolute positions and velocities, if needed.

Figure 2. Recovered position and velocity. The ranging radius of a node is shown in green dashed circle. In this example, 112/120 nodes are localized.

The current algorithm will be further developed and validated under various environmental conditions, and then implemented on real devices. Also, We are planning to extend our algorithm to more general settings. First, the algorithm will be extended to handle piecewise linear motion paths and various motion states. This extension will provide more realistic localization capability to the user. We also envision the integration of intertial devices to provide additional constraints to the solution and to handle transient state when the performance of ranging measurment is degraded or ranging itself is impossible. Additionally, optimization of computational complexity and communication cost will be important for the algorithm to be scalable.