基于时延的软件定义航空网络控制器部署策略*

高航航，王 翔，赵尚弘，彭 聪

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

0 引言

进入21 世纪以来，航空通信技术的崛起使得空间信息呈现出“爆炸式”的发展，这些重要信息需要借助于航空信息网络进行传输与处理。航空信息网络［1-2］能够实时获取、传输和处理空间数据信息，具有超远程、高动态、大容量等特点，能够打破地面信息系统对于高空中信息获取的局限性，在未来空间战争中能够发挥重要作用。随着通信技术手段的成熟，网络中传输的数据量迅速增长，网络规模随之扩大，航空信息网络与天基信息系统和地面信息系统分别建立通信链路，并与其进行信息交互，以此实现对信息的综合利用。

航空网络中包含功能各异的飞机，如侦察机、预警机、电子干扰机、无人机等，将这些空中平台所获取的数据进行传输、交换与融合等处理，可实现对航空信息网络中信息的有效管理与高效利用。航空信息网络作为信息化战场的重要组成部分，未来会朝着高度不确定性、高度动态性和高度对抗性发展。此外随着日益复杂的战场环境对作战效能要求的不断提高，现阶段的航空平台自身的能力面临很大的挑战。目前航空信息网络的设计主要从传输性能方面考虑，与作战任务不具备灵活的耦合关系，导致网络中的冗余进一步增多；又比如网络中的设备大多采用封闭式设计，内部集成大量的协议，缺乏开放接口，针对不同应用需求设计的网络设备难以共享操作等等。软件定义网络（Software Defined Network）的出现为上述问题带来了解决方法，SDN是一种数据控制分离、软件可编程的新型网络体系架构［3-5］，它采用集中式的控制平面和分布式的数据平面，控制平面和数据平面相互分离，控制层利用南向接口对数据平面中的网络设备进行集中式控制，并提供灵活的可编程能力。

当前国内外关于控制器部署主要围绕负载均衡、流量处理开销、可靠性等不同优化目标来确定控制器的部署位置。文献［6］以控制器部署个数和控制器位置为目标，提出了基于平均时延和最大时延的模型，并在不同网络拓扑中进行仿真测试。文献［7］提出k-critical 算法，构建robust 树解决控制层的部署问题，该算法对于控制层的鲁棒性有进一步提高。文献［8］定义一种二层建模方法，讨论故障情况下控制器部署对于SDN 性能的影响。针对网络子域划分这一问题，文献［9］通过引入惩罚函数避免产生孤立节点，并在时延和容量限制下提出一种负载均衡的多控制器部署算法。文献［10］定义了可预期控制链路亏损百分比，从可靠性方面对SDN 控制器的部署进行研究。文献［11］以航空信息网络的全网可靠性作为优化目标，采用人工免疫策略、小生境思想和改进遗传算法的混合优化算法。上述研究并没有考虑整体网络的时延情况，文中主要针对航空信息网络中全网时延这一目标加以优化。

本文基于软件定义网络思想，提出在航空信息网络中构建集群系统，为每个集群系统设置集群控制器，控制器管理该域内飞机。对k-means 算法改进，以实现对集群系统的合理划分，并为控制器建立可靠性部署。最后，以包含23 个节点的航空信息网络作为仿真场景，完成数据仿真，得出不同算法的部署结果，并进行分析对比。

1 模型分析

1.1 软件定义航空信息网络描述

航空平台作为航空信息网络中的基本作战单元，是实现空中信息获取、传输与处理的重要部分。通过将一定数量、能力各异的有人/无人航空平台构建为航空信息网络，在复杂的战场环境中根据实际的需求，通过各个平台间的优势互补，在很大程度上可以更好地适应未来战场环境［12-13］，航空信息网络结构如图1 所示。软件定义航空信息网络［14］基于软件定义网络思想，针对航空信息网络中的主要问题改进，与作战任务灵活耦合，进一步使航空信息网络的能力得到最大发挥。

图1 航空信息网络结构示意图

SDN 采用数控分离思想，当数据控制分离后，原来分布式的控制平面被集中化，利用逻辑集中控制的控制器可以实现对网络中流量的优化。然而随着网络规模的扩大，单个控制器的服务能力有限，将会导致整个网络的性能大大下降。控制平面的可扩展性则有效地解决了这一问题，通过在控制平面中部署多个控制器，以此提升网络的性能。在实际中常采用物理上分布、逻辑上集中的多控制器部署策略，SDN 基本网络架构如下页图2 所示。

图2 SDN 基本网络架构

在航空信息网络中，将整个网络拓扑划分为多个域，每个域称为航空集群域［15］，每个航空集群域内部署一个或多个集群控制器。集群控制器负责本域内的信息管理，集群控制器之间则通过共享数据来维持全网视图信息。根据软件定义航空信息网络中控制器部署问题的特征可知，数据传输距离、链路节点个数是网络时延模型中的重要因素，此外，链路故障率在网络可靠性模型中也有着重要影响。本文则通过合理部署控制器，在航空信息网络可靠性的基础上实现全网络的快速响应。

1.2 航空集群控制器部署可靠性分析

在部署控制器时，通常假设其所有通信链路发生故障的可能性相同，或者不考虑链路故障。然而在航空信息网络中，由于高空中各种未知因素的影响，使得通信链路容易发生故障，且每条通信链路发生故障的概率各不相同，因而此时用最短路径法并不能对网络性能进行更准确的分析。如图3 所示，假定该集群域内的控制器部署在位置C1，控制并管理其余节点S1～S5，虚线表示通信链路，虚线上的数字表示该链路发生故障的概率。当控制器C1和节点S2 进行通信时，如果此时考虑链路故障，并以通信路径所经过链路的总故障率最小为目标，利用最短路径法（如Dijkstra 算法）可得到传输路径为：（C1，S1，S2）和（C1，S1，S3，S2），此时利用最短路径算法并不能选择出最佳传输路径。随着网络中节点个数和链路个数的增加，使用最短路径算法会对网络整体的可靠性带来严重影响，进一步造成网络性能大大下降。

图3 链路故障率对网络性能的影响

图4 表示控制器部署位置对于网络可靠性性能的影响，在图4（a）中，当集群控制器部署在位置S7 时，假若（S5～S7）之间的链路发生故障，则会导致除S7 外剩余的交换机节点均与控制器C1 失去联系，此时的网络性能将急剧恶化。而在图4（b）中，控制器部署在位置S5，当（S5～S7）之间的链路发生故障时，此时只有交换机节点S7 失去控制，而网络剩余部分仍保持连通。可以看出，与控制器部署在位置S7 而言，部署在位置S5 将大大提高网络的可靠性。因而在集群域内合理地选取控制器部署位置，将能够有效提高网络整体性能。

图4 控制器部署位置对网络可靠性影响

1.3 数学模型分析

经过上述对网络性能的分析，本文在软件定义航空信息网络中对控制器的部署问题作出以下描述：

1）用带权无向图G（V，E，C）表示航空信息网络拓扑，其中V={v1，v2，…，vq}代表网络中的节点集合，节点数目为q，E={（vs，vt）|vs，vt∈V}代表网络节点之间的链路集合，C={c1，c2，…，cm}代表网络中控制器节点的集合，控制器节点控制管理着交换机节点。

2）假定交换机节点可以是网络中的任何节点位置，控制器节点的部署位置也可以是网络中的任何节点，当交换机节点和控制器节点位置重合时，认为二者之间的时延为0，且每一个交换机节点受唯一的控制器节点控制。

3）对于任意给定的两个节点vt和vs，设L（vt，vs）为节点vs到节点vt的最短路径距离，若节点vt和vs之间相通时，则定义节点间的连接关系为1，否则为0。

4）假设在交换机节点和控制器节点间使用带内通信，即二者仅通过现有的通信链路传输数据。最短路径法是以通信链路长度（或者节点跳数）作为路径选择的依据，这种方式并不能保证所选择的通信路径可靠性最高，但在通信时延方面结果最小。

5）为了提高网络的整体性能，交换机节点间传输数据时，为使传输时延尽可能短，采用最短路径法来获得传输时延最小化。而考虑到交换机节点向控制器节点发送数据时控制路径的重要性，在控制路径的选择上重点考虑可靠性，为使控制路径的可靠性最高，采用以控制路径所经过链路的故障率最小为权重的最短路径法。控制器为了获取全网的视图信息，需要对各集群域内控制器节点的数据进行同步，而数据同步路径对于可靠性的要求同样较高，因而同样采用以链路故障率最小为权重的最短路径法选择数据同步路径。

文中以全网时延最小为优化目标，目标函数表达式如式（1）所示，优化过程中约束条件如式（2）～式（5）所示：

其中，式（2）表示控制器部署在节点j，否则为0；式（3）表示交换机节点i 受控制器j 控制，否则为0；式（4）在总节点中选择k 个节点部署控制器；式（5）表示每个交换机节点只能由一个控制器控制。

由上述分析可知，控制器部署到网络后会产生3 种时延，分别为节点传输时延、控制路径时延和控制器同步时延，3 种时延的表达式如下所示：

其中，式（6）表示数据从交换机节点vt传输到交换机节点vs的传输路径时延；式（7）表示交换机节点之间数据的平均传输时延；式（8）表示数据从交换机节点vr传输到其集群域内的控制器节点cn的控制路径时延；式（9）表示交换机节点到控制器节点之间的平均控制时延；式（10）表示控制器节点间相邻路径个数；式（11）表示控制器节点cm与cn间传输数据时的平均同步时延。

2 算法方案设计

本文借鉴卫星网络路由策略中的“网络拓扑快照”思想［16-17］，在网络运行过程中将区间划分为若干个小时间片，每个小时间片称之为“快照（snapshot）”，在一个时间片内认为网络拓扑保持静止，即用连续的静态拓扑进行航空信息网络模拟。文中将控制器部署视作聚类分析［18-19］问题，将每个聚类视作为一个集群域，且假定每个集群域内仅部署一个控制器。以实际网络拓扑为输入，以不同方案下的部署结果作为输出。最后采用具有23 个节点、72 条链路的航空网络拓扑进行仿真。为了验证基于k-means 的改进算法在控制器部署方面的性能提升，本文同时设计了随机放置算法以及k-means 算法。在部署时，为了减小随机选取初始节点造成计算结果的极端性，将随机算法和k-means 算法运行10 次结果的平均值作为最终仿真结果。

在控制器部署时，需要构建航空集群域，本文在构建集群域时采用改进的k-means 算法。k-means 聚类算法以Dijkstra 算法为依据，在该算法中，由于初始节点的选取是随机的，因而会在一定程度上使得优化结果不能达到全局最优。而k-means 改进算法在k-means 算法基础上对初始节点的选取作以优化，避免其集中于节点密集的区域，使选取的初始节点在空间分布上与实际数据相符合，改进算法如下页表1 所示。

航空集群域确定后需要对控制器的位置进行部署，本文在一个集群域内仅部署一个控制器。文中以网络总时延最小为优化目标，同时为了确保网络的可靠性，要避免将控制器部署在网络中节点度小的位置上，具体算法如表2 所示。

3 仿真结果分析

为了验证本文所提出算法的有效性，采用随机生成的23 个节点、72 条链路作为航空信息网络进行仿真，并对每一个网络节点和链路进行编号，假定每个集群中部署一个控制器，且该控制器能够处理来自本集群域内交换机节点所传输的信息，链路中断概率设为［0，0.1］内的随机数，仿真中所传输的数据参考文献［20］进行设置。本文同时将随机放置算法、k-means 算法与文中改进算法加以对比，随机放置算法是在所有节点中随机选取若干个节点作为控制器位置进行部署，k-means 算法在划分集群时，初始节点是随机选取的，其余设置与本文算法相同。

表1 k-means 改进算法

表2 控制器部署节点选取

图5 所示为链路在不同中断概率下控制路径损失率的情况，控制路径损失率定义为数据由交换机节点向控制器节点间传输时，由于链路发生故障所导致的控制器节点无法收到数据的情况。可以看出，随着链路中断概率的增大，控制路径失效率也随之增大。在3 种算法仿真结果中，带权重最短路径法的效果最好，当链路中断概率为0.1 时，控制路径数据损失率在14%左右，而无权重最短路径法的性能较差，其控制路径数据损失率在44%左右，这是因为无权重最短路径法仅考虑路径最短，而不考虑链路的可靠性，当最短路径中包含某条高故障率链路时，必然会使得控制路径数据损失率较高。而对于无权重随机路径法而言，由于控制路径选取的随机性，使得控制路径可能绕过最短路径中那些高故障率链路，因而这两种方法的性能略有差距。而带权重最短路径法是以总路径故障率最低为目标，因而在3 种算法中性能最好，可以取得较理想的结果。

图5 链路故障与控制路径数据损失率的关系

图6 不同控制器数量下的网络时延

图6 所示为不同控制器数目下的网络时延情况，文中将控制器的个数从2 逐渐增加到8，并将本文所提算法与随机放置算法和k-means 算法进行对比，结果表明，采用随机放置方法的网络时延最高。这是由于控制器所选取的节点随机，并且不能保证距离控制器最近的节点被该控制器所控制，而k-means 算法和k-means 改进算法首先确定集群，随后在集群中部署控制器，这样有效地保证了距离控制器近的节点都能被该控制器所控制，相对于随机放置算法，其时延得到有效的降低。可以看出，当控制器数目为5 时，随机放置算法的时延结果为4.85 ms，而采用改进k-means 算法的时延则为2.24 ms。

下页图7 所示为不同控制器数目下的控制器同步总时延。从仿真可以看出，随着控制器数目的增多，总同步时延是逐渐增大的。这是由于控制器数目的增多，使得控制器之间同步数据的路径逐渐增多，进一步造成控制器间总同步时延的增大。可以看出，当控制器的个数为2 时，文中所提出算法的总同步时延为2.8 ms，当控制器数目为8 时，总同步时延则为17.2 ms。仿真结果表明，控制器间数据总同步时延将随着控制器个数的增多而增大，因而不能无限制部署控制器，网络中的控制器节点数目应在一定范围内才能合理地部署，而过多的控制器数量则会导致网络中增加过多不必要的开销。

图7 不同控制器数量下的总同步时延

4 结论

本文提出基于时延约束下的控制器可靠部署方案，定义数据传输时延、控制路径时延和控制器同步时延，并以全网络时延最小为优化目标，同时对控制路径和控制器同步路径进行可靠性优化，利用改进的k-means 算法，为在网络中使用多少控制器以及控制器位置的选择提供了方法。仿真结果表明，该方法在网络可靠性的基础上，能够实现全网络时延的优化。由于控制器节点处理信息的能力有限，当某个航空集群中的交换机节点过多，超过控制器节点的处理能力时，会使得该集群中的控制器节点过载，导致该集群处理信息能力大大下降，进而会造成整个航空网络性能下降。下一步将针对集群中交换机节点负载均衡展开研究，提出相应的控制器部署方案。