CN110532504B - QoS constraint decomposition method for constraint intensity perception of service combination - Google Patents

Abstract

The invention provides a global QoS constraint decomposition method oriented to service combination and constraint intensity perception. The invention defines a measurement method of user constraint intensity, designs a relaxation factor adaptive adjustment method based on fuzzy reasoning rules, and constructs a QoS constraint decomposition model oriented to service combination and constraint intensity perception. Using this model, in the constraint decomposition stage, when the user constraints are weak, the candidate services for each task can be effectively eliminated to reduce the size of the solution space when the global optimization method is used; when the user constraints are strong, each task can be A task retains a certain number of candidate services to increase the probability of finding a feasible combination scheme when combining services.

Description

A Constraint Strength Aware QoS Constraint Decomposition Method for Service Composition

technical field

The invention relates to the field of service combination optimization, in particular to a global QoS constraint decomposition method for service combination-oriented constraint intensity perception, which can be used to solve the QoS-aware service combination optimization problem.

Background technique

The QoS (Quality of Service)-aware service composition problem is a hotspot of academic research, and its purpose is to efficiently select composite services that satisfy the user's global constraints and user preferences according to the service's QoS.

Existing QoS-aware service composition methods can be divided into three categories: local optimization strategy, global optimization strategy and decomposition strategy based on global QoS constraints. The local optimization strategy is not easy to satisfy the user's global QoS constraints; the global optimization strategy often requires high time complexity; the service composition method based on the global QoS constraint decomposition strategy divides the service composition process into two parts: constraint decomposition and service optimization. flexible.

Existing global QoS constraint decomposition models can be divided into three categories: constraint decomposition models based on empirical formulas, which have poor adaptability; decomposition models that guarantee global QoS constraints, such models do not have to consider global QoS in the service optimization stage Constraints, so local optimization methods can be used to improve efficiency, but some feasible solutions will be lost. When the user's constraint intensity is high, it is easy to find no feasible combination scheme; the decomposition model that guarantees no loss of feasible solutions cannot guarantee the overall situation. Constraints, and when the user constraints are low, the efficiency of eliminating candidate services and reducing the solution search space is poor.

The invention aims at improving the self-adaptive ability of the model to the user constraint intensity by introducing a relaxation factor on the basis of the existing global QoS constraint decomposition model. That is: when the user constraint strength is strong, the probability of losing feasible solutions can be reduced, thereby increasing the probability of finding a feasible combination solution; when the user constraint strength is low, candidate services can be eliminated more effectively and the search space can be reduced.

Contents of the invention

The present invention is oriented to the optimization problem of QoS-aware service combination, and proposes a global QoS constraint decomposition model with constraint strength self-adaption. It mainly involves the following aspects:

(1) A global QoS constraint decomposition model with self-adaptive constraint strength for service composition.

Consider a workflow containing n tasks T={t ₁ ,t ₂ ,...,t _n }, task t _i has m _i candidate services. Assume that the user proposes upper limit constraints cq={cq ₁ ,cq ₂ ,…,cq _u } for u QoS attributes such as q ₁ , q ₂ ,…,q _u , and set them as detrimental attributes (gain attribute Can be converted into a debuff attribute by multiplying by -1). After constraint decomposition, the upper limit constraint on the jth QoS of task t _i is xq _ij . The constraint decomposition model for constructing global QoS is as follows:

Target:

Restrictions:

xq _ir ∈ [min(QoS(s _ij , q _r )), max(QoS(s _ij , q _r ))], i∈[1, n] ③

Equation ① describes the optimization objective of the model, which is to maximize the product of the number of candidate services satisfying the upper limit constraint xq _ij for all tasks. Among them, #{A} represents the number of elements in the set A; QoS(s, q _r ) represents the value of the q _r attribute of the service s.

Equation ② is used for the constraint strength of self-application users. Among them, QoS(cs ^* , q _r ) represents the aggregation value of the rth QoS of the whole workflow when the rth QoS value of task t _i is xq _ir . γ _r is the introduced relaxation factor. When the constraint strength is strong, γ _r should take a value greater than 0 to retain more candidate services and improve the success rate of finding a combination solution; when it is weak, γ _r can be 0 or less than The value of 0 is to ensure global constraints or to eliminate some candidate services to reduce the solution space.

Formula ③ is used to specify the value range of xq _ir . Among them, min(Qos(s _ij , q _r )), max(Qos(s _ij , q _r )) represent the minimum value and maximum value of attribute q _r in all candidate services of task t _i respectively.

(2) Definition of constraint strength.

则用户对q_r的约束强度ω_r(r＝1,2,…,u)由公式④确定。Suppose there is a composite service cs ^# = {s ₁ ^# , s ₁ ^# , ..., s _n ^# },

Then the user's constraint strength ω _r (r=1,2,...,u) on q r is determined _by formula ④.

Among them, QoS(cs ^# , q _r ) represents the aggregation value of the rth QoS of cs ^# .

(3) An adaptive adjustment method of relaxation factor based on fuzzy reasoning.

The value of the relaxation factor is mainly affected by factors such as the number of tasks, the number of constraints, and the strength of constraints. Since the number of constraints is usually small, the value of the relaxation factor can be determined for each situation of the number of constraints.

Taking the case where the number of constraints is 1 as an example, set the domain of discourse of the number of tasks as [1,200], the fuzzy subset as {N1, N2, N3}, and the membership function as shown in Figure 1; the domain of discourse of the constraint strength is [-1,1], divided into 13 grades, from small to large in order of W1, W2,...,W13, the membership function is shown in Figure 2; the domain of the relaxation factor is [-1,1], divided into 15 There are four grades, from small to large in order of S1, S2,..., S15, and the membership functions are shown in Figure 3. According to the fuzzy inference rules determined in Table 1, the projection surface of the relaxation factor can be obtained as shown in Figure 4.

Table 1 Fuzzy inference rules of relaxation factors

The advantages of the present invention are:

(1) The constructed global QoS constraint decomposition model has the capability of self-adaptive constraint strength. When the constraint strength is strong, the probability of finding a feasible combination scheme can be increased; when the constraint strength is weak, candidate services can be effectively eliminated and the search space can be reduced.

(2) A method for measuring the strength of user constraints is designed.

(3) A relaxation factor adaptive method based on fuzzy inference rules is designed, which can better adapt to different task scales and constraint strengths.

Description of drawings

Figure 1 is the membership function of the number of tasks.

Figure 2 is the membership function of the constraint strength.

Figure 3 is the membership function of the relaxation factor.

Figure 4 is the projection surface of the relaxation factor.

Detailed ways

The invention is a global QoS constraint decomposition method with self-adaptive constraint strength oriented to service combination. Specific steps are as follows:

(1) According to the service composition problem, determine the number of tasks, the global constraints given by the user, the number of constraints and other information.

(2) Calculate the user constraint strength of each QoS according to formula ④.

(3) Using fuzzy inference rules to determine the value of the relaxation factor for each constraint according to the number of tasks, the strength of constraints, and the number of constraints. For example, when the number of constraints is 1, the membership function of the number of design tasks is shown in Figure 1, the membership function of the user constraint strength is shown in Figure 2, the membership function of the relaxation factor is shown in Figure 3, and the fuzzy inference rules are shown in Table 1 is determined, the projection surface of the relaxation factor shown in Figure 4 can be obtained. Therefore, for the number of tasks determined by (1) and the user constraint strength determined by (2), the value of the corresponding relaxation factor can be determined according to FIG. 4 .

(4) Construct an optimization model with the optimal objective described by formula ① and the constraints determined by formula ② and ③.

(5) Use greedy algorithm or intelligent optimization algorithm to solve the optimization model in (4), and optimize the service combination according to the obtained solution, that is, the local constraints on each task. This part of work does not belong to the content of the present invention.

Claims (1)

1. A QoS constraint decomposition method facing constraint intensity perception of service combination is characterized in that:

(1) QoS constraint decomposition model facing constraint intensity perception of service combination;

consider a task containing n tasks t= { T ₁ ，t ₂ ，...，t _n Workflow, task t }, of _i With m _i Candidate services, set user pair q ₁ ，q ₂ ，...，q _u The u QoS attributes put forward an upper bound constraint cq= { cq ₁ ，cq ₂ ，...，cq _u Setting cq _r Is a subtractive attribute; if cq _r Is a gain attribute, which is multiplied by-1 to be converted into a loss attribute, and the constraint is decomposed to a task t _i The upper bound of the r-th QoS of (c) is xq _ir The constraint decomposition model of global QoS is constructed as follows:

the object is:

constraint conditions:

xq _ir ∈[min(QoS(s _ij ，q _r ))，max(QoS(s _ij ，q _r ))]，i∈[1，n] ③

equation (1) describes the optimization objective of the model, i.e., maximizing the satisfaction of the upper bound constraint in the candidate services for all tasks as xq _ij Wherein, # { A } represents the number of elements in set A; qoS (s, q) _r ) Q representing service s _r A value of the attribute;

equation (2) is used for constraint strength of self-application user, wherein QoS (cs) ^* ，q _r ) Representing when task t _i The r-th QoS is given a value xq _ir At this time, the aggregate value, γ, of the r-th QoS for the entire workflow _r For the introduced relaxation factor, gamma is the factor when the constraint strength is strong _r Taking a value greater than 0 to reserve more candidate services, and improving the success rate of searching a combination scheme; when weaker, gamma _r A value of 0 or less than 0 to ensure global constraints or multiple elimination of some candidate services, reducing solution space;

formula (3) is used for convention xq _ir Is a value range of (1)Middle min (QoS(s) _ij ，q _r ))、max(QoS(s _ij ，q _r ) Respectively represent tasks t _i Attribute q _r Minimum and maximum values of (2);

(2) Defining constraint intensity;

assume that there is a combinational service cs ^# ＝{s ₁ ^# ，s ₁ ^# ，...，s _n ^# }，

User pair q _r Is of constraint strength omega _r (r=1, 2,., u) is determined by formula (4);

wherein QoS (cs) ^# ，q _r ) Representation cs ^# Aggregate value for the r-th QoS of (c);

(3) A relaxation factor self-adaptive adjustment method based on fuzzy reasoning;

the value of the relaxation factor is influenced by the number of tasks, the number of constraints and the constraint intensity, and the value of the relaxation factor is determined according to the situations of each constraint number, namely, the number of tasks, the constraint intensity and the domain, fuzzy subset and membership function of the relaxation factor are respectively designed according to the given constraint number, and the reasoning rules among the number of tasks, the constraint intensity and the relaxation factor are designed, so that the projection curved surface of the relaxation factor is determined.

Images