基于QoS的卫星网络端-端通信可靠性分析

蔡睿妍，潘芸,*，魏德宾，石怀峰

1. 大连大学 通信与网络重点实验室，大连 116622 2. 大连大学 信息工程学院，大连 116622 3. 南京理工大学 自动化学院，南京 210094 4. 南京信息工程大学 电子与信息工程学院，南京 210044

对于广义上的卫星通信系统来说，其空间段的组成部分——卫星本身就是一个结构复杂功能多样的系统。传统的系统可靠性理论假设系统只有正常工作和完全失效2种状态，然而在卫星网络实际运行周期内，由于冲击、负载和老化等运行环境因素的影响使得卫星通信网络往往处于逐渐劣化过程中，相较于二态系统、多状态系统可靠性理论能更清楚地反映系统在使用过程中状态不断变化的规律[1-2]。早期对网络可靠性的研究主要是从网络拓扑结构出发来研究网络的连通性，并没有考虑网络完成用户需求的能力。目前，绝大部分对网络端-端可靠性算法都是基于最小路集来计算的[3-6]，这些算法的一般求解过程是：首先求出网络系统的最小路集，然后再利用容斥原理法或不交积和法计算网络端-端可靠性。

随着信息技术的发展和人们对卫星通信网络的业务要求逐步提高，网络的可靠性[7-11]一直是研究的热点问题。QoS(Quality of Service)对确保业务量不受延迟或丢弃、保证网络的高效运行起着至关重要的作用。Lin[12]提出将系统可靠性定义为在时间阈值T和预算带宽B下d单元数据从源发送到接收器的概率，以一种简单的下边界点生成算法为基础计算系统的可靠性。宋凤等[13]在传统不带路径约束的双端和k端网络可靠性研究基础上，提出了基于截断的路径约束方法，并根据该方法构造二元决策图(Binary Decision Diagram，BDD)模型进行带约束的k端网络可靠性分析。王秀君等[14]将网络中QoS约束指标指定为带宽和时延，通过链路不相交相似路由筛选来找到链路不相交的最短相似路由。乔晓东[15]提出一种考虑容量、时间以及可靠度约束的网络端-端可靠性计算，通过BDD不交化求出网络端-端可靠性。

以上现状并没有针对不同业务对可靠性进行分析，只考虑了部分QoS约束。由于卫星通信网络承担着多种业务，典型的有语音业务、视频业务、移动定位业务、图像下载业务等。业务类型不同，其对端到端传输时延、传输带宽等需求也有所不同。如何满足不同业务的QoS需求实现网络端-端可靠传输显得尤其重要。

在以往的最小路集和最小割集的算法中，端-端可靠性的计算都是基于单路径传输的。在多路径传输方面，Lin[16]为了缩短传输时间，使用允许数据同时通过多个最小路径发送的传输协议，将随机流网络流量从单路径传输扩展到2条及多条不交化路径传输的情况。为了解决使用具有不同延迟的不同路径导致相同流的数据包之间出现重新排序的问题，Yabandeh等[17]提出基于UDP(User Datagram Protocol)的方法尝试按顺序将数据传递给接收者，同时在接收者的应用程序上施加尽可能小的延迟和缓冲空间。仿真结果表明，多路径传输的性能与最优单路径相当。

在实际网络环境中，端-端多路径传输可以有效地聚合多条接入路径的带宽，从而使得网络获得更大的吞吐量，来满足业务对带宽的需求。属于同一业务的数据从多条路径传输，增加了从单条路径窃听数据进而尝试恢复初始数据内容的难度，提供了更好的数据私密性。而且多条端-端路径同时使用，可以根据网络中的拥塞状况动态地调整数据在不同路径的发送速率，从而实现在网络边缘处的负载均衡[18]。因此，多路径传输的可靠性问题也不可忽视。

综上，本文在卫星网络的多状态特性分析的基础上，针对业务QoS需求进行了网络端-端可靠性研究，即考虑链路的多状态和传输不同业务类型对网络可靠性产生的影响。本文中假设节点为正常工作状态。又因为多路径传输在卫星网络中广泛使用，在单路径可靠性研究基础上进一步对多路径传输的可靠性进行分析。结果表明不同类型的业务由于不同的QoS需求，可靠性并不相同，且网络多路径传输比单路径传输可靠性高。

1 基于MPSA的端-端可靠性分析

在经典的最小路集算法(Minimum Path Set Algorithms，MPSA)分析网络端-端可靠性的算法中，其基本思想是：先确定网络拓扑的源端和目的端,并写出网络的邻接矩阵和终点矩阵,再通过最小路集算法计算得出网络的所有最小路集，最后将这些最小路集通过不交化计算并代入各链路可靠性得出网络端-端可靠性的精确值。下面给出基于最小路集的端-端可靠性分析方法的相关定义[19]。

问题描述 设N=(V,E)是一个简单有向网络，V={v1,v2,…,vn}为节点集，E={a1,a2,…,am}为弧集。一个简单的双端网络如图1所示。

图1 一个简单的双端网络Fig.1 A simple two-terminal network

定义2 网络的终点矩阵Z=[zjk](1≤j≤n;1≤k≤n)， 其中，

且当j=k时，zjk=0。网络的终点矩阵反映了网络中每条弧的终点。

定义4 BDD是一种用来表达布尔逻辑函数的有向无环图，在BDD上搜索从根节点到叶节点为1的路径，即可获得不交化最小路集。如图1中以v1为源端、v4为目的端的端-端最小路集用函数,表示为f=a1a5+a2a6+a1a3a6+a2a4a5。根据BDD定义将函数f用BDD表示如图2所示。

图2 BDD不交化Fig.2 BDD minimization algorithm

则端-端最小路集不交化后为

定义5 端-端可靠性定义为在QoS约束下，将数据流从源节点成功传输到目的节点的概率。

2 端-端可靠性分析

2.1 业务分类

在实际网络运行过程中，由于不同类型的业务对QoS要求不同，传输业务满足QoS需求才是真正可靠。本文提出针对传输不同业务的约束条件(时延、带宽和丢包率)的不同，将传统的MPSA改进为适应不同业务QoS需求的算法，从而在网络可靠性的分析中，对不同业务进行差异分析。

根据不同业务对指标要求的差异，将业务分为3类，分别为时延敏感业务、带宽敏感业务和可靠性敏感业务[20]。时延敏感业务对时延指标较为敏感，要求具有较低的端到端时延。带宽敏感业务的特点是需要大带宽的链路进行传输，但不要求时延很快。可靠性敏感业务对端-端传输可靠性要求高，要求较小的网络丢包率。

2.2 相关指标分析

1) 时延。时延是指一个报文或分组从网络的一端传送到另一端所需要的时间。包括报文或分组在节点上被处理、从节点发出以及在节点间传播一定的距离而花费的时间消耗，即时延=处理时延+排队时延+发送时延+传播时延。本文仅考虑发送时延与传播时延。文中设Tmax为端-端最大时延约束，传输路径的总时延T应小于最大时延Tmax，否则此路径认为不可靠。

2) 带宽。带宽表示数据的传输能力，指单位时间内能够传输的比特数。文中设Bmin为最小带宽，传输路径中的每条链路带宽B应大于最小带宽Bmin，否则此路径不可靠。

3) 丢包率。在本文中，将链路误码率通过丢包率Ploss来表现，指的是一次数据传输过程中，由于网络拥塞、传输过程噪声较多等因素影响，导致数据校验时，数据包遭到破坏不能通过校验被丢弃与所传数据包总数的比值。文中设Pmax为最大丢包率，传输路径中的总丢包率P应小于最大丢包率，否则此路径不可靠。

4) 链路可靠度。规定的条件和时间内链路无故障工作的概率，反映链路完成规定功能的能力。

2.3 链路多状态分析

由于星间链路传输距离较长，以及通信链路所处传输环境的复杂性，通常伴随着较高的路径损耗，且传输过程中通信信息受到噪声及干扰的影响较多，使得链路的状态处于正常工作和完全失效2种状态之间的多个状态。

2.4 端-端可靠性算法

2.4.1 算法思想

本文算法的基本思想是针对卫星网络链路的多状态特性，根据传输业务的QoS约束找到对应网络状态下的最小路径集，对最小路集不交化处理再代入各链路可靠性计算网络端-端可靠性。

2.4.2 时延相关表达式

本文端-端网络时延由发送时延和传播时延2部分组成，相关表达式为

Tsend=packet/B

(1)

Ttrans=Llink/c

(2)

T=Tsend+Ttrans

(3)

式中：Tsend为发送时延；packet为文件大小；B为带宽；Ttrans为传播时延；Llink为链路长度；c为电磁波在信道上的传播速率。网络端-端时延为发送时延和传播时延之和。

2.4.3 算法步骤

基于业务QoS需求的端-端可靠性算法流程如图3所示，算法基本步骤为

图3 基于业务QoS需求的端-端可靠性分析流程图Fig.3 Flowchart of end-to-end reliability analysis based on requirement of service QoS

步骤2 邻接矩阵每一个元素代表着2节点之间的链路，将此时链路带宽与最小带宽比较，若链路带宽小于最小带宽，该元素设为0，更新矩阵A1，否则直接跳到步骤3。

步骤7 根据BDD定义将函数f不交化处理，代入各链路可靠度求得网络端-端可靠度。

3 算例分析

3.1 问题描述

将卫星运行周期Tp分成n个时间片[t0=0,t1],[t1,t2],[t2,t3],…,[tn-1,tn=Tp]。在每个时间片内，假定拓扑结构不变，且链路的切换和网络拓扑的变化只在时间点t0,t1,t2,…,tn-1时刻发生，一个时间片内的卫星网络拓扑如图4所示。

图4 卫星网络拓扑图Fig.4 Topology of satellite network

每条链路遵循统计独立的失效概率，各链路状态及其对应带宽如表1所示，每条边的状态概率分布及传输时间Ttrans和丢包率如表2所示，各业务的QoS需求如表3所示。

表1 各链路状态及其对应的带宽Table 1 Link states and their corresponding bandwidths

表2 链路状态数据Table 2 Data if link states

续表2 链路状态数据Table 2 Data if link states

表3 各业务QoS需求Table 3 QoS needs for each service

3.2 过程分析

根据表2链路状态概率生成一组网络状态(3,2,3,3,2,3,3,3,2,3,3,3,3,1)，以传输2 Mbit的文件为例，分别对文件为时延敏感业务、带宽敏感业务和可靠性敏感业务进行分析。

步骤1 根据图3得知此端-端卫星通信网络的源节点为v1、目的节点为v8,此网络的邻接矩阵为

A1=

终点矩阵为

步骤2 由2.4.3节算法步骤运算得知：对于时延敏感业务，此时满足QoS需求的可靠最小路集为{a1a4a9,a1a4a8a12}；对于带宽敏感业务，可靠最小路集为{a1a4a8a12}；对于可靠性敏感业务，可靠最小路集为{a2a5a12}。

步骤4 将各边的可靠度代入，即可求出网络端-端可靠性。此时，时延敏感业务端-端可靠性值为89.37%，带宽敏感业务为81.45%，可靠性敏感业务为76.95%。

3.3 结果分析

设置多组文件大小，重复3.2节运算步骤，本文算法结果如图5所示。

Lin等[12]中外学者没有考虑不同业务下的网络的端-端可靠性，在上述设定下，3种业务可靠性都相同。然而实际上从图5可以看出，3种不同类型的传输业务，在文件大小为2.5 Mbit时，时延敏感业务可靠性此时降为0，而带宽敏感业务和可靠性敏感业务此时仍具有高可靠性。可以看出在传输同等大小的文件下不同业务可靠性是不同的。本文算法显示，相同文件大小的情况下，传输业务类型的差异终将导致端-端可靠度的差异。并且，本文算法与最小路集算法相比只增加了if-else判断，没有增加for循环的次数，所以算法的时间复杂度依旧没变，但由于if-else判断删除了不满足QoS需求的链路，导致最终满足条件的最小路集里项数的减少，在BDD不交化处理时得到一定的简化，使得计算复杂度得到有效的降低。

图5 3种业务可靠性对比Fig.5 Comparison of reliabilities for three services

4 多路径端-端可靠性

多路径传输是指采用多条不相交的路径来投递分组以增加连接的容量和可靠性的机制。在3.2节最小路径集求解网络端-端可靠性的过程中，网络可靠性为所有可靠路径的概率和，但此时的路径是独立传输各种业务。本文在上述研究基础上，进一步对多路径传输可靠性进行了研究，与单路径的对比显示，多路径传输的可靠性得到了提高。

4.1 算法思想

在端-端网络中，找到源端到目的端的所有传输路径。网络多路径传输若要可靠，则需要每条路径时延都要满足需求，所有路径的总带宽大于需要的传输带宽。在每条路径时延、带宽满足的情况下，计算多路径可靠性，若可靠性满足要求，则多路径可靠，否则不可靠。约束公式为

(4)

式中：i为满足条件的路径集L中的路径；m为路径集L中的路径个数。由于每条路径带宽不同，传输时需要对每条路径应该承担的带宽大小进行分配。每条路径应该承担的带宽大小为

(5)

多路径传输时每条路径的发送时延为路径需要传输的数据带宽在当前可用带宽下的发送时延：

Tsend=B′i/Bii∈L

(6)

多路径端-端时延为所有路径的最大端-端时延：

T=Max{Ti}i∈L

(7)

4.2 可靠性分析

以图4网络为例，多路径传输时，满足时延敏感业务QoS需求的多路径是{a1a4a9,a2a5a12,a3a7a14}，满足带宽敏感业务QoS需求的多路径路集是{a1a4a9,a2a5a12,a3a7a14}，满足可靠性敏感业务QoS需求的路径是{a2a5a12}。多路径传输时，网络可靠性得到提高，时延得到缩短。

图6显示利用多路径并行传输2 Mbit文件，在不同业务下单路径与多路径传输时间比较。可以看出，时延敏感业务和带宽敏感业务多路径传输时，时延都得到了缩短。而由于可靠性敏感业务满足设定条件的路径只有一条，实际上仍然是单路径传输，所以时延没有缩短。

图6 多路径和单路径时延对比Fig.6 Comparison of delays for multipath and signal path methods

图7显示为传输时延敏感业务时，单路径和多路径端-端可靠性的比较。可以看出，在单路径传输时随着文件大小逐渐增大，时延敏感业务的时延需求渐渐达不到要求，单条可靠路径降为0，而多路径传输由于带宽增大，传输同样大小的文件的时延得到缩短，在单路径可靠性降为0时，仍保持着高可靠性。同理，带宽敏感业务和可靠性敏感业务随着传输文件的增大，单路径可靠性降为0时，多路径共同传输起到提高网络可靠性的重要作用。

图7 多路径和单路径可靠性对比Fig.7 Comparison of reliabilities for multi-path and single-path methods

5 结 论

1) 本文针对传统网络端-端可靠性分析中，计算网络端-端可靠性时没有体现传输不同业务的可靠性差异的问题，在卫星网络的多状态特性分析的基础上，通过案例模型分析了传输3种类型业务的可靠性。结果证明，该算法能很好地分析传输同样大小的文件时，由于业务类型差异导致的QoS指标差异从而带来的网络端-端可靠性的区别，比传统算法更贴近实际。

2) 由于端-端并行多路径传输在卫星网络上广泛使用，本文在上述研究的基础上，进一步对多路径的端-端可靠性进行了研究。研究结果显示多路径数据传输对比单路径传输时，端-端时延得到了缩短，可靠性在文件增大时得到了提高。本文的链路虽然有多个状态，但在实际运算中，只在一组已知状态下分析了网络端-端的可靠性，在接下来的研究中，将考虑根据状态概率生成的网络状态组合下的端-端可靠性。