Energy efficient routing in ad hoc networks

The rapid progress in wireless communications and digital electronics has enabled people to make "ubiquitous communications" using battery-based ad hoc networks. In such a network, energy efficient routing has always been an important subject. Past studies have been based on the assumption that the transmitting node consumes power, and that the receiving node does not. This assumption does not hold if acknowledgement is required, or if the ad hoc network has deployed the energy-conservation mode (sleeping mode). In either case, the process of receiving a packet requires the receiving node to send some packets back to the sending node and that will consume energy at the receiving side. When backward energy consumption is present, conventional shortest-path algorithms cannot be directly applied. We studied the Maximum Residual Energy Path (MREP) as an example and proved that for MREP, when backward energy consumption is present in the transmission (i.e. the receiving end consumes energy), finding a legal path that has enough energy for finishing the current transmission task has become NP-hard. We developed a heuristic scheme that allows Dijkstra-like algorithms to include the backward energy. The path found by the heuristic guarantees to be legal. Further, this heuristic method is applied to study various energy efficient routing algorithms and compare their performances, in terms of system life. Simulation results showed that the proposed heuristic schema can improve the performance but is more time consuming