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

  • Pipelines
  • Constraint Programming
  • Branch-and-Bound
  • Mixed Graphs
  • Conflict Graph
  • Shallow Light Tree
  • Precedence Constraints
  • Wireless Sensor Networks
  • Resource Constraints
  • Aggregation Convergecast
  • Scheduling

• Graduation date

  Fall 2013

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3XP6VF0K

• 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.