Σχεδιασμός, υλοποίηση και πειραματική αξιολόγηση αποδοτικών αλγορίθμων για κινητά δίκτυα αισθητήρων

• Κύριος συγγραφέας: Πατρούμπα, Δήμητρα
• Άλλοι συγγραφείς: Νικολετσέας, Σωτήρης
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2013
• Θέματα: Ασύρματα δίκτυα αισθητήρων; Πρωτόκολλα δρομολόγησης δεδομένων; Εξοικονόμηση ενέργειας; Πειραματική αξιολόγηση; Συστημικές εφαρμογές; Τυχαίοι περίπατοι; Επίγνωση ηλεκτρομαγνητικής ακτινοβολίας; Wireless sensor networks; Data routing protocols; Energy saving; Experimental evaluation; Applications; Random walks; Radiation awareness; 004.62

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