Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/6529
Title: Σχεδιασμός, υλοποίηση και πειραματική αξιολόγηση αποδοτικών αλγορίθμων για κινητά δίκτυα αισθητήρων
Authors: Πατρούμπα, Δήμητρα
Issue Date: 2013-12-09
Keywords: Ασύρματα δίκτυα αισθητήρων
Πρωτόκολλα δρομολόγησης δεδομένων
Εξοικονόμηση ενέργειας
Πειραματική αξιολόγηση
Συστημικές εφαρμογές
Τυχαίοι περίπατοι
Επίγνωση ηλεκτρομαγνητικής ακτινοβολίας
Keywords (translated): Wireless sensor networks
Data routing protocols
Energy saving
Experimental evaluation
Applications
Random walks
Radiation awareness
Abstract: Τα Δίκτυα Αισθητήρων αποτελούνται από ένα μεγάλο αριθμό μικρών αυτόνομων συσκευών, που αλληλεπιδρούν με το άμεσο περιβάλλον τους μέσω αισθητήρων, συλλέγουν δεδομένα και τα προωθούν προς ένας σταθερό, συνήθως, κέντρο ελέγχου, με αναμεταδόσεις στους ενδιάμεσους κόμβους. Η διαδικασία αυτή έχει ως αποτέλεσμα τη μεγάλη κατανάλωση ενέργειας στις συσκευές, ιδιαίτερα σε αυτές που βρίσκονται κοντά στο κέντρο ελέγχου, αφού πρέπει να αναμεταδίδουν και τα δεδομένα που φτάνουν από το υπόλοιπο δίκτυο προς το κέντρο ελέγχου. Για την επίτευξη μιας πιο ισορροπημένης και αποδοτικής διαδικασίας συλλογής δεδομένων, τα τελευταία χρόνια έχει υιοθετηθεί μια νέα προσέγγιση, όπου το κέντρο ελέγχου είναι κινητό. Η βασική ιδέα είναι ότι το κέντρο ελέγχου διαθέτει σημαντικά και εύκολα ανανεώσιμα αποθέματα ενέργειας, επομένως μπορεί να κινείται στην περιοχή όπου έχει αναπτυχθεί το δίκτυο αισθητήρων, αναλαμβάνοντας να συλλέξει τα δεδομένα από τους κόμβους με πολύ μικρό κόστος. Ωστόσο, η μετάδοση των δεδομένων μπορεί να παρουσιάζει σημαντικές καθυστερήσεις. Συλλογή δεδομένων με προσαρμοστικούς χρόνους αναμονής: Στην παρούσα διατριβή αναπτύχθηκαν πρωτόκολλα ελέγχου της κίνησης ενός κέντρου ελέγχου σε δίκτυο αισθητήρων με ανομοιογενή ανάπτυξη των κόμβων αισθητήρων, με στόχο την αποδοτική, ως προς την ενέργεια και τον χρόνο παράδοσης, συλλογή των δεδομένων. Πιο συγκεκριμένα, αρχικά παρουσιάζεται ένα πρωτόκολλο με βάση το οποίο το κέντρο ελέγχου διαιρεί νοητά το δίκτυο σε περιοχές τις οποίες και επισκέπτεται διαδοχικά, σταματώντας σε κάθε περιοχή για ένα συγκεκριμένο χρονικό διάστημα, ώστε να συλλέξει τα δεδομένα. Προτείνουμε δύο τρόπους κίνησης του κέντρου ελέγχου, ντετερμινιστικό και τυχαίο. Στην τυχαία κίνηση, η επιλογή της επόμενης περιοχής την οποία θα επισκεφτεί το κέντρο ελέγχου γίνεται με τυχαίο τρόπο, εισάγοντας όμως ένα όρο μεροληψίας, έτσι ώστε να προτιμούνται περιοχές που έχουν δεχτεί λιγότερες επισκέψεις. Επιπλέον η μέθοδός μας αποφασίζει το χρόνο παύσης σε κάθε περιοχή λαμβάνοντας υπόψιν κάποιες βασικές παραμέτρους του δικτύου, όπως τα αρχικά αποθέματα ενέργειας των κόμβων αισθητήρων και την πυκνότητα της κάθε περιοχής, έτσι ώστε να παραμένει περισσότερο χρόνο σε περιοχές με μεγαλύτερη πυκνότητα, άρα και μεγαλύτερη ποσότητα πληροφορίας. Με τον τρόπο αυτό επιτυγχάνεται η γρήγορη κάλυψη όλου του δικτύου, καθώς επίσης και η δίκαιη εξυπηρέτηση των επιμέρους περιοχών του δικτύου. Προσαρμοστικοί τυχαίοι περίπατοι Στη συνέχεια, μελετάται η χρήση τυχαίων περιπάτων κατά την κίνηση του κέντρου ελέγχου σε δίκτυα αισθητήρων με στόχο την επίτευξη ενός ικανοποιητικού σημείου ισορροπίας μεταξύ κατανάλωσης ενέργειας και καθυστέρησης στην παράδοση των μηνυμάτων. Για την ικανοποίηση του στόχου αυτού, προτείνουμε τρεις νέους τυχαίους περιπάτους, τους α) Τυχαίος Περίπατος με Αδράνεια, κατά τον οποίο το κινούμενο αντικείμενο τείνει να διατηρεί την ίδια κατεύθυνση στην κίνησή του όσο ανακαλύπτει κόμβους αισθητήρων που δεν έχει επισκεφτεί και αλλάζει την κατεύθυνσή του όταν φτάνει σε κόμβους που έχει ξαναεπισκεφτεί, β) Explore-and-Go, κατά τον οποίο το κινούμενο αντικείμενο τείνει να εκτελεί μια Brownian κίνηση γύρω από την περιοχή του όσο υπάρχουν κόμβοι που δεν έχουν δεχτεί επίσκεψη, γ) Curly Random Walk, όπου το κινούμενο αντικείμενο διαπερνάει όλη την περιοχή του δικτύου ξεκινώντας από το κέντρο και επεκτείνοντας την κίνησή του με συνεχόμενες κυκλικές κινήσεις προς τα έξω. Για την εφαρμογή των τυχαίων περιπάτων χρησιμοποιούμε ένα νοητό πλέγμα ώστε να καλύπτουμε την περιοχή του δικτύου αισθητήρων• οι περίπατοι κινούνται πάνω στους κόμβους του πλέγματος. Αν και στις περισσότερες περιπτώσεις οι τυχαίοι περίπατοι μελετώνται σε Gn,p και Grid γράφους, τα δίκτυα αισθητήρων μοντελοποιούνται με μεγαλύτερη ακρίβεια χρησιμοποιώντας το μοντέλο των Random Geometric Graphs (RGG), εφόσον έτσι αναπαρίσταται καλύτερα η χωρική εγγύτητα του δικτύου. Οι παραπάνω τυχαίοι περίπατοι δεν δίνουν τα επιθυμητά αποτελέσματα όταν τρέχουν σε RGG. Έτσι οδηγηθήκαμε στο σχεδιασμό ενός νέου τυχαίου περιπάτου, του γ-Stretched Random Walk, η βασική ιδέα του οποίου είναι να μεροληπτεί υπέρ της επίσκεψης των πιο μακρινών γειτόνων του τρέχοντος κόμβου έτσι ώστε να μειώσει στο ελάχιστο τις επικαλύψεις στις επισκέψεις. Αλγόριθμοι που λαμβάνουν υπόψιν την ηλεκτρομαγνητική ακτινοβολία στο δίκτυο: Εκτός από τη μελέτη της κίνησης του κέντρου ελέγχου σε δίκτυα αισθητήρων, στη διατριβή αυτή παρουσιάζεται μια πρώτη προσπάθεια μελέτης θεμάτων σχετικά με την επίγνωση της εκπομπή ακτινοβολίας σε περιβάλλοντα όπου λειτουργούν πολλαπλά ετερογενή ασύρματα δίκτυα. Ως ακτινοβολία σε ένα σημείου του τρισδιάστατου χώρου καλούμε τη συνολική ποσότητητα ηλεκτρομαγνητικής ακτινοβολίας που δέχεται το σημείο αυτό. Έτσι, καταρχάς μελετάμε σε αναλυτικό επίπεδο την ακτινοβολία σε διάφορες γνωστές τοπολογίες (τυχαίες, πλέγματα) και κατόπιν επικεντρώνουμε το ενδιαφέρον μας στην εύρεση ενός μονοπατιού ελάχιστης ακτινοβολίας το οποίο ακολουθείται από κάποιο άτομο που κινείται στην περιοχή που καλύπτεται από ένα ασύρματο δίκτυο αισθητήρων. Προτείνουμε τρεις ευρετικές μεθόδους για την εύρεση του μονοπατιού καθώς το άτομο κινείται, ενώ υπολογίζουμε και την οffline λύση χρησιμοποιώντας τον αλγόριθμο ελάχιστου μονοπατιού. Κατόπιν, εξετάζουμε το θεμελιώδες πρόβλημα της διάδοσης των δεδομένων σε ασύρματα δίκτυα αισθητήρων, προσπαθώντας τόσο να παραμείνει γρήγορη η διαδικασία παράδοσης των μηνυμάτων, παράλληλα όμως και η συνολική ηλεκτρομαγνητική ακτινοβολία που παράγεται από τις συνεχείς ασύρματες μεταδόσεις να διατηρηθεί σε χαμηλά επίπεδα. Αυτό επιτυγχάνεται αρχικά χρησιμοποιώντας κάποιες άπληστες ευρετικές μεθόδους που όμως λαμβάνουν υπόψιν την ακτινοβολία. Επιπλέον, οι μέθοδοι αυτοί συνδυάζονται με μεθόδους που πραγματοποιούν back-off στο χρόνο, χρησιμοποιώντας τοπικές ιδιότητες του δικτύου (όπως ο αριθμός γειτόνων, η απόσταση από το κέντρο ελέγχου), έτσι ώστε «απλωθεί» κατά κάποιο τρόπο η ακτινοβολία τόσο ως προς το χρόνο αλλά και ως προς το χώρο. Τα προτεινόμενα πρωτόκολλα αξιολογήθηκαν πειραματικά μέσω προσομοίωσης, χρησιμοποιώντας ποικίλες τιμές για βασικές παραμέτρους του δικτύου και σύγκρινοντάς τα με σχετικές υπάρχουσες ευρέως αποδεκτές μεθόδους. Συστημικές Εφαρμογές: Τέλος, στη διατριβή παρουσιάζονται κάποιες συστημικές εφαρμογές ασύρματων δικτύων αισθητήρων σε κτίρια. Συγκεκριμένα, η πρώτη εφαρμογή αναλαμβάνει σε περίπτωση ανίχνευσης φωτιάς, την εύρεση του ελάχιστου μονοπατιού μακριά από το σημείο όπου έγινε η ανίχνευση. Επιπλέον, παρέχει καθοδήγηση στους ενοίκους του κτιρίου (οι οποίοι μοντελοποιούνται από ένα κινούμενο ρομπότ) έτσι ώστε να εγκαταλείψουν με ασφάλεια το κτίριο. Η επόμενη εφαρμογή παρουσιάζει τη δυνατότητα της απρόσκοπτης διασύνδεσης αυτοματισμών έξυπνων κτιρίων, αποτελούμενων από ενσωματωμένα συστήματα, στο διαδίκτυο και την αφαιρετικοποίησή τους ως απλά web services. Η προσέγγιση αυτή έχει στόχο την δημιουργία ενός ευέλικτου, εύκολα κλιμακώσιμου συστήματος που είναι προσβάσιμο και ελεγχόμενο απομακρυσμένα. Η προσέγγιση που ακολουθήθηκε και παρουσιάζεται στην παρούσα διατριβή περιλαμβάνει την ανάπτυξη ενός αριθμού αισθητήρων μέσα σε ένα κτίριο, οι οποίοι αποκτούν IPv6 διεύθυνση ώστε να είναι προσβάσιμοι διαδικτυακά, ενώ παράλληλα διασυνδέονται με ηλεκτρικές συσκευές του κτιρίου για σχηματισμό αυτοματισμών. Τέλος αναπτύχθηκε μία web εφαρμογή για απομακρυσμένη διαχείριση του δικτύου και του κτιρίου γενικότερα.
Abstract (translated): Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their environment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays. Data collection with biased stop times: In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, we first propose a protocol, where the sink partitions the network area in equal square regions and then performs a network traversal by visiting each area sequentially. Also, it pauses in each area for a certain amount of time, in order to collect the data. Two network traversal methods are proposed, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region. Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only. Adaptive random walks: Afterwards, in order to achieve satisfactory energy-latency trade-offs the use of random walks for the sink' s motion pattern is studied. Towards this direction three new random walks evaluated on a grid overlaying the wireless sensor network are proposed. The first one is the Random Walk with Inertia where the sink tends to keep the same direction as long as it discovers new nodes, while changing direction when it encounters already visited ones. The second one is the Explore-and-Go Random Walk, where as long as there are undiscovered nodes on the nearby sub-regions of the network it tends to make a Brownian-like motion until all this area is covered. When no new sensors are discovered, it performs a more or less straight-line walk in order to move to a different, possibly unvisited area. The last one is the Curly Random Walk where the sink traverses the network area beginning from the center and expanding its traversal to the entire network area with consecutive circular-like moves. In random walk studies the Gn,p and Grid graph models are well established. However, wireless sensor networks are more accurately modeled via Random Geometric Graphs (RGG), as RGG better capture certain characteristics of WSN's such as link existence dependencies of neighbouring nodes due to geometric proximity. The above mentioned random walks do not behave well on this particular graph model, thus a new random walk was defined, the so called γ-stretched random walk. Its basic idea is to favour visiting distant neighbours of the current node towards reducing node overlap. Radiation-aware algorithms: Except for the issue of mobility in wireless sensor networks, in this work we also attempt (probably for the first time from a distributed networking perspective) to investigate the aspect of electromagnetic radiation in modern and future heterogeneous wireless networks. We call “radiation” at a target elementary surface the total amount of electromagnetic quantity (in terms of energy or power density) it is exposed to. Thus, we first evaluate, both mathematically and by simulation, the radiation in well known sensor network topologies (random, grid) and then focus on the minimum radiation path problem of finding low radiation trajectories for a person moving in a sensor network. We propose three online heuristics and then we identify the (offline) optimum path given by the shortest paths' algorithm. Afterwards, we focus on the fundamental problem of efficient data propagation in wireless sensor networks, trying to keep latency low while maintaining at low levels the radiation cumulated by wireless transmissions. We first propose greedy and oblivious routing heuristics that are radiation aware. We then combine them with temporal back-off schemes that use local properties of the network (e.g. number of neighbours, distance from sink) in order to “spread” radiation in a spatio-temporal way. Al the proposed protocols were evaluated via simulation, in diverse network settings and comparatively to related state of the art solutions. Systems and applications: Finally, in this work we present two applications of wireless sensor networks in buildings. More specifically, the first application, in the event of a fire inside a monitored building, uses the information from the deployed sensor network in order to find the shortest safest path away from the emergency and provides navigation guidance to the occupants (modelled by a mobile robot), in order to safely evacuate the building. The second application addresses networked embedded systems enabling the seamless interconnection of smart building automations to the Internet and their abstractions as web services, using the latest technologies based on IPv6, such as 6LOWPAN, COAP and RESTLess Architecture.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)

Files in This Item:
File Description SizeFormat 
Nimertis_Patroumpa(com).pdf4.52 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.