摘  要： 針對(duì)現(xiàn)有服務(wù)選擇技術(shù)的不足，提出一種應(yīng)用服務(wù)社會(huì)網(wǎng)絡(luò)SSN(Service Social Network)機(jī)制的方法。算法主要通過(guò)社會(huì)網(wǎng)絡(luò)原理，將Web候選服務(wù)根據(jù)聯(lián)系緊密程度和服務(wù)本身的QoS屬性選擇滿足用戶需求的組合Web服務(wù)，理論分析和實(shí)驗(yàn)表明算法的有效性和可行性。
關(guān)鍵詞： 服務(wù)選擇；社會(huì)網(wǎng)絡(luò)；服務(wù)質(zhì)量

    隨著面向服務(wù)計(jì)算技術(shù)的深入發(fā)展，通過(guò)組合Web服務(wù)建立分布式應(yīng)用系統(tǒng)逐漸成為基于Web應(yīng)用開(kāi)發(fā)的主流技術(shù)。在眾多可獲得的Web服務(wù)資源中，如何選擇合適的服務(wù)實(shí)例進(jìn)行組合，使之既能滿足應(yīng)用的功能需求，又能滿足用戶提出的QoS需求，是一個(gè)備受關(guān)注的問(wèn)題，并已得到了廣泛的研究。
    QoS約束的Web服務(wù)選擇與組合是一類組合優(yōu)化問(wèn)題。到目前為止，求解該問(wèn)題比較典型的方法有線性規(guī)劃算法[1-2]和遺傳算法[3-6]。線性規(guī)劃算法在候選服務(wù)集規(guī)模較小時(shí)是非常有效的，但是隨著規(guī)模的加大，計(jì)算耗時(shí)增長(zhǎng)速度明顯加快，可擴(kuò)展性變差。遺傳算法被用于QoS的全局組合優(yōu)化已有許多成功的案例，但是，由于在諸多的研究中一般采用隨機(jī)交叉和變異操作，沒(méi)有考慮候選服務(wù)實(shí)例之間實(shí)際存在的連接偏好，組合服務(wù)的可靠性難以得到有效的保證。連接頻率反映了服務(wù)之間的連接偏好，頻率越高，下一次連接的可能性就越大，在一定程度上可增強(qiáng)組合服務(wù)的可靠性。如何利用候選服務(wù)實(shí)例之間的連接偏好優(yōu)化服務(wù)的隨機(jī)選擇，提高服務(wù)組合的效率與成功率是本文主要關(guān)注的問(wèn)題。
    根據(jù)軟件工程的一般常識(shí)可知，一個(gè)復(fù)雜的組合服務(wù)包含平行、分支、選擇、循環(huán)等結(jié)構(gòu)，可以利用數(shù)據(jù)流聚合方法形成顆粒較大的結(jié)構(gòu)塊。而對(duì)于一個(gè)大規(guī)模的候選服務(wù)集合，應(yīng)用社會(huì)網(wǎng)絡(luò)社區(qū)形成機(jī)制[7]，也可以形成與服務(wù)流程聚合塊功能相一致的服務(wù)子集，即所謂的服務(wù)社區(qū)。這樣，服務(wù)選擇就演化成社區(qū)選擇問(wèn)題，運(yùn)用遺傳算法能較好地保證結(jié)構(gòu)性選擇，且依據(jù)連接權(quán)重形成的服務(wù)社區(qū)能充分體現(xiàn)服務(wù)之間的連接偏好。根據(jù)這一思想，本文提出了一個(gè)基于社區(qū)形成機(jī)制和遺傳算法的服務(wù)選擇方法，與傳統(tǒng)遺傳算法不同的是，設(shè)計(jì)了一個(gè)依據(jù)連接偏好的效用函數(shù)估算隨機(jī)選擇概率。初步的實(shí)驗(yàn)結(jié)果證明，該方法行之有效，且具有較高的計(jì)算效率。
1 問(wèn)題描述
    對(duì)于用戶提出的服務(wù)需求首先建立組合服務(wù)流程，圖1所示為一個(gè)有8個(gè)原子服務(wù)S1，S2，…，S8的服務(wù)流程。
    如圖1所示，一般一個(gè)組合Web服務(wù)流程由多個(gè)Web原子服務(wù)組成，每個(gè)Web原子服務(wù)又對(duì)應(yīng)有多個(gè)候選服務(wù)。這些候選服務(wù)可能由不同的服務(wù)提供者提供，具有相同的功能和不同的QoS度量值。

     隨著服務(wù)計(jì)算的迅速發(fā)展，可利用的Web服務(wù)資源越來(lái)越多，候選服務(wù)結(jié)點(diǎn)的規(guī)模也越來(lái)越大。本文總結(jié)了近期相關(guān)的工作，提出了一種基于社會(huì)網(wǎng)絡(luò)社區(qū)形成機(jī)制的Web服務(wù)選擇方法。將Web服務(wù)選擇問(wèn)題轉(zhuǎn)換到社會(huì)網(wǎng)絡(luò)中，利用社會(huì)網(wǎng)絡(luò)特有的性質(zhì)結(jié)點(diǎn)聯(lián)系強(qiáng)度等來(lái)解決服務(wù)選擇問(wèn)題。提出了一種服務(wù)社會(huì)網(wǎng)絡(luò)概率選擇方法，此方法與遺傳算法的不同之處在于變異結(jié)點(diǎn)的選擇不是隨機(jī)的，而是根據(jù)結(jié)點(diǎn)之間的連接頻率，它反映了服務(wù)之間的連接偏好，頻率越高，下一次連接的可能性就越大。
    雖然最終算法給出了很好的性能，但還有待進(jìn)一步改進(jìn)，如本文算法是基于單目標(biāo)優(yōu)化的，希望今后在多目標(biāo)優(yōu)化方面有所進(jìn)展。同時(shí)本文算法是基于歷史信息(服務(wù)實(shí)例)的，因此當(dāng)歷史信息較少或剛開(kāi)始沒(méi)有歷史信息時(shí)性能方面可能會(huì)很差，希望今后在這方面也有所研究。
參考文獻(xiàn)
[1] Zeng Liangzhao，BENATALLAH B，DUMAS M，et al.Quality  driven Web services composition[C].Proceedings of the 12th International Conference on World Wide，2003.
[2] ARDAGNA D，PERNICI B.Adaptive service composition in flexible processes[J].IEEE Trans.Software Eng，2007，33(6)：369-384.
[3] HWANG S Y，WANG H，TANG J，et al.A probabilistic  approach to modeling and estimating the QoS of Web-Services-based Workflows[J].Information Sciences，2007，23(177)：5484-5503.
[4] KLEIN A，ISHIKAWA F，BAUER B.A probabilistic approach  to service selection with conditional contracts and usage  patterns[C].ICSOC-ServiceWave2009，2009：253-268.
[5] Tang Maolin，Ai Lifeng.A hybrid genetic algorithm for the optimal constrained Web service selection problem in Web Service composition[C].WCCI 2010 IEEE World Congress  on Computational Intelligence，2010.
[6] Liu Shulei，Liu Yunxiang，Jing Ning，et al.A dynamic Web  service selection strategy with QoS global optimization based on multi-objective genetic algorithm[C].GCC2005，2005：84-89.
[7] KUMPULA J M，ONNELA J P，SARAMAKI J，et al.Model  of community emergence in weighted social networks[J].  Computer Physics Communication，2009(180)：517.
[8] YU T，ZHANG Y，LIN K J.Efficient algorithms for Web  services selection with end-to-end qos constraints[J].ACM Transactions on the Web，2007，1(1)：1-26.
[9] NEWMAN M E J.Analysis of weighted networks[J].Physical  review，2004，70(05)：1-9.
[10] WASSERMAN S，F(xiàn)AUST K.Introduction to social network analysis[M].Cambridge Cambridge Univ.Press，1994.