Login | Register

Minimum Latency Aggregation Convergecast in Wireless Sensor Networks

Title:

Minimum Latency Aggregation Convergecast in Wireless Sensor Networks

Gagnon, Jonathan (2014) Minimum Latency Aggregation Convergecast in Wireless Sensor Networks. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Gagnon_MSc_S2014.pdf - Accepted Version
Available under License Spectrum Terms of Access.
2MB

Abstract

In wireless sensor networks, sensor nodes are used to collect data from the environment and send it to a data collection point or a sink node using a convergecast tree. Considerable savings in energy can be obtained by aggregating data at intermediate nodes along the way to the sink.

We study the problem of finding a minimum latency aggregation tree and transmission schedule in wireless sensor networks. This problem is referred to as Minimum Latency Aggregation Scheduling (MLAS) in the literature and has been proven to be NP-Complete even for unit disk graphs. We present a new simpler proof of the NP-Completeness of the MLAS Problem for arbitrary networks and unit disk graphs. We give tight bounds for the latency of aggregation convergecast for grids, tori, and trees. For regular unit interval graphs, we provide an algorithm which is guaranteed to have a latency that is within one time slot of the optimal latency. Finally, for unit interval graphs we give a 2-approximation algorithm to solve the same problem.

For arbitrary graphs, we introduce a new algorithm for building an aggregation tree. Furthermore, we propose two new approaches for building a transmission schedule to perform aggregation on a given tree. We evaluate the performance of our algorithms through extensive simulations on randomly generated graphs and we compare them to the previous state of the art. Our results show that one of our algorithms has a latency that is 38% less than the latency of the previous best algorithm.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Gagnon, Jonathan
Institution:Concordia University
Degree Name:M. Sc.
Program:Computer Science
Date:April 2014
Thesis Supervisor(s):Narayanan, Lata
Keywords:Wireless Sensor Networks, WSN, aggregation convergecast, MLAS, scheduling
ID Code:978478
Deposited By: JONATHAN GAGNON
Deposited On:03 Jul 2014 18:02
Last Modified:18 Jan 2018 17:46
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top