Information dissemination in vehicular ad hoc networks

Abstract

Τα μη δομημένα οδικά δίκτυα (VANETs) αξιοποιούν τις δυνατότητες της τεχνολογίας πληροφορικής και επικοινωνιών για τη δημιουργία ενός ασφαλέστερου και πιο αποδοτικού δικτύου μεταφορών. Πολλές από τις εφαρμογές των VANETs δημιουργούν απαιτήσεις για διάδοση των πληροφοριών που είναι διαφορετικές από τα συμβατικά ΜΑΝΕΤs και, ως εκ τούτου, είναι δύσκολο να εκπληρωθούν με τις υπάρχουσες στρατηγικές. Οι εφαρμογές ασφαλείας θέτουν αυστηρές απαιτήσεις καθυστέρησης στην παράδοση των μηνυμάτων έκτακτης ανάγκης σε γεωγραφικές περιοχές όπου τα δεδομένα πρέπει να συλλέγονται, να διανέμονται και να συντηρούνται. Οι προκλήσεις του σχεδιασμού λύσεων περιλαμβάνουν τη μεταβλητή πυκνότητα των οχημάτων, την υψηλή κινητικότητα τους και την περιοριζόμενη, αλλά συχνά απρόβλεπτη, κίνησή τους. Στην παρούσα διατριβή αντιμετωπίζουμε το πρόβλημα της διάδοσης πληροφοριών σε VANETs με ιδιαίτερο ενδιαφέρον στο πλάνεμα (hover), στη δρομολόγηση και στη μετάδοση πληροφορίας και προτείνουμε νέες μεθόδους που ικανοποιούν τις διάφορες προκλήσεις. Προτείνουμε μια προσαρμοστική μέθοδο πλανέματος της πληροφορίας, η οποία βασίζεται στην εφαρμογή της επιδημικής διάχυσης εντός της περιοχής πλανέματος και πιθανοτικής διάχυσης έξω από αυτή. Χαρακτηριστικό της προτεινόμενης λύσης είναι ότι η πιθανότητα διάχυσης έξω από την περιοχή είναι προσαρμοστική βάσει της πυκνότητας των οχημάτων εντός της περιοχής πλανέματος. Η προτεινόμενη λύση έχει πολύ καλές ιδιότητες ευρωστίας, καθώς δε βασίζεται σε στατική υποδομή και επιτυγχάνει τους στόχους της, λόγω της υψηλής προσβασιμότητας που δεν υπερφορτώνει τους διαθέσιμους πόρους. Οι μέθοδοι που χρησιμοποιούνται στη λύση είναι ελκυστικές, δεδομένου ότι οδηγούν σε πρωτόκολλα με καθολικές ιδιότητες, τα οποία μπορούν να χρησιμοποιηθούν ως αποτελεσματικές λύσεις σε διάφορους άλλους τομείς εκτός του τομέα του οδικού δικτύου. Στη διατριβή αυτή έχουμε ενσωματώσει την προτεινόμενη λύση σε ένα σύστημα Αναμετάδοσης Δεδομένων με ένα διακομιστή Push, ως μέσο αποφόρτισης του διακομιστή, το οποίο βελτιώνει σημαντικά τις μετρικές απόδοσης. Επίσης, καταπιανόμαστε με το πρόβλημα της δρομολόγησης της πληροφορίας σε VANETs. Η πλειοψηφία των μηνυμάτων που ανταλλάσσονται από οχήματα χαρακτηρίζονται από μια πεπερασμένη χρονική διάρκεια ζωής, με τη λήξη της οποίας το επίπεδο χρησιμότητάς τους μειώνεται σημαντικά. Έτσι, είναι απαραίτητο να έχουμε αποτελεσματικές πολιτικές δρομολόγησης που να εξασφαλίζουν την παράδοση πληροφοριών σε στόχους πριν τη λήξη της προθεσμίας. Στην εργασία αυτή μελετάμε το πρόβλημα με βάση την πιθανότητα παράδοσης μηνυμάτων χρησιμοποιώντας θεωρεία γράφων. Έχουμε διαμορφώσει τον οδικό χάρτη και τα χαρακτηριστικά της κυκλοφορίας χρησιμοποιώντας ένα σταθμισμένο κατευθυνόμενο γράφημα που το ονομάζουμε Road-Graph. Χρησιμοποιούμε το Road-Graph για να υπολογίσουμε την πιθανότητα διάδοσης των πληροφοριών κατά μήκος μιας διαδρομής, σε ένα συγκεκριμένο χρονικό διάστημα. Έτσι, για κάθε δύο σημεία στο Road-Graph μπορούμε να βρούμε τη διαδρομή με τη μέγιστη πιθανότητα επιτυχούς παράδοσης της πληροφορίας κατά το επιλεγμένο χρονικό διάστημα. Αυτή η πληροφορία είναι πολύ σημαντική δεδομένου ότι μπορεί να χρησιμοποιηθεί από τα πρωτόκολλα δρομολόγησης για τη βέλτιστη δρομολόγηση πακέτων στο οδικό δίκτυο. Η δημιουργία του Road-Graph απαιτεί τον υπολογισμό της πιθανότητας μετάδοσης πληροφοριών μεταξύ των δύο διασταυρούμενων δρόμων. Δείχνουμε ότι η πιθανότητα μετάδοσης της πληροφορίας είναι στενά συνδεδεμένη με τις κυκλοφοριακές συνθήκες του δρόμου που θέλουμε να στείλουμε την πληροφορία. Χρησιμοποιώντας την μαθηματική ανάλυση μπορούμε να βρούμε τις ελάχιστες προϋποθέσεις που απαιτούνται για να εξασφαλιστεί, με υψηλή πιθανότητα, η διάδοση της πληροφορίας στις διασταυρώσεις.

VANETs harness the potential of information and communication technologies to create a safer and more efficient transportation network. Many applications of VANETs set up requirements for information dissemination that are different from conventional networks and, thus, difficult to fulfill with existing strategies. Safety applications pose stringent delay requirements on emergency message delivery and address geographical areas in which data needs to be cooperatively collected, distributed and maintained. Design challenges are then posed by the variable density, the high mobility and the confined but often unpredictable movement of vehicles. In this thesis we address the information dissemination problem in VANETs with particular interest in information hovering, routing and broadcast, and we propose new methods, which overcome the design challenges. We propose an adaptive information hovering scheme based on the application of epidemic routing within the hovering area and probabilistic flooding outside the area. A unique feature of the proposed protocol is that it is adaptive in the sense that the rebroadcast probability outside the hovering area is adaptively regulated based on vehicle density within the hovering area. The designed protocol is amenable for gradual deployment and has good robustness properties, as it does not rely on static infrastructure. The protocol reaches its design objectives as it achieves high reachability without overloading the available resources. The methods used are attractive, as they lead to protocols with universal properties that they can be utilized as effective solutions in areas beyond the vehicular technology area considered so far. We integrate the derived information hovering protocol in a Data Broadcasting system with a Push Server, as a means of data dissemination off-loading that significantly improves performance. We also address the information routing problem in VANETs. The majority of messages exchanged by vehicles are characterized by a finite lifetime period, after which their level of usefulness is greatly reduced. Thus, it is important to pursue efficient routing policies, which can ensure information delivery in target areas before this deadline expires. In this thesis we study the problem based on the probability to deliver messages using a graph theoretical approach. We model the road map and the traffic characteristics using a directed weighted graph, which we refer to as the Road-Graph. We use the Road-Graph to calculate the probability of disseminating information along a path, in a specific amount of time. So, for any two points on the Road-Graph we can find the path with the maximum probability of successful information delivery in the chosen time interval. This information is of great significance, since it can be utilized by routing protocols to optimally route packets in the vehicular network. The creation of the Road - Graph requires the calculation of the probability of information propagation between two intersecting roads. We show that the propagation probability is strongly related to the traffic conditions of the road where the information is to be transmitted. We use the derived formula to estimate the minimal conditions required to ensure that information propagation occurs with high probability on intersections.