随着科学技术的发展，通信技术也急速发展，成为了人们生活中不可或缺的一部 分。地面通信基站存在无法快速部署、地形局限性大、成本高等问题，而无人机具有 易于部署、高机动性和成本低等特点，使用无人机搭载微型基站能够弥补地面通信基 站存在的不足。但是，使用无人机作为空中通信平台也面临一些挑战，单无人机在实 时性、可靠性等方面存在不足，通常需要使用多无人机协同完成通信任务，多无人机 协同完成任务时，如何对其进行合理的目标分配，是亟待解决的难题。本文研究了两 种通信场景中无人机的目标分配算法。在多无人机协同覆盖区域中的目标场景中，提 出了基于密度的覆盖算法持续为目标提供通信服务，常被用于灾区救援；针对无人机 为多地提供通信服务的场景，提出将贪心算法与杂草繁殖机制融入单亲遗传算法，常 被用于辅助物联网进行数据收集。具体的研究内容如下：

      1、在多无人机协同覆盖目标点的问题研究中，针对传统覆盖算法因随机选取覆 盖中心，对邻域搜索能力弱导致覆盖率低的问题，本文提出了一种基于密度的覆盖算法。算法选取密度最大的目标点作为初始覆盖中心，采用均值中心化手段对覆盖中心进行优化，避免目标点因处于无人机覆盖边缘而导致通信质量差。此外，该算法对覆盖中心增加了两次扰动过程，扩大了对目标的搜索能力。实验证明，本文所提算法的覆盖率比传统算法有了显著提高，验证了该算法具有更强的鲁棒性和更高的覆盖率。针对算法中无法保证无人机连通性的问题，本文提出将基于密度覆盖算法与“自顶向下”的思想结合的算法。该算法首先使用三圆环确定初始覆盖中心，将生成单架无人机与两架无人机时的单机覆盖率进行比较，选用单机覆盖率更高的位置作为覆盖中心。然后设置冗余无人机，最后将未起到连通作用且覆盖率最低的无人机移除，增强了算法对邻域的搜索能力，能有效提高算法性能。实验证明，在无人机总覆盖面积达到地图面积 1/4 时，该算法对目标点能达到 80%以上的覆盖率，高于传统算法；

        2、在多无人机为多地提供通信保障服务的问题研究中，针对遗传算法中编码复杂、求解结果过于依赖初始种群的问题，本文提出将贪心算法与杂草繁殖机制融入单亲遗传算法。该算法使用了两段式染色体编码方式简化编码，利用贪心算法生成部分初始种群，有效提升了初始种群质量。另外，使用杂草繁殖机制生成后代以保证种群多样性，且在迭代后期采用局部变异算子，防止求解过早陷入局部最优。通过对比实验，证明了本文所提算法在求解该问题时的有效性。

With the development of science and technology, communication technology has also developed rapidly and has become an indispensable part of people's lives. Ground communication base stations have problems such as inability to deploy quickly, terrain limitations and high cost, while UAV has the characteristics of easy deployment, high mobility and low cost, and the use of UAV to carry micro base stations can make up for the shortcomings of ground communication base stations. However, the use of UAV as an air communication platform also faces some challenges, single UAV in real-time, reliability and other aspects of deficiencies, usually need to use multi-UAV collaborative completion of communication tasks, when multi-UAV collaborative completion of tasks, how to reasonably assign targets to it, is an urgent problem to be solved. This paper studies the target allocation algorithm of UAVs in two communication scenarios. In the target scenario in the multi-UAV collaborative coverage area, a density-based coverage algorithm is proposed to continuously provide communication services for the target, which is often used for disaster rescue. Aiming at the scenario where multi-UAV provide communication services for multiple places, it is proposed that the greedy algorithm and weed propagation mechanism be integrated into the single-parent genetic algorithm, which is often used to assist the Internet of Things for data collection. The specific research content is as follows:

1. In the research on the problem of multi-UAV collaborative coverage of target points, this paper proposes a density-based coverage algorithm for the problem that the traditional coverage algorithm has low coverage due to random selection of coverage center and weak neighborhood search ability. The algorithm selects the target point with the highest density as the initial coverage center, and uses the mean centralization method to optimize the coverage center to avoid poor communication quality caused by the target point being at the edge of UAV coverage. In addition, the algorithm adds two disturbance processes to the coverage center, expanding the search capability of the target. Experiments show that the coverage of the proposed algorithm is significantly improved compared with the traditional algorithm, which verifies that the algorithm has stronger robustness and higher coverage. Aiming at the problem that UAV connectivity cannot be guaranteed in the algorithm, this paper proposes an algorithm that combines the density-based coverage algorithm with the idea of "top-down". The algorithm first uses three rings to determine the initial coverage center, compares the single-machine coverage of the generated single UAV with the single-machine coverage of two UAVs, and selects the location with higher single-aircraft coverage as the coverage center. Then, redundant drones are set up, and finally the drones that do not play a communication role and have the lowest coverage are removed, which enhances the search ability of the algorithm to the neighborhood and can effectively improve the performance of the algorithm. Experiments show that when the total coverage area of the UAV reaches 1/4 of the map area, the algorithm can reach more than 80% coverage of the target point, which is higher than that of the traditional algorithm.

2. In the research on the problem of multi-UAV providing communication support services for multiple places, aiming at the problem that the genetic algorithm has complex coding and the solution result is too dependent on the initial population, this paper proposes to integrate the greedy algorithm and weed breeding mechanism into the single-parent genetic algorithm. The algorithm uses the two-segment chromosome coding method to simplify the coding, and uses the greedy algorithm to generate part of the initial population, which effectively improves the quality of the initial population. In addition, the weed propagation mechanism is used to generate generations to ensure population diversity, and local mutation operators are used in the late iteration to prevent the solution from falling into local optimization prematurely. Through comparative experiments, the effectiveness of the proposed algorithm in solving this problem is proved.

[1] Fahlstrom P.G, Gleason T.J. 无人机系统导论[M]. 北京：电子工业出版社, 2003.
[2] 马向玲, 雷宇曜. 有人/无人机协同作战关键技术[J]. 火力与指挥控制, 2012, 37(1):78-81.
[3] Rabbath C A, Gagnon E, Lauzon M. On the Cooperative Control of Multiple Unmanned Aerial Vehicles[J]. ieee canadian review, 2004.
[4] 王焱. 有人/无人机协同作战[J]. 电讯技术, 2013, 53(9):1253-1258.
[5] 作战技术超前数十年——美空军六大课题揭密[EB/OL]. 2002. [2014-1-6] .
[6] Yong Z, Rui Z, Teng J L. Wireless Communications with Unmanned Aerial Vehicles: Opportunities and Challenges[J]. IEEE Communications Magazine, 2016, 54(5):36-42.
[7] Zeng Y, Zhang R, Lim T J. Throughput Maximization for UAV-Enabled Mobile Relaying Systems[J]. IEEE Transactions on Communications, 2016:4983-4996.
[8] Mozaffari M , Saad W , Bennis M , et al. Efficient Deployment of Multiple Unmanned Aerial Vehicles for Optimal Wireless Coverage[J]. IEEE Communications Letters, 2016, 20(8):1647-1650.
[9] Lyu J, Yong Z, Rui Z. Cyclical Multiple Access in UAV-Aided Communications: A Throughput Delay Tradeoff[J]. IEEE Wireless Communications Letters, 2016, 5(6):600-603.
[10] Sujit P B, Sinha A, Ghose D. Multi-UAV Task Allocation using Team Theory[C]// European Control Conference Cdc-ecc 05 IEEE Conference on Decision & Control. IEEE, 2006.
[11] Sujit P B, Sinha A, Ghose D. Multiple UAV task allocation using negotiation[C]// 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006. ACM, 2006:471.
[12] Yan J, Minai A A, Polycarpou M M. Cooperative real-time search and task allocation in UAV teams[C]// Decision and Control, 2003. Proceedings. 42nd IEEE Conference on. IEEE, 2004.
[13] Ben-Asher Y, Feldman S, Gurfil P, et al. Distributed Decision and Control for Cooperative UAVs Using Ad Hoc Communication[J]. IEEE Transactions on Control Systems Technology, 2008, 16(3):511-516.
[14] Dionne D, Rabbath C A. Multi-UAV Decentralized Task Allocation with Intermittent Communications: the DTC algorithm[C]// American Control Conference. IEEE, 2007.
[15] Mozaffari M, Saad W, Bennis M, et al. Drone Small Cells in the Clouds: Design, Deployment and Performance Analysis[J]. IEEE, 2015.
[16] Freitas D, Pignaton E, Heimfarth, et al. Sensors, Vol. 13, Pages 12903-12928: Cooperation among Wirelessly Connected Static and Mobile Sensor Nodes for Surveillance Applications. 2013.
[17] Weber A. The Theory of the Location of Industries[J]. mat.sb, 1929.
[18] Hotelling H. Stability in competition[J]. Economic Journal,1929,39(1):41~57.
[19] Hakimi, S. L. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph[J]. Operations Research, 1964, 12(3):450-459.
[20] Hourani A, Kandeepan S, Jamalipour A. Modeling Air-to-Ground Path Loss for Low Altitude
Platforms in Urban Environments[C]// GLOBECOM'14, Satellite & Space Communication. IEEE, 2014.
[21] Kalantari E, Yanikomeroglu H, Yongacoglu A. On the Number and 3D Placement of Drone Base Stations in Wireless Cellular Networks[C]// 2016 IEEE 84th Vehicular Technology Conference (VTC-Fall). IEEE, 2017.
[22] Hatem, A, Fayed, et al. Erratum to: A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems[J]. Computational Optimization&Applications, 2013.
[23] Lyu J, Yong Z, Rui Z, et al. Placement Optimization of UAV-Mounted Mobile Base Stations[J].
IEEE Communications Letters, 2016, PP(99):1-1.
[24] 周毅, 马晓勇, 郜富晓,等. 基于深度强化学习的无人机自主部署及能效优化策略[J]. 物联网学报, 2019(2):9.
[25] Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures[J]. Omega, 2006, 34(3):209-219.
[26] 俞庆生, 林冬梅, 王东. 多旅行商问题研究综述[J]. 价值工程, 2012, 31(2):3.
[27] Ali A I, Kennington J L. The asymmetric M -travelling salesmen problem: A duality based branch and-bound algorithm [J]. Discrete Applied Mathematics, 1986, 13(2-3):259-276.
[28] Gavish B, Srikanth K. An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems[J]. Operations Research, 1986, 34(5):698-717.
[29] Wang Y, Chen Y, Lin Y. Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem[J]. Computers & Industrial Engineering,2017 (106): 105-122.
[30] A H Z, A M S, D W P B C. A comparative study of improved GA and PSO in solving multiple traveling salesmen problem[J]. Applied Soft Computing, 2018, 64:564-580.
[31] Venkatesh P, Singh A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing Journal, 2015, 26:74-89.
[32] Kencana E N, Harini I, Mayuliana K. The Performance of Ant System in Solving Multi Traveling Salesmen Problem[J]. Procedia Computer Science, 2017, 124:46-52.
[33] 周辉仁, 唐万生, 王海龙. 基于差分进化算法的多旅行商问题优化[J]. 系统工程理论与实践, 2010(8):6.
[34] 赵静, 曾建潮. 无线多媒体传感器网络感知模型与数量估计[J]. 软件学报, 2012, 23(8):11.
[35] 郭新明, 赵蔷, 蔡军伟. 基于覆盖概率模型的无线传感器网络覆盖算法[J]. 中国科技论文, 2013, 8(4):5.
[36] Wan P J, Xu X, Wang Z, Wireless coverage with disparate ranges[C]// Proceedings of the 12th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2011, Paris, France, May 16-20, 2011. ACM, 2011.
[37] Chen J, Zhang L, Kuo Y. Coverage-Enhancing Algorithm Based on Overlap-Sense Ratio in Wireless Multimedia Sensor Networks[J]. IEEE Sensors Journal, 2013, 13(6):2077-2083.
[38] Kumar S, Lai T H, Posner M E, et al. Maximizing the Lifetime of a Barrier of Wireless Sensors[J]. Mobile Computing, IEEE Transactions on, 2010, 9(8): p.1161-1172.
[39] Kumar S, Lai T, Arora A K. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007.
[40] 张洋, 刘聪锋. 无人机对地攻击目标分配问题研究[J]. 军民两用技术与产品, 2017(6):3.
[41] 陈侠, 乔艳芝. 无人机任务分配综述[J]. 沈阳航空航天大学学报, 2016, 33(6):7.
[42] Rasmussen S, Chandler P, Mitchell J W, et al. Optimal vs. Heuristic Assignment of Cooperative Autonomous Unmanned Air Vehicles. 2003.
[43] 叶媛媛, 闵春平, 沈林成,等. 基于满意决策的多 UAV 协同目标分配方法[J]. 国防科技大学学报, 2005.
[44] 陈英武, 方炎申, 李菊芳,等. 卫星任务调度问题的约束规划模型[J]. 国防科技大学学报, 2006, 28(5):7.
[45] Ekelin C, Jonsson J. Solving Embedded System Scheduling Problems using Constraint Programming[J]. Dept of Computer Engineering Chalmers University of Technology, 2000.
[46] Stone H S. Multiprocessor Scheduling with the Aid of Network Flow Algorithms[J]. IEEE Transactions on Software Engineering, 2006.
[47] Levchuk G M, Levchuk Y N, Pattipati K R, et al. Mapping Flows onto Networks to Optimize Organizational Processes[J]. mapping flows onto networks to optimize organizational processes,
2005.
[48] Wu X, Bai W, Xie Y, et al. A hybrid algorithm of particle swarm optimization, metropolis criterion and RTS smoother for path planning of UAVs[J]. Applied Soft Computing, 2018, 73:735-747.
[49] Zhen Z, Xing D, Gao C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm[J]. Aerospace Science & Technology, 2018, 76:402-411.
[50] 刘光远, 贺一, 温万惠. 禁忌搜索算法及应用[M]. 科学出版社, 2014.
[51] 周爱武, 于亚飞. K-Means 聚类算法的研究[J]. 计算机技术与发展, 2011, 21(2):4.
[52] Toregas C, Toregasswain R, Revelle C, et al. The location of emergency service facilities[J]. Operations Research, 1971, 19(6):1363-1373.
[53] 周银平, 李卫国. Kmeans 聚类算法及其评价方法和改进方向的研究[J]. 数字化用户,2019.
[54] 邓林培. 经典聚类算法研究综述[J]. 科技传播, 2019, 11(5):3.
[55] Papadimitriou C H. The Euclidean travelling salesman problem is NP-complete[J]. Theoretical Computer Science, 1977, 4(3):237-244.
[56] 王光, 林国宇. 改进的自适应参数 DBSCAN 聚类算法[J]. 计算机工程与应用, 2020, 56(14):7.
[57] Dorigo M, Gambardella L M. Ant colonies for the travelling salesman problem[J]. BioSystems, 1997(2):43.
[58] Goss S, Aron S, Deneubourg J L, et al. Self-organized shortcuts in the Argentine ant[J]. Naturwissenschaften, 1989, 76(12): 579-581.
[59] 刘雪豪. 基于改进蚁群算法的多无人机协同航迹规划研究[D].郑州航空工业管理学院,2020.
[60] Eberhart R C, Kennedy J. A New Optimizer Using Particle Swarm Theory[C]// Micro Machine and Human Science, 1995. MHS '95. Proceedings of the Sixth International Symposium on. 1995.
[61] Valle Y D, Venayagamoorthy G K, Mohagheghi S, et al. Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(2):171-195.
[62] 任子武, 伞冶. 自适应遗传算法的改进及在系统辨识中应用研究[J]. 系统仿真学报, 2006, 18(1):4.
[63] 赵新超, 郭赛. 遗传算法求解多旅行商问题的相对解空间分析[J]. 智能系统学报, 2018, 13(5):9.
[64] 邓丽芳. 遗传算法在旅行商问题中的应用研究[D].广东工业大学,2012.
[65] 胡士娟, 鲁海燕, 黄洋,等. 求解寻址多旅行商问题的改进单亲遗传算法[J]. 东北师大学报：自然科学版, 2019, 51(4):8.
[66] Carter A E, Ragsdale C T. A new approach to solving the multiple traveling salesperson problem
using genetic algorithms[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006.
[67] Brown E C, Ragsdale C T, Carter A E. A GROUPING GENETIC ALGORITHM FOR THE MULTIPLE TRAVELING SALESPERSON PROBLEM[J]. International Journal of Information Technology & Decision Making, 2007, 6(02):333-347.
[68] Yuan S, Skinner B, Huang S, et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European Journal of Operational Research, 2013, 228(1):72-82.
[69] Alok, SinghAnurag, Singh, et al. A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]. Soft Computing-A Fusion of Foundations,Methodolo gies&Applications, 2009.
[70] Liu W, Li S, Zhao F, et al. An ant colony optimization algorithm for the Multiple Traveling Salesmen Problem[C]// IEEE Conference on Industrial Electronics & Applications. IEEE, 2009.
[71] Soylu B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J]. Computers & Industrial Engineering, 2015, 90(DEC.):390-401