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| and |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 0(|V|~2) and 0(|V|~2log|V|), respectively), and analyze their performance in numerical simulations. They deviate from the optimal energy consumption by only ≈ 11% and ≈7.5%, respectively, and thereby outperform the well-known MIP (O(|V|~2), ≈22% deviation) and many other algorithms significantly.