On the Interaction Between Scheduling and Compressive Data Gathering in Wireless Sensor Networks

Compressive data gathering (CDG) has emerged as a useful method for collecting sensory data in large scale sensor networks; this technique is able to reduce global scale communication cost without introducing intensive computation, and is capable of extending the lifetime of the entire sensor network by balancing the aggregation and forwarding load across the network. With CDG, multiple forwarding trees are constructed, each for aggregating a coded or compressed measurement, and these measurements are collected at the sink for recovering the uncoded transmissions from the sensors. This paper studies the problem of constructing forwarding trees for collecting and aggregating sensed data in the network under the realistic physical interference model. The problem of gathering tree construction and link scheduling is addressed jointly, through a mathematical formulation, and its complexity is underlined. Our objective is to collect data at the sink with both minimal latency and fewer transmissions. We show the joint problem is NP-hard and owing to its complexity, we present a decentralized method for solving the tree construction and the link scheduling subproblems. Our link scheduling subproblem relies on defining an interference neighbourhood for each link and co-ordinating transmissions among network links to control the interference. We prove the correctness of our algorithmic method and analyse its performance. Numerical results are presented to compare the performance of the decentralized solution with the joint model as well as prior work from the literature.