Διάχυση πληροφορίας και κυρίαρχα σύνολα σε ασύρματα δίκτυα αισθητήρων

Abstract

Στη διάρκεια των τελευταίων δεκαετιών έχει αναπτυχθεί μεγάλος αριθμός Ασύρματων Δικτύων Αισθητήρων για την αποτύπωση των συνθηκών που επικρατούν στους χώρους όπου είναι εγκατεστημένα. Νέα δίκτυα αυτής της μορφής εγκαθίστανται διαρκώς, τα οποία λόγω των λειτουργικών απαιτήσεων και της τεχνολογικής προόδου έχουν αυξημένο αριθμό κόμβων. Ο όγκος των παραγόμενων δεδομένων είναι ιδιαίτερα μεγάλος και η συλλογή και η μεταφορά τους κεντρικά απαιτεί τη χρήση καινοτόμων μεθόδων. Στην παρούσα διατριβή προτείνονται δύο μέθοδοι αντιμετώπισης του προβλήματος της Διάχυσης της Πληροφορίας σε Ασύρματα Δίκτυα Αισθητήρων, δηλαδή της μεταφοράς των δεδομένων από και προς τους κόμβους αυτών των δικτύων. Η πρώτη μέθοδος που προτείνεται βασίζεται στη χρήση Τυχαίων Περιπατητών. Αρχικά παρουσιάζεται μια εις βάθος πρωτότυπη ανάλυση της απόδοσης της χρήσης ενός Τυχαίου Περιπατητή για την κάλυψη ενός Ασύρματου Δικτύου Αισθητήρων. Το αποτέλεσμα αυτής της ανάλυσης είναι μια αναλυτική σχέση για την κάλυψη του δικτύου ως συνάρτηση του απαιτούμενου χρόνου, που εκφράζεται ως ο αριθμός των απαιτούμενων αλμάτων του Τυχαίου Περιπατητή. Η ανάλυση αυτή υποστηρίζεται από εκτεταμένες προσομοιώσεις σε διάφορα μοντέλα δικτύων καθώς και από την εφαρμογή της σε πειραματικό ασύρματο δίκτυο που είναι εγκατεστημένο σε κτήρια του Ιονίου Πανεπιστημίου. Το συμπέρασμα αυτής της ανάλυσης είναι ότι η χρήση ενός Τυχαίου Περιπατητή για τη Διάχυση της Πληροφορίας σε Ασύρματα Δίκτυα Αισθητήρων επιτυγχάνει το στόχο της με χαμηλή επιβάρυνση των ενεργειακών πόρων των δικτύων, που είναι κρίσιμος παράγοντας για τη λειτουργία τους. Το μειονέκτημα αυτής της μεθόδου είναι ο σχετικά μεγάλος χρόνος που απαιτείται για την ολοκλήρωση της διαδικασίας. Στη συνέχεια εξετάζεται η χρήση Πολλαπλών Τυχαίων Περιπατητών που δρουν ταυτόχρονα, με στόχο τη μείωση του απαιτούμενου χρόνου σε σχέση με τη χρήση ενός Τυχαίου Περιπατητή. Για τη χρήση Πολλαπλών Τυχαίων Περιπατητών παρουσιάζεται η ανάλυση της απόδοσής τους, η οποία βασίζεται στα αποτελέσματα της ανάλυσης για τη χρήση ενός Τυχαίου Περιπατητή. Εξετάζεται, αρχικά, η κάλυψη του δικτύου, η οποία καταλήγει σε μια αναλυτική σχέση ως συνάρτηση του απαιτούμενου χρόνου για συγκεκριμένο αριθμό Τυχαίων Περιπατητών που δρουν ταυτόχρονα στο δίκτυο. Η σχέση αυτή αποδείχθηκε σύμφωνη με ανεξάρτητη εργασία της βιβλιογραφίας, η οποία εξετάζει το ίδιο ζήτημα για πλήρη δίκτυα. Στη συνέχεια παρουσιάζεται η ανάλυση της απόδοσης της χρήσης Πολλαπλών Τυχαίων Περιπατητών εφοδιασμένων με Μηχανισμό Αντιγραφής. Τέλος, αναλύεται η δυνατότητα κάλυψης των δικτύων με περιορισμούς χρόνου και ποσοστού κάλυψης, η οποία καταλήγει σε μια σχέση οποία επιτρέπει τον υπολογισμό του αριθμού των Τυχαίων Περιπατητών που απαιτούνται για την κάλυψη ενός ποσοστού των κόμβων των δικτύων σε συγκεκριμένο χρονικό διάστημα. ́Ολα τα αναλυτικά αποτελέσματα υποστηρίζονται από μεγάλο αριθμό προσομοιώσεων σε διάφορα μοντέλα δικτύων καθώς και από την πειραματική εφαρμογή τους στο πειραματικό ασύρματο δίκτυο του Ιονίου Πανεπιστημίου. Η δεύτερη μέθοδος που προτείνεται βασίζεται στη χρήση Συνδεδεμένων Κυρίαρχων Συνόλων. Τα Συνδεδεμένα Κυρίαρχα Σύνολα μπορούν να εξασφαλίσουν ότι όλοι οι κόμβοι ενός δικτύου είτε θα ανήκουν σε αυτά, είτε θα απέχουν το πολύ ένα συγκεκριμένο αριθμό αλμάτων από τουλάχιστον ένα κόμβο τους. Με αυτόν τον τρόπο, δημιουργείται ένα υποδίκτυο υποδομής, ή backbone, που διευκολύνει τη Διάχυση της Πληροφορίας από και προς τους κόμβους του δικτύου στο οποίο ανήκουν. Αρχικά προτείνεται ένας κατανεμημένος αλγόριθμος δύο φάσεων, που έχει ως αποτέλεσμα τη δημιουργία Συνδεδεμένου Κυρίαρχου Συνόλου d αλμάτων. Κατά την πρώτη φάση οι κόμβοι του δικτύου συλλέγουν τις απαιτούμενες πληροφορίες για την τοπολογία του δικτύου και κατά τη δεύτερη εκκινώντας από έναν κόμβο του δικτύου δημιουργείται το Συνδεδεμένο Κυρίαρχο Σύνολο d αλμάτων. Ο προτεινόμενος αλγόριθμος εξετάζεται αναλυτικά ως προς την ορθότητά του, τον αριθμό των απαιτούμενων μηνυμάτωνγια την εκτέλεσή του καθώς και για τον απαιτούμενο χρόνο επεξεργασίας και τερματισμού του. Η απόδοση του αλγόριθμου συγκρίνεται μέσω προσομοιώσεων, με την απόδοση ενός κεντρικοποιημένου αλγόριθμου καθώς και με αυτήν ενός σχετικά πρόσφατα προταθέντος κατανεμημένου. Το αποτέλεσμα της σύγκρισης είναι ότι η απόδοση του προτεινόμενου αλγόριθμου είναι παραπλήσια με αυτήν του κεντρικοποιημένου όσον αφορά το μέγεθος του παραγόμενου συνόλου και υπερτερεί σημαντικά του κατανεμημένου, όσον αφορά τόσο το μέγεθος του παραγόμενου συνόλου όσο και τον αριθμό των απαιτούμενων μηνυμάτων. Ο αριθμός των απαιτούμενων μηνυμάτων είναι κρίσιμο μέγεθος για αλγόριθμους που εκτελούνται σε Ασύρματα Δίκτυα Αισθητήρων γιατί καταναλώνουν ενεργειακούς πόρους των δικτύων. Τέλος παρουσιάζεται μια παραλλαγή του προτεινόμενου αλγόριθμου που δημιουργεί Προϋπολογισμένα Συνδεδεμένα Κυρίαρχα Σύνολα. Αυτά είναι τα Συνδεδεμένα Κυρίαρχα Σύνολα με άνω φράγμα ως προς το μέγεθός τους, τα οποία έχουν μεγάλη πρακτική χρησιμότητα. Αυτός ο αλγόριθμος υποστηρίζεται από προσομοιώσεις στις οποίες συγκρίνεται η απόδοση του με αυτήν του κύριου αλγόριθμου αυτής της διατριβής. Επιπρόσθετα οι δύο αλγόριθμοι εφαρμόζονται σε προσομοιώσεις που στηρίζονται σε δεδομένα που αντλήθηκαν από ανοικτή βάση δεδομένων και αφορούν την κίνηση των ταξί της πόλης της Νέας Υόρκης. Το συμπέρασμα είναι ότι η παραγωγή Προϋπολογισμένων Συνδεδεμένων Κυρίαρχων Συνόλων με κατάλληλη παραμετροποίηση επιτυγχάνει παραπλήσια αποτελέσματα με αυτά του κύριου αλγόριθμου, επιτυγχάνοντας όμως μεγάλη εξοικονόμηση υπολογιστικών πόρων.