多任务冗余无人机群智感知中的真实反向拍卖机制

《Journal of King Saud University Computer and Information Sciences》：Truthful reverse mechanism for multi-task-redundancy allocation in UAV crowdsensing

　　

配备多种传感设备和先进计算能力的无人机（UAV）能够提供广泛的服务。区域内需要服务的位置被称为兴趣点（PoI）。与边缘计算相比，无人机凭借其高机动性能够为PoI提供更优质的服务交付。本文考虑通过群智感知招募无人机为PoI提供服务。本工作的新颖之处在于引入了多任务冗余模型，其中每个任务包含冗余属性，指示完成该任务所需的无人机数量。提出了一种反向拍卖定价模型，无人机提交其成本，系统确定相应的奖励。研究了无人机群智感知中的多任务冗余分配问题。首先提出了一种最优反向拍卖机制并证明其具有真实性。鉴于分配问题是NP-hard的，开发了一种高效的反向拍卖机制。所提出的机制被证明能够实现真实性，从而推动系统趋向均衡。此外，所提出的机制还被证明能够实现个体理性、参与者主权和计算效率。此外，分析了所提出分配算法的近似比。实验结果表明，所提出的机制在动态环境中表现有效。

**研究背景与问题**

配备先进计算能力和多种高清晰度传感设备的无人机（UAV）能够满足广泛的任务需求。服务区域内需要关注的每个位置被定义为"兴趣点"（PoI），例如公交站牌、公园公共设施和农作物区域。每个PoI同时需要计算资源和感知服务。当采用移动边缘计算（MEC）为PoI提供服务时，需要在每个位置部署边缘服务器和传感设备，成本高昂且计算资源无法根据PoI需求的动态变化进行调整。无人机群智感知提供了解决这些挑战的合适方案，无人机可以快速部署到不同位置以响应动态的PoI需求。然而，无人机面临更高的服务成本和能量约束限制，难以设定统一奖励，因此将服务定价问题建模为拍卖框架下的反向拍卖模型。此外，环境数据采集常受噪声、传感器不精确性和外部干扰影响，依赖单架无人机进行数据采集可能导致显著测量误差或任务失败，因此需要多任务冗余模型——每个任务关联冗余属性，指定完成该任务所需的无人机数量，通过多架无人机协同执行同一任务促进数据融合和交叉验证，增强感知可靠性和整体数据质量。研究人员的目标是最大化群体效率，即PoI总价值与无人机总成本之差。无人机可能策略性地虚报成本以提高自身效用，因此分配机制必须实现真实性。VCG机制被公认为最优的真实性机制，但并非为反向拍卖场景设计，因此需要基于VCG机制开发最优反向拍卖机制。由于多任务冗余分配问题属于NP-hard，难以在合理时间内获得最优分配，因此需要设计高效的机制。

**关键技术方法**

研究人员提出了VCG-MTRA最优反向拍卖机制作为理论基准，通过调用最优求解器求解整数规划（IP-MTRA）问题并根据VCG原理重新推导支付规则。针对NP-hard特性，开发了ERAM-MTRA高效机制，包含ERAM-ALLOC分配算法（基于价值密度排序和单位成本非递减排序的贪心分配）和ERAM-REWARD奖励算法（基于二分搜索的关键支付计算）。实验采用CPLEX求解最优群体效率，在C++平台使用Visual Studio 2022进行仿真，结果取50次独立运行的平均值。对比方法包括Greedy-MMAPB、BFCM-HCO、FCFS和LCS。

**研究结果**

**不同PoI数量下的性能**：执行时间随PoI数量增加而增长，VCG-MTRA在仅6个PoI时执行时间超过半小时，不适合实际分配场景。ERAM-MTRA的群体效率接近VCG-MTRA并优于其他机制，最优解与ERAM-MTRA解之间的百分比差距最小为6.73%，最大为8.84%。ERAM-MTRA服务的PoI百分比接近VCG-MTRA且优于其他机制。ERAM-MTRA的无人机获胜者百分比较VCG-MTRA低但高于其他机制。VCG-MTRA的无人机效用高于ERAM-MTRA，因后者竞争更激烈导致奖励降低。ERAM-MTRA的平均资源利用率优于其他机制。

**不同无人机数量下的性能**：执行时间随无人机数量增加而增长，ERAM-MTRA快于VCG-MTRA。群体效率随无人机数量增加而增长，ERAM-MTRA接近VCG-MTRA并显著优于其他机制。ERAM-MTRA服务的PoI百分比显著高于其他机制。无人机获胜者百分比随无人机总数增加而下降，ERAM-MTRA接近VCG-MTRA并优于其他机制。ERAM-MTRA的无人机效用低于VCG-MTRA。

**不同最大需求无人机数量下的性能**：执行时间随最大需求无人机数量增加而增长。群体效率随最大需求无人机数量增加而增长，ERAM-MTRA总体效率显著高于其他算法。服务的PoI百分比随最大需求无人机数量增加而下降，ERAM-MTRA服务更多PoI。无人机获胜者数量随最大需求无人机数量增加而增长。

**非理想环境测试**：在包含20%通信失败概率、不确定信道条件、无人机故障和定位误差的环境中，ERAM-MTRA相比替代方案需要更少执行时间并实现更高群体效率，表明其在非理想环境中表现有效。

**超大规模仿真**：在PoI数量为1000至1500、无人机数量为1500的场景中，ERAM-MTRA执行速度极快并实现最高群体效率，表明其对大规模分配环境具有高度适应性。

**讨论与结论**

研究人员证明了VCG-MTRA满足个体理性，在无人机声明较低成本时具有真实性，但其真实性在一般情况下无法保证，且需要多次求解最优分配导致执行时间过长，因此应视为最优基准而非实际可用的真实性机制。ERAM-MTRA被证明满足个体理性、参与者主权和真实性，其分配算法具有单调性，奖励算法实现关键支付，近似比为?·?/(??1)·T_maxd_max/(T_mind_min)，时间复杂度为O(U(log₂σ_sys(Ulog₂U+PT_maxω_maxUR)))。研究结论部分翻译如下：本文研究了无人机群智感知中的多任务冗余分配问题。研究人员考虑了每个PoI可能有多个任务需要完成的情况，提出了一种新颖的多任务冗余模型，其中每个任务关联冗余属性，指定完成所需的无人机数量。服务定价问题在拍卖框架下建模，引入了反向拍卖模型，无人机向系统提交成本，系统随后确定相应奖励。提出了一种最优反向拍卖机制并证明其具有真实性。随后提出了一种高效反向拍卖机制，该机制具有真实性、个体理性、参与者主权和计算效率，并分析了所提出高效算法的近似比。大量实验验证了所提出机制的效率和有效性。资源模型通过多维资源类型解决了任务需求的异构性。未来工作可通过纳入更细粒度的区分（如传感器精度、数据处理能力和任务优先级）进一步增强模型对复杂场景的适用性，并在真实无人机群智感知数据集上评估模型性能以进一步验证所提出机制的实际适用性。