TY - JOUR
TI - Upper and lower bounds in radio networks
DO - https://doi.org/doi:10.7282/T3PZ5985
PY - 2007
AB - 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, we seek efficient-provable solutions to the most fundamental problem in Sensor Networks, its self organization. At the same time, we study lower bounds on the time complexity of such a problem. The first set of results in this thesis address the three parts that Sensor Network bootstrapping research has: to model the restrictions on sensor nodes; to prove that the sensors connectivity graph has a subgraph that would make a good network; and to give a distributed protocol for finding such a network subgraph that can be implemented on sensor nodes. A study of the Sensor Network 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. The second set of results of this thesis shows new lower bounds for collision-free transmissions in Radio Networks. The main lower bound is tight for a variety of problems. An extension of this result gives the first lower bound for Sensor Network Bootstrapping. A lower bound on the expectation for fair protocols is also shown. Another contribuition of this thesis is a survey of research in Radio Networks. The survey includes two parts that have received extensive study: upper bounds for Sensor Network formation, and upper and lower bounds for non-colliding transmissions in Radio Networks proved under the broader context of more complex problems.
KW - Computer Science
KW - Sensor networks
KW - Multisensor data fusion
KW - Signal processing
KW - Operator theory
LA - English
ER -