Sensor Nodes are very weak computers that get distributed at random on a surface in order to achieve a large-scale sensing task. Once deployed, they must wake up and form a Radio Network. Given the extremely limited resources of Sensor Nodes, finding efficient solutions even for basic problems is very challenging. The results in this thesis concern the initialization from scratch, or Bootstrapping, of a Sensor Network. More precisely, to find efficient provable solutions to the most fundamental problem in Sensor Networks, its self-organization, and to show lower bounds of the time complexity of such a problem.
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 Sensor 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 of 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.
Thus, Sensor Network Bootstrapping research 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 fast distributed protocol for finding such a network subgraph that can be implemented on Sensor Nodes. We present a formal Weak Sensor Model 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 hop-stretch, as required by the Weak Sensor Model. We give a Weak Sensor Model-compatible protocol for finding such graphs. Ours is the first network initialization algorithm that is implementable on Sensor Nodes.
A study of the Sensor Networks Bootstrapping problem would not be complete without a study of lower bounds on the time complexity of solving it. Strikingly, the most basic problem in a Radio Network, i.e. to achieve a successful transmission, can be proved to be as difficult as other more complex problems under the constraints of a Sensor Node. We show here new lower bounds for collision-free transmissions in Radio Networks for different settings and protocols. The main lower bound is tight for a variety of problems. An extension of this result gives the first lower bounds for Sensor Network Bootstrapping.
All Are Welcome To Attend
