(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111042196.7 (22)申请日 2021.09.07 (71)申请人 武汉大学 地址 430072 湖北省武汉市武昌区珞珈山 武汉大学 (72)发明人 周睿婷　韩紫怡　庞金龙　 (74)专利代理 机构 武汉科皓知识产权代理事务 所(特殊普通 合伙) 42222 代理人 肖明洲 (51)Int.Cl. H04W 72/04(2009.01) H04W 72/12(2009.01) G06N 20/00(2019.01) G06K 9/62(2006.01) G06F 30/27(2020.01)G06F 111/04(2020.01) (54)发明名称 一种面向边缘无线网络中UDL任务的在 线调 度系统及方法 (57)摘要 本发明公开了一种面向边缘无线网络中UDL 任务的在线调度系统及方法， UDL任务的训练数 据是由每个跨区域站点收集并提供的， 且UDL任 务均匀地从每个跨区域站点中选取足量的训练 数据进行模 型训练以保证模型的无偏性。 本发明 能够在UDL任务在线到达的情况下(不知道任何 未来任务信息)， 对其进行调度， 在最小化响应延 迟(训练时间)的同时降低边缘无线网络中跨区 域分布站点间昂贵的带宽成本。 边缘机器学习系 统可根据本发明确定UDL任务的部署和数据传 输， 以谋得最小化总训练成本。 本发明结合了线 性规划建模， 经典的贪心算法等， 从理论上证明 了其正确性和多项式运行时间。 本发 明的方法较 于功能相同的算法更高效。 权利要求书3页 说明书9页 附图3页 CN 113891466 A 2022.01.04 CN 113891466 A 1.一种面向边缘无线网络中UDL任务的在线调度系统， 其特征在于： 包括边缘分布式机 器学习子系统、 站点、 UDL任务； 所述边缘分布式机器学习子系统， 由R个跨区域分布的站点组成； 所述站点， 为一个边缘服务器或一个小型边缘云； 每个站点r能够提供 数量的k类资 源， 并通过无线网络与其它站点连接通信， 站点r与 站点r′之间的单位带宽成本为qrr′； 每个 站点r收集并为UDL任务i提供 训练数据块， 每一数据块的大小为θiMB； 其中， 资源类型的 数量记为K， 每一资源类型k∈[k]； 表示站点r为任务i收集的训练数据块的数量， 即初始 的训练数据块数量； 所述UDL任务， 每个UDL任务i在ai时隙到达并请求训练； 该任务申请一个计算节点或参 数服务器节点需要占用 或 单位的k类资源； 每个计算节点的处理能力为Pi； 每个数据块 需要训练Ei个轮次； 每时隙一个计 算节点与一个 参数服务器节点参 数交换的大小为 λiMB； 其 中， 表示任务申请一个计算节点需要占用的k类资源数量； 表示任务申请一个计算参 数服务器节点需要占用的k类资源数量。 2.一种面向边缘无线网络中UDL任务的在线调度 方法， 其特征在于： 首先将响应延迟转 化为一个非减成本 函数 表示UDL任务i的完成时间， ai表示任务i的到达时间； 并 将UDL任务i的训练总带宽成本定义为其数据传输成本和参数交换成本之和 Bi， 将总训练成 本最小化问题建模为混合整数非线性问题 然后， UDL任务 到达后在每个时隙计算确定该时隙执行时间窗口、 训练数据量、 计算节点和 参数服务器节 点的部署数量和位置以及数据传输； 其中， 上式中， T为系统中时隙数量， 每一时隙t∈[T]； R为系统中站点数量， 每一站点r∈[R]； qrr′为站点r与站点r ′之间的单位带宽成本； θi为任务i单个数据块的大小； 为在时隙 t， 任务i从站点r传输到站点r ′的数据块 的数量； λi为任务i每时隙一个计算节点与一个参 数服务器节点参数交换的大小； 为在时隙t， 任务i在 站点r部署计算节点的数量； 为在时隙t， 任务 i是否在站点r部署参数服 务器节点； 的约束条件为： 上式中， I为系统中任务数量， 每一任务i∈[I]； 为站点r为任务i收集的训练数据块 的数量； Pi为任务i单个计算节点的处理能力； 表示任务申请一个计算节点需要占用的k权　利　要　求　书 1/3 页 2 CN 113891466 A 2类资源数量； 表示任务申请一个计算参 数服务器节点需要占用的k类资源数量； 为站点 r中k类资源的容 量； K为站点资源类型的数量， 每一资源类型k∈[k]。 3.根据权利要求2所述的面向边缘无线网络中UDL任务的在线调度方法， 其特征在于： 所述UDL任务到达后在每个时隙计算确定该时隙执行时间窗口、 训练数据量、 计算节点和参 数服务器节点的部署数量和位置以及数据传输； 具体实现包括以下子步骤： 步骤1： 从t＝0， 系统开始进行任务训练； 步骤2： UDL任务在线到 达； 步骤3： 收集当前时隙新到 达的任务， 将其加入未完成任务 集合[Ja]； 步骤4： 对集合[Ja]中的每一任务进行预处理， 不考虑其余任务的情况下得到成本最小 的暂定调度方案； 具体实现包括以下子步骤： 步骤4.1： 枚举任务每 个时隙分配部署计算节点的数量； 步骤4.2： 对于已确定计算节点部署总数量的单时隙问题， 将任务计算节点和参数服务 器节点部署问题建模为整数线性 规划问题； 步骤4.3： 枚举参数服务器节点可能部署的位置并根据部署指标贪心地确定每个站点 部署计算节点的数量； 步骤4.4： 在部署不变的情况下， 计算出时隙t所有站点的训练数据量 如果存在站 点本地剩余训练数据量不满足所分配的训练数据量时， 就会发生数据传输； 将最小化数据 传输所需带宽成本的子 问题构建为整数线性规划问题， 并按照带宽成本最小的原则， 贪心 地从其余训练数据充足的站点收集数据； 步骤5： 根据优先级指标计计算集合[Ja]中每个任务的优先级并根据优先级对未完成任 务排序； 按序确定任务 最终部署方案， 包括： 资源充足时， 则执 行下述步骤6； 资源不足时， 优先级低的任务分别计算迁移计算节点和参数服务器节点的部署的成本 以及延后训练的成本， 比较得到成本较小的方案并更新该任务的部署 和 其中， 表示在时隙t， 任务i在站点r部署计算节点的数量； 表示在时隙t， 任务i是否在站 点r部署参数服 务器节点； 步骤6： 根据每个站点部署的计算节点的数量， 计算出时隙t所有站点的训练数据量 如果存在站点本地剩余训练数据量不满足所分配的训练数据量 时， 就会发生数据传 输； 将最小化数据传输所需带宽成本的子 问题构建为整数线性规划问题， 并按照带宽成本 最小的原则， 贪心地从其 余训练数据充足的站点收集数据； 步骤7： 通过任务的剩余数据量 判断任务是否 完成全部训练； 若是， 则移出集 合[Ja]， 并执行下述步骤8； 若否， 则执 行下述步骤8； 步骤8： 判断集 合[Ja]中的任务是否均确定调度方案； 若是， 则t＝t+1， 并回转执 行下述步骤2； 若否， 则回转执 行步骤5， 计算下一个序号任务的调度方案 。权　利　要　求　书 2/3 页 3 CN 113891466 A 3