# Computation Offloading Optimization in Mobile Edge Computing Based on HIBSA

Authors: Yang Liu; Jin Qi Zhu; Jinao Wang
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Multiaccess edge computation (MEC) is a hotspot in 5G network. The problem of task offloading is one of the core problems in MEC. In this paper, a novel computation offloading model which partitions tasks into subtasksis proposed. This model takes communication and computing resources, energy consumption of intelligent mobile devices, and weight of tasks into account. We then transform the model into a multiobjective optimization problem based on Pareto that balances the task weight and time efficiency of the offloaded tasks. In addition, an algorithm based on hybrid immune and bat scheduling algorithm (HIBSA) is further designed to tackle the proposed multiobjective optimization problem. The experimental results show that HIBSA can meet the requirements of both the task execution deadline and the weight of the offloaded tasks.


---

## Body

## 1. Introduction

With the rapid development of the Internet of Things (IoT), intelligent mobile devices (IMDs) have become indispensable tools in people’s daily life, and their functions have become more and more powerful, which can meet people’s needs in social, shopping, travel, entertainment, and so on. Due to the physical size constraint, mobile devices are usually resource-constrained and have a limited power supply. However, most of the computation-intensive services, such as image processing or video-based applications, need high processing power and have high resources consumption [1, 2]. Compute-intensive tasks cannot be completed in time or may even be blocked if they are only processed locally [3]. Hence, how to solve the contradiction between the limited resources of mobile terminals and the high resources requirement of compute-intensive services has become one of the main problems to be solved [4].Nowadays, multiaccess edge computation (MEC) [5] has been a promising paradigm to resolve the abovementioned problem [6, 7]. In MEC, an edge site/server is a microdata center, which is deployed attached to a small base station (SBS). By moving computing storage and service capabilities to the network edge, MEC can provide high reliability, high bandwidth, and low-latency computing services for mobile devices. Since mobile terminals can then offload tasks to the nearby edge computing servers with rich computing resources, the problem of resource limitation of IMDs can be resolved to some extent.Obviously, when multiple IMDs upload tasks at the same time, they will inevitably compete with each other for both communicational and computing resources [8]. Unreasonable resource allocation can result in a low data transmission rate and high delay. Therefore, the designation of the task scheduling scheme has an important influence on the performance of the MEC system. So far, many researchers have focused on the computation offloading scheduling problem. However, most of these studies have performance limitations, which can be explained from the following aspects. Firstly, some researches allocate tasks to only one edge server. However, since the density of SBSs is high [9, 10] in the future and the signal coverages of the SBSs often overlap with each other in real-world scenarios, there are multiple options when unloading tasks. In addition, application partitioning and repartitioning have been studied in depth in mobile cloud computing and distributed systems [11, 12], which can be used in the MEC system. Following these two ideas, assigning tasks to multiple edge servers is more reasonable. Secondly, some works [13] ignored the energy consumption of the IMDs. In fact, the energy consumption of mobile device must be considered because they usually cannot be recharged timely. Thirdly, most studies did not consider the weight of offloading tasks. However, those tasks that are important or have a long waiting time in the scheduling queue should be scheduled in priority for fairness. Finally, some studies have not jointly considered the allocation of both the communication and computing resources. Compared with the prior works, the contributions of our paper are as follows:(i)
The proposed task offloading model takes communication and computing resources, energy consumption of the IMD, and weight of tasks into account.(ii)
We consider the scenario that the mobile device can generate multiple tasks at the same time, which is more realistic compared with most related works. Moreover, we partition compute-incentive tasks into subtasks and then offload them to multiple edge servers for parallel computing. Compared to offloading a single task to an edge server, tasks can be executed in a more efficient way.(iii)
A novel multiobjective task scheduling algorithm is designed, which combines the advantages of both the bat algorithm and the immune algorithm to improve the reliability of task offloading while reducing the task completion time.(iv)
Extensive simulations have been conducted, and the results show that the proposed algorithm can effectively shorten the task execution time and has higher reliability compared with conventional algorithms.The rest of this paper is organized as follows. Section2 presents related works. Section 3 describes the system model and the problem formulation. In Section 4, we transform the offloading decision problem into a multiobjective optimization problem based on Pareto and then design a multiobjective task scheduling algorithm based on hybrid immune and bat scheduling algorithm (HIBSA). Section 5 gives the experimental comparisons of HIBSA with other algorithms, which validate the superior performance of HIBSA. Finally, we make the conclusion in Section 6.


## 2. Related Work

Task offloading refers to the process of allocating tasks to edge servers with sufficient resources according to some offloading policies. These policies determine both the efficiency and the achievable computation performance of the MEC. Task offloading is also called computing migration or computing offloading [14]. By delivering compute-incentive tasks such as face recognition and video optimization to MEC servers, high task quality of service (QoS) is achieved. In the last few years, task offloading problems have attracted great interest of researchers. For instance, Wu et al. [10] proposed an offloading algorithm based on support vector machine (SVM). The proposed algorithm firstly segments a task into several subtasks by using a weight allocation method. Then, each subtask is determined to be offloaded or executed locally. In [11], Mao et al. developed an online joint radio and computational resource management algorithm for a multiuser MEC system, with the objective of minimizing the long-term average weighted sum power consumption of the mobile devices and the MEC server, subject to a task buffer stability constraint. In literature [12], the authors proposed an efficient computation offloading algorithm by jointly optimizing user association and computation offloading where computation resource allocation and transmission power allocation are also considered. Also, the authors in work [13] proposed a novel offloading system to design robust offloading decisions for mobile services. This system considers the dependency relations among component services and aims to optimize task execution time and energy consumption of mobile devices. These abovementioned researches focus on the computation offloading problem in the single-server MEC system.On the other hand, many researchers have devoted their efforts to task offloading problems in multiuser and multiserver MEC systems. For example, in [15], a cross-edge computation offloading framework for compute-incentive applications was proposed. The transmission cost, task execution cost, coordination cost, as well as penalty for task failure were considered together in the offloading model designation. An online algorithm based on Lyapunov optimization is proposed to jointly determine edge server site selection and energy harvesting. Work [16] investigated computation offloading in a dynamic MEC system with multiple edge servers, where computational tasks with various requirements were dynamically generated by IoT devices and then offloaded to MEC servers in a time-varying operating environment. The objective of this work is to maximize the task completion time and minimize the energy consumption of IoT devices. In [17], the authors used an improved glowworm swarm optimization algorithm to solve the task offloading problem for a multiuser-multi-MEC environment. Also, the authors in work [18] presented a reinforcement learning framework based on the theory of stochastic learning automata towards enabling the end-users to select an MEC server to offload their data. To realize the proposed framework, an iterative and low-complexity algorithm is introduced and designed. Literature [19] proposed a cooperative offloading technique based on the Lagrangian suboptimal convergent computation offloading algorithm (LSCCOA) for multiaccess MEC in a distributed Internet of Things (IoT) network. However, none of the abovementioned methods considered the weight of the offloaded tasks. In fact, different tasks are of different importance to users.To indicate the importance of different tasks, the authors in [20] proposed a multiobjective task scheduling algorithm, which aimed to optimize the allocation of the weight of the offloaded tasks. However, this work has the following limitations. First, tasks in this work can be offloaded to an edge server only. Second, the energy consumption of the mobile terminal was ignored. Finally, a bat algorithm was used in this work to get the optimization result. Since the bat algorithm has no mutation operation, sometimes, the solutions are lack of diversity. Specifically, Table 1 shows the differences between some related studies and our work proposed in this paper.Table 1
The differences between several references and our work.
Related worksProblem formulationOptimization objectivesAlgorithm proposed[15]Markov decision process (MDP)Minimize the overall delay cost of all mobile devices subject to some constraintsThe sampling and classification (SAC) based edge site selection (SES) algorithm[18]A two-layer optimization frameworkMaximize its profit by processing the end-users’ data for each MEC server while maximizing its perceived satisfaction for each end-userData offloading and MEC server selection (DO-MECS) algorithm[19]Single-objective optimization problem with multiple constraintsLessen the weighted amount of power consumed by communicating devices subject to some constraintsThe Lagrangian suboptimal convergent computation offloading algorithm (LSCCOA)[20]Multiobjective optimization problem with multiple constraints based on ParetoMinimize the total execution time and maximize the total weight under the constraints of communication and computing resourcesBat algorithmOur methodMultiobjective optimization problem with multiple constraints based on ParetoMinimize the total execution time and maximize the total weight under the constraints of communication, computing and energy resourcesHybrid immune and bat scheduling algorithm (HIBSA)In this paper, the proposed model takes many aspects of task offloading into account. Moreover, the bat algorithm is combined with an immune algorithm to improve the performance of the bat algorithm and get better optimization results. Meanwhile, the scenario that mobile devices can generate multiple tasks simultaneously is considered. To the best of our knowledge, each device can only generate only one task in the related studies. Hence, our work is more realistic compared with relevant studies.


## 3. System Model and Problem Formulation

### 3.1. System Model

Suppose the proposed system consists ofn IMDs and m MEC servers. Let D=D1,D2,…,Dn denote the set of IMDs and CS=CS1,CS2,…,CSm denote the set of MEC servers. We also discretize time into multiple time slots, and all time slots have equal length as σ.Among setCS, one edge server in the central location is selected as the controller. The proposed HIBSA algorithm, which is detailed in Section 4, is executed on this controller. In each time slot σ, the IMDs generate computation task requests. Those requests along with the basic information of the IMDs (e.g., app type, local CPU-cycle frequency, and battery energy level) are then sent to the controller. By executing the HIBSA algorithm, the controller chooses the edge server for each IMD for task offloading. The architecture of this system model is shown in Figure 1.Figure 1
The architecture of system model.For any IMDDi∈D, there exists a task queue Ti=T1i,T2i,…,Tki,…, where Tki denotes the k-th task generated by the i-th IMD at a certain time slot. For task Tki, it can be denoted by four tuples dnumik,cnumik,wik,φik, where dnumik is the size of the input data for computation, cnumik is the CPU cycles to be processed for offloading, wik is the weight of the task, and φik is the remaining battery energy value of this IMD when generating this task. All generated tasks can be divided into two types. One is the real-time task, and another is the delay-tolerant task. The real-time task owns a maximum latency and must be finished before the delay threshold whereas the delay-tolerant task can tolerate a much longer delay.Furthermore, we use a binary matrixs=sij|sij∈0,1n×m to represent one scheduling solution, where sij = 1 denotes that the latest task generated by the i-th IMD is allocated to the j-th server in this scheduling solution, while sij = 0, otherwise.


### 3.2. Performance Evaluation

For any scheduling solution, its performance is described by a vector (time cost and weight), where time cost is the sum of the time consumption for executing all tasks. Moreover, time cost consists of two parts: one is the time delay for successfully completed tasks, and the other is the punishment time for failed tasks. The timetik for successfully finishing task Tki is as follows:(1)tik=tcomm+tcomp+tcoor+tlocal,where tcomm is communication cost and is denoted as(2)tcomm=maxj∈CS,sij=1dnumikCij⋅∑j∈CSsij,where Cij is the approximate data rate between the i-th IMD and the j-th edge server, based on the 3GPS TS 38.306; the transmission rate is as follows:(3)Cij=10−6⋅∑k=1KvLayersk⋅Qmk⋅fk⋅Rmax⋅NPRBBWk,μ⋅12TSμ⋅1−OHk,where K is the number of aggregated component carriers (CC) in a band or band combination between the i-th IMD and the j-th edge server. Rmax = 948/1024. For the k-th CC, vLayersk is the maximum number of layers; Qmk is the maximum modulation order; fk is the scaling factor; µ is the numerology; TSμ is the average OFDM symbol duration in a subframe for numerology μ; NPRBBWk,μ is the maximum RB allocation in bandwidth BW(k) with numerology μ, where BW(k) is the supported maximum bandwidth in the given band or band combination between the i-th IMD and the j-th edge server; and OH(k) is the overhead. tcomp, which is the time for computing this offloaded task, is given as (4)tcomp=maxj∈CS,sij=1cnumikfj⋅∑j∈CSsij,where fj is the CPU cycle frequency of the j-th edge server and tcoor is the coordination cost between multiple servers and is calculated as follows:(5)tcoor=ulc⋅∑j∈CSsij,where ulc is the unit latency cost and tlocal is local execution time that includes data preprocessing time and data packing time. tlocal is given as(6)tlocal=cikfi,where cik is the amount of CPU cycles to process the local execution and fi is the CPU cycle frequency of the i-th IMD. Besides, tik should satisfy(7)tik≤TCik,where TCik is the execution deadline of this task. Successfully completed tasks are put into the successful set Gsuc. Accordingly, the whole time consumption for successfully completed tasks is ∑i∈Gsuctik.There are two possibilities for the failed task. One is the task is overtime, namely,tik > TCik. These tasks must be omitted or wait for the next time to be scheduled again, which depends on the type of the task. The other is that the task is not assigned to any server in this schedule at all, namely, ∑j∈CSsij=0. These tasks also need to wait for the next schedule or to be omitted. In these conditions, a time punishment F was given (F>TCik), and the failed tasks are put into unsuccessful set Gfail. Thus, at a certain time slot σ, the total time cost of all the scheduling is defined as follows:(8)tall=Σi∈Gsuctik+Gfail⋅F.Another evaluation metric is weight. The sum of the weights of all successfully offloaded tasks is(9)w=∑i∈Ssucwi.


### 3.3. Problem Formulation

For the task scheduling problem involved in this paper, there are 2n×m possible scheduling solutions. The set of scheduling solutions is denoted as S. The optimization goal of this model is to find a scheduling s(s∈S) under the constraints of communication, computing, and energy resources, which can minimize the total execution time and maximize the total weight. Here, any scheduling solution should satisfy two constraints: one is the computing resources constraint, which is shown as(10)∀j∈CS∑i∈Dsij≤Mj,which means that the j-th server can be assigned up to at most Mj tasks due to its limited computational capability. The other one is the energy consumption constraint, which is shown as(11)εl+∑j∈CSεi,jtx⋅sij≤φik,where εl is the energy consumption of local execution and εijtx is the energy consumption for transmitting between the i-th IMD and the j-th edge server and is given by(12)εi,jtx=pitx⋅tcomm,where pitx represents the fixed transmit power of the IMDi. Formula (11) means the total energy consumption of the i-th IMD must be less than the current battery energy value of this device.Therefore, the proposed task scheduling problem can be formulated as the following combinatorial optimization problemP:(13)Pminf1s=tall=Σi∈Gsuctik+Gfail⋅F,minf2s=w=−∑i∈Ssucwi,s.t.C1:∀j∈CS∑i∈Dsij≤Mj,C2:εl+∑j∈CSεi,jtx⋅sij≤φik.


### 3.4. Demo

In this section, a simple demo was given to illustrate the task scheduling problem in multiple server environments. As shown in Figure2, suppose there are three devices (D1, D2, and D3) and two MEC servers (CS1 and CS2) in the system, and there are three queues T1,T2,T3, respectively. At the first time slot, tasks in each queue are denoted as T112,2,1,1,T125,5,3,2,T133,3,1,1, respectively.Figure 2
Initial condition of DEMO.For simplify, we make the following assumptions: (1) each MEC server can run only one task at one time; (2) the delay constraint of all these three tasks is 7, namelyTc = 7; (3) the data transmission rate Cij, the computation rate ηj, and the unit data energy consumption of transmission between i-th IMD and j-th server εijtx are all assumed to be 1; (4) the local execution time, energy consumption, and the coordination cost are ignored, namely εl=0 and tcoor = tlocal = 0. As shown in Table 2, three task scheduling solutions are given.Table 2
Solutions.
SolutionsCS\DD1D2D3s1CS1111CS2111s2CS1100CS2001s3CS1010CS2010Sinces1 cannot meet constraints (10) and (11), it is invalid scheduling. s2 satisfies constraints (10) and (11). According to formula (1), the task completion time of T11 is 4, which is less than the delay constraint. Therefore, this is a successful offloading, and sequence number 1 is put into set Gsuc. As a result, Gsuc = {1}. T12 is not assigned any computing server in this scheduling, so sequence number 2 is put into the failure set Gfail. According to formula (1), the task completion time of T13 is 6, which is less than the delay constraint value. Since it is a successful offloading, sequence number 3 is put into the success set Gsuc, and Gsuc is updates to {1, 3}. According to formulas (8) and (9), tall = 4 + 6 + F = 10 + F and w = 2. Also, s3 satisfies the constraints (10) and (11). T11 is not assigned any computing server in this scheduling. Thus, s3 is a failed offloading. According to formula (1), the completion time of T12 is 5. Therefore, this is a successful offloading, and sequence number 2 is put into the success set Gsuc and Gsuc = {2}. T13 is not assigned any computing server in this scheduling, so it is a failed offloading. Thus, we have tall = 5 + 2F and w=3.In all, none of these scheduling schemes has both the least time consumption time and the largest task completion weight. Generally, the best solution that meets all the objectives cannot be found. However, the noninferior solution can be found.


## 3.1. System Model

Suppose the proposed system consists ofn IMDs and m MEC servers. Let D=D1,D2,…,Dn denote the set of IMDs and CS=CS1,CS2,…,CSm denote the set of MEC servers. We also discretize time into multiple time slots, and all time slots have equal length as σ.Among setCS, one edge server in the central location is selected as the controller. The proposed HIBSA algorithm, which is detailed in Section 4, is executed on this controller. In each time slot σ, the IMDs generate computation task requests. Those requests along with the basic information of the IMDs (e.g., app type, local CPU-cycle frequency, and battery energy level) are then sent to the controller. By executing the HIBSA algorithm, the controller chooses the edge server for each IMD for task offloading. The architecture of this system model is shown in Figure 1.Figure 1
The architecture of system model.For any IMDDi∈D, there exists a task queue Ti=T1i,T2i,…,Tki,…, where Tki denotes the k-th task generated by the i-th IMD at a certain time slot. For task Tki, it can be denoted by four tuples dnumik,cnumik,wik,φik, where dnumik is the size of the input data for computation, cnumik is the CPU cycles to be processed for offloading, wik is the weight of the task, and φik is the remaining battery energy value of this IMD when generating this task. All generated tasks can be divided into two types. One is the real-time task, and another is the delay-tolerant task. The real-time task owns a maximum latency and must be finished before the delay threshold whereas the delay-tolerant task can tolerate a much longer delay.Furthermore, we use a binary matrixs=sij|sij∈0,1n×m to represent one scheduling solution, where sij = 1 denotes that the latest task generated by the i-th IMD is allocated to the j-th server in this scheduling solution, while sij = 0, otherwise.


## 3.2. Performance Evaluation

For any scheduling solution, its performance is described by a vector (time cost and weight), where time cost is the sum of the time consumption for executing all tasks. Moreover, time cost consists of two parts: one is the time delay for successfully completed tasks, and the other is the punishment time for failed tasks. The timetik for successfully finishing task Tki is as follows:(1)tik=tcomm+tcomp+tcoor+tlocal,where tcomm is communication cost and is denoted as(2)tcomm=maxj∈CS,sij=1dnumikCij⋅∑j∈CSsij,where Cij is the approximate data rate between the i-th IMD and the j-th edge server, based on the 3GPS TS 38.306; the transmission rate is as follows:(3)Cij=10−6⋅∑k=1KvLayersk⋅Qmk⋅fk⋅Rmax⋅NPRBBWk,μ⋅12TSμ⋅1−OHk,where K is the number of aggregated component carriers (CC) in a band or band combination between the i-th IMD and the j-th edge server. Rmax = 948/1024. For the k-th CC, vLayersk is the maximum number of layers; Qmk is the maximum modulation order; fk is the scaling factor; µ is the numerology; TSμ is the average OFDM symbol duration in a subframe for numerology μ; NPRBBWk,μ is the maximum RB allocation in bandwidth BW(k) with numerology μ, where BW(k) is the supported maximum bandwidth in the given band or band combination between the i-th IMD and the j-th edge server; and OH(k) is the overhead. tcomp, which is the time for computing this offloaded task, is given as (4)tcomp=maxj∈CS,sij=1cnumikfj⋅∑j∈CSsij,where fj is the CPU cycle frequency of the j-th edge server and tcoor is the coordination cost between multiple servers and is calculated as follows:(5)tcoor=ulc⋅∑j∈CSsij,where ulc is the unit latency cost and tlocal is local execution time that includes data preprocessing time and data packing time. tlocal is given as(6)tlocal=cikfi,where cik is the amount of CPU cycles to process the local execution and fi is the CPU cycle frequency of the i-th IMD. Besides, tik should satisfy(7)tik≤TCik,where TCik is the execution deadline of this task. Successfully completed tasks are put into the successful set Gsuc. Accordingly, the whole time consumption for successfully completed tasks is ∑i∈Gsuctik.There are two possibilities for the failed task. One is the task is overtime, namely,tik > TCik. These tasks must be omitted or wait for the next time to be scheduled again, which depends on the type of the task. The other is that the task is not assigned to any server in this schedule at all, namely, ∑j∈CSsij=0. These tasks also need to wait for the next schedule or to be omitted. In these conditions, a time punishment F was given (F>TCik), and the failed tasks are put into unsuccessful set Gfail. Thus, at a certain time slot σ, the total time cost of all the scheduling is defined as follows:(8)tall=Σi∈Gsuctik+Gfail⋅F.Another evaluation metric is weight. The sum of the weights of all successfully offloaded tasks is(9)w=∑i∈Ssucwi.


## 3.3. Problem Formulation

For the task scheduling problem involved in this paper, there are 2n×m possible scheduling solutions. The set of scheduling solutions is denoted as S. The optimization goal of this model is to find a scheduling s(s∈S) under the constraints of communication, computing, and energy resources, which can minimize the total execution time and maximize the total weight. Here, any scheduling solution should satisfy two constraints: one is the computing resources constraint, which is shown as(10)∀j∈CS∑i∈Dsij≤Mj,which means that the j-th server can be assigned up to at most Mj tasks due to its limited computational capability. The other one is the energy consumption constraint, which is shown as(11)εl+∑j∈CSεi,jtx⋅sij≤φik,where εl is the energy consumption of local execution and εijtx is the energy consumption for transmitting between the i-th IMD and the j-th edge server and is given by(12)εi,jtx=pitx⋅tcomm,where pitx represents the fixed transmit power of the IMDi. Formula (11) means the total energy consumption of the i-th IMD must be less than the current battery energy value of this device.Therefore, the proposed task scheduling problem can be formulated as the following combinatorial optimization problemP:(13)Pminf1s=tall=Σi∈Gsuctik+Gfail⋅F,minf2s=w=−∑i∈Ssucwi,s.t.C1:∀j∈CS∑i∈Dsij≤Mj,C2:εl+∑j∈CSεi,jtx⋅sij≤φik.


## 3.4. Demo

In this section, a simple demo was given to illustrate the task scheduling problem in multiple server environments. As shown in Figure2, suppose there are three devices (D1, D2, and D3) and two MEC servers (CS1 and CS2) in the system, and there are three queues T1,T2,T3, respectively. At the first time slot, tasks in each queue are denoted as T112,2,1,1,T125,5,3,2,T133,3,1,1, respectively.Figure 2
Initial condition of DEMO.For simplify, we make the following assumptions: (1) each MEC server can run only one task at one time; (2) the delay constraint of all these three tasks is 7, namelyTc = 7; (3) the data transmission rate Cij, the computation rate ηj, and the unit data energy consumption of transmission between i-th IMD and j-th server εijtx are all assumed to be 1; (4) the local execution time, energy consumption, and the coordination cost are ignored, namely εl=0 and tcoor = tlocal = 0. As shown in Table 2, three task scheduling solutions are given.Table 2
Solutions.
SolutionsCS\DD1D2D3s1CS1111CS2111s2CS1100CS2001s3CS1010CS2010Sinces1 cannot meet constraints (10) and (11), it is invalid scheduling. s2 satisfies constraints (10) and (11). According to formula (1), the task completion time of T11 is 4, which is less than the delay constraint. Therefore, this is a successful offloading, and sequence number 1 is put into set Gsuc. As a result, Gsuc = {1}. T12 is not assigned any computing server in this scheduling, so sequence number 2 is put into the failure set Gfail. According to formula (1), the task completion time of T13 is 6, which is less than the delay constraint value. Since it is a successful offloading, sequence number 3 is put into the success set Gsuc, and Gsuc is updates to {1, 3}. According to formulas (8) and (9), tall = 4 + 6 + F = 10 + F and w = 2. Also, s3 satisfies the constraints (10) and (11). T11 is not assigned any computing server in this scheduling. Thus, s3 is a failed offloading. According to formula (1), the completion time of T12 is 5. Therefore, this is a successful offloading, and sequence number 2 is put into the success set Gsuc and Gsuc = {2}. T13 is not assigned any computing server in this scheduling, so it is a failed offloading. Thus, we have tall = 5 + 2F and w=3.In all, none of these scheduling schemes has both the least time consumption time and the largest task completion weight. Generally, the best solution that meets all the objectives cannot be found. However, the noninferior solution can be found.


## 4. Proposed Algorithm

### 4.1. Multiobjective Optimization Problem

#### 4.1.1. Problem Statement

The general description of the multiobjective optimization problem is as follows:Given the vectorX=x1,x2,…,xn∈Rn, and it satisfies the following constraints:(14)giX≤0i=1,2,…,k,(15)hiX=0i=1,2,…,l.Suppose that there arer optimization objectives, which are in conflict with each other. The optimization objective can be expressed as follows:(16)minfX=minf1X,f2X,…,frX.We want to findX∗=x1∗,x2∗,…,xn∗ in order that fX∗ can be optimized while satisfying constraints (14) and (15). Obviously, the scheduling problem mentioned in this paper is a multiobjective optimization problem. Generally, it is necessary to consider the conflicting subobjectives comprehensively and make the trade-off among the subobjectives.


#### 4.1.2. Pareto-Optimal Set

Multiobjective optimization is to simultaneously optimize multiple subobjectives, and these subobjectives often conflict with each other. The optimization of one objective may result in the deterioration of another objective. Normally, no single solution can optimize all the objectives simultaneously. The trade-off among multiobjectives can be properly attained by using Pareto optimality [21].Definition 1 (Pareto dominance).
A decision vectorXA is said to dominate another decision vector XB (noted as XA≻XB) if and only if(17)∀i=1,2,…,r,fiXA≤fiXB∧∃j=1,2,…,r,fjXA<fjXB.Definition 2 (Pareto optimal).
A solutionX∗∈Xf is said to be Pareto optimal if and only if(18)¬∃X′∈Xf:fjX∗≥fjX′,∀j=1,2,…,r,where Xf represents the set of solutions.Definition 3 (Pareto-optimal set).
SetP∗ includes all Pareto-optimal solutions, which can be defined as follows:(19)P∗=X∗=X∈Xf|¬∃X′∈Xf:fjX≥fjX′,∀j=1,2,…,r.


#### 4.1.3. General Framework of MOEA Based on Pareto

An evolutionary algorithm (EA) is a kind of random search algorithm that simulates the natural selection and evolution of organisms. It is widely used because it is suitable for solving highly complex nonlinear problems. At the same time, it has good versatility. The advantages of EA have been fully demonstrated in solving single objective complex system optimization problems. However, EA cannot resolve multiobjective optimization problems effectively. For the multiobjective optimization problem, it can be resolved by the multiobjective evolutionary algorithm (MOEA). Over the last decades, the design method of MOEA has attracted great interest of researchers [22–24].Most MOEAs adopted the general process, which is shown in Figure3. The whole process of MOEA is described as follows. Firstly, an initial population P is generated, and an algorithm is selected to operate on P to obtain a new evolutionary population R. Next, a strategy is adopted to construct the nondominated set (NDSet) of P∪R. Generally, the set size is set when designing the algorithm (such as N). If the size of the current set is greater than or less than N, the size of the NDSet needs to be adjusted according to a certain strategy. In the adjusting process, the NDSet must meet both the size requirements and the individual diversity. Then whether the termination condition is satisfied is judged. The process ends if and only if the termination condition is satisfied. Otherwise, we need to copy the individuals in NDSet to P and continue to the next round of evolution.Figure 3
General flow of multiobjective evolutionary algorithm based on Pareto.


### 4.2. Individual Evaluation Method

Different from the single-objective optimization problem, the multiobjective optimization problem needs vector comparison. The multiobjective optimization strategy adopted in this paper is similar to the method of NGSA-II [25–27], but some changes have been made. All scheduling schemes are divided into three types. For any scheduling s of the first type, it can complete all tasks on the premise of satisfying constraints (10) and (11). Obviously, this type of scheduling is ideal, so it is set to the highest rank 0, namely ranks = 0. The scheduling of the same level is ranked according to the task completion time, and the higher priority value has little task completion time. The second type is also to satisfy constraints (10) and (11), but it can only complete a part of offloaded tasks. We regard each scheduling s of this type as an individual in the evolutionary algorithm. According to the NSGA-II method [28], all individuals in the first nondominated front are found firstly. In order to find the individuals in the next nondominated front, the solutions of the first front are discounted temporarily, and the above procedure is repeated. The rank of the scheduling s in the first front is 1, namely ranks = 1. Similarly, the rank of the scheduling in the second front is 2, so back and forth. Compared with the crowding distance of individuals in the same rank, individuals with higher aggregation density have a higher priority value. The third type is the scheduling that violates constraints (10) and (11). Assuming that the second type is divided into n ranks, for the scheduling s that belongs to the third type, its rank is n + 1, namely ranks = n + 1. The scheduling that violates constraint (10) to a lower degree has a higher priority. According to the abovementioned method, suppose there are scheduling p and scheduling q, the comparison strategy between them is described in Algorithm 1.Algorithm1: Individual evaluation algorithm (IEA).
(1)
If (rankp < rankq)(2)
p≻q(3)
If (rankp = rankq= 0 and tp < tq)(4)
p≻q(5)
If (rankp = rankq = n+1 and∑j∈csmax∑i∈Dpij−Mj,0<∑j∈csmax∑i∈Dqij−Mj,0)(6)
p≻q(7)
If (1 ≤ rankp ≤ n and 1 ≤ rankq ≤ n and dp > dq)(8)
p≻q(dp and dq represent the aggregation density of p and q, respectively)


### 4.3. Our Algorithm

#### 4.3.1. Bat Algorithm

As mentioned above, the basis of multiobjective evolutionary algorithm is an evolutionary algorithm. At present, the most commonly used evolutionary algorithms include simulated annealing algorithm, genetic algorithm, distribution estimation algorithm, and particle swarm optimization algorithm. However, in these algorithms, the individual’s movement mode does not adopt the position update mode of the deterministic algorithm. That is, “only move to the solution that is better than the current position” method is used. Yang [29] proposed a bat algorithm (BA) that adopts the method of “only move to the solution which is better than the current position.” BA simulates the behavior of microbats in nature, which uses echolocation to hunt prey and avoid obstacles. Compared with other evolutionary algorithms, BA has the characteristics of higher computational efficiency, stronger optimization ability, and robustness.According to the bat’s echolocation behavior and its correlation with objective optimization, the parameters and updating equations ofn bats during flight are given below: Suppose that there are n virtual bats living in the domain. In the t-th generation, the information containing the i-th (i = 1, 2, …, n) bat can be expressed as five tuples: xi⟶t,vi⟶t,frit,Ait,rit, where xi⟶t=xi1t,xi2t,…,xikt,…,xiNt denotes the position information of the t-th generation of the i-th bat and a solution of the search space, the speed vi⟶t=vi1t,vi2t,…,vikt,…,viNt represents the velocity direction of the i-th bat in the t-th generation, while frequency fri (t), loudness Ai (t), and pulse emission frequency ri (t) are three parameters needed by i-th bat in the algorithm. In the (t+1)-th generation, each bat firstly updates its speed according to the formula, which is described as follows:(20)vit+1=vit+xit−pt⋅fritm,where p⟶t=p1t,p2t,…,pkt,…,pNt indicates the historical optimal position of the previous t generations, while xit−ptfrit represents the effect of the deviation between xi⟶t and p⟶t on the speed of the next generation, and the frequency fri (t) is randomly generated according to the following formula:(21)frit=frmin+frmax−frmin⋅rand1,where rand1 is a uniformly distributed random number in (0, 1) and the two parameters frmax and frmin are the preset as the upper and lower frequency limits, respectively.On this basis, when each bat performs a global or local search, the selection of its search mode is determined in a random way. It means random numberrand2, which is uniformly distributed between 0 and 1 needs to be determined. If rank2<r1t, the i-th bat will search for food in the following global search mode:(22)xi′t+1=xit+vit+1.Otherwise, thei-th bat will perform a local search according to the following formula:(23)xi′t+1=pt+εi⋅At¯,where εi is a uniformly distributed random number belongs to (−1, 1) and At¯=∑j=1nAjt/n is the average loudness of the bat at the t-th time.After the new locationxi′⟶t+1=xi1′t,xi2′t,…,xik′t,…,xiN′t is calculated, the bat will be judged whether to move instead of moving to the new location immediately according to the following update rules:(24)xi⟶t+1=xi′⟶t+1,rand3<Aitandfxi′⟶t+1<fxi⟶t,xi⟶t,else.When updating the position, a uniformly distributed random numberrand3 that belongs to (0, 1) was selected. When rand3<Ait and fxi′⟶t+1<fxi⟶t are satisfied simultaneously, the i-th bat updates the location to xi⟶t+1. Otherwise, the location of i-th bat is still xi⟶t without updating the location to xi⟶t+1.The update formula of the pulse emission rateri (t + 1) is as follows:(25)rit+1=ri0⋅1−e−γt.LoudnessAi(t + 1) is updated as follows:(26)Ait+1=αAit,where α > 0 and γ > 0 are both preset parameters, Ai(0) is the initial value of loudness, and ri (0) is the initial value of pulse emission rate. In the paper, Ai(0) is random selected from [0, 1] and ri (0) = 0.1.In the basic bat algorithm, equations (20) and (22) represent the global search mechanism of the algorithm, while equation (23) represents the local search mechanism of the bat algorithm.


#### 4.3.2. Hybrid Immune Bat Algorithm

It was shown that the optimization ability of BA mainly depends on the interaction and influence between bat individuals. Due to the lack of a mutation mechanism, it is difficult for individuals to get rid of the constraint of a local extreme value. Moreover, in the evolution process, the super bats in the population may attract other individuals to gather around them quickly, which results in a significant decline in population diversity. Meanwhile, the bat individuals are getting closer to the optimal individuals of the population in order that the population has lost the ability of further evolution [30]. In this paper, the clonal selection mechanism in the artificial immune system is introduced, which can enhance the diversity of bat population, enhance the ability of wide range variation, and increase the convergence rate.Suppose that an individual populationB=b1,b2,…,bn is obtained through the process of the bat algorithm, which is a temporary clonal population. Each bat i (i = 1, 2, …, n) in the temporary clonal population is regarded as an antibody. The specific methods are as follows:Step 1: thek (k < n) antibody individuals selected in a random way were grouped into subpopulation Sub1=b1′,b2′,…,bk′. And clone and copy subpopulation Sub1. The cloning operator is described as follows:(27)Sub2=TcSub1=TCb1′,TCb2′,…,TCbk′,whereTCbi′=qi×bi′,i=1,2,…,k, where qi is the number of clones of bi′, which is proportional to the fitness of bi′. A new population Sub2 was generated by cloning.Step 2: implement high-frequency mutation for each individual in group Sub2, and the mutation operator is adaptive, which is related to both evolution generations and individual fitness. For any bi′=bi1′,bi2′,…,bij′,…,bin′, the mutation formula is given as follows:(28)bij′new=∼bij′old,rand4<ηtandrand5<Δ,bij′old,else.ηt in formula (28) is given as follows:(29)ηt=1−r11−t/Tb,whereb is a positive constant, r1∈0,1. In the early stages of evolution, r11−t/Tb was smaller, ηt≈1, but in the later stage of evolution, when t approaches T, ηt≈0, local search is carried out in a small space.Furthermore,Δ in formula (28) is formulated as follows:(30)Δ=1−r2Rλ,wherer2∈0,1, the parameter λ plays the role of adjusting the search area, and the value is generally 2–5 [31]. R in the above formula is formulated as follows:(31)R=1−fitbi′fitmax,wherefitbi′ represents the fitness of antibody bi′ and fitmax is the maximum fitness value, which is the aggregation density of the individual. Obviously, for those with higher fitness, the Δ value is smaller, and the mutation possibility is small, while for those with lower fitness, the mutation possibility is relatively large.Step 3: immune clonal selection: the best individual from the clonal mutation individuals is selected for the next generation. The full algorithm of HIBSA is given in Algorithm2.


#### 4.3.3. The Full Algorithm of HIBSA

Algorithm2: Hybrid immune and bat scheduling algorithm (HIBSA).
(1)
The scheduling populationP0 is randomly generated, the population size is n, and the initialization generation t = 0(2)
According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 inP are put into the set P0t and P1t, respectively(3)
If (P0t≠Φ)select the optimal solution inP0t as the result and the algorithm ends(4)
else(5)
while (t < T)(6)
A solution is randomly selected fromP1t as the historical optimal position of the current population, and BA is implemented for Pt to get PBt(7)
Clear setP0t, P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(8)
If (P0t≠Φ)(9)
select the optimal solution inP0t as the result and the algorithm ends(10)
else(11)
ForPBt, the immune clonal selection algorithm is implemented to get PIt(12)
Clear setP0t and P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(13)
If (P0t≠Φ)(14)
select the optimal solution inP0t as the result and the algorithm ends(15)
else(16)
According to the individual evaluation algorithm, put the firstn individuals in the set PBt∪PIt into Pt+1(17)
t = t + 1(18)
end if(19)
end if(20)
end while(21)
end if(22)
select a solution randomly fromP1t as the result and the algorithm ends


### 4.4. Time Complexity Analysis

In this section, the time complexity of HIBSA is analyzed. Based on the flowchart in Figure3, assuming that the population P size, the new group R size are both N, the number of objectives is M (in fact, M is 2 in this paper). The number of decision valuables is m×n (n is the number of IMDs and m is the number of MEC servers). The basic operators and their time complexity analysis are given as follows:(1)
Generate initial populationP. Population initialization is to generate individuals randomly and calculate the values of objectives, so the time complexity is O (m × n × N) + O (M × N).(2)
A new groupR was obtained by EA evolution. In this paper, the evolutionary algorithm combines the bat algorithm and the immune algorithm together. In both these two algorithms, identifying nondominated individuals was needed. When identifying nondominated individuals, individuals are compared with each other based on the objectives. Hence, the time complexity is O (M × N2).(3)
Construct nondominated set (NDSet) of P∪R. As these operators are performed in the P∪R, so the time complexity of nondominated individuals identification isO (M × (2N)2)(4)
Adjust the scale of NDSet to meet the requirements of distribution. In this stage, adjust operator selects nondominated individuals with greater fitness values to preserve. Therefore, in the assignment of fitness values, the time complexity of the crowding-distance assignment isO (M × N × log (N)).Based on the above analysis, in a single generation, the worst time complexity can be written as follows:(32)OM×N2.


## 4.1. Multiobjective Optimization Problem

### 4.1.1. Problem Statement

The general description of the multiobjective optimization problem is as follows:Given the vectorX=x1,x2,…,xn∈Rn, and it satisfies the following constraints:(14)giX≤0i=1,2,…,k,(15)hiX=0i=1,2,…,l.Suppose that there arer optimization objectives, which are in conflict with each other. The optimization objective can be expressed as follows:(16)minfX=minf1X,f2X,…,frX.We want to findX∗=x1∗,x2∗,…,xn∗ in order that fX∗ can be optimized while satisfying constraints (14) and (15). Obviously, the scheduling problem mentioned in this paper is a multiobjective optimization problem. Generally, it is necessary to consider the conflicting subobjectives comprehensively and make the trade-off among the subobjectives.


### 4.1.2. Pareto-Optimal Set

Multiobjective optimization is to simultaneously optimize multiple subobjectives, and these subobjectives often conflict with each other. The optimization of one objective may result in the deterioration of another objective. Normally, no single solution can optimize all the objectives simultaneously. The trade-off among multiobjectives can be properly attained by using Pareto optimality [21].Definition 1 (Pareto dominance).
A decision vectorXA is said to dominate another decision vector XB (noted as XA≻XB) if and only if(17)∀i=1,2,…,r,fiXA≤fiXB∧∃j=1,2,…,r,fjXA<fjXB.Definition 2 (Pareto optimal).
A solutionX∗∈Xf is said to be Pareto optimal if and only if(18)¬∃X′∈Xf:fjX∗≥fjX′,∀j=1,2,…,r,where Xf represents the set of solutions.Definition 3 (Pareto-optimal set).
SetP∗ includes all Pareto-optimal solutions, which can be defined as follows:(19)P∗=X∗=X∈Xf|¬∃X′∈Xf:fjX≥fjX′,∀j=1,2,…,r.


### 4.1.3. General Framework of MOEA Based on Pareto

An evolutionary algorithm (EA) is a kind of random search algorithm that simulates the natural selection and evolution of organisms. It is widely used because it is suitable for solving highly complex nonlinear problems. At the same time, it has good versatility. The advantages of EA have been fully demonstrated in solving single objective complex system optimization problems. However, EA cannot resolve multiobjective optimization problems effectively. For the multiobjective optimization problem, it can be resolved by the multiobjective evolutionary algorithm (MOEA). Over the last decades, the design method of MOEA has attracted great interest of researchers [22–24].Most MOEAs adopted the general process, which is shown in Figure3. The whole process of MOEA is described as follows. Firstly, an initial population P is generated, and an algorithm is selected to operate on P to obtain a new evolutionary population R. Next, a strategy is adopted to construct the nondominated set (NDSet) of P∪R. Generally, the set size is set when designing the algorithm (such as N). If the size of the current set is greater than or less than N, the size of the NDSet needs to be adjusted according to a certain strategy. In the adjusting process, the NDSet must meet both the size requirements and the individual diversity. Then whether the termination condition is satisfied is judged. The process ends if and only if the termination condition is satisfied. Otherwise, we need to copy the individuals in NDSet to P and continue to the next round of evolution.Figure 3
General flow of multiobjective evolutionary algorithm based on Pareto.


## 4.1.1. Problem Statement

The general description of the multiobjective optimization problem is as follows:Given the vectorX=x1,x2,…,xn∈Rn, and it satisfies the following constraints:(14)giX≤0i=1,2,…,k,(15)hiX=0i=1,2,…,l.Suppose that there arer optimization objectives, which are in conflict with each other. The optimization objective can be expressed as follows:(16)minfX=minf1X,f2X,…,frX.We want to findX∗=x1∗,x2∗,…,xn∗ in order that fX∗ can be optimized while satisfying constraints (14) and (15). Obviously, the scheduling problem mentioned in this paper is a multiobjective optimization problem. Generally, it is necessary to consider the conflicting subobjectives comprehensively and make the trade-off among the subobjectives.


## 4.1.2. Pareto-Optimal Set

Multiobjective optimization is to simultaneously optimize multiple subobjectives, and these subobjectives often conflict with each other. The optimization of one objective may result in the deterioration of another objective. Normally, no single solution can optimize all the objectives simultaneously. The trade-off among multiobjectives can be properly attained by using Pareto optimality [21].Definition 1 (Pareto dominance).
A decision vectorXA is said to dominate another decision vector XB (noted as XA≻XB) if and only if(17)∀i=1,2,…,r,fiXA≤fiXB∧∃j=1,2,…,r,fjXA<fjXB.Definition 2 (Pareto optimal).
A solutionX∗∈Xf is said to be Pareto optimal if and only if(18)¬∃X′∈Xf:fjX∗≥fjX′,∀j=1,2,…,r,where Xf represents the set of solutions.Definition 3 (Pareto-optimal set).
SetP∗ includes all Pareto-optimal solutions, which can be defined as follows:(19)P∗=X∗=X∈Xf|¬∃X′∈Xf:fjX≥fjX′,∀j=1,2,…,r.


## 4.1.3. General Framework of MOEA Based on Pareto

An evolutionary algorithm (EA) is a kind of random search algorithm that simulates the natural selection and evolution of organisms. It is widely used because it is suitable for solving highly complex nonlinear problems. At the same time, it has good versatility. The advantages of EA have been fully demonstrated in solving single objective complex system optimization problems. However, EA cannot resolve multiobjective optimization problems effectively. For the multiobjective optimization problem, it can be resolved by the multiobjective evolutionary algorithm (MOEA). Over the last decades, the design method of MOEA has attracted great interest of researchers [22–24].Most MOEAs adopted the general process, which is shown in Figure3. The whole process of MOEA is described as follows. Firstly, an initial population P is generated, and an algorithm is selected to operate on P to obtain a new evolutionary population R. Next, a strategy is adopted to construct the nondominated set (NDSet) of P∪R. Generally, the set size is set when designing the algorithm (such as N). If the size of the current set is greater than or less than N, the size of the NDSet needs to be adjusted according to a certain strategy. In the adjusting process, the NDSet must meet both the size requirements and the individual diversity. Then whether the termination condition is satisfied is judged. The process ends if and only if the termination condition is satisfied. Otherwise, we need to copy the individuals in NDSet to P and continue to the next round of evolution.Figure 3
General flow of multiobjective evolutionary algorithm based on Pareto.


## 4.2. Individual Evaluation Method

Different from the single-objective optimization problem, the multiobjective optimization problem needs vector comparison. The multiobjective optimization strategy adopted in this paper is similar to the method of NGSA-II [25–27], but some changes have been made. All scheduling schemes are divided into three types. For any scheduling s of the first type, it can complete all tasks on the premise of satisfying constraints (10) and (11). Obviously, this type of scheduling is ideal, so it is set to the highest rank 0, namely ranks = 0. The scheduling of the same level is ranked according to the task completion time, and the higher priority value has little task completion time. The second type is also to satisfy constraints (10) and (11), but it can only complete a part of offloaded tasks. We regard each scheduling s of this type as an individual in the evolutionary algorithm. According to the NSGA-II method [28], all individuals in the first nondominated front are found firstly. In order to find the individuals in the next nondominated front, the solutions of the first front are discounted temporarily, and the above procedure is repeated. The rank of the scheduling s in the first front is 1, namely ranks = 1. Similarly, the rank of the scheduling in the second front is 2, so back and forth. Compared with the crowding distance of individuals in the same rank, individuals with higher aggregation density have a higher priority value. The third type is the scheduling that violates constraints (10) and (11). Assuming that the second type is divided into n ranks, for the scheduling s that belongs to the third type, its rank is n + 1, namely ranks = n + 1. The scheduling that violates constraint (10) to a lower degree has a higher priority. According to the abovementioned method, suppose there are scheduling p and scheduling q, the comparison strategy between them is described in Algorithm 1.Algorithm1: Individual evaluation algorithm (IEA).
(1)
If (rankp < rankq)(2)
p≻q(3)
If (rankp = rankq= 0 and tp < tq)(4)
p≻q(5)
If (rankp = rankq = n+1 and∑j∈csmax∑i∈Dpij−Mj,0<∑j∈csmax∑i∈Dqij−Mj,0)(6)
p≻q(7)
If (1 ≤ rankp ≤ n and 1 ≤ rankq ≤ n and dp > dq)(8)
p≻q(dp and dq represent the aggregation density of p and q, respectively)


## 4.3. Our Algorithm

### 4.3.1. Bat Algorithm

As mentioned above, the basis of multiobjective evolutionary algorithm is an evolutionary algorithm. At present, the most commonly used evolutionary algorithms include simulated annealing algorithm, genetic algorithm, distribution estimation algorithm, and particle swarm optimization algorithm. However, in these algorithms, the individual’s movement mode does not adopt the position update mode of the deterministic algorithm. That is, “only move to the solution that is better than the current position” method is used. Yang [29] proposed a bat algorithm (BA) that adopts the method of “only move to the solution which is better than the current position.” BA simulates the behavior of microbats in nature, which uses echolocation to hunt prey and avoid obstacles. Compared with other evolutionary algorithms, BA has the characteristics of higher computational efficiency, stronger optimization ability, and robustness.According to the bat’s echolocation behavior and its correlation with objective optimization, the parameters and updating equations ofn bats during flight are given below: Suppose that there are n virtual bats living in the domain. In the t-th generation, the information containing the i-th (i = 1, 2, …, n) bat can be expressed as five tuples: xi⟶t,vi⟶t,frit,Ait,rit, where xi⟶t=xi1t,xi2t,…,xikt,…,xiNt denotes the position information of the t-th generation of the i-th bat and a solution of the search space, the speed vi⟶t=vi1t,vi2t,…,vikt,…,viNt represents the velocity direction of the i-th bat in the t-th generation, while frequency fri (t), loudness Ai (t), and pulse emission frequency ri (t) are three parameters needed by i-th bat in the algorithm. In the (t+1)-th generation, each bat firstly updates its speed according to the formula, which is described as follows:(20)vit+1=vit+xit−pt⋅fritm,where p⟶t=p1t,p2t,…,pkt,…,pNt indicates the historical optimal position of the previous t generations, while xit−ptfrit represents the effect of the deviation between xi⟶t and p⟶t on the speed of the next generation, and the frequency fri (t) is randomly generated according to the following formula:(21)frit=frmin+frmax−frmin⋅rand1,where rand1 is a uniformly distributed random number in (0, 1) and the two parameters frmax and frmin are the preset as the upper and lower frequency limits, respectively.On this basis, when each bat performs a global or local search, the selection of its search mode is determined in a random way. It means random numberrand2, which is uniformly distributed between 0 and 1 needs to be determined. If rank2<r1t, the i-th bat will search for food in the following global search mode:(22)xi′t+1=xit+vit+1.Otherwise, thei-th bat will perform a local search according to the following formula:(23)xi′t+1=pt+εi⋅At¯,where εi is a uniformly distributed random number belongs to (−1, 1) and At¯=∑j=1nAjt/n is the average loudness of the bat at the t-th time.After the new locationxi′⟶t+1=xi1′t,xi2′t,…,xik′t,…,xiN′t is calculated, the bat will be judged whether to move instead of moving to the new location immediately according to the following update rules:(24)xi⟶t+1=xi′⟶t+1,rand3<Aitandfxi′⟶t+1<fxi⟶t,xi⟶t,else.When updating the position, a uniformly distributed random numberrand3 that belongs to (0, 1) was selected. When rand3<Ait and fxi′⟶t+1<fxi⟶t are satisfied simultaneously, the i-th bat updates the location to xi⟶t+1. Otherwise, the location of i-th bat is still xi⟶t without updating the location to xi⟶t+1.The update formula of the pulse emission rateri (t + 1) is as follows:(25)rit+1=ri0⋅1−e−γt.LoudnessAi(t + 1) is updated as follows:(26)Ait+1=αAit,where α > 0 and γ > 0 are both preset parameters, Ai(0) is the initial value of loudness, and ri (0) is the initial value of pulse emission rate. In the paper, Ai(0) is random selected from [0, 1] and ri (0) = 0.1.In the basic bat algorithm, equations (20) and (22) represent the global search mechanism of the algorithm, while equation (23) represents the local search mechanism of the bat algorithm.


### 4.3.2. Hybrid Immune Bat Algorithm

It was shown that the optimization ability of BA mainly depends on the interaction and influence between bat individuals. Due to the lack of a mutation mechanism, it is difficult for individuals to get rid of the constraint of a local extreme value. Moreover, in the evolution process, the super bats in the population may attract other individuals to gather around them quickly, which results in a significant decline in population diversity. Meanwhile, the bat individuals are getting closer to the optimal individuals of the population in order that the population has lost the ability of further evolution [30]. In this paper, the clonal selection mechanism in the artificial immune system is introduced, which can enhance the diversity of bat population, enhance the ability of wide range variation, and increase the convergence rate.Suppose that an individual populationB=b1,b2,…,bn is obtained through the process of the bat algorithm, which is a temporary clonal population. Each bat i (i = 1, 2, …, n) in the temporary clonal population is regarded as an antibody. The specific methods are as follows:Step 1: thek (k < n) antibody individuals selected in a random way were grouped into subpopulation Sub1=b1′,b2′,…,bk′. And clone and copy subpopulation Sub1. The cloning operator is described as follows:(27)Sub2=TcSub1=TCb1′,TCb2′,…,TCbk′,whereTCbi′=qi×bi′,i=1,2,…,k, where qi is the number of clones of bi′, which is proportional to the fitness of bi′. A new population Sub2 was generated by cloning.Step 2: implement high-frequency mutation for each individual in group Sub2, and the mutation operator is adaptive, which is related to both evolution generations and individual fitness. For any bi′=bi1′,bi2′,…,bij′,…,bin′, the mutation formula is given as follows:(28)bij′new=∼bij′old,rand4<ηtandrand5<Δ,bij′old,else.ηt in formula (28) is given as follows:(29)ηt=1−r11−t/Tb,whereb is a positive constant, r1∈0,1. In the early stages of evolution, r11−t/Tb was smaller, ηt≈1, but in the later stage of evolution, when t approaches T, ηt≈0, local search is carried out in a small space.Furthermore,Δ in formula (28) is formulated as follows:(30)Δ=1−r2Rλ,wherer2∈0,1, the parameter λ plays the role of adjusting the search area, and the value is generally 2–5 [31]. R in the above formula is formulated as follows:(31)R=1−fitbi′fitmax,wherefitbi′ represents the fitness of antibody bi′ and fitmax is the maximum fitness value, which is the aggregation density of the individual. Obviously, for those with higher fitness, the Δ value is smaller, and the mutation possibility is small, while for those with lower fitness, the mutation possibility is relatively large.Step 3: immune clonal selection: the best individual from the clonal mutation individuals is selected for the next generation. The full algorithm of HIBSA is given in Algorithm2.


### 4.3.3. The Full Algorithm of HIBSA

Algorithm2: Hybrid immune and bat scheduling algorithm (HIBSA).
(1)
The scheduling populationP0 is randomly generated, the population size is n, and the initialization generation t = 0(2)
According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 inP are put into the set P0t and P1t, respectively(3)
If (P0t≠Φ)select the optimal solution inP0t as the result and the algorithm ends(4)
else(5)
while (t < T)(6)
A solution is randomly selected fromP1t as the historical optimal position of the current population, and BA is implemented for Pt to get PBt(7)
Clear setP0t, P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(8)
If (P0t≠Φ)(9)
select the optimal solution inP0t as the result and the algorithm ends(10)
else(11)
ForPBt, the immune clonal selection algorithm is implemented to get PIt(12)
Clear setP0t and P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(13)
If (P0t≠Φ)(14)
select the optimal solution inP0t as the result and the algorithm ends(15)
else(16)
According to the individual evaluation algorithm, put the firstn individuals in the set PBt∪PIt into Pt+1(17)
t = t + 1(18)
end if(19)
end if(20)
end while(21)
end if(22)
select a solution randomly fromP1t as the result and the algorithm ends


## 4.3.1. Bat Algorithm

As mentioned above, the basis of multiobjective evolutionary algorithm is an evolutionary algorithm. At present, the most commonly used evolutionary algorithms include simulated annealing algorithm, genetic algorithm, distribution estimation algorithm, and particle swarm optimization algorithm. However, in these algorithms, the individual’s movement mode does not adopt the position update mode of the deterministic algorithm. That is, “only move to the solution that is better than the current position” method is used. Yang [29] proposed a bat algorithm (BA) that adopts the method of “only move to the solution which is better than the current position.” BA simulates the behavior of microbats in nature, which uses echolocation to hunt prey and avoid obstacles. Compared with other evolutionary algorithms, BA has the characteristics of higher computational efficiency, stronger optimization ability, and robustness.According to the bat’s echolocation behavior and its correlation with objective optimization, the parameters and updating equations ofn bats during flight are given below: Suppose that there are n virtual bats living in the domain. In the t-th generation, the information containing the i-th (i = 1, 2, …, n) bat can be expressed as five tuples: xi⟶t,vi⟶t,frit,Ait,rit, where xi⟶t=xi1t,xi2t,…,xikt,…,xiNt denotes the position information of the t-th generation of the i-th bat and a solution of the search space, the speed vi⟶t=vi1t,vi2t,…,vikt,…,viNt represents the velocity direction of the i-th bat in the t-th generation, while frequency fri (t), loudness Ai (t), and pulse emission frequency ri (t) are three parameters needed by i-th bat in the algorithm. In the (t+1)-th generation, each bat firstly updates its speed according to the formula, which is described as follows:(20)vit+1=vit+xit−pt⋅fritm,where p⟶t=p1t,p2t,…,pkt,…,pNt indicates the historical optimal position of the previous t generations, while xit−ptfrit represents the effect of the deviation between xi⟶t and p⟶t on the speed of the next generation, and the frequency fri (t) is randomly generated according to the following formula:(21)frit=frmin+frmax−frmin⋅rand1,where rand1 is a uniformly distributed random number in (0, 1) and the two parameters frmax and frmin are the preset as the upper and lower frequency limits, respectively.On this basis, when each bat performs a global or local search, the selection of its search mode is determined in a random way. It means random numberrand2, which is uniformly distributed between 0 and 1 needs to be determined. If rank2<r1t, the i-th bat will search for food in the following global search mode:(22)xi′t+1=xit+vit+1.Otherwise, thei-th bat will perform a local search according to the following formula:(23)xi′t+1=pt+εi⋅At¯,where εi is a uniformly distributed random number belongs to (−1, 1) and At¯=∑j=1nAjt/n is the average loudness of the bat at the t-th time.After the new locationxi′⟶t+1=xi1′t,xi2′t,…,xik′t,…,xiN′t is calculated, the bat will be judged whether to move instead of moving to the new location immediately according to the following update rules:(24)xi⟶t+1=xi′⟶t+1,rand3<Aitandfxi′⟶t+1<fxi⟶t,xi⟶t,else.When updating the position, a uniformly distributed random numberrand3 that belongs to (0, 1) was selected. When rand3<Ait and fxi′⟶t+1<fxi⟶t are satisfied simultaneously, the i-th bat updates the location to xi⟶t+1. Otherwise, the location of i-th bat is still xi⟶t without updating the location to xi⟶t+1.The update formula of the pulse emission rateri (t + 1) is as follows:(25)rit+1=ri0⋅1−e−γt.LoudnessAi(t + 1) is updated as follows:(26)Ait+1=αAit,where α > 0 and γ > 0 are both preset parameters, Ai(0) is the initial value of loudness, and ri (0) is the initial value of pulse emission rate. In the paper, Ai(0) is random selected from [0, 1] and ri (0) = 0.1.In the basic bat algorithm, equations (20) and (22) represent the global search mechanism of the algorithm, while equation (23) represents the local search mechanism of the bat algorithm.


## 4.3.2. Hybrid Immune Bat Algorithm

It was shown that the optimization ability of BA mainly depends on the interaction and influence between bat individuals. Due to the lack of a mutation mechanism, it is difficult for individuals to get rid of the constraint of a local extreme value. Moreover, in the evolution process, the super bats in the population may attract other individuals to gather around them quickly, which results in a significant decline in population diversity. Meanwhile, the bat individuals are getting closer to the optimal individuals of the population in order that the population has lost the ability of further evolution [30]. In this paper, the clonal selection mechanism in the artificial immune system is introduced, which can enhance the diversity of bat population, enhance the ability of wide range variation, and increase the convergence rate.Suppose that an individual populationB=b1,b2,…,bn is obtained through the process of the bat algorithm, which is a temporary clonal population. Each bat i (i = 1, 2, …, n) in the temporary clonal population is regarded as an antibody. The specific methods are as follows:Step 1: thek (k < n) antibody individuals selected in a random way were grouped into subpopulation Sub1=b1′,b2′,…,bk′. And clone and copy subpopulation Sub1. The cloning operator is described as follows:(27)Sub2=TcSub1=TCb1′,TCb2′,…,TCbk′,whereTCbi′=qi×bi′,i=1,2,…,k, where qi is the number of clones of bi′, which is proportional to the fitness of bi′. A new population Sub2 was generated by cloning.Step 2: implement high-frequency mutation for each individual in group Sub2, and the mutation operator is adaptive, which is related to both evolution generations and individual fitness. For any bi′=bi1′,bi2′,…,bij′,…,bin′, the mutation formula is given as follows:(28)bij′new=∼bij′old,rand4<ηtandrand5<Δ,bij′old,else.ηt in formula (28) is given as follows:(29)ηt=1−r11−t/Tb,whereb is a positive constant, r1∈0,1. In the early stages of evolution, r11−t/Tb was smaller, ηt≈1, but in the later stage of evolution, when t approaches T, ηt≈0, local search is carried out in a small space.Furthermore,Δ in formula (28) is formulated as follows:(30)Δ=1−r2Rλ,wherer2∈0,1, the parameter λ plays the role of adjusting the search area, and the value is generally 2–5 [31]. R in the above formula is formulated as follows:(31)R=1−fitbi′fitmax,wherefitbi′ represents the fitness of antibody bi′ and fitmax is the maximum fitness value, which is the aggregation density of the individual. Obviously, for those with higher fitness, the Δ value is smaller, and the mutation possibility is small, while for those with lower fitness, the mutation possibility is relatively large.Step 3: immune clonal selection: the best individual from the clonal mutation individuals is selected for the next generation. The full algorithm of HIBSA is given in Algorithm2.


## 4.3.3. The Full Algorithm of HIBSA

Algorithm2: Hybrid immune and bat scheduling algorithm (HIBSA).
(1)
The scheduling populationP0 is randomly generated, the population size is n, and the initialization generation t = 0(2)
According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 inP are put into the set P0t and P1t, respectively(3)
If (P0t≠Φ)select the optimal solution inP0t as the result and the algorithm ends(4)
else(5)
while (t < T)(6)
A solution is randomly selected fromP1t as the historical optimal position of the current population, and BA is implemented for Pt to get PBt(7)
Clear setP0t, P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(8)
If (P0t≠Φ)(9)
select the optimal solution inP0t as the result and the algorithm ends(10)
else(11)
ForPBt, the immune clonal selection algorithm is implemented to get PIt(12)
Clear setP0t and P1t. According to the individual evaluation algorithm, all the individuals of rank 0 and rank 1 in the set PBt are put into the set P0t and P1t, respectively(13)
If (P0t≠Φ)(14)
select the optimal solution inP0t as the result and the algorithm ends(15)
else(16)
According to the individual evaluation algorithm, put the firstn individuals in the set PBt∪PIt into Pt+1(17)
t = t + 1(18)
end if(19)
end if(20)
end while(21)
end if(22)
select a solution randomly fromP1t as the result and the algorithm ends


## 4.4. Time Complexity Analysis

In this section, the time complexity of HIBSA is analyzed. Based on the flowchart in Figure3, assuming that the population P size, the new group R size are both N, the number of objectives is M (in fact, M is 2 in this paper). The number of decision valuables is m×n (n is the number of IMDs and m is the number of MEC servers). The basic operators and their time complexity analysis are given as follows:(1)
Generate initial populationP. Population initialization is to generate individuals randomly and calculate the values of objectives, so the time complexity is O (m × n × N) + O (M × N).(2)
A new groupR was obtained by EA evolution. In this paper, the evolutionary algorithm combines the bat algorithm and the immune algorithm together. In both these two algorithms, identifying nondominated individuals was needed. When identifying nondominated individuals, individuals are compared with each other based on the objectives. Hence, the time complexity is O (M × N2).(3)
Construct nondominated set (NDSet) of P∪R. As these operators are performed in the P∪R, so the time complexity of nondominated individuals identification isO (M × (2N)2)(4)
Adjust the scale of NDSet to meet the requirements of distribution. In this stage, adjust operator selects nondominated individuals with greater fitness values to preserve. Therefore, in the assignment of fitness values, the time complexity of the crowding-distance assignment isO (M × N × log (N)).Based on the above analysis, in a single generation, the worst time complexity can be written as follows:(32)OM×N2.


## 5. Experimental Evaluation

In this section, we evaluate the performance of HIBSA through simulations and compare its performance against several algorithms.


### 5.1. Verification Policies

Suppose that at one time, there aren mobile devices and m computing servers, and each device currently has a task queue to be offloaded. Assuming that on the t-th slot, the k-th task Tik in the current queue on the i-th device is ready to be offloaded. If the offloading is successful, the device intends to offload the next scheduling task in the queue at the (t + 1)-th slot, which means the (k + 1)-th task Tik+1 prepares to be offloaded. However, if task Tik fails to be offloaded at the t-th slot, the current task Tik can be omitted or wait to be scheduled at the (t + 1)-th slot, which is decided by whether the task is a real-time task or not. In order to verify the performance of the proposed scheduling algorithm, it is compared with sequential scheduling algorithm (SSA), random scheduling algorithm (RSA), time priority greedy scheduling algorithm (TPGSA), and weight priority greedy scheduling algorithm (WPGSA). The comparison algorithms are described as follows:(1)
SSA: the scheduling is carried out according to the equipment number, and the one with a small equipment number is scheduled first.(2)
RSA: in this method, each task is scheduled randomly.(3)
TPGSA: at one time, all tasks to be scheduled are sorted by the expected completion time. The shorter the task completion time, the earlier the task is scheduled.(4)
WPGSA: at one time, all the tasks to be scheduled are sorted by the task weight.The experimental platform used in this paper is MATLAB 2016a [32], and the main simulation parameters are presented in Table 3.Table 3
Simulation parameters for task offloading.
ParameterValueNotem3–5Number of MEC serversdnum[1–7] MbThe size of the input dataucc [20]1,000 cycles/bitUnit CPU cycles (per bit)F8 GHzThe CPU cycle frequency of CSulc0.05 msUnit latency costTC5 msMaximum latencyMj5 tasksMEC server computing capacitypitx0.1 WFixed transmit power of IMDφ40 mJSafe discharge thresholdN10Number of IMDswi[1–100]Task weightfrmax [33–36]2The upper frequency of batfrmin [33–36]0The lower frequency of batα [37–39]0.9The update parameter of the loudness of batγ [37–39]0.1The update parameter of the pulse emission rate of batN30Number of initialization populationsGen30Number of generations


### 5.2. Experimental Result

In this section, experimental results are given. Due to the limitation of space, we only show the experimental data of the first 20 time slots.


#### 5.2.1. Execution Time Analysis

The results about total task execution time in the first 20 time slots obtained by the five algorithms are shown in Table4.Table 4
The total task execution time in the first 20 time slots.
T1234567891011121314151617181920SSA66120167.33228293.33346.67419.33485.33558618690749.33815.33880.679409941,059.331,112.671,178.671,244RSA66.67130196.67262324.67380454.67535.33604668.67738810.67878.67949.331,015.331,088.671,167.331,2341,3161,396TPGSA54.00107.33160.67220.67280.67340.00406.00466.00539.33605.33670.67736.00796.00862.00926.67992.671,058.671,118.001,171.331,236.67WPGSA73.33120.67167.33240.67313.33360.00407.33480.00534.00607.33680.00732.67804.00876.00949.331,020.671,073.331,146.001,186.671,258.67HIBSA5495.33134.67188261.33334370.67428501.33552.67622.67689.33762.67835.33887.33940999.331,072.671,108.671,174We take the task completion time of TPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the task completion time of these five algorithms at 20 time slots is shown in Figure4:Figure 4
Comparison of task execution time ratio of various algorithms of 20 time slots.We can see from Figure4 that SSA, RSA, and WPGSA are all not as good as TPGSA in task execution time. However, the performance of HIBSA is better than TPGSA. As shown in Figure 5, if the average execution time of the TPGSA algorithm is 1, the average task execution time of the SSA algorithm is 1.04; the average scheduling time of the RSA algorithm is 1.13; and the average scheduling time of the WPGSA algorithm is 1.05. However, the task execution time of HIBSA is only 0.93. That is, the scheduling time of the algorithm proposed in this paper is only 93% of the TPGSA algorithm.Figure 5
Comparison of average task execution time ratio of various algorithms.


#### 5.2.2. Weight Analysis

The results about the sum of task weight in the first 20 time slots of the five algorithms are shown in Table5.Table 5
The sum of task weight in the first 20 time slots.
T1234567891011121314151617181920SSA3126268511,2541,4851,7182,1282,4402,8503,1723,4923,7334,0634,3034,5444,8495,0895,3225,6345,874RSA2033165376509621,1761,3961,5971,8091,9312,2422,4442,6652,6962,7373,2373,6373,7503,9604,071TPGSA3145477711,0841,4061,6381,9502,2632,7633,0843,3153,5553,8774,1984,3484,6604,9815,2135,4465,686WPGSA5007258691,3691,7791,9232,1482,5582,8723,3723,7823,9254,1554,4754,9755,2055,3485,7585,8946,214HIBSA3147479821,2061,7062,1162,2612,4842,9843,0183,4193,8304,3304,7404,8114,9545,1775,6775,9036,134We take the weight of WPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the weight of each algorithm at 20 time slots is shown in Figure6:Figure 6
Comparison of task weight ratio of various algorithms of 20 time slots.Taking WPGSA as the benchmark, SSA, RSA, and TPGSA are not as good as WPGSA in weight, while HIBSA proposed in this paper is better than WPGSA sometimes and slightly worse than WPGSA. As shown in Figure7, if the average scheduling weight of WPGSA is 1, the average scheduling weight of SSA is 0.92; the average scheduling weight of RSA is only 0.59; and the average scheduling weight of TPGSA is 0.87, while the scheduling weight of HIBSA is slightly worse than WPGSA. According to the scheduling strategy proposed in the paper, the scheduling weight of the proposed algorithm is 98% of WPGSA.Figure 7
Comparison of average task weight ratio of various algorithms.


#### 5.2.3. Analysis of the Total Number of Offloaded Tasks

The total number of tasks offloaded by each device in the first 20 time slots by using different algorithms is shown in Table6Table 6
The total number of scheduled tasks for 10 mobile devices in the first 20 time slots.
DEV ID12345678910SumSSA2020202020179510132RSA1211881210896993TPGSA2020201918187740133WPGSA18171917131018855130HIBSA16181414131313151311140As shown in Table6, 10 devices offload 132 tasks in 20 time slots by using SSA. RSA algorithm offloads 93 tasks only. TPGSA offloads 133 tasks. WPGSA offloads 130 tasks, while HIBSA has the largest number of offloaded tasks. This is because the algorithm proposed in this paper is a multiobjective optimization algorithm, and it also takes fairness into consideration in task scheduling. Figure 8 is a comparison box plot of the number of scheduling devices using these five algorithms. As shown in Figure 8, the quartile deviation between the SSA algorithm and the TPGSA algorithm is large, which results in the unfairness of the algorithm for the task scheduling of each device. Some devices offload all generated tasks, while some devices have no tasks to offload. Obviously, the quartile deviation of HIBSA proposed in the paper is only 1.75, which is better than the other four algorithms.Figure 8
Comparison of the number of tasks offloaded by different algorithms.


#### 5.2.4. Scalability Analysis

As analyzed in Section4.4, the performance of the algorithm proposed in this paper is only related to the number N of the initialization population. However, some studies have shown that the setting of the number of initialization population should be related to the length of the problem. In this paper, the length of the problem is the product (m × n) of the number of available MEC servers and the number of IMDs. That is, with the increase of the number of servers and the number of IMDs, the number of initialization population should be increased to meet the diversity of the population.In the algorithm proposed in this paper, we adopt the method of adding diversity judgment in the iterative execution of the algorithm. If the population diversity is lower than the threshold preset, we can improve the population diversity through population diversity regulation. As shown in Figure9, when the number of available servers is increased from 3 to 5, the number of solution space will grow from 230 to 250 rapidly. However, the number of initialization populations we set is all 30. The experimental results indicate that the solutions obtained by HIBSA are not affected. They are significantly improved in terms of tasks execution time, the total weight of tasks, and the number of offloaded tasks, which shows the scalability of the algorithm.Figure 9
the scalability of the algorithm: (a) tasks execution time, (b) the total weight of tasks, and (c) the number of tasks offloading.
(a)(b)(c)


## 5.1. Verification Policies

Suppose that at one time, there aren mobile devices and m computing servers, and each device currently has a task queue to be offloaded. Assuming that on the t-th slot, the k-th task Tik in the current queue on the i-th device is ready to be offloaded. If the offloading is successful, the device intends to offload the next scheduling task in the queue at the (t + 1)-th slot, which means the (k + 1)-th task Tik+1 prepares to be offloaded. However, if task Tik fails to be offloaded at the t-th slot, the current task Tik can be omitted or wait to be scheduled at the (t + 1)-th slot, which is decided by whether the task is a real-time task or not. In order to verify the performance of the proposed scheduling algorithm, it is compared with sequential scheduling algorithm (SSA), random scheduling algorithm (RSA), time priority greedy scheduling algorithm (TPGSA), and weight priority greedy scheduling algorithm (WPGSA). The comparison algorithms are described as follows:(1)
SSA: the scheduling is carried out according to the equipment number, and the one with a small equipment number is scheduled first.(2)
RSA: in this method, each task is scheduled randomly.(3)
TPGSA: at one time, all tasks to be scheduled are sorted by the expected completion time. The shorter the task completion time, the earlier the task is scheduled.(4)
WPGSA: at one time, all the tasks to be scheduled are sorted by the task weight.The experimental platform used in this paper is MATLAB 2016a [32], and the main simulation parameters are presented in Table 3.Table 3
Simulation parameters for task offloading.
ParameterValueNotem3–5Number of MEC serversdnum[1–7] MbThe size of the input dataucc [20]1,000 cycles/bitUnit CPU cycles (per bit)F8 GHzThe CPU cycle frequency of CSulc0.05 msUnit latency costTC5 msMaximum latencyMj5 tasksMEC server computing capacitypitx0.1 WFixed transmit power of IMDφ40 mJSafe discharge thresholdN10Number of IMDswi[1–100]Task weightfrmax [33–36]2The upper frequency of batfrmin [33–36]0The lower frequency of batα [37–39]0.9The update parameter of the loudness of batγ [37–39]0.1The update parameter of the pulse emission rate of batN30Number of initialization populationsGen30Number of generations


## 5.2. Experimental Result

In this section, experimental results are given. Due to the limitation of space, we only show the experimental data of the first 20 time slots.


### 5.2.1. Execution Time Analysis

The results about total task execution time in the first 20 time slots obtained by the five algorithms are shown in Table4.Table 4
The total task execution time in the first 20 time slots.
T1234567891011121314151617181920SSA66120167.33228293.33346.67419.33485.33558618690749.33815.33880.679409941,059.331,112.671,178.671,244RSA66.67130196.67262324.67380454.67535.33604668.67738810.67878.67949.331,015.331,088.671,167.331,2341,3161,396TPGSA54.00107.33160.67220.67280.67340.00406.00466.00539.33605.33670.67736.00796.00862.00926.67992.671,058.671,118.001,171.331,236.67WPGSA73.33120.67167.33240.67313.33360.00407.33480.00534.00607.33680.00732.67804.00876.00949.331,020.671,073.331,146.001,186.671,258.67HIBSA5495.33134.67188261.33334370.67428501.33552.67622.67689.33762.67835.33887.33940999.331,072.671,108.671,174We take the task completion time of TPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the task completion time of these five algorithms at 20 time slots is shown in Figure4:Figure 4
Comparison of task execution time ratio of various algorithms of 20 time slots.We can see from Figure4 that SSA, RSA, and WPGSA are all not as good as TPGSA in task execution time. However, the performance of HIBSA is better than TPGSA. As shown in Figure 5, if the average execution time of the TPGSA algorithm is 1, the average task execution time of the SSA algorithm is 1.04; the average scheduling time of the RSA algorithm is 1.13; and the average scheduling time of the WPGSA algorithm is 1.05. However, the task execution time of HIBSA is only 0.93. That is, the scheduling time of the algorithm proposed in this paper is only 93% of the TPGSA algorithm.Figure 5
Comparison of average task execution time ratio of various algorithms.


### 5.2.2. Weight Analysis

The results about the sum of task weight in the first 20 time slots of the five algorithms are shown in Table5.Table 5
The sum of task weight in the first 20 time slots.
T1234567891011121314151617181920SSA3126268511,2541,4851,7182,1282,4402,8503,1723,4923,7334,0634,3034,5444,8495,0895,3225,6345,874RSA2033165376509621,1761,3961,5971,8091,9312,2422,4442,6652,6962,7373,2373,6373,7503,9604,071TPGSA3145477711,0841,4061,6381,9502,2632,7633,0843,3153,5553,8774,1984,3484,6604,9815,2135,4465,686WPGSA5007258691,3691,7791,9232,1482,5582,8723,3723,7823,9254,1554,4754,9755,2055,3485,7585,8946,214HIBSA3147479821,2061,7062,1162,2612,4842,9843,0183,4193,8304,3304,7404,8114,9545,1775,6775,9036,134We take the weight of WPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the weight of each algorithm at 20 time slots is shown in Figure6:Figure 6
Comparison of task weight ratio of various algorithms of 20 time slots.Taking WPGSA as the benchmark, SSA, RSA, and TPGSA are not as good as WPGSA in weight, while HIBSA proposed in this paper is better than WPGSA sometimes and slightly worse than WPGSA. As shown in Figure7, if the average scheduling weight of WPGSA is 1, the average scheduling weight of SSA is 0.92; the average scheduling weight of RSA is only 0.59; and the average scheduling weight of TPGSA is 0.87, while the scheduling weight of HIBSA is slightly worse than WPGSA. According to the scheduling strategy proposed in the paper, the scheduling weight of the proposed algorithm is 98% of WPGSA.Figure 7
Comparison of average task weight ratio of various algorithms.


### 5.2.3. Analysis of the Total Number of Offloaded Tasks

The total number of tasks offloaded by each device in the first 20 time slots by using different algorithms is shown in Table6Table 6
The total number of scheduled tasks for 10 mobile devices in the first 20 time slots.
DEV ID12345678910SumSSA2020202020179510132RSA1211881210896993TPGSA2020201918187740133WPGSA18171917131018855130HIBSA16181414131313151311140As shown in Table6, 10 devices offload 132 tasks in 20 time slots by using SSA. RSA algorithm offloads 93 tasks only. TPGSA offloads 133 tasks. WPGSA offloads 130 tasks, while HIBSA has the largest number of offloaded tasks. This is because the algorithm proposed in this paper is a multiobjective optimization algorithm, and it also takes fairness into consideration in task scheduling. Figure 8 is a comparison box plot of the number of scheduling devices using these five algorithms. As shown in Figure 8, the quartile deviation between the SSA algorithm and the TPGSA algorithm is large, which results in the unfairness of the algorithm for the task scheduling of each device. Some devices offload all generated tasks, while some devices have no tasks to offload. Obviously, the quartile deviation of HIBSA proposed in the paper is only 1.75, which is better than the other four algorithms.Figure 8
Comparison of the number of tasks offloaded by different algorithms.


### 5.2.4. Scalability Analysis

As analyzed in Section4.4, the performance of the algorithm proposed in this paper is only related to the number N of the initialization population. However, some studies have shown that the setting of the number of initialization population should be related to the length of the problem. In this paper, the length of the problem is the product (m × n) of the number of available MEC servers and the number of IMDs. That is, with the increase of the number of servers and the number of IMDs, the number of initialization population should be increased to meet the diversity of the population.In the algorithm proposed in this paper, we adopt the method of adding diversity judgment in the iterative execution of the algorithm. If the population diversity is lower than the threshold preset, we can improve the population diversity through population diversity regulation. As shown in Figure9, when the number of available servers is increased from 3 to 5, the number of solution space will grow from 230 to 250 rapidly. However, the number of initialization populations we set is all 30. The experimental results indicate that the solutions obtained by HIBSA are not affected. They are significantly improved in terms of tasks execution time, the total weight of tasks, and the number of offloaded tasks, which shows the scalability of the algorithm.Figure 9
the scalability of the algorithm: (a) tasks execution time, (b) the total weight of tasks, and (c) the number of tasks offloading.
(a)(b)(c)


## 5.2.1. Execution Time Analysis

The results about total task execution time in the first 20 time slots obtained by the five algorithms are shown in Table4.Table 4
The total task execution time in the first 20 time slots.
T1234567891011121314151617181920SSA66120167.33228293.33346.67419.33485.33558618690749.33815.33880.679409941,059.331,112.671,178.671,244RSA66.67130196.67262324.67380454.67535.33604668.67738810.67878.67949.331,015.331,088.671,167.331,2341,3161,396TPGSA54.00107.33160.67220.67280.67340.00406.00466.00539.33605.33670.67736.00796.00862.00926.67992.671,058.671,118.001,171.331,236.67WPGSA73.33120.67167.33240.67313.33360.00407.33480.00534.00607.33680.00732.67804.00876.00949.331,020.671,073.331,146.001,186.671,258.67HIBSA5495.33134.67188261.33334370.67428501.33552.67622.67689.33762.67835.33887.33940999.331,072.671,108.671,174We take the task completion time of TPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the task completion time of these five algorithms at 20 time slots is shown in Figure4:Figure 4
Comparison of task execution time ratio of various algorithms of 20 time slots.We can see from Figure4 that SSA, RSA, and WPGSA are all not as good as TPGSA in task execution time. However, the performance of HIBSA is better than TPGSA. As shown in Figure 5, if the average execution time of the TPGSA algorithm is 1, the average task execution time of the SSA algorithm is 1.04; the average scheduling time of the RSA algorithm is 1.13; and the average scheduling time of the WPGSA algorithm is 1.05. However, the task execution time of HIBSA is only 0.93. That is, the scheduling time of the algorithm proposed in this paper is only 93% of the TPGSA algorithm.Figure 5
Comparison of average task execution time ratio of various algorithms.


## 5.2.2. Weight Analysis

The results about the sum of task weight in the first 20 time slots of the five algorithms are shown in Table5.Table 5
The sum of task weight in the first 20 time slots.
T1234567891011121314151617181920SSA3126268511,2541,4851,7182,1282,4402,8503,1723,4923,7334,0634,3034,5444,8495,0895,3225,6345,874RSA2033165376509621,1761,3961,5971,8091,9312,2422,4442,6652,6962,7373,2373,6373,7503,9604,071TPGSA3145477711,0841,4061,6381,9502,2632,7633,0843,3153,5553,8774,1984,3484,6604,9815,2135,4465,686WPGSA5007258691,3691,7791,9232,1482,5582,8723,3723,7823,9254,1554,4754,9755,2055,3485,7585,8946,214HIBSA3147479821,2061,7062,1162,2612,4842,9843,0183,4193,8304,3304,7404,8114,9545,1775,6775,9036,134We take the weight of WPGSA as the benchmark and normalize its value to 1. Thus, the comparison of the results about the weight of each algorithm at 20 time slots is shown in Figure6:Figure 6
Comparison of task weight ratio of various algorithms of 20 time slots.Taking WPGSA as the benchmark, SSA, RSA, and TPGSA are not as good as WPGSA in weight, while HIBSA proposed in this paper is better than WPGSA sometimes and slightly worse than WPGSA. As shown in Figure7, if the average scheduling weight of WPGSA is 1, the average scheduling weight of SSA is 0.92; the average scheduling weight of RSA is only 0.59; and the average scheduling weight of TPGSA is 0.87, while the scheduling weight of HIBSA is slightly worse than WPGSA. According to the scheduling strategy proposed in the paper, the scheduling weight of the proposed algorithm is 98% of WPGSA.Figure 7
Comparison of average task weight ratio of various algorithms.


## 5.2.3. Analysis of the Total Number of Offloaded Tasks

The total number of tasks offloaded by each device in the first 20 time slots by using different algorithms is shown in Table6Table 6
The total number of scheduled tasks for 10 mobile devices in the first 20 time slots.
DEV ID12345678910SumSSA2020202020179510132RSA1211881210896993TPGSA2020201918187740133WPGSA18171917131018855130HIBSA16181414131313151311140As shown in Table6, 10 devices offload 132 tasks in 20 time slots by using SSA. RSA algorithm offloads 93 tasks only. TPGSA offloads 133 tasks. WPGSA offloads 130 tasks, while HIBSA has the largest number of offloaded tasks. This is because the algorithm proposed in this paper is a multiobjective optimization algorithm, and it also takes fairness into consideration in task scheduling. Figure 8 is a comparison box plot of the number of scheduling devices using these five algorithms. As shown in Figure 8, the quartile deviation between the SSA algorithm and the TPGSA algorithm is large, which results in the unfairness of the algorithm for the task scheduling of each device. Some devices offload all generated tasks, while some devices have no tasks to offload. Obviously, the quartile deviation of HIBSA proposed in the paper is only 1.75, which is better than the other four algorithms.Figure 8
Comparison of the number of tasks offloaded by different algorithms.


## 5.2.4. Scalability Analysis

As analyzed in Section4.4, the performance of the algorithm proposed in this paper is only related to the number N of the initialization population. However, some studies have shown that the setting of the number of initialization population should be related to the length of the problem. In this paper, the length of the problem is the product (m × n) of the number of available MEC servers and the number of IMDs. That is, with the increase of the number of servers and the number of IMDs, the number of initialization population should be increased to meet the diversity of the population.In the algorithm proposed in this paper, we adopt the method of adding diversity judgment in the iterative execution of the algorithm. If the population diversity is lower than the threshold preset, we can improve the population diversity through population diversity regulation. As shown in Figure9, when the number of available servers is increased from 3 to 5, the number of solution space will grow from 230 to 250 rapidly. However, the number of initialization populations we set is all 30. The experimental results indicate that the solutions obtained by HIBSA are not affected. They are significantly improved in terms of tasks execution time, the total weight of tasks, and the number of offloaded tasks, which shows the scalability of the algorithm.Figure 9
the scalability of the algorithm: (a) tasks execution time, (b) the total weight of tasks, and (c) the number of tasks offloading.
(a)(b)(c)


## 6. Conclusions

Task offloading in mobile edge computing relieves the data computing pressure of local devices and central cloud by offloading data to the edge cloud, which also reduces the task execution delay caused by the lack of computing resources. In this paper, an algorithm based on hybrid immune and bat scheduling algorithm (HIBSA) is proposed to tackle the multiobjective optimization problem. Three main contributions are presented in this paper. Firstly, the proposed system model considers communication and computing resources, energy consumption of intelligent mobile devices, and weight of tasks. Secondly, the scenario that the mobile device can generate multiple tasks at the same time is considered, which is more realistic compared with most of the related works. Thirdly, the evolutionary algorithm presented combines the advantages of the bat algorithm and the immune algorithm that ensures the convergence and diversity of solutions. Finally, the practicability of the proposed algorithm is well verified by simulation. We can see from experimental results that the algorithm can meet the requirements of both the task execution time of the offloaded tasks and the weight of the completed tasks. Moreover, the algorithm has good scalability. However, the performance of the proposed algorithm can further be improved in the future. It needs to be further verified by using real scene data also.



---

*Source: 7716654-2021-11-05.xml*