Home
Resource
Upper and lower bounds in radio networks
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(476.80 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Mosteiro, Miguel. Upper and lower bounds in radio networks. Retrieved from https://doi.org/doi:10.7282/T3PZ5985

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

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
Date Created2007
Other Date2007 (degree)
SubjectComputer Science, Sensor networks, Multisensor data fusion, Signal processing, Operator theory
Extentxi, 93 pages
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.
NotePh.D.
NoteIncludes bibliographical references (p. 86-91).
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3PZ5985
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.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024