[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN112948058B - Response time optimization method for fair deployment after centralized service decoupling - Google Patents

Response time optimization method for fair deployment after centralized service decoupling Download PDF

Info

Publication number
CN112948058B
CN112948058B CN202110271251.3A CN202110271251A CN112948058B CN 112948058 B CN112948058 B CN 112948058B CN 202110271251 A CN202110271251 A CN 202110271251A CN 112948058 B CN112948058 B CN 112948058B
Authority
CN
China
Prior art keywords
service
sub
represented
edge server
coupling
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.)
Active
Application number
CN202110271251.3A
Other languages
Chinese (zh)
Other versions
CN112948058A (en
Inventor
魏同权
段媛
张润泽
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
East China Normal University
Original Assignee
East China Normal University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by East China Normal University filed Critical East China Normal University
Priority to CN202110271251.3A priority Critical patent/CN112948058B/en
Publication of CN112948058A publication Critical patent/CN112948058A/en
Application granted granted Critical
Publication of CN112948058B publication Critical patent/CN112948058B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

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/44—Arrangements for executing specific programs
    • G06F9/455—Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
    • G06F9/45533—Hypervisors; Virtual machine monitors
    • G06F9/45558—Hypervisor-specific management and integration aspects
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/23—Clustering techniques
    • G06F18/232—Non-hierarchical techniques
    • G06F18/2321—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions
    • G06F18/23213—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions with fixed number of clusters, e.g. K-means clustering
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/60—Software deployment
    • 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/44—Arrangements for executing specific programs
    • G06F9/445—Program loading or initiating
    • G06F9/44594—Unloading
    • 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/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/485—Task life-cycle, e.g. stopping, restarting, resuming execution
    • 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/505—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 load
    • 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/5083—Techniques for rebalancing the load in a distributed system
    • 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/44—Arrangements for executing specific programs
    • G06F9/455—Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
    • G06F9/45533—Hypervisors; Virtual machine monitors
    • G06F9/45558—Hypervisor-specific management and integration aspects
    • G06F2009/45595—Network integration; Enabling network access in virtual machine instances

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Evolutionary Biology (AREA)
  • Evolutionary Computation (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Artificial Intelligence (AREA)
  • Probability & Statistics with Applications (AREA)
  • Computer And Data Communications (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention discloses a response time optimization method for fair deployment after centralized service decoupling, which is characterized in that a service decoupling method and an MOEA/D algorithm-based sub-service are adopted for deployment, and the decoupled sub-service and a low-coupling-degree service are deployed on an edge server and subjected to multi-objective optimization, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server. Compared with the prior art, the method has the advantages of ensuring the shortest overall response time under the condition of guaranteeing the load fairness of the edge server, effectively improving the expected response time of the whole system, greatly reducing the occupation of network bandwidth resources, reducing the service communication cost by about 40 percent, along with simple method, convenient use and high efficiency.

Description

Response time optimization method for fair deployment after centralized service decoupling
Technical Field
The invention relates to the technical field of clustering and multi-objective optimization, in particular to a response time optimization method for fair deployment after centralized service decoupling in edge computing.
Background
At present, the influence and complexity between the centralized services of the cloud are high, the development efficiency is low, and the development of software application is difficult to meet. With the advent of small-scale clouds and server clusters in the edge of the network, deployment of services onto edge servers is supported, which can reduce the response time of the system and save network bandwidth. Compared to a traditional Content Delivery Network (CDN) that solves latency and bandwidth problems by deploying a cache close to a request, deployment to an edge server enables sensitive or critical business data of an enterprise to be better protected, because a CDN grid is typically located at a data center of an Internet Service Provider (ISP) and belongs outside the enterprise.
In the service deployment strategy in the prior art, the position of the edge server and the deployment cost are considered, but the fairness of the working time between the edge servers is ignored, so that the overall response time of the load of the edge servers is longer, a large amount of network bandwidth resources are wasted or occupied, and the service communication cost is high.
Disclosure of Invention
The invention aims to design a response time optimization method for fair deployment after centralized service decoupling aiming at the defects of the prior art, which adopts a service decoupling method and an MOEA/D algorithm-based sub-service deployment, deploys the decoupled sub-service and a low-coupling-degree service on an edge server and performs multi-objective optimization, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server, the expected response time of the whole system is effectively improved, the occupation of network bandwidth resources is greatly reduced, the service communication cost is reduced by about 40%, and the method is simple, convenient to use and high in efficiency.
The purpose of the invention is realized by the following steps: a response time optimization method for fair deployment after decoupling of centralized services is characterized in that a service decoupling method and an MOEA/D algorithm-based sub-service deployment are adopted, the decoupled sub-service and a low-coupling-degree service are deployed on an edge server and subjected to multi-objective optimization, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server, the specific optimization comprises the construction of a coupling degree model, a transmission service communication overhead model and a communication delay model, the coupling degree calculation is carried out on all the services to obtain the coupling degree value of the service, the coupling degree of the service is used for judging whether the coupling degree of the service is higher than a given coupling degree threshold value or not, if the coupling degree of the service is lower than the coupling degree threshold value, the deployment of the sub-service is directly carried out, and if the coupling degree of the service is higher than the coupling degree threshold value, the service is decoupled. The method comprises the following steps of decoupling two stages of high coupling services, firstly decoupling in an off-line stage, extracting characteristics based on service fields according to the subscription condition of each edge server to the high coupling services, clustering the high coupling services by using a k-means based method, decoupling in an on-line stage, taking the clustering result of the off-line decoupling as the initial input of the on-line clustering, clustering services with fields added or deleted by using a streaming k-means based method in real time, proposing a sub-service deployment model for the sub-services comprising the services after low coupling services and high coupling services are decoupled, and deploying the sub-services by using a MOEA/D based method, wherein the response time optimization of fair deployment specifically comprises the following steps:
Step 1: and constructing a system architecture and coupling degree model of the edge cloud, a transmission service communication overhead model and a communication delay model.
Step 2: calculating the coupling degree of all the services, judging the coupling degree value of the obtained service and a given coupling degree threshold value, and if the coupling degree value is lower than the coupling degree threshold value, directly deploying the sub-services; if the coupling degree threshold value is higher, the service is decoupled.
And step 3: and (3) performing two-stage decoupling on the high coupling service in the step (2), firstly performing off-line stage decoupling, performing service field-based feature extraction according to the subscription condition of each edge server to the high coupling service, and clustering the high coupling service by using a k-means-based method. And then performing on-line stage decoupling, taking a clustering result of off-line decoupling as initial input of on-line clustering, and performing real-time clustering on services with added or deleted fields by using a streaming k-means based method.
And 4, step 4: and deploying sub-services based on an MOEA/D algorithm according to the constructed coupling degree model, the transmission service communication overhead model and the communication delay model, wherein the sub-services comprise the low-coupling service in the step 2 and the clustering output result of the two stages in the step 3.
And 5: and after deployment is finished, obtaining an optimal solution of multiple targets, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server.
The implementation process of the step 1 specifically comprises the following steps:
step A1: construction of degree of coupling model
Establishing cloud server to maintain N s A service, each service S i (1≤i≤N s ) By
Figure BDA0002974487570000021
Field composition for edge server N es Each edge server E j (1≤j≤N es ) Subscribing to several fields in one or more services according to its own needs.
Is provided with
Figure BDA0002974487570000022
Representing edge servers E j And service S i The subscription relationship of the middle field k, if E j Subscribed to service S i K in (1), then
Figure BDA0002974487570000023
Is 1, otherwise is 0, respectively introduces the influence of different operations of the fields expressed by the following formulas a to c on the service
Figure BDA0002974487570000024
And
Figure BDA0002974487570000025
Figure BDA0002974487570000026
Figure BDA0002974487570000027
Figure BDA0002974487570000028
thus, the edge server E j Subscription service S i The influence of the middle field k on the middle field is represented by the following formula d
Figure BDA0002974487570000029
Figure BDA00029744875700000210
Wherein: w is a j Are the influence coefficients of different operations.
Thus, edge server E j Subscription service S i The influence of (a) is represented by the following formula e
Figure BDA00029744875700000211
Figure BDA00029744875700000212
Wherein: p is a radical of k Is the modification frequency of field k.
To sum up, service S i Degree of coupling F i Can be calculated by the following formula f:
Figure BDA00029744875700000213
step A2: construction of transport service communication overhead model
Recording service S i Offload from cloud Server to edge Server E j Has an additional information size of A (A > 0), and serves S i Size B i Then transmitting service S i Overhead of communication
Figure BDA00029744875700000214
Can be calculated from the following formula g:
Figure BDA00029744875700000215
will S i Is divided into
Figure BDA0002974487570000031
Sub-services, i.e.
Figure BDA0002974487570000032
Partitioned sub-services
Figure BDA0002974487570000033
A size of
Figure BDA0002974487570000034
Transmits its sub-service
Figure BDA0002974487570000035
Overhead of communication
Figure BDA0002974487570000036
Can be calculated by the following equation h:
Figure BDA0002974487570000037
wherein:
Figure BDA0002974487570000038
satisfy the requirement of
Figure BDA0002974487570000039
Edge server E k Subscribed to sub-services
Figure BDA00029744875700000310
Fields of China, i.e. considered as subscribed to a sub-service
Figure BDA00029744875700000311
Its edge server E k Whether or not sub-services are subscribed to
Figure BDA00029744875700000312
Is represented by the following formula i
Figure BDA00029744875700000313
Figure BDA00029744875700000314
Then, the edge server E k Accepting sub-services offloaded from cloud servers
Figure BDA00029744875700000315
The required communication overhead can be calculated by the following equation j:
Figure BDA00029744875700000316
then, the edge server E k Accepting service S offloaded from cloud server i The required communication overhead can be calculated by the following k:
Figure BDA00029744875700000317
therefore, all edge servers receive the service S in the cloud server through a given service dividing method i The communication overhead of (c) is then calculated by the following equation m:
Figure BDA00029744875700000318
and satisfies the following constraints:
Figure BDA00029744875700000319
Figure BDA00029744875700000320
Figure BDA00029744875700000321
Figure BDA00029744875700000322
A＞0，
Figure BDA00029744875700000323
Figure BDA00029744875700000324
step A3: construction of communication delay model
Note the book
Figure BDA00029744875700000325
Two edge servers E represented by the following n formula i And E j Inter-transmission delay:
Figure BDA00029744875700000326
wherein: b (E) i ，E j ) Is the bandwidth; w (E) i ，E j ) Is represented by the following r formula in an edge server E i To the edge server E j Sub-service set S transmitted therebetween nb The size of (2):
Figure BDA00029744875700000327
note the book
Figure BDA00029744875700000328
Is the propagation delay expressed by the following equation:
Figure BDA0002974487570000041
wherein: d (E) i ，E j ) Is the distance between two edge servers; theta is the propagation speed of the electric signal in the optical cable; if there is no edge server between the two edge serversRouting, then
Figure BDA0002974487570000042
Will be set to infinity;
in summary, the wire communication delay between two edge servers is calculated by the following equation:
Figure BDA0002974487570000043
wherein:
Figure BDA0002974487570000044
for terminal i to edge server E j The delay of the wireless transmission distance between the two antennas is represented by the following u formula:
Figure BDA0002974487570000045
wherein: w (i, E) j ) Representing terminal i to edge server E j The size of the transmission task, and the maximum data transmission rate tr (i, E) j ) Calculated by the following v formula:
Figure BDA0002974487570000046
wherein: b (i, E) j ) For terminal i to edge server E j Bandwidth of the wireless communication link to transmit data;
Figure BDA0002974487570000047
is the signal-to-noise ratio; p i Is the transmission power of terminal i; g (i, E) j ) For terminal i and edge server E j A signal gain in between; n is a radical of p Is the in-channel noise power.
Thus, the terminal i goes to the edge server E j Is calculated by the following equation w:
Figure BDA0002974487570000048
wherein: e i Is located next to the base station closest to terminal i.
The step 2 specifically comprises: and calculating the coupling degrees of all services by using a coupling degree model formula. And judging whether the coupling degree of the service is higher than a given coupling degree threshold value or not, and if the coupling degree of the service is lower than the coupling degree threshold value M, the service is called as low-coupling service, and the service can be directly deployed. If the coupling degree is higher than the threshold value, the service is called as a high coupling service, decoupling is needed to be performed on the service, and then the service after decoupling, namely deployment of the sub-service, is performed.
The implementation process of the step 3 specifically comprises the following steps:
step B1: memory two-dimensional matrix
Figure BDA0002974487570000049
For service S i (1≤i≤N s ) The feature matrix, which stores the field information of all edge servers subscribing the service, is represented by the following formula 1:
Figure BDA00029744875700000410
note the book
Figure BDA00029744875700000411
Representing a service S for the following formula 2 i The feature vector of field k:
Figure BDA00029744875700000412
then, a two-dimensional matrix
Figure BDA00029744875700000413
Feature matrix represented by the following formula 3
Figure BDA00029744875700000414
Figure BDA00029744875700000415
Wherein,
Figure BDA00029744875700000416
for service S i The number of fields contained in;
according to the characteristic matrix
Figure BDA00029744875700000417
Performing k-means clustering on the obtained data, determining k value, and initializing clustering center by using k-means +
Figure BDA00029744875700000418
The minimum objective function is calculated by the following formula 4:
Figure BDA00029744875700000419
step B2: taking the clustering result of the step B1 as the input of the online clustering of the step, namely, the clustering center after the given t-th batch data arrives, and the batch data
Figure BDA0002974487570000051
Wherein: o is t When the t +1 th batch of data arrives, the updated clustering center is expressed by the following formulas 5-6:
Figure BDA0002974487570000052
Figure BDA0002974487570000053
wherein: α is an attenuation factor, when increasing the field, ± select +, when decreasing the field, ± select-;
Figure BDA0002974487570000054
is the kth clustering center when the t-th batch processing arrives;
Figure BDA0002974487570000055
a number indicating the kth cluster;
Figure BDA0002974487570000056
the cluster center of the new field data of the cluster is represented by the following formula 7:
Figure BDA0002974487570000057
Wherein:
Figure BDA0002974487570000058
is a certain field data in the t-th batch of data; i.e. i v To represent
Figure BDA0002974487570000059
Belong to item i v Clustering;
Figure BDA00029744875700000510
the number of new data assigned to the cluster is represented by equation 8 below:
Figure BDA00029744875700000511
in summary, the new cluster center point is represented by the following formula 9:
Figure BDA00029744875700000512
the implementation process of the step 4 specifically comprises the following steps:
step C1: definition of S sub For clustered partitioned sub-service and low coupling service sets, S i (1≤i≤N s ) Represented by the following formula 10
Figure BDA00029744875700000513
The sub-services:
Figure BDA00029744875700000514
the divided fields in each sub-service are not repeated, and the union of the two sub-services is null according to the following formula 11:
Figure BDA00029744875700000515
then S sub Can be represented by the following formula 12:
Figure BDA00029744875700000516
recording vis (i, s) j )(1≤i≤N t ，s j ∈S sub ) Whether or not terminal i represented by the following formula 13 subscribes to sub-service s j ：
Figure BDA00029744875700000517
Note the book
Figure BDA00029744875700000518
Indicates whether the condition i-C is satisfied, if so, the method
Figure BDA00029744875700000519
Otherwise
Figure BDA00029744875700000520
Wherein: c is
A constant value; i is a variable represented by the following formula 14:
Figure BDA00029744875700000521
input(s) j ) Representing sub-services s j Whether or not to deploy to edge server E i (1≤i≤N es ) Up, if deployed, put(s) j ) Can be represented by the following formula 15:
put(s j )＝i(15)；
wherein: put(s) j )∈[0，N-1]And is
Figure BDA00029744875700000522
In summary, the objective function for optimizing the response time is calculated by the following equation 16:
Figure BDA0002974487570000061
wherein: i S sub Is the sub-service set S sub The number of services; e is N es A set of edge servers; n is a radical of t Refers to the number of terminals.
Note t (E) j ，s k ) An edge server E represented by the following formula 17 j Handling sub-service jobs k Required time period of (c):
Figure BDA0002974487570000062
wherein:
Figure BDA0002974487570000063
serving a child s k The size of (d);
Figure BDA0002974487570000064
as an edge server E j Computing power of (1), note t max ，t min The method comprises the following steps of respectively representing the longest working time and the shortest working time of the edge server by the following formulas 18-19:
Figure BDA0002974487570000065
Figure BDA0002974487570000066
in summary, the objective function for optimizing the edge server work balance can be represented by the following equation 20:
I 2 ＝min(t max -t min ) (20)；
and the following constraint conditions are satisfied:
Figure BDA0002974487570000067
Figure BDA0002974487570000068
vis(i，s k )∈{0，1}；
Figure BDA0002974487570000069
g(i，E j )＞0；
N p ＞0；
s k ∈S sub ；
1≤i≤N t ，1≤j≤N es ，1≤k≤|S sub |。
step C2: converting the multi-objective optimization problem into a plurality of single-objective optimization problems represented by the following formula 21 by using a MOEA/D algorithm:
Figure BDA00029744875700000610
s.t.x∈Ω
wherein: λ ═ λ 1 ，λ 2 ，...，λ m ) As weight vector, for each lambda i (i＝1M) all have lambda i Is not less than 0 and
Figure BDA00029744875700000611
Figure BDA00029744875700000612
is a reference vector in which the value of each reference point is the minimum value of each dimension of the objective function, i.e.
Figure BDA00029744875700000613
Inputting a multi-objective optimization problem, a condition for stopping iteration and a population size N pop Weight vector and number of neighbors of weight vector T nb And finally outputting a set PS of pareto optimal points, wherein the specific algorithm is as follows: firstly, initializing PS to be a non-empty set, and setting an initial reference point
Figure BDA00029744875700000614
Calculating the distance between each weight vector and other vectors, and calculating the T nearest to the current individual nb Individual weight vectors by randomly initializing population individuals
Figure BDA00029744875700000615
Calculating a target value FV i ＝F(x i ) (ii) a For each population individual, randomly selecting two from neighbors, using a genetic operator to generate a solution y, performing Gaussian rounding on the generated new solution to obtain y', and then updating a reference point
Figure BDA00029744875700000616
If the updated reference point z j The value being less than that of the objective function, i.e. z j ＜f j (y'), updating the reference point to z j ＝f j (y'); updating the neighborhood, and for each neighbor j, if the constraint value corresponding to the new solution is less than or equal to the original individual of the neighborhood, namely g (y' | lambda) j ，z)≤g(x j |λ j Z), then the original individual is replaced with the new solution, i.e. x j The target value FV is updated simultaneously when y is equal to y j F (y'); most preferablyAnd updating the PS value, judging whether a stopping condition is met, stopping iteration and outputting the PS if the stopping condition is met.
Compared with the prior art, the method has the advantages of ensuring the shortest overall response time under the condition of guaranteeing the load fairness of the edge server, effectively improving the expected response time of the whole system, greatly reducing the occupation of network bandwidth resources, reducing the service communication cost by about 40 percent, along with simple method, convenient use and high efficiency.
Drawings
FIG. 1 is a bar graph of the degree of coupling of example 1;
FIG. 2 is a graph of communication overhead before/after service decoupling according to example 1;
FIG. 3 is a time histogram of the solution service add field operation of the online and offline algorithm of example 1;
FIG. 4 is a time histogram of the solution of the service reduction field operation of the online and offline algorithm of embodiment 1;
FIG. 5 is a graph of the average waiting time of the online and offline algorithms of different numbers of terminals in embodiment 1;
fig. 6 is a histogram of the optimal solution of service deployment obtained by three algorithms for the number of edge servers of 3 in embodiment 1;
FIG. 7 is a histogram of the optimal solution of service deployment obtained by three algorithms for the number of edge servers of 4 in example 1;
fig. 8 is a histogram of the optimal solution of service deployment obtained by three algorithms for the number of edge servers of 5 in embodiment 1.
Detailed Description
The method comprises the steps of constructing a system architecture and a coupling degree model, a transmission service communication overhead model and a communication delay model, calculating the coupling degree of all services, judging the coupling degree value of the obtained service and a given coupling degree threshold value, and directly deploying the sub-services if the coupling degree value of the service is lower than the coupling degree threshold value. Decoupling the service if the coupling value of the service is above the coupling threshold. The high coupling service is decoupled in two stages, firstly, the off-line stage decoupling is carried out, the feature extraction based on the service field is carried out according to the subscription condition of each edge server to the high coupling service, and the high coupling service is clustered by using a method based on k-means. And then performing on-line stage decoupling, taking a clustering result of off-line decoupling as initial input of on-line clustering, and performing real-time clustering on services with added or deleted fields by using a streaming k-means based method. For services after the sub-services comprise low coupling services and high coupling services after decoupling, a sub-service deployment model is provided, and the sub-services are deployed by using a MOEA/D (mobility agent architecture/data encryption) based method, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server, and the specific optimization comprises the following steps:
Step 1: system architecture and coupling degree model for constructing edge cloud, transmission service communication overhead model and communication delay model
A1: degree of coupling model
Establishing cloud server to maintain N s A service, each service S i (1≤i≤N s ) By
Figure BDA0002974487570000071
And (4) forming fields. For edge server N es In other words, each edge server E j (1≤j≤N es ) Subscribing to several fields in one or more services according to its own needs. Is provided with
Figure BDA0002974487570000072
Representing edge servers E j And service S i The subscription relationship of the middle field k, if E j Subscribed to service S i K in (1), then
Figure BDA0002974487570000073
Is 1, otherwise is 0. Introducing the influence of different operations on the service represented by the following a-c expressions
Figure BDA0002974487570000074
And
Figure BDA0002974487570000075
Figure BDA0002974487570000076
Figure BDA0002974487570000077
Figure BDA0002974487570000081
thus, the edge server E j Subscription service S i The influence of the middle field k on the middle field is represented by the following formula d
Figure BDA0002974487570000082
Figure BDA0002974487570000083
Wherein: w is a l Are the influence coefficients of different operations.
Thus, edge server E j Subscription service S i The influence of (a) is represented by the following formula e
Figure BDA0002974487570000084
Figure BDA0002974487570000085
Wherein: p is a radical of k Is the modification frequency of field k.
To sum up, service S i The calculation formula of the coupling degree is expressed by the following formula f:
Figure BDA0002974487570000086
a2: construction of transport service communication overhead model
Recording service S i Slave cloud clothesServer offload to edge Server E j Has an additional information size of A (A > 0), and serves S i Size B i Then transmitting service S i Overhead of communication
Figure BDA0002974487570000087
Represented by the following formula g:
Figure BDA0002974487570000088
will S i Is divided into
Figure BDA0002974487570000089
Sub-services, i.e.
Figure BDA00029744875700000810
Partitioned sub-services
Figure BDA00029744875700000811
A size of
Figure BDA00029744875700000812
Transmits its sub-service
Figure BDA00029744875700000813
Overhead of communication
Figure BDA00029744875700000814
Represented by the following formula h:
Figure BDA00029744875700000815
wherein:
Figure BDA00029744875700000816
satisfy the requirement of
Figure BDA00029744875700000817
Edge server Ek subscribes to sub-services
Figure BDA00029744875700000818
Fields of China, i.e. considered as subscribed to a sub-service
Figure BDA00029744875700000819
Its edge server E k Whether or not sub-services are subscribed to
Figure BDA00029744875700000820
Then it is represented by the following formula i
Figure BDA00029744875700000821
Figure BDA00029744875700000822
Then, the edge server E k Accepting sub-services offloaded from cloud servers
Figure BDA00029744875700000823
The required communication overhead is represented by the following j equation:
Figure BDA00029744875700000824
then, the edge server E k Accepting service S offloaded from cloud server i The required communication overhead is represented by the following k:
Figure BDA00029744875700000825
therefore, all edge servers receive the service S in the cloud server through a given service dividing method i The communication overhead is expressed by the following equation m:
Figure BDA00029744875700000826
and satisfies the following constraints:
Figure BDA0002974487570000091
Figure BDA0002974487570000092
Figure BDA0002974487570000093
Figure BDA0002974487570000094
A＞0，
Figure BDA0002974487570000095
Figure BDA0002974487570000096
a3: construction of communication delay model
Note the book
Figure BDA0002974487570000097
Two edge servers E represented by the following n formula i And E j Inter-transmission delay:
Figure BDA0002974487570000098
wherein: b (E) i ，E j ) Is the bandwidth; w (E) i ，E j ) Is represented by the following r formula in an edge server E i To the edge server E j Sub-service set S transmitted between nb The size of (2):
Figure BDA0002974487570000099
note the book
Figure BDA00029744875700000910
Is the propagation delay expressed by the following equation:
Figure BDA00029744875700000911
wherein: d (E) i ，E j ) Is the distance between two edge servers; theta is the propagation speed of the electric signal in the optical cable; if there is no route between the two edge servers, then
Figure BDA00029744875700000912
Will be set to infinity.
In summary, the wired communication delay between two edge servers is represented by the following equation:
Figure BDA00029744875700000913
wherein:
Figure BDA00029744875700000914
for terminal i to edge server E j The delay of the wireless transmission distance between the two is represented by the following u formula:
Figure BDA00029744875700000915
wherein: w (i, E) j ) Representing terminal i to edge server E j The size of the transmission task, and the maximum data transmission rate tr (i, E) j ) Represented by the following formula v:
Figure BDA00029744875700000916
wherein: b (i, E) j ) For terminal i to edge server E j Bandwidth of the wireless communication link to transmit data;
Figure BDA00029744875700000917
signal-to-noise ratio; p i Is the transmission power of terminal i; g (i, E) j ) For terminal i and edge server E j A signal gain in between; n is a radical of p Is the in-channel noise power.
Thus, the terminal i goes to the edge server E j Is represented by the following w formula:
Figure BDA00029744875700000918
wherein: e i Is located next to the base station closest to terminal i.
Step 2: and calculating the coupling degrees of all services by using a coupling degree model formula. And judging whether the coupling degree of the service is higher than a given coupling degree threshold value or not, and if the coupling degree of the service is lower than the coupling degree threshold value M, the service is called as low-coupling service, and the service can be directly deployed. If the coupling degree is higher than the threshold value, the service is called as a high coupling service, decoupling is needed to be performed on the service, and then the service after decoupling, namely deployment of the sub-service, is performed.
And step 3: the method comprises the following steps of performing off-line stage decoupling and on-line stage decoupling on the coupling service higher than a coupling threshold, wherein the implementation process specifically comprises the following steps:
b1: memory two-dimensional matrix
Figure BDA00029744875700001023
For service S i (1≤i≤N s ) The feature matrix, which stores the field information of all edge servers subscribing the service, is represented by the following formula 1:
Figure BDA0002974487570000101
note the book
Figure BDA0002974487570000102
Representing a service S for the following formula 2 i The feature vector of field k:
Figure BDA0002974487570000103
then, a two-dimensional matrix
Figure BDA0002974487570000104
Feature matrix represented by the following formula 3
Figure BDA0002974487570000105
Figure BDA0002974487570000106
Wherein,
Figure BDA0002974487570000107
for service S i The number of fields contained in (a).
According to the characteristic matrix
Figure BDA0002974487570000108
Performing k-means clustering on the obtained data, determining k value, and initializing clustering center by using k-means +
Figure BDA0002974487570000109
The minimization objective function is expressed by the following formula 4:
Figure BDA00029744875700001010
b2: taking the clustering result of the step B1 as the input of the online clustering of the step, namely, the clustering center after the given t-th batch data arrives, and the batch data
Figure BDA00029744875700001011
Wherein: o is t When the t +1 th batch of data arrives, the updated clustering center is expressed by the following formulas 5-6:
Figure BDA00029744875700001012
Figure BDA00029744875700001013
wherein: α is an attenuation factor, when increasing the field, ± select +, when decreasing the field, ± select-;
Figure BDA00029744875700001014
is the kth clustering center when the t-th batch processing arrives;
Figure BDA00029744875700001015
a number indicating the kth cluster;
Figure BDA00029744875700001016
The cluster center of the new field data of the cluster is represented by the following formula 7:
Figure BDA00029744875700001017
wherein:
Figure BDA00029744875700001018
is a certain field data in the t-th batch of data; i.e. i v To represent
Figure BDA00029744875700001019
Belong to item i v Clustering;
Figure BDA00029744875700001020
the number of new data assigned to the cluster is represented by equation 8 below:
Figure BDA00029744875700001021
in summary, the new cluster center point is represented by the following formula 9:
Figure BDA00029744875700001022
and 4, step 4: deploying the sub-services based on an MOEA/D algorithm according to the constructed coupling degree model, the transmission service communication overhead model and the communication delay model, wherein the sub-services comprise the low coupling service in the step 2 and the clustering output result in the two stages in the step 3, and the implementation process specifically comprises the following steps:
c1: definition of S sub For clustered partitioned sub-service and low coupling service sets, S i (1≤i≤N s ) Represented by the following formula 10
Figure BDA0002974487570000111
The sub-services:
Figure BDA0002974487570000112
the divided fields in each sub-service are not repeated, and the union of the two sub-services is null according to the following formula 11:
Figure BDA0002974487570000113
then S sub Can be represented by the following formula 12:
Figure BDA0002974487570000114
recording vis (i, s) j )(1≤i≤N t ，s j ∈S sub ) Whether or not terminal i represented by the following formula 13 subscribes to sub-service s j ：
Figure BDA0002974487570000115
Note the book
Figure BDA0002974487570000116
Indicates whether the condition i-C is satisfied, if so, the method
Figure BDA0002974487570000117
Otherwise
Figure BDA0002974487570000118
Wherein: c is
A constant value; i is a variable represented by the following formula 14:
Figure BDA0002974487570000119
input(s) j ) Representing sub-services s j Whether or not to deploy to edge server E i (1≤i≤N es ) Up, if deployed, put(s) j ) Can be represented by the following formula 15:
put(s j )＝i (15)；
wherein: put(s) j )∈[0，N-1]And is
Figure BDA00029744875700001110
In summary, the objective function for optimizing the response time is expressed by the following equation 16:
Figure BDA00029744875700001111
wherein: i S sub Is the sub-service set S sub Number of servicesAn amount; e is N es A set of edge servers; n is a radical of t Refers to the number of terminals.
Note t (E) j ，s k ) An edge server E represented by the following formula 17 j Handling sub-service jobs k Required time period of (c):
Figure BDA00029744875700001112
wherein:
Figure BDA00029744875700001113
serving a child s k The size of (d);
Figure BDA00029744875700001114
as an edge server E j Computing power of (1), note t max ，t min The method comprises the following steps of respectively representing the longest working time and the shortest working time of the edge server by the following formulas 18-19:
Figure BDA00029744875700001115
Figure BDA00029744875700001116
in summary, the objective function for optimizing the edge server work balance can be represented by the following equation 20:
I 2 ＝min(t max -t min ) (20)；
and the following constraint conditions are satisfied:
Figure BDA00029744875700001117
Figure BDA0002974487570000121
vis(i，s k )∈{0，1}；
Figure BDA0002974487570000122
g(i，E j )＞0；
N p ＞0；
s k ∈S sub ；
1≤i≤N t ，1≤j≤N es ，1≤k≤|S sub |。
c2: converting the multi-objective optimization problem into a plurality of single-objective optimization problems represented by the following formula 21 by using a MOEA/D algorithm:
Figure BDA0002974487570000123
s.t.x∈Ω
wherein: λ ═ λ 1 ，λ 2 ，...，λ m ) As weight vector, for each lambda i Each of (i ═ 1, 2,. m) has λ i Is not less than 0 and
Figure BDA0002974487570000124
Figure BDA0002974487570000125
is a reference vector in which the value of each reference point is the minimum value of each dimension of the objective function, i.e.
Figure BDA0002974487570000126
Inputting a multi-objective optimization problem, a condition for stopping iteration and a population size N pop Weight vector and number of neighbors of weight vector T nb And finally outputting a set PS of pareto optimal points, wherein the specific algorithm is as follows: firstly, initializing PS to be a non-empty set, and setting an initial reference point
Figure BDA0002974487570000127
Calculating each weight vectorThe distance from other vectors and the T nearest to the current individual is calculated nb Individual weight vectors by randomly initializing population individuals
Figure BDA0002974487570000128
Calculating a target value FV i ＝F(x i ) (ii) a For each population individual, randomly selecting two from neighbors, using a genetic operator to generate a solution y, performing Gaussian rounding on the generated new solution to obtain y', and then updating a reference point
Figure BDA0002974487570000129
If the updated reference point z j The value being less than that of the objective function, i.e. z j ＜f j (y'), updating the reference point to z j ＝f j (y'); updating the neighborhood, and for each neighbor j, if the constraint value corresponding to the new solution is less than or equal to the original individual of the neighborhood, namely g (y' | lambda) j ，z)≤g(x j |λ j Z), then the original individual is replaced with the new solution, i.e. x j The target value FV is updated simultaneously when y is equal to y j F (y'); and finally, updating the PS value, judging whether a stopping condition is met, and stopping iteration and outputting the PS if the stopping condition is met.
And 5: after deployment is finished, a multi-target optimal solution can be obtained, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server.
The following takes the specific implementation of the simulation experiment as an example to verify the effectiveness of the coupling degree model, the two-stage method for decoupling the high-coupling service and the sub-service deployment strategy, and further details the present invention.
Example 1
(I) Experimental setup
1-1 degree of coupling model
To validate the degree of coupling model proposed by the present invention, a data set provided by CFETS information technology (shanghai) ltd was used. The data set contains field data for 20 systems subscribed to each service. Through this data set, 15 service-based system subscription states are consolidated out. Then treat the system as an edge server and for 15 clothesAnd performing coupling degree calculation. After the coupling values are obtained, the high coupling threshold is selected by a quartile method, i.e., the top 25%, 50%, and 75% of the services are considered high coupling services, in order from high to low. Wherein,
Figure BDA00029744875700001210
1-2 high-coupling service decoupling model
To verify the effectiveness of the two stages proposed by the present invention on the high coupling service decoupling method, the offline method and the online method were compared and analyzed and used two data sets, one provided by CFETS information technology (shanghai) ltd, and the other being the american census data (1990) data set, which contained 68 attributes for clustering. For the first data set, 15 services were clustered by k-means to verify the effectiveness of the offline decoupling algorithm. For the add-field based online decoupling algorithm, the first 200,000 pieces of data from the second dataset were selected and divided into 10 groups of 20,000 data each. For each set of data, the first 10,000 data were used for offline clustering. The last 10,000 data were used for online clustering, with an average of 5 groups. 4 batches of data are set and the last 2,000 data will be discarded to prevent data corruption and unusable cases. The benchmark algorithm is implemented using only an offline decoupling algorithm for each set of 18,000 data.
In the online decoupling algorithm, the parameter α is set to 0.9. Meanwhile, to verify the validity of the delete fragment based on-line decoupling algorithm, for the first dataset, the batch is set to 2, and each batch will be (n) min 5% +3) as the number of fragments to be deleted. Wherein the deleted fragments are randomly generated; n is min Is the minimum number of each cluster. For the second data set, the first 200,000 pieces of data were selected from the second data set and divided into 10 groups of 20,000 data each. For each set of data, the first 10,000 data are used, while the last 10,000 data are discarded. Set 4 batches of data, each batch to be (n) min 5% +3) as the number of segments to be deleted, wherein the segments to be deleted will be generated randomly. Benchmark algorithm onlyBy using an offline decoupling algorithm for each set of remaining data. Since no new data is introduced in the deleted fields, there is no need to make the model sensitive to the deleted data, so the parameter α is 1. The offline and online algorithms are compared to the three indicators "bandwidth savings", "average latency" and "algorithm run time".
For the bandwidth indicator saved, the communication overhead is calculated according to the aforementioned f formula
Figure BDA00029744875700001312
Set A to 20 bytes and set each field size to 200 bytes, which contains 150 bytes of metadata and 50 bytes of data. If sub-service S i Included
Figure BDA0002974487570000131
Segment, size of sub-service is obtained
Figure BDA0002974487570000132
For the average latency indicator, note t 0 Is an initial time, N b Is the number of batches. The moment when the ith batch of data starts to be transmitted is recorded as t 2i-1 And for the ith batch of data,
Figure BDA0002974487570000133
represents the transmission from the cloud server to the terminal k (1 ≦ k ≦ N t ) Each field having a size b and a transmission rate of
Figure BDA0002974487570000134
Figure BDA0002974487570000135
Is the moment when terminal k starts transmission. Therefore, it can be concluded that the transmission of the ith batch of data is completed at time t 2i Namely:
Figure BDA0002974487570000136
in summary, the average latency of the offline decoupling algorithm is:
Figure BDA0002974487570000137
wherein: t is t nt Time for next offline decoupling clustering; a is a specific time point in the time period.
The average latency of the on-line decoupling algorithm is:
Figure BDA0002974487570000138
setting an initial time to t 0 Is 0, t 2i-1 In the interval [24h, 72h]In (1),
Figure BDA0002974487570000139
set to 2000. Each field size b is 200 bytes.
Figure BDA00029744875700001310
Will be taken randomly from 0-2 h. a is set to 0.5. Wherein t is nt Is equal to
Figure BDA00029744875700001311
Since the offline algorithm will execute immediately after the last batch of data arrives.
1-3 sub-service deployment policies
In order to verify the effectiveness of the MOEA/D adopted by the invention, the MOEA/D is compared and analyzed by using three reference algorithms, namely RAND, GA and PSO. The data sets adopted are the base station data set of Shanghai telecommunication and the track data set of Shanghai taxi. The data set of base stations in the shanghai telecommunications contains, among other things, the exact location information of 3,233 base stations and the information of the mobile subscribers connected to these base stations. This data set is used to model the location information of base stations and cloud servers, some edge servers being randomly configured on some base stations. The shanghai taxi track dataset contains tracks of 4,328 taxis from shanghai on 2 months and 20 days of 2007. A specific time period is randomly selected from the data set, then a certain number of taxis are randomly selected during the time period, and the position of the taxi is simulated as the position of the terminal.
Since the position information in the data set is composed of latitude and longitude, given longitude and latitude are calculated as the following expression 1-3 between two points A (x) 1 ，y 1 ) And B (x) 2 ，y 2 ) Distance Len of AB ：
Figure BDA0002974487570000141
Wherein: r is 6371 kilometer of the radius of the earth; a ═ x 1 -x 2 ；b＝y 1 -y 2 。
In the wired communication model, two edge servers E i 、E j Bandwidth B (E) in between i ，E j ) In [10,20 ]]Evenly distributed in Mhz. In the wireless communication model, the wireless channel gain g (i, E) j ) Is 127+30 × logd. Where d is the terminal i to the edge server E j The distance between them; terminal i and edge server E j B (i, E) of the channel bandwidth in between j ) Randomly generated in 10Mhz to 20 Mhz; noise power is set to 2 × 10 -13 W, the transmission power of each terminal is 0.5W; the sub-service size is set between 300MB and 600 MB; the storage space of the edge server is in the interval of [10, 16 ]]GB; the computational resources are 25Ghz and the computational intensity is [500,1000 ]]Cycle/bit. Thus, the computing power of the edge server
Figure BDA0002974487570000143
Is randomly generated between 25-50 bit/s.
(II) results of the experiment
2-1 degree of coupling model
The coupling values of the 15 services in the first data set are calculated according to the coupling definition and sorted from low to high according to the coupling values, and the calculation results are detailed in the service coupling values of table 1 below:
Table 1: service coupling degree value
Figure BDA0002974487570000142
Figure BDA0002974487570000151
The services in table 1 above are the top 25%, 50% and 75%, respectively, and are considered to be highly coupled services.
Referring to fig. 1, services with a degree of coupling exceeding 25% are shown, sorted according to the degree of coupling value.
2-2 high coupling service decoupling model
Referring to fig. 2, it can be seen that the communication cost of most services after decoupling is reduced by about 40% compared to that before decoupling, and only service 8 after decoupling has a higher communication cost than that before decoupling. This is because after decoupling the service 8, all edge servers subscribing to the service 8 still fully subscribe to all sub-services divided by the service 8. The additional overhead will be accumulated after decoupling, so the communication cost of service 8 after decoupling is higher than before decoupling.
Referring to fig. 3-4, the results of the algorithm runtime for 10 data sets in the second data set are shown, respectively, using offline and online algorithms to solve the problem of adding (or deleting) fields by the service. It can be seen from the figure that the running time required by the online algorithm is less than that required by the offline algorithm, whether the segment is added or deleted, without reducing the accuracy of the algorithm. When the field adding service is considered, the online algorithm can save 27% of the time required for completing the offline algorithm on average; the online algorithm can save on average 8% of the time required to complete the offline algorithm when considering the service of deleting segments. This is because online algorithms require only one round to divide all data, while offline algorithms typically require several rounds of algorithms to converge.
Referring to fig. 5, the average wait time for offline and online algorithms with different numbers of terminals is shown. It can be seen from the figure that the average latency of the online algorithm with six different sets of terminal numbers is much lower than the average latency of the offline algorithm. The average latency of the online algorithm is substantially 4 s. It depends on the end of transmission time of the last edge server, which is usually determined by the start transmission time and the transmission time of the edge server. From the point of view of average latency, online algorithms are more conducive to maintaining a lower degree of coupling for real-time maintenance services.
2-3 sub-service deployment model
Referring to FIGS. 6-8, the number of edge servers is shown as 3, 4, and 5, respectively; when the number of the services is 5, 10, 20 and 30, and the number of the terminals is 5, 10, 20 and 30, the optimal solution of service deployment is obtained through three algorithms of MOEA/D, PSO and GA. Function value of mu 1 I 1 +μ 2 I 2 Wherein: mu.s 1 ＝1，μ 2 50. It can be seen from the figure that the optimal solutions obtained by the three algorithms are consistent when the magnitude is small. When the amount of data is gradually increased, the optimal solution based on the MOEA/D algorithm is better than the other two algorithms. This is because the GA algorithm may be trapped in the local optimal solution, and in the case of the PSO algorithm being in a convergent state, since the particles all move toward the optimal solution, the late convergence speed is slow and the accuracy is not high.
Referring to fig. 6 to 8, it is shown that when the number of edge servers is 3, 4 and 5, respectively, where (fig. a), (fig. b) (fig. c) and (fig. D) are 5, 10, 20 and 30 for the number of services, respectively, the optimal solution of service deployment is obtained through three algorithms, MOEA/D, PSO and GA, with the number of terminals according to 5, 10, 20 and 30.
The invention adopts the coupling degree calculation of the centralized service and then selects the service with high coupling degree to carry out two-stage decoupling. Then, under the condition that the response time is minimized, the MOEA/D multi-objective optimization method is used for deploying the decoupled sub-services and the low-coupling-degree services on the edge server in a fair manner, the deployment result is closer to the optimal solution, the problem of response time optimization of fair deployment after centralized service decoupling in edge computing is solved well, the service communication cost can be reduced by 40%, the decoupling algorithm comprises an off-line stage and an on-line stage, and the algorithm completion time of the on-line stage can be reduced by 27% maximally compared with the algorithm completion time of the off-line stage.
The above examples are only for further illustration of the present invention and are not intended to limit the present invention, and all equivalent implementations of the present invention should be included within the scope of the claims of the present invention.

Claims (5)

1. A response time optimization method for fair deployment after centralized service decoupling is characterized in that a service decoupling method and an MOEA/D algorithm-based sub-service are adopted for deployment, the decoupled sub-service and a low-coupling-degree service are deployed on an edge server and multi-objective optimization is carried out, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server, and the specific optimization comprises the following steps:
step l: constructing a system architecture and coupling degree model, a transmission service communication overhead model and a communication delay model of the edge cloud;
step 2: calculating the coupling degree of all the services, judging the calculated coupling degree and a set coupling degree threshold value, and if the calculated coupling degree is lower than the coupling degree threshold value, directly deploying the sub-services; if the coupling degree is higher than the threshold, decoupling the service;
and step 3: performing off-line stage decoupling and on-line stage decoupling on the coupling service higher than the coupling degree threshold, wherein the off-line stage decoupling is to perform service field-based feature extraction according to the subscription condition of each edge server to the high coupling service, and clustering the high coupling service by using a k-means-based method; the on-line stage decoupling is to use the off-line decoupled clustering result as the initial input of on-line clustering, and to use a streaming k-means based method to perform real-time clustering on the services with added or deleted fields;
And 4, step 4: deploying sub-services by using an MOEA/D algorithm according to the constructed coupling degree model, the transmission service communication overhead model and the communication delay model, wherein the sub-services comprise the low coupling service in the step 2 and the clustering output result of the two stages in the step 3;
and 5: after deployment is finished, a multi-target optimal solution can be obtained, so that the overall response time is shortest under the condition of ensuring the load fairness of the edge server.
2. The method for optimizing response time for fair deployment after centralized service decoupling according to claim l, wherein the implementation process of step l specifically includes the following steps:
step A1: construction of degree of coupling model
Establishing cloud server to maintain N s A service, each service S i (1≤i≤N s ) By
Figure FDA0002974487560000018
Field composition for edge server N es Each edge server E j (1≤j≤N es ) Subscribing a plurality of fields in one or more services according to the requirements of the users;
is provided with
Figure FDA0002974487560000011
Representing edge servers E j And service S i The subscription relationship of the middle field k, if E j Subscribed to service S i K in (1), then
Figure FDA0002974487560000012
If the value is l, otherwise, the value is 0, and the influence of different operations of the fields represented by the following formulas a to c on the service is respectively introduced
Figure FDA0002974487560000013
And
Figure FDA0002974487560000014
Figure FDA0002974487560000015
Figure FDA0002974487560000016
Figure FDA0002974487560000017
thus, the edge server E j Subscription service S i The influence of the middle field k on the middle field is represented by the following formula d
Figure FDA0002974487560000021
Figure FDA0002974487560000022
Wherein: w is a l Impact coefficients for different operations;
thus, edge server E j Subscription service S i The influence of (a) is represented by the following formula e
Figure FDA0002974487560000023
Figure FDA0002974487560000024
Wherein: p is a radical of k Is the modification frequency of field k;
to sum up, service S i The calculation formula of the coupling degree is expressed by the following formula f:
Figure FDA0002974487560000025
step A2: construction of transport service communication overhead model
Recording service S i Offload from cloud Server to edge Server E j Has an additional information size of A (A > 0), and serves S i Size B i Then transmitting service S i Overhead of communication
Figure FDA0002974487560000026
Represented by the following formula g:
Figure FDA0002974487560000027
will S i Is divided into
Figure FDA0002974487560000028
Sub-services, i.e.
Figure FDA0002974487560000029
Partitioned sub-services
Figure FDA00029744875600000210
A size of
Figure FDA00029744875600000211
Transmits its sub-service
Figure FDA00029744875600000212
Overhead of communication
Figure FDA00029744875600000213
Represented by the following formula h:
Figure FDA00029744875600000214
wherein:
Figure FDA00029744875600000215
satisfy the requirement of
Figure FDA00029744875600000216
Edge server E k Subscribe to sonService
Figure FDA00029744875600000217
Fields of China, i.e. considered as subscribed to a sub-service
Figure FDA00029744875600000218
Its edge server E k Whether or not sub-services are subscribed to
Figure FDA00029744875600000219
Then it is represented by the following formula i
Figure FDA00029744875600000220
Figure FDA00029744875600000221
Then, the edge server E k Accepting sub-services offloaded from cloud servers
Figure FDA00029744875600000222
The required communication overhead is represented by the following j equation:
Figure FDA00029744875600000223
then, the edge server E k Accepting service S offloaded from cloud server i The required communication overhead is represented by the following k:
Figure FDA00029744875600000224
therefore, all edge servers receive the service S in the cloud server through a given service dividing method i The communication overhead is expressed by the following equation m:
Figure FDA0002974487560000031
and satisfies the following constraints:
Figure FDA0002974487560000032
Figure FDA0002974487560000033
Figure FDA0002974487560000034
Figure FDA0002974487560000035
A＞0，
Figure FDA0002974487560000036
Figure FDA0002974487560000037
step A3: construction of communication delay model
Note the book
Figure FDA0002974487560000038
Two edge servers E represented by the following n formula i And E j Inter-transmission delay:
Figure FDA0002974487560000039
wherein: b (E) i ，E j ) Is the bandwidth; w (E) i ，E j ) Is represented by the following r formula in an edge server E i To the edge server E j Sub-service set S transmitted between nb The size of (2):
Figure FDA00029744875600000310
note the book
Figure FDA00029744875600000311
Is the propagation delay expressed by the following equation:
Figure FDA00029744875600000312
wherein: d (E) i ，E j ) Is the distance between two edge servers; theta is the propagation speed of the electric signal in the optical cable; if there is no route between the two edge servers, then
Figure FDA00029744875600000313
Will be set to infinity;
in summary, the wired communication delay between two edge servers is represented by the following equation:
Figure FDA00029744875600000314
wherein:
Figure FDA00029744875600000315
for terminal i to edge server E j The delay of the wireless transmission distance between the two is represented by the following u formula:
Figure FDA00029744875600000316
wherein: w (i, E) j ) Representing terminal i to edge server E j The size of the transmission task, and the maximum data transmission rate tr (i, E) j ) Represented by the following formula v:
Figure FDA0002974487560000041
wherein: b (i, E) j ) For terminal i to edge server E j Bandwidth of the wireless communication link to transmit data;
Figure FDA0002974487560000042
signal-to-noise ratio; p i Is the transmission power of terminal i; g (i, E) j ) For terminal i and edge server E j A signal gain in between; n is a radical of p Is the in-channel noise power;
thus, the terminal i goes to the edge server E j Is represented by the following w formula:
Figure FDA0002974487560000043
wherein: e i Is located next to the base station closest to terminal i.
3. The method for optimizing response time for fair deployment after centralized service decoupling according to claim l, wherein the implementation process of step 2 specifically includes: calculating the coupling degrees of all services by using a coupling degree model formula; judging whether the coupling degree of the service is higher than a given coupling degree threshold value or not, and if the coupling degree of the service is lower than the coupling degree threshold value M, namely low-coupling service, directly deploying the service; if the coupling degree is higher than the threshold value, the service is called as a high coupling service, the service needs to be decoupled, and then the service after decoupling, namely the deployment of the sub-service, is carried out.
4. The response time optimization method for fair deployment after centralized service decoupling according to claim 1, wherein the implementation process of step 3 specifically includes the following steps:
step B1: memory two-dimensional matrix
Figure FDA00029744875600000414
For service S i (1≤i≤N s ) The feature matrix is expressed by the following formula I, and the field information of all the edge servers subscribing the service is stored:
Figure FDA00029744875600000415
note book
Figure FDA0002974487560000044
Representing a service S for the following formula 2 i The feature vector of field k:
Figure FDA0002974487560000045
then, a two-dimensional matrix
Figure FDA0002974487560000046
Feature matrix represented by the following formula 3
Figure FDA0002974487560000047
Figure FDA0002974487560000048
Wherein,
Figure FDA0002974487560000049
for service S i The number of fields contained in;
according to the above characteristic momentsMatrix of
Figure FDA00029744875600000410
Performing k-means clustering on the obtained data, determining k value, and initializing clustering center by using k-means +
Figure FDA00029744875600000411
And the minimization objective function is expressed by the following equation 4:
Figure FDA00029744875600000412
step B2: taking the clustering result of the step Bl as the input of the online clustering of the step, namely, giving the clustering center after the t-th batch of data arrives, and batch of data
Figure FDA00029744875600000413
Wherein: o is t When the t + l data arrives, the updated clustering center is expressed by the following formulas 5-6:
Figure FDA0002974487560000051
Figure FDA0002974487560000052
wherein: α is an attenuation factor, when increasing the field, ± select +, when decreasing the field, ± select-;
Figure FDA0002974487560000053
is the kth clustering center when the t-th batch processing arrives;
Figure FDA0002974487560000054
a number indicating the kth cluster;
Figure FDA0002974487560000055
the cluster center of the new field data of the cluster is represented by the following formula 7:
Figure FDA0002974487560000056
wherein:
Figure FDA0002974487560000057
is a certain field data in the t-th batch of data; i.e. i v To represent
Figure FDA0002974487560000058
Belong to item i v Clustering;
Figure FDA0002974487560000059
the number of new data assigned to the cluster is represented by equation 8 below:
Figure FDA00029744875600000510
in summary, the new cluster center point is represented by the following formula 9:
Figure FDA00029744875600000511
5. the response time optimization method for fair deployment after centralized service decoupling according to claim l, wherein the implementation process of step 4 specifically includes the following steps:
Step Cl: definition of S sub For clustered partitioned sub-service and low coupling service sets, S i (1≤i≤N s ) Represented by the following formula 10
Figure FDA00029744875600000512
The sub-services:
Figure FDA00029744875600000513
each divided sub-service is expressed by the following formula 11, and the union of the two sub-services is null:
Figure FDA00029744875600000514
then S sub Can be represented by the following formula 12:
Figure FDA00029744875600000515
recording vis (i, s) j )(1≤i≤N t ，s j ∈S sub ) Whether or not terminal i represented by the following formula 13 subscribes to sub-service s j ：
Figure FDA00029744875600000516
Note the book
Figure FDA00029744875600000517
Indicates whether the condition i-C is satisfied, if so, the method
Figure FDA00029744875600000518
Otherwise
Figure FDA00029744875600000519
Wherein: c is a constant; i is a variable represented by the following formula 14:
Figure FDA00029744875600000520
input(s) j ) Representing sub-services s j Whether or not to deploy to edge server E i (1≤i≤N es ) Up, if deployed, put(s) j ) Can be represented by the following formula 15:
put(s j )＝i(15)；
wherein: put(s) j )∈[0，N-1]And is
Figure FDA00029744875600000521
In summary, the objective function for optimizing the response time is expressed by the following equation 16:
Figure FDA0002974487560000061
wherein: i S sub Is the sub-service set S sub The number of services; e is N es A set of edge servers; n is a radical of t Refers to the number of terminals;
note t (E) j ，s k ) An edge server E represented by the following formula 17 j Handling sub-service jobs k Required time period of (c):
Figure FDA0002974487560000062
wherein:
Figure FDA0002974487560000063
serving a child s k The size of (d);
Figure FDA0002974487560000064
as an edge server E j Computing power of (1), note t max ，t min Respectively representing the longest working time and the shortest working time of the edge server represented by the following formulas 18-19:
Figure FDA0002974487560000065
Figure FDA0002974487560000066
in summary, the objective function for optimizing the operation balance of the edge server is represented by the following equation 20:
I 2 ＝min(t max -t min ) (20)；
And the following constraint conditions are satisfied:
Figure FDA0002974487560000067
Figure FDA0002974487560000068
vis(i，s k )∈{0，1}；
Figure FDA0002974487560000069
g(i，E j )＞0；
N p ＞0；
s k ∈S sub ；
1≤i≤N t ，1≤j≤N es ，1≤k≤|S sub |；
step C2: converting the multi-objective optimization problem into a plurality of single-objective optimization problems expressed by the following 2l formula by using a MOEA/D algorithm:
Figure FDA00029744875600000610
s.t.x∈Ω
wherein: λ ═ λ 1 ，λ 2 ，...，λ m ) As weight vector, for each lambda i Each of (i ═ 1, 2,. m) has λ i Is not less than 0 and
Figure FDA00029744875600000611
Figure FDA00029744875600000612
is a reference vector in which the value of each reference point is the minimum value of each dimension of the objective function, i.e.
Figure FDA00029744875600000613
Figure FDA00029744875600000614
Inputting a multi-objective optimization problem, a condition for stopping iteration and a population size N pop Weight vector and number of neighbors of weight vector T nb And finally outputting a set PS of pareto optimal points, wherein the specific algorithm is as follows: firstly, initializing PS to be a non-empty set, and setting an initial reference point
Figure FDA00029744875600000615
Calculating the distance between each weight vector and other vectors, and calculating the T nearest to the current individual nb Individual weight vectors by randomly initializing population individuals
Figure FDA00029744875600000616
Calculating a target value FV i ＝F(x i ) (ii) a For each population individual, randomly selecting two from neighbors, using a genetic operator to generate a solution y, performing Gaussian rounding on the generated new solution to obtain y', and then updating a reference point
Figure FDA0002974487560000071
If the updated reference point z j The value being less than that of the objective function, i.e. z j ＜f j (y'), updating the reference point toz j ＝f j (y'); updating the neighborhood, and for each neighbor j, if the constraint value corresponding to the new solution is less than or equal to the original individual of the neighborhood, namely g (y' | lambda) j ，z)≤g(x j |λ j Z), then the original individual is replaced by the new solution, i.e. x) j The target value FV is updated simultaneously when y is equal to y j F (y'); and finally, updating the PS value, judging whether a stopping condition is met, and stopping iteration and outputting the PS if the stopping condition is met.
CN202110271251.3A 2021-03-12 2021-03-12 Response time optimization method for fair deployment after centralized service decoupling Active CN112948058B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110271251.3A CN112948058B (en) 2021-03-12 2021-03-12 Response time optimization method for fair deployment after centralized service decoupling

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110271251.3A CN112948058B (en) 2021-03-12 2021-03-12 Response time optimization method for fair deployment after centralized service decoupling

Publications (2)

Publication Number Publication Date
CN112948058A CN112948058A (en) 2021-06-11
CN112948058B true CN112948058B (en) 2022-07-29

Family

ID=76229636

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110271251.3A Active CN112948058B (en) 2021-03-12 2021-03-12 Response time optimization method for fair deployment after centralized service decoupling

Country Status (1)

Country Link
CN (1) CN112948058B (en)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108701182A (en) * 2016-08-31 2018-10-23 甲骨文国际公司 The data management of multi-tenant identity cloud service
CN111159207A (en) * 2019-12-16 2020-05-15 中国建设银行股份有限公司 Information processing method and device
CN111932027A (en) * 2020-08-28 2020-11-13 电子科技大学 Cloud service comprehensive scheduling optimization system and method fusing edge facilities

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10467036B2 (en) * 2014-09-30 2019-11-05 International Business Machines Corporation Dynamic metering adjustment for service management of computing platform
US10778709B2 (en) * 2018-10-31 2020-09-15 International Business Machines Corporation Cloud-native extensibility provided to security analytics

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108701182A (en) * 2016-08-31 2018-10-23 甲骨文国际公司 The data management of multi-tenant identity cloud service
CN111159207A (en) * 2019-12-16 2020-05-15 中国建设银行股份有限公司 Information processing method and device
CN111932027A (en) * 2020-08-28 2020-11-13 电子科技大学 Cloud service comprehensive scheduling optimization system and method fusing edge facilities

Also Published As

Publication number Publication date
CN112948058A (en) 2021-06-11

Similar Documents

Publication Publication Date Title
Feng et al. Joint service pricing and cooperative relay communication for federated learning
CN112512056B (en) Multi-objective optimization calculation unloading method in mobile edge calculation network
CN108134843B (en) Service function chain deployment method under 5G-C-RAN scene
CN109885397B (en) Delay optimization load task migration algorithm in edge computing environment
CN110717300B (en) Edge calculation task allocation method for real-time online monitoring service of power internet of things
CN110570075B (en) Power business edge calculation task allocation method and device
CN112187891B (en) Load optimization method and device of edge computing node set based on multiple services
CN110557732A (en) vehicle edge computing network task unloading load balancing system and balancing method
CN111836284B (en) Energy consumption optimization calculation and unloading method and system based on mobile edge calculation
CN110647403A (en) Cloud computing resource allocation method in multi-user MEC system
CN111796880A (en) Unloading scheduling method for edge cloud computing task
CN112948058B (en) Response time optimization method for fair deployment after centralized service decoupling
CN112596910A (en) Cloud computing resource scheduling method in multi-user MEC system
CN114466335A (en) Game theory-based joint optimization method in D2D-assisted MEC system
CN113676357A (en) Decision method for edge data processing in power internet of things and application thereof
Zhong et al. Slice allocation of 5G network for smart grid with deep reinforcement learning ACKTR
CN111580943A (en) Task scheduling method oriented to multi-hop unloading in low-delay edge calculation
CN113784372B (en) Terminal multi-service model-oriented joint optimization method
CN114615705B (en) Single-user resource allocation strategy method based on 5G network
CN114390489B (en) End-to-end network slice servitization deployment method
CN116806043A (en) Routing method, device, electronic equipment and mobile edge network
CN109921991A (en) A kind of SDN controller portion arranging method based on Dinkelbach
CN113923224B (en) Electric power internet of things task unloading method, server and terminal
Singhal et al. Resource-aware Deployment of Dynamic DNNs over Multi-tiered Interconnected Systems
CN115051999B (en) Energy consumption optimal task unloading method, device and system based on cloud edge cooperation

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
GR01 Patent grant
GR01 Patent grant