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

Το Διαδίκτυο αναμφίβολα αποτελεί την μεγαλύτερη ανακάλυψη στον τομέα διάδοσης της πληροφορίας από την εποχή του Γουτεμβέργιου και της τυπογραφίας, έχοντας ριζικά αλλάξει τον τρόπο επικοινωνίας και αλληλεπίδρασης των ανθρώπων. Στον πυρήνα του Διαδικτύου βρίσκονται τεχνολογίες οι οποίες αναπτύχθηκαν με σκοπό την επίτευξη επικοινωνίας ανάμεσα σε ετερογενή συστήματα και δίκτυα. Με αυτό τον τρόπο, ενώ το Διαδίκτυο αρχικά αποτελείτο αποκλειστικά από δίκτυα υπολογιστών, στην συνέχεια ενσωματώθηκαν σε αυτό και άλλοι τύποι δικτύων όπως τα σταθερά τηλεφωνικά δίκτυα, τα δίκτυα κινητής τηλεφωνίας, τα δορυφορικά δίκτυα, κ.α. Πλέον το Διαδίκτυο αποτελεί ένα μετα-δίκτυο δικτύων το οποίο συνεχίζει να επεκτείνεται και οι αντίστοιχες υποστηρικτικές τεχνολογίες συνεχίζουν να εξελίσσονται. Στο ορατό μέλλον, στο Διαδίκτυο θα προστεθούν και τα ενσωματωμένα συστήματα ελέγχου πραγματώνοντας με αυτό τον τρόπο το όραμα του Διαδικτύου των Αντικειμένων (Internet of Things). Η κύρια υποστηρικτική τεχνολογία για το Διαδίκτυο των Αντικειμένων είναι τα Ασύρματα Δίκτυα Αισθητήρων (Α.Δ.Α.). Τα Ασύρματα Δίκτυα Αισθητήρων αποτελούν μία ειδική κατηγορία κατανεμημένων και αυτό-οργανούμενων δικτύων τα οποία υπόσχονται να γεφυρώσουν το χάσμα ανάμεσα στον φυσικό και τον ψηφιακό κόσμο. Αποτελούνται από μικρές αυτόνομες συσκευές, περιορισμένων υπολογιστικών δυνατοτήτων, εξοπλισμένες με ψηφιακούς αισθητήρες. Οι συσκευές αυτές συλλέγουν δεδομένα και δουλεύοντας συνεργατικά μεταξύ τους, τα διαδρομούν μέσω πολύ-βηματικών μεταδόσεων. Με αυτό τον τρόπο, αν και ο κάθε κόμβος του δικτύου χαρακτηρίζεται από σημαντικούς περιορισμούς (στην υπολογιστική ισχύ, την ενέργεια, την ασύρματη επικοινωνία, κ.α.) τα δίκτυα τα οποία συντίθενται είναι σε θέση να φέρουν εις πέρας δύσκολα υπολογιστικά προβλήματα, παράγοντας και διακινώντας μεγάλες ποσότητες πληροφορίας. Η διατριβή που κρατάτε στα χέρια σας αποτελεί προϊόν πρωτότυπης έρευνας σε ζητήματα αποδοτικής συλλογής δεδομένων από Ασύρματα Δίκτυα Αισθητήρων, ενώ έχει παρουσιαστεί σε γνωστά επιστημονικά περιοδικά και ανταγωνιστικά συνέδρια διεθνούς κύρους. Το κείμενο είναι οργανωμένο σε τρεις ενότητες. Στην πρώτη ενότητα μελετώνται θέματα κίνησης στα Ασύρματα Δίκτυα Αισθητήρων. Πιο συγκεκριμένα προτείνεται μια οικογένεια ευρετικών αλγορίθμων για την γρήγορη και αποδοτική συλλογή δεδομένων από δίκτυα τα οποία χαρακτηρίζονται από έντονη και δυναμική κινητικότητα των κόμβων. Επιπλέον, μελετώνται οι τυχαίοι περίπατοι ως απλές, αποδοτικές στρατηγικές κίνησης κέντρων ελέγχου για την συλλογή δεδομένων σε δίκτυα αισθητήρων με στατικούς κόμβους. Για την αναπαράσταση των δικτύων χρησιμοποιούνται τα μοντέλα του πλέγματος και των τυχαίων γεωμετρικών γράφων. Στην δεύτερη ενότητα μελετώνται δύο πρόσφατα θεμελιωμένα προβλήματα στα Ασύρματα Δίκτυα Αισθητήρων (σχετιζόμενα με πρόσφατες τεχνολογικές εξελίξεις) και παρουσιάζονται αντίστοιχες πρωτότυπες προσεγγίσεις. Το πρώτο πρόβλημα εξετάζει την διαδρόμηση δεδομένων με πρωτόκολλα χαμηλής ηλεκτρομαγνητικής ακτινοβολίας υπό το πρίσμα των Ασύρματων Δικτύων Αισθητήρων. Ωστόσο, πρέπει να σημειωθεί ότι το πρόβλημα ανάγεται ευρύτερα σε ετερογενή ασύρματα δίκτυα. Το δεύτερο πρόβλημα εξετάζει την διαχείριση ενέργειας σε Ασύρματα Δίκτυα Αισθητήρων στα οποία μία ειδική μονάδα κινούμενη μέσα στο δίκτυο επαναφορτίζει τους κόμβους μέσω ασύρματης μετάδοσης ενέργειας. Στην τρίτη ενότητα παρουσιάζονται μια σειρά πρότυπων συστημάτων και εφαρμογών του Μελλοντικού Διαδικτύου, που αναπτύχθηκαν στα πλαίσια της παρούσας διατριβής. Τα συστήματα συνδυάζουν τα Ασύρματα Δίκτυα Αισθητήρων με την νέας γενιάς στοίβα πρωτοκόλλων επικοινωνίας IPv6 καθιστώντας δυνατή την απρόσκοπτη και διαφανή επικοινωνία των κόμβων του δικτύου με το Διαδίκτυο και τον έξω κόσμο. Οι εφαρμογές των συστημάτων περιλαμβάνουν την ανάπτυξη ενός έξυπνου/πράσινου δωματίου και αντίστοιχων σεναρίων χρήσης του με δυνατότητες απομακρυσμένου ελέγχου μέσω Διαδικτύου (προσωποποίηση της συμπεριφοράς του δωματίου στον χρήστη, αλληλεπίδραση του δωματίου στην φυσική παρουσία, ασφαλής εκκένωση κτηρίου σε συνθήκες κινδύνου, κ.α.), την ανάπτυξη πρότυπου συστήματος έξυπνης άρδευσης, τον εντοπισμό θέσης με υψηλή ακρίβεια σε εσωτερικό χώρο, καθώς και την επεξεργασία κοινωνικής σηματοδότησης κατά την διάρκεια ανθρώπινων αλληλεπιδράσεων. Με την παρούσα διδακτορική διατριβή κλείνει ένας κύκλος έρευνας που διήρκεσε κάτι λιγότερο από πέντε χρόνια. Ωστόσο, αρκετά θέματα θα αποτελέσουν και στο μέλλον πεδίο έντονης ερευνητικής δραστηριότητας. Η εκπεμπόμενη ηλεκτρομαγνητική ακτινοβολία κατά την διάρκεια ασύρματων μεταδόσεων δεδομένων είναι ένα αμφιλεγόμενο ζήτημα από την πλευρά της ασφάλειας της δημόσιας υγείας. Πιστεύουμε όμως ότι αξίζει να μελετηθεί και από τον κλάδο της Επιστήμης των Υπολογιστών καθώς το πλήθος των ασύρματων δικτύων και η πυκνότητα της περιρρέουσας ακτινοβολίας στην καθημερινή μας ζωή ολοένα και αυξάνεται. Ένα δεύτερο πεδίο έρευνας αναδύεται από την πραγμάτωση του Διαδικτύου των Αντικειμένων και τις δυνατότητες που αυτό παρέχει στα πλαίσια του Μελλοντικού Διαδικτύου. Ενδεικτικά αναφέρεται η ανάδειξη νέων μοντέλων δικτύων στα πρότυπα των κοινωνικών δικτύων, τα οποία θα περιλαμβάνουν αλληλεπιδράσεις ανάμεσα σε ανθρώπους και σε αντικείμενα. Καλή Ανάγνωση. / The Internet is undoubtedly the biggest breakthrough in dissemination of information since the era of Gutenberg and the printing press that has radically changed the way of communication and interaction among people. At the core of the Internet lie technologies which are developed to achieve communication between heterogeneous systems and networks. In this way, while the Internet initially consisted exclusively of computer networks, it then incorporated other types of networks as well, such as land line telephone networks, cellular networks, satellite networks, social networks and so on. Nowadays, the Internet is a meta-network of networks which continues to expand and relevant enabling technologies continue to evolve. In the foreseeable future, the Internet will also include embedded control systems, thus realizing the vision of the Internet of Things. The main enabling technology of the Internet of Things vision is Wireless Sensor Networks (WSNs). Wireless Sensor Networks are a special class of distributed and self-organized networks which promise to bridge the gap between the physical and digital world. A WSN consists of small autonomous devices with minimal computational capabilities that are equipped with digital sensors. These devices collect data from their immediate environment and working collaboratively with each other, propagate them via multi-hop transmissions. In this way, although each node of the network is characterized by significant limitations (in terms of computational power, energy reserves, wireless communication capabilities, etc.) the formed networks are able to carry out difficult computational problems and thus to generate and route large amounts of information. The dissertation that you hold in your hands is the product of original and novel research on several aspects of efficient data collection from Wireless Sensor Networks. Corresponding research findings have been published in prestigious scientific journals and competitive, peer-reviewed international conferences. The dissertation is organized into three parts. In the first part mobility aspects of Wireless Sensor Networks are studied. More specifically, a family of heuristic algorithms is proposed for fast and efficient data collection in networks that are characterized by diverse and dynamic node mobility. Moreover, random walks are studied as simple, efficient mobility strategies for data collection in sensor networks in which sensor motes are stationary. Sensor networks are modeled either as Grids or as Random Geometric Graphs. In the second part two recently acquired problems in Wireless Sensor Networks (associated with recent technological advances) are studied. The first problem examines data routing protocols that yield low electromagnetic radiation in the context of Wireless Sensor Networks. The second problem examines energy management in Wireless Sensor Networks in which a special unit (namely the Charger) traverses the network area and is able to recharge sensor motes via wireless energy transfer. In the third part a series of prototype systems and applications for the Future Internet that have been developed in the context of this dissertation are presented. These systems combine Wireless Sensor Networks with the new generation, IPv6 Internet protocol stack, thus allowing seamless and transparent communication between sensor motes and the rest of the Internet world. These systems include the development of a smart / green room and corresponding use-case scenarios (room adaptation to human presence, safe evacuation in emergency conditions, etc.), the development of a prototype smart irrigation system, fine grained in-door localization, and social signal processing. This dissertation concludes a research cycle, which lasted a little less than five years. However, there is more than enough space for future research. The emitted electromagnetic radiation during wireless data transmissions is a controversial issue in terms of public health. However, we believe that it worth’s to be studied from an ICT point of view as the number of wireless networks in our everyday life keeps growing. A second area of research emerges from the realization of the Internet of Things vision and the opportunities it provides as part of the Future Internet; for instance the emergence of a new social network paradigm, that will capture interactions between humans and objects.

Τα Δίκτυα Αισθητήρων αποτελούνται από ένα μεγάλο αριθμό μικρών αυτόνομων συσκευών, που αλληλεπιδρούν με το άμεσο περιβάλλον τους μέσω αισθητήρων, συλλέγουν δεδομένα και τα προωθούν προς ένας σταθερό, συνήθως, κέντρο ελέγχου, με αναμεταδόσεις στους ενδιάμεσους κόμβους. Η διαδικασία αυτή έχει ως αποτέλεσμα τη μεγάλη κατανάλωση ενέργειας στις συσκευές, ιδιαίτερα σε αυτές που βρίσκονται κοντά στο κέντρο ελέγχου, αφού πρέπει να αναμεταδίδουν και τα δεδομένα που φτάνουν από το υπόλοιπο δίκτυο προς το κέντρο ελέγχου. Για την επίτευξη μιας πιο ισορροπημένης και αποδοτικής διαδικασίας συλλογής δεδομένων, τα τελευταία χρόνια έχει υιοθετηθεί μια νέα προσέγγιση, όπου το κέντρο ελέγχου είναι κινητό. Η βασική ιδέα είναι ότι το κέντρο ελέγχου διαθέτει σημαντικά και εύκολα ανανεώσιμα αποθέματα ενέργειας, επομένως μπορεί να κινείται στην περιοχή όπου έχει αναπτυχθεί το δίκτυο αισθητήρων, αναλαμβάνοντας να συλλέξει τα δεδομένα από τους κόμβους με πολύ μικρό κόστος. Ωστόσο, η μετάδοση των δεδομένων μπορεί να παρουσιάζει σημαντικές καθυστερήσεις. Συλλογή δεδομένων με προσαρμοστικούς χρόνους αναμονής: Στην παρούσα διατριβή αναπτύχθηκαν πρωτόκολλα ελέγχου της κίνησης ενός κέντρου ελέγχου σε δίκτυο αισθητήρων με ανομοιογενή ανάπτυξη των κόμβων αισθητήρων, με στόχο την αποδοτική, ως προς την ενέργεια και τον χρόνο παράδοσης, συλλογή των δεδομένων. Πιο συγκεκριμένα, αρχικά παρουσιάζεται ένα πρωτόκολλο με βάση το οποίο το κέντρο ελέγχου διαιρεί νοητά το δίκτυο σε περιοχές τις οποίες και επισκέπτεται διαδοχικά, σταματώντας σε κάθε περιοχή για ένα συγκεκριμένο χρονικό διάστημα, ώστε να συλλέξει τα δεδομένα. Προτείνουμε δύο τρόπους κίνησης του κέντρου ελέγχου, ντετερμινιστικό και τυχαίο. Στην τυχαία κίνηση, η επιλογή της επόμενης περιοχής την οποία θα επισκεφτεί το κέντρο ελέγχου γίνεται με τυχαίο τρόπο, εισάγοντας όμως ένα όρο μεροληψίας, έτσι ώστε να προτιμούνται περιοχές που έχουν δεχτεί λιγότερες επισκέψεις. Επιπλέον η μέθοδός μας αποφασίζει το χρόνο παύσης σε κάθε περιοχή λαμβάνοντας υπόψιν κάποιες βασικές παραμέτρους του δικτύου, όπως τα αρχικά αποθέματα ενέργειας των κόμβων αισθητήρων και την πυκνότητα της κάθε περιοχής, έτσι ώστε να παραμένει περισσότερο χρόνο σε περιοχές με μεγαλύτερη πυκνότητα, άρα και μεγαλύτερη ποσότητα πληροφορίας. Με τον τρόπο αυτό επιτυγχάνεται η γρήγορη κάλυψη όλου του δικτύου, καθώς επίσης και η δίκαιη εξυπηρέτηση των επιμέρους περιοχών του δικτύου. Προσαρμοστικοί τυχαίοι περίπατοι Στη συνέχεια, μελετάται η χρήση τυχαίων περιπάτων κατά την κίνηση του κέντρου ελέγχου σε δίκτυα αισθητήρων με στόχο την επίτευξη ενός ικανοποιητικού σημείου ισορροπίας μεταξύ κατανάλωσης ενέργειας και καθυστέρησης στην παράδοση των μηνυμάτων. Για την ικανοποίηση του στόχου αυτού, προτείνουμε τρεις νέους τυχαίους περιπάτους, τους α) Τυχαίος Περίπατος με Αδράνεια, κατά τον οποίο το κινούμενο αντικείμενο τείνει να διατηρεί την ίδια κατεύθυνση στην κίνησή του όσο ανακαλύπτει κόμβους αισθητήρων που δεν έχει επισκεφτεί και αλλάζει την κατεύθυνσή του όταν φτάνει σε κόμβους που έχει ξαναεπισκεφτεί, β) 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.

Έστω $V$ ένα σύνολο $n$ κορυφών και έστω ${\cal M}$ ένα πεπερασμένα αριθμήσιμο σύνολο $m$ ετικετών. Ένα γράφημα ετικετών προκύπτει αν αντιστοιχήσουμε σε κάθε κορυφή $v \in V$ ένα υποσύνολο $S_v$ του ${\cal M}$ και στη συνέχεια ενώσουμε όποιες κορυφές έχουν κοινά στοιχεία στα αντίστοιχα σύνολα ετικετών τους. Η παρούσα διδακτορική διατριβή ασχολείται με την εξέταση συνδυαστικών ιδιοτήτων και το σχεδιασμό και ανάλυση αλγορίθμων που σχετίζονται με δυο μοντέλα τυχαίων γραφημάτων που προκύπτουν από την επιλογή των συνόλων $S_v$ με βάση συγκεκριμένες κατανομές. Το πρώτο από αυτά τα μοντέλα ονομάζεται \emph{Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, p}$ (\textlatin{random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ διαμορφώνεται επιλέγοντας ανεξάρτητα κάθε ετικέτα με πιθανότητα $p$. Το δεύτερο μοντέλο ονομάζεται \emph{Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, \lambda}$ (\textlatin{uniform random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ επιλέγεται (ανεξάρτητα για κάθε κορυφή) ισοπίθανα ανάμεσα σε όλα τα υποσύνολα του ${\cal M}$ μεγέθους $\lambda$. Τα μοντέλα αυτά μπορούν να χρησιμοποιηθούν για να μοντελοποιήσουν καταστάσεις που αφορούν θέματα ασφάλειας σε δίκτυα αισθητήρων, αλλά και για την αναπαράσταση των συγκρούσεων (\textlatin{conflicts}) που δημιουργούνται σε περιπτώσεις διαμοιρασμού πόρων. Ακόμα, μπορούν να χρησιμοποιηθούν για τη μοντελοποίηση κοινωνικών γραφημάτων (\textlatin{social graphs}) στα οποία δυο οντότητες συνδέονται όταν έχουν κάποιο κοινό χαρακτηριστικό. Στο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, p}$ μελετάμε καταρχήν το πρόβλημα της ύπαρξης κύκλων \textlatin{Hamilton}. Συγκεκριμένα, αποδεικνύουμε ένα άνω φράγμα για την πιθανότητα επιλογής ετικετών $p$ έτσι ώστε κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ να περιέχει ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1 καθώς το $n$ τείνει στο άπειρο. Ακόμα, αναλύουμε δυο πιθανοτικούς αλγορίθμους που, για ορισμένες τιμές των παραμέτρων $m, p$ του μοντέλου, καταφέρνουν να κατασκευάσουν ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1, δηλαδή σχεδόν πάντα. Επίσης, δείχνουμε ότι σχεδόν κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ έχει καλή επεκτασιμότητα (\textlatin{expansion}), ακόμα και για $p$ πολύ κοντά στο κατώφλι συνεκτικότητας του μοντέλου. Στη συνέχεια, δίνουμε βέλτιστα άνω φράγματα (που ισχύουν με πιθανότητα που τείνει στο 1 σε ένα ευρύ πεδίο τιμών των παραμέτρων του μοντέλου) για σημαντικές ποσότητες που αφορούν τυχαίους περιπάτους σ ε στιγμιότυπα του ${\cal G}_{n, m, p}$ όπως ο χρόνος μίξης (\textlatin{mixing time}) και ο χρόνος κάλυψης (\textlatin{cover time}). Στο Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, \lambda}$ μελετάμε την ύπαρξη κύκλων \textlatin{Hamilton} σε ένα ορισμένο πεδίο τιμών των παραμέτρων $m, \lambda$ του μοντέλου. Τέλος, υπολογίζουμε με τη βοήθεια της Πιθανοτικής Μεθόδου το κατώφλι ύπαρξης ανεξάρτητων συνόλων κορυφών. / Let $V$ be a set of $i$ vertices and let ${\cal M}$ be a finite set of $m$ labels. An intersection graph is then constructed by assigning to each vertex $v \in V$ a subset $S_v$ of ${\cal M}$ and then connecting every pair of vertices that have common labels in their corresponding label sets. This thesis concerns the study of combinatorial properties, as well as the design and analysis of algorithms on two kinds of random intersection graphs models that arise from different choices of the distribution that we use to construct the sets $S_v$. In the first of these models, called \emph{Random Intersection Graphs Model} ${\cal G}_{n, m, p}$, each set of labels $S_v$ is constructed by choosing independently each label with probability $p$. In the second model, called \emph{Uniform Random Intersection Graphs Model} ${\cal G}_{n, m, \lambda}$, each label set $S_v$ is selected equiprobably (and independently for each vertex $v$) among all subsets of ${\cal M}$ of size $\lambda$. These models can be used to abstract situations that concern the efficient and secure communication in sensor networks, but can also be used to model the conflicts that occur in oblivious resource sharing in distributed settings. Moreover, random intersection graph models can be used to model social graphs, in which two entities are connected when they have a common feature. In the Random Intersection Graphs Model ${\cal G}_{n, m, p}$, we first study the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance $G_{n, m, p}$ of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for constructing Hamilton cycles in a wide range of the parameters $m, p$. Moreover, we show that almost every random instance of the ${\cal G}_{n, m, p}$ model is an expander, even for $p$ very close to the connectivity threshold. Finally, we give close to optimal bounds (that hold with probability that goes to 1 for a wide range of the parameters of the model) for important quantities (like the mixing time and the cover time) concerning random walks on random instances of ${\cal G}_{n, m, p}$. In the Uniform Random Intersection Graphs Model ${\cal G}_{n, m, \lambda}$ we study the existence of Hamilton cycles for a ce rtain range of the parameters $m, \lambda$. Finally, by using the probabilistic method we compute the independence number of ${\cal G}_{n, m, \lambda}$.