Στην παρούσα διδακτορική διατριβή ασχολούμαστε με ζητήματα ελαχιστοποίησης της κατανάλωσης ενέργειας που ανακύπτουν σε ασύρματα δίκτυα. Εξετάζουμε τόσο την περίπτωση ασυρμάτων δικτύων τύπου ad hoc όσο και την περίπτωση όπου υπάρχει ένα σταθερό ενσύρματο δίκτυο το οποίο συνδέει τους σταθμούς εκπομπής, οι οποίοι χρησιμοποιούν ασύρματα μέσα προκειμένου να μεταδώσουν μηνύματα στους χρήστες.
Στην πρώτη κατηγορία, μελετούμε τόσο περιπτώσεις όπου η συνάρτηση κόστους στις ακμές είναι συμμετρική, όσο και περιπτώσεις όπου δεν ισχύει αυτή η υπόθεση. Εξετάζουμε επιπλέον προβλήματα που προκύπτουν όταν θεωρούμε ότι οι σταθμοί βρίσκονται σε κάποιον Ευκλείδειο χώρο και η απόσταση εξαρτάται από την Ευκλείδεια απόσταση. Παρουσιάζουμε αποτελέσματα υπολογιστικής δυσκολίας για την εύρεση τόσο της βέλτιστης λύσης όσο και μιας καλής προσεγγιστικής λύσης. Από την άλλη πλευρά, αποδεικνύουμε άνω φράγματα στον λόγο προσέγγισης διάφορων πολυωνυμικών αλγορίθμων.
Στην περίπτωση που θεωρούμε πως οι σταθμοί μετάδοσης είναι συνδεδεμένοι με ένα ενσύρματο δίκτυο, έχουμε το πρόβλημα της συσταδοποίησης. Παρουσιάζουμε έναν βέλτιστο πολυωνυμικό αλγόριθμο για την περίπτωση όπου τα σημεία είναι συνευθειακά, ενώ αποδεικνύουμε αποτελέσματα υπολογιστικής δυσκολίας για την περίπτωση των δύο ή περισσοτέρων διαστάσεων. Τέλος, παρουσιάζουμε έναν προσεγγιστικό αλγόριθμο του οποίου ο λόγος προσέγγισης μπορεί να πλησιάσει αυθαίρετα κόντα το 1, με άλλα λόγια παρουσιάζουμε ένα προσεγγιστικό σχήμα πολυωνυμικού χρόνου. / In 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; 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).
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/657 |
| Date | 23 November 2007 |
| Creators | Κανελλόπουλος, Παναγιώτης |
| Contributors | Κακλαμάνης, Χρήστος, Kanellopoulos, Panagiotis, Κακλαμάνης, Χρήστος, Κυρούσης, Ελευθέριος, Σπυράκης, Παύλος, Βαρβαρίγος, Εμμανουήλ, Κοσμαδάκης, Σταύρος, Νικολετσέας, Σωτήριος, Καραγιάννης, Ιωάννης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0022 seconds