Στόχος της εργασίας είναι να εμβαθύνει πάνω στο σημαντικό θέμα της ποιότητας υπηρεσίας, εξειδικεύοντας το θέμα για τα ATM switches. Μελετά τους αλγορίθμους που εφαρμόζονται ή λειτουργούν σε θεωρητικό επίπεδο για τα ATM switches και τον τρόπο που επηρεάζουν τις διάφορες παραμέτρους του QoS. Για το λόγο αυτό ορισμένοι αλγόριθμοι εφαρμόζονται σε εξομοιωτή δικτύων και με βάση τη συμπεριφορά τους εκτιμάται η επίδραση των διαφόρων αλγορίθμων στην απόδοση και τη συμπεριφορά των δικτύων. / This research examines closely the important issue of quality of service, specializing the issue on ATM switches. It examines the algorithms that are applied or used on theoretical level on ATM switches and the way they affect the QoS parameters. For this reason some algorithms are applied on a network simulator and according the network’s behavior we estimate the effect of different algorithms on networks’ performance and behavior.

Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση. Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων. Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα, προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης, χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά. Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def- inition of which is: We are given a sequence of tasks that are to be processed on a set of machines. Each task is characterized by its running time and has to be scheduled on a machine, for at least its running time. In addition, there are speedup requests from a subset of tasks. The scheduling algorithm is asked to produce a schedule that minimizes an objective function in par- allel with serving as many as possible speedup requests. The introduction gives a theoretical background concerning scheduling prob- lems and algorithms, with an emphasis on the di_erence between static and dynamic algorithms. The objective of the second chapter, is to study the problem above, in its many variations, with a reference to parameters like the number of the machines, deadlines etc. The result of this study, is the development and the evaluation of two algorithms, using objective functions like makespan, and also some new ones that arise in the essay and their need is analyzed. The thesis closes with a consideration of already known schedul- ing problems and its variants, that have been proved to be NP-complete.

Στις ημέρες μας, εμφανίζεται ολοένα και σε περισσότερα πλαίσια η ανάγκη για την ανάπτυξη αξιόπιστων ασύρματων αυτοοργανούμενων δικτύων (Mobile Ad hoc Networks). Τα δίκτυα αυτά δεν απαιτούν την ύπαρξη μίας σταθερής υποδομής ή διαδικασίας προετοιμασίας και εγκατάστασης, ενώ παράλληλα επιτρέπουν τη δημιουργία δυναμικών και συχνά μεταβαλλόμενων τοπολογιών με υπολογιστικούς κόμβους που κινούνται με τυχαίο τρόπο και συχνά χαρακτηρίζονται από αυστηρούς ενεργειακούς περιορισμούς. Το πρόβλημα της αποτελεσματικής σχεδίασης και ανάπτυξης αυτοοργανούμενων δικτύων αποτελεί μία πρόκληση που έχει προσελκύσει αρκετές ερευνητικές προσπάθειες. Στο πλαίσιο της παρούσας εργασίας, το ενδιαφέρον επικεντρώνεται στη μελέτη αλγορίθμων δρομολόγησης δεδομένων μεταξύ των κόμβων ενός αυτοοργανούμενου ασύρματου δικτύου. Αρχικά, παρατίθεται μία κριτική επισκόπηση των αλγορίθμων δρομολόγησης που υπάρχουν στη βιβλιογραφία. Στη συνέχεια, λαμβάνει χώρα η υλοποίηση του πρωτοκόλλου ZRP (Zone Routing Protocol), το οποίο όπως προκύπτει από την προαναφερθείσα κριτική επισκόπηση παρουσιάζει σημαντικά πλεονεκτήματα για αυτήν την κατηγορία δικτύων. Ακολουθεί η παρουσίαση τριών σειρών προσομοιώσεων που πραγματοποιήθηκαν για την ποσοτική αξιολόγηση του ZRP πρωτοκόλλου σε διάφορα σενάρια φορτίου και κινητικότητας των υπολογιστικών κόμβων. Παράλληλα, πραγματοποιήθηκε και μία εκτεταμένη ποσοτική σύγκριση του DSR πρωτοκόλλου με το ZRP. Τέλος, στο πλαίσιο της εργασίας προτείνεται μία βελτιωμένη παραλλαγή του πρωτοκόλλου ZRP, το επονομαζόμενο AZRP (Adaptive Zone Routing Protocol). Το AZRP πρωτόκολλο προσπαθεί να βελτιώσει και να επεκτείνει τους μηχανισμούς του ZRP εισάγοντας μία τεχνική αυτόματης προσαρμογής του μεγέθους της ζώνης δρομολόγησης κάθε κόμβου. Με αυτόν τον τρόπο το AZRP μπορεί να προσαρμόζεται πιο αποτελεσματικά σε οποιαδήποτε κατάσταση του δικτύου ανά πάσα χρονική στιγμή. Η ιδέα αυτή οδήγησε και σε μία σχετική επιστημονική δημοσίευση στο πλαίσιο της διπλωματικής αυτής. / Nowadays, there is a growing need to deploy reliable mobile ad hoc networks (MANETs). These networks enable the development of dynamic and frequently changing topologies of computational nodes that move randomly, and typically have energy consumption limitations, without relying on a centralized, pre-configured infrastructure. The abundance of challenges in the design and deployment of such networks has attracted the interest of many research efforts. The focus of this thesis is on the study of routing algorithms for MANETs. Initially, the thesis presents a critical survey of such routing algorithms mentioned in the bibliography. Next, an implementation of the ZRP protocol (Zone Routing Algorithm) is presented, which according to the aforementioned survey was found to have significant advantages for MANETs. Subsequently, three sets of simulations that evaluated the performance of the ZRP protocol in different scenarios of node mobility and network traffic are presented. In addition, an extended quantitative comparison of the DSR and ZRP protocol performance is also presented. Finally, in the context of this thesis a new, improved version of the ZRP protocol is proposed, named AZRP (Adaptive Zone Routing Protocol). The AZRP protocol tries to improve the performance of ZRP by introducing a mechanism that automatically adjusts the size of the routing zone of each node based on the overall network traffic and node mobility. The latter idea led to a related publication in the context of this thesis.

Στα αυτοοργανούμενα ασύρματα δίκτυα, αυτόνομοι κόμβοι με κάρτες ασύρματης μετάδοσης σχηματίζουν ένα δίκτυο χωρίς προϋπάρχουσα δομή. Η δρομολόγηση σε ένα συμβατικό δίκτυο γίνεται από ειδικούς δρομολογητές, είτε υλοποιημένους σε υλικό ειδικά για αυτό το σκοπό, ή υπολογιστές εξοπλισμένους με πολλαπλές διεπαφές δικτύου και ανάλογο λογισμικό. Αντίθετα, σε ένα ad-hoc δίκτυο, η δρομολόγηση διεκπεραιώνετε από τους ίδιους τους κόμβους. Κάθε κόμβος έχει τη δυνατότητα να προωθεί δικτυακό φορτίου στους υπόλοιπους. Αντίθετα με τους σταθερούς δρομολογητές, ένας κόμβος ασύρματου δικτύου έχει μόνο μια δικτυακή διεπαφή, καθώς όλη η επικοινωνία γίνεται μέσω ενός και μόνο ασύρματου καναλιού. Οι κόμβοι σε ένα ad-hoc δίκτυο προσφέρονται να προωθήσουν την δικτυακή κίνηση εκ μέρους άλλων κόμβων. Αν αρνηθούν να το κάνουν αυτό, η συνδεσιμότητα μεταξύ των κόμβων επηρεάζεται αρνητικά. Η λειτουργικότητα και χρησιμότητα του ad-hoc δικτύου εξαρτάται σημαντικά από την ικανότητα προώθησης πακέτων των κόμβων του. Συνεπώς, καταλαβαίνουμε ότι ο αλγόριθμος δρομολόγησης του ad-hoc δικτύου διαδρατίζει σημαντικό ρόλο στην απόδοσή του. Βασικός σκοπός της διπλωματικής αυτής εργασίας είναι να μελετήσει την απόδοση μερικών βασικών αλγορίθμων δρομολόγησης ως προς κάποιες μετρήσιμες παραμέτρους (throughput, end to end delay, delivery ratio). Έγιναν εξομοιώσεις για δύο διαφορετικά πρωτόκολλα φυσικού επιπέδου (802.11 και 802.15.4). Επίσης, αναλύονται θεωρητικά σε βάθος διάφορα ζητήματα σχετικά με τη διευθυνσιοδότηση, τη δρομολόγηση, τα σχετικά MAC πρωτόκολλα, τη δικτυακή ασφάλεια, τη κατανάλωσης ενέργειας, τις απαιτήσεις στο hardware των διάφορων αλγορίθμων δρομολόγησης που έχουν αναπτυχθεί από την ακαδημαϊκή κοινότητα και τη βιομηχανία. / In ad hoc wireless networks, autonomous nodes with wireless transmission cards form a network without pre-existing structure. The route in a conventional network is carried out by routers made for this reason, whether implemented on hardware specifically for this purpose, or computers equipped with multiple network interfaces and appropriate software. Conversely, in an ad-hoc network, routing is handled the nodes themselves. Each node has the ability to forward network load to others. Unlike fixed routers, a wireless network node has only one network interface and all communication is via a single wireless channel. The nodes in an ad-hoc network offer to promote the network traffic from other nodes. If they refuse to do so, the connectivity between nodes is affected negatively. The functionality and usefulness of ad-hoc network depends heavily on the ability to forward packages of nodes. Therefore, the routing algorithm in ad-hoc network plays an important role in the network's performance. The main purpose of this thesis is to study the performance of certain basic routing algorithms in terms of some measurable parameters (throughput, end to end delay, delivery ratio). We carried out simulations for two different physical layer protocols (802.11 and 802.15.4). Also, we analyzed theoretically various issues related to addressing, routing, related MAC protocols, network security, energy consumption requirements in the hardware of the various routing algorithms developed by academia and industry.

Στην παρούσα εργασία εξετάζουμε το πρόβλημα της δρομολόγησης σε δίκτυα ad-hoc, όπου οι κόμβοι είναι ακίνητοι και έχουν πεπερασμένα αλλά επαναφορτιζόμενα ενεργειακά αποθέματα. Αρχικά μελετάμε σε θεωρητική βάση τους ενεργειακούς και χωρητικούς περιορισμούς. Ενεργειακοί είναι οι περιορισμοί που οφείλονται στην μικρή ενεργειακή αυτοτέλεια των κόμβων, ενώ οι χωρητικοί περιορισμοί οφείλονται στην περιορισμένη χωρητικότητα του ασύρματου μέσου και στην παρεμβολή. Συγκεκριμένα εξετάζουμε πώς ορισμένα δικτυακά χαρακτηριστικά επηρεάζουν την απόδοση του δικτύου. Τέτοια δικτυακά χαρακτηριστικά είναι η πυκνότητα των κόμβων του δικτύου, η φυσική απόσταση τους, η ακτίνα μετάδοσης τους κ.α. Εξετάζουμε διαφόρων ειδών δίκτυα και σε γενικές γραμμές αποδεικνύουμε ότι η ενέργεια είναι ο κρίσιμος πόρος σε δίκτυα τα οποία είναι αραιά ή οι κόμβοι τους έχουν μικρό ρυθμό επαναφόρτισης της ενέργειας ή μεγάλη ακτίνα μετάδοσης. Στην αντίθετη περίπτωση η απόδοση των δικτύων περιορίζεται από την χωρητικότητα και την παρεμβολή. Επιπλέον προτείνουμε και υλοποιούμε έναν ενεργειακά-αποδοτικό αλγόριθμο δρομολόγησης με πολλαπλά κόστη, όπου ένα διάνυσμα από παραμέτρους, εν’αντιθέσει με μία μόνο παράμετρο, ανατίθεται σε κάθε σύνδεσμο του δικτύου. Σε κάθε ανακαλυπτόμενη διαδρομή ανατίθεται ομοίως ένα διάνυσμα παραμέτρων, που προκύπτει από τα αντίστοιχα διανύσματα των συνδέσμων της διαδρομής. Οι παράμετροι που χρησιμοποιούμε είναι ο αριθμός των συνδέσμων της διαδρομής, η υπολειπόμενη ενέργεια και η ισχύς μετάδοσης. Ο αλγόριθμος αυτός συγκρίνεται με τον αλγόριθμο ελάχιστου-μήκους διαδρομής, για την επίλυση του προβλήματος του άπειρου χρονικού ορίζοντα. Στο πρόβλημα του άπειρου χρονικά ορίζοντα, ενέργεια και νέα πακέτα δεδομένων δημιουργούνται συνεχώς σε κάθε κόμβο του δικτύου. Στα πειράματα που εκτελέσαμε μας ενδιαφέρει να υπολογίσουμε την μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax στους κόμβους, η οποία επιτρέπει στο δίκτυο μας να παραμένει ευσταθές. Ένα δίκτυο χαρακτηρίζεται ευσταθές όταν η εισερχόμενη κίνηση εξυπηρετείται από το δίκτυο με μικρή μέση καθυστέρηση παράδοσης αλλά και μεγάλο ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων στους προορισμούς τους. Όταν μία από αυτές τις συνθήκες δεν ισχύει τότε θεωρούμε ότι το δίκτυο είναι ασταθές και δεν μας ενδιαφέρει περαιτέρω η μελέτη του. Ουσιαστικά η μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax είναι η μέγιστη απόδοση του δικτύου μας. Η μέση καθυστέρηση παράδοσης των πακέτων δεδομένων ορίζεται ως ο μέσος χρόνος μεταξύ της δημιουργίας ενός πακέτου στον κόμβο-πηγή και της λήψης του πακέτου στον κόμβο-προορισμού. Το ποσοστό της επιτυχούς παράδοσης των πακέτων δεδομένων ορίζεται σαν τον λόγο του αριθμού των πακέτων που παρελήφθησαν επιτυχώς από τους κόμβους-προορισμού προς τον αριθμό των πακέτων που δημιουργήθηκαν στους κόμβους-πηγής. Κατά την διάρκεια των πειραμάτων μας δοκιμάζουμε διάφορες πιθανότητες δημιουργίας πακέτων δεδομένων p και διάφορους ρυθμούς επαναφόρτισης των κόμβων X. Από τα αποτελέσματα των πειραμάτων μας παρατηρούμε ότι ο ενεργειακά-αποδοτικός αλγόριθμος δρομολόγησης με πολλαπλά κόστη υπερτερεί του αλγορίθμου ελάχιστου-μήκους διαδρομής, πετυχαίνοντας όταν το δίκτυο είναι ενεργειακά περιορισμένο, μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax σχεδόν διπλάσια από αυτή που πετυχαίνει ο ελάχιστου-μήκους διαδρομής αλγόριθμος. Ακόμα παρατηρούμε ότι η μέση καθυστέρηση καθώς και το ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων παρουσιάζουν καλύτερα αποτελέσματα με την χρήση του ενεργειακά-αποδοτικού αλγορίθμου. Επιπλέον παρατηρούμε ότι η μέση καθυστέρηση αυξάνει πολύ απότομα σε σχέση με την πιθανότητα δημιουργίας πακέτων δεδομένων p, όταν το δίκτυο γίνεται ασταθές λόγο των ενεργειακών περιορισμών. Αντίθετα η αύξηση αυτή είναι πολύ πιο ομαλή, όταν το δίκτυο γίνεται ασταθές λόγο των χωρητικών περιορισμών. / In our thesis we examine the problem of routing in ad-hoc networks, where the nodes are stationary and have limited but rechargeable energy reserves. Initially we study theoretically, the energy and the capacity constraints. The energy constraints are the result of the limited energy reserves of the nodes, while the capacity constraints are the result of the limited capacity and of the interference in the wireless medium. In our theoretically study we examine how the various network characteristics, influence the network performance. Such network characteristics are the nodes density, their distance, the transmission radius etc. We examine various network topologies and in every case we prove that energy is a vital resource in networks which are sparsely or where the nodes have small recharge rate or big transmission radius. In every other case the performance of a network is constrained by the capacity and the interference. Furthermore we propose and implement an energy-aware multicost routing algorithm, where a vector of parameters, instead of just one parameter, is assigned to each link of the network. In the same way in every discovered path, a vector of parameters is assigned. This vector is calculated using the vectors of the links from which the path consists of. The parameters used are the hops number, the residual energy and the transmission power. The proposed algorithm is compared with the minimum-hop algorithm, under the infinite time horizon problem. In this problem energy and data packets are constantly created in every node of the network. In our experiments we are interested in finding the maximum packet generation probability pmax in the nodes, under which the network remains stable. A network is characterized as stable when the incoming traffic is served by the network with small average delivery delay and big successful delivery ratio, of the packets in their destinations. When one of these conditions doesn’t hold, then we assume that the network is unstable and we do not study it anymore. The maximum packet generation probability pmax is in fact the maximum throughput of the network. The average delivery delay is defined as the average time between the creation of a data packet in the source-node and the reception of the packet in the destination-node. The successful delivery ratio is defined as the ratio of the number of packets successfully received by their destinations by the number of packets created in the source-nodes. During our experiments we tried various packet generation probabilities p and recharge rates at the nodes X. From the results of ours experiments we observe that the energy-aware multicost routing algorithm outperforms the minimum-hop algorithm. Specifically when the network is energy constrained, the maximum packet generation probability pmax is almost double as the one achieved by the minimum-hop algorithm. Furthermore the average delivery delay and the successful delivery ratio present better results using the energy-aware algorithm. Also we generally observe that the average delivery delay increases suddenly as the packet generation probability p increases, when the network becomes unstable because of the energy constraints. On the other hand the increase in the average delivery delay is much more normal, when the network becomes unstable because of the capacity constraints.

Η αλματώδης ανάπτυξη που παρατηρείται τα τελευταία χρόνια στον τομέα των οπτικών δικτύων τηλεπικοινωνιών, έχει ως συνέπεια την αύξηση της κατανάλωσης ενέργειας. Σήμερα υπολογίζεται ότι η ενέργεια που οφείλεται σε IT τεχνολογίες αποτελεί το 1%-2% της παγκόσμιας κατανάλωσης. Ωστόσο, τα ποσοστά αυτά αναμένεται να αυξηθούν δραματικά μιας και όλο και περισσότερες εφαρμογές, που απαιτούν μεγάλο εύρος ζώνης (π.χ. video streaming, HDTV), αναπτύσσονται ταχύτατα. Μέχρι πρόσφατα ο κύριος περιορισμός στην ανάπτυξη των δικτύων ήταν το κόστος εξοπλισμού και μετάδοσης. Σήμερα το μεγαλύτερο πρόβλημα είναι η όλο και αυξανόμενη κατανάλωση ενέργειας. Έτσι λοιπόν πιο energy-aware προσεγγίσεις για το σχεδιασμό, την υλοποίηση και τη λειτουργία των οπτικών δικτύων κρίνονται πλέον απαραίτητες. Για την αντιμετώπιση του προβλήματος της κατανάλωσης ενέργειας σε οπτικά δίκτυα υπάρχουν δυο προσεγγίσεις: η ανάπτυξη ενεργο-αποδοτικών συσκευών δικτύου ή η ανάπτυξη αλγορίθμων δρομολόγησης και ανάθεσης μήκους κύματος (RWA) που να λαμβάνουν υπόψη τους και την ενέργεια που καταναλώνει το δίκτυο. Στην παρούσα διπλωματική εργασία επιλέχθηκε η δεύτερη προσέγγιση όπου και αναπτύχθηκαν Energy Aware RWA αλγόριθμοι για τον σχεδιασμό WDM οπτικών δικτύων με στόχο την ελαχιστοποίηση της ενέργειας που καταναλώνεται. Αυτό επιτυγχάνεται μειώνοντας τον αριθμό των συσκευών του δικτύου, όπως αναγεννητές, ενισχυτές, add/drop τερματικά κ.τ.λ. που είναι γνωστό ότι καταναλώνουν αρκετή ενέργεια κατά τη λειτουργία τους. Αρχικά αναπτύχθηκε ένας αλγόριθμος σε Ακέραιο Γραμμικό Ακέραιο Προγραμματισμό (Integer Linear Programming - ILP) που ελαχιστοποιεί από κοινού όλες εκείνες τις συσκευές του δικτύου που καταναλώνουν ενέργεια. Έπειτα το πρόβλημα χωρίζεται σε δυο υπο-προβλήματα: την κατανομή αναγεννητών σε κόμβους του δικτύου όπου η αναγέννηση είναι απαραίτητη και στο Energy Aware RWA. Σε αυτή τη περίπτωση εκτός από ILP προγραμματισμό εφαρμόζεται επίσης και χαλάρωση των περιορισμών ακεραιότητας (LP προγραμματισμός) ώστε να μπορούν να προκύψουν λύσεις και για μεγαλύτερες τοπολογίες. Για τον υπολογισμό της απόδοσης των προτεινόμενων αλγορίθμων διεξάγονται μια σειρά από πειράματα εξομοιώσεων σε Matlab, με τη βοήθεια του LINDO API για την επίλυση των (I)LP προβλημάτων σε ένα μικρό δίκτυο αλλά και στο ευρωπαϊκό δίκτυο Geant-2. Oι προτεινόμενοι αλγόριθμοι συγκρίνονται με τυπικούς RWA αλγορίθμους που δεν λαμβάνουν υπόψη την ενέργεια ή ελαχιστοποιούν κάποιες από τις συνιστώσες του δικτύου. Οι υπολογισμοί δείχνουν ότι η κατανάλωση της ενέργειας του δικτύου μπορεί να μειωθεί μέχρι και 45% σε δίκτυο με συνδέσμους μονής ίνας και μέχρι και 65% σε συνδέσμους διπλής ίνας. / The continuing deployment and upgrade of optical telecommunication networks drive up power and energy consumption, in a way that makes operators worry that future energy consumption levels may pose constraints on communications growth that are more significant than those posed by bandwidth considerations. As community concerns about global energy consumption grow, the power consumption of the optical networks is becoming an issue of increasing importance. Even though energy consumption of IT-related infrastructure currently represents between 1% and 2% of global energy consumption, such values are destined to rise, as more bandwidth-hungry applications (such as video streaming, and HDTV in particular) continue to be developed. Thus, it seems that an energy-aware approach is increasingly needed during the design, implementation and operation of optical networks. Two different approaches can be explored to reduce energy consumption in optical networks: the improvement of the energy efficiency of the equipment and the energy awareness of the Routing and Wavelengths Assignment (RWA) algorithms. In this work the energy minimization problem in optical networks is considered from an algorithmic perspective. The objective of the proposed algorithms is to plan optical WDM networks so as to minimize the energy consumed, by minimizing the number of the most energy-consuming components. Such components can be amplifiers, regenerators, add/drop terminals, optical fibers, etc. Firstly an Integer Linear Programming (ILP) formulation is given that aims at jointly minimizing the energy consuming modules present in an optical network, such as the regenerators, amplifiers, wavelength selective switches, etc. Then the problem for a general (translucent network) is decomposed into a regeneration placement problem, and an energy-aware RWA for transparent networks problem, where again ILP formulations are given to minimize energy consumption. The ILP of the decomposed problem is solved as an LP problem, by relaxing the integer constraints, in order to obtain solutions for larger network topologies. In order to evaluate the performance of the proposed Energy Aware (EA)-RWA algorithms a number of simulation experiments is carried out. All the RWA algorithms are implemented in Matlab and LINDO API is used to solve the corresponding (I)LP problems. The proposed algorithms are compared with RWA algorithms that do not consider energy minimization techniques or RWA algorithms that partially take into account energy consuming components. The simulation results showed that the energy consumption in the optical layer can be reduced by up to 45% in single fiber networks and by up to 65% in multi-fiber networks.

Τα ασύρματα δίκτυα μικροαισθητήρων αποτελούνται από ένα πολύ μεγάλο πλήθος συσκευών που τοποθετούνται σε μία περιοχή ενδιαφέροντος και αυτοοργανώνονται σε ένα αδόμητο δίκτυο, προκειμένου να καταγράψουν/μετρήσουν/παρακολουθήσουν κάποια περιβαλλοντική μετρική ή φαινόμενο και εν συνεχεία να μεταφέρουν τα δεδομένα σε κάποιο κέντρο ελέγχου. Λόγω των πολύ περιορισμένων δυνατοτήτων των συσκευών, ειδικά όσον αφορά την εμβέλεια επικοινωνίας και τα αποθέματα ενέργειας, αλλά και λόγω του πλήθους τους, είναι απαραίτητη η ανάπτυξη νέων αλγορίθμων και πρωτοκόλλων σχεδιασμένων για τα ιδιαίτερα προβλήματα των δικτύων αισθητήρων. Στην παρούσα διατριβή παρουσιάζουμε έρευνα επικεντρωμένη στην ανάπτυξη, προσομοίωση και αξιολόγηση ενεργειακά αποδοτικών αλγορίθμων, δηλαδή βασικός στόχος είναι η ελαχιστοποίηση της κατανάλωσης ενέργειας. Παρά τη ραγδαία εξέλιξη της τεχνολογίας του υλικού το πρόβλημα βελτιστοποίησης της ενέργειας των συσκευών αισθητήρων παραμένει επίκαιρο αφού οι υπάρχουσες και άμεσα διαφαινόμενες λύσεις μέσω υλικού δεν έχουν δώσει ικανοποιητική απάντηση. Επικεντρώνουμε την έρευνά μας σε τρεις βασικές κατευθύνσεις που στοχεύουν στην εξοικονόμηση και βελτιστοποίηση της κατανάλωσης ενέργειας σε διαφορετικά επίπεδα. Κοινός στόχος είναι η μείωση του κόστους επικοινωνίας, μέσω της ανάδειξης καινοτόμων τεχνικών που δίνουν ώθηση στην ανάπτυξη νέων αλγορίθμων. Συγκεκριμένα, διερευνήσαμε τεχνικές κατανεμημένης προσαρμογής της λειτουργίας ενός πρωτοκόλλου όπου χρησιμοποιούμε πληροφορία διαθέσιμη τοπικά σε κάθε κόμβο ώστε με καθαρά τοπικές επιλογές, να βελτιώσουμε τη συνολική συμπε- ριφορά ενός πρωτοκόλλου. Επίσης προτείνουμε τεχνικές τοπικής συλλογής και εκμετάλλευσης περιορισμένης γνώσης των συνθηκών του δικτύου. Με ενεργειακά αποδοτικό τρόπο συλλέγουμε επιπλέον πληροφορία που χρησιμοποιούμε προκειμένου να επιτευχθούν βελτιστοποιήσεις όπως ο σχηματισμός ενεργειακά αποδοτικών, χαμηλής καθυστέρησης και ανθεκτικών σε σφάλματα μονοπατιών για μετάδοση δεδομένων. Ακόμα, διερευνούμε τεχνικές διαχείρισης της κινητικότητας σε περιπτώσεις δικτύων όπου χαρακτηριστικό είναι η κίνηση τόσο του κέντρου ελέγχου όσο και των συσκευών αισθητήρων. Εξετάσαμε μεθόδους διαπέρασης και κάλυψης του δικτύου από κινητά κέντρα ελέγχου που βασίζονται σε πιθανοτική κίνηση που ευνοεί την επίσκεψη κάποιων περιοχών με βάση τοπικά κριτήρια (συχνότητα προηγούμενων επισκέψεων, τοπική πυκνότητα δικτύου). Οι αλγόριθμοι που αναπτύσσουμε βασισμένοι σε αυτές τις τεχνικές λειτουργούν α) σε επίπεδο διαχείρισης της ίδιας της συσκευής, β) σε επίπεδο πρωτοκόλλου δρομολόγησης και γ) συνολικά σε επίπεδο δικτύου, αναδεικνύοντας μακροσκοπική συμπεριφορά από τοπικές αλληλεπιδράσεις. Οι αλγόριθμοι εφαρμόζονται σε περιπτώσεις δικτύων με διαφορές στην πυκνότητα, κατανομή κόμβων, διαθέσιμη ενέργεια αλλά και με ριζικές διαφοροποιήσεις στο μοντέλο αφού εξετάζουμε δίκτυα με παρουσία σφαλμάτων, σταδιακή ανάπτυξη κόμβων ακόμα και με κινούμενους κόμβους. Σε όλες αυτές τις περιπτώσεις οι τεχνικές μας πετυχαίνουν σημαντικά οφέλη γεγονός που αναδεικνύει την αξία τους σαν εργαλεία αλγοριθμικής σχεδίασης. / -

Η αλματώδης πρόοδος στις ασύρματες επικοινωνίες έχει φέρει ως αποτέλεσμα την δυνατότητα δημιουργίας μικρών σε μέγεθος μικροϋπολογιστικών συστημάτων που έχουν την δυνατότητα ασύρματης διασύνδεσης. Λόγω του μικρού μεγέθους αυτών είναι δυνατή η μεταφορά τους ακόμα και από φυσικά πρόσωπα και άρα προσφέρουν με τον τρόπο αυτό το πλεονέκτημα φορητότητας. Παράλληλα η επιθυμία για δημιουργία δικτύων μεγάλης κλίμακας με χρήση τέτοιων συσκευών χωρίς την δυνατότητα σταθερής παροχής ενέργειας δημιούργησε την ανάγκη μικρής εμβέλειας μετάδοσης και άρα πολλαπλών επαναμεταδόσεων ανά πακέτο δεδομένων μέχρι να φτάσει στον τελικό προορισμό του. Το ερευνητικό αντικείμενο αυτής της διδακτορικής διατριβής είναι η πρόταση μίας ολοκληρωμένης ασύρματης δομής που θα παρέχει δυνατότητες ασύρματης διασύνδεσης σε δίκτυα μεγάλης κλίμακας χωρίς ύπαρξη κεντρικής διαχείρισης. Το πρόβλημα της εύρεσης διαδρομών σε ένα ασύρματο δίκτυο κινούμενων αισθητήρων αποτελεί ένα πολύ δύσκολο εγχείρημα, ακόμα δε περισσότερο αν λάβουμε υπόψη μας και το ασύρματο μέσο που είναι ένα μη-ντετερμινιστικό φυσικό μέσο δικτύου. Η ύπαρξη απαιτήσεων πραγματικού χρόνου παρ’ όλες τις δυσκολίες υπάρχει σε εφαρμογές δικτύων κινούμενων αισθητήρων και δυσκολεύει περαιτέρω την σχεδίαση μιας δομής που θα διατηρεί διασυνδεσιμότητα μεταξύ των αισθητήρων του δικτύου ενώ παράλληλα θα ικανοποιεί τις απαιτήσεις πραγματικού χρόνου. Πρόσθετα οι δυναμικές συνθήκες που παρατηρούνται σε ένα ασύρματο δίκτυο κινούμενων αισθητήρων όσον αφορά σημαντικές παραμέτρους λειτουργίας όπως μεταβλητό φορτίο εφαρμογής, ταχύτητα φυσικής κίνησης του κινούμενου αισθητήρα και αριθμός συγκέντρωσης τους στην ίδια ασύρματη περιοχή καθώς και η μη ύπαρξη σταθερής παροχής ενέργειας, δημιουργούν την ανάγκη σχεδίασης μιας ασύρματης δομής που θα έχει την δυνατότητα να προσαρμόζεται στις εκάστοτε συνθήκες του δικτύου. Υποστηρίζοντας δυνατότητα προσαρμογής στις εκάστοτε συνθήκες του δικτύου ενώ παράλληλα εξυπηρετούνται οι απαιτήσεις πραγματικού χρόνου, δημιουργείται η δυνατότητα μείωσης του προσθετόμενου πρωτοκολλικού δικτυακού φόρτου άρα και μείωση της ενεργειακής κατανάλωσης του κινούμενου αισθητήρα. Προχωρώντας περαιτέρω, η λειτουργία του πρωτοκόλλου δρομολόγησης μπορεί επίσης να βελτιστοποιηθεί ώστε να εξυπηρετεί τα δρομολογούμενα πακέτα με μεγαλύτερη επιτυχία. Η παρούσα διδακτορική διατριβή έρχεται να καλύψει την ανάγκη για τεχνικές προσαρμοστικότητας σε ασύρματα δίκτυα στις εκάστοτε συνθήκες του δικτύου και να παρουσιάσει μια πρόταση πρότυπης υλοποίησης που να βελτιστοποιεί την λειτουργία του ασύρματου δικτύου, παρακολουθώντας σε πραγματικό χρόνο κρίσιμες μεταβλητές της λειτουργίας. Τα κυριότερα αποτελέσματα της παρούσας διδακτορικής διατριβής παρουσιάζονται παρακάτω: • Μελέτη και ανάλυση της εν γένη συμπεριφοράς υπαρχόντων προτεινόμενων δομών για την δρομολόγηση σε ασύρματα κινούμενα δίκτυα αισθητήρων. • Σχεδίαση και ανάλυση πρότυπης υβριδικής δομής στηριζόμενη σε γνωστούς αποδεκτούς αλγορίθμους δρομολόγησης. • Μελέτη και ανάλυση των μεταβλητών λειτουργίας και εξαγωγή των κρίσιμων μεταβλητών μέσω των οποίων μπορεί να γίνει η αναγνώριση κατάστασης του ασύρματου δικτύου. • Σχεδίαση, ανάλυση και υλοποίηση πρότυπου αλγορίθμου ελέγχου και προσαρμογής λειτουργίας της ασύρματης δομής στις εκάστοτε συνθήκες λειτουργίας του δικτύου. • Πλήρης υλοποίηση πρότυπης δικτυακής ασύρματης αρχιτεκτονικής με δυνατότητες αναπροσαρμογής σε μεταβλητές συνθήκες δικτύου. • Λήψη και δημοσίευση πλήρους συνόλου μετρήσεων μέσω προσομοίωσης της προτεινόμενης δομής με χρήση παγκοσμίου φήμης λογισμικού προσομοίωσης δικτύων και απόδειξη της επιτυγχανόμενης βελτίωσης λειτουργίας του δικτύου. / The progress in wireless telecommunications has resulted in the creation of small sized microprocessor systems that are wireless enabled. Due to the small size of these systems, they are considered portable since they can even be carried by a person. Furthermore, the need to create large scale wireless networks using such systems, without a fixed power supply, has created the constraint of small communication range for such devices. This leads to multiple retransmissions of data packets in order to reach their final destination within the wireless network. This communication is often referred to as multihop communication. The research objective of this thesis is to propose a new wireless architecture that will provide wireless connectivity for large scale wireless ad-hoc networks without the need of central management. The problem of finding a route, or even worse, the optimal route in a wireless ad-hoc network is very difficult and gets even worse if we consider the nature of the wireless medium that is un-deterministic and probably the less predictable medium used in networks. The need of real time constraints in wireless ad-hoc networks exists however, making even more difficult the design of a wireless architecture that will provide connectivity in the domain of a wireless network while managing to succeed in satisfying the real time constraints. Furthermore the dynamic nature of a wireless mobile network as far as important functional variables are concerned, like application load, speed of node movement, rate of connectivity in the same wireless domain, as well as the lack of a fixed power supply, create the need of adaptivity support, based on network status, in any wireless module designed to address the above problems. Supporting an adaptivity functionality based on the wireless network status, while managing to meet the real time constrains imposed from the application, we manage to lower the overhead of the network protocol, hence reducing the energy consumption of the wireless node. Moving forward, the functionality of the routing protocol itself is enhanced so as to route the data packets to the destination node with higher rates of success. This dissertation manages to fulfill the need for techniques of adaptivity in wireless ad-hoc networks by presenting a new wireless architecture, that is enhancing the general behavior of a wireless network by monitoring in real time various critical network variables and change the protocols behavior to adapt to changing network condition. The more important results of this dissertation are presented below: • Study and analysis of general behavior of already existing routing protocols for ad-hoc wireless networks. • Design and analysis of a prototype hybrid module, based on existing routing algorithms. • Study and analysis of functional variables, extraction of critical functional variables that can be used to identify the status of the wireless network within a certain domain. • Design, analysis and implementation of a prototype algorithm that controls and adapts the general functionality of the wireless module based on the network status. • Implementation prototype of a wireless architecture supporting automatic real time adaptability to network status based on real time monitoring of network variables. • Collection and publication of a full set of tests by using a world wide known software tool to simulate data networks, and proof of the resulted functionality enhancement of the wireless network’s behaviour.

Τα Δίκτυα Αισθητήρων αποτελούνται από ένα μεγάλο αριθμό μικρών αυτόνομων συσκευών, που αλληλεπιδρούν με το άμεσο περιβάλλον τους μέσω αισθητήρων, συλλέγουν δεδομένα και τα προωθούν προς ένας σταθερό, συνήθως, κέντρο ελέγχου, με αναμεταδόσεις στους ενδιάμεσους κόμβους. Η διαδικασία αυτή έχει ως αποτέλεσμα τη μεγάλη κατανάλωση ενέργειας στις συσκευές, ιδιαίτερα σε αυτές που βρίσκονται κοντά στο κέντρο ελέγχου, αφού πρέπει να αναμεταδίδουν και τα δεδομένα που φτάνουν από το υπόλοιπο δίκτυο προς το κέντρο ελέγχου. Για την επίτευξη μιας πιο ισορροπημένης και αποδοτικής διαδικασίας συλλογής δεδομένων, τα τελευταία χρόνια έχει υιοθετηθεί μια νέα προσέγγιση, όπου το κέντρο ελέγχου είναι κινητό. Η βασική ιδέα είναι ότι το κέντρο ελέγχου διαθέτει σημαντικά και εύκολα ανανεώσιμα αποθέματα ενέργειας, επομένως μπορεί να κινείται στην περιοχή όπου έχει αναπτυχθεί το δίκτυο αισθητήρων, αναλαμβάνοντας να συλλέξει τα δεδομένα από τους κόμβους με πολύ μικρό κόστος. Ωστόσο, η μετάδοση των δεδομένων μπορεί να παρουσιάζει σημαντικές καθυστερήσεις. Συλλογή δεδομένων με προσαρμοστικούς χρόνους αναμονής: Στην παρούσα διατριβή αναπτύχθηκαν πρωτόκολλα ελέγχου της κίνησης ενός κέντρου ελέγχου σε δίκτυο αισθητήρων με ανομοιογενή ανάπτυξη των κόμβων αισθητήρων, με στόχο την αποδοτική, ως προς την ενέργεια και τον χρόνο παράδοσης, συλλογή των δεδομένων. Πιο συγκεκριμένα, αρχικά παρουσιάζεται ένα πρωτόκολλο με βάση το οποίο το κέντρο ελέγχου διαιρεί νοητά το δίκτυο σε περιοχές τις οποίες και επισκέπτεται διαδοχικά, σταματώντας σε κάθε περιοχή για ένα συγκεκριμένο χρονικό διάστημα, ώστε να συλλέξει τα δεδομένα. Προτείνουμε δύο τρόπους κίνησης του κέντρου ελέγχου, ντετερμινιστικό και τυχαίο. Στην τυχαία κίνηση, η επιλογή της επόμενης περιοχής την οποία θα επισκεφτεί το κέντρο ελέγχου γίνεται με τυχαίο τρόπο, εισάγοντας όμως ένα όρο μεροληψίας, έτσι ώστε να προτιμούνται περιοχές που έχουν δεχτεί λιγότερες επισκέψεις. Επιπλέον η μέθοδός μας αποφασίζει το χρόνο παύσης σε κάθε περιοχή λαμβάνοντας υπόψιν κάποιες βασικές παραμέτρους του δικτύου, όπως τα αρχικά αποθέματα ενέργειας των κόμβων αισθητήρων και την πυκνότητα της κάθε περιοχής, έτσι ώστε να παραμένει περισσότερο χρόνο σε περιοχές με μεγαλύτερη πυκνότητα, άρα και μεγαλύτερη ποσότητα πληροφορίας. Με τον τρόπο αυτό επιτυγχάνεται η γρήγορη κάλυψη όλου του δικτύου, καθώς επίσης και η δίκαιη εξυπηρέτηση των επιμέρους περιοχών του δικτύου. Προσαρμοστικοί τυχαίοι περίπατοι Στη συνέχεια, μελετάται η χρήση τυχαίων περιπάτων κατά την κίνηση του κέντρου ελέγχου σε δίκτυα αισθητήρων με στόχο την επίτευξη ενός ικανοποιητικού σημείου ισορροπίας μεταξύ κατανάλωσης ενέργειας και καθυστέρησης στην παράδοση των μηνυμάτων. Για την ικανοποίηση του στόχου αυτού, προτείνουμε τρεις νέους τυχαίους περιπάτους, τους α) Τυχαίος Περίπατος με Αδράνεια, κατά τον οποίο το κινούμενο αντικείμενο τείνει να διατηρεί την ίδια κατεύθυνση στην κίνησή του όσο ανακαλύπτει κόμβους αισθητήρων που δεν έχει επισκεφτεί και αλλάζει την κατεύθυνσή του όταν φτάνει σε κόμβους που έχει ξαναεπισκεφτεί, β) Explore-and-Go, κατά τον οποίο το κινούμενο αντικείμενο τείνει να εκτελεί μια Brownian κίνηση γύρω από την περιοχή του όσο υπάρχουν κόμβοι που δεν έχουν δεχτεί επίσκεψη, γ) Curly Random Walk, όπου το κινούμενο αντικείμενο διαπερνάει όλη την περιοχή του δικτύου ξεκινώντας από το κέντρο και επεκτείνοντας την κίνησή του με συνεχόμενες κυκλικές κινήσεις προς τα έξω. Για την εφαρμογή των τυχαίων περιπάτων χρησιμοποιούμε ένα νοητό πλέγμα ώστε να καλύπτουμε την περιοχή του δικτύου αισθητήρων• οι περίπατοι κινούνται πάνω στους κόμβους του πλέγματος. Αν και στις περισσότερες περιπτώσεις οι τυχαίοι περίπατοι μελετώνται σε Gn,p και Grid γράφους, τα δίκτυα αισθητήρων μοντελοποιούνται με μεγαλύτερη ακρίβεια χρησιμοποιώντας το μοντέλο των Random Geometric Graphs (RGG), εφόσον έτσι αναπαρίσταται καλύτερα η χωρική εγγύτητα του δικτύου. Οι παραπάνω τυχαίοι περίπατοι δεν δίνουν τα επιθυμητά αποτελέσματα όταν τρέχουν σε RGG. Έτσι οδηγηθήκαμε στο σχεδιασμό ενός νέου τυχαίου περιπάτου, του γ-Stretched Random Walk, η βασική ιδέα του οποίου είναι να μεροληπτεί υπέρ της επίσκεψης των πιο μακρινών γειτόνων του τρέχοντος κόμβου έτσι ώστε να μειώσει στο ελάχιστο τις επικαλύψεις στις επισκέψεις. Αλγόριθμοι που λαμβάνουν υπόψιν την ηλεκτρομαγνητική ακτινοβολία στο δίκτυο: Εκτός από τη μελέτη της κίνησης του κέντρου ελέγχου σε δίκτυα αισθητήρων, στη διατριβή αυτή παρουσιάζεται μια πρώτη προσπάθεια μελέτης θεμάτων σχετικά με την επίγνωση της εκπομπή ακτινοβολίας σε περιβάλλοντα όπου λειτουργούν πολλαπλά ετερογενή ασύρματα δίκτυα. Ως ακτινοβολία σε ένα σημείου του τρισδιάστατου χώρου καλούμε τη συνολική ποσότητητα ηλεκτρομαγνητικής ακτινοβολίας που δέχεται το σημείο αυτό. Έτσι, καταρχάς μελετάμε σε αναλυτικό επίπεδο την ακτινοβολία σε διάφορες γνωστές τοπολογίες (τυχαίες, πλέγματα) και κατόπιν επικεντρώνουμε το ενδιαφέρον μας στην εύρεση ενός μονοπατιού ελάχιστης ακτινοβολίας το οποίο ακολουθείται από κάποιο άτομο που κινείται στην περιοχή που καλύπτεται από ένα ασύρματο δίκτυο αισθητήρων. Προτείνουμε τρεις ευρετικές μεθόδους για την εύρεση του μονοπατιού καθώς το άτομο κινείται, ενώ υπολογίζουμε και την οffline λύση χρησιμοποιώντας τον αλγόριθμο ελάχιστου μονοπατιού. Κατόπιν, εξετάζουμε το θεμελιώδες πρόβλημα της διάδοσης των δεδομένων σε ασύρματα δίκτυα αισθητήρων, προσπαθώντας τόσο να παραμείνει γρήγορη η διαδικασία παράδοσης των μηνυμάτων, παράλληλα όμως και η συνολική ηλεκτρομαγνητική ακτινοβολία που παράγεται από τις συνεχείς ασύρματες μεταδόσεις να διατηρηθεί σε χαμηλά επίπεδα. Αυτό επιτυγχάνεται αρχικά χρησιμοποιώντας κάποιες άπληστες ευρετικές μεθόδους που όμως λαμβάνουν υπόψιν την ακτινοβολία. Επιπλέον, οι μέθοδοι αυτοί συνδυάζονται με μεθόδους που πραγματοποιούν back-off στο χρόνο, χρησιμοποιώντας τοπικές ιδιότητες του δικτύου (όπως ο αριθμός γειτόνων, η απόσταση από το κέντρο ελέγχου), έτσι ώστε «απλωθεί» κατά κάποιο τρόπο η ακτινοβολία τόσο ως προς το χρόνο αλλά και ως προς το χώρο. Τα προτεινόμενα πρωτόκολλα αξιολογήθηκαν πειραματικά μέσω προσομοίωσης, χρησιμοποιώντας ποικίλες τιμές για βασικές παραμέτρους του δικτύου και σύγκρινοντάς τα με σχετικές υπάρχουσες ευρέως αποδεκτές μεθόδους. Συστημικές Εφαρμογές: Τέλος, στη διατριβή παρουσιάζονται κάποιες συστημικές εφαρμογές ασύρματων δικτύων αισθητήρων σε κτίρια. Συγκεκριμένα, η πρώτη εφαρμογή αναλαμβάνει σε περίπτωση ανίχνευσης φωτιάς, την εύρεση του ελάχιστου μονοπατιού μακριά από το σημείο όπου έγινε η ανίχνευση. Επιπλέον, παρέχει καθοδήγηση στους ενοίκους του κτιρίου (οι οποίοι μοντελοποιούνται από ένα κινούμενο ρομπότ) έτσι ώστε να εγκαταλείψουν με ασφάλεια το κτίριο. Η επόμενη εφαρμογή παρουσιάζει τη δυνατότητα της απρόσκοπτης διασύνδεσης αυτοματισμών έξυπνων κτιρίων, αποτελούμενων από ενσωματωμένα συστήματα, στο διαδίκτυο και την αφαιρετικοποίησή τους ως απλά web services. Η προσέγγιση αυτή έχει στόχο την δημιουργία ενός ευέλικτου, εύκολα κλιμακώσιμου συστήματος που είναι προσβάσιμο και ελεγχόμενο απομακρυσμένα. Η προσέγγιση που ακολουθήθηκε και παρουσιάζεται στην παρούσα διατριβή περιλαμβάνει την ανάπτυξη ενός αριθμού αισθητήρων μέσα σε ένα κτίριο, οι οποίοι αποκτούν IPv6 διεύθυνση ώστε να είναι προσβάσιμοι διαδικτυακά, ενώ παράλληλα διασυνδέονται με ηλεκτρικές συσκευές του κτιρίου για σχηματισμό αυτοματισμών. Τέλος αναπτύχθηκε μία web εφαρμογή για απομακρυσμένη διαχείριση του δικτύου και του κτιρίου γενικότερα. / Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their environment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays. Data collection with biased stop times: In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, we first propose a protocol, where the sink partitions the network area in equal square regions and then performs a network traversal by visiting each area sequentially. Also, it pauses in each area for a certain amount of time, in order to collect the data. Two network traversal methods are proposed, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region. Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only. Adaptive random walks: Afterwards, in order to achieve satisfactory energy-latency trade-offs the use of random walks for the sink' s motion pattern is studied. Towards this direction three new random walks evaluated on a grid overlaying the wireless sensor network are proposed. The first one is the Random Walk with Inertia where the sink tends to keep the same direction as long as it discovers new nodes, while changing direction when it encounters already visited ones. The second one is the Explore-and-Go Random Walk, where as long as there are undiscovered nodes on the nearby sub-regions of the network it tends to make a Brownian-like motion until all this area is covered. When no new sensors are discovered, it performs a more or less straight-line walk in order to move to a different, possibly unvisited area. The last one is the Curly Random Walk where the sink traverses the network area beginning from the center and expanding its traversal to the entire network area with consecutive circular-like moves. In random walk studies the Gn,p and Grid graph models are well established. However, wireless sensor networks are more accurately modeled via Random Geometric Graphs (RGG), as RGG better capture certain characteristics of WSN's such as link existence dependencies of neighbouring nodes due to geometric proximity. The above mentioned random walks do not behave well on this particular graph model, thus a new random walk was defined, the so called γ-stretched random walk. Its basic idea is to favour visiting distant neighbours of the current node towards reducing node overlap. Radiation-aware algorithms: Except for the issue of mobility in wireless sensor networks, in this work we also attempt (probably for the first time from a distributed networking perspective) to investigate the aspect of electromagnetic radiation in modern and future heterogeneous wireless networks. We call “radiation” at a target elementary surface the total amount of electromagnetic quantity (in terms of energy or power density) it is exposed to. Thus, we first evaluate, both mathematically and by simulation, the radiation in well known sensor network topologies (random, grid) and then focus on the minimum radiation path problem of finding low radiation trajectories for a person moving in a sensor network. We propose three online heuristics and then we identify the (offline) optimum path given by the shortest paths' algorithm. Afterwards, we focus on the fundamental problem of efficient data propagation in wireless sensor networks, trying to keep latency low while maintaining at low levels the radiation cumulated by wireless transmissions. We first propose greedy and oblivious routing heuristics that are radiation aware. We then combine them with temporal back-off schemes that use local properties of the network (e.g. number of neighbours, distance from sink) in order to “spread” radiation in a spatio-temporal way. Al the proposed protocols were evaluated via simulation, in diverse network settings and comparatively to related state of the art solutions. Systems and applications: Finally, in this work we present two applications of wireless sensor networks in buildings. More specifically, the first application, in the event of a fire inside a monitored building, uses the information from the deployed sensor network in order to find the shortest safest path away from the emergency and provides navigation guidance to the occupants (modelled by a mobile robot), in order to safely evacuate the building. The second application addresses networked embedded systems enabling the seamless interconnection of smart building automations to the Internet and their abstractions as web services, using the latest technologies based on IPv6, such as 6LOWPAN, COAP and RESTLess Architecture.

Η διπλωματική εργασία διαπραγματεύεται την εφαρμοσιμότητα του peer-to-peer υπολογισμού και τεχνικών στα ασύρματα κινητά ad-hoc δίκτυα και στα δίκτυα αισθητήρων. Παρουσιάζεται μια παραλλαγή ενός νέου P2P πρωτοκόλλου (Energy Level Distributed Tree) που σαν κύρια λειτουργία του έχει την αύξηση του προσδόκιμου λειτουργίας ενός δικτύου αισθητήρων. Επίσης, γίνεται αναφορά στα πιο δημοφιλή εργαλεία προσομοίωσης για P2P πρωτόκολλα δρομολόγησης και παρουσιάζεται ένα νέο εργαλείο, d-p2p-sim, με δυνατότητα προσομοίωσης εκατομμυρίων κόμβων. Τέλος, εξετάζουμε την απόδοση ενός νέου P2P πρωτοκόλλου δρομολόγησης, του Nested Balanced Distributed Tree, που απαντά με βέλτιστο τρόπο ερωτήμα ακριβούς ταιριάσματος και ερωτήματα διαστήματος παρουσιάζοντας παράλληλα δύο νέους αλγορίθμους αναζήτησης για αυτό. / In this master thesis we study the applicability of the peer-to-peer computing and techniques on wireless ad-hoc networks and sensor-nets. We propose a simplified mapping of an optimal P2P protocol (NBDT) onto sensor-nets, the so called Energy Level Distributed Tree (ELDT), which has one main operation: the life expectancy of a sensor-net. Furthermore, are examined the most popular Peer-to-Peer simulators and is presented a new distributed simulator for P2P routing algorithms. The key feature of the proposed simulator is the ability to simulate millions of peers. Finally, is presented a revised version of the NBDT protocol which is hot-spot free and achieves a better load distribution introducing a negligible routing overhead.