孫巖煒，郭云川，張玲翠，方濱興

(1.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100093；2.東莞電子科技大學(xué)電子信息工程研究院，廣東 東莞 523808)

基于多選項(xiàng)二次聯(lián)合背包的態(tài)勢(shì)感知資源分配算法

孫巖煒1，郭云川1，張玲翠1，方濱興2

(1.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100093；2.東莞電子科技大學(xué)電子信息工程研究院，廣東 東莞 523808)

為了有效應(yīng)對(duì)潛在網(wǎng)絡(luò)威脅，通過(guò)合理利用資源達(dá)到最大化提升當(dāng)前環(huán)境安全態(tài)勢(shì)的目的，研究了有限資源的最優(yōu)分配方案。網(wǎng)絡(luò)態(tài)勢(shì)的整體性特點(diǎn)使針對(duì)某一指標(biāo)的改善可能會(huì)間接影響其他指標(biāo)，并且投入力度不同，影響程度也有所差異。針對(duì)上述特性，將問(wèn)題抽象成多選項(xiàng)二次聯(lián)合背包模型，通過(guò)二次背包特性表示態(tài)勢(shì)評(píng)估指標(biāo)項(xiàng)之間的相互影響，通過(guò)多選項(xiàng)背包特性來(lái)表示單個(gè)指標(biāo)項(xiàng)的多種投入可能。最后對(duì)其做半定規(guī)劃松弛，采用分支定界法對(duì)問(wèn)題進(jìn)行求解。實(shí)驗(yàn)證明了算法的準(zhǔn)確性和高效性。

資源分配；態(tài)勢(shì)感知；多選項(xiàng)二次聯(lián)合背包；半定松弛

1 引言

態(tài)勢(shì)感知的定義最早由Endsley在1988年提出，強(qiáng)調(diào)在一定的空間和時(shí)間范圍內(nèi)對(duì)環(huán)境中元素的獲取和理解，并且對(duì)未來(lái)的狀態(tài)進(jìn)行預(yù)測(cè)。隨后在1995年又提出了態(tài)勢(shì)感知模型[1]，如圖1所示。該定義被應(yīng)用到網(wǎng)絡(luò)中，引起了眾多學(xué)者的注意，近年來(lái)，涌現(xiàn)出了大量的研究文獻(xiàn)，研究?jī)?nèi)容主要包括數(shù)據(jù)采集[2]、數(shù)據(jù)融合[3,4]、未知異常檢測(cè)[5]和態(tài)勢(shì)可視化展示[6]等，而對(duì)用戶進(jìn)行決策支持的研究則相對(duì)較少。正如Tadda等[7]的闡述，目前態(tài)勢(shì)感知的討論還僅局限于某一個(gè)特定的時(shí)間點(diǎn)。理想化的模型應(yīng)像Webb等[8]提出的，分析當(dāng)前網(wǎng)絡(luò)環(huán)境態(tài)勢(shì)，產(chǎn)生相應(yīng)的措施，態(tài)勢(shì)受措施影響，進(jìn)而形成新的態(tài)勢(shì)，如此循環(huán)往復(fù)。由此可見(jiàn)，決策支持模塊的研究，是保證整體態(tài)勢(shì)感知實(shí)時(shí)性的關(guān)鍵。

圖1 態(tài)勢(shì)感知模型

依照ISO27001、NIST SP800等現(xiàn)有的風(fēng)險(xiǎn)評(píng)估準(zhǔn)則，以及細(xì)化的安全評(píng)估指標(biāo)子項(xiàng)[9]，用戶很容易將當(dāng)前環(huán)境的各個(gè)指標(biāo)進(jìn)行量化考核，最終加權(quán)得到整體的態(tài)勢(shì)評(píng)估結(jié)果。但是面對(duì)亟待改進(jìn)的指標(biāo)子項(xiàng)以及受限的資源總量，如何將資源在指標(biāo)子項(xiàng)之間進(jìn)行分配，從而最大化地提升整體的態(tài)勢(shì)評(píng)估結(jié)果，是一個(gè)復(fù)雜的規(guī)劃問(wèn)題。因?yàn)閼B(tài)勢(shì)是一個(gè)整體的概念，各指標(biāo)子項(xiàng)之間存在著相互的影響關(guān)系，牽一發(fā)而動(dòng)全身。例如，通過(guò)態(tài)勢(shì)評(píng)估，發(fā)現(xiàn)某些關(guān)鍵區(qū)域缺乏管理和監(jiān)督，并且工作人員安全意識(shí)不足。針對(duì)此情況，如果投入大量資源，加大人員考核力度和監(jiān)管力度，雖然在一定程度上有利于員工提升自己的安全意識(shí)，但同時(shí)對(duì)員工的過(guò)分監(jiān)督、懷疑與不信任，也會(huì)產(chǎn)生不可忽視的社會(huì)心理學(xué)問(wèn)題[10]，員工有可能表現(xiàn)出消極怠工甚至報(bào)復(fù)的行為，即對(duì)態(tài)勢(shì)的其他指標(biāo)子項(xiàng)產(chǎn)生負(fù)面影響。正是由于這些錯(cuò)綜復(fù)雜的關(guān)聯(lián)關(guān)系，管理者面對(duì)大量有待改進(jìn)的指標(biāo)子項(xiàng)，即使有很多改進(jìn)手段，但容易因考慮不周投入不適當(dāng)而造成資源的不均衡分配，使最后收益甚微。

面對(duì)大量的指標(biāo)子項(xiàng)，如何分配有限的資源使收益最大化，是典型的背包問(wèn)題。雖然背包問(wèn)題有很多種變形，而且相應(yīng)的算法也很成熟，但是應(yīng)用到態(tài)勢(shì)感知環(huán)境下，依然有一些問(wèn)題沒(méi)有得到很好的解決。首先，本場(chǎng)景指標(biāo)子項(xiàng)之間存在相互影響，并且不同的投入力度，其影響程度也有所差異，目前，尚無(wú)任何一個(gè)模型能夠很好地模擬上述特性；其次，目前，有關(guān)背包問(wèn)題的研究，隨著投入的增長(zhǎng)，對(duì)應(yīng)的產(chǎn)出是單調(diào)遞增的，而本場(chǎng)景可能存在產(chǎn)出不增反降的情況，目前，針對(duì)此情況的求解研究十分有限。

針對(duì)上述兩點(diǎn)，本文的主要貢獻(xiàn)如下：將二次背包問(wèn)題與多選項(xiàng)背包問(wèn)題相結(jié)合，提出了多選項(xiàng)二次聯(lián)合背包模型（MCQKP,multiple-choice quadratic knapsack problem），從而很好地解決了態(tài)勢(shì)感知環(huán)境下的資源分配問(wèn)題；在求解問(wèn)題時(shí)，考慮了收益矩陣元素取值為負(fù)的情況，給出了半定規(guī)劃松弛的求解方法。

2 相關(guān)工作

隨著應(yīng)用背景的不同，資源分配方法存在巨大差異，根據(jù)資源分配模型中參與方的數(shù)量差異，可大致分為如下3種：只有單方參與的資源分配問(wèn)題、雙方參與的資源分配問(wèn)題以及多方參與的資源分配問(wèn)題。

單方參與的資源分配問(wèn)題主要應(yīng)用在云計(jì)算、通信網(wǎng)絡(luò)數(shù)據(jù)傳輸、網(wǎng)絡(luò)防護(hù)措施選擇等方面，這類問(wèn)題可簡(jiǎn)單概括為：在滿足一定限制的前提下，使參與方的收益最大化或者損失最小化。如果收益函數(shù)是線性的，則可用典型的背包問(wèn)題求解，如果是非線性的，則可以通過(guò)取對(duì)數(shù)等方式將問(wèn)題線性化之后求解[11]，或采用典型的數(shù)據(jù)分組分析模型進(jìn)行分析[12]。Aisopos 等[13]通過(guò)背包模型，將云計(jì)算中需要的內(nèi)存、硬盤、CPU資源進(jìn)行綜合考慮，并且根據(jù)用戶需求碎片化的特點(diǎn)，將多重背包問(wèn)題進(jìn)行了整數(shù)松弛，使整個(gè)求解過(guò)程的時(shí)間復(fù)雜度大大降低。Xiao 等[14]的研究目的并非收益最大化，而是在滿足虛擬機(jī)需求的前提下，盡可能減少工作實(shí)體機(jī)數(shù)量，從而達(dá)到節(jié)約資源的目的。另外，通信過(guò)程中的帶寬分配，也經(jīng)常用線性規(guī)劃模型來(lái)處理。Hajiaghajani等[15]討論終端對(duì)終端通信的過(guò)程，在保證服務(wù)質(zhì)量的前提下，使最大速率(sum-rate)最大化。Ferdosian等[16]將背包算法用在LTE技術(shù)當(dāng)中，在帶寬有限的前提下，通過(guò)評(píng)估量化，選取用戶的一個(gè)子集提供服務(wù)，從而實(shí)現(xiàn)系統(tǒng)性能的最大化。同樣受限于帶寬，Sheu等[17]討論無(wú)線城域網(wǎng)的資源分配問(wèn)題，力求通過(guò)合理分配帶寬，使網(wǎng)絡(luò)吞吐量達(dá)到最大化，同時(shí)使受眾用戶數(shù)量最大化。

涉及雙方參與的資源分配問(wèn)題，最典型的研究是基于博弈論的資源分配方法。這類研究在網(wǎng)絡(luò)攻防領(lǐng)域應(yīng)用十分廣泛，主要是通過(guò)計(jì)算納什均衡，來(lái)指導(dǎo)管理員對(duì)資源的分配。例如，F(xiàn)ielder等[18]通過(guò)模擬攻防雙方的零和博弈，算出混合策略下的納什均衡，從而指導(dǎo)用戶進(jìn)行資源分配優(yōu)化。Khouzani 等[19]在考慮威脅動(dòng)態(tài)轉(zhuǎn)移時(shí)，同樣通過(guò)博弈論的方法，計(jì)算帕累托最優(yōu)，進(jìn)而計(jì)算系統(tǒng)損失的最小值。同樣在資源受限的前提下，Ojamaa等[20]通過(guò)離散動(dòng)態(tài)規(guī)劃，計(jì)算帕累托最優(yōu)方案，對(duì)用戶進(jìn)行決策支持。

涉及多方參與的資源分配問(wèn)題，主要應(yīng)用在云計(jì)算、設(shè)備到設(shè)備（D2D）通信等環(huán)境，普遍采用博弈論下的拍賣模型對(duì)問(wèn)題進(jìn)行模擬和求解。在D2D通信背景下，Wang等[21]提出迭代聯(lián)合拍賣算法，通過(guò)功率控制和聯(lián)合信道管理，有效提高用戶設(shè)備的續(xù)航能力。Hasan等[22]通過(guò)拍賣的方法，研究多層異構(gòu)網(wǎng)絡(luò)下的頻率、時(shí)隙等資源的合理分配。有關(guān)云計(jì)算下的資源分配，Zhang等[23]針對(duì)用戶需求的異構(gòu)性，提出了一種新的競(jìng)標(biāo)表述方式，并且構(gòu)建了具有激勵(lì)機(jī)制的在線云資源拍賣機(jī)制。

結(jié)合上述分析，由于本文研究的目的旨在利用有限資源最大化提升當(dāng)前環(huán)境的安全態(tài)勢(shì)，并未涉及攻擊方，以及其他多方參與的情況，因此，本文研究單方參與的關(guān)于網(wǎng)絡(luò)安全防護(hù)的資源分配問(wèn)題。與本文類似的研究還包括：Gupta等[24]考慮網(wǎng)絡(luò)風(fēng)險(xiǎn)與相應(yīng)策略之間的關(guān)系，假設(shè)針對(duì)每一個(gè)潛在的風(fēng)險(xiǎn)，都會(huì)有一個(gè)補(bǔ)救措施與之對(duì)應(yīng)，但同時(shí)該措施可能會(huì)引起其他方面的新風(fēng)險(xiǎn)產(chǎn)生，于是措施選擇問(wèn)題便轉(zhuǎn)化成了最小覆蓋的問(wèn)題。雖然考慮了風(fēng)險(xiǎn)與措施之間的相互影響，但是在建模時(shí)將問(wèn)題進(jìn)行了簡(jiǎn)化，針對(duì)某一個(gè)風(fēng)險(xiǎn)，只設(shè)定了解決、未解決和部分解決這3個(gè)狀態(tài)，這使其決策支持算法的計(jì)算量大大降低。在它的基礎(chǔ)上，Viduto 等[25]還考慮了投入成本的限制因素；Schilling等[11]從德國(guó)聯(lián)邦信息安全辦公室獲取到大量有價(jià)值的安全數(shù)據(jù)，從中提取出500多項(xiàng)威脅以及1 200多項(xiàng)應(yīng)對(duì)措施，以網(wǎng)絡(luò)組件為單位，計(jì)算威脅值。Rees等[26]主要對(duì)收益、損失等參數(shù)進(jìn)行了討論，通過(guò)模糊集理論來(lái)處理風(fēng)險(xiǎn)管理當(dāng)中的不確定性。Sawik等[27]在評(píng)估風(fēng)險(xiǎn)時(shí)用到了風(fēng)險(xiǎn)價(jià)值和條件風(fēng)險(xiǎn)價(jià)值這2個(gè)指標(biāo)方法。Mukhopadhyay 等[28]通過(guò)基于耦合的貝葉斯信念網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)風(fēng)險(xiǎn)進(jìn)行評(píng)估和量化，并且根據(jù)不同的需求以及有限的投入資源，動(dòng)態(tài)調(diào)整決策支持方案。Gordon等[29]將風(fēng)險(xiǎn)與投入進(jìn)行分級(jí)討論，針對(duì)不同的安全風(fēng)險(xiǎn)等級(jí)，計(jì)算相對(duì)應(yīng)的最優(yōu)投入策略。

雖然文獻(xiàn)[11,24,25]做了內(nèi)容類似的研究，在選擇防護(hù)措施時(shí)考慮到了整體性特點(diǎn)，提出了防護(hù)措施與安全威脅之間多對(duì)多的映射關(guān)系，但作者在選擇措施時(shí)均只考慮選與不選2種可能，并沒(méi)有考慮實(shí)施力度的差異，因此，上述研究均有不同程度的局限性。為了克服上述局限，本文采用二次背包模型對(duì)問(wèn)題進(jìn)行模擬，同時(shí)為了使本文的研究更加貼近實(shí)際，對(duì)問(wèn)題進(jìn)行了擴(kuò)充，目前已有的關(guān)于二次背包及其變形[30～32]均已無(wú)法滿足需求，因此，本文提出了新的背包模型——多選項(xiàng)二次聯(lián)合背包。

3 多選項(xiàng)二次聯(lián)合背包問(wèn)題模型

首先對(duì)應(yīng)用場(chǎng)景進(jìn)行描述，指出目前研究的不足，接著通過(guò)示例引出問(wèn)題的數(shù)學(xué)表示，并對(duì)問(wèn)題當(dāng)中的參數(shù)及合理性做了簡(jiǎn)單討論，最后提出多選項(xiàng)二次聯(lián)合背包模型的數(shù)學(xué)表述。

3.1 問(wèn)題描述

在描述問(wèn)題之前，先給出指標(biāo)子項(xiàng)以及投入子項(xiàng)的定義，接著給出態(tài)勢(shì)環(huán)境下的背包問(wèn)題的定義，并且通過(guò)逐步引入限制條件，指出目前研究存在的不足。

定義1指標(biāo)子項(xiàng)。當(dāng)前環(huán)境下，將影響整體態(tài)勢(shì)的每一個(gè)環(huán)節(jié)，細(xì)分為可供評(píng)估的若干個(gè)指標(biāo)項(xiàng)，稱之為指標(biāo)子項(xiàng)，如系統(tǒng)頑健性這個(gè)環(huán)節(jié)包含管理員密碼修改頻率是否達(dá)標(biāo)、服務(wù)器代碼是否包含容錯(cuò)處理和系統(tǒng)內(nèi)部是否開(kāi)啟不必要的服務(wù)等指標(biāo)子項(xiàng)；項(xiàng)目及人員管理環(huán)節(jié)包含特定操作是否有配套規(guī)范守則、人員是否遵守、是否有專人監(jiān)督和是否定期開(kāi)展人員安全意識(shí)考核等子項(xiàng)。每一個(gè)指標(biāo)子項(xiàng)用INDn表示。

定義2投入子項(xiàng)。態(tài)勢(shì)評(píng)估結(jié)果中未達(dá)標(biāo)的指標(biāo)子項(xiàng)，即需要投入一定資源進(jìn)行改善的指標(biāo)項(xiàng)。投入子項(xiàng)用INVn表示，每個(gè)投入子項(xiàng)包含2個(gè)屬性：改善所需資源消耗ri和改善后帶來(lái)的評(píng)估提升值pi（相關(guān)參數(shù)將在3.2節(jié)做簡(jiǎn)單討論，而具體的資源消耗與提升函數(shù)關(guān)系的討論，超出了本文的研究范圍，在這里只做簡(jiǎn)單的假設(shè)）。

定義3態(tài)勢(shì)環(huán)境下的背包問(wèn)題。在投入資源總量受限的條件下，如何選取投入子項(xiàng)進(jìn)行資源分配，使在不超過(guò)總資源限制的前提下，達(dá)到評(píng)估提升總和最大，這是態(tài)勢(shì)環(huán)境下的背包問(wèn)題。圖2以柱狀圖的形式描述該問(wèn)題，針對(duì)每一個(gè)指標(biāo)項(xiàng)，其高度表示態(tài)勢(shì)評(píng)估值大小，虛線框表示對(duì)該項(xiàng)指標(biāo)進(jìn)行投入時(shí)所獲得的態(tài)勢(shì)收益提升，箭頭虛線表示一種可行的分配方案。

圖2 簡(jiǎn)單資源分配

在上述問(wèn)題的基礎(chǔ)上，考慮項(xiàng)目之間存在相互影響的情況。如根據(jù)態(tài)勢(shì)評(píng)估結(jié)果，需要在人員培訓(xùn)、人員考核等子項(xiàng)投入資源，最直接的表現(xiàn)是每個(gè)投入子項(xiàng)獲得相應(yīng)的評(píng)估值提升。同時(shí)，人員培訓(xùn)還有助于提升員工自身的安全意識(shí)，從而在其他工作，如代碼質(zhì)量方面、密碼強(qiáng)度方面和應(yīng)急響應(yīng)方面有間接的提升。但是，加強(qiáng)監(jiān)督力度等措施，會(huì)對(duì)工作人員的心里產(chǎn)生不可忽視的影響，甚至產(chǎn)生報(bào)復(fù)心里，惡意破壞系統(tǒng)內(nèi)部的正常工作。在本例中的直接體現(xiàn)即對(duì)一些特定項(xiàng)產(chǎn)生負(fù)收益，資源分配圖示如圖3所示。與圖2相比較，負(fù)收益通過(guò)實(shí)線箭頭表示(圖中部分表示簡(jiǎn)化為pxx)。

從圖3可以看出，在投入第2項(xiàng)的時(shí)候，除了會(huì)獲得自身的收益p22之外，其他項(xiàng)的收益也會(huì)受到相應(yīng)的影響，如圖3中p21、p23等。但是，與二次背包問(wèn)題不同的是，這里的相互影響是“靜態(tài)”的，只要對(duì)人員培訓(xùn)進(jìn)行投入，那么與其相關(guān)聯(lián)的p21、p23等就會(huì)出現(xiàn)。在這種情況下，只要將問(wèn)題中的pi稍作調(diào)整，即，其中，m為受影響項(xiàng)個(gè)數(shù)，pii表示投入項(xiàng)i本身的收益，pij表示投入項(xiàng)i對(duì)子項(xiàng)j的間接影響收益。經(jīng)過(guò)轉(zhuǎn)化之后，問(wèn)題還是可以順利轉(zhuǎn)化為簡(jiǎn)單的背包問(wèn)題。

圖3 考慮相互影響的資源分配

上面的討論針對(duì)某一個(gè)投入項(xiàng)i，只有投入與不投入2種情況。而實(shí)際中往往每一項(xiàng)i可以有多種投入選擇，即可以選擇投入ri1,ri2,…,rin的資源，同時(shí)，其相對(duì)應(yīng)的收益也會(huì)存在不同，即。這個(gè)問(wèn)題下的相互影響，已經(jīng)不再是“靜態(tài)”影響，而是會(huì)隨著投入的多少發(fā)生改變，同樣的投入子項(xiàng)，不同的資源分配，往往會(huì)導(dǎo)致大不相同的提升結(jié)果。例如，適度對(duì)人員監(jiān)督子項(xiàng)進(jìn)行投入，會(huì)獲得較為理想的正收益，如圖4(c)所示，但是如果過(guò)度投入，則會(huì)對(duì)其他子項(xiàng)產(chǎn)生負(fù)面影響，如圖4(a)所示。在這種情況下，現(xiàn)有模型已經(jīng)無(wú)法滿足求解需求，因此，本文提出了多選項(xiàng)二次聯(lián)合背包模型。

3.2 多選項(xiàng)二次聯(lián)合背包模型參數(shù)討論

受二次背包問(wèn)題的啟發(fā)，本文通過(guò)二維矩陣表述指標(biāo)子項(xiàng)之間的相互影響收益，本文統(tǒng)稱為收益矩陣Λ。其中，對(duì)角線上的元素表示自身收益，其余元素表示相互影響收益；由于每個(gè)子項(xiàng)存在多種投入可能，并且每種投入對(duì)其他子項(xiàng)的影響也存在差異，故矩陣當(dāng)中的每個(gè)元素通過(guò)4個(gè)角標(biāo)進(jìn)行描述，其中，pij,kl表示第i項(xiàng)投入j時(shí)對(duì)第k項(xiàng)投入l時(shí)的影響收益，*表示不允許出現(xiàn)的數(shù)[33]。

通過(guò)一個(gè)簡(jiǎn)單的例子介紹收益矩陣（為了介紹方便，下述實(shí)例并不考慮資源總量的限制）。假設(shè)目前可供投入的子項(xiàng)只有人員考核、人員監(jiān)督和人員培訓(xùn)3項(xiàng)，每一項(xiàng)可以有投入值為0、1和2這3種選擇。根據(jù)定義可以得到如下收益矩陣Λ為

假設(shè)投入方案為：對(duì)人員考核這一項(xiàng)投入值為1，人員監(jiān)督投入2，對(duì)人員培訓(xùn)不進(jìn)行投入，通過(guò)0?1向量α表示投入方案，此方案可以通過(guò)如下向量表示為

同時(shí)，此分配方案對(duì)應(yīng)的總收益為

收益矩陣中的元素pij,kl取值，可參見(jiàn)文獻(xiàn)[9]等，本文只對(duì)其合理性做簡(jiǎn)單討論。

1) 矩陣中的元素，如果i=k則j=l,即不存在p11,22等元素，在矩陣中用*表示。在上述實(shí)例中，即不存在人員考核子項(xiàng)投入1對(duì)人員考核子項(xiàng)投入2造成的影響。

2) 針對(duì)矩陣當(dāng)中的元素pij,kl，當(dāng)j為0，l取任意數(shù)時(shí)，根據(jù)定義可得pij,kl的取值為0，對(duì)應(yīng)上例中的p30,11、p30,22等元素，即投入為0的子項(xiàng)i對(duì)其他任何子項(xiàng)的影響為0。但是它關(guān)于主對(duì)角線位置對(duì)稱的元素pkl,ij在上述情況下，卻可能存在不為0的情況，對(duì)應(yīng)上例中的p11,30、p22,30等元素，所以本矩陣嚴(yán)格意義上并非對(duì)稱矩陣。但是，可以將關(guān)于主對(duì)角線位置對(duì)稱的兩兩元素取平均值，人工將矩陣對(duì)稱化，這樣做的目的是方便后續(xù)計(jì)算，同時(shí)不影響計(jì)算結(jié)果，詳細(xì)證明見(jiàn)命題1。

3) 如果i和k保持不變，j和l的任意變化，都會(huì)使影響因子產(chǎn)生變化。

命題1在求解收益最大化的過(guò)程當(dāng)中，對(duì)于任何一個(gè)收益矩陣Λ，在不影響計(jì)算結(jié)果的前提下，都可以化為一個(gè)等價(jià)的對(duì)稱收益矩陣Λ。

證明假設(shè)原始收益矩陣Λ中的元素用pij,kl表示，新建對(duì)稱矩陣 ′Λ中的元素用pi′j,kl表示，令

從上面的表述中可以看出 ′Λ是對(duì)稱的。現(xiàn)在要證明Λ和 ′Λ具有相同的最優(yōu)分配方案。設(shè)?α為原始收益矩陣Λ的最優(yōu)分配方案，即

則總的收益提升P可表示為

從上述等式變換可以得知，矩陣Λ的最優(yōu)分配方案α?同時(shí)也是對(duì)稱矩陣Λ′的最優(yōu)分配方案，因此，將矩陣進(jìn)行對(duì)稱化處理，并不影響最優(yōu)分配方案，故命題得證。

3.3 多選項(xiàng)二次聯(lián)合背包模型數(shù)學(xué)表述

通過(guò)上面的描述，最終可以得到多選項(xiàng)二次聯(lián)合背包的數(shù)學(xué)抽象。

假設(shè)共有n個(gè)物品被分為m個(gè)相互獨(dú)立的分組：Ν1,…,Nm，每一個(gè)物品j∈Ni，重量為wij，Λ為n×n矩陣，其中，pij,ij表示第i組第j個(gè)物品被選中所獲得的收益。另外，pij,kl+pkl,ij表示第i組第j個(gè)物品與第k組第l個(gè)物品同時(shí)選中時(shí)所產(chǎn)生的額外收益，背包總?cè)萘坑胏表示。同時(shí)出于書(shū)寫(xiě)以及計(jì)算方便，本文規(guī)定pij,ij′=0 (其中j ≠ j′)。多選項(xiàng)二次聯(lián)合背包（MCQKP）模型可以表述為

可以看出，該問(wèn)題是NP難題，因?yàn)槿绻サ艏s束條件(1)，問(wèn)題便轉(zhuǎn)換為了一般的二次背包問(wèn)題，而二次背包是NP難題的。另外，與大部分的研究不同，從實(shí)際情況出發(fā)，本模型并沒(méi)有限定矩陣Λ當(dāng)中的元素的取值為非負(fù)。

需要指出的是，從MCQKP的數(shù)學(xué)表述上來(lái)看，它與廣義二次分配問(wèn)題[34]的表述是極為類似的。但是，二次分配問(wèn)題的定義，是將M項(xiàng)任務(wù)分發(fā)給N種可能的設(shè)備去處理，其資源消耗矩陣表示如下。

根據(jù)定義以及矩陣表述可以看出，二次分配問(wèn)題當(dāng)中的每一項(xiàng)任務(wù)M都對(duì)應(yīng)相同數(shù)目N的分配可能。對(duì)應(yīng)背包問(wèn)題，它等同于要求每一個(gè)分組內(nèi)的物品數(shù)目均相同，這顯然是有局限性的，所以本文闡述的背包模型，在適用范圍上要優(yōu)于目前已有的廣義二次分配問(wèn)題。

4 多選項(xiàng)二次聯(lián)合背包問(wèn)題求解

對(duì)于背包類的NP問(wèn)題求解，可分為近似解與精確解兩大類，本文所提的解法屬于精確解。針對(duì)背包問(wèn)題的精確求解，目前已有較為普遍的解決方案CPLEX Optimization Studio，但是受限于其計(jì)算問(wèn)題上界時(shí)松弛程度較大，它無(wú)法快速地求解這類NP問(wèn)題，尤其是當(dāng)計(jì)算規(guī)模大于一定規(guī)模的時(shí)候，求解時(shí)間將超過(guò)1 h甚至更長(zhǎng)時(shí)間。雖然所有精確解在計(jì)算NP問(wèn)題時(shí)的時(shí)間復(fù)雜度均為指數(shù)級(jí)，但是計(jì)算不同精確度的上界，對(duì)于整個(gè)計(jì)算時(shí)間的影響十分明顯。因此，本文借鑒已有研究，對(duì)問(wèn)題進(jìn)行了半定松弛，通過(guò)松弛求解出相比于CPLEX更為精確的上界，并通過(guò)啟發(fā)式方法求得問(wèn)題的下界，最后通過(guò)分支定界法對(duì)問(wèn)題進(jìn)行精確求解。

4.1 通過(guò)半定松弛求解問(wèn)題上界

根據(jù)文獻(xiàn)[35]提出的QCR方法，本文對(duì)MCQKP同樣做了半定松弛，表述如下。

上述問(wèn)題可以通過(guò)CSDP注1：該工具可在網(wǎng)站http://www.coin-or.org/獲取。等已有的求解工具進(jìn)行求解，求解時(shí)間也較為理想，相關(guān)證明以及求解方法參考文獻(xiàn)[35]，在此不做過(guò)多論述。

4.2 通過(guò)啟發(fā)式算法計(jì)算問(wèn)題下界

算法參照文獻(xiàn)[36]中介紹的計(jì)算下界的啟發(fā)式方法，但是由于本問(wèn)題的分組特性，需要在原方法上加以修改，具體計(jì)算步驟如下。

1) 計(jì)算問(wèn)題當(dāng)中每一個(gè)分組i里面收益最高的子項(xiàng)，，并置xij=1。

3) 逐個(gè)遍歷集合{xij|xij=1}中的每一個(gè)元素，縮小j的值，重新計(jì)算，并記作Plow′；選取使ΔPlow=Plow–Plo′w最小的xij變換，即xij置0，xij′置。重復(fù)此過(guò)程直到W≤c時(shí)結(jié)束。至此，算法已得到了問(wèn)題的一個(gè)下界Plow1。

4) 繼續(xù)對(duì)Plow1進(jìn)行優(yōu)化。依次遍歷集合{xij|xij=0}的部分，如果xij子項(xiàng)可以直接投入所需資源而沒(méi)有超過(guò)總限制，則將ΔPijlow記錄為投入該子項(xiàng)所獲得的利益增量。如果無(wú)法直接投入，在不超過(guò)總資源的基礎(chǔ)上，將該子項(xiàng)與已投入的子項(xiàng)依次輪換，將 ΔPijlow記錄為收益增量的最大值。選取每一個(gè)ΔPijlow當(dāng)中的最大值進(jìn)行置換，重復(fù)此步驟，直到ΔPlow為0時(shí)停止，這樣算法就得到了一個(gè)較為優(yōu)質(zhì)的下界。

4.3 通過(guò)分支定界法求解問(wèn)題的最優(yōu)解

在得到問(wèn)題的上界和下界之后，可以用經(jīng)典的分支定界法對(duì)問(wèn)題進(jìn)行求解，相關(guān)求解的方法在文獻(xiàn)[36]中已有較為詳細(xì)的論述。

5 實(shí)驗(yàn)環(huán)境與結(jié)果分析

5.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

本文在Windows 8系統(tǒng)下進(jìn)行獨(dú)立性能測(cè)試。測(cè)試機(jī)配置為Intel Core i3-3240 3.4 GHz處理器，6 GB內(nèi)存，其中，CSDP算法采用ECLIPSE集成CSDP-6.1.1進(jìn)行計(jì)算處理， ECLIPSE分配的虛擬內(nèi)存為2 GB；CLPEX運(yùn)行環(huán)境為CPLEX Optimization Studio Community Edition 12.6。

本文從文獻(xiàn)[9]中提取了30組指標(biāo)子項(xiàng)，規(guī)定其中10組指標(biāo)子項(xiàng)可投入選項(xiàng)為4項(xiàng)，其余20組指標(biāo)可投入選項(xiàng)為3項(xiàng)，生成了100×100的收益矩陣Λ。其中，子項(xiàng)之間的相互影響根據(jù)文獻(xiàn)[3,37]當(dāng)中的威脅與防護(hù)措施之間多對(duì)多的映射來(lái)生成。表1列舉了部分措施所對(duì)應(yīng)的威脅數(shù)目以及可能引起的負(fù)面影響數(shù)目。

表1 防護(hù)措施與威脅對(duì)應(yīng)關(guān)系

具體的各個(gè)子項(xiàng)的量化結(jié)果，文獻(xiàn)沒(méi)有介紹，用戶可以根據(jù)每項(xiàng)指標(biāo)的重要程度差異，來(lái)量化投入資源到該子項(xiàng)時(shí)所能獲得的收益提升。實(shí)驗(yàn)假設(shè)整體態(tài)勢(shì)的最優(yōu)值為100，前10項(xiàng)指標(biāo)項(xiàng)的投入收益p（包含自身收益以及與其相關(guān)的所有間接收益）的范圍是0～4，后20項(xiàng)投入收益p的范圍是0～3。

5.2 實(shí)驗(yàn)高效性結(jié)果分析

首先進(jìn)行運(yùn)行時(shí)間的對(duì)比，通過(guò)隨機(jī)生成不同規(guī)模的收益矩陣，規(guī)定其矩陣密度δ=90%，將矩陣同時(shí)放在CPLEX 12.6 Community Edition環(huán)境與半定規(guī)劃算法進(jìn)行運(yùn)算，運(yùn)行時(shí)間上限定為1 800 s，二者的運(yùn)行時(shí)間對(duì)比如圖5所示。

圖5 算法運(yùn)行時(shí)間隨收益矩陣規(guī)模變化趨勢(shì)

從圖5中可以看到，在規(guī)模較小的情況下，二者的運(yùn)行時(shí)間差異并不明顯，在CPLEX環(huán)境下，運(yùn)算時(shí)間在矩陣規(guī)模達(dá)到30之后開(kāi)始急劇增多，在矩陣規(guī)模達(dá)到50時(shí)，已經(jīng)無(wú)法在1 h內(nèi)求得精確解；而采用半定規(guī)劃求解時(shí)，當(dāng)規(guī)模增加到100時(shí)，其運(yùn)行時(shí)間仍在650 s左右，其1 h內(nèi)能夠計(jì)算出的最大矩陣規(guī)模達(dá)到125；造成差距如此巨大的一個(gè)原因，是由于CPLEX對(duì)于問(wèn)題上界求解的松弛度較高，因此未能有效地縮小枚舉范圍，為了有效地衡量二者在計(jì)算上下界時(shí)的差異，，松弛度越小，表明上下界貼合越接近，搜索空間越小。表2列出了2種算法松弛度的差異，從表2中可以看出，CPLEX計(jì)算的松弛度平均值達(dá)到80.9%，而半定規(guī)劃的松弛度平均值只有22.26%。

5.3 實(shí)驗(yàn)準(zhǔn)確性結(jié)果分析

出于最優(yōu)化計(jì)算結(jié)果的對(duì)比，除了本文提出的多選項(xiàng)二次聯(lián)合背包模型之外，還計(jì)算了經(jīng)典背包分配方案[38]和二次背包[39]分配方案。其中，經(jīng)典背包分配方案在計(jì)算時(shí)只考慮主對(duì)角線元素，而忽視指標(biāo)項(xiàng)之間的相互影響。二次背包分配方案只考慮投入與不投入2種情況，并不考慮多種投入可能。

表2 2類解法松弛度比較

圖6是3種方案的態(tài)勢(shì)評(píng)估總收益P隨著投入資源總量變化的曲線，可看出，給定任意數(shù)量的資源限制，多選項(xiàng)二次聯(lián)合背包模型分配方案獲得的收益都是最大的，而且隨著投入數(shù)目的增加，其優(yōu)勢(shì)表現(xiàn)得越明顯，因?yàn)橘Y源投入越多，其投入的子項(xiàng)數(shù)量也相應(yīng)增多，子項(xiàng)間的相互影響越發(fā)明顯，在投入接近140時(shí)，收益達(dá)到最大值100，而其他2種方案的最大值在90附近。值得注意的是，經(jīng)典背包方案在投入總量為140附近的時(shí)候，出現(xiàn)了態(tài)勢(shì)評(píng)估收益隨投入增加而下降的情況，造成這一現(xiàn)象的原因是各子項(xiàng)之間存在抑制影響，而經(jīng)典背包方案在考慮資源分配時(shí)并沒(méi)有兼顧此類影響，致使出現(xiàn)投入增加而收益下降的情況出現(xiàn)。

圖6 態(tài)勢(shì)評(píng)估收益隨總投入變化

圖7是3種分配方案的投入產(chǎn)出比，表示在某一固定投入總量的情況下，單位資源所能獲得的態(tài)勢(shì)評(píng)估收益。由于某種方案在某些特定的投入總數(shù)限制下，可能存在資源有剩余的情況，所以實(shí)際的投入產(chǎn)出比與總收益的曲線趨勢(shì)并不完全一致。從圖7中可以看出，隨著投入增多，單位資源所能獲得的平均收益均為下降趨勢(shì)，這是由于在資源總量很少的情況下，要想獲得最大化的收益提升，必然要把有限的資源投入到性價(jià)比最高的子項(xiàng)當(dāng)中，隨著投入總量的增加，單位資源所能獲得的收益提升也隨之降低。經(jīng)典方案之所以起點(diǎn)較低，同樣是因?yàn)闆](méi)有考慮子項(xiàng)之間存在的影響收益，單純地選取自身收益最高的子項(xiàng)先行投入，另外2種方案則選取自身收益與影響收益總和最高的子項(xiàng)進(jìn)行投入。但是二次方案沒(méi)有考慮投入的多力度性，在資源總量25附近出現(xiàn)了大幅波動(dòng)，因?yàn)橘Y源總量較少時(shí)，二次方案容易出現(xiàn)資源的不完全利用，即并沒(méi)有把25的資源全部有效分配，而由于方案考慮的力度過(guò)大，剩余資源不足以完成分配，直到總量增加，新增資源與之前的剩余資源足夠進(jìn)行下一次分配，其收益才會(huì)有跳躍式增長(zhǎng)。

圖7 單位資源態(tài)勢(shì)評(píng)估收益隨總投入變化

圖8是算法規(guī)定投入總數(shù)為100的時(shí)候，30項(xiàng)指標(biāo)的投入情況，受到條件限制，二次方案曲線浮動(dòng)較為明顯，相比之下，另外2種投入方案的浮動(dòng)較為平緩。聯(lián)合方案的投入多集中在中線附近，表明投入較為平均。

圖8 指標(biāo)子項(xiàng)投入明細(xì)

與圖8相對(duì)應(yīng)，圖9是算法規(guī)定投入總數(shù)為100的時(shí)候，30項(xiàng)指標(biāo)的提升情況。以聯(lián)合方案的指標(biāo)提升值的升序順序進(jìn)行展示，由于投入資源的差異，各項(xiàng)指標(biāo)的提升差異較為明顯，但是聯(lián)合方案的各項(xiàng)提升較為平均，更加符合態(tài)勢(shì)的整體性特點(diǎn)，同時(shí)整體水平也高于其他2種方案。

圖9 指標(biāo)子項(xiàng)態(tài)勢(shì)評(píng)估值提升明細(xì)

6 結(jié)束語(yǔ)

網(wǎng)絡(luò)安全態(tài)勢(shì)感知雖然受到廣泛關(guān)注，但是絕大部分研究都聚焦于問(wèn)題的發(fā)現(xiàn)和態(tài)勢(shì)的展示，決策支持方面的研究則相對(duì)較少。在發(fā)現(xiàn)威脅以后，如何利用有限的資源最大化地消除隱患，提升當(dāng)前環(huán)境的安全態(tài)勢(shì)，是一個(gè)復(fù)雜的規(guī)劃問(wèn)題。因?yàn)閼B(tài)勢(shì)是一個(gè)整體的概念，各子項(xiàng)之間存在著相互的影響關(guān)系。根據(jù)該特點(diǎn)，本文將問(wèn)題抽象成為一種新的背包模型，即多選項(xiàng)二次聯(lián)合背包，并對(duì)其進(jìn)行了半定規(guī)劃松弛，采用分支定界法對(duì)問(wèn)題進(jìn)行求解。最后通過(guò)模擬實(shí)驗(yàn)，證明了本算法的分配方案，要優(yōu)于目前已有的二次背包分配方案以及經(jīng)典背包分配方案。

[1]ENDSLEY M R.Toward a theory of situation awareness in dynamic systems[J].Human Factors:The Journal of the Human Factors and Ergonomics Society,1995,37(1):32-64.

[2]DIETTERICH T G,BAO X,KEISER V,et al.Machine learning methods for high level cyber situation awareness[M]//Cyber Situational Awareness.Springer US,2010:227-247.

[3]LIU P,JIA X,ZHANG S,et al.Cross-layer damage assessment for cyber situational awareness[J].Advances in Information Security,2010,46:155-176.

[4]PREDEN J,MOTUS L,MERISTE M,et al.Situation awareness for networked systems[C]//2011 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support (CogSIMA).IEEE,2011:123-130.

[5]BRANNON N G,SEIFFERTT J E,DRAELOS T J,et al.Coordinated machine learning and decision support for situation awareness[J].Neural Networks,2009,22(3):316-325.

[6]TAMASSIA R,PALAZZI B,PAPAMANTHOU C.Graph drawing for security visualization[C]//International Symposium on Graph Drawing.Springer Berlin Heidelberg,2008:2-13.

[7]TADDA G P,SALERNO J S.Overview of cyber situation awareness[M].Cyber Situational Awareness.Springer US,2010:15-35.

[8]WEBB J,AHMAD A,MAYNARD S B,et al.A situation awareness model for information security risk management[J].Computers &Security,2014,44:1-15.

[9]Federal Office for Information Security:13 EL:Cross-reference tables of the IT-grundschutz catalogues:13th version (2013).[EB/OL].https:// http://enos.itcollege.ee/～valdo/bsieng/en/gstoolhtml/allgemein/vorwort /00001.html.

[10]GREITZER F L,FRINCKE D A.Combining traditional cyber security audit data with psychosocial data:towards predictive modeling for insider threat mitigation[M]//Insider Threats in Cyber Security.Springer US,2010:85-113.

[11]SCHILLING A,WERNERS B.Optimizing information systems security design based on existing security knowledge[C]//International Conference on Advanced Information Systems Engineering.Springer International Publishing,2015:447-458.

[12]DU J,COOK W D,LIANG L,et al.Fixed cost and resource allocation based on DEA cross-efficiency[J].European Journal of Operational Research,2014,235(1):206-214.

[13]AISOPOS F,TSERPES K,VARVARIGOU T.Resource management in software as a service using the knapsack problem model[J].International Journal of Production Economics,2013,141(2):465-477.

[14]XIAO Z,SONG W,CHEN Q.Dynamic resource allocation using virtual machines for cloud computing environment[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(6):1107-1117.

[15]HAJIAGHAJANI F,RASTI M.Downlink resource reuse for device-to-device communication underlying cellular networks using a generalized knapsack framework[C]//2016 13th IEEE Annual Consumer Communications &Networking Conference (CCNC).IEEE,2016:171-176.

[16]FERDOSIAN N,OTHMAN M,ALI B M,et al.Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks[J].Wireless Networks,2015:1-14.

[17]SHEU J P,KAO C C,YANG S R,et al.A resource allocation scheme for scalable video multicast in WiMAX relay networks[J].IEEE Transactions on Mobile Computing,2013,12(1):90-104.

[18]FIELDER A,PANAOUSIS E,MALACARIA P,et al.Decision support approaches for cyber security investment[J].Decision Support Systems,2016,86:13-23.

[19]KHOUZANI M H R,MALACARIA P,HANKIN C,et al.Efficient numerical frameworks for multi-objective cyber security planning[C]//European Symposium on Research in Computer Security.Springer International Publishing,2016:179-197.

[20]OJAMAA A,TYUGU E,KIVIMAA J.Pareto-optimal situation analysis for selection of security measures[C]//MILCOM 2008-2008 IEEEMilitary Communications Conference.IEEE,2008:1-7.

[21]WANG F,XU C,SONG L,et al.Energy-efficient resource allocation for device-to-device underlay communication[J].IEEE Transactions on Wireless Communications14.4.2015:2082-2092.

[22]HASAN M,HOSSAIN E.Distributed resource allocation in D2D-enabled multi-tier cellular networks:an auction approach[C]// 2015 IEEE International Conference on Communications (ICC).IEEE,2015.

[23]ZHANG H,JIANG H,LI B,et al.A framework for truthful online auctions in cloud computing with heterogeneous user demands[J].IEEE Transactions on Computers,2016,65(3):805-818.

[24]GUPTA M,REES J,CHATURVEDI A,et al.Matching information security vulnerabilities to organizational security profiles:a genetic algorithm approach[J].Decision Support Systems,2006,41(3):592-603.

[25]VIDUTO V,MAPLE C,HUANG W,et al.A novel risk assessment and optimization model for a multi-objective network security countermeasure selection problem[J].Decision Support Systems,2012,53(3):599-610.

[26]REES L P,DEANE J K,RAKES T R,et al.Decision support for cyber security risk planning[J].Decision Support Systems,2011,51(3):493-505.

[27]SAWIK T.Selection of optimal countermeasure portfolio in IT security planning[J].Decision Support Systems,2013,55(1):156-164.

[28]MUKHOPADHYAY A,CHATTERJEE S,SAHA D,et al.Cyber-risk decision models:to insure IT or not?[J].Decision Support Systems,2013,56:11-26.

[29]GORDON L A,LOEB M P.The economics of information security investment[M]//Economics of Information Security.Springer US,2004:105-125.

[30]LéTOCART L,PLATEAU M C,PLATEAU G.An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem[J].Pesquisa Operacional,2014,34(1):49-72.

[31]SHENG H,SUN J,SUN X.A Rigorous method for solving 0-1 polynomial knapsack problem [J].Journal of Shanghai University (Natural Science Edition),2006,4:012.

[32]BRETTHAUER K M,SHETTY B.Quadratic resource allocation with generalized upper bounds[J].Operations Research Letters,1997,20(2):51-57.

[33]HAHN P,GRANT T.Lower bounds for the quadratic assignment problem based upon a dual formulation[J].Operations Research,1998,46(6):912-922.

[34]HAHN P M,KIM B J,GUIGNARD M,et al.An algorithm for the generalized quadratic assignment problem[J].Computational Optimization and Applications,2008,40(3):351-372.

[35]BILLIONNET A,ELLOUMI S,PLATEAU M C.Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation:the QCR method[J].Discrete Applied Mathematics,2009,157(6):1185-1197.

[36]CAPRARA A,PISINGER D,TOTH P.Exact solution of the quadratic knapsack problem[J].Informs Journal on Computing,1999,11(2):125-137.

[37]ANDERSON R H,FELDMAN P M,GERWEHR S,et al.Securing the US defense information infrastructure:a proposed approach[R].Rand Corp Santa Monica CA,1999.

[38]KELLERER H,PFERSCHY U,PISINGER D.Introduction to NP-completeness of knapsack problems[M].Springer Berlin Heidelberg,2004.

[39]BRETTHAUER K M,SHETTY B.The nonlinear knapsack problem–algorithms and applications[J].European Journal of Operational Research,2002,138(3):459-472.

孫巖煒（1989-），男，山西太原人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全。

郭云川（1977-），男，四川營(yíng)山人，博士，中國(guó)科學(xué)院信息工程研究所副研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息系統(tǒng)安全、訪問(wèn)控制。

張玲翠（1986-），女，河北故城人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、信息保護(hù)。

方濱興（1960-），男，江西萬(wàn)年人，中國(guó)工程院院士，東莞電子科技大學(xué)教授，主要研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)與信息安全。

Resource allocation algorithm for situation awareness based on multiple-choice quadratic knapsack

SUN Yan-wei1,GUO Yun-chuan1,ZHANG Ling-cui1,FANG Bin-xing2
(1.State Key Laboratory of Information Security,Institute of Information Engineering,CAS,Beijing 100093,China;2.Institute of Electronic and Information Engineering,University of Electronic Science and Technology of China in Dongguan,Dongguan 523808,China)

In order to deal with the potential cyber-threat and improve the security situation by using limited resource properly,the optimal allocation of resource focused on cyber security situation.The coherence of network situation lead to the fact that the enhancement of certain item may also affect some other items,and different amount of investment may also result in different degree of impact,therefore,the problem was extracted into the multiple-choice quadratic knapsack problem.The characteristics of quadratic knapsack problem was used to model the interactions among the situation indicator items,meanwhile used the multiple choice knapsack problem to model the multiple investment choice for each item.A branch and bound algorithm was conducted by using the semi-definite relaxation.The experiment results show the accuracy and efficiency of proposed algorithm.

resource allocation,situation awareness,multiple-choice quadratic knapsack,semi-definite relaxation

s:Strategic Priority Research Program of Chinese Academy of Sciences(No.XDA06030200),The National Key Research and Development Program of China (No.2016YFB0800303,No.2016YFB0800700),Core Electronic Devices,High-end General Purpose Chips and Basic Software Products (No.2015ZX01029101),The Industry-University-Research Cooperation Project of Guangdong Province (No.2016B090921001)

TP301

A

10.11959/j.issn.1000-436x.2016272

2016-08-11；

2016-11-01

郭云川，guoyunchuan@iie.ac.cn

中國(guó)科學(xué)院戰(zhàn)略先導(dǎo)專項(xiàng)基金資助項(xiàng)目（No.XDA06030200）；國(guó)家重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目（No.2016YFB0800303,No.2016YFB0800700）；核高基基金資助項(xiàng)目（No.2015ZX01029101）；廣東省產(chǎn)學(xué)研合作基金資助項(xiàng)目（No.2016B090921001）