Energy-efficient broadcast and multicast algorithms in wireless ad hoc networks

This thesis systematically explores two fundamental classes of energy-efficient broadcast/multicast problem: the BPM/MPM (Broadcast/Multicast Power Minimization) problem and the BLM/MLM (Broadcast/Multicast Lifetime Maximization) problem. For the first class of problem, we have developed a general analytical MILP (Mixed Integer Linear Programming) model for the MPM problem in an ad hoc network with adaptive antennas, and also implemented a group of polynomial-time algorithms practically to handle significantly large networks for which the MILP model may not be computationally efficient. For the second problem, we have first used theoretical analysis to derive two polynomial-time optimal algorithms for the MLM/BLM problem in the omni-directional antenna scenarios. We then study the same problem with directional antennas, and conjecture that this problem is NP-hard. Based on the same analytical model, we have developed a constraint formulation for the MLM/BLM problem in terms of MILP, and also implemented a group of polynomial-time algorithms practically. Finally, we consider the same problems in mobile ad hoc networks (MANETs) and propose several distributed algorithms. Several localized operations are presented for our distributed algorithms, in which each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes. Through extensive simulation study, we show that these distributed algorithms are very efficient both in terms of energy (power or lifetime) and operation overhead