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

Abstract

Over the last decades, a large number of Wireless Sensor Networks have been developed to monitor the conditions in the places where they are installed. Networks of this kind are constantly being installed, which due to functional requirements and technological advancements have an increased number of nodes. The amount of the produced data is enormous, and the collection and transmission of them centrally requires the use of innovative methods. In this thesis, two methods are proposed to address the problem of information dissemination in WSNs, that is, the transmission of data to and from the nodes of these networks. The first proposed method is based on the use of random walkers. Initially an in-depth original analysis of the performance of using one random walker to cover a WSN is presented. The result of this analysis is an analytic relation of the network coverage as a function of the time required, expressed as the number of random walker’s hops. This analysis is supported by extensive simulations on various network models as well as its application to an experimental wireless network installed in Ionian University’s buildings. The conclusion of this analysis is that the use of one random walker for the dissemination of information in WSNs achieves its goal with a low burden on the network’s energy resources, which is a critical factor for their peration. The disadvantage of this method is the relatively long time for the completion of the process. Next, the use of multiple random walkers acting simultaneously is considered, in order to reduce the time required for the network coverage compared to the use of one random walker. The performance analysis of the use of multiple random walkers presented, is based on the results of the aforementioned analysis of the use of one random walker. The network coverage is initially examined, resulting a function of the time required for a given number of random walkers operating simultaneously on the network, in a detailed analytical form. This analytical form proved to be consistent with a previously published work, which addresses the same issue for complete graphs. Then an analysis of the performance of multiple random walkerswith Replication Mechanism is presented. Finally, an analytical form is derived, that enables the calculation of the number of random walkers needed for the coverage of a percentage of the network’s nodes in a given time interval. All the analytical results are supported by extensive simulations on various network models as well as by their experimental application to the Ionian University Experimental Wireless Network. The second proposed method is based on the use of connected dominating sets. Connected Dominating Sets can ensure that all nodes in a network will either belong to them or they are at least a certain number of hops away from at least one node of them. This creates a backbone that facilitates the Dissemination of Information to and from the nodes of the network to which they belong. Initially, a distributed two-phase algorithm is proposed, which creates a d-hop connected dominating set. During the first phase, the network nodes collect the required topology information and during the second phase, starting from a network node, a d-hop Connected Dominating Set is created. The proposed algorithm is examined analytically for itscorrectness, the number of messages needed for the execution, and the processing and termination time. The algorithm’s performance is compared through simulations with the performance of a centralized algorithm and with that of a relatively recently proposed distributed one. The result of the comparison is that the performance of the proposed algorithm is similar to that of the centralized one, in terms of the size of the produced set, and it significantly outperforms the distributed one in terms of both the size of the produced set and of the number of required messages. The number of required messages is a critical parameter for algorithms that run on WSNs because they consume the network’s energy resources.Finally, a variation of the proposed algorithm that generates budget limited Connected Dominating Sets is presented. These are Connected Dominating Sets with an upper bound as to their size and are of great practical utility. This algorithm is supported by simulations that compare its performance with that of the main algorithm of this thesis. Both algorithms are also applied to simulations based on data drawn from an open database for New York City taxis traffic. The conclusion is that the production of budget limited Connected Dominating Sets, achieves results similar to those of the main algorithm, consuming lower computational resources.

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