CN111443989B - Virtual machine placement method, device, equipment and storage medium based on harmony search - Google Patents

Abstract

The invention belongs to the technical field of cloud computing, and discloses a virtual machine placement method, device and equipment based on harmony search and a storage medium. The method comprises the following steps: acquiring a virtual machine set and a physical host set to be placed, and establishing a sound memory library according to the virtual machine set and the physical host set; generating a new harmony according to the preset harmony generation condition; performing fitness calculation on various harmony sounds and new harmony sounds in the harmony sound memory library, and updating harmony sounds in the harmony sound memory library according to a calculation result; determining a target harmony with the maximum fitness value according to the updating result, and taking the tone information of the target harmony as the optimal solution for placing the virtual machine; and placing the virtual machines in the virtual machine set into the physical hosts corresponding to the physical host set according to the optimal solution for placing the virtual machines. Under the condition that the resource utilization rate and the energy consumption of the physical host are both constrained, the low-energy optimization of virtual machine placement is formed by generating a new harmony, namely a new placement scheme.

Description

Virtual machine placement method, device, equipment and storage medium based on harmony search

technical field

The present invention relates to the technical field of cloud computing, and in particular to a harmony search-based virtual machine placement method, device, device and storage medium.

Background technique

The problem of high energy consumption in cloud computing data centers has become more and more prominent, and the energy consumption of hosts and cooling systems has constituted the main part of the operating costs of data centers. Inefficient utilization of physical hosts increases the energy costs of the data center. Through virtualization technology, several virtual machines can be virtualized on one physical host, and user applications can be executed in units of virtual machines. How to place virtual machines on the host becomes a key factor that ultimately affects the energy consumption of the host. The virtual machine placement problem is the process of placing a collection of virtual machines onto a physical host. Due to the heterogeneity of virtual machine resource requests and the difference in host resource provisioning capabilities, different virtual machine placement strategies will result in different host energy consumption. However, studies have shown that idle physical hosts still consume more than half of the energy consumption of fully loaded hosts. In order to reduce the overall energy consumption of hosts, a smaller number of hosts should be used as much as possible for virtual machine placement, so as to shut down completely unused hosts and save energy consumption of idle parts.

The harmony search mechanism is a highly efficient heuristic method. This method simulates the process of impromptu music performance. The player adjusts the pitch of the instrument impromptu. The goal is to play the most beautiful harmony through different pitch adjustments. It can be used in continuous spaces. Optimization problems can also be used for discrete space optimization problems. Based on this method, it is simple to implement and has less dependent parameters.

Contents of the invention

The main purpose of the present invention is to provide a virtual machine placement method, device, equipment and storage medium based on harmony search, aiming at solving the technical problem of how to realize virtual machine placement with less dependent parameters and low energy consumption.

In order to achieve the above object, the present invention provides a virtual machine placement method based on harmony search, the method comprising:

Obtain a set of virtual machines and a set of physical hosts to be placed, and establish a harmony memory bank according to the set of virtual machines and the set of physical hosts;

Generate a new harmony according to the preset harmony generation conditions;

Computing the fitness of various harmony in the harmony memory and the new harmony, and updating the harmony in the harmony memory according to the calculation result;

Determine the target harmony with the maximum fitness value according to the update result, and use the pitch information of the target harmony as the optimal solution for placing the virtual machine;

The virtual machines in the virtual machine set are placed in the physical hosts corresponding to the physical host set according to the optimal virtual machine placement solution.

Preferably, the step of obtaining the set of virtual machines and the set of physical hosts to be placed, and establishing a harmony memory bank according to the set of virtual machines and the set of physical hosts, specifically includes:

Obtain the number of physical hosts corresponding to the set of physical hosts and the number of virtual machines corresponding to the set of virtual machines;

Using the number of virtual machines as the number of tone information corresponding to various chords, randomly setting the tone information corresponding to various chords according to the number of physical hosts;

A harmony memory bank is established according to the number of preset harmony types, the number of tone information and the tone information.

Preferably, the step of generating a new harmony according to preset harmony generation conditions specifically includes:

randomly setting the number of tone information equal to the number of virtual machines according to the number of physical hosts, so as to obtain the harmony to be processed;

A harmony memory bank selection process and tone fine-tuning perturbation process are performed on the harmony to be processed, so as to obtain a processed new harmony.

Preferably, the step of performing harmony memory bank selection processing and tone fine-tuning disturbance processing on the harmony to be processed to obtain a processed new harmony specifically includes:

Generate a first random number pair corresponding to each tone information in the harmony to be processed, and randomly select a tone from the harmony memory bank according to the first random number pair and the preset harmony memory bank selection probability information, and replace the tone information corresponding to the harmony to be processed with the tone information;

Generate a second random number pair corresponding to each pitch information in the harmony to be processed, and perform pitch fine-tuning disturbance processing on the replaced pitch information according to the second random number pair, pitch adjustment probability, and disturbance bandwidth, so as to obtain a processing New harmony after.

Preferably, said generating the first random number pair corresponding to each tone information in the harmony to be processed, selecting the probability from the harmony memory according to the first random number pair and the preset harmony memory bank Before the step of randomly selecting tone information in the library, and replacing the tone information corresponding to the harmony to be processed with the tone information, it also includes:

Obtain the current number of iterations of the harmony memory bank;

The pitch adjustment probability and the disturbance bandwidth are updated according to the current number of iterations.

Preferably, the step of calculating the fitness of various harmony in the harmony memory and the new harmony, and updating the harmony in the harmony memory according to the calculation result, specifically include:

Computing the fitness of various harmony in the harmony memory and the new harmony;

Obtaining the candidate harmony with the smallest current fitness value in the harmony memory, and judging whether the fitness value of the new harmony is greater than the fitness value of the candidate harmony;

When the fitness value of the new harmony is greater than the fitness value of the candidate harmony, the candidate harmony is replaced by the new harmony, so as to realize the sum in the harmony memory sound update.

Preferably, after the step of determining the target harmony with the largest fitness value according to the update result, and using the pitch information of the target harmony as the optimal solution for virtual machine placement, the method further includes:

Detecting the current number of iterations of the current harmony memory bank, and judging whether the current number of iterations is less than the preset number of iterations;

When the current number of iterations is less than the preset number of iterations, returning to the step of generating a new harmony according to preset harmony generation conditions;

When the current number of iterations is equal to the preset number of iterations, output the optimal solution for virtual machine placement.

In addition, in order to achieve the above purpose, the present invention also proposes a virtual machine placement device based on harmony search, which includes: a harmony library establishment module, a fitness calculation module, an optimal solution acquisition module and a placement module, wherein;

The harmony library building module is used to obtain a set of virtual machines and a set of physical hosts to be placed, and establish a harmony memory bank according to the set of virtual machines and the set of physical hosts;

The fitness calculation module is used to generate a new harmony according to preset harmony generation conditions; it is also used to calculate the fitness of various harmony in the harmony memory and the new harmony, And update the harmony in the harmony memory bank according to the calculation result;

The optimal solution acquisition module is used to determine the target harmony with the largest fitness value according to the update result, and use the tone information of the harmony as the optimal solution for virtual machine placement;

The placement module is configured to place the virtual machines in the virtual machine set into physical hosts corresponding to the physical host set according to the optimal virtual machine placement solution.

In addition, in order to achieve the above object, the present invention also proposes a device for placing a virtual machine based on harmony search, which includes: a memory, a processor, and a device based on A virtual machine placement program based on harmony search, the virtual machine placement program based on harmony search is configured to implement the steps of the method for placing a virtual machine based on harmony search as described above.

In addition, in order to achieve the above object, the present invention also proposes a storage medium, the storage medium stores a virtual machine placement program based on harmony search, and the virtual machine placement program based on harmony search is implemented when the processor executes The steps of the virtual machine placement method based on harmony search as described above.

The present invention acquires a set of virtual machines and a set of physical hosts to be placed, and establishes a harmony memory library according to the set of virtual machines and the set of physical hosts; generates a new harmony according to preset harmony generation conditions; Carry out fitness calculations for various harmony in the harmony memory and the new harmony, and update the harmony in the harmony memory according to the calculation result; determine the target with the largest fitness value according to the update result Harmony, and use the tone information of the target harmony as the optimal solution for virtual machine placement; according to the optimal solution for virtual machine placement, place the virtual machines in the virtual machine set on the corresponding physical host set in the host. Under the condition that the resource utilization rate and energy consumption of the physical host are constrained, by generating a new harmony, that is, a new placement scheme, a low-energy optimization of virtual machine placement is formed, which improves the efficiency and effect of virtual machine placement.

Description of drawings

Fig. 1 is a schematic structural diagram of a virtual machine placement device based on a harmony search in a hardware operating environment related to the solution of an embodiment of the present invention;

Fig. 2 is a schematic flow chart of the first embodiment of the virtual machine placement method based on harmony search in the present invention;

FIG. 3 is a schematic flowchart of a second embodiment of the harmony search-based virtual machine placement method of the present invention;

Fig. 4 is a structural block diagram of the first embodiment of the harmony search-based virtual machine placement device of the present invention.

The realization of the purpose of the present invention, functional characteristics and advantages will be further described in conjunction with the embodiments and with reference to the accompanying drawings.

Detailed ways

It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Referring to FIG. 1 , FIG. 1 is a schematic structural diagram of a virtual machine placement device based on harmony search in a hardware operating environment involved in the solution of an embodiment of the present invention.

As shown in FIG. 1 , the virtual machine placement device based on harmony search may include: a processor 1001 , such as a central processing unit (Central Processing Unit, CPU), a communication bus 1002 , a user interface 1003 , a network interface 1004 , and a memory 1005 . Wherein, the communication bus 1002 is used to realize connection and communication between these components. The user interface 1003 may include a display screen (Display), an input unit such as a keyboard (Keyboard), and the optional user interface 1003 may also include a standard wired interface and a wireless interface. The network interface 1004 may optionally include a standard wired interface and a wireless interface (such as a wireless fidelity (WIreless-FIdelity, WI-FI) interface). The memory 1005 may be a high-speed random access memory (Random Access Memory, RAM) memory, or a stable non-volatile memory (Non-Volatile Memory, NVM), such as a disk memory. Optionally, the memory 1005 may also be a storage device independent of the aforementioned processor 1001 .

Those skilled in the art can understand that the structure shown in FIG. 1 does not constitute a limitation on the virtual machine placement device based on harmony search, and may include more or less components than those shown in the figure, or combine certain components, or Different component arrangements.

As shown in FIG. 1 , the memory 1005 as a storage medium may include an operating system, a network communication module, a user interface module, and a virtual machine placement program based on harmony search.

In the virtual machine placement device based on harmony search shown in Figure 1, the network interface 1004 is mainly used for data communication with the network server; the user interface 1003 is mainly used for data interaction with users; the virtual machine based on harmony search in the present invention The processor 1001 and memory 1005 in the machine placement device can be set in the harmony search-based virtual machine placement device, and the harmony search-based virtual machine placement device calls the harmony search-based virtual machine storage device stored in the memory 1005 through the processor 1001 virtual machine placement program, and execute the harmony search-based virtual machine placement method provided by the embodiment of the present invention.

An embodiment of the present invention provides a method for placing a virtual machine based on harmony search. Referring to FIG. 2 , FIG. 2 is a schematic flow chart of a first embodiment of a method for placing a virtual machine based on harmony search according to the present invention.

It should be noted that in the cloud computing environment, the energy consumption of the physical host mainly comes from the CPU, memory RAM, and storage system. Usually, the energy consumption of the CPU accounts for most of the energy consumption of the physical host. Dynamic voltage/frequency scaling (DVFS, Dynamic voltage and frequency scaling) is the most commonly used energy-saving technology for a single CPU. This technology mainly considers two states of CPU: idle state and load state. In an idle state (that is, without any execution load), the internal components of the CPU can be switched to a shutdown mode, thereby reducing the clock frequency of the CPU, and the CPU can run at a minimum operating frequency to save energy consumption. In the load state, the energy consumption of the CPU depends on the amount of load executed on the CPU and the utilization rate of the CPU. Studies have shown that the power consumption of a physical host is linearly related to its CPU utilization.

Define the host power consumption formula as:

Among them, P _{j, max} represents the maximum power consumption of the physical host h _j , that is, the power consumption when the physical host is fully loaded, P _j , _idle represents the minimum power consumption of the physical host h _j , that is, the power consumption when the physical host is idle, the The power consumption is usually 70% of the full load power consumption, u _{j, CPU} represents the CPU utilization of the physical host h _j .

It is easy to understand that, assuming that there are n virtual machines to be placed in the cloud computing environment, expressed as a set V={v ₁ , v ₂ ,...,v _n }, there are m available physical hosts, expressed as a set H = {h ₁ , h ₂ , . . . , h _m }. The problem of virtual machine placement is the process of mapping collections of virtual machines to physical hosts. Consider requests for three resource types during placement, including: CPU, memory RAM, and disk storage DISK. Let _{ri, CPU} , ri _{, RAM} and ri _{, DISK} denote the request amount of virtual machine v _i on CPU resource, memory RAM resource and storage DISK resource respectively, i=1, 2,..., n, c _{j, CPU} , c _{j, RAM} and c _{j, DISK} represent the provisioning capabilities of the physical host h _j on CPU resources, memory RAM resources and storage DISK resources respectively, j=1, 2, . . . , m. Let x _i,j represent the placement factor, indicating whether the virtual machine v _i is placed on the physical host h _j , which is a binary variable, and the expression of the placement factor is:

Let z _j represent the utilization factor of the physical host, indicating whether the physical host h _j is utilized during the virtual machine placement process, which is a binary variable, and the expression of the utilization factor is:

In order to save energy consumption of physical hosts, completely idle physical hosts need to be converted to sleep mode, so as to save energy consumption of idle physical hosts. Therefore, the energy consumption minimization formula is:

The corresponding constraints are as follows: the corresponding constraints of the virtual machine, to ensure that a virtual machine can only be placed on one physical host, the corresponding formula is as follows:

Placement factor constraints, indicating that the placement factor is a binary number that can only take the value 0 or 1, and the corresponding formula is as follows:

Using factor constraints, it indicates that the physical host utilization factor is a binary number that can only take the value 0 or 1, and the corresponding formula is as follows:

The memory constraint condition indicates that the amount of memory requested by the virtual machine cannot exceed the memory capacity of the host, and the corresponding formula is as follows:

The memory request constraints ensure that the memory resources requested by the virtual machine cannot exceed the memory capacity of the physical host. The corresponding formula is as follows:

The storage request constraints ensure that the storage resources requested by the virtual machine cannot exceed the storage capacity of the physical host. The corresponding formula is as follows:

In this embodiment, the virtual machine placement method based on harmony search includes the following steps:

Step S10, obtaining a set of virtual machines and a set of physical hosts to be placed, and establishing a harmony memory library according to the set of virtual machines and the set of physical hosts.

Step S10 specifically includes: obtaining the number of physical hosts corresponding to the set of physical hosts and the number of virtual machines corresponding to the set of virtual machines; using the number of virtual machines as the number of tone information corresponding to various chords, according to the physical host Randomly set the tone information corresponding to various harmony; according to the number of preset harmony types, the number of tone information and the tone information, a harmony memory bank is established.

Let a harmony h be expressed as:

X _h ＝[x _h,1 ,x _h,2 ,...,x _h,n ]

Among them, the element x _{h, k} in the vector represents the tone played by the kth instrument in the harmony h, and the tone corresponds to the serial number of the physical host where the virtual machine k is placed, and the value of the physical host serial number is within the interval [1, m] Integer value, h=1, 2, ..., HMS, HMS indicates the size of the harmony memory, HMS is the number of preset harmony types, which can be set according to the actual needs of the problem, k = 1, 2, ..., n, n represents the number of musical instruments, corresponding to the total number of virtual machines to be placed, that is, the corresponding number of tone information. In other words, a harmony represents a virtual machine placement scheme, which can be defined in an n-dimensional search space. A harmony in the harmony search mechanism under the virtual machine placement problem can only appear in the form of a discrete numerical sequence number between 1 and m, where m represents the maximum number of physical hosts.

In this embodiment, if the harmony h is X _h = [2, 1, 5, 4, 2, 3, 2, 1], it indicates that a total of 8 musical instruments play 8 tones, which represent the virtual machine placement scheme The meaning is: virtual machines v ₁ , v ₅ and v ₇ are placed on physical host h ₂ , virtual machines v ₂ and v ₈ are placed on physical host h ₁ , virtual machine v ₃ is placed on physical host h ₅ , virtual machine _v4 is placed on the physical host _h4 , and the virtual machine _v6 is placed on the physical host _h3 .

All possible harmony can form a matrix, defined as the harmony memory HM:

Step S20, generating a new harmony according to preset harmony generation conditions.

Step S20 specifically includes: randomly setting tone information equal to the number of virtual machines according to the number of physical hosts to obtain the harmony to be processed; performing harmony memory bank selection processing and tone fine-tuning disturbance processing on the harmony to be processed , to get the new processed harmony.

It should be noted that the process of selecting the harmony memory bank specifically includes: generating a first random number pair corresponding to each tone information in the harmony to be processed, and according to the first random number pair and the preset sum The sound memory selection probability randomly selects pitch information from the harmony memory, and replaces the pitch information corresponding to the harmony to be processed with the pitch information.

For each tone x _{h , k in harmony X h,} k=1, 2, ..., n, randomly generate a pair of random numbers, that is, the first pair of random numbers, the first pair of random numbers includes random The number r ₁ and the random number r ₂ , the two random numbers in the random number pair are both between (0, 1).

If r ₁ is less than the harmony memory bank selection probability HMCR, then randomly select a harmony HM[a][b] from the harmony memory bank HM to replace x _{h, k} , a=1, 2, ..., HMS, b=1, 2,..., n, that is, the tone x _{h, k} is updated as:

x _h,k = HM[a][b]

Otherwise, if r ₁ >HMCR, then the update value of x _{h, k} randomly generates an integer number in the interval [1, m], namely:

Among them, r ₂ represents a random number in the interval (0, 1).

It should be noted that the process of tone fine-tuning disturbance processing specifically includes: generating a second random number pair corresponding to each tone information in the chorus to be processed, and according to the second random number pair, tone adjustment probability and disturbance bandwidth pair The replaced tone information is subjected to tone fine-tuning perturbation processing to obtain the processed new harmony.

It is easy to understand that, for each tone x _{h , k} in harmony X h, k=1, 2, ..., n, a pair of random numbers is randomly generated, that is, the second pair of random numbers, the first pair of random numbers The random number pair includes a random number r ₃ and a random number r ₄ , and both of the two random numbers in the random number pair are between (0, 1).

While satisfying r ₁ <HMCR, if r ₃ is smaller than the pitch adjustment probability PAR, further fine-tuning disturbance is performed on the update value HM[a][b] of the previous step. The fine-tuning perturbation formula is:

Among them, r ₄ represents a random number in the interval (0, 1), and BW represents the disturbance bandwidth.

Since the placement scheme is only an integer value limited to the interval [1, m], that is, the value of x _{h, k} must be within the interval [1, m], and according to the update method of the fine-tuning disturbance formula, it may appear that the value is not in conditions within this range. Therefore, the optimized pitch fine-tuning perturbation formula is:

表示向下取整，m表示物理主机总量，即最大物理主机序号。Among them, mod means modulo operation,

Indicates rounding down, and m indicates the total number of physical hosts, that is, the maximum physical host serial number.

The first random number pair corresponding to each tone information in the harmony to be processed is generated, and randomly selected from the harmony memory bank according to the first random number pair and the preset harmony memory bank selection probability Before the step of selecting tone information and replacing the tone information corresponding to the harmony to be processed with the tone information, it also includes: obtaining the current iteration number of the harmony memory bank; adjusting the probability and pitch according to the current iteration number The perturbation bandwidth is updated.

In the traditional harmony search mechanism, the pitch adjustment probability PAR and the disturbance bandwidth BW are both fixed values. The two parameters determine the global exploration and local development balance in the harmony search process, and the fixed values do not consider the iteration of the harmony search. evolutionary process. A smaller PAR at the beginning of the iteration can make the harmony search have a stronger overall exploration ability, avoiding the premature and too fast convergence of the algorithm; while a larger PAR in the later stage of the iteration can make the harmony search have a stronger local development ability, and improve the local exploration ability. The search capability in the space speeds up the algorithm convergence. At the same time, the same considerations apply to BW, and corresponding changes should be made as the iteration progresses.

In this embodiment, the formula corresponding to the pitch adjustment probability PAR is:

Among them, PAR(t) represents the pitch adjustment probability at iteration t, PAR _min represents the minimum value of pitch modulation probability, PAR _max represents the maximum value of pitch modulation probability, T _max represents the maximum number of iterations of harmony search, that is, the maximum value of harmony performance frequency.

In this embodiment, the formula corresponding to the disturbance bandwidth BW is:

Among them, BW(t) represents the disturbance bandwidth at iteration t, BW _min represents the minimum value of the disturbance bandwidth, BW _max represents the maximum value of the disturbance bandwidth, and T _max represents the maximum number of iterations of harmony search, that is, the maximum number of harmony performances.

Step S30, calculating the fitness of various harmony in the harmony memory and the new harmony, and updating the harmony in the harmony memory according to the calculation result.

It should be noted that the fitness calculation is performed on various harmony in the harmony memory and the new harmony; the candidate harmony with the smallest current fitness value in the harmony memory is obtained, and judged Whether the fitness value of the new harmony is greater than the fitness value of the candidate harmony; when the fitness value of the new harmony is greater than the fitness value of the candidate harmony, the candidate The harmony is replaced by the new harmony, so as to update the harmony in the harmony memory. That is, if the new harmony fitness is greater than the worst fitness harmony in the current harmony memory HM, replace the worst fitness harmony with the newly generated harmony; otherwise, maintain the original harmony memory HM constant.

According to the placement target of the virtual machine, the smaller the value of the objective function, the greater the fitness of the individual. Therefore, the fitness function of the virtual machine placement scheme represented by the evaluation harmony can be set as:

Wherein, P represents the objective function in the energy consumption minimization formula, that is, to minimize the power consumption of the physical host.

If the obtained placement scheme cannot meet the resource constraints of the physical host, its fitness can be set to 0. Therefore, when evaluating the quality of the placement scheme represented by the harmony, the optimized fitness function is:

Step S40, determine the target harmony with the highest fitness value according to the update result, and use the pitch information of the target harmony as the optimal solution for virtual machine placement.

It is easy to understand that the goal of virtual machine placement is to reduce the energy consumption of the host, therefore, the larger the fitness value, the better the placement solution represented by harmony.

Step S50, place the virtual machines in the virtual machine set on physical hosts corresponding to the physical host set according to the optimal virtual machine placement solution.

It is easy to understand that after obtaining the optimal solution for virtual machine placement, the virtual machine can be placed according to the optimal solution, so as to realize the reasonable application of physical host resources and energy consumption.

In the embodiment of the present invention, through the above method, under the condition that the resource utilization rate and energy consumption of the physical host are constrained, by generating a new harmony, that is, a new placement scheme, the low energy consumption optimization of virtual machine placement is formed, and the virtual machine placement is improved. efficiency and effectiveness.

Referring to FIG. 3 , FIG. 3 is a schematic flowchart of a third embodiment of a harmony search-based virtual machine placement method according to the present invention. Based on the first embodiment above, the method for placing a virtual machine based on harmony search in this embodiment, after step S40, further includes:

Step S401, detecting the current iteration number of the current harmony memory bank, and judging whether the current iteration number is less than a preset iteration number.

Step S402, when the current iteration number is less than the preset iteration number, return to the step of generating a new harmony according to preset harmony generation conditions.

It is easy to understand that the preset number of iterations is the maximum number of iterations of the harmony memory HM, which is set according to the requirement of virtual machine placement when generating the harmony memory HM. When the number of iterations is insufficient, a new harmony, that is, a new virtual machine placement plan, is repeatedly generated and the fitness is calculated. According to the calculation results, corresponding judgments are made, and the harmony memory HM is updated until the maximum number of iterations Tmax is reached. Finally, the harmony with the greatest fitness in the output harmony memory is used as the final virtual machine placement optimal solution.

Step S403, when the current number of iterations is equal to the preset number of iterations, output the optimal solution for virtual machine placement.

The embodiment of the present invention uses the above method to iteratively generate new harmony, so that the harmony library is continuously updated, and new placement schemes are continuously formed to obtain an optimized placement scheme, which improves the accuracy and effect of virtual machine placement.

Referring to FIG. 4 , FIG. 4 is a structural block diagram of the first embodiment of the harmony search-based virtual machine placement device of the present invention. It should be noted that this embodiment is based on the cloud computing environment in the foregoing method embodiments, which will not be repeated here. The device includes: a harmony library building module 10, a fitness calculation module 20, an optimal solution acquisition module 30 and a placement module 40, wherein;

The harmony library building module 10 is configured to acquire a set of virtual machines and a set of physical hosts to be placed, and build a harmony memory bank according to the set of virtual machines and the set of physical hosts.

The harmony library building module 10 is specifically used to: obtain the number of physical hosts corresponding to the set of physical hosts and the number of virtual machines corresponding to the set of virtual machines; use the number of virtual machines as the tone corresponding to various harmony The number of information, according to the number of physical hosts, randomly sets the tone information corresponding to various harmony; according to the number of preset harmony types, the number of tone information and the tone information, a harmony memory bank is established.

Let a harmony h be expressed as:

X _h ＝[x _h,1 ,x _h,2 ,...,x _h,n ]

Among them, the element x _{h, k} in the vector represents the tone played by the kth instrument in the harmony h, and the tone corresponds to the serial number of the physical host where the virtual machine k is placed, and the value of the physical host serial number is within the interval [1, m] Integer value, h=1, 2, ..., HMS, HMS indicates the size of the harmony memory, HMS is the number of preset harmony types, which can be set according to the actual needs of the problem, k = 1, 2, ..., n, n represents the number of musical instruments, corresponding to the total number of virtual machines to be placed, that is, the corresponding number of tone information. In other words, a harmony represents a virtual machine placement scheme, which can be defined in an n-dimensional search space. A harmony in the harmony search mechanism under the virtual machine placement problem can only appear in the form of a discrete numerical sequence number between 1 and m, where m represents the maximum number of physical hosts.

In this embodiment, if the harmony h is X _h = [2, 1, 5, 4, 2, 3, 2, 1], it indicates that a total of 8 musical instruments play 8 tones, which represent the virtual machine placement scheme The meaning is: virtual machines v ₁ , v ₅ and v ₇ are placed on physical host h ₂ , virtual machines v ₂ and v ₈ are placed on physical host h ₁ , virtual machine v ₃ is placed on physical host h ₅ , virtual machine _v4 is placed on the physical host _h4 , and the virtual machine _v6 is placed on the physical host _h3 .

All possible harmony can form a matrix, defined as the harmony memory HM:

The fitness calculation module 20 is configured to generate a new harmony according to preset harmony generation conditions. Specifically, according to the number of physical hosts, randomly setting the number of tone information equal to the number of virtual machines to obtain the harmony to be processed; performing harmony memory bank selection processing and tone fine-tuning disturbance processing on the harmony to be processed, to obtain Get the new processed harmonies.

It should be noted that the process of selecting the harmony memory bank specifically includes: generating a first random number pair corresponding to each tone information in the harmony to be processed, and according to the first random number pair and the preset sum The sound memory selection probability randomly selects pitch information from the harmony memory, and replaces the pitch information corresponding to the harmony to be processed with the pitch information.

For each tone x _{h , k in harmony X h,} k=1, 2, ..., n, randomly generate a pair of random numbers, that is, the first pair of random numbers, the first pair of random numbers includes random The number r ₁ and the random number r ₂ , the two random numbers in the random number pair are both between (0, 1).

If r ₁ is less than the harmony memory bank selection probability HMCR, then randomly select a harmony HM[a][b] from the harmony memory bank HM to replace x _{h, k} , a=1, 2, ..., HMS, b=1, 2,..., n, that is, the tone x _{h, k} is updated as:

x _h,k = HM[a][b]

Otherwise, if r ₁ >HMCR, then the update value of x _{h, k} randomly generates an integer number in the interval [1, m], namely:

Among them, r ₂ represents a random number in the interval (0, 1).

It should be noted that the process of tone fine-tuning disturbance processing specifically includes: generating a second random number pair corresponding to each tone information in the chorus to be processed, and according to the second random number pair, tone adjustment probability and disturbance bandwidth pair The replaced tone information is subjected to tone fine-tuning perturbation processing to obtain the processed new harmony.

It is easy to understand that, for each tone x _{h , k} in harmony X h, k=1, 2, ..., n, a pair of random numbers is randomly generated, that is, the second pair of random numbers, the first pair of random numbers The random number pair includes a random number r ₃ and a random number r ₄ , and both of the two random numbers in the random number pair are between (0, 1).

While satisfying r ₁ <HMCR, if r ₃ is smaller than the pitch adjustment probability PAR, further fine-tuning disturbance is performed on the update value HM[a][b] of the previous step. The fine-tuning perturbation formula is:

Among them, r ₄ represents a random number in the interval (0, 1), and BW represents the disturbance bandwidth.

Since the placement scheme is only an integer value limited to the interval [1, m], that is, the value of x _{h, k} must be within the interval [1, m], and according to the update method of the fine-tuning disturbance formula, it may appear that the value is not in conditions within this range. Therefore, the optimized pitch fine-tuning perturbation formula is:

表示向下取整，m表示物理主机总量，即最大物理主机序号。Among them, mod means modulo operation,

Indicates rounding down, and m indicates the total number of physical hosts, that is, the maximum physical host serial number.

The first random number pair corresponding to each tone information in the harmony to be processed is generated, and randomly selected from the harmony memory bank according to the first random number pair and the preset harmony memory bank selection probability Before the step of selecting tone information and replacing the tone information corresponding to the harmony to be processed with the tone information, it also includes: obtaining the current iteration number of the harmony memory bank; adjusting the probability and pitch according to the current iteration number The perturbation bandwidth is updated.

In the traditional harmony search mechanism, the pitch adjustment probability PAR and the disturbance bandwidth BW are both fixed values. The two parameters determine the global exploration and local development balance in the harmony search process, and the fixed values do not consider the iteration of the harmony search. evolutionary process. A smaller PAR at the beginning of the iteration can make the harmony search have a stronger overall exploration ability, avoiding the premature and too fast convergence of the algorithm; while a larger PAR in the later stage of the iteration can make the harmony search have a stronger local development ability, and improve the local exploration ability. The search capability in the space speeds up the algorithm convergence. At the same time, the same considerations apply to BW, and corresponding changes should be made as the iteration progresses.

In this embodiment, the formula corresponding to the pitch adjustment probability PAR is:

Among them, PAR(t) represents the pitch adjustment probability at iteration t, PAR _min represents the minimum value of pitch modulation probability, PAR _max represents the maximum value of pitch modulation probability, T _max represents the maximum number of iterations of harmony search, that is, the maximum value of harmony performance frequency.

In this embodiment, the formula corresponding to the disturbance bandwidth BW is:

Among them, BW(t) represents the disturbance bandwidth at iteration t, BW _min represents the minimum value of the disturbance bandwidth, BW _max represents the maximum value of the disturbance bandwidth, and T _max represents the maximum number of iterations of harmony search, that is, the maximum number of harmony performances.

The fitness calculation module 20 is also used to calculate the fitness of various harmony in the harmony memory and the new harmony, and calculate the harmony in the harmony memory according to the calculation results. to update.

It should be noted that the fitness calculation is performed on various harmony in the harmony memory and the new harmony; the candidate harmony with the smallest current fitness value in the harmony memory is obtained, and judged Whether the fitness value of the new harmony is greater than the fitness value of the candidate harmony; when the fitness value of the new harmony is greater than the fitness value of the candidate harmony, the candidate The harmony is replaced by the new harmony, so as to update the harmony in the harmony memory. That is, if the new harmony fitness is greater than the worst fitness harmony in the current harmony memory HM, replace the worst fitness harmony with the newly generated harmony; otherwise, maintain the original harmony memory HM constant.

According to the placement target of the virtual machine, the smaller the value of the objective function, the greater the fitness of the individual. Therefore, the fitness function of the virtual machine placement scheme represented by the evaluation harmony can be set as:

Wherein, P represents the objective function in the energy consumption minimization formula, that is, to minimize the power consumption of the physical host.

If the obtained placement scheme cannot meet the resource constraints of the physical host, its fitness can be set to 0. Therefore, when evaluating the quality of the placement scheme represented by the harmony, the optimized fitness function is:

The optimal solution acquisition module 30 is configured to determine the target harmony with the largest fitness value according to the update result, and use the pitch information of the target harmony as the optimal solution for virtual machine placement.

It is easy to understand that the goal of virtual machine placement is to reduce the energy consumption of the host, therefore, the larger the fitness value, the better the placement solution represented by harmony.

The placing module 40 is configured to place the virtual machines in the virtual machine set on physical hosts corresponding to the physical host set according to the optimal virtual machine placement solution.

It is easy to understand that after obtaining the optimal solution for virtual machine placement, the virtual machine can be placed according to the optimal solution, so as to realize the reasonable application of physical host resources and energy consumption.

In the embodiment of the present invention, by using the above-mentioned device, under the condition that the resource utilization rate and energy consumption of the physical host are constrained, by generating a new harmony, that is, a new placement scheme, low energy consumption optimization of virtual machine placement is formed, and virtual machine placement is improved. efficiency and effectiveness.

In addition, the embodiment of the present invention also proposes a virtual machine placement device based on harmony search, the device is an electronic device, and the device includes: a memory, a processor, and a A harmony search-based virtual machine placement program running on the processor, the harmony search-based virtual machine placement program configured to implement the steps of the harmony search-based virtual machine placement method described above.

Since this device adopts all the technical solutions of all the above-mentioned embodiments, it at least has all the beneficial effects brought by the technical solutions of the above-mentioned embodiments, which will not be repeated here.

In addition, the embodiment of the present invention also proposes a storage medium, on which a virtual machine placement program based on harmony search is stored, and the virtual machine placement program based on harmony search is executed by a processor as described above Steps of a harmony search based virtual machine placement method.

Since the storage medium adopts all the technical solutions of all the above-mentioned embodiments, it at least has all the beneficial effects brought by the technical solutions of the above-mentioned embodiments, which will not be repeated here.

It should be understood that the above is only an example, and does not constitute any limitation to the technical solution of the present invention. In specific applications, those skilled in the art can make settings according to needs, and the present invention is not limited thereto.

It should be noted that the workflow described above is only illustrative and does not limit the protection scope of the present invention. In practical applications, those skilled in the art can select part or all of them to implement according to actual needs. The purpose of the scheme of this embodiment is not limited here.

In addition, for technical details not described in detail in this embodiment, reference may be made to the harmony search-based virtual machine placement method provided in any embodiment of the present invention, and details are not repeated here.

In addition, it should be noted that in this embodiment, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion, so that a process, method, article or system comprising a series of elements not only includes those elements, but also includes other elements not expressly listed, or also includes elements inherent in such process, method, article, or system. Without further limitations, an element defined by the phrase "comprising a..." does not preclude the presence of additional identical elements in the process, method, article or system comprising that element.

The serial numbers of the above embodiments of the present invention are for description only, and do not represent the advantages and disadvantages of the embodiments.

Through the description of the above embodiments, those skilled in the art can clearly understand that the methods of the above embodiments can be implemented by means of software plus a necessary general-purpose hardware platform, and of course also by hardware, but in many cases the former is better implementation. Based on such an understanding, the essence of the technical solution of the present invention or the part that contributes to the prior art can be embodied in the form of a software product, and the computer software product is stored in a storage medium (such as a read-only memory (Read Only Memory) , ROM)/RAM, magnetic disk, optical disk), including several instructions to make a terminal device (which can be a mobile phone, computer, server, or network device, etc.) execute the methods described in various embodiments of the present invention.

The above are only preferred embodiments of the present invention, and are not intended to limit the patent scope of the present invention. Any equivalent structure or equivalent process conversion made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in other related technical fields , are all included in the scope of patent protection of the present invention in the same way.

Claims (5)

1. A harmony search-based virtual machine placement method, the method comprising:

acquiring a virtual machine set and a physical host set to be placed, and establishing a sound memory library according to the virtual machine set and the physical host set;

generating a new harmony according to the preset harmony generation condition;

performing fitness calculation on various harmony sounds in the harmony memory library and the new harmony sounds, and updating harmony sounds in the harmony memory library according to a calculation result;

determining a target harmony with the maximum fitness value according to the updating result, and taking the tone information of the target harmony as a virtual machine placement optimal solution;

placing the virtual machines in the virtual machine set into the physical hosts corresponding to the physical host set according to the optimal placement solution of the virtual machines;

the step of obtaining a virtual machine set and a physical host set to be placed, and establishing a sound memory bank according to the virtual machine set and the physical host set specifically comprises the following steps:

acquiring the number of physical hosts corresponding to the physical host set and the number of virtual machines corresponding to the virtual machine set;

taking the virtual machine number as the tone information number corresponding to various sounds, and randomly setting the tone information corresponding to various sounds according to the physical host number;

Establishing a harmony memory library according to the preset sum sound seed number, the tone information number and the tone information;

the step of generating a new harmony according to the preset harmony generation condition specifically comprises the following steps:

randomly setting tone information with the number of the virtual machines according to the physical host machine number so as to obtain harmony to be processed;

generating a first random number pair corresponding to each tone information in the harmony to be processed, randomly selecting tone information from a harmony memory bank according to the first random number pair and a preset harmony memory bank selection probability, and replacing the tone information corresponding to the harmony to be processed with the tone information;

generating a second random number pair corresponding to each tone information in the harmony to be processed, and carrying out tone fine tuning disturbance processing on the replaced tone information according to the second random number pair, the tone adjustment probability and the disturbance bandwidth so as to acquire a processed new harmony;

the step of adaptively calculating various harmony sounds in the harmony memory bank and the new harmony sounds and updating the harmony sounds in the harmony memory bank according to the calculation result specifically comprises the following steps:

performing fitness calculation on various harmony sounds and the new harmony sounds in the harmony sound memory library;

Acquiring a to-be-selected harmony with the minimum current fitness value in the harmony memory library, and judging whether the fitness value of the new harmony is larger than the fitness value of the to-be-selected harmony;

when the fitness value of the new harmony is larger than that of the harmony to be selected, replacing the harmony to be selected with the new harmony so as to update the harmony in the harmony memory bank;

after the step of determining the target harmony with the maximum fitness value according to the updating result and taking the tone information of the target harmony as the optimal solution for placing the virtual machine, the method further comprises the following steps:

detecting the current iteration number of a current harmony memory bank, and judging whether the current iteration number is smaller than a preset iteration number or not;

returning to the step of generating a new harmony according to a preset harmony generating condition when the current iteration number is smaller than the preset iteration number;

and outputting the optimal solution placed by the virtual machine when the current iteration number is equal to the preset iteration number.

2. The harmony search-based virtual machine placement method of claim 1, wherein the step of generating a first random number pair corresponding to each tone information in the harmony to be processed, randomly selecting tone information from the harmony memory according to the first random number pair and a preset harmony memory selection probability, and replacing the tone information corresponding to the harmony to be processed with the tone information, further comprises:

Acquiring the current iteration times of the harmony memory bank;

and updating the tone adjustment probability and the disturbance bandwidth according to the current iteration times.

3. A harmony search-based virtual machine placement apparatus, the apparatus comprising: the system comprises a sound library establishing module, an adaptability calculating module, an optimal solution obtaining module and a placing module, wherein the sound library establishing module is used for establishing a sound library;

the harmony library establishing module is used for acquiring a virtual machine set and a physical host set to be placed, and establishing a harmony memory library according to the virtual machine set and the physical host set;

the fitness computing module is used for generating a new harmony according to preset harmony generation conditions; the method is also used for carrying out adaptability calculation on various harmony sounds in the harmony memory library and the new harmony sounds, and updating harmony sounds in the harmony memory library according to a calculation result;

the optimal solution acquisition module is used for determining a target harmony with the maximum fitness value according to the updating result, and taking the tone information of the harmony as a virtual machine to place an optimal solution;

the placement module is used for placing the virtual machines in the virtual machine set into the physical hosts corresponding to the physical host set according to the optimal placement solution of the virtual machines;

The harmony library establishment module is further used for acquiring the physical host number corresponding to the physical host set and the virtual machine number corresponding to the virtual machine set; taking the virtual machine number as the tone information number corresponding to various sounds, and randomly setting the tone information corresponding to various sounds according to the physical host number; establishing a harmony memory library according to the preset sum sound seed number, the tone information number and the tone information;

the fitness computing module is further used for randomly setting tone information with the number of the virtual machines according to the physical host numbers so as to obtain harmony to be processed; generating a first random number pair corresponding to each tone information in the harmony to be processed, randomly selecting tone information from a harmony memory bank according to the first random number pair and a preset harmony memory bank selection probability, and replacing the tone information corresponding to the harmony to be processed with the tone information; generating a second random number pair corresponding to each tone information in the harmony to be processed, and carrying out tone fine tuning disturbance processing on the replaced tone information according to the second random number pair, the tone adjustment probability and the disturbance bandwidth so as to acquire a processed new harmony; performing fitness calculation on various harmony sounds and the new harmony sounds in the harmony sound memory library; acquiring a to-be-selected harmony with the minimum current fitness value in the harmony memory library, and judging whether the fitness value of the new harmony is larger than the fitness value of the to-be-selected harmony; when the fitness value of the new harmony is larger than that of the harmony to be selected, replacing the harmony to be selected with the new harmony so as to update the harmony in the harmony memory bank;

The optimal solution acquisition module is further used for detecting the current iteration times of the current harmony memory bank and judging whether the current iteration times are smaller than preset iteration times or not; returning to the step of generating a new harmony according to a preset harmony generating condition when the current iteration number is smaller than the preset iteration number; and outputting the optimal solution placed by the virtual machine when the current iteration number is equal to the preset iteration number.

4. A harmony search-based virtual machine placement apparatus, the apparatus comprising: memory, a processor, and a harmony search based virtual machine placement program stored on the memory and executable on the processor, the harmony search based virtual machine placement program configured to implement the steps of the harmony search based virtual machine placement method as defined in any one of claims 1 to 2.

5. A storage medium, wherein a harmony search based virtual machine placement program is stored on the storage medium, which when executed by a processor implements the steps of the harmony search based virtual machine placement method as defined in any one of claims 1 to 2.

Images