CN104579454A - 基于软件定义网络的多目标优化的卫星流控制方法 - Google Patents

Abstract

本发明公开了一种基于软件定义网络的多目标优化的卫星流控制方法。本发明通过引入多目标优化框架，实时地将多QoS需求的流，通过遗传算法进行拟合计算，得到若干个非劣解集，并将解集传输给控制器，为相应的交换设备产生合适的流表，建立相应的逻辑链路。该方法具有的优点如下：采用集中式控制，相较于传统网络分布式决策系统，路由收敛更快，能够适应快速变化的卫星网络；卫星网络可预知的地理位置信息和链路带宽信息能够被引入到多目标优化系统中，可以有效地提高路由效率；采用多目标优化算法进行路径规划，能够处理复杂QoS需求，降低了复杂QoS情况下无法找到路径的机率。

Description

基于软件定义网络的多目标优化的卫星流控制方法

技术领域

本发明涉及卫星组网技术问题，尤其涉及一种基于软件定义网络的多目标优化的卫星流控制方法。

背景技术

卫星通信系统具有覆盖面广、组网灵活、使用便捷等优点，可为全球用户提供大容量、远距离和机动灵活的音视频、数据等通信业务；同时，卫星通信可提供不受地理环境、气候条件限制的通信服务，便于构建无中断全球覆盖移动通信网络。因此，借助在轨卫星实现全球范围内的测控、导航和组网通信，已成为下一代网络的重要研究方向之一。2006年，原国防科工委副主任、载人航天工程副总指挥，现任浙江大学航空航天学院院长，航天测控专家沈荣骏院士提出了建设天地一体化网络的构想。2012年，随着“天链一号03星”的成功发射升空，中国第一代中继卫星系统通过三颗卫星进行了全球组网运行，向中、低轨卫星与载人飞行器提供了数据转发与中继服务。2012年12月27日，由14颗卫星组成的“北斗”卫星导航系统正式向亚太地区开放，该系统初步具备了网络通信的短报文功能。随着中国航天事业的发展，卫星发射愈加频繁，在轨卫星数量越来越多，星间组网技术的研究已迫在眉睫。

软件定义网络的概念标准OpenFlow在2008年由斯坦福大学、华盛顿大学、麻省理工大学、加州大学伯克利分校、普林斯顿大学、圣路易斯华盛顿大学等高校联合提出。初期软件定义网络计划希望通过在普通以太网交换机上增加对OpenFlow协议的支持，以实现将传统的网络交换机控制平面与数据平面分离，在校园小规模网络中支持实验性的网络协议测试功能[1,2]。根据OpenFlow 1.0标准，典型的OpenFlow交换机包括一个内部的流表和标准化的外部接口来增加或删除流表项。同时，OpenFlow交换机通过一个加密的安全通道与控制器相连，接收来自控制器的命令，同时向控制器汇报交换机的运行情况[3]。随着SDN技术的发展，在OpenFlow 1.3版本中，已经加入了多流表串行处理机制以应对复杂的流控制需求[4]。

参考文献：

[1]N.McKeown,T.Anderson,et al.,OpenFlow:Enabling Innovation in CampusNetworks,ACM SIGCOMM Computer Communication Review,38(2):69-74,2008.

[2]N.Gude,T.Koponen and et al.,NOX:towards an operating system for networks,ACM SIGCOMM Computer Communication Review,38(3):105-110,2008

[3]OpenFlow Switch Specification,version 1.0.0.[EB/OL],http://www.openflow.org/documents/openflow-spec-v1.0.0.pdf,2014/02/21.

[4]OpenFlow Switch Specification,version 1.3.0.[EB/OL],https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.0.pdf,2014/02/21.

发明内容

本发明的目的是提供一种基于软件定义网络的多目标优化的卫星流控制方法。

一种基于软件定义网络的多目标优化的卫星流控制方法的步骤如下：

1)LEO卫星通过GEO或MEO卫星通告控制器其具体的经纬度信息；

2)控制器依据各LEO卫星的通告信息，实时形成卫星链路拓扑结构；

3)卫星终端通过LEO卫星向目的结点发送数据包；

4)LEO卫星检查自身流表，当卫星链路的目的地已存在本地，则将数据包转发至下一跳链接；当卫星链路的目的地未存在本地，则将数据包通过GEO或MEO卫星传送至控制器；

5)控制器记录数据包的源地址，并检查数据包的目的地址是否已知，当目的地址未知，则放弃数据包；当目的地址已知，则传递源地址与目的地址和当前卫星拓扑给多目标优化器，通过遗传算法规划非劣路径。

所述的遗传算法规划非劣路径的方法如下：

首先作如下定义：对于两个任意决策变量x_A，x_B∈X_f，X_f为可行解集合，

1)当且仅当 $\&ForAll;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)<f_i$ 时，称A占优于B；

2)当且仅当 $\&ForAll;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)\&le;f_i$ 且 $\&Exists;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)<f_i$ 时，称A弱占优于B；

3)当且仅当A不占优于B，且B不占优于A时，称A与B无差别。

遗传算法主要包括分层算法和拥挤度比较算法。

所述的分层算法为：

1)设i＝1；

2)对于所有的j＝1,2,n且j≠i，按照以上定义比较个体x_i和个体x_j之间的支配与非支配关系；

3)如果不存在任何一个个体x_j优于x_i，则x_i标记为非支配个体；

4)令i＝i+1，转到步骤(2)，直到找到所有的非支配个体；

通过分层算法得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经标记的非支配个体，即这些个体不再进行下一轮比较，再遵循步骤1)-步骤4)，就会得到第二级非支配层，依此类推，直到整个种群被分层；

所述的拥挤度比较算法为：

每个点的拥挤度i_d置为0；

针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即o_d＝l_d＝∞；

对其他个体进行拥挤度的计算：

$i_d=\underset{j=1}{\overset{m}{\mathrm{\&Sigma;}}}\left(\right|{f_j}^{i+1}-{f_j}^{i-1}\left|\right)$

其中，i_d表示i点的拥挤度，f_j ⁱ⁺¹表示i+1点的第j个目标函数值，f_j ^i-1表示i-1点的第j个目标函数值；

拥挤度指的是种群中给定点的周围个体的密度，多目标优化器在每次完成分层算法后将启动拥挤度比较算法对每个个体计算其拥挤度并排序；

多目标优化器将每层依次排序，同层内按拥挤度排序，淘汰适应度较低的一半，将适应度较高的一半进行位反转的变异和按位杂交的方式产生同样个数的新个体后，加入下一轮优化计算的初始种群中，开始启动下一轮优化计算，当多目标优化器在默认的步数内无法产生路径，则放弃该数据包；当多目标优化器在默认的步数内产生了相应的路径，则通知控制器更新相关结点的流表，形成逻辑链路。

本发明与现有技术相比具有的有益效果：

1、本发明公开了基于软件定义网络的多目标优化的卫星流控制方法的优势为：多目标优化地集中规划路由路径，能够处理复杂QoS需求。

目前常见的QoS算法通常采用较简单的多级阶梯式的处理方式，在处理复杂QoS需求时可能无法获得最优路径而容易失败。而本发明所采用的多目标优化算法进行集中规划路由路径，能够采用遗传算法等人工智能算法进行复杂QoS规划。即使复杂的QoS中存在互相冲突的需求，亦能够找到合适的非劣解集。因此，采用集中式的多目标优化算法有助于处理日亦复杂的路由QoS需求。

2、本发明公开了基于软件定义网络的多目标优化的卫星流控制方法的优势为：融合了卫星的轨道信息，加快了路由规划时间。

卫星处于高速运行状态中，相对高速运动的卫星网络时刻在发生变化，传统的网络路由策略不考虑卫星轨道信息将很难在短时间内收敛，导致收敛后的路由规划已不再适用于高速变化的新拓扑网络结构。本发明引入了卫星轨道信息，有助于加速多目标优化算法搜寻最佳路径。因此，本方法可以提供更加快速、实时、合适的路由规划服务。

3、本发明公开了基于软件定义网络的多目标优化的卫星流控制方法的优势为：上星后能够实时调整路由策略。

本发明的卫星流控制方法采用软件定义网络技术，相对于其他传统的组网技术来说，该组网策略简化了星上的决策能力。卫星硬件仅需理解较为简单的路径转发指令，无需了解复杂的上层协议。上层协议的处理由集中的控制中心进行处理，分解为简单的路径转发指令后下发至卫星硬件。因此，采用本发明所述的卫星网络能够在上星后不对硬件进行修改即可实时完成路由策略的调整，有利于适应新的路由需求。

附图说明

下面结合附图和实施例对本发明做进一步说明。

图1为传统卫星网络与软件定义卫星网络对比示意图；

图2为卫星网络控制器架构图；

图3为实施例托普及结果图；

图4为实施例流程图。

具体实施方式

一种基于软件定义网络的多目标优化的卫星流控制方法的步骤如下：

1)LEO卫星通过GEO或MEO卫星通告控制器其具体的经纬度信息；

2)控制器依据各LEO卫星的通告信息，实时形成卫星链路拓扑结构；

3)卫星终端通过LEO卫星向目的结点发送数据包；

4)LEO卫星检查自身流表，当卫星链路的目的地已存在本地，则将数据包转发至下一跳链接；当卫星链路的目的地未存在本地，则将数据包通过GEO或MEO卫星传送至控制器；

5)控制器记录数据包的源地址，并检查数据包的目的地址是否已知，当目的地址未知，则放弃数据包；当目的地址已知，则传递源地址与目的地址和当前卫星拓扑给多目标优化器，通过遗传算法规划非劣路径。

所述的遗传算法规划非劣路径的方法如下：

首先作如下定义：对于两个任意决策变量x_A，x_B∈X_f，X_f为可行解集合，

1)当且仅当 $\&ForAll;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)<f_i$ 时，称A占优于B；

2)当且仅当 $\&ForAll;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)\&le;f_i$ 且 $\&Exists;i=\{\mathrm{1,2},...,k\}:f_i\left(x_A\right)<f_i$ 时，称A弱占优于B；

3)当且仅当A不占优于B，且B不占优于A时，称A与B无差别。

遗传算法主要包括分层算法和拥挤度比较算法。

所述的分层算法为：

1)设i＝1；

2)对于所有的j＝1,2,n且j≠i，按照以上定义比较个体x_i和个体x_j之间的支配与非支配关系；

3)如果不存在任何一个个体x_j优于x_i，则x_i标记为非支配个体；

4)令i＝i+1，转到步骤(2)，直到找到所有的非支配个体；

通过分层算法得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经标记的非支配个体，即这些个体不再进行下一轮比较，再遵循步骤1)-步骤4)，就会得到第二级非支配层，依此类推，直到整个种群被分层；

所述的拥挤度比较算法为：

每个点的拥挤度i_d置为0；

针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即o_d＝l_d＝∞；

对其他个体进行拥挤度的计算：

$i_d=\underset{j=1}{\overset{m}{\mathrm{\&Sigma;}}}\left(\right|{f_j}^{i+1}-{f_j}^{i-1}\left|\right)$

其中，i_d表示i点的拥挤度，f_j ⁱ⁺¹表示i+1点的第j个目标函数值，f_j ^i-1表示i-1点的第j个目标函数值；

拥挤度指的是种群中给定点的周围个体的密度，多目标优化器在每次完成分层算法后将启动拥挤度比较算法对每个个体计算其拥挤度并排序；

多目标优化器将每层依次排序，同层内按拥挤度排序，淘汰适应度较低的一半，将适应度较高的一半进行位反转的变异和按位杂交的方式产生同样个数的新个体后，加入下一轮优化计算的初始种群中，开始启动下一轮优化计算，当多目标优化器在默认的步数内无法产生路径，则放弃该数据包；当多目标优化器在默认的步数内产生了相应的路径，则通知控制器更新相关结点的流表，形成逻辑链路。

实施例

如图3、4所示，基于软件定义网络的多目标优化的卫星流控制方法的步骤如下：

1.S0-S2、S11-S13、S22-S24、S33-S35为部分LEO卫星，他们的实时位置信息通过图中未画出的GEO卫星传送给地面控制器；

2.控制器依据各LEO卫星的通告信息，实时形成卫星链路拓扑结构，图4为拓扑图的一部分；

3.卫星终端H2通过LEO卫星S24向目的结点H1发送ping数据包；

4.S24卫星检查自身流表，该链路的目的地H1未存在本地，则将该数据包通过GEO卫星传送至控制器；

5.控制器记录该数据包的源地址，并检查数据包的目的地址是否已知。目的地址H1未知，放弃该数据包。

6.下一时刻，卫星终端H1通过S0卫星向目的结点H2发送ping数据包；

7.S0卫星检查自身流表，该链路的目的地H2未存在本地，则将该数据包通过GEO卫星传送至控制器；

8.控制器记录该数据包的源地址，并检查数据包的目的地址是否已知。目的地址已知，则传递源地址H1与目的地址H2和当前卫星拓扑给多目标优化器，通过权利要求2中所述的遗传算法规划非劣路径，如S0-S11-S12-S23-S24，并将该路径依次下传至相关的所有卫星上；

9.H1所发出的数据包顺着S0-S11-S12-S23-S24向H2传输，反之亦然。

Claims (4)

1.一种基于软件定义网络的多目标优化的卫星流控制方法，其特征在于它的步骤如下：

1)LEO卫星通过GEO或MEO卫星通告控制器其具体的经纬度信息；

2)控制器依据各LEO卫星的通告信息，实时形成卫星链路拓扑结构；

3)卫星终端通过LEO卫星向目的结点发送数据包；

4)LEO卫星检查自身流表，当卫星链路的目的地已存在本地，则将数据包转发至下一跳链接；当卫星链路的目的地未存在本地，则将数据包通过GEO或MEO卫星传送至控制器；

5)控制器记录数据包的源地址，并检查数据包的目的地址是否已知，当目的地址未知，则放弃数据包；当目的地址已知，则传递源地址与目的地址和当前卫星拓扑给多目标优化器，通过遗传算法规划非劣路径。

2.如权利要求1所述的一种基于软件定义网络的多目标优化的卫星流控制方法，其特征在于所述的遗传算法规划非劣路径的方法如下：

首先作如下定义：对于两个任意决策变量x_A，x_B∈X_f，X_f为可行解集合，

1)当且仅当时，称A占优于B；

2)当且仅当且时，称A弱占优于B；

3)当且仅当A不占优于B，且B不占优于A时，称A与B无差别，遗传算法主要包括分层算法和拥挤度比较算法。

3.如权利要求2所述的一种基于软件定义网络的多目标优化的卫星流控制方法，其特征在于所述的分层算法为：

1)设i＝1；

2)对于所有的j＝1,2,n且j≠i，按照以上定义比较个体x_i和个体x_j之间的支配与非支配关系；

3)如果不存在任何一个个体x_j优于x_i，则x_i标记为非支配个体；

4)令i＝i+1，转到步骤(2)，直到找到所有的非支配个体；

通过分层算法得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经标记的非支配个体，即这些个体不再进行下一轮比较，再遵循步骤1)-步骤4)，就会得到第二级非支配层，依此类推，直到整个种群被分层。

4.如权利要求2所述的一种基于软件定义网络的多目标优化的卫星流控制方法，其特征在于所述的拥挤度比较算法为：

每个点的拥挤度i_d置为0；

针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即o_d＝l_d＝∞；

对其他个体进行拥挤度的计算：

其中，i_d表示i点的拥挤度，表示i+1点的第j个目标函数值，表示i-1点的第j个目标函数值；

拥挤度指的是种群中给定点的周围个体的密度，多目标优化器在每次完成分层算法后将启动拥挤度比较算法对每个个体计算其拥挤度并排序；

多目标优化器将每层依次排序，同层内按拥挤度排序，淘汰适应度较低的一半，将适应度较高的一半进行位反转的变异和按位杂交的方式产生同样个数的新个体后，加入下一轮优化计算的初始种群中，开始启动下一轮优化计算，当多目标优化器在默认的步数内无法产生路径，则放弃该数据包；当多目标优化器在默认的步数内产生了相应的路径，则通知控制器更新相关结点的流表，形成逻辑链路。