一种基于负载感知的多层卫星网络路由方法
一种基于负载感知的多层卫星网络路由方法
【技术领域】
[0001] 本发明属于卫星通信技术领域，尤其设及一种基于负载感知的多层卫星网络路由 方法。
【背景技术】
[0002] 多层卫星网络（MLSN)作为下一代卫星通信构架的杰出代表，在近年来得到了广 泛的关注和研究。与传统的单层卫星网络不同，多层卫星网络由低轨道卫星（LEO)、中轨道 卫星（ME0)W及地球同步轨道卫星（GE0)等多种卫星星座融合而成，因此，它具有覆盖范围 广、传送时延短、网络容量大等优点。此外，该种层次化的网络构架便于网络的高效管理，从 而使得信息交互的开销更小，网络的鲁椿性更高，能够快速地从节点故障、链路中断等情况 中恢复过来。为了能够有效地在多层卫星网络中传输业务，路由策略是必不可少的。然而， 由于卫星周期性地绕地球转动，导致卫星网络的拓扑快速变化，链路中断和切换频繁发生， 该对路由协议的有效性提出了巨大挑战。此外，受气候、经济、地形等因素影响，地球表面人 口分布极度不均匀，导致业务的需求呈现较大的差异性，从而出现某些卫星已经非常拥塞 并开始大量丢包，而一部分卫星并未得到充分利用的情况。因此，有必要提出一种有效的路 由协议来捕捉并利用网络的拓扑变化，并实现网络的负载均衡，提高整体的吞吐量性能。
[0003] 目前，为了提高LE0/ME0多层卫星网络的吞吐量，研究者已经提出了许多路由算 法。按照对ME0层卫星利用程度的不同，该些算法大致可W分为两大类；一类是借助ME0层 卫星来实现网络的管理，另一类则是利用ME0层卫星实现远距离业务的传输。具体来说，第 一类路由算法中，ME0层主要用来周期性地收集LEO层星间链路的状态信息，如链路中断、 传播时延、排队时延等，它利用此类信息为LEO层卫星建立路由信息表并分发给LEO层卫 星，而LEO层卫星则负责业务的传输；第二类路由算法的核屯、在于利用ME0层卫星传输远距 离的业务，LEO层则用来传输近距离的业务，从而使得ME0层卫星与LEO层卫星得到不同程 度地利用，缓解了LEO层的拥塞。总而言之，上述两类算法分别利用了ME0层的不同功能来 做路由决策，从而使得多层卫星网络的吞吐量提高。
[0004] 但是，上述提出的两类算法都没有很好地融合多层卫星网络中ME0层兼具网络管 理与远距离业务传输的特性。具体来说，第一类算法没有充分利用ME0层传输业务的能力， 因此当LEO层负载较重并出现丢包时，ME0层卫星仍未被用来缓解LEO层的传输压力，从而 不能达到网络的负载均衡；第二类算法则将业务按照源到目的节点的距离长短分类，而不 是基于业务的具体服务质量怕〇巧需求（例如时延、吞吐量等）来区分，该在一定程度上限 制了网络对不同QoS业务的保障能力，另一方面，此类算法没有利用ME0层卫星便于网络管 理的优点，网络交互信息的开销较大，占用了一部分传输资源，限制了网络的吞吐量。此外， 上述两类算法都没有根据网络的负载变化情况进行路由决策，来动态地调整业务在ME0层 和LEO层的分流比例，并将业务的QoS需求与网络的结构特性相匹配，使得不同类型的业务 能通过最合适的层来传输，从而在实现负载均衡的基础上进一步保障不同业务的QoS。
【发明内容】
[0005] 本发明的目的在于提供一种基于负载感知的多层卫星网络路由方法，旨在解决现 有的卫星通信中存在的LEO/MEO多层卫星网络的吞吐量较低，不能达到网络的负载均衡， 网络交互信息的开销较大的问题。
[0006] 本发明是该样实现的，一种基于负载感知的多层卫星网络路由方法，所述基于负 载感知的多层卫星网络路由方法利用多层卫星网络层次化构架来对网络的负载进行周期 性地感知，并根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网 络的负载均衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时 最先分流对时延要求最低的业务从ME0层传输，而时延敏感业务始终从LEO层传输。
[0007] 进一步，所述基于负载感知的多层卫星网络路由方法具体包括W下步骤：
[0008] 步骤一，每个ME0节点Mu依据星上提前存储的网络拓扑r(t)构建W自己为簇首 节点的分簇Cu(t);
[0009] 步骤二每个簇内进行信息交换，簇首MEO节点Mu收集Cu(t)簇内LEO节点的链路 状态信息Aui(t)与Qy(t)，并依据它们构建相应的路由子图RGMu(t);
[0010] 步骤S，构建全局路由图RG(t) = {Vt，Et，w(i，j)};
[0011] 步骤四，每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子Xu(t)， [001引步骤五，每个ME0节点Mu根据全局路由图RG(t)使用Dijkstra算法 或Bellman-Ford算法得到Cu(t)簇内每个节点的最短路径，并据此构建路由表 巧打(0、巧r,,,々），对于簇首Mu节点，最终的路由表巧,=麻,,(。，而对于簇内LEO节点 Lui，若X。似=0,则最终路由表片7,二乃若X。似>0,则该部分业务的下一跳节 点为簇首节点Mu;
[001引步骤六，当前LEO节点Lui根据路由表RTui(t)为不同类型的业务计算最终的分流 比例x^(t)、x^(t)、Xue(t)并选择相应路由，当前ME0节点Mu则根据路由表RTu(t)将数 据传输至下一跳节点。
[0014] 步骤走，在经过一个拓扑更新周期AT的时间后，网络中每个节点开始重新执行 上述步骤一~步骤六，保证周期性地更新链路代价信息，进而动态调整路由选择，达到网络 的负载均衡并保障不同业务的QoS。
[0015] 进一步，所述步骤一具体包括：
[0016] 第一步，基于卫星运动轨迹的可预测性和周期性，所有ME0节点可提前计算并在 星上存储网络在第t个拓扑更新周期内的整体拓扑结构r(t);
[0017] 第二步，当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 r(t)；
[0018] 第S步，每个MEO节点Mu依据r(t)构建分簇Cu(t)，其中簇首为Mu节点，Cu(t)簇 内节点由一系列符合W下条件的LEO节点Lui组成，即Lui节点在Mu节点覆盖范围内且节点 Mu是距其最近的邻居ME0节点，分簇元素集合表示为：
[0019] Cu(t) = (Mu, Lui，Lu2,…，Lu|cu|}，
[0020] 其中|cj为Cu(t)簇内LEO节点的数目，Lw节点表示Cu(t)簇内第i个LEO节点。
[0021] 进一步，所述步骤二具体包括：
[002引第一步，每个簇首MEO节点Mu向Cu(t)簇内LEO节点Lui广播包含本节点的IP、地 理位置信息W及包序号的肥LL0包；
[002引第二步，簇内的LEO节点Lu浪收来自Cu(t)簇首Mu节点的肥LL0包并获取该簇首 节点的位置信息，若发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点； [0024] 第S步，每个LEO节点Lu在拓扑更新周期内监测外部新到达的业务流Aui(t)W 及平均排队时延Qu(t)信息，并向Cu(t)簇首MEO节点Mu发送包含该信息的数据包；
[002引第四步，Mu节点收集Cu(t)簇内所有LEO节点Lui的数据包并依据Qu(t)构建路由 子图RGMu(t) = {V(Mu)，E(Mu)，w(iJ)}。
[0026] 进一步，所述第四步具体实现包括：
[0027] 步骤一，Mu节点获取当前拓扑更新周期内的完整拓扑r(t)，WMu节点为根节点获 取它的所有邻居节点集合V(Mu)和连接Mu节点及其邻居节点的链路集合E(Mu);
[002引步骤二，计算链路集合E(Mu)中所有链路（i,j)的代价w(i,如=p(i,j)+q(i,如， 其中P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)根据网络的拓扑r(t) 提前算出，而q(i，j) =Qij(t);
[0029] 步骤S，合成最终的路由子图RGMu(t) = {V(Mu)，E(Mu)，w(i，j)}。
[0030] 进一步，所述步骤立具体包括：
[003U第一步，初始化阶段，每个ME0节点Mu向所有邻居ME0节点Mk广播包含RGMU(t)和 (Ut)信息的数据包，并接收来自Mk节点的包含RG"^(t)和Qku(t)信息的数据包；
[003引第二步，当ME0节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包， 若有，则删除此包，并将Mu加入到包序列号n所对应的集合n。中，若没有，则保存该数据 包，并发送给集合n。外的邻居ME0节点；
[003引第立步，当每个ME0节点获取到所有链路（i，如GEt的代价w(i，如后，交换过程 终止，并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。
[0034] 进一步，所述步骤四具体包括：
[0035] 第一步，计算簇内LEO节点新到达业务的总量Au(t)=EAui(t);
[0036] 第二步，定义LEO/MEO多层网络特征参 数（K、并执行如下计算：
[0039] 第S步，计算簇内节点的平均拥塞程度?u(t):
[0040]
[0041] 其中A"(t)、Cm、屯分别为实际到达ME0层链路的业务平均到达率，ME0层星间链 路的传输容量W及传播时延，A^t)、片、屯分别为实际到达LEO层链路的业务平均到达率， ME0层星间链路的传输容量化及传播时延，注意上述A"(t)、A,(t)包括外部用户新到达业 务和为邻节点中继的业务，并可W用下式计算：
[0044] 第四步，求解下述等式方程即可得到得到最优的分流因子Xu(t):
[0045]
[0046] 进一步，所述步骤六中将业务按照对时延的要求分成=类；A类业务为时延敏感 业务，对时延的要求最高，优先级最高，典型的业务代表为实时语音业务；B类业务为时延 容忍业务，对时延有一定的要求，优先级次之，典型的业务代表为视频流传输业务；C类业 务为尽力保障业务，对时延无要求，优先级最低，典型的代表为互联网中的文件传输、网页 浏览业务。
[0047] 本发明与现有技术相比，具有如下优点：
[0048] 1)本发明充分利用了LEO/MEO多层卫星网络的层次化架构来周期性地收集网络 的负载业务流量信息，并据此进行路由决策，使得LEO层卫星能够根据网络的负载变化情 况动态地调整其分流因子，将最优比例量的业务从ME0层传输，从而极大程度地缓解了由 于业务分布不均匀所导致的局部拥塞，达到整个网络的负载均衡，使网络的吞吐量提高。
[0049] 2)本发明对业务按照对时延需求进行分类，并将不同类型业务的服务质量需求与 LE0/ME0网络结构特性相匹配，使得不同类型的业务都能W最合适的路径传输，并在网络达 到拥塞时进行差异化分流，即先分流C类尽力保障业务，最后分流A类时延敏感业务，在达 到负载均衡的条件下尽力保障了不同业务的QoS需求。
[0050] 3)本发明利用ME0节点周期性地收集LEO节点的链路状态信息，避免了LEO层内 卫星由于计算路由带来的频繁信息交互，降低了系统的开销，减小了信息交换的时延，使得 网络能够更迅速地从节点故障或链路中断中恢复过来，提高了网络的自适应性和鲁椿性。
【附图说明】
[0051] 图1是本发明实施例提供的适用的LE0/ME0多层卫星网络场景示意图；
[0化2] 图2是本发明实施例提供的基于负载感知的多层卫星网络路由方法流程图。
【具体实施方式】
[0053] 为了使本发明的目的、技术方案及优点更加清楚明白，W下结合实施例，对本发明 进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用W解释本发明，并不用于 限定本发明。
[0化4] 本发明通过利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并 根据收集的负载信息来动态地调整业务在ME0层和LEO层的分流比例，从而达到网络的负 载均衡，此外，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最 先分流对时延要求最低的业务从ME0层传输，而时延敏感业务始终从LEO层传输，保障了不 同类型业务的QoS。
[0055] 下面结合附图对本发明的应用原理作详细的描述。
[0化6] 参照图1，本发明使用的LEO/MEO多层卫星网络由LEO层和LEO层构成，LEO层网 络包括所有的LEO卫星节点，它包括町个轨道，每个轨道有S 卫星；ME0层网络包括所有 的ME0节点，它包括P"个轨道，每个轨道有S"颗卫星，此外，LEO层和ME0层都能够提供全 球覆盖，且ME0层卫星轨道高度比LEO层卫星轨道高，相应地，ME0层卫星数目比LEO层卫 星数目少。
[0化7] 参照图2,本发明的具体实现步骤如下：
[0化引步骤1，每个ME0节点Mu依据星上提前存储的网络拓扑r(t)构建W自己为簇首 节点的分簇Cu(t);
[0化9] (la)基于卫星运动轨迹的可预测性和周期性，所有ME0节点可提前计算并在星上 存储网络在第t个拓扑更新周期内的整体拓扑结构r(t)，该计算过程可通过卫星仿真软 件STK模拟实现；
[0060] (lb)当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 r(t)；
[0061] (Ic)每个MEO节点Mu依据r(t)构建分簇Cu(t)，其中簇首为Mu节点，Cu(t)簇内 节点由一系列符合W下条件的LEO节点Lu組成，即Lui节点在Mu节点覆盖范围内且节点Mu 是距其最近的邻居MEO节点，该分簇元素集合可表示为：
[0062] Cu(t) = (Mu，Lui，Lu2,…，Lu|cu|}，
[006引其中ICul为Cu(t)簇内LEO节点的数目，Lui节点表示Cu(t)簇内第i个LEO节点。 [0064] 步骤2,每个簇内进行信息交换，簇首ME0节点Mu收集Cu(t)簇内LEO节点的链路 状态信息Aui(t)与Qy(t)，并依据它们构建相应的路由子图RGMu(t);
[00化](2a)每个簇首ME0节点Mu向Cu(t)簇内LEO节点Lui广播包含本节点的IP、地理 位置信息W及包序号的肥LL0包；
[0066] (2b)簇内的LEO节点Lui接收来自Cu(t)簇首Mu节点的肥LL0包并获取该簇首节 点的位置信息，若发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点；
[0067] (2c)每个LEO节点Lu在拓扑更新周期内监测外部新到达的业务流Aui(t)W及 平均排队时延Qu(t)信息，并向Cu(t)簇首MEO节点Mu发送包含该信息的数据包；
[0068] (2d)Mu节点收集Cu(t)簇内所有LEO节点L山的数据包并依据Qu(t)构建路由子 图RGMu(t) = {￥曲。)，6曲。)，*(1^')}，步骤具体实现包括：
[0069] (2dl)Mu节点获取当前拓扑更新周期内的完整拓扑r(t)，WMu节点为根节点获取 它的所有邻居节点集合V(Mu)和连接Mu节点及其邻居节点的链路集合E(Mu);
[0070] (2d2)计算链路集合E(Mu)中所有链路（i，j)的代价w(i，j) =p(i，j)+q(i，j)，其 中P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)可根据网络的拓扑r(t) 提前算出，而q(i，j) =Qij(t);
[0071] (2d3)合成最终的路由子图RGMu(t) = {V(Mu)，E(Mu)，w(i，j)}。
[007引步骤3,构建全局路由图RG(t) = {Vt，Et，w(i，j)};
[007引 （3a)初始化阶段，每个MEO节点Mu向所有邻居MEO节点Mk广播包含RGMu(t)和 (Ut)信息的数据包，并接收来自Mk节点的包含RG"^(t)和Qku(t)信息的数据包；
[0074] (3b)当ME0节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包，若 有，则删除此包，并将Mu加入到包序列号n所对应的集合n。中，若没有，则保存该数据包， 并将其发送给集合n。外的邻居MEO节点；
[007引 （3c)当每个MEO节点获取到所有链路（ij)GEt的代价w(ij)后，交换过程终 止，并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。
[0076]步骤4,每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子Xu(t)，
[0077] (4a)计算簇内LEO节点新到达业务的总量Au(t) =E(t);
[007引 （4b)定义LEO/MEO多层网络特征参数（K、并执行如下计算：
[0081] (4c)计算簇内节点的平均拥塞程度?u(t):
[0082]
[008引其中AM(t)、Cm、屯分别为实际到达ME0层链路的业务平均到达率，ME0层星间链 路的传输容量W及传播时延，A^t)、片、屯分别为实际到达LEO层链路的业务平均到达率， ME0层星间链路的传输容量化及传播时延，注意上述A"(t)、A,(t)包括外部用户新到达业 务和为邻节点中继的业务，并可W用下式计算：
[0086] (4d)求解下述等式方程即可得到得到最优的分流因子Xu(t):
[0087]
[00能]步骤5,每个ME0节点Mu根据全局路由图RG(t)使用DUkstra算法 或Bellman-Ford算法得到Cu(t)簇内每个节点的最短路径，并据此构建路由表 巧打(〇、，对于簇首Mu节点，最终的路由表= ，而对于簇内LEO节点 Lui，若X。似=0,则最终路由表= 如)，若X。似>0,则该部分业务的下一跳节 点为簇首节点Mu。
[0089] 步骤6,当前LEO节点Lui根据路由表RTui(t)为不同类型的业务计算最终的分流 比例Xw(t)、x^(t)、Xue(t)并选择相应路由，当前ME0节点Mu则根据路由表RTu(t)将数 据传输至下一跳节点。
[0090] 参照表1，将业务按照对时延的要求分成=类；A类业务为时延敏感业务，对时延 的要 求最高，优先级最高，典型的业务代表为实时语音业务；B类业务为时延容忍业务，对 时延有一定的要求，优先级次之，典型的业务代表为视频流传输业务；c类业务为尽力保障 业务，对时延无要求，优先级最低，典型的代表为互联网中的文件传输、网页浏览等业务；
[0091]表 1
[0092]
[0094] 当分流因子Xu(t)>0时，C类业务被最先分流，转从MEO层传输，若C类业务 的分流量小于需要分流至MEO层的业务量时，一部分B类业务将被分流，而为了保证A类 业务的时延要求，它始终不会被分流，其具体过程为：当Xu(t)Au(t) <Aue(t)时，仅有 X(t)AuWAcW比例的C类业务被分流至MEO层传输，其它业务保持原有路由不变；当 Xu(t)Au(t)> ^uc(t)且Xu(t)Au(t)< ^uB(t) +入uc(t)时，C类业务被全部分流至ME0 层传输，（XU(t)入U(t) -AUC(t)) /AW(t)比例的B类业务也被分流，而A类业务保持原有路 由不变；当Xu(t)Au(t)>A^(t)+Aue(t)时，所有的B类和C类业务被分流至ME0层传 输，而A类业务依然保持原有路由不变。
[0095] 步骤7,为了能适应网络负载的实时动态变化，在经过一个拓扑更新周期AT的时 间后，网络中每个节点开始重新执行上述步骤1~步骤6,W保证周期性地更新链路代价信 息，进而动态调整路由选择，达到网络的负载均衡并保障不同业务的QoS。
[0096] W上所述仅为本发明的较佳实施例而已，并不用W限制本发明，凡在本发明的精 神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种基于负载感知的多层卫星网络路由方法，其特征在于，所述基于负载感知的多 层卫星网络路由方法利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并 根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网络的负载均 衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最先分流对 时延要求最低的业务，从MEO层传输，而时延敏感业务始终从LEO层传输。2. 如权利要求1所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述基 于负载感知的多层卫星网络路由方法具体包括以下步骤： 步骤一，每个MEO节点Mu依据星上提前存储的网络拓扑Γ (t)构建为簇首节点的分簇 Cu⑴； 步骤二，每个簇内进行信息交换，簇首MEO节点Mu收集Cu(t)簇内LEO节点的链路状态 信息Xui (t)与QijU),并依据构建相应的路由子图Wi/,. W ; 步骤三，构建全局路由图RG(t) = {Vt，Et，w(i，j)}; 步骤四，每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子x u(t); 步骤五，每个MEO节点Mu根据全局路由图RG(t)使用Dijkstra算法或Bellman-Ford 算法得到Cu (t)簇内每个节点的最短路径，并构建路由表G,,⑴、，对于簇首]^节 点，最终的路由表/?7：(/)=斤"(/),而对于簇内LEO节点Lui，若xu(t) = 0,则最终路由表 /?7；.(〇 =介,,,.(/)，若xu(t) >0,则部分业务的下一跳节点为簇首节点Mu; 步骤六，当前LEO节点Lui根据路由表RT ui (t)为不同类型的业务计算最终的分流比例 X μ⑴、Xub⑴、Xuc⑴并选择相应路由，当前MEO节点Mu则根据路由表RT u⑴将数据传 输至下一跳节点； 步骤七，在经过一个拓扑更新周期△ T的时间后，网络中每个节点开始重新执行上述 步骤一~步骤六，保证周期性地更新链路代价信息，进而动态调整路由选择，达到网络的负 载均衡并保障不同业务的QoS。3. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤一具体包括： 第一步，基于卫星运动轨迹的可预测性和周期性，所有MEO节点提前计算并在星上存 储网络在第t个拓扑更新周期内的整体拓扑结构Γ (t); 第二步，当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 Γ⑴； 第三步，每个MEO节点Mu依据Γ (t)构建分簇Cu(t)，其中簇首为Mu节点，C u(t)簇内 节点由一系列符合以下条件的LEO节点Lui组成，即L ui节点在M u节点覆盖范围内且节点M u是最近的邻居MEO节点，分簇元素集合表示为： ('"(〇，乂丨，42，···，^}， 其中|CU|为Cu(t)簇内LEO节点的数目，1^节点表示Cu(t)簇内第i个LEO节点。4. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤二具体包括： 第一步，每个簇首MEO节点Mu向Cu (t)簇内LEO节点Lui广播包含本节点的IP、地理位 置信息以及包序号的HELLO包； 第二步，簇内的LEO节点1^接收来自Cu(t)簇首Mu节点的HELLO包并获取簇首节点的 位置信息，发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点； 第三步，每个LEO节点1^在拓扑更新周期内监测外部新到达的业务流λ ui(t)以及平 均排队时延Qij (t)信息，并向Cu(t)簇首MEO节点Mu发送包含信息的数据包； 第四步，Mu节点收集Cu(t)簇内所有LEO节点1^的数据包并依据QJt)构建路由子图 (，）= !K(MJ，￡(M")，u，(/，./)|。5. 如权利要求4所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述第 四步具体实现包括： 步骤一，Mu节点获取当前拓扑更新周期内的完整拓扑Γ (t)，以Mu节点为根节点获取它 的所有邻居节点集合V (Mu)和连接Mu节点及邻居节点的链路集合E (M u); 步骤二，计算链路集合E(Mu)中所有链路（i，j)的代价W(i，j)=p(i，j)+q(i，j)，其中 P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)根据网络的拓扑Γ⑴提前 算出，而 q(i, j) = Qij(t); 步骤三，合成最终的路由子图奶/"⑴=), [(Ο1仏./)丨。6. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤三具体包括： 第一步，初始化阶段，每个MEO节点Mu向所有邻居MEO节点M k广播包含^^t/.,⑴和 Quk⑴信息的数据包，并接收来自Mk节点的包含(0和Qku⑴信息的数据包； 第二步，当MEO节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包，若 有，则删除此包，并将Mu加入到包序列号η所对应的集合Π "中，若没有，则保存该数据包， 并发送给集合11"外的邻居MEO节点； 第三步，当每个MEO节点获取到所有链路（i，j) e Et的代价w(i，j)后，交换过程终止， 并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。7. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤四具体包括： 第一步，计算簇内LEO节点新到达业务的总量Au(t) = Σ Aui(t); 第二步，定义LE0/ME0多层网络特征参数ΦΜ、（K，并执行如下计算：第三步，计算簇内节点的平均拥塞程度?u(t):其中λ M(t)、CM、dM分别为实际到达MEO层链路的业务平均到达率，MEO层星间链路的 传输容量以及传播时延，λ Jt)、Q、4分别为实际到达LEO层链路的业务平均到达率，MEO 层星间链路的传输容量以及传播时延，λΜα)、λ Jt)包括外部用户新到达业务和为邻节点 中继的业务，并用下式计算：第四步，求解下述等式方程即得到最优的分流因子xu(t):8. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤六中将业务按照对时延的要求分成三类：时延敏感业务；时延容忍业务；尽力保障业务。9. 一种如权利要求1-8任意一项所述基于负载感知的多层卫星网络路由方法在LEO/ MEO两层卫星网络的应用。
【专利摘要】本发明公开了一种基于负载感知的多层卫星网络路由方法，利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网络的负载均衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最先分流对时延要求最低的业务，使其从MEO层传输，而时延敏感业务始终从LEO层传输。本发明缓解了由于业务分布不均匀所导致的局部拥塞，使网络的吞吐量提高，避免了LEO层内卫星由于计算路由带来的频繁信息交互，降低了系统的开销，减小了信息交换的时延，使得网络能够更迅速地从节点故障或链路中断中恢复过来，提高了网络的自适应性和鲁棒性。
【IPC分类】H04W40/04, H04W84/06, H04W28/08
【公开号】CN104902515
【申请号】CN201510309913
【发明人】盛敏, 汪宇, 王玺钧, 张琰, 李建东, 史琰, 刘润滋, 周笛
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年6月8日
【技术领域】
[0001] 本发明属于卫星通信技术领域，尤其设及一种基于负载感知的多层卫星网络路由 方法。
【背景技术】
[0002] 多层卫星网络（MLSN)作为下一代卫星通信构架的杰出代表，在近年来得到了广 泛的关注和研究。与传统的单层卫星网络不同，多层卫星网络由低轨道卫星（LEO)、中轨道 卫星（ME0)W及地球同步轨道卫星（GE0)等多种卫星星座融合而成，因此，它具有覆盖范围 广、传送时延短、网络容量大等优点。此外，该种层次化的网络构架便于网络的高效管理，从 而使得信息交互的开销更小，网络的鲁椿性更高，能够快速地从节点故障、链路中断等情况 中恢复过来。为了能够有效地在多层卫星网络中传输业务，路由策略是必不可少的。然而， 由于卫星周期性地绕地球转动，导致卫星网络的拓扑快速变化，链路中断和切换频繁发生， 该对路由协议的有效性提出了巨大挑战。此外，受气候、经济、地形等因素影响，地球表面人 口分布极度不均匀，导致业务的需求呈现较大的差异性，从而出现某些卫星已经非常拥塞 并开始大量丢包，而一部分卫星并未得到充分利用的情况。因此，有必要提出一种有效的路 由协议来捕捉并利用网络的拓扑变化，并实现网络的负载均衡，提高整体的吞吐量性能。
[0003] 目前，为了提高LE0/ME0多层卫星网络的吞吐量，研究者已经提出了许多路由算 法。按照对ME0层卫星利用程度的不同，该些算法大致可W分为两大类；一类是借助ME0层 卫星来实现网络的管理，另一类则是利用ME0层卫星实现远距离业务的传输。具体来说，第 一类路由算法中，ME0层主要用来周期性地收集LEO层星间链路的状态信息，如链路中断、 传播时延、排队时延等，它利用此类信息为LEO层卫星建立路由信息表并分发给LEO层卫 星，而LEO层卫星则负责业务的传输；第二类路由算法的核屯、在于利用ME0层卫星传输远距 离的业务，LEO层则用来传输近距离的业务，从而使得ME0层卫星与LEO层卫星得到不同程 度地利用，缓解了LEO层的拥塞。总而言之，上述两类算法分别利用了ME0层的不同功能来 做路由决策，从而使得多层卫星网络的吞吐量提高。
[0004] 但是，上述提出的两类算法都没有很好地融合多层卫星网络中ME0层兼具网络管 理与远距离业务传输的特性。具体来说，第一类算法没有充分利用ME0层传输业务的能力， 因此当LEO层负载较重并出现丢包时，ME0层卫星仍未被用来缓解LEO层的传输压力，从而 不能达到网络的负载均衡；第二类算法则将业务按照源到目的节点的距离长短分类，而不 是基于业务的具体服务质量怕〇巧需求（例如时延、吞吐量等）来区分，该在一定程度上限 制了网络对不同QoS业务的保障能力，另一方面，此类算法没有利用ME0层卫星便于网络管 理的优点，网络交互信息的开销较大，占用了一部分传输资源，限制了网络的吞吐量。此外， 上述两类算法都没有根据网络的负载变化情况进行路由决策，来动态地调整业务在ME0层 和LEO层的分流比例，并将业务的QoS需求与网络的结构特性相匹配，使得不同类型的业务 能通过最合适的层来传输，从而在实现负载均衡的基础上进一步保障不同业务的QoS。
【发明内容】
[0005] 本发明的目的在于提供一种基于负载感知的多层卫星网络路由方法，旨在解决现 有的卫星通信中存在的LEO/MEO多层卫星网络的吞吐量较低，不能达到网络的负载均衡， 网络交互信息的开销较大的问题。
[0006] 本发明是该样实现的，一种基于负载感知的多层卫星网络路由方法，所述基于负 载感知的多层卫星网络路由方法利用多层卫星网络层次化构架来对网络的负载进行周期 性地感知，并根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网 络的负载均衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时 最先分流对时延要求最低的业务从ME0层传输，而时延敏感业务始终从LEO层传输。
[0007] 进一步，所述基于负载感知的多层卫星网络路由方法具体包括W下步骤：
[0008] 步骤一，每个ME0节点Mu依据星上提前存储的网络拓扑r(t)构建W自己为簇首 节点的分簇Cu(t);
[0009] 步骤二每个簇内进行信息交换，簇首MEO节点Mu收集Cu(t)簇内LEO节点的链路 状态信息Aui(t)与Qy(t)，并依据它们构建相应的路由子图RGMu(t);
[0010] 步骤S，构建全局路由图RG(t) = {Vt，Et，w(i，j)};
[0011] 步骤四，每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子Xu(t)， [001引步骤五，每个ME0节点Mu根据全局路由图RG(t)使用Dijkstra算法 或Bellman-Ford算法得到Cu(t)簇内每个节点的最短路径，并据此构建路由表 巧打(0、巧r,,,々），对于簇首Mu节点，最终的路由表巧,=麻,,(。，而对于簇内LEO节点 Lui，若X。似=0,则最终路由表片7,二乃若X。似>0,则该部分业务的下一跳节 点为簇首节点Mu;
[001引步骤六，当前LEO节点Lui根据路由表RTui(t)为不同类型的业务计算最终的分流 比例x^(t)、x^(t)、Xue(t)并选择相应路由，当前ME0节点Mu则根据路由表RTu(t)将数 据传输至下一跳节点。
[0014] 步骤走，在经过一个拓扑更新周期AT的时间后，网络中每个节点开始重新执行 上述步骤一~步骤六，保证周期性地更新链路代价信息，进而动态调整路由选择，达到网络 的负载均衡并保障不同业务的QoS。
[0015] 进一步，所述步骤一具体包括：
[0016] 第一步，基于卫星运动轨迹的可预测性和周期性，所有ME0节点可提前计算并在 星上存储网络在第t个拓扑更新周期内的整体拓扑结构r(t);
[0017] 第二步，当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 r(t)；
[0018] 第S步，每个MEO节点Mu依据r(t)构建分簇Cu(t)，其中簇首为Mu节点，Cu(t)簇 内节点由一系列符合W下条件的LEO节点Lui组成，即Lui节点在Mu节点覆盖范围内且节点 Mu是距其最近的邻居ME0节点，分簇元素集合表示为：
[0019] Cu(t) = (Mu, Lui，Lu2,…，Lu|cu|}，
[0020] 其中|cj为Cu(t)簇内LEO节点的数目，Lw节点表示Cu(t)簇内第i个LEO节点。
[0021] 进一步，所述步骤二具体包括：
[002引第一步，每个簇首MEO节点Mu向Cu(t)簇内LEO节点Lui广播包含本节点的IP、地 理位置信息W及包序号的肥LL0包；
[002引第二步，簇内的LEO节点Lu浪收来自Cu(t)簇首Mu节点的肥LL0包并获取该簇首 节点的位置信息，若发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点； [0024] 第S步，每个LEO节点Lu在拓扑更新周期内监测外部新到达的业务流Aui(t)W 及平均排队时延Qu(t)信息，并向Cu(t)簇首MEO节点Mu发送包含该信息的数据包；
[002引第四步，Mu节点收集Cu(t)簇内所有LEO节点Lui的数据包并依据Qu(t)构建路由 子图RGMu(t) = {V(Mu)，E(Mu)，w(iJ)}。
[0026] 进一步，所述第四步具体实现包括：
[0027] 步骤一，Mu节点获取当前拓扑更新周期内的完整拓扑r(t)，WMu节点为根节点获 取它的所有邻居节点集合V(Mu)和连接Mu节点及其邻居节点的链路集合E(Mu);
[002引步骤二，计算链路集合E(Mu)中所有链路（i,j)的代价w(i,如=p(i,j)+q(i,如， 其中P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)根据网络的拓扑r(t) 提前算出，而q(i，j) =Qij(t);
[0029] 步骤S，合成最终的路由子图RGMu(t) = {V(Mu)，E(Mu)，w(i，j)}。
[0030] 进一步，所述步骤立具体包括：
[003U第一步，初始化阶段，每个ME0节点Mu向所有邻居ME0节点Mk广播包含RGMU(t)和 (Ut)信息的数据包，并接收来自Mk节点的包含RG"^(t)和Qku(t)信息的数据包；
[003引第二步，当ME0节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包， 若有，则删除此包，并将Mu加入到包序列号n所对应的集合n。中，若没有，则保存该数据 包，并发送给集合n。外的邻居ME0节点；
[003引第立步，当每个ME0节点获取到所有链路（i，如GEt的代价w(i，如后，交换过程 终止，并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。
[0034] 进一步，所述步骤四具体包括：
[0035] 第一步，计算簇内LEO节点新到达业务的总量Au(t)=EAui(t);
[0036] 第二步，定义LEO/MEO多层网络特征参 数（K、并执行如下计算：
[0039] 第S步，计算簇内节点的平均拥塞程度?u(t):
[0040]
[0041] 其中A"(t)、Cm、屯分别为实际到达ME0层链路的业务平均到达率，ME0层星间链 路的传输容量W及传播时延，A^t)、片、屯分别为实际到达LEO层链路的业务平均到达率， ME0层星间链路的传输容量化及传播时延，注意上述A"(t)、A,(t)包括外部用户新到达业 务和为邻节点中继的业务，并可W用下式计算：
[0044] 第四步，求解下述等式方程即可得到得到最优的分流因子Xu(t):
[0045]
[0046] 进一步，所述步骤六中将业务按照对时延的要求分成=类；A类业务为时延敏感 业务，对时延的要求最高，优先级最高，典型的业务代表为实时语音业务；B类业务为时延 容忍业务，对时延有一定的要求，优先级次之，典型的业务代表为视频流传输业务；C类业 务为尽力保障业务，对时延无要求，优先级最低，典型的代表为互联网中的文件传输、网页 浏览业务。
[0047] 本发明与现有技术相比，具有如下优点：
[0048] 1)本发明充分利用了LEO/MEO多层卫星网络的层次化架构来周期性地收集网络 的负载业务流量信息，并据此进行路由决策，使得LEO层卫星能够根据网络的负载变化情 况动态地调整其分流因子，将最优比例量的业务从ME0层传输，从而极大程度地缓解了由 于业务分布不均匀所导致的局部拥塞，达到整个网络的负载均衡，使网络的吞吐量提高。
[0049] 2)本发明对业务按照对时延需求进行分类，并将不同类型业务的服务质量需求与 LE0/ME0网络结构特性相匹配，使得不同类型的业务都能W最合适的路径传输，并在网络达 到拥塞时进行差异化分流，即先分流C类尽力保障业务，最后分流A类时延敏感业务，在达 到负载均衡的条件下尽力保障了不同业务的QoS需求。
[0050] 3)本发明利用ME0节点周期性地收集LEO节点的链路状态信息，避免了LEO层内 卫星由于计算路由带来的频繁信息交互，降低了系统的开销，减小了信息交换的时延，使得 网络能够更迅速地从节点故障或链路中断中恢复过来，提高了网络的自适应性和鲁椿性。
【附图说明】
[0051] 图1是本发明实施例提供的适用的LE0/ME0多层卫星网络场景示意图；
[0化2] 图2是本发明实施例提供的基于负载感知的多层卫星网络路由方法流程图。
【具体实施方式】
[0053] 为了使本发明的目的、技术方案及优点更加清楚明白，W下结合实施例，对本发明 进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用W解释本发明，并不用于 限定本发明。
[0化4] 本发明通过利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并 根据收集的负载信息来动态地调整业务在ME0层和LEO层的分流比例，从而达到网络的负 载均衡，此外，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最 先分流对时延要求最低的业务从ME0层传输，而时延敏感业务始终从LEO层传输，保障了不 同类型业务的QoS。
[0055] 下面结合附图对本发明的应用原理作详细的描述。
[0化6] 参照图1，本发明使用的LEO/MEO多层卫星网络由LEO层和LEO层构成，LEO层网 络包括所有的LEO卫星节点，它包括町个轨道，每个轨道有S 卫星；ME0层网络包括所有 的ME0节点，它包括P"个轨道，每个轨道有S"颗卫星，此外，LEO层和ME0层都能够提供全 球覆盖，且ME0层卫星轨道高度比LEO层卫星轨道高，相应地，ME0层卫星数目比LEO层卫 星数目少。
[0化7] 参照图2,本发明的具体实现步骤如下：
[0化引步骤1，每个ME0节点Mu依据星上提前存储的网络拓扑r(t)构建W自己为簇首 节点的分簇Cu(t);
[0化9] (la)基于卫星运动轨迹的可预测性和周期性，所有ME0节点可提前计算并在星上 存储网络在第t个拓扑更新周期内的整体拓扑结构r(t)，该计算过程可通过卫星仿真软 件STK模拟实现；
[0060] (lb)当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 r(t)；
[0061] (Ic)每个MEO节点Mu依据r(t)构建分簇Cu(t)，其中簇首为Mu节点，Cu(t)簇内 节点由一系列符合W下条件的LEO节点Lu組成，即Lui节点在Mu节点覆盖范围内且节点Mu 是距其最近的邻居MEO节点，该分簇元素集合可表示为：
[0062] Cu(t) = (Mu，Lui，Lu2,…，Lu|cu|}，
[006引其中ICul为Cu(t)簇内LEO节点的数目，Lui节点表示Cu(t)簇内第i个LEO节点。 [0064] 步骤2,每个簇内进行信息交换，簇首ME0节点Mu收集Cu(t)簇内LEO节点的链路 状态信息Aui(t)与Qy(t)，并依据它们构建相应的路由子图RGMu(t);
[00化](2a)每个簇首ME0节点Mu向Cu(t)簇内LEO节点Lui广播包含本节点的IP、地理 位置信息W及包序号的肥LL0包；
[0066] (2b)簇内的LEO节点Lui接收来自Cu(t)簇首Mu节点的肥LL0包并获取该簇首节 点的位置信息，若发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点；
[0067] (2c)每个LEO节点Lu在拓扑更新周期内监测外部新到达的业务流Aui(t)W及 平均排队时延Qu(t)信息，并向Cu(t)簇首MEO节点Mu发送包含该信息的数据包；
[0068] (2d)Mu节点收集Cu(t)簇内所有LEO节点L山的数据包并依据Qu(t)构建路由子 图RGMu(t) = {￥曲。)，6曲。)，*(1^')}，步骤具体实现包括：
[0069] (2dl)Mu节点获取当前拓扑更新周期内的完整拓扑r(t)，WMu节点为根节点获取 它的所有邻居节点集合V(Mu)和连接Mu节点及其邻居节点的链路集合E(Mu);
[0070] (2d2)计算链路集合E(Mu)中所有链路（i，j)的代价w(i，j) =p(i，j)+q(i，j)，其 中P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)可根据网络的拓扑r(t) 提前算出，而q(i，j) =Qij(t);
[0071] (2d3)合成最终的路由子图RGMu(t) = {V(Mu)，E(Mu)，w(i，j)}。
[007引步骤3,构建全局路由图RG(t) = {Vt，Et，w(i，j)};
[007引 （3a)初始化阶段，每个MEO节点Mu向所有邻居MEO节点Mk广播包含RGMu(t)和 (Ut)信息的数据包，并接收来自Mk节点的包含RG"^(t)和Qku(t)信息的数据包；
[0074] (3b)当ME0节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包，若 有，则删除此包，并将Mu加入到包序列号n所对应的集合n。中，若没有，则保存该数据包， 并将其发送给集合n。外的邻居MEO节点；
[007引 （3c)当每个MEO节点获取到所有链路（ij)GEt的代价w(ij)后，交换过程终 止，并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。
[0076]步骤4,每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子Xu(t)，
[0077] (4a)计算簇内LEO节点新到达业务的总量Au(t) =E(t);
[007引 （4b)定义LEO/MEO多层网络特征参数（K、并执行如下计算：
[0081] (4c)计算簇内节点的平均拥塞程度?u(t):
[0082]
[008引其中AM(t)、Cm、屯分别为实际到达ME0层链路的业务平均到达率，ME0层星间链 路的传输容量W及传播时延，A^t)、片、屯分别为实际到达LEO层链路的业务平均到达率， ME0层星间链路的传输容量化及传播时延，注意上述A"(t)、A,(t)包括外部用户新到达业 务和为邻节点中继的业务，并可W用下式计算：
[0086] (4d)求解下述等式方程即可得到得到最优的分流因子Xu(t):
[0087]
[00能]步骤5,每个ME0节点Mu根据全局路由图RG(t)使用DUkstra算法 或Bellman-Ford算法得到Cu(t)簇内每个节点的最短路径，并据此构建路由表 巧打(〇、，对于簇首Mu节点，最终的路由表= ，而对于簇内LEO节点 Lui，若X。似=0,则最终路由表= 如)，若X。似>0,则该部分业务的下一跳节 点为簇首节点Mu。
[0089] 步骤6,当前LEO节点Lui根据路由表RTui(t)为不同类型的业务计算最终的分流 比例Xw(t)、x^(t)、Xue(t)并选择相应路由，当前ME0节点Mu则根据路由表RTu(t)将数 据传输至下一跳节点。
[0090] 参照表1，将业务按照对时延的要求分成=类；A类业务为时延敏感业务，对时延 的要 求最高，优先级最高，典型的业务代表为实时语音业务；B类业务为时延容忍业务，对 时延有一定的要求，优先级次之，典型的业务代表为视频流传输业务；c类业务为尽力保障 业务，对时延无要求，优先级最低，典型的代表为互联网中的文件传输、网页浏览等业务；
[0091]表 1
[0092]
[0094] 当分流因子Xu(t)>0时，C类业务被最先分流，转从MEO层传输，若C类业务 的分流量小于需要分流至MEO层的业务量时，一部分B类业务将被分流，而为了保证A类 业务的时延要求，它始终不会被分流，其具体过程为：当Xu(t)Au(t) <Aue(t)时，仅有 X(t)AuWAcW比例的C类业务被分流至MEO层传输，其它业务保持原有路由不变；当 Xu(t)Au(t)> ^uc(t)且Xu(t)Au(t)< ^uB(t) +入uc(t)时，C类业务被全部分流至ME0 层传输，（XU(t)入U(t) -AUC(t)) /AW(t)比例的B类业务也被分流，而A类业务保持原有路 由不变；当Xu(t)Au(t)>A^(t)+Aue(t)时，所有的B类和C类业务被分流至ME0层传 输，而A类业务依然保持原有路由不变。
[0095] 步骤7,为了能适应网络负载的实时动态变化，在经过一个拓扑更新周期AT的时 间后，网络中每个节点开始重新执行上述步骤1~步骤6,W保证周期性地更新链路代价信 息，进而动态调整路由选择，达到网络的负载均衡并保障不同业务的QoS。
[0096] W上所述仅为本发明的较佳实施例而已，并不用W限制本发明，凡在本发明的精 神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种基于负载感知的多层卫星网络路由方法，其特征在于，所述基于负载感知的多 层卫星网络路由方法利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并 根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网络的负载均 衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最先分流对 时延要求最低的业务，从MEO层传输，而时延敏感业务始终从LEO层传输。2. 如权利要求1所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述基 于负载感知的多层卫星网络路由方法具体包括以下步骤： 步骤一，每个MEO节点Mu依据星上提前存储的网络拓扑Γ (t)构建为簇首节点的分簇 Cu⑴； 步骤二，每个簇内进行信息交换，簇首MEO节点Mu收集Cu(t)簇内LEO节点的链路状态 信息Xui (t)与QijU),并依据构建相应的路由子图Wi/,. W ; 步骤三，构建全局路由图RG(t) = {Vt，Et，w(i，j)}; 步骤四，每个MEO节点Mu为Cu(t)簇内LEO节点Lui计算最优分流因子x u(t); 步骤五，每个MEO节点Mu根据全局路由图RG(t)使用Dijkstra算法或Bellman-Ford 算法得到Cu (t)簇内每个节点的最短路径，并构建路由表G,,⑴、，对于簇首]^节 点，最终的路由表/?7：(/)=斤"(/),而对于簇内LEO节点Lui，若xu(t) = 0,则最终路由表 /?7；.(〇 =介,,,.(/)，若xu(t) >0,则部分业务的下一跳节点为簇首节点Mu; 步骤六，当前LEO节点Lui根据路由表RT ui (t)为不同类型的业务计算最终的分流比例 X μ⑴、Xub⑴、Xuc⑴并选择相应路由，当前MEO节点Mu则根据路由表RT u⑴将数据传 输至下一跳节点； 步骤七，在经过一个拓扑更新周期△ T的时间后，网络中每个节点开始重新执行上述 步骤一~步骤六，保证周期性地更新链路代价信息，进而动态调整路由选择，达到网络的负 载均衡并保障不同业务的QoS。3. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤一具体包括： 第一步，基于卫星运动轨迹的可预测性和周期性，所有MEO节点提前计算并在星上存 储网络在第t个拓扑更新周期内的整体拓扑结构Γ (t); 第二步，当拓扑更新周期到达时，获取当前第t个拓扑更新周期的整体拓扑结构 Γ⑴； 第三步，每个MEO节点Mu依据Γ (t)构建分簇Cu(t)，其中簇首为Mu节点，C u(t)簇内 节点由一系列符合以下条件的LEO节点Lui组成，即L ui节点在M u节点覆盖范围内且节点M u是最近的邻居MEO节点，分簇元素集合表示为： ('"(〇，乂丨，42，···，^}， 其中|CU|为Cu(t)簇内LEO节点的数目，1^节点表示Cu(t)簇内第i个LEO节点。4. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤二具体包括： 第一步，每个簇首MEO节点Mu向Cu (t)簇内LEO节点Lui广播包含本节点的IP、地理位 置信息以及包序号的HELLO包； 第二步，簇内的LEO节点1^接收来自Cu(t)簇首Mu节点的HELLO包并获取簇首节点的 位置信息，发现簇首节点已改变，则将新的簇首节点Mu替换原先的簇首节点； 第三步，每个LEO节点1^在拓扑更新周期内监测外部新到达的业务流λ ui(t)以及平 均排队时延Qij (t)信息，并向Cu(t)簇首MEO节点Mu发送包含信息的数据包； 第四步，Mu节点收集Cu(t)簇内所有LEO节点1^的数据包并依据QJt)构建路由子图 (，）= !K(MJ，￡(M")，u，(/，./)|。5. 如权利要求4所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述第 四步具体实现包括： 步骤一，Mu节点获取当前拓扑更新周期内的完整拓扑Γ (t)，以Mu节点为根节点获取它 的所有邻居节点集合V (Mu)和连接Mu节点及邻居节点的链路集合E (M u); 步骤二，计算链路集合E(Mu)中所有链路（i，j)的代价W(i，j)=p(i，j)+q(i，j)，其中 P(i，j)为链路的传播时延，q(i，j)为链路的排队时延，P(i，j)根据网络的拓扑Γ⑴提前 算出，而 q(i, j) = Qij(t); 步骤三，合成最终的路由子图奶/"⑴=), [(Ο1仏./)丨。6. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤三具体包括： 第一步，初始化阶段，每个MEO节点Mu向所有邻居MEO节点M k广播包含^^t/.,⑴和 Quk⑴信息的数据包，并接收来自Mk节点的包含(0和Qku⑴信息的数据包； 第二步，当MEO节点Mu接收到来自Mk的数据包后，查看缓存中是否含有此数据包，若 有，则删除此包，并将Mu加入到包序列号η所对应的集合Π "中，若没有，则保存该数据包， 并发送给集合11"外的邻居MEO节点； 第三步，当每个MEO节点获取到所有链路（i，j) e Et的代价w(i，j)后，交换过程终止， 并构建最终的路由图RG(t) = {Vt，Et，w(i，j)}。7. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤四具体包括： 第一步，计算簇内LEO节点新到达业务的总量Au(t) = Σ Aui(t); 第二步，定义LE0/ME0多层网络特征参数ΦΜ、（K，并执行如下计算：第三步，计算簇内节点的平均拥塞程度?u(t):其中λ M(t)、CM、dM分别为实际到达MEO层链路的业务平均到达率，MEO层星间链路的 传输容量以及传播时延，λ Jt)、Q、4分别为实际到达LEO层链路的业务平均到达率，MEO 层星间链路的传输容量以及传播时延，λΜα)、λ Jt)包括外部用户新到达业务和为邻节点 中继的业务，并用下式计算：第四步，求解下述等式方程即得到最优的分流因子xu(t):8. 如权利要求2所述的基于负载感知的多层卫星网络路由方法，其特征在于，所述步 骤六中将业务按照对时延的要求分成三类：时延敏感业务；时延容忍业务；尽力保障业务。9. 一种如权利要求1-8任意一项所述基于负载感知的多层卫星网络路由方法在LEO/ MEO两层卫星网络的应用。
【专利摘要】本发明公开了一种基于负载感知的多层卫星网络路由方法，利用多层卫星网络层次化构架来对网络的负载进行周期性地感知，并根据收集的负载信息来动态地调整业务在MEO层和LEO层的分流比例，达到网络的负载均衡，通过将业务的QoS需求与网络的结构特性相匹配，在网络业务负载较重时最先分流对时延要求最低的业务，使其从MEO层传输，而时延敏感业务始终从LEO层传输。本发明缓解了由于业务分布不均匀所导致的局部拥塞，使网络的吞吐量提高，避免了LEO层内卫星由于计算路由带来的频繁信息交互，降低了系统的开销，减小了信息交换的时延，使得网络能够更迅速地从节点故障或链路中断中恢复过来，提高了网络的自适应性和鲁棒性。
【IPC分类】H04W40/04, H04W84/06, H04W28/08
【公开号】CN104902515
【申请号】CN201510309913
【发明人】盛敏, 汪宇, 王玺钧, 张琰, 李建东, 史琰, 刘润滋, 周笛
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年6月8日
最新回复(0)