Performance Enriching Channel Allocation Algorithm for Vehicle-to-Vehicle City, Highway and Rural Network

Abstract

Future safety applications require the timely delivery of messages between vehicles. The 802.11p has been standardized as the standard Medium Access Control (MAC) protocol for vehicular communication. The 802.11p uses Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) as MAC. CSMA/CA induces unbounded channel access delay. As a result, it induces high collision. To reduce collision, distributed MAC is required for channel allocation. Many existing approaches have adopted Time Division Multiple Access (TDMA) based MAC design for channel allocation. However, these models are not efficient at utilizing bandwidth. Cognitive radio technique is been adopted by various existing approach for channel allocation in shared channel network to maximize system throughput. However, it induces MAC overhead, and channel allocation on a shared channel network is considered to be an NP-hard problem. This work addresses the above issues. Here we present distributed MAC design PECA (Performance Enriching Channel Allocation) for channel allocation in a shared channel network. The PECA model maximizes the system throughput and reduces the collision, which is experimentally proven. Experiments are conducted to evaluate the performance in terms of throughput, collision and successful packet transmission considering a highly congested vehicular ad-hoc network. Experiments are carried out to show the adaptiveness of proposed MAC design considering different environments such City, Highway and Rural (CHR).

1. Introduction

The vehicular Ad-Hoc Network (VANET) has attained wide interest due to the rapid growth of wireless technology. VANET is a special type of Mobile Ad-Hoc Network (MANET), where communication takes place among Vehicle to Vehicle (V2V), Vehicle to Infrastructure (V2I) and the combination of both (V2X). Vehicle-to-vehicle (V2V) communications are considered to be a fundamental part of future smart transport systems [1,2]. As a result, this has led to the growth of various smart transport systems [3]. The user expected to be connected everywhere which makes an immediate requirement in V2V connectivity and many applications are also envisioned. The advantage of such a connected network will aid in improving commuter awareness of traffic conditions, accelerate toll processing, be on the go infotainment access, enable sharing among vehicles, provide better safety and so forth. To support such smart transport systems, the Federal Communications Commission (FCC) of the United States (US) has dedicated 75 MHz of spectrum allocated in the 5.9 GHz band for Dedicated Short-Range Communications (DSRC). Then, the IEEE Wireless Access in Vehicular Environment standard stack (e.g., IEEE 1609.4 and IEEE 802.11p) was designed to cater to communications between vehicles in the DSRC band. As compared with other Ad-Hoc networks, VANET has distinctive characteristics such as dynamically varying topology, the high mobility of vehicle and strict delay constraints. These problems must be considered in designing MAC for VANET to cater for both safe and non-safety application services.

The CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) based 802.11p [4] has been standardized as the standard MAC protocol for vehicular communication. However, if traffic density is high, it induces high collision probability, specifically for broadcasting packets [5]. Broadcasting plays a significant role in transmitting safety related data such as road condition warnings and vehicle accident warnings. Apart from event driven transmission and Wireless Access in Vehicular Environments (WAVE) [6], Reference [7] also provides an extra layer for WAVE-Basic Service Advertisements (WSAs) and basic safety messages (BSMs) [8]. The WSAs needs to be periodically broadcasted by vehicles to cater non-safety application. The BSMs contain critical information of vehicles such as speed and location. To assure reliable real-time service, each vehicle needs to broadcast and exchange BSMs periodically (i.e., once in every 100 ms) [9].

In the IEEE 802.11p MAC protocol, the vehicle starts transmission directly if the channel sensed is idle. Otherwise, it arbitrarily selects the back-off time from the Contention Window (CW) and initializes the back-off counter. Transmission is initialized when the back-off counter is reached to zero. If more than two vehicles try to access channel simultaneously within two hop distance, a collision occurs and none of the data can be successfully received. Considering this scenario, to resend data the vehicle has to re-compete for channel access. An exponential back-off scheme is presented to decrease the likelihood of contention collision for unicast transmission. However, CSMA/CA has the problem potentially of unbounded channel access delay [10]. If the VANET device has multiple packets, it has to contend for multiple times. Furthermore, 802.11p suffers from interference problems due to hidden terminals, since it cannot use the RTS (Request to Send)/CTS (Clear to Send) mechanisms for broadcasting packets [11]. Considering this scenario too, the collision of the packet cannot even be identified right away. No exponential back-off methods can be used for broadcasting packet sand the likelihood of packet collision is significantly high [5].

To overcome the drawback of IEEE 802.11p, TDMA (time division multiple access) based MAC protocols are presented to provision efficient transmission in VANET [12]. However, their approach is centralized and takes advantage of RSUs (Road side units). As a result, it requires a large amount of RSUs. Hence, it is applicable for City environment. To address this, in Reference [13] presented a distributed MAC to utilize bandwidth efficiently. The model overcomes the bandwidth inefficiency of Space Division Multiple Access (SDMA) [14]. Their model reduces collision in the highway environment. However, their model did not consider maximizing system throughput. Cognitive radio technique has been adopted in Reference [15] to utilize bandwidth efficiently. To maximize system throughput on the multi-channel network, channel sharing technique is been adopted in References [15,16]. Channel allocation on shared channel network is considered to be an NP-hard problem [16]. In Reference [16] presented a theoretical model to solve the NP-hard problem. However, their model did not consider experimental study under different environmental conditions such as city, highway and rural area and besides it induce MAC protocol overhead. Further, number of alternative access technology using 80211ax [17] and 802.11bd [18]. The number of hybrid models is presented along with considering heterogeneous network [19,20,21]. However, none of these models has been evaluated under different radio propagation environments. Additionally, it will incur a high deployment cost and effective coordination is required. Thus, effective MAC scheduling is needed for utilizing resources efficiently irrespective of the network it operates. Further, to overcome the NP-hard problem and MAC protocol overhead for channel allocation in a shared channel network, our paper presents an efficient distributed design for channel allocation that maximizes the system throughput and reduces packet collision.

The research work contribution is as follows:

• Here we formulated the channel allocation problem to maximize system throughput as a linear optimization problem.
• This work presented two algorithms to solve the NP-hard problem for channel allocation in both shared and non-shared channel access.
• We present a Distributed MAC design for shared channel access by integrating MAC overhead into channel allocation.
• The model design brings a trade-off between maximizing system throughput and reducing collision, which is experimentally proven.
• The proposed MAC design is adaptive in nature, for instance, with city, highway and rural, which is experimentally shown.

The organization of this paper is structured as follows. Section 2 describes the extensive research survey work on improving the performance of Vanet so far. The proposed channel allocation model and distributed medium access control (decentralized) are presented in Section 3. The experimental study is carried out in Section 4. The future work and conclusion is described in the last section.

2. Related Work

In this section, we describe the state of the art related to MAC protocols used in vehicular ad-hoc networks. In Reference [22], the delay incurred by the 802.11p protocol due to variations in load is studied. The authors in Reference [23] presented a Decentralized Congestion Control (DCC) algorithm for a V2V network in order to support a cooperative smart transport system. The MAC layer uses carrier sensing to detect the busy state of a radio channel before initializing transmission. Their model overcomes the drawback of Enhanced Distributed Channel Access (EDCA) by introducing a queueing technique to handle packet priority for safety related applications. Experiments are conducted to evaluate performance in terms of coverage range and delay reliability under different environment loads for a highway environment. However, DCC adopts a cross-layer design considering a single channel. The authors in Reference [24] presented a cross layer MAC design for VANET. The objective of their design is to minimize interference between a communicating pair at the MAC and routing layer. They also presented a metric to maximize mean Signal to Interference Ratio (SIR) among transmitter and receiver. The experimental outcome shows improvement in terms of packet delivery ratio and throughput. However, their model induces control channel overhead due to computation and the maintenance of the state information of the channel, thus inducing a high risk of collision.

The authors in Reference [25] showed neighborhood knowledge aids in reducing collision. They presented a distributed synchronized beaconing scheduling mechanism, which aids in reducing packet loss in control channel contention for safety applications. However, the network utilization is very low when the traffic is much lower. It assigns slots to the cell with no vehicle, resulting in bandwidth wastage. In Reference [13], they presented a TDMA based MAC named PTMAC (Prediction based TDMA MAC). This aids in addressing packet collision due to hidden node problems under high traffic density. They presented a prediction model for variable traffic density of the two-way network. The outcome shows a reduction in collision for a varied network and traffic density. However, the model did not consider maximizing system throughput.

In order to maximize system throughput, the authors in Reference [15] adopted a cognitive radio technique to design MAC named Enhanced NonCooperative Cognitive division Multiple Access (ENCCMA). They combined FDMA (frequency division multiple access), TDMA and a cognitive radio technique to design a MAC for a shared multi-channel network. They conducted an experimental study of ENCCMA and a comparison with various state-of-arts of MAC. They showed significant performance improvement. However, allocating bandwidth to a vehicle on shared channel is considered to be a NP-hard problem [16]. To address NP-hard problem, Reference [16] presented an approximation algorithm for the cognitive vehicular network. Three constant-factor approximation algorithms are modeled with polynomial time complexity and theoretical performance guarantees. Theoretical guarantees are verified by simulation results. However, their channel allocation is not distributed in nature which induces MAC protocol overhead. In addition,, Reference [17] presented OFDMA based Multiple Access for IEEE 802.11ax. The model aimed to attain better synchronization and overhead reduction with fast back off and better channel sensing. Further, Reference [18] showed the need for reliable, low latency with high throughput for VANET. They presented an alternate radio access technology. They used IEEE 802.11bd instead for DSRC and NR V2X for C-V2X. These models are designed to cope with current dynamic application need and wireless traffic [25]. In Reference [25], presented a dynamic method for adapting rate and power with 1-hop broadcasting packets for each vehicle in multi-application conditions. The model is designed to reduce channel load and meets multiple application scenarios. However, maximizing system utility is not considered. In Reference [26], the authors presented a channel reservation MAC for a multi-channel environment using serial cooperation, using 802.11ax [21]. The model reduced channel access delay and, using cooperative communication, reduced packet collision. However, collision reduction performance was not evaluated by them. A survey conducted by a researcher in Reference [19] showed the need for a novel design considering heterogeneous VANET [20,21]. In Reference [20], for improving scalability and bandwidth utilization, they presented a distributed context-aware heterogeneous VANET association that dynamically selects its radio access technology in an autonomous manner based on user/application QoS prerequisite. In Reference [21], for enhancing quality of experience (QoE), they presented a hybrid model by combining a software defined network with VANET. Using SDN, the available bandwidth from both Wi-Fi and LTE is used for VANET communication. Further, using vehicle states’ information, the resources are allocated to vehicles with radio access technology that maximize the QoE of all vehicles. An extensive research survey was carried out, which showed that a new MAC design is required to maximize system throughput and minimize MAC overhead. The future MAC design should be adaptive in nature, that is, the design should consider different radio propagating environments such as city, highway and rural areas. In the next section, the problem formulation is presented.

3. Problem Formulation

This work aims at maximizing the network throughput for performing channel allocation. Let the throughput achieved by vehicle $\mathrm{x}$ be ${\mathrm{S}}_{\mathrm{x}}$ and ${\mathrm{e}}_{\mathrm{xy}}$ denotes the channel allocation decision. If channel $\mathrm{y}$ is allocated to vehicle $\mathrm{x}$, then ${\mathrm{e}}_{\mathrm{xy}}$ is set to 1, otherwise ${\mathrm{e}}_{\mathrm{xy}}$ is set to 0. The throughput gain problem can be expressed as

$$\underset{\mathrm{E}}{\max }{\displaystyle \sum }_{\mathrm{x}}^{\mathrm{R}}{\mathrm{S}}_{\mathrm{x}}.$$

(1)

where $\mathrm{R}$ is the total number of vehicle in vehicular ad-hoc network. Further, we have the following bound for non-shared channel allocation as

$${\displaystyle \sum }_{\mathrm{x}}^{\mathrm{R}}{\mathrm{e}}_{\mathrm{xy}}=1\forall \mathrm{y}.$$

(2)

We can now formulate the throughput attained by vehicle $\mathrm{x}$ on non-shared channel allocation as follows. Let ${\mathrm{V}}_{\mathrm{x}}$ be the channel set exclusively allocated to vehicle $\mathrm{x}$ and ${\mathrm{l}}_{\mathrm{xy}}$ be the likelihood that channel $\mathrm{y}$ is accessible to vehicle $\mathrm{x}$. For easiness, we consider that ${\mathrm{l}}_{\mathrm{xy}}$ are not dependent on each other. Therefore, the ${\mathrm{S}}_{\mathrm{x}}$ can be computed as follows

$${\mathrm{S}}_{\mathrm{x}}=1-{\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}{\mathrm{l}}_{\mathrm{xy}}^{\prime }=1-{\displaystyle \prod }_{\mathrm{y}=1}^{\mathrm{T}}{\left({\mathrm{l}}_{\mathrm{xy}}^{\prime }\right)}^{{\mathrm{e}}_{\mathrm{xy}}}$$

(3)

where ${\mathrm{l}}_{\mathrm{xy}}^{\prime }=1-{\mathrm{l}}_{\mathrm{xy}}$ is the likelihood that channel $\mathrm{y}$ is not accessible for vehicle $\mathrm{x}$ and $1-{\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}{\mathrm{l}}_{\mathrm{xy}}^{\prime }$ is the likelihood that utmost one channel is accessible to vehicle $\mathrm{x}$. Since each vehicle can utmost uses one accessible channel, its maximum throughput is one. In the shared channel allocation technique, the bounds in Equation (2) are not required. Hence, it can be seen that solving Equations (1) and (2) is a, NP-Hard problem, since it is a nonlinear integer program. In the next section, the PECA algorithm is presented.

4. Performance Enriched Channel Allocation (PECA) Algorithm

Here, we present a low-complexity and efficient technique for channel allocation for non-shared and shared channel vehicular networks. This work considers a distributed vehicular ad-hoc network in which $\mathrm{R}$ vehicles exploit spectrum opputunities in $\mathrm{T}$ channels. We also consider that each vehicle is within its communication radius (i.e., each vehicle can hear transmission of other vehicles). In addition, at most one channel can be accessed by each vehicle for performing data transmission. In addition, vehicles perform sensing on allocated channels at the beginning of each cycle to explore available channels for communication, where time is divided into a fixed-size of cycle. We also consider that perfect sensing can be accomplished with no sensing error.

4.1. Non-Shared Channel Allocation Algorithm (NSCA)

Let ${\mathrm{V}}_{\mathrm{x}}$ be the set of channel exclusively allocated for vehicle $\mathrm{x}$ (i.e., ${\mathrm{V}}_{\mathrm{x}}\cap {\mathrm{V}}_{\mathrm{y}}=\varnothing$, $\mathrm{x}\ne \mathrm{y}).$ The NSCA technique iteratively assigns a channel to vehicle to maximize the network throughput.

In each iteration of channel assignment, each vehicle $\mathrm{x}$ computes its gain in throughput if the best channel is allocated considering the following condition

$${\mathrm{y}}_{\mathrm{x}}^{\prime }=\underset{\mathrm{y}\in {\mathrm{V}}_{\mathrm{z}}}{\mathrm{argmax}}{\mathrm{l}}_{\mathrm{x},\mathrm{y}},$$

(4)

The gain in throughput can be computed as

$${\mathsf{\delta }\mathrm{S}}_{\mathrm{x}}={\mathrm{S}}_{\mathrm{x}}^{\mathrm{z}}-{\mathrm{S}}_{\mathrm{x}}^{\mathrm{q}}=\left[1-\left(1-{\mathrm{l}}_{{\mathrm{xy}}_{\mathrm{x}}^{\prime }}\right){\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}\left(1-{\mathrm{l}}_{\mathrm{xy}}\right)\right]-\left[1-{\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}\left(1-{\mathrm{l}}_{\mathrm{xy}}\right)\right]={\mathrm{l}}_{{\mathrm{xy}}_{\mathrm{x}}^{\prime }}{\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}\left(1-{\mathrm{l}}_{\mathrm{xy}}\right)$$

(5)

As can be observed from Equation (5), ${\mathsf{\delta }\mathrm{S}}_{\mathrm{x}}$ will be decreased with every iteration of allocation, because as ${\mathrm{V}}_{\mathrm{x}}$ increases, ${\displaystyle \prod }_{\mathrm{y}\in {\mathrm{V}}_{\mathrm{x}}}\left(1-{\mathrm{l}}_{\mathrm{xy}}\right)$ tends to zero. By considering this condition, the proposed Non-Shared Channel Allocation Algorithm (NSCA) is defined in Algorithm 1.

Algorithm 1: Non-Shared Channel Allocation Algorithm

Step 1. Input set of accessible channel ${\mathrm{V}}_{\mathrm{z}}=\left\{1,2,3,\dots ,\mathrm{T}\right\}$ & ${\mathrm{V}}_{\mathrm{x}}=\varnothing$ for $\mathrm{x}=1,2,3,\dots ,\mathrm{R}$.

Step 2. For $\mathrm{x}=1;\mathrm{x}<=\mathrm{R};\mathrm{R}++$

Step 3. ${\mathrm{y}}_{\mathrm{x}}^{\prime }=\underset{\mathrm{y}\in {\mathrm{V}}_{\mathrm{z}}}{\mathrm{argmax}}{\mathrm{l}}_{\mathrm{x},\mathrm{y}}$.

Step 4. If (${\mathrm{V}}_{\mathrm{x}}=\varnothing$) then

Step 5. Obtain ${\mathsf{\delta }\mathrm{S}}_{\mathrm{x}}={\mathrm{S}}_{\mathrm{x}}^{\mathrm{z}}-{\mathrm{S}}_{\mathrm{x}}^{\mathrm{q}}$, where ${\mathrm{S}}_{\mathrm{x}}^{\mathrm{q}}$ and ${\mathrm{S}}_{\mathrm{x}}^{\mathrm{z}}$ are the throughputs before and after channel allocation ${\mathrm{y}}_{\mathrm{x}}^{\prime }$.

Step 6. Else

Step 7. Obtain ${\mathsf{\delta }\mathrm{S}}_{\mathrm{x}}={\mathrm{l}}_{{\mathrm{xy}}_{\mathrm{x}}^{\prime }}$.

Step 8. End If

Step 9. End For

Step 10. ${\mathrm{x}}^{\prime }=\underset{\mathrm{x}}{\mathrm{argmax}}{\mathsf{\delta }\mathrm{V}}_{\mathrm{x}}$.

Step 11. Allocate channel ${{\mathrm{y}}^{\prime }}_{{\mathrm{x}}^{\prime }}$ to vehicle ${\mathrm{x}}^{\prime }$.

Step 12. Update ${\mathrm{V}}_{\mathrm{z}}={\mathrm{V}}_{\mathrm{z}}/{{\mathrm{y}}^{\prime }}_{{\mathrm{x}}^{\prime }}$.

Step 13. If ${\mathrm{V}}_{\mathrm{z}}$ is empty, terminate the process.

Step 14. Else, go to step 2.

Note: After executing Algorithm 1, we can obtain the set of the channel assigned to each vehicle, based on which the throughput can be computed using Equation (3).

4.2. Shared Channel Allocation Algorithm (SCA)

Channel sharing aids in improving the throughput performance of the multi-user vehicular Ad-hoc network. However, the MAC protocol incurs overhead due to channel access contention under multi-user channel assignment. Therefore, a refined channel allocation technique is required to balance throughput gain and Design overhead.

Our channel allocation model is composed of two stages. Firstly, we compute the channel assignment information of a single vehicle using Algorithm 1. Then, we process a multi-user channel assignment by allocating the channels that have been allocated to some vehicles, to other vehicles in the second stage. Now we are ready to model an SCA Algorithm 2 similar to NSCA Algorithm 1. However, computing the metric is quite a challenging and difficult task. Therefore, we compute throughput gain for channel allocation considering MAC overhead $\mathcal{D}<1$. Note that the Overhead $\mathcal{D}$ depends on the resultant of channel allocation (i.e., number of channels allocated to different vehicle). The computation of $\mathcal{D}$ is shown in a later subsection of this paper.

Let us consider a setup where channel $\mathrm{y}$ is the shared channel of vehicle ${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3,\dots ,{\mathrm{x}}_{\mathbb{V}}$, where $\mathbb{V}$ is the number of vehicles which share the channel. Here we compute throughput gain for a specific vehicle $\mathrm{x}$ if channel $\mathrm{y}$ is allocated to this vehicle. In fact, this throughput gain can be accomplished, because vehicle $\mathrm{x}$ may utilize channel $\mathrm{y}$ if this channel is not utilized by other vehicles ${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3,\dots ,{\mathrm{x}}_{\mathbb{V}}$ or the channel is not accessible. The throughput gain of vehicle $\mathrm{x}$ and channel $\mathrm{y}$ considering practical scenario (i.e., ${\mathrm{l}}_{\mathrm{x},\mathrm{y}}$ is closer to 1 (e.g., at least 0.8) is computed as

$${\mathsf{\delta }\mathrm{S}}_{\mathrm{x}}^{\mathbb{V},\mathrm{b}}\left(\mathrm{y}\right)=\left(1-\frac{1}{\mathbb{V}}\right)\left(1-\mathcal{D}\right){\mathrm{l}}_{\mathrm{xy}}\left({\prod }_{\mathrm{o}\in {\mathrm{V}}_{\mathrm{x}}}{\overline{\mathrm{l}}}_{\mathrm{xo}}\right)\ast \left(1-{\prod }_{\mathrm{o}\in {\mathrm{V}}_{\ast }^{\mathrm{C}}}{\overline{\mathrm{l}}}_{\mathrm{xo}}\right){\sum }_{\mathrm{n}=1}^{\mathbb{V}}\left[{\overline{\mathrm{l}}}_{{\mathrm{x}}_{\mathrm{n}}\mathrm{y}}\left({\prod }_{\mathrm{m}=1,\mathrm{m}\ne \mathrm{n}}^{\mathbb{V}}{\mathrm{l}}_{{\mathrm{x}}_{\mathrm{m}}\mathrm{y}}\right)\right].$$

(6)

Algorithm 2: Shared channel Allocation

Step 1. Input set of assigned channels $\forall$ vehicles ${\mathrm{V}}_{\mathrm{x}}=\varnothing$ for $\mathrm{x}=1,2,3,\dots ,\mathrm{R}$ and ${\mathcal{D}}_{\mathrm{o}}$

Step 2. Execute Algorithm 1 to get channel allocated for a single vehicle.

Step 3. Let the set of channels that are shared by $\mathrm{j}$ vehicles be ${\mathrm{P}}_{\mathrm{j}}$ and ${\mathrm{F}}_{\mathrm{y}}$ be the group of vehicles which share channel $\mathrm{y}$ and set ${\mathrm{F}}_{\mathrm{y}}^{\mathbb{T}}={\mathrm{F}}_{\mathrm{y}}\forall \mathrm{y}=1,2,3,\dots ,\mathrm{T}$.

Step 4. $\mathrm{Process}=1$; $\mathrm{o}=1$; $\mathrm{UpdateOvd}=0$.

Step 5. While $\mathrm{Process}=1$ do

Step 6. Obtain the set of channels ${\mathrm{P}}_{\mathrm{o}}$ shared by $\mathrm{o}$ vehicles

Step 7.  For $\mathrm{y}=1;\mathrm{y}\le \left|{\mathrm{P}}_{\mathrm{o}}\right|;\mathrm{y}++$

Step 8.   For $\mathrm{j}=1;\mathrm{j}\le \mathrm{R};\mathrm{J}++$

Step 9.    If $\mathrm{j}\in {\mathrm{F}}_{\mathrm{y}}$ then

Step 10.     ${\mathsf{\delta }\mathrm{S}}_{\mathrm{j}}^{\mathrm{o},\mathrm{b}}\left(\mathrm{y}\right)=0$.

Step 11.   Else

Step 12.     User $\mathrm{j}$ computes ${\mathsf{\delta }\mathrm{S}}_{\mathrm{j}}^{\mathrm{o},\mathrm{b}}\left(\mathrm{y}\right)$ considering that channel $\mathrm{y}$ is assigned to vehicle $\mathrm{j}$.

Step 13.   End If

Step 14.   End For

Step 15.  ${\mathrm{j}}_{\mathrm{y}}^{\prime }=\arg \underset{\mathrm{j}}{\max }{\mathsf{\delta }\mathrm{S}}_{\mathrm{j}}^{\mathrm{o},\mathrm{b}}\left(\mathrm{y}\right)$.

Step 16.  End For

Step 17. ${\mathrm{j}}_{\mathrm{y}}^{\prime }=\arg \underset{\mathrm{y}}{\max }{\mathsf{\delta }\mathrm{S}}_{{\mathrm{j}}_{\mathrm{y}}^{\prime }}^{\mathrm{o},\mathrm{b}}\left(\mathrm{y}\right)$.

Step 18. If ${\mathsf{\delta }\mathrm{S}}_{{\mathrm{j}}^{\prime }}^{\mathrm{o},\mathrm{b}}\left({{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}\right)\le ϵ$ and $\mathrm{UpdateOvd}=1$ then

Step 19.  Set $\mathrm{Process}=0$.

Step 20.  Go to step 35.

Step 21. End If

Step 22. If ${\mathsf{\delta }\mathrm{S}}_{{\mathrm{j}}^{\prime }}^{\mathrm{o},\mathrm{b}}\left({{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}\right)>ϵ$ then

Step 23.  Provisionally allocate channel ${{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}$ to vehicle ${\mathrm{j}}^{\prime }$, i.e., update ${\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}^{\mathbb{T}}={\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}\cup \left\{{\mathrm{j}}^{\prime }\right\}$.

Step 24.  Compute $\mathcal{A}$ and $\mathcal{D}$ with ${\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}^{\mathbb{T}}$ using Equations (11) and (12), respectively.

Step 25.  If $\left|\mathcal{D}-{\mathcal{D}}_{\mathrm{o}}\right|>{ϵ}_{\mathcal{D}}$ then

Step 26.  $\mathrm{Set}:\mathrm{Process}=1$.

Step 27.   Return to Step 7 using the updated ${\mathcal{D}}_{\mathrm{o}}=\mathcal{D}$.

Step 28.  Else

Step 29.   Update ${\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}={\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}^{\mathbb{T}}$ (i.e., allocate channel ${{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}$ to vehicle ${\mathrm{j}}^{\prime }$), compute $\mathcal{A}$ & ${\mathcal{D}}_{\mathrm{o}}$ with ${\mathrm{F}}_{{{\mathrm{y}}^{\prime }}_{{\mathrm{j}}^{\prime }}}$, & update ${\mathrm{P}}_{\mathrm{o}}$.

Step 30.   Update $\mathrm{UpdateOvd}=0$.

Step 31.  End If.

Step 32. End If.

Step 33. Return to step 7.

Step 34. $\mathrm{o}=\mathrm{o}+1$.

Step 35. End While

4.3. Contention Window Computation

To minimize the collision likelihood among contenting vehicle $\mathrm{V}$, the contention window $\mathcal{A}$ is computed. In fact, there is a tradeoff among overhead of MAC protocol and collision likelihood, which is influenced by $\mathcal{A}$, that is, a lesser value of $\mathcal{A}$ increases the collision likelihood at the cost of lower MAC overhead and vice versa, since each vehicle arbitrarily selects the same back-off time. As a result, the likelihood of the first collision is higher as the number of participating vehicles decreases for each probable collision.

Let ${ℒ}_{\mathrm{u}}$ be the likelihood of the first collision. Let us consider the constraint ${ℒ}_{\mathrm{u}}\le ϵ\mathrm{L}$, where $ϵ\mathrm{L}$ manages the overhead and collision likelihood tradeoff to determine contention window $\mathcal{A}$. Let’s evaluate ${ℒ}_{\mathrm{u}}$ as a function of $\mathcal{A}$ considering that there are $\mathrm{r}$ vehicles in the contention phase. With no loss of generality, let us consider that the arbitrary back-off time of $\mathrm{r}$ vehicles is ordered as ${\mathrm{g}}_1\le {\mathrm{g}}_2\le {\mathrm{g}}_3\le \dots \le {\mathrm{g}}_{\mathrm{r}}$. Assume that, if there are $\mathrm{r}$ vehicles in contention phase, the condition likelihood of the first collision can be expressed as

$${ℒ}_{\mathrm{u}}^{\left(\mathrm{r}\right)}={\displaystyle \sum }_{\mathrm{y}=2}^{\mathrm{r}}\mathbb{L}\left(\mathrm{y}\mathrm{vehicles}\mathrm{collide}\right)={\displaystyle \sum }_{\mathrm{y}=2}^{\mathrm{r}}{\displaystyle \sum }_{\mathrm{x}=0}^{\mathcal{A}-2}{\mathrm{U}}_{\mathrm{r}}^{\mathrm{y}}{\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\mathcal{A}$}\right.\right)}^{\mathrm{y}}{\left(\raisebox{1ex}{$\mathcal{A}-\mathrm{x}-1$}\!\left/ \!\raisebox{-1ex}{$\mathcal{A}$}\right.\right)}^{\mathrm{r}-\mathrm{y}}$$

(7)

where each term in double summation depicts the likelihood that $\mathrm{y}$ vehicles collide when they select identical back-off value with respect to $\mathrm{x}$. Therefore, the likelihood of the first collision can be computed as

$${ℒ}_{\mathrm{u}}={\displaystyle \sum }_{\mathrm{r}=2}^{\mathrm{R}}{ℒ}_{\mathrm{u}}^{\left(\mathrm{r}\right)}\ast \mathbb{L}\left\{\mathrm{r}\mathrm{vehicle}\mathrm{contend}\right\}$$

(8)

where $\mathbb{L}\left\{\mathrm{r}\mathrm{vehicle}\mathrm{contend}\right\}$ is the likelihood that $\mathrm{r}$ vehicles participate in the contention phase, ${ℒ}_{\mathrm{u}}^{\left(\mathrm{r}\right)}$ is computed using Equation (7). To evaluate ${ℒ}_{\mathrm{u}}$, we derive $\mathbb{L}\left\{\mathrm{r}\mathrm{vehicle}\mathrm{contend}\right\}$. It can be proved that vehicle $\mathrm{x}$ participates in contention if utmost one channel in ${\mathrm{V}}_{\mathrm{x}}^{\mathrm{C}}$ is accessible and all channels in ${\mathrm{V}}_{\mathrm{x}}$ are busy. The likelihood of this scenario can be expressed as

$$\begin{gathered} {ℒ}_{\mathrm{C}}^{\left(\mathrm{x}\right)}=\mathbb{L}\left\{\begin{array}{c}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{l}\mathrm{y}\mathrm{o}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{i}\mathrm{n}{\mathrm{V}}_{\mathrm{x}}^{\mathrm{C}}\mathrm{are}\mathrm{accessible}\mathrm{and}\\ \mathrm{all}\mathrm{achannel}\mathrm{in}{\mathrm{V}}_{\mathrm{x}}\mathrm{are}\mathrm{busy}\end{array}\right\} \\ =\left({\displaystyle \prod }_{\mathrm{y}ϵ{\mathrm{V}}_{\mathrm{x}}}{\overline{\mathrm{l}}}_{\mathrm{xy}}\right)\left(1-{\displaystyle \prod }_{\mathrm{y}ϵ{\mathrm{V}}_{\mathrm{x}}^{\mathrm{C}}}{\overline{\mathrm{l}}}_{\mathrm{xy}}\right). \end{gathered}$$

(9)

The likelihood of the scenario that $\mathrm{r}$ vehicles participate in contention phase is

$$\mathbb{L}\left\{\mathrm{r}\mathrm{vehicle}\mathrm{contend}\right\}={\displaystyle \sum }_{\mathrm{t}=1}^{{\mathrm{U}}_{\mathrm{R}}^{\mathrm{r}}}{\displaystyle \prod }_{\mathrm{x}\in {\wedge }_{\mathrm{t}}}{ℒ}_{\mathrm{C}}^{\left(\mathrm{x}\right)}{\displaystyle \prod }_{\mathrm{x}\in {\wedge }_{\mathrm{R}}\backslash {\wedge }_{\mathrm{t}}}{ℒ}_{\mathrm{C}}^{\left(\mathrm{x}\right)}$$

(10)

where ${\wedge }_{\mathrm{R}}$ is the set of all $\mathrm{R}$ vehicles $\left(\left\{1,2,3,\dots ,\mathrm{R}\right\}\right)$ and ${\wedge }_{\mathrm{t}}$ is one specific set of $\mathrm{r}$ users. Substituting the output in Equation (10) into Equation (8), the ${ℒ}_{\mathrm{u}}$ can be computed. Therefore, we can now determine $\mathcal{A}$ as

$$\mathcal{A}=\min \left\{\mathcal{A}|{ℒ}_{\mathrm{u}}\left(\mathcal{A}\right)\le ϵ\mathrm{L}\right\}$$

(11)

where for simplicity, ${ℒ}_{\mathrm{u}}\left(\mathcal{A}\right)$ in Equation (8) is denotes as function of $\mathcal{A}$.

4.4. MAC Overhead Computation

Using Equation (11), the mean overhead of the MAC protocol can be modeled. Let $\mathrm{h}$ be the mean value of a back-off parameter selected by any vehicle. Hence, we have $\mathrm{h}=\raisebox{1ex}{$\left(\mathcal{A}-1\right)$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$ since the back-off value is uniformly selected between zero and $\mathcal{A}-1$ interval (i.e., $\left[0,\mathcal{A}-1\right]$). Therefore, the mean overhead can be computed as

$$\mathcal{D}\left(\mathcal{A}\right)=(\left(\left[\mathcal{A}-1\right]\mathsf{\phi }/2)+{\mathrm{s}}_{\mathrm{CTS}}+{\mathrm{s}}_{\mathrm{RTS}}+3{\mathrm{s}}_{\mathrm{SIFS}}+{\mathrm{s}}_{\mathrm{SYNC}}+{\mathrm{s}}_{\mathrm{SEN}}\right)/{\mathrm{S}}_{ℐ}$$

(12)

where ${\mathrm{s}}_{\mathrm{CTS}}$, ${\mathrm{s}}_{\mathrm{RTS}}$ and ${\mathrm{s}}_{\mathrm{SIFS}}$ are the corresponding time of CTS (Clear to Send), RTS (Request to Send) and SIFS (Short inter frame space) packets, ${\mathrm{s}}_{\mathrm{SYNC}}$ is the size of synchronization packets, ${\mathrm{s}}_{\mathrm{SEN}}$ is the time of sensing, $\mathsf{\phi }$ is the time that corresponds to one back-off parameter and ${\mathrm{S}}_{ℐ}$ is the cycle time. The overhead $\mathcal{D}$ depends on channel allocation outcome. Therefore, $\mathcal{D}$ is updated in Algorithm 2 based on current channel allocation. Our shared channel allocation algorithm is efficient and run smoothly, since $\mathcal{D}$ does not change much in two consecutive assignment decisions which are experimentally proved in the next section.

5. Simulation Analysis and Result

The experiments were conducted on the Windows 10 operating system, 64-bit I-5 quad core processor with 16 GB RAM and Dedicated 4 GB Nvidia CUDA GPU card. The SIMITS simulator tool was used for experiment evaluation. The Proposed PECA and existing ENCCMA [13] algorithm was written in C# object oriented programing language using Visual studio framework 4.5, 2012. The PECA and city, highway and rural (CHR) radio propagating environment model [Ours] was incorporated into the SIMITS tool [27,28,29,30]. Experiments were conducted to evaluate the performance of PECA over ENCCMA in terms of throughput achieved, successful packet transmission and packet collision. The experiments were conducted considering different environments such as City, Highway and Rural. For all the simulation cases considered in this work, the speed of the vehicle was fixed to 20 cycles per frame, vehicles were varied from 20, 40 and 80 and performance was computed for city, highway and rural environments for both PECA and ENCCMA. Moreover, for evaluating PECA and ENCCMA under dense environments, the following simulation step was considered. Firstly, we considered a minimum of 20 and a maximum of 80 vehicles. Secondly, each vehicle initialized at the same location and they started contending for performing transmission. Then each vehicle started moving from its respective position one after the other. Further, a maximum of 40 slots were available at any given time for contending and performing transmission. Each message requires at least 4 slots for completing the transmission. Thus, a maximum of 10 vehicles can contend and perform transmission at any given time. Under this circumstance, the remaining 70 vehicles (i.e., considering 80 vehicles) will be waiting for contention. Under this setup, an improper scheduling method will lead to a high number of collisions and throughput degradation. Thus, this manuscript evaluates the proposed and existing model under such setups. The simulation parameter considered for evaluation are shown in

Table 1. Parameters.

Parameters	Value
Network	30 km × 30 km
MAC	ENCCMA & PECA
Modulation scheme	64-QAM
Mobility of Vehicles	20 cycle per frame
Bandwidth	27 Mbps
Frequency Channels	7
Vehicles	40, 20, & 80
Coding rate	0.75
Message size	75 bytes
Time slots	8 μs
Environment	Rural, City & Highway

.

5.1. Throughput Performance

Experiments were conducted to evaluate the performance of PECA and ENCCMA in terms of throughput achieved per channel for City, Highway and Rural as shown in Figure 1, Figure 2 and Figure 3, respectively, considering different vehicle densities. It is seen from Figure 1, the PECA improves throughput by 16.17%, 9.25% and 8.26% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average throughput improvement of 11.23% was achieved by PECA over ENCCMA for city environment. As seen from Figure 2, the PECA improves throughput by 14.12%, 18.01% and 21.93% considering 20, 40 and 80 vehicles, respectively, over ENCCMA. An average throughput improvement of 18.026% is achieved by PECA over ENCCMA for highway environment. Figure 3 shows the throughput performance for a rural environment. As seen from Figure 3, the PECA improves throughput by 16.42%, 40.38% and 16.17% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average throughput improvement of 24.32% is achieved by PECA over ENCCMA for a rural environment. The overall result achieved shows that PECA performs significantly better than ENCCMA considering varied vehicles and different environmental conditions, which shows the proposed model is adaptive in nature. However, the significant outcome attained by proposed PECA over existing ENCCMA is due to an efficient collision detection method under a shared channel environment. Further, based on collision likelihood information the slots are selected that maximize the system throughput.

5.2. Successful Packet Transmission Performance

Experiments evaluated the performance of PECA and ENCCMA in terms of successful packet transmission for City, Highway and Rural, as shown in Figure 4, Figure 5 and Figure 6, respectively, considering different vehicle densities. As seen from Figure 4, the PECA improves packet transmission by 14.58%, 11.06% and 6.54% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet transmission improvement of 10.93% is achieved by PECA over ENCCMA for a city environment. As seen from Figure 5, the PECA improves packet transmission by 14.89%, 28.00% and 21.90% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet transmission improvement of 21.59% is achieved by PECA over ENCCMA for a highway environment. The Figure 6 shows the packet transmission performance for a rural environment. It is seen from Figure 6, the PECA improves packet transmission by 23.25%, 19.60% and 11.62% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet transmission improvement of 18.16% is achieved by PECA over ENCCMA for a rural environment. The overall result achieved shows that PECA performs significantly better than ENCCMA considering varied vehicles and different environmental conditions in terms of packet transmission. Therefore, the significant outcome attained by the proposed PECA over existing ENCCMA is due to the efficient collision detection method. Thus, it aided in minimizing collision and maximize system throughput. As a result, the packet transmission in the network improved.

5.3. Collision Performance

We evaluated the performance of PECA and ENCCMA in terms of packet collision for City, Highway and Rural as shown in Figure 7, Figure 8 and Figure 9, respectively, considering different vehicle densities. As seen from Figure 7, the PECA reduces packet collision by 64.70%, 26.66% and 5.3% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet collision reduction of 32.22% is achieved by PECA over ENCCMA for a city environment. As seen from Figure 8, the PECA reduces packet collision by 27.77%, 32.81% and 15.58% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet collision reduction of 25.39% is achieved by PECA over ENCCMA for a highway environment. Figure 9 shows the packet collision performance for a rural environment. As seen from Figure 9, the PECA reduces packet collision by 51.51%, 33.76% and 08.53% considering 20, 40 and 80 vehicles respectively over ENCCMA. An average packet collision reduction of 31.27% is achieved by PECA over ENCCMA for rural environment. The overall result achieved shows that PECA performs significantly better than ENCCMA considering varied vehicles and different environmental conditions in terms of packet collision. However, the significant outcome attained by the proposed PECA over the existing ENCCMA is due to the efficient back off method post identifying collision in the network under a shared channel environment. Then, the average overhead is computed and updated in the channel allocation process under the shared channel environment. Thus, it aided in minimizing collision in the network.

6. Conclusions

This work describes a performance enriched and distribute MAC and for V2V and V2I, namely PECA. PECA overcomes the collision problem due to the channel access delay of CSMA/CA MAC of 802.11p. Here, we showed that the channel allocation problem is an NP-hard non-linear integer programming problem. When each user is given a dedicated channel for transmission for a certain period of time, it is called a non-shared channel allocation. When channels are shared among neighboring vehicles, each vehicle is given a certain amount of time for transmission. Note: in our work, the amount of time required for channel access is defined by two factors, that is, maximizing throughput and minimizing overhead. This work presents an efficient spectrum access mechanism (algorithm) on a multi-channel shared medium access network. The model aims to bring a trade-off between throughput and MAC performance. The model aims to maximize system throughput and minimize MAC overhead (collision). Two algorithms are presented, one for a non-shared channel and then for the shared channel network. First, based on the throughput gain requirement, the user selects the best available channel. Here, the user does not share the channel. The users access the channel for a stipulated session of time and then leave the channel for another user to access it. However, this algorithm does not utilize the bandwidth efficiently since the channel is not shared. To address this, in the second algorithm, a shared channel allocation algorithm is presented. Here, a set of users share the channel among neighboring users. A likelihood estimation for maximizing throughput and minimizing MAC overhead is modeled considering a multi user shared channel network. This algorithm utilizes bandwidth efficiently, which aids in minimizing collision and maximizing system throughput. Experiments are carried out to evaluate the performance of the proposed PECA and the existing ENCCMA in terms of throughput, successful packet transmission and collision. Experiments are carried out considering varied vehicles. The outcomes show significant performance improvement of PECA over ENCCMA, an average throughput improvement of 11.23%, 18.026% and 24.32% achieved by PECA over ENCCMA for city, highway and rural environments respectively, considering varied vehicles, an average packet transmission improvement of 10.93%, 21.59% and 18.16% achieved by PECA over ENCCMA for city, highway and rural environments respectively, considering varied vehicles, an average packet collision reduction of 32.22%, 25.39% and 32.27% achieved by PECA over ENCCMA for city, highway and rural environments respectively, considering varied vehicles. The significant throughput, successful packet transmission and collision outcome are attained due to the development of an efficient collision detection method. Further, using collision likelihood information, the slots are selected that maximize the system throughput. Additionally, the back off information is updated in the channel allocation process, aiding in reducing packet collision and improving successful packet transmission in high density/congested VANET. The overall result achieved shows the adaptiveness of the proposed MAC, considering varied devices and a radio propagating environment. Future work would consider provisioning security among V2V and V2I communication for both ENCCMA and PECA and evaluate their performance.