# Improvement and Performance Evaluation of IEEE 802.11p Protocol in Dense Scenario of VANET

Authors: Zufang Dou; Xingkai Zhou; Qiaoli Yang; Liben Yang; Jianwen Tian
Journal: Mobile Information Systems
 (2022)

---

## Abstract

In vehicle nodes dense networks, the existing IEEE 802.11p protocol cannot guarantee effective data transmission efficiency because of the aggravation of the collision between nodes. In the cluster-based network, to ensure the effective transmission of data packets, this paper proposes an improved IEEE 802.11p protocol combined with TDMA, which is suitable for dense scenarios. At the same time, the performance of the improved mechanism is analyzed by establishing a two-dimensional Markov model, and the performance indexes such as system transmission rate and delay are obtained. Finally, the improved mechanism is simulated and evaluated, and the influence of the number of nodes and cluster heads on the system communication performance is studied. To a certain extent, it can guide the deployment of roadside facilities and the optimization of cluster heads in VANET.


---

## Body

## 1. Introduction

Wireless vehicular ad hoc network (VANET) is composed of vehicles, pedestrians, and roadside communication nodes. The nodes in the network cooperate with each other, which can perceive the surrounding traffic environment and interact in real time and improve road safety by preventing accidents. Therefore, VANET improves road safety by preventing accidents. In VANET, mobile vehicles and pedestrians can be used to create on-board networks. Each vehicle and pedestrian within the transmission range and road side unit (RSU) can be used as the communication node or router. The node supports communication within the transmission range of 100 to 500 m, and it can expand the transmission range by establishing multiple hops. Therefore, information about the status of road and vehicle nodes can be transmitted to every node. The VANET has very high application value. It not only supports safe applications, including vehicle collision warning, accident reminder, and emergency broadcast but also supports nonsafety applications such as information sharing, riders’ mutual assistance, and multimedia entertainment.MAC protocol is an access protocol for controlling nodes to use limited wireless channels. The research of MAC protocol can improve channel utilization, reduce delay, ensure channel fairness, and reduce network congestion. The IEEE.802.11p protocol based on CSMA/CA uses a back-off mechanism and nodes’ access channels through competition [1–4]. The CSMA/CA mechanism can coordinate nodes’ access channels at different time points. The number of nodes has little influence on channel access. Even if the number of nodes in the network is too large, access performance will decrease, but the mechanism can still maintain a certain availability without clock synchronization. Therefore, the IEEE.802.11p protocol is mostly used in VANET.Because the nodes in VANET move fast and the topology changes dynamically, there are high requirements for the effectiveness of message transmission. With the increase of urban car ownership year by year, in peak travel and holidays, the traffic flow is very large, and the node-intensive scene has become increasingly common. The efficient communication in this scene has become a problem that cannot be ignored in VANET. However, in high-density networks, competition-based CSMA/CA mechanisms exacerbate node-to-node collisions and do not guarantee lower latencies. Thus, the transmission efficiency of the network will be greatly reduced, which has a serious impact on the transportation system. In particular, when traffic accidents and other emergencies cannot be effectively transmitted, it will cause significant economic losses and human casualties. Therefore, ensuring effective communication in dense scenarios is a critical issue for VANET.In VANET, nodes periodically broadcast beacon packets using the IEEE 802.11p-based broadcast communication technology, which includes the location information, moving speed, and identification number. And these packets can also provide relevant data for planning travel routes and safe driving of cars. When data conflict occurred, the node enters the back-off state, and the size of the back-off window will increase according to the protocol. It may result in long waiting time and low collision probability for nodes because of the DCF mechanism uses a binary exponential back-off algorithm. However, in dense vehicles network, the number of vehicle nodes in same competing channel increases, resulting in increase of collision rate and decrease of transmission rate. Conversely, in sparse vehicles network, choosing larger competing window may cause long-term channel idleness, and the efficacy of beacon transmission cannot be guaranteed, which seriously affects the performance of communication mechanism in VANET. Therefore, the size of back-off window is the key factor affecting the performance of VANET, especially in dense networks.To address these issues and improve the performance of VANET in dense scenarios, in a cluster-based network, this paper presents an improved IEEE 802.11p protocol combined with TDMA, to improve transmission efficiency by improving the successful transmission rate of retransmitted data. At the same time, a two-dimensional Markov model is established to analyze the performance of the mechanism, and the analytical expressions of the system delay, transmission rate, and other indicators are obtained. Finally, the mechanism is simulated and the system transmission rate and delay are evaluated. The influence of the number of nodes and clusters on system performance is discussed. The performance evaluation results show that the network model greatly improves the communication performance in dense node scenarios.The contributions of this paper are as follows:(1)
This paper presents an IEEE.802.11p protocol for dense scenarios(2)
This paper studies the vehicle network based on cluster structure and establishes a mathematical model with the number of cluster heads and nodes as important parameters(3)
This paper studies the influence of the number of vehicle nodes on network performance in dense scenarios(4)
This paper provides theoretical support for the optimization of clusters and the deployment of roadside facilities in dense scenarios


## 2. Related Works

The VANET could be considered as a special practical application of wireless ad hoc networks because of its network characteristics, such as highly dynamic topology, strict delay requirements, high speed of node movement, predictable trajectory, and accurate positioning. Moreover, its research covers many fields including intelligent transportation, computer networks, and wireless communications. The application prospect of VANET is bright and broad, which received great attention from both academia and industry.In recent years, many scholars have done a great deal of research on the MAC protocol of VANET. Present researches are mainly centered on improving the protocol, evaluating the performance, and modeling the channel. In terms of protocol improvement, literature [5] designed a hybrid protocol of time division multiple access and carrier sensing. It improves the utilization rate of the shared channel and reduces the scheduling overhead. Literature [6] proposed a multihop clustering technology applied in VANET, which eliminates malicious nodes by finding the most trusted cluster head in the cluster. This method can effectively improve the transmission efficiency and stability of nodes in the network. Literature [7] designed a Q-learning reward mechanism for sharing wireless channels among multiple vehicles to maximize the transmission of packets. This mechanism effectively improves the utilization of bandwidth, reduces waste of channel resources, and optimizes priority issues. Literature [8] proposed a communication mechanism named CARHet (Context-AwaRe Heterogeneous V2V communications) for multilink and multi-RAT vehicle networks. The simulation results verify that the communication mechanism can help to solve the challenge of bandwidth and scalability requirements on vehicle networks in the future. In terms of performance evaluation, Bianchi analyzed the performance of IEEE 802.11 Distributed Coordination Function (DCF) by establishing Markov chain model [9]. For safety applications of VANETs based on IEEE 802.11p/bd, literature [10] developed a SINR-based model to evaluate the service quality. Literature [11] presents a Markov chain analysis model that evaluates the performance of IEEE 802.11 MAC in VANET. The relationship between performance indicators and parameters is derived. Finally, two access mechanisms, CSMA/CA and RTS/CTS, are compared. However, the performance of IEEE 802.11 MAC in node-intensive scenarios is not evaluated. Literature [12] studies the impact of the IEEE 802.11p MAC layer on the vehicle navigation terminal by establishing an analytical model. However, this study does not evaluate the impact of MAC layer parameters and the number of nodes on the communication mechanism in detail. Literature [13] established a Markov chain analysis model to analyze the performance of IEEE 802.11 DCF under different competition window sizes. Based on the simulation results, the expressions of channel busy probability, successful transmission probability, and conflict probability are derived. Literature [14] simulates the beacons of different time intervals and analyzes the performance of the IEEE 1609.4 MAC layer. However, the impact of messages other than beacons on communication mechanism is not considered.While many areas in the MAC mechanism performance and evaluation have improved over time, as shown in Table1, performance in dense scenarios has not been changed a lot. Therefore, this paper mainly focuses on the dense scenario to improve the communication performance in this scenario.Table 1
Comparison of some existing protocols of VANET.
PaperResearch contentMethodDense scenesSimulatorYear[14]Performance evaluationFlooding technology×OMNeT++2017[13]Performance evaluationMarkov chain model×MATLAB2018[7]Improvement of protocolQ-learning reward mechanism×OMNeT++2019[12]Performance evaluationMarkov chain model×MATLAB2019[6]Improvement of protocolAdvanced clustering technique based on multihop×NS-22020[11]Performance evaluationMarkov chain model×MATLAB2020[5]Improvement of protocolHybrid protocol of TDMA and CSMA×NS-32021[8]Improvement of protocolHeterogeneous V2V communication algorithm×VEINS2021[10]Performance evaluationModel based on SINR√NS-22021The applicability of IEEE 802.11p has been fully tested and passed various scenario tests, such as throughput under the line of sight propagation conditions, hidden terminal problems, fading, and collision [15, 16]. However, most of these tests are carried out in sparse scenes, and satisfactory performance is obtained. In a dense node network, when the number of vehicles increases, channel congestion will increase, resulting in reduced communication performance [17]. Literature [18] analyzes the correlation between vehicle density and network congestion. Simulation results show that in high vehicle density, there will be more serious congestion, lower throughput, and higher packet loss rate. An efficient evaluate all integer partition (EAIP) algorithm is proposed based on an improved IEEE 802.11 DCF model in literature [19]. The results show that the EAIP algorithm is better than the existing ROIP algorithm. However, it only considers a small number of nodes and does not consider the performance of the algorithm when the number of nodes is larger. In the environment of dense distribution of nodes, literature [20] proposed the transmitting opportunity control (TOC) method. By prohibiting the transmission of some terminals near the access point, higher communication priority is provided for the terminals far away from the access point, so as to improve the minimum uplink (UL) throughput of the system. It only considers the improvement of the minimum UL throughput of the system and does not optimize other performance indicators. Literature [21] proposed a cluster-based channel allocation scheme, which is a centralized algorithm for minimizing channel interference. It is composed of two modules: RSS-Aware Channel Selection Module (RCSM) and Interference-Aware Clustering Module (ICM). RCSM can calculate the channel with less interference. ICM can reduce the channel conflict with adjacent access points by reasonably optimizing the interference domain of the wireless network. Simulation results show that the proposed channel allocation scheme has a significant improvement in throughput compared with the traditional scheme. In literature [22], an adaptive particle swarm optimization algorithm is proposed. Its performance is compared with TPC in ieee802.11n dense topology network, and OPNET simulation is used in high-density scenes. The simulation results show that in terms of throughput gain, Physical Carrier Sensing (PCS) obtains a higher total throughput gain, while Transmit Power Control (TPC) obtains a relatively low gain. Literature [23] proposed a decentralized power allocation scheme based on deep reinforcement learning (DRL) to optimize the power consumption and transmission delay of the system. In this scheme, the deep deterministic policy gradient (DDPG) algorithm was used to learn the optimal power allocation scheme. To solve the problems of access fairness and data freshness, literature [24] proposed a multiobjective optimization scheme of mobile edge computing (MEC) assisted queuing network, which can adjust the size of the contention window through vehicle speed. Literature [25] established a model and analyzed the time-dependent performance based on IEEE 802.11p when the vehicles in the fleet encountered interference. It is verified that IEEE 802.11p can maintain the stability of communication under disturbance.For the communication mechanism of the VANET, the current references focus on channel allocation, throughput, the protocol algorithm, and the performance evaluation, etc. The communication performance of the cluster-based VANET is rarely considered in dense nodes’ scenes. In addition, effective communication access mechanisms are lacking in dense scenarios. On the basis of literature [3], a more efficient MAC mechanism is proposed to apply to dense nodes’ scenarios in this paper. Then, by establishing a new Markov chain model, the performance of the entire mechanism is evaluated. At the same time, the influence of the number of vehicles on the system performance is also discussed in the simulation section.


## 3. Proposed Protocol

In this part, we introduced the cluster-based network architecture of VANET and the main assumptions in this paper. Then, we present an improved IEEE 802.11p protocol combined with TDMA to improve transmission efficiency of vehicle nodes by increasing the transmission rate of retransmitted packets.


### 3.1. System Design

The network topology of the VANET used in this paper is shown in Figure1, in which the vehicles are divided into clusters. In each cluster, a vehicle is selected as the cluster head (CH). There are two different devices—On Board Unit (OBU) equipped inside the vehicle and road side unit (RSU) located next to the lane. The OBUs adopt V2V communication between each other and V2I communication to RSU. The OBUs in the same cluster communicate through the time division multiple access (TDMA) protocol, and the carrier-sense multiple access with collision avoidance (CSMA/CA) mechanism of IEEE802.11p is used for communication between the clusters. Taking security application messages as an example, the OBU in the cluster first uploads the messages to the CH through TDMA protocol, and the CH uploads the messages to RSU according to IEEE 802.11p protocol, and finally deliver it to the control center. In the dense nodes scenario, this cluster-based network can effectively reduce the competition between OBUs and realize effective transmission by reducing the number of OBUs directly communicating with RSU.Figure 1
Architecture of VANET.The assumptions of this paper are as follows:(1)
The number of Cluster Members (CMs) is equal in all clusters(2)
All CHs are within the radiorange of another CH, so there are no hidden terminals(3)
The channel frequency of intracluster communication is different from that of adjacent clusters(4)
The cluster head has been selected


### 3.2. Protocol Mechanism

Based on the cluster-based network architecture of VANET, an improved IEEE 802.11p protocol combined with TDMA is proposed in this part, as shown in Figure2.Figure 2
The basic process of data transmission in proposed protocol.Figure2 describes the basic process of data transmission in the improved IEEE 802.11p protocol combined with TDMA. CHs use the TDMA protocol to collect data from each Cluster Member (CM) and send the data to RSU through the nonbeacon-enabled CSMA/CA protocol. Therefore, this model is divided into two phases, namely, the TDMA phase and the contention phase. For each cluster structure, the CH allocates communication time to Cluster Members (CMs) through broadcast beacon, and each CM uploads information to its CH in the allotted time, as shown in the TDMA phase of Figure 2. When the transmission is saturated, it means that every member in the cluster transmits data packets to the cluster head; when the transmission is unsaturated, it means that some members in the cluster do not transmit data packets to the cluster head. In the second stage, all CHs begin the contention channel and upload data to RSU, according to IEEE 802.11p protocol. Moreover, the CH only transmits one packet at a time. That is, the CMN+1 packets of CH need CMN+1 times of competition, considering that the number of CMs is CMN.Figure3(a) depicts the basic IEEE 802.11p protocol proposed in the literature [3]. The basic process of the IEEE802.11p protocol mechanism in literature [3] can be summarized as follows:Step 1.
To start data transmission, the node initializes the following three parameters: number of back-offs (NB=0), back-off exponent (BE=macMinBE), and Retransmission Times (RT=0).Step 2.
The node first waits for a random time interval in the range of0,2BE−1. Next, the node performs clear channel assessment (CCA) to check whether the channel is idle.Step 3.
If the channel is observed free, the node will send the packet and wait for receiving the ACK packet.Step 4.
If the channel is observed busy, the node determines whether the values of NB are greater than macMaxCSMABackoffs. If NB is not greater than macMaxCSMABackoffs, BE and NB are added as one unit and return to step2. The increase of the value of BE increases the length of the competition window, and the growth process will continue until BE is equal to macMaxBE. After this, BE remains unchanged. If the number of consecutive tries to access the channel is greater than macMaxCSMABackoffs, the channel access fails and the data packet is dropped.Step 5.
When the node receives the ACK packet, it indicates that the packet was successfully transmitted. If the node does not receive the ACK packet, it implies that there is a collision. The next step is to determine if the value of RT is greater than macMaxFrameRetries.Step 6.
If a collision occurs, the value of RT is added as one unit until it equals the macMaxFrameRetries and the node return step1 to access the channel again.Step 7.
If RT is greater than macMaxFrameRetries, it implies that the transmission failed and the packet is dropped.Figure 3
(a) The basic flow chart of IEEE 802.11p protocol. (b) The basic flow chart after improving.
(a)(b)Although the basic IEEE 802.11p protocol can ensure the effectiveness and fairness of node transmission, its disadvantages are also obvious in node dense networks. When the transmission of conflict occurs (the channel is busy), the node enters the back-off state and increases the size of the back-off window. Similarly, when the channel is idle but the data transmission fails, the node will enter the back-off state and initialize the size of the back-off window. This is reasonable in the scene with sparse nodes, since the node does not need to increase the wait time when the channel is idle, and the contention window setting to the minimum value can reduce the waiting time of the node, so as to reduce the transmission delay. However, in the scenario of dense nodes, this is bound to increase the number of competing nodes, the probability of competition and conflict between nodes, and finally reduce the successful transmission rate. Especially, with the increase of the number of nodes, the communication system has serious consequences or even collapse.Therefore, we propose a new communication mechanism to cope with these issues in Figure3(b). When the channel is idle but the data transmission fails, the node will enter the back-off state keeping the original window size. In essence, the window size represents the current node density, so maintaining the window size can effectively reduce the node competition, the node collision probability, and improve the successful transmission rate. The end of transmission is divided into three cases: successful transmission, failed transmission, and channel access failure.The process of improved mechanism in this paper just changes step6 to step 6∗, and the other steps remain unchanged. The Step 6∗ is shown below.Step 6.
∗If a collision occurs, the value of RT is added as one unit until it equals the macMaxFrameRetries and the node return step2and records the previous number of back-offs without resetting BE and NB.The advantages of the optimized mechanism are as follows:(1)
The proposed mechanism is designed for the node dense environment to solve the problem of aggravating conflict when the number of nodes is large(2)
By recording the number of node back-offs, this mechanism can effectively reduce node collision and improve the data transfer rate(3)
When a node fails to transmit packets, the node enters into back-off state, which is helpful for the node to find a suitable time for its own access channel. In addition, it can optimize the allocation of channel resources according to the communication conditions of the node and effectively improve the utilization of channel resources(4)
The optimized IEEE802.11p protocol improves data transmission rate compared with the original protocol. By recording the number of back-offs of data packets, the node can reach the maximum back-off times faster, so as to reduce the competition of the system and increase the system throughput


## 3.1. System Design

The network topology of the VANET used in this paper is shown in Figure1, in which the vehicles are divided into clusters. In each cluster, a vehicle is selected as the cluster head (CH). There are two different devices—On Board Unit (OBU) equipped inside the vehicle and road side unit (RSU) located next to the lane. The OBUs adopt V2V communication between each other and V2I communication to RSU. The OBUs in the same cluster communicate through the time division multiple access (TDMA) protocol, and the carrier-sense multiple access with collision avoidance (CSMA/CA) mechanism of IEEE802.11p is used for communication between the clusters. Taking security application messages as an example, the OBU in the cluster first uploads the messages to the CH through TDMA protocol, and the CH uploads the messages to RSU according to IEEE 802.11p protocol, and finally deliver it to the control center. In the dense nodes scenario, this cluster-based network can effectively reduce the competition between OBUs and realize effective transmission by reducing the number of OBUs directly communicating with RSU.Figure 1
Architecture of VANET.The assumptions of this paper are as follows:(1)
The number of Cluster Members (CMs) is equal in all clusters(2)
All CHs are within the radiorange of another CH, so there are no hidden terminals(3)
The channel frequency of intracluster communication is different from that of adjacent clusters(4)
The cluster head has been selected


## 3.2. Protocol Mechanism

Based on the cluster-based network architecture of VANET, an improved IEEE 802.11p protocol combined with TDMA is proposed in this part, as shown in Figure2.Figure 2
The basic process of data transmission in proposed protocol.Figure2 describes the basic process of data transmission in the improved IEEE 802.11p protocol combined with TDMA. CHs use the TDMA protocol to collect data from each Cluster Member (CM) and send the data to RSU through the nonbeacon-enabled CSMA/CA protocol. Therefore, this model is divided into two phases, namely, the TDMA phase and the contention phase. For each cluster structure, the CH allocates communication time to Cluster Members (CMs) through broadcast beacon, and each CM uploads information to its CH in the allotted time, as shown in the TDMA phase of Figure 2. When the transmission is saturated, it means that every member in the cluster transmits data packets to the cluster head; when the transmission is unsaturated, it means that some members in the cluster do not transmit data packets to the cluster head. In the second stage, all CHs begin the contention channel and upload data to RSU, according to IEEE 802.11p protocol. Moreover, the CH only transmits one packet at a time. That is, the CMN+1 packets of CH need CMN+1 times of competition, considering that the number of CMs is CMN.Figure3(a) depicts the basic IEEE 802.11p protocol proposed in the literature [3]. The basic process of the IEEE802.11p protocol mechanism in literature [3] can be summarized as follows:Step 1.
To start data transmission, the node initializes the following three parameters: number of back-offs (NB=0), back-off exponent (BE=macMinBE), and Retransmission Times (RT=0).Step 2.
The node first waits for a random time interval in the range of0,2BE−1. Next, the node performs clear channel assessment (CCA) to check whether the channel is idle.Step 3.
If the channel is observed free, the node will send the packet and wait for receiving the ACK packet.Step 4.
If the channel is observed busy, the node determines whether the values of NB are greater than macMaxCSMABackoffs. If NB is not greater than macMaxCSMABackoffs, BE and NB are added as one unit and return to step2. The increase of the value of BE increases the length of the competition window, and the growth process will continue until BE is equal to macMaxBE. After this, BE remains unchanged. If the number of consecutive tries to access the channel is greater than macMaxCSMABackoffs, the channel access fails and the data packet is dropped.Step 5.
When the node receives the ACK packet, it indicates that the packet was successfully transmitted. If the node does not receive the ACK packet, it implies that there is a collision. The next step is to determine if the value of RT is greater than macMaxFrameRetries.Step 6.
If a collision occurs, the value of RT is added as one unit until it equals the macMaxFrameRetries and the node return step1 to access the channel again.Step 7.
If RT is greater than macMaxFrameRetries, it implies that the transmission failed and the packet is dropped.Figure 3
(a) The basic flow chart of IEEE 802.11p protocol. (b) The basic flow chart after improving.
(a)(b)Although the basic IEEE 802.11p protocol can ensure the effectiveness and fairness of node transmission, its disadvantages are also obvious in node dense networks. When the transmission of conflict occurs (the channel is busy), the node enters the back-off state and increases the size of the back-off window. Similarly, when the channel is idle but the data transmission fails, the node will enter the back-off state and initialize the size of the back-off window. This is reasonable in the scene with sparse nodes, since the node does not need to increase the wait time when the channel is idle, and the contention window setting to the minimum value can reduce the waiting time of the node, so as to reduce the transmission delay. However, in the scenario of dense nodes, this is bound to increase the number of competing nodes, the probability of competition and conflict between nodes, and finally reduce the successful transmission rate. Especially, with the increase of the number of nodes, the communication system has serious consequences or even collapse.Therefore, we propose a new communication mechanism to cope with these issues in Figure3(b). When the channel is idle but the data transmission fails, the node will enter the back-off state keeping the original window size. In essence, the window size represents the current node density, so maintaining the window size can effectively reduce the node competition, the node collision probability, and improve the successful transmission rate. The end of transmission is divided into three cases: successful transmission, failed transmission, and channel access failure.The process of improved mechanism in this paper just changes step6 to step 6∗, and the other steps remain unchanged. The Step 6∗ is shown below.Step 6.
∗If a collision occurs, the value of RT is added as one unit until it equals the macMaxFrameRetries and the node return step2and records the previous number of back-offs without resetting BE and NB.The advantages of the optimized mechanism are as follows:(1)
The proposed mechanism is designed for the node dense environment to solve the problem of aggravating conflict when the number of nodes is large(2)
By recording the number of node back-offs, this mechanism can effectively reduce node collision and improve the data transfer rate(3)
When a node fails to transmit packets, the node enters into back-off state, which is helpful for the node to find a suitable time for its own access channel. In addition, it can optimize the allocation of channel resources according to the communication conditions of the node and effectively improve the utilization of channel resources(4)
The optimized IEEE802.11p protocol improves data transmission rate compared with the original protocol. By recording the number of back-offs of data packets, the node can reach the maximum back-off times faster, so as to reduce the competition of the system and increase the system throughput


## 4. Performance Analysis

In order to verify the efficiency of the improved mechanism, the performance of the improved mechanism is analyzed in this part. Firstly, the improved mechanism is modeled by Markov model, and the number of nodes and cluster heads in the cluster are the main parameters. Secondly, the performance indexes such as transmission rate and delay of the improved mechanism are obtained.


### 4.1. Markov Chain Model

A Markov chain model is considered to characterize the execution process of the node during the contention phase. Figure4(a) is the Markov chain model of CSMA/CA protocol proposed in literature [3], and Figure 4(b) is the nonbeacon-enabled CSMA/CA Markov chain model proposed in this paper. Bn,m represents block B in Figure 4(c), respectively, and n and m are the number of back-off state and the number of packet retransmission. The block CB in Figure 4(c) represents that the Markov chain model is constructed by block B and the connections between them. All successful outputs of block B are connected to the outputs of block CB.Figure 4
(a) The Markov chain model of basic CSMA/CA protocol. (b) The Markov chain of nonbeacon-enabled CSMA/CA improved protocol. (c) The CB block.
(a)(b)(c)In Figure4, as described in the protocol in literature [3], when the node successfully accesses the channel but the data transmission fails, the values of Number of Back-offs (NB) and Back-off Exponent (BE) all return to the initial values, and Retransmission Times (RT) adds 1. That is, the node retries to access the channel after waiting for a random time interval in0,W0. At this time, the node has lost the number of failed access channels, it increases the chance for reaccessing channel, which slows down the node from reaching its maximum number of back-off. During the retransmit process, competition between nodes increases, as well as collision probability and channel occupancy. Indirectly, the probability of successful transmission decreases.In the improved protocol, the values of BE and NB are remained unchanged when node successfully accesses the channel but the data transmission fails. In particular, after failed transmission, the node maintains its previous number of back-offs. So the maximum number of back-off can be reached faster in this situation. More importantly, compared with the original protocol, the node back-off time increases. It increases the transmission opportunities of nodes and reduces the competition between nodes which means the conflict rate are lower. It implies that the improved mechanism in this paper has a higher probability of transmission successfully and throughput.To exemplify this, consider using a example. In the original mechanism, the node first tries accessing channel fromB0,0 state. After the node unsuccessfully accesses channel k1 times, the node inters state Bk1,00≤k1≤n. Then, it successfully accesses channel but the data transmission failed, and the node back off to the next row state Bk1,1. Next, the node tries to access channel at Bk1,1 state, if after the node unsuccessfully accesses the channel k2 times0≤k2≤n−k1, the packet is successfully transmitted in state Bk1+k2,1. In short, the node’s first attempt to send packets at state Bk1,0 and successfully sent data packets at Bk1+k2,1 after 1 times retransmission and k1+k2 times access failure of node.A new Markov chain model is presented for the case where the nonbeacon-enabled CSMA/CA protocol only attempts to transmit once, as shown in Figure5. This model is only used for an attempt to send a data packet, so it enters into the channel access failure state after once failed access. If the node can successfully access the channel after performing CCA for the first time, it will send a data packet. Otherwise, the node will enter into the channel access failure state. The model can be extended to be applied to limited retransmission.Figure 5
Markov chain model with one time of attempting to send data packets.When a node transmits a data packet, it waits for a random time interval within0,2BE−1. The size of the contention window isWi,j. Respectively, i and j are the number of channel access failures and the number of packet retransmission. When performing CCA, if the channel access is successful, the node enters the packet transmission state. In the next step, the node waits to receive the ACK packet, and the probability of collision is PC. If the node receives the ACK packet, it indicates that the data packet is successfully transmitted. If data was not successfully accepted within the timer, it implicit the packet transmission fails. In CCA state, if the channel is busy, then the channel access fails, and data packets fail to be transmitted. Here, the probability of channel observed busy is α. The symbols used in this paper are listed in Table 2.Table 2
Variable definitions.
VariableMeaningBi,jProbability of occurrence ofBi,jPBeaconProbability of beacon statePTDMASteady-state probability of TDMA statePCBSum of steady-state probabilities of CB statesPTSteady-state probability of each state in TDMA phasePBi,jSum of steady-state probabilities of allBi,j statesPBacki,jSteady-state probability of each back-off statePCCAi,jSteady-state probability of each CCA statePAti,jSteady-state probability of each ACK accepting timeout statePrAi,jSteady-state probability of each ACK accepted stateLDNumber of states for packet transmissionLACKACK status numberLAtACK acceptance timeout status numberCMNNumber of members in the clusterCNNumber of cluster headsPCCollision probabilityαProbability of being busy in CCA stateτSum of steady-state probabilities of CCA state in CBnmacMaxCSMABackoffsmmacMaxFrameRetriesLetPBeacon be the probability of the beacon state. It is assumed that all steady-state probabilities of TDMA state are equal, expressed as PT. Because these states have only one entrance and one exit, they are locally continuous states. In addition, PBeacon is equal to PT. CMN represents the number of Cluster Members, and LD represents the number of states required for transmission. The steady-state probability of the TDMA cycle can be expressed as
(1)PTDMA=CMN⋅LD⋅PT.The entry probability of each CB is also equal toPT. From the Markov competitive model in Figure 4(b), Equation (2) is obtained, which represents the steady-state probability of each stage.
(2)B0,0=PT,Bi,0=α⋅Bi−1,0=αi⋅PT;i>0,B0,j=PC⋅1−α⋅B0,j−1=PC⋅1−αj⋅PT;j>0,Bi,j=i+j!i!j!PC⋅1−αj⋅αi⋅PT;i,j>0.In the model proposed in this paper,B0,0 is the probability of the entrance, and its value is equal to PT. Bi,0 represents the steady-state probability of i times back-off. Similarly, B0,j represents the steady-state probability of j time retransmissions, and Bi,j represents the steady-state probability of i time back-off and j time retransmissions. Its steady-state probability can be derived from Markov chain model.The derivation of the expressionBi,j is as follows:
(1)
Based on the Markov chain model, the expressions ofB0,1, B1,1, and B2,1 are obtained, and the expressions of Bn,1 are derived by observation method(2)
In the same way, by observing the expressions ofB0,2, B1,2, and B2,2 can obtain the expression of Bn,2; by observing expressions of B0,3, B1,3 and, B2,3 can obtain the expressions of Bn,3.(3)
Finally, based on the expressions ofBn,1, Bn,2, and Bn,3, the expression of Bi,j can be derivedFrom Figure4(b), in the Markov chain model proposed in this paper, the steady-state probability of Bi,j is determined by two parts. One is the steady-state probability of the Bi−1,j in the row of Bi,j, and the other is the steady-state probability of the Bi,j−1 in the column of Bi,j. Compared with the literature [3], the Markov chain proposed in this paper is relatively complicated. Please refer to the Appendix for the specific derivation process of Equation (2).We propose a unit of time—tb−slot—to define the duration of a unit state. The number of states in each state is equal to its duration divided by tb−slot. It is assumed that tb−slot is equal to 320 μs. For example, if the data packet length is 120 bytes and the data transmission rate is 250 kbps, then the duration of sending is 3.84 ms. Hence, the number of states is equal to 384 ms/320 μs, and the result is 12 states. In the same way, algorithms for other states do the same. The state number of each receiving situation is the transmission time of the packet divided by the tb−slot.The probability of the back-off state is represented byPbacki,j and its expression in Equation (3).
(3)Pbacki,j=Bi,j⋅1Wi⋅WiWi+12.The probability of the CCA state is equal to the entry probability of the corresponding block. It will eventually enter CCA state when it enters the block CB. Consequently, the probability of each state of the transmission block can be calculated as follows:(4)PCCAi,j=Bi,j,Ptransi,j=1−α⋅PCCAi,j=1−α⋅Bi,j.The steady-state probability of ACK timeout and ACK reception is obtained from Equation (5) and Equation (6).
(5)PAti,j=PC⋅Ptransi,j=PC⋅1−α⋅Bi,j,(6)PrAi,j=1−PC⋅Ptransi,j=1−PC⋅1−α⋅Bi,j.The sum of all steady-state probabilities inBi,j is obtained from Equation (7).
(7)PBi,j=Pbacki,j+PCCAi,j+LD⋅Ptransi,j+LACK⋅PAti,j+LAt⋅PAti,j=Bi,j⋅Wi+12+1+LD⋅1−α+LACK⋅1−PC⋅1−α+LAt⋅PC⋅1−α.PCB represents the sum of all state probabilities in block CB, which is equal to the sum of PBi,j. To simplify, let,
(8)G=LD1−α+LACK1−PC1−α+LAt⋅PC1−αA=PC1−α.The sum of all steady-state probabilities of block CB is obtained from Equation (9).
(9)PCB=∑j=1m∑i=0nPBi,j=∑j=1m∑i=0nBi,j×Wi+12+1+LD1−α+LACK1−PC⋅1−α+LAt⋅PC1−α=∑j=1m∑i=0ni+j!i!j!Aj⋅αj⋅PTWi2+1.5+G,Wi=2iWi,i≤323Wi,i>3.For the specific derivation process ofPCB please see the Appendix.The probability of each state in the final model is derived from the property of the Markov chain, which is that the sum of the probabilities of all states is equal to one. The steady-state probability of the model is obtained from Equation (10).
(10)PBeacon+PTDMA+CMN+1⋅PCB=PT+CMN·LD·PT+CMN+1⋅PCB=1.The steady-state probability depends on two parameters:PC and α. The main assumption is that the probability of each node transmitting data packets has nothing to do with other nodes. When at least one CH node sends data packets to the channel or the base station sends an ACK packet, the channel will be busy in the CCA state. In other words, when no node sends data packets to the channel, the channel will be clear. Therefore, the probability that the channel is clear is obtained from Equation (11). Where τ is the probability that the CH node decides to send data packets, which is equal to the sum of the steady-state probabilities of the CCA state in block CB.
(11)1−α=1−τ1−αLD+LACK⋅1−PCCN−1.Collision is defined as at least two CHs sending data to RSU. The probability of collision is represented byPC, and it is obtained from Equation (12).
(12)PC=1−1−τCN−1.Both the value ofPC and α depend on τ which is also equal to the probability that the CH node is at CCA state. The probability of the CCA state is equal to the probability of entering its own block B multiplied by the number of CB blocks. Therefore, τ can be calculated as
(13)τ=CMN+1×∑j=1m∑i=0nPCCAi,j=CMN+1×∑j=0m∑i=0nBi,j=CMN+1×∑j=0m∑i=0ni+j!i!j!PC⋅1−αj⋅αi⋅PT=CMN+1⋅PT×∑j=0mAj⋅1j!∑i=0ni+j!i!⋅αi=CMN+1⋅PT×∑j=0mAj⋅1j!j!+j+1!α+j+2!2α2+j+3!2α3=CMN+1⋅PT⋅1+α+α2+α3+1+2α+3α2+4α3⋅A+1+3α+6α2+10α3⋅A2+1+4α+10α2+20α3⋅A3+1+5α+15α2+35α3⋅A4+1+6α+21α2+56α3⋅A5.As can be seen from the above, taking the number of node members and cluster heads as the main parameters, we analyze the transmission process of system nodes in detail by establishing Markov model. Then, we begin to calculate the main performance indicators of the system in the next section.


### 4.2. Protocol Performance Measures

In this part, two parameters, the successful transmission rate and the average transmission delay, are used to evaluate the performance of the improved protocol.


#### 4.2.1. Packet Delivery Ratio (PDR)

Packet delivery ratio (PDR) is the ratio of the number of packets successfully delivered to the total number of packets transmitted. PDR is equal to the sum of the entry probabilities ofBi,j under the condition of B0,0 multiplied by the probability of successful transmission in Bi,j.
(14)PDR=∑j=0m∑i=0nBi,j1−PC1−αB0,0=∑j=1m∑i=0ni+j!i!j!PCj1−αj+1αi1−PC.


#### 4.2.2. Average Delay

The average time from receiving a packet in the TDMA phase to successful transmission in the CB block is called the average delay. The average delay between the input and the successful transmission is the transmission delay in the block CB, which is derived from the model in Figure5. DCB is the average delay of successful transmission in the block CB. It also represents the average state from input to successful transmission in Figure 4(b).Definition 1.
LetX=Y1,Y2,⋯,YnZ1,Z2,⋯,Zn, the average of X is equal to ∑PYiYi+∑PZiZi. The average of Y in X is equal to ∑PYiYi/∑PYi, ∑PYi as the share of Yi in the average value.According to Definition1, DCB is the sum of the average share of each block divided by PDR, and it is obtained from Equation (15).
(15)DCB=∑j=0m∑i=0nSDBi.jPDR.In Figure4(b), SDBi,j is the share of each Bi,j in DCB. It is equal to the probability of successful transmission in Bi,j multiplied by the average number of states. The average number of states is between the input of the block CB and the successful transmission state of Bi,j. Since the total probability of the successful transmission is less than one, the total delay of all blocks is divided by the total probability of successful transmission to normalize. From the competition model, the average number of states between the input of B0,0 and the successful transmission state is the first item in the Equation (16). In W0+1/2+LD+1, the first term is the average value of the back-off state, the second term is the state number of the transmission block, and the third term corresponds to the CCA state.
(16)SDB0,0=Wi+12+1+LD1−PC1−α.Correspondingly, based on the competition model in this paper,SDBi,0 is obtained from Equation (17), where Ri is the number of states between the CCA states of entry Bi,j and B0,j. SDBi,1 can be obtained by combining Equation (19) and Equation (20).
(17)SDBi,0=Ri+LDαi1−PC1−α,(18)Ri=∑k=0iWk+12+i,(19)SDB0,1=R0+LDPC1−α1−PC1−α,(20)SDB1,1=R1+LDα⋅PC1−α1−PC1−α,(21)SDBi,1=Ri+Ri+LD+LD+LAtαi⋅αi⋅PC1−α1−PC1−α=2Ri+2LD+LAtα2i⋅PC1−PC1−α2.To exemplify this, consider using a example. The share of the successful transmission delay ofB3,1 is composed of the transmission delay of each Bi,0. When a collision occurs in Bi,0, the node enters into Bi,1. Consequently, the average number of states is Ri+LD+LAt. Moreover, when B3,1 is successfully transmitted, the average number of states between the B0,0 entry and the successful transmission is R3+LD+LAt. Correspondingly, the probability of B3,1 is α3⋅PC1−α1−PC1−α. The first probability is the probability of collision in B3,0, and the second probability is the probability of successful transmission in B3,1 if a collision occurs in B3,0.Similarly,SDBi,j is the probability of successful transmission in Bi,j multiplied by the average number of states from block CB to the successful transmission state in Bi,j. Equation (22) and Equation (23) are expressions of SDBi,2 and SDBi,3, then derived from Equation (22) and Equation (23), the expression of SDBi,j is Equation (24).
(22)SDBi,2=3Ri+3LD+2LAtα3i⋅PC21−PC1−α3,(23)SDBi,3=4Ri+4LD+3LAtα4i⋅PC31−PC1−α4,(24)SDBi,j=j+1Ri+j+1LD+j⋅LAtαj+1i⋅PCj1−PC1−αj+1.Compared with the literature [3], the average delay model used in this paper is more simplified. AD is the average number of states from the CM sending a data packet to the end of the successful transmission of the corresponding block CB. The expression of the average delay (AD) is the Equation (25). From Figure 2, the average delay of CMi is composed of three items. The first item is the average number of states from the beginning of receiving a data packet to the end of the TDMA phase, which is equal to CMN−i∗LD. The second term is the average number of states from the start of the contention phase to the start of sending data packets, which is equal to i∗DCB. The last term is the average number of states between input and successful transmission in CBi, which is equal to DCB. Therefore, AD is the average of all CMS, and it can be obtained from Equation (25).
(25)AD=1CMN+1∑n=0CMNCMN−nLD+n×DCB+DCB=CMN2LD+DCB+DCB.


## 4.1. Markov Chain Model

A Markov chain model is considered to characterize the execution process of the node during the contention phase. Figure4(a) is the Markov chain model of CSMA/CA protocol proposed in literature [3], and Figure 4(b) is the nonbeacon-enabled CSMA/CA Markov chain model proposed in this paper. Bn,m represents block B in Figure 4(c), respectively, and n and m are the number of back-off state and the number of packet retransmission. The block CB in Figure 4(c) represents that the Markov chain model is constructed by block B and the connections between them. All successful outputs of block B are connected to the outputs of block CB.Figure 4
(a) The Markov chain model of basic CSMA/CA protocol. (b) The Markov chain of nonbeacon-enabled CSMA/CA improved protocol. (c) The CB block.
(a)(b)(c)In Figure4, as described in the protocol in literature [3], when the node successfully accesses the channel but the data transmission fails, the values of Number of Back-offs (NB) and Back-off Exponent (BE) all return to the initial values, and Retransmission Times (RT) adds 1. That is, the node retries to access the channel after waiting for a random time interval in0,W0. At this time, the node has lost the number of failed access channels, it increases the chance for reaccessing channel, which slows down the node from reaching its maximum number of back-off. During the retransmit process, competition between nodes increases, as well as collision probability and channel occupancy. Indirectly, the probability of successful transmission decreases.In the improved protocol, the values of BE and NB are remained unchanged when node successfully accesses the channel but the data transmission fails. In particular, after failed transmission, the node maintains its previous number of back-offs. So the maximum number of back-off can be reached faster in this situation. More importantly, compared with the original protocol, the node back-off time increases. It increases the transmission opportunities of nodes and reduces the competition between nodes which means the conflict rate are lower. It implies that the improved mechanism in this paper has a higher probability of transmission successfully and throughput.To exemplify this, consider using a example. In the original mechanism, the node first tries accessing channel fromB0,0 state. After the node unsuccessfully accesses channel k1 times, the node inters state Bk1,00≤k1≤n. Then, it successfully accesses channel but the data transmission failed, and the node back off to the next row state Bk1,1. Next, the node tries to access channel at Bk1,1 state, if after the node unsuccessfully accesses the channel k2 times0≤k2≤n−k1, the packet is successfully transmitted in state Bk1+k2,1. In short, the node’s first attempt to send packets at state Bk1,0 and successfully sent data packets at Bk1+k2,1 after 1 times retransmission and k1+k2 times access failure of node.A new Markov chain model is presented for the case where the nonbeacon-enabled CSMA/CA protocol only attempts to transmit once, as shown in Figure5. This model is only used for an attempt to send a data packet, so it enters into the channel access failure state after once failed access. If the node can successfully access the channel after performing CCA for the first time, it will send a data packet. Otherwise, the node will enter into the channel access failure state. The model can be extended to be applied to limited retransmission.Figure 5
Markov chain model with one time of attempting to send data packets.When a node transmits a data packet, it waits for a random time interval within0,2BE−1. The size of the contention window isWi,j. Respectively, i and j are the number of channel access failures and the number of packet retransmission. When performing CCA, if the channel access is successful, the node enters the packet transmission state. In the next step, the node waits to receive the ACK packet, and the probability of collision is PC. If the node receives the ACK packet, it indicates that the data packet is successfully transmitted. If data was not successfully accepted within the timer, it implicit the packet transmission fails. In CCA state, if the channel is busy, then the channel access fails, and data packets fail to be transmitted. Here, the probability of channel observed busy is α. The symbols used in this paper are listed in Table 2.Table 2
Variable definitions.
VariableMeaningBi,jProbability of occurrence ofBi,jPBeaconProbability of beacon statePTDMASteady-state probability of TDMA statePCBSum of steady-state probabilities of CB statesPTSteady-state probability of each state in TDMA phasePBi,jSum of steady-state probabilities of allBi,j statesPBacki,jSteady-state probability of each back-off statePCCAi,jSteady-state probability of each CCA statePAti,jSteady-state probability of each ACK accepting timeout statePrAi,jSteady-state probability of each ACK accepted stateLDNumber of states for packet transmissionLACKACK status numberLAtACK acceptance timeout status numberCMNNumber of members in the clusterCNNumber of cluster headsPCCollision probabilityαProbability of being busy in CCA stateτSum of steady-state probabilities of CCA state in CBnmacMaxCSMABackoffsmmacMaxFrameRetriesLetPBeacon be the probability of the beacon state. It is assumed that all steady-state probabilities of TDMA state are equal, expressed as PT. Because these states have only one entrance and one exit, they are locally continuous states. In addition, PBeacon is equal to PT. CMN represents the number of Cluster Members, and LD represents the number of states required for transmission. The steady-state probability of the TDMA cycle can be expressed as
(1)PTDMA=CMN⋅LD⋅PT.The entry probability of each CB is also equal toPT. From the Markov competitive model in Figure 4(b), Equation (2) is obtained, which represents the steady-state probability of each stage.
(2)B0,0=PT,Bi,0=α⋅Bi−1,0=αi⋅PT;i>0,B0,j=PC⋅1−α⋅B0,j−1=PC⋅1−αj⋅PT;j>0,Bi,j=i+j!i!j!PC⋅1−αj⋅αi⋅PT;i,j>0.In the model proposed in this paper,B0,0 is the probability of the entrance, and its value is equal to PT. Bi,0 represents the steady-state probability of i times back-off. Similarly, B0,j represents the steady-state probability of j time retransmissions, and Bi,j represents the steady-state probability of i time back-off and j time retransmissions. Its steady-state probability can be derived from Markov chain model.The derivation of the expressionBi,j is as follows:
(1)
Based on the Markov chain model, the expressions ofB0,1, B1,1, and B2,1 are obtained, and the expressions of Bn,1 are derived by observation method(2)
In the same way, by observing the expressions ofB0,2, B1,2, and B2,2 can obtain the expression of Bn,2; by observing expressions of B0,3, B1,3 and, B2,3 can obtain the expressions of Bn,3.(3)
Finally, based on the expressions ofBn,1, Bn,2, and Bn,3, the expression of Bi,j can be derivedFrom Figure4(b), in the Markov chain model proposed in this paper, the steady-state probability of Bi,j is determined by two parts. One is the steady-state probability of the Bi−1,j in the row of Bi,j, and the other is the steady-state probability of the Bi,j−1 in the column of Bi,j. Compared with the literature [3], the Markov chain proposed in this paper is relatively complicated. Please refer to the Appendix for the specific derivation process of Equation (2).We propose a unit of time—tb−slot—to define the duration of a unit state. The number of states in each state is equal to its duration divided by tb−slot. It is assumed that tb−slot is equal to 320 μs. For example, if the data packet length is 120 bytes and the data transmission rate is 250 kbps, then the duration of sending is 3.84 ms. Hence, the number of states is equal to 384 ms/320 μs, and the result is 12 states. In the same way, algorithms for other states do the same. The state number of each receiving situation is the transmission time of the packet divided by the tb−slot.The probability of the back-off state is represented byPbacki,j and its expression in Equation (3).
(3)Pbacki,j=Bi,j⋅1Wi⋅WiWi+12.The probability of the CCA state is equal to the entry probability of the corresponding block. It will eventually enter CCA state when it enters the block CB. Consequently, the probability of each state of the transmission block can be calculated as follows:(4)PCCAi,j=Bi,j,Ptransi,j=1−α⋅PCCAi,j=1−α⋅Bi,j.The steady-state probability of ACK timeout and ACK reception is obtained from Equation (5) and Equation (6).
(5)PAti,j=PC⋅Ptransi,j=PC⋅1−α⋅Bi,j,(6)PrAi,j=1−PC⋅Ptransi,j=1−PC⋅1−α⋅Bi,j.The sum of all steady-state probabilities inBi,j is obtained from Equation (7).
(7)PBi,j=Pbacki,j+PCCAi,j+LD⋅Ptransi,j+LACK⋅PAti,j+LAt⋅PAti,j=Bi,j⋅Wi+12+1+LD⋅1−α+LACK⋅1−PC⋅1−α+LAt⋅PC⋅1−α.PCB represents the sum of all state probabilities in block CB, which is equal to the sum of PBi,j. To simplify, let,
(8)G=LD1−α+LACK1−PC1−α+LAt⋅PC1−αA=PC1−α.The sum of all steady-state probabilities of block CB is obtained from Equation (9).
(9)PCB=∑j=1m∑i=0nPBi,j=∑j=1m∑i=0nBi,j×Wi+12+1+LD1−α+LACK1−PC⋅1−α+LAt⋅PC1−α=∑j=1m∑i=0ni+j!i!j!Aj⋅αj⋅PTWi2+1.5+G,Wi=2iWi,i≤323Wi,i>3.For the specific derivation process ofPCB please see the Appendix.The probability of each state in the final model is derived from the property of the Markov chain, which is that the sum of the probabilities of all states is equal to one. The steady-state probability of the model is obtained from Equation (10).
(10)PBeacon+PTDMA+CMN+1⋅PCB=PT+CMN·LD·PT+CMN+1⋅PCB=1.The steady-state probability depends on two parameters:PC and α. The main assumption is that the probability of each node transmitting data packets has nothing to do with other nodes. When at least one CH node sends data packets to the channel or the base station sends an ACK packet, the channel will be busy in the CCA state. In other words, when no node sends data packets to the channel, the channel will be clear. Therefore, the probability that the channel is clear is obtained from Equation (11). Where τ is the probability that the CH node decides to send data packets, which is equal to the sum of the steady-state probabilities of the CCA state in block CB.
(11)1−α=1−τ1−αLD+LACK⋅1−PCCN−1.Collision is defined as at least two CHs sending data to RSU. The probability of collision is represented byPC, and it is obtained from Equation (12).
(12)PC=1−1−τCN−1.Both the value ofPC and α depend on τ which is also equal to the probability that the CH node is at CCA state. The probability of the CCA state is equal to the probability of entering its own block B multiplied by the number of CB blocks. Therefore, τ can be calculated as
(13)τ=CMN+1×∑j=1m∑i=0nPCCAi,j=CMN+1×∑j=0m∑i=0nBi,j=CMN+1×∑j=0m∑i=0ni+j!i!j!PC⋅1−αj⋅αi⋅PT=CMN+1⋅PT×∑j=0mAj⋅1j!∑i=0ni+j!i!⋅αi=CMN+1⋅PT×∑j=0mAj⋅1j!j!+j+1!α+j+2!2α2+j+3!2α3=CMN+1⋅PT⋅1+α+α2+α3+1+2α+3α2+4α3⋅A+1+3α+6α2+10α3⋅A2+1+4α+10α2+20α3⋅A3+1+5α+15α2+35α3⋅A4+1+6α+21α2+56α3⋅A5.As can be seen from the above, taking the number of node members and cluster heads as the main parameters, we analyze the transmission process of system nodes in detail by establishing Markov model. Then, we begin to calculate the main performance indicators of the system in the next section.


## 4.2. Protocol Performance Measures

In this part, two parameters, the successful transmission rate and the average transmission delay, are used to evaluate the performance of the improved protocol.


### 4.2.1. Packet Delivery Ratio (PDR)

Packet delivery ratio (PDR) is the ratio of the number of packets successfully delivered to the total number of packets transmitted. PDR is equal to the sum of the entry probabilities ofBi,j under the condition of B0,0 multiplied by the probability of successful transmission in Bi,j.
(14)PDR=∑j=0m∑i=0nBi,j1−PC1−αB0,0=∑j=1m∑i=0ni+j!i!j!PCj1−αj+1αi1−PC.


### 4.2.2. Average Delay

The average time from receiving a packet in the TDMA phase to successful transmission in the CB block is called the average delay. The average delay between the input and the successful transmission is the transmission delay in the block CB, which is derived from the model in Figure5. DCB is the average delay of successful transmission in the block CB. It also represents the average state from input to successful transmission in Figure 4(b).Definition 1.
LetX=Y1,Y2,⋯,YnZ1,Z2,⋯,Zn, the average of X is equal to ∑PYiYi+∑PZiZi. The average of Y in X is equal to ∑PYiYi/∑PYi, ∑PYi as the share of Yi in the average value.According to Definition1, DCB is the sum of the average share of each block divided by PDR, and it is obtained from Equation (15).
(15)DCB=∑j=0m∑i=0nSDBi.jPDR.In Figure4(b), SDBi,j is the share of each Bi,j in DCB. It is equal to the probability of successful transmission in Bi,j multiplied by the average number of states. The average number of states is between the input of the block CB and the successful transmission state of Bi,j. Since the total probability of the successful transmission is less than one, the total delay of all blocks is divided by the total probability of successful transmission to normalize. From the competition model, the average number of states between the input of B0,0 and the successful transmission state is the first item in the Equation (16). In W0+1/2+LD+1, the first term is the average value of the back-off state, the second term is the state number of the transmission block, and the third term corresponds to the CCA state.
(16)SDB0,0=Wi+12+1+LD1−PC1−α.Correspondingly, based on the competition model in this paper,SDBi,0 is obtained from Equation (17), where Ri is the number of states between the CCA states of entry Bi,j and B0,j. SDBi,1 can be obtained by combining Equation (19) and Equation (20).
(17)SDBi,0=Ri+LDαi1−PC1−α,(18)Ri=∑k=0iWk+12+i,(19)SDB0,1=R0+LDPC1−α1−PC1−α,(20)SDB1,1=R1+LDα⋅PC1−α1−PC1−α,(21)SDBi,1=Ri+Ri+LD+LD+LAtαi⋅αi⋅PC1−α1−PC1−α=2Ri+2LD+LAtα2i⋅PC1−PC1−α2.To exemplify this, consider using a example. The share of the successful transmission delay ofB3,1 is composed of the transmission delay of each Bi,0. When a collision occurs in Bi,0, the node enters into Bi,1. Consequently, the average number of states is Ri+LD+LAt. Moreover, when B3,1 is successfully transmitted, the average number of states between the B0,0 entry and the successful transmission is R3+LD+LAt. Correspondingly, the probability of B3,1 is α3⋅PC1−α1−PC1−α. The first probability is the probability of collision in B3,0, and the second probability is the probability of successful transmission in B3,1 if a collision occurs in B3,0.Similarly,SDBi,j is the probability of successful transmission in Bi,j multiplied by the average number of states from block CB to the successful transmission state in Bi,j. Equation (22) and Equation (23) are expressions of SDBi,2 and SDBi,3, then derived from Equation (22) and Equation (23), the expression of SDBi,j is Equation (24).
(22)SDBi,2=3Ri+3LD+2LAtα3i⋅PC21−PC1−α3,(23)SDBi,3=4Ri+4LD+3LAtα4i⋅PC31−PC1−α4,(24)SDBi,j=j+1Ri+j+1LD+j⋅LAtαj+1i⋅PCj1−PC1−αj+1.Compared with the literature [3], the average delay model used in this paper is more simplified. AD is the average number of states from the CM sending a data packet to the end of the successful transmission of the corresponding block CB. The expression of the average delay (AD) is the Equation (25). From Figure 2, the average delay of CMi is composed of three items. The first item is the average number of states from the beginning of receiving a data packet to the end of the TDMA phase, which is equal to CMN−i∗LD. The second term is the average number of states from the start of the contention phase to the start of sending data packets, which is equal to i∗DCB. The last term is the average number of states between input and successful transmission in CBi, which is equal to DCB. Therefore, AD is the average of all CMS, and it can be obtained from Equation (25).
(25)AD=1CMN+1∑n=0CMNCMN−nLD+n×DCB+DCB=CMN2LD+DCB+DCB.


## 4.2.1. Packet Delivery Ratio (PDR)

Packet delivery ratio (PDR) is the ratio of the number of packets successfully delivered to the total number of packets transmitted. PDR is equal to the sum of the entry probabilities ofBi,j under the condition of B0,0 multiplied by the probability of successful transmission in Bi,j.
(14)PDR=∑j=0m∑i=0nBi,j1−PC1−αB0,0=∑j=1m∑i=0ni+j!i!j!PCj1−αj+1αi1−PC.


## 4.2.2. Average Delay

The average time from receiving a packet in the TDMA phase to successful transmission in the CB block is called the average delay. The average delay between the input and the successful transmission is the transmission delay in the block CB, which is derived from the model in Figure5. DCB is the average delay of successful transmission in the block CB. It also represents the average state from input to successful transmission in Figure 4(b).Definition 1.
LetX=Y1,Y2,⋯,YnZ1,Z2,⋯,Zn, the average of X is equal to ∑PYiYi+∑PZiZi. The average of Y in X is equal to ∑PYiYi/∑PYi, ∑PYi as the share of Yi in the average value.According to Definition1, DCB is the sum of the average share of each block divided by PDR, and it is obtained from Equation (15).
(15)DCB=∑j=0m∑i=0nSDBi.jPDR.In Figure4(b), SDBi,j is the share of each Bi,j in DCB. It is equal to the probability of successful transmission in Bi,j multiplied by the average number of states. The average number of states is between the input of the block CB and the successful transmission state of Bi,j. Since the total probability of the successful transmission is less than one, the total delay of all blocks is divided by the total probability of successful transmission to normalize. From the competition model, the average number of states between the input of B0,0 and the successful transmission state is the first item in the Equation (16). In W0+1/2+LD+1, the first term is the average value of the back-off state, the second term is the state number of the transmission block, and the third term corresponds to the CCA state.
(16)SDB0,0=Wi+12+1+LD1−PC1−α.Correspondingly, based on the competition model in this paper,SDBi,0 is obtained from Equation (17), where Ri is the number of states between the CCA states of entry Bi,j and B0,j. SDBi,1 can be obtained by combining Equation (19) and Equation (20).
(17)SDBi,0=Ri+LDαi1−PC1−α,(18)Ri=∑k=0iWk+12+i,(19)SDB0,1=R0+LDPC1−α1−PC1−α,(20)SDB1,1=R1+LDα⋅PC1−α1−PC1−α,(21)SDBi,1=Ri+Ri+LD+LD+LAtαi⋅αi⋅PC1−α1−PC1−α=2Ri+2LD+LAtα2i⋅PC1−PC1−α2.To exemplify this, consider using a example. The share of the successful transmission delay ofB3,1 is composed of the transmission delay of each Bi,0. When a collision occurs in Bi,0, the node enters into Bi,1. Consequently, the average number of states is Ri+LD+LAt. Moreover, when B3,1 is successfully transmitted, the average number of states between the B0,0 entry and the successful transmission is R3+LD+LAt. Correspondingly, the probability of B3,1 is α3⋅PC1−α1−PC1−α. The first probability is the probability of collision in B3,0, and the second probability is the probability of successful transmission in B3,1 if a collision occurs in B3,0.Similarly,SDBi,j is the probability of successful transmission in Bi,j multiplied by the average number of states from block CB to the successful transmission state in Bi,j. Equation (22) and Equation (23) are expressions of SDBi,2 and SDBi,3, then derived from Equation (22) and Equation (23), the expression of SDBi,j is Equation (24).
(22)SDBi,2=3Ri+3LD+2LAtα3i⋅PC21−PC1−α3,(23)SDBi,3=4Ri+4LD+3LAtα4i⋅PC31−PC1−α4,(24)SDBi,j=j+1Ri+j+1LD+j⋅LAtαj+1i⋅PCj1−PC1−αj+1.Compared with the literature [3], the average delay model used in this paper is more simplified. AD is the average number of states from the CM sending a data packet to the end of the successful transmission of the corresponding block CB. The expression of the average delay (AD) is the Equation (25). From Figure 2, the average delay of CMi is composed of three items. The first item is the average number of states from the beginning of receiving a data packet to the end of the TDMA phase, which is equal to CMN−i∗LD. The second term is the average number of states from the start of the contention phase to the start of sending data packets, which is equal to i∗DCB. The last term is the average number of states between input and successful transmission in CBi, which is equal to DCB. Therefore, AD is the average of all CMS, and it can be obtained from Equation (25).
(25)AD=1CMN+1∑n=0CMNCMN−nLD+n×DCB+DCB=CMN2LD+DCB+DCB.


## 5. Numerical Simulation

In this part, the accuracy of the proposed protocol is checked first. Then, the effects of MAC layer parameters and the number of clusters on the performance of the protocol are evaluated. Moreover, the simulation results are compared with the protocol in literature [3]. The simulation parameters of this article are summarized in Table 3. It is stipulated that the transmission range of all nodes is constant.Table 3
Default parameters.
ParameterValueData length120 bytesTransmission speed250 kbpsACK duration864μsSIFS192μsLAt2.7 (0.864 ms)LACK1.1 (0.352 ms)Wmin7Wmax56macMaxCSMABackoffs5macMinCSMABackoffs1macMaxFrameRetries3macMinFrameRetries0macMaxBE5macMinBE3Number of nodes36-648Number of packetsCMN+1nmacMaxCSMABackoffsmmacMaxFrameRetriesFigure6 shows the relationship between α and the number of clusters (CHs) at 12, 36, 72, and 108 nodes, respectively. The Figure consists of four curves with a constant number of nodes. Each curve shows that the value of α increases with the increase in the number of clusters. Furthermore, from the view of nodes, the value of α increases as the number of nodes increases. Especially, the number of clusters is equal to the number of CHs. When the number of nodes is 12, starting from CH=3, the growth rate of α has slowed down. After CH=5, the value of α tends to be stable. When the number of nodes is 36, from CH=0 to CH=6, the value of α shows an upward trend. After CH=6, the value of α tends to be stable. When the number of nodes is 72, from CH=10 to CH=28, the value of α increases slowly. After CH=28, the value of α tends to be stable. When the number of nodes is 108, from CH=7 to CH=51, the value of α increases slowly. After CH=51, the value of α tends to be stable. In all the above four cases, the value of α increases to a certain point 1. That is, in the vehicle network, the vehicle network tends to collapse as the increase in the number of nodes causes more collisions and the probability of channel busy tends to 1. The main reason is that the increase of cluster number increases the competition among CHs in the competition phase. In addition, compared with the literature [3], the model in this paper has a lower rate of channel occupancy. The simulation results in this paper gives a better response than in literature [3] demonstrating that the model in this paper is beneficial in terms of transmission successfully.Figure 6
The graph of the functional relationship betweenα and the number of clusters when the number of nodes is 12, 36, 72, and 108.Figure7 shows the functional relationship among the number of clusters and the value of the transmission failure probability PC when the number of nodes is 12, 36, 72, and 108, respectively. On the one hand, the value of PC increases as the number of clusters increases. This is obvious in the VANET. On the other hand, the value of the PC also increases as the number of nodes increases. As the number of CHs increases, more than two or more CHs send packets to RSU at the same time during a certain time, which will lead to an increase in the probability of collision in the channel. Moreover, when the number of nodes increases, it also will cause channel congestion and aggravates collision. In the improved protocol, when a collision occurs, the node retransmits the data packet with the previous number of back-offs, rather than backing off from the start state in the next phase. Since the previous number of back-offs are maintained and a larger contention window size is selected, the transmission opportunity of CHs becomes larger, the maximum number of back-off can be reached quickly. This reduces channel occupancy and conflicts and indirectly improves the success of data transmission. The lower probability of collision has increased the performance of the model proposed in this paper, in comparison to the protocol in literature [3], which is unable to improve transmission success rate due to rising in the collision rate. It is verified that the average collision rate for all the nodes is reduced averagely by 25.4% in normal conditions using the proposed protocol.Figure 7
The graph of the functional relationship between thePC and the number of clusters when the number of nodes is 12, 36, 72, and 108.Figure8 describes the variation of the number of clusters and packet delivery ratio when the maximum times of retransmission is 0, 1, 2, and 3, respectively. As the number of clusters increases, the collision rate increases. PDR falls with the increasing number of clusters due to the increased competitiveness among clusters, and the converse nature is observed in the case of PDR for the value of macMaxFrameRetries increases. Because an increase in the number of retransmissions increases the opportunities of packets sent. However, the overall trend of the PDR is decreasing as the number of clusters increases. That is because the chance of retransmitting the packet increases, and the wait time of CH in the channel also increases. Moreover, a comparison with literature [3] between four different macMaxFrameRetries cases has been carried out. Simulation results show that the average PDR of VANET in this paper is observed to be 43.05% higher than existing in literature [3].Figure 8
The functional relationship between PDR and the number of clusters when the maximum number of retransmissions is 0, 1, 2, and 3.Figure9 shows the functional relationship between the number of clusters and the PDR when the maximum back-off times is 1, 3, and 5, respectively. It can be seen from the Figure that PDR increases when the value of the macMaxCSMABackoffs increases. On the contrary, PDR decreases with the increase of the number of clusters. Increasing the number of back-offs increases the transmission success rate, because the number of back-off increases the chance for accessing the channel successfully. However, it also leads to a disadvantage that the waiting time of the node to transmit packets will increase and increases system transmission delay.Figure 9
The functional relationship between PDR and the number of clusters when the maximum back-off times are 1, 3, and 5.Figure10 illustrates the functional relationship among the number of clusters and the average delay when the maximum number of retransmissions is 0, 1, 2, and 3, respectively. When the number of clusters increases, the average delay will increase. Because as the number of clusters increases, competition between nodes increases, the size of the back-off window increases, and the transmission wait time increases accordingly. In the Figure, from CH=0 to CH=4, the transmission delay increases the fastest. It is implied that the transmission success rate is the highest during this period, because successful transmission means a greater wait time. Especially, when there are relatively few CHs, the transmission delay of the system is sensitive to the changes of the CHs. Because the number of competing CHs is small, the PDR is larger. After CH=6, the growth rate of transmission delay is slowing down. Similarly, low transmission success means less wait time for CHs and it also verifies the simulation results of PDR reduction trend in Figures 8 and 9. In addition, by comparing the curves of Maxretry=0, Maxretry=1, Maxretry=2, and Maxretry=3, it can be seen that the number of retransmissions is the key factor influencing the transmission delay of the system. The average delay increases as the value of macMaxFrameRetries increases. Because the increase in the number of retransmissions leads to an increase in the chance of sending data packets, the waiting time in CHs is increased. In further analysis, lowering the value of macMaxFrameRetries can significantly prevent transmission delay because of less waiting time in CHS. Conversely, it cannot improve the PDR of transmission.Figure 10
Relationship between successful transmission delay and the number of clusters when the maximum number of retransmissions is 0, 1, 2, and 3.Figure11 shows the functional relationship among the number of clusters and the average delay when the maximum back-off times are 1, 3, and 5, respectively. The Figure illustrates that the average delay increases with the value of the macMaxCSMABackoffs and also increases with the increase of the number of clusters. As the number of back-offs increases, the waiting time of the node will increase. Hence, the more back-offs, the greater the transmission delay of the system. After CH=6, the average delay is stable when the maximum number of back-off is 1, 3, and 5, respectively. This is because the successful transmission rate during this period is very low and most packets are discarded because they reach the maximum retransmission or back-off times.Figure 11
Relationship between successful transmission delay and the number of clusters when the maximum back-off times are 1, 3, and 5.The simulation results show that the improved protocol can obviously reduce the rate of collision and channel occupancy of the system when the node density is large, and the PDR of the system is also improved. Moreover, it does not increase too much transmission delay and is a suitable back-off mechanism for vehicle node-dense scenarios. Upon comparison with protocol in literature [3], the improved protocol performs better because of the new retransmit strategy involved in it which can record previous number of back-offs to increase the chances of data transmission. Conversely, the value of BE, NB, and RT is reset to the default value in literature [3]. Through the model and simulation results, we observe that PC and α have direct effect on PDR and average transmission delay. In addition, the above four parameters are greatly affected by the MAC layer parameters and the network topology, and improper selection may result in poor network performance. For a network with a constant number of nodes, increasing the number of CHs will result in a decrease in PDR and increase the average transmission delay. Specifically, the PDR increases with the increase in values of macMaxCSMABackoffs and macMaxFrameRetries. Because increasing the number of back-offs and the number of retransmissions can increase the chances for transmitting data packets. Moreover, it also adds up to some problems. For instance, by increasing the values of macMaxCSMABackoffs and macMaxFrameRetries, the average stay time of the node increases, increasing average delay. For average delay and PDR, macMaxCSMAbackoffs are more influential than macMaxFrameRetries. Therefore, using an appropriate back-off method can improve the performance of the communication mechanisms.


## 6. Conclusion

With the increase of urban car ownership year by year, node-intensive scenarios become increasingly common. However, in vehicle node intensive networks, the existing IEEE 802.11p protocol aggravates the collision between nodes and cannot ensure effective data transmission efficiency. In cluster-based VANET, this paper proposes an improved IEEE 802.11p protocol combined with TDMA for dense scenarios, which ensures the data transmission effect by improving the transmission rate of retransmission packets. At the same time, taking the number of nodes and cluster heads as the main parameters, the performance of the improved mechanism is analyzed by establishing a two-dimensional Markov model, and the analytical expressions of system transmission rate, delay, and other performance indexes are obtained. Finally, the mechanism is simulated and the performance of the improved mechanism is evaluated. The simulation results show that the proposed protocol has better performance in the node dense scenarios, and the transmission success rate is 41.25% higher than that in the literature [3]. Particularly, the average transmission delay increases with the increase of the number of clusters, and the data transmission rate decreases with the increase of the number of clusters. The conclusion provides theoretical guidance for the deployment of roadside facilities and the optimization of cluster structure in VANET.



---

*Source: 1955948-2022-04-16.xml*