PhD Dissertation Defense: Eunyoung Seo
Tuesday, November 20, 2012
1:00 p.m. Room 2328, AVW Bldg.
For More Information:
Maria Hoo
301 405 3681 mch@umd.edu

ANNOUNCEMENT: PhD Dissertation Defense

Name: Eunyoung Seo

Committee:

Professor Richard J. La, Chair/Advisor

Professor Armand Makowski

Professor Mark Shayman

Professor Sennur Ulukus

Professor Aravind Srinivasan, Dean's Representative

Date/Time: Tuesday, November 20, 2012 at 1 PM

Location: Room 2328, AV Williams Building

Title: Mobile ad hoc networks-its connectivity and routing overhead

This dissertation focuses on a study of network connectivity and routing overhead in mobile ad-hoc networks (MANETs). First part is related to finding the smallest communication range needed for bi-directional connectivity, called the critical transmission range (CTR), with group mobility model. In the second part, we research the smallest communication range of the nodes necessary for no node isolation considering trust constraint in one-hop connectivity. Then, in the third part, under the assumption that nodes employ the CTR for network connectivity in MANETs, overhead required for location information collection and retrieval under geographic routing is studied.

We begin with an investigation of the communication range of the nodes necessary for network connectivity, which we call bi-directional connectivity, in one dimensional case. Unlike in most of existing studies, however, the locations or mobilities of the nodes are correlated through group mobility: Nodes are broken into groups, with each group comprising the same number of nodes, and lie on a unit circle. The locations of the nodes in the same group are not mutually independent, but are instead conditionally independent given the location of the group.

We examine the distribution of the CTR when both the number of groups and the number of nodes in a group are large. We first demonstrate that the CTR exhibits a parametric sensitivity with respect to the space each group occupies on the unit circle. Then, we offer an explanation for the observed sensitivity by identifying what is known as a very strong threshold and asymptotic bounds for CTR.

Related to the first part, we explore the communication range of the nodes necessary for no node isolation where the locations of the nodes are mutually independent and uniformly distributed on a torus. Differently from existing studies, one-hop connectivity of two nodes is determined by both geometric and trust constraints. More specifically, in order to have a communication link for two nodes, they should be within a certain common communication range and satisfy trust requirements, i.e., the trust level of a node exceeds the required trust threshold of the other. Under the given one-hop connectivity, we find the smallest common communication range needed for no nodes to be isolated when the number of nodes is large. Simulation results suggest that the probability of no node isolation and the probability of network connectivity behave very similarly.

In the third part of this dissertation, we study routing overhead due to location information collection and retrieval in MANETs employing geographic routing with no hierarchy. We first provide a new framework for quantifying overhead due to control messages generated to exchange location information. Second, we compute the minimum number of bits required on average to describe the locations of a node, borrowing tools from information theory. This result is then used to demonstrate that the expected overhead is \Omega(n^{1.5} \log(n)), where n is the number of nodes, under both proactive and reactive geographic routing, with the assumptions that (i) nodes' mobility is independent and (ii) nodes adjust their transmission range to maintain network connectivity. Finally, we prove that the minimum expected overhead under the same assumptions is \Theta(n \log(n)).