Μελέτη αποδοτικών αλγορίθμων για τον έλεγχο τοπολογίας και τη διάχυση / συλλογή πληροφοριών σε μεγάλου εύρους ασύρματα δίκτυα αισθητήρων
Authors: Τζεβελέκας Λεωνίδας 
Published: January 2014

Οι πρόσφατες επιστημονικές εξελίξεις στους χώρους της μικροηλεκτρονικής, των ολοκληρωμένων κυκλωμάτων και των τηλεπικοινωνιών επιτρέπουν το σχεδιασμό και τη λειτουργία καινοτόμων μοντέλων ασύρματων δικτύων επικοινωνιών που βασίζονται στη συνεργατική λειτουργία μεγάλου πλήθους μικροσκοπικών κόμβων αισθητήρων. Η παρούσα διδακτορική διατριβή επικεντρώνεται στην μελέτη/ πρόταση ενεργειακά αποδοτικών αλγορίθμων που εφαρμόζονται σε Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) μεγάλου πλήθους κόμβων με στόχο τον έλεγχο της τοπολογίας και τη διάχυση/ συλλογή πληροφορίας στο δίκτυο. Η διατριβή περιλαμβάνει πέντε κεφάλαια, όπως περιγράφονται συνοπτικά στη συνέχεια. Το Κεφάλαιο 1 αποτελεί μια εκτενή εισαγωγή στα Ασύρματα Δίκτυα Αισθητήρων. Αρχικά αναφέρεται η επιμέρους τεχνολογική πρόοδος που έχει λάβει χώρα, προκειμένου να είναι τεχνικά δυνατό να κατασκευαστούν οι κόμβοι αισθητήρες σε μεγάλες κλίμακες. Μια μεγάλη συλλογή από κόμβους αισθητήρες, ενταγμένοι στο φυσικό χώρο, αποτελούν ένα «έξυπνο περιβάλλον». Τα τεχνικά χαρακτηριστικά του «έξυπνου περιβάλλοντος» αναλύονται και τα μοντέλα λειτουργίας των Ασύρματων Δικτύων Αισθητήρων που έχουν προταθεί στη βιβλιογραφία εξηγούνται. Τέλος, γίνεται εκτεταμένη αναφορά στις τεχνικές προκλήσεις που καλούνται τα πρωτοκόλλα λειτουργίας των Ασύρματων Δικτύων Αισθητήρων να καλύψουν και τα πιο ευρέως διαδεδομένα, προτεινόμενα πρωτόκολλα αναπτύσσονται διεξοδικά (SPIN prοtocol, LEACH protocol, Directed Diffusion protocol, Publish/ Subscribe protocol). Στο Κεφάλαιο 2 παραθέτουμε μια καινούρια τεχνική για την κατανεμημένη ομαδοποίηση των κόμβων αισθητήρων εντός ενός δικτύου αισθητήρων μεγάλου πλήθους κόμβων. Οι προτεινόμενοι αλγόριθμοι Directed Budget Based (DBB) και Directed Budget Based with Random Delays (DBB-RD) είναι βασισμένοι σε δυο παλαιότερα δημοσιευμένους αλγόριθμους κατανεμημένης ομαδοποίησης κόμβων με ονόματα Rapid και Persistent. Οι αλγόριθμοι ξεκινούν την ομαδοποίηση από ένα αρχικό πλήθος κουπονιών που δίνονται στον κόμβο αρχηγό, τα οποία στη συνέχεια διαμοιράζονται τμηματικά προς τους πρώτους γείτονες. Η διαδικασία επαναλαμβάνεται σε κύκλους λειτουργίας έως ότου τα κουπόνια διαμοιρασμού καταναλωθούν πλήρως ή δεν υπάρχει επιπλέον χώρος για ανάπτυξη των ομάδων. Η κατευθυνόμενη ομαδοποίηση σύμφωνα με τους DBB και DBB-RD αλγορίθμους αποδεικνύεται ότι είναι επωφελής για το δίκτυο αισθητήρων τόσο λόγω του μειωμένου πλήθους ανταλλασσόμενων μηνυμάτων για την ολοκλήρωση της διαδικασίας ομαδοποίησης όσο και λόγω των αποτελεσμάτων της διαδικασίας που καταλήγει σε ομάδες εντός του δικτύου που είναι πολύ κοντά στο επιθυμητό αρχικό πλήθος κόμβων. Στο Κεφάλαιο 3 αναπτύσσεται μια καινούρια τεχνική για τη διάχυση πληροφοριών σε Ασύρματο Δίκτυο Αισθητήρων μεγάλου πλήθους κόμβων. Η τεχνική που περιγράφεται βασίζεται στη χρήση τυχαίων περιπάτων για τη μεταφορά πληροφοριών στο δίκτυο αισθητήρων, το οποίο μοντελοποιείται ως τυχαίος γεωμετρικός γράφος, και αποτελεί ουσιαστικά την επιτάχυνση της διαδικασίας κάλυψης δικτύου από έναν τυχαίο περίπατο. Ο κλασσικός, ευρέως διαδεδομένος τυχαίος περίπατος περιλαμβάνει την μετακίνηση του πράκτορα στο δίκτυο κάνοντας τυχαία επιλογή μεταξύ όλων των πρώτων γειτόνων του επισκεπτόμενου κόμβου...