Maximizing Information in Unreliable Sensor Networks Under Deadline and Energy Constraints
The authors study the problem of maximizing the information in a wireless sensor network with unreliable links. 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 a combinatorial optimization problem that maximizes the information that reaches the sink under deadline, energy, and interference constraints. This framework allows using a variety of error recovery schemes to tackle link unreliability. They show that this optimization problem is NP-hard in the strong sense when the input is the maximum node degree of the tree.