Master of Science / Department of Computing and Information Sciences / Gurdip Singh / Severe energy constraints and limited computing abilities of the nodes in a network present a major challenge in the design and deployment of a wireless sensor network. This thesis aims to present energy efficient algorithms for data fusion and information aggregation in a sensor network. The various methodologies of data fusion presented in this thesis intend to reduce the data traffic within a network by mapping the sensor network application task graph onto a sensor network topology. Partitioning of an application into sub-tasks that can be mapped onto the nodes of a sensor network offers opportunities to reduce the overall energy consumption of a sensor network. The first approach proposes a grid based coordinated incremental data fusion and routing with heterogeneous nodes of varied computational abilities. In this approach high performance nodes arranged in a mesh like structure spanning the network topology, are present amongst the resource constrained nodes. The sensor network protocol performance, measured in terms of hop-count is analysed for various grid sizes of the high performance nodes. To reduce network traffic and increase the energy efficiency in a randomly deployed sensor network, distributed clustering strategies which consider network density and structure similarity are applied on the network topology. The clustering methods aim to improve the energy efficiency of the sensor network by dividing the network into logical clusters and mapping the fusion points onto the clusters. Routing of network information is performed by inter-cluster and intra-cluster routing.

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

[pt] As redes de sensores sem fio se constituem numa área que outorga grandes oportunidades para a oferta de uma série de aplicações inovadoras e com baixo custo. Os dispositivos destas redes são bastantes pequenos e sua fonte de alimentação são baterias. O tempo de vida destas é limitado, limitando assim o tempo da vida dos sensores e da rede como um todo. Por esta razão nos últimos anos o tema de eficiência energética tem atraído grande interesse de pesquisadores. O aumento do custo da energia e do consumo global da energia pelo setor de ICT (Information and Communications Technologies) têm crescido vertiginosamente devido ao aumento continuo do número de clientes e da demanda por aplicações de maior complexidade. Por tudo isso têm sido desenvolvidos distintos métodos e técnicas para economizar energia nas RSSF. Neste trabalho se implementam dois algoritmos que levam em conta critérios para economizar os custos de energia da rede e através de experimentos de simulação se avalia os mesmos. Nos resultados pode se observar as vantagens de trabalhar com sistemas que visam a eficiência energética. / [en] The WSNs (Wireless Sensor Networks) belong to an area that gives rise to great opportunities to spread innovative and low cost applications. These kinds of networks are composed of tiny devices with limited energy. The main source of power supply for WSNs are batteries, which are limited in cycle life, thus limiting the sensors lifetime and the network as a whole. Due to that fact, the energy efficiency network is becoming the main concern to be addressed by researchers. Rising energy prices and global energy consumption by the ICT (Information and Communications Technologies) sector have grown dramatically due to the continuous increase in customer number and the demand for more complex applications. For the reasons outlined above, different energy-saving techniques for WSNs have been developed. Two energy-saving algorithms for WSNs were implemented in this thesis, and they were tested by experimental evaluation using simulation. The results obtained from the simulations showed the advantages of working with systems aiming at energy efficiency.