基于时延的LEO 卫星网络SDN 控制器动态放置方法

韩珍珍，赵国锋，徐川，周文涛，周洋洋

（重庆邮电大学通信与信息工程学院，重庆 400065）

1 引言

卫星网络能够覆盖海洋、高山、沙漠等地面网络不能覆盖的区域，在重大自然灾害预防及应急救援工作中，能够根据覆盖需求动态组网，从而支撑应急服务。天地一体化信息网络融合了卫星网络与地面网络的特点，能够支撑多样化的空间网络需求，这也成为未来网络发展的新趋势[1-3]。SDN（software defined network）的引入进一步提高了天地一体化信息网络的可扩展性及灵活性[4]。为了满足应急任务低时延、高可靠的服务需求，需要部署多个SDN 控制器来实现卫星网络的分布式控制，因此，控制器放置的数量和位置是设计控制器放置方案，提高卫星网络灵活性需要考虑的关键问题。

针对上述问题，卫星网络多控制器部署方案被相继提出，基于控制器部署的空间地理位置可将其划分为单层部署方案和多层部署方案两类，具体特点如表1 所示。单层部署方案是指在单卫星轨道层或者地面部署控制器[6-9]，如基于地面站数目稳定且具有强大的计算能力和存储能力，将控制器部署在地面中心站点上，能够提高卫星网络接入管理的灵活性[6]；基于GEO（geostationary earth orbit）卫星节点覆盖范围广、数目稳定且对地静止的特征，将GEO 卫星群作为控制器增强网络的可扩展性和灵活性[7]；基于LEO（low earth orbit）层卫星低时延的特性，在低轨星座中选择部分LEO 卫星节点作为控制器，以此来构建分布式控制架构，从而提高网络控制的灵活性，且文献[8]将LEO 轨道卫星节点交替设为控制节点和交换机来实现网络控制的内嵌；文献[9]基于地面用户流量动态需求模型设计LEO 层动态控制器放置算法，并将控制器放置模型转换为整型线性规划模型，求解最优控制器配置方案，优化平均流建立时间。然而，受卫星节点轨道位置特性的影响，上述单层控制器部署方法无法综合利用各个轨道层面的卫星的特性，整个网络控制的灵活性受限，不能在兼顾卫星网络广覆盖的同时满足低时延的需求。

表1 卫星网络多控制器放置方案对比分析

此外，研究者提出在多个卫星轨道层面和地面上设计主从控制模式的多层部署方案[10-13]，充分利用各层卫星节点的特点，提高网络的可扩展性。例如，Li 等[10]提出在地面和GEO 层部署控制器构成网络的控制平面；Xu 等[11]提出三层控制架构设计方案，控制平面由作为超级控制器的地面站、作为区域控制器的GEO 卫星群及作为从控制器的部分LEO 卫星构成，并在文献[12]提出基于轨道平面划分的从属控制器动态选取方法。类似地，Wu 等[13]提出由GEO、MEO（medium earth orbit）和LEO不同轨道卫星节点控制器构成的多层控制方案，通过构建多目标优化模型确定最优的控制器放置方法。

然而，基于卫星星座在整个LEO 层放置控制器的方案虽然能够充分利用LEO 层低时延的特点，但需要选择大量的卫星节点作为控制器以满足控制器对交换机的关联覆盖。当节点数目增加和动态性增强时，控制节点需要进行同步以维护全局网络视图。此时，节点间大量的信令交互会导致网络时延增加，仍然无法很好地满足应急任务动态组网的低时延需求。

本文提出了一种基于时延的LEO 卫星网络SDN 控制器动态放置方法，能够在满足应急卫星组网覆盖需求的同时降低网络时延。首先，以卫星对任务终端的覆盖为基础，设置卫星节点覆盖冗余度，并设计基于冗余覆盖的应急卫星子网划分机制，从而保障任务区域的有效覆盖；其次，对网络时延进行分析建模，在子网内以时延为优化目标确定控制器放置方案；最后，将控制器放置问题转化为设备放置问题，利用近似算法对模型进行求解，进一步降低网络时延。

2 控制器放置问题分析及思路

软件定义天地一体化信息网络基础架构如图1所示，整个控制平面由地面管理控制中心、GEO 卫星群主控制器和LEO 卫星层从控制器构成。

图1 软件定义天地一体化信息网络基础架构

2.1 问题分析

面对需要快速组网的应急通信场景，如抗震救灾等，系统能够根据应急任务需求构建应急卫星子网，从控制器能够及时根据本地卫星子网状态变化进行动态调整，提高网络控制的灵活性，并将本地卫星子网内的控制消息上传给主控制器，由主控制器完成全局网络视图的动态更新，使整个星座系统呈现为逻辑上集中、地理上分散的分布式控制架构。然而，受地理及社会因素的影响，GEO 卫星数量及位置相对稳定，选为主控制器可增加网络的稳定性。多层网络SDN 控制器部署方案的灵活性主要取决于如何选择合适的LEO 卫星作为从控制器，以保证网络有效覆盖和网络响应时延。

为了满足应急任务动态组网的低网络响应时延的需求，LEO 卫星网络的控制放置方案需要考虑的2 个关键问题：1)如何根据应急任务的覆盖需求动态划分卫星子网以满足卫星子网的有效覆盖；2)如何在卫星子网内选择合适的卫星节点作为控制器以降低网络响应时延。

2.2 研究思路

针对上述问题，本文提出基于时延的LEO 卫星网络SDN 控制器动态放置方法，其流程如图2 所示。

图2 基于时延的SDN 控制器放置方法流程

图3 卫星对地覆盖的几何性质

主要步骤如下。

1)基于覆盖冗余度的卫星子网划分机制

根据卫星对地覆盖特性确定满足当前覆盖需求的基础卫星子网S0后，当卫星节点动态变化时，为了满足卫星子网对应急区域的有效覆盖，选择卫星对终端的有效覆盖时间窗口，以此来设计卫星节点的覆盖冗余值N，根据卫星节点的覆盖冗余值，确定需要满足冗余覆盖的卫星子网Sr，在卫星节点动态组网中能够避免因网络切换而产生的覆盖漏洞。

2)建立基于网络时延的优化模型

在卫星子网内，基于分布式控制卫星网络的时延分析，以网络时延作为控制器放置方案的目标函数，选择卫星的可用度及星间链路的可靠性作为约束条件进行建模分析，能够在设计控制器放置方案时优化网络时延，提高网络控制的性能。

3)优化模型近似算法求解

将上述控制器放置问题转化为设备放置问题，设计基于近似算法的求解方法，优化模型最优化求解的时间复杂度，提高控制方案的稳定性，从而进一步降低网络时延。

3 控制器放置问题分析模型

3.1 卫星子网动态划分建模

为了避免因终端速度移动过快卫星切换不及时而导致的覆盖漏洞问题，本节提出基于覆盖冗余度的动态子网划分机制，其中覆盖冗余值由卫星与终端的相对位置和相对速度确定；基于该冗余值来扩展卫星子网，以此满足卫星网络的冗余覆盖。

3.1.1 覆盖冗余值N

为了保障卫星对终端的有效覆盖，定义覆盖冗余值N表示在基础的卫星对地最大时间窗口内终端需要切换的卫星数目。在建模过程中，假设卫星轨道和地球均为圆形，其中卫星对地覆盖的几何性质如图3 所示，卫星对地高度为H，运行速度为vs，地球半径为Re，卫星对地球的切线确定了卫星的最大覆盖范围[14-15]，此时的地心角一般设为α，终端是卫星对地覆盖范围内高度为h、速度为vu的节点，所对应的最大地心角为β。

根据卫星对地覆盖的几何性质，卫星沿运行轨道方向在单位时间T 内转过的弧度为αs，终端节点单位时间内转过的弧度为βu，结合弧长计算式，当αs=α 时，得到卫星对地最大覆盖时间窗口为

随着卫星与终端的相对运动，当卫星与终端相对角度差值超过2α 时，终端将超出卫星的覆盖范围，当αs-βu=2α 时，卫星对终端覆盖的时间窗口值Tmax为

1)当终端速度为0 时，此时N=1。

2)当终端与卫星相对运动方向相同时，N 值在0～1 之间，此时令N=1。

3)当终端与卫星相对运动方向相反时，N 值在1～2 之间，此时令N=2。

3.1.2 基于覆盖冗余度的卫星子网划分方法

卫星子网的划分需要满足网络对任务区域的有效覆盖，若仅根据当前卫星对地面的基础覆盖来确定卫星子网，则当终端与卫星子网边缘的卫星相对速度过大时，卫星网络不能满足对终端的覆盖，这会导致覆盖漏洞的问题。针对该问题，本节提出了基于冗余度的卫星子网划分机制，能够满足终端对卫星下一时刻切换的需求。

首先，根据任务终端的覆盖需求及卫星对地覆盖范围，确定一个基础的卫星子网S0；然后，计算子网边界卫星节点关联终端的N 值，取最大的N 值作为该卫星节点的扩展冗余度，图4 中以N=1 为例进行说明；最后，选取LEO 卫星子网S0的边界卫星节点（如图4 中节点A 和节点B）间隔N-1 条轨道（如图4 中Oaa和Oba），及垂直于与边界卫星节点同轨道且间隔N-1 颗卫星的卫星节点到地心距离为半径且以地心为圆心的弧线（如图4 中Cas和Cbs），这些边界卫星节点的外围曲线围成区域所包含的卫星节点构成基于冗余度扩展后的卫星子网Sr，满足可能存在的终端切换的要求，从而满足卫星子网覆盖需求。

图4 基于冗余覆盖的卫星子网划分

3.2 基于时延的控制器放置建模

卫星网络中控制器放置的数量和选取的位置会影响网络时延，同时也受存储容量和星间链路的可关联性约束，本节以网络时延作为优化目标，以卫星节点容量及星间链路的关联关系作为约束条件，对卫星网络控制器放置问题进行建模分析，主要符号定义如表2 所示。

表2 参数符号及其定义

3.2.1 网络时延分析

基于分布式控制的卫星网络时延包括网络维护时间、数据流建立时间、控制同步时间和控制器切换时间，在这里主要考虑传播时间和传输时间对网络响应时延产生的影响。具体过程如图5 所示。

1)网络维护时间

图5 中a—c 为网络维护过程。首先，控制器根据链路检测协议，向其管理的交换机发送链路检测数据分组，交换机向其邻域节点一跳转发数据分组，接收到该数据分组的交换机通过packet_in 方式将信息上传到其连接的控制器。网络维护过程产生的平均时延代价为

其中，等号右边第一项表示控制器间进行信息交互产生的时间，第二项表示交换机进行信息交互产生的时间，每项都包括信息的传播时间和传输处理时间，eij表示两节点之间的边。

图5 分布式控制系统时延分析

2)数据流建立时间

图5 中d—e 为业务流的建立过程，以图5 中交换机S1为例。每当新的业务流到达交换机S1时，由于从S1流表中没有匹配到相应的数据流转发规则，需要向控制器C2packet_in 业务信息，控制器C2再向交换机S1packet_out 并安装该流的转发规则。流建立过程的时延代价为

3)控制同步时间

图5 中f—g 为控制器集群同步过程。从属控制器向主控制器Cm发送本域的网络信息，主控制器再向从属控制器发送全局网络信息。控制器集群平均同步时延代价为

4)控制器切换时间

图5 中h—j 为交换机S2从控制器C1迁移到C2的过程。在切换过程中，控制器集群之间首先需要进行网络信息同步，然后原控制器向迁移的交换机发送切换信息，该交换机向新关联的控制器发送连接请求，目的控制器收到请求后回复确认信息。交换机迁移引起的平均时延代价为

其中，等号右边第一项表示交换机与原控制器断开时间，第二项表示交换机与新控制器连接时间。

3.2.2 控制器放置方案优化模型

根据上述分析可以得到，以最小化网络时延确定子网控制器放置方案时可得到优化目标函数，即

其中，目标函数式(8)表示分布式卫星子网的网络响应时延；约束式(9)表示开启的控制器数目小于或等于网络节点数目；约束式(10)表示每个交换机仅由一个控制器控制；约束式(11)可以保证控制器能够承载关联交换机的请求，其中Us表示卫星节点的最大容量；约束式(12)能够限制控制链路关联关系，其中pij是二进制数，i 与j 连接为1，否则为0，当i=j 时，该卫星节点是控制器。

4 基于近似算法的控制器放置模型求解

4.1 控制器放置问题近似求解算法

针对上述基于网络时延的控制器放置模型，最优解的求解是NP-hard 问题[16-17]，当网络节点较多时，算法求解复杂，难以在有效的时间内获得最优解。针对该类问题，启发式算法可以对模型进行快速求解，但是无法保证解的准确性和稳定性。需要近似算法对该问题进行有效求解，且对解的有效性进行约束[18]。在提出具体求解算法之前，先将目标函数转换为有容量限制的设施选址问题[19]，具体如式(13)～式(17)所示。

其中，目标函数式(13)表示通过时延代价的优化确定控制器放置方案，其中xij表示控制器与交换机的匹配关系，yi表示节点i 为控制器；约束式(14)表示每个交换机与一个控制器相关联；约束式(15)表示与控制器卫星关联的交换机个数小于卫星星间链路的数量，其中ui表示星间链路的条数；约束式(16)表示只要有交换机关联，那么控制器必须处于开启状态；约束式(17)表示xij和yi是二进制数。其中，有

针对上述设备放置问题的求解，本节提出按需动态控制器动态放置近似算法（ODAA,on demand dynamic approximate algorithm）。根据覆盖需求确定卫星子网S0，根据边缘卫星节点的扩展冗余度N 确定卫星子网Sr。在子网Sr内确定控制器放置方案，主要设计思想是根据目标函数式(13)建立控制器与交换机之间的关联，随着控制器数量的增加，重新判断交换机和控制器的关联关系，直至输出最终结果。事件1 表示出现系统最小时延匹配时，将交换机j 关联到控制器i 上，事件2 表示若增开新控制器存在更低的网络时延，则开启新控制器，完成交换机与控制器的关联，降低系统时延，具体步骤如算法1 所示。

算法1按需动态控制器放置近似算法

输入S0，{ fi,cij,ui}，{dij}

输出可行整数解集(x,y)

计算基础卫星子网S0的边界卫星节点的N 值；

基于N 扩展S0获得Sr，进而获得子网内卫星节点集合V；

当U≠∅时，针对j∈C 则αj=t，按照任意顺序执行以下两类事件；//t是时间变量；

事件1

事件2

如果j ∈ C则xij=1；

返回(x,y)解集

4.2 按需动态控制器动态放置近似算法有效性说明

本节通过引理1 证明目标函数式(13)是规约设备放置问题，因而具有可求解的近似算法；进而用引理2 证明本文所提的按需动态控制器放置算法是近似算法，该算法能够在降低计算复杂度的同时保证解的有效性。

引理1目标函数式(13)是规约设备放置问题。

证明在目标函数式(13)中，fi表示开启控制器所产生的时间代价，主要包括控制器与控制器之间的节点同步时间；cij表示交换机关联的时间代价，主要包括两部分，分别为交换机与控制器之间的时间及交换机与交换机之间的时间。根据有容量限制设备放置问题的基本属性可得，cij需要满足非负性、对称性及三角不等式[19]。

1)非负性

cij为交换机的连接代价，pij’为二进制数，Fij为大于零的数值，为大于0 的数值，可得cij第一部分非负，第二部分有以下2 种情况。

情况1当pij’=0 时，(1-2 pij’)Ih值非负，此时，cij第二部分非负。

情况2当pij’=1 时，当前i 与j 节点的配置关系不发生改变，Ih=0，(1-2 pij’)Ih=0，从而可得cij第二部分非负。

因此，cij满足非负性。

2)对称性

由于dij=dij，Fij=Fji，，由式(21)可得cij=cji，因此cij具有对称性。

3)三角不等式

三角不等关系如图6 所示。从以下2 种情况证明对于∀1 ≤j ＜i ≤k,必然满足性质αi≤rj,i+di+dj。

情况1当αj=αi时，显然满足αi≤rj,i+di+dj。

情况2当αj＜ αi时，因为j 在t 时刻没有连接到另一控制器 i(j)，所以t=αi-ε≤ci(j)j，αi=t-ε≤ci(j)i≤ci(j)j+di+dj=rj,i+di+dj。

图6 三角不等关系

由以上分析可得，目标函数的最优化求解问题是规约设备放置问题。

证毕。

引理2目标函数式(13)对应的设备放置问题具有近似度为2 的近似算法。

证明根据文献[20]将上述控制器放置问题归纳成线性代价的设备选址问题（LCFLP,linear cost facility location problem），在软容量设施选址问题（SCFLP,soft capacitated facility location problem）中，控制器设施i 的开启代价为

其中，当k ≥1 时，有

所以SCFLP 是相应LCFLP(a,b,c)的(2,1)-规约。则该问题可以等效转换为相应的无容量限制设施选址问题UFLP(b,c+a)（un-capacitated facility location problem），且满足

结合文献[19]中的推论2 可得，UFLP(b,c+a)运行上述算法可以得到LCFLP(a,b,c)(1,2)-近似算法。再根据文献[20]中定理3 得到，上述SCFLP 求解算法ODAA 是近似度为2 的近似算法。

5 仿真实验及结果分析

针对卫星网络的特点，本文主要利用STK（satellite tool kit）对LEO 低轨星座系统的卫星节点及星间链路进行建模，并联合Matlab 完成控制器放置方法的仿真验证。在Iridium 星座系统中，网络任务由地面移动终端产生，任务流的大小及基本分布情况主要参考文献[13]，在GMT 2019-04-10 8:00 am 到2019-04-11 7:00 am 时段内，通过需要放置的控制器的数量、网络响应时间及平均流建立时间验证本文所提方案的可行性及有效性，并根据文献[21-22]设置如表3 所示的仿真实验参数。

表3 主要实验参数设置

5.1 控制器放置数量

控制器放置数量实验主要验证本文所提子网划分机制能够有效减少控制器放置的数量。其中卫星子网占比γ 指满足地面网络冗余覆盖需求的总卫星子网Sr与整个星座对地覆盖的比值。

不同子网占比下控制器放置的数量如图7 所示。由图7 可得，随着卫星子网占比的不断提高，卫星子网覆盖区域不断扩大，需要放置的控制器数量随之增加。当γ=0.1 时，卫星节点数量较少，子网中控制器卫星节点与交换机的配比约为1:5，即一个控制节点卫星关联5 个交换机的卫星。当网络达到全覆盖时，需要放置的控制器的数量平均是12 颗，放置控制器的卫星和作为交换机的卫星的配比略大于1:4，基本满足卫星网络星间链路的特点。由此可见，为了满足控制器对交换机的覆盖需求，卫星子网越大，需要放置的控制器数量就越多。因此基于覆盖需求的子网划分机制相较基于全网的控制器放置方案能够根据网络的覆盖需求放置控制器，在满足网络覆盖需求的同时能够优化需要放置的控制器的数量。

图7 不同子网占比下控制器放置的数量

5.2 网络时延分析

网络时延分析实验主要验证本文所提ODAA在不同的子网中能够优化网络时延，保证交换机与控制器的关联配置，从而保持平均流建立时间。

当卫星子网占比不同时，采用ODAA 放置控制器平均网络时延及平均流建立时间变化趋势如图8所示。由图8 可得，随着子网占比的增加，网络时延近似成比例增加，但平均流建立时间维持在20～25 ms。因为随着卫星子网范围的扩大，需要放置更多的控制器来满足对交换机的关联，由式(8)可得网络时延也随之增加，受星间链路特性的约束，一个放置控制器的卫星节点最多与4 个作为交换机的卫星直接关联，交换机与控制器平均间隔一跳的距离；由式(5)可得平均流建立时间相对稳定。随着时间的推移，控制器放置方案能够动态更新，网络时延和流建立时间能够保持相对稳定。因此，本文所提基于子网划分机制的控制器放置算法能够优化网络时延和平均流建立时间，提高网络的灵活性。

图8 不同卫星子网占比网络时延的变化

5.3 算法有效性对比分析

为了验证所提近似算法的有效性，基于整个网络系统，将所提算法ODAA 与文献[13]中动态控制器放置求解加速粒子群算法ASPO（accelerated particle swarm optimization）及最优搜索算法OptSearch（optimal search）进行对比分析。

如图9 所示，本文所提算法ODAA 在控制器放置数量、平均网络响应时延及平均流建立时间上相较ASPO 算法所得结果更趋向于最优搜索算法，且与ASPO 算法相比ODAA 能够降低约10%的平均网络时延及23%的平均流建立时间，有效改善网络控制的时延性能。

OptSearch 算法能够得到最低时延代价的优化解，但是随着网络节点的增加，由于其算法执行时间过长，从而导致适用性差，其中OptSearch算法的具体时间复杂度为O(2nn3)。为了在提高算法求解的精确度的同时降低计算时间复杂度，在进行控制器选择时，本文所提算法根据星间链路的特性对解的有效性进行约束，设计逼近于最优解的求解方法，获得时间复杂度为O(n2)的启发式求解算方法。基于一般启发式求解方法的控制器放置求解算法ASPO，其算法的时间复杂度为O(mn)，虽然此算法能够降低优化算法的时间复杂度，但是无法保证解的准确性。相较ASPO 算法，本文所提算法在不明显增加计算复杂度的基础上，获得了逼近于最优解的控制器放置方案，且在优化算法计算时间的同时能够保证解的稳定性。

图9 不同算法对比分析

6 结束语

本文提出了一种基于时延的LEO 卫星网络控制器动态放置方法。该方法能够根据本地卫星子网的动态变化灵活地调整网络的大小，避免卫星节点切换不及时而引起的网络覆盖漏洞问题，并在子网内以网络响应时延作为优化目标函数，能够优化控制卫星节点与交换卫星节点之间的关联关系，从而降低网络的平均流建立时间及响应时间。针对优化目标函数有效求解问题，将控制器放置问题转换为设备放置问题，设计近似算法在降低计算时间复杂度的同时获得更加逼近最优的放置方案，从而进一步提高所提方案的稳定性。