天地一体化智能网络智能节点部署策略

2022-01-21何兆斌孔志翔

小型微型计算机系统 2022年1期

杨力，何兆斌，孔志翔

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

1 引言

随着卫星网络技术的不断发展，具有星间链路的低轨卫星(Low Earth Orbit，LEO)网络以其庞大的部署规模以及较低的部署成本，已经能够实现全球移动通信的无缝式覆盖.然而随着物联网技术的不断发展、信息化程度不断增加，以及天基接入网中的星座规模不断增大、拓扑结构不断复杂，导致了星上的计算任务随之增加.传统将计算任务传输到高轨卫星(Geostationary Earth Orbit，GEO)计算或是经GEO卫星转发到地面数据中心的计算模式，会造成极高的传输时延，无法满足越来越多实时性应用的需求.因此，急需一项新技术来解决卫星网络中传输时延过高的问题[1].

移动边缘计算的核心理念是将计算任务尽可能的放置在离数据源最近的计算资源上运行，从而有效减少计算系统的传输时延，缓解云计算中心的压力[2].本文结合天地一体化智能网络架构，将边缘服务器部署在具有计算和存储能力智能卫星节点上，提出一种基于人工蜂群的智能卫星节点优化部署算法——iABC(improved-Artificial Bee Colony Algorithm)，来实现一个边缘服务系统.该算法充分考虑了卫星节点拓扑结构的动态性和周期性，可选取出边缘服务有效覆盖率最高的智能卫星节点部署方案，旨在使用最少的智能卫星节点部署，来达到最佳的边缘服务有效覆盖率，进而最大化的降低系统的传输时延.该算法适用于绝大多数的卫星系统.文章的最后，本文对该算法进行了仿真实验.

2 相关工作

移动边缘计算(Mobile Edge Computing，MEC)技术以其卓越的实时性和连通性，已经解决了很多传统云计算中存在的问题，受到了越来越多的研究人员的青睐.目前，已经有一些学者考虑将边缘计算技术应用到卫星网络中去.2017年，张寒[3]等人提出了基于SDN/NFV的天地一体化网络架构.该架构中，软件定义网络(Software Defined Network，SDN)、网络功能虚拟化(Network Functions Virtualization，NFV)和移动边缘计算MEC三者协同作用，实现对网络的统一管理，调度协同.2018年，于晓艺[4]等人分析了MEC在卫星网络中的适用性，然后在地面 5G 基于服务的网络架构的基础上提出了融合MEC的卫星网络架构.但是这些架构中的边缘服务节点大都部署在地面网中.因此，在人烟稀少的地区，以及广袤的海上区域，边缘服务就很难有效覆盖.

在如何有效部署边缘服务器这个问题上，Jia[5]等人研究了边缘服务器在无线城域网中的优化部署问题.Xu[6]等人根据边缘服务器的容量限制不同，优化了其在边缘网络中的部署问题.Dhaou[7]等人为了最小化网关的数目，采用遗传算法，解决了卫星与MANETs混合网络中网关的选择问题.陈卓[8]等人结合了遗传算法和模拟退火算法，提出了一种集群化部署策略iGSA(improved-genetic and simulated annealing)，有效降低了业务流的端到端时延.但是这些研究都是针对地面网络.卫星节点具有高动态性，拓扑结构几乎每时每刻都在变化，因此需要结合卫星节点的高动态性特点，设计一个算法来解决天地一体化智能网络中智能卫星节点的部署问题.

天地一体化智能网络的智能卫星节点具有很强的存储和计算能力，是边缘服务器的良好载体.本文结合移动边缘计算的思想，将边缘服务器部署在智能卫星节点上，使其能够为临近的卫星节点以及地面用户节点提供边缘计算服务，并提出了一种能适应卫星节点高动态性、周期性特点的智能节点优化部署算法，有效地解决了上述存在的问题.

3 基于人工蜂群的智能卫星节点部署算法

天地一体化智能网络是以传统卫星网络为基础，搭配部分具有计算和存储能力的智能卫星节点，以实现能源自配置、状态自调整的一种新型网络[9].智能卫星节点部署在LEO卫星层，可为地面终端以及邻近普通卫星节点提供边缘计算服务，与传统需要传输到GEO相比，该模式将会极大地降低传输距离，减少传输时延，因此可满足更多实时性任务的需要.

智能卫星节点的部署，可以很好地解决数据爆炸式增长环境下，带宽不足、传输时延大等问题.然而，面对庞大的卫星星座，该部署多少，以及如何部署边缘服务节点，是首先需要考虑的问题.本文采用人工蜂群优化算法，结合网络分簇算法，提出一个基于人工蜂群的智能卫星节点优化部署算法iABC.该算法充分考虑了卫星节点的高动态性，结合卫星运行轨迹具有周期性、卫星连接度有限、卫星可视范围有限等特点，以部署最少的智能卫星节点，达到整体边缘服务有效服务覆盖率最高.

为了更好地研究天地一体化智能网络中智能卫星节点的部署问题，本文采用D={d1，d2，…，di}来表示智能卫网络中的所有LEO卫星节点.其中，R=|D|为天地一体化智能网络中卫星节点的个数，di保存了第i个卫星节点的初始位置信息；X={x[注]https://www.cnblogs.com/ybl20000418/p/11366576.html，x2，…，xn}表示天地一体化智能网络中的智能卫星节点的部署策略，N=|X|为智能卫星节点的个数.其中1≤xn≤R，xi≠xj，表示在天地一体化智能网络中的R个卫星节点中，第xn个节点为智能卫星节点.

3.1 网络分簇算法

网络分簇算法[10，11]是计算智能节点部署策略适应度的算法，其充分考虑了卫星节点高动态性的特点，并且贯穿于整个智能卫星节点部署算法的始终.该算法的功能是在已知智能节点的部署策略X，以及LEO卫星层中各卫星节点信息(包括具体坐标、轨道信息、运行周期、节点连接度等)的情况下，计算出对应部署策略X的边缘服务有效覆盖率.以此来评价对应部署策略X的适应度，为接下来的人工蜂群算法提供部署策略X的评价指标.

图1 网络分簇算法示意图Fig.1 Schematic diagram of network clustering algorithm

图1为网络分簇算法的简单示意图.该算法借鉴网络分簇的思想，将整个LEO星座分为若干个簇，每个非智能卫星节点在自己的可视范围内选择最适合自己的智能卫星节点当作边缘服务节点.由于卫星节点具有很强的动态性，在某一个时间点中，卫星dj能获取到边缘服务，但下一个时间点可能在可视范围内就无法找到合适的智能卫星节点来提供边缘服务.因此，本文针对卫星节点具有较强动态性和周期性的特点，采取划分时间段的研究方法.即把一个完整的卫星系统运行周期T分成n个确定的时间段，即[t0=0，t1]，[t1，t2]，…，[tn-1，tn=T]，并假定在每个时间段内卫星的拓扑结构不变[12].借此，可根据轨道参数计算出每个时间段内各卫星的具体坐标，计算方法如下：

(1)

其中：

Ωi=Ωoi-ωo(t-t0)

(2)

vi=voi+no(t-t0)

(3)

通过以上公式可以得出各卫星对应的直角坐标系[Xi，Yi，Zi]，该坐标系的原点为地心，XOY平面和地球赤道平面重合，OZ轴与地球的极轴重合，OX轴与格林威治子午线方向一致.其中，a为卫星离地心的距离、voi为卫星初始的近地点幅角、Ωoi为卫星初始的升交点赤经、ii为赤道面倾角、no为卫星公转角速度、ωo为地球自转角速度.令t0=0表示初始时刻，改变t的值即可得出各卫星在不同时间段的具体坐标.

在已知各卫星节点的具体坐标后，即可计算出两点的空间距离.非智能卫星节点在可视距离内寻找离自己最近的智能卫星节点，并提出连接请求.智能卫星节点根据自己的最大连接度K与最近的K个卫星建立连接.直到所有非智能节点都得到了连接，或已无合适智能节点可提供连接.求可视距离的示意图如图2所示.

图2 卫星可视性示意图Fig.2 Satellite visibility diagram

通过以上步骤即可得出在某个时间段内所有卫星节点获取边缘服务的情况.本文以Slinkti来表示t时间段内第i颗卫星获取边缘服务的情况，Slinkti=1表示能获取到边缘服务，Slinkti=0表示无法获取边缘服务.因此，单个时间段内边缘服务的有效覆盖率Pt以及一个周期内的边缘服务有效覆盖率P的计算公式如下：

(4)

(5)

其中，n为划分的时间段个数.至此，即可计算出一个运行周期内该系统的边缘服务有效覆盖率P.为下文评判智能节点部署策略的优劣，提供了有效的数据支持.该算法的步骤如下：

算法1.网络分簇算法

输入：节点分布状态D，部署策略X

输出：边缘服务有效覆盖率P

1.初始化：卫星的最大连接度K=4、P=0、连接申请队列Link=∅

2.for每个时间片t

3.根据公式计算出该时间片内各卫星的直角坐标，得出对应Dt

4.while存在d未与x建立连接

5.fordi∈D

6.forxj∈X

7. 计算Lij；

8.endfor

9. 将节点di加入到连接申请队列Linkj；

10.endfor

11.if所有连接申请队列Link≠∅

12. 遍历Link将普通节点加入到对应智能节点所属的簇；

13.else

14.break；

15.endwhile

16.根据(4)式计算出Pt

17.endfor

18.根据(5)式计算出P

19.返回：P

3.2 人工蜂群算法

人工蜂群算法[13，14](Artificial Bee Colony Algorithm，ABC)模拟的是自然界中蜜蜂采蜜的过程.蜜蜂在自然界中，总能在各种环境中以极高的效率找到最优的蜜源，而且能够适应环境的各种变化.人工蜂群算法通过模拟蜜蜂采蜜的过程，将蜂群分为引领蜂、跟随蜂和侦查蜂.在每一次的搜索过程中，引领蜂和跟随蜂先后开采蜜源，寻找最优解，侦查蜂则用于避免陷入局部最优解.该算法可以很好的求出复杂问题的最优解，且收敛速度较快.因此，本文提出一个基于人工蜂群的智能卫星节点优化部署算法iABC.该算法通过对LEO卫星层中智能节点部署策略X进行迭代，利用前文网络分簇算法计算出该策略X下的系统整体边缘服务有效覆盖率P，并以此作为适应度求出最佳的智能卫星节点部署策略.

3.2.1 蜜源的编码表示及问题的初始化

本文使用N维向量X来表示人工蜂群中的蜜源，每一个蜜源代表一个智能卫星节点部署方案.例如某个蜜源Xi的编码表示为：Xi=xi1，xi2，…，xin，其中，xin∈{1，2，…，R}，R为一体化智能网络中卫星节点的个数，且满足xin≠xim，表示卫星节点中，对应编号为xin的卫星部署为智能卫星节点.i∈{1，2，…，M}，M为人工蜂群算法中蜜源的个数，本文取M=10.人工蜂群算法中，引领蜂与蜜源保持一一对应，且跟随蜂数量与引领蜂一致，故都取为M.终止条件设置为达到最大迭代次数MCN或系统整体边缘服务有效时间达到100%.

3.2.2 蜜源的适应度函数及新解的产生

每个蜜源Xi(可行解)都有其花蜜量(适应度fiti)对应相应解的质量.本文计算每个蜜源Xi的适应度fiti采用的是前文提出的网络分簇算法.通过该算法计算出每个Xi的系统平均边缘服务有效覆盖率，并将其作为评判蜜源Xi优劣的适应度.公式如下：

fiti=fcluster(Xi)

(6)

每次迭代的过程中引领蜂都会在蜜源附近寻找新的可行解，具体公式如下：

vij=xij+φij(xij-xkj)

(7)

式中，k∈{1，2，…，M}，j∈{1，2，…，N}，且k≠i，φij为[-1，1]之间的随机数.通过计算新蜜源的适应度fiti，来决定是否取代旧的蜜源.

通过引领蜂提供的蜜源信息(适应度fiti)，跟随蜂采用轮盘赌的方式来决定跟随哪一只引领蜂：

(8)

pi为对应引领蜂被跟随的概率，跟随蜂在到达对应蜜源后由(7)式产生新解，通过计算其适应度fiti，根据新解的fiti来判断是否保留新解.

3.2.3 避免陷入局部最优

设置一个门限值Limit，当一个可行解的迭代次数超过Limit次仍未更新，那么就认为解空间陷入局部最优，此可行解Xi就会被舍弃.当一个可行解Xi被舍弃后，其对应的引领蜂就会转化成侦查蜂，并由(9)式产生一个新的可行解来代替它1.

xij=xminj+rand(0，1)(xmaxj-xminj)

(9)

其中，xminj和xmaxj表示的是解空间中第j维向量的下限和上限，在本文中xminj=0，xmaxj=R.rand(0，1)为0～1内的随机数.

3.2.4 具体步骤

本文基于人工蜂群算法，结合改进的网络分簇算法，提出了一个基于人工蜂群的智能卫星节点部署算法.该算法在智能节点部署数量N以及卫星节点分布状态D已知的情况下，可以通过迭代找出边缘服务覆盖率最高的智能节点部署方案X.算法步骤如算法2所示.之后，可以再通过改变智能节点部署数量N，来找到N取不同值下的最佳智能节点部署策略.

算法2.基于人工蜂群的节点部署算法

输入：节点分布状态D，节点部署数量N

1.初始化：蜜源个数M，最大迭代次数MCN，门限值Limit，fitmax=0，X1～XM，利用(6)式计算出fit1～fitM，更新次数trail1～trailM=0.

2.for迭代次数≤MCNandfitmax<1

3.fori=1：M

4. 利用(7)式得出Xnew，进行贪婪选择保存最优的X；

5.endfor

6.fori=1：M

7. 利用(8)式计算出Pi；

8.endfor

9.fori=1：M

10. 跟随蜂根据P1～Pm决定跟随的对象Xj，j∈{1，2，…，M}；

11. 之后操作与引领蜂活动类似，得出Xnew并决定是否更新Xj；

12.endfor

13.判断是否traili≥limit，若是，则利用(9)式生成新解Xi；

14.更新fiti=fcluster(Xi)，traili=0；

15.保存当前循环的最优解

16.endfor

17.返回X，fitmax；

4 算法仿真

4.1 仿真环境

为了验证智能卫星节点部署策略的有效性，本文利用Matlab和STK平台，搭建了一个天地一体化智能网络中天基接入网的仿真环境.仿真平台的硬件环境为Inter(R)Core(TM)i7-6700HQ CPU @2.60GHz，运行内存为16G.采用了具有66颗LEO的铱星星座(Iridium Constellation)以及3颗位于赤道平面的GEO卫星作为仿真系统.其中，3颗GEO卫星的经度分别为100E、140W和20W.LEO星座的具体参数如表1所示.

表1 星座仿真参数
Table 1 Constellation simulation parameters

LEO卫星参数铱星星座轨道高度780km轨道倾角86.3°轨道数目6单轨道卫星数目11卫星总数66轨道面升交点赤经差60°轨道周期6027.1s连接度4

随着仿真星座规模的大小不同，仿真时，算法的部分参数也会有相应的调整.本次实验中iABC算法的部分参数如表2所示.

表2 基于人工蜂群的智能卫星节点部署算法参数
Table 2 Parameters of intelligent satellite node deployment algorithm based on artificial bee colony

参数名称具体数值时间段长度△t60s蜜源个数M10引领蜂数量10跟随蜂数量10最大迭代次数MCN200门限值Limit20

4.2 仿真结果

智能卫星节点部署数量N的取值，直接决定了整个系统边缘服务有效覆盖率的大小.然而N取值过高会导致部署成本变高.因此N取多少，也是我们需要同时考虑的问题.由于铱星星座具有66颗LEO卫星，设定每颗卫星的连接度为4，则要使系统有效服务覆盖率达到100%，理论上部署边缘服务器的数量N最少为14(66/(4+1)=13.2).故先取N=14，迭代次数为200时得到的优化结果及示意图如图3所示.

图3 当N=14时边缘服务覆盖率优化效果图Fig.3 Edge service coverage optimization result when N=14

根据图3的结果可以看出，当N=14时，该算法可以得出一个智能节点部署策略，使边缘服务的有效覆盖率近似达到98%，非常接近理论值.

图4 iABC算法与iGSA、PSO的优化对比图Fig.4 Optimization comparison chart of iABC algorithm，iGSA and PSO

为了更好地体现iABC算法的优势.本文将提出的iABC算法与iGSA算法和PSO粒子群算法[15](Partical Swarm Optimization PSO)做了详细的仿真对比.在设定并经过1000次迭代后，3种算法得出了不同的部署策略，优化速度和有效覆盖率的优化效果也不尽相同.如图4所示，经过1000次迭代，iABC算法的优化速度明显比另外两个算法高出很多.在优化效果上，也要比iGSA算法与PSO算法高出7.6%左右，因而可以得出更好的最优解.

图5为当N取10～20时，各个算法经过1000次迭代后得到的优化结果对比图.从图中可以明显看出，本文提出的算法在N=16时即可得到一个智能节点部署策略，使边缘服务有效服务覆盖率达到99.85%，在N=17时就可达到100%.而另外两个算法均在N=19时才使有效服务覆盖率达到100%，优化效果提升约为10.5%.

图5 节点数N取不同值时不同算法的优化结果对比图Fig.5 Comparison of optimization results of different algorithms when the number of nodes N takes different values

4.3 平均传输时延的优化结果

通过在智能卫星节点上部署边缘计算服务器，非智能卫星节点可以将复杂计算任务迁移到离自己最近的智能卫星节点上，然后智能卫星节点再将计算结果返回原卫星节点.与传统云计算模型相比，该计算模式可以极大地降低数据的传输距离.因此，更高的边缘服务覆盖率，必然会带来更低的传输时延.图6描述的是所有卫星节点从同时发出计算请求到收到计算结果所需要的平均传输时延.该图的横坐标为部署的边缘服务节点数N，纵坐标为平均传输时延，单位为毫秒(ms).平均传输时延Tra的计算公式为：

Trai=2Si/C

(10)

(11)

其中，Trai为第i颗卫星从发出计算请求到收到计算结果的数据传输时延；Si为第i颗卫星到目标节点的直线距离，若该卫星可以请求到边缘服务，目标节点就取距其最近的边缘服务节点，若无法请求到边缘服务，目标节点则取为离其最近的GEO节点，若第i颗卫星为智能卫星节点，则取Si=0；C为光在真空中的传播速度；R为卫星节点总数[16].

图6 平均传输时延的优化效果图Fig.6 Optimized effect diagram of average transmission delay

传统卫星网络架构中，信息通过GEO卫星进行传输，传输时延高达240ms以上.从图6可以看出，当智能节点数目N=10时，智能卫星网络系统的平均传输时延仅有30ms.当智能节点数N=16时，系统的平均传输时延降到了7ms左右，之后再次增加边缘节点数目，对系统的平均传输时延优化效果就不再明显.因此可以得出：边缘节点的加入，可以有效的降低智能卫星网络系统的平均传输时延.本文提出的基于人工蜂群的智能节点部署算法，可以根据不同星座，快速找出最佳的边缘服务节点部署策略，为今后星上边缘服务系统的部署提供一定的帮助.