Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13745
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΧρήστος Τσανικίδης
dc.date.accessioned2018-07-23T09:30:55Z-
dc.date.available2018-07-23T09:30:55Z-
dc.date.issued2018-4-2
dc.date.submitted2018-3-19
dc.identifier.urihttp://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13745-
dc.description.abstractΣτην εργασία αυτή μελετάται ένα πρόβλημα κάλυψης ή παρακολούθησης του χώρου από αισθητήρες τοποθετημένους τυχαία σε ένα περιβάλλον με κυρτά αδιαφανή εμπόδια κατανεμημένα τυχαία. Οι αισθητήρες μπορούν να καλύπτουν τα σημεία ενός δίσκου με κέντρο αυτούς, στα οποία διαθέτουν ορατότητα γραμμής (line of sight). Οι αισθητήρες έχουν την δυνατότητα να μεταβάλλουν την ακτίνα κάλυψής τους, και με την αύξηση αυτής καταναλώνουν περισσότερη ενέργεια. Ο στόχος μας είναι να μπορούμενα παρακολουθούμε ένα μεγάλο ποσοστό του χώρου χωρίς να καταναλώνουμε πολλή ενέργεια. Για να πετύχουμε το ζητούμενο μοντελοποιήσαμε το πρόβλημα ως ένα πρόβλημα μεγιστοποίησης του λόγου του συνεργατικά καλυπτόμενου εμβαδού δια τη συνολική καταναλισκώμενη ενέργεια στο υποσύνολο των έγκυρων αναθέσεων των ακτίνων, που έχουν πάνω από ένα προκαθορισμένο ποσοστό κάλυψης. Έπειτα διατυπώσαμε ένα απλούστερο εναλλακτικό κριτήριο, όπου θέλαμε να ελαχιστοποιήσουμε την καταναλισκώμενη ενέργεια στο χώρο των λύσεων που έχουν τουλάχιστον το όριο κάλυψης που απαιτούμε. Δείξαμε ότι αυτό το πρόβλημα έχει λύση σε ένα μικρότερο σύνολο λύσεων στο οποίο η απλούστερη διατύπωση ταυτίζεται με την αρχική του λόγου εμβαδού δια ενέργεια. Επιπλέον είδαμε ότι ο μικρότερος αυτός χώρος λύσεων είναι υποσύνολο του συνόρου της αρχικής εφικτής περιοχής. Έπειτα αναπτύξαμε τρεις μεθόδους για την αντιμετώπιση των προβλημάτων αυτών, γύρω από την κεντρική ιδέα προτίμησης κόμβων οι οποίοι με μικρές διαφοροποιήσεις της ακτίνας έχουν μεγάλες διαφοροποιήσεις στο λόγο Εμβαδού δια Ενέργεια. 1) Η πρώτη μέθοδος, του Άπληστου Κεντρικοποιημένου Αλγόριθμου, ξεκινάει από μια μηδενική κατάσταση για όλες τις ακτίνες των αισθητήρων και κάθε φορά επιλέγει να αυξήσει τον αισθητήρα με τον καλύτερο λόγο εμβαδού δια ενέργειας. Ο αλγόριθμος τερματίζει όταν περάσει το όριο κάλυψης που θέλουμε. 2) Έπειτα αναπτύξαμε έναν Τυχαιοποιημένο Άπληστο Αλγόριθμο ο οποίος επιλέγει από ένα τυχαίο υποσύνολο των κόμβων, τον κόμβο που θα αυξηθεί. 3) Τέλος ορίσαμε έναν Κατανεμημένο Τοπικό Αλγόριθμο, ο οποίος ορίζει έναν γράφο που εκφράζει τις εξαρτήσεις μεταξύ των κόμβων, και βασισμένοι σε αυτόν οι κόμβοι αποφασίζουν εάν θα μεταβάλλουν ή όχι την ακτίνα τους ανεξάρτητα. Ορίσαμε επίσης ένα κατανεμημένο κριτήριο απόφασης διακοπής αύξησης της ακτίνας ανεξάρτητα για κάθε κόμβο. Ολοκληρώσαμε την εργασία αυτή με εκτεταμένες προσομοιώσεις, όπου και χρησιμοποιήθηκαν μετρικές για την αξιολόγηση των αποτελεσμάτων.
dc.languageGreek
dc.subjectευρετικές μέθοδοι
dc.subjectβελτιστοποίηση
dc.subjectχωρικά δίκτυα παρακολούθησης
dc.subjectανάθεση πόρων
dc.subjectπρόβλημα κάλυψης
dc.titleΜελέτη Και Ανάθεση Πόρων Σε Χωρικά Δίκτυα Παρακολούθησης Παρουσία Εμποδίων
dc.typeDiploma Thesis
dc.description.pages95
dc.contributor.supervisorΠαπαβασιλείου Συμεών
dc.departmentΤομέας Επικοινωνιών, Ηλεκτρονικής & Συστημάτων Πληροφορικής
dc.organizationΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2018-0073.pdf2.36 MBAdobe PDFView/Open


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