Search

CN-121984859-A - Service function chain optimization deployment method and system suitable for full-dynamic unmanned aerial vehicle network

CN121984859ACN 121984859 ACN121984859 ACN 121984859ACN-121984859-A

Abstract

The invention discloses a service function chain optimizing deployment method suitable for a full-dynamic unmanned aerial vehicle network, which mainly solves the problems of unbalanced network resource distribution and low SFC deployment success rate in the prior art. The method comprises the steps of determining an initial position of the unmanned aerial vehicle, constructing a network topology according to the unmanned aerial vehicle, the user position and the communication capacity, solving an SFC deployment problem on the current network topology, iteratively solving the maximum request acceptance number, calculating resource tension of each unmanned aerial vehicle node according to the dual variables, calculating virtual force born by each unmanned aerial vehicle based on the network topology, the resource tension and a request set refused due to insufficient coverage and updating the unmanned aerial vehicle position, and repeatedly executing the network topology construction, the SFC deployment solution and the position update until convergence conditions are met, and outputting the maximum SFC request acceptance number, the optimal unmanned aerial vehicle position and the SFC deployment scheme. The invention can effectively improve the balance of network resource distribution, improve the SFC request acceptance rate, and can be used for unmanned aerial vehicle network service deployment in the scenes of emergency communication, post-disaster rescue and the like.

Inventors

  • MA YINGHONG
  • LIU TANGWEN
  • DONG XU
  • JIAO YI
  • LIU WEI
  • LI HONGYAN
  • LIU QIN

Assignees

  • 西安电子科技大学

Dates

Publication Date
20260505
Application Date
20260116

Claims (11)

  1. 1. The service function chain optimizing deployment method for the full-dynamic unmanned aerial vehicle network is characterized by comprising the following steps of: (1) Determining an initial position of an Unmanned Aerial Vehicle (UAV) according to user distribution, and constructing a network topology according to the UAV position, the user position and the communication capability Wherein For a set of nodes, including UAV nodes and user nodes, The UAV communication link and the user access link are included as a link set; (2) Using network topology On the premise of meeting node resource constraint and link bandwidth constraint, generating a candidate service path set for each service function chain SFC request, maximizing the request acceptance number and outputting resource tension Request set denied due to insufficient coverage ; (3) Based on network topology Resource tension Request set denied due to insufficient coverage Calculating virtual force born by each UAV and updating the position of the UAV ; (4) Repeatedly executing network topology construction, SFC deployment solution and position update until convergence conditions are met, outputting maximum request acceptance number and optimal UAV position configuration A corresponding SFC deployment scheme.
  2. 2. The method of claim 1, wherein the network topology is constructed in accordance with UAV location, user location, and communications capabilities in (1) The implementation includes: 1a) Distributed by users As input, will Individual users are clustered into The mass center of each cluster is used as an initial horizontal coordinate of a corresponding UAV to obtain UAV position configuration: Wherein Is the first The position coordinates of the individual users are used, , Is the first The horizontal coordinates of the individual UAVs, The flying height of all UAVs is fixed as ; 1B) Defining node sets Wherein For a set of UAV nodes, Represent the first A UAV node; for a set of user nodes, Represent the first A plurality of user nodes; 1c) Defining a set of inter-UAV communication links Wherein Is a UAV node And (3) with Communication link between two UAVs when the distance between them is such that And is also provided with The time-link exists in the presence of a time-link, Is the maximum communication distance; 1d) Defining a set of user access links Wherein Is a user node With UAV node Access link between user and UAV when the distance between user and UAV is satisfied The time-link exists in the presence of a time-link, A coverage radius for the UAV; 1e) By a collection of communication links And user access link set Constructing a link set ; 1F) By node sets And link set Constructing a network topology 。
  3. 3. The method of claim 1, wherein the network topology is used in (2) On the premise of meeting node resource constraint and link bandwidth constraint, generating a candidate service path set for each service function chain SFC request, wherein the implementation comprises the following steps: 2a) According to the source user Demand for flow Delay tolerance And a virtual network function VNF sequence defining an SFC request: , Wherein the method comprises the steps of , Is the first The first SFC request The number of VNFs is one, For the length of the chain, ; 2B) Representing service paths as triplets : , Wherein, the A sequence of nodes is deployed for the VNF, Is the first Deployment nodes of the VNFs; For a sequence of routing paths, Is the first A segment routing path; Is an access node; 2c) According to the source user Selecting a location from a source user location Recently and satisfy Is used as an access node , Adding the request to a set of requests rejected due to insufficient coverage if there is no UAV node satisfying the condition ; 2D) From an access node Initially, a deployment node is selected for each VNF in turn, i.e. the node with the most abundant remaining resources is selected from the neighbors of the current node as deployment node ; 2E) Calculating routing paths between adjacent deployment nodes by adopting shortest path algorithm ; 2F) According to the service path Calculating end-to-end delay of service path And will satisfy the delay constraint Is added to the candidate path set Is a kind of medium.
  4. 4. The method of claim 1, wherein the maximizing SFC request acceptance number in (2), The realization includes: 2g) Definition of the first embodiment Individual SFC requests Is the first of (2) The computational resource requirements of the VNFs are The storage resource requirement is According to the service path The resource consumption was calculated and expressed as follows: , , , Wherein, the 、 、 Respectively the service paths Opposite node Computing resource consumption, storage resource consumption and links of (a) Is used to control the bandwidth consumption of the (c) device, Is the first The deployment node of the VNF, Is the first The path of the segment is routed over the path, In order for the flow to be required, Is the chain length; taking a value of 1 when the condition is met, or taking a value of 0 when the condition is met; 2h) With maximized SFC request acceptance number as an objective function, with service path selection variable For decision variables, in the current candidate path set The above constructs a constraint master problem containing service uniqueness constraints and resource capacity constraints, which is expressed as follows: , , , , , Wherein, the For the total number of SFC requests, To request Is a set of current candidate paths of (c), 、 Respectively nodes Is a computing resource capacity and a storage resource capacity of (1), For a link Bandwidth capacity constraint of (2) Representing that at most one service path is selected per SFC request, constraint To constraint of Respectively representing that the computing resource, the storage resource and the bandwidth consumption of each link of each node do not exceed the capacity; 2i) Relaxing integer constraints to Solving the relaxation problem by adopting a linear programming solver to obtain the current solution and the dual variable Wherein 、 、 The method comprises the steps of respectively calculating dual variables corresponding to resource constraint, storage resource constraint and bandwidth constraint; 2j) Constructing a pricing sub-problem for each SFC request based on the dual variables, targeting a maximum number of tests, expressed as: , , Wherein, the For serving paths Is used for the verification of the number of the test pieces, 、 、 Respectively the service paths Opposite node Computing resource consumption, storage resource consumption and links of (a) Is used to control the bandwidth consumption of the (c) device, For a set of UAV nodes, As a set of links, For serving paths Is provided with an end-to-end delay, For SFC request Is tolerant of delay of (a); 2k) Solving the pricing sub-problem by adopting a dynamic programming algorithm, and judging whether the pricing sub-problem finds a check number Is a service path of (a); if found, add it to the candidate set Returning to 2 i) continuing iteration; if not, the iteration is terminated, and 2m is executed); 2 m) converting the linear relaxation solution into an integer solution, resulting in a maximum SFC request acceptance number.
  5. 5. The method of claim 1, wherein the output resource tension in (2) Request set denied due to insufficient coverage The following are respectively indicated: , , Wherein, the To normalize the computing resource dual variables, For a set of UAV nodes, To calculate the corresponding dual variables of the resource constraint, Is a small positive number; To normalize the storage resource dual variables, To store the corresponding dual variables of the resource constraint, Is a node The normalized bandwidth resource dual variable of the associated link, The corresponding dual variables of the bandwidth constraint, Is a node The set of links that are connected together, 、 、 Respectively calculating weight coefficients of resources, storage resources and bandwidth; As source user Is provided in the position of (a), Is the first The location of the individual UAVs, Is the coverage radius of the UAV.
  6. 6. The method of claim 4, wherein the 2 k) solves a pricing sub-problem using a dynamic programming algorithm, the implementation comprising: 2k1) Defining states of dynamic programming Its value is service function chain SFC request First, the The virtual network function VNF is located at a node The accumulated time delay is Minimum resource occupation cost at the time; 2k2) According to resource tension For ascending arrangement of UAV nodes of all unmanned aerial vehicles, only the lowest stress degree is reserved Individual nodes form a candidate set ; 2K3) According to dual variables Respectively calculating node costs And link cost : , , Wherein, the And Respectively the first The computational and storage resource requirements of the VNFs, Is the flow demand; 2k4) Based on candidate set Cost of node And link cost The state of dynamic programming is calculated according to the following formula And (3) performing state transition: , Wherein, the For the slave UAV node To UAV node Is a transmission delay of (1); 2k5) In satisfying the time delay constraint Selecting the least costly state from among the end states of (a) Counting the number of tests : , Wherein, the For SFC request Is used for the chain length of the steel wire, And Respectively a termination node and an accumulated time delay corresponding to the minimum cost state, Is tolerant to time delay; 2k6) When the check number satisfies When the service path is traced back from the termination state to the state transition path, a corresponding service path is obtained 。
  7. 7. The method of claim 4, wherein the 2 m) converting the linear relaxation solution to an integer solution results in a maximum SFC request acceptance number, the implementation comprising: 2m 1) define initialization iteration times The maximum iteration number is A convergence threshold of And will be dual variable An initial value as a Lagrangian multiplier; 2m 2) for each SFC request According to the first The Lagrangian multiplier of the multiple iterations calculates each candidate service path thereof Is to correct the income of : , Wherein, the 、 、 Lagrangian multipliers corresponding to the computational resource constraints, the storage resource constraints and the bandwidth constraints respectively, 、 、 Respectively the service paths Opposite node Computing resource consumption, storage resource consumption and links of (a) Is used to control the bandwidth consumption of the (c) device, For a set of UAV nodes, Is a link set; 2m 3) updating Lagrangian multiplier by sub-gradient method according to the first The multiplier of the iteration is calculated to obtain the first Lagrangian multiplier for multiple iterations : , , , Wherein, the 、 、 Respectively the first The computational resources, storage resources and Lagrangian multipliers corresponding to bandwidth constraints of the multiple iterations, Is the first The step size of the number of iterations, A variable is selected for the service path and, 、 、 Respectively the service paths Opposite node Computing resource consumption, storage resource consumption and links of (a) Is used to control the bandwidth consumption of the (c) device, 、 Respectively nodes Is a computing resource capacity and a storage resource capacity of (1), For a link Is defined by the ratio of the bandwidth capacity of (a), The total number of SFC requests; 2m 4) calculating the multiplier change amount And judging whether the convergence condition is satisfied or not: If it is Or (b) Outputting the maximum SFC request acceptance number; otherwise, let Returning to 2m 2) continues the iteration.
  8. 8. The method of claim 1, wherein the step (3) is based on network topology Resource tension Request set denied due to insufficient coverage Calculating virtual forces to which each UAV is subjected, and updating the UAV position, wherein the method comprises the following steps: 3a) According to network topology Resource tension Set of rejected requests Respectively calculating UAV nodes of unmanned aerial vehicle Is of even attraction of (1) Suction force of covering Repulsive force of safety distance Boundary constraint force : , , , , Wherein, the To traverse and remove All of the UAV nodes outside of the network, For UAV node Is used for the resource shortage of (1), For the distance decay factor of the dual attractive force, For UAVs Is provided in the position of (a), For UAVs Is provided in the position of (a), In order to cover the distance decay factor of the attractive force, Is the source user location; Is UAV (unmanned aerial vehicle) And (3) with The repulsive force of the safety distance between the two, For the minimum safe distance between the UAVs, Is the repulsive force gain coefficient; for UAV node The x component of the boundary constraint force, For UAV node Is used for the x-coordinate of (c), As the x-direction boundary of the coverage area, For the boundary-affected zone of interest, A boundary penalty coefficient; for UAV node The y-component of the boundary constraint force, For UAV node Is used for the purpose of the (c), Is the y-direction boundary of the coverage area; 3b) Calculating the total virtual force to which each UAV is subjected according to the result of 3 a): , Wherein, the Is a node The total virtual force to which the force is applied; 3c) The UAV position is updated based on the total virtual force exerted by the UAV, and the updating formula is as follows: ; ; Wherein, the For UAV node The momentum item before the update is used, For UAV node The momentum items after the update are updated, As the momentum coefficient of the magnetic field, In order to be a step size, To update the pre-UAV node Is used for the position vector of (a), For updated UAV node Is a position vector of (a).
  9. 9. The method of claim 1, wherein (4) repeatedly performing network topology construction, SFC deployment solution, and location update until convergence criteria are met, outputting a maximum request acceptance number, an optimal UAV location configuration And a corresponding SFC deployment scheme, the implementation of which comprises: 4a) Defining the number of outer layer iterations The maximum iteration number is A convergence threshold of ; 4B) Calculate the first Minor iterations Sum of all UAV position variables: And combine it with Comparison is performed: If it is Or (b) Outputting the maximum request acceptance number and the optimal UAV position configuration A corresponding SFC deployment scheme; Otherwise, executing 4 c); 4c) Based on current UAV position Performing 1 b) and 1 c) in (1) to build a network topology In the following Performing (2) solving SFC deployment scheme to obtain resource tension degree Request set denied due to insufficient coverage Performing (3) calculating virtual forces and updating UAV positions Order-making Returning to 4 b).
  10. 10. A service function chain optimized deployment system for a fully dynamic unmanned aerial vehicle network, comprising: an initialization module for distributing according to users Determining initial position configuration of UAV ; A network topology construction module for configuring according to the current UAV position Construction of network topology for user location and communication capability ; The SFC deployment solving module is used for generating a candidate service path set for each SFC request on the premise of meeting node resource constraint and link bandwidth constraint, maximizing the request acceptance number and outputting the maximum SFC request acceptance number and resource tension degree Request set denied due to insufficient coverage ; A location updating module for network topology Resource tension And denied request set Constructing a virtual force field model, and calculating the total virtual force born by each UAV Updating UAV position ; The iteration control module is used for repeatedly executing network topology construction, SFC deployment solution and position update until convergence conditions are met, outputting the maximum request acceptance number and optimal UAV position configuration A corresponding SFC deployment scheme.
  11. 11. The system of claim 10, wherein the SFC deployment solution module comprises: A candidate path generation sub-module for generating a candidate path according to the SFC request Generating a set of candidate service paths Comprising selecting an access node Selecting a deployment node for each VNF Calculating routing paths Adding service paths meeting delay constraint into a candidate path set, and adding requests of source users which are not in any coverage range of the UAV into a request set refused due to insufficient coverage ; A constraint main problem solving sub-module for constructing a constraint main problem containing service uniqueness constraint and resource capacity constraint by taking the maximized SFC request acceptance number as an objective function, and solving after relaxing the integer constraint to obtain a dual variable ; A pricing sub-problem solving sub-module for building based on dual variables to maximize the number of tests For pricing sub-problems of targets, dynamic programming is adopted to search for a check number Is a new service path of (a); an integer sub-module, which is used for converting the linear relaxation solution into an integer solution and outputting the maximum SFC request acceptance number; resource tension computation submodule for computing according to dual variables Computing resource tension of each UAV node 。

Description

Service function chain optimization deployment method and system suitable for full-dynamic unmanned aerial vehicle network Technical Field The invention belongs to the technical field of unmanned aerial vehicle network and network function virtualization, and particularly relates to a service function chain deployment method which can be used for communication tasks of post-disaster rescue, field/desert/ocean/border temporary coverage and the like which lack ground infrastructure. Background In communication task scenarios lacking ground infrastructure, such as post-disaster rescue, field/desert/ocean/border temporary coverage, how to quickly build a communication network and give it the ability to serve on demand is a critical issue. The unmanned aerial vehicle UAV is used as flight equipment with low cost and high maneuverability, can carry communication and quickly construct a low-altitude mobile network by calculating load, and provides strong network reconstruction capability for on-demand service by flexibly controlling and adjusting network topology through the position of the UAV. The service function chain SFC technology can arrange the virtual network function VNF in sequence according to service requirements, and provide end-to-end agile service customized according to requirements by relying on reasonable deployment of the VNF in a physical network. Therefore, the flexible deployment of SFC according to service requirements by using the unmanned aerial vehicle network is an advantageous scheme for solving the problems. However, in stark contrast to terrestrial networks, unmanned aerial vehicle networks have highly flexible topology reconfiguration capabilities. This brings a wide optimization space for the deployment of SFC on the one hand, but introduces a new challenge of the mutual coupling of UAV position decisions and SFC deployment decisions on the other hand. At present, aiming at the related problems related to position optimization and SFC deployment in an unmanned aerial vehicle network, domestic and foreign scholars have developed some research works, but the existing method can not effectively solve the coupling decision problem. Chen Ziyan in the "intelligent reconstruction research of service-oriented unmanned aerial vehicle network topology" paper, a topology reconstruction method based on a deep Q network DQN is provided for a network system composed of ground users and multiple UAVs. Firstly, calculating service time delay according to an air-to-ground and air-to-air channel model, then calculating energy consumption of the UAV, constructing an optimization problem with the aim of maximizing net income, finally modeling the problem as a Markov decision process, and outputting the flight action of the UAV through a DQN algorithm to realize dynamic reconstruction of network topology. However, in the method, since the VNF is deployed on each UAV in advance to form a fixed SFC structure, the network performance is optimized only by adjusting the UAV flight track, and the SFC deployment is not used as an optimization variable, so that joint solution of the UAV position optimization and the SFC deployment optimization cannot be realized. Patent document 202110452553.0 discloses a joint optimization method of an IRS-assisted unmanned aerial vehicle communication network, which comprises the steps of establishing joint optimization problems about UAV initial position deployment, UAV track optimization, UAV emission beam formation and IRS phase offset with the aim of maximizing the weighted sum rate of all users in the network, decomposing the joint optimization problems into two sub-problems, optimizing the UAV emission beam and the IRS phase offset by using an approximate linearity method and an iterative rank minimization method respectively, optimizing the initial position and track of the unmanned aerial vehicle by using an enhanced k-means method and a reinforcement learning algorithm, and performing iterative calculation according to the two sub-problems until convergence. According to the method, multivariable joint solution is realized through alternate optimization, and although the signal transmission quality of an unmanned aerial vehicle communication network can be improved, a service function chain is not deployed for a wireless signal enhancement scene facing a physical layer, two sub-problems in the alternate optimization framework are mutually independent, the position optimization sub-problem cannot perceive specific resource bottleneck information of a beam/phase optimization sub-problem, and only the objective function value is used for establishing a connection, so that a mechanism for transmitting structural feedback from an optimization result to position adjustment is lacking, and the coupling problem of UAV position optimization and SFC deployment optimization is difficult to solve. Disclosure of Invention The invention aims to overcome the defects in the prior a