Optimal minimum energy routing for cooperative multi-hop wireless networks

This paper investigates the minimum energy routing problem in cooperative multi-hop networks where a single source communicates to a single destination assisted by several relays that accumulate energy or information from retransmissions. This problem is known to be NP-complete if relays are required to decode the source message completely (allcast communications). We extend the problem formulation to also consider the following cases: i) allcast communications with limited accumulative capabilities at relays, ii) unicast communications where relays are only required to decode part of the source message, and iii) the cut-set upper bound. First, for each of these cases, we derive the minimum power-rate ratio for a given path, namely the path weight. We show that this path weight admits a useful duality property which, basically, allows us to compute the weight of a path either as a function of the weight of the intermediate paths between the source and the relays (forward) but also from the weights of the intermediate paths between the relays and the destination (backward). Based on this duality result, we present network scenarios for which we guarantee the optimality of efficient routing protocols based on Dijkstra´s algorithm.