Network discovery is a fundamental task in wireless ad hoc (sensor) networks. The goal is to identify a part of the network with a particular user-specified set of graph theoretic and/or geometric properties. Representative examples of network discovery tasks include finding the shortest path between two points, a path or spanning tree through a specified subset of points, or all nodes in a given area, and areas that are not covered (holes and obstacles). We are developing efficient localized algorithms for all of these problems using the same basic systematic approach. The key new insight and building block is at each step of the process the goal is to visit nodes that provide new knowledge about the network structure, but also are likely to have neighbors that will facilitate the network discovery process. The likelihood is measured using a variety of weighted Monte Carlo integral calculations for evaluation of newly discovered areas. Although the algorithms are localized, they are able to efficiently build or estimate global objective functions.
The algorithms are flexible in the sense that they can be easily adapted to a variety of network, communication, and cost models. The effectiveness of the approach and algorithms is demonstrated on benchmarks using statistical scaling algorithms that quantify the tradeoff between the quality of the solution and the energy cost of the algorithm.
1Outside Adviser (non-EECS), UCLA