CN-122001776-A - Resource-constrained network node deployment method based on convergent squirrel search algorithm

CN122001776ACN 122001776 ACN122001776 ACN 122001776ACN-122001776-A

Abstract

The invention discloses a resource-limited network node deployment method based on a convergent squirrel search algorithm, which aims at solving the problems of calculation divergence, infeasibility of deployment schemes due to hardware budget hyperbranched and low area coverage utility existing in large-scale network node deployment, and provides a convergent element heuristic algorithm (CSSA), which is obviously superior to the prior art in aspects of convergence stability, optimizing precision, calculation efficiency, parameter theory completeness and the like through a strict convergence parameter constraint and a local search mechanism, ensures that a high-quality node deployment scheme meeting engineering budget constraint is output in a limited calculation time, can effectively solve the difficult problems that the algorithm is easy to fall into local optimum and parameter selection blindness in large-scale network planning, and has higher theoretical significance and engineering application value.

Inventors

LIU FAN
LI QIANMU
CHEN LINA
WAN HONGYAN
XU XIN
WANG MIAOMIAO
GU YANG
LI CHUNQI
WANG YUE

Assignees

南京理工大学

Dates

Publication Date: 20260508
Application Date: 20260408

Claims (10)

1. The resource-constrained network node deployment method based on the convergent squirrel search algorithm is characterized by comprising the following steps of: s1, acquiring nodes of an area to be deployed, and modeling a problem of maximum coverage of budget; S2, solving the budget maximum coverage problem based on a convergent squirrel search algorithm to obtain an optimal node deployment scheme, and executing node deployment, wherein the method specifically comprises the following steps: s2.1, initializing an algorithm; S2.2, converting the position vector of the individual squirrel into a binary solution by using a Sigmoid mapping mechanism, wherein the binary solution represents a discrete state control instruction of a node, 0 represents that the node is not selected, and 1 represents that the node is selected; s2.3, taking the total effect of network coverage as fitness, and arranging individual squirrels in a population in a descending order according to fitness values, and dividing the individual squirrels into three types: ① Determining that the individual squirrels arranged in the 1 st row are globally optimal, and marking the individual squirrels as the individual squirrels positioned in the hickory tree; ② Determining that the squirrel individuals arranged from the 2 nd to the w are locally optimal, and marking the squirrel individuals as the squirrel individuals positioned in oaks, wherein w is a preset experience value; ③ Confirm the row from w+1 to w The squirrel individuals of the (2) are common individuals and marked as squirrel individuals positioned in common trees, wherein omega is the population scale; S2.4, updating and optimizing each type of squirrel individuals respectively, and carrying out local search operation on the updated and optimized squirrel individuals; s2.5, comparing fitness value of individual squirrel currently located in hickory Global optimum fitness value with history If (if) Order of principle And mark The corresponding binary solution is the current global optimal solution, otherwise Keeping unchanged, returning to S2.3, and reclassifying the individual squirrels until the set maximum iteration times are reached; s2.6, obtaining a position vector corresponding to the current global optimal solution, generating a specific geographic coordinate point according to the position vector, and executing node deployment.
2. The method according to claim 1, characterized in that after S2.4, before S2.5, the method further comprises seasonal monitoring and random reset, in particular: If the seasonal constants of all the squirrel individuals on the oak trees are smaller than the preset minimum seasonal constant, performing random reset based on the Lewy flight on part of the squirrel individuals on the ordinary tree so as to jump out of the local optimum.
3. The method according to claim 2, wherein the seasonal constant is calculated by: , Wherein, the The seasonal constant of individual a of squirrels located on oak is represented, Represents the value of the ith element in the binary solution corresponding to individual a of the squirrel on the oak, Representing an ith element value in a binary solution corresponding to a squirrel individual on a hickory tree, wherein m is the node number of an area to be deployed; the calculation formula of the preset minimum seasonal constant is as follows: , Wherein, the Representing the number of current iterations and, Is the maximum number of iterations.
4. The method of claim 2, wherein the random reset result based on the Lewy flight is: , Wherein, the Representing the random reset result of the individual squirrel on the ordinary tree; representing a dimension of Mantegna algorithm Is subjected to random search step length vectors obeying the Lev distribution; And Is two of The real number array of the dimension is characterized in that the element values of the corresponding positions of the real number array are distributed as the lower bound and the upper bound of the element values of the corresponding positions of the individual position vectors of the squirrel.
5. The method of claim 1, wherein S2.1 is an initialization algorithm parameter comprising population size, maximum number of iterations, glide constant, predator occurrence probability, and distance factor, and randomly generating an initial position vector for each individual squirrel representing a potential node deployment scenario.
6. The method of claim 1, wherein the converting the continuous position vector of the individual squirrels into a binary solution in S2.2 using a Sigmoid mapping mechanism comprises: position vector for individual i of squirrels Wherein Representing positions of nodes j in a node deployment scheme corresponding to individual i of the squirrel, j=1, 2,..m, m representing the number of nodes in the area to be deployed; respectively to Executing the sigmoid function and obtaining a corresponding binary solution based on the following formula : , In the formula, Representing the discrete state control instruction of the node j in the node deployment scheme corresponding to the individual i of the squirrel, Indicating that node j in the individual i squirrel's corresponding node deployment scheme is selected, Indicating that a node j in the deployment scheme of the corresponding node of the individual i of the squirrel is not selected; representing a sigmoid function, r represents a random real number in the (0, 1) interval.
7. The method of claim 1, wherein the updating and optimizing each individual class of squirrels in S2.4 comprises: ① For all the individual squirrels on the oak, a position update strategy is executed according to the occurrence probability of predators, so that the individual squirrels move towards the hickory, and the position update formula is as follows: , Wherein, the Is shown in A binary solution of individual a of the squirrel on the oak and being prepared to move toward the hickory is performed in a number of iterations, Is shown in Individual a of the squirrel on the oak in the next iteration and ready to move toward the hickory is now Binary solutions in the secondary iterations; Is shown in Binary solution of individual squirrels located on hickory at the time of iteration, The moving distance of the squirrel is shown, Is a random number in the interval 0,1, Indicating the probability of the occurrence of a predator, Is a glide constant; ② For all individual squirrels on a common tree, they were randomly split into two parts, wherein: A part of squirrel individuals execute a position updating strategy according to the occurrence probability of predators, so that the squirrel individuals move towards oaks, and the position updating formula is as follows: , Wherein, the Is a random number in the interval 0,1, Is shown in the first The binary solution of individual n of squirrels on a normal tree and moving to the oak is being prepared in a number of iterations, Is shown in the first Individual n of squirrels on the normal tree in the next iteration and ready to move to the oak are in Binary solutions in the secondary iterations; Is shown in Binary solutions of any individual squirrel on the oak in the iterations; and the other part of squirrel individuals execute a position updating strategy according to the occurrence probability of predators so as to move towards the hickory, wherein the position updating formula is as follows: , Wherein the method comprises the steps of Is a random number between 0 and 1, Is shown in the first A binary solution of individual n of the squirrel on the normal tree and moving toward the hickory is being prepared in a number of iterations, Is shown in the first The binary solution of individual n of the squirrel on the normal tree in the iteration and moving towards the hickory tree is being prepared.
8. The method of claim 1, wherein the performing a local search operation on the updated and optimized individual squirrels in S2.4 comprises: S2.4.1, traversing all unselected nodes in the current binary solution, and sequentially executing the following judgment: If the total cost of a selected new node of ① is not more than the set budget constraint and the total network coverage utility of the unselected node is larger than the total network coverage utility of the current binary solution ②, the discrete state control instruction of the unselected node is set to be 1, and the current binary solution is updated, otherwise, the current binary solution is maintained, wherein the calculation formula of the total cost is as follows: , Wherein, the Representing the new total cost of the unselected node j after it was selected, Representing the deployment cost of the unselected node j, Representing a set of nodes for which the discrete state control instruction is 1 in the current binary solution, Representing the deployment cost of node k; the calculation formula of the total utility of the new network coverage is as follows: , Wherein, the Representing the total utility of the new network coverage after the unselected nodes j are selected, Representing the set of monitoring targets covered by all selected nodes and monitoring targets that can be covered by unselected nodes j in the current binary solution, Representing a monitored target Utility value of (2); S2.4.2, for the nodes which are still not selected after the traversal of S2.4.1 is completed, calculating the marginal benefit density of the nodes relative to the current binary solution, and selecting the node corresponding to the maximum marginal benefit density as the best candidate node, wherein the calculation formula of the marginal benefit density is as follows: , Wherein, the Represents the set of monitoring targets that can be covered by node u that is still not selected after the traversal of S2.4.1 is completed and that are not covered by all selected nodes in the binary solution obtained by the S2.4.1, Representing a monitored target Is used to determine the utility value of (1), Representing nodes Is a deployment cost of (a); S2.4.3, replacing each selected node in the current binary solution by using the best candidate node in turn, calculating the replaced exchange cost and exchange utility, if the exchange cost is not more than the set budget constraint and the exchange utility is greater than the network coverage total utility of the current binary solution, enabling the discrete state control instruction of the best candidate node to be 1 and the discrete state control instruction of the replaced selected node to be 0, terminating the current traversal of the selected node, and returning S2.4.2 to reselect the best candidate node, otherwise, keeping the current binary solution, continuously attempting to replace the next selected node, and if the exchange does not occur after traversing all the selected nodes, terminating the local search, wherein the calculation formula of the exchange cost is as follows: , Wherein, the Representing the cost of the exchange and, As the total cost of the current binary solution, Representing best candidate nodes Is provided for the deployment costs of (a), Representing best candidate nodes Alternate selected nodes Is a deployment cost of (a); the calculation formula of the exchange utility is as follows: , Wherein, the Representing the effectiveness of the exchange, The total utility of network coverage representing the current binary solution, Representing a shutdown node The resulting loss of utility is that of, Indicated at the shutdown node On the premise of starting the best candidate node With marginal utility gain.
9. The method of claim 8, wherein the shutdown node Resulting loss of utility The calculation formula of (2) is as follows: , The closing node On the premise of starting the best candidate node Marginal utility gain The calculation formula of (2) is as follows: , Wherein, the Representing nodes Nodes that can be covered and are not currently being divided by the binary solution Outside the set of monitoring targets covered by any one of the selected nodes, Representing a monitored target Is used to determine the utility value of (1), Representing nodes Nodes that can be covered and are not currently being divided by the binary solution Outside the set of monitoring targets covered by any one of the selected nodes, Representing a monitored target Utility value of (2).
10. An electronic device, comprising: A memory for storing a computer program; A processor for implementing the steps of the method for deploying a resource-constrained network node based on a converged squirrel search algorithm as claimed in any one of claims 1-9 when said computer program is executed.

Description

Resource-constrained network node deployment method based on convergent squirrel search algorithm Technical Field The invention relates to the technical field of network planning and resource scheduling, in particular to a resource-restricted network node deployment method based on a convergent squirrel search algorithm. Background With the development of the internet of things, how to deploy monitoring nodes under a limited budget (e.g., funds, power) to cover a maximum area is a key engineering difficulty. The academia typically models such resource-constrained deployment problems as budget maximum coverage problems (Budgeted Maximum Coverage Problem, BMCP). BMCP are widely available in numerous industrial fields, such as supply chain networks, network monitoring point deployments, program distribution, and software defined networks. By being a unified model of the diversified tasks, BMCP lays a foundation for developing efficient algorithms for balancing effectiveness and feasibility. Since BMCP belongs to the NP-hard problem, along with the expansion of the problem scale, the calculation time of the precise algorithm (such as the branch-and-bound method) increases exponentially, and it is difficult to meet the actual application requirements. Existing meta-heuristic algorithms (such as genetic algorithm, standard squirrel search algorithm SSA, etc.) can give a feasible solution in a reasonable time, but have the following drawbacks: 1. Most algorithms rely on random search, which is not justified by the lack of theoretical convergence guarantee, to converge to global optimum. 2. The method is easy to trap in a search trap, and individuals are easy to be trapped at the boundary (upper or lower boundary) of a search space in the later period of iteration, so that population diversity is lost, and the method is trapped in local optimum. 3. Parameter selection is blind, namely key control parameters (such as movement step length) are usually selected empirically, and theoretical basis is lacked. Therefore, there is a need for an efficient optimization method with tight convergence demonstration that effectively circumvents search traps. Disclosure of Invention Aiming at the problems mentioned in the background art, the invention provides a resource-restricted network node deployment method based on a convergent squirrel search algorithm CSSA, the core of which is a convergent element heuristic algorithm based on a search mechanism of the Squirrel Search Algorithm (SSA) but with unique convergent characteristics. When the squirrel position is updated to promote meta heuristic search, a value range is designated for key parameters of the squirrel position, and strict theoretical analysis is provided to prove the capability of CSSA to converge to a globally optimal solution in a solution space. And a concept of a search trap is introduced to analyze the search track of the individual squirrel so as to predict the occurrence of the CSSA falling into the search boundary in the evolution process. The CSSA provided by the invention can escape from the search trap by selecting the proper parameter value determined by the trajectory analysis, and is superior to the existing most advanced algorithm in terms of effectiveness and efficiency in terms of BMCP. The technical scheme adopted by the invention is as follows in order to solve the technical problems: a resource-constrained network node deployment method based on a convergent squirrel search algorithm comprises the following steps: s1, acquiring nodes of an area to be deployed, and modeling a problem of maximum coverage of budget; S2, solving the budget maximum coverage problem based on a convergent squirrel search algorithm to obtain an optimal node deployment scheme, and executing node deployment, wherein the method specifically comprises the following steps: S2.1, initializing algorithm parameters, wherein the parameters comprise population scale, maximum iteration times, gliding constants, predators occurrence probability and moving distance factors, and randomly generating initial position vectors of each individual squirrel, and each individual squirrel in the population represents a potential node deployment scheme; S2.2, converting the position vector of the individual squirrel into a binary solution by using a Sigmoid mapping mechanism, wherein the binary solution represents a discrete state control instruction of a node, 0 represents that the node is not selected, and 1 represents that the node is selected; s2.3, taking the total effect of network coverage as fitness, and arranging individual squirrels in a population in a descending order according to fitness values, and dividing the individual squirrels into three types: ① Determining that the individual squirrels arranged in the 1 st row are globally optimal, and marking the individual squirrels as the individual squirrels positioned in the hickory tree; ② Determining that the squirrel individuals a