Efficient sensor data collection with dynamic traffic patterns

• Main Author: Zhao, Wenbo
• Other Authors: Tang Xueyan
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering::Mathematics of computing::Numerical analysis
• Online Access: http://hdl.handle.net/10356/60752
• Institution: Nanyang Technological University

In a typical monitoring application, sensor nodes periodically sample the physical world and their acquired data are continuously collected by a base station. In continuous sensor data collection, due to the energy conservation concerns or the nature of the sensor applications, not all data are reported to the base station at each sampling interval. Decisions of what data to report are driven by data itself and can only be made after the data are acquired by sensor nodes. As a result, the traffic pattern in the network often changes over time in an unpredictable manner. This thesis studies the construction of TDMA schedules and routing structures to efficiently handle dynamic traffic patterns in continuous sensor data collection. In the first part of the thesis, we propose a novel TDMA schedule that is capable of efficiently collecting sensor data for any network traffic pattern and is thus well suited to continuous data collection with dynamic traffic patterns. In the proposed schedule, the energy consumed by sensor nodes for any traffic pattern is very close to the minimum required by their workloads given in the traffic pattern. The schedule also allows the base station to conclude data collection as early as possible according to the traffic load, thereby reducing the latency of data collection. We present a distributed algorithm for constructing the proposed schedule. We develop a mathematical model to analyze the performance of the proposed schedule. We also conduct simulation experiments to evaluate the performance of different schedules using real-world data traces. Both the analytical and simulation results show that, compared with existing schedules that are targeted on a fixed traffic pattern, our proposed schedule significantly improves the energy efficiency and time efficiency of sensor data collection with dynamic traffic patterns. In the second part of the thesis, we investigate efficient routing structures to extend the network lifetime for continuous sensor data collection with dynamic traffic patterns. Both the tree and DAG (Directed Acyclic Graph) routing structures are explored. We develop a performance model to analyze the energy consumption of sensor nodes in tree-based routing structures and apply the model to the construction of the routing tree to optimize the network lifetime. We formulate the problem of finding the lifetime-optimal DAG routing structure as a mixed integer programming problem and design an efficient greedy algorithm to compute a near-lifetime-optimal DAG structure. We further propose two methods to carry out data collection based on the DAG structure constructed. The DAG decomposition method decomposes the DAG into a set of trees and chooses one of the trees as the routing structure for data collection at each sampling interval. The DAG-based scheduling method directly constructs a TDMA schedule on the DAG structure for data collection. We conduct simulation experiments to evaluate the performance of the proposed methods using real-world data traces. The results show that both of our proposed DAG decomposition and DAG-based scheduling methods outperform the method of building a single routing tree for data collection.