Συντάχθηκε 01-12-2011 10:59
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΜΠΟΥΡΔΑΚΗΣ ΣΑΒΒΑΣ
με θέμα
“ Σύγκριση αλγορίθμων για ανίχνευση εξέχουσων τιμών σε δίκτυα αισθητήρων”
“Comparison of algorithms for Outliers detection in Sensor Networks”
Παρασκευή 2 Δεκεμβρίου 2011, 17μμ
Αίθουσα 145Π58, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επ.Καθ. Αντώνιος Δεληγιαννάκης (επιβλέπων)
Επ.Καθ. Μιχαήλ Γ. Λαγουδάκης
Καθ. Μίνως Γαροφαλάκης
Περίληψη
Σημαντικός αριθμός ερευνητικών εργασιών έχουν εστιάσει τα τελευταία χρόνια στην ανίχνευση εξέχουσων τιμών (outliers) σε δίκτυα αισθητήρων. Υπάρχουν πολλοί τρόποι να οριστεί κάποια τιμή/κόμβος ως outlier, αλλά γενικά outlier μπορεί να θεωρηθεί ένας αισθητήρας του οποίου οι μετρήσεις αποκλίνουν σημαντικά από τις μετρήσεις άλλων, γειτονικών, κόμβων. Η ανίχνευση μη φυσιολογικών μετρήσεων ενός κόμβου είναι ενδιαφέρουσα, επειδή αυτό το γεγονός μπορεί να βοηθήσει είτε στον εντοπισμό δυσλειτουργίας κάποιου κόμβου είτε για να ανιχνεύσει έναν κόμβο που παρατηρεί ένα τοπικά ενδιαφέρον φαινόμενο (π.χ. μια πυρκαγιά). Στην εργασία αυτή παρουσιάζουμε νέους αλγόριθμους για την ανίχνευση outlier στα δίκτυα αισθητήρων, βασισμένους στη γεωμετρική προσέγγιση. Σε αντίθεση με προηγούμενες εργασίες οι αλγόριθμοι μας εκτελούν έναν κατανεμημένο έλεγχο παρακολούθησης outlier κόμβων, παρουσιάζουν 100% ακρίβεια στον έλεγχο (υποθέτοντας ότι δεν υπάρχουν απώλειες μηνυμάτων) και η μετάδοση των μηνυμάτων μπορεί να περιοριστεί μόνο σε ένα μέρος των εποχών, επιτρέποντας έτσι στους κόμβους με ασφάλεια να απέχουν στη μετάδοση μηνυμάτων για αρκετές εποχές, περιορίζοντας έτσι την κατανάλωση ενέργειας. Η προσέγγισή μας στηρίζεται στη μετατροπή κοινών μετρικών ομοιότητας με τέτοιο τρόπο, ώστε να επιτρέπει την εφαρμογή της πρόσφατα προτεινόμενης γεωμετρικής προσέγγισης η οποία μας επιτρέπει να ελέγχουμε με ακρίβεια, κατά πόσον μια σύνθετη, ενδεχομένως μη γραμμική συνάρτηση είναι πάνω ή κάτω από ένα συγκεκριμένο όριο. Στη συνέχεια προτείνουμε ένα γενικό πλαίσιο ενώ παρουσιάζουμε πολλαπλούς τρόπους λειτουργίας, οι οποίοι επιτρέπουν σε κάθε κόμβο αισθητήρα να παρακολουθεί με ακρίβεια την ομοιότητά του με άλλους κόμβους. Τα πειράματα μας αποδεικνύουν ότι οι αλγόριθμοι μας μπορούν να ανιχνεύσουν με ακρίβεια outlier, σε ένα κλάσμα του κόστους επικοινωνίας που θα απαιτούσε μια συγκεντρωτική προσέγγιση (ακόμα και στην συγκεντρωτική περίπτωση όπου ο κεντρικός κόμβος βρίσκεται σε ακτίνα επικοινωνίας με όλους τους κόμβους αισθητήρων). Επιπλέον, δείχνουμε ότι αυτή η εξοικονόμηση εύρους ζώνης γίνεται ακόμα μεγαλύτερη, δεδομένου ότι ενσωματώνουμε περαιτέρω βελτιστοποιήσεις στον αλγόριθμό μας.
Abstract
The topic of outlier detection in sensor networks has received significant attention in recent years. Detecting when the measurements of a node become “abnormal” is interesting, because this event may help detect either a malfunctioning node, or a node that starts observing a local interesting phenomenon (i.e., a fire). In this thesis we present new algorithms for detecting outliers in sensor networks, based on the geometric approach. Unlike prior work. our algorithms perform a distributed monitoring of outlier readings, exhibit 100% accuracy in their monitoring (assuming no message losses), and require the transmission of messages only at a fraction of the epochs, thus allowing nodes to safely refrain from transmitting in many epochs. Our approach is based on transforming common similarity metrics in a way that admits the application of the recently proposed geometric approach. We then propose a general framework and suggest multiple modes of operation, which allow each sensor node to accurately monitor its similarity to other nodes. Our experiments demonstrate that our algorithms can accurately detect outliers at a fraction of the communication cost that a centralized approach would require (even in the case where the central node lies just one hop away from all sensor nodes). Moreover, we demonstrate that these bandwidth savings become even larger as we incorporate further optimizations in our proposed modes of operation.
