航空信息网络服务功能链协同构建与映射策略

宋鑫康, 赵尚弘, 王 翔, 郝少伟

(1. 空军工程大学信息与导航学院, 陕西 西安 710077;2. 中国人民解放军93721部队, 山西 朔州 038300)

0 引 言

传统航空信息网络存在网络服务与专用硬件紧耦合的弊端,使其难以提供敏捷灵活的定制化服务;同时航空平台有限的设备承载能力,进一步制约了网络服务水平的提升。而网络功能虚拟化(network function virtualization,NFV)技术的发展将有助于改变部署专用设备提供服务的现状,可基于通用服务器借助软件实现虚拟网络功能(virtual network function,VNF),从而实现网络功能与专有硬件的分离。NFV技术与航空信息网络的结合可改变平台软硬件紧耦合的现状,实现对集群资源的细粒度管理和高效聚合。借助VNF可根据需求在不同位置上进行实例化的优势,按照不同任务的服务功能需求连接相应VNF构成服务功能链(service function chain, SFC),可充分发挥集群体系化作战优势。基于NFV技术的航空平台可依托通用服务器提供多样化网络功能,但作战任务的部署将面临所需服务功能逻辑顺序及部署位置未知的挑战,因此本文旨在解决根据作战任务服务请求构建SFC并进行高效映射问题。

SFC的构建过程需在保证服务功能间依赖关系的基础上将作战任务所需服务功能进行排列,而SFC映射过程需在满足资源需求条件下将作战任务请求映射至底层航空信息网络,因此SFC的构建与映射本质属于非确定性多项式难题(non-deterministic polynomial-hard, NP-hard)。作为5G网络性能提升的关键技术,目前相关研究均以地面网络作为研究对象,文献[7-8]聚焦于服务链映射问题,文献[6,9-13]综合考虑了服务链构建和映射过程。文献[6]基于改进粒子群算法获得服务链构建和映射方案,以服务链资源开销最小作为优化目标对构建和映射方案混合编码,可有效降低服务链的实际资源映射开销,但算法的时间复杂度较大。文献[9]提出了在线SFC联合构建和映射算法,基于当前节点不断选取有限跳数内服务功能以完成带宽需求最小的服务链构建,在确定服务功能类型基础上选择剩余计算资源最大平台进行映射。该方法在映射过程中未考虑链路负载情况,使得带宽资源极可能无法满足任务需求。文献[10]实现服务链构建与映射过程的相互协调,基于当前部署节点以贪婪策略选取后续服务功能,提高了成功映射概率,但未考虑底层网络状态,导致容易陷入局部最优。文献[11]以带宽资源最小化为优化目标,针对服务功能间3种不同依赖关系设计了相应的服务链构建和映射方法,但忽略了服务功能逻辑顺序的改变对所需资源的影响。文献[12]提出基于一种非协调方法来解决服务链构建与映射问题,采用启发式方法获得服务链构建方案,然后将映射问题表述为约束条件下的混合整数问题,该方法计算量大,适用于小规模网络。同时,由于两阶段为独立求解,所以联合结果没有得到进一步优化。

上述研究针对SFC构建和映射方案的求解相对独立,在构建与映射方案匹配关系不断调整过程中获得最优解。该方式在实现网络资源情况与服务链构建方案的相互协调方面时间开销较大,无法适应航空作战时延敏感特征。其次,相较于地面网络,航空领域战场复杂多变,任务请求得到快速响应的需求更加迫切。针对上述问题,本文提出了一种航空信息网络服务链协同构建与映射策略,区别于已有算法,所提策略基于映射平台资源状况确定服务链构建方案,极大简化构建和映射方案相互调整过程,减少了搜索时间开销,在有限时间内可获得较优方案,可实现任务请求的快速响应以及任务请求接受率的提高。所提策略借助启发式算法时间复杂度低的优势,基于改进蚁群算法以链路负载率为牵引确定服务功能的映射平台,应用广度优先搜索思想确定最佳服务链构建方案。

1 系统建模

1.1 网络模型

1.1.1 航空信息网络模型

112 作战任务请求模型

每项作战任务请求表示为=(,,,),其中和分别表示作战任务的初始平台和目的平台,和仅发挥数据发送和接收功能,忽略流量对服务模块计算资源的占用;表示作战任务所需的服务功能集合;表示初始平台所发送数据的初始带宽。

1.2 问题描述

121 SFC构建

SFC构建过程需在遵循服务功能间依赖关系的基础上将作战任务所需服务功能进行排列。由于各服务功能的流量改变率存在差异,不同的排列顺序会使得所构建SFC对服务模块计算资源和通信链路带宽资源产生不同需求。如图1(a)所示作战任务请求共需5种服务功能类型,同时虚线表示各服务功能间依赖关系,例如类型的运行以完成类型运行为前提;图1 (b)为基于作战任务需求得到的所有符合服务功能间依赖关系的SFC构建方案。如图1所示,不同的排列方式使得各服务功能所需计算资源和带宽资源需求存在差异,初始平台发送带宽需求为30 Mb/s的数据,由于服务功能的流量改变率为08,所以经服务功能后流量带宽需求转变为24 Mb/s。同时,服务功能的资源开销比为02,则相应服务模块需提供6 Mb计算资源。以此类推可得SFC1所示排列方式可实现对资源的需求总量达到最小,其对计算资源需求为35.45 Mb,对带宽资源需求为129.08 Mb/s。

图1 作战任务需求及相应的SFCFig.1 Operational mission requirements and corresponding SFC

1.2.2 SFC映射

SFC映射需将作战任务请求映射至底层航空信息网络,映射过程需确定SFC中服务功能及链路与航空信息网络中平台及通信链路对应关系,而平台所承载服务模块的计算资源和通信链路的带宽资源将直接影响服务链能否映射成功。对于服务链映射过程,不同服务链构建方案映射至相同平台和通信链路以及基于同一服务链选取不同平台及通信链路,均会影响服务链的实际资源占用情况。如图2所示,基于SFC1构建方案采取不同映射方式可能会影响服务链的映射成功率,若平台和间链路带宽无法满足需求,将导致方案1映射失败;同时所采取映射方案会影响平台和链路剩余资源,尤其对于关键链路的资源占用会影响后续服务链的映射成功率。

图2 服务链映射示意图Fig.2 Schematic diagram of service chain mapping

1.3 优化目标

作战任务请求的部署可分为SFC构建和映射两个步骤,本文旨在通过合理地构建及映射SFC,最大化作战任务请求的接受率,因此目标函数定义为

(1)

请求接受率为初始时刻到时刻映射成功的任务请求总数与到达的任务请求总数之比,其中num()表示截止时刻映射成功的请求总数,num()表示截止时刻到达的请求总数。约束条件如下:

(2)

(3)

(4)

(5)

(6)

(7)

C4～C6表示SFC映射过程中资源约束。C4表示服务功能所映射航空平台的服务模块需要有足够的计算资源。C5表示服务功能和间链路所映射通信链路需要有足够的带宽资源保证数据流量正常传输,在忽略流量分割情况下通信路径的最小带宽取决于所经过带宽最小的链路。6表示流量传输满足链路连通性约束,即除路径端点外,中间节点流入链路数量与流出链路数量相等。

1.4 评价指标

对于航空信息网络SFC协同构建和映射问题,除请求接受率指标外,考虑到作战任务的时延敏感特点和网络的资源利用情况,选取请求平均等待时间、资源利用率和映射资源开销作为评价指标。

1.4.1 请求平均等待时间

航空领域战场态势复杂多变,作战任务请求的快速响应有助于提高作战效率,保证作战任务的顺利完成。任务平均等待时间为截止时刻所有到达任务的等待时间之和与到达数量之比:

(8)

142 资源利用率

资源利用率为各时刻当前网络占用资源量与网络资源总量之比,本文从平台计算资源利用率和链路带宽资源利用率进行评价,如下所示:

(9)

(10)

SFC构建和映射方案可通过资源开销情况进行反映,资源开销为所占用计算资源与带宽资源的加权和,如下所示:

(11)

为协调计算资源和带宽资源在资源开销中影响比重而引入加权参数ϑ和,其取值分别为1和05。

2 算法设计

SFC构建与映射问题属于NP-hard问题,同时复杂多变的航空战场对算法的时间复杂度提出了较高要求。蚁群算法兼顾启发式算法在较短时间内可获得较优解特点的同时,具有鲁棒性强、并行分布式计算、全局搜索能力突出的优势,因此本文将蚁群算法用于确定服务功能与航空平台的映射关系,但考虑到算法存在收敛速度慢、局部搜索能力不强等劣势,针对其进行了改进以提升算法性能。其次,应用广度优先搜索算法确定当前映射资源条件下最佳服务功能排列顺序,即服务链构建方案,其中选取最短路径作为各服务功能间通信链路。

2.1 算法改进原理

2.1.1 解空间优化

转移概率是蚂蚁寻路过程中的关键指标,时刻蚂蚁基于航空平台到航空平台的转移概率如下所示：

(12)

传统蚁群算法各可行解设置相同信息素初始值,增强了节点选取的随机性,提高了算法的全局搜索能力,但也使得需要花费较长时间以发挥正反馈机制效果,进而导致了算法初期收敛速度较慢。结合服务链映射问题,在算法中引入链路和平台负载因子,在算法运行初期可缩小可行解搜索范围,以提高算法收敛速度。

链路负载因子:定义链路负载矩阵作为全局变量,记录各时刻航空信息网络中通信链路的负载情况,将有助于避免蚂蚁选取链路负载较大的通信链路。链路负载因子定义如下:

桩后土拱处于极限平衡状态时，邱子义等[12]、刘小丽等[18]认为土拱沿着K点水平方向发生破坏，如图7所示。图7中桩后均存在三角形受压区，左侧拱的桩后受压区为EFG，EF的长度t1为桩后土拱的厚度；K为EF的中点，即拱轴线与拱脚截面的交点。

(13)

平台负载因子:定义平台负载矩阵作为全局变量,记录航空平台各服务模块的计算资源占用情况,当服务模块计算资源占用超过所设定80%阈值时,将该服务模块从可行解空间删除,从而缩小可行解空间范围。链路和平台负载因子的设定,将有助于提高算法初期的收敛速度,同时选取资源相对充足的平台和链路利于任务请求的成功映射。

212 信息素更新

所提算法中对航空平台所承载服务模块赋予信息素属性,本文对信息素的更新策略进行改进以提高蚁群算法的收敛速度和算法运行性能。

(14)

(15)

2.2 算法实现

本文提出负载平衡服务链构建与嵌入(load balancing service chain construction and embedding, LBCE)算法,以链路和平台负载率为牵引,旨在实现SFC构建和映射过程中的负载均衡。算法首先以任务请求中初始平台为起点,综合考虑其他平台与初始平台间链路以及服务模块信息素情况,应用式(12)求解得到满足任务服务需求的各平台转移概率,依据转移概率选择相应服务功能映射平台,进而将所选平台作为起点依次完成后续平台的选择,从而完成蚁群初始化。其次针对各蚂蚁基于所选定航空平台利用广度优先搜索算法,从任务初始平台出发以服务功能依赖关系为约束,获得映射方案中后续可运行服务功能所对应平台集合,判断初始平台与集合中各平台间最短通信路径是否满足带宽需求,将满足需求平台作为当前平台以此类推寻找后续平台,直至到达目的平台,从而获得当前映射关系下满足功能依赖关系的所有服务链构建方案,将资源开销最小的方案作为该蚂蚁的行动路径。当所有蚂蚁完成路径选取后,记录全局最优方案及资源开销最优值,按照式(14)和式(15)完成各蚂蚁所选平台相应服务模块的信息素浓度更新。最后当蚁群算法循环满足迭代次数终止后,根据所得全局最优方案,更新平台和链路负载因子辅助后续服务链的构建与映射。

算法 1 LBCE算法输入: 航空信息网络G,作战任务请求M输出: 服务链构建与映射方案1: while n

24:end while25:/*平台和链路负载因子更新*/26:根据所得最优方案更新所选平台和链路负载情况。

3 仿真与分析

3.1 仿真设置

本文在Matlab仿真环境下对所提算法进行分析评估。航空信息网络的参数设置如下:场景区域为1 000 km×1 000 km,航空平台数量为50架,基于改进的Salam算法随机生成网络拓扑,网络中每条无向边设置为两条有向边,每个方向链路带宽服从[70,80]的均匀分布。借鉴文献[6],仿真设置如图3所示4种不同类型作战任务请求,各任务请求的源平台和目的平台随机产生,任务请求的初始流量服从[30,40]的均匀分布。仿真实验随机生成1 000个作战任务请求,其到达率服从λ=0.7的泊松分布,生存周期和服务周期分别服从μ=10、η=100的指数分布。为避免随机因素干扰,仿真实验共进行10次,取实验结果平均值作为最终结果。

图3 作战任务请求类型Fig.3 Combat mission request types

各航空平台仅可运行部分VNF,因此本文设置每个平台随机承载任意2～3种类型服务模块,各服务模块参数设置如表1所示。

表1 服务功能类型及其参数Table 1 Service function types and their parameters

文献[6]所提算法可有效降低SFC的资源映射开销,提高作战任务的请求接受率。文献[9]所提算法的时间复杂度较低,可满足作战任务快速响应需求。因此,将本文所提LBCE算法与文献[6]和文献[9]中算法进行对比,算法具体描述如表2所示。同时,对算法中种群规模和迭代次数进行限制以适应航空作战特点。

表2 算法描述Table 2 Algorithm description

3.2 结果分析

图4为不同作战任务请求数量下各算法请求接受率对比,相较于文献[6]算法和LBCE算法,由于文献[9]算法缺乏对可行解的迭代优化以及映射过程中未考虑链路负载情况,使得文献[9]算法映射成功率最低,甚至在仿真初期出现请求接受率直线下降问题。文献[6]算法由于采用服务链构建方案与映射方案不断匹配的方式进行求解,在迭代次数和种群规模有限条件下致使构建方案与网络资源的相互协调过程不够充分,无法有效降低所得方案的资源开销情况,导致映射成功率低于LBCE算法。LBCE算法在选定航空平台后应用广度优先搜索算法可确定当前资源状况下最佳服务链构建方案,从而降低了服务链构建和映射方案的资源开销,相比文献[6]和文献[9]算法请求接受率分别提高了约12.3%和46.2%。

图4 不同作战任务请求数量下请求接受率Fig.4 Request acceptance rate under different number of combat mission requests

图5为不同作战任务请求数量下各算法任务平均等待时间对比,任务的等待时间主要取决于当前航空信息网络资源情况,若当前网络资源状况可满足到达任务需求,则任务等待时间为0,否则任务会在生存周期允许范围内等待其他任务释放网络资源。文献[9]算法由于仅建立一种服务链构建和映射方案使得任务请求接受率较低,致使等待队列累积任务请求数量较多,导致其任务平均等待时间最长。文献[6]算法由于服务链构建和映射方案资源开销较大,当正在服务任务到达一定数量后网络剩余资源严重不足,无法满足后续任务需求,增大了任务的平均等待时间。LBCE算法在满足资源需求的同时可结合网络资源情况完成服务链构建,因此任务的平均等待时间较短,相较文献[6]和文献[9]算法任务平均等待时间降低了约12.1%和26.8%,可实现任务请求的快速响应。

图5 不同作战任务请求数量下请求平均等待时间Fig.5 Average waiting time for requests under different number of combat mission requests

图6和图7为各作战任务请求到达时刻航空信息网络的平台计算资源和链路带宽资源利用率,仿真初期,随着作战任务需求不断到达计算资源和带宽资源利用率不断增大。当网络服务任务数量接近饱和时,LBCE算法的平台计算资源和链路带宽资源利用率基本维持在41.8%和18.7%;文献[6]算法的平台计算资源和链路带宽资源利用率基本维持在37.4%和28.9%;文献[9]算法的平台计算资源和链路带宽资源利用率基本维持在29.4%和19.7%;LBCE算法由于可满足较多任务需求,其平台计算资源利用率较高,同时其以链路负载率和通信跳数为依据选取平台,可降低带宽资源开销。文献[6]算法可以满足较多任务请求,因此平台计算资源利用率较高,但可能存在所选平台间通信跳数过多问题,从而导致对链路资源利用率较高。文献[9]算法由于请求接受率较低导致平台计算资源和链路带宽资源利用率均不高。

图6 航空信息网络平台计算资源利用率Fig.6 Calculation resource utilization rate of aviation information network platform

图7 航空信息网络链路带宽资源利用率Fig.7 Link bandwidth resource utilization of aviation information network

图8为随机选取25组3种算法均成功映射的服务链,将其资源开销情况进行对比。由图8可知,LBCE算法所得服务链构建和映射方案资源开销最小,文献[9]算法由于对平台间通信跳数进行限制使得带宽资源消耗较少,因此大部分映射成功的服务链资源开销仅次于LBCE算法,而文献[6]算法由于存在平台间通信路径过长问题使得映射方案资源开销较多,少数情况资源开销优于文献[9]算法。

图8 服务链映射资源开销Fig.8 Service chain mapping resource overhead

表3对各算法成功映射服务链资源开销情况进行分析,由表3可知，LBCE算法可实现服务链构建和映射方案资源开销最小且稳定,文献[6]算法由于通信路径长度的随机性导致资源开销均方差较大,即资源开销波动性较大。同时,文献[9]算法由于搜索过程较为简单,算法平均时间开销最小,文献[6]算法由于涉及种群迭代及交叉、变异操作,算法平均时间开销最大,LBCE算法仅涉及蚂蚁种群迭代过程,平均时间开销介于两者之间。

表3 3种算法映射数据分析Table 3 Map data analysis of three algorithms

4 结束语

本文针对航空信息网络服务链构建与映射问题,提出了以平台和链路负载率为牵引的服务链构建和映射策略。研究结果表明,相比两种对比算法请求接受率分别提高了约12.3%和46.2%,任务平均等待时间分别降低了约12.1%和26.8%,服务链资源开销分别降低了28.3%和16.7%。算法在时间复杂度较低条件下可有效提高任务请求接受率，并降低服务链构建和映射方案的资源开销,实现任务请求的快速响应。然而,作战任务请求中初始和目的平台由于具有不确定性,使得服务链映射成功率以及各时刻计算资源和带宽资源的整体水平较低。因此,下一步研究重点考虑服务模块和已映射服务功能的动态调整问题。