CN113452552B - Information entropy perception-based super-multi-target controller placement method - Google Patents

Abstract

The invention discloses a super multi-target controller placement method based on information entropy perception, comprising: initializing network information and configuration information corresponding to a wide area network; acquiring topological link length information corresponding to the wide area network; acquiring an initial population; The number of iterations, iterative optimization processing is performed on the initial population to obtain the optimal population; according to the optimal population, the optimal solution set and the optimal controller placement scheme set are obtained by calculation. The invention can determine the placement and deployment of the controller according to the deployment cost of the control network, the load difference of the controller, the average propagation delay between the controller and the switching node, the average propagation delay between the controllers and the reliability of the control network Scheme collection.

Description

A super multi-objective controller placement method based on information entropy perception

technical field

The invention belongs to the technical field of communication, and in particular relates to a super multi-target controller placement method based on information entropy perception.

Background technique

Wide area network is widely used because of its advantages of large transmission capacity, easy transmission of various signals, and dynamic reconfiguration of networking, especially in cloud computing services.

In the prior art, SDN (Software Defined Network, Software Defined Network) is usually used to carry out intelligent global management and control of the WAN. The main feature of the SDN is the separation of control and forwarding, that is, the distributed control is changed into a relatively centralized control of multiple controllers. For control, open standard interfaces are used between layers, and common hardware is used to complete necessary forwarding. For example, SDN is used to control the WAN based on Dense Wavelength Division Multiplexing (Dense Wavelength Division Multiplexing) technology.

However, in order to apply SDN to the WAN, it is first necessary to place a certain number of controllers in the WAN, divide the WAN into multiple domains, each domain is managed by a separate controller, and determine the location of the controller to meet specific needs SDN-CPPs (SDN ControllerPlacement Problems, SDN Controller Placement Problems), the controller placement problem will limit the network fault tolerance, expand In addition, the number and location of the controllers will seriously affect the delay, reliability, elasticity and other indicators of the WAN. Further, the indicators can be abstracted into mutually restrained optimization goals. Therefore, this problem is currently considered to be is a nondeterministic polynomial NP-hard problem. In addition, since the virtualization of various network elements in the WAN is handled by NFV (Network Functions Virtualization), and SDN is responsible for the virtualization of the network itself, such as the interconnection between network nodes, the controller placement problem of SDN-CPPs is also It will affect the performance of VN (Virtual Network, virtual network).

There are still many defects in the technical solutions for solving the above-mentioned controller placement problem in the prior art. First, it only considers the propagation delay between the controller and the switches it controls from a single perspective, and does not consider the propagation between controllers. The delay will lead to the inability to optimize the delay consumed by the propagation of control information between controllers, thereby affecting the performance of the network. Second, the load balancing problem is not considered. Because the load of most controllers is too large or too small, It will lead to the shortage or waste of controller storage resources in the final placement scheme; thirdly, only the reliability of the control network is considered alone, not combined with other optimization goals; fourthly, the new control link and the operation of the controller are not considered. Maintenance, only considering the placement cost of the controller, is not conducive to the practical application of the placement scheme.

SUMMARY OF THE INVENTION

In order to solve the above problems existing in the prior art, the present invention provides a super multi-objective controller placement method based on information entropy perception. The technical problem to be solved by the present invention is realized by the following technical solutions:

网络拓扑节点数量信息|N|、网络拓扑链路数量信息|E|、信息熵网格数a_i,i＝1,2,…,5、直连链路源节点信息A_i和直连链路宿节点信息O_i，其中，i为1，2，……，|N|，网络中第i个节点的可靠性r_i ^node，其中，i为1，2，……，|N|，网络中第i条链路的可靠性r_i ^edge，其中，i为1，2，……，|E|；所述配置信息包括：种群规模信息Num、控制器数量上限信息maxCNum、进化感知阈值信息τ、控制器的部署成本

控制器管理所属交换节点产生的成本

新建控制链路产生的成本

控制链路成本的权重ψ和最大进化代数信息G_max；步骤2：获取所述广域网对应的拓扑链路长度信息；步骤3：获取初始种群；步骤4：按照预设最大进化代数信息G_max，对初始种群进行迭代优化处理，以得到最优种群；步骤5：根据所述最优种群，计算得到最优解集和最优控制器放置方案集。A method for placing a super-multi-target controller based on information entropy perception, comprising: step 1: initializing network information and configuration information corresponding to a wide area network, the network information comprising: network node longitude information λ _i , network node latitude information

Network topology node number information |N|, network topology link number information |E|, information entropy grid number a _i , i=1,2,...,5, direct link source node information A _i and direct link Road sink node information O _i , where i is 1, 2, ..., |N|, the reliability of the ith node in the network r _i ^node , where i is 1, 2, ..., |N|, Reliability r _i ^edge of the i-th link in the network, where i is 1, 2, ..., |E|; the configuration information includes: population size information Num, upper limit information on the number of controllers maxCNum, evolution perception threshold Information τ, the deployment cost of the controller

The cost incurred by the controller to manage the switching nodes to which it belongs

Cost of new control link

Control the weight ψ of the link cost and the maximum evolutionary algebra information G _max ; Step 2: obtain the topological link length information corresponding to the wide area network; Step 3: obtain the initial population; Step 4: According to the preset maximum evolutionary algebra information G _max , Perform iterative optimization processing on the initial population to obtain the optimal population; Step 5: According to the optimal population, calculate and obtain the optimal solution set and the optimal controller placement scheme set.

In an embodiment of the present invention, the step 2 includes: step 2-1: based on the network information, calculate the length of the topology link corresponding to the wide area network, which is expressed as:

表示第i个源节点A_i的经度，

表示第i个源节点A_i的纬度，

表示第i个宿节点O_i的经度，

表示第i个宿节点O_i纬度，L(A_i,O_i)表示第i个源节点A_i和第i个宿节点O_i之间直连链路的长度，i取值为1，2，…，|N|；步骤2-2：根据预设最短路计算规则，计算所述广域网对应的拓扑中任意两个节点之间的最短路信息。Among them, R _earth represents the radius of the earth, and the value is R _earth =6400km,

represents the longitude of the i-th source node A _i ,

represents the latitude of the i-th source node A _i ,

represents the longitude of the i-th sink node O _i ,

Represents the latitude of the ith sink node O _i , L(A _i ,O _i ) represents the length of the direct link between the ith source node A _i and the ith sink node O _i , and i is 1, 2 , .

In an embodiment of the present invention, the step 3 includes: step 3-1: randomly generate an integer according to the upper limit information on the number of controllers maxCNum, where the integer range is between [1, maxCNum], The integer is used as the number of controllers for the i-th individual; Step 3-2: Obtain the i-th random vector R _v (i) of length N, and sort the random vector from large to small to obtain R _v1 ( i), wherein the value of each position in the random vector is a random number between (0, 1), and the number C _num (i) in the R _v1 (i) is the initial population threshold ε _i ; step 3-3: Modify the number smaller than the initial population threshold εi in R _v (i) to 0, and the number greater than or equal to εi to 1 to obtain the i-th initial individual; Step 3-4: Repeat step 3- 1 to step 3-3, until i=Num, to obtain the initial population P ₀ .

Beneficial effects of the present invention:

First, the present invention adaptively adjusts the calculation formula of the crowding degree according to the information entropy perception coefficient H _par , so that when the population to be optimized is selected, the population to be optimized with better convergence and distribution can be obtained. When the coefficient H _par is small, it means that the distribution of the population to be optimized is poor. Therefore, in the process of calculating the distribution of the population, the weight of the Harmonic average distance will increase, which helps to improve the distribution of the population; When the entropy perception coefficient H _par is large, it means that the distribution of the population to be optimized is excellent, which can promote the increase of the population convergence. Therefore, in the calculation process of the population distribution, the Euclidean distance between each individual and the origin O _m The weight will increase, which will help to improve the convergence of the population, which can promote the evolution of the population in a better direction, which is convenient to obtain higher control network performance, lower control network propagation delay, and more reasonable controller storage. A set of controller placement solutions for resource allocation, higher control network reliability, and lower controller placement costs.

排序等级平均信息熵值H_re较小，说明待优化种群

的选择压力较小，这说明精英个体不易从待优化种群中选出，因而使用K支配排序的方法提高种群内精英个体的选择压力，从而促使精英个体在交配池中聚集；而如果待优化种群

排序等级平均信息熵值H_re较大，说明待优化种群

的选择压力较大，这说明精英个体可以从待优化种群中选出，因而使用非支配排序的方法选择种群内的精英个体。Second, in the process of generating the mating pool, the present invention uses two sorting strategies according to the different selection pressures of the population to be optimized.

The average information entropy value H _re of the ranking level is small, indicating that the population to be optimized

The selection pressure of is small, which means that elite individuals are not easy to be selected from the population to be optimized. Therefore, the K-dominated sorting method is used to increase the selection pressure of elite individuals in the population, thereby promoting elite individuals to gather in the mating pool; and if the population to be optimized is

The average information entropy value H _re of the ranking level is relatively large, indicating that the population to be optimized is

The selection pressure of is relatively large, which means that elite individuals can be selected from the population to be optimized, so the non-dominated sorting method is used to select the elite individuals in the population.

Third, the present invention carefully selects five optimization objectives in the calculation of the optimization objectives, which are the deployment cost of the control network, the load difference of the controller, the propagation delay between the controller and the switching nodes, and the delay between the control nodes. Propagation delay, and reliability of the control network. These five optimization objectives are mutually restrained, and the five optimization objectives are optimized at the same time, so that the control network can achieve better performance indicators on different scales.

The present invention will be further described in detail below with reference to the accompanying drawings and embodiments.

Description of drawings

1 is a schematic flowchart of a method for placing a super-multi-target controller based on information entropy perception provided by an embodiment of the present invention;

Fig. 2 is a kind of the present invention that the embodiment of the present invention provides and contrast method under Internet OS3E obtains approximate optimal controller placement scheme set R the optimized target value contrast schematic diagram;

Fig. 3 is another kind of the present invention that the embodiment of the present invention provides and the contrasting schematic diagram of the optimization target value of the obtained approximate optimal controller placement scheme set R under Internet OS3E;

Fig. 4 is another kind of the present invention that the embodiment of the present invention provides and the comparison method under Internet OS3E obtains the approximate optimal controller placement scheme set R the optimized target value comparison schematic diagram;

Fig. 5 is another kind of the present invention that the embodiment of the present invention provides and the comparative method under Internet OS3E obtains the approximate optimal controller placement scheme set R the optimized target value comparison schematic diagram;

Fig. 6 is another kind of the present invention that the embodiment of the present invention provides and the contrasting schematic diagram of the optimization target value of the approximate optimal controller placement scheme set R obtained under Internet OS3E;

FIG. 7 is a schematic diagram showing the comparison of the optimization target values of the approximate optimal controller placement scheme set R obtained by the present invention and the comparative method under Internet OS3E according to another embodiment of the present invention.

Detailed ways

The present invention will be described in further detail below with reference to specific embodiments, but the embodiments of the present invention are not limited thereto.

Example 1

Please refer to FIG. 1. FIG. 1 is a schematic flowchart of a method for placing a super-multi-target controller based on information entropy perception provided by an embodiment of the present invention, including:

Step 1: Initialize the network information and configuration information corresponding to the WAN.

The wide area network of the present invention is described by taking the Internet OS3E network as an example. The Internet OS3E network is an American backbone network and is widely used in the simulation research of the controller placement problem.

网络拓扑节点数量信息|N|、网络拓扑链路数量信息|E|、信息熵网格数a_i,i＝1,2,…,5、直连链路源节点信息A_i和直连链路宿节点信息O_i，其中，i为1，2，……，|N|，网络中第i个节点的可靠性r_i ^node，其中，i为1，2，……，|N|，网络中第i条链路的可靠性r_i ^edge，其中，i为1，2，……，|E|；所述配置信息包括：种群规模信息Num、控制器数量上限信息maxCNum、进化感知阈值信息τ、控制器的部署成本

控制器管理所属交换节点产生的成本

新建控制链路产生的成本

控制链路成本的权重ψ和最大进化代数信息G_max。Optionally, the network information includes: network node longitude information λ _i , network node latitude information

Network topology node number information |N|, network topology link number information |E|, information entropy grid number a _i , i=1,2,...,5, direct link source node information A _i and direct link Road sink node information O _i , where i is 1, 2, ..., |N|, the reliability of the ith node in the network r _i ^node , where i is 1, 2, ..., |N|, Reliability r _i ^edge of the i-th link in the network, where i is 1, 2, ..., |E|; the configuration information includes: population size information Num, upper limit information on the number of controllers maxCNum, evolution perception threshold Information τ, the deployment cost of the controller

The cost incurred by the controller to manage the switching nodes to which it belongs

Cost of new control link

The weight ψ that controls the link cost and the maximum evolutionary algebraic information G _max .

The present invention takes Num=100, evolution perception threshold τ=0.4, maximum evolutionary algebra _Gmax =100, total number of network topology nodes |N|=34 and total number of network topology links |E|=42 to conduct simulation experiments.

Step 2: Acquire topological link length information corresponding to the wide area network.

Optionally, the step 2 includes:

Step 2-1: Based on the network information, calculate the length of the topology link corresponding to the WAN, which is expressed as:

表示第i个源节点A_i的经度，

表示第i个源节点A_i的纬度，

表示第i个宿节点O_i的经度，

表示第i个宿节点O_i纬度，L(A_i,O_i)表示第i个源节点A_i和第i个宿节点O_i之间直连链路的长度，i取值为1，2，…，|N|。Among them, R _earth represents the radius of the earth, and the value is R _earth =6400km,

represents the longitude of the i-th source node A _i ,

represents the latitude of the i-th source node A _i ,

represents the longitude of the i-th sink node O _i ,

Represents the latitude of the ith sink node O _i , L(A _i ,O _i ) represents the length of the direct link between the ith source node A _i and the ith sink node O _i , and i is 1, 2 , …, |N|.

Step 2-2: Calculate the shortest path information between any two nodes in the topology corresponding to the wide area network according to a preset shortest path calculation rule.

Internet OS3E网络拓扑节点数N、第i个源节点A_i和第i个宿节点O_i之间直连链路的长度L(A_i,O_i)，这些参数输入给该算法Floyd算法；通过MATLAB软件计算并输出Internet OS3E网络拓扑中任意两个节点i和节点j之间的最短路集合s_ij，i，j＝1，2，……，|N|，且i≠j。The preset shortest calculation rule is determined by those skilled in the art according to business needs, and the present invention does not limit it, for example, Floyd algorithm or Dijkstra algorithm, the present invention takes Floyd algorithm as an example to illustrate, specifically, it will input the Internet OS3E network Longitude λ _i and latitude of the ith node of the topology network

The number of Internet OS3E network topology nodes N, the length of the direct link between the ith source node A _i and the ith sink node O _i , L(A _i , O _i ), these parameters are input to the algorithm Floyd algorithm; MATLAB software calculates and outputs the shortest path set s _ij between any two nodes i and j in the Internet OS3E network topology, i, j = 1, 2, ..., |N|, and i≠j.

Step 3: Obtain the initial population P ₀ .

Optionally, the step 3 includes:

Step 3-1: According to the information maxCNum of the upper limit of the number of controllers, randomly generate an integer, where the integer range is between [1, maxCNum], and the integer is used as the number of controllers of the ith individual C _num ( i).

Step 3-2: Obtain the i-th random vector R _v (i) of length |N|, and sort the random vectors from large to small to obtain R _v1 (i), where each of the random vectors The values of the positions are all random numbers between (0, 1), and the C _num (i)th number in the R _v1 (i) is the initial population threshold ε _i .

Step 3-3: Modify the number less than the initial population threshold εi in R _v (i) to 0, and the number greater than or equal to εi to 1 to obtain the i-th initial individual.

Step 3-4: Repeat steps 3-1 to 3-3 until i=Num, and obtain the initial population P ₀ .

Step 4: Perform iterative optimization processing on the initial population according to the preset maximum evolutionary algebra information G _max to obtain the optimal population.

Optionally, the step 4 includes:

Step 4-1: Determine the population to be optimized

中的每个个体都代表一个控制器部署方案，其中G_ene为当前进化代数，G_ene的取值为0，1，2，…，G_max。

Each individual in represents a controller deployment scheme, where _Gene is the current evolutionary algebra, and the value of _{Gene is 0, 1, 2, ..., G max .}

Step 4-2: Calculate the objective function value corresponding to all individuals in the population to be optimized;

Optionally, the step 4-2 includes:

中按从小到大顺序选出第i个个体x_i，i＝1，2，…，Num，根据交换节点由距离最近的控制器控制的原则，将交换节点分配给控制器节点，得到该个体的控制器部署数量m、第i个节点控制器的个数k_i，i＝1，2，…，|N|、第i个控制器控制交换节点的个数w_i，i＝1，2，…，m、节点i部署控制器且交换节点j的交换机是否由节点i的控制器控制的布尔变量c_ij，i，j＝1，2，…，|N|、网络中第i个节点是否部署控制器的布尔变量h_i，i＝1，2，…，|N|、第i条网络链路是否位于第j个控制器的控制网络区域中的布尔变量

i＝1，2，…，|E|，j＝1，2，…，|N|、第i个交换节点是否位于第j个控制器的控制网络区域中的布尔变量

i，j＝1，2，…，|N|。Step 4-21: Sequence from the population to be optimized

Select the i-th individual x _i in ascending order, i=1, 2, . The number of deployed controllers m, the number of i-th node controllers k _i , _i =1, 2, . , ..., m, node i deploys a controller and switches whether the switch of node j is controlled by the controller of node i, the Boolean variable c _ij , i, j=1, 2, ..., |N|, the ith node in the network Boolean variable h _i of whether to deploy the controller, i=1, 2, . . . , |N|, whether the ith network link is located in the control network area of the jth controller

i=1, 2,..., |E|, j=1, 2,..., |N|, Boolean variable whether the ith switching node is located in the control network area of the jth controller

i, j = 1, 2, ..., |N|.

中第i个个体x_i的目标函数，i＝1，2，…，Num，表示为：Step 4-22: Calculate the population to be optimized

The objective function of the i-th individual x _i , i=1, 2, ..., Num, is expressed as:

F( _xi )=(f ₁ ( _xi ), f ₂ ( _xi ), f ₃ ( _xi ), f ₄ ( _xi ), f ₅ ( _xi )) ^T ,

中第i个个体x_i的目标函数，f₁(x_i)表示待优化种群

中第i个个体x_i的控制器部署成本，f₂(x_i)表示待优化种群

中第i个个体x_i的负载差异，f₃(x_i)表示待优化种群

中第i个个体x_i的控制网络中控制器与交换节点之间的平均传播时延，f₄(x_i)表示待优化种群

中第i个个体x_i的控制网络中控制器之间的平均传播时延，f₅(x_i)表示待优化种群

中第i个个体x_i的控制网络的不可靠性。Among them, F(x _i ) represents the population to be optimized

The objective function of the _i -th individual xi in , f ₁ ( _xi ) represents the population to be optimized

The controller deployment cost of the _i -th individual xi in , f ₂ ( _xi ) represents the population to be optimized

The load difference of the _i -th individual xi in , f ₃ ( _xi ) represents the population to be optimized

The average propagation delay between the controller and the switching node in the control network of the _i -th individual xi, f ₄ ( _xi ) represents the population to be optimized

The average propagation delay between the controllers in the control network of the _i -th individual xi, f ₅ ( _xi ) represents the population to be optimized

The unreliability of the control network for the _i -th individual xi in .

Step 4-23: Repeat steps 4-21 to 4-22 until the objective function values of all individuals in the population to be optimized are calculated.

第r个排序等级中的个体总数D_sum(r)，其中，r＝1,2，…。Step 4-3: Perform non-dominated sorting on the population to be optimized to obtain the Pareto optimal solution set Ω corresponding to the population to be optimized, the total number of ranking levels Deg of all individuals, and the population to be optimized.

The total number of individuals in the r-th ranking level D _sum (r), where r = 1, 2, . . .

Step 4-4: Calculate the information entropy perception coefficient H _par .

Optionally, the steps 4-3 include:

Step 4-41: Normalize each optimization objective in all individual objective functions in the Pareto optimal solution set Ω, and express as:

F'(x _i )={f' ₁ (x _i ),f' ₂ (x _i ),...,f' _M (x _i )},i=1,2,...,|Ω|,

Among them, F'(x _i ) is the normalized objective function value of the ith individual in the Pareto optimal solution set Ω, and the value range of i is i=1, 2,...,|Ω|, |Ω | is the number of individuals in the Pareto optimal solution set Ω, M is the number of optimization targets, the value M=5, f' _k ( _xi ) is the i-th individual x _i in the Pareto optimal solution set Ω The k-th normalized optimization objective is expressed as:

Among them, f _k ( _xi ) is the k-th optimization objective value in the objective function of x _i of the individual, the value range of k is k=1, 2,...,M, and M is the number of optimization objectives (M=5) .

It should be noted that, the present invention is described by taking M=5 as an example.

Step 4-42: Calculate the influence distance between any two different individuals in the Pareto optimal solution set Ω. The specific calculation method is as follows:

Among them, d( _xi , x _j ) is the influence distance between individual _xi and individual x _j , f' _k ( _xi ) is the k-th normalized optimization of the ith individual _xi in the population Goal, f' _k (x _j ) is the k-th normalized optimization goal of the j-th individual x _j in the population, and the value range of k is k=1, 2,...,M, where M is the optimization goal number.

It should be noted that, the present invention is described by taking M=5 as an example.

Step 4-43: Calculate the Gaussian influence function value between any two different individuals in the Pareto optimal solution set Ω. The specific calculation method is as follows:

Among them, d(x _i , x _j ) is the influence distance between individual x _i and individual x _j , σ is the standard deviation of the distribution, π is the pi, the value range of i and j is i≠j, i, j=1,2,...,|Ω|.

Step 4-44: The density value of a single individual refers to the sum of the influence function values of all non-dominated individuals in the target space on the individual. Assuming that the scale of the Pareto optimal solution set in the target space is |Ω|, then the jth Density value of individual x _j :

Among them, D _m (x _j ) represents the density value of the jth individual in the population, and the value range of j is j=1, 2,..., |Ω|, and Ω represents the Pareto optimal solution of the population in the target space The size of the Pareto optimal solution set is |Ω|.

Step 4-45: Divide the target space into a ₁ ×a ₂ ×a ₃ ×a ₄ ×a ₅ grids, and count the number of Pareto optimal solution sets in each grid |Ω _ijkbd | , where the value ranges of i,j,k,b,d are i=1,2,...,a ₁ , j=1,2,...,a ₂ , k=1,2,...,a ₃ , b=1,2,...,a ₄ , d=1,2,...,a ₅ .

It should be noted that the present invention takes ɑ _k =4 as an example for simulation description, where k=1, 2, . . . , M.

Step 4-46: Calculate the sum D _ijkbd of the density values of all individuals in each grid of the Pareto optimal solution set in the target space. The specific calculation method is as follows:

Step 4-47: Calculate the density function of the Pareto optimal solution set. The specific calculation method is as follows:

Among them, ρ _ijkbd represents the density function value of the Pareto optimal solution set in the ijkbd grid space, and the value range of i, j, k, b, d is i=1, 2,...,a ₁ , j =1,2,...,a ₂ , k=1,2,...,a ₃ ,b=1,2,...,a ₄ ,d=1,2,...,a ₅ .

Step 4-48: Calculate the information entropy of the Pareto optimal solution set, the specific calculation method is as follows:

Among them, H _Par is the information entropy of the Pareto optimal solution set Ω.

Step 4-5: Convert the coding mode of the population to be optimized from binary code to Gray code to obtain the population to be optimized in the form of Gray code

进行优化，以得到新种群。Step 4-6: For the population to be optimized in the Gray code form

Optimizing to get new populations.

Optionally, the steps 4-6 include:

的拥挤度C(x_i)。Step 4-61: Calculate the population

The crowding degree C(x _i ).

The steps 4-61 include:

中全部个体目标函数中的每一个优化目标均归一化，具体由以下公式实现：Step 4-61a: the population to be optimized

Each optimization objective in all individual objective functions in is normalized, which is realized by the following formula:

F'(x _i )={f' ₁ (x _i ),f' ₂ (x _i ),...,f' _M (x _i )},i=1,2,...,Num,

中第i个个体归一化后的目标函数值，i的取值范围i＝1,2,…,Num，Num为种群规模，f'_k(x_i)为待优化种群

中第i个个体x_i中第k个归一化后的优化目标，具体计算方式如下：Among them, F'(x _i ) is the population to be optimized

The normalized objective function value of the i-th individual in the i, the value range of i is i=1,2,...,Num, where Num is the population size, and f' _k ( _xi ) is the population to be optimized

The k-th normalized optimization objective in the _i -th individual xi is as follows:

Among them, f _k ( _xi ) is the k-th optimization objective value in the objective function of x _i of the individual, the value range of k is k=1, 2,...,M, M is the number of optimization objectives, the value in this paper is M=5.

中任意两个不同个体间的影响距离，具体计算方式如下：Step 4-61b: Calculate the population to be optimized

The influence distance between any two different individuals is calculated as follows:

Among them, d( _xi , x _j ) is the influence distance between individual _xi and individual x _j , f' _k ( _xi ) is the k-th normalized optimization of the ith individual _xi in the population Goal, f' _k (x _j ) is the k-th normalized optimization goal of the j-th individual x _j in the population, and the value range of k is k=1, 2,...,M, where M is the optimization goal The number, in this paper, is M=5.

Step 4-61c: Calculate the Harmonic average distance of all individuals in the population. The specific calculation formula is as follows:

的个体数。Among them, Num is the population to be optimized

number of individuals.

的原点O_m，具体计算方式如下：Step 4-61d: Obtain the population to be optimized

The origin O _m of , the specific calculation method is as follows:

的规模，M为优化目标个数，取值M＝5。Among them, Num is the population to be optimized

The scale of , M is the number of optimization targets, and the value is M=5.

与原点O_m之间的欧氏距离H_eur，具体计算方式如下：Step 4-61e: Obtain the population to be optimized

The Euclidean distance H _eur from the origin O _m is calculated as follows:

中第i个个体与原点O_m之间的欧氏距离。Among them, _{He eur} (x _i ) represents the population to be optimized

The Euclidean distance between the ith individual in and the origin O _m .

中全部个体的拥挤度，具体计算方式如下：Step 4-61f: Calculate the population to be optimized

The crowding degree of all individuals in the calculation method is as follows:

C(x _i )=(1-H _Par )·H _eur (x _i )+H _Par ·H _arm (x _i ), i=1,2,...,Num,

中第i个个体的拥挤度，H_Par表示Pareto解集Ω的信息熵，H_eur(x_i)表示待优化种群

中第i个个体与原点O_m之间的欧氏距离，H_arm(x_i)表示待优化种群

中第i个个体的Harmonic平均距离，i的取值范围为i＝1,2,…,Num，Num为待优化种群

的个体数。Among them, C(x _i ) represents the population to be optimized

The crowding degree of the ith individual in , H _Par represents the information entropy of the Pareto solution set Ω, _{He eur} (x _i ) represents the population to be optimized

The Euclidean distance between the i-th individual and the origin O _m , H _arm (x _i ) represents the population to be optimized

The Harmonic average distance of the i-th individual in the i, the value range of i is i=1,2,...,Num, Num is the population to be optimized

number of individuals.

的排序等级平均信息熵H_re，并选择压力阈值进行比较。Step 4-62: Calculate the population to be optimized in Gray code form

The average information entropy H _re of the ranking rank, and the pressure threshold is selected for comparison.

Optionally, the steps 4-62 include:

进行非支配排序的结果，计算排序等级平均信息熵H_re，具体计算公式为：Step 4-62a: Optimize the population according to the treatment

The result of non-dominated sorting is used to calculate the average information entropy H _re of the sorting level. The specific calculation formula is:

Among them, Num represents the population size, Deg represents the total number of ranking levels of all individuals in the population, Deg is an integer and the value range is [1, Num], D _sum (r) represents the individuals included in the r-th ranking level in the population to be optimized The total number, r is an integer and the value range is [1,Deg].

的拥挤度C(x_i)生成交配池；或者，如果H_re小于等于选择压力阈值，则使用K支配排序结果与种群

的拥挤度C(x_i)生成交配池。If H _re is greater than the selection pressure threshold, use the non-dominated sorting result with the population

The crowding degree C(x _i ) of , generates the mating pool; or, if H _re is less than or equal to the selection pressure threshold, use K to dominate the sorting result and the population

The crowding degree C(x _i ) generates the mating pool.

计算B_t(x_i,x_j)、E_q(x_i,x_j)和W_s(x_i,x_j)集合，具体计算方式如下：Step 4-62b: in the population to be optimized

Calculate the sets of B _t ( _xi , x _j ), E _q ( _xi , x _j ) and W _s ( _xi , x _j ), and the specific calculation methods are as follows:

Among them, B _t ( _xi , x _j ) represents the number of objective function values that individual x _i is better than individual x _j in the M-dimensional target space, and E _q ( _xi , x _j ) represents the M-dimensional target space. The number of objective function values of individual x _i and individual x _j is the same, and W _s (x _i , x _j ) represents the number of objective function values of individual x _i inferior to individual x _j in the M-dimensional objective space.

Step 4-62c: Calculate the dominance relationship between the individual _xi and the individual x _j in the population. If the following relationship is satisfied between the individual _xi and the individual x _j , it is recorded as _xi < _K x _j , and the specific calculation method is as follows:

Among them, M is the number of optimization targets, K is the selection pressure, and G _G ( _xi ) represents the energy function value of the _ith individual xi, and its specific calculation method is as follows:

Step 4-62d: Calculate the K dominance level K _s ( _xi ) of the _i -th individual xi in the population, and the specific calculation method is as follows:

K _s (x _i )=|{x _j |x _j ＞ _K x _i ,j=1,2,…,Num,i≠j}|,i=1,2,…,Num

Step 4-63: Use the evolutionary algorithm based on non-dominated sorting to evolve the population to be optimized in the form of Gray code

Optionally, the steps 4-63 include:

Step 4-63a: Randomly select two parent individuals y1 _nt and y2 _nt in the nt group from the mating pool in the form of Gray code, and perform single-point crossover and single-point mutation on these two parent individuals to obtain the child. Generation individuals y1 _rt ' and y2 _nt ', nt=1, 2, ..., Num.

Step 4-63b: Repeat step 4-63a until nt=Num, and generate a descendant population PG _off ={y1 _nt ',nt=1,2,...,Num} whose scale is in the form of Num Gray code.

和子代种群P_off进行合并，得到整体种群，

Step 4-63c: Convert the coding mode of the offspring population PG _off in the form of Gray code from Gray code to binary code to obtain the offspring population P _off , and convert the current population

Merge with the offspring population P _off to obtain the overall population,

进行非支配排序，得到新种群

Step 4-63d: For the overall population

Perform non-dominated sorting to get a new population

Step 4-7: Analyze the number of iterations corresponding to the new population, and when the number of iterations corresponding to the new population is less than the preset number of iterations, determine the new population as a new population to be optimized, and repeat the steps Steps 4-2 to 4-7; or, when the number of iterations corresponding to the new population is equal to the preset number of iterations, the new population is determined as the optimal population.

The preset number of iterations is expressed as G _max , also known as the maximum evolutionary algebra, and the preset number of iterations is set by those skilled in the art according to business needs, which is not specifically limited in the present invention. The number of iterations corresponding to the new population is expressed as _Gene . When the number of iterations of the new population is equal to the maximum number of iterations, the iteration is terminated, and the new population at this time is determined as the optimal population.

Optionally, after the steps 4-6, the method further includes:

Step S1: Calculate the total number of deployed controllers C={C _i , i=1,2,...,Num} corresponding to the deployment scheme represented by all individuals in the new population, where C _i =sum(x _i ), i=1,2,...,Num;

Optionally, the step S1 includes:

中取出第i个个体，并计算该第i个个体所代表的部署方案需要的控制器总数C_i：Step S11: from the population to be optimized

Take out the i-th individual and calculate the total number of controllers C _i required by the deployment scheme represented by the i-th individual:

C _i =sum(x _i ), i=1,2,...,Num;

Step S12: Repeat step S11 until i=Num, to obtain the total number of controllers that need to be deployed in the deployment scheme represented by all individuals: C={C _i , i=1, 2, . . . , Num}.

Step S2: verifying the legitimacy of all individuals in the new population;

Compare the total number of controllers C that need to be deployed in the deployment scheme represented by all individuals with the number of Internet OS3E network nodes: if C is greater than half of the total number of Internet OS3E network nodes, it is determined as an illegal individual U, and the illegal individual U is determined. Make corrections, that is, execute step S3; or, if C is less than or equal to half of the total number of Internet OS3E network nodes, then judge the legitimacy of the next individual, and continue to execute step 5 until the legitimacy of all individuals is judged.

Step S3: When the individual is illegal, correct the individual.

Optionally, the step S3 includes:

Step S31: For the illegal individual U, calculate its disturbance parameter δ=1/C _i , and generate a random vector rand with a length of |N|, where the value of each locus is a random number between (0,1). , and the perturbation vector is generated by the following formula:

In the formula, i represents the random vector and the i-th locus of the disturbance vector, and Dis represents the disturbance vector generated according to the illegal individual U.

Step S32: Modify the individual according to the preset modification formula, which is expressed as:

Among them, U'(i) represents the i-th locus of the legal individual after correction, U(i) represents the i-th locus of the illegal individual, U(i)+Dis(i) represents the illegal individual U and the disturbance The sum of the ith locus of the vector Dis, when U(i)+Dis(i)=1, then U'(i)=1, that is, the controller should be placed in the network node corresponding to the ith locus, Otherwise, U'(i)=0, that is, no controller is placed in the network node corresponding to the i-th locus.

Step S33: Repeat steps S31 to S32 until the correction and correction of all loci U'(i) of all illegal individuals is completed, and the corrected legal individual U'={U'(i), i=1, 2, ... ,N}.

Step 5: Calculate the optimal solution set and the optimal controller placement scheme set according to the optimal population.

The optimal population is non-dominantly sorted, and the Pareto solution set corresponding to the optimal population is obtained. The Pareto solution set is the approximate optimal controller placement data information, also known as the optimal controller placement scheme set R.

To sum up, the beneficial effects of the present invention:

First, the present invention adaptively adjusts the calculation formula of the crowding degree according to the information entropy perception coefficient H _par , so that when the population to be optimized is selected, the population to be optimized with better convergence and distribution can be obtained. When the coefficient H _par is small, it means that the distribution of the population to be optimized is poor. Therefore, in the process of calculating the distribution of the population, the weight of the Harmonic average distance will increase, which helps to improve the distribution of the population; When the entropy perception coefficient H _par is large, it means that the distribution of the population to be optimized is excellent, which can promote the increase of the population convergence. Therefore, in the calculation process of the population distribution, the Euclidean distance between each individual and the origin O _m The weight will increase, which will help to improve the convergence of the population, which can promote the evolution of the population in a better direction, which is convenient to obtain higher control network performance, lower control network propagation delay, and more reasonable controller storage. A set of controller placement solutions for resource allocation, higher control network reliability, and lower controller placement costs.

排序等级平均信息熵值H_re较小，说明待优化种群

的选择压力较小，这说明精英个体不易从待优化种群中选出，因而使用K支配排序的方法提高种群内精英个体的选择压力，从而促使精英个体在交配池中聚集；而如果待优化种群

排序等级平均信息熵值H_re较大，说明待优化种群

的选择压力较大，这说明精英个体可以从待优化种群中选出，因而使用非支配排序的方法选择种群内的精英个体。Second, in the process of generating the mating pool, the present invention uses two sorting strategies according to the different selection pressures of the population to be optimized.

The average information entropy value H _re of the ranking level is small, indicating that the population to be optimized

The selection pressure of is small, which means that elite individuals are not easy to be selected from the population to be optimized. Therefore, the K-dominated sorting method is used to increase the selection pressure of elite individuals in the population, thereby promoting elite individuals to gather in the mating pool; and if the population to be optimized is

The average information entropy value H _re of the ranking level is relatively large, indicating that the population to be optimized is

The selection pressure of is relatively large, which means that elite individuals can be selected from the population to be optimized, so the non-dominated sorting method is used to select the elite individuals in the population.

Third, the present invention carefully selects five optimization objectives in the calculation of the optimization objectives, which are the deployment cost of the control network, the load difference of the controller, the propagation delay between the controller and the switching nodes, and the delay between the control nodes. Propagation delay, and reliability of the control network. These five optimization objectives are mutually restrained, and the five optimization objectives are optimized at the same time, so that the control network can achieve better performance indicators on different scales.

The beneficial effects of the present invention are further verified through simulation experiments:

1. Simulation conditions:

Condition 1: Set the population size of the decomposition-based multi-objective differential evolution algorithm MOEA/D Num=100, the maximum evolutionary generation G _max =100, the crossover probability P _c =0.9, and the mutation probability P _m =0.9;

Condition 2: The population size of the multi-objective evolutionary algorithm NSGA-II based on non-dominated sorting and elite selection strategy is Num=100, evolutionary generation _Gmax =100, crossover probability _Pc =0.9, mutation probability _Pm =0.9.

Simulation software: MATLAB software is used.

2. Simulation content:

Simulation 1, using the present invention to simulate the placement position of the multi-objective controller, solve the obtained approximate optimal controller placement scheme set R, and obtain the objective function value F ₁ of all placement schemes in the approximate optimal controller placement scheme set R in this simulation (x)={F(x _kt )}, the F ₁ (x) is a matrix.

Simulation 2, using condition 1, use the existing decomposition-based multi-objective differential evolution algorithm MOEA/D to simulate the placement position of the multi-objective controller, solve the approximate optimal controller placement scheme set R, and calculate all its placement schemes To optimize the target value F ₂ (x), the calculation steps are the same as those of Simulation 1. The calculated F ₂ (x) is a matrix.

Simulation 3, using Condition 2, use the existing multi-objective evolutionary algorithm NSGA-II based on non-dominated sorting and elite selection strategy to simulate the placement position of multi-objective controllers, solve the approximate optimal controller placement scheme set R, and calculate All of its placement schemes optimize the target value F ₃ (x), and its calculation steps are the same as in Simulation 1. The calculated F ₃ (x) is a matrix.

Input the optimization objective values F ₁ (x), F ₂ (x) and F ₃ (x) of the three placement schemes obtained by simulation 1, simulation 2 and simulation 3 into the MATLAB software, and draw in the MATLAB software to obtain this The comparison chart of the optimization target value of the approximate optimal controller placement scheme set R obtained by the invention and the existing two methods under Internet OS3E is shown in Figures 2 to 7.

It can be seen from Fig. 2 to Fig. 7 that, compared with the existing method, the optimized target value F ₁ (x) of the approximate optimal controller placement scheme set R obtained by this method is relatively better, that is, from five Three optimization objectives are arbitrarily selected from the optimization objectives, and the corresponding solution set is closer to the origin, which shows that the approximate optimal controller placement scheme set R obtained by this method can make the network have better performance, and it can control the deployment cost of the network, the controller and the controller. A better set of controller deployment schemes is obtained between the five optimization objectives of the load difference, the average propagation delay between the controller and the switching node, the average propagation delay between the controllers, and the reliability of the control network.

Referring to Fig. 2, it is the optimization target value comparison diagram of the obtained approximate optimal controller placement scheme set R under Internet OS3E with the present invention and the contrast method (the abscissa is the control network deployment cost, and the ordinate is the difference between the controller and the switching node. Average propagation delay, the vertical axis is the average propagation delay between controllers);

Referring to Fig. 3, it is the optimization target value comparison diagram of the obtained approximate optimal controller placement scheme set R under Internet OS3E with the present invention and the contrast method (the abscissa is the control network deployment cost, the ordinate is the load difference of the controller, and the ordinate is the load difference of the controller. is the average propagation delay between the controller and the switching node);

Referring to Fig. 4, it is the optimization target value comparison diagram of the obtained approximate optimal controller placement scheme set R under Internet OS3E with the present invention and the contrast method (the abscissa is the control network deployment cost, the ordinate is the load difference of the controller, and the ordinate is the load difference of the controller. is the average propagation delay between controllers);

Referring to Fig. 5, it is the optimization target value comparison diagram of the approximate optimal controller placement scheme set R obtained under Internet OS3E with the present invention and the contrast method (the abscissa is the load difference of the controller, and the ordinate is the difference between the controller and the switching node. The average propagation delay of , and the vertical axis is the average propagation delay between controllers);

Referring to Fig. 6, it is the optimization target value comparison diagram of the approximate optimal controller placement scheme set R obtained by the present invention and the comparison method under Internet OS3E (the abscissa is the average propagation delay between the controllers, and the ordinate is the control network deployment. cost, the vertical axis is the unreliability of the control network);

Referring to Fig. 7, it is the optimization target value comparison diagram of the obtained approximate optimal controller placement scheme set R under Internet OS3E with the present invention and the contrast method (the abscissa is the load difference of the controllers, and the ordinate is the average spread between the controllers. delay, the vertical axis is the unreliability of the control network).

In the description of the present invention, "plurality" means two or more, unless otherwise expressly and specifically defined.

In the description of this specification, description with reference to the terms "one embodiment," "some embodiments," "example," "specific example," or "some examples", etc., mean specific features described in connection with the embodiment or example , structure, material or feature is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the particular features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, those skilled in the art may combine and combine the different embodiments or examples described in this specification.

Although the application is described herein in conjunction with the various embodiments, those skilled in the art will understand and understand from a review of the drawings, the disclosure, and the appended claims in practicing the claimed application. Other variations of the disclosed embodiments are implemented. In the claims, the word "comprising" does not exclude other components or steps, and "a" or "an" does not exclude a plurality. A single processor or other unit may fulfill the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that these measures cannot be combined to advantage.

It should be understood by those skilled in the art that the embodiments of the present application may be provided as a method, an apparatus (apparatus), or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects, all of which are collectively referred to herein as a "module" or "system." Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein. The computer program is stored/distributed in a suitable medium, provided with or as part of other hardware, or may take other forms of distribution, such as over the Internet or other wired or wireless telecommunication systems.

The present application is described with reference to the flowcharts and/or block diagrams of the methods, apparatuses (devices) and computer program products of the embodiments of the present application. It will be understood that each flow and/or block in the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flow of the flowcharts and/or the block or blocks of the block diagrams.

These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

The above content is a further detailed description of the present invention in conjunction with specific preferred embodiments, and it cannot be assumed that the specific implementation of the present invention is limited to these descriptions. For ordinary technical personnel in the technical fields of the invention, under the premise of not being separated from the concept of the invention, a number of simple deductions or replacements can also be made, which should be deemed to be the protection of the present invention.

Claims (5)

1. A placement method of a super multi-target controller based on information entropy perception is characterized by comprising the following steps:

step 1: initializing network information and configuration information corresponding to a wide area network, wherein the network information comprises: network node longitude information lambda _i Network node latitude information

Network topology node quantity information | N |, network topology link quantity information | E |, information entropy grid quantity a _i I =1,2, \ 8230;, 5, direct link source node information A _i And direct link sink node information O _i Wherein i is 1,2, \8230 |, N |, reliability r of ith node in network _i ^node Wherein i is 1,2, \8230 |, N |, the reliability r of the ith link in the network _i ^edge Wherein, i is 1,2, \8230 |, | E |; the configuration information includes: population scale information Num, controller number upper limit information maxCNum, evolution perception threshold information tau and deployment cost of controllers

The controller manages the costs incurred by the switch nodes to which it belongs

Cost incurred by newly building a control link

Weight psi to control link cost and maximum evolution algebraic information G _max ；

And 2, step: acquiring topology link length information corresponding to the wide area network;

and step 3: obtaining an initial population;

and 4, step 4: according to preset maximum evolution algebraic information G _max Performing iterative optimization processing on the initial population to obtain an optimal population;

and 5: calculating to obtain an optimal solution set and an optimal controller placement scheme set according to the optimal population;

the step 3 comprises the following steps:

step 3-1: randomly generating an integer according to the controller quantity upper limit information maxNum, wherein the integer is in the range of [1,maxNum]The integer is used as the controller number C of the ith individual _num (i)；

Step 3-2: obtaining the ith random vector R of length | N | _v (i) And sorting the random vectors from large to small to obtain R _v1 (i) Wherein the value of each position in the random vector is a random number between (0, 1), R _v1 (i) Middle C _num (i) Number is initial population threshold epsilon _i ；

Step 3-3: r is to be _v (i) Modifying the number of the initial population smaller than the threshold value epsilon i into 0, and modifying the number of the initial population larger than or equal to epsilon i into 1 to obtain the ith initial individual;

step 3-4: repeating the steps 3-1 to 3-3 until i = Num, and obtaining an initial population P ₀ ；

The step 4 comprises the following steps:

step 4-1: determining a population to be optimized

Step 4-2: calculating objective function values corresponding to all individuals in the population to be optimized;

step 4-3: performing non-dominated sorting on the population to be optimized to obtain the priority to be optimizedPareto optimal solution set omega corresponding to the chemical population, total number Deg of all individual ranking levels and population to be optimized

Total number of individuals D in the r-th ranking level _sum (r), wherein r =1,2, \8230;

step 4-4: calculating information entropy perception coefficient H _par ；

And 4-5: converting the coding mode of the population to be optimized from binary coding to Gray code to obtain the population to be optimized in the form of Gray code

And 4-6: for the population to be optimized in the form of Gray codes

Optimizing to obtain a new population;

and 4-7: analyzing the iteration times corresponding to the new population, determining the new population as a new population to be optimized when the iteration times corresponding to the new population are smaller than the preset iteration times, and repeatedly executing the steps 4-2 to 4-7; or when the iteration times corresponding to the new population are equal to the preset iteration times, determining the new population as an optimal population;

the step 4-2 comprises the following steps:

step 4-21: sequentially from the population to be optimized

In the order of small to large, the ith individual x is selected _i I =1,2, \ 8230;. Num, which allocates the switching nodes to the controller nodes according to the principle that the switching nodes are controlled by the nearest controller, and obtains the deployment number m of the controllers of the individual and the number k of the controllers of the ith node _i I =1,2, \8230 |, the ith controller controls the number w of the switching nodes _i I =1,2, \ 8230, m, node i deploy controllers and intersectBoolean variable c whether the switch that switches node j is controlled by the controller of node i _ij I, j =1,2, \8230 |, | N |, whether the ith node in the network deploys the Boolean variable h of the controller _i I =1,2, \8230 |, whether or not | N |, i-th network link is located in the Boolean variable in the control network zone of the jth controller

i =1,2, \8230 |, | E |, j =1,2, \8230 |, | N |, whether or not the ith switching node is located in the Boolean variable of the control network region of the jth controller

i，j＝1，2，…，|N|；

And 4-22: calculating population to be optimized

Of (i) th individual x _i I =1,2, \8230;, num, expressed as:

wherein, F (x) _i ) Representing a population to be optimized

Of (i) th individual x _i An objective function of f ₁ (x _i ) Representing a population to be optimized

Of (ii) the ith individual x _i Controller deployment cost of f ₂ (x _i ) Representing a population to be optimized

Of (i) th individual x _i Load difference of f ₃ (x _i ) Representing a population to be optimized

Of (i) th individual x _i Controlling the average propagation delay between the controller and the switching node in the network, f ₄ (x _i ) Representing a population to be optimized

Of (ii) the ith individual x _i Controlling the average propagation delay between controllers in the network, f ₅ (x _i ) Representing a population to be optimized

Of (ii) the ith individual x _i The unreliability of the control network of (c);

and 4-23: repeating the steps 4-11 to 4-12 until the objective function values of all individuals in the population to be optimized are calculated;

the step 4-4 comprises the following steps:

step 4-41: normalizing each optimization objective in all individual objective functions in the pareto optimal solution set omega by:

F'(x _i )＝{f' ₁ (x _i ),f' ₂ (x _i ),…,f' _M (x _i )},i＝1,2,…,|Ω|，

wherein, F' (x) _i ) The value range of i is i =1,2, \ 8230 |, | Ω |, | Ω | is the number of individuals of the pareto optimal solution set Ω, M is the optimal target number, and M =5,f' _k (x _i ) For the ith individual x in the pareto optimal solution set omega _i The k-th normalized optimization objective in (1) is expressed as:

wherein f is _k (x _i ) Is x of an individual _i The k-th optimization target value in the objective function has the value range of k =1,2, \ 8230, M and M are the number of optimization targets (M = 5);

and 4-42: calculating the influence distance between any two different individuals in the pareto optimal solution set omega in the following specific calculation mode:

wherein, d (x) _i ,x _j ) Is an individual x _i And individual x _j Of (c) influence distance, f' _k (x _i ) Is the ith individual x in the population _i K th normalized optimization target of (1)' _k (x _j ) Is the j th individual x in the population _j In the kth normalized optimization target, the value range of k is k =1,2, \8230, and M are the number of the optimization targets;

and 4-43: calculating the Gaussian influence function value between any two different individuals in the pareto optimal solution set omega in the following specific calculation mode:

wherein, d (x) _i ,x _j ) Is an individual x _i And individual x _j The influence distance between the two groups is sigma which is the standard deviation of the distribution degree, pi is the circumferential rate, and the value ranges of i and j are i ≠ j, i, j =1,2, \ 8230 |;

and 4-44: calculating the density value of each individual in the population in the following specific calculation mode:

the density value of a single individual is the sum of the influence function values of all non-dominant individuals in the target space on the individual, and if the scale of the pareto optimal solution set in the target space is | Ω |, the jth individual x _j Density value of (c):

wherein D is _m (x _j ) The method comprises the steps of representing the density value of the jth individual in a population, wherein the value range of j is j =1,2, \8230, | omega | represents the pareto optimal solution set of the population in a target space, and the scale of the pareto optimal solution set is | omega |;

step 4-45: dividing the target space into a ₁ ×a ₂ ×a ₃ ×a ₄ ×a ₅ The grids are calculated, and the number | omega of the individuals in each grid of the pareto optimal solution set is counted _ijkbd Wherein i, j, k, b, d have a value in the range of i =1,2, \8230;, a ₁ ，j＝1,2,…,a ₂ ，k＝1,2,…,a ₃ ，b＝1,2,…,a ₄ ，d＝1,2,…,a ₅ ；

And 4-46: calculating the sum D of the density values of all the individuals in each grid of the target space in the pareto optimal solution set _ijkbd The specific calculation method is as follows:

and 4-47: calculating a density function of the pareto optimal solution set in a specific calculation mode as follows:

where ρ is _ijkbd The density function values i, j, k, b, d representing the optimal solution set of pareto in the ijkbd grid space have values in the range i =1,2, \ 8230;, a ₁ ，j＝1,2,…,a ₂ ，k＝1,2,…,a ₃ ，b＝1,2,…,a ₄ ，d＝1,2,…,a ₅ ；

And 4-48: calculating the information entropy of the pareto optimal solution set in the following specific calculation mode:

wherein H _Par Information entropy of a pareto optimal solution set omega is obtained;

the steps 4-6 comprise:

step 4-61: computing populations

Degree of congestion C (x) _i )；

And 4-62: calculating a population to be optimized in the form of gray codes

Rank average information entropy of H _re Selecting a pressure threshold value for comparison;

and 4-63: evolution of a population to be optimized in the form of Gray codes using an evolutionary algorithm based on non-dominated sorting

2. The method of claim 1, wherein step 2 comprises:

step 2-1: based on the network information, calculating the length of a topological link corresponding to the wide area network, and expressing as:

wherein R is _earth Representing the radius of the earth, by a value R _earth ＝6400km，

Represents the ith source node A _i The longitude of (a) is determined,

represents the ith source node A _i The latitude of (a) is determined,

represents the ith sink node O _i The longitude of (a) is determined,

represents the ith sink node O _i Latitude, L (A) _i ,O _i ) Represents the ith source node A _i And the ith sink node O _i The length of the direct link between the two links, i is 1,2, \ 8230 |, | N |;

step 2-2: and calculating the shortest-circuit information between any two nodes in the topology corresponding to the wide area network according to a preset shortest-circuit calculation rule.

3. The method of claim 1, wherein after the steps 4-6, the method further comprises:

step S1: calculating the total number C of deployed controllers corresponding to the deployment scheme represented by all individuals in the new population = { C = { C = } _i I =1,2, \8230;, num }, wherein C _i ＝sum(x _i )，i＝1,2,…,Num；

Step S2: verifying the legality of all individuals in the new population;

and step S3: when an individual is illegal, the individual is corrected.

4. The method according to claim 3, wherein the step S1 comprises:

step S11: from the population to be optimized

The ith individual is taken out, and the total controller number C required by the deployment scheme represented by the ith individual is calculated _i ：

C _i ＝sum(x _i )，i＝1,2,…,Num；

Step S12: repeating the step S11 until i = Num, and obtaining the total number of controllers which need to be deployed in the deployment scheme represented by all individuals: c = { C _i ，i＝1,2,…,Num}。

5. The method according to claim 3, wherein the step S3 comprises:

step S31: for the illegal individual U, calculating the disturbance parameter delta =1/C _i And generating a random vector rand of length | N |, in which the value of each locus is a random number between (0, 1), and generating a perturbation vector by the following formula:

wherein i represents the ith gene position of the random vector and the disturbance vector, and Dis represents the disturbance vector generated according to the illegal individual U;

step S32: and correcting the individuals according to a preset modification formula, wherein the formula is as follows:

wherein, U ' (i) represents the i-th gene position of the corrected legal individual, U (i) represents the i-th gene position of the illegal individual, U (i) + Dis (i) represents the sum of the U of the illegal individual and the i-th gene position of the disturbance vector Dis, when U (i) + Dis (i) =1, then U ' (i) =1, i.e. the controller is to be placed at the network node corresponding to the i-th gene position, otherwise, U ' (i) =0, i.e. the controller is not to be placed at the network node corresponding to the i-th gene position;

step S33: and repeating the steps S31 to S32 until the correction of all the gene positions U ' (i) of all the illegal individuals is completed, and obtaining the corrected legal individuals U ' = { U ' (i), i =1,2, \ 8230;, N }.

Images