Numerous studies on energy-efficient routing for multihop ad hoc networks (MANET) look at extending battery life by minimizing the cost at the transmitting node. In this paper, we study the complexity of energy-efficient routing when the energy cost of receiving packets is also considered. We first prove that, surprisingly, even when all nodes transmit at the same power, finding a simple unicast path that guarantees enough remaining energy locally at each node in the network then becomes an NP-complete problem. Hence we propose several heuristics based on Dijkstra's shortest path algorithm in which we integrate the notion of remaining energy in order to satisfy flow requirements. We show with several simulations that these heuristics not only allow the computation of routes that save energy of nodes with low battery but also allow the network to handle more flows
['Géraud Allard', 'Bernard Mans']
Reducing the energy drain in multihop ad hoc networks