An Analytical Approach to Relay Access Delay in Multihop Relay Chain of VANETs

Abstract

On the demand of many applications, vehicle to vehicle (V2V) communications have attracted many researchers’ attentions. In the developments of traffic safety applications based on VANET, the dissemination delay is critical. The dissemination delay of safety messages in the form of text has been studied thoroughly. In contrast, the dissemination delays of video or audio safety messages are just emerging and there are still a lot of things to be done. Considering the poor communication environment of multimedia safety messages dissemination in V2V, the analysis of multimedia message dissemination delay has great significance in the traffic safety applications. By extending and integrating previous achievements of analyzing MAC access delay in video stream dissemination, we proposed a method for modeling the relay access delay of IEEE 802.11p in the multihop relay chain of VANETs. Simulation results showed that the cumulative distribution function, the expectation, and the standard deviation of the relay access delays can be calculated effectively. In addition, the impacts of the number of hops and the length of packets on the relay access delays have been properly evaluated. Our study would open these research issues for discussion, which will contribute to the design and implementation of traffic safety.

1. Introduction

VANETs have recently received great attentions from both academic and industrial communities [1–5]. In VANETs, V2V can provide safety applications which are the primary purpose of vehicular communication technology development [6–9]. In V2V networks, vehicles are equipped with advanced wireless network equipment which has a sizeable bandwidth for multimedia data transmission. In the near future, traffic safety applications can be enhanced by the multimedia safety messages. In a real scenario, the live video streaming from the accident or dangerous situation, such as debris flow, earthquake, mass fire, and explosion occurring, will be more helpful than plain text message for drivers. The driver can make an informed decision based on practical situation for the next action, like moving forward or backward. For example, assume a serious accident happened on the highway followed by major traffic congestion. In this case, the multimedia live information such as image and video streaming from the scene of action can be captured by the lead vehicle and delivered to other vehicles several kilometers away. The live visual information can be easily understood or accepted by the drivers and help them decide if they should proceed or turn around. In more serious emergency scenarios, the multimedia safety messages will assist the victims to prevent the situation from worsening and it will help the appropriate authorities to organize efficient rescue operations.

The live multimedia information must be disseminated as soon as possible in V2V network for road traffic safety. If the multimedia safety messages are not disseminated in time, the severe congestion caused by the accident or the natural disaster will deteriorate fast to an uncontrollable situation. A critical measure for multimedia safety messages delivery over multiple hops to remote vehicles well beyond the visual range is the end-to-end delay [10–13]. To understand the potential for V2V to support such delay-sensitive traffic safety applications, analytical method for end-to-end delay is in demand. The end-to-end delay usually consists of three parts: the packet delayed by data processing, the packet delayed in the queue by scheduling policy, and the packet delayed by the medium accessing [14–19]. The third kind of delay is known as MAC access delay and is much longer than the other two kinds of delays. So MAC access delay is worth discussing deeply, and that is what we focused on in the article.

It is generally known that MAC access delay is determined by both the MAC protocol and the structure of VANET. The most popular wireless networking technology available nowadays for establishing VANET is the IEEE 802.11p [20–22]. Owing to the geometric feature of two lane roadways, vehicles usually drive in sequence in low traffic density as shown in Figure 1. In Figure 1, one is composed of five vehicles and moves from the left to the right. The other is formed by three vehicles and drives from the left to the right. When the vehicles drive to the same direction and communicate with each other, the vehicles will compose a multihop relay chain. It means that the multihop relay chain is a realistic structure of VANETs for multimedia video delivery [10, 23–25]. The main idea behind the multihop relay chain is to make use of intermediate vehicles for relaying the multimedia packets to ensure an efficient message relay with the maximum dissemination distance and the minimum dissemination delay. In such a kind of networks and given limitations in coverage and interference, each intermediate vehicle with two neighbor vehicles in its communication range can realize the maximum dissemination distance and the minimum dissemination delay. This situation, for example, could be as shown in Figure 1. In such a multihop relay chain, vehicle states and channel condition, especially of the number of hops, are the major factors of the MAC access delay of IEEE 802.11p [10, 25–29].

Figure 1

Two multihop relay chains in the two lane roadways.

This paper is a tentative research in this direction, and we extend and integrate the discrete-time Markov models from [30, 31] to analyze the MAC access delay of IEEE 802.11p in multihop relay chain. In Section 2, we review the related work. In Section 3, we present the derivations of the explicit expressions, the expectation, and standard deviation of relay access delay and propose an approximate method to obtain the complementary cumulative distribution function of relay access delay. In Section 4, we validate and discuss the proposed analytical model by comparing calculation result and ns-2 simulation and in Section 5, we conclude the work.

2. Related Work

The delay analysis of the IEEE 802.11p MAC sublayer with the queuing models has been partially investigated in some articles. A performance increase in data packet delivery ratio and decrease in average end-to-end packet delay on a 2-lane motorway were demonstrated in [32, 33]. In [34], Cai et al. considered the behavior of the relay node as a queuing system and represented the service for its own packet transmission as an M/G/1-type Markov chain. In [35], a buffer management and a queuing model were proposed to analyze throughputs and delays in the delay tolerant networks by Niyato et al. Also, some publications concerned the delay of IEEE 802.11p in channel access and wireless propagation. Ma and Chen proposed analytic model accounts for impact of priority access, message arrival interval, hidden terminal, channel fading, and highly mobile on indices in [36]. Agarwal et al. derived both upper and lower bounds on the average message propagation speed by exploiting a connection with the classical pattern-matching problem in probability theory in [37, 38]. Vinel et al. designed a model which explicitly accounted the operation of IEEE 802.11p and computed mean decision delay as a function of number of vehicles, ratio of intruders, and contention window sizes in [39].

According to previous results, network structures can be classified into two groups: multihop relay and single-hop to infrastructure [40–46]. In this paper, we concentrate the attention on relay access delay of IEEE 802.11p in multihop relay chain.

In 2011, Rostamzadeh and Gopalakrishnan proposed a mathematical model for approximating the relationship between message delay and physical distance in a vehicular network [47]. Combining an expression for the number of successful packet transmissions with the estimates of intervehicle spacing, Rostamzadeh and Gopalakrishnan formulated the relationship between the distance traversed by a message and the time taken to traverse this distance [47]. In [47], the transmission delay is fixed for each transmission, and the propagation delay of each hop obeys an exponential distribution. In contrast, we consider that the propagation delay between adjacent vehicles is so little that we can ignore it. Besides that, the main difference between [47] and our research is reflected in the opinions on transmission delay of each hop. The transmission delay of each hop is considered as complex and random in our research. The transmission delay of each hop is considered as consisting of three parts, and the most important one in the three parts is the MAC access delay which is one of our main research contents.

In the same year, Sjöberg et al. evaluated the performance of IEEE 802.11p in terms of the MAC-to-MAC delay, a measure which captured both the reliability and the delay of the delivered data traffic for a varying number of vehicles in one hop [48]. The cumulative distribution function of the MAC-to-MAC delay was depicted by experimentally evaluating the MAC methods of IEEE 802.11p [48]. There are two major distinctions generally differentiated [48] from this paper. First, the performance of MAC-to-MAC delay is not modeled with an analytic method and is only evaluated in experiment in [48]. In this paper, the performance of relay access delay is not only evaluated in different scenarios but also modeled with a theoretical analysis method. This method infers the cumulative distribution function, the expectation, and the standard deviation of relay access delay. Second, the MAC-to-MAC delay, studied thoroughly in [48], is the end-to-end delay for one hop. The relay access delay as our main research object is the end-to-end delay for multihop.

In 2013, Liu et al. investigated modeling and delay analysis of intermittently connected stationary and isolated roadside units [49]. In [49], roadside units experience frequent disruptions in terrestrial application, and mobile vehicles present opportunistic relaying capabilities that promote roadside network connectivity. Information is encapsulated into bundles buffered at the source roadside unit, and vehicles opportunistically transport them to the destination roadside unit [49]. More specifically, theoretical expressions were derived for the estimation of three delay-performance metrics: the bundle queuing delay, transit delay, and end-to-end delivery delay [49]. In the scenario of [49], the information disseminates from source roadside unit to destination roadside unit through vehicles relaying. In this paper, we also study the theoretical expressions of end-to-end delivery delay. However, message is spread from the lead vehicle to the tail vehicle through the middle vehicles relaying. The topics of ours and [49] are the same, but the scenes of the two articles are different.

In 2012, Khabbaz et al. proposed in-depth study on the insights of message delivery delay in VANETs towards the identified two major factors: message delivery distance and density of vehicles, based on a bidirectional vehicle traffic model [50]. In their framework, the reverse traffic was used to disseminate emergency messages with short delivery latency, and the number of vehicles in the reverse direction obeys a Poisson distribution [50]. However, when the severe congestion caused by the accident or the natural disaster takes place on the road, vehicles in the reverse direction will be stopped by the traffic jam and not help deliver the messages. To make it more realistic, we consider that vehicles can only communicate with other vehicles that move in the same direction. The vehicles moving in the same direction can constitute a stable multihop relay chain which is a proper structure in forwarding message along the road to prevent congestion deterioration. In our scenario, a live video streaming will be recorded by the lead vehicle of the multihop relay chain with a driving recorder and propagated to the vehicles in the same direction several miles behind.

3. Analytical Model of Relay Access Delay

In this section, we propose an analytical model for performance evaluations of relay access delay of multihop relay chain. Firstly we derive the vehicular traffic model of multihop relay chain in Section 3.1 followed by derivation of the expression of relay access delay in Section 3.2. In Section 3.3, we demonstrate how to calculate the expectation and variance of relay access delay. In Section 3.4, we propose a method to get the complementary cumulative distribution function of relay access delay which can be used to obtain the probability that relay access delay is greater than the given constraint.

Descriptions of all variables used in the paper are summarized in the Notation Section.

3.1. Vehicular Traffic Model

In this section we will describe the vehicular traffic model which will be used in the following part of this paper. We will then describe the proposed multimedia information dissemination model used to characterize the dissemination process throughout the multihop relay chain. These models will be used in Sections 3.2~3.4 to derive the service capacity model.

The network model is built on a two lane roadways scenario, where vehicles can only communicate with other vehicles which are moving in the same direction. Moreover, assume vehicles are distributed with a sparse density and equipped with driving recorder and car monitor. Vehicles are also equipped with a Global Positioning System (GPS) for positioning and time synchronization purposes. When an accident or dangerous situation (e.g., debris flow, earthquake, mass fire and explosion, terrorist attack damage, etc.) occurs ahead, live video streaming recorded by driving recorder will be propagated from the lead car and sent to the vehicles several miles behind to inform drivers of the problem and allow them to decide if they should proceed or turn around.

Since the multimedia data transmission along the highway is much larger than the range of one hop, we simplify the network as a multihop relay chain as shown in Figure 2. The access to the medium is free of contention in the chain, since the chain is too long to implement centralized management. Transmission in the chain uses an assigned channel to avoid interference from the other serve channel. We also assume that all the vehicles have a fixed and uniform transmission range denoted by M. The spacing between two adjacent vehicles in the chain should be less than M to ensure reliable communication. Moreover, for minimum channel contention, the distance between two nonadjacent vehicles in the chain is as close as possible to M. According to this method, the set of vehicles form a multihop relay chain. When the number of vehicles in such chain is given, video dissemination can be spread further with the less channel competition, because each vehicle in such a chain only has two neighbor vehicles in its transmission range. Moreover, this structure of chain is suitable for the scene described in Figure 2.

Figure 2

One direction relay model scenario in two lane roadways.

As shown in Figure 2, a video stream is relayed along the chain using IEEE 802.11p. In our scenarios, we make several simplified assumptions. First, the lead vehicle of the chain is the only video packet source, and other vehicles carry and forward the video packet sequentially. It means that the intermediate vehicle is only responsible for forwarding the video captured by the leading vehicle and never sends the video captured from itself. Second, we assume that the interference range equals the transmission range. Third, video transmission using an assigned channel is to avoid the interference from another service. The MAC access competition in the assigned channel is only caused by video dissemination. Considering the mechanism of IEEE 802.11P, the MAC access delay caused by MAC access competition is the main ingredient of the delay of video dissemination [30, 31]. From the reviews of the delay of video dissemination in multihop relay chain, an index named “relay access delay” can be proposed to evaluate the total MAC access delay effect of every vehicle. The terms “vehicle” and “node” will be interchangeably used throughout this paper.

3.2. Expression of Relay Access Delay

Let D be the random variable (rv) representing the MAC access delay of each node [32]. In our work, we adopt Sakurai and Vu's approach to get the D of every relay node [32]. For indicating the total effect of D of every relay node, the relay access delay is considered as the sum of D of each node in the multihop relay chain. Let R denote the relay access delay of multihop relay chain. As shown in Figure 2, the relay access delay from node 1 to node n can be expressed as

$$\begin{array}{cc}& R={{\displaystyle \sum }}_{j=\mathrm{1}}^n{D}_j.\end{array}$$

(1)

To obtain R in (1), the calculation of $D_j$ must be solved first. We introduce (2-4) and (6-8) from [32] to get D of each node, and we make some changes in symbol of variable for convenience.

In (2), $D_j$ consists of two parts, $A_j$ and $T_j$ . The constant $T_j$ is equal to $T_s$ in (3), and $T_s$ represents the channel occupancy of a successful transmitted packet [32]:

$$\begin{array}{cc}& D_j=A_j+T_j,\hspace{1em}\mathrm{1}\le j\le n,\end{array}$$

(2)

$$\begin{array}{cc}& T_j=T_s.\end{array}$$

(3)

The rv $A_j$ represents the sum of durations of transmission failure and backoffs involving the tagged node j, and the durations of interruptions by the single-hop neighbors of tagged node j [32]. Because the number of backoff periods depends on the number of retransmissions, the value of $A_j$ strongly depends on the number of retransmissions [32]. Therefore, the rv $A_j$ can be represented as a simple mixture of distributions as described in (4), where each component distribution represents a conditional distribution conditioned on a certain number of retransmissions taking place, and the mixing probabilities are the respective probabilities of the number of retransmissions [32]:

$$\begin{array}{cc}& A_j=A_j^v\hspace{1em}\text{w.p.}\hspace{0.17em}\hspace{0.17em}{\alpha }_j,\hspace{1em}\mathrm{0}\le v\le r-\mathrm{1}.\end{array}$$

(4)

In (4), v is the number of retransmission and $A_j^v$ is $A_j$ when v retransmissions have occurred. The number of retransmissions before success obeys a truncated geometric distribution [32], so that the probability of the vth retransmission of the tagged node j is ${\alpha }_j$ , where “w.p.” in (4) means “with probability”, and r is the maximum backoff stage determined by the IEEE 802.11p. The transmission failure is the only reason that causes node j retransmission, and we therefore have that

$$\begin{array}{cc}& {\alpha }_j=\frac{\left(\mathrm{1}-p_j\right){\left(p_j\right)}^v}{\mathrm{1}-{\left(p_j\right)}^r},\hspace{1em}\mathrm{1}\le j\le n,\end{array}$$

(5)

where $p_j$ is the transmission failure probability of the tagged node j. We can derive $p_j$ from [30, 31] for computing

$$\begin{array}{cc}& A_j^v=\left\{\begin{array}{cc}{\displaystyle \sum }_{w=\mathrm{0}}^v{B}_{j,v}^w+{\displaystyle \sum }_{w=\mathrm{1}}^v{C}_{j,v}^w,\hfill & \mathrm{1}\le v\le r-\mathrm{1},\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le w\le v\hfill \\ B_{j,v}^w,\hfill & v=\mathrm{0},\hspace{0.17em}\hspace{0.17em}w=\mathrm{0},\hfill \end{array}\right.\end{array}$$

(6)

$$\begin{array}{cc}& C_{j,v}^w=T_c.\end{array}$$

(7)

Equation (6) is derived according to the principle of IEEE 802.11p. The time that node j spends in transmitting a packet successfully after v failures is denoted by $A_j^v$ . In IEEE 802.11p, a node monitors the channel activity when it has a new packet to transmit. If the channel is occupied by its neighbor nodes, the node j persists to monitor the channel until it is judged as idle for metric $C_{j,v}^w$ . At this point, the node j generates a random backoff interval before transmitting to minimize the probability of collision with packets being transmitted by other nodes. In (6), $B_{j,v}^w$ expresses a random backoff interval, which represents the time after v transmitting failures of node j.

If node j successfully sends a packet after v failures, node j experiences v transmissions and $v+1$ backoff. In (6), the generic component $A_j^v$ is comprised of $v+1$ backoff intervals, denoted by $B_{j,v}^w$ , and v transmissions, denoted by $C_{j,v}^w$ [32]. The constant $C_{j,v}^w$ accounts for the channel occupancy of a failed transmission which is caused by the collision or the imperfect wireless channel. The rv $B_{j,v}^w$ represents the backoff interval and the corresponding interruptions [32]. The subscripts j, v, and w identify the component that belongs to the wth retransmission of node j before the packet is transmitted successfully in the vth retransmission. Similar to [32], $C_{j,v}^w$ is equal to $T_c$ in (7). $T_c$ represents the channel occupancy of a failed transmission

$$\begin{array}{ll}& B_{j,v}^w=\left\{\begin{array}{ll}{\displaystyle \sum }_{k=\mathrm{1}}^{U^w}\left(t_{\text{slot}}+Y_{j,v,w}^k\right),\hfill & \mathrm{1}\le U^w,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le k\le U^w\hfill \\ \mathrm{0},\hfill & U^w=\mathrm{0},\hfill \end{array}\right.\\ w=\mathrm{0},\dots ,v.\end{array}$$

(8)

In (8), the scope of $B_{j,v}^w$ is defined by a backoff interval that takes a discrete uniform distribution. For simplicity, we assume that each slot in the backoff interval can be interrupted at the start of the slot by a successful transmission or a collision. After an interruption, the backoff slot is assumed to pass without further incident. We also ignore the possibility of the same slot being interrupted more than once, because the probability of multiple interruptions is small.

In (8), because $B_{j,v}^w$ represents the backoff intervals and their interruptions as defined in (6), $B_{j,v}^w$ can be considered as a random sum of the durations of a slot and their interruptions. In (8), an interruption is denoted by $Y_{j,v,w}^k$ , in which the subscripts k, j, v, and w identify the component that belongs to the kth backoff slot in the wth retransmission of node j before the packet is transmitted successfully in the vth retransmission.

According to IEEE 802.11p, the backoff period durations are discrete uniform random variables and given by

$$\begin{array}{cc}& U^w=U\left(\mathrm{0},{\mathrm{2}}^w·W_{\mathrm{0}}-\mathrm{1}\right),\hspace{1em}\mathrm{0}\le w\le v,\end{array}$$

(9)

where U is the uniform distribution and $W_0$ is the initial contention window size defined by IEEE 802.11p.

Equation (10) represents the probability distribution of the interruption $Y_{j,v,w}^k$ , in the kth backoff slot of the wth retransmission of the node j before the packet is transmitted successfully in the vth retransmission. The rv $Y_{j,v,w}^k$ is equal to zero if no single-hop neighbors transmit in the slot. If there are one or more transmissions, the transmission of node j is failure, and $Y_{j,v,w}^k$ equals $T_c$ . If there is only node j transmission, the transmission of node j is successful, and $Y_{j,v,w}^k$ is equal to $T_s$ . The successes and failures of the transmission are both derived at the point of view of the node j

$$\begin{array}{ll}& Y_{j,v,w}^k=\left\{\begin{array}{ll}0\hfill & \text{w.p.}\hspace{0.17em}\left(1-{\tau }_{j-1}\right)·\left(1-{\tau }_{j+1}\right),\hfill \\ T_c\hfill & \text{w.p.}\hspace{0.17em}\hspace{0.17em}{\tau }_{j-1}·p_{j-1}·(1-{\tau }_{j+1})\hfill \\ \hfill & \hspace{1em}\hspace{1em}+\hspace{0.17em}{\tau }_{j+1}·p_{j+1}·(1-{\tau }_{j-1})\hfill \\ \hfill & \hspace{1em}\hspace{1em}+\hspace{0.17em}{\tau }_{j-1}·p_{j-1}·{\tau }_{j+1}·p_{j+1},\hfill \\ T_s\hfill & \text{w.p.}\hspace{0.17em}\hspace{0.17em}{\tau }_{j-1}·(1-p_{j-1})+{\tau }_{j+1}·(1-p_{j+1})\hfill \\ \hfill & \hspace{1em}\hspace{1em}-\hspace{0.17em}{\tau }_{j-1}·\left(1-p_{j-1}\right)·{\tau }_{j+1}·\left(1-p_{j+1}\right),\hfill \end{array}\right.\\ 2\le j\le n-1,\hspace{1em}0\le v\le r-1,\hspace{1em}0\le w\le v,\hspace{1em}1\le k\le U^w.\end{array}$$

(10)

In (10), ${\tau }_{j-\mathrm{1}}$ and ${\tau }_{j+\mathrm{1}}$ are the transmission probability of node $j-1$ and node $j+1$ which are both the single-hop neighbors of node j. We derive τ of every node from [30, 31] directly.

So far, only $T_s$ and $T_c$ have not been calculated. To facilitate the calculation, we ignore the propagation delay. According to the mechanism of IEEE 802.11p [51], we can obtain the expressions of $T_s$ and $T_c$ as

$$\begin{array}{ll}& T_s=t_{\text{RTS}}+t_{\text{SIFS}}+t_{\text{CTS}}+t_{\text{SIFS}}+t_{\text{HEAD}}\\ +t_{\text{LOAD}}+t_{\text{SIFS}}+t_{\text{ACK}}+t_{\text{DIFS}},\\ T_c=t_{\text{RTS}}+t_{\text{DIFS}},\end{array}$$

(11)

where $t_{\text{LOAD}}$ , $t_{\text{HEAD}}$ , $t_{\text{CTS}}$ , $t_{\text{RTS}}$ , $t_{\text{ACK}}$ , $t_{\text{SIFS}}$ , and $t_{\text{DIFS}}$ denote the transmission time of data as the load in packet, header of physical packet, RTS packet, CTS packet, ACK packet, and duration of SIFS and DIFS. The values of these parameters are constants in IEEE 802.11p [51].

From the analysis above, the expressions of $D_j$ , $A_j$ , $A_j^v$ , $B_{j,v}^w$ , and $Y_{j,v,w}^k$ have been given. Substituting (1)–(11) in sequence, we can obtain the expression of R in multihop relay chain.

3.3. Expectation and Standard Deviation of Relay Access Delay

The expectation and the standard deviation of relay access delay, denoted by $E[R]$ and StdDev[R], respectively, can be trivially defined as (12)

$$\begin{array}{cc}& E\left[R\right]={{\displaystyle \sum }}_{j=\mathrm{1}}^{n}E\left[D_j\right],\\ \text{StdDev}\left[R\right]=\sqrt{\left|{{\displaystyle \sum }}_{f,g=\mathrm{1}}^n\text{Cov}\left(D_f,D_g\right)\right|}.\end{array}$$

(12)

When node f and node g are neighbors or have the common neighbor node, the transmission of node f and node g can force adjacent nodes to the backoff stage. Consequently, node f and node g are not independent and have a nonzero cross covariance. It means that $\text{Cov}(D_f,D_g)$ must be considered in different scenarios. The MAC access delays of node f and node g are represented by $D_f$ and $D_g$ , respectively. It makes for more complexity in analyzing $\text{Cov}(D_f,D_g)$ .

Based on (2), we have

$$\begin{array}{ll}& E\left[D_j\right]=E\left[A_j\right]+E\left[T_j\right],\hspace{1em}\mathrm{1}\le j\le n,\\ E\left[D_f·D_g\right]\\ \hspace{1em}\hspace{1em}=E[A_f·A_g]+E\left[T\right](E\left[A_f\right]+E\left[A_g\right])\\ \hspace{1em}\hspace{1em}\hspace{1em}+E{\left[T\right]}^{\mathrm{2}},\hspace{1em}\mathrm{1}\le f\le n,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le g\le n,\\ E\left[D_f\right]·E\left[D_g\right]\\ \hspace{1em}\hspace{1em}=E\left[A_f\right]·E\left[A_g\right]+E\left[T\right](E\left[A_f\right]+E\left[A_g\right])\\ \hspace{1em}\hspace{1em}\hspace{1em}+E{\left[T\right]}^{\mathrm{2}},\hspace{1em}\mathrm{1}\le f\le n,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le g\le n,\\ \text{Cov}\left[D_f,D_g\right]\\ \hspace{1em}\hspace{1em}=E[D_f·D_g]-E\left[D_f\right]·E\left[D_g\right]\\ \hspace{1em}\hspace{1em}=E\left[A_f·A_g\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}-E\left[A_f\right]·E\left[A_g\right],\hspace{1em}\mathrm{1}\le f\le n,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le g\le n.\end{array}$$

(13)

As described in (4) and (5), the rv $A_j$ obeys a truncated geometric distribution and $T_j$ is a constant. Thus, $E[A_j]$ , $E[T_j]$ , and $E[A_f·A_g]$ in (13) can be expressed as

$$\begin{array}{ll}& E\left[A_j\right]={{\displaystyle \sum }}_{v=\mathrm{0}}^{r-\mathrm{1}}\frac{\left(\mathrm{1}-p_j\right){\left(p_j\right)}^v}{\mathrm{1}-{\left(p_j\right)}^r}·E\left[A_j^v\right],\\ E\left[T_j\right]=T_s,\\ E[A_f·A_g]\\ \hspace{1em}={{\displaystyle \sum }}_{v_{\mathrm{1}}=\mathrm{0}}^{r-\mathrm{1}}{{\displaystyle \sum }}_{v_{\mathrm{2}}=\mathrm{0}}^{r-\mathrm{1}}\frac{\left(\mathrm{1}-p_f\right){\left(p_f\right)}^{v_{\mathrm{1}}}}{\mathrm{1}-p_f^r}·\frac{\left(\mathrm{1}-p_g\right){\left(p_g\right)}^{v_{\mathrm{2}}}}{\mathrm{1}-p_g^r}\\ \hspace{1em}\hspace{1em}·E\left[A_f^{v_{\mathrm{1}}}·A_g^{v_{\mathrm{2}}}\right],\end{array}$$

(14)

where $E[A_f·A_g]$ can be regarded as the expectation of the product of $A_f$ and $A_g$ . The superscripts $v_1$ and $v_2$ indicate that node f and node g transmit the packet successfully in the $v_1$ th and $v_2$ th retransmission, respectively. At any given time, node f and node g can stay in any backoff stages, before they transmit the packet successfully.

Given (6), $E[A_j^v]$ and $E[A_f^{v_1}·A_g^{v_2}]$ in (14) can be obtained as

$$\begin{array}{ll}& E\left[A_j^v\right]={{\displaystyle \sum }}_{w=\mathrm{0}}^{v}E\left[B_{j,v}^w\right]+v·E\left[C_{j,v}^w\right],\\ E[A_f^{v_{\mathrm{1}}}·A_g^{v_{\mathrm{2}}}]\\ ={{\displaystyle \sum }}_{w_{\mathrm{1}}=\mathrm{0}\begin{array}{l}\end{array}}^{v_{\mathrm{1}}}{{\displaystyle \sum }}_{w_{\mathrm{2}}=\mathrm{0}}^{v_{\mathrm{2}}}E[B_{f,v_{\mathrm{1}}}^{w_{\mathrm{1}}}·B_{g,v_{\mathrm{2}}}^{w_{\mathrm{2}}}]+v_{\mathrm{2}}·E\left[C_{g,v_{\mathrm{2}}}^{w_{\mathrm{2}}}\right]·{{\displaystyle \sum }}_{w_{\mathrm{1}}=\mathrm{0}}^{v_{\mathrm{1}}}E\left[B_{f,v_{\mathrm{1}}}^{w_{\mathrm{1}}}\right]\\ \hspace{1em}+v_{\mathrm{1}}·v_{\mathrm{2}}·E\left[C_{f,v_{\mathrm{1}}}^{w_{\mathrm{1}}}\right]·E\left[C_{g,v_{\mathrm{2}}}^{w_{\mathrm{2}}}\right]+v_{\mathrm{1}}·E\left[C_{f,v_{\mathrm{1}}}^{w_{\mathrm{1}}}\right]\\ \hspace{1em}·{{\displaystyle \sum }}_{w_{\mathrm{2}}=\mathrm{0}}^{v_{\mathrm{2}}}E\left[B_{g,v_{\mathrm{2}}}^{w_{\mathrm{2}}}\right],\end{array}$$

(15)

where $B_{j,v}^w$ are independent identically distributed in w for fixed v of the node j. The changeable w denotes the diverse backoff stages of the node j. The superscripts $w_1$ and $w_2$ indicate the $w_1$ th and $w_2$ th backoff stages for fixed $v_1$ and $v_2$ of node f and node g, respectively.

Considering (7) and (8), $E[B_{j,v}^w],\hspace{0.17em}\hspace{0.17em}E[C_{j,v}^w]$ , and $E[B_{f,v_1}^{w_1}·B_{g,v_2}^{w_2}]$ in (15) can be derived as

$$\begin{array}{ll}& E\left[B_{j,v}^w\right]=\left(t_{\text{slot}}+E\left[Y_{j,v,w}^k\right]\right)·E\left[U^w\right],\\ E\left[C_{j,v}^w\right]=T_c,\\ E\left[B_{f,v_1}^{w_1}·B_{g,v_2}^{w_2}\right]\\ =E\left[U^{w_2}\right]·E\left[U^{w_1}\right]\\ \hspace{1em}·\left(\phantom{\left(E\left[{Y_{f,v_{\mathrm{1}},w}^{k_{\mathrm{1}}}}_{\mathrm{1}}\right]+E\left[Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\right)}E\left[{Y_{f,v_{\mathrm{1}},w}^{k_{\mathrm{1}}}}_{\mathrm{1}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left.t_{\text{slot}}·\left(E\left[{Y_{f,v_{\mathrm{1}},w}^{k_{\mathrm{1}}}}_{\mathrm{1}}\right]+E\left[Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\right)+{\left(t_{\text{slot}}\right)}^{\mathrm{2}}\right).\end{array}$$

(16)

From (9)–(11), $E[U^w]$ and $E[Y_{j,v,w}^k]$ in (16) can be expressed as

$$\begin{array}{ll}& E\left[U^w\right]=\frac{{\mathrm{2}}^w·W_{\mathrm{0}}-\mathrm{1}}{\mathrm{2}},\\ E\left[Y_{j,v,w}^k\right]=T_c·\left({\tau }_{j-\mathrm{1}}·p_{j-\mathrm{1}}·\left(\mathrm{1}-{\tau }_{j+\mathrm{1}}\right)+{\tau }_{j+\mathrm{1}}·p_{j+\mathrm{1}}\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}·\left.\left(\mathrm{1}-{\tau }_{j-\mathrm{1}}\right)+{\tau }_{j-\mathrm{1}}·p_{j-\mathrm{1}}·{\tau }_{j+\mathrm{1}}·p_{j+\mathrm{1}}\right)\\ +T_s·\left({\tau }_{j-\mathrm{1}}·\left(\mathrm{1}-p_{j-\mathrm{1}}\right)+{\tau }_{j+\mathrm{1}}·(\mathrm{1}-p_{j+\mathrm{1}})\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-\left.{\tau }_{j-\mathrm{1}}·\left(\mathrm{1}-p_{j-\mathrm{1}}\right)·{\tau }_{j+\mathrm{1}}·\left(\mathrm{1}-p_{j+\mathrm{1}}\right)\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}\hspace{0.17em}\hspace{0.17em}\begin{array}{l}\mathrm{2}\le j\le n-\mathrm{1}\end{array},\\ E\left[Y_{j,v,w}^k\right]=\left(T_c-T_s\right)·{\tau }_{\mathrm{2}}·p_{\mathrm{2}}+T_s·{\tau }_{\mathrm{2}},\hspace{1em}j=\mathrm{1},\\ E\left[Y_{j,v,w}^k\right]=\left(T_c-T_s\right)·{\tau }_{n-\mathrm{1}}·p_{n-\mathrm{1}}+T_s·{\tau }_{n-\mathrm{1}},\hspace{1em}j=n.\end{array}$$

(17)

To calculate $E[Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}]$ in (16), the detailed expressions of the probability distribution of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ are critical. We can consider $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ as a whole discrete random variable. The superscripts $k_1$ and $k_2$ indicate the $k_1$ th and $k_2$ th backoff slot in the $w_1$ th and $w_2$ th backoff stage, before node f and node g transmit the packet successfully in the $v_1$ th and $v_2$ th retransmission, respectively.

Because the backoff slot in the backoff stage of every node is determined by the interruption from the other node, the relation between $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}$ and $Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is different under the interruption pattern between node j and node g. The interruption pattern between node j and node g in the multihop relay chain can be divided into three kinds according to the relative spatial position. $(1)$ In the first scenario, node j and node g are single-hop neighbors to each other, as shown in Figure 3. $(2)$ In the second scenario, node j and node g are double-hop neighbors to each other, as illustrated in Figure 4. $(3)$ In the third scenario, there are more than two nodes between node j and node g, as demonstrated in Figure 5.

Figure 3

In the first scenario, node f and node g are one-hop neighbors to each other.

Figure 4

In the second scenario, node f and node g are double-hop neighbors to each other.

Figure 5

In the third scenario, there are more than two nodes between node j and node g.

The probability distribution of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ and $E[Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}]$ in each pattern will be given in the following analysis.

3.3.1. The First Scenario

Consider

$$\begin{array}{ll}& Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}\\ =\left\{\begin{array}{l}\begin{array}{ll}0& \text{w.p.}\hspace{0.17em}\hspace{0.17em}1-{\tau }_{f-1}·{\tau }_{g+1}\\ T_c^2\phantom{\frac{1}{1}}& \text{w.p.}\hspace{0.17em}\hspace{0.17em}{\tau }_{f-1}·{\tau }_{g+1}·p_{f-1}·p_{g+1}\\ T_s^2& \text{w.p.}\hspace{0.17em}\hspace{0.17em}{\tau }_{f-1}·{\tau }_{g+1}·\left(1-p_{f-1}\right)·\left(1-p_{g+1}\right)\\ T_c·T_s& \text{w.p.}\hspace{0.17em}\hspace{0.17em}{\tau }_{f-1}·{\tau }_{g+1}\\ & \hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.5em}·\left(p_{f-1}+p_{g+1}-2·p_{f-1}·p_{g+1}\right),\end{array}\end{array}\right.\\ \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}g-f=1,\hspace{1em}2\le g\le n-1,\hspace{1em}2\le f\le n-1.\end{array}$$

(18)

In (18), the discrete probability distribution of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is expressed, when node f and node g are single-hop neighbors. When $g-f=1$ , $2\le g\le n-1$ and $2\le f\le n-1$ , node f and node g are single-hop neighbors, as shown in Figure 3.

Consider that $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is the product of two discrete random variables $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}$ and $Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ , so $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is also a discrete random variable. The possible values of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ are zero, $T_c$ , $T_s$ , and $T_c·T_s$ . In Figure 3, because $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ means that node f and node g are one-hop neighbors to each other, they cannot send any packet to interrupt each other. In particular, node f can only be interrupted by node $f-1$ , and node g can only be interrupted by node $g+1$ .

In (18), ${\tau }_{f-\mathrm{1}}$ and ${\tau }_{g+\mathrm{1}}$ are the transmission probabilities of node $f-1$ and node $g+1$ , respectively. Moreover, $p_{f-\mathrm{1}}$ and $p_{g+\mathrm{1}}$ are the transmission failure probabilities of node $f-1$ and node $g+1$ , respectively. In (18), the four possible values of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ can be assigned as follows. (1) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=\mathrm{0}$ , where channel is idle, so node f and node g are both uninterrupted. (2) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_c^{\mathrm{2}}$ , where node f is interrupted by a failure transmission of node $f-1$ , at the same time, node g is interrupted by a failure transmission of node $g+1$ . (3) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_s^{\mathrm{2}}$ , where node f is interrupted by a successful transmission of node $f-1$ ; simultaneously, node g is interrupted by a successful transmission of node $g+1$ . (4) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_s·T_c$ , where either of node f or node g is interrupted by a failure transmission, and in the meantime, the other is interrupted by a successful transmission.

When $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ follows the probability distribution in (18), the expectation of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is given as

$$\begin{array}{l}E\left[Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\\ =T_c^{\mathrm{2}}·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}\\ \hspace{1em}+T_s^{\mathrm{2}}·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})·(\mathrm{1}-p_{g+\mathrm{1}})\\ \hspace{1em}+T_c·T_s·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·\left(p_{f-\mathrm{1}}+p_{g+\mathrm{1}}-\mathrm{2}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}\right),\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}g-f=\mathrm{1}\hspace{1em}\mathrm{2}\le g\le n-\mathrm{1}\hspace{1em}\mathrm{2}\le f\le n-\mathrm{1}.\end{array}$$

(19)

In (19), we derive the expectation of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ in Figure 3. Because $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is a discrete random variable and follows the probability distribution in (18), the definition of expectation in probability theory is applied to structure (19).

3.3.2. The Second Scenario

Consider

$$\begin{array}{l}{Y}_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\\ =\left\{\begin{array}{ll}\mathrm{0}\phantom{\frac{1}{1}}\hfill & \text{w.p.}\hspace{0.17em}\left\{(\mathrm{1}-{\tau }_{f+\mathrm{1}})·(\mathrm{1}-{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}})\right\}\hfill \\ T_c^{\mathrm{2}}\hfill & \text{w.p.}\hspace{0.17em}\left\{(\mathrm{1}-{\tau }_{f+\mathrm{1}})·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}\right.\hfill \\ \hfill & \hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}+\hspace{0.17em}{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{1em}·({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}+\mathrm{1}-{\tau }_{f-\mathrm{1}})\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}\left.·({\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}+\mathrm{1}-{\tau }_{g+\mathrm{1}})\right\}\hfill \\ T_s^{\mathrm{2}}\hfill & \text{w.p.}\hspace{0.17em}\left\{(\mathrm{1}-{\tau }_{f+\mathrm{1}}+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}})\right.\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})·(\mathrm{1}-p_{g+\mathrm{1}})\hfill \\ \hfill & \hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}\left.+\hspace{0.17em}{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right\}\hfill \\ T_c·T_s\hfill & \text{w.p.}\hspace{0.17em}\left\{\left(\mathrm{1}-{\tau }_{f+\mathrm{1}}\right)·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}\right.\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}·\left(p_{f-\mathrm{1}}+p_{g+\mathrm{1}}-\mathrm{2}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}+\hspace{0.17em}{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}·{\tau }_{f-\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right)\hfill \\ \hfill & \hspace{0.5em}\hspace{1em}\hspace{1em}\hspace{1em}·\left({\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}+\mathrm{1}-{\tau }_{g+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}+\hspace{0.17em}{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}·{\tau }_{g+\mathrm{1}}·\left(\mathrm{1}-p_{g+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{1em}\left.·\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}+\mathrm{1}-{\tau }_{f-\mathrm{1}}\right)\right\},\hfill \end{array}\right.\\ \hspace{1em}\hspace{1em}g-f=\mathrm{2},\hspace{1em}\mathrm{2}\le g\le n-\mathrm{1},\hspace{1em}\mathrm{2}\le f\le n-\mathrm{1}.\end{array}$$

(20)

As shown in Figure 4, when $g-f=2$ , $2\le g\le n-1$ and $2\le f\le n-1$ , node f and node g have a common single-hop neighbor node $f+1$ . Specifically, node f and node g can be interrupted by node $f+1$ simultaneously, and they also can be interrupted by node $f-1$ and node $g+1$ , respectively. The probability distribution of   $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ is given in (20).

In (20), ${\tau }_{f-\mathrm{1}}$ , ${\tau }_{f+\mathrm{1}}$ , and ${\tau }_{g+\mathrm{1}}$ are the transmission probabilities of node $f-1$ , node $f+1$ , and node $g+1$ . In addition, $p_{f-\mathrm{1}}$ , $p_{f+\mathrm{1}}$ , and $p_{g+\mathrm{1}}$ are the transmission failure probabilities of node $f-1$ , node $f+1$ , and node $g+1$ . The zero, $T_c$ , $T_s$ , and $T_c·T_s$ are the four possible values of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ . The four values of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ can be allocated as follows. (1) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=\mathrm{0}$ , where channel is idle, and therefore node f and node g are both uninterrupted. (2) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_c^{\mathrm{2}}$ , where node f and node g are both interrupted by the failure transmission of node $f+1$ ; otherwise, node f and node g are interrupted by the failure transmission of node $f-1$ and node $g+1$ , respectively. (3) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_s^{\mathrm{2}}$ , where node f and node g are both interrupted by the successful transmission of node $f+1$ ; otherwise, node f and node g are interrupted by the successful transmission of node $f-1$ and node $g+1$ , respectively. (4) $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}=T_s·T_c$ , where either node f or node g is interrupted by a failure transmission, and in the meantime, the other is interrupted by a successful transmission.

When $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ follows the probability distribution in (20), the expectation of $Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}$ can be calculated as

$$\begin{array}{ll}& E\left[Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\\ =T_c^{\mathrm{2}}·\left\{(\mathrm{1}-{\tau }_{f+\mathrm{1}})·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right.\\ \left.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}+\mathrm{1}-{\tau }_{f-\mathrm{1}})·({\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}+\mathrm{1}-{\tau }_{g+\mathrm{1}})\right\}\\ \hspace{1em}+T_s^{\mathrm{2}}·\left\{\left(\mathrm{1}-{\tau }_{f+\mathrm{1}}+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right)·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right)\right.\\ \left.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left(\mathrm{1}-p_{g+\mathrm{1}}\right)+{\tau }_{f+\mathrm{1}}·\left(\mathrm{1}-p_{f+\mathrm{1}}\right)\right\}\\ \hspace{1em}+T_c·T_s·\left\{\left(\mathrm{1}-{\tau }_{f+\mathrm{1}}\right)·{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left(p_{f-\mathrm{1}}+p_{g+\mathrm{1}}-\mathrm{2}·p_{f-\mathrm{1}}·p_{g+\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}·{\tau }_{f-\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left({\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}+\mathrm{1}-{\tau }_{g+\mathrm{1}}\right)+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}·{\tau }_{g+\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left.\left(\mathrm{1}-p_{g+\mathrm{1}}\right)·\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}+\mathrm{1}-{\tau }_{f-\mathrm{1}}\right)\right\},\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}g-f=\mathrm{2},\hspace{1em}\mathrm{2}\le g\le n-\mathrm{1},\hspace{1em}\mathrm{2}\le f\le n-\mathrm{1}.\end{array}$$

(21)

In (21), we derive the expectation of $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ in Figure 4. Since $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ is a discrete random variable and follows the probability distribution in (20), the definition of expectation in probability theory is used to structure (21).

3.3.3. The Third Scenario

Consider

$$\begin{array}{ll}& Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\\ =\left\{\begin{array}{l}\begin{array}{ll}\mathrm{0}\hfill & \text{w.p.\hspace{0.17em}}\left\{\mathrm{1}-{\tau }_{f-\mathrm{1}}·{\tau }_{g+\mathrm{1}}-{\tau }_{f+\mathrm{1}}·{\tau }_{g-\mathrm{1}}-{\tau }_{f+\mathrm{1}}·{\tau }_{g+\mathrm{1}}\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}-\hspace{0.17em}{\tau }_{f-\mathrm{1}}·{\tau }_{g-\mathrm{1}}+{\tau }_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·{\tau }_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}+\hspace{0.17em}{\tau }_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·{\tau }_{g-\mathrm{1}}+{\tau }_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·{\tau }_{g+\mathrm{1}}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\left.+\hspace{0.17em}{\tau }_{f-\mathrm{1}}·{\tau }_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}+{\tau }_{f+\mathrm{1}}·{\tau }_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}\right\}\hfill \\ T_c^{\mathrm{2}}\hfill & \text{w.p.\hspace{0.17em}}\left\{\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·(\mathrm{1}-{\tau }_{f+\mathrm{1}})+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right.\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.·(\mathrm{1}-{\tau }_{f-\mathrm{1}})+{\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}·\left({\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·(\mathrm{1}-{\tau }_{g+\mathrm{1}})+{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.\left.·(\mathrm{1}-{\tau }_{g-\mathrm{1}})+{\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right)\right\}\hfill \\ T_s^{\mathrm{2}}\hfill & \text{w.p.\hspace{0.17em}}\left\{\left({\tau }_{f-\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})+{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right.\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.-\hspace{0.17em}{\tau }_{f-\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})·{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{0.17em}·\left({\tau }_{g-\mathrm{1}}·(\mathrm{1}-p_{g-\mathrm{1}})+{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{g+\mathrm{1}})\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.\left.-\hspace{0.17em}{\tau }_{g-\mathrm{1}}·(\mathrm{1}-p_{g-\mathrm{1}})·{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{g+\mathrm{1}})\right)\right\}\hfill \\ T_c·T_s\hfill & \text{w.p.\hspace{0.17em}}\left\{\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·(\mathrm{1}-{\tau }_{f+\mathrm{1}})+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right.\right.\text{\hspace{0.17em}<!--?layout cmd="vspace" value="6"?-->}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.·(\mathrm{1}-{\tau }_{f-\mathrm{1}})+{\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}·\left({\tau }_{g-\mathrm{1}}·(\mathrm{1}-p_{g-\mathrm{1}})+{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{g+\mathrm{1}})\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\left.-\hspace{0.17em}{\tau }_{g-\mathrm{1}}·(\mathrm{1}-p_{g-\mathrm{1}})·{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{g+\mathrm{1}})\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}+\left({\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·(\mathrm{1}-{\tau }_{g+\mathrm{1}})+{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right.\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{0.17em}\left.·(\mathrm{1}-{\tau }_{g-\mathrm{1}})+{\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right)\hfill \\ \hfill & \hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{1em}·\left({\tau }_{f-\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})+{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right.\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-\hspace{0.17em}{\tau }_{f-\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right),\hfill \\ \hfill & \hspace{1em}\hspace{0.5em}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{0.17em}\left.·\left.{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right)\right\},\hfill \end{array}\end{array}\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{0.17em}g-f\ge \mathrm{3},\hspace{1em}\mathrm{2}\le g\le n-\mathrm{1},\hspace{1em}\mathrm{2}\le f\le n-\mathrm{1}.\end{array}$$

(22)

When $g-f\ge 3$ , $2\le g\le n-1$ and $2\le f\le n-1$ , node f and node g have their own two single-hop neighbors, as shown in Figure 5. More specifically, node f only can be interrupted by node $f-1$ and node $f+1$ , and node g only can be interrupted by node $g-1$ and node $g+1$ . We define the probability distribution of $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ defined in (22).

In (22), ${\tau }_{f-1}$ , ${\tau }_{f+1}$ , ${\tau }_{g-1}$ , and ${\tau }_{g+1}$ are the transmission probabilities of node $f-1$ , node $f+1$ , node $g-1$ , and node $g+1$ . Furthermore, $p_{f-1}$ , $p_{f+1}$ , $p_{g-1}$ , and $p_{g+1}$ are the transmission failure probabilities of node $f-1$ , node $f+1$ , node $g-1$ , and node $g+1$ . The four values of $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ can be assigned as follows. $(1)\hspace{0.17em}\hspace{0.17em}{Y}_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}=0$ , where channel is idle; therefore, node f and node g are both uninterrupted. $(2)\hspace{0.17em}\hspace{0.17em}{Y}_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}=T_c^2$ , where node f is interrupted by a failure transmission of node $f-1$ or node $f+1$ , and at the same time, node g is interrupted by a failure transmission of node $g-1$ or node $g+1$ . $(3)\hspace{0.17em}\hspace{0.17em}{Y}_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}=T_s^2$ , where node f is interrupted by a successful transmission of node $f-1$ or node $f+1$ , and in the meanwhile node g is interrupted by a successful transmission of node $g-1$ or node $g+1$ . $(4)\hspace{0.17em}\hspace{0.17em}{Y}_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}=T_s·T_c$ , where either node f or node g is interrupted by a failure transmission of its one-hop neighbors, and in the meantime the other is interrupted by a successful transmission of its one-hop neighbors.

When the discrete rv $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ follows the probability distribution in (22), $E[Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}]$ is computed as

$$\begin{array}{ll}& E\left[Y_{f,v_{\mathrm{1}},w_{\mathrm{1}}}^{k_{\mathrm{1}}}·Y_{g,v_{\mathrm{2}},w_{\mathrm{2}}}^{k_{\mathrm{2}}}\right]\\ =T_c^{\mathrm{2}}·\left\{\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·(\mathrm{1}-{\tau }_{f+\mathrm{1}})+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}·(\mathrm{1}-{\tau }_{f-\mathrm{1}})\right.\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.+{\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left({\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·(\mathrm{1}-{\tau }_{g+\mathrm{1}})+{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}·(\mathrm{1}-{\tau }_{g-\mathrm{1}})\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{0.5em}\left.\left.+{\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right)\right\}\\ \hspace{1em}+T_s^{\mathrm{2}}·\left\{\left({\tau }_{f-\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})+{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right.\right.\\ \left.\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-{\tau }_{f-\mathrm{1}}·(\mathrm{1}-p_{f-\mathrm{1}})·{\tau }_{f+\mathrm{1}}·(\mathrm{1}-p_{f+\mathrm{1}})\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left({\tau }_{g-\mathrm{1}}·(\mathrm{1}-p_{g-\mathrm{1}})+{\tau }_{g+\mathrm{1}}·(\mathrm{1}-p_{g+\mathrm{1}})\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.\left.-{\tau }_{g-\mathrm{1}}·\left(\mathrm{1}-p_{g-\mathrm{1}}\right)·{\tau }_{g+\mathrm{1}}·\left(\mathrm{1}-p_{g+\mathrm{1}}\right)\right)\right\}\\ \hspace{1em}+T_c·T_s·\left\{\left({\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·\left(\mathrm{1}-{\tau }_{f+\mathrm{1}}\right)+{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right.\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.·\left(\mathrm{1}-{\tau }_{f-\mathrm{1}}\right)+{\tau }_{f-\mathrm{1}}·p_{f-\mathrm{1}}·{\tau }_{f+\mathrm{1}}·p_{f+\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\left({\tau }_{g-\mathrm{1}}·\left(\mathrm{1}-p_{g-\mathrm{1}}\right)+{\tau }_{g+\mathrm{1}}·\left(\mathrm{1}-p_{g+\mathrm{1}}\right)\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.-{\tau }_{g-\mathrm{1}}·\left(\mathrm{1}-p_{g-\mathrm{1}}\right)·{\tau }_{g+\mathrm{1}}·\left(\mathrm{1}-p_{g+\mathrm{1}}\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}+\left({\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·\left(\mathrm{1}-{\tau }_{g+\mathrm{1}}\right)+{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.·\left(\mathrm{1}-{\tau }_{g-\mathrm{1}}\right)+{\tau }_{g-\mathrm{1}}·p_{g-\mathrm{1}}·{\tau }_{g+\mathrm{1}}·p_{g+\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}·\left({\tau }_{f-\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right)+{\tau }_{f+\mathrm{1}}·\left(\mathrm{1}-p_{f+\mathrm{1}}\right)\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.\left.-{\tau }_{f-\mathrm{1}}·\left(\mathrm{1}-p_{f-\mathrm{1}}\right)·{\tau }_{f+\mathrm{1}}·\left(\mathrm{1}-p_{f+\mathrm{1}}\right)\right)\right\},\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}g-f\ge \mathrm{3},\hspace{1em}\mathrm{2}\le g\le n-\mathrm{1},\hspace{1em}\mathrm{2}\le f\le n-\mathrm{1}.\end{array}$$

(23)

In (23), we derive the expectation of $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ in Figure 5. We consider that $Y_{f,v_1,w_1}^{k_1}·Y_{g,v_2,w_2}^{k_2}$ is a discrete random variable and follows the probability distribution in (22), so we apply the definition of expectation in probability theory to obtain (23).

From (13)–(23), we can finally obtain $E[R]$ and StdDev $[R]$ in (12), which indicates the expectation and the standard deviation of the relay access delay in multihop relay chain.

3.4. Complementary Cumulative Distribution Function of Relay Access Delay

In a multihop relay chain, the probability that R is greater than the given constraint in delay sensitive applications is usually concerned. Hence, the complementary cumulative distribution function (CCDF) of R can be defined as

$$\begin{array}{cc}& \begin{array}{cc}\text{CCDF}& \mathrm{Pr}\{c\le R<\infty \}=F\left(\infty \right)-F\left(c\right).\end{array}\end{array}$$

(24)

The relay access delay R is a discrete random variable, because the values of $D_j$ , $A_j$ , $T_s$ , $A_j^v$ , $B_{j,v}^w$ , $C_{j,v}^w$ , $T_c$ , $Y_{j,v,w}^k$ , $t_{\text{slot}}$ , $t_{\text{LOAD}}$ , $t_{\text{SIFS}}$ , $t_{\text{ACK}}$ , and $t_{\text{DIFS}}$ are all discrete. We define the probability mass function (PMF), cumulative distribution function (CDF), and characteristic function (CF) of the discrete rv R as follows:

$$\begin{array}{ll}& \text{PMF}\hspace{1em}\mathrm{Pr}\left\{R=a_k\right\},\hspace{1em}k=\mathrm{1,2},\dots ,\infty ,\hspace{0.17em}\hspace{0.17em}\mathrm{0}<a_k<\infty ,\end{array}$$

(25)

$$\begin{array}{ll}& \text{CDF}\hspace{1em}\mathrm{Pr}=\{\mathrm{0}<R\le c\}=F\left(c\right)\\ ={{\displaystyle \sum }}_{a_k\le c}\mathrm{Pr}\left\{R=a_k\right\},\hspace{1em}\mathrm{0}<a_k<c<\infty ,\end{array}$$

(26)

$$\begin{array}{ll}& \text{CF}\hspace{1em}\phi \left(t\right)={\displaystyle \sum }_{k=\mathrm{1}}^{\infty }{e}^{i·t·a_k}·\mathrm{Pr}\left\{R=a_k\right\},\hspace{1em}i=\sqrt{-\mathrm{1}}\begin{array}{l}\end{array},\hspace{0.17em}\hspace{0.17em}\mathrm{0}<a_k<\infty .\end{array}$$

(27)

The CCDF of R cannot be used directly according to (24), because the PMF of R is unknown. However, we can obtain the CCDF of R from the CF of R via the inversion theorem proposed by Gil-Pelaez in [52]. On the basis of inversion theorem in [52], we can get

$$\begin{array}{ll}& F\left(\infty \right)-F\left(c\right)\\ \hspace{1em}\hspace{1em}=\underset{\tau \to \infty }{\lim }\frac{1}{2\pi }{{\displaystyle \int }}_{-\tau }^{\tau }\frac{e^{-i·t·c}-e^{-i·t·\infty }}{i·t}\phi \left(t\right)dt,\hspace{1em}i=\sqrt{-\mathrm{1}}.\end{array}$$

(28)

When the inversion theorem as denoted in (28) is introduced, the next major task is to get the expression of $\phi (t)$ which has been defined in (27) and represents the CF of R.

The whole method of getting the CCDF of R from the CF of R can be divided into four steps, as demonstrated in Figure 6.

Figure 6

Procedure of computing the CCDF of R.

Step  1 (Utilize E[ $D_j$ ] and $Cov(D_f,D_g)$ in Section 3.3 to Calculate the kth Moment of R). The kth moment of R can be obtained from the $E[D_j]$ and $\text{Cov}(D_f,D_g)$ which have been computed in Section 3.3. The rest of the process can now be reformulated with more detail as follows.

The arbitrary order moment of R can be calculated by Harr's point estimation [53]. Harr's point estimation method is a computationally straightforward technique and is a second moment method which is capable of taking into account the first two moments (i.e., the expectation and variance) of the involved random variables. It can be used to estimate any order moment involving several random variables which are either dependent or independent [53].

According to (1), the expression of R can be considered as a function of n random variables $D_1,D_2,D_3,\dots ,D_n$ as

$$\begin{array}{cc}& R=f\left(\mathit{D}\right)=D_{\mathrm{1}}+D_{\mathrm{2}}+D_{\mathrm{3}}+\cdots +D_n,\end{array}$$

(29)

where $\mathit{D}={\left(D_1,D_2,\dots ,D_n\right)}^T$ is an n-dimensional column random variable and the superscript T represents the transpose of a matrix or vector. Consider D having an expectation vector $\mathit{\mu }$ , a covariance matrix $\mathit{\sigma }$ , and the correlation matrix $\mathit{\rho }$ :

$$\begin{array}{ll}& \mathit{\mu }={\left[E\left[D_1\right],E\left[D_2\right],E\left[D_3\right],\dots ,E\left[D_n\right]\right]}^T,\end{array}$$

(30)

$$\begin{array}{ll}& \mathit{\sigma }\\ \hspace{1em}\hspace{1em}=\left[\begin{array}{lllll}\text{Var}\left[D_1\right]& \text{Cov}(D_1,D_2)& \text{Cov}(D_1,D_3)& \cdots & \text{Cov}(D_1,D_n)\\ \text{Cov}(D_2,D_1)& \text{Var}\left[D_2\right]& \text{Cov}(D_2,D_3)& \cdots & \text{Cov}(D_2,D_n)\\ \text{Cov}(D_3,D_1)& \text{Cov}(D_3,D_2)& \text{Var}\left[D_3\right]& \cdots & \text{Cov}(D_3,D_n)\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \text{Cov}(D_n,D_1)& \text{Cov}(D_3,D_2)& \text{Cov}(D_n,D_3)& \cdots & \text{Var}\left[D_n\right]\end{array}\right],\end{array}$$

(31)

$$\begin{array}{l}\mathit{\rho }=\left[\begin{array}{lllll}1& {\rho }_{12}& {\rho }_{13}& \cdots & {\rho }_{1n}\\ {\rho }_{21}& 1& {\rho }_{23}& \cdots & {\rho }_{2n}\\ {\rho }_{31}& {\rho }_{32}& 1& \cdots & {\rho }_{3n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\rho }_{n1}& {\rho }_{n2}& {\rho }_{n3}& \cdots & 1\end{array}\right],\\ {\rho }_{ij}=\frac{\text{Cov}(D_i,D_j)}{\sqrt{\text{Var}\left[D_i\right]}·\sqrt{\text{Var}\left[D_j\right]}}.\end{array}$$

(32)

Note that $\mathit{\sigma }$ and $\mathit{\rho }$ are symmetric matrices that are $\text{Cov}(D_i,D_j)=\text{Cov}(D_j,D_i)$ and ${\rho }_{ij}={\rho }_{ij}$ for $i\ne j$ . Because $D_j$ is the MAC access delay of each node in the multihop relay chain, the values of the elements in $\mathit{\mu }$ , $\mathit{\sigma }$ , and $\mathit{\rho }$ in (30)–(32) can be found in Section 3.3.

Because Harr's point estimation only utilizes the first two moments of $[D_1,D_2,D_3,\dots ,D_n]$ the requirements of Harr's point estimation are satisfied in our study.

Moreover, Harr's point estimation method is built on orthogonal transformations of the correlation matrix [53]. The orthogonal transformation can be made using the eigenvalue eigenvector decomposition or spectral decomposition by which $\mathit{\rho }$ , defined in (32), can be decomposed as

$$\begin{array}{cc}& \mathit{\rho }=\mathbf{V}\mathit{\Lambda }{\mathbf{V}}^T,\end{array}$$

(33)

where V is a $n\times n$ eigenvector matrix consisting of n eigenvectors as $\mathit{V}=({\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_n)$ with ${\mathit{v}}_i$ being the ith column eigenvector and $\mathit{\Lambda }=\mathrm{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$ is a diagonal eigenvalues matrix [53].

For a multivariate model $R=f(\mathit{D})$ involving n random variables, Harr's method selects the evaluation points located at the intersections of n eigenvector axes with the surface of a hypersphere having a radius of the square root of n in the eigenspace as [53]

$$\begin{array}{cc}& {\mathbf{D}}_{i\pm }=\mathit{\mu }\pm \sqrt{n{\mathbf{\omega }}^{\mathrm{1}/\mathrm{2}}}·{\mathit{v}}_i,\hspace{1em}i=\mathrm{1,2},\dots ,n,\end{array}$$

(34)

in which ${\mathit{D}}_{i\mathbf{\pm }}$ represents the vector of coordinates of the n random variables in the parameter space corresponding to the ith eigenvector ${\mathit{v}}_i$ in (33); $\mathit{\mu }$ has been defined in (30); $\mathit{\omega }$ is the diagonal matrix of the variances of D derived from $\mathit{\sigma }$ in (31); $\mathit{\omega }=\mathrm{diag}\left(\text{Var}\left[D_1\right],\text{Var}\left[D_2\right],\dots ,\text{Var}\left[D_n\right]\right)$ [53].

According to [53], the kth moment of the relay access delay R about the origin can be calculated according to the following equations:

$$\begin{array}{ll}& E\left[R^k\right]=\frac{{\sum }_{i=\mathrm{1}}^n{\lambda }_i·\left(\left({\left(f\left({\mathit{D}}_{i+}\right)\right)}^k+{\left(f\left({\mathit{D}}_{i-}\right)\right)}^k\right)/\mathrm{2}\right)}{{\sum }_{i=\mathrm{1}}^n{\lambda }_i},\\ i=\mathrm{1,2},\dots ,n,\hspace{1em}k=\mathrm{1,2},\dots ,\end{array}$$

(35)

where the definitions of ${\mathit{D}}_{i\mathbf{\pm }}$ and λ can found in (33) and (34), and the function f represents the summation function defined in (29).

Step  2 (Use the kth Moment of R to Calculate the kth Derivative of the CF of R). The arbitrary order moment of R will be used to approximate the arbitrary derivative of the CF of R. The detailed calculation and explanation of Harr's point estimation can be found in [53].

According to the property of CF of R, we have

$$\begin{array}{cc}& {\phi }^{\left(k\right)}\left(0\right)=E\left[R^k\right]·i^k,\hspace{1em}i=\sqrt{-1},\hspace{0.17em}\hspace{0.17em}k=\mathrm{1,2},\dots ,\end{array}$$

(36)

where ${\phi }^k(0)$ is the kth derivative of the CF of R on $t=0$ and $E[R^k]$ is the kth moment of R from (35) [53].

Step  3 (Apply the kth Derivative of the CF of R to Approach the CF of R). When the ${\phi }^k(0)$ is derived from the kth moment of R from (35) and (36) by the Harr's point estimation, ${\phi }^k(0)$ is used to calculate the CF of R in arbitrarily small degree through the Taylor series approximation, as given by (37):

$$\begin{array}{cc}& \phi \left(t\right)=\phi \left(0\right)+{{\displaystyle \sum }}_{k=1}^{\infty }\frac{{\phi }^{\left(k\right)}\left(0\right)}{k!}{\left(i·t\right)}^k,\hspace{1em}k=\mathrm{1,2},\dots ,\end{array}$$

(37)

where the value of $\phi (0)$ is equal to 1, according to Bochner's theorem [54].

Step  4 (Utilize the CF of R to Calculate the CCDF of R). When the approximation of CF of R, indexed by $\phi (t)$ in (37), has been got, the approximation of CCDF of R will be computed by (24) and (28) based on the Gil-Pelaez inversion theorem in [52]. By substituting (28) into (24) and substituting (37) into (28), the CCDF of R can be given as

$$\begin{array}{ll}& \text{CCDF}\hspace{0.5em}\mathrm{Pr}\{c\le R<\infty \}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}=F\left(\infty \right)-F\left(c\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}=\underset{\tau \to \infty }{\lim }\frac{\mathrm{1}}{\mathrm{2}\pi }{{\displaystyle \int }}_{-\tau }^{\tau }\frac{e^{-i·t·c}-e^{-i·t·\infty }}{i·t}\phi \left(t\right)dt\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}=\underset{\tau \to \infty }{\lim }\frac{\mathrm{1}}{\mathrm{2}\pi }{{\displaystyle \int }}_{-\tau }^{\tau }\frac{e^{-i·t·c}-e^{-i·t·\infty }}{i·t}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{1em}\times \left[\phi \left(\mathrm{0}\right)+{{\displaystyle \sum }}_{k=\mathrm{1}}^{\infty }\frac{{\phi }^{\left(k\right)}\left(\mathrm{0}\right)}{k!}{\left(i·t\right)}^k\right]dt,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}i=\sqrt{-\mathrm{1}},\hspace{1em}k=\mathrm{1,2},\dots .\end{array}$$

(38)

We can see that the inversion theorem proposed by Gil-Pelaez is a particularly useful tool for numerical evaluation of a general distribution function by numerical integration. Now the probability that relay access delay is greater than the given constraint in delay sensitive applications can be calculated by the CCDF of R in (38).

4. Numerical Evaluation and Discussion

In this section, we evaluate the performance of expectation, standard deviation, and CCDF of the relay access delay in multihop relay network.

A group of researchers designed a new model of IEEE 802.11 MAC and PHY modules for ns-2 which support IEEE 802.11p. This new model is implemented in ns-2 version 2.34 and this version of ns-2 is used in our study to validate the model and calculation [55]. We changed the mechanism of traffic generation to implement the unsaturated traffic environment, as required by the Markov model in [30, 31].

In our scenarios, multiple nodes are evenly distributed in the multihop relay chain and the two endpoint nodes are the source and destination, respectively. The packet is relayed sequentially by the nodes from the source to the destination, as demonstrated in Figure 2. In the simulations, we adopt a simple fixed routing scheme which manually appoints the single-hop neighbors of any nodes. The IEEE 802.11p PHY and MAC parameters and their values used in the simulations are listed in Table 1. To facilitate the calculation, we also applied a fixed length of data packet and ignored the propagation delays. We mainly concern the MAC access delay of the entire multihop relay chain.

Table 1

IEEE 802.11p specific parameters in simulation.

Parameter	Value
Carrier sense threshold	−85 dBm
Noise floor	−99 dBm
Data rate	12 Mbps
Retry limit	7
CWmin	16
CWmax	1024
Phys header	192 μs
Slot time	20 μs
SIFS	30 μs
DIFS	58 μs
Ack packet	112 bit
RTS packet	160 bit
CTS packet	112 bit
Channel bandwidth	10 Mhz
SINR for preamble capture	4 dB
SINR for frame body capture	10 dB

4.1. Evaluating and Discussing $E[R]$ and StdDev $[R]$

In Figure 7, we plot $E[R]$ and StdDev $[R]$ as a function of the number of hops. When the number of nodes increases from 2 to 9, the hop count raises form 1 to 8 accordingly. The results obtained from the situations match our analytical results, though there are some small margins. We can find that $E[R]$ and StdDev $[R]$ both increase with the number of nodes, because the new nodes introduce the new hops. The other worthy of attention is higher growth rate of the curve of $E[R]$ in contrast with the curve of StdDev $[R]$ . The reason is that StdDev $[R]$ is the square root of the sum of the elements in the covariance matrix. Although the new nodes impact the existing nodes in the multihop relay chain, the effects decrease with the count of hops. However, the addition of nodes can directly promote the rise in $E[R]$ .

Figure 7

$E[R]$ and StdDev $[R]$ change with the number of hops and the length of packet.

In Figure 7, there are three test scenarios corresponding to 64, 320, and 640 bytes in DATA packet. The accuracy of our analytical model can be maintained for a range of different DATA packet sizes. An increase with the larger DATA packets also can be observed. The length of DATA packet impacts the value of $E[R]$ and StdDev $[R]$ by affecting the value of $T_s$ and $E[Y_{j,v,w}^k]$ . When the DATA packet has more bytes, more time is needed to be spent on avoiding the DATA packet of the single-hop neighbor.

The backoff stage and backoff interval of every node both grow rapidly, and this finally increases the value of $E[R]$ and StdDev $[R]$ .

4.2. Evaluating and Discussing CCDF of R

Next, we compare the CCDF of R in the proposed analytical model and simulation result. As presented in Section 3.3, Harr's point estimation is applied to obtain $E[R^3]$ , $E[R^4]$ , and $E[R^5]$ , and the CF of R is approximated by the Taylor series of first five terms.

In Figure 8, we plot the CCDF of relay access delay for one hop, two hops, five hops, and seven hops. The observation concerns the accuracy of the analysis. It is evident that our model assumptions and approximations are suitable for relay access delay considered. Moreover, we also can find that the length of DATA packet impacts on the CCDF of R.

Figure 8

The complementary cumulative distribution function (CCDF) of relay access delay.

We can observe the heavy-tailed distribution shown in Figure 8. There is an initial linearity followed by a faster roll off, which is characteristic of a truncated power-law tail distribution. The power-law exponent decreases with increasing the number of nodes and the point of truncation moves further into the tail with the increasing of DATA packet length. Sakurai and Vu [32] previously proved that the heavy tail is a direct consequence of the exponential growth of the backoff window in the exponential backoff process in the analysis of access delay. Hence, relay access delay can be regarded as a sum of the access delay statistics for truncated binary exponential backoff (BEB) with different value of parameters.

4.3. Delay Requirement in Multimedia Video Delivery

In this section, we investigate the effects of the end-to-end delays on the quality of user's experience in live video transmission. It is clear that the long end-to-end delay degrades quality of live multimedia subjectively. Therefore, it is necessary to study the effect of the delay on the quality of experience degradation. Many researchers have reported the effect of delay on subjectivity of multimedia.

In 2000, Baldi and Ofek proposed a delay requirement in multimedia video delivery and published their research achievements in [56]. Baldi and Ofek consider that 100 ms is a typical upper limit of end-to-end delay for real-time video transmission. Excessively delayed frames beyond this value are ignored and treated similarly to lost frames.

In 2012, Anjum et al. put forward that the end-to-end delay of video dissemination should be measured in terms of its mean, and it was more meaningful to express it as a statistical upper bound in the form of a percentile [57]. In [57], the satisfactory end-to-end delay is less than 150 ms in 95% of the time for video stream in an IP network.

In IEEE 802.11p, available bandwidth is sufficient for commonly used multimedia streaming services. However, delay is an important problem, which is caused mostly by CSMA/CA medium access mechanism of IEEE 802.11p. When the medium is highly occupied by other neighbors’ transmission, CSMA/CA prevents transmitter from sending a packet that may cause MAC access delay. The total effect on the MAC access delay of every vehicle in multihop relay chain is regarded as relay access delay which is a very large part of end-to-end delay under conditions of saturation.

Integrating different kinds of delay requirement in multimedia video delivery [56, 57], 100 ms is an appropriate upper boundary of 95% confidence interval of relay access delay in video dissemination. It means that the 95 percent of relay access delay is less than 100 ms in a live video transmission. As shown in Figure 8(d), when the value of relay access delay is equal to 100 ms, the probability of complementary cumulative distribution function is less than 5%. It means that more than 95 percent of the relay access delay is less than 100 ms, when eight or fewer nodes are in the multihop relay chain.

As shown in Figure 7(a), the expectation of relay access delay increases to the number of nodes in the multihop relay chain. When the number of nodes increases to ten in the multihop relay chain, the upper boundary of 95% confidence interval of relay access delay cannot meet 100 ms requirement. It indicates that IEEE 802.11p cannot satisfy the delay constrains, when the number of nodes in the multihop relay chain is ten or more. This result suggests that IEEE 802.11p cannot meet the delay requirement in multimedia video delivery in the long multihop relay chain, because CSMA/CA mechanism introduces a very large delay under saturation traffic like live video dissemination. In the long multihop relay chain, IEEE 802.11p needs to be improved by introducing noncompetitive MAC access delay, when multimedia video is delivered along the long multihop relay chain to spread driving safety.

5. Conclusions

In this paper, we proposed an analysis method to study the information dissemination process and the relay access delay in multihop relay chain which is an effective structure in the communication between two vehicles. In particular, the analysis developed attempts to relate the expression, the expectation, the variance, and the complementary cumulative distribution function of relay access delay. The proposed model has been proved to be effective in estimating the impact of hops and packet size correlation on the dissemination of information in the network. We hope our research will be helpful in the design and implementation of multimedia dissemination in VANETs by providing probabilistic characteristics of multihop relay delay.