OVERVIEW

In many ENS systems a small set of sensor nodes (beacons) has prior information about their locations from GPS or other techniques. The rest of the nodes are not aware of their locations (unknown nodes, or unknown-location nodes). In situ localization is the process that seeks to determine the relative and/or absolute position of each unknown node using the measured distance between different nodes. Such distance can be measured by approaches based on a variety of technologies such as acoustic ranging, RSSI and RF proximity estimation. There are a multitude of algorithmic approaches as well.

The goal is to develop centralized and more importantly localized localization techniques for large-scale sensor networks. Centralized algorithms assume that all the measured distances are forwarded to the center node, which then computes the location of each node using such information. Localized algorithms do not require the existence of the center node and allow each node to compute its position based on its local information by atomic multilateration, a method to estimate the location of a node if it is within the communication range of at least three beacons

APPROACHes

We introduce the concept of Solvability and investigate a set of necessary and sufficient conditions. The location discovery problem is solvable if the location of each unknown node can be uniquely determined with the presence of random noise and/or ranging error.

Lemma 1. There exist situations for whicht the location discovery problem is unsolvable regardless of the number of beacons we have and the technique we use.

Lemma 2. It is not necessary for each node to have at least three neighbors in its communication range to locate its position.

Theorem 3. The following is a set of necessary and sufficient conditions for the location discovery problem to be solvable in a 2-dimensional plane:

C1. At least three non-collinear beacons exist in the network.
C2. Each unknown node either has at least three non-collinear neighbors, or has at least two (collinear) neighbors and its mirror image with respect to this line has at least three non-collinear neighbors.
C3. Each unknown node (or its mirror image if the node does not have three or more non-collinear neighbors) has disjoint paths to at least three beacons.

When the instance is determined to be solvable, we formulate the problem as an instance of a nonlinear function minimization and combine multiple optimization techniques and the maximal likelihood principle to obtain solutions. More importantly, we developed a set of techniques that construct error models that accurately captures the error behavior and use that as our optimization target instead of the traditional norms.

SYSTEMS / EXPERIMENTS

We have conducted two sets of experiments based on the distance measurements collected from a deployed sensor network with and generated by software simulation that operates in both centralized and localized modes. The simulation results are obtained by varying the following parameters: network size, connectivity, random noise level, and the percentage of beacons. We use the distance measurements recorded by actual sensors to evaluate the performance of different optimization targets L1, L2 and statistical error models. The accuracy of locations of the unknown nodes is compared against the communication range. The two key observations from the results are: i) statistical model-based optimization achieves greater accuracy compared to other norms; ii) the localized algorithm achieves a similar level of accuracy as the centralized algorithm while having a large advantage in terms of communication cost.

ACCOMPLISHMENTS

• Defined a set of necessary and sufficient conditions for the problem to be solvable.
• Developed a Distributed localized algorithm based on the set of necessary and sufficient conditions, that not only hold advantages in term of communication cost, but also achieves similar accuracy as the centralized algorithms.
• Constructed non-parametric statistical error models that address the issue of what to optimize.
• Developed a Centralized algorithm based on nonlinear function optimization and the maximal likelihood principle.

FUTURE DIRECTIONS

• Performance studies of the distributed localization approach
• More comprehensive and extensive experiments and evaluations of performance based on different set-ups and parameters
• Performance studies on other types of measurements

Figure 1. Location error normalized against the communication range

PEOPLE

FACULTY

Prof. Miodrag Potkonjak

GRADUATE STUDENTS

Jessica Feng
Gang Qu