An Enhanced Multi-Constraint Optimization Algorithm for Efficient Network Topology Generation

Abstract

In order to address a problem in the research related to the low stability and communication efficiency issues in the generation of optical communication constellation network topology, there is a critical component for sensing the interaction among satellites. This paper makes a novel contribution by proposing a multi-constraint optimization algorithm for optical communication constellation network topology generation. The proposed method significantly improves the existing systems by considering multiple attributes that influence the establishment of inter-satellite links and reducing the impact of subjective factors. This unique approach involves calculating the entropy weight of each attribute using the information entropy method based on the degree of change in each indicator. Subsequently, the weights of the indicators are corrected to obtain the objective weight of each attribute. The comprehensive weight of the link, computed based on the initial link attribute values and weights, serves as the decision basis for link selection, thereby forming the satellite network topology. Upon evaluation, the proposed method has shown remarkable superiority over the compared schemes in terms of communication efficiency and stability.

1. Introduction

As advancements in space-based reconnaissance ballistic missile systems progress towards tactical development, there is a growing demand for satellite reconnaissance and autonomous multi-satellite cooperation in executing reconnaissance tasks. Traditional single satellites, restricted to individual tasks, are unable to meet these increasing requirements. However, existing satellite communication systems in our country have not yet achieved satellite networking. Single-satellite resources are limited, and inter-satellite resources remain isolated with low interconnectivity and interaction capabilities, leading to inefficient use of constellation resources. The Optical Communication Constellation Network (OCCN) offers a potential solution. This satellite network employs laser-based inter-satellite links for communication [1], facilitating information transmission and exchange through established inter-satellite links. The OCCN presents several advantages, such as low power and mass requirements, a license-free spectrum, and high bandwidth. China has proposed the concept of a space-based optical network founded on navigation constellations [2,3,4]. The quality of topology design considerably affects the performance of such space-based optical networks. Serving as intermediate nodes for ground-to-air communication, satellite networks must manage significant information transmission, acquisition, and distribution tasks. However, they also pose challenges including complex composition structures, dynamic topology changes, large spatial scales, and high degrees of self-organization, which impact the stability of the satellite network topology. A stable satellite network topology is essential for network information exchange, resource sharing, and implementing on-orbit routing. The satellite constellation network structure model exhibits a periodic nature, reflecting the periodic behavior of each node. Consequently, developing and optimizing satellite network topologies using reliable algorithms has emerged as a research area of interest both nationally and internationally. While substantial progress has been achieved in terrestrial network topology generation, research on satellite network topology generation remains limited. Unlike terrestrial networks, satellite networks provide all-weather, high-bandwidth coverage across vast areas and are unrestricted by terrain [5]. The swift movement of satellites, however, results in rapid changes in satellite network topologies. Several dynamic topology masking methods have been proposed to address this challenge, such as Virtual Topology (VT) [6,7] and Virtual Node (VN) methods. Nonetheless, conventional VN methods have been insufficient in fully masking topology dynamics. In response to this challenge, this paper presents the following contributions:

• Taking into account the properties of the constellation network, we introduce a multi-constraint optimization-based algorithm for generating optical communication constellation network topologies. The resulting topology boasts improved stability and communication efficiency.
• Determining index weights is essential under multiple constraint conditions. We suggest a multi-attribute weight calculation method to establish link weights, which serves as the basis for forming and removing links.
• Simulation results reveal that our proposed algorithm outperforms the LCT strategy in stability by 14.3397% and achieves a 13.0753% improvement in communication efficiency compared to the SLI scheme, thereby confirming the effectiveness of our approach.

2. Related Work

The optical satellite constellation network, a high-speed data transmission platform, relies significantly on its topology configuration. Enhancing the constellation’s structure is crucial for improving the network’s reliability, stability, and communication efficiency. Consequently, the study of the optical satellite constellation network’s topology seeks to devise an optimized constellation structure that enhances efficient data transmission and communication services, thereby promoting productivity and fostering innovation. The study also assists in addressing inter-satellite connection issues, improving constellation coordination, and augmenting overall efficiency, thus providing valuable insights and technical support for satellite communication advancements.

Numerous researchers have proposed various optimization algorithms to enhance network performance. The approach proposed by Shaukat et al. [8] aimed to maximize system performance and reliability by considering the impact of satellite network topology on link allocation. However, a potential drawback of this method is that it may require substantial computational resources due to the use of Monte Carlo simulations. Yang et al. [9] suggested a multi-path routing algorithm for satellite networks, based on ant colony optimization, which effectively reduces energy consumption while transmitting data efficiently. However, the algorithm’s efficiency can be compromised due to the ant colony optimization limitations, satellite node count, and network topology. This optimization can be applied in low earth orbit satellite networks to achieve efficient load balancing [10]. Jianyun et al. [11] proposed an ant colony optimization-based routing algorithm for medium-to-high earth orbit satellite constellation networks. Though it yields shorter average delays and better network performance, it is unsuitable for dynamically changing network topologies and traffic distribution. Lodewijks et al. [12] optimize airport BHTS design using the particle swarm optimization (PSO) algorithm and effectively solves the optimization problem. Among them, the self-adjusting PSO algorithm performs the best in terms of CPU time. In the optical communication satellite constellation topology design, similar optimization algorithms can also be used, such as applying the PSO algorithm to the inter-satellite link, as well as optimization—optimization of node placement or optimization of bandwidth allocation, etc. Zeng et al. [13] investigated the topology design of optical intersatellite links for future navigation satellite networks, introducing a topology design algorithm rooted in Kruskal’s algorithm. The intersatellite links’ topology structure is optimized to form the minimum spanning tree, with dynamic programming being employed to optimize the bandwidth allocation of these links. However, further optimization of network performance necessitates the incorporation of a wider range of topology control strategies. Yang et al. [14] introduced a topology optimization scheme for space information networks, which utilizes the generation tree algorithm to improve both network performance and stability.

Particle swarm optimization algorithms have also been applied by researchers to optimize the topology structure of inter-satellite networks. Xu et al. [15] and Han et al. [16] centered their research on using the particle swarm optimization algorithm to optimize the topology structure of inter-satellite networks in the Global Navigation Satellite System (GNSS), with the goal of maximizing system performance and reliability. Furthermore, these studies took into account the impact of satellite network topology on link allocation.

Hana et al. [17] proposed a novel topology optimization algorithm, reformulating the optimization problem of satellite-to-satellite links as an integer programming problem. A multi-objective optimization genetic algorithm is presented, aimed at minimizing delay, energy consumption, and link cost for satellite-to-satellite connections. However, the authors did not consider the effects of interference and weather on satellite-to-satellite links, focusing exclusively on laser and Ka-band mixed satellite navigation systems. Zhu et al. [18] concentrated on the optimization design of visibility and topology of optical satellite-to-satellite links in ultra-large constellations, proposing a genetic algorithm-based optimization strategy to enhance the visibility and reliability of these links.

Emphasis has also been placed on multi-objective optimization in this field of research. Dai et al. [19] successfully employed a multi-objective genetic algorithm to balance various objectives, such as coverage, coverage uniformity, and system cost. Long et al. [20] and He et al. [21] introduced reliable approaches for satellite network routing and resource allocation, based on multi-objective optimization, which improved system performance and efficiency.

Wang et al. [22] suggested a dynamic resource scheduling scheme, founded on the principles of edge computing. Tu et al. [23] put forth a degree-constrained topology generation algorithm aimed at increasing the flexibility and controllability of software-defined satellite networks. Meanwhile, Dong et al. [24] recommended a constellation design method that prioritized user demand and service quality, optimizing broadband networks on high-altitude platforms.

Considering the strengths and weaknesses of these methods, our focus is on the role of multi-constraint optimization in generating the topology of optical communication satellite constellations. We aim to evaluate the impact of multiple attributes on satellites when establishing inter-satellite links.

3. System Model and Problem Description

3.1. System Model

In this paper, we employ a virtual topology strategy to accommodate the dynamic nature of optical communication constellation networks (OCCNs). The constellation network topology is represented as a time-varying graph, depicted in Figure 1. The dynamic topology relationships of the OCCN satellite nodes are discretized by dividing a complete satellite network operation period T into several time slices. The topologies of the optical communication satellite constellation network remain relatively stable within different time periods, referred to as the perception cycle I, with $I=ts-te$. Cycle T comprises a collection of perception periods, $T=\left\{I_1,I_2,\dots ,I_n\right\}$. In light of the characteristics of OCCNs, we assume the following:

• Each satellite is assigned a unique identifier i.
• The communication channel between two satellites operates in full-duplex mode.
• Every satellite has a finite number of optical transceivers, indicating the degree of connectivity d.
• Neighboring nodes are defined as other nodes within the communication radius of a satellite node, with which direct communication is possible.

Based on time-varying graph theory, the optical communication constellation network (OCCN) can be modeled as a simple weighted graph $G=(V,E,W)$. At a given time slot $t=\left\{t_1,t_2,\dots ,t_n\right\}$, the set of vertices $V=\left\{v_1,v_2,\dots ,v_n\right\}$ represents all satellite nodes in the constellation network. The collection of degrees for the satellite nodes, numbered as $1,2,\dots ,n$, is denoted by $D=\left\{d_1,d_2,\dots ,d_n\right\}$.

3.2. Problem Description

For each satellite in the constellation network, a $n\times n$ matrix $E^t$ is constructed, starting from the neighboring nodes. This matrix represents the edge set of links between all pairs of satellites at time slot t, it can be expressed as:

$$E^t=\left[\begin{array}{ccc}{e}_{11}^t& \cdots & e_{1n}^t\\ ⋮& \ddots & ⋮\\ e_{n1}^t& \cdots & e_{nn}^t\end{array}\right]$$

(1)

When $e_{ij}^t=1$, a link is established between node $v_i$ and node $v_j$, permitting the two neighboring nodes to communicate and exchange information. Conversely, when $e_{ij}^t=0$, nodes $v_i$ and $v_j$ cannot establish a link, meaning the nodes cannot communicate directly. Thus, this edge set reflects the connectivity between satellites within the constellation network, forming the network topology.

Under ideal conditions, the visibility criterion between two satellite nodes, $v_i$ and $v_j$, is:

$$\begin{array}{cc}\hfill & \hfill d\le d_{\max }=\sqrt{R_i^2-R_h^2}+\sqrt{R_j^2-R_h^2}\hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill & \hfill \delta ={cos}^{-1}\left(\frac{R_i^2+R_j^2-d^2}{2·R_i·R_j}\right)\le {\delta }_{\max }.\hfill \end{array}$$

(3)

In this context, d represents the link length between satellites; $\delta$ is the geocentric angle formed between nodes $v_i$ and $v_j$; $R_h$ denotes the distance from the geocenter to the line connecting nodes $v_i$ and $v_j$; and $R_i$ and $R_j$ represent the distances from nodes $v_i$ and $v_j$ to the geocenter, respectively.

Proposition 1. 

For any two satellite nodes, $v_i$ and $v_j$, in an optical communication constellation network (OCCN) with an established link between them, the relationship between the geocentric angle, ${\delta }_{ij}$, and the average link duration, $d{l}_{ij}$, can be mathematically represented as:

$$\frac{d\left({\delta }_{ij}\right)}{dt}<0\Rightarrow \frac{d\left(d{l}_{ij}\right)}{dt}>0.$$

(4)

This indicates that a decrease in the geocentric angle ${\delta }_{ij}$ over time corresponds to an increase in the average link duration $d{l}_{ij}$ over the same period.

Proof. 

$$S=k·d^{-2}$$

(5)

where k is a constant of proportionality.

From the visibility criterion between two satellite nodes, $v_i$ and $v_j$, we have:

$$d=\sqrt{R_i^2-R_h^2}+\sqrt{R_j^2-R_h^2}.$$

(6)

Substituting d into the formula for S gives:

$$S=k·{\left(\sqrt{R_i^2-R_h^2}+\sqrt{R_j^2-R_h^2}\right)}^{-2}.$$

(7)

We also have the formula for $\delta$, the geocentric angle, as follows:

$$\delta ={cos}^{-1}\left(\frac{R_i^2+R_j^2-d^2}{2·R_i·R_j}\right).$$

(8)

When $\delta$ decreases, from the cosine function properties, the denominator of the fraction inside the cosine function increases. This results in a decrease in d according to the formula of d. When d decreases, from the formula for S, S increases, which means the stability of the link increases.

This completes the proof that a decrease in the geocentric angle, $\delta$, leads to an increase in the average link duration, $dl$, thus enhancing the stability of the communication link in the OCCN.    □

Due to the unique properties of satellite networks, including large spatiotemporal scales, prolonged delays, dynamic changes, frequent inter-satellite link switching, limited on-board resources, and communication range constraints imposed by antenna elevation angle [25], traditional network node communication limitations are insufficient for on-board communication environments. In this paper, we consider the following constraints for inter-satellite optical communication:

• Link propagation delay: $t\le t_{\max }$;
• Link bandwidth: $b\ge b_{\min }$;
• Link survival time: $lt\ge {lt}_{\min }$;
• Elevation angle between satellites: $\delta \le {\delta }_{\max }$.

If these constraints are met, an initial potential link is established between the two satellite nodes. The number of optical transceivers for each satellite, however, is limited [26]. Therefore, each satellite node’s degree constraint must also be considered. Investigating how to establish inter-satellite links while adhering to these constraints, in addition to ensuring the stability and high communication efficiency of the satellite network topology, is a key issue in generating the constellation network topology.

In this paper, we introduce two metrics, the average link length ($al$) and the average link duration ($dl$), to evaluate the communication efficiency and stability of the constellation network topology.

Average Link Length ($al$): This metric is defined as the average length of all the links in the network. Physically, the link length has a direct impact on the quality of a link. The longer the link, the greater the attenuation and diffusion of light, leading to a lower signal quality [27]. Therefore, a shorter average link length usually means better link quality and higher communication efficiency. Additionally, the link length directly affects the propagation delay of signals. The longer the link, the longer the time for signals to travel from the sender to the receiver. Hence, maintaining a shorter average link length can reduce the overall delay in the network, enhancing network performance [28]. It is expressed as follows:

$$al=\frac{1}{\left|E\right|}\sum _{(i,j)\in E}{d}_{ij}$$

(9)

where $d_{ij}$ is the length of the link between node $v_i$ and node $v_j$, and $\left|E\right|$ is the total number of links in the network. A shorter average link length signifies a reduced propagation delay and heightened overall communication efficiency among satellites within the constellation network topology. Contrarily, a longer average link length infers a more extended propagation delay and diminished overall communication efficiency between satellites in the constellation network topology.

Average Link Duration ($dl$): This metric is defined as the average duration of all the links in the network. The average link duration is a direct indicator of link stability. In dynamic networks, the duration of a link is often influenced by many factors such as node mobility, energy consumption, and communication range [29]. The longer the average link duration, the more stable the links in the network, meaning that communication between nodes is less likely to be interrupted. Therefore, the stability of links directly affects the stability and reliability of the network [30]. By maximizing the average link duration, the stability and reliability of the network can be effectively improved.

Therefore, by optimizing the average link length and average link duration, the stability of optical communication network links can be effectively enhanced. It is calculated as follows:

$$dl=\frac{1}{\left|E\right|}\sum _{(i,j)\in E}{t}_{ij}$$

(10)

where $t_{ij}$ is the duration of the link between node $v_i$ and node $v_j$, and $\left|E\right|$ is the total number of links in the network. A shorter average link duration results in more frequent link switching and adverse network stability. Conversely, a longer average link duration implies superior network stability.

Normalization of average link length ($al$) and average link duration ($dl$):

$$\mu =\frac{a{l}_{ij}-\min \left(al\right)}{\max \left(al\right)-\min \left(al\right)}$$

(11)

$$\lambda =\frac{d{l}_{ij}-\min \left(dl\right)}{\max \left(dl\right)-\min \left(dl\right)}.$$

(12)

Therefore, this paper posits that both $al$ and $dl$ are equally significant in influencing the communication efficiency and stability of the optical communication constellation network, with $al$ having an inverse relationship with communication efficiency and $dl$ exhibiting a direct relationship with stability. The weights of −1 and 1 assigned to $\mu$ and $\lambda$, respectively, in the objective function, are aimed at maximizing communication efficiency and stability within the constellation network topology, subject to various constraints, which is a single-objective multi-constraint optimization problem. The objective function can be represented as follows:

$$\begin{array}{c}{\displaystyle \underset{1\le i,j\le n}{\max }}{\displaystyle \sum _{i=1}^n}{\displaystyle \sum _{j=1}^n}({\lambda }_{ij}-{\mu }_{ij})\hfill \\ \mathrm{s}.\mathrm{t}.\hfill \\ \mathrm{C}1:\delta \le {\delta }_{\max }\hfill \\ \mathrm{C}2:lt\le l{t}_{\max }\hfill \\ \mathrm{C}3:t\le t_{\max }\hfill \\ \mathrm{C}4:b\ge b_{\min }.\hfill \end{array}$$

(13)

We must solve the maximum values of communication efficiency and stability under the constraint of inter-satellite optical communication constraints. The model is established as follows.

4. Algorithm Design

In this study, we propose the Multi-Constraint Optimization for Network Topology Generation (MCOTG) method to resolve the single-objective optimization problem. The single-objective optimization problem in our model concerns the generation of an optical communication constellation network that is optimized for specific constraints, including visibility time window constraints and degree constraints for each satellite. The MCOTG method is designed to efficiently navigate this problem space by considering multiple constraints during the topology generation process. The method starts with an initial network topology and iteratively refines it by evaluating link weights based on several attributes and by removing redundant links. This process facilitates the optimization of the network topology under the specified constraints, hence addressing the single-objective optimization problem. Moreover, by considering the effects of link propagation delay, link bandwidth, and link lifetime on inter-satellite communication, the MCOTG method ensures that the resultant network is not only optimized for the constraints but also for performance and robustness. Therefore, we believe that our MCOTG method is a feasible solution to the single-objective optimization problem.

The MCOTG comprises three primary components: network topology initialization, link weight determination, and redundant link removal. As illustrated in Figure 2, the algorithm considers the impact of multiple attributes on satellites. Initial links are established between satellites that satisfy visibility time window constraints. For these links, a multi-attribute decision-making method is employed to determine attribute weights, minimizing the influence of subjective factors on indicator weight decision-making. Subsequently, link weights are calculated, providing a basis for link removal decisions. During the link removal process, if a satellite possesses an excessive number of potential nodes, smaller-weight potential links are removed first to ensure the constellation network topology’s connectivity. The process continues until all satellites satisfy degree constraints, finalizing the optical communication constellation network topology.

4.1. Network Topology Initialization

For each satellite node in OCCN, a potential inter-satellite link can be established as long as it satisfies the geometric visibility and inter-satellite optical communication constraints with other satellite nodes. The algorithm for establishing the initial links is shown in Algorithm 1.

Algorithm 1: Network Topology Initialization Algorithm.

4.2. Link Weight Calculation Using Multi-Attribute Decision Making

In this paper, we comprehensively consider three factors that affect inter-satellite link communication: link propagation delay, link bandwidth, and link lifetime. We propose a multi-attribute decision-making weight calculation method for potential links between satellite nodes, which assigns a multi-attribute decision-making weight as the basis for link selection. The larger the multi-attribute decision-making weight, the better the link performance, and the higher the priority for selection. The algorithm of weight calculation is as follows.

4.2.1. Standardize Decision Attribute Parameter Values

Establish a multi-attribute decision matrix for each of the n potential inter-satellite links of the satellite node, which can be represented as:

$$D=\left\{\begin{array}{ccc}{a}_1& b_1& c_1\\ ⋮& ⋮& ⋮\\ a_n& b_n& c_n\end{array}\right\}.$$

(14)

The meanings and measurements of different attributes are not the same. To facilitate the unified calculation of link weights and improve the accuracy of the calculation, it is necessary to eliminate the differences between data through standardization. The multi-attribute decision matrix can be standardized by Formula (6) to achieve this:

$$r_{ij}=\frac{\frac{1}{x_{ij}}}{\underset{i\in N}{\max }\left(\frac{1}{x_{ij}}\right)}=\frac{\underset{i\in N}{\max }\left(x_{ij}\right)}{x_{ij}}=\frac{x_j^{-}}{x_{ij}}.$$

(15)

Here, $X_{ij}$ represents the value of the original decision matrix, and r represents the value of the standardized decision matrix after normalization. Formula (15) can solve the incommensurability problem among multiple attributes and obtain the normalized standard decision matrix R. It can be represented as:

$$R=\left[\begin{array}{ccc}{r}_{11}& \cdots & r_{1m}\\ ⋮& \ddots & ⋮\\ r_{n1}& \cdots & r_{nm}\end{array}\right].$$

(16)

4.2.2. Calculating Attribute Weights

In this paper, the method of information entropy is adopted to determine the weights of various attributes. The selection of attribute weights has a direct impact on the comprehensive weight of the links. The attribute weights should be directly proportional to the significance of the attribute in the entire decision-making process.

Given a normalized standard decision matrix, $R={\left(x_{ij}\right)}_{n\times m}$, the entropy value for the jth attribute $S_j$ can be calculated using the information entropy Formulas (17) and (18), as shown below:

$$p_{ij}=\frac{x_{ij}}{{\sum }_{i=1}^n{x}_{ij}},\forall i,j$$

(17)

$$S_j=-k\sum _{i=1}^n{p}_{ij}ln{p}_{ij}.$$

(18)

Here, k is a constant, and the inclusion of its value ensures that the range of entropy values lies within the interval [0, 1]. The information entropy difference, $h_j$, can be defined as:

$$h_j=1-s_j.$$

(19)

Substituting Formula (19), we can obtain the attribute weights:

$$q_j=\frac{h_j}{{\sum }_{j=1}^m{\beta }_j{h}_j},\forall j.$$

(20)

This formula ensures that $0\le q_j\le 1$, ${\sum }_{j=1}^m{q}_j=1$. Moreover, the introduction of the variable $\beta$ in the formula allows for the adjustment of attribute weights in the decision-making process, permitting varying degrees of importance to be assigned to different attributes. In cases without preference, the value of $\beta$ is set to 1.

4.2.3. Calculating Comprehensive Weight Value of Links

In Section 4.2.1 of the paper, the normalized decision attribute matrix was acquired. Subsequently, the weights of each attribute were calculated, resulting in a row vector Q representing the attribute weights. These two matrices are then multiplied to obtain a comprehensive weight value matrix W for n potential links of a satellite node as follows:

$$W=D\times Q=\left[\begin{array}{ccc}{d}_{11}& \cdots & d_{13}\\ ⋮& \ddots & ⋮\\ d_{n1}& \dots & d_{n3}\end{array}\right]\times \left[\begin{array}{c}{q}_{11}\\ q_{21}\\ q_{31}\end{array}\right]=\left[\begin{array}{c}{w}_{11}\\ w_{21}\\ \dots \\ w_{n1}\end{array}\right].$$

(21)

By following these steps, the multi-attribute decision-making weight values for all potential links of each satellite node can be calculated. These weight values are subsequently assigned to all potential links in the optical communication constellation network for the purpose of constructing link decisions. The multi-attribute weighting algorithm process is depicted in Algorithm 2.    

Algorithm 2: Multi-Attribute Decision-making Weight Algorithm.

4.3. Delete Link

Following the establishment of the initial links in Section 3.1 and the assignment of weights to the links in Section 3.2, a process to delete poor-performing potential links for satellite nodes with more potential links than the node degree is introduced. First, a link with the smallest weight is removed from these nodes. This operation is executed iteratively until all satellite nodes have a number of potential links less than the node degree, ultimately resulting in a satellite network topology. The detailed procedure of the link deletion algorithm is demonstrated in Algorithm 3.

Algorithm 3: Link deletion algorithm.

Upon making decisions on the deletion of links through the link deletion algorithm for the initialized potential links, an optical communication constellation network topology with the same number of nodes as the satellite nodes in the constellation network is generated, where the number of inter-satellite links for each satellite node does not exceed the number of optical transceivers. The complete procedure of the MCOTG algorithm is illustrated in Figure 3.

4.4. Time Complexity Analysis of the Algorithm

Proof: We first analyze the time complexity for the initial link creation algorithm, which creates inter-satellite links. The outer loop runs n iterations, where n denotes the number of nodes. The inner loop iterates through all neighbors of each node, which can be as many as n in the worst case. Operations within the inner loop, such as checking visibility, communication constraints, and potentially adding a link, have a constant time complexity $O\left(1\right)$. Thus, this part of the algorithm exhibits a time complexity of $O\left(n^2\right)$.

Next, we consider the link pruning process. Like before, the outer loop runs n iterations. The inner while loop continues as long as a node’s degree remains greater than d. In the worst case, this could be n. The operations within the while loop, finding and removing the link with the smallest weight, may have a time complexity of $O\left(n\right)$ if implemented inefficiently. However, it could be solved in $O(logn)$ time. Therefore, in the worst case, this part of the algorithm has a time complexity of $O(n^{2}logn)$.

Regarding the multi-attribute decision-making weight algorithm, the following steps are performed: initializing the constellation network topology, calculating the average link length, and computing the average link duration. These operations generally have time complexities of $O\left(n\right)$ or $O\left(m\right)$, where n represents the number of nodes, and m denotes the number of links. Combining the complexities, the total time complexity of the link creation algorithm amounts to $O\left(n^2\right)+O(n^{2}logn)=O(n^{2}logn)$ in the worst case.

When iterating through each node in the constellation network, the outer loop runs n times, where n is the number of nodes in the network. Inside this loop, we perform the following tasks: (a) building a multi-attribute decision matrix D with complexity $O(n\ast a)$, where a is the attribute count; (b) normalizing D to obtain R, which also has a complexity of $O(n\ast a)$, assuming that all matrix entries are visited; (c) computing $p_{ij}$, $S_j$, $h_j$, and $q_j$, each with a complexity of $O\left(n\right)$, as they involve sums over n; (d) obtaining the attribute weight vector Q, an $O\left(1\right)$ operation; (e) calculating $W=D\ast Q$, with complexity $O\left(n^2\right)$, since D is an $n\times n$ matrix.

For the link deletion algorithm, the outer loop runs n times, where n is the number of nodes in the graph. Inside this loop, we: (a) initialize the node in constant time, $O\left(1\right)$; (b) perform an “if condition” check; (c) sort the links of a node according to their weights, an operation with time complexity $O(mlogm)$, where m is the number of links associated with a node. In the worst case, m could be as large as n, resulting in a complexity of $O(nlogn)$.

When analyzing the three algorithms’ time complexities separately, we obtain the following results: Initial Link Creation Algorithm: $O(n^{2}logn)$; Multi-Attribute Decision-making Weight Algorithm: $O(n^2\ast a)$, where a is the number of attributes; Link Deletion Algorithm: $O(n^{2}logn)$ or potentially $O\left(n^3\right)$ if edge deletion is an $O\left(n\right)$ operation. Since the algorithms form parts of a larger algorithm sequentially, the total time complexity is the maximum of these three, as they do not depend on each other and do not form nested loops. If edge deletion can be performed in constant time, the total time complexity is $O(n^{2}logn)$.

5. Results

To verify the performance of the proposed MCOTG algorithm, we conducted joint simulations using System Tool Kit (STK) and Visual Studio (VS), with the LEO satellite constellation adopting the Walker constellation for experimentation.

5.1. Test Methods and Parameters

The Walker constellation is a constellation configuration characterized by having the same orbital altitude, uniformly distributed inclined circular orbital planes, and other features.

Table 1. Simulation Parameter Settings.

Constellation Parameters	Parameter Value
Orbital inclination (${}^{\circ }$)	87.9${}^{\circ }$
Orbit count	4
Number of satellites per orbit	5
Number of satellites	20
Constellation type	Walker Constellation
Inter-satellite link status	Non-permanent Link

presents the parameters for the constellation network. In the experiment, each satellite in the constellation network has a unique identifier, and they are numbered sequentially using characters. Moreover, each satellite has a limited number of optical transceivers, represented as degree constraints. In this experiment, we set the degree value for each satellite to 4.

Table 2. Detailed Parameters of 20 Walker Constellation Satellites.

Orbit	Satellite Name	Int’l Code	Perigee (km)	Apogee (km)	Orbital Period (min)
1	ONEWEB-0012	2019-010A	1203.7	1206.1	109.4
1	ONEWEB-0010	2019-010B	1204.0	1205.8	109.4
1	ONEWEB-0008	2019-010C	1203.2	1206.6	109.4
1	ONEWEB-0007	2019-010D	1207.5	1210.3	109.5
1	ONEWEB-0006	2019-010E	1207.6	1210.2	109.5
2	ONEWEB-0011	2019-010F	1207.1	1210.7	109.5
2	ONEWEB-0021	2020-008D	1227.4	1230.3	109.9
2	ONEWEB-0022	2020-008E	1227.3	1230.4	109.9
2	ONEWEB-0023	2020-008F	1226.9	1230.8	109.9
2	ONEWEB-0024	2020-008G	1227.4	1230.3	109.9
3	ONEWEB-0025	2020-008H	1227.3	1230.4	109.9
3	ONEWEB-0028	2020-008K	1223.3	1226.3	109.8
3	ONEWEB-0032	2020-008L	1227.4	1230.3	109.9
3	ONEWEB-0033	2020-008M	1227.5	1230.2	109.9
3	ONEWEB-0035	2020-008N	1227.3	1230.3	109.9
4	ONEWEB-0038	2020-008Q	1223.6	1226.1	109.8
4	ONEWEB-0044	2020-008V	1227.3	1230.4	109.9
4	ONEWEB-0045	2020-008W	1223.4	1226.3	109.8
4	ONEWEB-0047	2020-008X	1227.3	1230.4	109.9
4	ONEWEB-0048	2020-008Y	1227.2	1230.5	109.9

presents detailed information on the 20 Walker constellation satellites utilized in our simulation experiment. Each entry in the table represents a specific satellite and offers data on key parameters essential for our analysis. These parameters include:

Satellite Name: This column identifies each satellite by its designated name. International ID: This column denotes the internationally recognized identifier of each satellite, which is unique and globally accepted.

Perigee: The perigee listed for each satellite corresponds to the closest point in its orbit to Earth. These values provide crucial information about the orbital geometry and potential for data communication.

Apogee: The apogee denotes the farthest point in the satellite’s orbit from Earth. Like perigee, these values contribute to a comprehensive understanding of each satellite’s orbit.

Orbital Period: The period column represents the time it takes for each satellite to complete one full orbit around Earth. This measure is significant as it impacts the satellite’s visibility and communication windows.

For each satellite in the Walker constellation network, an initialization chaining process is performed, where potential links are established based on the geometric visibility conditions between satellites. Four satellites, each in a different color, represent their positions in four distinct orbits within the Walker constellation. The initialization chaining process results in the formation of the satellite constellation network topology, as depicted in Figure 4.

Figure 5 shows the visualization of the constellation network topology after calculating the multi-attribute decision weights for all potential links of each satellite using the MCOTG algorithm and removing redundant links.

In this paper, the proposed algorithm comprehensively considers the influence of various attributes on satellites and objectively determines the weight of each attribute through a multi-constraint optimization algorithm. This enables the calculation of link weights, providing a decision basis for link selection and generating the optical communication constellation network topology. As shown in the experimental results in Figure 4 and Figure 5, the algorithm successfully generates an initial network topology while satisfying the constraints of inter-satellite optical communication, and obtains the final optimized network topology through link deletion operations.

The MCOTG algorithm proposed in this paper is compared with the Shortest Link Initialization (SLI) topology generation algorithm and the Longest Connection Time (LCT) topology generation algorithm in terms of average link length and average link lifetime. The LCT strategy algorithm prioritizes the selection of satellite nodes with the longest connection duration for establishing links, while the SLI strategy algorithm prioritizes the selection of satellite nodes with the shortest link length for establishing links. We use average link length and average link lifetime as evaluation metrics to analyze the communication efficiency and stability of the generated network topology.

5.2. Algorithm Performance

In terms of the average inter-satellite link connection duration, which reflects the stability of the satellite network topology, we observe different performances among the LCT, SLI, and our proposed MCOTG methods. From the statistical summary in

Table 3. Comparison of Methods for Satellite Link Length Analysis.

Method	Number of Satellites	Mean	Std. Dev.	Std. Error	Lower Limit	Upper Limit
LCT	20	7382.50	602.249	134.667	7100.64	7664.36
SLI	20	6257.50	557.078	124.566	5996.78	6518.22
MCOTG	20	6345.00	327.229	73.171	6191.85	6498.15

, we note that the mean link duration for the LCT method is highest, at 7382.50 min, followed by the MCOTG at 6345.00 min, and the SLI strategy at 6257.50 min.

The lower standard deviation of 327.229 for MCOTG indicates that it has a more consistent performance compared to LCT and SLI. This suggests that the MCOTG method is capable of maintaining a more stable link connection duration across different satellite network topologies.

Although the MCOTG’s mean link length is lower than that of the LCT, it is important to note that this method provides a higher communication efficiency as indicated by its shorter average link length. Furthermore, the upper limit of the 95% confidence interval for the MCOTG method indicates a potential to achieve higher link durations, with a value close to the mean of the LCT method.

Overall, while the LCT strategy can achieve a longer average link duration, our proposed MCOTG algorithm provides a balance between communication efficiency and network stability. This balance is crucial for satellite networks, where both aspects play an important role in achieving an optimal performance. Figure 6 and Figure 7 show that the average link length of the LCT scheme is higher than the other two topology generation methods, indicating that the communication efficiency of the network topology generated by the MCOTG algorithm and SLI strategy is higher than the LCT strategy. In terms of communication efficiency, the MCOTG algorithm is 14.3397% higher than the LCT strategy and 0.8876% lower than the SLI strategy.

A close examination of Figure 8 and Figure 9 reveals that the average link lifetime of the SLI strategy is shorter compared to the other two strategies, which indicates that the MCOTG algorithm and the satellite network topology possess greater stability. The SLI strategy demonstrates a higher level of stability than does the LCT strategy, with a stability increase of 13.0753% and a reduction of 6.4387% compared to the LCT strategy.

As is shown in

Table 4. Comparison of Methods for Satellite Link Lifetime Analysis.

Method	Number of Satellites	Mean	Std. Dev.	Std. Error	Lower Limit	Upper Limit
LCT	20	58.20	2.707	0.605	56.93	59.47
SLI	20	48.075	7.0455	1.5754	44.778	51.372
MCOTG	20	54.275	5.9703	1.3350	51.481	57.069

, although the LCT strategy yields the highest mean value, indicating a longer average link lifetime, its standard deviation and standard error are also higher, suggesting less consistency in its performance. On the other hand, the SLI strategy, while demonstrating lower mean values and thus shorter average link lifetimes, does provide a more consistent performance, as indicated by its smaller standard deviation and standard error.

In contrast, the proposed algorithm offers a notable improvement in both aspects. Despite its mean value being lower than LCT, it is significantly higher than SLI, indicating longer average link lifetimes than the latter. More importantly, its standard deviation and standard error values are the lowest among the three methods, which means it provides the most consistent performance.

Further, the 95% confidence intervals, defined by the lower and upper limits in Table 4, substantiate our results. Briefly, a 95% confidence interval is a probable range for the true mean lifetime, with a narrower interval indicating more precise estimation. For the MCOTG method, its tighter interval underscores its superior stability and efficiency.

In conclusion, while the LCT and SLI strategies have their own strengths, the MCOTG algorithm, proposed in this study, outshines them by offering a more reliable and efficient solution for satellite link lifetime management in complex communication environments.

6. Conclusions and Future Work

In terms of performance, the MCOTG algorithm has shown robust results in both communication efficiency and network stability. It is important to consider both these aspects in a satellite communication network, as an increased link length might improve communication efficiency, but can negatively impact the stability of the network due to increased chances of link breakages. On the other hand, a higher average link lifetime might suggest a stable network, but could compromise on communication efficiency. Hence, a good balance between the two, as demonstrated by the MCOTG algorithm, provides an overall optimal solution for satellite network topology generation.

The above experimental results convincingly illustrate that the MCOTG algorithm can generate a network topology that strikes a balance between communication efficiency and network stability. In the context of satellite communication networks where link lifetime and length are essential, our proposed method performs admirably.

In conclusion, our results suggest that the MCOTG algorithm is a promising approach for generating the network topology of satellite constellations. It provides a reliable solution for the efficient operation of satellite networks, and the potential for future improvements and enhancements to its functionality and effectiveness should be the focus of future research efforts.

A promising direction for future research in the satellite network topology domain is the integration of advanced optimization techniques with the MCOTG algorithm. By leveraging strategies such as genetic algorithms, simulated annealing, or particle swarm optimization, we can enhance both the stability and communication efficiency of the network. These techniques can refine the algorithm’s solution space, providing robust mechanisms to avoid local minima and optimize multi-constraint problems. Therefore, further investigation into this incorporation holds the potential for a significant leap in the performance of satellite network topology generation.