论文范文:多无人机博弈决策与协同通信方法研究

来源: 未知 作者:paper 发布时间: 2022-05-26 11:19
论文地区:中国 论文语言:中文 论文类型:财务管理
无人机具有成本低、灵活性高、部署方便、无人员伤亡等优点,在军事和民 用方面得到了广泛关注。多无人机协同应用可以弥补单架无人机能力的局限性, 在复杂任务场景中发挥重要
无人机具有成本低、灵活性高、部署方便、无人员伤亡等优点,在军事和民
用方面得到了广泛关注。多无人机协同应用可以弥补单架无人机能力的局限性,
在复杂任务场景中发挥重要的作用。然而多无人机协同应用离不开决策与通信技
术的支撑,其中,任务最优决策是实现协同控制的核心,集群自适应分簇是提
高网络扩展性的基础,路由高效选择是实现远距离通信的关键,资源与轨迹合理
优化是保证通信性能的前提。因此,本文将以实现多无人机高效完成任务为目的,
对无人机任务决策、集群分簇、路由选择、资源分配与轨迹优化问题展开研究。
主要研究内容如下:
(1)针对复杂任务场景下多无人机任务决策问题,首先研究面向非对抗任
务的大规模无人机任务决策,考虑任务重要性、执行任务的无人机数量以及燃料
消耗,提出基于联盟博弈的非对抗任务决策方法,进一步考虑无人机与任务的动
态不确定性以及无人机通信距离受限的影响,提出任务重分配方法,实现决策结
果的动态调整,解决传统任务决策方法收敛速度慢、适应性差的问题。其次研究
面向对抗任务的多无人机任务决策,考虑对抗过程具有复杂博弈特性、动态随机
特性,以己方收益最大为目标,提出基于随机博弈的对抗任务决策方法,为对抗
环境下己方提供最优策略,解决多阶段博弈决策问题。
(2)针对具有协同关系的无人机集群分簇问题,考虑无人机快速移动会造
成通信网络拓扑频繁更新、通信链路不稳定,且执行同一任务的无人机具有高度
相似的运动方式和频繁的信息交互需求,提出基于联盟博弈的无人机集群分簇方
法,通过建立集群分簇问题的联盟博弈模型,设计包含无人机切换集合生成-切
换操作建立-最佳切换操作选择三个阶段的求解算法,将无人机网络分成多个相
连的区域,解决大规模网络管理困难问题,提高网络的稳定性。
(3)针对面向远距离信息传输需求的多无人机路由选择问题,考虑部分无
人机与地面站相距较远,导致直传链路通信距离和速率受限,提出基于网络形
成博弈的多无人机路由选择方法,通过建立路由选择问题的网络形成博弈模型,
设计寻找无人机纯策略和混合策略的求解算法,为每架无人机规划到地面站的信
息传输路径,解决无人机与地面站远距离信息传输问题。
(4)针对面向无人机通信的资源分配与轨迹优化问题,考虑无人机到地面
站不存在路由的情况,通过部署中继无人机辅助通信。在任务无人机通信需求、
能量受限以及中继无人机能量、机动能力受限等约束下,以网络吞吐量最大为目
标,基于凸优化设计迭代方法对任务无人机时隙与功率、中继无人机功率等通
信资源以及中继无人机飞行轨迹进行合理优化,解决无路由下远距离无人机与
I
地面站的通信问题。
关键词:无人机,任务决策,协同通信,集群分簇,路由选择,资源分配,轨
迹优化,博弈论
II
ABSTRACT
 With the advantages of low cost, high flexibility, convenient deployment and no
casualties, unmanned aerial vehicle (UAV) has been received extensive attention in
military and civil applications. As multi-U AV coordination could make up for the
limitation of single-U AV, it plays an important role in complex mission scenarios.
However, the multi-U AV coordination can’t do without the support of
decision-making and communication technologies. Among them, optimal task
decision-making is the core to achieve cooperative control. Adaptive swarm clustering
is the basis of improving network scalability. Efficient routing selection is the key to
realize long-distance communication. And reasonable resource and trajectory
optimization is the premises to guarantee the communication performance. Therefore,
this thesis studies the task decision-making, swarm clustering, routing selection,
resource allocation and trajectory optimization problems for the purpose of realizing
efficient missions of multi-U AV. The main research contents are as follows:
 (1)The multi-U AV task decision-making problem under complex scenarios is
investigated. Firstly, large-scale UAV task decision-making for non-adversarial
scenarios is studied. Considering the importance of tasks, the number of UAVs and
fuel consumption, a non-adversarial task decision-making method based on coalition
game is proposed. Further considering the dynamic and uncertain nature of the UAVs
and the tasks, as well as the influence of the limited communication range of the
UAVs, a task reallocation method is proposed to realize the dynamic adjustment of the
decision result. This is used to solve the problem of slow convergence and poor
adaptability of traditional task decision-making methods. Secondly, multi-U AV task
decision-making for adversarial scenarios is studied. Considering the complex game
and dynamic stochastic characteristics of the adversarial process, an adversarial task
decision-making method based on stochastic game is proposed to maximize the
benefits of own side. This is used to provide the optimial strategy under the
adversarial environment and solve multi-stage game decision problems.
 (2)The U AV swarm clustering problem is investigated with a cooperative
relationship. Considering that the rapid movement of UAVs will cause frequent
updates of communication network topology and unstable communication links. And
UAVs performing the same task have highly similar movement patterns and frequent
information exchange requirements. A U AV clustering method based on coalition
III
game is proposed. In this method, a coalition game model of swarm clustering is
established. After that, a three-stage solution algorithm including U AV switching set
generation-switch operation establishment-optimal switch operation selection is
designed to divide the U AV network into multiple connected areas. This is used to
solve the difficult problem of large-scale network management and improve the
network stability.
(3)To meet the long-distance information transmission requirement, the
multi-U AV routing selection problem is investigated. Condering that some UAVs are
far away from the ground station, which leads to the limitation of the communication
range and rate of the direct transmission link. A multi-U AV routing selection method
based on network formation game is proposed. In this method, a network formation
game model of routing selection is established. Then, a solution algorithm to find the
pure-strategy and mixed-strategy for UAVs is designed to plan a the information
transmission path to the ground station for each U AV. This is used to solve the
problem of remote information transmission between the UAVs and the ground
station.
(4)The resource allocation and trajectory optimization problem for the U AV
communication is investigated. Considering that there is no route from U AV to
ground station, relay U AV is deployed to assist communication. Under the
communication requirements and energy constraints of mission UAVs as well as the
energy and mobility constraints of relay U AV, in order to maximize the network
throughput, an iterative method based on convex optimization is designed to
reasonably optimize not only the time and power of the mission UAVs, but also the
power and flying trajectory of the relay U AV. This is used to solve the remote
communication problem between UAVs and ground station without routing.
KEY WORDS: Unmanned aerial vehicle (UAV), Task decision-making,
Cooperative communication, Swarm clustering, Routing selection, Resource
allocation, Trajectory optimization, Game theory
IV
目录
摘 要............................................................................................................................I
ABSTRACT...............................................................................................................III
目录...............................................................................................................................V
第 1 章 绪论..................................................................................................................1
 1.1 课题的研究背景与意义.................................................................................1
 1.2 多无人机任务决策与协同通信研究现状.....................................................5
 1.2.1 多无人机任务决策研究现状..............................................................6
 1.2.2 无人机集群分簇研究现状..................................................................7
 1.2.3 多无人机路由选择研究现状..............................................................9
 1.2.4 多无人机资源分配与轨迹优化研究现状........................................10
 1.2.5 多无人机任务决策与协同通信面临的难点问题............................14
 1.3 研究内容与组织结构...................................................................................15
 1.3.1 论文的研究内容................................................................................15
 1.3.2 论文的组织结构................................................................................17
第 2 章 复杂任务场景下多无人机任务决策 ...........................................................19
 2.1 引言...............................................................................................................19
 2.2 面向非对抗任务的大规模无人机任务决策...............................................20
 2.2.1 任务场景............................................................................................20
 2.2.2 非对抗任务决策问题描述................................................................21
 2.2.3 基于联盟博弈的非对抗任务决策....................................................23
 2.2.4 仿真验证............................................................................................30
 2.3 面向对抗任务的多无人机任务决策...........................................................34
 2.3.1 任务场景............................................................................................34
 2.3.2 对抗任务决策问题描述....................................................................35
 2.3.3 基于随机博弈的对抗任务决策........................................................36
 2.3.4 仿真验证............................................................................................40
 2.4 小结...............................................................................................................44
第 3 章 考虑协同关系的无人机集群分簇................................................................45
 3.1 引言...............................................................................................................45
 3.2 通信场景.......................................................................................................46
 3.3 无人机集群分簇问题描述...........................................................................46
 3.3.1 约束条件............................................................................................47
V
3.3.2 性能指标 ...........................................................................................47
3.3.3 优化模型 ...........................................................................................49
3.4 联盟博弈模型 ..............................................................................................49
3.5 基于联盟切换的求解策略 ..........................................................................50
3.6 仿真验证 ......................................................................................................56
3.6.1 仿真参数 ...........................................................................................56
3.6.2 仿真结果 ...........................................................................................57
3.7 小结 ..............................................................................................................62
第 4 章 面向远距离信息传输需求的多无人机路由选择.......................................63
4.1 引言 ..............................................................................................................63
4.2 通信场景 ......................................................................................................64
4.3 多无人机路由选择问题描述 ......................................................................64
4.3.1 约束条件 ...........................................................................................65
4.3.2 性能指标 ...........................................................................................66
4.3.3 优化模型 ...........................................................................................69
4.4 网络形成博弈模型 ......................................................................................69
4.5 基于最佳响应的求解策略 ..........................................................................71
4.6 仿真验证 ......................................................................................................75
4.6.1 仿真参数 ...........................................................................................75
4.6.2 仿真结果 ...........................................................................................76
4.7 小结 ..............................................................................................................80
第 5 章 面向无人机通信的资源分配与轨迹优化...................................................81
5.1 引言 ..............................................................................................................81
5.2 通信场景 ......................................................................................................82
5.3 无人机资源分配与轨迹优化问题描述 ......................................................83
5.3.1 约束条件 ...........................................................................................83
5.3.2 性能指标 ...........................................................................................85
5.3.3 优化模型 ...........................................................................................87
5.4 基于凸优化的求解策略 ..............................................................................87
5.4.1 子问题 1:任务无人机时隙分配 ....................................................88
5.4.2 子问题 2:任务无人机和中继无人机功率分配 ............................88
5.4.3 子问题 3:中继无人机轨迹优化 ....................................................90  5.4.4 整体优化算法 ...................................................................................96
5.5 仿真验证 ......................................................................................................97
VI
5.5.1 仿真参数............................................................................................97
5.5.2 仿真结果............................................................................................98
5.6 小结.............................................................................................................101
第 6 章 总结与展望..................................................................................................103
6.1 主要研究成果.............................................................................................103
6.2 未来工作展望.............................................................................................104
参考文献....................................................................................................................107
发表论文和参加科研情况........................................................................................121
致谢............................................................................................................................123
VII
第 1 章 绪论
第1章 绪论
本章首先阐述课题的研究背景与意义,然后对国内外研究现状进行综述,分
析多无人机任务决策与协同通信的难点问题,最后给出研究内容及组织结构。
1.1 课题的研究背景与意义
无人机(Unmanned Aerial Vehicle, UAV),又称无人驾驶飞机,是指利用空气
动力提供升力,可以遥控或自主控制,可回收利用,能够携带有效载荷,执行特
定空中任务的无人飞行器[1]。与有人机相比,无人机具有成本低、灵活性高、部
署方便、隐蔽性好、无人员伤亡等优点,在侦察打击、环境监测、信息收集、搜
索救援等军事和民用方面发挥了重要作用。
近年来,随着传感器技术、通信技术、控制技术的发展,无人机在战场博弈
中的地位日渐凸显。从 1991 年海湾战争开始,以美国为首的多个国家正式将无
人机投入到实际作战,利用无人机充当诱饵、收集情报信息,并通过电子干扰、
电子对抗压制敌方通信系统。此后在 1999 年科索沃战争、2001 年阿富汗战争中,
美国都出动了多架无人机执行战场侦察、信息传输任务,并且在 2003 年伊拉克
战争中,首次使用“全球鹰”无人机作为战场实时监视的空基平台,与战斗机协同
作战。由此可见,无人机作为未来战争中的有力武器,将发挥至关重要的作用。
然而,面对日益复杂的应用环境和多样性的任务需求,多无人机协同不仅可
以弥补单架无人机能力的局限性,还能提升任务执行效率,增加系统的可靠性,
实现功能与资源互补。为了推进多无人机协同作战,美国启动了多个项目,如图
1-1-图 1-4 所示,2014 年美国国防高级研究计划局(Defense Advanced Research
Projects Agency, DARPA)提出了“拒止环境协同作战” (Collaborative Operations in
Denied Environment, CODE)项目,旨在研究自主协同算法,增强无人机在通信中
断、无法使用全球定位系统(Global Positioning System, GPS)等不利条件下的协同
作战能力。2015 年 DARPA 启动了“小精灵”(Gremins)项目,重点研究无人蜂群的
发射和回收。同年美国海军研究院发起了“低成本无人机蜂群技术” (Low-Cost
U AV Swarming Technology, LOCUST)项目,并于第二年完成了 30 架无人机发射
及编组飞行的试验,有力推动了无人蜂群低成本高效作战应用。2016 年底,
DARPA 又启动了“进攻性蜂群使能战术”(OFFensive Swarm-Enabled Tactics,
1
天津大学博士学位论文
OFFSET)项目,旨在开发突破性的城市无人集群作战战术。美国这些研究项目表
明多无人机协同应用已经成为发展趋势,开展与其相关的研究,不仅有助于推动
集群智能的发展,而且对提高国家军事实力具有非常重要的意义。
图 1-1 “拒止环境协同作战”项目 图 1-2 “小精灵”项目
图 1-3 “低成本无人机蜂群战术”项目 图 1-4 “进攻性蜂群使能战术”项目
决策技术作为无人机的“大脑”,体现了无人机的自主性与智能性,是实现多
无人机协同应用必不可少的一部分。如图 1-5-图 1-6 所示,美国国防部在《无
人机系统路线图 2005-2030》中将无人机自主控制等级分为十级,与无人机的智
能水平相对应,包括单机自主(1-4 级)、多机自主(5-7 级)、集群自主(8-10 级)三
个层次,等级 5 以上要求无人机具备自主决策能力,能够在复杂环境下做出快速
反应。此外,2018 年美国国防部在《无人系统综合路线图 2017-2042》中再次强
调自主性技术的发展可以明显提高无人机任务执行效率,将彻底改变作战概念。
这些资料印证了决策的重要性,表明决策是无人机完成任务的重要保证。因此,
多无人机协同离不开决策技术的支撑,研究与之相关的科学问题具有前瞻性、
创新性和战略性,能够促进无人机协同应用发展,增强我国的国际竞争力。
2017…………………………2029……………………2042
近期 中期 长期
人工智能/机器学习 -加强与提供人工智能和
-加强与提供人工智能和
机器学习解决方案的公
机器学习解决方案的公
司合作
司合作
-大力应用云计算
-大力应用云计算 -加强基于增强现实
-加强基于增强现实
和虚拟现实技术的人
和虚拟现实技术的人
机交互研发
机交互研发 -持续感知
-持续感知
-高度自治
-高度自治
提高效率和有效性 -安全性和效率得到提
-安全性和效率得到提
升,如无人机空中避撞
升,如无人机空中避撞
能力和地面自动驾驶车
能力和地面自动驾驶车
安全特性得到提升
安全特性得到提升 -无人系统直接执行
-无人系统直接执行
相关操作辅助人类,
相关操作辅助人类,
如无人机作为有人战
如无人机作为有人战
机的僚机,辅助作战
机的僚机,辅助作战 -无人机机群成为
-无人机机群成为
高度协同的系统
高度协同的系统
设计者、操作者与无
人系统之间的信任 -确保人类决策的权威
-确保人类决策的权威
无人系统的武器化 -需国防部达成战略共识 -人类决定无人系统作为僚机
-需国防部达成战略共识 -人类决定无人系统作为僚机
且通过法律评估 或队友参与战斗
且通过法律评估 或队友参与战斗
图 1-5 无人机自主控制等级 图 1-6 无人机自主性综合路线图
2
第 1 章 绪论
为了提高任务完成效率,无人机需要与地面站、其他无人机等实时可靠地
传输控制指令和应用数据,而通信网络作为无人机的“耳朵和嘴巴”,是无人机
收发信息的重要途径。如图 1-7-图 1-8 所示,2014 年 DARPA 启动了“对抗环境
中的通信”项目,旨在研究抗干扰、难探测的通信技术,抵抗频谱战威胁。2016
年美国国防战略能力办公室进行了空中自主集群技术演示,其中 103 架“山鹑”
无人机通过快速交互组网,形成集群队形。2017 年初,美国空军研究实验室为
了寻求有人/无人机编队作战机载联网技术,公布了“自主网络”征询书。这些现
状表明实现多无人机协同应用还离不开通信技术的支撑。
图 1-7 “对抗环境中的通信”项目 图 1-8 空中自主集群技术演示
图 1-9 网络中心战 图 1-10 DyNAMO 项目信息覆盖云
20 世纪末,美国海军学院首次提出“网络中心战”的概念,如图 1-9 所示,
2001 年美国国防部将其正式确立为未来主要的战争模式,旨在通过网络使各个
作战系统共享态势、协同决策,发挥最大作战效能。这不仅对各国部队建设产生
了深远的影响,还有力推动了信息化作战的新军事变革。而无人机网络作为“网
络中心战”的重要组成部分,是保障各个任务执行单元互联互通的关键环节。为
了实现有人/无人机信息共享,如图 1-10 所示,2015 年 DARPA 发布了“满足任
务最优化的动态适应网络”(Dynamic Network Adaptation for Mission Optimization,
DyNAMO)项目,旨在开发网络自适应管理技术。然而无人机呈现出集群化的应
用趋势,且无人机高速移动造成网络拓扑频繁更新,通信链路不稳定,因此,根
3
天津大学博士学位论文
据无人机信息传输需求,开展无人机集群分簇、路由选择的研究,对提高网络的
稳定性和可扩展性具有非常重要的意义。
此外,为了满足无人机任务需求,需要保证高质量的通信服务。无论是军
事领域,还是民用领域,无人机与移动通信技术的结合已经成为大势所趋。如
图 1-11-图 1-12 所示,2018 年美国国际战略研究中心发布了《5G 技术将重塑创
新与安全环境》报告,指出具备高速率、高可靠、低时延、低功耗特性的第五代
(5th generation, 5G)移动通信技术能够大幅提升多无人机协同作战能力。不仅如
此,无人机的机动性在民用领域也发挥了重要作用,受到了工业界的青睐,一
方面,无人机可以作为空中移动基站或者中继,为危险应急场所或基础设施受
损区域提供按需通信服务,这方面主要包括谷歌的 Loon 项目、Facebook 的“天
网”计划、欧洲科学研究委员会资助的 Perfume 项目以及诺基亚贝尔实验室的
F-Cell 技术;另一方面,无人机可以作为空中用户,通过蜂窝网络,实现无人机
的超视距控制与信息传输,在此方面英特尔、高通、中国移动、华为等都进行了
大量试验。由此可见,无人机与移动通信技术的结合成为了各国重点关注的发
展方向。然而,通信质量不仅与信道带宽、时隙、发送功率等通信资源大小相
关,还由接收端和发送端之间的距离决定,在基于无人机的通信网络中,为了
保证吞吐量、能量/频谱效率等关键性能,需要在合理分配信道、时隙、功率
等通信资源的同时,优化无人机飞行轨迹,但是多样化的场景、多种物理约束
以及多维变量,造成资源分配与轨迹优化问题难以处理。因此,开展面向无人
机通信的资源分配与轨迹优化研究,探讨相关方法的可行性,是实现无人机与
移动通信技术双赢的有效途径,对保证无人机通信性能,推进行业发展有十分
重要的理论意义及工程价值。
图 1-11 5G 技术重构未来战场 图 1-12 无人机与移动通信网络
综上所述,多无人机协同技术是体现群体智能水平和国家科技实力的重要
标志,同时也是一项极具挑战性的研究课题,其中决策技术是实现无人机协同
控制的核心,通信技术是无人机获得信息的手段,是保障合理规划与稳定控制
4
第 1 章 绪论
的前提。因此,围绕多无人机任务决策与协同通信这一关键科学问题,开展任
务决策、集群分簇、路由选择、资源分配与轨迹优化等相关理论研究,这将对
发挥无人机个体自主性和群体涌现性,具有至关重要的理论意义及应用价值。
1.2 多无人机任务决策与协同通信研究现状
无人机在执行任务过程中,为了高效地完成任务,通常需要与地面站、其他
无人机进行信息交互。目前可用的通信技术主要有点对点直接通信、卫星通信、
蜂窝网络辅助通信、自组网四种[2],其中点对点通信无法实现远距离信息传输,
适用于单机与地面站近距离通信,具有简单、成本低的优势,并且民用场景一般
采用非授权频段,使得无人机容易受到外界干扰,通信可靠性和安全性低;卫星
通信虽然可以实现全球覆盖,但成本高、能耗大,还会产生较高的时延和损耗,
适用于全球鹰、捕食者等大型军用无人机;随着 5G 技术的发展,无人机与蜂窝
网络的结合受到了广泛关注,由于蜂窝网络可以提供几乎无处不在的连接和较高
的通信性能,因此可以远程控制无人机执行农业植保、电力巡检等任务,但是空
中用户与地面用户的共存会带来严重的干扰问题,此外,在危险应急场景及偏远
地区无法使用蜂窝网络;自组网不依靠地面基础设施,不存在控制中心,可临时
快速组网,具有抗毁性强、自愈性好等优势,在众多领域得到了广泛应用,但无
人机动态移动造成通信链路频繁更新,网络不稳定。因此,在实际应用中需要根
据无人机应用场景、通信需求选择合适的通信技术。本文考虑以下几个问题:第
一,在执行任务过程中,无人机与任务动态变化,且无人机通信距离受限,只能
与邻机通信,如何通过邻机交互完成任务决策是需要考虑的问题;第二,无人机
已经成为敌我作战、交通执法等强对抗任务中的重要力量,而对抗过程呈现多阶
段博弈的特点,如何考虑当前时刻决策对未来的影响完成任务决策也是需要解决
的问题;第三,同一任务通常需要多架无人机协同执行,且无人机具有根据任务
驱动移动的特性,随着集群规模的扩大,如何考虑无人机之间的协同关系,实现
无人机集群分簇也是需要考虑的问题;第四,无人机通信距离受限,无法与远距
离节点直接通信,如何高效地选择路由,通过多跳实现远距离信息传输是当前面
临的关键问题;第五,通信性能不仅由信道带宽、时隙、发送功率等通信资源大
小决定,还与无人机位置相关,如何对通信资源与无人机飞行轨迹进行优化,提
高通信性能是当前国内外学者关注的热点问题。因此,本文将以无人机高效完成
任务为目的,围绕无人机任务决策、集群分簇、路由选择、资源分配与轨迹优化
对相关研究现状进行综述。
5
天津大学博士学位论文
1.2.1 多无人机任务决策研究现状
多无人机任务决策是指充分考虑任务需求和无人机自身能力,以最小的任务
代价实现收益最大化。多无人机任务决策可分为面向非对抗任务和对抗任务两类,
面向非对抗任务的任务决策旨在根据任务需求,为每个任务分配合适的无人机,
实现任务收益最大;而面向对抗任务的任务决策需要考虑任务目标的对抗性以及
无人机自身能力,以己方收益最大为目标,找到最优策略。
针对面向非对抗任务的无人机任务决策问题,国内外学者开展了大量研究工
作,提出粒子群、整数规划、拍卖、联盟博弈等多种求解方法。2016 年,西北
工业大学张耀中等[3]考虑多无人机协同执行侦查任务,针对任务区域决策问题,
提出改进的粒子群方法,利用二进制矩阵对粒子进行离散化,并加入交叉变异算
子,最大化无人机收益。2018 年,葡萄牙波尔图大学 Sujit P. Baliyarasimhuni 团
队[4]针对无人机执行信息收集任务,提出基于混合整数规划的任务决策方法,实
现了网络能耗最小化。然而上述研究是在任务情况完全已知下,以地面站为单一
决策主体的集中式决策,不适用于规模较大和动态场景。为了实现以无人机为决
策主体的分布式决策,2012 年,美国麻省理工学院 Jonathan P. How 团队[5]考虑
智能体通信距离受限,针对时间敏感型目标,首次提出一致性拍卖方法
(consensus-based auction algorithm, CBAA),通过借鉴市场决策机制,采用拍卖方
式进行任务选择,基于一致性策略消解冲突,并将该方法扩展到了多任务场景。
2019 年,西北工业大学付小卫等[6]在 CBAA 基础上,研究了异构无人机任务动
态决策问题。西北工业大学段晓军等[7]考虑任务优先级,对 CBAA 方法中的随机
拍卖过程进行改进,提出两阶段拍卖方法。然而无人机在执行任务过程中存在合
作与竞争关系,博弈论作为一门研究多方在合作或竞争关系下,选择最优决策的
理论,为无人机非对抗任务决策问题提供了新的解决思路。2011 年,美国弗吉
尼亚理工大学 Walid Saad 等[8]针对无人机数据收集任务决策问题,考虑任务执行
顺序,以吞吐量和时延作为性能指标,提出基于享乐博弈的任务决策方法,将无
人机和任务作为博弈参与者,通过切换得到最优任务决策结果。2017 年,新加
坡南洋理工大学 Rajarshi 等[9]针对通信和感知距离受限下的无人机搜救任务决策
问题,考虑任务情况不确定,建立联盟博弈模型,采用最大熵方法实现了任务最
优决策。2018 年,英国克兰菲尔德大学 Inmo Jang 等[10]针对大规模智能体系统,
考虑社会抑制性,提出基于享乐博弈的任务决策方法,由每个智能体根据已有信
息自主选择,在多项式时间内实现了收敛。
上述研究中任务目标不具有对抗性,而在追踪、围捕、打击等对抗任务中,
还需要考虑任务目标的防御、攻击等对抗能力。早在 2007 年,中佛罗里达大学
6
第 1 章 绪论
Marwan A. Simaan 团队[11]就开展了敌我双方对抗目标决策问题的研究,考虑双方
每个作战单元的杀伤力、价值,提出邻居搜索方法,降低了博弈求解的复杂度。
在此基础上,2015 年,北京航空航天大学段海滨等[12]以敌我双方剩余作战能力
作为性能指标,建立攻击目标决策问题的动态博弈模型,提出基于改进的粒子群
方法求解近似纳什均衡解。同年,北京理工大学陈杰等[13]考虑敌方类型不确定,
以敌我双方导弹剩余数量和平台毁伤程度为性能指标,提出基于最佳响应的迭代
求解方法。2018 年,韩国科学技术院 Han-Lim Choi 团队[14]-[15]针对超视距敌我作
战,建立随机博弈模型,考虑导弹发射时间,以我方最小、敌方最大损伤为目标,
采用最优化方法得到最优目标决策和导弹最佳发射时间。然而上述研究只考虑了
确定环境下的任务目标决策问题,在实际应用中,对抗环境复杂多变,具有动态
不确定性,但是传统方法只适用于解决静态或小规模动态环境中的决策问题。随
着人工智能的发展,以深度强化学习为代表的智能方法在解决多无人机任务决策
问题中存在一定的潜力。2017 年,美国 OpenAI[16]在随机博弈基础上提出多智能
体深度确定性策略梯度方法,将强化学习应用于协同导航、协同围捕等场景。同
年,伦敦大学学院汪军团队联合阿里巴巴合作[17]研究了多个智能体间的合作与竞
争,建立星际争霸的随机博弈模型,提出多智能体双向协调网络;并进一步考虑
红蓝双方大规模智能体协同打击场景,提出平均场多智能体强化学习方法[18]-[19],
为智能体规划打击或移动方向。不仅如此,2019 年,美国德克萨斯大学 Frank L.
Lewis 等[20]针对多智能体协同围捕问题,建立了追逃微分博弈模型,采用自适应
动态规划方法,为各个智能体规划围捕目标及运动轨迹。
综上所述,国内外学者在多无人机任务决策方面已进行了深入探索与研究,
取得了一定成果。现有研究主要分为面向非对抗任务和对抗任务两方面,其中,
非对抗任务决策又可以分为集中式和分布式两类,集中式任务决策由地面站作
为单一决策主体,主要用于解决确定环境下的任务决策问题;分布式任务决策
由每架无人机作为决策主体,可以用于动态不确定的环境。在对抗任务决策中,
任务目标和己方存在对抗关系,双方策略互相影响,且对抗过程具有复杂博弈特
性、动态随机特性,决策难度较大。因此,无论对非对抗任务决策还是对对抗任
务决策问题的研究,都具有十分重要的意义。
1.2.2 无人机集群分簇研究现状
决策作为无人机的“大脑”,是实现协同控制的核心,其优劣会直接决定任
务执行效果。而通信作为无人机的“耳朵和嘴巴”,影响无人机的信息收发效率,
是实现无人机协同应用必不可少的一环。然而随着执行任务无人机数量的增多,
无人机集群的通信网络管理愈发困难,而且无人机的快速移动造成通信网络拓扑
7
天津大学博士学位论文
频繁更新,通信链路不稳定。此时集群分簇以其分层管理的特点成为解决该问题
的有效手段。无人机集群分簇是指考虑无人机位置、移动趋势等因素,将无人机
网络分成多个相连的区域,每个区域形成一簇,实现网络分层,并自适应调整。
1995 年,美国加州大学洛杉矶分校 Mario Gerla[21]首次提出采用分层结构提
高网络的可扩展性,并提出最小 ID 和最大度(LID/HD)两种分簇方法。以此为基
础,通过对无人机进行分簇管理,不仅可以有效降低路由复杂度,还可以在不同
簇实现通信资源的复用。近年来,研究人员先后提出多种无人机分簇方法,主要
划分为基于多参数加权和基于移动预测的分簇方法。在基于多参数加权的分簇方
法中,将距离、能耗等多个因素进行加权作为簇头选择标准。2008 年,北京航
空航天大学张军等[22]针对大规模无人机通信网络,提出两阶段分簇方法,首先由
地面站根据无人机的位置信息确定初始簇,然后在无人机移动过程中,考虑节点
间链路保持时间、节点度、剩余能量等因素进行簇的更新。2012 年,北京航空
航天大学罗喜伶等[23]将相对速度、无人机的战术值加权作为选择簇头的标准,在
编队内具有最大权重的无人机作为簇头,其他无人机作为簇成员,并进一步考虑
战场具有复杂不确定性,提出备选簇头方法,当簇头失效时,由备选簇头快速接
替簇头的任务。2017 年,韩国电子技术研究院 Jong-Hong Park 等[24]针对无人机
高速移动造成无人机与地面站链路不稳定的问题,考虑无人机能量受限,提出面
向任务的无人机簇头选择方法,所有无人机向地面站发送位置和剩余能量信息,
由地面站综合考虑无人机与地面站间距离以及无人机剩余能量选择簇头。2019
年,朝鲜大学 Sangman Moh 等[25]综合考虑簇间距离、簇内距离、剩余能量、无
人机位置建立适应度函数,提出基于粒子群的分簇方法,令无人机随机移动验证
所提方法可以降低网络能耗。然而无人机的移动性是引起网络拓扑变化频繁、间
歇性通信的主要因素,因此,有必要在分簇过程中通过无人机的移动信息对链路
进行提前预测,以减少簇的更新频率。2011 年,南京航空航天大学臧寿红等[26]
考虑无人机随机移动,提出了利用字典树结构的预测方法,将邻居集保持概率作
为簇头选择标准,无人机对比与簇头间的链路保持时间,选择最长的簇加入。2016
年,空军工程大学茹乐等[27]考虑到传统方法不适用于无人机自组织网络,将运动
稳定性和链路保持概率作为分簇标准,提出了一种生物启发的移动预测分簇方法,
通过无人机随机移动验证所提方法可以提高网络稳定性。2015 年,清华大学姜
春晓团队[28]-[29]考虑链路可用性和分区边界的影响,提出分布式无人机网关选择
方法,通过评估无人机稳定度,采用中心网关收集稳定度信息,调整分区参数,
有效应对无人机高速移动导致网络拓扑频繁更新。2019 年,姜春晓团队进一步
考虑异构云辅助的多无人机系统[30],提出基于能量消耗的网关选择方法,有效延
长了网络生存周期。
8
第 1 章 绪论
综上所述,针对无人机集群分簇问题,目前研究人员取得了丰硕的成果,提
出多种基于参数加权和基于移动预测的集群分簇方法。其中,基于参数加权的分
簇方法简单、易于实现,没有充分利用无人机的运动趋势信息。基于移动预测的
分簇方法通过邻机交互,预测链路的生存时间或概率,可以有效降低簇的切换频
率,但增加了无人机的计算负荷。因此,两种方法各有优缺点,在实际中需要根
据无人机的任务特性按需选择。
1.2.3 多无人机路由选择研究现状
由于无线信号在传播过程中不断衰减,当目的节点和源节点相距较远时,如
何选择合适的路由成为了国内外多名学者关注的热点问题。多无人机路由选择是
指选择一条从源节点到目的节点的信息传输路径,通过中间节点转发,实现远距
离通信。
在只有两跳通信的系统中,路由选择也称为中继选择,当有多架中继无人机
辅助通信时,源节点需要选择合适的中继实现信息传输。2017 年,北京航空航
天大学周锐等人[31]利用中继无人机在任务无人机和地面站间建立两跳通信网络,
提出了模糊中继选择方法,实现了任务收益最大化。2018 年,陆军工程大学姚
昌华等[32]-[33]考虑轻量型无人机能量受限,无法与卫星直接通信问题,提出了基
于势博弈和基于联盟博弈的中继选择方法,实现了通信能耗最小化。2019 年,
徐煜华团队[34]-[37]考虑多层异构无人机网络中信道资源受限,提出了基于匹配博
弈的中继选择方法,实现了网络满意度最大化。并进一步针对可变的网络拓扑,
提出快速势-匹配方法。在此基础上,中国矿业大学孙彦景等[38]研究了考虑社交
属性的无人机通信网络中继选择问题。
在多跳通信的系统中,无人机信息需要经过网络中的其他无人机多跳传输到
达目的节点。2013 年,瑞士联邦理工学院 Stefano Rosati 等[39]-[40]针对无人机到地
面站路由选择问题,将考虑机间相对速度的链路质量作为准则,提出一种改进的
优化链路状态路由方法,采用最短路径进行路由选择,实现了两架无人机的实物
演示验证。2014 年,电子科技大学王玉文等[41]针对多无人机远距离信息传输问
题,考虑无人机间距离,提出了基于移动感知的优化链路状态路由,提高了数据
包成功传输概率。2016 年,空军工程大学茹乐等[42]针对无人机移动造成网络拓
扑高动态变化问题,综合考虑距离和跳数,基于蚁群方法对动态源路由协议进行
改进,在动态网络中实现了路由高效选择。多特蒙德工业大学 Christian Wietfeld
团队[43]从安全角度,提出基于位置感知的路由协议,实现了信息可靠传输。2017
年,苏黎世联邦理工学院 Mahdi Asadpour 团队[44]针对多无人机时延容忍网络路
由选择问题,提出运动驱动的数据包转发方法,有效处理链路中断情况。韩国仁
9
天津大学博士学位论文
荷大学 Sang-Jo Yoo 等[45]针对多无人机网络路由选择问题,采用考虑链路连接时
长、跳数的最短路径方法,降低了路由更新频率。美国弗吉尼亚理工大学 Walid
Saad 团队[46]针对地面基站到核心网直传链路速率受限问题,利用多架无人机辅
助,考虑地面基站到核心网的可达速率与时延,采用基于博弈的路由选择方法,
使通信性能提高一倍。2019 年,西北工业大学唐晓等[47]提出一种航向感知的机
会路由协议,首先利用邻机和目的节点位置信息计算节点转移概率,之后令各节
点基于方向信息和转移概率选择路由,有效降低了路由寻找时间。陆军工程大学
王海等[48]针对多无人机通信网络,将能量消耗作为性能指标,对比了存储-携带-
转发路由和逐跳路由,结果显示可以通过修改逐跳路由提高能效。北京邮电大学
冯志勇团队[49]针对大规模无人机远距离通信问题,提出双层无人机通信架构,利
用多架固定翼无人机建立上层网络,作为中继辅助下层无人机通信,在此基础上,
考虑无人机位置信息以及上下层节点的连接性,提出了低时延路由方法。此外,
华盛顿大学 Raj Jain[50]、Laghouat 大学 Omar Sami Oubbati[51]、朝鲜大学 Sangman
Moh[52]、东南大学程光[53]、空军工程大学张衡阳[54]、河海大学韩光洁[55]、帕多
瓦大学 Daniele Ronzani 等[56]等都对现有无人机网络路由协议进行了综述。
综上所述,针对多无人机路由选择问题,现有研究主要分为两跳通信和多跳
通信两种场景。其中,两跳通信不需要信息经过多次转发,但需要中继无人机具
有较强的通信能力;多跳通信利用现有网络中的无人机辅助,但增加了路由寻找
的复杂性和网络开销,且前提是必须存在一条到达目的节点的路由。因此,在实
际中需要根据无人机的能力和分布情况以及任务需求合理规划,实现无人机与无
人机、无人机与地面站远距离通信。
1.2.4 多无人机资源分配与轨迹优化研究现状
通信质量不仅受信道带宽、时隙和功率等通信资源的影响,还与无人机的位
置相关。资源和轨迹合理优化是保证无人机通信性能的前提,开展与之相关的研
究具有非常重要的科学意义和工程价值。面向无人机通信的资源分配是指考虑可
用资源、通信需求,以通信性能最佳为目标,为无人机分配信道、时隙、功率
等通信资源,实现资源的有效管理和充分利用。面向无人机通信的轨迹优化是指
考虑环境中的障碍物、无人机机动能力、通信需求,以通信性能最佳为目标,为
无人机规划一条飞行路线。目前,国内外学者对面向无人机通信的资源分配与轨
迹优化问题展开了深入研究,考虑的场景主要有地面站-无人机通信、无人机作
为基站的上/下行通信、无人机辅助的上/下行协作通信以及无人机辅助的无线能
量通信等。下面首先从资源分配单个问题说起,再综述资源分配与轨迹优化现状。
根据优化机制不同,可以分为集中式和分布式两类。
10
第 1 章 绪论
1. 资源分配研究现状
常用的集中式资源分配有凸优化、动态规划等方法。2016 年,美国弗吉尼
亚理工大学 Walid Saad 团队[57]考虑无人机执行数据收集任务,针对传感器功率
和无人机资源块分配问题,在传感器节点速率需求约束下,采用改进的牛顿法,
实现传感器总能耗最小。2017 年,日本东北大学 Nei Kato 团队[58]-[59]针对无人机
与地面站时分多址通信系统中的时隙资源分配问题,提出基于小区虚拟化的空间
分割方法;并进一步考虑无人机辅助的协作通信系统[60],对帧结构进行优化,实
现了无人机远距离高吞吐量通信。为了便于求解,研究学者提出块坐标下降(block
coordinate descent, BCD)方法,将多维变量优化问题拆分为多个单维变量优化子
问题进行迭代求解,该方法具有快速收敛的特性,且能够得到局部最优解,在资
源分配中得到了广泛应用。2017 年,韩国科学技术学院 Youngnam Han 团队[61]-[62]
针对多层无人机辅助的三维蜂窝网络中频谱和功率分配问题,在 BCD 方法的基
础上,采用梯度下降法和对分法,实现了数据包传输时延最小;并进一步针对无
人机辅助的下行协作通信系统中时隙分配、基站功率分配和无人机功率分配问题
[63],在中断概率约束下,采用同样方法,实现了网络吞吐量最大。2018 年,新
加坡国立大学张瑞团队[64]-[65]针对无人机作为空中用户的上行通信系统中基站关
联和功率分配问题,提出基于 BCD与连续凸逼近(successive convex approximation,
SCA)的集中式方法和基于聚类的分布式方法,实现了空中和地面用户整体速率
最大化。北京大学宋令阳团队[66]针对下行数据卸载中的频谱分配问题,考虑宏基
站与无人机具有自私性,采用动态规划方法,实现了宏基站收入最大化。陆军工
程大学王金龙、丁国如团队[67]-[68]考虑无人机辅助的端到端(device-to-device, D2D)
社交网络,针对无人机与 D2D 用户的功率分配问题,在 D2D 用户和下行用户服
务质量的约束下,提出半分布式凸优化方法,实现了网络整体效用最大化;并进
一步考虑采用能量收集技术的无人机通信系统,针对能量收集-信息传输的时隙
分配和 D2D 用户功率分配问题[69],提出包含差分规划和黄金分割的迭代方法,
实现了网络平均吞吐量最大化;不仅如此,该团队考虑地面站与无人机通信中时
频资源块和功率分配问题[70],在 BCD 基础上,提出包含光滑逼近和梯度投影的
迭代方法,保证了信息传输的可靠性。随着 5G 技术的发展,物联网受到研究人
员的广泛关注,2019 年,南京邮电大学 Gui[71]针对无人机辅助的异构物联网中子
信道和功率分配问题,设计了不依靠干扰消除的非正交多址方案,实现了用户和
物联网设备高效的信息传输。
集中式方法需要提前已知节点位置信息,主要由控制中心完成优化,而在动
态变化的任务环境中,节点信息未知,且无人机通常具有分布式的组织特点,不
存在控制中心,因此如何对无人机通信网络进行分布式资源分配是研究的热点。
11
天津大学博士学位论文
2017 年,厦门大学肖亮团队[72]-[75]针对无人机功率分配问题,考虑信息安全传输
需求,采用强化学习方法,应对攻击者的干扰、欺骗、窃听行为。2018 年,日
本东北大学 Nei Kato 团队[76]针对无人机与 D2D 用户共存网络中的信道分配问题,
在博弈框架下提出一种令节点自主决策的分布式方法,实现了动态场景中信道快
速分配。陆军工程大学任国春等[77]-[78]为了满足无人机通信网络抗干扰传输需求,
建立博弈模型,描述出无人机与干扰者的竞争关系,采用最优化方法确定无人机
的发送功率;并进一步针对信道分配问题[79],在随机博弈框架下采用强化学习方
法,实现了恶意干扰者存在下的高效通信。2019 年,陆军工程大学徐煜华等针
对多无人机通信网络信道分配问题[80]-[81]和时隙接入问题[82],建立博弈模型,提
出 log-linear 学习方法,有效降低了无人机交互冲突。南洋理工大学 Dusit Niyato
团队[83]针对无人机辅助的边缘计算系统中资源管理及定价问题,建立博弈模型,
提出一种分层强化学习方法。
2. 资源分配与无人机轨迹优化研究现状
上述研究主要关注传统资源分配问题,而通信质量不仅由时隙、带宽、发送
功率等通信资源大小决定,还与信息发送者和接收者之间的距离相关,因此无人
机的部署位置也会影响通信性能。2014 年,墨尔本皇家理工大学 Akram
Al-Hourani 等[84]分析了城市环境中路径损耗和环境参数与无人机最优高度的关
系,并首次用公式表示出无人机到地面视距和非视距链路的概率。受此启发,国
内外学者将传统资源分配问题与无人机位置优化问题综合考虑,开展了大量研究。
2017 年,加拿大卡尔顿大学 Halim Yanikomeroglu 团队[85]针对无人机作为基站的
下行通信系统中用户关联、带宽分配和无人机位置优化问题,在回程链路容量约
束下,提出基于凸优化和粒子群的迭代方法,实现了用户通信速率最大化。2018
年,伦敦玛丽女王大学潘存华等[86]-[87]针对上行通信系统中带宽分配及无人机位
置优化问题,在速率需求约束下,提出基于凸优化的迭代方法,最小化上行传输
功率;并进一步针对无人机辅助的下行通信网络中资源块长度和无人机位置优化
问题,在时延约束下,采用相同方法,最大化解码成功率。陆军工程大学丁国如
团队[88]-[89]针对无人机功率分配和位置优化问题,考虑速率公平、视距连接及信
息因果约束,基于凸优化的迭代方法,实现了网络总速率最大化。广东工业大学
许杰等[90]针对无人机与网关多跳通信系统中带宽分配、功率分配和无人机位置优
化问题,在数据流守恒、回程速率约束下,采用相同方法,实现了网络吞吐量最
大化。不仅如此,无人机作为重要的天基平台,能够与地基和空基平台互联实现
无缝覆盖,为了推动空天地一体化网络的发展,2019 年,清华大学姜春晓团队[91]
针对空天地异构网络中子信道分配、天基用户功率分配、无人机高度优化问题,
在地基用户和空基用户服务质量约束下,提出包含拉格朗日对偶分解和凹凸过程
12
第 1 章 绪论
的迭代方法,实现了天基用户整体通信速率最大化;并进一步考虑将非正交多址
接入技术应用于无人机辅助的上行通信系统[92],针对子信道分配、物联网设备功
率分配和无人机高度优化问题,采用匹配法和基于凸优化的迭代方法,实现了网
络吞吐量最大化。
以上研究侧重于如何得到无人机的最佳部署位置,利用无人机的空间自由度
可以进一步提高通信性能,国内外学者在传统资源分配问题的基础上,考虑无人
机机动约束,对资源分配与无人机飞行轨迹优化问题开展了广泛研究。2016 年,
新加坡国立大学张瑞团队[93]针对无人机辅助的协作通信系统中发送端功率分配、
无人机功率分配和飞行轨迹优化问题,考虑信息因果约束和无人机机动约束,首
次提出将优化问题拆分为多个子问题迭代优化,并通过 SCA 方法将非凸优化子
问题转化为可以直接利用 CVX(convex programming)工具箱求解的凸优化问题,
实现了网络吞吐量最大化。以此研究成果为基础,2018 年,张瑞团队[94]-[95]针对
多无人机辅助的下行通信系统中用户关联、无人机功率分配和飞行轨迹优化问题,
采用同样的方法,实现了网络中最小的用户吞吐量最大化;并进一步考虑正交频
分多址接入系统中和最低速率约束,解决了频谱分配、无人机功率分配和飞行轨
迹的优化问题[96]-[97]。张瑞团队还首次给出固定翼无人机的能耗模型[98],以能效
作为指标开展研究[99]-[101]。不仅如此,张瑞团队还与广东工业大学许杰、张广驰、
东南大学曾勇、杨绿溪、南京理工大学束锋等研究人员合作,探讨了无人机辅助
的多播信道通信[102]、无人机辅助的无线能量传输[103]-[106]、无人机辅助的物理层
安全[107]-[111]、无人机辅助的信息缓存[112]、无人机辅助的边缘计算[113]、无人机辅
助的认知无线通信[114]等场景中的资源分配与无人机飞行轨迹优化问题。在此基
础上,韩国科学技术学院 Seongah Jeong[115]-[116]、高丽大学 Inkyu Lee[117]-[119]、陆
军工程大学王金龙、丁国如[120]-[123]、北京邮电大学尹斯星[124]、哈尔滨工业大学
吴芝路[125]-[127]、大连理工大学赵楠[128]-[129]、南昌大学杨鼎成、肖霖[130]-[132]等众
多学者也对该问题开展了深入研究。与此不同,2019 年,浙江大学蔡云龙团队
提出一种基于惩罚凹凸过程的优化方法,在无人机辅助的边缘计算[133]、安全通
信[134]-[135]、非正交多址接入[136]场景中得到应用。此外,宋令阳团队[137]-[143]综合
考虑无人机的信息感知与传输,对无人机飞行速度优化开展了研究,实现了无人
机中继网络中断概率最小化。
上述研究从集中式优化角度研究了资源分配与轨迹优化问题,但需要环境已
知,在解决动态不确定环境下的优化问题时,强化学习等分布式方法通过结合神
经网络使智能体具备自主学习能力,具有很大潜力。2017 年,美国弗吉尼亚理
工大学 Walid Saad 团队[144]-[145]针对无人机辅助的缓存管理系统中用户关联、授
权和非授权频谱分配问题,提出基于液态机的机器学习方法,首次使用回声状态
13
天津大学博士学位论文
网络预测用户内容请求分布和移动模式[146];并进一步考虑地面用户与无人机用
户共存的蜂窝通信系统,针对基站关联、无人机功率分配以及飞行轨迹优化问题
[147]-[148],提出基于回声状态网络的深度强化学习方法,实现了网络干扰、通信时
延和路径长度综合性能最小;不仅如此,该团队还针对无人机辅助的虚拟现实网
络中内容传输和缓存资源优化问题[149]-[151],将液态机与回声状态网络结合。在此
基础上,2018 年,伦敦玛丽女王大学刘元玮团队[152]-[155]针对无人机辅助的下行
通信系统中无人机功率分配和飞行轨迹优化问题,采用多智能体强化学习方法,
提高了通信性能;并进一步针对无人机飞行轨迹已知场景中用户关联、子信道分
配以及功率分配问题[156],建立随机博弈模型,提出一种结构共享的多智能体强
化学习方法。除此之外,马里兰大学 Huang[157]、北京理工大学刘驰[158]-[160]、南
京邮电大学王保云[161]-[162]等学者也对无人机通信网络进行了研究。
综上所述,无人机是未来移动通信不可或缺的一部分。当无人机作为基站、
中继、或空中用户时,利用无人机的空间自由度可以进一步提高通信性能,因此,
传统通信资源分配问题与无人机轨迹优化问题的结合具有十分重要的研究意义。
针对面向无人机通信的资源分配与轨迹优化问题,国内外学者进行了广泛深入地
研究,提出多种方法,应用于不同的无人机通信场景。其中,集中式方法具有求
解能力强、易于实现的特点,适用于确定的环境;分布式方法具有自适应强的优
势,多适用于动态变化的环境,但对无人机的智能水平要求较高。因此,两种方
法都具有研究价值。
1.2.5 多无人机任务决策与协同通信面临的难点问题
针对多无人机任务决策与协同通信问题,目前国内外学者开展了广泛深入的
研究,取得了丰硕的成果,但现有研究没有考虑以下问题:
(1)在非对抗任务决策研究工作中,随着无人机数量的增多,粒子群、整
数规划等集中式方法虽然求解能力强,但收敛速度慢,而拍卖、联盟博弈等分布
式方法的研究大多只考虑静态场景,未考虑无人机和任务数量变化带来的动态不
确定情况。在对抗任务决策研究工作中,现有研究工作大多考虑无人机单阶段决
策问题,较少考虑当前时刻决策对未来的影响。
(2)在无人机集群分簇研究工作中,现有研究工作大都是基于无人机随机
移动、互不相关的假设设计的,然而在多无人机协同执行任务过程中,无人机具
有根据任务需求移动的特性,执行同一任务的无人机具有高度相似的运动方式和
频繁的信息交互需求,因此,在无人机集群分簇中需要考虑无人机间的协同关系。
(3)在多无人机路由选择研究工作中,现有研究大多基于任意两架无人
机通信的假设设计的,没有考虑以地面站作为终点的多无人机路由选择。此外,
14
第 1 章 绪论
通信链路可承受的负载有限,当多架无人机选择相同路由传输时,势必会降低
通信效率,并且容易发生拥塞,现有研究大多没有考虑无人机之间的相互影响
关系。因此,需要考虑无人机的信息传输需求和竞争关系设计路由选择方法。
(4)在无人机资源分配与轨迹优化中,现有研究侧重于无人机辅助的静态
通信网络,对无人机辅助动态网络的研究较少。此外,无人机通常携带不同的传
感器设备,具有不同的任务和信息传输需求,现有研究大多没有考虑无人机的这
一特性。
综上所述,本文将以无人机高效完成任务为目的,围绕现有研究中未考虑的
这些问题,开展无人机任务决策、集群分簇、路由选择、资源分配与轨迹优化的
研究。
1.3 研究内容与组织结构
1.3.1 论文的研究内容
簇5
簇8
簇3 簇10
 簇6
簇9
簇4 簇2
簇7
中继无人机
信息传输路由
簇1
地面站 g 中继辅助传输
图 1-13 论文总体场景图
本文考虑图 1-13 所示的场景,以无人机高效完成任务为目的,进行如下研
究:首先,考虑地面站派出无人机集群执行任务,研究复杂任务场景下多无人机
任务决策,包括面向非对抗任务的大规模无人机任务决策和面向对抗任务的多无
人机任务决策两部分;然后,考虑随着集群规模的扩大,网络管理困难,且无人
机的快速移动造成通信网络拓扑频繁更新,通信链路不稳定,研究考虑协同关系
的无人机集群分簇,其中无人机的任务属性由任务决策提供;其次,在集群分簇
的基础上,考虑部分无人机距离地面站较远,直传链路距离和速率受限,研究多
无人机路由选择,远距离无人机需要经过多跳回传信息;最后,考虑无人机与地
15
天津大学博士学位论文
面站不存在路由,通过部署中继无人机辅助通信,研究面向无人机通信的资源分
配与轨迹优化。本文各部分关联如图 1-14 所示,基于博弈论和凸优化工具开展
研究,第二章属于任务决策问题,第三、四、五章属于无人机协同通信问题,其
中第二、三、四章均采用了博弈方法,第五章采用了凸优化方法。具体研究内容
如下:
图 1-14 论文研究框图
(1)复杂任务场景下多无人机任务决策
考虑任务决策的优劣直接决定无人机任务执行效果,研究复杂任务场景下
多无人机任务决策。首先针对面向非对抗任务的大规模无人机任务决策问题,考
虑任务需求、类型以及无人机能力建立约束条件,考虑任务重要性、执行任务的
无人机数量以及燃料消耗建立性能指标,提出基于联盟博弈的非对抗任务决策方
法,在此基础上,考虑无人机通信距离受限、飞行途中无人机失效/增加、任务
失效/增加的影响,提出任务重分配方法,通过仿真验证了所提方法的有效性。
其次,针对面向对抗任务的多无人机任务决策问题,在对抗双方策略约束下,以
己方收益最大为目标,提出基于随机博弈的对抗任务决策方法,为博弈对抗环境
下无人机决策提供有力支撑,并通过仿真对所提方法的有效性进行了验证。
(2)考虑协同关系的无人机集群分簇
随着执行任务无人机数量的增多,无人机集群的通信网络管理愈发困难,且
无人机的快速移动造成通信网络拓扑频繁更新,通信链路不稳定,进一步增加了
集群无人机通信网络管理的难度。为了解决此问题,考虑执行同一任务的无人机
具有高度相似的运动方式和频繁的信息交互需求,研究无人机集群分簇。在簇内
16
第 1 章 绪论
无人机数量和直径约束下,建立考虑无人机通信效率和任务属性的性能指标,提
出基于联盟博弈的无人机集群分簇方法,在该方法中,通过建立无人机集群分簇
问题的联盟博弈模型,设计包含无人机切换集合生成-切换操作建立-最佳切换操
作选择三个阶段的求解策略,将无人机网络分成多个相连的区域,通过仿真验证
所提方法的有效性。
(3)面向远距离信息传输需求的多无人机路由选择
考虑部分无人机与地面站直传链路通信距离和速率受限,为了满足无人机到
地面站远距离信息传输需求,研究多无人机路由选择。根据无人机与地面站以及
无人机之间链路关系建立约束条件,根据无人机到地面站的可达速率、等待时延、
能量消耗建立综合性能指标。考虑到无人机所选路由不仅影响自己的收益,也
会影响其他无人机收益,提出基于网络形成博弈的无人机路由选择方法,在该
方法中,通过建立多无人机路由选择问题的博弈模型,设计寻找无人机纯策略
和混合策略的求解算法,为每架无人机规划到地面站的信息传输路径,完成无人
机的路由选择,实现远距离信息传输,并通过仿真对所提方法的有效性进行验证。
(4)面向无人机通信的资源分配与轨迹优化
考虑无人机到地面站不存在路由,为了保证无人机通信性能,通过部署中继
无人机辅助任务无人机与地面站通信,研究面向无人机通信的资源分配与轨迹优
化。考虑任务无人机通信需求、能量受限以及中继无人机能量、机动能力受限等
约束的影响,以网络吞吐量最大为目标,对任务无人机时隙与功率、中继无人
机功率等通信资源以及中继无人机飞行轨迹进行合理优化,通过将此优化问题
划分为三个子问题迭代优化,并采用连续凸逼近将非凸子问题转化为易于求解的
凸优化问题,完成多维变量的优化,实现无路由下远距离无人机与地面站通信,
并通过仿真验证所提方法的有效性。
1.3.2 论文的组织结构
论文结构如下:
第一章:绪论。阐述无人机应用的研究背景与意义,对无人机任务决策、集
群分簇、路由选择、资源分配与轨迹优化进行国内外现状综述及总结,最后概述
论文的主要研究内容和组织结构。
第二章:复杂任务场景下多无人机任务决策。首先研究基于联盟博弈的大规
模无人机非对抗任务决策;然后考虑任务目标具有对抗性,研究基于随机博弈的
多无人机对抗任务决策。
第三章:考虑协同关系的无人机集群分簇。为了解决网络管理困难问题,提
高网络的稳定性,考虑无人机之间的协同关系,研究基于联盟博弈的无人机集群
17
天津大学博士学位论文
分簇,将无人机网络分成多个相连的区域。
第四章:面向远距离信息传输需求的多无人机路由选择。为了满足无人机到
地面站远距离信息传输需求,研究基于网络形成博弈的多无人机路由选择,通过
建立多跳协作通信网络,实现无人机信息回传。
第五章:面向无人机通信的资源分配与轨迹优化。考虑无人机到地面站不存
在路由,针对中继无人机辅助下的任务无人机与地面站通信系统,研究通信资源
与中继无人机飞行轨迹的优化方法,最大化任务无人机到地面站的吞吐量。
第六章:总结与展望。对全文研究工作进行总结,并对未来的研究工作进行
展望。
18
第 2 章 复杂任务场景下多无人机任务决策
第2章 复杂任务场景下多无人机任务决策
2.1 引言
多无人机任务决策是指充分考虑任务需求和无人机自身能力,以最小的任务
代价实现收益最大化。近年来,美国在“快速轻型自主性”和“拒止环境协同作战”
等项目以及《无人机路线图》中,着重强调了无人机自主决策能力的必要性。此
外,决策作为无人机的“大脑”,还体现了无人机的智能水平,其优劣直接决定无
人机任务执行效果。因此,研究高效的多无人机任务决策对提高无人机的自主
性与智能性具有非常重要的意义。
针对无人机任务决策的研究主要面临以下三类问题:一、随着无人机数量的
增多,集中式决策方法收敛速度慢,这将会耗费大量的时间和计算资源,无法满
足实时性要求;二、现有分布式任务决策的研究大多考虑静态场景,较少考虑无
人机和任务数量变化带来的动态不确定情况;三、为了避免人员伤亡,无人机已
经成为敌我作战、交通执法等强对抗任务中的重要力量,而对抗过程呈现多阶段
博弈的特点,现有研究工作大多考虑无人机单阶段对抗,较少考虑当前时刻决策
对未来的影响。因此,针对以上问题,本章第一部分将开展大规模无人机非对抗
任务决策的研究,接着第二部分考虑多架无人机执行对抗任务,开展多无人机对
抗任务决策的研究。
目前博弈论在不同领域得到广泛应用,取得了良好的效果,其主要用于解决
多个决策主体在合作或竞争关系下,为自己选择最优决策的问题。其中,联盟博
弈是指决策者为提高自身利益,与其他决策主体形成稳定联盟的过程,联盟博弈
为解决大规模无人机非对抗任务决策问题提供了新的思路;随机博弈是指包含
多个参与者进行的具有状态转移的多阶段博弈过程,其适用于解决多阶段对抗
任务决策问题。
总体来说,本章研究复杂任务场景下多无人机任务决策问题,主要研究内容
如图 2-1 所示。首先针对大规模无人机执行多个非对抗任务场景,考虑任务需求、
类型以及无人机能力建立无人机与任务的类型和数目关系约束,考虑任务重要性、
执行任务的无人机数量以及燃料消耗建立性能指标,研究基于联盟博弈的非对抗
任务决策方法,在此基础上,考虑无人机通信距离受限,且飞行途中存在无人机
失效/增加、任务失效/增加情况,研究任务重分配方法,解决传统任务决策方法
19
天津大学博士学位论文
收敛速度慢、不适用于动态不确定环境的问题。其次,针对无人机执行对抗任务
场景,在对抗双方攻击策略的约束下,以己方收益最大为目标,研究基于随机博
弈的对抗任务决策方法,将双方剩余对抗能力作为状态,可攻击目标作为动作,
考虑双方无人机躲避能力设计状态转移概率,采用动态规划进行求解,为对抗环
境下己方提供最优策略,解决多阶段对抗决策问题。
面向非对抗任务的大规模无人机任务决策 面向对抗任务的多无人机任务决策
问题描述 基于联盟博弈的非对抗任务
 决策 问题描述 基于随机博弈的对抗任务
决策
约束条件:
类型约束、数目关系约束 建立联盟博弈模型 约束条件:
对抗双方攻击策略约束 建立随机博弈模型
· 状态:对抗双方剩余对抗能力
· 动作:选择的攻击目标
· 立即回报:对抗双方剩余对抗
性能指标:
任务重要性、执行任务的无
人机数量以及燃料消耗 联盟形成算法
 (地面站)
无人机失效/增加、
 任务失效/增加
任务重分配算法
(无人机) 性能指标:
己方收益 能力差距
· 状态转移概率:由对抗双方无
人机躲避能力决定
基于动态规划的博弈求解算法
图 2-1 第二章研究内容结构图
本章结构安排如下:第 2.2 节针对大规模无人机执行多个非对抗任务,研究
基于联盟博弈的大规模无人机非对抗任务决策方法,并利用 Matlab 仿真验证所
提方法的有效性;第 2.3 节针对多无人机执行对抗任务,为了最大化己方收益,
研究基于随机博弈的多无人机对抗任务决策方法,采用 Matlab 工具对所提方法
进行验证;2.4 节给出本章小结。
2.2 面向非对抗任务的大规模无人机任务决策
2.2.1 任务场景
假设存在V 架无人机、M 个任务,包含搜索救援、信息收集和通信中继等
三类非对抗任务,令 .,V}表示无人机集合, ...,M}表示任务
集合,V ,要求每架无人机选择一个任务。在任务执行过程中,受到无
人机失效/增加、任务失效/增加的影响,无人机数量、任务数量可能存在变化,
在这种动态不确定的环境中,考虑任务和无人机的各种约束条件,如何为每架
无人机分配合适的任务是需要解决的难点问题。
20
第 2 章 复杂任务场景下多无人机任务决策
2.2.2 非对抗任务决策问题描述
下面给出大规模无人机非对抗任务决策问题描述。首先,考虑任务需求、类
型和无人机能力建立无人机与任务的类型和数目关系约束;其次,考虑任务重要
性、选择任务的无人机数量以及无人机燃料消耗建立性能指标;最后,建立非
对抗任务决策问题的优化模型。
1. 约束条件
(1)类型约束
令 a 表示无人机i 是否选择任务 m,将任务类型分为搜索救援、信息收集
和通信中继三类,每个任务对应一种类型,无人机根据自身能力,可以执行一
种或多种任务。因此,无人机i 与任务 m的类型约束可以表示为:
a i  (2-1)
其中, a 表示无人机i 不能选择任务 m,T 表示无人机i 可以选择的任务集
合, 表示无人机i 不能选择的任务集合。例如,不具有图像感知能力的无
人机不能执行搜索任务;完成某个任务所需燃料超过无人机的剩余燃料时,无人
机也不能选择此任务。
(2)数目关系约束
考虑每个任务至少需要若干架无人机协同执行,对无人机数目的要求与具体
任务相关,例如,在搜索任务中,单架无人机无法在短时间内完成搜索。根据任
务需求,建立约束条件:
V
 (2-2)
 a , m
i=1
其中,
num 表示任务 m所需的无人机数量,num 。当任务 m没有此项需求
m m
时,num =0。由于每架无人机最多选择一个任务,因此 a 需满足:
m
M
 (2-3)
 a i 
m=1
通过上述分析可知 a 是二进制向量:
a }, i  (2-4)
2. 性能指标
本节综合考虑任务重要性、选择任务的无人机数量以及燃料消耗,建立无
人机i 的性能指标,作为无人机i 的收益。令C 表示选择任务 m的无人机集合,
C 表示选择任务 m的无人机数量,无人机i 的收益可以表示为:
21
天津大学博士学位论文
r
i ( ,
m
u
mT
m
C (2-5)
 
 
0, otherwise
其中,d 表示无人机i 与任务 m的距离,c 表示无人机单位距离的燃料消耗。u
i,m
表示任务 m的收益,上式表明当不满足任务需求或无人机不可以执行任务 m时,
无人机的收益为零。下面给出u 的具体形式。
C 时,随着执行此任务的无人机数量增加,该任务执行效率越高,
m
任务收益越大,因此,任务 m的收益u 可以表示为:
u C , (2-6)
其中, v 表示任务 m的重要性。定义如下:
v (2-7)
其中, E 表示任务 m的紧急程度, I 表示任务 m的重要程度,
b 和
1 b 表示相应
2
的权重系数。
从式(2-6)可以看出,随着 C 的增加,任务 m的收益u 增大,从式(2-5)可
以看出,无人机的收益递减,这是因为无人机需要与其他无人机共享任务收益。
为了便于理解,假设任务收益为 100,至少需要 5 架无人机协同执行该任务,图
2-2-图 2-3 给出了任务收益和无人机收益的变化曲线,可以看出,随着选择任务
的无人机数量增加,任务收益增大,无人机收益降低。
图 2-2 任务收益变化 图 2-3 无人机收益变化
3. 非对抗任务决策优化模型
根据上述约束条件(2-1)-(2-4)和性能指标(2-5),建立无人机非对抗任务决策问
题的优化模型如下:
22
第 2 章 复杂任务场景下多无人机任务决策
V M
 ( C (2-8)
max r m,
i
{a i 1 m 1
= =
s.t. (2-1)-(2-4)
上述优化问题的目标是在满足无人机与任务的类型和数目关系约束下,为每
架无人机分配合适的任务,最大化全局收益。
本节给出了面向非对抗任务的无人机任务决策问题描述,随着无人机规模的
扩大,集中式任务决策方法收敛速度慢,不适用于大规模任务决策场景,因此
具有分布式特点的拍卖和联盟博弈方法引起了国内外学者的广泛关注。但是拍
卖方法大多需要拍卖中心或者任务“卖方”辅助,不易于实现,而联盟博弈为解
决大规模无人机非对抗任务决策问题提供了新的思路,故接下来设计基于联盟
博弈的非对抗任务决策方法。
2.2.3 基于联盟博弈的非对抗任务决策
联盟博弈又称为合作博弈,是指决策者以同盟、合作的方式与其他决策者
形成稳定联盟的过程,其中博弈是指若干个理性决策者(rational decision-maker)
通过复杂交互产生或好或坏结果的情况,通常用数学模型描述,联盟是指理性
决策者具有合作意向,希望通过形成合作组织来产生较好的结果。因此联盟博
弈要解决的主要问题是如何形成恰当的合作组织以取得期望的结果[163]。后面
将这些理性决策者称为博弈的参与者。利用联盟博弈解决无人机非对抗任务决
策问题时,首先需要对待解决的非对抗任务决策问题(2-8)建立联盟博弈模型;
然后在联盟博弈模型的基础上,设计求解策略,从而得到无人机非对抗任务决
策的解。
1. 非对抗任务决策问题的联盟博弈模型
由上述定义可知,在本节非对抗任务决策问题中,联盟表示选择同一任务的
无人机形成一个集体,共同分配合作得到的联盟收益,因此,每个任务对应一个
联盟,也就是说,非对抗任务决策将无人机划分为多个不相交的联盟分区[8],定
义 2.1 给出了非对抗任务决策问题中联盟分区的定义。
定义 2.1:在非对抗任务决策问题中,联盟分区定义为集合  =C , ,
其中C ,m[0,M ],表示无人机集群形成的第 m个不相交的联盟。集合 中的联盟满足 以及C ,m  m。
利用联盟博弈解决无人机非对抗任务决策问题时,首先需要对待解决的无
人机非对抗任务决策问题(2-8)建立联盟博弈模型。联盟博弈包括两个要素[163],
首先是需要形成联盟的参与者集合,其次是联盟收益,用来定量描述联盟的价
23
天津大学博士学位论文
值。联盟收益的定义至关重要,它决定了联盟博弈的性质,与要解决的问题紧
密相关。根据上面对联盟博弈的介绍,联盟博弈模型可以用 ( 表示。下面
给出无人机非对抗任务决策问题中参与者集合 和联盟收益u的具体定义:
(1)参与者集合
将执行非对抗任务的V 架无人机作为参与者,因此,无人机非对抗任务决策
问题的联盟博弈中参与者集合可以表示为:
.,V} (2-9)
(2)联盟收益u
考虑上述非对抗任务决策问题描述中约束条件(2-2)和任务收益(2-6)设计联
盟收益。当 C 小于 num ,不满足约束条件(2-2)时,联盟收益为零;当 C 大
m
于或等于 num ,满足约束条件(2-2)时,此时将联盟收益设置为任务收益,可由
m
式(2-6)表示。因此,对于无人机来说,各任务对应的联盟收益可以表示为:
 
 
0, m
u =
 
m
u C
C m
m (2-10)
其中,空任务的联盟收益为 0。
与非合作博弈中关注参与者的个体收益不同,联盟博弈更关注如何形成稳定
的联盟结构,因此联盟博弈模型中不包括个体参与者的动作,只有参与者和联
盟收益两个要素。以公平分配为原则,联盟收益平均分配给联盟内无人机。当
不满足约束条件(2-2)时,为了令无人机优先选择此任务,且已经选择该任务的无
人机不偏离当前联盟,将无人机收益调整如下:
r
 
 
 
 
C
 
 
mT
C
 
 
  
0, m T
 
m (2-11)
其中, 是一个比较大的常数。在无人机非对抗任务决策问题的联盟博弈中,
每架无人机以找到使自身收益最大的任务为目标:
max r (2-12)
m
这一小节建立了非对抗任务决策问题的联盟博弈模型。下一小节将介绍上述
联盟博弈模型的求解方法,计算得到非对抗任务决策结果。
2. 求解策略
24
第 2 章 复杂任务场景下多无人机任务决策
这一部分将给出上述联盟博弈的求解策略。首先介绍如何形成初始联盟分区,
然后给出稳定联盟分区的数学定义,最后介绍如何通过求解算法获得最终的稳定
联盟分区,得到非对抗任务决策结果。
(1)初始联盟分区
在非对抗任务决策问题的联盟博弈中,将每架无人机初始化为选择空任务,
并将此时的联盟分区作为初始联盟分区。
在获得初始联盟分区后,无人机个体通过离开当前联盟,加入另一个联盟来
更新任务决策结果,形成新的联盟分区。博弈中通常根据参与者的偏好关系对比
不同任务的优劣,如定义 2.2 所示。
定义 2.2:在非对抗任务决策中,对于无人机i 来说,当选择任务 m得到的无人机
收益 r 大于另一个任务m对应的无人机收益 r 时,与任务m相
比,无人机i 偏向于选择任务 m。因此无人机i 对任务的偏好关系“ ”可以定义为:
(m, C (2-13)
其中,表示等价关系, 表示弱偏好。
(2)非对抗任务决策问题中稳定联盟分区的数学定义
无人机为了形成稳定的联盟分区,会不断执行联盟切换。基于偏好关系的定
义,即定义 2.2,下面给出非对抗任务决策问题的联盟博弈中纳什稳定的联盟分
区的定义,如定义 2.3 所示。令 表示当前联盟分区,(i)表示第i 架无人机选
择的任务,C 表示第i 架无人机所属联盟。
定义 2.3:若对于 m ,无人机i 都偏好于当前所在联盟,即满足
( i , C ,则联盟分区  是纳什稳定的,即为联盟博弈(2-9)
( )
-(2-10)的解。
由定义 2.3 可以看出,纳什稳定的联盟分区意味着没有无人机可以单方面偏
离当前联盟,即从单架无人机的角度看,无法通过偏离联盟获得更大的无人机收
益。此时获得的稳定的联盟分区即为非对抗任务决策问题的解。
接下来,分析非对抗任务决策问题的联盟博弈特性。根据联盟收益是否只取
决于联盟成员,联盟博弈可以分为特征形式(characteristic form)和分区形式
(partition form)两类[163],其中,基于特征形式的联盟收益只与自身联盟成员相关,
而基于分区形式的联盟收益还与其他联盟成员相关。因此,上述非对抗任务决策
问题的联盟博弈属于特征形式。根据联盟收益是否可以在联盟中转移,联盟博弈
又可以分为不可转移效用(nontransferable utility, NTU)和可转移效用(transferable
utility, TU)两类[163],其中,不可转移效用联盟博弈中联盟收益不能转移,各个联
盟成员的收益不能直接比较,而可转移效用联盟博弈中联盟收益能够在联盟成员
25
天津大学博士学位论文
间任意转移。因此,上述非对抗任务决策问题的联盟博弈为可转移效用联盟博弈。
(3)求解算法
为了获得稳定的联盟分区,首先所有无人机选择空任务,完成非对抗任务决
策初始化,然后根据已知任务信息依次为每架无人机选择合适的任务,直到形成
稳定的联盟分区。该算法由地面站进行计算,下面给出具体步骤:
1)初始 化非对抗任务决策,所有无人机选择空任务,即 联盟分区 
 = C ,将无人机随机排序;
2)判断联盟分区是否达到纳什稳定分区,若达到纳什稳定分区,则停止迭
代,否则,迭代次数加 1,执行第 3)步;
3)按次序选择无人机,当无人机i 进行决策时,计算无人机i 选择每个任务
的收益,令无人机i 选择无人机收益最大的任务,更新联盟分区。若无人机是最
后一架决策的无人机,返回第 2)步,否则继续执行此步骤。
在上述步骤中,无人机按次序依次选择最佳任务,通过若干轮迭代,任务决
策结果稳定,得到纳什稳定的联盟分区。此算法称为非对抗任务决策的联盟形成
算法。
定理 2.1:得到纳什稳定的联盟分区后,一架新的无人机i加入,那么最多需要V +1
次迭代,能够再次形成纳什稳定的联盟分区ˆ ,其中,V 是原有无人机数量。
证明:假设新的无人机i加入前,联盟分区是纳什稳定的,即没有无人机愿意
偏离当前所在联盟。以第i 架无人机为例,无人机i 可以忍受所在联盟增加的无
人机数量为:
( ) ( )
i min max i ,C , (2-14)
 
(
 =  
C
( )
若 ( ) 0
  ,意味着无人机i 会偏离当前联盟,不符合 是纳什稳定的联盟分区
 i
前提,故  ( )  0 。
 i
假设新的无人机 i 加入联盟 C ,形成新的联盟 C 和联盟分区  ,若
 ( )  0,i C ,即联盟C 中原有无人机都可以接受新的无人机i加入,那
 i
么不需要执行任何操作,所形成的联盟分区 是纳什稳定的。若至少存在一架
无人机iˆ 满足 (ˆ) 0
  ,那么该无人机iˆ 一定属于联盟C 。若无人机iˆ 偏离联盟
 
i
C ,加入其它联盟,形成新的联盟分区  ,那么   ,也就是说,无人机
( ) 1  i
i的加入驱逐出联盟中原有的无人机iˆ ,即使另一架无人机再次加入该联盟,无
人机 i 也不会偏离所在联盟。因此,最多需要V+1 次迭代,使得  ˆ  0 ,
 
(i)
  ,即再次形成纳什稳定的联盟分区ˆ 。证毕。 ■
i
从定理 2.1 可以看出,若初始联盟分区是纳什稳定的,一架新的无人机加入
后,还可以形成纳什稳定的联盟分区,接下来证明上述求解策略肯定收敛为纳什
26
第 2 章 复杂任务场景下多无人机任务决策
稳定的联盟分区。
定理 2.2:上述非对抗任务决策问题的求解策略最终形成的联盟分区肯定是纳什
稳定的。
证明:采用归纳法证明。
当只有一架无人机时,无人机根据偏好选择使其收益最大的联盟,不会偏离,
因此,所形成的联盟分区是纳什稳定的。进一步,假设有Vˆ 架无人机,可以形成
纳什稳定的联盟分区;那么,当一架新的无人机加入,有Vˆ+1 架无人机时,根据
定理 2.1,还可以形成纳什稳定的联盟分区。
综上所述,上述非对抗任务决策问题的求解策略最终形成的联盟分区肯定是
纳什稳定的。证毕。 ■
根据定理 2.1,在上述非对抗任务决策问题的求解策略中,一架新的无人机
加入后,最多需要V +1次迭代。因此,上述非对抗任务决策问题的求解算法最
多需要V (V +1)/ 2 次迭代实现收敛。
当上述非对抗任务决策问题的求解算法收敛时,所有无人机都分配到此时的
最佳任务,即得到纳什稳定的联盟分区。之后无人机根据分配的任务,向相应任
务地点飞行。然而,在飞行途中或者任务执行过程中,受到外界以及无人机自身
因素的影响,无人机数量可能发生变化,不仅如此,部分任务可能很快被执行,
也可能失效,且无人机还可能探测到新的任务,造成任务数量变化。在这种动态
不确定的环境中,需要在地面站决策结果的基础上执行任务重分配,而地面站通
常距离任务区域较远,且获得的任务信息不及时,因此,需要设计以无人机为决
策主体的任务重分配算法。
3. 任务重分配算法
受到通信范围的限制,无人机在飞行途中或者任务执行过程中,无法直接与
所有无人机通信,即不能获得全局信息,只能通过邻机交互获得局部信息,而基
于局部信息进行任务重分配会造成决策结果存在冲突。为了解决此问题,引入冲
突消解阶段[10]。在任务重分配算法中,每次迭代包含任务选择和冲突消解两个阶
段,其中,在任务选择阶段中,每架无人机根据局部信息选择收益最大的任务;
在冲突消解阶段中,无人机在邻机范围内对任务决策结果达成一致。令  表示
i
无人机i 认为的任务决策结果,是无人机i 的局部信息,iterationi 表示无人机i 更
新 i 表示无人机i 的时间戳,statei 表示无人机i 的状态。下面设
 的次数,stamp
i
计任务重分配算法 2-1:
算法 2-1 任务重分配
//以第i 架无人机为例
27
天津大学博士学位论文
 等于地面站任务决策结果, iteration =0
1:初始化 i ,stampi =0 。当无人机i 所在联
i
盟发生变化或探测到任务变化时, statei =0 ,否则 statei =1。
2:若存在无人机处于不满意状态
//任务选择阶段
3: 若state =0
i
4: 在  中寻找收益最大的任务,假设该任务为 m*;
i
5: 若 m*   (i)
i
6: 无人机i 离开当前联盟,加入新联盟C ,更新
i
7: 更新次数加 1: iteration =iteration +1
i i ;
8: 随机产生时间戳:stamp =rand(0,1)
i ;
9: 结束
10: statei =1;
11: 结束
12: 无人机i 向所有邻机广播消息 messagei =iteration ,stamp , ,并接收所有邻
i i i
机的消息 message , neighbor
k k  i ;
//冲突消解阶段
13: 无人机i 对比接收到的所有消息,选择更新次数最大的,假设该消息来源于
邻机 k ;
14: 若 iterationk >iterationi 或者 iterationk =iterationi ,stampk  stampi
15: iterationi =iterationk ,stampi =stampk ,i =k ,statei = 0 ;
16: 结束
17:结束
上述算法的具体步骤如下:
(1)初始化 i 等于零,stampi 等于零;
 等于上述地面站任务决策结果,iteration
i
当无人机i 所在联盟发生变化或探测到任务变化时,令无人机i 处于不满意状态,
即statei =0 ,否则无人机i 对当前决策结果i 满意,即statei =1;
(2)若所有无人机处于满意状态,任务重分配算法收敛,算法结束,否则,每
架无人机执行步骤(3),以无人机i 为例;
(3)任务选择阶段:
1)无人机i 判断自己是否处于满意状态;
2)当statei =1时,意味着无人机i 对决策结果i 满意,执行步骤 5);
3)当state =0
i 时,无人机i 对决策结果i 不满意。在 中寻找收益最大的任
i
务,即arg maxC (m, C ,假设该任务为 m*。若 m*  (i),意味着无
i
人机i 加入其他联盟可以得到更高无人机收益,则离开当前联盟C ,加入新联
i
28
第 2 章 复杂任务场景下多无人机任务决策
盟C ,并且更新
 ,iterationi =iterationi +1,随机产生时间戳stampi =rand(0,1)。
i
若 m*= (i),意味着无人机i 当前所在联盟C 就是最佳的,不需要更换联盟;
i
i
4)由于无人机i 选择了可以带来最大收益的任务,无人机i 变为满意状态,
即state =1
i ;
5)无人机i 向所有邻机广播消息 messagei =iteration ,stamp , ,其中包含
i i i
无人机i 的更新次数iterationi 、时间戳stampi 、局部信息 ,并且接收所有邻机
i
的消息 message , neighbor
k k  i ,其中, neighbor
i 表示无人机i 的邻机,由是否能
够通信决定。
(4)冲突消解阶段:
1)无人机i 对比接收到的所有消息,选择更新次数最大的,假设该消息来源
于邻机k ;
2)无人机i 对比 messagei 与 messagek ,当iterationk >iterationi 或者iterationk =
iterationi 、stampk  stampi 时,意味着无人机k 的局部信息
 比
k 更有效,无人
i
机i 更改自己的更新次数、时间戳、局部信息和状态,执行如下操作:
iterationi =iterationk ,stampi =stampk ,i = k ,statei = 0 (2-15)
 中无人机i 的任务不一定是令其收益最大的任务,故无人机i 的状态变 其中,
k
为不满意。当iteration <iteration
k i 或者iterationk =iterationi 、stampk  stampi 时,意
味着无人机i 的局部信息 在邻机范围内最有效,无人机i 不需要执行任何操作。
i
基于此步骤,无人机i 在邻机范围内完成冲突消解,对任务决策结果达成一致。
返回步骤(2)。
当所有无人机都处于满意状态时,任务重分配算法达到收敛。从以上分析可
以看出,所提方法中每架无人机作为决策主体,共同完成任务重分配。在实际应
用中,无人机可以周期性与邻机交互任务决策结果,根据若干次任务决策结果不
变判断是否达到收敛。
上述定理 2.1 和 2.2 虽然只证明了地面站任务决策算法收敛,但对于以无人
机为决策主体的任务重分配算法仍然是有效的。这是因为在任务重分配中增加了
冲突消解阶段,邻机范围只有一个有效的任务选择被保留,也就是说,虽然在任
务选择阶段,所有无人机选择各自局部信息下的最佳任务,但只要无人机形成的
网络是连通的,经过邻机交互后,邻机范围内最终只有一个生存下来,因此,定
理 2.1 和 2.2 仍成立。不仅如此,即使网络不是连通的,由于选择同一任务的无
人机飞行方向相似,这些无人机仍可以保持通信。
在以无人机为决策主体的任务重分配算法中,受限于无人机通信能力,无人
机形成的网络不一定是全连通的,因此,需要考虑网络直径的影响,所需迭代次
29
天津大学博士学位论文
数为 ( ( ) 2 )
O D G V ,其中,Ddiameter (G) 为网络直径,网络直径定义为任意两架
diameter
无人机之间最短路径的最大跳数。每次迭代,所有无人机根据局部信息对比 M +1
个任务(包括空任务)可以获得的无人机收益,因此,计算开销为 O(D (G)
diameter
MV 2 )。值得注意的是,定理 2.1 是在找到纳什稳定分区后,一架新的无人机加
入最多需要V+1次迭代,然而在以无人机为决策主体的任务重分配算法中,无人
机同时决策,不必在纳什稳定分区基础上进行任务选择,因此,所需迭代次数远
远小于V (V+1)/ 2 。
2.2.4 仿真验证
在 Windows 10 操作系统中,基于 Matlab 2014a 仿真环境编写上述算法实现
仿真实验,计算机配置为 Intel(R) Core i5-2450M @2.5GHz 处理器,8G 内存。
1. 仿真参数
假设存在 15 个已知任务,任务相关参数如表 2-1 所示。存在 100 架无人
机,分为两类,其中 1-50 号无人机可以执行所有任务,51-100 号无人机可以
执行信息收集和通信中继任务,权重系数 b =0.6 , b =0.4 。
1 2
表 2-1 仿真参数
任务编号 类型 紧急程度 重要程度 至少需要的无人
机数量 num
m
1 搜索救援 1 90 100 5
2 搜索救援 2 100 90 5
3 搜索救援 3 80 100 5
4 搜索救援 4 100 90 5
5 搜索救援 5 100 80 5
6 搜索救援 6 90 90 5
7 搜索救援 7 70 100 5
8 信息收集 1 80 60 4
9 信息收集 2 60 50 4
10 信息收集 3 70 60 4
11 信息收集 4 50 50 6
12 信息收集 5 60 70 6
13 信息收集 6 70 80 6
14 通信中继 1 90 100 6
15 通信中继 2 70 90 4
30
第 2 章 复杂任务场景下多无人机任务决策
2. 仿真结果
(1)非对抗任务决策结果
为了验证地面站任务决策算法有效性,考虑上述仿真参数设置,得到任务决
策结果如表 2-2 所示,可以看出,每个任务分配到的无人机数量都满足任务需求,
此外,无人机不会分配到不能执行的任务。
表 2-2 任务决策结果
任务编号 执行任务的无人机编号 无人机平均收益
1 [42,24,7,25,48,30] 10.3665
2 [20,6,32,23,2,38] 10.8764
3 [39,37,9,41,12,11] 10.0606
4 [19,27,10,33,3,15,22,21] 8.3358
5 [28,46,45,16,4,8,44,13,34] 8.4824
6 [29,18,35,47,17,49] 10.2438
7 [31,1,14,26,5,36] 10.9974
8 [94,71,99,82,77,61] 6.8785
9 [43,83,88,93] 8.9537
10 [91,75,62,73,74,66,92,84] 6.1441
11 [96,51,64,95,52,81] 3.3882
12 [86,100,58,56,87,98] 6.1384
13 [97,40,78,50,89,68] 7.6242
14 [53,55,59,69,70,72,79,80,60] 8.2774
15 [54,57,63,65,67,76,85,90] 6.0558
为了验证以无人机为决策主体的任务重分配算法的有效性,根据上述任务决
策结果,无人机向相应任务地点飞行。在飞行途中,发现新任务 16 和 17,这两
个新任务分别需要 4 架和 6 架无人机,任务重要性分别为 80 和 100,且只有 26-75
号无人机可以执行这两个任务,无人机通信距离为 200 米。任务重分配结果如
表 2-3 所示,仿真结果表明,以无人机为决策主体的任务重分配算法是有效的。
此外,当满足任务需求后,执行任务的无人机数量越少、无人机越接近任务目标
地点,无人机平均收益越高。
表 2-3 增加任务 16 和 17 之后,任务重分配结果
任务编号 执行任务的无人机编号 无人机平均收益
31
天津大学博士学位论文
1 [7,24,25,30,45] 14.6932
2 [2,20,22,23,32,31] 12.0330
3 [11,12,37,39,41] 14.2135
4 [3,10,15,19,21,27,33] 11.2458
5 [4,8,13,16,28,44,46,6] 10.9466
6 [17,18,29,35,49] 14.3934
7 [1,5,14,26,36,9] 12.1458
8 [61,82,94,99] 14.1529
9 [43,83,88,93] 10.1533
10 [66,75,84,91,92,71] 10.1371
11 [96,51,64,95,52,81] 4.5878
12 [86,100,58,56,87,98] 7.3379
13 [97,40,78,50,89,68] 8.8237
14 [53,60,69,70,79,80,76] 12.4278
15 [63,65,67,77,85,90] 10.5053
16 [42,59,62,72,73,74,54] 8.6007
17 [47,55,38,57,34,48] 13.0092
(2)地面站任务决策算法性能评估
为了验证地面站任务决策算法性能,将所提算法与平均分配算法进行对比,
其中平均分配算法是指当满足任务需求约束后,将剩余无人机平均分配给每个任
务。图 2-4 给出不同算法下无人机平均收益,仿真结果表明,所提算法得到的无
人机平均收益较大。
图 2-4 不同算法下无人机平均收益 图 2-5 粒子群算法与所提算法的收敛时间
32
第 2 章 复杂任务场景下多无人机任务决策
进一步将所提算法与粒子群算法进行对比,图 2-5 给出两种算法的收敛时间。
仿真结果表明,当集群规模扩大时,两种算法都需要更长时间收敛,然而,对于
100 架无人机的任务决策,所提算法在 1 秒以内就可以完成决策,而粒子群算法
需要 10 秒,因此,相比于基于粒子群的任务决策算法,所提算法在求解速度上
具有较大优势。
为了验证地面站任务决策算法的收敛性,图 2-6-图 2-7 给出不同无人机规
模和任务规模下收敛性的统计结果,其中箱形图从上到下分别表示最大值、上四
分位数、中位数、下四分位数和最小值。仿真结果表明,随着无人机集群规模的
扩大,需要更多迭代实现收敛,这是因为博弈的参与者增多,需要更多迭代才能
收敛到纳什稳定的联盟分区。然而,随着任务数量的增加,迭代次数降低,这是
因为任务数量的增加使得无人机可选任务增多,任务决策结果调整次数降低。
图 2-6 不同无人机规模下收敛性 图 2-7 不同任务规模下收敛性
(3)以无人机为决策主体的任务重分配算法性能评估
图 2-8 无人机数量变化的影响
33
天津大学博士学位论文
为了验证以无人机为决策主体的任务重分配算法收敛性,首先,考虑无人机
失效或新的无人机加入对任务重分配的影响,如图 2-8 给出无人机数量变化下算
法的收敛性。仿真结果表明,当新的无人机加入时,任务重分配复杂度与新加入
的无人机个数呈正比,然而,部分无人机失效后,剩余无人机能够很快完成任务
重分配,这是因为无人机偏向于选择无人机数量较少的任务。
其次,考虑任务失效或新任务产生的影响,图 2-9 给出任务数量变化算法的
收敛性。仿真结果表明,任务失效需要的迭代次数远远大于新任务的产生,这有
两点原因,第一,执行失效任务的无人机需要从空任务开始重新选择,这些无人
机的规模决定了附加迭代次数;第二,虽然有新任务产生,但是仅当新任务带来
的无人机收益大于当前任务的无人机收益时,无人机才可能选择新任务。
图 2-9 任务数量变化的影响
2.3 面向对抗任务的多无人机任务决策
2.3.1 任务场景
上一节针对非对抗任务,研究了大规模无人机任务决策。本节考虑对抗任
务,研究小规模无人机对抗任务决策。假设红蓝两方处于超视距对抗,蓝方有
N 架无人机,分为两类,第一类无人机有 N1 架,第二类无人机有 N2 架,
blue blue blue
红方有 N 架无人机,分为两类,第一类无人机有 N1 架,第二类无人机有 N 2
red red red
架,红蓝双方每架无人机携带T 枚武器。在对抗过程的每个阶段,每架无人机
34
第 2 章 复杂任务场景下多无人机任务决策
选择对方一架无人机进行攻击,并向其发射一枚武器。当任意一方无人机全部被
消灭或者没有剩余武器时,对抗过程终止。由于无人机具有躲避能力,是否命中
存在随机性,且双方剩余能力由上一阶段博弈结果决定,因此,在这种多阶段博
弈中,考虑目标以及己方能力,以己方收益最大为目标,如何为每架无人机决策
合适的攻击目标是需要解决的难点问题。
2.3.2 对抗任务决策问题描述
令 st 表示第t 阶段红蓝双方状态, abt lue =[a 和 arted =[a
a 分别表示蓝方和红方动作,其中, a 表示攻击红方第 j 架无人机
的蓝方无人机数量, a 表示攻击蓝方第i 架无人机的红方无人机数量, Nt 表
blue
示第t 博弈阶段开始时蓝方剩余的无人机数量,N 表示红方剩余的无人机数量,
t red
R (s a a )与 ( )
blue , blue, red Rred s ,ablue,ared 表示在状态st 下,蓝方选择动作
t t t t t t t t
at ,红方选
blue
择动作a ,蓝方和红方分别得到的立即回报。红蓝双方均以己方收益最大作为
t red
目标,己方收益等于累计回报,可以表示为:
( ) T t t ( t t t )
 
J π ,π =E  R s ,a ,a
 
blue blue red a~π π 1 blue blue red
 =
blue red
t
( ) ( )
T t t t t t 
J π ,π =E  R s ,a ,a
red blue red ~  =1 red blue red
a π π
 
blue red
t (2-16)
其中, J (π π )与 J (π π )分别表示蓝方和红方的累计回报, πblue =
blue blue , red red blue , red
[π ,...,πt ,...,πT ]与 π π1 π π 表示蓝方和红方所有阶段的策略,
1 red =[ red ,..., tred ,..., Tred ]
blue blue blue
t πt 分别表示第t 阶段蓝方和红方的策略,a ~ πblue πred 表示按策略
π 与 π 与
blue red blue
π 采取动作, 为折扣因子,T 表示博弈阶段。
red
由于蓝方和红方是完全对抗关系,因此,双方立即回报相加等于零,即一
方所得是另一方所失,可以得到:
( ) ( )
Rt st at at −Rt st at at (2-17)
blue , blue, red = red , blue, red
由此得到 ( ) ( )
Jblue πblue ,πred = − Jred πblue ,πred 。
红蓝双方均以己方收益,即累计回报最大作为目标,寻找自己的最优策略,
因此,本节面向对抗任务的多无人机任务决策问题的优化模型可以描述为(2-18),
同时满足约束(2-19)-(2-22):
( )
max min J π ,π (2-18)
blue red
π π
blue red
s.t.
t st at = , t (2-19)
blue ( , blue ) 1
a A
t t
blue blue
 
t st t = , t
red ( ,ared ) 1 (2-20)
a A
t t
red red
35
天津大学博士学位论文
btlue (st ,abt lue )  0, t,abt lue (2-21)
rted (st ,arted )  0, t,arted (2-22)
其中, ( ) ( )
J π π J π π 表示蓝方的累计回报,
blue , red = blue blue, red At 表示第t 阶段蓝方
blue
可选动作集, blue ( , blue )
A 表示第t 阶段红方可选动作集,t st at 表示蓝方在状态st
t
red
下选择动作 red ( , red )
a 的概率, t st at 表示红方在状态st 下选择动作
t
blue at 的概率。
red
本节给出了面向对抗任务的多无人机任务决策问题描述,考虑到无人机具有
躲避能力,是否命中存在随机性,因此双方状态的转移也具有随机性,因此下 一
节基于随机博弈设计对抗任务决策方法。
2.3.3 基于随机博弈的对抗任务决策
随机博弈又称为马尔科夫博弈,是指包含多个参与者进行的具有状态转移
的多阶段博弈过程。利用随机博弈解决对抗任务决策问题时,首先需要对待解
决的对抗任务决策问题(2-18)建立随机博弈模型;然后在随机博弈模型的基础
上,设计求解算法,从而得到己方最优策略,即对抗任务决策问题(2-18)的解。
1. 对抗任务决策问题的随机博弈模型
随机博弈模型包含参与者、状态、动作、状态转移概率、立即回报、折扣因
子六方面,其通常表示为 A,P,R, },其中, N 表示参与者,S表示状
态,A 表示动作, P 表示状态转移概率, R 表示立即回报, 表示折扣因子。针
对上述对抗任务决策问题,各符号的具体含义如下:
(1)参与者集合 N
将蓝方和红方作为参与者,因此,对抗任务决策问题的随机博弈中参与者集
合可以表示为:
N = {blue, red} (2-23)
(2)状态S
将红蓝双方剩余战斗能力,包括每类无人机剩余数量、武器数量作为状态,
因此,第t 阶段的状态可以表示为:
s blue,1, blue,2 , red,1, red,2 , (2-24)
t = nt nt nt nt t
其中,n 和
t
blue,1 n 分别表示第t 阶段蓝方第一类和第二类无人机剩余数量,nt
t
blue,2 red,1
和 n 分别表示红方第一类和第二类无人机剩余数量,那么蓝方剩余无人机总数
t
red,2
N n n ,红方剩余无人机总数为
t t t
blue = blue,1+ blue,2 N n n 。t 表示无人机剩余
t t t
red = red,1+ red,2
武器数量,无人机在每个博弈阶段消耗一枚武器,初始阶段无人机的武器数量相
同。
36
第 2 章 复杂任务场景下多无人机任务决策
(3)动作A
将红蓝双方攻击目标的可能分配作为动作 A=A A ,其中,A 表示蓝
blue red blue
方动作集,
A 表示红方动作集,例如,
abt lue =[Nbtlue ,0,...,0]T Atblue 表示第t 阶段 red
蓝方 N 架无人机攻击红方第 1 架无人机。在第t 阶段蓝方动作集中有(N )
t
t N
t blue
blue red
种可选动作,可见红蓝双方剩余无人机数量越多,动作集合越大。由于红蓝双方
是超视距对抗[14]-[15],为了降低博弈复杂度,状态st 中只体现了不同种类无人机
的数量,因此,动作集中存在大量重复动作,例如,当红方第一架和第二架无人
机属于相同类型时,[Nt ,0,0,...,0]T 与[0,Nt ,0,...,0]T 表示相同的动作。根据以
blue blue
上分析,将蓝方第t 阶段动作简化表示为:
T
abt lue =aˆ1T ,aˆ2T  (2-25)
e aˆ e aˆ ,
Tn T + Tn T = Nt 其中,受到蓝方剩余无人机数量的限制,要求 e =[1,...,
t t
1 2 blue t
n
red,1 red,2 red,1
1]T 表示 ,维全 1 矩阵。此外,为了降低博弈复杂度,缩小动作集空间,
n aˆ 与aˆ
t
red 1 1 2
还满足 j  k j  k j  k
e a e a e a e a 。同理,可以得到红方动作。
T ˆT T ˆT , T ˆT T ˆT ,
1 1 22 2
(4)状态转移概率 P
在对抗任务决策问题中,状态转移概率 P(st ,at ,at ,st+1) 表示在状态st 下,
blue red
蓝方采取动作a ,红方采取动作a ,转移到状态st+1 的概率,由红蓝双方的命
t t blue red
中概率决定,下面给出命中概率的具体计算过程。
考虑到每类无人机的机动能力、探测能力不同,蓝方第一类无人机的躲避概
率为 P ,第二类无人机的躲避概率为 P ,红方第一类和第二类无人机的躲避概
b1 b2
率分别为
概率为: P 和
r1 P 。当蓝方k 架无人机攻击红方第一类同一架无人机时,蓝方命中
r2
( )
k
P − P (2-26)
kill,1
blue, =1 r1
k
同理,得到 Pkill,2 ,Pkill,2 ,Pkill,2 ,根据命中概率计算状态转移概率,上述命中概
blue,k red,k red,k
率属于分散攻击下的命中概率。为了便于理解,给出简单示例:假设在第t 阶段,
状态为 2, 2,3, 2, 2
st = ,表示蓝方有两类无人机各两架,红方有三架第一类无人
T
机,两架第二类无人机,每架无人机剩余两枚武器,假设蓝方采取动作
ablue =[3, 0, 0,1, 0] ,红方采取动作
t T at T ,表示蓝方利用三架无人机攻击
red =[2, 0, 3, 0]
红方第一类 1 号无人机,一架无人机攻击红方第二类 1 号无人机,而红方利用两
架无人机攻击蓝方第一类 1 号无人机,三架无人机攻击蓝方第二类 1 号无人机,
那么可以转移到的状态有 16 种,分别为
37
天津大学博士学位论文
s = 2, 2, 3, 2,1 ,s = 2, 2, 3,1,1 ,s = 2,2,2,2,1 ,s = 2, 2, 2,1,1
t+1 t+1 t+1 t+1
 T  T  T  T
T T T T
s 2,1, 3, 2,1 ,s 2,1, 3,1,1 ,s 2,1, 2, 2,1 ,s 2,1, 2,1,1
t+1 t+1 t+1 t+1
=   =   =   =  
s = 1, 2, 3, 2,1 ,s = 1, 2, 3,1,1 ,s = 1, 2, 2, 2,1 ,s = 1, 2, 2,1,1
t+1 t+1 t+1 t+1
       
T T T T
s =        
 t+1 t = 1,1, 3,1,1 ,s = 1,1, 2, 2,1 ,s = 1,1, 2,1,1
 1,1, 3, 2,1 ,s
 T T T T
 t t
+1 +1 +1 (2-27)
其中,转移到状态st+1 = 1, 2, 3,1,1 的概率为[1−(P )2 ](P )3(P )3[1−(P )],同理,
T
b1 b2 r1 r2
可以得到转移到其他 15 种状态的概率。
(5)立即回报 R
由于红蓝双方都关注于最终的胜利,给出终止状态的立即回报,其他状态的
立即回报为零。当任意一方没有剩余无人机或武器时博弈终止,令 blue = blue,1
V v
n v n ,V v n + v n 分别表示博弈终止时蓝方和红方剩余战
bFlue,1+ blue,2 bFlue,2 red = red,1 red,1 red,2 red,2
F F
斗能力的价值,v 和
blue,1 v 分别表示蓝方第一类和第二类无人机的价值,v 和
blue,2 red,1
v 分别表示红方第一类和第二类无人机的价值。终止状态下,根据红蓝双方剩
red,2
余无人机,蓝方立即回报可以表示为:
− 
2 2
 
 
V V , if V V
blue red blue red
R =
blue
− V −V if V V
2 2
,
 
red blue blue red (2-28)
由于红蓝双方是完全对抗关系,红蓝双方的立即回报值相加为零,因此,红方立
即回报可以表示为
(6)折扣因子 R − R ,该博弈属于零和随机博弈。
red = blue
折扣因子表示未来阶段的回报相对于当前阶段回报的重要程度。 =0 表示只
考虑当前回报不考虑未来回报, =1表示将未来回报和当前回报看得同等重要,
在对抗任务决策问题中,选取折扣因子 =0.9。
值得注意的是,随机博弈的解是获得每个决策阶段的纳什均衡。这一小节
建立了对抗任务决策问题的随机博弈模型,该博弈包含多个决策阶段,由于动态
规划具有从上往下分析问题、从下往上求解问题的特性,是求解多阶段博弈决策
的主要方法,因此,下一步采用动态规划对上述随机博弈进行求解。
2. 求解策略
在动态规划中,状态值函数V(st ) 指状态st 的价值,代表了从状态st 开始根
据策略(π ,π ) 选择动作得到的累计回报;动作值函数 Q(st ,at ,at )指的是状
blue red blue red
态st 下,动作(at ,at ) 的价值,代表了从状态st 、动作(at ,at ) 出发,根据策
blue red blue red
略(π ,π ) 选择动作得到的累计回报。根据贝尔曼最优方程,状态值函数和动
blue red
作值函数具有如下关系:
Q R  P V
(s ,a ,a )= (s ,a ,a )+ (s ,a ,a ,s +1) (s +1) (2-29)
t t t t t t t t t t t
blue red blue red blue red
s
t +1
38
第 2 章 复杂任务场景下多无人机任务决策
 
     
 
V(s )= max min Q(s ,a ,a )  (s ,a )  (s ,a ) (2-30)
t t t t t t t t t t
blue red blue blue red red t t
π  
  π
blue red t t
a a
blue red
其中,(2-30)是求解两个参与者的零和博弈,等价于如下两个线性规划问题的解:
max
π
t
blue ˆ
V
blue (2-31)
s.t.
a A
t t
blue blue ˆ
Q t t t  t t t V t t
(s ,a ,a ) (s ,a )  , a A (2-32)
blue red blue blue blue red red
 
btlue (st ,abt lue ) =1 (2-33)
a A
t t
blue blue
 s a  a (2-34)
btlue ( t , bt lue ) 0, bt lue
min
π
t
red ˆ
V
red (2-35)
s.t.
a A
t t
red red ˆ
Q(s ,a ,a ) (s ,a ) V , a  A (2-36)
t t t t t t t t
blue red red red red blue blue
 
rted (st ,arted ) =1 (2-37)
a A
t t
red red
rted (st ,arted )  0, arted (2-38)
在已知动作值函数 Q(st ,at ,at ) 下,上述两个线性规划问题可以采用
blue red
CVX(convex programming)等优化工具直接求解得到蓝方和红方第t 阶段的最优
策略 t* V s 。在上述对抗任务决策问题中,蓝/
π 与 *
πt ,进而得到状态值函数 ( )
t blue red
红方的目标是找到每个状态下的最优策略,最大化/最小化己方累计回报,该最
优策略就是随机博弈的解,也就是纳什均衡策略。
在随机博弈中,当前阶段参与者的策略不仅影响该阶段博弈,还影响下一阶
段的状态,从而影响未来阶段,因此,在每个阶段进行决策时,不仅需要考虑当
前阶段,还应考虑对未来阶段的影响,但是影响程度很难评估。为了解决此问题,
从最终阶段开始,向前递推,依次寻找每个状态下己方最优策略。
由(2-24)可知,每个阶段,将红蓝双方无人机剩余数量、武器数量作为状态,
由于在对抗过程中,双方剩余无人机数量和武器数量不断减少,因此,当前阶段
状态中每个变量都大于或等于未来阶段状态中的相应变量,也就是说状态的转移
是有限的。由于随机博弈终止状态的状态值函数等于立即回报,根据终止状态的
状态值函数和状态转移概率,通过(2-29)可以得到终止状态的前一决策阶段动作
值函数,进一步通过(2-30)得到终止状态的前一决策阶段己方最优策略和状态值
函数,依次往前递推,迭代计算(2-29)和(2-30),即可得到每个状态下的纳什均衡
策略。具体步骤如下:
39
天津大学博士学位论文
(1)初始化所有状态的状态值函数为零;
(2)当任意一方无人机全部被消灭或者没有剩余武器时,博弈终止,由此可以
确定哪些状态为最终状态,根据最终状态的立即回报,得到最终状态的状态值函
数,开始往前递推;
(3)令t 的取值从 1 增加到T ,每次执行(4)-(8);
(4)令 n 的取值从 0 增加到 N1 ,每次执行(5)-(8);
blue,1 blue
(5)令 n 的取值从 0 增加到 N2 ,每次执行(6)-(8);
blue,2 blue
(6)令 n 的取值从 0 增加到 N1 ,每次执行(7)-(8);
red,1 red
(7)令 n 的取值从 0 增加到 N 2 ,每次执行(8);
red,2 red
(8)根据t 、 n 、
blue,1 n 、
blue,2 n 、 n 的值,建立状态s ,通过(2-29)得到此
red,1 red,2
状态的动作值函数,进一步求解(2-30),得到此状态下的最优策略和状态值函数。
根据以上步骤得到每个状态下红蓝双方的最优策略。在实际应用中,博弈参
与者首先判断所处状态,然后根据状态选择相应的最优策略。
由于在对抗过程中,双方剩余无人机数量和武器数量不断减少,因此,博弈
阶段是有限的。此外,在单个博弈阶段中,主要通过求解(2-30)得到最优策略,
由于(2-30)是两个参与者的零和博弈,等价于两个线性规划问题,且此线性规划
问题的可行域不为空,可以直接通过优化工具箱求解,故所提方法是收敛的。
在红蓝双方对抗博弈中,共有(N1 +1)(N2 +1)(N1 +1)(N2 +1)(T 种
blue blue red red
状态,每种状态下复杂度不同,当状态 s = [n ,n ,n ,n ,t 时,蓝方
blue,1 blue,2 red,1 red,2
有 ( ) (n +n )
n + n 种动作,红方有 + 种动作,然而,考虑
(n +n ) (n n )
blue,1 blue,2 red,1 red,2 red,1 red,2 blue,1 blue,2
到同类无人机具有相同的能力,动作集空间得到大幅缩小,复杂度也有效降低,
采用 CVX 工具箱求解(2-39)的复杂度为 ( )
O x3 ,求解(2-40)的复杂度为O(y3 ) ,其
中 x为蓝方在当前状态下可选动作数量, y 为红方在当前状态下可选动作数量。
2.3.4 仿真验证
在 Windows 10 操作系统中,基于 Matlab 2014a 仿真环境编写上述算法实现
仿真实验,计算机配置为 Intel(R) Core i5-2450M @2.5GHz 处理器,8G 内存。
1. 仿真参数
为了便于分析,考虑多打少、对等对抗和少打多三种情况,每架无人机有
4 枚武器:
(1)多打少:蓝方有 5 架无人机,红方有 3 架无人机,且蓝方 5 架无人机躲
避概率为 0.5,每架无人机价值为 10,红方 3 架无人机躲避概率为 0.7,但具有
不同的价值,其中 2 架无人机价值为 10,1 架无人机价值为 15,由躲避概率可
知,蓝方单架无人机能力比红方无人机弱。
40
第 2 章 复杂任务场景下多无人机任务决策
(2)对等对抗:蓝方有 5 架无人机,红方有 5 架无人机,且红蓝双方每架无
人机的躲避概率为 0.7,价值为 10,即红蓝双方实力完全相同。
(3)少打多:蓝方有 5 架无人机,红方有 7 架无人机,且蓝方 5 架无人机躲
避概率为 0.7,其中三架无人机价值为 10,两架无人机价值为 15,红方 7 架无人
机躲避概率为 0.5,其中四架无人机价值为 10,三架无人机价值为 15,由躲避
概率可知,蓝方单架无人机能力比红方无人机强。
2. 仿真结果
(1)多打少场景
蓝方累计回报越大,代表蓝方赢的概率越高。多打少场景中红蓝双方最佳
动作如表 2-4 所示,可以看出,蓝方优先攻击红方价值高的无人机。此时,蓝方
累计回报为 13.0773,红方累计回报为-13.0773。图 2-10 进一步给出多打少场景
中蓝方躲避概率对累计回报的影响曲线,仿真结果表明,蓝方要想占据优势,必
须令己方无人机躲避概率大于 0.2。
表 2-4 多对少场景采用分散攻击仿真结果
蓝方 红方
无人机编号 目标编号 目标价值 无人机编号 目标编号 目标价值
1 1 10 1 1 10
2 1 10 2 2 10
3 2 10 3 3 10
4 3 15 - - -
5 3 15 - - -
图 2-10 多打少场景蓝方无人机躲避概率对累计回报的影响
41
天津大学博士学位论文
(2)对等对抗
对等对抗场景中蓝方和红方最佳动作如表 2-5 所示,蓝方累计回报为 0,红
蓝双方获胜的概率相同。
表 2-5 对等对抗场景采用分散攻击仿真结果
蓝方 红方
无人机编号 目标编号 目标价值 无人机编号 目标编号 目标价值
1 1 10 1 1 10
2 2 10 2 2 10
3 3 10 3 3 10
4 4 10 4 4 10
5 5 10 5 5 10
为了使蓝方获胜,考虑无人机相互配合,采用协同攻击提高命中率,当蓝方
k 架无人机协同攻击红方同一架无人机时,蓝方命中概率由分散攻击的1−(P )k
r
提升为1−(P )2k ,其中,
P 为红方无人机躲避概率。当蓝方采用协同攻击、红方
r r
仍采用分散攻击时,双方最佳动作如表 2-6 所示,此时蓝方累计回报为 3.4749,
红方累计回报为-3.4749。图 2-11 进一步给出蓝方躲避概率对己方累计回报的影
响曲线,仿真结果表明,当红蓝双方都采用分散攻击时,蓝方要想占据优势,其
无人机的躲避概率必须不低于红方;当蓝方无人机的躲避概率等于红方时,蓝方
可以通过协同攻击提高累计回报,占据优势。
表 2-6 对等对抗场景蓝方采用协同攻击仿真结果
蓝方 红方
无人机编号 目标编号 目标价值 无人机编号 目标编号 目标价值
1 1 10 1 1 10
2 1 10 2 2 10
3 2 10 3 3 10
4 2 10 4 4 10
5 3 10 5 5 10
42
第 2 章 复杂任务场景下多无人机任务决策
图 2-11 对等对抗场景蓝方无人机躲避概率对累计回报的影响
(3)少打多场景
表 2-7 少打多场景双方采用分散攻击仿真结果
蓝方 红方
无人机编号 目标编号 目标价值 无人机编号 目标编号 目标价值
1 1 10 1 1 10
2 2 10 2 2 10
3 5 15 3 3 10
4 6 15 4 4 15
5 7 15 5 4 15
- - - 6 5 15
- - - 7 5 15
少打多场景中红蓝双方最佳动作如表 2-7 所示,可以看出,双方优先攻击对
方价值高的无人机。此时,蓝方累计回报为-6.7961,这是因为与红方相比,蓝方
参与博弈的无人机数量较少。图 2-12 给出少打多场景蓝方躲避概率对累计回报
的影响曲线,仿真结果表明,蓝方采用协同攻击并没有带来较大优势,这种情况
下蓝方要想占据优势,必须令己方累计回报为正,即无人机的躲避概率大于 0.7。
43
天津大学博士学位论文
图 2-12 少打多场景蓝方无人机躲避概率对累计回报的影响
2.4 小结
本章针对复杂任务场景下多无人机任务决策问题进行了研究,获得的主要成
果如下:
(1)研究了面向非对抗任务的大规模无人机任务决策问题。在无人机与任
务的类型和数目关系约束下,考虑任务重要性、选择任务的无人机数量以及无
人机燃料消耗建立性能指标,提出基于联盟博弈的任务决策方法,并进一步考
虑飞行途中或任务执行过程中无人机数量和任务数量变化,提出以无人机为决策
主体的任务重分配方法。仿真结果表明,所提方法不仅比基于粒子群的传统方法
收敛速度快,还能根据任务或无人机变化调整任务决策结果。
(2)研究了面向对抗任务的多无人机任务决策问题。将对抗双方作为决策
主体,在对抗双方攻击策略的约束下,以己方收益最大为目标,提出基于随机博
弈的对抗任务决策方法,考虑双方无人机躲避能力分析状态的转移,采用动态规
划进行求解,得到每个状态下己方最优策略,为每架无人机分配攻击目标。仿真
结果表明,所设计的方法是有效的,且通过协同攻击可以得到更高收益。
本章节研究了多无人机任务决策,任务决策完成后,无人机需要与其他平台
进行信息交互。通信是无人机收发信息的手段,其性能直接影响任务执行效率,
开展与之相关的研究具有非常重要的意义。因此多无人机协同通信是后续章节
研究的重点科学问题。
44
第 3 章 考虑协同关系的无人机集群分簇
第3章 考虑协同关系的无人机集群分簇
3.1 引言
上一章对复杂任务场景下多无人机任务决策进行了研究,随着执行任务无
人机数量的增多,无人机集群的通信网络管理愈发困难,而且无人机的快速移动
造成通信网络拓扑频繁更新、通信链路不稳定,进一步增加了集群无人机通信网
络管理的难度。此时集群分簇以其分层管理的特点成为解决该问题的有效手段。
无人机集群分簇是指考虑无人机位置、移动趋势等因素,将无人机网络分成
多个相连的区域,每个区域形成一簇,实现网络分层,并自适应调整。由于集群
分簇具备分层管理的特点,因此可以有效解决大规模网络管理困难的问题,提高
网络的稳定性。通过集群分簇,无人机被分为簇头和簇成员两种角色,簇头无人
机负责管理簇内无人机成员,完成资源分配。然而,在多无人机协同执行任务过
程中,无人机具有根据任务移动的特性,执行同一任务的无人机具有高度相似的
运动方式和频繁的信息交互需求,现有的无人机分簇方法大都是基于无人机随机
移动、互不相关的假设设计的,没有考虑具有协同关系的无人机集群网络。因此,
本章重点展开对考虑协同关系的无人机集群分簇问题的研究。
上一章介绍了联盟博弈,其是指决策者以同盟、合作的方式与其他决策者形
成稳定联盟的过程。集群无人机的分簇过程与联盟博弈类似,因此本章采用联盟
博弈方法解决无人机集群分簇问题。
本章主要研究内容如图 3-1 所示。首先,为了保证无人机通信性能,建立簇
内无人机数量和簇的直径约束,综合考虑无人机的通信效率和任务属性建立性能
指标;其次,提出基于联盟博弈的无人机集群分簇方法,在该方法中,通过建立
无人机集群分簇问题的联盟博弈模型以及设计包含无人机切换集合生成-切换操
作建立-最佳切换操作选择三个阶段的求解策略,将无人机网络分成多个相连的
区域。
本章结构安排如下:第 3.2 节给出通信场景;第 3.3 节给出无人机集群分簇
问题描述;第 3.4 节为无人机集群分簇问题建立联盟博弈模型;第 3.5 节设计求
解策略;第 3.6 节采用 Matlab 工具,对所提方法进行验证;第 3.7 节给出本章小
结。
45
天津大学博士学位论文
通信场景 问题描述 联盟博弈模型 求解策略
多架无人机协同执行任务
约束条件: 切换集合生成
参与者:
簇内无人机数量、簇的直径
网络中的无人机集群 执行同一任务的无人机具有
高度相似的运动方式
 切换操作建立
性能指标:
联盟收益:
执行同一任务的无人机信息
交互频繁 无人机通信效率和任务属性 不满足约束,联盟收益=0;
满足约束,联盟收益=性能指标 最佳切换操作选择
图 3-1 第三章研究内容结构图
3.2 通信场景
考虑集群内存在V 架无人机执行 M 个任务,令 .,V}表示无人机集
合, O 表示执行第 m个任务的无人机集合。为了便于通信网络管理,集群内所
m
有无人机会形成 K 个簇,令 ..,K}表示簇的集合, Ck 表示第k 个簇包含
的无人机集合。一方面,考虑到簇间通信效率比簇内低,簇的数量过多时会产
生较高时延,另一方面,执行同一任务的无人机更需要频繁交互任务信息,因
此如何综合考虑集群无人机的通信效率和执行任务属性,得到最优分簇结果,完
成通信网络管理是需要解决的难点问题。图 3-2 为无人机集群分簇示意图,为
了减少簇的数量,提高通信效率,距离较近的执行任务 1 和任务 2 的无人机被
划分在一簇,如图 3-2 中的簇
机划分在一簇中。 C ,而簇
1 C 和簇C 都是将执行同一任务的无人
2 K
C
2
C
1 C
K
执行任务1的无人机
执行任务2的无人机
执行任务3的无人机
执行任务M的无人机
任务区域
图 3-2 无人机集群分簇示意图
3.3 无人机集群分簇问题描述
下面给出无人机集群分簇问题描述,首先,建立簇内无人机数量和簇的直径
约束;然后,考虑无人机通信效率和任务属性建立性能指标;最后,建立集群分
46
第 3 章 考虑协同关系的无人机集群分簇
簇问题的优化模型。
3.3.1 约束条件
1. 簇内无人机数量约束
由于通信资源有限,为保证簇内通信的有效进行,单个簇内的无人机数量不
宜过多,否则会影响通信效果。例如,在时分多址系统中,无人机数量越多,每
架无人机可用时间资源越短,其可传输的信息量也越少。因此,需要对簇内无人
机数量进行约束,即
n  n k  (3-1)
max , k
其中,n 表示第 k 个簇中的无人机数量,nmax 表示单个簇可允许的无人机最大数
k
量。
2. 簇的直径约束
簇的直径是指簇内任意两架无人机之间采用最短路径连接时通过的无人
机数目的最大值。需要注意的是,最短路径内无人机数目越多,相应的通信时
延和成本也就越高。为了降低通信时延和成本,需要对单个簇的直径进行约束,
即:
    (3-2)
k max , k
 表示第 k 个簇的直径, 表示单个簇可允许的最大直径。 其中,
k max
3.3.2 性能指标
地面站完成任务决策后,会分别指派不同组无人机执行相应的任务。考虑
到执行同一任务的多架无人机会频繁交互任务信息,因此一种可行的无人机集
群分簇方式是将执行同一任务的无人机划分为一簇。然而,当执行同一任务的
无人机数量较少、较多或零散分布时,容易导致无人机簇数量过多、簇内无人
机数量过多或簇内含有多跳链路,造成无人机通信效率降低[165]。为了控制簇
的数量、提高通信性能,本节综合考虑无人机的通信效率和任务属性,建立如
式(3-3)所示的性能指标:
F(C ) = f C  f C  1− ),k  (3-3)
1( ) + 2 ( ) ( k k k
其中, f2 (Ck ) 与无人机的任务属性相关, [0,
f1(Ck ) 与无人机的通信效率相关,
1]是权衡因子, = 1时表明以最大化通信效率为目标进行分簇,不考虑各无人
机所执行的任务属性; = 0 时表明仅将执行同一任务的无人机划分为一簇。下
47
天津大学博士学位论文
面分别给出 f C 和
1( k ) f C 的具体形式。
2 ( k )
首先,给出 f C 的具体形式,其与无人机的通信效率相关。由于簇间通
1( k )
信效率比簇内通信效率低[165],簇的数量太多会产生较高的时延,且无人机动态
移动造成簇的结构需要频繁更新,为了减少簇的数量、提高网络的稳定性,
f C 定义如下:
1( k )
( )2
n
f (C ) min P
= k  L (3-4) 1 k 2 i, j
( )
n (i, j)
k
max
其中,n 表示簇C 中无人机数量, 是簇C 中任意两架无人机直传通信链路的
k k k
集合,
P 表示簇Ck 中无人机i 与其邻机 j 之间预测的链路生存概率,链路生存概
L i, j
率是指无人机之间链路生存的可能性,引入此项的目的是提高网络的稳定性,
下面给出无人机间链路生存概率的计算方式。假设无人机i 与邻机 j 都处于动态
移动的状态,为了便于描述,无人机i 与其邻机 j 的相对移动模型[27]如图 3-3 所
示,无人机i 处于位置 A,虚线表示无人机i 的通信范围,其邻机 j 以相对速度v
i, j
从位置 B 向位置 D 移动。网络中每架无人机周期性广播 Hello 消息进行邻机交互,
无人机 j 在位置 B 和位置 C 分别接收到来自无人机i 的 Hello 消息。由于两个连
续的 Hello 消息时间间隔很小,因此,假设在单个时间间隔内无人机的相对移动
速度和移动方向保持不变,根据接收信号计算出无人机i 与无人机 j 的相对移动
速度
v 以及位置 C 与位置 D 的距离
i, j
概率: d ,得到无人机i 与无人机 j 间的链路生存
C,D
P
L
i, j d d 
C,D C,D
, T
 
 
th
v T v
i, j th i, j
d
 
1, T
C,D
 
th
v
 
i, j (3-5)
其中,T 为链路生存时间的门限值,当无人机i 与无人机 j 的移动速度和方向十
th
分接近时,相对移动速度v 趋近于 0,那么链路生存概率接近 1。
i, j
D
i
A
d
C,D
C
j B v
i, j
图 3-3 无人机i 与其邻机 j 的相对移动模型
其次,给出 f C 的具体形式,其与无人机的任务属性相关。考虑到执行
2 ( k )
48
第 3 章 考虑协同关系的无人机集群分簇
同一任务的无人机需要频繁交互任务信息,因此将执行同一任务的无人机尽可
能划分在一簇。定义 f2 (Ck ) 为:
f (C )
2 k (
n
1
=  (3-6)
(
m
其中, n 表示执行第 m个任务的整体无人机数量, n 表示簇C 中执行第 m个任
k
务的无人机数量, 表示簇C 内无人机执行任务的编号。
k f C 越大,表
2 ( k )
明同一簇内无人机所执行的任务数量越少,即执行同一任务的无人机尽可能划分
在一簇。
3.3.3 优化模型
根据上述约束条件(3-1)-(3-2)和性能指标(3-3),建立集群分簇问题的优化模型
如下:
K
  (3-7)
max F(C )
k
C1 ,C2 ,...,C 1
 K =
k
s.t. n  n k 
max ,
k
   
k max , k
上述优化问题的目标是在满足簇内无人机数量和直径约束下,考虑无人机的
通信效率和任务属性,找到合适的分簇结构,最大化网络整体性能。本节给出了
无人机集群分簇的问题描述,接下来为上述优化问题建立联盟博弈模型。
3.4 联盟博弈模型
由上一章可知,联盟博弈又称为合作博弈,是指决策者以同盟、合作的方
式与其他决策者形成稳定联盟的过程。联盟博弈要解决的问题与无人机集群分簇
问题一致。在无人机集群分簇问题中,联盟与簇等价,具有相同的含义,每个簇
对应一个联盟,也就是说,无人机集群最终会形成多个不相交的联盟,这一结构
称为联盟分区(或联盟结构)。定义 3.1 给出了无人机集群分簇问题中联盟分区的
定义。
定义 3.1:在无人机集群分簇问题中,联盟分区定义为集合 ={C ,...,C },其中
1 K
C  ,k [1,K],表示无人机集群形成的第k 个不相交的联盟。集合中的联
k
C ,k  k 。 盟满足 以及
k
49
天津大学博士学位论文
利用联盟博弈解决无人机集群分簇问题时,首先需要对待解决的无人机集
群分簇问题(3-7)建立联盟博弈模型。由上一章可知,联盟博弈模型可以用 (
表示。下面给出无人机集群分簇问题中参与者集合 和联盟收益u的具体定义:
(1)参与者集合
将网络中V 架无人机作为参与者,因此,无人机集群分簇问题的联盟博弈中
参与者集合可以表示为:
.,V} (3-8)
(2)联盟收益u
为了判断某一联盟的好坏,根据约束条件(3-1)-(3-2)和性能指标(3-3)设置联
盟收益 u。当无人机形成的簇不满足约束条件(3-1)-(3-2)时,此时形成的联盟无
效,将联盟收益设置为零;当满足约束条件(3-1)-(3-2)时,此时形成的联盟有效,
联盟收益可以由式(3-3)表示。因此,无人机形成的簇对应联盟收益可以表示为:
u(C )
k F C      
 ( ), k n n ,
=  k k max k max
0, k  otherwise
(3-9)
与非合作博弈中关注参与者的个体收益不同,联盟博弈更关注集体行为以及
如何形成稳定的联盟结构以最大化所有联盟的总收益,因此联盟博弈模型中不
包括个体参与者的动作,只有参与者和联盟收益两个要素。下面给出联盟博弈
最终目标的数学表达:
K
  , (3-10)
max u(C ) C  
 k k s
C C C
1 , 2 ,..., 1
K k=
其中, 为最终形成的稳定联盟分区,即无人机集群最优分簇结果。
s
这一小节建立了无人机集群分簇问题的联盟博弈模型。下一小节将介绍上述
联盟博弈模型的求解方法,计算得到无人机集群分簇结果。
3.5 基于联盟切换的求解策略
这一部分将给出上述联盟博弈的求解策略,首先介绍如何形成初始联盟分区
与新联盟分区,然后给出稳定联盟分区的数学定义,最后介绍如何通过求解算法,
不断生成新联盟分区,从而获得最终的稳定联盟分区,得到最优分簇结果,实现
无人机集群通信性能与任务效率最大化。
1. 初始联盟分区与新联盟分区的形成方法
在集群分簇问题中,将每架无人机初始化为一个联盟,并将此时的联盟分区
50
第 3 章 考虑协同关系的无人机集群分簇
作为初始联盟分区。
在获得初始联盟分区后,无人机个体或集体通过离开当前联盟、加入另一个
联盟来更新集群的联盟结构,形成新的联盟分区。无人机个体或集体的这种更改
联盟的行为称为切换操作(switch operation),也就是说,无人机通过切换操作来
形成新的联盟分区。
下面给出定义切换操作的数学表达式,如定义 3.2 所示。
定义 3.2:切换操作 , ( C 加入另一联盟
 定义为参与者集合 离开当前联盟 C
k l k l
C  ,C  且C  C 。因此切换操作的数学表达式可 的行为,其中,
k l l k
以写为 C 。
 , ( ,
k l l
从定义 3.2 可以看出,当 = , ( C ,
C  时,切换操作 会产生一个新联盟 =
l k l l
C 中包含的参与者为集合 ,此时集群内联盟的数量加 1;当 时,切换操
l
作 C 与C 合并,此时集群内联盟的数量减 1。在切换操作中,
 , ( 会使联盟
k l k l
需要确定执行切换操作的参与者集合 和联盟l 。为了衡量切换操作的好坏,定
义切换操作 , (
 的切换收益(switch operation gain)为:
k l
(k l ( l ) +u(Ck ) −u(Cl ) −u(Ck ) (3-11)
,
其中,C 和 C  和Cl 是切换操作后形成的新联盟,
C 是切换操作执行前的联盟,
k l k
C  = C ,C  =C 。 可以表示为
k k l l
为了对比切换操作的优劣,博弈中通常根据切换收益定义参与者的偏好关系,
如定义 3.3 所示。
定义 3.3:对于参与者来说,当切换操作
 产生的切换收益
, (
k l ( (
k l 大于
,
 , ( 对应的切换收益
另一个切换操作
k l (  ( 时,与 , ( 相比,参与
k ,l k l
者偏向于选择切换操作 , (
 。因此参与者对切换操作的偏好关系“ ”可以表示
k l
为:
 , ( (3-12)
k l
其中,表示等价关系, 表示弱偏好。
2. 稳定联盟分区的数学定义
无人机为了形成稳定的联盟分区,会不断执行切换操作。基于切换操作和
切换收益的定义,即定义 3.2 和定义 3.3,下面给出联盟博弈中纳什稳定的联
盟分区的定义,如定义 3.4 所示。
定义 3.4:若对于k  K ,  ,  ,切换操作 产生的切换
i C C k,l ({i})
k l
收益   均小于等于零,则联盟分区
( k l ({i}))
, ={C ,...,C } 是纳什稳定的,即为
1 K
联盟博弈式(3-8)-式(3-10)的解。
由定义 3.4 可以看出,纳什稳定的联盟分区意味着没有无人机可以单方面偏
51
天津大学博士学位论文
离当前联盟,即从无人机的角度看,无法通过切换操作增加所有联盟的总收益。
此时获得的稳定的联盟分区即为无人机集群分簇问题的解。
若无人机切换前和切换后网络中簇都满足约束,那么切换后整体网络性能的
变化,即式(3-7)目标函数的变化为:
K ' K
 
F(C ) − F(C )
k k
k=1 k=1 (3-13)
K ' K
 
= F(C ) + F(C ) + F(C ) − F(C ) − F(C ) − F(C )
k ' l ' j k l j
 j=1, jk ', jl ' j=1, jk, jl
= u(C ) +u(C ) − u(C ) −u(C )
k
l k l
= ( (
k,l
其中, K为切换后网络中簇的数量。从上式可以看出,切换收益反应在了目标
函数上,当切换收益大于零时,切换才是有效的,因此,无人机执行的所有切换
操作都会增加整体网络性能,即增大式(3-7)的目标函数。
接下来,分析集群分簇问题的联盟博弈特性。根据 2.2.3 节中联盟博弈分类,
集群分簇问题的联盟博弈中联盟收益只与联盟内成员相关,且切换操作的收益只
取决于两个联盟的联盟收益,与联盟收益如何在联盟成员间转移无关,因此属于
特征形式和可转移效用联盟博弈。
当两个簇构成的大联盟得到的联盟收益大于两个簇的联盟收益之和时,即
u(C C ) +u(C ),C ,C ,C (3-14)
1 1 2 1 2 1
那么,联盟博弈具有超可加性(superadditive),无人机偏向于形成大联盟。若任意
两个簇满足
u(C ) +u(C )  u(C C ,C (3-15)
1 2 1 1 1 2
那么,联盟博弈是凸的(convex)。
根据(3-14)-(3-15),本章所设计的集群分簇问题的联盟博弈在静态网络和动
态网络表现出不同的特性,下面分别进行分析。在静态网络中,互为邻居的两架
无人机链路生存概率为 1,即 f C 只取决于联盟内无人机的数量,显然, 1( k )
1( k ) f C
f C 是凸函数,并且当满足约束条件(3-1)-(3-2)时,联盟收益是单调递增的。
2 ( k )
对于两个满足约束的联盟C 和C ,若C 也满足约束,那么
k l k
(n n ) n n
 + 2  2 + 2 = + (3-16)
f (C k l k l f (C ) f (C )
1 k 2 2 2 1 k 1 l
n n n
max max max
52
第 3 章 考虑协同关系的无人机集群分簇
f (C
2 k 1 (n
 
M n
m
 
1
 n
 (3-17) = 
M
 
m
 
m
 f (C ) + f (C )
2 k 2 l
因此,u(C C ) +u(C ),故在静态网络中集群分簇问题的联盟博弈具有
k k l
超可加性,并且是凸博弈,然而无人机的协同关系和约束条件(3-1)-(3-2)限制了
大联盟的形成。
在动态网络中, f1(Ck ) 与簇内无人机之间最小的链路生存概率有关,因此,
集群分簇问题的联盟收益不是单调的,且不具有超可加性,不是凸博弈。
3. 求解算法
为了获得稳定的联盟分区,设计求解算法 3-1:
算法 3-1 求解算法
1:初始化集群分簇:每架无人机单独成簇;
//无人机i 决策,其执行任务 m 且属于簇 C
k
//无人机切换集合生成
2:初始化无人机切换集合 P ;
3:在簇
C 中找到具有邻居数最多的无人机 j ,且 j j (i, j ) ,并建立无
k
人机集合 S =i, j,k , j) ;
4:若簇 C 满足约束条件(3-1)-(3-2)
k
5: 若C \ i 满足满足约束条件(3-1)-(3-2)
k
6: P ;
7: 结束
8: 若C \ S 满足约束条件(3-1)-(3-2)
k
9: P ;
10: 结束
11:否则
12: P ;
13:结束
//切换操作建立
14:初始化切换操作 ;
15:对于每个
53
天津大学博士学位论文
16: 切换操作 ;
17: 对于簇 C 的每个邻簇
C k l
18: 若C 满足约束条件(3-1)-(3-2),且切换收益大于零
l
19: 切换操作 ;
20: 结束
21: 结束
22:结束
//最佳切换操作选择
23:找到 和l* ,其满足 , (
k l
*
24:若 中无人机都是有效的,那么无人机集合 离开簇 C ,加入簇C ,即联盟
k
* l
分区根据
C 更新
k
在上述算法中,首先每架无人机单独成簇,完成集群分簇初始化,然后集群
内每架无人机周期性执行“切换集合生成-切换操作建立-最佳切换操作选择”三个
步骤,直到形成稳定的联盟分区。下面给出具体步骤:
(1)初始化集群分簇,每架无人机单独成簇;
(2)对于任意无人机i ,i ,假设其执行第 m个任务且属于簇
 C ,周期性执
k
行“切换集合生成-切换操作建立-最佳切换操作选择”三个步骤;
1)无人机切换集合生成步骤。首先将与无人机i 一同执行切换操作的无人机
集合设为空集,即 P ;然后在簇C 中找到具有邻居数量最多的无人机 j ,且无
k
人机 j 满足 j{j (i, j) } ,并建立无人机集合 S ={i, j,k ,
(k , j) },这里的目的是为了让执行同一任务的无人机尽可能划分为一
簇;最后根据切换前后簇C 是否满足约束条件,建立不同的切换集合:当簇C 、
k k
C \i 满足约束条件(3-1)-(3-2)时,无人机切换集合为:P ;当簇C 、C \ S
k k k
满足约束条件(3-1)-(3-2)时,无人机切换集合为:P ;当无人机i 所在簇C
k
不满足上述约束条件时,无人机切换集合为: P 。
2)切换操作建立步骤。无人机只能在邻簇进行切换(包括空簇),邻簇的定义
为当两架属于不同簇的无人机互为邻居时,这两个簇为邻簇。为了降低不满足约
束的簇的数量,形成的新簇必须满足约束条件(3-1)-(3-2),且只有切换收益大于
零时,切换才是有效的,由此生成可以执行的切换操作。
3)最佳切换操作选择步骤。根据切换收益,找到执行切换操作的最佳无人机
切换集合 和邻簇l* ,若 中无人机都是有效的,那么无人机集合 离开簇C ,
k
加入簇C ,联盟分区根据C ,C 得到更新。
* k * l l
一段时间后,簇结构趋于稳定,所形成的联盟分区是纳什稳定的,此时完成
54
第 3 章 考虑协同关系的无人机集群分簇
无人机集群分簇。
 开始,所提出的基于 定理 3.1:对于静态网络,从任意满足约束的联盟分区
initial
联盟博弈的无人机集群分簇方法,总能使网络收敛到包含多个不相交联盟的分区。
证明:由于网络是静态的,那么互为邻居的两架无人机链路生存概率为 1。令
n
表示经过n次切换操作后的联盟分区,n代表所有参与者执行的切换操作总次数。
假设初始联盟分区为 ,所提方法由一系列切换操作组成,每个切换操作都
initial
将当前联盟分区 切换到另一个联盟分区 ,因此,簇的形成过程包含一系列
联盟分区更新操作:
 →  →  → (3-18)
initial 1 2
由于初始联盟分区中每个簇满足约束,经过一次切换后,新的联盟分区所有簇仍
然满足约束,依次类推,网络中簇总是满足约束。此外,每个切换操作使得所有
簇的联盟收益总和增加,由于可形成的联盟分区数量是有限的,故式(3-18)将收
敛到最终联盟分区。因此,所提出的基于联盟博弈的无人机集群分簇方法,总能
使网络收敛到包含多个不相交联盟的分区。证毕。 ■
对于动态网络,在簇的初始形成阶段,无人机存在切换频繁,当簇结构趋于
稳定后,分簇结果根据无人机的移动动态更新。
定理 3.2:如果没有无人机尝试脱离当前联盟,那么所形成的联盟分区是纳什稳
定的。
证明:假设采用所提方法形成的最终联盟分区不是纳什稳定的,则存在切换操
( ({ }))  0 ,簇
k l i C 中无人机i 将会触发切换操作,离开当前簇,加入簇
, k C ,
l
这与是联盟分区定义相矛盾,因此,所形成的最终联盟分区是纳什稳定的。
证毕。 ■
在基于联盟博弈的无人机集群分簇方法中,无人机需要对比邻簇,选择切换
收益最大的切换操作,该环节复杂度由具有最大度的无人机决定,令
D G 表
deg ree ( )
示无人机度,其中,G 表示网络拓扑, deg ree ( )
D G V ,因此,单次切换的复杂度
为 ( ( ))
O D G 。
deg ree
完成无人机集群分簇后,根据应用需求决定是否选出一架无人机作为簇头管
理簇内无人机成员。下面给出一种簇头选择策略。
为了提高簇内通信效率、降低簇头更新频率,根据无人机在簇内邻居数量和
执行同一任务的邻居数量,每架无人机根据(3-19)计算自己的权重,将权重与簇
C 中其他无人机权重进行对比,权重最大的无人机i 成为簇头。
k
ˆ ˆ ˆ +ˆ ˆ
W = c n c n (3-19)
o i 1 i 2 i
其中,nˆ 表示无人机i 在簇C 中邻居数量,nˆo 表示无人机i 在簇C 中执行同一任
i k i k
55
天津大学博士学位论文
cˆ 和cˆ 是权重因子。此时完成无人机集群的分层管理。无人机被 务的邻居数量,
1 2
分为簇头和簇成员两种角色,簇头无人机负责管理簇内无人机成员,可以由簇头
无人机寻找到地面站的路由。
3.6 仿真验证
在 Windows 10 操作系统中,基于 Matlab 2014a 仿真环境编写上述算法实现
仿真实验,计算机配置为 Intel(R) Core i5-2450M @2.5GHz 处理器,8G 内存。
3.6.1 仿真参数
仿真场景设置为 5km×5km×120m 的空域,假设无人机飞行在 100~120 米
高度执行任务。当信噪比低于门限值时,两架无人机无法通信。无人机每间隔
5秒检测所在簇是否满足约束,决定如何更新分簇结果,自适应网络拓扑的变化,
所有统计仿真结果采用蒙特卡洛仿真,进行 100 次独立的仿真实验,在每次仿
真中,每个任务至少分配一架无人机。仿真参数如表 3-1 所示。
表 3-1 仿真参数
参数 含义 参数值
V 无人机数量 100
v 无人机最大飞行速度 10m/s
max
p 无人机信号发送功率 20dBm
i
路径损耗指数 4
 2 噪声功率 -100 dBm
 信噪比门限 0dB
 簇的最大直径 2
max
HI(Hello interval) Hello 消息间隔 1s
权衡参数 10−5
T 链路生存时间门限 5
th
首先将每架无人机单独成簇,完成集群分簇初始化。然后考虑到多架无人机
协同执行同一任务,执行同一任务的无人机具有高度相似的运动方式,通过改
进参考点组移动模型(Reference Point Group Mobility model,RPGM)来模拟无人
机的运动,无人机在所执行任务周围选择位置并朝该位置飞行,并根据任务目标
56
第 3 章 考虑协同关系的无人机集群分簇
位置的改变,调整移动速度和方向。
3.6.2 仿真结果
1. 无人机集群分簇结果
为了验证所设计的无人机集群分簇方法的有效性,考虑簇内无人机数量约束
nmax = 15,图 3-4 和表 3-2 给出某一时刻的分簇结果,其中任务决策结果由 2.2
节表 2-2 给出。从图中可以看出,100 架无人机形成了 10 个簇,这 10 个簇内无
人机数量分别为 12、8、9、12、12、10、9、14、8、6。仿真结果表明,上述集
群分簇方法令每簇包含尽可能多的无人机,可以有效控制簇的数量,此外仿真
结果还表明将执行同一任务的无人机划分在一簇。
5000
任务12 任务2 簇1
4000 簇8 任务13 任务8 任务9 任务1
3000 任务5 簇2 任务14 簇6 簇4
任务11
2000
簇7
任务6
任务4 任务15
 簇5
任务7 1000
簇10
簇3
任务3
簇9
任务10
0
0 1000 2000 3000 4000 5000
x(m)
图 3-4 基于联盟博弈的集群分簇结果示意图
表 3-2 无人机集群分簇结果
任务编号 执行任务的无人机编号 簇的编号
1 [42,24,7,25,48,30] 4
2 [20,6,32,23,2,38] 1
3 [39,37,9,41,12,11] 5
4 [19,27,10,33,3,15,22,21] 2
5 [28,46,45,16,4,8,44,13,34] 3
6 [29,18,35,47,17,49] 5
7 [31,1,14,26,5,36] 10
8 [94,71,99,82,77,61] 1
9 [43,83,88,93] 6
57
天津大学博士学位论文
10 [91,75,62,73,74,66,92,84] 9
11 [96,51,64,95,52,81] 4
12 [86,100,58,56,87,98] 8
13 [97,40,78,50,89,68] 6
14 [53,55,59,69,70,72,79,80,60] 7
15 [54,57,63,65,67,76,85,90] 8
为了便于理解,上述无人机集群分簇中执行每个任务的无人机数量分布相对
均匀。接下来考虑无人机随机分配,且每个任务至少分配一架无人机,无人机在
任务周围分散分布,分析算法的性能。
2. 收敛性
为了验证所提方法的收敛性,给出不同集群规模下上述集群分簇方法收敛性,
如图 3-5 所示。图中箱形图从上到下分别表示最大值、上四分位数、中位数、下
四分位数和最小值。考虑任务数量 M =10,仿真结果表明,当V = 50 时,最小、
平均、最大需要 2、2.9、4 次迭代,然而当V = 250时,分别需要 3、4.2、6 次迭
代,这是因为随着集群规模的扩大,无人机可以执行的切换操作数量增加,为了
达到稳定网络,需要更多迭代实现收敛,此外,图 3-5 还表明随着集群规模的扩
大,要实现上述集群分簇方法收敛所需迭代次数呈现缓慢增长趋势。
图 3-5 基于联盟博弈的集群分簇方法收敛性
3. 性能评估
为了验证所设计的无人机集群分簇方法性能,首先分析任务种类、无人机最
58
第 3 章 考虑协同关系的无人机集群分簇
大移动速度以及 Hello 消息间隔对网络性能的影响;其次考虑随机游走移动模型,
进一步验证所提方法的有效性;最后将所提方法与不考虑预测机制的方案和基于
生物启发的移动预测分簇方法[27]进行对比。
图 3-6 给出任务种类不同时平均联盟收益随时间的变化,可以看出,前 10
秒网络的平均联盟收益不断增长,并且随着任务种类 M 增加,平均联盟收益变
大,这是因为执行同类任务的无人机规模降低,更可能划分在一簇。此外,当
M = 5时,无人机移动对簇的切换影响较小,平均联盟收益变化几乎不变。
图 3-6 考虑任务种类不同,网络的平均联盟收益变化曲线
图 3-7 不同的移动速度下簇的调整次数变化曲线
为了验证集群分簇后网络的稳定性,分析不同移动速度对簇的调整次数的
影响。考虑无人机三种不同的最大移动速度,分别是 max 5m/s max 10m/s
v = 、v = 、
59
天津大学博士学位论文
vmax = 20m/s ,图 3-7 给出簇的调整次数变化曲线。从图中可以看出,大约 10 秒
后三种情况簇的调整频率均有所下降,这表明上述集群分簇方法可以收敛,此外,
10 秒以后随着无人机移动,分簇结果得到更新,但更新频率较低,这一点证明
了网络的稳定性较高。
此外,Hello 消息间隔也会直接影响网络性能,图 3-8 分析了不同 Hello 消
息间隔和移动速度对网络调整次数的影响。从图中可以看出,随着 Hello 消息间
隔的增大,网络所需调整次数增加。当 Hello 消息间隔较小时,调整次数较低,
这是因为移动预测机制准确性较高;此外,当 Hello 消息间隔相同时,随着无人
机速度的增加,簇不满足约束条件的概率增高,故调整次数会增加。
250
5m/s 10m/s 15m/s 20m/s 25m/s
200
150
100
50
0 HI=0.5s HI=1s HI=2s
Hello 消息间隔
图 3-8 不同 Hello 消息间隔下,簇的调整次数
(a)改进的参考点组移动模型 (b)随机游走移动模型
图 3-9 不同移动模型下,簇的调整次数
为了不失一般性,进一步考虑随机游走移动模型,该模型中不考虑无人机的
60
第 3 章 考虑协同关系的无人机集群分簇
协同关系,每架无人机随机改变移动速度和方向,因此权衡参数  = 1。图 3-9
给出了簇的调整次数,可以看出,随机游走模型中网络频繁变化,因此,所提方
法更适用于具有协同关系的无人机集群场景。
为了验证所设计的无人机集群分簇方法性能,将所提方法与传统启发式分簇
(Traditional heuristic clustering,THC)[165]方法和基于生物启发的移动预测分簇
(Bio-inspired mobility prediction clustering,BIMPC)[27]方法进行对比,其中 BIMPC
采用运动稳定性和链路保持概率作为分簇标准。文献[49]、[166]-[167]提出利用
网络平均传输时延对考虑协同关系的分簇算法进行性能评价,图 3-10 和图 3-11
给出了相应算法的性能。
图 3-10 不同移动速度下网络平均传输时延
图 3-11 不同集群规模下网络平均传输时延
61
天津大学博士学位论文
仿真结果表明,随着最大移动速度的增加,网络平均传输时延下降,这是因
v 的增加造成无人机的相似运动更加明显,执行同一任务的无人机更可能划
max
分为一簇。但是随着集群规模的增加,执行同一任务的无人机数量增加,受到簇
内无人机数量和簇的直径约束,这些无人机被分到多个簇,因此,网络平均传输
时延增大。此外,仿真结果还表明,所提集群分簇方法的网络平均传输时延低于
THC 方法,因此,对链路生存概率的预测是有效的,且与 BIMPC 方法对比,上
述集群分簇方法可以降低 12%的网络平均传输时延。
3.7 小结
本章为了解决网络管理困难问题、提高网络的稳定性,考虑无人机的协同关
系,对无人机集群分簇问题进行了研究,获得的主要成果如下:
(1)以大规模无人机执行多个任务作为场景,建立包含簇内无人机数量和
直径的约束条件,设计移动预测机制获得无人机间的链路生存概率,综合考虑无
人机的通信效率和任务属性建立性能指标;
(2)设计基于联盟博弈的无人机集群分簇方法,在该方法中,首先建立集
群分簇的联盟博弈模型;然后分析此联盟博弈的特性,设计包含切换集合生成-
切换操作建立-最佳切换操作选择三个阶段的求解策略,通过无人机自主切换实
现簇的更新;
(3)通过仿真验证了所提方法的有效性和收敛性,并分析了无人机飞行速
度以及 Hello 消息间隔的影响,此外,与传统启发式分簇和基于生物启发的移动
预测方法进行了仿真对比,结果显示所设计的分簇方法能够有效提升通信性能。
本章研究了考虑协同关系的无人机集群分簇问题,完成分簇后,还需要考虑
远距离无人机如何与地面站通信,这是下一步亟需解决的关键问题。
62
第 4 章 面向远距离信息传输需求的多无人机路由选择
第4章 面向远距离信息传输需求的多无人机路由选择
4.1 引言
上一章研究了考虑协同关系的无人机集群分簇问题,提出基于联盟博弈的
集群分簇方法。然而当无人机与地面站相距较远时,直传链路信号衰减严重、
通信距离和速率受限,此时无人机需要选择一条到地面站的路由完成信息回传。
无人机到地面站路由选择是指根据无人机信息传输需求,合理优化无人机
到地面站的网络拓扑,为每架无人机规划一条到地面站的信息传输路径。在该网
络中,近距离无人机与地面站直接连接,远距离无人机通过近距离无人机辅助通
信实现信息回传。然而通信链路可承受的负载有限,当多架无人机选择相同路
由传输时,势必会降低通信效率,并且容易发生拥塞。现有的无人机路由选择
方法大多基于任意两架无人机通信的假设设计的,没有考虑以地面站作为终点
的多无人机回传信息场景和无人机之间相互影响关系,因此,本章将针对面向
远距离信息传输需求的多无人机路由选择问题进行研究。
无人机所选路由不仅影响自己的收益,也会影响其他无人机收益,博弈为
解决这种相互影响的多方最优决策问题提供了良好的分析工具,具备分布式执
行与自适应强等优点,其中,网络形成博弈[163]主要研究多个参与者如何选择通
信链路形成连通网络,为解决无人机路由选择问题提供了新的思路。因此,本章
采用基于网络形成博弈方法解决多无人机路由选择问题。
本章主要研究内容如图 4-1 所示。首先,根据无人机与地面站以及无人机
之间的链路关系建立约束条件,考虑无人机到地面站的可达速率、等待时延和
能量消耗建立综合性能指标,作为路由选择的依据;其次,设计基于网络形成
博弈的多无人机路由选择方法,在该方法中,通过建立多无人机路由选择的博
弈模型以及设计寻找纯策略和混合策略的求解算法,为每架无人机规划到地面站
的信息传输路径,完成无人机的路由选择,实现远距离信息传输。
本章结构安排如下:第 4.2 节给出通信场景;第 4.3 节给出多无人机路由选
择问题描述;第 4.4 节为多无人机路由选择问题建立网络形成博弈模型;第 4.5
节设计求解策略;第 4.6 节采用 Matlab 工具仿真验证所提方法的有效性。第 4.7
节给出本章小结。
63
天津大学博士学位论文
通信场景 问题描述 网络形成博弈模型 求解策略
参与者:
多无人机执行数据收集及
传输任务 约束条件:
无人机与地面站间、无人机之
间链路关系约束 向地面站传输信息的无人机
动作:
可选择的下一跳节点
( ) 包括地面站和无人机 寻找纯策略
部分无人机与地面站直传链
路通信距离和速率受限 性能指标:
无人机到地面站的可达速率、
等待时延、能量消耗 收益: 寻找混合策略
选择动作后得到的性能指标
图 4-1 第四章研究内容结构图
4.2 通信场景
假设存在V 架无人机,负责收集信息并向地面站 g 传输,令 .,V}表
 表示单位时间内无人机i 需要传输的数据包数量, 示无人机集合, B 表示无人
i i
机i 的可用带宽。为了实现高效的信息传输,远距离无人机通过多跳链路的方
式完成信息回传,形成路由后,网络中的转发无人机采用解码转发协作通信方
式。然而,通信链路可承受的负载有限,每架无人机如何选择到地面站的路由,
形成以地面站为根节点的树形多跳通信网络是需要解决的难点问题。图 4-2
给出了无人机选择路由后与地面站形成的网络,该网络是以地面站为根节点的
树形多跳通信网络,其中无人机 1、5、7 距离地面站较近,选择直接通信,其余
七架无人机则由于距离地面站过远,通过选择合适的路由与地面站建立连接。
3
2
 6
4
1
5
 8
7 9
10 距离受限
地面站 g
图 4-2 无人机与地面站形成的网络示意图
4.3 多无人机路由选择问题描述
下面给出多无人机路由选择问题描述,首先根据无人机与地面站以及无人机
之间的链路关系建立约束条件;然后考虑无人机到地面站的可达速率、等待时
64
第 4 章 面向远距离信息传输需求的多无人机路由选择
延和能量消耗建立综合性能指标,作为路由选择的依据;最后给出多无人机路
由选择问题的优化模型。
4.3.1 约束条件
定义α ={i g ,i 和β ={i j ,i 表示链路关系,其中,α表示所有
, ,
无人机与地面站之间的链路关系,若无人机i 选择与地面站 g 直接连接,则 , 1
 = ,
i g
 , = 0 ;β表示各个无人机之间的链路关系,若无人机i 选择无人机 j 作为下 否则
i g
一跳节点,则
此需要满足 = ,否则
, 1
i j = 。由以上分析, 和
, 0
i j i,g 为二进制变量,因
i, j
i,g 0,1, i, j 0,1 i  (4-1)
为了保证无人机与地面站连通,所形成的网络需要至少有一架无人机与地面
站 g 直接连接,因此, 还需要满足:
i,g
V
 (4-2)
  1
i,g i=1
此外,每架无人机均有传输信息的需求,其需要将信息传输给下一跳节点,
即地面站或者另外一架无人机。考虑到每架无人机只选择一条路由,信息只能向
一个节点流出,因此 和  需要满足:
i,g i, j
V
  (4-3)
 +  =1 i 
i,g i, j
 j=1, ji
此外,为了避免由地面站和无人机组成的通信网络形成环路,限制该通信网
络中只存在V 条链路:
V V V
  (4-4)
 +  =V
 i,g i, j
i=1 i=1 j=1
采 用 有 向 图 G( 表 示 由 地 面 站 和 无 人 机 组 成 的 通 信 网 络 , 其 中
V,g}表示由V 架无人机和地面站 g 组成的顶点集合, 表示连接不
同顶点的有向边集合。因此,有向边(i, j) 表示信息从节点i 传输到节点 j ,此
时节点 j 是无人机i 的下一跳节点。由此可见,集合 可以由无人机与地面站之
间的链路关系 i g i
α ={ ,  以及无人机之间的链路关系
,
定。 β ={i j ,i 确
,
65
天津大学博士学位论文
4.3.2 性能指标
首先给出无人机i 到地面站 g 信息传输路由 q 的定义,然后考虑无人机到地
i
面站的可达速率、等待时延和能量消耗建立综合性能指标,作为路由选择的依
据。
定义 4.1:无人机i 到地面站 g 的路由 q 由 中顶点i i 间的链路组成,其中,
1,..., K i
i i 代表无人机i ,i =g 代表地面站 g ,并且对于任意的 k 1,...,K −1,直传链
1=
K
( , )
i i +  。
k k 1
1. 综合性能指标
这一部分将考虑无人机到地面站的可达速率、等待时延和能量消耗等因素
的影响,建立无人机i 选择路由 q 的综合性能指标。可达速率 R (q ,G) 是指单
i i i
位时间内无人机i 通过路由 q 可以传输至地面站的最大信息量, R (q ,G) 越大,
i i i
说明该条路由可以传输的信息量也越大;等待时延i (qi ,G) 是指无人机i 通过路
由 q 向地面站信息传输过程中的等待传输时间,当无人机需要向地面站传输发
i
送的数据量较大时,等待时延越大;能量消耗 E (q ,G) 是指无人机i 通过路由
i i q
i
向地面站信息传输过程中通信网络所消耗的能量,由于网络内各架无人机的能
量有限,因此能量消耗不能过大。通过以上分析,定义无人机i 选择路由 q 的
i
综合性能指标:
f (q ,G)
i i =
 
1i
R (q ,G)
 
i i
 
  i   i
 (q ,G) E (q ,G)
2 3
   
i i i i (4-5)
其中, f (q ,G) 表示无人机i 所选路由的性能,取决于所形成的网络拓扑, 、
i i 1i
 和 是权重因子, 1i +2i +3i =1。下面分别给出可达
    且满足
1i , 2i , 3i [0,1] 2i 3i
速率、等待时延和能量消耗的表达形式。
2. 可达速率
无人机i 到地面站选择路由 q 的可达速率 R (q ,G) 等于路由中所有直传链路
i i i
的最小可达速率。也就是说,当无人机i 的发送信息经由路由 q ,通过 K −1跳传
i
输到地面站 g 时,所选路由的可达速率 R (q ,G) 为 K −1跳直传链路中的最小可
i i
达速率,可以表示为:
R (q ,G) = min R (4-6)
i i k K i ,i
=1,..., −1 k k 1
+
其中,R
i ,i
k k +1 i i + 的可达速率,ik  ,i  ,k 代表第k 跳,
是直传链路( , )
k k 1 k +1
K 是路由 q 内包含的无人机数量。
i
直传链路(i ,i + ) 的可达速率
k k 1 R
i ,i
k k +1 由直传链路的信噪比决定。信噪比定义为
接收功率与噪声功率的比值,接收端
i + 的接收功率由发送端ik 的发送功率和路
k 1
66
第 4 章 面向远距离信息传输需求的多无人机路由选择
径损耗决定,而路径损耗为信号在信道中传播的损耗程度。下面首先给出无人机
到地面站的可达速率,即 +1=
i g ,然后给出无人机到无人机直传链路的可达速率,
k
i  。 即
k+1
(1)无人机到地面站直传链路的可达速率(i g )
+1= k
为了得到无人机到地面站直传链路的可达速率,首先计算路径损耗。由于信
号在不同信道中传播时的损耗程度不同,而无人机与地面站间直传链路受到任务
环境、无人机高度与障碍物等因素的影响,具有随机性,通常考虑 视距
(line-of-sight, LoS)链路和非视距(non-line-of-sight, NLoS)链路概率信道模型[46]。
直传链路 (i , g ) 为 LoS 链路的概率可以写为:
k
P
LoS
i ,g
k = 1
1+b exp(−b [ −b ])
2 1 2 (4-7)
其中, arcsin h / d i 与地面站 g
b 和  = 表示无人机
b 是与环境相关的常量, ( )
1 i i ,g k
2
k k
之间的仰角, h 是无人机
i 的高度,
i
k
k d 是无人机i 与地面站 g 之间的距离。此
i ,g k
k
时直传链路( , ) , 1 ,
i g 为 NLoS 链路的概率是 PNLoS = − PLoS 。
 k i g i g
 k k
信号在 LoS 链路和 NLoS 链路的路径损耗[139]可以分别表示为:
L (dB)=20log(d )+20log(f )+20log
LoS
i ,g i ,g c
 
 c 
k k (4-8)
4  +
L (dB)=20log(d )+20log(f )+20log
NLoS
i ,g i ,g c NLoS
 
 c 
k k (4-9)
其中, f 是无人机通信系统载波频率,c是光速,
 是 NLoS 链路的额外损
c NLoS
耗,其取值与环境相关。因此直传链路(i , g ) 的平均路径损耗为:
k
L = P L + P L (4-10)
LoS LoS NLoS NLoS i ,g i ,g i ,g i ,g i ,g
k k k k k
根据信噪比的定义与路径损耗的表达式(4-10),直传链路(i , g) 的信噪比r
k
 k
i ,g
可以表示为:
p
r
= i
k
i g L
, 10 /10 2
k ik g 
, (4-11)
其中, p 为无人机i 的发送功率, 2 为噪声功率。
i
k
k
基于直传链路(i , g) 的信噪比r ,相应的可达速率
k i ,g
k R 可以表示为:
i ,g
k
R , = B log2 (1+ r , ) (4-12)
i g i i g
k k k
其中, i 的可用带宽。
B 为无人机
i k
 k
当对于与地面站 g 直接通信的无人机i ,仅需要经过一跳,即 ,i = i 时,
, =1
i g k
67
天津大学博士学位论文
无人机i 选择路由 q 的可达速率等于无人机i 到地面站 g 直传链路的可达速率:
i
Ri (qi ,G) = Ri g (4-13)
,
然而当无人机i 不与地面站 g 直接连接,即 i,g =0 时,需要考虑无人机i 选择
路由
q 到地面站 g 所经过的所有直传链路。
i
i  ) (2)无人机之间直传链路的可达速率(
k+1
机间通信通常采用自由空间信道模型[46],[139]。因此直传链路 ( , )
i i 的路径
k k +1
损耗为:
  
4
L (dB) 20log(d )+20log(f )+20log
=  
i ,i i ,i c
 c 
k k +1 k k +1 (4-14)
其中, i 与无人机i 之间的距离。直传链路
d 是无人机
i ,i
k k +1
k k +1
可以表示为: ( , )
i i 的信噪比r
k k +1 i ,i
k k +1
p
r
= i
k
i ,i 10L /10 2
 
k k +1 ik ,ik +1 (4-15)
其中, p 为无人机i 的发送功率。
i k
k
基于直传链路 ( , )
i i 的信噪比r ,相应的可达速率
k k +1 i ,i
k k +1 R 可以表示为:
i ,i
k k +1
R , = B log2 (1+ r , ) (4-16)
i i i i i
k k +1 k k k +1
3. 等待时延
假设路由内的各架无人机均采用解码转发协作通信方式,即每个转发无人机
将接收到的信号先解码再编码发送。考虑将路由中每架无人机近似为 M/D/1 队
列系统,采用先进先出方式传输信息。无人机i 选择路由 q 的平均等待时延可以
i
写为:
(q ,G)
i i   
1
 (4-17)
=  i ,i − + 
k k+1
2 (  ) 
 
(i ,i ) q i ,i i ,i i ,i i ,i
+  + + + +
k k 1 i k k 1 k k 1 k k 1 k k 1
其中, + =  +  表示直传链路(i ,i + )q 总的到达率(包/秒),这些数据包
i ,i i i k k 1 i
k k 1 k k
来源于无人机 i 产生的数据包  以及和 i 连接的其他无人机产生的数据包
k i k
k
 = 
i j j  + = +  是服
,A 是G 中与无人机ik 相连的无人机集合。 i ,i Ri ,i / A
i
k k k 1 k k 1
k ik
 i i + 的可达速率, 是数据包大小。从式中可以看出,
务率,R 是直传链路( , )
i ,i k k 1
k k +1
当   +  + 时,等待时延将会无限大,因此,只有当链路的到达率
 +  + 时,等待时延将会无限大,因此,只有当链路的到达率
i ,i i ,i i ,i
k k 1 k k 1 k k+1
 时,链路(i ,i + ) 才是有效的。
服务率
i ,i k k 1
k k +1
4. 能量消耗 小于
能量消耗主要来源于路由 q 内无人机i 收集信息、其他转发无人机数据处理
i
以及接收转发信息产生的能量消耗。首先考虑无人机i 收集信息能量消耗,为了
68
第 4 章 面向远距离信息传输需求的多无人机路由选择
收集信息,单位时间内无人机i 的能量消耗为:
E = e (4-18)
s
i s i
其中,e 为收集单个比特信息消耗的能量。其次,考虑其他转发无人机数据处理
s
能量消耗,当无人机作为转发节点时,需要对接收信号进行解码并重新编码,因
此,单位时间内,为了处理无人机i 的信息,需要消耗的能量为:
E p = (K −1)e (4-19)
i p i
其中,e 为处理单个比特信息消耗的能量。最后,考虑其他转发无人机接收转发
p
信息能量消耗,主要包括发送和接收能耗,因此,单位时间内,为了将无人机i 的
信息传输到地面站,此部分的能量消耗为:
K−1
E ( p p )T
c r
=  + (4-20) i i i k
k k +1
k=1
其中,p 和
i
k pr 分别表示发送和接收功率,T = R  是直传链路 i i + 传
, / ( ) ( , )
i k i i i k k 1
k +1
k k +1
输无人机i 的信息所需的通信时间。
综上所述,通过路由 q 传输无人机i 的信息,整体网络所消耗的总能量为:
i
E (q ,G) = Es + Ep + Ec (4-21)
i i i i i
4.3.3 优化模型
根据上述约束条件(4-1)-(4-4)和性能指标(4-5),建立多无人机路由选择问题
的优化模型如下:
 
  1i
R (q ,G)
V
 
 (4-22)
max f (q ,G) =
i i
i i  
 , , , =1    
2i 3i
(q ,G) E (q ,G)
i g i j
i
   
i i i i
s.t. (4-1)-(4-4)
其中,R (q ,G)、 ( , )
i qi G 、Ei (qi ,G) 的定义分别如式(4-6)、(4-17)、(4-21)所示。 i i
上述优化问题的目标是为每架无人机找到合适的信息传输路由,实现无人机
到地面站信息传输的速率、等待时延、能量消耗的综合性能最大化。本节给出了
多无人机路由选择的问题描述,接下来为上述优化问题建立网络形成博弈模型。
4.4 网络形成博弈模型
网络形成博弈是研究学者们为解决互联网络形成问题专门提出的博弈理论,
由于网络内节点之间为非合作关系,因此网络形成博弈属于非合作博弈[163]。其
69
天津大学博士学位论文
主要研究多个参与者受到网络拓扑结构的影响,通过博弈选择通信链路形成互联
网络的过程。利用网络形成博弈解决无人机路由选择问题(4-22)时,首先需要
对待解决的无人机路由选择问题建立网络形成博弈模型。
由于网络形成博弈属于非合作博弈,因此博弈模型包含参与者、动作、收益
三方面,其通常表示为 {u } } ,其中, 表示参与者集合;S 表
i
示参与者i 可以选择的动作集;u 表示参与者i 选择动作后得到的收益,选择的动
i
作不同收益也不同。针对多无人机路由选择问题,各符号的具体含义如下:
(1)参与者集合
将网络中向地面站传输信息的V 架无人机作为博弈的参与者,因此,网络形
成博弈中的参与者集合可以表示为:
.,V} (4-23)
(2)动作集S
i
在上述无人机路由选择问题中,每架无人机选择一个下一跳节点,因此将当
前网络中可选择的下一跳节点(包括地面站和无人机)作为无人机的动作。当网络
拓扑为G 时,无人机i 的动作集可以表示为:
S ( ) {( , ) | , ) ( , ) } (4-24)
i G = i j j  qj G  uj qj G −
其中, V,g}表示V 架无人机和地面站 g 的集合, i ={ j  ,i)
A
q ,k =1,...,K −1}是将无人机i 包含在路由中的无人机集合,为了防止网络出现环
j
A 。G是当无人机i 选择 j 作为下一跳节点 路,无人机i 的动作集中不应该包含
i
时所形成的网络,  0是取值很小的常数,u (q ,G) 和 ( , )
u q G 分别表示网络 j j j j
拓扑为G和G 时无人机 j 的收益。考虑网络节点存在自私性,无人机的动作不
能造成下一跳节点收益明显下降,否则下一跳节点不会参与合作转发信息,因此
u q G  u q G − 。 需要满足 ( , ) ( , )
j j j j
(3)收益u
i
无人机选择下一跳节点后,根据上述性能指标(4-5),得到无人机i 的收益可
以表示为:
u (q ,G) = f (q ,G) (4-25)
i i i i
在多无人机路由选择问题的网络形成博弈中,无人机i 每次决策根据收益选
择保持之前的动作或通过新的动作 s S (G) 替换原有动作。每架无人机以找到
i i
使自身收益最大的路由为目标:
maxu (q ,G),i (4-26)
i i
s
i
如果无人机i 没有动作可以选择,那么无人机i 与地面站 g 之间不存在直传和
70
第 4 章 面向远距离信息传输需求的多无人机路由选择
多跳通信链路,也就是说无人机i 与网络失去连接,收益变为零。因此,始终存
在无人机i 到地面站的通信链路。
这一小节建立了多无人机路由选择问题的网络形成博弈模型。下一小节将介
绍上述网络形成博弈模型的求解方法,计算得到每架无人机的路由选择结果。
4.5 基于最佳响应的求解策略
这一部分将给出上述网络形成博弈的求解策略,首先介绍每架无人机如何选
择初始路由,然后给出网络形成博弈的解的数学定义,即纳什均衡,最后介绍如
何通过求解算法获得纳什均衡,得到每架无人机的路由选择结果。
1. 初始路由选择
在多无人机路由选择问题中,令无人机选择与离地面站最近的邻机作为其下
一跳节点,将此时无人机与地面站之间形成的网络作为初始网络,以减少算法的
求解时间。
2. 网络形成博弈中纳什均衡的数学定义
上述网络形成博弈的解为纳什均衡,在纳什均衡下,每架无人机均找到此时
使自己收益(4-25)最大的路由。当无人机i 找到使收益u (q ,G) 最大的动作 s 且选
i i i
择动作 s 的概率为 1 时,
i s 称为无人机i 的纯策略,选择的最优动作为最佳响应
i
动作。但是纯策略可能有多个,也可能不存在,当出现这种情况时无人机会陷入
循环迭代,为了解决此问题,需要寻找混合策略。下面分别给出最佳响应(best
response,BR)、纯策略/混合策略、纯策略纳什均衡以及混合策略纳什均衡的具
体定义。令 s s − s + s
s ={s ,...,s }表示所有无人机的动作,
s ={ ,..., , ,..., }表示除 1 V -i 1 i 1 i 1 V
了无人机i 、其他无人机的动作。
定义 4.2:在其他无人机不改变动作的前提下,如果无人机i 的动作 s* 可以使其获
i
得最大收益,即
u (q*,G ) u (q ,G ),s 
s S (4-27) i i s* i i s s i i
, ,
i -i
i -i
那么动作 s* 是无人机i 的最佳响应动作,可以表示为 s* BR(s )。
i i -i
定义 4.3:如果博弈中每个参与者选择一种特定行动,即选择特定动作的概率为
1,选择其他动作的概率为 0,则此特定动作为纯策略(pure strategy),否则为混合
策略(mixed strategy)。
定义 4.4:如果所有无人机的动作都是最佳响应动作,即
s BR(s ),i  (4-28)
i -i
那么s ={s ,...,s }是博弈的纯策略纳什均衡。
1 V
71
天津大学博士学位论文
纯策略纳什均衡对应的网络称为纯策略纳什网络。当博弈中每个或部分参与
者不是选择一种特定行动时,每架无人机为自己的可选动作分配概率,令
P ={P ,...,P }表示所有无人机的动作概率分布,
1 V P {P ,...,P ,P ,...,P }表示
− = − +
i 1 i 1 i 1 V
除了无人机i ,其他无人机的动作概率分布。
定义 4.5:如果所有无人机的动作概率分布满足
u  (4-29)
= =  
其中,u E(u ) [ p (s )u (q ,G )]是无人机i 采用P 时的期望收
i j j i i s ,s i
 jV
sS
i −i
益,S=(S ,S ),p (s )表示无人机 j 的动作 s 分配到的概率。那么 P ={P*,...,P*}=
i −i
j j j 1 V
( , )
P* P* 是博弈的混合策略纳什均衡。此时对应的网络称为混合策略纳什网络。
i −i
3. 求解算法
为了获得纳什均衡,设计求解算法 4-1:
算法 4-1 求解算法
1:初始化所有无人机选择与离地面站最近的邻机连接;
//寻找纯策略
2:若当前网络没有收敛到纯策略纳什网络,所有无人机依次决策,循环执行以下步
骤,假设当前决策的是无人机i
3:记录各无人机位置和网络拓扑;
4: 若当前网络在记录中没有出现,即没有陷入循环迭代
5: 无人机i 根据 * ( )
si  BR s−i 选择动作 s* ;
i
6: 若无人机i 的动作不是之前动作
7: 无人机i 根据新动作替换当前连接;
8: 结束
9: 否则(产生循环迭代)
10: 触发寻找混合策略,即跳转到步骤 13;
11: 结束
12:结束
//寻找混合策略
13:若当前网络没有收敛到混合策略纳什网络,无人机依次决策,循环执行以下步骤,
假设当前决策的是无人机i
14: 无人机i 根据 s* = arg max S f 选择动作 si* ;
i s
i i
15: 若无人机i 的动作不是之前动作
16: 无人机i 根据新动作替换当前连接;
72
第 4 章 面向远距离信息传输需求的多无人机路由选择
17: 结束
18: 所有无人机更新无人机i 的动作概率分布 P ;
i
19:结束
在上述算法中,首先,所有无人机选择与离地面站最近的邻机连接,完成路
由选择初始化;然后每架无人机选择纯策略,即寻找纯策略纳什均衡,为了及时
发现循环迭代的产生,每架无人机在决策时记录各无人机位置和网络拓扑,若在
之后迭代中出现记录中的网络,说明产生循环迭代,即陷入局部极小。当循环迭
代产生时触发寻找混合策略纳什均衡,也就是说寻找无人机的混合策略。下面给
出具体步骤:
(1)初始化:所有无人机选择与离地面站最近的邻机连接;
(2)寻找纯策略
寻找每架无人机的纯策略的详细过程如下:
1)初始化迭代次数l=0 ;
2)判断当前网络是否收敛到纯策略纳什网络,若没有,执行步骤 3),若收
敛,停止迭代;
3)无人机按次序依次决策,当无人机i 进行决策时,记录各无人机位置和网
络拓扑,判断当前网络是否在记录中出现,即是否陷入循环迭代,若没有,执行
步骤 4),若陷入循环迭代,触发寻找混合策略纳什均衡,执行(3);
4)无人机i 根据式(4-27)选择自己的最佳动作 s* ,若该动作不是无人机i 之前
i
的动作,则无人机i 根据新动作替换下一跳节点,若无人机是最后一架决策的无
人机,继续 5),否则返回 3);
5)迭代次数 l=l+1,返回 2)。
寻找纯策略可能导致两种结果,第一种是找到纯策略纳什均衡,所有无人机
的动作都是此时的最佳响应,这也意味着可以得到一个稳定网络,该网络中没有
无人机会有动机单方面偏离自己的动作,也就是说,在其他无人机动作不变时,
没有无人机可以通过改变当前路由提高自己的收益。第二种结果是某些无人机纯
策略不存在,陷入循环迭代,即陷入局部最小,为了解决该问题,触发寻找混合
策略。
(3)寻找混合策略
在寻找混合策略过程中,无人机对自己的动作分配概率,例如无人机i 为自
 
p s ,且 p (s ) =1 己的可选动作 s 分配概率 ( )
。下面给出详细过程:
i i i i i
s S
1)初始化迭代次数l=0;
i i
2)判断当前网络是否收敛到混合策略纳什网络,若没有,执行步骤 3),若
收敛,停止迭代;
73
天津大学博士学位论文
3)无人机按次序依次决策,当无人机i 进行决策时,无人机i 根据式(4-30)选
择自己的最佳动作 s* ,若该动作不是无人机i 之前的动作,则无人机i 根据新动作
i
替换当前下一跳节点:
s =  f
* arg max S (4-30) i s
i i
其中,
f ... ... [p (s ), )]
=    
1 1 ,s
i −i
s S s S s S s S
1 1 i−1 i−1 i+1 i+1 V V
Pi =[pi (si )]s S 表示无人机i 的期望收益;
i i
4)所有无人机更新无人机i 的动作概率分布[164]:
P P (v P ) (4-31)
l l l l
+ =  +  − 
1 1
i i l+ i i
1
P 代表了无人机i 截止到 l次迭代选择每个动作对应的比例, 式中, i =[pi (si )]s
l l
 S
i i
即无人机i 的动作概率分布, l [ l ( )] S 维矢量,无人机i 的动作 s* 对应
v 是
i vi si s
 = 
S i i i i
的位置为 1,即 vl(s*) =1,其余位置为 0,令 = l+1,
P P 。若无人机是最后一架
i i i i i
决策的无人机,继续 5),否则返回 3);
5)迭代次数 l=l+1,返回 2)。
当寻找混合策略最终收敛时,可以得到混合策略纳什均衡。实际应用中,无
人机首先寻找纯策略,若在寻找纯策略过程中产生循环迭代,触发寻找混合策略。
为了清晰地了解博弈过程,以寻找纯策略为例给出简单示例:假设有四架无
人机参与博弈,由无人机任务的重要程度,确定路由更新次序为{1,2,3,4},令 0
代表地面站,初始网络如图 4-3(a)所示。根据次序,1 号无人机首先进行更新,
其动作集为[2,3,4,0],通过计算每个动作对应的收益,选择使收益最大的动作,
假设为[2],则 1 号无人机和 2 号无人机建立连接,并将动作通知其他无人机,
如图 4-3(b)所示。接着 2 号无人机更新,其动作集为[3,4,0],通过计算,假设选
择动作[0],即其动作不变,那么网络拓扑变为图 4-3(c)。接着 3 号无人机进行更
新,其动作集为[1,2,4,0],通过计算,假设选择[4],则 3 号无人机和 4 号无人机
建立连接,如图 4-3(d)所示。最后 4 号无人机更新,其动作集为[1,2,0],假设选
择动作[2],则 4 号和 2 号无人机建立连接,如图 4-3(e)所示。
(a) (b) (c) (d) (e) (f)
图 4-3 一次迭代过程示例
完成一次迭代后,得到新的网络拓扑,如图 4-3(f)所示,之后进行下一轮迭
74
第 4 章 面向远距离信息传输需求的多无人机路由选择
代,当所有无人机的动作为最佳响应动作时,网络收敛到纯策略纳什网络,迭代
终止。当然,也有可能产生循环迭代,当产生循环迭代时,触发寻找混合策略,
无人机为每个可选动作分配概率。
引理 4.1:若博弈参与者个数是有限的,且每个参与者有动作有限,那么该博弈
至少存在一个纳什均衡,包括混合策略纳什均衡。
根据引理 4.1,上述路由选择问题对应的网络形成博弈肯定存在纳什均衡。
其中,寻找纯策略收敛到纯策略纳什网络或循环迭代。当得到纯策略纳什网络
时,所提方法收敛,不触发混合策略寻找过程;当产生循环迭代时,触发寻找混
合策略,纯策略寻找过程终止。由于混合策略纳什均衡的寻找过程需要无人机频
繁交互,复杂度远远高于寻找纯策略过程,为了提高效率,可以考虑由网络控制
中心辅助计算。由于目前还没有理论能够证明所提寻找混合策略方法的收敛性,
因此,下一节从仿真角度对寻找混合策略的收敛性进行验证。此外,为了提高收
敛速度,可以设置最大迭代次数,使算法收敛。
在寻找纯策略中,每次迭代无人机需要选择最佳响应动作,复杂度为
( )
O V − A ,其中,
i A 是连接无人机i 的无人机数量,星型拓扑属于最差情况,
i
其复杂度是O(V ) ,当无人机更新动作后,其他无人机需要重新计算收益,因此,
得到纯策略纳什网络的复杂度为O(V 2 ) 。当产生循环迭代后,触发寻找混合策略,
其复杂度取决于最大迭代次数。可见,随着网络规模的增加,复杂度不断增长,
为了有效解决此问题,根据实际应用,可以周期性运行上述方法,也可以考虑由
网络控制中心辅助计算,还可以将无人机根据区域划分,在每个区域中运行所提
方法,从而大幅降低复杂度。
4.6 仿真验证
在 Windows 10 操作系统中,基于 Matlab 2014a 仿真环境编写上述算法实现
仿真实验,计算机配置为 Intel(R) Core i5-2450M @2.5GHz 处理器,8G 内存。
4.6.1 仿真参数
仿真场景设置为 5km×5km×120m 的空域,假设无人机飞行在 100~120 米
高度收集信息并向地面站传输。初始时刻所有无人机选择与离地面站最近的邻
机连接,其余无人机和地面站均是无人机可以选择的下一跳节点。仿真参数如
表 4-1 所示。
75
天津大学博士学位论文
表 4-1 仿真参数
参数 含义 参数值
V 无人机数量 10
B 无人机带宽 5MHz
i
f 系统载波频率 2GHz
c
b , b 环境常量[46] 0.13,11.9
1 2
 非视距链路额外衰减因子 20dB
NLoS
p 无人机信号发送功率 20dBm
i
 2 噪声功率 -100 dBm
 单位时间数据包数量 50
i
 数据包大小 256bit
e ,
s e 感知、信息处理能量消耗 50nJ/bit,10nJ/bit
p
p 接收功率 15dBm
 r
i
 , , 权重因子 0.5,0.3,0.2
1i 2i 3i
4.6.2 仿真结果
1. 路由选择结果
图 4-4 无人机路由选择结果
为了验证所提方法的有效性,图 4-4 中实线给出了最终形成的路由选择结果。
仿真结果表明,远距离无人机通过多跳链路连接地面站,此外,从性能指标函数
的表达式可知,跳数会影响无人机性能,进而对无人机的路由选择也产生了影响。
例如,无人机 7 虽然距离无人机 3 比地面站近,但是经过无人机 3 需要两跳,而
76
第 4 章 面向远距离信息传输需求的多无人机路由选择
直接与地面站连接只需要一跳。此外,当无人机 10 进行决策时,无人机 10 不可
以选择无人机 4 和 5 作为其下一跳节点,否则会形成环形网络。从图中还可以看
出,当无人机 6 进行决策时,无人机 6 可以选择无人机 7、8、2、3、10 或 9 等
作为其下一跳节点。然而虽然无人机 8 选择距离较近的 2 作为其下一跳,但是无
人机 6 没有选择 8,这是因为 6 选择 8 会经历更多跳;无人机 6 没有选择 2,这
是因为 2 需要为 8 转发信息,6 再选择 2 会增加 2 到地面站的链路负载,同理无
人机 6 没有选择 10;无人机 6 没有选择 3 或者 9,这是因为 3 或者 9 不仅需要为
其他无人机转发信息,还离 6 较远。
2. 收敛性
首先验证寻找纯策略过程的收敛性。通过 100 次独立实验,得到不同无人机
规模下所提方法的收敛性,如图 4-5 所示。图中三条曲线分别表示最大、平均、
最小迭代次数。从图中可以看出,当V=5时,所需最大、平均、最小迭代次数分
别为 3、2.4、2,而当V=25时,迭代次数增加为 5、3.6、3,这是因为随着无人
机数量的增加,每架无人机可选动作增加,需要更多迭代才能达到稳定网络。此
外,从收敛性来看,随着无人机规模的扩大,迭代次数缓慢增长。
图 4-5 寻找纯策略的收敛性
其次验证寻找混合策略过程的收敛性。当无人机按图 4-6(a)所示分布,且
{1,2,3}选择与地面站直接连接,{4,5,6}只能在{1,2,3}中选择下一跳节点,{7,8,9,10}
只能在{4,5,6}中选择下一跳节点时,无人机 6、7 与 10 在寻找纯策略过程中陷入
循环迭代。图 4-6(b)给出循环迭代产生后寻找混合策略过程的收敛性。从图中可
以看出,无人机 6 没有选择距离更近的无人机 3 作为其下一跳节点,这是因为相
比于无人机与无人机之间的通信链路,无人机与地面站的通信链路比对距离更加
77
天津大学博士学位论文
敏感。此外,受到地面反射的影响,无人机 3 距离地面站较远,信号损耗较大。
仿真结果还表明,经过若干轮迭代后,无人机 6、7 与 10 的寻找混合策略过程逐
渐收敛。
(a) 无人机分布情况 (b) 寻找混合策略的收敛性
图 4-6 寻找混合策略的收敛性
3. 性能评估
为了验证所提方法的性能,首先分析无人机自私程度对网络性能的影响。当
无人机的收益没有明显降低时,才会参与合作。图 4-7 分析了不同自私程度下网
络性能。仿真结果表明,随着网络规模的扩大和自私程度的增加,平均收益降低,
无人机所需跳数减小。
(a) 平均收益 (b) 跳数
图 4-7 无人机自私性对网络性能的影响
由于路由选择结果与无人机的决策顺序有关,因此,不同决策顺序可能具
有不同解,即博弈可能存在多个纳什均衡,为了不失一般性,进一步分析不同
纳什均衡的性能。假设网络中存在V 架无人机,那么可以形成(V +1)(V −1) 种网络
78
第 4 章 面向远距离信息传输需求的多无人机路由选择
结构,可见对于大规模网络,通过遍历所有网络结构,找到最有效的均衡是一个
相当复杂的过程。为了便于分析,考虑V=3和V=4两种场景,分别有 16 种和 125
种网络结构,图 4-8(a)所示为 10000 种随机网络产生的纯策略纳什均衡数量,从
图中可以看出,V=4时共有 28 个网络存在两个纯策略纳什均衡,远远低于网络
结构数量。图 4-8(b)给出V=4时,无人机在不同均衡下的平均收益,可以看出,
不同均衡下网络性能近似相等。
(a) 纳什均衡个数 (b) 无人机在不同均衡下的平均收益
图 4-8 多个纳什均衡存在结果分析
(a) 平均收益 (b) 跳数
图 4-9 激励设置对网络性能的影响
通过设置激励机制可以提高均衡的有效性,下面进行仿真验证。考虑由地面
站根据无人机转发的数据包数量,给予相应的额外奖励,图 4-9 分析了有激励与
无激励的网络性能,仿真结果表明,随着网络规模的增加,两种情况下无人机的
平均收益近似相等,但是通过设置激励,无人机所需跳数降低。
为了进一步验证所提方法的性能,将所提方法与最近邻方法和直接传输方
案进行对比。从图 4-10 中可以看出,尽管网络中无人机规模不同,所提方法性
79
天津大学博士学位论文
能始终优于其他两种方法。图 4-11 进一步考虑权重因子的影响,假设时延与能
量消耗具有相同权重,当可达速率的权重较小时,无人机对时延和能量消耗更为
敏感,采用较少跳数与地面站连接,随着可达速率权重的增大,无人机对时延和
能量消耗较为容忍,网络平均收益增大。
图 4-10 不同无人机数量 图 4-11 不同权重因子
4.7 小结
本章针对远距离无人机与地面站直传链路的通信距离和速率受限问题,对多
无人机路由选择问题进行了研究,获得的主要成果如下:
(1)以无人机收集及传输信息作为任务场景,根据无人机与地面站以及无
人机之间链路关系建立约束条件,考虑无人机到地面站的可达速率、等待时延、
能量消耗建立综合性能指标,作为路由选择的依据;
(2)考虑无人机所选路由不仅影响自己的收益,也会影响其他无人机收
益,设计基于网络形成博弈的路由选择方法,在该方法中,首先建立路由选择的
网络形成博弈模型,其中考虑网络节点具有自私性建立无人机的可选动作集;然
后,利用最佳响应易于实现的优势,设计寻找纯策略/混合策略的求解算法,实
现无人机的路由选择,完成远距离信息传输;
(3)通过仿真验证了所提方法的有效性和收敛性,分析了无人机自私程度
对网络性能的影响,并考虑博弈存在多个纳什均衡,为无人机设计合作激励机制,
最后,与最近邻方法和直接传输方案进行了对比,结果显示所设计的方法能够获
得较高的网络收益。
本章研究了面向远距离传输需求的多无人机路由选择,可以用于解决远距离
无人机与地面站通信问题。然而本章假设至少有一架无人机与地面站直接连接,
当无人机不存在到地面站的路由时,如何实现与地面站通信是下一步亟需解决的
关键问题。
学术论文网提供数万篇的免费毕业论文、硕士论文、博士论文、sci论文发表的范文供您参考,并提供经济、管理、医学、法律、文学、教育、理工论文、mba作业、英语作业的论文辅导写作、发表等服务,团队实力雄厚,多达人,帮您解决一切论文烦恼。