Download the full-sized PDF of Time and Throughput Efficient Scheduling for Data Gathering in Wireless Sensor NetworksDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Time and Throughput Efficient Scheduling for Data Gathering in Wireless Sensor Networks Open Access


Other title
Conflict Graph
Aggregation Convergecast
Mixed Graphs
Precedence Constraints
Resource Constraints
Shallow Light Tree
Constraint Programming
Wireless Sensor Networks
Type of item
Degree grantor
University of Alberta
Author or creator
de Souza, Evandro
Supervisor and department
Nikolaidis, Ioanis (Computing Science)
Examining committee member and department
Fair, Ivan (Electrical and Computer Engineering)
Kalogeraki, Vana (Athens University of Economics and Business)
MacGregor, Michael (Computing Science)
Harms, Janelle (Computing Science)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
Wireless sensor networks have become a very important tool for monitoring physical and environmental conditions over a wide area. These networks are distributed collections of small sensor nodes. Typically, sensor nodes collect data that must converge to a single sink location, possibly across multiple hops. The data on the way to sink location can be aggregated inside the network. This aggregation convergecast process requires significant coordination between the sensor nodes in the selection of routes, and in the scheduling of the times for data transmission. Both impose considerable restrictions on the communication protocols. In this thesis, we study problems of routing and scheduling in wireless sensor networks when precedence and resource constraints requirements are present. Instead of looking for a schedule and logical topology that have been designed for a generic network or traffic demand, we study collision-free scheduling and logical topology solutions for applications restricted by both constraints. We propose a model for the aggregation convergecast problem using constraint satisfaction to extract characteristics of optimal solutions and to expose the limitations of current solutions in the literature. Using the characteristics observed, we propose the construction of a logical topology that balances the effects of both constraints on the data collection schedule length. A typical solution for the problem encompasses two phases, a initial aggregation tree selection, followed by the node transmission schedule. We show that the scheduling part can be modeled as a Mixed Graph Coloring, and we propose a scheduling solution. Departing from the emphasis on schedule length (delay) minimization, we study the problem of throughput-oriented solutions, where the data collection rate is of higher importance, instead of delay. We relax the restriction that all precedence between nodes must be satisfied within a single collection period, and use pipelining to increase the data collection throughput.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Souza, E. & Nikolaidis, I. Modeling aggregation convergecast scheduling using constraints Proceedings of the 14th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems, ACM, 2011, 231-234Souza, E. & Nikolaidis, I. An exploration of aggregation convergecast scheduling, Ad Hoc Networks, Elsevier, Article in PressSouza, E. & Nikolaidis, I. On the Application of Pipelining in Aggregation Convergecast Scheduling 14th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (IEEE WoWMoM 2013), 2013

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1399898
Last modified: 2015:10:22 06:27:05-06:00
Filename: Evandro_de_Souza-Fall2013.pdf
Original checksum: 1428f4675c5511fefc9d7db6cf1f330d
Well formed: false
Valid: false
Status message: No document catalog dictionary offset=0
File title: Time and Throughput Efficient Scheduling for Data Gathering in Wireless Sensor Networks
File author: Evandro de Souza
Activity of users you follow
User Activity Date