Cuiqin Dai,Qingyang Song＊

1 School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China

2 Chongqing Key Lab of Mobile Communication Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

3 School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

Abstract:To satisfy the increasing demands of high-speed transmission,high-efficiency computing,and real-time communications in the high-dynamic and heterogeneous networks,the Contact Plan Design (CPD) has attracted continuous attention in recent years,especially for the spatial-node-based Internet of Everything (IoE).In this paper,we study the NP-hardness of contact scheduling and the attenuation of atmospheric precipitation in the spatial-node-based IoE.Two heuristic computing methods for contact plan design are proposed by comprehensively considering the time-varying topology,the intermittent connectivity,and the adaptive transmission in different weather conditions,which are named Contact Plan Design-Particle Swarm Optimization (CPD-PSO) and Contact Plan Design-Greedy algorithm with the Minimum Delivery Time (CPD-GMDT) separately.For the population-based algorithm,CPD-PSO not only solves the CPD problem with a limited-resource condition,but also dynamically adjusts the search scope to ensure the continuous searching capability of the algorithm.For the CPD-GMDT that makes CP decisions based on the current state,the algorithm uses the idea of greedy algorithm to schedule Satellite-Platform Links (SPLs) and Inter Satellite Links (ISLs) respectively using the strategies of optimal matching and load balancing.The simulation results show that the proposed CPD-PSO outperforms Contact Plan Design-Genetic Algorithm (CPD-GA) in terms of fitness and delivery time,and CPD-GMDT presents better overall delay than Fair Contact Plan (FCP).

Keywords:Internet of Everything; heuristic computing; contact plan design; particle swarm optimization; greedy algorithms

I.INTRODUCTION

As an evolution of the Internet of things (IoT),the Internet of Everything (IoE) is not only a system composed of smart physical devices,vehicles,and other items embedded with various electronics,sensors and processors,but also the integration of various networks to achieve high-speed data service at low cost and realize wide area coverage [1-3].It will create unprecedented volume of complex data which must be stored,processed and transmitted in real time for more time-sensitive applications.This emerging wave requires not only intelligent computing ability,dynamical assigning network resource in real-time sensitive workloads,but also seamless mobility support.Therefore,more and more attention is focused on the design of novel computing methods by integrating with artificial intelligence and other new emerging technologies in spatial-nodebased IoE [4-6].

Since the invention of the internet,computing has changed a lot.In the initial stage,there are only single processors which provided the computing power.Later parallel computing concept enters the scene,soon after it evolves to distributed and grid computing,and finally Cloud Computing (CC) paradigm emerges.As an Internet-based computing method,CC is conventionally considered where sharing and virtualizing of hardware,software,and information resources are provided on-demand.In [7],authors present an integrated satellite CC framework for the Internet of satellite networking,which can not only enrich conventional virtualization of computing,storage and networking resources,but also reduce cost and increase availability,scalability and flexibility by cooperation between spatial nodes and ground nodes.A novel Fog-computing-based Radio Access Network (F-RAN) architecture is proposed and challenges of adaptive transmission modes are studied in [8].In contrast to CC,Fog Computing (FC) is more centralized as a highly virtualized platform to provide computation,storage,and networking between the end nodes in the IoT and traditional clouds [9-11].Stated thus,it seems that these computing methods can offer many advantages,whereas there are some concerns which are not inevitable for the IoE paradigms,especially for the spatial-node-based IoE.

The spatial-node-based IoE,consists of all the web-enabled devices that collect,send and act on data they acquire from their surrounding environments using spatial sensors,processors and communication hardware.In the spatial-node-based IoE,satellite nodes are always used for remote sensing,navigation and communications.However,the connections of inter satellites and connections from satellites to ground stations are frequently interrupted due to orbital mechanism,which leads to the time-varying feature of spatial network topology.Because of the intermittent connectivity between nodes,the spatial nodes can only transfer data when there is an available temporal link (i.e.,contact).By exploiting the predictable nature of the contacts in satellite networks,Contact Graph Routing (CGR) is proposed to determine the routing scheme for time-varying topologies [12].Nevertheless,the time-varying topology and the intermittent connectivity make it difficult for spatial nodes to fully utilize all potential contacts,i.e.,only one of the contacts can be activated at a satellite at the same time.In light of this problem,Contact Plan Design (CPD) was proposed to address the issue of the contact scheduling in satellite networks [13].

In CPD,early works focused mainly on the connectivity between satellites,but not addressed the time-evolving nature of satellite networks.With the concern of topology information,authors in [14] aimed to minimize the total cost of networks by building a sparse structure from the original topology,whereas the constraints on resource usage was ignored.In the condition of limited transponders,the concept of fairness for CPD was first introduced in [15],which aimed to maximize the fairness in link assignment.In [16],authors tried to maintain the advantage in fairness while minimizing the overall route delay based on simulated annealing algorithm.To further improve the overall delay in the satellite network,a genetic-based algorithm named Contact Plan Design-Genetic Algorithm (CPDGA) was proposed in [17].With the consideration of differentiated missions,energy budget and link capacity were jointly addressed in [18].Unfortunately,on the one hand,almost all of aforementioned CPD schemes were proposed for satellite networks,which could hardly meet the requirements of massive and timely data transmission in space communications; on the other,the time-varying topology and intermittent connectivity make spatial nodes unable to fully utilize all the potential contacts,and there will be a conflict in contact establishment between the spatial nodes.In order to meet requirements of the spatial-nodebased IoE in terms of high-speed transmission,high-efficiency computing,and real-time communications,more novel computing methods need to be introduced for CPD.

In addition,the spatial-node-based IoE will bring together spatial nodes,air nodes,and ground nodes to satisfy the explosively increasing demands of real-time and low-delay transmission of massive spatial data,and making networked connections more relevant and valuable.However,the line-of-sight (LOS) communication between the satellite and ground station is easily blocked due to the rain attenuation,long distance and masking effect.For the sake of the reliability of the spatial data transmission,High Altitude Platforms (HAPs) are introduced into the spatial-node-based IoE networking to perform collaborative communications with traditional satellite nodes [19-21].HAPs have the feature of short range LOS and a rapid roll-out capability and the ability to serve a large number of users [22].Since an HAP is placed in the stratosphere,it has good links to both satellites and ground stations,and may improve system performance in terms of throughput or energy usage [23].Therefore,the spatial-node-based IoE networking by integrating satellites,HAPs and earth stations is attracting more and more attention,which further increases the difficulty of CPD [24].

In this paper,we study the CPD problem to minimize the overall delay time with cross-layer cooperation in a spatial- nodebased IoE which consists of satellites,HAPs,and ground stations.The main contributions of this research can be summarized as follows:

·Firstly,aiming to develop the transmission efficiency in Platform-Earth Links (PELs) and cooperate with the following contact scheduling in Inter Satellite Links (ISLs) and Satellite-Platform Links (SPLs),the data on HAPs are adaptively modulated according to the different weather conditions in the downlink of PELs.

·Next,we propose a population-based computing method named Contact Plan Design-Particle Swarm Optimization (CPDPSO).The binary string is encoded and corrected to get the Contact Plan (CP) that meets the constraint in CPD.Besides,through the population-based iterative computing,the search scope of the particle can be adjusted dynamically to design the CP with the minimum delivery time.

·Last,we propose a state-based computing method named Contact Plan Design-Greedy algorithm with the Minimum Delivery Time (CPD-GMDT).The algorithm performs optimal matching for SPLs and at the same time implements the load balancing strategy for satellite nodes through ISLs.The aggregation of the two types of link scheduling schemes constitutes the CP at the current state.

The remainder of this paper is organized as follows.Section II presents the system model,which is composed by network model and channel model.Section III details the adaptive transmission scheme on HAPs.Sections IV and V describe the proposed heuristic computing methods,which are CPD-GMDT and CPD-PSO,respectively.In Section VI,the proposed algorithms are compared with two classical CPD algorithms by simulations,and the conclusion is drawn in Section VII.

II.SYSTEM MODEL

Characterized by wide band and small-sized terminals,Ka-band is well suited for satellite communication.However,the channel quality of the Earth-Satellite Link (ESL) in Ka-band is severely affected by weather conditions in LEO satellite communication.If the communication link is built directly between the LEO satellite and the ground node,the channel state will change drastically as the satellite moves,which could further affect the stability of the network performance.

In view of the above,the spatial-node-based IoE system is constructed by integrating satellites,HAPs and earth stations.As shown in Figure 1,the ESL is divided into the PEL and the SPL whose channel characteristics are more stable.Here,we assume that HAPs and earth stations are static,and PELs between HAPs and earth stations can be constantly established,which are marked with the solid line in figure 1.Due to the periodic movement of satellites,the connection status of ISLs and SPLs may change over time,so ISLs and SPLs are represented by dashed lines.In this paper,the purpose of data detour to the high-level network is to complete the delivery task as early as possible.In order to avoid wasting unnecessary link resources,oneway and double-way arrows are used in Figure 1 to indicate whether data can be transmitted back between nodes.In the following,the system model is divided into network model and channel model,and each of them is presented in detail.

Fig.1.System model.

Fig.2.Space-time graph of the spatial-node-based IoE.

2.1 Network model

The contact between satellites in the spatialnode-based IoE is interrupted frequently due to the orbital mechanism,which means that the topology changes frequently during the data transmission.As shown in figure 2,the time-evolving network model is illustrated by the space-time graph,and HAPs are also included in the graph.

In figure 2,the continuous network is divided into several static topologies,each of them corresponds to a stateC1,C2,…,Cn.Each state has a certain duration of time [t0,t1],[t1,t2],...,[t n-1,tn],which is called contact timeCT1,CT2,…,CTn.The network topology remains the same during the state and changes when the time reaches the end or beginning of the state.Here are some related restrictions in the network model as follows.

wheresandpdenote satellite nodes and HAP nodes respectively,and their numbers are denoted asNsandNh.nandmdenote thenthsending node and themthreceiving node respectively.Bcn,refers the load of nodenat statec.Xcnm,,indicates the data size traversing from nodento nodem.Pcnm,,denotes the number of transponders that nodencontact with nodem.CTcindicates the contact time at statec.For the sake of simplicity,we assume the bandwidth of each contact is constant and equal,thenCTccan also be called the contact capacity of statec.

Equation (1) specifies the flow balance in the spatial-node-based IoE.Equation (2) emphasizes the limited transponder number caused by resource constraints on satellites and HAPs,and the HAPs are inhabited to transmit data back to satellites.Equation (3) imposes that the transmission amount of any contacts should be no greater than contact capacity.

2.2 Channel model

It is well known that rain attenuation is the most influential factor in Ka-band communications when links are in line-of-sight (LOS) condition.Unlike the ESL of Geosynchronous Earth Orbit (GEO) satellite communication,there is no mature solution to the modeling of LEO downlink channels in the Ka-band at present because of the unstable channel and insufficient measured data.To address the issue in a simple way,the HAP node in the system model can divide the dynamic changing ESL into two parts,the SPL and the PEL.Although the length of the SPL still varies with the satellites movement,the height of HAPs protects the communication link free from bad weathers.In Addition,since both the ends of the PEL are static nodes,the channel characteristic of the link is more stable,and the HAP nodes can perform adaptive transmission according to the weather conditions to maximize the transmission efficiency.For simplification,the measured data of PELs can be replaced by that of the ESL of GEO satellite communication.Since the ground nodes in the model are stationary and there are a lot of LOS signals in the PEL,C.LOO [25] channel model is adopted.Then the received signal can be expressed as (4),

whererindicates the envelope of the received signal.zdenotes the LOS component,and the component is subject to the Lognormal distribution when the model in the impact of shadowing.wis the multipath component which is subject to the Rayleigh distribution.φandφ0are the phases that obey the uniform distribution over [0,2 ]π.Since there is no large shelter around the earth station,and thuszis constant and the Probability Distribution Function (PDF) of the signal follows the Rician distribution in (5),

whereσ2denotes the power of the multipath signal,Adenotes the peak amplitude of the LOS signal,andI0indicates the zeroth modified Bessel function of the first kind.

In the satellite communication with Kaband,the PDF of the envelope and phase of the received signal are Gaussian distribution [25],which are shown in (6) and (7),

wherepw(r) andpw(φ) denote the PDF of the envelope and phase.m′ andσ′2are the mean and variance of the envelope of the received signal.m′ andσ′2are the mean and variance of the phase of the received signal.

Compared with the loss caused by signal envelope,the loss due to phase fading can be negligible.Therefore,the following calculation of the system performance only considers the envelope fading.The C.Loo model assumes that the weather-induced fading and ground-induced fading are independent of each other,so the envelope of the received signalpr(r) can be expressed as (8),

III.ADAPTIVE TRANSMISSION SCHEME

The adaptive transmission scheme in this section is introduced to cooperate with the following contact scheduling so as to improve the delivery efficiency.In this section,we first evaluate the performance of different modulation modes under different weather conditions by simulation,and then decide the modulation modes based on the weather conditions at each earth station and a predetermined Bit Error Rate (BER) threshold.

Six kinds of modulation schemes commonly used in satellite communication are adopted in our scheme:QPSK,8-QAM,16-QAM,32-QAM,64-QAM,and 128-QAM.The coding methods of data are both Low Density Parity Check (LDPC) code with a coding rate of 1/2.The BER calculation of M-PSK and M-QAM are presented below.

Table I.The channel envelopment model in PELs.

Fig.3.The BER under clear weather.

Fig.4.The BER under light rain weather.

For M-QAM,the instantaneous BER of the M-QAM constellation [26] is shown as (9),

whereQ()⋅ refers to q-function,which equals to the expressionis the Signal to Noise Ratio (SNRs) of the signal,andThen,the average BER of the system is shown in (10),

For M-QPSK,the instantaneous BER of the M-QPSK constellation [26] is shown as (11),

where ζ M=max(log 2 M,2),andbk=sin((2k-1)π/M).

Similarly,the instantaneous BER of M-PSK can be obtained by bringing (11) along with (8) into (10).

Based on the above calculation of instantaneous BER under different weathers,six modulation schemes are simulated under different SNRs.With the consideration that the earth station is located at the suburbs,the Rice K factor is set to 28 [26].The parameters of channel envelopment are shown in Table I.

From figure 3 to 5,we can observe that the BER always decreases with the increasing SNR at any of the weather conditions.When the weather condition is fixed,the higher the modulation order,the higher the BER observed,which is in line with the expected result.Similarly,when both the SNR and the modulation scheme are fixed,the greater the rainfall,the higher the BER is.Based on the above results,the SNR is set to a fixed value of 15,and the highest BER of the system is set to 10-6.The simulation with different modulation schemes under different weathers is shown in figure 6.

Based on the simulation results in figure 6,128-QAM,32-QAM,and QPSK are selected under the weather of clear,light rain,and rain.After determining the modulation mode,each HAP establishes a transfer table which contains forested weathers,the beginning and ending time of each forested weather,modulation schemes,and corresponding transfer rates.For a population-based heuristic that has completed a single iteration and obtained the result of the link assignment,the determined transfer rate can cooperate with the algorithm to evaluate the merits of each individual.For a state-based heuristic that aims to minimize the delivery time,the determined transfer rate can cooperate with the load to estimate the time it takes to deliver the loaded data.Based on the conclusions drawn in this section,the CPs for ISLs and SPLs are designed in the subsequent two sections.

IV.CONTACT PLAN DESIGN-PARTICLE SWARM OPTIMIZATION

As the basement of CPD-PSO,the PSO algorithm is a metaheuristic algorithm that simulates the behavior of birds randomly searching for food.CPD-PSO not only solves the CPD problem with a limited-resource condition,but also dynamically adjusts the search scope to ensure the continuous searching capability of the algorithm.The algorithm updates the position and velocity of particles through the interaction of various information among them,and then iteratively brings the particle swarm closer to the optimal solution.However,due to the limited resources on CPD,it is not easy to extend the PSO algorithm to CPD while keeping the search efficiency of the algorithm.

The overall process of CPD-PSO is shown in figure 7.In the initial stage,a series of parameters that related to the algorithm such as the initial topology of the spatial-nodebased IoE,the number of particles (i.e.,group size),inertia weights,acceleration constants and the maximum number of iterations of the algorithm are needed to input.Then,a random binary string is coded to represent a set of initial candidate CPs.Since the random encoding does not consider the issue of the transponder constraint in CPD,the next step is the correction of the string.After this,the particles are evaluated,and get the corresponding fitness that can indicate the merits of particles.Then,determine whether the algorithm needs to continue iteration,if necessary,the algorithm continues with the following steps,otherwise it terminates.Next,the historical optimal information is updated based on the comparison between current fitness and historical fitness.To push the particles closer to the optimal position,the next step is to update the position and the velocity of the particle with various dynamic and static parameters.Since the update rule in CPD-PSO is only affected by the position and the velocity of particles,the renewed position may break the constraint,and thus continue with the correction part.The detailed process of the algorithm is described in below.

Fig.5.The BER under rain weather.

Fig.6.The BER under different weathers.

Fig.7.The overall flow chart of CPD-PSO.

Fig.8.The encoding and correction in CPD-PSO.

PSO was originally proposed to solve the optimization problem of continuous function.However,the CPD problem is based on discrete space.To adapt to CPD,CPD-PSO codes the CP as a string of binary numbers.The string is composed of several binary substrings,and the length of the substring and the value of each position are determined by the topology structure of corresponding state.Taking the initial topology of the space-time graph in figure 2 as an example,the encoding and correction method are described in detail below.

Since the total number of contacts that can be established at the first state of the system is eight,the length of the first binary substring in figure 8 is eight.Each binary value in the substring has a corresponding meaning.For example,when the first position of the first substringPcss1,1,2is 1,this means that the connection between satellites1and satellites2at statec1is established.Since the generated string does not consider the constraint of CPD,it needs to be corrected.On the one hand,it is forbidden for the unloaded sender to build links so as to avoid wasting link resource.On the other hand,considering that a node can only utilize one transponder to transmit data at the same time,the link to be built is randomly selected among the conflicted links.

In order to highlight the superiority of different particles in the group,the evaluation step calculates the fitness of each particle to distinguish the quality of each particle.The evaluation function as shown in (12),

whereNeindicates the number of earth stations,andTcis the cumulative delivery time of the system as of the statec.

Since only the PELs have a direct effect on the overall delivery time,the fitness of the particle will be affected if and only if the sender is a HAP and the receiver is an earth station.Besides,to ensure that the overall delivery time can be continuously optimized during the iteration,CPD-PSO penalizes the part of the particles which consume the longest time in the group.Specifically,the fitness of the penalized particles is forced to change to the lowest fitness value in the group.The relationship among the number of penalized particlesθp,punishment ratioRpand group sizeGcan be represented as:θp=G⋅Rp.After completing the above steps,the algorithm determines whether the termination conditions are reached.The algorithm chooses the static mechanism of termination,when the iteration reaches a certain number of times,the algorithm terminates,or performs the main optimization operation of CPD-PSO below.

To ensure that the group gradually approaches the optimal solution during the iteration process,CPD-PSO needs to save the optimal position found by each particle and the corresponding fitness of the position.If the particle finds a position with better fitness,the saved historical optimal position of the particle is updated.After this,the particle updates its position based on the current position,the historical optimal position,and the inertial velocity to bring itself closer to the optimal solution.The detailed process of the update is shown below.

To illustrate the optimization process of particles,we abstract the change of one-dimensional real number as the movement of particles in the square graph.Influenced by a series of factors,the position of the particle eventually falls in a triangle zone which is divided by a bisector.If the position falls in the “1” region of the upper half,the output is 1,otherwise 0.For the update of velocity,the update can be decomposed into two processes.Firstly,the velocity of the particle is affected by its own inertia velocityvij,and its historical optimal positionp i,j(t).The velocity after being affected for the first time is denoted asvij,′ in figure 9.Then,the velocityvij,′ is affected by the historical optimal positionp i,g(t) which is found by the particle group,and the position after this update is the final position of the particle in the current iteration.The update of velocity can be expressed by the following (13).

where subscriptidenotes the label of the current particle in the group,andjdenotes the positionjin the binary string.vi,j(t) andvi,j(t+ 1) denote the velocity of the particle in the iteration times ofnandn+1,respectively.wi(t) is the inertia weight of particleiin the iteration times oft,which is determined by (14).c1andc2,respectively,are learning factors,which determine the strength of the optimum position on the current optimization direction.r1andr2are random numbers in the range of [0,1].

wherewi(t+ 1) denotes the inertia weight of the particleiin the iteration times oft+1.wmaxandwminare the maximum inertia weight and the minimum inertia weight of CPD-PSO.f avg(t) andfmin(t) denote the average fitness and the minimum fitness of the group in the iteration times oft.f i(t) is the fitness of particleiin the iteration times oft.

Fig.9.The movement of the particle in CPD-PSO.

The final position is not only dependent on velocity,but also related to the initial positions of the current iteration times.The updated position of the particle is

Finally,the output of the position is determined as

Since the update mechanism of the position ignores the transponder restriction in CPD,there is a continuing need for the correction and evaluation part.Repeat the above process until the termination condition of CPD-PSO is reached.The final optimal CP searched by CPD-PSO is the historical optimal individual which is continuously saved and updated by the particle group during the iterations.

V.CONTACT PLAN DESIGN-GREEDY ALGORITHM WITH THE MINIMUM DELIVERY TIME

For the CPD-GMDT,it makes CP decisions based on the current state,and can be regarded as a local optimization decision without global consideration.In addition,it uses the idea of greedy algorithm to schedule Satellite-Platform Links (SPLs) and Inter Satellite Links (ISLs) by jointly considering the strategies of optimal matching and load balancing.In CPD,Fair Contact Plan (FCP) is a representative state-based algorithm that maximizes the fairness with low computational complexity.However,the contact time between satellites will change as the state changes,the fairness of establishing times of ISLs in FCP cannot fully guarantee the fairness for data transmission.In addition,pursuing fairness only from the ISLs perspective whereas neglecting the need for data transmission in ESLs is also one of the drawbacks of FCP.In light of the above problems,CPD-GMDT is proposed to minimize the delivery time while achieving load balancing among satellites as much as possible.

Fig.10.The overall process of CPD-GMDT.

Figure 10 shows the overall process of CPD-GMDT.CPD-GMDT divides the CPD problem into two parts:one for SPLs,the other for ISLs.For SPLs,there is fewer communication opportunities between the HAP node and the satellite node,and the establishment of SPLs at different times has a direct impact on overall delay of system.Therefore,the algorithm prioritizes the establishment of SPLs.However,there may be multiple SPLs available in the network at the same time,and there are conflicts of resource usage between these links.At this point,how to schedule these conflicting links and minimize the overall delivery time of the system is one of the problems that CPD-GMDT needs to solve.For ISLs,the purpose of the link in CPD-GMDT is to distribute data to relay satellites so as to provide the sender of SPLs enough data to be delivered as much as possible.However,the contact time of different SPLs in the network is different,the load data on each satellite will continuously flow into the HAPs as the state changes,which will widen the load difference between the satellites.Thus,another issue that CPD-GMDT needs to solve is how to ensure that the sender of SPLs has enough data as the state changes.

For the prioritized SPLs,CPD-GMDT first picks out all the available links for subsequent scheduling.The available SPL means that not only the link exists in the topology,but also the sender of the link is loaded for delivery.The algorithm then traverses all available links and calculates the expected fitness of the system,which is shown in figure 11.

In figure 11,we first assume that all available SPLs are successfully established,and the load on both ends of the links are updated virtually according to the establishment result.It should be noted that the update here does not actually update the load of HAPs,but rather simulates the impact each SPL has on the load of HAPs.For example,when the satellites1establishes the link with HAPh1,the renewed load of HAP nodeh1is denoted ash1,1.If the loads ofs1,s2,ands6are equal,then they have the same effect on the load ofh1,i.e.,h1,1,h2,1,andh6,1are equal.With the help of the updated load information and the transfer table of each node,the delivery time of each HAP is estimated.Since it is hard to predict subsequent specific data transmission,the estimation of delivery time here is based on the assumption that HAP nodes utilize PELs to delivery data to earth stations at any later time.Based on the estimated delivery time,the fitness of the HAP is accordingly calculated by (12).The reason why the following optimal matching is based on the fitness rather than the delivery time is that the evaluation function makes the algorithm more likely to refuse the establishment of the SPLs which results in long delivery time,and thus shorten the overall delivery time of the system.

After completing the virtual establishment of all available SPLs,the final establishment of SPLs at the current state is made based on the estimated fitness value.In our envisioned scenario,one satellite node can only establish a single contact with one HAP node,and the gain brought by the link to the system can be expressed by the predicted fitness.Then,the problem can be regarded as a matching prob- lem.For this feature,the Hungary algorithm is used to find the best match between pairs of nodes,and the matching result is the final CP of SPLs at the current state.

After the scheduling of SPLs,CPD-GMDT plans the establishment of ISLs.Since the algorithm has just scheduled the SPLs at the state,the selection of available ISLs should not only consider the topology and the load issues in the selection of available SPLs,but also confirm whether or not the node has been occupied by the scheduled SPLs.Since the state-based strategy in the algorithm cannot predict the CPs at following states,the algorithm distributes the data to each satellite node as evenly as possible so that the sender of SPLs can efficiently utilize the contact capacity to transfer data when SPLs are available.Thus,the load balancing strategy in CPD-GMDT is to fill the load gap between each satellite node.After all the available contacts at the current state have been planned,the actual load of each node is updated according to the CPD result.In addition,for unplanned PELs,once the HAP is free from the establishment of SPLs,the HAP establishes a PEL to transfer data to the earth station.The iterative process will continue until all nodes have finished their transmission,and the final CP is the accumulation of the CPD results of each state.

Fig.11.The calculation of fitness in CPD-GMDT.

VI.SIMULATION RESULTS AND ANALYSIS

A total of six satellite nodes,four earth stations and four HAPs are set in the system model.With the height of 1000 km,three satellites are spaced at argument of latitude 60°,120°,and 180° along the inclination of 97.86°,the other three are spaced at argument of latitude 90°,180°,and 270° along the inclination of 83.86° [27].Four earth stations locate at Kashi (39.5°N,76°E),Miyun (40.5°N,117°E),Kunming (25°N,103°E),and Sanya (18°N,109°E).The bandwidth of ISLs and SPLs are set to 200MHz,and the modulation and the coding scheme of the links are the QPSK modulation of LDPC code with a coding rate of 1/2.The bandwidth of PELs is set to 50MHz[22].The historical rainfall data for each of the stations is taken from the National Meteorological Data Share Platform of China [28].For the sake of simplicity,we set the size of a packet to 200Mbit,which means that ISLs or SPLs will consume one second each time a packet is delivered.Each satellite node is assigned 2000 packets to be transmitted to earth nodes.The group size of CPD-PSO is set to 40,and the maximum iteration times are 100.The learning factorsc1andc2are both set to 2,and the maximum weightwmaxand minimum weightwminare set to 0.6 and 0.8 respectively.

Fig.12.Performance evaluation of FCP and CPD-GMDT in terms of Jain Index.

For population-based heuristics,we use CPD-GA proposed in [17] as a reference algorithm to compare with the proposed CPDPSO.For state-based heuristics,FCP [15] is adopted to compare with the proposed CPD-GMDT.Since the purpose of the paper is to minimize the delivery time,FCP needs to be optimized to make it more comparable.On the one hand,the FCP designs the CP by considering the fair establishment in ISLs and SPLs,so as to guarantee the HAPs in the network can receive the data as soon as possible.On the other hand,in order to improve link utilization,the FCP forbids the unloaded nodes from establishing links.Furthermore,the transmission mechanism of PELs among all reference algorithms is the same as that of our proposed algorithms.Specifically,when HAPs are free from the establishment of SPLs,the loaded HAPs establish PELs and transmit the modulated data to earth stations.

Since both CPD-GMDT and FCP adopt fair strategies for ISLs scheduling,the Jain index [29] is used to quantify the fairness of loads among satellites.Jain index can be expressed asWhen the Jain index equals the minimum value 1/Ns,it means that only one satellite is loaded.When the Jain index equals the maximum value 1,the load of all the satellites is the same.

In the envisioned network,only a few satellites can establish continuous contacts with HAPs at specific time periods.As the data on satellites are gradually delivered to HAPs,the load distribution of satellites in the network gradually becomes unbalanced,resulting in a decrease of Jain index in figure 12.However,it should be noted that the Jain index also increases with the number of received packets.When the satellites that continuously contact with HAPs cannot communicate with HAPs,the higher-loaded satellites will transmit data to the satellites with lower load.And thus,the load among satellites is balanced and Jain index accordingly increase.Due to the establishment of SPLs takes priority over ISLs in CPD-GMDT,the Jain index of CPD-GMDT decreases sharply in the later stage of transmission.

Figure 13 shows the increase of the number of received packets at HAPs and earth stations in FCP and CPD-GMDT with time.Since the packets need to reach the HAPs before they retransmitted to the earth stations,the overall delivery time of the two algorithms at earth stations are both lag behind the HAPs in figure 13.As the delivery time increases,the growth curves of HAP nodes are stagnant due to the intermittent connection between satellite nodes and HAP nodes.For the comparison between two algorithms,CPD-GMDT estimates the delivery time for each state and schedules the SPLs based on the estimated fitness,which allows the load data on the satellites to be delivered to the HAPs as soon as possible.Thus,CPD-GMDT performs the delivery mission faster than FCP,whether it is a HAP node or earth node.

Figure 14 shows the number of packets received by each earth station in CPD-GMDT and FCP,and the corresponding weather conditions when packets arriving at earth stations are also distinguished in the bar.For the reason of axis length limitation,we simplify CPD-GMDT on the abscissa to CG and FCP to F,so CG1 represents the earth nodese1in CPD-GMDT.Since each HAP in our model can only be connected to a fixed earth station,the amount of data received at each earth station can also be regarded as the received amount of its corresponding connected HAP.The total contact time of each HAP with satellites is different during the whole transfer process,so the amount of received data of each HAP in figure 14 also shows a difference.Compared with FCP,CPD-GMDT schedules PELs according to the optimal matching results,so CPD-GMDT makes better use of the weather conditions for data transmission.

In order to compare the proposed CPDPSO with the referenced CPD-GA more fairly,the group size of CPD-GA is the same as that of CPD-PSO,and the calculation of fitness is showed in (12).Both algorithms share the same randomly generated initial group.Other algorithm parameters in CPD-GA are commonly used values,the crossover rate and mutation rate are 0.4 and 0.05 respectively,and crossover method is a single point crossover.

Fig.13.Performance evaluation of FCP and CPD-GMDT in terms of delivery time.

Fig.14.Performance evaluation of FCP and CPD-GMDT in terms of Received packets at different ground stations.

Since both CPD-GA and CPD-PSO perform iterations with the aim of fitness,the average fitness of the group always increases with the iteration times in figure 15.Although the average fitness of CPD-GMDT is lower than that of CPD-GA in the early stage of iterations,the fitness of CPD-PSO gradually surpass that of CPD-GA with the increase of iteration times.This can be accounted for the fact that no matter how the group iterates in CPD-PSO,each particle saves its own optimal position,which in turn gives a variety of meaningful CPs.For CPD-GA,the algorithm can only get the group information of a single iteration for each iteration.The lack of historical information makes the search scope of CPD-GA shrink faster,resulting in the slowing down of the growth of fitness value with the iteration times and finally lags behind CPD-PSO.

Fig.15.Performance evaluation of CPD-GA and CPD-PSO in terms of average fitness.

Fig.16.Performance evaluation of CPD-GA and CPD-PSO in terms of average delivery time.

As expected,the average delivery time of CPD-PSO and CPD-GA basically decreases with the iteration times in figure 16.The occasional increase of delivery time is due to the fact that the evaluation function cannot fully guarantee that the particles with higher fitness also own the advantage of delivery time,the algorithm may use the delivery time in exchange for the benefits of fitness.In addition,the descending curve of the average delivery time of the CPD-PSO is smoother than that of the CPD-GA.According to the iterative mechanism of CPD-GA,the historical information cannot be preserved,it makes that the algorithm cannot guarantee that the delivery time of each iteration group will be optimized,thus makes that the fluctuation of CPD-GA is more obvious than that of CPD-PSO.

Compared with the evaluation parameters of average fitness and average delivery time,the minimum delivery time can better reflect the optimization ability of algorithms.We can observe that in figure 17,the minimum delivery time of CPD-PSO decreases with iteration times,and its changing rate is obviously faster than that of CPD-GA.This is due to the fact that the particles of CPD-PSO take into account both the historical optimal positions of individuals and groups during the optimization process,and the inertia weight of the current velocity is dynamically adjusted during the iteration,so that the particle can always maintain a reasonable search scope and finally find a better CP.

VII.CONCLUSION

In this paper,we have proposed heuristic computing methods to solve the cross-layer CPD problem in the spatial-node-based IoE.At first,we have constructed an integrated network composed of satellite nodes,HAPs nodes and earth stations.Among them,the HAP node can adaptively modulate the load data according to different weather conditions,which can significantly improve the transmission efficiency.Next,we have proposed two heuristic computing methods to cross-layer design the CPs by collaborating with the adaptive transmission schemes.In the first method which is named CPD-GMDT,the algorithm takes a load balancing strategy for ISLs,while the optimal matching strategy is implemented on SPLs so as to minimize the overall delivery time.For the second which is named CPD-PSO,the algorithm encodes and corrects the CP to output the result that meets the resource limitation,and dynamically adjusts the inertia weight to determine the search scope of the particle so as to improve the search capability of the algorithm.The simulation results demonstrate that the proposed CPD-GMDT is superior to FCP in terms of delivery time,and CPD-PSO outperforms CPD-GA both in fitness and delivery time.

Fig.17.Performance evaluation of CPD-GA and CPD-PSO in terms of minimum delivery time.

ACKNOWLEDGEMENT

This research work was jointly supported by the National Natural Science Foundation in China (61601075,61671092,61771120,61801105),the Fundamental Research Funds for the Central University (N171602002),and the Natural Science Foundation Project of CQ CSTC (cstc2016jcyjA0174).