1、近年來(lái)，隨著電子商務(wù)和Internet的不斷發(fā)展，Web服務(wù)已經(jīng)成為最具有生命力的Web應(yīng)用集成技術(shù)之一。對(duì)Web服務(wù)的相關(guān)的研究也得到順利開(kāi)展。具體來(lái)說(shuō)，研究者們從Web服務(wù)的抽象和描述、服務(wù)語(yǔ)義和語(yǔ)義級(jí)互操作、服務(wù)社區(qū)化、服務(wù)組合、服務(wù)驗(yàn)證和測(cè)試、服務(wù)的有效管理和組織、服務(wù)的選取、匹配和替換算法、服務(wù)質(zhì)量等方面對(duì)Web服務(wù)展開(kāi)了研究，并已取得了一定的成果。然而在現(xiàn)實(shí)的很多應(yīng)用中，單個(gè)服務(wù)可能難以滿足現(xiàn)在面向服務(wù)應(yīng)用的需求，作為一個(gè)解

2、決方法，由不同的服務(wù)所提供的功能做組合的一個(gè)新型的服務(wù)可能滿足這樣的需求，如此搜索構(gòu)造這樣新型服務(wù)的過(guò)程就被稱作為組合Web服務(wù)的發(fā)現(xiàn)。本文在前人研究的基礎(chǔ)上，對(duì)面向用戶請(qǐng)求的組合Web服務(wù)發(fā)現(xiàn)的問(wèn)題進(jìn)行了深入的探討和研究，提出了基于與或樹(shù)求解的組合Web服務(wù)發(fā)現(xiàn)模型，并設(shè)計(jì)了最優(yōu)Web組合服務(wù)發(fā)現(xiàn)算法、全部’Web組合服務(wù)發(fā)現(xiàn)算法、Top-k優(yōu)組合服務(wù)發(fā)現(xiàn)算法，這些組合算法都高效實(shí)時(shí)處理的特性，具有較高的實(shí)用價(jià)值，這些特性都通過(guò)實(shí)驗(yàn)進(jìn)

3、行了驗(yàn)證。 本文的主要貢獻(xiàn)包括： (1)本文設(shè)計(jì)了一個(gè)同與或樹(shù)同構(gòu)的二叉樹(shù)結(jié)構(gòu)，在此數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上把組合服務(wù)發(fā)現(xiàn)的問(wèn)題轉(zhuǎn)化成為了樹(shù)求解遍歷的問(wèn)題。設(shè)計(jì)了專門用于尋找組合服務(wù)調(diào)用中間結(jié)點(diǎn)的前驅(qū)條件集的策略，并且通過(guò)理論和實(shí)驗(yàn)來(lái)證明了這個(gè)策略的高效性。 (2)提出了面向用戶請(qǐng)求的，基于與或樹(shù)求解的Entire-WSSTs和 Optimal-WSST算法，分別用于求解全部服務(wù)組合，最優(yōu)服務(wù)組合的問(wèn)題。在此期間，為了提高

4、效率我們還做了相應(yīng)的優(yōu)化策略?；谶@兩個(gè)算法，我們實(shí)現(xiàn)了能夠回答用戶請(qǐng)求的組合Web服務(wù)發(fā)現(xiàn)的系統(tǒng)BITS，并且進(jìn)行了一系列的實(shí)驗(yàn)來(lái)驗(yàn)證系統(tǒng)中所實(shí)現(xiàn)的算法的性能。另外本系統(tǒng)還在ICEBE2005服務(wù)組合大賽上獲得了冠軍。 (3)有時(shí)候單個(gè)的最優(yōu)組合Web服務(wù)不能滿足用戶要求，獲取全部組合Web服務(wù)所消耗的時(shí)間又是用戶不可以容忍的。于是，在擴(kuò)展前兩個(gè)求最優(yōu)和全部組合Web服務(wù)算法的基礎(chǔ)上，同時(shí)考慮服務(wù)質(zhì)量的因數(shù)，我們?cè)O(shè)計(jì)了兩個(gè)求前

5、k個(gè)較優(yōu)組合Web服務(wù)的算法，Complete—WSCBT和WSCBT<'*>算法。其中Complete-WSCBT算法是直接從Entire-WSSTs演變過(guò)來(lái)的算法，能夠準(zhǔn)確的找到前k個(gè)最優(yōu)的組合Web服務(wù)，但是效率較低。另一方面，WSCBT<'*>算法是一個(gè)基于啟發(fā)式規(guī)則的算法，雖然找到的是近似的前k個(gè)最優(yōu)組合Web服務(wù)，但通過(guò)實(shí)驗(yàn)證明該近似度相當(dāng)?shù)母?，足以滿足用戶的需求，并且擁有很高的效率。在此基礎(chǔ)上我們擴(kuò)展了原來(lái)的BITS系統(tǒng)，