# Multitask Offloading Strategy for Edge Computing in Time-Sensitive Networking

Authors: Junhua Chen; Chenggen Pu; Ping Wang; Xueda Huang; Yan Zhang; Yanfei Liu
Journal: Mobile Information Systems
 (2022)

---

## Abstract

Edge computing is a creative computing paradigm that enhances the computing capacity of the edge device close to the data source. As the key technology of edge computing, task offloading, which can improve the response speed and the stability of the network system, has attracted much attention and has been applied in many network scenarios. However, few studies have considered the application of task offloading in time-sensitive networking (TSN), which is a promising technology that has the potential to guarantee data delivery with bounded latency and low jitter. To this end, we establish a task offloading stream transmission model for TSN based on the queueing theory. With the model, the average response time can be achieved by quantitative calculation. Then, we introduce the backward method to construct a utility function and formulate an exact potential game to model the task offloading competition among edge devices considering the minimization of the average response time of all tasks. Furthermore, a distributed and sequential decision-making algorithm for multitask offloading (DSDA-MO) is proposed to find the Nash equilibrium. Through numerical studies, we evaluate the algorithm performance as well as the benefit of the multitask offloading mechanism. The results reveal that through the proposed game theoretic approach, we can obtain the optimal multitask offloading strategy, which can significantly reduce the task computation delay in TSN, within a finite number of rounds of calculation.


---

## Body

## 1. Introduction

With the advent of the era of Industry 4.0, related technologies, such as artificial intelligence (AI), cyber-physical systems (CPSs), and industrial internet of things (IIOT), have been deeply studied and developed [1, 2]. In many cases, such as the case of industrial equipment and systems sharing the communication channel in the industrial field network, the data packet delivery requires bounded latency and low jitter, which are known as deterministic real-time communication. The traditional network technology can no longer meet the requirements of deterministic real-time transmission of industrial data, let alone support the mixed transmission of periodic control data and emergency data in many complex industrial scenarios. To overcome this challenge, IEEE promotes a new real-time communication protocol standard, IEEE 802.1 Time-sensitive networking (TSN) [3, 4], which evolved based on IEEE 802.1 audio video bridging (AVB) series standards. Utilizing network-wide clock synchronization, time-aware haper (TAS), traffic scheduling, and other mechanisms, TSN realizes the shared network transmission of time-sensitive streams and nonreal-time streams within the local area network.During the development process of industrial network technology, the industry and academy find that the traditional centralized cloud computing model cannot satisfy the requirement of real-time computing in the industrial field. Therefore, a new computing paradigm, named edge computing (EC), has come out to address the challenge of real-time processing data from the network edge. EC provides an architecture for migrating computation power from the remote cloud to the local position close to the data source by deploying edge computing nodes (ECNs) or edge computing servers (ECSs) near the edge devices [5–8].Since TSN can reduce the delay of data transmission and EC can reduce the time cost of data computation, the combination of TSN and EC technologies will be able to decrease the overall delay of the industrial system. The core principles of EC are computing resource allocation and computing service provision. A common application of EC is task offloading from edge devices to ECN/ECS, i.e., tasks generated in edge devices are delivered to ECN/ECS for remote computing [9]. Recently, several studies have investigated computing task offloading strategies in many network environments for EC [10–12]. However, to the best of our knowledge, few studies have considered their applications in TSN. We are the first to study the computing task offloading strategy in TSN.The TSN standard comprises a series of protocol clusters, of which IEEE 802.1Qbv [13] is now widely applied in industrial scenarios. The core of IEEE 802.1Qbv is the principle of time-triggered communication controlled by gate control list (GCL) according to the traffic priority. The GCL is usually generated in advance of data delivery in TSN according to the transmission requirements of the given application. Generally, edge devices are ignorant of the details of GCL. Hence, it is challenging to evaluate the task offloading cost and design the multi-task offloading strategy, i.e., whether each task should be computed locally or offloaded to an ECN/ECS. For scenarios that are similar to the uncertain transmission conditions, Li [14] applied the queuing theory to model and evaluate the average delay encountered in task offloading. Moreover, Li proposed a strategy for adjusting the arrival rates of tasks offloaded from user equipment (UE) to different mobile edge computing (MEC) [15] servers based on the average delay. Motivated by these ideas, this paper treats each edge device as an M/G/1 queueing system continuously generating multitasks. Moreover, it is assumed that the hybrid stream, which is composed of the task offloading substreams and the original TSN substreams with the same priority, injects into an M/G/1 queue with server breakdown in the TSN switch. Based on it, this paper proposes a system model and designs a strategy decision-making algorithm on the basis of the potential game theory. The technical contributions of this article can be summarized as follows:(1)
This paper establishes a task offloading streams transmission model by treating each edge device as an M/G/1 queueing system continuously generating multitasks and treating the TSN switch as many M/G/1 queueing systems with server breakdown. Through the proposed model, the average response time of tasks generated on each edge device can be obtained through quantitative calculation, and the optimal multitask offloading strategy of the edge device can be studied mathematically and rigorously.(2)
This paper constructs a utility function with the backward method and formulates an exact potential game to model the task offloading competition among edge devices considering the minimization of the average response time of all tasks.(3)
To effectively find the Nash equilibrium, a distributed and sequential decision-making algorithm for multitask offloading (DSDA-MO) is proposed, and its performance is studied in simulation experiments.The remainder of this paper is structured as follows: in Section2, the related work is presented. In Section 3, we describe the system model. In Section 4, we introduce the game formulating the competition among edge devices for edge computing resources and propose a DSDA-MO algorithm to search the Nash equilibrium. In Section 5, numerical results are presented, and the algorithm is evaluated. Finally, the paper is concluded in Section 6.


## 2. Related Work

As the key technology of EC, computing offloading refers to offloading tasks generated on terminal devices to ECN/ECS based on rational offloading decisions and resource allocation strategies [16]. Utilizing the computing offloading mechanism, the terminal devices, also named edge devices, with limited computing resources can achieve less response time and energy consumption by the tasks executing on ECN/ECS. There are three main goals for task offloading decision-making: shorten the task computing time, reduce the device energy consumption, and jointly optimize the weighted sum of task computing time and energy consumption.Over the past few years, task offloading in MEC has received more and more attention. Several studies jointly model the computing mode decision problem and resource allocation problem. Liu et al. [17] propose an efficient one-dimensional search algorithm to find the optimal task scheduling strategy. It uses the Markov chain to analyze the average delay and energy consumption of each task on the mobile device for computing task offloading strategies, according to the queuing state of the task buffer, the execution state of the local processing unit, and the state of the transmission unit. It establishes a mathematical model of delay minimization problems with power constraints. Chen and Hao [18] study the task offloading problem in ultradense networks from the perspective of software-defined networking (SDN) thinking and model the task offloading problem as an NP-hard mixed integer nonlinear programming (MINLP) problem. In reference [19], mobile devices offload computing tasks to multiple ECSs and download results from the MEC servers in a preset time slot. By jointly optimizing task scheduling and resource allocation, the computational delay of tasks is minimized.Recently, many pieces of literature have proposed some approaches to deal with multitask offloading situations [20–23]. In these approaches, the author of reference [20] constructs a multitask scheduling scheme for multicore mobile devices to balance the execution cost and energy consumption; the author of reference [21] aims to the tradeoff for energy consumption and time cost of a single task with different offloadable components, the author of reference [22] proposes a decision-making strategy for the multitask offloading game and constructs the Nash equilibrium. In addition, many researchers apply game theoretic approaches for computation offloading and resource allocation with minimizing the time cost as an optimal objective, by treating the multiuser computation offloading strategy making as a noncooperative game [24–29].Overall, a lot of literature focuses on modeling task offloading decision-making mode and has promoted many excellent algorithms to resolve the optimal problem of the offloading strategies for EC in the mobile network. However, few studies have considered the TSN scenarios. To the best of our knowledge, this is the first study that reviews the task offloading problem for EC in the TSN environment. In TSN, the tasks are generated in the queue in each edge device, and the transmission packages are cached in the queues of TSN switches for delivery controlled by GLC. Utilizing queueing theory to evaluate task offloading time cost seems an appropriate choice. The author of reference [30] uses M/M/1 queueing theory to model the task offloading competition as a noncooperative game in a three tiers architecture, consisting of mobile nodes, cloudlets, and cloud servers. Li [14] establishes an M/G/1 queueing model for the UEs and an M/G/m queueing model for the MEC and models a noncooperative game to study the stabilization of a competitive mobile edge computing environment. Inspired by the previous studies, we model multitask offloading competition in TSN as a potential game by using queueing theory.


## 3. System Model

This section studies a TSN system comprising multiple TSN end nodes, one TSN switch,M edge devices denoted by the set M=D1,D2,…,DM, and N ECSs denoted by the set N=E1,E2,…,EN. The multitask offloading in the TSN system is shown in Figure 1, and the notations and definitions in the proposed system model are listed in Table 1. We consider that each edge device has a queueing system to process the continuously generated tasks. A task in Di can be further described as ti=li,ρi, where li is the task body size (including the code and data) and ρi is the processing density in cycles per bit, i.e., the number of cycles required to process a unit bit of the task body. The task processing time in the edge device can be calculated as li∗ρi/f^i, where f^i is the process frequency of the given edge device Di in cycles per second (e.g., MIPS). Usually, ρi is treated as a constant according to the task application type and li follows an arbitrary probability distribution; thus, the task computing time is also an arbitrary random variable. We assume that in each edge device, the task interarrival time follows an exponential distribution. Therefore, each edge device can be treated as an M/G/1 queueing system.Figure 1
Multitask offloading in time-sensitive networking system. The task offloading substream to ECS n is composed of offloading packages marked in blue from all edge devices, and the original TSN substream to ECS n consists of TSN packages marked in yellow from all TSN end nodes.Table 1
Summary of notations and definitions.
NotationDefinitionDiThe edge devicei, 1≤i≤MEnThe ECSn, 1≤n≤NMThe set of edge devices,M=D1,D2,…,DMNThe set of ECSs,N=E1,E2,…,EMtia task generated onDili,∆The size of the unoffloadable tasks onDi, including code and datali,∗The size of the offloadable tasks onDi , including code and dataρiThe processing density of tasks inDiλi,∆The arrival rate of the unoffloadable tasks generated onDiλi,nIfn=0, the arrival rate of tasks computed locally in Di if 1≤n≤N, the arrival rate of tasks offloaded from Di to EnλiThe sum of arrival rates of offloadable tasks generated onDi, λi=∑n=0Nλi,nλ˜p,nThe arrival rate of the original TSN stream of priorityp to En in the TSN gatewayΛnThe available maximum offloading task arrival rate from all edge devices toEnvThe bandwidth of the TSN networkCi,nIfn=0, the execution time of tasks computed locally in Di if 1≤n≤N, the execution time of the tasks generated on Di and computed remotely in EnC¯i,nMean ofCi,nQ¯∗,nThe average time that the members of the hybrid streams spend in queueQp,nT¯i,nIfn=0, the average time cost of the tasks computed locally in Di if 1≤n≤N, the average time cost of the tasks generated on Di and computed remotely in EnT¯i,0lThe average time cost when all tasks are processed locally inDiT¯iThe average time cost of all tasks generated onDiW¯∗,nThe average waiting time of the tasks from all edge devices toEn spent in TSN gatewaygp,nThe length of the original TSN packages in queueQp,nhnThe service interrupted time of queueQp,nΩ0,nThe service time of the original the TSN substream inQp,nΩ∗,nAll the service time of the compound stream inQp,nf^iThe processing frequency ofDifnThe processing frequency ofEnGThe multi-task offloading gameSiThe task offloading strategy of theDiS−iThe task offloading strategy set of all edge devices exceptDiSThe task offloading strategy space of all edge devicesξThe accuracy parameterBenefiting from the edge computing technology, edge devices could choose tasks to be offloaded to the nearby ECSs to achieve faster computation speed or less power consumption than local computing. The tasks on Di are divided into two types of M/G/1 substreams: unoffloadable computing task substream and offloadable computing task substream. The latter includes local computing tasks and remote computing tasks offloaded to other ECSs. Correspondingly, the whole task arrival rate of Di can be formulated as λi=λi,∆+λi,0+∑n=1Nλi,n, where λi,∆ is the arrival rates of the tasks unoffloadable, λi,0 is the arrival rates of the tasks that are offloadable and executed locally, and λi,n is the arrival rates of the tasks that are to be offloaded to the ECS En. The arrival rate distribution vector λi,∆,λi,0,λi,1,⋯,λi,N (for 1≤i≤M) represents the computation offloading strategy of Di. Similarly, there are two types of task body sizes, which are denoted as li,∆ and li,∗ corresponding to the aforementioned unoffloadable and offloadable task substreams, respectively; these variables are independent and identically distributed (i.i.d.) random variables with an arbitrary probability distribution. Since most devices generally work on periodic duty in TSN, the statistical distribution of the attributes of the tasks in the edge devices can be obtained via long-term statistics. Herein, we assume that the expected values of li,∆ and li,∗, i.e., Eli,∆ and Eli,∗, and their second moment, Eli,∆2 and Eli,∗2, are available.Each task generated in an edge device has two choices: local computing or remote computing in one of the ECSs. We discuss the two cases of the local computing and the remote computing approaches here.


### 3.1. Local Computing

The local computing task stream is composed of an unloadable task substream and a loadable local computing task substream; the arrival rates of these substreams are given byλi,∆ and λi,0, respectively. Let Ci,0 denote the tasks’ local computing time in Di; then, the average time for local computing is as follows:(1)ECi,0=λi,∆λi,∆+λi,0⋅Eli,∆×ρif^i+λi,0λi,∆+λi,0⋅Eli,∗×ρif^i.The second moment ofCi,0 can be obtained as follows:(2)ECi,02=λi,∆λi,∆+λi,0⋅Eli,∆2×ρi2f^i2+λi,0λi,∆+λi,0⋅Eli,∗2×ρi2f^i2.Furthermore, according to the Pollaczek–Khintchine formula [31], the average waiting time in the queue is given by the following expression:(3)W¯i,0=λi,∆+λi,0ECi,0221−λi,∆+λi,0ECi,0,s.t1>λi,∆+λi,0ECi,0,and the average response time for all local computing tasks on Di is as follows:(4)T¯i,0=W¯i,0+ECi,0=ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗+ρiλi,∆Eli,∆+λi,0Eli,∗f^iλi,∆+λi,0.If all tasks are executed locally, i.e.,λi,0=λi−λi,∆, the average response time for all tasks in Di is as follows:(5)T¯i,0l=ρi2λi,∆Eli,∆2−Eli,∗2+λiEli,∗22f^i2−2f^iρiλi,∆Eli,∆−Eli,∗+λiEli,∗+ρiλi,∆Eli,∆−Eli,∗+λiEli,∗f^iλi.


### 3.2. Remote Computing in ECS

In the scenario of task remote computing, a task generated on one edge device is delivered to an ECS using TSN. To simplify the model, we assume that the tasks generated on edge devices only pass one TSN switch to reach various ECSs and the whole TSN network is consistent with the IEEE 802.1Qbv standard. As shown in Figure1, each TSN device injects into the TSN data stream from the relevant ingress port of the TSN switch. Then, the switching fabric of the switch redirects the data stream to the proper output port according to the TSN data frame destination. To provide latency and jitter guarantees, before being transported to a specific output port that is connected to En, the TSN stream must pass through a priority filter and be reshaped in eight priority queues, Q0,n,Q1,n,Q2,n,…,Q7,n, and be finally ejected out from egress port according to the frame priority and GCL state without conflict; this process is known as the time aware shaper (TAS) mechanism. In the computing tasks offloading scenario, the hybrid stream composed of task offloading substreams and original TSN substreams is transmitted over the network. In IEEE802.1Q stand, the stream type and priority are defined in Table 2. To reduce the impact on original TSN data transmission, we set the priority of all the task offloading substreams to be p (e.g., p=2, excellent effort traffic), i.e., all the task offloading streams to En get into the queue Qp,n, for all 0≤p≤7, 1≤n≤N.Table 2
IEEE 802.1Q data stream priority [32].
PriorityAcronymStream type0BEBest effort1BEBackground2EEExcellent effort3CACritical applications4VI“Video,” <100 ms latency and jitter5VO“Voice,” <10 ms latency and jitter6ICInternetwork control7NCNetwork controlFirst, we ignore the priority queue delivery interruption caused by TAS. Herein, we have three assumptions. First, we assume that before the task offloading substreams were generated, the queueQp,n was in agreement with the M/G/1 queue model. Second, we assume that the original TSN substream of priority p, whose empress port is the same as the task offloading substreams to En, arrives according to a Poisson process with a rate of λ˜p,n, and the length of each package (composed of many TSN frames) is gp,n following a general distribution. Third, we assume that Egp,n and Egp,n2 are available, and we set the TSN switch egress port sending speed as v. Thus, the service time, Ω0,n, of the original TSN substream in Qp,n is an i.i.d random variable with mean EΩ0,n=Egp,n/v and second moment EΩ0,n2=Egp,n2/v2. When the task offloading stream from edge device Di to En arrives at queue Qp,n, it is considered as a single Poisson substream with arrival rate λi,n. Its service time Ωi,n is also an i.i.d. random variable with mean EΩi,n=Eli,∗/v and second moment EΩi,n2=Eli,∗2/v2. The compound stream, composed of the original TSN data Poisson substream and the task offloading Poisson substreams from all devices to En, is still a Poisson stream, whose arrival rate is λ˜p,n+∑i=1Mλi,n. Let the service time of each substream in queue Qp,n be denoted by Ω0,n,Ω1,n,⋯,ΩM,n; then, the whole service time Ω∗,n of the compound stream is an i.i.d. random variable with mean(6)EΩ∗,n=λ˜p,nEΩ0,nλ˜p,n+∑i=1Mλi,n+∑i=1Mλi,nΩi,nλ˜p,n+∑i=1Mλi,n=λ˜p,nEgp,n+∑i=1Mλi,nEli,∗vλ˜p,n+∑i=1Mλi,n,and second moment(7)EΩ∗,n2=λ˜p,nEΩ0,n2λ˜p,n+∑i=1Mλi,n+∑i=1Mλi,nEΩi,n2λ˜p,n+∑i=1Mλi,n=λ˜p,nEgp,n2+∑i=1Mλi,nEli,∗2v2λ˜p,n+∑i=1Mλi,nAccording to the standard IEEE802.1Qbv, the transmission of queueQp,n may be interrupted, i.e., queue service breakdown may occur, due to the GLC state or higher priority queue transmission requirements. We assume that the queue system of Qp,n remains in a stable state before the task offloading substreams reach the switch and that the transmission server breaks down at an exponential rate αn, i.e., the probability that the queue will be able to serve for an additional time t without breaking down is e−αnt. After the transmission server breaks down, the queue system stops sending data for a random time denoted as hn with a general distribution; subsequently, the server goes on from the point at which it broke down. We assume that based on long-term statistics of the stable original TSN stream queue system, the mean time Ehn and the second moment Ehn2 are known. When the task offloading streams arrive at Qp,n, as the GCL and higher priority queues are unchanged and only the customer arrival rate increases in Qp,n, we suppose that the server of queue Qp,n still breaks down at the exponential rate αn, and the pause time still follows the previous general distribution.Here, we discuss the average time a customer spends in queueQp,n with server breaking down. Let H denote the random variable “cost time” that includes service and pause time of server breaking down, k denotes the number of times the server breaks down, and hn1,hn2,…,hnk denote the amount of time the server waits for in each breakdown period. Then, it can be found that(8)H=∑i=1khni+Ω∗,n.According to the Pollaczek–Khintchine formula [31], the average waiting time before a customer begins to be served is calculated as follows:(9)W¯∗,n=λpEH221−λpEH.To obtainEH and EH2, we assume that a customer in Qp,n requires service time s′; thus, we can obtain the following expressions:(10)EH|Ω∗,n=s′=E∑i=1khni|Ω∗,n=s′+s′,(11)VarH|Ω∗,n=s′=Var∑i=1khni|Ω∗,n=s′.As the number of times the server was interrupted while a customer is in service is a Poisson random variable with meanαns′, the sum ∑i=1khni is also a compound Poisson variable with mean αns′, when Ω∗,n=s′. Consequently, it can be seen that(12)E∑i=1khni|Ω∗,n=s′=αns′Ehn,(13)Var∑i=1khni|Ω∗,n=s′=αns′Ehn2.Using equations (9)–(13), it can be found that(14)EH|Ω∗,n=αnΩ∗,nEhn+Ω∗,n,(15)VarH|Ω∗,n=αnΩ∗,nEhn2.Furthermore, we see that(16)EH=EEH|Ω∗,n=EΩ∗,n1+αnEhn,(17)VarH=EVarH|Ω∗,n+VarEH|Ω∗,n=αnEΩ∗,nEhn2+1+αnEhn2VarΩ∗,n.The second moment can then be obtained as follows:(18)EH2=VarH+EH2=αnEhn2EΩ∗,n+EΩ∗,n21+αnEhn2.Finally, substituting equations (16) and (18) into equation (9) and assuming that the inequality 1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn is satisfied, the average waiting time can be written as follows:(19)W¯∗,n=λ˜p,n+∑i=1Mλi,nαnEhn2EΩ∗,n+EΩ∗,n21+αnEhn221−λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn,s.t.1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn.Thus, the average time that the members of the hybrid stream spend in queueQp,n is calculated as follows:(20)Q¯∗,n=W¯∗,n+EH=W¯∗,n+EΩ∗,n1+αnEhn.Suppose that when task offloading streams reach theEn, En immediately provides parallel computing services, which offer CPU resources with frequency fn for each offloaded task. To guarantee that the offloading computing service requirement is beyond the maximum capacity of En, the parameter Λn is used to denote the available maximum offloading task arrival rate from all edge devices to En, i.e., ∑i=1Mλi,n≤Λn. In En, the average computation time for offloaded tasks from Di is C¯i,n=Eli,∗×ρi/fn. Considering that the data transmission speed on the TSN wire is fast (e.g., 1000 Mbps) and the offloaded task computation result’s volume is typically small (maybe a few bytes), the time of computation result delivering back can be neglected. Moreover, the time for the task offloading stream in the switch is mostly spent in Qp,n, then the average remote computing time for all tasks offloaded from edge device Di to En can be written as follows:(21)T¯i,n=Q¯∗,n+C¯i,n.Finally, the average response time for all the tasks generated in edge deviceDi can be obtained as follows:(22)T¯i=λi,∆+λi,0λiT¯i,0+∑j=1Nλi,jλiT¯i,j.


## 3.1. Local Computing

The local computing task stream is composed of an unloadable task substream and a loadable local computing task substream; the arrival rates of these substreams are given byλi,∆ and λi,0, respectively. Let Ci,0 denote the tasks’ local computing time in Di; then, the average time for local computing is as follows:(1)ECi,0=λi,∆λi,∆+λi,0⋅Eli,∆×ρif^i+λi,0λi,∆+λi,0⋅Eli,∗×ρif^i.The second moment ofCi,0 can be obtained as follows:(2)ECi,02=λi,∆λi,∆+λi,0⋅Eli,∆2×ρi2f^i2+λi,0λi,∆+λi,0⋅Eli,∗2×ρi2f^i2.Furthermore, according to the Pollaczek–Khintchine formula [31], the average waiting time in the queue is given by the following expression:(3)W¯i,0=λi,∆+λi,0ECi,0221−λi,∆+λi,0ECi,0,s.t1>λi,∆+λi,0ECi,0,and the average response time for all local computing tasks on Di is as follows:(4)T¯i,0=W¯i,0+ECi,0=ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗+ρiλi,∆Eli,∆+λi,0Eli,∗f^iλi,∆+λi,0.If all tasks are executed locally, i.e.,λi,0=λi−λi,∆, the average response time for all tasks in Di is as follows:(5)T¯i,0l=ρi2λi,∆Eli,∆2−Eli,∗2+λiEli,∗22f^i2−2f^iρiλi,∆Eli,∆−Eli,∗+λiEli,∗+ρiλi,∆Eli,∆−Eli,∗+λiEli,∗f^iλi.


## 3.2. Remote Computing in ECS

In the scenario of task remote computing, a task generated on one edge device is delivered to an ECS using TSN. To simplify the model, we assume that the tasks generated on edge devices only pass one TSN switch to reach various ECSs and the whole TSN network is consistent with the IEEE 802.1Qbv standard. As shown in Figure1, each TSN device injects into the TSN data stream from the relevant ingress port of the TSN switch. Then, the switching fabric of the switch redirects the data stream to the proper output port according to the TSN data frame destination. To provide latency and jitter guarantees, before being transported to a specific output port that is connected to En, the TSN stream must pass through a priority filter and be reshaped in eight priority queues, Q0,n,Q1,n,Q2,n,…,Q7,n, and be finally ejected out from egress port according to the frame priority and GCL state without conflict; this process is known as the time aware shaper (TAS) mechanism. In the computing tasks offloading scenario, the hybrid stream composed of task offloading substreams and original TSN substreams is transmitted over the network. In IEEE802.1Q stand, the stream type and priority are defined in Table 2. To reduce the impact on original TSN data transmission, we set the priority of all the task offloading substreams to be p (e.g., p=2, excellent effort traffic), i.e., all the task offloading streams to En get into the queue Qp,n, for all 0≤p≤7, 1≤n≤N.Table 2
IEEE 802.1Q data stream priority [32].
PriorityAcronymStream type0BEBest effort1BEBackground2EEExcellent effort3CACritical applications4VI“Video,” <100 ms latency and jitter5VO“Voice,” <10 ms latency and jitter6ICInternetwork control7NCNetwork controlFirst, we ignore the priority queue delivery interruption caused by TAS. Herein, we have three assumptions. First, we assume that before the task offloading substreams were generated, the queueQp,n was in agreement with the M/G/1 queue model. Second, we assume that the original TSN substream of priority p, whose empress port is the same as the task offloading substreams to En, arrives according to a Poisson process with a rate of λ˜p,n, and the length of each package (composed of many TSN frames) is gp,n following a general distribution. Third, we assume that Egp,n and Egp,n2 are available, and we set the TSN switch egress port sending speed as v. Thus, the service time, Ω0,n, of the original TSN substream in Qp,n is an i.i.d random variable with mean EΩ0,n=Egp,n/v and second moment EΩ0,n2=Egp,n2/v2. When the task offloading stream from edge device Di to En arrives at queue Qp,n, it is considered as a single Poisson substream with arrival rate λi,n. Its service time Ωi,n is also an i.i.d. random variable with mean EΩi,n=Eli,∗/v and second moment EΩi,n2=Eli,∗2/v2. The compound stream, composed of the original TSN data Poisson substream and the task offloading Poisson substreams from all devices to En, is still a Poisson stream, whose arrival rate is λ˜p,n+∑i=1Mλi,n. Let the service time of each substream in queue Qp,n be denoted by Ω0,n,Ω1,n,⋯,ΩM,n; then, the whole service time Ω∗,n of the compound stream is an i.i.d. random variable with mean(6)EΩ∗,n=λ˜p,nEΩ0,nλ˜p,n+∑i=1Mλi,n+∑i=1Mλi,nΩi,nλ˜p,n+∑i=1Mλi,n=λ˜p,nEgp,n+∑i=1Mλi,nEli,∗vλ˜p,n+∑i=1Mλi,n,and second moment(7)EΩ∗,n2=λ˜p,nEΩ0,n2λ˜p,n+∑i=1Mλi,n+∑i=1Mλi,nEΩi,n2λ˜p,n+∑i=1Mλi,n=λ˜p,nEgp,n2+∑i=1Mλi,nEli,∗2v2λ˜p,n+∑i=1Mλi,nAccording to the standard IEEE802.1Qbv, the transmission of queueQp,n may be interrupted, i.e., queue service breakdown may occur, due to the GLC state or higher priority queue transmission requirements. We assume that the queue system of Qp,n remains in a stable state before the task offloading substreams reach the switch and that the transmission server breaks down at an exponential rate αn, i.e., the probability that the queue will be able to serve for an additional time t without breaking down is e−αnt. After the transmission server breaks down, the queue system stops sending data for a random time denoted as hn with a general distribution; subsequently, the server goes on from the point at which it broke down. We assume that based on long-term statistics of the stable original TSN stream queue system, the mean time Ehn and the second moment Ehn2 are known. When the task offloading streams arrive at Qp,n, as the GCL and higher priority queues are unchanged and only the customer arrival rate increases in Qp,n, we suppose that the server of queue Qp,n still breaks down at the exponential rate αn, and the pause time still follows the previous general distribution.Here, we discuss the average time a customer spends in queueQp,n with server breaking down. Let H denote the random variable “cost time” that includes service and pause time of server breaking down, k denotes the number of times the server breaks down, and hn1,hn2,…,hnk denote the amount of time the server waits for in each breakdown period. Then, it can be found that(8)H=∑i=1khni+Ω∗,n.According to the Pollaczek–Khintchine formula [31], the average waiting time before a customer begins to be served is calculated as follows:(9)W¯∗,n=λpEH221−λpEH.To obtainEH and EH2, we assume that a customer in Qp,n requires service time s′; thus, we can obtain the following expressions:(10)EH|Ω∗,n=s′=E∑i=1khni|Ω∗,n=s′+s′,(11)VarH|Ω∗,n=s′=Var∑i=1khni|Ω∗,n=s′.As the number of times the server was interrupted while a customer is in service is a Poisson random variable with meanαns′, the sum ∑i=1khni is also a compound Poisson variable with mean αns′, when Ω∗,n=s′. Consequently, it can be seen that(12)E∑i=1khni|Ω∗,n=s′=αns′Ehn,(13)Var∑i=1khni|Ω∗,n=s′=αns′Ehn2.Using equations (9)–(13), it can be found that(14)EH|Ω∗,n=αnΩ∗,nEhn+Ω∗,n,(15)VarH|Ω∗,n=αnΩ∗,nEhn2.Furthermore, we see that(16)EH=EEH|Ω∗,n=EΩ∗,n1+αnEhn,(17)VarH=EVarH|Ω∗,n+VarEH|Ω∗,n=αnEΩ∗,nEhn2+1+αnEhn2VarΩ∗,n.The second moment can then be obtained as follows:(18)EH2=VarH+EH2=αnEhn2EΩ∗,n+EΩ∗,n21+αnEhn2.Finally, substituting equations (16) and (18) into equation (9) and assuming that the inequality 1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn is satisfied, the average waiting time can be written as follows:(19)W¯∗,n=λ˜p,n+∑i=1Mλi,nαnEhn2EΩ∗,n+EΩ∗,n21+αnEhn221−λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn,s.t.1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn.Thus, the average time that the members of the hybrid stream spend in queueQp,n is calculated as follows:(20)Q¯∗,n=W¯∗,n+EH=W¯∗,n+EΩ∗,n1+αnEhn.Suppose that when task offloading streams reach theEn, En immediately provides parallel computing services, which offer CPU resources with frequency fn for each offloaded task. To guarantee that the offloading computing service requirement is beyond the maximum capacity of En, the parameter Λn is used to denote the available maximum offloading task arrival rate from all edge devices to En, i.e., ∑i=1Mλi,n≤Λn. In En, the average computation time for offloaded tasks from Di is C¯i,n=Eli,∗×ρi/fn. Considering that the data transmission speed on the TSN wire is fast (e.g., 1000 Mbps) and the offloaded task computation result’s volume is typically small (maybe a few bytes), the time of computation result delivering back can be neglected. Moreover, the time for the task offloading stream in the switch is mostly spent in Qp,n, then the average remote computing time for all tasks offloaded from edge device Di to En can be written as follows:(21)T¯i,n=Q¯∗,n+C¯i,n.Finally, the average response time for all the tasks generated in edge deviceDi can be obtained as follows:(22)T¯i=λi,∆+λi,0λiT¯i,0+∑j=1Nλi,jλiT¯i,j.


## 4. Problem Formulation and Algorithm

### 4.1. Game Formulation

In the TSN computation offloading scenario, each edge device is independent and selfish with the aim of utilizing the maximum ECS computing resources possible to reduce its own response time; this represents a suitable situation for game theory to be used to model the competition process among all edge devices. Considering the edge device setM=D1,D2,…,DM as the game players, the arrival rate allocation policy set Si=λi,0,λi,1,…,λi,N∈RN+1 as the strategies of player Di (where λi=λi,∆+λi,0+λi,1+…+λi,N), and the Cartesian products of all individual strategy set, i.e., S=S1×S2×…×SM, as the strategy space, we give the multitask offloading game as follows:Definition 1.
Multitask offloading game: the multitask offloading game,G, which is composed of the player set M, the offloading strategy space S, and the utility function set Ui,∀i∈M, is represented as follows:(23)G=M,S,Uii∈M.
We expect that within limited rounds of decision-making, the players can reach a certain consensus, i.e., each player benefits most in that state. Thus, we now introduce Nash Equilibrium as follows:Definition 2.
Nash equilibrium [33]: the strategy profile Si∗i∈M is a Nash equilibrium of multitask offloading game G if and only if(24)UiSi∗,S−i≤UiSi′,S−i,∀Si′∈Si,where S−i is the offloading strategies of computing devices except Di. That means there is no more optimal strategy than Si∗ to get more benefit based on the utility function. The challenge in fully defining the game formulation (equation (23)) is to find an appropriate utility function, which allows all players to maximize the benefits from their own perspectives and achieve Nash equilibrium. Here, we adopt the exact potential game theory as defined below to design the utility function.Definition 3.
Exact potential game [34]: the multitask offloading game, G, is an exact potential game if and only if there exists a potential function FS:S⟶R that satisfies(25)Uisi,s−i−Uisi′,s−i=Fsi,s−i−Fsi′,s−i,∀si,si′∈Si;∀s−i∈S−i;∀i∈M.
As the existence of Nash equilibrium is a fundamental property of exact potential games, we construct a potential function,F and a utility function, Ui, to ensure that the multitask offloading game, G, is an exact potential game using the backward method [34]. We let FS denote the whole system benefits that can be achieved via task offloading computing rather than the situation in which all tasks are locally executed. FS can be represented in computation time, as the greater benefit is equated with a lesser time cost. Thus, we see that.(26)FS=∑k=1MT¯k,0l−∑k=1Mλk,∆+λk,0T¯k,0λk−∑k=1M∑j=1Nλk,jT¯k,jλk.
Subsequently, considering equations (1)–(22), a decomposition can be obtained as follows:(27)FSi,S−i=∑k=1MT¯k,0l−λi,∆+λi,0T¯i,0λi−∑k=1,k≠iMλk,∆+λk,0T¯k,0λk−∑k=1M∑j=1Nλk,jQ¯∗,jλk−∑j=1Nλk,jQ¯∗,jλk−∑k=1,k≠iM∑j=1Nλk,jC¯i,jλk=−λi,∆+λi,0λi∙ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗−ρiλi,∆Eli,∆+λi,0Eli,∗λif^i−∑k=1M∑j=1Nλk,jλkW¯∗,j+EΩ∗,j1+αjEhj−∑j=1Nλi,jEli,∗ρiλifj+∑k=1MT¯k,0l−∑k=1,k≠iM∑j=1Nλk,jElk,∗ρkλkfj−∑k=1,k≠iMλk,∆+λk,0T¯k,0λk⏟Non−contributingtermϕiS−i.
Then, we can obtain the utility function of the potential game withUiSi,S−i=FSi,S−i−ϕiS−i, where ϕiS−i is a noncontributing term from the perspective of player Di. Thus, the utility function of the exact potential game G is given as follows:(28)UiSi,S−i=−λi,∆+λi,0λi∙ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗−ρiλi,∆Eli,∆+λi,0Eli,∗λif^i−∑k=1M∑j=1Nλk,jλkW¯∗,j+EΩ∗,j1+αjEhj−∑j=1Nλi,jEli,∗ρiλifj.


### 4.2. The Algorithm

Based on the utility functionUi, the best response strategy of each edge device is described.Definition 4.
Best response strategy: letS−i represent the strategies of all the edge devices except device Di, the best response strategy of Di is given by(29a)Si∗=argmaxSiUiSi,S−i,(29b)λi,∆+∑j=0Nλi,j=λi,(29c)∑k=1Mλk,j≤Λj,(29d)1>λi,∆+λi,0ECi,0,(29e)1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn.
Equation (29a) represents the choice of Di to pursue minimal time cost. The constraint equation (29b) guarantees that the decision of the task arrival rate allocation meets the total arrival rate requirement for each edge device. The constraint equation (29c) ensures that the workload of ECSs providing remote computing services is not beyond the upper limit of its capacity. Equations (29d) and (29e) guarantee that the queuing system is in a serviceable state.
According to the aforementioned system model and game formulation, the distributed and sequential decision-making algorithm for multi-task offloading (DSDA-MO) was designed. A summary of this algorithm is given in Algorithm 1. After the strategies of each edge device are initialized, a token is passed among edge devices, and the device in possession of the token calculates its best response strategy based on all the decisions of the other devices. The algorithm runs (line 3–8) until theMSES∗R,S∗R−1, the mean square error between the strategy of the current round and the strategy of the previous round, is less than accuracy parameter ξ (e.g., ξ=10−10). MSES∗R,S∗R−1 is defined as follows:(30)MSES∗R,S∗R−1=∑i=1M∑j=1Nλi,j∗Ri−λi,j∗Ri−12M.
In each round of Algorithm 1, the equations (29a)–(29e). Problem could been solved via the Lagrange multiplier method with the algorithm of iterative search in feasible region, and the complexity is OMNlog1/δ2, where δ is the search interval. Thus, the complexity of Algorithm 1 is ORMNlog1/δ2, where R is the number of rounds mainly determined by the accuracy parameter ξ in line 9.Algorithm 1:Distributed and sequential decision-making algorithm for multitask offloading (DSDA-MO).
Input:λi, λi,∆, ρi, Eli,∆, Eli,∆2, Eli,∗, Eli,∗2, Ehj, Ehj2, λ˜p,j, fi, Egp,j, Egp,j2,αj, λ˜p,j, Λj, v and f^j, for all 1≤i≤Mand1≤j≤N(1)
Initialization:Si∗0=λi,0∗0,λi,1∗0,…,λi,N∗0 and Ri←0 for all 1≤i≤M, and give the token to first edge device D1.(2)
Repeat:(3)
PlayerDi waits for the token(4)
PlayerDi collects and updates all the other edge devices’ decisions, S−i∗(5)
Ri←Ri+1(6)
PlayerDi calculates the best response strategySi∗Ri←argmaxUiSi,S−i,Subject to (29b)–(29e)(7)
PlayerDi broadcasts Si∗ to all the other edge devices(8)
PlayerDi sends the token to the next node(9)
UntilMSES∗R,S∗R−1<ξ(10)
Output:S∗←S1∗R1,S2∗R2,…,SN∗RN


## 4.1. Game Formulation

In the TSN computation offloading scenario, each edge device is independent and selfish with the aim of utilizing the maximum ECS computing resources possible to reduce its own response time; this represents a suitable situation for game theory to be used to model the competition process among all edge devices. Considering the edge device setM=D1,D2,…,DM as the game players, the arrival rate allocation policy set Si=λi,0,λi,1,…,λi,N∈RN+1 as the strategies of player Di (where λi=λi,∆+λi,0+λi,1+…+λi,N), and the Cartesian products of all individual strategy set, i.e., S=S1×S2×…×SM, as the strategy space, we give the multitask offloading game as follows:Definition 1.
Multitask offloading game: the multitask offloading game,G, which is composed of the player set M, the offloading strategy space S, and the utility function set Ui,∀i∈M, is represented as follows:(23)G=M,S,Uii∈M.
We expect that within limited rounds of decision-making, the players can reach a certain consensus, i.e., each player benefits most in that state. Thus, we now introduce Nash Equilibrium as follows:Definition 2.
Nash equilibrium [33]: the strategy profile Si∗i∈M is a Nash equilibrium of multitask offloading game G if and only if(24)UiSi∗,S−i≤UiSi′,S−i,∀Si′∈Si,where S−i is the offloading strategies of computing devices except Di. That means there is no more optimal strategy than Si∗ to get more benefit based on the utility function. The challenge in fully defining the game formulation (equation (23)) is to find an appropriate utility function, which allows all players to maximize the benefits from their own perspectives and achieve Nash equilibrium. Here, we adopt the exact potential game theory as defined below to design the utility function.Definition 3.
Exact potential game [34]: the multitask offloading game, G, is an exact potential game if and only if there exists a potential function FS:S⟶R that satisfies(25)Uisi,s−i−Uisi′,s−i=Fsi,s−i−Fsi′,s−i,∀si,si′∈Si;∀s−i∈S−i;∀i∈M.
As the existence of Nash equilibrium is a fundamental property of exact potential games, we construct a potential function,F and a utility function, Ui, to ensure that the multitask offloading game, G, is an exact potential game using the backward method [34]. We let FS denote the whole system benefits that can be achieved via task offloading computing rather than the situation in which all tasks are locally executed. FS can be represented in computation time, as the greater benefit is equated with a lesser time cost. Thus, we see that.(26)FS=∑k=1MT¯k,0l−∑k=1Mλk,∆+λk,0T¯k,0λk−∑k=1M∑j=1Nλk,jT¯k,jλk.
Subsequently, considering equations (1)–(22), a decomposition can be obtained as follows:(27)FSi,S−i=∑k=1MT¯k,0l−λi,∆+λi,0T¯i,0λi−∑k=1,k≠iMλk,∆+λk,0T¯k,0λk−∑k=1M∑j=1Nλk,jQ¯∗,jλk−∑j=1Nλk,jQ¯∗,jλk−∑k=1,k≠iM∑j=1Nλk,jC¯i,jλk=−λi,∆+λi,0λi∙ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗−ρiλi,∆Eli,∆+λi,0Eli,∗λif^i−∑k=1M∑j=1Nλk,jλkW¯∗,j+EΩ∗,j1+αjEhj−∑j=1Nλi,jEli,∗ρiλifj+∑k=1MT¯k,0l−∑k=1,k≠iM∑j=1Nλk,jElk,∗ρkλkfj−∑k=1,k≠iMλk,∆+λk,0T¯k,0λk⏟Non−contributingtermϕiS−i.
Then, we can obtain the utility function of the potential game withUiSi,S−i=FSi,S−i−ϕiS−i, where ϕiS−i is a noncontributing term from the perspective of player Di. Thus, the utility function of the exact potential game G is given as follows:(28)UiSi,S−i=−λi,∆+λi,0λi∙ρi2λi,∆Eli,∆2+λi,0Eli,∗22f^i2−2f^iρiλi,∆Eli,∆+λi,0Eli,∗−ρiλi,∆Eli,∆+λi,0Eli,∗λif^i−∑k=1M∑j=1Nλk,jλkW¯∗,j+EΩ∗,j1+αjEhj−∑j=1Nλi,jEli,∗ρiλifj.


## 4.2. The Algorithm

Based on the utility functionUi, the best response strategy of each edge device is described.Definition 4.
Best response strategy: letS−i represent the strategies of all the edge devices except device Di, the best response strategy of Di is given by(29a)Si∗=argmaxSiUiSi,S−i,(29b)λi,∆+∑j=0Nλi,j=λi,(29c)∑k=1Mλk,j≤Λj,(29d)1>λi,∆+λi,0ECi,0,(29e)1>λ˜p,n+∑i=1Mλi,nEΩ∗,n1+αnEhn.
Equation (29a) represents the choice of Di to pursue minimal time cost. The constraint equation (29b) guarantees that the decision of the task arrival rate allocation meets the total arrival rate requirement for each edge device. The constraint equation (29c) ensures that the workload of ECSs providing remote computing services is not beyond the upper limit of its capacity. Equations (29d) and (29e) guarantee that the queuing system is in a serviceable state.
According to the aforementioned system model and game formulation, the distributed and sequential decision-making algorithm for multi-task offloading (DSDA-MO) was designed. A summary of this algorithm is given in Algorithm 1. After the strategies of each edge device are initialized, a token is passed among edge devices, and the device in possession of the token calculates its best response strategy based on all the decisions of the other devices. The algorithm runs (line 3–8) until theMSES∗R,S∗R−1, the mean square error between the strategy of the current round and the strategy of the previous round, is less than accuracy parameter ξ (e.g., ξ=10−10). MSES∗R,S∗R−1 is defined as follows:(30)MSES∗R,S∗R−1=∑i=1M∑j=1Nλi,j∗Ri−λi,j∗Ri−12M.
In each round of Algorithm 1, the equations (29a)–(29e). Problem could been solved via the Lagrange multiplier method with the algorithm of iterative search in feasible region, and the complexity is OMNlog1/δ2, where δ is the search interval. Thus, the complexity of Algorithm 1 is ORMNlog1/δ2, where R is the number of rounds mainly determined by the accuracy parameter ξ in line 9.Algorithm 1:Distributed and sequential decision-making algorithm for multitask offloading (DSDA-MO).
Input:λi, λi,∆, ρi, Eli,∆, Eli,∆2, Eli,∗, Eli,∗2, Ehj, Ehj2, λ˜p,j, fi, Egp,j, Egp,j2,αj, λ˜p,j, Λj, v and f^j, for all 1≤i≤Mand1≤j≤N(1)
Initialization:Si∗0=λi,0∗0,λi,1∗0,…,λi,N∗0 and Ri←0 for all 1≤i≤M, and give the token to first edge device D1.(2)
Repeat:(3)
PlayerDi waits for the token(4)
PlayerDi collects and updates all the other edge devices’ decisions, S−i∗(5)
Ri←Ri+1(6)
PlayerDi calculates the best response strategySi∗Ri←argmaxUiSi,S−i,Subject to (29b)–(29e)(7)
PlayerDi broadcasts Si∗ to all the other edge devices(8)
PlayerDi sends the token to the next node(9)
UntilMSES∗R,S∗R−1<ξ(10)
Output:S∗←S1∗R1,S2∗R2,…,SN∗RN


## 5. Numerical Results

In this section, the results of numerical experiments are reported to evaluate the proposed system model and the DSDA-MO algorithm. In the simulation setup, we considerM edge devices (D1,D2,…,Di, i = 1, 2, …, M) and N ECSs (E1, E2,…,Ej,j = 1,2, …, N) with the following parameters: λi=3.4+0.1i−1, λi,∆=0.5+0.05i−1, Eli,∆=5+i−1Mbit, Eli,∆2=1.5Eli,∆2, Eli,∗=100+i−1Mbit, Eli,∗2=1.6Eli,∗2, ρi=1+0.1i−1BI/Mbit, Egp,j=40+0.5j−1Mbit, Egp,j2=1.3Egp,j2, Ehj=0.01+0.001j−1s, Ehj2=1.1Ehj2, αj=0.03+0.001j−1, λ˜p,j=1.2+0.1j−1, Λj=7+0.5j−1, f^i= 0.8 + 0.1(i − 1) GHz, fj=3.2+0.2j−1 GHz, and v=1000Mbps, for all 1≤i≤M, 1≤j≤N. The simulation is constructed on MATLAB platform.


### 5.1. Nash Equilibrium of the Game

First, we setM = 6, N = 5 to evaluate the results of Nash equilibrium, i.e., the final optimal strategy Si∗=λi,0∗,λi,1∗,…,λi,N∗ for 1≤i≤M. Figure 2 shows the curves describing the utility of the edge devices D1,…,D6 found at each round of the DSDA-MO algorithm. It seems that the utilities fluctuate wildly in the initial rounds of calculations and then enter a stable zone with low variation. Figure 2 shows the average time cost at each round, and it illustrates that the average time cost of each device remains near a stable value after about 200 rounds. The results in Figures 2 and 3 verify that the game reaches the approximate Nash equilibrium after finite rounds of calculation in the proposed algorithm.Figure 2
Utility of the edge devices obtained using the proposed algorithm at each round. The curves of utility from round 50 to 80 are zoomed.Figure 3
Average time cost of the edge devices at each round.To further evaluate the speed of convergence of the Nash equilibrium, we list the strategies, i.e.,λ5,0∗R,λ5,1∗R,…,λ5,5∗R and λ6,0∗R,λ6,1∗R,…,λ6,5∗R, from 30 to 90 rounds in Tables 3 and 4, and give the curves of strategies at each round (as shown in Figure 4) by using the edge device D5 and D6 as examples. The results in Tables 3 and 4 and Figure 4 show that λi,1∗,…,λi,N∗ changes significantly in each round at the early stage until round number 200; from this point on, the optimal strategy remains in a stable state, which is consistent with the findings presented in Figures 2 and 3. As discussed earlier in Algorithm 1, the round number to get approximate Nash equilibrium mainly depends on the accuracy parameter ξ. Table 5 presents the relationship between the round number and the value of ξ, listed as 10−1,10−2,…,10−10. It shows that the round number increases with the improvement of the accuracy requirement. That is to say, a smaller value of ξ leads to a greater round number. We can select the appropriate parameters according to the application demand with the appropriate balance between the Nash equilibrium accuracy and the algorithm running time.Table 3
Convergence of the Nash equilibrium in exampleD5.
Roundλ5,0∗λ5,1∗λ5,2∗λ5,3∗λ5,4∗λ5,5∗302.98131210.13482700.15255760.16655720.17780810.1869380402.96815890.12893640.15172910.16987350.18461370.1966883502.96221630.12129200.14934410.17178680.19013340.2052274602.96234490.11221180.14567370.17253370.19454400.2126918702.96288870.10296200.14191340.17325440.19890310.2200784802.96415920.09361930.13809220.17393390.20314230.2270532902.96425540.08471290.13468020.17498010.20761040.2337610Table 4
Convergence of the Nash equilibrium in exampleD6.
Roundλ6,0∗λ6,1∗λ6,2∗λ6,3∗λ6,4∗λ6,5∗302.96835380.1650650.1782110.1885030.1966660.2032013402.96524010.1579010.1756360.1897420.2011140.2103667502.95988250.1509560.1734300.1914590.2061210.2181514602.95914860.1427970.1701890.1922850.2103420.2252379702.95948290.1341830.1666480.1929320.2144630.2322909802.96058330.1251980.1628840.1934620.2185400.2393330902.96083940.1162030.1592370.1942030.2228820.2466355Figure 4
Optimal strategy of the arrival rate obtained by using the proposed algorithm at each round: edge deviceD5 and D6 as examples. (a) Edge device D5 and (b) edge device D6.
(a)(b)Table 5
Round number with the value of accuracy parameterξ.
Accuracy parameterξRound number10−1310−21210−32110−43510−56410−612710−717710−822010−928910−10327


### 5.2. Benefit of the Game

In this subsection, we focus on analyzing the benefit that edge devices obtain from the proposed game. Let accuracy parameterξ=10−8; after 220 rounds of calculation in Algorithm 1, we obtain the final optimal strategy profile S∗. Figure 5 presents the arrival rate of the un-offloadable tasks (known parameter), the sum of the optimal arrival rates of the tasks offloaded from Dm to all ECSs (i.e., ∑j=1Nλm,j∗, 1≤m≤M), and the optimal arrival rate of the offloadable local computing tasks (i.e., λm,0∗) in edge devices. It is found that ∑j=1Nλm,j∗ increases as the arrival rate of all tasks generated on each edge device increases with λi=3.4+0.1i−1 in our experiment settings. In other words, the amount of the offloaded tasks increases as the computation workload ascends in edge devices. Figure 6 illustrates the average time with the decision of all locally-computed tasks versus the average time with optimal strategy profile S∗ obtained by Algorithm 1. Compared with the method of all tasks computing locally, our proposed algorithm brings significant time-saving advantages for each device, where D6 obtains 13.03% decrement in time cost.Figure 5
Optimal strategies of the task arrival rate consisting of the arrival rate of the unoffloadable tasks (known parameter), the arrival rate of the offloadable local computing tasks, and the arrival rate of the tasks offloaded to ECSs.Figure 6
Average time cost with the decision of all tasks computed locally vs. average time cost with optimal strategy profileS∗ obtained by algorithm 1.To study the profitability of the proposed approach, we define the task offloading proportionRi,n∈0,1, as(31)Ri,n=∑j=1nλi,j∗∑j=0nλi,j∗,where ∑j=1Nλi,j∗ is the sum of the arrival rates of the tasks offloaded to E1,E2,…,EN from Di, and ∑j=0Nλi,j∗ is the sum of the arrival rates of all offloadable tasks on Di. The larger Ri,n means more benefits obtained from task offloading for Di. Figure 7 illustrates that the task offloading proportions of D1,D2,…,D6 increase in order as their computation workload increases accordingly, and the task offloading proportion increment of D6 reaches more than 25%.Figure 7
Task offloading proportion of each edge device.We also study the workload of the edge computing servers in the game. Figure8 illustrates the final amount of the workload in the target ECS set N, i.e., E1,E2,...,EN, and the final decision that how many tasks on each edge device will choose each ECS. The decision is indicated by the arrival rate λ^j from all edge devices to Ej,1≤j≤N. From Figure 8, we can see that although the processing frequencies of the members of set N increase successively in our experiment settings, the sum of the task arrival rates from the edge devices to ECSs, i.e., λ^1,λ^2,…,λ^N, descends gradually. In other words, ECSs gradually lost their attraction to the tasks offloaded from edge devices as the processing frequency increases successively. This is because each offloaded task needs to consider both the computation time and the transmission time and makes a decision based on the sum of them. Although high processing frequency of the target ECS leads to low computation time for the offloaded task, the sum of the task arrival rates may also be small due to a possible high transmission time cost. In our experimental settings, it is assumed that the busy degree of the TSN links to E1,E2,…,EN increase successively. That is to say, the average interrupted time of the TSN output queues corresponding to each target ECS, i.e., Ehn, increases orderly. This experiment setting results in an increase in the transmission time of the same task to E1,E2,…,EN orderly. Hence, the number of the tasks selected to be offloaded to ECSs, namely, the task arrival rates to ECSs, gradually decreases in Figure 8. Especially, almost none of the edge devices here decided to offload their task to E5.Figure 8
Optimal arrival rates of the tasks to each ECS.To analyze the influence of the number of the edge devices,M, and the number of ECSs, N, on the task offloading decision-making result, we construct an experiment with M=10,15,20,25,30, N=20,25,30, and ξ=10−5. Figure 9 shows the average response time of the tasks in the edge devices with different M and N, which reflects the impact on the performance of the entire edge computing system. Obviously, the average response time of the edge computing system increases as M increases when N is fixed. Inversely, the average response time decrease as N increases when M is fixed.Figure 9
The average response time of the tasks in all edge devices with differentM and N values.


## 5.1. Nash Equilibrium of the Game

First, we setM = 6, N = 5 to evaluate the results of Nash equilibrium, i.e., the final optimal strategy Si∗=λi,0∗,λi,1∗,…,λi,N∗ for 1≤i≤M. Figure 2 shows the curves describing the utility of the edge devices D1,…,D6 found at each round of the DSDA-MO algorithm. It seems that the utilities fluctuate wildly in the initial rounds of calculations and then enter a stable zone with low variation. Figure 2 shows the average time cost at each round, and it illustrates that the average time cost of each device remains near a stable value after about 200 rounds. The results in Figures 2 and 3 verify that the game reaches the approximate Nash equilibrium after finite rounds of calculation in the proposed algorithm.Figure 2
Utility of the edge devices obtained using the proposed algorithm at each round. The curves of utility from round 50 to 80 are zoomed.Figure 3
Average time cost of the edge devices at each round.To further evaluate the speed of convergence of the Nash equilibrium, we list the strategies, i.e.,λ5,0∗R,λ5,1∗R,…,λ5,5∗R and λ6,0∗R,λ6,1∗R,…,λ6,5∗R, from 30 to 90 rounds in Tables 3 and 4, and give the curves of strategies at each round (as shown in Figure 4) by using the edge device D5 and D6 as examples. The results in Tables 3 and 4 and Figure 4 show that λi,1∗,…,λi,N∗ changes significantly in each round at the early stage until round number 200; from this point on, the optimal strategy remains in a stable state, which is consistent with the findings presented in Figures 2 and 3. As discussed earlier in Algorithm 1, the round number to get approximate Nash equilibrium mainly depends on the accuracy parameter ξ. Table 5 presents the relationship between the round number and the value of ξ, listed as 10−1,10−2,…,10−10. It shows that the round number increases with the improvement of the accuracy requirement. That is to say, a smaller value of ξ leads to a greater round number. We can select the appropriate parameters according to the application demand with the appropriate balance between the Nash equilibrium accuracy and the algorithm running time.Table 3
Convergence of the Nash equilibrium in exampleD5.
Roundλ5,0∗λ5,1∗λ5,2∗λ5,3∗λ5,4∗λ5,5∗302.98131210.13482700.15255760.16655720.17780810.1869380402.96815890.12893640.15172910.16987350.18461370.1966883502.96221630.12129200.14934410.17178680.19013340.2052274602.96234490.11221180.14567370.17253370.19454400.2126918702.96288870.10296200.14191340.17325440.19890310.2200784802.96415920.09361930.13809220.17393390.20314230.2270532902.96425540.08471290.13468020.17498010.20761040.2337610Table 4
Convergence of the Nash equilibrium in exampleD6.
Roundλ6,0∗λ6,1∗λ6,2∗λ6,3∗λ6,4∗λ6,5∗302.96835380.1650650.1782110.1885030.1966660.2032013402.96524010.1579010.1756360.1897420.2011140.2103667502.95988250.1509560.1734300.1914590.2061210.2181514602.95914860.1427970.1701890.1922850.2103420.2252379702.95948290.1341830.1666480.1929320.2144630.2322909802.96058330.1251980.1628840.1934620.2185400.2393330902.96083940.1162030.1592370.1942030.2228820.2466355Figure 4
Optimal strategy of the arrival rate obtained by using the proposed algorithm at each round: edge deviceD5 and D6 as examples. (a) Edge device D5 and (b) edge device D6.
(a)(b)Table 5
Round number with the value of accuracy parameterξ.
Accuracy parameterξRound number10−1310−21210−32110−43510−56410−612710−717710−822010−928910−10327


## 5.2. Benefit of the Game

In this subsection, we focus on analyzing the benefit that edge devices obtain from the proposed game. Let accuracy parameterξ=10−8; after 220 rounds of calculation in Algorithm 1, we obtain the final optimal strategy profile S∗. Figure 5 presents the arrival rate of the un-offloadable tasks (known parameter), the sum of the optimal arrival rates of the tasks offloaded from Dm to all ECSs (i.e., ∑j=1Nλm,j∗, 1≤m≤M), and the optimal arrival rate of the offloadable local computing tasks (i.e., λm,0∗) in edge devices. It is found that ∑j=1Nλm,j∗ increases as the arrival rate of all tasks generated on each edge device increases with λi=3.4+0.1i−1 in our experiment settings. In other words, the amount of the offloaded tasks increases as the computation workload ascends in edge devices. Figure 6 illustrates the average time with the decision of all locally-computed tasks versus the average time with optimal strategy profile S∗ obtained by Algorithm 1. Compared with the method of all tasks computing locally, our proposed algorithm brings significant time-saving advantages for each device, where D6 obtains 13.03% decrement in time cost.Figure 5
Optimal strategies of the task arrival rate consisting of the arrival rate of the unoffloadable tasks (known parameter), the arrival rate of the offloadable local computing tasks, and the arrival rate of the tasks offloaded to ECSs.Figure 6
Average time cost with the decision of all tasks computed locally vs. average time cost with optimal strategy profileS∗ obtained by algorithm 1.To study the profitability of the proposed approach, we define the task offloading proportionRi,n∈0,1, as(31)Ri,n=∑j=1nλi,j∗∑j=0nλi,j∗,where ∑j=1Nλi,j∗ is the sum of the arrival rates of the tasks offloaded to E1,E2,…,EN from Di, and ∑j=0Nλi,j∗ is the sum of the arrival rates of all offloadable tasks on Di. The larger Ri,n means more benefits obtained from task offloading for Di. Figure 7 illustrates that the task offloading proportions of D1,D2,…,D6 increase in order as their computation workload increases accordingly, and the task offloading proportion increment of D6 reaches more than 25%.Figure 7
Task offloading proportion of each edge device.We also study the workload of the edge computing servers in the game. Figure8 illustrates the final amount of the workload in the target ECS set N, i.e., E1,E2,...,EN, and the final decision that how many tasks on each edge device will choose each ECS. The decision is indicated by the arrival rate λ^j from all edge devices to Ej,1≤j≤N. From Figure 8, we can see that although the processing frequencies of the members of set N increase successively in our experiment settings, the sum of the task arrival rates from the edge devices to ECSs, i.e., λ^1,λ^2,…,λ^N, descends gradually. In other words, ECSs gradually lost their attraction to the tasks offloaded from edge devices as the processing frequency increases successively. This is because each offloaded task needs to consider both the computation time and the transmission time and makes a decision based on the sum of them. Although high processing frequency of the target ECS leads to low computation time for the offloaded task, the sum of the task arrival rates may also be small due to a possible high transmission time cost. In our experimental settings, it is assumed that the busy degree of the TSN links to E1,E2,…,EN increase successively. That is to say, the average interrupted time of the TSN output queues corresponding to each target ECS, i.e., Ehn, increases orderly. This experiment setting results in an increase in the transmission time of the same task to E1,E2,…,EN orderly. Hence, the number of the tasks selected to be offloaded to ECSs, namely, the task arrival rates to ECSs, gradually decreases in Figure 8. Especially, almost none of the edge devices here decided to offload their task to E5.Figure 8
Optimal arrival rates of the tasks to each ECS.To analyze the influence of the number of the edge devices,M, and the number of ECSs, N, on the task offloading decision-making result, we construct an experiment with M=10,15,20,25,30, N=20,25,30, and ξ=10−5. Figure 9 shows the average response time of the tasks in the edge devices with different M and N, which reflects the impact on the performance of the entire edge computing system. Obviously, the average response time of the edge computing system increases as M increases when N is fixed. Inversely, the average response time decrease as N increases when M is fixed.Figure 9
The average response time of the tasks in all edge devices with differentM and N values.


## 6. Conclusion

In this paper, we adopt the queueing theory to establish a time-cost model for task offloading stream transmission to resolve the problem of task offloading decision-making for edge computing in TSN. Meanwhile, we construct a utility function with the backward method to formulate the task offloading competition among edge devices as a game model. To find the Nash equilibrium of the proposed game, we design a distributed and sequential decision-making algorithm for multitask offloading. Finally, the exist of Nash equilibrium, the speed of convergence of Nash equilibrium, and the relationship between the number of calculation rounds and accuracy parameterξ are investigated through numerical experiments. Furthermore, to study the benefit of the proposed game theoretic approach, we analyze and compare the optimal strategy of task arrival rate, average time cost, and task offloading proportion among each edge device. The experiment results demonstrate that the TSN edge devices can obtain the optimal multi-task offloading strategies within finite rounds of calculation, which significantly reduce the average time cost of task computation, by utilizing the proposed model and approach.


## 7. Future Work

For future work, we will study the scenario where the tasks are generated in the queues of edge devices and are processed in the queues of ECSs, involving a multilevel queuing system. The goal is to develop efficient algorithms for each edge device to find the best response in games considering the fluence to TSN transmission. In addition, we will jointly allocate the task arrival rates and computing resources (such as computing memory and storage space) to further promote the application of edge computing technology in TSN.



---

*Source: 1750192-2022-12-30.xml*