軍事云環(huán)境下基于動態(tài)博弈的資源調(diào)度方法?

牛 侃，張恒巍，王晉東，歐陽旦，王 娜

（1.解放軍信息工程大學，鄭州 450001；2.解放軍61226部隊，北京 100079；3.空軍電子技術研究所，北京 100089）

軍事云環(huán)境下基于動態(tài)博弈的資源調(diào)度方法?

牛 侃1，2，張恒巍1，王晉東1，歐陽旦3，王 娜1

（1.解放軍信息工程大學，鄭州 450001；2.解放軍61226部隊，北京 100079；3.空軍電子技術研究所，北京 100089）

針對軍事云環(huán)境下聯(lián)合指揮資源調(diào)度優(yōu)化問題，綜合考慮了多部隊任務需求，多目標優(yōu)化，多部隊資源競爭等約束條件，運用動態(tài)博弈理論及方法，建立并提出了一種基于完全信息擴展博弈的資源調(diào)度模型及方法，提高了資源調(diào)度效率，兼顧了多部隊利益，增加了聯(lián)合作戰(zhàn)效益。最后通過實驗驗證了其有效性及準確性。

軍事云，聯(lián)合指揮，資源調(diào)度，動態(tài)博弈，納什均衡

0 引言

云計算是將任務分布在大量計算機構(gòu)成的資源池上，通過統(tǒng)一管理和調(diào)度，實現(xiàn)用戶按需獲取計算能力、存儲空間和信息服務的一種新型計算模式［1-3］。隨著云計算的迅速發(fā)展，其在軍事信息領域的應用前景日益受到各國軍方的重視，而軍事云作為下一代軍事信息系統(tǒng)的發(fā)展趨勢，主要是指基于云計算理論，采用云計算服務模式，構(gòu)建的軍事云模式。具體指基于軍事信息網(wǎng)絡組件，將軍事衛(wèi)星、軍事通信、偵察預警、指揮控制、火力打擊、綜合保障等軍事基礎設施和系統(tǒng)內(nèi)聚融合，為作戰(zhàn)指揮提供按需自主、動態(tài)擴展、柔性伸縮的網(wǎng)絡服務的新一代軍事網(wǎng)絡架構(gòu)［4］。但軍事云又不同于Google、IBM等云計算平臺，其是與互聯(lián)網(wǎng)物理隔絕的私有云環(huán)境，通過整合現(xiàn)有軍事信息資源，構(gòu)造獨立的云計算中心，為部隊的戰(zhàn)時聯(lián)合指揮、日常訓練及抗險救災等活動提供信息服務支撐［5］。

目前，云計算資源調(diào)度方法多種多樣，ZHANG Haorong等人［6］將蟻群模擬退火算法用于云環(huán)境任務調(diào)度，YUAN Hao等人［7］提出社會力群智能優(yōu)化算法的云計算調(diào)度研究，他們都是從調(diào)度中心整體利益出發(fā)，把智能算法運用于云計算資源調(diào)度，提高了資源調(diào)度效率，保證了系統(tǒng)的性能。但不足之處是以調(diào)度中心整體利益為主，不能滿足所有用戶的資源需求，不能保證資源分配公平性。LIN Changlei［8］研究基于博弈論的云計算資源分配機制，滿足了個體理性與激勵兼容特性，不足之處是過分追求云計算資源價格，未保證用戶其他的需求，即未保證用戶的服務質(zhì)量QoS（Quality of Service）。在信息化條件下，聯(lián)合作戰(zhàn)指揮由于各部隊對資源的類型及需求程度各有差異，不同類型資源的空間具有異構(gòu)性且不需要考慮資源的價格，所以在軍事云環(huán)境資源調(diào)度過程中，多個部隊同時提交任務請求，形成了競爭（即資源使用沖突）。為了滿足每個部隊的需求，符合各部隊提出的約束條件如任務完成時間、系統(tǒng)穩(wěn)定性、數(shù)據(jù)保密性等等，同時達到資源的最合理有效的使用和配置，亟需設計出一種合理有效的資源調(diào)度模型及方法。

博弈論是經(jīng)濟學最基本的理論之一，用于解決不同個體之間的競爭與相互制衡問題。而軍事云環(huán)境資源調(diào)度問題是研究如何解決多個部隊之間的競爭，達到滿足所有部隊的需求。正好適用于博弈論理論和基本方法。針對軍事云環(huán)境資源調(diào)度實際問題，本文基于動態(tài)博弈論，提出一種合理有效的資源調(diào)度模型及方法，用于解決軍事云環(huán)境中多部隊資源競爭問題，提高聯(lián)合作戰(zhàn)效益。

1 軍事云環(huán)境下基于動態(tài)博弈的資源調(diào)度模型構(gòu)建

軍事云環(huán)境下資源調(diào)度是指在資源虛擬化基礎上，聯(lián)合指揮中心動態(tài)地分配各部隊執(zhí)行任務所需的計算資源，為執(zhí)行任務提供可行性環(huán)境，是各類任務順利實施的基礎。即在軍事云環(huán)境資源調(diào)度過程中，物理資源被軍事云系統(tǒng)虛擬化成虛擬單元，作為執(zhí)行任務的載體。部隊執(zhí)行任務往往對應一種最佳的虛擬單元類型，而任意充足的物理資源（如各類傳感器、計算機、數(shù)據(jù)庫等）都可以創(chuàng)建這些對應的虛擬單元，進而可以分配給各部隊來完成其任務［9］。但不同的創(chuàng)建方案直接影響部隊獲得的服務質(zhì)量QoS（Quality of Service），即影響部隊執(zhí)行任務的效率，因此，QoS是各部隊爭奪的主要目標。

博弈論是研究參與者的行為發(fā)生直接相互作用時候的決策以及這種決策的均衡問題的。動態(tài)博弈論是指參與人有先后行動順序，并且后行動者可以觀察到前者行動，并據(jù)此作出相應的選擇。而擴展博弈是通過樹的形式來描述一組博弈序列，完全信息博弈是指在博弈的過程中，每個博弈參與者都了解其他參與者選擇不同策略的收益情況，也知道之前所有發(fā)生過的決策。因此，完全信息擴展博弈是一種動態(tài)博弈。從軍事云環(huán)境資源調(diào)度的邏輯上看，它與商業(yè)云計算資源調(diào)度的區(qū)別主要有以下幾個特點：①各部隊根據(jù)上級命令提交任務請求，而任務的屬性又是分等級的，可以認為是有先后順序進行的請求博弈；②軍事云環(huán)境資源池資源性能有差別，高性能資源被多個部隊使用會降低該資源性能；③級別高的任務優(yōu)先保障資源分配；④同一級別的任務，申請部隊的策略相互制約，即前一個部隊的策略影響后一個部隊的策略選擇；⑤聯(lián)合指揮中心掌握各部隊申請任務的屬性、內(nèi)容及收益函數(shù)。因此，各部隊提交任務請求的過程可以看作是動態(tài)博弈論中完全信息擴展博弈的過程，所以本文是在聯(lián)合指揮中心構(gòu)建軍事云環(huán)境下基于完全信息擴展博弈的資源調(diào)度模型。

1.1 模型假設

假設1.理性假設 假設各部隊是完全理性的，不會因要獲得最大收益而發(fā)送毫無意義、惡意占用資源的任務請求。

假設2.類型假設 假設不同部隊的需求不同，提出的QoS不同。

假設3.收益假設 假設所有部隊的目標都是在滿足自己QoS的前提下，請求資源來完成任務。聯(lián)合指揮中心的目標是盡可能滿足所有部隊提出的需求，反饋資源完成其任務。

1.2 模型定義

定義1 軍事云環(huán)境動態(tài)博弈資源調(diào)度模型MCED-GRSM（Military Cloud Environment Dynamic Game Resource Scheduling Model） 是一個 五 元組MCED-GRSM=（N，T，S，I，U），其中：

（1）N=（N1，N2，…，Nn）是博弈的參與者集合。參與者是參與博弈的獨立決策、獨立承擔結(jié)果的個人或組織，在不同的場合中，參與者的定義是不同的。在本文中，參與者是某一時間片段所有發(fā)送任務請求的部隊。

（2）T=（T1，T2，…，Tn）是參與者的行動順序。即在某一時間片段部隊選擇資源的先后順序，在軍事云環(huán)境中首先根據(jù)任務屬性高低進行資源選擇排序，即任務級別高的部隊先選擇可用資源來完成任務；然后任務級別相同的部隊采取先申請先選擇的排序原則。

（3）S=（S1，S2，…，Sn） 是參與者的策略空間。表示參與者Ni的策略空間，每個參與者都應有1種以上的策略，即h≥1。在軍事云環(huán)境中，各部隊的策略采取選擇最優(yōu)資源原則。

（4）I=（I1，I2， … ，In） 是 參 與 者 的 信 息 集 。表示參與者Ni的信息集，每個參與者都應有一種以上的策略，即k≥1。在本文中，部隊選擇資源時知道前一個部隊的選擇策略。

（5）U=（U1，U2，…，Un）是參與者的收益函數(shù)集合。表示部隊n在部隊1，2，…，n-1行動之后選擇策略sn的收益。收益函數(shù)表示參與者從博弈中可以得到的收益水平，由所有參與者的策略共同決定，參與者不同的策略組合所得到的收益不同。在軍事云環(huán)境中，參與者收益函數(shù)是部隊QoS的滿意度。

定義2 軍事云環(huán)境資源調(diào)度博弈樹是常常用于表示調(diào)度過程中實現(xiàn)每個收益的策略路徑表現(xiàn)形式。它具有一般樹的結(jié)構(gòu)，用一個三元組表示（N，S，U）表示，如圖1所示。其中N表示所有節(jié)點集合，代表資源調(diào)度中所有部隊的集合；S是博弈樹中有向邊的集合，代表資源調(diào)度中部隊的策略；U則是部隊收益的集合，代表在不同策略下取得的收益。

圖1 軍事云環(huán)境資源調(diào)度博弈樹

2 軍事云環(huán)境下基于動態(tài)博弈的收益量化計算及均衡分析

2.1 收益量化計算

軍事云環(huán)境資源調(diào)度中部隊收益的量化計算是后續(xù)調(diào)度博弈分析的基礎，且直接影響資源調(diào)度的結(jié)果。因此，對各部隊的策略進行合理地收益量化是非常有必要的。在實際的資源調(diào)度過程中，聯(lián)合指揮中心資源趨近無限多，資源性能有優(yōu)良差別；申請不同任務的部隊對資源性能權重不同。而聯(lián)合指揮中心是盡可能滿足所有部隊的QoS，反饋資源執(zhí)行其任務，保證作戰(zhàn)效益，從而獲得收益。相反如果不能盡可能滿足所有部隊的QoS，就會降低作戰(zhàn)效益，得到損失。

本文認為各部隊的收益是其QoS的滿意度，即：

其中Q代表服務質(zhì)量指標，例如響應時間、可靠性、保密性等。代表部隊對各類指標的權重，代表了部隊對i類型資源服務質(zhì)量的滿意度。

而聯(lián)合指揮中心的收益是所有部隊的總收益，即：

2.2 均衡分析

任何一個部隊申請資源都希望獲得聯(lián)合指揮中心的優(yōu)質(zhì)資源，滿足自己的QoS，從而完成任務。如果聯(lián)合指揮中心不能滿足其QoS，就會降低部隊作戰(zhàn)效益。所以面對所有申請資源部隊的不同QoS，如何分配資源選取策略，盡可能滿足所有部隊的QoS是軍事云環(huán)境資源調(diào)度的關鍵問題。

在資源調(diào)度過程中，各部隊根據(jù)提交任務的屬性高低按序選擇優(yōu)質(zhì)資源，后一個部隊只能根據(jù)前一個部隊行為來選擇資源，以盡可能滿足自己的QoS，得到最大收益U。本文采用博弈論中的逆向歸納法（backward induction in games）求解博弈的納什均衡解。

定義3 逆向歸納法。從博弈終點節(jié)的直接前行節(jié)開始，然后通過博弈樹逆向歸納的方法，被稱為博弈中的逆向歸納法?？紤]圖1中的擴展博弈，求解是從擴展博弈樹的底端開始?？紤]部隊n的子博弈，如果部隊n-1選擇策略則對于部隊n來說選擇策略優(yōu)于選擇其他任何一個策略。同樣的，當部隊n-1選擇策略時，部隊n的最優(yōu)策略是

將本文的方法和文獻［6-8］進行對比，結(jié)果見表1所示。

表1 方法比較

由表1可以看出，相比其他文獻，本文方法具有實現(xiàn)多邊最優(yōu)，解決多部隊資源使用沖突，增強聯(lián)合作戰(zhàn)指揮效益等優(yōu)點。

3 應用實例與分析

3.1 實驗環(huán)境描述

軍事云環(huán)境資源調(diào)度實例如圖2所示，采用Gambit博弈軟件進行均衡分析。該實例描述了一個虛擬化軍事云環(huán)境下資源調(diào)度問題，聯(lián)合指揮中心資源池趨近無限大，各部隊的QoS指標有響應時間、穩(wěn)定性、保密性。某一時間片段有4個團向聯(lián)合指揮中心提交作戰(zhàn)任務，而每個團的QoS不同，即對不同類型資源的權重不同。聯(lián)合指揮中心在資源調(diào)度過程中首先根據(jù)作戰(zhàn)任務屬性的高低分配各團選擇資源的先后順序，然后再對任務級別相同的團采取先申請先選擇原則分配先后順序。而后一個團只能根據(jù)前一個團的行為來選擇資源，以盡可能滿足自己的QoS。

圖2 軍事云環(huán)境資源調(diào)度結(jié)構(gòu)示意圖

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

調(diào)度模型根據(jù)已有信息生成本次博弈數(shù)據(jù)表2。

表2 軍事云環(huán)境資源調(diào)度數(shù)據(jù)表

確定完本次軍事云環(huán)境資源調(diào)度博弈數(shù)據(jù)之后計算各團選擇不同策略的收益量化，如表3和表4所示。

表3 軍事云環(huán)境資源調(diào)度各團收益（高級別任務）

表4 軍事云環(huán)境資源調(diào)度各團收益（低級別任務）

經(jīng)過收益量化計算后，將上述數(shù)據(jù)輸入Gambit博弈軟件進行均衡分析。由此可得到博弈樹如圖3、圖4所示。

圖3 軍事云環(huán)境資源調(diào)度博弈樹（高級別任務）

圖4 軍事云環(huán)境資源調(diào)度博弈樹（低級別任務）

實驗結(jié)果表示可分別從高低級別任務的博弈中找到唯一一個納什均衡解，構(gòu)成本次軍事云環(huán)境資源調(diào)度的納什均衡解，結(jié)果為：，即4個團均會選擇第2個策略。

3.3 實驗分析

對上述納什均衡可解釋為：軍事云環(huán)境資源調(diào)度過程中，首先保障高級別任務的資源分配，然后同一級別任務的各部隊根據(jù)前一個部隊的策略行動，盡可能選擇優(yōu)質(zhì)資源來執(zhí)行作戰(zhàn)任務，使自己的收益最大。即在納什均衡中，各部隊均會選擇最優(yōu)資源來執(zhí)行任務。

以上結(jié)果表明，本文所提出的軍事云環(huán)境資源調(diào)度模型及方法可以更加合理、有效地反映策略收益對部隊執(zhí)行任務的影響，并且可以有效地進行最優(yōu)的資源調(diào)度。

4 結(jié)論

軍事云環(huán)境是以云計算技術為基礎，加快了信息共享的步伐，促進戰(zhàn)斗力生成模式向適應信息化戰(zhàn)爭的方向轉(zhuǎn)變，為今后聯(lián)合作戰(zhàn)指揮帶來顯著的效益。本文建立了動態(tài)博弈的資源調(diào)度模型MCED-GRSM，并進行了詳細的定義。該模型首先根據(jù)各部隊任務的屬性高低分配選擇資源的優(yōu)先權，然后對任務屬性相同的團采取先申請先選擇分配優(yōu)先權，最后給出了博弈的均衡求解過程。從聯(lián)合作戰(zhàn)指揮角度出發(fā)，將軍事云環(huán)境資源分配問題通過動態(tài)博弈中完全信息擴展博弈模型進行分析，使資源調(diào)度提高效率，增加聯(lián)合作戰(zhàn)效益。最后，通過一個調(diào)度實例對本文提出的模式和方法進行了驗證，實驗證明是有效和可行的。

［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］王俊麗，申良強，雷建棟，等.云計算技術應用于軍事信息系統(tǒng)設想［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- ），男，河南鄭州人，碩士研究生，助理工程師。研究方向：云計算資源管理、博弈論。