Search

CN-122027006-A - Dynamic region segmentation-based load balancing routing method, system and medium

CN122027006ACN 122027006 ACN122027006 ACN 122027006ACN-122027006-A

Abstract

The invention relates to a load balancing routing method, a system and a medium based on dynamic region segmentation, wherein the method operates on a double time scale and comprises a dynamic region segmentation stage with a long time slot scale and a mixed routing stage with a short time slot scale; in the hybrid routing stage, the head node of the current cluster selects the next hop cluster for the data stream according to the real-time geographic position and the load state of the neighbor cluster in a distributed mode, and the head node of the current cluster constructs a low-load routing path in the cluster for the data stream based on a residual topology method in a centralized mode so as to realize the maximization of the throughput of the system. The invention realizes the load balancing route of the data transmission flow of the large-scale satellite network, and improves the load balancing effect of the whole network and the reliability of the transmission flow.

Inventors

  • LUO JINGJING
  • CHEN AO
  • HUANG JUNTAO

Assignees

  • 哈尔滨工业大学(深圳)(哈尔滨工业大学深圳科技创新研究院)

Dates

Publication Date
20260512
Application Date
20260413

Claims (10)

  1. 1. A dynamic region segmentation based load balancing routing method, wherein the method operates on a dual time scale, comprising a long time slot scale dynamic region segmentation phase and a short time slot scale hybrid routing phase, the method comprising the steps of: step S10, in the dynamic region segmentation stage, based on a dynamic region segmentation algorithm, the cluster attribution of the satellite nodes is dynamically adjusted according to the real-time load and the historical flow information of the satellite nodes; step S20, in the hybrid routing stage, selecting a next hop cluster for the data stream according to the real-time geographic position and the load state of the neighbor cluster in a distributed mode by the head node of the current cluster; Step S30, constructing a low-load routing path inside the cluster for the data stream based on a residual topology method by the head node of the current cluster in a centralized manner to achieve the maximization of the system throughput.
  2. 2. The dynamic region segmentation based load balancing routing method according to claim 1, wherein the step S10 is preceded by: Step S00, constructing an LEO giant constellation network model, a traffic and load model, a satellite communication model and an optimization problem about a low-load routing path, wherein the step S00 comprises the following steps of: step S01, using Representing the constellation of LEO satellites, Representing the total number of satellites in the constellation, Representing the number of tracks in a constellation, all tracks having the same track height And track inclination angle And The satellites are uniformly distributed in On the surface of the rail, the track is provided with a plurality of grooves, For determining the phase difference between corresponding satellites in adjacent orbital planes as an orbital phase factor, the phase deviation between satellites in adjacent orbits is recorded as In the constellation, the satellite set is marked as Each satellite can establish ISL with four adjacent satellites, including two inter-plane ISLs and two intra-plane ISLs; The method of double time scale is adopted to divide time slot, firstly, the whole running period is divided into Discrete time slots Forming a long time scale, completing the change of satellite and cluster topology, Representing a set of time slots, after which each time slot is assembled Further subdivided into The equally spaced small time slots are denoted as Forming short time scale to complete relay forwarding of traffic, so that the satellite constellation topology is used The representation, wherein, For time slots In the inner part, the topology of the satellite constellation, For a set of satellite nodes, For time slots Inner satellite link set and in time slot Inner satellite And satellite For links established between A representation; step S02, modeling satellite clusters, wherein the satellite cluster set is recorded as , For time slots Number of inner clusters, clusters In time slot The number of the inner satellite nodes Representation, definition of binary variables Representing the mapping relationship of the satellites and the clusters, Is shown in time slot Inner satellite Located in a cluster In, otherwise Cluster(s) Is used for topology of (a) The representation, wherein, Representing time slots Inner satellite cluster Is used for the topology of the (a), Is shown in time slot In, cluster Is provided with a set of satellite nodes, Is shown in time slot In, cluster Is a satellite link set; step S03, modeling the ground area by dividing the ground covered by the satellite into Each area is defined according to longitude and latitude to form a ground area set, which is recorded as Setting a uniform ground station in the center of each ground area, selecting the satellite closest to the ground station as access point, uploading the traffic in the area to the satellite network via the satellite or downloading the traffic, assuming that the satellite can communicate with the ground station in the area when the satellite is above a certain ground area, defining binary variables Representing the relationship between the ground area and the satellites, Is shown in time slot In the ground area Selecting satellites As an access satellite, otherwise 。
  3. 3. The method according to claim 2, wherein the data stream is generated as a basic unit of transmission, has a specific statistical characteristic with respect to the transmission process, is completely generated by the ground station, and takes another ground station as a final transmission destination, and the step of constructing the traffic and load model in step S00 comprises: At each minislot In the ground area Flow rate generated Obeying parameters of Poisson distribution of (c): (1) Wherein, the Representing the poisson distribution function, Is a natural constant which is used for the production of the high-temperature-resistant ceramic material, Representing a ground area Taking into account historical traffic data as a reference factor for adaptive cluster changes, defining traffic metrics in terms of mathematical models by first defining the time slot at the current time Each small time slot in (a) Inner satellite The accessed flow is as follows: (2) Wherein, the Representing a ground area In small time slots The flow rate generated in the internal part of the valve, Representing a ground area And satellite Whether or not to connect in time slots Satellite The forwarded traffic is: Thus, in time slots The total flow through each satellite is: (3) Wherein, the And Respectively represent satellites In small time slots Traffic for internal access and traffic for forwarding, defined in time slots The total flow successfully forwarded by each satellite is that And the time slot is calculated by the formula (4) Inner satellite Is of the load degree of (2) : (4) Wherein, the Representing the sum of the total traffic of all satellite loads in the same time slot, Is shown in time slot Inner flow through satellite Is a total flow of (1); Introduction of discount factors Appropriate discounting of satellite loading in historical time slots is performed to calculate the current time slot In the method, the discounted weight of each satellite and each cluster reduces the influence of satellite loads far from the current time slot on cluster change, and satellite loads close to the current time slot have larger influence on cluster change, and the satellite loads are in the time slot Inner satellite Discount weights of (2) The method comprises the following steps: (5) Wherein the method comprises the steps of Representing a history of time slots, Representing historical time slots Is used for the load of the load-dependent weight coefficient, Representing historical time slots Inner satellite Normalized load level of (1) cluster Discount weights of (2) Obtained by summing the discounted weights of all satellites within it: (6) Wherein, the Is shown in time slot Inner satellite Discount weights of (c).
  4. 4. The dynamic region segmentation based load balancing routing method according to claim 3, wherein the step of constructing a satellite communication model in step S00 comprises: describing the position of a satellite using a spherical coordinate system, the satellite Is expressed as coordinates of Wherein For the earth's altitude, As a satellite orbit height, the satellite orbit height, And Satellites respectively Based on these coordinates, satellites And satellite In time slot Distance of Europe inside Calculated by the formula (7): (7) assuming that additive white gaussian noise is present and the wireless channel is symmetric, then the link Free space path loss of (2) Expressed as: (8) Wherein the method comprises the steps of Representing the carrier wavelength(s), Representing satellites And satellite In time slot The Euclidean distance in the link, and the information transmission rate of the link according to the Shannon theorem Calculated by a formula (9); (9) Wherein, the Representing the transmitting power, wherein the unit is W; And Antenna gains for the receive antenna and the transmit antenna, respectively; Is the boltzmann constant; representing the channel bandwidth in MHz; Is the thermal noise temperature, in K, A logarithmic function with a base of 2 is shown, Is shown in time slot Inward link Free space path loss of (a); Thereafter, a data stream is established Path model of (d), data stream Is written as: wherein For data flow Is provided with a source satellite node of (a), For data flow Is provided with a plurality of satellite nodes for the purpose, Is a group of satellite pairs which establish inter-satellite links and meets ; Finally, establishing a data stream In the time delay model of the transmission in the satellite network, three main time delays are considered, namely the transmission time delay and the propagation time delay generated when the data stream is transmitted on a link and the queuing time delay generated by the queuing processing of the data stream on the satellite, wherein the three main time delays are the time delay in the time slot Inner minislots In, data flow On the link The transmission delay and the propagation delay are calculated by the formula (10) and the formula (11) respectively: (10) (11) Wherein, the The speed of light is indicated as being the speed of light, Is shown in time slot Inward link Is used for the distance of (a), Indicating the size of each data stream, Is shown in time slot Inward link Information transmission rate of (2) in small time slots In, data stream In satellite The queuing delay is defined as Representing a data stream Defining the transmission queue capacity of each satellite as At each small time slot Inner satellite The occupied capacity of the transmission queue of (2) is recorded as The transmission of the data stream follows the first-in first-out principle, if the satellite No other data stream waiting for transmission in the transmission queue of (a) then the data stream Can be transmitted from the queue, otherwise, if there are other data streams waiting in the queue, it must be at the satellite Continues waiting until it becomes the next pending item in the queue, data flow From satellite Forwarding to adjacent satellites Is of (2) Given by equation (12): (12) Wherein, the And Respectively expressed in small time slots In, data stream On the link The transmission delay and the propagation delay on the antenna, Indicated in a small time slot In, data stream In satellite Queuing delay on the data stream End-to-end delay of (i.e. along its transmission path) Can be expressed as: (13) Further, setting the end-to-end time delay threshold as Data flow Must be satisfied when forwarding of (a) Is carried out under the condition of (2).
  5. 5. The dynamic region segmentation based load balancing routing method according to claim 4, wherein the step of constructing an optimization problem for the low load routing path in step S00 comprises: System throughput employing end-to-end successful delivery rate As a measure, the measure can be calculated by the formula (14): (14) Wherein, the Indicated in a small time slot The data stream successfully transmitted in the internal network, Indicated in a small time slot Inner satellite The optimization problem can be expressed as: (15) Wherein, the For an end-to-end successful delivery rate, Representing a data stream Is provided with a routing path for the routing path, Is a time slot Inner satellite And cluster Is used for the mapping relation binary decision variable of the (a), Defining the relationship between satellites and clusters, i.e. for any one satellite Any one satellite cluster , Is shown in time slot Inner satellite Located in a cluster In, otherwise ; The representation being for any one satellite At any time slot In which only one satellite cluster can be located In, ensure that at each time slot Each satellite is assigned to only one cluster; the representation being for any one satellite cluster At any time slot The number of satellites contained in the system must be greater than 1, ensuring that in each time slot At least one satellite exists in each cluster, so that the effectiveness of the satellite clusters is ensured; Restrictions on the capacity of the satellite transmission queues ensure that at any time slot Inner minislots Any one of the satellites Traffic carried by a transmit queue of (c) Cannot exceed the capacity of the transmission queue ; Limiting the end-to-end transmission delay of a data stream, meaning at any time slot Inner minislots In, data flow End-to-end delay of (c) Cannot exceed a given delay threshold Ensure that the data stream can be transmitted within a designated time, optimize the problem The method is divided into two sub-problems, namely, a cluster dynamic segmentation optimization problem on a long scale Load balancing routing problem on a short time scale : (16) (17) Wherein, the Is shown in time slot Inner cluster Is used to determine the discount weight of the (c), In time slot Inner cluster The number of the inner satellites is set, Is shown in time slot Inner satellite Successfully forwarded traffic.
  6. 6. The dynamic region segmentation based load balancing routing method according to claim 5, wherein the step S10 comprises: Step S101, using satellite cluster set Representing alliance partitioning policies for clusters according to alliance game theory There are three indicators: 1) Benefit of Quantifying the value of the alliance, an , Representing an empty set of satellites, for a satellite cluster The benefit is defined as: (18) Wherein, the Is shown in time slot Inner cluster Is used to determine the discount weight of the (c), In time slot Inner cluster The number of the inner satellites is set, Is shown in time slot Inner satellite Successfully forwarded traffic; 2) Cost of (C) The cost for quantifying collaboration is defined as follows: (19) There is no penalty when the cluster partition satisfies two hard constraints simultaneously (1) I.e. single satellite single cluster attribution constraint, wherein For time slots An inner set of satellite clusters is provided, Is a time slot Inner satellite And cluster Binary decision variables of the affiliation of (2) I.e. cluster non-null constraint, in which The method is a whole network satellite node set, otherwise, the cost is positive infinity; 3) Value of The difference between the revenue obtained from the collaboration and the cost of the collaboration is quantified, and the index is calculated according to equation (20): (20) step S102, defining a satellite set for cluster switching By any satellite node And in the same cluster Adjacent satellites in the space are formed; step S103, defining a possible switching operation For satellite sets From the original cluster Switching to a new cluster The process of (1), namely: (21) Wherein, if the satellite is assembled Switching to Indicating that the satellite set establishes a new satellite cluster, resulting in an increase in the number of clusters in the network, if the satellite set Is a cluster An internal unique satellite set, after the switching operation, the cluster Merge into a cluster Leading to a reduced number of clusters in the network; step S104, defining and executing a switching operation Switching gain that can be brought about The method comprises the following steps: (22) Wherein the method comprises the steps of And Representing satellite sets, respectively Removing clusters Front and back clusters Is of value (1); And Representing satellite sets, respectively Entering a cluster Front and back clusters Is of value (1); If satellite collection And simultaneously, a plurality of executable switching operations are provided, and the operation with the highest switching gain is selected to be executed, wherein the switching preference is defined as follows: (23) I.e. if switching operation Is higher than the switching gain of Is indicative of a switching operation Ratio of The priority is high; Initially, at cluster Inner satellite Together with adjacent satellites in the same cluster to form a satellite set Subsequently, for satellite collection Adjacent clusters of (a) Searching if the cluster With satellite collection A link connection exists between them, they are considered to be adjacent; establishing a handover operation for these neighboring clusters And calculating corresponding switching gain if the switching gain is Is a finite positive real number, then the switching operation is deemed valid and the switching operation is then performed Joining to a candidate operation set In, when candidate operation set Non-space time, select cluster with highest switching gain As a set of satellites New attribution in cluster And cluster Satellite set without switching operation in progress The cluster switch of (a) will be performed, otherwise the switch operation will be discarded, at each time slot Initially, clusters in the network will be dynamically partitioned, and this process continues until no positive gain switching operation is found for He Juyou.
  7. 7. The dynamic region segmentation based load balancing routing method according to claim 6, wherein the step S20 comprises: When data flow Entering a current cluster When the cluster The control node of the system is responsible for searching the exit node in the cluster for the data stream, and the data stream enters the current cluster in two ways, namely, the data stream is uploaded to the current cluster from the ground station through an access satellite, the data stream is forwarded to the entry node of the current cluster from an adjacent cluster, and the control node judges the data stream Destination node of (a) Whether or not to locate in a cluster Inner, if the destination node Belonging to a cluster Then node Is set as a data stream In the cluster In (a) an egress node of (b) If the destination node Not in cluster In the method, the control node needs to execute a routing algorithm among clusters, and the control node is from the current cluster Neighbor cluster set of (a) In selecting a next hop cluster for a data stream And determines that the cluster is currently in Inside exit node Ingress nodes within a next hop cluster Furthermore, data flow The current position is a cluster Is defined by the entry node of (a) ; In selecting the next hop cluster, a weight-based inter-cluster routing index is first calculated according to equation (24) The index combines load and distance factors: (24) Wherein, the Representing a current cluster Neighbor clusters of (a) To destination cluster The normalized distance is obtained by dividing the actual distance by Dividing by clusters All neighbor clusters To destination cluster Maximum distance of (2) To obtain the product, Indicated in a small time slot Inner satellite The size of the traffic carried by the transmit queue of (c), Transmission queue capacity for each satellite; The cluster load balancing factor and the distance weight factor are respectively represented as weight coefficients, and the cluster with the minimum route index is screened out from the neighbor clusters The cluster will act as a data stream And finally, if the cluster is the next hop cluster And cluster With multiple link connections between them, then selected such that The shortest link serves as the transmission link between the clusters, Representing a data stream From satellite nodes Transmitted to satellite nodes Single-hop transmission delay of (a) node Will be the data stream In the cluster Internal egress node, node Then as a data stream In the cluster An ingress node within.
  8. 8. The dynamic region segmentation based load balancing routing method according to claim 7, wherein the step S30 comprises: step S301, network state sensing and residual topology construction, namely dynamically constructing a current cluster based on a real-time load state Specifically, the method comprises setting the maximum load factor of the satellite as , At the current small time slot In, for clusters Each satellite node within If it transmits the queue load Then satellite is taken And ISL slave clusters directly connected with the same After that, evaluating connectivity of the cluster topology, if the topology is found to be not connected, setting the load of the satellite as an impossible upper limit And rejoin it to the cluster Thereby obtaining a cluster in the topology of (a) In small time slots Is a residual topology of (2); Step S302, candidate path generation, namely applying a depth-first traversal algorithm on residual topology to find slave nodes To the node All candidate route paths are ordered according to the ascending order of the hop count, and are defined For data flow In the cluster A set of routing paths in ascending order of hop count, And For data flow In the cluster Internal transmission of the first And Setting the threshold value of the number of routing paths in the cluster as If the number of paths exceeds Only the front with low route similarity and few hops is reserved The method for calculating the route similarity comprises the steps of setting a route similarity threshold as If the path with fewer hops is used And path Common edge count of (2) The ratio of the number of sides exceeds I.e. (25) The similarity of the two paths is considered to be too high, and paths with more hops should be discarded Wherein Representing satellite pairs in any one candidate path; step S303, path preferred decision, namely establishing a comprehensive utility index in the cluster to plan the final transmission route in the cluster aiming at the candidate route path set, and defining Characterizing each path within a cluster Comprehensive utility values in two dimensions of load degree and transmission delay; The calculation can be performed by the following formula: (26) Wherein, the Representing candidate paths The number of satellite nodes that pass through, Representing candidate paths Through links ; And Respectively data streams In the cluster The maximum path load and the longest path delay among all paths in the network, The load balance factor and the time delay weight factor in the cluster are respectively represented as weight coefficients, the dimension difference is eliminated through normalization processing, the index comparability is ensured, and finally, the method is selected Minimal path as data stream In the cluster Final routing path within.
  9. 9. A dynamic region segmentation based load balancing routing system, characterized in that the system comprises a memory, a processor and a dynamic region segmentation based load balancing routing program stored on the processor, which when run by the processor performs the steps of the method according to any of claims 1 to 8.
  10. 10. A computer readable storage medium, characterized in that the computer readable storage medium stores a dynamic region segmentation based load balancing routing program which when executed by a processor performs the steps of the method according to any of claims 1 to 8.

Description

Dynamic region segmentation-based load balancing routing method, system and medium Technical Field The invention relates to the technical field of satellite routing, in particular to a load balancing routing method, a system and a medium based on dynamic region segmentation for a huge constellation scene. Background In recent years, the continuous evolution and wide application of the fifth generation and sixth generation mobile communication technologies (5 th/6th Generation Mobile Communication Technology,5G/6G) significantly improves the transmission efficiency and service capability of the communication system, and further promotes the rapid increase of global mobile data traffic and the wide popularization of diversified access services. To cope with the increasing communication demands, the terrestrial communication network has made remarkable progress in coverage, transmission rate, system capacity, and the like. However, due to geographical condition limitation, deployment cost and other factors, the ground network is difficult to realize global seamless coverage, which indicates that the ground network cannot independently meet the communication requirements of future ubiquity, high reliability and multi-service integration. In this context, satellite communication networks are an indispensable component in 5G Non-terrestrial network (Non-TERRESTRIAL NETWORK, NTN) architecture by virtue of their wide area coverage, flexible networking, and Non-regional limitations. Particularly, in special scenes such as remote areas, aviation routes, ocean areas and the like where ground infrastructure is difficult to cover, satellite communication plays a vital role, and plays a key role in the evolution and construction of a sixth generation mobile communication system in the future. Currently, in view of the characteristics inherent in Low Earth Orbit (LEO) satellites, designing a set of high-performance routing algorithms for a huge LEO satellite network is facing a series of core challenges to be solved. The primary challenge arises from the scalability problem that arises from the expansion of network sizes. Specifically, as the satellite constellation scale continues to expand, the number of spatial nodes increases exponentially, and the category of the huge constellation network evolves, for example, the constellation scale planned by Starlink systems is up to tens of thousands of satellite levels. The abrupt expansion of node scale directly leads to a significant increase in the complexity of routing computation and causes a significant increase in the control signaling overhead, which makes the traditional fully centralized routing management strategy face a great difficulty in practical deployment. When the global routing algorithm designed for the small-scale satellite constellation is applied to such a huge network, the calculation complexity is increased sharply, the overall network overhead is increased remarkably, and meanwhile, the effective allocation of the distributed satellite resources in the constellation is difficult to realize, so that the resource utilization rate is reduced. Second, the high dynamic characteristics exhibited by giant LEO satellite constellation networks pose serious challenges for transmission stability of the inter-satellite link (INTER SATELLITE LINK, ISL) and reliable delivery of end-to-end data traffic. With the increasing number of satellite nodes in the constellation, the relative positions between the nodes in the high-speed motion state and the inter-satellite link distance are in continuous and frequent changes, and the dynamic changes further cause the satellite network topology connection relationship to present continuous and rapid change characteristics and present remarkable dynamic instability. This high degree of dynamics essentially requires that the routing algorithm must have the ability to quickly perceive changes in network topology and be able to dynamically optimize the data transmission path in an adaptive manner, thereby maintaining continuity of network service and operational stability of the system as a whole. And thirdly, due to the fact that significant space-time difference exists in service flow demands among different geographic areas in the global scope, the traffic load in the satellite network is directly caused to be in a highly non-uniform distribution situation, so that congestion phenomenon is easy to occur on part of key nodes and core links in the network, the probability of losing data flow is finally raised, and quality experience of various user services is seriously affected. LEO satellite networks are intended to provide access services to subscribers worldwide, however, the inherent imbalance in global traffic distribution results in data traffic carried over satellite links also exhibiting non-uniform spatial distribution characteristics. The unbalanced flow distribution mode is extremely easy to cause local congestion of