Towards minimizing delay and energy consumption in vehicular fog computing (VFC)

Abstract

Vehicular Fog Computing (VFC) is a natural extension of Fog Computing (FC) in Intelligent Transportation Systems (ITS). It is an emerging computing model that leverages latency aware and energy aware application deployment in ITS. However, due to heterogeneity, scale and dynamicity of vehicular networks (VN), deployment of VFC is a challenging task. In this paper, we propose a multi-objective optimization model towards minimizing the response time and energy consumption of VFC applications. Using the concepts of probability and queuing theory, we propose an efficient offloading scheme for the fog computing nodes (FCN) used in VFC architecture. The optimization model is then solved using a modified differential evolution (MDE) algorithm. Extensive experimentations performed on real-world vehicular trace of Shenzhen, reveals the superiority of proposed VFC framework over generic cloud platforms.

Keywords

Intelligent transportation systems modified differential evolution vehicular fog computing

1 Introduction

An Intelligent Transportation System (ITS) is a pervasive network of densely populated energy and resource-constrained devices and vehicles, all capable of gathering and transferring huge volumes of heterogeneous data in real-time. However, due to the Computing-Bandwidth-Energy (CBE) restrictions of the cellular network, a system of this complexity is practically unfeasible [1]. Through the notion of Internet of Things (IoT), the future internet is bringing the ITS devices and applications connected to the internet [2]. By blending the vehicles and roadside infrastructures viz. Roadside Units (RSU), On-board Units (OBU), access points (AP) and base stations (BS), etc, into the internet, they become smart, with the ability to react and make decisions on their own [8]. Internet of Vehicles (IoV) is an extension of IoT technology in Vehicular Networks (VN), i.e. those smart ‘things’ being connected over internet are restricted to only vehicles. Through the use of modern electronics and integration of the information, IoV helps to maintain traffic flow, performs more effective fleet management and accident avoidance, etc. In fact, one of the key objective of IoV is to achieve the vision of ‘from Smart phone to Smart car’ [5].

As majority of Smart City (SC) architectures are being proposed to modernize the existing city infrastructures, several challenges may arise [4]. For instance, some devices may be old, some are new, and all of them need to communicate with different protocols. Handling such diverse range of physical as well as logical infrastructures will give rise to compatibility and interoperability issues. For many ITS applications such as traffic congestion management, autonomous driving, collision avoidance, etc, latency can be a critical issue when real-time decisions are to be made [3]. With vehicles and IoV devices generating and recording data in real time, every second or minute, the amount of data can be massive. When multiplied by hundreds of vehicles and devices across multiple traffic zones, the amount of data can be too huge for the network to handle when it finally reaches the cloud data center. Consequently, employing too many servers and machines for handling those computing requests means exorbitant customization costs and carbon footprint [6, 26]. The de facto Cloud Computing (CC) model, though have virtually unlimited resource pooling capabilities, it ceases to welcome its proponents because of its failure in building a common and multipurpose platform that can provide feasible solutions to the mission critical ITS requirements [7, 11].

Vehicular Fog Computing (VFC) is a parallel and distributed computing model where storage and computing resources are installed on the intermediary VN intersections, network switches, RSUs, sensors and gateways [9, 17]. Specifically, the VFC is a natural extension of Fog Computing (FC) in VN, where the key goal of FC is to alleviate the connectivity, bandwidth and latency issues prevalent in CC [18, 20]. The notion is to allow machines and vehicles to speak directly to each other without traversing the cloud, by connecting machines, devices and sensors directly to each other (at only one or few steps). Another objective of FC based ITS platforms is to standardize and ensure secure communication between all VN entities, old and new, across all traffic zones, so that customization and service costs are kept to a minimum. Both these platforms complement each other to form a mutually assistive and inter-dependent service continuum between the remote cloud and the ITS point of attachments (PoA), in order to make computing, storage, control, and networking services possible anywhere along the continuum [10, 23].

Due to the decentralized and heterogeneous nature of vehicular networks, the scale of FCN infrastructure, the complex structure of CDCs, the heterogeneity of resource types and their interdependencies, the variability and unpredictability of the vehicular workload, workload allocation in VFC is a complex task [22]. In the context of VFC, workload allocation the process of allocating SCN and energy resources (indirectly) to a set of applications/services, such that the performance objectives of the ITS applications, network operators, the service providers and the vehicle users are satisfied [24, 25]. The objective is also to efficiently use the available resources (e.g. VM) towards meeting the Service Level Agreements (SLAs) and associated constraints in a multi-user environment. Besides, the workload scheduling algorithms are primarily focused to improve the applications’ performance, their availability, cost-effective scaling of available resources in accordance with dynamic application demands [27]. Simultaneously, the algorithms must also meet non-functional requirements such as security, regulation and trust, etc.

Motivated by this, in this paper, we present a intuition based general framework to investigate the feasibility of VFC architectures. The key contribution of this paper are as follows:

We provide a multi-objective optimization (MOO) model for minimizing the delay and energy consumption of VFC architecture and perform a comparative study of response time and power consumption with respect to generic CC framework.

Using the concepts of probability and queuing theory, we thoroughly examine the offloading and computation profiles of different computing elements in a VFC system.

We solve the proposed MOO framework using a Modified Differential Evolution (MDE) algorithm.

We provide extensive simulation studies on real-world vehicular traces of Snenzhen, China, in order to demonstrate the feasibility of the VFC scheme over generic cloud based ITS architectures.

2 Networking and system model

In a cloud computing model, the Cloud Data Center (CDC) provides sharable resource pool available for on-demand use [16]. Since the CDCs are far away from the data generation sites, data migration and service latencies will be intolerable for real-time and interactive ITS applications. However, in VFC architecture, low/battery powered FCNs are deployed at the dedicated edges of the network to offer store, compute and networking support for ITS applications, offering real-time response and geo-distributed intelligence [19]. Figure 1 shows a general framework for a VFC (Vehicle-Fog-Cloud) architecture considered in this work. There are three layers in this architecture. The lowermost physical layer comprises of vehicles, passenger devices (PDs), Intelligent Traffic Lights (ITL), Vehicular Sensor networks (VSN) etc. For sake of simplicity but without loss of generality we will use only vehicle to represent a physical layer entity. Fog computing nodes (FCNs) such as switches, routers, micro-servers, etc, are deployed in middle FC layer whereas high performance cloud servers are located in CC layer.

Fig. 1

Offloading Policy in proposed VFC.

Consider a VFC framework where data and computation are selectively offloaded to either cloud or fog layer depending on the ITS application specific logic. Without loss of generality, let us assume the sets C, F, and N represents the set of CDCs, FCNs and number of consumers. The cardinality of each these sets are C, F and N respectively. Thus, an instance of VFC network (see Fig. 3.1) can be modeled as a connected cellular graph G {V (.) , E (w)} of order (C+N +F), whose vertices V (.) are constituted by sets C, F, and N respectively. The function E (w) denotes the set of edges having weights w = {w₁, w₂, . . .}. Here each weight w_i represents the Network Usage Descriptor (NUD) between each pair of vertices in V(.). In our analysis we model w_i by a triple (r_n2n, ω_n2n, τ_n2n) , where r_n2n denotes the transmission rate between two nodes, ω_n2n denotes the link bandwidth between two nodes and τ_n2n denotes the end-to-end delay. In this section we first describe the delay model for a typical VFC scenario. Following this, we formulate the energy consumption model for the whole network.

2.1 Delay model

Each time a workload is generated by the vehicle, it can either processed locally by vehicle OBU, offload it to FC layer or offload to CC layer. The FCNs in turn may process the workload, forward to other FCNs, or dispatch to CC servers. Thus, the response time τ_v for vehicle v can be expressed as:

$\begin{matrix} τ_{v} = & Π_{v}^{V} \cdot τ_{v}^{s} + [(1 - Π_{v}^{V}) \cdot {BV}_{v}^{l} {(τ_{vf}^{tran} \cdot {BV}_{v}^{b}) \\ + τ_{vf}^{prop} + τ_{vf} (t) \cdot {BV}_{vf}} + (1 - {BV}_{v}^{l}) {τ_{vc}^{tran} \\ + τ_{vc}^{prop} + τ_{c}^{proc}}] \end{matrix}$ (1) where $Π_{v}^{V}$ is the probability that request is processed by the host vehicle OBU, $(1 - Π_{v}^{V})$ gives the probability of offloading to upper layers, ${BV}_{v}^{l}$ is the binary variable that indicates whether vehicle v is connected to a location or not. If ${BV}_{v}^{l} = 0$ the vehicle is connected to cloud. Binary variable ${BV}_{v}^{b}$ indicates whether link of bandwidth unit (BU) b is allocated to v-f link or not.

We denote the computing capability of vehicle v as $Q_{v}^{s}$ and assume that the incoming requests follow a Poisson distribution with arrival rate $r_{v}^{a}$ . Modeling the traffic model at the host vehicle as an M/M/1 queue, we obtain the response time $τ_{v}^{s}$ for locally processing requests as: $τ_{v}^{s} = τ_{v}^{s} = \frac{1}{N} \sum_{v = 1}^{V} \frac{1}{Q_{v}^{s} (1 - {POF}_{v}) - Π_{v}^{V} \cdot r_{v}^{a}}$ (2) where, POF_v is the processor occupancy factor that represents the normalized workload on vehicle v, i.e. the fraction of CPU that has been engaged for serving other tasks. A zero value of POF_v indicates the CPU is idle, thus can accept requests from PD. In case POF_v = 1 the server is fully occupied and the requests must be offloaded to either fog or cloud. Each time when the vehicle is on run, it continuously executes some kernel requests. Thus, $0 \leq {POF}_{v}) \leq 1$ (3) The transmission delay is the time taken for a client process to send the information over the network. Thus the transmission time $τ_{vf}^{tran}$ for vehicle v to transmit a request of size σ bytes into FCN f is given by: $τ_{vf}^{tran} = \frac{r_{f}^{a} \cdot σ}{R}$ (4) where $R_{v}^{f}$ is the uplink data rate for computation offloading of vehicle v. Since the uploading data rate depends on the transmit power of vehicle P _v, it can be expressed as: $R_{v}^{f} = ω \ln (1 + \frac{C \cdot g_{v}}{h_{o} + \sum_{v^{*} \in V \land v \neq v^{*}} P_{v} \cdot g_{v}})$ (5) where ω is the channel bandwidth and ω is the transmission power of vehicle v, g_v is the channel gain between vehicle v and RSU and h_o denotes the noise power. Propagation delay is the time taken to transmit a data signal from source to destination. The propagation speed of wireless communications is the speed of light (c). In Vehicle-to-Infrastructure (V2I) communication, we generally use DSRC or LTE protocol, hence the propagation delay $τ_{vf}^{prop}$ for offloading workload from vehicle v at location a to FCN f at location b is given by: $τ_{vf}^{prop} = \frac{τ_{vf}^{prop}}{c} \forall v \in V$ (6) where (x1, y1) and (x2, y2) are the Cartesian coordinates of location a and b respectively. The transmission delay term $τ_{vc}^{tran}$ for vehicle to cloud offloading and the propagation delay term $τ_{vc}^{prop}$ in Equation (1) can be derived similarly. $τ_{C}^{proc}$ is the computation delay in cloud layer which comprises of both queuing delay as well as processing delay. It is defined in section 2.5. τ_vf (t) is the delay in the FC layer corresponding to t^th offload. Thus it can be recursively defined as:

$\begin{matrix} τ_{vf} (t) = π_{f} \cdot τ_{f}^{proc} + (1 - π_{f}) [{BV}_{f}^{t} \cdot {(τ_{{ff}^{*}}^{tran} \cdot {BV}_{f}^{b}) \\ + τ_{{ff}^{*}}^{prop} + τ_{vf} (t + 1)} + (1 - {BV}_{f}^{t}) \cdot {(τ_{fc}^{tran} \cdot {BV}_{f}^{b}) \\ + τ_{fc}^{prop} + τ_{c}^{proc}}] \end{matrix}$ (7) where π_f is the probability of workload acceptance at FCN f, binary variable ${BV}_{f}^{t}$ indicates an offloading function defined as: ${BV}_{f}^{t} = {\begin{matrix} 1 t \leq t_{z} \\ 0 otherwise \end{matrix}$ (8)

Since delay term $τ_{vf}^{(t)}$ is a recursive function that depends on the number of hops made during fog-fog offload, it is required to define the inter-fog cooperation mechanism. Thus, in order to explain the terms involved in Equation (7), we investigate the VFC offloading strategy in section.

2.2 Energy model

The net power consumption term in a typical VFC model involves energy $(P_{sys}^{tran})$ consumed due to transmission of workloads from physical layer to cloud servers directly or via FC layer, and energy term $P_{sys}^{comp}$ due to computations at vehicles, FCNs and cloud servers. Thus, $P_{sys} = P_{sys}^{tran} + P_{sys}^{comp}$ (9) where, $P_{sys}^{tran} = \sum_{v \in V} P_{vf}^{tran} + \sum_{f \in F \land f^{*} \in F} P_{{ff}^{*}}^{tran} + \sum_{c \in C} P_{fc}^{tran}$ (10) and $P_{vf}^{tran} = p_{v}^{tran} \cdot τ_{vf}^{tran} = \frac{p_{v}^{tran} \cdot Π_{v}^{V} \cdot r_{v}^{V} \cdot σ_{v}}{R}$ (11) we have taken the transmit power $p_{v}^{tran}$ of vehicle v equal to 23 dBm. The expressions for $P_{{ff}^{*}}^{tran}$ and $P_{fc}^{tran}$ can be derived similarly. The power consumption due to computation is given as: $P_{sys}^{comp} = \sum_{v \in V} P_{v}^{comp} + \sum_{f \in F} P_{f}^{comp} + \sum_{c \in C} P_{c}^{omp}$ (12) Now, the energy consumption due to processing of a request of size σ_v by the OBU of vehicle v is given as: $P_{v}^{comp} = \frac{α_{v} \cdot σ_{v} \cdot γ_{v}}{p_{v}^{comp}}$ (13) where $P_{v}^{comp}$ is the compute power of vehicle v, γ_v is processing density, α_v is an application specific constant, defined as: $α_{v} = ξ_{v} \cdot (p_{v}^{comp})^{φ_{v}} + ϱ_{v}$ (14) Here, ξ_v, φ_v and ϱ_v are are application specific constants. We have taken ξ_v = 0.33, φ_v = 3 and ϱ_v = 0.1. The energy consumption profile of a typical fog node $(P_{f}^{comp})$ can be represented as a quadratic, monotonic increasing and strictly convex function of computation volume $r_{f}^{a}$ . The function satisfies the fact that marginal power consumption of fog nodes increases proportionally with time. It also ensures that computation power consumption to be proportional to the amount of analytics activities performed. Thus, $P_{f}^{comp} = A_{f} \cdot {(r_{f}^{a})}^{2} + B_{f} \cdot r_{f}^{a} + C_{f}$ (15) where A_f > 0, B_f ≥ 0, C_f ≥ 0 are predetermined parameters. For our analysis, A_f = 2, B_f = 3, and C_f = 1 respectively.

Similarly, if each data center is assumed to host homogenous computing elements (machines) of identical CPU frequency η_c, the power consumption component $P_{c}^{comp}$ of each computational element at cloud server can be approximated as a function of η_c, given by: $P_{c}^{comp} = {BV}_{c} \cdot η_{c} \cdot n_{c}$ (16) where BV_c is the binary variable that denotes the On/Off status of cloud server c., i.e. BV_c = 1 means On and vice versa, n_c denotes the number of turned-on machines at server c. The CPU frequency η_c of cloud server c can be approximated through a polynomial function given as: $η_{c} = D_{c} \cdot η_{c}^{◊} + E_{c}$ (17) where D_c and E_c are positive constants. In realistic scenario, ◊ varies between 2.5 and 3. All three attributes can be obtained by curve fitting against empirical measurements when profiling the system offline [21]. Thus, $P_{c}^{comp} = {BV}_{c} \cdot \cdot n_{c} (D_{c} \cdot η_{c}^{◊} + E_{c})$ (18)

2.3 FCN acceptance probability

Each time a request if presented to FCN f, it computes the estimated processing time $τ_{f}^{EWT}$ and compares it with processing threshold of given task. In case $τ_{f}^{EWT}$ is less than $τ_{\max}^{EWT}$ , the request will be accepted by FCN f. Hence, the acceptance probability of FCN f is given by: $π_{f} = π [τ_{f}^{EWT} < τ_{\max}^{EWT}]$ (19) Thus, in order to derive the value of π_f we need to obtain the probability distribution function (PDF) of $τ_{f}^{EWT}$ . By definition, $τ_{f}^{EWT}$ is the sum of the computing (queuing plus processing) delays of all the requests in FCN f. Thus, it can be given as: $τ_{f}^{EWT} = \sum_{p}^{N} Ψ_{p}^{f}$ (20) where $Ψ_{p}^{f}$ is the random variable showing the computing delays of p^th task of FCN f.

Define variable $τ_{f}^{n}$ as the sum of n exponentially distributed processing delays i.e. $τ_{f}^{n} = \sum_{p}^{n} Ψ_{p}^{f}$ . Since, the sum of n independent and identically distributed exponential random variables with parameter λ is a Gamma function with parameters (n, λ) thus the PDF of $τ_{f}^{n}$ is given by: $Γ_{τ_{f}^{n}} = \frac{λ_{f} \cdot (λ_{f} \cdot x)^{n - 1} \cdot e^{- λ_{f} \cdot x}}{(n - 1)!} u (x)$ (21) where u (x) is the unit step function. If $π_{f}^{n}$ denote the steady state probability of FCN f, the value of π_f can be derived as:

$\begin{matrix} π_{f} = π [τ_{f}^{EWT} < v τ_{\max}^{EWT}] = \sum_{n = 1}^{\infty} π [τ_{f}^{EWT} < τ_{\max}^{EWT}] \cdot π_{f}^{n} \\ = π_{f}^{o} + \sum_{n = 1}^{\infty} π [τ_{f}^{EWT} < τ_{\max}^{EWT}] \cdot π_{f}^{n} \\ = π_{f}^{o} + \sum_{n = 1}^{\infty} [\int_{0}^{τ_{\max}^{EWT}} Γ_{τ_{f}^{n}} (x) dx] \cdot π_{f}^{n} \end{matrix}$ (22)

2.4 Delay in FC layer

Having defined the inter-fog communication strategy and the FCN’s acceptance probability π_f, we are in a position to explain the terms involved in Equation (7). The first delay term $τ_{f}^{proc}$ in Equation (7) gives the average computing time of FCN f. For that we model each FCN as an M/M/1 queue where the incoming workload for each FCN f follows a Poisson distribution with arrival rate $r_{f}^{a}$ and processing times follow an exponential distribution with rate $τ_{f}^{proc}$ . In order to obtain expression for $τ_{f}^{proc}$ we use the FCN’s steady state probability $π_{f}^{n}$ defined in Equation (22). Thus, $τ_{f}^{proc} = E (τ_{f}^{EWT}) = \sum_{n}^{\infty} E (τ_{f}^{EWT} | N = n) \cdot π_{f}^{n}$ (23) Using the closed form of $π_{f}^{n}$ , we get $E (τ_{f}^{EWT} | N = n) = \frac{n}{λ_{f}}$ (24) From (23) and (24) we get $τ_{f}^{proc} = \sum_{n}^{\infty} (\frac{n}{λ_{f}}) \cdot π_{f}^{n}$ (25)

The binary variable ${BV}_{f}^{t}$ in Equation (7) is the decision parameter for FCN-to-FCN offloading. For instance, as shown in Equation (8), if the number of hops t < t_z then ${BV}_{f}^{t} = 1$ which means the request can be forwarded to neighboring FCN. Consequently, inter-FCN propagation delay $(τ_{{ff}^{*}}^{prop})$ , transmission delay $(τ_{{ff}^{*}}^{tran})$ as well as FC delay term $τ_{vf}^{(t + 1)}$ for next hop will come into play.

In case, the number of hops exceeds the maximum allowable hops for the virtual FCN cluster z i.e. t ≤ t_z, the request will be dropped by all FCNs and thus dispatched to cloud. Here, the request incurs FCN-cloud propagation and transmission delay terms $τ_{fc}^{prop}$ and $τ_{fc}^{prop}$ respectively. Moreover, it also incurs an additional delay term $τ_{c}^{proc}$ for cloud scale processing, as described in next section.

2.5 Delay in CC layer

In order to evaluate the average computing delay of CC layer, we model each cloud server c as an M/M/∞ queue with arrival rate $r_{C}^{a}$ . Thus, the computation delay at cloud server c is given by: $r_{C}^{a} = \frac{1}{r_{c}^{a}}$ (26)

Therefore, the average service delay for vehicle v can be given as: $τ_{v}^{s} = \frac{\sum_{v \in V} τ_{v}}{| V |}$ (27)

2.6 Modeling the workload

Since workload arrival rate $r_{f}^{a}$ at FCN f needed for the finding the FCN’s steady-state probability used in (23), in this section we derive the workloads for both FC and CC layer in terms of total workload $r_{v}^{a}$ generated from vehicle v.

An FCN may host numerous VM for executing tasks generated from both physical layer as well as FC layer. Thus, the incoming traffic r_f for FCN f can be given as: $r_{f} = r_{f}^{v} + \sum_{i = 1}^{t_{z}} r_{fi} \forall i$ (28) where $r_{f}^{v}$ is the workload coming from physical layer, r_{f
₁}, r_{f
₂} ….r_{f
_{t
_z}} represents the workload for FCN f coming from neighboring FCNs f₁, f₂,... f_{t
_z} respectively. Since the actual workload entering into FCN’s processing queue depends on the acceptance probability π_f, thus $r_{f}^{a} = π_{f} \cdot r_{f} = π_{f} \cdot (r_{f}^{v} + \sum_{i = 1}^{t_{z}} r_{fi}) \forall i$ (29) For obtaining the expression for $r_{f}^{v}$ used in (29) we define a mapping function F^-1 (f) that gives the set of vehicles v ∈ V that offloads their workload to FCN f. Then, the closed form of $r_{f}^{v}$ can be given as: $r_{v}^{f} = \sum_{v \in F^{- 1} (f)} {r_{v}^{a} \cdot (1 - π_{v}^{V}) \cdot {BV}_{v}^{l}}$ (30)

In order to evaluate equations for r_fi in (30), we need to solve the following system of equations. $ψ_{f 1} = (1 - π_{f}) \cdot r_{f}$ (31) $ψ_{f 2} = (1 - π_{f}) \cdot r_{f 1}$ (32) $ψ_{{ft}_{z}} = (1 - π_{f}) \cdot r f (t_{z} - 1)$ (33)

If fog node f cannot accept a task sent from vehicle v, it will be offloaded for the first time to FCN f’s best neighbour, according to (31). Other Equations (32-33) can be evaluated similarly. In general, if a k-hop request is rejected by FCN f, then it will be offloaded for (k + 1) ^th hop to the f’s best neighbor. Finally, if a request has already made t_z hops, and is not accepted by fog nodej, it will be offloaded to the cloud. Thus, $C_{f} = (1 - π_{f}) \cdot ψ_{{ft}_{z}}$ (34) Though ψ_f1 can be obtained from Equation (31), ψ_f2, ψ_f3,....ψ_{ft
_z} can only be obtained after evaluating r_fi’s. Now, if f^* is the neighboring FCN in the previous hop (i.e. from the FCN that has dispatches its request to f), the probability that f^*’s nearest node is FCN f, is given by: $ϑ_{f^{*}} = \frac{1}{\deg (f^{*})}$ (35) where deg (f^*) is the degree of node labeled f^* in the cellular graph G (.). Hence, the values of r_fi can be estimated as: $r_{fi} = \sum_{f^{*} \in neighbor (f)} [ψ_{f^{*} i} \cdot \frac{1}{(\deg (f^{*})}] 1 \leq i \leq t_{z}$ (36)

Once the workload for FC is obtained, we can also obtain the workload for the CC layer. It can be observed from Fig. 1 that the incoming traffic to the cloud servers are both from physical layer nodes and as well as from FC layer. Thus using the same strategy as in Equation (29), we can obtain the workload for cloud server c as:

$r_{c}^{a} = \sum_{v \in G^{- 1} (c)} {r_{v}^{a} \cdot (1 - π_{v}^{V}) \cdot (1 - {BV}_{v}^{l}) + \sum_{f \in H^{- 1} (c)} C_{f}}$ (37)

where G^-1 (c) and H^-1 (c) are the mapping functions that represents the set of vehicles and set of FCNs that offload their workload to cloud server c respectively.

2.7 Optimization model

Our objective will be to find the energy consumption-service delay trade-off in both generic cloud based as well fog based computational model. In other words, the aggregated power consumption of vehicles, FCNs and cloud servers are to be minimized by ensuring that the average response time of vehicular request is less than a given threshold $τ_{v}^{o}$ . Therefore, in this section, we present a multi-objective mixed-integer nonlinear programming (MINLP) formulation for minimum delay and minimum energy, with the joint consideration of all the constraints defined for VFC architecture. The overall optimization problem can be formulated as: $\begin{matrix} P 1 & \underset{\forall v, \forall f, \forall c}{minimize} & F (τ_{v}, P_{sys}) \\ s . t : 3, 19 \end{matrix}$ (38) and $τ_{v} \leq τ_{v}^{o}$ (39)

3 Solution strategy and algorithmic set-up

It can be seen that the formulated optimization model is a multistage, discrete, non-convex, constrained mixed-integer non-linear programming problem (MINLP). Usually classical mathematical programming techniques fail to provide tractable solutions to such problems. Evolutionary optimization algorithms specifically meta-heuristic methods such as differential evolution (DE) provide promising approach to solve an MINLP. DE is a population-based evolutionary multi-objective optimization (EMO) method which had proven to be very simple yet powerful to solve minimization problems with nonlinear and multi-modal objective functions. It differs from conventional EMO in that instead of having a predefined probability distribution function (pdf) for mutation process, it utilizes the differences of randomly sampled pairs of objective vectors for its mutation process. In other words, the initial value of the j^th parameter in the i^th individual at the generation is generated by: $x_{i, o}^{j} = x_{\min}^{j} + rand (0, 1) \cdot (x_{\max}^{j} - x_{\min}^{j})$ (40)

However, it is worth noting that the optimization capability of DE depends extensively on the diversity between vectors. It may lead to a high possibility of obtaining a local optimal solution if the diversity of the population descends too fast during evolutionary process [13]. In order to handle this, in selection process, we employed a modified version of differential evolution with a fitness sharing function of niche radius (ρ), that reduces the fitness of similar offspring’s. Here, the individuals lying in same group will share the corresponding fitness value and in the selection operation, clusters having larger fitness sharing value will be selected for producing the next generation off springs. The fitness sharing function is given by: $f (δ, d_{ij}) = {\begin{matrix} 1 - (\frac{d_{ij}}{ρ})^{δ} 0 \leq d_{ij} < ρ \\ 0 otherwise \end{matrix}$ (41) The niche count ρ_c for every individual population j can be calculated as: $ρ_{c} = \sum_{j = 1}^{F} f (δ, d_{ij})$ (42)

Since during selection process, individuals with large fitness survive and used for mutation or recombination purpose,thus if any individual with large fitness survive during selection process, the shared fitness is simply calculated by: $S_{f} = \frac{f_{j}}{\sum_{j = 1}^{F} f (δ, d_{ij})}$ (43) Calculating the shared fitness $S_{f}^{*}$ before selection operation supplements significant computations for evaluating values before executing selection operation. The underlying principle of employing $S_{f}^{*}$ is to cluster the population into smaller groups defined by a similarity measure. In this work the similarity is defined by a distance function d_ij that satisfies Equation (44). $f (d_{ij}) = {\begin{matrix} 0 \leq d_{ij} \leq 1 \\ f (0) = 1 \\ lim_{d_{ij} \to \infty} f (d_{ij}) = 0 \end{matrix}$ (44)

3.1 Encoding strategy

As shown in Fig. 2, an offloading strategy V_f for all the vehicular workload uploaded from each RSU to either FC layer or CC layer is encoded by a chromosome C_p. Each gene in the chromosome represents the FCN or cloud server to which the workload is offloaded. If FCN f is assigned the task from v^th vehicle, the value of gene at v^th position will be f. Other settings for MDE is given in Table 1. The complete description of MDE based offloading strategy is given in Algorithm 1.

Fig. 2

Proposed encoding strategy for computation offloading.

Table 1

MDE parameter settings

Parameter	Value
Population size	100F
Crossover Probability	DE/rand/1
Mutation Probability	0.1
Number of Iterations	3000

4 Case study

In order to demonstrate the feasibility of the proposed VFC model, in this subsection we provide some preliminary results according to real-world traces of Taxies and Buses in Shenzhen, China, generated by Project-Shenzhen Smart City Initiative [15]. Shenzhen has nearly 12 million population, and its size is about 2050 sq. Km. We conduct a comprehensive comparative study on mobility patterns of two heterogeneous transportation fleets consisting of over 13 thousand buses and 14 thousand taxi-cabs, to identify their real-world features. The attribute description of each vehicle in the dataset is given in Table 3. A candidate RSU is assumed to be installed across the highways with range of 1Km2 across major road segments in Shenzhen. The arrival rate for moving vehicles is compiled every 15 minutes within the range of 500 m of each RSU. By analyzing the arrival rate of moving vehicles in the dataset, we notice that the average number of vehicles is between 100 and 500 per second with an RSU. The other network parameters are given in Table 4.

Table 2
Offloading Probabilities and corresponding operation modes

Case $Π_{v}^{V}$ ${BV}_{v}^{l}$ Mode

1 0.0 0 Cloud only

2 0.1 0 t_z≈ ∞ (No cloud)

3 0.0 1 VFC (no edge)

4 0.1 1 VFC

Case	$Π_{v}^{V}$	${BV}_{v}^{l}$	Mode
1	0.0	0	Cloud only
2	0.1	0	t_z≈ ∞ (No cloud)
3	0.0	1	VFC (no edge)
4	0.1	1	VFC

Table 3

Fleet description in Shenzhen, China [15], (Date of data collection: 2013-10-22)

Bus	Taxi
# of bus lines-976	# of bus lines-976
# of Bus- 13032	# of Bus- 14,453
# of passengers-4 million	# of passengers- 66
# records (one day)- 4 million	million
Format- Bus ID, Time, Latitude, Longitude, Occupancy	# records (one day)- 4 million
Status, Speed	Format- Taxi ID, Time, Latitude, Longitude, Occupancy
Sampling rate: 2/min.	Status, Speed
	Sampling rate: 2/min.

Table 4

Parameter specifications

Parameters	For real-world VN
Number of applications per vehicle	5
$r_{v}^{a}$	U[1, 5]
σ	N (10⁶, 2 × 10⁵) cycles
$τ_{v}^{o}$	1 sec
Available BU at each FCN channel	10
Processing Capacity of FCN $(Q_{f}^{p})$	8 × 10⁹ cycles/sec
Vehicle to FCN processing Ratio	U[100,400]
FCN to Cloud processing Ratio	U[200,500]
Communication cost	U[1,3]
VM rental cost (per VM)	U[2,5]
Transmission cost (to fog)	U[0.5, 1.5]
Transmission cost (to cloud)	U[2.5, 5]
Transmission delays	U[1, 5]
Propagation delays	U[0.5,1.2]
Number of runs	100
POF _v	0.3

4.1 Results and discusions

4.1.1 Variation of delay-power consumption with varying workload

In order to analyze the performance of proposed offloading strategy, we define four modes of computation, based on the value of $Π_{v}^{V}$ , ${BV}_{v}^{l}$ & t_z as shown in Table 2. In Fig. 3, we show the variation of response time and power consumption with varying vehicular workloads. It can be observed that the response time in Case 4 is minimum. This is due to the combined effect of processing at both local edge (vehicle) and FCNs. However, the delay is maximum in Case 1 because the workloads need to be offloaded to the remote cloud servers which incurs high communication delay in Equation (1). Similaly, the power consumption is also minimum in Case 4. It is due the distributed nature of FCNs across the VN infrastructures. The decentralized FCNs architectrure allows hosting and distribution the vehicular workload in a peer-to-peer (P2P) fashion across the network, thereby significantly reducing the energy footprint.

Fig. 3

Delay-Power consumption with varying workload for generic cloud model.

4.1.2 Comparison of response delay and power consumption for four cases

In Fig. 4(a) and (b) we respectively summarize the variation of delay and power consumption for all four cases at a glance. It can be seen that the delay is least for Case 4 (green bars) in Fig. 4(a). It is due to the physical proximity of FCNs where most of the workload is processed, thereby saving the vehicle-to-cloud WAN bandwidth. Similar trend follows from power consumption as in fog assisted systems (case 4) avoids excessive energy dissipation in high frequency cloud servers, insted it uses the locally hosted commodity servers (i.e. FCNs) where energy dissepation rate is substantially lower (refer to Equations (15) and (18)).

Fig. 4

(a): Delay comparison for four cases (b): Comparison of power consumption for four cases.

5 Conclusion

In this paper, we present a multi-objective optimization (MOO) analytical framework for minimizing the response time and power consumption in VFC architecture. The vision of VFC is studied in this paper as a complement to cloud computing and an essential ingredient of the ITS infrastrctures. We used the concepts of probability and queuing theory to introduce a model for handling vehicular workload across various layers of VFC architecture. By solving the MOO model with an evolutionary MDE algorithm, we showed how our delay-minimizing fog offloading policy can be beneficial for the mission critical ITS applications. Extensive numerical results for a benchmark real world vehicular trace are presented to demonstrate the efficiacy of proposed VFC framework.

References

Ning

, Huang

and Wang

, Vehicular fog computing: Enabling real-time traffic management for smart cities, IEEE Wirel Commun26(1) (2019), 87–93.

Saleem

, Crespi

, Rehmani

M.H.

and Copeland.

, Internet of things-aided Smart Grid: technologies, architectures, applications, prototypes, and future research directions, IEEE Access7 (2019), 62962–63003.

Bitam

and Mellouk.

, Its-cloud: Cloud computing for intelligent transportation system. In 2012 IEEE global communications conference (GLOBECOM), pp. 2054–2059. IEEE, 2012.

Hussain

M.M.

and Beg

M.M.

, Fog Computing for Internet of Things (IoT)-Aided Smart Grid Architectures, Big Data and cognitive computing3(1) (2019), 8.

Kaiwartya

, Abdullah

A.H.

, Cao

, Altameem

, Prasad

, Lin

C.-T.

and Liu

, Internet of vehicles: Motivation, layered architecture, network model, challenges, and future aspects, IEEE Access4 (2016), 5356–5373.

Sarkar

, Subarna

and Sudip

, Assessment of the Suitability of Fog Computing in the Context of Internet of Things, IEEE Transactions on Cloud Computing6(1) (2015), 46–59.

Kenneth

, Ganesh

and Van Renesse

, Running smart grid control software on cloud computing architectures, In Workshop Computational Needs for the Next Generation Electric Grid, Cornell University, pp. 1–33, 2011.

Hussain

M.M.

, Alam

M.S.

and Beg

M.M.S.

, Fog Computing Model for Evolving Smart Transportation Applications, In Fog and Edge Computing: Principles and Paradigms, Edited by Rajkumar Buyya, WILEY, 2019, pp. 347–372.

Hou

, Yong

, Chen

, Wu

, Jin

and Chen

, Vehicular fog computing: A viewpoint of vehicles as the infrastructures, IEEE Transactions on Vehicular Technology65(6) (2016), 3860–3873.

10.

Hussain

M.M.

and Beg

M.M. S.

, Using Vehicles as Fog Infrastructures for Transportation Cyber-Physical Systems (T-CPS), International Journal of Software Science and Computational Intelligence (IJSSCI)11(1) (2019), Article 4.

11.

Van Steen

and Tanenbaum

A.S.

, Distributed systems principles and paradigms, Network2 (2002), 28.

12.

Hussain

M.M.

, Alam

M.S.

and Beg

M.M.S.

, Feasibility of fog computing in smart grid architectures, In Proceedings of 2nd International Conference on Communication, Computing and Networking, pp. 999–1010. Springer, Singapore, 2019.

13.

Yang

G.Y.

, Dong

Z.Y.

and Po Wong

, A modified differential evolution algorithm with fitness sharing for power system planning, IEEE Transactions on Power Systems23(2) (2008), 514–522.

14.

Hussain

M.M.

, Alam

M.S.

, Beg

M.M.S.

and Laskar

S.H.

, Big Data Analytics Platforms for Electric Vehicle Integration in Transport Oriented Smart Cities, International Journal of Digital Crime and Forensics (IJDCF)11(3) (2019), Article 2. IGI Global.

15.

Wang

, Li

, Zhang

, Ge

, Fu

, Zhang

, Wang

and Zhang

, sharedCharging: Data-Driven Shared Charging for Large-Scale Heterogeneous Electric Vehicle Fleets, Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies3(3) (2019), 108.

16.

Hussain

M.M.

, Alam

M.S.

and Beg

M.M.S.

, Vehicular Fog Computing-Planning and Design, Procedia Computer Science133 (2019), Elsevier.

17.

Huang

, Lu

and Choo

K.-K.R.

, Vehicular fog computing: architecture, use case, and security and forensic challenges, IEEE Communications Magazine55(11) (2017), 105–111.

18.

Truong

N.B.

, Lee

G.M.

and Ghamri-Doudane

, Software defined networking-based vehicular adhoc network with fog computing, In 2015 IFIP/IEEE International Symposium on Integrated Network Management (IM), pp. 1202–1207. IEEE, 2015.

19.

Chen

, Jiao

, Li

and Fu

, Efficient multi-user computation offloading for mobile-edge cloud computing, IEEE/ACM Transactions on Networking24(5) (2015), 2795–2808.

20.

Wen

, Zhang

and Luo

, Energy-optimal mobile application execution: Taming resource-poor mobile devices with cloud clones. In 2012 Proceedings Ieee Infocom, pp. 2716–2720. IEEE, 2012.

21.

Beraldi

, Abderrahmen

and Alnuweiri

, Cooperative load balancing scheme for edge computing resources, In 2017 Second International Conference on Fog and Mobile Edge Computing (FMEC), pp. 94–100. IEEE, 2017.

22.

Fricker

, Guillemin

, Robert

and Thompson

, Analysis of an offloading scheme for data centers in the framework of fog computing, ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS)1(4) (2016), 16.

23.

Guédon

, Hidden hybrid Markov/semi-Markov chains, Computational statistics & Data analysis49(3) (2005), 663–688.

24.

Alber

, Exact Algorithms for NP Hard Problems on Networks: Design, Analysis, and Implementation, PhD diss., University of Tübingen, Germany, 2002.

25.

Krishnaveni

and Sivakumar

, Survey on dynamic resource allocation strategy in cloud computing environment, International Journal of Computer Applications Technology and Research2(6) (2013), 731–737.

26.

Woeginger

G.J.

, Exact algorithms for NP-hard problems: A survey, In Combinatorial optimization–eureka, you shrink!, pp. 185–207. Springer, Berlin, Heidelberg, 2003.

27.

Mario

J.-P.H.

and Christian

, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, In Proceedings of the 8th annual international conference on Mobile computing and networking, pp. 172–182. ACM, 2002.

Towards minimizing delay and energy consumption in vehicular fog computing (VFC)

Abstract

Keywords

1 Introduction

2 Networking and system model

Table 2 Offloading Probabilities and corresponding operation modes Case Π v V BV v l Mode 1 0.0 0 Cloud only 2 0.1 0 t z ≈ ∞ (No cloud) 3 0.0 1 VFC (no edge) 4 0.1 1 VFC

4.1.1 Variation of delay-power consumption with varying workload

References

Table 2
Offloading Probabilities and corresponding operation modes

Case $Π_{v}^{V}$ ${BV}_{v}^{l}$ Mode

1 0.0 0 Cloud only

2 0.1 0 t_z≈ ∞ (No cloud)

3 0.0 1 VFC (no edge)

4 0.1 1 VFC