On-line disjoint path routing for network capacity maximization in energy-constrained ad hoc networks

In this paper we consider on-line disjoint path routing in energy-constrained ad hoc networks. The objective is to maximize the network capacity, i.e. maximize the number of messages routed successfully by the network without any knowledge of future disjoint path connection request arrivals and generation rates. Specifically, in this paper we first present two centralized on-line algorithms for the problem. One is based on maximizing local network lifetime, which aims to minimize the transmission energy consumption, under the constraint that the local network lifetime is no less than γ times of the optimum after the realization of each disjoint path connection request, where γ is constant with 0 < γ ≤ 1. Another is based on the exponential function of energy utilization at nodes, and the competitive ratio of this latter algorithm is also analyzed if admission control mechanism is employed. We then conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and the transmission energy consumption for each disjoint path connection request. The experimental results show that the proposed algorithms outperform those existing algorithms that do not take into account the power load balancing at nodes in terms of maximizing the network capacity. © 2005 Elsevier B.V. All rights reserved.