基于流量预测的双层卫星网络动态路由算法

阎冬 汪路元

（北京空间飞行器总体设计部，北京 100094）

基于流量预测的双层卫星网络动态路由算法

阎冬 汪路元

（北京空间飞行器总体设计部，北京 100094）

卫星网络具有覆盖广泛、接入简单等优点，被认为是下一代互联网的重要组成部分。文章提出了一种基于流量预测的双层卫星网络动态路由技术，拓扑采用LEO层和GEO层双层卫星网络结构，能够支持卫星网络新节点的动态加入。针对卫星网络管理员节点在执行网络任务时可能造成高负载导致高丢包率，从而影响网络性能的缺点，提出卫星网络管理员节点调整策略，根据流量预测算法对超过阈值的卫星网络管理员节点进行更换。最后，文章通过仿真试验对算法性能进行了验证，证明此算法在端到端时延和管理员节点丢包率方面具有优势。

双层卫星网络；动态接入；流量预测

1 引言

随着全球一体化进程的加快，人们对于网络技术的依赖程度越来越高。传统网络主要依靠地面的链路和设备传输信息，难以覆盖高山、海洋、沙漠等地形复杂的区域，并且一旦网络链路发生故障，则会造成长时间的网络服务中断，给国家经济和建设造成巨大损失［1］。卫星网络具有全球覆盖、接入简单、支持多种业务等诸多优点，在气象预测、环境与灾害监测、资源探测等领域得到广泛应用，被认为是下一代互联网的重要组成部分。

由卫星通信技术和组网技术的发展可以看出，卫星网络逐步由单层组网方式发展为多层组网方式。虽然单层组网方式实现较为简单，但却不够灵活，不便于实现网络管理；多层组网方式虽然实现较单层组网方式复杂，并且组网层数越多实现越复杂，但却能很方便地实现网络管理，能够提供包括实时业务、非实时业务等多种类型的网络服务。当前我国正在开展的导航网络建设，就是一种多层拓扑结构的网络，也因为它良好的覆盖性、较高的数据传输能力等，被诸多研究者认为是未来空间网络的重要组成部分。因此，本文研究多层卫星网络的路由机制对未来卫星网络建设有极强的现实意义。

目前，国内外研究人员已经针对多层卫星组网的路由策略进行了一定的研究，并且提出了多种方案。这些方案主要有虚拟节点策略和虚拟拓扑策略［2-6］，大多只对相对固定网络拓扑进行了研究，虽然可以在不同的时间或空间切换路由表，但却无法对临时新加入网络的节点进行网络服务。除此之外，这些方案将拓扑中的某些节点作为网络的管理员节点，并没有关注到这些节点本身的负载状况。在实际情况中，由于卫星的高成本因素，这些管理节点往往并不只是起到网络作用，还要完成其它常规任务。因此，一旦这些管理节点的负载过重，不仅影响它的常规任务的执行，而且会使整个网络性能急剧下降，甚至崩溃。针对这些问题，并且综合考虑了系统实现的复杂程度，本文提出了一种基于流量预测的双层卫星网络动态路由算法（Traffic Prediction Based Dynamic Routing，TPDR），可以支持网络节点的动态加入，又能够避免网络中的管理员节点负载过重而影响网络性能。

2 基于流量预测的双层卫星网络动态路由方法

针对当前多层卫星网络路由方法只能对固定网络结构中的节点进行数据路由和网络服务，无法解决临时性节点加入卫星网络实现正常网络服务，并且没有考虑卫星网络管理员节点的负载情况，可能导致路由信息发送失败，使网络性能下降，甚至崩溃的问题，本文拟从以下几个方面进行改进：首先，提出一种支持临时性节点动态加入并正常实现网络服务的双层卫星网络模型；其次，提出基于流量预测的网络节点负载控制方法，可以有效避免卫星网络“管理员”节点负载过高而影响网络性能。

2.1 定义

在对TPDR方法进行详细介绍之前，需要对其中的一些概念加以定义。①卫星网络：由在轨航天器组成的通信网络，可以支持子网内节点间、不同子网节点间、节点到地面等通信方式，本文主要讨论前两种天基方式的通信。②子网（SN）：每个LEO层轨道面上的卫星组成一个子网。③区域（AREA）：每个GEO卫星视距范围内的LEO层卫星组成一个区域。④网络节点（NODE）：卫星网络中的节点由卫星或者航天器组成，包括LEO层卫星和GEO层卫星，由于其特殊性，具有处理能力有限，难以补充处理资源的特点。网络节点可以使用逻辑地址Lij来描述，Lij=｛（i，j），0≤i≤NL-1，0≤j≤NS-1｝，i表示子网编号，j表示LEO卫星在本子网内的编号，NL表示子网数量，NS表示子网内LEO卫星数量。如果j=0，则表示该网络节点为GEO卫星节点。⑤管理员节点（MANAGER）：每个区域的一个子网内LEO卫星都存在一个管理员。它维护本区域节点信息，包括节点连接关系和健康数据，任务是将接收方不属于本子网的数据包发送给GEO卫星。⑥链路LINK：每个子网内的LEO卫星按照各自位置依次由子网内链路（Inner Sub-network Link，ISL）相连接，LEO层管理员则通过层间链路（Inter Orbit Link，IOL）与GEO卫星相连接。

2.2 TPDR网络模型

TPDR网络是由LEO层卫星节点和GEO卫星节点组成的双层网络，TPDR网络模型示意图如图1所示。

图1 TPDR网络模型示意图Eig.1 TPDR topology

图1中，每个子网内的LEO卫星节点依次与相邻的LEO卫星节点有链路链接，而GEO卫星节点只与子网内的管理员有链路相连。TPDR中节点的连接关系如图2所示。

TPDR中，每个LEO卫星节点掌握着本子网的拓扑信息，在子网内LEO卫星节点可以用定义④中的逻辑地址来表示，LEO卫星节点可以根据自己当前的物理位置信息（可以使用经度和纬度来表示），结合本子网的运动轨迹，推断出本子网其它节点目前的物理位置。当有新节点要加入到子网中时，需要首先向本子网的管理员节点将自己的信息注册，然后管理员节点向其所属的GEO卫星报告新节点信息。当管理员节点接收到GEO卫星的确认信息后，向新节点发送确认加入子网信息，并更新本子网成员信息表后在全子网广播。GEO卫星掌握着视距范围内所有子网的拓扑结构和成员信息，以及其他GEO卫星所覆盖的子网范围。如图2中，每个GEO卫星视距范围内包含多个子网，可以覆盖从南纬70°到北纬70°之间的区域，GEO会与每个子网内的管理员建立连接，并进行数据传输。首先，GEO卫星会指定每个子网内一个LEO卫星节点作为本子网的管理员节点，该LEO卫星节点是本子网在GEO卫星视距范围飞行时间最长的网络节点，这样可以尽量减少管理员切换的次数。在图2中，假设LEO卫星由南向北飞行，G1在SN1中选择L14作为本子网的管理员。当L14即将飞出G1的视距范围时，会给G1发送管理员切换请求。G1收到请求后会重新选择新的管理员，向新管理员发送管理员执行命令并与其建立连接，同时给L14发送管理员切换确认，并断开与其的连接。新的管理员收到管理员执行请求后，向G1发送管理员执行确认，并在本子网广播管理员身份信息，并收集本子网所有成员的健康信息。管理员也会定期向其所属的GEO卫星节点汇报自己的健康状况信息。

图2 TPDR节点的连接关系Eig.2 Nodes connection relation

在TPDR中传输的天基范围内数据包，简单来说可以分为3种类型。第一种是发送者和接受者在同一个子网SN1中如L11要给L13发送数据包，则只需将数据包在本子网传输即可。第二种是发送者L13在子网SN1中，而接受者L22在子网SN2中，并且子网SN1和SN2都在同一个区域中。L13现将数据包发送给本子网的管理员L14，然后L14将数据包发送给G1。G1经过查表后发现接收方在本区域的子网SN2，将数据包发送给SN2的管理员L23。最后，L23在本子网内将数据包发送给L22。第三种是发送者L13在子网SN1中，而接受者L52在子网SN5中，并且子网SN1和SN5不在同一个区域中。L13现将数据包发送给本子网的管理员L14，然后L14将数据包发送给G1。G1经过查表后发现接收方不在本区域，接收方子网属于G2的覆盖范围，则将数据包发送给G2。G2接收到数据包后，发现接收方在子网SN5，然后将数据包发送给SN5的管理员L53。最后，L53在本子网内将数据包发送给L52。

在实际的卫星网络中，由于卫星节点可能由多种类型的卫星构成，如导航卫星、遥感卫星、通信卫星等，因此需要支持多种类型数据传输。TPDR能满足未来卫星网络工程中的数据传输，支持多种类型的服务质量，既可以支持对实时性要求高的数据，如通信数据，又可以支持实时性要求没那么高，但是却对数据完整性要求很高的数据，如数据量较大的多媒体数据。前者的实现主要根据当前时刻子网内节点位置与地面站的位置的相对关系，将数据发送到处于地面站测控范围内的适合节点上，然后直接发送到地面；后者则是将数据发送到GEO卫星节点中，在确认了数据完整性之后，再通过GEO卫星节点发送到地面。

2.3 基于流量预测的节点负载控制方法

卫星网络具有动态变化、节点处理资源局限、难以维护等与地面网络差异很大的特点，决定了对该网络拓扑结构和节点管理的研究具有极大的挑战性。在卫星管理中，为了实现对动态网络的管理，需要有一些节点额外承担网络管理的任务。这些卫星网络管理员节点在网络管理中起着很重要的作用，但是由于它们还要执行常规任务，在出现数据量很大的网络任务时可能会导致管理员节点负载过重，影响卫星网络的正常运行，甚至导致网络崩溃。

数据包到达率是衡量某一时刻网络节点流量大小的指标，也是影响空间网络节点性能的一项关键指标。数据包到达率越高，节点为了处理这些数据包所需要的计算量也越大。如果数据包到达率超过了节点的处理阈值，可能导致节点较高的丢包率。由于管理员节点是空间网络中的关键节点，当管理员节点负载较大时，难以在执行常规任务的同时，保证路由表计算、路由信息分发等网络任务的完成。如果能够有效预测某一时刻节点流量情况，可以有效地避免节点负载过高，保证空间网络能够维持较低的丢包率，提供稳定的数据传输能力。

由于管理员节点在双层卫星网络中的重要作用，它们的性能往往对整个网络性能产生较大影响。因此，需要在卫星网络路由机制中增加管理员节点负载控制策略，保证管理员节点的高性能工作状态。本节提出了一种基于流量预测的管理员节点负载控制方法。考虑到卫星节点的处理能力的局限性，本文采用计算相对简单的线性预测技术对数据流量进行分析和预测。它的基本思想是：流量数据的每个取样值可以用它过去若干个取样值的加权和来表示，各加权系数的确定原则是使预测误差的均方值最小。典型的线性预测模型有自回归模型（Autoregressive，AR）和自回归滑动模型（Autoregressive Moving Average，ARMA），ARMA模型在计算机网络和传感器网络中的流量预测方面已经有了一定的研究［7-9］。应用ARMA能够有效分析出平稳数据序列的相关性，比AR模型具有更小的预测方差值。因此，本文选择ARMA（2p，2p-1）模型对卫星网络节点的数据流量进行分析。其中p为阶数，如果该值过大，将需要很大的计算量，所以本文算法中取常用的ARMA（2，1）模型。

假设某卫星网络节点的数据流量序列为｛Xn'｝，该序列具有周期性，但可能会存在着一定的非平稳性，需要对其进行取对数运算，得到平稳序列｛Xn｝。随后使用该平稳序列建立ARMA模型，预测第n+1个流量。

式中：B是后移算子；ai是白噪声，它是独立同分布的高斯随机变量。

式中：φ1，φ2，θ1是估计参数。ARMA矩估计方法主要有最小二乘法，最大似然估计方法，最大熵估计方法等等，考虑到卫星网络节点的计算处理能力，本文采用最小二乘估计方法求解通过估计参数判断时间序列的稳定性，其稳定性条件为

如果满足此条件即为平稳序列，得到ARMA拟合模型为

根据卫星节点的数据处理能力，为它们设置数据处理阈值Tmax，即流量阈值。一方面，在选择本区域管理员节点时，需要首先对被选择节点的流量进行预测，如果预测得到的管理员节点流量大小超过该阈值Tmax，则不选择该节点作为管理员节点；另一方面，当管理员节点在运行过程中，会按照一定的周期对它的流量进行预测和评估，如果其流量大小超过该阈值Tmax，则需要在本区域的本子网内切换管理员节点。考虑到工程实际中卫星节点计算能力有限，需要尽可能使用简单的切换算法，减少卫星节点的计算量开销。管理员节点确定和切换算法流程图见图3。

3 性能评价

在卫星网络路由机制的设计中，端到端延迟及丢包率是其中重要的性能指标，直接关系到路由机制是否适用于实际的卫星网络工程应用。为了验证TPDR的性能，本节选择一种经典的SGRP多层卫星网络路由算法［5，10］，对卫星节点端到端时延和管理节点丢包率进行对比。实验中各项环境参数，包括轨道高度、角速度、数据包平均长度等，按照典型的导航卫星及遥感卫星的实际参数进行设置，充分贴近实际节点的具体情况，具有更强的说服力及现实意义。对于不同的卫星网络路由算法，卫星节点端到端时延是一项基本的网络性能指标，能够说明网络路由方法的合理性。管理员节点是多层卫星网络中的关键节点，丢包率反映了它目前的数据转发和传输能力，影响着整个网络的性能。参照文献［11］，本节的实验设置TPDR及SGRP环境参数，具体参数设置见表1。

表1 实验环境参数设置Table 1 Experiment environment setting

为了保证实验的真实性和有效性，对不同平均链路负载状况下进行1000次实验，取平均值。图4是不同链路负载状况下的端到端平均时延的实验结果。

图4 平均端到端时延Eig.4 Average end-to-end delay

在图4所示的卫星节点平均端到端时延的实验结果不难看出，TPDR的性能要优于SGRP。可能是出于以下原因：首先，SGRP算法需要将收集的网络拓扑在MEO层的不同MEO卫星之间进行信息交换，网络拓扑更新较慢；其次，SGRP的网络拓扑快照划分较为琐碎，链路更新过于频繁，协议时延开销较大。

除了端到端时延之外，本节要对卫星网络管理节点的丢包率进行验证。图5是卫星网络管理员节点在不同链路负载状况下丢包率的实验结果。实验中假设子网中节点流量的3%发往子网外。

图5 卫星网络管理节点丢包率Eig.5 Packet loss rate of manager node

图5所示的实验结果可以看出，TPDR在卫星管理节点丢包率方面有着更好的性能。其中一个原因是TPDR卫星管理节点使用流量预测算法，当卫星管理员节点预测到在某一时刻处于某一位置的预测流量造成的负载大于某一个阈值时，将更换子网内的管理员节点，而SGRP中却没有管理员节点负载控制策略。本试验中设置管理员节点切换的负载阈值为30%。另一个原因是SGPR中的管理员节点负责的成员较多，需要转发的本区域外的数据较多，也会使丢包率有一定的增加。

4 结束语

天地一体化网络是未来空间数据系统发展的必然趋势，而卫星网络则是其中的主要组成部分。当前，从国家到各个研究机构和高校，都将卫星网络作为一项非常重要的研究内容加以推进。本文结合目前我国已经开展的航天工程布局，针对卫星节点计算能力有限的实际情况，提出一种基于节点流量预测的双层卫星动态路由算法TPDR。该算法主要由以下几个部分组成：①TPDR拓扑由LEO层卫星和GEO卫星构成，可以支持多种类型的服务质量，支持新节点动态加入，并且改进了SGRP中拓扑快照切换频繁的缺点，使端到端平均时延得到了改进。②TPDR管理员节点可以根据某一物理位置和某一时间段内的数据流量的历史信息，预测下一次的数据流量值，如果该流量造成的节点负载大于设置的阈值，则更换子网的管理员节点，这样能够避免子网管理员节点丢包率过高。最后通过仿真验证的方法证明TPDR在端到端平均时延和子网管理员丢包率方面有较好的性能，能够对未来空间网络建设起到指导作用。

（

）

［1］Akyildiz I E，Jeong S.Satellite ATM networks：a survey［J］.IEEE Communication Magazine，1997，35（7）：30-44

［2］Ekici E，Akyildiz I E，Michael D B.Datagram routing algorithm for LEO satellite networks［C］//Proceedings of IEEE Infocom.New York：IEEE，2000：500-508

［3］Werner M.A dynamic routing concept for ATM-based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997（8）：1636-1648

［4］Akyildiz I E，Ekici E，Bender M D.MLSR：a novel routing algorithm for multi-layered satellite IP network［J］.IEEE/ACM Transaction on Networking，2002（3）：411-424

［5］Chen C，Ekici E，Akyildiz I E.Satellite grouping and routing protocol for LEO/MEO satellite IP networks［C］//Proceedings of The 5th ACM International Workshop on Wireless Mobile Multimedia.Los Angeles：ACM，2002：109-116

［6］Chen C，Ekici E.A routing protocol for hierarchical LEO/MEO satellite IP networks［J］.ACM Wireless Network Journal，2005，11（4）：507-521

［7］曹晓梅，韩志杰，陈贵海.基于流量预测的传感器网络拒绝服务攻击检测方案［J］.计算机学报，2007，30（10）：1798-1805 Cao Xiaomei，Han Zhijie，Chen Guihai.DoS attack detection scheme for sensor networks based on traffic prediction［J］.Chinese Journal of Computers，2007：1798-1805（in Chinese）

［8］李捷，刘先省，韩志杰.基于ARMA的无线传感器网络流量预测模型的研究［J］.电子与信息学报，2007，29（5）：1224-1227 LiJie，Liu Xianxing，Han Zhijie.Research on the ARMA-based traffic prediction algorithm for wireless sensor network［J］.Journal of Electronics&Information Technology，2007，29（5）：1224-1227（in Chinese）

［9］邹柏强，刘强.基于ARMA模型的网络流量预测［J］.计算机研究与发展，2002，39（12）：113-118 Zou Baixian，Liu Qiang.ARMA-based traffic prediction and overload detection of network［J］.Journal of Computer Research and Development，2002，39（12）：113-118（in Chinese）

［10］龙飞.卫星网络鲁棒QoS路由技术研究［M］.北京：国防工业出版社，2010 Long Eei.Research on robust QoS routing for satellite network［J］.Beijing：National Defense Industry Press，2010（in Chinese）

［11］王汝传，饶元，郑彦，等.卫星通信网路由技术及其模拟［M］.北京：人民邮电出版社，2010 Wang Ruchuan，Rao Yuan，Zheng Yan，et al.Satellite communication network routing technology and simulation［M］.Beijing：Posts&Telecom Press，2010（in Chinese）

（编辑：张小琳）

Traffic Prediction-based Routing Algorithm for LEO&GEO Satellite Network

YAN Dong WANG Luyuan
（Beijing Institute of Spacecraft System Engineering，Beijing 100094，China）

Satellite network has the advantage of global coverage and simple access，so it is considered to be an important part of next generation Internet.In this paper，we propose a novel traffic prediction based dynamic routing technique for double-layered satellite networks，which is called TPDR.It has a double-layered structure，composed of LEO layer and GEO layer.TPDR supports new nodes to join the network，and prevents the manager nodes from becoming overloaded based on traffic prediction.In the end，the performances of end-to-end delay and loss rate of manager packet are evaluated by simulations.

double-layered satellite networks；dynamic access；traffic prediction

TP393.04

A DOI：10.3969/j.issn.1673-8748.2015.03.012

2015-02-13；

2015-05-05

国家自然科学基金重大研究计划（91438102）

阎冬，男，博士，工程师，研究方向为星间网络技术与航天器数据管理技术。Email：yandong200@163.com。