博弈论在无人机应急通信网络研究中的应用

2020-04-08周韬瑒

现代计算机 2020年7期

周韬瑒

（安徽工业大学管理科学与工程学院，马鞍山 243032）

0 引言

蜂窝移动网络已经经历了2G、3G、4G通信，现在正往5G大步迈进。由于极速增长的通信速度，伴随着各种各样互联网应用的产生，使得人们进入了互联网时代。实时通信对人们带来了极大便利，让整个社会对网络产生了极大的依赖。如果有一天通信中断，所有与网络有关的应用都将停止，这无疑会对我们的生产生活产生严重的影响。所以对于应急通信的研究成为移动通信研究中重要的一部分。无人机网络现场评估对于控制灾情、营救受灾群众以及灾后重建具有重大意义，无人机网络可以帮助救灾指挥官识别、处理和掌握大型自然灾害或其他紧急情况中的关键因素。此外，因其网络建构价格便宜、对应用场地要求低、易于快速部署以及扩展性强等优势，受到了越来越多研究人员的关注，因此，深入研究基于多无人机的无线应急通信网络具有重要的实际意义和应用前景[1,2]。博弈论是研究具有竞争或者合作性质现象的理论与方法，它既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论最大的特点是能够为相应的博弈过程找到一个纳什均衡，有时候这个找到的均衡点也正是最优策略解，针对突发事件现场无线路由器自组织网络的快速安置以及灵活组织，采用博弈论的理论与模型对以多无人机为中继节点中的竞争与合作进行建模，使得我们对问题的研究找到最优策略。

1 博弈论的基本概念

1.1 博弈论的基本元素

博弈论起源于经济学，它被用来模拟冲突或合作方的行为[3]。它提供了一种分析竞争参与者之间相互作用的方法，该方法已成功应用于进化生物学、政治、控制系统、通信和许多其他学科的问题。在博弈理论中，博弈的基本元素包括：参与人（Player）、策略（Strategy）、支付（或收益，Payoff）。博弈是由这些元素所组成的决策情况，当中每个元素都必须清楚明确，下面给出这些基本元素的定义。

（1）参与人。参与人也称局中人，是指博弈中选择行动最大化自己效用的决策主体。参与人是理性人，其目标是通过选择某种策略以使自己的收益最大化。在博弈论中，我们常用Γ={1，2，…，n}表示一个n人博弈的所有参与者的集合，用i∈Γ代表博弈中的任何一位参与者。

（2）策略集。策略集中包含了参与者能够选择的所有策略，策略和行动是十分相似的两个概念，策略可分为纯策略和混合策略。策略是参与人在给定信息集的情况下选择行动的一种规则，它规定参与人在什么情境下选择什么行动，是参与者的“行动方案”。它是一项规则而非行动本身，每个参与人均有可供其选择的多种策略。在一个n人博弈中，可以用si∈Si表示第i位参与者的一个特定策略，而Si则表示第i位参与者所有可选择的策略的集合或策略空间。n位参与者各选择一个策略形成n维向量s={s1,s2,…,sn}称为策略组合。

（3）收益。参与者选择某个策略时所能获得的效用，每个参与者从各种策略组合中获得的收益，由于它是策略组合s的函数，所以也称为支付函数。一个n人博弈中，用 ui（s1,s2,….,si,….,sn）表示第 i位参与者的支付。博弈的基本特征是一位参与者的支付不仅取决于自己的策略选择，而且取决于其他参与人的策略选择。

1.2 博弈过程及结果描述方法

在博弈中，一个均衡就是一个由所以参与者的最优策略所组成的组合，即一个特殊的策略组合。给定其他参与人选择的策略，每个理性参与人将选择最大化自己的回报的策略。这就导致了一种平衡状态，没有任何参与者偏离其选择策略的动机；这样的举动会减少该参与人的收益。这组选择称为纳什均衡（NE）。Nash平衡是最流行的游戏解决方案概念。在理想的世界中，将有一套策略，每个玩家选择一个动作，所有玩家的最佳反应都将重合。此状态称为“纯策略纳什均衡”（PSNE）。在真实情境中，并不总是有PSNE，但是在可能的策略范围内存在概率分布。这种类型的NE被称为“混合策略纳什均衡”（MSNE）。直觉上来说，PSNE是MSNE的特例，为此，每个玩家的选择之一的概率为1。在一个n人博弈中，如果为每个参与者给一个编号，那么便可以用si*表示第i位参与者的最优策略。而s*=（s1*,s2*,…,sn*）则是由所有参与者的最优策略所组成的策略组合，即是一个均衡。

在一个n人博弈中，参与人用集合N={1,2，…，n}来表示，而参与人在当前情境下能够选择的行动策略用集合S来表示，参与人i所选择的策略用si来表示si∈S，那么 s*={s1*,s2*,…,sn*}为纳什均衡，当且仅当对任意的 i∈N，存在：

其中，s-i*表示除了参与人i以外其他参与人所选择的策略，ui为参与人的最后收益，收益的计算是这些博弈中的关键阶段。在有的情况下，博弈不存在纳什均衡，同时，也在有的情境下，博弈可能存在不止一个纳什均衡。

2 基于博弈论的无人机应急通信网络

2.1 应急通信系统的发展状况

目前国内比较成熟的应急通信系统主要集中于移动指挥车，如基于车载型移动应急指挥系统[4]。通过将移动指挥车以及移动接入点等部署到应急区域，从而搭建临时无线通信网络。同时，在国内面向公共突发事件情景下的应急机制的研究主要停留在传统方法，如应急物资调度、应急设施选择和路径优化等[5]。除此之外，卫星网络也是应急通信的重要手段，但主要由于其用户扩展性差，这种通信主要用于指挥系统。众多研究可以发现，当前研究成果不能适用于无基础通信设备情景下用户应急通信的要求。由于无人机体积小、操作简单、成本低等特点，国内外众多研究人员也提出基于多无人机的自组织网络[6,7]。不同于传统无线网络或自组织网络，基于多无人机的无线应急网络，一方面需要根据用户信息（终端用户数量、通信量、位置信息等）的变化改变其网络拓扑；另一方面，具有通信中转功能的无人机，根据其他无人机的飞行路径和通信要求，也需要改变其位置以保持无人机与无人机之间的连通性；于此同时，某些无人机还起到网关的作用，与原地基站建立通信链路，实现临时网络与外界网络的联系。

2.2 博弈论在无线通信领域的研究进展

博弈论是研究参与人如何进行策略选择，以及这种决策如何达到均衡。博弈论最大的特点是可以为相应的博弈过程找到纳什均衡点，有时候这个均衡点就是最优解，这样，博弈论就能够指导和分析无线通信网络中的众多算法设计。博弈论在无线通信网络的应用已有大量的研究，其中主要的研究包括：功率控制、流量控制、拥塞控制、路由协议、网络安全、协作中继通信以及资源预留的竞价等[8]。本文探讨了基于无人机的无线路由器自组织应急通信网络的关键技术，针对突发事件现场无线路由器自组织网络的快速安置以及灵活组织，搭建出一种面向紧急突发状况的以无人机为中继节点的无线应急通信网络体系结构，来满足现场的应急指挥调度需求并且努力恢复用户通信。将博弈论思想引进，探讨无人机在当前体系下的移动机制问题。

2.3 无人机网络最大生命期通信模型

如图1所示的双层无线网络：路由层网状（mesh）网络和无人机网络。前者由K个路由器和一些终端用户组成，这是一种传统的无线路由器网状网络。后者由U个无人机和一个远程基站（例如：移动通信车辆）组成。无人机可以从路由器或其他无人机转发数据，以实现灾区内与外部终端用户之间的通信。双层网络可以轻松快速地部署到灾区，灾难避难所、现场救援中心等，为终端提供紧急通信服务。研究的范围是在路由器能量有限的条件下，无人机以以最快的方式收集数据，这是判定网络性能的关键点。对于无人机而言，我们可以把无人机视为博弈中的参与人，无人机在飞行中共有8种可执行动作：东、西、南、北、东南、东北、西南、西北。无人机在某一位置的可飞行方向其实是围绕自身360度方向，但我们只考虑8个方向的位置。那么这8个方向：东、西、南、北、东南、东北、西南、西北，便是无人机作为参与人的策略集。在这种情况下就变成了无人机与无人机之间的博弈，他们的收益就是无人机收集到的路由器的数据，同时，路由器都有能量的限制，无人机要在限制能量的条件下选择最有利于自己的飞行路径，即收益最大的策略，从而达到总体最优，即找到纳什均衡点，无人机作为参与人可采取合作博弈的方式，以达到总体最优。