Preprint: pdf (200K).
Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, and assuming that each terminal node has a message to share with each other node, the problem is to build a shared multicast tree spanning all terminal nodes, such that the total energy comsumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.
Go to next publication
Return to Richard Brent's index page