《基于流量工程的最小链路代价多层卫星路由算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

基于流量工程的最小链路代价多层卫星路由算法

范文

刘冠男++傅宁

摘要：本文首先分析了多层卫星路由研究的现状，指出当前环境下多层卫星路由算法研究的重点在路由的层次化和分层处理。针对现有路由算法在QoS（Quality of Service）性能上的局限，在此基础上提出了基于流量工程的最小链路代价多层卫星路由算法TE-MSP（Traffic Engineering-Minimizing Sum of Path-cost），建立了流量模型和链路代价公式，并通过仿真验证了该算法能在繁忙时起到12%的分流效果、并减少23%的链路花费。

关键词：多层卫星；路由；流量模型；代价函数

中图分类号：TN915.09 文献标识码：A DOI： 10.3969/j.issn.1003-6970.2015.10.020

引言

传统卫星和地面网关以微波作为信息传输媒介，受到频率限制，仅能工作在每秒百兆比特量级的传输速率上，勉强能实现星上业务的存储转发功能。

近几十年来，卫星激光技术和节点处理能力方面的提高，使卫星网络的通信能力提升至一个新的水平。卫星节点已从早期的信号接收处理的中继站，转变为具有星上处理能力与存储能力、能够进行自主计算，使卫星节点间组网的成为可能。

目前国内外已投入使用的卫星网络多是单层卫星，同时借助地面站来完成中转和监控任务，不仅不能充分利用卫星网络的资源和结构，同时地面站会受到地理环境因素的限制而难以完美建立。因此，具有星间链路，由多轨道卫星组成的网络成为卫星通信发展的趋势。同时针对多层卫星路由的研究仍是当前的热点。在未来空天地一体化信息网络融合的发展背景下，卫星网络因为在其中的重要组成和衔接部分功能正逐渐成为重视和青睐的对象，而国内外对卫星网络的研究仍不成熟，很多关键技术和核心问题尚待解决。由最初的同步轨道卫星发展到现在的多层协作卫星网络，利用卫星实现全球、应急以及军事等特殊环境下的通信优势越来越明显。已有的多层卫星网络路由协议包括HSRP （hierarchical satellite routing protocl），MLSR （multilayered satellite routing）， TDRP （tune-slot division QoS routing protocol等。

国内外学者对路由性能和卫星链路建模两方面的研究有很多的经验，但将路由技术应用到多层卫星场景中是一个新的领域。卫星通信网络作为解决传统网络局限性和满足通信需求的关键，成为国内外社会研究的热点。

国外方面，2000年，韩国的Jae-Wook Lee等人提出了星上星系统，利用多层网络解决星间长距离传输问题，并提出了HSRP算法。2010年，土耳其的A.AIGhamdi等人提出了一种基于虚拟区域的最小带宽算法。该算法根据卫星网络的数据流量选择最短路径，具有较好的复杂度和QoS性能但局限于单层卫星。2011年，日本的Noriki Uchida等人基于卫星网络研究多路径冗余方案以应对灾难场景，利用链路存活检测和多路径概率传输等技术手段保证数据的安全性，但没有关注网络的QoS性能。

国内，2012年，哈尔滨工程大学的杨春秀提出并设计了优化的路由协议NMLSR （New Multi-LayeredSatellite Routing），该路由协议相对于MLSR（Multi-Layered Satellite Routing）协议具有较小的路由开销，较低的丢包率。但适用的场景受到限制。2012年浙江大学的邓德鑫提出了基于MPLS的多层卫星网络路由算法，采用信息采集的路由策略，针对时延敏感和业务需求进行了问题建模，缺少对因素的综合考虑。2014年，西安电子科技大学的陈竞提出了一种适用于双层卫星网的非对称路由协议-A-SGRP （Asymmetric-Satellite Grouping and Routing Protocol）路由协议主要从最短路径计算、路由表优化和特殊链路情况处理方案这三方面对SGRP （SatelliteGrouping and Routing Protocol）协议进行了改进及优化。但还有全局路由定期更新效率低的问题。

目前对多层卫星路由算法的研究主要是单一的时延丢包率等因素，没有对时延、带宽等链路因素进行综合考率，同时许多算法采用分组思想，选择覆盖时间长的波束进行接入，限制了卫星的选择并需要地面站届入。因此本文提出基于流量工程的最小链路代价多层卫星路由算法TE-MSP（Tratric Engineer-ing-Minimizing Sum of Path-cost）设计流量模型，控制流量分配减少拥堵提出链路代价函数，综合考虑QoS因素影响，以时延带宽作为公式因子，既保证了QoS性能，同时避免了对接入控制的限制。

1 基于流量工程的最小链路代价多层卫星路由算法

为了减轻网络拥塞，对整个网络的流量进行合理控制，因此提出基于流量工程的最小链路代价多层卫星路由算法TE-MSP （Tratllc Engineering-MinimizingSum of Path-cost），本算法借助流量工程中设计流量模型，提出链路代价函数，综合考虑多QoS因素的影响，从而选择出适应大容量、复杂网络的卫星转发路径，在特定情况下具有更好的时延和链路条件，具有一定的拥塞控制能力。应用该算法的网络结构图如图l所示。

图l所述的卫星网络由LEO/MEO两层卫星组成。层内卫星由层内链路连接，两层卫星间由层间链路连接。MEO对低层卫星具有数据收集管理功能，因此层间链路具有充足的带宽。

1.1 流量工程

流量工程指通过路由选择均衡网络流量，使数据均匀分布，减少网络拥堵的技术。在大规模网络中，大量用户和业务存在，网络中存在大量数据，如果采用RIP （Routing Information Protocol）、OSPF （OpenShortest Path First）等最短路径协议，会导致某些节点具有大量数据排队，增加整个网络时延，降低全网节点的利用率。

流量工程中的指标有链路级别，即：带宽、时延、利用率：还有流量请求级别，即：最小化路径时延（路径上所有链路时延之和）、路径最大链路利用率和路径最大可用带宽。本文借助流量工程，设计双层卫星的物理拓扑映射规则，提出流量分配公式，从而优化流量工程指标。

流量通过映射分布到网络的各链路中，映射方式可以表示为不同节点间的转移概率。转移概率的计算过程需要获取全局的拓扑信息。首先多层卫星网络采用RIP算法，卫星节点向相邻节点发送数据包，各节点通过包里的ST table逐渐修改完善拓扑信息，其包格式设计如下图2所示。

ST table中记录了节点s，t之间的跳数H，（i，j）∈E的时延delay（i，j）。ιij表示链路的流量，ci，j表示最大容量，则对于i，j都属于LEO节点时，公式（1）表示（i，j）的转移概率。

在公式（1）中，表示利用率的倒数，与转移概率之间是负指数关系，这是为了强调利用率对转移概率的负反馈作用。H、T表示时延越短，跳数越小的路径上的链路转移概率越大。

对于i，j中存在MEO节点的情况不能简单的使用公式（1），使用MEO时应该考虑MEO卫星承载着核心管理功能，不能考虑线性的使用概率。同时MEO卫星的带宽充足，主要考虑发生流量碰撞造成的影响。

MEO的下行端口数为M，已使用的端口为数N，为了避免流量较大时发生碰撞，从而使下行链路时延增加，LEO丢包率增大，MEO选择的概率公式如公式（2）。w1、W2是调整MEO选择概率的权值，改变它们将改变曲线的平缓和尖锐区间并能控制其转变阈值，从而使MEO的使用方式灵活自由。通过仿真验证，w1取值为1，w2取值0.6时，接入MEO的概率几乎不受影响且发生碰撞的概率较小。

拓扑计算后的R表示在节点s，t间的转移概率，网络中的流量矩阵用D表示，它代表网络中节点s，t之间的流量请求值，物理拓扑与流量矩阵的乘积就是网络流量分布L。在一个有向图G （V，E）中，L是具有E个元素的向量，R是DxE的矩阵.如公式（3）所示，其中rde，o≤rde≤1，d∈{（s，t）|s，t∈V），e∈E。

链路的负载L=DxR表示s，t之间的流量之和。说明流量的输出由转移概率矩阵和网络流量决定，以概率公式的方法可以优化网络。

在解决实际问题时需要引入约束条件，如带宽、时延等因素，并通过定义路径的选择方式得到优化路由。如果以￠i，j表示链路（i，j）上的路由代价，则链路代价约束的公式如下式（4）

链路代价的具体内容在下一节。

1.2 链路代价模型

星上星系统是一种连接LEO及其上层卫星的架构，该系统的转发标准是短距离使用LEO发送，长距离使用MEO进行转发。在数据量较大的情况下，会造成ISL堵塞，影响通信质量。引入QoS指标，进行时延受限下的负载均衡，从而实现流量工程对数据流量进行规划分配的目的。本算法的模型建立在该系统之上。

QoS是本模型关注的重点，针对QoS的度量因素有凹形受限、路径最优等思路。在卫星网络中关注QoS因素，主要是针对时延、带宽、吞吐量、丢包率等因素，通过选择链路条件，限制不稳定的连接情况，对节点的属性进行考虑而获得QoS性能提升。本文综合考虑多层卫星网络的特点，以节点带宽作为衡量节点忙碌的因素，以链路的代价衡量链路的繁忙和优劣性，建立QoS模型。

分析路由算法时，将多层卫星网络看做简单带权无向连通图G= （V，E）。V是图中所有交点的集合，E是图中所有边的集合。针对图化网络的元素度量方案如边长度、边权值、节点独立属性、节点网络属性及结合式等。本文选择边和节点结合的方式度量网络。设每条边的权值代表链路的代价，函数表示为cost （e）。设时延函数为delay （e），带宽函数为bandwidth （e），各参数的计算公式如下。

其中D表示从源节点R到目的节点S的一条可行路径，公式（5）（6）（7）中的D （p）、C（p）、B（p）分别表示该路径的时延、代价、最小带宽。时延的约束条件为D，带宽的约束条件为B。

当所选链路使用较少时时延短、丢包率低，但出于相对偏远位置，会导致时延较长：而过于关注时延，如使用最短路径等可能造成大量的数据堆积，严重损坏链路带宽和丢包率。因此引入链路代价函数，链路的代价综合考虑所选链路的带宽和链路长度，由时延、带宽组成代价函数，由系数wl和w2调节时延和带宽的敏感程度，wl+w2=1，通常各取0.5。时延相对于带宽很小，对带宽进行归一化处理。所选链路综合考虑带宽、丢包率，代价最小的情况下保证了带宽、时延处于平衡状态，其代价函数如公式（8）。

cost（e）=w1·delay（e）+w2·bind（e），e∈p

（8）

对于整条路径来说，通过不同状态下链路的平均长度估算链路的花费比较简单易行。对于walker星座来说，单层卫星内结构相对固定，不同轨道的卫星的分布具有规律性，因此针对固定的星座在大量通信的情况下对路径采用统计平均的方式是可行的。设所有可行路径的集合P={Ps，d （n）|n=1，2…N}，针对路径的花费函数公式见公式（9）。

时延主要由发送时延、传播时延、排队时延组成。在多层卫星网络中，传播时延是主要的影响因素。而排队时延由网络繁忙度U和节点传输速率T和包的平均大小P决定，排队时延D的计算公式如下。

公式中的S表示报文的处理速度，A表示卫星路由的处理速度，U表示节点繁忙度。较小的数据报文传输时，发送时延很短，可以忽略不计，因此总体时延T为传播时延与排队时延之和，如公式（11）。传播时延公式参数有链路长度L和传输速度V。

本文提出的算法是基于流量工程的最小链路代价算法，路径带宽受限而链路代价最小，在网络繁忙时流量不会过于集中，时延带宽和丢包率形成的代价花费最小，其模型如公式（12）。

该模型属于QoS常用的双度量参数——路径最优参数模型，即带宽受限约束，链路代价代价最小，该问题是线性规划问题。在两层网络中，上层网络对LEO的完全控制，管理全局信息，具有较大的带宽，因此可将模型计算过程分为TE-MSP算法启用前和启用后两种情况。

1.3 多层卫星路由方案

MEO和LEO每时每刻都在运动，两层网络的拓扑结构会随时变化，因此建立的路由策略必须考虑星间链路的改变。当卫星移动到链路边缘时发生断裂，此时会影响数据正常传输，建立路由时也需要考虑。

（1） LEO发送拓扑探测信息，获取流量矩阵

（2） MEO汇聚流量信息计算概率转移矩阵

（3） LEO接收到用户请求，将呼叫请求发给MEO，MEO根据流量公式和链路代价模型计算路径程，建立路由表项

（4） MEO将路由表项分发给LEO，LEO传给用户作为封装的包头

（5）用户开始传输数据

2 仿真结果分析

为了证明流量工程的流量管理功能，先设计如下仿真。对某次接入MEO的请求，当前端口的使用情况与请求响应的概率。其数据见图3。

如图3所示，当端口使用率小于0.5时，MEO的采用率下降平缓，峰值大于0.6，增加了MEO接入使用的机会。当端口使用率大于0.5时，MEO的接入概率下降速度加快，使用概率0.7时请求响应概率仅0.25，从而减少碰撞的发生。

为了验证本算法在LEO卫星间的流量管理功能，设计仿真如下，对某节点的链路使用OSPF算法和TE-MSP算法在一段时间内处理拥塞的情况。OSPF是典型的随机取路算法。其结果如图4。

如图4所示，在O.lmin处，OSPF算法的流量为30Mbps，而本算法为50Mbps。在流量较低的时候，OSPF算法按照概率取路，对本节点的时延、跳数等因素考虑不足，分配流量数低于本算法，对节点的利用效果不好。在时间为0.4min时，OSPF流量达到了90Mbps，而本算法的流量为80Mbps。而时间为0.6min时，OSPF算法的流量为98Mbps，TE-MSP算法流量为86Mbps。说明当流量增加造成拥堵时，OSPF算法任然随机分配流量，导致节点流量不减少，丢包率增加，通信性能不好。而TE-MSP算法通过转移概率公式调节流量，取得了12%的分流效果，减少了拥堵。

为了证明链路代价模型的先进性，本文对OSPF算法和TE-MSP算法在不同的链路利用率的时延进行了仿真对比。仿真结果如图5。为了进行仿真，需要对网络中的路径长度进行平均估算。OSPF算法所选择的路径总是最短，虽然传播时延较短，但是在网络繁忙的情况下，相对的排队时延会变长，从而影响路径的时延因素。在该网络场景中，OSPF算法只会经过LEO卫星传输数据。对6*6矩阵的LEO卫星来说，可以将路径的跳数进行平均估算。在本场景中，LEO的到最远节点的最近跳数是6，繁忙度超过50%后每增加10%需要增加一条冗余，因此最大跳数HOPmax是9，而最小跳数HOPmin为1。因此在计算传播时延时，以平均跳数5作为传播跳数。

图5为使用OSPF算法和TE-MSP算法的时延情况。当链路利用率在0.4-0.75之间，此时链路的传播时延起着更大的效果。OSPF算法的较短路径具有更少的时延。但随着利用率增加，超过0.75后，排队时延急剧增加，导致OSPF算法的整个时延已经大于TE MSP算法时延。说明场景处于繁忙状态时，TE-MSP算法的平均时延较短。

为了得出TE-MSP算法在不同环境条件下的链路花费，并验证该算法具有较小的链路代价，对OSPF算法和本算法在不同的链路利用率下进行了仿真。结果如图6。

链路利用率低于0.4时，两种算法区别不大。因此对利用率在0.4以后的情况进行分析。如图5所示，当利用率高于0.4后，TE-MSP算法把拥塞链路的数据通过MEO进行传输。在利用率为0.4-0.65之间，此时多余的数据不消耗太多的排队时延，此时传输时延占据链路代价的大部分，可以看到此时链路代价略高于最短路径算法。但随着利用率增加，TE-MSP算法把带宽控制在lOOOkhz左右，并通过转移数据减少排队时延，因此传播时延变长的对代价的影响减弱，当链路利用率>0.65时，TE-MSP算法的代价已经小于继续按照最短路径算法选路的代价。随着繁忙度增加，TE-MSP算法的效果增加，在峰值处代价减少23%。

本文首先对MEO端口使用率与请求响应情况的关系进行了仿真，以及LEO卫星在遇到大流量时本算法与OSPF算法的对比仿真，证明了本算法提出的流量公式的分流作用；然后仿真对比了本算法和OSPF算法在不同链路利用率的时延曲线，可以看出本算法在繁忙场景中控制时延增长的效果；最后仿真对比了两种算法的链路代价，证明了本算法在控制链路花费上的优越性。

3 总结

本文针对多层卫星网络的路由算法提出了基于流量工程的最小链路代价算法，本算法综合考虑QoS因素，比传统算法更合理，以时延、带宽形成链路代价函数，借助流量工程思想，通过流量转移概率限制链路使用率，从而使数据的传输代价降低，网络拥塞情况减小。通过仿真结果可知，在复杂的多层卫星网络环境中，本算法可以有效应对网络繁忙的情况，具有可靠的流量调节功能，减少网络时延，提高带宽利用率，满足业务的QoS需求。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。