军事云环境下基于动态博弈的资源调度方法⋆

牛 侃，张恒巍，王晋东，欧阳旦，王 娜

（1.解放军信息工程大学，郑州 450001；2.解放军61226部队，北京 100079；3.空军电子技术研究所，北京 100089）

军事云环境下基于动态博弈的资源调度方法⋆

牛 侃1，2，张恒巍1，王晋东1，欧阳旦3，王 娜1

（1.解放军信息工程大学，郑州 450001；2.解放军61226部队，北京 100079；3.空军电子技术研究所，北京 100089）

针对军事云环境下联合指挥资源调度优化问题，综合考虑了多部队任务需求，多目标优化，多部队资源竞争等约束条件，运用动态博弈理论及方法，建立并提出了一种基于完全信息扩展博弈的资源调度模型及方法，提高了资源调度效率，兼顾了多部队利益，增加了联合作战效益。最后通过实验验证了其有效性及准确性。

军事云，联合指挥，资源调度，动态博弈，纳什均衡

0 引言

云计算是将任务分布在大量计算机构成的资源池上，通过统一管理和调度，实现用户按需获取计算能力、存储空间和信息服务的一种新型计算模式［1-3］。随着云计算的迅速发展，其在军事信息领域的应用前景日益受到各国军方的重视，而军事云作为下一代军事信息系统的发展趋势，主要是指基于云计算理论，采用云计算服务模式，构建的军事云模式。具体指基于军事信息网络组件，将军事卫星、军事通信、侦察预警、指挥控制、火力打击、综合保障等军事基础设施和系统内聚融合，为作战指挥提供按需自主、动态扩展、柔性伸缩的网络服务的新一代军事网络架构［4］。但军事云又不同于Google、IBM等云计算平台，其是与互联网物理隔绝的私有云环境，通过整合现有军事信息资源，构造独立的云计算中心，为部队的战时联合指挥、日常训练及抗险救灾等活动提供信息服务支撑［5］。

目前，云计算资源调度方法多种多样，ZHANG Haorong等人［6］将蚁群模拟退火算法用于云环境任务调度，YUAN Hao等人［7］提出社会力群智能优化算法的云计算调度研究，他们都是从调度中心整体利益出发，把智能算法运用于云计算资源调度，提高了资源调度效率，保证了系统的性能。但不足之处是以调度中心整体利益为主，不能满足所有用户的资源需求，不能保证资源分配公平性。LIN Changlei［8］研究基于博弈论的云计算资源分配机制，满足了个体理性与激励兼容特性，不足之处是过分追求云计算资源价格，未保证用户其他的需求，即未保证用户的服务质量QoS（Quality of Service）。在信息化条件下，联合作战指挥由于各部队对资源的类型及需求程度各有差异，不同类型资源的空间具有异构性且不需要考虑资源的价格，所以在军事云环境资源调度过程中，多个部队同时提交任务请求，形成了竞争（即资源使用冲突）。为了满足每个部队的需求，符合各部队提出的约束条件如任务完成时间、系统稳定性、数据保密性等等，同时达到资源的最合理有效的使用和配置，亟需设计出一种合理有效的资源调度模型及方法。

博弈论是经济学最基本的理论之一，用于解决不同个体之间的竞争与相互制衡问题。而军事云环境资源调度问题是研究如何解决多个部队之间的竞争，达到满足所有部队的需求。正好适用于博弈论理论和基本方法。针对军事云环境资源调度实际问题，本文基于动态博弈论，提出一种合理有效的资源调度模型及方法，用于解决军事云环境中多部队资源竞争问题，提高联合作战效益。

1 军事云环境下基于动态博弈的资源调度模型构建

军事云环境下资源调度是指在资源虚拟化基础上，联合指挥中心动态地分配各部队执行任务所需的计算资源，为执行任务提供可行性环境，是各类任务顺利实施的基础。即在军事云环境资源调度过程中，物理资源被军事云系统虚拟化成虚拟单元，作为执行任务的载体。部队执行任务往往对应一种最佳的虚拟单元类型，而任意充足的物理资源（如各类传感器、计算机、数据库等）都可以创建这些对应的虚拟单元，进而可以分配给各部队来完成其任务［9］。但不同的创建方案直接影响部队获得的服务质量QoS（Quality of Service），即影响部队执行任务的效率，因此，QoS是各部队争夺的主要目标。

博弈论是研究参与者的行为发生直接相互作用时候的决策以及这种决策的均衡问题的。动态博弈论是指参与人有先后行动顺序，并且后行动者可以观察到前者行动，并据此作出相应的选择。而扩展博弈是通过树的形式来描述一组博弈序列，完全信息博弈是指在博弈的过程中，每个博弈参与者都了解其他参与者选择不同策略的收益情况，也知道之前所有发生过的决策。因此，完全信息扩展博弈是一种动态博弈。从军事云环境资源调度的逻辑上看，它与商业云计算资源调度的区别主要有以下几个特点：①各部队根据上级命令提交任务请求，而任务的属性又是分等级的，可以认为是有先后顺序进行的请求博弈；②军事云环境资源池资源性能有差别，高性能资源被多个部队使用会降低该资源性能；③级别高的任务优先保障资源分配；④同一级别的任务，申请部队的策略相互制约，即前一个部队的策略影响后一个部队的策略选择；⑤联合指挥中心掌握各部队申请任务的属性、内容及收益函数。因此，各部队提交任务请求的过程可以看作是动态博弈论中完全信息扩展博弈的过程，所以本文是在联合指挥中心构建军事云环境下基于完全信息扩展博弈的资源调度模型。

1.1 模型假设

假设1.理性假设 假设各部队是完全理性的，不会因要获得最大收益而发送毫无意义、恶意占用资源的任务请求。

假设2.类型假设 假设不同部队的需求不同，提出的QoS不同。

假设3.收益假设 假设所有部队的目标都是在满足自己QoS的前提下，请求资源来完成任务。联合指挥中心的目标是尽可能满足所有部队提出的需求，反馈资源完成其任务。

1.2 模型定义

定义1 军事云环境动态博弈资源调度模型MCED-GRSM（Military Cloud Environment Dynamic Game Resource Scheduling Model） 是一个 五 元组MCED-GRSM=（N，T，S，I，U），其中：

（1）N=（N1，N2，…，Nn）是博弈的参与者集合。参与者是参与博弈的独立决策、独立承担结果的个人或组织，在不同的场合中，参与者的定义是不同的。在本文中，参与者是某一时间片段所有发送任务请求的部队。

（2）T=（T1，T2，…，Tn）是参与者的行动顺序。即在某一时间片段部队选择资源的先后顺序，在军事云环境中首先根据任务属性高低进行资源选择排序，即任务级别高的部队先选择可用资源来完成任务；然后任务级别相同的部队采取先申请先选择的排序原则。

（3）S=（S1，S2，…，Sn） 是参与者的策略空间。表示参与者Ni的策略空间，每个参与者都应有1种以上的策略，即h≥1。在军事云环境中，各部队的策略采取选择最优资源原则。

（4）I=（I1，I2， … ，In） 是 参 与 者 的 信 息 集 。表示参与者Ni的信息集，每个参与者都应有一种以上的策略，即k≥1。在本文中，部队选择资源时知道前一个部队的选择策略。

（5）U=（U1，U2，…，Un）是参与者的收益函数集合。表示部队n在部队1，2，…，n-1行动之后选择策略sn的收益。收益函数表示参与者从博弈中可以得到的收益水平，由所有参与者的策略共同决定，参与者不同的策略组合所得到的收益不同。在军事云环境中，参与者收益函数是部队QoS的满意度。

定义2 军事云环境资源调度博弈树是常常用于表示调度过程中实现每个收益的策略路径表现形式。它具有一般树的结构，用一个三元组表示（N，S，U）表示，如图1所示。其中N表示所有节点集合，代表资源调度中所有部队的集合；S是博弈树中有向边的集合，代表资源调度中部队的策略；U则是部队收益的集合，代表在不同策略下取得的收益。

图1 军事云环境资源调度博弈树

2 军事云环境下基于动态博弈的收益量化计算及均衡分析

2.1 收益量化计算

军事云环境资源调度中部队收益的量化计算是后续调度博弈分析的基础，且直接影响资源调度的结果。因此，对各部队的策略进行合理地收益量化是非常有必要的。在实际的资源调度过程中，联合指挥中心资源趋近无限多，资源性能有优良差别；申请不同任务的部队对资源性能权重不同。而联合指挥中心是尽可能满足所有部队的QoS，反馈资源执行其任务，保证作战效益，从而获得收益。相反如果不能尽可能满足所有部队的QoS，就会降低作战效益，得到损失。

本文认为各部队的收益是其QoS的满意度，即：

其中Q代表服务质量指标，例如响应时间、可靠性、保密性等。代表部队对各类指标的权重，代表了部队对i类型资源服务质量的满意度。

而联合指挥中心的收益是所有部队的总收益，即：

2.2 均衡分析

任何一个部队申请资源都希望获得联合指挥中心的优质资源，满足自己的QoS，从而完成任务。如果联合指挥中心不能满足其QoS，就会降低部队作战效益。所以面对所有申请资源部队的不同QoS，如何分配资源选取策略，尽可能满足所有部队的QoS是军事云环境资源调度的关键问题。

在资源调度过程中，各部队根据提交任务的属性高低按序选择优质资源，后一个部队只能根据前一个部队行为来选择资源，以尽可能满足自己的QoS，得到最大收益U。本文采用博弈论中的逆向归纳法（backward induction in games）求解博弈的纳什均衡解。

定义3 逆向归纳法。从博弈终点节的直接前行节开始，然后通过博弈树逆向归纳的方法，被称为博弈中的逆向归纳法。考虑图1中的扩展博弈，求解是从扩展博弈树的底端开始。考虑部队n的子博弈，如果部队n-1选择策略则对于部队n来说选择策略优于选择其他任何一个策略。同样的，当部队n-1选择策略时，部队n的最优策略是

将本文的方法和文献［6-8］进行对比，结果见表1所示。

表1 方法比较

由表1可以看出，相比其他文献，本文方法具有实现多边最优，解决多部队资源使用冲突，增强联合作战指挥效益等优点。

3 应用实例与分析

3.1 实验环境描述

军事云环境资源调度实例如图2所示，采用Gambit博弈软件进行均衡分析。该实例描述了一个虚拟化军事云环境下资源调度问题，联合指挥中心资源池趋近无限大，各部队的QoS指标有响应时间、稳定性、保密性。某一时间片段有4个团向联合指挥中心提交作战任务，而每个团的QoS不同，即对不同类型资源的权重不同。联合指挥中心在资源调度过程中首先根据作战任务属性的高低分配各团选择资源的先后顺序，然后再对任务级别相同的团采取先申请先选择原则分配先后顺序。而后一个团只能根据前一个团的行为来选择资源，以尽可能满足自己的QoS。

图2 军事云环境资源调度结构示意图

3.2 博弈收益计算及均衡求解

调度模型根据已有信息生成本次博弈数据表2。

表2 军事云环境资源调度数据表

确定完本次军事云环境资源调度博弈数据之后计算各团选择不同策略的收益量化，如表3和表4所示。

表3 军事云环境资源调度各团收益（高级别任务）

表4 军事云环境资源调度各团收益（低级别任务）

经过收益量化计算后，将上述数据输入Gambit博弈软件进行均衡分析。由此可得到博弈树如图3、图4所示。

图3 军事云环境资源调度博弈树（高级别任务）

图4 军事云环境资源调度博弈树（低级别任务）

实验结果表示可分别从高低级别任务的博弈中找到唯一一个纳什均衡解，构成本次军事云环境资源调度的纳什均衡解，结果为：，即4个团均会选择第2个策略。

3.3 实验分析

对上述纳什均衡可解释为：军事云环境资源调度过程中，首先保障高级别任务的资源分配，然后同一级别任务的各部队根据前一个部队的策略行动，尽可能选择优质资源来执行作战任务，使自己的收益最大。即在纳什均衡中，各部队均会选择最优资源来执行任务。

以上结果表明，本文所提出的军事云环境资源调度模型及方法可以更加合理、有效地反映策略收益对部队执行任务的影响，并且可以有效地进行最优的资源调度。

4 结论

军事云环境是以云计算技术为基础，加快了信息共享的步伐，促进战斗力生成模式向适应信息化战争的方向转变，为今后联合作战指挥带来显著的效益。本文建立了动态博弈的资源调度模型MCED-GRSM，并进行了详细的定义。该模型首先根据各部队任务的属性高低分配选择资源的优先权，然后对任务属性相同的团采取先申请先选择分配优先权，最后给出了博弈的均衡求解过程。从联合作战指挥角度出发，将军事云环境资源分配问题通过动态博弈中完全信息扩展博弈模型进行分析，使资源调度提高效率，增加联合作战效益。最后，通过一个调度实例对本文提出的模式和方法进行了验证，实验证明是有效和可行的。

［1］MELL P，GRANCE T.The NIST definition of cloud computing ［R］.National Institute of Standards and Technology，2011.

［2］MELL P，GRANCE T.The NIST definition of cloud computing ［R］.National Institute of Standards and Technology，2011.

［3］XIONG A P，HUANG K，YANG C.Resource scheduling strategy for cloud computing environment based on optimal benefits［J］.Microelectronics&Computer，2013，30（11）：104-107.

［4］LUO J Z，JIN J H，SONG A B，et al.Cloud computing：architecture and key technologies［J］.Journal on Communications，2011，32（7）：3-21.

［5］WEI B.Research on key technologies of services composition under the military cloud environment［D］.Zhengzhou：PLA Information Engineering University，2014.

［6］ZHANG H R.Task scheduling algorithm based on simulated annealing ant colony algorithm in cloud computing environmen ［J］.Journal of Guangdong University of Technology，2014，31（3）：77-82.

［7］YUAN H.Resource scheduling algorithm based on social force swarm optimization algorithm in cloud computing［J］.Computer Science，2015，42（4）：206-208.

［8］LIN C L.A research on cloud computing resource allocation mechanism design based on game theory［D］.Hangzhou：Hangzhou Dianzi University，Hangzhou，2013.

［9］熊家军，李强.云计算及其军事应用［M］.北京：科学出版社，2011：173-174.

［10］王俊丽，申良强，雷建栋，等.云计算技术应用于军事信息系统设想［J］.火力与指挥控制，2013，38（S1）：66-68.

Resource Scheduling Method Based on Dynamic Game under Military Cloud Environment

NIU Kan1，2，ZHANG Heng-wei1，WANG Jin-dong1，OU Yang-dan3，WANG Na1
（1.PLA Information Engineering University，Zhengzhou 450001，China；2.Unit 61226 of PLA，Beijing 100079，China；3.The Air Force Institute of Electronic Technology，Beijing 100089，China）

To joint command resource scheduling optimization problem under the military cloud environment，this paper considers the constrains such as the multiple forces mission requirements，multi-objective optimization and the multiple forces competition for resources.It uses the theory and method of dynamic game to build and put forward a kind of resource scheduling model and method based on complete information extension game.The method improves the efficiency of the resource scheduling and balances the interests of multiple forces and increases the benefit of joint operations.Finally the effectiveness and accuracy are verified by experiment.

military cloud，joint command，resource scheduling，dynamic game，nash equilibrium

TP393.01

A

10.3969/j.issn.1002-0640.2017.07.004

1002-0640（2017）07-0016-05

2016-04-05

2016-07-07

国家自然科学基金资助项目（61303074，61309013）

牛 侃（1988- ），男，河南郑州人，硕士研究生，助理工程师。研究方向：云计算资源管理、博弈论。