Lookahead Expansion Algorithm for Minimum Power Multicasting in Wireless Ad Hoc Networks

Outlet Title

Wireless Algorithms, Systems, and Applications 4th International Conference

Document Type


Publication Date



In this paper, we present a lookahead expansion algorithm (named as Shrinking and Lookahead Expansion, SLE for short) for minimum power multicast tree problem in wireless ad hoc networks. SLE adopts the powerful shrinking process from our previous work, SOR (Shrinking Overlapped Range) algorithm, and adds an intelligent lookahead process to further improve the solution quality. The lookahead process (called as lookahead expansion) expands the intermediate tree to a feasible tree by adding transmissions with minimum power, one by one. The algorithm maintains the found feasible tree with the minimum power sum in addition to the intermediate tree which is not feasible until the end. This lookahead process generates the effective diversification of the solution search space. The computational results strongly support the solid and outstanding performance of SLE owing to the lookahead process.