摘要：如何均衡的利用有限的时隙资源最大化无人机之间的通信能力，是无人机通信领域的关键问题。本文研究了考虑最大时隙约束的网络通信能力最大化问题，在将时隙资源离散化后，构建了0-1整数规划模型，用以决策无人机在任意时隙资源下的收发状态。针对大规模0-1整数规划模型，设计了自适应大邻域搜索算法。本文进行了算例测试，验证了本文所提快速求解算法的正确性，并验证了自适应大邻域算法在求解大规模问题时的有效性。

关键词：无人机通信；时隙资源；网络通信能力；自适应大邻域搜索算法

1.引言

初级用户或对安全性要求较高的应用通常采用单独飞行和单一遥控的模式，即单飞单控模式。但是，这种模式无法实现多个无人机的协同操作和分工（Su et al.， 2023）。随着通信、自主导航和协同系统的发展，单飞单控模式逐渐演变为无人机组网模式，实现更高效的协同工作和任务协调（ Javaid et al.， 2023）。

无人机组网涉及多个技术和应用层面。关键问题包括高效的通信网络建立、任务分配、路径规划、资源分配等（ Han and Baek， 2021; Zhang and Xing， 2020;）。多波束定向天线技术在无人机组网中具有重要作用，可以减少信号干扰、扩大传输范围和提高数据传输速率（Gupta et al.， 2016）。资源分配策略如时分多址（TDMA）是关键，需要考虑时隙规划和时隙分配问题。

时隙资源分配问题包括设计时隙分配协议和全局时隙分配。前者主要基于局部信息，用于调度和协调网络中节点的数据发送时机（Aydin and Akyuz， 2017）。后者假定无人机拥有全局信息，针对所有时隙资源和无人机进行资源分配和调度（Lee and Park， 2001）。本文采用线性整数规划方法研究通信网络中的无人机收发匹配问题，以探索无人机自组网通信能力的边界。

2. 问题描述和数学模型

2.1. 问题描述

考虑一个由个无人机为节点构成的通信网络。该网络中的每个无人机都部署了接收和发送信息的设备，且任意两个无人机之间都可以通信。由于搭载在同一无人机上接收和发送信息的设备之间存在干扰，这使得任意一个无人机配载的通信设备不能同时收发信息。也就是说，在任意时刻，任意无人机配载的通信设备只能处于接收信息或者发送信息的状态。令表示网络中所有无人机构成的集合。令表示无人机配载的通信设备可能的通信状态构成的集合，和分别表示接收信息状态和发送信息状态。为了方便描述无人机配载的通信设备所处的通信状态，我们把研究的时间段按照时隙长度进行离散。对于任意无人机配载的通信设备在每个时隙内，要么处于接收信息状态，要么处于发送信息状态。令表示无人机配载的通信设备在第个时隙所处的通信状态。如果无人机配载的通信设备在时隙处于接收信息的状态，则；否则，。为了便于对无人机通信网络的管理和维护，我们对所有无人机配载的通信设备采用相同周期性的通信状态管理，即所有无人机配载的通信设备按照个时隙周期性重复各自的通信状态。依据定义，对于任意无人机，我们都有。

对于任意的两个不同的无人机和，在第个时隙内，只有当其中一个无人机处于发送信息状态，另一个无人机处于接收信息状态，它们才能够进行单向通信，即一个发送信息，另一个接收信息。否则，两个无人机之间将处于不通信的状态。当无人机处于发送信息状态和无人机处于接收信息状态时，我们称无人机处于对无人机的单向通信状态。令表示无人机和在第个时隙内的通信状态。如果无人机和在第个时隙内分别处于接收信息和发送信息状态，则；否则，有。依据定义，当且仅当和满足时（即无人机处于对无人机的单向通信状态），我们有；否则，。由于单个无人机配载的通信设备的通信状态具有周期性，任意两个无人机之间的通信状态也具有周期性，并且周期也是个时隙。

对于任意给定的两个无人机和，我们把一个周期内无人机处于对无人机的单向通信状态的时隙数量定义为无人机对无人机的单向通信能力。令表示无人机对无人机的单向通信的重要程度。整个无人机网络的通信能力则定义为所有无人机对之间的单向通信能力加权之和。无人机通信网络优化问题就是要通过优化所有无人机上通信设备在各个时隙内的状态来最大化无人机网络的通信能力。考虑到网络时隙资源利用的均衡性，任意无人机对之间的通信还需要满足最大时隙间隔约束，即在连续个时隙内，任意无人机都需要对无人机实现至少一次单向通信。由于无人机配载的通信设备的通信状态和两个无人机之间的通信状态的周期性，在无人机通信网络优化问题中，我们只需要考虑一个周期。令表示一个周期内所有时隙构成的集合。

2.2. 数学模型

无人机网络容量最大化问题中有两类复杂的约束：（i）无人机通信设备的状态与单向通信状态之间的关系约束和（ii）无人机之间单向通信的最大时隙约束。下面详细介绍这两类约束。

依据定义，表1给出了无人机和无人机上的通信设备的状态与无人机对无人机的单向通信状态之间的关系。由表1中的变量关系，我们有

等价地，我们可以得到无人机通信设备的状态与单向通信状态之间的关系约束如下：

令表示第个时隙和之后的个时隙构成的集合。考虑到无人机配载的通信设备通信状态的周期性和无人机之间单向通信的周期性，我们有：

无人机之间单向通信的最大时隙约束要求相邻的两次单向通信间隔不超过个时隙，即当时，存在一个时隙使得。此时，必有。于是，无人机之间单向通信的最大时隙约束可以表述如下：

其中，当时，约束条件始终成立。

考虑最大时隙约束的无人机网络容量最大化问题可以描述为如下线性0-1整数规划问题：

其中，目标函数最大化整个无人机网络的通信能力。约束条件要求任意两个无人机在一个周期内至少要完成一次通信。约束条件和要求决策变量为0-1变量。

3. 权重随机下启发式求解算法

线性0-1整数规划问题所对应的模型中，变量数量有个，约束有个。随着节点和时隙个数的增加，模型的变量和约束条件的规模越来越大。现有精确求解算法（如分支定界方法、割平面方法，以及隐枚举方法），无法在短时间内求出最优解，因此采用启发式算法来解决这个问题。

3.1. 算法概述

一般的启发式算通常建立在对问题的解进行局部的邻域操作上。这种局部搜索启发式算法能在短时间内搜索大量的解，但是在每一次迭代中，一个解的改动都很小。当求解约束较紧的问题时，这种算法一般比较难使搜索从一个解空间跳转到另一个解空间，而大邻域搜索算法能较好的处理这种情况。故本文设计了一种自适应大邻域搜索算法，对大规模的问题进行求解。

大邻域搜索算法主要包括三个部分：初始可行解的生成，破坏算子和修复算子。在每一次迭代中，通过破坏和修复当前解，该算法可以得到一个新的可行解。自适应大邻域搜索算法，它是大邻域搜索算法的扩展。这两种算法不同的地方在于，大邻域搜索算法通常只有一个破坏算子和一个修复算子，而自适应大邻域搜索算法包括多个破坏算子和多个修复算子。该算法从一个初始可行解开始。在每一次迭代中，该算法采用轮盘赌选择方法挑选出一个破坏算子和一个修复算子。通过破坏和修复当前解，该算法可以得到一个新的可行解。新解的接受是采用模拟退火的接受准则。每过一定的迭代次数，该算法会更新每个破坏算子和修复算子被选择的概率。当达到最大迭代次数时，算法终止。在自适应大邻域搜索算法中，自适应的调整每个算子被选择的概率使得表现好的算子更容易被选中，有利于算法得到更好的解。

3.2. 解的编码与评估

在自适应大邻域搜索算法中，我们采用一种简易的编码方式。使用一个行列的二维数组表示所有节点在任意时隙的状态，二维数组中0或者1分别对应节点的收或发状态，即，。由于可有节点对对应的和表示出来，因此作为中间变量，不再对其进行编码。针对初始解的生成，通过随机生成行的0或者1填充至二维数组中即可，如下所示（）。

本文的0-1整数规划模型中由于存在复杂的约束，即最大时隙约束（约束4），在求解中不易处理，将其设置为软约束。因此，在算法的迭代过程中，允许不可行解的存在。令表示一个解的适应度值，其中为问题P的原目标函数，表示解对于最大时隙约束的违背，是惩罚系数，且随着算法迭代次数自适应调整。调整规则如下：每100次迭代，统计这100个新解中违背最大时隙约束的个数，如果违背最大时隙约束的新解的个数超过50个，则增大，；否则减小，。是事先给定的参数。适应度值用来评价解的优劣。

3.3. 破坏和修复算子

在算子设计中，本文采用了破坏和修复两类算子。其中，破坏算子包含三类算子，修复算子包含两类算子。

3.3.1. 破坏算子

破坏算子都是以一定规则从当前解中删除一定数量的收状态（）。在每一次迭代中，删除某一状态的数量是随机选择的，其取值范围是。其中，是预先给定的参数。不同的破坏算子选择不同删除规则。本文引入相似删除算子，随机删除算子和最差删除算子等三类破坏算子。

（i）相似删除算子

删除二维数组中相似的个“1”。二维数组中任意两个位置的“1”的相似程度的评价准则为：。其中表示这两个“1”的行间距，表示这两个“1”的列间距，和分别是行间距系数和列间距系数。相似度越小则表示两个“1”越相似。

（ii）随机删除算子

随机删除二维数组中的个“1”。

（iii）最差删除算子

删除二维数组中最差的个“1”。某位置上“1”的差的程度的评价准则为：将某位置设为当前位置，把当前位置“1”改成“0”后得到新解，则当前位置“1”的适应度值的增量。由于本问题目标函数为最大化问题，越小，则该“1”越好；相反，越大，则该“1”越差。在当前解中逐一选取 “1”的位置，计算各自位置上的增量，按照增量的降序排序，将前个位置的“1”改成“0”。

3.3.2. 修复算子

修复算子是把破坏算子删除的“1”以寻优的方式重新插回当前解中适当的位置。具体而言，修复算子就是向二维数组中插入个“1”，即把这些位置上的“0”改成“1”。本算法引入婪插入算子和次优插入算子等两类修复算子。

（i）贪婪插入算子

在二维数组中选择最优的个“0”。某位置上“0”的好的程度的评价准则为：将某位置设为当前位置，把当前位置“0”改成“1”后得到新解，则当前位置“0”的适应度值的增量。由于本问题目标函数为最大化问题，越大，则该“0”越好；相反，越小，则该“0”越差。在当前解中逐一选取 “0”的位置，计算各自位置上的增量，选择增量最大位置将“0”改成“1”，更新当前解后，重复执行该操作次。

（ii）次优插入算子

与贪婪插入选择最优位置插入不同，次优插入算子每次选择二维数组中次优位置的“0”改成“1”，直到有个“0”改成“1”。

3.3.3. 算子权重和选择概率的更新

在每一次迭代中，根据得到的新解的表现，我们会分别给此次挑选出的破坏算子和修复算子一个分数。这主要分为三种情况：如果新解比目前的全局最优解要好，则挑选出的破坏算子和修复算子各得33分；如果新解比当前解要好但比目前的全局最优解要差，则挑选出的破坏算子和修复算子各得9分；如果新解比当前解要差但被接受了，则挑选出的破坏算子和修复算子各得13分。第三种情况的得分比第二种情况的得分要大（即13>9），是因为差的解被接受能增加解的多样性。

将把算法的整个迭代过程分为一个个片段，每个片段都包含100次迭代。在每个片段开始时，所有的破坏算子和修复算子的得分都会设置为0。令表示破坏算子的集合。对所有的破坏算子，令表示破坏算子在片段的权重。在算法完成片段时，在子段中，破坏算子的权重的计算公式如下：

其中，为算子在片段中累计获得的分数，为算子在片段中累计被挑选的次数，为给定的参数。

所有算子在第一个片段的权重都设置为1。利用每个破坏算子的权重，我们可以计算破坏算子在片段的选择概率。修复算子的权重和概率的更新方式与破坏算子的类似，在此不再赘述。

3.4. 详细算法

在自适应大邻域搜索算法中，从一个初始可行解开始，在每一次迭代中，采用轮盘赌选择方法挑选破坏算子和修复算子。通过破坏和修复当前解，可以得到一个新的可行解。新解的接受准则采用模拟退火的接受准则。每过一定的迭代次数，该算法会更新每个破坏算子和修复算子被选择的概率。当达到最大迭代次数时，算法终止。在每次迭代过程中，自适应的调整每个算子被选择的概率使得表现好的算子更容易被选中，有利于算法得到更好的解。通过设计多组破坏算子和修复算子，并对各个破坏和修复算子进行选择和权重调整，从而扩大解空间搜索范围，对当前解进行改进，提高算法寻优能力，从而找到最优解。本算法详细流程如算法1所示。

4. 算例测试

为了验证本文所提出方法的合理性，本文通过不断增大无人机规模来改变网络参数进而得到不同的算例进行验算。最大时隙长度的设置会影响到问题解的存在性，一般而言，无人机越多，最大时隙长度会越大。为了得到存在可行解的最大时隙间隔长度，本文构建了最小化最大时隙模型，

其中，约束（10）表示节点对之间最大时隙约束，即相邻两次处于通信状态间的时隙个数不能超过最大时隙个数。

利用主流商业软件Cplex或者Gurobi求解上述模型，得到最小化最大时隙如表2所示。

本文提出的自适应大邻域算法，在CPU为Intel（R）Core（TM）i9-10900K@3.70GHz，内存为32G的计算机，采用Visual C#语言编程实现。同时采用Cplex求解器考虑最大时隙约束的无人机网络容量最大化问题。给出了两种方法求解问题时的目标函数值、通信次数和算法运行时间。算例结果显示，Cplex求解器在无人机数量小于7时能够对问题快速求解，但随着无人机数量的不断增加，Cplex求解器无法对问题进行有效求解。因此，Cplex求解器只适用于小规模问题，无法处理大规模场景下的问题。相比之下，自适应大邻域算法不仅可以准确求解小规模问题，还能处理大规模问题，并且具有较高的求解效率和求解质量。5. 结论

本文通过构建0-1整数规划模型，考虑最大时隙约束的网络通信能力最大化问题，实现了对无人机时隙资源的均衡利用。本文提出了自适应大邻域搜索算法，用于解决大规模的0-1整数规划问题。算例结果表明，本文提出的自适应大邻域算法能够针对不同规模的无人机网络进行求解，且求解效率较高。在通信领域，本文的研究结果对于优化无人机时隙资源的利用具有重要意义。通过最大化网络通信能力，无人机的通信效率得到提升，可以更好地服务于各种应用场景的通信任务。

参考文献

[1]Chen， J.Y.C.， 2010. UAV-guided navigation for ground robot tele-operation in a military reconnaissance environment. Ergonomics 53， 940–950. https：//doi.org/10.1080/00140139.2010.500404

[2]Gu， Q.， Fan， T.， Pan， F.， Zhang， C.， 2020. A vehicle-UAV operation scheme for instant delivery. Computers & Industrial Engineering 149， 106809. https：//doi.org/10.1016/j.cie.2020.106809

[3]Gupta， L.， Jain， R.， Vaszkun， G.， 2016. Survey of Important Issues in UAV Communication Networks. IEEE Commun. Surv. Tutorials 18， 1123–1152. https：//doi.org/10.1109/COMST.2015.2495297

[4]Han， S.I.， Baek， J.， 2021. Optimal UAV Deployment and Resource Management in UAV Relay Networks. Sensors 21， 6878. https：//doi.org/10.3390/s21206878

[5]Javaid， S.， Saeed， N.， Qadir， Z.， Fahim， H.， He， B.， Song， H.， Bilal， M.， 2023. Communication and Control in Collaborative UAVs： Recent Advances and Future Trends. IEEE Trans. Intell. Transport. Syst. 24， 5719–5739. https：//doi.org/10.1109/TITS.2023.3248841

[6]Lee， T.， Park， S.， 2001. An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links. European Journal of Operational Research 135， 57–66. https：//doi.org/10.1016/S0377-2217（00）00291-5

[7]Mohsan， S.A.H.， Othman， N.Q.H.， Li， Y.， Alsharif， M.H.， Khan， M.A.， 2023. Unmanned aerial vehicles （UAVs）： practical aspects， applications， open challenges， security issues， and future trends. Intel Serv Robotics. https：//doi.org/10.1007/s11370-022-00452-4

[8]Muhmad Kamarulzaman， A.M.， Wan Mohd Jaafar， W.S.， Mohd Said， M.N.， Saad， S.N.M.， Mohan， M.， 2023. UAV Implementations in Urban Planning and Related Sectors of Rapidly Developing Nations： A Review and Future Perspectives for Malaysia. Remote Sensing 15， 2845. https：//doi.org/10.3390/rs15112845

[9]Su， Y.-H.， Bhowmick， P.， Lanzon， A.， 2023. A robust adaptive formation control methodology for networked multi-UAV systems with applications to cooperative payload transportation. Control Engineering Practice 138， 105608. https：//doi.org/10.1016/j.conengprac.2023.105608

[10]Xi， X.， Cao， X.， Yang， P.， Chen， J.， Quek， T.Q.S.， Wu， D.， 2021. Network Resource Allocation for eMBB Payload and URLLC Control Information Communication Multiplexing in a Multi-UAV Relay Network. IEEE Trans. Commun. 69， 1802–1817. https：//doi.org/10.1109/TCOMM.2020.3042970

[11]Zhang， J.， Xing， J.， 2020. Cooperative task assignment of multi-UAV system. Chinese Journal of Aeronautics 33， 2825–2827. https：//doi.org/10.1016/j.cja.2020.02.009

作者简介：

汪捷（1999.8），男 汉族 安徽省安庆人 学历：硕士 职称：无 从事交通网络建模与优化和智慧交通相关研究

黄子轩（1994.10），女 汉族 安徽淮南人 学历：博士在读 职称：无，从事卫星互联网、天地一体化、编队组网研究

张靖（1983.10），男 汉族 安徽合肥人 学历：硕士 职称：中级工程师，从事无线通信、卫星测控通信与定向自组织网络技术研究