0 引言
卫星通信网络由于其覆盖广、部署快、不受地面影响的优点,已经被用于多个商用系统,同时在国家基础服务、抢险抗灾、军事应用等方面也是最可靠的通信手段[1-3]。由于大数据时代的到来传统微波网络在卫星上出现频带资源有限、方向性差、通信容量小的问题,而光网络有着带宽宽、安全性高,传输速率快等优点,会是未来卫星网络发展的必然趋势[4]。受到卫星节点移动速度快、网络拓扑时变性强、卫星大小、功耗和空间环境等因素的影响使得卫星光网络对路由和波长分配(RWA)解决方案提出更高的要求,而卫星光网络的研究重点就是RWA问题[5]。
卫星光网络中路由技术的好坏决定网络性能的优劣。RWA问题的挑战在于同时涉及到业务的路由计算和波长分配问题[6]。在波分复用(WDM)卫星光网络中,RWA问题就是寻找满足波长一致性约束条件下链路代价最小的路径,使得通信阻塞率最小或者波长利用率最高[7]。研究人员已经尝试使用粒子群算法和深度强化学习算法来解决这个问题。Li等[8]提出一种基于软件定义网络(SDN)的深度强化学习卫星光网络RWA算法,利用深度强化学习来感知当前网络状态,可以达到更好逼近最优路径的目的;Wen等[9]提出了基于跨层设计的卫星光网络蚁群RWA算法,将协议栈集成到一个分类框架中,降低跨层开销,提高网络性能;Liu等[10]提出了基于多业务的卫星光网络RWA算法,将业务进行分组,根据不同业务需求进行分配,降低了网络阻塞概率;Sun等[11]提出基于卫星光网络中2种低轨卫星(LEO)星座的RWA算法,提出超级卫星的概念在星座内划分区域,选取中心节点进行统一调度,节省了与控制中心进行信息交互的时间;Dong等[12]提出基于小窗口策略的卫星光网络蚁群RWA算法,加快了算法的收敛性。
然而以上算法存在计算量大、收敛速度慢、陷入局部最优概率大的缺点。Jiang等[13]受到天牛须搜索行为的启发提出一种新的生物启发式优化策略,称为天牛须搜索算法。相比之下,天牛须搜索(BAS)算法具有强大的全局搜索能力和快速的搜索速度,以及通用性和鲁棒性好的优点[14]。Zhang等[15]提出一种基于天牛须群落优化改进算法用来提高卫星时钟偏差预测性能;Aghila Rajagopal等[16]提出一种多任务级天牛须搜索与极限学习机结合的算法用于识别低轨地球轨道(LEO)卫星最优路由,仿真结果表明,与蚁群算法相比具有优越性能;Lin Zhou等[17]提出一种改进的天牛须群落算法,并指出组合策略可以加快整体迭代收敛速度,降低种群陷入局部最优解的概率。
本文针对卫星光网络RWA问题,提出一种基于改进天牛须群落的卫星光网络RWA算法,应用波长矩阵乘的计算方式计算相邻卫星节点之间公有可用波长数量,综合考虑传输时延,卫星节点负载状态,最大可用波长数构建约束优化模型,减少无效路由次数,提高波长利用率。充分考虑卫星之间链路有限特点,以天牛须群落算法为基础,使用组合策略引入蚁群算法信息素的概念,在搜索方向上对具有一定协方差的最大信息素方向和原有算法搜索方向进行随机选择,扩大算法搜索范围,提高寻找最优解的概率。
1 卫星光网络路由问题定义与模型
1.1 卫星光网络RWA模型
卫星光网络RWA模型如图1所示,卫星光网络节点之间通过星间链路(ISL)连接,卫星光网络包含2种ISL,轨间ISL和轨内ISL,轨内ISL稳定性好并且传输延迟固定,轨间 ISL的长度和延迟会随着卫星的运动变化而变化。采用具有RWA 功能的WDM架构构建波长数量相同的ISL网络,多个光路可以共享同一条物理链路,但是会分配不同波长。卫星节点配备了WDM光交换装置,光中继线负责光信号转发和接收,中间交换单元负责把信号从接收端转向发送端,由于卫星节点没有波长转换器,因此,源节点到目的节点建立的通路应该具有同一波长,如图1所示,当业务到来需要从开始节点S到目的节点D之间建立通信时,根据波长一致性原则,选择可用波长为λ2波长建立光链路通路(S→V1→V2→V3→V4→D),其中Vi|i=1,2,3,4表示中间卫星节点。
图1 卫星光网络RWA模型
Fig.1 RWA model of satellite optical network
地球静止轨道(GEO)卫星可以在较高的空间层次使用较少的卫星数量实现无缝覆盖整个地球范围,从而实现通信,但是GEO卫星距离地球赤道 35 786 km,这种无法克服的物理距离导致卫星与地面之间的信号传播时间超过120 ms[18]。高轨道的这一根本问题暴露了使用GEO卫星进行通信出现的实时性差,传输损耗大的缺点,低轨卫星具有轨道高度低,传输损耗低,成本效益高的优点。因此,本文中采用由低轨卫星组成的卫星星座来进行路由算法的仿真验证。
1.2 卫星光网络RWA约束优化模型
卫星光网络的节点位置会随着时间发生变化,但这种变化是有规律的,具有周期性。在较短的时间段内,网络中各个节点的连接关系不变,该时间段的网络拓扑可以看成是静止的,因此采用虚拟拓扑的方法,将光网络中卫星运行一周的时间划分为若干个时间片,在每个时间片内网络拓扑结构可以视为静止状态从而屏蔽卫星光网络拓扑的动态性。将卫星光网络系统的拓扑结构视为无向图,则网络结构可表示为G={V,E},其中V={V1,V2,…,Vn},表示卫星节点集合,E={Eij|i, j∈V,Vi≠Vj},表示卫星之间可建立激光链路的集合。每个节点都应该建立2个表,分别用于登记链路信息和卫星波长矩阵信息。
随着空间技术的迅猛发展,卫星光网络承载业务类型开始变得多样化,需要考虑多个服务质量(QoS)参数进行优化才能满足用户的需求,因此本文中所提出的路由算法将考虑以下几个因素:
1) 单段链路的传输时延公式如下:
(1)
式(1)中:Dij(t)表示在t时刻i、 j卫星节点之间的距离;C表示光速,由于卫星星座的拓扑周期确定,所以Dij(t)可以被提前计算。
2) 卫星节点的负载状态公式定义如下:
(2)
式(2)中:Loj(t)表示j卫星节点在t时刻待处理的消息队列长度;Loj_out表示j卫星节点消息处理速度;Loj_in表示j卫星节点消息到来速度;SP是一个常量,表示卫星节点的负载状态保持恒定并且大于当Loj_out>Loj_in时的最大值,当消息到来速度大于消息处理速度时取值为正无穷。
3) 每个卫星节点应从链路集合获取当前时刻可与自己建立光路链接的卫星节点并构建波长矩阵如下:
(3)
式(3)中:n表示当前时刻可与j卫星节点建立光链路的卫星节点的数量;m表示一个链路的所有波长数。当波长可用时,表示为1,当波长不可用时,表示为0。前一卫星节点与当前卫星节点光链路之间的波长使用矩阵表示如下:
Bji(t)=([Bji1,Bji2,…,Bjim])
(4)
在每次进行路由选择的时候,根据前一节点与当前节点之间的波长矩阵做乘积,根据结果计算波长冲突度,计算公式如下:
Bc(t)=Bji(t)(Bjn(t)-Bji(t))T
(5)
式(5)中,Bjn(t)-Bji(t)表示当前卫星波长矩阵去掉i、 j卫星的波长矩阵之后所表示的最终波长矩阵。在Bc中选择最大值作为备选路径,记为Bjmax,表示为
Bjmax(t)=maxBc(t)
(6)
式(6)中,如果Bjmax(t)的值大于零,表示前一节点与当前节点之间拥有公有空闲可用波长,否则,代表该路径无公有可用波长,不满足波长一致性约束。
单段链路消耗定义公式如下:
Costij(t)=Delayij+Loadj
(7)
建立约束优化模型如下:
(8)
式(8)中:Costsd(t)表示从开始节点到目的节点的路径消耗;Dmax、Lomax分别表示最大传输时延的设定阈值和最大负载状态阈值。第1个约束条件表示单段链路的传输时延应该小于单段链路最大传输时延的设定阈值,以确保应用的服务质量要求。第2个约束条件表示单段链路的负载状态应小于单段链路最大负载设定阈值,确保数据的可达性。第3约束表示当前卫星节点最终生成的波长矩阵中的最大值必须大于零来确保路由过程中满足波长一致性。
2 改进天牛须群落的卫星光网络RWA算法
天牛须群搜索算法是借用粒子群的思想对原始天牛须搜索算法进行扩展的一种群优化搜索算法。与其他群优化算法一样,每个天牛代表一种优化问题的潜在解决方案,个体之间进行信息共享。每个天牛的距离和方向由他们的生长速度和天线检测到的信息强度决定。本文中天牛群落数量表示为X=(X1,X2,…,XN),N表示天牛群落的整体数量,单个天牛搜索位置Xn=(X1n,X2n,…,XKn),其中Xkn表示天牛群落中第n个天牛在第k个搜索维度所处的位置,根据适应度函数可以计算出每个天牛的适应度值,单个天牛的速度表示为Sn=(S1n,S2n,…,SKn)T。
原始搜索方向采用随机搜索方向增大算法搜索范围,但是收敛性能不足,因此搜索方向选择引入蚁群算法的信息素机制,采用具有一定协方差的最大信息素水平的方向之一和原始随机搜索方向之间进行选择来扩大算法的搜索范围,对搜索方向进行更新,公式如下:
(9)
式(9)中:
表示每个天牛个体的下一个运动方向;τ表示每个天牛个体的信息素水平;
表示天牛在搜索过程中最大信息素的方向;σ表示协方差;rands(·)表示生成随机方向的函数;k表示算法中天牛个体的搜索维度,将其归一化作为基础搜索方向; β表示二项分布的结果,通过引入二项分布,增加搜索方向的随机性,扩大算法的搜索范围,减少陷入局部最优的概率。将生成的新的搜索方向按照搜索维度进行划分
信息素更新公式如下:
(10)
式(10)中: τij(t+Δt)表示在i、 j链路上进行下一个状态转换生成的新的信息素的值;ρ∈[0,1]表示信息素的挥发程度;
表示第n个天牛在链路i、 j上沉积的信息素值。
(11)
式(11)中: Cn表示第n只天牛经过的路径的长度;I表示上一代天牛完成路径选择之后释放的信息素浓度总和。对天牛个体在下一时刻的位置进行更新,公式如下:
(12)
式(12)中:
表示第n个个体在第t+1次迭代的第k个维度位置;
表示第n个个体在第t次迭代在第k个维度的位置;
表示第n个个体在第k个维度的运行速度;sign表示符号函数; f表示当前个体的适应度函数。
通过使用当前卫星节点的负载因子,结合卫星传输时延和波长利用率对适应度函数进行定义,公式如下:
(13)
式(13)中:Delayij(t)、Bjmax(t)、Loadj(t)分别表示当前卫星i到下一节点j的传输时延、当前卫星最大可用波长数和下一卫星节点的负载状态。Delaymax、m、Lomax分别表示卫星最大传输时延、链路之间波长总数、队列最大长度。其中λ1、λ2、λ3分别表示传输延迟、波长冲突度和负载状态的权重且 λ1+λ2+λ3=1。
BS-ACRWA算法的算法流程如图2所示。
图2 BS-ACRWA算法流程图
Fig.2 BS-ACRWA algorithm flow chart
3 仿真分析
3.1 仿真场景设置
本文中首先使用STK仿真软件对卫星光网络架构进行模拟仿真,使用NS2搭建路由仿真平台,在此基础上使用C++ 对所提算法进行了仿真验证。采用铱星星座系统作为LEO卫星光网络的仿真场景,由6个轨道面66颗卫星组成,每个轨道面内11颗卫星,星间链路最大可用波长数为16[19],卫星光网络铱星星座参数如表1所示,星座拓扑结构如图3所示。
表1 卫星星座参数
Table 1 Satellite constellation parameter
参数名称Iridium节点数量N66轨道数量P6卫星高度/km780轨道倾角/(°)86.4单个轨道节点数S11轨道周期s6 840节点终端数量4轨内ISL距离/km4 033轨间ISL距离/km≤6 594
图3 卫星光网络铱星星座拓扑图
Fig.3 Iridium satellite optical network constellation topology
3.2 仿真结果分析
为了说明算法性能,将该方法与文献[20]所提出的基于多业务的卫星光网络蚁群优化波长路由算法(SARWA),文献[8]所提出的基于跨层设计的蚁群路由和波长分配算法(CL-ACRWA)以及Dijkstra算法进行比较。业务强度是网络每小时被占用的波长信道与平均占用时长的乘积,单位为Erl[12]。在卫星光网络的仿真场景中,4种算法在不同业务强度下网络平均时延的比较如图4所示,在业务强度较低的时候,4种算法的平均时延基本相等,这是因为当业务强度较低的时候,网络的空闲状态较高,满足算法选择条件的卫星节点的数量较多,出现不满足算法选择条件的概率较小,业务总是以最短路径从源节点到达目的节点。随着业务强度的增加,不满足算法选择条件的卫星节点数量增加,不同算法的平均时延出现差异,其中BS-ACRWA算法的平均时延最小,其次是SARWA算法,然后是CL-ACRWA算法,最后是Dijkstra算法。从图3可以看到BS-ACRWA算法的平均时延总是小于其他3种算法的,随着业务强度的增加BS-ACRWA算法平均时延比SARWA算法降低了5%,比CL-ACRWA算法降低了10.8%。
图4 比较不同算法的网络平均时延
Fig.4 Compare the average network delay of different algorithms
图5展示了在不同业务强度下4种算法的网络平均丢包率的变化,从图5中可以看到,当业务强度较小的时候,4种算法的丢包率相差不大,这是因为业务强度小,满足算法选择的节点数量多,影响丢包率的主要因素是数据包在卫星之间进行传播,随着业务强度的不断增加,算法的丢包率也在不断增加,此时影响丢包率的因素中传输时延所占比重不断减小,卫星节点的负载状态过高导致的丢包率所占的比重在不断增加。随着业务强度的增加,不同算法的丢包率出现差异,其中BS-ACRWA算法的丢包率总是小于其他3个算法,特别当业务强度为550 Erl时,BS-ACRWA算法的丢包率比SARWA算法小了0.02,比CL-ACRWA算法小了0.05,这是因为当业务强度高的时候,一些卫星节点的负载状态比较高,BS-ACRWA算法在路由过程中考虑了卫星节点负载状态,当有2个负载状态不同的卫星节点都满足选择条件的时候,BS-ACRWA算法会选择负载状态较小的卫星节点。
图5 比较不同算法的网络平均丢包率
Fig.5 Compare the average packet loss rate of different algorithms
在不同业务强度下不同算法的网络阻塞率如图6所示,从图6中可以看到,随着业务强度的增加,卫星节点要处理的数据包的数量增加导致卫星光网络的拥塞率增加。与其他算法相比,BS-ACRWA算法在不同业务强度的网络阻塞率最低,当业务强度为300 Erl时,BS-ACRWA的网络阻塞率比SARWA小0.07,比CL-ACRWA小0.11,比Dijkstra小0.37。在进行卫星节点选择时,BS-ACRWA算法考虑了卫星节点的链路长度信息、卫星节点的负载状态和当前里链路是否有公有可用波长。相比之下,Dijkstra算法只关心链路长度信息,无法根据网络环境的改变做出调整,所以随着业务强度的增加网络阻塞率会迅速增加,SARWA算法和CL-ACRWA算法都会考虑卫星节点的负载状态,由于SARWA算法将不同业务划分了等级,不同的业务在进行路由过程中会根据条件选择不同的卫星节点,因此在网络阻塞率方面的性能优于CL-ACRWA算法,但是都没有考虑当前链路是否有公有可用波长,所以在网络阻塞率上的性能都低于BS-ACRWA算法。
图6 比较不同算法的网络阻塞率
Fig.6 Compare the network blocking rate of different algorithms
图7表示了在不同业务强度下不同算法的通信成功率的变化,从图中可以看到4种算法的通信成功率都会随着业务强度的增加而下降,原因在于在高业务强度的情况下,网络拥塞程度增大,导致数据包丢失、延迟增加等问题,从而影响通信成功率。当业务强度为450 Erl时,BS-ACRWA算法的通信成功率比SARWA算法高4%,比CL-ACRWA算法高7%,比Dijkstra算法高15%,证明了BS-ACRWA算法在进行路由过程中的稳定性。
图7 比较不同算法的通信成功率
Fig.7 Compare the communication success rate of different algorithms
波长利用率是卫星路由算法的重要指标之一,本文通过在路由选择阶段使用波长冲突度的概念来提高算法的波长利用率。从图8可以看出,当业务强度较低的时候,所有算法的波长利用率都比较低,这是因为在业务强度较低的情况下,链路波长资源处于空闲状态的数量较多,随着业务强度的增加,4种算法的波长利用率都在增加。从图8中可以看出,BS-ACRWA算法的波长利用率总是优于其他算法,特别地,当业务强度为450 Erl时,比SARWA算法高0.05,比CL-ACRWA算法高0.11,比Dijkstra算法高0.23,证明了所提算法在提高波长利用率上的有效性。
图8 比较不同算法的波长利用率
Fig.8 Compare the wavelength utilization rate of different algorithms
4 结论
基于改进天牛须群落的卫星光网络路由算法可以根据当前卫星光网络的节点状态做出最佳的路由和波长分配策略,保障网络阻塞率、通信时延、丢包率、通信成功率并且提高波长利用率。
基于改进天牛须群落的卫星光网络路由算法利用组合策略提高算法性能,其中引入蚁群算法信息素机制扩大搜索范围减少陷入局部最优的概率。下一步的研究工作将针对卫星光网络中通信可靠性进行优化,提高卫星通信可靠性。
[1]张沛,刘帅军,马治国,等.基于深度增强学习和多目标优化改进的卫星资源分配算法[J].通信学报,2020,41(6):51-60.ZHANG Pei,LIU Shuaijun,MA Zhiguo,et al.Satellite resource allocation algorithm based on deep reinforcement learning and multi-objective optimization[J].Journal of Communication,2020,41(6):51-60.
[2]胡先童.基于平均场博弈的超密集5G小蜂窝网络下行功率管理[J].重庆工商大学学报(自然科学版),2022,39(6):105-111.HU Xiantong.Downlink power management of Ultra-dense 5G small cellular networks based on mean field game[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2022,39(6):105-111.
[3]GUIDOTTI A,VANELLI-CORALLI A,CONTI M,et al.Architectures and key technical challenges for 5G systems incorporating satellites[J].IEEE Transactions on Vehicular Technology,2019,68(3):2624-2639.
[4]SHI Y,CAO Y,LIU J,et al.A cross-domain SDN architecture for multi-layered space-terrestrial integrated networks[J].IEEE Network,2019,33(1):29-35.
[5]LIU Y,ZHANG Q,XIN X,et al.Bee colony algorithm optimization based on link cost for routing and wavelength assignment in satellite optical networks[J].IEICE Transactions on Communications,2020,103(6):690-702.
[6]王蔚龙,李勇军,赵尚弘,等.基于改进蚁群算法的卫星光网络波长分配方法[J].激光与红外,2021,51(7):909-916.WANG Weilong,LI Yongjun,ZHAO Shanghong,et al.Wavelength allocation method of satellite optical network based on improved ant colony algorithm[J].Laser &Infrared,2021,51(7):909-916.
[7]王蔚龙,李勇军,赵尚弘,等.基于负载均衡的卫星光网络路由与波长分配方法研究[J].激光与光电子学进展,2021,58(7):0706004.WANG Weilong,LI Yongjun,ZHAO Shanghong,et al.Research on routing and wavelength allocation of satellite optical networks based on load balancing[J].Laser &Optoelectronics Progress,2021,58(7):0706004.
[8]李信,李勇军,赵尚弘.基于深度强化学习的卫星光网络波长路由算法[J/OL].系统工程与电子技术:2022,43(4):1-9.LI Xin,LI Yongjun,ZHAO Shanghong.Wavelength routing algorithm for satellite optical networks based on deep reinforcement learning[J/OL].Systems Engineering and Electronics,2022,43(4):1-9.
[9]WEN G,ZHANG Q,WANG H,et al.An ant colony algorithm based on cross-layer design for routing and wavelength assignment in optical satellite networks[J].China Communications,2017,14(8):63-75.
[10]刘庆利,姚俊飞,刘治国.基于多业务的卫星光网络波长路由算法研究[J].系统仿真学报,2017,29(8):1780-1787.LIU Qingli,YAO Junfei,LIU Zhiguo.Research on wavelength routing algorithm based on multi-service in satellite optical networks[J].Journal of System Simulation,2017,29(8):1780-1787.
[11]SUN X,CAO S.A routing and wavelength assignment algorithm based on two types of leo constellations in optical satellite networks[J].Journal of Lightwave Technology,2020,38(8):2106-2113.
[12]DONG Y,ZHAO S,RAN H,et al.Routing and wavelength assignment in a satellite optical network based on ant colony optimization with the small window strategy[J].Journal of Optical Communications and Networking,2015,7(10):995-1000.
[13]JIANG X,LI S.BAS:Beetle antennae search algorithm for optimization problems[J].International Journal of Robotics and Control,2018,1:2577-2582.
[14]YA S,ZHAO X,LIU C,et al.Enhancing short-term prediction of BDS-3 satellite clock bias based with bso optimized BP neural network[J].International Journal of Aerospace Engineering,2022,26:1546-1564.
[15]ZHANG B,DUAN Y,ZHANG Y and WANG Y,Particle swarm optimization algorithm based on beetle antennae search algorithm to solve path planning problem[J].2020 IEEE 4th Information Technology,Networking,Electronic and Automation Control Conference (ITNEC),2020(1):1586-1589.
[16]RAJAGOPAL A,RAMACHANDRAN A,SHANKAR K,et al.Optimal routing strategy based on extreme learning machine with beetle antennae search algorithm for Low Earth Orbit satellite communication networks[J].International Journal of Satellite Communications and Networking,2021,39(3):305-317.
[17]ZHOU L,CHEN K,DONG H,et al.An improved beetle swarm optimization algorithm for the intelligent navigation control of autonomous sailing robots[J].IEEE Access,2020 9:5296-5311.
[18]GIAMBENE,GIOVANNI,CLAUDIO SACCHI,et al.Personal satellite services[J].Third International ICST Conference,2011(1):17-18.
[19]CHAN V W S.Optical satellite networks[J].Journal of Lightwave Technology,2003,21(11):2811—2827.
[20]石晓东,李勇军,赵尚弘,等.软件定义卫星光网络蚁群优化波长路由技术[J].红外与激光工程,2020,49(10):211-218.SHI Xiaodong,LI Yongjun,ZHAO Shanghong.Ant colony optimization routing and wavelength technology for software-defined satellite optical networks[J].Infrared and Laser Engineering,2020,49(10):211-218.