Contents I. Introduction
A vehicular ad hoc network (VANET) consists of a group of moving vehicles and probably a fixed infrastructure (such as roadside units), supporting intervehicle communications, and vehicle-to-infrastructure communications. Typical information transmitted in a VANET includes safety messages (such as accident notifications, road condition warnings, and emergency braking alarms) and interactive communications (such as instant message and online games). In this work, we consider intervehicle communications among a group of vehicles on a highway. Considering that the road width of highways is usually much smaller than the wireless transmission range and that the curves on highways are usually not sharp, we can approximately model the group of vehicles as a 1-D linear VANET (1-DL-VANET). A similar model is adopted in [1] and [2]. Here, we consider only intervehicle communications, and thus, roadside units are not involved. In a 1-DL-VANET, some vehicles may leave or quit the current network, e.g., due to arriving at their exits on the highway or due to mechanical faults. Upon departures of those vehicles, it is desired that any two remaining vehicles can still communicate with each other. In other words, the high connectivity level of the 1-DL-VANET is desired. In specific, if there exists a one- or multiple-hop communication path between any two nodes in a network, the network is said to be connected; otherwise, the network is said to be unconnected or disconnected. A network is called -connected if removal of any arbitrary nodes does not disconnect the network [3]. In particular, biconnectivity means that , which is a popular connectivity measure [4]–[8].
