Minimum power broadcast trees for wireless networks: integer programming formulations

Abstract

Wireless multicast/broadcast sessions, unlike wired networks, inherently reach several nodes with a single transmission. For omnidirectional wireless broadcast to a node, all nodes closer will also be reached. Heuristic algorithms for constructing the minimum power tree in wireless networks have been proposed by Wieselthier et al. and Stojmenovic et al. Recently, an evolutionary search procedure has been proposed by Marks et al. In this paper, we present three different integer programming models which can be used for an optimal solution of the minimum power broadcast/multicast problem in wireless networks. The models assume complete knowledge of the distance matrix and is therefore most suited for networks where the locations of the nodes are fixed.