分布式環(huán)境中基于市場(chǎng)機(jī)制的資源自適應(yīng)調(diào)價(jià)策略

丁長(zhǎng)松，王志英，胡志剛

?

分布式環(huán)境中基于市場(chǎng)機(jī)制的資源自適應(yīng)調(diào)價(jià)策略

丁長(zhǎng)松1,2，王志英1，胡志剛3

（1. 國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院，湖南長(zhǎng)沙 410073； 2．湖南中醫(yī)藥大學(xué)管理與信息工程學(xué)院，湖南長(zhǎng)沙 410208；3．中南大學(xué)軟件學(xué)院，湖南長(zhǎng)沙 410083）

針對(duì)分布式環(huán)境中資源定價(jià)面臨的資源使用率、價(jià)格、收益三者之間的沖突問(wèn)題，提出一種基于市場(chǎng)機(jī)制的資源自適應(yīng)調(diào)價(jià)策略。該策略在保障資源提供者收益前提下，通過(guò)資源價(jià)格自適應(yīng)動(dòng)態(tài)調(diào)整來(lái)平衡資源節(jié)點(diǎn)上的任務(wù)分配與資源提供者收益之間的沖突。理論分析證明了調(diào)價(jià)策略的有效性，并在此基礎(chǔ)上設(shè)計(jì)了自適應(yīng)調(diào)價(jià)算法。仿真實(shí)驗(yàn)采用真實(shí)分布式系統(tǒng)中資源節(jié)點(diǎn)信息作為實(shí)驗(yàn)節(jié)點(diǎn)的性能參數(shù)，在大規(guī)模網(wǎng)格任務(wù)中檢驗(yàn)了自適應(yīng)調(diào)價(jià)策略的性能表現(xiàn)。實(shí)驗(yàn)結(jié)果表明，基于市場(chǎng)機(jī)制的“自適應(yīng)調(diào)價(jià)策略”在保障資源收益、均衡資源利用率的性能表現(xiàn)方面顯著優(yōu)于傳統(tǒng)的定價(jià)策略。

分布式計(jì)算；市場(chǎng)機(jī)制；自適應(yīng)；調(diào)價(jià)策略

1 引言

網(wǎng)格計(jì)算[1]和云計(jì)算[2]等網(wǎng)絡(luò)計(jì)算平臺(tái)通過(guò)整合資源提供強(qiáng)大的計(jì)算能力，為實(shí)時(shí)計(jì)算、可視化遠(yuǎn)程醫(yī)療、電子商務(wù)等領(lǐng)域中復(fù)雜的大型任務(wù)提供服務(wù)，并在服務(wù)過(guò)程中保障“非凡的服務(wù)質(zhì)量”[3]。相關(guān)研究[4~6]顯示，利用經(jīng)濟(jì)模型管理資源在促進(jìn)資源公平分配、激勵(lì)資源所有者和資源使用者參與交易、資源分配與資源供需變化的自適應(yīng)等方面都有很好的表現(xiàn)。然而，作為市場(chǎng)機(jī)制中的核心問(wèn)題之一，資源定價(jià)問(wèn)題一直難以得到有效解決，其復(fù)雜性主要體現(xiàn)在以下2個(gè)方面：1）資源提供給其他用戶使用的時(shí)間段內(nèi)，到達(dá)的本地任務(wù)QoS指標(biāo)，如等待時(shí)間、資源利用率等均受到不同程度的影響，網(wǎng)絡(luò)環(huán)境下資源的動(dòng)態(tài)性增加了量化這種負(fù)面影響的難度；2）市場(chǎng)經(jīng)濟(jì)環(huán)境中收益、價(jià)格以及資源分配三者之間關(guān)系的復(fù)雜性，加大了利用價(jià)格平衡資源提供者收益的難度。因此，如何通過(guò)合理的定價(jià)機(jī)制來(lái)保障資源提供者本地任務(wù)的QoS且使資源提供者獲得合理收益，是一個(gè)亟待解決的問(wèn)題。

本文從資源性能的真實(shí)統(tǒng)計(jì)特性出發(fā)，將市場(chǎng)經(jīng)濟(jì)中價(jià)格對(duì)資源使用者的影響作為價(jià)格調(diào)整的基礎(chǔ)，引入成本價(jià)格彌補(bǔ)出讓資源使用權(quán)帶來(lái)的不利影響、利潤(rùn)價(jià)格增加額外收益，通過(guò)價(jià)格的自適應(yīng)調(diào)整保障資源提供者得到合理的資源分配，并促使各資源節(jié)點(diǎn)的負(fù)載大體平衡。

2 相關(guān)工作

借用經(jīng)濟(jì)學(xué)理論分析市場(chǎng)交易中各參與方的行為、交易收益的方法已被廣泛應(yīng)用于計(jì)算機(jī)資源管理中，且其有效性已在諸多基于經(jīng)濟(jì)學(xué)理論的實(shí)際資源管理系統(tǒng)中得到驗(yàn)證。如為解決聯(lián)網(wǎng)異構(gòu)計(jì)算機(jī)的調(diào)度問(wèn)題，Waldspurger等[7]設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)面向市場(chǎng)調(diào)度的Spawn系統(tǒng)。該系統(tǒng)采用Vickrey拍賣機(jī)制，用戶根據(jù)各自偏好，如成本最低、響應(yīng)時(shí)間最小等指標(biāo)，制定相應(yīng)競(jìng)標(biāo)策略。針對(duì)網(wǎng)絡(luò)中多用戶的帶寬分配問(wèn)題，文獻(xiàn)[8]采用效用函數(shù)衡量網(wǎng)絡(luò)用戶的滿意度，提出了基于網(wǎng)絡(luò)聚合效用最大化的網(wǎng)絡(luò)跨層映射模型，該模型求解出的最優(yōu)帶寬分配與各用戶的支付費(fèi)用情況相關(guān)。近年來(lái)出現(xiàn)的云計(jì)算模式由于其提出就考慮商業(yè)實(shí)現(xiàn)，因而經(jīng)濟(jì)學(xué)理論往往應(yīng)用于資源分配中，如針對(duì)云虛擬機(jī)資源的分配問(wèn)題，文獻(xiàn)[9]提出了以云效用最大為資源調(diào)度目標(biāo)的云虛擬機(jī)資源分配模型。

資源定價(jià)作為經(jīng)濟(jì)模型中資源交易各參與方關(guān)注重點(diǎn)，其策略直接影響到資源管理的效果。資源定價(jià)主要分為集中式和分布式2種策略。前者根據(jù)資源市場(chǎng)的總體供需情況對(duì)資源價(jià)格進(jìn)行同步調(diào)節(jié)，如商業(yè)分配方式[10]；后者則根據(jù)資源供需情況進(jìn)行單獨(dú)調(diào)價(jià)，整體資源的均衡價(jià)格通過(guò)對(duì)每個(gè)資源重復(fù)調(diào)價(jià)獲得。集中式定價(jià)算法收斂速度快，但價(jià)格相對(duì)固定，難以適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境，且算法復(fù)雜度相對(duì)較高。分布式定價(jià)在進(jìn)行價(jià)格調(diào)節(jié)時(shí)沒(méi)有考慮各個(gè)資源價(jià)格之間的相關(guān)性，因而不適應(yīng)資源價(jià)格關(guān)聯(lián)性較強(qiáng)的情況[11]，但算法復(fù)雜度相對(duì)較低。針對(duì)市場(chǎng)機(jī)制下網(wǎng)格資源調(diào)價(jià)動(dòng)態(tài)變化快，資源價(jià)格的調(diào)整節(jié)奏與網(wǎng)格環(huán)境中資源供需關(guān)系變化難以保持相對(duì)一致的情況，文獻(xiàn)[11]結(jié)合集中式調(diào)價(jià)算法收斂快速的優(yōu)點(diǎn)，對(duì)分布式調(diào)價(jià)WALRAS算法[12]進(jìn)行了改進(jìn)，提了分布式分組調(diào)價(jià)算法。文獻(xiàn)[13]針對(duì)異構(gòu)無(wú)線網(wǎng)絡(luò)資源管理問(wèn)題，提出了基于Stackelberg博弈模型的分布式定價(jià)和資源分配算法。

相關(guān)研究顯示[14~16]，分布式環(huán)境中資源所有者出讓資源使用權(quán)后，將導(dǎo)致本地任務(wù)的性能指標(biāo)如任務(wù)反應(yīng)時(shí)間、任務(wù)平均等待時(shí)間增加等問(wèn)題。為了弱化其給本地任務(wù)帶來(lái)的負(fù)面影響，文獻(xiàn)[17]根據(jù)本地任務(wù)的統(tǒng)計(jì)特性制定定價(jià)策略，通過(guò)價(jià)格來(lái)保障資源提供者利益。針對(duì)網(wǎng)格計(jì)算中多QoS約束的作業(yè)調(diào)度NP難問(wèn)題，文獻(xiàn)[18]將該問(wèn)題歸約為多目標(biāo)組合最優(yōu)化問(wèn)題，并提出了相應(yīng)的多目標(biāo)演化算法以保障網(wǎng)格用戶的效用。針對(duì)分布式資源管理中用戶的信任QoS與服務(wù)調(diào)度難以融合的問(wèn)題，文獻(xiàn)[19]通過(guò)效用函數(shù)量化服務(wù)提供者與服務(wù)請(qǐng)求者間信任關(guān)系，并在此基礎(chǔ)上提出了保證多QoS的服務(wù)調(diào)度算法。

本文借鑒了分布式定價(jià)策略中“根據(jù)資源供需情況單獨(dú)調(diào)價(jià)以達(dá)供需平衡”的思想，但與傳統(tǒng)的分布式資源定價(jià)機(jī)制沒(méi)有考慮資源間的相關(guān)性不同，本文將資源間的相關(guān)性體現(xiàn)在任務(wù)分配的博弈之中，通過(guò)市場(chǎng)交易中心根據(jù)資源所有者的報(bào)價(jià)與市場(chǎng)整體情況確定資源分配方案，資源所有者通過(guò)價(jià)格調(diào)整使分配方案與整個(gè)市場(chǎng)的供需關(guān)系保持一致。

3 問(wèn)題描述

多資源協(xié)同服務(wù)的交易系統(tǒng)由資源用戶、交易中心、資源代理和資源提供方4個(gè)主要實(shí)體組成。其中，資源提供方由資源集群組成，作為生產(chǎn)者提供資源。本文僅考慮在某時(shí)間段已被使用的資源在該時(shí)間段不能再被其他用戶使用的獨(dú)占型、消耗型資源，如CPU計(jì)算能力、存儲(chǔ)能力等，并由資源代理對(duì)價(jià)格進(jìn)行決策；資源用戶作為消費(fèi)者使用資源提供方的服務(wù)，根據(jù)使用服務(wù)的情況支付相應(yīng)的費(fèi)用；資源分配由交易中心決定，整個(gè)資源交易在交易中心的監(jiān)管下進(jìn)行；資源代理根據(jù)資源提供方的歷史統(tǒng)計(jì)情況與市場(chǎng)交易情況對(duì)資源的利潤(rùn)價(jià)格進(jìn)行自動(dòng)調(diào)節(jié)。

資源提供方和資源用戶通過(guò)市場(chǎng)交易來(lái)提供和使用資源，雙方追求各自收益最大化?；谝话闶袌?chǎng)經(jīng)濟(jì)學(xué)中理性選擇原理和曼昆經(jīng)濟(jì)學(xué)理論[20]，本文基于以下3點(diǎn)假設(shè)。

1) 資源提供方希望通過(guò)提供相同資源使用權(quán)所獲得的資源利潤(rùn)越大越好。

2) 在使用相同服務(wù)的情況下，資源用戶希望支付費(fèi)用越低越好。

3) 市場(chǎng)希望各交易參與方滿意，各資源提供方的收益大體平衡。

在上述3點(diǎn)假設(shè)的基礎(chǔ)上，設(shè)資源提供方將某時(shí)間段內(nèi)的資源使用權(quán)以單位時(shí)間價(jià)格提供給資源用戶并獲得一定的收益，其收益為

其中，為資源提供方實(shí)際出讓的服務(wù)能力，即資源交易中資源的交易量。根據(jù)前面的假設(shè)可知，在提供相同服務(wù)的前提下，價(jià)格越低的資源提供方由于資源用戶追求低的費(fèi)用，因而其獲得資源交易量越大。在為資源用戶提供資源服務(wù)的時(shí)間段內(nèi)可能增加“資源碎片”或可能導(dǎo)致該時(shí)間段內(nèi)到達(dá)的本地任務(wù)QoS無(wú)法保障等情況，從而給本地任務(wù)造成一定的損失。本文采用經(jīng)濟(jì)學(xué)中成本加成定價(jià)模式[21]，將資源單位價(jià)格表示為單位成本和加成價(jià)格

(2)

其中，單位成本0為提供資源使用權(quán)給資源所有者帶來(lái)負(fù)面影響以及為提供服務(wù)所增加的額外開銷在市場(chǎng)環(huán)境中的貨幣量化，如協(xié)同服務(wù)時(shí)增加的網(wǎng)絡(luò)通信開銷成本也包含其中。0根據(jù)實(shí)際環(huán)境確定，如文獻(xiàn)[17]針對(duì)網(wǎng)格計(jì)算環(huán)境采取了本地任務(wù)的概率分布特性進(jìn)行計(jì)算；Δ為加成部分，根據(jù)“3C+R”定價(jià)原理中成本是定價(jià)下限約束[23]，將Δ>0作為約束條件。由加成定價(jià)模式的定價(jià)經(jīng)驗(yàn)公式可知

(4)

根據(jù)第2點(diǎn)假設(shè)可知，理性的資源用戶在相同服務(wù)的前提下會(huì)選擇與價(jià)格低的資源提供方進(jìn)行交易。因此，在資源用戶的總需求確定的情況下，資源用戶和資源提供方之間發(fā)生的交易量與資源價(jià)格相關(guān)。又由于在實(shí)際的資源交易場(chǎng)景中成本0確定，從式（4）可知資源價(jià)格隨值的變化而變化。綜合上述分析可得，資源的交易量與利潤(rùn)因子相關(guān)。基于此，本文基于資源的交易量與利潤(rùn)因子之間的相關(guān)性，通過(guò)調(diào)節(jié)值促使各節(jié)點(diǎn)負(fù)載趨于均衡。

4 自適應(yīng)調(diào)價(jià)策略

資源交易中參與者根據(jù)歷史情況對(duì)本次交易的結(jié)果做出期望，但由于交易是多方博弈過(guò)程，其實(shí)際結(jié)果與期望存在著差異。針對(duì)該情況，根據(jù)資源代理預(yù)期出讓的服務(wù)能力0與資源提供方實(shí)際出讓的服務(wù)能力之間的差距分為：1）|?0|≤0；2）0<|?0|≤1；3）1<|?0|。其中，0和1分別代表資源代理所能接受和較靠近接受的出讓服務(wù)能力與期望出讓服務(wù)能力之間的最大差值，0同時(shí)也是價(jià)格自適應(yīng)調(diào)整終止參數(shù)。1）和2）分配結(jié)果沒(méi)有達(dá)到資源代理所能接受的范圍，因而需要對(duì)價(jià)格進(jìn)行適當(dāng)調(diào)整以使出讓的服務(wù)能力滿足資源代理的期望，其調(diào)價(jià)流程如圖1所示。

4.1 第1調(diào)價(jià)策略

當(dāng)0<|?0|≤1時(shí)，利潤(rùn)因子值只需進(jìn)行微調(diào)。由于每次調(diào)整為使|?0|趨近于0，因而該調(diào)整可采用摸索過(guò)程（tatonnement）[22]。在調(diào)整過(guò)程中利潤(rùn)因子相近，2次幅度調(diào)整關(guān)系表示為，其中和分別為第次調(diào)價(jià)幅度和價(jià)格調(diào)整速率，為使每次調(diào)整后|-0|更趨近0，令，其中，為常系數(shù)，其值域?yàn)?0, 1)。該摸索過(guò)程如圖2所示，通過(guò)構(gòu)造李亞普諾夫能量函數(shù)的方法可證明該過(guò)程是收斂的。

4.2 第2調(diào)價(jià)策略

當(dāng)1<|?0|時(shí)，利潤(rùn)因子值需調(diào)整的幅度較大，其調(diào)整目標(biāo)依然是使|?0|趨近于0，因而該調(diào)整過(guò)程依然可采用摸索過(guò)程。與第1調(diào)價(jià)策略不同之處在于，為使|?0|能在盡量少的調(diào)整過(guò)程中接近0甚至達(dá)到|?0|≤0的范圍，利潤(rùn)因子相近的2次幅度調(diào)整速率的系數(shù)的取值方法如下

4.3 自適應(yīng)調(diào)價(jià)算法

自適應(yīng)調(diào)價(jià)算法（A3PA, auto-adapted adjustment price algorithm）的偽碼如圖3所示。

輸入：由各資源集群信息組成的隊(duì)列RQ、任務(wù)申請(qǐng)T、資源代理承受閾值k0、k1輸出：價(jià)格方案p=(p1,…, pn)Begin1) 初始化價(jià)格方案（p=null）2) 過(guò)濾掉不滿足任務(wù)申請(qǐng)QoS約束的資源節(jié)點(diǎn)，并對(duì)符合條件的資源節(jié)點(diǎn)的利潤(rùn)因子λi進(jìn)行初始化，計(jì)算成本價(jià)格并將價(jià)格上報(bào)給交易中心，Q=03) while Q=0 do4) 交易中心根據(jù)各資源代理報(bào)價(jià)，結(jié)合市場(chǎng)規(guī)則選擇資源分配方案5) 計(jì)算在各資源代理所能接受的分配方案區(qū)間的任務(wù)QoS表現(xiàn)6) if QoS表現(xiàn)滿足需求約束，then Q=17) end while8) while RQ<>null do9) if 存在資源代理|c?c0|≤k0 then10) 該資源代理出隊(duì)列RQ，并將該代理價(jià)格加入隊(duì)列p=(p1,…, pn)11) else if |c?c0|≤k1 then 12) 執(zhí)行第1調(diào)價(jià)策略else13) 執(zhí)行第2調(diào)價(jià)策略14)endif15) 隊(duì)列RQ中的代理上報(bào)交易中心調(diào)整后的價(jià)格16)end while17) 輸出p=(p1,…, pn)End

A3PA算法首先初始化價(jià)格方案，過(guò)濾不滿足任務(wù)QoS約束的節(jié)點(diǎn)和根據(jù)歷史日志計(jì)算出成本價(jià)格并對(duì)利潤(rùn)因子進(jìn)行初始化（步驟1)和步驟2)），接下來(lái)根據(jù)任務(wù)QoS約束確定資源分配方案（步驟3)~ 步驟7)），然后資源代理隊(duì)列根據(jù)交易中心的分配方案確定是否對(duì)價(jià)格進(jìn)行調(diào)整以及如何調(diào)整（步驟9)~ 步驟13)）。為保證每個(gè)資源代理獲得可接受的分配方案，用<>null作為循環(huán)約束條件（步驟8)~步驟16)）。理想情況為交易中心根據(jù)各資源代理初始化利潤(rùn)因子λ計(jì)算出的分配方案就能滿足各資源代理的期望，在該情況下算法的時(shí)間復(fù)雜度為()。最壞情況為根據(jù)各資源代理初始化利潤(rùn)因子計(jì)算出的資源交易量沒(méi)有資源代理能接受，每個(gè)節(jié)點(diǎn)都需要進(jìn)行調(diào)價(jià)，但是需要調(diào)價(jià)的資源代理數(shù)量與時(shí)間復(fù)雜度無(wú)關(guān)，這是由于在步驟8)~步驟16)中循環(huán)約束條件只要存在資源代理對(duì)資源分配方案不滿意就繼續(xù)調(diào)整價(jià)格，具體的時(shí)間復(fù)雜度與所選的調(diào)整策略承受閾值0相關(guān)，A3PA算法的收斂性由調(diào)價(jià)策略1和調(diào)價(jià)策略2的收斂性保障。

5 實(shí)驗(yàn)結(jié)果與性能評(píng)估

5.1 仿真實(shí)驗(yàn)設(shè)計(jì)

為檢驗(yàn)本文提出的分布式環(huán)境中自適應(yīng)定價(jià)策略（A3PS, auto-adapted adjustment price strategy）的性能表現(xiàn)，基于GridSim搭建了一個(gè)分布式系統(tǒng)。實(shí)驗(yàn)中各站點(diǎn)性能參數(shù)配置采用Grid’5000[23]在2015年4月22日的實(shí)際配置，詳細(xì)信息如表1所示。任務(wù)負(fù)載采用Lublin-Feitelson模型生成?？紤]到任務(wù)由Lublin-Feitelson模型隨機(jī)生成，實(shí)驗(yàn)數(shù)據(jù)采用每次實(shí)驗(yàn)重復(fù)10次后的平均結(jié)果。

表1 模擬網(wǎng)格系統(tǒng)的數(shù)據(jù)信息

模擬實(shí)驗(yàn)將A3PS策略與在資源定價(jià)中廣泛應(yīng)用的招投標(biāo)/合同網(wǎng)模型（TCM, tender/contract-net model）[24]和商品市場(chǎng)模型（CMM, commodity market model）[25]的性能表現(xiàn)進(jìn)行比較。

5.2 性能分析與比較

5.2.1 性能比較

表2 模擬實(shí)驗(yàn)結(jié)果

表2中數(shù)據(jù)顯示，TCM策略的任務(wù)完成時(shí)間最長(zhǎng)，而A3PS策略的任務(wù)完成時(shí)間最短，其原因在于TCM策略中資源價(jià)格由資源所有者指定，其定價(jià)機(jī)制相對(duì)固定，導(dǎo)致資源用戶選擇資源時(shí)具有隨機(jī)性，選擇的資源不一定是最合適的資源。然而，A3PS策略其價(jià)格中成本價(jià)格部分就蘊(yùn)含著本地任務(wù)對(duì)資源的使用情況，而理性的資源使用者都傾向于選擇價(jià)格低的資源，因此其任務(wù)完成時(shí)間最短。TCM模型的最大反映出各資源利用率情況相差很大，這正是由于TCM模型中資源用戶一旦選擇了某個(gè)資源提供方后就不會(huì)考慮其他資源情況的這一缺陷所致，而A3PS策略的最小體現(xiàn)了其有使資源負(fù)載趨向平衡的能力，分析原因還是在于A3PS策略的定價(jià)考慮了成本價(jià)格且利潤(rùn)價(jià)格與市場(chǎng)整體利潤(rùn)平衡時(shí)的資源提供方才停止調(diào)價(jià)，而資源用戶將任務(wù)放在價(jià)格較低的資源節(jié)點(diǎn)上運(yùn)行，價(jià)格低的資源節(jié)點(diǎn)其本地任務(wù)相對(duì)較少，因而起到了平衡資源節(jié)點(diǎn)負(fù)載作用。

表2中數(shù)據(jù)顯示，3種策略的總收益和總利潤(rùn)之間的差距都較大。導(dǎo)致這一現(xiàn)象的原因在于實(shí)驗(yàn)中設(shè)置的費(fèi)用預(yù)算較大，在進(jìn)行任務(wù)分配時(shí)費(fèi)用預(yù)算對(duì)分配策略影響不大。實(shí)驗(yàn)中發(fā)現(xiàn)如果將費(fèi)用預(yù)算減少，3種策略的總收益差距會(huì)減小。造成總利潤(rùn)之間的差距較大的原因是，A3PS策略在成本價(jià)格較低的資源節(jié)點(diǎn)上分配的任務(wù)多，因而其利潤(rùn)相對(duì)高，根據(jù)定價(jià)策略可知，成本價(jià)格與資源節(jié)點(diǎn)原有負(fù)載相關(guān)，即成本價(jià)格低的節(jié)點(diǎn)其負(fù)載較低，通過(guò)A3PS策略把資源用戶的任務(wù)更多地分配到負(fù)載較低的節(jié)點(diǎn)中，這也與A3PS策略值最小相符合。

實(shí)驗(yàn)中發(fā)現(xiàn)，A3PS策略的資源節(jié)點(diǎn)總調(diào)價(jià)次數(shù)明顯高于其他策略，正是由于該策略具有自適應(yīng)調(diào)價(jià)的靈活性，根據(jù)市場(chǎng)供需情況采用自動(dòng)調(diào)價(jià)，使收益符合各自預(yù)期。

5.2.2 參數(shù)分析

上述檢驗(yàn)A3PS策略實(shí)驗(yàn)中，當(dāng)0<|?0|≤1時(shí)，采取第1調(diào)價(jià)策略時(shí)||=0.1；當(dāng)1<|?0|時(shí)，初始=1.2，接納閾值0=0.025。為進(jìn)一步研究不同參數(shù)情況下調(diào)價(jià)策略對(duì)資源節(jié)點(diǎn)以及任務(wù)QoS指標(biāo)的影響，對(duì)策略中參數(shù)采取了不同的取值。表3中1、2分別為0<|?0|≤1時(shí)，||和1<|?0|中的取值。

表3 模擬實(shí)驗(yàn)結(jié)果

綜合上述實(shí)驗(yàn)結(jié)果可以得出：調(diào)價(jià)函數(shù)和接納閾值對(duì)系統(tǒng)的調(diào)節(jié)次數(shù)有很大的影響，接納閾值相同的情況下調(diào)價(jià)函數(shù)的變化對(duì)各資源的總收益與任務(wù)完成時(shí)間沒(méi)有明顯影響，資源的總收益和任務(wù)完成時(shí)間、調(diào)價(jià)次數(shù)與接受閾值相關(guān)，而且接受閾值越小調(diào)價(jià)次數(shù)越多，收益越大，這表示資源提供者對(duì)分配策略的要求比較苛刻，表明資源分配方案與價(jià)格調(diào)整函數(shù)關(guān)系不大，只要資源提供方的接納分配策略范圍|?0|<0確定，其資源分配方案就能確定。

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

如何合理地對(duì)資源定價(jià)是基于市場(chǎng)機(jī)制進(jìn)行資源管理的一個(gè)核心問(wèn)題。本文在保障本地節(jié)點(diǎn)利益并尊重市場(chǎng)規(guī)律的前提下，對(duì)資源提供方出讓的使用權(quán)進(jìn)行價(jià)格確定，在該定價(jià)過(guò)程中資源代理利用市場(chǎng)對(duì)價(jià)格的反應(yīng)，通過(guò)對(duì)價(jià)格進(jìn)行自適應(yīng)調(diào)整，使市場(chǎng)中資源分配方案符合資源代理所設(shè)置的資源分配接納區(qū)間，以此來(lái)保障資源提供方的收益，并建立了資源自適應(yīng)市場(chǎng)變化的定價(jià)策略。對(duì)GridSim進(jìn)行了改進(jìn)與擴(kuò)展，并在此平臺(tái)上對(duì)提出的自適應(yīng)定價(jià)策略進(jìn)行的仿真實(shí)驗(yàn)結(jié)果表明，本文提出的定價(jià)策略不但保障了資源提供方的收益，而且能使各資源節(jié)點(diǎn)的資源負(fù)載趨于平衡。下一步工作將主要集中研究資源提供者不同偏好以及多QoS約束下保障價(jià)格的定價(jià)機(jī)制與價(jià)格調(diào)整函數(shù)的優(yōu)化。

[1] FOSTER I, KESSELMAN C. The grid: blueprint for a new computing infrastructure, second edition [M]. Singapore: Elsevier Inc. 2004.

[2] 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.

[3] FOSTER I. What is the Grid? a three point checklist [J]. GRID Today, 2002, 1(6): 20-27.

[4] BUYYA R. Economic-based distributed resource management and scheduling for grid computing[D]. Monash University, Australia, 2002.

[5] SANDHOLM T. Making markets and democtacy work: a story of incentives and computing[C]//The International Joint Conference on Artificial Intelligence (IJCAI-03), c2003: 1649-1671.

[6] 曹鴻強(qiáng), 肖儂, 盧錫城, 等. 一種基于市場(chǎng)機(jī)制的計(jì)算網(wǎng)格資源分配方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2002, 39(8): 913-916

CAO H Q, XIAO N, LU X C, et al. A market-based approach to allocate resources for computational grids [J]. Journal of Computer Research and Development, 2002, 8(39): 913-916.

[7] WALDSPURGER C, HOGG T, HUBERMAN B, et al. Spawan: a distributed computation economy [J]. IEEE Transactions on Software Engineering, 1992, 18(2): 103-117.

[8] 李世勇, 楊冬, 秦雅娟, 等.基于效用最大化的網(wǎng)絡(luò)跨層映射[J].軟件學(xué)報(bào),2011,22(8):1855-1871.

LI S Y, YANG D, QIN Y J, et al. Network cross-layer mapping based in utility maximization[J]. Journal of Softeware, 2011, 22(8): 1855-1871.

[9] 師雪霖,徐恪.云虛擬機(jī)資源分配的效用最大化模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2013,36(2): 252-262.

SHI X L, XU K. Utility maximiztion model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262.

[10] KENYON C, CHELIOTIS G. Grid resource commercialization: economic engineering and delivery scenarios grid resource management: state of the art and research issues [M]. Kluwer, 2003.

[11] 翁楚良, 陸鑫達(dá). 一種基于市場(chǎng)機(jī)制的網(wǎng)格資源調(diào)價(jià)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(7): 1151-1156.

WENG C L, LU X D. A pricing algorithm for market-based resource management on grid computing systems[J]. Jouranl of Computer Research and Development, 2004, 7(41): 1151-1156.

[12] CHENG J Q, WELLMAN M P. The WALRAS algorithm: a convergent distributed implementation of general equilibrium outcomes [J]. Computational Economics, 1998, 12(1): 1-24.

[13] 姜永, 陳山枝, 胡博. 異構(gòu)無(wú)線網(wǎng)絡(luò)中基于Stackelberg博弈的分布式定價(jià)和資源分配算法[J].通信學(xué)報(bào), 2013, 34(1): 61-68.

JIANG Y, CHEN S Z, HU B. Stackelberg games – based distributed algorithm of pricing and resource allocation in heterogeneous wireless netwotks[J]. Journal on Communications, 2013, 34(1): 61-68.

[14] SMITH W, FOSTER I, TAYLOR V. Scheduling with advanced reservations[C]//14th International Parallel and Distributed Processing Symposium(IPDPS 2000), c2000: 127-132.

[15] CAO J F. Zimmermann. Queue scheduling and advance reservations with COSY[C]//18th International conference on Parallel and Distributed Processing Symposium, c2004: 63a.

[16] HEINE F, HOVESTADT M, KAO O, et al. On the impact of reservations from the Grid on planning-based resource management[C]//International Conference on Computational Science-(ICCS 2005). c2005: 155-162.

[17] 丁長(zhǎng)松, 王志英, 胡志剛. 基于效用驅(qū)動(dòng)的網(wǎng)格資源協(xié)同預(yù)留策略[J]. 通信學(xué)報(bào), 2014, 35(3): 101-107.

DING C S, WANG Z Y, HU Z G. Utility-driven based co-allocation resource reservation strategy in computational grid[J]. Journal on Communications, 2014, 35(3): 101-107.

[18] 張偉哲, 胡銘曾, 張宏莉, 等. 多QoS約束網(wǎng)格作業(yè)調(diào)度問(wèn)題的多目標(biāo)演化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(11): 1855-1862.

ZHANG W Z, HU M Z, ZHANG H L, et al. A multiobjective evolutionary algorithm for grid job scheduling of multi-QoS constraints [J]. Journal of Computer Research and development, 2006, 43(11): 1855-1862.

[19] 張偉哲, 方濱興, 胡銘曾, 等. 基于信任QoS增強(qiáng)的計(jì)算服務(wù)調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(7): 1157-1166.

ZHANG W Z, FANG B X, HU M Z, et al. A trust-QoS enhanced grid service scheduling [J]. Chinese Journal of Computers, 2006, 29(7): 1157-1166.

[20] MANKIW N G. Teaching the principles of economics [J]. Eastern Economic Journal, 1998, 24(4): 519-524.

[21] 駱品亮.定價(jià)策略[M]. 上海:上海財(cái)經(jīng)大學(xué)出版社, 2013. 19-22. LUO P L. Pricing strategy. Shanghai: Shanghai University of Finance and Economics Press, 2013. 19-22.

[22] VARIAN H R. Microeconomic analysis[M]. New York: W.W. Norton & Company, 1992.

[23] MediaWiki. Grid5000: Home[EB/OL]. https://www.grid5000.fr/ mediawiki/index.php/Grid5000:Home.

[24] SMITH R, DAVIS R. The contract net protocol: high level communication and control in a distributed problem solver [J]. IEEE Transactions on Computers, 1980, 29(12): 1104-1113.

[25] MCKNIGHT L W, BOROUMAND J. Pricing internet service: approaches and challenges [J]. IEEE Computer, 2000, 33(2): 128-129.

Self-adaptive price adjustment strategy based on market mechanism in distributed environment

DING Chang-song1,2, WANG Zhi-ying1, HU Zhi-gang3

(1. College of Computer, National University of Defense Technology, Changsha 410073, China; 2. School of Management and Information Engineering, Hunan University of Chinese Medicine, Changsha 410208, China; 3. School of Software, Central South University, Changsha 410083, China)

To solve the resource pricing problem of the collision among resource utilization, price and benefits in distributed computing environments, a self-adaptive pricing strategy of resource services based on market mechanism was proposed. On the premise of the local resource benefits, this adaptive pricing strategy guaranteed the resource to self-adapt the price dynamically so as to balance the collision between the assigned tasks on the resource node and the benefits of the resource provider. The theoretical analysis proved the effectiveness of the pricing strategy, and the algorithm of the pricing strategy was designed. Resources node information in the real distributed systems was used as the performance parameters of experimental node in the simulation experiments, and the performance of the adaptive pricing strategy was tested in a large-scale grid mission. Experimental results show that, compared with the traditional pricing strategies, the adaptive pricing strategy based on market mechanism has vastly superior performance on the resource benefits and the balance of resource utilization.

distributed computing, market mechanism, self-adaptive, price adjustment strategy

TP393

A

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

2015-05-20；

2016-01-05

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.81573985）；湖南省科技廳基金資助項(xiàng)目（No.2011RS4025, No.2013GK3143）；湖南省教育廳優(yōu)秀青年基金資助項(xiàng)目（No.13B079）

The National Natural Science Foundation of China (No.81573985),The Science and Technology Projects Fund of Hunan Province (No.2011RS4025, No.2013GK3143), Scientific Research Fund for Outstanding Young Teachers of Hunan Provincial Education Department (No.13B079)

丁長(zhǎng)松（1975-），男，湖南漢壽人，湖南中醫(yī)藥大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)樵朴?jì)算、中醫(yī)藥信息化。

王志英（1956-），男，山西長(zhǎng)治人，國(guó)防科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)。

胡志剛（1963-），男，山西孝義人，中南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)并行計(jì)算、嵌入式系統(tǒng)、網(wǎng)絡(luò)安全。