Μελέτη Και Ανάθεση Πόρων Σε Χωρικά Δίκτυα Παρακολούθησης Παρουσία Εμποδίων

Abstract

Στην εργασία αυτή μελετάται ένα πρόβλημα κάλυψης ή παρακολούθησης του χώρου από αισθητήρες τοποθετημένους τυχαία σε ένα περιβάλλον με κυρτά αδιαφανή εμπόδια κατανεμημένα τυχαία. Οι αισθητήρες μπορούν να καλύπτουν τα σημεία ενός δίσκου με κέντρο αυτούς, στα οποία διαθέτουν ορατότητα γραμμής (line of sight). Οι αισθητήρες έχουν την δυνατότητα να μεταβάλλουν την ακτίνα κάλυψής τους, και με την αύξηση αυτής καταναλώνουν περισσότερη ενέργεια. Ο στόχος μας είναι να μπορούμενα παρακολουθούμε ένα μεγάλο ποσοστό του χώρου χωρίς να καταναλώνουμε πολλή ενέργεια. Για να πετύχουμε το ζητούμενο μοντελοποιήσαμε το πρόβλημα ως ένα πρόβλημα μεγιστοποίησης του λόγου του συνεργατικά καλυπτόμενου εμβαδού δια τη συνολική καταναλισκώμενη ενέργεια στο υποσύνολο των έγκυρων αναθέσεων των ακτίνων, που έχουν πάνω από ένα προκαθορισμένο ποσοστό κάλυψης. Έπειτα διατυπώσαμε ένα απλούστερο εναλλακτικό κριτήριο, όπου θέλαμε να ελαχιστοποιήσουμε την καταναλισκώμενη ενέργεια στο χώρο των λύσεων που έχουν τουλάχιστον το όριο κάλυψης που απαιτούμε. Δείξαμε ότι αυτό το πρόβλημα έχει λύση σε ένα μικρότερο σύνολο λύσεων στο οποίο η απλούστερη διατύπωση ταυτίζεται με την αρχική του λόγου εμβαδού δια ενέργεια. Επιπλέον είδαμε ότι ο μικρότερος αυτός χώρος λύσεων είναι υποσύνολο του συνόρου της αρχικής εφικτής περιοχής. Έπειτα αναπτύξαμε τρεις μεθόδους για την αντιμετώπιση των προβλημάτων αυτών, γύρω από την κεντρική ιδέα προτίμησης κόμβων οι οποίοι με μικρές διαφοροποιήσεις της ακτίνας έχουν μεγάλες διαφοροποιήσεις στο λόγο Εμβαδού δια Ενέργεια. 1) Η πρώτη μέθοδος, του Άπληστου Κεντρικοποιημένου Αλγόριθμου, ξεκινάει από μια μηδενική κατάσταση για όλες τις ακτίνες των αισθητήρων και κάθε φορά επιλέγει να αυξήσει τον αισθητήρα με τον καλύτερο λόγο εμβαδού δια ενέργειας. Ο αλγόριθμος τερματίζει όταν περάσει το όριο κάλυψης που θέλουμε. 2) Έπειτα αναπτύξαμε έναν Τυχαιοποιημένο Άπληστο Αλγόριθμο ο οποίος επιλέγει από ένα τυχαίο υποσύνολο των κόμβων, τον κόμβο που θα αυξηθεί. 3) Τέλος ορίσαμε έναν Κατανεμημένο Τοπικό Αλγόριθμο, ο οποίος ορίζει έναν γράφο που εκφράζει τις εξαρτήσεις μεταξύ των κόμβων, και βασισμένοι σε αυτόν οι κόμβοι αποφασίζουν εάν θα μεταβάλλουν ή όχι την ακτίνα τους ανεξάρτητα. Ορίσαμε επίσης ένα κατανεμημένο κριτήριο απόφασης διακοπής αύξησης της ακτίνας ανεξάρτητα για κάθε κόμβο. Ολοκληρώσαμε την εργασία αυτή με εκτεταμένες προσομοιώσεις, όπου και χρησιμοποιήθηκαν μετρικές για την αξιολόγηση των αποτελεσμάτων.