# Joint Computation Offloading and Resource Allocation for NOMA-Enabled Multitask D2D System

Authors: Yuelin Han; Qi Zhu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Due to the limited computing capacity of mobile device and high network-accessing delay, user in the area where mobile terminals are densely distributed (e.g., schools, malls, and hospitals) will experience high latency when processing multiple computation-intensive tasks. In this paper, a computation offloading scheme based on Device-to-Device (D2D) communication is proposed to deal with the problem that users have multiple tasks to process. Exploiting nonorthogonal multiple access (NOMA), user can offload tasks to multiple nearby devices that have available idle computing resource. We aim to minimize the user’s total cost including time latency, energy consumption, and offloading charge, which is formulated as a mixed integer nonlinear programming (MINLP) problem. We use decomposition approach to solve our problem and propose a two-layer optimization scheme named Multitask Joint Computation Offloading and Resource Allocation (MT-JCORA). In the inner layer, the NOMA-transmission time optimization problem in given task offloading decision is proved as a strictly convex problem. In the outer layer, we design a heuristic algorithm based on GA algorithm to obtain the optimal task offloading decision. Simulation results demonstrate that MT-JCORA can effectively reduce the total cost of user compared with related schemes.


---

## Body

## 1. Introduction

The rapid development of mobile networks and smart devices provides a lot of service applications for people’s daily life, but at the same time, these applications also produce a large number of computation-intensive tasks. In particular, with the emergence of virtual reality, face recognition, and environmental interaction applications, the limited computing capacity of mobile terminal devices is difficult to meet the complex tasks with large computation and time-delay sensitivity. The problem that how to improve the Quality-of-Experience of mobile has been studied in existing work [1, 2]. Mobile edge computing (MEC) is considered to be an effective technology to face this challenge [3]. MEC offers cloud computing capabilities within the radio access network (RAN). MEC connects the user directly to the nearest cloud service-enabled edge network, which enable their requirement to be satisfied at anytime and anywhere [4–7]. By offloading tasks to the edge computing server connected to the base station [8], the user can get a better application experience. MEC server can complete tasks and return results to users in a short time due to its high computing capability.In recent years, computation offloading problem has been studied in order to make more effective use of MEC system [9–15]. In [9], edge computing-based Internet-of-Medical-Things (IoMTs) was studied to optimize latency and energy of edge-enabled sensor network environment during the peak time. In [10], the problem of energy-efficient resource management in cloud data centers was studied to ensure that the computing resources are efficiently utilized in server application workloads and minimize energy consumption while maintaining the required service level agreement (SLA). Song et al. [11] proposed an energy-efficient NOMA-enabled multiaccess MEC computation offloading scheme where each user’s task can be offloaded to multiple MEC servers simultaneously in partial mode. Meanwhile, the authors optimized the radio resource allocation for NOMA transmission. Jia et al. [12] propose a NOMA-enabled cognitive radio (CR) MEC architecture of multiple secondary users and multiple cognitive small base stations (SBSs), where all SBSs are equipped with limited computation and share the spectrum bands of primary users (PUs). In NOMA-enabled multiuser computation offloading scenario, Zhou et al. [13] formulated a computation offloading problem which jointly optimizes computation resource allocation, transmission power allocation, and subchannel assignment to minimize total completion delay. In [14], joint computation offloading and user association problem was studied for multitask mobile edge computing system to minimize total energy consumption. In Wu et al. [15], multitask and multiserver scenario was considered. The smart terminal generates a group of tasks and could offload them to various MEC servers simultaneously. All the above references focus on studying the computation offloading problem without considering the cooperative abilities among mobile terminals.Nowadays, mobile terminals are densely distributed and each device has a certain computing capacity. The user with lower computing capacity can offload its task to idle devices around by Device-to-Device (D2D) communications. Compared with MEC offloading scheme, D2D technology can further improve user’s experience and make full use of the cooperation among mobile users [16]. There have been various works studying in D2D-enabled offloading system [17–23]. In [17], the authors proposed a novel D2D-MEC technique that collaborates D2D communications and MEC to maximize the number of devices supported by cellular networks under the constraints of communication and computation resources. In [18], a computation offloading scheme for precedence-constrained tasks in a base station-assisted D2D scenario for the information-centric Internet of Things (IC-IoT) was proposed. In [19], the authors considered a cellular D2D MEC system consisting of one base station (BS) deployed with an MEC server and users. In [20], a novel mobile task offloading framework was proposed based on network-assisted D2D collaboration, where mobile users can dynamically and beneficially share the computation and communication resources among each other via the control assistance by the network operators. In [21], the authors proposed a D2D-enabled MEC framework that facilitates partial computation offloading to minimize the latency in shared spectrum. In [22], stochastic application requests, unpredictable mobile terminals states, time varying channel states, and computation resources were considered in D2D-assisted multiuser MEC system. In [23], the allocation of resource in D2D-aided Fog computing system with multiple mobile user equipment was investigated.Generally speaking, most of existing computation offloading works suppose that the smart terminal has only one computation-intensive task to process and choose to offload the task to one server in partial or binary way. Actually, one user may have multiple tasks with different latency limitations to process. For example, users often run multiple applications at the same time when using mobile devices, such as video players, social platforms, mobile games, and chat tools. However, the computing capacity of mobile device is limited; it is difficult to meet each task’s latency tolerance when processing multiple tasks. What is more, lower computing capacity may cause excessive CPU memory usage, which result in device crashes or automatic exit of some applications. In order to improve user experience, it is necessary to study the computation offloading problem in multitask multiaccess scenarios. In the scenario that mobile users are densely distributed, a lot of devices with idle computing resource may exist around the busy user who has multiple tasks to process. In this scene, users can offload multiple tasks to multiple nearby idle devices at the same time to reduce task execution time and energy consumption. Considering that (1) different idle devices have different idle computing resource and (2) different tasks have different properties and (3) channel status between the task publisher and idle devices, it is necessary to optimize the multitask multiaccess computation offloading problem. In this paper, we propose an optimization scheme named Multitask Joint Computation Offloading and Resource Allocation (MT-JCORA) for the scenario that users are densely distributed. Task execution time, energy consumption, and offloading charge are considered in MT-JCORA. The major contributions of this paper are as follows.(1)
We formulate the joint task offloading, task execution scheduling, and transmission time problem for a single user in NOMA-enabled multitask multiaccess D2D system. In our proposed framework, the user has multiple tasks with different latency limitations to process and can offload them to multiple idle devices around simultaneously. We formulate the problem aimed at minimizing the weighted sum of total latency, energy consumption, and task offloading charge while subject to each task’s latency tolerance(2)
For the formulated mixed integer nonlinear programming (MINLP) problem, we use decomposition approach to solve it and propose a novel two-layer scheme named MT-JCORA. In the inner layer, we consider a given task offloading decision and formulate the NOMA-transmission time allocation optimization problem, which is proved as a strictly convex problem, and we propose corresponding algorithm based on convex theory to solve it. In the outer layer, using the proposed algorithm as the basis, we study the task offloading decision to further minimize the MT’s total cost. Considering the complexity of problem in multiaccess multitask offloading scenario, we propose a heuristic algorithm based on GA algorithm to obtain the optimal task offloading decision(3)
We perform extensive evaluations under various system parameters to verify the performance of our proposed MT-JCORA scheme. Compared with local computing scheme, random offloading scheme, and the scheme in [15], MT-JCORA can reduce the weighted sum of total latency, energy consumption, and offloading charge efficiently versus the number of tasksThe rest of this paper is organized as follows. We introduce the system model and problem formulation in Section2. Our proposed two-layer optimization scheme MT-JCORA is presented in Section 3. Simulation results and comparisons with related schemes are presented in Section 4. In Section 5, we conclude this paper.


## 2. System Model

### 2.1. Offloading Framework

We consider a NOMA-enabled task offloading D2D collaborative system, in which devices are divided into two types, namely, task device (TD) and idle device (ID). During the computation offloading period, TD has multiple tasks that need to be executed and ID has available idle computing resource. As shown in Figure1, the system includes one TD and N IDs. We assume these devices are densely distributed, and denote the group of IDs as Λ=1,2,⋯,N. In particular, we assume the channel power gains from the TD to each ID are ordered as
(1)g1≥g2≥⋯≥gN.Figure 1
NOMA-enabled D2D offloading system.The channel status remains unchanged during one computation offloading period in quasistatic scenario [24]. Due to the limited computing capacity, it is hard for TD to meet each task’s latency limitation when processing multiple computation-intensive tasks. In the scenario where mobile devices are densely distributed, a lot of IDs may exist around the TD. The TD could offload tasks to nearby IDs to reduce time latency or energy consumption. Exploiting NOMA, the TD can offload tasks to multiple IDs at the same time.We consider that each device has large enough storage capacity and could cache multiple tasks during one computation period. Tasks are executed on each device in serial mode and different devices process tasks in parallel mode. For convenience, we assume that the task execution on each idle device is performed after task transmission finishing and each task’s output result could be sent back immediately after its execution. We do not consider the transmission delay of calculated results due to the small size [25] [26]. The important notations used in the rest of this paper are summarized in Table 1.Table 1
Notations’ definition.
NotationDefinitionΛSet of idle devicesΓSet of tasksTmTaskmgnChannel gain between TD and IDnCmRequired CPU cycles forTmDmInput data size forTmLmLatency limitation forTmxm,nOffloading indicator forTmxOffloading indicator of all tasksK0Number of tasks processed locallyKnNumber of tasks processed on IDnS0Task execution sequence on TDSnTask execution sequence on IDnflocComputing capacity of TDfnComputing capacity of IDnSnmLocation ofTm in SnS0mLocation ofTm in S0WChannel bandwidthn0Noise power spectrumμlEnergy consumption coefficient of TDμnEnergy consumption coefficient of IDnPmaxTransmission power limitation of TDEmaxnEnergy consumption limitation of IDnηnEnergy value coefficient of usernαTime latency coefficientβEnergy coefficientγOffloading charge coefficient


### 2.2. Task Model

We assume that TD hasM independent tasks to process, and each task can be offloaded or processed locally. We denote Γ=T1,T2,⋯,TM as the group of tasks. Each task Tm is described by three parameters, denoted as Cm,Dm,Lm. Cm (in CPU cycles) is the amount of CPU cycles required to execute task Tm, Dm (in bits) is input date size of task Tm, and Lm is the latency limitation of task Tm. We assume that each task is atomic and could not be further divided. Each task Tm has N+1 execution location choices. We denote xm,n∈0,1 as the offloading decision of task Tm, where n∈0∪Λ. If TD executes task Tm locally, xm,0=1. If TD decides to offload task Tm to idle device n, xm,n=1. To ensure that each task be executed at most on one device, the offloading decision of each task should satisfy
(2)∑n=0Nxm,n=1.We denoteK0,K1,⋯,Kn as the final number of tasks that are needed to be executed on each terminal. We denote S0=S0,1,S0,2,⋯,S0,K0 as the set of tasks processed locally; meanwhile, the vector is the order of task execution on TD. We denote Sn=Sn,1,Sn,2,⋯,Sn,Kn as the set of tasks processed on ID n; meanwhile, the vector is the order of task execution on ID n.


### 2.3. Cost Model

In this paper, we consider the user cost is consisted of time latency, energy consumption, and offloading charge that should be paid to IDs. If TD processes tasks locally, user cost is consisted of the energy consumption of task execution and time latency. If TD chooses to offload tasks to IDs, the user cost is consisted of the energy consumption of task transmission, transmission time latency, task execution time latency, and offloading charge. We will discuss the user cost in local computing mode and D2D offloading mode, respectively, as follows.


#### 2.3.1. Local Computing

If TD executes taskTm locally and local task execution order is S0, the completion time of task Tm is given by
(3)tm=∑i=S0,1S0mCifloc,where floc is the computation capability of TD and S0m is the location of task Tm in vector S0. We denote the energy coefficient μl to represent the energy consumption per CPU cycles on TD, which is related to CPU chip structure. The energy consumption to execute task Tm is given by
(4)Emexe=μlCm.The total energy consumption of task execution on TD is given as(5)Eloc=∑m=S0,1S0,K0μlCm.


#### 2.3.2. D2D-Based Offloading

In D2D offloading mode, NOMA technology is exploited to enable TD to transmit multiple tasks to different IDs simultaneously. Denotex as the offloading decision of all tasks; the transmission time of NOMA scheme is expressed as ttran. The minimum total transmit power in need can be expressed as
(6)Ptotx,ttran=Wn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm−Wn0gN,where W denotes the channel bandwidth and n0 is the power spectral of additive white Gaussian noise. The proof of (6) can refer [27], Prop. 1. The TD’s energy consumption of task transmission can be given by
(7)Etran=ttran⋅Ptot.If TD decides to offload taskTm to ID n and the task execution order on terminal n is Sn, the execution time of task Tm is given by
(8)tm,nexe=Cmfn,where fn is the computation capability of ID n. The completion time of task Tm is given by
(9)tm=ttran+∑i=Sn,1SnmCifn,where Snm is the location of task Tm in vector Sn. Combined with expression (3), the completion time of each task Tm can be expressed as
(10)tm=∑i=S0,1S0mCifloc,xm,n=1,n=0,ttran+∑i=Sn,1SnmCifn,xm,n=1,n∈Λ.Considering that IDs will consume energy of device during task execution, users do not have enough motivation to help each other. Therefore, to promote the cooperation among users, the TD should pay IDs task offloading charge for help. According to the law of diminishing marginal utility [28], task offloading charge that TD should pay to ID n is given by
(11)Monn=φnlog21+∑i=Sn,1Sn,KnμnCi,where φn is energy price coefficient of ID n and μn is the energy consumption coefficient of ID n. Since the remaining battery of different IDs is not the same, users of IDs may attach different importance to energy consumption. For the users whose device has sufficient remaining battery, they are likely to participate in helping others to execute tasks to earn service fees. On the contrary, if the user’s device is being in low battery state, user may be more concerned with energy consumption than task offloading charge. Considering ID’s computation capability and energy consumption limitation and user’s personal selfishness, φn is given as
(12)φn=fnEmaxnηn,where Emaxn is the energy consumption limitation of ID n and ηn denotes the value factor that user n attaches to energy consumption. Jointly considering task latency, energy consumption, and task offloading charge, the TD’s cost function Φ expression can be given as
(13)Φ=αmaxtm+βEloc+Etran+γ∑n=1NMonn,where α, β, and γ reflect the user’s attention to time latency, energy consumption, and offloading charge, respectively.


### 2.4. Problem Formulation

Based on the analysis of task model and cost model, we formulate the single user cost optimization problem in NOMA-enabled D2D system. We focus on minimizing the weighted sum of time latency, energy consumption, and task offloading charge. The mathematical problem is formulated as(14)Ρ1:Minimizex,ttran,S0,SnΦ(15a)s.t.tm≤Lm,∀m∈1,2,⋯,M(15b)∑m=Sn,1Sn,KnμCm≤Emaxn∀n∈Λ,(15c)Ptot≤Pmax,(15d)α+β+γ=1,(15e)∑j=1Nxi,j=1,(15f)α,β,γ∈0,1,ttran>0,xm,n∈0,1,where Pmax is the maximum transmission power of TD. Constraint (15a) ensures that each task must be completed in its latency limitation. Constraint (15b) ensures that the energy consumption of ID cannot exceed its limitation. Constraint (15c) ensures that the transmission power of TD cannot exceed Pmax. Constraint (15d) defines the relationship among the coefficients of time latency, energy consumption, and offloading charge. Constraint (15e) ensures that each task could only be executed on one device. Constraint (15f) clarifies the value range of parameters.


## 2.1. Offloading Framework

We consider a NOMA-enabled task offloading D2D collaborative system, in which devices are divided into two types, namely, task device (TD) and idle device (ID). During the computation offloading period, TD has multiple tasks that need to be executed and ID has available idle computing resource. As shown in Figure1, the system includes one TD and N IDs. We assume these devices are densely distributed, and denote the group of IDs as Λ=1,2,⋯,N. In particular, we assume the channel power gains from the TD to each ID are ordered as
(1)g1≥g2≥⋯≥gN.Figure 1
NOMA-enabled D2D offloading system.The channel status remains unchanged during one computation offloading period in quasistatic scenario [24]. Due to the limited computing capacity, it is hard for TD to meet each task’s latency limitation when processing multiple computation-intensive tasks. In the scenario where mobile devices are densely distributed, a lot of IDs may exist around the TD. The TD could offload tasks to nearby IDs to reduce time latency or energy consumption. Exploiting NOMA, the TD can offload tasks to multiple IDs at the same time.We consider that each device has large enough storage capacity and could cache multiple tasks during one computation period. Tasks are executed on each device in serial mode and different devices process tasks in parallel mode. For convenience, we assume that the task execution on each idle device is performed after task transmission finishing and each task’s output result could be sent back immediately after its execution. We do not consider the transmission delay of calculated results due to the small size [25] [26]. The important notations used in the rest of this paper are summarized in Table 1.Table 1
Notations’ definition.
NotationDefinitionΛSet of idle devicesΓSet of tasksTmTaskmgnChannel gain between TD and IDnCmRequired CPU cycles forTmDmInput data size forTmLmLatency limitation forTmxm,nOffloading indicator forTmxOffloading indicator of all tasksK0Number of tasks processed locallyKnNumber of tasks processed on IDnS0Task execution sequence on TDSnTask execution sequence on IDnflocComputing capacity of TDfnComputing capacity of IDnSnmLocation ofTm in SnS0mLocation ofTm in S0WChannel bandwidthn0Noise power spectrumμlEnergy consumption coefficient of TDμnEnergy consumption coefficient of IDnPmaxTransmission power limitation of TDEmaxnEnergy consumption limitation of IDnηnEnergy value coefficient of usernαTime latency coefficientβEnergy coefficientγOffloading charge coefficient


## 2.2. Task Model

We assume that TD hasM independent tasks to process, and each task can be offloaded or processed locally. We denote Γ=T1,T2,⋯,TM as the group of tasks. Each task Tm is described by three parameters, denoted as Cm,Dm,Lm. Cm (in CPU cycles) is the amount of CPU cycles required to execute task Tm, Dm (in bits) is input date size of task Tm, and Lm is the latency limitation of task Tm. We assume that each task is atomic and could not be further divided. Each task Tm has N+1 execution location choices. We denote xm,n∈0,1 as the offloading decision of task Tm, where n∈0∪Λ. If TD executes task Tm locally, xm,0=1. If TD decides to offload task Tm to idle device n, xm,n=1. To ensure that each task be executed at most on one device, the offloading decision of each task should satisfy
(2)∑n=0Nxm,n=1.We denoteK0,K1,⋯,Kn as the final number of tasks that are needed to be executed on each terminal. We denote S0=S0,1,S0,2,⋯,S0,K0 as the set of tasks processed locally; meanwhile, the vector is the order of task execution on TD. We denote Sn=Sn,1,Sn,2,⋯,Sn,Kn as the set of tasks processed on ID n; meanwhile, the vector is the order of task execution on ID n.


## 2.3. Cost Model

In this paper, we consider the user cost is consisted of time latency, energy consumption, and offloading charge that should be paid to IDs. If TD processes tasks locally, user cost is consisted of the energy consumption of task execution and time latency. If TD chooses to offload tasks to IDs, the user cost is consisted of the energy consumption of task transmission, transmission time latency, task execution time latency, and offloading charge. We will discuss the user cost in local computing mode and D2D offloading mode, respectively, as follows.


### 2.3.1. Local Computing

If TD executes taskTm locally and local task execution order is S0, the completion time of task Tm is given by
(3)tm=∑i=S0,1S0mCifloc,where floc is the computation capability of TD and S0m is the location of task Tm in vector S0. We denote the energy coefficient μl to represent the energy consumption per CPU cycles on TD, which is related to CPU chip structure. The energy consumption to execute task Tm is given by
(4)Emexe=μlCm.The total energy consumption of task execution on TD is given as(5)Eloc=∑m=S0,1S0,K0μlCm.


### 2.3.2. D2D-Based Offloading

In D2D offloading mode, NOMA technology is exploited to enable TD to transmit multiple tasks to different IDs simultaneously. Denotex as the offloading decision of all tasks; the transmission time of NOMA scheme is expressed as ttran. The minimum total transmit power in need can be expressed as
(6)Ptotx,ttran=Wn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm−Wn0gN,where W denotes the channel bandwidth and n0 is the power spectral of additive white Gaussian noise. The proof of (6) can refer [27], Prop. 1. The TD’s energy consumption of task transmission can be given by
(7)Etran=ttran⋅Ptot.If TD decides to offload taskTm to ID n and the task execution order on terminal n is Sn, the execution time of task Tm is given by
(8)tm,nexe=Cmfn,where fn is the computation capability of ID n. The completion time of task Tm is given by
(9)tm=ttran+∑i=Sn,1SnmCifn,where Snm is the location of task Tm in vector Sn. Combined with expression (3), the completion time of each task Tm can be expressed as
(10)tm=∑i=S0,1S0mCifloc,xm,n=1,n=0,ttran+∑i=Sn,1SnmCifn,xm,n=1,n∈Λ.Considering that IDs will consume energy of device during task execution, users do not have enough motivation to help each other. Therefore, to promote the cooperation among users, the TD should pay IDs task offloading charge for help. According to the law of diminishing marginal utility [28], task offloading charge that TD should pay to ID n is given by
(11)Monn=φnlog21+∑i=Sn,1Sn,KnμnCi,where φn is energy price coefficient of ID n and μn is the energy consumption coefficient of ID n. Since the remaining battery of different IDs is not the same, users of IDs may attach different importance to energy consumption. For the users whose device has sufficient remaining battery, they are likely to participate in helping others to execute tasks to earn service fees. On the contrary, if the user’s device is being in low battery state, user may be more concerned with energy consumption than task offloading charge. Considering ID’s computation capability and energy consumption limitation and user’s personal selfishness, φn is given as
(12)φn=fnEmaxnηn,where Emaxn is the energy consumption limitation of ID n and ηn denotes the value factor that user n attaches to energy consumption. Jointly considering task latency, energy consumption, and task offloading charge, the TD’s cost function Φ expression can be given as
(13)Φ=αmaxtm+βEloc+Etran+γ∑n=1NMonn,where α, β, and γ reflect the user’s attention to time latency, energy consumption, and offloading charge, respectively.


## 2.3.1. Local Computing

If TD executes taskTm locally and local task execution order is S0, the completion time of task Tm is given by
(3)tm=∑i=S0,1S0mCifloc,where floc is the computation capability of TD and S0m is the location of task Tm in vector S0. We denote the energy coefficient μl to represent the energy consumption per CPU cycles on TD, which is related to CPU chip structure. The energy consumption to execute task Tm is given by
(4)Emexe=μlCm.The total energy consumption of task execution on TD is given as(5)Eloc=∑m=S0,1S0,K0μlCm.


## 2.3.2. D2D-Based Offloading

In D2D offloading mode, NOMA technology is exploited to enable TD to transmit multiple tasks to different IDs simultaneously. Denotex as the offloading decision of all tasks; the transmission time of NOMA scheme is expressed as ttran. The minimum total transmit power in need can be expressed as
(6)Ptotx,ttran=Wn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm−Wn0gN,where W denotes the channel bandwidth and n0 is the power spectral of additive white Gaussian noise. The proof of (6) can refer [27], Prop. 1. The TD’s energy consumption of task transmission can be given by
(7)Etran=ttran⋅Ptot.If TD decides to offload taskTm to ID n and the task execution order on terminal n is Sn, the execution time of task Tm is given by
(8)tm,nexe=Cmfn,where fn is the computation capability of ID n. The completion time of task Tm is given by
(9)tm=ttran+∑i=Sn,1SnmCifn,where Snm is the location of task Tm in vector Sn. Combined with expression (3), the completion time of each task Tm can be expressed as
(10)tm=∑i=S0,1S0mCifloc,xm,n=1,n=0,ttran+∑i=Sn,1SnmCifn,xm,n=1,n∈Λ.Considering that IDs will consume energy of device during task execution, users do not have enough motivation to help each other. Therefore, to promote the cooperation among users, the TD should pay IDs task offloading charge for help. According to the law of diminishing marginal utility [28], task offloading charge that TD should pay to ID n is given by
(11)Monn=φnlog21+∑i=Sn,1Sn,KnμnCi,where φn is energy price coefficient of ID n and μn is the energy consumption coefficient of ID n. Since the remaining battery of different IDs is not the same, users of IDs may attach different importance to energy consumption. For the users whose device has sufficient remaining battery, they are likely to participate in helping others to execute tasks to earn service fees. On the contrary, if the user’s device is being in low battery state, user may be more concerned with energy consumption than task offloading charge. Considering ID’s computation capability and energy consumption limitation and user’s personal selfishness, φn is given as
(12)φn=fnEmaxnηn,where Emaxn is the energy consumption limitation of ID n and ηn denotes the value factor that user n attaches to energy consumption. Jointly considering task latency, energy consumption, and task offloading charge, the TD’s cost function Φ expression can be given as
(13)Φ=αmaxtm+βEloc+Etran+γ∑n=1NMonn,where α, β, and γ reflect the user’s attention to time latency, energy consumption, and offloading charge, respectively.


## 2.4. Problem Formulation

Based on the analysis of task model and cost model, we formulate the single user cost optimization problem in NOMA-enabled D2D system. We focus on minimizing the weighted sum of time latency, energy consumption, and task offloading charge. The mathematical problem is formulated as(14)Ρ1:Minimizex,ttran,S0,SnΦ(15a)s.t.tm≤Lm,∀m∈1,2,⋯,M(15b)∑m=Sn,1Sn,KnμCm≤Emaxn∀n∈Λ,(15c)Ptot≤Pmax,(15d)α+β+γ=1,(15e)∑j=1Nxi,j=1,(15f)α,β,γ∈0,1,ttran>0,xm,n∈0,1,where Pmax is the maximum transmission power of TD. Constraint (15a) ensures that each task must be completed in its latency limitation. Constraint (15b) ensures that the energy consumption of ID cannot exceed its limitation. Constraint (15c) ensures that the transmission power of TD cannot exceed Pmax. Constraint (15d) defines the relationship among the coefficients of time latency, energy consumption, and offloading charge. Constraint (15e) ensures that each task could only be executed on one device. Constraint (15f) clarifies the value range of parameters.


## 3. Algorithm Design

In this section, we propose a two-layer optimization scheme named Multitask Joint Computation Offloading and Resource Allocation (MT-JCORA) for solving problemΡ1. In order to simplify the constraints of Ρ1, we adopt a penalty function method [29] to convert constraint (15a) into a corresponding penalty. For the offloading decision that fails to complete all tasks on time, penalty should be added on total cost. Problem Ρ1 is transformed as
(16)Ρ2:Minimizex,ttran,S0,SnΦ+σmaxm∈1,2,⋯Mmaxtm−Lm,0tm−Lms.t.14b−14fwhere σ is the penalty coefficient.Ignoring the influence of transmission timettran, we consider S0 and Sn that satisfied constraint (15a) as the feasible task execution sequence under certain offloading decision x. We consider x is feasible if there exists at least one feasible task execution sequence under it. The task sequencing way of S0 and Sn will affect the feasible region of x, but has no influence on the optimal value of problem Ρ2. In order to get the largest feasible region of x, the order of tasks in S0 and Sn should be sorted by each task’s latency limitation Lm; that is, the task with high latency requirement will be executed firstly.In the problem ofΡ2, x is an integer variable, and ttran is a continuous variable. In addition, the user cost function is nonlinear with respect to ttran according to (6). Therefore, problem Ρ2 is a constrained mixed integer nonlinear programming problem. To obtain the optimal computation offloading scheme, we adopt a two-layer optimization structure scheme as follows.


### 3.1. Inner-Solving Optimal Transmission Timettran

Considering that the execution latency of each task, local execution energy consumption, and task offloading charge are determined in given task offloading decisionx, problem Ρ2 can be transformed as
(17)Sub‐t:Minimizettranαttran+βttranPtotttrans.t.14aand14c


### 3.2. Outer-Solving Optimal Task Offloading Decisionx

On the basis of the inner layer problemSub‐t is solved, we can obtain the TD’s total cost by the optimal transmission time result for any task offloading decision. Problem Ρ2 can be simplified as the problem Sub‐x to get the optimal task offloading decision.
(18)Sub‐x:Minimizexαmaxtm+βEloc+γ∑n=1NMonn+σmaxm∈1,2,⋯Mmaxtm−Lm,0tm−Lms.t.14a,14band14d−14f


### 3.3. Proposed Algorithm to Solve Problem (Sub-t)

To ensure that each task could be completed in their latency limitation, the transmission time upper limitttranup should be solved in given task offloading decision x. The transmission time upper limit between TD and ID n in given execution sequence Sn can be expressed as
(19)Δn=minm∈SnLm−∑i=Sn,1SnmCifn.The transmission time upper limit in given task offloading decisionx can be given as
(20)ttranup=minn∈ΛΔn.Based on (20), the constraint (15a) can be converted to the form of transmission time constraint, and problem Sub‐t can be transformed as
(21)Sub‐t‐i:Minimizettranαttran+βttranPtotttran(22a)s.t.0<ttran≤ttranup(22b)Ptotttran≤Pmax.Constraint (22a) stems from constraint (15a). Constraint (22b) stems from (15c).Define functionfttran and give the first and second derivative of it as follows.
(23)fttran=αttran+βttranWn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm−Wn0gN,(24)f′ttran=α−βWn0gN+βn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDmW−ln2⋅1ttran∑k=nN∑m=1Mxm,kDm,(25)f″ttran=βn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm⋅ln22⋅1ttran3W∑k=nN∑m=1Mxm,kDm2.Based on the analysis of (25), f″ttran>0 is always satisfied when ttran>0, and fttran is a strictly convex function. It can be proved with (6) that Ptot is a strictly decreasing function of ttran under given task offloading decision x, and (22b) is also convex. Combined with the convex region (22a), it can be proved that problem Sub‐t‐i is a strictly convex optimization problem.Considering the transmission power limitation andPtot increases as the decrease of ttran in given task offloading decision x, denote ttranlow as the transmission time lower limit under constraint (22b). ttranlow can be solved by the equation Pmax−Ptotttran=0. Denote t′tran as the value to satisfy f′ttran=0. t′tran is the optimal transmission time decision to minimize TD’s cost without considering each task’s latency tolerance. The solution of ttranlow or t′tran is a complex nonlinear problem and is difficult to get results directly. We adopt bisection search method to get the values of ttranlow and t′tran under arbitrary precision constraint. With the analysis of limits for the function f′ttran and Pmax−Ptotttran, we have
(26)limttran⟶0+f′ttran<0,limttran⟶0+Pmax−Ptotttran<0limttran⟶+∞f′ttran=α>0,limttran⟶+∞Pmax−Ptotttran=Pmax>0.Both functionf′ttran and Pmax−Ptotttran are positively correlated with ttran. We obtain t′tran and ttranlow under certain precision constraint by using bisection search to minimize the value of f′ttran and Pmax−Ptotttran, respectively.We aim at maximizing the number of tasks completed on time, meanwhile optimizing user’s total cost.Here, we analyze the optimal transmission timettran∗ as follows:
(1)
Ifttranup≥ttranlow, which means the maximal transmission power of TD could ensure that task transmission can be completed within ttranup. In this case, all the tasks that are offloaded to IDs could be executed within their latency limitation and ttran∗ should be further solved to minimize TD’s cost. If ttranlow≤t′tran and t′tran≤ttranup, either maximum transmission power or each task’s latency tolerance has no influence on TD’s optimal cost, and ttran∗ is given as ttran∗=t′tran. If ttranlow≤t′tran and t′tran>ttranup, t′tran cannot promise all tasks be completed on time. In order to maximize the ratio of tasks completed on time, the value of ttran∗ can be given as ttran∗=ttranup. If ttranlow>t′tran, the optimal TD’s cost is limited by its maximum transmission power. In order to minimize TD’s cost, the value of ttran∗ can be given as ttran∗=ttranlow. In summary, the value of ttran∗ can be given as follows:(27)ttran∗=mint′tran,ttranup,ttranlow≤t′tran,ttranlow,ttranlow>t′tran.(2)
Ifttranup<ttranlow, it may be caused by the following two reasons:(i)
Some tasks that are offloaded cannot be completed on time due to the fact that the maximal transmission powerPmax cannot ensure ttranlow≤ttranup(ii)
Some tasks that are offloaded cannot be completed on time due to the unreasonable task offloading decisionx, that is, ttranup<0For the above two cases, we discuss the value ofttran∗ as follows.Ifmaxm∈ΓLm−t′m<ttranlow, this means that no offloaded task can be completed in latency limitation. In this case, the value of ttran∗ is given as follows.
(28)ttran∗=maxttranlow,t′tran.Ifmaxm∈ΓLm−tm≥ttranlow, this means that there exist some offloaded tasks that can be completed on time. In this case, ttran∗ should be solved to maximize the ratio of tasks completed on time meanwhile minimizing the TD’s total cost. We calculate the new transmission time upper limit ttranup∗ among the tasks that can be completed on time according to (19) and (20). If ttranup∗≥t′tran and ttranlow≤t′tran, the value of ttran∗ can be given as ttran∗=t′tran to minimize TD’s cost. If ttranup∗≥t′tran and ttranlow>t′tran, the value of ttran∗ can be given as ttran∗=ttranlow to satisfy the transmission power constraint. If ttranup∗<t′tran, the value of ttran∗ can be given as ttran∗=ttranup∗ to maximize the ratio of tasks completed on time. In summary, the value of ttran∗ can be given as follows.
(29)ttran∗=maxttranlow,t′tran,ttranup∗≥t′tran,ttranup∗,ttranup∗<t′tran.The pseudocode of the proposed transmission time algorithm is represented in Algorithm1. As shown in Algorithm 1, with given task offloading decision x and the tasks’ latency tolerances Lmm∈Γ, we could obtain the optimal transmission time decision ttran∗. As shown in line 1, the corresponding ttranlow, t′tran, and ttranup should be calculated firstly under given x and Lmm∈Γ. In lines 2–7, the case that all the offloaded tasks can be completed on time is described, and the value of ttran∗ can be give as (27). In lines 8-9, there is no offloaded task that can be completed on time; in this case, we choose to minimize TD’s cost without considering the ratio of tasks completed on time. The value of ttran∗ can be given as (28). In lines 10–17, the case that part of offloaded tasks can be completed on time is described. In line 11, in order to minimize the ratio of tasks completed on time, the new transmission time up limit ttranup∗ should be calculated firstly according to (19) and (20). The value of ttran∗ can be given as (29).Algorithm 1: The optimal transmission time.
Input:x, Lmm∈ΓOutput:ttran∗1.  Calculatettranlow, t′tran, and ttranup2.Ifttranlow≤ttranupdo3.Ifttranlow≤t′trando4.ttran∗=mint′tran,ttranup5.Else do6.ttran∗=ttranlow7.End if8.Else ifmaxm∈ΓLm−tm<ttranlowdo9.ttran∗=maxttranlow,t′tran10.Else ifmaxm∈ΓLm−tm≥ttranlowdo11.  Calculate the new transmission time up limitttranup∗12.Ifttranup∗<t′trando13.ttran∗=ttranup∗14.Else do15.ttran∗=maxttranlow,t′tran16.End if17.End if


### 3.4. Proposed Algorithm to Solve Problem (Sub-x)

Due to the fact that the task offloading decisionx is an integer variable and the value region of x is finite, we can obtain the optimal task offloading decision by enumeration. Considering that the time complexity of exhaustive scheme increases exponentially as the number of tasks increases, we propose Algorithm 2 based on genetic algorithm to solve the problem Sub‐x.Algorithm 2: The optimal offloading decision.
Inputs:p^, g^, q^, m^Output:x∗1. Initialize the gene of each individual according to (15b) and (15e)2.Whileg≤g^do3.i=04.Whilei<q^do5.   Select two individuals from the population6.   Generateθ1,θ2 randomly7.   Perform the crossover operation, denote the offspring as child 1 and child 28.For each child do9.If the child cannot meet (15b) or (15e) do10.      Execute correction for the child11.End if12.    Add the child to the population13.End for14.i=i+215.End while16.For each individual do17.   Generateθ3,θ4 randomly18.   Perform the mutation operation according tom^19.If the individual cannot meet (15b) or (15e) do20.    Execute correction for the individual21.End if22.End for23.  Calculate the fitness of each individual24.  Select the bestp^ individuals according to finesses as the new population25.End while26. Return the best individual in the population asx∗The basic principle of genetic algorithm is biological evolution process based on natural selection and genetics mechanism. It is usually used to solve nonlinear, global, and more complex combinatorial optimization problems, and it is a high-performance computing model [30]. Genetic algorithm mainly contains three operations, namely, cross operation, mutation operation, and selection operation. Denote p^ as the population size. In the initialization of genetic algorithm, we should convert the task offloading decision into individual by encoding. Each task of TD has N+1 execution locations, and the solution of task offloading decision x contains M×N+1 elements, which represent the execution indicators of TD’s tasks. We convert each solution of task offloading decision x into an individual of population. As shown in Figure 2, each individual has N+1 genes, which represent the local device and N idle devices. There exist M elements on each gene, which represent task execution indicators on each device, respectively.Figure 2
Individual gene diagram.In cross operation, two individuals as the parents will be selected from population, and cross operation will be executed on them. Denoteθ1,θ2 as the cross point of parents, where θ1 denotes the location of gene and θ2 denotes the location of elements on θ1. On the basis of θ1,θ2, exchange the genes of these two individuals, and generate two new individuals. Each new individual represents a new solution of task offloading decision x. Due to the randomness of θ1,θ2, the new individuals may mean unreasonable task offloading decision; in other words, the new individuals may cannot satisfy the constraints (15b) and (15e). Therefore, necessary correction should be done for the new individuals; details are as follows:
(1)
For the task that is for the tasks that are missing to execute, we assign available execution location randomly for them(2)
For the tasks that are executed repeatedly, we decide their final execution locationAfter correction, the new individuals will be added into the population. Denoteq^ as the number of individuals needed to be reproduced in each evolution, and mutation operation will be executed after all the q^ new individuals are reproduced.In mutation operation, each individual in the population will execute gene mutation. Denotem^ as the mutation possibility of each individual. Denote θ3,θ4 as the mutation point, where θ3 denotes the location of gene and θ4 denotes the location of elements on θ3. Denote xθ3,θ4 as the value of the element on θ3,θ4.Details of mutation are as follows:(1)
Letxθ3,θ4=0 when xθ3,θ4=1, and select device to execute the corresponding task randomly(2)
Letxθ3,θ4=1 when xθ3,θ4=0, and remove the corresponding task from its original execution deviceDue to the randomness ofθ3,θ4, correction should also be executed for individuals after mutation.On the basis of Algorithm1, we could obtain the optimal NOMA-transmission time decision under given task offloading decision, and then, the corresponding TD’s cost of each individual could be calculated. The lower TD’s cost means the higher fitness of individual. In selection operation, the best p^ individuals will be selected to participate the next evolution. The pseudocode is represented in Algorithm 2.Denoteg^ as the maximum evolution iterations. As shown in Algorithm 2, each evolution contains three parts, which are cross operation, mutation operation, and selection operation. As shown in line 1, in the phase of initialization, the elements on each individual are initialized randomly according to (15b) and (15e) to ensure that the energy consumption of each ID does not exceed their energy limitations and each task be executed at most one device. In lines 3–15, the crossover operations will generate q^ new individuals. In lines 5–7, two individuals are selected randomly from the population as the parents and generate two offspring. In lines 8–13, we firstly check whether each child is satisfied with (15b) and (15e) and then execute correction for the unreasonable child. As shown in lines 16–22, during the mutation phase, every individual will perform mutation operation according to the possibility m^. In line 17, θ3,θ4 is selected randomly on individual. In line 18, we perform the mutation operation for current individual. As shown in lines 19–21, we also correct the individual according to (15b) and (15e). As shown in lines 23-24, after the mutation operation, we calculate the fitness of each individual and select the best p^ individuals from the population for the next evolution.


## 3.1. Inner-Solving Optimal Transmission Timettran

Considering that the execution latency of each task, local execution energy consumption, and task offloading charge are determined in given task offloading decisionx, problem Ρ2 can be transformed as
(17)Sub‐t:Minimizettranαttran+βttranPtotttrans.t.14aand14c


## 3.2. Outer-Solving Optimal Task Offloading Decisionx

On the basis of the inner layer problemSub‐t is solved, we can obtain the TD’s total cost by the optimal transmission time result for any task offloading decision. Problem Ρ2 can be simplified as the problem Sub‐x to get the optimal task offloading decision.
(18)Sub‐x:Minimizexαmaxtm+βEloc+γ∑n=1NMonn+σmaxm∈1,2,⋯Mmaxtm−Lm,0tm−Lms.t.14a,14band14d−14f


## 3.3. Proposed Algorithm to Solve Problem (Sub-t)

To ensure that each task could be completed in their latency limitation, the transmission time upper limitttranup should be solved in given task offloading decision x. The transmission time upper limit between TD and ID n in given execution sequence Sn can be expressed as
(19)Δn=minm∈SnLm−∑i=Sn,1SnmCifn.The transmission time upper limit in given task offloading decisionx can be given as
(20)ttranup=minn∈ΛΔn.Based on (20), the constraint (15a) can be converted to the form of transmission time constraint, and problem Sub‐t can be transformed as
(21)Sub‐t‐i:Minimizettranαttran+βttranPtotttran(22a)s.t.0<ttran≤ttranup(22b)Ptotttran≤Pmax.Constraint (22a) stems from constraint (15a). Constraint (22b) stems from (15c).Define functionfttran and give the first and second derivative of it as follows.
(23)fttran=αttran+βttranWn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm−Wn0gN,(24)f′ttran=α−βWn0gN+βn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDmW−ln2⋅1ttran∑k=nN∑m=1Mxm,kDm,(25)f″ttran=βn0∑n=1N1gn−1gn−121/ttranW∑k=nN∑m=1Mxm,kDm⋅ln22⋅1ttran3W∑k=nN∑m=1Mxm,kDm2.Based on the analysis of (25), f″ttran>0 is always satisfied when ttran>0, and fttran is a strictly convex function. It can be proved with (6) that Ptot is a strictly decreasing function of ttran under given task offloading decision x, and (22b) is also convex. Combined with the convex region (22a), it can be proved that problem Sub‐t‐i is a strictly convex optimization problem.Considering the transmission power limitation andPtot increases as the decrease of ttran in given task offloading decision x, denote ttranlow as the transmission time lower limit under constraint (22b). ttranlow can be solved by the equation Pmax−Ptotttran=0. Denote t′tran as the value to satisfy f′ttran=0. t′tran is the optimal transmission time decision to minimize TD’s cost without considering each task’s latency tolerance. The solution of ttranlow or t′tran is a complex nonlinear problem and is difficult to get results directly. We adopt bisection search method to get the values of ttranlow and t′tran under arbitrary precision constraint. With the analysis of limits for the function f′ttran and Pmax−Ptotttran, we have
(26)limttran⟶0+f′ttran<0,limttran⟶0+Pmax−Ptotttran<0limttran⟶+∞f′ttran=α>0,limttran⟶+∞Pmax−Ptotttran=Pmax>0.Both functionf′ttran and Pmax−Ptotttran are positively correlated with ttran. We obtain t′tran and ttranlow under certain precision constraint by using bisection search to minimize the value of f′ttran and Pmax−Ptotttran, respectively.We aim at maximizing the number of tasks completed on time, meanwhile optimizing user’s total cost.Here, we analyze the optimal transmission timettran∗ as follows:
(1)
Ifttranup≥ttranlow, which means the maximal transmission power of TD could ensure that task transmission can be completed within ttranup. In this case, all the tasks that are offloaded to IDs could be executed within their latency limitation and ttran∗ should be further solved to minimize TD’s cost. If ttranlow≤t′tran and t′tran≤ttranup, either maximum transmission power or each task’s latency tolerance has no influence on TD’s optimal cost, and ttran∗ is given as ttran∗=t′tran. If ttranlow≤t′tran and t′tran>ttranup, t′tran cannot promise all tasks be completed on time. In order to maximize the ratio of tasks completed on time, the value of ttran∗ can be given as ttran∗=ttranup. If ttranlow>t′tran, the optimal TD’s cost is limited by its maximum transmission power. In order to minimize TD’s cost, the value of ttran∗ can be given as ttran∗=ttranlow. In summary, the value of ttran∗ can be given as follows:(27)ttran∗=mint′tran,ttranup,ttranlow≤t′tran,ttranlow,ttranlow>t′tran.(2)
Ifttranup<ttranlow, it may be caused by the following two reasons:(i)
Some tasks that are offloaded cannot be completed on time due to the fact that the maximal transmission powerPmax cannot ensure ttranlow≤ttranup(ii)
Some tasks that are offloaded cannot be completed on time due to the unreasonable task offloading decisionx, that is, ttranup<0For the above two cases, we discuss the value ofttran∗ as follows.Ifmaxm∈ΓLm−t′m<ttranlow, this means that no offloaded task can be completed in latency limitation. In this case, the value of ttran∗ is given as follows.
(28)ttran∗=maxttranlow,t′tran.Ifmaxm∈ΓLm−tm≥ttranlow, this means that there exist some offloaded tasks that can be completed on time. In this case, ttran∗ should be solved to maximize the ratio of tasks completed on time meanwhile minimizing the TD’s total cost. We calculate the new transmission time upper limit ttranup∗ among the tasks that can be completed on time according to (19) and (20). If ttranup∗≥t′tran and ttranlow≤t′tran, the value of ttran∗ can be given as ttran∗=t′tran to minimize TD’s cost. If ttranup∗≥t′tran and ttranlow>t′tran, the value of ttran∗ can be given as ttran∗=ttranlow to satisfy the transmission power constraint. If ttranup∗<t′tran, the value of ttran∗ can be given as ttran∗=ttranup∗ to maximize the ratio of tasks completed on time. In summary, the value of ttran∗ can be given as follows.
(29)ttran∗=maxttranlow,t′tran,ttranup∗≥t′tran,ttranup∗,ttranup∗<t′tran.The pseudocode of the proposed transmission time algorithm is represented in Algorithm1. As shown in Algorithm 1, with given task offloading decision x and the tasks’ latency tolerances Lmm∈Γ, we could obtain the optimal transmission time decision ttran∗. As shown in line 1, the corresponding ttranlow, t′tran, and ttranup should be calculated firstly under given x and Lmm∈Γ. In lines 2–7, the case that all the offloaded tasks can be completed on time is described, and the value of ttran∗ can be give as (27). In lines 8-9, there is no offloaded task that can be completed on time; in this case, we choose to minimize TD’s cost without considering the ratio of tasks completed on time. The value of ttran∗ can be given as (28). In lines 10–17, the case that part of offloaded tasks can be completed on time is described. In line 11, in order to minimize the ratio of tasks completed on time, the new transmission time up limit ttranup∗ should be calculated firstly according to (19) and (20). The value of ttran∗ can be given as (29).Algorithm 1: The optimal transmission time.
Input:x, Lmm∈ΓOutput:ttran∗1.  Calculatettranlow, t′tran, and ttranup2.Ifttranlow≤ttranupdo3.Ifttranlow≤t′trando4.ttran∗=mint′tran,ttranup5.Else do6.ttran∗=ttranlow7.End if8.Else ifmaxm∈ΓLm−tm<ttranlowdo9.ttran∗=maxttranlow,t′tran10.Else ifmaxm∈ΓLm−tm≥ttranlowdo11.  Calculate the new transmission time up limitttranup∗12.Ifttranup∗<t′trando13.ttran∗=ttranup∗14.Else do15.ttran∗=maxttranlow,t′tran16.End if17.End if


## 3.4. Proposed Algorithm to Solve Problem (Sub-x)

Due to the fact that the task offloading decisionx is an integer variable and the value region of x is finite, we can obtain the optimal task offloading decision by enumeration. Considering that the time complexity of exhaustive scheme increases exponentially as the number of tasks increases, we propose Algorithm 2 based on genetic algorithm to solve the problem Sub‐x.Algorithm 2: The optimal offloading decision.
Inputs:p^, g^, q^, m^Output:x∗1. Initialize the gene of each individual according to (15b) and (15e)2.Whileg≤g^do3.i=04.Whilei<q^do5.   Select two individuals from the population6.   Generateθ1,θ2 randomly7.   Perform the crossover operation, denote the offspring as child 1 and child 28.For each child do9.If the child cannot meet (15b) or (15e) do10.      Execute correction for the child11.End if12.    Add the child to the population13.End for14.i=i+215.End while16.For each individual do17.   Generateθ3,θ4 randomly18.   Perform the mutation operation according tom^19.If the individual cannot meet (15b) or (15e) do20.    Execute correction for the individual21.End if22.End for23.  Calculate the fitness of each individual24.  Select the bestp^ individuals according to finesses as the new population25.End while26. Return the best individual in the population asx∗The basic principle of genetic algorithm is biological evolution process based on natural selection and genetics mechanism. It is usually used to solve nonlinear, global, and more complex combinatorial optimization problems, and it is a high-performance computing model [30]. Genetic algorithm mainly contains three operations, namely, cross operation, mutation operation, and selection operation. Denote p^ as the population size. In the initialization of genetic algorithm, we should convert the task offloading decision into individual by encoding. Each task of TD has N+1 execution locations, and the solution of task offloading decision x contains M×N+1 elements, which represent the execution indicators of TD’s tasks. We convert each solution of task offloading decision x into an individual of population. As shown in Figure 2, each individual has N+1 genes, which represent the local device and N idle devices. There exist M elements on each gene, which represent task execution indicators on each device, respectively.Figure 2
Individual gene diagram.In cross operation, two individuals as the parents will be selected from population, and cross operation will be executed on them. Denoteθ1,θ2 as the cross point of parents, where θ1 denotes the location of gene and θ2 denotes the location of elements on θ1. On the basis of θ1,θ2, exchange the genes of these two individuals, and generate two new individuals. Each new individual represents a new solution of task offloading decision x. Due to the randomness of θ1,θ2, the new individuals may mean unreasonable task offloading decision; in other words, the new individuals may cannot satisfy the constraints (15b) and (15e). Therefore, necessary correction should be done for the new individuals; details are as follows:
(1)
For the task that is for the tasks that are missing to execute, we assign available execution location randomly for them(2)
For the tasks that are executed repeatedly, we decide their final execution locationAfter correction, the new individuals will be added into the population. Denoteq^ as the number of individuals needed to be reproduced in each evolution, and mutation operation will be executed after all the q^ new individuals are reproduced.In mutation operation, each individual in the population will execute gene mutation. Denotem^ as the mutation possibility of each individual. Denote θ3,θ4 as the mutation point, where θ3 denotes the location of gene and θ4 denotes the location of elements on θ3. Denote xθ3,θ4 as the value of the element on θ3,θ4.Details of mutation are as follows:(1)
Letxθ3,θ4=0 when xθ3,θ4=1, and select device to execute the corresponding task randomly(2)
Letxθ3,θ4=1 when xθ3,θ4=0, and remove the corresponding task from its original execution deviceDue to the randomness ofθ3,θ4, correction should also be executed for individuals after mutation.On the basis of Algorithm1, we could obtain the optimal NOMA-transmission time decision under given task offloading decision, and then, the corresponding TD’s cost of each individual could be calculated. The lower TD’s cost means the higher fitness of individual. In selection operation, the best p^ individuals will be selected to participate the next evolution. The pseudocode is represented in Algorithm 2.Denoteg^ as the maximum evolution iterations. As shown in Algorithm 2, each evolution contains three parts, which are cross operation, mutation operation, and selection operation. As shown in line 1, in the phase of initialization, the elements on each individual are initialized randomly according to (15b) and (15e) to ensure that the energy consumption of each ID does not exceed their energy limitations and each task be executed at most one device. In lines 3–15, the crossover operations will generate q^ new individuals. In lines 5–7, two individuals are selected randomly from the population as the parents and generate two offspring. In lines 8–13, we firstly check whether each child is satisfied with (15b) and (15e) and then execute correction for the unreasonable child. As shown in lines 16–22, during the mutation phase, every individual will perform mutation operation according to the possibility m^. In line 17, θ3,θ4 is selected randomly on individual. In line 18, we perform the mutation operation for current individual. As shown in lines 19–21, we also correct the individual according to (15b) and (15e). As shown in lines 23-24, after the mutation operation, we calculate the fitness of each individual and select the best p^ individuals from the population for the next evolution.


## 4. Experiment Evaluation

In this section, we evaluate the performance of our proposed MT-JCORA optimization scheme in terms of total cost, time latency, energy consumption, and the ratio of tasks completed on time.


### 4.1. Parameter Setting

We evaluate the performance of our proposed algorithms by computer software MATLAB, and the simulation scenario is shown in Figure1. The parameters of simulation are given as follows according to [31, 32]. IDs are distributed randomly in the D2D communication coverage area of the user who has multiple tasks to execute. The number of IDs is 5. The maximum D2D communication coverage radius is 50 m. The channel bandwidth W is 20 MHz. The channel gains between user and IDs are given as h=kd−λ, where the path loss coefficient k is 0.001 and path loss exponent λ is 3.6. The input data size of each task varies from 2 to 5 MB, each task’s required CPU cycles varies from 1.5 to 4.5 gigacycles, and each task’s latency limitation randomly varies from 4 to 6 s. The computation capacity of each ID varies from 2 to 4 GHz. The computation capacity of local device is 2 GHz. The energy coefficient μ is 500 mJ/gigacycle. The energy consumption limitation of each ID is 5 J, and the value coefficients ηn of their user vary from 1 to 2 J/Hz. We set the delay coefficient α, energy consumption coefficient β, and offloading charge coefficient γ of user as 0.3, 0.4, and 0.3, respectively. Transmitting power limitation Pmax of local device is 1 W, and the noise power spectrum is -163 dBm/Hz. Parameters of Algorithm 2 are given as follows: g^=500, p^=100, q^=50, and m^=0.5.In order to evaluate the performance of the proposed MT-JCORA, we introduce other four methods in the same parameter setting for comparison.(i)
Random scheme (RS): each task selects the execution device randomly, and each ID could receive multiple tasks during one computation period(ii)
Exhaustive scheme (ES): exhaust all the possible task offloading decisions, and calculate user total cost under the corresponding optimal transmission time(iii)
Local scheme (LS): all the tasks are executed locally(iv)
Scheme in [15]: MT could offload multiple tasks to IDs around simultaneously, but each ID could receive at most one task


### 4.2. Simulation Results

Figure3 shows the ratio of tasks completed on time versus the number of TD’s tasks in our proposed MT-JCORA, RS, ES, LS, and the scheme in [15], respectively. As can be seen from Figure 3, the performance of MT-JCORA is basically the same as that of ES scheme, which is because MT-JCORA jointly consider all task’s latency limitation and could efficiently search the optimal task offloading decision. In LS scheme, all the tasks are executed in serial on TD. Some tasks cannot be completed within their latency limitation due to the limited computing capacity of TD, and the ratio of tasks completed on time decreases sharply as the increasement of number of tasks. In the scheme of [15], TD could offload at most one task to each ID. As the increasement of number of tasks, more and more tasks cannot be offloaded and have to be executed locally, and the performance of the scheme deteriorates gradually. In RS scheme, each task’s offloading decision is determined randomly and each ID could receive multiple tasks, which causes the performance of RS to be better than the scheme of [15] when TD has multiple tasks. There exists the case that too many tasks are executed on one device due to the randomness of RS, so the performance of RS is worse than MT-JCORA.Figure 3
Comparisons of ratios of tasks completed on time in various schemes.Figure4 depicts the TD’s total cost versus the number of TD’s tasks in MT-JCORA scheme, RS, ES, and the scheme in [15], respectively. As can be seen from Figure 4, the performance of MT-JCORA is the same as ES under different number of tasks, which is because MT-JCORA could search the optimal task offloading decision and corresponding NOMA-transmission time decision. It is worth noting that the time complexity of MT-JCORA algorithm is much lower than ES under multiaccess multitask scenario. In the scheme of [15], TD’s total cost subjects to the number of ID around, because each ID could receive at most one task from TD. What is more, the scheme in [15] is aimed at minimizing the energy consumption of user’s device without considering the time latency and offloading charge. MT-JCORA jointly consider time latency, energy consumption, and offloading charge and could take advantage of each ID’s computing resource, so the performance of the scheme in [15] is worse than MT-JCORA. RS allows user to offload multiple tasks to one ID; what is more, we have optimized the NOMA-transmission time for RS scheme. Although the performance of RS is not good as the scheme of [15] when TD has less tasks, it tends to become better than the scheme of [15] as the number of tasks increases.Figure 4
Comparisons of total cost in different schemes.Figure5 shows the energy consumption of TD versus the number of tasks in MT-JCORA scheme and the scheme in [15], respectively. As can be seen from Figure 5, the energy consumption in MT-JCORA scheme is greater than that in the scheme of [15] when TD has less tasks. MT-JCORA scheme jointly optimizes time latency, energy consumption, and offloading charge, but the scheme in [15] focuses on optimizing the energy consumption of TD, so the performance of MT-JCORA scheme is not good as the scheme in [15]. But the scheme in [15] allows TD offload to each ID at most one task, which means that the remaining tasks besides the offloaded ones should be executed locally, the energy consumption of TD will increase sharply due to the execution. Comparing with the scheme in [15], MT-JCORA could offload multiple tasks to one ID and efficiently take advantage of the idle computing resource of the nearby IDs. MT-JCORA allow TD to offload more than one task to a close ID to reduce transmission energy consumption; meanwhile, it can allow TD to offload more tasks to IDs to reduce task execution energy consumption. As the increasement of the number of TD’s tasks, the performance of MT-JCORA scheme trends to be better than the scheme in [15].Figure 5
Comparisons of energy consumption in various schemes.Figure6 shows the time latency for completing all tasks versus the number of TD’s tasks in our proposed MT-JCORA scheme and the scheme in [15], respectively. Here, we assume that the latency limitation of each task is 5 s. As can be seen from Figure 6, comparing with the scheme in [15], MT-JCORA could achieve lower time latency under different number of TD’s tasks. The scheme in [15] focuses on minimizing the energy consumption of TD without considering the time latency for completing all tasks. MT-JCORA is aimed at minimizing the weighted sum of time latency, energy consumption, and offloading charge. In MT-JCORA, TD could offload more tasks to the ID who has more idle computing resource to reduce the execution latency. Meanwhile, MT-JCORA makes the best of the channel status information between TD and IDs when making task offloading decision, which means that MT-JCORA could achieve shorter NOMA-transmission latency. Therefore, the performance of MT-JCORA is obviously superior to the scheme in [15].Figure 6
Comparisons of time latency in various schemes.Figure7 shows TD’s total cost versus the number of tasks in our proposed MT-JCORA scheme under different average energy consumption limitation Enmax of IDs. Here, the average energy consumption limitations of IDs are 3 J, 5 J, and 8 J, respectively. As can be seen from Figure 7, the total cost of TD tends to decrease as the average energy consumption limitation Enmax of IDs increases. The reason is that IDs could accept higher energy consumption when they have sufficient remaining battery, the corresponding energy price coefficients will be lower according to (12), and TD could offload tasks to IDs with less offloading charge. Meanwhile, the lower energy price coefficients of IDs will encourage TD to offload more tasks to IDs to save more execution energy.Figure 7
Comparisons of total cost in different average energy consumption limitations of ID.Figure8 depicts the TD’s total cost versus the number of tasks in our proposed MT-JCORA scheme under different average computing capacity fn of IDs. Here, the average computing capacity of IDs is 2 GHz, 3 GHz, and 4 GHz, respectively. It can be seen from Figure 8 that TD’s total cost tends to decrease as the average computing capacity fn of IDs increases. Even though the higher computing capacity fn will decrease the task execution latency, the energy price coefficient of ID will also increase. When the time latency coefficient α=0.3 and offloading charge coefficient γ=0.3, the influence of fn on offloading charge is greater than that on time latency according to (10)–(12). Therefore, when the average computing capacity of IDs increases, user’s total cost will increase too.Figure 8
Comparisons of total cost in different average computing capacity of IDs.Figure9 shows the performance advantage of our proposed NOMA-enabled computation offloading scheme compared with the frequency division multiple access- (FDMA-) based offloading scheme. In the FDMA-based scheme, TD equally divides its total channel bandwidth for different D2D links in order to offload tasks to multiple IDs simultaneously. For making fair comparison, the total transmission power in FDMA-based scheme is equal to that in our proposed NOMA-enabled scheme. Although there exists no cochannel interference among TD’s transmission to different IDs, the FDMA-based scheme yields a low spectrum efficiency in comparison with our proposed NOMA-enabled scheme. We test two cases in Figure 9, namely, the case 5IDs and 3IDs. The case 5IDs means that there exist five IDs nearby the TD. The case 3IDs means that there exist three IDs nearby the TD. As can be seen from Figure 9, no matter the number of IDs is 3 or 5, our proposed NOMA-enabled scheme can effectively reduce the total cost of user.Figure 9
Comparisons of our NOMA-enabled offloading and the FDMA-based scheme.


## 4.1. Parameter Setting

We evaluate the performance of our proposed algorithms by computer software MATLAB, and the simulation scenario is shown in Figure1. The parameters of simulation are given as follows according to [31, 32]. IDs are distributed randomly in the D2D communication coverage area of the user who has multiple tasks to execute. The number of IDs is 5. The maximum D2D communication coverage radius is 50 m. The channel bandwidth W is 20 MHz. The channel gains between user and IDs are given as h=kd−λ, where the path loss coefficient k is 0.001 and path loss exponent λ is 3.6. The input data size of each task varies from 2 to 5 MB, each task’s required CPU cycles varies from 1.5 to 4.5 gigacycles, and each task’s latency limitation randomly varies from 4 to 6 s. The computation capacity of each ID varies from 2 to 4 GHz. The computation capacity of local device is 2 GHz. The energy coefficient μ is 500 mJ/gigacycle. The energy consumption limitation of each ID is 5 J, and the value coefficients ηn of their user vary from 1 to 2 J/Hz. We set the delay coefficient α, energy consumption coefficient β, and offloading charge coefficient γ of user as 0.3, 0.4, and 0.3, respectively. Transmitting power limitation Pmax of local device is 1 W, and the noise power spectrum is -163 dBm/Hz. Parameters of Algorithm 2 are given as follows: g^=500, p^=100, q^=50, and m^=0.5.In order to evaluate the performance of the proposed MT-JCORA, we introduce other four methods in the same parameter setting for comparison.(i)
Random scheme (RS): each task selects the execution device randomly, and each ID could receive multiple tasks during one computation period(ii)
Exhaustive scheme (ES): exhaust all the possible task offloading decisions, and calculate user total cost under the corresponding optimal transmission time(iii)
Local scheme (LS): all the tasks are executed locally(iv)
Scheme in [15]: MT could offload multiple tasks to IDs around simultaneously, but each ID could receive at most one task


## 4.2. Simulation Results

Figure3 shows the ratio of tasks completed on time versus the number of TD’s tasks in our proposed MT-JCORA, RS, ES, LS, and the scheme in [15], respectively. As can be seen from Figure 3, the performance of MT-JCORA is basically the same as that of ES scheme, which is because MT-JCORA jointly consider all task’s latency limitation and could efficiently search the optimal task offloading decision. In LS scheme, all the tasks are executed in serial on TD. Some tasks cannot be completed within their latency limitation due to the limited computing capacity of TD, and the ratio of tasks completed on time decreases sharply as the increasement of number of tasks. In the scheme of [15], TD could offload at most one task to each ID. As the increasement of number of tasks, more and more tasks cannot be offloaded and have to be executed locally, and the performance of the scheme deteriorates gradually. In RS scheme, each task’s offloading decision is determined randomly and each ID could receive multiple tasks, which causes the performance of RS to be better than the scheme of [15] when TD has multiple tasks. There exists the case that too many tasks are executed on one device due to the randomness of RS, so the performance of RS is worse than MT-JCORA.Figure 3
Comparisons of ratios of tasks completed on time in various schemes.Figure4 depicts the TD’s total cost versus the number of TD’s tasks in MT-JCORA scheme, RS, ES, and the scheme in [15], respectively. As can be seen from Figure 4, the performance of MT-JCORA is the same as ES under different number of tasks, which is because MT-JCORA could search the optimal task offloading decision and corresponding NOMA-transmission time decision. It is worth noting that the time complexity of MT-JCORA algorithm is much lower than ES under multiaccess multitask scenario. In the scheme of [15], TD’s total cost subjects to the number of ID around, because each ID could receive at most one task from TD. What is more, the scheme in [15] is aimed at minimizing the energy consumption of user’s device without considering the time latency and offloading charge. MT-JCORA jointly consider time latency, energy consumption, and offloading charge and could take advantage of each ID’s computing resource, so the performance of the scheme in [15] is worse than MT-JCORA. RS allows user to offload multiple tasks to one ID; what is more, we have optimized the NOMA-transmission time for RS scheme. Although the performance of RS is not good as the scheme of [15] when TD has less tasks, it tends to become better than the scheme of [15] as the number of tasks increases.Figure 4
Comparisons of total cost in different schemes.Figure5 shows the energy consumption of TD versus the number of tasks in MT-JCORA scheme and the scheme in [15], respectively. As can be seen from Figure 5, the energy consumption in MT-JCORA scheme is greater than that in the scheme of [15] when TD has less tasks. MT-JCORA scheme jointly optimizes time latency, energy consumption, and offloading charge, but the scheme in [15] focuses on optimizing the energy consumption of TD, so the performance of MT-JCORA scheme is not good as the scheme in [15]. But the scheme in [15] allows TD offload to each ID at most one task, which means that the remaining tasks besides the offloaded ones should be executed locally, the energy consumption of TD will increase sharply due to the execution. Comparing with the scheme in [15], MT-JCORA could offload multiple tasks to one ID and efficiently take advantage of the idle computing resource of the nearby IDs. MT-JCORA allow TD to offload more than one task to a close ID to reduce transmission energy consumption; meanwhile, it can allow TD to offload more tasks to IDs to reduce task execution energy consumption. As the increasement of the number of TD’s tasks, the performance of MT-JCORA scheme trends to be better than the scheme in [15].Figure 5
Comparisons of energy consumption in various schemes.Figure6 shows the time latency for completing all tasks versus the number of TD’s tasks in our proposed MT-JCORA scheme and the scheme in [15], respectively. Here, we assume that the latency limitation of each task is 5 s. As can be seen from Figure 6, comparing with the scheme in [15], MT-JCORA could achieve lower time latency under different number of TD’s tasks. The scheme in [15] focuses on minimizing the energy consumption of TD without considering the time latency for completing all tasks. MT-JCORA is aimed at minimizing the weighted sum of time latency, energy consumption, and offloading charge. In MT-JCORA, TD could offload more tasks to the ID who has more idle computing resource to reduce the execution latency. Meanwhile, MT-JCORA makes the best of the channel status information between TD and IDs when making task offloading decision, which means that MT-JCORA could achieve shorter NOMA-transmission latency. Therefore, the performance of MT-JCORA is obviously superior to the scheme in [15].Figure 6
Comparisons of time latency in various schemes.Figure7 shows TD’s total cost versus the number of tasks in our proposed MT-JCORA scheme under different average energy consumption limitation Enmax of IDs. Here, the average energy consumption limitations of IDs are 3 J, 5 J, and 8 J, respectively. As can be seen from Figure 7, the total cost of TD tends to decrease as the average energy consumption limitation Enmax of IDs increases. The reason is that IDs could accept higher energy consumption when they have sufficient remaining battery, the corresponding energy price coefficients will be lower according to (12), and TD could offload tasks to IDs with less offloading charge. Meanwhile, the lower energy price coefficients of IDs will encourage TD to offload more tasks to IDs to save more execution energy.Figure 7
Comparisons of total cost in different average energy consumption limitations of ID.Figure8 depicts the TD’s total cost versus the number of tasks in our proposed MT-JCORA scheme under different average computing capacity fn of IDs. Here, the average computing capacity of IDs is 2 GHz, 3 GHz, and 4 GHz, respectively. It can be seen from Figure 8 that TD’s total cost tends to decrease as the average computing capacity fn of IDs increases. Even though the higher computing capacity fn will decrease the task execution latency, the energy price coefficient of ID will also increase. When the time latency coefficient α=0.3 and offloading charge coefficient γ=0.3, the influence of fn on offloading charge is greater than that on time latency according to (10)–(12). Therefore, when the average computing capacity of IDs increases, user’s total cost will increase too.Figure 8
Comparisons of total cost in different average computing capacity of IDs.Figure9 shows the performance advantage of our proposed NOMA-enabled computation offloading scheme compared with the frequency division multiple access- (FDMA-) based offloading scheme. In the FDMA-based scheme, TD equally divides its total channel bandwidth for different D2D links in order to offload tasks to multiple IDs simultaneously. For making fair comparison, the total transmission power in FDMA-based scheme is equal to that in our proposed NOMA-enabled scheme. Although there exists no cochannel interference among TD’s transmission to different IDs, the FDMA-based scheme yields a low spectrum efficiency in comparison with our proposed NOMA-enabled scheme. We test two cases in Figure 9, namely, the case 5IDs and 3IDs. The case 5IDs means that there exist five IDs nearby the TD. The case 3IDs means that there exist three IDs nearby the TD. As can be seen from Figure 9, no matter the number of IDs is 3 or 5, our proposed NOMA-enabled scheme can effectively reduce the total cost of user.Figure 9
Comparisons of our NOMA-enabled offloading and the FDMA-based scheme.


## 5. Conclusion

In this paper, we investigate the problem of multitask computation offloading and resource allocation in NOMA-enabled D2D communication system. We aim to minimize the total cost of MT for completing all tasks, which is the weighted sum of time latency, energy consumption, and offload charge. For the formulated mixed integer nonlinear programming problem, we use decomposition approach to solve it and propose a novel two-layer scheme named MT-JCORA. In the inner layer, we consider a given task offloading decision and formulate the NOMA-transmission time allocation optimization problem, which is proved as a strictly convex problem, and we propose a corresponding algorithm based on convex theory to solve it. In the outer layer, using the proposed algorithm as the basis, we study the task offloading decision to further minimize the MT’s total cost. Considering the complexity of problem in multiaccess multitask offloading scenario, we design a heuristic algorithm based on GA algorithm to obtain the optimal task offloading decision. Numerical results show that our proposed scheme can effectively reduce the total cost of users compared with related schemes. In the future, we will consider the scenario of multiple users with multiple tasks and investigate a better transmission scheme to further reduce the time latency.



---

*Source: 5349571-2022-07-28.xml*