## 2 Related Work  
Routing packets in a vehicular ad hoc network is a task that can be formalized as routing in an undirected graph, in which graph nodes are stations, and edges are virtual communication links between two stations. In static ad hoc networks, network architectures are defined by minimizing the number of nodes relaying application data traffic. One approach consists of computing a network backbone, a minimal set of nodes and links required to enable communications between any couple of nodes in the network. In graph theory, two problems are analogous: the identification of a spanning tree [16] and that of a connected dominating set (CDS) [17]. In mobile ad hoc networks (MANETs), network protocols need to dynamically update changes in the network topology in a distributed manner [18], with each wireless station having its own local view of the rest of the network. In a centralized approach, network changes need to be propagated toward a central node, which compute routing tables and send them back to every node. However, this could quickly become impossible due to the network splitting resulting from link failures, notably because of nodes becoming too far from each other to exchange information. In a perfect environment with no time constraints, in which all nodes are static and able to transmit all packets without any failure, the optimal CDS structure could be an efficient and viable centralized solution. However, the mobility observed in VANETs causes links to be short-lived, thus leading the network graph to be highly dynamic. The lack of redundancy of the minimal CDS structure can create bottlenecks at crossing nodes, which cannot be circumvented to forward packets throughout the network. Such crossing nodes then become points of failure when node mobility creates the risk of link failure. Both the time-critical and time-constrained communications usually encountered in VANETs have a maximum validity period beyond which the shared information is stale. If a path to a node is lost, the route must be recomputed, resulting in transmission delays. In multihop communications, such delays can happen at every node relaying packets, adding up to and exceeding the applications' time requirements. One solution to improve network resiliency is structural redundancy: multiple (joined or disjoined) paths exist to reach the destination, thus mitigating the impact of one link's failure on the delivery of the transmitted packets. Concerning the OLSR protocol [15], a global CDS is computed in a decentralized way, with every node computing a dominating set (DS) to cover its two-hop neighborhood. By means of periodical HELLO messages (i.e., beacons) broadcast and received, any node running OLSR can be sensed by its one-hop neighbors and discover them. Each HELLO message contains the IP identifier of its source node and the link state to the one-hop neighbors it has detected, thus enabling any receiving node to update its local perception of both its one-hop neighbors and the two-hop neighbors that it can reach through the HELLO originator (Figure 1a). After updating its table of one- and two-hop neighbors, an OLSR node then computes an optimal set of its one-hop neighbors, which are called multipoint relays (Figure 1b), so as to cover all of its two-hop neighbors. Next, every MPR node broadcasts, throughout the network, information about its links with the nodes that selected it (its selectors) through a topology control (TC) message. In order to optimize the flooding of such broadcast messages, the OLSR protocol only allows MPR nodes to forward TC messages, which reduces control packet overhead compared to blind flooding. By using only the links between MPR nodes and their selectors for packet routing, OLSR creates a mesh network, which is actually a CDS composed of all MPR nodes in the VANET (Figure 1c). Each node can select multiple MPRs and be selected as the MPR by several other nodes, thus leading to the accumulation of MPR coverage areas and the availability of multiple paths.