Evolution of Vehicle Network on a Highway
Gleb Dubosarskii Serguei Primak Xianbin Wang







IEEE Transactions on Vehicular Technology, Vol. XX, No. XX, XXX 2015









Evolution of Vehicle Network on a Highway
    
Gleb Dubosarskii, Student Member, IEEE, Serguei Primak, Member, IEEE,
 Xianbin Wang, Fellow, IEEE
G. Dubosarskii, S. Primak and X. Wang are with the Department of Electrical and Computer Engineering, Western University,
	London, Ontario, Canada, N6A 5B9 (e-mail: gdubosar@uwo.ca; slprimak@uwo.ca; ).
Manuscript received November 30, 2018; revised April 1, 2019.
    December 30, 2023
==============================================================================================================================================================================================================================================================================================================================================================================





One of the challenges related to the investigation of vehicular networks is associated with predicting a network state regarding both short-term and long-term network evolutionary changes. This paper analyzes a case in which vehicles are located on a straight road, and the connectivity state between two consecutive cars is determined by the Markov chain model with two states. The transition probabilities of the considered model are explicitly expressed in terms of known parameters of the network using the Wang-Moayery model. Within the presented model, the network evolution is described in terms of determinative parameters, such as average link duration, average cluster lifetime, and a clusters’ existence probability between two fixed moments of time. In support of the theoretically obtained probabilistic distributions, the results of numerical simulations are provided.




Vehicular network, clustering, network evolution, link duration.













§ INTRODUCTION

Vehicular Adhoc Networks (VANETs) have become one of the frontier topics  of research <cit.>–<cit.> over the last decade due to the anticipated mass deployment of self-driving vehicles. A VANET consists of a set of fast moving vehicles equipped with sensing,   communication and infotainment systems. This turns  the neighboring connected vehicles into a moving wireless network, that enables vehicles to connect with each other and share safety and entertainment related content. Self-driving vehicles are expected to significantly reduce the number of road accidents and traffic congestion, improve road safety, and further enable intelligent transportation.

Vehicle networking is a relatively new field that allows for the application of emerging technologies such as machine learning, which is widely used in many areas from image processing to financial data analysis. Based on extensive statistics, a neural network is capable of predicting and classifying data, and therefore, it is a powerful tool for solving a variety of different problems.  Machine learning techniques have applications in optimization of information transmission between vehicles <cit.>, <cit.>, improving transportation safety <cit.>, and reducing transmission delays <cit.>. The applications of machine learning in the aforementioned areas, as well as for network congestion control, wireless resource management, and load balancing are discussed in a comprehensive survey <cit.>. It includes not only classical deep learning algorithms used for the system’s state prediction from available data, but also modern developments in the field of reinforcement learning, that makes it possible to find strategies leading to long-term rewards in the cases, where a problem can be reformulated as a game. Reinforcement learning algorithms demonstrate their superiority in comparison to the previous approaches in resource management and resource allocation tasks, and allow for a reduction in computational complexity.

In recent years, significant progress has been made in the area of MAC protocols for vehicular networks <cit.>–<cit.>. Due to the dynamic topology of the network, the development of robust and efficient transmission of information in Vehicle-to-Vehicle (V2V), and Vehicle-to-RSU (V2R) scenarios becomes highly significant. One important issue here is avoiding collisions where more than one node transmits at the same time interval, because resending the same packages causes delays, which is not acceptable for delay-sensitive applications. For overcoming the problem, near collision free MAC protocols adapting to different densities of traffic flow have been proposed.

MAC protocols are intrinsically complicated, which makes them almost impossible to analyze analytically from a statistical point of view. For practical applications, it is important to estimate the average cluster size of the network and probability of multihop connectivity between two vehicles. To address these challenges, in the case of a straight road (see articles <cit.>–<cit.>), simplified models are proposed, making it possible to derive explicit expressions for the aforementioned fundamental network characteristics, and the probability of full connectivity. In <cit.>, the authors consider a more complicated case, where vehicle networks are moving along two perpendicular roads towards the intersection. They derive formulas for the outage probability and the transmission probability, assuming that intervehicle distance has Poisson distribution.

However, these studies are limited to a current moment, while it is important to investigate how connectivity changes over time. In particular, it is important to know what the average link duration is. In the articles <cit.> and <cit.>, the explicit formulas for the link duration are obtained under different assumptions. In <cit.>, the average link duration is investigated assuming a two-way road, and that vehicles only transmit messages to other vehicles moving in the opposite direction. In <cit.>, the average link duration is calculated in the case of one-way traffic under the assumption that speed increases linearly until it reaches the speed limit and then remains constant.

Network evolution is a stochastic process. Therefore, we can predict the state of the system for the next moment of time only with certain probability. It explains the application of the probability theory to the analysis of network evolution. The channel interruption probability is small, but positive, leading to an increase in the probability of disconnection over time. This article is aimed at describing the evolution of the network in terms of the probability of maintaining a connection between two consecutive vehicles and the vehicles forming a cluster, and investigating how rapidly the probability decreases. We derive explicit expressions for the probabilities of link duration, cluster existence over a certain amount of time, and the  probability of cluster existence between two fixed moments of time. The obtained results related to cluster evolution are new, and they provide an insight into dynamical changes in the network.


It is convenient to investigate the connectivity properties of the system not at every moment, but only on a discrete uniform time mesh. It means that the difference between two consecutive moments of time has a fixed duration Δ t. Let t be the current moment of time. The Markov model determines the probability of an event that at the moment of time t+Δ t, the consecutive vehicles could establish a connection based on the communication state at the time moment t. This probability is explicitly expressed in terms of macro parameters of the system <cit.>, <cit.>. Using the state-transition matrix of the Markov process, it is possible to express the desired connection probabilities in terms of the matrix coefficients, and thereby, allows the calculation of the required connectivity characteristics.


Also, we consider such a stability characteristic of the connection between two consecutive cars as ω-stable connection. This type of connection guarantees that the time between consecutive connections does not exceed ωΔ t (Δ t is a timestep). In other words, this weakened condition means that at some moments of time the vehicles may fail to establish a connection, but they connect at least once at each time interval that has length  ωΔ t. This type of communication is closer to the actual operating conditions, where connection may disappear  for short periods of time, but it is important to ensure that it is regularly reestablished. We derive recurrent equations for calculating the probabilities and verify the results using simulations.


The article is organized as follows. Section <ref> describes the parameters and the structure of a considered network model. Section <ref> investigates the statistics of node-to-node connectivity between cars assuming a fading channel between the nodes.The detailed mathematical derivations are summarized in Section <ref>, and a brief summary is given in <ref>. The derived expressions are verified through a number of simulations in Sections <ref>, <ref>.




§ NETWORK MODEL

We consider the following probabilistic model that describes the evolution of the network over time.
It is assumed that there are two states of connection Good and Bad.
In the Good state, neighboring cars can establish a connection, while the Bad state corresponds to the case where neighboring cars cannot connect with each other.
We suppose that initially the system is in the equilibrium state; the initial probabilities of connection are calculated in the section V.
We consider the system evolution process with timestep Δ t (introduced at the end of the previous section).
Let p be the probability that connected neighbouring cars cannot establish a connection at the next moment of time, in other words, p is the probability that at the next moment of time the system moves from the Good state to the Bad state.
By analogy, let q be the probability that at the next moment the system moves from the Bad state to the Good state. Therefore, connectivity between two consecutive cars can be described by two-state Markov Model depicted below (letters G and B denote the Good and the Bad states, respectively). The explicit values of the parameters p and q are given in the next section.



	
    < g r a p h i c s >


	Fig 1. Markov diagram of the connectivity process
 with the Good and the Bad states






§ PROBABILISTIC CONNECTIVITY MODEL


Everywhere in the article it is assumed that all n vehicles move along one-way road with the same constant speed v.
Each car can establish a connection only with the closest front and back neighbours.
We assume a Rayleigh fading channel between every pair of cars. Consequently, the amplitude of the received signal is exponentially distributed with pdf

    p(x)=1/λe^-x/λ,

where λ represents the average SNR (Signal-to-noise ratio) over the fading channel. We use the Wang-Moayery model <cit.> to determine values of the parameters p and q. According to this model, we determine state of the system by comparison signal amplitude A and threshold A. If A≥A then we assume, that the system is in the Good state, otherwise it is in the Bad state. We denote by p_B the probability of the Bad case, therefore,

    p_B=∫_0^A p(x)dx = ∫_0^A1/λe^-x/λdx=1-e^-A/λ.


The probability of the Good state is given by the formula

    p_G=1-p_B=e^-A/λ.

Assuming the Clark model, the following formula for the level crossing rate is obtained in <cit.>:

    LCR(x)=√(2π x/λ)f_De^-x/λ,

where f_D is Doppler shift. Also, the following two explicit formulas for parameters p and q (they are introduced in the previous section) are derived

    p=LCR(A)/Rp_G=√(2πA/λ)f_D/R,


    q=LCR(A)/Rp_B=√(2πA/λ)f_De^-A/λ/R(1-e^-A/λ),

where R is the symbol rate.
Taking into account (<ref>), (<ref>), and the following formula for the maximum Doppler shift [Maximum Doppler shift is consistent with geometry of the problem, since vehicles follow the signal propagation path.]:

    f_D=vf_c/c,

where f_c and c are transmitted frequency and velocity of light respectively, we obtain

    p=LCR(A)/Rp_G=√(2πA/λ)vf_c/Rc,


    q=LCR(A)/Rp_B=√(2πA/λ)vf_ce^-A/λ/R c(1-e^-A/λ).

The timestep Δ t (see description of timestep in the section <ref>) satisfies Nyquist-–Shannon criterion

    Δ t≤1/2f_D.




§ MAIN RESULTS


Let p_G(m) be the probability that at the moment mΔ t two fixed consecutive cars can establish a connection.
We assume that the system is initially in the equilibrium state (for more details see section V).
In the above mentioned section, the probability p_G(m) of a successful connection between two consecutive cars at the moment of time mΔ t satisfies the following formula:

    p_G(m)=q/p+q,

where parameters p and q are calculated by the formulas (<ref>) and (<ref>). Thus, probability p_G(m) does not depend on m, and, therefore, we denote it by p_G.










Let symbol P_twocars(m) stand for
the probability that connection between two cars once established has duration mΔ t.
The probability P_twocars(m) is given by the formula

    P_twocars(m)=(1-p)^m-1p.








The average link duration T_twocars and its variance σ_twocars^2 of the distribution (<ref>) are determined by the formulas

    T_twocars=Δ t/p,



    σ_twocars^2=(1-p)Δ t^2/p^2.







Definition.  A cluster is a such group of vehicles that any two cars in the group can communicate with each other, probably through other vehicles of the cluster.

In our model, each vehicle connects only to the closest forward and backward cars.
Therefore, in the framework of our model, clusters are formed by several consecutive cars.
On Fig. 2 below, five cars are depicted that form two clusters. The first cluster is formed by cars 1, 2, 3 and the second cluster is composed of cars 4 and 5.
Significantly, cars 1 and 3 cannot communicate directly, and the only communication way for them is through car 2,
while vehicles 3 and 4 are disconnected. We prove that the connectivity probability is given by the formula p/(p+q). Therefore, connectivity state between two consecutive vehicles depends on the parameters listed in the section <ref>. It is worth mentioning that this probability is close to 1 (stable connection) if p≈ 1 and q ≈ 0.



We derive the probability P_clust(m) that the cluster formed by the cars k,k+1,…,k+s once being formed exists exactly time mΔ t. Let us introduce parameter γ by the formula

    γ=
    2,     1<kk+s<n, 
    
    1,     k=1k+s=n,
    
    0,     k=1k+s=n.

The probability P_clust(m) satisfies the formula

    P_clust(m)= (1-p)^s(m-1)(1-q)^γ(m-1) (1-(1-p)^s(1-q)^γ).




	
    < g r a p h i c s >


	Fig 2. Network of 5 cars that form two clusters.










The average existence cluster lifetime T_clust and variance σ_clust^2 of the distribution (<ref>) can be obtained by the formulas

    T_clust=Δ t/1-(1-p)^s(1-q)^γ.


    σ_clust^2 =
    (1-q)^γ(1-p)^sΔ t^2/(1-(1-q)^γ(1-p)^s)^2,

where γ is determined in (<ref>).






We study not only the duration of a cluster lifetime, but also the probability that cluster does exist between two given moments of time. More precisely, we derive the following formula for the probability P_clust(m,l) that the cluster that consists of cars k,k+1,…,k+s is formed at the moment of time mΔ t, exists until lΔ t (l ≥ m), and does not exist at the moment (l+1)Δ t as follows:

    P_clust(m,l)={p_G^s(1-p_G)^γ. 
    -(1-p)^s p_G^s(1-p_G)^γ(1-q)^γ.}
    ×(1-p)^s(l-m)(1-q)^γ(l-m){1-(1-p)^s(1-q)^γ},

where p_G and γ are given by the formulas (<ref>) and (<ref>).










Finally, we analyse the property of ω-stability of a connection
that is defined as the ability of two vehicles to establish connection within every time interval ωΔ t.
More formally, we assume that connection is ω-stable between moments mΔ t and lΔ t,
if there is at least one successful connection not later that the moment (m+ω)Δ t, time difference between every two consecutive connections does not exceed ωΔ t and the last connection is established at the moment (l-ω)Δ t or later.
At the end of the section V, we derive the algorithm for  finding the  probability that the connection between two cars is ω-stable on a pre-selected interval.
The algorithm has linear complexity and recurrently calculates the probability under the assumption of known parameters p and q.



§ MATHEMATICAL DERIVATIONS




 §.§ Probability of two cars being connected at the moment mΔ t


Let p_G(m) be the probability that there is a connection between predetermined consecutive cars at the moment of time mΔ t and by p_B(m) the probability that there is no connection at mΔ t.
Let us find the limiting distributions p_G(∞)=lim_m→∞p_G(m) and p_B(∞)=lim_m→∞p_B(m).
According to the Markov model (see Fig. 1), we have

    p_G(m) = p_G(m-1)(1-p) + p_B(m-1)q,


    p_G(m) + p_B(m) = 1.

When m →∞, the equations (<ref>) and (<ref>) take the following form

    p_G(∞) = p_G(∞)(1-p)+p_B(∞)q,


    p_G(∞) + p_B(∞)=1.

Solving system of linear equations (<ref>) and (<ref>), we obtain

    p_G(∞)=q/p+q,


    p_B(∞)=p/p+q.



We assume that at the moment when we observe the system, it has reached its limiting distribution, therefore,  the probabilities at every moment mΔ t are equal to the limiting probabilities:











    p_G(m)=q/p+q,


    p_B(m)=p/p+q.

Thus, we denote them p_G and p_B.




















































 §.§ Distribution of link duration


Let us consider two consecutive cars.
We find the probability P_twocars(m) of the event that the connection lifetime between these cars is exactly mΔ t.
In other words, if the connection between cars is firstly established at the moment of time Δ t, we calculate the probability that the cars keep the connection up to the time instant mΔ t, and at the time (m+1)Δ t the connection cannot be established.
This probability is given by the formula

    P_twocars(m)=(1-p)^m-1p,

since at the time Δ t the system is in the Good state, and the probability that it remains in the Good state at the moments 2Δ t, 3Δ t,… mΔ t is (1-p)^m-1 (see Markov diagram on Fig. 1), and the probability that the system changes the state from Good to Bad at the time instant (m+1)Δ t is p.

Using relation (<ref>), we can calculate the average link duration T_twocars and variance σ_twocars^2 of the distribution by the formulas

    T_twocars=∑_l=1^∞ lΔ t P_twocars(l)=∑_l=1^∞ lΔ t (1-p)^l-1p=Δ t/p,


    σ_twocars^2=∑_l=1^∞ (lΔ t)^2 P_twocars(l)-T_twocars^2
    =∑_l=1^∞ l^2 Δ t^2 (1-p)^l-1p-Δ t^2/p^2
    =(2-p/p^2-1/p^2)Δ t^2=(1-p)Δ t^2/p^2.
















 §.§ Distribution of a cluster lifetime


In this section we find the probability P_clust(m) that the existence duration of a cluster composed by cars k, k+1,…,k+s equals exactly mΔ t. We could assume that the cluster exists since the moment Δ t until the moment mΔ t and does not exist at the moment (m+1)Δ t.
The probability P_clust(m) satisfies the formula

    P_clust(m)= (1-p)^s(m-1)(1-q)^γ(m-1) (1-(1-p)^s(1-q)^γ),

where γ is defined by (<ref>).

Let us derive the equation (<ref>).
We consider only the case where k > 1 and k+s < n, because in other cases derivations are similar. The probability P_clust(m) can be calculated by the formula

    P_clust(m)= P_1 P_2,

where P_1 is a probability that the cluster exists at the moments 2Δ t, … mΔ t under the condition that it exists at the moment Δ t, and P_2 is a probability that the cluster does not exist at the moment (m+1)Δ t under the assumption that it exists at the moment mΔ t. First, we  calculate the probability P_1.
The fact that the cluster k,k+1,…,k+s exists at the moment Δ t simply means that at this moment there is a connection between every pair of cars (k,k+1), (k+1,k+2), …, (k+s-1,k+s) and there is no connection between pairs of cars (k,k-1) and (k+s,k+s+1).
The probability that all pairs of cars  (k,k+1), (k+1,k+2), …, (k+s-1,k+s) preserve a connection at the moment 2Δ t is (1-p)^s (see Markov diagram on Fig. 1).
The probability that the pairs of cars (k,k-1) and (k+s,k+s+1) continue to be disconnected at the moment 2Δ t is (1-q)^2. Thus, the probability that the cluster exists at the moment 2Δ t is (1-p)^s(1-q)^2. Continuing these derivations until the moment mΔ t, we find the probability P_1 given as follows:

    P_1 =(1-p)^s(m-1)(1-q)^2(m-1),

since there are m-1 transitions between steps Δ t and mΔ t and at each step we need to multiply the answer by the transitional probability (1-p)^s(1-q)^2.
Finally, we derive the probability P_2.
The cluster should cease to exist at the moment (m+1)Δ t.
The probability that the cluster continues to exist at the next moment is (1-p)^s(1-q)^2, therefore, the probability that it does not exist is

    P_2=1-(1-p)^s(1-q)^2.

Formulas (<ref>)–(<ref>) prove the equation (<ref>).

The average time of cluster existence T_clust and its variance σ_clust^2 are determined by the following formulas:

    T_clust=∑_l=1^∞ lΔ t P_clust(l)
    =∑_l=1^∞ lΔ t(1-p)^s(l-1)(1-q)^γ(l-1) (1-(1-p)^s(1-q)^γ)
    =
    Δ t/1-(1-p)^s(1-q)^γ.


    σ_clust^2=∑_l=1^∞ (lΔ t)^2P_clust(l) - T_clust^2
    =(1+(1-p)^s(1-q)^γ)Δ t^2/(1-(1-p)^s(1-q)^γ)^2-(Δ t/1-(1-p)^s(1-q)^γ)^2
    =
    (1-q)^γ(1-p)^sΔ t^2/(1-(1-q)^γ(1-p)^s)^2.





 §.§ Probability of cluster existence between fixed moments of time



In the section, we derive the probability of a cluster existence between two particular moments of time.
We consider only the case where k>1 and k+s<n, because in other cases derivations are similar.
However, before solving the problem, we find the probability P_clustbeg(m) that at the time mΔ t the cluster that consists of cars k,k+1,…, k+s, is formed, and it does not exist at the moment (m-1)Δ t.

Let us denote the probability of the event that at the moment mΔ t there is a cluster consisting of cars k,k+1, …, k+s by P_1 and the probability that the cluster k,k+1, …, k+s exists at the moments (m-1)Δ t and mΔ t by P_2. Therefore, the probability P_clustbeg(m) is given as follows:

    P_clustbeg(m)=P_1-P_2.

Next, we  calculate each of the probabilities P_1 and P_2 separately.
Firstly, we establish that

    P_1=p_G^s(1-p_G)^2.

Indeed, if the cluster k,k+1, …, k+s exists at the moment mΔ t then
the pairs of cars (k,k+1), (k+1,k+2),…,(k+s-1,k+s) are connected (each with the probability p_G). Thus, the probability of this event is p_G^s, since there are s such pairs.
Additionally, there is no connection between the pairs of cars (k,k-1) and (k+s, k+s+1) (each of disconnections occurs with the probability 1-p_G).
Multiplying the aforementioned probabilities, we get the relation (<ref>).

Regarding the probability P_2, we prove the formula

    P_2=(1-p)^s p_G^s(1-p_G)^2(1-q)^2.

The probability P_2 can be represented as follows:

    P_2=P_3 P_4,

where P_3 is a probability that the cluster k,k+1, …, k+s exists at the moment (m-1)Δ t and P_4 is a probability that it continues to exist at the moment of time mΔ t under the assumption that it exists at the moment (m-1)Δ t.
Repeating derivations for the probability P_1 in the case of the  time instant (m-1)Δ t, we have

    P_3=P_1=p_G^s(1-p_G)^2.

Next, we prove the relation

    P_4=(1-p)^s(1-q)^2.

Suppose, the cluster exists at the moment of time (m-1)Δ t.
The probability that a connection between any pair of the consecutive cars of the cluster is preserved at the moment mΔ t equals 1-p.
Consequently, the probability that the connection between all s pairs of cars is preserved equals (1-p)^s.
The pairs of cars (k-1,k) and (k+s,k+s+1) cannot establish a connection at the moment (m-1)Δ t, the probability that these pairs remain disconnected is (1-q)^2. Multiplying two probabilities (1-p)^s and (1-q)^2, we derive the formula (<ref>).

From (<ref>)–(<ref>), we conclude that

    P_clustbeg(m)=p_G^s(1-p_G)^2
    -(1-p)^s p_G^s(1-p_G)^2(1-q)^2.


Using the obtained probabilities, we can find the probability P_clust(m,l) that the cluster k,k+1,… k+s exists between moments of time mΔ t and lΔ t (l ≥ m). In other words, it is the probability that the cluster exists from the time instant mΔ t to lΔ t (l ≥ m), and does not exist at the moments (m-1)Δ t and (l+1)Δ t.
The probability P_clust(m,l) satisfies the formula

    P_clust(m,l)=(p_G^s(1-p_G)^2
    -(1-p)^s p_G^s(1-p_G)^2(1-q)^2)
    ×(1-p)^s(l-m)(1-q)^2(l-m)(1-(1-p)^s(1-q)^2).

The probability P_clust(m,l) can be decomposed in the product of three terms as follows:

    P_clust(m,l) = P_clustbeg(m)P_5P_6,

where P_5 is a probability that the cluster exists until the moment lΔ t, and P_6 is a probability that the cluster ceases to exist at the moment (l+1)Δ t assuming that it exists at the moment lΔ t. First, we consider the probability P_5 and prove the formula

    P_5 = (1-p)^s(l-m)(1-q)^2(l-m).

By analogy with derivations of (<ref>), we deduce that the probability, that the connection established between the pairs of cars (k,k+1), (k+1,k+2),…,(k+s-1,k+s) at the moment of time mΔ t is preserved at the time instances (m+1)Δ t,… ,lΔ t, equals (1-p)^s(l-m).
Following the same logic of (<ref>), we derive that the probability, that the pairs of cars (k-1,k) and (k+s,k+s+1) do not communicate at the moments of time (m+1)Δ t,… , lΔ t under the condition that the connection is not established at the moment (m-1)Δ t equals (1-q)^2(l-m).
The probability P_5 can be calculated as a product of these probabilities and, therefore, (<ref>) is proven.
By repeating steps of the proof of the equation (<ref>), we conclude that

    P_6=1-(1-p)^s(1-q)^2.

From the formulas (<ref>), (<ref>)–(<ref>), we derive (<ref>).




 §.§ ω-stable connection
 
Definition  A connection between moments of time m and l (m ≤ l) is ω-stable
if the time difference between every two consecutive connections does not exceed time ωΔ t.
Additionally we assume that there exists at least one successful connection established not later than (m + ω)Δ t, and the last connection is established at the moment of time (l-ω)Δ t or later.

It does not make sense to consider ω-stable connection if l<m+ω, because in this case every connection is ω-stable.
Therefore, we assume that l≥ m+ω.
Also, we suppose that ω is an integer number and ω≥ 2.


In the section, we find the probability P_ω(m,l) that the connection between two consecutive cars is ω-stable between the moments mΔ t and lΔ t.
Let us introduce the function h(a,b) equaling the probability that at the moment of time aΔ t, the last connection is established at the time instant bΔ t, and
the function g(a) equaling the probability that there is no connection at the time interval [0, aΔ t].
To derive the function g(a) explicitly, we should multiply the probability (1-p_G), that at the moment mΔ t there is no connection, by the probability (1-q)^a-m that at the moments (m+1)Δ,… aΔ there is no connection as well.
Therefore, the function g(a) has the form

    g(a)=
    (1-p_G)(1-q)^a-m,     a<m+ω
    
    0,     a≥ m+ω.

The following recurrences take place:




    h(a,b)=0, b<a-ω,


    h(a,b)=h(a-1,b)(1-q), a-ω≤ b<a-1,


    h(a,a-1)=h(a-1,a-1)p,


    h(a,a)=h(a-1,a-1)(1-p)+∑_r=a-ω^a-2 h(a-1,r)q+g(a-1)q.

The formula (<ref>) holds, since for b<a-ω, the probability h(a,b) equals zero due to the fact that the time difference between the last connection at the moment of time bΔ t and the next connection exceeds ωΔ t.
The formula (<ref>) holds, because if b<a-1 then at the moment (a-1)Δ t the system is in the Bad state, and the probability that it remains in this state is 1-q.
The formula (<ref>) is derived by applying the same logic.
Finally, in (<ref>), the recursive formula for the probability that the connection is established at the time instant aΔ t, is obtained.
Due to the ω-stability of the connection, the previous time of the connection lies between (a-ω)Δ t and (a-1)Δ t.
The summand h(a-1,a-1)(1-p) occurs in the formula (<ref>), since it is the probability that at the moment of time (a-1)Δ t the system is in the Good state and remains at this state up to the moment of time aΔ t.
The sum ∑_r=a-ω^a-2 h(a-1,r)q contains probabilities h(a-1,r) that the time instant rΔ t is the last moment of time when the system is in the Good state.
It means that the system is in the Bad state at the moment (a-1)Δ t and moves to the Good state at the moment aΔ t. It explains the multiplication of the terms h(a-1,l) by q.

The probability P_ω(m,l) can be calculated by the formula

    P_ω(m,l)=∑_r=l-ω^l h(l,r),

because the last moment of time before lΔ t when the system is in the Good state, can be only lΔ t,(l-1)Δ t,…, (l-ω)Δ t.


The following formulas hold:

    h(m,m)=p_G,


    h(m+1,m+1)=p_G,

where p_G is determined by the formula (<ref>).
The equality (<ref>) takes place , since the probability that connection is established at the moment mΔ is exactly p_G, the formula (<ref>) is obtained similarly, taking into account that ω≥ 2.

Under condition of a > b, application of the relations (<ref>) and (<ref>) provides the expression

    h(a,b)=h(a-1,b)(1-q)=h(a-2,b)(1-q)^2=…
    
    =h(b+1,b)(1-q)^a-b-1=h(b,b)(1-q)^a-b-1p.

From (<ref>) and (<ref>), we obtain

    h(a,a)=h(a-1,a-1)(1-p)
    +∑_r=a-ω^a-2 h(a-1,r)q +g(a-1)q
    =
    h(a-1,a-1)(1-p)  
    +∑_r=a-ω^a-2 h(r,r)(1-q)^a-r-2pq+g(a-1)q.

By substituting a-1 instead of a into (<ref>), we derive

    h(a-1,a-1)
    =h(a-2,a-2)(1-p)  
    +∑_r=a-ω-1^a-3 h(r,r)(1-q)^a-r-3pq+g(a-2)q.

Multiplying (<ref>) by (1-q), we get the following equality:

    h(a-1,a-1)(1-q)=h(a-2,a-2)(1-p)(1-q) 
    + ∑_r=a-ω-1^a-3 h(r,r)(1-q)^a-r-2pq+g(a-2)q(1-q).

Subtraction (<ref>) from (<ref>) gives us

    h(a,a)-h(a-1,a-1)(1-q)=h(a-1,a-1)(1-p)
    -h(a-2,a-2)(1-p)(1-q) +  h(a-2,a-2)pq 
    -h(a-ω-1,a-ω-1) (1-q)^ω-1pq
    +g(a-1)q-g(a-2)q(1-q).

After simplifying (<ref>), we finally derive

    h(a,a)=h(a-1,a-1)(2-p-q)
    -h(a-2,a-2)(1-p-q) 
    -h(a-ω-1,a-ω-1) (1-q)^ω-1pq
    +g(a-1)q-g(a-2)q(1-q).


Let us introduce the function f(a) by the formula

    f(a)=h(a,a).

Expressions (<ref>) and (<ref>) provide the relation

    f(a)=f(a-1)(2-p-q)-f(a-2)(1-p-q)
     -f(a-ω-1) (1-q)^ω-1pq+g(a-1)q-g(a-2)q(1-q).




Our next goal is to express the probability P_ω(m,l) in terms of the function f(a).
Substitution a=l+1 in (<ref>) gives us

    h(l+1,l+1)=h(l,l)(1-p)+q∑_r=l+1-ω^l-1 h(l,r)+g(l)q.

Subtracting (<ref>) multiplied by q  from (<ref>) produces the following equality:

    h(l+1,l+1)- qP_ω(m,l)
    
    = h(l,l)(1-p)-h(l,l)q-h(l,l-ω)q+g(l)q.

Applying (<ref>) to (<ref>), we get

    h(l+1,l+1)- qP_ω(m,l)=h(l,l)(1-p-q) 
    -  h(l-ω,l-ω)(1-q)^ω-1pq+g(l)q.







Therefore, taking into account (<ref>), we derive

    P_ω(m,l)=1/q{f(l+1)-f(l)(1-p-q)
    +  f(l-ω)(1-q)^ω-1pq-g(l)q}.

From (<ref>) and (<ref>), we obtain

    f(m)=p_G,  f(m+1)=p_G.


Combining previous formulas we derive the algorithm below for
calculating the probability P_ω(m,l).
In lines 2, 3, 4 and 7 two arrays f and g are declared and initialized to zero.
Lines 5, 6 and 9 are obtained by the formulas (<ref>) and (<ref>), respectively.
Lines 12–14 are derived by (<ref>), the return value in the line 17 is obtained by the formula (<ref>).







§ SIMULATIONS


In order to verify the theoretical development we conduct a number of numerical simulations with the following parameters:


    R=10^5 symbol/sec, fc=3.9 GHz, A/λ=0.1.

The speed of cars v takes the following values:

    v=30, 60, 90 km/h.

The Doppler frequency shift is calculated by the formula

    f_D=vf_c/c.

For the speeds v=30, 60, 90 km/h Doppler frequency f_D equals 108,217,325  Hz, respectively.
The timestep Δ t between two consecutive transmissions should satisfy the Nyquist–Shannon criteria

    Δ t≤1/2f_D.

We assume that Δ t is given by the formula

    Δ t=1/10f_D.

For speeds v=30, 60, 90 km/h, values of the parameter Δ t are 9× 10^-4,4.6× 10^-4,3× 10^-4 seconds, respectively.




Under these assumptions from (<ref>) and (<ref>), we get the following values of parameters p and q for speeds v=30, 60, 90 km/h:

    p=8.5× 10^-4,1.7× 10^-3, 2.5× 10^-3,


    q=8.1× 10^-3, 1.6× 10^-2, 2.5× 10^-2.

We assume that the network consists of n=10 vehicles.






We use logarithmic scale for all graphs below.
We consider the probabilities of the event that the system remains connected throughout the time interval [0, t].
By this, we mean that the connection is established at each moment of time on a discrete time grid during the interval [0, t]. If we increase the value of the parameter t, then we  increase the number of time moments when the vehicles should remain connected, so the probability of this event decreases. In other words, the considered probabilities are monotonically decreasing functions of the parameter t.

All graphs are represented as straight lines, since the probabilities exponentially decreasing with time, which in logarithmic scale, is represented as linear decreasing straight lines.

We compare the results obtained by the formulas and the results of numerical simulations.
The simulation results obtained by generating evolution of the vehicle network on the road many times, calculating number of the cases where  required characteristics of the network occur and dividing this number by the number of trials.
The values of parameters p and q are too small (about 10^-3–10^-4) that results in negligible probabilities computed by the formulas (<ref>), (<ref>) and (<ref>). It makes impossible to achieve an appropriate simulation precision for the reasonable time.
Therefore, we do not depict the corresponding simulation results on the Figs 3, 4 and 5.


Fig. 3 presents graphs of the distribution (<ref>) of the link duration between two consecutive cars for v=30,60,90 km/h.




	
    < g r a p h i c s >


	Fig 3. Graphs of the distribution (<ref>) of the link duration between two consecutive cars for v=30,60,90 km/h



Fig. 4 shows the distribution (<ref>) of the lifetime of the cluster that consists of cars 2, 3 and 4 for v=30,60,90 km/h.


To illustrate decreasing of the probability (<ref>) of the cluster existence between fixed moments of time mΔ t and lΔ t, we fix the value of the parameter m=2 and vary the value of l=m,m+1,….
We assume that the cluster consists of cars with numbers 2, 3 and 4.
The graphs of the obtained functions of parameter l are shown on the Fig. 5 below.

Fig. 6 demonstrates both the simulation results and the probabilities computed by the algorithm from the section <ref>.
We fix an initial moment of time mΔ t and assume that m=2, and vary l=m,m+1,….
Simulations results are obtained after 50000 generations of the car evolution process.




 
	
    < g r a p h i c s >


	Fig 4. Graphs of the probability P_clust(m) given by the formula (<ref>) for v=30,60,90 km/h





 
	
    < g r a p h i c s >


	Fig 5. Graphs of the probability P_clust(r,t) of the cluster existence between times given by the formula (<ref>).



 
	
    < g r a p h i c s >


	Fig 6. Graphs of numerical simulation of the probability of 3-stable connection between times m=2 and l with variable l, and the probability P_ω(m,l) returned by algorithm from the section <ref>.







§ SIMULATIONS FOR LARGE VALUES 
OF PARAMETERS P AND Q
 



In the section, we perform simulations that confirm the correctness of the formulas (<ref>), (<ref>) and (<ref>) for increased values of parameters p and q, which have the order of 10^-2. The results are represented on Figs. 7, 8 and 9 below.
The graphs perfectly match each other, which proves the correctness of the above mentioned formulas.



Fig. 7 presents two graphs of the numerical simulation and probability of the link duration P_twocars given by the formula (<ref>) for p=0.02, q=0.02, Δ t=0.01 and 10^5 iterations.



Below on Fig. 8, the simulation results of the cluster lifetime duration are presented for the cluster that consists of cars 2, 3 and 4, and also, the graph of the predicted distribution  P_clust(m) for p=0.02,q=0.02, Δ t=0.01 and 10^5 iterations.



	
    < g r a p h i c s >


	Fig 7. Graphs of the numerical simulation of the distribution of the connection lifetime duration between two consecutive cars and distribution (<ref>).





	
    < g r a p h i c s >


	Fig 8. Graphs of the numerical simulations of the cluster lifetime and the probability P_clust(m).





Simulation results of the probability of the cluster existence between times 15Δ t and 15Δ t,16Δ t… 30Δ t are shown on Fig 9.
Thus, we assume value of m=15 to be constant and change the value of the parameter l=15,16,… 30.
Fig. 9 depicts the graph of the probability (<ref>) for p=0.05, q=0.05, Δ t=0.01 and 10^6 iterations.



	
    < g r a p h i c s >


	Fig 9. Graphs of the numerical simulation of the probability of the cluster existence between times 15Δ t and 15Δ t,16Δ t… 30Δ t and P_clust(m,l).





§ CONCLUSION


In the article, we consider evolution of the vehicle network on a highway and assume that the connection between each pair of consecutive cars can be established with a certain probability.
We derive the probability distributions that describe evolution of such characteristics of the network as a distribution of the link duration between each pair of cars, cluster lifetime, and etc.
All the derivations are performed under the assumption that the connectivity model is described by the two state Markov chain model, where the parameters of the model are explicitly expressed through the parameters of the network.







1

ML
R.K. Kansla, K. Bansal,  "A Machine Learning Approach to Beaconing for Vehicular Ad Hoc Network (A Review)". IOSR J. Comput. Eng., vol. 16, no. 4, pp. 52–55, 2014.

ML2 N. Taherkhani, S. Pierre, "Centralized and Localized Data Congestion Control Strategy for Vehicular Ad Hoc Networks Using a Machine Learning Clustering Algorithm", IEEE Trans. Intell. Transp. Syst., vol. 17, no. 11, pp. 3275 – 3285, 2016.


ML3 Z. Peng, S. Gao, Z. Li, B. Xiao, Y. Qian, "Vehicle Safety Improvement through Deep Learning and Mobile Sensing", IEEE Netw., vol. 32, no. 4, pp. 28 – 33, 2018.


ML4 Q. Zheng, K. Zheng, H. Zhang, V. C. M. Leung, "Delay-Optimal Virtualized Radio Resource Scheduling in Software-Defined Vehicular Networks via Stochastic Learning", IEEE Trans. Veh. Technol., vol. 65, no. 10, pp. 7857 – 7867, 2016.


ML5 H. Ye, L. Liang, G. Ye Li, J. Kim, L. Lu, M. Wu, "Machine Learning for Vehicular Networks: Recent Advances and Application Examples", IEEE Veh. Technol. Mag., vol. 13, no. 2, pp. 94 – 101, 2018.



M1 V. Nguyen, T. Oo, P. Chuan, C. Hong "An Efficient Time Slot Acquisition on the Hybrid TDMA/CSMA Multichannel MAC in VANETs", IEEE Commun. Lett., vol. 20, no. 5, pp. 970 – 973, 2016.

M2 Z. Tianjiao, Z. Qi, "Game-based TDMA MAC protocol for vehicular network",IEEE J. Commun. Netw., vol. 19, no. 3, pp. 209 – 217, 2017.


M3 C. Shao, S. Leng, Y. Zhang, A. Vinel, M. Jonsson, "Performance Analysis of Connectivity Probability and Connectivity-Aware MAC Protocol Design for Platoon-Based VANETs", IEEE Trans. Veh. Technol., vol. 64, no. 12, pp. 5596 – 5609, 2015.


M4 Y. Cao, H. Zhang, D. Wu, D. Yuan, "OGCMAC: A Novel OFDM Based Group Contention MAC for VANET Control Channel",
IEEE Trans. Wireless Commun., vol. 16, pp. 5796 – 5809, no. 7, 2017.

M5 S. Bharati, W. Zhuang, "CAH-MAC: Cooperative ADHOC MAC for Vehicular Networks", IEEE J. Sel. Areas Commun., vol. 31, no. 9,
pp. 470 – 479, 2013.

M6 Y. Yao, K. Zhang, X. Zhou, "A Flexible Multi-Channel Coordination MAC Protocol for Vehicular Ad Hoc Networks",
IEEE Commun. Lett., vol 21, no. 6, pp. 1305 – 1308, 2017.





P1
B. Wang, T. Adams, W. Jin, Q. Meng, "The process of information propagation in a traffic stream with a general vehicle headway: A revisit", Transp. Research Emerg. Technol. C, vol. 18, no. 3, pp. 367–375, 2010.



P2
A. Babu and V. Muhammed Ajeer, "Analytical model for connectivity of vehicular
ad hoc networks in the presence of channel randomness," Int.
	J. Commun. Syst., vol. 26, no. 7, pp. 927–946, 2011.


P3
S. Kwon, Y. Kim, and N. B. Shroff, "Analysis of connectivity and capacity in
1-d vehicle-to-vehicle networks," IEEE Trans. Wireless Commun., vol. 15, no. 12, pp. 8182–8194, 2016.


Clust H. Wang, R. P. Liu, W. Ni, W. Chen, I. B. Collings, "VANET Modeling and Clustering Design Under Practical Traffic, Channel and Mobility Conditions",
IEEE Trans. Commun., vol. 63, no. 3,
pp. 870 – 881, 2015.






My
G. Dubosarskii, S. Primak, X. Wang, "On the higher order statistics of car clustering in vehicle communications networks on a road," in Proc. 28th IEEE Int. Symp. Pers., Indoor Mobile Radio Commun. (PIMRC), 2017.

Clust3 S. T. Hasson, Z. Y. Hasan, "Roads clustering approach's in VANET models", in Proc. 
	Conf. New Trends Inf. Commun. Technol. Appl. (NTICT),
pp. 316 – 321, 2017.

CarNet A. Kesting, M. Treiber, D. Helbing "Connectivity Statistics of Store-and-Forward Intervehicle Communication", IEEE Trans. Intell. Transp. Syst., vol. 11, no. 1, pp. 172 – 181, 2010.


CarNet2 G. Yan and S. Olariu, "A Probabilistic Analysis of Link Duration in
Vehicular Ad Hoc Networks", IEEE Trans. Intell. Transp. Syst., vol. 12, no. 4,
pp.  1227 – 1236, 2011.





WM H. Wang, N. Moayeri, "Finite-state Markov channel — a useful model for radio communication channels",
 IEEE Trans. Veh. Technol., vol 44, no. 1, 163–171, 1995.

Primak S. Primak, V. Kontorovich, V. Lyandres, Stochastic methods and their applications to communications: stochastic differential equations approach. 2005, p. 434.











Gleb Dubosarskii
received his B.E. and M.S. degrees in Applied Mathematics from the Ural Federal University in 2009 and 2011,
respectively, and his Candidate of Science Degree in Approximation Theory
from the Krasovskii Institute of Mathematics and Mechanics of the Ural
Branch of the Russian Academy of Sciences in 2014. Currently, he is a
Ph.D. student in the Department of Electrical and Computer Engineering
at Western University, Canada. His current research interests are in
the areas of communications, machine learning and mathematical
modeling.



Serguei L. Primak
(S’94-M’97) received the MSEE degree from
St. Petersburg University of Telecommunications, St. Petersburg,
Russia, in 1991 and the PhD degree in electrical engineering from the
Ben-Gurion University of the Negev, Beer-Sheva, Israel, in 1996.
Currently, he is a lecturer and post-doctoral fellow with the University of
Western Ontario, London, Ontario, Canada. His current interests are in
the field of ultrawideband radar applications, random signal generations,
modeling of wave propagation in a city, timefrequency analysis, and
inverse problems of electromagnetics. He is a member of the IEEE.



Xianbin Wang(S’98-M’99-SM’06-F’17) is a Professor and Tier 1 Canada Research Chair at Western
University, Canada. He received his Ph.D. degree in
electrical and computer engineering from National
University of Singapore in 2001.
Prior to joining Western, he was with Communications Research Centre Canada (CRC) as a Research Scientist/Senior Research Scientist between
July 2002 and Dec. 2007. From Jan. 2001 to July
2002, he was a system designer at STMicroelectronics. His current research interests include 5G
technologies, Internet-of-Things, communications security, machine learning
and locationing technologies. Dr. Wang has over 350 peer-reviewed journal
and conference papers, in addition to 29 granted and pending patents and
several standard contributions.
Dr. Wang is a Fellow of Canadian Academy of Engineering, a Fellow of
IEEE and an IEEE Distinguished Lecturer. He has received many awards and
recognitions, including Canada Research Chair, CRC Presidents Excellence
Award, Canadian Federal Government Public Service Award, Ontario Early
Researcher Award and six IEEE Best Paper Awards. He currently serves
as an Editor/Associate Editor for IEEE Transactions on Communications,
IEEE Transactions on Broadcasting, and IEEE Transactions on Vehicular
Technology and He was also an Associate Editor for IEEE Transactions
on Wireless Communications between 2007 and 2011, and IEEE Wireless
Communications Letters between 2011 and 2016. Dr. Wang was involved in
many IEEE conferences including GLOBECOM, ICC, VTC, PIMRC, WCNC
and CWIT, in different roles such as symposium chair, tutorial instructor, track
chair, session chair and TPC co-chair.




