• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于螢火蟲(chóng)算法的多租戶SaaS優(yōu)化部署研究*

    2016-07-21 01:27:49胡龍茂王會(huì)穎
    關(guān)鍵詞:優(yōu)化

    胡龍茂,王會(huì)穎

    (安徽財(cái)貿(mào)職業(yè)學(xué)院,安徽 合肥 230601)

    ?

    基于螢火蟲(chóng)算法的多租戶SaaS優(yōu)化部署研究*

    胡龍茂,王會(huì)穎

    (安徽財(cái)貿(mào)職業(yè)學(xué)院,安徽 合肥 230601)

    摘要:軟件即服務(wù)(SaaS)日益成為云計(jì)算環(huán)境下的軟件交付模式,SaaS的部署費(fèi)用也成為SaaS提供商關(guān)注的問(wèn)題.該文首先針對(duì)SaaS環(huán)境下租戶的響應(yīng)時(shí)間性能需求,建立最小化SaaS提供商的虛擬機(jī)費(fèi)用模型,然后將SaaS部署問(wèn)題分解為裝箱問(wèn)題,最后采用物品編碼方式,提出利用具有良好全局尋優(yōu)能力的螢火蟲(chóng)算法求解多租戶SaaS部署的優(yōu)化方案.

    關(guān)鍵詞:SaaS;多租戶;虛擬機(jī)費(fèi)用;螢火蟲(chóng)算法;優(yōu)化

    軟件即服務(wù) (Software as a Service, SaaS)是云計(jì)算在應(yīng)用層提供的服務(wù),在此模式下,客戶無(wú)需購(gòu)買和維護(hù)軟件,而是按需租用服務(wù)提供商的軟件服務(wù),由服務(wù)提供商負(fù)責(zé)軟件的開(kāi)發(fā)、部署、組合、維護(hù).SaaS的典型特征是不同的租戶共享軟件的同一實(shí)例,這些實(shí)例對(duì)租戶而言是透明的,租戶無(wú)需了解服務(wù)部署的位置,也無(wú)需擔(dān)心服務(wù)的質(zhì)量,服務(wù)就像是獨(dú)占的[1].對(duì)于租戶提出的SaaS應(yīng)用請(qǐng)求,SaaS服務(wù)提供商部署一定數(shù)量的應(yīng)用實(shí)例,這些應(yīng)用實(shí)例將安裝在向云基礎(chǔ)設(shè)施提供商租用的虛擬機(jī)上面.從SaaS服務(wù)提供者的成本角度而言,其優(yōu)化目標(biāo)是在滿足每個(gè)租戶服務(wù)級(jí)別協(xié)議(Service Level Agreement,SLA)的條件下,使租用的虛擬機(jī)的總費(fèi)用最低.

    多租戶SaaS環(huán)境下的資源分配是一個(gè)典型的組合優(yōu)化問(wèn)題,適合采用非線性方法進(jìn)行求解.劍橋?qū)W者Yang在2008年提出的螢火蟲(chóng)算法(Firefly Algorith,FA)[2]是一種仿生智能群算法,應(yīng)用于處理函數(shù)優(yōu)化問(wèn)題及組合優(yōu)化問(wèn)題,通過(guò)調(diào)整參數(shù),能獲得比隨機(jī)搜索和粒子群算法更好的性能[3-4],本文研究了螢火蟲(chóng)算法在分配虛擬機(jī)資源中的優(yōu)化部署問(wèn)題.

    1多租戶SaaS模型及數(shù)學(xué)描述

    云平臺(tái)中多租戶SaaS模型主要包括租戶、SaaS提供商和組成云基礎(chǔ)設(shè)施(IaaS)的虛擬機(jī),如圖1所示.租戶是租用Web軟件的客戶.SaaS提供商對(duì)外提供多種SaaS應(yīng)用,當(dāng)一個(gè)或多個(gè)租戶需要租用某種應(yīng)用時(shí),SaaS提供商根據(jù)SLA計(jì)算出需要部署的應(yīng)用的實(shí)例數(shù)目,然后通過(guò)某種策略將這些實(shí)例部署到向云基礎(chǔ)設(shè)施提供商租來(lái)的虛擬機(jī)上.IaaS供應(yīng)的虛擬機(jī)有多種型號(hào),其CPU性能、存儲(chǔ)容量及通道性能均不一樣,其使用費(fèi)用也不一樣,客戶可以根據(jù)自身情況租用合適的虛擬機(jī).

    圖1 多租戶SaaS模型

    設(shè)某SaaS提供商有m個(gè)租戶,提供n種SaaS應(yīng)用.每種應(yīng)用可以部署多個(gè)應(yīng)用實(shí)例,租戶和應(yīng)用實(shí)例之間是多對(duì)多的聯(lián)系.應(yīng)用實(shí)例部署在租來(lái)的p類虛擬機(jī)上,每類虛擬機(jī)包括q種資源,如處理能力、內(nèi)存及I/O性能等.每個(gè)租戶在使用應(yīng)用前要用

    SaaS提供商簽訂SLA,SLA規(guī)定了應(yīng)用實(shí)例所應(yīng)達(dá)到的性能.

    基于費(fèi)用優(yōu)化的多租戶SaaS部署的數(shù)學(xué)模型如下:

    i=1,2,…,q;j=1,2,…,p

    (1)

    其中,在目標(biāo)函數(shù)中,countj表示第j類虛擬機(jī)的數(shù)量,evaluej表示第j類虛擬機(jī)的租用價(jià)格.在約束條件中,consumeijk表示虛擬機(jī)j上部署第第k個(gè)實(shí)例所消耗的i類資源量,在達(dá)到響應(yīng)時(shí)間的性能需求下,consumeijk與并發(fā)用戶數(shù)成線性關(guān)系[5];casej表示在虛擬機(jī)j上部署的實(shí)例數(shù)量;allowij表示虛擬機(jī)j上第i類資源的最大利用率;consumeij表示虛擬機(jī)j上第i類資源的消耗量.

    多租戶SaaS部署問(wèn)題可以看作是將x個(gè)物品裝到y(tǒng)個(gè)箱子的裝箱問(wèn)題,其中,每個(gè)物品代表一個(gè)應(yīng)用實(shí)例及其所對(duì)應(yīng)的租戶,每個(gè)箱子代表一個(gè)虛擬機(jī).因此多租戶SaaS部署問(wèn)題是NP問(wèn)題,時(shí)間復(fù)雜度高,本文采用螢火蟲(chóng)算法來(lái)求解近似最優(yōu)方案.

    2螢火蟲(chóng)算法

    螢火蟲(chóng)算法通過(guò)模擬自然界中螢火蟲(chóng)的群體行為實(shí)現(xiàn)目標(biāo)優(yōu)化.螢火蟲(chóng)的亮度越高,其吸引力也越大,會(huì)吸引亮度較弱的螢火蟲(chóng)向其移動(dòng).隨著距離的增大,螢火蟲(chóng)的亮度和吸引力逐漸減少.螢火蟲(chóng)的亮度由其所處位置的目標(biāo)值而確定,位置越佳,亮度越高.在螢火蟲(chóng)算法中,用螢火蟲(chóng)個(gè)體表示搜索空間的點(diǎn),用目標(biāo)函數(shù)值表示個(gè)體所處位置的好壞,螢火蟲(chóng)個(gè)體的移動(dòng)即較優(yōu)解取代劣解的過(guò)程,通過(guò)個(gè)體位置的不斷變化,最終達(dá)到優(yōu)化結(jié)果.螢火蟲(chóng)算法的定義[2]如下:

    定義1螢火蟲(chóng)的相對(duì)亮度為:

    I=I0e-γrij2

    (2)

    其中,I0為螢火蟲(chóng)的原始亮度,即自身(r=0)亮度,取決于目標(biāo)函數(shù),目標(biāo)函數(shù)所處位置越好則原始亮度越高;γ為光吸收系數(shù),表征了媒介對(duì)光的吸收效果;rij為螢火蟲(chóng)i和j間的距離.

    定義2螢火蟲(chóng)的吸引力:

    β=β0e-γr2

    (3)

    其中,β0是在r=0處的吸引力.

    定義3螢火蟲(chóng)i向更有吸引力的螢火蟲(chóng)j移動(dòng)的位置變化:

    xi=xi+β(xj-xi)+α(rand-1/2)

    (4)

    其中,xi、xj為螢火蟲(chóng)的坐標(biāo);α∈[0,1]為步長(zhǎng)因子;rand為[0,1]區(qū)間均勻分布的隨機(jī)數(shù)發(fā)生器.

    3基于螢火蟲(chóng)算法的多租戶SaaS優(yōu)化部署

    3.1SaaS部署的編碼方式

    設(shè)有租戶集合U={U1,U2,…,Um}、應(yīng)用集合A={A1,A2,…,An}及租約關(guān)系集合UA?U×A,SaaS部署的編碼如下:

    (1)將每一個(gè)租約關(guān)系(Ui,Aj)∈UA映射為一個(gè)租戶-應(yīng)用實(shí)例關(guān)系.如{(U1,A1),(U2,A1)}生成{(U1,C1),(U2,C2)},其中C1和C2都是A2的實(shí)例.

    (2)裝箱編碼方式.將步驟(1)中生成的應(yīng)用實(shí)例看成是物品,采用基于物品的編碼進(jìn)行裝箱,如編碼x={2,5,1,4,3}表示先裝2號(hào)物品,然后再裝5號(hào)物品,以此類推,最后裝3號(hào)物品.

    (3)裝箱策略.常用的裝箱策略有下次適應(yīng)算法、首次適應(yīng)算法和最佳適應(yīng)算法等.本文采用首次適應(yīng)算法.將當(dāng)前物品裝箱時(shí),查找非空箱子,當(dāng)找到一個(gè)非空箱能裝下當(dāng)前物品時(shí),則將其裝箱;如未找到這樣的非空箱,則開(kāi)啟新的箱子.

    (4)不同編碼的距離計(jì)算.編碼xi和xj的第k個(gè)分量的距離定義如下:

    (5)

    那么編碼xi和xj之間的距離

    (6)

    在裝箱過(guò)程中,如果屬于同一個(gè)應(yīng)用的多個(gè)實(shí)例被安裝到同一臺(tái)虛擬機(jī)上,則這多個(gè)實(shí)例被合并成一個(gè)實(shí)例,與此同時(shí),租戶-應(yīng)用實(shí)例關(guān)系也被合并.

    3.2算法流程

    求解多租戶SaaS優(yōu)化部署的螢火蟲(chóng)算法流程如下.

    步驟1初始化基本參數(shù).包括螢火蟲(chóng)數(shù)目n,光吸收系數(shù)γ,最大吸引力β0,步長(zhǎng)因子α,最大迭代次數(shù)maxT.

    步驟2初始化螢火蟲(chóng)的位置.對(duì)于SaaS部署問(wèn)題,將所有的應(yīng)用實(shí)例進(jìn)行排序編碼,一個(gè)螢火蟲(chóng)表示一種編碼方式,將螢火蟲(chóng)隨機(jī)放置在解空間中.

    步驟3按照式(1)計(jì)算螢火蟲(chóng)的目標(biāo)函數(shù)值作為原始亮度,按照式(2)(3)計(jì)算螢火蟲(chóng)的相對(duì)亮度和吸引力(螢火蟲(chóng)之間的距離按式(6)進(jìn)行計(jì)算),根據(jù)相對(duì)亮度決定螢火蟲(chóng)的移動(dòng)方向.

    步驟4按照式(4)更新螢火蟲(chóng)的位置,由于物品編碼順序都是整數(shù)值,故需將更新后的位置四舍五入成整數(shù)值.

    步驟5當(dāng)滿足結(jié)束條件時(shí),跳轉(zhuǎn)步驟6輸出結(jié)果;否則,轉(zhuǎn)步驟3.

    步驟6輸出最優(yōu)目標(biāo)值,并按照3.1節(jié)輸出最優(yōu)部署方案.

    4結(jié)語(yǔ)

    螢火蟲(chóng)算法利用個(gè)體趨向最亮的螢火蟲(chóng)來(lái)實(shí)現(xiàn)目標(biāo)尋優(yōu),適用于函數(shù)優(yōu)化和組合優(yōu)化問(wèn)題.本文通過(guò)將租戶和SaaS應(yīng)用的簽訂的租約關(guān)系進(jìn)行分解,使得SaaS部署問(wèn)題成為一個(gè)裝箱問(wèn)題,采用基于物品的編碼方式,利用螢火蟲(chóng)算法求解最優(yōu)目標(biāo)值和最優(yōu)解.對(duì)于多租戶SaaS優(yōu)化部署問(wèn)題,以往多采用遺傳算法、蟻群算法[5-6]等進(jìn)行求解,本文的解決方案提供了另一條多租戶SaaS優(yōu)化部署的可行途徑.

    參考文獻(xiàn):

    [1]Shi Y L,Luan S,Li Q Z,et al.TLA Based Customization and Verification Mechanism of Business Process for SaaS[J].Chinese Journal of Computers,2010,33(11):2055-2067(in Chinese)(史玉良,欒帥,李慶忠,等.基于TLA的SaaS業(yè)務(wù)流程定制及驗(yàn)證機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),2010,33(11):2055-2067.

    [2]Yang X S.Nature-inspired metaheuristic algorithm [M].[S.l]:Luniver Press,2008:83-96.

    [3]Yang X S.Firefly algorithms for multimodal optimization[C].Lectrue Notes in Computer Science,2009,5792:169-178.

    [4]Yang X S,DEB S.Eagle strategy using levy walk and firefly algorithms for stochastic optimization[J].Studies in Computational Intelligence,2010,284:101-111.

    [5]孟凡超,周學(xué)權(quán),曹祖鳳,初佃輝,戰(zhàn)德臣.基于成本優(yōu)化的多租戶SaaS應(yīng)用優(yōu)化放置算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014(06):1508-1518.

    [6]王會(huì)穎,倪志偉,伍章俊,等.基于MapReduce和多目標(biāo)蟻群算法的多租戶服務(wù)定制算法[J].模式識(shí)別與人工智能,2014,(12):1105-1116.

    (責(zé)任編輯:王前)

    DOI:10.13877/j.cnki.cn22-1284.2016.06.003

    *收稿日期:2016-01-24

    基金項(xiàng)目:安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目“基于MapReduce的螢火蟲(chóng)算法及其在多租戶SaaS優(yōu)化部署中的研究與應(yīng)用”(KJ2016A009)

    作者簡(jiǎn)介:胡龍茂,男,安徽太湖人,講師.

    中圖分類號(hào):TP301.6

    文獻(xiàn)標(biāo)志碼:A

    文章編號(hào):1008-7974(2016)03-0007-03

    猜你喜歡
    優(yōu)化
    超限高層建筑結(jié)構(gòu)設(shè)計(jì)與優(yōu)化思考
    PEMFC流道的多目標(biāo)優(yōu)化
    能源工程(2022年1期)2022-03-29 01:06:28
    民用建筑防煙排煙設(shè)計(jì)優(yōu)化探討
    關(guān)于優(yōu)化消防安全告知承諾的一些思考
    一道優(yōu)化題的幾何解法
    由“形”啟“數(shù)”優(yōu)化運(yùn)算——以2021年解析幾何高考題為例
    圍繞“地、業(yè)、人”優(yōu)化產(chǎn)業(yè)扶貧
    事業(yè)單位中固定資產(chǎn)會(huì)計(jì)處理的優(yōu)化
    4K HDR性能大幅度優(yōu)化 JVC DLA-X8 18 BC
    幾種常見(jiàn)的負(fù)載均衡算法的優(yōu)化
    電子制作(2017年20期)2017-04-26 06:57:45
    贺兰县| 杭锦旗| 延长县| 扎兰屯市| 溧水县| 自治县| 新密市| 西藏| 清流县| 嘉鱼县| 浮山县| 平湖市| 宣城市| 民县| 仁寿县| 昌宁县| 新巴尔虎右旗| 三门峡市| 三原县| 宜宾市| 无锡市| 成安县| 永昌县| 仁寿县| 武清区| 白朗县| 揭西县| 仪陇县| 自贡市| 潢川县| 闽清县| 元氏县| 师宗县| 登封市| 大邑县| 黄龙县| 桐庐县| 仲巴县| 高唐县| 霸州市| 舞阳县|