r-shrink: a heuristic for improving minimum power broadcast trees in wireless networks

Abstract

Broadcasting in wireless networks, unlike wired networks, inherently reaches several nodes with a single transmission. For omni-directional wireless broadcast to a node, all nodes closer will also be reached. This property can be used to compute routing trees which minimize the sum of the transmitter powers. It has been shown that this problem is NP-complete. In this paper, we present the r-shrink procedure, a heuristic for improving the solutions obtained using fast sub-optimal algorithms. Specifically, we focus on the low-complexity BIP algorithm and Prim's minimum spanning tree algorithm and show through extensive simulations that better solutions are obtained almost always, with considerably lower tree power, if the proposed procedure is used to improve the trees generated using these algorithms.