基于网络分域的航空信息网络控制器部署方法

付皓通, 王 翔, 赵尚弘, 宋鑫康, 薛凤凤

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

现阶段以“平台为中心”设计思路构建的航空信息网络[1]存在功能与设备耦合,平台间信息传输共享不畅,网络集中管控能力不足等问题[2-3],面对日益复杂的业务需求及不断增长的业务流量,越来越难以满足用户的服务需求。软件定义网络[4-5](software defined network,SDN)技术的出现为航空信息网络的发展带来了全新的思路,SDN使网络管理与数据传输相分离,建立逻辑集中的控制平面实现全网设备的统一管理,控制平面不参与具体的流量传输,专注于控制策略的制定和下发;设备平台简化为传输单元,负责接收控制平面下发的指令并执行流量传输等操作。SDN具有的开放性、灵活性及可编程性等特点,为提升航空信息网络资源管控能力带来了巨大优势,可显著提升网络任务服务效能[6]。

应用SDN技术构建航空信息网络[7],首先需要在网络中的关键节点部署控制器,建立逻辑集中的控制架构,为网络资源集中高效管控,灵活动态调度提供体系架构保障。目前SDN控制器部署问题逐渐成为研究热点[8],研究表明控制器的数量和部署位置会显著影响网络性能[9],前者影响着控制平面的稳定性及可扩展性,而后者关系到网络的管理和配置效率。目前相关研究以地面网络应用为背景,文献[10]对时延优化问题进行研究,提出基于聚类的网络划分算法来减少传播时延;文献[11]针对可靠性部署问题分别采用贪婪算法和模拟退火算法进行求解,得到了可靠性优化的部署方案;文献[12]综合网络时延和负载均衡度,采用改进多目标遗传算法进行求解,加快算法收敛性的同时提高了解的多样性;文献[13]对网络弹性和容错性部署问题进行研究,应用Pareto优化理论实现了二者的权衡;文献[14]对负载均衡问题进行研究,采用博弈论方法重新分配交换机来实现控制器的负载均衡;文献[15]提出了一种基于网络划分的部署算法,降低算法复杂度的同时可实现请求时延及网络可靠性的优化。然而文中仅考虑了区域内的流量传输,未考虑跨区域流量传输场景,且网络模型有待进一步完善,算法复杂度仍需进一步降低。

与地面应用场景不同,航空信息网络具有网络规模大、战场环境对抗性高、电磁环境干扰强等特点,控制节点容易出现故障损毁问题,因此采用多全局控制器的混合式结构[16-17]来提升网络的鲁棒性性及可扩展性。此外,面对瞬息万变的战场态势,信息传输时延、网络负载均衡度、网络可靠性及部署成本等因素均对网络性能有较大影响,决定着航空信息网络在体系对抗中是否能取得优势地位,因此在控制器部署问题中需要对上述指标进行充分考虑。

为推进SDN与航空信息网络的结合进程,有效提升航空信息网络的综合性能,本文结合航空信息网络场景特点,针对网络中的关键性能指标,设计了一种基于SDN的航空信息网络混合式控制架构,来实现对全网平台的集中管控;综合考虑区域内流量传输及跨区域流量传输两种重要传输场景,建立请求时延函数,并对网络模型及约束条件进行完善细化;借鉴网络分域能够有效降低算法寻优复杂度的思想,在控制架构建立过程中,首先依据平台间的时延性能将网络划分为不同区域,确保区域内部平台之间的信息能够快速传输;其次,为避免单一性能指标存在的局限,依据请求时延、负载均衡指数及控制器数量等指标对网络平台进行域间调度,从而提升网络的综合性能;在此基础上,以网络可靠性最大化为优化目标部署控制器,建立集中控制体系,实现对网络的集中管控。为验证本文所提算法的有效性,在仿真实验部分对算法性能进行验证分析。

1 系统模型

1.1 场景描述

航空信息网络混合式控制架构如图1所示,网络中存在多种类型的有人/无人机平台,依据航空任务动态组织。为实现网络的集中高效管控,同时提升控制平面的可扩展性,将网络控制平面划分为区域控制器平面和全局控制器平面。区域控制器平面由区域控制器(area controller,AC)组成,每个区域控制器能够管理一定范围和规模的网络,负责域内平台管理及流量转发,收集底层网络状态信息并向上提供给全局控制器;全局控制器平面由多个空间分布的全局控制器(global controller,GC)组成,全局控制器之间通过分布式通信协议共享各自掌握的网络状态信息,从而形成统一的网络视图信息,并负责跨区域流量的处理和转发。

(a)航空集群作战场景 (b)混合式控制架构

控制器根据网络规模、空间分布、网络流量等情况按需部署在网络中,以实现网络的高效管控[18]。假设网络中所有节点都可以部署成为控制节点,控制器功能与平台应用程序共享设备底层物理资源,可以根据部署指令动态开启或关闭控制器功能,实现控制器的弹性部署。网络中动态变化的控制器形成控制器资源池,部署成为区域控制器平面和全局控制器平面,共同形成逻辑集中的网络控制架构。

1.2 网络模型

航空信息网络用无向图G(V,E)表示,其中V={v1,v2,…,vN}表示航空平台集合,E表示平台间的链路集合,网络可划分为多个区域,每个区域都包含一定数量的网络节点与相关链路,对每个区域部署一个控制器来实现对该区域节点的管控。网络划分约束可表示为:

G(V,E)=G1(V1,E1)∪G2(V2,E2)∪…∪GK(VK,EK)

(1)

Gi∩Gj=∅,i≠j

(2)

航空信息网络中相关变量及定义归纳如表1。

表1 航空信息网络相关变量及定义

1.3 性能指标

1.3.1 平均请求时延

与单控制器架构和扁平式控制架构不同,在混合式控制架构中,网络节点的流量请求有2种类型:①节点到区域控制器的流量请求;②节点到全局控制器的流量请求。对于域内通信而言,节点产生的流量请求到达区域控制器,由区域控制器处理并转发到域内节点,实现域内流量传输。区域k中节点的域内流量请求时延可表示为:

(3)

对于域间通信而言,节点产生的流量请求经区域控制器后到达全局控制器,由全局控制器处理后转发到其他区域控制器,进而转发至目的节点,实现跨域流量传输。区域k中节点的跨域流量请求时延可表示为:

(4)

式中:d(u,v)为Dijkstra算法计算得到的最短路径。

设每个节点的跨域通信概率为P,域内通信概率为1-P,域k的平均请求时延可表示为:

(5)

1.3.2 负载均衡指数

在混合式架构中,网络被划分为不同的区域,区域控制器管理并维护着域内网络功能的正常运行。网络的负载均衡性是控制器部署时需要考虑的重要因素[19]。文中综合考虑节点流量请求速率与节点数量的影响,区域k的负载均衡指数可表示为:

(6)

1.3.3 网络可靠性

在航空信息网络中,控制平面的可靠性是网络性能的重要指标,可靠性越高,控制平面能够正常运行的时间就越长[20]。可靠性通常包括节点可靠性和链路可靠性,设节点故障的概率为pv,链路中断的概率为pe,则节点i和j之间的链路可靠性可表示为:

R(i,j)=∏e∈Ei,j(1-pe)∏v∈Vi,j(1-pv)

(7)

式中:Vi,j和Ei,j分别表示i和j之间最短路径所包含的节点集合与链路集合。

1.3.4 控制器数量

航空信息网络的部署成本主要取决于部署的控制器数量,因此,在满足网络管理需求的条件下,最小化控制器的部署数量,能有效降低网络部署成本并提升资源利用率。设每个控制器的容量为φ,不引起控制器过载的最大资源利用率为Umax,网络中所需的最少控制器数量为:

K0=μtotal/(φ·Umax)

(8)

设网络中实际部署的控制器数量为K,则实际部署数量与最少数量的偏差可表示为:

(9)

式中:Kvar值越小,表示实际部署的控制器数量越少,网络部署成本越低。

1.4 优化目标及约束条件

通过定义网络请求时延、负载均衡度、网络可靠性及控制器数量等指标,能够对航空信息网络性能进行比较全面的衡量。在控制器部署的过程中,需要同时考虑对上述性能指标进行优化,以增强网络的综合性能,提升快速响应能力、负载均衡性及网络可靠性,并降低部署成本。网络的优化目标可以表示为:

Kvar},K0≤K≤N

(10)

式中:X={x1,x2,…,xK},xk={xk,1,xk,2,…,xk,N},且xk,j={0,1}。区域数量K为优化变量,K不小于最小分域数量K0,且不超过节点总数N。

网络中相关的约束条件表示如下:

∈Ei,j

(11)

式中:C1表示每个节点在同一时刻只能划分到一个区域;C2表示域内节点的流量请求速率之和不超过控制器承载限度。C3表示节从点i到节点j的数据流至少需要经过一条链路;C4、C5表示为避免数据流出现环路并且保证数据流流向,每个数据流最多只能从一个节点流出或从一个节点流入;C6表示流经一个节点的数据流需满足连续性约束[22];C7表示流经链路eu,v的所有数据流之和不超过链路的带宽bu,v。

2 控制器部署算法设计

航空信息网络的网络规模庞大,直接部署控制器面临寻优范围广、计算复杂度大、运算时间长、难以及时部署等问题。为解决上述问题,本节结合航空场景特点,提出一种航空信息网络控制器部署算法(aviation information network controller deployment algorithm,AIN-CD)。

2.1 网络划分

为实现网络的快速划分,本节基于节点距离构造模块度函数进行网络分域,得到相似度高、节点间时延小的划分方案,保证算法能够快速收敛。基于距离的模块度函数构造如下:

(12)

(13)

Ai,j=χ/d(i,j)

(14)

式中:Ai,j表示节点i和j之间边的权重,其与节点之间的距离成反比,同时为避免Ai,j值过小以系数χ调节;Σin表示域内所有节点之间的边权重之和;Σtot表示与域内节点相连的所有边的权重之和。网络模块度值等于所有子域模块度值之和。

节点从原域中取出,加入到目的域时,会产生模块度增益[22]:

(15)

式中:wi,in表示节点i与目的域相连的所有边的权重之和;wi表示与节点i相连的所有边的权重之和。

在分域过程中,将每个节点依次取出,遍历相邻的域并计算ΔQ,若存在ΔQ>0,则选择模块度增益最大的域放入该节点,否则不发生移动。重复上述过程,直到网络的模块度值不再发生变化;接下来将各域内点合并为一个超节点,继续对超节点执行分域操作,直至达到收敛条件。

2.2 域间调度

在本节中,综合考虑请求时延、负载均衡及控制器数量的影响对网络节点进行调度,进一步优化网络的分域结构。

将各域中节点组成节点联盟,依据请求时延、负载均衡及控制器数量建立分域优化函数,通过比较分域优化函数的变化来判断域间节点是否进行调度。构造分域优化函数如下:

(16)

式中:U(ν)表示分域结构为ν时的优化函数值;Dmax、Lmax分别表示平均请求时延、负载均衡度指数的最大值。此时优化目标可转化为寻找分域优化函数的最大值,即maxU(ν)。节点n从域Vi调度到域Vj的条件可表示为:

(Vi,ν)n(Vj,ν')⟺U()

(17)

若节点n倾向于留在当前域Vi中,则相应的调度关系可表示为:

(Vi,ν)≻n(Vj,ν')⟺U(ν)≥U(ν')

(18)

式中:当前网络分域结构和相邻结构分别表示为ν和ν',分域数量K为网络中非空子域的数量,节点调度算法流程如表2。

表2 域间调度算法流程

2.3 控制器部署

航空信息网络具有空间分布范围广泛、网络拓扑动态变化、链路连接状况不稳定等特点,容易出现通信中断、平台失连及损毁等问题,从而导致网络功能失效及网络性能下降,因此在部署控制器时,选择网络中可靠性最高的节点进行部署,可以提升控制平面的可靠性。可靠性最大化的控制器部署算法见表3。

表3 控制器部署算法流程

在算法1形成的分域结构基础上,依次遍历每个区域,选择区域中可靠性最大的节点部署区域控制器实现对该区域的管控;后依次遍历每个区域控制器节点,选择其中可靠性最高的|Cg|个节点部署全局控制器,从而形成层次式控制结构。

3 复杂度分析

在网络分域阶段,设第i次迭代后网络网络规模为Ni,则算法收敛需要执行的计算量为N(N-1)+N1(N1-1)+…+1.2K0(1.2K0-1),由于Ni≪N,时间复杂度为ο(N2)。在域间调度阶段,域内每个节点都需要与其他域进行比较交换,网络总节点数为N,分域数量为K,平均每个域中的节点数为N/K,则需要执行的计算量为(N/K)(K-1)K,时间复杂度为ο(KN)。在控制器部署阶段,需要遍历域内每个节点,选择可靠性最大的节点进行部署,算法时间复杂度为ο(N);之后遍历所有局部控制器节点,选择可靠性最大的|Cg|个节点部署全局控制器,时间复杂度为ο(K)。因此,AIN-CD算法的时间复杂度为ο(N2)+ο(KN)+ο(N)+ο(K),由于K≪N,因此算法时间复杂度近似为ο(N2),与网络节点数量的平方成正比。

4 实验分析

4.1 仿真环境设置

在本节中基于MATLAB环境对所提模型和算法进行仿真实验,并将AIN-CD算法和改进K-means算法[24](improved K-means algorithm, IKM)、基于帕累托优化的控制器部署算法[25](Pareto-based optimal controller placement algorithm, POCO)和随机部署算法(random deployment algorithm, RD)的性能进行比较,仿真区域为400 km×300 km的矩形区域,节点的通信半径为50 km,网络拓扑在给定网络规模下随机生成,节点之间的最短路径由Dijkstra算法计算得到,相关仿真参数设置见表5,每次仿真实验重复执行20次,取平均值作为实验结果。

表5 仿真参数设置

4.2 实验结果分析

AIN-CD算法能够根据模块度函数及分域优化函数自适应地计算得到最佳的网络分域数量,而IKM、POCO和RD算法需要预先指定网络分域数量,因此将其他算法的分域数量设置为与AIN-CD算法相同。

图2为不同网络规模下算法的平均请求时延变化。随着网络规模不断增长,平均请求时延不断增大。RD算法采取了随机部署策略,没有考虑对网络性能指标进行优化,因此平均请求时延最大。当网络规模小于120时,AIN-CDA算法的平均请求时延小于IKM算法;当网络规模大于120时,IKM算法的平均请求时延最小。IKM算法依据节点间距离最短对网络进行划分,因此能获得较小的平均请求时延。

图2 不同网络规模下平均请求时延

图3为α=0.5,β=0.5时不同网络规模下算法的负载均衡指数变化。随着网络规模不断增长,负载均衡指数不断增大,负载均衡性逐渐下降。RD算法的负载均衡性能最差,容易出现网络负载失衡及控制器过载等问题,IKM算法的负载均衡性优于RD算法。POCO算法的负载均衡性低于AIN-CD算法,由于POCO算法同时对请求时延、负载均衡和可靠性进行寻优,各目标之间存在一定程度的互斥关系,对其他性能指标进行优化时会降低负载均衡性。与其他算法相比,AIN-CD算法的负载均衡指数最小,表明其负载均衡性最好。当α=0.5,β=0.5时,AIN-CD算法综合考虑域内节点流量请求速率与节点数量的影响,实现了较好的负载均衡性。

图3 不同网络规模下负载均衡指数

图4所示为不同网络规模下算法的可靠性对比。RD算法的可靠性最低,IKM算法在部署过程仅对时延性能进行优化,其可靠性低于AIN-CD算法;当网络规模大于140时,AIN-CD算法的可靠性低于POCO算法。由于AIN-CD算法首先对网络进行划分,一定程度上限制了算法的优化能力;而POCO算法面向全网搜索寻优,能有效避免陷入局部最优,算法的全局寻优能力更强,因此网络规模增大时算法的可靠性最高。

图4 不同网络规模下网络可靠性

设置网络规模为120,图5～图7为该规模下4种算法在不同分域数量时的网络性能对比。AIN-CD算法将网络划分为6个子域,并且不随分域数量增长而变化,因此在图5～图7中为直线。

图5和图6分别为不同分域数量下平均请求时延和负载均衡指数的变化。随着分域数量的增加,4种算法的平均请求时延和负载均衡指数均不断下降。由于分域数量逐渐增加,域中节点不断减少,从而降低了域内请求时延和网络管理压力。当分域数量多于6时,IKM算法和POCO算法的平均请求时延低于AIN-CD算法;当分域数量多于7时,IKM算法和POCO算法的负载均衡指数小于AIN-CD算法。然而控制器随分域数量增加而增长,增加了网络部署成本。AIN-CD算法将分域数量作为优化目标之一,根据网络状况进行合理分域,在保证较好时延和负载均衡性能的同时,能够有效降低网络部署成本。

图5 不同分域数量下平均请求时延

图6 不同分域数量下负载均衡指数

图7所示为不同分域数量下网络可靠性的变化。随着分域数量的增加,4种算法的可靠性不断提高,从而验证了增加控制器数量能够有效提升网络可靠性。当分域数量多于7时,POCO算法的可靠性高于其他算法。

图7 不同分域数量下网络可靠性变化

图8为不同网络规模下算法平均计算时间的变化,将IKM算法、POCO算法和RD算法的分域数量设置为与AIN-CD算法相同。随着网络规模不断增长,算法的计算时间不断增加,AIN-CD算法的计算时间小于IKM算法和POCO算法。AIN-CD算法通过网络分域与域内寻优,有效降低了计算复杂度,从而减少计算时间;POCO算法的计算时间明显增加,约为AIN-CD算法的3倍左右。由于POCO算法面向全网搜索寻优,对网络规模变化敏感,当网络规模增大时计算复杂度迅速增长,因此计算时间最长。而RD算法采用随机部署策略,不涉及对网络性能进行优化,因此计算时间最短。

图8 不同网络规模下算法计算时间变化

5 结语

本文面向航空信息网络控制器部署问题开展研究,针对航空信息网络规模庞大、拓扑动态变化、战场对抗剧烈等特点,归纳了平均请求时延、负载均衡指数、控制器数量、网络可靠性等关键性能指标,提出了一种网络划分和域内部署的控制器部署算法。研究结果表明,所提算法具有较低的计算复杂度,能够有效提升网络综合性能,适用于解决航空场景下的控制器动态部署问题。深度强化学习是人工智能技术的重要突破,为提升航空信息网络资源优化能力和网络管理效率带来了可能,未来将开展基于深度强化学习的航空信息网络控制器部署方法研究。