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

Ταρνάρης, Κωνσταντίνος

Development of optimization schemes for wireless sensor networks

Μεταπτυχιακή διπλωματική εργασία

Author

Ταρνάρης, Κωνσταντίνος

Date

2022-02-22

Advisor

Kandris, Dionisis

Κύριο άρθρο (2.873Mb)

Keywords

Αλγόριθμος βελτιστοποίησης σμήνους σωματιδίων ; Αλγόριθμος σμήνους σωματιδίων ; Ασύρματα δίκτυα αισθητήρων ; Γενετικοί αλγόριθμοι ; Κάλυψη ; κ-Κάλυψη ; Υπολογιστική νοημοσύνη

Abstract

Τα ασύρματα δίκτυα αισθητήρων (ΑΔΑ) έχουν προσελκύσει τεράστιο ερευνητικό ενδιαφέρον. Ένα σημαντικό αντικείμενο της έρευνας στα ασύρματα δίκτυα αισθητήρων είναι το πρόβλημα κάλυψης. Πρόκειται για το πρόβλημα της εύρεσης της βέλτιστης διάταξης με την οποία πρέπει να τοποθετηθούν οι αισθητήριοι κόμβοι σε ένα δίκτυο, οι οποίοι έχουν δεδομένη εμβέλεια ανίχνευσης, προκειμένου να μεγιστοποιηθεί το ποσοστό της περιοχής που καλύπτεται από αυτούς. Αντίστοιχα, το πρόβλημα της κ-κάλυψης αφορά τη διασφάλιση ότι μια περιοχή ενδιαφέροντος θα ανιχνεύεται πάντα ταυτόχρονα από τουλάχιστον κ αισθητήριους κόμβους. Σκοπός αυτής της μεταπτυχιακής διατριβής είναι η μελέτη υφιστάμενων μεθοδολογιών και η ανάπτυξη νέων μεθοδολογιών αυτού του είδους που αποσκοπούν στη μεγιστοποίηση της κάλυψης και της πολλαπλής κάλυψης σε ασύρματα δίκτυα αισθητήρων, βελτιστοποιώντας την τοποθέτηση των αισθητήριων κόμβων στον χώρο. Ειδικότερα, αρχικά πραγματοποιήθηκε η εισαγωγή αφενός μεν στο σχετικό θεωρητικό υπόβαθρο που αφορά στην κάλυψη και την κ-κάλυψη στα ασύρματα δίκτυα αισθητήρων, αφετέρου δε σε μεθόδους της υπολογιστικής νοημοσύνης και ειδικότερα στους εξελικτικούς αλγορίθμους και στον αλγόριθμο βελτιστοποίησης σμήνους σωματιδίων που χρησιμοποιήθηκαν σε αυτήν την ερευνητική εργασία για την ανάπτυξη καινοτόμων σχημάτων βελτιστοποίησης της κάλυψης σε ασύρματα δίκτυα αισθητήρων. Στη συνέχεια, διερευνήθηκε η εύρεση λύσης στα συγκεκριμένα προβλήματα με χρήση γενετικών αλγορίθμων (genetic algorithms, GA), και του αλγόριθμου βελτιστοποίησης σμήνους σωματιδίων (particle swarm optimization, PSO) που αποτελεί κατηγορία των αλγορίθμων που βασίζονται στην ευφυΐα σμήνους και μιμείται τον τρόπο με τον οποίο αλληλεπιδρούν σμήνη πτηνών ως προς την εύρεση της βέλτιστης διαδρομής που θα ακολουθήσουν. Μέσω μίας σειράς πειραμάτων κλιμακούμενης δυσκολίας, αξιολογήθηκε η απόδοση των σχημάτων ελέγχου που αναπτύχθηκαν. Ειδικότερα, στα αρχικά πειράματα διακριβώθηκε η δυνατότητα να επιτευχθεί η μεγιστοποίηση της κάλυψης του χώρου και στα επόμενα, διερευνήθηκε και η δυνατότητα των σχημάτων ελέγχου να επιτύχουν επιπρόσθετα και κ-κάλυψη. Τέλος, η απόδοση των σχημάτων ελέγχου που αναπτύχθηκαν συγκρίθηκε με αυτήν δύο δημοφιλών αλγορίθμων αυτού του είδους.

Abstract

Wireless sensor networks (WSNs) have attracted enormous research interest. The coverage problem is an important subject of research in WSNs. This is the problem of finding the optimal arrangement with which the sensor nodes must be placed in a network, which have a given detection range, in order to maximize the percentage of the area covered by them. Accordingly, the problem of k coverage is to ensure that an area of interest is always detected simultaneously by at least k sensor nodes. The purpose of this master's thesis is the study of existing methodologies and the development of new methodologies of this kind that aim to maximize coverage and multiple coverage in wireless sensor networks, optimizing the placement of the sensor nodes existing within the network field. In particular, at first the relevant theoretical background on both coverage and k-coverage in WSNs and specific methods of computational intelligence used in this thesis was established. Next, the solution to the specific problems was investigated using genetic algorithms (GA), and the particle swarm optimization (PSO) algorithm. Through a series of scalable experiments, the performance of the control schemes developed was evaluated. In particular, in the initial experiments the possibility of achieving the maximization of the coverage of the space was verified and in the subsequent ones, the possibility of the control schemes to achieve additional and k-coverage was investigated. Finally, the performance of the control schemes developed was compared with that of two popular algorithms of this kind.