Online Multicasting for Network Capacity Maximization in Energy-Constrained Ad Hoc Networks

Abstract

In this paper, we present new algorithms for online multicast routing in ad hoc networks where nodes are energy-constrained. The objective is to maximize the total amount of multicast message data routed successfully over the network without any knowledge of future multicast request arrivals and generation rates. Specifically, we first propose an online algorithm for the problem based on an exponential function of energy utilization at each node. The competitive ratio of the proposed algorithm is analyzed if admission control of multicast requests is permitted. We then provide another online algorithm for the problem, which is based on minimizing transmission energy consumption for each multicast request and guaranteeing that the local network lifetime is no less than 7 times of the optimum, where 7 is constant with 0 < γ ≤ 1. We finally conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and transmission energy consumption for each multicast request. The experimental results clearly indicate that, for online multicast routing in ad hoc wireless networks, the network capacity is proportional to the network lifetime if the transmission energy consumption for each multicast request is at the same time minimized. This is in contrast to the implication by Kar et al. that the network lifetime is proportional to the network capacity when they considered the online unicast routing by devising an algorithm based on the exponential function of energy utilization at each node.