空间延迟/中断容忍网络的接触图路由研究综述∗

徐 双,王兴伟,黄 敏,张琳琳

1(东北大学 计算机科学与工程学院,辽宁 沈阳 110169)

2(东北大学 信息科学与工程学院,辽宁 沈阳 110819)

空间通信和组网技术的发展,为空间探索技术的发展开启了新纪元[1].早期空间通信大多采用地球同步轨道(geo-synchronous orbit)卫星,利用弯管通信技术实现数据中继转发和广播,难以完成连续的信息捕捉和传输[2].星上计算和处理能力的提高以及星际链路通信技术的发展,为空间通信和组网提供了重要的技术支撑[3].卫星通信具有覆盖范围广、通信距离远、传输容量大、对地面环境依赖性低等特点[4],在防灾救灾、紧急救援、全球导航定位、空间遥测等任务中发挥着重要作用[5].然而,卫星通信系统主要需要应对如下困难:(1)远距离传输造成的长传输延迟;(2)通信链路易受干扰造成的高误码率;(3)复杂的空间环境以及节点移动造成的链路中断;(4)特定于供应商的网络基础设施造成的网络协议标准难以统一,特别是由此导致的网络异构性;(5)星上设备存储和处理能力有限,特别是维修困难[6].随着空间通信需求的不断增长,实现空间设备间类似于Internet的通信变得越来越重要[7].

延迟/中断容忍网络(delay/disruption tolerant network,简称 DTN)最初是由美国喷气推进实验室(Jet Propulsion Laboratory,简称JPL)为开发行星际互联网(interplanetary Internet,简称IPN)而提出的一种网络体系架构[8],后被广泛应用于军事作战网络、稀疏传感网络等地面网络.DTN也是构建卫星网络的可选方案[9],尤其是满足低地球轨道星座系统间歇性连接的需要[10].DTN在传输层与应用层之间引入叠加层(overlay)[11],采用消息的“存储-携带-转发(store-carry-forward)”机制解决网络中的间歇性连接、长传输延迟、高误码率等问题,适用于通信受延迟、带宽、误码等严重影响的空间网络[9].束协议(bundle protocol,简称BP)作为DTN协议的重要组成部分,提供了保管传输(custody transfer)、主动和被动式束分片(proactive and reactive bundle fragmentation)、滞后绑定(late binding)这些重要功能,为DTN网络的实施提供了可能性[12].在BP中,采用束作为传输数据的基本单元,并通过汇聚层适配器实现与TCP、UDP、LTP(licklider transmission protocol)、蓝牙等不同协议之间的匹配,从而使DTN能够解决异构网络互联中存在的问题.

路由是 DTN必备的基本功能,旨在提高束的交付率并降低交付延迟[13].通常,路由是指路径上的每个节点选择最优相邻节点转发数据的复杂过程.Internet网络主机在分发数据前,根据当前网络拓扑和节点间连接信息计算最优的包转发路径,而DTN所采用的网络状态信息中还需包含接触传输速率、节点存储容量等.由于网络状态信息可能随时间推移而变化,网络转发节点需要根据当前可用的网络状态信息判断是否需要重新计算转发路径或仍沿先前路径继续转发数据.Internet网络状态信息变化可被迅速地传播,因此每个节点掌握的当前网络状态几乎都是准确、一致的.而DTN连接具有间歇性,且信号传播时延长,所以网络状态信息的一致性维护困难,网络状态信息具有滞后性.此外,数据包在转发到相邻节点前,可能需要长时间存储在当前节点.

在机会性DTN(opportunistic DTN)中,节点具有移动性,节点间的接触具有随机性[14].因此,基于洪泛和概率的路由算法被广泛应用在机会性DTN中[15-17].空间DTN节点彼此之间不断相对运动,节点位置不断变化,但节点运动轨迹的数学模型可预先建立,从而准确地计算出节点间的接触机会[18],这类网络被称为确定性 DTN(deterministic DTN)[13].关于确定性DTN的路由分析研究工作可追溯到2003年,文献[19]提出了采用时间演化图表示网络拓扑变化来研究最小成本路径.2004年,文献[20]根据节点运动的可预知性,提出了一个时空路由(space-time routing)框架,为每个节点构建由每个时隙间隔内的下一跳组成的时空路由表,给出了基于时空图模型的路由算法.然而,上述两种静态路由算法依赖于地面上预计算的完整路径以及分配这些路径到网络节点的及时性,缺乏对变化业务流和拓扑的响应.为解决上述问题,2008年,Burleigh提出了分布式的接触图路由(contact graph routing,简称CGR)算法.该算法利用网络接触的可预知性,采用启发式算法动态计算出多条路径,为空间DTN提供了一种有效的路由方案[21].文献[22,23]评估了CGR、Epidemic和Prophet在空间DTN中的性能并指出,在拓扑信息可预知的空间网络中,CGR具有较小的延迟和缓存消耗.此外,CGR已被多次成功地应用于 DTN的空间实测实验[24].目前,CGR白皮书已被提交到国际空间数据系统咨询委员会(Consultative Committee for Space Data Systems,简称 CCSDS)进行标准化,并重新标记为“调度感知束路由(schedule-aware bundle routing,简称 SABR)”[25].

本文第1节描述CGR的基本原理、相关术语和算法过程.第2节分析和总结CGR存在的问题和相应的改进方法.第3节介绍CGR的工程应用.第4节对比评估CGR算法在多层卫星网络中的性能.第5节总结全文,对未来的研究方向进行展望.

1 CGR

1.1 基本原理

CGR是一种分布式路径计算方法,路径上的每个节点一旦接收到束,则重新计算到达该束的目的节点的最佳路径,从而确定当前节点的下一跳节点[26].CGR假定:(1)网络具有拓扑预计算能力;(2)网络中的每个节点能够及时而准确地获知全局网络接触信息和本地队列占用情况;(3)网络拓扑的变化频率低于网络节点配置信息的同步频率[27];(4)不可预知的拓扑变化发生频率低,节点失效彼此独立发生[28].可预知的网络拓扑变化作为节点配置信息,可以提前分发到网络中的每个节点,而对于不可预知的拓扑变化,CGR依赖于网络管理功能来更新被影响节点的配置.

接触(contact)是指两个 DTN节点之间建立通信链路的机会,由拓扑间隔内的所有可行接触组成的时序列表称为接触计划(contact plan,简称CP)[29].接触计划采用接触消息(contact message)和范围消息(range message)两种类型的接触计划消息(contact plan message)表示[21,30].其中,接触消息包含接触的起始时刻、结束时刻、发送节点、接收节点和数据传输速率(B/s);范围消息包含接触的起始时刻、结束时刻、发送节点、接收节点、发送节点与接收节点间的距离(<1光秒).根据接触计划,每个节点可以在本地构建以任意其他节点为目的节点的有向无环图,即接触图(contact graph),接触图的顶点对应于接触,边对应于束在节点上的存储.接触图可用以下两个链表表示:由所有以目的节点为接收节点的接触消息派生出来的xmit对象链表,该链表封装了接触的起始时刻、结束时刻、发送节点和数据传输速率,链表中的对象根据接触的结束时刻排序;由范围消息得出的origin对象链表,该链表封装了发送节点以及发送节点与目的节点间的当前距离.

图1是一个由4个卫星节点组成的空间DTN网络,节点A发送数据到节点D;表1是该网络对应的接触计划,其中的每个表项描述两节点之间接触的起止时刻和数据传输速率[31].以表1中的接触计划为例,构建从节点A到节点D的接触图,结果如图2所示[26].图中添加了两个概念顶点(notional vertice),分别为图中的根顶点和终端顶点.前者表示从节点A到A的接触,而后者表示从节点D到D的接触,图中其他顶点均为表1中有助于节点A发送数据到节点D的接触.在图2中进行路径搜索,构建从发送节点A到目的节点D的路由列表(route list)[32].每次搜索都找出从根顶点开始到终端顶点结束的最低成本路径,并将搜索到的路径添加到节点的路由列表中.在进行下一次搜索之前,从接触图中删除本次搜索到的路径的初始接触.重复以上过程,直到搜索不到路径为止.从图2中可以看出,从A到D共有3条可用路径.

Fig.1 DTN network topology图1 DTN网络拓扑

Table 1 Contact plan list表1 接触计划列表

Fig.2 Contact graph from nodeAtoD图2 从A到D的接触图

基于接触图的路由工作流程由接触计划生成、接触计划分发和路由计算这3个阶段构成,如图3所示[26].

Fig.3 Contact plan generation,distribution and utilization图3 接触计划的生成、分发和利用

由于接触计划依赖于特定的网络和通信平台,因此将接触计划的生成过程从路由应用中解耦出来.在初始阶段,空间任务操控中心根据网络节点的通信系统属性(如传输功率、调制机制、误比特率、天线辐射方向等)和节点的轨道动力学特性(如位置、姿态等)确定接触的可行性,构造接触计划[33];然后,由地面站将接触计划分发到网络中的每个节点;最后,节点调用CGR,根据已知的接触计划生成到达目的节点的有效路径.

1.2 相关术语

本节给出CGR相关术语的定义和计算公式,并在表2中列出本文中使用的变量符号及含义.

Table 2 Variable notations and definition表2 变量符号及含义

(1)合格路径(well-formed routes):构成从源节点到目的节点的端到端路径的接触序列,该序列的第1个接触为源节点与其相邻节点间的接触,后续接触是前一个接触的接收节点与其相邻节点间的接触,而最后一个接触是以接收节点为目的节点的接触.该路径中不存在环路,即不存在两个接触的发送节点或接收节点相同的情况.

(2)失效时刻(expiration time):束的创建时刻与其生存时间(time-to-live)之和,即.

(3)单向光行时边界(one-way light time(OWLT)margin):OWLT是光在两节点间传输所需的时间,指代距离.OWLT边界是束在任意两节点间传播时,节点间OWLT变化的最大增量.假设网络中任意两节点间距离变化的最大速率约为 67km/s,则初始距离为K光秒的两节点间每秒增加的最大距离为67km.因此,数据从发送节点传输到接收节点所需的传播时间不会超过(K+Q)s,其中,Q=(67×K)/30000.

(4)最后时刻(last moment):接触发送束的最晚时刻,即保证束在截止时刻Tdeadline之前到达接收节点的最晚发送时刻.如果接触的起始时刻在最后时刻之后,则该接触的接收节点无法在之前接收到束.

(5)容量(capacity):接触的数据传输速率与其持续时间的乘积,即

(6)估计容量消耗(estimated capacity consumption):假设汇聚层采用UDP/IP协议,则每个帧的开销为100字节.每帧中可封装的束的字节数等于帧的大小减去每帧的开销.例如,Internet的最大传输单元大小为1 500字节,则每帧中束的最大字节数为1400=(1500-100).传输给定大小的束所需的帧数等于束的大小除以每帧中束的最大字节数的商向上取整.束的总开销为每个帧的开销乘以传输该束所需的帧数.束的估计容量消耗为束的大小与总开销之和,即

(7)剩余容量(residual capacity):本地节点与邻居节点间给定接触的剩余容量是两节点间不晚于给定接触调度的所有接触的容量之和减去优先级不低于发送束的所有待传输束的估计容量消耗之和,即

(8)可用机会(plausible opportunity):剩余容量不小于发送束的估计容量消耗的接触.

(9)可用路径(plausible route):由可用传输机会组成的合格路径,且路径上每个接触开始传输束的时刻先于最后时刻.最后一个接触的截止时刻为束的失效时刻,而其余每个接触的截止时刻为每个接触的结束时刻.

(10)收回时刻(forfeit time):可用路径上所有接触的最早结束时刻.

(11)网络距离(network distance):可用路径的网络距离是指束沿着该路径从源节点转发到目的节点所经过的中间节点数,即跳数.

(12)被排除的相邻节点(excluded neighbor):本地节点的相邻节点中拒绝托管发送到给定目的节点的束的相邻节点.

(13)关键束(critical bundles):必须且应尽快投递到目的节点的束.关键束将被插入到所有可用路径对应的输出队列中,而非关键束仅被插入到所有可用路径中收回时刻最早的路径所对应的输出队列中.

(14)转发延迟(forwarding latency):节点接收、排队以及发送束所用的时间,使用束大小的2倍除以接触的数据发送速率估算,即.

1.3 算法过程

CGR利用可预知的接触计划消息获取网络拓扑,不需要预测或发现过程[34].CGR的处理过程如图4所示.首先,节点根据接收到的接触消息和范围消息生成接触图;之后,执行接触检查过程(contact review procedure,简称CRP),根据生成的接触图计算出可用来转发束的相邻节点列表;最后,通过转发决策过程(forwarding decision procedure,简称FDP)选择下一跳节点.

Fig.4 Three processing steps of CGR algorithm图4 CGR算法的3个处理步骤

接触图构建完成后,节点通过CGR-CRP过程和CGR-FDP过程实现路径计算与束转发的流程如下.

输入:B,CP.

输出:将B插入到相应的输出队列.

算法的第2行～第39行是节点根据接触计划执行路径计算的过程.

· 第2行将每次迭代的目的节点加入到被排除的相邻节点集合中,以防止路由环路的产生.

· 第4行～第6行计算通过每个接触发送束的最晚时刻:如果该时刻早于当前时刻或接触的起始时刻,则跳过此接触.

· 第8行～第11行表示当前目的节点为束的目的节点时,更新路径收回时间;当接触的发送节点为本地节点时,计算束的估计容量消耗和接触剩余容量.

· 第14行～第 23行是当接触剩余容量大于束的估计容量消耗时,判断当前目的节点与本地节点的相邻节点间的从属关系以及路径收回时间与束的投递时间的大小关系,决定是否更新束的交付时间、路径距离和路径列表.

· 第28行～第 34行是当接触的发送节点既不是本地节点也不是排除节点时,更新路径收回时刻、当前目的节点、路径网络距离等,并递归调用CGR-CRP过程.

算法的第40行～第50行是根据束的重要性将其插入到输出队列的过程,其中,第41行、第42行表示束是关键束时,将其复制并插入到本地节点的所有可用相邻节点对应的输出队列中;第 44行、第 45行表示束是普通束时,从本地节点的所有可用相邻节点中选出最早收回的相邻节点,将束插入到该节点所对应的输出队列中.

2 CGR的改进

自2008年CGR首次提出以来,很多研究都致力于CGR的功能完善和应用.图5是CGR的发展简史[26].2009年,IETF(Internet Engineering Task Force)发布了CGR文档[35];2010年,CGR文档被更新为IETF互联网草案[30];2011年,Segui等人[24]提出了增强CGR(enhanced CGR,简称ECGR),把最早到达时刻(earliest-arrival-time)作为路径选择度量值,并使用标准的 Dijkstra算法选择路径;2012年,Birrane等人提出了扩展块 CGR(CGR-extension block,简称 CGR-EB),以增加数据包报头开销为代价来降低中间节点的计算开销[28];2014年,Fraire等人提出了缓存CGR(cache-CGR,简称 C-CGR),以最大程度地减少CGR的执行次数[36];同年,Bezirgiannidis等人提出了最早传输机会CGR(CGR-earliest transmission opportunity,简称CGR-ETO),引入节点队列信息,以改善CGR应对网络状态变化的能力[37],并在文献[38]中提出了超额预订管理(overbooking management)机制,以提高低优先级束的交付率.

Fig.5 Brief history of CGR图5 CGR简史

关于拥塞控制(congestion control),文献[39-41]相继提出了预测容量消耗(predictive capacity consumption,简称PCC)[39]、基于本地信息的拥塞控制[40]、路径感知CGR(path-aware CGR,简称PA-CGR)和多图CGR(multigraph CGR,简称MG-CGR)[41]等多种改进方法.2016年,Burleigh等人为了实现确定性DTN和机会性DTN路由机制的统一,提出了机会CGR(opportunistic CGR,简称OCGR)[31].2017年,时文丰等人在CGR中引入了接触异常处理机制,提高了CGR应对接触失效的能力[42].

2.1 算法收敛性

保证路由算法的收敛性需要满足两个特性:不存在路由环路、不存在持续震荡.在路径选择中采用单调递增(或递减)的度量指标,可以保证路由的收敛性[24].CGR采用最早收回时刻作为路径选择度量指标,以最大程度地减少传输机会的浪费.然而,最早收回时刻不是一个单调递增(或递减)的度量指标,不能保证路径选择过程中始终不会出现路由环路和震荡.为此,文献[24]提出了ECGR算法,用最早到达时刻代替最早收回时刻,并使用标准的 Dijkstra算法进行路径选择.最早到达时刻满足全局单调递减的特性,因而可以避免路由环路和持续震荡的产生.此外,Dijkstra算法计算开销小,且可用于构建多播树.上述功能改善已经成为 CGR核心功能的一部分,在JPL开发的星际覆盖网络(interplanetary overlay network,简称ION)仿真平台中得以实现[43].

2.2 计算开销

CGR路径上的每个中间节点重新计算束的最优转发路径,以应对网络状态的变化.重计算在给算法带来灵活性的同时,也增加了算法的计算开销.为了解决此问题,文献[28,34]提出了 CGR-EB,将计算出的路径信息和用于路径计算的接触图信息编码到束的扩展块中,传输到下游节点.下游节点进行如下路径有效性验证.

首先,根据当前节点的接触计划检查下一跳接触的稳定性.

· 如果下一跳接触不稳定,则重新执行CGR来计算新的路径,并根据新路径更新CGR的扩展块.

· 如果接触是稳定的,则验证接触传输速率和容量是否在容错范围内:

➢ 如果误差超出了容错范围,则重新执行CGR来计算新的路径,并根据新路径更新CGR的扩展块;

➢ 否则,可选择进行一跳扫描来查找是否存在到达指定的下一跳节点的更快路径,如果存在,则采用较快的接触转发束.

继续重复上述过程,检测后续几个接触的稳定性.

CGR-EB仅当接触稳定性验证失效时才重新执行CGR,不需要在每个中间节点都执行复杂的CGR路由计算.与执行CGR相比,验证路径有效性的计算开销小,因此,CGR-EB更加适合节点资源受限的网络环境.此外,当编码路径有效时,可使用多种成本函数重新搜索潜在的较优路径,既不必担心产生路由环路,又避免了预计算路径为当前次优路径的情况.最后,利用束携带并传播路径信息可以为拥塞预测和拓扑同步提供可用的信息.受CGR-EB算法的启发,文献[44]提出了一种基于 CGR的源路由算法,由源节点根据已知的接触计划和节点缓冲区占用率计算束的转发路径,并将所得路径编码在包头中供中间节点使用.该方法以传输成本为代价,降低了中间节点的计算开销.

虽然CGR-EB算法和基于CGR的源路由算法采用路径编码的方式减少了调用CGR的次数,但同时也增加了每个束的报头开销.文献[36]提出的 C-CGR在减少 CGR执行次数的同时,保留了本地拥塞避免的特性.C-CGR将每个目的节点对应的当前节点的下一跳相邻节点记录到本地缓存区中.当有束到达时,本地节点先查找缓存区中是否存在与此束的目的节点对应的下一跳相邻节点.

· 如果不存在,则调用CGR为此束计算可用的下一跳相邻节点,并将计算出的下一跳节点记录到本地缓存区中.

· 如果查找到了对应的下一跳相邻节点,则判断相应接触的容量和结束时刻是否有效:如果接触失效,则调用CGR计算新的下一跳节点,并更新本地缓存区中目的节点对应的下一跳相邻节点信息;如果接触可用,则仅需更新接触的剩余容量信息.

在最坏情况下,C-CGR的计算开销与CGR相同;在分片密集型DTN中,C-CGR的计算开销明显低于CGR.

2.3 预测准确性

虽然 CGR、ECGR、CGR-EB和C-CGR均采用动态转发决策策略,但它们可能使用的是已经过时或不能反映当前网络状态的接触信息.这是因为空间网络接触调度虽然具有规律性,但仍然存在由不利的天气条件或概率性动态参数(如排队延迟)等扰乱预定网络接触调度的情况,因此需要改进路由算法以应对网络接触调度规律变化等问题.文献[37]提出了 CGR-ETO算法,引入最早传输机会(由排队延迟和链路中断确定)作为路由计算的度量指标,并使用接触计划更新协议(contact plan update protocol,简称CPUP)传播网络特征和参数变化信息,从而提高了延迟预测的准确度.然而,CGR-ETO仅考虑本地节点的排队延迟,无法应对所选路径下游节点以及下游链路的性能瓶颈.文献[45]提出了基于统计预测的多跳节点排队延迟预测方法,提高了投递时间预测的准确性.但此方法依赖于节点间信息的定期交互,增加了额外的网络信息交互开销.而文献[46]提出了增强 CGRETO(enhanced CGR-ETO),既将所考虑的排队延迟范围由本地节点扩展到路径上的所有节点,又避免了额外的信息交互开销.增强CGR-ETO将ETO的值作为参数值编码到节点接触信息中,本地节点根据获取的接触信息计算路径上所有节点的队列长度,而不使用任何类似于 CPUP的传播机制.该方法在提高投递时间预测准确性的同时,避免了节点间状态信息交互的昂贵代价.

2.4 超额预订管理

由于接触持续时间和数据传输速率有限,因此接触容量有限.虽然CGR在转发束之前检查接触剩余容量的可用性,但在剩余容量的计算中,只考虑了队列中优先级不低于转发束的束所需消耗的容量,因此在转发较高优先级的束时,CGR通过忽略低优先级的束来保证高优先级束的转发.如果接触已经被低优先级的束完全预订了,则在转发高优先级的束时,低优先级的束将错过其接触,造成接触超额认购(contact oversubscription)[47].CGR采用后验方式处理接触超额认购,即一旦已经错过接触的束的有效时间到期(一般为接触的结束时刻),则重新转发这些束.这种后验方法虽然健壮,但效率不高.文献[38]提出了一种先验方法,即超额预订管理,改善 CGR性能.在超额预定管理中,用总剩余容量评估接触可用性,计算总剩余容量时,不区分束的优先级而综合考虑队列中所有束所需消耗的容量.当出现超额认购时,首先转发引发超额认购的高优先级的束,然后立即转发错过接触的低优先级束.此外,文献[38]指出,最早传输机会与超额预定管理能够实现优势互补,极大地改善了CGR路由决策的性能.这两项改进均已被CGR的官方版所采纳,并在ION中得以实现[43].

2.5 拥塞控制

拥塞问题可以定义为试图发送比接触或节点缓冲区可承载数据量要多的数据,因此,网络中的接触容量限制和过多的业务量都可能会引起拥塞.CGR通过维护本地节点接触的剩余容量信息来避免使用本地拥塞链路转发数据的情况.这种仅考虑本地接触剩余容量而忽略后续路径接触容量及中间节点存储能力的方式可能会引起不必要的业务量反弹效应[41],因此,文献[39]提出了PCC算法.PCC既可以作为DTN流量控制方案,也可以作为DTN拓扑同步方法.它将节点生成的源与目的节点间的可行路径及路径上每个接触的剩余容量信息封装到数据包头部中,中间节点根据接收的数据包头部信息和异步反馈消息完成本地接触图更新、容量预测和路由决策.PCC虽然通过利用相邻节点间的信息交互改善了本地节点的知识处理能力,但所需的包头部开销非常大.

文献[41]提出了PA-CGR和MG-CGR两种拥塞避免方法,并提出了基于可预知的接触计划和业务量的线性规划模型,作为分析和对比DTN拥塞感知机制的基准.PA-CGR算法利用接触计划中已包含的接触容量信息,推测路径容量(路径容量由路径上剩余容量最小的接触决定),并根据路径容量和本地接触的剩余容量进行路由决策.PA-CGR提高了接触计划中网络拓扑信息的利用率,扩展了CGR的拥塞避免特性.与PCC相比,包头部开销减小了,但包投递率降低了.MG-CGR利用确定性DTN中接触计划和业务量的可预知性以及线性规划模型构建拥塞避免路由架构.MG-CGR与CGR、PCC和PA-CGR最大的区别在于,MG-CGR利用线性规划模型为每个节点定制特定的接触计划,然后,每个节点根据特定的接触计划采用CGR-EB进行路由计算和转发.对于业务量可预知的确定性DTN,MG-CGR性能逼近线性规划模型的上限,而对于业务量随机的情况,PCC的性能最好.

此外,针对地球观测卫星网络这类数据生成和资源预留均由任务操控制中心管理的空间 DTN,文献[48]提出了全局路径感知CGR(global path-aware CGR,简称GPA-CGR),即在接触图生成阶段,基于可预知的拓扑信息和业务量全局视图采用演化算法生成无拥塞的接触计划,并分发给网络中的每个节点.每个节点基于接收到的接触计划,应用CGR-EB计算数据包转发路径.鉴于GPA-CGR依赖于可预测的业务量生成接触计划,处理不可预测业务、拓扑变化以及业务量预测误差的能力有限,文献[48]在GPA-CGR中引入了容量计算误差余量,并分发次优备份接触计划到网络中的所有节点以防网络突发事件的发生.

除了上述工作以外,文献[40]改进了CGR-ETO的转发决策机制,提出了基于本地信息的拥塞控制机制.该机制充分利用了 CGR的多路径计算能力,将次优路径作为备用路径,通过队列出队/入队速率和束的最早传输时刻预测网络状态.如果将束沿着最优路径转发会造成传输队列拥塞,则利用备用路径转发该束来避免拥塞发生.

2.6 机会性扩展

目前,DTN路由方案呈现二分性,即确定性DTN路由方案和随机性DTN路由方案彼此相互独立.为了给出一个适合所有DTN环境的统一路由方案,文献[31]提出了基于CGR的OCGR算法.与CGR相比,OCGR算法不仅扩展了接触计划,而且在转发决策过程中引入了束交付置信度.在 OCGR中,接触计划由预定接触(scheduled contact)、发现接触(discovered contact)和预测接触(predicted contact)组成.预定接触通过接触计划调度得出,发现接触由节点实时发现,预测接触则依据发现接触的历史信息进行预测.预定接触和发现接触的置信度为 1,而预测接触的置信度由发现接触日志信息推导得出.OCGR定义路径的置信度为路径中所有接触的置信度的乘积,并根据路径的置信度确定束的交付置信度.OCGR的研究仍处于起步阶段,其性能尚未超过其他机会路由算法,但一般认为,此改进是可行的[31].

2.7 异常处理

空间DTN网络所处网络环境复杂,接触易受电磁波干扰、邻频干扰等影响而意外中断,网络节点可能遭遇攻击、能量耗尽、天线故障等而失效,造成网络拓扑意外变化.CGR基于准确的接触计划进行路由决策,缺少应对节点或链路异常的能力.文献[42]在CGR中引入了应对接触意外中断的策略,提高了CGR处理接触异常的能力.该机制首先根据接触上连续发生束重传的次数判断链路是否发生意外中断;一旦检测到接触中断,则将接触失效信息通告给所有节点,与此同时,激活接触失效探测机制发送探测束检测接触是否恢复;如果接触恢复,则将接触恢复消息下发给所有节点;节点接收到接触失效或恢复消息后更新本地接触图,重新计算路径.

3 CGR工程应用

已经有多种DTN开源仿真平台,包括DTN2、ION、Postellation、IBR-DTN、JDTN和ONE等[49].其中,DTN2由加利福尼亚大学采用C和C++语言编程实现,主要包含的路由协议有静态路由、洪泛路由、延迟容忍链路状态路由(delay tolerant link state routing,简称DTLSR)和基于概率的Prophet路由等[50].ION是由JPL实验室针对空间网络开发的软件平台,采用C语言实现,支持Linux、Solaris、OS/X、FreeBSD、VxWorks、RTEMS等平台,路由采用CGR[51].Postellation是由Viagenie使用C语言开发的,支持IPv4和IPv6[52].IBR-DTN是由布伦瑞克工业大学基于C++语言开发的,支持Openwrt、Ubuntu、Android、MacOS等系统,其路由模块主要包括静态连接路由、基于发现的路由、传染路由、洪泛路由和Prophet路由[53].JDTN是由思科开发的基于Java语言实现的平台,支持Android等移动平台[54].ONE是由Keränen等人基于Java语言设计的机会DTN路由仿真平台,主要支持DirectDelivery、Epidemic、Maxprop、Prophet、Spary and Wait等路由协议[55].在上述仿真平台中,CGR主要在 ION中实现,而 ION多用于仿真由有限节点组成的小规模空间 DTN.为了补充 CGR的研究评估手段,Berlati等人已将CGR移植到ONE上,打破了基于小规模网络测试评估CGR性能的局面[56].

多项空间实验被相继展开,以验证DTN范型和CGR的有效性.根据实测实验开展的时间先后顺序,我们简要介绍以下4个实验,如图6所示.在2008年10月进行的为期27天的深度撞击网络(deep impact network,简称DINET)实验中,顺利接收到了来自火星的292张图片[57];2009年7月,美国国家航空航天局(National Aeronautics and Space Administration,简称NASA)在国际空间站(International Space Station,简称ISS)上开始DTN范式实验,并于2016年5月在ISS上正式运行[58];2010年11月,塞萨斯德谟克里特大学等多个研究单位共同开始了为期3年半的空间数据路由器(space-data router,简称 SDR)项目,验证了 CGR有助于空间科学数据的分发[59];2011年～2013年期间,日本宇宙航空研究开发机构(Japan aerospace exploration agency,简称JAXA)与NASA联合完成了DTN技术测试,证实了在航天器中使用DTN与CGR是可行的[60].

Fig.6 Conducted real test experiments图6 已开展的实测实验

3.1 深度撞击网络

DINET是为测试DTN协议(如BP、CGR等)实施的深空飞行验证实验[61].在该实验中,将ION软件上载到深度撞击飞行器中,同时,在地面多台计算机上安装 ION软件模拟地球、火星和火卫一(phobos),从而构建一个火星-地球通信的虚拟场景.深度撞击飞行器作为中继路由,实现火星与地球之间的数据传递.DINET的网络系统组成如图7所示[57].

· 7号节点表示深度撞击飞行器,是网络中唯一没有被放置在JPL实验室的节点.

· 节点2、节点4、节点8和节点16模拟地球表面的通信系统.

· 节点3、节点6和节点12模拟火星表面的通信系统.

· 节点5、节点10和节点20模拟火卫一表面的通信系统[7].

· 节点8、节点12和节点20模拟终端节点.其中,节点12和节点20生成图像文件,节点8接收和显示图像文件.

· 节点2、节点3和节点5分别模拟地球、火星和火卫一通信系统与深度撞击号之间的中间接口系统.

· 节点4、节点6、节点10模拟终端节点和地面系统间的路由器.

· 节点16表示实验中用于分析和检测实验数据的管理系统[62].

Fig.7 DINET system components图7 DINET的系统组成

该实验模拟了火星和火卫一表面探测节点将采集的图像通过深度撞击飞行器传回地面的过程.图中的每个带箭头的虚线表示DTN网络接触序列;中间接口系统与实验操作中心之间带箭头的实蓝线表示用于连接实验设备的局域网.图中节点6和节点10之间的链路为节点12和节点20之间的数据传输提供备用路径.经过近一个月的测试,CGR性能表现良好,实验中发现的漏洞也已经在高版本的ION中得以解决.

3.2 国际空间站

自2009年起,NASA在ISS上开展了多项DTN验证实验.2009年7月的第1个实验是通过数据中继卫星系统(data relay satellite system,简称 TDRSS)下载位于 ISS上的商业通用生物处理设备(commercial generic bioprocessing apparatus 5,简称CGBA-5)中的图像文件[63].图像文件从ISS传输到位于亨茨维尔的马歇尔航天中心,然后转发到位于科罗拉多大学波尔得分校的有效载荷操作控制中心.虽然此次部署的 CGBA拓扑复杂度并不足以充分发挥CGR的作用,但其成功部署,使ISS运营团队更加确信DTN将成为ISS通信技术的重要组成部分[64].2012年,NASA和欧洲航天局(European Space Agency,简称ESA)模拟了在轨飞行器上的宇航员远程控制行星表面探测器的场景[65].ISS上的指挥官Williams成功地借助DTN协议发送远程控制命令,远程“驾驶”位于欧洲太空操作中心的小型乐高(Lego)机器人[66].该实验证明了使用 DTN通信基础设施从在轨航天器向地面机器人发送命令以及接收从机器人发回的数据的可行性.

3.3 空间数据路由器

由于空间数据收集中心和学术研究机构与卫星间的可通信时间有限,而且空间数据收集中心与学术研究机构间缺乏高效的通信机制,因此空间数据分发面临庞大数据量、时效性和连续性的制约,常常造成空间数据未能被有效及时地利用[59].为此,欧盟委员会资助成立空间数据路由器项目,旨在建立一个基于 DTN的空间数据开发架构,从数据量、及时性和连续性方面改进空间数据的分发.该项目的构想如图8所示[67]:利用DTN叠加层和 CGR进行路由决策,一旦接收到空间任务数据,就直接转发给研究机构等感兴趣的终端用户.该项目评估了CGR在空间任务地面段的适用性,证实了CGR有助于空间数据的高效分发[60].

Fig.8 Space data dissemination based on SDR图8 基于SDR的空间数据分发

3.4 JAXA/NASA DTN测试

JAXA与NASA通过半真实半模拟的空间延迟/中断环境,测试了DTN技术的可行性以及CCSDS文件传输协议(CCSDS file delivery protocol,简称CFDP)、Bundle流服务(Bundle streaming service,简称BSS)和CGR的有效性.该测试分为 4个不同的测试阶段[68],见表3.第 1阶段主要是在开始正式测试之前验证网络连接性和DTN基本功能;第2阶段通过模拟飞行器的运行场景验证DTN功能;第3阶段在真实的数据中继实验卫星(data relay test satellite,简称DRTS)空间链路环境下验证DTN功能;第4阶段通过DRTS空间链路连接ISS上的DTN节点与JAXA航空中心的DTN节点来验证DTN的功能.为了证实在长距离延迟和中断环境中CGR的可行性,采用了一个典型的深空中继通信场景,如图9所示.该场景由 1个任务操作中心(mission operation center,简称MOC)、1个行星表面探测车(rover)、1个DRTS卫星、2个行星中继轨道卫星(ROP1和ROP2)和2个地面站(GT1和 GT2)组成[69].Rover采集生成的数据通过 DRTS、ROP1、ROP2、GT1和 GT2传输到 MOC.测试中将 ION部署在所有节点上,并利用 CGR动态查找最佳路由.为了更加真实地模拟实际通信环境中的链路延迟和中断,在测试中加入DRTS卫星和两个地面站之间的实际传播延迟和处理延迟以及通过延迟模拟器模拟的DRTS卫星与ROP1和ROP2之间3 600s的往返延迟.此外,通过开关射频链路,模拟由无线电干扰和雨衰引起的不可预测中断以及由航天器间不可视引起的可预测中断,并通过增加或减小射频电平大小,模拟实际降雨的衰减水平.测试结果显示,CGR能够实现传输路径的自动选择,成功地完成了图像文件的传输.

Table 3 JAXA/NASA DTN test items表3 JAXA/NASA DTN测试内容

Fig.9 JAXA DTN test topology图9 JAXA的DTN测试拓扑

4 性能评估

本文将CGR应用到由GEO/MEO/LEO组成的多层卫星网络中,从拓扑处理策略、路由跳数、路径延迟、故障处理和拥塞控制等5个方面对比分析了CGR与多层卫星路由算法(multi-layered satellite routing algorithm,简称MLSR)[70]的性能.MLSR根据GEO卫星和MEO卫星的覆盖范围将MEO卫星和LEO卫星分组,并根据分组关系变化划分时隙,GEO卫星和MEO卫星为组管理者,负责网络状态信息维护和路由表计算.鉴于采用ION仿真大规模多层卫星网络所需的硬件成本高,本文选用支持CGR的ONE平台作为多层卫星网络模拟器来对比评估两种路由算法性能.由于ONE中不包含卫星节点的运动模型,我们采用STK构建多层卫星网络拓扑结构,分析并生成其星间连接、距离、星下点轨迹等数据,导入到 ONE中进行仿真.ONE模拟器的主要参数设置见表4.

Table 4 Main parameter settings of ONE表4 ONE主要参数设置

所用的多层星座参数见表5,其中,GEO卫星轨道位于赤道上方,MEO卫星和LEO卫星则分别采用倾斜轨道和极轨道.仿真中,将36颗LEO卫星编号为0～35,12颗MEO卫星编号为36～47,3颗GEO卫星编号为48～50.

Table 5 Main parameters of satellite constellation表5 卫星星座主要参数

4.1 时隙分布

本文以24h为系统周期,分别按照CGR和MLSR的拓扑处理策略,将多层卫星网络的一个系统周期划分为多个时隙,结果如图10和图11所示.

Fig.10 MLSR slot distribution图10 MLSR时隙分布

Fig.11 CGR slot distribution图11 CGR时隙分布

图10为按照MLSR的拓扑处理策略划分时隙的结果,多层星座的一个系统周期被划分为4 972个时隙,时隙间隔大多分布在60s以内,最短时隙间隔长度为1s,最长为122s.图11为按照CGR的拓扑处理策略划分时隙的结果,其时隙总数为59个,均匀分布在7 100s以内,最短时隙间隔长度为439s,最长为7 038s.原因在于,MEO卫星与LEO卫星之间的组间关系频繁变化,造成MLSR一个系统周期内的时隙数量较大;而CGR采用星间接触的最大连通时间为单位划分时隙,时隙数量少.过短的时隙间隔导致路由算法可能不收敛,而过多数量的时隙导致需要大量空间来存储相关状态信息,给星上资源有限的卫星节点带来挑战.

4.2 跳数和延迟

假设地面站以编号为 0的LEO卫星为接入卫星,分别向编号为 1～50的卫星节点发送数据包,统计MLSR和CGR求得的路径延迟和路由跳数,结果如图12所示.可以看出,CGR求得的路径延迟比MLSR略小,但也存在部分路径延迟大于 MLSR的情况.原因在于,CGR可以充分利用长时隙间隔内的所有链路进行数据传输,MLSR只能通过短时隙间隔内始终连通的链路传输数据.但由于MLSR综合考虑了传播延迟、处理延迟和队列延迟,而 CGR只考虑了链路容量限制没有考虑排队延迟,因此当节点缓存队列中数据包较多时,CGR的路径延迟略大于MLSR.

Fig.12 Hops and delay图12 跳数和延迟

由图12可知,通过编号为0的LEO卫星向编号为1～35的LEO卫星发送数据时,MLSR的路由跳数分布在2跳;CGR的路由跳数分别以30%的概率分布在1跳、2跳和3跳,而以10%的概率分布在4跳.当通过编号为0的LEO卫星向编号为36～47的MEO卫星发送数据时,MLSR的路由跳数以40%的概率分布在3跳,而以60%的概率分布在1跳;CGR的路由跳数以30%的概率分布在2跳,而以70%的概率分布在1跳.当通过编号为0的LEO卫星向编号为48～50的GEO卫星发送数据时,MLSR的路由跳数分布在2跳、3跳、4跳,CGR的路由跳数为4跳.此外,对比路由跳数和延迟的关系可知,当路由跳数增大时,两种算法的路径延迟并未出现大幅度增大的情况,仅在向 GEO 卫星发送数据时,路径延迟大幅增大.原因在于,卫星网络的路径延迟主要取决于传播延迟,MLSR仅以路径延迟作为度量值指导选路过程,CGR同时考虑了路径延迟和跳数两个度量值,LEO卫星和GEO卫星间的传输距离远,传输延迟长,导致路径延迟大.

4.3 故障处理

卫星天线故障、能量耗尽或黑客攻击等会造成卫星节点意外失效,使得经过失效节点的路径无法继续使用.本文假设编号为10、27和38的3颗卫星同时在第15s发生意外失效,失效时长为175s,统计分析该失效时间段内所有预计经过失效节点传输的数据包的投递率,结果如图13所示.由图可知,随着卫星节点失效时间的增加,CGR的包投递率逐渐降低;而MLSR的包投递率仅在节点失效刚发生后的较短时间内出现下降,之后迅速恢复到较高水平.原因在于,CGR的路径计算所依据的是预知的接触计划,当节点失效发生后经过失效节点的最优路径仍被用来继续转发数据包,致使大量数据包聚积在失效节点附近的邻接节点中,引起数据包因生命周期失效或节点队列溢出而被丢失,降低了数据包投递率;而 MLSR具有节点失效处理能力,当节点失效发生后,其邻接节点会主动发起拓扑更新及路由重计算,因此数据包可以避开失效节点进行转发,减轻了节点失效对数据包传输的影响.

Fig.13 Packet delivery ratio under node failures图13 节点失效时的数据包投递率

4.4 拥塞控制

当网络业务请求数量增多时,CGR最多选用3条路径同时传输数据.分别统计当业务请求增多时采用CGR和MLSR传输业务请求的平均端到端延迟,结果如图14所示.

Fig.14 Influence of traffic requests on end-to-end delay图14 业务请求对端到端延迟的影响

由图可知,CGR和MLSR的平均端到端延迟均随业务请求数增加而增加,但CGR的平均端到端延迟增长幅度比MLSR要小.此外,在业务请求数量相同的情况下,CGR的平均端到端延迟明显低于MLSR.原因在于,业务请求的增多会导致节点排队延迟变长,使路径的端到端延迟变大.而 CGR具有多路径计算能力,在业务请求数量增加时,可以通过多条路径进行业务传输,减小了节点上的排队延迟,因此,CGR端到端延迟增长幅度比采用单路径传输的MLSR要小.

5 总结与展望

空间DTN具有长延迟、高误码率、拓扑频繁变化等特点,这些特点给空间DTN路由带来严峻的挑战.CGR为空间 DTN路由提供了一个切实可行的解决方案,受到了学术界的广泛关注.本文根据现有文献,给出了 CGR的基本原理、相关术语和算法过程,综述了针对CGR的缺陷提出的改进方案和已部署的验证CGR的空间飞行实验,并在多层卫星网络中对比评估了CGR的性能.在此基础上,本文提出以下有待进一步研究的问题.

(1)CGR-EB和C-CGR分别采用路径编码和路径缓存的方式降低了CGR的计算开销,但是前者增加了包头部开销,而后者以缓存空间为代价.如何将CGR-EB和C-CGR相结合以进一步改善系统整体性能,是一个值得研究的问题.

(2)改进CGR,使其适用于随机性DTN.虽然针对该问题,现有文献已提出了OCGR,但性能较差,算法设计有待进一步改进.

(3)CGR在有效性和带宽开销上与当前的 Internet路由算法相当,但计算复杂度高.尽管这对于小规模简单网络来说不是问题,但对于复杂的大规模网络则不可行.文献[18]首次测试了CGR在小、中、大这3种规模时变网络拓扑上的性能并指出,随着节点间接触数量和网络节点数目的增加,CGR计算开销显著增长,每个束的转发时间呈指数增长.因此,在CGR中引入划域的思想,对于降低CGR计算开销、完善其理论基础具有重要的意义.

(4)路由协议在提高服务质量(quality of service,简称QoS)中扮演着重要的角色,而空间DTN中的QoS路由与QoS保障机制等研究仍处于发展的早期阶段[71],因此,设计具有QoS保障能力的CGR是一个有待研究的问题.

(5)CGR采用接触列表描述所有时间间隔内节点间的通信机会,对于同一时间段内相同源和目的节点间的上下行链路分别使用不同的接触项描述[72].因此,当网络规模扩大或网络服务持续时间变长时,接触计划列表将变得非常大,降低了CGR算法效率.设计适用于大规模、长服务时间DTN的接触计划描述方法,对完善CGR理论基础具有重要的意义.

(6)空间网络配置更新困难、星上计算和处理能力有限、高异构性等特点,给空间组网技术的发展带来了严峻的挑战.将SDN(software defined networking)和NFV(network function virtualization)引入到空间网络来设计新的网络组网范式,是应对上述挑战的有效途径[73].引入 SDN,可以解耦控制平面和转发平面,使空间网络具有可编程性、灵活性和可重构的特点;引入NFV,能够简化网络管理,促进资源共享、聚合动态分配[74,75].同时,引入上述两种技术能够实现空间网络统一、灵活、细粒度的配置和管理,可以解决空间网络静态路由中因控制结构不灵活而无法满足负载均衡、故障管理和网络扩展的问题以及动态路由全网控制能力弱的问题,有效地权衡空间网络路由灵活性和可控性.