随着战场环境的动态变化和作战任务的复杂多样性，单架无人机的自身能力有限，执行任务受损伤的概率比较大，已经无法满足战争的需求。相比单架无人机，多无人机协同作战在时间和空间上都占有比较大的优势，具有更好的灵活性，可以充分发挥自身的优势去完成更复杂的工作，提高工作效率和任务的成功率[1]。多无人机协同作战的广泛应用，促使多无人机协同任务分配技术得到了迅速的发展。多无人机协同任务分配[2]，指的是根据各种设备和系统提供的环境信息，以及无人机自身的性能，对多架无人机进行任务的分配，并且能够随着动态环境的变化进行实时协商和任务方案的调整[3]。
世界各国对无人机等智能体的协同任务分配方面高度重视，各个领域的学者和专家进行了大量研究，提出了大量任务分配算法，有离散粒子群优化法[4]、遗传算法[5]、黑板模型算法[6]、基于概率估计的交叉熵法[7]、合同网算法[8]。
在合同网算法中，无人机担任的角色非常灵活，可以担任招标者，也可以担任投标者。所有的无人机之间都可以进行通信，是一种非常灵活且鲁棒性较高的分布式任务分配算法。文献[9]为了适应Agent能力动态变动的环境，引入信任度的概念，提出了动态合同网。后来研究人员通过引入交互信任度、熟人信任度和阈值等策略提高效率。信任是对无人机能够完成任务的相信程度[10]，当无人机在完成任务时可以更新信任度，或者根据熟人推荐的评定信息来更新信任度[11]。文献[12]使用任务信任度和任务负载率双重因素对合同网进行改进，并用信任度阈值的策略对任务的发布范围进行弹性选择。文献[13]将合同网协议与管理者之间的直接谈判相结合，文献[14]采用了合同网算法模型，为了使任务分配更能适用于动态环境，建立能力模型和执行的任务描述，通过将正在执行的任务进行招标来动态改变自身能力以进行任务的再分配，这种协商策略的引入，明显地改善了任务分配的效果，但也增加了决策的成本，导致通信量增大。文献[15]采用传统合同网算法，引入了一种计算边际成本的投标模型和评标模型，虽然能够改善任务分配的效果，但同时也增大了系统中的通信量。
1 传统合同网算法
合同网算法(contract net protocol，CNP)是由Randall Davis和Reid G.Smith于1980年提出的，用于解决分布式问题的任务协作和任务分配算法，该算法通过模拟人类在活动中的招投评标机制，实现任务分配。合同网算法的基本思想是通过招标、投标、中标、签约4个阶段，如图1所示。
1) 招标阶段：系统中的某架无人机发现新任务或者发现有任务无法独立完成需要分配时，该无人机作为招标者，制定招标信息后，向其它无人机发布招标信息寻求帮助，通知其他无人机作为投标者来参与此次招标活动。
2) 投标阶段：系统中的其他无人机接收到招标者发送的招标信息后，参考招标信息中的能力和资源需求，以及自身的具体情况，制定参与投标的标书，并发送给招标者参与投标。
3) 中标阶段：招标者接收到投标者的标书后，根据具体的投标信息评估准则进行评标，选择出最合适的投标者成为本轮招标活动的中标者。
4) 签约阶段：根据合同信息，招标者和中标者达成一致后，双方签订合同，中标者的任务序列中加入此任务，至此完成一次任务的分配。
图1 传统合同网算法任务分配过程框图
Fig.1 Traditional contract net task allocation algorithm process schematic
传统的合同网算法虽然能够将任务成功的分配给系统成员，但是仍然存在不足之处，降低了任务分配的效率和系统的整体效能。传统合同网算法中，没有限制可以参与投标的无人机数量，不管有没有足够的能力执行任务，只要是接收到招标信息的无人机，都可以参与到投标活动中进行投标。这样频繁的通信，会加重系统的通信负担。若系统中的无人机数量不断增加，就会造成系统中的通信量快速增大，甚至会导致系统的拥堵和瘫痪。本文选择合同网算法解决多无人机的协同任务分配问题，设计了一种合同网改进算法，在投标阶段进行改进，不仅降低了系统中的投标者的数量，均衡了通信量，还降低了无人机的工作负载，并使其保持在一个稳定的水平。
2 改进合同网算法
2.1 任务效能模型
无人机协同任务分配方案的好坏需要用某个指标来衡量，所以本文建立了任务效能模型，该模型以无人机完成任务时所获得的收益函数和付出的代价函数为基础，通过计算2个函数的差值来反应任务分配方案的优劣和可行性。
无人机UAVi完成任务获得的收益主要由任务自身的价值以及无人机UAVi执行任务的能力共同来决定。任务自身的价值是预先设定好的，无人机UAVi执行任务的能力是根据数据库的历史信息获取的，主要体现在无人机自身的性能和无人机历史网络吞吐量，无人机自身性能包括无人机携带的武器装备、传感器、最大续航时间和可靠性等，通常以概率进行描述。
无人机UAVi对某目标Tj执行攻击任务，目标Tj的自身价值为Vj，UAVi对该目标的摧毁概率为Pj，无人机UAVi对目标进行攻击后的生存概率为Ps，则无人机UAVi执行该攻击任务Tj所获得的收益Reward(Tj)为：
Reward(Tj)=Vj*Pj*Ps
无人机UAVi完成任务Tj所需要付出的代价表示为cost(Tj)，该代价函数主要考虑以下2个方面：
一是作用在无人机上的阻力，阻力计算公式为
其中，
称为动压， ρ为飞行高度处的空气密度，V为无人机的飞行速度，S为机翼的有效面积，Cx为阻力系数，通常是通过风洞实验得来的曲线。
式中，Cx0为零升阻力系数，CL为升力系数，通常也是通过风洞实验得来的：
CL=CLa(α-α0)
式中：α为迎角，α0为升力等于零时的迎角，CLa与翼型有关，近似为常数。
A为机翼的展弦比：
式中：L为翼展长度，S为机翼的面积。需要注意的是，两者的数量单位要保持一致。
综上所述可得，作用在无人机上的阻力为：
则无人机付出的阻力代价表示为
二是无人机UAVi执行任务Tj的风险代价，用无人机自身的价值Vi和无人机在执行任务过程中的损耗概率Pk来表示，即：
Riskcost(Tj)=Vi*Pk
因此，无人机UAVi执行任务Tj的代价为：
cost(Tj)=w1*Xcost(Tj) + w2*Riskcost(Tj)
w1和w2表示的是对于任务分配结果的影响程度，值越大，说明该因素对于任务分配的结果有很大的影响。其中w1+w2=1。
通过上述对无人机的收益函数Reward(Tj)和代价函数cost(Tj)的定义，可得无人机UAVi完成任务Tj的任务效能U(Tj)为
U(Tj)=Reward(Tj)-cost(Tj)
在计算时需要先将不同的单位进行统一，即分别对任务收益Reward(Tj)和任务代价cost(Tj)进行归一化处理，统一成相同的量纲后再进行运算。
综上所述，多无人机协同任务分配的目标函数模型为
Uij表示无人机UAVi执行完任务Tj后所获得的任务效能。也就是说，多无人机协同任务分配的最终目标是，使系统中的所有无人机执行完任务序列中的所有任务后，系统的整体任务效能达到最大。
2.2 投标策略
传统合同网算法中，在接收到招标者发布的任务后，系统中所有的无人机均可参与投标，这就会造成系统通信频繁，同时招标者后续的评标工作负担也会增大。那么，为了减少系统中的通信量，最简单直接的办法就是减少投标者的数量。
本文设计了一种基于无人机能力评估方法的投标策略。无人机的能力评估方法，是以无人机的能力大小为评判标准，需要结合无人机之前和当下的情况来进行综合评估。投标者可以根据自己曾经完成任务的相关历史信息，获得自己的历史任务效能；其次，还要以投标者执行本轮招标任务的任务效能为依据进行判断；最后，根据投标者自身的当前状态，获取投标者的工作负载和网络吞吐量。根据以上4个方面，获取评估所需要的相关信息，使投标者对自己的能力进行评估。
引入历史任务效能
表示无人机UAVi在历史任务中所获得的任务效能。通过该指标可以反映出无人机在执行历史任务时的表现优劣、稳定性和可靠度。计算公式如下所示：
引入工作负载为Ti，即无人机UAVi完成任务的最短时间为Ti，则平均工作负载为
式中，w1为系统中执行任务的无人机数量。
所以，无人机UAVi的工作负载系数为
工作负载系数CTi的含义是：
当CTi<0时，说明第i架无人机的工作负载比系统中的平均负载低；
当CTi>0时，说明第i架无人机的工作负载比系统中的平均负载高；
当CTi<CTj时，说明第i架无人机的工作负载比第架无人机的工作负载低。
其中:
为无人机平均网络吞吐量，THRt为无人机t时刻的网络吞吐量，t时刻为无人机收到招标书的时刻。
当Wt>10时，说明此时无人机网络超负荷，应减少任务量。
当1<Wt≤10时，说明此时无人机的网络负载较大，不适合增加任务量。
当0.5<Wt≤1时，说明此时无人机的网络负载较轻，可以增加任务量。
当Wt≤0.5时，说明此时无人机网络负载小，适合增加任务量。
综上所述，无人机的能力Ai可表示为
β1和β2分别表示历史任务效能和执行本轮招标任务的任务效能的影响因子。β1+β2=1。
在招标者发送的标书中，包含招标者自身的能力值
在投标者收到招标者发布的任务后，首先根据无人机能力评估方法，计算出自己的能力值Ai，然后再与招标者的能力值进行比较。若大于招标者的能力值，则进行投标，反之，则不投标。图2为改进后合同网算法过程框图。
图2 改进合同网算法任务分配过程框图
Fig.2 Improved network algorithm task allocation process diagram of contract
基于无人机能力评估方法的投标策略，既考虑了无人机的历史任务效能和本轮招标任务的任务效能，又考虑了无人机的工作负载。不仅保证了投标者执行任务的稳定性和可靠性，还保证了投标者执行本次任务能够获得较大的任务效能。另外，也避免了给无人机带来过大的工作压力。
3 仿真与分析
为了验证本文所设计算法的有效性，进行了多组计算机模拟仿真实验。假设系统中有8架无人机对50个目标执行任务，信道容量为600 bps，模拟战场区域是边长为 10 km的正方形区域。
图3为无人机改进合同网算法与另外2种算法中投标者的数量对比仿真曲线，系统中有8架无人机，一共对30个任务进行了招标，每个招标任务的投标者数量如图所示。由仿真结果的对比可以看出，改进合同网算法中，每个招标任务的投标者数量要明显小于传统合同网算法中的投标者数量，平均减少了56.25%。而在传统合同网算法中，系统中所有的无人机都作为投标者进行了投标，故投标者的数量即为系统中无人机的数量，始终保持不变。文献[14]投标阶段考虑了当前能力，投标数量相应减少。改进合同网算法中的投标者在投标前对历史和当前的自身能力还有现阶段任务状况进行考虑，只有具备任务要求能力并且大于招标者能力的投标者才会参与投标，这样就减小了投标者的数量以及招标者的评标压力。
图3 投标者数量仿真曲线
Fig.3 The number of bidders
图4为中标者改进合同网算法与另外2种算法中的执行任务的时间对比仿真曲线。
图4 执行任务时间仿真曲线
Fig.4 Task execution time
执行任务的时间就是上文所定义的工作负载，由图可以看出，改进合同网算法中，对能否成为投标者有了工作负载的约束，如果此时工作负载较高，则拒绝投标，从而使中标者执行任务的时间降低，并且使得每次中标者的执行任务时间相当。文献[14]算法，可以选择将优先级低的任务重新分配，并对该任务进行招标，以此来寻找系统的最优分配方案，但任务再分配会导致任务完成时间增加。在传统合同网算法中，中标者的执行任务时间比改进合同网算法高很多，上下波动范围较大，不稳定。说明改进合同网算法中的投标策略在考虑工作负载这一因素后，不仅能够降低无人机的执行任务的时间，还能使其保持在相对稳定状态。
图5为中标者在改进合同网算法与另外2种算法的中的无人机网络吞吐量仿真曲线。其值越小，说明无人机的任务分配越合理，即已选择当前通信状态比较空闲的无人机参与投标。由图可知，改进合同网算法中，经过投标策略的设定，对能否成为投标者考虑了当前无人机吞吐量，使得每一个无人机充分利用网络带宽，网络吞吐量处于比较稳定状态。对于文献[14]算法来说，由于该算法能够将自身的正在处理的任务进行招标，这样会增加标书的数量进而增加系统的通信量，会造成通信负担。在传统合同网算法中，中标者的网络吞吐量大小不一，波动范围较大，不能很好地利用网络带宽，造成了资源浪费，也很可能会造成网络拥塞。进而说明，改进合同网算法中的投标策略在考虑网络吞吐量这一因素后，不仅能降低网络的数据流量，均衡网络吞吐量，还可以有效减少网络拥塞。
图5 中标者吞吐量仿真曲线
Fig.5 The throughput of the successful bidder
图6为改进合同网算法与另外2种算法系统任务效能的仿真曲线，仿真次数为30次。
图6 任务效能仿真曲线
Fig.6 Comparison chart of task effectiveness
由仿真对比结果可以看出，改进合同网算法的系统任务效能优于另外2种算法。说明通过对无人机进行工作负载以及网络吞吐量的进行投标约束，从而减少无人机付出的代价，选择了当前状态比较好的无人机投标，提高任务效能。多无人机协同任务分配方案的好坏就是通过任务效能这个变量来体现的，说明改进的合同网算法能够很好的对模型进行求解，提高分配效率，验证了其可行性和有效性。
4 结论
本文提出了一种改进的合同网算法。仿真结果表明，改进的合同网算法与传统的合同网算法相比，在保证系统任务效能的前提下，投标者的数量明显减少，从而大大降低了系统中的通信量。另外，无人机的工作负载不仅得到了明显降低，无人机网络吞吐量处于均衡水平。优化效果明显，验证了改进算法的可行性和有效性。
[1] 张哲，吴剑，何诚，等.复杂环境下多目标多无人机协同任务规划[J].兵器装备工程学报，2020(02):123-128.
Zhang Z，Wu J，He C，et al.Multi-target and multi-UAV coordinated mission planning in complex environments[J].Journal of Ordnance Equipment Engineering，2020(02):123-128.
[2] 杨晨，张少卿，孟光磊.多无人机协同任务规划研究[J].指挥与控制学报，2018，4(03):234-248.
Yang C，Zhang S Q，Meng G L.Research on multi-UAV cooperative mission planning[J].Journal of Command and Control，2018，4(03):234-248.
[3] Luo R B，Zheng H X，Guo J F.Solving the multi-functional heterogeneous UAV cooperative mission planning problem using multi-swarm fruit fly optimization algorithm[J].Sensors(Basel，Switzerland)，2020，20(18):17-24.
[4] 梁国强，康宇航，邢志川，等.基于离散粒子群优化的无人机协同多任务分配[J].计算机仿真，2018，35(02):22-28.
Liang G Q，Kang Y H，Xing Z C，et al.Cooperative multi-task allocation of UAV based on discrete particle swarm optimization[J].Computer Simulation，2018，35(02):22-28.
[5] 赵民全.基于改进遗传算法的多无人机协同任务规划[J].舰船电子对抗，2020，43(04):44-47.
Zhao M Q .Multi-UAV cooperative mission planning based on improved genetic algorithm[J].Ship Electronic Warfare，2020，43(04):44-47.
[6] KEVICZKY T，BORRELLI F，FREGENE K，et al.Decentralized receding horizon control and coordination of autonomous vehicle formations[J].IEEE Transactions on Control Systems Technology，2008，16(01):19-33.
[7] NGUYEN D M，THI H A L，PHAM D T.A cross-entropy method for nonlinear uav task assignment problem[C]//Computing and Communication Technologies，Research，Innovation，and Vision for the Future(RIVF)，2010 IEEE RIVF International Conference on.IEEE，2010:1-5.
[8] Reid G.Smith.The contract net protocol:High-level communication and control in a distributed problem solver[J].IEEE Trans.Computers，1980，29(12):1104-1113.
[9] 张海俊，史忠植.动态合同网协议[J].计算机工程，2004(21):44-46，57.
Zhang H J，Shi Z Z.Dynamic contract network agreement[J].Computer Engineering，2004(21):44-46，57.
[10] 陈坚，廖守亿，邓方林.一种基于多Agent的计算机生成兵力协作方法[J].计算机仿真，2010，27(02):113-117.
Chen J，Liao S Y，Deng F L.A computer-generated force collaboration method based on multi-agent[J].Computer Simulation，2010，27(02):113-117.
[11] 贺利坚.多Agent系统中信任和信誉模型的研究[D].北京:北京交通大学，2011.
He L J.Research on trust and reputation model in multi-agent system[D].Beijing:Beijing Jiaotong University，2011.
[12] 李新亮，翟江涛，戴跃伟.动态环境下基于改进合同网的多Agent任务分配算法[J].科学技术与工程，2013，13(27):8014-8019.
Li X L，Zhai J T，Dai Y W.Multi-agent task allocation algorithm based on improved contract network in dynamic environment[J].Science Technology and Engineering，2013，13(27):8014-8019.
[13] Panescu DPascal C.An extended contract net protocol with direct negotiation of managers[J].Springer International Publishing，2014(10):51-56.
[14] 李明，刘玮，张彦铎.基于改进合同网协议的多Agent动态任务分配[J].山东大学学报(工学版)，2016，46(02):54-59,66.
Li M，Liu W，Zhang Y D.Multi-agent dynamic task allocation based on improved contract network protocol[J].Journal of Shandong University(Engineering Science Edition)，2016，46(02):54-59,66.
[15] 肖玉杰，李杰，刘方.基于合同网的分布式动态任务分配算法[J].舰船科学技术，2015，37(03):113-118.
Xiao Y J，Li J，Liu F.Distributed dynamic task allocation algorithm based on contract network[J].Ship Science and Technology，2015，37(03):113-118.