【《空间光网络模型设计和路由算法分析案例》8300字】

空间光网络模型设计和路由算法分析案例目录TOC\o"1-3"\h\u8933空间光网络模型设计和路由算法分析案例 1501.1联合DFS和Dijkstra路由算法 1315141.1.1网络模型 179121.1.2路由算法 4202551.2基于跨层设计的路由算法 781951.2.1理论模型 8111171.2.2路由算法 11263351.3多约束QoS路由算法 16214171.1.1理论模型 16182691.1.2路由算法 181.1联合DFS和Dijkstra路由算法尽管Dijkstra算法方法很简单，但它没有考虑网络状态信息，相同的源-目标节点将仅选择相同的传输路径，这很容易导致链路的部分拥塞。参考文献24提供了一个基于SDN的LEO卫星网络，该网络在光学卫星网络的最短路径中使用Dijkstra算法。将SDN的思想与LEO卫星网络相结合，可以实现对网络的更加灵活的监视和管理，使网络扩展更为便捷。通过结合深度搜索（DFS）的思想和Dijkstra的算法，对于大量基于SDN的LEO移动卫星网络，提高了计算效率，并提高了计算结果可靠性。1.1.1网络模型如图1.1显示了基于SDN的光卫星网络的逻辑架构。其中，网络体系结构的应用层由各种空间任务组成。控制层是整个体系结构的核心，由几个GEO控制器组成，GEO卫星具有全球视野，负责制定特定的路由策略。基础设施层由LEO卫星光网络组成，并负责根据GEO卫星发送的流表的元素来处理和发送相应的数据。在LEO卫星光网络中，通信链路都是激光链路，这些链路使用WDM技术在光链路中建立多波长信道，并使用经过优化的波长路由技术。图1.1基于SDN的卫星光网络逻辑架构图1.2显示了基于SDN的光卫星网络路由机制的基本过程。GEO卫星用作SDN控制器，以通过南接口与LEO卫星光网络进行通信。首先，GEO卫星必须与LEO卫星光网络中的每个卫星节点进行交互，以获得整体拓扑状态和节点链接信息。然后，通过部署在GEO卫星中的波长路由算法对该信息进行处理，以实时计算最佳传输路径，并且该路径信息会通过南向接口均匀分布到网络中的每个卫星节点。整个网络路由过程反映了SDN对网络进行集中控制和管理的特征。图1.2基于SDN的卫星光网络路由算法在LEO卫星网络中，卫星节点的操作随时间变化，并且是周期性的，并且节点不断地进行连接-断开-连接。但是，在一定时间段内，如果网络中不同节点之间不存在连接关系，则该时间段内的网络拓扑可以认为是静态的。因此，虚拟拓扑的思想可以用来将卫星绕卫星网络运行的时间T划分为几个时隙。在每个时隙中，网络的拓扑保持静态，这有效地保护了卫星网络的拓扑。高动态。传输数据包时，只需确定源节点和目的节点，然后根据相应的时隙计算出路由信息即可完成数据传输，如图1.3所示。使用此方法可以显着减少LEO卫星网络中卫星节点路由的计算开销，同时还可以提高数据包传输的效率并增加数据传输的延迟。图1.3基于虚拟拓扑的路由机制1.1.2路由算法Dijkstra算法一种经典路由算法，用于查找最短路径。该算法用于查找从源节点到网络中所有其他节点的链路成本最少的路径。但对于给定源节点和目标节点的有向图，需要对经典的Dijkstra算法进行适当的改进，一旦标记了目标节点，循环就会结束，输出源节点和目标间的最短路径和最短路径链接成本。DFS算法可以找到源节点和目标节点之间的所有通信路径以满足通信需求，因为它们将搜索图的每个节点。所以，可以获得所有链接信息，并且结果的可靠性更好。但是由于需要搜索拓扑图中的每个节点，因此该算法的时间复杂度非常高，为O（n！）。因此，当卫星节点数量达到数百或更高时，算法的计算效率将极低。卫星的拓扑可能已更改，因为它尚未计算所需的路径。可以采用修剪以提高DFS算法的效率。修剪的关键思想是删除无用的搜索分支。常用的修剪方法是可行修剪，概率修剪，最优修剪等。由于Dijkstra算法只需要找到源节点和目的节点之间开销最小的链路，因此该算法的时间复杂度较低，为平方阶O（n

2），因此计算效率较高。但是它仅以最小的链路开销找到路径的一部分，因此在查找路径时，它可能会跳过所需的必要节点，并且找到的路径不符合要求，从而导致路由失败。图

1.4显示了卫星通信网络拓扑的一部分，其中S代表源卫星，D代表目的卫星，而S

1是必需的卫星节点。Dijkstra算法将根据链路成本选择链路成本较小的路径，计算出的传输路径为S

-

S

2-

D，可以看出该路径不包括不满足传输需求的必要卫星节点S

1。要求。在DFS算法将计算源节点与目的地节点之间的所有传送路径，所以结果包含两个路径小号-S

2-

D和S

-

S

1-

D，根据通信要求，因此可以根据需要选择传输路径为S

-

S

1-

D。因此，在LEO卫星网络中计算路由信息时，可以考虑这两种算法的优点。因此，将两种算法结合起来，不仅可以提高算法的效率，而且可以提高找到的所需路径的可靠性。图1.4部分拓扑在有大量卫星节点的情况下，我们将DFS和Dijkstra算法集成在一起，以提高计算效率。根据网络的实时情况，将LEO卫星网络划分为一系列集群。因此，根据不同恒星群的链接条件，采用了DFS算法和Dijkstra算法。在网络流量大，网络拥塞高的组中使用Dijkstra算法，在有大量必要卫星的组中采用DFS算法。它不仅可以提高通信路径的计算效率，而且避免了Dijkstra算法的局限性，可能导致计算结果不符合要求。图1.5显示了联合DFS和Dijkstra算法的过程。首先，在卫星通信过程中，我们设置了源卫星，目的卫星和必要的卫星节点集。在源卫星节点处，使用Dijkstra算法查找从其他卫星节点到源卫星节点的链路成本最低的路径。当与之间的第一发现需要卫星节点和源卫星最小的链路成本的路径被找到时，Dijkstra算法端和Subsetnode−1，其中Subsetnode代表所需的必要卫星节点数。然后，我们使用第一个找到的必要卫星节点N

1作为起始节点，采用DFS算法，即D

F

S（N

1），每次搜索必要节点Ni时，检查Subsetnode等于0，如果Subsetnode≠0，我们将继续使用DFS算法进行深度搜索，即D

F

S（Ni），否则，如果Subsetnode=0，则DFS算法结束。最后，我们将最后找到的必要卫星节点作为起始节点，并采用Dijkstra算法找到最后找到的必要卫星节点与目的卫星之间的链路开销最小的路径。通过整合以上步骤，我们可以找到符合要求的通信链接。这样，可以通过减小DFS算法的问题量表的大小来大大减少计算时间，并且由于使用深度优先搜索不会跳过必要的卫星节点，因此提高了路径的可靠性。Dijkstra算法可以有效地避免卫星组中业务量分布较大的卫星节点超出必要的卫星节点，从而减少了机载存储器中数据包的排队时间，并减少了数据的平均端到端延迟通信，从而提高了卫星网络的效率。图1.5联合DFS和Dijkstra算法1.2基于跨层设计的路由算法文献25提出了一种基于跨层设计的蚁群波长分配和路由算法（CLACRWA），该算法可以克服多普勒波长向光学卫星网络中的数据移动。首先，建立考虑了多普勒波长偏移，传播延迟和波长连续性的约束的层间优化模型。然后，采用蚁群算法求解层间优化模型，从而为每个连接请求找到满足上述约束的最优光路。CLACRWA的性能通过信息成功收敛和传输延迟的概率来衡量。同时，传输时延可以满足实时业务传输的基本要求。1.2.1理论模型如图1.6所示，系统架构由卫星网络，网关地球站（GES）和卫星用户组成。卫星网络由具有光学ISL的Walker星座组成，可以实现全球空基通信服务。沃克星座可以表示为θ：N/P/F[15]RyutaroSuzuki,YasuhikoYasuda.StudyonISLnetworkstructureinLEOsatellitecommunicationsystems[J].ActaAstronautica,2006,61(7):648-658.15]，其中θ是轨道平面的倾斜度，N是卫星总数，P是轨道平面数，每个轨道由S个卫星组成[15]RyutaroSuzuki,YasuhikoYasuda.StudyonISLnetworkstructureinLEOsatellitecommunicationsystems[J].ActaAstronautica,2006,61(7):648-658.图1.6系统架构假设在光学卫星网络中采用常规星座，具有波长路由的WDM体系结构可用于ISL，并且中间节点中没有波长转换器，则应在波长连续性约束下建立光路。跨层优化可以将协议栈的各层集成到一个综合的分类框架中，从而可以提高卫星网络的性能[16]HWang,QZhang,XXin,etal.Cross-layerdesignandant-colonyoptimization-basedroutingalgorithmforlowearthorbitsatellitenetworks[J].ChinaCOounications,2013,10(10):37-46.16][16]HWang,QZhang,XXin,etal.Cross-layerdesignandant-colonyoptimization-basedroutingalgorithmforlowearthorbitsatellitenetworks[J].ChinaCOounications,2013,10(10):37-46.在图1.7中，第一部分描述了应用的QoS要求的两个重要因素，包括传输延迟和BER[17]FDong,OLi,XRan,etal.AdynamicprotocolstackstructurefordiversifiedQoSrequirementsinAdHocnetwork[J].ChinaCommunications,2016,13[S1]:43-51.17][17]FDong,OLi,XRan,etal.AdynamicprotocolstackstructurefordiversifiedQoSrequirementsinAdHocnetwork[J].ChinaCommunications,2016,13[S1]:43-51.[18]ZHaitao,ZShaojie,EmilianoGarcia-Palacios.Cross-LayerFrameworkforFine-GrainedChannelAccessinNextGenerationHigh-DensityWiFiNetworks[J].ChinaCommunications,2016,13(02):55-67.图1.7体系结构的跨层设计的问题目的是为每个源到目的地的连接请求寻找总成本最低的光路。考虑到传输延迟，多普勒波长偏移和波长连续性的约束，将跨层优化模型描述为Minmize：subjectton∈P(s,d)∀∀(1.1)首先，也是最重要的，相关的符号定义如下所示，在图1.8中，P(s,d)代表一个光路从源卫星s连接请求开始，经过一系列的中间节点，到达目的卫星d。n是在P(s,d)上一个卫星，i是输入链接，j是卫星n的输出链接到在P(s,d)上的下一个节点，link(n,j)是一个ISL从卫星n，通过输出链接j，到在P(s,d)上的下一个节点。Ω={λ1，…，λk，…,λW}图1.8光路的原理图其次，Costsd(t)表示P(s,d)在时刻t的光路总成本。Costsd(t)由两部分组成，分别是由传输延迟引起的链路成本和由多普勒波长偏移引入的链路成本。因此Costsd(t)Cost(1.2)在式中TDmax和|∆λTDnj(t)表示在时刻t从卫星n通过输出链路j到下一个卫星的传输延迟。它由两部分组成，信号通过link(n,j)的传播延迟和中间节点转发信号的处理延迟，分别表示为PDnj(t)和PRT(1.3)在此，PDnj(t)由两颗卫星之间的距离确定。PRDnj[19]NKARAFOLS,SBARONI.Opticalsatellitenetworks[J].Journaloflight-wavetechnology,2000,18(12):1792-1806.∆λnjt表明从卫星n多普勒波长位移，通过输出链接j，在时刻t到下一个卫星。两个ISL卫星的相对距离变化随着时间的推移，∆λnjt[20]QYang,LTan,JMa.Dopplercharacterizationoflaserinter-satellitelinksforopticalLEOsatelliteconstellations[J].OpticsCommunications,2009,282(17):3547-3552.正如TDnj(t)和∆λ第三，TDth和∆λth是传输延迟阈值和多普勒波长位移阈值，其实时传输业务可以分别在光学卫星网络容忍。P(s,d)的传输延迟和多普勒波长偏移的ISL不能大于TDth最后，wnjt是用在linkn,j∈P(s,d)上的波长连接请求。为了满足波长连接约束每个ISL沿着光路中使用的波长应该是一样的[21]HZang,JPJue,BMukherjee.Areviewofroutingandwavelengthassignmentapproachesforwave-length-routedopticalWDMnetworks[J].OpticalNetworksMagazine,2000,1(1):47-60.21]。[21]HZang,JPJue,BMukherjee.Areviewofroutingandwavelengthassignmentapproachesforwave-length-routedopticalWDMnetworks[J].OpticalNetworksMagazine,2000,1(1):47-60.1.2.2路由算法在CLACRWA中，信息素集中根据三种信息，包括路径长度，波长使用和多普勒波长偏移来计算。对于前向蚂蚁，路径长度越短，则蚂蚁越有可能通过。关于蚂蚁一定移动的可取性的启发式信息称为可取性，并定义为nnjd=(1.4)其中，nnjd是前向蚂蚁选择卫星n到卫星d的输出链路j的可取性，|xnjd(t)|是从n波长使用量是通过特定输出链路和波长对资源保留的度量。若资源预留成功，将提高信息素浓度，否则浓度将降低。多普勒波长偏移可以通过特定的输出链路反映BER特性。当多普勒频移的值大于时，信息素浓度将降低。每个卫星都有一个信息素表（PT）。表1显示了具有两个输入和输出链接，两个波长和两个目的地的信息素表示例。信息素值具有以下含义：i是输入链路，j是输出链路，k是在两个卫星之间切换的波长，而d是目标卫星。表1信息素表CLACRWA由两个主要阶段组成：初始化阶段和实施阶段。在初始化阶段，将初始化参数。对于每颗卫星n，都会初始化其信息素表。对于每个目标卫星d，建立其在时刻t从卫星n到卫星d的可用相邻卫星的候选列表，用Nnd(t)表示。同样地，来自于卫星可用波长的候选人名单n，通过输出链路j到卫星d在时刻t，由下式Wnj如图1.9所示，一旦初始化阶段结束，它将等待进入实施阶段。当源到目标的连接请求到达时，实现阶段开始，源卫星将创建许多前向蚂蚁。实施阶段中使用的相关符号和条件解释如下。图1.9CLACRWA算法xd（t）记录转发蚂蚁通过的路径。Antblocked表示蚂蚁是否被阻止。Antblocked=1表示蚂蚁被阻止，而Ant图1.9所示，在实施阶段有四个部分：初始波长分配、状态转换规则，局部更新规则和全局更新规则。每个部分的细节描述如下。(1)初始波长分配首先，前向蚂蚁从光源开始，运行初始波长分配规则，选择输出链路u和波长λu，λ=(1.5)Nndt随着Wnj（2）状态转换规则随后，当来自输入链路i的前向蚂蚁到达中间卫星n时，它使用以下状态转换规则选择输出链路u切换到下一个卫星。u=(1.6)r~U(0，1)，r0∈[0,1]是一个参数，用于确定开发与探索的相对重要性：前向蚂蚁采样一个随机数0≤r≤1。如果r不大于r0那是最好的输出链接，根据等式上被选择，否则根据下式选择输出链接。plink(1.7)(3)局部更新规则成功进行切换预留后，波长可用，并且多普勒波长偏移小于∆λτ(1.8)∝1∈(0,1)是信息素的增量系数。（4）全局更新规则当转发蚂蚁被阻止或到达目的地时，卫星将会创建一个反馈蚂蚁并执行全局更新规则。反馈蚂蚁沿着路径前进，然后沿着路径返回源卫星，并在此过程中更新信息素浓度。该规则显示为

τijkd(1.9)β1∈(0,1)是信息素衰减参数。γijk确定是否使用正反馈或负反馈来更新信息素浓度，其定义如式（1.10）所示。γ(1.10)如方程式所示（1.10），取值为true的标志成功应满足以下条件：1）转发蚂蚁成功到达目的卫星；2）路径上每个ISL的波长使用和多普勒波长偏移应满足约束。当success是true的时，沿着这条道路xdt就会有积极的反馈。沿路径的每颗卫星n从输入链路v到波长λ到输出链路u的信息素浓度都得到了增强。如果success是flase的，那么这条路径上就会出现负面反馈。负反馈有两种不同形式：1）当由于在k的第k个波长上的波长资源保留失败而使卫星m中的前向蚂蚁被阻挡时，沿路径的每个卫星n的输入链路v到波长到输出链路u的信息素浓度会减弱；2）当由于多普勒波长偏移大于导致在卫星m中阻止前向蚂蚁时，到卫星m的输出链路如（1.11）中所述，信息素沉积经历指数衰减并且衰减常数为w。∆l=|x∆(1.11)当反馈蚂蚁到达源卫星时，蚂蚁的搜索行为结束了，将重复进行直到所有蚂蚁都完成搜索行为为止。然后通过使用等式(1.1)中的成本表达式。在整个蚂蚁找到的所有可用路径中确定最佳路径。最终，建立了可靠的光路。另外，由于卫星相对于用户处于运动中，并且由于指向，获取和跟踪要求，某些星座具有非永久性ISL，因此连接可能会在其整个生命周期中断开。在这种情况下，连接将完全重新路由[22]LFranck,GMaral.Routinginnetworksofintersatellitelinks[J].IEEETransactionsonAerospaceandElectronicSystems,2002,38(03):902-917.22][22]LFranck,GMaral.Routinginnetworksofintersatellitelinks[J].IEEETransactionsonAerospaceandElectronicSystems,2002,38(03):902-917.1.3多约束QoS路由算法在波长分配方面，如果不对业务进行区分服务，会导致高QoS需求的业务以及高优先级的业务不能得到及时处理，从而降低网络性能。因此，在进行路径选择和波长分配时，应充分考虑网络结构的动态变化、业务差异化QoS需求以及网络的波长使用和阻塞情况[23]ShiX,LiY,ZhaoS,etal.Multi-QoSadaptivealgorithmbasedSDNforsatellitenetwork[C].IOPConferenceSeries:MaterialsScienceandEngineering,2020.23][23]ShiX,LiY,ZhaoS,etal.Multi-QoSadaptivealgorithmbasedSDNforsatellitenetwork[C].IOPConferenceSeries:MaterialsScienceandEngineering,2020.文献26针对卫星光网络，提出了一种基于SDN的蚁群优化波长路由算法(Ant

colony

optimization

wave-length

routing

algorithm

based

on

SDN，SARWA)。首先，对传统的蚁群算法进行了改进，将4种业务的QoS需求与蚁群算法相结合，作为蚂蚁选路的考虑因素，进而选出一条满足多种QoS的路径。其次，对业务进行分类，为不同业务分配不同的波长集，从而降低高优等级业务的阻塞率。1.1.1理论模型随着空间技术的飞速发展，卫星光网络已经从仅需要提供传输功能的运营商网络发展成为需要为用户提供各种服务的企业网络。在光卫星网络中，空间服务的类型主要包括控制服务，语音服务，视频服务和数据服务。不同类型的空间服务必须满足不同的服务质量要求。针对单个QoS参数优化的路由算法不再能够满足用户需求。卫星光网络应该支持不同QoS的自适应路由过程，而不是仅仅支持传输，因此，在业务路由过程中应充分考虑业务的动态变化特