Semester

Spring

Date of Graduation

2017

Document Type

Problem/Project Report

Degree Type

MS

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

Brian Woerner

Committee Member

Matthew Valenti

Abstract

ABSTRACT Analysis of Multi-Resolution Data Aggregation using Push-assisted Random Walks in Mobile Ad-hoc Networks (MANETs) Sowmya Srinivasapura Devaraja Data Aggregation in Mobile Ad-hoc Network (MANET) has proven challenging because of changing topology. Structure-based models like tree-based, cluster-based and chain-based have high maintenance cost. In earlier works, different forms of biased random walks have been verified to be effective without need for structure maintenance. The key idea in the protocol was to use one or more tokens that are circulated using biased random walks to effectively compute the data aggregation. One such protocol is EZ-AG that uses "Push-assisted Self-Repelling Random Walks". A self-repelling random walk of a token on a graph is one in which at each step, the token moves to a neighbor that has been visited least often. While self-repelling random walks visit all nodes in the network much faster than plain random walks, they tend to slow down when most of the nodes are already visited. It's verified that a single step push phase at each node can significantly speed up the aggregation and eliminate the slow down. Results have been verified that EZ-AG achieves aggregation in only O (N) time and messages. When the network is quite large, obtaining only one aggregate may not be sufficient. It will be more useful to provide distance-sensitive multi-resolution aggregates of data. The contribution in this project is, we have analyzed the Hierarchical EZ-AG proposed to provide multi-resolution results. We show that aggregates for nearby regions are obtained at faster rate in comparison to the farther region. The idea is to introduce the tokens in the network at distinct levels, execute EZ-AG protocol and obtain localized data aggregation output at distinct levels. Existing techniques for hierarchical aggregations require O (N log5.4 (N)) messages. Hierarchical EZ-AG outperforms these techniques by aggregating with only O (N log (N)) messages. We evaluate the performance of hierarchical EZ-AG considering message overhead, token messages, number of aggregations at distinct levels, node speed and mobility. Our results are validated using simulations in network simulator, ns-3 for network ranging from 100 to 4000 nodes under different node speeds and mobility models.

Download

Share

COinS