Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους. / The characteristic feature of wireless ad hoc networks is that there is no fixed infastructure (in constrast with cellular networks). One considerabe example of such networks is sensor networks, which can be used to monitor a natural phenomenon, or to construct a temporary communication network in areas where a disaster has occurred, etc, therefore wireless ad hoc networks is a research area of great interest. In wireless ad hoc networks when a node needs to send a message to a node which relies outside of its transmission range, then the transmission takes place through the nodes which rely on a path which connects these two nodes. The wireless nodes, however, have limited energy, therefore routing method is crusial for the operation of the network. Routing protocols are based on several methods, such as: each node is allowed to communicate with only a selected subset of its neighbors, or each node chooses to transmits a message to one of its neighbors based on its geometrical position. Another routing method is to construct a virtual backbone network. The virtual network has the same nodes as the ad hoc network, but only its links are used for the routing of messages. The construction of the virtual network must be executed in a distributed way and its size and structure must be suitable to allow the nodes to consume as less energy as possible in order to support the routing protocol. In this work 1) we have developed two new routing methods for wireless ad hoc networks by constructing virtual networks. These two methods are based on corresponding algorithms for maintaining spanners. The virtual networks constructed have relatively small number of links, while having the ability that for every pair of nodes their distance in the virtual network is at most t times their distance in the ad hoc network (parameter t depends on the algorithm). 2) we have implemented these two algorithms in a simulation environment, and we have conducted an extensive study on them.

Μέχρι σήμερα στη δρομολόγηση στα ασύρματα αδόμητα δίκτυα λαμβάνεται ως κριτήριο ένα μοναδιαίο μέγεθος για κάθε σύνδεσμο του δικτύου, το οποίο αναπαριστά το κόστος της μετάδοσης πάνω στον συγκεκριμένο σύνδεσμο. Στη δρομολόγηση με βάση πολλαπλά κριτήρια η βασική ιδέα είναι ότι σε κάθε σύνδεσμο ανατίθεται ένα διάνυσμα από παραμέτρους-κόστη με βάση το οποίο προκύπτει και ένα αντίστοιχο διάνυσμα για κάθε μονοπάτι. Για κάθε ζευγάρι κόμβων αποστολέα-παραλήπτη γίνεται καταρχήν η εύρεση όλων των υποψήφιων για χρήση μονοπατιών. Τα υποψήφια μονοπάτια, που λαμβάνονται υπόψη κατά τη διαδικασία επιλογής, έχουν την ιδιότητα να είναι μη-κυριαρχημένα μεταξύ τους. Στη συνέχεια εφαρμόζεται στο σύνολο των μη-κυριαρχημένων μονοπατιών μια συνάρτηση που συνδυάζοντας τις συνιστώσες του κάθε διανύσματος παράγει το κόστος χρήσης κάθε μονοπατιού και έτσι το μονοπάτι με το ελάχιστο κόστος επιλέγεται για χρήση. Στα πλαίσια της εργασίας, καταρχήν μελετήθηκε ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη χρησιμοποιώντας παραμέτρους-κόστη σχετικές με την ενέργεια, όπως η τρέχουσα διαθέσιμη ενέργεια στους κόμβους και η ισχύς μετάδοσής τους. Στη συνέχεια στις παραμέτρους προστέθηκε και η παρεμβολή που δημιουργείται από τη μετάδοση πάνω σε ένα σύνδεσμο. Τα αποτελέσματα των προσομοιώσεων έδειξαν ότι ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη, σε σχέση με τον ελάχιστου μήκους διαδρομής, κατανέμει πιο ομοιόμορφα την κίνηση στο δίκτυο, επιμηκύνει τον χρόνο ζωής του δικτύου και αυξάνει το ποσοστό των παραδιδόμενων πακέτων. Στο επόμενο στάδιο της εργασίας έγινε μια κατανεμημένη υλοποίηση του αλγορίθμου δρομολόγησης με πολλαπλά κόστη, που επιπλέον λαμβάνει υπόψη την κινητικότητα των κόμβων του δικτύου, η οποία και πάλι φάνηκε να υπερέχει έναντι πιο παραδοσιακών πρακτικών. Τέλος η ιδέα της δρομολόγησης με πολλαπλά κόστη εφαρμόστηκε για τη λύση του προβλήματος ενεργο-αποδοτικής πολλαπλής ή ολικής εκπομπής (multicasting ή broadcasting, αντίστοιχα). Στόχος ήταν να βρεθεί η βέλτιστη ενεργο-αποδοτικά ακολουθία συνδέσμων πάνω στους οποίους πρέπει να γίνει μετάδοση ενός πακέτου προκειμένου να υλοποιηθεί η επιθυμητή εκπομπή. Σαν παράμετροι-κόστη χρησιμοποιήθηκαν η τρέχουσα διαθέσιμη ενέργεια και η ισχύς μετάδοσης των κόμβων. Τα αποτελέσματα δείχνουν σαφή υπεροχή του αλγορίθμου με πολλαπλά κόστη έναντι παραδοσιακών λύσεων τόσο για πολλαπλή εκπομπή όσο και για ολική εκπομπή. / Until now, routing in wireless ad hoc networks has been studied by taking into account a single scalar metric for every network link, representing the cost of transmitting through this link. In multicost routing a vector of cost parameters is assigned to each link, based on which a respective cost vector is produced for every path in the network. For every source-destination pair all the candidate paths are initially calculated that are non-dominated to each other. At the cost vectors of the candidate paths, an optimization function is applied in order to produce a cost for each path based on which the selection of the optimal one is made. In the present thesis multicost routing in wireless ad hoc networks was studied initially using as cost parameters the node residual energy and transmission power. As a next step the interference cause by the transmission of each link was added to the cost vectors assigned to each network link. The simulation results showed that multicost routing in comparison to traditional routing practices achieves more uniform traffic distribution and energy consumption in the network, prolongs the network lifetime and increases the percentage of the packets that are successfully delivered to their destinations. Expanding these ideas, the multicost routing algorithm was next implemented in a fully distributed fashion in which additionally the node mobility was taken into account. The results again proved that a significant improvement was accomplished compared to minimum-hop routing. Finally, multicost routing was applied in the field of multicasting and broadcasting in wireless ad hoc networks. The emphasis was again on energy-efficiency by incorporating energy-related cost parameters like node residual energy and transmission power. The multicost algorithm calculates the optimal energy-efficient sequence of nodes that by transmitting implement the desired communication task (multicasting or broadcasting). Simulation results illustrate a clear advantage of our algorithm over established solutions for energy-efficient multicasting and broadcasting.

Στην παρούσα διδακτορική διατριβή, ασχολούµαστε µε ζητήµατα που ανακύπτουν σε ασύρµατα δίκτυα επικοινωνίας, δηλ. δίκτυα που βασίζονται σε τηλεπικοινωνιακή υποδοµή όπως τα κυψελικά δίκτυα κινητής τηλεφωνίας, δίκτυα αυτόνοµων ασύρµατων εκποµπών όπως τα ασύρµατα δίκτυα τύπου ad hoc, κτλ. Τα ασύρµατα δίκτυα επικοινωνίας διαφόρων τύπων έχουν εξελιχθεί σηµαντικά τα τελευταία χρόνια. Ειδικότερα, τα ασύρµατα αδόµητα δίκτυα (ή αλλιώς ασύρµατα δίκτυα τύπου ad hoc) έχουν προσελκύσει το έντονο εν­διαφέρον της επιστηµονικής κοινότητας λόγω των πολλών εφαρµογών που έχουν κυρίως σε περιπτώσεις όπου δεν είναι δυνατή ή επιθυµητή η ολική ή µερική κάλυψη µέσω υποδοµής µε βάση την ενσύρµατη δικτύωση (π.χ., επι­κοινωνία σε δυσπρόσιτες ή αποµακρυσµένες περιοχές, φυσικές καταστροφές, στρατιωτικές εφαρµογές, κλπ.). ΄Οπως και στα παραδοσιακά ενσύρµατα δίκτυα, σηµαντικό πρόβληµα αποτελεί η εγκαθίδρυση σχηµάτων επικοινωνίας όπως διάδοση (broadcasting, multicasting), επικοινωνία όλων µε όλους (gossiping, all-to-all communica­tion), και επικοινωνία σε οµάδες (group communication). Για την επικοινω­νία απαιτείται η κατανάλωση ενέργειας στους κόµβους του δικτύου και, λαµβ.άνοντας υπόψη ότι τα αδόµητα ασύρµατα δίκτυα χρησιµοποιούν κόµβους µε περιορισµένα αποθέµατα ενέργειας, είναι απαραίτητη η ορθολογιστική χρήση αυτής της ενέργειας κατά την επικοινωνία. Αυτό µπορεί να σηµαίνει ότι είναι επιθυµητή είτε η ελαχιστοποίηση της συνολικής ενέργειας που κα­ταναλώνεται στους κόµβους του δικτύου για επικοινωνία ή η ελαχιστοποίηση της µέγιστης ενέργειας ώστε να επιτυγχάνεται όσο το δυνατό µεγαλύτερος χρόνος ζωής όλων των κόµβων του δικτύου. Στη διατριβή εξετάζουµε αλγόριθ­µους για την εγκαθίδρυση διαφορετικών σχηµάτων επικοινωνίας σε αδόµητα ασύρµατα δίκτυα όπου βασικό κριτήριο για την εκτίµηση της απόδοσής τους θα είναι η κατανάλωση ενέργειας που επιφέρουν στο δίκτυο. Μοντελοποιούµε τα δίκτυα µε ειδικά γραφήµατα και τα αντίστοιχα προβλήµατα επικοινωνίας σαν προβλήµατα συνδυαστικής βελτιστοποίησης στα γραφήµατα αυτά. Τα αποτελέσµατά µας περιλαµβάνουν νέους αλγόριθµους που βελτιώνουν προηγούµενα γνωστά σχετικά αποτελέσµατα και νέα κάτω φράγµατα. Με κεντρικό στόχο την αποδοτική κατανοµή ενέργειας σε ασύρµατα δίκτυα, η µελέτη µας έχει διττό χαρακτήρα: από τη µια πλευρά, ασχολούµαστε µε µε­λέτη και ανάλυση θεµελιωδών προβληµάτων της Θεωρητικής Επιστήµης των Υπολογιστών (όπως, π.χ., το πρόβληµα Κάλυψης µε Σύνολα). Τέτοια προβλήµατα, και ειδικές περιπτώσεις τους, παρουσιάζουν εξαιρετικό ενδιαφέρον αφού χρησιµοποιούνται (µεταξύ άλλων) συχνά για τη µοντελοποίηση προβλη­µάτων ενεργειακά αποδοτικής επικοινωνίας σε ασύρµατα δίκτυα. Επιπλέον, προτείνουµε και αναλύουµε νέους αλγόριθµους για συγκεκριµένα σενάρια επικοινωνίας σε σύγχρονα ασύρµατα δίκτυα. Από την άλλη πλευρά, µελετάµε και εκτιµούµε πειραµατικά την απόδοση αρκετών αλγορίθµων και τεχνικών (από τη βιβλιογραφία αλλά και νέων) για ενεργειακά αποδοτική επικοινωνία σε ασύρµατα δίκτυα. Ειδικότερα: Μελετάµε το πρόβληµα κάλυψης µε σύνολα και ενδιαφέρουσες παραλ­λαγές του. Παρουσιάζουµε νέους συνδυαστικούς προσεγγιστικούς αλγόριθµους για το πρόβληµα k-κάλυψης συνόλων. Προηγούµενες προσεγγίσεις έχουν βασισθεί σε επεκτάσεις του άπληστου αλγόριθµου µέσω αποδοτικού χειρισµού µικρών συνόλων. Οι νέοι αλγόριθµοι επεκτείνουν περαιτέρω τις προηγούµενες προσεγγίσεις χρησιµοποιώντας την ιδέα του υπολογισµού µεγάλων οµάδων στοιχείων και στη συνέχεια της οµαδοποίησής τους σε σύνολα µεγάλου µεγέθους. Τα αποτελέσµατά µας βελτιώνουν τα καλύτερα γνωστά φράγµατα προσέγγισης για το πρόβληµα k-κάλυψης συνόλων για κάθε τιµή του k >= 6. Η τεχνική που χρησιµοποιούµε για την ανάλυση παρουσιάζει επιπλέον ανεξάρτητα ενδιαφέρον: το πάνω φράγµα για τον παράγοντα προ­σέγγισης επιτυγχάνεται φράσσοντας την αντικειµενική τιµή ενός γραµµικού προγράµµατος η οποία ‘αποκαλύπτει’ το λόγο προσέγγισης του υπό εξέταση αλγορίθµου (factor-revealing). Παρουσιάζουµε έναν απλό αλγόριθµο για το πρόβληµα εύρεσης µέγιστου δάσους γεννητικού αστέρα. Λαµβάνουµε υπόψη το γεγονός ότι το πρόβληµα αποτελεί ειδική περίπτωση του συµπληρωµατικού προβλήµατος κάλυψης συ­νόλου και προσαρµόζουµε έναν αλγόριθµο των Duh και Furer για την επίλυ­σή του. Αποδεικνύουµε ότι ο αλγόριθµος αυτός υπολογίζει 193/240 που είναι περίπου ίσο με 0.804 ­προσεγγιστικά δάση γεννητικών αστέρων. Το αποτέλεσµα αυτό βελτιώνει ένα προηγούµενο άνω φράγµα µε τιµή 0.71 των Chen και άλλων. Αν και ο αλ­γόριθµος είναι καθαρά συνδυαστικός, η ανάλυσή µας ορίζει ένα γραµµικό πρόγραµµα που χρησιµοποιεί µια παράµετρο f το οποίο είναι επιλύσιµο για τιµές της παραµέτρου f που δεν είναι µικρότερες από το λόγο προσέγγισης του αλγορίθµου. Η ανάλυση είναι αυστηρή και, το ενδιαφέρον είναι ότι, µπορεί να εφαρµοστεί και σε συµπληρωµατικές εκδοχές του προβλήµατος κάλυψης συνόλου όπως η εξοικονόµηση χρωµάτων. Δίνει την ίδια εγγύηση προσέγγισης µε τιµή 193/240 που οριακά βελτιώνει το προηγούµενο γνω­στό κάτω φράγµα των Duh και Furer. Αποδεικνύουµε επίσης ότι, γενικά, µια φυσική κλάση αλγορίθµων τοπικής αναζήτησης δε δίνουν καλύτερα από 1/2-προσεγγιστικά δάση γεννητικών αστέρων. Μελετάµε προβλήµατα επικοινωνίας σε ασύρµατα δίκτυα που υποστηρί­ζουν πολλαπλά µέσα ασύρµατης διασύνδεσης. Σε τέτοια δίκτυα, δύο κόµβοι µπορούν να επικοινωνήσουν αν είναι αρκετά κοντά και διαθέτουν κάποιο κοινό µέσο ασύρµατης διασύνδεσης. Η ενεργοποίηση ενός µέσου ασύρµατης διασύνδεσης επιφέρει ένα κόστος που αντανακλά την ενέργεια που καταναλώ­νεται όταν κάποιος κόµβος χρησιµοποιεί το µέσο αυτό. Διακρίνουµε µεταξύ της συµµετρικής και της µη συµµετρικής περίπτωσης, µε βάση το κόστος ενεργοποίησης για κάθε ασύρµατο µέσο διασύνδεσης είναι το ίδιο για όλους τους κόµβους ή όχι. Για τη συµµετρική περίπτωση, παρουσιάζουµε έναν (3/2+ε)–προσεγγιστικό αλγόριθµο για το πρόβληµα πλήρους διασύνδεσης µε ελάχιστο κόστος ενεργοποίησης, βελτιώνοντας ένα προηγούµενο φράγµα µε τιµή 2. Για τη µη συµµετρική περίπτωση, αποδεικνύουµε ότι το πρόβληµα διασύνδεσης δεν είναι προσεγγίσιµο στα πλαίσια ενός παράγοντα υπολογα­ριθµικού ως προς το πλήθος των κόµβων και παρουσιάζουµε ένα λογαριθµι­κό προσεγγιστικό αλγόριθµο για µια γενικότερη περίπτωση που µοντελοποιεί την οµαδική επικοινωνία. Επίσης, µελετάµε αλγόριθµους για τον υπολογισµό αποδοτικών ως προς την ενέργεια δένδρων µετάδοσης (multicasting) σε ασύρµατα αδόµητα δί­κτυα. Τέτοιοι αλγόριθµοι είτε ξεκινούν από µια κενή λύση η οποία σταδιακά επαυξάνεται για να δώσει ένα δένδρο µετάδοσης (επαυξητικοί αλγόριθµοι ­augmentation algorithms) είτε λαµβάνουν σαν είσοδο ένα αρχικό δένδρο µε­τάδοσης και εκτελούν ‘περιπάτους ’ σε διαφορετικά δένδρα µετάδοσης για πεπερασµένο αριθµό βηµάτων µέχρι να επιτευχθεί κάποια αποδεκτή µείωση στην κατανάλωση της ενέργειας (αλγόριθµοι τοπικής αναζήτησης -local search algorithms). Εστιάζουµε τόσο σε επαυξητικούς αλγόριθµους όσο και σε αλγό­ριθµους τοπικής αναζήτησης και συγκεκριµένα έχουµε υλοποιήσει αρκετούς υπάρχοντες αλγόριθµους από τη βιβλιογραφία αλλά και νέους. Συγκρίνου­µε πειραµατικά τους αλγόριθµους αυτούς σε τυχαία γεωµετρικά στιγµιότυπα του προβλήµατος και επιτυγχάνουµε αποτελέσµατα όσον αφορά στην αποδο­τικότητα ως προς την ενέργεια των λύσεων που λαµβάνουµε. Παρουσιάζουµε επίσης αποτελέσµατα σχετικά µε το χρόνο εκτέλεσης των υλοποιήσεών µας. Επίσης διερευνούµε το κατά πόσον οι λύσεις που λαµβάνουµε από επαυ­ξητικούς αλγόριθµους µπορούν να βελτιωθούν µέσω αλγορίθµων τοπικής αναζήτησης. Τα αποτελέσµατά µας αποδεικνύουν ότι ένας από τους νέους αλγόριθµους που προτείνουµε και οι εκδοχές του επιτυγχάνουν τις πιο απο­δοτικές ενεργειακά λύσεις και µάλιστα πολύ γρήγορα και, επιπλέον, υποδεικ­νύουν ιδιότητες γεωµετρικών στιγµιοτύπων του προβλήµατος που συντελούν στη βελτιωµένη απόδοση των επαυξητικών αλγορίθµων. / In this dissertation, we study issues arising in wireless communication networks, i.e., networks based on telecommunication infrastructure like cellular wireless networks, networks of autonomous wireless transmitters like ad hoc wireless networks, and so on. Wireless networks have received significant attention during the recent years. Especially, ad hoc wireless networks for which unlike traditional wired networks or cellular wireless networks, no wired backbone infrastructure is installed emerged due to their potential applications in emergency disaster relief, battlefield, etc. Like in traditional wired networks, an important problem concerns the establishment of communication patterns like broadcasting, multicasting, gossiping, all-to-all communication, and group communication. Communication then requires energy consumption at network nodes, and given that in ad hoc wireless networks energy is a scarce resource, it is of paramount importance to use it efficiently when establishing communication patterns. In such a setting, it is usually pursued that either the total energy consumed at networks nodes or the maximum energy consumed at any network node is minimized so that the network lifetime is prolonged as long as possible. Herein, we present and analyze theoretically and experimentally algorithms for guaranteeing the establishment of various communication patterns in ad hoc wireless networks and evaluate their performance in terms of their energy-efficiency. We represent these networks using graphs and model the corresponding communication problems as combinatorial optimization problems in such graphs. Our results include new algorithms which improve previously known relevant results as well as new lower bounds. Our main objective being the efficient energy allocation in wireless networks, our study is of dual character: on the one hand, we study and analyze fundamental problems of Theoretical Computer Science (like, e.g., Set Cover); such problems, as well as special cases of them, are highly interesting since they usually model energy-efficient communication problems in wireless networks. Furthermore, we propose and analyse new algorithms for particular communication scenaria in modern wireless networks. On the other hand, we experimentally study and evaluate several algorithms and techniques (both from the literature and new ones) for energy-efficient communication in wireless networks.