## Efficient Localized Network Discovery for Wireless Ad Hoc Sensor
Networks

Farinaz Koushanfar and Miodrag Potkonjak^{1}

(Professor Alberto L. Sangiovanni-Vincentelli)

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.

^{1}Outside Adviser (non-EECS), UCLA

Send mail to the author : (farinaz@eecs.berkeley.edu)

Edit this abstract