Back to search
University of Victoria (Canada)
On the complexity of energy-efficient broadcasting in wireless networks
Abstract
dc:description.abstractWe examine the complexity of the minimum-energy broadcast tree problem for wire-less networks. Some versions are known to be NP-complete. We show that the Euclidean version with unlimited power levels is also NP-complete. We assume a broadcast power metric of p(r) = kra where r is the broadcast radius, and k > 0 and a > 2 are properties of the signal propagation medium. We prove NP-completeness using a reduction from the planar 3-satisfiability problem
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2008
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hollemans, Peter Francis
- Advisor dc:contributor.supervisor
-
- King, Valerie
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/1071