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

Abstract

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 ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> - 1) arbitrary nodes from a network does not disconnect the network, the network is said to be <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> -connected. In this paper, we investigate the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> -connectivity of the 1-DL-VANET. Sufficient and necessary conditions are derived for the 1-DL-VANET to be <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> -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 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> -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.