一种基于栅格时延预测的卫星传输优化方法

摘要

本发明公开了一种基于栅格时延预测的卫星传输优化方法，包括：首先，根据卫星星座的参数，基于地理栅格划分网格优先级，确定用户与卫星的关联和切换方式；其次，并根据任务的卸载位置，建立任务的时延模型；然后，根据随机网络演算推导的栅格时延边界设定任务限制时延，作为卫星的栅格资源约束条件，并设定目标优化函数；之后，考虑多个任务卸载至同一节点竞争资源的情况，基于栅格时延保障研究公平的资源分配方案；最后，在确定的资源分配方式下，研究用户任务的卸载和调度决策，分析其在提高系统任务完成率方面的表现。

权利要求

1.一种卫星传输优化方法，其特征在于，包括：采用基于地理栅格和随机网络演算的卫星物联网业务建模分析方法，推导出栅格时延边界，基于所述栅格时延边界设定栅格时延限制值，作为栅格时延保障；

基于栅格时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题P1；

将问题P1解耦为基于栅格时延保障的公平资源分配子问题和任务卸载与调度决策子问题；

采用对偶上升法对公平通信与计算资源分配子问题进行求解，得到公平的通信资源分配和计算资源的分配；

基于所述通信资源分配和计算资源分配，采用深度Q网络对任务卸载与调度决策子问题进行求解，得到用户当前任务的卸载决策和调度决策；

其中，基于栅格时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题P1，包括：其中，w为l个时隙内完成并返回结果的用户任务总数；当栅格i范围内的用户m的任务k在基于SNC推导而设置的限定时延 内完成并返回结果，即 时， 否则为

0； 为第l个时隙在本地处理的任务的集合， 表示任务在本地处理； 为第l个时隙用户任务卸载的集合，表示用户m的任务卸载至卫星n处理； 为第l个时隙用户任务的调度集合， 表示从卫星的传输或处理队列中调度用户m的任务，否则不调度任务；Cl＝{C1,l,C2,l,...,CN,l}, 为第l个时隙卫星给各用户分配的通信资源；Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用户分配的计算资源； 和 分别为第l个时隙卫星n可分配的通信资源和计算资源； 和分别为第l个时隙从卫星n的传输和处理队列中调度的任务集合；

s.t.表示约束条件，约束条件式(18a)保证第l个时隙卫星给用户m分配的通信资源不应大于第l个时隙卫星n可分配的通信资源 约束条件式(18b)保证第l个时隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式(18c)保证用户m的链路时延 不应大于基于SN；C设定的栅格i的限定时延根据任务的卸载位置不同，用户m的任务k产生的时延 共有三种情况：①如果任务在本地处理，其时延为：

wait process

其中，τ 表示由于本地计算资源被正在处理的任务占用而产生的等待时延；τ ＝Tm/Xm，Xm为用户m的计算资源，Tm为用户m的任务k的大小；

②如果任务卸载至与其关联的接入星na处理，其时延为：off wait

其中，τ 为任务从用户卸载到接入星na的时延，包括传输等待时延τ 、传输时延trans propτ 、传播时延τ 三部分， 为接入星na给用户m分配的通信资源，process

c为光速，为用户m到接入星na的传播距离；τ 由等待处理时延和处理时延两部分组成，为接入星na给用户m分配的计算资源，为了避免资源浪费，任务传输完成后，才可进入处理队列分配计算资源，此处 和 的分配是独立且有先后顺序的，不一return定在同一时隙完成；τ 为结果返回时延，由于返回的处理结果数据量很小，因此忽略传输时延，只考虑返回的传播时延；如果处理结果可在接入星结束覆盖前返回用户，否则， 为接入星na到切换星nh的最短路由距离， 为切换星nh到用户m的传播距离；

③如果任务通过与其关联的接入星na卸载至处理星np处理，其时延为：off ISL

其中，τ 为任务从用户m卸载到接入星na的时延，计算方式同(20)一致；τ 为任务从接入星na通过星间链路卸载到处理星np的时延， 为接入星na到处理星npprocess w_pro process

的星间路由距离；τ 包括任务在处理星的处理队列的等待时延τ 和处理时延τreturn

两部分；τ 为处理结果从处理星np返回用户m的传播时延，首先处理结果会先从处理星np返回接入星na，再由接入星返回给用户，如果处理结果可在接入星结束覆盖前返回用户，否则， 为处理星np到切换星nh的星间路由距离；

在第l个时隙，设卸载决策 和调度决策 已知，卫星的公平通信与计算资源分配子问题表述为：

其中， 为栅格i范围的用户m的任务从卫星n的传输队列中调度并分配通信资源后产生的传输时延； 为栅格i范围的用户m的任务从卫星n的处理队列中调度并分配计算资源后产生的处理时延； 为基于SNC设定的栅格i的限定时延；Cl＝{C1,l,C2,l,...,CN,l},为第l个时隙卫星给各用户分配的通信资源；Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用户分配的计算资源； 和 分别为第l个时隙卫星n可分配的通信资源和计算资源；

s.t.表示约束条件，约束条件式(22a)保证第l个时隙卫星n给用户m分配的通信资源不应大于第l个时隙卫星n可分配的通信资源 约束条件式(22b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延 约束条件式(23a)保证第l个时隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式(23b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延

2.根据权利要求1所述的卫星传输优化方法，其特征在于，采用对偶上升法对公平通信与计算资源分配子问题进行求解，包括：采用对偶上升法对通信资源分配子问题进行求解：引入辅助变量χ，传输时延 其中Tm为用户m的任务k的大小；

公式(22)转换为：

构造拉格朗日函数A：

其中，μm≥0，ν≥0,η≥0为拉格朗日乘子；

则A的对偶函数为：

其中，

D的最大值即为公式(22)所求的最小值；

通过交替迭代辅助变量χ和拉格朗日乘子μm、ν、η，得到公平的通信资源分配

3.根据权利要求1所述的卫星传输优化方法，其特征在于，采用对偶上升法对公平通信与计算资源分配子问题进行求解，包括：采用对偶上升法对计算资源分配子问题进行求解：引入辅助变量χ，处理时延 其中Tm为用户m的任务k的大小；

公式(23)转换为：

构造拉格朗日函数A：

其中，μm≥0，ν≥0,η≥0为拉格朗日乘子；

则A的对偶函数为：

其中，

D的最大值即为公式(23)所求的最小值；

通过交替迭代辅助变量χ和拉格朗日乘子μm、ν、η，得到公平的计算资源分配

4.根据权利要求1所述的卫星传输优化方法，其特征在于，采用深度Q网络对任务卸载与调度决策子问题进行求解，包括：将物联网终端的信息：PU(l)、XU,l、Tl，卫星的信息：Ps(l)、Βl、Cl、Xl，队列的信息：Qtrans,l、Qpro,l输入预训练好的深度Q网络；

得到输出的任务的卸载决策 和调度决策

定义第l个时隙的状态hl＝{PU(l),Ps(l),Tl,Βl,XU,l,Cl,Xl,Qtrans,l,Qpro,lQlocal,l}，PU(l)，Ps(l)分别为第l个时隙用户和卫星的位置；Tl＝{T1,l,T2,l,...,TM,l}为第l个时隙等待或正在调度的用户任务的大小；Βl＝{Β1,l,Β2,l,...,ΒM,l}为第l个时隙用户关联卫星的情况，Βm,l∈{1,2...,N}；XU,l＝{X1,l,X2,l,...,XM,l}，Xm,l∈{0,1}表示第l个时隙用户本地的计算资源是否被占用，即是否有任务正在本地处理；Cl＝{C1,l,C2,l,...,CN,l}为第l个时隙卫星被占用的通信资源；Xl＝{X1,l,X2,l,...,XN,l}为第l个时隙卫星被占用的计算资源；

和 分别为第l个时隙卫星的传输

队列和处理队列中等待调度的任务总量； 为第l个时隙本地用户任务到达队列中等待调度的任务总量；

从任务卸载和调度决策的角度定义第l个时隙的动作其中，Eoff∈{1,2...,Z}为任务的卸载决策，Eoff＝0表示任务在本地处理，Eoff＝Z表示任务卸载至卫星Z处理，Eexe∈{0,1}表示是否从卫星的传输或处理队列中调度任务；通过动作al即可得到用户当前任务的卸载决策 和调度决策

5.根据权利要求1所述的卫星传输优化方法，其特征在于，栅格时延边界表示为：其中D(n)为时延函数，P(D(n)＞x)表示时延超过某个值x的概率，β(n)为随机服务曲线，β(n)是关于n的线性函数，即β(n)＝ρβ(θ)n，ρβ是随机服务曲线β(n)的斜率函数，θ、θ1均为大于0的自由参数。

6.一种卫星传输优化装置，其特征在于，包括处理器及存储介质；

所述存储介质用于存储指令；

所述处理器用于根据所述指令进行操作以执行根据权利要求1至5任一项所述方法的步骤。

7.一种存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至5任一项所述方法的步骤。

说明书

一种基于栅格时延预测的卫星传输优化方法

技术领域

[0001] 本发明属于卫星传输任务卸载和资源分配技术领域，尤其涉及一种基于栅格时延预测的卫星传输优化方法。

背景技术

[0002] 由于单颗卫星的覆盖范围可以达到数万平方公里量级，其覆盖区域将跨越多种地理环境。同时，由于卫星相对地面高速运动，其服务范围内的业务特征呈现快速时变的特性，从而导致全球范围内的卫星物联网业务量分布存在较明显的时空不均匀性。

[0003] 关于卫星网络业务建模与分析领域的相关研究大多未考虑地理位置的问题，而研究与地理位置信息相关的业务模型是解决卫星物联网海量节点随机接入业务碰撞的重要基础。国内外针对卫星物联网架构的传输优化策略研究己经非常丰富，但针对基于移动边缘计算的卫星物联网架构，大多研究未考虑业务QoS服务质量的保障问题，尚缺乏基于时延预测的传输优化策略。

发明内容

[0004] 针对现有技术的不足，本发明的目的在于提供一种基于栅格时延预测的卫星传输优化方法，针对卫星运动导致的时变特性、卫星网络业务到达的突发性、系统服务随机性问题，采用基于地理栅格和随机网络演算的卫星物联网业务建模分析方法，推导栅格时延边界作为 Qos服务质量保障，并基于栅格统计时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题，为解决该问题，将其解耦为基于栅格时延保障的公平资源分配和任务卸载与调度决策两个子问题，分别采用对偶上升法和深度Q网络(DQN)对两个子问题进行求解，以提高卫星网络的资源利用率。

[0005] 本发明为了解决以上问题采用了以下技术方案：

[0006] 第一方面，本发明提供了一种卫星传输优化方法，包括：

[0007] 采用基于地理栅格和随机网络演算的卫星物联网业务建模分析方法，推导出栅格时延边界，基于所述栅格时延边界设定栅格时延限制值，作为栅格时延保障；

[0008] 基于栅格时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题P1；

[0009] 将问题P1解耦为基于栅格时延保障的公平资源分配子问题和任务卸载与调度决策子问题；

[0010] 采用对偶上升法对公平通信与计算资源分配子问题进行求解，得到公平的通信资源分配和计算资源的分配；

[0011] 基于所述通信资源分配和计算资源分配，采用深度Q网络(DQN)对任务卸载与调度决策子问题进行求解，得到用户当前任务的卸载决策和调度决策。

[0012] 在一些实施例中，基于栅格时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题P1，包括：

[0013]

[0014]

[0015] 其中，w为l个时隙内完成并返回结果的用户任务总数；当栅格i范围内的用户m的任务 k在基于SNC推导而设置的限定时延 内完成并返回结果，即 时，否则为0； 为第l个时隙在本地处理的任务的集合，
表示任务在本地处理； 为第l个时隙用户任务卸载的集合，
表示用户m的任务卸载至卫星n处理； 为第l个时隙用户任务
的调度集合， 表示从卫星的传输或处理队列中调度用户m的任务，否则
不调度任务；Cl＝{C1,l,C2,l,...,CN,l}, 为第l个时隙卫星给各用户分
配的通信资源；Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用
户分配的计算资源； 和 分别为第l个时隙卫星n可分配的通信资源和计算资源；
和 分别为第l个时隙从卫星n的传输和处理队列中调度的任务集合；

[0016] s.t.表示约束条件，约束条件式(18a)保证第l个时隙卫星给用户m分配的通信资源 不应大于第l个时隙卫星n可分配的通信资源 约束条件式(18b)保证第l个时隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式 (18c)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延

[0017] 在一些实施例中，在第l个时隙，设卸载决策 和调度决策 已知，卫星的公平通信与计算资源分配子问题表述为：

[0018]

[0019]

[0020] 其中， 为栅格i范围的用户m的任务从卫星n的传输队列中调度并分配通信资源后产生的传输时延； 为栅格i范围的用户m的任务从卫星n的处理队列中调度并分配计算资源后产生的处理时延； 为基于SNC设定的栅格i的限定时延； Cl＝{C1,l,C2,l,...,CN,l}, 为第l个时隙卫星给各用户分配的通信资源； Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用户分配的计算资源； 和 分别
为第l个时隙卫星n可分配的通信资源和计算资源；

[0021] s.t.表示约束条件，约束条件式(22a)保证第l个时隙卫星n给用户m分配的通信资源 不应大于第l个时隙卫星n可分配的通信资源 约束条件式(22b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延 约束条件式(23a)保证第l个时
隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式(23b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延

[0022] 在一些实施例中，采用对偶上升法对公平通信与计算资源分配子问题进行求解，包括：

[0023] 采用对偶上升法对通信资源分配子问题进行求解：

[0024] 引入辅助变量χ，传输时延 其中Tm为用户m的任务k的大小；

[0025] 公式(22)转换为：

[0026]

[0027]

[0028]

[0029]

[0030] 构造拉格朗日函数A：

[0031]

[0032] 其中，μm≥0，ν≥0,η≥0为拉格朗日乘子；

[0033] 则A的对偶函数为：

[0034]

[0035] 其中，

[0036] D的最大值即为公式(22)所求的最小值；

[0037] 通过交替迭代辅助变量χ和拉格朗日乘子μm、ν、η，得到公平的通信资源分配[0038] 同理，采用对偶上升法对计算资源分配子问题进行求解：

[0039] 引入辅助变量χ，处理时延 其中Tm为用户m的任务k的大小；

[0040] 公式(23)转换为：

[0041]

[0042]

[0043]

[0044]

[0045] 构造拉格朗日函数A：

[0046]

[0047] 其中，μm≥0，ν≥0,η≥0为拉格朗日乘子；

[0048] 则A的对偶函数为：

[0049]

[0050] 其中，

[0051] D的最大值即为公式(23)所求的最小值；

[0052] 通过交替迭代辅助变量χ和拉格朗日乘子μm、ν、η，得到公平的计算资源分配[0053] 在一些实施例中，采用深度Q网络对任务卸载与调度决策子问题进行求解，包括：

[0054] 将物联网终端的信息：PU(l)、XU,l、Tl，卫星的信息：Ps(l)、Bl、Cl、Xl，队列的信息：Qtrans,l、Qpro,l输入预训练好的深度Q网络；

[0055] 得到输出的任务的卸载决策 和调度决策

[0056] 定义第l个时隙的状态hl＝{PU(l),Ps(l),Tl,Bl,XU,l,Cl,Xl,Qtrans,l,Qpro,lQlocal,l}，PU(l)，Ps(l)分别为第l个时隙用户和卫星的位置；Tl＝{T1,l,T2,l,...,TM,l}为第l个时隙等待或正在调度的用户任务的大小；Bl＝{B1,l,B2,l,...,BM,l}为第l个时隙用户关联卫星的情况，Bm,l∈{1,2...,N}；XU,l＝{X1,l,X2,l,...,XM,l}，Xm,l∈{0,1}表示第l个时隙用户本地的计算资源是否被占用，即是否有任务正在本地处理；Cl＝{C1,l,C2,l,...,CN,l}为第l个时隙卫星被占用的通信资源；Xl＝{X1,l,X2,l,...,XN,l}为第l个时隙卫星被占用的计算资源；和 分别为第l个时隙卫星的传输
队列和处理队列中等待调度的任务总量； 为第l个时隙本地
用户任务到达队列中等待调度的任务总量；

[0057] 从任务卸载和调度决策的角度定义第l个时隙的动作其中，Eoff∈{1,2...,Z}为任务的卸载决策，Eoff＝0表示任务在本地处理， Eoff＝Z表示任务卸载至卫星Z处理，Eexe∈{0,1}表示是否从卫星的传输或处理队列中调度任务；通过动作al即可得到用户当前任务的卸载决策 和调度决策

[0058] 在一些实施例中，栅格时延边界表示为：

[0059]

[0060] 其中D(n)为时延函数，P(D(n)＞x)表示时延超过某个值x的概率，β(n)为随机服务曲线，β(n)是关于n的线性函数，即β(n)＝ρβ(θ)n，ρβ是随机服务曲线β(n)的斜率函数，θ、θ1均为大于0的自由参数。

[0061] 第二方面，本发明提供了一种卫星传输优化装置，包括处理器及存储介质；

[0062] 所述存储介质用于存储指令；

[0063] 所述处理器用于根据所述指令进行操作以执行根据第一方面所述方法的步骤。

[0064] 第三方面，本发明提供了一种存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现第一方面所述方法的步骤。

[0065] 与现有技术相比，本发明具有以下技术效果：本发明根据随机网络演算推导的栅格时延边界设定任务限制时延，作为卫星的栅格资源约束条件，能够在保障栅格业务QoS、用户公平性的基础上实现动态网络环境中路由关键性能指标(KPI)的快速、准确、低开销评估与推断，提高卫星网络的资源利用率。

附图说明

[0066] 图1是本发明实施例中基于栅格时延预测的卫星传输优化方法的流程图。

[0067] 图2是本发明实施例中栅格业务建模的流程图。

[0068] 图3是本发明实施例中融合星地协同网络架构图。

[0069] 图4是本发明实施例中联合算法流程图。

具体实施方式

[0070] 下面结合附图对本发明作进一步描述，以下实施例仅用于更加清楚地说明本发明的技术方案。

[0071] 在本发明的描述中，若干的含义是一个以上，多个的含义是两个以上，大于、小于、超过等理解为不包括本数，以上、以下、以内等理解为包括本数。如果有描述到第一、第二只是用于区分技术特征为目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量或者隐含指明所指示的技术特征的先后关系。

[0072] 本发明的描述中，参考术语“一个实施例”、“一些实施例”、“示意性实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

[0073] 实施例1

[0074] 一种卫星传输优化方法，包括：

[0075] 采用基于地理栅格和随机网络演算的卫星物联网业务建模分析方法，推导出栅格时延边界，将栅格时延边界作为服务质量保障；基于所述栅格时延边界设定栅格时延限制值，作为栅格时延保障；(将栅格i范围内的用户m的任务k在基于SNC随机网络演算推导而设置的限定时延表示为 )

[0076] 基于栅格时延保障，联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题P1；

[0077] 将问题P1解耦为基于栅格时延保障的公平资源分配子问题和任务卸载与调度决策子问题；

[0078] 采用对偶上升法对公平通信与计算资源分配子问题进行求解，得到公平的通信资源分配和计算资源的分配；

[0079] 基于所述通信资源分配和计算资源分配，采用深度Q网络(DQN)对任务卸载与调度决策子问题进行求解，得到用户当前任务的卸载决策和调度决策。

[0080] 在一些实施例中，如图1所示，一种基于栅格时延预测的卫星传输优化方法，包括：

[0081] 步骤一.基于地理栅格和随机网络演算的网络业务建模与分析：

[0082] 与地面物联网相对静态的拓扑结构不同，由于卫星节点的高动态特性，终端每次产生的业务都可能经由不同的卫星节点汇聚。其中卫星星下点运动轨迹可由卫星星历推算得出，本方案采用随机网络演算理论结合地理栅格的方法分析卫星网络的排队性能，在选取卫星网络的业务到达和信道服务模型时，需充分考虑卫星网络业务到达的随机性和突发性，以及多址接入协议引入的系统服务随机性。研究思路如下：

[0083] 如图2所示，首先，分析全球物联网终端部署，划分地理栅格；然后，基于随机网络演算进行以栅格为单位的业务建模，通过分析网络中业务到达特性和系统服务特性，选取合适的到达模型和服务模型，推导相应的随机到达曲线和随机服务曲线；最后推导各栅格网络性能边界。

[0084] (1)地理栅格划分

[0085] 由于卫星的广覆盖特性，在卫星波束的覆盖区域中势必涵盖多样的地理环境，因而覆盖区内的业务将呈现多样性。因此为了确定覆盖区域内的业务特征，必须要系统性地分析覆盖区域的地理环境情况。首先将地球表面展开看成一二维平面，并按一定的经纬度间隔将地球表面划分为许多栅格，由于划分后的栅格中可能会包含多种地理环境，所以某栅格的设备部署密度由多种地理环境共同决定，定义栅格i的设备部署密度为：

[0086]

[0087] 其中Si表示栅格i的面积，n表示该栅格内包含的地理环境类型数量，ρj表示在地理环境类型 j对应的设备部署密度，Si,j表示栅格i内地理环境类型j所占的面积。Si的计算方式为：

[0088]

[0089] 其中， 和 为栅格i纬度的起止值，μ是该栅格的经度范围，ae是地球赤道圆的半径，e1为第一离心率。

[0090] 卫星波束在地面的投影将直接决定其覆盖范围，从而决定其覆盖区域内的栅格数目。由于物联网业务汇聚于卫星层面，为了简化覆盖面积的计算，可将卫星的全部点波束看成一个合成波束，则其在地面的投影可近似看成为以星下点为圆心的圆周所围区域，如图所示，其圆心角为：

[0091]

[0092] 其中，Re为地球半径，H为轨道高度，α为最小通信仰角。

[0093] (2)业务到达模型

[0094] 现有研究成果验证了卫星网络业务具有自相似性和突发特性。随机网络演算理论是一种新型排队理论分析方法，该理论并不限定网络中业务到达和服务服某种特定分布，而是用包络的方法对网络中的业务到达和信道服务建模，并在模型中引入违反概率，可精确描述卫星网络中业务产生的随机性、突发性以及信道服务的随机性。

[0095] 因此，为了精确描述卫星网络业务的突发特性，并在模型准确性和理论分析的简化之间取得折中，采用马尔可夫调制开关过程(Markov‑modulated ON‑OFF，MMOO)对卫星网络的业务到达进行表征，该模型具有较大可调节性，可适用于不同程度的突发业务。

[0096] 对于业务到达过程A(n)，我们将其用两状态马尔科夫链来表征，其状态空间S由0和1 组成。状态1表示发送节点处于ON状态，以固定速率h发送数据包；状态0表发送节点处于OFF状态，此时无数据包产生。从0状态转换到1状态的概率为μ，而从1转换为0的概率为λ。

[0097] 卫星网络业务到达过程A(n)具有v.b.c.随机到达曲线，用马尔科夫调制的开关过程表征的业务到达A(n), 有

[0098]

[0099] 因此

[0100]

[0101]

[0102] 卫星网络业务到达过程A(n)具有v.b.c.随机到达曲线，即：A(n)～sac，其中有

[0103] α(n)＝ρα(θ)n   (7)

[0104]

[0105]

[0106] 由此可见，α(n)是关于n的线性函数，ρα(θ)是它的斜率，f(x)是α(n)的边界函数。

[0107] (3)信道服务模型

[0108] 在卫星网络的场景中，服务随机性体现在MAC层多用户通过随机接入协议竞争信道服务带来的随机性。目前卫星网络中多采用时隙Aloha协议实现信道预约，因此本方案采用两状态马尔科夫链对时隙Aloha协议的工作原理进行表征。在状态1时，链路可提供速率C来传输数据，在状态0时，链路无法为数据包提供服务。当信道从状态0转换到状态1时，可实现一次数据包成功传输，相应的状态转移概率即为一次成功传输数据的概率ps。当信道从状态1转换为状态0，数据包发生碰撞导致传输失败，相应的状态转移概率为1‑ps。

[0109] 卫星网络的随机服务过程S(n)有随机服务曲线S(n)～s‑ssc，其中：

[0110]

[0111] g(x)＝e‑θx    (11)

[0112]

[0113] 由此可见，β(n)是关于n的线性函数，ρβ(θ)是它的斜率，g(x)是β(n)的边界函数。

[0114] (4)栅格时延边界分析

[0115] 卫星网络时延边界表达式为：

[0116]

[0117] 其中D(n)为时延函数，P(D(n)＞x)表示时延超过某个值x的概率，β(n)为随机服务曲线，β(n)是关于n的线性函数，即β(n)＝ρβ(θ)n，ρβ是随机服务曲线β(n)的斜率函数，θ、θ1均为大于0的自由参数。

[0118] 证明：如果系统到达过程与服务过程相互独立，那么系统时延边界的计算可转化为如下：

[0119]

[0120] 根据函数最大水平距离的定义：

[0121] h(α+x,β)＝supm≥0{inf{τ≥0:α(m)+x≤β(m+τ)}}   (15)

[0122] 可以理解为：求出τ的最小值，使得α(s)+x≤β(s+τ)在s≥0时恒成立。因此，当s＝0 时， 将x的值带入时延求解公式(14)可得：

[0123]‑θx

[0124] 将 g(x)＝e 带入公式(16)，可得：

[0125]

[0126] 结论得证。

[0127] (5)基于上述四步原理划分地理栅格，基于随机网络演算建立栅格业务到达模型和服务模型，并推导出栅格性能边界，再基于边界设定一个栅格时延限制值，将栅格i范围内的用户m的任务k在基于SNC推导而设置的限定时延表示为 该栅格业务建模与分析方法可以有效地为卫星网络资源分配设计提供Qos保障。

[0128] 步骤二.融合MEC场景下基于栅格统计时延保障的任务调度与资源分配策略[0129] 现有研究大多只关注卫星网络资源管理的单个或两个方面，本方案联合考虑任务的卸载决策、调度决策、通信和计算资源的分配方式，将优化问题表述为混合整数非线性规划问题，为解决该问题，将其解耦为基于栅格时延保障的公平资源分配和任务卸载与调度决策两个子问题，分别采用对偶上升法和深度Q网络(DQN)进行求解。具体过程如下：

[0130] 1)我们将具有四个耦合因素的复杂问题解耦为两个子问题，首先是具有栅格时延保障以及固定卸载决策的计算和通信资源分配问题，其次是具有动态约束的卸载与调度决策问题。

[0131] 2)为联合优化具有栅格时延保障以及固定卸载决策的卫星计算和通信资源，采用对偶上升法求解最优的通信和计算资源分配。然后，将资源分配子问题的结果输入到卸载决策问题中，将具有动态约束的卸载决策问题制定为马尔可夫决策过程(MDP)，并使用深度Q网络(DQN) 来增加卸载决策的长期回报，提高任务的完成率。

[0132] 研究思路：首先，根据卫星星座的参数，基于地理栅格划分网格优先级，确定用户与卫星的关联和切换方式；其次，并根据任务的卸载位置，建立任务的时延模型；然后，根据随机网络演算推导的栅格时延边界设定任务限制时延，作为卫星的栅格资源约束条件，并设定目标优化函数；之后，考虑多个任务卸载至同一节点竞争资源的情况，基于栅格时延保障研究公平的资源分配方案；最后，在确定的资源分配方式下，研究用户任务的卸载和调度决策，分析其在提高系统任务完成率方面的表现。

[0133] 场景介绍：如图3所示，在融合MEC的星地协同网络架构的应用场景下，地面上有M 个物联网终端用户，M个用户都会有持续到达的任务，空中有N颗卫星组成的卫星星座，卫星可通过星间无线链路与其他卫星通信，以实现对用户任务的星间协作处理。用户的任务可在本地处理或卸载至卫星处理，本地同时只能处理一个任务，星上可并行处理多个任务。卸载至卫星的任务可在与用户关联的接入星处理并在处理完成后将结果返回用户。当接入星的资源难以满足用户需求时，可以通过星间无线链路将任务卸载至周围其他卫星进行处理，以额外10ms左右的传播时延换取更低的处理时延，以达到星间协作处理的优化效果。

[0134] (1)问题建模及分析

[0135] 在本发明的研究场景中，通过星间无线链路实现卫星网络对地面用户任务的协作处理，为了尽量保证用户任务在限定的时延内完成，需要对任务卸载决策、调度决策、通信和计算资源分配联合进行优化。因此，本发明的最优化问题可表述为，

[0136]

[0137]

[0138] 其中，w为l个时隙内完成并返回结果的用户任务总数；当栅格i范围内的用户m的任务 k在基于SNC推导而设置的限定时延 内完成并返回结果，即 时，否则为0； 为第l个时隙在本地处理的任务的集合， 表
示任务在本地处理； 为第l个时隙用户任务卸载的集合，
表示用户m的任务卸载至卫星n处理； 为第l个时隙用户任务
的调度集合， 表示从卫星的传输或处理队列中调度用户m的任务，否则
不调度任务；Cl＝{C1,l,C2,l,...,CN,l}, 为第l个时隙卫星给各用户分
配的通信资源；Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用
户分配的计算资源； 和 分别为第l个时隙卫星n可分配的通信和计算资源； 和
分别为第l个时隙从卫星n的传输和处理队列中调度的任务集合。

[0139] 约束条件式(18a)保证第l个时隙卫星给用户m分配的通信资源 不应大于第l个时隙卫星n可分配的通信资源 约束条件式(18b)保证第l个时隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式(18c)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延

[0140] (2)算法流程

[0141] 完整的算法流程如图4所示，首先基于地理栅格划分和随机网络建模推导栅格业务限制时延，然后在每个调度时隙，判断是否因为卫星的运动发生切星，之后由基于DQN的任务卸载与调度算法，对持续到达的任务进行卸载和调度，从而对于在同一颗卫星的传输/处理队列中同时调度的任务，由基于对偶上升法的公平资源分配算法为其分配通信与计算资源，即在己知任务卸载与调度决策的前提下，将通信与计算资源的分配问题建模为最大－最小公平性问题进行求解，以提高系统任务完成率。在系统运行期间重复上述步骤。

[0142] (3)时延模型

[0143] 根据任务的卸载位置不同，用户m的任务k产生的时延 共有三种情况。

[0144] ①如果任务在本地处理，其时延为，

[0145]

[0146] 其中，τwait表示由于本地计算资源被正在处理的任务占用而产生的等待时延；

[0147] τprocess＝Tm/Xm，Xm为用户m的计算资源，Tm为用户m的任务k的大小。

[0148] ②如果任务卸载至与其关联的接入星na处理，其时延为，

[0149]

[0150] 其中，τoff为任务从用户卸载到接入星na的时延，包括传输等待时延τwait、传输时延trans propτ 、传播时延τ 三部分， 为接入星na给用户m分配的通信资源，
process
c为光速，为用户m到接入星na的传播距离；τ 由等待处理时延和处理时
延两部分组成， 为接入星na给用户m分配的计算资源，需要注意的是，为
了避免资源浪费，任务传输完成后，才可进入处理队列分配计算资源，此处 和 的分配return
是独立且有先后顺序的，不一定在同一时隙完成；τ 为结果返回时延，由于返回的处理结果数据量很小，因此忽略传输时延，只考虑返回的传播时延。如果处理结果可在接入星结束覆盖前返回用户， 否则， 而为接入星na到切
换星nh的最短路由距离，可由Dijkstra算法求得， 为切换星nh到用户m的传播距离。

[0151] ③如果任务通过与其关联的接入星na卸载至处理星np处理，其时延为

[0152]

[0153] 其中，τoff为任务从用户m卸载到接入星na的时延，计算方式同(20)一致；τISL为任务从接入星na通过星间链路卸载到处理星np的时延，考虑到星间充足的通信资源，星间链路的传输时延可以忽略不计，因此 为接入星na到处理星np的星间路由距离process
(单跳或多跳)，由Dijkstra算法求得；τ 包括任务在处理星的处理队列的等待时延w_pro process return
τ 和处理时延τ 两部分；τ 为处理结果从处理星np返回用户m的传播时延，首先处理结果会先从处理星np返回接入星na，再由接入星返回给用户，如果处理结果可在接入星结束覆盖前返回用户， 否则， 为处理
星np到切换星nh的星间路由距离。

[0154] (4)卫星覆盖与切换策略

[0155] 依据前文所述卫星波束在地面的投影将直接决定其覆盖范围，从而决定其覆盖区域内的栅格数目，由于系统需对全球提供无缝覆盖，在系统设计时卫星覆盖区域会出现部分重叠。在重叠区域内，终端将根据距离最近原则优先选择卫星节点进行传输。

[0156] 卫星覆盖区域按照距星下点的距离被划分为若干优先级网格，在卫星重叠覆盖区域内，处在同一个地理栅格中的所有物联网设备节点实时选择优先级最高的卫星进行汇聚。当通信仰角小于最小覆盖仰角αmin时，表示该卫星即将结束覆盖终端，重新根据该优先级准则选择优先级更高的卫星进行切换。如果任务处理结果未能在接入星结束覆盖前返回，则通过切换的卫星将结果返回。

[0157] 以某一个时刻为例，某一颗卫星相对于地理网格的优先级按照如下的步骤进行计算：

[0158] 步骤1、取出卫星星下点所处的经纬度坐标，确定其处于地理网格的网格索引。

[0159] 步骤2、将卫星星下点所处的网格的优先级设置为1，为其周围网格设置相应的优先级，距离此网格越近，表示与卫星的距离越小，则优先级越高。

[0160] 步骤3、网格取出相对于自身优先级最高的卫星编号进行接入。

[0161] (5)基于对偶上升法的公平资源分配算法

[0162] 为了求解任务卸载与调度决策的子问题，需要先求得资源分配子问题的解。在己知任务卸载与调度决策的前提下，将通信与计算资源的分配问题建模为最大－最小公平性问题进行求解，以最小化任务的最大时延，提高系统整体的任务完成率。详细的求解推导过程如下文所示。

[0163] 在第l个时隙，如果卸载决策 和调度决策 已知，卫星的公平资源分配问题可表述为，

[0164]

[0165]

[0166] 其中， 为栅格i范围的用户m的任务从卫星n的传输队列中调度并分配通信资源后产生的传输时延； 为栅格i范围的用户m的任务从卫星n的处理队列中调度并分配计算资源后产生的处理时延； 为基于SNC设定的栅格i的限定时延； Cl＝{C1,l,C2,l,...,CN,l}, 为第l个时隙卫星给各用户分配的通信资源； Xl＝{X1,l,X2,l,...,XN,l}， 为第l个时隙卫星给各用户分配的计算资源； 和
分别为第l个时隙卫星n可分配的通信和计算资源。

[0167] 约束条件式(22a)保证第l个时隙卫星给用户m分配的通信资源 不应大于第l个时隙卫星n可分配的通信资源 约束条件式(22b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延 同理，约束条件式(23a)保证第l个时隙卫星给用户m分配的计算资源 不应大于第l个时隙卫星n可分配的计算资源 约束条件式(23b)保证用户m的链路时延 不应大于基于SNC设定的栅格i的限定时延

[0168] 由于最优化问题(22)和(23)是两个凸问题，可由对偶上升法(DualAscent)进行求解。

[0169] 首先，采用对偶上升法对通信资源分配子问题进行求解：

[0170] 引入辅助变量χ，由前文可知传输时延 则公式(22)可转换为，

[0171]

[0172]

[0173]

[0174]

[0175] 其中，引入辅助变量χ后，优化模型约束条件由(22a‑b)转换为(24a‑c)。

[0176] 其次，构造拉格朗日函数A：

[0177]

[0178] 其中，μm≥0，ν≥0,η≥0为拉格朗日乘子。

[0179] 则A的对偶函数为：

[0180]

[0181] 其中，

[0182] 由于公式(22)为凸问题，则D的最大值即为公式(22)所求的最小值。求解过程如下所示。

[0183]

[0184]

[0185] 如果μm、ν、η的更新值连续100次迭代小于0.001，则认为其己收敛。通过交替迭代自变量和拉格朗日乘子，可以得到公平的通信资源分配

[0186] 同理，采用对偶上升法对计算资源分配子问题进行求解，包括：

[0187] 引入辅助变量χ，处理时延 其中Tm为用户m的任务k的大小

[0188] 公式(23)转换为：

[0189]

[0190]

[0191] 构造拉格朗日函数A：

[0192]

[0193] 其中，μm≥0，ν≥0,η≥0为拉格朗日乘子；

[0194] 则A的对偶函数为：

[0195]

[0196] 其中，

[0197] D的最大值即为公式(23)所求的最小值；

[0198] 通过交替迭代辅助变量χ和拉格朗日乘子μm、ν、η，得到公平的计算资源分配求解过程如下所示。

[0199]

[0200]

[0201] (6)基于DQN的任务卸载与调度决策算法

[0202] 由前文可得到每个时隙最公平的通信和计算资源分配。然而，卸载与调度的联合决策仍然是一个非凸的动态规划问题。因此采用DQN算法，解决持续到达的多批任务在长时间段内耦合的卸载、调度、资源分配问题。此问题具体的MDP表示如下：

[0203] 1)Stata(H)：

[0204] 定义第l个时隙的状态hl＝{PU(l),Ps(l),Tl,Bl,XU,l,Cl,Xl,Qtrans,l,Qpro,lQlocal,l}，PU(l)，Ps(l)分别为第l个时隙用户和卫星的位置；Tl＝{T1,l,T2,l,...,TM,l}为第l个时隙等待或正在调度的用户任务的大小；Bl＝{B1,l,B2,l,...,BM,l}为第l个时隙用户关联卫星的情况，Bm,l∈{1,2...,N}；XU,l＝{X1,l,X2,l,...,XM,l}，Xm,l∈{0,1}表示第l个时隙用户本地的计算资源是否被占用，即是否有任务正在本地处理；Cl＝{C1,l,C2,l,...,CN,l}为第l个时隙卫星被占用的通信资源；Xl＝{X1,l,X2,l,...,XN,l}为第l个时隙卫星被占用的计算资源；和 分别为第l个时隙卫星的传输
队列和处理队列中等待调度的任务总量； 为第l个时隙本地
用户任务到达队列中等待调度的任务总量。

[0205] 2)Action(A)

[0206] 每个时隙的动作空间应包括用户当前任务的卸载、调度决策和卫星通信、计算资源的分配。由于通信资源分配Cl和计算资源分配Xl可由算法1‑1和算法1‑2得到，因此，从任务卸载和调度决策的角度定义第l个时隙的动作其中， Eoff∈{1,2...,Z}为任务的卸载决策，Eoff＝0表示任务在本地处理，Eoff＝Z表示任务卸载至卫星Z处理，由于整个星座的卫星个数N通常在几百到几千，大部分离用户距离很远，因此，仅考虑离用户最近的Z颗卫星进行卸载；Eexe∈{0,1}表示是否从卫星的传输或处理队列中调度任务。通过al即可得到用户当前任务的卸载决策 和调度决策

[0207] 3)TransitionProbability(P)

[0208] 在本方案所研究的场景中，动作空间和状态空间都非常庞大，且状态空间中的部分量为连续变量，难以得到精确的状态转移概率。因此，本方案选择了model‑free的深度强化学习 DQN架构。

[0209] 4)Reward(R)

[0210] 为了最大化用户任务的完成率，定义第l个时隙状态hl下选择动作al的回报为：

[0211]

[0212] 其中， 为第l个时隙调度任务k而产生的传输或处理时延；RP是一个正的常数，使d为第l个时隙在限制时延内完成的任务个数；Rd为任务在限制时延内完成的额外回报。

[0213] 采用深度Q网络对任务卸载与调度决策子问题进行求解，包括：

[0214] 将物联网终端的信息：PU(l)、XU,l、Tl，卫星的信息：Ps(l)、Bl、Cl、Xl，队列的信息：Qtrans,l、Qpro,l输入预训练好的深度Q网络；

[0215] 得到输出的任务的卸载决策 和调度决策

[0216] 深度Q网络的训练过程如算法2所示，其中，γ、ε、ζ、δ为训练寻优过程中涉及的网络参数：γ是动作价值函数的折扣因子；ε为贪心策略选择动作概率(贪心策略，就是小概率选择随机动作，大概率选择最优动作)，即以ε的概率随机选择动作，以1‑ε的概率选择最优动作；ζ为经验回放池；δ用于计算训练损失函数，其训练目标为使损失函数最小化。

[0217] 每个时隙进行一次任务调度，每个时隙为训练过程的一步。首先以参数γ、ε、ζ初始化网络和经验池。其次在每个时隙l的状态hl下，根据ε贪心策略选取动作，即以ε的概率随机选择动作，以1‑ε的概率选择最优动作。然后输入根据算法1‑1和算法1‑2，计算得到的卫星通信资源分配Cl和计算资源的分配Xl。接着更新系统环境至下一状态hl+1，计算本时隙的状态hl下选择动作al的回报R(hl,al)，并将hl和al保存至经验池中。最后计算损失函数的值，每隔固定的步数，从主网络中复制参数到目标网络。重复上述步骤直至损失函数收敛于0。

[0218]

[0219] 实施例2

[0220] 第二方面，本实施例提供了一种卫星传输优化装置，包括处理器及存储介质；

[0221] 所述存储介质用于存储指令；

[0222] 所述处理器用于根据所述指令进行操作以执行根据实施例1所述方法的步骤。

[0223] 实施例3

[0224] 第三方面，本实施例提供了一种存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现实施例1所述方法的步骤。

[0225] 本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。

[0226] 本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/ 或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/ 或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

[0227] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

[0228] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

[0229] 本领域内的技术人员应该明白，本申请的实施例可提供为方法或计算机程序产品。以上实施例仅用于说明本发明所提出的方法而并非限制本方法，尽管上文通过实施例对本专利方法进行了详细的说明，所述领域的技术人员应当理解，仅对本发明具体实施方法进行同等替换而其本质并未改变的方案应包含在本发明的权利要求保护范围之内。