Analysis and Computational Study of Several Integer Programming Formulations for Minimum-Energy Multicasting in Wireless Ad Hoc Networks

摘要

A multicast session in a wireless ad hoc network concerns routing messages from a source to a set of destination devices. Transmitting messages consumes energy at the source and intermediate devices of the session. Since a battery is the only energy source in many applications of wireless ad hoc networks, energy efficiency is an important performance measure of multicasting. In this paper, we present and analyze integer programming models for the problem of minimizing the total energy required by multicasting. We start from a straightforward multicommodity flow model, which is strengthened by a more efficient representation of transmission power. Further strengthening is accomplished by lifting the capacity constraints of the model. We then present cut-based models for the problem, and prove, from a bounding standpoint, the equivalence in strength between these models and their flow-based counterparts. By expanding the underlying graph, we show that the problem can be transformed into finding a minimum Steiner arbores-cence. The expanded graph arises also in the separation procedure for solving one of the cut-based models. In addition to a theoretical analysis of the relation between various models, we perform extensive computational experiments to study the numerical strengths of these models and their efficiency in solving the problem.