Deadline Constrained Scheduling for Data Aggregation in Unreliable Sensor Networks
The authors study the problem of maximizing the aggregated information in a wireless sensor network. They consider a sensor network with a tree topology, where the root corresponds to the sink, and the rest of the network detects an event and transmits data to the sink. They formulate an integer optimization problem that maximizes the aggregated information that reaches the sink under deadline and interference constraints. This framework allows using a variety of error recovery schemes to tackle link unreliability. They show that the optimal solution involves solving a Job Interval Selection Problem (JISP) which is known to be MAX SNP-Hard. They construct a sub-optimal version, and develop a low complexity, distributed optimal solution to this version.