RUcore: Rutgers University Community Repository
Upper and lower bounds in radio networks
Descriptive
TitleInfo
Title
Upper and lower bounds in radio networks
Name
(type = personal)
NamePart
(type = family)
Mosteiro
NamePart
(type = given)
Miguel
DisplayForm
Miguel Mosteiro
Role
RoleTerm
(authority = RULIB)
author
Name
(type = personal)
NamePart
(type = family)
Farach-Colton
NamePart
(type = given)
Martin
Affiliation
Advisory Committee
DisplayForm
Martin Farach-Colton
Role
RoleTerm
(authority = RULIB)
chair
Name
(type = personal)
NamePart
(type = family)
Muthukrishnan
NamePart
(type = given)
S.
Affiliation
Advisory Committee
DisplayForm
S. Muthukrishnan
Role
RoleTerm
(authority = RULIB)
internal member
Name
(type = personal)
NamePart
(type = family)
Steiger
NamePart
(type = given)
William
Affiliation
Advisory Committee
DisplayForm
William Steiger
Role
RoleTerm
(authority = RULIB)
internal member
Name
(type = personal)
NamePart
(type = family)
Bender
NamePart
(type = given)
Michael
Affiliation
Advisory Committee
DisplayForm
Michael Bender
Role
RoleTerm
(authority = RULIB)
outside member
Name
(type = corporate)
NamePart
Rutgers University
Role
RoleTerm
(authority = RULIB)
degree grantor
Name
(type = corporate)
NamePart
Graduate School-New Brunswick
Role
RoleTerm
(authority = RULIB)
school
TypeOfResource
Text
Genre
(authority = marcgt)
theses
OriginInfo
DateCreated
(qualifier = exact)
2007
DateOther
(qualifier = exact);
(type = degree)
2007
Language
LanguageTerm
(authority = ISO 639-3:2007);
(type = text)
English
PhysicalDescription
Form
(authority = marcform)
electronic
InternetMediaType
application/pdf
InternetMediaType
text/xml
Extent
xi, 93 pages
Abstract
(type = abstract)
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.
Note
(type = degree)
Ph.D.
Note
(type = bibliography)
Includes bibliographical references (p. 86-91).
Subject
(authority = RUETD)
Topic
Computer Science
Subject
(authority = ETD-LCSH)
Topic
Sensor networks
Subject
(authority = ETD-LCSH)
Topic
Multisensor data fusion
Subject
(authority = ETD-LCSH)
Topic
Signal processing
Subject
(authority = ETD-LCSH)
Topic
Operator theory
RelatedItem
(type = host)
TitleInfo
Title
Graduate School - New Brunswick Electronic Theses and Dissertations
Identifier
(type = local)
rucore19991600001
Identifier
(type = hdl)
http://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.13483
Identifier
ETD_186
Identifier
(type = doi)
doi:10.7282/T3PZ5985
Location
PhysicalLocation
(authority = marcorg);
(displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Genre
(authority = ExL-Esploro)
ETD doctoral
Back to the top
Rights
RightsDeclaration
(AUTHORITY = GS);
(ID = rulibRdec0006)
The author owns the copyright to this work.
Copyright
Status
Copyright protected
Availability
Status
Open
AssociatedEntity
(AUTHORITY = rulib);
(ID = 1)
Name
Miguel Mosteiro
Role
Copyright holder
Affiliation
Rutgers University. Graduate School-New Brunswick
RightsEvent
(AUTHORITY = rulib);
(ID = 1)
Type
Permission or license
Detail
Non-exclusive ETD license
AssociatedObject
(AUTHORITY = rulib);
(ID = 1)
Type
License
Name
Author Agreement License
Detail
I hereby grant to the Rutgers University Libraries and to my school the non-exclusive right to archive, reproduce and distribute my thesis or dissertation, in whole or in part, and/or my abstract, in whole or in part, in and from an electronic format, subject to the release date subsequently stipulated in this submittal form and approved by my school. I represent and stipulate that the thesis or dissertation and its abstract are my original work, that they do not infringe or violate any rights of others, and that I make these grants as the sole owner of the rights to my thesis or dissertation and its abstract. I represent that I have obtained written permissions, when necessary, from the owner(s) of each third party copyrighted matter to be included in my thesis or dissertation and will supply copies of such upon request by my school. I acknowledge that RU ETD and my school will not distribute my thesis or dissertation or its abstract if, in their reasonable judgment, they believe all such rights have not been secured. I acknowledge that I retain ownership rights to the copyright of my work. I also retain the right to use all or part of this thesis or dissertation in future works, such as articles or books.
Back to the top
Technical
Format
(TYPE = mime);
(VERSION = )
application/x-tar
FileSize
(UNIT = bytes)
490496
Checksum
(METHOD = SHA1)
b86d81c9ca2aea9d75df74dca4e1b5b1d696fd86
ContentModel
ETD
CompressionScheme
other
OperatingSystem
(VERSION = 5.1)
windows xp
Format
(TYPE = mime);
(VERSION = NULL)
application/x-tar
Back to the top
Statistical Profile