基于动态网络拓扑的副本放置方法及装置

本发明涉及计算机边缘分布式存储，尤其涉及一种基于动态网络拓扑的副本放置方法及装置。

背景技术：

1、随着边缘集群协同计算普及，边端遥感探测数据规模激增，端边协同分布式文件系统成为数据存储共享核心底座，副本放置直接决定边缘数据访问可靠性与传输效率。现有边端副本放置策略存在核心缺陷：无法在动态网络拓扑下同时保障时间窗口内全部请求可达、低访问时延与低副本维护开销，难以适配链路抖动、节点移动、网络分区的边端场景。

2、静态拓扑、热点中心、预测学习、在线贪心四类传统方法均存在短板：静态与热点策略无法适配时变拓扑易产生服务空洞；预测类算法误差传导、边缘部署成本高；常规贪心算法仅单一优化时延，缺少时延上浮可控的副本精简机制，无法对可达性、时延、副本数量做系统性权衡，在线迭代计算与副本同步开销难以管控，无法满足边缘业务sla实时运行需求。

技术实现思路

1、针对现有技术存在的问题，本发明提供一种基于多源雷达数据的三维水平风场反演方法及装置，能够解决有边端副本放置可达性不足、多目标无法协同优化、在线计算开销过大问题，兼顾可达性、时延、副本数量三重指标，贪心迭代架构计算量可控，适配云边端边缘集群动态拓扑实时部署。

2、为实现上述目的，采用如下技术方案：

3、本发明提供一种基于动态网络拓扑的副本放置方法，包括以下步骤：

4、步骤1，构建边端集群时空系统模型：将时间轴离散为连续时隙，划分互不重叠的时间决策窗口，构建每时隙动态拓扑图，采集窗口内各节点文件请求频率、节点剩余存储容量、链路带宽数据；

5、步骤2，全覆盖优先构造初始可行副本集合：筛选窗口全时隙存储容量满足文件存储需求的候选节点，迭代选取加权覆盖请求规模最大、平均访问时延最低的候选节点加入副本集，直至窗口内所有请求均可被副本节点服务，得到满足全请求可达约束的初始副本集合；

6、步骤3，边际时延增益贪心增补副本：遍历未入选候选节点，计算新增该节点带来的窗口加权总时延下降量，每轮选取时延增益最大节点加入副本集并更新服务映射与时延矩阵，无增益时停止增补；

7、步骤4，ϵ松弛约束精简冗余副本：计算窗口加权总时延，依次尝试移除单副节点，对该节点原有服务请求匹配替代副本；若全部请求存在替代副本且删除后总时延不超过(1+ϵ)倍原始总时延，则移除该副本节点，循环迭代至无可精简节点，输出最终副本放置方案、服务映射矩阵与时延矩阵；以时间窗口为粒度统一刻画动态拓扑与时变请求，先保障全请求可达，再优化访问时延，最后通过ϵ松弛可控削减副本数量，同步解决动态边缘网络请求不可达、多目标无法协同优化、副本维护开销过高的问题。

8、优选地，步骤1中，构建的动态拓扑图记为

9、；

10、在时隙内认为网络状态保持不变；v(t)为时隙可通信存储节点集合，为时隙可用链路集合，为节点剩余存储容量集合，为链路可用带宽集合；定义二元变量，表征节点i是否存放文件f副本，二元变量，表征节点i的文件请求由节点j服务，同一时间窗口内副本放置变量保持恒定。

11、优选地，步骤1中，时延模型包括单跳传输时延与传播时延，节点i由副本节点j服务的端到端时延为两节点最短路径所有链路时延之和；窗口加权总时延以各节点时隙请求频率为权重累加全部请求访问时延。

12、优选地，步骤2筛选候选节点的规则为：筛选在当前窗口全部时隙内剩余存储容量均大于目标文件大小的边端设备作为候选节点：，为窗口起点，为时间窗口长度，为窗口内相对时隙偏移量。

13、优选地，步骤2中，选取节点的评判指标包括加权覆盖规模与加权平均时延；加权覆盖规模为节点j可覆盖未覆盖请求按请求频率累加总量，当多个候选节点加权覆盖规模相同时，选择加权平均时延更小的节点加入副本集合。

14、优选地，步骤3中，节点j的时延下降量计算方式为：；

15、每轮选择最大的节点加入结果集，更新被改善请求的服务映射与最优时延；

16、累加所有可被节点降低时延的请求，以请求频率为权重计算原最优时延与节点服务时延的差值总和，越大代表新增该副本降时延效果越显著。

17、优选地，步骤4中，先计算窗口内频率加权总时延 ，随后迭代扫描当前副本集合；对任一副本节点，构造其服务请求集；

18、删除副本节点时，先获取副本节点单独服务的全部请求集合；若请求集合为空直接删除节点；若存在请求无可达替代副本，则保留节点。

19、优选地，步骤4中，计算删除代价，ϵ为预设时延上浮松弛阈值，仅当移除副本节点后的总时延增量满足时，执行副本节点删除操作，其中为移除节点带来的总时延上升量。

20、本发明提供一种基于动态网络拓扑的副本放置装置，用于执行上述基于动态网络拓扑的副本放置方法，包括：

21、建模模块，用于离散时隙与划分时间窗口，构建动态拓扑模型、请求时延模型；

22、覆盖构造模块，用于筛选候选节点，迭代生成全覆盖初始副本可行解；

23、时延优化模块，用于计算各候选节点边际时延增益，贪心增补副本降低总访问时延；

24、副本精简模块，用于基于ϵ松弛约束反向删减冗余副本，输出最终副本放置与服务映射结果。

25、本发明提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述基于动态网络拓扑的副本放置方法的步骤。

26、与现有技术相比，本发明具有如下有益效果：

27、1.动态网络下全请求可达性保障，大幅降低业务失败率。本发明创新性引入时间窗口与时隙离散建模机制，在算法第一阶段优先构建覆盖窗口内全部请求的副本可行解，强制满足各连通片副本最低数量约束，从根源解决传统静态拓扑、热点类副本策略在链路波动、节点断连、网络分区场景下出现的服务空洞、请求不可达、频繁重试问题，显著提升边缘集群数据访问可靠性，适配移动边端、无线遥感等拓扑时变场景。

28、2.实现可达性、时延、副本数量三目标协同均衡优化，适配多类业务sla。现有算法仅单一优化平均时延或命中率，无法兼顾多指标约束。本发明采用“覆盖构造-时延增益增补-ϵ松弛精简”三段式分层优化架构，先保证基础服务能力，再降低访问时延，最后通过可配置ϵ松弛阈值可控放宽时延指标以削减副本数量，能够根据业务对时延容忍度灵活权衡副本存储与同步开销，具备可解释、可调节的多目标权衡能力，适配不同时延、存储成本要求的边缘业务。

29、3.算法计算、副本维护开销可控，边缘侧轻量化部署。本发明全程采用贪心迭代、局部更新的轻量化求解逻辑，无需复杂深度学习模型训练与推理，不存在预测误差传导带来的副本频繁迁移问题；副本精简阶段仅局部重映射删除节点对应的请求服务关系，无需全局重算拓扑与请求匹配，控制面、数据面计算负载低，无需占用大量边缘算力，可在线窗口化持续运行，工程落地难度低，适合资源受限的边端设备集群。

30、4.数学约束完备，兼容边端设备多维度硬件限制。建模阶段统一纳入节点存储容量、链路带宽、时隙连通性、副本数量下限等多重物理约束，在副本选点、增补、删减全流程自动校验存储上限、节点可达性，不会出现副本放置超出设备存储、跨断连链路分配服务的不合理方案，输出的副本放置结果完全贴合边端集群硬件资源限制，方案可行性强。

31、5.服务映射与副本放置联合输出，一站式支撑边缘分布式存储调度。算法同步输出最优副本节点集合、窗口加权时延矩阵、请求-副本服务映射矩阵，不仅给出副本部署位置，还直接提供每时隙全部请求的最优服务节点分配策略，无需额外二次匹配计算，可直接对接边缘分布式文件系统调度模块，简化上层存储业务调度逻辑，降低系统集成开发成本。