软件定义卫星网络多控制器部署策略

陈金涛，梁 俊，郭子桢，肖 楠，刘 波

(空军工程大学 信息与导航学院，陕西 西安 710077)

传统的卫星网络架构垂直集成、相对封闭，在发展过程中遇到了许多难题，比如设备的更新升级困难、无法提供更细粒度的服务、设备间互操作性差、难以与地面网络融合等[1]。而软件定义网络(Software Defined Network，SDN)以其灵活、开放、可编程的特点被看作是解决上述问题的关键技术之一[2]。将软件定义网络引入卫星网络的软件定义卫星网络(Software Defined Satellite Network，SDSN)架构正在获得越来越多的研究和关注。在软件定义卫星网络中流表下发、资源分配等功能都由控制层来完成[3]，交换机只需完成数据转发和硬件配置，从而简化网络管理、提高资源利用率，并可通过网络的可编程性实现创新。低轨道卫星星座作为卫星网络的重要组成部分，其控制层的规划、控制器的部署是软件定义卫星网络必须解决的关键问题。目前已经发表了许多相关的研究成果，然而在这些研究中仍然存在被忽视的问题：① 由于卫星网络的网络尺度大，处理时延相对于传播时延小，因此在大部分软件定义卫星网络的研究中都直接忽略了处理时延的影响。然而在控制器处理能力不足或控制器负载不均的情况下，处理时延亦能够影响网络性能，简单忽略处理时延或是认为所有流请求在控制器中都需要相同的处理时间的做法显然是不合适的。② 大部分现有研究都忽略了软件定义卫星网络星间链路的状态变化对网络性能的影响。当卫星飞过两极地区时(纬度大于60度时[4])，为了防止互相干扰会关闭轨道间卫星链路，这种链路状态的周期性变化会带来网络拓扑的改变，需要在部署控制器时加以考虑[5]。③ 目前针对软件定义卫星网络控制器部署可靠性的研究还比较少。

文献[6]主要以开销为优化目标设计了软件定义卫星网络控制器部署模型，该模型全面地分析了控制器的状态同步开销、信息收集开销、流建立开销、网络重规划开销等并以改进的粒子群算法求解。然而该模型中没有加入对控制器处理能力的考虑，对可靠性的分析也不足。SoftLEO[7]策略将低轨道卫星按照轨道分为6组，选择6个纬度相近的节点作为每组卫星的控制器部署位置以减小控制器间的通信开销。然而由于对星间链路的状态变化考虑不足，在控制器进入两极时控制器的通信开销将显著增大。文献[8]同样按照轨道将卫星分组，并从每组中选出最靠近赤道且方向相反的两颗卫星部署控制器，整个网络共部署12个控制器。这种方案虽然考虑了卫星进入两极时轨道间链路关闭对网络性能的影响，却没有考虑链路的失效和处理时延。同时，这种部署方案要求卫星星座中所有节点均安装控制器模块且动态调整其开闭状态，网络状态变化时的重规划开销过大。文献[9]在部署控制器时将网络端到端时延和负载均衡指数作为优化目标，然而却只考虑了路径传播时延，也没有对部署方案的可靠性进行考虑。文献[10]采用双门限法定义控制器的负载状态并设计了交换机迁移算法以实现控制器负载的动态均衡，然而仿真所用拓扑较为简单，未基于卫星网络特点做针对性考虑。文献[11]以控制器与交换机的最短距离为指标开展了卫星网络扩展性研究，主要解决现有网络的扩展问题，未考虑网络初始规划方法。文献[12]详细刻画了卫星网络中流建立过程产生的时延，并以其为优化目标设计控制器部署方案，然而文中仅考虑了流建立时延而未考虑其他网络性能指标，也未考虑卫星链路状态变化。

在现有研究成果基础上，笔者在建立时延模型时加入处理时延，并且在建立轨道模型时加入了链路状态的变化使之更贴近实际。同时，设计了链路失效代价以概率的方法量化网络的可靠性。基于控制时延可靠性的控制器部署策略(Controller Deployment Strategy based on Reliability of control delay，CDS-R)共分为两步：首先在保证控制器分布均匀的情况下，尽量选择度中心性高的节点部署控制器，随后根据网络的业务和拓扑变化动态为控制器分配交换机；使用改进的粒子群算法求解控制器部署问题。仿真结果表明，CDS-R策略能够有效提高网络应对链路失效的可靠性，降低控制时延、负载均衡率指标，并且重构开销保持在合理范围内。

1 优化目标

运用图论知识可将SDSN网络描述为G=(V，E)，V、E分别为网络节点集合及直连链路集合。其他网络参数及其说明如表1。其中xk，j、cvj均为二进制变量，xk，j反映控制器与交换机连接关系、cvj反映控制器的部署位置，其具体取值方法如下式：

表1 网络参数汇总表

(1)

(2)

在进一步对网络指标进行定义前做如下说明：网络中所有节点(包括作为控制器使用的卫星节点)都具有交换机功能；控制器与交换机间的通信均在带内进行；为了避免过大的网络部署开销和网络重构开销，网络中仅部署有限数量的控制器且部署完成后不再调整控制器的开闭状态；采用时间片思想[13]处理动态变化的卫星网络拓扑，假定在一个时间片内网络拓扑及流量情况不发生变化，且网络控制域规划方式的调整仅发生在时间片切换时；只考虑网络中的链路失效，不考虑节点失效。

1.1 控制器部署位置选取

由于网络中部署控制器的数量有限且开闭状态固定，必须慎重地选择控制器部署位置，确保在不同的网络拓扑条件下控制器均能够较好地控制整个网络。同时在部署控制器时还应当充分考虑链路状态的影响。

定义1节点度中心性。度中心性是刻画节点重要性的最直接度量指标[14]，两极地区星间链路的关闭也能在度中心性上得到直观的反映。因此，度中心性是选择控制器部署位置的重要依据，其定义方法如下：

(3)

度中心性越优秀的节点与其他节点的直连链路越多，在发生链路失效时也有更大的调整空间。因此应当尽量选择度中心性高的节点部署控制器。

定义2最差距离。为了适应网络拓扑的周期性变化，控制器应当尽可能均匀地分布在网络中以保证在不同时间片内控制器均能较好地发挥作用。将最差距离定义为网络中交换机到控制器最短距离的最大值：

(4)

控制器的部署应当使得θ尽量小，以避免控制器分布过于集中导致某些节点距离控制器过远。

因此，选取控制器部署位置的优化目标为

(5)

即使控制器尽量均匀地分布在整个网络中，以减小交换机到控制器的最短距离，并通过优化节点度中心性选择直连链路较多的节点部署控制器，同时防止在同一时间片内控制器集中进入两极地区。

1.2 控制域划分

控制器部署位置确定后，需要为控制器合理地分配交换机以保证网络的性能。控制域的划分需要保证网络具有较小的控制时延，控制器间的负载分布尽量均匀，网络受链路故障的影响尽量小。

定义3控制器与交换机间控制时延。将交换机sj与控制器ck间的控制时延定义如下：

(6)

其中，右侧第1项为控制器处理时延，第2项为传播时延[15]，c为自由空间中光速。

由定义可知，当网络中控制器处理能力充足时，处理时延小于传播时延，控制时延主要受第2项影响；而当网络中控制器资源紧张时，处理时延对控制时延的影响力提升。结合上式，将控制器的控制时延定义为控制器与其控制域内所属交换机的控制时延之和，将整个网络的控制时延定义为控制器控制时延按照负载加权的平均值。

(7)

(8)

(9)

其中pk代表控制器ck的负载，其值为所有受该控制器控制的交换机流请求速率之和。

由于网络控制时延按负载加权得到，当网络负载不均衡时，网络控制时延主要受负载最大的控制器影响而使得整个网络的控制时延性能不理想，因此网络时延的定义同时也要求负载在控制器间均匀分配。

(10)

(11)

(12)

(13)

(14)

其中，α为单位长度星间链路的物理中断概率。值得注意的是，由于轨道间链路的反复开闭，轨道间链路应当比轨道内链路具有更高的单位长度物理中断概率。文中仿真中轨道内与轨道间链路α分别取0.002及0.003。

定义6链路失效代价。借鉴文献[14]同时结合卫星网络特点，将链路失效代价定义为链路失效后网络控制时延的增加量(可能是零)。该值反映了控制路径上的直连链路在部署方案中的重要性，链路失效代价越大，链路对网络控制时延的影响越大。

δl=T(G-el)-T(G) ，

(15)

其中，G代表原有网络拓扑，G-el代表el失效后的网络拓扑。

定义7可靠性系数。部署方案的可靠性系数定义为链路失效代价与链路失效概率乘积的总和。可靠性系数越小，网络链路失效对控制时延的影响越小。该值从概率的角度反映了网络应对链路失效的能力。

(16)

基于上述定义，可将SDSN控制域划分优化目标概括如下：

minδ，

(17)

(18)

(19)

∀k∈C，pk

(20)

∀j∈S，xk，j≤cvj，

(21)

(22)

优化目标为使部署方案的可靠性系数达到最小以提高网络部署可靠性。式(18)表示每个交换机只能受到惟一一个控制器管理；式(19)要求网络中没有空载控制器；式(20)表示控制器的处理能力应大于其负载；式(21)表示只有节点上部署了控制器才能管理其他交换机；式(22)限定网络中控制器数量为M。

2 求解方法

选择粒子群算法(Particle Swarm Optimization，PSO)作为求近似最优解的手段。粒子群算法是一种基于种群的随机迭代寻优算法。算法中并没有许多需要调节的参数，其将问题的解抽象为每个粒子的位置，通过适应度函数评价粒子位置的好坏，每个粒子具有当前位置、历史最佳位置和当前速度3种属性，具有效率高、执行速度快等优点，已经被广泛应用于工程、经济与科学领域[16-18]中。因此选择粒子群算法的理由如下：第一，算法规则简单，收敛速度快，容易实现；第二，算法已在地面软件定义网络的控制器部署问题中得到了较为充分的研究和应用。同时，采用惯性因子随迭代次数递减的粒子群算法以提升算法性能[19]。算法求解过程如下。

策略基于控制时延可靠性的控制器部署策略(CDS-R)。

输入：SDSN网络G=(V，E)，卫星业务流量f，控制器处理能力r，控制器数量M。

输出：控制器部署位置CLoc，控制域划分方式X。

① 随机生成控制器部署位置CLoc。

② 利用粒子群算法更新粒子位置。

③ 得到满足优化目标的控制器部署方案CLoc并作为下一步算法的输入。

④ 随机生成控制域划分方式X。

⑤ 利用粒子群算法更新粒子位置。

⑥ 得到满足优化目标的控制域划分方式X。

⑦ 输出CLoc、X。

3 仿真与结果

3.1 仿真环境建立

本实验利用STK 11.01进行卫星轨道的仿真和拓扑信息的采集，借助MATLAB 2016b进行算法仿真并对实验结果进行分析。为了使实验结果具有可比性，实验在相同条件下进行。由于Iridium[20]为最经典的低轨道卫星星座，且具有卫星间通信链路，本实验在Iridium拓扑下进行，拓扑参数如表2。实验在一个轨道周期内划分了若干个时间片，将不同时间片部署网络的性能取平均值作为最终的仿真结果。

表2 仿真实验拓扑参数

采用文献[21]设计的卫星业务模型用以模拟。该模型将地球表面分为288个区域，区域内每106个用户产生1 Mb/s流量，如果用户数不足106，其产生的流量也按照1 Mb/s处理。各个区域产生的流量不是固定不变的，而是随着当地时间的变化而变化，时间系数为

(23)

其中，ti代表i地区当地时间。每个区域与距其最近的卫星节点相连，卫星节点的源流量为与其相连的各个区域流量之和。值得注意的是，在SDN架构下，并不是所有的流量包都需要上交给控制器，只有无法与流表匹配的数据包会占用控制器处理资源，假设这部分流量的比例为10%[12]。交换机sj流请求速率计算方法如下：

(24)

其中，mi表示i地区用户数，n表示i地区由sj转发。

同时该模型还规定了ui到uj节点间流量计算方法，如式(25)，依据此式可计算得直连链路上的流量fl。

(25)

3.2 仿真结果分析

实验1控制器数量对网络部署的影响。本实验选取地面SDN网络部署策略中的k-center[22]策略、随机部署策略(Random Deployment，RD)及SDSN部署策略以文献[9]的部署方案(下文简称为NS)作为对比。k-center策略按照距离对节点进行聚类，并在聚类中心部署控制器；RD策略随机选取控制器部署位置并按照就近原则为控制器分配交换机；NS方案[9]以网络通信时延及控制器管理的交换机数量均衡为优化目标并利用NSGA-Ⅱ算法求解。为了便于对比，实验中单个控制器处理能力均取60 Mbit/s。

图1展示了控制时延、负载均衡率、可靠性系数这3种策略与控制器数量间的关系。随着控制器数量的增加，3种部署方式的网络性能均不断提高。CDS-R的控制时延、负载均衡率、可靠性系数均优于另外两种方案，按照对照方案性能与文中之差除以对照方案性能的计算方法，可得控制时延较对比方案降低至少34.84%(M=4时最少)、可靠性系数亦优于对比方案，负载均衡率更是降低了50%以上。这是由于k-center策略和RD策略作为地面SDN网络控制器部署策略，并不适应卫星网络环境，卫星网络业务时间、空间分布非常不均匀，而k-center策略和RD策略在为控制器分配交换机时没有考虑负载，极易出现按照距离将大量节点分配给同一个控制器的情况，造成控制器负载不均衡，控制时延增加。且很多流量较大的链路被作为控制链路使用，可靠性较差，一旦发生链路失效将严重影响网络性能。NS方案控制时延不够理想，这是由于该方案构建网络时控制器间距离对优化目标影响巨大，导致控制器分布相对集中。同时，NS方案通过控制的交换机数量约束控制器负载，然而由于卫星节点间业务差距较大，故NS方案负载均衡性能仍与文中方案有一定差距。k-center策略和RD策略性能不够理想也反映了SDSN中部署控制器时仅考虑节点间距离或传播时延是不够的。

(a) 控制时延

实验2CDS-R仿真性能与控制器处理能力的关系。本实验取M=6，由于k-center、RD等方案均为考虑控制器处理能力，故本实验仅展示了CDS-R仿真性能，如图2所示。

从图2可以看出，随着控制器处理能力的提升，网络的控制时延不断减小，而负载均衡率和可靠性系数稍有增加。分析式(7)不难发现，网络的控制时延受传播时延和控制器处理时延的共同影响。当控制器处理资源充裕时，控制器处理时延相对较小；控制时延主要受传播时延的影响，因此CDS-R在规划网络时将传播时延作为主要考虑因素；更多距离短但失效概率大的链路将出现在控制链路中，虽然造成了网络可靠性和负载均衡性能的降低，但仍远优于M=6时其他算法(见图2)。由于低轨道卫星节点处理资源优先，通常小于本实验所取数值，故CDS-R能够较好地适应卫星网络环境。

(a) 控制时延

实验3CDS-R与现有低轨道卫星星座控制器部署方案的对比。图3中的点分别代表了控制器数量为6时的CDS-R、控制器数量为12时的CDS-R、SoftLEO方案[7]以及从控制器选择策略(Slave Controller Selection Strategy，SCSS)(仅借鉴其控制器选择方法而不采用原文中的多级部署架构)[8]。结果表明，在相同情况下，CDS-R网络性能均优于对比方案。这是由于SoftLEO方案与SCSS方案均按照卫星轨道划分控制域，由于全球不同地区的巨大流量差异，各个控制器间的负载很难达到均衡。而且这种分配方法使得网络中部分卫星节点距离控制器很远，无法保证较小的网络控制时延，同时这也使得部分节点受链路状态的影响严重，一旦链路失效，网络性能下降严重，同样无法保证网络的控制时延可靠性。

图3 SDSN控制器部署方案的对比

图4反映了仿真时间内不同控制器部署方案的网络重构开销大小。网络重构开销计算方法参考文献[6]。由于SoftLEO方案为完全静态的控制器部署方式，故其重构开销为零。由图可知CDS-R策略的重构开销比SCSS小得多，在控制器数量同等情况下重构开销降低了约26.55%。这是因为SCSS方案中需要实时调整控制器部署位置，增大了网络重构开销。本实验未考虑设备制造与发射带来的开销，否则SCSS的开销将会更大。

图4 网络重构开销对比

4 结束语

针对现有SDSN低轨道卫星星座控制器部署方案中忽略处理时延、对网络链路状态缺乏考虑的问题，笔者将处理时延纳入时延模型，定义了网络可靠性系数以反映网络应对链路失效变化的能力，并设计了CDS-R策略完成控制器的可靠部署。仿真结果表明，该策略的控制时延、负载均衡率、可靠性系数等性能均较对比方案有较大提升，且重构开销保持在可以接受的范围内。但仍存在以下不足：① 仅考虑了控制器在低轨道卫星星座中的部署，未加入同步轨道卫星、卫星地面站考虑控制器的多层次部署；② 未针对优化目标设计相应的求解算法，而是在经典优化算法的基础上做简单调整改进；③ 仅以概率方法衡量了网络部署方法对网络可靠性的影响，未针对链路中断设计恢复策略。以上不足将在未来研究中加以研究改进。