Design and analysis of novel routing protocols for vehicular delay tolerant networks

Abstract

Σε αυτή τη διατριβή προτείνουμε δύο πρωτόκολλα δρομολόγησης για ασύρματα δίκτυα με ανοχή στην καθυστέρηση. Στο πρώτο μέρος της διατριβής παρουσιάζουμε το πρωτόκολλο Delay Tolerant Firework Routing (DTFR), ένα πρωτόκολλο για δίκτυα με ανοχή στην καθυστέρηση, τα οποία αποτελούνται από έναν πολύ μεγάλο αριθμό κόμβων, οι οποίοι έχουν τρόπο να ξέρουν τη θέση τους. Δίκτυα με αυτές τις ιδιότητες υπάρχουν σε πολλές πρακτικές εφαρμογές, για παράδειγμα δίκτυα που αποτελούνται από αυτοκίνητα. Στο DTFR, το πακέτο ταξιδεύει από την πηγή στην τοποθεσία που εκτιμάται ότι βρίσκεται ο προορισμός, δημιουργείται ένας αριθμός αντιγράφων και τα αντίγραφα ταξιδεύουν στη γύρο περιοχή προς όλες τις κατευθύνσεις. Χρησιμοποιώντας προσομοίωση σε ένα σενάριο δικτύου με αυτοκίνητα, συγκρίνουμε το DTFR με δύο βασικά πρωτόκολλα για ασύρματα δίκτυα με ανοχή στην καθυστέρηση, το flooding και το Spray and Wait, δύο πρωτόκολλα που προτάθηκαν πρόσφατα για δίκτυα αυτοκινήτων, το GeoCross και το GeoDTN+Nav, και ένα πρωτόκολλο το οποίο σχεδιάσαμε για να το χρησιμοποιήσουμε σαν άνω φράγμα, το Bethlehem Routing (BR). Επίσης αναπτύσσουμε ανάλυση βασισμένη σε εργαλεία στοχαστικής γεωμετρίας, ένα αριθμό υποθέσεων που απλοποιούν το πρόβλημα, και έναν μικρό αριθμό προσεκτικά επιλεγμένων προσεγγίσεων. Βρίσκουμε εκφράσεις για τον ρυθμό μετάδοσης δεδομένων και για τον χρόνο που χρειάζεται για να παραδοθούν τα πακέτα, στο DTFR και στο BR. Στη συνέχεια διερευνούμε τη χρήση διάφορων κανόνων για να επιλέγουμε τον επόμενο κόμβο που θα πάρει το πακέτο καθώς το πακέτο ταξιδεύει από κόμβο σε κόμβο για να φτάσει στην τοποθεσία του προορισμού του. Αυτοί οι κανόνες λαμβάνουν υπόψη τη θέση και την ταχύτητα του κόμβου που έχει το πακέτο και του κόμβου που είναι υποψήφιος για να πάρει το πακέτο. Βρίσκουμε για αυτούς τους κανόνες την μέση καθυστέρηση και το μέσο κόστος που χρειάζεται για να παραδοθεί ένα πακέτο, με προσομοίωση ή και ανάλυση. Στο δεύτερο μέρος της διατριβής παρουσιάζουμε το πρωτόκολλο Extended Minimum Estimated Expected Delay (EMEED). Αυτό το πρωτόκολλο είναι σχεδιασμένο για δίκτυα με ανοχή στην καθυστέρηση στα οποία οι κόμβοι συναντούν ορισμένους από τους κόμβους του δικτύου πιο συχνά από άλλους. Στο EMEED, κάθε δύο κόμβοι που συναντούνται συχνά, είτε άμεσα είτε μέσω άλλων, μεταδίδουν στο δίκτυο τη μέση τιμή του χρόνου που πρέπει να περιμένουν μέχρι να συναντηθούν. Οι κόμβοι δρομολογούν πακέτα με βάση πίνακες δρομολόγησης που δημιουργούνται χρησιμοποιώντας αυτές τις μέσες τιμές. Όταν η κύρια του παράμετρος, η ακτίνα επαφής, είναι ίση με τη μονάδα, το EMEED λειτουργεί παρόμοια με το γνωστό πρωτόκολλο Minimum Estimated Expected Delay (MEED). Όμως, χρησιμοποιώντας χαρακτηριστικά παραδείγματα και προσομοίωση, δείχνουμε ότι για πολλά σενάρια κίνησης, όταν η ακτίνα επαφής είναι μεγαλύτερη από τη μονάδα, το EMEED είναι καλύτερο από το MEED όσο αφορά τον λόγο του αριθμού των πακέτων που φτάνουν στον προορισμό τους εντός της δοθείσας προθεσμίας προς τον αριθμό των πακέτων που δημιουργούνται, με μια μικρή αύξηση στο εύρος ζώνης που σπαταλείται για να εκπεμφθούν πακέτα ελέγχου. Συγκρίνουμε με προσομοίωση το EMEED με το BUBBLE, ένα πρωτόκολλο που προτάθηκε πρόσφατα για σενάρια στα οποία κάποιοι κόμβοι συναντούν ορισμένους κόμβους του δικτύου πιο συχνά από άλλους. Βρίσκουμε ότι το EMEED έχει συνολικά συγκρίσιμο λόγο αριθμού πακέτων που φτάνουν προς αριθμό πακέτων που δημιουργούνται σε σχέση με το BUBBLE αλλά χρησιμοποιεί λιγότερο εύρος ζώνης για τη λειτουργία του. Επίσης συγκρίνουμε το EMEED με το flooding και το Spray and Wait. Η σύγκριση γίνεται σε δύο σενάρια δικτύων, ένα σχετικό με δίκτυα τσέπης και ανθρώπους που φέρουν μαζί τους τους κόμβους και ένα σχετικό με δίκτυα που αποτελούνται από αυτοκίνητα στο οποίο χρησιμοποιούμε το εργαλείο προσομοίωσης κίνησης SUMO.

In this thesis we propose two routing protocols for wireless mobile Delay Tolerant Networks (DTNs). In the first part of the thesis, we present the Delay Tolerant Firework Routing (DTFR) protocol, a protocol designed for use in DTNs that consist of a very large number of location aware, highly mobile nodes. Networks with these properties appear frequently in many settings, notably in vehicular networks (VANETs). Under DTFR, each data packet travels from the source to the estimated location of the destination using high priority transmissions and a delay tolerant variant of geographic forwarding. Once there, a number of packet replicas are created, and the replicas proceed to travel through the area where the destination is expected to be. Using simulations in an urban setting, we compare DTFR with two baseline protocols (flooding and Spray and Wait), two recently proposed state of the art protocols (GeoCross and GeoDTN+Nav), and an idealistic protocol of our design which we term Bethlehem Routing (BR). For a wide range of environmental parameters, DTFR performs significantly better than other realistic protocols, in terms of throughput and delay, and close to the upper performance bounds of BR. We also develop an analytical framework based on stochastic geometry tools, a number of simplifying assumptions, and a small number of judiciously chosen approximations. Using this framework, we develop approximate closed form expressions for the average end-to-end throughput and delivery delay of DTFR and BR. We then explore the use of different rules for choosing the next hop, as the packet travels toward its target location. These rules take into account the position and velocity of the current holder and candidates for receiving the packet and the position of the target location. We evaluate these rules, by analysis and simulation, in terms of the average packet delay and the average packet cost they incur per unit of progress. In the second part of the thesis, we present the Extended Minimum Estimated Expected Delay (EMEED) protocol which is designed for use in wireless DTNs that consist of a large number of highly mobile nodes with non-uniform correlated mobility patterns. Under the EMEED protocol, any two nodes that are often in contact, either directly or through a multihop path, disseminate in the network the expected time they have to wait until they come into contact. Nodes route packets according to routing tables created using these expected times. When its main parameter, the \textit{contact radius}, is equal to unity, the EMEED protocol operates similarly to the well known Minimum Estimated Expected Delay (MEED) protocol. However, using simulations, we show that for many mobility scenarios, when the contact radius is greater than unity, the EMEED protocol performs far better than MEED, in terms of throughput and delay, with only a modest increase in the control overhead. e compare, using simulations, EMEED with BUBBLE, a state of the art protocol that was also proposed for a scenario where the nodes have preferred locations of movement, and find that EMEED has an overall comparable packet delivery rate but uses the available bandwidth much more judiciously than BUBBLE. We also compare EMEED with flooding and with Spray and Wait. The comparison is made in two mobility scenarios, one related to pocket networks and human levels of mobility, and one related to VANETs, using the SUMO mobility simulation tool.