Blockchain and IoT-Driven Optimized Consensus Mechanism for Electric Vehicle Scheduling at Charging Stations

Abstract

The emerging demand for electric vehicles in urban cities leads to the need to install a huge number of charging stations. With this requirement, electric vehicle coordination and scheduling at charging stations in real-time becomes highly tedious. Thus, there is a need for an efficient scheduling mechanism for electric vehicle charging at charging stations. This paper proposes a novel blockchain and Internet of Things-based consensus mechanism called COME for secure and trustable electric vehicle scheduling at charging stations. The proposed mechanism is intending to resolve conflicts at charging stations. The integrated InterPlanetary File System protocol facilitates a cost-efficient mechanism with minimized bandwidth for electric vehicle scheduling. The proposed mechanism ensures that there is no loss for either the electric vehicle or the charging station. We formulate different scenarios for electric vehicle charging and apply different scheduling algorithms, including first-come first-served, longest remaining time first, and coalition game theory. The performance of the proposed COME consensus mechanism is estimated by comparing it with the practical Byzantine Fault Tolerance consensus protocol and traditional systems based on the charging demand, wait time, conflict resolution, scalability, and InterPlanetary File System bandwidth parameters. The performance results show that the proposed COME consensus mechanism ensures that electric vehicles can have their vehicle charged without any conflict and that the charging station can be satisfied in terms of profit. Moreover, the proposed COME consensus mechanism outperforms the both practical Byzantine Fault Tolerance consensus protocol and the traditional system in terms of scalability and conflict resolution along with additional parameters such as wait time, charging demand, and bandwidth analysis.

1. Introduction

Over the years, the demand for mobility and transportation has evolved significantly. As per reports, the number of vehicles on the road in 2015 was 1.1 billion cars and 377 million trucks [1], and this is expected to increase to as much as two billion by the year 2040 [2]. Due to the increasing number of vehicles, the governments of most countries have implemented various vehicle regulations and guidelines to reduce fuel consumption and the greenhouse effect [3]. Automobile industries have begun contributing towards the same by shifting a portion of the manufacturing momentum towards electric vehicles (EVs) [3]. As a result, the market demand for EVs has increased rapidly over the past several years. It has been observed in [4] that the EV stock will likely increase by as much as 120 million over the next ten years as consumers shift to EVs over internal combustion vehicles. Especially in smart cities, the adoption of EVs has increased tremendously in recent years due to the high cost, high maintenance, and low energy efficiency of fossil fuel vehicles [5].

As per the UK government’s decision, petrol vehicles are going to be phased out by 2030 in keeping with environmentally friendly planning [6]. However, the growth in the number of EVs requires the installation of a large amount of charging station (CS) infrastructure in order to enable efficient charging of EVs. The increase in demand for EVs is likely to overburden the request for charging points (CPs) at the CS [7]. Thus, it is necessary to efficiently acquire coordination policies for scheduling EVs at the CS without any conflicts. Many researchers worldwide have discussed various coordination schemes to schedule EVs for charging while ignoring the charging demand uncertainty and arrival time in real time [8]. However, these factors can make the CS less reliable for EVs, which can demotivate EV charging at that particular CS, leading to a loss for the CS [9]. To address the issues mentioned above, researchers around the world have tried to resolve them by implementing different coordination algorithms for EVs [10,11]. For example, Alvarez et al. [12] presented a hybrid artificial bee colony incorporated with local search algorithms to schedule EVs for charging. Qarebagh et al. [13] discussed a simulated annealing heuristic algorithm to resolve the position allocation problem for EV charging. To resolve the security and privacy issues in [13], Chamola et al. [14] investigated an internet of things (IoT) and edge computing-based architecture for secure and optimal EV charging scheduling. Similarly, Kumar et al. [15] adopted an IoT technology approach to secure EV scheduling using a Match Market and cryptography-based algorithm. Moreover, the authors of [16] designed an IoT-based efficient coordination mechanism between the EVs and CS using a Concurrent Transmission (CT)-based mechanism to schedule EVs in a reliable way.

In [17], Venkatakirthiga et al. formulated an optimization algorithm to schedule EVs for residential consumers in the form of a linear programming model. The authors in [18] discussed EV charging scheduling in residential networks with a two-step non-linear optimization approach. Lu et al. [19] proposed a decentralized price coordination algorithm for EV charging at a CS. They mainly focused on securing EV charging against adversarial and external attacks. Many researchers have suggested different coordination algorithms for EV scheduling [20,21]. However, most of these do not address scheduling of EVs at the CS or consider factors such as wait times, increased charging demand, conflict resolution, or IPFS bandwidth. Furthermore, there is little discussion in the literature of security and privacy issues arising in the context of EV scheduling. Several authors [14,15,16] have incorporated IoT-based frameworks for secure charging scheduling, although monitoring communications between EVs for charging can encounter various security attacks such as single-point-of-failure, eavesdropping, etc. [22]. Motivated by this apparent research gap, we introduce a novel blockchain and IoT-based consensus mechanism with an IPFS protocol to effectively monitor and schedule EVs at the CS. Moreover, the integration of blockchain technology with IPFS in the proposed COME mechanism overcomes the security and trust issues of IoT technology in order to further provides trustable and cost-efficient charging scheduling for EVs with minimal required bandwidth. Blockchain is becoming a disruptive technology in many industrial and service sectors [23]. To understand the utilization of blockchain in other industrial sectors, Agrawal et al. [24] carried out a case study on a blockchain-based framework for supply chain traceability to establish trust between supply chain participants in the network. Chiacchio et al. [25] proposed a non-fungible token solution to strengthen the tracking and tracing capability of the pharmaceutical supply chain utilizing blockchain technology. Auer et al. [26] presented a case study on blockchain and IoT-based shared mobility for car sharing and leasing to provide secure and authentic data storage for users. Furthermore, considering the modernization of the transportation system, the authors of [27] studied the use of a blockchain for data collection in the automotive industry sector in order to address challenges such as scalability, costs, privacy, security attacks, etc. Thus, the security advantages and applications of blockchain technology in varied industrial sectors motivates us to incorporate it into our proposed optimized consensus mechanism for EV scheduling.

The mechanism is designed to support the convenient charging of EVs while avoiding any financial loss on the part of the CS. The proposed mechanism aims to schedule arriving EVs for the multiple CPs available at a CS. It is applied to ensure that EVs do not need to search for another CS due to higher wait times, otherwise a particular CS may suffer from loss. This approach makes the mechanism reliable for both EVs and CS.

Many researchers have suggested solutions to coordinate EV scheduling at the CS, however, they have not discussed scenarios involving security when a large number of EVs simultaneously arrive at the CS. For example, in [12,14,15,17], the authors primarily emphasized scheduling EVs for charging. However, they did not explore which EV (emergency, low-energy, and sufficient energy EVs) should be allocated to each CP available at the CS. Furthermore, the adoption of IoT [14,15] does not provide a promising solution to mitigate the privacy issues involved in EV scheduling. Motivated by this, we introduce a blockchain and IoT-based consensus mechanism integrated with the IPFS to allocate CPs for EV charging at the CS. As a decentralized and transparent network, a blockchain can facilitate enhanced security and privacy in EV scheduling for the CPs at the CS. The main aim when integrating blockchain with IoT in the proposed consensus mechanism is to overcome the secure data storage issues of IoT for EV scheduling at the CS. Our approach ensures that data transactions added to the blockchain network cannot be altered or changed, which prevents data manipulation, data spoofing, Man-in-the-Middle (MITM), and other kinds of security attacks from disrupting the network. IPFS ensures low-cost transactions between EV and CS for efficient scheduling with the minimum bandwidth. The consensus mechanism is applicable based on the arrival of a number of EVs less than or up to a threshold number and whether there is any emergency situation or high authority EV arriving for charging at a particular CS. Moreover, EVs do not have to wait in the queue to charge, and the CS can benefit when the number of EVs arriving exceeds the threshold, which is resolved using the FCFS scheduling algorithm and coalition game theory approach in scenario 3. Thus, there is a need to introduce a blockchain-based consensus mechanism to schedule EVs to reach the CP on time within the threshold waiting time, leading to a benefit to the CS. We simulate the performance of the blockchain and IoT-based consensus mechanism considering different scenarios based on the arrival of a number of EVs (less, up to, or more than the threshold number) and in an emergency situation. All scenarios are simulated in the Remix IDE (Integrated Development Environment) using Solidity high-level language written as a self-executable code while fully considering various performance parameters.

In brief, the research contribution of this paper are as follows:

• We propose a novel blockchain and IoT-based consensus mechanism called COME for scheduling and monitoring EV use of available CPs at a CS. This approach is designed considering multiple scenarios based on the type and number of EVs arriving at the CS.
• We integrate IPFS with blockchain to attain minimum bandwidth and cost efficiency for communication between the EVs and CS during charging.
• We employ various scheduling algorithms and coalition game theory to resolve conflicts between EVs arriving at the CS.
• We evaluate the performance of the proposed COME consensus mechanism by considering various performance parameters, including wait time, conflict resolution, charging demand, scalability, and IPFS bandwidth.

The rest of this paper is organized as follows. Section 2 describes the operation of the consensus mechanisms considering different scenarios. Section 3 presents the experimental results. Finally, the paper is concluded in Section 4.

2. Preliminaries

Before discussing the optimized blockchain and IoT-based consensus mechanism for EV charging, we need to generalize the consensus mechanism by which the blockchain maintains data integrity and confidentiality in the network. Blockchain, as a distributed ledger technology, facilitates data storage in the form of a chain of blocks in a distributed manner without the involvement of any centralized authority [28]. Each block in the blockchain consists of data that is verified, validated, and appended to the next block to form a secure and preserved network. Therefore, a blockchain network proves to be entirely secure and transparent, adding transactions which are unalterable and thereby ensuring the confidentiality and verifiability of the network. The security of a blockchain network is due to the introduced consensus protocol, which ensures that all the participants or nodes agree on the validity of all transactions in order to prevent any malicious or adversarial attacks [29]. For example, if a transaction requested is added to the blockchain network, then all of the nodes in the network should be in consensus to add it to the network. Various consensus algorithms such as Proof of Work (PoW), Proof of Stake (PoS), Proof of Burn (PoB), and others can be used to facilitate security and data integrity in the blockchain network [30].

Here, we propose a blockchain-based consensus mechanism to schedule EVs for CPs at the CS. With the increasing number of EVs, it is becoming difficult to schedule them at the CS. The difficulty of the problem depends on the number and type of arriving EVs. For example, if the number of EVs arriving at the CS is the same as the number of CPs, then the EVs can each be directly allocated to a CP based on the FCFS algorithm. However, if the number of EVs arriving at the CS is more than the number of CPs, we need to consider different scenarios based on the type of EVs, i.e., emergency or high-authority vehicles, in order to coordinate them efficiently. This raises the need for the EVs and CS to be in consensus in order for them to be efficiently scheduled among the CPs. The CS avoids loss because adding data transactions to the blockchain network ensures that consensus between the EVs and CS is established securely and efficiently.

3. Consensus Mechanism

The blockchain and IoT-based COME consensus mechanism comprises various members, including different EVs and CS designed based on different scenarios. Blockchain as a decentralized and immutable framework is used to secure transactions between the EVs and CS for the purposes of charging. Figure 1 shows the scheduling of m number of EVs, i.e., {${\xi }_1,{\xi }_2,\dots ,{\xi }_m$} ∈${\xi }_e$ arriving for charging at n number of installed CPs, i.e., {${\chi }_1,{\chi }_2,\dots ,{\chi }_n$} ∈${\chi }_s$ at a CS embedded with the IoT devices, i.e., sound sensors to detect emergency vehicles (${\xi }_v$) arriving at the CS. Here, ${\xi }_v$ can be of two types: an emergency situation such as an ambulance, police vehicle, or fire brigade, and a less severe situation such as arrival of high-authority vehicle. The CS is equipped with RFID sensors to monitor and manage the energy (${\mathrm{Y}}_{{\xi }_e}$) of EVs at the time of their arrival. EVs with a timestamp order $\Delta ({\xi }_e)$, i.e., $\{\Delta ({\xi }_1),\Delta ({\xi }_2),\dots ,\Delta ({\xi }_m)\}$, ${\mathrm{Y}}_{{\xi }_e}$, and burst time (${\mathsf{\Lambda }}_{{\xi }_e}$) need to be scheduled at the CS; ${\Delta }_{{\xi }_e}$ for EVs can be written in ascending order in the form of $\{\Delta ({\xi }_1)<\Delta ({\xi }_2)<,\dots ,<\Delta ({\xi }_m)\}$:

$$\gamma =\left\{\begin{array}{cc}\epsilon \hfill & \mathrm{emergency\; vehicle}\hfill \\ \phi \hfill & \mathrm{no\; emergency\; vehicle}\hfill \end{array}\right.$$

(1)

Furthermore, we consider different scenarios for scheduling the number of arriving EVs at a CS with the assumption that the nodes, i.e., the EV and CS involved in the network, are responsive and honest, which prevents any malicious activity from disrupting the network. Moreover, it ensures reliable and secure coordination between the EV and CS in the network.

3.1. Scenario 1: Number of EVs Arriving Is Less Than the Number of CPs

In the first scenario, when the number of EVs arriving is less than or equal to the number of CPs at the CS, the EVs can be scheduled for charging in an optimal way using the First-Come First-Served (FCFS) algorithm. Arriving EVs can be scheduled directly at the CP based on their timestamp order $\Delta ({\xi }_e)$. However, Figure 2 shows that if there are ${\xi }_v$ EVs arriving at the CS, the EV that arrives first can search for another CP and ${\xi }_v$ can be allocated to the CP with priority. In case of an emergency situation, the EVs can be scheduled with the help of the execution time ${\theta }_{{\xi }_v}$ and turnaround time ${\vartheta }_{{\xi }_v}$ of ${\xi }_v$ using parameters $\Delta ({\xi }_v)$ and (${\mathsf{\Lambda }}_{{\xi }_v}$). The FCFS algorithm to allocate the EVs at a given CP can be defined as follows:

Definition 1.

FCFS is a scheduling algorithm that schedules EVs for charging at the CS based on their timestamp order $\Delta ({\xi }_e)$. It schedules EVs based on parameters such as the execution time (${\theta }_{{\xi }_v}$) and turn-around time (${\vartheta }_{{\xi }_v}$) of ${\xi }_v$, which can be expressed as follows:

$$\{{\theta }_{{\xi }_v},{\vartheta }_{{\xi }_v}\}=\{(\Delta ({\xi }_v),{\mathsf{\Lambda }}_{{\xi }_v}),({\theta }_{{\xi }_v},\Delta ({\xi }_v))\}$$

(2)

As per Definition 1, ${\theta }_{{\xi }_v}$ can be calculated using $\Delta ({\xi }_v)$ and ${\mathsf{\Lambda }}_{{\xi }_v}$. The other parameter, ${\vartheta }_{{\xi }_v}$, can be evaluated using ${\theta }_{{\xi }_v}$ and $\Delta ({\xi }_v)$, as shown in Equation (2). As discussed earlier, fewer EVs request to access the CS. For this reason, we implement the FCFS algorithm for scheduling EVs. However, if an EV arrives with for an emergency, the EV that arrives first can leave the CP to search for another slot at the CS. In this case, the emergency EV crew does not have to wait to before having their vehicle charged. The aforementioned parameters for scheduling EVs can be represented as follows:

$${\xi }_v(\epsilon ,\Delta ({\xi }_v))\stackrel{\mu }{\to }\sum _{s=1}^{n^{{}^{\prime }}}{\chi }_s,n^{{}^{\prime }}\le n,$$

(3)

$$\sum _{e=1}^{m^{{}^{\prime }}}{\theta }_{{\xi }_v}=\sum _{e=1}^{m^{{}^{\prime }}}\Delta ({\xi }_v)+\sum _{e=1}^{m^{{}^{\prime }}}{\mathsf{\Lambda }}_{{\xi }_v},m^{{}^{\prime }}\le m,e>0,$$

(4)

$$\sum _{e=1}^{m^{{}^{\prime }}}{\vartheta }_{{\xi }_v}=\sum _{e=1}^{m^{{}^{\prime }}}{\theta }_{{\xi }_v}-\sum _{e=1}^{m^{{}^{\prime }}}\Delta ({\xi }_v),$$

(5)

$${\xi }_e(\Delta ({\xi }_e),\phi )\stackrel{\beta }{\to }\sum _{s=1}^{n^{{}^{\prime }}}{\chi }_s,s>0.$$

(6)

where $m^{{}^{\prime }}$ signifies the number of arriving EVs associated with a timestamp order, execution time, burst time, and turnaround time for charging, $\beta$ denotes the EVs allocated for charging at the CPs based on the FCFS algorithm with the help of $\Delta ({\xi }_e)$, and $\mu$ signifies the ${\xi }_v$ allocated to $n^{{}^{\prime }}$ number of CPs in the case of an emergency.

Algorithm 1 shows the detailed procedure for scheduling m number of EVs at n number of CPs with the time complexity of $O(m)$ and $O(n)$.

Algorithm 1 FCFS algorithm for scheduling fewer EVs than CPs at CS

Input: $\Delta ({\xi }_e),{\mathsf{\Lambda }}_{{\xi }_v},\epsilon ,\phi$ Output: EV schedule with wait time ${\mathsf{\Theta }}_{{\xi }_e}$ for charging in case of emergency Initialization: e = 1, s = 1 1: procedureSchedule_EVs(${\xi }_e,{\chi }_s,EVs$) 2:   When $EVs$ arriving are less than CPs at a CS 3:   for $i=1,2,\dots ,m$ do 4:     for $j=1,2,\dots ,n$ do 5:       if $EVs\in {\xi }_v$ then 6:         ${\xi }_v(\epsilon ,\Delta ({\xi }_v))\stackrel{\mu }{\to }{\sum }_{}^{n^{{}^{\prime }}}{\chi }_s$ 7:         ${\sum }_{}^{m^{{}^{\prime }}}{\theta }_{{\xi }_v}={\sum }_{}^{m^{{}^{\prime }}}\Delta ({\xi }_v)+{\sum }_{}^{m^{{}^{\prime }}}{\mathsf{\Lambda }}_{{\xi }_v}$ 8:         ${\sum }_{}^{m^{{}^{\prime }}}{\vartheta }_{{\xi }_v}={\sum }_{}^{m^{{}^{\prime }}}{\theta }_{{\xi }_v}-{\sum }_{}^{m^{{}^{\prime }}}\Delta ({\xi }_v)$ 9:       else 10:         ${\xi }_e(\Delta ({\xi }_e),\phi )\stackrel{\beta }{\to }{\sum }_{}^{n^{{}^{\prime }}}{\chi }_s$ 11:       end if 12:     end for 13:   end for 14: end procedure

3.2. Scenario 2: Number of EVs arriving up to a Threshold Number

In the proposed consensus mechanism, the second scenario can be considered when the number of EVs entering with $\Delta ({\xi }_e)$ for charging is greater than the number of CPs. It is necessary to check the energy ${\mathrm{Y}}_{{\xi }_e}$ of the EVs, i.e., whether they arrive with energy lower than the threshold energy value for charging ($T{h}_E$). If the number of EVs arriving is up to a particular threshold number, i.e., $T{h}_{EVs}$, then EVs can be scheduled using the LRTF scheduling algorithm based on the parameter ${\mathrm{Y}}_{{\xi }_e}$. The number of EVs arriving within $T{h}_{EVs}$ can be scheduled based on the ${\mathrm{Y}}_{{\xi }_e}$, which can be represented as follows:

$${\mathrm{Y}}_{{\xi }_e}=\left\{\begin{array}{cc}\mathrm{\Xi }\hfill & \mathrm{Energy\; less\; than\; the\; threshold\; value}\hfill \\ {\mathrm{\Xi }}^{{}^{\prime }}\hfill & \mathrm{Energy\; crosses\; the\; threshold\; value}\hfill \end{array}\right.$$

(7)

Definition 2.

LRTF can be defined as a preemptive scheduling algorithm to schedule EVs based on their $\Delta ({\xi }_e)$ and energy ${\mathrm{Y}}_{{\xi }_m}$. LRTF works on the principle that the EVs arriving with $\Delta ({\xi }_e)$ along with energy ${\mathrm{Y}}_{{\xi }_e}$ less than the $T{H}_E$ receive priority for charging over other EVs with available energy ${\mathrm{Y}}_{{\xi }_e}$ greater than $T{H}_E$. It can be defined as

$${\xi }_e^{{\chi }_s}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi })>{\xi }_e^{{\chi }_s}({\mathrm{Y}}_{{\xi }_e})({\mathrm{\Xi }}^{{}^{\prime }})$$

(8)

As discussed in Definition 2, EVs with available energy ${\mathrm{Y}}_{{\xi }_e}$ less than $T{h}_E$ have the chance to charge their vehicles first. Due to the preemptive nature of the scheduling algorithm, it executes for a fixed amount of time T. After that, if EVs arrive with less available energy, they preempt the other EVs for charging.

There can be a case in which EVs arriving at the CS all have energy ${\mathrm{Y}}_{{\xi }_e}$ greater than $T{H}_E$; in this case, EVs are scheduled based on their $\Delta ({\xi }_e)$, i.e., the EVs that arrive first receive access to the CP first.

However, Figure 3 shows that if an emergency vehicle (${\xi }_v$) such as an ambulance arrives at the CS, it can preempt other EVs. Similarly, if all the EVs arriving at the CS are emergency vehicles, they are scheduled based on their $\Delta ({\xi }_v)$. The LRTF scheduling algorithm relies on parameters including the waiting time of EVs ($W{a}_{{\xi }_e}$) with energy ${\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})$, which can be calculated using the turnaround time ($T{u}_{{\xi }_e}$) of EVs with energy ${\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi })$ and execution time ($E{x}_{{\xi }_e}$) of EVs with energy ${\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi })$. The waiting time of ${\xi }_v$ is less than the waiting time of other EVs, as ${\xi }_v$ are preferred first for charging, i.e., {$W{a}_{{\xi }_v}<W{a}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))<W{a}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))$}. Thus, emergency vehicles with the highest priority can be scheduled for charging by preempting other EVs. Then, EVs with energy ${\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})$ have to wait for charging, meaning that EVs with energy ${\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi })$ can charge their vehicle based on the LRTF algorithm as shown in Algorithm 2. These parameters can be interpreted using $\Delta ({\xi }_e)$ and (${\mathsf{\Lambda }}_{{\xi }_e}$), which are represented as follows:

$${\xi }_v(\epsilon ,\Delta ({\xi }_v))\stackrel{\omega }{\to }\sum _{s=1}^{n^{{}^{″}}}{\chi }_s,$$

(9)

$$\sum _{e=1}^{m^{{}^{″}}}E{x}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))=\sum _{e=1}^{m^{{}^{″}}}\Delta ({\xi }_e)+\sum _{e=1}^{m^{{}^{″}}}{\mathsf{\Lambda }}_{{\xi }_e},m^{{}^{″}}\le m,$$

(10)

$$\sum _{e=1}^{m^{{}^{″}}}T{u}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))=\sum _{e=1}^{m^{{}^{″}}}E{x}_{{\xi }_e}-\sum _{e=1}^{m^{{}^{″}}}\Delta ({\xi }_e),$$

(11)

$$\sum _{e=1}^{m^{{}^{″}}}W{a}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))=\sum _{e=1}^{m^{{}^{″}}}T{u}_{{\xi }_e}-\sum _{e=1}^{m^{{}^{″}}}{\mathsf{\Lambda }}_{{\xi }_e},$$

(12)

$${\xi }_e({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{\iota }{\to }\sum _{s=1}^{n^{{}^{″}}}{\chi }_s,n^{{}^{″}}\le n.$$

(13)

where $m^{{}^{″}}$ denotes the number of EVs along with their timestamp order, execution time, burst time, waiting time, turnaround time, and available energy for charging, $\iota$ signifies the allocation of EVs to $n^{{}^{″}}$ number of CPs based on ${\mathrm{Y}}_{{\xi }_e}$, and $\omega$ shows the allocation of ${\xi }_v$ to CP at a CS. We use a Longest Remaining Time First (LRTF) scheduling algorithm instead of the FCFS algorithm due to the increase in the number of EVs up to a threshold number compared to the number of CPs. EVs can be scheduled according to their emergency status and energy requirements. Algorithm 2 shows the procedure for scheduleing m number of EVs at n number of CPs with time complexity $O(m)$ and $O(n)$.

Algorithm 2 LRTF algorithm for scheduling EVs arrived up to a threshold number

Input: $\Delta ({\xi }_e),{\mathsf{\Lambda }}_{{\xi }_e},\epsilon ,\phi ,{\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})$ Output: EVs schedule with waiting time $W{a}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))$ for charging Initialization: e = 1, s = 1 1: procedureSchedule_EVs(${\xi }_e,{\chi }_s,EVs$) 2:   When arriving $EVs$ are up to a threshold number 3:   for $i=1,2,\dots ,m$ do 4:     for $j=1,2,\dots ,n$ do 5:       if $EVs\in {\xi }_v$ then 6:         ${\xi }_v(\epsilon ,\Delta ({\xi }_v))\stackrel{\omega }{\to }{\sum }_{}^{n^{{}^{″}}}{\chi }_s$ 7:       else 8:         ${\sum }_{}^{m^{{}^{″}}}E{x}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))={\sum }_{}^{m^{{}^{″}}}\Delta ({\xi }_e)+{\sum }_{}^{m^{{}^{″}}}{\mathsf{\Lambda }}_{{\xi }_e}$ 9:         ${\sum }_{}^{m^{{}^{″}}}T{u}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))={\sum }_{}^{m^{{}^{″}}}E{x}_{{\xi }_e}-{\sum }_{}^{m^{{}^{″}}}\Delta ({\xi }_e)$ 10:         ${\sum }_{}^{m^{{}^{″}}}W{a}_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))={\sum }_{}^{m^{{}^{″}}}T{u}_{{\xi }_e}-{\sum }_{}^{m^{{}^{″}}}{\mathsf{\Lambda }}_{{\xi }_e}$ 11:         ${\xi }_e({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{\iota }{\to }{\sum }_{}^{n^{{}^{″}}}{\chi }_s$ 12:       end if 13:     end for 14:   end for 15: end procedure

3.3. Scenario 3: Number of EVs Arriving Exceeds the Threshold Number

In the third scenario, the number of EVs arriving at the CS crosses a particular threshold value $T{h}_{EVs}$, leading to a higher number of EVs than the number of CPs. Now, there can be a number of possible ways to schedule the arriving EVs in case of emergency or energy less than the threshold value. We consider an arrival queue ($A_q$($EVs$)) for EVs, which is divided into two more queues, i.e., a normal queue ($A_q^{nq}$($EVs$)) and priority queue ($A_q^{pq}$($EVs$)); $A_q^{nq}$($EVs$) contains EVs with energy ${\mathrm{Y}}_{{\xi }_e}$ greater than $T{H}_E$ and $A_q^{pq}$($EVs$) consists of a low-energy queue ($A_q^{pq}$($lq$)($EVs$)), i.e., EVs with energy ${\mathrm{Y}}_{{\xi }_e}$ less than $T{H}_E$. An emergency queue ($A_q^{pq}$($eq$)($EVs$)), i.e., EVs ${\xi }_v$, consists of emergency vehicles with the highest priority. Now, we need to consider the scheduled EVs $S_{{\xi }_e}$ at the CS with their timestamp order $S_{{\Delta }_{{\xi }_e}}$ based on which EVs can be scheduled. We consider a linked list $L{i}_{S_{{\xi }_e}}$ which contains the scheduled EVs, i.e., $S_{{\xi }_e}$ charging at the CPs with the assumption of energy ${\mathrm{Y}}_{{\xi }_e}$ greater than $T{H}_E$. The cases based on the arriving EVs for charging can be defined as follows:

3.3.1. Case 1: When Priority Queue Is Empty

In case 1, we consider an empty priority queue. This means that all the EVs arriving at the CS have energy ${\mathrm{Y}}_{{\xi }_e}$($\mathrm{\Xi }$), as mentioned in the previous scenario for the arrival of EVs up to a threshold number. However, as we are considering an assumption for $S_{{\xi }_e}$ of energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$), the arriving EVs can be scheduled for charging based on their timestamp order ${\Delta }_{{\xi }_e}$ using the FCFS algorithm. This means that the EVs arriving with the minimum timestamp order (${\Delta }^{min}({\xi }_e)$) receive preference for charging. Thus, Figure 4 shows that the EV with the minimum timestamp order has to wait for a particular time T to allow the scheduled EVs to charge their vehicles. Thus, EVs arriving with a minimum timestamp order can be allocated for charging with a waiting time of $W{a}_{{\xi }_e}^{nq}$ evaluated using execution time ($E{x}_{S_{{\xi }_e}}$) and turnaround time ($T{u}_{S_{{\xi }_e}}$) of the scheduled EV which has been charged vehicle first in the linked list $L{i}_{S_{{\xi }_e}}$ using $\Delta ({\xi }_e)$ and (${\mathsf{\Lambda }}_{{\xi }_e}$). The following associations to schedule EVs can be represented as follows:

$${\Delta }^{min}({\xi }_e)=min\{{\Delta }_{{\xi }_1},{\Delta }_{{\xi }_2},\dots \dots ,{\Delta }_{{\xi }_m\}}$$

(14)

$$S_{{\Delta }^{min}({\xi }_e)}=min\{S_{{\Delta }_{{\xi }_1}},S_{{\Delta }_{{\xi }_2}},\dots \dots ,S_{{\Delta }_{{\xi }_m\}}}$$

(15)

$$W{a}_{{\xi }_e}^{nq}=\left\{\begin{array}{cc}{ϵ}^{{}^{\prime }},\hfill & \mathrm{If\; EV\; wait\; for\; the\; limited\; time}\hfill \\ {\lambda }^{{}^{\prime }},\hfill & \mathrm{If\; EV\; cross\; the\; threshold\; time}\hfill \end{array}\right.$$

(16)

$$\sum _{e=1}^{l}E{x}_{S_{{\xi }_e}}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))=\sum _{e=1}^l{S}_{{\Delta }^{min}({\xi }_e)}+\sum _{e=1}^l{S}_{{\mathsf{\Lambda }}_{{\xi }_e}},l\le m,$$

(17)

$$\sum _{e=1}^{l}T{u}_{S_{{\xi }_e}}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))=\sum _{e=1}^{l}E{x}_{S_{{\xi }_e}}-\sum _{e=1}^l{S}_{{\Delta }^{min}({\xi }_e)},$$

(18)

$$\sum _{e=1}^{l}W{a}_{{\xi }_e}^{nq}({ϵ}^{{}^{\prime }},{\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})=\sum _{e=1}^{l}T{u}_{S_{{\xi }_e}}-\sum _{e=1}^l{S}_{{\mathsf{\Lambda }}_{{\xi }_e}},$$

(19)

$${\xi }_e({\Delta }^{min}({\xi }_e),({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{\eta }{\to }\sum _{s=1}^k{\chi }_s,k\le n.$$

(20)

where l represents the number of arriving EVs waiting to be scheduled based on the execution and turnaround times with the minimum timestamp and $\eta$ denotes the scheduling of EVs to k number of CPs on the basis of ${\Delta }^{min}({\xi }_e)$.

Algorithm 3 shows the detailed procedure to allocate m number of EVs in the normal queue to n number of CPs with time complexity $O(m)$ and $O(n)$.

Algorithm 3 Algorithm to schedule arriving EVs exceeding the threshold number

Input: $S_{{\xi }_e},\Delta ({\xi }_e),{\mathsf{\Lambda }}_{{\xi }_e},\epsilon ,\phi ,{\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}),r{e}_{S_{{\xi }_e}}$ Output: Arrived EVs exceeding the threshold number scheduled for CP with waiting time $W{a}_{{\xi }_e}^{nq}$, $W{a}_{{\xi }_e}^{nlq}$, and $W{a}_{{\xi }_v}^{NP}$ Initialization: e = 1, s = 1 1: procedureSchedule_EVs(${\xi }_e,{\chi }_s,EVs$) 2:   When $EVs$ arriving are less than CPs at CS 3:   for $i=1,2,\dots ,m$ do 4:     for $j=1,2,\dots ,n$ do 5:       if $A_q^{pq}$($EVs)\in \varnothing$ then 6:         ${\sum }_{}^{l}E{x}_{S_{{\xi }_e}}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))={\sum }_{}^l{S}_{{\Delta }^{min}({\xi }_e)}+{\sum }_{}^l{S}_{{\mathsf{\Lambda }}_{{\xi }_e}}$ 7:         ${\sum }_{}^{l}T{u}_{S_{{\xi }_e}}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))={\sum }_{}^{l}E{x}_{S_{{\xi }_e}}-{\sum }_{}^l{S}_{{\Delta }^{min}({\xi }_e)}$ 8:         ${\sum }_{}^{l}W{a}_{{\xi }_e}^{nq}({ϵ}^{{}^{\prime }},{\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})={\sum }_{}^{l}T{u}_{S_{{\xi }_e}}-{\sum }_{}^l{S}_{{\mathsf{\Lambda }}_{{\xi }_e}}$ 9:         ${\xi }_e({\Delta }^{min}({\xi }_e),({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }})),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{\eta }{\to }{\sum }_{}^k{\chi }_s$ 10:       else if ($A_q^{pq}$($eq$)($EVs$)) $\in \varnothing$ then 11:         ${\sum }_{}^{l^{{}^{\prime }}}W{a}_{{\xi }_e}^{nlq}={\sum }_{}^{l^{{}^{\prime }}}\{P{t}_{S_{{\xi }_e}}^{nlq}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))-S{t}_{{\xi }_e}^{nlq}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))\}$ 12:         ${\xi }_e({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi }),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{{\eta }^{{}^{\prime }}}{\to }{\sum }_{}^{k^{{}^{\prime }}}{\chi }_s$ 13:         ${\xi }_e({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi }))\stackrel{r{e}_{S_{{\xi }_e}}}{\to }{\sum }_{}^{l^{{}^{\prime }}}{S}_{{\Delta }^{min}({\xi }_e)}$ 14:       else 15:         ${\sum }_{}^{o}W{a}_{{\xi }_v}^{NP}={\sum }_{}^o{\mathsf{\Psi }}_{{\xi }_e}^{NP}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))-{\sum }_{}^o{\psi }_{{\xi }_v}^{NP}$ 16:         ${\xi }_v({\zeta }_{{\xi }_v},{\mathsf{\Lambda }}_{{\xi }_e},\epsilon )\stackrel{{\eta }^{{}^{″}}}{\to }{\sum }_{}^{o^{{}^{\prime }}}{\chi }_s$ 17:         ${\xi }_v({\zeta }_{{\xi }_v})\stackrel{r{e}_{S_{{\xi }_e}}}{\to }{\sum }_{}^o{S}_{{\Delta }^{min}({\xi }_e)}$ 18:       end if 19:     end for 20:   end for 21: end procedure

3.3.2. Case 2: Emergency Queue Is Empty

We consider this case to schedule EVs for charging when all of the arrived EVs belong to the normal queue and low energy queue, i.e., the emergency queue is empty. Thus, we want to schedule EVs arriving with energy ${\mathrm{Y}}_{{\xi }_e}$($\mathrm{\Xi }$) and ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) present in the low energy queue and normal queue for charging at the CS with the assumption that all scheduled EVs are of energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$). EVs can be scheduled for charging using the FCFS algorithm by assigning priority to EVs. The assigned priority can be expressed as {${\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi })$>${\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})({\mathrm{\Xi }}^{{}^{\prime }})$}, in which higher priority is assigned to EVs with energy ${\mathrm{Y}}_{{\xi }_e}$ less than $T{H}_E$ over EVs which already have sufficient energy. Thus, Figure 5 shows that when EVs with higher priority arrive at the CS, the vehicle can be allocated charging priority. However, if EVs arrive with the same priority, we can consider the previous case to schedule EVs using the FCFS algorithm based on their timestamp order. EVs with higher priority can replace the scheduled EV with the minimum timestamp order in a preemptive way. According to the assumption, all the EVs present in the linked list $L{i}_{S_{{\xi }_e}}$ have energy greater than $T{H}_E$. Thus, a scheduled EV that is been replaced has to be inserted in the waiting queue $W_q(EVs)$.

As discussed, a higher priority is assigned to EVs in the low energy queue; they can directly preempt scheduled EVs based on their timestamp order. The wait time $W{a}_{{\xi }_e}^{nlq}$ associated with the EVs present in the low energy queue can be evaluated using the preemption time ($P{t}_{{\xi }_e}$) and scheduling time ($S{t}_{{\xi }_e}$) while preempting the scheduled EV with the minimum timestamp order. As the scheduled EV that has been replaced has to wait in the wait queue $W_q(EVs)$, the high priority EV provides the replaced EV with a reward ($r{e}_{S_{{\xi }_e}}$). The parameters for scheduling a high priority EV can be represented as follows:

$$\sum _{e=1}^{l^{{}^{\prime }}}W{a}_{{\xi }_e}^{nlq}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }))=\sum _{e=1}^{l^{{}^{\prime }}}P{t}_{S_{{\xi }_e}}^{nlq}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))-\sum _{e=1}^{l^{{}^{\prime }}}S{t}_{{\xi }_e}^{nlq}({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi })),$$

(21)

$${\xi }_e({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi }),{\mathsf{\Lambda }}_{{\xi }_e},\phi )\stackrel{{\eta }^{{}^{\prime }}}{\to }\sum _{s=1}^{k^{{}^{\prime }}}{\chi }_s,k^{{}^{\prime }}\le n,$$

(22)

$${\xi }_e({\mathrm{Y}}_{{\xi }_e}(\mathrm{\Xi }),{\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi }))\stackrel{r{e}_{S_{{\xi }_e}}}{\to }\sum _{e=1}^{l^{{}^{\prime }}}{S}_{{\Delta }^{min}({\xi }_e)},l^{{}^{\prime }}\le m.$$

(23)

where $l^{{}^{\prime }}$ denotes the number of EVs waiting to be scheduled for charging based on the wait time calculated using $P{t}_{{\xi }_e}$ and $S{t}_{{\xi }_e}$ and ${\eta }^{{}^{\prime }}$ shows the number of EVs with energy less than the threshold value associated with $k^{{}^{\prime }}$ number of CPs for charging.

Algorithm 3 shows the procedure to schedule m number of EVs present in the normal queue and low energy queue at n number of CPs with time complexity $O(m)$ and $O(n)$.

3.3.3. Case 3: When EVs in the Priority Queue and Normal Queue Exceed the Threshold Number

EVs are scheduled for charging with a certain assigned priority. In the previous case, EVs arrive with energy ${\mathrm{Y}}_{{\xi }_e}$($\mathrm{\Xi }$) and ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$). However, if an emergency vehicle ${\xi }_v$ arrives at the CS, the priority order can be arranged further, i.e., {${\zeta }_{{\xi }_v}$>${\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})(\mathrm{\Xi })$>${\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})({\mathrm{\Xi }}^{{}^{\prime }})$}. Having already scheduled EVs with energy less than the threshold value in the previous case, in this case we consider the assumption that the linked list contains EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$).

Here, Figure 6 shows that the arrival of EVs ${\xi }_v$ in case of emergency with the highest priority can be scheduled by preempting the EV with the lowest priority, i.e., EVs with energy ${\mathrm{Y}}_{{\xi }_e}$ greater than $T{H}_E$ based on their timestamp order. This means the EV with the highest priority can charge its vehicle by replacing the scheduled EV with the lowest priority, i.e., $S_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$), present in the linked list $L{i}_{S_{{\xi }_e}}$. Similarly, when EVs with the same priority arrive, we can consider the previous case, i.e., Case 1, to schedule EVs based on their timestamp order. The waiting time $W{a}_{{\xi }_v}^{NP}$ involved in scheduling ${\xi }_v$ in case of emergency can be evaluated using the preemption time (${\mathsf{\Psi }}_{{\xi }_e}^{NP}$) and allocation time (${\psi }_{{\xi }_v}^{NP}$) required to schedule the EV with the highest priority. Now, a reward $r{e}_{S_{{\xi }_e}}$ is transferred to the sacrificing scheduled EV, i.e., $S_{{\xi }_e}$ of energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$). Similarly, $S_{{\xi }_e}$ has to wait in the waiting queue $W_q(EVs)$ with the lowest priority, as we mentioned in the previous case. Algorithm 3 shows the procedure to schedule m number of EVs in normal and priority queue at n number of CPs with time complexity $O(m)$ and $O(n)$. The associations required for scheduling can be represented as follows.

$$\sum _{e=1}^{o}W{a}_{{\xi }_v}^{NP}=\sum _{e=1}^o{\mathsf{\Psi }}_{{\xi }_e}^{NP}({\mathrm{Y}}_{{\xi }_e}({\mathrm{\Xi }}^{{}^{\prime }}))-\sum _{e=1}^o{\psi }_{{\xi }_v}^{NP},o\le m,$$

(24)

$${\xi }_v({\zeta }_{{\xi }_v},{\mathsf{\Lambda }}_{{\xi }_e},\epsilon )\stackrel{{\eta }^{{}^{″}}}{\to }\sum _{s=1}^{o^{{}^{\prime }}}{\chi }_s,o^{{}^{\prime }}\le n,$$

(25)

$${\xi }_v({\zeta }_{{\xi }_v})\stackrel{r{e}_{S_{{\xi }_e}}}{\to }\sum _{e=1}^o{S}_{{\Delta }^{min}({\xi }_e)}.$$

(26)

where o indicates the number of EVs in case of emergency waiting to be scheduled for charging and ${\eta }^{{}^{″}}$ denotes the number of EVs associated with $o^{{}^{\prime }}$ number of CPs for charging.

In this scenario, after EVs are scheduled in an emergency, the next EV with higher priority and energy ${\mathrm{Y}}_{{\xi }_e}$($\mathrm{\Xi }$) can be scheduled similarly, as mentioned in the previous case. However, now there is an emergency EV scheduled in the linked list that cannot be preempted, as it has the highest priority. Thus, the EV with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) again has to wait for charging.

Here, we have observed from all the cases that there can be an issue of starvation for EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$), i.e., greater than the threshold value. As in Case 2 and Case 3, EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) with the lowest priority must remain in the wait queue $W_q(EVs)$ to charge their vehicles. If the waiting time for EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) considering the different cases exceeds the particular threshold time ($T{h}_{W_q(EVs)}$), it is necessary to introduce a game theory approach to ensure that these vehicles are able to charge.

3.3.4. When the Waiting Time of EVs Exceeds the Threshold Time

We have discussed various scenarios to schedule EVs based on several different cases. However, in Case 3 the number of EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) waiting in the queue reaches the threshold waiting time. This leads to the issue of starvation for EVs waiting to have their vehicles charged. Thus, we introduce a game theoretical approach for EVs waiting in the queue with the assumption that they receive the opportunity to charge when there is an emergency vehicle in less severe condition. To thid end, we divide emergencies into two categories: first, a critical situation such as an ambulance, fire brigade, or police vehicle, and second, a less severe condition such as the arrival of a high-authority vehicle. Thus, we can consider that if there is no emergency, EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) can waiting in the queue for their chance to charge their vehicle based on the timestamp order $ϵ$ according to the available charging slots. This can be represented as follows.

$${\xi }_v=\left\{\begin{array}{cc}ϵ\hfill & \mathrm{No\; severe\; emergency}\hfill \\ \lambda \hfill & \mathrm{Severe\; emergency}\hfill \end{array}\right.$$

(27)

Here, we adapt a coalition game theory approach by which EVs waiting in the $W_q(EVs)$ can form a coalition with ${\xi }_e$ in case of a less severe emergency. We use the idea of transferable utility (TU) to transfer a reward to the cooperating EV. The coalition and TU can be represented as follows.

Coalition Game: the coalition game $K_g$ comprises of a set $\{P,{\omega }^{{}^{\prime }}\}$, where P denotes the number of players $\{1,2,\dots ,p,\dots N\}$, which is P = $\{{\xi }_1,{\xi }_2,\dots \dots ,{\xi }_m\}$, and ${\omega }^{{}^{\prime }}$ is the coalition function mapped as a real valued number ${\omega }^{{}^{\prime }}:2^P\to \mathbb{R}$ and can be computed as the maximum output to each coalition ${\mathsf{\Psi }}^{{}^{\prime z}}\subseteq P$ [31,32].

TU Game: We use the concept of the TU game in which ${\omega }^{{}^{\prime }}({\mathsf{\Psi }}^{{}^{\prime z}})$ is a real-valued function for coalition ${\mathsf{\Psi }}^z\subseteq P$ formed among EVs who agree to form a coalition with EVs ${\xi }_e$ waiting in the queue for charging to transfer the reward to the contributing EV ${\xi }_v(ϵ)$ in case of no severe emergency. We use the Shapley value as a solution to provide EVs cooperating in a coalition with rewards. The Shapley value (${\pi }_p({\omega }^{{}^{\prime }})$) works on the principle that a reward is transferred to the contributing EV based on their forming of a coalition ${\mathsf{\Psi }}^{{}^{\prime }}$. The reward transferred for player ${\xi }_v(ϵ)\in P$ considering the Shapley value for coalition ${\mathsf{\Psi }}^{{}^{\prime }}$ can be interpreted as follows [31]:

$${\pi }_{{\xi }_v}({\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ)=\sum _{\forall {\mathsf{\Psi }}^{{}^{\prime }}\subseteq P}^{}\frac{(|{\mathsf{\Psi }}^{{}^{\prime }}|-1)!.(P-|{\mathsf{\Psi }}^{{}^{\prime }}|)!}{P!}.({\omega }^{{}^{\prime }}({\mathsf{\Psi }}^{{}^{\prime }})-{\omega }^{{}^{\prime }}({\mathsf{\Psi }}^{{}^{\prime {\xi }_e}}))$$

(28)

s.t.

$$({\xi }_1,{\xi }_2,\dots \dots ,{\xi }_m)\in {\mathsf{\Psi }}^{{}^{\prime }}$$

(29)

The cooperative game consists of N players, i.e., $\{{\xi }_1,{\xi }_2,\dots \dots ,{\xi }_m\}$, in which players ${\xi }_e(W_q(EVs))$ and ${\xi }_v$ both try to charge their vehicles prior to others. Both players decide on a strategy to achieve the same by maximizing their priority, i.e., ${\zeta }_{{\xi }_e}({\mathrm{Y}}_{{\xi }_e})({\mathrm{\Xi }}^{{}^{\prime }})$ and ${\zeta }_{{\xi }_v}$. We can represent the strategy ($S{r}_{EVs}$) as follows:

$$\{{\xi }_v((A_q^{pq}(eq)),ϵ),{\xi }_e(W_q(EVs))\}=max\sum _{e=1}^m\{{\zeta }_{{\xi }_v},{\zeta }_{{\xi }_e}\}$$

(30)

Thus, players try to charge their vehicle before others with the help of strategy $S{r}_{EVs}$. However, if this strategy is followed, then EVs waiting in the queue for a long time do not have the chance to charge. This leads to a loss for the CS if they decide to search for another CS to have their vehicle charged.

Therefore, EVs waiting in the queue can form a coalition with arriving emergency vehicle with no severity. This means that EVs have the opportunity to charge in case of the arrival of ${\xi }_v(ϵ)$ with no severe condition. In return, the EV that has the opportunity to charge has to transfer a reward to the contributing ${\xi }_v$. This condition forms a Nash Equilibrium in which EVs waiting in the queue can receive the chance to charge and contributing EVs receive a reward ${\pi }_{{\xi }_v}({\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ)$ calculated using the Shapley value for the same, leading to benefit for both EVs and the CS in the coalition. Algorithm 4 shows the procedure for scheduling m number of EVs with energy ${\mathrm{Y}}_{{\xi }_e}$(${\mathrm{\Xi }}^{{}^{\prime }}$) waiting in the queue at n number of CPs using coalition game theory with time complexity $O(m)$ and $O(n)$. This can be represented as follows:

$${\xi }_e(W_q(EVs))\stackrel{f}{\to }\sum _{s=1}^{f^{{}^{\prime }}}{\chi }_s,f^{{}^{\prime }}\le n,$$

(31)

$${\xi }_e(W_q(EVs))\stackrel{{\pi }_{{\xi }_v}({\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ)}{\to }\sum _{e=1}^b{\xi }_v((A_q^{pq}(eq)),ϵ)$$

(32)

where f denotes the scheduling of EVs waiting in the queue at $f^{{}^{\prime }}$ number of CPs at the CS.

Algorithm 4 Algorithm to schedule EVs for charging when waiting time exceeds the threshold value

Input: $((A_q^{pq}(eq)),ϵ),(W_q(EVs)),{\zeta }_{{\xi }_e},{\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ$ Output: EVs waiting in the queue scheduled for charging Initialization: e = 1, s = 1 1: procedureSchedule_EVs(${\xi }_e,{\chi }_s,EVs$) 2:   When waiting time for $EVs$ exceeds the threshold value 3:   if $EVs\in \{{\xi }_v((A_q^{pq}(eq)),ϵ),{\xi }_e(W_q(EVs))\}$ then 4:     for $i=1,2,\dots ,m$ do 5:       $\{{\xi }_v((A_q^{pq}(eq)),ϵ),{\xi }_e(W_q(EVs))\}=max{\sum }_{}^m\{{\zeta }_{{\xi }_v},{\zeta }_{{\xi }_e}\}$ 6:     end for 7:     for each {$P,{\mathsf{\Psi }}^{{}^{\prime z}}$} do 8:       ${\pi }_{{\xi }_v}({\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ)={\sum }_{\forall {\mathsf{\Psi }}^{{}^{\prime }}\subseteq P}^{}\frac{(|{\mathsf{\Psi }}^{{}^{\prime }}|-1)!.(P-|{\mathsf{\Psi }}^{{}^{\prime }}|)!}{P!}.({\omega }^{{}^{\prime }}({\mathsf{\Psi }}^{{}^{\prime }})-{\omega }^{{}^{\prime }}({\mathsf{\Psi }}^{{}^{\prime {\xi }_e}}))$ 9:     end for 10:     for $i=1,2,\dots ,m$ do 11:       for $j=1,2,\dots ,n$ do 12:         ${\xi }_e(W_q(EVs))\stackrel{f}{\to }{\sum }_{}^{f^{{}^{\prime }}}{\chi }_s$ 13:         ${\xi }_e(W_q(EVs))\stackrel{{\pi }_{{\xi }_v}({\omega }^{{}^{\prime }},{\mathsf{\Psi }}^{{}^{\prime }},ϵ)}{\to }{\sum }_{}^b{\xi }_v((A_q^{pq}(eq)),ϵ)$ 14:       end for 15:     end for 16:   end if 17: end procedure

Thus far, we have considered different scenarios to perform EV scheduling at a CS with the help of a blockchain network incorporating IPFS. Scheduling is based on different scenarios involving the arrival of emergency, low-energy, and sufficient-energy EVs. The blockchain network keeps track of the users, i.e., EVs and CS, during scheduling. Thus, even if a malicious EV tries to access the CS, it is only charged based on its requirements. In this way, the blockchain can deny the request of a particular EV for charging to ensure that other EVs are not delayed. The introduction of the blockchain network ensures that EVs are scheduled in a secure and trusted manner based on the discussed scenarios.

4. Experimental Results

This section presents a performance analysis of the proposed consensus mechanism, COME, in comparison with the traditional pBFT mechanism, considering the parameters waiting time, conflict resolution, and charging demand for EVs. The results are simulated with proposed consensus mechanism to schedule the EVs at the CP to ensure that EVs can be charged conveniently and the CS does not suffer any loss. We discuss different scenarios involving the number of EVs arriving at CPs below and up to a threshold number using the FCFS and LRTF scheduling algorithms considering scenario 1 and scenario 2. Moreover, if the waiting time of the EVs exceeds the threshold time in scenario 3, coalition game theory is implemented considering emergency or less severe situations; otherwise, the FCFS algorithm is implemented to schedule EV charging.

Furthermore, we consider a blockchain network for EV scheduling in which additional parameters such as scalability and IPFS bandwidth are used to highlight the benefits of the blockchain and IPFS-based proposed consensus mechanism in COME compared to traditional systems. The results of the proposed mechanism are evaluated after executing the smart contracts of the consensus mechanism considering different scenarios to schedule EVs at the CS in Remix IDE using Solidity written as a self-executable, which ensures the security of the system by authenticating the identity of involved nodes in the network [33]. The simulated results for the proposed consensus mechanism are as follows.

4.1. Waiting Time for EVs

Figure 7 shows the waiting time with the increase in the number of EVs arriving at the CS based on the scenarios. In scenario 1, we consider a number of EVs arriving at the CS that is less than the number of available CPs ($EVs<CPs$). Then, EV scheduling is performed based on the FCFS algorithm to ensure that EVs can receive a CP at the CS for charging based on their timestamp order. However, an emergency vehicle always receives priority to charge at the CP. In scenarios 2 and 3, we consider EVs arriving up to a threshold number ($EVs>CPs$) and EVs arriving exceeding the threshold number ($EVs>CPs$). For scenario 2, EVs can be scheduled at a CP using the LRTF scheduling algorithm. In scenario 3, we consider different scenarios based on the arrival of emergency EVs or EVs with energy less than the threshold value. Here, considering all of these simulated scenarios in a wait time comparative analysis of the different considered algorithms. The graph depicts that in scenario 1 the waiting time for EVs is zero, as they do not have to wait for a CP, even in an emergency, as they can simply search for another available CP for charging. In scenario 2, as the number of EVs increases up to a threshold number, the waiting time for EVs increases due to the arrival of EVs with energy less than the threshold value or in emergencies. In scenario 3, the wait time is quite a lot higher than in scenario 2 due to the number of EVs exceeding the threshold number. The graph shows that when EVs must wait up to a threshold wait time, the wait time tends to be constant due to the applied coalition game theory approach, as EVs waiting in the queue have a chance to charge.

4.2. Conflict Resolution for EVs

Figure 8 shows a comparison of conflict resolution of the proposed mechanism and practical Byzantine Fault tolerance (pBFT) over the increase in the number of EVs arriving at the CS. The comparison shows that with fewer EVs arriving at the CS, both consensus protocols can process the requests for charging at the same level, however, as the number of EVs arriving at the CS exceeds the threshold number, the proposed mechanism can resolve conflicts better than the pBFT protocol. This is because we use both scheduling algorithms and a game theoretical approach to allocate EVs above than the threshold number for charging. Thus, the proposed mechanism seems to be more beneficial in resolving conflicts efficiently than pBFT, and can further encourage EVs to opt for charging at the CS. Moreover, we consider several scenarios for EV scheduling at the CS based on the number and type of EVs, i.e., emergency or high-authority vehicles, showing the applicability of the proposed COME mechanism in dynamic scenarios.

4.3. Charging Demand for EVs

Figure 9 depicts the number of requests that can be processed with the increase in charging demand for EVs. It can be seen from the graph that with a lesser charging demand from EVs the number of requests that need to be processed is quite low. However, as the charging demand for EVs increases, the number of requests processed increases exponentially. This is due to the scheduling algorithms and coalition game theory approach applied to schedule EVs for charging without any conflict. Moreover, the proposed mechanism is quite efficient in dealing with increasing EV charging demand due to the applied scheduling algorithms, i.e., FCFS and LRTF, and coalition game theory approach.

4.4. Scalability

Figure 10 shows a scalability comparison of the blockchain and IPFS-based proposed consensus mechanism with the blockchain as data storage. In the proposed mechanism, IPFS helps to acquire the minimized bandwidth for data storage of the EVs and CSs. Therefore, it can be perceived from the graph that the proposed mechanism with IPFS tends to be highly scalable with an increasing number of transactions. However, the use of a blockchain as data storage yields poor results in terms of scalability. Due to the increase in the number of transactions, the blockchain network has to store a whole block of transactions, which is quite costly for users. Therefore, the blockchain and IPFS-based proposed consensus mechanism provides better results in terms of scalability than using a blockchain for data storage. By incorporating IPFS in the proposed mechanism, COME strengthens the scalability of the blockchain by facilitating data storage access for users, i.e., the EVs and CS, with the help of the cryptographic hashes generated by the IPFS.

4.5. IPFS Bandwidth Analysis

Figure 11 depicts the bandwidth requirements of the IPFS data storage protocol employed in the proposed consensus mechanism. Users, i.e., the EVs and CS, can store their data for scheduling in the IPFS in the form of hashes. This seems to improve data storage in the proposed system in terms of cost efficiency; furthermore, it can be observed from the graph that minimal IPFS bandwidth is required to perform data storage in the proposed consensus mechanism. The bandwidth analysis is carried out by installing the setup of IPFS in the local system to incorporate the data using the generated cryptographic hash. In this way, the IPFS can directly assign the hash keys to the users, i.e., the EVs and CS, to accomplish their data storage requests. Furthermore, users can efficiently perform data transactions over the blockchain network with the help of the cost-efficient IPFS.

5. Discussion and Conclusions

5.1. Discussion

A rapid surge in EVs can overburden the limited number of CPs at the CS, necessitating a coordination algorithm to optimally schedule EVs at the CS for charging. For example, the arrival of EVs (both emergency and non-emergency vehicles) at the CS requires a procedure by which the scheduling of EVs can be prioritized for charging and to prevent delay or dissatisfaction among EVs while charging. Various advanced optimization algorithms such as heuristics, metaheuristics, and hybrid algorithms have been explored to perform EV scheduling in different domains such as online learning, transportation, healthcare, multi-objective optimization, data classification, etc. The research works include Dulebenets’ [34] proposal of a diploid evolutionary algorithm to enable sustainable cross-docking management for truck scheduling, which showed improved performance compared to a conventional evolutionary algorithm. The authors of [35] studied a berth scheduling case study with the help of an applied linear programming model based on the self-adaptive parameter control strategy. Later, [36] extended the previous work in [34] to perform adaptive and low service cost truck scheduling at a cross-docking terminal utilizing the Polyploid Memetic Algorithm. However, the above-mentioned research works do not focus on performance parameters such as wait time, conflict resolution, charging demand, scalability, and IPFS bandwidth analysis with the increase in the number of EVs for charging. Therefore, considering that the increasing number of EVs can overburden charging infrastructure, it is necessary to manage this issue. Thus, we have proposed a blockchain and IoT-driven consensus mechanism for optimal EVs scheduling at the CS. We have presented different scenarios for optimal allocation of EVs for charging, which are designed by utilizing scheduling algorithms and a coalition game theory approach based on the number of EVs, i.e., whether the number exceeds the threshold or not. If the number of EVs arriving is less than the number of CPs, then the FCFS scheduling algorithm is utilized to allocate the EVs to CPs for charging, as discussed in scenario 1. Scenario 2 involves a number of EVs arriving up to a threshold number. In this scenario, we check their available energy to enable efficient scheduling at the CS using the LRTF algorithm. Finally, scenario 3 involves a number of EVs that exceeds the threshold number. In scenario 3, different cases are considered based on the arrival of emergency vehicles or the available energy associated with the EVs for allocation to a CS with the help of the scheduling algorithms and the coalition game theory approach. Hence, we have specified several scenarios to enable optimized and efficient coordination between nodes, i.e., the EVs and CS, involved in the blockchain network. Therefore, the proposed consensus mechanism, COME, is designed utilizing several algorithms which ensure that the participating nodes in the network are in consensus, with the assumption that only honest and responsive nodes are involved. Finally, the blockchain-based proposed consensus mechanism is simulated in Remix IDE considering the designed scenarios in terms of parameters, i.e., wait time, conflict resolution, charging demand, scalability, and IPFS bandwidth analysis. In future work, the performance of the proposed blockchain-based consensus mechanism can be improved by considering a scenario that lessens the effect of any involvement of dishonest or non-responsive nodes, which can interrupt the scheduling of EVs at the CS.

5.2. Conclusions

This paper has proposed an optimized blockchain and IoT-based consensus mechanism, COME, to schedule EVs for charging at a CS. With the increase in the number of EVs, it is becoming difficult to coordinate them efficiently at a CS, especially in case of emergency EVs or high-authority vehicles. We explored various traditional consensus protocols and obtained insights into their charging demand, wait time, scalability, and IPFS bandwidth issues. The aforementioned challenges can discourage EVs from charging, leading to a loss for the CS. Therefore, we applied different scheduling algorithms such as FCFS, LRTF, and coalition game theory over diverse scenarios to resolve conflicts between EVs and the CS. Scenarios were considered based on the number of EVs arriving at the CS and the emergency situation. For example, if the number of EVs arriving at the CS is less than or up to a threshold number, scheduling can be resolved using the FCFS and LRTF scheduling algorithms considered in scenario 1 and scenario 2. Moreover, if EVs arriving at the CS exceed the threshold number, the different cases considered here for EV scheduling using FCFS and the coalition game theory approach can be relied on. Finally, the performance of the proposed consensus mechanism has been simulated by executing the smart contracts in Remix IDE implemented using Solidity high-level language and considering performance metrics such as charging demand, wait time, conflict resolution, scalability, and IPFS bandwidth in comparison with the traditional pBFT consensus protocol. The comparisons shows that the proposed COME mechanism outperforms the traditional system in terms of security, reliability, and conflict resolution.

In the future, the performance of the proposed consensus mechanism can be optimized in case of the arrival of a number of EVs when the wait time exceeds the threshold time by using different game theory approaches in dynamic real-time scenarios. Moreover, several advanced optimization algorithms, i.e., heuristics, metaheuristics, and hybrid algorithms, can be explored in different domains, such as transportation, healthcare, multi-objective optimization, data classification, etc., to improve the applicability of the proposed mechanism. Additionally, we intend to consider the scenario in which any dishonest or non-responsive nodes (i.e., the EVs and CS) involved in the network are observed and prevented from disrupting the scheduling through any malicious attack.