CN113065093B - A method and device for determining a link to be repaired - Google Patents

Abstract

The embodiments of the present invention provide a method and device for determining a link to be repaired, calculating the obtained optimal solution of the current objective function as the current optimal solution of the objective; and calculating the optimal solution of the current objective based on the optimal solution of the current objective The first function value of the current objective function corresponding to the optimal solution and the maximum value of the current objective function are used as the second function value; if the first function value and the second function value satisfy the preset convergence condition, based on the current objective The optimal solution is to determine the current link to be repaired; if the first function value and the second function value do not meet the preset convergence conditions, based on the current target optimal solution, determine the current data discarding decision vector and the current flow allocation vector and the actual calculation vector of the current node to update the current objective function, and perform the steps of calculating the optimal solution of the current objective function as the current objective optimal solution. Based on the above processing, the success rate of the target edge computing network in processing computing tasks can be improved.

Description

A method and device for determining a link to be repaired

technical field

The present invention relates to the technical field of computer networks, and in particular, to a method and device for determining a link to be repaired.

Background technique

An edge computing network may include a plurality of edge nodes, each of which is used to process data assigned to the edge node. Every two connected edge nodes in an edge computing network form a link. Since the data that an edge node can process is limited, for each edge node, when the edge node receives a lot of data, it can send to another edge node in the link (which can be called the target link) to which the edge node belongs. A part of the data (which may be referred to as data to be processed) is further processed by another edge node in the target link to process the data to be processed.

If the edge node in a link (which can be called a damaged link) is maliciously attacked, or the hardware of the edge node is damaged, or the line connecting the two edge nodes in the damaged link is damaged, it will cause The edge nodes in this link cannot complete the data processing.

Therefore, it is necessary to repair damaged links in edge computing networks in a timely manner. Since repair resources (for example, repair personnel, replaceable equipment, etc.) are limited, it is necessary to determine the current need to be repaired from each damaged link. The damaged link (may be referred to as the link to be repaired), and the link to be repaired is repaired, so that the edge nodes in the link to be repaired can process computing tasks.

SUMMARY OF THE INVENTION

The purpose of the embodiments of the present invention is to provide a method and an apparatus for determining a link to be repaired, so as to avoid that too much data cannot be processed, and further, the success rate of the target edge computing network in processing computing tasks can be improved. The specific technical solutions are as follows:

In the first aspect, in order to achieve the above object, an embodiment of the present invention provides a method for determining a link to be repaired, the method comprising:

Obtain the current objective function; wherein, the current objective function represents the determination of repairing each damaged link in the target edge computing network based on the link repair decision vector, the data discarding decision vector, the flow allocation vector and the node actual computation vector. The minimum value of the total resources required; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector corresponds to each damaged link one-to-one, and a first element Indicates the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector corresponds to the edge nodes in the target edge computing network one-to-one , a second element represents the current amount of data that needs to be discarded by the edge node corresponding to the second element, the third element in the flow allocation vector corresponds to the links in the target edge computing network one-to-one, and a third element Indicates the total amount of data that each edge node in the link corresponding to the third element can currently migrate. The four elements represent the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element;

Calculate the optimal solution of the current objective function as the optimal solution of the current objective;

Based on the current target optimal solution, calculate the function value of the current objective function corresponding to the current target optimal solution as the first function value, and the maximum value of the current objective function as the second function value;

If the first function value and the second function value satisfy a preset convergence condition, determine the current link to be repaired based on the current target optimal solution;

If the first function value and the second function value do not satisfy the preset convergence condition, determine the current data discarding decision vector, the current flow allocation vector and the current node actual calculation based on the current target optimal solution Quantity vector to update the current objective function, and return to perform the calculation of the optimal solution of the current objective function as the step of the current optimal solution of the objective.

Optionally, the current objective function is:

表示当前的目标函数，min_e,η表示以e和η作为自变量的最小值函数，e表示当前的链路修复决策向量，η表示当前的目标函数的最优割平面，当前的目标函数的最优割平面为基于当前的数据丢弃决策向量、当前的流分配向量和当前的节点实际计算量向量确定出的，E⁰表示所述目标边缘计算网络中的受损链路构成的集合，c_ij表示修复链路ij所需的资源，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，e_ij为当前的链路修复决策向量中与链路ij对应的元素，e_ij表示链路ij的处理方式。

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cut plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual calculation vector, E ⁰ represents the set of damaged links in the target edge computing network, c _ij represents the resources required to repair the link ij, the link ij is the link composed of the i-th edge node and the j-th edge node, and e _ij is the element corresponding to the link ij in the current link repair decision vector , e _ij represents the processing mode of link ij.

Optionally, based on the current target optimal solution, calculate the function value of the current objective function corresponding to the current target optimal solution, as the first function value, and the maximum value of the current objective function, as the second function values, including:

Calculate the function value of the current objective function corresponding to the current objective optimal solution as the first function value;

Based on the current objective optimal solution and the network maximum flow problem solving algorithm, calculate the optimal solution of the sub-function of the current objective function; wherein, the sub-function is:

min _d,f,p θ=Σ _i∈N a _i d _i

in,

表示链路ij的链路容量，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，f_ij为当前的流分配向量中与链路ij对应的元素，f_ij表示链路ij中各边缘节点当前能够迁移的总数据量，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，p_i为当前的节点实际计算量向量中与第i个边缘节点对应的元素，p_i表示第i个边缘节点本地存储的数据中第i个边缘节点当前能够处理的数据量，f_ih为当前的流分配向量中与链路ih对应的元素，f_ih表示链路ih中各边缘节点当前能够迁移的总数据量，链路ih为由第i个边缘节点和第h个边缘节点组成的链路，E¹表示所述目标边缘计算网络中的未受损链路的构成的集合，r_i表示第i个边缘节点本地存储的数据量；min _d,d,p θ represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discard decision vector, and f represents the current flow allocation vector , p represents the actual calculation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, d _i is the current data Discard the element corresponding to the ith edge node in the decision vector, d _i represents the current amount of data that the ith edge node needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data currently migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the current actual node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ih is the current flow allocation vector and the chain. The element corresponding to the path ih, f _ih represents the total amount of data that can be migrated by each edge node in the link ih, and the link ih is the link composed of the i-th edge node and the h-th edge node, and E ¹ represents the The set of undamaged links in the target edge computing network, ri represents the amount of data stored locally by the _ith edge node;

Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value;

Based on the third function value, the current optimal solution of the target, the maximum value of the current target function determined last time, and the first preset formula, the maximum value of the current target function is calculated as the second function value; wherein, The first preset formula is:

表示所述第二函数值，

表示上一次计算的当前的目标函数的最大值，c_ij表示修复链路ij所需的资源，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，θ表示所述第三函数值。

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value.

Optionally, if the first function value and the second function value do not satisfy the preset convergence condition, based on the current target optimal solution, determine the current data discarding decision vector and the current flow allocation vector. and the actual calculation vector of the current node to update the current objective function, and return the optimal solution for calculating the current objective function as the steps of the current objective optimal solution, including:

If the first function value and the second function value do not satisfy the preset convergence condition, based on the current optimal solution of the objective and the third function value, update the optimal cut plane of the current objective function to Update the current objective function, and return the optimal solution for calculating the current objective function as the step of the current objective optimal solution; wherein, the updated optimal cutting plane is:

表示链路ij的链路容量，e′_ij为下一次需要确定的链路修复决策向量中与链路ij对应的元素，e′_ij表示链路ij的处理方式，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式。η′ represents the updated optimal cut plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity pair of link ij the degree of influence of the function value of the sub-function,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij.

Optionally, the preset convergence condition is:

表示所述第二函数值，

表示所述第一函数值，ε表示预设阈值。

represents the second function value,

represents the first function value, and ε represents a preset threshold.

In a second aspect, in order to achieve the above object, an embodiment of the present invention provides an apparatus for determining a link to be repaired, the apparatus comprising:

The obtaining module is used to obtain the current objective function; wherein, the current objective function represents the determined restoration target edge computing network based on the link restoration decision vector, the data discarding decision vector, the flow allocation vector and the node actual calculation amount vector. The minimum value of the total resources required by the damaged link; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector corresponds to each damaged link one-to-one , a first element represents the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector is the same as the one in the target edge computing network. One-to-one correspondence between edge nodes, a second element indicates the amount of data that the edge node corresponding to the second element currently needs to discard, and the third element in the flow allocation vector corresponds to the link in the target edge computing network one-to-one , a third element represents the total amount of data that can be migrated currently by each edge node in the link corresponding to the third element, and the fourth element in the actual calculation vector of the node is the same as the edge node in the target edge computing network. One correspondence, one fourth element represents the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element;

The first determination module is used to calculate the optimal solution of the current objective function as the current optimal solution of the objective;

The second determination module is configured to calculate, based on the current target optimal solution, the function value of the current objective function corresponding to the current target optimal solution, as the first function value, and the maximum value of the current objective function as the second function value;

a third determining module, configured to determine the current link to be repaired based on the current target optimal solution if the first function value and the second function value satisfy a preset convergence condition;

The updating module is used to determine the current data discarding decision vector, the current flow allocation vector and The current node actually calculates the vector to update the current objective function, and returns the optimal solution for calculating the current objective function as the step of the current objective optimal solution.

Optionally, the current objective function is:

表示当前的目标函数，min_e,η表示以e和η作为自变量的最小值函数，e表示当前的链路修复决策向量，η表示当前的目标函数的最优割平面，当前的目标函数的最优割平面为基于当前的数据丢弃决策向量、当前的流分配向量和当前的节点实际计算量向量确定出的，E⁰表示所述目标边缘计算网络中的受损链路构成的集合，c_ij表示修复链路ij所需的资源，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，e_ij为当前的链路修复决策向量中与链路ij对应的元素，e_ij表示链路ij的处理方式。

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cut plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual calculation vector, E ⁰ represents the set of damaged links in the target edge computing network, c _ij represents the resources required to repair the link ij, the link ij is the link composed of the i-th edge node and the j-th edge node, and e _ij is the element corresponding to the link ij in the current link repair decision vector , e _ij represents the processing mode of link ij.

Optionally, the second determination module is specifically used to calculate the function value of the current objective function corresponding to the current objective optimal solution, as the first function value;

Based on the current objective optimal solution and the network maximum flow problem solving algorithm, calculate the optimal solution of the sub-function of the current objective function; wherein, the sub-function is:

min _d,f,p θ=Σ _i∈N a _i d _i

in,

表示链路ij的链路容量，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，f_ij为当前的流分配向量中与链路ij对应的元素，f_ij表示链路ij中各边缘节点当前能够迁移的总数据量，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，p_i为当前的节点实际计算量向量中与第i个边缘节点对应的元素，p_i表示第i个边缘节点本地存储的数据中第i个边缘节点当前能够处理的数据量，f_ih为当前的流分配向量中与链路ih对应的元素，f_ih表示链路ih中各边缘节点当前能够迁移的总数据量，链路ih为由第i个边缘节点和第h个边缘节点组成的链路，E¹表示所述目标边缘计算网络中的未受损链路的构成的集合，r_i表示第i个边缘节点本地存储的数据量；min _d,d,p θ represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discard decision vector, and f represents the current flow allocation vector , p represents the actual calculation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, d _i is the current data Discard the element corresponding to the ith edge node in the decision vector, d _i represents the current amount of data that the ith edge node needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data currently migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the current actual node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ih is the current flow allocation vector and the chain. The element corresponding to the path ih, f _ih represents the total amount of data that can be migrated by each edge node in the link ih, and the link ih is the link composed of the i-th edge node and the h-th edge node, and E ¹ represents the The set of undamaged links in the target edge computing network, ri represents the amount of data stored locally by the _ith edge node;

Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value;

Based on the third function value, the current optimal solution of the target, the maximum value of the current target function determined last time, and the first preset formula, the maximum value of the current target function is calculated as the second function value; wherein, The first preset formula is:

表示所述第二函数值，

表示上一次计算的当前的目标函数的最大值，c_ij表示修复链路ij所需的资源，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，θ表示所述第三函数值。

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value.

Optionally, the updating module is specifically configured to, if the first function value and the second function value do not meet the preset convergence condition, based on the current target optimal solution and the third function value, Update the optimal cutting plane of the current objective function to update the current objective function, and return to perform the calculation of the optimal solution of the current objective function as the step of the current optimal cutting plane; wherein, the updated optimal cutting plane for:

表示链路ij的链路容量，e′_ij为下一次需要确定的链路修复决策向量中与链路ij对应的元素，e′_ij表示链路ij的处理方式，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式。η′ represents the updated optimal cut plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity pair of link ij the degree of influence of the function value of the sub-function,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij.

Optionally, the preset convergence condition is:

表示所述第二函数值，

表示所述第一函数值，ε表示预设阈值。

represents the second function value,

represents the first function value, and ε represents a preset threshold.

An embodiment of the present invention further provides an electronic device, including a processor, a communication interface, a memory, and a communication bus, wherein the processor, the communication interface, and the memory communicate with each other through the communication bus;

memory for storing computer programs;

The processor is configured to implement any of the above-mentioned steps of the method for determining the link to be repaired when executing the program stored in the memory.

An embodiment of the present invention further provides a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, the determination of any of the above-mentioned links to be repaired is implemented method steps.

Embodiments of the present invention also provide a computer program product containing instructions, which, when running on a computer, cause the computer to execute any of the above-mentioned methods for determining a link to be repaired.

In a method for determining a link to be repaired provided by an embodiment of the present invention, the current objective function is obtained; the optimal solution of the current objective function is calculated as the current optimal solution of the objective; based on the current optimal solution of the objective, the current objective function is calculated The function value of the current objective function corresponding to the optimal solution of the objective is taken as the first function value, and the maximum value of the current objective function is taken as the second function value; if the first function value and the second function value satisfy the preset convergence condition, based on the current target optimal solution, determine the current link to be repaired; if the first function value and the second function value do not meet the preset convergence conditions, determine the current data discarding decision vector based on the current target optimal solution , the current flow allocation vector and the current node actual calculation amount vector to update the current objective function, and return the optimal solution for calculating the current objective function as the step of the current objective optimal solution.

Based on the above processing, the objective function represents the minimum value of the total resources required to repair each damaged link in the target edge computing network determined based on the link repair decision vector, the data discarding decision vector, the flow allocation vector and the actual computation amount vector of the node. value. Since the data discarding decision vector, flow allocation vector and node actual computation vector can represent the current unprocessed data volume of each edge node, the optimal solution of the objective function is determined based on the current unprocessed data volume of each edge node, That is to say, the current link to be repaired is determined based on the current amount of unprocessed data of each edge node. Therefore, it can avoid that more data cannot be processed, and further, the success rate of the target edge computing network in processing computing tasks can be improved.

Of course, it is not necessary for any product or method of the present invention to achieve all of the advantages described above at the same time.

Description of drawings

In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those of ordinary skill in the art, other embodiments can also be obtained according to these drawings without creative efforts.

1 is a flowchart of a method for determining a link to be repaired according to an embodiment of the present invention;

2 is a flowchart of another method for determining a link to be repaired according to an embodiment of the present invention;

3 is a flowchart of another method for determining a link to be repaired according to an embodiment of the present invention;

4 is a flowchart of another method for determining a link to be repaired according to an embodiment of the present invention;

5 is a structural diagram of an apparatus for determining a link to be repaired according to an embodiment of the present invention;

FIG. 6 is a structural diagram of an electronic device according to an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art based on the present application fall within the protection scope of the present invention.

Referring to FIG. 1, FIG. 1 is a flowchart of a method for determining a link to be repaired according to an embodiment of the present invention. The method is applied to an electronic device, and the method may include the following steps:

S101: Obtain the current objective function.

Among them, the current objective function represents the minimum value of the total resources required to repair each damaged link in the target edge computing network determined based on the link repair decision vector, the data discarding decision vector, the flow allocation vector and the node actual computation vector. value. The arguments of the current objective function include the link repair decision vector. The first element in the link repair decision vector corresponds to each damaged link one-to-one, and a first element indicates the processing method of the damaged link corresponding to the first element, and the processing method is repair or not repair; data discarding decision The second element in the vector corresponds to the edge nodes in the target edge computing network one-to-one. A second element represents the current amount of data that needs to be discarded by the edge node corresponding to the second element. The third element in the flow allocation vector corresponds to the target edge. The links in the computing network are in one-to-one correspondence, and a third element represents the total amount of data that can be migrated by each edge node in the link corresponding to the third element. The edge nodes correspond to each other one-to-one, and a fourth element indicates the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element.

S102: Calculate the optimal solution of the current objective function as the current optimal solution of the objective.

S103: Based on the current target optimal solution, calculate the function value of the current objective function corresponding to the current target optimal solution as the first function value, and the current maximum value of the objective function as the second function value.

S104: If the first function value and the second function value satisfy the preset convergence condition, determine the current link to be repaired based on the current target optimal solution.

S105: If the first function value and the second function value do not meet the preset convergence conditions, based on the current target optimal solution, determine the current data discarding decision vector, the current flow allocation vector, and the current node actual calculation vector, to Update the current objective function, and return to step S102.

Based on the method for determining a link to be repaired provided by the embodiment of the present invention, the objective function represents the repair target edge computing network determined based on the link repair decision vector, the data discarding decision vector, the flow allocation vector, and the node actual calculation amount vector. The minimum value of the total resources required by the damaged link. Since the data discarding decision vector, flow allocation vector and node actual computation vector can represent the current unprocessed data volume of each edge node, the optimal solution of the objective function is determined based on the current unprocessed data volume of each edge node, That is to say, the current link to be repaired is determined based on the current amount of unprocessed data of each edge node. Therefore, it can avoid that more data cannot be processed, and further, the success rate of the target edge computing network in processing computing tasks can be improved.

The electronic device can be connected to each edge node in the target edge computing network, and further, the electronic device can obtain the current unprocessed data volume of the edge node from each edge node, and the current unprocessed data volume of the edge node is the edge node. The amount of data stored locally by the node; alternatively, the electronic device may not have a connection relationship with each edge node in the target edge computing network, and the user can obtain the amount of data stored locally by each edge node, and each obtained edge node is localized The amount of stored data is stored in the electronic device.

Furthermore, the electronic device may execute the method for determining a link to be repaired provided by the embodiment of the present invention, and determine the current link to be repaired based on the amount of data stored locally by each edge node.

In step S101, the target edge computing network may be an edge computing network that currently has a damaged link.

Referring to FIG. 2, FIG. 2 is a structural diagram of a target edge computing network according to an embodiment of the present invention. The target edge computing network includes multiple edge nodes. In this embodiment, the target edge computing network includes 6 edge nodes as an example. The 6 edge nodes include: edge node 1, edge node 2, edge node 3, and edge node 4. , edge node 5 and edge node 6.

In Fig. 2, the link formed by the edge nodes connected by the dotted line represents the damaged link, and the link formed by the edge nodes connected by the solid line represents the undamaged link. The damaged link includes: the link composed of edge node 1 and edge node 2 (may be referred to as link 12), the link composed of edge node 1 and edge node 3 (may be referred to as link 13), and the link composed of edge node 1 and edge node 3 (may be referred to as link 13). A link formed by edge node 2 and edge node 3 (may be referred to as link 23 ).

Based on the method provided by the embodiment of the present invention, the current link to be repaired can be determined from the link 12 , the link 13 , and the link 23 .

When determining the current links to be repaired, if it is determined that there are many current links to be repaired, after the current links to be repaired are repaired, the computing capability of the edge computing network recovers well, and accordingly, repair the current The link to be repaired requires more resources. If it is determined that there are few links to be repaired at present, the resources required to repair the current links to be repaired are also less, but the computing power of the edge computing network is still not high, which may cause more data due to the inability of the edge nodes to process it. are discarded, which in turn makes the edge computing network unable to complete the computing task.

Therefore, it is necessary to comprehensively consider the total resources required to repair each damaged link in the target edge computing network, as well as the current unprocessed data volume of each edge node in the target edge computing network, and the currently unprocessed data of each edge node in the target edge computing network. The amount of data, that is, the amount of data stored locally by each edge node in the target edge computing network. The corresponding relationship between the total resources required to repair each damaged link in the target edge computing network and the amount of data stored locally by each edge node in the target edge computing network can be expressed as the following formula (1):

in,

表示修复目标边缘计算网络中的各个受损链路所需的总资源，min_e,d,f,p表示以e、d、f和p作为自变量的最小值函数，e表示当前的链路修复决策向量，d表示当前的数据丢弃决策向量，f表示当前的流分配向量，p表示当前的节点实际计算量向量，c_ij表示修复链路ij所需的资源，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，e_ij为当前的链路修复决策向量中与链路ij对应的元素，e_ij表示链路ij的处理方式，a_i表示第i个边缘节点丢弃每单位大小的数据的代价，d_i为当前的数据丢弃决策向量中与第i个边缘节点对应的元素，d_i表示第i个边缘节点丢弃的数据量，p_i为当前的节点实际计算量向量中与第i个边缘节点对应的元素，p_i表示第i个边缘节点本地存储的数据中第i个边缘节点当前能够处理的数据量，f_ij为当前的流分配向量中与链路ij对应的元素，f_ij表示链路ij中各边缘节点当前能够迁移的总数据量，f_ih为当前的流分配向量中与链路ih对应的元素，f_ih表示链路ih中各边缘节点当前能够迁移的总数据量，链路ih为由第i个边缘节点和第h个边缘节点组成的链路，E¹表示目标边缘计算网络中的未受损链路的构成的集合，r_i表示第i个边缘节点本地存储的数据量。

Represents the total resources required to repair each damaged link in the target edge computing network, min _e,d,f,p represents the minimum value function with e, d, f and p as independent variables, e represents the current link Repair decision vector, d represents the current data discarding decision vector, f represents the current flow allocation vector, p represents the actual calculation amount vector of the current node, c _ij represents the resources required to repair the link ij, and link ij is the A link composed of an edge node and the jth edge node, e _ij is the element corresponding to link ij in the current link repair decision vector, e _ij represents the processing method of link ij, a _i represents the ith edge The cost of discarding data per unit size by a node, d _i is the element corresponding to the ith edge node in the current data discarding decision vector, d _i represents the amount of data discarded by the ith edge node, and p _i is the actual value of the current node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ij is the current flow allocation vector in the and chain. The element corresponding to path ij, f _ij represents the total amount of data that each edge node in link ij can currently migrate, f _ih is the element corresponding to link ih in the current flow allocation vector, f _ih represents each edge in link ih The total amount of data that the node can currently migrate, the link ih is the link composed of the i-th edge node and the h-th edge node, E ¹ represents the set of undamaged links in the target edge computing network, r _i represents the amount of data stored locally by the i-th edge node.

The amount of data stored locally by the ith edge node, that is, the amount of data currently unprocessed by the ith edge node. The amount of data ri stored locally by the _i -th edge node includes: the amount of data that the i-th edge node has received but not processed, and the amount of data received by the i-th edge node during the process of repairing the link to which the i-th edge node belongs. amount of data.

The resource c _ij required to repair the link ij can be determined according to the degree of damage of the link ij (for example, the degree of damage of the edge nodes in the link ij, the damage of the line connecting the ith edge node and the jth edge node. The greater the damage degree of the link ij, the greater the resource c _ij required to repair the link ij. The cost a _i of discarding data per unit size by the ith edge node can be the economic loss caused by discarding data per unit size for the ith edge node.

)得到的差值。The current amount of data d _i that needs to be discarded by the i-th edge node is: the data amount ri stored locally by the _i -th edge node, minus the data amount p _i that the i-th edge node can currently handle, and then subtract the i-th edge node The amount of data that the edge node can currently migrate (i.e.

) to get the difference.

Among the data stored locally by the i-th edge node, the current amount of data p _i that can be processed by the i-th edge node satisfies the following conditions:

表示第i个边缘节点最大能够处理的数据量，

可以根据第i个边缘节点的CPU(Central Processing Unit，中央处理器)转速确定，一个边缘节点的CPU转速越大，则该边缘节点最大能够处理的数据量也越大。

Indicates the maximum amount of data that the i-th edge node can process,

It can be determined according to the rotational speed of the CPU (Central Processing Unit, central processing unit) of the ith edge node. The greater the CPU rotational speed of an edge node, the greater the maximum amount of data that can be processed by the edge node.

When f _ij >0, it means that the data migrates from the ith edge node to the j th edge node, and when f _ij <0, it means that the data migrates from the j th edge node to the ith edge node. The total amount of data f _ij that can be migrated by each edge node in the link ij satisfies the following conditions:

表示链路ij的链路容量，链路ij的链路容量表示在预设时间段内链路ij能够传输的最大数据量。预设时间段可以由技术人员根据经验设置。

represents the link capacity of link ij, and the link capacity of link ij represents the maximum amount of data that can be transmitted by link ij within a preset time period. The preset time period can be set by the technician according to experience.

When link ij is a damaged link, the current total data volume f _{ij that can be migrated by each edge node in link ij} satisfies the following conditions:

e _ij is the element corresponding to the link ij in the current link repair decision vector, and e _ij represents the processing mode of the link ij.

When e _ij is the first value, it indicates that the processing mode of link ij is repair, and when e _ij is the second value, it indicates that the processing mode of link ij is not repairing. Both the first numerical value and the second numerical value can be set by the skilled person according to experience, and the first numerical value is different from the second numerical value. For example, the first value is 1 and the second value is 0. When e _ij is 1, it indicates that the processing mode of link ij is repaired, and when e _ij is 0, it indicates that the processing mode of link ij is not repaired.

Since the calculation amount of the optimal solution of the function shown in formula (1) is relatively large, in order to improve the calculation speed and improve the efficiency of determining the link to be repaired, the Benders (Planning Problem Decomposition of Complex Variables) algorithm can be used. , decompose the function shown in formula (1) to obtain the current objective function and the sub-functions of the current objective function. Subsequently, the current link to be repaired may be determined based on the current objective function and the sub-function of the current objective function.

Among them, the current objective function can be:

表示当前的目标函数，min_e,η表示以e和η作为自变量的最小值函数，e表示当前的链路修复决策向量，η表示当前的目标函数的最优割平面，当前的目标函数的最优割平面为基于当前的数据丢弃决策向量、当前的流分配向量和当前的节点实际计算量向量确定出的，E⁰表示目标边缘计算网络中的受损链路构成的集合，c_ij表示修复链路ij所需的资源，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，e_ij为当前的链路修复决策向量中与链路ij对应的元素，e_ij表示链路ij的处理方式。

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cutting plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual computation vector, E ⁰ represents the set of damaged links in the target edge computing network, and c _ij represents Resource required to repair link ij, link ij is the link composed of the i-th edge node and the j-th edge node, e _ij is the element corresponding to link ij in the current link repair decision vector, e _ij represents the processing method of link ij.

In step S102, the electronic device may obtain the optimal solution of the current objective function determined last time, and calculate the optimal solution of the current objective function based on the optimal solution of the current objective function determined last time and the network maximum flow problem solving algorithm. the optimal solution of the subfunction. For the specific manner in which the electronic device calculates the optimal solution of the sub-function of the current objective function, reference may be made to the related introduction in the subsequent embodiments.

Then, the electronic device may calculate the function value (which may be referred to as the fourth function value) of the current sub-function of the objective function corresponding to the optimal solution of the current sub-function of the objective function. Further, the electronic device can calculate the optimal cut plane of the current objective function based on the optimal solution and the fourth function value of the current objective function determined last time, and based on the optimal cut plane of the current objective function and the preset algorithm , calculate the optimal solution of the current objective function as the optimal solution of the current objective.

The preset algorithm may be an ant colony algorithm, a simulated annealing algorithm, or a genetic algorithm, but is not limited thereto.

It can be understood that, when calculating the optimal solution of the current objective function for the first time, the electronic device may randomly select a link repair decision vector as the optimal solution of the current objective function determined last time.

In an embodiment of the present invention, referring to FIG. 3 , step S103 may include the following steps:

S1031: Calculate the function value of the current objective function corresponding to the current objective optimal solution as the first function value.

S1032: Calculate the optimal solution of the sub-function of the current objective function based on the current objective optimal solution and the network maximum flow problem solving algorithm.

Among them, the sub-function is:

min _d,f,p θ=∑ _i∈N a _i d _i (7)

in,

表示链路ij的链路容量，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，f_ij为当前的流分配向量中与链路ij对应的元素，f_ij表示链路ij中各边缘节点当前能够迁移的总数据量，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，p_i为当前的节点实际计算量向量中与第i个边缘节点对应的元素，p_i表示第i个边缘节点本地存储的数据中第i个边缘节点当前能够处理的数据量，f_ih为当前的流分配向量中与链路ih对应的元素，f_ih表示链路ih中各边缘节点当前能够迁移的总数据量，链路ih为由第i个边缘节点和第h个边缘节点组成的链路，E¹表示目标边缘计算网络中的未受损链路的构成的集合，r_i表示第i个边缘节点本地存储的数据量。min _d,d,p represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discarding decision vector, f represents the current flow allocation vector, p represents The actual computation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, and d _i is the difference between the current data discarding decision vector and the The element corresponding to the ith edge node, d _i represents the amount of data that the ith edge node currently needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data currently migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the current actual node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ih is the current flow allocation vector and the chain. The element corresponding to the path ih, f _ih represents the total amount of data that can be migrated by each edge node in the link ih, the link ih is the link composed of the i-th edge node and the h-th edge node, E ¹ represents the target edge Compute the set of undamaged links in the network, where ri represents the amount of data stored locally by the _ith edge node.

S1033: Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value.

S1034: Calculate the current maximum value of the objective function as the second function value based on the third function value, the current target optimal solution, the current maximum value of the target function determined last time, and the first preset formula.

Among them, the first preset formula is:

表示第二函数值，

表示上一次计算的当前的目标函数的最大值，c_ij表示修复链路ij所需的资源，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，θ表示第三函数值。当前的目标最优解也就是本次确定出的链路修复决策向量(即当前的链路修复决策向量)。

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value. The current target optimal solution is the link repair decision vector determined this time (ie, the current link repair decision vector).

In an implementation manner, since the optimal cutting plane of the current objective function has been calculated when the optimal solution of the current objective function (that is, the current optimal solution of the objective) is calculated, and further, the optimal cutting plane of the current objective function is obtained by calculation. After the optimal solution is obtained, the function value of the current objective function corresponding to the current objective optimal solution can be calculated based on the current target optimal solution and the above formula (6), as the first function value.

The electronic device can also calculate the optimal solution of the sub-function of the current objective function based on the current optimal solution of the objective and the algorithm for solving the network maximum flow problem, and the optimal solution of the sub-function of the current objective function includes the calculated current data. The values of the decision vector, the current flow allocation vector, and the current node actual computation vector are discarded. The algorithm for solving the network maximum flow problem may be the Dinic algorithm, or the EdmondsKarp algorithm, or the Ford-Fulkerson (greedy algorithm), but it is not limited thereto.

After the optimal solution of the sub-function of the current objective function is obtained by calculation, the electronic device can calculate The function value of the sub-function of the current objective function is used as the third function value. Further, the electronic device can calculate the maximum value of the current target function based on the third function value, the current target optimal solution, the maximum value of the current target function calculated last time and the above-mentioned formula (9), as the second function value .

可以为：+∞。When the maximum value of the current objective function is calculated for the first time, the maximum value of the current objective function calculated last time

Can be: +∞.

In step S104, if the first function value and the second function value satisfy the preset convergence condition, it indicates that the current objective function has converged, and the link to be repaired corresponding to the current objective optimal solution is repaired, and fewer repair resources are required . Therefore, the electronic device can determine the current link to be repaired based on the current target optimal solution.

In an implementation manner, the electronic device can determine the first element of the first value from the current optimal solution of the target, and the processing method of the damaged link corresponding to the first element is repair, and the electronic device can use the processing method. The damaged link to be repaired is determined as the current link to be repaired. Furthermore, the current link to be repaired can be repaired, so that the link to be repaired can process computing tasks.

In an embodiment of the present invention, the preset convergence condition may be:

表示第二函数值，

表示第一函数值，ε表示预设阈值。其中，预设阈值可以由技术人员根据经验设置，例如，预设阈值可以为0.02，或者也可以为0.01，但并不限于此。满足预设收敛条件表示在修复资源较少时，可以修复较多的受损链路。

represents the second function value,

represents the first function value, and ε represents the preset threshold. Wherein, the preset threshold may be set by technical personnel according to experience, for example, the preset threshold may be 0.02, or may also be 0.01, but is not limited thereto. Satisfying the preset convergence condition means that more damaged links can be repaired when there are fewer repair resources.

In step S105, if the first function value and the second function value do not satisfy the preset convergence condition, indicating that the current objective function has not converged, the electronic device can update the current objective function, and use the updated objective function as the current objective function, and calculate the optimal solution of the current objective function again, and so on, until the determined first function value and second function value corresponding to the current objective optimal solution meet the preset convergence conditions, the electronic device can be based on the current The target optimal solution to determine the current link to be repaired.

In an embodiment of the present invention, referring to FIG. 4 , step S105 may include the following steps:

S1051: If the first function value and the second function value do not meet the preset convergence conditions, based on the current target optimal solution and the third function value, update the optimal cut plane of the current objective function to update the current objective function, And return to step S102.

Among them, the updated optimal cutting plane is:

表示链路ij的链路容量，e′_ij为下一次需要确定的链路修复决策向量中与链路ij对应的元素，e′_ij表示链路ij的处理方式，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式。η′ represents the updated optimal cutting plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity of link ij to the sub-function the degree of influence of the value,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij.

in,

表示上一次计算时链路ij的链路容量，θ″表示基于

计算的当前的目标函数的子函数的函数值。

Indicates the link capacity of the link ij at the last calculation, θ″ represents the

Calculates the function value of the subfunction of the current objective function.

In an implementation manner, if the first function value and the second function value do not satisfy the preset convergence condition, the electronic device may obtain the optimal solution of the sub-function of the current objective function. The optimal solution of the sub-function of the current objective function includes: the current data discarding decision vector, the current flow allocation vector and the current node actual calculation amount vector. Then, the electronic device may calculate the function value (ie, the third function value) of the sub-function of the current objective function corresponding to the optimal solution of the sub-function of the current objective function.

Further, the electronic device can calculate and obtain the updated optimal cut plane based on the current target optimal solution, the third function value and the above formula (11), and further, the objective function including the updated optimal cut plane can be calculated as As the current objective function, and calculate the optimal solution of the current objective function again, and so on, until the determined first function value and second function value corresponding to the current objective optimal solution meet the preset convergence conditions, the electronic The device may determine the current link to be repaired based on the current target optimal solution.

In order to make those skilled in the art better understand the technical solutions of the embodiments of the present invention, the technical solutions of the embodiments of the present invention are exemplarily introduced.

After decomposing the function shown in formula (1) based on the Benders algorithm to obtain the current objective function and the sub-functions of the current objective function, a link repair decision vector e1 can be randomly selected as the maximum value of the current objective function. The optimal solution (that is, the current target optimal solution), and based on the current target optimal solution e1 and the above formula (7), formula (8) and formula (9), calculate the optimal sub-function of the current objective function Solve for d1, f1, and p1.

(即第一函数值)，并基于当前的目标最优解e1、当前的目标函数的子函数的函数值θ1和上述公式(9)，计算得到当前的目标函数的最大值

(即第二函数值)。Then, based on the optimal solutions d1, f1, p1 of the sub-functions of the current objective function and the above formula (7), the function value θ1 of the corresponding sub-functions of the current objective function can be calculated, and based on the current objective function The function value θ1 of the sub-function and the above formula (11) determine the optimal cutting plane η1 of the current objective function. Further, the electronic device can calculate the function value of the current objective function based on the current target optimal solution e1, the optimal cut plane η1 of the current objective function and the above formula (6).

(that is, the first function value), and based on the current target optimal solution e1, the function value θ1 of the sub-function of the current objective function, and the above formula (9), the maximum value of the current objective function is calculated.

(ie the second function value).

和第二函数值

是否满足预设收敛条件，当第一函数值

和第二函数值

满足预设收敛条件时，可以确定当前的目标最优解e1中为第一数值的第一元素，并确定该第一元素对应的受损链路为当前的待修复链路。Further, the electronic device can determine the first function value

and the second function value

Whether the preset convergence conditions are met, when the first function value

and the second function value

When the preset convergence condition is satisfied, it may be determined that the current target optimal solution e1 is the first element of the first value, and the damaged link corresponding to the first element is determined to be the current link to be repaired.

和第二函数值

不满足预设收敛条件时，可以基于当前的目标函数的最优割平面η1和上述公式(6)，计算当前的目标函数的最优解e2，作为当前的目标最优解，并基于当前的目标最优解e2和上述公式(7)、公式(8)和公式(9)，计算得到当前的目标函数的子函数的最优解d2、f2和p2。When the first function value

and the second function value

When the preset convergence conditions are not met, the optimal cutting plane η1 of the current objective function and the above formula (6) can be used to calculate the optimal solution e2 of the current objective function as the current optimal solution of the objective. The objective optimal solution e2 and the above formula (7), formula (8) and formula (9) are calculated to obtain the optimal solutions d2, f2 and p2 of the sub-functions of the current objective function.

(即第一函数值)，并基于当前的目标最优解e2、当前的目标函数的子函数的函数值θ2和上述公式(9)，计算得到当前的目标函数的最大值

(即第二函数值)。Then, based on the optimal solutions d2, f2 and p2 of the sub-function of the current objective function and the above formula (7), the function value θ2 of the corresponding sub-function of the current objective function can be calculated, and based on the current objective function The function value θ2 of the sub-function and the above formula (11) determine the optimal cutting plane η2 of the current objective function. Further, the electronic device can calculate the function value of the current objective function based on the current target optimal solution e2, the optimal cut plane η2 of the current objective function and the above formula (6).

(that is, the first function value), and based on the current objective optimal solution e2, the function value θ2 of the sub-function of the current objective function, and the above formula (9), the maximum value of the current objective function is calculated.

(ie the second function value).

和第二函数值

是否满足预设收敛条件，以此类推，直至确定出的

和

满足预设收敛条件，进而，可以确定与

和

对应的当前的目标最优解en中为第一数值的第一元素，并确定该第一元素对应的受损链路为当前的待修复链路。The electronic device can continue to judge the first function

and the second function value

Whether the preset convergence conditions are met, and so on, until the determined

and

Satisfy the preset convergence conditions, and then, it can be determined that the

and

The corresponding current target optimal solution en is the first element of the first value, and it is determined that the damaged link corresponding to the first element is the current link to be repaired.

Corresponding to the method embodiment in FIG. 1 , see FIG. 5 , which is a structural diagram of an apparatus for determining a link to be repaired according to an embodiment of the present invention, where the apparatus includes:

The obtaining module 501 is used to obtain the current objective function; wherein, the current objective function represents the determined restoration target edge computing network based on the link restoration decision vector, the data discarding decision vector, the flow allocation vector and the node actual calculation amount vector. The minimum value of the total resources required by each damaged link; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector is one-to-one with each damaged link Correspondingly, a first element represents the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector is the same as that in the target edge computing network. One-to-one correspondence between the edge nodes in the flow distribution vector, a second element represents the current amount of data that needs to be discarded by the edge node corresponding to the second element, and the third element in the flow allocation vector is one-to-one with the link in the target edge computing network Correspondingly, a third element represents the current total amount of data that can be migrated by each edge node in the link corresponding to the third element, and the fourth element in the actual calculation vector of the node is the same as the edge node in the target edge computing network. One-to-one correspondence, a fourth element represents the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element;

The first determination module 502 is used to calculate the optimal solution of the current objective function as the current optimal solution of the objective;

The second determination module 503 is configured to calculate, based on the current target optimal solution, the function value of the current objective function corresponding to the current target optimal solution, as the first function value, and the maximum value of the current objective function, as the first function value. two function values;

A third determination module 504, configured to determine the current link to be repaired based on the current target optimal solution if the first function value and the second function value satisfy a preset convergence condition;

The updating module 505 is used to determine the current data discarding decision vector and the current flow allocation vector based on the current target optimal solution if the first function value and the second function value do not meet the preset convergence conditions and the actual calculation vector of the current node to update the current objective function, and return the optimal solution for calculating the current objective function as the step of the current objective optimal solution.

Optionally, the current objective function is:

表示当前的目标函数，min_e,η表示以e和η作为自变量的最小值函数，e表示当前的链路修复决策向量，η表示当前的目标函数的最优割平面，当前的目标函数的最优割平面为基于当前的数据丢弃决策向量、当前的流分配向量和当前的节点实际计算量向量确定出的，E⁰表示所述目标边缘计算网络中的受损链路构成的集合，c_ij表示修复链路ij所需的资源，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，e_ij为当前的链路修复决策向量中与链路ij对应的元素，e_ij表示链路ij的处理方式。

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cut plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual calculation vector, E ⁰ represents the set of damaged links in the target edge computing network, c _ij represents the resources required to repair the link ij, the link ij is the link composed of the i-th edge node and the j-th edge node, and e _ij is the element corresponding to the link ij in the current link repair decision vector , e _ij represents the processing mode of link ij.

Optionally, the second determination module 503 is specifically configured to calculate the function value of the current objective function corresponding to the current objective optimal solution, as the first function value;

Based on the current objective optimal solution and the network maximum flow problem solving algorithm, calculate the optimal solution of the sub-function of the current objective function; wherein, the sub-function is:

min _d,f,p θ=Σ _i∈N a _i d _i

in,

表示链路ij的链路容量，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，f_ij为当前的流分配向量中与链路ij对应的元素，f_ij表示链路ij中各边缘节点当前能够迁移的总数据量，链路ij为由第i个边缘节点和第j个边缘节点组成的链路，p_i为当前的节点实际计算量向量中与第i个边缘节点对应的元素，p_i表示第i个边缘节点本地存储的数据中第i个边缘节点当前能够处理的数据量，f_ih为当前的流分配向量中与链路ih对应的元素，f_ih表示链路ih中各边缘节点当前能够迁移的总数据量，链路ih为由第i个边缘节点和第h个边缘节点组成的链路，E¹表示所述目标边缘计算网络中的未受损链路的构成的集合，r_i表示第i个边缘节点本地存储的数据量；min _d,d,p θ represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discard decision vector, and f represents the current flow allocation vector , p represents the actual calculation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, d _i is the current data Discard the element corresponding to the ith edge node in the decision vector, d _i represents the current amount of data that the ith edge node needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data currently migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the current actual node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ih is the current flow allocation vector and the chain. The element corresponding to the path ih, f _ih represents the total amount of data that can be migrated by each edge node in the link ih, and the link ih is the link composed of the i-th edge node and the h-th edge node, and E ¹ represents the The set of undamaged links in the target edge computing network, ri represents the amount of data stored locally by the _ith edge node;

Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value;

Based on the third function value, the current optimal solution of the target, the maximum value of the current target function determined last time, and the first preset formula, the maximum value of the current target function is calculated as the second function value; wherein, The first preset formula is:

表示所述第二函数值，

表示上一次计算的当前的目标函数的最大值，c_ij表示修复链路ij所需的资源，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式，θ表示所述第三函数值。

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value.

Optionally, the updating module 505 is specifically configured to, if the first function value and the second function value do not satisfy the preset convergence condition, based on the current target optimal solution and the third function value , update the optimal cut plane of the current objective function to update the current objective function, and return to perform the calculation of the optimal solution of the current objective function as the step of the current optimal solution of the objective; wherein, the updated optimal cut The plane is:

表示链路ij的链路容量，e′_ij为下一次需要确定的链路修复决策向量中与链路ij对应的元素，e′_ij表示链路ij的处理方式，e_ij为当前的目标最优解中与链路ij对应的元素，e_ij表示链路ij的处理方式。η′ represents the updated optimal cut plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity pair of link ij the degree of influence of the function value of the sub-function,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij.

Optionally, the preset convergence condition is:

表示所述第二函数值，

表示所述第一函数值，ε表示预设阈值。

represents the second function value,

represents the first function value, and ε represents a preset threshold.

Based on the device for determining a link to be repaired provided by the embodiment of the present invention, the objective function represents the determination of the repair target edge computing network based on the link repair decision vector, the data discard decision vector, the flow allocation vector and the node actual calculation amount vector. The minimum value of the total resources required by the damaged link. Since the data discarding decision vector, flow allocation vector and node actual computation vector can represent the current unprocessed data volume of each edge node, the optimal solution of the objective function is determined based on the current unprocessed data volume of each edge node, That is to say, the current link to be repaired is determined based on the current amount of unprocessed data of each edge node. Therefore, it can avoid that more data cannot be processed, and further, the success rate of the target edge computing network in processing computing tasks can be improved.

An embodiment of the present invention further provides an electronic device, as shown in FIG. 6 , including a processor 601 , a communication interface 602 , a memory 603 and a communication bus 604 , wherein the processor 601 , the communication interface 602 , and the memory 603 pass through the communication bus 604 complete communication with each other;

a memory 603 for storing computer programs;

When the processor 601 is used to execute the program stored in the memory 603, the following steps are implemented:

Obtain the current objective function; wherein, the current objective function represents the determination of repairing each damaged link in the target edge computing network based on the link repair decision vector, the data discarding decision vector, the flow allocation vector and the node actual computation vector. The minimum value of the total resources required; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector corresponds to each damaged link one-to-one, and a first element Indicates the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector corresponds to the edge nodes in the target edge computing network one-to-one , a second element represents the current amount of data that needs to be discarded by the edge node corresponding to the second element, the third element in the flow allocation vector corresponds to the links in the target edge computing network one-to-one, and a third element Indicates the total amount of data that each edge node in the link corresponding to the third element can currently migrate. The four elements represent the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element;

Calculate the optimal solution of the current objective function as the optimal solution of the current objective;

Based on the current target optimal solution, calculate the function value of the current objective function corresponding to the current target optimal solution as the first function value, and the maximum value of the current objective function as the second function value;

If the first function value and the second function value satisfy a preset convergence condition, determine the current link to be repaired based on the current target optimal solution;

If the first function value and the second function value do not satisfy the preset convergence condition, determine the current data discarding decision vector, the current flow allocation vector and the current node actual calculation based on the current target optimal solution Quantity vector to update the current objective function, and return to perform the calculation of the optimal solution of the current objective function as the step of the current optimal solution of the objective.

The communication bus mentioned in the above electronic device may be a peripheral component interconnect standard (Peripheral Component Interconnect, PCI) bus or an Extended Industry Standard Architecture (Extended Industry Standard Architecture, EISA) bus or the like. The communication bus can be divided into an address bus, a data bus, a control bus, and the like. For ease of presentation, only one thick line is used in the figure, but it does not mean that there is only one bus or one type of bus.

The communication interface is used for communication between the above electronic device and other devices.

The memory may include random access memory (Random Access Memory, RAM), and may also include non-volatile memory (Non-Volatile Memory, NVM), such as at least one disk memory. Optionally, the memory may also be at least one storage device located away from the aforementioned processor.

The above-mentioned processor may be a general-purpose processor, including a central processing unit (CPU), a network processor (NP), etc.; it may also be a digital signal processor (Digital Signal Processor, DSP), an application-specific integrated circuit (Application Specific Integrated Circuit, ASIC), Field-Programmable Gate Array (Field-Programmable Gate Array, FPGA) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components.

Based on the electronic device provided by the embodiment of the present invention, the objective function represents the fixed value of each damaged link in the repair target edge computing network determined based on the link repair decision vector, the data discarding decision vector, the flow allocation vector, and the actual computation amount vector of the node. The minimum value of the total resources required. Since the data discarding decision vector, flow allocation vector and node actual computation vector can represent the current unprocessed data volume of each edge node, the optimal solution of the objective function is determined based on the current unprocessed data volume of each edge node, That is to say, the current link to be repaired is determined based on the current amount of unprocessed data of each edge node. Therefore, it can avoid that more data cannot be processed, and further, the success rate of the target edge computing network in processing computing tasks can be improved.

In another embodiment provided by the present invention, a computer-readable storage medium is also provided, where a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, any one of the above chains to be repaired is implemented The steps of the road determination method.

In yet another embodiment provided by the present invention, there is also provided a computer program product containing instructions, which, when running on a computer, cause the computer to execute any method for determining a link to be repaired in the above-mentioned embodiments.

In the above-mentioned embodiments, it may be implemented in whole or in part by software, hardware, firmware or any combination thereof. When implemented in software, it can be implemented in whole or in part in the form of a computer program product. The computer program product includes one or more computer instructions. When the computer program instructions are loaded and executed on a computer, all or part of the processes or functions described in the embodiments of the present invention are generated. The computer may be a general purpose computer, special purpose computer, computer network, or other programmable device. The computer instructions may be stored in or transmitted from one computer-readable storage medium to another computer-readable storage medium, for example, the computer instructions may be downloaded from a website site, computer, server, or data center Transmission to another website site, computer, server, or data center is by wire (eg, coaxial cable, fiber optic, digital subscriber line (DSL)) or wireless (eg, infrared, wireless, microwave, etc.). The computer-readable storage medium may be any available medium that can be accessed by a computer or a data storage device such as a server, data center, etc. that includes an integration of one or more available media. The usable media may be magnetic media (eg, floppy disks, hard disks, magnetic tapes), optical media (eg, DVD), or semiconductor media (eg, Solid State Disk (SSD)), among others.

It should be noted that, in this document, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply any relationship between these entities or operations. any such actual relationship or sequence exists. Moreover, the terms "comprising", "comprising" or any other variation thereof are intended to encompass non-exclusive inclusion such that a process, method, article or device comprising a list of elements includes not only those elements, but also includes not explicitly listed or other elements inherent to such a process, method, article or apparatus. Without further limitation, an element qualified by the phrase "comprising a..." does not preclude the presence of additional identical elements in a process, method, article or apparatus that includes the element.

Each embodiment in this specification is described in a related manner, and the same and similar parts between the various embodiments may be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, for the apparatus, electronic device, computer-readable storage medium and computer program product embodiments, since they are basically similar to the method embodiments, the description is relatively simple, and reference may be made to some descriptions of the method embodiments for related parts.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the protection scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention are included in the protection scope of the present invention.

Claims (8)

1. A method for determining a link to be repaired, wherein the method comprises: Obtain the current objective function; wherein, the current objective function represents the determination of repairing each damaged link in the target edge computing network based on the link repair decision vector, the data discarding decision vector, the flow allocation vector and the node actual computation vector. The minimum value of the total resources required; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector corresponds to each damaged link one-to-one, and a first element Indicates the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector corresponds to the edge nodes in the target edge computing network one-to-one , a second element represents the current amount of data that needs to be discarded by the edge node corresponding to the second element, the third element in the flow allocation vector corresponds to the links in the target edge computing network one-to-one, and a third element Indicates the total amount of data that each edge node in the link corresponding to the third element can currently migrate. The four elements represent the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element; Calculate the optimal solution of the current objective function as the optimal solution of the current objective; Based on the current target optimal solution, calculate the function value of the current objective function corresponding to the current target optimal solution as the first function value, and the maximum value of the current objective function as the second function value; If the first function value and the second function value satisfy a preset convergence condition, determine the current link to be repaired based on the current target optimal solution; If the first function value and the second function value do not satisfy the preset convergence condition, determine the current data discarding decision vector, the current flow allocation vector and the current node actual calculation based on the current target optimal solution Quantity vector to update the current objective function, and return the optimal solution to calculate the current objective function as the step of the current objective optimal solution; The current objective function is:

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cut plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual calculation vector, E ⁰ represents the set of damaged links in the target edge computing network, c _ij represents the resources required to repair the link ij, the link ij is the link composed of the i-th edge node and the j-th edge node, and e _ij is the element corresponding to the link ij in the current link repair decision vector , e _ij represents the processing mode of link ij. 2. method according to claim 1, is characterized in that, described based on current target optimal solution, calculate the function value of the current objective function corresponding to current target optimal solution, as first function value, and current The maximum value of the objective function of , as the second function value, includes: Calculate the function value of the current objective function corresponding to the current objective optimal solution as the first function value; Based on the current objective optimal solution and the network maximum flow problem solving algorithm, calculate the optimal solution of the sub-function of the current objective function; wherein, the sub-function is: min _d,f,p θ=Σ _i∈N a _i d _i in,

min _d,d,p θ represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discard decision vector, and f represents the current flow allocation vector , p represents the actual calculation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, d _i is the current data Discard the element corresponding to the ith edge node in the decision vector, d _i represents the current amount of data that the ith edge node needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data currently migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the current actual node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, and f _ih is the current flow allocation vector and the chain. The element corresponding to the path ih, f _ih represents the total amount of data that can be migrated by each edge node in the link ih, and the link ih is the link composed of the i-th edge node and the h-th edge node, and E ¹ represents the The set of undamaged links in the target edge computing network, ri represents the amount of data stored locally by the _ith edge node; Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value; Based on the third function value, the current optimal solution of the target, the maximum value of the current target function determined last time, and the first preset formula, the maximum value of the current target function is calculated as the second function value; wherein, The first preset formula is:

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value. 3. The method according to claim 2, wherein, if the first function value and the second function value do not meet the preset convergence condition, based on the current target optimal solution, determine the current The data discarding decision vector, the current flow allocation vector and the current node actual calculation vector are used to update the current objective function, and return the optimal solution to perform the calculation of the current objective function as the step of the current objective optimal solution, include: If the first function value and the second function value do not satisfy the preset convergence condition, based on the current optimal solution of the objective and the third function value, update the optimal cut plane of the current objective function to Update the current objective function, and return the optimal solution for calculating the current objective function as the step of the current objective optimal solution; wherein, the updated optimal cutting plane is:

η′ represents the updated optimal cut plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity pair of link ij the degree of influence of the function value of the sub-function,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij. 4. The method according to claim 1, wherein the preset convergence condition is:

represents the second function value,

represents the first function value, and ε represents a preset threshold. 5. An apparatus for determining a link to be repaired, wherein the apparatus comprises: The acquisition module is used to acquire the current objective function; wherein, the current objective function represents the determined restoration target edge computing network based on the link restoration decision vector, the data discarding decision vector, the flow allocation vector and the node actual calculation amount vector. The minimum value of the total resources required by the damaged link; the independent variable of the current objective function includes a link repair decision vector; the first element in the link repair decision vector corresponds to each damaged link one-to-one , a first element represents the processing method of the damaged link corresponding to the first element, and the processing method is to repair or not to repair; the second element in the data discarding decision vector is the same as the one in the target edge computing network. One-to-one correspondence between edge nodes, a second element indicates the amount of data that the edge node corresponding to the second element currently needs to discard, and the third element in the flow allocation vector corresponds to the link in the target edge computing network one-to-one , a third element represents the total amount of data that can be migrated currently by each edge node in the link corresponding to the third element, and the fourth element in the actual calculation vector of the node is the same as the edge node in the target edge computing network. One correspondence, one fourth element represents the amount of data that the edge node can currently process in the data locally stored by the edge node corresponding to the fourth element; The first determination module is used to calculate the optimal solution of the current objective function as the current optimal solution of the objective; The second determination module is configured to calculate, based on the current target optimal solution, the function value of the current objective function corresponding to the current target optimal solution, as the first function value, and the maximum value of the current objective function as the second function value; a third determining module, configured to determine the current link to be repaired based on the current target optimal solution if the first function value and the second function value satisfy a preset convergence condition; The updating module is used to determine the current data discarding decision vector, the current flow allocation vector and The current node actually calculates the vector to update the current objective function, and returns the optimal solution for calculating the current objective function as the step of the current objective optimal solution; The current objective function is:

Represents the current objective function, min _{e, η} represents the minimum value function with e and η as independent variables, e represents the current link repair decision vector, η represents the optimal cut plane of the current objective function, and the The optimal cut plane is determined based on the current data discarding decision vector, the current flow allocation vector and the current node actual calculation vector, E ⁰ represents the set of damaged links in the target edge computing network, c _ij represents the resources required to repair the link ij, the link ij is the link composed of the i-th edge node and the j-th edge node, and e _ij is the element corresponding to the link ij in the current link repair decision vector , e _ij represents the processing mode of link ij. 6. device according to claim 5, is characterized in that, the second determination module, is specifically used for calculating the function value of the current objective function corresponding to the current target optimal solution, as the first function value; Based on the current objective optimal solution and the network maximum flow problem solving algorithm, calculate the optimal solution of the sub-function of the current objective function; wherein, the sub-function is: min _d,f,p θ=Σ _i∈N a _i d _i in,

min _d,d,p θ represents the sub-function, min _d,d,p represents the minimum value function with d, f and p as independent variables, d represents the current data discard decision vector, and f represents the current flow allocation vector , p represents the actual calculation amount vector of the current node, N represents the set of edge nodes in the target edge computing network, a _i represents the cost of discarding data per unit size by the ith edge node, d _i is the current data Discard the element corresponding to the ith edge node in the decision vector, d _i represents the current amount of data that the ith edge node needs to discard,

Represents the link capacity of the link ij, e _ij is the element corresponding to the link ij in the current target optimal solution, e _ij represents the processing method of the link ij, f _ij is the link ij in the current flow allocation vector Corresponding elements, f _ij represents the total amount of data that can be migrated by each edge node in link ij, link ij is the link composed of the i-th edge node and the j-th edge node, and p _i is the actual current node The element corresponding to the ith edge node in the calculation vector, pi represents the amount of data that the _ith edge node can currently process in the data stored locally by the ith edge node, f _ih is the current flow allocation vector and the chain The element corresponding to the path ih, f _ih represents the total amount of data that each edge node in the link ih can currently migrate, and the link ih is the link composed of the i-th edge node and the h-th edge node, and E ¹ represents the The set of undamaged links in the target edge computing network, ri represents the amount of data stored locally by the _ith edge node; Calculate the function value of the sub-function corresponding to the optimal solution of the sub-function as the third function value; Based on the third function value, the current optimal solution of the target, the maximum value of the current target function determined last time, and the first preset formula, the maximum value of the current target function is calculated as the second function value; wherein, The first preset formula is:

represents the second function value,

Represents the maximum value of the current objective function calculated last time, c _ij represents the resources required to repair the link ij, e _ij is the element corresponding to the link ij in the current optimal solution of the target, and e _ij represents the value of the link ij Processing mode, θ represents the third function value. 7. The apparatus according to claim 6, wherein the update module is specifically configured to, if the first function value and the second function value do not satisfy the preset convergence condition, based on the current target The optimal solution and the third function value, update the optimal cutting plane of the current objective function to update the current objective function, and return the optimal solution that performs the calculation of the current objective function, as the optimal solution of the current objective function. Steps; wherein, the updated optimal cutting plane is:

η′ represents the updated optimal cut plane, θ represents the third function value, E ⁰ represents the set of damaged links in the target edge computing network, μ _ij represents the link capacity pair of link ij the degree of influence of the function value of the sub-function,

Represents the link capacity of link ij, e' _ij is the element corresponding to link ij in the link repair decision vector to be determined next time, e' _ij represents the processing method of link ij, and e _ij is the current target maximum The element corresponding to the link ij in the optimal solution, e _ij represents the processing method of the link ij. 8. An electronic device, characterized in that it comprises a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface, and the memory complete mutual communication through the communication bus; memory for storing computer programs; The processor is configured to implement the method steps described in any one of claims 1-4 when executing the program stored in the memory.

Images