航空信息网络集中控制器部署优化策略研究*

冉金鹏，赵尚弘，王 翔

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

1 引言

航空信息网络是指利用可用的无线通信链路和适当的组网机制将各个航空平台、传感器等链接形成的信息化网络系统，具有高动态、覆盖广、重负载、多任务等特点[1-2]。当前提出的航空信息网络架构大多遵循传统的网络架构和服务模式，主要是基于信息传输的可靠性和稳定性等方面考虑，与业务应用不具备灵活的耦合关系，导致网络难以实现互联互通，且网内各种协议体制采用封闭式设计，缺乏开放性，上述特点使得现阶段航空信息网络管理起来十分复杂且效率低下[3]。

软件定义网络（software defined networking，SDN）[3]的出现正好解决了上述的一系列问题。SDN 使数据平面与控制平面分离，突破了原网络中两平面紧密耦合的部署方式，采用逻辑集中的控制器对数据分发、转换设备进行统一管理，使执行任务的各物理设备可以独立完成相应功能。因此，有学者考虑将SDN 技术引入航空信息网络，利用SDN 技术优势进一步优化航空信息网络性能，提出一种基于SDN 思想的新型航空信息网络架构，即软件定义航空信息网络[4]。本文侧重于研究软件定义航空信息网络架构下的控制器优化部署问题，对具体架构内容不再做过多赘述。

软件定义航空信息网络中控制器的部署对全网的运转起着“金字塔”顶端式的核心控制作用[5]，其处理能力直接决定了整个网络的性能好坏。因此，控制器的优化部署问题成为软件定义航空信息网络领域的热难点。多控制器部署问题主要包括两方面，控制器部署的位置以及相应所需的控制器个数。控制器部署的位置反映了控制器与网络节点之间的映射关系，须兼顾全网平均时延、网络管理复杂度以及各控制器之间的负载均衡；所需的控制器个数则直接关系到网络的健壮性和成本开销，多个控制器协同部署可有效提升网络稳定性和可扩展性。综合考虑时延、可靠性和负载均衡对网络性能的影响是控制器优化部署要解决的核心问题，这是一个典型的NP-hard（non-deterministic polynomial hard）问题[6]。

文献[6]基于贪心算法进行求解，采用控制器与交换机间平均传输时延和网络零故障率时最坏传输时延等两个性能指标研究问题，有效解决了控制器部署的位置和数量问题，但未考虑可靠性、网络开销及负载均衡等问题。文献[7]综合考虑传播延迟和负载均衡，提出了网络聚类粒子群优化算法（network clustering particle swarm optimization algorithm，NCPSO），通过生成具有高聚类效率的多样化个体并克服离散问题中使用的粒子群算法的缺点，减少了控制器放置的数量，具有良好的负载均衡性能。文献[8]以最小化SDN 控制路径平均故障率为优化目标，提出了几种网络可靠性的度量和优化部署算法，并使用真实的网络拓扑进一步评估量化控制器位置及数量对控制网络可靠性的影响。但是同时以全局平均时延、网络可靠性以及控制器负载均衡为优化目标的相关多目标组合优化问题却少有研究。

基于上述分析，本文在基于控制器部署负载均衡基础上同时考虑全局平均时延和网络可靠性，将改进的蝙蝠优化算法引入到软件定义航空信息网络多控制器部署问题中，建立了多目标整数规划模型，并采用改进算法对模型进行迭代求解。

2 控制器部署问题模型设计

本文在满足软件定义航空信息网络特殊环境需求的前提下，综合考虑网络时延、可靠性和均衡问题，构建了控制器部署问题多目标组合优化模型，具体描述如下：

（1）软件定义航空信息网络用无向图G(V,E)表示，其中V表示网络拓扑中节点集合，V={v1,v2,…,vn}，vi表示一个网络节点，|V|=n为节点个数，1 ≤i≤n；E表示连接各网络节点的链路集合。

（2）定义Vl⊆V为部署在网络中的控制器集合，Vl={vl1,vl2,…,vls}，vld表示一个控制器及其部署位置，|Vl|=s为控制器部署的个数，1 ≤d≤s。

（3）网络中每个节点表示一个交换机，本文中统称为传输节点。另外，假设网络中一个传输节点仅受唯一控制器控制，而控制器可以管理多个传输节点。控制器部署在传输节点上，即与交换机处于同一位置，此时可认为两者的时延和中断概率都为0。

（4）假设网络中节点和链路相互独立，互不影响，即节点故障并不影响链路性能。反之，链路故障也不影响节点性能，对于网络元素（节点或者链路）w∈V⋃E，定义Pw为元素中断概率，且0 ＜Pw＜1。

（5）对于传输节点vi、vd，定义r(vi,vd)为传输节点vi到vd的最短路径，假设控制路径为传输节点到控制器以及控制器到控制器的有效路径，且控制路径只取最短路径，定义控制器与控制器之间的路径为邻接路径，当采用层次型控制器部署时，由文献[9]可知，邻接路径条数受控制器个数约束。

（6）设vi∈V,vld∈Vl，x(vld)=1 代表一个控制器布置在位置vld，否则为0；y(vi,vld)=1 代表x(vld)=1 且传输节点vi分配给了控制器vld，或x(vi)=x(vld)=1 且控制器之间有邻接路径，否则为0；设pw(vi,vld)=1 代表vi与vld之间控制路径经过元素w，否则为0。在SDN 网络无保护机制情况下，控制路径平均故障率指传输节点与控制器以及控制器与控制器之间失去连接概率的均值[10]，本文以中断概率近似代替平均故障率，设网络状态分为连通和中断两种状态，则连通状态出现的概率为：

那么网络中断概率为：

（7）对于航空信息网络高动态性特征的考虑，借鉴卫星网络中“拓扑快照”[11]的思想将网络运行时间切割为许多时间碎片，在碎片时间内网络处于保持状态，利用连续静态拓扑模拟航空网络的动态拓扑时变。

2.1 全局平均时延

网络时延包括处理时延、等待时延、传输时延以及发送时延。在网络未拥塞情况下，等待时延[12]忽略不计；处理时延与发送时延通常为固定值；传输时延与两个节点间距离有关，包括控制器与传输节点间以及控制器与控制器之间的传输时延[13]。在网络时延方面，本文仅考虑软件定义航空信息网络的传输时延对全网性能的影响。最小化传输节点间和控制器的延时能有效提高网络中元素故障的发现率和数据传输效率，降低网络拥塞。而逻辑集中、物理分布式控制器部署特点要求控制器与控制器之间的延时尽量最小，确保全网状态逻辑一致，提高协同处理过程的快速反应能力。下面给出最小化全局平均时延公式：

式中，将传输节点和控制器的最短路径时延集合定义为d(vi,vld)，控制器与控制器之间的最短路径时延集合定义为d(vli,vld)，网络节点之间的时延存储在时延矩阵中，用于最短路径时延的计算，n为网络中节点个数，s为控制器部署的个数，c1、c2为调整传输节点和控制器之间延时以及控制器与控制器延时的比例参数，本文取c1=c2=0.5。加号前半部分用于计算传输节点间到控制器的平均时延，加号后半部分用于计算控制器与控制器之间的平均时延，两者之和即为全局平均时延。优化目标f1为最小化全局平均时延。

2.2 全网中断概率

由于航空信息网络具有空间大尺度分布、高动态、拓扑链路不稳定等特点，其节点和链路性能受大气信道影响严重，极易导致节点和链路失连以及网络中断，而网络鲁棒性和可靠性直接影响到整个航空平台性能的优劣，因而在分析研究软件定义航空信息网络控制器部署优化问题时应该着重考虑全网中断概率。通常网络故障分为节点故障和链路故障两类，节点故障又分为传输节点故障和控制器故障，一般由设备中软、硬件故障引起，易导致传输节点和控制器间连接中断，链路故障一般由链路维护、链路攻击引起，易造成传输链路上数据的丢失。单一链路和节点的故障会造成传输节点和控制器之间以及控制器之间用于管理与控制SDN 指令的控制路径的中断，控制路径的中断则会带来网络拓扑的不稳定，从而影响网络的全局可视性。因此，考虑节点和链路故障影响，将部分节点和链路发生故障时全网中断概率最小化作为优化目标，给出最小化全网中断概率公式：

式中,y(vi,vld)=1 代表x(vld)=1 且传输节点vi分配给了控制器vld，或x(vi)=x(vld)=1 且控制器之间有邻接路径，否则为0；pw(vi,vld)=1 代表vi与vld间控制路径经过元素w，否则为0。Pw为元素中断概率，且0 ＜Pw＜1。优化目标f2为最小化全网中断概率。

2.3 控制器负载失衡度

对于软件定义航空信息网络负载均衡问题的考虑，一方面结合成本开销，使用最少数量的控制器最大化地利用控制器控制能力，另一方面不能使控制器实际负载超过其额定负载能力，否则将增加网络拥塞，降低网络性能[14]。这就要求接入控制器的传输节点数量尽可能均匀分布在整个全局网络，减小全局网络控制器负载差异度，从而保证网络资源的充分利用，提高航空信息网络连接成功率，增加航空信息网络鲁棒性。下面给出最小化控制器负载失衡度公式：

式中，qvld表示控制器vld接入控制的节点个数，q0表示所有控制器的平均接入节点数，s为控制器个数。从上式可以看出，控制器负载失衡度越小，控制器控制的传输节点数量越均衡，负载均衡性能越好。

2.4 约束条件

结合控制器部署问题特性，可列出以上三个目标函数的约束条件，如下所示：

式（7）表示网络中部署的控制器个数；式（8）表示网络中一个传输节点仅受唯一控制器控制；式（9）表示控制器间邻接路径的条数；式（10）表示前文中已叙述的控制器整数规划假设条件。

3 控制器部署优化策略分析

本文研究的控制器优化部署问题以传输节点-控制器分配方案为优化对象，算法优化时引入变速度修正因子和高斯变异扰动，克服蝙蝠算法存在的收敛速度慢、易陷入局部最优的缺点，利用改进的蝙蝠优化算法求出模型的非劣最优解集。

3.1 蝙蝠算法及改进

蝙蝠算法[15]是由剑桥大学学者Yang 在2010 年提出的一种新型智能优化算法，该算法通过模拟自然界蝙蝠种群的回声定位来准确探测猎物的位置以及有效避障。与其他一些优化算法相比，该算法具有寻优更为简洁、收敛速度较快、鲁棒性强等特点，适合于求解多目标优化问题。

该算法基本思路是以一只蝙蝠作为基本单元，且每只蝙蝠都有一个适应度值来对函数解空间进行优化。每只蝙蝠可以调整自身发射超声波的强度、频度等对空间进行搜索，使整个种群的活动逐步由无序变为有序。蝙蝠位置以及速度更新公式如下：

式中，fi表示第i只蝙蝠的脉冲频率；fmin、fmax分别表示最小和最大脉冲频率；α是属于[0,1]的任一随机数；Xi(t)和Vi(t)分别表示第i只蝙蝠t时刻的位置和速度；Xbest(t-1)表示t-1 时刻全局蝙蝠中使得适应度值最小的最优位置。当蝙蝠个体在进行局部寻优时，则随机扰动从当前最优解集中任选一解更新下一位置，公式如下：

式中，η∈[-1,1]，Ai(t)表示蝙蝠的脉冲强度。

在搜寻初期，蝙蝠发射的声波脉冲具有较大的脉冲强度和较小的脉冲频度，以便于扩大搜索空间，当距离目标较近时，蝙蝠会减小脉冲强度并增加脉冲频度，以便于准确定位目标。蝙蝠发射声波脉冲强度和频度更新公式如下：

式中，β为脉冲强度衰减系数，β∈[0,1]；γ为脉冲频度放大系数，γ＞0；ri(t)表示第i只蝙蝠t时刻的脉冲频度。

针对基本蝙蝠算法在寻优末段容易陷入局部最优的极值，本文引入变速度修正因子，使得蝙蝠的前期搜索为后期的搜索提供经验，尽可能避免局部极值的困境；为了进一步提高算法的运算效率，本文引入高斯变异扰动，使得蝙蝠在局部寻优阶段，减少更新至下一位置的随机性，提高收敛速度。

3.2 算法相关参数定义

蝙蝠位置定义：算法中每只蝙蝠的位置表示控制器部署问题的一个解，即一种可能的控制器分配方案，解集长度为传输节点个数n，可表示为X=[x1,x2,…,xn]。解中第i个位置对应于第i个节点所接入的控制器，每个传输节点的控制器选择xi构成控制器部署方案X。

蝙蝠速度定义：算法中每只蝙蝠的速度表示蝙蝠位置解向量的寻优更新策略，可表示为V=[v1,v2,…,。向量中元素取1 表示该位置解向量需要进行寻优更新。

适应度函数定义：蝙蝠在搜寻猎物过程中通过不断更新函数的适应度值达到寻优更新的目的，此处取目标函数F(X)={f1,f2,f3}，依次对其进行计算以评价部署方案优劣。本文研究的是一个三目标决策的问题，中断概率与时延、负载失衡度三目标之间在一定程度上可能存在互斥情况，例如当要求控制器间高可靠性时，其传输时延可能较大，因此当满足一个或者两个优化部署方案时不一定能同时保证另外一个或者两个达到最优，此时考虑在可行部署方案中取非劣最优解集以最大限度满足最优部署。

3.3 算法设计与描述

本文所提算法的设计思路是：首先根据初始化网络中传输节点-控制器分布找出一个可行的控制器分配方案，将其作为初始解，然后按照本文所提的改进方式更新蝙蝠的位置与速度，并在迭代中进行Pareto 解集选择，通过不断递进寻优，获得控制器部署问题的近似最优解。算法的具体流程图、步骤及伪代码描述如下。

OBA-CP（controller placement based on optimized bat algorithm）算法流程图如图1 所示。

OBA-CP 算法具体步骤描述如下：

步骤1随机初始化蝙蝠个体N，初始位置Xi(t)，初始速度Vi(t)，脉冲强度Ai(t)，脉冲频度ri(t)，脉冲频率fi范围。

Fig.1 Flow chart of improved bat algorithm图1 改进蝙蝠算法流程图

步骤2根据适应度函数F(X)求出每只蝙蝠的适应度函数值，并找出最优解，记录最优解位置X*。

步骤3更新蝙蝠位置与速度。引入变速度修正因子，对速度更新公式进行改进优化。

式中，χ(t)表示引入的变速度修正因子，其作用是使蝙蝠的前期搜索为后期搜索提供参照；χmax、χmin分别为χ(t)最大值和最小值；σ∈[1,T]，T表示最大迭代次数。

步骤4生成随机数rand1，如果rand1 ＜ri，则引入高斯变异操作，其作用是减少更新至下一位置的随机性，提高收敛速度。

式中，N(0,1)表示服从均值为0，方差为1的高斯分布。

步骤5再次生成随机数rand2，如果满足rand2 ＜Ai&fit(Xi)＜fit(Xnew)，则接受新解，更新Ai(t)和ri。

步骤6排列所有蝙蝠位置，找出当前最优值及对应位置。

步骤7设当前最优解为F*，然后使所有蝙蝠继续向下一时刻搜寻，另设解空间保存已找到的最优解集，解空间元素随搜寻进行逐渐增多，其前沿逼近真实的Pareto 前沿。当达到最大迭代次数后转到步骤8，否则转到步骤3。

步骤8输出结果。

OBA-CP 算法伪代码描述如下：

输入：网络拓扑G(V,E)。

输出：模型的Pareto 解集。

4 仿真及结果分析

为了验证本文提出算法的有效性，采用节点数30 的航空信息网络拓扑，参考文献[16-17]中初始化方法，用传输时延代表链路权重，时延越大，权值越高，设权值为区间[1,10]内的随机整数。为保证网络连通性，考虑网络组件故障率较小的场景，设单个节点和单条链路的中断概率分别为区间[0,0.02]和[0,0.04]内的随机数。实验网络拓扑结构如图2 所示，在1×1 范围内随机生成均分分布的传输节点和链路，控制器部署在传输节点上。设置改进的蝙蝠优化算法种群规模N为80，最大迭代次数T为500，初始脉冲强度和脉冲频度为0.5，fmax、fmin分别为3 和0，β、γ均为0.9，σ取2。

Fig.2 Experimental network topology图2 实验网络拓扑

各算法利用生成的相同网络拓扑，分别取控制器个数从3 个到11 个，重复100 次计算取最终平均值，从全局平均时延、全网中断概率和控制器负载均衡等三项性能尺度指标对改进算法进行评价，并以SPEA-Ⅱ算法[18]和NCPSO 算法[7]作为对比。文献[18]基于典型的多目标优化算法SPEA（strength Pareto evolutionary algorithm）提出了SPEA-Ⅱ算法，利用模糊集理论优化折衷分配方案，证明了改进算法可以产生更广泛且不受支配的Pareto 解集，NCPSO 算法则是利用粒子群递进寻优的思想解决多控制器部署问题。

图3 为采用OBA-CP 算法获得Pareto 解最优前沿，由图可知，全网中断概率与全局平均时延、控制器负载失衡度成反比，验证了控制器部署问题是一个多目标决策问题，中断概率与时延、负载失衡度三目标之间在一定程度上存在互斥情况。此外，表明了Pareto 解最优前沿并不是一个最优解，而是在满足一定约束条件下的权衡解，网络部署决策者可根据Pareto 解最优前沿选择其中满足特定网络需求的一个或一组有效解作为控制器部署问题的最终解。

Fig.3 Pareto solution optimal frontier图3 Pareto 解最优前沿

图4 比较了不同算法下的全局平均时延，由图4可知，随着控制器数量的增加，全局平均时延逐渐降低，符合全局平均时延定义。刚开始控制器个数在4个左右时，通过OBA-CP 算法与NCPSO 算法计算出的时延基本相当，但随着迭代进行，后期在部署相同控制器数量条件下，采用OBA-CP 算法整体上拥有最小的平均时延，其性能优于NCPSO 算法和SPEA-Ⅱ算法。在不同的控制器数量条件下，OBA-CP 算法得到的部署结果中平均时延较NCPSO 算法和SPEA-Ⅱ算法分别降低了2.33%和3.47%。

Fig.4 Global average delay of different algorithms图4 不同算法的全局平均时延

图5 比较了不同算法下的全网中断概率，由图5可知，当控制器个数小于8 个时，随着控制器数量的增加，全网中断概率降低速度较快，超过8 个以后，中断概率趋于稳定，且在部署相同控制器数量条件下，采用OBA-CP 算法明显性能优于NCPSO 算法和SPEA-Ⅱ算法。只有在控制器数量为7 时，NCPSO 算法的中断概率略低于OBA-CP 算法，但这不影响整体上性能效果。对于不同控制器数量条件下中断概率降低的效率，与NCPSO 算法和SPEA-Ⅱ算法相比，平均降低了0.41%和1.25%。

Fig.5 Network-wide outage probability of different algorithms图5 不同算法的全网中断概率

Fig.6 Load imbalance of different algorithms图6 不同算法的整体负载失衡度

图6 比较了不同算法下的整体负载失衡度，由图6 可知，在初始阶段，当控制器个数较少时，三种算法的负载失衡度较高，是由于网络中控制器接入节点个数分布的不均衡所导致；随着控制器个数的增加，失衡度迅速下降，特别地，采用OBA-CP 算法的失衡度较NCPSO 算法和SPEA-Ⅱ算法分别降低了0.73%和0.96%。三种算法得到的失衡度均在0.40 以下且效率对比基本持平。

图7 比较了不同算法下的平均计算用时，由图7可知，采用SPEA-Ⅱ算法的计算用时远高于OBA-CP算法和NCPSO 算法，约为OBA-CP 算法的5 倍左右，这是由于SPEA-Ⅱ算法存在搜索效率低的问题，而采用OBA-CP 算法具有更短的运行时间，这是由于改进的蝙蝠算法具有较好的收敛性和全局搜索能力，有利于搜索过程快速收敛到Pareto 解最优前沿。

Fig.7 Average calculation time of different algorithms图7 不同算法的平均计算用时

由图4～图7 的分析可知，OBA-CP 算法通过对网络拓扑中控制器各部署位置的网络性能进行评估以获取近似最优解，利用优化策略提高蝙蝠算法的收敛速度和运算效率。性能对比上采用OBA-CP 算法的平均时延和计算用时略优于NCPSO 算法，采用OBA-CP 算法的平均时延、中断概率和计算用时显著优于SPEA-Ⅱ算法。

5 结束语

本文针对逻辑集中控制的航空信息网络环境，综合考虑全局平均时延、网络可靠性和控制器负载均衡等三项性能尺度指标，建立了软件定义航空信息网络控制器部署问题的多目标组合优化模型，采用改进的蝙蝠优化算法进行求解，充分利用其较好的寻优功能获得满足特定条件的航空信息网络控制器部署问题的Pareto 解集。仿真结果表明，所搭建的模型可实现多控制器的合理有效部署，提出的算法具有更高的效率，能够快速收敛到Pareto 最优前沿。与SPEA-Ⅱ算法和NCPSO 算法相比，改进算法在三项指标上均有良好的网络性能，对于解决软件定义航空信息网络多控制器优化部署问题提供了一种新思路。由于控制器的部署对于软件定义航空信息网络性能具有重要影响，其中还存在很多问题需要解决，下一步将对一致性、域内连通性等方面展开研究。