CN118055063A - Semi-distributed route search algorithm suitable for satellite-ground network - Google Patents

Abstract

The present invention relates to a semi-distributed routing search algorithm suitable for satellite-to-ground networks, comprising the following steps: detecting the on-off status of a satellite temporary link; selecting a first-hop node and constructing a minimum-hop-count grid; establishing a priority evaluation mechanism and evaluating the next two-hop nodes according to the priority evaluation mechanism; updating the current node position and performing the next round of pathfinding until reaching a receiving terminal. The present invention greatly improves the communication quality while greatly reducing the transmission distance of communication tasks through temporary links, and quickly searches for suitable communication routes for a large number of communication tasks while ensuring end-to-end delay and network load balancing.

Description

A semi-distributed routing search algorithm for satellite-to-ground networks

Technical Field

The present invention relates to the field of routing search algorithms, and in particular to a distributed routing search algorithm suitable for satellite-to-ground networks.

Background technique

In real life, there are a lot of communication needs at all times, and these communication tasks need to be transmitted to a specific receiving end through a huge satellite communication network. Due to the significant difference between satellite transmission and ground transmission, satellite transmission adopts different routing schemes. According to different decision-making methods, satellite routing is divided into centralized routing, distributed routing and hybrid routing. Distributed routing does not rely on the central controller, and the routing decision is dispersed to each satellite node. Each satellite node obtains link status information and network topology through information exchange with surrounding satellite nodes, finds the minimum grid for data packet transmission, and the routing of the data packet is searched in the minimum grid.

Common methods for route search include heuristic algorithms such as A* and simulated annealing. Due to the lack of global information of the entire network, distributed routing may fall into a local optimal solution, and the resulting route is not globally optimal, resulting in a waste of resources. At the same time, the design of distributed routing does not take into account the temporary links of satellites, because the communication status judgment of temporary links requires frequent information exchange between satellites to perceive changes in the local network, which will increase the communication control overhead.

Summary of the invention

In view of this, the present invention provides a semi-distributed routing search algorithm suitable for satellite-to-ground networks, which greatly reduces the transmission distance of communication tasks and greatly improves the communication quality by considering temporary links at the first-hop node of the routing.

To achieve the above object, the present invention provides a semi-distributed routing search applicable to a satellite-to-ground network, characterized in that the semi-distributed routing search comprises the following steps:

S1. Detect the on/off status of the satellite temporary link;

S2, select the first hop node and build a minimum hop grid;

S3. Establish a priority evaluation mechanism and evaluate the next two hop nodes according to the priority evaluation mechanism;

S4: Update the current node position and perform the next round of path finding until the receiving terminal is reached.

Preferably, the on/off detection method of the satellite temporary link is: establishing a visibility list at the current moment according to the link on/off schedule stored on the satellite, obtaining the visible satellite node numbers, and a stable communication link can be formed between the visible satellites at the current moment.

Preferably, the first hop node is selected by traversing all selectable first hop nodes, taking the first hop node as the starting point, establishing a minimum hop number grid according to the characteristics of the satellite-to-ground network mesh topology structure, selecting the smallest grid, and using its starting node as the first hop node.

Preferably, the minimum hop network is constructed by using a virtual topology method to model a real satellite network or a topology diagram of a static mesh structure at discrete time points, and the minimum grid area constructed in the mesh topology according to the starting point and the end point is the minimum hop network.

Preferably, the priority evaluation mechanism is: to examine two-hop nodes to expand the diversion field of view and weaken the local optimal problem, to use link load and node load to construct a priority evaluation function for auxiliary node selection, and to measure the link congestion status and node transmission capacity by comprehensively evaluating the transmission pressure of the link and the utilization of time and frequency resources on the satellite.

Preferably, the link load is: the number of resource blocks being transmitted and waiting to be transmitted on the satellite-to-ground link; the link congestion state is evaluated by a congestion judgment threshold set according to the link load and the average link load, and the link congestion state can be regarded as a weighted coefficient of the node load; the node load is: the proportion of the remaining satellite time-frequency resources to the total time-frequency resources within a period of time

The beneficial effects of the present invention are:

(1) When the present invention converts the dynamic topology into static topology, it not only stores the permanent links in the satellite network, but also considers the temporary links in the satellite network; the temporary links increase the size of the solution space and provide a communication task transmission route with less overhead.

(2) The present invention expands the scope of load balancing to two hops, determines dynamic routing nodes in units of two hops in the minimum hop grid, weakens the local optimal problem of distributed routing, and achieves better algorithm effects under the premise of slightly increasing communication overhead.

(3) The present invention uses node load and link load to construct a priority evaluation function for auxiliary node selection, and measures the link congestion status and node transmission capacity by comprehensively evaluating the transmission pressure of the link and the utilization of time and frequency resources on the satellite.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a process framework of the present invention;

FIG2 is a diagram of the satellite-to-ground network topology in the present invention;

FIG3 is a comparison chart of communication effect evaluation indicators in the present invention;

FIG. 4 is a diagram showing specific numerical values of communication indicators in the present invention.

Detailed ways

In order to further explain the technical means and effects adopted by the present invention to achieve the predetermined invention purpose, the specific implementation mode, structure, characteristics and effects of the present invention are described in detail below in combination with the accompanying drawings and preferred embodiments.

This embodiment discloses a semi-distributed routing search algorithm applicable to a satellite-to-ground network. The semi-distributed routing search includes the following steps:

S1. Detect the on/off status of the satellite temporary link;

S2, select the first hop node and build a minimum hop grid;

S3. Establish a priority evaluation mechanism and evaluate the next two hop nodes according to the priority evaluation mechanism;

S4: Update the current node position and perform the next round of path finding until the receiving terminal is reached.

The on/off detection method of the satellite temporary link is: establish a visibility list at the current moment according to the link on/off schedule stored on the satellite, obtain the visible satellite node number, and visibility indicates that a stable communication link can be formed between the two satellites at the current moment.

The method of selecting the first hop node is: traverse all the selectable first hop nodes, take the first hop node as the starting point, establish a minimum hop number grid according to the characteristics of the satellite-ground network mesh topology, select the smallest grid, and use its starting node as the first hop node.

The method of constructing the minimum hop network is: using a virtual topology method, modeling the real satellite network into a static mesh topology at discrete time points, and the minimum grid area constructed in the mesh topology according to the starting point and the end point is the minimum hop network.

The priority evaluation mechanism is as follows: two-hop nodes are examined to expand the diversion vision and weaken the local optimal problem, link load and node load are used to construct the priority evaluation function for auxiliary node selection, and the link congestion status and node transmission capacity are measured by comprehensively evaluating the transmission pressure of the link and the utilization of time and frequency resources on the satellite.

The link load is the number of resource blocks being transmitted and waiting to be transmitted on the satellite-to-ground link. The link congestion state is evaluated by setting a congestion judgment threshold based on the link load and the average link load. The link congestion state can be regarded as a weighted coefficient of the node load.

Node load is the ratio of remaining satellite time and frequency resources to total time and frequency resources over a period of time.

As shown in Figure 1, the specific steps of the present invention are as follows:

(1) Determine whether the first hop node adopts a temporary link node; if the temporary link can reduce the minimum number of hops required for resource block transmission, then the temporary link node is adopted to execute step (2); otherwise, step (3) is executed.

(2) Based on the temporary link nodes and the target node, construct a minimum hop count grid and go to step (4).

(3) Based on the starting node and the target node, construct a minimum hop network and go to step (4).

(4) Determine whether the current node has reached the boundary of the minimum hop count grid. If yes, go to step (7); otherwise, go to step (5).

(5) Determine four alternative routes in units of two hops in the minimum hop grid, add the priorities of the nodes contained in the alternative routes using the priority evaluation mechanism proposed in the present invention to obtain the priorities of the alternative routes, and add the nodes in the alternative routes with the highest priority to the dynamic routes.

(6) Update the current node and determine whether the dynamic route has reached the target node. If it has, end the algorithm; otherwise, go to step (4).

(7) Determine the transmission direction of the resource block on the minimum grid boundary, and add the grid boundary points one by one to the dynamic routing until the target node is reached, and the algorithm ends.

As shown in the specific satellite-to-ground network topology diagram in Figure 2, each node (x, y) has four permanent links that can be connected. The thin solid lines shown in Figure 2 correspond to the communication with the four nodes (x-1, y), (x+1, y), (x, y-1) and (x, y+1), respectively. In addition, temporary links will be generated. The generation of temporary links is due to the fact that when satellites moving in three-dimensional space approach each other, a short period of time for communication will be generated. As shown by the dotted line with an arrow in Figure 2, a temporary link can be considered at the starting satellite, and the link can be calculated by the link on-off schedule. The dotted rectangle in Figure 2 is the minimum hop grid generated by different starting nodes. It can be seen that the smaller the grid, the fewer hops the communication route has. The first hop node is determined based on the minimum hop grid. The grid constructed by the (4, 2) node in Figure 2 has only two hops, so this node is selected as the starting node.

The satellite-to-ground network simulation uses the algorithm proposed in the present invention and the Dijkstra algorithm as the routing search algorithms for the communication tasks. The simulation scenario is run continuously. The comparison results of the communication indicators of the two algorithms after stabilization are shown in FIG3 .

As shown in Figure 4, the algorithm proposed by the present invention is superior to the comparison algorithm in terms of the six indicators of queuing delay, transmission delay, total delay, packet loss rate, data delivery rate and transmission overhead ratio. In terms of total delay, the algorithm proposed by the present invention is 30.7% lower than the Dijkstra algorithm. Specifically, the reduction in delay is mainly reflected in the reduction of queuing delay, which has decreased by 59.2%, while the transmission delay is basically the same, indicating that the algorithm proposed by the present invention has a better load distribution effect under the premise of keeping the number of routing hops unchanged.

The packet loss rate of the algorithm proposed in the present invention is almost 0, and the data delivery rate is the highest, which is 6.0% higher than the Dijkstra algorithm, and the transmission overhead is reduced by 44.5%. From the three indicators of packet loss rate, data delivery rate and transmission overhead, the routing search algorithm proposed in the present invention can quickly realize the transmission of communication tasks, greatly reduce the number of communication tasks in the network, and improve the stability of the network.

From the comparative experimental results, it can be seen that the routing search algorithm proposed in the present invention can quickly search for a suitable route for a communication task in a satellite-to-ground network, and has a fast calculation speed, achieves load balancing, and has the best network communication effect.

The above description is only a preferred embodiment of the present invention and does not limit the present invention in any form. Although the present invention has been disclosed as a preferred embodiment as above, it is not used to limit the present invention. Any technical personnel in this field can make some changes or modify the technical contents disclosed above into equivalent embodiments without departing from the scope of the technical solution of the present invention. However, any brief modifications, equivalent changes and modifications made to the above embodiments based on the technical essence of the present invention without departing from the content of the technical solution of the present invention are still within the scope of the technical solution of the present invention.

Claims (6)

1. A semi-distributed route search algorithm suitable for a star-to-ground network, wherein the semi-distributed route search comprises the steps of:

s1, detecting the on-off condition of a satellite temporary link;

s2, selecting a first hop node to construct a minimum hop count grid;

s3, establishing a priority evaluation mechanism, and evaluating the next two-hop node according to the priority evaluation mechanism;

and S4, updating the current node position, and carrying out next round of route searching until the current node position reaches the receiving terminal.

2. The semi-distributed route search algorithm applicable to the satellite-to-ground network according to claim 1, wherein the on-off detection mode of the satellite temporary link is as follows: and establishing a visibility list at the current moment according to a link on-off time table stored on the satellite, and acquiring the number of the visible satellite node.

3. The semi-distributed route search algorithm for a star-to-ground network of claim 1, wherein the first hop node is selected by: traversing all the selectable first hop nodes, taking the first hop nodes as starting points, establishing a minimum hop count grid according to the characteristics of a mesh topological structure of the star network, selecting the minimum grid, and taking the starting nodes as the first hop nodes.

4. A semi-distributed route search algorithm applicable to a star-to-ground network according to claim 3, characterized in that the minimum hop count network is constructed in the following manner: and modeling a real satellite network into a topological graph of a static mesh structure at discrete time points by adopting a virtual topology method, and constructing a minimum mesh area in the mesh topology according to a starting point and an ending point, namely the minimum hop count network.

5. The semi-distributed route search algorithm for a star-to-ground network of claim 1, wherein the priority evaluation mechanism is: and (3) examining two-hop nodes to expand the split view and weaken the local optimal problem, and constructing a priority evaluation function for auxiliary node selection by using the link load and the node load.

6. The semi-distributed route search algorithm for a star-to-ground network of claim 5 wherein said link load is: the number of resource blocks being transmitted and waiting for transmission on the satellite-to-ground link; evaluating the congestion state of the link through a congestion judgment threshold value set according to the link load and the average link load; the node load is: the satellite remaining time-frequency resources are proportional to the total time-frequency resources over a period of time.