CN103425524B - Method and system for balancing multi-service terminal aggregation - Google Patents

Abstract

The invention discloses a method and system for balancing multi-service terminal aggregation. The method comprises the steps that firstly, the dimension reduction process is carried out on a terminal aggregation model for a plurality of ubiquitous services to obtain an MMKP model, and secondly, the MMKP model is solved through a terminal aggregation algorithm based on balance to obtain a vector quantity solution of a balancing service with the highest total benefits, wherein the vector quantity solution serves as an optimal solution of the MMKP model. The terminal aggregation EDC algorithm based on the balance is adopted in the process of solving, wherein a heuristic algorithm is the core of the terminal aggregation EDC algorithm. After an initial feasible solution is found in the algorithm, one-time forward direction upgrading is carried out under the condition of resource constraint to obtain a locally optimal solution, then the reverse upgrading process containing at least one-time degrading is carried out under the condition of loosened constraints, two times of upgrading are carried out, and the problem that one-direction searching only can obtain the locally primal solution is effectively solved. The comprehensiveness of benefits of multi-terminal services is met, meanwhile, the problem of difference among users is solved, and the balance of multi-terminal aggregation inside the system is achieved.

Description

Method and system for balancing multi-service terminal aggregation

Technical Field

The present invention relates to the field of wireless communication technologies, and in particular, to a method and a system for balancing multi-service terminal aggregation.

Background

At present, the high-speed and ubiquitous development of a network greatly expands the edge of the network, a large number of heterogeneous terminals are arranged at the edge of the network and around users, and are interconnected through heterogeneous network access modes to support the intercommunication between people and people, between people and objects, and between objects, so that great changes are brought to the edge of the network, and ubiquitous peripheral environments are formed, such as personal area networks, smart homes, opportunity networks and the like. Meanwhile, the continuous emergence of communication technologies such as LTE (Long Term Evolution), WLAN (Wireless Local Area network), WiMAX (world Interoperability for Microwave Access), etc. has led to rapid increase in user demand and push the development of ubiquitous Networks, so that ubiquitous peripheral environments can support richer service functions and provide better service experience.

In the prior art, according to individual information and cooperation information of terminals in different terminal capability sets, the proximity of the terminals and optimal terminals is calculated through TOPSIS (Technique for Order Preference by Similarity to an Ideal Solution) multi-attribute decision, a group of Pareto optimal Solution sets are obtained through calculation by adopting a multi-objective evolutionary algorithm, finally, the comprehensive expression of each optimal Solution in the optimal Solution sets is determined according to the requirements on the individual expression and the cooperative expression of the terminals, and the terminals are selected to form a polymerization terminal group according to the optimal Solution with the maximum comprehensive expression. The invention fully considers the individual capability and the cooperative capability of the terminal, so that the overall efficiency of the finally formed aggregation terminal group is optimal, and the problem of terminal aggregation can be effectively supported; in addition, the invention also automatically determines the weight of the multi-index parameters, can reduce the burden of the user and has better universality.

The problem of multi-service-oriented terminal aggregation is to integrate a network context and a service context, and select a set of terminals executing services for each user to form a Capable Piconet (CP). In the process of solving the terminal aggregation problem, two major challenges are mainly faced: the method has the advantages that firstly, the resource is limited, shared resources on terminal equipment and shared bandwidth on a communication link are limited in ubiquitous environments, and the demands of different ubiquitous services on the resources and the bandwidth are different at different quality levels; secondly, the terminal attribute problems, such as service distance, response delay, reliability, etc., are also important factors affecting the service quality. Therefore, multi-service terminal aggregation must take into account the dual constraints of resources and terminals.

Therefore, establishing a terminal aggregation mechanism for balancing multi-user benefits has great significance for ubiquitous peripheral environments. In the current ubiquitous peripheral environment, distributed ubiquitous services need aggregation of multiple terminals to be completed, and network resources and terminal capabilities are limited, so that it is difficult to balance quality benefits of multiple users executing request services at the same time, that is, balance is poor.

Disclosure of Invention

Technical problem to be solved

Aiming at the defects, the technical problem to be solved by the invention is to solve the problem of reducing user difference as much as possible on the premise of maximizing resources when multi-user terminal aggregation is carried out on ubiquitous services of a peripheral environment, namely to ensure the equilibrium of multi-terminal aggregation.

(II) technical scheme

In order to solve the above problems, the present invention provides a method for balancing multi-service terminal aggregation, which specifically comprises the following steps:

s1: performing dimensionality reduction processing on the terminal aggregation model for the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model;

s2: solving the MMKP model by adopting a terminal aggregation algorithm based on balance to obtain a vector solution with the highest total benefit of the balance service as an optimal solution of the MMKP model, wherein the solving process specifically comprises the following steps:

s21: the priority of all the ubiquitous services in the waiting state is preset, and the number of the ubiquitous services in the same priority is more than or equal to 1;

s22: sequencing the ubiquitous services in the waiting state according to the priorities, defining the highest priority as a first priority, and adding the ubiquitous services with the first priority into a processing queue;

s23: applying an algorithm with a heuristic search idea to the ubiquitous services with the same first priority for upgrading twice, and obtaining an optimal aggregation scheme when the ubiquitous services with the first priority are subjected to terminal aggregation, wherein the optimal aggregation scheme obtains the maximum total benefit of balanced services;

s24: judging whether the optimal aggregation scheme has an optimal solution, if so, entering a step S25, otherwise, deleting the ubiquitous service belonging to the first priority from the processing list, increasing the priority of other ubiquitous services lower than the first priority, adding the ubiquitous services into a processing queue as the first priority, and returning to the step S23;

s25: and converting the ubiquitous service from a waiting state to a ready state, allocating resources and bandwidth for the ubiquitous service, and adding the ubiquitous service in the ready state to an execution queue.

Further, the step S23 specifically includes:

s231: performing data preprocessing on the ubiquitous service with the first priority in the processing queue;

s232: searching an initial feasible solution from a candidate piconet, wherein the candidate piconet needs to simultaneously meet the constraint conditions of terminal resources and link bandwidth;

s233: judging whether the initial feasible solution exists, if so, entering a step S234, otherwise, failing to search the optimal aggregation scheme;

s234: carrying out forward upgrading on the initial feasible solution to obtain a primary solution vector;

s235: carrying out reverse upgrading on the primary solution vector to obtain a secondary solution vector;

s236: and judging the secondary solution vector, if a solution superior to the primary solution vector cannot be found, taking the primary solution vector as an optimal solution, wherein the total benefit of the equalization service of the optimal solution is the maximum, otherwise, jumping back to the step S234.

Further, the step S232 of finding the initial feasible solution specifically includes:

s2321: selecting the subscript of a candidate piconet with the minimum service quality benefit as an initial solution of the ubiquitous service for each ubiquitous service;

s2322: judging whether the initial solution meets constraint conditions of terminal resources and link bandwidth, wherein the constraint conditions are as follows:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,the value range of (1), (2), (…), (K = m · T + E) is the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, and E is the total number of communication links, if the initial solution is satisfied, the initial solution is feasible, and the process proceeds to step S233, otherwise, the process proceeds to step 2323;

s2323: selecting a candidate piconet with the largest amount of saved aggregated resources from all candidate piconets of the ubiquitous service, replacing the initial solution with the subscript of the candidate piconet with the largest amount of saved aggregated resources if a replacement principle is satisfied, and otherwise, not processing, wherein the amount of saved aggregated resources is savedWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

Further, the step S234 of forward upgrading includes:

s2341: under the condition of meeting the resource constraint condition, searching a candidate piconet for each ubiquitous service, wherein the total benefit of the balance service is higher than that of the balance service of the initial feasible solution, if the aggregated resource saving amount is found to be higher than the current maximum value, using the subscript of the candidate piconet as a better solution, and replacing the initial feasible solution with the better solution, otherwise, entering a step S2342;

s2342: judging whether the total benefit increment of the equalization service on the unit aggregation resource saving amount is higher than that of the initial feasible solution or not in the candidate piconet, if so, taking the subscript of the candidate piconet as a better solution, and replacing the initial feasible solution by the better solution, wherein the total benefit increment of the equalization service on the unit aggregation resource saving amount is delta U_i,j/Δa_i,jWherein Δ U_i,j=U_i,X[i]-U_i,j。

Further, the reverse upgrade process is accompanied by at least one degradation process, specifically:

s2351: under the condition of ignoring resource constraint, searching the piconet with the largest increment of the total benefits of the equalization service on the unit extra aggregation resource in the candidate piconets, and finding an upgrade replacement if the piconet exists, wherein the increment of the total benefits of the equalization service on the unit extra aggregation resource is delta U_i,j/Δa_i′_,jWherein ${\mathrm{\Δa}}_{i,j}^{\′}={\mathrm{\Σ}}_{\tilde{k}}({\tilde{r}}_{X\left[i\right],\tilde{k}}^i-{\tilde{r}}_{j,\tilde{k}}^i)/({\tilde{R}}_{\tilde{k}}-C_{\tilde{k}});$

S2352: searching for the piconet with the smallest increment of the total benefit of the equalization service on the unit of extra aggregation resource in the candidate piconets, wherein the total benefit of the equalization is higher than that before reverse upgrading, and if the total benefit of the equalization service exists, finding a degradation replacement;

s2353: and judging whether the solution after degradation replacement found in the step S2352 is feasible, if so, replacing the better solution with a better solution, taking the better solution as the initial feasible solution, returning to the step S234, if not, returning to the step S2352 for degradation again, and if not, taking the solution finally obtained in the step S234 as the optimal solution.

In order to solve the above problem, the present invention further provides a system for balancing multi-service terminal aggregation, including: the system comprises a model construction module and a model solving module, wherein the model construction module is used for carrying out dimensionality reduction processing on a terminal aggregation MODC model facing the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model, and the model solving module adopts a terminal aggregation algorithm based on balance to solve the MMKP model to obtain a vector solution with the highest total benefit of the balance service as an optimal solution of the MMKP model;

the model solving module specifically comprises: the system comprises a priority module, a priority sequencing module, an optimal aggregation scheme solving module, a priority promoting module and a state conversion module;

the priority module is used for presetting the priorities of all the ubiquitous services in a waiting state, and the number of the ubiquitous services in the same priority is more than or equal to 1;

the priority ordering module is used for ordering the ubiquitous services in the waiting state according to the priorities, defining the highest priority as a first priority and adding the ubiquitous services with the first priority into a processing queue;

the optimal aggregation scheme solving module is used for carrying out two-time upgrading on the ubiquitous services with the same first priority by applying an algorithm with a heuristic search idea, so as to obtain an optimal aggregation scheme when the ubiquitous services with the first priority are subjected to terminal aggregation, wherein the optimal aggregation scheme obtains the maximum total benefit of balanced services;

the priority promotion module is used for judging whether the optimal aggregation scheme has an optimal solution or not, if so, entering a state conversion module, otherwise, deleting the ubiquitous service belonging to the first priority from the processing list, promoting the priorities of other ubiquitous services lower than the first priority, adding the ubiquitous services as the first priority into a processing queue, and returning to the optimal aggregation scheme solving module;

the state conversion module is used for converting the ubiquitous service from a waiting state to a ready state, distributing resources and bandwidth for the ubiquitous service, and adding the ubiquitous service in the ready state to an execution queue.

Further, the optimal aggregation scheme solving module specifically includes: the system comprises a preprocessing module, an initial feasible solution module, a scheme determining module, a forward upgrading module, a reverse upgrading module and a first judging module;

the preprocessing module is used for preprocessing the data of the ubiquitous service with the first priority in the processing queue;

the initial feasible solution module is used for searching an initial feasible solution from candidate piconets, and the candidate piconets need to simultaneously meet constraint conditions of terminal resources and link bandwidth;

the scheme determining module is used for judging whether the initial feasible solution exists or not, if so, entering the forward upgrading module, otherwise, failing to search the optimal aggregation scheme;

the forward upgrading module is used for performing forward upgrading on the initial feasible solution to obtain a primary solution vector;

the reverse upgrading module is used for performing reverse upgrading on the primary solution vector to obtain a secondary solution vector;

the first judgment module is used for judging the secondary solution vector, if a solution superior to the primary solution vector cannot be found, the primary solution vector is used as an optimal solution, the total benefit of the balance service of the optimal solution is maximum, and otherwise, the forward upgrading module is jumped back.

Further, the initial feasible solution module comprises: the system comprises an initial solution selection module, a constraint judgment module and a first replacement module;

the initial solution selection module is used for selecting the subscript of the candidate piconet with the minimum service quality benefit as the initial solution of the ubiquitous service for each ubiquitous service;

the constraint judging module is used for judging whether the initial solution meets constraint conditions of terminal resources and link bandwidth, wherein the constraint conditions are as follows:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,the value range of (a) is 1,2, …, K = m · T + E is the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, E is the total number of communication links, if satisfied, the initial solution is feasible, the initial solution is taken as the initial feasible solution, and the scheme determination module is entered, otherwise, the first replacement module is entered;

the first replacement module is used for selecting a candidate piconet with the largest amount of saved aggregated resources from all candidate piconets of the ubiquitous service, replacing the initial solution with the subscript of the candidate piconet with the largest amount of saved aggregated resources if a replacement principle is met, and otherwise, not processing, wherein the amount of saved aggregated resources is savedWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

Further, the forward upgrade module comprises: a better solution searching module and a better solution judging module;

the better solution searching module is used for searching a candidate piconet for which the total balance service benefit is higher than that of the initial feasible solution for each ubiquitous service under the condition of meeting the resource constraint condition, if the aggregated resource saving amount is found to be higher than the current maximum value, the subscript of the candidate piconet is used as a better solution, the initial feasible solution is replaced by the better solution, and if the aggregated resource saving amount is not higher than the current maximum value, the better solution judging module is entered;

the preferred solution judging moduleThe block is configured to determine whether there is an increased total benefit of the equalization service per unit of the savings in the aggregated resources in the candidate piconet that is higher than the initial feasible solution, if so, take the subscript of the candidate piconet as a better solution, and replace the initial feasible solution with the better solution, wherein the increased total benefit of the equalization service per unit of the savings in the aggregated resources is au_i,j/Δa_i,jWherein Δ U_i,j=U_i,X[i]-U_i,j。

Further, the reverse upgrade module specifically includes: the second replacement module, the more optimal solution searching module and the more optimal solution confirming module;

the second replacement module is used for searching the piconet with the largest total benefit increment of the balanced service on the unit extra aggregation resource in the candidate piconets under the condition of ignoring the resource constraint, and finding an upgrade replacement if the piconet exists, wherein the total benefit increment of the balanced service on the unit extra aggregation resource is delta U_i,j/Δa_i′_,jWherein

The more optimal solution searching module is used for searching the piconet with the smallest increment of the total benefit of the equalization service on the unit extra aggregation resource in the candidate piconets, and the total benefit of the equalization is higher than that before reverse upgrading, if the total benefit of the equalization service exists, a degradation replacement is found;

the better solution confirmation module is used for judging whether the solution after degradation replacement found by the better solution searching module is feasible, if the solution is feasible, replacing is carried out, the better solution is used for replacing the better solution to be used as the initial feasible solution, the solution enters the forward upgrading module, if the solution is not feasible, the solution enters the better solution searching module to be degraded again, and if the solution which meets the conditions cannot be found, the solution finally obtained by the forward upgrading module is used as the optimal solution.

(III) advantageous effects

The invention provides a method and a system for balancing multi-service terminal aggregation. In the MMKP model solving process after dimension reduction, different services are firstly distinguished through priority, and the ubiquitous services with the same priority are upgraded twice by combining a heuristic search idea, so that the defects that the optimal solution obtained through one-time upgrading is limited and the difference of service quality and benefit among users cannot be solved are overcome. And selecting an optimal terminal aggregation scheme through heuristic search, wherein the optimal aggregation scheme can integrate double constraints of resources and bandwidth, and an optimal solution is solved for the optimal aggregation scheme to obtain a scheme with the maximum total benefit of the balanced service. The invention solves the problem of large difference among users generated in multi-terminal aggregation and ensures the balance in multi-terminal aggregation.

Drawings

Fig. 1 is a flowchart illustrating steps of a method for balancing multi-service terminal aggregation according to the present invention;

FIG. 2 is a flowchart illustrating a specific step of step S2 according to the present invention;

FIG. 3 is a flowchart of the ET-HEU algorithm of step S23 according to the present invention;

FIG. 4 is a topology diagram of 10 terminals in a preferred embodiment of the present invention;

FIG. 5 is a diagram of the ubiquitous service S under the 2 nd priority in the preferred embodiment of the present invention¹、S²、S³A schematic diagram of the relationship between the related information and the terminal information;

fig. 6 is a schematic composition diagram of a system for balancing multi-service terminal aggregation according to the present invention.

Detailed Description

The following detailed description of embodiments of the present invention is provided in connection with the accompanying drawings and examples. The following examples are intended to illustrate the invention but are not intended to limit the scope of the invention.

The embodiment of the invention provides a method for balancing multi-service terminal aggregation, and the specific flow is shown in figure 1, and the method comprises the following steps:

step S1: and performing dimensionality reduction processing on the terminal aggregation model for the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model.

For solving the problem of terminal aggregation of ubiquitous services, a mathematical model needs to be constructed, and the problem of terminal aggregation oriented to multiple services is to select the UG (S) capable of supporting the UG (D, L) from the UG (D, L) for n ubiquitous services requested simultaneouslyⁱ,Aⁱ) The problem of the optimal subgraph of (1) is to firstly define a ubiquitous service model and a ubiquitous network model.

(1) Ubiquitous business model (USM): each ubiquitous service i (i =1, …, n) uses an undirected graph UG (S)ⁱ,Aⁱ) Representation, including system service setsAnd service interaction setWherein,refers to the v-th system service in service i,refers to the e-th interaction among system services. Corresponding system serviceThe resource demand vector at quality level q isSystem service interactionThe bandwidth requirement at quality level q is

(2) Ubiquitous Network Model (UNM): similar to the ubiquitous service model, the ubiquitous peripheral network is represented by an undirected graph UG (D, L) containing a terminal set D = { D = { D }_tT =1,. T } and the set of communication links L = { L = |_sI s = 1. Wherein d is_tThe terminal refers to the t terminal in the network; l_sAnd indicating the s-th communication link between the terminals. Corresponding terminal d_tHas a maximum resource vector ofCommunication link l_sThe maximum bandwidth of is B_s。

For a single ubiquitous service i, one piconet CP needs to satisfy two criteria: at a specific quality level q, performing system service on the selected systemTerminal d of_tAnd performing system business interactionsThe available resources on the terminal and the available bandwidth on the link meet the requirements:

$\left\{\begin{array}{c}{r}_v^{i,q}\≤R^t\\ b_e^{i,q}\≤\min \left\{B_s\right|{\∀l}_s\∈L\}\end{array}\right.$ formula (1)

Where the first line of equation (1) is a constraint on resources and the second line is a constraint on bandwidth.

In a ubiquitous peripheral environment, when a CP is selected to execute a service i, a user quality of service benefit can be calculated by the following equation:

$u_c^{i,q}={\mathrm{\α}}_i\·\frac{q}{q_i}+(1-{\mathrm{\α}}_i)\·{\mathrm{\Σ}}_{f=1}^{\mathrm{\β}}{w}_f^i{\mathrm{\θ}}_{c,f}^i$ formula (2)

Where q denotes the quality level of the piconet CP, q_iIndicating the quality grade number, β is the number of terminal QoS factors, andweight and normalized benefit value of f-th QoS factor α_i(0≤α_i≦ 1) is a weight for the quality level benefit, the user may personalize α_iThe setting is performed.

For n ubiquitous services, the service quality benefits under a certain aggregation scheme are respectively assumed to beThe overall quality of service benefit isHowever, the overall efficiency of the system is only reflected, and the balance among internal users cannot be reflected. In order to balance the benefits of each user, the embodiment of the invention adopts the relative entropy as an index for quantitatively describing the equilibrium.

The processed data has a probability between 0 and 1, which is known from the principle of information entropy. Therefore, the multi-service benefits need to be normalized first, so that the entropy can be calculated. Order toObtaining a normalized quality of service benefit (p)₁,ρ₂,...ρ_n) Then, the normalized system entropy is as follows:

$S=-{\mathrm{\Σ}}_{i=1}^n({\mathrm{\ρ}}_1,{\mathrm{\ρ}}_2,\·\·\·{\mathrm{\ρ}}_n)$ formula (3)

From the extreme property of the entropy, when the values are completely equal, the entropy takes the maximum valueThen the relative benefit entropy is defined:

S_u=(S_max-S)/S_maxformula (4)

Using relative benefit entropy S_u(S_u∈[0,1]) Correcting the comprehensive service quality benefit, and defining a balance service quality benefit (balance service total benefit for short) function:

$U_e=(1-{\mathrm{\λS}}_u){\mathrm{\Σ}}_{i=1}^n{u}_c^{i,q}$ formula (5)

Therefore, the following steps are carried out: s_uThe smaller the result is, the closer the benefit value of each service is, and the more balanced the result is; at the same time, S_uThe smaller the size and the combined effectThe larger the value after the multiplication of the benefits, the better the system benefits. Therefore, it is reasonable to use the relative entropy as an index of quantization equalization. Wherein λ is a balance index coefficient (λ S)_u∈[0,1]). The larger the λ, the more important the equality; λ =0, the equalization problem is not considered.

Under the constraint of resources and bandwidth, the total benefit of the balanced service is taken as an objective function (c)^i,qThe number of CPs capable of executing the service i at the quality level q), and a multi-service-oriented terminal aggregation MODC model is abstracted as follows:

$\mathrm{Max}(1-{\mathrm{\λS}}_u){\mathrm{\Σ}}_{i=1}^n{\mathrm{\Σ}}_{q=1}^{q_i}{\mathrm{\Σ}}_{c=1}^{c^i,q}{u}_c^{i,q}\·x_c^{i,q}$

$\left\{\begin{array}{c}{\mathrm{\Σ}}_{i=1}^n{\mathrm{\Σ}}_{q=1}^{q_i}{\mathrm{\Σ}}_{c=1}^{c^{i,q}}{\mathrm{\Σ}}_{v=1}^{v_i}{r}_{v,k}^{i,q}\·y_c^{i,q}(v,t)\≤R_k^t,\∀t,k\\ {\mathrm{\Σ}}_{i=1}^n{\mathrm{\Σ}}_{q=1}^{q_i}{\mathrm{\Σ}}_{c=1}^{c^{i,q}}{{\mathrm{\Σ}}_{\mathrm{\θ}=1}^{{\mathrm{\θ}}_i}b}_e^{i,q}\·z_c^{i,q}(e,s)\≤B_s,\∀s\\ {\mathrm{\Σ}}_{q=1}^{q_i}{\mathrm{\Σ}}_{c=1}^{c^{i,q}}{x}_c^{i,q}=1\end{array}\right.$ formula (6)

Wherein S_uFor relative benefit entropy, λ is the equilibrium index coefficient, the magnitude of the λ value represents the importance of equilibrium, λ S_u∈[0,1]N is the number of ubiquitous services, q is the quality level of the ubiquitous services_iNumber of quality classes for the ith ubiquitous service, c^i,qThe number of piconets that can perform the ith ubiquitous service for quality level q,in order to achieve the benefits of the quality of service,is the maximum resource of the t-th terminal,for corresponding system serviceAt the resource requirement of the quality level q,for the vth system service in service i,interacting for system servicesAt the bandwidth requirement of the quality level q,for the e-th interaction between system services,

as can be seen from the formula of the MODC model, the problem is a multi-dimensional linear integer programming problem, is an NP-hard (No-deterministic Polynomial) non-deterministic Polynomial problem, and has high computational complexity.

The terminal aggregation mechanism for balancing Multiple services provided in the embodiment of the present invention performs dimension reduction processing on an MODC model, and simplifies the MODC model into a familiar MMKP (Multiple-dimensional and Multiple-choice of knapack distribution, multi-dimensional multi-choice Knapsack Problem) model, where the dimension reduction processing is as follows:

and for the ubiquitous service i, combining the CPs under all quality levels into a one-dimensional candidate piconet. Thus, the number of candidate piconets isSimilarly, the resource and bandwidth limitations are combined into a one-dimensional constraint, the total number of constraints being by K = m · T + E.

For candidate piconets p (p =1, 2.. c.) in the merged new sequence_i) If, if $p={\mathrm{\Σ}}_{i=1}^{q-1}{c}^{i,q}+c(0\≤c\≤c^{i,q}),$ There is a change in the following parameters:

① entropy of relative benefit

② quality of service benefits

③ ubiquitous service demands

Formula (7)

WhereinInteracting for system servicesAt the bandwidth requirement of the quality level q,is the e-th interaction among system services.

The resulting resource and bandwidth constraints are:

formula (8)

WhereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,is 1,2, …, K = m · T + E as the total number of constraints, m as the number of resource types on the terminal, T as the number of terminals, E as the total number of communication links.

The obtained MMKP model after dimensionality reduction is as follows:

$\mathrm{Max}(1-\mathrm{\λ}{\tilde{S}}_u){\mathrm{\Σ}}_{i=1}^n{\mathrm{\Σ}}_{p=1}^{c_i}{\tilde{u}}_p^i\·{\tilde{x}}_p^i$

$s.t.\left\{\begin{array}{c}{\mathrm{\Σ}}_{i=1}^n{\mathrm{\Σ}}_{p=1}^{c_i}{\tilde{r}}_{p,k}^i{\tilde{x}}_p^i\≤{\tilde{R}}_{\tilde{k}},\∀\tilde{k}\\ {\mathrm{\Σ}}_{p=1}^{c_i}{\tilde{x}}_p^i=1,\∀i\end{array}\right.,$ formula (9)

WhereinFor the relative benefit entropy after dimensionality reduction, n is the number of ubiquitous services, c_iAs to the number of candidate piconets,p is a candidate piconet, and p = (1, 2.., c)_i)，c^i,qFor the number of piconets with quality level q capable of performing the ith ubiquitous service,in order to achieve the benefits of the quality of service,are resource and bandwidth constraints.

And then solving by adopting a balanced terminal aggregation EDC algorithm taking a heuristic algorithm as a core.

Step S2: and solving the MMKP model by adopting a terminal aggregation algorithm based on balance to obtain a vector solution with the highest total benefit of the balance service as the optimal solution of the MMKP model.

In the process of studying MMKP models, ubiquitous services generally have 3 states: wait, ready and execute, the difference being: the service in the waiting state is not allocated with resources and bandwidth, the service in the ready state is allocated with corresponding resources and bandwidth and is to be executed, and the service in the executing state occupies the resources and bandwidth.

In a ubiquitous peripheral environment, the limitation of network resources and terminal capabilities may cause a competition problem when multiple users request. This necessarily results in some of the ubiquitous traffic being executed first and some later. The EDC algorithm assigns each ubiquitous Service a Priority (Pr for short) according to a Service Layer Agreement (SLA), and preferentially executes the ubiquitous Service with a higher Priority when contention occurs, so as to implement differentiated services of different levels of services. Meanwhile, in order to avoid the embarrassing situation that the service with high priority is continuously requested and the service with low priority cannot be executed, the algorithm can immediately improve the priority of the original service with low priority after the service with high priority is executed. For ubiquitous services with the same priority, a Heuristic algorithm is adopted to select the aggregation scheme with the maximum Total benefit of the balanced service, wherein the used algorithm is an ET-HEU (equal-Total-reliability) algorithm, the ET-HEU algorithm is the core of an EDC algorithm, and the Heuristic algorithm is a Heuristic algorithm. The concept of aggregated Resources (Aggregate Resources) is also used in the algorithm. The core idea of the ET-HEU algorithm is as follows: the MMKP problem is preprocessed, an initial solution is found according to heuristic information, and a better feasible solution is obtained through a series of upgrading and degrading. Upgrading refers to increasing the total benefit of the balance service of the solution of the scheme by one replacement, and degrading refers to increasing the total benefit of the balance service of the solution of the scheme by one replacementAnd (4) reducing. Wherein, the scheme solves X = (X)₁,x₂…) is a one-dimensional vector formed by the chosen index of the piconet CP performing the ubiquitous service. A flow chart of the MMKP solution process is shown in fig. 2, comprising the following steps:

step S21: firstly, newly arrived ubiquitous services are put into a waiting state, and then the priorities of all the ubiquitous services in the waiting state are preset, wherein the number of the ubiquitous services in the same priority is more than or equal to 1.

Step S22: and sequencing the ubiquitous services in the waiting state according to the priorities, defining the highest priority as a first priority, and adding the ubiquitous services with the first priority into a processing queue. The ubiquitous services with equal priority belong to the same batch, and are also added into the processing queue in the same batch, and the number of the ubiquitous services with the same priority can be one or more.

Step S23: and upgrading the ubiquitous services with the same first priority twice by applying an algorithm with a heuristic search idea, and obtaining an optimal aggregation scheme when the ubiquitous services with the first priority are subjected to terminal aggregation, wherein the optimal aggregation scheme has the maximum total benefit of the balanced service.

Step S24: and judging whether the optimal aggregation scheme has an optimal solution, if so, entering the step S25, otherwise, deleting the ubiquitous service belonging to the first priority from the processing list, increasing the priority of other ubiquitous services lower than the first priority, adding the ubiquitous services into the processing queue as the first priority, and returning to the step S23.

Step S25: and converting the state of the ubiquitous service into a ready state, allocating resources and bandwidth for the ubiquitous service, and adding the ubiquitous service in the ready state to an execution queue. Wherein before adding the ubiquitous traffic in the ready state to the execution queue, further comprising: and judging whether the ubiquitous service in the waiting state is batched, if so, adding the next batched batch into the processing queue as a first priority, and otherwise, directly adding the ubiquitous service in the ready state into the execution queue.

The ET-HEU algorithm flow in step S23 is shown in fig. 3, and specifically includes the following steps:

step S231: and performing data preprocessing on the ubiquitous service in the processing queue.

The data preprocessing specifically comprises the following steps:

step S2311: and selecting all candidate piconets for each ubiquitous service according to the current service requirement and the network state to form a candidate piconet set.

Step S2312: and calculating the service quality benefit of each candidate piconet, and performing non-descending ordering on all candidate piconets of each ubiquitous service according to the service quality benefit.

The service quality benefits of the candidate CPs are obtained by calculation according to a formula (2), and are ranked according to the service quality benefits of the candidate CPs in each ubiquitous service, wherein the non-decreasing sequence is equal to be in the same level, and the non-equal sequence is arranged according to the increasing sequence.

Step S232: an initial feasible solution is found from candidate piconets that need to satisfy both the constraints of terminal resources and link bandwidth.

Specifically, the searching for the initial feasible solution includes:

step S2321: the index of the candidate piconet with the least quality of service benefit is selected for each ubiquitous service as the initial solution for the ubiquitous service. Since the candidate CPs under each ubiquitous service have been arranged in a non-decreasing order in the above steps, the 1 st candidate CP is the smallest in quality of service benefit, so the 1 st candidate CP is selected for all the ubiquitous services, and the smallest in quality of service benefit is taken as the initial solution.

Step S2322: judging whether the initial solution meets the constraint conditions of terminal resources and link bandwidth, wherein the constraint conditions are as follows:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,the value range of (1), (2), (…), (K = m · T + E) is the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, and E is the total number of communication links, if the value range of (m = m · T + E) is satisfied, the initial solution is feasible, the initial solution is taken as the initial feasible solution, and step S233 is entered, otherwise, step S2323 is entered.

Step S2323: selecting a candidate piconet with the largest amount of accumulated resource saving from all candidate piconets of the ubiquitous service, replacing the initial solution with the subscript of the candidate piconet with the largest amount of accumulated resource saving if a replacement principle is met, and otherwise, not processing, wherein the amount of accumulated resource saving isWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

Wherein the replacement principle and the requirement for the violated factor after replacement need to satisfy the following conditions:

reducing the maximum violation factor after replacement;

the violation factor is not increased after the resource which violates the maximum constraint is replaced;

and the resource which does not violate the maximum constraint still does not violate the maximum constraint after the replacement.

Wherein the violation factor is calculated by

Step S233: and judging whether the initial feasible solution exists, if so, entering the step S234, otherwise, failing to search the optimal aggregation scheme.

Step S234: and carrying out forward upgrading on the initial feasible solution to obtain a primary solution vector.

Wherein the forward upgrade comprises:

step S2341: and under the condition of meeting the resource constraint condition, searching a candidate piconet for each ubiquitous service, wherein the total benefit of the equalization service is higher than that of the initial feasible solution, if the aggregated resource saving amount is found and is higher than the current maximum value, using the subscript of the candidate piconet as a better solution and replacing the initial feasible solution with the better solution, and otherwise, entering the step S2342.

Step S2342: judging whether the total benefit increment of the equalization service on the unit aggregation resource saving amount in the candidate piconets is higher than the initial feasible solution or not, if so, taking the subscript of the candidate piconets as a better solution, and replacing the initial feasible solution with the better solution, wherein the total benefit increment of the equalization service on the unit aggregation resource saving amount is delta U_i,j/Δa_i,jWherein Δ U_i,j=U_i,X[i]-U_i,j。

Step S235: and carrying out reverse upgrading on the primary solution vector to obtain a secondary solution vector.

Wherein, in the reverse upgrading process, at least one time of degradation processing is accompanied, specifically:

s2351: searching the micro with maximum increment of the total benefit of the balanced service on the unit extra aggregation resource in the candidate piconet under the condition of ignoring resource constraintMicrogrid, if it exists, finding an upgrade replacement, in which the increment of the total benefit of the equalization service on the unit of additional aggregated resources is DeltaU_i,j/Δa′_i,jWherein ${\mathrm{\Δa}}_{i,j}^{\′}={\mathrm{\Σ}}_{\tilde{k}}({\tilde{r}}_{X\left[i\right],\tilde{k}}^i-{\tilde{r}}_{j,\tilde{k}}^i)/({\tilde{R}}_{\tilde{k}}-C_{\tilde{k}}).$

S2352: and searching the piconet with the smallest increment of the total benefit of the equalization service on the unit extra aggregation resource in the candidate piconets, and finding a degradation replacement if the total benefit of the equalization service exists before reverse upgrading.

S2353: and judging whether the solution after degradation replacement found in the step S2352 is feasible, if so, replacing the better solution with a more optimal solution, taking the more optimal solution as an initial feasible solution, returning to the step S234, if not, returning to the step S2352 for degradation again, and if not, taking the solution finally obtained in the step S234 as an optimal solution.

Step S236: and judging the secondary solution vector, and if a solution superior to the primary solution vector cannot be found, taking the primary solution vector as an optimal solution, otherwise, returning to the step S234.

The obtained balance service of the optimal solution has the maximum total benefit, the benefits of each user can be balanced, the problem that the service benefits of different users are different is solved, and the balance during multi-terminal aggregation is ensured.

A preferred solution of the embodiment of the present invention is given below, 10 user terminals exist in a 100m × 150m ubiquitous network, a topological diagram is shown in fig. 4, 3 resources can be provided for each terminal, and 5 users initiate ubiquitous service requests at the same time and are respectively S¹、S²、S³、S⁴、S⁵。

First, step S21 is executed to determine S¹、S²、S³Has a priority of 2, S⁴、S⁵Has a priority of 1. Then, step S22 is executed to determine S according to the priority¹、S²、S³Divided into first batch, S⁴、S⁵Grouping as a second batch while adding S¹、S²、S³Adding the processing queue, solving the aggregation scheme by using an ET-HEU algorithm, namely step S23, and judging whether a feasible solution exists, namely step S24: if so, executing step S25 will implement the ubiquitous service S¹、S²、S³Turning to the ready state, and checking whether there is another batch, step S26; if not, then S is added¹、S²、S³Remove from the processing queue while raising S⁴、S⁵Has a priority of 2. Step S26 is performed because of the presence of a batch S⁴、S⁵Therefore, steps S22-S26 are executed again, and all requests are requestedAfter the transaction is completed, step 27 is executed to add the ubiquitous transaction in the ready state to the execution queue.

With S at priority 2¹、S²、S³The flow of the ET-HEU algorithm provided by the present invention is described for example, and its related service information and terminal information are shown in table 1 and fig. 5.

TABLE 1

Step S231: firstly, preprocessing data:

for ubiquitous service S¹、S²、S³All candidate CPs are selected, wherein only piconets with terminal resources and link bandwidth meeting the requirements can become the candidate CPs.

Calculating the user service quality benefit of the candidate CP according to the formula (2) Value of and QoS factor utilizationIn relation to, QoS factor utilization in calculationThe main considerations are: distance of service, response delay, validity, and reliability, among other parameters, to QoS factor utilizationThe influence is only small and is not considered here. Wherein the benefit function refers to the QoS factor utilization rate of a single terminalThe composition function is used to calculate the QoS factor utilization of multiple terminals, i.e., CPs

① distance of traffic, ratio of actual distance from terminal to user performing system traffic to optimal distance the benefit function is $D=\frac{d(d,\mathrm{\μ},\mathrm{\σ})}{d(\mathrm{\μ},\mathrm{\μ},\mathrm{\σ})},$ Wherein $d(d,\mathrm{\μ},\mathrm{\σ})=\frac{1}{\sqrt{2\mathrm{\π}}\mathrm{\σ}}\exp (-\frac{{(d-\mathrm{\μ})}^2}{{2\mathrm{\σ}}^2}),$ d is a terminal andthe actual distance between users, μ is the optimal distance and σ is the sensitivity. The synthesis function is ${\mathrm{\θ}}_d={\mathrm{\Σ}}_{v=1}^{v_i}{w}_D^{v}D,$ ${\mathrm{\Σ}}_{v=1}^{v_i}{w}_D^v=1.$

② response delay, average time interval between the user's sending of system service request and the receipt of response, the benefit function isWherein T is_rFor response time, T_maxThe longest latency. The synthesis function is ${\mathrm{\θ}}_t={\mathrm{\Σ}}_{v=1}^{v_i}{w}_T^{v}T,$ ${\mathrm{\Σ}}_{v=1}^{v_i}{w}_T^v=1.$

③ effectiveness-average length of time for a terminal to perform system traffic, the benefit function isWherein T is_aTo implement system service time, T_tTo monitor the total time, the synthesis function is ${\mathrm{\θ}}_a={\mathrm{\Π}}_{v=1}^{v_i}A.$

④ reliability the probability of a terminal successfully executing a system service, the benefit function isWherein N is_sFor the number of successfully responded requests, N is the total number of requests, the synthesis function is

Will be ubiquitous service S¹、S²、S³The candidate CPs are arranged according to the non-decreasing user QoS benefit, and the result after the arrangement is assumed to be S¹(CP₁ ¹,...,)、S²(CP₁ ²,...,)、S³(CP₁ ³,...,CP₅ ³)。

Step S232: an initial feasible solution is found.

(1) To S¹、S²、S³The 1 st candidate CP is selected, i.e., the initial solution is X = (1, 1, 1), respectively.

(2) If worse, the initial solution is not feasible.

(3) To S¹、S²、S³Is traversed, assuming that the CP is₅ ¹The maximum amount of resources saved by aggregation and satisfying the replacement principle, then replace X = (5, 1, 1); wherein the calculation formula of the saving amount of the aggregated resources isWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]Is the ith component of the initial solution, j is the index of the candidate piconet after replacement, and the formula for the violation factor is

Step S234: finding an initial feasible solution, X = (5, 1, 1), and performing forward upgrade on the initial feasible solution, which specifically includes the steps of:

traverse S¹、S²、S³In the bad condition, the feasible schemes with higher overall efficiency of the balanced service and larger resource-saving amount of aggregation cannot be found, but the schemes have the defects of higher overall efficiency of the balanced service and larger resource-saving amountBalanced service total benefit delta U over unit aggregated resource savings_i,j/Δa_i,jMaximum, wherein Δ U_i,j=U_i,X[i]-U_i,jThen, replacement is performed so that X = (5, 6, 1), and a better solution X = (5, 6, 1) is found.

Step S235: performing reverse upgrade on the solution vector obtained in the above step, wherein the reverse upgrade process includes at least one degradation, and specifically includes:

(1) neglecting the constraint condition, and setting the total benefit increment delta U of the balanced service on the unit extra aggregation resource_i,j/Δa′_i,jMaximum upgrade replacement X [3 ]]1 → 3, wherein ${\mathrm{\Δa}}_{i,j}^{\′}={\mathrm{\Σ}}_{\tilde{k}}({\tilde{r}}_{X\left[i\right],\tilde{k}}^i-{\tilde{r}}_{j,\tilde{k}}^i)/({\tilde{R}}_{\tilde{k}}-C_{\tilde{k}}),$ Let X' = (5, 6, 3).

(2) Suppose there is a degraded replacement X' [2]:6 → 5 with the minimum increment of the total benefit of the balanced service on the unit of extra aggregated resources at the same time, and the total benefit of the balanced service is higher than X. Let X "= (5, 5, 3).

(3) Assuming that X ″ satisfies the constraint, the replacement is performed such that X = (5, 5, 3), and the optimal solution X = (5, 5, 3) is found, and the algorithm ends.

In summary, the method for balancing multi-service terminal aggregation provided by the embodiment of the present invention performs the dimension reduction processing on the constructed terminal aggregation model first, combines the resource and bandwidth constraints into the one-dimensional constraint, and reduces the computation complexity. In the process of solving the MMKP model after dimension reduction, different services are firstly distinguished through priorities, then improvement is carried out based on a heuristic EDC algorithm, an initial solution is searched according to heuristic information, an optimal solution formed by one-dimensional vectors is finally obtained through upgrading and degrading replacement, and an optimal aggregation scheme with the maximum total benefit of balanced services is obtained. Furthermore, the invention establishes a multi-service-oriented terminal aggregation model and corrects the service quality benefit and the service quality benefit by combining the relative benefit entropy, so that the limited network resources and terminal capability in the peripheral environment are effectively utilized on one hand, and the user service requirements are met as much as possible without excessively great difference in service quality on the other hand. Aiming at the mathematical model of the invention, the multidimensional integer programming problem is reduced into the MMKP model, the complexity is reduced, the problem is easy to process, the differentiated service of different services is realized through the priority based on the balanced terminal aggregation algorithm, then the heuristic algorithm is adopted for the same service, the optimal aggregation scheme is continuously searched through a series of degradation and upgrade, and the heuristic information during the heuristic search is the maximum benefit of balanced service quality, so the system comprehensiveness and the internal balance of multi-user benefit are well considered.

Correspondingly, the invention also provides a system for balancing the aggregation of the multi-service terminals, which mainly comprises the following steps: a model building module 10 and a model solving module 20, as shown in fig. 6.

The model building module 10 is used for performing dimensionality reduction processing on the terminal aggregation model for the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model, and the model solving module 20 is used for solving the MMKP model by using a terminal aggregation algorithm based on balance to obtain a vector solution with the highest total benefit of the balanced service as an optimal solution of the MMKP model.

The model solving module 20 specifically includes: a priority module 21, a prioritization module 22, an optimal aggregation scheme solving module 23, a priority promotion module 24, and a state transition module 25.

The priority module 21 is configured to preset priorities of all the ubiquitous services in the waiting state, where the number of the ubiquitous services in the same priority is greater than or equal to 1.

The priority sorting module 22 is configured to sort the ubiquitous services in the waiting state according to the priorities, define the highest priority as a first priority, and add the ubiquitous services with the first priority into the processing queue.

The optimal aggregation scheme solving module 23 is configured to perform two upgrades on the ubiquitous services with the same first priority by applying an algorithm with a heuristic search idea, to obtain an optimal aggregation scheme when the ubiquitous services with the first priority perform terminal aggregation, where a total benefit of balanced services obtained by the optimal aggregation scheme is the largest.

The priority raising module 24 is configured to determine whether the optimal aggregation scheme has an optimal solution, if so, enter the state conversion module 25, otherwise, delete the ubiquitous service belonging to the first priority from the processing list, raise the priority of other ubiquitous services lower than the first priority, add the ubiquitous services as the first priority into the processing queue, and return to the optimal aggregation scheme solving module 23.

The state conversion module 25 is configured to convert the ubiquitous service from the waiting state to the ready state, allocate resources and bandwidth to the ubiquitous service, and add the ubiquitous service in the ready state to the execution queue.

Wherein before adding the ubiquitous traffic in the ready state to the execution queue, further comprising: and judging whether the ubiquitous service in the waiting state is batched, if so, adding the next batched batch into the processing queue as a first priority, and otherwise, directly adding the ubiquitous service in the ready state into the execution queue.

The most critical part of the model solving module 23 is the optimal aggregation scheme solving module 23, which specifically includes: a preprocessing module 231, an initial feasible solution module 232, a scheme determination module 233, a forward upgrade module 234, a reverse upgrade module 235, and a first judgment module 236.

The preprocessing module 231 is configured to perform data preprocessing on the ubiquitous traffic in the processing queue, the initial feasible solution module 232 is configured to search an initial feasible solution from candidate piconets, where the candidate piconets need to satisfy constraint conditions of terminal resources and link bandwidths, and the scheme determining module 233 is configured to determine whether the initial feasible solution exists, and if so, enter the forward upgrading module 234, otherwise, the best aggregation scheme fails to be searched.

The forward upgrading module 234 is configured to forward upgrade the initial feasible solution to obtain a first-level solution vector, the reverse upgrading module 235 is configured to reverse upgrade the first-level solution vector to obtain a second-level solution vector, the first determining module 236 is configured to determine the second-level solution vector, if a solution better than the first-level solution vector cannot be found, the first-level solution vector is used as an optimal solution, otherwise, the forward upgrading module is skipped.

Wherein the preprocessing module 231 includes: a candidate design module 2311 and a ranking module 2312. The candidate design module 2311 is configured to select all candidate piconets for each ubiquitous service according to the current service requirement and network status to form a candidate piconet set, where subscripts of each candidate piconet are identified by numbers, and the ranking module 2322 is configured to calculate a quality of service benefit of each candidate piconet and non-decrementally rank all candidate piconets of each ubiquitous service according to the magnitude of the quality of service benefit.

Wherein the initial feasible solution module 232 includes: an initial solution selection module 2321, a constraint determination module 2322 and a first replacement module 2323.

The initial solution selecting module 2321 is configured to select, for each ubiquitous service, a subscript of a candidate piconet with a minimum quality of service benefit as an initial solution of the ubiquitous service, and the constraint judging module 2322 is configured to judge whether the initial solution satisfies constraint conditions of terminal resources and link bandwidth, where the constraint conditions are:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,the value range of (1, 2, …, K = m · T + E is the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, and E is the total number of communication links, if the value range of (1, 2, …), the initial solution is feasible, the initial solution is taken as the initial feasible solution, and the scheme determination module 233 is entered, otherwise, the first replacement module 2323 is entered.

A first replacing module 2323 is configured to select a candidate piconet with the largest amount of saving of the aggregated resources from all candidate piconets of the ubiquitous service, replace the initial solution with the index of the candidate piconet with the largest amount of saving of the aggregated resources if a replacing rule is satisfied, and otherwise, do not process the solution, wherein the amount of saving of the aggregated resources is savedWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

The forward upgrade module 234 includes: the optimal solution searching module 2341 and the optimal solution determining module 2342, where the optimal solution searching module 2341 is configured to search, for each ubiquitous service, a candidate piconet whose total benefit of the balancing service is higher than that of the balancing service of the initial feasible solution under the condition that the resource constraint condition is met, if the aggregated resource saving amount is found and is higher than the current maximum value, the subscript of the candidate piconet is used as the optimal solution, and the initial feasible solution is replaced by the optimal solution, otherwise, the optimal solution determining module 2342 is entered.

The better solution determining module 2342 is configured to determine whether the total benefit increment of the balance service in the unit aggregation resource saving amount in the candidate piconet is higher than the initial feasible solution, if so, use the subscript of the candidate piconet as the better solution, and replace the initial feasible solution with the better solution, where the total benefit increment of the balance service in the unit aggregation resource saving amount is Δ U_i,j/Δa_i,jWherein Δ U_i,j=U_i,X[i]-U_i,j。

The reverse upgrade module 235 specifically includes: a second alternate module 2351, a better solution lookup module 2352 and a better solution validation module 2353.

The second replacement module 2351 is used for searching the piconet with the largest increment of the total benefits of the equalization service on the unit extra aggregation resource in the candidate piconets under the condition of ignoring the resource constraint, and finding an upgrade replacement if the piconet exists, wherein the increment of the total benefits of the equalization service on the unit extra aggregation resource is delta U_i,j/Δa′_i,jWherein ${\mathrm{\Δa}}_{i,j}^{\′}={\mathrm{\Σ}}_{\tilde{k}}({\tilde{r}}_{X\left[i\right],\tilde{k}}^i-{\tilde{r}}_{j,\tilde{k}}^i)/({\tilde{R}}_{\tilde{k}}-C_{\tilde{k}}).$

The better solution searching module 2352 is used for searching the piconet with the smallest increment of the total benefit of the equalization service on the unit extra aggregation resource in the candidate piconets, and the total benefit of the equalization is higher than that before the reverse upgrade, if the total benefit exists, a downgrade replacement is found.

The better solution confirming module 2353 is configured to determine whether the solution after degradation replacement found by the better solution searching module is feasible, if feasible, perform replacement, replace the better solution with the better solution, take the better solution as the initial feasible solution, and return to step S234, if infeasible, return to step S2352 to perform degradation again, and if no degradation meeting the condition is found, take the solution finally obtained in S234 as the optimal solution.

The system for balancing the multi-service terminal aggregation provided by the invention can also realize the beneficial effect of the method for balancing the multi-service terminal aggregation.

The above embodiments are only for illustrating the invention and are not to be construed as limiting the invention, and those skilled in the art can make various changes and modifications without departing from the spirit and scope of the invention, therefore, all equivalent technical solutions also belong to the scope of the invention, and the scope of the invention is defined by the claims.

Claims (6)

1. A method for balancing multi-service terminal aggregation is characterized in that the method specifically comprises the following steps:

s1: performing dimensionality reduction processing on the terminal aggregation model for the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model;

s2: solving the MMKP model by adopting a terminal aggregation algorithm based on balance to obtain a vector solution with the highest total benefit of the balance service as an optimal solution of the MMKP model, wherein the solving process specifically comprises the following steps:

s21: the priority of all the ubiquitous services in the waiting state is preset, and the number of the ubiquitous services in the same priority is more than or equal to 1;

s22: sequencing the ubiquitous services in the waiting state according to the priorities, defining the highest priority as a first priority, and adding the ubiquitous services with the first priority into a processing queue;

s23: applying an algorithm with a heuristic search idea to the ubiquitous services with the same first priority for upgrading twice, and obtaining an optimal aggregation scheme when the ubiquitous services with the first priority are subjected to terminal aggregation, wherein the optimal aggregation scheme obtains the maximum total benefit of balanced services;

s24: judging whether the optimal aggregation scheme has an optimal solution, if so, entering a step S25, otherwise, deleting the ubiquitous service belonging to the first priority from the processing list, increasing the priority of other ubiquitous services lower than the first priority, adding the ubiquitous services into a processing queue as the first priority, and returning to the step S23;

s25: converting the ubiquitous service from a waiting state to a ready state, allocating resources and bandwidth to the ubiquitous service, and adding the ubiquitous service in the ready state to an execution queue;

wherein, the step S23 specifically includes:

s231: performing data preprocessing on the ubiquitous service with the first priority in the processing queue;

s232: searching an initial feasible solution from a candidate piconet, wherein the candidate piconet needs to simultaneously meet the constraint conditions of terminal resources and link bandwidth;

s233: judging whether the initial feasible solution exists, if so, entering a step S234, otherwise, failing to search the optimal aggregation scheme;

s234: carrying out forward upgrading on the initial feasible solution to obtain a primary solution vector;

s235: carrying out reverse upgrading on the primary solution vector to obtain a secondary solution vector;

s236: judging the secondary solution vector, if a solution superior to the primary solution vector cannot be found, taking the primary solution vector as an optimal solution, wherein the total benefit of the equalization service of the optimal solution is the maximum, otherwise, jumping back to the step S234;

wherein, the step S232 of searching for the initial feasible solution specifically includes:

s2321: selecting the subscript of a candidate piconet with the minimum service quality benefit as an initial solution of the ubiquitous service for each ubiquitous service;

s2322: judging whether the initial solution meets constraint conditions of terminal resources and link bandwidth, wherein the constraint conditions are as follows:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,if the value range of (1, 2, …) is defined as m · T + E as the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, and E is the total number of communication links, if the value range of (K) is defined as m · T + E, the initial solution is feasible, the initial solution is taken as the initial feasible solution, and step S233 is entered, otherwise, step S2323 is entered;

s2323: selecting a candidate piconet with the largest amount of saved aggregated resources from all candidate piconets of the ubiquitous service, replacing the initial solution with the subscript of the candidate piconet with the largest amount of saved aggregated resources if a replacement principle is satisfied, and otherwise, not processing, wherein the amount of saved aggregated resources is savedWhere C is the actual resource consumption vector,for ubiquitous business demands, xi]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

2. The method of claim 1, wherein the step S234 forward upgrading comprises:

s2341: under the condition of meeting the resource constraint condition, searching a candidate piconet for each ubiquitous service, wherein the total benefit of the balance service is higher than that of the balance service of the initial feasible solution, if the resource saving amount is found and the aggregation resource saving amount is higher than the current maximum value, using the subscript of the candidate piconet as a better solution, and replacing the initial feasible solution with the better solution, otherwise, entering a step S2342;

s2342: judging whether the total benefit increment of the equalization service on the unit aggregation resource saving amount is higher than that of the initial feasible solution or not in the candidate piconet, if so, taking the subscript of the candidate piconet as a better solution, and replacing the initial feasible solution by the better solution, wherein the total benefit increment of the equalization service on the unit aggregation resource saving amount is delta U_i,j/Δa_i,jWherein Δ U_i,j＝U_i,X[i]-U_i,j。

3. The method according to claim 2, wherein the reverse upgrade process is accompanied by at least one downgrade process, specifically:

s2351: under the condition of ignoring resource constraint, searching the piconet with the largest increment of the total benefits of the equalization service on the unit extra aggregation resource in the candidate piconets, and finding an upgrade replacement if the piconet exists, wherein the increment of the total benefits of the equalization service on the unit extra aggregation resource is delta U_i,j/Δa′_i,jWherein

S2352: searching for the piconet with the smallest increment of the total benefit of the equalization service on the unit of extra aggregation resource in the candidate piconets, wherein the total benefit of the equalization is higher than that before reverse upgrading, and if the total benefit of the equalization service exists, finding a degradation replacement;

s2353: and judging whether the solution after degradation replacement found in the step S2352 is feasible, if so, replacing the better solution with a better solution, taking the better solution as the initial feasible solution, returning to the step S234, if not, returning to the step S2352 for degradation again, and if not, taking the solution finally obtained in the step S234 as the optimal solution.

4. A system for balancing multi-service terminal aggregation, the system comprising: the system comprises a model construction module and a model solving module, wherein the model construction module is used for carrying out dimensionality reduction processing on a terminal aggregation MODC model facing the multi-ubiquitous service to obtain a multi-dimensional multi-choice knapsack problem MMKP model, and the model solving module adopts a terminal aggregation algorithm based on balance to solve the MMKP model to obtain a vector solution with the highest total benefit of the balance service as an optimal solution of the MMKP model;

the model solving module specifically comprises: the system comprises a priority module, a priority sequencing module, an optimal aggregation scheme solving module, a priority promoting module and a state conversion module;

the priority module is used for presetting the priorities of all the ubiquitous services in a waiting state, and the number of the ubiquitous services in the same priority is more than or equal to 1;

the priority ordering module is used for ordering the ubiquitous services in the waiting state according to the priorities, defining the highest priority as a first priority and adding the ubiquitous services with the first priority into a processing queue;

the optimal aggregation scheme solving module is used for carrying out two-time upgrading on the ubiquitous services with the same first priority by applying an algorithm with a heuristic search idea, so as to obtain an optimal aggregation scheme when the ubiquitous services with the first priority are subjected to terminal aggregation, wherein the optimal aggregation scheme obtains the maximum total benefit of balanced services;

the priority promotion module is used for judging whether the optimal aggregation scheme has an optimal solution or not, if so, entering a state conversion module, otherwise, deleting the ubiquitous service belonging to the first priority from the processing list, promoting the priorities of other ubiquitous services lower than the first priority, adding the ubiquitous services as the first priority into a processing queue, and returning to the optimal aggregation scheme solving module;

the state conversion module is used for converting the ubiquitous service from a waiting state to a ready state, allocating resources and bandwidth to the ubiquitous service and adding the ubiquitous service in the ready state to an execution queue;

the optimal aggregation scheme solving module specifically comprises: the system comprises a preprocessing module, an initial feasible solution module, a scheme determining module, a forward upgrading module, a reverse upgrading module and a first judging module;

the preprocessing module is used for preprocessing the data of the ubiquitous service with the first priority in the processing queue;

the initial feasible solution module is used for searching an initial feasible solution from candidate piconets, and the candidate piconets need to simultaneously meet constraint conditions of terminal resources and link bandwidth;

the scheme determining module is used for judging whether the initial feasible solution exists or not, if so, entering the forward upgrading module, otherwise, failing to search the optimal aggregation scheme;

the forward upgrading module is used for performing forward upgrading on the initial feasible solution to obtain a primary solution vector;

the reverse upgrading module is used for performing reverse upgrading on the primary solution vector to obtain a secondary solution vector;

the first judgment module is used for judging the secondary solution vector, if a solution superior to the primary solution vector cannot be found, the primary solution vector is used as an optimal solution, the total benefit of the balance service of the optimal solution is maximum, and otherwise, the forward upgrading module is jumped back;

wherein the initial feasible solution module comprises: the system comprises an initial solution selection module, a constraint judgment module and a first replacement module;

the initial solution selection module is used for selecting the subscript of the candidate piconet with the minimum service quality benefit as the initial solution of the ubiquitous service for each ubiquitous service;

the constraint judging module is used for judging whether the initial solution meets constraint conditions of terminal resources and link bandwidth, wherein the constraint conditions are as follows:

whereinIs as followsThe combined resources and bandwidth constraints are then compared to the total bandwidth,the value range of (a) is 1,2, …, K is m · T + E as the total number of constraints, m is the number of resource types on the terminal, T is the number of terminals, and E is the total number of communication links, if the value range of (a) is 1,2, …, the initial solution is feasible, the initial solution is an initial feasible solution, and the scheme determination module is entered, otherwise the first replacement module is entered;

the first replacement module is used for selecting a candidate piconet with the largest amount of saved aggregated resources from all candidate piconets of the ubiquitous service, replacing the initial solution with the subscript of the candidate piconet with the largest amount of saved aggregated resources if a replacement principle is met, and otherwise, not processing, wherein the amount of saved aggregated resources is savedWhere C is the actual resource consumption vector,for the general industryBusiness requirement, X [ i ]]For the ith component of the initial solution, j is the index of the replaced candidate piconet.

5. The system of claim 4, wherein the forward upgrade module comprises: a better solution searching module and a better solution judging module;

the better solution searching module is used for searching a candidate piconet for which the total balance service benefit is higher than that of the initial feasible solution for each ubiquitous service under the condition of meeting the resource constraint condition, if the aggregated resource saving amount is found and is higher than the current maximum value, the subscript of the candidate piconet is used as a better solution, the initial feasible solution is replaced by the better solution, and if the aggregated resource saving amount is not higher than the current maximum value, the better solution judging module is entered;

the better solution judging module is used for judging whether the equilibrium service total benefit increment in the unit aggregation resource saving amount is higher than that of the initial feasible solution or not in the candidate piconet, if so, the subscript of the candidate piconet is used as a better solution, and the initial feasible solution is replaced by the better solution, wherein the equilibrium service total benefit increment in the unit aggregation resource saving amount is delta U_i,j/Δa_i,jWherein Δ U_i,j＝U_i,X[i]-U_i,j。

6. The system of claim 4, wherein the reverse upgrade module specifically comprises: the second replacement module, the more optimal solution searching module and the more optimal solution confirming module;

the second replacement module is used for searching the piconet with the largest total benefit increment of the balanced service on the unit extra aggregation resource in the candidate piconets under the condition of ignoring the resource constraint, and finding an upgrade replacement if the piconet exists, wherein the total benefit increment of the balanced service on the unit extra aggregation resource is delta U_i,j/Δa′_i,jWherein

The more optimal solution searching module is used for searching the piconet with the smallest increment of the total benefit of the equalization service on the unit extra aggregation resource in the candidate piconets, and the total benefit of the equalization is higher than that before reverse upgrading, if the total benefit of the equalization service exists, a degradation replacement is found;

the better solution confirmation module is used for judging whether the solution after degradation replacement found by the better solution searching module is feasible, if the solution is feasible, replacing is carried out, the better solution is used for replacing the better solution to be used as the initial feasible solution, the solution enters the forward upgrading module, if the solution is not feasible, the solution enters the better solution searching module to be degraded again, and if the solution which meets the conditions cannot be found, the solution finally obtained by the forward upgrading module is used as the optimal solution.