大规模嵌入式系统中速度与延迟感知任务分配优化研究：基于ILP和学习型局部搜索算法的解决方案

针对大规模嵌入式系统软件部署中实时性能保障难题，研究人员提出速度与延迟感知任务分配问题(SLAAP)，通过建立整数线性规划(ILP)模型实现小规模实例精确求解，并开发学习型局部搜索算法(LBLS)高效处理工业级规模问题。该研究为航空航天TT&C地面站等实时系统提供了关键部署方案，理论证明与实验验证兼具创新性与实用性。

　　

随着嵌入式系统规模指数级增长，软件部署面临前所未有的复杂性挑战。在航空航天、工业控制等实时性要求严苛的领域，任务分配不仅需要满足计算资源约束，还必须确保任务间通信速度(speed)和延迟(latency)达到软件设计推荐值。传统人工分配方式在应对包含数百个计算单元(computational units)的树状拓扑系统时捉襟见肘，亟需建立系统化的优化方法。

针对这一核心问题，研究人员开展了速度与延迟感知任务分配问题(Speed- and Latency-Aware Assignment Problem, SLAAP)的攻关研究。通过将软件规范建模为有向图（顶点代表任务，弧线表示依赖关系并标注推荐速度s?(u,v)和延迟l?(u,v)）、系统架构描述为无向图（顶点对应计算单元，边记录实际通信参数），构建了兼具理论深度与工程实用性的优化框架。理论层面首次证明即使系统拓扑为简单星型结构，SLAAP仍具NP难特性；实践层面创新性地开发出ILP精确解法与学习型局部搜索(LBLS)启发式算法的双轨解决方案。

关键技术方法包括：1) 通过独立集问题归约证明SLAAP的NP难性；2) 设计包含二元变量x_u,i
和间隙变量g^s
_u,v
/g^l
_u,v
的ILP模型，采用线性化技术处理二次项；3) LBLS算法集成移动(move)、交换(exchange)和随机k链(random-k-chain)三类算子，利用历史高质量解生成初始解。实验采用真实航空航天TT&C地面站数据与人工生成实例，在AMD Ryzen平台验证算法有效性。

研究结果方面：
• 问题建模与复杂性分析：严格定义SLAAP的输入输出规范，通过独立集问题归约证明其计算不可行性，为算法设计奠定理论基础。
• ILP精确解法：建立包含O(|V||C|)变量的线性模型，通过Gurobi求解器实现小规模实例(<50节点)的精确求解，间隙(gap)计算验证方案最优性。
• LBLS启发式算法：针对工业级规模实例(>200节点)，LBLS通过学习历史解分布初始化，结合三类算子实现快速收敛，在32GB内存设备上处理真实TT&C调制案例仅需分钟级耗时。
• 实证验证：对比实验显示ILP在小型实例中达成100%约束满足率，LBLS在大型实例中保持95%以上的服务质量(QoS)，特别在载波信号处理任务分配中降低23%延迟违规。

结论与讨论指出，该研究首次系统解决了嵌入式系统部署中的双目标优化难题：1) 理论贡献在于揭示SLAAP的基础复杂性特征；2) 方法论创新体现为ILP-LBLS混合求解框架，兼顾精度与效率；3) 工程价值通过TT&C案例得到实证，其信号处理任务(如AGC₁
→DDC路径)的分配方案已投入实际应用。未来工作可扩展至异构计算架构和动态负载场景，为工业4.0时代的智能嵌入式系统提供核心调度支持。论文成果发表于《Knowledge-Based Systems》，为实时系统优化领域树立了新的技术标杆。