CN107168797A - Resource regulating method based on dynamic game under cloud environment - Google Patents
Resource regulating method based on dynamic game under cloud environment Download PDFInfo
- Publication number
- CN107168797A CN107168797A CN201710335668.5A CN201710335668A CN107168797A CN 107168797 A CN107168797 A CN 107168797A CN 201710335668 A CN201710335668 A CN 201710335668A CN 107168797 A CN107168797 A CN 107168797A
- Authority
- CN
- China
- Prior art keywords
- user
- game
- resource scheduling
- cloud environment
- resource
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 62
- 230000001105 regulatory effect Effects 0.000 title abstract 2
- 230000006698 induction Effects 0.000 claims abstract description 13
- 230000008901 benefit Effects 0.000 claims description 22
- 230000008569 process Effects 0.000 claims description 13
- 230000006870 function Effects 0.000 claims description 11
- 230000009471 action Effects 0.000 claims description 7
- 239000000969 carrier Substances 0.000 claims description 4
- 230000001939 inductive effect Effects 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 5
- 238000013468 resource allocation Methods 0.000 description 5
- 238000004458 analytical method Methods 0.000 description 4
- 238000004364 calculation method Methods 0.000 description 4
- 238000011161 development Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000013459 approach Methods 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 238000011002 quantification Methods 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 230000007480 spreading Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- FKLFBQCQQYDUAM-UHFFFAOYSA-N fenpiclonil Chemical compound ClC1=CC=CC(C=2C(=CNC=2)C#N)=C1Cl FKLFBQCQQYDUAM-UHFFFAOYSA-N 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000012163 sequencing technique Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
- G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
- G06F9/5038—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5072—Grid computing
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5077—Logical partitioning of resources; Management or configuration of virtualized resources
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/10—Services
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2209/00—Indexing scheme relating to G06F9/00
- G06F2209/50—Indexing scheme relating to G06F9/50
- G06F2209/5021—Priority
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Business, Economics & Management (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Economics (AREA)
- Tourism & Hospitality (AREA)
- General Engineering & Computer Science (AREA)
- Strategic Management (AREA)
- Human Resources & Organizations (AREA)
- Marketing (AREA)
- General Business, Economics & Management (AREA)
- General Health & Medical Sciences (AREA)
- Primary Health Care (AREA)
- Mathematical Physics (AREA)
- Health & Medical Sciences (AREA)
- Development Economics (AREA)
- Game Theory and Decision Science (AREA)
- Entrepreneurship & Innovation (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention belongs to the scheduling of resource technical field based on cloud computing, and in particular to the resource regulating method based on dynamic game under a kind of cloud environment, comprise the following steps：Build the resource dispatching model based on dynamic game under cloud environment；Resource dispatching model based on dynamic game, the priority for selecting resource is distributed according to the attribute of each user task height；Take task attribute identical user first to file first to select the strategy of allocation priority, and the income of each user is defined as to its QoS satisfaction；The Nash Equilibrium Solution of game is solved using reverse induction.The present invention is directed to multiple users resource competing problem caused by submission task simultaneously under cloud environment, set up cloud environment dynamic game resource dispatching model, the resource contention between each user is modeled and analyzed using dynamic game theory, the QoS demand of all users is met as much as possible；So as to meet the demand of each user to the full extent；The Nash Equilibrium Solution of Dynamic Game Model is solved using reverse induction, it is achieved thereby that resource most rationally effective configuration.
Description
Technical Field
The invention belongs to the technical field of resource scheduling based on cloud computing, and particularly relates to a resource scheduling method based on dynamic game in a cloud environment.
Background
Cloud computing is an emerging computing model developed on the basis of technologies such as grid computing, parallel computing and P2P. A large number of computing resources, storage resources and software resources stored on a data center cluster are linked together (including hardware resources such as a CPU (Central processing Unit), a memory, a hard disk and the like, and software resources such as a development environment, an application program and the like), centralized and unified management is carried out, a large-scale shared virtual resource pool is formed, and is provided for users to use as required, so that cloud services which are 'come-and-go-as-you-go' and seem 'unlimited' in capacity are provided for the users. With the rapid development of distributed technologies, cloud computing has become a key research field. Cloud computing is built on an Architecture (SOA) and provides computing resources in a Service manner, and users can obtain cloud services as required.
With the rapid development of cloud computing, mass resources are integrated into the cloud, user requirements are continuously increased, services provided by a cloud computing center are continuously increased, and huge resource scheduling pressure is faced. Because the cloud computing system is in a dynamic environment and the user population is huge, each application program has continuously changing resource requirements, so that the performance requirement of the application program is dynamically met[8]. On the other hand, the cloud computing uses a virtualization technology to shield the complexity of bottom hardware, and the flexibility is improved. In a multi-user environment, applications for a large number of users run on one physical device, sharing hardware and storage devices. On-demand resource supply and multi-user resource sharing of cloud computing cause the problem of cloud computing resource scheduling to become a security problem in subsequent cloud computingThe latter second major challenge.
In the cloud computing service resource scheduling process, a plurality of users submit task requests in sequence, and the task requests can be divided into a plurality of user groups according to time nodes of the requests. The resource allocation method requires the same type of resources, but the user group submitted first is ensured not to monopolize the type of resources in the scheduling process, so that resource competition among different user groups is formed. In order to meet the requirements of each user group, satisfy the constraint conditions provided by the user groups, such as task completion time, cost required by task completion and the like, and achieve the most reasonable and effective use and configuration of resources, a competition model based on dynamic game needs to be established, and a fair and effective resource scheduling method is designed, is used for solving the competition problem of non-simultaneous resource application by multiple users in cloud service resource scheduling, and not only improves the resource scheduling efficiency, but also ensures the fairness of resource allocation.
In the prior art, resource scheduling based on an intelligent optimization algorithm is generally adopted, and the intelligent algorithm is applied to cloud computing resource scheduling from the overall benefit of a scheduling center, so that the resource scheduling efficiency is improved, and the performance of a system is ensured. But the disadvantages are that the overall benefits of the scheduling center are taken as the main, the resource requirements of all users cannot be met, and the fairness of resource allocation cannot be ensured.
The other resource scheduling based on the game theory meets the characteristics of individual rationality and incentive compatibility, and has the disadvantages of excessive pursuit of cloud computing resource price and no guarantee of other requirements of users, namely, no guarantee of quality of service (QoS) of the users.
The game theory is one of the most basic theories of economics, is used for solving the problems of competition and mutual balance among different individuals, and is considered as the largest achievement obtained in the social science field of the 20 th century in western social science. The game theory is used for solving the problems of competition and mutual balance among different individuals and is considered as the largest achievement in the social science field of the 20 th century in western social science. Game theory, as a theory for studying participant competition, is of great value in modeling and analyzing competition between different individuals. Aiming at the problem of competition of non-simultaneous resource application by multiple users in cloud service resource scheduling, the invention provides a reasonable and effective resource scheduling model and method based on a dynamic game theory, which are used for solving the problem of resource competition of the multiple users in a cloud environment and improving the resource scheduling efficiency.
Disclosure of Invention
The invention provides a resource scheduling method based on dynamic game under cloud environment, aiming at the problems that the prior art has the resource scheduling based on an intelligent optimization algorithm, mainly takes the overall benefits of a scheduling center, can not meet the resource requirements of all users, can not ensure the fairness of resource allocation, has the resource scheduling based on game theory, excessively pursues the price of cloud computing resources, and does not ensure other requirements of the users, namely, does not ensure the service quality of the users.
The technical scheme of the invention is as follows: a resource scheduling method based on dynamic game in a cloud environment comprises the following steps:
step 1: constructing a resource scheduling model based on dynamic game under a cloud environment;
step 2: based on a resource scheduling model of a dynamic game, the priority of the selected resources is distributed according to the attribute of each user task;
and step 3: firstly applying for a strategy of firstly selecting and distributing priorities for users with the same task attributes, and defining the benefit of each user as the satisfaction degree of the QoS of each user;
and 4, step 4: and solving the Nash equilibrium solution of the game by using a reverse induction method.
In the resource scheduling method based on the dynamic game in the cloud environment, the resource scheduling in the cloud environment in step 1 means that on the basis of resource virtualization, a resource scheduling center dynamically allocates computing resources required by each user to execute tasks, so as to provide a feasible environment for executing the tasks; in the resource scheduling process under the cloud environment, physical resources are virtualized into virtual units by a cloud system and serve as carriers for executing tasks.
The resource scheduling method based on dynamic game in cloud environment, the dynamic game resource scheduling model in cloud environment is a quintuple, i.e. MCED-GRSM ═ N, T, S, I, U, where: n ═ N (N)1,N2,…,Nn) The method is characterized by comprising the following steps that a game participant set is provided, and participants are all users sending task requests in a certain time segment; t ═ T (T)1,T2,…,Tn) Is the action sequence of the participants, namely the sequence of the resources selected by the users in a certain time segment; s ═(S1,S2,…,Sn) Is the policy space of the participant and,representing participant NiEach participant has more than 1 strategy, namely h is more than or equal to 1;
I＝(I1,I2,…,In) Is the set of information of the participant that,representing participant NiEach participant should have more than 1 strategy, namely k is more than or equal to 1;
U＝(U1,U2,…,Un) Is the set of revenue functions for the participant,indicating that user n selects policy s after user 1, 2, …, n-1 actionnThe profit of (2); the profit function represents the level of profit that a participant can receive from a game, and is determined by the policies of all participants together, and the profits obtained by different policy combinations of the participants are different.
According to the resource scheduling method based on the dynamic game in the cloud environment, the scheduling model meets three assumptions, namely: rational assumption is that: the method comprises the following steps that all users are assumed to be completely rational, and a task request which has no meaning and occupies resources maliciously cannot be sent due to the fact that the maximum benefit is obtained; the type assumption is that: the proposed QoS is different assuming that the requirements of different users are different; the benefit assumption is that: assuming that the target of all users is to request resources to complete tasks on the premise of meeting the QoS of the users, the target of the resource scheduling center is to meet the requirements of all users as far as possible and feed back the resources to complete the tasks.
In the resource scheduling method based on dynamic game in cloud environment, the profit of the user in the step 3 is defined as the satisfaction of the QoS of the user measured by using a cloud environment resource scheduling game tree, the cloud environment resource scheduling game tree is represented by a triple (N, S, U), wherein N represents all node sets and represents the set of all users in resource scheduling; s is a set of directed edges in the game tree and represents the strategy of users in resource scheduling; u is the set of user profits, representing the profits obtained under different policies.
In the resource scheduling method based on dynamic game in cloud environment, the satisfaction degree of the QoS is measured by the income of each user, namely Ui(s1,…,si)＝1Q1+2Q2+...+nQn+ …, where Q represents a quality of service indicator,1,2,…,nrepresenting the user's weight for each type of metric,1,2,…,n∈(0,1)。iQirepresenting the satisfaction degree of the user on the service quality of the i-type resource; and the profit of the resource scheduling center is the total profit of all users, namely:
the resource scheduling method based on the dynamic game in the cloud environment comprises the following specific steps of: a method of starting from a directly preceding section of a game ending section and then reversely inducing through a game tree is called as a reverse induction method in the game; the solution is started from the bottom of the expanded game tree, the sub-game of the user n is considered, and if the user n-1 selects the strategySlightly less thanThen for user n a policy is selectedRather than selecting any of the other policies, as such, when user n-1 selects a policyThe optimal strategy for user n isEach user knows this information, so user n-1 will select a policyTo maximize their benefits, thus solving for sub-equilibrium game solutionsBy analogy, the equilibrium game solution is finally solved
The resource scheduling method based on dynamic game in the cloud environment, and the strategy in the dynamic game resource scheduling model in the cloud environmentIs a nash equalization, if for all i ∈ N,is thatI.e. for all si∈SiAnd all i ∈ N, having:wherein,representing user i selecting the optimal policy after user i-1 actionThe yield of (a) to (b) is,meaning that user i selects a non-optimal policy s after user i-1 actsiThe gain of (1).
The invention has the beneficial effects that: aiming at the problem of resource competition caused by simultaneous task submission of a plurality of users in a cloud environment, a cloud environment dynamic game resource scheduling model is established, and the resource competition among the users is modeled and analyzed by using a dynamic game theory, so that the QoS requirements of all the users are met as much as possible; a revenue function is established based on the weight of the user to each index, and the difference of each user to the type and the demand degree of the resource is considered all around; an optimal resource selection strategy is designed, users with high task levels are preferentially ensured to select task resources first, and the principle of applying for first selection is adopted for users with the same task levels, so that the requirements of each user are met to the greatest extent; and solving the Nash equilibrium solution of the dynamic game model by using a reverse induction method, thereby realizing the most reasonable and effective allocation of resources.
Drawings
FIG. 1 is a block diagram of a scheduling method of the present invention;
FIG. 2 is a schematic diagram of a cloud environment resource scheduling game tree structure;
FIG. 3 is a schematic diagram of a resource scheduling structure of a cloud environment;
FIG. 4 is a schematic diagram of a cloud environment resource scheduling game tree structure of a high-level task;
FIG. 5 is a schematic diagram of a low-level task cloud environment resource scheduling game tree structure;
Detailed Description
Example 1: with reference to fig. 1 to 5, a resource scheduling method based on dynamic gaming in a cloud environment includes the following steps:
step 1: constructing a resource scheduling model based on dynamic game under a cloud environment; step 2: based on a resource scheduling model of a dynamic game, the priority of the selected resources is distributed according to the attribute of each user task; and step 3: firstly applying for a strategy of firstly selecting and distributing priorities for users with the same task attributes, and defining the benefit of each user as the satisfaction degree of the QoS of each user; and 4, step 4: and solving the Nash equilibrium solution of the game by using a reverse induction method.
Specifically, resource scheduling in the cloud environment in step 1 means that on the basis of resource virtualization, a resource scheduling center dynamically allocates computing resources required by each user to execute tasks, so as to provide a feasible environment for executing the tasks; in the resource scheduling process under the cloud environment, physical resources are virtualized into virtual units by a cloud system and serve as carriers for executing tasks.
Specifically, the cloud environment dynamic game resource scheduling model is a quintuple, that is, MCED-GRSM ═ N, T, S, I, U, where: n ═ N (N)1,N2,…,Nn) The method is characterized by comprising the following steps that a game participant set is provided, and participants are all users sending task requests in a certain time segment; t ═ T (T)1,T2,…,Tn) Is the action sequence of the participants, namely the sequence of the resources selected by the users in a certain time segment; s ═(S1,S2,…,Sn) Is the policy space of the participant and,representing participant NiEach participant of the policy space ofMore than 1 strategy is needed, namely h is more than or equal to 1;
I＝(I1,I2,…,In) Is the set of information of the participant that,representing participant NiEach participant should have more than 1 strategy, namely k is more than or equal to 1;
U＝(U1,U2,…,Un) Is the set of revenue functions for the participant,indicating that user n selects policy s after user 1, 2, …, n-1 actionnThe profit of (2); the profit function represents the level of profit that a participant can receive from a game, and is determined by the policies of all participants together, and the profits obtained by different policy combinations of the participants are different.
According to the resource scheduling method based on the dynamic game in the cloud environment, the scheduling model meets three assumptions, namely: rational assumption is that: the method comprises the following steps that all users are assumed to be completely rational, and a task request which has no meaning and occupies resources maliciously cannot be sent due to the fact that the maximum benefit is obtained; the type assumption is that: the proposed QoS is different assuming that the requirements of different users are different; the benefit assumption is that: assuming that the target of all users is to request resources to complete tasks on the premise of meeting the QoS of the users, the target of the resource scheduling center is to meet the requirements of all users as far as possible and feed back the resources to complete the tasks.
Specifically, the profit of the users in step 3 is defined as the satisfaction of the QoS thereof, which is measured by using a cloud environment resource scheduling game tree, wherein the cloud environment resource scheduling game tree is represented by a triple (N, S, U), wherein N represents all node sets and represents the sets of all users in resource scheduling; s is a set of directed edges in the game tree and represents the strategy of users in resource scheduling; u is the set of user profits, representing the profits obtained under different policies.
In particular, QoS satisfaction is measured by the revenue of each user, i.e., Ui(s1,…,si)＝1Q1+2Q2+...+nQn+ …, where Q represents a quality of service indicator,1,2,…,nrepresenting the user's weight for each type of metric,1,2,…,n∈(0,1)。iQirepresenting the satisfaction degree of the user on the service quality of the i-type resource; and the profit of the resource scheduling center is the total profit of all users, namely:
specifically, step 4 specifically includes: a method of starting from a directly preceding section of a game ending section and then reversely inducing through a game tree is called as a reverse induction method in the game; the solution is started from the bottom of the expanded game tree, the sub-game of the user n is considered, and if the user n-1 selects the strategyThen for user n a policy is selectedRather than selecting any of the other policies, as such, when user n-1 selects a policyThe optimal strategy for user n isEach user knows this information, so user n-1 will select a policyTo maximize their benefits, thus solving for sub-equilibrium game solutionsBy analogy, finally findSolving a balanced game solution
Specifically, in the cloud environment dynamic game resource scheduling model, the strategyIs a nash equalization, if for all i ∈ N,is thatI.e. for all si∈SiAnd all i ∈ N, having:wherein,representing user i selecting the optimal policy after user i-1 actionThe yield of (a) to (b) is,meaning that user i selects a non-optimal policy s after user i-1 actsiThe gain of (1).
Embodiment 2, with reference to fig. 1 to 5, a resource scheduling method based on dynamic gaming in a cloud environment is provided, where resource scheduling in the cloud environment refers to that a resource scheduling center dynamically allocates computing resources required by each user to execute a task on the basis of resource virtualization, so as to provide a feasible environment for executing the task, and is a basis for smoothly implementing various tasks. In other words, in the process of scheduling the cloud environment resources, the physical resources are virtualized by the cloud system into virtual units, which serve as carriers for executing tasks. The user's task often corresponds to an optimal virtual unit type, and any sufficient physical resources (such as various sensors, computers, databases, etc.) can create these corresponding virtual units, which can then be assigned to each user to complete their task. However, different creation schemes directly affect the quality of service (QoS) obtained by users, i.e. the efficiency of performing tasks by users, so QoS is a main target for users to compete.
Dynamic game theory refers to the fact that the actions of participants are in a sequential order, and the actions of the participants can observe the selection of the former and make corresponding selections according to the selection. While the extended game describes a group of game sequences in a tree form, the full information game refers to that each game participant knows the income condition of other participants selecting different strategies and also knows all the previous decisions. The multi-user service resource scheduling is characterized as follows: (1) the users submit task requests at different time nodes according to respective requirements, the task requests can be considered to be performed in sequence, and the task requests are divided into different user groups according to the request time of the users; (2) while cloud computing resource pools approach infinity, resource performance differs. If a certain high-performance resource is used by a plurality of users, the performance of the resource can be greatly reduced, so that the strategy of the former user can influence the strategy selection of the latter user, namely the user strategies are mutually restricted; (3) the cloud computing scheduling center masters the sequence, the request content and the income function of the user application. Therefore, the process of multi-user service resource scheduling can be regarded as the process of a complete information spreading game in a dynamic game, so that the invention establishes a multi-user resource scheduling model based on the complete information spreading game in a cloud computing resource scheduling center.
Model assumptions, assume 1. rational assumptions: it is assumed that each user is completely rational and does not send a meaningless and maliciously occupied resource task request for obtaining the maximum profit. Hypothesis 2. type hypothesis: the proposed QoS varies, given the different needs of different users. Hypothesis 3. benefit hypothesis: it is assumed that all users aim to request resources to complete their tasks while satisfying their own QoS. The resource scheduling center aims to meet the requirements of all users as far as possible and feed back resources to complete the tasks of the users.
Model definition
Definition 1, Cloud environment dynamic gaming Resource Scheduling model MCED-GRSM (milery Cloud environment dynamic Resource Scheduling model) is a quintuple MCED-GRSM ═ (N, T, S, I, U), where:
1)N＝(N1,N2,…,Nn) Is the set of participants in the game. Participants are independent decisions, individuals or organizations that independently undertake outcomes for participating in a game, and the definition of participants is different in different instances. In this context, a participant is a user who sends a task request for a certain time segment.
2)T＝(T1,T2,…,Tn) Is the order of the participant's actions. In the cloud environment, resource selection and sequencing are firstly carried out according to the task attributes, namely, the users with high task level select available resources to complete the task; and then users with the same task level adopt a first-application first-selection ordering principle.
3)S＝(S1,S2,…,Sn) Is the policy space of the participant. SiRepresenting participant NiEach participant should have more than 1 strategy, namely h is more than or equal to 1. In a cloud environment, the strategy of each user adopts a principle of selecting optimal resources.
4)I＝(I1,I2,…,In) Is the information set of the participant.Representing participant NiEach participant should have more than 1 strategy, i.e. k is more than or equal to 1. In this context, the selection policy of the previous user is known when the user selects a resource.
5)U＝(U1,U2,…,Un) Is the participant's set of revenue functions.Indicating that user n selects policy s after user 1, 2, …, n-1 actionnThe gain of (1). The profit function represents the level of profit that a participant can receive from a game, and is determined by the policies of all participants together, and the profits obtained by different policy combinations of the participants are different. In a cloud environment, the participant revenue function is the satisfaction of the user's QoS.
Definition 2, cloud environment resource scheduling game tree is a representation of a policy path often used to represent each benefit realized in the scheduling process. It has the general tree structure, represented by a triple representation (N, S, U), as shown in fig. 2. Wherein N represents all node sets and represents the set of all users in resource scheduling; s is a set of directed edges in the game tree and represents the strategy of users in resource scheduling; u is the set of user profits, representing the profits obtained under different policies.
Income quantitative calculation and balanced analysis based on dynamic game under cloud environment include, (1) income quantitative calculation:
quantitative calculation of user profits in cloud environment resource scheduling is the basis of subsequent scheduling game analysis, and the resource scheduling result is directly influenced. Therefore, it is very necessary to make reasonable profit quantification of the policy of each user. In the actual resource scheduling process, the resource scheduling center has almost infinite resources and excellent resource performance difference; the users applying for different tasks have different weights for the resource performance. The resource scheduling center can meet the QoS of all users as much as possible, and feeds back resources to execute tasks of the users, so that benefits are obtained. Conversely, if the QoS of all users cannot be satisfied as much as possible, the efficiency is reduced and the loss is obtained.
The benefit of each user is considered herein to be its satisfaction of QoS, namely:
Ui(s1,…,si)＝1Q1+2Q2+...+nQn+…
where Q represents a quality of service indicator such as response time, reliability, privacy, etc.1,2,…,nRepresenting the user's weight for each type of metric,1,2,…,n∈(0,1)。iQirepresenting the satisfaction of the user on the service quality of the i-type resource.
And the profit of the resource scheduling center is the total profit of all users, namely:
(2) and (3) equilibrium analysis: any user applying for resources hopes to obtain high-quality resources of the resource scheduling center and meet the QoS of the user, and therefore the task is completed. If the resource scheduling center cannot meet its QoS, the user benefit is reduced. Therefore, in the face of different QoS of all resource application users, how to allocate the resource selection strategy and meet the QoS of all the users as far as possible is a key problem of resource scheduling in the cloud environment.
In the resource scheduling process, each user selects high-quality resources in sequence according to the attribute of the submitted task, and the latter user can only select resources according to the behavior of the former user so as to meet the QoS of the user as much as possible and obtain the maximum profit U. The method adopts a reverse induction in games method in the game theory to solve the Nash equilibrium solution of the game.
Definition 3, inverse induction method: the method of starting from the directly preceding section of the game's final section and then reverse induction through the game tree is called reverse induction in the game. The solution starts at the bottom of the extended game tree. Considering the sub-game of user n, if user n-1 selects a strategyThen for user n a policy is selectedRather than selecting any of the other strategies. Similarly, when user n-1 selects a policyThe optimal strategy for user n isEach user knows this information, so user n-1 will select a policyTo maximize their benefits, thus solving for sub-equilibrium game solutionsBy analogy, the equilibrium game solution is finally solved
Definitions 4 strategies in the MCED-GRSM modelIs a nash equalization, if for all i ∈ N,is thatI.e. for all si∈SiAnd all i ∈ N, having:
wherein,indicating that user i is a userSelecting an optimal policy after an i-1 actionThe yield of (a) to (b) is,meaning that user i selects a non-optimal policy s after user i-1 actsiThe gain of (1).
Specifically, an example of cloud environment resource scheduling is shown in fig. 3. The example describes a resource scheduling problem in a virtualized cloud environment, a resource pool of a resource scheduling center approaches infinity, and QoS indexes of users have response time, stability and confidentiality. Four users submit tasks to the resource scheduling center in a certain time slice, and the QoS of each user is different, namely the weight of different types of resources is different. In the resource scheduling process, the resource scheduling center firstly allocates the sequence of resource selection of each user according to the level of the task attribute, and then allocates the sequence of the users with the same task level by applying a first selection principle. And the latter user can only select resources according to the behavior of the former user to satisfy the own QoS as much as possible. And the scheduling model generates a game data table 2 according to the existing information.
Table 2 cloud environment resource scheduling data table
And calculating income quantification of different strategies selected by each user after the cloud environment resource scheduling game data is determined, as shown in tables 3 and 4.
Table 3 cloud environment resource scheduling user profits (high-level task)
Table 4 cloud environment resource scheduling user profits (low-level tasks)
And after income quantitative calculation, inputting the data into Gambit game software for balanced analysis. The game tree is thus obtained as shown in fig. 4 and 5.
The experimental result shows that only one Nash equilibrium solution can be found from the games of the high-level and low-level tasks respectively to form the Nash equilibrium solution for the cloud environment resource scheduling, and the result is as follows:i.e. four users will each select the second policy.
The nash equilibrium can be interpreted as: in the process of scheduling the resources in the cloud environment, firstly, the resource allocation of high-level tasks is guaranteed, then, each user of the same-level task performs actions according to the strategy of the previous user, and high-quality resources are selected as far as possible to execute the tasks, so that the benefit of the user is maximized. That is, in nash equalization, each user selects the optimal resources to perform the task. The results show that the cloud environment resource scheduling model and the cloud environment resource scheduling method provided by the invention can more reasonably and effectively reflect the influence of strategy income on the task execution of the user, and can effectively perform optimal resource scheduling.
Claims (8)
1. A resource scheduling method based on dynamic game under a cloud environment is characterized by comprising the following steps:
step 1: constructing a resource scheduling model based on dynamic game under a cloud environment;
step 2: based on a resource scheduling model of a dynamic game, the priority of the selected resources is distributed according to the attribute of each user task;
and step 3: firstly applying for a strategy of firstly selecting and distributing priorities for users with the same task attributes, and defining the benefit of each user as the satisfaction degree of the QoS of each user;
and 4, step 4: and solving the Nash equilibrium solution of the game by using a reverse induction method.
2. The resource scheduling method based on the dynamic game under the cloud environment according to claim 1, wherein the resource scheduling under the cloud environment in the step 1 is that on the basis of resource virtualization, a resource scheduling center dynamically allocates computing resources required by each user to execute a task, so as to provide a feasible environment for executing the task; in the resource scheduling process under the cloud environment, physical resources are virtualized into virtual units by a cloud system and serve as carriers for executing tasks.
3. The resource scheduling method based on the dynamic game under the cloud environment according to claim 1, wherein: the cloud environment dynamic game resource scheduling model is a quintuple, namely MCED-GRSM ═ N, T, S, I, U, wherein: n ═ N (N)1,N2,…,Nn) The method is characterized by comprising the following steps that a game participant set is provided, and participants are all users sending task requests in a certain time segment; t ═ T (T)1,T2,…,Tn) Is the action sequence of the participants, namely the sequence of the resources selected by the users in a certain time segment; s ═(S1,S2,…,Sn) Is the policy space of the participant and,representing participant NiEach participant has more than 1 strategy, namely h is more than or equal to 1;
I＝(I1,I2,…,In) Is the set of information of the participant that,representing participant NiEach participant should have more than 1 strategy, namely k is more than or equal to 1;
U＝(U1,U2,…,Un) Is the set of revenue functions for the participant,s2∈S2,…,sn∈Sn,Un(s1,s2,…,sn) Indicating that user n selects policy s after user 1, 2, …, n-1 actionnThe profit of (2); the profit function represents the level of profit that a participant can receive from a game, and is determined by the policies of all participants together, and the profits obtained by different policy combinations of the participants are different.
4. The resource scheduling method based on dynamic gaming in cloud environment according to claim 1, wherein the scheduling model satisfies three assumptions, namely: rational assumption is that: the method comprises the following steps that all users are assumed to be completely rational, and a task request which has no meaning and occupies resources maliciously cannot be sent due to the fact that the maximum benefit is obtained; the type assumption is that: the proposed QoS is different assuming that the requirements of different users are different; the benefit assumption is that: assuming that the target of all users is to request resources to complete tasks on the premise of meeting the QoS of the users, the target of the resource scheduling center is to meet the requirements of all users as far as possible and feed back the resources to complete the tasks.
5. The method for resource scheduling based on dynamic gaming in cloud environment according to claim 1, wherein the profit of the user in step 3 is defined as satisfaction of QoS thereof measured by using a cloud environment resource scheduling game tree, the cloud environment resource scheduling game tree is represented by a triple representation (N, S, U), where N represents a set of all nodes and represents a set of all users in resource scheduling; s is a set of directed edges in the game tree and represents the strategy of users in resource scheduling; u is the set of user profits, representing the profits obtained under different policies.
6. The resource scheduling method based on the dynamic game under the cloud environment according to claim 5, wherein: the satisfaction of the QoS is measured by the revenue of each user, i.e. Ui(s1,…,si)＝1Q1+2Q2+...+nQn+ …, where Q represents a quality of service indicator,1,2,…,nrepresenting the user's weight for each type of metric,1,2,…,n∈(0,1)。iQirepresenting the satisfaction degree of the user on the service quality of the i-type resource; and the profit of the resource scheduling center is the total profit of all users, namely:
7. the resource scheduling method based on the dynamic game under the cloud environment according to claim 1, wherein: the step 4 specifically comprises the following steps: a method of starting from a directly preceding section of a game ending section and then reversely inducing through a game tree is called as a reverse induction method in the game; the solution is started from the bottom of the expanded game tree, the sub-game of the user n is considered, and if the user n-1 selects the strategyThen for user n a policy is selectedRather than selecting any of the other policies, as such, when user n-1 selects a policyThe optimal strategy for user n isEach user knows this information, so user n-1 will select a policyTo maximize their benefits, thus solving for sub-equilibrium game solutionsBy analogy, the equilibrium game solution is finally solved
8. The resource scheduling method based on dynamic game under cloud environment of claim 1, wherein in the resource scheduling model of dynamic game under cloud environment, the policyIs a nash equalization, if for all i ∈ N,is thatI.e. for all si∈SiAnd all i ∈ N, having:wherein,representing user i selecting the optimal policy after user i-1 actionThe yield of (a) to (b) is,meaning that user i selects a non-optimal policy s after user i-1 actsiThe gain of (1).
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710335668.5A CN107168797A (en) | 2017-05-12 | 2017-05-12 | Resource regulating method based on dynamic game under cloud environment |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710335668.5A CN107168797A (en) | 2017-05-12 | 2017-05-12 | Resource regulating method based on dynamic game under cloud environment |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN107168797A true CN107168797A (en) | 2017-09-15 |
Family
ID=59815573
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710335668.5A Pending CN107168797A (en) | 2017-05-12 | 2017-05-12 | Resource regulating method based on dynamic game under cloud environment |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107168797A (en) |
Cited By (18)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109218440A (en) * | 2018-10-12 | 2019-01-15 | 上海拟态数据技术有限公司 | A kind of mimicry web server isomery execution body dynamic dispatching method of displaying |
| CN109460295A (en) * | 2018-10-19 | 2019-03-12 | 中南大学 | A kind of edge calculations performance optimization method based on multi-user's competitive behavior model |
| CN109739628A (en) * | 2018-12-28 | 2019-05-10 | 北京工业大学 | A kind of cloud computing method for scheduling task based on expense |
| CN109901050A (en) * | 2019-02-25 | 2019-06-18 | 哈尔滨师范大学 | A kind of three dimension system chip testing method for optimizing resources and system |
| CN110266770A (en) * | 2019-05-30 | 2019-09-20 | 湖南大学 | Idle cloud resource dispatching method and device based on game theory |
| CN110365515A (en) * | 2019-05-30 | 2019-10-22 | 东南大学 | Service internet multi-tenant satisfaction measure based on extensive entropy |
| CN110505217A (en) * | 2019-08-05 | 2019-11-26 | 河北科技大学 | A kind of location privacy protection method merged based on game theory with block chain |
| CN110599051A (en) * | 2019-09-19 | 2019-12-20 | 桂林电子科技大学 | Sub-game perfect Nash balanced fetching method of two agents |
| CN110772798A (en) * | 2019-10-23 | 2020-02-11 | 桂林电子科技大学 | Method for searching Nash equilibrium sequence based on FIP structure |
| CN110825517A (en) * | 2019-09-29 | 2020-02-21 | 清华大学 | Distributed resource dynamic allocation method based on evolutionary game theory |
| CN110851268A (en) * | 2019-10-17 | 2020-02-28 | 中山大学 | Edge scheduling optimization method based on congestion game |
| CN111597047A (en) * | 2020-05-15 | 2020-08-28 | 北京金山云网络技术有限公司 | Service deployment method, device, electronic equipment and storage medium |
| CN112308279A (en) * | 2019-08-02 | 2021-02-02 | 南京理工大学 | Multi-server fund distribution method |
| CN113283785A (en) * | 2021-06-09 | 2021-08-20 | 广东工业大学 | Cooperative scheduling optimization method for multi-task manufacturing resources |
| CN113298392A (en) * | 2021-05-29 | 2021-08-24 | 西北工业大学 | Heterogeneous weapon target allocation method based on induction method |
| CN113658422A (en) * | 2021-07-26 | 2021-11-16 | 江苏大学 | Optimal scheduling method for unmanned electric vehicle |
| CN115208900A (en) * | 2022-07-15 | 2022-10-18 | 柏域信息科技（上海）有限公司 | Multi-cloud-architecture cloud service resource scheduling method based on block chain and game model |
| CN115438931A (en) * | 2022-08-22 | 2022-12-06 | 成都飞机工业（集团）有限责任公司 | Production line assembly operation scheduling method, device, equipment and medium |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103095788A (en) * | 2011-11-02 | 2013-05-08 | 佳都新太科技股份有限公司 | Cloud resource scheduling policy based on network topology |
| CN103677960A (en) * | 2013-12-19 | 2014-03-26 | 安徽师范大学 | Game resetting method for virtual machines capable of controlling energy consumption |
| US9413814B2 (en) * | 2010-09-29 | 2016-08-09 | Citrix Systems, Inc. | Systems and methods for providing quality of service via a flow controlled tunnel |
| CN106454849A (en) * | 2016-10-08 | 2017-02-22 | 重庆大学 | High-energy efficiency resource allocation method for cooperative cognitive radio network |
-
2017
- 2017-05-12 CN CN201710335668.5A patent/CN107168797A/en active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9413814B2 (en) * | 2010-09-29 | 2016-08-09 | Citrix Systems, Inc. | Systems and methods for providing quality of service via a flow controlled tunnel |
| CN103095788A (en) * | 2011-11-02 | 2013-05-08 | 佳都新太科技股份有限公司 | Cloud resource scheduling policy based on network topology |
| CN103677960A (en) * | 2013-12-19 | 2014-03-26 | 安徽师范大学 | Game resetting method for virtual machines capable of controlling energy consumption |
| CN106454849A (en) * | 2016-10-08 | 2017-02-22 | 重庆大学 | High-energy efficiency resource allocation method for cooperative cognitive radio network |
Non-Patent Citations (2)
| Title |
|---|
| 张健: "静态贝叶斯博弈在信息系统风险分析中的应用", 《计算机工程与应用》 * |
| 徐昕: "基于博弈论的云计算资源调度方法研究", 《中国优秀博士学位论文全文数据库 信息科技辑，第I139-1页》 * |
Cited By (26)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109218440A (en) * | 2018-10-12 | 2019-01-15 | 上海拟态数据技术有限公司 | A kind of mimicry web server isomery execution body dynamic dispatching method of displaying |
| CN109460295A (en) * | 2018-10-19 | 2019-03-12 | 中南大学 | A kind of edge calculations performance optimization method based on multi-user's competitive behavior model |
| CN109739628A (en) * | 2018-12-28 | 2019-05-10 | 北京工业大学 | A kind of cloud computing method for scheduling task based on expense |
| CN109901050A (en) * | 2019-02-25 | 2019-06-18 | 哈尔滨师范大学 | A kind of three dimension system chip testing method for optimizing resources and system |
| CN110266770A (en) * | 2019-05-30 | 2019-09-20 | 湖南大学 | Idle cloud resource dispatching method and device based on game theory |
| CN110365515A (en) * | 2019-05-30 | 2019-10-22 | 东南大学 | Service internet multi-tenant satisfaction measure based on extensive entropy |
| CN110266770B (en) * | 2019-05-30 | 2020-07-07 | 湖南大学 | Game theory-based idle cloud resource scheduling method and device |
| CN110365515B (en) * | 2019-05-30 | 2022-04-08 | 东南大学 | Service internet multi-tenant satisfaction degree measuring method based on generalization entropy |
| CN112308279A (en) * | 2019-08-02 | 2021-02-02 | 南京理工大学 | Multi-server fund distribution method |
| CN110505217A (en) * | 2019-08-05 | 2019-11-26 | 河北科技大学 | A kind of location privacy protection method merged based on game theory with block chain |
| CN110505217B (en) * | 2019-08-05 | 2021-11-02 | 河北科技大学 | Position privacy protection method based on game theory and block chain fusion |
| CN110599051A (en) * | 2019-09-19 | 2019-12-20 | 桂林电子科技大学 | Sub-game perfect Nash balanced fetching method of two agents |
| CN110825517A (en) * | 2019-09-29 | 2020-02-21 | 清华大学 | Distributed resource dynamic allocation method based on evolutionary game theory |
| CN110825517B (en) * | 2019-09-29 | 2020-09-08 | 清华大学 | Distributed resource dynamic allocation method based on evolutionary game theory |
| CN110851268A (en) * | 2019-10-17 | 2020-02-28 | 中山大学 | Edge scheduling optimization method based on congestion game |
| CN110851268B (en) * | 2019-10-17 | 2023-06-13 | 中山大学 | Edge scheduling optimization method based on congestion game |
| CN110772798A (en) * | 2019-10-23 | 2020-02-11 | 桂林电子科技大学 | Method for searching Nash equilibrium sequence based on FIP structure |
| CN111597047A (en) * | 2020-05-15 | 2020-08-28 | 北京金山云网络技术有限公司 | Service deployment method, device, electronic equipment and storage medium |
| CN113298392A (en) * | 2021-05-29 | 2021-08-24 | 西北工业大学 | Heterogeneous weapon target allocation method based on induction method |
| CN113298392B (en) * | 2021-05-29 | 2023-06-06 | 西北工业大学 | Heterogeneous weapon target distribution method based on induction method |
| CN113283785A (en) * | 2021-06-09 | 2021-08-20 | 广东工业大学 | Cooperative scheduling optimization method for multi-task manufacturing resources |
| CN113658422A (en) * | 2021-07-26 | 2021-11-16 | 江苏大学 | Optimal scheduling method for unmanned electric vehicle |
| CN115208900A (en) * | 2022-07-15 | 2022-10-18 | 柏域信息科技（上海）有限公司 | Multi-cloud-architecture cloud service resource scheduling method based on block chain and game model |
| CN115208900B (en) * | 2022-07-15 | 2024-03-15 | 柏域信息科技（上海）有限公司 | Multi-cloud architecture cloud service resource scheduling method based on blockchain and game model |
| CN115438931A (en) * | 2022-08-22 | 2022-12-06 | 成都飞机工业（集团）有限责任公司 | Production line assembly operation scheduling method, device, equipment and medium |
| CN115438931B (en) * | 2022-08-22 | 2024-03-15 | 成都飞机工业（集团）有限责任公司 | Method, device, equipment and medium for scheduling assembly operation of production line |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107168797A (en) | Resource regulating method based on dynamic game under cloud environment | |
| Liu et al. | A new service mechanism for profit optimizations of a cloud provider and its users | |
| US20190324819A1 (en) | Distributed-system task assignment method and apparatus | |
| Liu et al. | Strategy configurations of multiple users competition for cloud service reservation | |
| Liu et al. | Job scheduling model for cloud computing based on multi-objective genetic algorithm | |
| Li et al. | A framework of price bidding configurations for resource usage in cloud computing | |
| Mashayekhy et al. | Cloud federations in the sky: Formation game and mechanism | |
| Ge et al. | GA-based task scheduler for the cloud computing systems | |
| Choudhary et al. | A dynamic optimization algorithm for task scheduling in cloud environment | |
| WO2018113472A1 (en) | Method for scheduling resource, and server | |
| Zhu et al. | ANGEL: Agent-based scheduling for real-time tasks in virtualized clouds | |
| WO2017167025A1 (en) | Method and device for realizing task scheduling, and computer storage medium | |
| Mashayekhy et al. | A trust-aware mechanism for cloud federation formation | |
| CN110597639B (en) | CPU distribution control method, device, server and storage medium | |
| Li et al. | A distributed QoS-constraint task scheduling scheme in cloud computing environment: model and algorithm | |
| CN106412124B (en) | A kind of and sequence cloud service platform task distribution system and method for allocating tasks | |
| CN107562537B (en) | Cloud computing task scheduling method based on universal gravitation search | |
| CN103685492B (en) | Dispatching method, dispatching device and application of Hadoop trunking system | |
| CN112306642A (en) | Workflow scheduling method based on stable matching game theory | |
| Patra et al. | Game theoretic approach for real-time task scheduling in cloud computing environment | |
| Yang et al. | Multi-policy-aware MapReduce resource allocation and scheduling for smart computing cluster | |
| Parikh et al. | Double level priority based optimization algorithm for task scheduling in cloud computing | |
| CN106802822A (en) | A kind of cloud data center cognitive resources dispatching method based on moth algorithm | |
| Adrian et al. | Analysis of K-means algorithm for VM allocation in cloud computing | |
| Ananth et al. | Cooperative game theoretic approach for job scheduling in cloud computing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20170915 |