刘冬宁，曾思敏，陈凌丰，吴诗珏

(广东工业大学 计算机学院，广东 广州，510006)

在地震发生后，地面的基础设施被破坏，导致灾区的通信网络瘫痪。救援工作是紧急、突发、具有时效性的，通信中断会极大地影响救援工作，所以构建稳定的通信网络是灾区救援的重要任务。无人机(unmanned aerial vehicle,UAV)可以跨越地理环境障碍，在救援中完成巡逻、搜索、探测等多项任务，还可以搭载相关设备后作为网络中继，为灾区提供稳定的通信服务。因此利用无人机中继建立临时的通信网络的方式应运而生[1-4]。其中，Liu等[3]充分探讨了在发生灾难时，如何部署无人机基站的网络接入和通信资源分配的方案，证明在灾后利用无人机基站恢复通信的可行性。

然而，通信网络需要有多个中继点不规则地散布在灾区的各个角落。利用无人机建立网络时，因无人机在数量有限的情况下还需要完成多项任务，如巡航、侦察遇难者等，所以在保证通信质量的前提下，如何使用有限的无人机完成中继任务，实现任务的最优分配，是灾区重建通信网络面临的重大挑战。

为解决非饱和式救援期间的多无人机协同最优分配这一关键问题，王峰[5]、王巍等[6]研究如何利用启发式算法解决多无人机协同任务分配问题。除此之外，集中式和分布式的新型算法也被广泛应用于无人机指派中，其中Schwarzrock等[7]基于集中式提出3种基于启发式算法的变形，使其互相补充来解决多架无人机执行协同任务的分配问题。……