Parallel label propagation algorithm based on weight and random walk

1.   Introduction

According to Ericsson's "Mobile Market Report", it is predicted that by the end of 2025, there will be more than 2.8 billion 5G subscribers worldwide. 5G will cover nearly 65% of the world's population, and 5G networks will carry 45% of data traffic. Among that, smartphones will account for 86%, and the world will usher in the Internet era of the explosive growth of network data and information. The increasing popularity of 5G networks has witnessed the rapid development of the Internet of Things ^[1], which has stimulated the emergence of various forms of new applications, such as AR, VR, autonomous driving, smart cities, telemedicine and other technical fields. These application scenarios require a higher bandwidth rate and lower system energy consumption and computing delay ^[2,3], while the centralized processing mode adopted by the mobile cloud computing model is far from the terminal devices and cannot meet the daily needs of users ^[4,5]. Therefore, mobile edge computing (MEC) technology has emerged.

Mobile edge computing ^[6] is considered one of the core technologies in developing modern communication networks and 5G technology. MEC performs operations such as computing processing and resource allocation on edge nodes by introducing computing data to the edge of the mobile network. As a research hotspot of MEC, resource allocation mainly studies the problem of where to unload computing tasks ^[7]. In the MEC network scenario of computing-intensive applications, tasks need to be reasonably allocated to maximize the utilization rate of each computing node's storage, CPU and other resources. Therefore, effective resource allocation can not only avoid channel interference between tasks but also increase the calculation rate of tasks, effectively reducing resource occupancy rate and improving resource utilization rate ^[8,9]. Although a large number of excellent works are devoted to the related research of resource allocation in the MEC environment, numerous studies cover resource allocation based on joint computing offload, channel allocation, spectrum allocation, power allocation and other technologies; and most of the optimization objectives are offload delay, system energy consumption or user income. Thus, there is little research on dynamic resource allocation under multi-user and multiple MEC servers. Therefore, this paper studies the dynamic resource allocation problem in the mobile edge environment and proposes a resource allocation optimization method based on comprehensive utility in the MEC (RAOCU). The method mainly includes three parts: job classification based on an improved Naive Bayes algorithm, resource service node classification based on resource utilization and resource allocation based on comprehensive utility. The main, specific contributions of this work are summarized as follows.

1) Aiming at the problem of inaccurate job classification results caused by the underflow of the Naive Bayes algorithm, the Naive Bayes algorithm is optimized. The conditional probability of the job type is obtained according to the established Naive Bayes formula, and then the posterior probability that the running job is a CPU-intensive job and I/O-intensive job under certain conditions is obtained, which improves the Naive Bayes Classifier performance.

2) For resource allocation based on comprehensive utility, by considering the three factors of resource location, task priority and network transmission cost, matching computing resources are assigned to the particular types of jobs, and according to the weighted bipartite graph, the optimal solution of matching job and resource nodes is obtained.

3) The experimental results demonstrate that, compared with other algorithms, the algorithm of this paper can classify job types and resource service nodes more effectively, reduce resource occupancy rate and improve resource utilization rate.

The rest of the paper is organized as follows: Section 2 is the research status, and Section 3 expounds on and analyzes the design of resource optimization methods based on comprehensive utility in an MEC environment, including job classification based on an improved Naive Bayes algorithm, resource service node classification based on resource utilization rate and resource allocation based on comprehensive utility. Section 4 provides a detailed description of the proposed algorithm. Section 5 provides a comparison and analysis of experimental results. Finally, Section 6 summarizes the paper and discusses its development direction.

2.   Related work

Many scholars have conducted relevant research on resource allocation in the MEC environment. Tran et al. ^[10] studied joint task offloading and resource allocation, aiming at maximizing the revenue of user task offloading, and the total revenue of the user is characterized as the weighted sum of task execution delay and energy consumption. Xu et al. ^[11] established a comprehensive model, Zenith, to capture the optimization problem of online resource allocation in the edge cloud. Based on the proposed model, an auction-based resource contract mechanism and a delay scheduling technology to maximize the utility of service providers were proposed. Dab et al. ^[12] proposed a joint task allocation and resource allocation method aiming at minimizing the energy consumption of mobile terminals. This scheme formulated the optimization problem based on integer programming and proposed an enhancement algorithm considering the waiting delay of mobile terminals and data transmission. Jinke et al. ^[13] studied the joint communication and computing resource allocation of multi-user multiple access communication systems, established a function with the delay and energy consumption of mobile devices as the optimization objectives and proposed a resource allocation scheme based on a subgradient algorithm. You et al. ^[14] discussed the resource allocation problem of minimum energy consumption in multi-user multiple access systems, defined the average unloading priority function and described the resource allocation as a convex optimization problem to minimize the weighted sum of system energy consumption under the constraint of calculation execution delay. Sardellitti et al. ^[15] considered a multi-cell mobile edge computing offload system, which jointly allocates radio and computing resources to minimize the total energy consumption of mobile terminals under the constraint of offload delay. Ketyko et al. ^[16] studied the offloading decision with the goal of maximizing the number of service applications and assigning computing nodes by priority. Wang et al. ^[17] used the method of deep learning to allocate resources and proposed a dynamic unloading scheme. Lemaréchal et al. ^[18] proposed a layered MEC deployment architecture when MEC computing resources are limited. Boyd et al. ^[19] proposed three different cloud selection strategies to optimize delay, total cluster energy consumption and energy consumption of each SCeNB in the cluster. Liu et al. ^[20] used the knapsack model to optimize the whole resource allocation and load balancing problem. Jabeen et al. ^[21] proposed an interference management scheme, which allocates communication resources and computing resources under the condition of minimum interference. Avgeris et al. ^[22] proposed an optimal resource allocation framework leveraging the amalgamation of the edge resources. A mechanism based on Markov Random Fields was introduced to allocate redundant workload. To speed up the learning and reduce the resource consumption of the network, Zuo et al. ^[23] formulated a problem of joint transmission time allocation, computing frequency control and user selection. Fan et al. ^[24] modeled the resource allocation and pricing of a cloud/edge computing service provider (CESP) as a mixed-integer programming problem (MIP) with the goal of optimizing the revenue of the CESP, and an efficient resource allocation and pricing algorithm based on iterative greed and search was proposed. AlQerm et al. ^[25] proposed a novel resource allocation model that aimed to maximize the IoT applications' utilities considering multiple applications' priorities and various delay requirements and guaranteed resource allocation fairness. In order to solve the multi-user resource allocation problem, Huang et al. ^[26] adopted a performance-aware resource allocation (PARA) scheme based on a depth deterministic policy gradient (DDPG) to derive the optimal resource allocation strategy. Lin et al. ^[27] formulated the upstream resource allocation as a stratified multi-objective optimization model, adjusting the spectrum and storage allocation between latency-critical and delay-tolerant flows. Zhu et al. ^[28] formulated the virtual resource allocation strategy as an optimization problem that aims to maximize the revenue earned by mobile virtual network operators and proposed a distributed virtual resource allocation algorithm based on the alternating direction method of multipliers. Shabbir et al. ^[29] compared other commonly used algorithms against the health information security at the MCC environment in terms of better performance and auxiliary qualitative security-ensuring measures.

Although the literature mentioned above on resource allocation optimization has made some achievements, in the multi-user and multi-MEC server environment, the classification of resource nodes and the low utilization rate of resources in resource allocation are seldom considered. Therefore, this paper proposes a resource optimization algorithm based on comprehensive utility in the MEC environment, and the dynamic resource allocation problem in the mobile edge environment is studied.

3.   Design of resource allocation optimization algorithm based on comprehensive utility in MEC environment

The resource allocation optimization method based on comprehensive utility in the MEC environment proposed in this paper mainly includes job classification based on an improved Naive Bayesian algorithm, classification of resource service nodes based on resource utilization rate and resource allocation based on comprehensive utility. The main parameters involved and their meanings are shown in Table 1.

3.1.   Job classification based on improved Naive Bayesian algorithm

In the edge computing environment, by deploying edge computing nodes at the edge of the network, various mobile applications and new application scenarios can provide users with various services, increasing the number and types of jobs that edge computing nodes need to handle exponentially. Therefore, different types of jobs will generate different workloads on the cluster, including I/O-bound or CPU-bound workloads. In the research of job classification, jobs are mostly divided into I/O type or CPU type. I/O-intensive jobs are allocated to I/O type resources. CPU-intensive jobs are allocated to CPU type resources to achieve the load balance of cluster nodes and reduce the response delay of task allocation in the edge environment. Job classification based on job priority or resource requirements will also affect job resource allocation for most applications. The job controller uses the priority and the load indexes to establish the Bayes' theorem's conditional probability.

The jobs are divided into I/O type or CPU type according to the characteristics of the jobs. The ratio of input data (MID) to output data (MOD) is represented as $\rho {\text{ = }}MOD/MID$, MCD denotes Map processing data, SOD indicates the output result of Shuffle, RID shows the output data of Reduce, $MTCT$ represents the completion time of the Map task, $DIOR$ illustrates the I/O rate of the disk, and $N$ illustrates the number of tasks. Therefore, I/O type and CPU type tasks can be defined as follows:

If the sum of the resource utilization rates of the five stages of MapReduce (MID, MOD, MCD, SOD and RID) is greater than or equal to the disk I/O utilization rate, the job is a CPU type job; otherwise, it is an I/O type of job. According to Eqs (1) and (2), it can be seen that the categories that affect the job include input data (MID), output data (MOD), Shuffle output result (SOD), Reduce output data (RID) and $\rho$ factors, and among them, the values of some factors need to be determined after the job is executed. This paper needs to classify jobs before they are executed, so Eqs (1) and (2) cannot be used to directly judge the types of work. Therefore, this paper uses the Bayesian classifier to classify jobs in Hadoop. According to job-related features and node characteristics, the Bayesian classifier is adopted, and its input data is expressed as job characteristics and node characteristics. According to job characteristics and node characteristics, the Bayesian classifier divides jobs into I/O-intensive and CPU-intensive jobs.

Equations (3) and (4) calculate the conditional probability that the running job is I/O-intensive and CPU-intensive under certain specific conditions.

$jo{b_z}$ represents job $z$, and ${{\rm X}_n}$ indicates job characteristics and node characteristics, where it is assumed that each ${{\rm X}_n}$ is independent of each other. Taking CPU-intensive jobs as an example, $P\left({B|A} \right) = P\left({AB} \right)/P\left(A \right)$ can be acquired according to the Bayesian formula, as shown in Eq (5).

Equation (6) can be derived from Eq (5).

Since there is no correlation between $P\left({{{\rm X}_1}, {{\rm X}_2}, \ldots, {{\rm X}_n}} \right)$ and job attributes, it can be ignored. Thus, Eq (6) can be converted to Eq (7).

As shown in Eqs (5)-(7), the posterior probability $P\left({jo{b_{\text{z}}}{\text{ = }}CPU|{{\rm X}_1}, {{\rm X}_2}, \ldots, {{\rm X}_n}} \right)$ can be obtained by being given $jo{b_{\text{z}}}{\text{ = }}CPU$ under the premise of the conditional independence assumption, which is expressed as Eq (8).

Owing to the value of $P\left({{{\rm X}_1}, {{\rm X}_2}, \ldots, {{\rm X}_n}} \right)$ being constant, it is only necessary to calculate the relative size of the numerator in Eq (8), which can be expressed as Eq (9).

Based on Eq (9), when the posterior probability $P\left({jo{b_{\text{z}}}{\text{ = }}CPU|{{\rm X}_1}, {{\rm X}_2}, \ldots, {{\rm X}_n}} \right)$ is contrasted, more conditional probabilities are required for multiplication calculation. At the same time, it is likely that underflow will occur, which will lead to the abnormal execution of the next command, thus leading to the uncertainty result of a posterior probability $P\left({jo{b_{\text{z}}}{\text{ = }}CPU|{{\rm X}_1}, {{\rm X}_2}, \ldots, {{\rm X}_n}} \right)$, thereby affecting the judgment of job type, influencing the feasibility of the algorithm and reducing the performance of the algorithm. Consequently, this paper optimizes according to the disadvantages of the Naive Bayes algorithm, and Eq (9) is transformed into the following:

It can be seen from Eq (10) that there may be a value of 0 on the right side of the equation, which will have a certain impact on the job classification result, thus affecting the performance of the algorithm. The Laplace smoothing technique can effectively avoid the situation where the right side of the equation is 0, and we can add 1 to the right side of the equation. Therefore, the class conditional probability of I/O-intensive jobs and CPU-intensive jobs can be expressed as

In Eq (11), ${T_k}$ denotes the number of occurrences of feature items in I/O-intensive jobs and CPU-intensive jobs in the total workload, the total number of all feature items of a job type, and ${T_c}$ illustrates the smoothing factor, the total number of feature items of all job types. Therefore, the posterior probability for the two types of operations can be formulated as

The job type is judged according to the established Naive Bayes posterior probability. Therefore, when $P\left({jo{b_z} = CPU{\text{|}}{{\rm X}_1}, \ldots, {{\rm X}_n}} \right) > P\left({jo{b_z} = I/O{\text{|}}{{\rm X}_1}, \ldots, {{\rm X}_n}} \right)$, the job is CPU-intensive, and when $P\left({jo{b_z} = I/O{\text{|}}{{\rm X}_1}, \ldots, {{\rm X}_n}} \right) > P\left({jo{b_z} = CPU{\text{|}}{{\rm X}_1}, \ldots, {{\rm X}_n}} \right)$, the job is I/O-intensive. The job classification algorithm based on improved Naive Bayes is shown in Algorithm 4.1.

3.2.   Resource service nodes are classified based on resource utilization

In the problem of resource allocation in the edge cloud environment, not only the types of jobs and the arrival times and regularity of jobs should be considered, but also the requirements for resource types of jobs should be considered. Therefore, according to the resource utilization rates of I/O and CPU, the resource service nodes are divided into I/O main resource and CPU main resource to make full use of the system resources.

TaskTracker sends heartbeat information to JobTracker within a specific time to indicate that the node is running. Therefore, I/O and CPU usages on TaskTracker are captured by adding specific indicators. According to the heartbeat message received from TaskTracker, JobTracker obtains the resource utilization rate information of the node. There, I/O and CPU resource utilization rates in TaskTracker are achieved as follows:

In Eq (14), $T_{CPU}^{cumulative}$ shows the actual CPU cycle used to execute the job, the cumulative CPU cycle, $T_{CPU}^{last}$ indicates the last cumulative CPU cycle, $T_{CPU}^{current}$ denotes the current CPU cycle, and the value of $T_{CPU}^{lastcurrent}$ manifests the historical CPU cycle and the CPU cycle at the last heartbeat. $U_{i/o}^{read}$ indicates the cumulative read amount of the job in I/O, and $U_{i/o}^{write}$ shows the cumulative output of the job in I/O. When $CP{U_{usage}} > I/{O_{usage}}$, the resource node is the main CPU resource, and when $CP{U_{usage}} \leqslant I/{O_{usage}}$, the resource node is the main I/O resource. The classification algorithm of resource service nodes is shown in Algorithm 4.2.

3.3.   Resource allocation based on comprehensive utility

In this section, resource nodes are calculated for job allocation according to three factors: resource location, task priority and network transmission cost. The optimal solution of job and resource node matching is obtained according to the method of a weighted bipartite graph.

The job is denoted as $z$, each job $z\left({0 \leqslant z \leqslant f} \right)$ is composed of multiple tasks ${l_z}$, and each task is indivisible, independent and non-preemptive. The task ${h_z}$ is illustrated as ${h_z}{\text{ = }}\left({v_h^z, s_h^z} \right)\left({1 \leqslant {h_z} \leqslant {l_z}} \right)$, $v_h^z$ represents the amount of computation required to complete task ${h_z}$, and $s_h^z$ illustrates the memory size required to complete task ${h_z}$. The resource pool set is defined as $j\left({0 \leqslant j \leqslant J} \right)$, and each resource pool is indicated as $j \triangleq \left({{v_j}, {s_j}} \right)$, where ${v_j}$ is the computing power of the CPU, and ${s_j}$ is the memory size of the resource pool $j$. Therefore, the similarity between task ${h_z}$ and resource service node $j$ can be defined as follows. $u_j^{'}$ is the transpose of vector ${u_j}$.

The priority $y\left({{h_z}} \right)$ of task ${h_z}$ is expressed as

In Eq (17), $y\left(z \right)$ represents the priority of job $z$, which is determined by the scheduling priority in the data processing system, $y_h^z$ denotes the priority of resources required by task ${h_z}$, and $\eta$ indicates the weight coefficient. As the value of $y\left({{h_z}} \right)$ increases, the priority of task ${h_z}$ will also increase, and $y_h^z$ is determined by the location of resources required by task ${h_z}$. When the required resources are stored in the memory on the local server, set $y_h^z{\text{ = }}2$. When the demand resources are stored in the disk on the local server $y_h^z{\text{ = 1}}$, and otherwise, $y_h^z{\text{ = }}\frac{1}{{h\left({{l_e}, {l_o}}~ \right)}}$. ${l_e}$ represents the location of the local server, ${l_o}$ illustrates the location of the required resources, and $h\left({{l_e}, {l_o}} \right)$ describes the minimum network distance between the local server and the required resources.

The network transmission cost is illustrated as

In Eq (18), $\delta$ represents the quantity of required content, ${w_t}$ indicates the size of the $t$ -th required content, $h\left({{l_e}, {w_t}} \right)$ manifests the minimum network distance between the local server and the needed content location, and $band\left({{l_e}, {w_t}} \right)$ illustrates the bandwidth between the local server and the required content location. When the demand content is stored on the local server, $h\left({{l_e}, {w_t}} \right){\text{ = }}0$ and $band\left({{l_e}, {w_t}} \right){\text{ = }}1$. Therefore, the job resource matching optimization problem is described as

In Eq (19), for $\pi _{hj}^z \in \left\{ {0, 1} \right\}$, when the $h$ -th task matches the $j$ -th resource pool, $\pi _{hj}^z{\text{ = }}1$; otherwise, $\pi _{hj}^z{\text{ = 0}}$. Since problem $P{\text{1}}$ is a shaping programming problem, that is, an NP hard problem, in order to solve this problem, problem $P{\text{1}}$ is transformed into an optimal matching problem under the condition of a weighted bipartite graph. Consequently, in the weighted bipartite graph, the weight of task ${h_z}$ and resource pool $j$ is composed of their similarities. The weight between task priority and network transmission cost can be depicted as

$\psi \left({{h_z}, j} \right)$ represents the weight between task ${h_z}$ and container ${u_r}$, ${\lambda _1}$ denotes the weight coefficient of similarity, ${\lambda _2}$ illustrates the weight coefficient of task priority, and ${\lambda _3}$ manifests the weight coefficient of network transmission cost.

$P{\text{1}}$ can be reduced to the following programming problem.

When $\sum\nolimits_{z = 1}^f {{l_z}} > j$, $\sum\nolimits_{z = 1}^f {{l_z}} {\text{ - j}}$ virtual resource pools need to be added, so that there is a one-to-one relationship between each task and each resource pool. The weight between each task and the added virtual resource pool is zero. The resource allocation algorithm is based on comprehensive utility, as shown in Algorithm 4.3.

4.   Implementation of resource allocation optimization algorithm based on comprehensive utility in MEC environment

4.1.   Job classification based on improved Naive Bayesian algorithm

The first step is to establish the conditional probability of the job by using Naive Bayes and then calculate the posterior probability of each job type according to the formula. Aiming at the shortcomings of Naive Bayes, the Laplace Smoothing technique is used to optimize the Naive Bayes algorithm. Finally, the posterior probability of the job to be classified is computed, and the job type is judged according to the acquired posterior probability of the job type. The core pseudo-code of job classification based on the improved Naive Bayesian algorithm is shown in Algorithm 1.

4.2.   Resource service nodes are classified based on resource utilization

According to the resource utilization rate, the resource pool is divided into CPU main resources and I/O main resources. The core pseudo-code for classifying resource service nodes is shown in Algorithm 2.

4.3.   Resource allocation optimization based on comprehensive utility

It is necessary to divide corresponding types of jobs into corresponding resource pools. This paper formulates a resource allocation algorithm based on comprehensive utility by calculating the similarity between tasks and resource pools, task priority and network transmission overhead of required resources. The core pseudo-code is exhibited in Algorithm 3.

The flow chart of the resource allocation optimization algorithm based on comprehensive utility in the MEC environment is shown in Figure 1.

5.   Performance evaluation

5.1.   Experimental environment and configuration

5.1.1.   Environment settings

1) Experimental environment

This experimental environment is ubuntu-18.10-desktop-amd64, JDK1.8.0_11. Use the virtual machine software VMware Workstation 15.0.4 and SSH tools OpenSSH-server and OpenSSH-client. Build cloud computing framework Hadoop-3.1.2. The Linux system cloning tool is Clonezilla. The integrated development environment is Linux Eclipse 4.5.0. The specific experimental test environment and cluster node configuration in this study are indicated in Figure 2 and Table 2.

In order to simulate the actual scene of the experiment, the edge server is built with nine mobile terminals with different configurations. The remote cloud uses the Aliyun instance to build the environment. Edge servers and remote cloud communicate via VPN. Table 2 shows the configuration of the cluster node of the Edge Server.

2) Experimental data

The experiment data comes from the dataset of Stanford Network ^[30] (SNAP), including the online social network set, communication network set, Amazon network set, and other large network data sets. The range is [2,40] G, the size of the experimental data set is about 40 GB, the size of each segmented data is 128 MB, and the range of the map task is [14,300]. Therefore, the scale of the dataset executed by the benchmark program in this experiment is shown in Table 3.

5.1.2.   Test cases and parameter settings

The experiment uses different job streams as the test cases ^[31], namely Wordcount, Kmeans, and Teragen. Since there are not many data calculation operations in the map and reduced phases of WordCount, this type of job can be classified as I/O-intensive. Kmeans involves more data computing operations in the Map and Reduce phases and does not have too many intermediate data read and write operations, so this type of job is classified as CPU-intensive. The data generated by Teragen is mostly used for subsequent programs, so this type of job can be classified as I/O intensive. The test case related data description of this experiment is shown in Table 4.

5.2.   Experimental results and analysis

In order to verify the effectiveness and stability of the algorithm proposed in this paper, the average job execution time and hit rate are used as the evaluation indicators of algorithm performance.

5.2.1.   Influence of job number on algorithm performance

This group of experiments analyzes the average job execution time of the same job running under FIFO ^[32], FAIR ^[33], COSHH ^[34] and RAOCU. This experiment sets four job streams for each type of job, each job stream has 35 jobs, and a total of 140 jobs are submitted. Jobs of WorkCount, Kmeans and Teragen types are executed eight times each with job counts of 20, 60, 100 and 140, respectively. The average execution times of jobs under different numbers of jobs are shown in Figure 3. The job hit rates under different job numbers are shown in Figure 4.

Figure 3 shows that when the number of jobs is 20, the average execution times of FIFO, FAIR, COSHH and RAOCU have little distinction, and they can all be stable at about 350 s. With increasing job data, COSHH can achieve a lower average job execution delay than FIFO and FAIR. The average job execution delay of the algorithm in this paper can show a lower trend than the other three algorithms. As the scale of job data increases, some jobs have priority implemented, while some jobs are only part of the execution jobs. For the jobs with priority execution, the Map task collects the job execution information and classifies the jobs, and then the remaining job allocates resources according to the corresponding labels. Because the RAOCU uses an improved Naive Bayes classification algorithm to classify the job, it can effectively speed up the classification of job data and reduce the average job execution time.

Figure 4 shows that with the increase in the number of tasks, the job hit rate of each algorithm also increases. For example, under the number of 140 jobs, the job hit rate of RAOCU is about 46.3% higher than that of 20 tasks, so the job hit rate of RAOCU is higher than those of the FIFO, FAIR and COSHH algorithms. In the case of 140 jobs, the RAOCU hit rate is about 25.9% higher than FIFO, 12.96% higher than FAIR and 11.1% higher than COSHH.

5.2.2.   Influence of available storage space on algorithm performance under different resource service nodes

Figure 5 describes the average execution times of jobs with available storage space under different resource service nodes. Figure 6 illustrates the hit rates of job resources under different storage spaces.

As shown in Figure 5, as the available storage space increases, the average job execution time for each algorithm decreases. When the size of the storage space under the resource service node increases from 20 to 50, the average job execution time of RAOCU is reduced by about 53.3%. Under the same available storage space, the average job execution time of the algorithm in this paper shows a lower trend than the other three algorithms. The resource location considered in RAOCU establishes the relationship between the task and the resource pool according to the similarity, which can be matched by the task content and effectively reduce the average execution time of the job.

As shown in Figure 6, with the increase of storage space under the resource service node, the job hit rate of each algorithm also rises. When the size of the storage space under the resource service node changes from 20 to 50, the job hit rate of RAOCU increases by about 61.5%, which is higher than those of the FIFO, FAIR and COSHH algorithms. When the available storage space is 50, RAOCU's job hit rate is about 31.2% higher than FIFO's, 26% higher than FAIR's and 14.3% higher than COSHH's. With the same available storage space, the job hit rates of the other three algorithms are lower than that of the RAOCU algorithm. As the available storage space under the resource service node increases, the edge nodes contain more content. In resource matching, RAOCU considers three factors: resource location, task priority and network transmission cost, thus improving the hit rate of each algorithm.

5.2.3.   Influence of the number of resource service nodes on algorithm performance

Figure 7 depicts the influence of the number of resource service nodes on the average job execution times. Figure 8 manifests the influence of the number of resource service nodes on the job hit rates.

As shown in Figure 7, when the number of resource service nodes is between 20 and 100, the FIFO and FAIR algorithms fluctuate greatly. The average task execution delay of FIFO decreases first and then increases with the increase of resource service nodes. FAIR's average task execution delay first decreases and gradually increases with the number of resource service nodes. COSHH's performance shows a trend of first declining and then stabilizing. When it is stable, RAOCU shows a lower average job response time than COSHH. When the number of resource service nodes is about 52, the average job response time of RAOCU is the lowest.

It can be seen from Figure 8 that with the increasing number of resource service nodes, the job hit rates of FIFO and FAIR algorithms are in a relatively stable trend. Compared with FIFO and FAIR, COSHH and RAOCU show a convex trend with the increase in the number of resource service nodes. With the increase of resource service nodes, the job hit rates first show an upward trend and then gradually decrease. RAOCU considers the classification of jobs and the classification of resource service nodes. When the number of resource service nodes is too low, the matching between jobs and corresponding resource service nodes cannot be well completed, so the job hit rate is low. When the number of resource service nodes exceeds a specific number, the job will be matched to resource service nodes of the same type. Hence, RAOCU improves the utilization rate of resource nodes to a certain extent and has higher optimization performance than FIFO, FAIR and COSHH.

5.3.   Experiment summary

By analyzing the above three sets of experiments, the following conclusions can be drawn: 1) The number of jobs impacts the resource optimization algorithm. As the number of jobs increases, the average task execution delay and the job hit rate also increase. 2) The available storage space under different resource service nodes will affect the resource allocation optimization algorithm. As the available storage space increases, the average task execution delay decreases, and the job hit rate gradually increases. 3) The number of resource service nodes influences the resource optimization algorithm. As the number of resource service nodes increases, the average task execution time increases steadily, while the job hit rate increases first and then gradually decreases.

6.   Conclusions and future work

This paper studies the resource allocation optimization method based on comprehensive utility in multi-user and multiple MEC environments. The algorithm mainly includes job classification based on an improved Naive Bayesian algorithm, resource service node classification based on resource utilization rate and resource allocation based on comprehensive utility. Finally, the simulation results show that the RAOCU algorithm can reduce the resource occupancy rate and improve the resource utilization rate. At the same time, it has good performance in the average job execution delay and job hit rate. However, when classifying the computing tasks requested by the mobile terminal, this work does not consider the deadline and computing cost of the job. In the classification method of resource service nodes, only the resource utilization rate of resource service nodes is considered for classification. The network load of resource service node classification after job classification is not considered, so the next key work will be about these aspects of research.

Acknowledgments

The work was supported by the National Natural Science Foundation (NSF) under grants (No. 61802353), the Natural Science Foundation of Henan Province (No. 202300410505), the project of Science and Technology of Henan Province (NO. 192102210270) and the Henan Provincial Department of Science and Technology (NO. 192102210270).

Conflict of interest

The authors declared that they have no conflicts of interest to this work. We declare that we do not have any commercial or associative interest that represents a conflict of interest in connection with the work submitted.