基于切比雪夫神经网络的软件定义卫星网络智能路由策略*

梁 俊，孙伟超，肖 楠，陈威龙，郭子桢

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

传统的卫星网络依赖于封闭和有计划的体系架构[1]，面临配置更新、新通信和网络技术的引入、差异化服务的提供以及卫星和地面网络集成等挑战[2-3]。软件定义网络(Software Defined Network, SDN)实现了控制平面和数据平面的完全解耦[4]，具有灵活性、可编程性和逻辑集中性等特点，能够提高网络资源利用率[5]，简化网络管理流程，降低运营成本，促进了网络的演进和创新[6]。

国内外许多学者对在卫星网络中引入SDN进行了探索。文献[7]针对卫星网络通信存在长时延和频繁的地面-卫星切换以及卫星网络配置成本较高的问题，将SDN与卫星网络相结合，增加了网络的灵活性以及可扩展性，降低了星上处理开销。文献[8]提出了一种聚合SDN的新一代空天地一体化网络，网络部署方式灵活，网络可扩展性强，资源利用率高。文献[9]提出了基于SDN架构的低地球轨道(Low Earth Orbit, LEO)卫星网络，将地面网络控制中心作为SDN控制器，计算路由策略，优化了资源利用方式。文献[10]针对传统卫星系统架构导致的卫星通信系统的管理和配置效率低下、管理不灵活等问题，提出了一种基于SDN和网络功能虚拟化的空间地面综合多层卫星通信网。

然而以上文献均采用OpenFlow协议作为SDN南向编程接口。随着OpenFlow版本的推进，不断扩展的“多级流表”以及复杂的流表项查找、匹配问题给资源受限的LEO卫星的存储和处理能力带来很大挑战[11-12]。

神经网络(Neural Network, NN)是一种自学习、自调整的智能工具，能够进行大规模的并行计算[13]。NN模型可以从海量数据中获取目标，在分类、模式识别、预测等多个领域都有着广泛的应用。在SDN中，通过逻辑集中的控制器容易获得大量的流量数据和网络信息。文献[14]首次提出一种在SDN中，用径向基函数(Radial Basis Function, RBF)神经网络代替流表的方法，节省了存储空间。然而支持RBF算法的NN各个权值不能完全独立地求解，难以在星上并行运算，且需要进行烦琐的高阶矩阵求逆运算，难以适应星上路由的要求。以正交多项式为基础的Chebyshev神经网络函数逼近性能优越，基函数的正交性保证NN在多项式的节点处权值求解迅捷[15]。

通过以上分析，提出一种基于Chebyshev神经网络的SDN卫星网络智能路由架构。通过训练神经网络获取数据流的传输模式用于预测路由，同时，用NN代替流表以节省三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)的存储空间，提高数据流的路由和转发效率。

1 系统架构

采用单层卫星多层控制器(Single-layer Satellite Multiple-layer Controller, SSMC)架构，将基于SDN的卫星网络架构分为三层：地球同步轨道(Geostationary Earth Orbit, GEO)卫星控制平面、LEO卫星数据平面、地面控制平面，如图1所示。各平面的功能模块如图2所示。

图1 系统架构Fig.1 System architecture

图2 各平面功能Fig.2 Various plane functions

1.1 控制平面

控制平面由GEO卫星控制层和地面控制层组成，主要功能是利用其强大的计算能力，收集和处理网络流信息并通过训练NN获取数据流传输模式。其中，GEO卫星为局部控制器，只负责管理自身覆盖区域内的LEO卫星交换机，当LEO卫星发出路由请求时，如果数据流的源和目的节点都在同一颗GEO卫星覆盖区域内，则GEO卫星发挥控制器的功能；否则，GEO卫星作为LEO卫星与地面控制器通信的中继节点，将路由请求消息转发到地面控制器。地面控制器为全局控制器，掌握网络全局拓扑变化、流量分布、节点负载等信息[16]。

地面控制器的核心功能模块描述如下：

1)网络监控模块。负责实时监控LEO卫星网络全局的状态和拓扑变化。

2)数据收集模块。负责收集GEO卫星传来的路由请求消息，从中提取数据流的源、目的地、业务类型和路径信息，用于训练NN。

3)数据预处理模块。负责对收集到的数据进行预处理，构造用于NN训练和测试的样本集。包括数据流路径的预处理、训练集和测试集的构造、样本集的归一化等。

4)NN训练模块。负责训练NN，并根据历史流量数据获得数据流的传输模式。

5)NN包生成模块。负责利用NN参数创建NN包，具体格式见1.4节。

6)NN包下发模块。负责将NN包发送给管理源和目的节点的GEO卫星控制器，并下发给所有相关LEO卫星。

GEO卫星控制器除了具有以上功能模块，还具有数据中继模块，作为地面控制器和LEO卫星的中继节点。此外，GEO卫星控制器的网络监控、数据收集模块都是面向自身覆盖区域内的LEO卫星网络。

1.2 数据平面

数据平面由LEO卫星交换机组成，核心功能是利用控制器下发的NN预测数据流的路径，对数据流进行路由转发。其核心功能模块描述如下：

1)NN创建模块。LEO卫星交换机接收到NN包后，根据存储在NN包中的结构参数创建NN。

2)路径预测模块。当接收到用户发送的业务数据后，从中提取三个元组信息(源、目的地、业务类型)作为NN的输入进行路径预测。

3)数据流转发模块。根据路径预测模块得到的路径转发数据包。

1.3 NN预处理

在训练NN之前，需要对其进行预处理，主要包括样本集的归一化以及训练集和测试集的构造。

当有数据流经过网络时，控制器从数据流中提取源节点Src、目的节点Dst、业务类型Type用于构造样本集，并记录数据流的传输路径Path。进行NN预处理时，以样本(Src,Dst,Type)作为NN的输入，以Route作为输出。随机选取30%的样本作为训练集，其余70%的样本作为测试集[14]。

为了提高NN的学习效果，对样本(Src,Dst,Type)进行归一化处理。

(1)

(2)

(3)

其中，Src′、Dst′、Type′分别是Src、Dst、Type的归一化值。Srcmax、Srcmin，Dstmax、Dstmin，Typemax、Typemin分别是Src、Dst、Type的最大值和最小值。每个变量的归一化值在0和1之间。

在样本集归一化后,控制器使用训练集训练NN，直到预测成功率达到预设标准，NN训练结束。之后，控制器依据训练好的NN创建NN包，并将NN包下发给相关LEO卫星交换机。

1.4 NN包

为了将NN包与一般的数据包区分开来，设计了NN包的特定格式。NN包由NN的结构参数组成，包括输入层节点个数、隐藏层节点个数、输出层节点个数、输入层与隐藏层连接权值、隐藏层之间的连接权值、隐藏层与输出层之间的连接权值等。

以Chebyshev神经网络包为例，Chebyshev NN输入层和隐藏层之间的连接权值为固定值1，且只有一个隐藏层。因此，不考虑Chebyshev NN包中输入与隐藏层之间的连接权值、隐藏层之间的权值。

M、N和K分别表示输入、隐藏和输出层中的节点数，Oi表示i次正交多项式，Wij表示第i个隐藏节点与第j个输出节点之间的权值。Chebyshev NN包格式如图3所示。

图3 Chebyshev NN包的格式Fig.3 Format of the Chebyshev NN packet

2 Chebyshev神经网络智能路由策略

传统的多层感知器(Multi-Layer Perceptron, MLP)神经网络采用的误差反向传播(Back Propagation, BP)算法训练时间长，易陷入局部最小值；而支持向量机(Support Vector Machine, SVM)和RBF算法的各个权值不能完全独立地被求解，且需要进行烦琐的高阶矩阵求逆运算，难以在星上并行计算。因此这些训练算法难以适应星上路由的要求[15]。

Chebyshev神经网络是一种基于Chebyshev正交多项式的神经网络，逼近性能优越，基函数的正交性保证神经网络在多项式的结点处权值求解迅捷，能够较好地满足卫星网络的需求。基于第1节的系统架构，提出了一种基于Chebyshev神经网络的智能路由策略(Intelligent Routing Strategy based on Chebyshev Neural Network, IRSCNN)。

2.1 Chebyshev神经网络模型

一元Chebyshev NN由一个输入层、一个隐藏层和一个输出层组成，如图4所示[15]。其中Oj(xi)代表j次正交多项式，其系构成了NN的单隐藏层结构，Wij是Oj(xi)的权值。NN训练的目标是通过训练集，用已知的正交多项式对未知进行线性逼近，即求yi。

图4 一元Chebyshev神经网络模型Fig.4 Monadic Chebyshev neural network model

(4)

以(Src,Dst,Type)作为Chebyshev NN的输入，得到数据流的路径Route作为NN的输出。因此需考虑三元Chebyshev NN模型，设输入为三维向量[x1,x2,x3]T，输出是关于三元函数yi=f(x1,x2,x3)的一个精确逼近。根据文献[15]得：

f(x1,x2,x3)=ON1N2N3(x1,x2,x3)

(5)

式中，f是待模拟的函数，O是用以逼近xj的kj次多项式，Wj1j2j3是该正交多项式组合的权值。

另外，神经网络的输出是一个或一组标量值，而NN的输出应该能表示成一条最优路径，因此需要一种映射方法来形成标量值和最优路径之间的映射。采用路径标量表示[15]。

(6)

式中，Ri为所有到源节点Src链路距离为i的节点Nij组成的集合，j为第i个子集内的节点数。

2.2 路由算法

当一个新的数据流到达源节点S时，S首先检查是否已经构建了NN。如果已经构建了NN，则交换机从到达的数据流中提取(Src,Dst,Type)，并将它们作为NN的输入来预测路径，并对其进行路由转发。

如果没有构建NN，则将数据流相关信息封装到路由请求消息中，发送到控制器。GEO卫星控制器接收到该请求时，将最近训练完的NN下发给所有交换机。交换机在接收到NN包后，根据从NN包中得到的结构参数构建NN，然后利用所提取的流信息作为NN输入来预测路径，对数据流进行路由。

对于S，每次切换完成后，S依据控制器下发的NN包构造一个Chebyshev NN训练器。具体路由算法由两部分组成。

2.2.1 初始化阶段

当一个新的数据流到达源交换机S时，S从第一个数据包中提取(Src,Dst,Type)，此时没有训练好的NN存储在交换机中，S向控制器C发送包含交换机编号以及数据流(Src,Dst,Type)信息的路由请求消息。当C收到S发送的路由请求消息时，将最近训练完的NN分发到所有相关交换机中。交换机在接收到NN包后，根据从NN包中得到的结构参数构建NN，然后利用所提取的流信息作为NN输入来预测路径，对数据流进行路由。

控制器在构造新的Chebyshev NN时，通过1.3节生成数据集对神经网络进行训练，在控制器对NN的训练过程中，利用Chebyshev多项式的正交性，采用文献[17]快速权值确定算法求得。

虽然与直接调用路由算法相比，增加了NN训练过程的计算复杂度，但占用存储空间的减小，以及丢包率和网络拥塞的减少使得算法总体性能优越。

2.2.2 正常转发阶段

初始阶段结束后到下次切换前，算法处于正常转发阶段。训练完的NN相当于一张“路由表”存储在卫星节点中。新到达的路由请求作为测试样本输入到NN以得出最优路径，并根据路径对数据流进行转发。

当出现S预测路由失败、一些链路失效或过载、网络拓扑改变、主机请求超时之中任一情况时，S发送重路由请求消息到C。重路由请求消息包含节点编号以及数据流(Src,Dst,Type)信息。然后，C根据重路由算法重新计算最优路径，并将其下发给交换机。

同时增加一个负反馈机制，路由失效后，目标节点将反馈一条错误通知信息告知源节点路由失效。收到错误通知信息后，S将该分类错误的路径添加到重路由请求消息中发送到控制器，作为反例进一步训练NN。该机制帮助C凭借错误通知信息感知网络中链路信息的更新，并通过进一步的训练对NN进行相应的调节，为以后的选路提供最新的路由信息。

在进行路径预测时，将数据流的业务类型作为NN的一个输入向量，根据用户在带宽、时延、时延抖动、误码率等方面的要求，可以有效地分配网络资源，使路径能够更好地满足不同用户对服务质量(Quality of Service, QoS)的要求。

对于业务类型，根据IP网络中的QoS分类标准[18]将所有网络应用划分为6类，见表1。其中：U表示“未指定”，TD、DV、LR和ER分别表示“传输时延”“时延抖动”“丢包率”和“误码率”。

其实我没有那么与世隔绝，我们的生活与外面的世界只是有着几年的延时而已，其他的一切正常。我们默认的岛歌是《太平洋的风》，那是我们学校从陆地来的音乐老师教我们唱的。他说，这首歌是他写的：最早的一件衣裳，最早的一片呼唤，最早的一个故乡，最早的一件往事，是太平洋的风，徐徐吹来，吹过所有的全部。

表1 业务类型划分

2.3 重路由算法

当数据流到达交换机时，交换机提取(Src,Dst,Type)，然后使用Chebyshev NN来预测数据流的路径。然而，路径预测成功率达不到100%。因此，设计了重路由算法，见算法1。当路由预测失败时，交换机将重路由请求消息发送给控制器。

算法1 重路由算法

当接收到请求消息时，控制器根据重路由算法重新计算数据流的最佳路由。

重路由算法的主要思想是根据当前的网络状态信息(例如带宽、延迟和错误率)选择最短路径，以满足尽可能多的QoS约束条件。首先，源地址SrcIP和目的地址DstIP分别映射到相应的源节点Src和目的节点Dst，并将数据流的业务类型Type映射到相应的QoS参数(即带宽、延迟和差错率)。其次，对不能满足带宽要求的所有链路进行过滤。最后，计算满足时延要求的路径集DLPathSet，并从DLPathSet中选择满足差错率要求的路径ERPathSet。如果ERPathSet包含多个路径，则选择最短路径作为最优路径。

2.4 复杂度分析

在本节中，分析了所提出的路由策略的时间复杂度和空间复杂度。

路由策略涉及的过程主要包括Chebyshev NN训练、NN包下发、NN创建、数据流信息提取、NN路径预测。暂不考虑控制器与交换机之间通信(即NN包下发)的时间开销。

由上节可知，Chebyshev NN训练过程的时间复杂度T1和空间复杂度S1均为O(1)。

Chebyshev NN创建过程的时间复杂度T2为O(mn+nk)，空间复杂度S2为O(mn+nk)。这里，m和n分别是RBFNN中的输入节点和隐藏节点的数目，k是RBFNN中输出节点的数目。

数据流信息提取过程中从数据包中提取m个字段作为Chebyshev NN的输入，其时间复杂度T3和空间复杂度S3均为O(m)。

基于上述分析，所提出的路由策略的时间复杂度为：

T=T1+T2+T3+T4

=O(1)+O(mn+nk)+O(m)+

O(mn+nk)～O(mn+nk)

(7)

所提出的路由策略的空间复杂度为

S=S1+S2+S3+S4

=O(1)+O(mn+nk)+O(m)+

O(mn+nk)～O(mn+nk)

(8)

3 仿真与性能评估

3.1 仿真设置

基于斯坦福大学研发的轻量级测试平台Mininet，选取改进的ONOS控制器作为实验控制器。为了避免Mininet和ONOS之间的干扰，将两者以虚拟机的形式部署在两个物理设备上。选取6台均有相同配置的实验机器，机器的配置为Intel Core i5 3.3 GHz、4 GB RAM、2 Gbp网卡，基于Ubuntu 14.04 LTS系统。借助MATLAB工具对实验结果进行分析。采用类似文献[16]中的仿真场景，该场景由3颗GEO卫星控制器、48颗LEO卫星交换机、3个地面控制器组成。

不同于一般的网络，卫星网络中的节点处在不断的运动之中，节点间时延和链路连通性也在不断发生变化。本文仿真模型中存在轨内链路、轨间链路、层间链路三种星间链路(Inter-Satellite Link, ISL)，为了模拟真实卫星网络的动态变换特性，根据文献[18] 在t时刻，星间链路ISLSj→Si的传播时延定义为：

D(Sj→Si,t)=r(Sj→Si,t)/c

(9)

ISL的链路稳定性函数为：

(10)

采用静态和动态链路设计方案，通过端到端传输时延和丢包率对链路稳定性进行分析，星间链路的传输速率为20 Mbit/s，将(wt,wd,ws)取值为(1/3,1/3,1/3)，在考虑链路传输时延和生存时间的基础上同时考虑真实空间干扰因素的影响，以提高传输的连续性和减少网络丢包率。

为了模拟真实的流量状况，采用文献[19]中的数据流模型。地球表面被划分为12×24=288个区域。每个区域的数值代表上网用户的数量，已被106整除。对于每106个上网用户，流量为1 Mbit/s。

为了方便与基于神经网络的SDN智能路由方案(Neural Network-based Intelligent Routing Scheme for SDN, NNIRSS)[14]对比，根据QoS分类标准，将所有业务应用分成6类，并指定相应的QoS参数，如表2所示[14]。

表2 QoS参数

仿真实验由两部分组成。在第一部分中，利用从上述场景中收集到的历史流量数据，对不同的业务流进行分类，并构造训练集和测试集来训练NN以寻找最优参数，NN训练完成后，将NN包存储在控制器中。在第二部分中，将提出的路由策略与基于传统OpenFlow的路由方案(Traditional OpenFlow-based SDN Routing scheme, TOSR)以及NNIRSS[14]进行比较。

3.2 仿真结果分析

通过以下几个指标较全面地评价IRSCNN的性能。

1)NN包占用的存储空间(Storage Space, SP)：在提出的策略中，流表被NN包替换，对流表占用的存储空间和NN包占用的空间进行对比。

2)包传递率(Packet Delivery Rate, PDR)：数据包成功到达目的节点的比例。

3)丢包率(Packet Loss Rate, PLR)：丢失数据包占所有数据包的比例。

4)包传输时延(Packet Delay, PD)：端到端的数据包传输时延。

每个仿真实验重复10次并取其平均值作为度量值。

3.2.1 实验1：SP

在基于OpenFlow的SDN中，数据流根据流表进行路由和转发。流表存储在TCAM中。然而，在所提出的路由策略中，数据流根据NN进行路由和转发，不需要存储在TCAM中。为了便于存储空间比较，假设SDN中的每个交换机包含1000个流表项。在OpenFlow V1.1.0中，流表项匹配域的最大长度是356 bit。因此，流表项占用的TCAM存储空间约为444.57 KB。IRSCNN与NNIRSS之间SP的对比结果如图5所示。即使考虑将NN存储在TCAM中，Chebyshev NN占用的TCAM存储空间也远小于444.57 KB。且与采用RBFNN的NNIRSS相比,由于空间复杂度降低，进一步减少了存储空间。

图5 SP对比Fig.5 Comparison of SP

因此可以得出，所提出的IRSCNN可以显著减少占用的TCAM存储空间。

3.2.2 实验2：PDR

IRSCNN、NNIRSS与TOSR之间PDR的对比结果如图6所示。随着流量到达速率的增加，网络中的数据包总数增加，导致网络拥塞。由于交换机的处理能力有限，流中的一些数据包被丢弃，无法成功地路由和转发到目的地。由图6可知，无论IRSCNN、NNIRSS还是TOSR，相应的PDR都随着流量到达速率的增加而变小。

图6 PDR对比Fig.6 Comparison of PDR

然而，当流量到达率变大时，IRSCNN的PDR是高于NNIRSS和TOSR的。TOSR对数据流采用最短路由策略，在TOSR中，流中的数据包沿最短路径路由并转发，导致来自相同数据流的数据包沿着同一路径路由。在IRSCNN和NNIRSS中，流中的数据包根据其相应的业务类型进行路由和转发，即不同类型的数据包在IRSCNN和NNIRS中沿不同的路径进行路由和转发，且采用Chebyshev NN的IRSCNN相比NNIRSS求解更迅速，处理速度更快。因此，传送到目的地的数据包的总数大于NNIRSS和TOSR。

3.2.3 实验3：PLR

IRSCNN、NNIRSS与TOSR之间的PLR比较结果如图7所示。随着流量到达速率的增加，三者的PLR都变高，而IRSCNN的PLR比NNIRSS和TOSR的PLR要小。其原因与上述PDR比较相似。在TOSR中，流中的数据包被路由并转发在最短路径中。而在IRSCNN和NNIRS中，基于不同的业务类型，数据包沿着不同的路径被转发。随着流量到达速率的增加，TOSR中由于在相同路径上路由的数据包过多引起网络拥塞而丢弃了大量的数据包，且采用Chebyshev NN的IRSCNN相比NNIRSS求解更迅速，处理速度更快，可以减少拥塞。因此，IRSCNN中丢弃的数据包的数量要小于NNIRSS和TOSR中的丢弃的数据包的数量。

3.2.4 实验4：PD

IRSCNN、NNIRSS与TOSR在不同流量到达速率下的PD比较结果如图8所示。无论在IRSCNN、NNIRSS还是TOSR中，随着流量到达速率的增加，流中的数据包总数都变得更大。过多的数据包会导致网络拥塞。网络拥塞越严重，数据包传输到目的节点的时间就越长。

图8 PD对比Fig.8 Comparison of PD

此外，由图8可知，TOSR、NNIRSS的PD的长度比IRSCNN更长。虽然TOSR采用最短路由算法，但是随着流量到达率的增加，网络拥塞更加严重，TOSR的PD变得更长。另一方面，在IRSCNN、NNIRSS中，数据包的路由和转发过程不涉及复杂的流表查找和匹配过程，与TOSR相比，NN路径预测耗时更短，同时采用Chebyshev NN的IRSCNN相比NNIRSS求解更迅捷，处理速度更快。

综上，IRSCNN在SP、PDR、PLR和PD性能方面均优于TOSR和NNIRSS，采用的路由策略具有更高数据包传输成功率，更低的丢包率，更低的数据包传输时延，因此在传输时延和链路稳定性方面也具有更好的性能。

4 结论

针对OpenFlow协议中流表扩展导致TCAM存储空间不足的问题，提出了基于NN的软件定义卫星网络智能路由架构，用NN来代替流表，大大减少了占用的TCAM存储空间和相应的硬件成本，取消了复杂的流表生成过程，不再需要查找和匹配流表项，提高了路由效率。并在所提架构的基础上提出基于Chebyshev NN的智能路由策略，LEO卫星根据数据流的业务类型通过训练后的Chebyshev NN来预测路径，满足了应用的QoS需求。最后，通过仿真实验对所提IRSCNN性能进行了评估。仿真结果表明：提出的路由策略能够显著减少占用的TCAM空间，提高路由转发效率。