A Fast Mixed Integer Programming Formulation for Minimum-Power Broadcasting in Wireless Networks

Broadcasting means the distribution of packets from a certain source to all other hosts. One of the possible efficient implementations of broadcasting is to construct a spanning tree rooted at a given source such that each host can receive a copy of the broadcast packet originating from the source. Since the operations of most hosts in wireless networks mainly rely on battery power, in this paper the authors will focus on the issue of establishing a minimum-power broadcast tree in wireless networks, which has been proven to be NP-complete. Based on the concepts of integer programming and network flow, several mixed integer programming formulations with the capability of constructing a minimum-power broadcast tree have been proposed.