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

  • Author / Creator
    de Souza, Evandro
  • 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.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Nikolaidis, Ioanis (Computing Science)
  • Examining committee members and their departments
    • Fair, Ivan (Electrical and Computer Engineering)
    • MacGregor, Michael (Computing Science)
    • Kalogeraki, Vana (Athens University of Economics and Business)
    • Harms, Janelle (Computing Science)