Date of Graduation

2016

Document Type

Dissertation

Degree Type

PhD

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

Vinod K Kulathumani

Committee Co-Chair

Yaser Fallah

Committee Member

Katerina Goseva-Poptojanova

Committee Member

Ashish Nimbarte

Committee Member

YangFang Ye

Abstract

The focus of this thesis is on the design of scalable data aggregation protocols for Mobile Ad-hoc Networks (MANETs). Data aggregation Protocols that rely on network structures such as trees or backbones are not well suited for MANETs because the underlying topology of MANETs is constantly changing. On the other hand, unstructured techniques such as flooding and gossiping have a high messaging overhead and take a long time to finish. Therefore, in this thesis, we explore the use of random walks as a structure-free alternative for data aggregation in MANETs.;The basic idea is to introduce one or more tokens that successively visit each node in a MANET by executing a random walk and compute the aggregate state. While random walks are simple, robust and overhead-free, plain random walks tend to be slow in visiting all nodes because the token can get stuck in regions of already visited nodes. Therefore, we first introduce self-repelling random walks (SRRW) in which at each step, the token chooses a neighbor that has been visited the least number of times. While SRRW significantly speeds up random walks in the initial stages, towards the end a slowdown is observed when a significant fraction of nodes are already visited. To address this shortcoming, we then develop two complementary strategies that speed up data aggregation.;First, we introduce gradient biased random walks (a pull-based strategy) where short temporary multi-hop gradients are used to pull the tokens toward unvisited node. We prove that gradient biased random walks achieve a cover time of O(N) and message overhead of O(NlogN) where N is the number of nodes in the network. Next, we introduce a push-based strategy in which self-repelling random walks are complemented by a single step push phase before the random walk phase, in which each node broadcasts its information to its neighbors. We show that this small push goes a long way in speeding up data aggregation. Push based random walks finish data aggregation in O(N) message and time. Finally, we describe hierarchical extension of the push-based protocol which can produce multi-resolution aggregates at each node using only O(NlogN) messages.;All our results are validated using simulations in ns-3 in networks ranging from 100 to 4000 nodes under different network densities, node speed and mobility models.

Download

Share

COinS