CN-122027537-A - Design method of agile clustering routing protocol for large-scale satellite constellation

CN122027537ACN 122027537 ACN122027537 ACN 122027537ACN-122027537-A

Abstract

The invention discloses a design method of an agile clustering routing protocol for a large-scale satellite constellation, which comprises the following steps of step 1, firstly, clustering nodes; step 2, after the nodes are clustered, starting neighbor discovery and route update; step 3, if the links in the cluster are disconnected, performing intra-cluster topology updating and route recalculation; in the process of updating the topology in the cluster, if a node leaves the cluster, the node carries out a node cluster program again; step 4, if the inter-cluster link is disconnected, performing inter-cluster topology updating and route recalculation; the invention has the following advantages: the existing clustering routing scheme is mostly designed aiming at the traditional WALKER constellation, and the inter-satellite link performance is assumed to be consistent, and the difference of factors such as different orbits, constellation topologies and the like in a satellite network is ignored.

Inventors

ZHANG JIAXIN
WANG GUOQUAN
XU SHAOXIANG
LI YAXUAN
ZHAO CHENYU
ZHANG XING
WANG WENBO

Assignees

北京邮电大学
雄安空天信息研究院

Dates

Publication Date: 20260512
Application Date: 20260129

Claims (6)

1. The design method of the agile clustering routing protocol for the large-scale satellite constellation is characterized by comprising the following steps of: Step 1, initially, firstly, entering a cluster by a node; Step 2, after the nodes are clustered, starting neighbor discovery and route update; Step 3, if the link in the cluster is disconnected, the topology in the cluster is updated and the route is recalculated; And step 4, if the inter-cluster link is disconnected, performing inter-cluster topology updating and route recalculation.
2. The method for designing agile clustering routing protocol for large-scale satellite constellation according to claim 1, wherein in the step 1, the nodes are clustered first at the beginning, and the method comprises the following specific steps: Step 1.1, initializing, wherein node states of all nodes are set as free nodes, and cluster ID and cluster head ID information is NULL; Step 1.2, the controller selects cluster head nodes from the gateway satellite, and sends cluster head notification messages to the selected cluster head nodes, wherein the cluster head notification messages comprise cluster ID and cluster radius information; step 1.3, the node which receives the cluster head notification message changes the state of the node to be the cluster head, and changes the cluster ID; Step 1.4, broadcasting a cluster notification message to the periphery by a cluster Head, wherein the cluster notification message comprises a cluster ID, cluster Head ID information, TTL (transistor-transistor logic), cluster Head address information and route_to_head information, wherein the TTL is a cluster radius received by the cluster Head, the route_to_head information records a node address of a path in the message broadcasting process, and the information is empty initially; If the node receiving the clustered notification message is a free node, judging whether TTL in the message is greater than 1, if so, subtracting 1 from TTL in the message, adding the last hop to the end of router_to_head of the message, and broadcasting to surrounding neighbors again, thereby realizing the flooding effect in the cluster radius, if TTL is less than or equal to 1, not broadcasting the message any more, if the node receiving the clustered notification message is a member node, judging whether the cluster ID in the message is consistent with the cluster ID of the node, if so, forwarding the clustered notification message, otherwise, not forwarding the notification message; Step 1.6, if the free node is the first time to receive the cluster-entering notice message from the cluster head, the free node sets the last hop of the message as the next hop to the cluster head and sends a cluster request message to the cluster head, wherein the free node comprises the node ID, the address and the path from the cluster head to the free node, and in view of each node experienced in the process of flooding the cluster-entering notice message, the next hop route information to the cluster head exists, the cluster-entering request message can be forwarded to the cluster head hop by hop, if the node does not receive the cluster-entering notice message from the cluster head for the first time, the free node directly sends the cluster-entering request message to the cluster head, and after sending the cluster-entering request message, the free node changes the state of the free node to be in a pending state; Step 1.7, after the cluster head node receives the cluster request message, recording the ID and address information of the newly-clustered node; step 1.8, the cluster head sends a cluster-entering confirmation message to a corresponding undetermined node according to a path from the cluster head to the free node in the cluster-entering request message, wherein the message comprises a cluster ID, a cluster head ID and a cluster head address; Step 1.9, after receiving the cluster-entering confirmation message, the node changes the state of the node to be a member, changes the cluster ID, the cluster head ID and the cluster head address according to the information in the message, and starts to periodically broadcast the HELLO message; Step 1.10, in addition, the cluster head generates a cluster update message containing update types, namely 'NEW', cluster ID and address information of a newly-entering cluster node, and forwards the cluster update message to other cluster head nodes of the network through a control node; Step 1.11, other cluster heads receive the cluster update message, add the new node address in the message to the address list of the corresponding cluster, update the route between clusters after receiving no other cluster neighbor update message, cluster topology update message and cluster update message in Tinter, so as to finish the initial node clustering.
3. The method for designing agile clustering routing protocol for large-scale satellite constellation according to claim 1, wherein step 2 is characterized in that after the nodes are clustered, neighbor discovery and routing update are started, and the message format involved therein comprises the following specific steps: Step 2.1, after receiving the cluster-entering confirmation message, the member node in the cluster starts to periodically broadcast HELLO message, wherein the message comprises the ID of the node, the node address, the cluster ID information and a neighbor ID list of the node; Step 2.2, after receiving HELLO message of adjacent node, member node judges whether there is node ID in HELLO message in self neighbor list, if not, add the node ID in the message into self neighbor list; Step 2.3, judging whether the neighbor ID list in the message contains the self ID, if so, considering that the neighbor and the self establish a bidirectional adjacent relation, and if not, waiting for the next HELLO message to be received; Step 2.4, judging whether the cluster IDs of the two parties are the same, if so, considering that the intra-cluster neighbors are found, and at the moment, jumping step 2.4.1 to execute the intra-cluster route updating step as follows: step 2.4.1.1 member nodes send topology updating messages in the cluster to the cluster head, and at the moment, an update_type field in the messages is NEW, and the update_type field contains IDs of the member nodes and newly discovered neighbors; Step 2.4.1.2, after the cluster head receives the message, updating the topology map in the cluster; Step 2.4.1.3, the cluster head waits for a period of time Tintra, if new intra-cluster topology updating information is received in Tintra, the timer reckons, if the new intra-cluster topology updating information is not received in Tintra, the intra-cluster topology table is updated according to the intra-cluster topology updating information received in Tintra, and an end-to-end routing table in the cluster is calculated; Step 2.4.1.4, the cluster head transmits an intra-cluster route update message to an intra-cluster member node, wherein each route entry contains destination node and next-hop information; Step 2.4.1.5, the member node updates the routing table according to the information in the routing update message in the cluster, if the information is different, the member node considers that the inter-cluster neighbors are found, and the step 2.4.2 is skipped to execute the inter-cluster routing update flow as follows: Step 2.4.2.1, finding member nodes of the inter-cluster neighbors to be regarded as cluster edge nodes, wherein the cluster edge nodes record neighbor cluster IDs and corresponding neighbor node addresses in a local neighbor cluster database; Step 2.4.2.2 edge node sends the cluster head to the cluster head and updates the message, at this moment, the update_type field in the message is "NEW", include self ID and adjacent cluster ID information in the message; step 2.4.2.3, after the cluster head receives the inter-cluster topology updating message, adding the edge node ID in the message into an alternative edge node list of the corresponding neighbor cluster; Step 2.4.2.4 cluster head judges whether the cluster ID in the message is a newly discovered neighbor cluster, if yes, the step 2.4.2.5 is skipped, if not, the step 2.4.2.7 is skipped; Step 2.4.2.5, updating an inter-cluster topological graph by the cluster head; step 2.4.2.6, the cluster head generates an inter-cluster topology update message which contains an update type, namely 'NEW', a cluster ID and a NEW neighbor cluster ID, and forwards the update message to other cluster heads through a control node, and the other cluster heads recalculate the inter-cluster route and issue the inter-cluster topology update message; Step 2.4.2.7, the cluster head waits for a period of time Tinter, if a new inter-cluster neighbor update message, an inter-cluster topology update message or a cluster update message is received in Tinter, the timer is re-timed, and when the timer returns to zero, the ID of the next-hop cluster to other clusters is calculated based on Dijkstra algorithm according to the inter-cluster topology map; step 2.4.2.8, randomly selecting an edge node from the candidate edge node list of the corresponding neighbor cluster according to the next-hop cluster ID of the other clusters; step 2.4.2.9 encapsulates the inter-cluster routing update message in the form of { < edge node IP >, < destination IP1>, < destination IP2>, < destination IPn > } according to all the node IP information of the destination cluster and the corresponding edge node IP information, and issues the inter-cluster routing update message to the corresponding member node; step 2.4.2.10 constructs an inter-cluster route update message of { < next hop cluster ID >, < destination IP1>, < destination IP2>, < destination IPn > } according to all the node IP information of the destination cluster and the ID information of the corresponding edge node, and sends the inter-cluster route update message to the corresponding edge node; After the cluster head calculates the inter-cluster routing tables of all clusters in step 2.4.2.11, the inter-cluster routing tables are respectively issued to the edge nodes and member nodes except the edge nodes, so that complete inter-cluster routing is established.
4. The method for designing agile clustering routing protocol for large-scale satellite constellation according to claim 1, wherein in step 3, if the intra-cluster link is disconnected, intra-cluster topology update and routing recalculation are performed, and in the process of intra-cluster topology update, if a node is clustered, the node performs a node clustering procedure again, which comprises the following specific steps: step 3.1, when the member in the cluster does not receive the neighbor HELLO message within a certain time, the corresponding link is considered to be disconnected; Step 3.2, the member sends a topology Update message in the cluster to the cluster head, wherein at the moment, an update_type field in the message is DEL, which represents that the topology Update is caused by link disconnection, and the message contains node IDs at two ends of the disconnected link; Step 3.3, after the cluster head receives the message, updating the topology map in the cluster; Step 3.4, judging whether the node is separated from the cluster or not by the cluster head, if yes, jumping to step 3.5, otherwise jumping to step 3.8; step 3.5, the cluster head updates the member information in the cluster, and the cluster-off node re-executes the node clustering process; step 3.6, generating a cluster update message containing the update type, the cluster ID and the address of the cluster-leaving node by the cluster head, and forwarding the cluster update message to other cluster head nodes by the control node; Step 3.7, deleting addresses of the cluster-leaving nodes in the cluster update message from the address list of the corresponding cluster by other cluster heads, and updating the inter-cluster route after other inter-cluster neighbor update messages, inter-cluster topology update messages and cluster update messages are not received in Tinter; step 3.8, the cluster head waits Tintra, if Tintra does not receive other intra-cluster topology updating messages, the intra-cluster route is recalculated, and the intra-cluster route updating message is issued; step 3.9, the member in the cluster updates the routing table in the cluster according to the message content.
5. The method for designing agile clustering routing protocol for large-scale satellite constellation according to claim 1, wherein step 4 shows the steps of inter-cluster topology updating and route recalculation, and the specific steps are as follows: Step 4.1, when two edge nodes of adjacent clusters do not receive HELLO messages of each other within a period of time, the edge nodes judge that a link between the two edge nodes is disconnected; Step 4.2, the edge node sends an inter-cluster neighbor Update message to the cluster head, wherein the update_type field in the message is DEL, and the Update is caused by the disconnection of links among the edge nodes, and the message contains the node ID of the edge node and the cluster ID of the corresponding neighbor cluster; and 4.3, after the cluster head receives the inter-cluster updating information, judging whether other alternative edge nodes are still in the current cluster and the neighbor cluster, namely whether other nodes are still in an alternative edge node list of the corresponding cluster, if yes, the inter-cluster topological diagram is unchanged, and if not, the step 4.4.1 in the step 4 is skipped, and if not, the step 4.4.2 is skipped.
6. The method for designing agile clustering routing protocol for large-scale satellite constellation according to claim 1, wherein in step 4, if the inter-cluster link is disconnected, the inter-cluster topology updating and routing recalculation are performed, and the specific steps are as follows: Step 4.4.1. Cluster first selects new cluster edge nodes: Step 4.4.1.1, a routing table among clusters is unchanged, and a cluster head randomly selects a new edge node corresponding to a target cluster from an alternative edge node list; Step 4.4.1.2, the cluster head sends an inter-cluster update message to other intra-cluster members in the format of < edge node address >, < destination address 1>, < destination address 2>, < destination address n >; step 4.4.1.3, the cluster head sends an inter-cluster route update message to the new edge node in the format of < next-hop cluster ID >, < destination address 1>, < destination address 2>, < destination address n >; Step 4.4.1.4, after the edge node and the member node receive the inter-cluster route update message, updating the inter-cluster route table, thereby completing the inter-cluster route update without recalculating the inter-cluster route; step 4.4.2. Cluster head recalculates inter-cluster route: step 4.4.2.1, updating an inter-cluster topological graph by the cluster head; Step 4.4.2.2 cluster heads generate an inter-cluster topology Update message, at this time, an update_type field in the message is DEL, which represents that the inter-cluster topology Update is caused by the disconnection of links between edge nodes, the message contains an Update Type, a cluster ID and an original neighbor cluster ID which is disconnected, and the Update Type, the cluster ID and the original neighbor cluster ID are forwarded to other cluster heads through a control node, and the other cluster heads recalculate the inter-cluster route and issue; Step 4.4.2.3, the cluster head waits for a period of time Tinter, if a new inter-cluster neighbor update message, an inter-cluster topology update message or a cluster update message is received in Tinter, the timer is re-timed, and when the timer returns to zero, the cluster head re-calculates the inter-cluster route according to the inter-cluster topology map; Step 4.4.2.4, the cluster head sends an inter-cluster route update message to the common member node according to the newly calculated inter-cluster route, wherein the format is < edge node address >, < destination address 1>, < destination address 2>, < destination address n >; step 4.4.2.5, the cluster head sends an inter-cluster route update message to the new edge node according to the newly calculated inter-cluster route, wherein the format is < next-hop cluster ID >, < destination address 1>, < destination address 2>, < destination address n >; and 4.4.2.6, the member node and the edge node update the own routing table according to the received inter-cluster routing update message respectively.

Description

Design method of agile clustering routing protocol for large-scale satellite constellation Technical Field The invention relates to the field of satellite communication, in particular to a rapid convergence and low-overhead agile clustering routing protocol design method for a large-scale satellite constellation. Background With the continuous expansion of the satellite network scale and the planning and deployment of constellations of different orbit heights and different functional domains at home and abroad, the satellite network gradually develops towards the direction of multi-functional domain coexistence and cross-functional domain cooperative giant constellations. However, the cross-domain giant star base has the problems of slow convergence, difficult convergence, high cost and complex calculation of a large-scale network, and in order to solve the problems, a hierarchical dividing and dividing clustering routing idea can be adopted to divide the large-scale network into a dry cluster structure, and the convergence time and the management cost are reduced in a intra-cluster autonomous and inter-cluster cooperative mode. The typical clustering algorithm comprises Lin Chunhung and other authors put forward a clustering algorithm based on an ID (identity), see document 1[LinChunhung , Mario Gerla . Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications[J].15(7).1997,9:1265-1275. ];, sheep and other authors put forward a clustering algorithm based on node connectivity, see document 2 [ Yang, cao Xiaomei, chen Guihai. A safe highest node degree clustering algorithm in a mobile ad hoc network, a small microcomputer system [ J ] (08). 2008,8:1377-1383 ]. The authors PRITHWISH BASU put forward a clustering algorithm based on node mobility, see document 3[Prithwish Basu, Khan N, Thomas LiTTLe. A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks[C].In.Proceedings of the 21st International Conference on Distributed Computing Systems.2001:413-418];, chatterjee M, das and other authors put forward a clustering algorithm based on a comprehensive weight, respectively select a node with the largest node ID, a node with the largest relative motion with other nodes and a node with the largest sum of multiple weights as cluster head nodes, see document 4[Chatterjee M,Das S K,Turgut D.WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks. Cluster Computing[J].5(2).2002,4:193-204].. In addition, in a wireless sensor network, the LEACH (Low-ENERGY ADAPTIVE Clustering Hierarchy) protocol put forward by Wendi Rabiner Heinzelman and other people uniformly distributes the energy load of the whole network to each sensor by periodically randomly selecting cluster head nodes, the cluster head nodes are adopted by the distributed strategy, and the cluster head nodes are enabled to realize the self-balancing of the energy consumption of the network to be high in a certain cluster head, and the task is avoided. Aiming at the routing problem of a large-scale satellite network, related research and patent application documents of a clustering routing technology also exist at present, an author Li Rui proposes a large-scale satellite network routing method based on region division, the network is simply divided into a plurality of rectangular grids according to the topological characteristics of a constellation network, see document 5[ large-scale satellite network inter-satellite routing algorithm research [ D ]. Beijing post university, 2024.DOI:10.26969/d.cnki.gbydu.2024.001506], an author Chen C proposes a satellite grouping routing protocol (SGRP, SATELLITE GROUPING AND ROUTING PROTOCOL), satellites in a medium orbit satellite coverage range are divided into a group, topology and time delay information in the group are collected by the medium orbit satellite, and whole network flooding is avoided, see document 6[Chen C, Ekici E. A routing protocol for hierarchical LEO/MEO satellite IP networks[J]. Wireless networks, 2005, 11(4): 507-521]. In published patent application documents, for example, chinese patent application publication No. CN116192239B discloses a multi-satellite dynamic clustering method, which can dynamically form a plurality of satellite clusters in a constellation, determine a cluster head in each cluster, and subsequently manage and control each satellite in the cluster by the cluster head satellite. Each satellite has three states, cluster head, member and pending. The method comprises the steps of determining a cluster of a satellite, wherein a cluster head state refers to a cluster head of the satellite which is already a cluster, a member state refers to a member (non-cluster head) of the satellite which is already a cluster, a pending state refers to a state that the satellite does not determine the cluster to which the satellite belongs, and the state is a state that the dynamic clustering program of the satellite is started, the three st