Performance enhancement on topology-transparent TDMA MAC policies for IoT environments

Abstract

We are living in the age of the Internet of Things, where millions of devices of different characteristics are connected to some kind of network and this number is growing rapidly. Some of these networks consist of nodes characterized by high mobility and in geographical areas where there is no centralized infrastructure to support their operation. Therefore, participating nodes must rely on suitable protocols which will allow them to communicate with each other without relying on centralized coordination. In addition, the applications running on the nodes may be numerous and with diverse, often conflicting, requirements in terms of network performance. In order for the underlying network to be able to support these applications, new medium access control protocols need to be designed and implemented, as existing ones are often unable to satisfactorily meet their requirements. A protocol class that may be suitable for some applications is the class of topology-transparent TDMA protocols which, as their name implies, remain unaffected by topology changes due to node mobility. Their main advantage lies in the fact that when the neighborhood of a particular node changes, there is no need for re-calculation of the set of time-slots in which transmissions are allowed, thus eliminating a major disadvantage of the TDMA protocols, especially when they are implemented in a distributed network environment. However, this advantage comes with the trade-off of allowing packet collisions among the nodes, something that is usually not the case under traditional TDMA protocols. Moreover, another disadvantage of this class of protocols, is their relatively low throughput performance. In this thesis, a study of existing topology-transparent TDMA medium access policies is presented. Subsequently, new policies are proposed which extend the existing ones in order to improve their performance. Initially, the Deterministic Policy, the first topology-transparent TDMA policy ever proposed, is implemented and evaluated in vehicular network scenarios, in order to demonstrate that such policies are indeed suitable to networks where their topology changes rapidly. Comparisons through simulations are conducted with another TDMA policy which has been specifically designed for vehicular networks but follows a more traditional method of allocating time-slots to nodes, i.e. taking into account the time-slots in which neighboring nodes are transmitting and recalculating the corresponding sets in a distributed manner when necessary. Subsequently, two new policies are proposed which extend existing ones and aim to improve on their performance, but each one follows a different approach. The first approach is based on another existing TDMA topology-transparent policy, the Probabilistic Policy, which allows nodes to transmit during all non-assigned time-slots (in addition to their assigned time-slots) but under probability p. In the proposed policy, information from the immediate neighborhood of each node is used in order to identify time-slots during which, if a transmission takes place, it is almost certain that a packet collision will occur. This information is exploited in such way that each node eventually transmits probabilistically only in a subset of its non-assigned time-slots instead of all of them. It is shown that the proposed policy improves throughput when compared to that of the Probabilistic Policy, while at the same time fewer messages have been transmitted in total. The second approach is based on another topology-transparent TDMA policy, the Adaptive Policy, which allows nodes to transmit in any particular non-assigned time-slot with probability p=1, as long as the previous transmission during this slot was successful and until an unsuccessful one occurs. In the proposed policy each node again exploits information from its neighborhood and uses a selected fairness metric as feedback with the purpose of adjusting the transmission probability value in non-assigned time-slots. The decision for this adjustment is based on whether the node feels that has been treated fairly or not, when compared to its neighboring nodes. Finally, an implementation of the Deterministic Policy in a real network consisting of low-cost devices is presented in order to evaluate the potential of applying similar policies in corresponding environments. It is shown that, despite the additional issues introduced by the transmission medium on a low-cost network, the implemented policy performs within the expected specifications.

Ζούμε στην εποχή του Διαδικτύου των Πραγμάτων, όπου εκατομμύρια συσκευές διαφορετικών χαρακτηριστικών συνδέονται σε κάποιο δίκτυο και ο αριθμός αυτός αυξάνεται με γρήγορους ρυθμούς. Μερικά από αυτά τα δίκτυα αποτελούνται από κόμβους που χαρακτηρίζονται από υψηλή κινητικότητα και σε γεωγραφικές περιοχές όπου δεν υπάρχει κεντρική υποδομή για την υποστήριξη της λειτουργίας τους. Επομένως, οι συμμετέχοντες κόμβοι πρέπει να βασίζονται σε κατάλληλα πρωτόκολλα που θα τους επιτρέπουν να επικοινωνούν μεταξύ τους χωρίς να βασίζονται σε κεντρικό συντονισμό. Επιπλέον, οι εφαρμογές που εκτελούνται στους κόμβους μπορεί να είναι πολυάριθμες και με διαφορετικές, συχνά αντικρουόμενες, απαιτήσεις όσον αφορά την απόδοση του δικτύου. Προκειμένου το υποκείμενο δίκτυο να μπορεί να υποστηρίξει αυτές τις εφαρμογές, πρέπει να σχεδιαστούν και να εφαρμοστούν νέα πρωτόκολλα ελέγχου πρόσβασης μέσου, καθώς τα υπάρχοντα συχνά δεν μπορούν να ανταποκριθούν ικανοποιητικά στις απαιτήσεις τους. Μια κλάση πρωτοκόλλων που πιθανώς να είναι κατάλληλη για ορισμένες εφαρμογές είναι η κατηγορία πρωτοκόλλων TDMA διάφανων της τοπολογίας τα οποία, όπως υποδηλώνει το όνομά τους, παραμένουν ανεπηρέαστα από αλλαγές τοπολογίας λόγω της κινητικότητας των κόμβων. Το κύριο πλεονέκτημά τους έγκειται στο γεγονός ότι όταν αλλάζει η γειτονιά ενός συγκεκριμένου κόμβου, δεν υπάρχει ανάγκη για εκ νέου υπολογισμό του συνόλου των χρονοθυρίδων στις οποίες επιτρέπoνται μεταδόσεις, εξαλείφοντας έτσι ένα σημαντικό μειονέκτημα των πρωτοκόλλων TDMA, ειδικά όταν αυτά υλοποιούνται σε κατανεμημένο περιβάλλον δικτύου. Ωστόσο, αυτό το πλεονέκτημα έρχεται με την απαίτηση να επιτρέπονται συγκρούσεις πακέτων μεταξύ των κόμβων, κάτι που συνήθως δεν συμβαίνει στα παραδοσιακά TDMA πρωτόκολλα. Επιπλέον, ένα άλλο μειονέκτημα αυτής της κατηγορίας πρωτοκόλλων, είναι η σχετικά χαμηλή ρυθμαπόδοση. Σε αυτή τη διατριβή, παρουσιάζεται μια μελέτη υφιστάμενων TDMA πολιτικών πρόσβασης μέσου διάφανων της τοπολογίας. Στη συνέχεια προτείνονται νέες πολιτικές που επεκτείνουν τις υπάρχουσες με στόχο τη βελτίωση της απόδοσής τους. Αρχικά, η Ντετερμινιστική Πολιτική, η πρώτη TDMA πολιτική διάφανη της τοπολογίας που προτάθηκε, εφαρμόζεται και αξιολογείται σε σενάρια δικτύων οχημάτων, προκειμένου να δειχθεί ότι τέτοιες πολιτικές είναι πράγματι κατάλληλες για δίκτυα όπου η τοπολογία τους αλλάζει με γρήγορους ρυθμούς. Πραγματοποιούνται συγκρίσεις μέσω προσομοιώσεων με μια άλλη πολιτική TDMA που έχει σχεδιαστεί ειδικά για δίκτυα οχημάτων, αλλά ακολουθεί μια πιο παραδοσιακή μέθοδο κατανομής χρονοθυρίδων σε κόμβους, δηλαδή λαμβάνοντας υπόψη τις χρονοθυρίδες στις οποίες εκπέμπουν οι γειτονικοί κόμβοι και επανυπολογίζοντας τα αντίστοιχα σύνολα με κατανεμημένο τρόπο όταν είναι απαραίτητο. Στη συνέχεια, προτείνονται δύο νέες πολιτικές που επεκτείνουν τις υπάρχουσες και στοχεύουν στη βελτίωση της απόδοσής τους, αλλά η καθεμία ακολουθεί διαφορετική προσέγγιση. Η πρώτη προσέγγιση βασίζεται σε μια άλλη υπάρχουσα πολιτική TDMA διάφανη της τοπολογίας, την Πιθανοτική Πολιτική, η οποία επιτρέπει στους κόμβους να εκπέμπουν κατά τη διάρκεια όλων των μη ανατεθειμένων χρονικών θυρίδων (επιπλέον των χρονοθυρίδων που τους έχουν ανατεθεί) αλλά με πιθανότητα p. Στην προτεινόμενη πολιτική, οι πληροφορίες από την άμεση γειτονιά κάθε κόμβου χρησιμοποιούνται για τον εντοπισμό χρονοθυρίδων κατά τις οποίες, εάν λάβει χώρα μια μετάδοση, είναι σχεδόν βέβαιο ότι θα προκύψει σύγκρουση πακέτων. Αυτή η πληροφορία αξιοποιείται με τέτοιο τρόπο ώστε κάθε κόμβος να εκπέμπει τελικά με πιθανότητα μόνο σε ένα υποσύνολο των μη ανατεθειμένων χρονοθυρίδων αντί για όλες. Δείχνεται ότι η προτεινόμενη πολιτική παρουσιάζει βελτιώμένη απόδοση σε σύγκριση με αυτή της Πιθανοτικής Πολιτικής, ενώ ταυτόχρονα μεταδίδει λιγότερα μηνύματα συνολικά. Η δεύτερη προσέγγιση βασίζεται σε μια άλλη πολιτική TDMA διάφανη της τοπολογίας, την Προσαρμοστική Πολιτική, η οποία επιτρέπει στους κόμβους να μεταδίδουν σε οποιοδήποτε συγκεκριμένη μη ανατεθειμένη χρονοθυρίδα με πιθανότητα p=1, εφόσον η προηγούμενη μετάδοση κατά τη διάρκεια αυτής της χρονοθυρίδας ήταν επιτυχής και μέχρι να προκύψει κάποια αποτυχημένη. Στην προτεινόμενη πολιτική, κάθε κόμβος εκμεταλλεύεται ξανά πληροφορίες από τη γειτονιά του και χρησιμοποιεί μια επιλεγμένη μετρική δίκαιης μεταχείρισης ως ανατροφοδότηση με σκοπό την προσαρμογή της τιμής πιθανότητας μετάδοσης σε μη ανατεθειμένες χρονοθυρίδες. Η απόφαση για αυτήν την προσαρμογή βασίζεται στο κατά πόσο ο κόμβος αισθάνεται ότι έχει αντιμετωπιστεί δίκαια ή όχι, σε σύγκριση με τους γειτονικούς του κόμβους. Τέλος, παρουσιάζεται μια εφαρμογή της Ντετερμινιστικής Πολιτικής σε ένα πραγματικό δίκτυο που αποτελείται από συσκευές χαμηλού κόστους προκειμένου να αξιολογηθεί η δυνατότητα εφαρμογής παρόμοιων πολιτικών σε αντίστοιχα περιβάλλοντα. Παρουσιάζεται ότι, παρά τα πρόσθετα προβλήματα που εισάγονται από το μέσο μετάδοσης σε ένα δίκτυο χαμηλού κόστους, η εφαρμοζόμενη πολιτική λειτουργεί εντός των αναμενόμενων προδιαγραφών.