RUcore Resource Object
RUcore Resource Object
PDF-1(476.80 KB)
Uniform TitleUpper and lower bounds in radio networks
NameMosteiro, Miguel (author), Farach-Colton, Martin (chair), Muthukrishnan, S. (internal member), Steiger, William (internal member), Bender, Michael (outside member), Rutgers University, Graduate School-New Brunswick,
Degree Date2007
Date Created2007
SubjectComputer Science,
Sensor networks,
Multisensor data fusion,
Signal processing,
Operator theory
DescriptionSensor 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.
Note[degree] Ph.D.
Note[bibliography] Includes bibliographical references (p. 86-91).
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.13483
LanguageEnglish
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.