RUcore Resource Object
RUcore Resource Object
PDF-1(561.73 KB)
Uniform TitleAlgorithms and LP-duality based lower bounds in ad-hoc radio networks
NameFernandes, Rohan Jude (author), Farach-Colton, Martin (chair), Saks, Michael (internal member), S., Muthukrishnan (internal member), Bender, Michael (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2007
Date Created2007
SubjectComputer Science,
Sensor networks,
Radio frequency
DescriptionAn 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).
NotePh.D.
NoteIncludes bibliographical references (p. 70-73).
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.15842
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.