# Routing Strategy for LEO Satellite Networks Based on Membership Degree Functions

Authors: Jian Zhou; Qian Bo; Lijuan Sun; Juan Wang; Xiaoyong Yan
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The deployment of Mobile Edge Computing (MEC) servers on Low Earth Orbit (LEO) satellites to form MEC satellites is of increasing concern. A routing strategy is the key technology in MEC satellites. To solve the uncertainty problem of LEO satellite link information caused by complex space environments, a routing strategy for LEO satellite networks based on membership degree functions is proposed. First, a routing model based on uncertain link information is established. In particular, the membership function is designed to describe the uncertain link information. Based on this, the comprehensive evaluation of the path is calculated, and the routing model considering uncertainty is established with the comprehensive evaluation of the path as the optimization objective. Second, in order to quickly calculate the path, a grey wolf optimization algorithm is designed to solve the routing model. Finally, simulation results show that the proposed strategy can achieve efficient and secure routing in complex space environments and improve the overall performance compared with the performances of traditional routing strategies.


---

## Body

## 1. Introduction

Mobile Edge Computing (MEC), which is a novel and powerful paradigm, is a promising alternative for providing computing capabilities at the edges of networks [1–3]. Low Earth Orbit (LEO) satellite networks possess the advantages of near real-time, wide coverage, and anti-destructive properties [4, 5]. Recently, some studies have combined LEO satellite networks with MEC to deploy MEC servers on LEO satellites for reducing delays and more general purposes [6–8]. As a new MEC architecture, MEC satellites are an emerging topic [9–11]. The design of communication protocols in MEC satellites for achieving efficient and secure data transmission is currently a research hotspot.As the core of the communication protocol, the routing strategy for satellite networks is responsible for data transmission between the intersatellite links and for determining the overall performance of satellite networks [12]. Compared with terrestrial networks, satellite networks possess dynamic topological structures and unbalanced data traffic, which makes the routing strategy for terrestrial networks unsuitable for satellite networks. Thus, the routing strategy for satellite networks has been specially researched [13]. The existing research has focused on the high dynamic change issue of satellite networks. Based on the predictability, periodicity, regularity, and other features of satellite networks, routing strategies based on virtual topology [14–16], virtual nodes [17, 18], and coverage domain partitioning [19] were proposed. At the same time, the data traffic imbalance problem was also of high concern, and a routing strategy based on the load balance was proposed [20–22].However, the link information of LEO satellite networks has a certain degree of uncertainty. On the one hand, the complexity of LEO satellite networks and operating space environments leads to uncertainty in the measured values of link information [23]. For example, harsh space environments such as vacuums, solar radiation, and weak magnetic fields bring about LEO satellite faults, which result in packet loss. The high-speed movement of LEO satellites brings about the issue of dynamic distances between satellites, which results in the instability of the transmission delay. The relatively long delay of intersatellite links results in the nonreal-time updating of link information. On the other hand, link evaluations themselves, such as “low delay,” “high reliability,” and “high bandwidth,” possess a certain degree of uncertainty. In summary, traditional routing strategies for satellite networks are not efficient because they do not consider the complicated factors that affect the routing process. Therefore, the uncertainty of link information cannot be ignored.In recent years, uncertain routing strategies in complex environments have attracted the attention of researchers [24] and have been successfully applied in the field of wireless sensor networks [25, 26]. At present, some researchers have focused on uncertain routing strategies in satellite networks. Zhang et al. [27] transformed multiattribute parameters of satellites into a comprehensive parameter through the Choquet fuzzy integral. Li et al. [28] estimated the congestion status between adjacent satellites through fuzzy congestion indicators and then proposed a fuzzy routing strategy to avoid congestion. Jiang et al. [29] established a fuzzy rule set and proposed a fuzzy routing strategy that satisfies multiservice QoS for satellite networks. This paper considers the uncertainty of link information, such as the transmission delay, packet loss rate, and available bandwidth, and studies the uncertain routing strategy for LEO satellite networks.To solve the uncertainty problem of LEO satellite link information caused by complex space environments, a routing strategy based on membership degree functions is proposed in this paper. The contributions of this paper are as follows:(1)
A routing model based on uncertain link information is established. Specifically, the uncertain link information is described by the membership degree function, and then the comprehensive evaluation of the path is obtained by integrating different link information of each link in the path. On this basis, the routing model considering uncertainty is established according to the comprehensive evaluation of the path.(2)
A grey wolf optimization (GWO) algorithm is designed to solve the routing model on the premise of ensuring the validity of the path.(3)
Simulation results are presented to show that the proposed strategy can obtain the optimal paths in complex space environments and improve the performance in terms of average delay, packet loss rate, and throughput, compared with traditional routing strategies.The remainder of the paper is organized as follows: the background of membership degree functions is given in Section2. The overall process of the proposed strategy is described in Section 3. The routing model based on uncertain link information is established in Section 4. The GWO algorithm is designed to solve the routing model in Section 5. The simulation analysis is given in Section 6. Finally, the conclusion of the paper is given in Section 7.


## 2. Background of Membership Degree Functions

With the increasing demand for the description and calculation of uncertain data, uncertainty theory continues to evolve. The membership degree function in fuzzy set theory is an efficient tool for describing and dealing with the fuzziness of data [30]. The basic idea of the membership degree function is to extend classical Boolean logic to continuous logic with arbitrary values in a certain interval [31]. Due to the uncertainty of link information, the uncertain link information is described by the membership degree function in fuzzy set theory, which can better reflect the actual situation of a LEO satellite network. The basic information regarding membership degree functions is given in this section.LetU be the domain. μA:U0,1 is a mapping from the domain U to the interval 0,1, and A is called a fuzzy subset of U. μA is called the membership degree function of A. If x∈U, the value of μAx represents the fuzzy degree to which x belongs toA [32].The closer the value ofμAx is to 1, the higher the degree to which x belongs to A. In contrast, the closer the value of μAx is to 0, the lower the degree to which x belongs to A. In particular, when μAx=1, x is considered to belong to A entirely. On the other hand, when μAx=0, x is not considered to belong to A at all.In this paper, we suppose thatx∈R+,U is the link information, and A is a certain kind of link information in U, e.g., a low transmission delay, low packet loss rate, or high available bandwidth.


## 3. Overall Process of the Proposed Strategy

The overall process of the proposed strategy is shown in Figure1. The specific steps are as follows: first, the virtual node method is employed to solve the dynamic change issue of the LEO satellite network, and then the LEO satellite network is represented by a directed graph. Second, the uncertain link information is described by the designed membership degree function. Third, the distance between the membership degree function of link information and the ideal point is calculated, which is employed as the comprehensive evaluation of the link, and then the comprehensive evaluation of the path is obtained by accumulating the comprehensive evaluations of all links in the path. Fourth, the comprehensive evaluation of the path is taken as the optimization objective for establishing the routing model. Finally, the routing model is solved by GWO, and the optimal path can be obtained.Figure 1
Overall process of the proposed strategy.


## 4. Routing Model Based on Uncertain Link Information

### 4.1. Link Information Description

In this section, taking the transmission delay, packet loss rate, and available bandwidth as examples, the link information of LEO satellite networks is represented by the designed membership degree function, which can better reflect the actual situation of a LEO satellite network. The transmission delay from satellite nodeg to satellite node k is denoted as tdgk. The packet loss rate from satellite node g to satellite node k is denoted as lrgk. The available bandwidth from satellite node g to satellite node k is denoted as bdgk. In particular, tdgk, lrgk, and bdgk∈R+.In general, the link information can be divided into efficiency indexes (the larger the better) and cost indexes (the smaller the better). To eliminate the influences of different types of link information on LEO satellite networks, the link information needs to be normalized.


#### 4.1.1. Membership Degree Function of the Transmission Delay

The high-speed movement of LEO satellites brings about the issue of dynamic distances between satellites. Hence, the transmission delay is dynamically changed, which results in the uncertainty of the transmission delay. Whentdgk is less than or equal to Tdgk¯, the transmission delay is considered to have already conformed to the optimal link, so the membership degree function of the transmission delay is invariably 1. When tdgk is greater than Tdgk¯, the degree of conformation of the transmission delay to the optimal link stabilizes relatively at the beginning and then decreases rapidly. For that reason, the membership degree function of the transmission delay of link g,k is described by the exponential function as follows:(1)mfgktd=1,tdgk≤Tdgk¯,e−tdgk+Tdgk¯,tdgk>Tdgk¯,where Tdgk¯ is the transmission delay threshold of link g,k. Since the transmission delay is an additive parameter, it is calculated as Tdgk¯=Tdij/Hcij, where Tdij is the maximum transmission delay threshold of the path, and Hcij is the maximum hop count threshold of the baseline path. Tdgk¯ represents the fact that the transmission delay threshold is averaged to every link in the path. The transmission delay can be denoted by tdgk=Lgk/vtgk, where Lgk is the link distance from satellite node g to satellite node k and vtgk is the constant of light velocity. The smaller tdgk is, the more consistent the optimal link. When tdgk is less than or equal to Tdgk¯, mfgktd is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When tdgk is greater than Tdgk¯, the membership degree of the transmission delay decreases as tdgk increases. That is, the degree of conformation to the optimal link decreases.


#### 4.1.2. Membership Degree Function of the Packet Loss Rate

A harsh space environment, such as a vacuum, an area with solar radiation, or a weak magnetic field, brings about LEO satellite faults, which result in packet loss. Thus, the packet loss rate possesses a certain uncertainty. Whenlrgk is less than or equal to Lrgk¯, the packet loss rate is considered to have already conformed to the optimal link, so the membership degree function of the packet loss rate is invariably 1. When lrgk is greater than Lrgk¯, the degree of conformation of the packet loss rate to the optimal link decreases linearly as the packet loss rate increases. For that reason, the membership degree function of the packet loss rate of link g,k is described by the linear function as follows:(2)mfgklr=1,lrgk≤Lrgk¯,1−lrgk1−Lrgk¯,lrgk>Lrgk¯,where Lrgk¯ is the packet loss rate threshold of link g,k. Since the packet loss rate is a multiplicative parameter, it is calculated as Lrgk¯=LrijHcij, where Lrij is the maximum packet loss rate threshold of the path and Hcij is the maximum hop count threshold of the baseline path. Lrgk¯ represents the fact that the packet loss rate threshold is averaged to every link in the path. The packet loss rate can be denoted by lrgk=1−pkgke/pkgks, where pkgke is the total number of packets received by satellite node k and pkgks is the total number of packets sent by satellite node g. The smaller lrgk is, the more consistent the optimal link. When lrgk is less than or equal to Lrgk¯, mfgklr is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When lrgk is greater than Lrgk¯, the membership degree of the packet loss rate decreases as lrgk increases. That is, the degree of conformation to the optimal link decreases.


#### 4.1.3. Membership Degree Function of the Available Bandwidth

Due to the high-speed movement of LEO satellites, the LEO satellite network is in a state of dynamic change, which results in the uncertainty of the available bandwidth. Whenbdgk is less than Bdgk¯, the degree of conformation of the available bandwidth to the optimal link increases rapidly at the beginning and then stabilizes relatively. When bdgk is greater than or equal to Bdgk¯, the available bandwidth is considered to have already conformed to the optimal link, so the membership degree function of the available bandwidth is invariably 1. For that reason, the membership degree function of the available bandwidth of link g,k is described by the logarithmic function as follows:(3)mfgkbd=1,bdgk≥Bdgk¯,lnbdgkBdgk¯+e−1,bdgk<Bdgk¯,where Bdgk¯ is the available bandwidth threshold of link g,k. Since the available bandwidth is a concavity parameter, it is calculated as Bdgk¯=bdgkmin+bdgkmax/2, where bdgkmin is the minimum value of available bandwidth in the previous time period t and bdgkmax is the maximum value of available bandwidth in the previous time period t. Bdgk¯ represents the average available bandwidth threshold. The available bandwidth can be denoted by bdgk=bdgksum−bdgkoc, where bdgksum is the total bandwidth of link g,k and bdgkoc is the occupied bandwidth of link g,k. The larger bdgk is, the more consistent the optimal link. When bdgk increases to Bdgk¯, the membership degree of the available bandwidth increases. That is, the degree of conformation to the optimal link increases. When bdgk is greater than Bdgk¯, mfgkbd is invariably 1, which demonstrates that the current link completely conforms to the optimal link.


### 4.2. Comprehensive Evaluation of the Path

For the convenience of the routing calculation, ideal point theory [33] is employed to integrate these three link information criteria, i.e., the transmission delay, packet loss rate, and available bandwidth, into a comprehensive evaluation of the link. Euclidean distance is used to measure the distance between two points in ideal point theory. Therefore, Euclidean distance is adopted to calculate the distance between the membership degree function of the link information and the ideal point. This distance is defined as the comprehensive evaluation of the link. The comprehensive evaluation of the link from satellite node g to satellite node k is calculated as follows:(4)ldgk=mfgktd−12+mfgklr−12+mfgkbd−12.The comprehensive evaluation of the path from the source satellite nodei to the destination satellite node j can be obtained by accumulating the comprehensive evaluations of all links in pathij as follows:(5)pdij=∑∀g,k∈pathijldgk,where the smaller the pdij is, the greater the conformation of the path to the optimal path.


### 4.3. Routing Model Establishment

The routing model is established with the comprehensive evaluation of the path as the optimization objective, and the transmission delay of the path, the packet loss rate of the path, the available bandwidth of the path, and the hop count of the path as constraints. The LEO satellite network is regarded as a directed graphGV，E using virtual nodes, where V represents the set of all nodes and E represents the set of all links in the satellite network. Suppose i,j,g,k∈V, g,k∈E, and pathijis the path from node i to node j; then, the routing model of GV,E is as follows:(6)minpdijs.t.∑∀g,k∈pathijtdgk≤Tdij∏∀g,k∈pathij1−lrgk≥1−Lrijmin∀g,k∈pathijbdgk≥Bdij∑∀g,k∈pathijHcgk≤Hcij.In particular,pdij is the comprehensive evaluation of the path from the source satellite node i to the destination satellite node j. ∑∀g,k∈pathijtdgk≤Tdij is the transmission delay constraint of the path; that is, the sum of the transmission delays of all links in the selected path must be less than or equal to the maximum transmission delay threshold of path Tdij. ∏∀g,k∈pathij1−lrgk≥1−Lrij is the packet loss rate constraint of the path; that is, the product of the reliability of every link in the selected path must be greater than or equal to the minimum reliability threshold of path 1−Lrij. In particular, Lrij is the maximum packet loss rate threshold of the path. min∀g,k∈pathijbdgk≥Bdij is the available bandwidth constraint of the path; that is, the minimum available bandwidth of every link in the selected path must be greater than or equal to the minimum available bandwidth threshold of path Bdij. ∑∀g,k∈pathijHcgk≤Hcij is the hop count constraint of the path; that is, the hop count of the selected path must be less than or equal to the maximum hop count threshold of the baseline path. The baseline path is generated by a depth search with a depth limit Hcij. Hcij=numorbit+numorbit_sat/2, where numorbit is the number of orbits of LEO satellite networks and numorbit_sat is the number of satellites in one orbit. In particular, if the values of pdij of two paths are the same, the optimal path is randomly selected from the two paths.


## 4.1. Link Information Description

In this section, taking the transmission delay, packet loss rate, and available bandwidth as examples, the link information of LEO satellite networks is represented by the designed membership degree function, which can better reflect the actual situation of a LEO satellite network. The transmission delay from satellite nodeg to satellite node k is denoted as tdgk. The packet loss rate from satellite node g to satellite node k is denoted as lrgk. The available bandwidth from satellite node g to satellite node k is denoted as bdgk. In particular, tdgk, lrgk, and bdgk∈R+.In general, the link information can be divided into efficiency indexes (the larger the better) and cost indexes (the smaller the better). To eliminate the influences of different types of link information on LEO satellite networks, the link information needs to be normalized.


### 4.1.1. Membership Degree Function of the Transmission Delay

The high-speed movement of LEO satellites brings about the issue of dynamic distances between satellites. Hence, the transmission delay is dynamically changed, which results in the uncertainty of the transmission delay. Whentdgk is less than or equal to Tdgk¯, the transmission delay is considered to have already conformed to the optimal link, so the membership degree function of the transmission delay is invariably 1. When tdgk is greater than Tdgk¯, the degree of conformation of the transmission delay to the optimal link stabilizes relatively at the beginning and then decreases rapidly. For that reason, the membership degree function of the transmission delay of link g,k is described by the exponential function as follows:(1)mfgktd=1,tdgk≤Tdgk¯,e−tdgk+Tdgk¯,tdgk>Tdgk¯,where Tdgk¯ is the transmission delay threshold of link g,k. Since the transmission delay is an additive parameter, it is calculated as Tdgk¯=Tdij/Hcij, where Tdij is the maximum transmission delay threshold of the path, and Hcij is the maximum hop count threshold of the baseline path. Tdgk¯ represents the fact that the transmission delay threshold is averaged to every link in the path. The transmission delay can be denoted by tdgk=Lgk/vtgk, where Lgk is the link distance from satellite node g to satellite node k and vtgk is the constant of light velocity. The smaller tdgk is, the more consistent the optimal link. When tdgk is less than or equal to Tdgk¯, mfgktd is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When tdgk is greater than Tdgk¯, the membership degree of the transmission delay decreases as tdgk increases. That is, the degree of conformation to the optimal link decreases.


### 4.1.2. Membership Degree Function of the Packet Loss Rate

A harsh space environment, such as a vacuum, an area with solar radiation, or a weak magnetic field, brings about LEO satellite faults, which result in packet loss. Thus, the packet loss rate possesses a certain uncertainty. Whenlrgk is less than or equal to Lrgk¯, the packet loss rate is considered to have already conformed to the optimal link, so the membership degree function of the packet loss rate is invariably 1. When lrgk is greater than Lrgk¯, the degree of conformation of the packet loss rate to the optimal link decreases linearly as the packet loss rate increases. For that reason, the membership degree function of the packet loss rate of link g,k is described by the linear function as follows:(2)mfgklr=1,lrgk≤Lrgk¯,1−lrgk1−Lrgk¯,lrgk>Lrgk¯,where Lrgk¯ is the packet loss rate threshold of link g,k. Since the packet loss rate is a multiplicative parameter, it is calculated as Lrgk¯=LrijHcij, where Lrij is the maximum packet loss rate threshold of the path and Hcij is the maximum hop count threshold of the baseline path. Lrgk¯ represents the fact that the packet loss rate threshold is averaged to every link in the path. The packet loss rate can be denoted by lrgk=1−pkgke/pkgks, where pkgke is the total number of packets received by satellite node k and pkgks is the total number of packets sent by satellite node g. The smaller lrgk is, the more consistent the optimal link. When lrgk is less than or equal to Lrgk¯, mfgklr is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When lrgk is greater than Lrgk¯, the membership degree of the packet loss rate decreases as lrgk increases. That is, the degree of conformation to the optimal link decreases.


### 4.1.3. Membership Degree Function of the Available Bandwidth

Due to the high-speed movement of LEO satellites, the LEO satellite network is in a state of dynamic change, which results in the uncertainty of the available bandwidth. Whenbdgk is less than Bdgk¯, the degree of conformation of the available bandwidth to the optimal link increases rapidly at the beginning and then stabilizes relatively. When bdgk is greater than or equal to Bdgk¯, the available bandwidth is considered to have already conformed to the optimal link, so the membership degree function of the available bandwidth is invariably 1. For that reason, the membership degree function of the available bandwidth of link g,k is described by the logarithmic function as follows:(3)mfgkbd=1,bdgk≥Bdgk¯,lnbdgkBdgk¯+e−1,bdgk<Bdgk¯,where Bdgk¯ is the available bandwidth threshold of link g,k. Since the available bandwidth is a concavity parameter, it is calculated as Bdgk¯=bdgkmin+bdgkmax/2, where bdgkmin is the minimum value of available bandwidth in the previous time period t and bdgkmax is the maximum value of available bandwidth in the previous time period t. Bdgk¯ represents the average available bandwidth threshold. The available bandwidth can be denoted by bdgk=bdgksum−bdgkoc, where bdgksum is the total bandwidth of link g,k and bdgkoc is the occupied bandwidth of link g,k. The larger bdgk is, the more consistent the optimal link. When bdgk increases to Bdgk¯, the membership degree of the available bandwidth increases. That is, the degree of conformation to the optimal link increases. When bdgk is greater than Bdgk¯, mfgkbd is invariably 1, which demonstrates that the current link completely conforms to the optimal link.


## 4.1.1. Membership Degree Function of the Transmission Delay

The high-speed movement of LEO satellites brings about the issue of dynamic distances between satellites. Hence, the transmission delay is dynamically changed, which results in the uncertainty of the transmission delay. Whentdgk is less than or equal to Tdgk¯, the transmission delay is considered to have already conformed to the optimal link, so the membership degree function of the transmission delay is invariably 1. When tdgk is greater than Tdgk¯, the degree of conformation of the transmission delay to the optimal link stabilizes relatively at the beginning and then decreases rapidly. For that reason, the membership degree function of the transmission delay of link g,k is described by the exponential function as follows:(1)mfgktd=1,tdgk≤Tdgk¯,e−tdgk+Tdgk¯,tdgk>Tdgk¯,where Tdgk¯ is the transmission delay threshold of link g,k. Since the transmission delay is an additive parameter, it is calculated as Tdgk¯=Tdij/Hcij, where Tdij is the maximum transmission delay threshold of the path, and Hcij is the maximum hop count threshold of the baseline path. Tdgk¯ represents the fact that the transmission delay threshold is averaged to every link in the path. The transmission delay can be denoted by tdgk=Lgk/vtgk, where Lgk is the link distance from satellite node g to satellite node k and vtgk is the constant of light velocity. The smaller tdgk is, the more consistent the optimal link. When tdgk is less than or equal to Tdgk¯, mfgktd is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When tdgk is greater than Tdgk¯, the membership degree of the transmission delay decreases as tdgk increases. That is, the degree of conformation to the optimal link decreases.


## 4.1.2. Membership Degree Function of the Packet Loss Rate

A harsh space environment, such as a vacuum, an area with solar radiation, or a weak magnetic field, brings about LEO satellite faults, which result in packet loss. Thus, the packet loss rate possesses a certain uncertainty. Whenlrgk is less than or equal to Lrgk¯, the packet loss rate is considered to have already conformed to the optimal link, so the membership degree function of the packet loss rate is invariably 1. When lrgk is greater than Lrgk¯, the degree of conformation of the packet loss rate to the optimal link decreases linearly as the packet loss rate increases. For that reason, the membership degree function of the packet loss rate of link g,k is described by the linear function as follows:(2)mfgklr=1,lrgk≤Lrgk¯,1−lrgk1−Lrgk¯,lrgk>Lrgk¯,where Lrgk¯ is the packet loss rate threshold of link g,k. Since the packet loss rate is a multiplicative parameter, it is calculated as Lrgk¯=LrijHcij, where Lrij is the maximum packet loss rate threshold of the path and Hcij is the maximum hop count threshold of the baseline path. Lrgk¯ represents the fact that the packet loss rate threshold is averaged to every link in the path. The packet loss rate can be denoted by lrgk=1−pkgke/pkgks, where pkgke is the total number of packets received by satellite node k and pkgks is the total number of packets sent by satellite node g. The smaller lrgk is, the more consistent the optimal link. When lrgk is less than or equal to Lrgk¯, mfgklr is invariably 1, which demonstrates that the current link completely conforms to the optimal link. When lrgk is greater than Lrgk¯, the membership degree of the packet loss rate decreases as lrgk increases. That is, the degree of conformation to the optimal link decreases.


## 4.1.3. Membership Degree Function of the Available Bandwidth

Due to the high-speed movement of LEO satellites, the LEO satellite network is in a state of dynamic change, which results in the uncertainty of the available bandwidth. Whenbdgk is less than Bdgk¯, the degree of conformation of the available bandwidth to the optimal link increases rapidly at the beginning and then stabilizes relatively. When bdgk is greater than or equal to Bdgk¯, the available bandwidth is considered to have already conformed to the optimal link, so the membership degree function of the available bandwidth is invariably 1. For that reason, the membership degree function of the available bandwidth of link g,k is described by the logarithmic function as follows:(3)mfgkbd=1,bdgk≥Bdgk¯,lnbdgkBdgk¯+e−1,bdgk<Bdgk¯,where Bdgk¯ is the available bandwidth threshold of link g,k. Since the available bandwidth is a concavity parameter, it is calculated as Bdgk¯=bdgkmin+bdgkmax/2, where bdgkmin is the minimum value of available bandwidth in the previous time period t and bdgkmax is the maximum value of available bandwidth in the previous time period t. Bdgk¯ represents the average available bandwidth threshold. The available bandwidth can be denoted by bdgk=bdgksum−bdgkoc, where bdgksum is the total bandwidth of link g,k and bdgkoc is the occupied bandwidth of link g,k. The larger bdgk is, the more consistent the optimal link. When bdgk increases to Bdgk¯, the membership degree of the available bandwidth increases. That is, the degree of conformation to the optimal link increases. When bdgk is greater than Bdgk¯, mfgkbd is invariably 1, which demonstrates that the current link completely conforms to the optimal link.


## 4.2. Comprehensive Evaluation of the Path

For the convenience of the routing calculation, ideal point theory [33] is employed to integrate these three link information criteria, i.e., the transmission delay, packet loss rate, and available bandwidth, into a comprehensive evaluation of the link. Euclidean distance is used to measure the distance between two points in ideal point theory. Therefore, Euclidean distance is adopted to calculate the distance between the membership degree function of the link information and the ideal point. This distance is defined as the comprehensive evaluation of the link. The comprehensive evaluation of the link from satellite node g to satellite node k is calculated as follows:(4)ldgk=mfgktd−12+mfgklr−12+mfgkbd−12.The comprehensive evaluation of the path from the source satellite nodei to the destination satellite node j can be obtained by accumulating the comprehensive evaluations of all links in pathij as follows:(5)pdij=∑∀g,k∈pathijldgk,where the smaller the pdij is, the greater the conformation of the path to the optimal path.


## 4.3. Routing Model Establishment

The routing model is established with the comprehensive evaluation of the path as the optimization objective, and the transmission delay of the path, the packet loss rate of the path, the available bandwidth of the path, and the hop count of the path as constraints. The LEO satellite network is regarded as a directed graphGV，E using virtual nodes, where V represents the set of all nodes and E represents the set of all links in the satellite network. Suppose i,j,g,k∈V, g,k∈E, and pathijis the path from node i to node j; then, the routing model of GV,E is as follows:(6)minpdijs.t.∑∀g,k∈pathijtdgk≤Tdij∏∀g,k∈pathij1−lrgk≥1−Lrijmin∀g,k∈pathijbdgk≥Bdij∑∀g,k∈pathijHcgk≤Hcij.In particular,pdij is the comprehensive evaluation of the path from the source satellite node i to the destination satellite node j. ∑∀g,k∈pathijtdgk≤Tdij is the transmission delay constraint of the path; that is, the sum of the transmission delays of all links in the selected path must be less than or equal to the maximum transmission delay threshold of path Tdij. ∏∀g,k∈pathij1−lrgk≥1−Lrij is the packet loss rate constraint of the path; that is, the product of the reliability of every link in the selected path must be greater than or equal to the minimum reliability threshold of path 1−Lrij. In particular, Lrij is the maximum packet loss rate threshold of the path. min∀g,k∈pathijbdgk≥Bdij is the available bandwidth constraint of the path; that is, the minimum available bandwidth of every link in the selected path must be greater than or equal to the minimum available bandwidth threshold of path Bdij. ∑∀g,k∈pathijHcgk≤Hcij is the hop count constraint of the path; that is, the hop count of the selected path must be less than or equal to the maximum hop count threshold of the baseline path. The baseline path is generated by a depth search with a depth limit Hcij. Hcij=numorbit+numorbit_sat/2, where numorbit is the number of orbits of LEO satellite networks and numorbit_sat is the number of satellites in one orbit. In particular, if the values of pdij of two paths are the same, the optimal path is randomly selected from the two paths.


## 5. Routing Model Solution Based on the Grey Wolf Optimization Algorithm

The solution of the multiconstraint model is an NP-hard problem [34, 35]. The computational complexity of the routing model increases as the satellite network scale increases. As a new-element heuristic group intelligence algorithm, GWO was proposed by Mirjalili et al. [36]. GWO possesses the advantages of fast convergence and a small amount of required calculations, compared with traditional optimization algorithms. Due to the limited computing capacity of satellite networks, GWO is used to solve the routing model in this section. The flowchart of the solution of the routing model based on GWO is shown in Figure 2. The critical steps of GWO include individual position coding, initial population generation, fitness function design, and prey hunting.Figure 2
Flowchart of the solution of the routing model based on GWO.


### 5.1. Individual Position Coding

In this paper, the path is encoded by the satellite node sequence. An individual, which is recorded by a complete path from the source satellite nodei to the destination satellite node j, can be expressed as Pathsij=i,g,k,…,m,j,i,g,k,m,j∈V. Correspondingly, the path information set of pathij is expressed as Infoij=tdig,lrig,bdig,tdgk,lrgk,bdgk,…,tdmj,lrmj,bdmj. As shown in Figure 3, the link information of the source satellite node i and the destination satellite node j is, respectively, represented by tdig,lrig,bdig and tdmj,lrmj,bdmj, where the transmission delay, packet loss rate, and available bandwidth from satellite node ito satellite node g are represented by tdig,lrig,bdig, respectively. In the process of solving the routing model, the source satellite node i and the destination satellite node j of each individual remain unchanged.Figure 3
Individual position coding.


### 5.2. Initial Population Generation

To ensure the validity of the generated path, the initial path is randomly generated from the source satellite nodei to the destination satellite node j. Afterwards, the initial path is placed into the path set Pathsij.


### 5.3. Fitness Function Design

The optimization objectivepdij of the routing model is used as the fitness function of GWO. The path set Pathsij is sorted in ascending order according to the value of the fitness function, and then the top three individuals are selected as pathα, pathβ, and pathδ in turn.


### 5.4. Prey Hunting

pathα, pathβ, and pathδ are considered as prey positions. Any pathω is continuously updated until the optimal path is obtained, as shown in Figure 4, and the updated path pathω′ is calculated with the guidance of pathα, pathβ, and pathδ as follows:(7)Rα=C1pathα−pathω,Rβ=C2pathβ−pathω,Rδ=C3pathδ−pathω,pathω′=pathα−A1Rα+pathβ−A2Rβ+pathδ−A3Rδ3,where Rα, Rβ, and Rδ are the absolute values of the relative distances between pathωand pathα, pathβ, and pathδ, respectively. C1, C2, and C3 are the influence factors. A1, A2, and A3 are the convergence impact factors.Figure 4
Prey hunting.


## 5.1. Individual Position Coding

In this paper, the path is encoded by the satellite node sequence. An individual, which is recorded by a complete path from the source satellite nodei to the destination satellite node j, can be expressed as Pathsij=i,g,k,…,m,j,i,g,k,m,j∈V. Correspondingly, the path information set of pathij is expressed as Infoij=tdig,lrig,bdig,tdgk,lrgk,bdgk,…,tdmj,lrmj,bdmj. As shown in Figure 3, the link information of the source satellite node i and the destination satellite node j is, respectively, represented by tdig,lrig,bdig and tdmj,lrmj,bdmj, where the transmission delay, packet loss rate, and available bandwidth from satellite node ito satellite node g are represented by tdig,lrig,bdig, respectively. In the process of solving the routing model, the source satellite node i and the destination satellite node j of each individual remain unchanged.Figure 3
Individual position coding.


## 5.2. Initial Population Generation

To ensure the validity of the generated path, the initial path is randomly generated from the source satellite nodei to the destination satellite node j. Afterwards, the initial path is placed into the path set Pathsij.


## 5.3. Fitness Function Design

The optimization objectivepdij of the routing model is used as the fitness function of GWO. The path set Pathsij is sorted in ascending order according to the value of the fitness function, and then the top three individuals are selected as pathα, pathβ, and pathδ in turn.


## 5.4. Prey Hunting

pathα, pathβ, and pathδ are considered as prey positions. Any pathω is continuously updated until the optimal path is obtained, as shown in Figure 4, and the updated path pathω′ is calculated with the guidance of pathα, pathβ, and pathδ as follows:(7)Rα=C1pathα−pathω,Rβ=C2pathβ−pathω,Rδ=C3pathδ−pathω,pathω′=pathα−A1Rα+pathβ−A2Rβ+pathδ−A3Rδ3,where Rα, Rβ, and Rδ are the absolute values of the relative distances between pathωand pathα, pathβ, and pathδ, respectively. C1, C2, and C3 are the influence factors. A1, A2, and A3 are the convergence impact factors.Figure 4
Prey hunting.


## 6. Simulation Analysis

### 6.1. Simulation Environment

We simulate the proposed strategy in NS2 and Visual Studio to verify its effectiveness. The LEO satellite network is constructed with the Iridium constellation of polar orbits in this simulation. The network topology is composed of 66 LEO satellites, and the specific parameters are shown in Table1. The virtual node method is employed to solve the dynamic change issue of LEO satellite networks. According to the coverage area of each satellite in Iridium, Earth’s surface is divided into 66 virtual nodes, which is equal to the number of LEO satellites. The positions and topologies of the 66 virtual nodes are shown in Figure 5.Table 1
Parameters of the LEO satellite network.
ParametersValuesModelIridiumOrbit number6Satellite number66Adjacent orbit interval27°Orbit height780 kmLink bandwidth25 mbpsQueue buffer size50 kbFigure 5
Positions and topologies of the virtual nodes.Moreover, the routing update method is consistent with the literature [37]. A centralized routing computing method is adopted at the regional centre of the virtual nodes. LEO satellites monitor their link information in real time. When the monitored link information exceeds a certain threshold, the link information is sent to the regional centre of the virtual nodes. The route is calculated based on the collected link information at the regional centre. After the calculation is completed, the route is sent to the LEO satellites in the region.A total of 120 user nodes are generated uniformly on the surface of Earth, and each user node generates traffic flows with the same probability. The source-destination pairs are randomly generated.


### 6.2. Simulation Results

The routing strategy for LEO satellite networks based on membership degree functions (RSSN-MDF) is compared with the routing strategy for satellite networks based on Dijkstra algorithm (RSSN-D), the routing strategy for satellite networks based on multilayer decision making (RSSN-ML) [38], and the routing strategy for satellite networks based on multiobjective decision making (RSSN-MDM) [39] in terms of average delay, delay jitter, packet loss rate, throughput, and comprehensive performance.Figure6 shows the comparison of the average delays at different packet sending rates. As shown in this figure, the average delay of RSSN-D increases rapidly as the packet sending rate increases. This is because RSSN-D only takes the transmission delay as the basis of the path calculation and easily becomes congested. RSSN-MDM takes the available bandwidth as one of the link evaluation indicators, effectively avoiding congestion. Consequently, the average delay of RSSN-MDM is better than that of RSSN-ML. RSSN-MDF takes the transmission delay, packet loss rate, and available bandwidth as the optimization objectives and also considers the uncertainty of link information, so RSSN-MDF can adapt to complex space environments and avoid congestion to some extent. Thus, the optimal path can be obtained by RSSN-MDF. As a result, the average delay of RSSN-MDF is always low.Figure 6
Comparison of average delays.Figure7 shows the comparison of delay jitters at different packet sending rates. The delay jitter is the difference between the maximum delay and the minimum delay when the packets pass through the path. As shown in this figure, the delay jitters of RSSN-MDM, RSSN-MDF, and RSSN-D are high and that of RSSN-ML is low. This is because RSSN-ML uses the hierarchical clustering method to calculate the route, which can reduce the complexity of the calculation and decrease the disturbance of the delay. RSSN-MDF takes the transmission delay of the path, packet loss rate of the path, available bandwidth of the path, and hop count of the path as constraints. Meanwhile, RSSN-MDF adopts a centralized routing computing method. The above reasons lead to higher computational complexity. Moreover, there is a delay in the routing update of RSSN-MDF. Some satellites may forward packets according to the old path, and some may forward packets according to the new path. Thus, the difference in the packet delays between RSSN-MDF and the other methods is large. As a result, the delay jitter of RSSN-MDF is high.Figure 7
Comparison of delay jitters.Figure8 shows the comparison of packet loss rates at different packet sending rates. As shown in this figure, the packet loss rates of RSSN-MDF and RSSN-MDM are better than those of RSSN-ML and RSSN-D. This is because RSSN-MDF and RSSN-MDM are similar in terms of their transmission delays, packet loss rates, and available bandwidth as their link evaluation indicators. In addition, RSSN-ML and RSSN-D calculate their paths according to the determined values without considering the uncertainty of link information. Therefore, the packet loss rates of RSSN-ML and RSSN-D rapidly increase as the packet sending rates increase. RSSN-MDF takes the uncertainty of link information into account and introduces path constraints into the routing model, which further improves the reliability of the routing calculation. As a result, the packet loss rate of RSSN-MDF is always low.Figure 8
Comparison of packet loss rates.Figure9 shows the comparison of throughputs at different packet sending rates. As shown in this figure, the throughputs of RSSN-ML and RSSN-D are always low. This is because these two strategies calculate their paths according to the determined values; the optimal paths cannot be obtained in complex space environments. The throughput of RSSN-MDF is similar to that of RSSN-MDM at the beginning and then it becomes superior to that of RSSN-MDM. This is because RSSN-MDF not only considers the uncertainty of link information but also takes the available bandwidth as the link evaluation indicator. Thus, RSSN-MDF can adapt to complex space environments and avoid congestion to some extent. As a result, the throughput of RSSN-MDF increases as the packet sending rate increases.Figure 9
Comparison of throughputs.To evaluate the overall performances of the four strategies, the comprehensive performance is used as an index. First, the average delay, delay jitter, packet loss rate, and throughput are all transformed into cost indexes, and min-max normalization is carried out. Then, the comprehensive performance is calculated by the average weighted summation of these normalized indexes. The smaller the comprehensive performance value is, the better the routing strategy will perform. Figure10 shows the comparison of comprehensive performances at different packet sending rates. As the packet sending rates increase, the comprehensive performances of RSSN-D and RSSN-ML worsen, while those of RSSN-D and RSSN-ML are relatively stable. As shown in this figure, the comprehensive performance of the proposed strategy is the best. In summary, RSSN-MDF can achieve efficient and secure routing in complex space environments.Figure 10
Comparison of comprehensive performances.


## 6.1. Simulation Environment

We simulate the proposed strategy in NS2 and Visual Studio to verify its effectiveness. The LEO satellite network is constructed with the Iridium constellation of polar orbits in this simulation. The network topology is composed of 66 LEO satellites, and the specific parameters are shown in Table1. The virtual node method is employed to solve the dynamic change issue of LEO satellite networks. According to the coverage area of each satellite in Iridium, Earth’s surface is divided into 66 virtual nodes, which is equal to the number of LEO satellites. The positions and topologies of the 66 virtual nodes are shown in Figure 5.Table 1
Parameters of the LEO satellite network.
ParametersValuesModelIridiumOrbit number6Satellite number66Adjacent orbit interval27°Orbit height780 kmLink bandwidth25 mbpsQueue buffer size50 kbFigure 5
Positions and topologies of the virtual nodes.Moreover, the routing update method is consistent with the literature [37]. A centralized routing computing method is adopted at the regional centre of the virtual nodes. LEO satellites monitor their link information in real time. When the monitored link information exceeds a certain threshold, the link information is sent to the regional centre of the virtual nodes. The route is calculated based on the collected link information at the regional centre. After the calculation is completed, the route is sent to the LEO satellites in the region.A total of 120 user nodes are generated uniformly on the surface of Earth, and each user node generates traffic flows with the same probability. The source-destination pairs are randomly generated.


## 6.2. Simulation Results

The routing strategy for LEO satellite networks based on membership degree functions (RSSN-MDF) is compared with the routing strategy for satellite networks based on Dijkstra algorithm (RSSN-D), the routing strategy for satellite networks based on multilayer decision making (RSSN-ML) [38], and the routing strategy for satellite networks based on multiobjective decision making (RSSN-MDM) [39] in terms of average delay, delay jitter, packet loss rate, throughput, and comprehensive performance.Figure6 shows the comparison of the average delays at different packet sending rates. As shown in this figure, the average delay of RSSN-D increases rapidly as the packet sending rate increases. This is because RSSN-D only takes the transmission delay as the basis of the path calculation and easily becomes congested. RSSN-MDM takes the available bandwidth as one of the link evaluation indicators, effectively avoiding congestion. Consequently, the average delay of RSSN-MDM is better than that of RSSN-ML. RSSN-MDF takes the transmission delay, packet loss rate, and available bandwidth as the optimization objectives and also considers the uncertainty of link information, so RSSN-MDF can adapt to complex space environments and avoid congestion to some extent. Thus, the optimal path can be obtained by RSSN-MDF. As a result, the average delay of RSSN-MDF is always low.Figure 6
Comparison of average delays.Figure7 shows the comparison of delay jitters at different packet sending rates. The delay jitter is the difference between the maximum delay and the minimum delay when the packets pass through the path. As shown in this figure, the delay jitters of RSSN-MDM, RSSN-MDF, and RSSN-D are high and that of RSSN-ML is low. This is because RSSN-ML uses the hierarchical clustering method to calculate the route, which can reduce the complexity of the calculation and decrease the disturbance of the delay. RSSN-MDF takes the transmission delay of the path, packet loss rate of the path, available bandwidth of the path, and hop count of the path as constraints. Meanwhile, RSSN-MDF adopts a centralized routing computing method. The above reasons lead to higher computational complexity. Moreover, there is a delay in the routing update of RSSN-MDF. Some satellites may forward packets according to the old path, and some may forward packets according to the new path. Thus, the difference in the packet delays between RSSN-MDF and the other methods is large. As a result, the delay jitter of RSSN-MDF is high.Figure 7
Comparison of delay jitters.Figure8 shows the comparison of packet loss rates at different packet sending rates. As shown in this figure, the packet loss rates of RSSN-MDF and RSSN-MDM are better than those of RSSN-ML and RSSN-D. This is because RSSN-MDF and RSSN-MDM are similar in terms of their transmission delays, packet loss rates, and available bandwidth as their link evaluation indicators. In addition, RSSN-ML and RSSN-D calculate their paths according to the determined values without considering the uncertainty of link information. Therefore, the packet loss rates of RSSN-ML and RSSN-D rapidly increase as the packet sending rates increase. RSSN-MDF takes the uncertainty of link information into account and introduces path constraints into the routing model, which further improves the reliability of the routing calculation. As a result, the packet loss rate of RSSN-MDF is always low.Figure 8
Comparison of packet loss rates.Figure9 shows the comparison of throughputs at different packet sending rates. As shown in this figure, the throughputs of RSSN-ML and RSSN-D are always low. This is because these two strategies calculate their paths according to the determined values; the optimal paths cannot be obtained in complex space environments. The throughput of RSSN-MDF is similar to that of RSSN-MDM at the beginning and then it becomes superior to that of RSSN-MDM. This is because RSSN-MDF not only considers the uncertainty of link information but also takes the available bandwidth as the link evaluation indicator. Thus, RSSN-MDF can adapt to complex space environments and avoid congestion to some extent. As a result, the throughput of RSSN-MDF increases as the packet sending rate increases.Figure 9
Comparison of throughputs.To evaluate the overall performances of the four strategies, the comprehensive performance is used as an index. First, the average delay, delay jitter, packet loss rate, and throughput are all transformed into cost indexes, and min-max normalization is carried out. Then, the comprehensive performance is calculated by the average weighted summation of these normalized indexes. The smaller the comprehensive performance value is, the better the routing strategy will perform. Figure10 shows the comparison of comprehensive performances at different packet sending rates. As the packet sending rates increase, the comprehensive performances of RSSN-D and RSSN-ML worsen, while those of RSSN-D and RSSN-ML are relatively stable. As shown in this figure, the comprehensive performance of the proposed strategy is the best. In summary, RSSN-MDF can achieve efficient and secure routing in complex space environments.Figure 10
Comparison of comprehensive performances.


## 7. Conclusions

Research on routing strategies is significant for MEC satellites. However, the complexity of LEO satellite networks leads to the uncertainty of link information. In this paper, a routing strategy for LEO satellite networks based on membership degree functions is proposed. First, a routing model based on uncertain link information is established. Specifically, the uncertain link information is described by the designed membership degree function, and then the comprehensive evaluation of the path is obtained by integrating different link information of each link in the path. Afterwards, the comprehensive evaluation of the path is taken as the optimization objective to establish the routing model. Second, a GWO algorithm is designed to solve the routing model. Finally, simulation results show that the proposed strategy can achieve efficient and secure routing in complex space environments. Although the proposed strategy loses some delay jitter, it improves the performance in terms of average delay, packet loss rate, and throughput, compared with the performances of traditional routing strategies. The influence of the degree of uncertainty will be taken into consideration in future research.



---

*Source: 8822985-2020-10-16.xml*