Optimized Workload Allocation in Vehicular Edge Computing: A Sequential Game Approach

Abstract

With the development of Vehicle-to-Everything (V2X) communication technologies, Vehicular Edge Computing (VEC) is utilized to speed up the running of vehicular computation workload by deploying VEC servers in close proximity to vehicular terminals. Due to resource limitation of VEC servers, VEC servers are unable to perform a large number of vehicular computation workloads. To improve the performance of VEC servers, we propose a new workload allocation framework where vehicular terminals are divided into Resource Provision Terminals (RPTs) and Resource Demand Terminals (RDTs). In this framework, we design an optimized workload allocation strategy through a sequential Stackelberg game. With the sequential Stackelberg game, a VEC server, RDTs, and RPTs achieve an efficient coordination of the workload allocation. The sequential Stackelberg game is proven to reach two sequential Nash Equilibriums. The simulation results validate the efficiency of the optimized workload allocation strategy.

1 Introduction

With the development of Vehicle-to-Everything (V2X) communication technologies, vehicular networks have gained extensive attention in recent years [1]. Meanwhile, vehicular terminals in vehicular networks can run various new applications such as real-time navigation, interactive gaming and augmented reality. However, vehicular terminals have relatively limited resources due to the physical size constraint. Therefore, it is difficult for vehicular terminals to support real-time and low-latency applications.

In order to meet the requirement of resource-constraint vehicular terminals, Vehicular Edge Computing (VEC) was proposed for vehicular network. VEC is similar to the concept of vehicular fog computing which has been proposed in [2]. VEC locally deploys light-weight cloud servers in close proximity to vehicular terminals. Therefore, vehicular terminals can get realtime interaction and low delay services from VEC servers. Due to resource limitation of VEC servers, VEC servers are unable to perform a large number of vehicular computation workloads [3]. Thus, an optimized workload allocation strategy is essential for a VEC server in vehicular network.

Many researchers engaged in studying the efficient workload allocation strategies. In [3], the authors studied delay constrained offloading for vehicular edge computing in cloud-enabled vehicular networks and designed an efficient computation offloading scheme with a contract theoretic approach. In [4], the authors proposed to combine the vehicular cloud with the infrastructure-based cloud to expand the current available resources for task requests from smartphones, and designed an algorithm to select the suitable cloud service provider to perform the requested task. In [5], the authors proposed a non-cooperation matrix game to balance the workload of multiple local servers for vehicular terminals. In [6], the authors used Semi-Markov Decision Process method to optimize computation resource allocation scheme in vehicular cloud computing.

Vehicular terminals, having idle computation resources, are normally distributed within the coverage of the VEC server. However, few work has considered utilizing idle computation resources of vehicular terminals as the compensation of the VEC server. In addition, the mobility of vehicular terminals has been ignored in those work. In this paper, we propose a new workload allocation framework in vehicular network. The main contributions of this paper are summarized as follows.

• We propose a new workload allocation framework. In this framework, vehicular terminals are divided into Resource Provision Terminals (RPTs) and Resource Demand Terminals (RDTs). We design an optimized workload allocation strategy for the combination of RPTs, RDTs, and a VEC server.

• We elaborately use a sequential Stackelberg game to analyze and solve the optimized workload allocation. With the sequential Stackelberg game, the VEC server, RPTs and RDTs can maximize their utilities, respectively.

• The sequential Stackelberg game is proven to reach two unique sequential Nash Equilibriums. We propose a sequential algorithm to find out the unique solution for the Nash Equilibriums.

The rest of this paper is organized as follows. System model is introduced in Sect. 2. Problem formulation is presented in Sect. 3. We present the workload allocation strategy and propose a sequential algorithm for the sequential Stackelberg game in Sect. 4. The simulation results are presented in Sect. 5. We conclude the paper in Sect. 6.

2 System Model

Figure 1 shows the new workload allocation framework. The framework consists of a VEC server and vehicular terminals within the communication radius of the VEC server. In one cycle, when vehicular terminals are executing real-time and low-latency applications, they become Resource Demand Terminals (RDTs) who require computation resources for computation services. We denote N as the set of RDTs. When vehicular terminals are under low-loaded condition, they become Resource Provision Terminals (RPTs) who have idle computation resources. We denote M as the set of RPTs. We denote K as the set of total vehicular terminals. The roles of the RDTs and RPTs may be converted under different conditions $(K=N+M)$.

Fig. 1.

The workload allocation framework.

RDT $n \in N$ wants to purchase computation amount $x_n$ from the VEC server. The unit price charged by the VEC server for computation resource is denoted as $p_n$. Taking the payment into consideration, each RDT adjusts its required computation amount. After collecting the required computation amount from RDTs, the VEC server adjusts the unit price for its own maximum utility. Finally, the VEC server and RDTs reach a coordination with mutually satisfactory unit price and computation amount. Further, to improve the performance of the VEC server, the VEC server offers an incentive $R_0$ to recruit idle computation resources from M to serve RDTs. The computation amount that the RPT $m \in M$ provides is denoted as $y_m$. Considering the cost and obtained incentive, each RPT adjusts its offered computation amount. After collecting the offered computation amount from RPTs, the VEC server adjusts the incentive. Finally, the VEC server and RPTs reach a coordination with mutually satisfactory incentives and computation amount.

3 Problem Formulation

3.1 Utilities of RDTs and RPTs

The satisfaction function monotonically increases on ${x_n}$. Therefore, we define the satisfaction function of RDT n as ${\varphi _n}\log ({x_n}\,+\,1\,-\,x_n^{\min })$, where ${\varphi _n}$ is a parameter and $x_n^{min}$ is the minimum demand computation amount. The cost of RDT n is the payment to the VEC server, which is given by ${p_n}{x_n}$. Therefore, the utility of RDT n is denoted as

$$\begin{aligned} {u_n} = {\varphi _n}\log ({x_n} + 1 - x_n^{\min }) - {p_n}{x_n}. \end{aligned}$$

(1)

Following the principle of proportional sharing, the incentive amount of RPT m is proportional to its offered computation amount. For convenience, the incentive of RPT m is given by $\frac{{{y_m}}}{{\sum \limits _{m \in M} {{y_m}} }}R_0$. Therefore, the utility of RPT m is denoted as

$$\begin{aligned} {u_m} = \frac{{{y_m}}}{{\sum \limits _{m \in M} {{y_m}} }}R_0 - {e_m}{y_m}, \end{aligned}$$

(2)

where $e_m$ is unit energy consumption. According to the realistic measurements in [7, 8], we can set ${e_m} = {10^{ - 11}}{\left( {{s_m}} \right) ^2}$, where $s_m$ is computation capability of RPT m.

3.2 Utility of VEC Server

The total cost includes the computation energy consumption and transmission energy consumption of the VEC server.

Firstly, the VEC server serves RDTs with computation amount $\sum \limits _{n \in N} {{x_n}}$. To reduce the energy consumption, the VEC server pays $R_0$ to recruit computation amount $\sum \limits _{m \in k} {{y_m}}$ from RPTs. From [9], the computation energy consumption of the VEC server is denoted as ${c_0} ={\sigma _0}{\left( {{z_0}} \right) ^2} + {\eta _0}{z_0} + {\alpha _0}$, where ${z_0}={\sum \limits _{n \in N} {{x_n}} - \sum \limits _{m \in k} {{y_m}} }$. It is provided by the VEC server.

Secondly, the transmission energy consumption of the VEC server is related to the mobility of RPTs. From [4, 10], we know that the wireless channel would fade when RPT m is driving at high speed. When the speed of RPT m is less than a threshold speed, the bandwidth resource of m is $B_m^{in}$. When the speed of RPT m exceeds the threshold speed, the fading rate of RPT m is proportional to its speed and denoted as $r_m=wv_m$, where w is a constant factor. Therefore, the bandwidth resources consumed by RPT m are denoted as $B_m = B_m^{in}+{\int \limits }r_mdt$, where t is the residence time of RPT m within the communication coverage of the VEC server. From [11], the transmission rate of RPT m can be obtained by $R_m = B_mlog_2(1 + \frac{{P_m}{d_m}^{-\eta }{|h_0|}^2}{N_0})$, where ${\eta }$ is a parameter and ${d_m}$ is the average distance between the VEC server and RPT m. $P_m$ is the transmit power of the VEC server. $h_0$ is the complex Gaussian channel coefficient that follows the complex normal distribution CN(0, 1). $N_0$ is the additive white Gaussian noise (AWGN) at the RPT receivers. Therefore, the transmission energy consumption is denoted by ${q_m} =\frac{{{y_m}}}{{{R_m}}}{P_m}$. The utility of the VEC server is denoted as

$$\begin{aligned} {u_0} = \sum \limits _{n \in N} {{p_n}{x_n}} - {c_0}-R_0-{\beta _0}\sum \limits _{m \in M} {{q_m}}, \end{aligned}$$

(3)

where ${\beta _0}$ is unit cost per energy consumption.

All the RPTs, the VEC server, and the RDTs are assumed to be rational and want to make multilevel independent decision to maximize their utilities. It is impossible that the utilities of three-party are satisfied simultaneously, due to the heterogenous framework of the workload allocation. A sequential stackelberg game studies the sequential decision of the players. Therefore, we model the sequential decision as the sequential stackelberg game [12]. The problem is formulated to

$$\begin{aligned}&\mathop {\max }\limits _{{R_0}} ({u_0}),\end{aligned}$$

(4)

$$\begin{aligned}&s.t. \mathop {\max }\limits _{{x_n} \in X} ({u_n}\left| {{p_n}}, \right. {R_0}), \end{aligned}$$

(5)

$$\begin{aligned}&\, \, \, \, \, \,\mathop {\max }\limits _{{y_m} \in Y} ({u_m}\left| {{R_0}} \right) . \end{aligned}$$

(6)

The optimal decisions of the three-party including the VEC server, the RDTs and the RPTs are analyzed based on their utilities. In the first stage, the VEC server is the leader and the RDTs are the followers. Their optimal decisions are charged prices and requested computation amount respectively. In the second stage, the VEC server is the leader and the RPTs are followers. Their optimal decisions are optimal incentives and offered computation amount.

4 Solution and Algorithm

In this section, we use the backward induction method to prove the existence and uniqueness of the sequential Nash Equilibriums for problem (6). We propose a sequential algorithm for the sequential Stackelberg game.

4.1 Stackelberg Equilibrium Solution

4.1.1 Nash Equilibrium Between VEC Server and RDTs

Theorem 1

A unique Nash Equilibrium exists between the RPTs and the VEC server.

Proof:

by taking the derivative of the utility function $u_n$ with respect to $x_n$, we obtain

$$\begin{aligned} \frac{{{d^2}{u_n}}}{{d{x_n}^2}} = - \frac{{{\varphi _n}}}{{{{\left( {{x_n} + 1 - x_n^{\min }} \right) }^2}}}<0. \end{aligned}$$

(7)

Clearly, the utility function $u_n$ of n is concave function, which indicates that the maximum value of the utility function exists. Using first order optimality condition $\frac{{d{u_n}}}{{d{x_n}}}=0$, we get the optimal computation amount ${x_n^{*}} = \frac{{{\varphi _n}}}{{{p_n}}}\,+\,x_n^{\min }\,-\,1$.

From the above equation, we know the relationship between the price and the optimal computation amount. We derivative the optimal price, denoted as ${p_n^{*}} = \frac{{{\varphi _n}}}{{{x_n} + 1 - x_n^{\min }}}$, based on the interaction between RDT n and the VEC server. We substitute $p_n^{*}$ into Eq. (3) and get

$$\begin{aligned} {u_0} = \sum \limits _{n \in N} {\frac{{{\varphi _n}}}{{{x_n} + 1 - x_n^{\min }}}{x_n}}-c_0. \end{aligned}$$

(8)

The second derivative of the function can be obtained as

$$\begin{aligned} \frac{{{\partial ^2}{u_0}}}{{\partial {x_n}^2}} = - 2\frac{{{\varphi _n}}}{{{{\left( {{x_n} + 1 - x_n^{\min }} \right) }^3}}} - 2{\beta _0}{\sigma _0} < 0\ . \end{aligned}$$

(9)

Clearly, the second-order derivative of the utility of the VEC server is negative and strictly convex function. Therefore a unique Nash Equilibrium exists in the game.    $\blacksquare$

4.1.2 Nash Equilibrium Between VEC Server and RPTs

In the stage, the VEC server is the leader and the RPTs are the followers. We prove that it exists an Nash Equilibrium. The Nash Equilibrium is unique.

Definition 1

When the other followers’ strategies $\varvec{y_{-m}}$ are given, the best response function ${\varvec{f_m}}({y_m},\varvec{y_{-m}})$ of RPT can be defined by

$$\begin{aligned} {\varvec{f_m}}({y_m},\varvec{y_{-m}})= \arg \max {u_m}{({y_m},\varvec{y_{-m}})}. \end{aligned}$$

(10)

Theorem 2

(Existence). An Nash Equilibrium exists among RPTs.

Proof:

give the second order condition of the RPT’s utility ${u_m}({y_m},\varvec{y_{-m}})$ as

$$\begin{aligned} \frac{{{\partial ^2}{u_m}({y_m},\varvec{y_{-m}})}}{{\partial {y_m}^2}} = - 2{\left( {\frac{1}{{{y_m} + \sum \limits _{j \in k\backslash m} {{y_j}} }}} \right) ^3}{R_0}<0. \end{aligned}$$

(11)

Since the second-order derivative of ${u_m}$ is negative, the utility ${u_m}$ is a strictly convex function in ${y_m}$. Therefore an Nash Equilibrium exists in the game.    $\blacksquare$

The Nash Equilibrium is unique. The key of the Nash Equilibrium is to prove that the best response function of each RPT is a standard function [14].

Definition 2

$\varvec{f(\varvec{p})}=(\varvec{f_1(\varvec{p})},\varvec{f_2(\varvec{p})},...,\varvec{f_M(\varvec{p}))}$, where $\varvec{p}=(p_1,...p_M)$. $\varvec{f(\varvec{p})}$ is said to be standard if it satisfies the following properties for all $\varvec{p}\ge 0$

• Positivity: $\varvec{f(\varvec{p})} > 0$.

• Monotonicity: for all $\varvec{p}$ and $\varvec{p}'$, if $\varvec{p} > \varvec{p}'$ then $\varvec{f(\varvec{p})} >\varvec{f(\varvec{p}')}$.

• Scalability: for all $\mu > 1$, ${\mu }\varvec{f(\varvec{p})} \ge \varvec{f(\varvec{{\mu }p})}$.

Theorem 3

The best response function ${\varvec{f_m}}({y_m},\varvec{y_{-m}})$ of RPT m is a standard function of $\varvec{y_{-m}}$.

Proof:

from the Theorem 1, we know that the utility function ${u_0}({y_m},\varvec{y_{-m}})$ is strictly concave. Let $\frac{{\partial {u_0}}}{{\partial {x_i}}} =0$, we get the best function ${\varvec{f_m}}({y_m},\varvec{y_{-m}})$ of m,

$$\begin{aligned} {\varvec{f_m}}({y_m},\varvec{y_{-m}})= \left\{ \begin{array}{l} \sqrt{\frac{{\sum \limits _{i \in k/m} {{y_i}} {R_0}}}{{e_m}}} - \sum \limits _{i \in k/m} {{y_m}}, \\ 0,{R_0} \le e_i\sum \limits _{i \in k/m} {{y_m}}. \end{array} \right. \end{aligned}$$

(12)

Next, we prove that the best function ${\varvec{f_m}}({y_m},\varvec{y_{-m}})$ satisfies the three properties of a standard function.

$\bullet$ Positivity: when ${y_m}>0$ and ${R_0} \le e_i\sum \limits _{i \in k/m} {{y_i}}$ are satisfied, we get

$$\begin{aligned} {\varvec{f_m}}({y_m},\varvec{y_{-m}})=\sqrt{\frac{{\sum \limits _{i \in k/m} {{x_i}} {R_0}}}{{{e_m}}}} - \sum \limits _{i \in k/m} {{x_i}}>0. \end{aligned}$$

(13)

$\bullet$ Monotonicity: given the first order condition of $\varvec{{f_m}}({y_m},\varvec{y_{-m}})$ with respect to ${y_i}$, we obtain

$$\begin{aligned} \frac{{\partial {f_m}({y_m},\varvec{y_{-m}})}}{{\partial {y_i}}} = \sqrt{\frac{{\sum \limits _{i \in k/m} {{y_i}} {R_0}}}{{4e{}_m}}} - 1>0. \end{aligned}$$

(14)

We get the constrain $\sum \limits _{i \in k/m} {{y_i}} > \frac{{4E_m^{consu}}}{{{R_0}}}$. When it is satisfied, the monotonicity is satisfied.

$\bullet$ Scalability: based on (12), we obtain

$$\begin{aligned} \lambda \varvec{{f_m}}({y_m},\varvec{y_{-m}}) - \varvec{{f_m}}(\lambda {y_m},\varvec{y_{-m}}) =(\lambda - \sqrt{\lambda })\sqrt{\frac{{{R_0}\sum \limits _{i \in k/m} {{y_i}} }}{{e_m}}}. \end{aligned}$$

(15)

For $\forall \lambda > 1$, we have $(\lambda - \sqrt{\lambda }) > 0$. Therefore, it is positive.

Based on Eq. (12), we get the total amount computation of the RPTs as $\sum \limits _{m \in k} {{y_m}} = \frac{{(k - 1)}}{{\sum \limits _{m \in k} {e_m} }}{R_0}$ . We substitute $\sum \limits _{m \in k} {{y_m}}$ into Eq. (6). The problem can be written as

$$\begin{aligned}&\mathop {\min }\limits _{} ({c_1}),\end{aligned}$$

(16)

$$\begin{aligned}&s.t. k > 1,\end{aligned}$$

(17)

$$\begin{aligned}&\, \, \, \, \, \,{R_0} > 0,\end{aligned}$$

(18)

$$\begin{aligned}&\, \, \, \, \, {\beta _0},{\sigma _0},{\eta _0},{\alpha _0} > 0, \end{aligned}$$

(19)

where

$$\begin{aligned} {\begin{matrix} &{}{c_1} = {R_0} + {\beta _0}{\sigma _0}{(\sum \limits _{n \in N} {{x_n}} - \frac{{(k - 1)}}{{\sum \limits _{m \in k} {e_m} }}{R_0})^2}+ {\beta _0}{\alpha _0}\\ &{}+ {\beta _0}{\eta _0}(\sum \limits _{n \in N} {{x_n}} - \frac{{(k - 1)}}{{\sum \limits _{m \in k} {e_m} }}{R_0}) +\frac{{(k - 1){R_0}}}{{\sum \limits _{m \in k} {{e_m}} }}\sum \limits _{m \in k} {\frac{{{P_m}}}{{{R_m}}}}.\\ \end{matrix}} \end{aligned}$$

(20)

We give the second order condition and get $\frac{{{\partial ^2}{c_1}}}{{\partial {R_0}^2}} =2{A^2}{\sigma _0}{\beta _0}>0$ , where $A = \frac{{k - 1}}{{\sum \limits _{m \in k} {{e_m}} }}$. Clearly, the cost of the VEC server is convex, which indicates that the minimum value of this function exists. Therefore, given first order optimality condition $\frac{{d{c_1}}}{{d{R_0}}}=0$, we get the optimal $R_0^{*}$

$$\begin{aligned} {R_0^{*}} =\frac{{2A\sum \limits _{n \in N} {{x_n}} + {\beta _0}{\eta _0}A - 1 - A\sum \limits _{m \in k} {\frac{{{P_m}}}{{{R_m}}}} }}{{2{A^2}{\sigma _0}{\beta _0}}}. \end{aligned}$$

(21)

4.2 Sequential Distributed Algorithm

To reach two sequential Nash Equilibrium, we propose a sequential algorithm. Details are given in Algorithm 1.

5 Numerical Results

We evaluate the performance of the proposed workload allocation strategy by simulations. The VEC server is assumed to be located in (500, 500) (in m). We use the following parameter settings as that in [4, 5, 7, 9]: $\beta \in [2,50]$, $\sigma =2$, $\eta \in (0,\frac{3}{2})$, $\alpha \in [1,10]$, $\varphi \in [10,20]$, $v \in [1,10]$, $s_m=50$ to 100 GZ, $B_m=6$ to 10 Mbps.

Figure 2 shows the total energy consumption of the VEC server with respective to the number of computation resource. The energy consumption of the VEC server increases as the number of computation resource increases. The energy consumption of the VEC server by our proposed workload allocation strategy consumes less energy for the same computation resource. It is because the VEC server utilizes idle computation resource of the RPTs to reduce its energy consumption. Figure 3 shows the cost of the VEC server in computation resources for two values of $\beta _0$. The VEC server has higher cost with larger $\beta _0$. With our proposed strategy, the VEC server consumes lower cost in computation resources. It is because the VEC server consumes lower cost and cooperates with the RPTs. Figure 4 shows the impact of the speed of RPTs on the cost of the VEC server. The cost of the VEC server n increases as the speed of RPTs increases. It is because that RPTs provide less computation resources as the cost of RPTs increases.

Fig. 2.

Impact of computation resources on the VEC server

Fig. 3.

Cost of the VEC server with different ${\beta _0}$

Fig. 4.

Impact of the speed of RPTs on the VEC server.

6 Conclusion

In this paper, we propose a workload allocation framework in VEC. In the framework, RPTs are recruited to improve the performance of computation services which serve the RDTs. An optimized workload allocation strategy is proposed to maximize the utilities of the VEC server, the RPTs and the RDTs. We use a sequential Stackelberg game to design the strategy. The sequential Stackelberg game is proven to reach two sequential Nash Equilibriums. The simulations validate the efficiency of the optimized workload allocation strategy.