# Pattern-Identified Online Task Scheduling in Multitier Edge Computing for Industrial IoT Services

Authors: Nhu-Ngoc Dao; Duc-Nghia Vu; Yunseong Lee; Sungrae Cho; Chihyun Cho; Hyunbum Kim
Journal: Mobile Information Systems
 (2018)

---

## Abstract

In smart manufacturing, production machinery and auxiliary devices, referred to as industrial Internet of things (IIoT), are connected to a unified networking infrastructure for management and command deliveries in a precise production process. However, providing autonomous, reliable, and real-time offloaded services for such a production is an open challenge since these IIoT devices are assumed lightweight embedded platforms with limited computing performance. In this paper, we propose a pattern-identified online task scheduling (PIOTS) mechanism for the networking infrastructure, where multitier edge computing is provided, in order to handle the offloaded tasks in real time. First, historical IIoT task patterns in every timeslot are used to train a self-organizing map (SOM), which represents the features of the task patterns within defined dimensions. Consequently, offline task scheduling among edge computing-enabled entities is performed on the set of all SOM neurons using the Hungarian method to determine the expected optimal task assignments. In real-time context, whenever a task arrives at the infrastructure, the expected optimal assignment for the task is scheduled to the appropriate edge computing-enabled entity. Numerical simulation results show that the proposed PIOTS mechanism overcomes existing solutions in terms of computation performance and service capability.


---

## Body

## 1. Introduction

Recently, smartization in manufacturing has been considered as one of the major trends realizing the fourth industrial revolution [1]. In the smart factory, production machinery and auxiliary devices, which are referred to as industrial Internet of things (IIoT), maintain permanent connections to a unified networking infrastructure, where Internet service is available. In this environment, all of the connected IIoT devices acquire mutual cooperation with each other and they request the working commands from central management entities in the network. For instance, precise production processes require trigger feedback from control entities to adjust reactions of machines and robots if an unexpected issue occurs. Another example is when smoke is detected in a warehouse, a real-time shutdown command should be immediately dispatched to electrical working chains and a real-time activation command should force the fire extinguishing system to be activated [2]. However, since these IIoT devices are assumed to be lightweight embedded platforms with limited computing resources, it is inappropriate to execute real-time services using its own power of the devices.Fortunately, thanks to the advances of the emerging fifth-generation (5G) technologies, the 5G mobile edge computing (MEC) can provide autonomous, reliable, and real-time offloaded services for these IIoT devices and applications. Defined by the European telecommunications standards institute (ETSI), the MEC providescloud-computing capabilities and an IT service environment at the edge of the network [3]. To be more specific, multitier MEC (mMEC) is a virtualized hierarchical MEC framework where edge computing-enabled entities (ECEs) are layered according to its computing performance. The operation of mMEC framework is supervised by a central orchestrator [4]. The orchestrator schedules the tasks offloaded from IIoT devices among ECEs in order to maximize computation performance and decrease energy consumption while keeping the IIoT applications’ requirements.Aiming at this objective, we propose a pattern-identified online task scheduling (PIOTS) mechanism for the mMEC framework in smart factory for handling the offloaded IIoT tasks in real time. First, historical IIoT task patterns in every timeslot are used to train a self-organizing map (SOM), which represents the features of the task patterns within defined dimension [5]. As a result, a set of typical SOMs for IIoT task patterns are identified. At the beginning of each timeslot, offline task scheduling among ECEs is performed on the neuron set of the typical SOM using the Hungarian method to determine the expected optimal task assignments. Thereafter, whenever a task arrives at the mMEC framework, the task is matched into the current SOM to find the best matching SOM neuron for it. Based on that, the expected optimal assignment for this matched SOM neuron is scheduled for the task, assigning to appropriate ECE in online manner. The main contributions of this paper are three-fold:(i)
First, expected optimal assignments are scheduled for offloaded IIoT tasks that arrived at the mMEC framework in real time. In other words, a task assignment delay is reduced significantly.(ii)
Second, the duration of task assignment calculation is decreased because this operation works on the SOM neuron set within defined dimension. The neuron set is a representative of the historical incoming tasks, which is not greater than the size of real task patterns in each timeslot. As a result, the computational complexity and calculation latency are reduced as well.(iii)
Third, the expected optimal task assignment calculation is performed independently on the task scheduling timeline. Therefore, the task assignment can be operated continuously in real time without waiting for the task assignment calculation to be completed.The remainder of this paper is organized as follows. Section2 surveys the state-of-the-art-related work. Section 3 describes the proposed pattern-identified online task scheduling mechanism in detail. Section 4 provides the system setup, evaluation methodology, and evaluation metric definitions. Based on that, the performance of the PIOTS mechanism in comparison to other techniques is analyzed in Section 5. Finally, the paper is concluded in Section 6.


## 2. Related Work

Optimal task assignments in multitier edge computing have been classified into three main categories: latency awareness, energy awareness, and quality-of-service (QoS) awareness including their variants [6, 7].The latency-aware approaches focus on minimizing execution latency of the task offloaded to the edge servers. The execution latency involves three portions: transmission duration from the IIoT devices to the edge servers, queuing and processing duration at the edge servers, and return duration for successful reception of the result in the IIoT devices [8, 9]. The mMEC framework can be designed and supported by several emerging technologies such as network functions virtualization (NFV) and software defined networking (SDN). In [10], Dao et al. proposed an adaptive balancing scheme (ARB) to distribute tasks among edge servers in the remote radio heads in order to improve the serviceability of the network, especially in terms of task execution latency. The ARB scheme combines the Hungarian method and the backpressure algorithm for this purpose. In [11], Mao et al. aim at reducing the task execution latency by using a low-complexity Lyapunov optimization-based dynamic computation offloading (LODCO) algorithm. The LODCO algorithm handles CPU utilization in the edge servers according to the task arrival. On the other hand, Liu et al. [12] considered application buffer queuing state, available computing powers, and channel quality to conduct the optimal offloading decision. The tasks will be assigned to the edge servers if the total execution latency made by the edge server is shorter than the duration spent to execute the task locally by the IIoT devices. Otherwise, the IIoT devices will execute their tasks themselves.The energy-aware approaches aim at minimizing energy consumption for task execution in edge computing. Typically, the energy consumption is considered on task delivery and task computation. In [13], an energy reduction method was proposed based on the Bak–Tang–Wiesenfeld sandpile. When an edge server exceeds a certain capacity threshold, it collapses and initiates an avalanche of migrating tasks in order to balance the workload among edge servers. The achievement results in a significant reduction in task assignment errors and redundancy, which dominates the overhead of energy consumption. On the other hand, You et al. [14] considered the transmission energy for multiple IIoT devices offloaded tasks to the edge-computing framework. The optimal solution was developed and resolved so as to minimize the weighted sum mobile energy consumption under the constraint on computation latency. In [15], the problem of interdependent task scheduling was addressed within an edge system of deep memory hierarchies to obtain energy efficiency. The intermediate data of the tasks are prioritized and assigned at appropriate levels of cache memory to optimize latency and energy in data access. In order to make the offloading decision, Li et al. formulated the problem in a 0-1 nonlinear integer programming with a consideration of channel interference threshold and the time deadline [16]. Based on that assumption, a reverse auction based offloading policy has been proposed to obtain energy efficiency improvement for task execution.The QoS-aware approaches consider multiple criteria of IIoT service requirements such as execution latency, service availability, transmission throughput, and security as trade-off problems, which have to be optimized. In [17], a distributed optimization algorithm that cooperated among edge servers, called offload forwarding, is proposed by using the distributed alternating direction method of multipliers (ADMM) via variable splitting to maximize QoS and energy efficiency. For focusing on maximizing the transmission throughput for task offloading, Vu et al. [18] utilize the Hungarian method to optimize the downlink sum rate in fog computing-enabled networks. On the other hand, Zeng et al. [19] proposed a security-aware and budget-aware workflow scheduling strategy (SABA), which considers the task distribution among providers to achieve cost-effective and secure services in the context of convergent network. This strategy is applicable to the edge computing environment where edge servers act the role of service providers for offloaded tasks from the IIoT devices. Within the same purpose, Xu et al. proposed the green offloading (GO) scheme [20] that uses the reverse auction theory to develop the offloading decision while satisfying the user quality-of-service (QoS) requirements, bandwidth, and the maximum transmit power.Although the existing approaches have significantly contributed to improve the performance of the edge computing, most of the existing approaches face a drawback in online task handling, where the tasks that arrive at the edge framework have to be queued before the scheduling decision is made. This queuing behavior generates significant latency, especially in cases of smart manufacturing, where real-time response requirement is a crucial criterion for precise production processes. In the next section, our proposed PIOTS mechanism, which overcomes these issues, is described in detail.


## 3. Pattern-Identified Online Task Scheduling

### 3.1. Basic Assumptions

In this paper, we consider a networking infrastructure for smart manufacturing where mMEC framework is covered. Machinery and auxiliary devices participate in a smart production process, generate their IIoT tasks, and offload them to the mMEC framework for centralized handling. The IIoT tasks are processed and responded to the IIoT devices on demands. Typically, the production process operates continuously in a long duration (e.g., weeks, months, and even years). Therefore, we assume that the IIoT task patterns maintain their permanent trends even though instant tasks are generated randomly by the IIoT devices. In this circumstance, real-time response is considered as a crucial requirement for precise productions. Figure1 illustrates the system model where the IIoT devices are supported by the mMEC framework in smart manufacturing environment. The IIoT devices are connected to the network via wireless access points (APs) and switches (SWs). The mMEC framework consists of APs/SWs, routers, and local servers/storages, which have various computing capacities. In a mMEC framework, all these ECEs are managed and scheduled their computations by a central device named orchestrator.Figure 1
System model where the IIoT devices are supported by the mMEC framework in smart manufacturing environment.


### 3.2. Self-Organizing Map

Self-organizing map is an artificial neural network (ANN) that utilizes unsupervised learning on the high-dimensional data to produce a defined low-dimensional representation calledmap (Figure 2). Each SOM is formed by a defined number of neurons, which reflect the map dimension. The operation of the SOMs includes two modes: training and mapping. The training mode develops a map based on the input set of tasks. Meanwhile, the mapping mode is used for classifying new arrived tasks.Figure 2
Self-organizing map (SOM).The SOM algorithm to train the map is iterated by two steps after initialization as follows.Initialization: Assume that there are n tasks in the input set X, wherein each task i1≤i≤n is characterized by l features forming a corresponding vector xi→=fi1,fi2,…,fil. Accordingly, each neuron j in the SOM 1≤j≤k has a 1-dimensional weight vector wj→, where wj→=wj1,wj2,…,wjl. To start the SOM algorithm in order to train the map, each neuron initiates its own weight vector with random values. Afterwards, the two steps below are contiguously repeated for each task in the X. In detail, for task i, the SOM algorithm performs the following steps:Step 1 (matching): Euclidean distance between task i and each neuron in the SOM is calculated in order to find the best matching unit. The best matching unit for the task i is the neuron wi∗→, which has the smallest Euclidean distance to the task i. In other words, wi∗→ is given by(1)wi∗→=argmin∀j,1≤j≤k∑s=1lfis−wjs2.Step 2 (neuron update): all neurons in the neighborhood of the neuron wi∗→ update their weight vectors to be closer to task i by(2)wj→t+1=wj→t+θt⋅μt⋅xi→−wj→t,where wj→t is the weight vector of neuron j at this iteration t. θt is the neighborhood function, which has diminished every iteration. θt determines the distance from the neuron wi∗→ to define the neighboring neurons. μt is the learning factor, which calculates the amount of effect from the input task i to the neuron j based on distance between them [21]. The mathematical expressions of θt and μt are described as follows:(3)θt=exp−wi∗→22σ2t,(4)μt=μ0×exp−tlgRX,where R is the maximum radius from the center of the map (i.e., 0.5maxMapWidth,MapHeight) and σt is the neighborhood radius that is given by(5)σt=R×exp−t2lgRX.


### 3.3. Pattern-Identified Online Task Scheduling

In this section, we describe the PIOTS mechanism in detail. The rationale behind the PIOTS includes three steps: (i) identifying the set of typical SOMs for IIoT task patterns, (ii) calculating expected optimal task assignment on the typical SOM prior to each timeslot, and (iii) online assigning new arrived tasks to appropriate ECEs. Steps (i) and (ii) are in the offline mode and step (iii) is in the online mode.


#### 3.3.1. Offline Mode

(1) Typical SOM identification: in terms of task execution offloading, a IIoT task i is characterized by a four-dimensional feature vector as given by(6)xi→=ui,ci,ri,τi,where ui,ci,ri,andτi are relative task size, relative average processing complexity, relative response size, and relative execution deadline compared to their minimum and maximum values of all trained tasks, respectively. As mentioned in Section 3.1, the production process operates continuously during a given period. Within each timeslot in this period, given that there is an average number Nx tasks in the set χt of IIoT tasks offloaded to the mMEC framework, the number k of neurons in the SOM is selected as(7)k=1λNx,λ≥1,where ⋅ is the nearest integer function and λ is a scale level, which supports reduction of the SOM size. Based on these settings, the k-neuron two-dimensional SOM is trained using all offloaded IIoT tasks in the given period. For each distinctive period, we obtain a typical trained SOM to represent the offloaded IIoT tasks. A distinctive period is defined as a cycle of the offloaded IIoT task arrival; after this duration, the task arrival is repeated again in terms of volume and characteristics.(2) Expected optimal task assignment calculation: Figure 3 describes the PIOTS operation timeline in a random IIoT task arrival context. Prior to timeslot t, the PIOTS mechanism performs the Ht function at t−Δt in order to determine the expected optimal task assignment during timeslot t. The Ht function uses the Hungarian method [22] to address the expected optimal task assignment problem between the neuron set of the typical SOM in timeslot t and the current ECE set. The result of Ht function will be applied for online task assignment in the whole duration from timeslot t to timeslot t+1 even though the Ht+1 function will start at t+1−Δt.Figure 3
IIoT task arrival and PIOTS operation timeline.The expected optimal task assignment problem is defined as“Given the current performance status (i.e., task buffer and CPU frequency) of ECEs and the transmission status (i.e., access data rate between IIoT devices and the mMEC framework and forwarding data rate among ECEs), minimize the total latency of task execution when assigning the neuron set of the typical SOM to the ECEs.”The expected optimal task assignment problem can be formulated as follows. LetW and ℳ denote the set of k neurons in the SOM and the set of m ECEs in the mMEC framework, respectively. Since the SOM neurons have trained by using the historical tasks, the weight vector of the neuron reflects the average values of the task features, accordingly. That is, wj1,wj2,wj3,andwj4 in the weight vector wj→ of neuron j reflect the average values of the relative task size, relative average processing complexity, relative response size, and relative execution deadline, respectively. Let the current buffer size of tasks waiting for processing in ECEs be bs CPU cycles. Hence, the total latency Ljs when neuron j is assigned to ECEs is as follows.(8)Ljs=wj1+wj3rajs︸a+bsCs︸b+wj1wj2Cs︸c+wj1+wj3rbjs︸d,where Cs, rajs, and rbjs are the CPU frequency of ECEs in Hz, the access data rate from the IIoT device that owned task j to the network in bps, and the internal forwarding rate to the ECEs in bps, respectively. Equation (8) consists of (a) uploading latency, (b) queuing latency, (c) task processing latency, and (d) response latency. The access data rate rajs is given by(9)rajs=BWjslog21+SINRj,where BWjs and SINRj are the bandwidth allocated for the IIoT device and the channel quality between the IIoT device and the network, respectively.Based on that, the expected optimal task assignment problemℱ can be described as follows:(10)ℱminimize:∑j=1k∑s=1mzjsLjs,(11)s.t.zjs∈0,1,(12)Ljs≤wj4,(13)∑j=1kzjs=1,∀s=1,2,…,m,where the indicator zjs is given by(14)zjs=1,ifneuronjisassignedtoECEs,0,otherwise.Constraint (13) ensures that a neuron could only be assigned to one ECE and the maximum matchings are established for all m neurons of the SOM.It is observed that task assignment problemℱ regards a bipartite graph of two sets W and ℳ. We apply the Hungarian method (referred as H⋅) on the graph to achieve the optimal solution. Function H⋅ is performed as follows (see Algorithm 1):(i)
Augment the latency matrix of all possible task assignments from neuron setW to ECE set ℳ into a square matrix (named V) with dimension maxW,ℳ by supplementing additional entries of constant number (e.g., 0).(ii)
In each row ofV, subtract the smallest row entry from all of the row entries. Similarly, in each column of V, subtract the smallest column entry from all of the column entries.(iii)
Find the minimum numberυ of rows and columns by which all zero entries are covered.(iv)
Ifυ is equal to the size of V, the optimal solution is found. Pick up a set of 0 entries satisfying in which no more than two 0 entries are in the same row or column. Otherwise, if υ is less than the size of V, determine the smallest entry γ that is uncovered in the previous step. Afterwards, subtract γ from all uncovered rows and add γ to all covered columns. Return to the previous step to find the minimum number υ again.double
Algorithm 1: Pseudocode of function H(⋅).
(1)
Generate a square latency matrixV from W and M.
(2)
In each row, subtract all entries by the smallest row entry.
(3)
In each column, subtract all entries by the smallest column entry.
(4)
Find the minimum numberυ of rows and columns that cover all zero entries.
(5)
Ifυ==V, the optimal solution is found.
(6)
Ifυ<V,Find the smallest entryγ in the matrix,Subtract all uncovered rows byγ,Add all covered columns byγ,Return to Line (4).For each timeslot, the functionH⋅ is calculated prior Δt before the beginning of the timeslot in order to find the expected optimal task assignment solution.


#### 3.3.2. Online Mode

Online task assignment: in the online mode, when an IIoT task arrives at the mMEC framework, the task is matched to the SOM so as to seek the best matching neuron, using (1) with the computational complexity of O1. According to the optimal assignment for the found neuron that was determined by function H⋅ in the offline mode, this assignment is performed on the arrived IIoT task immediately.


## 3.1. Basic Assumptions

In this paper, we consider a networking infrastructure for smart manufacturing where mMEC framework is covered. Machinery and auxiliary devices participate in a smart production process, generate their IIoT tasks, and offload them to the mMEC framework for centralized handling. The IIoT tasks are processed and responded to the IIoT devices on demands. Typically, the production process operates continuously in a long duration (e.g., weeks, months, and even years). Therefore, we assume that the IIoT task patterns maintain their permanent trends even though instant tasks are generated randomly by the IIoT devices. In this circumstance, real-time response is considered as a crucial requirement for precise productions. Figure1 illustrates the system model where the IIoT devices are supported by the mMEC framework in smart manufacturing environment. The IIoT devices are connected to the network via wireless access points (APs) and switches (SWs). The mMEC framework consists of APs/SWs, routers, and local servers/storages, which have various computing capacities. In a mMEC framework, all these ECEs are managed and scheduled their computations by a central device named orchestrator.Figure 1
System model where the IIoT devices are supported by the mMEC framework in smart manufacturing environment.


## 3.2. Self-Organizing Map

Self-organizing map is an artificial neural network (ANN) that utilizes unsupervised learning on the high-dimensional data to produce a defined low-dimensional representation calledmap (Figure 2). Each SOM is formed by a defined number of neurons, which reflect the map dimension. The operation of the SOMs includes two modes: training and mapping. The training mode develops a map based on the input set of tasks. Meanwhile, the mapping mode is used for classifying new arrived tasks.Figure 2
Self-organizing map (SOM).The SOM algorithm to train the map is iterated by two steps after initialization as follows.Initialization: Assume that there are n tasks in the input set X, wherein each task i1≤i≤n is characterized by l features forming a corresponding vector xi→=fi1,fi2,…,fil. Accordingly, each neuron j in the SOM 1≤j≤k has a 1-dimensional weight vector wj→, where wj→=wj1,wj2,…,wjl. To start the SOM algorithm in order to train the map, each neuron initiates its own weight vector with random values. Afterwards, the two steps below are contiguously repeated for each task in the X. In detail, for task i, the SOM algorithm performs the following steps:Step 1 (matching): Euclidean distance between task i and each neuron in the SOM is calculated in order to find the best matching unit. The best matching unit for the task i is the neuron wi∗→, which has the smallest Euclidean distance to the task i. In other words, wi∗→ is given by(1)wi∗→=argmin∀j,1≤j≤k∑s=1lfis−wjs2.Step 2 (neuron update): all neurons in the neighborhood of the neuron wi∗→ update their weight vectors to be closer to task i by(2)wj→t+1=wj→t+θt⋅μt⋅xi→−wj→t,where wj→t is the weight vector of neuron j at this iteration t. θt is the neighborhood function, which has diminished every iteration. θt determines the distance from the neuron wi∗→ to define the neighboring neurons. μt is the learning factor, which calculates the amount of effect from the input task i to the neuron j based on distance between them [21]. The mathematical expressions of θt and μt are described as follows:(3)θt=exp−wi∗→22σ2t,(4)μt=μ0×exp−tlgRX,where R is the maximum radius from the center of the map (i.e., 0.5maxMapWidth,MapHeight) and σt is the neighborhood radius that is given by(5)σt=R×exp−t2lgRX.


## 3.3. Pattern-Identified Online Task Scheduling

In this section, we describe the PIOTS mechanism in detail. The rationale behind the PIOTS includes three steps: (i) identifying the set of typical SOMs for IIoT task patterns, (ii) calculating expected optimal task assignment on the typical SOM prior to each timeslot, and (iii) online assigning new arrived tasks to appropriate ECEs. Steps (i) and (ii) are in the offline mode and step (iii) is in the online mode.


### 3.3.1. Offline Mode

(1) Typical SOM identification: in terms of task execution offloading, a IIoT task i is characterized by a four-dimensional feature vector as given by(6)xi→=ui,ci,ri,τi,where ui,ci,ri,andτi are relative task size, relative average processing complexity, relative response size, and relative execution deadline compared to their minimum and maximum values of all trained tasks, respectively. As mentioned in Section 3.1, the production process operates continuously during a given period. Within each timeslot in this period, given that there is an average number Nx tasks in the set χt of IIoT tasks offloaded to the mMEC framework, the number k of neurons in the SOM is selected as(7)k=1λNx,λ≥1,where ⋅ is the nearest integer function and λ is a scale level, which supports reduction of the SOM size. Based on these settings, the k-neuron two-dimensional SOM is trained using all offloaded IIoT tasks in the given period. For each distinctive period, we obtain a typical trained SOM to represent the offloaded IIoT tasks. A distinctive period is defined as a cycle of the offloaded IIoT task arrival; after this duration, the task arrival is repeated again in terms of volume and characteristics.(2) Expected optimal task assignment calculation: Figure 3 describes the PIOTS operation timeline in a random IIoT task arrival context. Prior to timeslot t, the PIOTS mechanism performs the Ht function at t−Δt in order to determine the expected optimal task assignment during timeslot t. The Ht function uses the Hungarian method [22] to address the expected optimal task assignment problem between the neuron set of the typical SOM in timeslot t and the current ECE set. The result of Ht function will be applied for online task assignment in the whole duration from timeslot t to timeslot t+1 even though the Ht+1 function will start at t+1−Δt.Figure 3
IIoT task arrival and PIOTS operation timeline.The expected optimal task assignment problem is defined as“Given the current performance status (i.e., task buffer and CPU frequency) of ECEs and the transmission status (i.e., access data rate between IIoT devices and the mMEC framework and forwarding data rate among ECEs), minimize the total latency of task execution when assigning the neuron set of the typical SOM to the ECEs.”The expected optimal task assignment problem can be formulated as follows. LetW and ℳ denote the set of k neurons in the SOM and the set of m ECEs in the mMEC framework, respectively. Since the SOM neurons have trained by using the historical tasks, the weight vector of the neuron reflects the average values of the task features, accordingly. That is, wj1,wj2,wj3,andwj4 in the weight vector wj→ of neuron j reflect the average values of the relative task size, relative average processing complexity, relative response size, and relative execution deadline, respectively. Let the current buffer size of tasks waiting for processing in ECEs be bs CPU cycles. Hence, the total latency Ljs when neuron j is assigned to ECEs is as follows.(8)Ljs=wj1+wj3rajs︸a+bsCs︸b+wj1wj2Cs︸c+wj1+wj3rbjs︸d,where Cs, rajs, and rbjs are the CPU frequency of ECEs in Hz, the access data rate from the IIoT device that owned task j to the network in bps, and the internal forwarding rate to the ECEs in bps, respectively. Equation (8) consists of (a) uploading latency, (b) queuing latency, (c) task processing latency, and (d) response latency. The access data rate rajs is given by(9)rajs=BWjslog21+SINRj,where BWjs and SINRj are the bandwidth allocated for the IIoT device and the channel quality between the IIoT device and the network, respectively.Based on that, the expected optimal task assignment problemℱ can be described as follows:(10)ℱminimize:∑j=1k∑s=1mzjsLjs,(11)s.t.zjs∈0,1,(12)Ljs≤wj4,(13)∑j=1kzjs=1,∀s=1,2,…,m,where the indicator zjs is given by(14)zjs=1,ifneuronjisassignedtoECEs,0,otherwise.Constraint (13) ensures that a neuron could only be assigned to one ECE and the maximum matchings are established for all m neurons of the SOM.It is observed that task assignment problemℱ regards a bipartite graph of two sets W and ℳ. We apply the Hungarian method (referred as H⋅) on the graph to achieve the optimal solution. Function H⋅ is performed as follows (see Algorithm 1):(i)
Augment the latency matrix of all possible task assignments from neuron setW to ECE set ℳ into a square matrix (named V) with dimension maxW,ℳ by supplementing additional entries of constant number (e.g., 0).(ii)
In each row ofV, subtract the smallest row entry from all of the row entries. Similarly, in each column of V, subtract the smallest column entry from all of the column entries.(iii)
Find the minimum numberυ of rows and columns by which all zero entries are covered.(iv)
Ifυ is equal to the size of V, the optimal solution is found. Pick up a set of 0 entries satisfying in which no more than two 0 entries are in the same row or column. Otherwise, if υ is less than the size of V, determine the smallest entry γ that is uncovered in the previous step. Afterwards, subtract γ from all uncovered rows and add γ to all covered columns. Return to the previous step to find the minimum number υ again.double
Algorithm 1: Pseudocode of function H(⋅).
(1)
Generate a square latency matrixV from W and M.
(2)
In each row, subtract all entries by the smallest row entry.
(3)
In each column, subtract all entries by the smallest column entry.
(4)
Find the minimum numberυ of rows and columns that cover all zero entries.
(5)
Ifυ==V, the optimal solution is found.
(6)
Ifυ<V,Find the smallest entryγ in the matrix,Subtract all uncovered rows byγ,Add all covered columns byγ,Return to Line (4).For each timeslot, the functionH⋅ is calculated prior Δt before the beginning of the timeslot in order to find the expected optimal task assignment solution.


### 3.3.2. Online Mode

Online task assignment: in the online mode, when an IIoT task arrives at the mMEC framework, the task is matched to the SOM so as to seek the best matching neuron, using (1) with the computational complexity of O1. According to the optimal assignment for the found neuron that was determined by function H⋅ in the offline mode, this assignment is performed on the arrived IIoT task immediately.


## 3.3.1. Offline Mode

(1) Typical SOM identification: in terms of task execution offloading, a IIoT task i is characterized by a four-dimensional feature vector as given by(6)xi→=ui,ci,ri,τi,where ui,ci,ri,andτi are relative task size, relative average processing complexity, relative response size, and relative execution deadline compared to their minimum and maximum values of all trained tasks, respectively. As mentioned in Section 3.1, the production process operates continuously during a given period. Within each timeslot in this period, given that there is an average number Nx tasks in the set χt of IIoT tasks offloaded to the mMEC framework, the number k of neurons in the SOM is selected as(7)k=1λNx,λ≥1,where ⋅ is the nearest integer function and λ is a scale level, which supports reduction of the SOM size. Based on these settings, the k-neuron two-dimensional SOM is trained using all offloaded IIoT tasks in the given period. For each distinctive period, we obtain a typical trained SOM to represent the offloaded IIoT tasks. A distinctive period is defined as a cycle of the offloaded IIoT task arrival; after this duration, the task arrival is repeated again in terms of volume and characteristics.(2) Expected optimal task assignment calculation: Figure 3 describes the PIOTS operation timeline in a random IIoT task arrival context. Prior to timeslot t, the PIOTS mechanism performs the Ht function at t−Δt in order to determine the expected optimal task assignment during timeslot t. The Ht function uses the Hungarian method [22] to address the expected optimal task assignment problem between the neuron set of the typical SOM in timeslot t and the current ECE set. The result of Ht function will be applied for online task assignment in the whole duration from timeslot t to timeslot t+1 even though the Ht+1 function will start at t+1−Δt.Figure 3
IIoT task arrival and PIOTS operation timeline.The expected optimal task assignment problem is defined as“Given the current performance status (i.e., task buffer and CPU frequency) of ECEs and the transmission status (i.e., access data rate between IIoT devices and the mMEC framework and forwarding data rate among ECEs), minimize the total latency of task execution when assigning the neuron set of the typical SOM to the ECEs.”The expected optimal task assignment problem can be formulated as follows. LetW and ℳ denote the set of k neurons in the SOM and the set of m ECEs in the mMEC framework, respectively. Since the SOM neurons have trained by using the historical tasks, the weight vector of the neuron reflects the average values of the task features, accordingly. That is, wj1,wj2,wj3,andwj4 in the weight vector wj→ of neuron j reflect the average values of the relative task size, relative average processing complexity, relative response size, and relative execution deadline, respectively. Let the current buffer size of tasks waiting for processing in ECEs be bs CPU cycles. Hence, the total latency Ljs when neuron j is assigned to ECEs is as follows.(8)Ljs=wj1+wj3rajs︸a+bsCs︸b+wj1wj2Cs︸c+wj1+wj3rbjs︸d,where Cs, rajs, and rbjs are the CPU frequency of ECEs in Hz, the access data rate from the IIoT device that owned task j to the network in bps, and the internal forwarding rate to the ECEs in bps, respectively. Equation (8) consists of (a) uploading latency, (b) queuing latency, (c) task processing latency, and (d) response latency. The access data rate rajs is given by(9)rajs=BWjslog21+SINRj,where BWjs and SINRj are the bandwidth allocated for the IIoT device and the channel quality between the IIoT device and the network, respectively.Based on that, the expected optimal task assignment problemℱ can be described as follows:(10)ℱminimize:∑j=1k∑s=1mzjsLjs,(11)s.t.zjs∈0,1,(12)Ljs≤wj4,(13)∑j=1kzjs=1,∀s=1,2,…,m,where the indicator zjs is given by(14)zjs=1,ifneuronjisassignedtoECEs,0,otherwise.Constraint (13) ensures that a neuron could only be assigned to one ECE and the maximum matchings are established for all m neurons of the SOM.It is observed that task assignment problemℱ regards a bipartite graph of two sets W and ℳ. We apply the Hungarian method (referred as H⋅) on the graph to achieve the optimal solution. Function H⋅ is performed as follows (see Algorithm 1):(i)
Augment the latency matrix of all possible task assignments from neuron setW to ECE set ℳ into a square matrix (named V) with dimension maxW,ℳ by supplementing additional entries of constant number (e.g., 0).(ii)
In each row ofV, subtract the smallest row entry from all of the row entries. Similarly, in each column of V, subtract the smallest column entry from all of the column entries.(iii)
Find the minimum numberυ of rows and columns by which all zero entries are covered.(iv)
Ifυ is equal to the size of V, the optimal solution is found. Pick up a set of 0 entries satisfying in which no more than two 0 entries are in the same row or column. Otherwise, if υ is less than the size of V, determine the smallest entry γ that is uncovered in the previous step. Afterwards, subtract γ from all uncovered rows and add γ to all covered columns. Return to the previous step to find the minimum number υ again.double
Algorithm 1: Pseudocode of function H(⋅).
(1)
Generate a square latency matrixV from W and M.
(2)
In each row, subtract all entries by the smallest row entry.
(3)
In each column, subtract all entries by the smallest column entry.
(4)
Find the minimum numberυ of rows and columns that cover all zero entries.
(5)
Ifυ==V, the optimal solution is found.
(6)
Ifυ<V,Find the smallest entryγ in the matrix,Subtract all uncovered rows byγ,Add all covered columns byγ,Return to Line (4).For each timeslot, the functionH⋅ is calculated prior Δt before the beginning of the timeslot in order to find the expected optimal task assignment solution.


## 3.3.2. Online Mode

Online task assignment: in the online mode, when an IIoT task arrives at the mMEC framework, the task is matched to the SOM so as to seek the best matching neuron, using (1) with the computational complexity of O1. According to the optimal assignment for the found neuron that was determined by function H⋅ in the offline mode, this assignment is performed on the arrived IIoT task immediately.


## 4. Evaluation Preparations

### 4.1. System Settings

In order to evaluate the performance of the PIOTS scheme, we considered a network model, where the mMEC framework consists of 20 ECEs equipped with various CPU frequencies of {1.5, 2.5, 5.0, 10.0, 25.0} GHz. The total number of IIoT devices associated with the network is 300. The task processing complexity is determined as {10, 50, 100, 500, 1000} cycles/bit derived from the practical analysis presented in [23]. Execution deadline is randomly set within (0.5, 1.5) s. Lastly, timeslot duration is set to 0.1 s. These simulation parameters are summarized in Table 1.Table 1
Simulation parameters.
Parameter
Value
Orchestrator configuration
CPU: Intel Core i5-6400 2.7 GHz; RAM: 16 GB
Number of ECEs
20
CPU frequency of ECEs
{1.5, 2.5, 5.0, 10.0, 25.0} GHz
Number of IIoT devices
300
Task processing complexity
{10, 50, 100, 500, 1000} cycles/bit
Execution deadline
0.5–1.5 s
Timeslot duration
0.1 s
Simulation duration
300 timeslotsIn terms of task and response size settings, we derived these parameters from a part of theCAIDA anonymized Internet traces data set [24]. The CAIDA data set contains anonymized passive traffic traces from the Equinix-Chicago Internet data collection monitor located at an Equinix datacenter in Chicago, IL, on high-speed Internet backbone links. Table 2 shows statistical indexes of the task samples used for SOM training and system evaluation. The tasks are selected for three types of traffic as follows:(i)
Environmental sensor data: the information of environmental conditions is reported to central applications in the mMEC framework during each fixed period. The task size is configured within constant and small dimension, and these tasks do not require response from the applications.(ii)
Video surveillance data: live streaming data from monitoring cameras are delivered to surveillance applications in the mMEC framework for video analysis and storage. These tasks are packetized in fixed and large size. The response data might be issued from the applications if there are any alarms that should be announced.(iii)
Production control data: these data are generated by the machinery during precise production processes. The tasks are regularly offloaded to the mMEC framework within a determined size. Tasks require responses from the applications to exactly handle production work.Table 2
Statistical indexes of task samples for SOM training and system evaluation.
Index
Value
Number of tasks
120,000
Min, max, and average values of task sizes
{129, 512, 316.45} kb
Min, max, and average values of response sizes
{0, 32, 15.47} kb


### 4.2. Evaluation Methodology

Within the aforementioned system settings, our proposed PIOTS scheme has been compared to the offline Hungarian task assignment (OHTA) algorithm and the online greedy task assignment (OGTA) algorithm. Initially 30,000 samples of the selected tasks derived from the CAIDA data set are used to train the SOM in the PIOTS scheme. Then, 90,000 other samples are used for evaluation (Table2). The operations of these schemes are described as follows:(i)
The PIOTS scheme is performed as shown in Section3.3.(ii)
The OHTA algorithm gathers all arrived tasks at the input buffer of the mMEC framework during one timeslot. At the end of each timeslot, the Hungarian method is utilized to decide the optimal task assignment for all tasks in this timeslot [22].(iii)
The OGTA algorithm determines an ECE, which provides the lowest latency for task execution following (8), for the arrived task [25].The simulation results are logged in terms of task execution latency and execution error rate. The execution error rate evaluates the ratio of the over-deadline task executions and the total offloaded tasks.


## 4.1. System Settings

In order to evaluate the performance of the PIOTS scheme, we considered a network model, where the mMEC framework consists of 20 ECEs equipped with various CPU frequencies of {1.5, 2.5, 5.0, 10.0, 25.0} GHz. The total number of IIoT devices associated with the network is 300. The task processing complexity is determined as {10, 50, 100, 500, 1000} cycles/bit derived from the practical analysis presented in [23]. Execution deadline is randomly set within (0.5, 1.5) s. Lastly, timeslot duration is set to 0.1 s. These simulation parameters are summarized in Table 1.Table 1
Simulation parameters.
Parameter
Value
Orchestrator configuration
CPU: Intel Core i5-6400 2.7 GHz; RAM: 16 GB
Number of ECEs
20
CPU frequency of ECEs
{1.5, 2.5, 5.0, 10.0, 25.0} GHz
Number of IIoT devices
300
Task processing complexity
{10, 50, 100, 500, 1000} cycles/bit
Execution deadline
0.5–1.5 s
Timeslot duration
0.1 s
Simulation duration
300 timeslotsIn terms of task and response size settings, we derived these parameters from a part of theCAIDA anonymized Internet traces data set [24]. The CAIDA data set contains anonymized passive traffic traces from the Equinix-Chicago Internet data collection monitor located at an Equinix datacenter in Chicago, IL, on high-speed Internet backbone links. Table 2 shows statistical indexes of the task samples used for SOM training and system evaluation. The tasks are selected for three types of traffic as follows:(i)
Environmental sensor data: the information of environmental conditions is reported to central applications in the mMEC framework during each fixed period. The task size is configured within constant and small dimension, and these tasks do not require response from the applications.(ii)
Video surveillance data: live streaming data from monitoring cameras are delivered to surveillance applications in the mMEC framework for video analysis and storage. These tasks are packetized in fixed and large size. The response data might be issued from the applications if there are any alarms that should be announced.(iii)
Production control data: these data are generated by the machinery during precise production processes. The tasks are regularly offloaded to the mMEC framework within a determined size. Tasks require responses from the applications to exactly handle production work.Table 2
Statistical indexes of task samples for SOM training and system evaluation.
Index
Value
Number of tasks
120,000
Min, max, and average values of task sizes
{129, 512, 316.45} kb
Min, max, and average values of response sizes
{0, 32, 15.47} kb


## 4.2. Evaluation Methodology

Within the aforementioned system settings, our proposed PIOTS scheme has been compared to the offline Hungarian task assignment (OHTA) algorithm and the online greedy task assignment (OGTA) algorithm. Initially 30,000 samples of the selected tasks derived from the CAIDA data set are used to train the SOM in the PIOTS scheme. Then, 90,000 other samples are used for evaluation (Table2). The operations of these schemes are described as follows:(i)
The PIOTS scheme is performed as shown in Section3.3.(ii)
The OHTA algorithm gathers all arrived tasks at the input buffer of the mMEC framework during one timeslot. At the end of each timeslot, the Hungarian method is utilized to decide the optimal task assignment for all tasks in this timeslot [22].(iii)
The OGTA algorithm determines an ECE, which provides the lowest latency for task execution following (8), for the arrived task [25].The simulation results are logged in terms of task execution latency and execution error rate. The execution error rate evaluates the ratio of the over-deadline task executions and the total offloaded tasks.


## 5. Numerical Result Analysis

First, the proposed PIOTS scheme is compared to the optimal solution of the objective functionℱ. The optimal solution for the integer programming problem ℱ used in this paper is a combination of the Hungarian method and backpressure algorithm [10]. Figure 4 illustrates the outcomes of ℱ depending on various IIoT task arrivals through 300 timeslots. Numerical results reveal that the PIOTS scheme provides an approximate performance compared to the optimal solution. The difference in average task processing latency is 0.159 ms. It is worth noting that the PIOTS scheme performs the expected task assignment based on the typical task set derived from the SOM map; then, it does real task assignment online. Moreover, the SOM map is trained by using the collected IIoT tasks arrived at the network in the past. Therefore, within a sufficient number of neurons in the SOM map that well represents for the typical characteristics of the incoming IIoT tasks, the mMEC framework can classify the incoming tasks immediately and then it handles the tasks by approximately optimal assignment. That is, each incoming task is immediately assigned to appropriate ECE right after the task arrives at the network. Meanwhile, the optimal solution is calculated based on the set of gathered IIoT tasks in each timeslot.Figure 4
PIOTS scheme versus optimal solution for the objective functionℱ.Table3 shows statistical indexes of time consumption in ms for task assignment decision of the orchestrator when applying the PIOTS, OHTA, and OGTA schemes, respectively. The average decision-making duration that the PIOTS scheme consumes is 0.038 ms, which is smaller than the OHTA scheme’s 100.1027 ms (approximate 2635 times of reduction) and greater than the OGTA scheme’s 0.0355 ms (approximate 15 times of increase). The reason is because the PIOTS scheme calculates (1) for all neurons in the SOM map, while the OHTA scheme must wait until the end of each timeslot to calculate the optimal solutions. The OGTA scheme achieves the smallest duration since it performs (8) for only 20 ECEs and selects the smallest latency value. Although there is a difference between the PIOTS and OGTA schemes, the average values are considered to insignificantly affect the task processing latency. The standard deviation and standard error mean show that all schemes are performed in a stable condition.Table 3
Time consumption in ms for task assignment decision of the orchestrator.
Scheme
Mean
Standard deviation
Standard error mean
PIOTS
0.0380
0.00242
0.00011
OHTA
100.1407
0.00265
0.00012
OGTA
0.0025
0.00111
0.00005Figure5 demonstrates a comparison of the average task processing latency when applying three competitors (PIOTS, OHTA, and OGTA). The PIOTS scheme achieves an effective performance since the typical task set is used to predetermine the expected task assignment for incoming tasks. Meanwhile, the OHTA scheme performs task assignment based on the gathered incoming tasks during each timeslot. Although the OHTA scheme provides better adaptation to varying task arrivals, it must wait until the end of each timeslot to collect the tasks and then determine the optimal assignment. On the other hand, the OGTA scheme greedily assigns tasks to the ECEs of lowest latency. In statistic perspective, for average take processing latency, the PIOTS scheme overcomes the OHTA scheme and the OGTA scheme by 41.47% and 4.47%, respectively.Figure 5
Average latency of task processing.In order to evaluate the service capability of the network, we utilize the execution error rate, which is defined by the percentage of deadline-violated IIoT devices in the total associated devices in the network. Figure6 shows simulation results corresponding to three thresholds of execution deadline including 0.5 s, 1.0 s, and 1.5 s as aforementioned in the system settings (Table 1). During 300 simulated timeslots, the execution error rates for 0.5-second deadline are approximate among PIOTS, OHTA, and OGTA schemes (0.970%, 0.976%, and 0.977%, resp.). Meanwhile, in terms of 1.5-second deadline, the PIOTS scheme decreases the execution error rate to 0.826% (approximate 5.7% and 1.2% decreases compared to the OGTA and OHTA schemes, resp.). This analysis demonstrates that the PIOTS scheme provides better balanced task distribution among ECEs in order to satisfy task execution deadlines.Figure 6
Percentage of deadline-violated IIoT devices.Figure7 plots average buffering latency for IIoT tasks arrived at the ECEs during 100, 200, and 300 timeslots. Since the arrived task volume has been configured to over capacitate the ECE performances leading to a saturated condition in the network, buffering latency increases by timeslot. It is observed that the OGTA scheme makes significant buffering latency in every timeslots. On the other hand, the PIOTS scheme achieves the lowest buffering latency by 44.33% and 4.32% in timeslot 300, compared to the OGTA scheme and OHTA scheme, respectively. Figure 8 depicts task distribution among ECEs, which helps to clarify the reason for the buffering latency achievements of the schemes. The y-axis represents the assigned task volume in gigacycles (a.k.a. computational CPU cycles) among ECEs, which is given by a production function of task size and task processing complexity for all assigned tasks in each ECE. In the OGTA scheme, the arrived tasks are assigned more equally among ECEs (represented by the width of the box plotted) in comparison with other schemes. Since the PIOTS scheme and OHTA scheme are able to adapt task distribution according to the diversity of ECE computation performances, they provide better task assignments resulting in lower buffering latency.Figure 7
Average buffering latency for IIoT tasks arrived at the ECEs.Figure 8
Task distribution among ECEs.


## 6. Concluding Remarks

In this paper, a pattern-identified online task scheduling mechanism has been proposed to deliberate on real-time task assignment in the smart manufacturing system. The proposed PIOTS scheme utilizes SOM technology for task identification and then assigns the task to appropriate ECE by using the Hungarian method. Simulation results demonstrate that the PIOTS scheme overcomes the existing algorithms in terms of task processing latency and service capability for satisfying IIoT applications. In future research, individual requirements of IIoT applications will be considered and verified via several popular datasets within the purpose of achieving the optimal performance for task handling in the entire network. Moreover, a consideration of applying game-theoretic approach should be studied to develop a distributed computational mMEC framework.



---

*Source: 2101206-2018-04-04.xml*