# Empirical Matching-Based Computation Offloading Optimization for 5G and Edge Computing-Integrated EIoT

Authors: Hui Zhang; Huixia Ding; Yang Wang; Sachula Meng; Sicheng Zhu; Ling Teng; Fangyun Dong
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Electric Internet of things (EIoT) that integrates 5G and edge computing can provide data transmission and processing guarantee for smart grid. However, computation offloading optimization including joint optimization of server selection and computation resource allocation still faces several challenges such as difficulty in tradeoff balance among various quality of service (QoS) parameters, coupling between server selection and computation resource allocation, and multi-device competition. To address these challenges, we propose an empirical matching-based computation offloading optimization algorithm for 5G and edge computing-integrated EIoT. The optimization objective is to minimize the computation offloading delay by jointly optimizing large timescale server selection and small timescale computation resource allocation. We first model the large timescale server selection problem as a many-to-one matching problem, which can be decoupled from small timescale computation resource allocation by establishing a matching preference list based on empirical performance. Then, the large timescale server selection problem is solved by pricing-based matching with a quota algorithm. Furthermore, based on the obtained suboptimal result of large timescale server selection, the small timescale computation resource allocation problem is subsequently solved by Lagrange dual decomposition, the result of which is used to update large timescale empirical performance. Finally, extensive simulations are carried out to demonstrate the superior performance of the proposed algorithm by comparing it with existing algorithms.


---

## Body

## 1. Introduction

In order to achieve the energy supply-demand balance and the safe and stable operation of the smart grid, massive electric Internet of things (EIoT) devices need to be deployed to support multiple types of real-time data collection, such as voltage, current, active/reactive power, electric energy, temperature, and humidity [1–3]. The integration of 5G and edge computing provides a viable solution for the real-time data monitoring. Specifically, 5G provides communication guarantee for real-time data collection and information interaction due to the advantages of high reliability, wide connection, and low delay [4]. Compared with ad hoc networks, 5G with central control functionality can achieve centralized and efficient resource scheduling and management for computation offloading optimization in EIoT. Edge computing provides computation guarantee for real-time data processing with the superiority of high-speed computation and low-delay transmission [5, 6]. Compared with cloud computing, edge computing alleviates the high transmission delay and network congestion by reducing transmission distance between devices and servers. In addition, it outperforms fog computing in terms of privacy, security, and computation capacity due to the unified security management and abundant computation resources.Computation offloading plays a crucial role in 5G and edge computing-integrated EIoT, which includes server selection and computation resource allocation [7, 8]. First, devices select an appropriate server and offload the computation task to the selected edge server via 5G for real-time processing. Then, edge servers allocate computation resources based on service requirements and computation capacity to reduce computation delay [9]. However, the computation offloading optimization for 5G and edge computing-integrated EIoT still faces several challenges.
(i)
Difficulty in tradeoff balance among various QoS parameters: services in 5G and edge computing-integrated EIoT have differentiated quality of service (QoS) requirements in delay, reliability, and so on. The QoS parameters are mutually influencing; e.g., improving reliability by using extra signaling overhead may harm delay and vice versa. Hence, it is necessary to balance the tradeoff among various QoS parameters through computation offloading optimization.(ii)
Coupling between large timescale server selection and small timescale computation resource allocation: server selection in large timescale leads to changes in the characteristics and number of devices served by servers, which in turn affects the computation resource allocation in small timescale. The inefficient decisions of computation resource allocation in small timescale directly affect the data computation delay performance of devices, which in turn affects the evaluation of the empirical performance of the servers in large timescale and may result in frequent server selection switching.(iii)
Multi-device competition in server selection and computation resource allocation: the contradiction between limited computation resources and multiple devices not only leads to competition for powerful servers in large timescale server selection but also causes competition for CPU frequency in small timescale computation resource allocation. In particular, the performance of delay and reliability is severely reduced by the competition for the same server.Computation offloading within multi-access edge computing (MEC) has drawn extensive research in academia. In [10], Zaman et al. provided a survey of mobility management-based task offloading in edge networks. The taxonomy of research work classification is based on objectives, constraints, models, scenarios, and so on, and several future research directions for offloading in edge computing were presented. Lagrange dual approach has been widely adopted for addressing computation offloading problems with convex properties. In [11], Zhou et al. studied a multi-access edge computing-based task offloading algorithm for lightweight user by combining machine learning with Lagrange dual approach to minimize offloading energy consumption. In [12], Wang et al. proposed a Lagrange dual method-based communication resource allocation algorithm to minimize the weighted sum-energy consumption in MEC. Nevertheless, Lagrange dual approach cannot handle nonconvex problems which are common in multi-access networks. As an alternative approach, game theory is explored to cope with multi-user task offloading problems in MEC. In [13], Apostolopoulos et al. proposed a noncooperative game-based distributed cognitive data offloading algorithm to maximize users’ utilities. In [14], Wang et al. proposed a noncooperative game-based computation offloading algorithm to adjust the offloading probability of each user and maximize vehicular utility. The drawback of game theory lies on required prior knowledge to derive utilities of players, which are essential to solve both cooperative and noncooperative games. Compared with game theory, reinforcement learning is more suitable for addressing computation offloading problems with uncertain information. In [15], Dinh et al. studied a model-free reinforcement learning-based computation offloading mechanism to maximize the utility function of each mobile user. In [16], Gao et al. proposed a novel Q learning-based computation offloading scheme for MEC system to minimize the system loss function. However, the aforementioned works have not considered the difficulty in tradeoff balance among various QoS requirements such as delay and reliability. Moreover, they focus on single timescale computation offloading optimization, while the coupling and mutual interconnection between large timescale server selection and small timescale computation resource allocation are neglected. The elimination of multi-access competition requires cooperation among different devices, which imposes another challenge on reinforcement learning-based computation offloading.Matching theory is an effective method to solve the optimization of mutual relationship between two sides [17]. In [18], Seng et al. proposed an efficient task virtual machine matching algorithm to coordinate the offloading problems among mobile users and edge servers. In [19], Zhou et al. proposed a low complexity and stable computation offloading mechanism to minimize the total network delay based on pricing-based matching. However, the existing works only consider the one-to-one matching, which is not suitable to the scenario that the same server can serve multiple devices at the same time. In [20], Liu et al. proposed a many-to-one matching-based channel allocation algorithm for mobile users, which achieves higher throughput performance. In [21], Wang et al. proposed a many-to-one matching theory-based subchannel allocation algorithm to reduce the energy efficiency. However, the joint optimization of reliability and delay is ignored. In [22], Zhang et al. proposed a joint optimization algorithm of computation offloading and computation resource allocation, which optimizes network stability and achieves the tradeoff between energy efficiency and average service delay. Nevertheless, the aforementioned works do not consider the coupling between small timescale computation resource allocation and large timescale sever selection.Motivated by the aforementioned challenges including difficulty in tradeoff balance among various QoS parameters, coupling between large timescale server selection and small timescale computation resource allocation, and the multi-device competition in server selection and computation resource allocation, we propose an empirical matching-based computation offloading optimization algorithm for 5G and edge computing-integrated EIoT. The optimization objective is to minimize the computation offloading delay by jointly optimizing large timescale server selection and small timescale computation resource allocation. We first model the large timescale server selection problem as a many-to-one matching problem, which can be decoupled from small timescale computation resource allocation by establishing matching preference lists based on empirical performance. Then, the large timescale server selection problem is solved by pricing-based matching with quota algorithm. Furthermore, based on the obtained suboptimal result of large timescale server selection, the small timescale computation resource allocation problem is subsequently solved by Lagrange dual decomposition, the result of which is used to update large timescale empirical performance. Finally, extensive simulations are carried out to demonstrate the superior performance of the proposed algorithm by comparing it with existing algorithms. The main contributions of this paper are summarized as follows:(i)
Differentiated QoS guarantee: differentiated QoS demands such as reliability and delay are guaranteed through the minimization of the long-term total delay of all devices under the constrains of server computation capacity and transmission signal-to-interference-plus-noise ratio (SINR). Specifically, reliability is enforced by eliminating servers which cannot satisfy the SINR constraint from the device preference lists.(ii)
Multi-timescale computation offloading optimization: server selection is optimized in large timescale based on empirical matching with empirical performance enabled matching preference list and pricing-based matching with quota enabled matching conflict elimination. On the basis, computation resource allocation is optimized in small timescale based on Lagrange dual decomposition to reduce computation delay.(iii)
Extensive performance evaluation: compared with two state-of-the-art algorithms, simulation results demonstrate that the proposed algorithm has superior performance in computation offloading delay. Moreover, the impacts of key parameters such as quota and SINR threshold on delay performance are revealed to provide guidance for the real-world implementation of computation offloading optimization in 5G and edge computing-integrated EIoT.The rest of the paper is organized as follows. Section2 demonstrates the system model of computation offloading for 5G and edge computing-integrated EIoT and formulates the multi-timescale joint optimization problem. Section 3 introduces the proposed empirical matching-based computation offloading optimization algorithm. The simulation results are shown in Section 4. Section 5 concludes the paper.


## 2. System Model

In this paper, we consider a scenario of computation offloading for 5G and edge computing-integrated EIoT, as shown in Figure1. The set of M devices and N base stations (BSs) are represented as M=1,2,⋯,m,⋯,M and N=1,2,⋯,n,⋯,N, respectively. The edge server and BS are located in the same place to provide computation and communication services. For simplicity, we denote the sets of BS and edge server as N. An example is shown in Figure 1, where the process of computation offloading includes two stages, i.e., server selection and computation resource allocation. In the first stage, when devices 1, 2, and 3 select the same BS 1 with limited offloading quota of 2 devices, BS 1 chooses to allocate computation resources for devices 1 and 2 and reject the access request of device 3. Device 3 finally offloads the computation task to BS 2 with a larger quota. We assume that BSs receive the time synchronization signal from the 5G time synchronization network and broadcast to all edge servers and devices to ensure that computation offloading is performed on the basis of time synchronization [15, 23].Figure 1
Computation offloading for 5G and edge computing-integrated EIoT.A slot model is adopted [24] where server selection is optimized in large timescale, i.e., epoch, and computation resource allocation is optimized in small timescale, i.e., slot. The total optimization period has G epochs, each of which consists of T0 slots, i.e., T=GT0. The sets of epochs and slots are denoted as G=1,⋯,g,⋯,G and T=1,⋯,t,⋯,T. The slot set of the g-th epoch is given by
(1)Tg=g−1T0+1,g−1T0+2,⋯,gT0.The key notations used in this paper are summarized in Table1.Table 1
Summary of notations.
NotationsDefinitionNotationsDefinitionMNumber of devicesτm,nOtTransmission delay ofm to n in the t-th slotNNumber of BSsτm,nCtComputation delay for processingAmt in the t-th slotGNumber of epochsτm,ntThe total computation offloading delayTNumber of slotsfn,maxThe maximum computation resourcesGSet of epochsfm,ntAllocated computation resources byn to mTSet of slotsLThe preference list of devicesMSet of devicesγm,ntSINR betweenm and n in the t-th slotNSet of BSs or edge serversRm,ntTransmission rate betweenm and n in the t-th slotxm,ngServer selection variableθm,ngPreference value ofm towards n in the g-th epochBnTransmission bandwidthpngServer price of matchingm with nPTXtTransmission powerτ~m,ngAverage offloading delay ofm in the g-th epochhm,ntChannel gain betweenm and nγminSINR threshold for data reliable transmissionN0Noise spectral power densityzIterative index of Lagrangian multiplier updateλm,ntElectromagnetic interference powerρζntt,zThe update step length ofζntζntLagrangian sub vectorεmData computation density ofmQnThe quota ofnAmtThe size of packets arriving atm in the t-th slot


### 2.1. Transmission Model

At each epoch, a device selects a server for computation offloading. Definexm,ng as the server selection variable, where xm,ng=1 represents that device m selects server n for computation offloading, and otherwise, xm,ng=0. Considering uplink data transmission, the SINR between device m and server n in the t-th slot is [25]
(2)γm,nt=PTXthm,ntBnN0+λm,nt,where Bn is the transmission bandwidth. PTXt is the transmission power, hm,nt is the channel gain between device m and server n in the t-th slot, N0 is the noise spectral power density, and λm,nt is the electromagnetic interference power.To ensure reliability requirement, SINR constraint is given by(3)γm,nt≥γmin,where γmin is SINR threshold for data reliable transmission. The transmission rate between device m and server n in the t-th slot is given by
(4Rm,nt=Bnlog1+γm,nt.We assume that the size of packets arriving at devicem in the t-th slot is Amt. Hence, the transmission delay of device m offloading Amt data to server n in the t-th slot is
(5)τm,nOt=AmtRm,nt.


### 2.2. Computation Model

Definefm,nt as the allocated computation resources by server n to device m. The computation delay for processing Amt data in the t-th slot [26] is given by
(6)τm,nCt=εmAmtfm,nt,where εm is the data computation density of device m, i.e., the required CPU cycles to process one bit data.The total allocated computation resource of servern should be lower than the maximum computation resource fn,max, i.e.,
(7)∑m=1Mfm,nt≤fn,max.


### 2.3. Problem Formulation

The total delay that devicem selects server n for computation offloading is composed of the transmission delay and the computation delay, i.e.,
(8)τm,nt=τm,nOt+τm,nCt.The objective is to minimize the long-term total delay of all devices under the constrains of servers’ computation capacity and transmission reliability, which can be expressed as(9)P1:minxm,ng,fm,nt∑t=1T∑m=1M∑n=1Nxm,ngτm,nts.t.C1:xm,ng=0,1,∀m∈M,∀n∈N,∀g∈G,C2:∑m=1Mxm,ng≤Qn,∀n∈N,∀g∈G,C3:∑n=1Nxm,ng=1,∀m∈M,∀g∈G,C4:∑m=1Mfm,nt≤fn,max,∀n∈N,∀t∈T,C5:γm,nt≥γmin,∀m∈M,∀t∈T,where Qn is the quota of server n, C2 represents that each edge server can be selected by at most Qn devices at the same time, C3 represents that each device can select only one edge server for computation offloading in an epoch, C4 represents the edge server computation resource constraint, and C5 represents the SINR constraint.We neglect energy consumption because major delay-sensitive EIoT devices can continuously draw energy from the power grid. Nevertheless, the proposed algorithm can also be extended to the scenario where energy consumption is minimized.


## 2.1. Transmission Model

At each epoch, a device selects a server for computation offloading. Definexm,ng as the server selection variable, where xm,ng=1 represents that device m selects server n for computation offloading, and otherwise, xm,ng=0. Considering uplink data transmission, the SINR between device m and server n in the t-th slot is [25]
(2)γm,nt=PTXthm,ntBnN0+λm,nt,where Bn is the transmission bandwidth. PTXt is the transmission power, hm,nt is the channel gain between device m and server n in the t-th slot, N0 is the noise spectral power density, and λm,nt is the electromagnetic interference power.To ensure reliability requirement, SINR constraint is given by(3)γm,nt≥γmin,where γmin is SINR threshold for data reliable transmission. The transmission rate between device m and server n in the t-th slot is given by
(4Rm,nt=Bnlog1+γm,nt.We assume that the size of packets arriving at devicem in the t-th slot is Amt. Hence, the transmission delay of device m offloading Amt data to server n in the t-th slot is
(5)τm,nOt=AmtRm,nt.


## 2.2. Computation Model

Definefm,nt as the allocated computation resources by server n to device m. The computation delay for processing Amt data in the t-th slot [26] is given by
(6)τm,nCt=εmAmtfm,nt,where εm is the data computation density of device m, i.e., the required CPU cycles to process one bit data.The total allocated computation resource of servern should be lower than the maximum computation resource fn,max, i.e.,
(7)∑m=1Mfm,nt≤fn,max.


## 2.3. Problem Formulation

The total delay that devicem selects server n for computation offloading is composed of the transmission delay and the computation delay, i.e.,
(8)τm,nt=τm,nOt+τm,nCt.The objective is to minimize the long-term total delay of all devices under the constrains of servers’ computation capacity and transmission reliability, which can be expressed as(9)P1:minxm,ng,fm,nt∑t=1T∑m=1M∑n=1Nxm,ngτm,nts.t.C1:xm,ng=0,1,∀m∈M,∀n∈N,∀g∈G,C2:∑m=1Mxm,ng≤Qn,∀n∈N,∀g∈G,C3:∑n=1Nxm,ng=1,∀m∈M,∀g∈G,C4:∑m=1Mfm,nt≤fn,max,∀n∈N,∀t∈T,C5:γm,nt≥γmin,∀m∈M,∀t∈T,where Qn is the quota of server n, C2 represents that each edge server can be selected by at most Qn devices at the same time, C3 represents that each device can select only one edge server for computation offloading in an epoch, C4 represents the edge server computation resource constraint, and C5 represents the SINR constraint.We neglect energy consumption because major delay-sensitive EIoT devices can continuously draw energy from the power grid. Nevertheless, the proposed algorithm can also be extended to the scenario where energy consumption is minimized.


## 3. Empirical Matching-Based Computation Offloading Optimization Algorithm for 5G and Edge Computing-Integrated EIoT

In this section, we introduce the problem transformation. Then, we propose the empirical matching-based large timescale server selection algorithm and Lagrange dual decomposition-based small timescale computation resource allocation for 5G and edge computing-integrated EIoT.


### 3.1. Problem Transformation

The long-term stochastic joint optimization problemP1 includes two subproblems, i.e., large timescale server selection problem and small timescale computation resource allocation problem. The large timescale server selection problem is first modeled as a many-to-one matching problem, which is decoupled from small timescale computation resource allocation by establishing matching preference list based on empirical performance of delay and reliability. Then, the large timescale server selection problem is solved by pricing-based matching with quota algorithm. Based on the obtained suboptimal result of large timescale server selection strategy, the small timescale computation resource allocation problem is subsequently solved by Lagrange dual decomposition, the result of which is used to update large timescale empirical performance.


### 3.2. Empirical Matching-Based Large Timescale Server Selection

The large timescale server selection optimization problem is transformed into a many-to-one matching problem, which is defined as a triple (M,N,L), where M and N represent the sets of matching devices and servers, respectively, and L represents the preference list of devices.Theorem 1.
A matchingϕ is a many-to-one correspondence of set M to set N based on the preference list L. ϕm=n represents the matching of device m and server n, i.e., xm,ng=1. Specially, server n can match at most Qn devices at the same time.To decouple the large timescale server selection from the small timescale resource allocation, the preference list is established based on empirical performance of delay and reliability. The empirical matching-based large timescale server selection algorithm is summarized in Algorithm 1, including preference list establishment and the pricing-based iterative matching [27].


#### 3.2.1. Preference List Establishment

In the initialization, each EIoT device first traverses all servers once to obtain the value ofτ~m,ng. At the beginning of the g-th period, the server selection decision is made based on the empirical information up to the current period. Thus, the preference value of device m towards server n in the g-th period is defined as θm,ng, which is expressed as
(10)θm,ng=−∑i=0g−1xm,niτ~m,ni∑i=0g−1xm,ni−png,where png represents the server price of matching device m with server n, the initial value of which is set as zero and τ~m,ng represents the average offloading delay of device m in the g-th epoch, which is expressed as
(11)τ~m,ng=1T0∑t=g−1T0gT0∑n=1Nxm,ntτm,nt.


#### 3.2.2. The Implementation Procedure of Pricing-Based Iterative Matching

#### 3.2.3. Empirical Matching-Based Large Timescale Server Selection Algorithm

(Step 1)
Wheng=0, initialize xm,ng=0, qn=Qn, png=0, ∀m∈M,∀n∈N,∀g∈G [1]. Define Θ as the set of unmatched devices, and set Θ=M at the beginning. Define Γn as the set of devices proposed to server n, and set Γn=∅ at the beginning. All devices traverse all servers once to complete the initialization of the preference list g≤G.(Step 2)
When $g \le G$, eachm∈Θ calculates its preference value θm,ng towards n as (10) and sorts θm,ng in descending order to obtain the preference list Lmg.(Step 3)
Eachm∈M proposes its most preferred server in Lmg. Each server, e.g., n, adds m into Γn if m proposes n. Forn∈N, if ∣Γn∣≤qn, n matches with the devices, e.g., m, from the proposed devices, i.e., xm,nt=1. Update qn=qn−∣Γn∣. Update Θ=Θ\m. Otherwise, n updates the price png as (13). Unmatched devices execute steps 2~3, until every device m has been matched with a server, i.e., ϕm≠∅, or there exists no available server for unmatched device m.The implementation procedure of pricing-based matching consists of three phases, which are introduced as follows.Step 1.
Wheng=0, initialize xm,ng=0, qn=Q, png=0, ∀m∈M,∀n∈N,∀g∈G, the set of unmatched devices as Θ=M, and the set of devices which proposed to server n as Γn=∅.Step 2.
Eachm∈Θ calculates the preference value θm,ng for unmatched device m towards n as (10) and sorts θm,ng in a descending order to obtain the preference list Lmg. We introduce ≻m to compare the preferences towards different servers. For example, n≻mn′ means that device m prefers server n than server n′, which is expressed as
(12)n≻mn′⇔θm,ng>θm,n′g.
When a server is selected by multiple devices exceeding to its quota, the server increases the pricepng with increment Δpn to eliminate matching conflicts, which is expressed as
(13)png=png+Δpn.
Then, the preference listLmg is updated according to new preference value as 10 and 12.Step 3.
Eachm∈M proposes to its most preferred server in Lmg. Then, each server, e.g., n, adds m into Γn if m proposes to n. n matches with the devices, e.g., m, from the proposed devices, i.e., xm,ng=1. Repeat until every device m has been matched with a server.
Therefore, the optimal matching result can be obtained as(14)xm,ng=1⇔ϕm=n.


#### 3.2.4. Complexity Analysis

The computation complexity of the proposed server selection algorithm mainly depends on preference value calculation, preference list establishment, and pricing-based iterative matching process, where the complexities of these three steps are, respectivelyOMN, OMNlogMN, and OMN. Hence, the complexity of the proposed algorithm is O2MN+MNlogMN.


### 3.3. Lagrange Dual Decomposition-Based Small Timescale Computation Resource Allocation

Based on the many-to-one matching-based large timescale server selection, the small timescale computation resource allocation is subsequently optimized. For edge servern, the computation resource allocation problem in the t-th slot can be expressed as
(15)P2:minfm,ntΨnts.t.C3:∑m=1Mfm,nt≤fn,max,∀n∈N,∀t∈T,where Ψnt can be expressed as
(16)Ψnt=∑m=1Mτm,nCt=∑m=1MεmAmtfm,nt.Based on Jensen’s inequality theorem [28], (16) satisfies fEΨnt≤EfΨnt while f· is a convex function. Therefore, P2 is a convex function and can be solved by Lagrange dual decomposition [29]. Define ζnt as a Lagrangian subvector corresponding to constraint C3. The Lagrange equation can be expressed as
(17)Lfm,nt,ζn=Ψnfm,nt+ζnt∑m=1Mfm,nt−fn,max.Based on Lagrange dual decomposition,P2 can be transformed as
(18)maxζnt>0minfm,ntLfm,nt,ζnt.Based on Karush-Kuhn-Tucker conditions, it can obtain(19)fm,nt,z+1=maxargfm,nt∇fm,nt=0,0,where z is the iterative index of Lagrangian multiplier update. Lagrangian multiplier ζnt update can be expressed as
(20)ζnt,z+1=maxζnt,z+∑m=1Mfm,nt−fn,maxρζntt,z,0,where ρζntt,z is the update step length.


## 3.1. Problem Transformation

The long-term stochastic joint optimization problemP1 includes two subproblems, i.e., large timescale server selection problem and small timescale computation resource allocation problem. The large timescale server selection problem is first modeled as a many-to-one matching problem, which is decoupled from small timescale computation resource allocation by establishing matching preference list based on empirical performance of delay and reliability. Then, the large timescale server selection problem is solved by pricing-based matching with quota algorithm. Based on the obtained suboptimal result of large timescale server selection strategy, the small timescale computation resource allocation problem is subsequently solved by Lagrange dual decomposition, the result of which is used to update large timescale empirical performance.


## 3.2. Empirical Matching-Based Large Timescale Server Selection

The large timescale server selection optimization problem is transformed into a many-to-one matching problem, which is defined as a triple (M,N,L), where M and N represent the sets of matching devices and servers, respectively, and L represents the preference list of devices.Theorem 1.
A matchingϕ is a many-to-one correspondence of set M to set N based on the preference list L. ϕm=n represents the matching of device m and server n, i.e., xm,ng=1. Specially, server n can match at most Qn devices at the same time.To decouple the large timescale server selection from the small timescale resource allocation, the preference list is established based on empirical performance of delay and reliability. The empirical matching-based large timescale server selection algorithm is summarized in Algorithm 1, including preference list establishment and the pricing-based iterative matching [27].


### 3.2.1. Preference List Establishment

In the initialization, each EIoT device first traverses all servers once to obtain the value ofτ~m,ng. At the beginning of the g-th period, the server selection decision is made based on the empirical information up to the current period. Thus, the preference value of device m towards server n in the g-th period is defined as θm,ng, which is expressed as
(10)θm,ng=−∑i=0g−1xm,niτ~m,ni∑i=0g−1xm,ni−png,where png represents the server price of matching device m with server n, the initial value of which is set as zero and τ~m,ng represents the average offloading delay of device m in the g-th epoch, which is expressed as
(11)τ~m,ng=1T0∑t=g−1T0gT0∑n=1Nxm,ntτm,nt.


### 3.2.2. The Implementation Procedure of Pricing-Based Iterative Matching

### 3.2.3. Empirical Matching-Based Large Timescale Server Selection Algorithm

(Step 1)
Wheng=0, initialize xm,ng=0, qn=Qn, png=0, ∀m∈M,∀n∈N,∀g∈G [1]. Define Θ as the set of unmatched devices, and set Θ=M at the beginning. Define Γn as the set of devices proposed to server n, and set Γn=∅ at the beginning. All devices traverse all servers once to complete the initialization of the preference list g≤G.(Step 2)
When $g \le G$, eachm∈Θ calculates its preference value θm,ng towards n as (10) and sorts θm,ng in descending order to obtain the preference list Lmg.(Step 3)
Eachm∈M proposes its most preferred server in Lmg. Each server, e.g., n, adds m into Γn if m proposes n. Forn∈N, if ∣Γn∣≤qn, n matches with the devices, e.g., m, from the proposed devices, i.e., xm,nt=1. Update qn=qn−∣Γn∣. Update Θ=Θ\m. Otherwise, n updates the price png as (13). Unmatched devices execute steps 2~3, until every device m has been matched with a server, i.e., ϕm≠∅, or there exists no available server for unmatched device m.The implementation procedure of pricing-based matching consists of three phases, which are introduced as follows.Step 1.
Wheng=0, initialize xm,ng=0, qn=Q, png=0, ∀m∈M,∀n∈N,∀g∈G, the set of unmatched devices as Θ=M, and the set of devices which proposed to server n as Γn=∅.Step 2.
Eachm∈Θ calculates the preference value θm,ng for unmatched device m towards n as (10) and sorts θm,ng in a descending order to obtain the preference list Lmg. We introduce ≻m to compare the preferences towards different servers. For example, n≻mn′ means that device m prefers server n than server n′, which is expressed as
(12)n≻mn′⇔θm,ng>θm,n′g.
When a server is selected by multiple devices exceeding to its quota, the server increases the pricepng with increment Δpn to eliminate matching conflicts, which is expressed as
(13)png=png+Δpn.
Then, the preference listLmg is updated according to new preference value as 10 and 12.Step 3.
Eachm∈M proposes to its most preferred server in Lmg. Then, each server, e.g., n, adds m into Γn if m proposes to n. n matches with the devices, e.g., m, from the proposed devices, i.e., xm,ng=1. Repeat until every device m has been matched with a server.
Therefore, the optimal matching result can be obtained as(14)xm,ng=1⇔ϕm=n.


### 3.2.4. Complexity Analysis

The computation complexity of the proposed server selection algorithm mainly depends on preference value calculation, preference list establishment, and pricing-based iterative matching process, where the complexities of these three steps are, respectivelyOMN, OMNlogMN, and OMN. Hence, the complexity of the proposed algorithm is O2MN+MNlogMN.


## 3.2.1. Preference List Establishment

In the initialization, each EIoT device first traverses all servers once to obtain the value ofτ~m,ng. At the beginning of the g-th period, the server selection decision is made based on the empirical information up to the current period. Thus, the preference value of device m towards server n in the g-th period is defined as θm,ng, which is expressed as
(10)θm,ng=−∑i=0g−1xm,niτ~m,ni∑i=0g−1xm,ni−png,where png represents the server price of matching device m with server n, the initial value of which is set as zero and τ~m,ng represents the average offloading delay of device m in the g-th epoch, which is expressed as
(11)τ~m,ng=1T0∑t=g−1T0gT0∑n=1Nxm,ntτm,nt.


## 3.2.2. The Implementation Procedure of Pricing-Based Iterative Matching

## 3.2.3. Empirical Matching-Based Large Timescale Server Selection Algorithm

(Step 1)
Wheng=0, initialize xm,ng=0, qn=Qn, png=0, ∀m∈M,∀n∈N,∀g∈G [1]. Define Θ as the set of unmatched devices, and set Θ=M at the beginning. Define Γn as the set of devices proposed to server n, and set Γn=∅ at the beginning. All devices traverse all servers once to complete the initialization of the preference list g≤G.(Step 2)
When $g \le G$, eachm∈Θ calculates its preference value θm,ng towards n as (10) and sorts θm,ng in descending order to obtain the preference list Lmg.(Step 3)
Eachm∈M proposes its most preferred server in Lmg. Each server, e.g., n, adds m into Γn if m proposes n. Forn∈N, if ∣Γn∣≤qn, n matches with the devices, e.g., m, from the proposed devices, i.e., xm,nt=1. Update qn=qn−∣Γn∣. Update Θ=Θ\m. Otherwise, n updates the price png as (13). Unmatched devices execute steps 2~3, until every device m has been matched with a server, i.e., ϕm≠∅, or there exists no available server for unmatched device m.The implementation procedure of pricing-based matching consists of three phases, which are introduced as follows.Step 1.
Wheng=0, initialize xm,ng=0, qn=Q, png=0, ∀m∈M,∀n∈N,∀g∈G, the set of unmatched devices as Θ=M, and the set of devices which proposed to server n as Γn=∅.Step 2.
Eachm∈Θ calculates the preference value θm,ng for unmatched device m towards n as (10) and sorts θm,ng in a descending order to obtain the preference list Lmg. We introduce ≻m to compare the preferences towards different servers. For example, n≻mn′ means that device m prefers server n than server n′, which is expressed as
(12)n≻mn′⇔θm,ng>θm,n′g.
When a server is selected by multiple devices exceeding to its quota, the server increases the pricepng with increment Δpn to eliminate matching conflicts, which is expressed as
(13)png=png+Δpn.
Then, the preference listLmg is updated according to new preference value as 10 and 12.Step 3.
Eachm∈M proposes to its most preferred server in Lmg. Then, each server, e.g., n, adds m into Γn if m proposes to n. n matches with the devices, e.g., m, from the proposed devices, i.e., xm,ng=1. Repeat until every device m has been matched with a server.
Therefore, the optimal matching result can be obtained as(14)xm,ng=1⇔ϕm=n.


## 3.2.4. Complexity Analysis

The computation complexity of the proposed server selection algorithm mainly depends on preference value calculation, preference list establishment, and pricing-based iterative matching process, where the complexities of these three steps are, respectivelyOMN, OMNlogMN, and OMN. Hence, the complexity of the proposed algorithm is O2MN+MNlogMN.


## 3.3. Lagrange Dual Decomposition-Based Small Timescale Computation Resource Allocation

Based on the many-to-one matching-based large timescale server selection, the small timescale computation resource allocation is subsequently optimized. For edge servern, the computation resource allocation problem in the t-th slot can be expressed as
(15)P2:minfm,ntΨnts.t.C3:∑m=1Mfm,nt≤fn,max,∀n∈N,∀t∈T,where Ψnt can be expressed as
(16)Ψnt=∑m=1Mτm,nCt=∑m=1MεmAmtfm,nt.Based on Jensen’s inequality theorem [28], (16) satisfies fEΨnt≤EfΨnt while f· is a convex function. Therefore, P2 is a convex function and can be solved by Lagrange dual decomposition [29]. Define ζnt as a Lagrangian subvector corresponding to constraint C3. The Lagrange equation can be expressed as
(17)Lfm,nt,ζn=Ψnfm,nt+ζnt∑m=1Mfm,nt−fn,max.Based on Lagrange dual decomposition,P2 can be transformed as
(18)maxζnt>0minfm,ntLfm,nt,ζnt.Based on Karush-Kuhn-Tucker conditions, it can obtain(19)fm,nt,z+1=maxargfm,nt∇fm,nt=0,0,where z is the iterative index of Lagrangian multiplier update. Lagrangian multiplier ζnt update can be expressed as
(20)ζnt,z+1=maxζnt,z+∑m=1Mfm,nt−fn,maxρζntt,z,0,where ρζntt,z is the update step length.


## 4. Simulation Results

In this section, we introduce the simulation results and analysis. We consider a computation offloading scenario of EIoT with20 devices and 5 servers. In the case of largescale fading, the channel gain is calculated according to hm,nt=127+30logrm,n [30], where rm,n is the distance between device m and server n, and distributed within 0.03,0.05 km. According to the actual environment of EIoT, the electromagnetic interference power varies from 28 dBm to 30 dBm. The specific simulation parameters are summarized in Table 2 [31–35]. Two existing algorithms are employed for comparison. The first one is the price matching-based computation offloading (PMCO) algorithm [27], where server-side computation resources are allocated equally. The second one is the greedy matching-based computation offloading (GMCO) algorithm [36], where large timescale server selection is solved based on greedy matching strategy and small timescale computation resource allocation is implemented once in the first time slot of each epoch. In addition, we extend the proposed algorithm to a large-scale computation offloading scenario with 100 devices to verify its effectiveness and robustness. The simulation software is MATLAB 2021. The real execution time of the proposed algorithm is about 49 ms per time slot, which achieves real-time or near-real-time. When adopting dedicated execution module such as DSP, the real execution time can be further reduced to millisecond level or even microsecond level.Table 2
Simulation parameters.
ParameterValueParameterValueM20N5Qn6G20T200T010Bn0.1 MHzγmin10 dBAm0.2,0.5 MbitsPTX0.1 Wfn,max10,30 GHzN0−114 dBmΔpn5εm1000 cycles


### 4.1. Transmission Delay Performance

Figure2 shows the box plots of transmission delay. Compared with PMCO and GMCO, the proposed algorithm can reduce the median transmission delay by 13.85% and 19.82% and reduce the transmission delay fluctuation by 65.79% and 68.29%, respectively. The proposed algorithm utilizes empirical matching-based large timescale server selection to reduce the transmission delay, thus performing the best. PMCO outperforms GMCO in terms of transmission delay because PMCO considers the server selection optimization based on price matching, thus effectively reducing the transmission delay.Figure 2
Transmission delay of different algorithms.


### 4.2. Computation Delay Performance

Figure3 show the box plots of computation delay. Compared with PMCO and GMCO, the median computation delay is decreased by 24.78% and 16.05%, and the computation delay fluctuation is decreased by 46.77% and 31.25%, respectively. The proposed algorithm utilizes Lagrange dual decomposition-based small timescale computation resource allocation to improve computation delay performance, thus performing the best. PMCO performs worse than GMCO in terms of computation delay. The reason is that GMCO considers the computation resource allocation, which leads to a lower computation delay.Figure 3
Computation delay of different algorithms.


### 4.3. Total Computation Offloading Delay Performance

Figure4 shows the total computation offloading delay versus time slot. The proposed algorithm outperforms PMCO and GMCO by 14.96% and 19.79%. The reason is that the proposed algorithm can avoid adversarial channels to improve delay performance through large timescale server selection. Then, given the large timescale server selection strategies, it further optimizes the small timescale computation resource allocation in each slot. However, PMCO neglects the optimization of computation resource allocation. The GMCO algorithm based on greedy matching and single-slot computation resource allocation cannot solve matching conflict from the perspective of the whole network and adjust the allocation strategies based on real-time information.Figure 4
Total computation offloading delay versus time slot.Figure5 shows the total computation offloading delay versus number of devices. As the number of devices increases from 10 to 100, the total computation offloading delay of PMCO and GMCO increases by 28.21% and 28.99%, while the total computation offloading delay of the proposed algorithm is slightly increased by 10.14%. The reason why total computation offloading delay increases is that the conflicts caused by multiple devices selecting the same server increases, and the computation resource allocated to each device is poorer. Even in a multi-access scenario with 100 devices, the proposed algorithm can adaptively balance the performance return of all devices through pricing-based iterative matching and adjust the resource allocation strategies based on dynamic data arrival.Figure 5
Total computation offloading delay versus number of devicesM (M=10~100).Figure6 shows the impact of the quota Qn on transmission delay and computation delay. The bars in the figure represent the transmission delay and the curves represent the computation delay. When Qn increases from 4 to 8, the transmission delay and computation delay of PMCO and GMCO are decreased by 7.85%, 6.62%, 6.79%, and 11.13%, in which those of the proposed algorithm are obviously decreased by 14.11% and 11.13%. The reason for it is that the final delay performance depends on the worst computation offloading situation, where the larger Qn means the greater offloading possibility to servers with better channels and computation resources for devices. In addition, the proposed algorithm can well coordinate the competition among multiple devices for servers and computation resources based on empirical information and real-time resource allocation.Figure 6
The impact of quotaQn on transmission delay and computation delay.Table3 shows the impact of γmin on total computation offloading delay. With the increasing of γmin, the total computation offloading delay decreases first and then increases. When γmin=12 dB, the total computation offloading delay reaches the minimum value. The reason is that when γmin increases from 8 to 12 dB, stringent reliability constraints impel devices to select servers with better empirical channel states, thus significantly reducing transmission delay at the beginning. However, as γmin continues to increase from 12 to 16 dB, the servers with better channel states will be occupied by more devices resulting in a higher computation delay.Table 3
The impact ofγmin on total computation offloading delay.
γmin (dB)810121416Proposed75.24ms74.80 ms73.25 ms74.46 ms75.82 msPMCO95.80 ms94.23 ms93.15 ms95.12 ms95.60 msGMCO92.73 ms90.95 ms89.82 ms90.23 ms92.86 ms


## 4.1. Transmission Delay Performance

Figure2 shows the box plots of transmission delay. Compared with PMCO and GMCO, the proposed algorithm can reduce the median transmission delay by 13.85% and 19.82% and reduce the transmission delay fluctuation by 65.79% and 68.29%, respectively. The proposed algorithm utilizes empirical matching-based large timescale server selection to reduce the transmission delay, thus performing the best. PMCO outperforms GMCO in terms of transmission delay because PMCO considers the server selection optimization based on price matching, thus effectively reducing the transmission delay.Figure 2
Transmission delay of different algorithms.


## 4.2. Computation Delay Performance

Figure3 show the box plots of computation delay. Compared with PMCO and GMCO, the median computation delay is decreased by 24.78% and 16.05%, and the computation delay fluctuation is decreased by 46.77% and 31.25%, respectively. The proposed algorithm utilizes Lagrange dual decomposition-based small timescale computation resource allocation to improve computation delay performance, thus performing the best. PMCO performs worse than GMCO in terms of computation delay. The reason is that GMCO considers the computation resource allocation, which leads to a lower computation delay.Figure 3
Computation delay of different algorithms.


## 4.3. Total Computation Offloading Delay Performance

Figure4 shows the total computation offloading delay versus time slot. The proposed algorithm outperforms PMCO and GMCO by 14.96% and 19.79%. The reason is that the proposed algorithm can avoid adversarial channels to improve delay performance through large timescale server selection. Then, given the large timescale server selection strategies, it further optimizes the small timescale computation resource allocation in each slot. However, PMCO neglects the optimization of computation resource allocation. The GMCO algorithm based on greedy matching and single-slot computation resource allocation cannot solve matching conflict from the perspective of the whole network and adjust the allocation strategies based on real-time information.Figure 4
Total computation offloading delay versus time slot.Figure5 shows the total computation offloading delay versus number of devices. As the number of devices increases from 10 to 100, the total computation offloading delay of PMCO and GMCO increases by 28.21% and 28.99%, while the total computation offloading delay of the proposed algorithm is slightly increased by 10.14%. The reason why total computation offloading delay increases is that the conflicts caused by multiple devices selecting the same server increases, and the computation resource allocated to each device is poorer. Even in a multi-access scenario with 100 devices, the proposed algorithm can adaptively balance the performance return of all devices through pricing-based iterative matching and adjust the resource allocation strategies based on dynamic data arrival.Figure 5
Total computation offloading delay versus number of devicesM (M=10~100).Figure6 shows the impact of the quota Qn on transmission delay and computation delay. The bars in the figure represent the transmission delay and the curves represent the computation delay. When Qn increases from 4 to 8, the transmission delay and computation delay of PMCO and GMCO are decreased by 7.85%, 6.62%, 6.79%, and 11.13%, in which those of the proposed algorithm are obviously decreased by 14.11% and 11.13%. The reason for it is that the final delay performance depends on the worst computation offloading situation, where the larger Qn means the greater offloading possibility to servers with better channels and computation resources for devices. In addition, the proposed algorithm can well coordinate the competition among multiple devices for servers and computation resources based on empirical information and real-time resource allocation.Figure 6
The impact of quotaQn on transmission delay and computation delay.Table3 shows the impact of γmin on total computation offloading delay. With the increasing of γmin, the total computation offloading delay decreases first and then increases. When γmin=12 dB, the total computation offloading delay reaches the minimum value. The reason is that when γmin increases from 8 to 12 dB, stringent reliability constraints impel devices to select servers with better empirical channel states, thus significantly reducing transmission delay at the beginning. However, as γmin continues to increase from 12 to 16 dB, the servers with better channel states will be occupied by more devices resulting in a higher computation delay.Table 3
The impact ofγmin on total computation offloading delay.
γmin (dB)810121416Proposed75.24ms74.80 ms73.25 ms74.46 ms75.82 msPMCO95.80 ms94.23 ms93.15 ms95.12 ms95.60 msGMCO92.73 ms90.95 ms89.82 ms90.23 ms92.86 ms


## 5. Conclusion

In this paper, we investigated a multi-timescale computation offloading optimization problem for 5G and edge computing-integrated EIoT. Specifically, we proposed an empirical matching-based computation offloading optimization algorithm, which includes the joint optimization of large timescale server selection and small timescale computation resource allocation. Compared with the existing PMCO and GMCO algorithms, the proposed algorithm could reduce the total computation offloading delay by14.96% and 19.79%, respectively. It could also reduce the median transmission delay by 13.85% and 19.82%, the transmission delay fluctuation by 65.79% and 68.29%, the median computation delay by 24.78% and 16.05%, and the computation delay fluctuation by 46.77% and 31.25%. Finally, future research directions are outlined.


### 5.1. Computation Offloading under Extensive EIoT Scenarios with Incomplete Information

In large-scale EIoT scenarios, considering the prohibitive signaling overheads, global state information such as the channel state between devices and servers, the amount of available computation resources of servers, and the computation resource allocation policy of servers is unknown to devices. Server selection needs to be optimized under incomplete information. A feasible approach is to empower computation offloading for EIoT by learning through interaction with the environment by exploring advanced artificial intelligence algorithms such as deep reinforcement learning and federated learning.


### 5.2. Insecure Computation Offloading under Malicious Attack

With the extensive access of massive devices, EIoT faces various malicious attacks including distributed denial of services (DDoS), time synchronization attack, sinkhole attack, and tampering attack. These malicious attacks make computation offloading in EIoT insecure, which results in loss and tampering of important information, such as fault data, alarm data, and load fluctuation, endangering the supply-demand balance as well as stable and secure operation of power grid. To solve this problem, advanced security technologies such as blockchain, identity authentication, encryption, and trusted computing can be adopted to ensure the secure data transmission and processing in computing offloading.


## 5.1. Computation Offloading under Extensive EIoT Scenarios with Incomplete Information

In large-scale EIoT scenarios, considering the prohibitive signaling overheads, global state information such as the channel state between devices and servers, the amount of available computation resources of servers, and the computation resource allocation policy of servers is unknown to devices. Server selection needs to be optimized under incomplete information. A feasible approach is to empower computation offloading for EIoT by learning through interaction with the environment by exploring advanced artificial intelligence algorithms such as deep reinforcement learning and federated learning.


## 5.2. Insecure Computation Offloading under Malicious Attack

With the extensive access of massive devices, EIoT faces various malicious attacks including distributed denial of services (DDoS), time synchronization attack, sinkhole attack, and tampering attack. These malicious attacks make computation offloading in EIoT insecure, which results in loss and tampering of important information, such as fault data, alarm data, and load fluctuation, endangering the supply-demand balance as well as stable and secure operation of power grid. To solve this problem, advanced security technologies such as blockchain, identity authentication, encryption, and trusted computing can be adopted to ensure the secure data transmission and processing in computing offloading.



---

*Source: 9162422-2022-04-15.xml*