《Algorithms》：Greedy Backbone Matheuristics for Hierarchical Functional Connected Dominating Sets in Heterogeneous Drone Networks
编辑推荐：
本文通过层次功能连通支配集（Hierarchical Functional Connected Dominating Set, HF-CDS）问题研究了灾害响应网络中的层次功能无人机部署。该问题联合确定主动无人机位置、由支配无人机构成的连通骨干、功能分配以及支
本文通过层次功能连通支配集（Hierarchical Functional Connected Dominating Set, HF-CDS）问题研究了灾害响应网络中的层次功能无人机部署。该问题联合确定主动无人机位置、由支配无人机构成的连通骨干、功能分配以及支配无人机与非支配无人机之间的层次授权链路。研究人员提出两种具有全局功能需求（global functionality requirements）的HF-CDS变体，二者具有相同的可行结构但设计目标不同：一种为成本最小化模型，另一种为负载均衡模型，后者惩罚非支配无人机过度集中于单个支配无人机的情况。从理论角度，研究人员证明了所提变体的NP困难性（NP-hardness），并讨论了与连通支配、层次包含和骨干负载相关的结构性质。主要算法贡献是一种自适应贪心骨干数学启发式算法（adaptive greedy backbone matheuristic），该算法首先使用多种贪心规则构造候选连通支配骨干，然后在骨干固定的情况下求解一个简化混合整数规划（mixed-integer programming, MIP）模型。这种设计将组合骨干构造任务与功能激活和分配决策分离，能够以较低计算开销生成高质量可行解。在连通几何图上的计算实验将精确公式与所提数学启发式变体进行比较，分析了解质量、运行时间、骨干规模以及部署成本与层次负载均衡之间的权衡。结果表明，所提方法为功能和连通异构无人机网络提供了一种可扩展的优化框架。
论文解读：异构无人机网络中层次功能连通支配集的贪心骨干数学启发式算法
在灾害响应场景中，无人机可为通信中继、视觉检测、搜救和医疗物流提供灵活支持。然而，设计无人机辅助应急网络不仅需要选择飞行平台，还需同时满足覆盖、连通性、异构功能分配以及可靠的层级协调。传统连通支配集（Connected Dominating Set, CDS）可用于构建虚拟骨干，但通常针对同质节点，未结合异构无人机功能、非支配主动无人机以及支配节点与非支配节点间的层次授权。现有无人机部署研究多关注通信覆盖、资源分配或任务分配，缺乏统一图优化模型。为此，研究人员提出层次功能连通支配集（HF-CDS）问题，将主动无人机选择、支配骨干构建、功能分配和层次授权联合建模。
该研究发表于《Algorithms》。研究人员提出了两种全局HF-CDS变体：成本最小化模型与负载均衡模型。前者最小化激活、支配和功能分配成本；后者额外惩罚单个支配无人机周围非支配无人机过度集中。理论上证明了两个变体均为NP-hard，并给出了可行解的结构性质：支配无人机集合包含于主动无人机集合，且构成连通支配集；负载均衡模型的最优解部署成本不优于成本最小化模型，但可换取更低的最大层次负载。实验结果表明，所提数学启发式算法能在较低计算开销下生成高质量可行解，为异构无人机网络提供了可扩展的优化框架。
在方法上，研究人员提出自适应贪心骨干数学启发式算法（AGBM）。主要关键技术包括：第一，使用覆盖贪心规则、度成本规则和功能感知规则构造候选连通支配骨干；第二，通过最短路径修复保证骨干连通性；第三，固定骨干后，求解一个去除根变量、流变量和连通性约束的简化混合整数规划（MIP），以确定剩余激活、功能分配和授权决策；第四，采用移除和交换邻域进行局部改进。实验数据采用合成的连通随机几何图，在单位正方形内随机生成节点，按欧氏距离连边，节点数从20到500，通信半径取200 m、300 m和500 m，功能集包括通信、测绘、救援和医疗，所有实例均由确定性种子生成。
6.1 小型与中型实例：在节点数20至100的小中型网络上，比较精确混合整数线性规划（MILP）与两种模型的求解性能。实验发现，通信半径越小，网络越稀疏，所需HF-CDS节点越多；通信半径增大时，所需支配节点显著减少，部署成本降低。成本最小化模型在多数实例中可以最优求解或获得较小间隙（gap），而负载均衡模型因附加公平性约束更难求解，在较大实例中达到时间限制，但最优性间隙通常低于9%。
6.2 大规模实例：在节点数100至500的网络上，将精确模型（1800秒限制）与AGBM比较。结果显示，AGBM在成本最小化模型上目标值接近精确解，且运行时间大幅缩短；负载均衡模型对精确求解器非常困难，AGBM在多数情况下也能提供可行解，但在部分密集网络中出现较大偏差和更大的骨干规模。诊断分析表明，该现象源于零负载初始化与单节点移除/交换邻域造成的局部最优障碍，而非随机搜索的不利实现。
6.3 负载均衡参数敏感性分析：在代表性中等实例上变化负载均衡惩罚参数λ。随着λ增大，解从低成本、正层次负载配置逐渐转向零负载配置，即更多主动无人机成为支配节点，最大层次负载H下降。中间参数值对应的权衡解在计算上更难验证，最优性间隙相应增大。
讨论与结论部分指出，负载均衡模型通过增加部署成本换取更均匀的层次负载，在灾害响应中可降低通信拥塞、协调负担和局部故障脆弱性。AGBM在成本最小化模型上表现突出，但负载均衡模型需进一步改进局部搜索。研究结论可概括为：本文提出了HF-CDS问题，建立了两种混合整数线性规划模型，证明了其NP困难性，并提出AGBM算法；实验表明，精确模型适用于中小规模网络，而AGBM能以显著更低的时间提供高质量可行解，是可扩展且可解释的求解框架。未来研究可引入负载感知局部搜索算子、有效不等式、鲁棒或随机扩展、多周期动态模型以及更真实的无线信道建模。
