Diversity backpressure routing with mutual information accumulation in wireless ad-hoc networks

We suggest and analyze algorithms for routing in ad-hoc networks that exploit mutual-information accumulation at receiving nodes, and are capable of routing multiple data streams (commodities) when only mean channel state information is present, and that only locally. The algorithm is a generalization of the DIVBAR algorithm, which in turn is based on backpressure routing. Packets are transmitted by each node on the links seeing the largest "backpressure", a measure for the differential queue lengths for a specific commodity at the considered nodes times the success probability for packets on that link. In contrast to traditional DIVBAR, nodes store and exploit partially received packets, thus increasing the probability of successful reception at retransmission, where the information is stored in separate "partial queues" at each node. We present two variants of our algorithm: DIVBAR-RMIA, which clears the partial queues whenever a packet is firstly decoded by one or more receiving nodes; DIVBAR-MIA, which retains the information about a specific packet in the partial queues until the packet has reached its destination. We prove that DIVBAR-RMIA performs strictly better than conventional DIVBAR (under some mild assumptions about the channel states), and that DIBVAR-MIA performs at least as well as DIVBAR-RMIA. Simulations not only confirm these results, but also demonstrate the impact of packet entropy on the achievable throughput.