Ad­hoc Localization of Wireless Sensor Nodes

international exchange of scholars for software projects

Research Exchange (ReX) Program Update
Koen Langendoen
Delft University of Technology, The Netherlands

This summer I worked for three months at the Berkeley Wireless Research Center (BWRC) as a visiting research scholar in the PicoRadio project. This visit was sponsored by a grant from the USENIX association and stichting NLnet (ReX program). Working at the BWRC was a great opportunity for me to get a hands­ on introduction into the rapidly evolving field of wireless sensor networks. The knowledge, skills, and research contacts acquired during my stay at the BWRC will be of great help in my new job as assistant professor at Delft University of Technology.

PicoRadio

The PicoRadio group at UC Berkeley is addressing the technological possibilities to integrate sensors, an embedded processor, a wireless link, and a power supply into a single small device. The target is to have operational sensor nodes by December 2002. Networks of wireless sensors can be used for a wide range of monitoring & control applications, for example, temperature control for office spaces, climate control for greenhouses, and security of buildings.

To ease the development of (commercial) applications it is of great importance that wireless sensor networks are (largely) self­configuring; with as little infrastructure as possible sensor nodes should become aware of their environment and start communicating and collaborating with neighbors to carry out the specific task at hand. System software (e.g., routing and location discovery) is needed to support self­organizing applications on wireless sensor networks.

Ad­hoc localization

During my stay at the BWRC I focused on the problem of determining the location of the individual nodes in an ad­hoc sensor network. Knowing the location of a sensor node is required to answer questions like "what is the temperature in the kitchen?", and for implementing efficient routing protocols (the energy required to communicate between nodes grows quadratically with the distance).

We assume that a small fraction (<10%) of anchor nodes know their location, for example, because they are equipped with an additional GPS receiver. The remaining nodes should then estimate their location using distance measurements to their neighbors. Within the PicoRadio project we use a 2­phase approach. First, the nodes compute a rough estimate based on the topology of the network; counting the number of hops to different anchors indicates a rough region of possible locations. Second, nodes refine their locations in a number of iterations involving multilateration. Knowing the distances to 3 reference points suffices to determine the location of a node (3­lateration). Additional reference points, however, are needed to cope with errors in the distance measurements.

The iterative refinement method raises two questions: 1) does the procedure converge?, and 2) how accurate are the estimated locations? Initial experiments with a discrete event simulator showed that even with perfect information (i.e., distance measurements without errors) very poor locations resulted in many cases.

I was able to identify two essential causes:

1. Bad topology. Nodes with too few connections (<3) to reference points cannot be properly located. Likewise, sets of nodes with too few "external" connections cannot be located. I developed an ad­hoc rule to identify such cases.
2. Error propagation. It is of critical importance to limit the effects of poor location estimates since in iterations the whole network is infected, where d is the network diameter.

Our solution to the above problems is to associate a confidence (a factor between 0 and 1) with each location estimate and weigh the information passed to the multilateration procedure.

Results and future work

Using confidence factors improved both the number of cases that converge as well as the accuracy of the individual locations. Figure 1 shows the error distribution (as percentage of the radio range) for a network of 400 nodes uniformly distributed over a square area including 40 (10%) anchor nodes. The correlation between the confidence metric and the location errors is also shown.

Figure 1: Error distribution (left) and confidence correlation (right).

These nice results, however, were obtained using true distances; the effects of measurement errors still need to be studied. Furthermore, we like to obtain a better understanding of the minimum requirements on the topology and infrastructure (average connectivity, fraction of anchor nodes, anchor placement) to realize a specified location accuracy. We also need to address the energy efficiency (i.e. amount of processing and communication) of the developed ad­hoc localization algorithm before running silicon can be produced. I am looking forward to collaborate with the PicoRadio group on these and other research questions in the future.