QoS and QoE aware multi objective resource allocation algorithm for cloud gaming

2.1. Literature review

The eight classical cloud gaming strategies based on resource allocation are devised in this section. Guo et al. [8] devised a model based on game theory in the cloud platform for meeting the complete needs of players at less cost. The game was confirmed as a potential game with an effective potential function. The model helped the players attain jointly agreeable steady states, and the model reduced the overhead and attained improved performance than other methods. The method scaled well with the count of users and can be an impending technique to optimize resources. Aslanpour et al. [1] devised a learning-based resource provisioning strategy for MMOG services devised based on autonomic computing models and learning automata (LA). The method’s efficiency is based on response time allocated to virtual machines (VMs), and the cost is accessed by simulation. The method reduced the overall cost of resources with enhanced response time. However, the method failed to analyze the resource provisioning method with optimization strategies. Zhu et al. [32] addressed revenue maximization as Stackelberg’s game. They evaluated the subsistence and individuality of the game equilibrium. Also, the dynamic pricing method was devised for maximizing both IaaS and SaaS. The outcomes revealed that the devised method was effective in utilizing resources and revenue maximization. However, the method failed to consider cooperation and competition amongst different IaaS providers to select the most apposite providers. Haouari et al. [10] devised a prediction-driven resource allocation model for maximizing the QoE of users and reduce the distribution of resource cost. By utilizing the viewers’ location, a machine learning model was devised for predicting the viewer’s number with a geo-distributed cloud site. Secondly, with the predicted outcomes, an optimization issue was formed for allocating the resources. However, the method failed to include distributed proactive resources. Slivar et al. [29] devised a method, namely QoE-aware resource allocation, for solving the optimization issue deduced by numerous cloud gaming users. The optimization issue was addressed using techniques that adapt the QoE estimation method obtained from the prejudiced studies for different kinds of games. The results confirmed that both resource providers and cloud gaming service providers adapted video coding attributes for resource allocation. However, the method failed to consider optimized resource allocation in different network links. Lee et al. [20] devised a speculative execution system, namely Outatime for mobile cloud gaming, capable of facade network latency. The Outatime offered tentative rendered frames for resource allocation. The method helped predict the future and facilitated cloud gaming providers to reach bigger communities by maintaining a high user experience level. Depasquale et al. [6] devised a cloud computing model that executed graphics-intensive programs like video games. It uses the GPU to render the graphics and stream the resulting video to the mobile device bandwidth inhibited channels. The mobile controls the user to interact with the game from remote areas. Liu et al. [25] devised two methods for improving the quality of apparent video and minimize computation complexity. Initially, the rendering-based prioritized encoding method was devised for enhancing the alleged game video quality based on the constraints of the network. Then, a macro-block level saliency map was devised to render the information. The prioritized allocation of rates was devised by dynamically adjusting the quantization parameter value for each macroblock based on the saliency mapping. Yiwen et al. [9] developed cloud gaming through the QoE-Oriented resource competition method. The distributed algorithm based on a potential gaming strategy is used to optimize the virtual machine placement in the cloud environment. This method obtained better performance efficiency. The drawback of this paper is that it is not suitable for multidimensional parameters. Yusen et al. [23] developed the resource usage reduction model using QoS in cloud gaming. In this, the brute-force algorithm is used for resource allocation in the cloud. They achieved high precision accuracy and increased resource utilization. The major disadvantage of the method is that it is not applicable to predict the interaction delay.

The solution representation is essential to determine the best solution for solving optimization issues. Here, the proposed Rider-based HSA algorithm is employed for selecting the appropriate solution, in which optimal games and VMs are selected from available solutions. The optimization discovers the optimum value amongst the solutions present in the solution set, which is first given as a random value. For allocating resources, the solution set contains an optimal set of games. Assume an application with seven games, as displayed in Fig. 3. Thus, the solution vector HSA games allocated at random at the initial time. Then based on fitness, the solution set acquires optimal games. These games are assigned to resources based on the newly devised fitness function.

OPEN IN VIEWER

Fig. 3.

Solution representation for resource allocation.

The fitness is evaluated to determine the best solution using the solution set. The fitness function formulated for the proposed Rider-based HSA is based on three parameters, which involve quantified experience of players, mean opinion score (MOS), and fairness. The quantified experience of players based on the gaming experience loss is the target optimization function. The solution’s fitness is considered as a maximization function so that optimal resource allocation is performed for initiating cloud gaming. The fitness function of the proposed Rider-based HSA is represented as, (3) F = QE + MOS + J T where, QE is the quantified experience of the players, MOS signifies mean opinion score, and J T represents fairness. The fitness is the maximization problem for which the QE should be maximal, MOS should be maximal, and fairness should be maximal.

The mean score opinion [29] is formulated as, (4) MOS = 1 l ∑ k = 1 l ( B k ∗ L k + V k ∗ L k ) where, B k signifies bit rate of the game that runs in kth VM, V k symbolizes video frame rate of the game running in kth VM, and L k indicates the resource parameters.

The resource parameters for improving Quality of Service (QoS) are formulated as, (5) L k = 1 4 ( X R + X Y + X C + X P max ( X R , X Y , X C , X P ) ) where, X R is the number of processors, X Y is the amount of memory usage, X C is the amount of bandwidth, and X P is the number of MIPS utilized for resource allocation.

By integrating delay, Frame per Second, and resolution, the gaming experience loss GL [8] of the player is devised, which is the target of each player and is formulated as, (6) GL = μ 1 U − μ 2 W l − μ 2 N where, μ 1 , μ 2 and μ 3 indicate constant parameters, U signifies delay, W l indicates experienced frames per second (FPS), and N is quality of gaming video.

The QE of the players should be maximal for the players, while the gaming experience loss should be minimal.

As the VM with games are formed and ruined dynamically, and there may subsist a clone delay amongst user p, which indicates delay in initializing service. By storing the games in the repository, the speed of writing on a hard disk is expressed as O for ease. If a player selects a game using file size x k , total delay [8] is expressed concerning the VM initialization time T and is given as, (7) U = ∑ k = 1 l x k O + T k where, x k indicate file size of the game in kth VM, O refers to writing speed of the hard disk, and T k is the VM initialization time.

The Frame per Second (FPS) [ 8 ] practiced by gaming users is a key experience measure. The users practice gaming with a key experience metric, namely Frame per Second (FPS), for dealing with the cloud scenario. Generally, the FPS is discovered with GPU, RAM, and CPU considering the physical server. In cloud gaming, the FPS is formulated as, (8) W l = ∑ k = 1 l ω 1 1 + e ω 2 [ 1 5 ∑ k = 1 l ϑ k + L k ] + ω 3 L k

Where, ω 1 , ω 2 and ω 3 indicate parameters for approximation.

The quality of game video [ 8 ] is represented as, (9) N = ∑ k = 1 l ( ω υ log 2 ( 1 + ℓ N k ω o + ∑ k = 1 ℓ ℓ N k ) ) where, ω, ℓ and ω o signifies constant, and N k represent video resolution of game in jth VM.

Fairness is represented as, (10) J T = 1 l × t ∑ k = 1 l ( ∑ s = 1 t Q ) ∗ UPL where, UPL signifies user preference level and Q be the QoE scores of games played by the history users.

4.3. Algorithmic description of the proposed Rider-based HSA algorithm

The allocation of resources is done using a novel optimization algorithm, namely the Rider-based HSA algorithm. The proposed Rider-based HSA algorithm integrates the ROA algorithm with the HSA. ROA [3] is motivated by riders’ actions that pass through reach a proverbial target place to turn into a winner. Here, the riders are chosen from the total riders of each group. Each group undergoes several strategies for reaching the target. Thus, it is noted that this method performs fault diagnosis with enhanced classification accuracy. Also, the ROA is highly productive and follows steps of fictional computing to address the problems of optimization but poses less convergence and is sensitive to hyperparameters. The ROA provides high performance in unknown search spaces and can solve constrained and unconstrained problems. On the other hand, HSA [4] is a recently devised mechanism that improves music. Here, musicians improve the pitches of instruments to obtain a perfect state of harmony. The HSA algorithm provides improved convergence speed and high accuracy. Besides, the HSA provides better tradeoffs between exploitative and explorative tendencies. It is applied to solve engineering optimization issues. Thus, the hybridization of HSA and ROA is done to obtain the optimal global solution. The steps considered in the proposed Rider-based HSA algorithm is described below:

Step 1) Initialization of Rider and other algorithmic parameters

The follower HSA a tendency to update position using leading rider position to reach the target more quickly and is expressed as, (12) D n + 1 f ( u , r ) = D S ( S , r ) + [ Cos ( Z u , r n ∗ D S ( S , r ) ∗ y u r ) ] where, r is coordinate selector, D S indicate leading rider position, S represent leading rider index, Z u , r n represent steering angle of the uth rider in rth coordinate, and y u n is the distance.

The over taker’s update position is utilized to maximize fitness by detecting the overtaker position and is formulated as, (13) D n + 1 o ( u , r ) = D n ( u , r ) + [ A n ( u ) ∗ D S ( S , r ) ] where, A n ( u ) represent the direction indicator of the uth rider at a time instant n.

The attacker poses a tendency to seize the leader’s position by following the leader’s update process and is given as, (14) D n + 1 a ( u , v ) = D S ( S , v ) + [ Cos Z u , v n ∗ D S ( S , v ) ] + y u n

The bypass riders pursue a familiar path without following the leading rider. In this context, the update rule of the bypass riders is exhibited in which the standard bypass rider is given as, (15) D n + 1 ( u , v ) = η [ D n ( α , v ) ∗ ρ ( v ) + D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ] where, η represent ransom number between 1 to H, α specifies a random number ranging between 1 to H and ρ indicate a random number between 0 and 1.

Assume α = u , then the equation can be rewritten as, (16) D n + 1 ( u , v ) = η [ D n ( u , v ) ∗ ρ ( v ) + D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ]

Every unit generated considering memory is further evaluated to discover if it should be pitch-adjusted. The update of HSA [4] is given as, (17) D n + 1 ( u , v ) = D n ( u , v ) ± rand ( 0 , 1 ) · E

Where, rand ( 0 , 1 ) represent the random number in [ 0 , 1 ] , E signifies arbitrary distance bandwidth. (18) D n ( u , v ) = D n + 1 ( u , v ) ± rand ( 0 , 1 ) · E

The bypass riders undergo a familiar path without following the leading rider. HSA enhances the update position of the bypass rider. Thus, the substitution of equation (18) is done in equation (16), and the resultant equation is expressed as, (19) D n + 1 ( u , v ) = η [ ( D n + 1 ( u , v ) ± rand ( 0 , 1 ) · E ) ∗ ρ ( v ) + D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ] , (20) D n + 1 ( u , v ) = η D n + 1 ( u , v ) ∗ ρ ( v ) + η [ ( D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ± rand ( 0 , 1 ) · E ) ∗ ρ ( v ) ] , (21) D n + 1 ( u , v ) − η D n + 1 ( u , v ) ∗ ρ ( v ) = η [ ( D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ± rand ( 0 , 1 ) · E ) ∗ ρ ( v ) ] , (22) D n + 1 ( u , v ) [ 1 − η ρ ( v ) ] = η [ ( D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ± rand ( 0 , 1 ) · E ) ∗ ρ ( v ) ] , (23) D n + 1 ( u , v ) = η [ ( D n ( γ , v ) ∗ [ 1 − ρ ( v ) ] ± rand ( 0 , 1 ) · E ) ∗ ρ ( v ) ] 1 − η ρ ( v )

Step 5) Determination of the success rate:

The pseudo-code of the proposed Rider-based HSA algorithm is illustrated in Table 1.

5.1. Experimental set-up

The proposed strategy is implemented in PYTHON with a PC with Windows 10 OS, 4GB RAM, and Intel i3 core processor. The number of PMs used is 6, the number of VM is equal to the task size, the population size is 5 and, the iteration used is 50.

5.2. Performance measures

The analysis of the methods is performed using Fairness, MOS, and QE parameters and is elaborated briefly in Section 4.2.

5.3. Comparative methods

The techniques adopted for the evaluation involve the Potential game-based optimization algorithm [8], Proactive resource allocation algorithm [10], QoE-aware resource allocation algorithm [29], Distributed algorithm [9], Yusen Li et al. [23], and Proposed Rider-based HSA.

5.4. Comparative analysis

The analysis of methods is done using Fairness, MOS, and QE parameters by varying the number of iterations. The analysis is done considering three games, size 100, 200, and 300, respectively.

OPEN IN VIEWER

Fig. 4.

Analysis of methods with game size 100 using a) Fairness, b) MOS, c) QE.

Figure 4 portrays the analysis of methods with game size 100 using Fairness, MOS, and QE parameters. The analysis of methods considering the parameter Fairness is portrayed in Fig. 4a). When the number of iterations is 10, the fairness values evaluated by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.106, 0.138, 0.138, 0.138, 0.138, and 0.148. Similarly, when the number of iterations is 50, the fairness values evaluated by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.135, 0.155, 0.156, 0.156, 0.156, and 0.177. The analysis of methods considering the MOS parameter is portrayed in Fig. 4b). When the number of iterations is 10, the MOS values evaluated using the potential game-based optimization algorithm, the Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, and a QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.759, 0.781, 0.784, 0.789, 0.792, and 0.793. Similarly, when the number of iterations is 50, the MOS values evaluated by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.889, 0.916, 0.917, 0.917, 0.917, and 0.921. The analysis of methods considering the parameter QE is portrayed in Fig. 4c). When the number of iterations is 10, the QE values are evaluated by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.361, 0.453, 0.454, 0.454, 0.454, and 0.455. Similarly, when the number of iterations is 50, the QE values evaluated by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.526, 0.560, 0.561, 0.563, 0.565, and 0.578.

OPEN IN VIEWER

Fig. 5.

Analysis of methods with game size 200 using a) Fairness, b) MOS, c) QE.

Figure 5 portrays the analysis of methods with game size 200 using Fairness, MOS, and QE parameters. The analysis of methods considering the parameter Fairness is portrayed in Fig. 4a). When the number of iterations is 10, the fairness values evaluated by the Potential game-based optimization algorithm, the Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.230, 0.440, 0.442, 0.444, 0.447, and 0.461. Similarly, when the number of iterations is 50, the fairness values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.401, 0.537, 0.539, 0.541, 0.545, and 0.547. The analysis of methods considering MOS is portrayed in Fig. 5b). When the number of iterations is 10, the MOS values estimated by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.712, 0.741, 0.742, 0.743, 0.745, and 0.750. Likewise, when the number of iterations is 50, the MOS values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.80, 0.824, 0.829, 0.831, 0.838, and 0.848. The analysis of methods considering the parameter QE is portrayed in Fig. 5c). When the number of iterations is 10, the QE values are measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.614, 0.961, 0.962, 0.962, 0.963, and 0.977. Likewise, when the number of iterations is 50, the QE values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.951, 0.988, 0.984, 0.984, 0.985, and 0.999.

OPEN IN VIEWER

Fig. 6.

Analysis of methods with game size 300 using a) Fairness, b) MOS, c) QE.

Figure 6 portrays the analysis of methods with game size 300 using Fairness, MOS, and QE parameters. The analysis of methods considering the parameter Fairness is portrayed in Fig. 6a). When the number of iterations is 10, the fairness values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.416, 0.846, 0.872, 0.894, 0.921, and 0.955. Similarly, when the number of iterations is 50, the fairness values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.538, 0.977, 0.980, 0.983, 0.990, and 0.999. The analysis of methods considering the MOS parameter is portrayed in Fig. 6b). When the number of iterations is 10, the MOS values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.735, 0.753, 0.754, 0.754, 0.754, and 0.818. Similarly, when the number of iterations is 50, the MOS values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.788, 0.799, 0.815, 0.821, 0.83, and 0.873. The analysis of methods considering the QE parameter is portrayed in Fig. 6c). When the number of iterations is 10, the QE values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.556, 0.847, 0.852, 0.865, 0.881, and 0.91. Similarly, when the number of iterations is 50, the QE values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 0.952, 0.965, 0.971, 0.981, 0.987, and 1.

OPEN IN VIEWER

Fig. 7.

Convergence graph. a) Game size 100, b) game size 200, and c) game size 300.

Figure 7 portrays the convergence analysis of methods with game sizes 100, 200, and 300. The analysis of convergence by considering game size 100 is portrayed in Fig. 7a). When the number of iterations is 10, the fitness values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 5326.509, 5340.325, 5342.521, 5289.075, 5342.250, and 5191.308. Similarly, when the number of iterations is 50, the fitness values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 5820.160, 5741.236, 5763.874, 5706.295, 5716.335, and 5735.412. The convergence analysis by game size 200 is portrayed in Fig. 7b). When the number of iterations is 10, the fitness values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 19552.850, 19950.152, 19742.654, 19749.215, 19751.125, and 19754.451. Similarly, when the number of iterations is 50, the fitness values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 20748.991, 20743.512, 20750.654, 20752.615, 20764.618, and 20789.215. The analysis by considering the game size 300 is portrayed in Fig. 7c). When the number of iterations is 10, the fitness values measured by the Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 045300.412, 45458.891, 45600.155, 45635.412, 45680.412, and 45720.652. Similarly, when the number of iterations is 50, the fitness values measured by Potential game-based optimization algorithm, Proactive resource allocation algorithm, Yusen Li et al., Distributed algorithm, QoE-aware resource allocation algorithm, and Proposed Rider-based HSA are 48600.412, 48647.132, 48670.512, 48673.536, 48681.158, and 48954.541.

Table 2 illustrates the analysis of methods considering fairness, MOS, and QE using game sizes 100, 200, and 300, respectively. Considering game size of 100, the performance improvement based on fairness using proposed Rider-based HSA with QoE-aware resource allocation algorithm is 11.299%, with the distributed algorithm is 11.29%, with Yusen Li et al., is 11.86%, with Proactive resource allocation algorithm is 11.864% and with Potential game-based optimization algorithm is 23.728%. The MOS computed by the proposed Rider-based HSA is 0.921. In contrast, the MOS of the Potential game-based optimization algorithm, Proactive resource allocation algorithm, QoE-aware resource allocation algorithm, Yusen Li et al., and Distributed algorithm are 0.890, 0.916, 0.918, 0.917, and 0.917. The QE computed by the proposed Rider-based HSA is 0.578. In contrast, the MOS of the Potential game-based optimization algorithm, Proactive resource allocation algorithm, QoE-aware resource allocation algorithm, Yusen Li et al., and Distributed algorithm are 0.527, 0.560, 0.565, 0.562, and 0.564. Considering game size = 200, the proposed Rider-based HSA measured maximal fairness of 0.547, maximal MOS of 0.848, and maximal QE of 0.999. Considering game size = 300, the proposed Rider-based HSA measured maximal fairness of 0.999, maximal MOS of 0.873, and maximal QE of 1. Through analysis, it is noted that the proposed Rider-based HSA offers superior performance in allocating resources with cloud infrastructures with maximal fairness of 0.999, maximal MOS of 0.873, and maximal QE of 1.