An Adaptive Routing Algorithm for Integrated Information Networks

Feng Wang,Dingde Jiang＊,Sheng Qi

School of Astronautics and Aeronautic,University of Electronic Science and Technology of China,Chengdu 611731,China

Abstract: The integrated information network is a large capacity information network that integrates various communication platforms on the ground,at sea,in the air and in the deep air through the inter-satellite and satellite-ground links to acquire information accurately,process it quickly,and transmit it efficiently.The satellite communication,as an important part of integrated information networks,is one of main approaches to acquire,process and distribute communication information and resources.In this paper,based on current researches of the satellite communication network,we put forward a 3-layer satellite communication network model based on the Software Defined Network (SDN).Meanwhile,to improve current routing policies of the Low Earth Orbit (LEO) satellite communication network,we put forward an Adaptive Routing Algorithm (ARA) to sustain the shortest satellite communication link.Experiment results show that the proposed method can effectively reduce link distance and communication delay,and realize adaptive path planning.

Keywords: integrated information network; software defined network; satellite communication; routing policy; adaptive path planning

I.INTRODUCTION

The integrated information network is a combination of the wide-coverage satellite network and the low-latency terrestrial and low-altitude communication network [1].It can realize heterogeneous network interconnection,global resource management,and various communication service.It has been the irreplaceable communication carrier.As shown in figure 1,the integrated information network architecture includes satellite backbone network,deep space communication network,stratospheric communication network,terrestrial communication network,and various cross-layer information transmission methods.Among them,satellite network is an important part of the integrated information network.It relies on the satellite communication with large-scale coverage and long-distance transmission,flexible access,etc.,to become the main means of acquiring,integrating,distributing and processing spatial information and resources,which plays an important role in the integrated information network.The satellite communication can meet communication requirements of oceans and remote areas which are difficult to be cover by terrestrial communication networks.It has the advantages of seamless coverage and take no account of the communication distance and costs.The satellite communication network consists of three parts:Geosynchronous Earth Orbit (GEO) satellites,Medium Earth Orbit (MEO) satellites,and Low Earth Orbit (LEO) satellites.Among them,due to the long information transmission delay of GEO satellites and MEO satellites,nowadays they are difficult to perform the real-time satellite communication with the rapid increase of the traffic caused by the various terminals.In contrast,due to low orbit,easy launch,excellent performance of satellite-ground links,and low channel delay,the LEO satellite has become one of main carriers of satellite communications.With the raise of the inter-satellite link (ISL) and inter-orbital link (IOL),LEO satellite networks,which provide communication services by satellite constellations composed of multiple LEO satellites through ISL and IOL,have become the mainstream.At present,the typical LEO satellite constellations are the polar orbit satellite constellation represented by the Iridium system and the inclined orbit satellite constellation represented by the Walker system [2].

Fig.1.The integrated information network architecture.

The routing technology has always been one of research hotspots of satellite communication networks.In a satellite network composed of multiple satellites,there are often multiple reachable paths between the source satellite and the destination satellite,and the optimal quality path needs to be calculated according to the path cost.Therefore,the routing technology has become one of necessary means to improve communication quality in the modern satellite communication network [3].The routing problem refers to the path calculation between the nodes in the network,which is the basis for realizing the interconnection between satellites in the space.This will directly affect the practical application of satellite networks.However,the LEO satellite has a smaller coverage area and the satellite communication link switches frequently.This time-varying topology brings a great challenge to the routing algorithm design.In the actual communication scenario,two communication targets on either side of the earth send communication requests to access the LEO constellation.Since the single LEO satellite moves fast relative to the ground,it can only provide users with communications for few minutes.At the same time,due to the relative motion,the distance between the satellites becomes far apart after a few minutes.Therefore,it is necessary to develop a suitable routing strategy based on the LEO satellites trajectory to ensure that communication objectives are always in good communication quality through timely link switching.

In recent years,scholars have carried out some research on communication routing strategies of the LEO satellite constellation.Xiao et al.[4] evaluated the impact of LEO constellation topologies and routing strategies on the communication link throughput.It was believed that the topology strategy of the reverse link could increase the number of ISL.In the LEO satellite network,the routing algorithm combined with the reverse ISL topology could reduce the packet loss rate and realize the optimization of the network capacity and robustness.However,the author only gave a general strategy and there was no specific path planning solution.Duan et al.[5] proposed the satellite handover to ensure the reliability of the communication link.Based on the user’s location information,the nearest satellite was selected as the access satellite at the time of handover.The method could reduce the access delay of the user and ensure the continuity of the communication,but did not analyze the continuity of the inter-satellite communication link.Tang et al.[6] proposed a multipath cooperative routing protocol for LEO satellite networks based on network coding,which could accelerate data transmission by transmitting different parts of data flows along different link paths.However,this method did not discuss the optimization of the real-time path.Zhu et al.[7] proposed the use of the Software Defined Network (SDN) to divide satellite networks into the control plane and data plane.Based on that,a Software Defined Routing Algorithm (SDRA) was proposed.The information could bypass the congested nodes and reduce the queuing delay after controller’s calculating.The SDN architecture could help to achieve better path planning,but the author did not do depth research on the possible changes of a specific path.It can be seen that the LEO satellite constellation has become the main bearing object of information in the satellite communication network because of its low orbit,easy launch,superior performance of satellite ground link,and small channel delay.However,due to its smaller coverage area and frequent satellite switching,the routing strategy for the LEO satellite network needs real-time nature and adaptation to change the communication link so that we can ensure the continuity of the communication process.This paper introduces the idea of the SDN architecture and proposes an adaptive routing algorithm for the integrated information network.Among them,the GEO satellite is the control satellite,the MEO satellite is the auxiliary path-finding satellite,and the LEO satellite is the underlying information forwarding satellite.The GEO satellite can calculate the optimal communication link and resource scheduling,and the LEO satellite carries out the data forwarding function.Further,the GEO satellite can adjust the inter-satellite link in a real-time way to ensure optimal communications between LEO satellites,to reduce network communication delay and improve the communication adaptive ability of the integrated information network.In addition,our previous work [8-11] is very helpful to the motivation and work in this paper.

The rest of this paper is organized as follows.Section II proposes an adaptive routing algorithm based on the analysis of inter-satellite communication links.Section III verifies the proposed adaptive routing algorithm through simulation experiments.Finally,we conclude our work in section IV.

II.ADAPTIVE ROUTING ALGORITHM

The LEO satellite communication coverage area is small and satellite switching is frequent,which are the challenge to study the routing algorithm with low delay and stability.Before proposing the adaptive routing algorithm,we first solve how to find the optimal path among the two targets.Firstly,the satellite communication link model includes inter-satellite links and terrestrial links.The establishment of the communication link in satellite communications has the following properties:

Physical Visibility:When satellites communicate with each other or the satellite communicates with ground targets,whether in laser or in microwave,the primary condition for the formation of a communication link is whether two nodes are visible.It depends on the relative position of satellites,ground targets,and the Earth.If the Earth blocks the connection between satellites,they are physically invisible and cannot form a communication link,or otherwise they can communicate.The detail is shown in figure 2.We setReas the radius of the Earth,Sas the satellite flying around the Earth,Das the distance of inter-satellites or the distance of ground-satellite,andHas the distance from centerOto destinationD.αindicates the angle between the inter-satellite and the earth-satellite centers.The relative positions between the satellites are as follows:

Fig.2.Satellite physical visibility model.

Algorithm 1.Satellite access algorithm.Input:Communication source A,Communication target B;Input:LEO satellite height HL; Output:Accessed Satellite A’,B’;1:A B D H R' '= = = -2 2;max L e= 3:if then 2:for do i 1 to n D ＆＆D '≤DiA iA ,max ,≤A 4:A L'= i;5:end if 6:if then D ＆＆D '≤DiB iB ,max ,≤B 7:B L'= i;8:end if 9:end for 10:returnA',B'

● The distance between satelliteS1and satelliteS2isD1,andH1is the distance fromOtoS1S2.If the following equation holds then the satellites are physically visible and can form an inter-satellite communication link.

● The distance between satelliteS2andS3isD2,andH2is the distance from the center of the sphere toS2S3.If the below equation holds then the satellites are not physically visible and it cannot establish the inter-satellite links.

● The distance between satelliteS1and satelliteS4isD3,andH3is the distance from the center of the sphere to the extension ofS1S4.If the below equation holds the satellites are physically visible and can form an inter-satellite communication link.

The above are three cases of physical visibility between satellites.For the visibility of the satellite and ground,since the LEO satellites are moving in their respective fixed orbits,the elevation angle of the ground target is not considered.It can be seen from figure 2,when the communication link betweenS2and the ground targetGis tangent to Re,the critical value is reached.The value of the distance at this time reaches the maximum valueDmax.That is,the condition of establishing a communication link between satellite and ground is:

From the above,physical visibility between nodes is the most basic and important reference factor when designing inter-satellite links and satellite-ground links.On the basis of physical visibility,the closer the distance of the satellite to the ground target,the shorter the delay of the satellite-ground access.It can ensure that the satellite communication link established at this time can last for a period of time,which will not be disconnected instantaneously,causing the communication link invalid.Therefore,when two ground targets request the satellite communication,we use the LEO satellites closest to the two targets at this time as the communication access satellites.According to the above theory,the satellite access algorithm is shown in Algorithm 1.It can be known from Algorithm 1 that after determining the location of theGcommunication target,the maximum visible distance to the satellite and ground is first calculated,and then the satellite closest to the target is searched as the access satellite in the visible range,thereby reducing the calculation.

Multi-coverage:In the planning of the satellite-ground link,the ground target is often physically visible to multiple satellites at the same time.According to the LEO satellite constellation such as the classic Iridium system,when any target on the ground wants to access the satellite network for communications at any time,the number of the covered LEO satellites is more than one.In the case where the ground users are randomly distributed relative to the satellites,the multiple coverages of the satellite result in different coverage times between different regions.Among them,the coverage time of a single satellite to the ground target can be obtained from figure 2.Without considering the elevation angle of the ground target,the link betweenS2and the ground target reaches a critical value when tangent to the Earth,thenS2will be tangent twice withG.The time interval in the two state is the coverage time ofS2toG.If the satellite period isT,the maximum coverage time ofS2toGis

According to the multi-coverage nature of the LEO constellation to the ground target,it is particularly important to select which satellite to access when accessing the satellite network.Access to different satellites will result in different communication coverage times,which affects the planning of subsequent inter-satellite communication links.

Periodicity:Each satellite periodically moves around the Earth.In the LEO satellite constellation,and all satellites operate at the same altitude.Therefore,the satellite’s motion cycle is the same.From the periodicity of the satellite motion,the inter-satellite link and the satellite-to-ground link also periodically open and close and change the length.This will affect the calculation of the satellite link delay.We set the complete communication time between two satellites asT.For a complete communication link,the below equation is obtained

Then the communication timeTtotalof the entire link is:

Therefore,in the inter-satellite communication path planning,when considering the periodic motion of the satellite,it is necessary to not only select the link with better communication service at the current time but also consider the reliability and stability of communication links.This will help to select the current optimal communication path strategy at different times.

Physical visibility,multi-coverage,and periodicity properties are three basic aspects that need to be paid attention to when calculating inter-satellite and satellite-ground communication links.They are the basis of communication link planning.However,relying on these three aspects can only perform the static calculation of the satellite communication link.In the face of highly dynamic LEO satellite motion,the link that was connected at the last moment is likely to lose visibility in the next moment.Therefore,how to design a complete and adaptive routing scheme becomes a challenging problem.

Fig.3.Dijkstra algorithm model.

To address the problem that the traditional satellite network has high requirements of inter-satellite communication resources for satellite processing and switching,this paper uses the SDN architecture to solve the mentioned shortcomings.As shown in figure 1,under the 3-layer satellite network structure composed of GEO-MEO-LEO,the data plane and the control plane in the satellite communication network can be separated.Because GEO is relatively static on the ground and can achieve global coverage in a small amount,it can better process the communication requests of ground targets and calculate inter-satellite communication links continuously.Hence,GEO is designed as the top control satellites,responsible for calculating the optimal communication link and resource scheduling.MEO is designed as the auxiliary path-finding satellite that helps GEO collect information on ground targets and LEO satellites near targets.LEO is designed as the underlying forwarding satellite and is only responsible for receiving commands from GEO and carrying data forwarding functions.Under the SDN architecture,satellites at different levels can be rationally divided according to their own motion characteristics to achieve optimal resource allocation in satellite networks.With the programmable function of SDN,GEO can easily realize the update of the forwarding rules in the LEO network,so that it will be hold low data transmission delay and small resource consumption.Therefore,the adaptive routing method proposed in this paper is based on the SDN satellite network architecture.

The SDN architecture provides a global perspective for the entire satellite network,and the GEO can master the entire LEO satellite constellation topology in real time.Thereby,it is able to calculate the best communication link between two satellites.If using satellite networking for communications,we then must solve the routing problem.Before performing adaptive inter-satellite communication link planning,we first consider the optimal routing algorithm at a certain moment.In general,a route is that,in a network composed of multiple nodes,satellites from a source node,looking for one or more paths to one or more destination nodes,so that information can be transmitted from the source node to destination node along these paths.There are often many feasible paths from the source node to the destination node in the network.Thus,how to choose a path to transmit information is the problem solved by the routing scheme.The routing technology needs to know the network topology.It often has a series of important constraints in the routing calculation process.In this paper,we have improved the Dijkstra algorithm.The Dijkstra algorithm is the shortest path algorithm for calculating the distance from a vertex to the remaining vertices according to the weight.It aims to solve the shortest path problem in the directed graph.The model is shown in figure 3.Satellites from source node L1 look for the next node with the lowest weight.In this way,the final path is the smallest weight path.

In the satellite communication network,the communication link connects the communication source node with the destination node.As the distance between two satellite nodes can be considered as a weight parameter,it is feasible to use the Dijkstra algorithm for the shortest communication link planning between satellites.Due to the complex topology of the LEO satellite constellation,it is not necessary to perform traversal distance calculations for all nearby nodes when looking for a path.So we improved the Dijkstra algorithm by adding some column constraints.First,we number all the satellites in the LEO satellite constellation.And set the orbit number asiand the satellite number asj.For all satellites,there are

whereLijrepresents thejthsatellite in theithorbit.After the accessed satellite is determined,it is assumed that the first accessed satellite isLij.If its target satellite isLnm,Lijneeds to determine a nearby relay satelliteLij''to forward the communication data.Here,we consider the distance between satellites as the weight in the Dijkstra algorithm.At the same time,according to the theory described above,it is necessary to determine whether the selected relay satellite can communicate with each other.That is to determine ifLijandLij''exist.We can obtain the following equation

In the satellite constellation,we believe that the satellites in the same orbit have similar motion states,and the use of adjacent satellites in the same orbit as the next relay satellite can better maintain communication quality.Therefore,we empirically set a lower weight for adjacent satellite nodes in the same orbit,namly

Therefore,the final next relay satellite target can be expressed as follows:

where we limit the search scope to the satellites in the same orbit ofLijand the nearby two orbits,and set the distance betweenLijand the satellite in the same orbit interval as the maximum search distance.Through the above constraints,the next nodeLij''with the minimum weight is found,and that is the next relay satellite.According to the Dijkstra algorithm,the remaining relay satellite is searched until the target satellite is linked,then the path is found,which is the optimal at the current time.At the same time,considering the traffic carried by each satellite,we calculate the average communication links (ACI) carried by each satellite at the current moment as the benchmark to increase or decrease the weight of each satellite link.For the link below ACI,the weight is reduced to increase its probability as the optimal link.For links over ACI,the link weight is increased,thus reducing the probability of being chosen.After that,the load balance of the satellite communication network is guaranteed.Algorithm 2 represents the minimum inter-satellite link algorithm steps,and the detail process is shown in figure 4.

Adaptive path adjustment:According to the disccustion above,for communication sources and targets connected to the satellite communication network,the satellite coverage is greater than 1 at each moment,so that satellite access can be achieved at any time.So at any given moment,we will let the satellite that is closest to the target access to the communication target.For GEO,firstly it needs to select satellites that can be accessed,and then select the one with the shortest distance to the target to calculate the optimal path.In the SDN satellite structure,the GEO,as the controller,can not only obtain the entire satellite network topology in the current time slot,but also predict in advance the topology of all the later time slots according to the regular motion of satellites.In this way,before the arrival of the next time slot,the GEO can determine which satellite nodes may be added or deleted and formulate the forwarding rules of the next time slot in advance.Hence,information can be forwarded directly when new satellites are connected.This is the first step of adaptive adjustment of our proposed satellite routing algorithm.However,LEO satellites are highly dynamic,so the optimal path at the previous time may lose link visibility at the next time.Therefore,it is necessary to make timely adjustments to the link to achieve real-time optimal path.In this case,after the GEO controller has configured the optimal path for the target,it will monitor the path change in real time within the sustainable communication time range of the link,and it can switch in time when there is a better path.At the same time,GEO will recalculate the new optimal path when the satellites that cover communication source and destination change,thus keeping the target under the optimal communication link at all times.

Algorithm 2.Routing algorithm.Input:Accessed Satellite A’,B’;Input:Satellite A’,B’ number Lij ,Lkp;Output:The shortest path P[];1:P[0]= A’;2:w DAB 0= (',');3:for do DAB＞4:for do (',') 0 all the satellites from i-1 to i+1 5:if then ≤ ±6:wL L DL LHLL R DLL DLL( ,) ＆＆ ( ,) ( ,)＞ij ij e ij ij ij ij '' '' ,2= ; 7:end if 8:if then( ,) ( ,)ij ij ij ij '' '' ' i i=9:wL L DL L× ;10:end if 11:if wL L w DL B DAB( ,) ( ,)0.7=ij ij ij ij '' ''( ,) ＆＆ ( ,') (',')＜ij ij ij '' 0 ''＜12:w wL L 0= ( ,)ij ij;''13:end if 14:endfor 15:ACI(Lij'')de ciotetn;15:Pm L[]= ij'';16:m m= +1;17:A L'= ij'';18:endfor 19:returnP[]

Fig.4.The flowchart of the minimum inter-satellite link algorithm.

Algorithm 3.Adaptive routing algorithm.Input:Accessed Satellite A’,B’;Input:The current optimal path P[]Output:Adaptive accessed satellite A’,B’ and optimal top-k path Pnew[];1:for do= total 2:A’,B’=Algorithm 1; // find new accessed satellite 3:Pnew[]= Algorithm 2; // find new shortest path 4:end for 5:returnA',B'andP [] t 0 to T new

Further,relying on a large number of calculations and observations,a basic rule of satellite routing change is found that although the high dynamics of the satellites motion leads to the variation of the optimal route,its optimal top-k routes are usually stable.That is,the communication link between satellites is always switched among certain routes within a certain period of time.This rule will guide us to further reduce the computational space and reduce the delay of information transmission.When calculating the optimal communication route for the first time,the controller can not only calculate the optimal communication path at the current moment,but also calculate the optimal top-k paths to generate Alternative Path Pool (APP).When the communication link needs to be switched,the controller can directly select the current optimal communication link in the APP instead of re-calculating the optimal route based on the topology.This greatly reduces the computation time of the controller and further reduces the communication delay between terminals.This is the further step of adaptive adjustment of our satellite routing algorithm.This adaptive model is shown in figure 5.Based on the above discussion,the adaptive routing algorithm steps are presented in Algorithm 3.

III.SIMULATION RESULT AND ANALYSIS

Based on the simulation software STK and MATLAB,this paper uses MATLAB to connect with STK in real time to obtain LEO satellites track and perform adaptive routing algorithm to control LEO link generation and switching.In the satellite communication system,the used LEO constellation currently includes the polar orbit satellite constellation represented by the Iridium system.

The simulations in this section are primarily for LEO communication satellite.Therefore,we refer to the Iridium system to establish a satellite network scenario in the integrated information network in STK,as shown in figure 6.The satellite parameters of each layer of the track are shown in Table 1.The low-orbit communication satellite (Iridium system) directly form a communication link for the users on the ground adaptively.The scenario is that the communication users on the ground are two early warning aircraft,one from Chengdu to Beijing and the other from New York to London.The two warning aircraft on different sides of the Earth rely on the LEO satellite system for real-time communication.In order to verify the feasibility of our algorithm,we compare with other two methods in some characteristics (ARA,non-adaptive algorithm,and DTN) in the simulation such as delays,network robustness,and the communication costs of links like the hop count.

We counted the changes in the communication links of the three methods within 220 minutes,as shown in figure 7.In most of the time,the time delay of the proposed ARA scheme is much smaller than that of the delay tolerant networks (DTN) and non-adaptive algorithm (UnARA) and no more than 35ms.Each change in the APA curve represents an adaptive update of the communication link at that time to select the best path.Due to the communication transmission scheme of DTN is based on information storage and forwarding,When the current link cannot transmit information,the communication data will be temporarily stored at the node where the link is broken,and a new reachable path will be found to continue passing information.Therefore,it can be seen from the figure that there is a small time interval between each change of DTN link,and the communication link delay of DTN is particularly unstable,up to about 47ms.The UnARA method maintained the same good communication delay as the ARA method at the beginning,but because the communication link remained unchanged and lacked self-adaptability,the communication link is disconnected at 60min,and the connection is not reconnected until 180min.Therefore,by time delay comparison of the above methods,we can see that the ARA method not only has low communication delay,but also can keep the communication link in the connected state all the time with smaller latency.

Fig.5.Adaptive adjustment model of the inter-satellite path.

Fig.6.Three-layer satellite network model.

Fig.7.Time delay comparison.

Table.I.Basic parameters of the three-layer satellite.

Fig.8.Network robustness comparison.

Fig.9.Node hops comparison.

The network robustness comparison of the three methods is shown in figure 8.Here we define that as network nodes increase,the more potential communication links available at the same time,the more robust the network becomes.As can be seen from the figure,as the number of network nodes increases,the network topology becomes more complex and the visibility probability between nodes increases.Therefore,for ARA,more communication links will be filtered out at the same time.Although there is only one optimal communication link,if one LEO satellite fails to connect to the network,the ARA can immediately choose the best link in the alternative to keep the communication.However,the DTN and UnAPA methods are unable to deal with the sudden failure of communication link due to the lack of alternative communication links.Therefore,their network robustness is always maintained at a low level.

In LEO satellite network,the more nodes take part in a communication link,the more influence it will have on the communication quality considering that each node will read in and output data.Therefore,network hop is also an important index to measure the quality of communication links.Figure 9 compares the number of hops of communication links in three methods at different times.It can be seen from the figure that the ARA method is always stable in the 3-4-hop.The UnARA method disconnects the communication link after keeping 3 hops for a period because the communication link does not change.The hop number of the DTN method is unstable because its routing strategy will be reset when the link is broken,so it cannot maintain a stable hop number.

From what has been discussed above and based on the three aspects respectively,we compare three routing scheme performance of APA,UnAPA,and DTN.Through the above simulation,we can clearly see that the adaptive routing algorithm shows better performance compared with the other two algorithms,which makes the proposed approach applicable.

IV.CONCLUSIONS

Satellite communication is an important part of the integrated information network.This paper proposes an adaptive satellite communication routing algorithm based on SDN architecture,which can not only find the shortest communication link between satellites,but also optimize the communication link in real time according to satellite motion.Simulation results show that our method is promising.

ACKNOWLEDGMENTS

This work was supported in part by the National Natural Science Foundation of China (No.61571104),the Sichuan Science and Technology Program (No.2018JY0539),the Key projects of the Sichuan Provincial Education Department (No.18ZA0219),the Fundamental Research Funds for the Central Universities (No.ZYGX2017KYQD170),and the Innovation Funding (No.2018510007000134).The authors wish to thank the reviewers for their helpful comments.Dr.Dingde Jiang is corresponding author of this paper (email:jiangdd@uestc.edu.cn).