移動(dòng)Ad Hoc網(wǎng)絡(luò)環(huán)境下基于風(fēng)險(xiǎn)的高效可靠的服務(wù)組合方法研究*

胡海洋 ，呂 倩 ，俞東進(jìn) ，趙格華

（1.杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院 杭州 310018；2.南京大學(xué)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 南京 210093；3.香港中文大學(xué)計(jì)算機(jī)科學(xué)與工程系 香港）

1 引言

服務(wù)組合是指將現(xiàn)有的單一、功能簡單、可執(zhí)行的服務(wù)組合成新的復(fù)雜的服務(wù)。所謂服務(wù)，指的是任何可以被其他設(shè)備利用的現(xiàn)有設(shè)備上的軟件組件、數(shù)據(jù)以及硬件資源等。例如，使用手機(jī)上的天氣預(yù)報(bào)軟件可以為手機(jī)用戶提供天氣情況，這就是一個(gè)服務(wù)。

如今，移動(dòng)設(shè)備功能的不斷完善以及無線網(wǎng)絡(luò)的快速發(fā)展，使得在地理上相近的移動(dòng)設(shè)備可以形成一個(gè)小型的無線網(wǎng)絡(luò)。如果處于該網(wǎng)絡(luò)的某個(gè)用戶發(fā)出了一項(xiàng)服務(wù)請求，那么該網(wǎng)絡(luò)內(nèi)任何可以提供相應(yīng)服務(wù)的移動(dòng)設(shè)備都可能成為其服務(wù)的提供者。同時(shí)，由于用戶所請求服務(wù)的復(fù)雜性，在執(zhí)行過程中原服務(wù)請求可能被分解為多個(gè)子服務(wù)來完成，這一系列子服務(wù)通過某些方式組成一個(gè)服務(wù)組合，并且每個(gè)子服務(wù)可以由不同的設(shè)備提供。將服務(wù)分解為多個(gè)子服務(wù)，既可以減少服務(wù)的復(fù)雜性以獲得更好的解決方案，同時(shí)某些子服務(wù)的并行執(zhí)行可以減少服務(wù)的執(zhí)行時(shí)間。此外由于不同的設(shè)備完成同一個(gè)服務(wù)所需的時(shí)間并不一致，這就導(dǎo)致了選取不同的設(shè)備完成服務(wù)的總時(shí)間會(huì)不一致。

在移動(dòng)Ad Hoc網(wǎng)絡(luò)中，由于設(shè)備的移動(dòng)性，設(shè)備之間隨時(shí)可能失去連接，此時(shí)服務(wù)組合就會(huì)失效。目前關(guān)于在動(dòng)態(tài)環(huán)境中服務(wù)組合的可靠性研究，大部分關(guān)注于現(xiàn)有的服務(wù)組合被打斷之后如何進(jìn)行未完成的服務(wù)，而本文的目標(biāo)是為服務(wù)組合中包含的原子服務(wù)搜尋合適的服務(wù)提供者時(shí)進(jìn)行失效風(fēng)險(xiǎn)估計(jì)，使得服務(wù)組合能夠具有較高的可靠性。根據(jù)參考文獻(xiàn)[1～3]的結(jié)論，在移動(dòng)網(wǎng)絡(luò)環(huán)境中可對移動(dòng)的服務(wù)節(jié)點(diǎn)進(jìn)行聚類，得出兩個(gè)服務(wù)節(jié)點(diǎn)處于某個(gè)地理范圍內(nèi)的時(shí)間范圍。根據(jù)這一結(jié)論，本文對服務(wù)節(jié)點(diǎn)之間的移動(dòng)性進(jìn)行了分析，并針對服務(wù)節(jié)點(diǎn)的移動(dòng)性可能使兩個(gè)節(jié)點(diǎn)失去連接從而引起服務(wù)組合中斷的現(xiàn)象，提出了失效風(fēng)險(xiǎn)模型，此模型設(shè)計(jì)出3種用于確定服務(wù)組合中原子服務(wù)的服務(wù)提供者節(jié)點(diǎn)的算法，最后實(shí)現(xiàn)枚舉算法，與本文提出的算法進(jìn)行對比。

文章的主要貢獻(xiàn)如下：

·針對Ad Hoc網(wǎng)絡(luò)環(huán)境的特點(diǎn)，結(jié)合動(dòng)態(tài)預(yù)測技術(shù)結(jié)果，提出一種失效風(fēng)險(xiǎn)模型以描述服務(wù)組合失效的可能；

·設(shè)計(jì)并實(shí)現(xiàn)了3種算法為服務(wù)組合中的每個(gè)原子服務(wù)分配合適的服務(wù)提供者；

·在動(dòng)態(tài)預(yù)測技術(shù)準(zhǔn)確的情況下，實(shí)現(xiàn)對比算法，得到具有最高可靠性的組合方案，以此對比分析本文提出的算法的可行性以及必要性。

2 相關(guān)工作

隨著服務(wù)組合技術(shù)的不斷發(fā)展，它的應(yīng)用領(lǐng)域越來越廣。然而，由于影響服務(wù)組合可靠性的因素多種多樣，在靜態(tài)環(huán)境中，網(wǎng)絡(luò)負(fù)載、帶寬等都會(huì)影響其可靠性；在動(dòng)態(tài)環(huán)境中，服務(wù)節(jié)點(diǎn)的移動(dòng)性是影響服務(wù)組合可靠性的重要因素。因此，服務(wù)組合的可靠性問題一直是服務(wù)組合技術(shù)面臨的一大重要課題。目前，學(xué)術(shù)界對于服務(wù)組合可靠性問題有著大量的研究。針對移動(dòng)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)動(dòng)態(tài)的性質(zhì)，參考文獻(xiàn)[4]提出了一個(gè)框架，該框架包含服務(wù)路由和網(wǎng)絡(luò)路由兩部分，用于組合和發(fā)現(xiàn)服務(wù)，以此實(shí)現(xiàn)最小化服務(wù)的打斷次數(shù)。同樣地，面對動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中服務(wù)組合所面臨的若干問題，參考文獻(xiàn)[5]針對如何使用戶動(dòng)態(tài)地按需使用網(wǎng)絡(luò)中的各種服務(wù)這一問題，提出一種虛擬服務(wù)模型，并在此基礎(chǔ)上定義了虛擬服務(wù)的組合運(yùn)算，給出了動(dòng)態(tài)服務(wù)查找的算法。另外還介紹了支持虛擬服務(wù)透明組合的P2P服務(wù)組合原型系統(tǒng)，并在實(shí)驗(yàn)基礎(chǔ)上對虛擬服務(wù)及其支撐引擎進(jìn)行了客觀評(píng)價(jià)。實(shí)驗(yàn)表明，其所述虛擬服務(wù)及支撐引擎能使面向服務(wù)的應(yīng)用較好地適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下的服務(wù)變化，使用戶能夠透明地按需使用各種資源。參考文獻(xiàn)[6]從服務(wù)節(jié)點(diǎn)的動(dòng)態(tài)性有利于服務(wù)組合優(yōu)化的觀點(diǎn)出發(fā)，利用運(yùn)動(dòng)輔助優(yōu)化算法，通過減少冗余的跳轉(zhuǎn)次數(shù)來減少網(wǎng)絡(luò)開銷，從而改善服務(wù)組合的性能。參考文獻(xiàn)[7]針對服務(wù)組合失敗概率大等問題提出了Web服務(wù)隨機(jī)QoS指標(biāo)的度量方法和自適應(yīng)QoS管理體系結(jié)構(gòu)，利用隨機(jī)離散系統(tǒng)唯一的動(dòng)態(tài)控制方法——馬爾可夫決策過程（MDP），設(shè)計(jì)出了隨機(jī)QoS感知的可靠的Web服務(wù)組合。為了提高Web服務(wù)組合的可靠性，參考文獻(xiàn)[8]使用Web服務(wù)業(yè)務(wù)過程執(zhí)行語言（WS-BPEL）來支持成功的服務(wù)組合。該技術(shù)通過WS-BPEL的誕生動(dòng)態(tài)替換服務(wù)，可以有效地阻止由于意外發(fā)生的服務(wù)錯(cuò)誤導(dǎo)致的服務(wù)組合失效，從而提高服務(wù)組合的可靠性。

此外，參考文獻(xiàn)[9～13]從不同角度使用不同的方法來解決服務(wù)組合的可靠性問題。參考文獻(xiàn)[9]提出一種基于語言的框架來解釋服務(wù)模型和組合邏輯；參考文獻(xiàn)[10]設(shè)計(jì)一種服務(wù)組合重組的方法來保證服務(wù)組合的全局QoS；參考文獻(xiàn)[11]研究如何使用優(yōu)化鏈路狀態(tài)路由協(xié)議維持移動(dòng)網(wǎng)絡(luò)中服務(wù)的質(zhì)量；參考文獻(xiàn)[12]提出一種支持動(dòng)態(tài)地選擇Web服務(wù)的模型，從而使得服務(wù)組合能很好地使用網(wǎng)絡(luò)環(huán)境的變化；參考文獻(xiàn)[13]提出一種Web服務(wù)可靠性的階段模型，描述Web服務(wù)在服務(wù)發(fā)布、服務(wù)發(fā)現(xiàn)、服務(wù)組合等各個(gè)階段的失效過程，并構(gòu)建不同階段的可靠性模型進(jìn)行可靠性預(yù)測。

上述研究工作從不同方面對服務(wù)組合的相關(guān)技術(shù)進(jìn)行了分析與探討，從而為本文的研究提供了良好的基礎(chǔ)。然而對這些研究工作分析后可發(fā)現(xiàn)，大部分研究工作主要關(guān)注于如何在服務(wù)組合執(zhí)行過程中進(jìn)行動(dòng)態(tài)的服務(wù)提供者調(diào)整或者在服務(wù)組合被打斷之后如何進(jìn)行服務(wù)組合的重組。而對于綜合考慮服務(wù)節(jié)點(diǎn)的移動(dòng)性，并根據(jù)服務(wù)節(jié)點(diǎn)的移動(dòng)性進(jìn)行可靠性預(yù)測等方面的相關(guān)研究仍未充分開展。針對這一情況，本文利用服務(wù)節(jié)點(diǎn)移動(dòng)預(yù)測技術(shù)，對服務(wù)節(jié)點(diǎn)的移動(dòng)性進(jìn)行了分析與考慮，并在此基礎(chǔ)之上進(jìn)行服務(wù)組合可靠性模型設(shè)計(jì)以及尋找相應(yīng)的服務(wù)提供者的算法設(shè)計(jì)。

3 問題定義以及模型設(shè)計(jì)

本文目標(biāo)是在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中為服務(wù)請求尋找可靠性較高的服務(wù)組合方案?？紤]圖1的服務(wù)請求示例。

pi表示移動(dòng)設(shè)備的編號(hào)，{si,i=0,1,…}表示移動(dòng)設(shè)備可以提供的服務(wù)的集合。在一個(gè)網(wǎng)絡(luò)中存在著多個(gè)移動(dòng)設(shè)備，每個(gè)設(shè)備可以提供若干個(gè)服務(wù)。如果此時(shí)網(wǎng)絡(luò)中的某個(gè)用戶發(fā)出一個(gè)服務(wù)請求request，假定request的內(nèi)容為s1→{s2,s4}→s3，其中s2和s4并行執(zhí)行。服務(wù)請求用戶會(huì)將該請求發(fā)送給所有它可以連接到的移動(dòng)設(shè)備。接到請求后，每個(gè)移動(dòng)設(shè)備反饋給請求用戶可以提供的服務(wù)列表。請求用戶根據(jù)列表信息以及位置預(yù)測的信息確定請求中每個(gè)服務(wù)的提供者。

對于圖1所示的服務(wù)請求示例，箭頭所示的路徑表示一種服務(wù)組合提供者方案，箭頭上標(biāo)明的數(shù)字表示該條路徑的執(zhí)行順序，箭頭的指向表示數(shù)據(jù)流的方向。箭頭所示路徑的含義為由p2提供服務(wù)s1，p5和 p7分別提供服務(wù) s2和 s4，p3提供服務(wù) s3。

由圖1可知，對于同一個(gè)服務(wù)請求，可以有多種服務(wù)提供者方案。由于執(zhí)行服務(wù)的過程中設(shè)備處于移動(dòng)狀態(tài)，因此會(huì)出現(xiàn)服務(wù)執(zhí)行中斷的情況。另外不同的移動(dòng)設(shè)備完成同一服務(wù)的時(shí)間有所不同，會(huì)直接導(dǎo)致整個(gè)服務(wù)請求的完成時(shí)間有所不同。本文針對上述由于設(shè)備移動(dòng)導(dǎo)致的服務(wù)中斷問題，提出了相應(yīng)的衡量服務(wù)組合方案可靠性的標(biāo)準(zhǔn)，并提出相應(yīng)的數(shù)學(xué)模型以及算法，以確定服務(wù)請求的服務(wù)提供者分配方案。

3.1 基本概念

在動(dòng)態(tài)網(wǎng)絡(luò)中，影響服務(wù)組合可靠性的因素多種多樣，本文只針對在動(dòng)態(tài)網(wǎng)絡(luò)中服務(wù)節(jié)點(diǎn)的移動(dòng)性對服務(wù)組合的可靠性的影響。為方便闡述，本節(jié)定義了一些常用概念。

定義1 （原子服務(wù)）在網(wǎng)絡(luò)中不可再分的，可以完成某項(xiàng)相對簡單任務(wù)的服務(wù)稱為原子服務(wù)，表示為si（i為服務(wù)編號(hào)）。

定義2（服務(wù)節(jié)點(diǎn)）位于移動(dòng)網(wǎng)絡(luò)范圍內(nèi)的無線移動(dòng)設(shè)備，表示為Ni（i為設(shè)備在網(wǎng)絡(luò)中的編號(hào)）。每個(gè)服務(wù)節(jié)點(diǎn)可以提供多個(gè)原子服務(wù)，用SNi表示服務(wù)節(jié)點(diǎn)Ni可以提供的原子服務(wù)的集合，SNi={(sk,tki)|k∈N+}，其中tki表示Ni完成服務(wù)sk所需的時(shí)間，不同的服務(wù)節(jié)點(diǎn)完成相同服務(wù)所需的時(shí)間不同。

定義3 （服務(wù)請求者）在網(wǎng)絡(luò)中發(fā)出服務(wù)請求RS的服務(wù)節(jié)點(diǎn)，即網(wǎng)絡(luò)中的某一個(gè)服務(wù)節(jié)點(diǎn)，若服務(wù)節(jié)點(diǎn)Ni發(fā)出請求，則服務(wù)請求者表示為Nri。

定義4 （服務(wù)執(zhí)行流程圖）本文定義的服務(wù)執(zhí)行流程圖是由一系列原子服務(wù)通過串行或并行的順序組合而成的有向無環(huán)圖。每個(gè)服務(wù)執(zhí)行流程圖對應(yīng)一個(gè)服務(wù)請求RS。例如，圖2所示是由5個(gè)原子服務(wù)組合而成的一個(gè)服務(wù)執(zhí)行流程，圓圈表示原子服務(wù)，箭頭表示服務(wù)的執(zhí)行順序。由s1指向s2表示先執(zhí)行s1再執(zhí)行s2，是串行結(jié)構(gòu)；由s2出發(fā)有兩個(gè)箭頭分別指向s3和s4，表示s3和s4同時(shí)執(zhí)行，是并行結(jié)構(gòu)，并且只能由不同的服務(wù)節(jié)點(diǎn)提供。用表示服務(wù)執(zhí)行流程圖。

定義5 （服務(wù)提供者）在網(wǎng)絡(luò)中提供服務(wù)的服務(wù)節(jié)點(diǎn)，對于編號(hào)為i的服務(wù)節(jié)點(diǎn)表示為pi。

定義6（服務(wù)組合方案）每個(gè)服務(wù)組合方案對應(yīng)一個(gè)服務(wù)請求RS（一個(gè)服務(wù)請求有多個(gè)服務(wù)組合方案可以完成），用 S C 表示，S，二元組(si,pj)表示由服務(wù)提供者 pj提供原子服務(wù)si。

本文考慮無線移動(dòng)網(wǎng)絡(luò)環(huán)境中的動(dòng)態(tài)性，主要是指攜帶無線設(shè)備的個(gè)體的移動(dòng)性，這種移動(dòng)性導(dǎo)致了網(wǎng)絡(luò)內(nèi)任意兩個(gè)服務(wù)節(jié)點(diǎn)在地理上的距離不斷變化。由于無線信號(hào)極大地受到距離的影響，因此兩個(gè)服務(wù)節(jié)點(diǎn)能夠保持連接的時(shí)間受到了限制。鑒于上述特點(diǎn)，本文做了如下定義用于模擬網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)性。

定義7（服務(wù)節(jié)點(diǎn)的相對動(dòng)態(tài)時(shí)期）對于處于網(wǎng)絡(luò)內(nèi)的任意兩個(gè)服務(wù)節(jié)點(diǎn)Ni和Nj，用Tij=[aij,bij]表示這兩個(gè)節(jié)點(diǎn)之間的動(dòng)態(tài)性。即在Tij時(shí)間范圍內(nèi)兩個(gè)節(jié)點(diǎn)之間的連接隨時(shí)可能斷開，連接不穩(wěn)定。在時(shí)刻aij之前連接穩(wěn)定，不受動(dòng)態(tài)性影響，而在時(shí)刻bij之后一定會(huì)斷開連接。

3.2 問題模型定義

由于無線移動(dòng)網(wǎng)絡(luò)環(huán)境的動(dòng)態(tài)性，使得網(wǎng)絡(luò)中的任意兩個(gè)服務(wù)節(jié)點(diǎn)在某一時(shí)刻可能失去連接，導(dǎo)致服務(wù)組合的中斷。本文旨在為處于無線移動(dòng)網(wǎng)絡(luò)環(huán)境中的服務(wù)請求尋找具有較高可靠性的服務(wù)組合方案。給定一個(gè)服務(wù)請求RS，經(jīng)過分析得到了完成該服務(wù)請求對應(yīng)的服務(wù)執(zhí)行流程圖。根據(jù)已知的服務(wù)執(zhí)行流程圖，為圖中的每個(gè)原子服務(wù)尋找合適的提供者，并使得所得到的方案具有較高的可靠性即為本文的目標(biāo)。

根據(jù)網(wǎng)絡(luò)內(nèi)每個(gè)服務(wù)節(jié)點(diǎn)的Mlist，即可為Gers中的每個(gè)原子服務(wù)尋找合適的服務(wù)提供者。由于服務(wù)節(jié)點(diǎn)之間的動(dòng)態(tài)性，最終所得的方案存在著失效的可能，因此本文力求在服務(wù)組合執(zhí)行之前進(jìn)行可靠性分析，使得得出的方案具有較高的可靠性。

對于每一個(gè)服務(wù)請求RS，根據(jù)其他所有服務(wù)節(jié)點(diǎn)返回的匹配結(jié)果列表Mlist設(shè)計(jì)具有較高可靠性的服務(wù)組合方案為本文的目標(biāo)。本文所考慮的服務(wù)組合的可靠性并不是傳統(tǒng)意義上的服務(wù)組合的服務(wù)質(zhì)量、匹配程度以及容錯(cuò)性等特性，而是針對無線移動(dòng)網(wǎng)絡(luò)環(huán)境中，由于服務(wù)節(jié)點(diǎn)的移動(dòng)性所引起的服務(wù)組合中斷的可能性。

根據(jù)3.1節(jié)問題模型中的定義可知，由于每個(gè)服務(wù)提供者完成原子服務(wù)的時(shí)間不一樣，因此不同的服務(wù)組合方案所需的執(zhí)行時(shí)間也不一樣。對此本文做出如下定義。

定義8 （服務(wù)組合長度）一個(gè)服務(wù)組合的長度定義為串行的原子服務(wù)的數(shù)目個(gè)數(shù)加上并行結(jié)構(gòu)的數(shù)目，如圖2的服務(wù)組合長度為4。

定義9 （服務(wù)組合方案完成時(shí)間）一個(gè)服務(wù)組合方案SC所需的完成時(shí)間為CT=∑tik(si,pk)∈SC，tik表示服務(wù)提供者pk完成原子服務(wù)si所需的時(shí)間，并行結(jié)構(gòu)中選取最大執(zhí)行時(shí)間作為該并行結(jié)構(gòu)包含的所有原子服務(wù)的執(zhí)行時(shí)間。

根據(jù)定義7可知，在網(wǎng)絡(luò)中任意兩個(gè)服務(wù)節(jié)點(diǎn)在某一時(shí)間范圍內(nèi)可能連接也可能斷開。假設(shè)服務(wù)節(jié)點(diǎn)Nrj在某一時(shí)刻發(fā)出一個(gè)服務(wù)請求RS，其中的一個(gè)服務(wù)組合方案中包含了(si,pk)，即由服務(wù)提供者pk來提供si，那么如果在si執(zhí)行過程中Nk和Nrj失去連接，則si被迫中斷，服務(wù)組合方案失效。

對于某個(gè)原子服務(wù)si，如果可以找到這樣一個(gè)服務(wù)提供者pk，它與服務(wù)請求者保持連接的最后時(shí)刻晚于si執(zhí)行的完成時(shí)間，則si可以順利完成。但是，由于服務(wù)節(jié)點(diǎn)的頻繁移動(dòng)，為一個(gè)SC包含的每個(gè)原子服務(wù)尋找這樣的服務(wù)提供者幾乎是不可能的，只能尋找具有最小被打斷性可能的組合。

定義10 （超時(shí)風(fēng)險(xiǎn)系數(shù)）對應(yīng)于服務(wù)節(jié)點(diǎn)Nrk發(fā)出的服務(wù)請求PS的一個(gè)服務(wù)組合方案SC，用rij表示其中的每個(gè)元素(si,pj)承擔(dān)的超時(shí)風(fēng)險(xiǎn)系數(shù)，即在si還沒有執(zhí)行結(jié)束的時(shí)候pj和Nrk進(jìn)入相對動(dòng)態(tài)時(shí)期，此時(shí)完成服務(wù)需要承擔(dān)一定風(fēng)險(xiǎn)。rij的定義如下：

其中，stij為開始執(zhí)行服務(wù) si的時(shí)刻，ctij為完成si的時(shí)刻。stij>ajk,ctij≤bjk表示如果在進(jìn)入動(dòng)態(tài)期后才開始執(zhí)行服務(wù)，則承擔(dān)的超時(shí)風(fēng)險(xiǎn)系數(shù)為100%。當(dāng)服務(wù)的完成時(shí)間超出動(dòng)態(tài)期的最晚時(shí)間，服務(wù)一定會(huì)失敗，此時(shí)不需要考慮超時(shí)風(fēng)險(xiǎn)。

3.3 失效風(fēng)險(xiǎn)系數(shù)模型

基于上述動(dòng)態(tài)模擬及概念的定義，本文定義了如下失效風(fēng)險(xiǎn)系數(shù)模型用于為中的每個(gè)原子服務(wù)尋找合適的服務(wù)提供者，以使得整個(gè)服務(wù)組合方案具有較高的可靠性。在此，為描述服務(wù)組合方案的可靠性，本文做了如下定義。

定義12 （失效風(fēng)險(xiǎn)系數(shù)）基于超時(shí)風(fēng)險(xiǎn)系數(shù)以及不穩(wěn)定性的定義，用rpij表示由服務(wù)提供者pj提供單個(gè)原子服務(wù)si的失效風(fēng)險(xiǎn)系數(shù)如下：

整個(gè)服務(wù)組合方案的失效風(fēng)險(xiǎn)系數(shù)如下：

本文使用風(fēng)險(xiǎn)系數(shù)來描述一個(gè)服務(wù)組合方案的可靠性，規(guī)定失效風(fēng)險(xiǎn)系數(shù)越小，則其可靠性越高。已知網(wǎng)絡(luò)內(nèi)任意兩個(gè)服務(wù)節(jié)點(diǎn)的相對移動(dòng)性和每個(gè)服務(wù)節(jié)點(diǎn)對于特定的Mlist，根據(jù)上述定義的風(fēng)險(xiǎn)系數(shù)模型以及3.2節(jié)中的定義，即可為求得具有較高可靠性的服務(wù)組合方案，用 Result表示方案結(jié)果，Result={(si,pj)|si∈Ge,rp}，rp 表示方案整體的失效風(fēng)險(xiǎn)值，(si,pj)表示由pj提供原子服務(wù)si。

4 基于風(fēng)險(xiǎn)系數(shù)模型的可靠性方案設(shè)計(jì)

假設(shè)網(wǎng)絡(luò)中共有m個(gè)服務(wù)節(jié)點(diǎn)。對于一個(gè)包含n個(gè)原子服務(wù)節(jié)點(diǎn)的，若每個(gè)原子服務(wù)平均有k個(gè)服務(wù)提供者，那么對于每個(gè)都有kn種服務(wù)組合方案。若每次都對kn個(gè)服務(wù)組合方案進(jìn)行風(fēng)險(xiǎn)系數(shù)的計(jì)算，然后求得具有最小風(fēng)險(xiǎn)系數(shù)的方案是非常耗時(shí)的。對此，本文基于第3節(jié)提出的失效風(fēng)險(xiǎn)系數(shù)模型，提出以下3種算法來解決求解具有較小風(fēng)險(xiǎn)系數(shù)的服務(wù)組合方案的問題。

假設(shè)服務(wù)請求者Nr0在進(jìn)入網(wǎng)絡(luò)后的st時(shí)刻發(fā)出一個(gè)服務(wù)請求，得到中包含 n個(gè)原子服務(wù)為 s1，s2,…,sn。為每個(gè)原子服務(wù)分配一個(gè)執(zhí)行順序編號(hào)，用ei表示si的執(zhí)行順序，其中屬于同一并行結(jié)構(gòu)的服務(wù)具有相同的執(zhí)行順序編號(hào)。已知網(wǎng)絡(luò)中的其他服務(wù)節(jié)點(diǎn)均已返回匹配結(jié)果列表Mlist，根據(jù)Mlist，可以得出每個(gè)原子服務(wù)的服務(wù)提供者集合，用Pi表示服務(wù)si的服務(wù)提供者集合，Pi={pj|j∈N+}；用Sj表示服務(wù)提供者pj可以提供的屬于的原子服務(wù)集合，Sj={si|si∈}。

4.1 單步枚舉算法

單步枚舉算法（SsE算法）的主要思想是考慮單個(gè)步驟中服務(wù)的數(shù)量并不會(huì)太多，訪問一個(gè)步驟內(nèi)所有的執(zhí)行方案不會(huì)大幅增加執(zhí)行時(shí)間。該算法可以取得每個(gè)步驟的最優(yōu)結(jié)果，從而使得整體結(jié)果具有較高的可靠性。SsE算法的偽代碼如圖3所示。

在該算法中，每次確定一個(gè)執(zhí)行步驟中的原子服務(wù)的執(zhí)行方案，得到一個(gè)執(zhí)行步驟中的失效風(fēng)險(xiǎn)系數(shù)，將每次遍歷得到的風(fēng)險(xiǎn)系數(shù)相加，即得到整個(gè)服務(wù)組合方案的失效風(fēng)險(xiǎn)系數(shù)總和，確定服務(wù)組合方案的可靠性。由于每個(gè)執(zhí)行步驟中包含的原子服務(wù)數(shù)目遠(yuǎn)遠(yuǎn)小于一個(gè)服務(wù)請求中包含的所有原子服務(wù)數(shù)目，所以即使存在枚舉所有執(zhí)行方案的可能，也只是局部枚舉，對算法的時(shí)間復(fù)雜度影響并不大，該算法的平均時(shí)間復(fù)雜度為O(nm)，其中n為中原子服務(wù)的數(shù)目，m為網(wǎng)絡(luò)中服務(wù)提供者數(shù)目。

4.2 最大連續(xù)性及最長執(zhí)行時(shí)間算法

最大連續(xù)性及最長執(zhí)行時(shí)間（BC-LET）算法的主要思想如下。

從執(zhí)行順序編號(hào)最小的且未分配服務(wù)提供者的原子服務(wù)開始，計(jì)算每個(gè)服務(wù)提供者pj能夠連續(xù)提供的原子服務(wù)數(shù)目（對于并行的原子服務(wù)，選擇其中具有最大失效風(fēng)險(xiǎn)系數(shù)的原子服務(wù)），得到每個(gè)服務(wù)提供者pj一次連續(xù)能夠提供的原子服務(wù)的集合spj；選擇能夠提供最多原子服務(wù)的服務(wù)提供者，并將所有被選擇的原子服務(wù)視為一個(gè)服務(wù)，連續(xù)執(zhí)行不可斷開。若有多個(gè)服務(wù)提供者可以提供相同數(shù)目的原子服務(wù)，則根據(jù)失效風(fēng)險(xiǎn)值最小原則選擇。BC-LET算法的偽代碼如圖5所示。

該算法所選擇的服務(wù)組合方案的整體失效風(fēng)險(xiǎn)系數(shù)為每一次選擇的服務(wù)提供者的失效風(fēng)險(xiǎn)總和，平均執(zhí)行時(shí)間復(fù)雜度為O(nm)。

4.3 最晚相對動(dòng)態(tài)期算法

最晚相對動(dòng)態(tài)期（LUTR）算法主要利用已知的服務(wù)提供者之間動(dòng)態(tài)信息，在尋找過程中優(yōu)先選擇相對于服務(wù)請求者最晚進(jìn)入動(dòng)態(tài)期的服務(wù)節(jié)點(diǎn)，然后將該服務(wù)節(jié)點(diǎn)可以提供的服務(wù)標(biāo)記為已分配服務(wù)提供者，在剩余未分配服務(wù)提供者的服務(wù)中繼續(xù)按照上述原則進(jìn)行選擇。若在一次選擇中有多個(gè)服務(wù)節(jié)點(diǎn)具有相同的進(jìn)入動(dòng)態(tài)期時(shí)間，則優(yōu)先選擇最早進(jìn)入網(wǎng)絡(luò)的服務(wù)節(jié)點(diǎn)，其次選擇具有最晚失效時(shí)間的服務(wù)節(jié)點(diǎn)。

由于不同的服務(wù)節(jié)點(diǎn)完成相同的服務(wù)所需時(shí)間不同，先執(zhí)行的服務(wù)的執(zhí)行時(shí)間會(huì)直接影響后繼服務(wù)的開始執(zhí)行時(shí)間，因此當(dāng)有服務(wù)還未確定服務(wù)提供者時(shí)，其后繼的所有服務(wù)的開始時(shí)間都只是一個(gè)估計(jì)值，這會(huì)影響選擇的過程。因此該算法在進(jìn)行一次分配之后，再進(jìn)行一次調(diào)整，對現(xiàn)有分配方案進(jìn)行調(diào)整，調(diào)整過程中直接替換不符合條件的服務(wù)提供者，按照最小失效風(fēng)險(xiǎn)值進(jìn)行替換。LUTR算法偽代碼如圖6所示。

LUTR算法中調(diào)用的調(diào)整算法adjust_best(i,j,k,pro)需要對服務(wù)執(zhí)行流程圖中的每個(gè)原子服務(wù)進(jìn)行一次檢查，首先判斷為其分配的服務(wù)提供者能否滿足時(shí)間等要求，不滿足則進(jìn)行服務(wù)替換，否則不做任何修改。adjust_best(i,j,k,pro)算法偽代碼如圖7所示。

4.4 對比算法

假設(shè)位置預(yù)測不干擾計(jì)算結(jié)果的條件下，本文將利用枚舉法對服務(wù)組合的所有可執(zhí)行方案進(jìn)行失效風(fēng)險(xiǎn)比例的計(jì)算，進(jìn)而將本文提出的3種算法得到的結(jié)果與枚舉出的最優(yōu)方案的結(jié)果進(jìn)行比較，以此證明本文提出的算法在有效改進(jìn)時(shí)間復(fù)雜度的情況下依然可以保證結(jié)果的可靠性。比較從3方面進(jìn)行：算法所得失效風(fēng)險(xiǎn)比例值的比較；由于本文提出的算法會(huì)出現(xiàn)無解的情況，本文將計(jì)算在一定的實(shí)驗(yàn)次數(shù)中在枚舉情況下有解而本文算法無解的次數(shù)，以此來證明算法的可行性；比較本文提出的算法與枚舉算法的時(shí)間消耗。

5 實(shí)驗(yàn)

本文實(shí)驗(yàn)主要研究了服務(wù)組合的復(fù)雜性對算法結(jié)果及執(zhí)行時(shí)間的影響，同時(shí)在相同的數(shù)據(jù)集上實(shí)現(xiàn)了對比算法用于對比本文算法的可行性。服務(wù)組合的復(fù)雜性主要是指服務(wù)組合的長度以及服務(wù)組合的并行度P，定義并行度P=n/L，其中n為服務(wù)組合中原子服務(wù)數(shù)量。本文實(shí)驗(yàn)對于兩個(gè)服務(wù)節(jié)點(diǎn)之間的不穩(wěn)定性函數(shù)使用均勻分布表示，即服務(wù)節(jié)點(diǎn) Ni和 Nj在 t(aij≤t≤bij)時(shí)刻的不穩(wěn)定性

實(shí)驗(yàn)數(shù)據(jù)集的基本設(shè)置如下：在[0，T]時(shí)間段，網(wǎng)絡(luò)中總共有50個(gè)服務(wù)節(jié)點(diǎn)進(jìn)入或離去，每個(gè)服務(wù)節(jié)點(diǎn)在網(wǎng)絡(luò)中停留的時(shí)間不超過T。本文設(shè)定T=100個(gè)時(shí)間單位，另外設(shè)定共有50個(gè)原子服務(wù)可供選擇，每個(gè)服務(wù)節(jié)點(diǎn)可以提供5～10個(gè)原子服務(wù)，完成每個(gè)原子服務(wù)的時(shí)間為3～20個(gè)時(shí)間單位。

5.1 服務(wù)組合長度L的影響

固定參數(shù) P=2，然后改變 L 的值分別為 2、3、4、5、6、7，每種情況進(jìn)行50次實(shí)驗(yàn)取平均值，得到如圖8所示的實(shí)驗(yàn)結(jié)果。根據(jù)圖8的結(jié)果可知，當(dāng)服務(wù)組合長度較小時(shí)，4種算法的結(jié)果比較接近。而隨著服務(wù)組合長度增加，3種算法以及對比算法得出的失效風(fēng)險(xiǎn)值均有所增加，增加幅度也都不斷變大?？傮w而言，SsE算法與最優(yōu)結(jié)果的值最接近。而BC-LET算法和LUTR算法由于在求解過程中有較多的估計(jì)運(yùn)算，導(dǎo)致結(jié)果有所偏差，但是在值不超過5的情況下，其結(jié)果與SsE算法和最優(yōu)結(jié)果同樣比較接近，證明其在長度較短的情況下同樣適用。

5.2 服務(wù)組合并行度P的影響

考慮現(xiàn)實(shí)情況下服務(wù)組合的并行度不會(huì)很大，因此本文實(shí)驗(yàn)只考慮P=1、P=2、P=3的情況。固定參數(shù)L=4，進(jìn)行實(shí)驗(yàn)，所得結(jié)果如圖9所示。分析圖9可知，P值對SsE算法、LUTR算法和對比算法的影響趨勢不穩(wěn)定，原因在于3種算法對于每個(gè)并行結(jié)構(gòu)的失效風(fēng)險(xiǎn)取值只取其中最大的一個(gè)，并不是總和，因此趨勢不穩(wěn)定。而BC-LET算法是從服務(wù)提供者的角度來計(jì)算失效風(fēng)險(xiǎn)，因此隨著并行度的增加，其所得到的值也不斷增加。

結(jié)合圖8和圖9可知，3種算法的結(jié)果與最優(yōu)結(jié)果有所差距，但是整體而言結(jié)果較優(yōu)，尤其是SsE算法。之所以不能采用枚舉算法得到最優(yōu)結(jié)果，是因?yàn)闀r(shí)間上不允許。

5.3 完成時(shí)間對比

本文對4種算法進(jìn)行了完成時(shí)間的分析，表1、表2、表3分別是不同L值和P值下4種算法的執(zhí)行時(shí)間，表格中的**表示無法執(zhí)行完成，未得到時(shí)間結(jié)果。

表1 P=1時(shí)不同L值下每種算法的執(zhí)行時(shí)間（ms）

表2 P=2時(shí)不同L值下每種算法的執(zhí)行時(shí)間（ms）

從表1～表3的結(jié)果可以看出，本文提出的算法基本都能在0.1 s時(shí)間內(nèi)得出結(jié)果。而對比算法只有在服務(wù)組合的P=1的情況下或者P=2的少數(shù)情況下可行，一旦服務(wù)組合復(fù)雜度變高，則其執(zhí)行時(shí)間是不可估量的。而且，本文實(shí)驗(yàn)使用的數(shù)據(jù)集是采用少量數(shù)據(jù)的，現(xiàn)實(shí)情況中若每個(gè)原子服務(wù)的服務(wù)提供者數(shù)量過多，則對比算法根本不可能實(shí)現(xiàn)。

此外，由于本文提出的3種算法都沒有遍歷所有可能的組合方案，存在著原本可以找到匹配服務(wù)組合的請求卻未能得到結(jié)果的可能，本文用錯(cuò)判概率wp來表示這種可能性其中fr表示未得到匹配組合方案的服務(wù)請求次數(shù)，sr表示存在匹配組合方案的服務(wù)請求次數(shù)。為了驗(yàn)證本文提出的算法的可行性，分別對每種算法進(jìn)行720次運(yùn)算得到fr值，并執(zhí)行對比算法得到sr值。實(shí)驗(yàn)結(jié)果見表4。由表4的數(shù)據(jù)可以得出sr=712，因此SsE算法、BC-LET算法和LUTR算法的wp值分別是3.79%、5.05%、3.23%，可見本文提出的算法的錯(cuò)判率并不會(huì)影響算法整體的可行性。

表3 P=3時(shí)不同L值下每種算法的執(zhí)行時(shí)間（ms）

表4 720次執(zhí)行中每種算法沒有得到結(jié)果的次數(shù)

6 結(jié)束語

本文主要研究了在移動(dòng)Ad Hoc網(wǎng)絡(luò)中服務(wù)組合的可靠性問題，提出了一個(gè)數(shù)學(xué)模型以及3種算法以解決此問題，并通過實(shí)驗(yàn)證明提出的算法的可行性。

本文所考慮的服務(wù)組合目前只包含了并行和串行兩種結(jié)構(gòu)，并沒有考慮到現(xiàn)實(shí)情況下一個(gè)任務(wù)可以由不同的服務(wù)完成的選擇情況，未來將在這方面進(jìn)行研究。此外，文章所用的數(shù)據(jù)集雖然描述了網(wǎng)絡(luò)中服務(wù)節(jié)點(diǎn)的移動(dòng)性，但也與實(shí)際情況會(huì)有所差距，采集實(shí)際數(shù)據(jù)進(jìn)行研究也將是未來研究工作的一方面。

1 McDonald B,Znati F.A mobility based framework for adaptive clustering in wireless ad hoc networks.IEEE Journal on Selected Areas in Communications,1999,17(8):1466～1487

2 Yutaka Yanagisawa.Predictive indexing for position data of moving objects in the real world.Transactions on Computer and Science,2009(1):77～94

3 Gao Y J,Zheng B H.Continuous obstructed nearest neighbor queries in spatial databases.SIGMOD’09,2009:577～589

4 Jiang S S,Xue Y,Douglas C,et al.Minimum disruption service composition and recovery over mobile ad hoc networks.Mobile and Ubiquitous Systems:Networking&Services,2007:1～8

5 Li G,Ma X J,Han Y B.Transparent service composition in dynamic network environments.Chinese Journal of Computers,2007,30(4):579～587

6 Ibrahima K T,Yang Y,Zhen Q M,et al.Low redundant hop-countsforservice composition optimization in dynamic network.IEEE International Conference on Cloud and Service Computing,Guilin,China,2011:26～31

7 Fan X Q,Jiang C J,Wang J L,et al.Random-QoS-aware reliable web service composition.Journal of Software,2009,20(3):546～56

8 KIM J P,Hong J E.Dynamic service replacement to improve composite service reliability.International Conference on Secure Software Integration and Reliability Improvement, IEEE Computer Society,Washington D C,USA,2011:182～188

9 Wang Y,Sharad Singhal,Hamid Reza Motahari-Nezhad.A language-based framework for analyzing service representation models and service composition approaches.IEEE International Conference on E-Business Engineering,Shanghai,China,2010:222～229

10 Sherry X Sun,Zhao J.A decomposition-based approach for service composition with global QoS guarantees.Information Sciences,2012(5):138～153

11 Ge Y,Thomas Kunz,Louise Lamont.Quality of service routing in ad hoc networks using OLSR.Proceedings of the 36th Hawaii International Conference on System Sciences,Hawaii,2003

12 Xu D M,Zhao H,Zhang H G.Dynamic web service composition selection strategy for reliability.Computer Science,2011,38(8):53～59

13 Xie C L,Li B X,Wang X F,et al.A staged model for web services reliability.Journal of Southeast University,2012,42(1):40～44