Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα

Abstract

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 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).

Στην παρούσα διδακτορική διατριβή ασχολούμαστε με ζητήματα ελαχιστοποίησης της κατανάλωσης ενέργειας που ανακύπτουν σε ασύρματα δίκτυα. Εξετάζουμε τόσο την περίπτωση ασυρμάτων δικτύων τύπου ad hoc όσο και την περίπτωση όπου υπάρχει ένα σταθερό ενσύρματο δίκτυο το οποίο συνδέει τους σταθμούς εκπομπής οι οποίοι χρησιμοποιούν ασύρματα μέσα προκείμενου να μεταδώσουν μηνύματα στους χρήστες. Στην πρώτη κατηγορία μελετούμε τόσο περιπτώσεις όπου η συνάρτηση κόστους στις ακμές είναι συμμετρική όσο και περιπτώσεις οπού δεν ισχύει αυτή η υπόθεση. Εξετάζουμε επιπλέον προβλήματα που προκύπτουν όταν θεωρούμε ότι οι σταθμοί βρίσκονται σε κάποιον Ευκλείδειο χώρο και η απόσταση εξαρτάται από την Ευκλείδεια απόσταση. Παρουσιάζουμε αποτελέσματα υπολογιστικής δυσκολίας για την εύρεση τόσο της βέλτιστης λύσης όσο και μιας καλής προσεγγιστικής λύσης. Από την άλλη πλευρά αποδεικνύουμε άνω φράγματα στον λόγο προσέγγισης διαφόρων πολυωνυμικών αλγορίθμων. Στην περίπτωση που θεωρούμε πως οι σταθμοί μετάδοσης είναι συνδεδεμένοι με ένα ενσύρματο δίκτυο έχουμε το πρόβλημα της συσταδοποίησης. Παρουσιάζουμε έναν βέλτιστο πολυωνυμικό αλγόριθμο για την περίπτωση όπου τα σημεία είναι συνευθειακά ενώ αποδεικνύουμε αποτελέσματα υπολογιστικής δυσκολίας για την περίπτωση των δυο η περισσοτέρων διαστάσεων. Τέλος παρουσιάζουμε έναν προσεγγιστικό αλγόριθμο του οποίου ο λόγος προσέγγισης μπορεί να πλησιάσει αυθαίρετα κοντά το 1 με άλλα λογία παρουσιάζουμε ένα προσεγγιστικό σχήμα πολυωνυμικού χρόνου.