Rui Meireles

Leveraging Diversity and Spatial Connectivity in Multi-hop Vehicular Networks Degree Type: Ph.D. in Computer Science
Advisor(s): Peter Steenkiste, João Barros
Graduated: August 2015

Abstract:

Vehicular Ad-Hoc Networks (VANETs) were created with the goal of increasing traffic safety and efficiency through wireless communication. Due to the vehicles' limited radio range, multi-hop communication is useful to extend coverage. However, it is not an easy proposition. The dynamic topology and spatial heterogeneity that characterize VANETs require a fundamental change from traditional topology-based routing protocols and make it challenging to design a scheme that performs well under all conditions.

In this thesis we focus on the development of specialized vehicular geographic multihop communication protocols that address these challenges. First we tackle topology instability with the Density-Aware Zone-based Limited (DAZL) forwarding protocol. Instead of choosing one relay per hop as is traditional, DAZL species a geographic forwarding zone and has multiple vehicles inside it cooperate in forwarding. We show experimentally that because different vehicles experience different loss patterns, forwarders can cover each other's losses, increasing reliability through node diversity. Moreover, zone nodes coordinate to prioritize the best forwarders and avoid replication.

Second, we propose the Look-Ahead Spatial Protocol (LASP). LASP addresses the issue of spatial heterogeneity by using spatial connectivity information describing the probability of delivery between different geographic areas. Collected vehicular connectivity data exhibited a strong correlation between location and packet delivery ratio, demonstrating that spatial connectivity makes for a good multi-hop heuristic. LASP combines global historical spatial connectivity information with real-time local neighborhood connectivity information to estimate end-to-end delivery probabilities and select, at each hop, the next hop node that maximizes this probability.

Finally we join both ideas in the LASP-MF (Multi-Forwarder) protocol, which combines LASP's spatial-connectivity routing heuristic with DAZL's zone-based forwarding approach in a single protocol. Instead of picking a specific next-hop node, LASP-MF uses spatial connectivity to select a forwarding zone where nodes cooperate in forwarding in a manner similar to DAZL.

To enable a realistic evaluation, we leverage two vehicular testbeds currently deployed in the city of Porto, Portugal, both as sources of data for analysis and a platform for experimentation.

Thesis Committee:
Peter Steenkiste (Co-Chair, CMU)
João Barros (Co-Chair, University of Porto)
Srinivasan Seshan
Ragunathan (Raj) Rajkumar
Mario Gerla (University of California, Los Angeles)
Paulo Ferreira (University of Aveiro)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Vehicular networks, multi-hop, routing, forwarding, diversity, spatial connectivity