泛集群環(huán)境下成員穩(wěn)定性計(jì)算方法研究

劉瑞超

摘要：泛集群現(xiàn)在已經(jīng)被廣泛應(yīng)用到工業(yè)生產(chǎn)的各個(gè)領(lǐng)域。但是由于泛集群自身的不穩(wěn)定性，導(dǎo)致很多基于聯(lián)盟結(jié)構(gòu)形成的資源調(diào)度算法失效。針對(duì)這一問題，該文提出了一種從成員自私性角度出發(fā)的穩(wěn)定性計(jì)算方法。首先，建立泛集群場(chǎng)景，歸納了核心問題及聯(lián)盟結(jié)構(gòu)的數(shù)學(xué)模型;其次，給出一種計(jì)算“相對(duì)滿意解”的計(jì)算方法，并以此為依據(jù)給出穩(wěn)定性計(jì)算方法。

關(guān)鍵詞：泛集群;聯(lián)盟結(jié)構(gòu);資源調(diào)度;穩(wěn)定性計(jì)算

中圖分類號(hào)：TP273 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3044（2019）30-0226-02

1背景

在多智能體系統(tǒng)中，大規(guī)?？茖W(xué)計(jì)算問題通常會(huì)以形成聯(lián)盟的方式予以解決。有關(guān)聯(lián)盟形成的研究一直是多智能體系統(tǒng)（Multi-agent Systems，MASs）的關(guān)鍵問題，并已廣泛應(yīng)用于車輛路由、地質(zhì)分析、無人機(jī)群和多媒體安全等領(lǐng)域。

隨著普適計(jì)算模式的不斷發(fā)展，泛集群環(huán)境得到了廣泛應(yīng)用。因此，解決在泛集群環(huán)境下的聯(lián)盟形成問題逐漸成為適應(yīng)新型計(jì)算模式的迫切需要。泛集群是普適計(jì)算模式的載體，是由眾多獨(dú)立的、廉價(jià)的計(jì)算節(jié)點(diǎn)通過網(wǎng)絡(luò)構(gòu)成的開放式計(jì)算環(huán)境，計(jì)算節(jié)點(diǎn)可能是個(gè)人電腦、工作站或手機(jī)等計(jì)算單元，也可能是由多個(gè)計(jì)算單元組成的松散的“計(jì)算群體”，目的是提供高性價(jià)比的計(jì)算能力嘲。計(jì)算節(jié)點(diǎn)具有獨(dú)立性和不穩(wěn)定性，相當(dāng)于具有自主意識(shí)的自由的智能體。換言之，計(jì)算節(jié)點(diǎn)可以通過自身思考決定是否聽從調(diào)度和安排，表現(xiàn)出MASs成員的自私性，突出成員的個(gè)體理性。因此在泛集群環(huán)境下的聯(lián)盟形成的研究不僅要滿足“合作團(tuán)隊(duì)”的高效性，同時(shí)要滿足團(tuán)隊(duì)內(nèi)部的穩(wěn)定性。而其中如何定量的計(jì)算穩(wěn)定性，則是一直難以解決的問題之一，也是智能體自主意識(shí)研究領(lǐng)域的熱點(diǎn)。

2問題的數(shù)學(xué)模型

通常解決多任務(wù)多目標(biāo)約束的調(diào)度和效用分配問題的方法可歸納為如下描述。

方法1.聯(lián)盟結(jié)構(gòu)最優(yōu)法。根據(jù)多目標(biāo)約束的期望函數(shù)，采用最優(yōu)解算法獲得期望函數(shù)極值時(shí)的Mhest并直接獲得對(duì)應(yīng)Xbext。在封閉的計(jì)算環(huán)境下這種方法是可行的，因?yàn)槌蓡T的“自私性”并不凸顯。而在泛集群環(huán)境下，成員的主觀不穩(wěn)定性會(huì)導(dǎo)致方法無效。

方法2.分配向量最優(yōu)法。根據(jù)核覆蓋、邊界向量和web-bet集等概念，采用合作博弈算法獲得最穩(wěn)定的分配向量Xbest，并進(jìn)一步求解獲得Mbest。這是一種反向求解的方法，它保持了分配方案的穩(wěn)定性，適用于泛集群環(huán)境，避免了泛集群成員的“背叛意圖”，但存在以下問題：

（1）如何體現(xiàn)所有成員的整體滿意度。

（2）如何體現(xiàn)成員根據(jù)所有“可能的選擇”而對(duì)“當(dāng)前的選擇”做量化計(jì)算。

3成員穩(wěn)定性性的計(jì)算方法

3.1聯(lián)盟結(jié)構(gòu)模型和編碼規(guī)則