Back to search

West Virginia University

Exploiting random walks for robust, scalable, structure-free data aggregation and routing in mobile ad-hoc networks (MANETs)

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Lane Department of Computer Science and Electrical Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nakagawa, Masahiro
Contributors dc:contributor
  • Vinod K Kulathumani
  • Yaser Fallah
  • Katerina Goseva-Poptojanova
  • Ashish Nimbarte
  • YangFang Ye

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Nakagawa, Masahiro. Exploiting random walks for robust, scalable, structure-free data aggregation and routing in mobile ad-hoc networks (MANETs). Dissertation thesis, https://doi.org/10.33915/etd.6287