Minimum-Energy Multicasting
234. Weifa Liang,
Richard P. Brent, Yinlong Xu and Qingshan Wang,
Minimum-energy all-to-all multicasting in wireless ad hoc
networks,
IEEE Transactions on Wireless Communications , to appear
(accepted 4 August 2009).
Preprint:
pdf (200K).
Abstract
A wireless ad hoc network consists of mobile nodes that are powered by
batteries. The limited battery lifetime imposes a severe constraint on the
network performance; energy conservation in such a network is of
paramount importance, and energy efficient operations are critical to
prolong the lieftime of the network. All-to-all multicasting is one
fundamental operation in wireless ad hoc networks; in this paper we focus on
the design of energy-efficient routing algorithms for this operation.
Specifically, we consider the following minimum-energy all-to-all
multicasting problem.
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.
Return to Richard Brent's index page