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

Abstract

Wireless sensor networks are comprised of a vast number of devices situated in an area of interest that self organize in a structureless network in order to monitor/record/measure an environmental variable or phenomenon and subsequently to disseminate the data to the control center. Here we present research focused on the development simulation and evaluation of energy efficient algorithms, our basic goal is to minimize the energy consumption. Despite technology advances the problem of energy use optimization remains valid since current and emerging hardware solutions fail to solve it. We aim to reduce communication cost by introducing novel techniques that facilitate the development of new algorithms. We investigated techniques of distributed adaptation of the operations of a protocol by using information available locally on every node, thus through local choices we improve overall performance. We propose techniques for collecting and exploiting limited local knowledge of the network conditions. In an energy efficient manner we collect additional information which is used to achieve improvements such as forming energy efficient, low latency and fault tolerant paths to route data. We investigate techniques for managing mobility in networks where movement is a characteristic of the control center as well as the sensors. We examine methods for traversing and covering the network field based on probabilistic movement that uses local criteria to favor certain areas. The algorithms we develop based on these techniques operate: a) at low level managing devices, b) on the routing layer and c) network wide achieving macroscopic behavior through local interactions. The algorithms are applied in network cases that differ in density node distribution available energy and also in fundamentally different models such as under faults with incremental node deployment and mobile nodes. In all these settings our techniques achieve significant gains, thus distinguishing their value as tools of algorithmic design.

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