Chapter 10

Opportunistic Broadcasts in Vehicular Networks

In this chapter, we apply the concept of opportunistic routing in broadcasts in vehicular networks. Vehicular ad hoc network (VANET) is a special type of mobile MWN designed to provide a wide range of road applications such as safety warning (Torrent-Moreno et al. 2009; Xu et al. 2004), congestion avoidance or mobile infotainment (Li et al. 2011). One important function of VANET is the broadcast of event-driven warning messages (WMs) like accident and hazard warning, for example, after two vehicles collided with each other on a highway, or traffic congestion happens because of heavy rain or snow, the upcoming vehicles need to be notified immediately. In both cases, the WMs should be disseminated with only a short delay to vehicles that are up to several kilometers away, not only to prevent more possible accidents but also to enable the vehicles to make a detour as early as possible to avoid congestion. While Dedicated Short Range Communication (DSRC) (http://www.standards.its.dot.gov/Documents/advisories/dsrcadvisory.htm) allows the data transmission range of vehicles to be up to a few hundred meters, a single-hop broadcast is not sufficient to provide the desired warning message coverage. So a multihop broadcast is necessary to disseminate time-sensitive warning messages in VANETs.

There are three main performance goals in WM broadcast in VANETs. 1. High reliability, which is usually measured as the percentage of vehicles that received the warning message. 2. Fast dissemination–that is the warning messages should be delivered to the vehicles with short end-to-end delay. 3. High scalability, which means the WM's propagation should only incur a small transmission overhead (especially when the network is dense) because unnecessary transmissions waste precious bandwidth resource in VANET. In contrast to the mobile content distribution applications introduced in Chapter 7, we need to ensure a certain QoS requirement for each individual warning message, for example that message reception probability should be larger than a threshold (e.g., 95%), and maximum reception delay should be smaller than 200 ms for a distance within two propagation hops.

However, in real VANETs these goals are hard to achieve simultaneously. The major challenge comes from the lossy wireless transmissions (Torrent-Moreno et al. 28–25 September 2005, 2006), which would undermine the reliability of a one-hop broadcast. According to studies on the DSRC (Torrent-Moreno et al. 2004), the one-hop broadcast reception rate is low due to both channel fading and packet collisions caused by hidden terminals. There is also no channel resource reservation mechanism in 802.11 for broadcasts, which could experience severe packet collisions in a dense network with congested channels. Unlike unicast, in VANET it is difficult to let every vehicle acknowledge the reception of each broadcast message, mainly due to the ACK implosion problem (Tang and Gerla 2000). Therefore, there is hardly a reception guarantee for one-hop link layer broadcast1.

Since enhancing the reliability of a broadcast from the link layer is often highly complex most previous works have focused on broadcast strategies that use redundant network layer retransmissions. The blind flooding leads to the well-known broadcast storm problem (Ni et al. 1999) where packet collisions could arise due to uncoordinated simultaneous rebroadcasts.

Traditionally, connected dominant set-based (CDS-based) algorithms (Dai and Wu 2004; Lim and Kim 2000; Lou and Wu 2002; Qayyum et al. 2002) have been adopted in static multihop wireless networks (MWNs) to solve the broadcast storm problem by pre selecting a minimized set of relay nodes from all the nodes in the network to cover the rest of the nodes. They were developed under the unit disk graph (UDG) model in which a packet can be received if a node is within the transmission range of a relay node, otherwise it will be lost. However, this model does not take into account the characteristics of the lossy wireless medium and its broadcast nature. In the presence of lossy links, the pre-defined relay nodes may not receive a broadcast packet from a relay node in the upstream and the packet could die out from further propagation, thus the broadcast performance will be far from optimal in this case. There are also some works investigating optimized broadcasts in MWNs with unreliable links but they still follow the traditional way of pre-selecting multi point relays (MPRs), which is similar to traditional routing. As we have seen in the previous chapters, opportunistic routing takes advantage of the broadcast nature of the wireless medium and the spacial diversity, which can increase the throughput of routing significantly. Thus, by introducing the concept of opportunistic routing/opportunistic forwarding, the broadcast performance is also expected to improve dramatically.

Most broadcast algorithms in static MWNs are stateful, i.e., they require global or local topology information and need extra overheads for neighbor information exchange. However, VANET is a mobile network with a highly dynamic topology, where the neighbor information is often outdated; and stateful algorithms always incur a large overhead in acquiring neighbor information, which in turn causes performance degradation. Thus, in VANETs, various stateless broadcast schemes were also proposed to mitigate the broadcast storm problem, such as probability-based broadcast schemes (Wisitpongphan et al. December 2007b) and timer-based broadcast schemes (Alshaer and Horlait 2005; Mangharam et al. 2007; Oh et al. 2006; T-Moreno 2007). Although these schemes enjoy high reliability when the channel load is moderate, they do not have a well-coordinated broadcast mechanism, which still makes the amount of redundant transmissions prohibitively large in a dense network or where there is heavy data traffic. This drawback heavily degrades the broadcast performance and limits the scalability to be deployed in a real VANET.

In this chapter, we study the WM broadcast in VANETs, and propose an opportunistic broadcast (OppCast) protocol, a fully distributed protocol that simultaneously achieves high reliability and fast WM propagation while incurring low transmission overheads. OppCast achieves message reception reliability from two aspects: one is the link-layer, and the other is network layer. For the link layer, we propose a distributed opportunistic broadcast coordination function (OBCF), a reliable and efficient MAC-layer broadcast primitive for the recipients of a single broadcast to select the “best” relay nodes in a localized manner. An OBCF exploits the idea of opportunistic forwarding to enhance the reception reliability and reduce the hop delay in each single transmission; by transmitting a long-range, short broadcast acknowledgement (BACK) before each rebroadcast, OBCF effectively minimizes the redundant transmissions and alleviates the hidden terminal problem in a lossy environment.

From the network layer, the broadcast of each WM consists of two types of broadcast phases, where one phase quickly propagates a WM using relatively long hops and the other phase uses additional make-up transmissions between the long hops to ensure a certain PRR. The designs of both phases are optimized to minimize the total number of transmissions.

In addition, we investigate the WM broadcast problem under sparse VANETs with frequent network partitions. To maintain both high WM reception reliability and small end-to-end delay, OppCast switches adaptively between the fast propagation mode and the store-carry-and-forward mode, where the first one is used within continuous vehicle platoons and the second is used between platoons. The optimal switching condition between the two modes is characterized via both theoretical analysis and simulations.

The rest of the chapter is organized as follows. Sections 10.1 and 10.2 review the existing broadcast techniques in multihop wireless networks and VANETs. In Section 10.3 we give the problem statement. This is followed by an overview of the proposed opportunistic broadcast protocol (OppCast) in Section 10.4, and then the main design part is presented in Section 10.5. After that, Section 10.6 presents the theoretical analysis on parameter optimization, and Section 10.7 is the performance evaluation. Section 10.8 wraps up the chapter.