3.8

Υπολογισμός τελικού μονοπατιού

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

6, πραγματοποιείται η προσπέλαση του. Κατά την προσπέλαση, διατηρείται ένας

μετρητής C που μετράει το πλήθος των χωροpixel που έχουν επισκευθεί μέχρι στιγ-

μής. Επίσης, διατηρείται ένας αθροιστής S που αθροίζει το μέγεθος των δεδομένων

που έχουν συλλεχθεί μέχρι στιγμής. Σε κάθε βήμα, χρησιμοποιώντας τον αλγόριθμο

2, υπολογίζεται η συντομότερη διαδρομή CED (ClosestEnergyDistance) και το κό-

στος αυτής (C

CED

) που συνδέει το συγκεκριμένο χωροpixel από την το σύνολο των

χωροpixel στα οποία υπάρχει διαθέσιμη πηγή ενέργειας. Επιπλέον, υπολογίζεται η

συντομότερη διαδρομή CDD (ClosestDataDistance) και το κόστος αυτής (C

C

DD

)

που συνδέει το συγκεκριμένο χωροpixel από το σύνολο όλων των χωροpixel στα

οποία εκπέμπουν οι σταθμοί εκπομπής. Έτσι, όταν η εξ. 3.5 ή η εξ. 3.6 πλησιάζουν

στο 0, σταματάει προσωρινά η προσπέλαση του Ελαχίστου Γεννητικού Δέντρου και

το όχημα κατευθείνεται προς την πηγή ενέργειας ή προς το συντομότερο χωροpixel

στο οποίο υπάρχη εκπομπή ενός σταθμού. Για την κατεύθυνση του οχήματος χρη-

σιμοποιούνται οι διαδρομές CED και CDD που υπολογίστηκαν προηγουμένως. Σε

περίπτωση που ταυτοχρονα μηδενίζουν και οι δύο εξισώσεις, δίνεται προτεραιότητα

στην πηγή ενέργειας. Έτσι, ο αλγόριθμος εγγυάται: (α) πως το καθε όχημα θα επι-

λέξει να χρησιμοποιήσει την πηγή ενέργειας την κατάλληλη στιγμή, (β) πως κανένα

όχημα δεν σταματησει στην μέση της κάλυψης χώρου λόγω έλλειψης ενέργειας και

(γ) πως τα οχήματα θα επισκέπτονται χωροpixel εντός εμβέλειας κάποιου σταθμού

εκπομπής όταν αυτό είναι απαραίτητο, δηλαδή όταν ο διαθέσιμος αποθηκευτικός

χώρος πλησιάζει στο 0.

E = T otalEnergy

− C − C

CED

(3.5)

D = T otalCapacity

− C · DataCollectedP erV otile − C

CDD

· DataCollectedP erV otile

(3.6)

45