基于排隊(duì)論的Web服務(wù)社區(qū)最優(yōu)服務(wù)數(shù)設(shè)置*

何晨翔， 付曉東， 劉 驪， 劉利軍， 黃青松

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

?

基于排隊(duì)論的Web服務(wù)社區(qū)最優(yōu)服務(wù)數(shù)設(shè)置*

何晨翔， 付曉東， 劉 驪， 劉利軍， 黃青松

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650500)

Web服務(wù)社區(qū)是將功能類似的Web服務(wù)集中到一起為用戶提供服務(wù)，當(dāng)大量用戶同時(shí)訪問(wèn)社區(qū)時(shí)，會(huì)出現(xiàn)排隊(duì)現(xiàn)象。用戶在社區(qū)中排隊(duì)時(shí)會(huì)占用一部分資源，從而會(huì)產(chǎn)生一部分額外的成本。為此研究了如何設(shè)置最優(yōu)的服務(wù)數(shù)使得這部分的額外成本最小。給出Web服務(wù)社區(qū)的定義，將在服務(wù)社區(qū)中排隊(duì)的問(wèn)題映射成排隊(duì)論問(wèn)題，確定排隊(duì)模型為M/M/n。計(jì)算在穩(wěn)定狀態(tài)時(shí)用戶的排隊(duì)長(zhǎng)度，得出在社區(qū)中排隊(duì)的用戶數(shù)量。結(jié)合Web服務(wù)社區(qū)中的成本因素確定成本函數(shù)，結(jié)合經(jīng)濟(jì)學(xué)中的邊際分析法求出最佳的服務(wù)數(shù)。實(shí)驗(yàn)表明：該方法可以有效地找出最優(yōu)的服務(wù)數(shù)，且效率較高。

Web服務(wù)； Web服務(wù)社區(qū)； 排隊(duì)論； 邊際分析法

0 引 言

近年來(lái)，隨著互聯(lián)網(wǎng)上Web服務(wù)的數(shù)量的不斷增長(zhǎng)，面向服務(wù)計(jì)算SOC(service oriented computing)成為主流的計(jì)算范型。Web服務(wù)是一種嶄新的、模塊化、自描述的分布式計(jì)算模型，采用可擴(kuò)展標(biāo)記語(yǔ)言(XML)定義了Web 服務(wù)協(xié)議棧， 通過(guò)SOAP(simple object access protocol)、UDDI(universal description，discovery ,and integration) 、BPEL4WS(business process execution language for Web integration)和WSFL(Web services flow language)等協(xié)議，提供面向互聯(lián)網(wǎng)應(yīng)用的統(tǒng)一服務(wù)綁定、發(fā)現(xiàn)、及注冊(cè)集成調(diào)用機(jī)制[1]。

隨著Web服務(wù)的數(shù)量不斷增加，有學(xué)者就提出了Web服務(wù)社區(qū)的概念，文獻(xiàn)[2]指出Web服務(wù)社區(qū)是由大量的Web服務(wù)組合成的，其中，Web服務(wù)功能相似且具有不同的非功能的特性。例如，來(lái)自不同的提供者或QoS不同。由于在一個(gè)Web服務(wù)社區(qū)中的服務(wù)具有相同領(lǐng)域興趣，因此，在領(lǐng)域QoS評(píng)價(jià)上有最多的共同點(diǎn)，例如，有天氣查詢功能的服務(wù)共同組成天氣查詢服務(wù)社區(qū)。Web服務(wù)社區(qū)是動(dòng)態(tài)生成的，通過(guò)特定場(chǎng)景和協(xié)議建立和拆除，集結(jié)方式和P2P網(wǎng)絡(luò)類似[3]。所有的領(lǐng)域?qū)?yīng)的社區(qū)中都有一個(gè)主Web服務(wù)，它儲(chǔ)存該服務(wù)社區(qū)中所有Web服務(wù)的相關(guān)信息，并擁有優(yōu)于社區(qū)其他Web服務(wù)的各種參數(shù)。主Web服務(wù)基于語(yǔ)義聚集有相同原子功能的從Web服務(wù)。生成方式是雙向的，主服務(wù)定期到UDDI查詢是否有符合社區(qū)要求的節(jié)點(diǎn)，或由新節(jié)點(diǎn)向主服務(wù)提出加入請(qǐng)求，主服務(wù)認(rèn)證后加入[4～6]。

Web服務(wù)社區(qū)的概念提出后，文獻(xiàn)[7,8]提出了功能相似的Web服務(wù)被分組后如何更容易的在互聯(lián)網(wǎng)上被發(fā)現(xiàn)的問(wèn)題。然而這些研究同樣沒(méi)有研究當(dāng)Web服務(wù)社區(qū)中有大量的服務(wù)的情況下。文獻(xiàn)[9]中作者提出了在社區(qū)中如何有效的定位Web服務(wù)。作者提出在不同的環(huán)境下對(duì)服務(wù)的描述不同于語(yǔ)義層的意思，所以傳統(tǒng)的按照關(guān)鍵字去搜索是在Web服務(wù)的一個(gè)很小的范圍。然而該研究沒(méi)有考慮到當(dāng)Web服務(wù)社區(qū)中的服務(wù)數(shù)越來(lái)越多的情況。當(dāng)社區(qū)中服務(wù)或者用戶過(guò)多時(shí)作者提出的這種方法就會(huì)出現(xiàn)一些錯(cuò)誤的結(jié)果。

綜上所述，國(guó)內(nèi)外對(duì)Web服務(wù)社區(qū)進(jìn)行了大量的研究。對(duì)Web服務(wù)社區(qū)的研究多數(shù)是集中在Web服務(wù)的選擇和Web服務(wù)社區(qū)的結(jié)構(gòu)等問(wèn)題上，很少有涉及到Web服務(wù)的社區(qū)的成本問(wèn)題和社區(qū)中Web服務(wù)數(shù)的設(shè)置問(wèn)題。同時(shí)絕大多數(shù)研究沒(méi)有考慮到當(dāng)社區(qū)中有大量的Web服務(wù)和大量用戶訪問(wèn)社區(qū)的情況。本文研究的問(wèn)題首先就是考慮到社區(qū)中有大量的Web服務(wù)而且在一個(gè)時(shí)間段會(huì)有大量用戶訪問(wèn)服務(wù)社區(qū)。在這種情況下會(huì)出現(xiàn)排隊(duì)現(xiàn)象，然后本文結(jié)合了排隊(duì)論和邊際分析法對(duì)Web服務(wù)社區(qū)的運(yùn)行成本進(jìn)行了研究。

1 Web服務(wù)社區(qū)的排隊(duì)模型

1.1 Web服務(wù)社區(qū)

隨著Web服務(wù)的不斷增加，出現(xiàn)了Web服務(wù)的組合形式。文獻(xiàn)[4]給出了Web服務(wù)社區(qū)的相關(guān)概念和操作。這里用圖形表示出Web服務(wù)社區(qū)的體系結(jié)構(gòu)。如圖(1)所示。圖1 包含了2 類服務(wù)：一種是社區(qū)服務(wù)，另一個(gè)是普通Web 服務(wù)。圖1中的社區(qū)也是Web服務(wù)的一種，這類Web服務(wù)規(guī)定了某些功能接口，它自身不去實(shí)現(xiàn)這類功能，其功能由具體的Web 服務(wù)實(shí)現(xiàn)，圖1中虛線箭頭表示服務(wù)的發(fā)布，實(shí)線箭頭表示W(wǎng)eb 服務(wù)實(shí)現(xiàn)的相應(yīng)社區(qū)的功能，類似于面向?qū)ο笾谐惡妥宇惖年P(guān)系。

圖1 Web服務(wù)社區(qū)體系結(jié)構(gòu)Fig 1 Architecture of Web service community

在Web服務(wù)社區(qū)的體系結(jié)構(gòu)下，圖2給出了Web服務(wù)社區(qū)是如何給用戶提供服務(wù)。首先Web服務(wù)實(shí)現(xiàn)社區(qū)的接口然后在社區(qū)中注冊(cè)，然后Web服務(wù)去注冊(cè)中心進(jìn)行注冊(cè)。當(dāng)用戶要調(diào)用Web服務(wù)時(shí)，用戶首先到注冊(cè)中心查找相關(guān)信息，注冊(cè)中心會(huì)給出用戶所需要的Web服務(wù)所在的社區(qū)。用戶直接到對(duì)應(yīng)的社區(qū)中查找自己需要的Web服務(wù)。圖2中也能看出社區(qū)中可能存在多個(gè)用戶訪問(wèn)同一個(gè)Web服務(wù)，這里用戶要是調(diào)用相對(duì)應(yīng)的Web服務(wù)時(shí)就必須在社區(qū)中排隊(duì)。

圖2 Web服務(wù)與用戶的交互過(guò)程Fig 2 Interaction process of Web service with user

1.2 問(wèn)題描述

Web服務(wù)社區(qū)在給用戶提供服務(wù)時(shí)服務(wù)的數(shù)量是一定的，但是在一個(gè)時(shí)間段到達(dá)社區(qū)的用戶不是不確定的。當(dāng)大量用戶到達(dá)社區(qū)時(shí)就會(huì)出現(xiàn)社區(qū)不能給每個(gè)用戶提供服務(wù)的情況。這樣用戶就會(huì)在社區(qū)中排隊(duì)，等待服務(wù)。當(dāng)大量用戶在社區(qū)時(shí)會(huì)對(duì)社區(qū)產(chǎn)生一些如人力資源、網(wǎng)絡(luò)資源、系統(tǒng)資源等的成本。這些成本會(huì)對(duì)整個(gè)社區(qū)的運(yùn)營(yíng)產(chǎn)生一定的成本。這里要解決的兩個(gè)重要的問(wèn)題。第一是如何確定社區(qū)中排隊(duì)的用戶數(shù)，第二如何設(shè)置服務(wù)數(shù)使得社區(qū)的運(yùn)營(yíng)成本最少。

為了確定社區(qū)中排隊(duì)的用戶數(shù)，要先確定Web服務(wù)社區(qū)中的排隊(duì)模型，本文作者研究用戶服從泊松流到達(dá)服務(wù)社區(qū)。社區(qū)給用戶提供的服務(wù)時(shí)間服從負(fù)指數(shù)分布。各個(gè)服務(wù)之間都是獨(dú)立工作的。本文討論的服務(wù)社區(qū)在提供服務(wù)時(shí)沒(méi)有限制顧客來(lái)源和系統(tǒng)容量。

定義1 設(shè)M/M/n系統(tǒng)的輸入過(guò)程{N(t),t≥0}為參數(shù) 的泊松過(guò)程，即到達(dá)間隔時(shí)間序列{Jk,k≥0}為i.i.d隨機(jī)變量序列，且J1～Γ(1,λ)。服務(wù)機(jī)構(gòu)有n個(gè)(n≥1)服務(wù)臺(tái)，每個(gè)服務(wù)獨(dú)立工作，且具有相同分布的服務(wù)時(shí)間B，B～Γ(1,μ)，即顧客的服務(wù)時(shí)間序列{Bk,k≥1}為i.i.d隨機(jī)變量序列，且B1～Γ(1,μ)并設(shè){Bk,k≥1}與{Jk,k≥1}獨(dú)立。

由定義1知道在M/M/n排隊(duì)模型中，顧客是服從泊松分布到達(dá)系統(tǒng)的，服務(wù)給用戶提供服務(wù)是服從負(fù)指數(shù)分布的，所以，這里選擇M/M/n。在確定好排隊(duì)模型后可以利用排隊(duì)的知識(shí)論得出在社區(qū)中排隊(duì)的用戶數(shù)。

Web服務(wù)社區(qū)中的排隊(duì)模型為M/M/n,當(dāng)用戶按照泊松流到達(dá)系統(tǒng)時(shí)，社區(qū)不能給每個(gè)用戶提供服務(wù)，所以在M/M/n模型排隊(duì)下進(jìn)行排隊(duì)。排隊(duì)會(huì)消耗一些成本，把這些資源統(tǒng)稱為排隊(duì)成本。社區(qū)在給用戶提供服務(wù)時(shí)，服務(wù)本身也有其成本。在設(shè)置不同的服務(wù)數(shù)時(shí)，整個(gè)服務(wù)社區(qū)的運(yùn)營(yíng)成本不同。本文研究的重點(diǎn)是如何在服務(wù)社區(qū)中設(shè)置最優(yōu)的服務(wù)數(shù)使得Web服務(wù)社區(qū)在低成本下運(yùn)營(yíng)。

定義2 記w為排隊(duì)成本，服務(wù)的成本為a，社區(qū)提供的服務(wù)數(shù)c,系統(tǒng)中用戶排隊(duì)的長(zhǎng)度為Ns。得到Web服務(wù)社區(qū)的成本函數(shù)

g(c)=ac+wNs

(1)

在此函數(shù)中，要計(jì)算出最優(yōu)的服務(wù)數(shù)c，使得成本函數(shù)函數(shù)最小。這里排隊(duì)成本、服務(wù)成本都是從實(shí)際生活中能得到，現(xiàn)在需要計(jì)算的就是系統(tǒng)中排隊(duì)的用戶數(shù)Ns。

1.3 Web服務(wù)社區(qū)的排隊(duì)用戶數(shù)

在M/M/n模型下，Web服務(wù)社區(qū)中可以同時(shí)提供c(c>1)個(gè)服務(wù)，用戶服從泊松流到達(dá)，到達(dá)強(qiáng)度為λ。社區(qū)給用戶提供時(shí)沒(méi)有一個(gè)統(tǒng)一的時(shí)間，在M/M/n模型下社區(qū)給用戶提供的服務(wù)時(shí)間服從負(fù)指數(shù)分布，強(qiáng)度為μ。本文討論的服務(wù)社區(qū)在提供服務(wù)時(shí)沒(méi)有限制顧客來(lái)源和系統(tǒng)容量。

(2)

式中

(3)

當(dāng)系統(tǒng)處于平衡狀態(tài)下，系統(tǒng)中的等待對(duì)長(zhǎng)Ns是排隊(duì)對(duì)長(zhǎng)Nq與正在被服務(wù)的顧客數(shù)Nc之和。記作

Ns=Nq+Nc

(4)

當(dāng)ρc<1時(shí)，系統(tǒng)中排隊(duì)長(zhǎng)度Nq為

(5)

當(dāng)系統(tǒng)在平衡時(shí)正在被服務(wù)的顧客數(shù)Nc為

Nc=E[Nc]=ρ

(6)

所以,可以得到在系統(tǒng)在平衡狀態(tài)時(shí)系統(tǒng)的平均顧客數(shù)

(7)

2 邊際分析法

邊際分析法是對(duì)某種變量的增加以及由其引起的總量的變化進(jìn)行統(tǒng)籌考慮來(lái)尋求最優(yōu)解。[10]。本文解決的問(wèn)題是離散的，所以不能使用微積分原理。邊際分析法在解決離散問(wèn)題上的基本思想是追加下一個(gè)單位，然后兩兩比較，選擇相對(duì)優(yōu)的結(jié)果，然后再和其他的比較，直到選擇最優(yōu)的結(jié)果[11]。

本文利用邊際分析法在解決離散問(wèn)題上的思想。由定義(2)可知社區(qū)成本函數(shù)為g(c)=ac+wNs。由于c 是離散的，所以可以逐漸的增加c的值，所以可利用邊際分析法求出最優(yōu)的c。即c要同時(shí)滿足

(8)

整理得到

(9)

在上式中，通過(guò)不斷增加n的值來(lái)確定是否滿足不等式。如果c等于某個(gè)值時(shí)滿足不等式則將c的值輸出，即得出c是Web服務(wù)社區(qū)中提供的服務(wù)數(shù)使得整個(gè)服務(wù)社區(qū)的成本最小。算法如下：

INPUT:Webservicesetλ,μ,w,a

OUTPUT:Minc

1if(ρc<1)

2Computep0(ρ0)

3 Ns(pc)← Nq(pc) + Nc(pc)

4forc=1to∞

5ifMincexist

3 實(shí)驗(yàn)結(jié)果與分析

由于現(xiàn)存的Web服務(wù)社區(qū)比較少，無(wú)法獲得真實(shí)的數(shù)據(jù)，本文模擬銀行排隊(duì)的模型，c采集銀行排隊(duì)模型的數(shù)據(jù)。實(shí)驗(yàn)中，設(shè)置不同的λ，μ，w，a值，然后利用第三節(jié)研究的方法進(jìn)行驗(yàn)證。

實(shí)驗(yàn)首先以Eclipse為開(kāi)發(fā)工具，Java為開(kāi)發(fā)語(yǔ)言，在JDK開(kāi)發(fā)環(huán)境下進(jìn)行實(shí)驗(yàn)的。實(shí)驗(yàn)中設(shè)置λ，μ，w，a值，這里令λ，μ不變，讓w，a不斷的變化，在這種情況下找出最優(yōu)的c值?？梢缘玫綀D3。

圖3 服務(wù)數(shù)與社區(qū)成本的關(guān)系Fig 3 Relationship between service number and community cost

圖3中,隨著服務(wù)數(shù)不斷增大時(shí)，整體的成本會(huì)隨著增大。當(dāng)c=1時(shí)，成本值為負(fù)數(shù)所以舍棄。但是在c=3的時(shí)，成本出現(xiàn)了最小值。所以使用邊際分析法可以找到最優(yōu)的服務(wù)數(shù)c。

為了方便看出二者的差異，實(shí)驗(yàn)中首先讓參數(shù)μ變化，然后比較二者的運(yùn)行時(shí)間。再令λ變化，其他參數(shù)不變?？梢缘玫綀D4、圖5。

圖4 不同μ下邊際分析法與非邊際分析法的運(yùn)行時(shí)間關(guān)系Fig 4 Running time relationship between marginal analysis method and non marginal analysis method with different μ

由圖4可知可以看出，使用邊際分析法的運(yùn)行時(shí)間明顯要小于非邊際分析法，并且使用邊際分析法的運(yùn)行時(shí)間比較穩(wěn)定，運(yùn)算效率要高。

圖5 不同λ下邊際分析法與非邊際分析法的運(yùn)行時(shí)間關(guān)系Fig 5 Running time relationship between marginal analysis method and non marginal analysis method with different λ

由5圖可以看出，使用邊際分析法的運(yùn)行時(shí)間明顯要小于非邊際分析法。

實(shí)驗(yàn)中由于不同PC機(jī)的CPU處理能力不同得到的運(yùn)行時(shí)間也會(huì)不同，但是這里可以保證的是在不同的PC機(jī)上運(yùn)行使用邊際分析法所用的運(yùn)行時(shí)間會(huì)比沒(méi)有使用邊際分析法的運(yùn)行時(shí)間要短。

4 結(jié) 論

針對(duì)Web服務(wù)社區(qū)中最小成本運(yùn)營(yíng)的服務(wù)設(shè)置，本文首先，確定服務(wù)社區(qū)中用戶排隊(duì)的模型為多服務(wù)窗M/M/n。在M/M/n模型下，結(jié)合排隊(duì)論的知識(shí)確定在排隊(duì)穩(wěn)定情況下服務(wù)社區(qū)中用戶排隊(duì)的長(zhǎng)度。然后結(jié)合Web服務(wù)社區(qū)中的成本因素確定成本函數(shù)，并利經(jīng)濟(jì)學(xué)中的邊際分析法進(jìn)行計(jì)算分析，找出最優(yōu)的服務(wù)數(shù)。

通過(guò)實(shí)驗(yàn)驗(yàn)證，使用邊際分析法可以有效的找出最優(yōu)的服務(wù)個(gè)數(shù)，實(shí)驗(yàn)也說(shuō)明了使用邊際分析法要比不使用邊際分析法更有效率。下一步的研究是在M/M/n模型下的排隊(duì)時(shí)間最短。

[1] Guo D K,Ren Y,Chen H H,et al.A QoS-guaranteed and distri-buted model for Web service discovery[J].Journal of Software,2006,17(11):2324-2334.

[2] Bentahar J,Maamar Z,Benslimane D.Using argumentative agents to manage communities of web services[C]∥Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops,Washington D C,USA:IEEE Computer Society,2007:588-593.

[3] Li Ruixuan,Zhang Zhi,Wang Zhigang,et al.WebPeer:A P2P-based system for publishing and discovering Web services[C]∥Proc of the 2005 IEEE International Conference on Service Computing，Washington D C,USA:IEEE Computer Society,2005:149-158.

[4] Maamar Z,Lahkim Mohammed,Benslimane Djamal.Web Ser-vices Communities-Concepts & Operations[C]∥Proc of The 3rd Int’l Conf on Web Information Systems and Technologies,WEBIST’07,2007:323-327.

[5] Ali S,Omer R,Rashid A A.An extended registry for Web ser-vices[C]∥Proceedings of the Service Oriented Computing:Models,Architectures and Applications,SAINT—2003 IEEE Computer Society,Orlando,Florida,2003:85-89.

[6] Al-Masri E,Mahmoud Q H.Crawling multiple UDDI business registries[C]∥Proceedings of the 16th International Conference on World Wide Web,ACM,2007:1255-1256.

[7] Yahyaoui H,Maamar Z,Lim E,et al.Towards a community-based,social network-driven framework for Web services management[J].Future Generation Computer Systems,2013,29(6):1363-1377.

[8] Subramanian S.Highly-available Web service community[C]∥2009 the Sixth International Conference on Information Technology:New Generations,IEEE Computer Society,2009:296-301.

[9] Wang Lei,Liu Fangfang,Yu Jie,et al.Search of Web service based on community[C]∥2012 IEEE The 12th International Conference on Computer and Information Technology,2012:1072-1075.

[10] 李靜江,劉治蘭.管理經(jīng)濟(jì)學(xué)[M]．北京：華文出版社,2002.

[11] 鄺美瑕.關(guān)于離散型隨機(jī)變量的邊際分析決策問(wèn)題的探討[J]．武漢糧食工業(yè)學(xué)院學(xué)報(bào),1992(4):49-55.

Research on set of the optimal service number of web service community based on queue theory*

HE Chen-xiang， FU Xiao-dong， LIU Li， LIU Li-jun， HUANG Qing-song

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

Web service community collect similar Web services to provide services to users.There will be queuing phenomenon when a large number of users access to the community at the same time.Users will take up a portion of the resources when they are queuing in the community,so that a portion of the extra cost will be generated,aiming at this problem，study how to set up the optimal service number,so that the extra cost of this part is minimum.Give the definition of Web service community,and the problem of queuing in the service community is mapped into the problem of queuing theory,the queuing model isM/M/n.Calculate the queue length of users in steady state,and get the number of queuing users in the community.The cost function is determined by the cost factor in the Web service community.The optimal service number is obtained by the marginal analysis method in economics.Experiments show that the method can effectively find the optimal number of services,and the efficiency of the method is relatively high.

Web service； community of Web service； theory of queue； marginal analysis method

2015—11—13

國(guó)家自然科學(xué)基金資助項(xiàng)目(61462056，61462051，71161015，81360230)；云南省重點(diǎn)基金資助項(xiàng)目(2013FA013，2013FA032，2014FA028，2014FB133)

10.13873/J.1000—9787(2016)10—0056—04

TP 311

A

1000—9787(2016)10—0056—04

何晨翔(1989-)，男，安徽蕪湖人，碩士，研究方向?yàn)榉?wù)計(jì)算、軟件工程。