Μα καλά, πώς δουλεύει το GPS;

Είσαι στο κέντρο της πόλης σου, είναι μεσημέρι και σε παίρνει τηλέφωνο το φιλαράκι σου. Σου λέει να πας να την/τον συνατήσεις σε ένα μαγαζί που δεν ξέρεις καν ότι υπάρχει… Τι κάνεις;

Σιγά την απορία… Βγάζεις το κινητό, μπαίνεις στο Google Maps ή το Apple Maps, γράφεις το όνομα του μαγαζιού και σε 5 λεπτά είσαι εκεί!

Αλήθεια όμως… Πώς ξέρει το κινητό σου που βρίσκεται το μαγαζί; Πώς ξέρει καν που βρίσκεσαι εσύ; Επίσης, πώς ξέρει από όλους αυτούς τους δρόμους που υπάρχουν ποιον να ακολουθήσει;

Το πιο πιθανό είναι να μην τα είχες σκεφτεί όλα αυτά μέχρι τώρα… Ή ακόμα και αν τα είχες σκεφτεί, μάλλον η πιο προφανής απάντηση που είχες δώσει είναι ότι με κάποιο μαγικό τρόπο, κάπως, απλά δουλεύουν…

Για να είμαστε όμως ειλικρινείς, δεν είναι έτσι… Οι παραπάνω ερωτήσεις αποτελούν μέρος προβλημάτων που μαθηματικοί, μηχανικοί, φυσικοί, γενικά, η επιστημονική κοινότητα προσπαθεί να λύσει για χρόνια. Και εμείς σήμερα θα δούμε μόλις την βασική ιδέα για το πώς προσπαθούν να το καταφέρουν αυτό.

🛰 Τι σημαίνει GPS;

Ας ξεκινήσουμε με το να πούμε σε τι αναφέρεται η συντομογραφία GPS.

Είναι τα αρχικά των λέξεων Global Positioning System και χρησιμοποιείται για την αμερικανική υλοποίηση ενός παγκόσμιου συστήματος εντοπισμού γεωγραφικής θέσης.

Μία ερώτηση που ίσως έχεις τώρα είναι… Αμερικανικό; Δεν είναι διεθνές; Υπάρχουν δηλαδή και άλλες υλοποιήσεις;

Στην πραγματικότητα, ναι! Υπάρχουν και άλλες υλοποιήσεις, με τις δύο πιο γνωστές να είναι το GLONASS και το Galileo.

Τι κοινό έχουν όμως όλα αυτά;

Αποτελούν μεθόδους εντοπισμού θέσης, βασισμένες σε τεχνικές που ανήκουν στο Global Navigation Satellite Systems (GNSS).

Με απλά λόγια, πρόκειται για τεχνικές που αξιοποιούν δορυφόρους για να εκτιμήσουν τη θέση μας πάνω στη Γη.

Ένα απλοποιημένο παράδειγμα του τρόπου λειτουργίας τους, το οποίο θα δούμε στη συνέχεια, παρουσιάζεται εδώ:

Κάπου δηλαδή υπάρχουν οι δορυφόροι, αυτοί εκπέμπουν σήματα, το κινητό τα αντιλαμβάνεται αυτά τα σήματα, και με την χρήση αυτών των σημάτων, υπολογίζει την θέση του.

📌 Κόμβοι

Πριν επιχειρήσουμε να πούμε περισσότερα όμως σχετικά με το πρόβλημα του εντοπισμού της θέσης, ας δούμε πρώτα μερικούς ορισμούς.

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

Η πληροφορία σχετικά με τη θέση αυτών των nodes είναι γνωστή, είτε επειδή έχουν τοποθετηθεί από εμάς σε προκαθορισμένες θέσεις (π.χ. επίγειες κεραίες), είτε μέσω ενός εξωτερικού συστήματος. Για το πρόβλημα του GPS, αυτά τα nodes, συνήθως είναι οι δορυφόροι.

Αντίθετα, οι κόμβοι για τους οποίους δεν έχουμε αρχικά πληροφορίες για τη θέση τους, ονομάζονται Non-anchors. Στο παράδειγμα μας, μάλλον το κινητό θα ήταν ένας τέτοιος κόμβος.

Ένας άλλος σημαντικός ορισμός που θα πρέπει να αναφερθεί είναι ότι συχνά ονομάζουμε Settle nodes εκείνα τα οποία αρχικά δεν γνωρίζαμε τη θέση τους, αλλά στη συνέχεια την εκτιμήσαμε.

Ελπίζω ο παρακάτω πίνακας να το κάνει λίγο πιο ξεκάθαρο αυτό που μόλις αναφέραμε:

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

❓ Το κύριο πρόβλημα

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

Δηλαδή μπορούμε να χρησιμοποιήσουμε ηλεκτρομαγνητικά κύματα, ακουσικά κύματα ή οπτικές μεθόδους για να καταφέρουμε τον στόχο μας.

Σκοπός ενός localization system είναι, με χρήση της γνώσης που έχουμε για τα beacon nodes, να εκτιμηθεί η θέση όσο περισσότερων unknown nodes ώστε να τα μετατρέψουμε σε settled nodes και η εκτίμηση της κάθε θέσης να έχει όσο το δυνατόν μικρότερο error απόκλισης.

Κοίτα…

Ακριβώς παρακάτω υπάρχει ένας πίνακας…

Ευτυχώς, δεν θα σε βάλω να τον μάθεις απέξω. Απλά υπάρχει προκειμένου να κατανοήσεις ότι ήδη υπάρχουν διάφορες μέθοδοι, τεχνικές και αλγόριθμοι που χρησιμοποιούνται πίσω από τα συστήματα εντοπισμού της θέσης.

Γενικά, οι επιστήμονες έχουν - στις δημοσιεύσεις τους - χωρίσει το localization system σε τρία διακριτά components, για να απλοποιήσουν λίγο τα πράγματα.

Πρώτον, μπορεί να θεωρηθεί αυτό του Distance/Angle Estimation, του οποίου ο σκοπός είναι να υπολογίσει τη γωνία ή την απόσταση που έχουν δύο nodes του συστήματος μεταξύ τους. Η πληροφορία που θα παραχθεί από αυτό το component θα χρησιμοποιηθεί στα άλλα μέρη του συστήματος.

Στη συνέχεια, υπάρχει το Position Computation, του οποίου η δουλειά είναι να υπολογίσει την γεωγραφική θέση ενός node με βάση τη γνώση που έχουμε για τα beacons και την πληροφορία που λάβαμε από το πρώτο component.

Τέλος, υπάρχει το κύριο μέρος του συστήματος, με το όνομα Localization Algorithm, το οποίο ουσιαστικά είναι ο προκαθορισμένος τρόπος που θα ακολουθηθεί για να υπολογιστεί η θέση των unknown nodes με βάση όλες τις πληροφορίες που έχουμε.

Με βάση τον παραπάνω διαχωρισμό των Localization Systems σε τρία διακριτά μέρη, μπορούμε να καταλάβουμε ότι η απόκλιση της εκτίμησης του συνολικού συστήματος εξαρτάται από τα σφάλματα του κάθε μεμονωμένου μέρους.

Τέλος, έχει ήδη αναφερθεί ότι το πρόβλημα προσδιορισμού της θέσης ενός αντικειμένου μπορεί να προσεγγιστεί με χρήση διαφορετικών μεθόδων, οι οποίες μπορούν να κατηγοριοποιηθούν σε τεχνικές που σχετίζονται με ενέργεια (π.χ. RF και sound) και τεχνικές που σχετίζονται με οπτικά μέσα (κάποιες φορές μπορούν ακόμη και να συνδυαστούν βασικές αρχές της κάθε μίας για μία ενοποιημένη υλοποίηση).

∳ Υπολογισμοί

Νομίζω ότι πλέον είσαι έτοιμος να πάμε στα μαθηματικά!

Ξέρεις όλη την θεωρία, ΌΛΑ ΌΣΑ ΧΡΕΙΑΖΟΝΤΑΙ (😛)! Καιρός να τα δούμε στην πράξη λοιπόν.

Από την εικόνα στην αρχή του άρθρου, που δείχνει τους δορυφόρους, είδες κάποιους κύκλους να σχηματίζονται, με κέντρο τον δορυφόρο και ακτίνα το κινητό.

Για την ακρίβεια, δεν είναι κύκλοι, αλλά σφαίρες, αν μιλάμε για τον τρισδιάστατο χώρο.

Αν λοιπόν με κάποιον τρόπο καταφέρουμε να μετρήσουμε την απόσταση (ακτίνα) του δορυφόρου από το κινητό, τότε μπορούμε να έχουμε τις εξής εξισώσεις σφαιρών στα χέρια μας:

Για τον εντοπιστμό ενός αντικειμένου στον τρισδιάστατο χώρο θέλουμε τουλάχιστον 4 δορυφόρους, άρα 4 εξισώσεις.

Ενας τρόπος προσέγγισης, για την επίλυση των εξισώσεων είναι να τις αναλύσουμε στις παρακάτω:

Από εκεί, πάρα πολύ εύκολα (μην ρωτάς που είναι το εύκολα, απλά ακολούθα την συλλογιστική) μπορούμε να μετασχηματίσουμε το πρόβλημα σε πίνακες.

$$ AX=B $$

💭 Σύνοψη

Τι μένει λοιπόν για να απαντήσουμε στην αρχική μας ερώτηση;

Να “πετάξουμε” μερικούς δορυφόρους στο διάστημα, να καταφέρουμε να γνωρίζουμε την τοποθεσία τους (ήδη ψάχνουμε και εμείς τη θέση μας, πώς θα ξέρουμε αυτών;), να βρούμε την απόσταση του κινητού τηλεφώνου από κάθε δορυφόρο και, στη συνέχεια, πολύ απλά, να λύσουμε ένα γραμμικό σύστημα πινάκων.

Δεν είναι απλό;

Ίσως και όχι τελικά…

Το όλο πρόβλημα είναι αρκετά σύνθετο.

Και, όπως ήδη αναφέρθηκε, αποτελείται από πολλαπλά μικρότερα προβλήματα.

Για αυτό… Αν δεν κατάλαβες τη λειτουργία, μην αγχώνεσαι. Το συγκεκριμένο άρθρο είναι απλά η εισαγωγή σε ένα σύνολο σχετιζόμενων άρθρων για τον εντοπισμό θέσης αντικειμένων.

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

🔗 Παραπομπές

[1] Christos Spyridakis, “Design and implementation of a low cost embedded system for localization of drones flying in swarms”, Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2022 https://doi.org/10.26233/heallink.tuc.91531 [2] https://el.wikipedia.org/wiki/Global_Positioning_System [3] https://family1st.io/gps-vs-glonass-vs-galileo-whats-the-best-gnss/ [4] M. F. i Azam and M. N. Ayyaz, Location and position estimation in wireless sensor networks, 2016. arXiv: 1611.03420 cs.NI [5] A. Boukerche, H. A. B. F. Oliveira, E. F. Nakamura, and A. A. F. Loureiro, “Localization systems for wireless sensor networks,” IEEE Wireless Communications, vol. 14, no. 6, pp. 6–12, 2007. DOI: 10.1109/MWC.2007.4407221. [6] G. Mao, B. Fidan, and B. D. Anderson, “Wireless sensor network localization techniques,” Computer Networks, vol. 51, no. 10, pp. 2529 – 2553, 2007, issn: 1389-1286. DOI: https://doi.org/10.1016/j.comnet.2006.11.018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1389128606003227. [7] Research on localization algorithms and technologies, Nov. 2015. [Online]. Available: https://www.youtube.com/watch?v=XDFVtYEh0tM (visited on 12/2020) [8] A. Norrdine, An algebraic solution to the multilateration problem, Apr. 2015. doi: 10.13140/RG.2.1.1681.3602. [9] How gps works? trilateration explained, Mar. 2014. [Online]. Available: https://www.youtube.com/watch?v=4O3ZVHVFhes (visited on 12/2020) [10] Trilateration vs triangulation – how gps receivers work, Dec. 2020. [Online]. Available: https://gisgeography.com/trilateration-triangulation-gps/ (visited on 12/2020).