CN112202847B - A server resource allocation method based on mobile edge computing - Google Patents

Abstract

The invention claims to protect a server resource configuration method based on mobile edge computing, which belongs to the technical field of communication networks. Aiming at the access delay and load constraints of servers in mobile edge computing scenarios, an optimal configuration method for edge servers is proposed. According to the location and distribution density of mobile base stations in the area, the present invention satisfies the access delay and load constraints of servers through initial clustering, and performs multi-level clustering iteration through the methods of base station sorting, server location offset, and server number compression. , optimize the configuration of server resources in the area, thereby effectively reducing the number of servers configured and the average access delay, and improving the load balance of servers.

Description

Server resource allocation method based on mobile edge calculation

Technical Field

The invention belongs to the technical field of communication networks, and particularly relates to a server resource allocation method based on mobile edge computing.

Background

Due to the rapid development of the 5G technology, the rapid growth of mobile services is driven. However, due to constraints in computing power, storage resources, and battery capacity, the traffic handling capabilities of mobile terminal devices are limited to some extent. With the advent of computing offloading technology, the mobile terminal can offload services with large computation amount and low time delay requirement to the cloud server for processing, and return results in time, so as to alleviate the pressure of insufficient local processing capability of the mobile terminal. However, there still exist some problems to be solved by this offloading technology, especially when the distance from the mobile device to the cloud server is long, the offloading process has long transmission delay, which will seriously affect the Quality of Service (Quality of Service) of the delay-sensitive task. In recent years, the advent of Mobile Edge Computing (MEC) has provided the possibility of solving this problem. The MEC reduces the transmission distance of task unloading by distributing and configuring the servers to the wireless base stations closer to the users, and can effectively reduce the access time delay of the servers of the users, thereby providing various intelligent services with higher efficiency.

The resource allocation problem of the edge server is an important target for the research of the mobile edge computing technology. The reasonable edge server configuration method can effectively improve the utilization rate of server resources and the real-time performance of service completion. The configuration planning of the edge server has two strong constraint conditions, one is the access delay constraint of the server, and the other is the load constraint of the server. The simplest method for satisfying these two constraints is to increase the configuration density and number of edge servers, but may seriously affect the resource utilization and load balance of the servers, thereby causing huge loss to operators. Therefore, in order to improve the service quality of the mobile edge computing and the resource utilization rate and load balance of the server, the optimal configuration of the edge server resources is an important problem for the construction and perfection of the 5G network.

At present, most of the existing edge server configuration schemes are optimized only aiming at access delay, the calculation capacity constraint of the servers, the number of the servers and the load balance are ignored, and the resource utilization rate is difficult to further promote; a small number of configuration schemes are mainly optimized for load balance of a server, although a maximum delay threshold is introduced, the balance of delay is not considered, so that the difference of access delay of users in different areas is large, and the stability of user experience is difficult to ensure. In order to solve the above problems, the present invention provides a server resource allocation method based on mobile edge computing.

Disclosure of Invention

The present invention is directed to solving the above problems of the prior art. A server resource allocation method based on mobile edge computing is provided. The technical scheme of the invention is as follows:

a server resource allocation method based on mobile edge calculation is characterized in that initial clustering division is carried out on base stations according to the positions and distribution densities of mobile base stations in an area under the condition that the access time delay and load constraint conditions of a server are met, multilevel clustering iteration is carried out through a method of base station sequencing, server position offset and server quantity compression, server resource allocation is optimized, and the resource allocation method specifically comprises the following steps:

101. putting all base stations in the area into a set A, and initially configuring the base stations in the set A to obtain an initial central point set U ═ a_iH and corresponding cluster set of base stations C_iCalculating a target value R according to the target function, wherein an initialization variable j is 0, and k is 0;

102. according to the initial configuration, let R '═ R, R ═ R, where R' denotes the center point offset update index and R ″ denotes the random sequence update index;

103. making the current central point quantity I ═ U |;

104. if R ″)<R ', make R ' ═ R ', j ═ 0, update the centre point set U ═ { a ═_iH and corresponding cluster set of base stations C_iSkipping to the step 105, otherwise, skipping to the step 105;

105. j equals j +1, if j<J, wherein J updates the iteration termination tolerance for the center point, a for each center point a in U_iRandomly selecting one of the lambda base stations adjacent to the base station as a new central point to replace a_iStep 106, let k equal to 0; otherwise, jumping to step 110;

106. k is K +1, if K is less than or equal to K, wherein K is the iteration termination tolerance updated by the base station random sequence, all base stations are randomly arranged to generate a random sequence s, and the step 107 is skipped; otherwise, jumping to step 104;

107. sequentially dividing the base stations in the sequence s into a central point cluster set closest to the base stations according to the access time delay and the server load constraint condition;

108. if all base stations in the sequence s are divided, the division is regarded as effective division, a target value R is calculated according to a target function, and the step 109 is skipped; otherwise, jumping to step 106;

109. if R is less than R ', let R' ═ R, k ═ 0, update the center point set U ═ { a ═_iH and corresponding cluster set of base stations C_iSkipping to step 106; otherwise, jumping to step 106;

110. if I meets the constraint condition of the minimum number of servers, deleting one clustering center in U at random, enabling j to be 0, and jumping to step 103; otherwise, the output center point set U ═ a ═ is output_iH and corresponding cluster set of base stations C_iAnd fourthly, finishing the algorithm.

Further, the step 101 of performing initial configuration on the base station in the step a includes:

1) calculating the neighborhood density of each base station in the set A according to the coordinate position of the base station, and initializing a variable i to be 1;

2) the base station with the highest density in A is taken as the central point and is marked as a_iPutting the central point set U into the image;

3) according to the formula_iThe base stations which meet the access delay and server load constraint conditions in the A are sequentially moved into a cluster C from small to large_i；

4) If it is not

i +1, jumping to the step 2; otherwise, the central point set U ═ a_iH and corresponding cluster set of base stations C_iAs the initial solution.

Further, the access delay and the server load constraint condition in step 107 are shown in formulas (1) and (2):

T_i,n≤T_max (1)

l_i≤L_max (2)

in the formula (1), T_i,nRepresents the ith central point a_iAnd the nth base station point b_nTime delay between which is determined by the distance between two points, T_maxRepresents the maximum allowed access delay;

in the formula (2), l_iIndicates the load capacity of the ith server, L_maxRepresenting the maximum load upper bound for each server.

Further, the objective function of the steps 101 and 108 is shown in formula (3):

R＝ε·α+(1-ε)(β+γ) (3)

in the formula (3), epsilon represents a balance factor, epsilon is more than or equal to 0 and less than or equal to 1, alpha, beta and gamma represent a server number factor, an access delay factor and a server load factor, which are respectively shown in formulas (4), (5) and (6);

wherein, I represents the number of central points, which is equivalent to the number of configured servers, N represents the upper limit of the number of configured servers, which is equal to the total number of base stations, t_iDenotes the access delay of the ith server,. tau denotes the average access delay of the server,. l_iThe load amount of the ith server is represented, and η represents the average load amount of the server.

Further, the minimum server number constraint of step 110 is shown in equation (7):

in the formula (7), I_minRepresents the minimum number of configuration servers, and the value is the total load L of the base stations in the area_totalMost with each serverUpper limit of large load L_maxDivide and round up.

The invention has the following advantages and beneficial effects:

the method aims at the problems of access delay, the number of servers and load balance in the resource configuration of the edge server. According to the position and distribution density of the mobile base stations in the area, initial clustering division of the base station set is completed on the premise that access delay and load constraint of a server are met, and compared with a scheme of randomly generating an initial solution in conventional optimization, the method can effectively reduce the calculation amount of subsequent optimization iteration. Through random sequencing and iteration of base stations in the region and random offset and iteration of the server position, the clustering division scheme is effectively prevented from falling into local optimum; the configuration quantity of server resources is effectively reduced by iterative compression of the quantity of the servers; by strictly executing access delay and resource capacity constraint in multi-level iteration, the optimization solution can obtain good server load balance besides ensuring user service quality and improving resource utilization rate of the server.

Drawings

Fig. 1 is a flow chart of a configuration method of an edge server according to a preferred embodiment of the present invention.

Detailed Description

The technical solutions in the embodiments of the present invention will be described in detail and clearly with reference to the accompanying drawings. The described embodiments are only some of the embodiments of the present invention.

The technical scheme for solving the technical problems is as follows:

the concepts and models involved in the present disclosure are as follows:

1. network model

Assume that the base station profile within the region is G (b)_n,l_n) Wherein b is_n＝{x_n,y_nIs the position coordinate of each base station, n is the label of each base station, l_nIs the traffic load of each base station.

2. Other symbols referred to in the context of the present invention are described below:

a: initial set of base stations

b_n: the nth base station

U: set of center points

R': center point offset update index

R': random sequence update indicator

I: number of center points

a_i: the ith central point

λ: updating the number of neighboring points of the center point

J: midpoint update iteration termination tolerance

K: base station random sequence update iteration termination tolerance

s: random sequence of base station in A

C_i: ith base station clustering

T_i,n: center point a_iAnd base station point b_nTime delay therebetween

l_i: load of ith server

T_max: maximum allowed access delay

L_max: maximum load upper bound per server

I_min: configuring minimum number of servers

L_total: total load of base stations in area

The technical scheme of the invention is explained as follows:

1. initial configuration method

Step 1, calculating the neighborhood density of each base station in the set A according to the coordinate position of the base station, and initializing a variable i to be 1;

step 2, taking the base station with the maximum density in the A as a central point and marking as a_iPutting the central point set U into the image;

step 3, according to the formula_iThe base stations which meet the access delay and server load constraint conditions in the A are sequentially moved into a cluster C from small to large_i；

Step 4, if

i +1, jumping to the step 2; otherwise, the central point set U ═ a_iH and corresponding cluster set of base stations C_iAs the initial solution.

2. Access delay and server load constraints:

as shown in formulas (1) and (2):

T_i,n≤T_max (1)

l_i≤L_max (2)

in the formula (1), T_i,nRepresents the ith central point a_iAnd the nth base station point b_nTime delay between which is determined by the distance between two points, T_maxRepresents the maximum allowed access delay;

in the formula (2), l_iIndicates the load capacity of the ith server, L_maxRepresenting the maximum load upper bound for each server.

3. An objective function:

as shown in equation (3):

R＝ε·α+(1-ε)(β+γ) (3)

in the formula (3), epsilon represents a balance factor, epsilon is more than or equal to 0 and less than or equal to 1, alpha, beta and gamma represent a server number factor, an access delay factor and a server load factor, which are respectively shown in formulas (4), (5) and (6);

where I represents the number of hubs, which is equivalent to the number of servers deployed, and N representsUpper limit of number of configuration servers, whose value is equal to total number of base stations, t_iDenotes the access delay of the ith server,. tau denotes the average access delay of the server,. l_iThe load amount of the ith server is represented, and η represents the average load amount of the server.

4. Minimum number of servers constraint:

as shown in equation (7):

in the formula (7), I_minRepresents the minimum number of configuration servers, and the value is the total load L of the base stations in the area_totalUpper limit of maximum load L with each server_maxDivide and round up.

A server resource allocation method based on mobile edge calculation is disclosed, the specific implementation method comprises the following steps:

step 1: putting all base stations into A, and initially configuring the base stations in A to obtain initial U ═ a_iAnd { C }_iR is calculated according to the objective function, and the initialization variable j is 0, and k is 0;

step 2: according to an initial configuration, let R ═ R, R ═ R;

and step 3: making the current central point quantity I ═ U |;

and 4, step 4: if R ″)<R ', let R' ═ R ", j ═ 0, update U ═ a_iAnd { C }_iSkipping to the step 5; otherwise, jumping to step 5;

and 5: j equals j +1, if j<J, for each a in U_iRandomly selecting a point in adjacent lambda base stations to replace a_iStep 6, making k equal to 0; otherwise, jumping to step 10;

step 6: if K is equal to or less than K, randomly arranging all base stations to generate s, and jumping to the step 7; otherwise, jumping to step 4;

and 7: sequentially dividing the base stations in the s into a nearest cluster set according to the access time delay and the server load constraint condition;

and 8: if all the base stations in s are divided, the division is regarded as effective division, R is calculated according to the objective function, and the step 9 is skipped; otherwise, jumping to step 6;

and step 9: if R is less than R ', let R' ═ R, k ═ 0, update U ═ a_iAnd { C }_iSkipping to the step 6; otherwise, jumping to step 6;

step 10: if I meets the constraint condition of the minimum number of servers, deleting one clustering center in U at random, enabling j to be 0, and skipping to the step 3; otherwise, the output U ═ a_iAnd { C }_iAnd fourthly, finishing the algorithm.

The above examples are to be construed as merely illustrative and not limitative of the remainder of the disclosure. After reading the description of the invention, the skilled person can make various changes or modifications to the invention, and these equivalent changes and modifications also fall into the scope of the invention defined by the claims.

Claims (4)

1. A server resource allocation method based on mobile edge computing is characterized by comprising the following steps:

101. putting all base stations in the area into a set A, and initially configuring the base stations in the set A to obtain an initial central point set U ═ a_iH and corresponding cluster set of base stations C_iCalculating a target value R according to the target function, wherein an initialization variable j is 0, and k is 0;

102. according to the initial configuration, let R '═ R, R ═ R, where R' denotes the center point offset update index and R "denotes the random sequence update index;

103. making the current central point quantity I ═ U |;

104. if R '< R', let R '═ R', j ═ 0, update the center point set U ═ { a ═_iH and corresponding cluster set of base stations C_iSkipping to the step 105, otherwise, skipping to the step 105;

105. j is J +1, if J < J, where J updates the iteration termination tolerance for the center point, for each center point a in U_iIn its vicinity of λRandomly selecting one of the base stations as a new central point to replace a_iStep 106, let k equal to 0; otherwise, jumping to step 110;

106. k is K +1, if K is less than or equal to K, wherein K is the iteration termination tolerance updated by the base station random sequence, all base stations are randomly arranged to generate a random sequence s, and the step 107 is skipped; otherwise, jumping to step 104;

107. sequentially dividing the base stations in the sequence s into a central point cluster set closest to the base stations according to the access time delay and the server load constraint condition;

108. if all base stations in the sequence s are divided, the division is regarded as effective division, a target value R is calculated according to a target function, and the step 109 is skipped; otherwise, jumping to step 106;

109. if R is less than R', let R ═ R, k ═ 0, update the central point set U ═ { a ═ A_iH and corresponding cluster set of base stations C_iSkipping to step 106; otherwise, jumping to step 106;

110. if I meets the constraint condition of the minimum number of servers, deleting one clustering center in U at random, enabling j to be 0, and jumping to step 103; otherwise, the output center point set U ═ a ═ is output_iH and corresponding cluster set of base stations C_iFourthly, the algorithm is ended;

the objective function of steps 101 and 108 is shown in equation (3):

R＝ε·α+(1-ε)(β+γ) (3)

in the formula (3), epsilon represents a balance factor, epsilon is more than or equal to 0 and less than or equal to 1, alpha, beta and gamma represent a server number factor, an access delay factor and a server load factor, which are respectively shown in formulas (4), (5) and (6);

wherein, I represents the number of central points, which is equivalent to the number of configured servers, N represents the upper limit of the number of configured servers, which is equal to the total number of base stations, t_iDenotes the access delay of the ith server,. tau denotes the average access delay of the server,. l_iThe load amount of the ith server is represented, and η represents the average load amount of the server.

2. The method according to claim 1, wherein the step 101 of initially configuring the base station in a comprises:

1) calculating the neighborhood density of each base station in the set A according to the coordinate position of the base station, and initializing a variable i to be 1;

2) the base station with the highest density in A is taken as the central point and is marked as a_iPutting the central point set U into the image;

3) according to the formula_iThe base stations which meet the access delay and server load constraint conditions in the A are sequentially moved into a cluster C from small to large_i；

4) If it is not

i +1, jumping to the step 2; otherwise, the central point set U ═ a_iH and corresponding cluster set of base stations C_iAs the initial solution.

3. The method for allocating server resources based on mobile edge computing according to claim 1, wherein the access delay and server load constraint conditions of step 107 are shown in formulas (1) and (2):

T_i,n≤T_max (1)

l_i≤L_max (2)

in the formula (1), T_i,nRepresents the ith central point a_iAnd the nth base station point b_nTime delay between which is determined by the distance between two points, T_maxRepresents the maximum allowed access delay;

in the formula (2), l_iIndicates the load capacity of the ith server, L_maxRepresenting the maximum load upper bound for each server.

4. The method for allocating server resources based on mobile edge computing as claimed in claim 1, wherein the minimum server number constraint of step 110 is shown in formula (7):

in the formula (7), I_minRepresents the minimum number of configuration servers, and the value is the total load L of the base stations in the area_totalUpper limit of maximum load L with each server_maxDivide and round up.

Images