Sage Journals: Discover world-class research

Abstract

Mobile edge computing has attracted great interests in the popularity of fifth-generation (5G) networks and Internet of Things. It aims to supply low-latency and high-interaction services for delay-sensitive applications. Utilizing mobile edge computing with Smart Home, which is one of the most important fields of Internet of Things, is a method to satisfy users’ demand for higher computing power and storage capacity. However, due to limited computing resource, how to improve efficiency of resource allocation is a challenge. In this article, we propose a hierarchical architecture in Smart Home with mobile edge computing, providing low-latency services and promoting edge process for smart devices. Based on that, a Stackelberg Game is designed in order to allocate computing resource to devices efficiently. Then, one-to-many matching is established to handle resource allocation problems. It is proved that the allocation strategy can optimize the utility of mobile edge computing server and improve allocating efficiency. Simulation results show the effectiveness of the proposed strategy compared with schemes based on auction game, and present performance with different changing system parameters.

Keywords

Mobile edge computing Smart Home Stackelberg game one-to-many matching computing resource allocation

Introduction

Imminent fifth-generation (5G) cellular networks are expected to play a major role in supporting Internet of Things (IoT) to achieve ubiquitous coverage, inherent security, high connectivity, and quality of service (QoS). It can provide unique advantages considering its widespread infrastructures already deployed on a large scale, and service reliability offered by a mature wireless standard with various technologies. Due to the limited existing spectrum and the need for high-speed data rates, 5G is expected to incorporate higher frequency spectra in the millimeter wavebands, such as 30 and 60 GHz.^1,2 However, with rapid extension, the IoT need computation and storage in proximity of sensors and actuators to support delay-sensitive and computation-intensive applications. According to Cisco Global Cloud Index Networking,³ data generated by various end devices are expected to reach 600 ZB (zettabyte) in 2020. Traditional IoT frameworks adopt cloud computing to deal with large torrent of data generated by all kinds of IoT devices. Generally speaking, large-scale data centers or cloud is built in remote areas far from edge terminals. These architectures perform poorly in real-time response, edge security, and edge processing, which is intolerable for IoT applications that require real-time response. Under this circumstance, mobile edge computing (MEC) is proposed as a critical solution to provide low-latency, fast-response, and high-interaction service for edge terminals.

As a new computing paradigm that combines Internet, computation, and storage at the edge of network, MEC has promising benefits.⁴ With multiple edge nodes, called access points (APs), deployed in the edge of network, MEC brings “cloud” to the edge. It can meet real-time requirements or achieve interactive behaviors of a large variety of new edge applications, as it is deployed much closer to edge terminals. Furthermore, MEC also relieves data congestion within core Internet and satisfies demands of devices for a higher computational power and storage capacity, allowing them to offload their tasks. It has been applied in many aspects of IoT. Hui et al.⁵ proposed a fog computing-based resolution framework to efficiently resolve the individuals identity. Su et al.⁶ developed an edge caching scheme in vehicular networks based on edge computing. Tang et al.⁷ designed a hierarchical distributed fog computing architecture to support data-intensive analysis in future smart cities.

Nevertheless, extending of MEC in Smart Home meets challenges caused by limited computation and bandwidth resources. Research suggests that Chinese market of Smart Home is expected to increase by 48% on average each year. With the demand for Smart Home increasing rapidly, it faces severe deficiency of bandwidth and wasting of computational resources. Definitely, it is established at home for a better life quality, combining technology and services through networking process.^8,9 Applications in the system can communicate with one another and provide instant services in different phenomenon, raising high standard for computational capability and bandwidth. Faced with these issues, improving resource allocation efficiency is inevitable in Smart Home. Therefore, this article discusses how to design effective resource allocation strategy based on MEC. To meet demands for low-latency services of delay-sensitive applications, APs are deployed near the Smart Home system, forming a three-layered architecture. Applications can utilize computational and storage resources of AP to conduct tasks. In addition, effective allocation strategy needs to be designed, aiming to satisfy requirements of more applications with limited resources.

In this article, we propose a strategy for computational resource allocation to improve performance of Smart Home system with MEC. A hierarchical architecture is designed, consisting of user equipment (UE), AP, and MEC server. AP can aggregate data generated by UE and improve edge processing. Then, based on Stackelberg game and matching, an efficient and dynamic allocation strategy for computational resources is put up. Our main contributions are summarized as follows:

Build a resource allocation model for Smart Home system with MEC. A three-tier framework is built to support applications’ demands for real-time interaction services. And optimization problems are formulated, limited by computational resources, taking diverse tolerance in delay and rate of applications into consideration.

A Stackelberg Game is proposed to represent relations between AP and UE. In Stackelberg Game, AP sets prices for virtual computational resource unit as a leader, and UE can determine the number of requiring resource as a follower. Through the game, higher utilities for UE and AP can be obtained.

One-to-many matching is introduced to maximize utility of MEC server. AP competes for computational resources owned by MEC server, forming a one-to-many matching. Similarly, AP reallocates their resources to users. It is proved that MEC server can obtain the best outcomes according to matching. In other words, computational resources can be distributed optimally.

The performance of the proposed system is evaluated and compared with the existing model with respect to performance metrics.

The rest of this article is organized as follows: The “Related work” section reviews the related work. The “System model” section presents the system model, including system architecture, network model, and problem analysis. An resource allocation strategy based on the Stackelberg game and one-to-many matching is introduced in the “Resource allocation strategy based on game theory and one-to-many matching” section, after which we propose the experimental results and corresponding discussions in the “Simulation results and analysis” section. The “Conclusion and future work” section is the conclusion and future work.

Related work

Cloud computing in IoT

During the last decade, cloud computing drew considerable attention as it offers lower cost solutions for fluctuating and unforeseen computational demand.¹⁰ It has been adopted by many organizations or enterprises to meet their demands for massive data processing.

In terms of environment monitoring, in order to derive the physical topology at the cloud for effective real-time event detection, Yu et al.¹¹ proposed a cloud-orchestrated physical topology discovery scheme for large-scale IoT systems. A network-wide three-dimensional (3D) localization algorithm is developed to improve the efficiency and accuracy of topology discovery. In order to establish a sensing as a service model, Perera et al.¹² proposed a scalable energy-efficient data analytics platform for on-demand distributed mobile crowd sensing called C-MOSDEN, which considered different domains to facilitate all conditions.

In manufacturing, Tao et al.¹³ gave a brief overview of the application of cloud computing in IoT first. And then they established a cloud computing and IoT-based cloud manufacturing service architecture and designed technology systems, to realize the full sharing, free circulation, and optimal allocation of manufacturing resources and capabilities. In IoT big data storage, Cai et al.¹⁴ gave an overview about current technology and research in IoT application, and analyzed perspectives and challenges in establishing IoT-based data storage systems in cloud computing.

Though conventional data center design is highly regular with identical servers and networking hardware aligned in a grid-like fashion, the centralized form of remote computing resources is not compatible with enormous traffic originated from geographically distributed edge devices. In microgrids, Harmon et al.¹⁵ presented a cloud-based and hybrid wireless mesh communication framework in microgrids. A diffusion-based, fully distributed algorithm and a quasi-distributed approach on wide-area Internet-based cloud are implemented. To overcome security challenges for data mutuality between two parties in IoT, Wang et al.¹⁶ presented a framework based on cryptographic methods to support data security in cloud-assisted IoT. However, other types of security issues, such as authentication, were not considered in this article.

Above all, meeting the needs and QoS requirements of various tasks that are demanded by IoT devices cannot be achieved by solely employing cloud servers or edge computing servers. In order to cover and serve wide range of envisioned services, both cloud and edge computing facilities need to be incorporated into a joint architecture.

Resource allocation strategy based on edge computing in IoT

Recently, many literatures have studied resource allocation strategies in different edge computing scenes. Wang et al.¹⁷ proposed an integrated framework form computation offloading and interference management in wireless cellular networks with MEC. They performed resource allocation using the graph coloring methods. Nevertheless, they did not consider competence between applications. Munoz et al.¹⁸ focused on wireless application offloading for radio and computational resources, optimizing trade-off between energy consumption and latency in femto-cloud. The allocation framework could save terminal battery and reduce latency in executing application.

Game theory is adopted by many works to solve data offloading. Zhang et al.¹⁹ presented a coalitional game based on pricing scheme to offload big data to the MEC server. Lian et al.²⁰ designed a game-theoretic framework under the communication cost constraint to enable economically viable communications. They optimized performance of MEC depending on location of edge servers. Zhang et al.²¹ gave an algorithm based on differential game to control energy consumption for cognitive radio (CR) system. Zhang et al.²² discussed a joint optimization approach combining Stackelberg Game and matching to achieve computing resource allocation in three-tier networks. It realizes utility maximization for servers based on fog computing.

Although these works have dedicated to different edge computing scenes, most of them focused on power control or resource allocation for servers or base stations. In Smart Home, considering requirement for high QoS and real-time response of delay-sensitive applications, it is crucial to establish an efficient and distributed framework with low interference based on MEC.

System model

System architecture

To meet requirements of different applications for real-time interaction and low-latency services in Smart Home, a three-tier architecture is considered, where UE can offload its service to MEC data centers through an AP as shown in Figure 1. APs are located in middle layer, linking MEC server in upper layer and serving UE in bottom layer. Generally, UE is connected wirelessly in Smart Home. It consists of different subsystems, such as lighting control, surveillance, and HVAC (heating, ventilation, and air conditioning),²³ which supply different services and have diverse tolerance for delay and transmission speed. Therefore, an allocation strategy for computational resource based on pricing mechanism is designed, aiming to meet demands of applications with higher computational speed or lower latency for priority.

Figure 1.

System architecture.

Assume that the computational resource of MEC server is stable during a certain time. The server can allocate resources to linked wireless base stations. Each base station has an AP that is associated with covered UE. When executing low-latency or real-time interaction tasks, UE can submit requests for AP and offload tasks to MEC server through telecommunication links after receiving response from AP.

In this article, MEC server links with AP directly and distributes resources to them. After AP purchases computational resources from the server, it can make optimal allocating decisions on connected UE to gain better utility.

Network model

It is assumed that there are K APs, labeled as $A = {a_{1}, a_{2}, \dots, a_{K}}$ . The number of UE that is connected to $a_{k}$ is $M_{k}$ , denoted as $S^{k} = {s_{1}^{k}, s_{2}^{k}, \dots, s_{M_{k}}^{k}}$ . The workload arrival rate of user $s_{j}$ is denoted by $λ_{j}$ . Then, MEC server has a normalized preference list over all AP, denoted as $L = {L_{1}, L_{2}, \dots, L_{K}}$ . Similarly, $a_{k}$ has a preference list over its users, represented as $N^{k} = {η_{1}^{k}, η_{2}^{k}, \dots, η_{M_{k}}^{k}}$ . Define unit amount of computing resources that can be distributed by MEC server as “computing resource block (CRB).” Each CRB can provide computing service at a rate of $μ$ . Parameters used in this article are listed in Table 1.

Table 1.

The table of parameters.

Notation	Meaning
K	Amounts of AP
$a_{k}$	The kth AP in the system
$M_{k}$	Amounts of UE connected to $a_{k}$
M	Amounts of CRBs
A	Set of AP
$S^{k}$	Set of UE that connected to $a_{k}$
$μ$	Service rate of each CRB
$s_{j}^{k}$	The jth UE connected to $a_{k}$
$λ_{j}$	The workload arrival rate of $s_{j}^{k}$
$t_{j}$	The service delay of $s_{j}^{k}$
$o_{j}$	The queuing delay in servers
$h_{j}$	The network delay
$q_{j}$	CRB amounts that UE requires
$l_{j}^{k}$	Distance from $s_{j}^{k}$ to the server
$W_{k_{j}}^{s}$	Utility of $s_{j}^{k}$
$W_{k}^{a}$	Utility of $a_{k}$
$W^{o}$	Utility of the MEC server
L	The preference list of MEC server over all AP
$N^{k}$	The preference list of $a_{k}$ over connected UE
$α_{j}^{k}, β_{j}^{k}, γ_{j}^{k}$	Weight factors in the utility function of UE
$r_{j}^{k}$	Setting price of AP over UE
$p_{k}$	Renting price that AP rents CRB from servers
$c_{k}$	Transmission cost from MEC server to AP
$Q_{k}$	CRB amounts that AP requires
${\tilde{Q}}_{k}$	CRB amounts that AP is allocated
$t_{th}$	The upper bound of delay tolerance

AP, access point; UE, user equipment; CRB, computing resource block; MEC, mobile edge computing.

User terminals can get CRBs from MEC server to conduct high QoS applications. The quality of QoS can be measured by service delay $t_{j}$ . It consists of queuing delay $o_{j}$ at servers and network delay $h_{j}$ . Then, $t_{j}$ for $s_{j}$ can be calculated by

t_{j} = h_{j} + o_{j}

(1)

According to models in Liu et al.,²⁴ $o_{j}$ can be presented by

o_{j} = \frac{λ_{j}}{μ - \frac{λ_{j}}{q_{j}}}

(2)

Research suggests that the network delay $h_{j}$ is influenced by many unpredictable factors such as transmission distance, traffic flow, and hardware equipment. It is recognized that $h_{j}$ follows a linear function with the total distance, $l_{j}$ , which equals to the distance from server to AP plus length from AP to user. Set scalar as $θ$ , and $h_{j}$ can be represented as follows

h_{j} = θ \cdot l_{j}

(3)

Users have different valuation of the edge computing services, depended on certain factors such as latency and service rates. These factors influence the computing resource demands of users. The demand should be derived to maximize the utility of terminals. Therefore, a price mechanism is introduced in the article. UE can gain reward in the process of executing real-time tasks. The number of tasks is related to the workload arrival rate, $λ_{j}$ . Meanwhile, it needs to undertake payments of purchasing CRBs. Besides, $s_{j}^{k}$ ought to consider cost for service delay. It is worth noting that there is an upper bound for the service delay. If the delay is larger than the threshold, the task would be regarded as a failure. Given weight factors $α_{j}^{k}, β_{j}^{k}, γ_{j}^{k}$ , utility function of $s_{j}^{k}$ can be concluded

W_{k_{j}}^{s} = α_{j}^{k} \times λ_{j}^{k} - β_{j}^{k} \times q_{j}^{k} \times r_{j}^{k} - γ_{j}^{k} \times t_{j}^{k}

(4)

According to requests from UE, AP can receive revenues for distributing CRBs. And it should pay for MEC server for renting CRBs as well. CRB amounts that AP allocates to connected UE should not exceed what it rents from MEC server. Therefore, utility function of $a_{k}$ through incomes minus losses can be calculated

W_{k}^{a} = (\sum_{j = 1}^{M_{k}} r_{j}^{k} \times q_{j}^{k}) - p_{k} \times Q_{k}

(5)

MEC server can get payments from APs for renting CRBs. The expenditure of MEC server includes costs in transmitting and maintaining normal function of the network. To sum up, discounted utility function for MEC server is

W^{o} = \sum_{i = 1}^{K} l_{i} \times (p_{i} - c_{i}) \times Q_{i}

(6)

Through adopting the price mechanism, computing tasks and resources can be measured by incomes or expenditure. In this way, utility of these objects can represent the efficiency of computational resource allocation.

Problem analysis

In summary, problems that need to be considered are listed as follows.

Amount of CRBs that UE purchases from AP. In the system, UE requires to purchase CRBs from APs. Since the CRB amounts that UE demands is closely influenced by the upper bound of service delay and setting price of AP, UE should determine the optimal amounts of CRB for higher utility.

Pricing problem for AP. AP needs to rent CRBs from MEC server and sell them to connected UE. To obtain maximum outcomes, AP intends to sell with high setting prices and pay for low renting prices. However, there is a pair of contradictions: facing high setting prices, UE will reduce CRB amounts purchased from AP at the cost of larger latency. In an extreme situation, UE will give up if it cannot obtain profits from conducting tasks. Meanwhile, the lower renting price AP pays, the smaller CRBs that AP can be allocated from MEC server. Therefore, predicting the reactions of UE, AP is required to balance service price and renting price so as to gain the maximum revenues.

Allocation problem between MEC server and AP. According to different renting price and distance in multi-AP scenario, MEC server obtains various profits from providing CRBs to AP, causing different preference over all AP. The server aims to reach a maximum utility based on the preference list over all AP.

Allocation problem between AP and UE. After matching between MEC server and AP, the server has distributed its CRBs to all AP. If CRBs that AP rents from server are less than that it requires, AP needs to determine allocation strategy over UE. On the basis of serving price, AP allocates resource on all UE to achieve a higher utility.

Resource allocation strategy based on game theory and one-to-many matching

In this section, optimal problems and allocation strategy based on game theory and matching are proposed. Utility functions of MEC server, AP, and UE are formulated as optimization problems according to equations (4)–(6), respectively. To obtain maximum utility for MEC server, first, a Stackelberg Game is established to find optimal CRB number for UE and solve pricing problem for AP. Second, CRBs are distributed through a one-to-many matching between MEC server and AP. Finally, an optimal allocation scheme between AP and UE is given.

Optimization problems

Taking workloads arrival rate, service delay, and number of requiring resources into accounts, utilities of MEC server, AP, and UE are formulated. In this way, they can be used to measure efficiency and quantity of supplying real-time services. In this section, utilities of three objects are formulated as optimization problems.

$t_{th}$ represents maximum tolerance of service delay for $s_{j}^{k}$ . Queuing delay cannot surpass $t_{th}$ , or it is a failure task for users. Utility of UE should be greater than zero. When serving price for $s_{j}^{k}$ is determined, CRB number that AP requires can be calculated. An optimization problem for $s_{j}^{k}$ is formulated as follows

\begin{matrix} max_{q_{j}^{k}} W_{k_{j}}^{s} (q_{j}^{k} | r_{j}^{k}) \\ subject to {\begin{matrix} t_{j}^{k} \leq t_{th} \\ α_{j}^{k} \times λ_{j}^{k} \geq β_{j}^{k} \times q_{j}^{k} \times r_{j}^{k} + γ_{j}^{k} \times t_{j}^{k} \\ q_{j}^{k} \geq 0 \end{matrix} \end{matrix}

(7)

After observing behaviors of UE, AP can set a renting price for purchasing CRBs from MEC server. It may cause interference when CRB amount that AP allocates to UE exceeds what AP owns, since same bandwidth frequency may be shared by different users. Utility of AP is also greater than zero. Optimal CRB amount required by all AP is denoted by $Q_{k}^{*}$ . Prices determined by other devices except for $s_{j}^{k}$ are represented by $⇀ r_{- j}^{k}$ . In order to gain a maximum utility at a specific serving price for $s_{j}^{k}$ , optimization problem of AP can be formulated as below

\begin{matrix} max_{r_{j}^{k}} W_{k}^{a} (r_{j}^{k} | Q_{k}^{*}, p_{k}, ⇀ r_{- j}^{k}) \\ subject to {\begin{matrix} \sum_{j = 1}^{M_{k}} (r_{j}^{k} \cdot q_{j}^{k}) \geq p_{k} \cdot Q_{k} \\ r_{k} \geq 0 \\ \sum_{j = 1}^{M_{k}} q_{j}^{k} \leq Q_{k} \\ Q_{k} \geq 0 \end{matrix} \end{matrix}

(8)

When MEC server receives renting prices from AP, it allocates CRBs relying on the preference list over AP. Renting price set by AP should be greater than transmission cost that MEC server undertakes. As total number of CRBs in network is M, available number that can be rented by AP must be less than M. $Q_{- k}^{*}$ and $p_{- k}^{*}$ represent optimal CRB number and optimal renting price of other AP except $a_{k}$ , respectively. The optimization problem of MEC server is

\begin{matrix} max_{Q_{k}} W^{o} (Q_{k} | Q_{- k}^{*}, p_{- k}^{*}) \\ subject to {\begin{matrix} p_{k} \geq c_{k} \\ \sum_{i = 1}^{K} Q_{i} \leq M \end{matrix} \end{matrix}

(9)

Stackelberg game for AP and UE

In Stackelberg game,²⁵ AP acts as a leader, predicting serving prices and required CRB number for user devices. UE acts as a follower, purchasing CRBs from AP when knowing the setting price. In the whole process, AP can observe actions of UE and determine service price finally. According to the Stackelberg game, lemma 1 can be concluded as follows:

Lemma 1. When serving price that AP sets is $r_{j}^{k}$ , the optimal amount of CRBs to reach maximum utility for user $s_{j}^{k}$ is

q_{j}^{k^{*}} = \frac{λ_{j}^{k}}{μ} + \frac{λ_{j}^{k}}{μ \sqrt{\frac{β_{j}^{k} \times r_{j}^{k}}{γ_{j}^{k}}}}

(10)

Proof. On the basis of utility function of $s_{j}^{k}$ , the second derivation of $W_{k_{j}}^{s}$ with respect to $q_{j}^{k}$ is

\frac{\partial^{2} W_{k_{j}}^{s}}{\partial {(q_{j}^{k})}^{2}} = \frac{- 2 μ \times γ_{j}^{k} \times {(λ_{j}^{k})}^{2}}{{(μ \times q_{j}^{k} - λ_{j}^{k})}^{2}}

(11)

For $\partial^{2} W_{k_{j}}^{s} / \partial (q_{j}^{k})^{2} < 0$ , the first derivation of $W_{k_{j}}^{s}$ follows a decreasing relationship with respect to $q_{j}^{k}$ . When $\partial W_{k_{j}}^{s} / \partial q_{j}^{k} = 0$ , value of $q_{j}^{k *}$ is optimal number of CRBs for UE to gain a maximum utility. The first derivation of $W_{k_{j}}^{s}$ is

\frac{\partial W_{k_{j}}^{s}}{\partial q_{j}^{k}} = - β_{j}^{k} \times r_{j}^{k} + \frac{γ_{j}^{k} \times {(λ_{j}^{k})}^{2}}{{(μ \times q_{j}^{k} - λ_{j}^{k})}^{2}}

(12)

Let the first derivation of $W_{j}^{k}$ with respect to $q_{j}^{k}$ equal to zero, and we can calculate an optimal number of CRBs purchased by UE as shown in lemma 1.

According to equation (7) and equation (11), the optimization problem of AP can be adjusted as follows

\begin{matrix} max_{r_{k}} W_{k}^{a} (r_{j}^{k} | Q_{k}^{*}, p_{k}, ⇀ r_{- k}) \\ subject to {\begin{matrix} \sum_{i = 1}^{M_{k}} (\frac{λ_{j}^{k}}{μ} + \frac{λ_{j}^{k}}{μ \times \sqrt{\frac{β_{j}^{k} \times r_{j}^{k}}{γ_{j}^{k}}}}) \times r_{j}^{k} \geq p_{k} \times Q_{k} \\ r_{j}^{k} \geq 0 \\ \sum_{i = 1}^{M_{k}} q_{i}^{k} \leq Q_{k} \\ Q_{k} \geq 0 \end{matrix} \end{matrix}

(13)

Utility function of $a_{k}$ can also be updated

W_{k}^{a} = \sum_{i = 1}^{M_{k}} (\frac{λ_{j}^{k}}{μ} + \frac{λ_{j}^{k}}{μ \times \sqrt{\frac{β_{j}^{k} \cdot r_{j}^{k}}{γ_{j}^{k}}}} \times r_{j}^{k} - p_{k} \times Q_{k})

(14)

First derivation of $W_{k}^{a}$ is formulated as below

\frac{\partial W_{k}^{a}}{\partial r_{j}^{k}} = \frac{λ_{j}^{k}}{μ} + \frac{λ_{j}^{k}}{2 μ \times \sqrt{\frac{β_{j}^{k} \times r_{j}^{k}}{γ_{j}^{k}}}}

(15)

As $\frac{\partial W_{k}^{a}}{\partial r_{j}^{k}} > 0$ , utility of AP is positive correlated with $r_{j}^{k}$ .

Furthermore, service delay of UE cannot surpass maximum tolerance of delay $t_{th}$ . A low bound of $t_{th}$ according to equation (2) can be inferred as follows

q_{j}^{k} \geq \frac{λ_{j}^{k} \times t_{th}}{μ \times t_{th} - λ_{j}^{k}}

(16)

Therefore, following results in equation (10), an upper bound of $r_{j}^{k}$ can be calculated, which is just the optimal price to obtain maximum utility of $a_{k}$ according to equation (15)

r_{j}^{k} = \frac{γ_{j}^{k}}{β_{j}^{k}} \times {(\frac{μ \times t_{th} - λ_{j}^{k}}{λ_{j}^{k}})}^{2}

(17)

According to equation (10), AP can gain the optimal number of CRBs that it expects to rent from MEC server as below

{\tilde{Q}}_{k} = \sum_{i = 1}^{M_{k}} q_{i}^{k}

(18)

One-to-many matching for MEC server and AP

Knowing the number of CRBs that AP wants to rent, MEC server makes decision on how to distribute CRBs to AP. Based on renting price and transmission cost, server has different preference over all AP, denoted as $L = {L_{1}, L_{2}, \dots, L_{K}}$ . AP with a higher preference has priority in the process of allocating computing resource. Different distances between MEC server and AP affect communication cost among them. And utility of MEC server is related to the cost and renting price. Therefore, the value of preference over AP can be measured by communication cost and renting prices

L_{i} = p_{i} - c_{i}

(19)

According to analysis of formulated framework, a one-to-many matching between MEC server and AP is designed. As shown in Algorithm 1, after constructing a preference list over all AP in step 1, one pointer is set as an indicator pointing at the most preferred AP initially in step 2. In steps 8–11, if server can supply more CRBs than what AP needs, demands of AP can be satisfied. Otherwise, MEC server will allocate all the left CRBs to AP. At the end of each round, if all CRBs of server have been allocated, the pointer will remain unchanged, or it will move to next AP. In summary, AP with a low preference may gain insufficient CRBs. Then, it needs to reallocate resources to UE. According to Algorithm 1, we can get a conclusion as lemma 2 shows.

Algorithm 1. One-to-Many Matching Algorithm between MEC server and AP
1: Construct preference list $L = {L_{1}, L_{2}, \dots, L_{K}}$ for MEC server on all AP according to equation (19);
2: One pointer is set as an indicator pointing at first AP in preference list;
3: Construct a list $Q^{a} = {Q_{1}, Q_{2}, \dots Q_{K}}$ to represent number of CRB that AP expects to rent from MEC server according to equation (18). List $Q^{} = {{Q_{1}}^{}, {Q_{2}}^{}, \dots {Q_{K}}^{}}$ indicates real number of CRB that AP is allocated from MEC server, initialized as a zero profile;
4: Initialize total available number of CRB owned by MEC server $a_{0} = N$ ;
5: Set a flag $f_{k}$ to indicate whether AP $a_{k}$ has been chosen by MEC server in last round; initially, $f_{k} = 1$ ; once $a_{k}$ is chosen, $f_{k} = 0$ ;
6: MEC server determines which AP to choose according to preference list;
7: for $a_{k}$ which is chosen by MEC server in last round do
8: if $a_{0} \geq Q_{K}$ then
9: $a_{0} = a_{0} - Q_{K}, {Q_{K}}^{*} = Q_{K};$
10: else
11: ${Q_{K}}^{*} = a_{0}, a_{0} = 0;$
12: end if
13: Pointer moves to the most preferred AP in rest ones whose $f_{k} = 1$ ;
14: end for

Lemma 2. Through one-to-many matching between MEC server and AP in Algorithm 1, MEC server can obtain maximum utility.

Proof. In Algorithm 1, MEC server constructs a preference list over all AP. A higher preference for AP represents that MEC server can gain greater outcomes if distributing CRBs to the AP. We set an indicator pointer of list to point at the most preferred AP initially. If there is rest resource that can be allocated after last round, the pointer moves to the second preferred AP in the list. Therefore, the pointer can only move on one direction. In other words, MEC server cannot achieve a higher utility through other allocating order. Thus, server achieves maximum utility.

After renting CRBs from MEC server, AP needs to reallocate them to UE if it cannot meet users’ demand. Based on serving price, AP has difference preference over all UE, denoted as $N^{k} = {η_{1}^{k}, η_{2}^{k}, \dots, η_{M_{k}}^{k}}$

η_{i} = r_{i}

(20)

According to relationship between AP and UE, we establish a one-to-many matching in Algorithm 2. The procedures are similar to that in Algorithm 1. Matching objects are the main difference between them. Since a real-time task is considered inseparably generally, it is worth noting that if number of CRBs that AP can supply is less than what UE needs, the UE will be abandoned, and pointer moves to next one as shown in steps 9–12. On the basis of Algorithm 2, the AP which can rent CRBs from MEC server is able to gain the best profits.

Algorithm 2. One-to-Many Matching Algorithm between AP and UE
1: for $a_{k}$ do
2: Construct a preference list $N^{k} = {η_{1}^{k}, η_{2}^{k}, \dots, η_{M_{k}}^{k}}$ for all UE according to equation (20);
3: One pointer is set as an indicator pointing at first UE in preference list;
4: Initialize total available number of CRB owned by $a_{k}$ as $b_{0} = {Q_{K}}^{*}$ ;
5: Set a flag $g_{j}$ to indicate whether $s_{j}^{k}$ has been chosen by AP in last round; initially, $g_{j} = 1$ ; once $s_{j}^{k}$ is chosen, $g_{j} = 0$ ;
6: $a_{k}$ determines which UE to choose;
7: for $s_{j}^{k}$ which is chosen by AP in last round do
8: if $b_{0} \geq q_{j}^{k}$ then
9: $b_{0} = b_{0} - q_{j}^{k}$ ;
10: else
11: $q_{j}^{k} = b_{0}, b_{0} = 0$ ;
12: end if
13: Pointer moves to most preferred UE in rest ones whose $g_{j} = 1$ ;
14: end for
15: end for

Simulation results and analysis

In this section, simulation results of the proposed scheme are presented with MATLAB. Generally, there are a MEC server and 10 APs, which are deployed randomly in a circle with diameter of 10 km. Each AP is connected to several UE located within a distance of 1 km. Amount of UE connected to one AP is 20 approximately. MEC server can supply 1000 CRBs to users. According to Liu et al.,²⁴ the service rate of each computational block is set as 0.1 ms⁻¹, and workload arrival rate of each device is a random number averaged 0.5 ms⁻¹. And maximum tolerance of delay is 60 ms. Weight factors in utility function of UE are set as 50, 0.01, 0.001.

In simulation, experiments are conducted with different parameters changing, that is, total amounts of user devices, number of AP, workload arrival rate, service rate, and so on, to evaluate the proposed scheme in terms of utilities of different objects. Furthermore, we make a comparison between the proposed scheme and an allocation strategy based on auction game,²⁶ to evaluate performance and efficiency of the allocation mechanism.

As shown in Figure 2, utilities of MEC server and ratio of UE that can be served in two allocation strategies are compared with total number of equipment changing, ranging from 50 to 400. The simulation is carried out for 100 times. The figure describes that as amount of user devices rises, utility of MEC server increases gradually and coverages to an upper bound eventually. Schemes based on Stackelberg game outperform the situation under auction game all the time. The Stackelberg equilibrium ensures that the optimal CRB amounts and service price, chosen by UE, can maximize utility of MEC server. However, in auction game, UE is distributed fewer CRBs within maximum tolerance of delay, affecting profits that MEC server can receive. Utility gap will decrease as devices get more, as computing resource gets saturated. Nevertheless, the mechanism according to auction game is more stable with smaller variances.

Figure 2.

Comparison between schemes based on Stackelberg game or auction game.

On the contrary, ratio of UE that can be served under two curves both decline with equipment increasing. And compared with Stackelberg game, auction game can satisfy requirements of more UE. Due to CRBs amounts that UE requests are fewer, the server can meet their demands with higher ratio based on auction game.

Figure 3 describes that utility of MEC server changes with different workload arrival rate, $λ$ , and service rate of CRB, $μ$ . The utility rises when $λ$ increases. Higher workload rate causes that UE requires more CRBs to complete its tasks; hence, the server can allocate more CRBs and obtain higher profits until all CRBs are distributed. In addition, based on their distance, renting price that AP pays for MEC server remains unchanged. Therefore, incomes that MEC server receives are greater than expenditure.

Figure 3.

Utility of MEC server with different parameters.

With respect to $μ$ , utility of MEC server decreases and coverages to zero ultimately as illustrated in Figure 3. A greater service rate means that UE can conduct computation tasks with fewer CRBs. And total CRBs that all UE needs decline. Therefore, MEC server cannot gain the same revenues as before.

The maximum tolerance of delay, T, has various effects on utilities of MEC server, AP, and UE as indicated by Figure 4. First, when T increases, ranging from 40 to 140 ms, utility of server decreases and converges to a low bound. Since users can finish their tasks with fewer CRBs in a higher tolerance of delay, revenues that server can obtain from renting resources get lower. Second, utility of AP increases linearly and positively with delay increasing. According to equation (17), serving price is related to quadratic function T. With an unchanged renting price for MEC server and a higher pricing price for UE, AP gets more outcomes. Finally, utility of UE declines. Reasons are that even though optimal amount of CRBs decreases, serving price increases by a larger margin for UE as T gets higher. Therefore, UE receives fewer profits.

Figure 4.

Utility with T changing.

From Figures 5 –7, utilities of MEC server, AP, and UE are shown as number of available CRBs increasing in four conditions, where different amounts of AP are deployed in network. Number of AP are 5, 10, 15, and 20, respectively. Figure 5 illustrates that utility of MEC server increases and reaches an upper bound finally when CRBs increase. Utility with more AP rises in faster speed. Figure 6 shows that as CRBs increase, utility rises and remains stable finally. In Figure 7, utility of UE is proportional to number of CRBs. To sum up, when CRBs increase, MEC server can supply computing services for more UE, and utility of all objects get higher. Once demands of UE in the framework become saturated, utilities increase to a certain point. Furthermore, they all get higher utilities with more AP deployed. Analyzing these figures, we can conclude that when number of AP is 5, number of CRBs required by UE are about 1500. In other three conditions, total CRBs required are 3500, 4500 and 6000, respectively.

Figure 5.

Utility of MEC server with different number of CRBs.

Figure 6.

Utility of AP with different number of CRBs.

Figure 7.

Utility of UE with different number of CRBs.

Conclusion and future work

In this article, we establish a hierarchical framework including MEC server, AP, and UE for Smart Home networks based on MEC. And an optimization problem is formulated, limited by computational resources, taking diverse requirements for delay and rate of users into consideration. Stackelberg game is proposed to solve resource purchasing problem and pricing problem for AP. Then, one-to-many matching is adopted to handle computational resource allocation problems for MEC server and AP. With maximum utility, the allocation strategy can improve allocating efficiency and guaranteeing real-time QoS for user terminals. Simulation results demonstrate the influence of different parameters such as number of CRBs and workload arrival rate. It is proved that compared with allocating mechanism based on auction game, the proposed framework can achieve a higher utility for server under Stackelberg equilibrium.

For the future work, we will take mobility and interactivity of smart terminals into account and apply the mechanism into smart city.

Supplemental Material

supplemental_files_for_review – Supplemental material for Mobile edge computing resource allocation: A joint Stackelberg game and matching strategy

Supplemental material, supplemental_files_for_review for Mobile edge computing resource allocation: A joint Stackelberg game and matching strategy by Shaoyong Guo, Xing Hu, Gangsong Dong, Wencui Li and Xuesong Qiu in International Journal of Distributed Sensor Networks

Footnotes

Handling Editor: Feng Ye

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 was supported by National Natural Science Foundation of China (Grant No. 601702048) and Industrial Internet platform standard management service public support platform.

ORCID iD

Xing Hu

References

Vallati

Virdis

Mingozzi

et al . Mobile-edge computing come home connecting things in future smart homes using LTE device-to-device communications. IEEE Consum Electron M 2016; 5: 77–83.

Aun

NFM

Soh

Alhadi

et al . Revolutionizing wearables for 5G: 5G technologies: recent developments and future perspectives for wearable devices and antennas. IEEE Microw M 2017; 18: 108–124.

Networking

. Cisco global cloud index: forecast and methodology. 2015–2020 White Paper, https://www.cisco.com/c/dam/m/en_us/service-provider/ciscoknowledgenetwork/files/622_11_15-16-Cisco_GCI_CKN_2015-2020_AMER_EMEAR_NOV2016.pdf

Baktir

Ozgovde

Ersoy

. How can edge computing benefit from software-defined networking: a survey, use cases and future directions. IEEE Commun Surv Tut 2017; 19: 2359–2391.

Hui

Ning

Qiu

et al . Fog computing based face identification and resolution scheme in Internet of things. IEEE T Ind Inform 2017; 13: 1910–1920.

Hui

et al . An edge caching scheme to distribute content in vehicular networks. IEEE T Veh Technol 2018; 67: 5346–5356.

Tang

Chen

Hefferman

et al . Incorporating intelligence in fog computing for big data analysis in smart cities. IEEE T Ind Inform 2017; 13: 2140–2150.

Hua

. The present development situation and prospect of intelligent home. China Comput Commun 2017; 3: 153–154.

Rashidi

Cook

Holder

et al . Discovering activities to recognize and track in a smart environment. IEEE T Knowl Data En 2011; 23: 527–539.

10.

Pocatilu

Alecu

Vetrici

. Measuring the efficiency of cloud computing for e-learning systems. World Sci Eng Acad Soc 2010; 9: 42–51.

11.

Wang

Jin

et al . Cloud-orchestrated physical topology discovery of large-scale IoT systems using UAVs. IEEE T Ind Inform 2018; 14: 2261–2270.

12.

Perera

Dumidu

Liu

et al . Energy-efficient location and activity-aware on-demand mobile distributed sensing platform for sensing as a service in IoT clouds. IEEE T Comput Soc Syst 2015; 2: 171–181.

13.

Tao

Cheng

et al . CCIoT-CMfg: cloud computing and Internet of things-based cloud manufacturing service system. IEEE T Ind Inform 2014; 10: 1435–1442.

14.

Cai

Jiang

et al . IoT-based big data storage systems in cloud computing: perspectives and challenges. IEEE Internet Things 2017; 4: 75–87.

15.

Harmon

Ozgur

Hazar

et al . The Internet of microgrids: a cloud-based framework for wide area networked microgrids. IEEE T Ind Inform 2018; 14: 1262–1274.

16.

Wang

Yang

. Secure data collection, storage and access in cloud-assisted IoT. IEEE Cloud Comput 2018; 5: 77–88.

17.

Wang

Liang

et al . Joint computation offloading and interference management in wireless cellular networks with mobile edge computing. IEEE T Veh Technol 2017; 66: 7432–7445.

18.

Munoz

Pascualiserte

Vidal

. Joint allocation of radio and computational resources in wireless application offloading. In: 2013 future network and mobile summit, Lisboa, 3–5 July 2013, pp.1–10. New York: IEEE.

19.

Zhang

Chen

Yang

. Data offloading in mobile edge computing: a coalitional game based pricing approach. IEEE Access 2018; 6: 2760–2767.

20.

Lian

Chakrabortty

Duel

. Game-theoretic multi-agent control and network cost allocation under communication constraints. IEEE J Sel Area Comm 2017; 35: 330–340.

21.

Zhang

Zhou

Wang

et al . Power control algorithm based on differential game for CR system. J Electron Inform Technol 2010; 32: 141–145.

22.

Zhang

Xiao

et al . Computing resource allocation in three-tier IoT fog networks: a joint optimization approach combining Stackelberg game and matching. IEEE Internet Things 2017; 4: 1204–1215.

23.

Attia

Ashour

. Energy saving through smart home. Online J Power Energy Eng 2010; 2: 223–227.

24.

Liu

Lin

Wierman

et al . Geographical load balancing with renewables. Perf E R 2011; 39: 62–66.

25.

Myerson

. Game theory: analysis of conflict. Beijing, China: Chinese People’s Publishing House, 2015, pp.254–283.

26.

Ausubel

. An efficient dynamic auction for heterogeneous commodities. Am Econ Rev 2006; 96: 602–629.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.02 MB