基于多目标决策的LEO卫星网络多业务路由算法

2016-11-24杨力孙晶潘成胜邹启杰

通信学报 2016年10期

关键词：卫星网络路由时延

杨力，孙晶，潘成胜，邹启杰

（1. 大连大学信息工程学院，辽宁大连 116622；2. 通信与网络重点实验室，辽宁大连 116622）

基于多目标决策的LEO卫星网络多业务路由算法

杨力1,2，孙晶1,2，潘成胜1，邹启杰1,2

（1. 大连大学信息工程学院，辽宁大连 116622；2. 通信与网络重点实验室，辽宁大连 116622）

针对低轨（LEO, low earth orbit）卫星网络中，链路资源利用不均衡以及差异化业务的服务质量(QoS, quality of service)要求难以满足，容易导致网络整体运行效率降低的问题，提出了一种基于多目标决策的路由算法。将LEO卫星网络传输的业务定义为时延敏感、带宽敏感和可靠性敏感3类，采用本征向量法计算业务权值，并利用一致性比率判定所得权值可被接受，进一步，基于多目标决策理论，结合卫星网络节点与链路的实际状态与业务的具体要求，计算满足业务QoS需求的路径，从而实现LEO卫星网络的多目标动态优化路由。建立基于铱星网络系统的仿真实验平台，模拟网络时延、剩余带宽和误分组率等不确定特征，为随机产生的3类业务进行路由规划，仿真结果表明，算法在满足QoS约束的同时，能有效地均衡卫星链路的业务负载，而且在吞吐量等方面的性能均有较明显提升。

LEO卫星网络；QoS路由算法；多目标决策

1 引言

随着卫星网络技术的不断发展，低轨卫星系统已能较好地实现全球移动通信。具有星间链路的 LEO卫星网络能实现全球覆盖，并且与地球同步轨道(GEO, geosynchronous earth orbit)卫星网络相比，它能够有效降低传输时延，减少卫星对地面节点的依赖，并能够更好地支持地面移动终端。但 LEO卫星网络不同于一般的地面网络，它具有高误码率、长时延等空间通信的特点[1,2]，与此同时，卫星网络业务类型不同，其对端到端传输时延、传输带宽等服务的需求也有所不同，因此，卫星网络中不仅要满足不同业务传输的QoS参数要求，而且还需尽可能地提高网络传输效率，充分利用网络资源。而针对 QoS所提出的路由，无论是按需路由还是流量分配路由，大多都是考虑某一种或2种链路属性来决定，从而忽略其他约束条件，这样容易导致网络的局部负载过大。因此，路由算法需要在兼顾多约束条件的情况下,尽量平衡地利用网络资源[3～5]。

2 相关工作

根据卫星网络动态拓扑可预知性和周期性的特点，路由算法可以采用一些拓扑控制机制来屏蔽其拓扑的变化，本文是采用基于离散化的虚拟拓扑将系统周期划分时间片，再对静态的序列计算路由。

目前，有关 LEO卫星网络的路由算法中考虑链路状态特征的算法有以下几种。文献[6]提出一种应用于节点的精确负载均衡(ELB, explicit load balancing)策略，它根据下一跳链路的时延，当节点出现链路数据拥塞时，发送信号给邻居节点，邻节点选择次优路径，从而减少网络拥塞。文献[7]提出了一种受限最短路径优先(CSPF, constraints shortest path first)算法，这是一种改进的最短路径优先算法，它为了避免网络或节点拥塞，将链路带宽的反比定义链路权重，根据业务的特定要求，在链路状态数据库的基础上，得到最终最短路径。多路径 QoS路由(MPQR, multi-path QoS routing)算法[8]是当卫星收到传输请求时，计算同时满足时延和带宽限制的最优路径。

此外，考虑QoS业务分类的算法有以下几种。根据业务分类，文献[9]提出一种多服务按需路由(MOR, multiservice on-demand routing)协议，它单独对各类服务流量进行路由。文献[3]提出一种多业务类QoS路由 (MQoSR, multi-class QoS routing)算法，该算法根据时延和带宽将业务分为2类，利用相对空闲链路来减少链路拥塞。由于这些算法有的只考虑链路状态信息，有的只考虑到业务分类，而没有将这两者结合起来，没有针对当前业务和实时的链路状态为业务选择合适的路径，这样很难保证卫星网络资源整体利用率。

针对上述问题，本文提出一种基于多目标决策的 LEO卫星网络多业务路由算法。该算法评价了各链路的通信属性：时延、剩余带宽、误分组率，计算了不同业务的通信属性权重；利用多目标优化决策模型，选择适合业务特征的通信节点作为路由目标对象；最后，本文对该路由算法进行了性能的仿真实验。

3 相关概念

3.1 QoS介绍

QoS的定义最早是由国际电信联盟（ITU,International Telecommunication Union）提出的，即服务性能的综合体现，它所反映的是网络对用户所能提供的端到端服务的各种参数描述[10]。由此可知，为业务提供可靠的端到端服务相关的质量保证是 QoS的目标，而这意味着不同业务具有不同的性能需求，即QoS指标。

常用的网络通信链路和路径的基本 QoS指标有带宽、时延抖动、分组丢失率等，它们度量函数的特征可以分为：凹性参数、可加性参数和可乘性参数。为便于描述，用w( e)表示链路的某个QoS指标值，w( p)表示路径的相应某个QoS指标值，则QoS的相关度量参数分类和计算规则如表1所示。

表1QoS参数分类和计算规则

3.2 LEO卫星网络模型

LEO卫星网络的高速运动导致拓扑不断变化，相比地面网络，其路由机制将面临如下限制：1) 随着业务增多，多种业务的数据分组难免经过相同的卫星节点，从而对网络时延和吞吐量等性能产生影响；2) 星上处理和存储资源十分受限，充分利用资源势在必行。同时，LEO卫星网络也有可预知性、周期性、恒定性等。基于上述特点设计路由算法时，建立 LEO卫星网络模型既要描述通信节点之间的关系，又要能够计算各节点的流量。

定义 1用G( V, E)来表示卫星网络拓扑基本模型。其中，V=M×N表示在星座中共有分布于M条卫星轨道，每条轨道有N颗卫星，E代表卫星之间的星间链路（ISL），用Ek表示节点i到j的边集，其中，i, j∈V。

定义 2用ws,d表示网络中所有可能的源、目的（SD）节点对，则代表一条路径序列，是SD节点之间通过K条链路连接。

为了表示单个链路上的流量，令链路包含函数为

其中，若路径经过链路Ek则取1，反之取0。用C表示每个节点向其他节点发送的数据分组数量，则某个路径上的流量计算式为

3.3 多目标决策问题

多目标决策问题是指在一定数量的备选方案上进行偏好决策，如选择、排序、评价等，并且其决策过程考虑多个具有矛盾性且衡量标准不统一的目标的评价。此类问题由可行方案、目标集、偏好信息、权重以及决策单元组成。

由yij构成决策矩阵，选择适合的多目标决策方案，获得当前最优解x′，满足偏好序

可见，卫星网络多业务路由问题就是一个多目标决策问题，它适合采用多目标决策理论优化路由过程。

4 算法描述

本文算法的基本思想是：针对卫星网络拓扑结构动态特性，考虑不同业务的 QoS要求，根据链路的时延、剩余带宽和误分组率定义计算不同的权值系数，并建立多目标优化模型，对约束条件和目标函数进行确定，通过求解与理想链路最接近的链路得到最优路径。

4.1 问题定义

根据数据语音视频等多样化的业务的 QoS要求，本文把业务划分成3种：A类是实时业务，即时延敏感业务，如对时间要求高的指令语音等；B类是可允许一定时延，即带宽敏感业务，例如对地观测业务；C类是可靠性敏感业务，主要体现在对误分组率要求较为苛刻的业务上[11]。在此基础上对业务的优先级进一步规定，本文暂且定义 A类业务高于B类业务，B类业务高于C类业务。

因此链路的总时延

剩余带宽

误分组率

定义 3多业务路由的多目标决策问题 P，是指在可行链路域中，根据当前链路状态以及业务QoS要求，如何获得最优链路v′。即

图1网络拓扑及其抽象

4.2 基于业务特征的权值计算

解决多目标决策问题各目标之间矛盾性的关键在于权值系数的确定，本文算法运用本征向量法。由决策人把n个属性的重要性成对比较，把第p个属性对第q个属性的相对重要性记为αpq，并认为它就是属性p的权wp和属性q的权wq之比的近似值，个目标成对比较的结果形成矩阵A。

定义4基于业务特征的权重是指把第1个属性时延的权w1和第 2个属性剩余带宽的权w2之比记为α12，第2个属性剩余带宽的权w2和第3个属性误分组率的权w3之比记为α23，以此类推，构成决策矩阵。则

其中，Ι是单位矩阵，若矩阵Α中的值估计准确，上式严格等于 0，若估计不够准确，则Α中元素的小的摄动代表本征值的小的摄动，于是有

其中，λmax是矩阵Α的最大本征值。可以根据该式求得本征向量即权向量

为了判定矩阵Α在此方法中的科学性，引入一致性比率[12](CR, consistence rate)的概念，它用一致性指标(CI, consistence index)与随机指标(RI,random index)的比值来表示，可以用来判定矩阵Α是否被接受。其中，，对于阶数为n的矩阵对应的RI值如表2所示。

若 CR＞0.1，说明各元素αpq的估计一致性太差，应重新估计；若CR＜0.1，可认为αpq的估计基本一致，可用式(3)求得w。

表2阶数为n的矩阵对应的RI值

4.3 求解

在路由选择的开始阶段，首先根据卫星网络的拓扑结构进行时间片划分，针对不同的业务分类计算权值系数，对可行链路运用优选法[13]对链路集合进行筛选，淘汰一些处于劣势的链路方案，得到筛选后的链路集合在路由过程中，对可行链路进行针对不同业务的矩阵评估，然后求出目标函数的理想链路，在路径集中找出最接近理想链路的路径从而得到问题的帕累托最优解。

对于 LEO卫星网络多业务路由决策问题的求解基于以下定义。

定义 5业务需求下的理想链路，是指可行链路域V′中，链路 v*的各项属性满足或，其中，，则称 v*为理想链路。

假设这个多目标决策问题有很多条链路可选，作为可行链路域，在约束条件内，根据不同的业务类型，对于 A类业务，有链路，分别都满足时延、剩余带宽和误分组率的要求，则称为多目标绝对最优链路，绝对最优链路构成链路集合，链路集存在一个理想链路，满足

定义 6实际通信链路的性能与理想链路性能的差异是指2条链路属性向量的加权欧氏距离。

其中，w1, w2,…,wn即为n个目标函数的权值，满足

本文算法的约束条件是确保某2个节点之间有且只有一条路径，表示为

本文算法具体流程如下。

Step1卫星 s接收到数据传输要求，目的节点为d。

Step2获取拓扑结构时间片，业务需求时延为a1，带宽为a2，误分组率为 a3。

Step3筛选可行链路集合V，得V′，根据业务分类建立链路评价矩阵Α。

Step4判断理想链路*v是否存在，如果存在求解结束。

Step5如果理想链路不存在，求最接近理想链路的路径vi，作为下一个通信链路。

为能够进一步清晰描述负载均衡能力，引入负载分布指数[11]

其中，n为LEO卫星链路总数；xi表示经过第i条链路的数据分组数量； f∈[0,1]，表示网络中的流量均衡情况，f值越大表明负载越均衡。

本文算法的时间复杂度分析如下。由于针对每个节点需计算 3个属性值，时间复杂度O( kn)，k=3；同时还要计算链路的加权欧氏距离，即O( n2)；因而时间复杂度为O( n2+kn)，其中，k是需要评价的节点属性数量，最终算法时间复杂度为O( n2)。

5 仿真结果和性能分析

5.1 仿真设置

为了验证所提出路由算法，仿真以 Iridium星座建立网络模型，即用66颗LEO卫星和8个地面站构建网络拓扑。考虑到卫星空间环境的复杂性，为了保证选择数据的多样，在每个轨道面上选择4颗卫星，并且满足处于同一轨道的2颗卫星之间间隔一颗卫星，做到均匀分布，记录这 24颗卫星的带宽、时延等相关参数，从而提高仿真的可靠性，网络模型参数如表3所示。本文算法运行于星上，在仿真中所有带宽请求将在5对源—目的节点对之间随机产生。地面站随机产生业务，每个地面站发送数据的速率为1.5 Mbit/s，对于3种业务约束条件具体参数指标如表4所示。由于仿真实验的随机性，对源、目的节点之间的数据传输进行了10次实验，以下每个仿真的数据都是10次实验结果的平均值。

表3LEO卫星网络参数

表4QoS参数

总的带宽请求次数从100到1000之间递增。

在仿真中，定义时延权值为w1，剩余带宽权值为w2，误分组率权值为w3，通过比较 A类、B类和C类业务中不同属性的重要性，根据本征向量法求得的权向量如表5所示。

表5仿真属性权值设置

根据 3种属性权值设置计算得：CRA=0.07，CRB=0.03，CRC=0.05，均小于0.1，因此权向量估计可被接受。

5.2 不同QoS业务路由性能对比

当网络中 A、B、C 3类业务同时存在时，在源节点和目的节点相同的情况下，3类业务的传输效率对比如表6所示。

表6业务传输效率参数

从表6可看出，同样的链路状态下，3类业务会根据需求不同选择不同路由线路，A类业务时延最短，B类业务平均带宽最大，C类业务误分组率最低。

5.3 多目标业务路由性能分析

选择2个现有先进的典型路由算法与本文提出的算法进行比较，一个是 2014年提出的只考虑链路状态特征的ELB算法，一个是2009年提出的只考虑 QoS业务分类的 MOR算法，比较从路由开销、负载分布指数和吞吐量3个性能方面进行。

图2所示为当负载状态不一样时，不同路由算法产生的路由开销。

图2网络的路由开销

如图2所示，这3种路由算法的路由开销都随着负载的增加而增大。但是，随着负载的加重，本文算法的路由开销比其他2种路由算法低，最多低3%。其原因在于当处于高负载时，其他2种路由产生了数据分组的簇拥和集聚，导致部分拥塞，所以需要消耗更多的数据分组。而本文算法中最优化模型综合考虑了时延、剩余带宽和误分组率3个因素，可以达到均衡网络负载的目的，并且节省了路由开销。

图3所示为随着负载状态的增加，不同路由算法的负载分布指数情况。

图3负载分布指数

如图 3所示，本文算法的负载分布指数与MOR算法和ELB算法相比更高一些，这是因为本文在考虑当前链路特征的同时对业务进行分类，将二者结合起来，能够有效避免拥塞，仿真结果进一步验证了本文算法有利于均衡网络负载。

图4所示为本文路由算法与MOR和ELB算法在吞吐量上的性能比较。

图4网络的吞吐量

就网络吞吐量性能而言，由图4可以看出，在带宽请求次数为100到400之间时，本文算法略优于MOR算法，优于ELB算法。当带宽请求次数在400到1000之间时，本文算法与MOR和ELB算法相比有较大优势，并且随着带宽请求次数的增加，吞吐量也在持续增加，并且请求次数在800到1000之间，本文策略的吞吐量趋向平稳，相比MOR算法吞吐量增加了 16%。综上所述，本文策略在吞吐量上都要优于MOR和ELB算法。

5.4 与其他现有算法比对结果分析

下面是本文路由算法与WSP算法[15]、CSPF算法等其他路由算法的性能比较。

图 5是 4种路由算法的负载分布指数变化情况，随着负载的加重，本文算法的负载分布指数一直保持较高的状态，这是因为当负载状态变化时，本文的最优化模型能够将更多的链路作为路径选择，不会将路径局限在某些节点上，所以它的负载分布指数最优。

图5负载分布指数

图6是4种路由算法的网络吞吐量结果。可以看出，在带宽请求次数为100到200之间时，4种算法的吞吐量都比较接近，且本文算法略优于其他算法，随着带宽请求次数的增加，WSP算法相比其他算法性能较好，但整体相比，本文算法吞吐量始终最大，说明本文提出的算法在吞吐量指标上具有较明显提升。

图6网络的吞吐量

通过仿真可知，与ELB、MOR算法相比，本文算法将链路特征状态和业务QoS分类二者结合起来，在负载增多的情况下，负载分布指数提高了近 10%，路由开销小，吞吐量增加了 16%，与WSP、CSPF、MQoSR算法相比，负载分布指数和吞吐量都相对较高，使卫星网络整体性能得到提高。

6 结束语

本文针对 LEO卫星网络中，链路资源利用不均衡、不同业务与其对应的服务质量要求匹配性考虑不足的问题，提出一种基于多目标决策的业务路由算法。该路由算法建立可行链路集合的多目标决策模型，利用 QoS需求设置不同链路属性的权重集合，进而通过理想点法求解多目标决策问题，最终获得适合业务需求的路由节点。

仿真实验结果表明，本算法较其他典型算法路由开销更小，并且在高负载情况下，负载分布指数以及吞吐量方面均有明显的优势。从而，本算法解决了QoS业务需求与LEO卫星链路属性相结合的业务路由问题。

[1]FATIH A, OMER K, ABBAS J. Exploring the routing strategies in next-generation satellite networks[J]. IEEE Wireless Communications,2007,14(3):79-88.

[2]LI J, YE G Q, ZHANG J, et al. A routing algorithm satisfied ground station distribution constraint for satellite constellation network[C]//Science and Information Conference (SAI). 2015.

[3]WU Z, HU G, JIN F, et al. Agent-based dynamic routing in the packetswitched LEO satellite networks[C]// Wireless Communications amp; Signal Processing (WCSP), 2015 International Conference. IEEE, 2015.

[4]JIANG W J, ZONG P. QoS routing algorithm based on traffic classification in LEO satellite networks[C]//Paris: Eighth International Conference on Wireless and Optical Communication Networks (WOCN).2011.

[5]LU Y, ZHAO Y J, SUN F C ,et al. Routing techniques on satellite networks[J]. Journal of Software, 2014,25(5): 1085-1100.

[6]QUAN L, NGO-QUYNH T, MAGEDANZ T. RPL-based multipath routing protocols for internet of things on wireless sensor networks[C]//Advanced Technologies for Communications (ATC), 2014 International Conference. IEEE, 2014.

[7]JAUHARI A S, KISTIJANTORO A I. INET framework modifications in OMNeT++ simulator for MPLS traffic engineering[C]//Advanced Informatics: Concept, Theory and Application (ICAICTA), 2014 International Conference. IEEE, 2014: 87-92.

[8]RAO Y, WANG R C. Performance of QoS routing using genetic algorithm for Polar-orbit LEO satellite networks[J]. AEU-Int’l Journal of Electronics and Communications, 2011,65(6):530-538.

[9]PAPAPETROU E, KARAPANTAZIS S, PAVLIDOU F N. Multiservice on-demand routing in LEO satellite networks[J]. IEEE Trans. on Wireless Communications,2007,8(1):107-112.

[10]代志勇. 业务分类体系下的 QoS路由研究[D]. 南京: 南京邮电大学, 2013.DAI Z Y. Research on QoS routing in service classification system[D].Nanjing: Nanjing University of Posts and Telecommunications, 2013.

[11]TALEB T, MASHIMO D, JAMALIPOUR A, et al. Explicit load balancing technique for NGEO satellite IP network with on-board processing capabilities[J]. IEEE/ACM Transactions on Networking, 2009,17(l):281-293.

[12]岳超源. 决策理论与方法[M]. 科学出版社, 2003.YUE C Y. Decision making theory and methods[M]. Sciences Press,2003.

[13]郭得科. 基于Kautz图和Bloom滤波的对等网络研究[D]. 长沙: 国防科学技术大学, 2008.GUO D K. Research on peer-to-peer networks based on Kautz digraph and bloom filters[D]. Changsha: National University of Defense Technology, 2008.

[14]KINSY M A, CHO M H, SHIM K S, et al. Optimal and heuristic application-aware oblivious routing[J]. IEEE Transactions on Computers, 2013, 62(1): 59-73.

[15]刘暐. 一种新的双层卫星网络路由算法性能仿真研究[J]. 计算机仿真, 2014, 31(4): 118-122.LIU W. Research on performance simulation of novel routing algorithm for double - layered satellite networks[J]. Computer Simulation,2014, 31(4): 118-122.

LEO multi-service routing algorithm based on multi-objective decision making

YANG Li1,2, SUN Jing1,2, PAN Cheng-sheng1, ZOU Qi-jie1,2
(1. Information and Engineering College, Dalian University, Dalian 116622, China;2. Communication and Networks Key Laboratory, Dalian 116622, China)

In low earth orbit(LEO) satellite networks, in view of the unbalanced link resource, it's difficult to meet differentiated quality of service(QoS) requirements and easily lead to reduce the efficiency of the whole network. A routing algorithm based on multi-objective decision making was proposed which defined LEO satellite network transmission service as the delay sensitive, sensitive bandwidth and reliability sensitive three categories. It used the eigenvector method to calculate service weights, and used the consistency ratio to determine whether it can be accepted. Based on the multi-objective decision making theory, it combined with the actual state of satellite network nodes and links and the specific requirements of the business, calculating the path that meets the QoS requirements of the service, so as to realize the LEO satellite network multi objective dynamic routing optimization. Established simulation platform based on the iridium network system simulated network delay, the uncertain characteristics like the residual bandwidth and packet error rate, route planning for the randomly generated three classes of business. The simulation results show that, the algorithm not only satisfies the QoS constrain while balancing the traffic load of the satellite link effectively, but also improves the performance on the throughput.

LEO satellite network, QoS routing algorithm, multi-objective decision making

The National Natural Science Foundation of China (No.61301151, No.91338104)

TP393

10.11959/j.issn.1000-436x.2016192

2016-01-30；

2016-09-03

国家自然科学基金资助项目（No.61301151, No.91338104）