Μελέτη Αποδοτικών Αλγορίθμων για τον Έλεγχο Τοπολογίας σε Ασύρματα Δίκτυα Αισθητήρων Παρουσία Εμποδίων

Abstract

Τα τελευταία χρόνια παρατηρείται αυξημένο ενδιαφέρον για τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ), καθώς έχουν πληθώρα εφαρμογών. Βασικό χαρακτηριστικό ενός ασύρματου δικτύου είναι η κάλυψη – παρακολούθηση του χώρου. Επίσης η συνδεσιμότητα του είναι αναγκαία συνθήκη για την ομαλή λειτουργία του. Στην παρούσα εργασία μελετούνται τρόποι μείωσης της ενεργειακής κατανάλωσης ενός ασύρματου δικτύου αισθητήρων, που σχηματίζεται από αισθητήρες τοποθετημένους με τυχαίο τρόπο σε ένα δισδιάστατο χώρο με κυρτά, αδιαφανή εμπόδια. Η μείωση της ενεργειακής κατανάλωσης πρέπει να συντελείται χωρίς την υποβάθμιση των λειτουργιών του δικτύου, επομένως, υπό τις προϋποθέσεις της πλήρους κάλυψης του χώρου και της επικοινωνίας του συνόλου των αισθητήρων. Οι αισθητήρες θεωρούμε ότι διαθέτουν μεταβλητές ακτίνες αίσθησης και επικοινωνίας, με την ενεργειακή κατανάλωση να αυξάνεται με κάθε αύξηση της αντίστοιχης ακτίνας. Με βάση τις ακτίνες αυτές ορίζονται κυκλικοί δίσκοι με κέντρο τον αισθητήρα, εντός των οποίων ο αισθητήρας μπορεί να συλλέξει πληροφορίες ή να επικοινωνήσει αντίστοιχα. Ακόμα θεωρούμε το κόστος λειτουργίας των αισθητήρων ως το άθροισμα της ενέργειας που απαιτείται για την συλλογή πληροφοριών από τον περιβάλλοντα χώρο, την ενέργεια που καταναλώνει ένας αισθητήρας για την επικοινωνία του με τους υπόλοιπους, και το κόστος τοποθέτησης του αισθητήρα. Στόχος μας είναι η ελαχιστοποίηση του κόστους αυτού ενώ παράλληλα διατηρούνται κάποια σημαντικά χαρακτηριστικά του δικτύου (συνδεσιμότητα, πλήρης κάλυψη περιοχής ενδιαφέροντος). Το πετυχαίνουμε αυτό χωρίζοντας το πρόβλημα στα επιμέρους προβλήματα της μείωσης της ενεργειακής κατανάλωσης για την επικοινωνία των αισθητήρων και στην κατανάλωση για τη συλλογή πληροφοριών από το χώρο. Μοντελοποιώντας το δίκτυο αισθητήρων ως έναν γεωμετρικό γράφο, διατυπώνεται ένας αλγόριθμος που βασίζεται στον υπολογισμό του ελάχιστου συνδετικού δέντρου, με κόμβους τους αντίστοιχους αισθητήρες και ακμές μεταξύ των αντίστοιχων κόμβων εάν και μόνο εάν η απόσταση των αισθητήρων είναι μικρότερη ή ίση με τη μέγιστη ακτίνα επικοινωνίας και δεν παρεμβάλλεται κάποιο εμπόδιο. Στις ακμές αυτές ως βάρος ορίζεται η απόσταση των δύο αισθητήρων που αντιστοιχούν στους κόμβους που αυτές ενώνουν. Τέλος υπολογίζεται το ελάχιστο συνδετικό δένδρο και έτσι μπορούμε να ορίσουμε σε κάθε αισθητήρα ως τιμή ακτίνας επικοινωνίας το μέγιστο βάρος από τα βάρη των ακμών που προσπίπτουν στον αντίστοιχο κόμβο. Για τη μείωση της ενέργειας που απαιτείται για τη συλλογή πληροφοριών από το χώρο χρησιμοποιούνται κάποιοι άπληστοι αλγόριθμοι –κατανεμημένοι και κεντρικοποιημένοι- που συναντούνται στην βιβλιογραφία καθώς και μία παραλλαγή ενός κατανεμημένου. Στην παραλλαγή που προτείνουμε, χωρίζεται ολόκληρος ο χώρος ενδιαφέροντος σε τετραγωνικά, ισομεγέθη πλέγματα, με βάση τα οποία δίνεται η έννοια της «γειτονιάς» κάθε κόμβου, τους κοντινούς του κόμβους δηλαδή που χρησιμοποιεί για να λάβει τις αποφάσεις αυξομείωσης της ακτίνας του. Επίσης μεταβάλλεται το κριτήριο τερματισμού, αντιμετωπίζοντας έτσι κάποια προβλήματα του Κατανεμημένου Αλγορίθμου του Χρήστου Ν. Τσανικίδη. Η εργασία καταλήγει με την εκτέλεση εκτενών προσομοιώσεων και την αξιολόγηση και σύγκριση των προτεινόμενων αλγορίθμων και των αλγορίθμων της βιβλιογραφίας με τη χρήση διαφόρων μετρικών.