Τεχνικές συγκέντρωσης σε ασύρματα δίκτυα επικοινωνιών

Abstract

The present thesis deals with the design of distributed algorithms targeting at the lifetime prolongation of Wireless Sensor Networks (WSNs) using variations of classical game theory. Chapter 1 provides a quick overview of the principles of autonomous systems and distributed control, also introducing the reader to the basic characteristics of WSNs. In Chapter 2, a more thorough examination of the current state-of-the art concerning WSN specifications, applications and operational optimization protocols is given. Special attention is given to the existing literature related to node clustering and data aggregation.Chapter 3 provides an introduction to game theory and its variants of interest. First, coalitional and coalition formation game theory basics are overviewed, to support the theoretical analysis of Chapter 4; since these two variations of classical game theory are widely used to model the interactions of sets of cooperative players, they seem to perfectly fit the considered clustering optimization problem. Next, the players lack of information regarding the game states is discussed on the basis of bayesian games and the correlated equilibrium, covering the theory required for proper understanding of the analysis held on Chapter 5.In Chapter 4, a coalition formation game theoretic scheme is proposed that aims at maximizing wireless sensor networks lifetime under specified QoS. Employing a small number of nodes of increased computing power and lifetime called representatives, an adaptive clustering scheme is proposed where neighboring nodes form coalitions in order to increase energy efficiency at the cost of controllable data accuracy reduction. The coalition formation is globally optimized by the representatives. The spatial correlation of the sensed phenomenon measurements is exploited to formulate a cooperation scheme that reduces drastically the number of node transmissions. The specifications regarding the accuracy of the collected data determine the extent of coalition formation. The efficiency and stability of the proposed coalitional scheme are studied through simulations.The fifth chapter introduces a distributed correlated strategy based game theoretic framework to maximize the lifetime of multi-service WSNs at the same time assuring the global support of all the services over the WSN deployment. WSN lifetime maximization is dealt with as a multiple-player game among the multi-mode nodes. Since pure strategy approach is shown to lead to a stable but non optimal nodes allocation to the various WSN services, a correlated strategy approach is formed to lead a multi-service WSN close to its theoretical optimal state with respect to lifetime. The simulation results indicate that the proposed correlated strategy based framework leads the multi-service WSN operation close to its theoretical optimal at no significant overhead message exchange.

Αντικείμενο της διατριβής αποτελεί η σχεδίαση κατανεμημένων αλγορίθμων που αποσκοπούν στην επιμήκυνση της διάρκειας λειτουργίας ασυρμάτων δικτύων αισθητήρων (Wireless Sensor Networks, WSN) με χρήση παραλλαγών της κλασικής θεωρίας παιγνίων. Το Κεφάλαιο 1 παρέχει συνοπτική πληροφόρηση περί αυτόνομων συστημάτων και κατανεμημένου ελέγχου, εισάγοντας τον αναγνώστη στα βασικά χαρακτηριστικά των WSN. Στο Κεφάλαιο 2, γίνεται αναλυτική παρουσίαση των χαρακτηριστικών των WSN, των εφαρμογών τους καθώς και των βασικών τρόπων βελτίωσης της λειτουργίας τους. Παράλληλα, επιχειρείται επισκόπηση της σχετικής βιβλιογραφίας. Ιδιαίτερη έμφαση αποδίδεται στα σχήματα ομαδοποίησης κόμβων και συνάθροισης δεδομένων.Στο Κεφάλαιο 3 παρουσιάζεται η θεωρία παιγνίων και ορισμένες παραλλαγές αυτής. Αρχικά, παρουσιάζονται οι βασικές έννοιες των συνασπιστικών παιγνίων και των παιγνίων σχηματισμού συνασπισμών, έννοιες στις οποίες βασίζεται η ανάλυση που παρουσιάζεται στο Κεφάλαιο 4. Καθώς οι δύο αυτές παραλλαγές της κλασικής θεωρίας παιγνίων χρησιμοποιούνται ευρέως στη διεθνή βιβλιογραφία για τη μελέτη της διάδρασης μεταξύ συνόλων συνεργατικών παικτών, είναι ιδανικές για την υποστήριξη της θεωρητικής ανάλυσης του σχήματος ομαδοποίησης κόμβων που προτείνεται στο Κεφάλαιο 4. Στη συνέχεια, η έλλειψη πλήρους πληροφόρησης των παικτών ενός παιγνίου συζητείται στο πλαίσιο των παιγνίων Bayes και της συσχετισμένης ισορροπίας, καλύπτοντας τη θεωρία που απαιτείται για την κατανόηση του Κεφαλαίου 5.Στο Κεφάλαιο 4 προτείνεται μία μέθοδος σχηματισμού συνασπισμών που αποσκοπεί στη μεγιστοποίηση της διάρκειας λειτουργίας των WSN υπό συγκεκριμένες προδιαγραφές ακρίβειας/ποιότητας υπηρεσίας. Χρησιμοποιώντας μικρό πλήθος κόμβων --που καλούνται αντιπρόσωποι-- με αυξημένες υπολογιστικές και ενεργειακές δυνατότητες προτείνεται μία προσαρμοστική μέθοδος ομαδοποίησης κόμβων, σύμφωνα με την οποία γειτονικοί κόμβοι σχηματίζουν λειτουργικούς συνασπισμούς αποσκοπώντας στη μεγιστοποίηση της διάρκειας λειτουργίας τους, υπό αποδεκτή μείωση της ακρίβειας των μετρήσεών τους. Στη συνέχεια, οι αντιπρόσωποι βελτιστοποιούν τη δομή των ομαδοποιημένων κόμβων. Η προτεινόμενη μέθοδος αξιοποιεί τη χωρική συσχέτιση των υπό παρακολούθηση φυσικών φαινομένων για τη δημιουργία ενός συνεργατικού σχήματος που μειώνει σημαντικά το μέσο πλήθος μεταδόσεων των κόμβων. Οι προδιαγραφές ακρίβειας που χαρακτηρίζουν την αποδεκτή λειτουργία του WSN καθορίζουν την έκταση της ομαδοποίησης των κόμβων. Οι επιδόσεις και η σταθερότητα της προτεινόμενης μεθόδου επέκτασης της διάρκειας λειτουργίας WSN δικτύων εξετάζονται μέσω προσομοιώσεων.Το Κεφάλαιο 5 παρουσιάζει μια μέθοδο βασισμένη στην έννοια των συσχετισμένων στρατηγικών για τη μεγιστοποίηση της διάρκειας λειτουργίας WSN πολλαπλών υπηρεσιών, εξασφαλίζοντας την καθολική υποστήριξη των υπηρεσιών σε όλη τη γεωγραφική έκταση του WSN. Η μεγιστοποίηση της διάρκειας λειτουργίας ενός WSN πολλαπλών υπηρεσιών εξετάζεται ως παίγνιο πολλαπλών παικτών μεταξύ των κόμβων πολλαπλών λειτουργιών. Καθώς η εφαρμογή καθαρών στρατηγικών οδηγεί σε σταθερή αλλά όχι βέλτιστη κατανομή των κόμβων στις υποστηριζόμενες υπηρεσίες, διατυπώνεται μια προσέγγιση συσχετισμένων στρατηγικών για να οδηγήσει τη λειτουργία του WSN κοντά στη θεωρητικά βέλτιστη με κριτήριο τη διάρκεια λειτουργίας του. Τα αποτελέσματα των προσομοιώσεων καταδεικνύουν ότι η προτεινόμενη μέθοδος οδηγεί τη λειτουργία ενός WSN πολλαπλών υπηρεσιών κοντά στη θεωρητικά προβλεπόμενη βέλτιστη χωρίς να απαιτεί την ανταλλαγή σημαντικού πλήθους μηνυμάτων μεταξύ των κόμβων του WSN.