Resource-constrained maximum network throughputon space networks

1.Department of Electronic Engineering,Tsinghua University,Beijing 100084,China; 2.Departmentof Aeronautics and Astronautics Engineering,Tsinghua University,Beijing 100084,China; 3.Research Institute of Tsinghua University in Shenzhen,Shenzhen 518057,China

Resource-constrained maximum network throughputon space networks

Yanling Xing1,*,Ning Ge1,3,and Youzheng Wang2

1.Department of Electronic Engineering,Tsinghua University,Beijing 100084,China; 2.Departmentof Aeronautics and Astronautics Engineering,Tsinghua University,Beijing 100084,China; 3.Research Institute of Tsinghua University in Shenzhen,Shenzhen 518057,China

This paper investigates the maximum network throughput for resource-constrained space networks based on the delay and disruption-tolerantnetworking(DTN)architecture.Speci fi cally, this paper proposes a methodology for calculating the maximum network throughput of multiple transmission tasks under storage and delay constraints over a space network.A mixed-integerlinear programming(MILP)is formulated to solve this problem.Simulations results show thatthe proposed methodology can successfully calculate the optimalthroughputofa space network under storage and delay constraints,as well as a clear,monotonic relationship between end-to-end delay and the maximum network throughput under storage constraints.At the same time,the optimization results shine light on the routing and transport protocol design in space communication,which can be used to obtain the optimal network throughput.

throughput,disruption-tolerant networking(DTN), maximum fl ow,mixed-integer linear programming,evolving graph, space network.

1.Introduction

Space-based networks(hereafter“space networks”),consisting of satellites,spacecraft and ground stations,represent an importantcomponentof globalwireless networks. For space networks,especially those containing low earth orbit(LEO)satellites,lack of instantaneous end-to-end connectivity poses a distinct feature,which makes it diffi cult to design high-performance network protocols.As we know,the end-to-end throughputis an importantmeasure of network transmission performance.Throughputof a communication system can be affected by allthe layers, from the physicalmedium to the end-userbehavior.When various protocol overheads are taken into account,a useful data rate can be signi fi cantly different.For a network protocol designer,making full use of network resources and providing the optimal end-to-end throughput(hereafter“network throughput”)for all users are the ultimate aim.This is especially importantin space networks.Many institutes,including the Consultative Committee for Space Data Systems(CCSDS)and Internet Engineering Task Force Internet(IETF)Work Group,have worked out differentspace network protocols to improve space transmission performance.Among those,delay-and disruptiontolerant networking(DTN)protocols[1-3]are assumed to be an alternative solution to space networks.The delay tolerance ability is the main feature of DTN protocols. Many jobs have been developed for DTN protocols,such as transmission,routing,quality of service(QoS)and congestion control[4-8].In this paper,we do not intend to study DTN protocols,butto presenta methodology to calculate the maximum throughputoverspace networksbased on the DTN architecture and obtain an optimal solution for routing and traf fi c allocation.Note thattransmission is assumed to be lossless for simplicity.Multiple tasks run parallelin our scenario.Intermediate nodes have the capability of temporarily storing data.

As end-to-end routing in space networks is time-variant, the end-to-end throughput in space network is timedependent.And the instantaneous value is not enough to represent space network throughput.Therefore,the average amount of data over the transmission period is referred to as the space network throughput.Thus,for space networks,the throughputcan also be measured in bits per second(bit/s or bps).Clearly,in the DTN architecture,the capabilities of delay tolerance and node storage should be taken into consideration.Yetspace networks are resourceconstrained,the two capabilities should be limited.There-fore,our objective is to study the space network throughput in the condition of delay-constrained and resourceconstrained.In view of high dynamic of space networks, it is dif fi cult to give a close expression for the space network throughput;instead,we willgive an upper bound of itby calculation.

As we know,in the graph theory,a transmission upper bound over a static network can be obtained by solving a classical maximum fl ow problem[9-10].While in space networks,network topologies are time-variant,and a hop needs to go through a long distance.Transmission from end-to-end may take multiple hops and continue forseveral minutes,even severalhours.Thus,the classical maximum fl ow algorithm cannotbe directly employed to calculate the maximum throughputon space networks.Nevertheless,we will refer to the method presented in the classical maximum fl ow theory and propose a new version for the time related maximum throughput.

The main contributions of this paper are as follows.We model space networks with the time-dependent evolving graph.We then formulate the problem as a mixed-integer linearprogram and develop an algorithm to fi nd allchronologically feasible paths for a task.We also presentan optimalsolution by optimizing the totalamountof data over the feasible paths.We fi nally conduct experiments by simulation to evaluate the proposed algorithms.The experimentalresults show thatthe proposed algorithms are feasible in terms ofcalculating the maximum network throughput under time and storage constraints.To the best of our knowledge,this is the fi rst time that the problem of calculating the maximum network throughput for space networks under the DTN architecture with multiple tasks while meeting the delay and storage constraints is considered,and a routing and traf fi c allocation scheme can be used to achieve the optimaltransmission performance.

This paper is organized as follows.In Section 3,the evolving graph theory and space-time paths are brie fl y introduced,and evolving graphs are used to model space networks with some simpli fi cations.In Section 4,a timedependentmaximum fl ow algorithm is proposed to calculate the maximum network throughputfora space network with multiple tasks.Delay constraintand storage constraint are taken into consideration.In Section 5,the design and implementation of network simulations are described,and simulation results are analyzed.Finally,in Section 6,concluding remarks and plans for future work are provided.

2.Related work

Space networks are known for their high dynamics.In space networks,end-to-end communicationsare characterized by long delays,packetlosses,and sometimes intermittentconnectivity and link disruptions.In view of the complexity of space networks,the related researches aboutoptimizing space network throughputmainly concentrate on terrestrial networks currently.Network throughput maximization under a certain constraintwas studied in[11,12]. In[11],the problem of maximizing throughput under a network-wide energy constraint was formulated as a mixed-integernonlinearprogram.The optimalthroughputenergy curves have been provided,which are useful to both network operators and end users.In[12],the problem of throughput optimization in decentralized wireless networks with spatial randomness under queue stability and packet loss constraints was investigated.Researches on delay-throughput tradeoff when maximizing network throughputwere studied in[13-15].All-to-allthroughput maximization in wireless relay networks is aimed at maximizing network throughputwith multiple tasks and detailed in[16].Throughput improvement by network coding and spatial reuse in wireless networks was extensively studied in[17-21].In[22,23],a method of achieving the maximum network throughput based on optimizing scheduling and routing was studied.In[24],a topology controlalgorithm was proposed to optimize the throughput of wireless mesh networks.This paper designs a topology algorithm that can be used to structure network topology and optimize network throughputby combining collision domain load and powercontrol.

All these jobs have been developed for optimizing the terrestrialnetwork throughputby means of designing protocols.Similarly,space networks face the same problem thathow to achieve the optimaltransmission performance with limited resources.Differentfrom terrestrialnetworks, the space network has its particular features,which makes the problem more complex.In this paper,different from the above jobs,we preliminarily investigate the maximum space network throughputby means of theoreticalcalculation and propose a methodology to calculate the value.

3.Preliminaries

3.1 Modeling of space networks

Although network modeling is a key issue to analyze any large-scale wireless network,it is especially crucialto the design of space networks with a couple of distinguishing features.First,because space networks’topologies are time-variant,they cannot be characterized by traditional static models.Second,the deterministic orbital mechanisms make the random movementmodels inappropriate, which are usually used to study terrestrial mobile networks.Fortunately,a new model of the graph theory,the evolving graph(EG)[25-29],was recently proposed for capturing the features ofspace networks.In the EG theory,a space network can be treated as a fi xed schedule dynamic network(FSDN)[25]:infrastructure-less and dynamic, butpredictable.The EG theory could provide a reasonable topological representation for space networks.In EG,a space network G can be represented by G=(V,E,M), wherein V is a set of vertices,E is a set of edges and M is a setof connection intervals.Fig.1(a)shows the topologies of a space network at successive time steps.Fig.1(b) shows the corresponding EG model.

Fig.1 Space network topology and EG model

From Fig.1(b),we can see thatan EGaggregates the series of discrete time sequence subgraphs.A subgraph with an index corresponds to a static snapshotof the space network ata given interval.Intervals’IDs are discrete and labeled atthe corresponding edges.In space networks,topology changes are usually unequalintervals.Allconnection intervals form a set M in the time domain.The transmission time period is denoted by T.Hence,in Fig.1,the time interval set M isconnection intervals.Allthese connection intervals can be obtained from satellite toolkit(STK)software.

3.2 Finding feasible end-to-end paths

To achieve good performance,transmission over multiple paths is a prerequisite.In space transmission,apart from instantaneous direct paths,end-to-end paths with chronological multiple hops are usually feasible and in the majority.However,as time-dependent networks,endto-end paths with chronological multiple hops cannot be immediately obtained in space networks.Fortunately,the EG modelcan be employed to fi nd allfeasible end-to-end paths.Take the space network in Fig.1(b)for example.If the EG modelis not employed,there are only two instantaneous paths from A to C,namely,path A to C atthe 1st, 3rd,and 4th time intervals respectively and path A to B to C atthe 1sttime interval.Yet,ifthe EGmodelis employed and the DTN architecture is taken into consideration,we could present more than two paths from A to C.For example,the path A to B at the 1st time interval,followed by B to C atthe 2nd time interval,is feasible with two intervals of delay.This is a space-time path.To illustrate the issue of feasible paths more clearly,an expanding version of the EG named space-time graph[30]can be used to describe the time-evolving space network.Fig.2 shows the space-time graph for the space network in Fig.1.

Fig.2 Space-time graph ofthe space network and a space-time path (in dotted line)from A to C

When modeling and fi nding feasible paths in space networks,links,nodes and end-to-end delay have the following considerations:(i)alllinks are established according to the line-of-sightprinciple;(ii)in space-based communication,transmission delay is usually measured with millisecond,while link interruption may continue from severalseconds to severalminutes,thus,end-to-end delay mentioned here is mainly composed of link interruption delay;(iii) as resource-constrained networks,the intermediate node storage capacity of space networks is limited to a certain value;(iv)to simplify the problem,transmission is assumed to be lossless.

4.Time-dependent maximum flow algorithm

As mentioned in Section 1,we refer to the classical maximum fl ow to solve the problem presented in this paper. In Section 3,we build the models of space networks.In this section,a time-dependentmaximum fl ow(TDMF)algorithm is proposed to calculate the maximum throughput fora space network.Since the DTN architecture is applied in this paper,end-to-end delay and node-range storage are allowed.Moreover,values of end-to-end delay and node storage capacity should affect the value of the maximumthroughput.Thus,these values will be considered when formulating constraints.From Section 3,we can fi gure out thatmany none instantaneous connection space-time paths can be presented in the EG model,but these space-time paths are notdirectly available.In addition,since multiple tasks run simultaneously in our scenarios,a task is represented by a source-destination(S-D)pair.Thus,the proposed TDMF algorithm comprises two parts:(i)search all chronologically feasible paths for an S-D pair in a given transmission time period with a given end-to-end delay constraint;(ii)establish time-related constraints for each edge and each node based on the paths searched in part (i),and calculate the maximum totalamountof data transferred in the transmission time period by solving a linear programming(LP)formulation,which may be the most naturalmechanism to express the various constraints.

4.1 Algorithm to search allchronologically feasible paths for an S-D pair

This algorithm searches all chronologically feasible paths foran S-Dpairbased on the multi-protocollabelswitching (MPLS)algorithm[31].The motivation presented here is to avoid closed loops by labeling the nodes that have already been visited along a searching path.The search process is divided into three steps and implemented as follows:

Step 1Search all paths from S to D without considering the chronological order.This step consists of three substeps,namely,initialization,fi nding a path from S to D and fi nding allpaths from S to D.

Step 1.1Initialization.Take all edges and associated time intervals of the EG model as the input.Set the visit fl ag of D to-1(marking itas the destination),the visit fl ag of S to 1(marking it visited),and the visit fl ags of other nodes to 0(marking them unvisited).Generate a sparse adjacency matrix A composed of n rows,wherein n is the totalnumberof nodes in the EG model.The m th row vector is composed of the m th node and allits adjacentnodes thatthe node fl ows to.

Step 1.2Recursively search paths from S to D.

Step 1.2.1Push S to stack.Start from S and fi nd the fi rstadjacentnode of S in matrix A.

Step 1.2.2If the adjacent node is node D,then terminate path search process.Otherwise,check whether the node’s visit fl ag is 1.If the resultis 1,then fi nd the node’s nextadjacentnode by repeating this step.Otherwise,go to Step 1.2.3.

Step 1.2.3Setthe visit fl ag of the node to 1 and push it to the stack.Now take the node as the startnode and fi nd its adjacent node in matrix A.Call Step 1.2.2 and Step 1.2.3 recursively untilthe adjacentnode is D.So far,allnodes in stack compose a complete path from S to D.

Step 1.2.4Post-processing.Pop the nodes from stack. For allnods exceptS and D,setthe visit fl ags to 0.

Step 1.3Start from S and fi nd an adjacent node that has notbeen searched.Repeat Step 1.2 untilallpaths from S to D are found.

This concludes the path search process.Operations in the path search process could be illustrated by an example in Fig.3.Note thatnode 1 is the source and node 6 is the destination.Figs.3(c)-(f)are the results of Step 1.2.2 and Step 1.2.3.

Fig.3 Diagram of path search process

Step 2The chronologicalorder is taken into consideration.All chronologically feasible paths from S to D are selected from the paths obtained in Step 1.The principle is thatfora node in a path,atleastone time intervalof its out edge is later than the earliest interval of its in edge.If all of the nodes in a path satisfy the above principle,the path is chronologically feasible,and it is called a subpath of a task.Otherwise,the path is discarded.

Step 3After obtaining the chronologically feasible subpaths,select the subpaths along which the end-to-end delay satis fi es the given delay constraint and output the selected subpaths as a fi nal result set.So far,all feasible subpaths of a task have been found.

Step 4For all tasks,fi nd the fi nal path sets following Step 1 to Step 3.

4.2 Time-dependent mixed-integer linear programming formulation

Based on the obtained path sets,we create a timedependentmixed-integer linear programming formulation to solve the problem presented in Section 1.Before building the programming formulations,we assume that all tasks begin and fi nish simultaneously.In the formulations, we establish time-dependenttraf fi c and storage constraints for each node and each edge.The complete listof parameters in ourtime-dependentformulation is given as follows:

Assume that edge(ni,nj)is the m th sequential edge of subpath p starting from S.Let pmand Xpm,t,pdenote edge(ni,nj)and X(ni,nj),t,prespectively.Note that the up/down link capacity of an edge is assumed to be symmetric,that is U(ni,nj)=U(nj,ni).According to the assumptions made in Section 3,the amount of data over each edge in T for a given subpath is of equal value(the basic conservation law of fl ow)and denoted by yp.

Based on the above statement,the proposed mixedinteger linear programming(MILP)formulations can be expressed as follows:

By maximizing the objective function(1),we get the maximum total amount of data transferred from all of the sources to the destinations over transmission time period T.Inequality(2)expresses the fact that data fl owing over an edge of a subpath at time t cannot exceed its capacity.Equations(3)and(4)state the data conservation law of a subpath.That is,for a subpath,the total amount of data fl owing over an edge is equalto thatof those fl owing over another edge atthe end of transmission.Equation (5)shows that the total amount of data transferred for a task is the sum of the amount of data over each subpath. Inequality(6)expresses the fact that the total input data of a node is greater than or equal to its output data for a given time period.Inequality(7)expresses thatthe difference between the totalamountof data fl owing into a node and thatof those fl owing outof the node mustbe less than Cmax.Finally,inequality(8)is the non-negative constraint for each data fl ow.According to the de fi nition,the maximum network throughputis the value ofthe objective function averaged over T.Thatis

These MILP formulations can be solved by differentoptimization methods,among which optimization software is more preferable.In this paper,we select a professional, mature software tool,IBM CPLEX with version 12.6 to solve this problem.Once end-to-end delay changes,the optimal values will change accordingly.Thus,a quantitative relationship between end-to-end delay and maximum network throughputcould be established.It should be noted that we consider all tasks have the same end-to-end delay constraint,and the end-to-end delay is the sum of delay on each hop over a subpath.In addition,by optimizing, we can obtain X(ni,nj),t,pvalues for a data fl ow,whichactually contain the corresponding routing and traf fi c allocation information.

We should note that the proposed methodology is not aimed ata speci fi c network,butata class of networks that have intermittent connectivity,transmission of long distance and predictable topological change,such as space networks.

4.3 Computation complexity of TDMF algorithm

A simple computation complexity analysis of the TDMF algorithm is given here.The TDMF algorithm is actually a linear programming method.For linear programing formulations,the complexity has signi fi cantdependence with the number of constraints.The upper bound and the lower bound of a linear programing are O(n1.5)and O(n2), wherein n is the number of constraints.In the TDMF algorithm,assume u is the total number of feasible paths, w is the total number of time intervals,then the number of constraints is a linear function of u and w,denoted by au+bw,wherein a and b are two constants that could be calculated fora given network.Thus the computation complexity is between O((au+bw)1.5)and O((au+bw)2).

5.Simulation and analysis

The TDMF algorithm is capable of calculating the maximum network throughputfor any space network.In this section,we provide two typical simulation scenarios to evaluate the accuracy and applicability of it.The fi rst one is based on an iridium-like satellite constellation;and the second one is based on a double layer satellite network.

5.1 Simulation scenarios

5.1.1 Scenario based on an iridium-like constellation

The iridium constellation is the only LEO satellite system with inter-satellite links(ISLs)currently in orbit.Here,we consider an iridium-like con fi guration as the basis of our fi rst simulation scenario.A single task is running from a ground station to another ground station via this constellation in this scenario.In the iridium-like constellation, the orbital parameters and ISLs are the same as the iridium constellation,yet the transmission scheme is somewhat different.We assume thatboth ISLs and satellite-toground links(SGLs)operate at 10 Mbps.Unlike the real iridium constellation,our simulated ISLs do notclose at a high latitude.We take two points G1 and G2 on the ground as our S-D pair,one is in Africa,and the other is in Asia. Due to relative motion,SGLs are intermittentconnections. Fig.4 shows the constellation diagram of the simulation scenario.The link time intervalset for each edge could be obtained by the STK tool.

Fig.4 Diagram of iridium-like constellation scenario

5.1.2 Scenario based on a double layer satellite network Considering the state-of-the-art of space networks in our country and the future needs,a double layer satellite network composed of a medium-earth orbit(MEO)constellation,two LEO satellites and two ground stations are presented as the second scenario,wherein MEO constellation is proposed by Tsinghua University,LEOsatellites are two meteorologicalsatellites of China,namely YAOGAN2 and YAOGAN3,and the ground stations are located in mainland of China,namely Kashi station and Miyun station. MEO constellation is a relay network and it is an inclined orbit rose constellation composed of six MEO satellites. The six satellites are located at six orbits respectively.The speci fi c orbitalparameters are as follows:the semi-major axis is 26 563.1 km,the inclination is 53.13?,and the period is 43 085.4 s.

Two tasks are from the two LEO satellites to the two ground stations respectively via the MEO constellation. In the MEO constellation,there are permanent and nonpermanent ISLs.Non-permanent ISLs are also built between the MEO constellation and LEO satellites,the MEO constellation and ground stations.Both ISLs and SGLs operate at 20 Mbps.Fig.5 shows the constellationand connection diagram of this scenario.The two sources are named S1 and S2.The two destinations are named D1 and D2.Task from S1 to D1 is named as Task 1.

Fig.5 Diagram of 2-layer satellite network scenario

5.2 Results and analysis

5.2.1 Maximum network throughputwith delay and storage constraints

Since end-to-end delay and node storage capacity are two in fl uence factors of network throughput,we study the infl uence in this section respectively.In the fi rst simulation scenario,we inject data into G1 and transfer it continuously to G2 via the iridium-like network over T of 1 000 s. End-to-end delay values are set to 0 s,100 s,300 s,500 s, 800 s,900 s,and 1 000 s,respectively.Table 1 shows the maximum network throughputcalculated for each of these delay values.In the second scenario,we injectdata into S1 and S2 respectively and transfer itcontinuously to D1 and D2 via the 2-layersatellite network over T of7 200 s.Endto-end delay values are set to 0 s,10 s,50 s,100 s,200 s, 500 s,800 s and 1 000 s,respectively.

First,we fi x node storage capacity as in fi nity and study the relationship between end-to-end delay and the maximum network throughput.Table 2 shows the values of the maximum network throughputvs.the values of delay.

Table 1 Delay-throughput relationship for iridium-like satellite network

Table 2 Delay-throughput relationship for 2-layer satellite network

Intuitively,as the value of tolerantend-to-end delay increases,the maximum network throughput will increase. Data presented in Table 1 and Table 2 verify this conclusion.When the delay value is 0 s,the maximum throughputs are attheir minimum,namely 6.53 Mbps for Scenario 1 and 2.1 Mbps for Scenario 2.After that,when the delay value is 1 000 s in Scenario 1,the maximum throughput is at its maximum,45.28 Mbps.Similarly,when the delay value is 1 000 s in Scenario 2,the maximum throughput is at its maximum,14.28 Mbps.It is a monotonic non-decreasing relationship between the end-to-end delay and the maximum throughput.Although these maximum are loose transmission limits,the results present a fact that compared to some non-delay tolerant protocols,such as TCP/IP protocol,DTN protocols are more preferable. Moreover,there is a tradeoff between the high throughput and the smalldelay value.

Second,we willstudy the relationship between the maximum network throughputand node storage capacity with end-to-end delay fi xed.This simulation is based on Scenario 2.Setthe end-to-end delay to 10 s,100 s and 500 s. Under each delay value,set the node storage capacity to 200 Mbits,500 Mbits,1 000 Mbits,4 000 Mbits,8 000 Mbits,and 10 000 Mbits,respectively.Fig.6 shows the curves of maximum network throughputvs.node storage capacity under differentdelay values.

Fig.6 Curves ofthe maximum network throughputvs.node storage capacity under different delay values

From these results,we can see that the proposed methodology is capable of calculating the maximum network throughputfor a space network with delay and storage constraints.At a certain end-to-end delay value,the larger node storage capacity is,the larger the maximum network throughput will be.Moreover,for delay values tested,when node storage capacity reaches a certain value (here for 8 000 Mbits),the maximum network throughput will reach its maximum and notincrease any more.These quantitative relationships tellus thatin space networks,the intermediate node storage capacity needs to be set carefully to achieve the besttransmission performance.

5.2.2 Optimalrouting and traf fi c allocation scheme

In this simulation,we willstudy the transmission requirements to achieve the maximum network throughput,especially for routing and traf fi c allocation.Take the 2-layer satellite network scenario as the simulation object,and set the values of end-to-end delay to 10 s and 100 s and node storage capacity to 500 Mbits.Transmission time period T is 7 200 s.After optimization,the allocation results for each task could be obtained.Table 3 and Table 4 provide the detailed allocation results,i.e.values of X(ni,nj),t,pfor all tasks in time period T,wherein V1to V6representsix MEO satellites respectively.

Table 3 Routing and traffic allocation results(end-to-end delay=10 s,intermediate storage capacity=500 Mbits)

Table 4 Routing and traffic allocation results(end-to-end delay=100 s,intermediate storage capacity=500 Mbits)

From Table 3 and Table 4,we can fi gure out that the TDMF algorithm could not only give the maximum network throughputbut also provide the optimal routing and traf fi c allocation scheme.These results present a theoreticalbasis to design a multi-path routing protocolfor predefi ned tasks in the DTNbased network,which could balance and make full use of network resources.Besides routing protocol,the detailed traf fi c allocation also shine light on the design ofthe DTNtransportprotocol.Anyway,the proposed methodology gives the maximum network throughputfor a space network and provides a method for achieving the maximum.

6.Conclusions

In this paper,we investigate the issue of the maximum network throughput for space networks with multiple tasks under the DTN architecture and resource constraints and propose a methodology to calculate this value,which includes space network modeling and a proposed timedependentmaximum fl ow algorithm.Simulations demonstrate that the proposed methodology is applicable to calculate the maximum for arbitrary space network.Moreover,the relationship between the end-to-end delay and the maximum with storage constraintand the relationship between storage capacity and the maximum with delay constrainthave been studied respectively.According to the results,our researches provide directinsightinto the routing and transport protocoldesign under the DTN architecture to achieve a good transmission performance.

As it is a preliminary exploration on the issue of the maximum space network throughput,data transmission is simpli fi ed.And the value calculated may be a loose upper bound.Nevertheless,the proposed methodology presents a concrete method to achieve the optimal network throughputoverspace networks.

[1]C.Carlo,H.Cruickshank,S.Farrell,et al.Delay and disruption tolerant networking(DTN)an alternative solution for future satellite networking applications.Proceedings of the IEEE,2011,11(99):1980-1997.

[2]R.Beuran,S.Miwa,Y.Shinoda.Network emulation testbed for DTN applications and protocols.Proc.ofthe IEEE Conference on Computer Communications Workshops,2013:151-156.

[3]R.H.Wang,B.Modi,Q.Y.Zhang,et al.Use of a hybrid of DTN convergence layer adapters(CLAs)in interplanetary internet.Proc.ofthe IEEE InternationalConference on Communications,2012:3296-3300.

[4]C.Carlo,R.Firrincieli.Application of contactgraph routing to LEO satellite DTN communications.Proc.of the IEEE InternationalConference on Communications,2012:3301-3305.

[5]R.Diana,E.Lochin,L.Franck,etal.A DTN routing scheme for quasi-deterministic networks with application to LEO satellites topology.Proc.of the IEEE Vehicular Technology Conference,2012:1-5.

[6]K.Wang,H.Guo,L.Shu,et al.An improved congestion controlalgorithm based on social awareness in delay tolerantnetworks.Proc.of the IEEE International Conference on Communications,2014:1773-1777.

[7]J.A.Fraire,P.A.Ferreyra.Assessing DTN architecture reliability fordistributed satellite constellations preliminary results from a case study.Proc.ofthe IEEE BiennialCongress ofArgentina,2014:564-569.

[8]N.Uchida,N.Kawamura,K.Takahata,et al.Proposal of dynamic FEC controls with population estimation methods for delay tolerantnetworks.Proc.of the 28th International Conference on Advanced Information Networking and Applications Workshops,2014:633-638.

[9]A.Schrijver.On the history of the transportation and maximum fl ow problems.Mathematical Programming,2002, 91(3):437-445.

[10]L.F.Zhao,X.W.Meng.An improved algorithm for solving maximum fl ow problem.Proc.of the 8th International Con-ference on NaturalComputation,2012:1016-1018.

[11]C.M.Jiang,Y.Shi,Y.T.Hou,etal.Throughputmaximization for multi-hop wireless networks with network-wide energy constraint.IEEE Trans.on Wireless Communications,2013, 12(3):1255-1267.

[12]P.H.J.Nardelli,M.Kountouris,P.Cardieri,et al.Throughput optimization in wireless networks under stability and packet loss constraints.IEEE Trans.on Mobile Computing,2014, 13(8):1883-1895.

[13]J.Abouei,A.Bayesteh,A.K.Khandani.On the delaythroughput tradeoff in distributed wireless networks.IEEE Trans.on Information Theory,2012,58(4):2159-2.

[14]L.Ying,S.Shakkottai.On throughput optimality with delayed network-state information.Proc.of the Information Theory and Applications Workshop,2008:339-344.

[15]M.Chitre,M.Motani,S.Shahabudeen.Throughput of networks with large propagation delays.IEEE Journal ofOceanic Engineering,2012,37(4):645-658.

[16]D.Z.Zeng,S.Guo,M.Guizani,et al.All-to-all throughput maximization in wireless relay networks with multiple packet reception.Proc.of the IEEE Global Communications Conference,2012:5675-5680.

[17]T.-H.Kim,H.Choi,H.-S.Park.Centrality-based network coding node selection mechanism forimproving network throughput.Proc.of the 16th International Conference on Advanced Communication Technology,2014:864-867.

[18]S.Chieochan,E.Hossain.Channel assignment for throughputoptimization in multichannelmultiradio wireless mesh networks using network coding.IEEE Trans.on Mobile Computing,2013,12(1):118-135.

[19]X.C.Yang,J.Li,C.L.Xie,et al.Throughput gain of random wireless networks with physical-layer network coding. Tsinghua Science and Technology,2012,17(2):161-171.

[20]Z.L.Ning,Q.Y.Song,L.Guo,et al.Throughput improvementby network coding and spatialreuse in wireless mesh networks.Proc.ofthe IEEE Globecom Workshops,2013:4572-4577.

[21]K.K.Teav,Z.D.Zhou,B.Vucetic.Throughput optimization for MIMOY channels with physicalnetwork coding and adaptive nodulation.Proc.of the 75th IEEE Vehicular Technology Conference,2012:1-5.

[22]C.Y.Chang,M.H.Li,W.C.Huang,etal.An optimalscheduling algorithm for maximizing throughput in WiMAX mesh networks.IEEE Systems Journal,2013:1-14.

[23]E.Leonardi,M.Mellia,M.A.Marsan,et al.Joint optimalscheduling and routing for maximum network throughput. Proc.of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies,2005,2:819-830.

[24]Q.Xie,T.L.Huang.A topology controlalgorithm forthroughputoptimization forwirelessmesh networks.Proc.ofthe IEEE Conference Anthology,2013:1-4.

[25]J.Monteiro,A.Goldman,A.Ferreira.Performance evaluation of dynamic networks using an evolving graph combinatorial model.IEEE WiMob,2006:173-180.

[26]A.Anagnostopoulos,R.Kumar,M.Mahdian,et al.Algorithms on evolving graphs.Proc.of the 3rd ACM Innovations in TheoreticalComputer Science Conference,2012:149-160.

[27]B.B.Xuan,A.Ferreira,A.Jarry.Computing shortest,fastest, and foremost journeys in dynamic networks.International Journal of Foundations of Computer Science,2003,14(2): 267-285.

[28]A.Ferreira.Building a reference combinatorial model for dynamic networks:initialresults in evolving graphs.Paris:Inria, 2003.

[29]B.B.Xuan,A.Ferreira,A.Jarry.Evolving graphs and least cost journeys in dynamic networks.Proc.of WiOpt-Modeling and Optimization in Mobile,Ad-Hoc,and Wireless Networks, 2003:141-150.

[30]M.S.Huang,S.Y.Chen,Y.Zhu,etal.Topology control for time-evolving and predictable delay-tolerant networks.IEEE Trans.on Computers,2013,62(11):2308-2321.

[31]C.Jorge,K.Joud,G.Nasir.Routing in MPLS networks with probabilistic failures.Proc.of the IEEE ICC Communication QoS,Reliability and Modeling Symposium,2013:2534-2539.

Biographies

Yanling Xing was born in 1978.She received her B.S.and M.S.degrees from the Department of Communication Engineering from PLA University of Science and Technology,Nanjing,China, in 2001 and 2004 respectively.She is currently a Ph.D.candidate of the Department of Electronic Engineering,Tsinghua University,Beijing,China. Her current research interests are space communication protocols and space network theory.

E-mail:xu94xu@163.com

Ning Ge was born in 1971.He received his B.S. and Ph.D.degrees from the Department of Electronic Engineering,Tsinghua University,Beijing, China,in 1993 and 1997,respectively.He is currently a professorin Space Center,Tsinghua University,Beijing,China.His research interests include short range wireless communication,communication ASIC design,wireless communication,and information theory.

E-mail:gening@tsinghua.edu.cn

Youzheng Wang was born in 1970.He received his B.S.,M.S.and Ph.D.degrees in electronic engineering from Tsinghua University,Beijing,China, in 1992,1997 and 2009,respectively.Since 1997, he has been in the Department of Electronic Engineering,Tsinghua University,where he has been on the research staff and then promoted to an associate professor in 2004.He is currently an associate professor in the Department of Aeronautics and Astronautics Engineering, Tsinghua University.His research interests are resource allocation,cooperative communication,network coding,satellite communication and ad-hoc networks.

E-mail:yzhwang@tsinghua.edu.cn

10.1109/JSEE.2015.00026

Manuscriptreceived January 13,2014.

*Corresponding author.

This work was supported by the National Natural Sciences Foundation of China(61132002;61321061;61231011;61201183),the National Basic Research Program of China(2014CB340206)and the Tsinghua University Initiative Scienti fi c Research Program(2011Z05117).