A multi-user multi-operator computing pricing method for Internet of things based on bi-level optimization

Abstract

The Internet of mobile things is a promising paradigm that generates, stores, and processes amount of real-time data to render rich services for mobile users. Along with the increase of mobile devices in the field of Internet of things, more and more intelligent applications, such as face recognition and virtual reality, have emerged. These applications typically consume large amounts of computing and energy resources. However, due to the physical size limitations of Internet of things terminals, their computing capacity and power are limited, where users’ needs for application processing delay and power consumption cannot be met. Therefore, the concept of edge cloud computing has been proposed, which enhances the computing capacity of Internet of things terminals by offloading user tasks to edge servers for computation. When there are multiple operators, it is important to understand how users choose an operator to perform computation and how operators can reasonably price the computing capacity to meet their own interests. Therefore, we study the computation pricing and user decision-making problems of Internet of things under multi-user and multi-operator scenarios. The problem is divided into three phases and modeled as a two-level optimization problem. While an operator’s goal is to minimize the loss of his interests, the user’s goal is to minimize the computation cost (energy consumption and price). First, since the lower-level user decision-making problem is an integer linear programming problem, we transform it into an equivalent continuous linear programming problem by relaxation. Second, we transform the bi-level optimization problem into an equivalent single-level optimization problem by substituting the lower problem’s Karush–Kuhn–Tucker conditions into an upper problem. Finally, we use a spatial branch and bound algorithm to solve the problem. Experimental results show that the proposed algorithm can effectively maintain the benefits of both operators and users in the field of Internet of things.

Keywords

Internet of things computation offloading data offloading edge computing bi-level optimization

Introduction

In the recent years, the Internet of mobile things is a burgeoning technique that generates, stores, and processes amount of real-time data to render rich services for users. It has been widely used in every corner of our daily lives, including environmental, industrial, and medical fields. Along with the increase of various mobile devices (MDs) in the field of Internet of things (IoT), more and more new applications, such as face recognition and natural language processing, have emerged and have attracted people’s attention. Such mobile applications are often resource-intensive, which require a great deal of intensive computing, and will generate higher energy consumption. However, due to the physical size limitations of the terminals of IoT, their computing resources and battery life are limited. The contradictory relationship between resource-hungry applications and resource-constrained MDs poses significant challenges to the development of Internet of mobile things.^1,2

To address the above challenges, the concept of mobile cloud computing (MCC) has been proposed, which aims to enhance the ability of the terminals of IoT to handle resource-intensive applications by uploading the user’s computing tasks to a resource-rich remote public cloud. However, due to the distance between the users and the public cloud, a long delay will occur when performing wireless transmission, which could have a significant impact on interactive applications. To alleviate this issue, the concept of edge cloud computing^3,4 has been proposed, which provides cloud computing functionalities at the edges of wireless access networks in the vicinity of mobile users to enhance the computing power of IoT, decreasing processing delays and energy consumption of the MDs. In this way, large-scale resource-rich cloud infrastructures deployed by operators around users could enable users to make fast and low-latency connections to meet the needs of interactive applications of IoT.^5–7

With the development of edge computing technologies, operators deploy a large number of edge servers around users to provide computation offloading services. Under multi-user multi-edge server scenarios, different users can dynamically select which edge servers to offload based on their device status and servers’ computing price. At the same time, to make more profit, the edge server will adjust the price and service accordingly, to attract more users. Consequently, how to optimize user decisions and edge server pricing to minimize user’s computation cost while maximizing edge server’s revenue is particularly important in the field of IoT.^8,9 Therefore, we study a multi-user multi-edge server computing offloading method for economic benefit in this article.

Related work

The prior research work is summarized as follows. Xing and Seferoglu¹⁰ proposed a prediction-based edge cloud computing framework. First, this framework dynamically predicted the power, computing capacity, and mobility of user equipment. Second, it optimized resource allocation and user decisions based on the predicted results and the delay constraints of the user computing tasks. Finally, the effectiveness of the proposed scheme was verified on an Android phone. Olaniyan et al.¹¹ proposed an opportunity edge computing framework that provided services to other users by motivating idle users to share computing capacity. Jeong et al.¹² studied the use of unmanned aerial vehicle (UAV) to provide users with computation offloading services. The objective was to maximize the computational rate of all users by jointly optimizing UAV trajectories, resource allocation, and computational task assignment. Since the problem was non-convex, the authors proposed a two-stage optimization algorithm based on successive convex approximation (SCA) to solve the problem. Sardellitti et al.¹³ considered a multi-user multi-cell computation offloading system that jointly allocated radio and computing resources to minimize mobile energy consumption under offload delay constraints. Besides, in literature,^14–16 the profits of users were modeled using various metrics. However, the benefits of clouds were not considered by above the research works.

Therefore, considering the coexistence of central and edge clouds, the optimal user scheduling for offloading to different clouds was studied by Zhao et al.¹⁷ In addition, distributed multi-user computation offloading was designed using game theory in Chen et al.¹⁸ for energy and delay minimization. Zhang et al.¹⁹ developed an optimal unloading algorithm based on the Markov decision process (MDP) model for MDs in intermittently connected cloud systems, with the goal of minimizing computing costs. Zhang et al.¹⁹ considered the problem of maximizing the profit of the cloudlet management platform and introduced a new stochastic control algorithm to optimize the computing resource allocation and user decisions. In the work by Fang et al.,²⁰ an incentive compatible auction mechanism (ICAM) for resource transactions between MDs (buyers) and cloudlets (sellers) was proposed, which can effectively allocate cloudlets to meet the service requirements of MDs. Jin et al.²¹ studied the pricing policies of multiple cloud service providers (CSPs) in the MCC market and designed an algorithm to derive low complexity prices. However, they had only considered the problem with the price of homogeneous clouds, which was not practical in mobile edge computing scenarios, including edge clouds and remote clouds. Feng et al.²² studied the pricing strategy of CSPs based on computing resources, but they failed to further analyze how the amount of computing resources affects the profit of CSP.

Although the above work has carried out detailed research on computation offloading, little work studied the user decision and the edge server pricing problem in multi-user multi-edge server scenarios jointly. Therefore, we study the computation offloading problem in a multi-user multi-edge server scenario with the objective of minimizing user computing costs and minimizing operator losses. The main work of this article is as follows:

We studied the computation offloading problem in a multi-user multi-edge server scenario, where the problem was divided into three phases and modeled as a bi-level optimization problem. While the edge server optimization problem is the upper-level problem, which is considered as a continuous linear programming problem; the user optimization problem is the lower-level problem, which is considered as an integer linear programming problem.

We transformed the equivalent of the lower integer programming problem into a continuous integer programming problem, so that it can obtain the optimal solution in polynomial time. Then, we replaced the lower-level problem with its KKT condition and added it into the upper-level problem, thus transforming the original bi-level optimization problem into an equivalent single-level optimization problem.

Since the single-level optimization problem after transformation is non-convex, we used a spatial branch and bound algorithm to solve it. The experimental results showed that the proposed scheme can effectively maintain the benefits of operators and users.

Multi-user multi-operator bi-level optimization model

We consider the problem of computing task pricing under a multi-user multi-edge server scenario. Assume that there are a number of users, and each user device has only one radio. At the same time, there are numerous edge servers, and the computing capacity of the edge server is limited. Each user has a task, which can be partitioned into separate subtasks.^23,24 Each subtask can select one edge server for computing. Assume that the bandwidth allocation between users is frequency division multiplexing;²⁵ that is, the communication between users does not interfere with each other. The goal of the user is to minimize the cost, and the goal of the edge server is to minimize the loss of benefits. The specific process can be divided into the following three stages:

Phase 1: The edge servers announce the unit price of computing capacity;

Phase 2: Users choose to perform computing on a particular edge server according to the unit price;

Phase 3: Servers adjust the unit price according to users’ choices to achieve the goal of minimizing the loss, and then the first and second phases repeat until the result no longer changes.

User decision

Assume that the user collection is $I = {1, 2, \dots, N}$ , and the user’s subtask collection is $J_{i} = {1, 2, \dots K_{i}}$ . Also, assume that the edge server collection is $S = {1, 2, \dots, M}$ . $j = m (m > 0)$ represents the user on the $m$ edge server for computing. $a_{ijk}$ represent whether user i’s subtask $k$ is calculated on the server $j$ which is decided by the users. If the computation is done on the server, we have $a_{ijk} = 1$ , otherwise, $a_{ijk} = 0$ . Since a subtask can only be computed on one server, we have the following constraints

a_{ikj} \in {0, 1}

(1)

\sum_{j = 1}^{M} a_{ikj} = 1

(2)

The time that user $i$ uploads subtask $k$ to $j$ is given as

T_{ikj}^{(u)} = \frac{B_{ik}^{(u)}}{C_{i}^{(u)}}

(3)

where $B_{ik}^{(u)}$ represents the data that user $i$ needs to upload for subtask $k$ , and $C_{i}^{(u)}$ represents the bandwidth allocated to user $i$ .

Since the amount of data calculated by the task is very small,³ this article ignores the user’s download power consumption. Then, the energy required by user $i$ to compute subtask $k$ at edge server $j$ is equal to the communication energy consumption $E_{ikj}^{(c)}$ generated by uploading data. Therefore, we have the following equation

E_{ikj}^{(c)} = h_{ij} p_{i} T_{ikj}^{(u)}

(4)

where $P_{i}$ represents the transmit power of user $i$ and $h_{ij}$ represents the sensitivity of user $i$ to the services provided by edge server $j$ .¹⁸ The total energy consumption $E_{i}^{(c)}$ of the user computing task at the edge server is equal to the sum of the energy consumption of each subtask. Then, we have

E_{i}^{(c)} = \sum_{k = 1}^{K_{i}} \sum_{j = 1}^{M} a_{ikj} E_{ikj}^{(c)}

(5)

The total cost $Y_{ij}$ that user $i$ needs to pay for computing task $k$ at edge server $j$ is equal to the price of the unit CPU cycle multiplied by the number of CPU cycles required for task $k$ . Then, we have the following equation

Y_{ikj} = σ_{j} G_{ik}

(6)

where $σ_{j}$ represents the price per unit CPU cycle provided by the edge server $j$ , which is decided by the edge servers. And $G_{ik}$ denotes the CPU cycles required for computing task $k$ .

The total cost $Y_{i}$ that user $i$ needs to pay in the cloud computing task is equal to the sum of the costs generated by each edge server calculation, so we have

Y_{i} = \sum_{k = 1}^{K_{i}} \sum_{j = 1}^{M} b_{ij} a_{ikj} Y_{ikj}

(7)

where $b_{ij}$ represents the price sensitivity coefficient of $i$ to edge server $j$ . The user needs to consider both the energy cost and the price cost when computing. Because the user’s needs are different, two weights $α, β$ and $b$ are set to meet the needs of different users. Then, the computation cost $ϕ_{i}$ of user $i$ is given as

ϕ_{i} = α_{i} E_{i}^{(c)} + β_{i} Y_{i}

(8)

Substituting constraints (3)–(7) into equation (8), the expression of $ϕ_{i}$ can be rewritten as

ϕ_{i} = α_{i} \sum_{k = 1}^{K_{i}} \sum_{j = 1}^{M} (a_{ikj} E_{ikj}^{(c)}) + β_{i} \sum_{k = 1}^{K_{i}} \sum_{j = 1}^{M} (a_{ikj} σ_{j} G_{ik})

(9)

At the same time, because the edge server has limited computing resources, the maximum number of tasks can be served is also limited, so we have the following constraint

\sum_{i = 1}^{N} \sum_{k = 1}^{K_{i}} a_{ikj} \leq τ_{j}

(10)

The objective of users is minimize the total cost, so we have following problem P0

\begin{matrix} P 0 : min \sum_{i = 1}^{N} ϕ_{i} \\ s . t . (1), (2), (10) \end{matrix}

(11)

Operator computation pricing

Compared with a single edge server, an over-bid edge server will result in no users choosing to use its services when multiple edge servers provide computing services. As a result, edge services will reduce prices to attract more users. This will lead to a loss of profit to the edge server, so the edge server aims at minimizing benefit losses. The edge server price adjustment strategy is as follows: when too many users select the same edge server, it indicates that its bid is lower than other servers, so the operator will increase the unit price to increase revenue. When an edge server has few user choices, it indicates that its bid is higher than other servers, so operators will lower the unit price to attract more users.

Assuming that the initial price of the edge server $j$ is $θ_{j}$ , and the total loss of the edge server $j$ is equal to the unit price loss multiplied by the sum of the task’s required CPU cycles. Therefore, we have the following equation

z_{j} = \sum_{i = 1}^{N} \sum_{k = 1}^{K_{i}} (a_{ikj} G_{ik} (θ_{j} - σ_{j}))

(12)

where $z_{j}$ represents the loss of edge server $j$ . Therefore, the revenue maximization problem of all edge servers can be expressed as the following problem P1

\begin{matrix} P 1 : min \sum_{j = 1}^{M} z_{j} \\ s . t . 0 < σ_{j} \leq θ_{j} \end{matrix}

(13)

In problem P1, the decision variable is $σ_{j}$ .

The computation pricing problem under the above multi-user multi-edge server scenario is formulated as a bi-layer optimization problem.^26–28 The problem of minimizing the overall benefit loss of an edge server is P1, which is the upper-level optimization problem, and the user’s overall cost minimization problem P0 is the lower-level optimization problem.

Since problem P0 contains integer variables and all expressions are linear, problem P0 is a linear integer programming problem. Similarly, problem P1 is a linear programming problem. Therefore, problem P0 and problem P1 constitute a bi-layer optimization problem in which the upper level is continuously linear and the lower level is integer linear.

Discrete continuous bi-level optimization problem analyze

Since problem P0 is an NP-hard problem, there is currently no effective solution method to obtain its optimal solution in polynomial time. Therefore, we relax a set of integer variables $a$ into a set of continuous variables

0 \leq a_{ikj} \leq 1

(14)

Then, the integer linear programming problem P0 can be transformed into the following continuous linear programming problem P2

\begin{matrix} P 2 : min \sum_{i = 1}^{n} ϕ_{i} \\ s . t . (3 - 1), (3 - 2), (3 - 9) \end{matrix}

(15)

Problem P2 is a continuous linear programming problem that can be solved in polynomial time using many classical algorithms. Next, we will prove that P0 and P2 have the same optimal solution. Before the proof is given, the following definitions needed to be introduced.

Definition 1

If matrix $A \in R^{m \times n}$ is an integer matrix, $r \equiv rank A = min {m, n}$ and all $r \times r$ non-zero minor of $A$ are equal to 1 or -1, then $A$ is called a unimodular matrix.²⁹

Definition 2

If matrix $A$ is a model matrix and its minors are all equal to 0, 1, or −1, then $A$ is called a totally unimodular matrix.²⁹

According to literature,^30,31 we can rewrite problem P2 into following standard form

\begin{matrix} P 2 : min_{x} C_{x} \\ S . t . Ax \leq c \end{matrix}

(16)

in which matrix $C$ denotes the coefficient matrix of objective function, and matrix $A$ denotes the coefficient matrix of constraints.

Lemma 1

The coefficient matrix of P2’s constraints is a totally unimodular matrix.

Proof

Matrix $A$ and vector $c$ can be rewritten as

A = (\begin{matrix} 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 & 0 & 1 & \dots & 0 & 0 & 1 & \dots & 0 \\ ⋱ & ⋱ & ⋱ \\ 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & \dots & 1 & 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 & 1 & 1 & \dots & 1 & 0 & 0 & \dots & 0 \\ ⋱ & ⋱ & ⋱ \\ 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 & 1 & 1 & \dots & 1 \end{matrix})

(17)

c = [n_{1}, n_{2}, \dots, n_{NMK},]^{T}

(18)

where $n_{1}$ , $n_{2}$ , …, $n_{NMK}$ are constants. We can observe that all the minors of matrix $A$ are equal to 0 or 1. Therefore, matrix $A$ is totally unimodular matrix. ■

Lemma 1

The solution of problem P2 is integer.

Proof

According to the proof of Lemma 1, matrix $A$ is a totally unimodular matrix, and the values of vectors $c$ are all equal to 1. If the constraints coefficient matrix of a linear program problem is a totally unimodular matrix, then all its vertex solutions are integer.³² Meanwhile, if a linear matrix has an optimal solution, then at least one optimal solution at the vertices of the polyhedral feasible domain is defined by its constraints.³³ Therefore, the solution of problem P2 is an integer. ■

Theorem 1

Problems P0 and P2 have the same optimal solution.

Proof

The optimal solution of problem P0 is an integer, and problem P2 is obtained by slacking the integer variable of problem P0. According to Lemma 2, the optimal solution of problem P2 is also an integer. Therefore, the optimal solution of problem P0 and problem P2 is the same. ■

Thus, the optimal solution to problem P0 can be reached in the polynomial time. Since problem P0 is equivalent to problem P2, a bi-level optimization problem in which the upper level is problem P1 and the lower level is problem P2 is obtained. From literature,^34,35 it can be seen that even the bi-level liner optimization problem is hard to solve. And the most effective method for solving such problem is to transform it into a single-level problem.

Since the lower-level problem P2 is a continuous linear programming problem, its optimal value can be obtained using KKT conditions. Therefore, we can substitute its KKT condition into the upper-level problem P1 and get a single-level problem.

The Lagrange function of P2 is as follows

\begin{matrix} L (a, λ, u, v) = \sum_{i = 1}^{N} ϕ_{i} + \sum_{i = 1}^{N} \sum_{k = 1}^{K_{i}} λ_{ik} (\sum_{j = 1}^{M} a_{ikj} - 1) \\ \sum_{i = 1}^{N} \sum_{k = 1}^{K_{i}} \sum_{j = 0}^{M} \\ u_{ikj} a_{ikj} + \sum_{i = 1}^{N} \sum_{k = 1}^{K_{i}} \sum_{j = 0}^{M} v_{ikj} (a_{ikj} - 1) \end{matrix}

(19)

Then, its KKT conditions are given as follows

\begin{matrix} α_{i} h_{ij} E_{ikj}^{(c)} + β_{i} b_{ij} σ_{j} G_{ik} + λ_{ik} - u_{ikj} + v_{ily} = 0 \\ \forall i \in I, k \in J_{i}, j \in {1, 2, \dots, M} \end{matrix}

(20)

\sum_{j = 1}^{M} a_{ikj} - 1 = 0, \forall i \in I, k \in J_{i}

(21)

a_{ikj} \geq 0, \forall i \in I, k \in J_{i}, j \in S

(22)

a_{ikj} \leq 1, \forall i \in I, k \in J_{i}, j \in S

(23)

u_{ikj} a_{ikj} = 0, \forall i \in I, k \in J_{i}, j \in S

(24)

v_{ikj} (a_{ikj} - 1) = 0, \forall i \in I, k \in J_{i}, j \in S

(25)

v_{ikj} \geq 0, \forall i \in I, k \in J_{i}, j \in S

(26)

u_{ikj} \geq 0, \forall i \in I, k \in J_{i}, j \in S

(27)

By substituting constraints (20)–(27) into problem P1, we can obtain the following single-level optimization problem P3

\begin{matrix} P 3 : min \sum_{j = 1}^{M} z_{j} \\ s . t . (3 - 20) - (3 - 27) \\ 0 < σ_{j} \leq θ_{j} \end{matrix}

(28)

Since constraints (24) and (25) are non-convex, P3 is a non-convex problem.

The spatial branch and bound algorithm based on cut plane

We solve P3 using the spatial branch and bound algorithm.³⁶

Spatial branch and bound is a deterministic algorithm for solving global optimal problems for non-convex nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) problems. It is a kind of branch and bound method, but it can recursively decompose nonlinear functions into simple functions compared with the traditional branch and bound algorithm, so it can deal with non-convex problems to achieve the global optimal target.

The main idea of the spatial branch and bound algorithm is to segment the feasible domain of the variable and then to solve the upper and lower bounds of the function in each feasible domain to find an approximate solution sequence that can converge to the optimal solution. First, the algorithm decomposes the original non-convex problem and the convex relaxation to obtain the subproblem and the upper and lower bounds of the original problem. Second, in each iterative solution process, the algorithm performs convex relaxation on each non-convex subproblem to obtain the upper and lower bounds of the optimal solution of the objective function. Whether the upper and lower bounds finally converge, it indicates that the global optimal solution is found. Otherwise, if the upper and lower bounds do not satisfy a certain threshold, the algorithm continues to divide the feasible domain of the variable to obtain a smaller subproblem. If the subproblem does not produce a better upper and lower bound, the algorithm will prune it. The above process will be repeated until the global optimal solution to the original problem is found.

Assume that there are $N$ integer variables, the algorithm will go through all possible values for getting the optimal solution, and the time complexity can be calculated as $O (2^{N})$ . Besides, assume that the time complexity for solving convex problem is $O (M)$ , where $M$ is a constant. Therefore, the complexity of proposed algorithm is $O (2^{N} M)$ .

However, it should be noted that in the solution process of the algorithm, the space cutting plane can be used to reduce a large number of branches, thereby improving the running speed of the algorithm. As depicted above, the algorithm goes through all possible values of variables, and optimal solution can eventually be calculated, which denotes that the algorithm will eventually converge to the optimal solution.^37,38

The details are shown in Algorithm 1. Before that, we need to introduce following concepts: the original non-convex problem P3, the relaxation problem $SP$ of the original problem, the optimal value $U_{opt}$ of the original problem, the upper bound $UB$ of the original problem and its lower bound $LB$ , the sub-feasible domain $S_{j}$ of the problem, the original problem, and the optimal solution $a^{*}$ and $σ^{*}$ .

Algorithm 1. Spatial branch and bound for solving $P$ 3
1: $Initialize :$ set threshold $ρ = 0.01$ , optimal value $U_{opt} = + \infty$ , set sub-feasible domain $S_{j}$ as P3s all feasible domains.
2: Output: the optimal value $U_{opt}$ of the original problem and its corresponding optimal solutions $a^{}$ and $σ^{}$
3: while at least one $S_{j}$ is not traveled do
4: Select the sub-feasible domain $S_{j}$ and perform convex relaxation on problem P3 (convex hull or linearize the nonlinear term) to obtain the relaxation subproblem $SP$ ;
5: Step 3: solving the relaxation subproblem $SP$ in the feasible domain $S_{j}$ obtaining the lower bound $L B_{j}$ of problem P3 on a and the corresponding optimal solutions $a_{j}^{L}$ and $σ_{j}^{L}$
6: if $L B_{j} > U_{opt}$ then
7: goto step 3
8: else
9: Solving P3 on the feasible domain $S_{j}$ , obtaining its upper bound $U B_{j}$ and the corresponding optimal solutions $a_{j}^{U}$ and $σ_{j}^{U}$
10: if $U B_{j} > U_{opt}$ then
11: go to step 3
12: else
13: Set $U_{opt} = U B_{j}, a^{} = a_{j}^{U}, σ^{} = σ_{j}^{U}$
14: Cut the branch that $LB > UB$
15: if $L B_{j} - U B_{j} \leq ρ$ then
16: Continue
17: else
18: Divide current domain $S_{j}$ into sub-domains, go to step 3
19: end if
20: end if
21: end if
22: end while
Output: the optimal value $U_{opt}$ of the original problem and its corresponding optimal solutions $a^{}$ and $σ^{}$ .

Simulation results

In this section, the proposed method for solving multi-user multi-operator computing pricing and the user decision-making problem is verified. First, we introduce the experimental environment and other settings. Second, we study the impact of different parameters on user decision-making. Finally, we study the impact of different parameters on operator revenue and the overall system cost and verify the effectiveness of the proposed scheme.

Simulation settings

Assume that there are $N = 20$ users, each user has $K_{i} = 3$ subtasks, and each subtask of a user can only select one edge server for computing. Assuming that the user is performing an application for face recognition, the size needed for each subtask to be uploaded is 5000 KB, and the number of CPU cycles to be computed is 1 GHz.¹⁸ At the same time, assuming that there are $M = 4$ edge servers, the system bandwidth is 20 MHz.³⁹ In order to facilitate the verification and statistics of the experimental results, the users are divided into four categories according to service sensitivity and price sensitivity. Among them, users 1–5, 5–10, 11–15, and 16–20 are groups with different sensitivity coefficients. Like the previous research works,^40,41 specific parameters are shown in Tables 1 and 2.

Table 1.

Sensitivity coefficient $h_{ij}$ of users to edge servers.

	Server 1	Server 2	Server 3	Server 4
Users 1–5	0.5	0.8	0.34	0.63
Users 6–10	0.75	1.2	0.51	0.945
Users 11–15	1	1.6	0.68	1.26
Users 16–20	1.25	2	0.85	1.575

Table 2.

Price sensitivity coefficient $b_{ij}$ of users to edge servers.

	Server 1	Server 2	Server 3	Server 4
Users 1–5	0.42	0.59	1.01	0.93
Users 6–10	0.63	0.885	1.515	1.395
Users 11–15	0.84	1.18	2.02	1.86
Users 16–20	1.05	1.475	2.525	2.325

Assume that the number of tasks that each edge server can compute is 16, and that the user’s transmit power is 200 Mw.^42,43 If there is no special explanation, the user’s energy preference ratio and price preference ratio are set as 0.5 and 0.5, respectively. In addition, the initial prices of edge servers 1, 2, 3, and 4 are 50, 60, 70, and 80, respectively.

Analysis of simulation results

Figure 1 shows the number of served users with the different computing capacity of the servers. There are 20 users, so there are 60 subtasks. It can be seen that as the computing capacity of the servers increases, the number of users that are using servers 1, 2, and 3 are the same, but the number of users of server 4 is continuously decreasing. This is because server 4’s price is higher, and users will prefer the lower-priced servers in order to minimize their costs. Therefore, the user will select servers 1, 2, 3, and 4 in sequence. When servers 1, 2, and 3 are full, the user selects server 4, which produces the benefit of reducing its own cost.

Figure 1.

The number of served users with different computing capacities of servers.

Figure 2 shows the number of served users with different price sensitivities to server 4. The price sensitivities of all users to the edge server 4 are set to be the same, and the maximum number of users that the edge server can serve are 13, 26, 20, and 18, respectively. At the same time, the user’s preference for energy and price is set to 0, 1, which assumes that the user only cares about the impact of the price. It can be seen that when the sensitivity coefficient of the user to the edge server price 4 is 0.7, the number of users using the edge server 3 is small; that is, the user preferentially selects servers 1, 2, and 4 for computing. This is because the user’s price sensitivity to the edge server 3 is higher than that of other services at this time, resulting in a greater cost to the user using server 3. When the price sensitivity of the user to server 4 becomes 1, the number of users using edge server 3 is increased, the number of users using server 4 is lowered, and the number of users using server 3 is more than that of the users using 4. This is because the price sensitivity coefficients of the edge servers 3 and 4 are close, but the price of server 3 is low, so the price of server 3 is small, resulting in more users selecting server 3. Finally, when the sensitivity factor of server 4 rises to 1.3, its price is too high, resulting in no users using its services.

Figure 2.

The number of served users with different price sensitivities to server 4.

Figure 3 shows the number of served users with different unit prices of server 4. The maximum number of users that the edge server can serve is 15, 30, 18, and 24, and the price of the server is 50, 60, 70, and 40, respectively. At the same time, in order to study the impact of price on users, the energy and price preference ratios are set to 0 and 1, respectively. It can be seen that when the server price is 40, since the price of server 3 is high, the user selects servers 1, 2, and 4 for computing. When the price of server 4 becomes 60, the number of people who use it decreases, and the number of people who use server 2 increases. This is because the user has a lower price sensitivity coefficient to server 2, resulting in a lower price penalty for the user using server 2. As the price of server 4 rises to 8, it becomes the highest price among all servers. Therefore, some users choose server 3 for service, resulting in a decrease in the number of users and an increase in the number of users of server 3. This indicates that users will dynamically adjust their strategies according to the price changes of the server, so that their overall calculation cost is minimized.

Figure 3.

The number of served users with different unit price coefficients of server 4.

Figure 4 shows the number of served users with different energy and price coefficients. The maximum number of service providers for edge servers is 13, 26, 29, and 19, and the price of edge servers is 50, 60, 60, and 70, respectively. It can be seen that when the user energy and price preference coefficients are 1 and 0, respectively, that is, the user only cares about the energy cost, the user does not select server 2. The number of users of server 4 is 18, indicating that the user will choose servers 1, 3, and 4. This is because users have the highest sensitivity coefficient to the edge server 2, and in the case of the same energy consumption, the user prefers to use other servers. When the user energy and price preference become 0.5 and 0.5, the number of users using server 4 becomes 0, and some users start to use server 2. Similar to the above reasons, this switch is because the weighting cost of server 4 and the price are too high, causing the user to select another server. Similarly, when the user only cares about the price, the price of the server and the sensitivity coefficient of the user together determine the decision of which servers to use. Compared with Chen et al.,¹⁸ both price and energy sensitivities are considered. However, Chen et al.¹⁸ only considered the profit of users.

Figure 4.

The number of served users with different energy and price coefficients.

Figure 5 shows the overall user cost with different numbers of users and different computing size of tasks. It can be seen that as the number of users increases, the overall user cost also increases, and the rate of increase gradually increases. This is because the transmission resources in the system are limited. When the number of users increases, the bandwidth allocated by each user decreases accordingly, further causing the transmission rate to become smaller, the transmission delay to be longer, and the transmission energy consumption to increase. As the overall cost of users increases, operators need to be reasonably priced to attract more users, while making their own higher returns. This further demonstrates the need to study both issues simultaneously. At the same time, it can be seen that the larger the size of user tasks, the greater the overall cost for users.

Figure 5.

Overall users cost with different number of users and different computing size of tasks.

Figure 6 shows the operator loss with different numbers of users and different required CPU cycles of tasks. It can be seen that the more the users are, the greater the operator’s loss, because the operator provides a discount for each user, and the overall loss increases. In fact, although operators lose more, their revenues continue to increase, because the more the users are, the more the operators earn; the benefits are proportional to the number of users, and the losses are relatively small compared to the income. At the same time, it can be seen that when the number of users reaches 25, the growth rate suddenly becomes faster. This is because when the number of users increase, the competition of operators becomes more intense. Operators need to provide more discounts to attract users, resulting in faster loss growth, but their overall income is still increasing.

Figure 6.

Operator loss with different number of users and different required CPU cycles of tasks.

Figure 7 shows the overall user cost with different numbers of users and different required CPU cycles of tasks. Similar to Figure 5, the overall user cost increases as the number of users increases. At the same time, it can be seen that the more CPU cycles are required of user tasks, the greater the overall cost of users. This is because the cost that the user needs to pay is related to the CPU cycle consumed by the user. Therefore, the more CPU cycles, the greater the computational cost of the user, further leading to an overall user cost. The conclusion is consistent with the work by Feng et al.⁴⁴

Figure 7.

Overall user cost with different number of users and different required CPU cycles of tasks.

Conclusion

While the edge server optimization problem is the upper-level problem, which is considered as a continuous linear programming problem, the user optimization problem is the lower-level problem, which is considered as an integer linear programming problem.

We study the computation offloading problem of IoT under a multi-user multi-edge server scenario, with the goal of minimizing user computational cost and edge server loss. We divide the problem into three phases and model it as a bi-level optimization problem. While the edge server optimization problem is the upper-level problem and it is considered as a continuous linear programming problem, the user optimization problem is a lower-level problem and is considered as an integer linear programming problem, which is hard to solve. Therefore, the equivalent of the lower integer programming problem is transformed into a continuous linear programming problem, so that it can obtain the optimal solution in polynomial time. Then, we replace the lower-level problem with its KKT conditions and bring it into the upper-level problem, thus transforming the original multi-user multi-operator bi-level optimization problem into an equivalent single-level optimization problem. Since the single-level optimization problem after transformation is non-convex, we use the spatial branch and bound algorithm to solve it. The experimental results show that the proposed algorithm can effectively guarantee the benefits of both operators and users in the field of IoT.

In future, to deal with more complex scenorios, the subtask of each user will be considered to be not equal and the sizes of users in the groups are different.

Footnotes

Handling Editor: Vishal Sharma

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Natural Science Foundation of China (no. 61502118), the National Science and Technology Major Project of China (no. 2016ZX03001023-005), and the Natural Science Foundation of Heilongjiang Province in China (no. F2016009).

ORCID iD

Wei Jiang

References

You

Zeng

Zhang

, et al. Resource management for asynchronous mobile-edge computation offloading. In: Proceedings of the 2018 IEEE international conference on communications workshops (ICC workshops), Kansas City, MO, 20–24 May 2018, pp.1–6. New York: IEEE.

Mir

Loreto

Cloud and edge computing. IEEE Commun Mag 2017; 1(4): 40–40.

Guan

Deng

Liu

, et al. Analysis of multiple clients’ behaviors in edge computing environment. IEEE T Veh Technol 2018; 67(9): 9052–9055.

Premsankar

Di Francesco

Taleb

Edge computing for the Internet of things: a case study. IEEE Internet Things 2018; 5(2): 1275–1284.

Xiang

Wang

. Oblivious transfer via lossy encryption from lattice-based cryptography. Wirel Commun Mob Com 2018; 5973285: 1–11.

Wang

. Achieving one-round password-based authenticated key exchange over lattices. IEEE T Serv Comput, 2019. DOI: https://dx-doi-org.web.bisu.edu.cn/10.1109/TSC.2019.2939836

Zhao

, et al. Efficient oblivious transfer construction via multiple bits dual-mode cryptosystem for secure selection in the cloud. J Chin Inst Eng 2019; 42(1): 97–106.

Wang

Zhang

Revisiting post-quantum hash proof systems over lattices for Internet of thing authentications. J Amb Intel Hum Comp. Epub ahead of print 11 November 2019. DOI: 10.1007/s12652-019-01529-2.

Sharma

You

Yim

, et al. BRIoT: Behavior Rule Specification-Based Misbehavior Detection for IoT-Embedded Cyber-Physical Systems. IEEE Access 2019; 7: 118556–118580.

10.

Xing

Seferoglu

Predictive edge computing with hard deadlines. In: Proceedings of the 2018 IEEE international symposium on local and metropolitan area networks (LANMAN), Washington, DC, 25–27 June 2018, pp.13–18. New York: IEEE.

11.

Olaniyan

Fadahunsi

Maheswaran

, et al. Opportunistic edge computing: concepts, opportunities and research challenges. Future Gener Comp Sy 2018; 89: 633–645.

12.

Jeong

Simeone

Kang

Mobile edge computing via a UAV-mounted cloudlet: optimization of bit allocation and path planning. IEEE T Veh Technol 2018; 67(3): 2049–2063.

13.

Sardellitti

Scutari

Barbarossa

Joint optimization of radio and computational resources for multicell mobile-edge computing. IEEE T Signal Inform Process Netw 2015; 1(2): 89–103.

14.

Liu

Zheng

Guo

Socially aware dynamic computation offloading scheme for fog computing system with energy harvesting devices. IEEE Internet Things 2018; 5(3): 1869–1879.

15.

Samanta

Chang

Adaptive service offloading for revenue maximization in mobile edge computing with delay-constraint. IEEE Internet Things 2019; 6(2): 3864–3872.

16.

Liu

Zheng

Guo

, et al. Multi-objective optimization for computation offloading in fog computing. IEEE Internet Things 2017; 5(1): 283–294.

17.

Zhao

Sheng

Guo

, et al. A cooperative scheduling scheme of local cloud and internet cloud for delay-aware mobile cloud computing. In: Proceedings of the 2015 IEEE GLOBECOM workshops (GC workshops), San Diego, CA, 6–10 December 2015. New York: IEEE.

18.

Chen

Jiao

, et al. Efficient multi-user computation offloading for mobile-edge cloud computing. IEEE/ACM T Network 2016; 24(5): 2795–2808.

19.

Zhang

Niyato

Wang

Offloading in mobile cloudlet systems with intermittent connectivity. IEEE T Mobile Comput 2015; 14(12): 2516–2529.

20.

Fang

Yao

Zhao

, et al. A stochastic control approach to maximize profit on service provisioning for mobile cloudlet platforms. IEEE T Syst Man Cy A 2018; 48(4): 522–534.

21.

Jin

Song

Zhuang

Auction-based resource allocation for sharing cloudlets in mobile cloud computing. IEEE T Em Top Comput 2018; 6(1): 45–57.

22.

Feng

Price competition in an oligopoly market with multiple IaaS cloud providers. IEEE T Comput 2014; 63(1): 59–73.

23.

Chen

Liang

Dong

Multi-user multi-task offloading and resource allocation in mobile cloud systems. IEEE T Wirel Commun 2018; 17(10): 6790–6805.

24.

Lin

Zhang

, et al. An optimal application partition algorithm for energy efficient computation offloading. Appl Mech Mater 2014; 687–691: 3516–3520.

25.

Xiong

Liu

Zhang

, et al. TDMA in adaptive resonant beam charging for IoT devices. IEEE Internet Things 2019; 6(1): 867–877.

26.

Zhang

Optimal joint bidding and pricing of profit-seeking load serving entity. IEEE T Power Syst 2018; 33(5): 5427–5436.

27.

Colson

Marcotte

Savard

An overview of bilevel optimization. Ann Oper Res 2007; 153(1): 235–256.

28.

Bard

JF.

Practical bilevel optimization: algorithms and applications. Berlin: Springer, 2013.

29.

Camion

Characterization of totally unimodular matrices. P Am Math Soc 1965; 16(5): 1068–1073.

30.

Xie

, et al. Energy efficient scheduling for iot applications with offloading, user association and BS sleeping in ultra dense networks. In: Proceedings of the 2018 16th international symposium on modeling and optimization in mobile, ad hoc, and wireless networks (WiOpt), Shanghai, China, 7–11 May 2018, pp.1–6. New York: IEEE.

31.

Vanderbei

RJ.

Linear programming. Berlin: Springer, 2015.

32.

Smith

DK.

Theory of linear and integer programming. J Oper Res Soc 1987; 38(6): 561.

33.

Berenstein

Gay

Complex variables: an introduction. New York: Springer, 2012.

34.

Colson

Marcotte

Savard

Bilevel programming: a survey. 4OR 2005; 3(2): 87–107.

35.

Zhang

Han

Fuzzy bi-level decision-making techniques: a survey. Int J Comput Int Syst 2016; 9(Suppl. 1): 25–34.

36.

Speakman

Lee

On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation. J Global Optim 2018; 72: 129–153.

37.

Pozo

Guillen-Gosalbez

Sorribas

, et al. A spatial branch-and-bound framework for the global optimization of kinetic models of metabolic networks. Ind Eng Chem Res 2014; 50(9): 5225–5238.

38.

Gopalakrishnan

Raghunathan

Nikovski

, et al. Global optimization of optimal power flow using a branch & bound algorithm. In: Proceedings of the 2012 50th annual Allerton conference on communication, control, and computing (Allerton), Monticello, IL, 1–5 October 2012, pp.609–616. New York: IEEE.

39.

Kumar

Liu

Y-H

, et al. A survey of computation offloading for mobile systems. Mobile Netw Appl 2013; 18(1): 129–140.

40.

Zhou

Dastjerdi

Calheiros

, et al. A context sensitive offloading scheme for mobile cloud computing service. In: Proceedings of the 2015 IEEE 8th international conference on cloud computing, New York, 27 June–2 July 2015. New York: IEEE.

41.

Jiang

Mao

Energy delay tradeoff in cloud offloading for multi-core mobile devices. IEEE Access 2017; 3: 2306–2316.

42.

Zhang

Liu

, et al. An energy-aware task offloading mechanism in multiuser mobile-edge cloud computing. Mob Inf Syst 2018; 2018: 7646705.

43.

Chen

Hao

Qiu

, et al. Mobility-aware caching and computation offloading in 5G ultra-dense cellular networks. Sensors 2016; 16(7): 974.

44.

Feng

, et al. A near-optimal cloud offloading under multi-user multi-radio environments. Peer Peer Netw Appl 2018; 12: 1454–1465.