Connectivity Analysis for Free-Flow Traffic in VANETs: A Statistical Approach

Abstract

Intervehicle communication gives vehicles opportunities to exchange packets within the limited radio range and self-organized in Ad Hoc manner into VANETs (Vehicular Ad Hoc Networks). However, due to issues such as the high mobility, insufficient market penetration ratio, and lacking of roadside units, connectivity is actually a big problem in VANETs. In addition, relying only on the direct connectivity in most of the previous works, say broadcasting which provides one-hop connections between nodes is far from the continuously growing application demands in VANETs, such as inter-vehicle entertainments, cooperative collision avoidances, and inter-vehicle emergency notifications. Therefore, the indirect connectivity from multihop forwarding is also a necessary complement especially for the case where direct connection is hardly achieved. In this paper, we define a new metric, that is, available connectivity, to consider both direct and indirect connectivity. After analyzing the statistical properties of direct and indirect connectivity in vehicular environment, the available connectivity is proposed and quantified for practical usage. Numerical results show that our available connectivity could provide correct and useful references for protocols design and performance improvements of different applications.

1. Introduction

Vehicular Ad hoc Networks [1–3] (VANETs) are distributed, self-organized communication networks composed of moving vehicles and are thus characterized by very high nodal mobility and limited degrees of freedom in the mobility patterns. The discussed IEEE 1609 Wireless Access in Vehicular Environments [4] (WAVE) draft is being developed for VANETs applications mainly considering safety-related scenarios, such as cooperative forward collision warning [5, 6] (CCW) systems, traffic signal violation warning [7] systems, and lane change warning [8] systems, and at the same time taking account of some requirements from nonsafety-related applications [9]. Indeed, all the above applications greatly rely on the packets exchange on reliable links and robust connections between vehicles. From this perspective, network connectivity becomes a fundamental and crucial issue to any practical application in VANETs. Regarding the node mobility, vehicles can not only depend on the direct one-hop broadcasting; they also need packets to be indirectly forwarded to the destinations through store-carry or multihop relays. However, it is worth noting that both direct and indirect connections are sometime hardly achieved especially during sparse communication environments such as the suburb highway or cases with low market penetration ratio [10]. As a result, the limited connectivity directly affects the possible speed at which information can be transported over a VANET and hence directly influence the up-to-datedness of wanted notifications which may result in accidents.

In summary, analysis to the connectivity is very necessary in VANETs. Actually, a number of models have been proposed in previous works such as stochastic process [11] based, Gaussian unitary ensemble (GUE) of random-matrix theory [12] based, and queuing theory [13] based and almost all their works discussed the connectivity with the famous three-phase traffic theory in which the fundamental relationship between traffic parameters on a road segment is given by the following equation:

$$\begin{array}{cc}& F=S\times K,\end{array}$$

(1)

where F, S, and K are the traffic flow, average speed, and traffic density, respectively. The influences on the connectivity from the above parameters can be disclosed from Figure 1. Before the state transforming point, at which packets begin to be queued in transceivers' sending buffers when the density of vehicles increases, the connectivity is intermittent and thus needs further studying to improve the performance. For the stage after the state transforming point, which is named the congestion flow state and depicted by dashed line, the connectivity could be basically guaranteed regarding the larger density. In that case, road is often jammed by vehicles very close to each other whereby the direct connectivity can be readily obtained. Accordingly, our research will focus on the free-flow state depicted by the solid line throughout our paper.

Figure 1

Relationship between basic parameters in the vehicle traffic theory.

The rest of the paper is organized as follows. Section 2 provides our research motivations and discusses the possible usages of the available connectivity in VANETs. Section 3 presents previous related works. Section 4 introduces our definition of the available connectivity, assumptions, and the statistical analysis of direct and indirect connectivity. Numerical results and performance evaluations are presented in Section 5. Our work is concluded in Section 6 followed by acknowledgments and cited references.

2. Motivations

“Connectivity” in Ad Hoc networks actually has a mature body of research but still absorbed lots of research interests in VANETs recently. With VANETs gradually stepping into our daily life, the connectivity has played an important role in many road applications to ensure driving safety and increase comfortableness. For instance, in CCW scenario, a good connectivity could help to avoid the chain collisions through disseminating warning notifications farther and quicker. In Figure 2, the red car crashed with the blue car and sent a CCW message. Then, car 1 could receive the CCW by direct connection and take brake in time to avoid crash. However, without the help of the indirect connection, that is, multi-hop forwarding in this case, car 2, and 3 may collide with the front car if the intervehicle distances are approaching the unsafe range [14]. In Figure 3, vehicles 2~5 could detect the front traffic jam by the messages store-carry-forwarded by vehicle 1 from the red sender. Therefore, owing to the indirect connectivity, they can beforehand enter into the auxiliary road to avoid the congestion and save time. In summary, the connectivity, direct or indirect, could provide more opportunities for vehicles to make their decisions wisely and safely and to achieve better driving experiences. Hence, a good definition of the connectivity or the metric to measure the connectivity is essential in VANETs.

Figure 2

CCW application scenario.

Figure 3

Traffic jams avoidance.

In our work, we define the connectivity as the probability of connections which could be achieved directly or indirectly. Numerical results show that our definition can explore the potential transmission opportunities for vehicles especially in the safety-related applications context. The connection possibility is discussed through statistical analysis in terms of either connected durations or inter-vehicle distances. To reflect the high dynamics of the connectivity due to different mobility patterns, we also introduce the influence of velocity into our work.

Indeed, a wise definition of the available connectivity can practically make many otherwise complex problems easy. For example, to design an admission control strategy in VANETs, the available connectivity could provide important references for the connectivity improvement by giving the specific time or location at which the vehicles may be admitted into. In addition, to evaluate the performance of emergency-related applications, the available connectivity could roughly work out the delivery ratio of emergency notifications from given vehicles. On the other hand, to make the emergency notifications spread faster and further, the available connectivity could also be taken as a better criterion for relays selection. Besides, to route the packets based on the available connectivity, the throughput can be improved and the backup multiple paths may be simultaneously figured out whereby transmission robustness could be guaranteed. In a dense network, available connectivity may also be able to offer a reference for the threshold of packet generation rate to maintain sufficient connectivity but not make the overall network congested. In summary, along with the available connectivity, a plethora of works now can be implemented to improve the safety, comfortableness, and efficiency in VANETs.

3. Related Works

Although connectivity analysis is a classical issue in wireless communication networks, it is now still a hot topic in VANETs regarding the recently increasing research activities [15–17]. In my point of view, the connectivity research in VANETs can be generally classified into two categories: one for investigating the lifetime properties of connected links or paths; another via the measurement of inter-vehicle distances.

Researches on lifetime properties mainly focus on the statistical analysis of the connection duration. In [11], the authors discussed the connection duration expression in detail considering the velocity vectors with yaw angles. Their numerical results found that high relative velocities impose a hard task on some cooperative maneuvers including underlying routing protocols. However, even the short connection duration is still enough for emergency notification scenarios. In [18], the connection duration between two adjacent vehicles was figured out, given their speeds, directions, and the radio ranges. According to the calculated connection period expression, an admission control strategy is proposed to determine whether the next vehicle is allowed to be injected into the current traffic flow without interrupting the ongoing connections. In [19], metrics for evaluating nodal connectivity in VANETs had been presented considering the different nodal mobility patterns. The connection period distribution was characterized by average duration of the k-hop path existing between any two nodes. They also showed by simulation that multi-hop paths have much poorer connectivity performance than the single-hop one in VANETs.

Researches on the connectivity through inter-vehicle distances attempt to disclose the relationship between the connectivity and the distance which is defined as the length of the connected path. In [11], the distance distribution had been expressed by a tuple ( $h,v,\rho$ ), where h denotes the inter-vehicle distance, v indicates the velocity, and ρ is the market penetration ratio, respectively. By taking specific propagation model and the radio range into consideration, the connectivity formula was given. Without loss of generality, the expression was then further extended to the connectivity of a node with degree n. In [13], the authors introduced an equivalent $M/D/\infty$ queuing model and applied Laplace transform to the tail probability of the connection distance to find an explicit expression for the expected value of this distance. Their numerical results showed that the increasing of traffic flow and the vehicles' radio range correspondingly leads to the increasing of the discussed connectivity in terms of platoon size and connection distance. In [20], the paper showed that, under free-flow state, the connectivity increases with either the density or the number of lanes growing. Especially, they found that the inter-vehicle distances had a major impact on connectivity when it is within 3-4 times larger than the radio range. Beyond this distance, the connectivity declines slowly. In [21], a simple geometric analysis to the connectivity was proposed in vehicular networks under a distance-based radio communication model. The authors presented the notion of the connectivity robustness based on inter-vehicle distances, whereby a local computable function could be obtained to provide a sufficient condition for the connectedness of the network. For the above-mentioned works, although, most of them could deduce out or express the connectivity with vehicles density [22, 23], speed or equivalent speed [24], radio ranges [22, 25], and so forth, their methods actually can all be equivalently extended to the approach using statistical distributions of connection durations or inter-vehicle distances. Generally speaking, it is difficult to give a globally uniform probability density function (PDF) or cumulative distribution function (CDF) expression of the inter-vehicle distances or connection durations in different application scenarios such as overtaking, platoon, and collisions. But, when the traffics are in the free-flow state, the distribution function and probability of the minimum node degree can be exactly calculated whereby available connectivity could be figured out.

4. The Connectivity Analysis in VANETs

4.1. The Analytical Model and Definitions

As we have stated before, the connectivity in the free-flow state is worth studying in view of its uncertainty and scarcity. Thus, in this section, we introduce a highway as our discussing objective where vehicles form a free-flow state traffic with lower distribution density. In our analysis, an equipped vehicle is taken as a node for simplicity. The discussed scenario is plotted in Figure 4, where all cars drive on a single lane represented by a line. We assume that $X_0$ requests to send packets to cars on its right. $X_0$ here is the source node at the origin of the one-dimensional coordinate system and we also take it as the reference point later for our connectivity analysis. The arrival stochastic process of these vehicles is supposed to be a Poisson process with intensity F. Let ε denote the average density of equipped vehicles in our discussed road segment. Thus, the arrival rate λ is equal to $F\epsilon$ .

Figure 4

The analytical model used for highway and the vehicles traffic follows Poisson arrival process.

Definition 1.

Define the connectivity of two nodes as $C(x)$ , where $C(x)$ is the probability that node x could reach the reference node $X_0$ .

Definition 2.

Let i be the farthest node which can communicate with $X_0$ . i in later discussion is also named as the end node with radio range $R_i$ .

X is a variable representing the distance between $X_0$ and the end node. The PDF and CDF of X can be expressed as $f(x)=\text{Pr}(X=x)$ and $F(x)=\text{Pr}(X\le x)$ , respectively. If we suppose that X is within $[x,x+\mathrm{\Delta }x]$ , it means the following (i) There is at least one node in $[x,x+\mathrm{\Delta }x]$ . (ii) The end node could connect with $X_0$ by single-hop broadcasting. (iii) There is no node within $(x+\mathrm{\Delta }x,x+\mathrm{\Delta }x+R_i)$ . If and only if the above three conditions are all met, we say the node i is the end node [26].

We suppose that two nodes are connected if they are falling into the radio range of each other and the disconnection due to collisions or asymmetrical channel conditions is not taken into account.

4.2. The Statistical Model with Constant Radio Range Setting

In this section, we discuss the connectivity when all nodes choose the same constant radio range, that is, R. We model the one-dimension highway as an $M/D/\infty$ system [27] as shown in Figure 5.

Figure 5

The relationship between M/D/∞ system and highway model.

We investigate $C(x)$ of any equipped vehicle x in the highway. In free-flow state, vehicles move independently and their velocities follow the normal distribution [28] with PDF $f_v(v)$ as

$$\begin{array}{cc}& f_v\left(v\right)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-{\left(v-\mu \right)}^2/2{\sigma }^2},\end{array}$$

(2)

where μ is the average speed and σ is the standard deviation of velocity. We also introduce a metric, that is, speed factor, to reflect the impact of velocity on the inter-vehicle distances and the resulted connectivity.

Definition 3.

A is defined as the speed factor with unit hour/km as

$$\begin{array}{cc}& A={{\displaystyle \int }}_{v_{\min }}^{v_{\max }}\frac{{\stackrel{⌢}{f}}_v\left(v\right)}{v}dv,\end{array}$$

(3)

where

$$\begin{array}{cc}& {\stackrel{⌢}{f}}_v\left(v\right)=\frac{f_v\left(v\right)}{{{\displaystyle \int }}_{v_{\min }}^{v_{\max }}{f}_v\left(s\right)ds}.\end{array}$$

(4)

$v_{\min }$ and $v_{\max }$ in (4) indicate the permitted minimum and maximum velocity on highway, respectively, and they satisfy the following equation. Consider

$$\begin{array}{cc}& 2{{\displaystyle \int }}_{v_{\min }}^{v_{\max }}{f}_v\left(s\right)ds=\mathrm{erf}\left(\frac{v_{\max }-\mu }{\sigma \sqrt{2}}\right)-\mathrm{erf}\left(\frac{v_{\min }-\mu }{\sigma \sqrt{2}}\right).\end{array}$$

(5)

For a PDF curve of a normal distribution, the region corresponding to the x-axis coordinate ranging from $[\mu -3\sigma ,\mu +3\sigma ]$ covers about 99.7% of the probability area; thus, we reasonably choose $\mu -3\sigma$ and $\mu +3\sigma$ as the typical values of $v_{\min }$ and $v_{\max }$ , respectively. Indeed, vehicles in highway can travel neither too fast for safety consideration nor too slow for traffic efficiency. Although speed limits are set, overtaking is still allowed to reflect the practical case.

With the above definitions and assumptions, the expression of connectivity with constant radio range setting could be given as follows.

Theorem 4.

For the case where vehicles all have the same constant radio range, the connectivity could be deduced as

$$\begin{array}{cc}& C\left(x\right)=\{\begin{array}{cc}1,\hfill & x\in \left[0,R\right),\hfill \\ 1-e^{-\lambda AR}-\left(x-R\right)\lambda A{e}^{-\lambda AR},\hfill & x\in \left[R,2R\right),\hfill \\ C\left(nR\right)-w\left(x\right),\hfill & x\in \left[nR,\left(n+1\right)R\right),\hfill \end{array}\end{array}$$

(6)

where $n\ge 2$ , and

$$\begin{array}{l}\hspace{0.17em}\hspace{0.17em}C(nR)=\underset{x\to nR}{lim}C(x),\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}x\hspace{0.17em}\epsilon \hspace{0.17em}[(n-1)R,nR),\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}w(x)=\lambda A{e}^{-\lambda AR}{\int }_{nR}^x\left[\sum _{k=0}^{n-1}Q(k)\right]dt,\hfill \\ Q(k)=\frac{{[t-(k+1)R]}^k-e^{-\lambda AR}\cdot {[t-(k+2)R]}_{+}^k}{k!}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}.{(-\lambda A{e}^{-\lambda AR})}^k,\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{x}_{+}^k=\{\begin{array}{l}{x}^k,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}x\ge 0\hfill \\ 0,\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}x<0.\hfill \end{array}\hfill \end{array}$$

(7)

Proof.

Let $f_d(t)$ and $F_d(t)$ be the PDF and the CDF of the maximum radio range of $X_0$ . With Figure 5 and based on [27], we have

$$\begin{array}{cc}& f\left(x\right)=f_d\left(x+R\right),\end{array}$$

(8)

where $f_d(t)$ corresponds to the PDF of busy period in $M/D/\infty$ system, and its Laplace transform is given by

$$\begin{array}{cc}& L\left(f_d\left(t\right)\right)=f_d\left(s\right)=\frac{e^{-sR}\left(1-F_H\left(R\right)\right)}{1-{{\displaystyle \int }}_0^R{e}^{-sh}d{F}_H\left(h\right)},\end{array}$$

(9)

where $F_H(h)$ is the CDF of inter-vehicle distances. Note that inter-vehicle distances in $M/D/\infty$ system are independent and identically distributed (IID) [29].

Therefore, we have the following equations:

$$\begin{array}{cc}& f\left(x-R\right)=f_d\left(x\right),\\ L\left(F\left(x\right)\right)=F\left(s\right)=\frac{1}{s}{e}^{sR}{f}_d\left(s\right),\end{array}$$

(10)

where $f_d(s)$ and $F(s)$ correspond to the Laplace transform of $f_d(x)$ and $F(x)$ , respectively.

Based on Definition 2 for an end node, the connectivity of any node at x is

$$\begin{array}{cc}& C\left(x\right)=1-F\left(x-R\right),\end{array}$$

(11)

and its Laplace transform is

$$\begin{array}{cc}& L\left(C\left(x\right)\right)=C\left(s\right)=\frac{1}{s}-e^{-sR}F\left(s\right).\end{array}$$

(12)

With above equations, (12) can be rewritten as

$$\begin{array}{cc}& C\left(s\right)=\frac{1}{s}-\frac{1}{s}\frac{e^{-sR}\left(1-F_H\left(R\right)\right)}{1-{{\displaystyle \int }}_0^R{e}^{-sh}d{F}_H\left(h\right)}.\end{array}$$

(13)

Actually, in [13], the CDF expression of the inter-vehicle distance is given by

$$\begin{array}{cc}& F_H\left(h\right)=1-e^{-\lambda Ah},\end{array}$$

(14)

and the average inter-vehicle distance is written as

$$\begin{array}{cc}& E\left[H\right]=\frac{1}{\lambda A}.\end{array}$$

(15)

Thus, with (12) and (14), we have

$$\begin{array}{cc}& C\left(s\right)=\frac{1}{s}-\frac{1}{s}\frac{s+\lambda }{s{e}^{\left(s+\lambda \right)R}+\lambda }.\end{array}$$

(16)

Applying an inverse Laplace transforming [30] to (16), we have the expression of $C(x)$ as (6).

Remark 5.

$C(x)$ is equal to 1 when x is within the range $[0,R)$ ; that is, a node falling into tother radio range can connect to it if it wishes.

Remark 6.

If a node is exactly located at $x=R$ , then $1-C(R)$ is the probability that it cannot connect to the reference node. The probability that there is no node within range $(0,R]$ is $e^{-\lambda AR}$ for a Poisson arrival process.

Remark 7.

$C(x)$ decreases as the relative distance x increases. In the extreme case, $C(x)\to 0$ when $x\to \infty$ .

The above remarks also validate Theorem 4. To understand this theorem in depth, we also explore some connectivity-related statistical properties including the probability that a given node is isolated, the area that a sent message may cover, and the probability of the number of connected nodes. We also classify the connected nodes into two categories by relaying hops between them and analyzing the corresponding connectivity.

(1) Probability that a Given Node Is Isolated. The probability that a given node is isolated, denoted by $P_I$ , can be determined by the following theorem.

Theorem 8.

The isolation probability is given by

$$\begin{array}{cc}& P_I={\left(1-C\left(R\right)\right)}^2=e^{-2\lambda AR}.\end{array}$$

(17)

For a node at x, $P_I$ is equal to the probability that there is no node within the range $[x-R,x+R]$ .

(2) The Area that a Sent Message May Cover. We discuss the area that a sent message from the reference node can cover. The single and multi-hop cases are both considered. Generally, this characteristic can also be evaluated with coverage probability. Here, we use the expectation to show the average value in general case. Because the system is initially assumed not empty, the mathematic expectation could be given by the following theorem.

Theorem 9.

The expectation of the coverage area for a message sent from the reference node is

$$\begin{array}{cc}& E\left({\text{Cov}}_{+}\right)=-\frac{\partial }{\partial s}\left(1-s·C\left(s\right)\right)|{}_{s=0}+E\left[H\right],\end{array}$$

(18)

where ${\text{Cov}}_{+}$ means the area corresponding to the right side of a given node.

Proof.

Based on [27], we can obtain the following equations for different system initial conditions. Consider

$$\begin{array}{cc}& E\left[{\text{Cov}}_{+}\right]=-\frac{\partial f_d\left(s\right)}{\partial s}|{}_{s=0}+E\left[H\right].\end{array}$$

(19)

Then, with (10) and (12), (18) could be derived out.

Corollary 10.

If both sides of the discussed node are considered, (18) could be rewritten as

$$\begin{array}{cc}& E\left[\text{Cov}\right]=E\left[{\text{Cov}}_{+}+{\text{Cov}}_{-}\right]=\frac{2e^{\lambda AR}}{\lambda A},\end{array}$$

(20)

where ${\text{Cov}}_{-}$ corresponds to the area on the left.

(3) Probability of the Number of Connected Nodes. The node which can reach the reference node is called a connected node. Here we discuss the possible number of the connected nodes, that is, $\text{CN}$ . Similarly, we define ${\text{CN}}_{+}$ as the number on the right and ${\text{CN}}_{-}$ on the left.

Theorem 11.

The Probability Mass Function (PMF) of $CN$ is

$$\begin{array}{cc}& p\left(CN=m\right)=\left(m+1\right){\left(1-F_H\left(R\right)\right)}^2{F}_H{\left(R\right)}^m,\end{array}$$

(21)

where $m=\mathrm{0,1},\dots$ .

Proof.

We first focus on ${\text{CN}}_{+}$ and then extend the result to ${\text{CN}}_{-}$ .

The PMF of ${\text{CN}}_{+}$ for $k=0,1,\dots$ can be expressed as

$$\begin{array}{cc}& p\left({\text{CN}}_{+}=k\right)=\left(1-F_H\left(R\right)\right)F_H{\left(R\right)}^k.\end{array}$$

(22)

The result for ${\text{CN}}_{-}$ is proved in the same way. Then, the PMF for both sides is derived as follows. Consider

$$\begin{array}{l}p\left(\text{CN}=m\right)={\displaystyle \sum }_{k=0}^{m}p\left(\text{CN}=m,{\text{CN}}_{+}=k\right)\\ \phantom{p\left(CN=m\right)}={\displaystyle \sum }_{k=0}^{m}p\left({\text{CN}}_{-}=m-k,{\text{CN}}_{+}=k\right)\\ \phantom{p\left(CN=m\right)}={\displaystyle \sum }_{k=0}^{m}p\left(\text{CN}=m-k\right)p\left({\text{CN}}_{+}=k\right).\end{array}$$

(23)

Simplify the above equation and then the result can be rewritten as (21).

Theorem 12.

The tail probability of $CN$ is

$$\begin{array}{cc}& p\left(CN\ge m\right)=\left[m\left(1-F_H\left(R\right)\right)+1\right]F_H{\left(R\right)}^m.\end{array}$$

(24)

Proof.

According to (21), we have

$$\begin{array}{l}p\left(\text{CN}\ge m\right)={\displaystyle \sum }_{k=m}^{\infty }p\left(\text{CN}=k\right)\\ \phantom{p\left(\text{CN}\ge m\right)}={\displaystyle \sum }_{k=m}^{\infty }\left(k+1\right){\left(1-F_H\left(R\right)\right)}^2{F}_H{\left(R\right)}^k\\ \phantom{p\left(\text{CN}\ge m\right)}=\left[m\left(1-F_H\left(R\right)\right)+1\right]F_H{\left(R\right)}^m.\end{array}$$

(25)

In addition, the probability that at most k nodes are connected is

$$\begin{array}{cc}& p\left({\text{CN}}_{+}\le k\right)=1-F_H{\left(R\right)}^{k+1}.\end{array}$$

(26)

The probability generating function (PGF) of $\text{CN}$ is

$$\begin{array}{cc}& {\text{PGF}}_{{\text{CN}}_{+}}\left(z\right)=\frac{1-F_H\left(R\right)}{1-z{F}_H\left(R\right)}.\end{array}$$

(27)

And the expected value of ${\text{CN}}_{+}$ is

$$\begin{array}{cc}& E\left[{\text{CN}}_{+}\right]=\underset{z\to 1}{\lim }\frac{\partial {\text{PGF}}_{{\text{CN}}_{+}}\left(z\right)}{\partial z}=\frac{F_H\left(R\right)}{1-F_H\left(R\right)}.\end{array}$$

(28)

Substituting (14) into (28), we obtain

$$\begin{array}{cc}& E\left[{\text{CN}}_{+}\right]=e^{\lambda AR}-1.\end{array}$$

(29)

Corollary 13.

The expectation of $CN$ is

$$\begin{array}{cc}& E\left[CN\right]=2e^{\lambda AR}-2.\end{array}$$

(30)

Let Q be the probability lower bound when the number of connected nodes is $C{N_{re}}_{+}$ and it can be written as

$$\begin{array}{cc}& Q={\left(1-e^{-\lambda AR}\right)}^{C{N}_{re}}.\end{array}$$

(31)

For a given Q and ${{CN}_{re}}_{+}$ , we may obtain a critical radio range, which will be explained later in Corollary 14 as

$$\begin{array}{cc}& R_c=-\frac{1}{\lambda A}\ln \left(1-Q^{1/C{N}_{re}}\right).\end{array}$$

(32)

Actually, the radio range is together determined by the transmission power $P_{tx}$ , the additive Gaussian noise power $P_{noise}$ , the signal-to-noise ratio (SNR) ψ, and the path loss factor α. The relationship of them is described by (33) where K is a constant depending on the system setting.

$$\begin{array}{cc}& R={\left(\frac{K{P}_{tx}}{\psi P_{noise}}\right)}^{1/\alpha }.\end{array}$$

(33)

Similarly, the equation for Q considering both sides is

$$\begin{array}{cc}& Q=\left(C{N}_{re}+1\right)e^{-2\lambda AR}{\left(1-e^{-\lambda AR}\right)}^{C{N}_{re}}.\end{array}$$

(34)

Corollary 14.

The critical range $R_c$ could be determined by the intersection of following curves:

$$\begin{array}{cc}& y_1=\frac{Q}{C{N}_{re}+1}{e}^{2\lambda Ar},\\ y_2={\left(1-e^{-\lambda Ar}\right)}^{C{N}_{re}}.\end{array}$$

(35)

According to (32) and (33), the connectivity could be flexibly controlled via radio range adjustment.

(4) Two Kind of Connected Nodes

Definition 15.

The connected nodes can be classified into two categories: (1) nodes within the radio range of the reference node, which is denoted by $\text{IRN}$ ; (2) nodes out of its radio range expressed by $\text{ORN}$ .

An $\text{IRN}$ node is the one which can directly communicate with the reference node. We also separately discussed the left and right side cases of $\text{IRN}$ . Notice that ${\text{IRN}}_{+}$ follows Poisson distribution with parameter $\lambda AR$ and its PMF is

$$\begin{array}{cc}& p\left({\text{IRN}}_{+}=k\right)=\frac{{\left(\lambda AR\right)}^k}{k!}{e}^{-\lambda AR}.\end{array}$$

(36)

In the same way, the $\text{IRN}$ considering both sides could be derived as

$$\begin{array}{cc}& p\left(\text{IRN}=m\right)=\frac{{\left(2\lambda AR\right)}^m}{m!}{e}^{-2\lambda AR}.\end{array}$$

(37)

And the expectation of $\text{IRN}$ is given by

$$\begin{array}{cc}& E\left[\text{IRN}\right]=E\left[{\text{IRN}}_{+}\right]+E\left[{\text{IRN}}_{-}\right]=2\lambda AR.\end{array}$$

(38)

The $\text{ORN}$ indicates the number of nodes beyond the radio range of the reference node and connecting to $X_0$ through multiple hops.

Theorem 16.

The PMF of $OR{N}_{+}$ is

$$\begin{array}{cc}& p\left(OR{N}_{+}=i\right)=\{\begin{array}{cc}{e}^{-\lambda AR}\left(1+\lambda AR\right)\hfill & i=0,\hfill \\ e^{-2\lambda AR}{\left(1-e^{-\lambda AR}\right)}^{i-1}\hfill & \hfill \\ \hspace{1em}\times \left[e^{\lambda AR}-1-\lambda AR\right]\hfill & i\ge 1.\hfill \end{array}\end{array}$$

(39)

Proof.

From (22), (26), and (36), for $i\ge 1$ , we have

$$\begin{array}{l}p\left({\text{ORN}}_{+}=i\right)={\displaystyle \sum }_{k=0}^{\infty }p\left({\text{ORN}}_{+}=i,{\text{IRN}}_{+}=k\right)\\ \phantom{p\left(OR{N}_{+}=i\right)}={\displaystyle \sum }_{k=1}^{\infty }p\left({\text{ORN}}_{+}=i,{\text{IRN}}_{+}=k\right)\\ \phantom{p\left(OR{N}_{+}=i\right)}={\displaystyle \sum }_{k=1}^{\infty }p\left({\text{CN}}_{+}=k+i\right)\\ \phantom{p\left(OR{N}_{+}=i\right)=}\hspace{1em}\hspace{1em}\times p\left({\tau }_k\le R,{\tau }_{k+1}>R\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}=k+i\right),\end{array}$$

(40)

where ${\tau }_k,{\tau }_{k+1}$ represent the sum of the first k and $k+1$ inter-vehicle distances, respectively. Let $H_1,H_2,\dots$ be the inter-vehicle distances and they are IID to each other; that is,

$$\begin{array}{cc}& {\tau }_k=H_1+H_2+\cdots +H_k,\\ {\tau }_{k+1}=H_1+H_2+\cdots +H_k+H_{k+1},\\ {\tau }_{k+1}={\tau }_k+H_{k+1}.\end{array}$$

(41)

When ${\text{CN}}_{+}=k+i$ , the following inequality can be deduced:

$$\begin{array}{cc}& H_p\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}\le R,\hspace{1em}p=\mathrm{1,2},\dots ,k+i.\end{array}$$

(42)

And the PDF of $H_p\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}$ is

$$\begin{array}{cc}& f_{H_p|{\text{CN}}_{+}}\left(h\right)=\frac{\lambda A{e}^{-\lambda Ah}}{1-e^{-\lambda AR}},\hspace{1em}h\in \left[0,R\right].\end{array}$$

(43)

Taking Laplace transform to the above equation, we have

$$\begin{array}{cc}& f_{H_p|{\text{CN}}_{+}}\left(s\right)=\frac{\lambda A}{1-e^{-\lambda AR}}\frac{1-e^{-\left(\lambda A+s\right)R}}{s+\lambda A}.\end{array}$$

(44)

According to the independence of inter-vehicle distances, the following equation can be derived as

$$\begin{array}{cc}& f_{{\tau }_k|{\text{CN}}_{+}}\left(s\right)={\left(\frac{\lambda A}{1-e^{-\lambda AR}}\right)}^k{\left(\frac{1-e^{-(\lambda A+s)R}}{s+\lambda A}\right)}^k.\end{array}$$

(45)

Then the PDF of ${\tau }_k\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}$ is written as

$$\begin{array}{l}{f}_{{\tau }_k\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}}\left(t\right)={\left(\frac{\lambda A}{1-e^{-\lambda AR}}\right)}^k\\ \phantom{f_{{\tau }_k\hspace{0.17em}|\hspace{0.17em}C{N}_{+}}\left(t\right)=}·{\displaystyle \sum }_{j=0}^k{C}_k^j{\left(-1\right)}^j\frac{{\left(t-jR\right)}^{k-1}}{\left(k-1\right)!}{e}^{-\lambda A\left(t-jR\right)}U\left(t-jR\right),\end{array}$$

(46)

where $U(·)$ is a step function.

Meanwhile, the following conditional probability can be obtained as

$$\begin{array}{l}p\left({\tau }_{k+1}>R,{\tau }_k\le R\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}=k+i\right)\\ \hspace{1em}\hspace{1em}={{\displaystyle \int }}_0^{R}p\left(H_{k+1}>R-t\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}=k+i,{\tau }_k=t\right)d{F}_{H\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}}\left(t\right)\\ \hspace{1em}\hspace{1em}={{\displaystyle \int }}_0^R{f}_{{\tau }_k\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}}\left(t\right)dt{{\displaystyle \int }}_{R-t}^R{f}_{H_{k+1}\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}}\left(h\right)dh.\end{array}$$

(47)

With (22), (43), (46), and (47), we have

$$\begin{array}{l}p\left({\text{ORN}}_{+}=i\right)\\ \hspace{1em}={\displaystyle \sum }_{k=1}^{\infty }p\left({\tau }_k\le R,{\tau }_{k+1}>R\hspace{0.17em}|\hspace{0.17em}{\text{CN}}_{+}=k+i\right)\\ \hspace{1em}\hspace{1em}·p\left({\text{CN}}_{+}=k+i\right)\\ \hspace{1em}=e^{-2\lambda AR}{\left(1-e^{-\lambda AR}\right)}^{i-1}\left[e^{\lambda AR}-1-\lambda AR\right].\end{array}$$

(48)

When $i=0$ , we have

$$\begin{array}{l}p\left({\text{ORN}}_{+}=0\right)=1-{\displaystyle \sum }_{i=1}^{\infty }p\left({\text{ORN}}_{+}=i\right)\\ \phantom{p\left({\text{ORN}}_{+}=0\right)}=e^{-\lambda AR}\left(1+\lambda AR\right).\end{array}$$

(49)

Then, the PMF of ${\text{ORN}}_{+}$ is rewritten as (39).

Corollary 17.

The PMF of $ORN$ is expressed as

$$\begin{array}{l}p\left(ORN=m\right)\\ =\{\begin{array}{ll}{e}^{-2\lambda AR}{\left(1+\lambda AR\right)}^2\hfill & m=0,\hfill \\ 2e^{-2\lambda AR}\left(1+\lambda AR\right)\left[1-e^{-\lambda AR}-\lambda AR{e}^{-\lambda AR}\right]\hfill & m=1,\hfill \\ \left(m+1\right)e^{-3\lambda AR}{\left(1-e^{-\lambda AR}\right)}^{m-2}\hfill & \hfill \\ \hspace{1em}\times \left(e^{-\lambda AR}-1-\lambda AR\right)\hfill & \hfill \\ \hspace{1em}·\left(e^{-\lambda AR}-1-\lambda AR+\frac{2\lambda AR{e}^{\lambda AR}}{m+1}\right)\hfill & m\ge 2.\hfill \end{array}\end{array}$$

(50)

Proof.

Through (51), we have

$$\begin{array}{cc}& p(\text{ORN}=m)={\displaystyle \sum }_{i=0}^{m}p\left(\text{OR}{\text{N}}_{-}=m-i,\text{OR}{\text{N}}_{+}=i\right).\end{array}$$

(51)

Corollary 18.

The expectations of $OR{N}_{+}$ and $ORN$ are

$$\begin{array}{cc}& E\left[OR{N}_{+}\right]=e^{\lambda AR}-\lambda AR-1,\\ E\left[ORN\right]=2e^{\lambda AR}-2\lambda AR-2.\end{array}$$

(52)

We define $Hop{s}_{+}$ as a variable indicating the number of needed hops from the reference node to a connected node on $X_0$ ^’s right side and the following inequalities holds

$$\begin{array}{cc}& {Hops}_{+}\le C{N}_{+},\\ E\left[{Hops}_{+}\right]\le E\left[C{N}_{+}\right]=e^{\lambda AR}-1,\\ P\left({Hops}_{+}\ge h\right)\le P\left(C{N}_{+}\ge h\right)={\left(1-e^{-\lambda AR}\right)}^h.\end{array}$$

(53)

4.3. Statistical Model Considering Random Radio Range

If the channel fading is taken into account, the reachable radio range should be reconsidered. Thereupon, the connectivity will also need reexamination. For notion simplicity, we name such variable “radio range” as ERR (equivalent radio range). The $M/G/\infty$ queuing model is introduced to check the connectivity in this case. The traffic still follows a Poisson arrival process. Let $F_R(r)$ be the CDF of the radio range corresponding to the service time in $M/G/\infty$ .

The PDF of the busy period is [27]

$$\begin{array}{cc}& B\left(d\right)=1-{\left(\lambda A\right)}^{-1}{\displaystyle \sum }_{n=1}^{\infty }{\delta }^{\left(n\right)}\left(d\right),\end{array}$$

(54)

where ${\delta }^{(n)}(d)$ is the nth convolution of $\delta (d)$ , and

$$\begin{array}{cc}& \delta \left(d\right)=\lambda A\left[1-F_R\left(d\right)\right]\exp \left\{-\lambda A{{\displaystyle \int }}_0^d\left[1-F_R\left(r\right)\right]dr\right\}.\end{array}$$

(55)

Note that, in our work, route selection is based on the shortest path algorithm. And (54) corresponds to the case that nodes at $[0,d]$ can receive the messages sent from $X_0$ . Indeed, such nodes may not communicate with each other in some cases. Therefore, $B(d)$ cannot be directly taken as the connectivity.

Hereinafter, we define $C^F(x)$ as the instantaneous connectivity with a random fading channel. Similarly, the PDF and CDF of X are rewritten as $f^F(t)$ , $F^F(x)$ under this case. The distances between adjacent vehicles are denoted by $H_i$ ( $i=\mathrm{0,1},\dots$ ) and they are also IID to each other. Here, vehicles may have different ERRs $\{R_i\}$ experiencing different channel fadings.

Theorem 19.

The connectivity for the random radio range case can be expressed as

$$\begin{array}{l}{C}^F\left(x\right)=1-{\displaystyle \sum }_{m=1}^{\infty }{{\displaystyle \int }}_0^{x-a}\cdots {{\displaystyle \int }}_0^{x-a-x_0-\cdots -x_{m-2}}{{\displaystyle \int }}_0^{\infty }‍\\ \phantom{C^F\left(x\right)=}·{\displaystyle \prod }_{i=0}^{m-1}{\left[1-F_R\left(x_i\right)\right]}^2{F}_R\left(x_m\right)d{F}_H\left(x_m\right)\cdots d{F}_H\left(x_0\right),\end{array}$$

(56)

where a denotes the distance between the end node and its nearest relay.

Proof.

We assume that there are m connected nodes on $X_0$ 's right side. It means that the end node is the mth one. Thus, we have

$$\begin{array}{cc}& H_i\le \min \left(R_i,R_{i+1}\right),\hspace{1em}i=0,\dots ,m-1,\\ H_m>R_m.\end{array}$$

(57)

According to the definition of X, then

$$\begin{array}{l}{F}^F\left(x\right)=P\left(X\le x\right)\\ \phantom{F^F\left(x\right)}={\displaystyle \sum }_{m=1}^{\infty }p\left({\displaystyle \sum }_{j=0}^{m-1}{H}_j\le x,H_m>R_m,H_i\le \min \left(R_i,R_{i+1}\right)\right)\\ \phantom{F^F\left(x\right)}={\displaystyle \sum }_{m=1}^{\infty }{{\displaystyle \int }}_0^{x}p\{{\displaystyle \sum }_{j=0}^{m-1}{H}_j\le x,H_i\le \min \left(R_i,R_{i+1}\right),\\ \phantom{F^F\left(x\right)=}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\phantom{{\displaystyle \sum }_{j=0}^{m-1}{H}_j\le x,H_i\le \min \left(R_i,R_{i+1}\right),}{H}_m>R_m\hspace{0.17em}|\hspace{0.17em}{H}_0=x_0\}d{F}_H\left(x_0\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\cdots \\ \phantom{F^F\left(x\right)}={\displaystyle \sum }_{m=1}^{\infty }{{\displaystyle \int }}_0^x\dots {{\displaystyle \int }}_0^{x-x_0-\cdots -x_{m-2}}{{\displaystyle \int }}_0^{\infty }p\{H_i\le \min \left(R_i,R_{i+1}\right),\\ \phantom{F^F\left(x\right)=}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{H}_m>R_m\}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·d{F}_H\left(x_m\right)\cdots d{F}_H\left(x_0\right)\\ \phantom{F^F\left(x\right)}={\displaystyle \sum }_{m=1}^{\infty }{{\displaystyle \int }}_0^x\dots {{\displaystyle \int }}_0^{x-x_0-\cdots -x_{m-2}}{{\displaystyle \int }}_0^{\infty }d{F}_H\left(x_m\right)\cdots d{F}_H\left(x_0\right)\\ \phantom{F^F\left(x\right)=}·{\displaystyle \prod }_{i=0}^{m-2}{\left[1-F_R\left(x_i\right)\right]}^2\left[1-F_R\left(x_{m-1}\right)\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}\times \left[F_R\left(x_m\right)-F_R\left(x_{m-1}\right)\right].\end{array}$$

(58)

The connectivity between the reference node and a given node with $X=x$ is

$$\begin{array}{cc}& C\left(x\right)=1-F^F\left(x-a\right).\end{array}$$

(59)

To reflect the general fading types in vehicular environment, the Rayleigh and lognormal shadowing are introduced in our work. According to [31–33], the corresponding CDF and expectations of the radio range for the above fading models are as follows.

Lemma 20.

The PDF and average ERR of Rayleigh fading are

$$\begin{array}{cc}& F_R\left(r\right)=1-e^{-r^{\alpha }\psi P_{noise}/K{P}_{tx}},\end{array}$$

(60)

$$\begin{array}{cc}& E\left[R\right]=\frac{\mathrm{\Gamma }\left({\alpha }^{-1}\right)}{\alpha }{\left(\frac{K{P}_{tx}}{\psi P_{noise}}\right)}^{1/\alpha }.\end{array}$$

(61)

Lemma 21.

The PDF and average ERR for lognormal shadowing are

$$\begin{array}{cc}& F_R\left(r\right)=\mathrm{\Phi }\left(\frac{\ln \left(r^{\alpha }\psi P_{noise}/K{P}_{tx}\right)}{{\sigma }_s}\right),\end{array}$$

(62)

$$\begin{array}{cc}& E\left[R\right]={\left(\frac{K{P}_{tx}}{\psi P_{noise}}\right)}^{1/\alpha }{e}^{{\sigma }_s^2/2{\alpha }^2},\end{array}$$

(63)

where ${\sigma }_s$ is the standard deviation, and

$$\begin{array}{cc}& \mathrm{\Phi }\left(x\right)={{\displaystyle \int }}_{-\infty }^x\frac{1}{\sqrt{2\pi }}{e}^{-t^2/2}dt.\end{array}$$

(64)

Note that one just discusses the cases under free-flow state, say λ is generally very small. Then, in a Rayleigh fading channel, the pass loss factor could be taken as a constant during the transmission of a frame. Indeed, when λ becomes very large, the above assumption may fail in some cases.

Similar to the analyzing procedure when the radio range is constant, one also investigates some statistical characteristics for random radio range case, that is, probability that a given node is isolated, the area that a message may cover, the probability of the number of connected nodes, and its value for $IRN$ and $ORN$ , respectively.

(1) The Probability That a Given Node Is Isolated. For a fading channel, the number of nodes within R is Poisson distributed with parameter $2\lambda AE[R]$ and can be expressed as

$$\begin{array}{cc}& P_I^F=e^{-2\lambda AE\left[R\right]}.\end{array}$$

(65)

(2) The Area that a Transmitted Message May Cover. Based on [30], we know, the computational complexity of (56) is very high. However, by [27], the expectation value of the coverage area for a sent message is

$$\begin{array}{cc}& E\left[{\text{Cov}}_{+}\right]=\frac{1}{\lambda A{P}_0},\end{array}$$

(66)

where

$$\begin{array}{cc}& P_0\left(t\right)=\exp \left\{-\lambda A{{\displaystyle \int }}_0^t\left(1-F_R\left(r\right)\right)dr\right\},\\ P_0=\underset{t\to \infty }{\lim }{P}_0\left(t\right).\end{array}$$

(67)

The expectations for the area on the right and both sides are, respectively,

$$\begin{array}{cc}& E\left[{\text{Cov}}_{+}\right]=\frac{e^{\lambda AE\left[R\right]}}{\lambda A},\\ E\left[\text{Cov}\right]=\frac{2e^{\lambda AE\left[R\right]}}{\lambda A}.\end{array}$$

(68)

(3) The Probability of the Number of Connected Nodes. As stated in the corresponding parts for constant radio rage case, ${\text{CN}}^F$ , ${\text{CN}}_{+}^F$ , and ${\text{CN}}_{-}^F$ here are the number of connected nodes on both sides, the right and the left, respectively. Then, the probability of ${\text{CN}}_{+}^F$ given radio range of each car is

$$\begin{array}{l}p\left({\text{CN}}_{+}^F=m\hspace{0.17em}|\hspace{0.17em}\left\{R_i\right\}\right)\\ \hspace{1em}\hspace{1em}=p\left(H_i\le \min \left(R_i,R_{i+1}\right),H_m>\min \left(R_m,R_{m+1}\right)\hspace{0.17em}|\hspace{0.17em}\left\{R_i\right\}\right)\\ \hspace{1em}\hspace{1em}=e^{-\lambda A\min (R_m,R_{m+1})}{\displaystyle \prod }_{i=1}^{m-1}\left(1-e^{-\lambda A\min (R_i,R_{i+1})}\right).\end{array}$$

(69)

Because the radio range is a stochastic variable under a random channel, by (69), the number of connected nodes is mainly determined by the nodes with smaller ranges.

If we focus on the nodes which are within the radio range of $X_0$ , the number of them is named $H{N}_{+}$ and its PGF [27] is

$$\begin{array}{l}g\left(s\right)={\displaystyle \sum }_{k=0}^{\infty }{s}^k{{\displaystyle \int }}_0^{\infty }\cdots {{\displaystyle \int }}_0^{\infty }{\displaystyle \prod }_{i=0}^{k-1}{F}_R\left(h_k\right)·\lambda A{e}^{-\lambda A{h}_k}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\{\lambda A{e}^{-\lambda A{h}_i}[F_R\left({\displaystyle \sum }_{j=i}^k{h}_j\right)\\ \phantom{\left({\displaystyle \sum }_{j=i}^k{h}_j\right)}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-F_R\left(h_i\right)]d{h}_i\}d{h}_k.\end{array}$$

(70)

With (70), the PMF, CDF, and expectation expressions could be derived in theory. However, the procedures are actually very computationally complex. Owing to the works by [34, 35], the above statistics could be deduced in a simple way. Suppose that the vehicular arrival process is a Markovian arrival process (MAP) and it is stationary, ergodic, and nonempty. Without loss of generality, we assume that the arrival traffic flow size in MAP is one [27] and nodes enter into this system one by one.

According to [36], $H{N}_{+}$ follows $\text{DPH}({\alpha }_0,\mathbf{I}-{\int }_0^{\infty }{e}^{-\lambda Ar\mathbf{I}}d{F}_R(r))$ , where I is the identity matrix and ${\alpha }_0·\mathbf{1}$ = 1. $\mathbf{1}$ is an all-1 matrix. Thus, the lower bound of $H{N}_{+}$ can be derived as

$$\begin{array}{cc}& \text{LB}\left[E\left(H{N}_{+}\right)\right]=\frac{1}{{{\displaystyle \int }}_0^{\infty }{e}^{-\lambda Ar}d{F}_R\left(r\right)},\end{array}$$

(71)

and the result considering both sides is

$$\begin{array}{cc}& \text{LB}\left[E\left(HN\right)\right]=\frac{2}{{{\displaystyle \int }}_0^{\infty }{e}^{-\lambda Ar}d{F}_R\left(r\right)}.\end{array}$$

(72)

(4) Two Kinds of Connected Nodes. Let ${\text{IRN}}^F$ be the number of nodes within the radio range of $X_0$ . For $m=\mathrm{0,1},\dots$ , the PMF and its expectation, respectively, are

$$\begin{array}{cc}& p\left({\text{IRN}}^F=m\right)=\frac{{\left(2\lambda AE\left[R\right]\right)}^m}{m!}{e}^{-2\lambda AE\left[R\right]},\\ E\left[{\text{IRN}}^F\right]={{\displaystyle \int }}_0^{\infty }E\left[\text{IRN}\left(r\right)\right]d{F}_R\left(r\right)=2\lambda AE\left[R\right].\end{array}$$

(73)

For the number of nodes out of the radio range of $X_0$ , we have

$$\begin{array}{cc}& E\left[{\text{ORN}}^F\right]=E\left[{\text{CN}}^F\right]-E\left[{\text{IRN}}^F\right],\\ E\left[{\text{hops}}^F\right]\le E\left[{\text{CN}}^F\right],\\ P\left({\text{hops}}^F\ge h\right)\le P\left({\text{CN}}^F\ge h\right),\end{array}$$

(74)

where ${\text{hops}}^F$ is the needed number of hops to reach $X_0$ for a sent message.

4.4. Available Connectivity

The connectivity $C(x)$ stated before attempts to evaluate the connection probability between two nodes, either for single-hop broadcasting or for multi-hop relay. However, to completely reflect the connection possibility involving the potential chances, we introduce a new metric, that is, available connectivity, for a node to estimate its communication capability with $X_0$ .

Definition 22.

Available connectivity is defined as a metric to measure the connection possibility for a given node considering the contributions on connections from others.

Let i be an equipped vehicle running on a one-dimensional highway. $\mathrm{AC}(i,t)$ , say the available connectivity, is an instantaneous variable at time t. However, considering the high dynamics and frequently changing topology of VANETs, it is difficult to calculate the available connectivity every second. In addition, to get the available connectivity in a large-scale VANET with hundreds of nodes is still impractical. Thereupon, we introduce two limitations on $\mathrm{AC}(i,t)$ :

Limitation I.

$$\begin{array}{cc}& C\left(x\right)\ge C_{\text{th}}.\end{array}$$

(75)

Limitation II.

$$\begin{array}{cc}& p(\text{hops}\le n)\ge P_{\text{th}},\end{array}$$

(76)

where $C_{\text{th}}$ , $P_{\text{th}}$ denote the lower bound of connectivity and the upper bound of the number of hops.

To make our work practical, we discretize the time continuous variable $\mathrm{AC}(i,t)$ . Let θ be the sampling period, say available connectivity is measured every θ seconds. T is an element of the set $\{0,\theta ,2\theta ,\dots \}$ . Then, the available connectivity for any given node i can be rewritten as $\mathrm{AC}(i,T)$ . In general, a larger value of $\mathrm{AC}(i,T)$ corresponds to a bigger available connectivity. This means there are many potential nodes that could be used as forwarders to reach the destination node. It is worth noting that, instead of considering the connectivity between a given node and the reference node for analysis simplicity, we now focus on any communication pair in the network.

Definition 23.

Available connectivity includes two kinds of dissemination ways, say the direct and indirect. Namely, available connectivity is equal to the arithmetic sum of the direct connectivity and indirect connectivity.

• (i)

Direct connectivity: the connection probabilities between a given node and its $\text{IRNs}$ .

(ii)

Indirect connectivity: the connection probabilities between a given node and its $\text{IRNs}$ .

Theorem 24.

The available connectivity of node i at time T is

$$\begin{array}{cc}& \mathrm{AC}(i,T)={\displaystyle \sum }_{x_{k,T}}{\displaystyle \sum }_{n}p(hops=n,i⟷x_{k,T}),\end{array}$$

(77)

where $x_{k,T}$ are the nodes satisfying Limitations I and II, and $i\leftrightarrow x_{k,T}$ represents that i and $x_{k,T}$ can communicate to each other at time T.

Similarly, we have

$$\begin{array}{cc}& DirCon(i,T)={\displaystyle \sum }_{x_{k,T}}p\left(hops=1,i⟷x_{k,T}\right),\end{array}$$

(78)

where $DirCon(i,T)$ indicates the direct connectivity for i at T. If hops between any two communication pair are larger than 2, we have

$$\begin{array}{cc}& IndCon\left(i,T\right)={\displaystyle \sum }_{x_{k,T}}{\displaystyle \sum }_{n}p\left(hops=n,i⟷x_{k,T}\right),\end{array}$$

(79)

where $IndCon(i,T)$ denotes the indirectly connectivity for i at T.

With (77) and the definition of our available connectivity, we know that the number of hops influences the connection performance significantly. For different applications, the requirements of hop bounds are variously depending on the delay limitation, information generation frequency, energy efficiency, and so forth. Considering the high dynamics in VANETs, larger hops may correspondingly incur intolerable delays, thus resulting in the service failure especially for emergent events. Therefore, a small hop bound is acceptable in VANETs.

When using the shortest path route selection algorithm, the following two corollaries hold.

Corollary 25.

For the case that the radio range is a constant, Limitation I could be rewritten as

$$\begin{array}{cc}& {\left(1-e^{-\lambda AR}\right)}^{hops}\ge P_{th},\end{array}$$

(80)

thus

$$\begin{array}{cc}& hops\le \frac{\ln P_{th}}{\ln \left(1-e^{-\lambda AR}\right)}.\end{array}$$

(81)

Corollary 26.

Similarly, we can derive out the corresponding expression for the case where the radio range is a random variable depending on channel fadings. Consider

$$\begin{array}{cc}& {\displaystyle \prod }_{m=1}^{hops}\left(1-e^{-\lambda A\min \left(R_{m-1},R_m\right)}\right)\le P_{th}.\end{array}$$

(82)

With (82), the probability upper bound of the number of hops could be deduced.

5. Numerical Results

In this section, we will evaluate the performance of our proposed metric and investigate its feasibility and effectiveness with different simulation settings.

5.1. The Relationship between the Connectivity and R, λ, and A

According to (6) and (56), it is noted that the radio range R, the equipped vehicle arrival rate λ, and the speed factor A all have influences on the connectivity. In [37], the author provided some typical values for the expectation and standard deviation for vehicular speed on highway which follow the normal distribution as listed in Table 1. We will also use these settings in our later simulations.

Table 1

Normal-speed statistics.

μ (km/h)	σ (km/h)	A (h/km)
70	21	0.016105
90	27	0.012526
110	33	0.010249
130	39	0.008672
150	45	0.007516

The speed factor A is actually a function of μ and σ. Thus, we will firstly analyze the impact of μ, σ on A. The result is plotted in Figure 6. It is noted that the speed factor decreases when the mean of the velocity increases. In addition, the standard deviation has only a very limited influence on A. For σ, a great increasing of it could only slightly augment the speed factor.

Figure 6

The relationship between speed factor A (hour/km) and the expectation μ (km/hour), the standard deviation σ (km/hour).

The connectivity performance when the radio ranges of all nodes are the same constant is showed in Figure 7. In this simulation scenario, we placed 31 vehicles along a one-dimensional highway and investigated the resulted connectivity for a given node at x with different R (m), λ (vehicles/hour), and A (hour/km).

Figure 7

Connectivity versus x (m) with the radio range R (m), vehicle arrival rate λ (vehicles/hour), and speed factor A (hour/km) changing when all the nodes use the same constant radio range.

From Figure 7, it is noted that when $x>R$ , $C(x)$ decreases with the inter-vehicle distance to the reference node increases. However when $x<R$ , the connectivity will reasonably be 1. Therefore, it can be noticed that all the curves in Figure 7 show a sharp change at $x=R$ where the amplitude of this variation is determined by the values of λ, A, and R. Indeed, any rise of λ or A leads to an increase of $C(x)$ . Meanwhile, a larger radio range improves the connectivity performance greatly as shown in Figure 7. In addition, because A is determined by the mean and standard deviation of the speed, a vehicle with a large A will correspond to a smaller mean and standard deviation. Therefore, with other parameters unchanged, a bigger A will increase the connection probability considering moderate topology change.

As a result, it is noted that the variation of the radio range R will mainly influence the connectivity performance compared to other factors. With this conclusion, a critical radio range could be calculated for transmitting power saving consideration and applied to scenarios with determined connectivity requirements.

5.2. The Isolation Probability

The probability that a given node is isolated plays an important role in VANETs. Usually, it can be used for algorithms concerning clustering forming, relay selection, routing metric, and so forth. To reflect its influence on connectivity, the isolation probability is shown in Figures 8 and 9 based on (17) and (65), where Figure 8 corresponds to the constant radio range case and Figure 9 for the random radio range case. It is noted that in Figure 8, R is still the main influential factor to $P_I$ . Speed factor A is in inverse proportion to the isolation probability where a large A will decrease the isolated possibility for a given node. The reason is the same with Figure 7 that a larger A means a less dynamic network, thus resulting in a relatively stable topology. Additionally, the increase of λ will reduce $P_I$ due to more neighbors available.

Figure 8

The isolation probability considering nodes on both sides for the constant radio range case.

Figure 9

The isolation probability $P_I$ considering nodes on both sides under different channels where A = 0.012526 hour/km, $K{P}_{tx}/(\mathbf{\psi }{P}_{\text{noise}})$ = 3 × 10⁴; (1) deterministic channel, R = 108 m; (2) Rayleigh channel, α = 2.2; (3) shadowing fading channel, α = 2.2, ${\sigma }_s$ = 2.

For random radio range case, we compare the isolation probability under the deterministic, Rayleigh, and shadowing fading channel, respectively, as shown in Figure 9. From this figure and (33), (61), and (63), we notice that the Rayleigh shows the worst performance of $P_I$ while lognormal shadowing seems be suitable to reduce isolations between nodes and the deterministic model has a decent performance in between the other two.

5.3. The Number of Connected Nodes

Based on Theorem 16 and (14), the average tail probability of the number of connected nodes is plotted in Figure 10 for the constant radio range case. It is noted that the speed factor, arrival rate, and radio range all greatly influence the average tail probability. A smaller A, which corresponds to a larger average speed, will decrease the probability of vehicles forming a bigger cluster. The reason is that high mobility will make the network more dynamic and links unstable. As for the arrival rate λ, it seems to be in positive proportion to the average tail probability. In addition, among the three influential factors, radio range still contributes the most, which is consistent with the results from Figures 7 and 8.

Figure 10

The average tail probability of the number of connected nodes for the constant radio range case.

Figure 11 depicts the corresponding average tail probability of the random radio range case. We set $K{P}_{tx}/(\psi P_{\text{noise}})$ to 1.2 × 10⁵, the path loss factor α to 2.2, and the standard deviation for the lognormal shadowing to 2. Curves in Figure 11 show that a large arrival rate and low average velocity both increase the number of connected nodes. Compared to the curves from the lognormal shadowing in Figure 11, the results corresponding to the Rayleigh fading channel all show worse performance when other parameters are the same.

Figure 11

The average tail probability of the number of connected nodes on the right of the reference node for the random radio range case.

5.4. Available Connectivity

In this subsection, we will investigate the performance of our introduced available connectivity metric. For simplicity, the threshold of connectivity and $P_{\text{th}}$ are set to 0.1 and 0.5, respectively. The sampling period to investigate the available connectivity is every 4 seconds.

The performance for the constant radio range case is shown in Figure 12. When setting the arrival rate λ to 500 vehicles/hour, speed factor A to 0.008672 hour/km (corresponding to $\mu =130$ , $\sigma =39$  km/hour), and the radio range R to 200 m, the available connectivity of the reference node within 80 seconds is almost zero. After increasing A to 0.016105, the available connectivity begins to improve. It means that low average velocities lead to high available connectivity. In Figure 12, the radio range and vehicle arrival rate both greatly influence the available connectivity and the radio range is still the main factor, which is consistent with the previous results. A little rise of the radio range leads to a great increasing of the available connectivity. Thus, when traffic flow is sparse, that is, in free-flow state, the better way to improve the available connectivity is increasing the radio range. However, when traffic is dense, growth of radio range may not be a better choice for obtaining available connectivity considering the introduced interferences.

Figure 12

Available connectivity versus t (second) within 80 seconds for the case of constant radio range.

The available connectivity in random fading channels are plotted in Figures 13 and 14, where we set $K{P}_{tx}/(\psi P_{\text{noise}})$ to 1.2 × 10⁵, the path loss factor α to 2.2, and the standard deviation for lognormal shadowing to 2. The available connectivity of the reference node within 80 seconds in Rayleigh fading and lognormal shadowing channel is described in Figure 13. Similar to the results in Figure 12, the curves are approximately straight lines. Besides, high equipped vehicle arrival rate leads to a high available connectivity. For example, the available connectivity is about 9.5 when λ is equal to 500 vehicles/hour, and is about 13 when λ is equal to 700 vehicles/hour when the lognormal shadowing channel is used. Additionally, it can be noticed that a lower average velocity may pose positive impact on the available connectivity. Further, because the average radio range in shadowing channel is greater than that in Rayleigh channel, the available connectivity is higher under the shadowing fading channel.

Figure 13

Available connectivity versus t (seconds) within 80 seconds for the random radio range case.

Figure 14

The impact of hop bounds on the available connectivity under random fading channels.

To show the impact of hop bounds on the available connectivity, the performance from different hop bounds and channel fadings is plotted in Figure 14. Note that the upper bound of hops in Figure 13 is adaptively adjusted according to the average radio range. Because the hop bound is decided by application requirements, we introduce different settings including 5 (correspond to emergency case), 10, and 20 (corresponding to the delay tolerable services) in Rayleigh fading channel and lognormal shadowing channel. As shown in Figure 14, it is noticed that the different hop bounds settings greatly influence the available connectivity and a larger hop bound means a higher available connectivity. Thereupon, hop bounds should also be taken into consideration when designing different applications in VANETs.

6. Conclusion

In this paper, a useful metric, that is, available connectivity has been introduced in VANETs. Our proposed available connectivity comes not only from direct connections from neighbors, but also from the indirect links by multi-hop relay. The elaborate investigations of the related statistical properties of the connectivity have been given to reflect the influential factors and give the important references for applications design. Numerical results show that our proposed available connectivity has many potential relationships with network parameters and may provide important references for future protocols design in VANETs.