RUcore: Rutgers University Community Repository
Algorithms and LP-duality based lower bounds in ad-hoc radio networks
Descriptive
TitleInfo
(displayLabel = Citation Title);
(type = uniform)
Title
Algorithms and LP-duality based lower bounds in ad-hoc radio networks
Name
(ID = NAME001);
(type = personal)
NamePart
(type = family)
Fernandes
NamePart
(type = given)
Rohan Jude
DisplayForm
Rohan Jude Fernandes
Role
RoleTerm
(authority = RUETD)
author
Name
(ID = NAME002);
(type = personal)
NamePart
(type = family)
Farach-Colton
NamePart
(type = given)
Martin
Affiliation
Advisory Committee
DisplayForm
Martin Farach-Colton
Role
RoleTerm
(authority = RULIB)
chair
Name
(ID = NAME003);
(type = personal)
NamePart
(type = family)
Saks
NamePart
(type = given)
Michael
Affiliation
Advisory Committee
DisplayForm
Michael Saks
Role
RoleTerm
(authority = RULIB)
internal member
Name
(ID = NAME004);
(type = personal)
NamePart
(type = family)
S.
NamePart
(type = given)
Muthukrishnan
Affiliation
Advisory Committee
DisplayForm
Muthukrishnan S.
Role
RoleTerm
(authority = RULIB)
internal member
Name
(ID = NAME005);
(type = personal)
NamePart
(type = family)
Bender
NamePart
(type = given)
Michael
Affiliation
Advisory Committee
DisplayForm
Michael Bender
Role
RoleTerm
(authority = RULIB)
outside member
Name
(ID = NAME006);
(type = corporate)
NamePart
Rutgers University
Role
RoleTerm
(authority = RULIB)
degree grantor
Name
(ID = NAME007);
(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
English
PhysicalDescription
Form
(authority = marcform)
electronic
InternetMediaType
application/pdf
InternetMediaType
text/xml
Extent
xii, 75 pages
Abstract
An Ad-hoc Radio Network consists of nodes with no knowledge of its neighbors and knowledge of its own ID and n, the size of the network. In this thesis, we present algorithms and lower
bounds related to ad-hoc network initialization. Sensor networks are an important type of ad-hoc Radio Network, consisting of sensor nodes - very weak computers. Usually sensor nodes get distributed at random on a surface where they must wake up and initialize into a Radio Network. Due to the strict restrictions on sensor node
capabilities, it is difficult to find efficient solutions to even basic problems.
In our first result, 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 then give a Weak Sensor Model-compatible protocol for finding such graphs that runs in O(log2 n) time with high probability.
We then present new lower bounds for collision-free transmissions in Radio Networks. Our main result is a tight lower bound of
Omega(log n log (1/epsilon)) on the
epsilon-failure-probability time required by a fair randomized protocol to achieve a clear transmission in a one-hop network. We also prove a new lower bound for the important
multi-hop setting of nodes distributed as a connected Random Geometric Graph. In this setting, we prove a lower bound of
Omega(loglog n log (1/epsilon)) on fair protocols for clear transmissions in the well-studied case of sensor nodes distributed uniformly at random with enough nodes to ensure connectivity, and thus for more complicated problems such as MIS.
In the Wake-Up problem, we have a multi-hop, ad-hoc radio network with locally synchronized nodes. Each node either wakes up spontaneously or is activated when it receives a signal from a neighboring node. All nodes have knowledge of n, the number of nodes in the network and the diameter D. We present a new lower bound of Omega(D log n log (1/epsilon)) on the epsilon-failure-probability time taken by a fair protocol to wake up the entire network. Our lower bound is tight for high-probability protocols when D in mathcal O (n/log 2 n).
bounds related to ad-hoc network initialization. Sensor networks are an important type of ad-hoc Radio Network, consisting of sensor nodes - very weak computers. Usually sensor nodes get distributed at random on a surface where they must wake up and initialize into a Radio Network. Due to the strict restrictions on sensor node
capabilities, it is difficult to find efficient solutions to even basic problems.
In our first result, 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 then give a Weak Sensor Model-compatible protocol for finding such graphs that runs in O(log2 n) time with high probability.
We then present new lower bounds for collision-free transmissions in Radio Networks. Our main result is a tight lower bound of
Omega(log n log (1/epsilon)) on the
epsilon-failure-probability time required by a fair randomized protocol to achieve a clear transmission in a one-hop network. We also prove a new lower bound for the important
multi-hop setting of nodes distributed as a connected Random Geometric Graph. In this setting, we prove a lower bound of
Omega(loglog n log (1/epsilon)) on fair protocols for clear transmissions in the well-studied case of sensor nodes distributed uniformly at random with enough nodes to ensure connectivity, and thus for more complicated problems such as MIS.
In the Wake-Up problem, we have a multi-hop, ad-hoc radio network with locally synchronized nodes. Each node either wakes up spontaneously or is activated when it receives a signal from a neighboring node. All nodes have knowledge of n, the number of nodes in the network and the diameter D. We present a new lower bound of Omega(D log n log (1/epsilon)) on the epsilon-failure-probability time taken by a fair protocol to wake up the entire network. Our lower bound is tight for high-probability protocols when D in mathcal O (n/log 2 n).
Note
(type = degree)
Ph.D.
Note
(type = bibliography)
Includes bibliographical references (p. 70-73).
Subject
(ID = SUBJ1);
(authority = RUETD)
Topic
Computer Science
Subject
(ID = SUBJ2);
(authority = ETD-LCSH)
Topic
Sensor networks
Subject
(ID = SUBJ3);
(authority = ETD-LCSH)
Topic
Radio frequency
RelatedItem
(ID = RELATEDITEM001);
(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.15842
Identifier
(type = FEDORA_PID)
rutgers-lib:22819
Identifier
ETD_265
Location
PhysicalLocation
(authority = marcorg);
(displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier
(type = doi)
doi:10.7282/T35D8S8X
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
Rohan Fernandes
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)
577536
Checksum
(METHOD = SHA1)
3fe316a46b59d1d52bdc87b2e00efdb9709fe010
ContentModel
ETD
CompressionScheme
other
OperatingSystem
(VERSION = 5.1)
windows xp
Format
(TYPE = mime);
(VERSION = NULL)
application/x-tar
Back to the top
Statistical Profile