Minimum power broadcast trees for wireless networks: optimizing using the viability lemma

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. An algorithm for constructing the minimum power tree in wireless networks was first proposed by Wieselthier et al. (2000). The broadcast incremental power (BIP) algorithm suggested by them is a "node-based" minimum-cost tree algorithm for wireless networks. We propose an alternate search based paradigm wherein minimum-cost trees in wireless networks are found through a search process. Two computationally efficient procedures for checking the feasibility (viability) of a solution in the search space are presented. A straightforward procedure for initializing the search using stochastically generated trees is also proposed.