Sage Journals: Discover world-class research

Abstract

Satellite networks provide complete connectivity and worldwide data transmission capability for constructing the Internet of Things. However, because of the varying Internet of Things traffic density, satellite networks may endure imbalanced traffic requirements and frequent link congestion. To effectively resolve these problems and optimally transmit Internet of Things data, a novel hybrid global-local load balancing routing scheme for Low Earth Orbit satellite networks is proposed in this article. Hybrid global-local load balancing routing scheme enables satellites to route Internet of Things traffic through global planning and local real-time adjustments in two steps. In hybrid global-local load balancing routing scheme, given the predictive nature of Internet of Things traffic distribution and Low Earth Orbit satellite networks, the inter-satellite traffic demand is decomposed into a predictable long-range baseline and unpredictable short-range fluctuations. A global strategy is employed first for preliminary global traffic allocation based on long-range baselines, and a local strategy is then employed for route adjustments based on short-range fluctuations. With the combination of global planning and local real-time adjustments, network traffic can eventually obtain a near-optimal allocation. Numerical simulations indicate that in contrast to single-strategy schemes, hybrid global-local load balancing routing scheme can more thoroughly eliminate congestion, and it performs better in measures such as packet loss rate, average queuing delay, traffic distribution, route oscillation, and communication overhead.

Keywords

Internet of Things Low Earth Orbit satellite networks load balancing routing hybrid global-local strategy traffic demand decomposition

Introduction

The Internet of Things (IoT) is expected to comprise billions of heterogeneous smart devices that have sensor terminals, which may create an unprecedented access and exchange of information. With this information, it is possible to construct many smart systems, such as the automatic prevention of traffic jams and the development of smart grids,¹ or even a smarter planet.² Satellite networks (e.g. BeiDou Navigation Satellite System³) with their global coverage and bidirectional communication capabilities are considered candidates to build the backbone of the IoT.⁴ In satellite networks, an ingress satellite collects data from sensor terminals and sends these data to the destination terminals through the egress satellites. Compared with Wi-Fi, Bluetooth, and terrestrial cellular networks, satellite networks have distinct advantages in conducting remote facility monitoring and real-time asset management that spans a broad geographical area. However, with the large-scale deployment of sensing devices, the IoT also presents a set of data storage and processing challenges. Cloud computing infrastructure is considered to have the capability of compensating the IoT and accelerate its development and deployment by providing on-demand “unlimited” computing and storage resources in an efficient and cost-saving manner.^5,6 By using satellite networks, sensing devices in remote outlying regions that have no stable, terrestrial broadband infrastructure can easily access the cloud, and cloud operators can also easily deliver new configurations and tasks to distributed IoT devices at anywhere and anytime.⁷ Additionally, satellite networks can benefit IoT and cloud computing infrastructure with multicast capability for branch locations and offloading nonessential background traffic from the primary network connection.^8,9

To effectively transmit IoT data on satellite networks, an efficient routing scheme is critical. However, from a global perspective, the IoT traffic requirements for satellite networks are unbalanced. The satellites that cover developed areas generally have higher traffic loads than the satellites that cover underdeveloped areas, oceans, or mountains.¹⁰ In addition, when traditional shortest path routing algorithms are adopted, irregular constellation structures and varying lengths of inter-satellite links (ISLs) may cause traffic accumulation in specific areas, such as the minimum horizontal ring.¹¹ Because the bandwidth resources provided by satellites are often limited, the above factors may quickly lead to severe traffic congestion and significant packet drops in certain satellites while leaving other satellites poorly utilized.

Researchers have proposed load balancing routing schemes^12–25 to improve this situation. Among these schemes, two strategies are commonly used: global strategy and local strategy. Global strategy typically involves gathering global traffic state information and making routing decision based on the current global view. It alleviates global congestion and guarantees better traffic engineering but suffers from slow reaction times and large communication and storage overheads. Local strategy allows satellites to independently make routing decisions based on local traffic state information. It provides rapid traffic adaptability and introduces less overhead but is easily trapped in local optima. However, to the best of our knowledge, most load balancing routing schemes embrace the extremes of the design spectrum: they are based on either a global strategy^12–19 or a local strategy.^20–25 As either strategy has certain merits and flaws, none of these schemes offers the ideal performance.

Another significant defect in load balancing routing schemes is that they passively perform load balancing to mitigate observed congestion but neglect to proactively disperse traffic to prevent congestion. The root cause of this behavior may be that these schemes are designed on the assumption that traffic requirements are un-known and stochastic. Thus, they only monitor the current traffic state and continually eliminate building congestion. However, unlike wireless sensor networks (WSN),^26,27 Low Earth Orbit (LEO) satellite networks are highly deterministic systems. Their satellites rotate on fixed orbits. Their traffic requirement, which is closely related to geographical distribution of IoT devices, the daily evolution of traffic intensity, and the coverage relationship between satellites and geographical zones show strong periodical and predictable features.^28–30 This suggests that the amount of traffic that needs to be routed by each satellite at a particular time can be approximately estimated. Henceforth, load balancing routing schemes should take this into account and take measures in advance to prevent traffic concentration as opposed to reacting to the onset of congestion.

In this article, we propose a hybrid global-local (HGL) load balancing routing scheme that aims to eliminate congestion and optimally transmit IoT traffic through LEO satellite networks. Given the predictive nature of LEO satellite networks, the inter-satellite traffic demand is decomposed into a predictable long-range baseline and unpredictable short-range fluctuations. The long-range baseline, which is mainly derived from deterministic satellite movement and stable changes in IoT traffic density and intensity, represents the majority of ongoing changes in inter-satellite traffic demand. It can be statistically modeled and considered a crude estimation of the actual traffic demand. Short-range fluctuations, which are typically caused by bursts in IoT traffic requirements and network anomalies, represent a minor and stochastic portion of inter-satellite traffic demand. Traffic decomposition makes it possible to separate out major and predictable components of traffic demand and use them to perform preliminary traffic allocation. As a result, the majority of traffic volumes can be proactively dispersed from the entire network, which effectively prevents traffic concentration and congestion. In addition, if congestion still occurs after preliminary traffic allocation, only incremental portions of traffic need to be managed rather than all of it.

Based on this idea, HGL is implemented in two stages. First, it employs a global strategy to accomplish preliminary optimal traffic allocation based on long-range baseline traffic demands of all satellite pairs. Load balancing routing in this stage is mathematically formulated as a multi-commodity flow optimization problem seeking to minimize the total flow cost of the entire network. Next, HGL employs a local strategy to conduct real-time route adjustments based on the unpredictable fluctuations. In this stage, a satellite explicitly informs multiple upstream satellites to reroute a portion of traffic once it finds a burst of traffic resulting in queuing beyond a certain threshold.

HGL not only uses the global view of global strategy to proactively disperse the majority of traffic, which in turn significantly reduces the need for subsequent adjustments, but also allows nodes to use local strategy to promptly adapt to locally changing conditions without incurring a large overhead for global updates. In addition, because the baseline traffic demands are slow to change, HGL relaxes the burden of frequently updating the global strategy. We list the main contributions of our work as follows:

Hybrid scheme: To optimally transmit IoT data on LEO satellite networks, we design a novel hybrid global-local routing scheme that combines the advantages of both global and local strategies and simultaneously overcomes their shortcomings.

Traffic decomposition: For the first time, the inter-satellite IoT traffic demand is decomposed into a predictable long-range baseline and unpredictable short-range fluctuations. Moreover, we use authoritative statistics to model the baselines.

New optimization objective: When using global strategies, the optimal traffic allocation is traditionally formalized by minimizing the maximum flow of the network.^16,17,31 However, this objective often reserves redundant link capacity to accommodate the actual traffic, thus degrading the delay performance, in particular in non-congestion situations. To address this over-provisioning problem, HGL pursues the objective of minimizing the total flow cost of the network.³² Simulations prove that HGL can effectively reduce the average end-to-end delay while performing similarly to load balancing routing schemes with traditional objective.

Multi-hop congestion notification: The local real-time route adjustment phase in HGL is inspired by explicit load balancing (ELB) routing protocol.²⁰ However, instead of using one-hop congestion notification like ELB, HGL uses a novel multi-hop congestion notification mechanism in which multiple upstream satellites on the transmission path are notified to reroute a portion of data when there is a congested link. Therefore, HGL can more promptly alleviate congestion on a larger scale.

The remainder of this article is structured as follows. In section “Related works,” we summarize the related works and note their limitations. In section “IoT traffic demand of LEO satellite networks,” we introduce the decomposition of traffic demand time series and provide the methodology for baseline modeling. In section “Technical design of HGL,” we highlight the technical design of the proposed HGL and make a detailed analysis for parameter setting. In section “Performance evaluation,” we evaluate and analyze the performance of HGL using simulations. Finally, in section “Conclusion,” we conclude this article with a summary.

Related works

Nowadays, satellite networks are becoming increasingly important for broadband communication, navigation, and remote sensing. Although a lot of matters are important for satellite networks, such as data encryption,^33–39 image encryption,^40–46 and data coding,^47,48 to transmit data, routing should be solved first. While traditional routing algorithms in satellite networks mainly consider propagation delay, load balancing routing algorithms also take queuing delay and congestion status into consideration when selecting paths for packet transmission. HC Yan et al.¹² proposed a LEO satellite network link state routing (SLSR) scheme, which considers using the summation of propagation delay and expected queuing delay as the link cost for load balancing. In SLSR, satellites must first periodically flood the expected queuing delay to gather the global link state. Then, they choose the paths with minimum link cost as the optimal paths for data transmission. Using the same link cost metric, C Chen and Ekici¹³ introduced a satellite grouping and routing protocol (SGRP) for Multi-Layered Satellite Networks. In this scheme, LEO satellites are divided into groups that are managed by Medium Earth Orbit (MEO) satellites, and MEO satellites are responsible for collecting global link state information and calculating routing tables. In addition to queuing delay, load balancing routing protocol based on mobile agent (LBRP-MA), which was proposed in Rao et al.,¹⁴ also takes into account the geographical position when setting the link cost. It aims to migrate heavy traffic from the Northern Hemisphere to the Southern Hemisphere and employ mobile agents to gather global link states and calculate routing tables. SLSR, SGRP, and LBRP-MA provide traffic adaptability by taking into account queuing delay or geographical factors in the estimation of the shortest paths. However, only one outgoing path is provided for each traffic demand. As a result, it is difficult to distribute heavy traffic through multiple satellites. To solve this problem, JJ Bai et al.¹⁵ proposed a compact explicit multi-path routing (CEMR) algorithm which improves upon the above schemes by allowing each satellite to split traffic among the K-shortest paths. In addition, CEMR adopts a plane speaker mechanism to more effectively collect global traffic information. However, CEMR simply splits the traffic equably between the K-shortest paths. As optimal traffic allocation typically involves multiple paths with different traffic shares, the outcome of CEMR may deviate substantially from the ideal. HS Chang et al.¹⁶ proposed a finite-state-automation (FSA)-based routing algorithm that realizes optimal traffic allocation through heuristics. It divides the system period into equal-length intervals and regards the topology in each interval as fixed. Then, load balancing routing is formulated as a set of optimization problems in fixed topology networks. Unfortunately, FSA is an offline scheme that calculates the optimal link assignments based on the fixed propagation delays in each interval. Thus, it is not adaptable to real traffic conditions. Kucukates and Ersoy¹⁷ employed the Routing Set concept and proposed an online load balancing routing algorithm called the maximum-flow minimum-residual (MFMR) algorithm. This approach assumes that ISLs below the 50th latitude are of equal length and that each traffic source and destination can be placed on the diagonal position of a Routing Set. To reduce the large overhead caused by state messaging to the whole network, MFMR only periodically floods traffic state information in the Routing Set. Then, the maximum flow is minimized over the available paths in the Routing Set (not all the network) to balance the load in this area. MFMR provides a feasible solution for realizing optimal traffic allocation based on real-time traffic information. However, MFMR does not address traffic requirements, which are necessary for optimization. Moreover, traffic that is outside the 50th latitude and passes through the Polar Regions cannot be optimized by MFMR. Bertaux et al.¹⁸ and Bao et al.¹⁹ introduced two schemes for solving load balancing routing by applying software-defined networking (SDN) principle. However, the complexity and cost still need to be evaluated before making such a solution a reality.

As can be seen, although the above schemes have many differences, they all use a global strategy (we refer to them as global schemes). That is, the routing decisions in these schemes are made based on the traffic information gathered from the whole network (or the Routing Set). A key advantage of this type of scheme is global optimality. However, the need to create and maintain a global view of the traffic state often results in a significant amount of communication and storage overhead. Moreover, it is difficult for these schemes to manage congestion in real-time, as the information that is gathered can be outdated due to large propagation delays.

Faced with these shortcomings, researchers began to pursue new schemes that enable nodes to independently perform load balancing routing. Taleb et al.²⁰ proposed an ELB routing protocol that exclusively uses traffic load information from neighboring satellites. In ELB, a satellite explicitly informs its neighboring satellites to reroute a portion of traffic via alternative paths when it suffers heavy traffic loads that exceed a pre-defined threshold. ELB alleviates heavy traffic loads essentially in real-time fashion. It reacts rapidly to changes in traffic compared with global schemes. However, ELB only transmits the congestion notification to one-hop neighbors; thus, heavy traffic cannot be promptly dispersed by multiple upstream satellites. Moreover, the limited range within which traffic is rerouted may be a source of cascading congestion on neighboring satellites. Ö Korçak et al.²¹ proposed a priority-based adaptive routing (PAR) technique in which a routing decision is made at each hop by a priority mechanism depending on the past utilization and buffering information about the links. When sending packets, it tends to choose the links that are less utilized. PAR does not collect traffic information from other satellites, thus minimizing overhead. However, as the outgoing link state may not reflect the real state of the next hop node, PAR may sometimes send packets to satellites plagued by severe congestion. GH Song et al.²² proposed a traffic-light-based intelligent routing strategy (TLR) that performs load balancing routing considering the congestion status at both the current outgoing link and the next hop node. A set of traffic lights is used to indicate the congestion status at the current outgoing link and the next hop node. Packets are transmitted along dynamic routes according to the real-time color of traffic lights at the current outgoing link and the next hop node. However, due to the absence of a global view, TLR can only migrate aggregated traffic to neighboring light-loaded satellites and cannot disperse them over the entire network. Moreover, TLR still bears the risk of cascaded congestion as ELB does. In addition to these schemes, Nishiyama and colleagues^23–25 introduced some load balancing routing schemes for Multi-Layer Satellite Networks. The purpose of these schemes is to enable each satellite to transfer packets with fewer hops via the LEO layer and to transfer packets with more hops via the MEO layer or Geosynchronous Earth Orbit (GEO) layer. However, these schemes successfully utilize network capacity between layers but fail to distribute traffic in each layer.

As can be seen, the above schemes typically allow satellites to make routing decisions based on local traffic information. In other words, they use a local strategy (we refer to them as local schemes). Unlike global schemes, local schemes only gather the necessary information from neighboring satellites, thus generating less communication and storage overhead. In addition, as they can change routes in real-time, local schemes provide strong traffic adaptability. However, because there is no global view, routing decisions in local schemes occasionally cannot guarantee global optimality. Moreover, faced with highly dynamic traffic, local schemes may endure persistent feedback signals and frequent route oscillations.

Overall, the abovementioned schemes represent the typical load balancing routing solutions for satellite networks. However, as described, these schemes are based on either a global strategy or a local strategy. In addition, to the best of our knowledge, nearly all load balancing routing solutions are also based on a single strategy, as in the case of these typical schemes. Because either strategy has certain merits and flaws, no scheme can achieve ideal performance.

Another defect in existing load balancing routing schemes is load balancing routing is performed only when congestion is imminent; the predictability of satellite network is not used to proactively prevent congestion. Therefore, to overcome these weaknesses, our hybrid global-local scheme is proposed.

IoT traffic demand of LEO satellite networks

Exploring the characteristics of IoT traffic demand in LEO satellite networks is important to understand traffic distribution and to design better routing schemes. This section provides a detailed analysis of the global IoT traffic feature; it demonstrates how the inter-satellite traffic demand can be decomposed into a predictable long-range baseline and unpredictable short-range fluctuations, which form the basis of the development of our hybrid scheme. Moreover, this section provides the methodology for baseline modeling.

Predictable long-range baseline

In LEO satellite networks, each satellite provides access to services for all IoT devices within its coverage. The traffic demand between the two serving satellites depends on the potential traffic demand between the two coverage areas. Because satellite coverage varies geographically with the movement of constellations and because the traffic intensity in the coverage areas changes temporally, inter-satellite traffic demand is time varying. However, because the geographical variation of the satellite’s coverage area is cyclical and deterministic and because the temporal variation in aggregate IoT traffic intensity between two certain areas exhibits an evident daily pattern,^28,29 the evolution of inter-satellite traffic demand presents a clear deterministic and periodic trend. In addition, the period of this trend can be obtained by calculating the smallest common integer multiple of the satellite orbital period, the Earth’s rotation period, and the IoT traffic intensity period.

We now explain how to model the baseline of this trend. The ideal constellation is assumed to be the Iridium constellation,³⁰ which has a period of baseline traffic variation that is approximately equal to 24 h. Because the Iridium constellation has 66 satellites equally distributed in six planes, we correspondingly divide the Earth into 6 × 11 geographical zones as shown in Figure 1. To hide the complex repercussions caused by the mobility of satellites when modeling the baseline, we adopt the virtual satellite mechanism.^49–51 A total of 66 virtual satellites are fixed above the center of the geographical zones. At any time, each virtual satellite is represented by the physical satellite closest to it. When the physical satellite moves away and another moves within the range of the virtual satellite, the traffic demand and routing table information are switched to the successor satellite. Because the physical satellite periodically moves above the surface of the Earth, the mapping relationship between virtual satellites and physical satellites is cyclical and can be calculated in advance. Thus, if the baseline traffic demand between the two virtual satellites can be obtained, the baseline between the two physical satellites can also be derived. To simplify the analysis, we assume that IoT traffic demand in each geographical zone is mapped onto the virtual satellite that resides above the center of the zone and that each satellite is only responsible for one zone. Moreover, we follow^21,52 and assume that the potential traffic requirement for satellite networks from each geographical zone is proportional to the number of IoT devices in each zone. The statistics from the Organisation for Economic Co-operation and Development (OECD) in 2015¹⁰ for the IoT devices for each country are utilized to estimate the number of IoT devices in each zone. The results are depicted in Figure 1.

Figure 1.

Earth zone division and IoT device density.

We choose virtual satellite i as the ingress satellite and virtual satellite j as the egress satellite. $n_{i}$ stands for the number of IoT devices in the geographical zone under the coverage of satellite i, and $n_{j}$ stands for the number of IoT devices in the geographical zone under the coverage of satellite j. Then, the potential inter-satellite (virtual satellite) traffic volume between satellite i and satellite j, that is, $V_{ij}$ , depends on the device amount $n_{i}$ , $n_{j}$ , and the distance $d (i, j)$ between the two geographical zones’ centers^21,52

$V_{ij} = \frac{{(n_{i} * n_{j})}^{0.5}}{{(d (i, j))}^{1.5}}$ (1)

In addition to the geographical distribution of IoT traffic, the temporal variation of IoT traffic intensity in each geographical zone is also considered for baseline modeling. In Shafiq et al.²⁸ and Romirer-Maierhofer et al.,²⁹ the authors noted that the temporal variation of aggregate IoT traffic intensity between two certain areas exhibits an evident daily cycle. In addition, these authors identified that this variation is closely coupled with human working hours, and the reason for this phenomenon may be because that a majority of IoT devices are employed for business use. A daily profile,²¹ which is shown in Figure 2 and defines the aggregated traffic volume of each hour as a percentage of the total traffic volume within a single day, can demonstrate this daily variation in IoT traffic intensity. Therefore, if we assume that the daily evolution of IoT traffic intensity is the same for all areas worldwide and the local time of each geographical zone is equal to the solar time of the respective zone’s center longitude. Then, the hourly traffic demand (packets/second) between satellites i and j (traffic sent from satellite i to satellite j) can be computed by equation (2)¹⁴

$λ (i, j, a_{h}) = \frac{V_{ij}}{\sum_{k = 1}^{66} \sum_{l = 1}^{66} V_{kl}} * a_{h} * A * \frac{1}{3600}$ (2)

where h is the current local hour of the source terminals, $a_{h}$ is the traffic percentage in the corresponding hour h, and A represents the total IoT traffic generated worldwide per day (bit per day) for satellite networks.

Figure 2.

Daily variation of IoT traffic intensity.

Unpredictable short-range fluctuations

The above method models the long-range baseline in inter-satellite (virtual satellite) traffic demand variation. Generally, the actual variation in traffic demand conforms to the baseline. However, in certain periods, traffic demand can significantly deviate from the long-range baseline. Two major factors may contribute to this phenomenon. One factor is the unpredictable traffic fluctuations caused by terrestrial IoT applications. The other factor involves anomalies in the satellite network topology.

As Shafiq et al.²⁸ and Wu et al.⁵³ stated, although most IoT sensors are based on a time-triggered mechanism, several event-driven IoT applications can still result in severe bursts of traffic. In addition, under some special circumstances, such as natural disasters and holidays, IoT traffic volume can also change dramatically from the usual traffic. Because satellite networks mainly carry traffic from terrestrial IoT applications, the short-range unpredictable characteristics of terrestrial IoT traffic will inevitably be translated to the satellite segment and finally lead to unpredictable short-range fluctuations in inter-satellite traffic.

Anomalies in the satellite network topology refer to the topology changes and network failures that are caused by configuration mistakes, equipment damage, and other factors. These anomalies often cause traffic shifts among ISLs, which may lead to traffic fluctuations or even severe bursts of congestion in the satellite networks. Unfortunately, because of the harsh environment of space and the limited life span of satellite equipment, these anomalies are quite frequent and further perpetuate the short-range unpredictable characteristics of satellite traffic.

Technical design of HGL

Overview of HGL

Based on the idea presented in section “IoT traffic demand of LEO satellite networks,” the inter-satellite IoT traffic demand of LEO satellite networks can be decomposed into a combination of long-range baseline and short-range fluctuations (also referred to as deviations to the baseline) as illustrated on the left side of Figure 3. The long-range baseline extracts the deterministic dynamics in traffic demand. It represents the majority of traffic demand variation and can be considered a crude estimation of the actual traffic demand. Short-range fluctuations refer to all unpredictable changes apart from the baseline. They occur stochastically and temporarily and reflect the deviations between the real traffic volume and the estimated average traffic volume.

Figure 3.

An overview of the HGL scheme. The data used in this graph have been gathered from a nation-wide cellular operator in the United States during one complete week in August 2010.²⁸ The actual data reflect the aggregate uplink machine-to-machine (M2M) traffic intensity in the core networks on Monday, and the long-range baseline is calculated by averaging the traffic data from the complete week.

From the network view, long-range baseline traffic demands between all satellite pairs reflect the regular changes of all network traffic; they are preferably managed by global strategies. However, large short-range fluctuations tend to appear on particular satellites and are therefore more suitable for local strategies. Thus, we implement the HGL scheme in two stages, as shown in Figure 3. First, it concentrates on the baseline traffic demand variations and employs a global strategy to periodically conduct preliminary optimal traffic allocations. Load balancing routing at this stage is mathematically formulated as a set of multi-commodity flow optimizations that seek to minimize the total flow costs of the entire network. After implementing the calculated optimal routing tables, the network can disperse the network traffic in a balanced and effective manner. However, because the optimal routing tables are calculated based on the long-range baselines, they are not suitable for handling bursts of congestion caused by unpredictable traffic fluctuations. Continually updating the optimal routing table to eliminate bursts of congestion is costly and often too late. Therefore, a local strategy is employed to conduct real-time route adjustments during the global update intervals. In this stage, a satellite can explicitly inform its multi-hop upstream satellites to reroute a portion of traffic when its link occupancy rate exceeds a pre-defined threshold. As a consequence, the affected intermediate satellites can rapidly resolve the burst congestion instead of waiting for the next whole network update. Finally, by continuously combining global planning with local real-time adjustments, congestion can be effectively eliminated, and traffic can acquire a near-optimal distribution over the constellation. In the following section, we describe the two steps in detail.

Preliminary optimal traffic allocation

In the preliminary optimal traffic allocation phase, HGL periodically collects the global link state and utilizes the long-range baseline traffic demands to compute the optimal routing table every $Δ$ in interval time.

Consider the case of the Iridium constellation in Figure 4(a). Most satellites maintain four ISLs (two intra-plane ISLs and two inter-plane ISLs) with neighboring satellites, except those at high latitudes whose inter-plane ISLs are turned off. The intra-plane ISLs between neighboring satellites in the same plane are maintained at all times, and the propagation delay on the intra-plane ISLs is always fixed. In contrast, the inter-plane ISLs between neighboring satellites in different planes are shut down in the Polar Regions and re-established outside of the Polar Regions, and the propagation delay on the inter-plane ISLs becomes shorter when the end satellites move toward the polar regions. All satellites move in the same circular direction within the same plane. As a consequence, any satellite that is observed from the Earth moving from South to North will be observed to start moving from North to South when it crosses the North pole. Hence, between the first and last planes, there exists a seam called cross-seam. The opposite movement of the neighboring satellites along the cross-seam results in frequent handovers in the cross-seam ISLs.

Figure 4.

Network topology of the Iridium constellation: (a) 3D graphics and (b) 2D graphics.

Due to these frequent link switches and handovers, the topology of the satellite network becomes extremely dynamic, which makes routing problems complicated. To hide the mobility of satellites and consequent handover events from the routing protocol, we continue to adopt the virtual satellite mechanism,⁴⁹ which has been quoted in the section “IoT traffic demand of LEO satellite networks.” A total of 66 virtual satellites are supposed to evenly set above the surface of the earth and form a fixed mesh topology. The connectivity in this mesh topology is invariant. Each physical satellite represents a virtual satellite for a fixed period of time. When it leaves the area of the virtual satellite, it automatically transfers the routing table, traffic demand, and other relevant information to the successive satellite and execute a link handover. By using such mechanism, routing can be performed in the stable virtual topology, and the global routing update interval can be independent of link handover examination. Note that the delay between inter-plane virtual satellites is time varying due to the varying distance between physical satellites and the changing queuing delay. To effectively collect the global link state, we assign a plane speaker satellite (virtual satellite) for each plane.¹⁵ At the beginning of each global update interval, plane speakers are responsible for collecting the link state and queuing delay information within their planes and exchange the collected information with other plane speakers to build the global routing information base (GRIB). Non-plane speaker satellites can only broadcast their state information to their intra-plane satellites. Moreover, we request that the plane speakers at adjacent planes have a direct link as shown in Figure 4(a).

In GRIB, each link has a link cost $w (i, j)$ defined by the summation of propagation delay and expected queuing delay

$w (i, j) = T_{prop} (i, j) + T_{queue} (i, j)$ (3)

where $T_{prop} (i, j)$ denotes the one-way propagation delay from satellite i to satellite j and is computed as

$T_{prop} (i, j) = \frac{IS L_{length}}{c_{l}}$ (4)

where $c_{l}$ stands for the speed of light. $IS L_{length}$ is the length of the ISL between satellite i and satellite j. Because the motion of satellites is deterministic according to the selected constellation parameters, the $IS L_{length}$ and $T_{prop} (i, j)$ can be predicted.

$T_{queue} (i, j)$ denotes the expected queuing delay.^15,22 Because of the large propagation delay, the collected instant queuing delay may be outdated upon arrival at the plane speakers; therefore, we utilize the expected value to approximate the real queuing delay at that time

$T_{queue} (i, j) = \frac{1}{Δ} * \int_{t_{s} - Δ}^{t_{s}} \frac{q (m) * P_{avg}}{C} dm$ (5)

where $t_{s}$ denotes the start time of this time interval, C denotes the link capacity, $P_{avg}$ denotes the average packet size, and $q (m)$ denotes the number of packets in the queue (outgoing link queue at satellite $i)$ at time m.

Note that in $w (i, j)$ , propagation delay $T_{prop} (i, j)$ can be computed in advance. Only the un-deterministic parameter $T_{queue} (i, j)$ and accidental link breaks need to be reported to the plane speakers at the beginning of each interval, thus minimizing overhead. After gathering all the link states and building the GRIB, plane speakers can calculate the optimal routing table. We use $f_{(i, j)}^{(s, t)}$ to represent the traffic that is caused by the source–destination satellite pair $(s, t)$ and flows from satellite i to satellite j. Then, $f_{(i, j)} = \sum_{s, t} f_{(i, j)}^{(s, t)}$ is the total flow on link $(i, j)$ , which is obtained by summing over all source–destination pairs $(s, t)$ . In most load balancing schemes, the optimal traffic allocation is formalized to minimize the maximum flow of the network^16,17,31

$minimize : max_{(i, j)} {\frac{f_{(i, j)}}{C}}$ (6)

This objective achieves load balancing by reserving maximum residual bandwidth to all the links. However, it incurs longer delays because packets may be subjected to more detours to maintain low link utilization. This is inefficient, in particular in situations characterized by light loads. Therefore, in HGL, we suggest the optimization objective of minimizing the total flow cost,³² which not only balances the traffic but also optimizes the overall delay performance

$minimize : \sum_{i, j} \sum_{s, t} f_{(i, j)}^{(s, t)} w (i, j)$ (7)

and the objective is subjected to

$\sum_{j} f_{(i, j)}^{(s, t)} - \sum_{j} f_{(j, i)}^{(s, t)} = {\begin{matrix} D (s, t), & if i = s \\ - D (s, t), & if i = t \\ 0, & others \end{matrix} \forall i, s, t$ (8)

$\sum_{s, t} f_{(i, j)}^{(s, t)} \leq C \begin{matrix} \forall i, j \end{matrix}$ (9)

$f_{(i, j)}^{(s, t)} \geq 0 \begin{matrix} \forall i, j, s, t \end{matrix}$ (10)

where $D (s, t)$ is the traffic demand matrix, which tells us how much traffic flow is necessary to send from satellite s to satellite t. This is determined according to equation (2). For each source–destination pair $(s, t)$ , the flow conservation constraint equation (8) specifies that the traffic flowing into a node balances the traffic flowing out of the node. Constraint equation (9) indicates that the total flow on link $(i, j)$ cannot exceed the link capacity. Constraint equation (10) is the nonnegative limitation.

As can be seen, traffic allocation with the objective of minimizing the total flow cost and its constraints allows flows to preferentially use the lower-cost links but without exceeding the link capacities. In this way, HGL can find the cheapest way to send traffic based on the premise of load balancing.

If we regard the flow sent from s to t as a commodity, the above optimization problem equation (7)–(10) should be recognized as a minimum cost multi-commodity flow problem,⁵⁴ which is well known in graph theory. As fractional flows are allowed, the problem can be solved in fully polynomial time by the linear programming method.⁵⁵ A detailed description of the solution can be found in Karakostas.⁵⁶

Having obtained the flow matrix $f_{(i, j)}^{(s, t)}$ , we can utilize it to calculate the optimal routing table. To support this flow splitting method, we construct the routing table as shown in Table 1. We consider the routing table of satellite S40 in Figure 4(b) as an example. The routing table consists of five entries: destination, source, next_hop, weight, and left_time. The destination entry indicates the destinations of the packets and includes the satellite IDs (except itself) to ensure that any packet can find its destination. The source entry indicates the sources of the packets that flow through satellite S40. It is set according to the source attribute (s attribute) of each non-zero flow fraction $f_{(40, j)}^{(s, t)}$ and thus does not necessarily involve all the satellite IDs. For the packet belonging to a source–destination combination, there is a set of next_hop candidates according to the j attribute of $f_{(40, j)}^{(s, t)}$ . Moreover, to split the flow according to $f_{(40, j)}^{(s, t)}$ , we use the weight entry to specify the probability of each next_hop being selected when a request occurs. Finally, the left_time entry indicates the available time of the route. Note that for each destination, we also give a default shortest path that is marked in green. Packets that do not match the source–destination combination will be transmitted to the default shortest path. This is used in the local route adjustment phase and will be discussed in the next section.

Table 1.

Routing table of satellite S40 before traffic detour.

Destination	Source	Next_Hop	Weight	Left_Time (ms)
⋮	⋮	⋮	⋮	⋮
65	2	39	0.9	1000
		51	0.1	1000
	5	39	1	1000
	6	29	1	1000
	⋮	⋮	⋮	⋮
	NULL	39	1	1000

66	1	51	1	1000
	3	39	0.3	1000
		29	0.7	1000
	⋮	⋮	⋮	⋮
	NULL	41	1	1000

Local route adjustment

So far, the optimal routing table has been calculated and can be distributed to each satellite. Traffic will be proactively distributed to multiple paths in a balanced manner rather than concentrating on the shortest paths. However, as stated previously, the optimal routing table is inadequate for addressing unpredictable traffic. Therefore, we design the local route adjustment to complement preliminary traffic allocation and address this burst traffic.

In the local route adjustment phase, each satellite periodically detects the buffer queue and the traffic sending rate of each outgoing ISL every $δ$ interval $(δ << Δ)$ and immediately informs its upstream satellites to reroute a portion of traffic when its queue occupancy ratio exceeds a pre-defined threshold. We denote $Q (n)$ as the queue occupancy of the current satellite on the ISL at direction n and define $Q_{r} (n)$ as the queue occupancy ratio, which is $Q (n)$ divided by the total queue size $Q_{l}$ . When $Q_{r} (n)$ is inferior to a pre-defined threshold $α$ , the satellite is considered to be in a Free State (FS). When $Q_{r} (n)$ is between the threshold $α$ and another pre-defined threshold $β$ , the satellite is considered to be in a Fairly Busy State (FBS). If $Q_{r} (n)$ exceeds the threshold $β$ , the satellite is considered to be in a Busy State (BS).

As Figure 4(b) shows, when a given satellite S39 experiences state transition from FS to FBS relevant to direction n, it sends warning packets to its neighboring satellites (including S28, S40, S50, and S38) to inform them that S39 is going to be congested. Then, the neighboring satellites transform the link costs of the ISLs between them and S39 into infinite value and execute Dijkstra’s shortest path (DSP) algorithm to calculate the alternate routes that exclude S39. If traffic still accumulates and S39 enters the BS, S39 will transmit Busy-State Advertisement (BSA) packets to the neighbors requesting them to reduce their traffic sending rates by a ratio $χ$ . The left $1 - χ$ portion of the traffic will be transmitted via alternate routes retrieved earlier by each neighbor. As Figure 4(b) shows, when S28 and S40 receive BSAs, they detour a portion of the traffic to the alternate paths $\bar{S 28 S 27}$ and $\bar{S 40 S 51}$ , respectively. The routing table of satellite S40 is accordingly modified as shown in Table 2. The items in purple highlight the alternate routes. Note that the default shortest paths are also updated to guarantee that the detouring traffic does not flow into the congested node again.

Table 2.

Routing table of satellite S40 after traffic detour.

Destination	Source	Next_Hop	Weight	Left_Time (ms)
⋮	⋮	⋮	⋮	⋮
65	2	39	$0.9 * χ$	400
		51	$0.1 + 0.9 (1 - χ)$	400
	5	39	$1 * χ$	400
		51	$0 + (1 - χ)$	400
	6	29	1	1000
	⋮	⋮	⋮	⋮
	NULL	51	1	400

66	1	51	1	1000
		39	$0.3 * χ$	400
	3	29	0.7	400
		41	$0 + 0.3 (1 - χ)$	400
	⋮	⋮	⋮	⋮
	NULL	41	1	1000

In addition to modifying the routing table, neighboring satellites have one additional task, that is, to check whether it is necessary to ask upstream satellites to further detour the traffic. If the neighboring satellites find that the detoured traffic exceeds the link capacity of the alternate paths, they will immediately send BSAs to their upstream neighboring satellites to request them to further reroute the excess traffic to alternate paths. As shown in Figure 4(b), once the neighboring satellite S40 finds that the traffic that has been rerouted to the alternate path $\bar{S 40 S 51}$ exceeds the residual link capacity, it immediately informs its upstream satellite S41 that it must reroute the excess traffic to the alternate path, which is computed as $\bar{S 41 S 52}$ . This iterative process will continue until the detoured traffic cannot cause capacity overflow. Thus, large volumes of traffic can be more promptly dispersed by multiple source satellites, and the problem of cascaded congestion caused by traffic rerouting can be effectively eliminated. The BSA packet carries information regarding the congested satellite identifier (ID) and the detour ratio $χ$ . It is only broadcasted to directly connected neighboring satellites.

To promptly and effectively eliminate burst congestion, the rational setting thresholds $α$ , $β$ , and the detour ratio $χ$ are crucial. In addition, because the detour decision is distributed by each satellite in the local route adjustment phase, the packet has the possibility of being routed back to its previous hop;⁵⁷ therefore, HGL should consider avoiding traffic loops. In the following subsections, we analyze how to establish the values of $α$ , $β$ , and $χ$ and introduce the loop-free design in HGL.

The setting of $α$ and $β$

The key strategy behind an optimum setting of $α$ and $β$ is to avoid packet drops when a satellite is running under a heavy traffic load. Let C denote the maximum output traffic rate that is equal to the link capacity. To avoid inaccurate judgements due to temporary fluctuations, we employ a weighted traffic rate (WTR) to represent the traffic sending rate

$I_{n} = γ I_{n}^{pre} + (1 - γ) I_{n}^{now}$ (11)

where $I_{n}^{now}$ denotes the current value of the traffic sending rate on the outgoing ISL in direction n and $I_{n}^{pre}$ denotes the instant value of the traffic sending rate on the previous detection period ( $δ$ interval). $γ$ is the weighting coefficient, which is defined as a constant (0.5 $< γ <$ 1); thus, the WTR is only high when the traffic rate is high for a long period of time. Given the extreme situation, at time t, the queue occupancy ratio of this outgoing ISL is very close but remains below $β$ . Immediately after detection, the queue occupancy ratio exceeds $β$ ; however, the satellite has to wait $δ$ time (the detection interval) to recognize the change and d time (the average one-hop propagation delay) for the BSA to be transmitted to neighbors. If we assume that the WTR is constant over a short period of time, to ensure that the queue occupancy does not exceed the total queue length $Q_{l}$ , $β$ should satisfy

$β Q_{l} + \frac{(I_{n} - C) (δ + d)}{P_{avg}} \leq Q_{l}$ (12)

Taking the special case $β Q_{l} + \frac{(I_{n} - C) (δ + d)}{P_{avg}} = Q_{l},$ we get

$β = 1 - \frac{(I_{n} - C) (δ + d)}{Q_{l} P_{avg}}$ (13)

$α$ should be established to ensure a sufficient amount of time to calculate the alternate route before receiving the BSA. If we assume that the average time to calculate an alternate route by Dijkstra’s algorithm is e, to guarantee that neighbors have enough time to calculate the alternate paths before the BSA arrives, $α$ should meet

$α Q_{l} + \frac{(I_{n} - C) e}{P_{avg}} \leq β Q_{l}$ (14)

Combining the special case $α Q_{l} + \frac{(I_{n} - C) e}{P_{avg}} = β Q_{l}$ with equation (13), we obtain

$α = 1 - \frac{(I_{n} - C) (δ + d + e)}{Q_{l} P_{avg}}$ (15)

As shown in equations (13) and (15), when a WTR $I_{n}$ is given, $α$ and $β$ are calculated. $α$ and $β$ will decrease when $I_{n}$ increases.

The setting of detour ratio $χ$

The setting of detour ratio $χ$ should be discussed in terms of two cases. One is in the bottleneck satellite whose outgoing ISL is congested, and the other is in the upstream satellites.

In the bottleneck satellite

In response to burst congestion, the bottleneck satellite generates BSAs and sends them to neighboring satellites. In the bottleneck satellite, let $I_{ns}$ denote the sending rate of the traffic to the bottleneck outgoing ISL that originates from neighboring satellites and $I_{nt}$ denote that from the ground terminals. By the time the BSAs reach the neighboring satellites, the queue occupancy of the bottleneck ISL is

$q (t_{bsa}) = \min (β Q_{l} + \frac{(I_{ns} + I_{nt} - C) d}{P_{avg}}, Q_{l})$ (16)

To ensure a prompt recovery for the bottleneck satellite—one that lasts for at most $θ$ amount of time to reduce the queue occupancy ratio to $α$ —the new sending rate of traffic from the neighboring satellites $I_{ns}^{new}$ should satisfy

$C - (I_{ns}^{new} + I_{nt}) = \frac{P_{avg} * (q (t_{bsa}) - α Q_{l})}{θ}$ (17)

Therefore, we get

$I_{ns}^{new} = C - \frac{P_{avg} * (q (t_{bsa}) - α Q_{l})}{θ} - I_{nt}$ (18)

Thus, the detour ratio can be accordingly computed as

$χ = \frac{I_{ns}^{new}}{I_{ns}}$ (19)

In the upstream satellites

As stated previously, when a neighboring satellite or multi-hop upstream satellite receives the BSA from the congested node, it first checks whether it needs to further transmit BSAs to its upstream satellites. Let $I'_{ns}$ and $I'_{alts}$ denote the sending rate of the traffic to the congested node and the alternate path which originates from neighboring satellites, and $I'_{nt}$ and $I'_{altt}$ denote that which originates from the ground terminals. As the detour rule prescribed, the $(1 - χ) (I'_{ns} + I'_{nt})$ part of the traffic will be rerouted to the alternate path. However, if $(1 - χ) (I'_{ns} + I'_{nt}) + (I'_{alts} + I'_{altt}) > C$ , which indicates the detoured traffic exceeds the residual link capacity of the alternate path, the excess portion of the traffic will be further rerouted by its upstream satellites. Let $χ'$ denote the new detour ratio. In this situation, it should satisfy

$(1 - χ) (χ' I_{ns}^{'} + I_{nt}^{'}) + (χ' I_{alts}^{'} + I_{altt}^{'}) = C$ (20)

Therefore, we obtain

$χ' = \frac{C - (1 - χ) I_{nt}^{'} - I_{altt}^{'}}{(1 - χ) I_{ns}^{'} + I_{alts}^{'}}$ (21)

Conversely, if $(1 - χ) (I_{ns}^{'} + I_{nt}^{'}) + (I_{alts}^{'} + I_{altt}^{'}) \leq C$ , a further detour will be terminated.

After the queue occupancy ratio is brought back to $α$ , the traffic detours are also maintained for a residual time of $τ$ . By this setting, a sufficient recovery time can be granted before the satellites enter the BS again. The detour process is then finished, and the routing tables revert to the previous state.

Loop-free design

To avoid traffic loops, HGL requires the packet to record the passed hops in its head as it travels in the satellite network. When the next hop appears in the packet head, the packet is sent in another feasible direction (randomly selected). If both directions appear in the head, the packet is sent back to the former node to find other feasible directions. In our model, the satellite number is 66 (6 * 11), and packets at most traverse $11 / 2 + 5 = 10$ satellites to reach the destination. We allocate 1 byte to identify each satellite node in the packet head and set packet time to live (TTL) as 20 (20 = 10 × 2) to restrict the route path growth. Therefore, the length of the traversed path will cost at most 20 bytes. This cost is not large because the packet header in network layer (e.g. IPv4 packet header) could be as long as 60 bytes.

Performance evaluation

Simulation setup

In this section, we evaluate the performance of HGL using NS2 (network simulator). The experiments are conducted on the aforementioned Iridium constellation with LEO satellites residing at an altitude of 780 km. The Polar Regions are defined as the regions between latitudes $75^{\circ}$ and $90^{\circ}$ in the Northern and Southern Hemispheres, and the inter-plane ISLs inside these regions are assumed to be disconnected. Moreover, the cross-seam ISLs are allowed. For each satellite, ground-satellite link (GSL) and ISL handovers are checked every 10 s. The capacity of all ISLs are set to 25 Mbps ( $C = 25$ Mbps), and the capacity of all GSLs are set to 100 Mbps to eliminate the influence of packet drops due to limited downlink capacity. Each outgoing link has a buffer size of 100 packets ( $Q_{l} = 100$ ). The average one-hop ISL propagation delay is computed to be 14 ms ( $d = 14$ ms).²² In satellite networks, we assume that the IoT data transmission is based on Internet Protocol (IP), and the total packet size is assumed to be 1 Kbyte ( $P_{avg} = 1$ Kbyte).

In HGL, plane speakers are configured to collect the link state and expected queue delay every 30 s ( $Δ = 30$ s); hence, the optimal routing table is refreshed every 30 s. The detection interval of link queue occupancy is set to 10 ms ( $δ$ = 10 ms). The weighting coefficient of the WTR is set to 0.7 ( $γ$ = 0.7). The time for calculating alternate paths by Dijkstra’s algorithm is set to 10 ms (e = 10 ms). Satellites are required to recover from a BS to a FS in 200 ms ( $θ$ = 200 ms), and the residual time for satellites to reside in the FS after a transition from a BS is set to 200 ms ( $τ$ = 200 ms).

In the simulations, we conduct two kinds of HGL with different optimization objectives, one for the case of minimizing the maximum flow (HGL-MMF) and another for our proposed case of minimizing the total flow cost (HGL-MFC). For comparison, we also conduct DSP, MFMR, and TLR protocols. DSP is based on the gathered global routing metric of “propagation delay + expected queuing delay,” and the routing metric and routing table are updated every 30 s to remain identical to that in HGL. MFMR represents the class of global load balancing routing schemes that only periodically minimize the maximum flow without adapting to unpredictable traffic changes. The refresh time of the optimal routing table is also set to 30 s. TLR is implemented over the DSP algorithm. It represents the benchmark of the local load balancing routing scheme, which only considers local route adjustment. Based on these comparisons, we can evaluate how much the performance can be improved by our hybrid scheme.

For traffic generation, we set 66 ground terminals in the center of each geographical zone as shown in Figure 1. To better model the IoT traffic with both long-range predictable and short-range unpredictable characteristics, we control each node to generate on–off flow that obeys a Pareto distribution with the shape equal to 1.2. The average burst and idle time are set to 200 ms, and the mean value of the sending rate between each pair of nodes is set according to equation (2); thus, increasing the total offered traffic A in equation (2) will increase the average flow rates and in turn increases the average load of each satellite. Note that as the focus of the simulations is to evaluate how much performance can be improved by the hybrid scheme compared with single-strategy schemes based on the existence of the baseline, we are not greatly concerned about the effect of the deviation between the realistic baseline and the modeled baseline. Therefore, the mean values of the sending rate are directly set according to the modeled long-range baselines. Finally, all scenarios are run 10 times for 24 h (a system cycle), and we consider the average values the final results.

Simulation results

Packet loss rate

First, we evaluate the performance of HGL in terms of the packet loss rate. Figure 5(a) graphs the total packet loss rate experienced by each scheme under different settings of total offered traffic. HGL (including HGL-MMF and HGL-MFC) has the lowest packet loss rate. This proves that the hybrid scheme is effective and successfully reduces the packet loss rate compared with single-strategy schemes. Note that HGL-MMF achieves a smaller packet loss rate than that of HGL-MFC because minimizing the maximum flow leaves more space for future traffic growth. Therefore, when unpredictable traffic is coming, few packets tend to overflow the capacity. However, based on the diagram, we find that this difference is not significant (the mean difference is 3%). This is because a multi-hop traffic detour by local route adjustment also promptly accommodates the unpredictable traffic, which prevents packet losses from another perspective. For all the traffic volumes, DSP sustains the largest packet loss rate because it only tries to route the traffic to the shortest paths. Aggregated traffic may overflow the selected paths and finally lead to a large packet loss rate. MFMR uses multi-paths to spread the traffic over the entire network, which causes a significant decrease in the packet loss rate compared with that of DSP. However, due to its inability to address unpredictable traffic, the packet loss rate is still larger than that of HGL. TLR introduces traffic lights to indicate the congestion status and dynamically reroutes traffic to avoid packet drops when congestion is encountered. It performs well in conditions with light loads but deteriorates rapidly with increases in the traffic load, as TLR is the shortest path based and cannot actively spread traffic. When too much traffic has accumulated in the shortest paths, local adjustment is actually too late to stop the packet drops. Moreover, due to the lack of a global view and the limited detour range, severe traffic aggregation is difficult to overcome among neighboring satellites.

Figure 5.

Simulation results: (a) packet loss rate, (b) average end-to-end delay, (c) average queue occupancy for each satellite (A = 3.2 Tbit), (d) traffic distribution index, (e) number of route changes, and (f) communication overhead.

Average end-to-end delay

Second, we evaluate the performance of HGL in terms of average end-to-end delay. The average end-to-end delay of each scheme is computed by averaging the end-to-end delays of all source–destination pairs. As shown in Figure 5(b), MFMR and HGL-MMF show higher average end-to-end delay (worse performance) than others because they reserve maximum residual bandwidth to achieve the objective of minimizing the maximum flow. As a result, packets may suffer more detours to keep link utilization low. DSP always routes traffic to the single shortest paths. Its average end-to-end delay degrades substantially with heavy loads because long queuing delays begin to appear at the selected paths. TLR dynamically detours traffic to alternative paths in response to congestion. Although traffic detours may add additional delay in situations characterized by light loads, it is still more beneficial than having to bear severe queuing delays in conditions characterized by heavy loads, as the TLR curve is substantially below the DSP curve after the total offered traffic increased to 1.9 Tbit. HGL-MFC achieves the lowest average end-to-end delay in all five schemes. This should be attributed to the fact that HGL-MFC eliminates congestion and queuing delays to the greatest extent by combining proactive traffic dispersing with local real-time route adjustment. It can also be attributed to the fact that HGL-MFC prefers the shortest paths to carry traffic.

To verify that HGL can alleviate congestion and reduce queuing delays, we calculate the average queue occupancy (averaged value over the simulation launch time) of each satellite in Figure 5(c). The simulations are performed for cases where the total offered traffic A is set to 3.2 Tbit per day.

As can be seen, HGL (including HGL-MFC and HGL-MMF) achieves the lowest average queue occupancy. This indicates that congestion is successfully alleviated throughout the network by global traffic dispersing and local real-time adjustment in two steps. DSP exhibits the highest results for some satellites because it considers neither global traffic dispersing nor local adjustment. Traffic in DSP tends to highly concentrate on a few shortest paths in high-load areas, and satellites that often go through these shortest paths may have larger traffic loads and higher average queue occupancies. TLR can detour a portion of traffic from shortest paths to alternative paths when the shortest paths are congested. Thus, the average queue occupancies of these satellites are lower than DSP. MFMR always attempts to distribute traffic to all the paths in the constellation. Therefore, the average queue occupancy of each satellite in MFMR is more evenly distributed. However, due to its inability to address frequent burst traffic congestion, the queue occupancies of some satellites are still higher than HGL.

Traffic distribution index

Third, we evaluate the traffic distribution in each scheme. To explore how well the traffic is distributed across the network, the traffic distribution index (TDI)²⁰ is introduced

$f = \frac{{(\sum_{i = 1}^{n} x_{i})}^{2}}{n \sum_{i = 1}^{n} x_{i}^{2}}$ (22)

where n is the number of ISLs and $x_{i}$ represents the actual number of packets that traversed the ith ISL. It ranges from 0 to 1, and high values of TDI represent a good distribution of traffic over the constellation. Figure 5(d) plots the TDI for different schemes. As can be seen, the DSP scheme achieves the lowest result. TLR represents a relative improvement over DSP as it uses alternate paths. MFMR, HGL-MMF, and HGL-MFC significantly outperform DSP and TLR because they actively distribute traffic to more paths of the network. Moreover, with increasing total offered traffic, we can see a rapid increase in HGL-MFC. This indicates that the combination of minimizing the total flow cost and multi-hop congestion notification involves rapidly migrating traffic from shorter paths to other paths when heavy traffic builds.

Route oscillation

Because HGL uses the global view to proactively disperse baseline traffic demands, it should be able to reduce the need for subsequent route adjustments, which alleviates route oscillation problems. To verify this idea and investigate how many improvements can be obtained, we select HGL and TLR and compare the number of route changes during the system cycle.

Figure 5(e) indicates that HGL truly decreases the number of route changes compared to TLR. HGL-MFC reduces the amount by nearly half, and HGL-MMF reduces the amount by nearly three-fourth. Therefore, we can conclude that the use of long-range baseline traffic demands to conduct preliminary traffic allocation can significantly reduce the need for latter adjustment and effectively alleviate route oscillation problems.

Communication overhead

Finally, we compare the communication overhead of each scheme. Remember that HGL and DSP schemes are realized on the same basis: plane speakers periodically collect and exchange link states to establish the GRIB. MFMR collects link states based on the flooding mechanism in the routing sets. Figure 5(f) presents the result in a system cycle (24 h). As can be seen, DSP and MFMR exhibit a relatively lower and constant value compared with other schemes because they only periodically update the routing tables without adapting to unpredictable traffic fluctuations. The communication overhead is mainly derived from the packets for GRIB updating and the delivery of routing tables. In contrast, TLR, HGL-MFC, and HGL-MMF represent relatively higher values because they not only periodically update the global routing tables but also dynamically adjust their routes according to real-time traffic fluctuations. Warning packets and BSAs are produced on a large scale when intermediate satellites encounter unexpected congestion. Moreover, as HGL-MFC and HGL-MMF reduce the need for route adjustment, they generate less communication overhead than TLR.

Conclusion

In this article, we propose a novel load balancing routing scheme, HGL, for the IoT through satellite networks. It not only combines global strategy and local strategy to optimally allocate IoT traffic flows from the whole and part but also utilizes the regularity and predictability of LEO satellite networks to proactively disperse traffic loads to prevent congestion. Compared with single-strategy schemes, the simulation results indicate that HGL effectively reduces the occurrence of congestion and achieves better performance in terms of the packet loss rate, average queuing delay, traffic distribution, and route oscillation with a reasonable communication overhead. Meanwhile, HGL, whose objective is minimizing the total flow cost (HGL-MFC), can reduce the average end-to-end delay to a much greater degree than the traditional approach of minimizing the maximum flow. Therefore, for delay-sensitive IoT applications, HGL-MFC may be a better choice.

Although HGL is proved to work well in network layer, there is still much room for improvement to integrate HGL into higher layer protocols. For example, multi-path routing concept of HGL may sometimes lead to packet reordering. In case of connection-oriented transport protocols (e.g. TCP), this phenomenon may result in the transmission of duplicate acknowledgments and unnecessary halves of the congestion window. Fortunately, a number of TCP-enhanced technologies, such as TCP-PR,⁵⁸ FLARE,⁵⁹ and ALBAM,⁶⁰ can resolve this problem. Therefore, in the works that follow, we hope to integrate proper TCP-enhanced technology in the design of HGL and conduct further evaluation. Second, the baselines of the IoT traffic demands of LEO satellite networks may need to be revised using realistic traffic traces and appropriate prediction algorithms. Big data,^61–63 wavelet analysis,⁶⁴ and support vector regression^65–69 technologies would be helpful for analyzing traffic characteristic and designing better traffic model. Therefore, in future work, we hope to address more real-world projects, collect realistic traces, and find appropriate traffic prediction algorithms suitable for IoT and satellite environments.

Footnotes

Academic Editor: Xuyun Zhang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This study was supported by the National Natural Science Fund for Distinguished Young Scholar (grant no. 61425012) and the Fundamental Research Funds for the Central Universities (2014PTB-00-02) in China.

References

Miao

. Research on the architecture and key technology of Internet of Things (IoT) applied on smart grid. In: Proceedings of the IEEE international conference on advances in energy engineering (ICAEE), Beijing, China, 19–20 June 2010, pp.69–72. New York: IEEE.

Dam

RVD

. Internet of Things, smart spaces, and next generation networking. Berlin: Springer, 2013, pp.1–12.

BeiDou Navigation Satellite System. http://en.beidou.gov.cn/

Kawamoto

Nishiyama

Fadlullah

. Effective data collection via satellite-routed sensor system (SRSS) to realize global-scaled Internet of Things. IEEE Sens J 2013; 13(10): 3645–3654.

Aazam

Hung

Huh

. Cloud of Things: integrating Internet of Things with cloud computing and the issues involved. In: Proceedings of international Bhurban conference on applied sciences and technology, Islamabad, Pakistan, 14–18 January 2014, pp.414–419. New York: IEEE.

Rao

BBP

Saluia

Sharma

. Cloud computing for Internet of Things & sensing based applications. In: Proceedings of the sixth international conference on sensing technology (ICST), Kolkata, India, 18–21 December 2012, pp.374–380. New York: IEEE.

Botta

Donato

Persico

. On the integration of cloud computing and Internet of Things. In: Proceedings of the 2nd IEEE international conference on future Internet of Things and cloud, Barcelona, 27–29 August 2014, pp.23–30. New York: IEEE.

Babu

Lakshmi

Rao

. A study on cloud based Internet of Things: CloudIoT. In: Proceedings of global conference on communication technologies (GCCT), Thuckalay, India, 23–24 April 2015, pp.60–65. New York: IEEE.

Sanctis

Cianca

Araniti

. Satellite communications supporting Internet of Remote Things. IEEE Internet Th J 2016; 3(1): 113–123.

10.

Organisation for Economic Co-operation and Development. OECD digital economy outlook2015, http://ec.europa.eu/eurostat/documents/42577/3222224/Digital+economy+outlook+2015 (2015, pp.239–280).

11.

Liu

Han

Wang

. Performance analysis of routing algorithms in satellite network under node failure scenarios. In: Proceedings of the IEEE global communications conference (GLOBECOM’14), Austin, TX, 8–12 December 2014, pp.2838–2843. New York: IEEE.

12.

Yan

Zhang

Sun

. A novel routing scheme for LEO satellite networks based on link state routing. In: Proceedings of the IEEE 17th international conference on computational science and engineering, Chengdu, China, 19–21 December 2014, pp.876–880. New York: IEEE.

13.

Chen

Ekici

A routing protocol for hierarchical LEO/MEO satellite IP networks. Wirel Netw 2005; 11(4): 507–521.

14.

Rao

Wang

XL.

Load balancing routing for single-layered satellite networks. J China Univ Post Telecommun 2010; 17(2): 92–99.

15.

Bai

. Compact explicit multi-path routing for LEO satellite networks. In: Proceedings of the IEEE international workshop on high performance switching & routing (HPSR2005), Hongkong, China, 12–15 May 2005, pp.386–390. New York: IEEE.

16.

Chang

Kim

Lee

. FSA-based link assignment and routing in low-Earth orbit satellite networks. IEEE Trans Veh Technol 1998; 47(3): 1037–1048.

17.

Kucukates

Ersoy

Minimum flow maximum residual routing in LEO satellite networks using routing set. Wirel Netw 2008; 14(4): 501–517.

18.

Bertaux

Medjiah

Berthou

. Software defined networking and virtualization for broadband satellite networks. IEEE Commun Mag 2015; 53(3): 54–60.

19.

Bao

Zhao

. OpenSAN: a software-defined satellite network architecture. ACM SIGCOMM Comput Commun Rev 2014; 44(4): 347–348.

20.

Taleb

Mashimo

Jamalipour

. Explicit load balancing technique for NGEO satellite IP networks with on-board processing capabilities. IEEE ACM Trans Netw 2009; 17(1): 281–293.

21.

Korçak

Alagöz

Jamalipour

. Priority-based adaptive routing in NGEO satellite networks. Int J Commun Syst 2007; 20(3): 313–333.

22.

Song

Chao

Yang

. TLR: a traffic-light-based intelligent routing strategy for NGEO satellite IP networks. IEEE Trans Wirel Commun 2014; 13(6): 3380–3393.

23.

Nishiyama

Tada

Kato

. Toward optimized traffic distribution for efficient network capacity utilization in two-layered satellite networks. IEEE Trans Veh Technol 2013; 62(3): 1303–1313.

24.

Kawamoto

Nishiyama

Kato

. A traffic distribution technique to minimize packet delivery delay in multilayered satellite networks. IEEE Trans Veh Technol 2014; 62(7): 3315–3324.

25.

Nishiyama

Kudoh

Kato

. Load balancing and QoS provisioning based on congestion prediction for GEO/LEO hybrid satellite networks. Proc IEEE 2011; 99(11): 1998–2007.

26.

Xie

Wang

YX.

Construction of tree network with limited delivery latency in homogeneous wireless sensor networks. Wirel Pers Commun 2014; 78(1): 231–246.

27.

Shen

Tan

Wang

. A novel routing protocol providing good transmission reliability in underwater sensor networks. J Internet Technol 2015; 16(1): 171–178.

28.

Shafiq

Liu

. A first look at cellular machine-to-machine traffic: large scale measurement and characterization. ACM Sigmetr Perform Eval Rev 2012; 40(1): 65–76.

29.

Romirer-Maierhofer

Schiavone

D’Alconzo

Device-specific traffic characterization for root cause analysis in cellular networks traffic monitoring and analysis. Berlin: Springer, 2015, pp.64–78.

30.

Pratt

Raines

Fossa

. An operational and performance overview of the IRIDIUM low earth orbit satellite system. IEEE Commun Surv Tutor 1999; 2(2): 2–10.

31.

Wang

Xie

Qiu

. COPE: traffic engineering in dynamic networks. ACM SIGCOMM Comput Commun Rev 2006; 36(4): 99–110.

32.

Ahuja

Magnanti

Orlin

JB.

Network flows: theory, algorithms, and applications. Upper Saddle River, NJ: Prentice Hall, 1993.

33.

Guan

. Towards efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE Trans Inf Forensic Secur 2016; 11(12): 1.

34.

Xia

Wang

Sun

. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans Parallel Distrib Syst 2015; 27(2): 340–352.

35.

Ren

Shu

. Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE Trans Parallel Distrib Syst 2016; 27(9): 2546–2559.

36.

Yuan

Sun

Fingerprint liveness detection based on multi-scale LPQ and PCA. China Commun 2016; 13(7): 60–65.

37.

Sun

Liu

. Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans Commun 2015: 98(1): 190–200.

38.

Ren

Shen

Wang

. Mutual verifiable provable data auditing in public cloud storage. J Internet Technol 2015; 16(2): 317–323.

39.

Guo

Wang

. A variable threshold-value authentication architecture for wireless mesh networks. J Internet Technol 2014: 15(6): 929–936.

40.

Xia

Wang

Zhang

. A Privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing. IEEE Trans Inf Forensic Secur 2016; 11(11): 2594–2608.

41.

Zhou

Wang

QMJ

. Effective and efficient global context verification for image copy detection. IEEE Trans Inf Forensic Secur 2016; 12(1): 48–63.

42.

Yang

. Segmentation-based image copy-move forgery detection scheme. IEEE Trans Inf Forensic Secur 2015, 10(3): 507–518.

43.

Xia

Wang

Sun

. Steganalysis of LSB matching using differences between nonadjacent pixels. Multimed Tool Appl 2016; 75(4): 1947–1962.

44.

Zheng

Jeon

. Image segmentation by generalized hierarchical fuzzy C-means algorithm. J Intell Fuzzy Syst 2015; 28(2): 961–973.

45.

Chen

Shu

Coatrieux

. Color image analysis by quaternion-type moments. J Math Imaging Vis 2015; 51(1): 124–144.

46.

Zhou

Tang

. Social network and tag sources based augmenting collaborative recommender system. IEICE Trans Inf Syst 2015; 98(4):902–910.

47.

Pan

Lei

Zhang

. Fast motion estimation based on content property for low-complexity H.265/HEVC encoder. IEEE Trans Broadcast 2016; 62(3): 1–10.

48.

Pan

Zhang

Kwong

Efficient motion and disparity estimation optimization for low complexity multiview video coding. IEEE Trans Broadcast 2015; 61(2): 166–176.

49.

Mauger

Rosenberg

QoS guarantees for multimedia services on a TDMA-based satellite network. IEEE Commun Mag 1997; 35(7): 56–65.

50.

Zhao

Sun

. A survivable routing protocol for two-layered LEO/MEO satellite networks. Wirel Netw 2014; 20(5): 871–887.

51.

Zhao

Sun

. Dynamic fault-tolerant routing based on FSA for LEO satellite networks. IEEE Trans Comput 2013; 62(10): 1945–1958.

52.

Long

Satellite network robust QoS-aware routing. Berlin: Springer, 2014, pp.75–92.

53.

Zhu

. FASA: accelerated S-ALOHA using access history for event-driven M2M communications. IEEE ACM Trans Netw 2013; 21(6): 1904–1917.

54.

Assad

AA.

Multicommodity network flows: a survey. Networks 1978; 8(1): 37–91.

55.

Zhang

Sun

Wang

BW.

Efficient algorithm for k-barrier coverage based on integer linear programming. China Commun 2016; 13(7): 16–23.

56.

Karakostas

Faster approximation schemes for fractional multicommodity flow. ACM Trans Algorithm 2008; 4(1): 166–173.

57.

Tang

Feng

. Rollback links characterization for the snapshot routing algorithm in polar-orbit satellite networks. IEICE Trans Commun 2015; 98(8): 1715–1724.

58.

Bohacek

Hespanha

Lee

. A new TCP for persistent packet reordering. IEEE ACM Trans Netw 2006; 14(2): 369–382.

59.

Kandula

Katabi

Sinha

. Dynamic load balancing without packet reordering. ACM SIGCOMM Comput Commun Rev 2007; 37(2): 51–62.

60.

Zhong

Yeo

Lee

BS.

Adaptive load balancing algorithm for multiple homing mobile nodes. J Netw Comput Appl 2012; 35(1): 316–327.

61.

Zhang

. Structural balance theory-based E-commerce recommendation over big rating data. IEEE Trans Big Data. Epub ahead of print 16 September 2016. DOI: 10.1109/TBDATA.2016.2602849.

62.

Dou

. A context-aware service evaluation approach over big data for cloud applications. IEEE Trans Cloud Comput. Epub ahead of print 23 December 2015. DOI: 10.1109/TCC.2015.2511764.

63.

Dou

Chen

JJ.

Weighted PCA-based service selection method for multimedia services in cloud environment. Computing 2016; 98(1): 195–214.

64.

Wen

Shao

Xue

. A rapid learning algorithm for vehicle classification. Inf Sci 2015; 295(1): 395–406.

65.

Xia

Wang

Sun

. Steganalysis of least significant bit matching using multi-order differences. Secur Commun Netw 2014; 7(8): 1283–1291.

66.

Sheng

Tay

. Incremental support vector learning for ordinal regression. IEEE Trans Neural Netw Learn Syst 2015; 26(7): 1403–1416.

67.

Sun

Sheng

VS.

Structural minimax probability machine. IEEE Trans Neural Netw Learn Syst 2016; 1: 1–11.

68.

Sheng

Wang

. Incremental learning for -support vector regression. Neural Netw 2015; 67: 140–150.

69.

Sheng

VS.

A robust regularization path algorithm for -support vector classification. IEEE Trans Neural Netw Learn Syst 2016; 1: 1–8.

HGL: A hybrid global-local load balancing routing scheme for the Internet of Things through satellite networks

Abstract

Keywords

Introduction

Related works

IoT traffic demand of LEO satellite networks

Predictable long-range baseline

Unpredictable short-range fluctuations

Technical design of HGL

Overview of HGL

Preliminary optimal traffic allocation

Local route adjustment

The setting of α and β

The setting of detour ratio χ

In the bottleneck satellite

In the upstream satellites

Loop-free design

Performance evaluation

Simulation setup

Simulation results

Packet loss rate

Average end-to-end delay

Traffic distribution index

Route oscillation

Communication overhead

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

The setting of $α$ and $β$

The setting of detour ratio $χ$