1 Introduction

In recent years, the advancement in the computing paradigm and Internet of things (IoT) has inspired the industrial and research communities to encapsulate these technologies into conventional networks, such as mobile ad-hoc networks (MANETs), vehicular ad-hoc networks (VANETs), and flying ad-hoc networks (FANETs) [1, 2]. This advancement leads to ubiquitous applications/services with the help of cloud infrastructure through the Internet. However, sensitive applications, such as real-time, time-critical, and delay-sensitive (e.g., smart transportation, navigation, and augmented reality assistant) demand low latency, high bandwidth, and low congestion [3,4,5,6,7]. The end-to-end delay is significant between the end-user and the cloud server, which affects the applications. As a result, these services need to be available close to the end-user in order to meet the demand. This lead the researchers to introduce a new computing paradigm, called fog computing (FC) [3, 8, 9]. FC is a hierarchical distributed architecture, which acts as a middle layer between the end-user and the cloud server. It extends the cloud services to the edge and closer proximity to the end-user [10]. As a result, it fulfills the demand of the sensitive applications, and it complements the cloud [4]. The FC infrastructure consists of a set of devices, namely routers, gateways, switches, and other electronic devices, called fog nodes (FNs). These devices are capable of computing, storing, and transmitting/receiving data with other devices and the cloud.

The evolution of the IoT paradigm and vehicular networks enables smart vehicles to establish a connection with FNs or any devices to improve traffic efficiency [3]. The delay-sensitive and real-time applications can be provided in cognitive vehicular networks for ensuring safety, and remarkable convenience in transportation [11, 12]. However, these applications pose significant challenges to existing VANETs regarding high latency, bandwidth consumption, and storage capacity. The fog-empowered vehicular ad-hoc networks (FEVANETs) can address these challenges by integrating fog computing into VANETs [9, 13, 14]. The architecture of FEVANETs is shown in Fig. 1, which comprises roadside units (RSUs) and high power nodes (HPNs). The RSUs/HPNs are roadside infrastructure and are considered FNs. They are equipped with computation, storage, wide-area coverage, and communicating data with the cloud and other FNs. More specifically, the HPNs provide high computation, storage, and coverage area capacities, hence called powerful FNs. The HPNs are supervised by a central unit, which acts as an interface between the HPNs and the cloud servers through the Internet. Due to the limited resource constraints of FNs, efficient resource management is a crucial criterion for improving the service capability of FEVANETs [15]. Alternatively, the efficient resource utilization to maximize service capability, which indicates the network availability for serving vehicles to satisfy their desired requirements, is the primary challenge in FEVANETs [16]. The smart vehicles can establish a connection with FNs in FEVANETs using device association techniques, such as signal-aware, content-aware, and capacity-aware techniques. The signal-aware technique establishes a connection between FNs and vehicles depending on good signal-to-interference-plus-noise ratio (SINR) quality [17]. The content-aware technique establishes a connection between FNs and vehicles based on user favorite contents [18] and the capacity-aware technique establishes a connection using resource availability of FNs [19].

As the vehicles connecting to the vehicular network increase, these device association techniques lead to a load imbalance among FNs, which impacts the severe reduction in the network service capability and resource utilization efficiency [20]. To resolve this problem, we propose dynamic resource management (DRM) algorithm for efficient resource allocation among FNs and migrating services between pairs of FNs to improve their service capability and resource utilization efficiency. The set of smart vehicles reaching FEVANET can establish a connection with single FN or more than two FNs. In this work, we consider the set of vehicles in overlapped coverage regions of two or more FNs and served by those FNs. The resource blocks (RBs) of a set of vehicles in the overlapped coverage region are used for service migration between pairs of FNs to minimize occupied RBs and maximize the service capability of FEVANETs. A resource block is the smallest time-frequency unit in an orthogonal frequency division multiple access (OFDMA) system. A smart vehicle must be assigned with RBs before data transmission [21]. We simulate the proposed algorithm by taking 10 to 50 FNs and 300 to 2100 vehicles at an arrival rate of 10 vehicles/s. We compare the simulation results with dynamic resource orchestration (DRO) [22], signal-aware (SA) [17], DRO + SA and the basic algorithm, called random order (RO), in terms of service capability, serviceability, availability, throughput, and resource utilization efficiency. Note that the RO algorithm selects FNs arbitrarily and randomly migrates the RBs of vehicles. The set of smart vehicles that request services from FNs is termed vehicles in the rest of the content of this paper. In summary, the key contributions of this work are as follows.

  1. 1.

    We consider allocating RBs to newly arrived vehicles by migrating RBs between pairs of FNs without affecting their services. The RBs of vehicles are migrated to minimize overall allocated RBs.

  2. 2.

    The optimal RBs migration problem in FEVANETs is formulated into integer linear programming (ILP) by considering the variables that impact FNs’ resource constraints and the network’s service capability.

  3. 3.

    We propose a polynomial-time DRM algorithm for optimal migration of RBs between pairs of FNs to minimize occupied RBs among FNs and maximize the service capability and resource utilization efficiency of the network by migrating RBs of a set of vehicles.

  4. 4.

    We present extensive simulations to show that the DRM algorithm can achieve better performance than the four existing algorithms in terms of service capability, serviceability, availability, throughput, and resource utilization efficiency of the network.

The remainder of this paper is structured as follows. Section 2 of this paper describes the related work of the discussed problem. The problem statement is presented in Section 3. The DRM algorithm and the optimization of the problem are explained in Section 4. Section 5 presents the simulation outcomes of the DRM algorithm and its performance over other algorithms. The conclusion of this paper is presented in Section 6.

Fig. 1
figure 1

Architecture of FEVANETs

Full size image

2 Related work

The comparative study of computing techniques to disseminate, store and compute data for delay-sensitive applications in order to meet their requirements is given in [23]. However, the existing algorithms for resource scheduling can be classified based on their objectives, such as the service capability, throughput, spectral efficiency, and serviceability. The existing algorithms for resource scheduling can be classified based on their objectives, such as the service capability, throughput, spectral efficiency, and serviceability.

2.1 Quality of Service (QoS)

He et al. [24] have proposed a resource scheduling scheme in vehicular networks to facilitate video streaming using the semi-Markov decision process (SMDP). They have provided a better QoS for the user by increasing the bandwidth usage of the entire network. However, it fails to manage fair resource scheduling among FNs.The device association techniques such as signal-aware [17], content-aware[18], and capacity-aware[19] for various traditional networks provide better serviceability and network utilization efficiency. However, they fail to manage resource scheduling among FNs, leading to an unfair load among FNs, reducing network service capability and resource utilization efficiency. Several researchers have worked on load instability problems in networks to achieve optimal resource allocation in recent years [25,26,27]. More specifically, load instability problems happen when a large number of vehicles arrive in the network at the same time. Qafzezi et al. [28] have proposed fuzzy-based systems for resource management for making a decision on processing applications on the fog layer or cloud layer in software-defined networking supported VANETs. Their network resource management improves the QoS of the network.

2.2 Throughput

A joint downlink user association technique proposed by Liu et al. [17] in two-tier heterogeneous networks uses the resource partitioning and graph coloring approach to mitigate the co-tier interference among the nodes. This approach achieves better user throughput but cannot improve the serviceability of the network and may cause load imbalance among nodes which affects services of newly arrived vehicles. Vu et al. [22] have proposed a DRO scheme for fog-enabled connected vehicle networks (FCVNs) that manages resource allocation by migrating services between pairs of FNs. This scheme uses a solution returned by the maximum weight matching problem to find optimal pairs of FNs. The service migration using DRO is carried out to achieve better service capability, serviceability, resource utilization efficiency, and throughput. The DRO scheme reduces service capability and serviceability as there is an increase in the number of vehicles arriving at the network. However, when it is augmented with the SA algorithm, it improves the service capability and serviceability of the network. Vu et al. [29] have proposed a downlink sum-rate optimization (DSRO) scheme in F-RANs provides the resource allocation among RRHs using the Hungarian method. It upgrades the network’s performance in terms of serviceability and throughput, but they do not consider the service capability and availability. Ge et al. [30] have proposed a joint user association and user scheduling for load balancing by addressing a network-wide utility maximization problem in the heterogeneous networks over the downlink. They approximate the nonconvex throughput obtained with user scheduling to a concave function, and a distributed convex optimization approach is used to implement user association and user scheduling.

2.3 Spectral efficiency

The data rate optimization can be obtained by the methods mentioned in the above literature. However, these methods cannot provide resource efficiency due to the non-exact solution. Several research studies have been conducted on spectral efficiency for the evaluation of the network. These studies have used optimization techniques [31] and game theoretical models [32] to improve the spectral efficiency [33].

2.4 Serviceability

Dao et al. [34] have presented an ARB scheme using hungarian method for maximizing network serviceability in fog radio access networks (F-RANs). The network serviceability is obtained by migrating services between remote radio heads (RRHs). However, they do not consider the performance metrics like resource utilization, which decreases the network performance.

In the above literature, the existing algorithms maximize the performance metrics, such as service capability, serviceability, availability, and throughput, while satisfying the vehicle requirements in the FNs coverage area. However, this work differs from the existing works in the following aspects (Table 1).

  1. 1.

    The existing algorithms migrate the RBs of vehicles between pairs of FNs without considering the load on FN. On the contrary, the proposed algorithm migrates the RBs of vehicles between pairs of FNs, such that the load on FN is minimum.

  2. 2.

    The proposed algorithm can allocate RBs for newly arrived vehicles by reducing the allocated RBs of already arrived vehicles without affecting their services in comparison to the existing algorithms. Moreover, the proposed algorithm considers five different performance metrics.

Table 1 A comparative analysis
Full size table

3 Problem statement

Consider a FEVANETs in a city area A in which \(\mathcal {F}\) number of FNs are deployed. Each FN \(F_{i}\), 1 \(\le\) i \(\le\) \(\mathcal {F}\), has a communication range R and it can overlap with the communication range of neighboring FN \(F_{j}\), 1 \(\le\) j \(\le\) \(\mathcal {F}\), i \(\ne\) j. A FN \(F_{i}\) provides services to the set of vehicles \(\mathcal {P}_{t}(i)\) reaching its communication range at timeslot t. Note that the Poisson distribution is used for the arrival rate (departure rate) of vehicles to (from) the network with mean value \(\lambda\) (or \(\mu\)). Table 2 summarizes the different notations and their definitions used in this paper.

Table 2 Notations and their descriptions
Full size table

Let \(rb_{i}^{k}\) be the total number of RBs required for \(k^{th}\) vehicle with data rate \(d^{k}\) from the \(i^{th}\) FN, when \(k^{th}\) vehicle is present in the coverage area of \(i^{th}\) FN. It can be obtained as follows [22, 35].

$$\begin{aligned} rb_{i}^{k} = \left\lceil {\frac{1}{B \times \log _2(1+S_{i}^{k})} \times d^{k}}\right\rceil \end{aligned}$$
(1)

where B denotes the bandwidth that is used by one RB in a period of 1 ms, which is equivalent to 180 KHz [36], \(rb_{i}^{k}\) \(\in\) \(\mathbb {N}\), and \(S_{i}^{k}\) is the signal strength between the \(i^{th}\) FN and \(k^{th}\) vehicle on the data channel [37].

Let \(\mathcal {P}^{in}_{t}(i)\) be a set of vehicles arriving to \(i^{th}\) FN at timeslot t and \(\mathcal {P}^{out}_{t}(i)\) be a set of vehicles departing from \(i^{th}\) FN at timeslot t, after successful completion of their tasks. In this situation, the mean departure rate of the vehicles from the network (\(\mu\)) is obtained as follows [22].

$$\begin{aligned} \mu = \mathbb {E}\left[ \sum _{i=0}^\mathcal {F} \Vert \mathcal {P}^{out}_{t}(i)\Vert \right] \end{aligned}$$
(2)

At timeslot t, the number of vehicles served by FNs is denoted by \(\mathcal {P}_{t}(i)\) and can be defined as follows [22].

$$\begin{aligned} \mathcal {P}_{t}(i) = \mathcal {P}_{t-1}(i) \cup \mathcal {P}^{in}_{t}(i)\setminus \mathcal {P}^{out}_{t}(i) \end{aligned}$$
(3)

In a particular scenario, the number of vehicles getting service is limited due to resource constraints. In this circumstance, the remaining RBs, \(Ar_{t}(i)\) of \(i^{th}\) FN, after assigning the RBs to vehicles in \(\mathcal {P}_{t}(i)\), can be obtained as follows [22].

$$\begin{aligned} Ar_{t}(i) = Q_{i} - C_{t}(i) = Q_{i} - \sum _{k=0}^{\Vert \mathcal {P}_{t}(i)\Vert }rb_{i}^{k} \end{aligned}$$
(4)

where \(C_{t}(i)\) and \(Q_{i}\) are the occupied RBs and capacity of the \(i^{th}\) FN at time instant t, respectively. The service capability of \(i^{th}\) FN at timeslot t is given as follows [22].

$$\begin{aligned} Sc_{t}(i) = Ar_{t}(i) \times \frac{1}{Q_{i}} \end{aligned}$$
(5)

In the similar fashion, the network service capability at timeslot t can be determined as follows [22].

$$\begin{aligned} Sc_{t} = \sum _{i=0}^\mathcal {F}Ar_{t}(i) \times \frac{1}{\sum _{i=0}^\mathcal {F}Q_{i}} \end{aligned}$$
(6)

The deluge of vehicles arriving at the network can connect to preferred FNs based on the signal strength and favorite contents. The number of vehicles connecting to these FNs increase rapidly over time. It can exhaust the capacity of FNs and become impotent to provide the services because of limited resource constraints. As a result, the new incoming vehicles connect to the FNs that own inadequate resources. In order to provide better services, the services of the vehicles are migrated between pairs of FNs without increasing the number of RBs and balancing the load among the FNs. Alternatively, FNs are required to assign a large number of RBs to satisfy these vehicles’ required latency and data rate. Otherwise, it leads to a shrink in the network service capability and resource utilization efficiency.

In this paper, we consider allocating RBs to newly arrived vehicles among the FNs without increasing the number of RBs, such that the following objectives are fulfilled.

  1. 1.

    Network service capability is maximized.

  2. 2.

    Network serviceability is maximized.

  3. 3.

    Network availability is maximized.

  4. 4.

    Network throughput is maximized.

  5. 5.

    Resource utilization efficiency is maximized.

4 Dynamic resource management algorithm

The proposed algorithm, DRM, is a resource management algorithm for maximizing service capability in FEVANETs. The objective of this algorithm is to maximize the service capability, serviceability, availability, throughput, and resource utilization efficiency of the networks without increasing the number of RBs of the FNs. The basic idea of the proposed algorithm is as follows. Firstly, DRM identifies the vehicles in the overlapped region of the pairs of FNs and determines the number of RBs allocated to those vehicles from the FNs. Then DRM migrates the RBs of vehicles between the pairs of FNs in order to reduce the occupied RBs on the FNs. It is noteworthy to mention that the reduction of RBs leads to an increase in service capability, serviceability, availability, throughput, and resource utilization efficiency of the networks. The detailed description is discussed as follows.

At timeslot t, assume that the number of vehicles \(\Vert \mathcal {P}_{t}(i)\Vert\) connecting to preferred FNs increases, for which the resources of the FNs are tends to exhaust. Next, consider the vehicles present in a coverage area of two or more FNs and served by those FNs. Let \(\mathcal {P}_t(ij)\) be a set of vehicles in an overlapped coverage area of \(i^{th}\) FN and \(j^{th}\) FN at timeslot t. The set of vehicles, \(\mathcal {P}_t(ij)\), between pairs of FNs i and j, 1\(\le\) i, j \(\le\) \(\mathcal {F}\), i \(\ne\) j can be obtained as follows.

$$\begin{aligned} \mathcal {P}_t(ij) = \mathcal {P}_t(i) \cap \mathcal {P}_t(j) \end{aligned}$$
(7)

The \(\mathcal {P}_t(ij)\) represents vehicles for which RBs can be migrated between pairs of FNs. Let \(\mathbb {R}\) be the number of overlapped coverage areas in FEVANETs. The vehicles’ RB migration between pairs of FNs takes place only if there exists a minimum of one vehicle in the overlapped coverage area (i, j) \(\in\) \(\mathbb {R}\) and is served by those pairs of FNs. Mathematically, \(\mathcal {P}_t(ij)\) \(\ne\) \(\emptyset\).

Let \(p_{t}^{*}(ij)\) be an optimal set of vehicles whose RBs can migrate from \(i^{th}\) FN to \(j^{th}\) FN and its converse \(p_{t}^{*}(ji)\) be an optimal set of vehicles whose RBs can migrate from \(j^{th}\) FN to \(i^{th}\) FN. Let \(\mathcal {P}_{t}^{*}(i)\) and \(\mathcal {P}_{t}^{*}(j)\) be an optimal set of vehicles served by \(i^{th}\) and \(j^{th}\) FNs after optimal migration of RBs is performed. They can be derived as follows.

$$\begin{aligned} \begin{aligned} \mathcal {P}_t^*(i) = (\mathcal {P}_t(i) \setminus {p}_t^*(ij)) \cup p_t^*(ji) \end{aligned} \end{aligned}$$
(8)
$$\begin{aligned} \begin{aligned} \mathcal {P}_t^*(j) = (\mathcal {P}_t(j) \setminus {p}_t^*(ji)) \cup p_t^*(ij) \end{aligned} \end{aligned}$$
(9)

The optimal RB migration among FNs in resource-constrained FEVANETs can be formulated as an ILP problem, which is discussed in Section 4.1.

4.1 ILP formulation for optimal RB migration

We define a boolean variable \(x_{ij}^k\) to denote a vehicle k \(\in\) \(\mathcal {P}_{t}(ij)\) chosen for migrating RBs between \(i^{th}\) and \(j^{th}\) FNs, \(\forall (i,j)\) \(\in\) \(\mathbb {R}\).

$$\begin{aligned} x_{ij}^k = \left\{ \begin{array}{ll} 1, &{} \quad \text {If }k^{th}\; \text {vehicle is chosen for migrating RBs} \\ &{} \quad \text {between pairs of FNs}\;i\;\text {and}\;j \\ 0, &{} \quad \text {Otherwise} \end{array} \right. \end{aligned}$$

To maximize the network resource utilization efficiency, the vehicles in the overlapped coverage area (i, j), \(\forall\) \((i,j)\) \(\in\) \(\mathbb {R}\), are considered for optimal migration of RBs between pairs of FNs i and j, such that the overall occupied RBs by these vehicles is minimized. The optimal service migration among pairs of FNs i and j can be formulated as follows.

$$\begin{aligned} min \sum _{\forall (i,j)\in \mathbb {R}} \left( \sum _{\forall k \in \mathcal {P}_{t}(ij)} x_{ij}^k r_{ij}^{k} \right) \end{aligned}$$
(10)

subjected to

$$\begin{aligned} \sum _{\forall k \in \mathcal {P}_{t}(ij)} x_{ij}^k r_{ij}^{k} \le \delta _{ij}, \forall (i,j) \in \mathbb {R} \end{aligned}$$
(11)
$$\begin{aligned} \sum _{(i,j)\in \mathbb {R}}x_{ij}^k \le \Vert \mathcal {P}_t(ij)\Vert , \forall k \in \mathcal {P}_{t}(ij), 1 \le i,j \le \mathcal {F}, i \ne j \end{aligned}$$
(12)
$$\begin{aligned} \sum _{(i,j)\in \mathbb {R}}x_{ij}^k \le 1, \forall (i,j) \in \mathbb {R} \end{aligned}$$
(13)
$$\begin{aligned} x_{ij}^k \in \{0,1\}, \forall k \in \mathcal {P}_{t}(ij), \forall (i,j) \in \mathbb {R} \end{aligned}$$
(14)

where \(r_{ij}^{k}\) and \(\delta _{ij}\) are given by

$$\begin{aligned} r_{ij}^{k} = \left\{ \begin{array}{ll} rb_{i}^{k}, &{} \quad \text {if RBs of vehicle }k\; \text {are migrated from }j^{th} \\ &{} \quad \text {FN to }i^{th}\; \text {FN} \\ rb_{j}^{k}, &{} \quad \text {if RBs of vehicle }k\; \text {are migrated from }i^{th} \\ &{} \quad \text {FN to }j^{th}\; \text {FN} \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} \delta _{ij} = {\left\{ \begin{array}{ll} Q_{i} = Ar_{t}(i) + \sum _{\forall k \in \mathcal {P}_{t}(ij)} (rb_{i}^{k}) \\ Q_{j} = Ar_{t}(j) + \sum _{\forall k \in \mathcal {P}_{t}(ij)} (rb_{j}^{k}) \end{array}\right. } \end{aligned}$$
(15)

The constraint (given in Eq. 11) guarantees that the RBs occupied by the vehicles, when optimal migration is administered, do not surpass the capacity of the destination FN. The constraint (shown in Eq. 12) ensures that the at most \(\Vert \mathcal {P}_{t}(ij)\Vert\) vehicles in a region (i, j) \(\in\) \(\mathbb {R}\) can be chosen for migrating services between \(i^{th}\) and \(j^{th}\) FNs. The constraints in Eqs. (13) and (14) ensure a vehicle from all overlapped coverage regions is chosen only once for RB migration. By solving objective function (Eq. 10), we get the optimal set \(p_{t}^{*}(ij)\), and \(p_{t}^{*}(ji)\) of vehicles (from Eqs. 8 and 9) for the optimal service migration between the pairs of FNs i and j.

Theorem 1

The ILP optimization problem is NP-hard.

Proof

We use a well-known NP-hard problem, called seminar assignment problem (SAP), which is a special case of general assignment problem (GAP) [38] and reduce it to our ILP optimization problem in order to prove this theorem. Consider an instance of SAP having a number of n students and m seminar halls. Each seminar hall r \(\in\) m has a capacity of \(B_r\) \(\in\) \(\mathbb {N}\). The assignment of student s \(\in\) n to a seminar hall r has a profit \(p_{rs}\). The aim is to assign a subset of students to seminar halls, such that the number of students in each seminar hall r should be at most \(B_r\), and the total profit is maximized.

The instance of SAP is reduced to an instance of our ILP problem by mapping (one-to-one) the seminar halls to FNs, the students to the set of vehicles, and \(r^{th}\) seminar hall capacity \(B_r\) to \(i^{th}\) FN capacity (given as \(Q_i\)). However, the profit of assigning \(s^{th}\) student to \(r^{th}\) seminar hall is negated in the mapping of the allocated RBs of \(i^{th}\) FN to \(k^{th}\) vehicle, k \(\in\) \(\mathcal {P}_{t}(ij)\). Here, we assume that there exists a set of vehicles to do RB migration. This reduction can be carried out in polynomial time. Therefore, the instance of SAP has an assignment if and only if the instance of ILP problem has an assignment. This establishes the NP-hardness of the ILP optimization problem.

Theorem 2

ILP optimization problem can be optimally solved in polynomial time when \(\mathcal {F}\) is fixed.

Proof

From Theorem 1, it is clear that the ILP optimization problem is NP-hard. Now consider a graph model, G(V, E), representing the FEVANETs with \(\mathcal {F}\) FNs (Fig. 2a), in which set of vertices V represents the FNs and E is the set of edges in G. There exists an edge between \(i^{th}\) FN and \(j^{th}\) FN if and only if there exists one or more vehicle(s) in the overlapped coverage region and connected to those FNs as shown in Fig. 2b. As we know, this graph model can be solved in polynomial time when V is fixed [38]. Therefore, the ILP problem can also be solved in polynomial time when \(\mathcal {F}\) is fixed.

4.2 Algorithm description

Algorithm 1 presents the proposed algorithm, DRM, for the optimal RB migration in FEVANETs. The graph model G(V, E) and \(\mathcal {F}\) are given as input to Algorithm 1 and generates an optimal set of vehicles \(\mathcal {P}_t\) for RBs migration. Upon the arrival of vehicles in the overlapped coverage area (i, j), \(\forall\) (i, j) \(\in\) \(\mathbb {R}\) at timeslot t, it finds union of all vehicles \(\mathcal {P}_t\), which is present in the overlapped coverage area of each neighbor of \(i^{th}\) FN, say, \(j^{th}\) FN, 1 \(\le\) i, j \(\le\) \(\mathcal {F}\), i \(\ne\) j. Also, it finds the set of the occupied capacity of each neighboring FN, C (Step 5 to Step 10). The vehicles present in the set \(\mathcal {P}_t\) are served by both \(i^{th}\) and \(j^{th}\) FNs. For optimal RB migration, it invokes the MigrateRBs (Procedure 1) with \(\mathcal {P}_t\) and C for FN i in Step 11 of Algorithm 1.

figure c
figure d

For a given set of vehicles \(\mathcal {P}_t\) and the set of occupied capacities C, the MigrateRBs in Procedure 1 finds the vehicle \(k_{min}\) with minimum RBs and the corresponding \(f^{th}\) FN, such that the load on \(f^{th}\) FN is minimum in Step 2. Procedure 1 invokes FindMinVehicle, given in Procedure 2, to find the vehicle \(k_{min}\) and the corresponding \(f^{th}\) FN by taking \(\mathcal {P}_t\) and C as input. In Procedure 1, the RBs of vehicle \(k_{min}\) are migrated from \(i^{th}\) FN to \(f^{th}\) FN only if the remaining RBs of \(f^{th}\) FN satisfy the desired requirements of vehicle \(k_{min}\) and the vehicle \(k_{min}\) not served by FN f in Steps 3 and 4. Then it updates the occupied capacity and remaining RBs of \(i^{th}\) and \(f^{th}\) FNs in Step 5. Otherwise, it skips the vehicle \(k_{min}\) from the process of RB migration in Step 6. The vehicle \(k_{min}\) is removed from the set \(\mathcal {P}_t\) in Step 9. This process is repeated from Step 1 to Step 9 until the set \(\mathcal {P}_t\) becomes empty.

figure e
Fig. 2
figure 2

An example for RB migration using the proposed algorithm

Full size image
Fig. 3
figure 3

An optimal RB migration using DRM scheme for FEVANET given in Fig. 2a. a Occupied RBs of FNs before migration. b Occupied RBs of FNs after migration using DRM

Full size image

4.3 An illustration

Figure 2 shows as an example of FEVANET for optimal RB migration between FNs using the proposed algorithm, DRM, to reduce the occupied RBs in the group of FNs. This figure illustrates a scenario of FEVANET with four FNs and ten vehicles. The vehicles that FNs currently serve are indicated by solid orange lines, whereas dashed orange lines indicate the vehicles whose services can be migrated to FNs. The number of RBs required from FNs to satisfy desired requirements of vehicles is represented by numbers beside the orange lines. Fig. 2b is a graph representation of FEVANET, corresponding to Fig. 2a in which vertices represent FNs and an edge between vertices exists if vehicles are located in an overlapped coverage area of two FNs.

Firstly, the set of vehicles is connected to each FN given by \(FN_1=\{V_1, V_2, V_4, V_7\}\), \(FN_2=\{V_3, V_4, V_5, V_8\}\), \(FN_3=\{V_3, V_6, V_9\}\) and \(FN_4=\{V_1, V_2, V_5, V_6, V_{10}\}\). The union of vehicles in overlapped coverage region of two or more FNs is given by \({\{V_1, V_2, V_3, V_4, V_5, V_6\}}\). The current occupied RBs of each FN for vehicles in the overlapped coverage region are shown in Fig. 3a (i.e., before RB migration). The set of vehicles connected to each FN is given as input to Algorithm 1 for optimal RB migration among FNs.

When \(FN_{1}\) is chosen (i.e., iteration i = 1 of Algorithm 1), the set of all vehicles, which are in the overlapped coverage area of \(FN_{1}\) and its neighbor FNs, is determined. They are \(\mathcal {P}_t = \{V_1, V_2, V_4\}\). Here, the neighboring FN is \(FN_{j}\) = \(FN_{2}\) and \(\mathcal {P}_{t}(ij)\) = \(\mathcal {P}_t\) = \(\{V_4\}\). Similarly, when \(FN_{j}\) = \(FN_{4}\), \(\mathcal {P}_{t}(ij)\) = {\(V_1\), \(V_2\)} and \(\mathcal {P}_t\) = {\(V_1\), \(V_2\), \(V_4\)}. The migration algorithm MigrateRBs defined in Procedure 1 is invoked with the set \(\mathcal {P}_{t}\) and C that consists of a set of vehicles for RB migration and occupied capacities of neighboring FNs, respectively. The vehicle \(k_{min} = V_2\) \(\in\) \(\mathcal {P}_t\) and corresponding \(FN_{j}\) = \(FN_{4}\) are chosen for RB migration from \(FN_{1}\), since vehicle \(V_2\) is required minimum RBs (i.e., \(rb_{j}^{k_{min}}\) = 209) from \(FN_{4}\) using FindMinVehicle. After successful migration, the occupied RBs of \(FN_{4}\) are updated to 209, and vehicle \(V_2\) is removed from \(\mathcal {P}_t\). Subsequently, vehicles \(V_4\) and \(V_1\) are chosen from \(\mathcal {P}_t\) for RB migration. Note that these vehicles are selected based on the minimum number of RBs. After the completion of iteration i = 1, the occupied RBs of each FN are shown in Fig. 3b. In the next iteration (i.e., iteration i = 2 of Algorithm 1), the union of all vehicles in overlapped coverage region of \(FN_{2}\) and its neighbor FNs is \(\mathcal {P}_t = \{V_3, V_5\}\).

After the iteration i = 2, the occupied RBs of FNs \(FN_{1}\), \(FN_{2}\), \(FN_{3}\), and \(FN_{4}\) are 292, 223, 288, and 409, respectively. In the iteration i = 3, the \(FN_3\) is chosen and \(\mathcal {P}_t = \{V_6\}\) is obtained. For migrating RBs of vehicle \(V_6\), the load on \(FN_{3}\) and \(FN_{4}\) is 662 (i.e., 288 + 374) and 532 (i.e., 409 + 123), respectively. Since \(FN_{4}\) contains minimum load, the RBs are migrated from \(FN_{3}\) to \(FN_{4}\). The overall occupied RBs are 2417 before RB migration and RBs are reduced to 1335 after the migration. Therefore, the percentage of reduction is 44.76% (i.e., \(\frac{(2417 - 1335)}{2417}\)). Note that this reduction greatly improves the service capability, serviceability, availability, throughput, and resource utilization efficiency of the network. On the other hand, the percentage of reduction is 21.64% in the DRO [22], 43.67% in the SA [17] and 16.75% in the RO. This clearly shows the superior performance of DRM over the existing algorithms.

Theorem 3

The number of vehicles in the overlapped coverage region of two or more FNs for RB migration from \(i^{th}\) FN to each neighboring \(FN_{j}\) (1 \(\le\) j \(\le\) \(\mathcal {F}\), \(i \ne j\)) is at most \(\Vert \mathcal {P}_t\Vert\).

Proof

The \(j^{th}\) FN allocates the required RBs, \(rb_{j}^{k}\), when migrating service of a vehicle k from \(i^{th}\) FN if and only if the \(j^{th}\) FN has sufficient available RBs (i.e., \(Ar_{t}(j)\) \(\ge\) \(rb_{j}^{k}\)). Therefore, the total number of vehicles in the overlapped coverage region for RB migration from \(i^{th}\) FN to all the neighboring FNs is at most \(\Vert \mathcal {P}_t\Vert\). Note that the set \(\mathcal {P}_t\) is the union of the set of vehicles in the overlapped coverage region of each \(j^{th}\) FN (1 \(\le\) j \(\le\) \(\mathcal {F}\), \(i \ne j\)), which is neighbor to \(i^{th}\) FN (i.e., \(\mathcal {P}_t\) \(=\) \(\mathcal {P}_{t}\) \(\cup\) \(\mathcal {P}_{t}(ij)\)).

Theorem 4

The proposed algorithm DRM migrates the RBs of vehicle \(k_{min}\) \(\in\) \(\mathcal {P}_t\) with minimum load \(rb_{f}^{k_{min}}\) to \(f^{th}\) FN, such that the load on \(f^{th}\) FN is minimum.

Proof

Consider the FEVANET example with \(\mathcal {F}\) = 4 as shown in Fig. 2a. When FindMinVehicle is invoked in Procedure 1 with \(\mathcal {P}_t\) = {\(V_{3}\), \(V_{5}\)} for \(FN_{2}\) (i.e., in iteration i =2), suppose vehicle \(V_{3}\) is selected. Then the load on \(FN_{2}\) and \(FN_{3}\) is 551 (i.e., 223 + 328) and 228 (i.e., 0 + 228), respectively. When the vehicle \(V_{5}\) is selected, the load on \(FN_{2}\) and \(FN_{4}\) is 501 (i.e., 223 + 278) and 409 (i.e., 209 + 200), respectively. The proposed algorithm DRM using FindMinVehicle selects vehicle \(V_{3}\) and the corresponding \(FN_{3}\) instead of vehicle \(V_{5}\) with RBs 200. Since the load on \(FN_{3}\) is minimum, the RBs of vehicle \(V_{3}\) are migrated from \(FN_{2}\) to \(FN_{3}\). Therefore, it is proved that the proposed algorithm migrates the vehicle’s RBs to the corresponding FN, such that the load on FN is minimum.

4.4 Complexity analysis

The proposed algorithm DRM is presented in Algorithm 1, which invokes MigrateRBs (Procedure 1) with the occupied capacities and a set of vehicles in the overlapped coverage area (i, j), \(\forall\) \((i,j)\) \(\in\) \(\mathbb {R}\) of pairs of FNs as input. In Procedure 1, Step 2 (i.e., Procedure 2) takes \(\mathcal {O}(\Vert \mathcal {P}_t\Vert )\) time in worst case as it iterates for \(\mathcal {O}(\Vert \mathcal {P}_t\Vert )\) times. Steps 3-9 take constant time. The while loop iterates for \(\mathcal {O}(\Vert \mathcal {P}_t\Vert )\) times. Therefore, the overall running time of Procedure 1 is \(\mathcal {O}(\Vert \mathcal {P}_t\Vert ^2)\) in the worst case.

In the Algorithm 1, for a given \(FN_{i}\), Step 5 finds a set of vehicles in the overlapped coverage regions of each neighbor, say \(FN_{j}\), of \(i^{th}\) FN, 1 \(\le\) i, j \(\le\) \(\mathcal {F}\), \(i \ne j\). It takes \(\mathcal {O}(\mathcal {F})\) time in the worst case. The outer for loop in Algorithm 1 takes \(\mathcal {O}(\mathcal {F})\) time. Therefore, the worst case time complexity of Algorithm 1 is given as \(\mathcal {O}(\mathcal {F}(\mathcal {F} + \Vert \mathcal {P}_t\Vert ^2))\) \(\approx\) \(\mathcal {O}(\mathcal {F}^2 + \mathcal {F} (\Vert \mathcal {P}_t\Vert ^2))\).

5 Performance evaluation

The performance of the proposed algorithm is evaluated in terms of service capability, serviceability, availability, throughput, and resource utilization efficiency. The simulated results were compared with existing service migration algorithms, such as DRO [22], SA [17], DRO + SA and RO, in which FNs and vehicles are selected randomly.

5.1 Simulation setup

The simulations were carried out by creating a virtual environment using Python (version 3.8) on PyCharm integrated development environment (IDE) 2020.1.3. This IDE was running on an Intel(R) Xeon(R) Gold 622R CPU @ 2.90GHz 2.89 GHz processor, 64-bit operating system and 64.0 GB installed RAM. The simulation environment, including network traffic details, was set up based on the setup given in [17, 22]. We evaluate the execution of the proposed algorithm DRM in a network model with [10 \(\sim\) 50] FNs deployed in a region size of [1000 \(\times\) 1000] square meters as shown in Fig. 4. This road map shows an area of a city in which the deployment of FNs ranges from 10 to 50. These FNs are deployed in such a way that their coverage area overlaps with one or more FNs. We consider the mobility patterns of vehicles that arrived and/or departed to/from the network. They follow the Poisson distribution in each time slot. However, the mean arrival rate (\(\lambda\)) and mean departure rates (\(\mu\)) are 10 vehicles/s and 5 vehicles/s, respectively. It is noteworthy to mention that the velocity of vehicles is not explicitly shown as it is modelled in the form of \(\lambda\) and \(\mu\). When FNs cannot allocate required RBs, vehicles are served with minimum data rates ranging from 0.5 to 2.0 Mbps. As the mean arrival rate exceeds the mean departure rate, the number of vehicles available at the network increases in each time slot. The simulation results show the impact of the increase in the number of vehicles on the service capability, serviceability, availability and throughput of the network. The average results were obtained by conducting the Monte-Carlo simulations up to one hundred five times (i.e., 15 times for each result) with 210 timeslots using queuing model. We use IEEE 802.11p as our media access control (MAC) protocol to enable wireless access in FEVANETs. The Nakagami model is used to model the data/signal propagation. This model is considered as the most realistic model. The different parameters considered for the simulations with their values are given in Table 3.

Fig. 4
figure 4

A road map of [1000 \(\times\) 1000] square meters

Full size image
Table 3 Parameters and their values for simulations
Full size table

5.2 Service capability

Service capability is the ratio between the remaining resources and the total number of resources in a network [22]. Fig. 5 shows the network service capability by the proposed algorithm, DRM, and other existing migration algorithms, such as DRO, SA, and RO. It is observed that the FNs possess sufficient RBs to satisfy requests of the vehicles during initial timeslots. Hence, all the algorithms produce better service capability in the initial duration. However, as the deluge arrival of vehicles to the network increases, the network service capability reduces due to the reduction in the available RBs of FNs. The DRO algorithm uses the solution of maximum weight matching, which is the set of edges without common vertices and reduces the RBs of those vehicles in the set of edges returned by the matching solution. Therefore, there is a severe reduction in the service capability using the DRO algorithm.

The SA and RO algorithms enhance the service capability of the network as the number of vehicles arriving at the network increases. The SA algorithm improves the service capability using the graph colouring solution up to 97.80% and 24.03% when compared to DRO and RO, respectively. However, the proposed algorithm outperforms the service capability when compared to SA, RO and DRO+SA combined. The proposed algorithm enhances the service capability by 21.78%, 51.05% and 19.65% when compared to SA, RO and DRO+SA, respectively. The rationality behind this is that it is greedy to select a vehicle with minimum RBs.

Fig. 5
figure 5

Pictorial comparison of network service capability for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image

5.3 Serviceability

The network serviceability is the percentage of vehicles getting served with desired requirements in a network [34]. The serviceability of the network by the proposed algorithm and other migration algorithms is shown in Fig. 6. The simulation results show that all the algorithms behave similarly during the initial timeslot, as FNs contain enough RBs. However, the serviceability of the network reduces as the deluge arrival of vehicles at the network causes the FNs to be impotent in providing services to arrived vehicles. Therefore, there is a reduction in the serviceability of the network. The SA and the DRO augmented by SA (i.e., DRO+SA) behave similarly as vehicles arriving at the network increase. The SA and RO algorithm improves the serviceability of the network. The SA algorithm improves the serviceability by 52.42% and 13.03% when compared to DRO and RO algorithms, respectively. However, the proposed algorithm is greedy in selecting vehicles with minimum RBs for migrating RBs between pairs of FNs. Furthermore, it maximizes the RBs reduction of vehicles in the overlapped coverage regions to accommodate newly arrived vehicles with their desired data rates. Therefore, the proposed algorithm enhances the serviceability by 15.55%, as the vehicles connecting to the network increase when compared to the SA algorithm.

Fig. 6
figure 6

Pictorial comparison of network serviceability for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image

5.4 Availability

Availability is the percentage of vehicles getting served with minimum requirements in a network [34]. Fig. 7 presents the availability of the network satisfying incoming vehicles with a minimum data rate of 0.5 Mbps. As incoming vehicles connecting to the network increase, the capacity of FNs tends to exhaust in servicing vehicles. As a result, the network availability reduces gradually. The DRO algorithm enhances the availability better than the other algorithm. However, as vehicles arriving at the network increase at timeslot 150, the availability reduces. Fig. 8 shows the percentage of RBs reduction using the proposed algorithm and existing algorithms. The proposed algorithm maximizes the RBs reduction of vehicles up to 02.00% on average. Therefore, it is able to accommodate the vehicles with minimum data rates when they are not allocated with required data rates. Moreover, the proposed algorithm improves the availability of the network as vehicles connecting to the network increase by 08.94%, 17.41%, and 32.57% when compared to DRO, SA and RO, respectively.

Fig. 7
figure 7

Pictorial comparison of network availability for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image
Fig. 8
figure 8

Pictorial comparison of RBs reduction for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image

5.5 Throughput

Network throughput is obtained using the vehicle’s achievable rates at different timeslots and from different FNs. Using the Shannon formula, the achievable rate of vehicle k from FN i \(\in\) \(\mathcal {F}\), at timeslot t, is \(\mathcal {T}_{t}(ik)\) \(=\) \(B \log _2(1+S_{i}^{k})\), where B is the available bandwidth at \(i^{th}\) FN. If \(\alpha _{t}(ik)\) is an allocated time fraction to vehicle k, then the throughput of vehicle k from FN i is \(\tau _{t}(ik) =\) \(\alpha _{t}(ik)\) \(\times\) \(\mathcal {T}_{t}(ik)\). The network throughput is obtained from \(\sum _{\forall k \in \Vert \mathcal {P}_{t}(i)\Vert }\log \left( \sum _{t} \sum _{i\in \mathcal {F}}\tau _{t}(ik) \right)\) [17]. The network’s throughput is directly proportional to the time fraction allocated to the vehicles getting services. As a result, the throughput increases as the number of vehicles getting services increases. The network’s throughput for the proposed and existing algorithms is shown in Fig. 9, in which the throughput increases gradually as the vehicles getting services from the network increase. Furthermore, the proposed algorithm can accommodate newly arrived vehicles at FNs by reducing allocated RBs of vehicles that have already arrived without affecting their services. As a result, the proposed algorithm improves the network throughput up to 57.31%, 20.74%, and 39.13%, compared to DRO, SA, and RO algorithms, respectively.

Fig. 9
figure 9

Pictorial comparison of throughput for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image

5.6 Resource utilization efficiency

Resource utilization efficiency is the percentage of occupied RBs in a network. Fig. 10 shows the distribution of the average percentage of RBs used in the network obtained from the proposed and existing algorithms. The height of the box represents the distribution of the percentage of occupied RBs of FNs. The blue diamond symbol denotes the average percentage of RBs utilization of the entire network, and the red line inside the box denotes the median. When the arrival of vehicles at the network increases, it leads the FNs to be overloaded with their capacity. As a result, FNs become impotent to provide services to the new arriving vehicles. Thus, the existing algorithms, DRO, SA, and RO, provide 90.05%, 81.00%, and 83.38% of average RBs utilization, respectively. The DRO augmented by SA provide 82.12% of RBs utilization. On the contrary, the proposed algorithm minimizes the allocated RBs of vehicles that have arrived early in order to allocate RBs to newly arrived vehicles. Thus, the proposed algorithm provides 78.46% of average resource utilization by reducing allocated RBs of vehicles in overlapped coverage regions. Furthermore, the allocated RBs of vehicles are reduced by migrating RBs between pairs of FNs. The percentage of RBs reduction as vehicles connecting to the network increases for the proposed and existing algorithms is shown in Fig. 8. The reduced RBs of vehicles from FNs are reused to provide services to the newly arrived vehicles. The simulation results show that the proposed algorithm improves RB utilization efficiency by reducing allocated RBs by 12.87%, 03.13%, and 05.90% as compared to DRO, SA, and RO algorithms, respectively. Therefore, the proposed algorithm improves resource utilization efficiency by allocating released RBs to newly arrived vehicles.

Fig. 10
figure 10

Pictorial comparison of network resource utilization efficiency for DRM, DRO, SA, DRO+SA and RO algorithms

Full size image

6 Conclusion and future work

In this paper, we propose a DRM algorithm to manage RBs allocation in FEVANETs by considering vehicles in overlapped coverage regions of two or more FNs, and migrating RBs of a set of vehicles among pairs of FNs. The objective of the proposed algorithm is to improve the network service capability, serviceability, availability, throughput, and resource utilization efficiency by minimizing allocated RBs. The proposed algorithm maximizes the service capability of the network by minimizing the occupied RBs of vehicles that have already arrived. This reduction in allocated RBs is achieved by migrating allocated RBs of a set of vehicles among FNs and it is addressed by formulating ILP. The simulation outcomes show that the proposed algorithm reduces occupied RBs among FNs by migrating RBs of the set of vehicles and achieves better service capability, serviceability, availability, throughput and resource utilization efficiency when compared to other migration algorithms, such as DRO, SA and RO. As a future extension of this work, it can be extended to minimize energy consumption by FNs while providing services to vehicles by considering dynamic network conditions. Moreover, the proposed algorithm can be simulated using the traffic simulator, called simulation of urban mobility and the network simulator, called network simulator version 2, in order to make it more realistic. Alternatively, these simulators will provide real mobility traces to measure the performance of the proposed algorithm meticulously.