Συντάχθηκε 12-12-2013 14:16
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΜΑΡΙΝΑ ΜΑΥΡΙΚΟΥ
με θέμα
Σχεδίαση και Υλοποίηση Αλγορίθμων για αποτίμηση Συναθροιστικών Επερωτήσεων υπό την παρουσία Διπλότυπων Μετρήσεων
Design and Implementation of Algorithms for Aggregate Queries in the Presence of Duplicates
Δευτέρα 16 Δεκεμβρίου 2013, 11.30 πμ
Αίθουσα 2041, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επίκουρος Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Επίκουρος Καθηγητής Άγγελος Μπλέτσας
Καθηγητής Μίνως Γαροφαλάκης
Περίληψη
Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) χρησιμοποιούνται ευρέως στη σημερινή εποχή και είναι μια περιοχή συνεχώς αναπτυσσόμενη. Υπάρχει μεγάλος αριθμός από περιβαλλοντικές, οικονομικές, ιατρικές, ακόμη και στρατιωτικές εφαρμογές, οι οποίες χρησιμοποιούν αισθητήρες για τον έλεγχο και την παρακολούθηση δεδομένων και μετρήσεων. Επειδή αντιμετωπίζουν θέματα χαμηλής κατανάλωσης ενέργειας και ασύρματης δικτύωσης μεταξύ τους είναι σημαντική η εύρυθμη λειτουργία τους και η εγκυρότητα των αποτελεσμάτων τους.
Στόχος της διπλωματικής αυτής εργασίας είναι η ανίχνευση διπλότυπων τιμών μέσα στο δίκτυο. Διπλότυπα μπορούν να θεωρηθούν τα ids, τα οποία ανιχνεύονται πάνω από μία φορά μέσα στο δίκτυο. Η αναγνώριση διπλοτύπων σε ένα ΑΔΑ είναι σημαντική, ώστε να έχουμε αξιόπιστα τελικά αποτελέσματα, διατηρώντας, ταυτόχρονα, χαμηλή κατανάλωση ενέργειας και σωστή λειτουργία του δικτύου. Για τα συναθροιστικά επερωτήματα ΜΙΝ και ΜΑΧ, τα οποία είναι μονοτονικά και ενδεικτικά, η ύπαρξη διπλοτύπων σε αυτά είναι ανεκτική σε σφάλματα. Αλλά για συναθροιστικά επερωτήματα, τα οποία ειναι ευαίσθητα σε διπλότυπα, όπως τα COUNT, AVG και SUM, τα τελικά αποτελέσματα είναι εσφαλμένα.
Εκμεταλεύοντας την ιεραρχική τοπολογία, που δημιουργείται κατά την μετάδοση του επερωτήματος, οι κόμβοι μπορούν να ανιχνεύσουν αν έχουν κάποιο διπλότυπο στο υποδέντρο τους. Αν ένας κόμβος ανιχνεύσει ένα διπλότυπο και βρίσκεται στην πιο ψηλή ιεραρχία του δέντρου για το συγκεκριμένο διπλότυπο, τότε παρακολουθεί το διπλότυπο αυτό και συγχωνεύει τις μετρήσεις του διπλοτύπου αυτού.
Για να διατηρήσουμε την κατανάλωση ενέργειας χαμηλή, προσεγγίσαμε τον αλγόριθμό μας με τρείς διαφορετικές μεθόδους και τους συνδυασμούς τους. Οι μέθοδοι αυτοί είναι οι Full Data, Delta και Bloom Filter μέθοδοι. Μέσω των πειραμάτων που πραγματοποιήθηκαν, παρουσιάζουμε τα οφέλη για την κάθε μία μέθοδο. Οι ποσότητες σύγκρισης είναι η αξιοπιστία και η κατανάλωση ενέργειας. Οι αλγόριθμοι δοκιμάστηκαν και εφαρμόστηκαν στο ΑΔΑ του εργαστηρίου SoftNet.
Abstract
Wireless Sensor Networks (WSNs) are nowadays widely used and form a rapidly growing area of research. There is a great number of environmental, economical, medical and even military applications that uses sensors for controlling and monitoring data and measurements. Faced with issues of low power consumption and wireless networking, proper operations and reliability of sensor results are very significant.
The goal of this thesis is to detect duplicate values inside a network. Duplicate values can be considered to be ids that are detected more than one time in the network. The identification of duplicates in a WSN is important in order to have accurate final results, while maintaining low power consumption and proper operation of the network. For aggregate queries such as MIN and MAX, which are monotonic and exemplary, the existence of duplicates is fault- tolerant. But for duplicate-sensitive aggregates such as COUNT, AVG or SUM, it gives incorrect final results.
By taking advantage of the hierarchical topology, which is created, during the dissemination of the query, nodes can detect if they have duplicate values at their sub-trees. If a node detects a duplicate value and is the highest in the hierarchy of the tree for this duplicate value, then it keeps track of this value and merges measurements of this duplicate value.
In order to keep energy consumption low, we approached our algorithm with three different methods and their combinations. These methods are Full Data, Delta and Bloom Filter methods. Through the experiments that we did, we present the gain for each one of these methods. Reliability and energy consumption are our quantities of comparison. Algorithms were tested and executed at the WSN of lab SoftNet.
