引用本文
方维维, 姚雪宁, 王文瑞, 安源, 李晶. 分布式星群网络中基于联系图的路由技术研究[J]. 北京交通大学学报, 2017,41(5): 17-23.
FANG Weiwei, YAO Xuening, WANG Wenrui, AN Yuan, LI Jing. Research on contact graph routing in distributed satellite swarm networks[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2017,41(5): 17-23.
Doi:10.11860/j.issn.1673-0291.2017.05.003  
Permissions
Copyright©2017, 北京交通大学学报编辑部
北京交通大学学报编辑部 所有
分布式星群网络中基于联系图的路由技术研究
方维维1, 姚雪宁1, 王文瑞1, 安源2, 李晶2
1.北京交通大学 计算机与信息技术学院,北京 100044
2.西安卫星测控中心 宇航动力学国家重点实验室, 西安 710043

第一作者:方维维(1981—),男,安徽芜湖人,副教授,博士.研究方向为计算机网络.email:wwfang@bjtu.edu.cn

收稿日期: 2017-04-13
基金: 国家自然科学基金项目(61401516); 宇航动力学国家重点实验室开放课题(2016ADL-DW0402)
摘要

随着卫星技术和通信技术的发展,由全功能大型卫星组成的卫星星座网络正逐渐被由大量微小型卫星组成的分布式自组织星群网络所替代.这种新型卫星网络架构给星间数据通信和路由带来了自组织、自适应能力方面的问题.本文从延迟容忍的角度考虑,提出利用卫星周期性运动的特点构建网络结构,建立联系图来计算和选择路由.针对异常情况,采用被动发现和重路由机制重构网络拓扑,并利用满消息和空消息的传递来避免拥塞和控制流量.使用OPNET搭建网络仿真场景,分析对比该方案的性能.实验结果表明:与Flood路由、Spray-and-wait路由、Random路由相比,本文提出的路由技术具有更高的抗毁性能,且在平均端到端时延上从2 377 s降到16 s,平均吞吐量上从1 696 bit/s提高到2 895 bit/s.

关键词: 分布式星群网络; 联系图路由; 节点失效; 拥塞避免
中图分类号:TP393
Research on contact graph routing in distributed satellite swarm networks
FANG Weiwei1, YAO Xuening1, WANG Wenrui1, AN Yuan2, LI Jing2
1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044,China
2.State Key Laboratory of Astronautics Dynamics, Xi’an Satellite Control Center, Xi’an 710043, China;
Fund:National Natural Science Foundation of China (61401516); Open Project Program of the State Key Laboratory of Astronautics Dynamics (2016ADL-DW0402)
Abstract

With the development of satellite and communication technology, constellation networks are gradually replaced by distributed self-organized swarm networks, which accordingly leads to the revolution in satellite networks from full-functional large satellites to a large number of micro satellites. This new architecture of satellite network brings new challenges on self-organization and self-adaptation to inter satellite communication and packet routing. From the perspective of delay tolerant network, this paper proposes to utilize the periodic motion of satellites to construct the network topology, and establish contact graphs among satellite nodes to compute and choose routing paths. To cope with exceptional situations, the passively discovering and re-routing mechanism is designed to reconstruct the network topology, and two types of messages (Full/Empty) are employed to avoid congestion and control traffic. The performance of proposed routing algorithm is evaluated and compared with existing work by using the OPNET network simulator. The experiment results show that this new algorithm is more capable of resisting disruptions, and decreases average end-to-end delay from 2 377 s to 16 s, increases average throughput from 1 696 bit/s to 2 895 bit/s, compared to the Flood, Spray-and-wait and Random algorithms.

Keyword: distributed cluster networks; contact graph routing; node failure; congestion avoidance

随着空间探索及军事应用的推动[1], 卫星等航天器之间的组网及数据通信逐渐成为重要的问题和挑战[2].然而, 传统卫星星座网络的设计方法已经存在一些问题, 如依赖固定构型、易被攻击、网络可靠性差和建设成本高等.为降低大型航天器研制和部署风险, 不少国家和地区已开始分布式空间信息系统的研究, 如美国的F6计划和天基群组计划[3].由微小卫星组织而成的星群网络建设成本低、研制周期短、工作方式灵活和抗毁能力强, 并能够完成一些大型卫星所不能完成的信息采集和观测等任务[4], 越来越受到军事部门和研究机构的关注, 其网络协议实现、网络管理技术和通信机制设计等问题都具有重要的研究意义和价值[3].

传统的卫星星座网络具有相对稳定的网络拓扑结构, 每个节点功能完备、分工明确且基本不可替代.而在星群网络中, 节点体积较小, 节点间组织关系不固定, 网络结构松散, 可灵活重组, 具备较强抗毁能力.研究人员根据这些特点, 结合延迟容忍网络(Delay Tolerant Network, DTN)的思想来解决其网络路由和传输问题.目前, DTN的路由策略基本可分为两类, 即洪泛和转发[5].其中, 洪泛策略通过数据的多个拷贝达到数据传输的目的, 如传染路由、喷射路由[6]和概率性路由协议等, 而转发策略则通过网络拓扑结构选择最佳路径进行数据转发, 如最小期望延迟路由和最早发送路由等.与其他类型的DTN网络不同, 卫星网络的节点运动与节点间相遇具有周期性和规律性, 因此可以利用整个网络的链路通断信息来设计路由策略, 这就是基本的联系图路由(Contact Graph Routing, CGR)思想.基于该思想, 文献[5]通过减少网络时延来提高可靠性.文献[7]针对卫星网络负载均衡的问题, 提出两种优化网络性能的算法.然而这些已有工作都是对网络单一性能指标的优化, 不能解决网络节点失效等异常问题.

本文作者针对卫星网络中存在节点失效的异常情况, 以对地观测为任务场景, 基于CGR思想设计构建网络拓扑结构.并详细分析了这种网络结构下的节点通信方式、路由算法和异常处理机制.通过OPNET对该网络进行仿真, 和几种典型的同类型路由算法作为对比, 验证了联系图路由在通信能力及网络性能上的优势.

1 基本通信原理
1.1 联系图建立

参考CGR路由思想, 将每条可用链路称为一条联系(Contact), 则这些联系的集合即可表示网络的拓扑结构, 称为联系图.每条联系的结构如表1所示.

表1 联系的结构 Tab.1 Structure of contacts

为了便于路由, 将以上联系结构中目的节点相同的联系组织为一个列表, 则列表个数为网络中节点的个数.同时为了起到感知节点失效和拥塞避免等功能[8], 将联系图以5元组< 节点ID, 有效字段, 满字段, 库联系图, 当前联系图> 的形式进行组织.其中网络中不同节点分配不同的ID号.有效字段和满字段表示当前节点的当前状态, 前者表示当前节点是否失效, 后者表示当前节点的发送队列是否已满.库联系图和当前联系图包含的所有联系都以当前节点为目的节点, 库联系图中保留所有的联系, 当前联系图中保留当时有效的联系, 并定期更新, 用于路由的动态计算.联系图可预先通过轨道计算得到并在卫星发射之前存在各个节点, 以在发射后立即实现组网.

1.2 通信方式设计

星群网络不能够建立稳定且持久的端到端连接, 因此诸如TCP等面向连接的网络协议无法适用.该网络的数据发送过程应简单直接, 采用转发-确认的方式.

如图1所示, 卫星A根据联系图中的信息, 可在本地自行判断向卫星B发送数据的时机.卫星B收到数据后, 向卫星A发送该数据的应答消息, 卫星A收到应答后则一次通信完成.由于联系图中只保留节点的链路通断特性, 因此需要采用全向天线发送数据, 接收到数据的节点可能不只是目的节点.对于其他接收到数据的节点, 首先会确定是否接收, 对于不接收的数据直接丢弃.卫星与地面站之间的通信与以上过程类似.

图1 卫星通信示意图Fig.1 Schematic diagram of satellite communication

图2所示是卫星节点从接收数据到发送数据所做的处理过程.

图2 数据收发处理结构Fig.2 Structure for receiving and sending data

图2中, 加粗箭头显示节点与外部通信的数据流向; 接收端对发送给本节点的数据做出路由选择后将其移到缓存队列, 而对接收到的应答消息会销毁其对应已发数据的本地副本; 缓存队列用于保存本地节点中目前暂时无法发送的数据; 发送队列处理本地节点向其他节点发送数据的过程.

1.3 基本路由算法

联系图路由是一种面向时变拓扑的动态自组织路由思想[9].它基于已经获得的准确网络拓扑信息, 从而可以做出高可信度的路由计算.有了完整的联系图后, 通过递归检查每条联系, 即可找到符合要求的可用路径.对于当前网络拓扑中的n个节点, 若它们的平均联系个数为x, 则由于需要寻找所有可用路由, 该问题的平均时间复杂度达到O(xn).

考虑到网络规模和场景需求, 在路由计算的过程中加入多个分支限界条件, 排除不可用联系, 并通过合理的跳数限制(命名为 S)来大幅度减少联系检查过程.同时, 将已路过的节点保存在不可达集合(命名为 E)中, 从而避免检查不必要的分支或产生环路.该算法的大致流程如图3所示, 增加多个限制条件后的最差算法时间复杂度不超过 O(xS), 且没有多余的空间开销, 因此算法的额外空间复杂度为 O(1).该网络采用动态路由方式, 只保存路径的时间信息和下一跳节点.

图3 本文提出算法流程图Fig.3 Flow chart of algorithm proposed in this paper

具体算法过程如算法1的伪代码所示.

算法1

输入:联系图G, 不可达节点集合E, 当前数据包B, 目的节点D, 当前路径参数, 跳数限制S;

输出:由可用路径下一跳节点组成的集合P;

将B的上一跳节点和失效节点加入E, 清空P;

Routing(D, 路径参数){

将D加入E, 保留当前路径参数;

for(m ∈ D){

读取路径参数;

if(m过期或数据B过期)continue;

if(D就是数据B的目的节点)

将m的开始时间和结束时间更新为当期路径参数;

else{if(m的源节点就是当前节点){

if(m的剩余容量不足够发送B)continue;

if(D已经在P中)

{保留较短的路径信息; continue; }

保留当前路径信息;

将D加入P, 并更新跳数限制S; }

else{

if(m的源节点在E中)continue;

更新当前路径信息;

if(当前路径的跳数达到S)continue;

else

{调用函数Routing(m的源节点, 路径参数); }

}

}

}

将D从E中取出, 重置当前路径参数; }

路由结束后, 检查下一跳集合(名为P)中的所有路径, 选择最优路径作为数据的下一跳节点, 这里可根据具体需求设定择路标准, 如最早发送时间、最小节点编号和最短跳数等[10].本算法将选择从源节点到目的节点跳数最短的路径作为最优路径.

2 异常处理机制

以上的基本路由算法没有考虑节点失效等异常情况, 导致路由性能无法得到保障.因此, 需要根据具体情况设计相应的异常处理机制.数据转发失败可能的问题有:1)卫星网络中通信距离远、延迟大和环境不稳定等因素会影响数据的发送; 2)目的节点由于外部环境或自身故障等原因失效, 无法完成正常转发工作; 3)由于某些节点失效或某条链路使用频率过高, 从而引起的节点局部拥塞.

2.1节至2.3节分别针对以上问题提出相应的解决措施, 在2.4节中提出针对这些异常处理手段的路由扩展机制实现方法, 从而实现了基于CGR的卫星网络路由方案CGRS(CGR for Satellite).

2.1 超时重传和重路由

针对问题1), 本文设定数据的超时重传机制.在发送数据的过程中, 记录数据最近一次的发送时刻, 同时设定网络的应答等待时间.如果数据在应答等待时间过后仍保存在发送队列中, 则重新发送数据, 并更新最近发送时刻, 从而保证问题1)情况下的数据转发.应答等待时间的设定需要充分考虑数据发送和接收的时间, 过短的等待时间会增加多余的重传次数.

数据的多次重传不在路由算法的考虑之内, 因此在再次重传时可能已经错过了数据的可发送时间.此时网络拓扑发生变化, 目的节点不再可达, 数据进行重新路由.

2.2 感知失效节点

问题 2), 是影响网络重构的重要问题, 本文需要在多种转发失败的情况中筛选出它与其他问题的不同, 从而准确地对网络结构做出改变.为此, 在2.1节基本保证数据转发的措施中, 加入对重传次数的限定.即便空间网络环境中存在一些不可控因素, 但在设备功能正常且多次重传的情况下, 转发失败的情况基本不会发生.因此采用图4所示的流程, 将失效节点的感知整合到重路由和超时重传的检查过程中.

图4 发送队列的异常检测过程Fig.4 Detecting process for exception of sending queue

设定数据的最大重传次数是i, 在发送数据的过程中, 增加记录数据的实际发送次数.首先解决数据是否重路由的问题, 然后在再次发送前, 判断数据的实际发送次数是否超过最大重传次数i.若发送次数超过i, 说明对该数据的i次发送都不成功, 这在目的节点有效的情况下不可能发生, 从而判断目的节点失效.感知到失效节点后, 将本地当前联系图中对应节点的有效字段置0, 使之后的路由过程跳过该节点; 并在网络中广播失效信息, 完成整个网络对失效节点的感知.

2.3 拥塞避免和流量控制

图2中的发送队列是节点的数据出口, 如果这个队列处于满容量状态, 则可能导致大量排队数据来不及发送及本地存储数据的积压, 引起局部拥塞.如图5所示, 为了避免这种状况的发生, 设定稍低于队列满容量的值作为满阈值(如可设置为满容量的80%), 设定变量d来记录未来一段时间发送队列内数据的增量.节点在发送队列的数据量达到满阈值且d不为0时, 发送包含本节点ID的满消息, 使其他节点的路由过程跳过该节点, 从而抑制本地节点的入口流量; 并将联系图中该节点的满字段加1, 用来计数节点发送满消息的次数, 发送满消息达到一定次数后即可停止, 避免过多消耗链路资源.

图5 发送队列示意图Fig.5 Diagram for threshold controlling of sending queue

通过限制入口流量解决拥塞压力后, 还需要相应的流量恢复机制.如图5中与满阈值相对应的空阈值(如可设置为满容量的20%).当节点发送队列中的数据量低于空阈值时, 就会发送包含本节点ID的空消息, 使其他节点在路由计算的过程中恢复该节点, 从而恢复本地节点的入口流量; 并将联系图中该节点的满字段减1, 用来计数空消息的发送次数.

2.4 路由机制扩展

除正常的数据包和应答消息外, 节点间还包括3种异常消息的通信, 即上文提到的失效消息、满消息和空消息.异常消息只包含两个内容:异常节点ID和异常类型.异常节点ID标明发生异常的节点, 异常类型标明该节点发生的是什么异常.这些消息一旦发出, 接收节点会对它们做类似的处理, 见图6.

图6 异常消息处理示意图Fig.6 Schematic diagram of abnormal message processing

首次收到异常消息的节点会对其进行处理和转发, 但节点对于重复收到的消息会直接忽略, 避免造成多余的链路资源消耗.节点对异常消息的广播和转发保证了异常消息的广泛传播, 使整个网络能够尽量及时感知到网络结构的变化.

收到失效消息和满消息后, 节点会将联系图中对应节点的有效字段置0, 使之后的路由过程都跳过该节点, 从而停止向异常节点转发数据.收到空消息的节点会将联系图中对应节点的有效字段置1, 从而恢复对该节点的数据转发.而满字段只对本地节点有意义, 用于在收到数据时判断是否发送满消息.

3 仿真结果与性能分析
3.1 仿真场景

使用OPNET仿真软件实现相应的节点模型并构建网络场景, 对本文作者提出的 CGRS性能做分析和对比.仿真网络场景中包含55个卫星节点、3个地面站节点, 并设定3个地面移动节点模拟观测任务中的对象(即数据源), 其中卫星轨道参考文献[11]的设计, 具体参数见表2.轨道数据使用卫星系统仿真工具STK生成, 并导入到OPNET中使用, 所产生的初始网络拓扑如图7所示.

表2 卫星轨道数据 Tab.2 Data of satellite orbits

图7 OPNET仿真实验中的卫星网络初始拓扑Fig.7 Initial topology of satellite network in the OPNET simulator

为了分析和对比CGRS性能特点, 同时实现文献[12]中使用的两种典型DTN路由算法:Flood算法和Spray-and-Wait算法.Flood算法的思想是将数据发送给最早遇到的N个节点, 相当于每经过1跳, 数据就复制N份, 且规定每个节点每份数据只能收1次, 直到目的节点收到数据.Spray-and-Wait算法将节点分为Spray和Wait模式, 处于Spray模式的节点将数据发送给最早遇到的 N个节点, 而收到其他卫星发送的数据的节点转为Wait模式, 在遇到目的节点时才发送数据, 相当于两跳路由.另外, 还实现了一种随机路由(Random), 使卫星随机决定某个数据是否发送给遇到的节点.

3.2 通信性能分析

1) 在第1组性能对比实验中, 生成包含5 000个数据包时间间隔期望为2的泊松数据流, 每次仿真的各节点参数相同, 仿真开始后节点随机失效, 失效节点个数分别为0、10、20、30、40、50, 仿真时长为6 h, 测量地面站收到的包个数占网络中包个数的比率, 以此作为衡量网络通信能力的指标.每组实验运行5次, 取算术平均值, 得到图8的对比图, 此处的资源消耗为单位时间内网络中存在的数据包总体数量.

图8 多种路由方法的网络收包率和资源消耗对比Fig.8 Comparison of receiving rate and resource consumption for multiple routing methods

从图8中的实验结果可知, 在规模为55个卫星的网络中, 当失效节点个数少于15个时, CGRS能够保证网络数据的正常接收率在80%以上; 并且在无节点失效的情况下, 网络能够达到100%的数据接收率, 与对比的其他两种DTN路由算法相比有着明显的优势; 而Random算法虽然能够达到较高的转发能力, 但这是通过大量消耗网络资源为代价做到的, 在资源有限的卫星网络中实际并不可取.从网络转发能力和网络资源消耗这两个方面来看, 在参与对比的路由方案中, CGRS由于对网络拓扑有着较为精确的感知, 以最低的资源消耗达到了最高的转发能力.

2)在第2组性能对比实验中, 卫星不断从地面接收数据, 节点随机失效, 仿真时长2 h, 统计网络中的端到端时延、地面站吞吐量等性能指标.

图9是各路由方法在不同失效节点个数时的网络性能对比.Flood路由在时延和吞吐量上性能最差.相比之下, Spray-wait算法在参考Flood算法的情况下作了改进, 一定程度上提高了网络的性能.本文仿真实验中, 联系图路由虽然以跳数最短为择路标准, 但在时延和吞吐量方面也具有更好的性能, 与其他算法相比在路由性能上有着明显的优势.

图9 多种路由方法的平均端到端时延和平均吞吐量对比Fig.9 Comparison of average end-to-end delay and average throughput for multiple routing methods

4 结论

1)本文作者根据卫星节点的周期性运动特点和联系图思想, 基于联系图路由思想实现网络通信, 提出基本的路由算法和超时重传、重路由、失效节点感知和拥塞控制等异常处理机制.

2)实验表明本文提出的CGRS路由技术有效地保证了网络的通信能力, 与其他典型的路由算法相比, 在平均端到端时延上从2 377 s降到16 s, 平均吞吐量上从1 696 bit/s提高到2 895 bit/s, 具有明显的优势.

在未来的工作中, 需要考虑针对不同优先级数据对路由和转发策略做出进一步改进.

The authors have declared that no competing interests exist.

参考文献
[1] 高自新, 阮晓刚. 基于地面中继的卫星通信系统性能分析[J]. 北京交通大学学报, 2016, 40(3): 14-18.
GAO Zixin, RUAN Xiaogang. Performance analysis of satellite communication systems with the terrestrial relay[J]. Journal of Beijing Jiaotong University, 2016, 40(3): 14-18. (in Chinese) [本文引用:1]
[2] 张威, 张更新, 苟亮. 空间信息网络中的星座设计方法研究[J]. 中兴通讯技术, 2016, 22(4): 19-23.
ZHANG Wei, ZHANG Gengxin, GOU Liang. Satellite constellation design in space information network[J]. ZTE Technology Journal, 2016, 22(4): 19-23. (in Chinese) [本文引用:1]
[3] 王敬超, 于全. 基于分布式星群的空间信息网络体系架构与关键技术[J]. 中兴通讯技术, 2016, 22(4): 9-13.
WANG Jingchao, YU Quan. System architecture and key technology of space information network based on distributed satellite clusters[J]. ZTE Technology Journal, 2016, 22(4): 9-13. (in Chinese) [本文引用:2]
[4] RADHAKRISHNAN R, EDMONSON W, AFGHAH F, et al. Survey of inter-satellite communication for small satellite systems: physical layer to network layer view[J]. IEEE Communications Surveys & Tutorials, 2016, 18(4): 2442-2473. [本文引用:1]
[5] 杨锋, 虞万荣, 刘波, 等. C基于接触关系的空间DTN网络容量约束路由算法[C]// 微处理器技术论坛, 2012: 74-83.
YANG Feng, YU Wanrong, LIU Bo, et al. Capacity restricted foremost routing algorithm for space DTN based on contact graph[C]// Micro Processor Technology Forum, 2012: 74-83. (in Chinese) [本文引用:2]
[6] MONIKA A, VISHAL G. Simulation of epidemic, spray and wait and first contact routing protocols in delay tolerant network[C]//National Conference on Advances in Engineering, Technology & Management, 2015: 30-34. [本文引用:1]
[7] BEZIRGIANNIDIS N, CAINI C, MONTENERO D D P, et al. Contact graph routing enhancements for delay tolerant space communications[C]// Advanced Satellite Multimedia Systems Conference and the Signal Processing for Space Communications Workshop, 2014: 17-23. [本文引用:1]
[8] 郑少仁, 王海涛, 赵志峰, 等. Ad Hoc网络技术[M]. 北京: 人民邮电出版社, 2005: 64-90.
ZHENG Shaoren, WANG Haitao, ZHAO Zhifeng, et al . Ad Hoc network techniques[M]. Beijing: People’s Posts and Telecom Press, 2005: 64-90. (in Chinese) [本文引用:1]
[9] ARANITI G, BEZIRGIANNIDIS N, BIRRANE E, et al. Contact graph routing in DTN space networks: overview, enhancements and performance[J]. IEEE Communications Magazine, 2015, 53(3): 38-46. [本文引用:1]
[10] CAINI C, FIRRINCIELI R. Application of contact graph routing to Leo satellite DTN communications[C]// IEEE International Conference on Communications, 2012: 3301-3305. [本文引用:1]
[11] 林滨杰. 多层卫星网络拓扑结构及路由协议研究[D]. 北京: 中国科学技术大学, 2010.
LIN Binjie. Research on topology and routing protocol of multilayer satellite network[D]. Beijing: University of Science and Technology of China, 2010. (in Chinese) [本文引用:1]
[12] MEHTO A, CHAWLA M. Comparing delay tolerant network routing protocols for optimizing L-copies in spray and wait routing for minimum delay[C]// Conference on Advances in Communication and Control Systems, 2013: 239-244. [本文引用:1]