一种面向边缘服务器成本优化的流量调度方法

摘要

本发明公开了一种面向边缘服务器成本优化的流量调度方法，包括：读取结算周期时刻数内每个时刻的用户数、每个用户的带宽需求及服务时延；设定时延阈值；基于服务时延与时延阈值绘制拓扑网络图；构建用户的带宽需求队列和每个边缘服务器的带宽需求队列；依次对用户的带宽需求队列中的每个元素对应的带宽需求和该带宽需求是否位于95计费点内所对应时刻的拓扑网络图的属性进行变更，根据变更后的拓扑网络图中有向边的属性计算残差值，利用增广路法和bellman‑ford算法搜索图中的连通路径，直至不存在连通路径；根据每个时刻的拓扑网络图输出各时刻下所有用户的卸载流量值。本发明可在保证用户体验的情况下尽可能降低服务提供商成本。

权利要求

1.一种面向边缘服务器成本优化的流量调度方法，其特征在于，包括如下步骤：S1，构建包括边缘服务器和用户的流量调度系统，读取结算周期的时刻数T内每个时刻的用户数、边缘服务器数、每个用户的带宽需求、每个边缘服务器的带宽上限以及边缘服务器和用户之间的服务时延；

S2，设定时延阈值K；

S3，基于边缘服务器和用户之间的服务时延与时延阈值K之间的关系，绘制每个时刻下表征用户和边缘服务器连接属性的拓扑网络图；

S4，根据带宽需求大小分别构建用户的带宽需求队列和每个边缘服务器的带宽需求队列，并为用户的带宽需求队列中的每个元素设置索引，初始化索引号r＝1，所述每个边缘服务器的带宽需求队列中的每个元素均至少包含时刻和该时刻下边缘服务器的带宽需求两个子元素；

S5，根据索引号r所对应的带宽需求和该带宽需求是否位于95计费点内对索引号r所对应时刻的拓扑网络图的属性进行变更；

S6，根据步骤S5变更后的拓扑网络图中有向边的属性计算残差值，并利用增广路法和bellman‑ford算法搜索该拓扑网络图中的连通路径，根据残差值再次更新该拓扑网络图的属性并搜索连通路径，直至拓扑网络图中不存在连通路径；

S7，判断r＜N，如果是，执行r＝r+1，并返回步骤S5，否则根据每个时刻的拓扑网络图输出各时刻下所有用户的卸载流量值，其中，N表示用户总数；

所述步骤S3包括如下步骤：

S3.1，初始化时刻tnow＝1；

S3.2，将tnow时刻下每个边缘服务器和用户之间的服务时延与时延阈值K进行比较，判断对应的边缘服务器和用户之间是否可以发生卸载，其表达式为：式中，当 时，表示第i个边缘服务器Mi和第j个用户Nj之间可以发生卸载，当时，表示边缘服务器Mi和用户Nj之间不能发生卸载， 表示边缘服务器Mi与用户Nj之间的服务时延；

S3.3，将tnow时刻下的每个用户和每个边缘服务器分别看作一个节点，根据步骤S3.1得到的比较结果依次在每个用户和每个边缘服务器之间构建有向边，所述有向边的属性包括起点、终点、容量、流量和权重；

S3.4，增加虚拟节点S，将虚拟节点S视为起点、tnow时刻下的每个用户分别视为终点，在虚拟节点S和每个用户Nj之间依次构建容量为0、流量为0、权重为0的有向边S3.5，增加虚拟节点E，将tnow时刻下的每个边缘服务器分别视为起点、虚拟节点E视为终点，在每个边缘服务器Mi和虚拟节点E之间依次构建容量为边缘服务器的带宽上限、流量为0、权重为0的有向边 进而形成tnow时刻下的拓扑网络图S3.6，判断tnow

2.根据权利要求1所述的面向边缘服务器成本优化的流量调度方法，其特征在于，所述步骤S4包括如下步骤：S4.1，计算每个时刻下所有用户的带宽需求总数，按照降序顺序对所有时刻下的带宽需求总数进行排序形成用户的带宽需求队列QN；

S4.2，为步骤S4.1中得到的用户的带宽需求队列QN中的每个元素分别设置索引，并初始化索引号r＝1；

S4.3，为每个边缘服务器Mi设置一个带宽需求队列 所述带宽需求队列 中的每个元素包含时刻 和该时刻下边缘服务器的带宽需求 两个子元素，根据带宽需求队列 中每个元素的带宽需求对带宽需求队列 进行降序排序以更新带宽需求队列其中，k表示带宽需求队列 中的元素序号，且1≤k≤T；

S4.4，为每个边缘服务器Mi分别设置权重 和已使用时刻数 两个参数，并将这两个参数均初始化为0。

3.根据权利要求2所述的面向边缘服务器成本优化的流量调度方法，其特征在于，在步骤S4.3中，所述边缘服务器的带宽需求 对应的计算公式为：式中， 表示拓扑网络图中以边缘服务器Mi为起点虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间构建的有向边 的流量。

4.根据权利要求1所述的面向边缘服务器成本优化的流量调度方法，其特征在于，所述步骤S5包括如下步骤：S5.1，从用户的带宽需求队列QN中找到索引号r＝1对应的带宽需求 并将拓扑网络图 中的有向边 的容量变更为 其中， 表示td时刻的拓扑网络图， 表示用户 在td时刻下的带宽需求， 表示以虚拟节点S为起点、用户 为终点，在虚拟节点S和用户 之间所构建的有向边，且1≤jd≤N，1≤td≤T；

S5.2，若带宽需求 在边缘服务器Mi的带宽需求队列 中位于 也即

且 则将拓扑网络图 中的有向边 的权重变更为 否则将

拓扑网络图 中的有向边 的权重变更为权重 其中， 表示边缘服务器Mi的带宽需求队列 中元素序号为 的元素的时刻子元素， 表示以边缘服务器Mi为起点、虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间所构建的有向边， 表示边缘服务器Mi的已使用时刻数；

S5.3，判断 如果是，将拓扑网络图 中的有向边

的容量变更为 否则使拓扑网络图 中的有向边 的容量等于其流量，其

中， 表示边缘服务器Mi的带宽需求队列 中元素序号为T×5％处所对应的带宽需求子元素， 表示有向边 的流量。

5.根据权利要求1所述的面向边缘服务器成本优化的流量调度方法，其特征在于，所述步骤S6包括如下步骤：S6.1，根据拓扑网络图中有向边的残差值搜寻拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径， 表示用户的带宽需求队列中索引号r所对应的时刻td的拓扑网络图；

S6.2，根据属性计算步骤S6.1中代价最小的连通路径的残差值resi_min，将该连通路径中所有有向边的流量加上残差值resi_min，并将该连通路径中所有有向边的反向边的容量加上残差值resi_min，以分别更新该连通路径中所有有向边的流量和反向边的容量；

S6.3，判断resi_min>0，如果是，返回步骤S6.1，否则执行步骤S6.4；

S6.4，将拓扑网络图 中所有有向边 的容量更新为对应的边缘服务器Mi的带宽上限Ci，其中， 表示拓扑网络图中以边缘服务器Mi为起点、虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间所构建的有向边；

S6.5，根据有向边的残差值搜寻更新后的拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径；

S6.6，根据有向边的属性计算步骤S6.5中代价最小的连通路径的残差值 将该连通路径中所有有向边的流量加上残差值 将该连通路径中所有有向边的反向边的容量加上残差值 以分别更新该连通路径中所有有向边的流量和反向边的容量；

S6.7，判断 如果是，返回步骤S6.5，否则执行步骤S6.8；

S6.8，遍历每一个边缘服务器的带宽需求队列中的元素，判断是否有 如果有，执行 否则根据 的值将子元素td和子元素组成的元素对应的插入边缘服务器的带宽需求队列中，其中， 表示边缘服务器Mi的带宽需求队列 中元素序号为k的元素所对应的时刻子元素， 表示有向边 的流量， 表示边缘服务器Mi的带宽需求队列 中元素序号为k的元素所对应的带宽需求子元素；

S6.9，将步骤S6.8更新后的每一个边缘服务器的带宽需求队列中的前T×5％‑1个元素复制到新队列Q′中，根据带宽需求按照降序顺序对新队列Q′进行排序更新，如果带宽需求值相同，则按照边缘服务器的带宽上限升序排序以更新新队列Q′；

S6.10，遍历更新后的新队列Q′，将第l个元素所对应的边缘服务器的权重变更为T+N‑l,且l为正整数；

S6.11，判断拓扑网络图 中虚拟节点S和每个用户Nj之间的有向边 中是否都满足有向边 如果是，则将拓扑网络图 中有向边 的流量减去该有向边对应的反向边的流量 得到卸载流量值 即为td

时刻用户Nj卸载到边缘服务器Mi的流量值，否则执行步骤S6.12，其中， 表示有向边 的流量， 表示有向边 的容量， 表示以边缘服务器Mi为起点、用户Nj为终点，在边缘服务器Mi和用户Nj之间所构建的有向边， 表示有向边的反向边。

6.根据权利要求5所述的面向边缘服务器成本优化的流量调度方法，其特征在于，在步骤S6.1中，所述残差值是指有向边的容量减去有向边的流量的差值，对应的计算公式为：式中，resi表示残差值， 表示从起点start到终点end所绘制的有向边的容量， 表示有向边 的流量。

说明书

一种面向边缘服务器成本优化的流量调度方法

技术领域

[0001] 本发明属于互联网数据技术领域，具体涉及一种面向边缘服务器成本优化的流量调度方法。

背景技术

[0002] 目前移动视频流业务的兴起为互联网带来了大量的流量处理需求，同时为传统的集中式云服务带来了巨大的压力。传统的集中式云服务器远离用户节点，流量到达服务器需要经过长距离传输，服务的时延较高，体验较差。为了解决这一问题，边缘计算服务架构被提出。边缘计算通过在离用户较近的边缘侧设置多个分布式服务器解决了数据传输距离过长，时延高，用户体验差的问题，但也带来了新的流量调度问题。

[0003] 95带宽计费是一种服务器带宽计费模式。95带宽计费按自然日或者自然月结算，分别被称为95日计费和95月计费。95计费将结算时间前服务器的每5分钟有效带宽值进行降序排列，取该序列的第5％位的有效带宽值为计费标准。为了下文的表述清晰，在此称该经过排序的序列为服务器的带宽需求序列，总时刻乘5％的位置为95计费点，一台服务器带宽序列的95计费点的值为边缘服务器成本。该计费方式被广大服务器提供商所使用，是目前最流行的服务器带宽收费方式。同时，如何调度流量减少95计费下的服务器成本是服务提供商非常关心的研究热点。然而现有流量调度方案，没有考虑边缘计算场景下边缘服务器与用户拓扑的复杂性，不能合理调度多用户随时间不断变化的流量，使服务器带宽成本增加，服务提供商的利润减少。

发明内容

[0004] 针对现有流量调度方案不能合理调度多用户随时间不断变化的流量导致成本增加的技术问题，本发明提出了一种面向边缘服务器成本优化的流量调度方法，解决了互联网直播技术为满足用户提供稳定、低延时的视频流服务，需要大量的带宽资源，需要服务提供商也即直播平台向通信运营商租赁大量边缘服务器满足用户的带宽需求而带来的高成本问题。为解决以上技术问题，本发明所采用的技术方案如下：

[0005] 一种面向边缘服务器成本优化的流量调度方法，包括如下步骤：

[0006] S1，构建包括边缘服务器和用户的流量调度系统，读取结算周期的时刻数T内每个时刻的用户数、边缘服务器数、每个用户的带宽需求、每个边缘服务器的带宽上限以及边缘服务器和用户之间的服务时延；

[0007] S2，设定时延阈值K；

[0008] S3，基于边缘服务器和用户之间的服务时延与时延阈值K之间的关系，绘制每个时刻下表征用户和边缘服务器连接属性的拓扑网络图；

[0009] S4，根据带宽需求大小分别构建用户的带宽需求队列和每个边缘服务器的带宽需求队列，并为用户的带宽需求队列中的每个元素设置索引，初始化索引号r＝1，所述每个边缘服务器的带宽需求队列中的每个元素均至少包含时刻和该时刻下边缘服务器的带宽需求两个子元素；

[0010] S5，根据索引号r所对应的带宽需求和该带宽需求是否位于95计费点内对索引号r所对应时刻的拓扑网络图的属性进行变更；

[0011] S6，根据步骤S5变更后的拓扑网络图中有向边的属性计算残差值，并利用增广路法和bellman‑ford算法搜索该拓扑网络图中的连通路径，根据残差值再次更新该拓扑网络图的属性并搜索连通路径，直至拓扑网络图中不存在连通路径；

[0012] S7，判断r

[0013] 所述步骤S3包括如下步骤：

[0014] S3.1，初始化时刻tnow＝1；

[0015] S3.2，将tnow时刻下每个边缘服务器和用户之间的服务时延与时延阈值K进行比较，判断对应的边缘服务器和用户之间是否可以发生卸载，其表达式为：

[0016]

[0017] 式中，当 时，表示边缘服务器Mi和用户Nj之间可以发生卸载，当时，表示边缘服务器Mi和用户Nj之间不能发生卸载， 表示边缘服务器Mi与用户Nj之间的服务时延；

[0018] S3.3，将tnow时刻下的每个用户和每个边缘服务器分别看作一个节点，根据步骤S3.2得到的比较结果依次在每个用户和每个边缘服务器之间构建有向边，所述有向边的属性包括起点、终点、容量、流量和权重；

[0019] S3.4，增加虚拟节点S，将虚拟节点S视为起点、tnow时刻下的每个用户分别视为终点，在虚拟节点S和每个用户Nj之间依次构建容量为0、流量为0、权重为0的有向边[0020] S3.5，增加虚拟节点E，将tnow时刻下的每个边缘服务器分别视为起点、虚拟节点E视为终点，在每个边缘服务器Mi和虚拟节点E之间依次构建容量为边缘服务器的带宽上限、流量为0、权重为0的有向边 进而形成tnow时刻下的拓扑网络图

[0021] S3.6，判断tnow

[0022] 所述步骤S4包括如下步骤：

[0023] S4.1，计算每个时刻下所有用户的带宽需求总数，按照降序顺序对所有时刻下的带宽需求总数进行排序形成用户的带宽需求队列QN；

[0024] S4.2，为步骤S4.1中得到的用户的带宽需求队列QN中的每个元素分别设置索引，并初始化索引号r＝1；

[0025] S4.3，为每个边缘服务器Mi设置一个带宽需求队列 所述带宽需求队列 中的每个元素包含时刻 和该时刻下边缘服务器的带宽需求 两个子元素，根据带宽需求队列 中每个元素的带宽需求对带宽需求队列 进行降序排序以更新带宽需求队列 其中，k表示带宽需求队列 中的元素序号，且1≤k≤T；

[0026] S4.4，为每个边缘服务器Mi分别设置权重 和已使用时刻数 两个参数，并将这两个参数均初始化为0。

[0027] 在步骤S4.3中，所述边缘服务器的带宽需求 对应的计算公式为：

[0028]

[0029] 式中， 表示拓扑网络图中以边缘服务器Mi为起点虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间构建的有向边 的流量。

[0030] 所述步骤S5包括如下步骤：

[0031] S5.1，从用户的带宽需求队列QN中找到索引号r＝1对应的带宽需求 并将拓扑网络图 中的有向边 的容量变更为 其中， 表示td时刻的拓扑网络图，表示用户 在td时刻下的带宽需求， 表示以虚拟节点S为起点、用户 为终点，在虚拟节点S和用户 之间所构建的有向边，且1≤jd≤N，1≤td≤T；

[0032] S5.2，若带宽需求 在边缘服务器Mi的带宽需求队列 中位于 也即且 则将拓扑网络图 中的有向边 的权重变更为否则将拓扑网络图 中的有向边 的权重变更为权重 其中，
表示边缘服务器Mi的带宽需求队列 中 位置处所对应的时刻子元素， 表示以边缘服务器Mi为起点、虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间所构建的有向边， 表示带宽需求队列 中元素序号为 的元素的时刻子元素， 表示边缘服务器Mi的已使用时刻数；

[0033] S5.3，判断 如果是，将拓扑网络图 中的有向边的容量变更为 否则使拓扑网络图 中的有向边 的容量等于其
流量，其中， 表示边缘服务器Mi的带宽需求队列 中元素序号为T×5％处所对应的带宽需求子元素， 表示有向边 的流量。

[0034] 所述步骤S6包括如下步骤：

[0035] S6.1，根据拓扑网络图中有向边的残差值搜寻拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径， 表示用户的带宽需求队列中索引号r所对应的时刻td的拓扑网络图；

[0036] S6.2，根据属性计算步骤S6.1中代价最小的连通路径的残差值resi_min，将该连通路径中所有有向边的流量加上残差值resi_min，并将该连通路径中所有有向边的反向边的容量加上残差值resi_min，以分别更新该连通路径中所有有向边的流量和反向边的容量；

[0037] S6.3，判断resi_min>0，如果是，返回步骤S6.1，否则执行步骤S6.4；

[0038] S6.4，将拓扑网络图 中所有有向边 的容量更新为对应的边缘服务器Mi的带宽上限Ci，其中， 表示拓扑网络图中以边缘服务器Mi为起点、虚拟节点E为终点，在边缘服务器Mi和虚拟节点E之间所构建的有向边；

[0039] S6.5，根据有向边的残差值搜寻更新后的拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径；

[0040] S6.6，根据有向边的属性计算步骤S6.5中代价最小的连通路径的残差值将该连通路径中所有有向边的流量加上残差值 将该连通路径中所有有向边的反向边的容量加上残差值 以分别更新该连通路径中所有有向边的流量和反向边的容量；

[0041] S6.7，判断 如果是，返回步骤S6.5，否则执行步骤S6.8；

[0042] S6.8，遍历每一个边缘服务器的带宽需求队列中的元素，判断是否有如果有，执行 否则根据 的值将子元素td和子元素组成的元素对应的插入边缘服务器的带宽需求队列中，其中， 表示边缘服务器Mi的带宽需求队列 中元素序号为k的元素所对应的时刻子元素， 表示有向边 的流量， 表示边缘服务器Mi的带宽需求队列 中元素序号为k
的元素所对应的带宽需求子元素；

[0043] S6.9，将步骤S6.8更新后的每一个边缘服务器的带宽需求队列中的前T×5％‑1个元素复制到新队列Q′中，根据带宽需求按照降序顺序对新队列Q′进行排序更新，如果带宽需求值相同，则按照边缘服务器的带宽上限升序排序以更新新队列Q′；

[0044] S6.10，遍历更新后的新队列Q′，将第l个元素所对应的边缘服务器的权重变更为T+N‑l,且l为正整数；

[0045] S6.11，判断拓扑网络图 中虚拟节点S和每个用户Nj之间的有向边 中是否都满足有向边 如果是，则将拓扑网络图 中有向边的流量 减去该有向边对应的反向边的流量 得到卸载流
量值 即为td时刻用户Nj卸载到边缘服务器Mi的流量值，否则执行步骤S6.12，其中，表示有向边 的流量， 表示有向边 的容量，
表示以边缘服务器Mi为起点、用户Nj为终点，在边缘服务器Mi和用户Nj之间所构建的有向边， 表示有向边 的反向边。

[0046] 在步骤S6.1中，所述残差值是指有向边的容量减去有向边的流量的差值，对应的计算公式为：

[0047]

[0048] 式中，resi表示残差值， 表示从起点start到终点end所绘制的有向边的容量， 表示有向边 的流量。

[0049] 本发明的有益效果：

[0050] 本申请首先从理论上保证了用户的带宽需求一定能被调度到有带宽资源的服务器上，保证了全部用户的需求都能够被及时处理，满足了服务提供商必须首先保证用户体验的这一原则。同时，在满足用户的全部带宽需求的基础上，通过针对95计费特点的带宽需求调度显著降低了服务器成本。解决了现有带宽分配方案仅考虑对客户侧的服务保证，没有考虑在边缘计算场景下客户需求与服务成本之间的复杂关系，不能有效节约成本的问题。在满足用户时延和带宽需求的情况下，有效降低了服务提供商的成本，节约资金。

附图说明

[0051] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0052] 图1为三个用户和三个边缘服务器之间的流量卸载示意图。

[0053] 图2为图1的拓扑网络图。

[0054] 图3为不同时延阈值下本申请与现有技术的成本对比示意图。

具体实施方式

[0055] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0056] 一种面向边缘服务器成本优化的流量调度方法，包括如下步骤：

[0057] S1，构建包括边缘服务器和用户的流量调度系统，读取结算周期的时刻数T内每个时刻的用户数、边缘服务器数、每个用户的带宽需求、每个边缘服务器的带宽上限以及边缘服务器和用户之间的服务时延；

[0058] 所述用户的集合采用 表示， Nj表示第j个用户，下标N表示用户集合 中的用户总数。边缘服务器的集合采用 表示， Mi
表示第i个边缘服务器，下标M表示边缘服务器集合 中的边缘服务器总数，边缘服务器Mi的带宽上限为Ci。当95带宽计费按照一个自然日或自然月结算时，假设一个自然日或自然月共有T个时刻，在每个时刻t，用户Nj的带宽需求为 每个用户的带宽需求都可能会随时间变化，用户需要在每个时刻将自己的带宽需求全部卸载到边缘服务器，并且保证边缘服务器的总带宽不超过其带宽上限。同时，由于边缘服务器的地理位置分散，不同用户连接到不同的边缘服务器会有不同的服务时延，将 表示边缘服务器Mi与用户Nj之间的服务时延，当 大于时延阈值K时，服务时延过高会影响到用户体验，设定用户Nj不可以将自己的带宽需求卸载到边缘服务器Mi。

[0059] S2，设定时延阈值K；

[0060] S3，基于边缘服务器和用户之间的服务时延与时延阈值K之间的关系，绘制每个时刻下表征用户和边缘服务器连接属性的拓扑网络图，包括如下步骤：

[0061] S3.1，初始化时刻tnow＝1；

[0062] S3.2，将tnow时刻下每个边缘服务器和用户之间的服务时延与时延阈值K进行比较，判断对应的边缘服务器和用户之间是否可以发生卸载，其表达式为：

[0063]

[0064] 式中，当 时，表示边缘服务器Mi和用户Nj之间可以发生卸载，当时，表示边缘服务器Mi和用户Nj之间不能发生卸载。

[0065] 如图1所示，图中为三个用户和三个边缘服务器，用户1可以将流量调度到边缘服务器1、边缘服务器2和边缘服务器3上，用户2和用户3只能将流量卸载到边缘服务器1上。

[0066] S3.3，将tnow时刻下的每个用户和每个边缘服务器分别看作一个节点，根据步骤S3.2得到的比较结果依次在每个用户和每个边缘服务器之间构建有向边，所述有向边的属性包括起点、终点、容量、流量和权重；

[0067] 当边缘服务器Mi和用户Nj之间可以发生卸载也即 时，将边缘服务器Mi和用户Nj分别作为起点和终点，起点和终点确定时两者之间可以唯一确定一条有向边。具体地，将用户Nj视作起点start，将边缘服务器Mi视作终点end，在用户Nj和边缘服务器Mi之间构建容量为无穷大、流量为0、权重为0的有向边 有向边 的容量采用表示，有向边 的流量采用 表示，有向边 的权重采
用 表示，同时，将边缘服务器Mi视作起点start，将用户Nj视作终点end，在边缘服务器Mi和用户Nj之间构建容量为0、流量为0、权重为0的有向边 有向边 的容量采用 cap表示，有向边 的流量采用 表示，有向边
的权重采用 cost表示，有向边 和有向边 互为反向边。

[0068] S3.4，增加虚拟节点S，将虚拟节点S视为起点、tnow时刻下的每个用户分别视为终点，在虚拟节点S和每个用户Nj之间依次构建容量为0、流量为0、权重为0的有向边[0069] 具体地，对于用户Nj，将虚拟节点S视作起点start，将用户Nj视作终点end，在虚拟节点S和用户Nj之间构建容量为0、流量为0、权重为0的有向边 也即有向边 的容量 有向边 的流量 有向边 的权重

[0070] S3.5，增加虚拟节点E，将tnow时刻下的每个边缘服务器分别视为起点、虚拟节点E视为终点，在每个边缘服务器Mi和虚拟节点E之间依次构建容量为边缘服务器的带宽上限、流量为0、权重为0的有向边 进而形成tnow时刻下的拓扑网络图

[0071] 具体地，对于边缘服务器Mi，将边缘服务器Mi视作起点start，将虚拟节点E视作终点end，在边缘服务器Mi和虚拟节点E之间构建容量为Ci、流量为0、权重为0的有向边也即 有向 边 的 容 量 有向 边 的 流 量有向边 的权重

[0072] S3.6，判断tnow

[0073] 如图2所示为根据以上方法所形成的图1的拓扑网络图。

[0074] S4，根据带宽需求大小分别构建用户的带宽需求队列QN和每个边缘服务器Mi的带宽需求队列 并为用户的带宽需求队列QN中的每个元素设置索引，初始化索引号r＝1，所述每个边缘服务器Mi的带宽需求队列 中的每个元素包含时刻 和该时刻下边缘服务器的带宽需求 两个子元素，包括如下步骤：

[0075] S4.1，计算每个时刻下所有用户的带宽需求总数，按照降序顺序对所有时刻下的带宽需求总数进行排序形成用户的带宽需求队列QN；

[0076] 所述用户的带宽需求队列QN中的每个元素均包含时刻和该时刻下所有用户的带宽需求总数。由于在95计费的规则下，每台服务器都有5％的时刻不被计费，因此在带宽需求调度的初期，每个服务器都有充足的前5％的不被计费的名额，这时候将带宽需求集中起来冲击前5％的免费名额较为合理。因此如果不进行排序则可能会在算法初期遇到一些小的带宽需求，这时会错误的将小带宽需求集中起来，后期遇到大带宽需求时很容易超过前期集中起来的小的带宽需求，将其挤出前5％的不计费的名额，增加用户的成本。

[0077] S4.2，为步骤S4.1中得到的用户的带宽需求队列QN中的每个元素分别设置索引，并初始化索引号r＝1；

[0078] 根据索引号r＝1可以搜索到用户的带宽需求队列QN中的第一个元素，同样地，根据索引号r＝2可以搜索到用户的带宽需求队列QN中的第二个元素，方便依次对用户的带宽需求队列QN中的带宽需求依次处理。

[0079] S4.3，为每个边缘服务器Mi设置一个带宽需求队列 所述带宽需求队列 中的每个元素包含时刻 和该时刻下边缘服务器的带宽需求 两个子元素，根据带宽需求队列 的每个元素的带宽需求的大小对带宽需求队列 进行降序排序以更新带宽需求队列 其中，k表示带宽需求队列 中的元素序号，且1≤k≤T；

[0080] t时刻下边缘服务器的带宽需求 是指卸载到边缘服务器的带宽需求总和，其计算公式为：

[0081]

[0082] S4.4，为每个边缘服务器分别设置权重 和已使用时刻数 两个参数，并将这两个参数均初始化为0；

[0083] 所述已使用时刻数 表示当前边缘服务器Mi已经在多少个时刻被使用过。

[0084] S5，根据索引号r所对应的带宽需求 和该带宽需求 是否位于95计费点内，对索引号所对应时刻td的拓扑网络图 的有向边的属性进行变更，包括如下步骤：

[0085] S5.1，从用户的带宽需求队列QN中找到索引号r对应的带宽需求 表示用户在td时刻下的带宽需求，并将拓扑网络图 中的有向边 的容量变更为 对应的表达式为：

[0086]

[0087] 式中， 表示有向边 的容量，且1≤jd≤N，1≤td≤T。

[0088] S5.2，若带宽需求 在边缘服务器Mi的带宽需求队列 中位于 也即且 则将拓扑网络图 中的有向边 的权重变更为否则将拓扑网络图 中的有向边 的权重变更为权重 对应的表
达式分别为：

[0089]

[0090]

[0091] 式中， 表示有向边 的权重， 表示边缘服务器Mi的带宽需求队列 中元素序号为 的元素的时刻子元素。

[0092] 式(5)设置的原因在于，面对权重相同的边缘服务器，应该将带宽需求尽量调度到带宽上限大的服务器之上，尽量避免由于带宽上限的限制造成的前期大带宽需求分散，增加用户成本。式(4)设置的原因在于，在调度带宽需求使用已经付费的服务器时，应该考虑服务器已经使用过的次数，将带宽需求尽可能调度到使用次数少的服务器上，避免过度使用一个服务器造成的风险。

[0093] S5.3，判断 如果是，将拓扑网络图 中的有向边的容量变更为 否则将拓扑网络图 中的有向边 的流量值赋
值给有向边 的容量，其中， 表示边缘服务器Mi的带宽需求队列 中元
素序号为T×5％处元素的带宽需求子元素，对应的表达式为：

[0094]

[0095]

[0096] 式(6)和式(7)设置的原因在于，如果某台边缘服务器已经有多次带宽需求，在95计费标准下已经需要付费，则应指导新带宽需求尽量接近已付费值，尽量使已付出的成本服务更多的带宽需求，由于边缘服务器到终点连接的容量限制，这时进行的流量分配不会造成额外的服务器成本开销，由于边缘服务器已经付费，至少已经进行了总时刻数乘以5％次的流量调度，本次及后续流量调度也不会消耗边缘服务器不记费的流量调度次数。

[0097] S6，根据步骤S5变更后的拓扑网络图 中有向边的容量和流量计算残差值，利用增广路法和bellman‑ford算法搜索拓扑网络图 中的连通路径，根据残差值再次更新拓扑网络图 的有向边的属性并搜索连通路径，直至拓扑网络图 中不存在连通路径，包括如下步骤：

[0098] S6.1，根据有向边的残差值搜寻拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径；

[0099] 所述残差值是指有向边的容量减去有向边的流量的差值，对应的计算公式为：

[0100]

[0101] 式中，resi表示残差值， 表示起点start到终点end的有向边的容量，表示起点start到终点end的有向边的流量。

[0102] 若有向边的残差值resi>0，则认为该有向边连通，否则不连通，所述连通路径是指路径中的每条边均连通，也即为增广路，所述代价是指连通路径上每条有向边的权重的加和。

[0103] S6.2，计算出步骤S6.1中代价最小的连通路径的残差值resi_min，将该连通路径中所有有向边的流量加上残差值resi_min，将该连通路径中所有有向边的反向边的容量加上残差值resi_min，以分别更新该连通路径中所有有向边的流量和反向边的容量；

[0104] S6.3，判断resi_min>0，如果是，返回步骤S6.1，否则执行步骤S6.4；

[0105] S6.4，将拓扑网络图 中所有有向边 的容量更新为对应的边缘服务器Mi的带宽上限Ci，对应的公式为：

[0106]

[0107] 通过式(8)可以重新修改边缘服务器到终点连接的容量为边缘服务器的带宽上限，进而处理上一步没有调度完的流量。

[0108] S6.5，根据有向边的残差值搜寻更新后的拓扑网络图 中从虚拟节点S到虚拟节点E的连通路径，利用bellman‑ford算法搜索代价最小的连通路径；

[0109] S6.6，计算步骤S6.5中代价最小的连通路径的残差值 将该连通路径中所有有向边的流量加上残差值 将该连通路径中所有有向边的反向边的容量加上残差值 以分别更新该连通路径中所有有向边的流量和反向边的容量；

[0110] S6.7，判断 如果是，返回步骤S6.5，否则执行步骤S6.8；

[0111] S6.8，遍历每一个边缘服务器的带宽需求队列中的元素，判断是否有如果有，执行 否则根据 的值将子元素td和子元素组成的元素对应的插入边缘服务器的带宽需求队列中；

[0112] S6.9，将步骤S6.8更新后的每一个边缘服务器的带宽需求队列中的前T×5％‑1个元素复制到新队列Q′中，根据带宽需求值按照降序顺序对新队列Q′进行排序更新，如果带宽需求值相同，则按照边缘服务器的带宽上限升序排序以更新新队列Q′；

[0113] S6.10，遍历更新后的新队列Q′，将第l个元素所对应的边缘服务器的权重变更为T+N‑l,且l为正整数；

[0114] 步骤S6.10设置的好处在于：首先，如果队列中某一元素的带宽需求值也即流量为0，证明该服务器还有能够冲击带宽需求高峰，以使该需求在所有时刻达到前5％从而不计费的名额，因此希望先将带宽需求引入还有免费名额的服务器，来充分利用95计费下的免费带宽次数，减少边缘服务器成本。其次，如果带宽值不为0，则希望尽量将带宽需求引入这一点带宽值较小的服务器，原因在于这一时刻点为服务器免费带宽名额的最后一点，如果这一点的带宽值较少，则证明当前该服务器对于前5％的不计费的名额还未充分利用，则应该重新组织大流量，来更充分的利用前5％的不计费的名额。

[0115] S6.11，判断拓扑网络图 中虚拟节点S和每个用户Nj之间有向边 中是否都满足有向边 如果是，则将拓扑网络图 中有向边的流量 减去该有向边对应的反向边的流量 得到卸载流量值
即为td时刻用户Nj卸载到边缘服务器Mi的流量值，否则执行步骤S6.12，对应的计算公式为：

[0116]

[0117] 步骤S4.8‑S4.10以及S4.12‑S4.14不断搜索增广路，将增广路上所有有向边的流量增加上残差值，直到不存在增广路，当拓扑网络图 中不存在连通路径也即增广路径时，即表明该时刻即td时刻所有的用户带宽需求都被处理完毕，此时根据拓扑网络图 中边缘服务器和用户之间的连接的流量值，就可以得到该时刻的带宽需求调度方案。用户Nj与所有边缘服务器Mi之间的连接 的流量值 减去反向边的流量值为用户Nj向边缘服务器Mi卸载的带宽需求大小。也就是用户Nj会将
大小的带宽需求卸载到边缘服务器Mi。对用户Nj与所有边缘
服务器的连接计算上述值，就能得到用户Nj的完整的带宽调度方案。对所有用户执行上述操作，就能得到某时刻的完整的带宽调度方案。也就是S6.11所述，S6.11就已经得到调度方案了。

[0118] S7，判断r

[0119] 上述调度方案一定能保证在每个时刻都能调度完所有用户的全部流量需求，并且使边缘服务器的总带宽需求不超过其带宽上限，也即满足 其中， 表示时刻t用户Nj卸载到边缘服务器Mi的带宽需求，当服务时延 时， 因为步骤S4.4中将起点到用户的连接的容量 定为用户的带宽需求 如果当前边缘服务器和用户的拓扑网络图，用户的需求和边缘服务器的带宽上限使得存在一种能满足所有用户需求的调度方案，则上述搜索方式一定能将起点到用户的连接容量全部占满，如果不存在这种调度方案，则应考虑增加服务器等方案，此种情况不在本方案的考虑范围之内。同时，步骤S3.5中边缘服务器到终点的连接的容量 被设置成边缘服务器的带宽上限Ci，这一措施保证了边缘服务器接收的带宽需求不会超过边缘服务器的带宽上限。步骤S3.3中用户和边缘服务器之间容量无限的连接，则保证了在满足用户体验的情况下，带宽需求调度可以自由进行。

[0120] 以下使用原生最大流进行比较，并且通过调整时延阈值K，展示本申请在用户和边缘服务器连接不同的情况下都相比于原生最大流算法拥有更低的服务器成本，从图3中可以看出，即使时延阈值K变化带来了边缘节点和用户节点的连通性改变，本申请带来的服务器成本依然数倍优于基础最大流算法。因此，使用本申请即使客户对于服务质量的要求动态变化，也能在保证客户体验的情况下，数倍降低服务器成本。

[0121] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。