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

Abstract

Recent technological and scientific advances in the areas of solid state physics, integrated circuit design and telecommunications have led to enabling the functional design of innovative wireless networking models. These models comprise a large number of tiny sensor nodes working cooperatively towards building a wireless communication network. This doctoral dissertation focuses on the study/ proposal of energy-efficient algorithms for topology control and dissemination/ harvesting of information in large-scale Wireless Sensor Networks (WSNs). Chapter 1 of this dissertation is a detailed introduction in the subject of Wireless Sensor Networks. Specific details of recent technological advances towards making it technically feasible to produce large numbers of tiny sensor motes are explained. A large ensemble of sensor motes, which are embedded in the physical space, can produce a “smart environment”. The technical characteristics of “smart environments” are listed and the major models for Wireless Sensor Networks operation (as they have been proposed in literature) are explained. In Chapter 2, a novel technique is proposed for distributed clustering of sensor nodes in a large scale Wireless Sensor Network. The proposed Directed Budget Based (DBB) and Directed Budget Based with Random Delays (DBB-RD) algorithms have their basis on two previously published algorithms for distributed clustering of nodes in wireless networks, called Rapid and Persistent. The algorithms begin the distributed clustering process by distributing a set of coupons/ tokens offered to the initiator node evenly among the neighbors of that node; the process is then repeated in consecutive cycles of operation until the tokens are completely distributed or no more growth is possible in the network. The directed budget-based clustering algorithms called DBB and DBB-RD are proved through simulations to be energy-beneficial for the wireless sensor network due to both the reduced total number of exchanged messages in the network and the final cluster sizes achieved (close to the desired offered budget). ? Chapter 3 describes an innovative technique for information diffusion in a large scale WSN. The described technique is based on random walks for information propagation inside the sensor network, which is modeled as a random geometric graph. The classic, well known, random walk involves the proliferation of the agent in the network by choosing uniformly at random among all next hop neighbors of the currently visited node. In contrast to this, the in-chapter-3-described technique involves the design of a “freezing” mechanism for the direction of movement of the random walk agent, such that the agent is allowed to be forwarded towards a specific direction in the network. The particular forwarding direction is retained by the random walk-with-jumps agent for as long as the agent will stay in the “freezing state”. It is shown through both simulations and analysis that the incorporation of such a freezing mechanism into the otherwise pure random walk movement of the random walk agent will be beneficial for the overall covering process of the sensor network.

Οι πρόσφατες επιστημονικές εξελίξεις στους χώρους της μικροηλεκτρονικής, των ολοκληρωμένων κυκλωμάτων και των τηλεπικοινωνιών επιτρέπουν το σχεδιασμό και τη λειτουργία καινοτόμων μοντέλων ασύρματων δικτύων επικοινωνιών που βασίζονται στη συνεργατική λειτουργία μεγάλου πλήθους μικροσκοπικών κόμβων αισθητήρων. Η παρούσα διδακτορική διατριβή επικεντρώνεται στην μελέτη/ πρόταση ενεργειακά αποδοτικών αλγορίθμων που εφαρμόζονται σε Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) μεγάλου πλήθους κόμβων με στόχο τον έλεγχο της τοπολογίας και τη διάχυση/ συλλογή πληροφορίας στο δίκτυο. Η διατριβή περιλαμβάνει πέντε κεφάλαια, όπως περιγράφονται συνοπτικά στη συνέχεια. Το Κεφάλαιο 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 αναπτύσσεται μια καινούρια τεχνική για τη διάχυση πληροφοριών σε Ασύρματο Δίκτυο Αισθητήρων μεγάλου πλήθους κόμβων. Η τεχνική που περιγράφεται βασίζεται στη χρήση τυχαίων περιπάτων για τη μεταφορά πληροφοριών στο δίκτυο αισθητήρων, το οποίο μοντελοποιείται ως τυχαίος γεωμετρικός γράφος, και αποτελεί ουσιαστικά την επιτάχυνση της διαδικασίας κάλυψης δικτύου από έναν τυχαίο περίπατο. Ο κλασσικός, ευρέως διαδεδομένος τυχαίος περίπατος περιλαμβάνει την μετακίνηση του πράκτορα στο δίκτυο κάνοντας τυχαία επιλογή μεταξύ όλων των πρώτων γειτόνων του επισκεπτόμενου κόμβου...