Maximizing Information in Unreliable Sensor Networks Under Deadline and Energy Constraints

Abstract-We study the problem of maximizing the information in a wireless sensor network with unreliable links. We 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. We 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. We show that this optimization problem is NP-hard in the strong sense when the input is the maximum node degree of the tree. We then propose a dynamic programming framework for solving the problem exactly, which involves solving a special case of the Job Interval Selection Problem (JISP) at each node. Our solution has a polynomial time complexity when the maximum node degree is O(log N ) in a tree with N nodes. For trees with higher node degrees, we further develop a sub-optimal solution, which has low complexity and allows distributed implementation. We investigate tree structures for which this solution is optimal to the original problem. The efficiency of the sub-optimal solution is further demonstrated through numerical results on general trees