# A Semi-Markov Process Model for Performance Evaluation of DSRC Vehicular Safety Communication

Authors: Lin Hu; Xingyue Liu; Kun Zhou
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In this study, a new semi-Markov process (SMP)-based model is devised to evaluate the IEEE 802.11p enhanced distributed channel access (EDCA) broadcast performance for vehicular safety communication. Differing from the existing SMP analytical models, the proposed model takes the virtual collision among various prioritized access categories (ACs) inside each vehicle into consideration. Moreover, in contrast to the Markov chain-based models, our model is simpler but with approximate accuracy. Concretely, we first capture the behavior of each AC’s backoff entity using SMP. Then, the parameters of interest in the vehicular ad hoc network (VANET) such as packet transmission probability, conditional collision probability, and saturation throughput are derived. Finally, via MATLAB simulations, we demonstrate that the newly developed model achieves comparable accuracy in calculating these output parameters while its complexity and computation time is around one-tenth of that of the Markov chain-based models. Therefore, the proposed model is more suitable for real-time performance analysis of IEEE 802.11p EDCA safety communication in a freeway scenario.


---

## Body

## 1. Introduction

Thanks to the advanced wireless communication technologies, the intelligent transportation system (ITS) is projected to provide safe, effective, and high-quality future transportation systems [1]. The vehicular ad hoc network (VANET) had been viewed as an effective and efficient approach to satisfy ITS’s claims by offering miscellaneous safety and nonsafety applications. Dedicated short-range communication (DSRC) is the most prospective candidate to implement the new generation of a worldwide VANET. It works at a 5.9 GHz band ranging from 5.850–5.925 GHz, which is specified by the US Federal Communication Commission (FCC) [2]. The assigned 75 MHz band contains a 10 MHz control channel (CCH) and six 10 MHz service channels (SCHs) where the CCH is exclusive for common safety communications and the SCHs are for other nonsafety applications. The physical (PHY) layer and the medium access control (MAC) sublayer of DSRC utilize the IEEE 802.11p wireless access vehicular environment (WAVE) standard, which inherits from the IEEE 802.11 standard [3]. To be specific, the physical (PHY) layer of DSRC adopts orthogonal frequency-division multiplexing (OFDM) modulation scheme that is the same as the IEEE 802.11a standard but supports transmission rates from 3 to 27 Mb/s since it generally adopts half of the bandwidth as the IEEE 802.11a protocol, the MAC sublayer of which adopts enhanced distributed channel access (EDCA) to guarantee the quality-of-service (QoS) [4].Due to the highly dynamic topology and strict requirements in VANET, safety-related messages tend to be broadcast on CCH in a one-hop manner [5]. In a vehicle, the EDCA mechanism classifies safety-related messages from various applications into four following access categories (ACs) with corresponding priorities based on their criticalities to vehicles’ safety: (1) AC[0], who has the highest priority, conveys urgent information from a wayside unit such as traffic accidents and appalling road condition and from abnormal vehicles in front including brake failure and over speeding; (2) AC [1], who has higher precedence than AC [2] but lower precedence than AC[0], conveys the position and speed information advertised by the vehicle; (3) AC [2], who has higher precedence than AC [3] but lower precedence than AC [1], conveys the information released by vehicles asking for help when they are risk-free to other vehicles such as overheating or running out of gas; (4) AC [3], who has the lowest priority, communicates information aimed at setting up new nonsafety-related conversations through the SCHs. It is worth noting that these four ACs are all broadcast via the CCH.This study concerns the performance evaluation of safety-related messages broadcast on the CCH adopting IEEE 802.11p EDCA in a VANET environment. The main contributions of this study can be summarized as follows:(1)
We establish a new semi-Markov process (SMP)-based model to evaluate the IEEE 802.11p EDCA broadcast performance for vehicular safety communication under saturated conditions.(2)
Different from the existing SMP analytical models, we calculate the key performance indicators such as packet transmission probability, conditional collision probability, and saturation throughput by taking the virtual collision among four prioritized ACs inside each vehicle, namely, arbitration interframe space (AIFS) differentiation, the retry limit, the minimum, and maximum contention window (CW) into consideration.(3)
Compared with the Markov chain-based models, our model is simpler but with approximate accuracy.The rest of this study is well organized as follows: we first introduce a VANET model and provide the necessary assumptions for a typical freeway scenario. Then, the analytical model of single-hop broadcast based on the IEEE 802.11p EDCA mechanism to assess the performance from the view of a certain reference vehicle is established. In the simulations, we validate the accuracy of the built model, and its complexity and computation time are calculated using MATLAB simulator and then compared with the existing Markov chain-based models. Finally, the conclusion of this study is carried out.


## 2. State of the Art

Bianchi [6] initially proposed a 2-D Markov-chain model for performance evaluation of the IEEE 802.11 distributed coordination function (DCF) protocol. The state space S of the model in [6] can be easily computed by(1)S=∑i=0m2iCWmin+1,where i denotes the backoff stage of the binary exponential backoff mechanism, CWmin represents the minimum CW, and m stands for the maximum backoff stage. The state space S is as follows:(2)S=∑i=062i15+1=16×27−1=2032,for frequency-hopping spread spectrum (FHSS) physical layer specifications.Many of the previous research studies on performance analysis of VANET broadcast are grounded on Bianchi’s model, such as [7–10]. Also, some works extended the 2-D model into a 3-D model. For example, in the work of [11], Hwuang and Chang developed a 3-D Markov chain-based model to assess the performance of IEEE 802.11e EDCA protocol. Moreover, other analytical models combining two Markov chains were established for the IEEE 802.11p EDCA. In [12], a 1-D Markov model was used to model the backoff instance of highest precedence, AC[0], and a 2-D Markov model for lower precedence, AC [1]-AC [3]. Authors in [13–15] built a 2-D Markov model for the backoff procedure of an AC queue and a 1-D Markov model for the contention period of an AC queue. In addition to the above works, Gallardo et al. [16] proposed different models for each of the access categories AC [1] through AC [3], and Zhao et al. [17] employed a scalable analytical model to capture the IEEE 802.11p EDCA performance. Intuitively, the state space S of Bianchi’s model is with the order of O2m which is very large, let alone the theoretical models mentioned above for the more sophisticated IEEE 802.11p EDCA protocol.For simplicity and reduced complexity, SMP-based models for performance assessment of IEEE 802.11 DCF protocol have been devised in [18, 19]. The proposed models had a lessened number of states with the order of Om compared to that of Bianchi’s model with the order of O2m. The SMP model approach has also been exploited in the performance assessment of IEEE 802.11p EDCA. Yin et al. [20] introduced an SMP model for MAC level performance assessment of one type of safety service in a single channel. The authors in [21] extended the model to multichannel services and the model was extended to MAC and application-level performance evaluation in [22]. Reference [23] presented an SMP model for basic safety message broadcast performance analysis and various QoS metrics were defined and evaluated. However, all these works only consider the performance evaluation of a certain type of AC. The performance of multiple types of safety messages was analyzed in [24] using an SMP model. However, their work did not consider the virtual collisions and assumed that all ACs in a node were independent from each other which is not reasonable. A detailed survey and analysis of the most related models is shown in this study and generalized in Table 1.Table 1
Comparison of analytical models.
ReferenceApproachModeMAC typeADNumber of ACVCThroughput[6–17]Markov chain-basedU/BDCF/EDCA—1/2/3/4×/√√[18, 19]SMP basedUDCF———√[20–23]SMP basedBEDCA×1××[24]SMP basedBEDCA√4××Our modelSMP basedBEDCA√4√√Note: U: unicast, B: broadcast, AD: AIFS differentiation, VC: virtual collision, and ×: not considered.Motivated by the above-mentioned observations, we design an SMP-based analytical model for the IEEE 802.11p EDCA performance assessment for vehicular safety communication and derive the key performance indicators such as conditional collision probability, packet transmission probability, and saturation throughput. As far as we know, this is the first SMP-based analytical model designed for the performance of multiple types of safety message broadcast taking the virtual collisions into consideration, which can not only accurately calculate these output parameters but also achieve results with less complexity and computation time compared with the existing Markov chain-based models.


## 3. System Model and Assumptions

We first introduce the VANET model in the freeway scenario in this section. To facilitate modeling, we then enumerate some essential and reasonable assumptions.


### 3.1. System Model

Imagine that several vehicles run on a bidirectional freeway and each direction has one lane. Since the maximum transmission range defined in the IEEE 802.11p standard is up to 1 km and the width of two lanes is around 10 m, which can be neglected, we can then simplify this typical freeway scenario into a 1-D VANET model, which is illustrated in Figure1.Figure 1
The diagram of the 1-D VANET model.In this model, one node stands for one vehicle. The transmission range defined as the maximum distance between a pair of transceivers that can successfully contact each other is denoted byR. It depends on the transmission power and wireless channel condition. Also, we define the carrier sensing range as the maximum distance that a node can detect a signal and denote it as Lcs, which is a crucial parameter in the carrier sense multiple access/collision avoidance (CSMA/CA) technique.


### 3.2. Assumptions

We suppose the following scenarios for IEEE 802.11p VANET broadcasting in a freeway scenario:(1)
Vehicles are placed exponentially on a 1-D freeway whose distribution satisfies Poisson point process with parameterβ (in vehicles per meter); then, the probability of finding i vehicles existing in length l is obtained by(3)Pi,l=βlii!e−βl.(2)
As shown in Figure1, with the constraint R ≤ Lcs, we can readily figure out the mean number of vehicles in the transmission range and the carrier sensing range, respectively, as follows:(4)Ntr=2βR,Ncs=2βLcs.(3)
Safety-related messages are usually very short, so each of them can be encapsulated in a single packet [4]. Also, we assume that all ACs have the same mean packet size PD.(4)
The IEEE 802.11p EDCA protocol provides each AC with a MAC queue entity to occupy the medium and each entity always has a packet available for transmission, i.e., saturation condition.(5)
In this study, we only emphasize the influences of internal and external collisions on network performance. Hence, the impact of an error-prone channel is neglected. Such consideration can be readily extended from existing results such as [24, 25].


## 3.1. System Model

Imagine that several vehicles run on a bidirectional freeway and each direction has one lane. Since the maximum transmission range defined in the IEEE 802.11p standard is up to 1 km and the width of two lanes is around 10 m, which can be neglected, we can then simplify this typical freeway scenario into a 1-D VANET model, which is illustrated in Figure1.Figure 1
The diagram of the 1-D VANET model.In this model, one node stands for one vehicle. The transmission range defined as the maximum distance between a pair of transceivers that can successfully contact each other is denoted byR. It depends on the transmission power and wireless channel condition. Also, we define the carrier sensing range as the maximum distance that a node can detect a signal and denote it as Lcs, which is a crucial parameter in the carrier sense multiple access/collision avoidance (CSMA/CA) technique.


## 3.2. Assumptions

We suppose the following scenarios for IEEE 802.11p VANET broadcasting in a freeway scenario:(1)
Vehicles are placed exponentially on a 1-D freeway whose distribution satisfies Poisson point process with parameterβ (in vehicles per meter); then, the probability of finding i vehicles existing in length l is obtained by(3)Pi,l=βlii!e−βl.(2)
As shown in Figure1, with the constraint R ≤ Lcs, we can readily figure out the mean number of vehicles in the transmission range and the carrier sensing range, respectively, as follows:(4)Ntr=2βR,Ncs=2βLcs.(3)
Safety-related messages are usually very short, so each of them can be encapsulated in a single packet [4]. Also, we assume that all ACs have the same mean packet size PD.(4)
The IEEE 802.11p EDCA protocol provides each AC with a MAC queue entity to occupy the medium and each entity always has a packet available for transmission, i.e., saturation condition.(5)
In this study, we only emphasize the influences of internal and external collisions on network performance. Hence, the impact of an error-prone channel is neglected. Such consideration can be readily extended from existing results such as [24, 25].


## 4. Analytical Model

In this section, we expound on our analytical model for the IEEE 802.11p EDCA safety messages broadcast.


### 4.1. Differentiation Parameters in EDCA

The IEEE 802.11p EDCA distinguishes ACs by identifying channel access parameters, which include the CW, the AIFS, and the transmission opportunity (TXOP). Table2 lists the specific access parameter of IEEE 802.11p EDCA, where AC [0] corresponds to the highest priority and AC [3] corresponds to the lowest priority.(1)
CW: let Wi,j be the maximum CW size of AC[i] (i = 0, 1, 2, 3) at the jth backoff stage after j times failed transmission attempts; hence, Wi,0=CWi,min+1. Denote Mi as the maximum times the CW of AC[i] can be doubled; thus, Mi=log2CWi,max+1/CWi,min+1. Therefore, Wi,j can be computed by(5)Wi,j=2jWi,0,j≤Mi,2MiWi,0,Mi<j≤Li,whereLi is the retry limit for AC[i] packets. For convenience, we assume that all Li equals L in this study.(2)
AIFS: to support priority-based QoS, EDCA defines a different defer time called AIFS for ACs when the channel is detected free. The duration of AIFS is determined by the AIFS number (AIFSN) according to the following:(6)AIFSi=SIFS+AIFSNi×σ,whereσ is the slotted time, SIFS represents the short interframe space, and AIFSN[i] ≥ 2. Define Ai as the AIFS differentiation, which is given by(7)Ai=AIFSNi−AIFSN0.(3)
TXOP: the TXOP limit permits an AC entity to consecutively transmit several packets without channel contentions. However, the TXOP limit still has not been fixed by the IEEE 802.11p standard up to now. In this study, we assume it equals zero, which indicates an AC entity has to compete for the channel access opportunity every time it accomplishes a packet transmission.Table 2
Access parameter for IEEE 802.11p EDCA.
ACCWminCWmaxAIFSNTXOP limit3aCWminaCWmax902aCWminaCWmax601(aCWmin + 1)/2 − 1aCWmin300(aCWmin + 1)/4 − 1(aCWmin + 1)/2 − 120


### 4.2. IEEE 802.11p EDCA Broadcast Mechanism

As shown in Figure2, new different prioritized packets arrive at the MAC layer from higher layers and then are assigned to corresponding queues. Without considering the virtual collisions, the backoff instances in a station can be regarded as being independent from every single other. For each AC, it transmits if the channel is sensed vacant for an AIFS. Otherwise, the AC will keep monitoring the channel until the idle duration up to the AIFS. At present, a backoff procedure is triggered and a random interval is generated according to the AC’s CW value. The backoff counter starts to decrease only if the channel stays vacant for an AIFS. When the backoff counter reaches zero, it will be transmitted. Since safety messages tend to be broadcast, there is no ACK mechanism and the packet will be discarded regardless of the successful or failed transmission.Figure 2
The diagram of IEEE 802.11p EDCA backoff procedure.When taking the virtual collision into account, different backoff instances in a node cannot occupy the channel all alone. Figure2 presents a summarization of a station with virtual collision handling. If more than two backoff instances of a node are attempting to use the channel at the same time, a virtual collision happens. On this occasion, the packet that has the highest priority should be transmitted, and the packets with lower priorities enter another backoff stage with doubled CWs directly. If the failed retransmission count reaches the retry limit, it will be dropped.As demonstrated in Figure2, we denote the internal transmission probability that the backoff instance of AC[i] tries to transmit a packet in a timeslot observed by other ACs in the same node and the internal collision probability of AC[i] as ϖi and pvi, respectively. Accordingly, it has the following:(8)pv0=0,pv1=ϖ0,pv2=1−1−ϖ01−ϖ1,pv3=1−1−ϖ01−ϖ11−ϖ2.The external transmission probabilityτi observed by other nodes outside of the node is computed by the following:(9)τ0=ϖ01−pv0=ϖ0,τ1=ϖ11−pv1=ϖ11−ϖ0,τ2=ϖ21−pv2=ϖ21−ϖ01−ϖ1,τ3=ϖ31−pv3=ϖ31−ϖ01−ϖ11−ϖ2.Hence, the total transmission probabilityτ for a node can be written as follows:(10)τ=τ0+τ1+τ2+τ3.The external collision probabilitypc is calculated by the following:(11)pc=1−∑k=0∞1−τkNcs−1kk!e−Ncs−1=1−e−Ncs−1τ.We can observe from equation (11) that pc is obtained by 1 minus the successful transmission probability of the reference node. The following condition should be satisfied to ensure a successful transmission: when the reference node is transmitting, no nodes in its carrier sensing range transmit simultaneously. The average packet transmission time is given as follows:(12)Ttr=PHYHRb+MACH+EPRd+δ,where E[P] represents the average length of the data packet from the upper layer, PHYH and MACH stand for the lengths of packet header from physical and MAC layer separately, Rb and Rd, respectively, denote the basic rate and data rate and δ is the propagation delay.


### 4.3. SMP Model

In this part, the backoff procedure of AC[i] is simulated using an SMP approach. In the SMP model, an average state sojourn time, the duration that a node stays at the current state before making a state change from the present state, is incorporated. The subsequent state of the node in the SMP model hinges on the present state and its state sojourn time. The sample paths for the SMP model are timed sequences of the state transitions. If the process is seen at the instances of state transitions, the sample paths are the same as those of a Markov chain. Such a process is called the embedded Markov chain, which does not contain self-loops [26].In the following part, we first construct a (Li + 1)-state Markov chain to figure out the backoff stages of AC[i]. Given that the backoff interval involved in different backoff stages of AC[i] are not identical, this discrete-time Markov chain with a unit state sojourn time for all the states cannot exactly capture the behavior of the backoff procedure of AC[i], which then brings about the introduction of an embedded Markov chain allowing different state sojourn times for different states. However, this embedded Markov chain does not include self-loops (switching from the state j to itself). Thus, we subsequently model the backoff procedure of AC[i] with the SMP model allowing self-loops and different state sojourn times for different backoff stages. Ultimately, we calculate the parameters of interest grounded on the proposed SMP model.The (Li + 1)-state Markov chain in Figure 3 stands for the backoff procedure of AC[i]. The backoff instance of AC[i] with packets to send is in state 0. If the AC[i] escapes from virtual collision, its backoff instance loops back to state 0 and starts the next packet transmission. For virtual collision, the backoff instance of AC[i] in state j, j ∈ [0, Li − 1], proceeds retransmission and goes into state j + 1. For the backoff instance of AC[i] in state Li, it will always go into state 0 whether the packet is free from virtual collision or not. But it is different that for the case where no virtual collision happens in state Li, the backoff instance of AC[i] initiates a new packet transmission, while for the case where AC[i] suffers from virtual collision, it will drop the transmitting packet directly and then begin a new packet transmission. The changing from state j to state j + 1 indicates that the AC[i] packet transmission encounters the virtual collision and the transition from any state j, j ∈ [0, Li − 1], to state 0 indicates the AC[i] escapes from the virtual collision. The loopback is only possible for the state 0.Figure 3
The (Li + 1)-state Markov chain of AC[i].The state transitions of the (Li + 1)-state Markov chain can be described by the one-step state transition probability matrix Pi given by the following:(13)Pi=1−pvipvi00⋯001−pvi0pvi0⋯001−pvi00pvi⋯001−pvi000⋯00•••••••1−pvi000⋯pvi01−pvi000⋯0pvi1000⋯00,where pj,ki, 0 ≤ j, k ≤ Li, is the probability of transition from state j to state k and pj−1,ji, 1 ≤ j ≤ Li, is equal to the internal collision probability pvi.Then, we transform the above Markov chain into an embedded Markov chain (withpj,ji = 0, ∀j), as illustrated in Figure 4.Figure 4
The (Li + 1)-state embedded Markov chain of AC[i].The elementpj,ke,i of the state transition probability matrix Pe,i of the embedded Markov chain is given by the following:(14)pj,ke,i=0,forj=k,pj,ki1−pj,ji,forj≠k,which results in the following:(15)Pe,i=0100⋯001−pvi0pvi0⋯001−pvi00pvi⋯001−pvi000⋯00•••••••1−pvi000⋯pvi01−pvi000⋯0pvi1000⋯00.The stationary probabilityπje,i of the state j of the embedded Markov chain is derived by the following:(16)πje,i=∑k≠jπke,ipk,je,i,∀j∈0,Li.Combining these simultaneous equations with∑j=0Liπje,i=1, we acquire the stationary probabilities of the embedded Markov chain by the following:(17)π0e,i=π1e,i=1−pvi2−pvi−pviLi,πje,i=1−pvipvij−12−pvi−pviLi,∀j∈2,Li.which constitute the stationary probability vectorπe,i marked as π0e,i,π1e,i,π2e,i,…,πLie,i.Based on [26], the stationary probabilities vector πs,i of the SMP model is denoted as π0s,i,π1s,i,π2s,i,…,πLis,i, and(18)πjs,i=πje,i×EHji∑k=0Liπke,i×EHki,0≤j≤Li,where Hji represents the sojourn time of state j. The backoff interval of the backoff stage j is modeled with the state sojourn time, which is a random variable uniformly chosen within the range 0,Wi,j, for 0 ≤ j ≤ Li.Since high priority ACs’ AIFSs will affect low priority ones, the probability for each AC’s backoff counter to decrease one may not be identical. Letpbi be the backoff blocking probability. For a given backoff instance of AC[i] in a vehicle, pbi equals the possibility that the vehicle senses other vehicles using the channel or other ACs in the same vehicle are attempting transmissions. Due to the bigger AIFSNs, the lower priority ACs are deferred for a longer time than higher priority ones, which is shown in Figure 5. Hence, pbi is computed by the following:(19)pbi=1−∑k=0∞1−τkNcs−1kk!e−Ncs−1∏j=0j≠i31−ϖjAi+1,then, the average slot time σi¯ for each AC in a vehicle is obtained by the following:(20)σi¯=pbiTtr+1−pbiσ,and the normalized slot time for each AC in a vehicle is written as follows:(21)σi¯=σi¯σ.Figure 5
Illustration of the impact of different AIFSNs on backoff blocking probability.Therefore, the expected value of state sojourn timeEHji for state j of the semi-Markov process of AC[i] is given by the following:(22)EHji=Wi,j2σi¯,0≤j≤Li.For the given backoff instance of AC[i], it will visit state 0 successively after successfully escaping from the virtual collision in backoff stage j, 0 ≤ j ≤ Li, and after a packet drop in backoff stage Li. Hence, the excepted number of consecutive visits to state 0 is 1/1−1−pvi, and the expected value of state sojourn time for state 0 is as follows:(23)EH0i=Wi,02σi¯×1pvi=Wi,02pviσi¯.Using equation (18) and ∑j=0Liπjs,i=1, the stationary probabilities of the SMP of AC[i] are given by the following:(24)π0s,i=12Bipvi,π1s,i=1Bi,πjs,i=2pvij−1Bi,2≤j≤Mi,2Mi−1pvij−1Bi,Mi<j≤Li,where(25)Bi=1−2pviMi+12pvi1−2pvi+2Mi−1pviMi−pviLi1−pvi.The stationary probabilityπjs,i of the SMP represents the fraction of time spent by AC[i] in backoff stage j.In the following part, we exploit the stationary probability distribution of the SMP model and the state sojourn times to derive the packet transmission probabilityτ, conditional collision probability (i.e., external collision probability), and saturated network throughput. The internal transmission probability ϖi is computed as follows:if the backoff instance of AC[i] is in state j, it will transmit once after an expected time interval E[Hj], for 1 ≤ j ≤ Li. For state 0, AC[i] transmits once after an expected time interval of EH0/1/pvi. Hence, ϖi can be expressed as follows:(26)ϖi=π0s,i1/pviEH0+π1s,iEH1+⋯+πLis,iEHLi=1−pviLi+1BiWi,0pvi1−pviσi¯.So far, we have derived the internal transmission probability of AC[0]-AC [3] from the proposed SMP model and we can get the packet transmission probability τ by combining equations (8)–(10).LetSi be the saturation throughput for each AC in a station. Define Ptr as the possibility of at least one node in the transmission range transmitting in the considered slot time, Ps,i as the probability that a transmission attempt of AC[i] is successful conditioned on the fact that at least one node transmitting in the considered slot time, and Pfc as the probability that a transmission attempt fails owing to a collision conditioned on the fact that at least one node transmitting in the considered slot time. Thus, we have the following:(27)Ptr=1−∑k=0∞1−τkNtrk/k!e−Ntr=1−e−Ntrτ,Ps,i=Ntr×τi×∑k=0∞1−τkNcs−1k/k!e−Ncs−1Ptr,i=0,1,2,3,Pfc=1−∑k=0∞1−τkNtrk/k!e−Ntr−Ntr×τ×∑k=0∞1−τkNcs−1k/k!e−Ncs−1Ptr,and Si is derived by(28)Si=Ps,i×Ptr×EP1−Ptrσ+∑i=03Ptr×Ps,i×ts,i+Ptr×Pfc×tc,i,where the expressions of ts,i, and tc,i are given by(29)ts,i=tc,i=Ttr+AIFSi.


## 4.1. Differentiation Parameters in EDCA

The IEEE 802.11p EDCA distinguishes ACs by identifying channel access parameters, which include the CW, the AIFS, and the transmission opportunity (TXOP). Table2 lists the specific access parameter of IEEE 802.11p EDCA, where AC [0] corresponds to the highest priority and AC [3] corresponds to the lowest priority.(1)
CW: let Wi,j be the maximum CW size of AC[i] (i = 0, 1, 2, 3) at the jth backoff stage after j times failed transmission attempts; hence, Wi,0=CWi,min+1. Denote Mi as the maximum times the CW of AC[i] can be doubled; thus, Mi=log2CWi,max+1/CWi,min+1. Therefore, Wi,j can be computed by(5)Wi,j=2jWi,0,j≤Mi,2MiWi,0,Mi<j≤Li,whereLi is the retry limit for AC[i] packets. For convenience, we assume that all Li equals L in this study.(2)
AIFS: to support priority-based QoS, EDCA defines a different defer time called AIFS for ACs when the channel is detected free. The duration of AIFS is determined by the AIFS number (AIFSN) according to the following:(6)AIFSi=SIFS+AIFSNi×σ,whereσ is the slotted time, SIFS represents the short interframe space, and AIFSN[i] ≥ 2. Define Ai as the AIFS differentiation, which is given by(7)Ai=AIFSNi−AIFSN0.(3)
TXOP: the TXOP limit permits an AC entity to consecutively transmit several packets without channel contentions. However, the TXOP limit still has not been fixed by the IEEE 802.11p standard up to now. In this study, we assume it equals zero, which indicates an AC entity has to compete for the channel access opportunity every time it accomplishes a packet transmission.Table 2
Access parameter for IEEE 802.11p EDCA.
ACCWminCWmaxAIFSNTXOP limit3aCWminaCWmax902aCWminaCWmax601(aCWmin + 1)/2 − 1aCWmin300(aCWmin + 1)/4 − 1(aCWmin + 1)/2 − 120


## 4.2. IEEE 802.11p EDCA Broadcast Mechanism

As shown in Figure2, new different prioritized packets arrive at the MAC layer from higher layers and then are assigned to corresponding queues. Without considering the virtual collisions, the backoff instances in a station can be regarded as being independent from every single other. For each AC, it transmits if the channel is sensed vacant for an AIFS. Otherwise, the AC will keep monitoring the channel until the idle duration up to the AIFS. At present, a backoff procedure is triggered and a random interval is generated according to the AC’s CW value. The backoff counter starts to decrease only if the channel stays vacant for an AIFS. When the backoff counter reaches zero, it will be transmitted. Since safety messages tend to be broadcast, there is no ACK mechanism and the packet will be discarded regardless of the successful or failed transmission.Figure 2
The diagram of IEEE 802.11p EDCA backoff procedure.When taking the virtual collision into account, different backoff instances in a node cannot occupy the channel all alone. Figure2 presents a summarization of a station with virtual collision handling. If more than two backoff instances of a node are attempting to use the channel at the same time, a virtual collision happens. On this occasion, the packet that has the highest priority should be transmitted, and the packets with lower priorities enter another backoff stage with doubled CWs directly. If the failed retransmission count reaches the retry limit, it will be dropped.As demonstrated in Figure2, we denote the internal transmission probability that the backoff instance of AC[i] tries to transmit a packet in a timeslot observed by other ACs in the same node and the internal collision probability of AC[i] as ϖi and pvi, respectively. Accordingly, it has the following:(8)pv0=0,pv1=ϖ0,pv2=1−1−ϖ01−ϖ1,pv3=1−1−ϖ01−ϖ11−ϖ2.The external transmission probabilityτi observed by other nodes outside of the node is computed by the following:(9)τ0=ϖ01−pv0=ϖ0,τ1=ϖ11−pv1=ϖ11−ϖ0,τ2=ϖ21−pv2=ϖ21−ϖ01−ϖ1,τ3=ϖ31−pv3=ϖ31−ϖ01−ϖ11−ϖ2.Hence, the total transmission probabilityτ for a node can be written as follows:(10)τ=τ0+τ1+τ2+τ3.The external collision probabilitypc is calculated by the following:(11)pc=1−∑k=0∞1−τkNcs−1kk!e−Ncs−1=1−e−Ncs−1τ.We can observe from equation (11) that pc is obtained by 1 minus the successful transmission probability of the reference node. The following condition should be satisfied to ensure a successful transmission: when the reference node is transmitting, no nodes in its carrier sensing range transmit simultaneously. The average packet transmission time is given as follows:(12)Ttr=PHYHRb+MACH+EPRd+δ,where E[P] represents the average length of the data packet from the upper layer, PHYH and MACH stand for the lengths of packet header from physical and MAC layer separately, Rb and Rd, respectively, denote the basic rate and data rate and δ is the propagation delay.


## 4.3. SMP Model

In this part, the backoff procedure of AC[i] is simulated using an SMP approach. In the SMP model, an average state sojourn time, the duration that a node stays at the current state before making a state change from the present state, is incorporated. The subsequent state of the node in the SMP model hinges on the present state and its state sojourn time. The sample paths for the SMP model are timed sequences of the state transitions. If the process is seen at the instances of state transitions, the sample paths are the same as those of a Markov chain. Such a process is called the embedded Markov chain, which does not contain self-loops [26].In the following part, we first construct a (Li + 1)-state Markov chain to figure out the backoff stages of AC[i]. Given that the backoff interval involved in different backoff stages of AC[i] are not identical, this discrete-time Markov chain with a unit state sojourn time for all the states cannot exactly capture the behavior of the backoff procedure of AC[i], which then brings about the introduction of an embedded Markov chain allowing different state sojourn times for different states. However, this embedded Markov chain does not include self-loops (switching from the state j to itself). Thus, we subsequently model the backoff procedure of AC[i] with the SMP model allowing self-loops and different state sojourn times for different backoff stages. Ultimately, we calculate the parameters of interest grounded on the proposed SMP model.The (Li + 1)-state Markov chain in Figure 3 stands for the backoff procedure of AC[i]. The backoff instance of AC[i] with packets to send is in state 0. If the AC[i] escapes from virtual collision, its backoff instance loops back to state 0 and starts the next packet transmission. For virtual collision, the backoff instance of AC[i] in state j, j ∈ [0, Li − 1], proceeds retransmission and goes into state j + 1. For the backoff instance of AC[i] in state Li, it will always go into state 0 whether the packet is free from virtual collision or not. But it is different that for the case where no virtual collision happens in state Li, the backoff instance of AC[i] initiates a new packet transmission, while for the case where AC[i] suffers from virtual collision, it will drop the transmitting packet directly and then begin a new packet transmission. The changing from state j to state j + 1 indicates that the AC[i] packet transmission encounters the virtual collision and the transition from any state j, j ∈ [0, Li − 1], to state 0 indicates the AC[i] escapes from the virtual collision. The loopback is only possible for the state 0.Figure 3
The (Li + 1)-state Markov chain of AC[i].The state transitions of the (Li + 1)-state Markov chain can be described by the one-step state transition probability matrix Pi given by the following:(13)Pi=1−pvipvi00⋯001−pvi0pvi0⋯001−pvi00pvi⋯001−pvi000⋯00•••••••1−pvi000⋯pvi01−pvi000⋯0pvi1000⋯00,where pj,ki, 0 ≤ j, k ≤ Li, is the probability of transition from state j to state k and pj−1,ji, 1 ≤ j ≤ Li, is equal to the internal collision probability pvi.Then, we transform the above Markov chain into an embedded Markov chain (withpj,ji = 0, ∀j), as illustrated in Figure 4.Figure 4
The (Li + 1)-state embedded Markov chain of AC[i].The elementpj,ke,i of the state transition probability matrix Pe,i of the embedded Markov chain is given by the following:(14)pj,ke,i=0,forj=k,pj,ki1−pj,ji,forj≠k,which results in the following:(15)Pe,i=0100⋯001−pvi0pvi0⋯001−pvi00pvi⋯001−pvi000⋯00•••••••1−pvi000⋯pvi01−pvi000⋯0pvi1000⋯00.The stationary probabilityπje,i of the state j of the embedded Markov chain is derived by the following:(16)πje,i=∑k≠jπke,ipk,je,i,∀j∈0,Li.Combining these simultaneous equations with∑j=0Liπje,i=1, we acquire the stationary probabilities of the embedded Markov chain by the following:(17)π0e,i=π1e,i=1−pvi2−pvi−pviLi,πje,i=1−pvipvij−12−pvi−pviLi,∀j∈2,Li.which constitute the stationary probability vectorπe,i marked as π0e,i,π1e,i,π2e,i,…,πLie,i.Based on [26], the stationary probabilities vector πs,i of the SMP model is denoted as π0s,i,π1s,i,π2s,i,…,πLis,i, and(18)πjs,i=πje,i×EHji∑k=0Liπke,i×EHki,0≤j≤Li,where Hji represents the sojourn time of state j. The backoff interval of the backoff stage j is modeled with the state sojourn time, which is a random variable uniformly chosen within the range 0,Wi,j, for 0 ≤ j ≤ Li.Since high priority ACs’ AIFSs will affect low priority ones, the probability for each AC’s backoff counter to decrease one may not be identical. Letpbi be the backoff blocking probability. For a given backoff instance of AC[i] in a vehicle, pbi equals the possibility that the vehicle senses other vehicles using the channel or other ACs in the same vehicle are attempting transmissions. Due to the bigger AIFSNs, the lower priority ACs are deferred for a longer time than higher priority ones, which is shown in Figure 5. Hence, pbi is computed by the following:(19)pbi=1−∑k=0∞1−τkNcs−1kk!e−Ncs−1∏j=0j≠i31−ϖjAi+1,then, the average slot time σi¯ for each AC in a vehicle is obtained by the following:(20)σi¯=pbiTtr+1−pbiσ,and the normalized slot time for each AC in a vehicle is written as follows:(21)σi¯=σi¯σ.Figure 5
Illustration of the impact of different AIFSNs on backoff blocking probability.Therefore, the expected value of state sojourn timeEHji for state j of the semi-Markov process of AC[i] is given by the following:(22)EHji=Wi,j2σi¯,0≤j≤Li.For the given backoff instance of AC[i], it will visit state 0 successively after successfully escaping from the virtual collision in backoff stage j, 0 ≤ j ≤ Li, and after a packet drop in backoff stage Li. Hence, the excepted number of consecutive visits to state 0 is 1/1−1−pvi, and the expected value of state sojourn time for state 0 is as follows:(23)EH0i=Wi,02σi¯×1pvi=Wi,02pviσi¯.Using equation (18) and ∑j=0Liπjs,i=1, the stationary probabilities of the SMP of AC[i] are given by the following:(24)π0s,i=12Bipvi,π1s,i=1Bi,πjs,i=2pvij−1Bi,2≤j≤Mi,2Mi−1pvij−1Bi,Mi<j≤Li,where(25)Bi=1−2pviMi+12pvi1−2pvi+2Mi−1pviMi−pviLi1−pvi.The stationary probabilityπjs,i of the SMP represents the fraction of time spent by AC[i] in backoff stage j.In the following part, we exploit the stationary probability distribution of the SMP model and the state sojourn times to derive the packet transmission probabilityτ, conditional collision probability (i.e., external collision probability), and saturated network throughput. The internal transmission probability ϖi is computed as follows:if the backoff instance of AC[i] is in state j, it will transmit once after an expected time interval E[Hj], for 1 ≤ j ≤ Li. For state 0, AC[i] transmits once after an expected time interval of EH0/1/pvi. Hence, ϖi can be expressed as follows:(26)ϖi=π0s,i1/pviEH0+π1s,iEH1+⋯+πLis,iEHLi=1−pviLi+1BiWi,0pvi1−pviσi¯.So far, we have derived the internal transmission probability of AC[0]-AC [3] from the proposed SMP model and we can get the packet transmission probability τ by combining equations (8)–(10).LetSi be the saturation throughput for each AC in a station. Define Ptr as the possibility of at least one node in the transmission range transmitting in the considered slot time, Ps,i as the probability that a transmission attempt of AC[i] is successful conditioned on the fact that at least one node transmitting in the considered slot time, and Pfc as the probability that a transmission attempt fails owing to a collision conditioned on the fact that at least one node transmitting in the considered slot time. Thus, we have the following:(27)Ptr=1−∑k=0∞1−τkNtrk/k!e−Ntr=1−e−Ntrτ,Ps,i=Ntr×τi×∑k=0∞1−τkNcs−1k/k!e−Ncs−1Ptr,i=0,1,2,3,Pfc=1−∑k=0∞1−τkNtrk/k!e−Ntr−Ntr×τ×∑k=0∞1−τkNcs−1k/k!e−Ncs−1Ptr,and Si is derived by(28)Si=Ps,i×Ptr×EP1−Ptrσ+∑i=03Ptr×Ps,i×ts,i+Ptr×Pfc×tc,i,where the expressions of ts,i, and tc,i are given by(29)ts,i=tc,i=Ttr+AIFSi.


## 5. Simulations

In this part, we conduct the experiments using MATLAB. First, the essential network parameters (τ, pc, S) of VANET are calculated via the proposed SMP model where S=∑i=03Si is the aggregate throughput for all ACs, i.e., the overall throughput of each AC in a vehicle. Second, we evaluate the computation time for the proposed SMP model. To show our proposed model is less complex with high accuracy, we compare the experimental results from the proposed model with the results from the existing Markov chain-based models. In our study, we take Yao et al. model [12] as an example. The values of τ and pc derived by Yao et al. model (by setting ρi and pai in the study equal to 1) are denoted as τB and pB.The parameters of the freeway scenario are listed in Table3. The fixed-point iteration method is adopted to compute the conditional collision probability (pc) and packet transmission probability (τ). These results were further used for calculating the saturated throughput of the network (though the formula of network throughput is not presented in Yao’s paper, it can be derived in the same way as equation (28)). The input DSRC communication parameters are presented in Table 4. These calculations are carried out for different vehicle densities and the outputs obtained are compared with those from Yao et al. model (τB, pB, and SB). The results obtained from these two models are listed in Table 5.Table 3
Parameters of highway scenario.
ParametersValueHighway length1000 mDensity (β)0.01∼0.1 vehicles/mAverage vehicle distance100 m∼10 mTotal number of vehicles10∼100Transmission range (R)500 mCarrier sensing range (Lcs)700 mTable 4
Parameter settings of DSRC communication.
General parametersValueData rate (Rd)24 MbpsBasic rate (Rb)6 MbpsSlot time (σ)9μsecSIFS time16μsecDIFS = SIFS + 2 × slot time34μsecPropagation delay (δ)1μsecData payload length (E(P))200 octetsMAC sublayer overhead28 octetsPHY layer overload20μsecRetry limitL7aCWmin63aCWmax1023Table 5
Comparison of (τ, pc, S) and (τB, pB, SB) for different vehicle densities, respectively.
N(τ, pc, S)(τB, pB, SB)2(0.0740, 0.1248, 310.49 kB/s)(0.0729, 0.1236, 312.56 kB/s)3(0.0625, 0.1813, 384.74 kB/s)(0.0630, 0.1789, 382.98 kB/s)5(0.0511, 0.2640, 466.77 kB/s)(0.0502, 0.2569, 467.76 kB/s)10(0.0397, 0.4030, 523.69 kB/s)(0.0399, 0.4052, 519.71 kB/s)20(0.0319, 0.5772, 496.73 kB/s)(0.0327, 0.5775, 493.79 kB/s)30(0.0287, 0.6915, 439.51 kB/s)(0.0292, 0.6926, 441.52 kB/s)40(0.0270, 0.7729, 379.84 kB/s)(0.0273, 0.7738, 381.56 kB/s)50(0.0259, 0.8326, 323.07 kB/s)(0.0256, 0.8330, 321.10 kB/s)60(0.0252, 0.8768, 271.01 kB/s)(0.0251, 0.8771, 271.06 kB/s)70(0.0248, 0.9095, 224.43 kB/s)(0.0249, 0.9102, 221.48 kB/s)80(0.0245, 0.9338, 183.64 kB/s)(0.0247, 0.9343, 186.68 kB/s)90(0.0242, 0.9517, 148.59 kB/s)(0.0244, 0.9519, 145.63 kB/s)100(0.0241, 0.9648, 119.02 kB/s)(0.0240, 0.9654, 116.07 kB/s)We can readily observe from Table5 that the results of the proposed model are close to those of Yao’s model with a maximum deviation of 0.1% for saturated throughput S. As β increases, the number of vehicles in the transmission range of the reference vehicle increases which results in p increasing and τ decreasing for both two models. Especially, while β increases, S steadily grows until it reaches its maximum value, then declines to zero as β ⟶ ∞. This trend is predictable referring to [6] and consistent with Yao’s model. For better illustration, the comparisons between the theoretical results from Yao’s model and the SMP model with the simulation results are presented in Figures 6–8. It is apparent that both the theoretical curves match the simulation result very well which validates the accuracy of our model.Figure 6
Packet transmission probabilities (τ) with different vehicle densities.Figure 7
Conditional collision probabilities (p) with different vehicle densities.Figure 8
Aggregate throughputs of each AC (S) with different vehicle densities.For the computation time, it is acquired by exploiting the MATLAB commandstic and toc. Table 6 shows the MATLAB implementation times for the two models. It is visible that the computation times for both two models remain no change with different vehicle densities. More importantly, as the state number of our model is with the order of OL and the state number of Yao’s model is with the order of O2L, the proposed SMP model only uses nearly one-tenth of the time spent for computing the stationary probabilities of Yao’s model, which proves the proposed SMP model is more effective than the existing Markov chain-based models.Table 6
Comparison of computational time for Yao’s model (CB) and our model (C).
NCB (in seconds)C (in seconds)28.0580250.79587638.6087320.78176858.2020350.750957108.1753750.809911208.1361410.821079307.9889310.787711408.5632710.816115508.3615510.811665608.0631190.804857707.8731880.792516808.5896300.847394908.1325920.8372101007.6240870.791316


## 6. Conclusions

In this study, we model the network performance of IEEE 802.11p EDCA for vehicular safety communication using the semi-Markov process. The newly constructed SMP model considers the impacts of virtual collisions and varying priorities among different ACs inside each EDCA station. Also, the output parameters including the packet transmission probability, conditional collision probability, and saturated throughput are calculated. Furthermore, the accuracy and conciseness of the proposed model are validated by experimental results.



---

*Source: 7548608-2022-10-22.xml*