Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks

In this paper, we present three schemes to solve minimum total energy broadcasting problem in wireless ad hoc networks based on an efficient IP (integer programming) subproblem technique. Due to its NP-hardness, many heuristics have been studied. However, the heuristics in the literature suffer from coarse performance ratio. It is important to have knowledge of the optimal solution structure in order to develop more efficient heuristics and algorithms. We present one IP formulation and two iterative algorithms which make use of relaxed IPs to solve subproblems. The computational results show that our approaches outperform other techniques in the literature.