大规模物联网网络中多节点分配问题的启发式与元启发式方法

《IoT》：Heuristic and Metaheuristic Approaches for the Multi-Node Allocation Problem in Large-Scale IoT Networks

　　

在物联网(IoT)网络中，当应用需求超出单个节点容量时，便产生多节点分配(MNA)问题，需要将作业分布到多个设备上。该问题在大规模异构环境下具有挑战性，因其涉及在快速扩张的搜索空间中优化资源利用率、带宽消耗与延迟。研究人员提出两种可扩展方法：一种称为需求指数多节点分配(DI-MNA)的贪心启发式，以及将DI-MNA与NSGA-III结合的混合进化算法(NSGA-Hyb)。两种方法均利用有界组合探索与归一化需求指数高效引导搜索。研究人员在10至1000节点规模的物联网网络及不同工作负载下评估上述方法，并与小规模实例上的最优分支定界(B&B)算法比较。结果表明，DI-MNA在小型网络中取得近优解，且随网络规模增长保持低计算成本；在大规模场景中，DI-MNA持续匹配或优于进化方法，相对NSGA-Hyb最高加速达103倍，相对B&B超过104倍。这些发现表明，DI-MNA在大规模物联网网络资源分配中，于解质量、可扩展性与计算效率间提供了有效平衡。

研究背景方面，现代物联网(IoT)应用需求常超越单感知节点或边缘设备的处理、内存与带宽容量，必须将作业策略性分布至多个节点，形成多节点分配(MNA)问题。该问题在大规模异构环境中需同时优化处理资源(R)、带宽(B)与端到端延迟(L)，属NP-hard（经Subset-Sum与3-Partition归约证明为强NP-hard），精确方法在千节点以上不可行。已有文献多聚焦单节点分配，仅少数显式处理MNA且未在千至十千节点循环拓扑上给出可扩展近优方法，存在明确空白。研究人员在《IoT》发表论文，旨在提出兼顾解质量、可扩展性与运行时效的分配方法。

关键技术方法上，研究人员建立标量优化模型，将R、B、L surplus与延迟裕度合成为单一目标函数（式1），以二次罚项抑制过度预留；设计需求指数(DI)对作业三维需求做幅度归一化加权（式6-7），按DI降序调度作业；DI-MNA采用有界组合探索（超参cut_comb_nodes与cut_sol），对每作业用Dijkstra算延迟后枚举≤2节点子集，复杂度O(J·(n log n + C·k))，C、k有界故为多项式。元启发式方面，以NSGA-III为骨干，设NSGA-Enh（每代取最优）与NSGA-Hyb（以DI-MNA解播种种群），用DEAP库selNSGA3与eaMuPlusLambda，种群800、代120、交叉0.9、变异率2/n。基准含精确分支定界(B&B)，网络10–1000节点，轻量（作业:节点=1:10）与重量（1:2）两类负载，各跑10次。

研究结果部分，按原文小节归纳如下。

优化模型与复杂度表征：研究人员给出MNA决策版本Mna-Dec∈NP，并将Subset-Sum与3-Partition归约为其特例，证得MNA为强NP-hard，无伪多项式算法（除非P=NP）；目标函数（式1）以(S_R)²、(S_B)²罚过剩R、B，减L_margin保延迟裕度，约束（式5）硬限R、B、L。

DI-MNA启发式：相较前作MNA-IoT，DI-MNA引入幅度归一化DI排序、推广至任意图（非树）、有界搜索保多项式。算法先Dijkstra算源到各节点延迟，按延迟阈预选，枚举≤cut_sol节点组合，满足约束则算目标并更新最优，分配后节点置不可用。校准实验表明cut_sol=2、cut_comb_nodes=500在千节点下OF改善<0.4%而耗时降两数量级，故定为默认；千节点轻量运行时0.06s，重量0.14s。

NSGA元启发式：NSGA-Enh纯进化，NSGA-Hyb以DI-MNA解初始化种群。编码为每节点1比特，均匀交叉0.9，位翻变异概率2/n，参考点30个。结果显示在10–50节点轻量下NSGA-Enh偶优，但千节点时NSGA-Enh的OF约为DI-MNA的13倍；NSGA-Hyb在大网络OF与DI-MNA相同（Wilcoxon检验无显著差异），说明进化预算未带来质量增益。

实验与结果：轻量配置下，10节点时DI-MNA、NSGA-Hyb、NSGA-Enh与B&B的OF差<1%；50节点起DI-MNA与NSGA-Hyb重合最优；千节点轻量DI-MNA OF优于NSGA-Enh约13倍，重量配置千节点DI-MNA与NSGA-Hyb共收敛于422,360,635，NSGA-Enh达655,197,464。运行时DI-MNA千节点轻量0.06s、重量0.14s，NSGA类约22s（10节点）至数小时（千节点），相对B&B在50节点轻量加速超10⁴倍，相对NSGA-Hyb千节点轻量加速约35倍、重量更高；运行时标准差DI-MNA始终低1–3数量级，具备实时可预测性。

讨论与结论翻译：研究人员指出，MNA因结构异质、目标冲突与组合爆炸而难解；DI-MNA通过尺度感知DI归一化与有界组合探索，在千节点循环拓扑上取得近优解且运行时多项式、低方差。NSGA-Hyb以DI-MNA播种却未超越之，表明在该标量模型下贪心构造已占优，额外进化代仅增开销。该工作填补了千至十千节点规模MNA可扩展近优方法的文献空白，DI-MNA为大规模物联网资源分配在解质量、可扩展性及计算效率间提供了有效平衡，代码与实例已开源。未来方向含显式能耗项、DI-MNA内部并行化及紧近似比推导。