We investigate optimal routing and scheduling strategies for multi-hop
wireless networks with rateless codes. Rateless codes allow each node of the
network to accumulate mutual information with every packet transmission. This
enables a significant performance gain over conventional shortest path routing.
Further, it also outperforms cooperative communication techniques that are
based on energy accumulation. However, it creates complex and combinatorial
networking decisions concerning which nodes participate in transmission, and
which decode ordering to use. We formulate the general problem as a
combinatorial optimization problem and then make use of several structural
properties to simplify the solution and derive an optimal greedy algorithm.
Although the reduced problem still has exponential complexity, using the
insight obtained from the optimal solution to a line network, we propose two
simple heuristics that can be implemented in polynomial time in a distributed
fashion and compare them with the optimal solution. Simulations suggest that
both heuristics perform very close to the optimal solution over random network
topologies.