Login | Register

Optimal Schedules for Data Gathering in Wireless Sensor Networks


Optimal Schedules for Data Gathering in Wireless Sensor Networks

Bakshi, Mahesh (2017) Optimal Schedules for Data Gathering in Wireless Sensor Networks. PhD thesis, Concordia University.

[thumbnail of Bakshi_PhD_F2017.pdf]
Text (application/pdf)
Bakshi_PhD_F2017.pdf - Accepted Version
Available under License Spectrum Terms of Access.


Wireless Sensor Networks (WSNs) are widely used for target monitoring: sensors monitor a set of targets, and forward the collected or aggregated data using multi-hop routing to the same location, called the sink. The resulting communication scheme is called ConvergeCast or Aggregated ConvergeCast.

Several researchers studied the ConvergeCast and the Aggregated ConvergeCast, as to produce the shortest possible schedule that conveys all the packets or a packet aggregation to the sink. Nearly all proposed methods proceed in two steps, first the routing, and then the scheduling of the packets along the routes defined in the first step.

The thesis is organized around four contributions. The first one is an improvement of the previous mathematical models that outputs (minimum-sized) multi-set of transmission configurations (TCs), in which a transmission configuration is defined as a set of links that can transmit concurrently. Our model allows the transmission of several packets per target, in both single-path and multi-path settings; we give two new heuristics for generating new improved transmission configurations. While such models go beyond the routing step, they do not specify an ordering over time of the configurations. Consequently, the second contribution consists of several algorithms, one exact and several heuristics, for ordering the configurations. Our results show that the approach of scheduling when restricted to a tree generated by the first contribution significantly outperforms the ordering of configurations of TC-approach for single-rate, single packet per sensor traffic patterns, but the TC approach gives better results for multi-rate traffic and when there are a large number of packets per sensor.

In the last two contributions, we propose an exact mathematical model that takes care, in a single phase, of the routing and the scheduling, for the ConvergeCast and the aggregated ConvergeCast problem. They both correspond to decomposition models in which not only we generate transmission configurations, but an ordering of them.

We performed extensive simulations on networks with up to 70 sensors for both ConvergeCast and Aggregated ConvergeCast, and compared our one phase results with one of the best heuristics in the literature.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Bakshi, Mahesh
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science
Date:8 June 2017
Thesis Supervisor(s):Jaumard, Brigitte and Narayanan, Lata
ID Code:982608
Deposited On:08 Nov 2017 20:59
Last Modified:18 Jan 2018 17:55
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top