Minimum-energy broadcast in all-wireless networks

23 September 2002

proceedings article
Published by Association for Computing Machinery (ACM)

p. 172-182
https://doi.org/10.1145/570645.570667

Abstract

In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed

Keywords

This publication has 15 references indexed in Scilit:

Constructing minimum-energy broadcast trees in wireless ad hoc networks
Published by Association for Computing Machinery (ACM) ,2002
Optimizing sensor networks in the energy-latency-density design space
IEEE Transactions on Mobile Computing, 2002
Geography-informed energy conservation for Ad Hoc routing
Published by Association for Computing Machinery (ACM) ,2001
Toward self-organized mobile ad hoc networks: the terminodes project
IEEE Communications Magazine, 2001
PicoRodio supports ad hoc ultra-low power wireless networking
Computer, 2000
Wireless integrated network sensors
Communications of the ACM, 2000
Next century challenges
Published by Association for Computing Machinery (ACM) ,1999
Minimum energy mobile wireless networks
IEEE Journal on Selected Areas in Communications, 1999
A review of current routing protocols for ad hoc mobile wireless networks
IEEE Wireless Communications, 1999
Planar Formulae and Their Uses
SIAM Journal on Computing, 1982