# Swarm and Location-Based QoS Routing Algorithm in MEO/LEO Double-Layered Satellite Networks

Authors: Mingchuan Yang; Xinye Shao; Guanchang Xue; Yingzhe Dou
Journal: Wireless Communications and Mobile Computing
 (2023)

---

## Abstract

In this paper, we mainly research on the QoS (Quality of Service) routing algorithms for MEO/LEO (medium Earth orbit/low Earth orbit) double-layered satellite networks. In this type of networks, the rapidly changing network topology due to relative motion of satellites is one of the main challenges when designing an efficient routing algorithm. Specifically, the issues of high rerouting overhead and traffic routing with diverse QoS requirements remain to be resolved. This paper proposed a M-BMDP (modified bandwidth constrained minimum delay path) routing algorithm based on swarm and location for MEO/LEO double-layered satellite networks. This algorithm forms a set of LEO groups according to the footprint of MEO satellites and chooses the relative MEO satellites as its group manager. For delay sensitive traffic, the algorithm can improve the QoS as the cost of packet loss based on hop limit. And for users located in reversed crevice zone, the traffic can route through one MEO satellite to reduce the time delay. The simulation results show that the M-BMDP algorithm performs better in rerouting delay, overhead and pack loss rate compared with existing solutions.


---

## Body

## 1. Introduction

The wide dissemination of Internet of Things technologies into various industries, such as agriculture, forestry, industrial interconnection, etc, reveals data transfer issues in geographically remote locations due to absence of any network infrastructure [1]. With the constant development of satellite technology, as well as the extension of traffic type [2], multi-layered satellite network structure gradually replaces the single-layered network to carry on multiple kinds of traffic, bringing some new problems that need to be studied in the existing typical networks. For instance, the highly dynamic network topology with intermittent and complex inter-satellite link (ISL) connections makes the routing algorithm design very challenging. The research about multi-layered satellite network routing algorithm is favored by many researchers in recent years.The reference [3] proposed a novel Temporal Netgrid Model (TNM) to portray the time-varying topology of large-scale small satellite networks. In [4], a source-based and destination-based multipath cooperative routing algorithm has been proposed for LEO satellite networks. Satellite Grouping and Routing Protocol (SGRP) [5] is a traditional routing algorithm used in the double-layered satellite constellation. Thereinto, the LEO layers and MEO layers adopted Walker and ICO constellations, respectively. Among all the satellites, LEO satellites serve as transponders and MEO satellites serve as managers. The data traffic is carried by the LEO layer, and the routing table is calculated through Dijkstra’s algorithm in SGRP with the transmission delay as the cost. Congestion avoidance is performed by setting a threshold to the queue length of each link monitored by LEO satellites. Once the threshold is surpassed, the corresponding link is considered in congestion and all paths involved will be recalculated. In [5], SGRP was compared with Datagram Routing Algorithm (DRA) [6] and the simulation results show that the delay performance of SGRP is better especially when congestion occurs.In [7], Hierarchical and Distributed QoS (Quality of Service) Routing Protocol (HDRP) is proposed. HDRP algorithm uses Bandwidth constrained Minimum Delay Path (BMDP) to calculate the routing tables efficiently using delay and bandwidth as QoS metrics. In HDRP, data traffic will be transferred through MEO layer when LEO satellites belonging to two different MEO groups. In this way, HDRP exhibits excellent performance than SGRP when network congestion occurs. Both SGRP and HDRP employs virtual topology algorithm [8], which means that the network topology is considered fixed within a time slot. In each time slot, the satellite forwards data according to the calculated routing table. Since the links between MEO and LEO satellites changes rapidly, in this case, the virtual topology algorithm will result in dense slots division. Although some modified algorithms such as Footprint-based Virtual Topology (FVT) [9] have been proposed, the problem still remains to be resolved.Reference [10] proposed a QoS routing algorithm in GEO/LEO satellite networks, which makes full use of the double-layered satellite networks by transferring different kind of traffic through different layers, and focus on achieving load balancing. Class A traffic has the highest priority and the delay-sensitive interactive applications such as VoIP are involved. The traffic class A is never detoured in any situation because the increased detouring delay significantly degrades the QoS. Class B traffic consisting of relatively delay-robust applications such as real-time video streaming applications are delivered only through LEO satellites, i.e., traffic detouring is performed within the LEO layer. Class C traffic represents the best effort traffic, which is allowed to be diverted to GEO satellites because of its robustness to long delays and delay changes. It has better performance than other algorithms which will not distribute the traffic according to the QoS requirements. An Adaptive Routing Protocol for QoS (ARPQ) [11] is proposed to guarantee the QoS requirements of delay sensitive traffic, such as VoIP. When the monitored queue length exceeds the threshold, the delay insensitive traffic will detour to neighboring LEO satellite which has the lightest congestion state. And if the link still congests after diverting the delay insensitive traffic, the algorithm will detour the delay sensitive traffic to MEO layer to avoid the long queuing delay. This algorithm is used in MEO constellation with ISL exists between any two MEO satellites, and is not suitable for ICO con-stellation which has few links between MEO satellitesThe multi-layer satellite network combines the advantages of different orbital satellites, such as flexible networking, diversified functions, and strong invulnerability, and many performances are better than single-layer networks in terms of performance. Multi-layer satellite networks can support more types of services, and different types of services use different routing algorithms, which can improve performance when the network is congested. In this paper, we focus on the issues of frequent routing topology updates, network congestion, and rerouting transmission bandwidth and calculation time overhead for traditional double-layered satellite networks. The virtual node algorithm is to treat the satellite as a virtual node and divide the earth’s surface into many areas, which contains a logical address to represent this area. The satellite closest to the center of the area uses its logical address. In this algorithm, the topology of the network is always changing, and the satellite is constantly updating its logical address. In addition, a network routing algorithm imposes limitations on the amount of traffic data that can be sent. In response to these problems, this paper proposes a swarm and location based QoS routing algorithm which combines the virtual node and virtual topology strategies to meet the QoS requirements of different applications and achieve high utilization of the satellite networks. This algorithm uses the Modified-BMDP (M-BMDP) algorithm to calculate the optimal path of traffic data, which can meet higher QoS requirements.The paper is organized as follows. In section2, we introduce the architecture of MEO/LEO double-layered satellite network. In section 3, we describe the principles in detail which we use in the algorithm. The performance of our algorithm is verified in section 4. Finally, the conclusion remarks are provided in section 5.


## 2. The Architecture of MEO/LEO Double-Layered Satellite Networks

The main parameters of the MEO/LEO double-layered satellite networks are shown in Table1. The LEO layer is composed of 6 (using N instead in the following paragraphs) polar orbits planes, each orbit planes consists 12 (using M instead in the following paragraphs) satellites. The orbit planes are separated from each other with the same angular distance of 360°/2×N. The angular distance of the satellites in the same plane is 360°/M. Since the orbits are nearly circular, the radius, namely the distance between earth’s core and satellite is constant, represented by R. Each LEO satellite contains five links, four of them are ISLs with neighboring LEO satellites, and the remaining one is inter-orbit link (IOL) between LEO and MEO layers. The MEO layer constellation contains 10 satellites which are located in the two orbit planes, each orbit planes consists 5 satellites.Table 1
Parameters of the MEO/LEO double-layered satellite networks.
Parameters of networksLEO layerMEO layer (ICO)Altitude (km)78010355Number of orbits62Number of satellites per orbit125Maximum number of ISLs per satellite53Orbital inclination (°)86.445/135Figure1 is the MEO/LEO double-layered satellite network structure. As shown in the figure, the point C is the crossing point of the two orbit planes. There is a link between two MEO satellites in different orbits only when the distance of them is the shortest to the crossing point.Figure 1
Double-layered satellite network structure.The distance between adjacent satellites in the same orbit plane is the same, calculated as follows.(1)Ld=2R1−cos360∘M.For neighboring satellites located in adjacent orbit planes near the equator, the distance of the interplane ISL is calculated as follows.(2)Lh=α×coslat,where(3)α=2R1−cos360∘2×N,with lat is the latitude where the interplane ISL resides.Figure2 is the 3D coverage diagram of the MEO/LEO double-layered satellite networks. According to the virtual node algorithm, we will generate the logic areas according to the surface of the earth and the structure of the LEO layer. The network model consists of 82 satellite nodes, including 72 LEO satellites and 10 MEO satellites, as well as 2 user nodes. The LEO and MEO satellites correspond to the 72 logical areas and the 10 satellite managers, respectively.Figure 2
Diagram of 3D coverage.


## 3. Swarm and Location-Based QoS Routing Algorithm

In order to meet the needs of different QoS requirements and achieve higher resource utilization efficiency, the traffic is divided into two categories. Class A traffic represents delay-sensitive traffic, and class B traffic represents other types of traffic.Class A traffic transmitted in the LEO layer with a short time delay, and Class B traffic transmitted in the MEO layer through flooding algorithm. In this way, the network can perform better to ease the congestion. However, the end-to-end delay of Class B traffic will increase compared to those transmitted through the LEO layer, which is caused by the relatively high orbit of MEO satellite. Due to the fast movement between MEO and LEO satellites, the virtual topology algorithm will lead to some additional problems, such as abundant routing update time slots, increasing computational complexity, and handover issues when LEO satellites switch its access to MEO satellites.In the virtual node algorithm, the concept of logic area is introduced to simplify the description of the dynamic network topology in [12]. To solve these problems, this paper combines the virtual node and virtual topology algorithm. In this way the coverage relationship between MEO and LEO satellites will be turned into between virtual nodes, thereby simplifying the update of dynamic topology. We divide the surface of earth into 6∗12 grids which defined as logic areas. Each logic area chooses the nearest LEO satellite to its center as the matched satellites. In this way, a one-to-one mapping relationship will be established between the LEO satellites and the logical regions, and this mapping relationship will change with the movement of the satellites. The mapping satellite will be taken over by the successor satellite in the same plane. A logic area is given by p,q, wherep=0,⋯,N−1 is the index of orbit plane, and q=0,⋯,M−1 is the index of satellite in the orbit plane.The virtual topology algorithm is used in the process of selecting the MEO satellites as group manager. When the members of the group change, the topology needs to be updated. Footprints of MEO satellites are used for grouping LEO satellites that have been matched with logical areas [13], as shown in Figure 3. Where A and B represent the positions of MEO satellites, A′ and B′ are the sub-satellite points of A and B on earth, and C′ and D′ are the subpoints of satellite C and satellite D, respectively. In addition, there is a situation shown in Figure 3, when the LEO satellite C is overlapped by two MEO satellites, it will select the group whose manager MEO satellite has the longest coverage time to the central point of the logical area.Figure 3
Footprint of MEO satellite.The angleψ defined in Figure 3 is calculated as follows:
(4)ψ=90−εmin−arcsinRE+hLRE+hM⋅cosεmin,where RE is the radius of the earth, hL and hM are the altitude of the LEO satellites and MEO satellites, respectively, and εmin is the minimum elevation angle of the MEO satellite from the LEO satellite.The LEO satellite C matched with logic area will be within the footprint of MEO satellite B if the following condition is satisfied:(5)∠B′OD′=2arcsinB′D′2RE+hL≤ψ.


### 3.1. Principles of Beehive Algorithm

Wedde proposed Beehive Algorithm in 2004 for the first time in [14]. In this paper, we proposed a routing algorithm based on the idea of Beehive Algorithm, and introduce the concept of bee agents. There are two kinds of agents used in the paper, called short agent and long agent. We use LEO and MEO satellites as short agents and long agents, respectively. Due to the relative movement between LEO satellites and the continuous updating of their logical addresses, LEO satellites may enter or leave the coverage area of MEO satellites, so they are only a short agent for the satellite group. While the MEO satellite always acts as the group manager, it is called the long agent for the satellite group. The relationship between the two kinds of agents is illustrated in Figure 4.Figure 4
Agents in Beehive Algorithm.The LEO satellite is responsible for collecting path information between itself and its neighboring nodes, such as bandwidth utilization. As a group manager of multiple LEO satellites, MEO satellite collect path information collected by LEO satellites, and the working mechanism is like a swarm of bees. After the MEO satellite receives its group information, it is shared at the MEO layer, thus the MEO satellite contains the path information of the entire network. Each MEO satellite calculates and transmits the routing table for its group members according to the whole network state information.


### 3.2. Modified Minimum Hop Path Algorithm

In this section, we introduce an offline routing method which can reduce the routing overhead due to the information exchange among different satellites. Congestion avoidance is completed by calculating two alternative paths in case one is in congestion state. The routing table is calculated before the system is in operation. Therefore, this algorithm needs certain storage space on satellites to keep routing tables in advance.We modify the minimum hop path based on area division: According to the geographical facts, the horizontal distance near the equator is longer than that near the Polar Regions. Different from using the same weight when calculate the routing table, we divide the earth into 3 parts according to the latitude. The weight of intraplane ISL higher than 60 degrees south latitude or north latitude is set to 1, otherwise it is set to 2, and the weight of interplane ISL is set to 2.According to the relationship between the latitude and longitude of source and destination satellites, our algorithm will select two paths in different directions. We denote source and destination satellites asSlos,las and Dlod,lad, respectively.If the relationship of latitude between source and destination satellites satisfies equation (6), we can route the packet upward, and if it satisfies the equation (7), we can route the packet downward.
(6)0∘≤lad−las<90∘or−180∘≤lad−las<−90∘,(7)−90∘≤lad−las<0∘or90∘≤lad−las<180∘.If the relationship of longitude between the source and destination satellite satisfies equation (8), we can route the packet to the left side, and if it satisfies the equation (9), we can route the packet to the right side.
(8)−180∘≤lod−los<0∘or180∘≤lod−los<360∘.(9)0∘≤lod−los<180∘or−360∘≤lod−los<−180∘.In consequence, any two sources and destination satellites can meet two of the four equations, which mean that we can find two alternative paths.


### 3.3. Modified BMDP Algorithm

BMDP algorithm needs to meet the requirements of business bandwidth when calculates the routing table. If the link utilization exceeds the threshold we set, a rerouting mechanism is initiated to calculate alternative paths. Since the recalculation takes a certain amount of time, the traffic transmission during this period will still pass through the old path that is already congested, aggravating the congestion situation.In this paper, we improved the BMDP algorithm based on the concept of swarming and chose the modified minimum hop path algorithm as the backup routing algorithm to alleviate congestion, as shown in Figure5. The M-BMDP algorithm considers both queuing and propagation as delay metrics. Facing with the congestion problem, it will take the rerouting algorithm and adopt a modified minimum hop algorithm to select an off-line calculated path. The M-BMDP algorithm solves the problem of long rerouting time and reduces the routing overhead due to off-line calculation characteristic.Figure 5
The M-BMDP algorithm.GV,E describes the MEO/LEO double-layered satellite networks, where V and E represent the number of satellites and links (including ISL and IOL) in the network, respectively. The link between satellite u and v is described as u,v, and the total delay between node u and v is denoted by Du,v. We calculate the routing table according to the minimum delay path with the bandwidth constraint as follows.
(10)DminpV1,Vn=minDV1,V2+DV2,V3+⋯+DVn−1,Vnwhere pV1,Vn represents the path from V1 to Vn. DminpV1,Vn is the minimum delay path in all possible paths from V1 to Vn.


### 3.4. An Improved Algorithm Based on Hop Limit

Due to class A traffic is sensitive to delay than to packet loss rate, such as VoIP traffic, we improved the M-BMDP algorithm based on hop limit and link utilization state. Assuming that we already know the location of the calling and called users, we can also know the modified minimum hop path, which can be calculated offline. If the following equation is satisfied, we will improve the delay performance at the cost of increasing the packet loss rate.(11)P_num=minm,n,P_num≥λnum,linkr≥β,linkbei≥β,where m and n indicate the number of satellites in the two alternative paths which are calculated by the modified minimum hop algorithm. P_num is the shorter one between them. λnum is the hop number threshold, and β is threshold of the link utilization. linkr indicates the link utilization value of the preferred path calculated by M-BMDP algorithm, and linkbei indicates that of the alternative path. If the link utilization value linkr of preferred path is beyond the threshold we set, it will choose the alternative path. Then, if P_num and linkbei both beyond the limit, the modified algorithm will choose to drop the packet. The flowchart of the algorithm is shown in Figure 6.Figure 6
The flow chart of an improved algorithm based on hop limit.


### 3.5. An Improved Algorithm Based on Special Area Location

In reversed crevice zone, there is no ISL between any satellites inp1 and in p6 orbit, as shown in Figure 7. When the calling and called users are under the footprint of LEO satellites which belongs to the p1 orbit and p6 orbit, respectively, the path calculated by M-BMDP algorithm has to go through all orbit planes to arrive the destination, which will cause a long delay. To solve this problem, we made some improvements. The delay we considered here contains the transmission and queuing delay as follows:
(12)TDelay=Ttransmission+Tqueuing.Figure 7
Satellite movement in reversed crevice zone.And the delay of class A traffic transferred through LEO layer by M-BMDP algorithm is calculated as follows.(13)TDelay=∑i=1sTk+i−1,k+i+∑j=1N−1Tj×M+s,j+1×M+s+∑l=1NumTqueuingl,where k is the satellite number in orbit, and s indicates the difference of orbit index between source and destination LEO satellites. M is the number of satellites in an orbit, and N is the number of orbits. Num is the number of satellites in the calculated path. The last item in Equation (13) denotes the sum of the queuing delay, associated with the transmission rate and the capacity of the queue.Traditional algorithms detour traffic from the source LEO satellite to the MEO layer and then route to the MEO satellite that is the manager of the target LEO satellite group. The latency of this algorithm is calculated as follows:(14)TDelay=TLEOi,MEOk+TMEOs,LEOj+∑l=0s−kTMEOk,MEOk+l+Tqueuingi.When the source and destination LEO satellites are under footprints of two MEO satellites in different orbits, the third item in Equation (14) may be quite longer because the lack of inter-plane links in ICO system. We will make a slightly modification in the way that only one MEO satellite will use in flooding algorithm. Firstly, class A traffic is transferred in LEO layer in the same orbit with source LEO satellite. Secondly, if the current LEO satellite has the same MEO manager with the LEO satellite which is in the same plane with destination satellite, then route the traffic to this MEO manager satellite. As shown in Figure 8, we can always find such a relay LEO satellite. Thirdly, through the IOL between LEO and MEO layers, the traffic then routes to the destination satellite. The delay is calculated as follows.
(15)TDelay=∑l=1NumTLEOi,LEOi+l+TLEOP,MEOq+TMEOq,LEOj+∑n=1Num+2Tqueuingn.Figure 8
The coverage of MEO satellites in logical areas at a certain time.Now, we assume that the calling and called users are located near the Equator and are on the same latitude. The inter orbit delay in LEO layer is calculated as follows.(16)Tj×M+s,j+1×M+s=2πRLEOc×12×N,where RLEO=hLEO+r, N is the number of orbits, c denotes velocity of light, r denotes earth radius, and hLEO is the attitude of LEO satellites.We also assume that the selected MEO satellite is just over the LEO satellite. The delay caused by transferring between LEO and MEO layers is calculated as follows.(17)TLEOi,MEOk=hMEO−hLEOc,where hMEO and hLEO indicates the altitude of MEO and LEO satellites, respectively.


## 3.1. Principles of Beehive Algorithm

Wedde proposed Beehive Algorithm in 2004 for the first time in [14]. In this paper, we proposed a routing algorithm based on the idea of Beehive Algorithm, and introduce the concept of bee agents. There are two kinds of agents used in the paper, called short agent and long agent. We use LEO and MEO satellites as short agents and long agents, respectively. Due to the relative movement between LEO satellites and the continuous updating of their logical addresses, LEO satellites may enter or leave the coverage area of MEO satellites, so they are only a short agent for the satellite group. While the MEO satellite always acts as the group manager, it is called the long agent for the satellite group. The relationship between the two kinds of agents is illustrated in Figure 4.Figure 4
Agents in Beehive Algorithm.The LEO satellite is responsible for collecting path information between itself and its neighboring nodes, such as bandwidth utilization. As a group manager of multiple LEO satellites, MEO satellite collect path information collected by LEO satellites, and the working mechanism is like a swarm of bees. After the MEO satellite receives its group information, it is shared at the MEO layer, thus the MEO satellite contains the path information of the entire network. Each MEO satellite calculates and transmits the routing table for its group members according to the whole network state information.


## 3.2. Modified Minimum Hop Path Algorithm

In this section, we introduce an offline routing method which can reduce the routing overhead due to the information exchange among different satellites. Congestion avoidance is completed by calculating two alternative paths in case one is in congestion state. The routing table is calculated before the system is in operation. Therefore, this algorithm needs certain storage space on satellites to keep routing tables in advance.We modify the minimum hop path based on area division: According to the geographical facts, the horizontal distance near the equator is longer than that near the Polar Regions. Different from using the same weight when calculate the routing table, we divide the earth into 3 parts according to the latitude. The weight of intraplane ISL higher than 60 degrees south latitude or north latitude is set to 1, otherwise it is set to 2, and the weight of interplane ISL is set to 2.According to the relationship between the latitude and longitude of source and destination satellites, our algorithm will select two paths in different directions. We denote source and destination satellites asSlos,las and Dlod,lad, respectively.If the relationship of latitude between source and destination satellites satisfies equation (6), we can route the packet upward, and if it satisfies the equation (7), we can route the packet downward.
(6)0∘≤lad−las<90∘or−180∘≤lad−las<−90∘,(7)−90∘≤lad−las<0∘or90∘≤lad−las<180∘.If the relationship of longitude between the source and destination satellite satisfies equation (8), we can route the packet to the left side, and if it satisfies the equation (9), we can route the packet to the right side.
(8)−180∘≤lod−los<0∘or180∘≤lod−los<360∘.(9)0∘≤lod−los<180∘or−360∘≤lod−los<−180∘.In consequence, any two sources and destination satellites can meet two of the four equations, which mean that we can find two alternative paths.


## 3.3. Modified BMDP Algorithm

BMDP algorithm needs to meet the requirements of business bandwidth when calculates the routing table. If the link utilization exceeds the threshold we set, a rerouting mechanism is initiated to calculate alternative paths. Since the recalculation takes a certain amount of time, the traffic transmission during this period will still pass through the old path that is already congested, aggravating the congestion situation.In this paper, we improved the BMDP algorithm based on the concept of swarming and chose the modified minimum hop path algorithm as the backup routing algorithm to alleviate congestion, as shown in Figure5. The M-BMDP algorithm considers both queuing and propagation as delay metrics. Facing with the congestion problem, it will take the rerouting algorithm and adopt a modified minimum hop algorithm to select an off-line calculated path. The M-BMDP algorithm solves the problem of long rerouting time and reduces the routing overhead due to off-line calculation characteristic.Figure 5
The M-BMDP algorithm.GV,E describes the MEO/LEO double-layered satellite networks, where V and E represent the number of satellites and links (including ISL and IOL) in the network, respectively. The link between satellite u and v is described as u,v, and the total delay between node u and v is denoted by Du,v. We calculate the routing table according to the minimum delay path with the bandwidth constraint as follows.
(10)DminpV1,Vn=minDV1,V2+DV2,V3+⋯+DVn−1,Vnwhere pV1,Vn represents the path from V1 to Vn. DminpV1,Vn is the minimum delay path in all possible paths from V1 to Vn.


## 3.4. An Improved Algorithm Based on Hop Limit

Due to class A traffic is sensitive to delay than to packet loss rate, such as VoIP traffic, we improved the M-BMDP algorithm based on hop limit and link utilization state. Assuming that we already know the location of the calling and called users, we can also know the modified minimum hop path, which can be calculated offline. If the following equation is satisfied, we will improve the delay performance at the cost of increasing the packet loss rate.(11)P_num=minm,n,P_num≥λnum,linkr≥β,linkbei≥β,where m and n indicate the number of satellites in the two alternative paths which are calculated by the modified minimum hop algorithm. P_num is the shorter one between them. λnum is the hop number threshold, and β is threshold of the link utilization. linkr indicates the link utilization value of the preferred path calculated by M-BMDP algorithm, and linkbei indicates that of the alternative path. If the link utilization value linkr of preferred path is beyond the threshold we set, it will choose the alternative path. Then, if P_num and linkbei both beyond the limit, the modified algorithm will choose to drop the packet. The flowchart of the algorithm is shown in Figure 6.Figure 6
The flow chart of an improved algorithm based on hop limit.


## 3.5. An Improved Algorithm Based on Special Area Location

In reversed crevice zone, there is no ISL between any satellites inp1 and in p6 orbit, as shown in Figure 7. When the calling and called users are under the footprint of LEO satellites which belongs to the p1 orbit and p6 orbit, respectively, the path calculated by M-BMDP algorithm has to go through all orbit planes to arrive the destination, which will cause a long delay. To solve this problem, we made some improvements. The delay we considered here contains the transmission and queuing delay as follows:
(12)TDelay=Ttransmission+Tqueuing.Figure 7
Satellite movement in reversed crevice zone.And the delay of class A traffic transferred through LEO layer by M-BMDP algorithm is calculated as follows.(13)TDelay=∑i=1sTk+i−1,k+i+∑j=1N−1Tj×M+s,j+1×M+s+∑l=1NumTqueuingl,where k is the satellite number in orbit, and s indicates the difference of orbit index between source and destination LEO satellites. M is the number of satellites in an orbit, and N is the number of orbits. Num is the number of satellites in the calculated path. The last item in Equation (13) denotes the sum of the queuing delay, associated with the transmission rate and the capacity of the queue.Traditional algorithms detour traffic from the source LEO satellite to the MEO layer and then route to the MEO satellite that is the manager of the target LEO satellite group. The latency of this algorithm is calculated as follows:(14)TDelay=TLEOi,MEOk+TMEOs,LEOj+∑l=0s−kTMEOk,MEOk+l+Tqueuingi.When the source and destination LEO satellites are under footprints of two MEO satellites in different orbits, the third item in Equation (14) may be quite longer because the lack of inter-plane links in ICO system. We will make a slightly modification in the way that only one MEO satellite will use in flooding algorithm. Firstly, class A traffic is transferred in LEO layer in the same orbit with source LEO satellite. Secondly, if the current LEO satellite has the same MEO manager with the LEO satellite which is in the same plane with destination satellite, then route the traffic to this MEO manager satellite. As shown in Figure 8, we can always find such a relay LEO satellite. Thirdly, through the IOL between LEO and MEO layers, the traffic then routes to the destination satellite. The delay is calculated as follows.
(15)TDelay=∑l=1NumTLEOi,LEOi+l+TLEOP,MEOq+TMEOq,LEOj+∑n=1Num+2Tqueuingn.Figure 8
The coverage of MEO satellites in logical areas at a certain time.Now, we assume that the calling and called users are located near the Equator and are on the same latitude. The inter orbit delay in LEO layer is calculated as follows.(16)Tj×M+s,j+1×M+s=2πRLEOc×12×N,where RLEO=hLEO+r, N is the number of orbits, c denotes velocity of light, r denotes earth radius, and hLEO is the attitude of LEO satellites.We also assume that the selected MEO satellite is just over the LEO satellite. The delay caused by transferring between LEO and MEO layers is calculated as follows.(17)TLEOi,MEOk=hMEO−hLEOc,where hMEO and hLEO indicates the altitude of MEO and LEO satellites, respectively.


## 4. Simulation Results and Analysis

The MDSP (Multilayer Dijikstra shortest path) algorithm uses transmission delay as the calculating metric, calculates the routing table of its group members through Dijkstra’s algorithm, then LEO satellites transfer traffic according to this routing table. In the case of congestion, the MDSP cannot response in time due to it calculates the routing table periodically. The performance of the proposed M-BMDP algorithm in terms of end-to-end delay and packet loss rate will be analyzed. Both delay-sensitive and delay-insensitive traffic with diverse QoS requirements are considered. The traffic transition rate ranges from 540 kbps to 620 kbps and the packet size set as 1000 bits.


### 4.1. End-to-End Delay Analysis

#### 4.1.1. Delay of Class A (Delay-Sensitive Traffic)

Figure9 shows the end-to-end delay performance of the MDSP, BMDP, and M-BMDP algorithms for class A traffic. As expected, the delay increases as traffic transmission rate increases. Among all the three routing algorithms, MDSP algorithm have the worst delay performance due to it collects the link state information of the whole network periodically. M-BMDP algorithms have good performance in improving the delay characteristic of delay-sensitive traffic and has a significantly improvement compared to BMDP algorithm. Moreover, BMDP’s superiority over MDSP decreases with the increase of transmission rate.Figure 9
Delay of class A traffic.


#### 4.1.2. Delay of Class B (Delay-Insensitive Traffic)

In this section, these three algorithms all adopted the method of traffic classification. For class B traffic, they all transferred through MEO layer by flooding algorithm, so the delay curves of the three algorithms are overlapped, as shown in Figure10. Compared with class A traffic in Figure 9, class B has longer delay, caused by the reason that the higher altitude of MEO satellites. And there are only two links between the planes in MEO layer, traffic needs to be transferred through multiple MEO satellites when the source and destination MEO satellites are in different orbit. As a result, the delay will increase inevitably.Figure 10
Delay of Class B traffic.


#### 4.1.3. Delay of Class A Based on Hop Limit

Compared to the delay of class A traffic in M-BMDP algorithm, M-BMDP based on hop limit is decreased, as shown in Figure11. And the difference between them increases with the increase of data transmission rates. The decrease of the delay will provide a better QoS performance for class A traffic.Figure 11
Delay of class A based on hop limit.


### 4.2. Packet Loss Rate Analysis

In this section, we only consider the packet loss caused by the limited queue capacity, ignoring the influence of traffic conflict.


#### 4.2.1. Packet Loss Rate Based on M-BMDP

The simulation results of packet loss rate through three algorithms are shown in Figure12. Compared with the MDSP algorithm which does not take any measures to prevent network congestion, BMDP algorithm has a better packet loss characteristic. The packet loss is still ineluctable when using BMDP algorithm because of the rerouting process needs a certain time. With the M-BMDP algorithm we proposed, the alternative path is calculated in advance. When the utilization ratio of link is too high, M-BMDP algorithm utilizes the precomputed alternative path directly without calculating, so the M-BMDP can improve the real-time response ability.Figure 12
Packet loss rate.


#### 4.2.2. Packet Loss Rate Based on Hop Limit

As shown in Figure13, the packet loss rate increases in M-BMDP algorithm based on hop limit. It is worth decreasing the delay to obtain a better QoS even the loss rate increases for class A traffic, but the packet loss rate increases rapidly with higher data transmission rate.Figure 13
Packet loss rate based on hop limit.


### 4.3. Utilization State Analysis of IOLs

Figure14 shows the utilization of the IOLs. The IOLs are used when periodically transferring the state information and the routing tables between LEO satellites and MEO satellites, also when class B traffic transferred from LEO to MEO layer. Compare to the MDSP algorithm, BMDP offers another situation that the rerouting tables and the state information which are used to reroute are transferred between two layers. The rerouting tables are calculated off-line in M-BMDP algorithm, which do not need to collect the state information. Thus M-BMDP algorithm has the same utilization of IOLs with the MDSP algorithm.Figure 14
Utilization state of IOLs.


## 4.1. End-to-End Delay Analysis

### 4.1.1. Delay of Class A (Delay-Sensitive Traffic)

Figure9 shows the end-to-end delay performance of the MDSP, BMDP, and M-BMDP algorithms for class A traffic. As expected, the delay increases as traffic transmission rate increases. Among all the three routing algorithms, MDSP algorithm have the worst delay performance due to it collects the link state information of the whole network periodically. M-BMDP algorithms have good performance in improving the delay characteristic of delay-sensitive traffic and has a significantly improvement compared to BMDP algorithm. Moreover, BMDP’s superiority over MDSP decreases with the increase of transmission rate.Figure 9
Delay of class A traffic.


### 4.1.2. Delay of Class B (Delay-Insensitive Traffic)

In this section, these three algorithms all adopted the method of traffic classification. For class B traffic, they all transferred through MEO layer by flooding algorithm, so the delay curves of the three algorithms are overlapped, as shown in Figure10. Compared with class A traffic in Figure 9, class B has longer delay, caused by the reason that the higher altitude of MEO satellites. And there are only two links between the planes in MEO layer, traffic needs to be transferred through multiple MEO satellites when the source and destination MEO satellites are in different orbit. As a result, the delay will increase inevitably.Figure 10
Delay of Class B traffic.


### 4.1.3. Delay of Class A Based on Hop Limit

Compared to the delay of class A traffic in M-BMDP algorithm, M-BMDP based on hop limit is decreased, as shown in Figure11. And the difference between them increases with the increase of data transmission rates. The decrease of the delay will provide a better QoS performance for class A traffic.Figure 11
Delay of class A based on hop limit.


## 4.1.1. Delay of Class A (Delay-Sensitive Traffic)

Figure9 shows the end-to-end delay performance of the MDSP, BMDP, and M-BMDP algorithms for class A traffic. As expected, the delay increases as traffic transmission rate increases. Among all the three routing algorithms, MDSP algorithm have the worst delay performance due to it collects the link state information of the whole network periodically. M-BMDP algorithms have good performance in improving the delay characteristic of delay-sensitive traffic and has a significantly improvement compared to BMDP algorithm. Moreover, BMDP’s superiority over MDSP decreases with the increase of transmission rate.Figure 9
Delay of class A traffic.


## 4.1.2. Delay of Class B (Delay-Insensitive Traffic)

In this section, these three algorithms all adopted the method of traffic classification. For class B traffic, they all transferred through MEO layer by flooding algorithm, so the delay curves of the three algorithms are overlapped, as shown in Figure10. Compared with class A traffic in Figure 9, class B has longer delay, caused by the reason that the higher altitude of MEO satellites. And there are only two links between the planes in MEO layer, traffic needs to be transferred through multiple MEO satellites when the source and destination MEO satellites are in different orbit. As a result, the delay will increase inevitably.Figure 10
Delay of Class B traffic.


## 4.1.3. Delay of Class A Based on Hop Limit

Compared to the delay of class A traffic in M-BMDP algorithm, M-BMDP based on hop limit is decreased, as shown in Figure11. And the difference between them increases with the increase of data transmission rates. The decrease of the delay will provide a better QoS performance for class A traffic.Figure 11
Delay of class A based on hop limit.


## 4.2. Packet Loss Rate Analysis

In this section, we only consider the packet loss caused by the limited queue capacity, ignoring the influence of traffic conflict.


### 4.2.1. Packet Loss Rate Based on M-BMDP

The simulation results of packet loss rate through three algorithms are shown in Figure12. Compared with the MDSP algorithm which does not take any measures to prevent network congestion, BMDP algorithm has a better packet loss characteristic. The packet loss is still ineluctable when using BMDP algorithm because of the rerouting process needs a certain time. With the M-BMDP algorithm we proposed, the alternative path is calculated in advance. When the utilization ratio of link is too high, M-BMDP algorithm utilizes the precomputed alternative path directly without calculating, so the M-BMDP can improve the real-time response ability.Figure 12
Packet loss rate.


### 4.2.2. Packet Loss Rate Based on Hop Limit

As shown in Figure13, the packet loss rate increases in M-BMDP algorithm based on hop limit. It is worth decreasing the delay to obtain a better QoS even the loss rate increases for class A traffic, but the packet loss rate increases rapidly with higher data transmission rate.Figure 13
Packet loss rate based on hop limit.


## 4.2.1. Packet Loss Rate Based on M-BMDP

The simulation results of packet loss rate through three algorithms are shown in Figure12. Compared with the MDSP algorithm which does not take any measures to prevent network congestion, BMDP algorithm has a better packet loss characteristic. The packet loss is still ineluctable when using BMDP algorithm because of the rerouting process needs a certain time. With the M-BMDP algorithm we proposed, the alternative path is calculated in advance. When the utilization ratio of link is too high, M-BMDP algorithm utilizes the precomputed alternative path directly without calculating, so the M-BMDP can improve the real-time response ability.Figure 12
Packet loss rate.


## 4.2.2. Packet Loss Rate Based on Hop Limit

As shown in Figure13, the packet loss rate increases in M-BMDP algorithm based on hop limit. It is worth decreasing the delay to obtain a better QoS even the loss rate increases for class A traffic, but the packet loss rate increases rapidly with higher data transmission rate.Figure 13
Packet loss rate based on hop limit.


## 4.3. Utilization State Analysis of IOLs

Figure14 shows the utilization of the IOLs. The IOLs are used when periodically transferring the state information and the routing tables between LEO satellites and MEO satellites, also when class B traffic transferred from LEO to MEO layer. Compare to the MDSP algorithm, BMDP offers another situation that the rerouting tables and the state information which are used to reroute are transferred between two layers. The rerouting tables are calculated off-line in M-BMDP algorithm, which do not need to collect the state information. Thus M-BMDP algorithm has the same utilization of IOLs with the MDSP algorithm.Figure 14
Utilization state of IOLs.


## 5. Conclusions

In this paper, we proposed a swarm and location-based QoS routing algorithm in MEO/LEO double-layered satellite networks. We apply virtual topology and virtual node strategies to eliminate the satellite mobility, simplify the topology update problem, reducing additional overhead to cope with the dynamic network condition. We introduce the modified minimum hop algorithm to calculate the alternative path. In this way, we ease the network congestion and reduce the delay of class A traffic. We use M-BMDP algorithm to calculate the routing table using bandwidth, transmission, and queuing delay as QoS metrics. By all these, the simulation results show that our algorithm reduces the delay of class A traffic and the packet loss rate. For class A traffic, we also propose an improved algorithm based on hop limit. When the hop of a path calculated by our algorithm exceeds the threshold, we reduce class A delay by dropping the packet. Furthermore, we improve our algorithm when the calling and called users are both locate in the reversed crevice zone, the traffic will relay through a MEO manager satellite to reduce the delay. In this way, it has been shown that the delay of class A traffic significantly reduced. Above all, we have considered different traffic types and the situation of users located in special geographic locations such as reversed crevice zone. The time delay and packet loss rate characteristic curves of the simulation results shows a steady increase trend, indicating that the M-BMDP algorithm and its improved version have good stability, can meet the needs of the current satellite network development.



---

*Source: 4897698-2023-02-17.xml*