Center-oriented algorithms for the minimum energy broad and multicast problem in wireless ad hoc networks

Quickly finding low-energy multicast routings is vital for a wireless system’s energy efficiency. Therefore, key aspects of heuristics for the minimum energy multicast problem (MEMP) are low time complexity (measured in the numbers |V||V| and |A||A| of networking devices and their possible power assignments, respectively) and low deviation from the optimal energy consumption. Following a center-oriented approach, we develop the STSuS and STESuS algorithms (time complexity O(|V|2)O(|V|2) and O(|V|2log|V|)O(|V|2log|V|), respectively), and analyze their performance in numerical simulations. They deviate from the optimal energy consumption by only ≈11%≈11% and ≈7.5%≈7.5%, respectively, and thereby outperform the well-known MIP (O(|V|2)O(|V|2), ≈22% deviation) and many other algorithms significantly.