### DIMACS Theoretical Computer Science Seminar

Title: Upper and Lower Bounds in Sensor Network Bootstrapping

Speaker: **Rohan Fernandes**, Rutgers University

Date: November 29, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Sensor nodes are very weak computers that get distributed at random
on a surface. Once deployed, they must wake up and form a radio
network. Sensor network bootstrapping research thus has three
parts: one must model the restrictions on sensor nodes; one must
prove that the connectivity graph of the sensors has a subgraph that
would make a good network; and one must give a distributed protocol
for finding such a network subgraph that can be implemented on
sensor nodes.

Although many particular restrictions on sensor nodes are implicit
or explicit in many papers, there remain many inconsistencies and
ambiguities from paper to paper. The lack of a clear model means
that solutions to the network-bootstrapping problem in both the
theory and systems literature all violate constraints on sensor
nodes. For example, random geometric graph results on sensor
networks predict the existence of subgraphs on the connectivity
graph with good route-stretch, but these results do not address the
degree of such a graph, and sensor networks must have constant
degree. Furthermore, proposed protocols for actually finding such
graphs require that nodes have too much memory, whereas others
assume the existence of a contention-resolution mechanism.

We present a formal Weak Sensor Model(WSM) that summarizes the
literature on sensor node restrictions, taking the most restrictive
choices when possible. We show that sensor connectivity graphs have
low-degree subgraphs with good \emph{hop-stretch}, as required by the WSM.
Finally, we give a WSM-compatible protocol for finding such graphs.
Ours is the first network initialization algorithm that is
implementable on sensor nodes.

Time allowing, we will also show new lower bounds for collision-free
transmissions in Radio Networks. Our main result is a tight lower bound
of $\Omega(\log n \log (1/\epsilon))$ on the time required by a uniform
randomized protocol to achieve a clear transmission with success
probability $1-\epsilon$ in a one-hop setting. This result is extended
to non-uniform protocols as well. A new lower bound is proved for the
important multi-hop setting of nodes distributed as a connected Random
Geometric Graph. Our main result is tight for a variety of problems.