The Path-Based Minimum Power Broadcast Problem in Static Wireless Networks

The crucial design challenge in broadcasting is how to save energy, because each individual node only has a small battery as a power source. Thus, the objective of this paper is to find the optimal radii range for each node in static wireless networks so that the total power consumption can be minimized. The problem is formulated as a minimum-power broadcast tree constructed based on paths, instead of links or nodes. Since this problem is NP-complete, we adopt Lagrangian Relaxation (LR) to decompose it and independently solve the sub-problems. The LR dual-mode problem ensures the objective lower bound value. The primal-mode problem is solved via our proposed approximation heuristic, which takes prompts from a set of LR multipliers, to obtain the upper bound´s objective value. We present experimental results from randomly generated networks and show that our proposed algorithm saves more than 30%, 5%, and 10% energy compared to the Prim´s minimum spanning tree (PMST), the broadcast incremental power (BIP), and another proposed greedy incremental broadcast tree (GIBT) algorithms, respectively.