面向航空信息网络的控制器可靠性部署方法

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

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

0 概述

航空信息网络又称为机载网络、空基网络,主要通过高空航空平台进行信息发送、节点接收或转发,是以节点间的无线通信为传输链路所组成的网络,其具有高动态、覆盖范围广、作战任务多样化、接入数据量大等特点[1-2]。随着网络规模的扩大和作战环境的复杂化,当前的航空信息网络也逐渐暴露出一系列问题[3],例如:如何对航空平台所获得的战场信息进行高效共享以及灵活调度控制;不同的作战需求在网络时延、可靠性方面具有不同QoS需求,要求网络应具备较强的差异化服务能力;软件控制和硬件转发紧密耦合的传统网络设备难以满足网络快速发展的需要。面向未来的航空信息网络应当具备提供灵活耦合任务的差异化网络服务、支持灵活高效的网络配置、新网络技术能够简单快速部署等能力,而现有的无线信息网络仅能满足有限任务背景下模式固定的信息交互需求,难以支撑未来作战中航空集群成员间的灵活协同。

软件定义网络[4](Software Defined Network,SDN)的出现为解决上述问题提供了新思路,其通过将传统网络设备中的控制平面和数据平面相解耦,利用逻辑集中控制的SDN控制器对底层转发设备进行统一管控,控制平面负责策略制定与资源调配,底层转发设备进行数据业务的转发,有效提高了网络的信息处理和管理控制能力。然而集中式的控制平面存在单点失效、可靠性低、处理能力受限等缺点,实际中需要重点考虑控制平面的可扩展性,采用物理上分布、逻辑上集中的多控制器部署架构已成为目前解决控制平面可扩展性的重要方法。

当前对于SDN多控制器的部署研究主要以地面网络为主,评估指标包括网络时延、可靠性、流量开销等[5]。文献[6]针对SDN中控制器部署问题进行研究,首先定义平均传输时延和最大传输时延,在此基础上利用实际网络拓扑进行分析,得到控制器数量对网络时延的影响以及最优时延和平均时延的比较结果,但文中仅考虑了网络传输时延。文献[7]在传输时延基础上增加发送时延以完善现有的时延模型,并对该模型是否存在最优解进行证明,针对是否发送时延分别提出传输算法和输送算法。文献[8]针对传统静态部署方案难以应对高动态网络拓扑和流量变化这一问题,采用一种基于双门限的交换机动态迁移策略以解决控制器失效和资源浪费问题,结果表明该算法在提升系统吞吐量的同时可保证控制器间的负载均衡。文献[9]以航空网络的全网中断概率最小为目标,提出一种融合人工免疫策略、小生境思想以及改进遗传算法的混合优化算法,仿真表明该算法在获得更优值的同时其收敛时间也得到一定减少,但该文未考虑控制器的负载均衡问题。文献[10]针对控制路径平均故障率提出有效控制路径预期百分比这一指标,通过最大化预期百分比实现网络控制路径的强健壮性,但平均故障率仅能反映网络整体故障,无法反映网络的最坏状态。

航空信息网络具有高动态网络拓扑、远距离传输范围、大尺度节点分布以及不稳定的链路质量,因此,传统基于地面网络的多控制器架构、部署算法等不再适用。本文在总结航空信息网络特点的基础上,对传统平面式和层次式SDN多控制器架构进行改进,设计一种混合式多控制器部署架构。针对多控制器负载不均衡问题,提出改进的集群域划分算法,并以网络节点和链路中断概率为变量,将网络控制路径故障率最小作为优化目标,设计改进的离散粒子群优化算法实现多控制器部署。

1 模型分析

1.1 软件定义航空信息网络架构特点

航空信息网络位于天基网络和地面网络之间,如图1所示,其对上可与天基平台建立信息链路,实现天基信息及时注入航空信息网络,为航空平台提供信息支持,对下可与地面信息系统建立信息链路以保证地面指控信息的输入,实现综合信息处理分发、空中指挥控制和协同传输。目前航空信息网络正朝着网络异构化、业务多样化、功能复杂化的方向发展,加之网络节点的移动性、链路的不稳定性,其对当前的网络性能提出更高的要求。现有的无线信息网络虽然在传输可靠性、端到端时延、传输速率等网络传输性能指标上能够支撑现有的航空网络进行一定程度的作战协同,但其本质上并非契合未来航空集群作战的应用背景,网络仅能满足有限任务背景下模式固定的信息交互需求,与作战任务缺乏灵活的耦合关系,而构建一个基于SDN的航空信息网络将更符合未来作战对网络各方面性能的要求。

图1 航空信息网络示意图

软件定义航空信息网络[3,11]利用SDN逻辑集中控制的网络管控策略,能够实时掌握航空信息网络全局视图,实现对航空信息网络中业务流量的优化调度,满足网络中多用户需求,改善整体性能。控制器部署作为构建控制平面的前提,对提升网络性能具有重要意义,而控制平面中单控制器通常存在单点失效、处理能力受限等问题,因此,多控制器部署架构已经成为目前有效的解决方案。多控制器部署架构包括平面式架构[12]、垂直式架构[13]和混合式架构[14]。由于高空节点的移动性和链路的不可靠性易造成网络通信中断,在瞬息万变的战场中控制器节点也存在一定的故障风险,因此地面网络中的平面式多控制器架构将不再适用。考虑到上述因素,航空信息网络应采用混合式的控制器架构对网络进行集中管控,本文借鉴文献[15]所构建的混合式控制器架构模型,结合具体的应用场景设计一种航空信息网络下的混合式多控制器架构,如图2所示。

图2 混合式多控制器架构示意图

混合式多控制器架构中的控制平面由全局控制器(Global Controller,GC)和本地控制器(Local Controller,LC)组成,其中:GC可从全域战场视角对航空信息网络实施集中管控,应部署在信息综合处理能力和生存能力较强的飞机节点上,如指通机、预警机等,其控制优先级最高;LC负责管控其自身控制区域内的网络节点,考虑到航空信息网络的实际需求及特点,可在每个航空平台上布置LC,实际中网络根据自身状态及GC的部署策略开启或关闭相应的LC,实现对其动态部署。

1.2 数学建模

软件定义航空信息网络中的多控制器部署问题描述如下:

1)G(V,E,Vc,Ec)表示航空信息网络拓扑,其中,V代表网络中飞机节点集合,E代表飞机节点间的通信链路集合,Vc代表网络中部署的控制节点集合,Ec代表控制路径集合,且Vc⊆V,Ec⊆E。

2)本文假定已知混合式多控制器架构下GC的部署个数和位置,仅对控制平面中的LC进行部署,下文所提的控制节点与LC节点均为同一概念。

3)考虑到实际情况,网络中所有飞机节点均应布置控制器,控制器按照具体部署策略相应打开或关闭。当飞机节点i上的控制器打开时,节点i为控制节点;当控制器关闭时,节点i为交换节点,也称作普通传输节点,网络中任意节点均有机会成为控制节点或交换节点。

4)控制路径包括LC与GC节点之间的路径以及交换节点与LC节点间相连的路径。由于GC的优先级最高,因此GC之间单独配置控制路径,实现对网络视图信息的共享。其余控制路径为带内方式,不单独配置控制路径,即控制信息和数据信息通过相同的路径进行传输。

5)假定网络中节点和链路发生故障的概率均是独立的,po和pv分别表示链路中断概率和节点失效概率,有0≤po<1,0≤pv<1。

6)网络中每个LC在同一时间内只能由唯一的GC控制,每个交换节点也只能由唯一的LC控制。

为方便描述多控制器部署问题,现对具体数学模型中的符号进行说明,如表1所示。

表1 符号说明

根据上述分析,可将软件定义航空信息网络中的多控制器部署问题建立如下目标函数:

minf=f1+f2

(1)

(2)

(3)

s.t.pv,po∈[0,1);∀v∈V,e∈E

(4)

btjcl=htl;l∈Vc,t,j∈V

(5)

(6)

(7)

l∈Vc,e∈E,g∈{GC}

(8)

式(1)表示最小化控制路径故障率;式(2)表示LC节点和交换节点间的控制路径故障率;式(3)表示LC节点与GC节点间的控制路径故障率;式(4)表示节点、链路失效概率取值范围;式(5)表示节点t受控制节点l所管控;式(6)表示网络中部署的控制器个数;式(7)表示一个交换节点只能由一个LC节点管控;式(8)表示各式中变量的取值范围。

2 算法设计

2.1 航空集群域划分算法

在航空信息网络中存在着功能各异的飞机节点,本文参考文献[15],假定在执行某作战任务过程中其网络拓扑保持相对稳定,随着作战任务变化,网络拓扑也相应改变,本文在此基础上对航空信息网络进行进一步集群域划分。

2.1.1 k-means聚类算法

k-means是一种简单高效、快速实现的基于划分原理的聚类算法,其将数据集U={x1,x2,…,xn}按照某种准则划分为若干个子集,其中k为聚类数目,且聚类满足以下约束:

Uj≠∅,j=1,2,…,k

(9)

Ui∩Uj=∅,i,j=1,2,…,kandi≠j

(10)

图3所示为传统k-means算法流程,其中输入为数据集U和聚类个数k(见式(11)),输出为聚类划分结果,算法结束的条件为聚类中心不再发生变化或变化范围在规定的阈值内。

(11)

图3 传统k-means算法流程

由于k-means算法是随机选择初始聚类中心的,聚类结果会随初始聚心的改变而改变,因此本文引入聚类质量评估函数作为聚类效果的评价准则,其中对聚类质量评估函数定义如下:

(12)

(13)

式(12)表示各聚类的内距离和,J值越小则代表聚类的效果越优;式(13)表示集群域j的聚心。

2.1.2 改进k-means聚类算法

传统k-means聚类算法是一种贪婪算法,容易陷入局部最优,并且该算法选择的初始聚心极有可能偏离数据密集区,若初始聚心位于孤点或者偏远点,则会导致划分的集群域性能变差。针对该问题,本文参考文献[16-17]中提出的离群因子对k-means算法初始聚心位置随机这一不足加以改进,设计一种基于离散因子(Discrete Factor,DF)的改进k-means算法,通过计算各节点的离散因子值,并选择合适的离散因子值所对应的节点作为集群域初始中心,避免网络中的孤点或离散点成为初始聚心,最终得到的集群域也将更加合理。算法描述具体如下:

定义1数据x的第k距离

x的第k距离dk(x)指在数据集合U中存在数据o,数据o与数据x之间的距离记为d(o,x),当满足下述条件时,x的第k距离dk(x)等于d(o,x):

1)数据集U中至少存在k个数据o′∈D{x}满足d(x,o′)≤d(x,o) 。

2)数据集U中至多存在k-1个数据o′∈D{x}满足d(x,o′)

定义2数据x的第k距离邻域

数据x的第k距离邻域指不超过数据x的第k距离内所有数据的集合,其表达式如式(14)所示,可以看出,若该集合较大,则说明数据x的第k距离邻域较大,表明数据偏离程度较大,反之偏离程度较小。

Nk(x)={o∈D{x}|d(x,o)≤dk(x)}

(14)

定义3数据x的离散因子

数据x的离散因子Dk(x)指在(x)的第k距离范围内,集合U中数据的平均分布密度大小,Dk(x)值越大,则x越可能成为离群点,其计算公式如下:

(15)

(16)

本文利用欧式距离计算出数据x的第k距离大小,并根据式(14)得到数据x的第k距离邻域,最后在x的邻域内计算出其余节点相对x的平均分布状况,依次对集合U内数据进行计算,得到集合U内所有节点的平均分布密度大小。本文基于离散因子的改进k-means算法描述如下,其通过计算集合U中各数据的离散因子值,找出离散因子值较小的节点作为候选初始聚心集合,在该集合中通过计算距离进而得出最终的聚心位置。

算法1改进的k-means算法

输入数据集U,聚类个数k,取样系数α

输出聚类结果Uj(j=1,2,…,k)

1.for each xi∈U

2.计算xi的DF值,并将计算结果按照升序排列到ListDF中

3.选择ListDF中前n×α个数据,生成候选初始聚心集合CandidateClusterSet

4.令C=∅,在CandidateClusterSet中选择DF值最小的数据xi作为初始聚心C1,C={C1},并从CandidateClusterSet中删除该数据,Update CandidateClusterSet

5.for each xi∈CandidateClusterSet

6.计算数据xi与C1之间的欧氏距离,选择距离最大的数据点作为第2个初始聚心C2,C={C1,C2},并从Candidate ClusterSet中删除该数据,Update CandidateClusterSet

7.for each xi∈CandidateClusterSet

8.分别计算xi与{C1,C2}之间的距离,将计算结果相加,选择最大值所对应的数据作为下一个初始聚心C3,C={C1,C2,C3},并从CandidateClusterSet中删除该数据,Update CandidateClusterSet

模糊PID控制器采用单片机编程设计，由于MSP430单片机内部没有专用的浮点数处理器，因此在数据的处理过程中，浮点数的计算是通过特定的算法程序来实现，如果采用浮点数计算来进行数据处理，将消耗大量的CPU资源，同时数据的处理周期较长，影响其单片机的实时控制，因此在数据处理时应尽量少用实型数据计算处理。在实际设计中将浮点数的小数部分放大，在满足精度要求的基础上，尽可能采用整形数据来处理数据计算，也可以采用长整形来实现数据的处理（见图4）。

9.Repeat and Update C

10.until i>k

11.输出k个初始聚心结果uj( j=1,2,…,k)

12.从得到k个初始聚心出发,利用最短路径算法求出聚类结果

根据算法1可得到最终的聚心分布结果,相比于传统k-means算法,该算法有效地避免了聚心位于孤点或偏远点,使得聚心分布更加合理。算法在构造集群域时主要考虑节点的分布特点,而在实际部署过程中由于LC存在处理能力受限等问题,易造成某LC负载过载或欠载,从而引起数据拥塞或不能充分利用资源等问题,本文在此基础上加入LC负载受限这一约束条件对集群域划分结果进行优化调整。通过引入负载均衡指数B对各集群域间的负载是否均衡进行计算判断,其表达式如下:

(17)

(18)

其中,a(xi)表示节点xi向其集群域内的LC提交的数据请求信息,且集群域内所包含节点提交的总数据请求信息不能超过该集群域内LC的负载能力。LC负载约束的集群域划分算法描述如下:

算法2LC负载约束的集群域划分算法

输入初始聚心结果uj,负载均衡指数B

输出LC负载约束的聚类划分结果Uj

1.利用改进k-means算法求出初始聚心。

2.按照最短距离算法将xi分配给各uj,形成集群域Uj。

3.计算各集群域内LC负载以及负载均衡指数B,并判断B是否符合预先设置值,若符合,则转到步骤5,否则执行步骤4。

4.将LC过载对应的集群域内节点分配至距离次短的集群域内,并转到步骤3。

5.得到LC负载约束的集群域划分结果。

2.2 集群域内的控制器部署算法

将航空信息网络划分为多个集群域后,在集群域中以控制路径总故障率最小为目标进行LC部署,其目标函数如式(1)～ 式(8)所示,本文采用一种改进的离散粒子群算法BPSO对目标函数进行求解。

2.2.1 离散粒子群算法

离散粒子群优化算法是一种基于群体智能理论的优化算法,其用空间中的粒子表示问题的解,并根据适应度函数判断粒子的好坏,粒子依据个体最优和全局最优进行位置更新,具有收敛速度快、易实现等特点[18-20]。BPSO算法中的粒子Xi由d维二进制编码组成,将粒子Xi=(xi1,xi2,…,xid)的每一维限制为0或1,其速度Vi=(vi1,vi2,…,vid)不加限制,每个位根据式(19)改变速度,改变后的速度转换为位变量取1的概率,通常利用式(20)中的sigmoid函数计算该概率值,在算法搜索过程中,粒子Xi通过自身和种群状态对其位置动态调整,其每一维的速度和位置计算公式如下:

(19)

(20)

(21)

2.2.2 改进的离散粒子群优化算法

由上述分析可知,BPSO算法中的sigmoid函数仅能求解出粒子位取1或者取0的概率,无法求出粒子位的变化值大小。在实际生活中,人们在解决问题时通常会依赖以往的个人历史经验和社会历史经验[22]。 结合上述分析,本文提出一种改进的离散粒子群算法进行求解。

(22)

(23)

(24)

(25)

在寻找最优解的过程中,粒子的好坏程度用适应度函数来评价,本文用式(1)作为改进BPSO算法的适应度函数,即F=f,若某粒子的适应度函数值小,则代表该粒子所对应的解更优,否则较差,集群域内的LC部署算法描述如下:

算法3改进BPSO算法的控制器部署算法

输入各集群域Uj

输出控制器部署方案

1.设置粒子种群规模N,迭代次数Tmax,控制器数目k。

2.初始化粒子位置Xi,速度Vi,个体最优pid并计算全局最优pgd。

3.计算当前时刻粒子的适应度值F。

4.比较当前时刻粒子的适应度值F与个体最优下的适应度值和全局最优下的适应度值大小,判断是否更新个体最优和全局最优。

5.更新粒子速度Vi并根据表2更新粒子位置Xi。

6.是否达到迭代次数上限T,若未达到,则执行步骤3。

7.判断控制器数目i

8.得到不同的控制器个数k以及不同的LC部署方案。

上述LC部署算法根据式(19)对粒子速度进行更新,在对粒子位置更新时采用如下策略:

1.产生随机数r = rand()

if r < α then xi= 1 else xi=0

if r < 1- α then xi=1 else xi=0

if r < β then xi= 1 else xi=0

5.else

if r < 1- β then xi= 1 else xi=0

3 仿真结果分析

3.1 仿真设置

本文设置航空信息网络的范围为600 km×600 km,为体现出网络的动态性,在该范围内分别随机生成2种大小规模不同的网络拓扑,小规模网络包括36个节点和84条链路,大规模网络包括72个节点和176条链路。假定只有一个GC,且GC的位置随机指定,并忽略GC的数量和位置对网络性能和部署结果造成的影响。在部署LC过程中,假定所有LC的处理能力和负载容量均相同,所有传输节点向LC传输的请求信息量也相同,节点和链路发生故障的概率分别为[0,0.03]和[0,0.05]内的随机数。此外,为体现2种不同规模网络中部署LC的差异性,在小规模中的每个集群域内仅部署一个控制器,而在大规模网络中每个集群域内部署若干个控制器。

在仿真中同时设置Random算法、ANIGA算法[9]和Survivor[23]算法进行性能对比。Random算法在网络中随机选择节点部署LC;ANIGA是一种基于启发式的随机搜索算法,其通过循环迭代找出满足中断概率条件时的LC数量和位置。Survivor算法通过选择不相交路径最多的节点部署LC,并按最短距离为其分配交换机节点。此外,为排除干扰因素,仿真中将实验重复20次,并计算结果的平均值作为最终结果输出。

3.2 结果对比与分析

图4(a)和图4(b)分别为传统k-means算法和改进算法在2种不同网络中的聚类质量评估函数值,可以看出,改进算法的J值波动范围与k-means算法相比较小,且整体J值均低于k-means算法,这是由于在改进算法中加入了负载均衡模块,划分的每个集群域中节点个数差异较小,进而计算出的J值波动范围较小。此外,由于改进算法在选择初始聚心时充分考虑到网络中各节点的离散系数,有效地避免了孤点或离散点成为初始聚心,进而计算出的J值更小,说明了采用改进算法划分的集群域更合理。

图4 聚类质量评估函数值

图5(a)显示了在小规模网络中控制路径故障率随集群域个数变化的情况,可以看出,随着集群域个数的增加,4种算法下的控制路径故障率均逐渐降低,如集群域个数为2、6、10时对应的控制路径故障率分别为0.246、0.124、0.093,这是由于随着集群域个数的增加,小规模网络中的控制器数量随之增加,控制节点与交换节点间的控制路径增多,进而控制路径的可靠性增大。

图5(b)显示了在大规模网络中控制节点所占比例对网络控制路径故障率的影响,可以看出,在各集群域中控制节点比例逐渐增加的同时,控制路径故障率相应地减小,如集群域个数为4时,当控制节点比例为0.2、0.3和0.4时所对应的控制路径故障率分别为0.386、0.363、0.327,可见在集群域中通过增加控制器的个数能够有效地降低网络控制路径故障率。

图5 控制路径故障率

图6(a)显示了小规模网络下控制器间的数据同步时延,可以看出,随着集群域个数的增多,控制器间同步时延呈现上升的趋势,如优化前和优化后同步时延分别增加了2.741 ms和4.212 ms,这是由于随着集群域数量的增加,网络中的控制器个数随之增加,控制器节点间的控制路径增加,进而造成网络中的同步时延增大。此外,随着集群域个数的增多,集群域中节点数量减少,控制器部署位置的差异度也随之减小,从而优化前后控制器间同步时延的差距也逐渐缩小。

图6(b)显示了大规模网络下不同控制器数量对控制器间时延的影响,可以看出,随着集群域个数的增加,图中曲线的变化趋势较为缓慢,这是由于当集群域个数较少时,各集群域内的节点数量较多,其集群域内的控制节点也相对较多,而当集群域个数增多时,集群域内的节点数量减少,在同等控制节点数量比例下其集群域内的控制节点也相应减少。因此,尽管集群域个数在逐渐增多,但其控制器总数量与集群域个数较少时网络中的控制器总数量相差不大,意味着在网络中不能一味地追求集群域的数量,如图中集群域个数k=8时网络中的控制器间同步时延最小,在该集群域数量下可获得较小的时延开销。此外,在相同的集群域个数下,随着网络中控制节点比例的增加,控制路径数量也随之增加,进而使得控制器间同步时延开销增大,如当控制节点比例从0.2增加到0.4时,其控制器间平均时延值分别增加了1.608 ms和2.896 ms。

图6 控制器间时延

4 结束语

本文针对软件定义航空信息网络架构中的控制平面可扩展性问题展开研究,将航空信息网络划分为多个集群域。在划分集群域时,为避免集群域中心位于孤点或偏远点,提出一种基于离散因子的改进k-means算法,结果表明该算法得到的聚心分布更合理。在集群域内LC部署方面,以控制路径故障率最小为优化目标设计改进的BPSO算法。仿真结果验证了本文在解决控制器部署问题方面的有效性。本文重点考虑控制器无故障下的部署方案,下一步将针对控制器的可生存性进行研究,以确保控制器工作的可连续性。