A Simple Yet Effective Diversifying Improvement of the Minimum Power Multicast Tree Algorithms in Wireless Ad Hoc Networks

摘要

In this paper, we present an iterated algorithm framework that can be implemented with heuristics in the literature for the minimum energy multicasting problem in wireless ad hoc networks to improve the solution quality. We investigate three iterated algorithm implementations, IBIP, IOMEGa, ISOR, that are based on BIP, OMEGa, SOR. The algorithms run iterations to find better solutions of the problem and in each iteration, fixing the source node's transmission power, the algorithm finds the intermediate solutions. And after all the iterations, the algorithm prunes the broadcast tree into a multicast tree and gives the output of the best solution so far. By fixing the source node's transmission power we can achieve the diverse solution search without hurting the original algorithm's theoretical performance bound. The experimental results confirm that the iterated algorithms significantly improve the solution quality.