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

Abstract

In recent years, Wireless Sensor Networks and GeoSensor Networks (WSN and GSN) have rapidly evolved and now comprise a powerful tool in monitoring and observation of the natural environment, among other fields. The use of WSNs is critical in early warning systems, which are in high importance today.The optimum deployment of sensors is a multi-dimensional problem, which has two main components; network and positioning approach. In some cases, it is hard or even impossible to achieve perfect geometry in nodes’ deployment. The ideal and desirable scenario of nodes arranged in square or hexagonal grid would raise extremely the cost of the network, especially in unfriendly or hostile environments. In such environments the positions of the sensors have to be chosen among a list of possible points, which in most cases are randomly distributed. This constraint has to be taken under consideration during the WSN planning. Full geographical coverage is in some applications of the same, if not of greater importance than the network coverage. Cost is a crucial factor in network planning and given that resources are often limited, what matters, is to cover the whole area with the minimum number of sensors.In this PhD thesis a new methodology for sensor deployment and evaluation of the geometry of WNS is developed. The proposed methodology can be applied in any application, in which a WSN is required, with or without limitations to the positioning of the sensors, such as a fire detection WSN in a forest area or an extensive network for detecting deformations.The thesis consists of five chapters.The first chapter presents the relatively new science of WSNs and geosensorics. Definitions and basic concepts are given regarding the use of these instruments as a means for detection and monitoring of natural and artificial environment.In the second chapter the optimal deployment problem of a WSN is described. An introduction to the computational geometry and its application fields is made. The solution is approached by using the properties of Voronoi Diagrams and more specifically, the Centroidal Voronoi Tessellation (CVT). The theoretical background for both VD and CVT is given, before the proposed methodology is thoroughly explained.In the third chapter the evaluation method of the deployment of a WSN is approached, using the Delaunay triangulation, which is the dual graph of the Voronoi diagram.The fourth chapter presents the software created for the proposed deployment and evaluation methodologies of a WSN.In order to examine the functioning and the efficiency of the algorithm, different simulation scenarios were created and tests with different parameters were conducted. Special occasions of deployment are also faced. The findings of all these scenarios are recorded and analyzed.In the fifth and final chapter the conclusions of the research are presented and recommendations for future work are made.The main conclusion of the thesis is that the specific deployment and evaluation methodologies for WSNs and GSNs in any environment is efficient, fully customizable and reliable.With criterion the minimizing of the cost of the installation and the maintenance of the network, the optimum positions among all the candidate ones are searched, in order to achieve full coverage of the area with geometry that is as close as possible to the ideal one (equilateral triangles).

Τα τελευταία χρόνια, τα ασύρματα δίκτυα αισθητήρων και γεωαισθητήρων (WSN και GSN) εξελίσσονται με γρήγορο ρυθμό και συνθέτουν ένα ισχυρό εργαλείο για την παρακολούθηση και την παρατήρηση του φυσικού περιβάλλοντος. Η χρήση των ασύρματων δικτύων αισθητήρων είναι κομβικής σημασίας για τα συστήματα έγκαιρης προειδοποίησης, που ολοένα και συχνότερα χρησιμοποιούνται σήμερα.Στη διατριβή αυτή αναπτύσσεται μια νέα μεθοδολογία χωροθέτησης και αξιολόγησης ασύρματων δικτύων αισθητήρων και γεωαισθητήρων. Η προτεινόμενη μεθοδολογία μπορεί να αξιοποιηθεί σε οποιαδήποτε εφαρμογή παρουσιάζεται η απαίτηση για δίκτυα αισθητήρων, με ή χωρίς περιορισμούς ως προς τις θέσεις εγκατάστασης των αισθητήρων, όπως για παράδειγμα η εγκατάσταση δικτύου αισθητήρων ανίχνευσης πυρκαγιών σε δασική περιοχή ή η εγκατάσταση εκτεταμένου δικτύου αισθητήρων για ανίχνευση μικρομετακινήσεων ή παραμορφώσεων.Η διδακτορική διατριβή αποτελείται από 5 κεφάλαια.Στο πρώτο παρουσιάζεται η σχετικά νέα επιστήμη των γεωαισθητήρων (geosensorics). Δίνονται βασικές έννοιες και ορισμοί που βοηθούν στην καλύτερη κατανόηση των οργάνων αυτών ως μέσα ανίχνευσης και παρακολούθησης φυσικών και τεχνητών φαινομένων. Αναλύεται ο τρόπος λειτουργίας ενός ασύρματου δικτύου γεωαισθητήρων. Για να γίνει κατανοητή η ανάγκη παρακολούθησης φαινομένων με τη βοήθεια ασύρματων δικτύων γεωαισθητήρων, αναφέρονται ενδεικτικά ορισμένες εφαρμογές – από διαφορετικά επιστημονικά πεδία.Στο δεύτερο κεφάλαιο αναπτύσσεται το πρόβλημα της βέλτιστης χωροθέτησης ασύρματων δικτύων γεωαισθητήρων στο οποίο εστίασε η παρούσα διατριβή, καθώς και η προτεινόμενη μεθοδολογία επίλυσής του. Η επίλυση του προβλήματος προσεγγίζεται αξιοποιώντας τις ιδιότητες των πολύγωνων Voronoi και πιο συγκεκριμένα με την κεντροειδή διαμέριση Voronoi (CVT), μεθοδολογίες οι οποίες αναλύονται διεξοδικά.Το κεφάλαιο ολοκληρώνεται με την προτεινόμενη μεθοδολογία επιλογής των βέλτιστων θέσεων χωροθέτησης αισθητήρων.Στο τρίτο κεφάλαιο προσεγγίζεται η μεθοδολογία αξιολόγησης της χωροθέτησης, κάνοντας χρήση του τριγωνισμού Delaunay, ο οποίος αποτελεί ουσιαστικά το δυικό γράφημα του διαγράμματος Voronoi.Εξετάζονται πιθανές μετρικές, καταγράφονται τα πλεονεκτήματα και τα μειονεκτήματα κάθε μίας από τα οποία και προκρίνεται η μέση τιμή της τυπικής απόκλισης των πλευρών των τριγώνων που δημιουργούνται στο δίκτυο, ως η πλέον κατάλληλη. Στο τέλος του κεφαλαίου αναλύεται ο προτεινόμενος αλγόριθμος αξιολόγησης.Στο τέταρτο κεφάλαιο παρουσιάζεται το λογισμικό το οποίο δημιουργήθηκε με σκοπό τη διαδικασία χωροθέτησης και αξιολόγησης του ασύρματου δικτύου γεωαισθητήρων.Δημιουργούνται διαφορετικά σενάρια προσομοίωσης και πραγματοποιούνται δοκιμές με διαφορετικές παραμέτρους, ενώ εξετάζονται και ειδικές περιπτώσεις χωροθέτησης και καταγράφονται τα συμπεράσματα που προκύπτουν από τα σενάρια αυτά.Στο πέμπτο κεφάλαιο παρουσιάζονται τα συμπεράσματα που προέκυψαν από και γίνονται προτάσεις για περαιτέρω έρευνα.Βασικό συμπέρασμα της διδακτορικής διατριβής είναι, ότι η συγκεκριμένη μεθοδολογία χωροθέτησης και αξιολόγησης ενός ασύρματου δικτύου γεωαισθητήρων σε οποιοδήποτε περιβάλλον είναι αποδοτική, πλήρως παραμετροποιήσιμη και αξιόπιστη.Με γνώμονα την ελαχιστοποίηση του κόστους εγκατάστασης και συντήρησης του δικτύου, ζητούνται οι καλύτερες θέσεις αυτών, μεταξύ των υποψηφίων θέσεων τοποθέτησης, ώστε να επιτυγχάνεται η πλήρης κάλυψη της περιοχής με γεωμετρία που να πλησιάζει όσο είναι δυνατόν την ιδανική (ισόπλευρα τρίγωνα).