牛 侃，張恒巍，王晉東，歐陽(yáng)旦，王 娜

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

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

牛 侃1，2，張恒巍1，王晉東1，歐陽(yáng)旦3，王 娜1

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

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

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

0 引言

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

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

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

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

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

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

1.1 模型假設(shè)

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

假設(shè)2.類(lèi)型假設(shè) 假設(shè)不同部隊(duì)的需求不同，提出的QoS不同。

假設(shè)3.收益假設(shè) 假設(shè)所有部隊(duì)的目標(biāo)都是在滿(mǎn)足自己QoS的前提下，請(qǐng)求資源來(lái)完成任務(wù)。聯(lián)合指揮中心的目標(biāo)是盡可能滿(mǎn)足所有部隊(duì)提出的需求，反饋資源完成其任務(wù)。

1.2 模型定義

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

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

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

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

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

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

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

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

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

2.1 收益量化計(jì)算

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

本文認(rèn)為各部隊(duì)的收益是其QoS的滿(mǎn)意度，即：

其中Q代表服務(wù)質(zhì)量指標(biāo)，例如響應(yīng)時(shí)間、可靠性、保密性等。代表部隊(duì)對(duì)各類(lèi)指標(biāo)的權(quán)重，代表了部隊(duì)對(duì)i類(lèi)型資源服務(wù)質(zhì)量的滿(mǎn)意度。

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

2.2 均衡分析

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

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

定義3 逆向歸納法。從博弈終點(diǎn)節(jié)的直接前行節(jié)開(kāi)始，然后通過(guò)博弈樹(shù)逆向歸納的方法，被稱(chēng)為博弈中的逆向歸納法?？紤]圖1中的擴(kuò)展博弈，求解是從擴(kuò)展博弈樹(shù)的底端開(kāi)始?？紤]部隊(duì)n的子博弈，如果部隊(duì)n-1選擇策略則對(duì)于部隊(duì)n來(lái)說(shuō)選擇策略?xún)?yōu)于選擇其他任何一個(gè)策略。同樣的，當(dāng)部隊(duì)n-1選擇策略時(shí)，部隊(duì)n的最優(yōu)策略是

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

表1 方法比較

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

3 應(yīng)用實(shí)例與分析

3.1 實(shí)驗(yàn)環(huán)境描述

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

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

3.2 博弈收益計(jì)算及均衡求解

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

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

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)分析

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

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

4 結(jié)論

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

［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］熊家軍，李強(qiáng).云計(jì)算及其軍事應(yīng)用［M］.北京：科學(xué)出版社，2011：173-174.

［10］王俊麗，申良強(qiáng)，雷建棟，等.云計(jì)算技術(shù)應(yīng)用于軍事信息系統(tǒng)設(shè)想［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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61303074，61309013）

牛 侃（1988- ），男，河南鄭州人，碩士研究生，助理工程師。研究方向：云計(jì)算資源管理、博弈論。