基于排隊論的Web服務社區最優服務數設置*

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

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

?

基于排隊論的Web服務社區最優服務數設置*

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

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

Web服務社區是將功能類似的Web服務集中到一起為用戶提供服務，當大量用戶同時訪問社區時，會出現排隊現象。用戶在社區中排隊時會占用一部分資源，從而會產生一部分額外的成本。為此研究了如何設置最優的服務數使得這部分的額外成本最小。給出Web服務社區的定義，將在服務社區中排隊的問題映射成排隊論問題，確定排隊模型為M/M/n。計算在穩定狀態時用戶的排隊長度，得出在社區中排隊的用戶數量。結合Web服務社區中的成本因素確定成本函數，結合經濟學中的邊際分析法求出最佳的服務數。實驗表明：該方法可以有效地找出最優的服務數，且效率較高。

Web服務； Web服務社區； 排隊論； 邊際分析法

0 引 言

近年來，隨著互聯網上Web服務的數量的不斷增長，面向服務計算SOC(service oriented computing)成為主流的計算范型。Web服務是一種嶄新的、模塊化、自描述的分布式計算模型，采用可擴展標記語言(XML)定義了Web 服務協議棧， 通過SOAP(simple object access protocol)、UDDI(universal description，discovery ,and integration) 、BPEL4WS(business process execution language for Web integration)和WSFL(Web services flow language)等協議，提供面向互聯網應用的統一服務綁定、發現、及注冊集成調用機制[1]。

隨著Web服務的數量不斷增加，有學者就提出了Web服務社區的概念，文獻[2]指出Web服務社區是由大量的Web服務組合成的，其中，Web服務功能相似且具有不同的非功能的特性。例如，來自不同的提供者或QoS不同。由于在一個Web服務社區中的服務具有相同領域興趣，因此，在領域QoS評價上有最多的共同點，例如，有天氣查詢功能的服務共同組成天氣查詢服務社區。Web服務社區是動態生成的，通過特定場景和協議建立和拆除，集結方式和P2P網絡類似[3]。所有的領域對應的社區中都有一個主Web服務，它儲存該服務社區中所有Web服務的相關信息，并擁有優于社區其他Web服務的各種參數。主Web服務基于語義聚集有相同原子功能的從Web服務。生成方式是雙向的，主服務定期到UDDI查詢是否有符合社區要求的節點，或由新節點向主服務提出加入請求，主服務認證后加入[4～6]。

Web服務社區的概念提出后，文獻[7,8]提出了功能相似的Web服務被分組后如何更容易的在互聯網上被發現的問題。然而這些研究同樣沒有研究當Web服務社區中有大量的服務的情況下。文獻[9]中作者提出了在社區中如何有效的定位Web服務。作者提出在不同的環境下對服務的描述不同于語義層的意思，所以傳統的按照關鍵字去搜索是在Web服務的一個很小的范圍。然而該研究沒有考慮到當Web服務社區中的服務數越來越多的情況。當社區中服務或者用戶過多時作者提出的這種方法就會出現一些錯誤的結果。

綜上所述，國內外對Web服務社區進行了大量的研究。對Web服務社區的研究多數是集中在Web服務的選擇和Web服務社區的結構等問題上，很少有涉及到Web服務的社區的成本問題和社區中Web服務數的設置問題。同時絕大多數研究沒有考慮到當社區中有大量的Web服務和大量用戶訪問社區的情況。本文研究的問題首先就是考慮到社區中有大量的Web服務而且在一個時間段會有大量用戶訪問服務社區。在這種情況下會出現排隊現象，然后本文結合了排隊論和邊際分析法對Web服務社區的運行成本進行了研究。

1 Web服務社區的排隊模型

1.1 Web服務社區

隨著Web服務的不斷增加，出現了Web服務的組合形式。文獻[4]給出了Web服務社區的相關概念和操作。這里用圖形表示出Web服務社區的體系結構。如圖(1)所示。圖1 包含了2 類服務：一種是社區服務，另一個是普通Web 服務。圖1中的社區也是Web服務的一種，這類Web服務規定了某些功能接口，它自身不去實現這類功能，其功能由具體的Web 服務實現，圖1中虛線箭頭表示服務的發布，實線箭頭表示Web 服務實現的相應社區的功能，類似于面向對象中超類和子類的關系。

圖1 Web服務社區體系結構Fig 1 Architecture of Web service community

在Web服務社區的體系結構下，圖2給出了Web服務社區是如何給用戶提供服務。首先Web服務實現社區的接口然后在社區中注冊，然后Web服務去注冊中心進行注冊。當用戶要調用Web服務時，用戶首先到注冊中心查找相關信息，注冊中心會給出用戶所需要的Web服務所在的社區。用戶直接到對應的社區中查找自己需要的Web服務。圖2中也能看出社區中可能存在多個用戶訪問同一個Web服務，這里用戶要是調用相對應的Web服務時就必須在社區中排隊。

圖2 Web服務與用戶的交互過程Fig 2 Interaction process of Web service with user

1.2 問題描述

Web服務社區在給用戶提供服務時服務的數量是一定的，但是在一個時間段到達社區的用戶不是不確定的。當大量用戶到達社區時就會出現社區不能給每個用戶提供服務的情況。這樣用戶就會在社區中排隊，等待服務。當大量用戶在社區時會對社區產生一些如人力資源、網絡資源、系統資源等的成本。這些成本會對整個社區的運營產生一定的成本。這里要解決的兩個重要的問題。第一是如何確定社區中排隊的用戶數，第二如何設置服務數使得社區的運營成本最少。

為了確定社區中排隊的用戶數，要先確定Web服務社區中的排隊模型，本文作者研究用戶服從泊松流到達服務社區。社區給用戶提供的服務時間服從負指數分布。各個服務之間都是獨立工作的。本文討論的服務社區在提供服務時沒有限制顧客來源和系統容量。

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

由定義1知道在M/M/n排隊模型中，顧客是服從泊松分布到達系統的，服務給用戶提供服務是服從負指數分布的，所以，這里選擇M/M/n。在確定好排隊模型后可以利用排隊的知識論得出在社區中排隊的用戶數。

Web服務社區中的排隊模型為M/M/n,當用戶按照泊松流到達系統時，社區不能給每個用戶提供服務，所以在M/M/n模型排隊下進行排隊。排隊會消耗一些成本，把這些資源統稱為排隊成本。社區在給用戶提供服務時，服務本身也有其成本。在設置不同的服務數時，整個服務社區的運營成本不同。本文研究的重點是如何在服務社區中設置最優的服務數使得Web服務社區在低成本下運營。

定義2 記w為排隊成本，服務的成本為a，社區提供的服務數c,系統中用戶排隊的長度為Ns。得到Web服務社區的成本函數

g(c)=ac+wNs

(1)

在此函數中，要計算出最優的服務數c，使得成本函數函數最小。這里排隊成本、服務成本都是從實際生活中能得到，現在需要計算的就是系統中排隊的用戶數Ns。

1.3 Web服務社區的排隊用戶數

在M/M/n模型下，Web服務社區中可以同時提供c(c>1)個服務，用戶服從泊松流到達，到達強度為λ。社區給用戶提供時沒有一個統一的時間，在M/M/n模型下社區給用戶提供的服務時間服從負指數分布，強度為μ。本文討論的服務社區在提供服務時沒有限制顧客來源和系統容量。

(2)

式中

(3)

當系統處于平衡狀態下，系統中的等待對長Ns是排隊對長Nq與正在被服務的顧客數Nc之和。記作

Ns=Nq+Nc

(4)

當ρc<1時，系統中排隊長度Nq為

(5)

當系統在平衡時正在被服務的顧客數Nc為

Nc=E[Nc]=ρ

(6)

所以,可以得到在系統在平衡狀態時系統的平均顧客數

(7)

2 邊際分析法

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

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

(8)

整理得到

(9)

在上式中，通過不斷增加n的值來確定是否滿足不等式。如果c等于某個值時滿足不等式則將c的值輸出，即得出c是Web服務社區中提供的服務數使得整個服務社區的成本最小。算法如下：

INPUT:Webservicesetλ,μ,w,a

OUTPUT:Minc

1if(ρc<1)

2Computep0(ρ0)

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

4forc=1to∞

5ifMincexist

3 實驗結果與分析

由于現存的Web服務社區比較少，無法獲得真實的數據，本文模擬銀行排隊的模型，c采集銀行排隊模型的數據。實驗中，設置不同的λ，μ，w，a值，然后利用第三節研究的方法進行驗證。

實驗首先以Eclipse為開發工具，Java為開發語言，在JDK開發環境下進行實驗的。實驗中設置λ，μ，w，a值，這里令λ，μ不變，讓w，a不斷的變化，在這種情況下找出最優的c值。可以得到圖3。

圖3 服務數與社區成本的關系Fig 3 Relationship between service number and community cost

圖3中,隨著服務數不斷增大時，整體的成本會隨著增大。當c=1時，成本值為負數所以舍棄。但是在c=3的時，成本出現了最小值。所以使用邊際分析法可以找到最優的服務數c。

為了方便看出二者的差異，實驗中首先讓參數μ變化，然后比較二者的運行時間。再令λ變化，其他參數不變。可以得到圖4、圖5。

圖4 不同μ下邊際分析法與非邊際分析法的運行時間關系Fig 4 Running time relationship between marginal analysis method and non marginal analysis method with different μ

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

圖5 不同λ下邊際分析法與非邊際分析法的運行時間關系Fig 5 Running time relationship between marginal analysis method and non marginal analysis method with different λ

由5圖可以看出，使用邊際分析法的運行時間明顯要小于非邊際分析法。

實驗中由于不同PC機的CPU處理能力不同得到的運行時間也會不同，但是這里可以保證的是在不同的PC機上運行使用邊際分析法所用的運行時間會比沒有使用邊際分析法的運行時間要短。

4 結 論

針對Web服務社區中最小成本運營的服務設置，本文首先，確定服務社區中用戶排隊的模型為多服務窗M/M/n。在M/M/n模型下，結合排隊論的知識確定在排隊穩定情況下服務社區中用戶排隊的長度。然后結合Web服務社區中的成本因素確定成本函數，并利經濟學中的邊際分析法進行計算分析，找出最優的服務數。

通過實驗驗證，使用邊際分析法可以有效的找出最優的服務個數，實驗也說明了使用邊際分析法要比不使用邊際分析法更有效率。下一步的研究是在M/M/n模型下的排隊時間最短。

[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] 李靜江,劉治蘭.管理經濟學[M]．北京：華文出版社,2002.

[11] 鄺美瑕.關于離散型隨機變量的邊際分析決策問題的探討[J]．武漢糧食工業學院學報,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

國家自然科學基金資助項目(61462056，61462051，71161015，81360230)；云南省重點基金資助項目(2013FA013，2013FA032，2014FA028，2014FB133)

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

TP 311

A

1000—9787(2016)10—0056—04

何晨翔(1989-)，男，安徽蕪湖人，碩士，研究方向為服務計算、軟件工程。