# Distributed Routing Strategy Based on Machine Learning for LEO Satellite Network

Authors: Zhenyu Na; Zheng Pan; Xin Liu; Zhian Deng; Zihe Gao; Qing Guo
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

As the indispensable supplement of terrestrial communications, Low Earth Orbit (LEO) satellite network is the crucial part in future space-terrestrial integrated networks because of its unique advantages. However, the effective and reliable routing for LEO satellite network is an intractable task due to time-varying topology, frequent link handover, and imbalanced communication load. An Extreme Learning Machine (ELM) based distributed routing (ELMDR) strategy was put forward in this paper. Considering the traffic distribution density on the surface of the earth, ELMDR strategy makes routing decision based on traffic prediction. For traffic prediction, ELM, which is a fast and efficient machine learning algorithm, is adopted to forecast the traffic at satellite node. For the routing decision, mobile agents (MAs) are introduced to simultaneously and independently search for LEO satellite network and determine routing information. Simulation results demonstrate that, in comparison to the conventional Ant Colony Optimization (ACO) algorithm, ELMDR not only sufficiently uses underutilized link, but also reduces delay.


---

## Body

## 1. Introduction

In last decade, with the widespread applications of high-speed mobile Internet and the rapid advances of space technologies, satellite network has become the inseparable component of global mobile communications. Because of global coverage, satellite network can provide reliable communication services to the regions without terrestrial networks. Since Low Earth Orbit (LEO) satellite has the relatively low orbit altitude, it has the advantages of low transmission delay and link loss. The invulnerability is another feature of LEO satellite network due to the following reasons. On the one hand, the networking of LEO satellites is more flexible. On the other hand, inter-satellite links make the communication between satellites independent of the terrestrial infrastructure. Therefore, LEO satellite communications draw much attention of academia and industrial world [1–4].However, the global coverage of LEO satellite network needs tens to hundreds of satellites because of the relatively small coverage. Moreover, LEO satellite network has the characteristics of short orbit period, highly dynamic topology, and frequent link handovers. In addition, the advanced physical-layer techniques oriented to the Fifth Generation (5G) mobile communications greatly enhance the data transmission rate leading to an explosive growth of network traffic [5]. In such a LEO satellite network, how to design a reliable, efficient, and robust routing strategy is the primary task to guarantee reliable data transmission [6, 7].Some routing strategies for LEO satellite network were put forward at home and abroad. When it comes to early routing strategies, their focus mainly concentrates on connection-oriented routing [8–10]. Due to their offline computation resulting in the lagged routing information, they were quickly replaced by dynamic and non-connection-oriented routing strategies [11]. Many strategies were proposed [12–14], which mainly focus on the so-called logical address. These strategies are ultimately converted into the problem of the shortest path. However, the overload and congestion at satellite nodes on the shortest path are not taken into account by the strategies. To overcome the shortcoming, the balanced-load and prediction based routing strategies draw researchers’ attention.[15, 16] proposed the routing strategies combined with load balancing. In [15], the authors hold that the overloaded satellite node should be bypassed to relieve network congestion. In [16], the authors utilize multiagent system and physical-layer information to make routing decision and then convert load balancing into a multiobjective optimization problem. However, the combination of multiagent, physical-layer information and multiobjective optimization makes the routing almost impractical for real-time services in long-delay environment. Because prediction can provide the information in the future, some references proposed prediction based routing strategies. In [17], a time series analysis based routing scheme was proposed. Though the prediction method is simple, it suffers from low prediction accuracy. In [18], a routing algorithm based on load balancing and congestion prediction was proposed, in which only the congestion state is predicted, but it results in incomplete routing information.Considering dynamic network topology, the approaches based on Artificial Intelligence (AI) were put forward [19–26]. Though some traditional Artificial Neural Network (ANN) based strategies take Quality of Service (QoS) into consideration, they are often time-consuming because of complex training process. Another disadvantage is that they only focus on current routing information without considering the future state. At present, machine learning (ML) catches the eyes of the academic world [27, 28] because it can highly improve the performance of algorithms by learning of experience. ML has already been applied to many fields. Similar to traditional ANN, the training process of ML is also time-consuming. The appearance of Extreme Learning Machine (ELM) is a breakthrough to enhance training speed [29]. A distributed routing strategy on the basis of ELM is proposed in this paper. Firstly, ELM is used to predict upcoming traffic load at satellite nodes. Then, mobile agents (MAs) collect network information to make routing decision using the predicted traffic load. Finally, according to the routing decision, adjacent satellite nodes dynamically adjust traffic load.


## 2. Traffic Distribution Density and Its Quantification

The traffic distribution density (TDD) on the surface of the earth has a nonnegligible impact on routing performance. Traditionally, most routing strategies only react to the traffic load of satellite node itself. In fact, if the TDD on the surface of the earth below the satellite is considered, a proactive routing decision can be taken in advance to enhance routing performance. There are three factors to influence TDD on the surface of the earth, including two natural factors and one human factor. The first natural factor is the land-sea distribution. Specifically, a satellite over the ocean is often in the state of light load, while a satellite over a city is frequently in the state of heavy load. Another natural factor is relevant to the earth’s rotation. Obviously, the regions in day time are heavier in traffic load than the regions in night time. The human factor is often associated with economic level. In general, the developed countries and regions are equipped with the advanced infrastructure. Figure1 presents the Gross Domestic Product (GDP) density in the world [30]. The imbalance of the worldwide economic development brings about the imbalanced development of telecommunications. In general, the regions with dense population and developed economics are abundant in terrestrial telecommunication infrastructure.Figure 1
GDP density in the world.We divide the surface of the earth into several grids, which are quantified according to GDP density. As demonstrated in Figure2, we use the numbers from 1 to 10 as traffic index to represent the TDD. Both longitude and latitude are divided into 24 and 12 equal portions, respectively. Since the ocean occupies 71.8% of the surface of the earth, the number 1 dominates vast areas in Figure 2. For the developed regions, such as Scandinavia, West Europe, East Asia, and North America, they are quantified with numbers from 8 to 10. For the sake of intuition, Figure 3 presents the tridimensional histogram of the quantified traffic density.Figure 2
Quantified grids of traffic distribution density on the surface of the earth.Figure 3
Quantified grids of traffic distribution density on the surface of the earth.Huang et al. proposed ELM in his pioneering paper in 2004 [29, 31]. ELM is a special simple and single hidden layer neural network, whose advantages include simplicity, fast speed, and global optimization. Especially, its training and testing processes are much faster than traditional ANNs. Huang et al. also proved that the random selection of node parameter of hidden layer highly reduces the network training time and ELM can realize universal function approximation [32]. In this paper, the incremental ELM [32] is used to predict upcoming traffic because it is not subject to overfitting. Because LEO satellite runs on its orbit at high speed, its traffic load changes with the location change of subsatellite point. ELM is used to forecast the traffic for the satellite over specific grids below subsatellite point.


## 3. ELMDR Strategy for LEO Satellite Network

In order to make routing decision, MA is used to collect and exchange path information for LEO satellite network. MA is the distributed and intelligent agent with mobility, which can decide its movement behavior between nodes by itself in a high-efficiency way. MA can be classified into forward MA and backward MA. The former is generated and sent by the source satellite node to explore path information, while the latter is produced by the destination satellite node. Both forward MA and backward MA have a maximum time to live (TTL) which is defined as the hop limits of a MA. If their hops exceed TTL, they are deemed to expire and destroyed directly. The intention of setting TTL is partially to avoid loop and lagging routing information. In addition, satellite node would generate prediction agent to get traffic information to revise a routing preference factor which is used to adjust the traffic from adjacent satellite nodes.In order to record and update routing information, a data structure is maintained by each satellite node which is comprised of the pheromone matrixT, data-routing table R, delay model D, link queue model L, traffic prediction model P, and local statistical model M. T and R are the functions of a “distance vector”, which is not the ordinary concept of distance but the probability representing the path condition. D stands for the expected delay between the current node and each possible destination node. L denotes local traffic information. P records the predicted traffic. Statistical model M maintains the time related information.The routing strategy of ELMDR is presented as follows.(  1) Behavior of Forward MA. For each interval Δt, forward MA expressed as Fs→d is produced, which is responsible for the collection of nonlocal routing information. Fs→d has the same priority as the information data and accurately records network state. The traversal time between arbitrary two nodes and the identifiers of all nodes from s to d are recorded in a private memory H. The next node is selected according to the following rule:(1)pi,j=1M0q<q1τij∑j∈Mτijq≥q1,where pij is the probability to select the link(i,j); M0 represents the node set adjacent to node i; and τij means the pheromone on the link(i,j).Loop routing should be removed from forward MA and an adjacent node is randomly selected as the next hop. If the constraints ofq<q1 and q≥q1 are not included in (1), after a while, the probability of an optimal path selected based on pheromone distribution would get close to 1 that means path search approaches standstill. In other words, even if the optimal path is congested, subsequent data packets are still transferred along the path regardless of other potential idle paths. Such a case is considered by (1). q is a stochastic number between 0 and 1, while q1 is a constant between 0 and 1. A smaller q1 can be empirically selected to stop the search standstill. According to (1), forward MA selects the next node according to either the distribution of pheromone (i.e., when q≥q1) or random selection probability (i.e., when q<q1). As a result, though the probability to select the optimal path is still high, it is not equal to 1. The use of a small probability q1 makes some forward MAs explore other potentially optimal paths. When the originally optimal path is getting bad, forward MA can quickly discover the newly optimal path.(  2) Behavior of Backward MA. After forward MA Fs→d gets to node d, it is automatically deleted. In the meantime, the backward MA expressed as Bd→s, which includes all information collected by Fs→d, is generated by the destination node d. Bd→s goes back to node s along the same path passed by forward MA but from d to s. Carrying routing information, backward MA can quickly return to node s because of its higher priority than information data. All intermediate nodes update their routing tables according to the delay information provided by backward MA. The update rules are given below:(2)τijt+1=1-ρ·τijt+∑b=1mΔτijbt+Δτij′tΔτijbt=PhdblinkLi→jpassed byBd→s0otherwise.where ρ is the evaporation factor of pheromone whose value is between 0 and 1; the term of ∑b=1mΔτijb(t) is the pheromone increment on link(i,j) taken by Bd→s; Ph is the pheromone brought by Bd→s; db is the latency on link(i,j); and the term Δτij′(t) stands for the pheromone increment given to the agents to find the new optimal path. Specifically, when a new optimal path is discovered, most agents still select the originally optimal path and leave their pheromone. By using the pheromone increment, convergence speed of routing search can be enhanced.(  3) Data Update. For each intermediate satellite passed by node k, three actions are taken by backward MA, including to update M, evaluate the quality of path from node k to node d, and update local paths. Referring to the local traffic model Md, the path from node k to node d is assessed based on traversal time Tk→d. The smaller Tk→d is, the higher the path weight is. Based on the weight, all paths which use d as the destination node and k as the next hop are strengthened.μ d is the mean of Tk→d, while σd2 is the variance of Tk→d. Wd is the optimum traversal time of recent W values of traversal time experienced by forward MA. They are updated according to the following:(3)μd⟵μd+ηTk→d-μdσd2⟵σd2+ηTk→d-μd2-σd2Wd=Tk→dwhenTk→d<Wd,where η is weight factor.After updatingM, the path passed by Fs→d is evaluated according to the following expression:(4)r=c1WdTk→d+c2Isup⁡-Iinf⁡Isup⁡-Iinf⁡+Tk→d-Iinf⁡.Here, r is a preference factor. It represents the quality of the path found by forward MA. The aim of evaluation is to update pheromone table and routing table by the preference factor. Isup⁡ and Iinf⁡ are the estimations of the maximum value and the minimum value of μd. c1 and c2 stand for the weighting factors. r is revised according the predicted traffic. In general, when satellite flies over the region with heavy/light load, the potential node congestion/idleness is reported based on the corresponding large/small traffic index. When the predicted traffic is heavy, it means that satellite runs from the region with light load to the region with heavy load. In this case, the traffic sent to the satellite from its adjacent satellite nodes is reduced by using the revised r. When the predicted traffic is light, the traffic sent to the satellite from its adjacent satellite nodes is increased by using the revised r. Thus, the preference factor r should be adjusted according to the traffic model P.(  4) Prediction and Routing Update. Each satellite node maintains a data structure which records required information including the local traffic. The training process for ELM in each source node is started since source node sends data and forward MA goes to destination node. When backward MA returns to source node, a prediction agent is activated. Factually, the training process has been in progress before the activation. Thus, the required predicted traffic can be quickly given by the prediction MA. The future state of satellite node, the preference factor, and routing update are determined according to the predicted traffic.LetΔt denote the prediction interval, P^ denote the traffic load forecast at the time t+Δt, Q denote the queue size, q(t) denote the queue occupancy state at the time t, C denote the capacity of ISL, davg denote the packet length in average, and B denote the router buffer capacity, respectively. The following metric named congestion indicator is defined to characterize the load state of satellite node:(5)ξt=Q-qt·davg+C·Δt-P^B.The revising factor γ is defined as(6)γ=11+exp⁡-aξ.In (6), a denotes the slope parameter. The routing update is presented below:(7)τijt+1=1-ρτijt+γ·∑k=1mΔτijkt+Δτij′t.(  5) Link Handover Strategy. Since link handover in LEO satellite network would have a negative impact on routing performance, the corresponding routing strategy must adapt to links’ disconnection and reconnection. In view of the periodicity and predictability of satellite network topology, the link states of disconnection and reconnection can be calculated and stored in advance to facilitate the execution of link handover strategy. In order to illustrate the link handover strategy, we first specify the topology of LEO satellite network. Either Walker constellation or polar-orbit constellation has the topological snap demonstrated in Figure 4, in which the solid lines represent permanent intra-orbit link, while the dashed lines stand for inter-orbit links.Figure 4
Typical topological snap of LEO satellite network.As shown in Figure4, we suppose that a link handover happens to the inter-orbit link between LEO_101 and LEO_201. The influenced satellites mainly are LEO_101 and LEO_201, as well as their adjacent satellites. As illustrated in Figure 4, the four links of LEO_101 which connect LEO_102, LEO_201, LEO_111, and LEO_601 are numbered with 1, 2, 3, and 4, respectively. When the link between LEO_101 and LEO_201 is disconnected, the probability in the routing table of LEO_101 to send data packets to LEO_201 is proportionally allocated to LEO_102, LEO_111, and LEO_601, respectively. Likewise, LEO_201 takes the same action as LEO_101. We have the following expression:(8)pLEO_201,d=0∀d∈N,d≠LEO_101pn,d=pn,d+pn,d∑n=1NLEO_101-1pn,d·pLEO_201,dn∈NLEO_101,n≠LEO_201,where NLEO_101 is a collection including the satellite nodes whose data packets are sent to LEO_101. NLEO_101 represents the number of satellite nodes in the collection NLEO_101.When the link between LEO_101 and LEO_201 is reconnected, the probabilities of links numbered 1, 3, and 4 are allocated to link 2 according to the following rule. Specifically, the number of hops from LEO_101 to the destination node is calculated. The smaller the number of hops is, the higher the probability of link 2 is [33]. Correspondingly, LEO_201 takes the action similar to LEO_101. Thus, we have(9)pLEO_201,d=dist⁡LEO_201,d∑n=1NLEO_101,d-1dist⁡n,d∀d∈N,d≠LEO_101,n∈NLEO_101,n≠LEO_201pn,d=pn,d·1-dist⁡LEO_201,d∑n=1NLEO_101,d-1dist⁡n,d∀d∈N,d≠LEO_101,n∈NLEO_101,n≠LEO_201,where dist⁡(n,d) is used to calculate the number of hops on link(n,d).When link disconnection happens, routing table can fast-track it according to (8) because neither MAs nor data packets will be forwarded over the disconnected link. Considering the frequent link handover in LEO satellite network, if the routing strategy is always behind the change of network state, routing performance is bound to be affected. Fortunately, the periodicity and predictability of LEO satellite network topology make the real-time tracking of link handover possible.(  6) Main Flow of ELMDR Strategy. The main flow of ELMDR strategy is listed in Algorithm 1, which illustrates the process of routing establishment, update, and revision.Algorithm 1:Main flow of ELMDR strategy.
begin initialize routing table and data structure (A)satellite node generates and sends forward MA (B)select the next node according to (1) (C)handover judgement according to (8) and (9) (D)if loop avoidance == true go to step (E) else go to step (B) (E)record delay at intermediate node (F)forward MA arrives at destination node (G)destination node generates and sends backward MA (H)backward MA returns to source node (I)handover judgement according to (8) and (9) (J)update routing table according to (2) and data structure according to (3) (K)prediction MA is activated to predict traffic at satellite node (L)revise routing table according to (4)–(7) End


## 4. Simulation Results and Discussions

The performance of ELMDR is dependent on the accuracy of traffic prediction method to a large extent. In order to validate the prediction effect of ELM, we select the Internet data trace which is available on the website:http://ita.ee.lbl.gov/index.html. There are many data traces last updated on April 9, 2008, on the website. We use the trace of BC-pAug89 which started from 11:25 to 12:17 (about 3143 s) on August 29, 1989. 1,000,000 packets are included in the trace. As IP packets to a given destination in the modern Internet backbone present high self-similarity [34], there are no accurate models to predict Internet traffic [35]. We select one percent of the trace to train ELM. Because of traffic similarity, the data segment can be selected arbitrarily in the trace. We select the data in the first 5 s as the testing data. In view of the randomness of the time that a packet arrived at measurement hardware, we count the bytes in each interval of 0.04 s from the first to the 2140th packet captured (about 5 s). We implement the traffic prediction by using ELM based on MALTAB. The real traffic and the predicted traffic by ELM are compared and demonstrated in Figure 5. It is obvious that ELM can follow the change of real traffic only with minor errors. When real traffic sharply increases or decreases, the predicted traffic is often slightly below or above real traffic because of both the high similarity and the passiveness of prediction algorithm. Overall, ELM is competent for traffic prediction in the proposed routing strategy.Figure 5
Real traffic and predicted traffic.To verify the proposed routing strategy, the Iridium satellite system with the topology depicted in Figure4 is used as the simulation scenario. The following parameters are used in our simulations: a=1, ρ=0.75, q1=0.2, c1=0.7, and c2=0.3; the bandwidth of ISL is 10 Mbps. The simulation scenario is presented in Figure 6. We suppose Gateway 1 and Gateway 2 are connected to LAN1 and LAN2, respectively. LAN1 sends data to LAN2 10 s later. All scenario parameters are implemented on OPNET. The Ant Colony Optimization algorithm abbreviated as ACO [36] and proposed ELMDR are compared.Figure 6
LEO satellite network scenario.Figures7 and 8 present the link utilization performance of ACO and ELMDR. When LAN1 starts sending data to LAN2, the optimal path from LEO_301 to LEO_401 for both ACO and ELMDR is utilized with the similar link utilization. However, ACO only selects one optimal path, while ELMDR offloads a part of traffic to the suboptimal path from LEO_301 to LEO_302. In simulation, the training time and the testing time are less than 0.1 s. As shown in Figure 8, though the activation of prediction MA and the training and testing process need time, the discovery of suboptimal path for ELMDR is still earlier than ACO mainly because ELMDR can avoid path search falling into standstill and find suboptimal path promptly. Therefore, the discovery of paths from LEO_301 to LEO_302 and from LEO_301 to LEO_311 for ELMDR is earlier than ACO. It should be noted that the link utilization of the path from LEO_301 to LEO_201 for both ELMDR and ACO is zero, because the path is neither selected by ELMDR nor selected by ACO.Figure 7
Link utilization of ACO.Figure 8
Link utilization of ELMDR.Figure9 presents the queuing delay of LEO_301 in the case of link handover. Compared with ACO, as shown in Figure 9, the queuing delay for ELMDR caused by link handover changes slightly mainly because ELMDR can fast update routing table and follow the change of link state. Since the links from satellite LEO_301 to satellite LEO_302 and from satellite LEO_301 to satellite LEO_311 are utilized, a part of data packets avoids being sent to the originally congested node LEO_301. Though the distance between source node and destination node would increase, the queuing delay for LEO_301 is highly decreased.Figure 9
Queuing delay with handover for LEO_301.Figures10 and 11 present packet loss ratio (PLR) and average packet delay of ACO and ELMDR, respectively. In Figure 10, when sending rate is relatively low, both ACO and ELMDR provide almost the same PLR. However, when sending rate is high, ELMDR takes a slight lead. Because traffic prediction is adopted by ELMDR, data is diverted to suboptimal path. As a result, the packet losses due to timeout over congested link are decreased. Figure 11 demonstrates that ELMDR has slightly higher average delay than ACO. Though the paths from LEO_301 to LEO_302 and from LEO_301 to LEO_311 would increase the communication distance between source node and destination node, the sacrifice in average delay is affordable considering the lower link handover delay, PLR, and higher link utilization.Figure 10
Packet loss ratio.Figure 11
Average delay.


## 5. Conclusions

In this paper, a distributed routing strategy based on machine learning for Low Earth Orbit satellite network is put forward. The traffic load on the ground is analyzed and quantified, and then Extreme Learning Machine is adopted to forecast the traffic load of satellite node. The proposed routing is realized based on distributed mobile agents, which can search for, collect, update, and revise routing information. Prediction mobile agents revise routing by a preference factor so that congestion can be avoided. The additional link handover strategy ensures that traffic load can be diverted to the appropriate satellite nodes according to the probability in the case of link disconnection or reconnection. Simulation results demonstrate that, compared with ACO, the proposed ELMDR provides suboptimal path in the case of link handover and has low packet loss ratio and handover delay at the cost of slighter average delay.



---

*Source: 3026405-2018-06-14.xml*