Game-Theoretic Online Resource Allocation Scheme on Fog Computing for Mobile Multimedia Users

Yingmo Jie,Mingchu Li,Cheng Guo,＊,Ling Chen

1 Institution of Applied Mathematics,Dalian University of Technology,Dalian 116024,China

2 School of Mathematical Sciences,Dalian University of Technology,Dalian 116024,China

3 School of Software Technology,Dalian University of Technology,Dalian 116620,China

4 Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province,Dalian 116620,China

Abstract:Fog computing is introduced to relieve the problems triggered by the long distance between the cloud and terminal devices.In this paper,considering the mobility of terminal devices represented as mobile multimedia users (MMUs) and the continuity of requests delivered by them,we propose an online resource allocation scheme with respect to deciding the state of servers in fog nodes distributed at different zones on the premise of satisfying the quality of experience (QoE) based on a Stackelberg game.Specifically,a multi-round of a predictablyunpredictably dynamic scheme is derived from a single-round of a static scheme.The optimal allocation schemes are discussed in detail,and related experiments are designed.For simulations,comparing with non-strategy schemes,the performance of the dynamic scheme is better at minimizing the cost used to maintain fog nodes for providing services.

Keywords:fog computing; online resource allocation; Stackelberg game; dynamic multimedia

I.INTRODUCTION

With the rise of the Internet of Things (IoT) [1-3],massive data are continuously being transmitted from widely distributed sensors and intelligent terminals to the cloud.However,due to the long distance between the cloud and terminal devices,it will inevitably produce problems like high latency,network congestion,reliability and so on that cannot be guaranteed.To solve these problems,Cisco was inspired by the cloud to propose a new paradigm called fog,which exists between the cloud and terminal devices as a hub and transforms the edge of the network into a distributed computing infrastructure for applications.Instead of directly sending requests to the cloud,users send requests to the fog nodes.Here,each fog node has a certain amount of computing power to perform the functions of storage [4] and preprocessing [5-6],which can reduce the computing burden on the cloud.Recently,fog computing has ubiquitously covered many smart city applications,such as healthcare [7],vehicle networks [8],and so on.As the locations of fog nodes are closer to the terminal devices owned by end users,solutions to the above-mentioned problems are prominent.Nowadays,with the expansion of wirelesswired networks,an increasing number of end users are connecting to them to acquire high-quality services,which drastically increases the importance of fog computing.On the other hand,the cost for maintaining these fog nodes is extremely huge,and conflicts with the quality of experience (QoE) pursuit of end users.Hence,with the objective of minimizing the cost for providing services on the premise of satisfying the QoE,how to allocate the fog resources deserves attention.

During recent years,multimedia has gradually presented to the public services for video and audio.Since then,relevant works about multimedia resources allocation have been proposed.Commonly,a scheduler owns a certain amount of cloudfog resources to provide services for multimedia users who have some requests expecting to be processed.To obtain a satisfying QoE associated with the given requests,the objective of each multimedia user is to minimize the response time.Relatively,as the service provider,the scheduler should guarantee the QoE required by users.On the other hand,as the resource owner,the objective of the scheduler is to minimize the cost used to maintain fog node operation.However,satisfying QoE and minimizing the cost are in conflict with each other,i.e.,there exists conflicts between the scheduler and multimedia users.Hence,a leader vs.follower Stackelberg game is launched to model the interaction between the scheduler and multimedia user.However,according to the character about multimedia that the mobility of multimedia users and the continuity of their requests,the resource allocation scheme should be designed dynamically.However,few previous works have simultaneously discussed the above-mentioned issues.

In this paper,suffered from the above-mentioned problems and inspired by the Stackelberg game [9],we design an online resource allocation scheme under the background of multimedia service networks,where the scheduler provides multimedia services for mobile multimedia users (MMUs) through fog computing.In particular,the service time is divided into slots; for each slot,the scheduler first decides the states of all fog nodes distributed at different zones,then based on the strategy of the scheduler,each MMU selects an available fog node to deliver hisher requests.Considering the unknown future requests,our proposed methodology can solve this problem with the aid of history data to guarantee the normal operation of the fog nodes.Hence,our scheme can be considered as a generalized framework to propose all kinds of resource allocations when the history data are provided accurately.The main contributions of this paper are as follows:

1.A leader vs.follower Stackelberg game is employed to model the interaction between the scheduler and MMUs.

2.An online resource allocation scheme is proposed to maximize the scheduler's utility on the premise of satisfying the QoE required by MMUs.

3.A single-round of static requests scheme is extended to a multi-round of dynamic requests scheme.

4.A simple method for the scheduler to predict future requests in terms of history data is developed.

The remainder of this article is organized as follows.In section 2,we propose an online resource allocation scheme based on the Stackelberg game in detail.Following that,we evaluate the performance of this scheme in terms of minimizing the cost used to maintain fog nodes in section 3.Finally,in section 4,we briefly draw our conclusions with respect to this paper.

II.RESOURCE ALLOCATION SCHEME

2.1 System model

As two parties form the resource allocation scheme,the scheduler and MMUs are modeled as a leader vs.multiple followers Stackelberg game to interact with each other.The scheduler,who acts the role of leader and owns a huge number of resources,should decide the allocation of these resources at different fog nodes to cope with the requests from various MMUs distributed at different zones.Particularly,setting minimizing the cost of operating the multimedia networks as the objective,the strategy of the scheduler is to decide the state of each fog node—whether it is on or off.On the other hand,each MMU whose objective is minimizing the response time acts the follower to deliver the corresponding request to one fog node based on the strategy first committed by the scheduler.As the requests cannot be delivered to fog nodes at same time and because the multimedia users may be dynamically mobile when they need fog resources to provide services,we divide the service time into several slots to propose an online resource allocation scheme.For further clarification about our scheme,we provide figure 1 to specify it given a service slot.First of all,the service region is divided into some zones and every zone is equipped with a fog node to provide services for MMUs.The scheduler should decide the states of all nodes to minimizing the costs as well as satisfying the QoE given by MMUs.MMUs can obtain services from open fog node belonging to directly or indirectly covered zone.

Table I.Summary of notations.

Fig.1.System architecture of our scheme.

2.1.1 Zones

The service region to be analyzed is divided intozzones Z={1,2,…,z} .For any zone,it has been equipped with fog nodes to provide services for MMUs.A matrixMm={ik}zz×is employed to represent the adjacency relationship between different zones,wheremik=1 represents that zonesiandkare adjacent,and vice versa.Practically,adjacent zones can be regarded that they share a common geographical border with passable roads between them.A zone is to be adjacent to itself,i.e.,mii=1.According to the partition of the region,for any zonei Z∈,there are some MMUs inside,and it can be said that these MMUs are directly covered by it and constitute a set denoted asUi.For any MMU directly covered by zonei Z∈,we assume that hisher request not only can be processed byi's fog nodes but also by others contained ini's adjacent zones.Hence,for any MMUjin zonei Z∈,the fog nodes can be used to process hisher requests to constitute a set denoted asRi,whereUi⊂Ri.For any elementk U∈i,we can say that MMUjis indirectly covered by that element.Here,the detailed notations of this paper are illustrated in Tab.1.

2.1.2 Scheduler

To provide service for MMUs,these fog nodes distributed to different zones should switch on normally.However,keeping all fog nodes on working can waste resources when the amount of requests from MMUs is comparatively small and the cost used to operate these fog nodes is extensive.On the other hand,the QoE required by MMUs should be satisfied by the scheduler.Hence,as the administrator of these fog nodes,on the premise of satisfying MMUs' demand for resources,the scheduler should dynamically decide the state of each fog node,i.e.,an on or off state,based on the change in MMUs' requests to minimize the cost used to maintain these fog nodes.Mathematically,as the leader of the Stackelberg game,the strategy of the scheduler is denoted as a binary vectorb={b1,b2,…bz},wherebi=1(orbi=0) represents that the state of the fog node in zoneiis on (or off).

Here,we will introduce the cost used to maintain fog nodes to provide services.We assume that the multimedia requests delivered to each node are regarded as its workload and measured by power of its servers.Here,a common server power function was studied by Google [10],as follows:

wherecis defined as a factor to transform server power into cost;Tiis the working time when the state of the fog node in zoneiis on.

Finally,as the service users are not static but possibly continuously mobile and as their requests cannot be generated simultaneously,the resource allocation scheme should be changed dynamically with the service time passing by.In terms of mathematics,service timeTis evenly divided into several slots {1,2,,Γ… },and the actual time of each round is denoted asτ,whereT=⋅Γτ.For each slott,the strategy of the scheduler should be adjusted according to the actual requests and previous strategy.

2.1.3 MMUs

Based on the strategy decided by the scheduler,each MMU should select only one on-working fog node constructed in a zone among available zones set to deliver hisher request on the premise of satisfying QoE that can minimize the response time.For any MMUj U∈i,hisher available zones set are denoted asMathematically,as the follower of a Stackelberg game,the strategy of MMUj U∈iis denoted as a binary vectorwhereak=1 represents that heshe selects zonekto deliver the request and vice versa.

Here,we will introduce the response time associated with the processing requests.For any MMUj,we apply the following function

to represent the demand for QoE,wherexjis the amount of requests delivered by MMUjandαj(0 ＜αj＜ 1) represents the sensitivity of MMUjon satisfaction of the obtained services.For example,the sensitivity of listening to the music is smaller than that of watching the video.Hence,with the growths ofxjandαj,the response timeqjalso increases.Correspondingly,the response time for MMUjwhose request is processed at zoneican be formulated as:

whereεis the service charge offered by MMUj;riis the number of requests waiting for processing at zonei.

2.2 Problem formulation and optimal solutions

In this subsection,we will present the specific online resource allocation scheme based on a Stackelberg game.First,we will give an offline scheme reflected as a single-round of static requests.However,considering the continuity of requests delivered by mobile users,the cost used to maintain fog nodes and caused by restarting the servers equipped at fog nodes,we then further extend the original scheme to an online one reflected as multiround of dynamic requests.

2.2.1 Single-round of static requests scheme

Given the current requests from all MMUs,we only need to consider the optimal resource allocation scheme for the current round.The optimal model associated with the scheduler can be formulated as:

Here,the objective (5) is to minimize the total cost employed to maintain fog nodes distributed in different zones.Constraint (6) requires that each zone is covered by at least one fog node to provide services for its MMUs.Constraint (7) means that the actual amount of requests delivered to each fog node cannot access its capacity.Correspondingly,the optimal model with respect to MMUjcan be formulated as:

Here,the objective of (8) is to minimize the response time for MMUjwho is directly covered by zonei.Constraint (9) guarantees that the choice of the MMU is only one fog node constructed at a zone.

Next,we will calculate the optimal solutions for the above-mentioned models.For MMUs,it is easy to find out the optimal zone choice with the traversing method.However,the optimal problem associated with the scheduler is abstracted as a set cover problem [12].Inspired by the greedy algorithm of the set cover problem with weights [13],we propose an approach to solve this NP-hard problem.The main steps are as follows:

Step 1.Initialize all variable sets such asU i=Rifor eachi∈Z,b=0.

Step 2.Traversing all zones inZto find the optimal zoneithat satisfies the ratio of the intersection ofZand the elements covered by zoneiwhere the running cost is the biggest.Then open this fog node in zoneiand delete the elements which have an adjacent relationship with zoneifrom setZ.Based on eqs.(6)-(7),if the current decision breaks them,give up the biggest one but select the sub-biggest one.Repeat step 2 untilZis empty.

Step 3.Based on eqs.(8)-(9),any MMU will find an available fog node to deliver requests while minimizing the response time without accessing the capacity of the fog node.If there exists one MMU whose choice is different from hisher current connected fog node,then change the relevant two setsUto reconsider the fog node choices until no MMU modifies their choice.

Step 4.Calculate the total cost associated with the scheduler.If the value is smaller,retain it and the current solution as the initial solution.Otherwise,the relevant allocation strategy is classified as invalid list.We continue this process until the total cost of the previous solution is the same as the current solution.We regard this result as the final solution.

Based on the above-mentioned approach expected for a single-round,we will next further exploit it for multi-round.

2.2.2 Multi-round of predictably unpredictably dynamic requests scheme

As time goes on,the demand for processing requests changes dynamically caused by the incoming or outgoing users.Moreover,considering the mobility of MMUs,the locations also may have changed,which can affect the strategy of the scheduler.On the other hand,highlighting the utilization of resources and saving costs employed for running the fog nodes are also researchable.Hence,the resource allocation scheme should be dynamic following the change of requests.Here,we extend the above-mentioned scheme to a dynamic one in the equally time-slotted system,i.e.,the service time is evenly divided into several slots,and each slot represents one round.In practice,besides the cost used to provide actual services for users,the loss associated with wear and tear resulting from the daily operation of the fog nodes cannot be ignored.Especially,the loss caused by changing the state of the fog nodes may trigger more cost than that under the on-idle state.Based on this principle,we assume that the loss generated by changing the state denoted asIis between that for idly runningsrounds ands+1 rounds,i.e.,c⋅P(0 ) ⋅sτ＜I＜c⋅P(0) ⋅ (s+1)τ.Hence,for each round,the scheduler should also take the loss into consideration to decide the strategy for the current round.In particular,at the beginning of any round,for any fog node,if this node should switch off based on the requests delivered by MMUs,but needs to be on for at least one round among the nextsrounds,this node will keep “on” open for the current round.Otherwise,it will close it.If the future dynamic requests are predictable,the main steps used to solve this problem are as follows:

Step 1.At the beginning,apply the predictable requests and single-round static requests' steps to calculate the scheduler's strategy for futures+1 rounds.

Step 2.Before deciding each fog node's state for the current round,compare the open fog nodes of the prior round with that of the nextsrounds.In addition to switching on the relevant nodes,only switch off the ones for the prior round but not for the nextsrounds.

Step 3.Akin to step 1,only calculate for one future round,i.e.,rounds+2.Go back to step 2 until all service time slots are finished.

From the above-mentioned steps,it is not hard to find that the future requests with respect to MMUs are quite important for this scheme.However,in many practical situations,it is difficult to obtain future requests.Here,we apply security historical data [14-15] to predict the future requests.Specifically,to predict a certain time slot's requests,the historical data include the same time's in previousDdays and the prior slot's requests in the same day,where the later one is applied for an emergency in the current day.The predicted function associated with zoneiat slottis formulated as:

whereβτrepresents the influence weights of history dataτtoηitand satisfiesis the total requests delivered to zoneiat slottin previous dayτ.Particularly,is the one at thet-1 slot in the same day to avoid some emergencies,which can cause significant volatility for the actual requests.It is not hard to see that the influence weights of history data are quite important for predicting the future's requests.Here,we can apply some famous machine learning algorithms to calculate the values of them.After that,the future's requests can be obtained with the aid of eq.(10) and history data.With respect to the algorithm used for multi-round of unpredictably dynamic requests,it is same with that of predictably dynamic requests when the requests have been predicted.

Table II.Values of notations.

Fig.2.Cost of the scheduler generated by different schemes.

III.PERFORMANCE EVALUATIONS

To evaluate the performance for our scheme,we present the simulations to quantify the cost paid by the scheduler in terms of the number of service rounds,MMUs and open fog nodes.We also consider the response time of MMUs with respect to the number of open fog nodes.We applied eclipse and Java to write the programs,and the figures are drawn with origin 8.0.All computations are run on a machine with 2.3GHz Intel Core i5 with 8 GB memory.Here,the main values of the relevant notations are given in table 2.

3.1 Number of rounds

We compare the performance of our schemes with other non-strategy schemes by evaluating the number of rounds' influence denoted asr.In figure 2(a),given that future requests are known,we compare our scheme with naive scheme,i.e.,only considering current profit without futures'.From the results,we can observe that with the growth of services time,the scheduler should pay a larger cost to maintain services and the difference between naive scheme and ours also gradually enlarge.In figure 2(b),given that future requests are unknown,we employ the history data and eq.(10) to predict them.Taking the loss cost used to change the state of fog nodes into consideration,the performance of our scheme is better than that of the naive scheme.Finally,in figure 2(c),we compare our multi-round dynamic scheme with a non-strategy scheme named the random scheme.We assume that at half of these fog nodes will be open randomly at each round regardless of the requests.If there exist any requests that cannot be processed,we will give the scheduler a punishment cost.Here,we select the best and worst random cases to compare with our scheme.From the results,the performance of our scheme and the best random scheme are similar when the number of rounds is small; however,as the rounds increase,the difference between them obviously becomes larger.

Fig.3.Cost of the scheduler with the different number of MMUs.

Fig.4.Cost of the scheduler with the different number of fog nodes.

3.2 Number of MMUs

The number of MMUs is also an important factor that influences the scheduler's cost.Although each MMU should offer the service fares to the scheduler,we only consider the cost of maintaining services without a payoff.To compare with the single-round static scheme,for the multi-round dynamic scheme we distributed the same number of MMUs to different rounds,wherer=3 In figure 3,the performance of the single-round is better than the multi-round.The reason behind this is the cost used for on-idle fog nodes in the multiround scheme.The single-round scheme is entirely without consideration for the cost used for on-idle fog nodes.Hence,the cost of the single-round is much less than that of the multi-round.

3.3 Number of open fog nodes

As a matter of fact,the number of open fog nodes is also a significant factor that affects not only the scheduler's cost but also the MMUs' response time.Here,we consider the cost in terms of the single-round static scheme.Given the number of open fog nodes,there are some allocation strategies.Hence,we calculate the average cost and the minimum cost to measure the performance of our scheme.From the results of figure 4,we find that the optimal number of open fog nodes is three,and a punishment will be generated if the number of open fog nodes is too small to provide services.The extra cost will also be generated when too many on-idle fog nodes are active.Reversely,the number of open fog nodes also can influence the response time for the MMUs.In figure 5,given the number of MMUs,the decline rate in response time slows down as the number of open fog nodes increases until it reaches a threshold.More MMUs will trigger the longer response time given the number of open fog nodes.Hence,besides the specific fog nodes resource allocation,the number of open fog nodes also deserves to be considered carefully.

Fig.5.Response time of MMUs with the different number of fog nodes.

IV.CONCLUSION

In this paper,to mitigate the problems caused by remote distances for cloud computing and to resolve conflicts between the scheduler and MMUs,we introduce fog computing to design a resource allocation scheme in multimedia networks based on a Stackelberg game.To minimize the running cost used to maintain fog nodes distributed at various zones,the scheduler decides the states of these fog nodes on the premise of achieving QoE.Facing mobility of MMUs and continuity of requests,the original scheme is extended to an online scheme by dividing the service time into several slots.Simulation results for evaluating the utility of the scheduler demonstrate that the online scheme is superior to the non-strategy scheme.

For the future research about this paper,we will consider the competitions among MMUs who expect to get services from the same fog node.Then,instead of only pursuing profit for the scheduler,we need to consider a trade off between different objectives,such as energy conservation,latency,and coverage efficiency.

ACKNOWLEDGEMENT

This paper is supported by the National Natural Science Foundation of China under grant No.61501080,61572095,61871064,and 61877007