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 8, 11 (2009), 5490-5499.
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.
Go to next publication
Return to Richard Brent's index page