University of Patras
Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα
Abstract
dc:descriptionIn this dissertation we focus on issues related to energy consumption in wireless networks. We examine both ad hoc wireless networks where we assume that there is no wired infrastructure and networks where antennas are wired through a traditional wired backbone network but they transmit messages to the users using wireless means. In the first case we consider networks where the distance function can be symmetric or asymmetric edge cost functions can be used to model medium abnormalities or batteries with different energy levels. We prove results concerning the NP hardness of computing the optimal solution or in some cases even an approximate solution and also present upper bounds on the approximation ratio of several polynomial time algorithms. In the case where the antennas are connected through a wired backbone network we consider a clustering problem. We present an optimal polynomial time algorithm for the special case when points are located on a line. We also present NP hardness results concerning special cases of the problem in the case of 2 or more dimensions. Finally we conclude with a polynomial time approximation scheme (PTAS).
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2007
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kanellopoulos, Panagiotis
- Κανελλόπουλος, Παναγιώτης
Subjects
dc:subject × 10Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26749