基于SDN架构的空间信息网络路由策略设计

杨力 滕奇秀 孔志翔,3 蔡睿妍

(1 大连大学信息工程学院，辽宁大连 116622)(2 大连大学通信与网络实验室，辽宁大连 116622) (3 南京理工大学自动化学院，南京 210094)

空间信息网络是一个由深空网络、卫星网络和地面网络构成，实现天、地、空互联的规模巨大、异质异构的复杂网络。随着我国航天技术的发展，加之我国载人航天、空间站、深空探测等空间活动日益频繁，各种航天器种类和数量也在迅速增加，卫星与地面、卫星与卫星之间的通信组网要求越来越迫切。目前，我国在轨运行卫星大都只提供通信信道，星上不具有路由计算功能，路由策略制定只能由地面计算再重新上行，或者个别卫星简单处理后实现星间、星际之间的路由。这样既加重了卫星负载，也严重制约着空间信息网络对灵活、快速组网和有效路由策略的实现[1-2]。软件定义网络(SDN)技术是当前网络领域的新架构思路，通过解耦数据平面和控制平面，实现网络态势与控制的逻辑高度集中，降低数据平面的复杂度，可以将网络资源统一，灵活配置，实现卫星网络与地面网络的融合，统一控制，制定有效的路由策略。

现有的空间信息网络路由方法分为单层路由和多层路由。文献[3]和文献[4]中利用单层卫星网络运行的周期性和规律性，将其运行周期划分为多个时隙。在每个时隙内，将卫星网络视为虚拟静态拓扑，路由策略存储在每个卫星节点中，卫星通信过程中查询对应的转发路径即可。文献[5]中通过卫星地面链路建立源节点和目的节点之间的连接，获得一个时隙内的本地网络拓扑，减少用于建立Dijkstra算法相关矩阵的卫星和网关的数量，降低算法计算复杂度，根据网络拓扑计算路由。但是，此类方法由于运行周期分为较多时隙，需要星上有足够的存储空间，增加卫星负载。同时，对于链路故障，流量变化等情况处理能力较差。文献[6]中对于地球同步轨道/低地球轨道(GEO/LEO)双层卫星网络链路负载不均衡、多媒体业务具有不同服务质量(QoS)要求的问题，提出一种多业务路由算法。该算法结合业务利用率来调整不同业务链路初始权值，从而合理分配网络资源，满足各种QoS要求，优化卫星网络链路利用率。但是，该算法在业务利用率不同时，需要卫星计算业务权值来判断业务链路，增加了卫星的内存占用和运行负担。文献[7]中提出一种基于移动代理的卫星网络动态路由(SDRA-MA)方法，该方法在数据包到达时更新路由，没有数据包则不更新路由。在网络流量稳定时，该方法性能较好，但在网络流量传递频繁时，路由不断更新，性能低于普通路由算法。传统的空间信息网络转发策略由每颗卫星决定，导致网络耦合，给网络管理带来了很大困难，所以人们开始关注网络划分为数据平面和控制平面的SDN。在有关软件定义空间信息网络路由研究中，文献[8]中针对软件定义卫星网络(SDSN)中海量、动态、高优先级的控制流量对数据传输造成的干扰问题，提出一种数据流退让路由(DFRR)策略，考虑链路控制流量的大小对链路的影响，减少选择控制流量较大的链路。该策略有效地减少了链路拥塞，但只减少了影响因素，选择链路时未考虑路由对业务的适用性，并且切换链路增加链路代价。文献[9]中提出多路径承载策略，当卫星运动导致空间链路中断时，能够在降低业务质量的情况下不中断传输，有效地减少资源消耗。同时，提出基于安全因子感知的路由算法，提高全网络路由整体的可靠性和安全性。同样，该策略虽然保证了传输，但是也未考虑传输链路对数据业务是否适用。文献[10]中提出一种基于变形虫的波纹传播(AR)策略，将LEO和中地球轨道(MEO)运行周期的最小公倍数作为系统周期。系统周期分为若干快照周期，将卫星每个时刻位置进行记录，采用AR策略计算路由，系统根据“源-宿”卫星节点间距离，自动选择路由策略，提高运算速度。然而，系统周期为12 h，控制平面制定的路由策略周期过长，不能及时处理空间信息网络高动态造成的时变性问题，并且路由策略未考虑链路因素，对各类业务数据转发没有明显优势。

本文提出一种基于SDN架构的空间信息网络路由策略设计，利用SDN控制器掌握空间信息网络全局信息，获取网络的实时状态，建立路由计算模型，采用改进的遗传算法计算链路代价最小的路由，数据平面根据路由转发各类业务数据，控制平面制定的路由考虑链路状况，每个时间片重新选取路由，具有实时性，适用于各类业务数据。

1 基于SDN架构的空间信息网络模型

SDN架构下的空间信息网络[11]，以OpenFlow协议为基础，具备网络层数据控制分离、集中式可编程的特点，打破了路由功能的垂直整合，控制器对网络集中式管理、灵活控制，使整体网络可控性较强[12-14]。相比传统的卫星网络，在SDN架构下，空间信息网络具有高度可控性。控制平面可以获得全局视图，实时获取网络状态，进行复杂的路由计算，数据平面卫星节点只进行数据转发即可，降低了网络成本和星上开销。

目前，基于SDN架构的空间信息网络大多将地面站作为控制平面，高、中、低轨道卫星作为数据平面转发数据。本文设计的空间信息网络模型，其控制平面包含地面站和GEO卫星两部分，地面站为一级控制器，包含信息存储模块和路由计算模块；GEO卫星为二级控制器，包含节点探索模块和基础转发模块。控制层面采用分级控制，是考虑到地球自转时任务卫星与地面站距离较远，GEO卫星覆盖广，地面站通过GEO卫星将信息传递至数据平面。数据平面由MEO卫星和LEO卫星组成，接收控制器下发的规则对数据包进行快速转发。本文建立基于SDN架构的空间信息网络模型如图1所示，模块功能介绍如下。

(1)信息存储模块：一级控制器接收二级控制器传递的全局拓扑信息，以及链路状态信息。

(2)路由计算模块：根据信息存储模块中的链路时延、带宽和丢包率等信息计算链路的路由代价，利用改进的遗传算法选择出适合每类业务的最优路由。

(3)基础转发模块：二级控制器接收传回的全局信息并转发给一级控制器，同时转发一级控制器计算的流表规则下发到数据平面。

(4)节点探索模块：二级控制器利用链路层发现协议(LLDP)进行链路探索，获取全局拓扑结，在MEO卫星和LEO卫星上部署OpenFlow交换机，对各端口运行状态信息进行统计，统计的信息通过报文上报控制器，解析链路间的时延、带宽和丢包率信息。

图1 基于SDN架构的空间信息网络模型Fig.1 Spatial information network model based on SDN architecture

2 路由策略设计

基于SDN架构的空间信息网络路由策略是由整个网络的协同调度计算出每类业务的最优路由。本文设计的路由策略利用GEO卫星可以探索链路状态和数据转发，解决地球自转时地面站与任务卫星距离较远导致的信息不能及时传达问题，同时GEO卫星覆盖广，收集的链路信息比较全面。具体步骤和策略流程(见图2)如下。

(1)GEO卫星的探索模块周期性通过Packet_out报文发出LLDP数据包。

(2)数据平面的卫星接收到数据包，判断其接收端口是否为控制器端口。若是，将数据包转发出去；否则，将感知数据包通过Packet_in报文发送给控制器。

(3)GEO卫星接收到Packet_in报文，获取2个卫星节点之间的拓扑状态，解析链路带宽、时延和丢包率等链路状态信息，并传至地面站。

(4)地面站接收和存储GEO卫星获取的全局链路状态信息，利用改进的遗传算法计算各类业务数据的路由。

(5)判断转发业务数据的卫星与地面站距离是否较近。若是，则由地面站将路由决策发送到数据平面，MEO卫星和LEO卫星进行数据转发；否则，二级控制器GEO卫星接收地面站的路由决策，下发至数据平面，进行业务转发。

(6)时间周期将要结束时，根据新的链路状态制定的路由以流表形式下发，数据平面在下一个周期根据新的流表规则转发业务数据。

图2 基于SDN架构的空间信息网络路由策略流程Fig.2 Routing strategy flow of spatial information network based on SDN architecture

基于SDN架构的空间信息网络路由策略是路由的产生过程，建立路由模型进行求解，得到转发各类业务的最优路由。

2.1 路由模型

2.1.1 路由模型参数

基于SDN架构的空间信息网络拓扑模型采用G(V,E)表示，V为网络中所有卫星节点的集合，相邻2颗卫星之间的链路集合E={e=(i,j)|i,j∈V}[15]，相邻卫星之间有且只有一条链路，“源-宿”卫星节点间的路由集合为p，定义如下参数。

(1)

pb,k=min (pb,k(m))pb,k(m)≥0

(2)

(3)

式中：pd,k，pb,k，pl,k分别为第k条路由的时延、带宽和丢包率，pd,k(m)，pb,k(m)，pl,k(m)分别为其下第m段路径的时延、带宽和丢包率；N为源卫星节点到目的卫星节点之间相邻2个卫星链路段的个数。

因为不同性质的参数直接加和不能反映出不同因素的综合效果，所以将获得的链路时延参数和带宽参数归一化处理，将原始数据线性化映射到[0,1]的范围，实现对原始数据的等比例缩放，归一化函数为

(4)

式中：xk为链路中“源-宿”卫星节点中第k条路径pk的时延参数或带宽参数，根据归一化处理得到y1,y2,…,yn∈[0,1]，且无量级，n为“源-宿”卫星节点间的路由集合中路由的数量，归一化处理后计算pk的代价ck如下。

ck=w1·pd,y,k+w2·pl,k+w3·pb,y,k

(5)

式中：pd,y,k和pb,y,k别为第k条链路归一化处理的时延参数和带宽参数；w1，w2，w3分别为每个参数所占的权重。

权重选取策略采用判断矩阵法，将所有指标列出来，组成一个n×n的方阵，然后对各指标两两比较并打分，最后对各指标的得分求和，并作规范化处理。构造判断矩阵为

(6)

式中：aij为评价元素i对评价元素j的相对重要尺度，满足aijaji=1。

不同元素间的重要尺度如表1所示。

采用特征根法计算各因素权重过程如下。

表1 重要尺度

2.1.2 路由模型建立

(7)

2.2 改进的遗传算法求解路由模型

在求解路由模型中，“源-宿”卫星节点间的路由集合作为遗传算法的种群，采用改进的自适应交叉概率函数，以牺牲种群多样性为代价提高算法熟练效率，从而快速获得各业务类路由最优解。遗传算法求解代价路由时，当种群迭代到一定次数，或者种群适度值没有明显变化时，停止种群进化，选取最优解[16]，遗传算法流程如图3所示。

图3 遗传算法流程

2.2.1 染色体编码

染色体编码是将实际问题映射到遗传算法思想中[16]，在空间信息网络中，源节点代表染色体第1个位置，目的节点代表染色体最后1个位置，染色体基因序列顺序与路由经过的卫星节点顺序相同，因为路由包含卫星节点个数不同，所以基因长度不一致。染色体编码如图4所示。

注：S表示源卫星节点，D表示目的卫星节点，N1,N2,…,Nn表示该路由途径的卫星节点。

图4 染色体编码

Fig.4 Chromosome coding

2.2.2 适度函数设计

适度函数为ck=w1·pd,y,k+w2·pl,k+w3·pb,y,k，对于编码的染色体，根据业务类别利用判断矩阵法计算w1，w2，w3的权重值，结合路由的时延、带宽和丢包率等约束条件得出适度函数值，选取最优解Cmin。

2.2.3 改进的自适应交叉、变异算子

本文采用顺序选择法，首先计算当前q个染色体并按适度值从小到大排序，然后选择前q/2个染色体，剩余q/2个染色体再随机选择1/2，共选取3q/4个染色体，既保证优质个体不会丢失，又保证种群的多样性。交叉概率和变异概率是能影响种群寻优的关键[17]，本文重新定义一种调节种群概率的自适应交叉、变异算子，种群适应度Ci的平均值表示为Cavg，分散程度表示为F。

(8)

式中：H为路由集合中的路由个数。

(9)

自适应交叉、变异概率分别表示为Pc和Pm，计算公式如下。

(10)

式中：k1和k2均为(0,1)内的自适应概率参数。

F作为判断种群适应度集中或分散的依据，范围在[0,π/2]。当Cmin/Cavg增大时，F增大，此时种群适度值集中，很难产生优质解，容易陷入局部极值，自适应减小Pc和增加Pm，增大种群变异概率，能很好地摆脱局部极值；当Cmin/Cavg减小时，F减小，说明种群适应度比较分散，自适应增加Pc可以快速产生种群的优质解，同时自适应降低Pm，减少对优质解的破坏。

计算得到自适应交叉、变异概率后，对种群进行交叉和变异操作。本文从采用的交叉算子方法为共点交叉法，在选取的染色体中选择2个有共同基因片段的染色体，相同的基因片段代表同一个节点，相互交换共同节点处之后的染色体片段，组成新的染色体。变异算子采用单点变异法，在路由中随机选取一点作为变异点，变异点随机选择一个相邻节点，该节点不能是源节点到变异点路径中的节点，变异为相邻节点后重复变异操作，直到生成源节点到目的节点的路径。交叉、变异过程如图5所示。

图5 染色体交叉、变异过程

3 仿真验证

3.1 仿真平台及参数设定

为了验证路由策略的有效性，搭建SDN仿真平台。仿真平台硬件环境为Dell OptiPlex9020，处理器为Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz，软件环境如表2所示。

表2 仿真软件环境

在仿真平台上设计一个小型卫星星座，地面站和GEO为控制平面，MEO和LEO为数据平面，卫星节点信息表如表3所示。仿真中选取3类业务分别为时延敏感业务、丢包率敏感业务和综合业务，综合业务表示数据流既是时延敏感业务又是丢包率敏感业务。对于每类业务的权重系数分别采用判断矩阵法计算得到，3类业务相对重要程度如表4所示。

表3 卫星节点信息

表4 相对重要度

3.2 时延仿真

本文基于SDN架构的空间信息网络路由策略时延仿真结果如图6所示。仿真结果与文献[8]中的DFRR策略和文献[10]中的AR策略对比，在时延敏感业务端到端传输的平均时延方面，随着时间增加，本文路由策略相对其他2种策略较好，比DFRR策略降低了3.2%，比AR策略降低了5.3%。这是因为DFRR策略是通过减少链路拥塞因素提高路由效率，AR策略是根据卫星位置周期性变化提前计算路由进行数据转发，两者均没有考虑数据的实时业务需求和合理的相应业务路由。本文路由策略是考虑数据业务类别和链路状况制定路由，采用改进的遗传算法进行筛选，自适应交叉、变异使种群具有多样性，多次迭代后选择出的路由具有鲁棒性。因此，对于空间信息网络的大流量传输，具有较好的实用性和高效性，业务数据传输时降低了时延。

图6 敏感业务端到端传输时延Fig.6 Delay of source-to-end transmission for sensitive services

3.3 丢包率仿真

敏感业务端到端传输丢包率仿真结果如图7所示。不同时间周期的业务流数量不同，随着传输业务流数量的增加，本文策略相比于DFRR策略和AR策略性能较好。在平均丢包率上，本文策略比DFRR策略降低10.2%，比AR策略降低19.1%。这是因为，DFRR策略和AR策略选取路由考虑因素单一，而不能较好地服务于各类业务。本文策略根据权重计算路由代价，选取的路由在降低丢包率方面优势明显。

图7 敏感业务端到端传输丢包率Fig.7 Packet loss rate of source-to-end transmission for sensitive services

3.4 综合业务丢包率仿真

图8为综合业务端到端传输丢包率仿真结果。在3种策略对比下，在业务流量传输数量较小时，DFRR策略和AR策略比本文策略要好，因为本文策略考虑因素较多，具有一定的复杂度。但是，随着传输数量的增加，本文策略优势明显，平均丢包率相比DFRR策略和AR策略分别降低了5.5%和15.2%，综合业务数据传输减少了丢包率。

图8 综合业务端到端传输丢包率Fig.8 Packet loss rate of source-to-endtransmission for integrated services

4 结束语

本文基于SDN架构的空间信息网络路由策略，相比于传统网络路由，在控制平面可以实时获取全局的网络状态，路由策略适用于各类业务，每个周期的静态拓扑随着时间周期的变化而更新，能够体现卫星运行的动态性，路由策略具有实用性。对于各类单一业务和综合业务，能较好地降低时延和丢包率，并且在一个周期内能对数据流快速转发，实现高效传输，提高空间信息网络运行效率。空间信息网络的卫星节点数要多于仿真试验卫星节点数，本文策略应用于空间信息网络中，在卫星节点数较多时，相比于其他2种策略，同样能降低传输时延和减少丢包率。LEO卫星和MEO卫星不需要自身计算路由，减轻了卫星自身负载，降低了功耗。但是，本文策略选择出每类业务路由的算法要考虑全局多种链路因素，并通过改进的遗传算法进行筛选，具有一定的时间复杂度，时间消耗主要在优质路由的迭代选取上。通过多次试验本文的算法运行参数可知，实际应用中科学地设置算法参数可以减少优质路由的选取时间。在工程应用中，“源-宿”卫星节点相距较近时，路由集合中路由数较少，优质路由能够快速确定，减少交叉、变异，从而减少时间消耗。反之，两者距离较远时，优质路由的选取要具有鲁棒性和时效性，此时遗传算法的迭代选取十分重要。因此，后续的研究重点是确定合适的算法参数和降低时间复杂度，以及减少由于卫星动态性在时间片内产生的位移对路由策略时效性的影响，提高路由效率，结合SDN架构，制定对各类单一业务和综合业务具有时效性的路由策略。