UC Berkeley

The development of intelligent transportation systems is one of the most important strategies for making roads safer and more efficient. The key technology underpinning all such systems, from cooperative safety systems to electronic tolling, is wireless communications. Vehicles must be able to communicate with each other, and with fixed infrastructure, in real time. One promising architecture involves forming an ad hoc network among the vehicles and taking advantage of the peer-to-peer connectivity to reduce infrastructure costs.

In this dissertation, we consider the design and analysis of medium access control and network layer protocols for vehicular ad hoc networks. In particular, we examine the problem of distributing content over many hops from a source to a destination. The fundamental challenge in such systems is the inability of the vehicles to coordinate with each other. Because of the high frequency at which vehicles enter and exit the road, and the fact that vehicles may be moving at widely varying speeds, the topology is continuously changing. Therefore, centralized scheduling of transmissions to avoid collisions and global routing of packets is either technically infeasible or prohibitively expensive. We propose instead a class of uncoordinated protocols, based on randomized channel access and network coding. The key idea behind the coding is for the vehicles to transmit random combinations of all the packets that they have received, instead of simply forwarding packets. This scheme does not require link level feedback, and thus vehicles do not need to track the identities of their current neighbors.

We first consider a minimally coordinated protocol, where the vehicles on a road are partitioned into spatial blocks. The block structure is used to funnel waves of data down the road, while the vehicles within each block randomly contend with each other for the channel. We show that when the vehicles use network coding in this scheme, the end-to-end throughput is constant, as long as the number of blocks in the network does not grow exponentially in the vehicle density. Network coding allows for the reliable transport of data over many hops at the same rate at which data could be sent over a single hop.

Then we consider a completely uncoordinated protocol, which does not even require the assignment of vehicles to spatial blocks. We begin by providing a general algorithm for computing the throughput of an arbitrary network using such a protocol. The main technical contribution is to account for the fact that intermediate nodes may temporarily not have any new packets to transmit to their neighbors, due to the random channel access. We prove that the throughput of this wireless network is equal to the throughput of an equivalent wired network, despite the randomized medium access strategy. This result has application in a variety of other contexts, where it is often assumed for tractability that relays always have data when they use the channel.

We then apply this result to the problem of finding the throughput in an uncoordinated vehicular ad hoc network. In a congested highway, where the connectivity graph is homogeneous, a constant throughput can be provided to receivers that are located at an arbitrary distance from the source. In essence, every vehicle can be thought of as a digital repeater, despite the packet losses due to collisions.