Node-disjoint path routing in wireless networks: tradeoff between path lifetime and total energy

Survivability and lifetime are two important issues related to routing in wireless ad-hoc networks. Routing using node-disjoint paths enhances both survivability and data confidentiality. An elegant polynomial time algorithm has been reported recently that can compute node-disjoint paths connecting a source node to a destination node with minimum total energy. However, the problem of computing a pair of node-disjoint paths connecting a source node to a destination node with a lifetime no smaller than a given threshold has not been studied before. In this paper, we present efficient algorithms for computing a pair of node-disjoint paths connecting a source node to a destination node which either minimizes energy under lifetime constraint or maximizes lifetime under energy consumption constraint. We study the tradeoffs between path lifetime and total energy consumption in node-disjoint path routing and their effects on network throughput and network lifetime. Our preliminary simulation results show that routing with both path lifetime and total energy consumption considerations leads to significantly better network throughput and network lifetime.