$k$-Connectivity Analysis of One-Dimensional Linear VANETs

In a 1-D linear vehicular ad hoc network (1-DL-VANET), some vehicles may leave the network (e.g., at highway exits), which may make the 1-DL-VANET disconnected. Thus, it is important to analyze the connectivity of the 1-DL-VANET. When removal of any (k - 1) arbitrary nodes from a network does not disconnect the network, the network is said to be k-connected. In this paper, we investigate the k-connectivity of the 1-DL-VANET. Sufficient and necessary conditions are derived for the 1-DL-VANET to be k-connected, and based on this, a method is provided, with the help of matrix decomposition, to obtain expression of the probability of the 1-DL-VANET being k-connected. The expectation of the maximum number of tolerable vehicle departures is also derived. Simulation results confirm the accuracy of our analysis and indicate that the expectation of the maximum number of tolerable vehicle departures almost linearly increases with the total number of vehicles.

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].