无服务器计算中基于整数非线性规划的大规模工作流放置

《IEEE Access》：Large-Scale Workflow Placement in Serverless Computing Using Integer Nonlinear Programming

　　

无服务器边缘计算已成为一种强大的云框架，能够在用户无需管理底层服务器与边缘设备的前提下执行大规模工作流。研究人员针对将此类工作流部署于大量异构现有服务器与边缘设备上的挑战，旨在最小化用户的货币成本与工作流评估时间。为此，工作流与云节点属性被建模于数学框架中，进而将最优放置问题表述为非线性整数规划（nonlinear integer program）。为同时应对面向更大量云/边缘节点数的扩展问题以及节点属性的分解知识，研究人员提出一种新颖的分解策略。在案例研究中，研究人员展示了该分解方法良好的扩展特性，以及相较简单部署启发式平均改进10%。

研究背景与动机

无服务器计算（serverless computing）作为物联网（Internet of Things, IoT）应用的一种前景广阔的云计算范式，通过函数即服务（Functions-as-a-Service, FaaS）架构将用户与物理服务器解耦。工作流放置（placement problem）指在大量云、雾（fog）、边缘（edge）节点上为工作流各函数选定宿主节点，而调度（scheduling）则针对已部署实例按用户请求进行选择。现有放置方法分为基于机器学习、启发式与基于模型三类：启发式可扩展但次优，已被XFaaS、ECO等实际平台采用；机器学习与基于模型的方法可近优但面临状态表示困难与随节点数指数级增长的计算复杂度，且既往分解研究多关注工作流侧，云侧分解尤其最优放置下的云侧分解研究不足。与此同时，实际成本取决于随机请求序列与运行期工作流选择，精确建模不可行，多数优化方法退而优化延迟、执行时间等代理目标，且在含并行分支、数据依赖与通信成本时缺乏非线性建模能力。鉴于FaaS基础设施正从集中云走向跨供应商地域分布的云-雾-边环境，大规模可扩展最优放置成为迫切问题。该文发表于《IEEE Access》，提出将放置表述为混合整数非线性规划（Mixed-Integer Nonlinear Program, MINLP），并以分层分解策略应对扩展性与隐私/信息局部性挑战。

主要关键技术方法

研究人员首先建立工作流模型：有向无环图（directed acyclic graph, DAG）含n_func函数、n_branches并行分支，函数间后继关系由a_m,m?表示，分支归属由b_c,m表示，函数计算需求R_func,m=RAM_m·t_func,m，并显式建模输入数据d_in、发送数据d_send,m与依赖数据d_data,m。基础设施建模为层级云-雾-边架构，节点按层l、区域/供应商r、区域内序号i索引，延迟L_i,j由Algorithm 1基于curr_region、curr_node、succ_node、succ_region四类导航函数逐层累加头节点链路延迟求得。放置决策变量P_n,m,i∈{0,1}表示工作流n的函数m置于节点i；选择决策H_k,n∈{0,1}表示用户k选工作流n，以确定性选择策略避免两阶段随机规划开销。成本含分支时间T_n,c（函数执行时间x_m,it_func,m与相邻函数跨节点延迟L_i,j双线性项之和的最大值T_n）、货币成本（执行成本C_m,i=p_RAM,iR_func,m+p_data,id_data,m与数据传输双线性成本S_n,m,i），并引入基于利用率的等待成本项，整体构成带权重w₁,w₂,w₃的多目标MINLP，用Gurobi/BARON类求解器处理。为扩展至大规模，提出层级区域/供应商分解，子问题在头节点用局部信息求解，计算量随节点数呈对数增长。

研究结果

SECTION II 工作流与基础设施建模

研究人员将工作流表示为可分解DAG，纳入并行分支、数据依赖与传输成本；基础设施表示为区域/供应商两层（可推广至多层）层级，同区全连、跨区经头节点单链，延迟由Algorithm 1计算。结论：该建模同时支持非线性成本表达与按基础设施区域结构的后续分解。

SECTION III 求解策略

决策变量P_n,m,i与H_k,n在确定性选择下联合优化，避免随机请求建模。目标函数为min w₁·货币成本M + w₂·时间成本B + w₃·利用率成本U，约束含每函数单节点放置、每用户单工作流选择、T_n≥T_n,c、S_n,m,i双线性展开等。因MINLP随节点数指数复杂，研究人员给出分层分解：每层区域解本地子问题，仅向父头节点传递聚合信息。结论：分解后计算需求随云节点数对数增长，且适配去中心化下节点属性隐私/不共享场景。

SECTION IV 案例研究

通过广泛仿真评估扩展性、多目标Pareto权衡及与简单启发式对比，并做参数估计错误的鲁棒性分析。结论：分解法在节点规模增大时求解时间优势明显，平均比简单部署启发式改进10%；Pareto分析显示成本与时间目标间可量化折衷；对部署期参数误估具一定鲁棒性。

SECTION V 结论

研究人员指出，所提MINLP框架与分层分解策略解决了大规模去中心化FaaS中放置问题的扩展性与信息局部性双重缺口，将并行分支、数据依赖、通信与利用率等待成本统一进非线性模型，并以对数级扩展超越启发式约10%均值收益。未来可结合运行期学习细化选择策略与跨供应商定价。

讨论与结论翻译

研究人员总结：本文给出无服务器架构下工作流放置的数学框架，核心贡献为（i）提出可层级分解的MINLP模型，计算需求随节点数对数增长；（ii）在模型中显式纳入工作流选择策略，并引入基于利用率的计算节点与部署等待成本；（iii）集成并行分支、数据依赖与传输成本于非线性框架；（iv）以多目标Pareto分析刻画成本-时间权衡；（v）经仿真与鲁棒性分析验证规模扩展性与实际适用性。该工作填补了云侧分解与含复杂工作流特征的非线性最优放置建模空白，为跨供应商云-雾-边FaaS提供可部署的近优解路径。