基于服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)的服務(wù)依賴關(guān)系識別

楊冬菊，張偉達(dá)，趙卓峰

(1.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京100144；2.北方工業(yè)大學(xué) 數(shù)據(jù)工程研究院，北京100144)

0 引言

隨著服務(wù)計(jì)算技術(shù)的快速發(fā)展，以Web服務(wù)為基礎(chǔ)的面向分布式服務(wù)計(jì)算架構(gòu)模式已經(jīng)成為互聯(lián)網(wǎng)環(huán)境下的主流形態(tài)[1-3]?；ヂ?lián)網(wǎng)上的服務(wù)和軟件資源變得極大豐富。網(wǎng)上網(wǎng)下和跨領(lǐng)域之間建立了密切業(yè)務(wù)聯(lián)系，從而形成了跨網(wǎng)跨域跨世界的大規(guī)模網(wǎng)絡(luò)化復(fù)雜服務(wù)的生態(tài)系統(tǒng)——大服務(wù)[4]。大服務(wù)環(huán)境中的服務(wù)通過跨網(wǎng)跨域跨世界進(jìn)行組合，服務(wù)之間通過建立復(fù)雜的依賴及協(xié)作關(guān)系來處理物理信息空間的大數(shù)據(jù)和復(fù)雜的關(guān)聯(lián)業(yè)務(wù)。在此背景下，服務(wù)具有多樣化、異構(gòu)、復(fù)雜、海量等特點(diǎn)，服務(wù)的系統(tǒng)運(yùn)行與協(xié)同互操作模式等發(fā)生了巨大變化，利用云環(huán)境實(shí)現(xiàn)組合服務(wù)的劃分、分布式部署及并行執(zhí)行成為必然趨勢[5-6]。在對組合服務(wù)進(jìn)行合理劃分和分布部署時，需要考慮兩方面因素：①大服務(wù)視角下，服務(wù)之間可能會傳遞大量數(shù)據(jù)，即服務(wù)之間存在數(shù)據(jù)依賴，兩個服務(wù)之間的執(zhí)行距離及網(wǎng)絡(luò)延遲會影響組合服務(wù)的總體執(zhí)行效率；②服務(wù)執(zhí)行時除了存在邏輯上的前后依賴關(guān)系，還可能需要頻繁交換控制信息，即服務(wù)之間存在控制依賴，部署在動態(tài)、開放環(huán)境中分布執(zhí)行會由于存在設(shè)備、網(wǎng)絡(luò)等不確定性影響組合服務(wù)的成功執(zhí)行。

進(jìn)一步剖析上述兩個問題，如何識別并發(fā)現(xiàn)服務(wù)之間存在的數(shù)據(jù)依賴及控制依賴關(guān)系是實(shí)現(xiàn)組合服務(wù)合理劃分、分布部署的前提和基礎(chǔ)。在該過程中，需要解決3個問題：①如何刻畫、設(shè)計(jì)服務(wù)之間的依賴模型；②如何通過對已有服務(wù)關(guān)系的挖掘識別構(gòu)建服務(wù)依賴關(guān)系；③如何基于服務(wù)依賴關(guān)系支撐組合服務(wù)的劃分和分布部署。

針對上述問題，本文提出一種基于服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)的服務(wù)依賴關(guān)系挖掘方法，通過對已有組合服務(wù)的處理與解析，得到服務(wù)之間的控制流和數(shù)據(jù)流，構(gòu)建服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)，并以此為基礎(chǔ)利用圖遍歷算法DFS(depth-first search)、社區(qū)發(fā)現(xiàn)算法Louvain配合改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法HFPGrowth(Hmark-Frequent Pattern Growth)算法生成服務(wù)依賴圖，通過服務(wù)依賴圖有效地描述服務(wù)之間的依賴關(guān)系的強(qiáng)弱，從而支撐組合服務(wù)的合理劃分與分布部署，提高組合服務(wù)的運(yùn)行效率，減少組合服務(wù)因?yàn)榫W(wǎng)絡(luò)通信等原因?qū)е率〉母怕?。最后通過3個實(shí)驗(yàn)驗(yàn)證了本文方法的可行性和有效性，并通過與經(jīng)典算法的對比分析驗(yàn)證了方法的執(zhí)行效率。

1 相關(guān)工作

目前對服務(wù)依賴關(guān)系的研究大多集中在兩方面：①基于服務(wù)依賴關(guān)系實(shí)現(xiàn)服務(wù)的自動組合或組合服務(wù)的演化、優(yōu)化;②基于服務(wù)依賴關(guān)系在組合服務(wù)失效替換時保持其事務(wù)屬性。在實(shí)現(xiàn)方法上，大致可以分為3種：①利用Petri網(wǎng)等理論實(shí)現(xiàn)服務(wù)組合的推理或調(diào)優(yōu)[7-9]；②利用機(jī)器學(xué)習(xí)、事件驅(qū)動等手段建立服務(wù)依賴圖，通過服務(wù)依賴圖支撐服務(wù)組合或組合中的服務(wù)替換[10-14];③通過服務(wù)編排建立相應(yīng)的服務(wù)組合演化模型[15]。文獻(xiàn)[7]基于Petri網(wǎng)全局依賴網(wǎng)的服務(wù)組合自動演化，根據(jù)用戶演化需求對服務(wù)組合進(jìn)行正反向演化推理，為服務(wù)組合自動演化提供了形式化描述工具。文獻(xiàn)[8]引入基于Petri擴(kuò)展有色網(wǎng)(Expand Colored Petri Net， ECPN)構(gòu)建支持事務(wù)級屬性的層次化服務(wù)組合模型，然后利用服務(wù)事務(wù)粒度與服務(wù)補(bǔ)償機(jī)制進(jìn)行服務(wù)組合失效替換，促使服務(wù)組合的可信性增強(qiáng)演化。文獻(xiàn)[9]將服務(wù)聚類成服務(wù)簇，然后基于Petri的服務(wù)網(wǎng)元建立相應(yīng)的服務(wù)簇網(wǎng)元及其矩陣模型，根據(jù)失效服務(wù)網(wǎng)元標(biāo)準(zhǔn)矩陣和組合服務(wù)網(wǎng)模型，提出一種替換服務(wù)的快速查找與替換算法。文獻(xiàn)[10]通過一種數(shù)據(jù)服務(wù)依賴圖模型來實(shí)現(xiàn)服務(wù)組合，根據(jù)輸入的用戶數(shù)據(jù)需求約束，在依賴圖上搜索滿足需求的數(shù)據(jù)服務(wù)依賴子圖，然后執(zhí)行組合后的復(fù)合數(shù)據(jù)服務(wù)生成可視化數(shù)據(jù)視圖。文獻(xiàn)[11]將連續(xù)查詢機(jī)制引入可感知服務(wù)質(zhì)量 (Quality of Service， QoS)的自動服務(wù)組合中，以基于事件驅(qū)動的動態(tài)服務(wù)組合演化，通過有向無環(huán)圖建立服務(wù)依賴圖，配合事件驅(qū)動方法主動監(jiān)控并處理動態(tài)服務(wù)，進(jìn)而實(shí)現(xiàn)組合優(yōu)化。文獻(xiàn)[12]基于控制依賴和貝葉斯網(wǎng)絡(luò)組合而成貝葉斯服務(wù)依賴圖的錯誤定位方法，用于發(fā)現(xiàn)復(fù)合服務(wù)中的錯誤服務(wù)。文獻(xiàn)[13]通過分析WS-BPEL過程與其成員服務(wù)間的依賴關(guān)系，預(yù)判成員服務(wù)是否動態(tài)更新。文獻(xiàn)[14]基于事件驅(qū)動建立物聯(lián)網(wǎng)業(yè)務(wù)流程，通過對業(yè)務(wù)流程分解，將其劃分為多個服務(wù)和多個協(xié)同邏輯碎片，從而實(shí)現(xiàn)業(yè)務(wù)流程的分布式完全解耦執(zhí)行。文獻(xiàn)[15]通過面向服務(wù)編排建立相應(yīng)的服務(wù)組合演化技術(shù)框架或模型。

已有研究工作大多基于服務(wù)自動組合、演化及失效替換等出發(fā)點(diǎn)分析服務(wù)依賴，與本文關(guān)注的組合服務(wù)劃分與分布部署差異較大，而且大多只關(guān)注單一的數(shù)據(jù)依賴或控制依賴，顯然無法直接應(yīng)用在復(fù)雜多變的大服務(wù)環(huán)境中。

2 問題定義及方法原理

為便于問題定義與理解，以“高速公路緊急事故處置”場景為例作進(jìn)一步說明。該場景定義了一個組合服務(wù)“高速公路緊急事故處置”，將高速公路上處置緊急事故時需要的所有服務(wù)按照邏輯順序組合在一起，如圖1所示。啟動事件為監(jiān)測到事故發(fā)生，首先進(jìn)行事故信息的采集，包括事故發(fā)生的時間、地點(diǎn)、當(dāng)前路段的流量和車速、最近幾個收費(fèi)站的車流量、當(dāng)前的天氣情況、事故地點(diǎn)附近的收費(fèi)站或路段監(jiān)控攝像頭等，根據(jù)這些數(shù)據(jù)對事故級別進(jìn)行判定，包括車輛損傷程度、有無人員傷亡、有無惡劣天氣、有無道路損毀等，然后對事故進(jìn)行相應(yīng)處置，包括警車和救護(hù)車等應(yīng)急車輛的調(diào)度以及其他車輛的管控，前者搜索范圍內(nèi)的緊急車輛并進(jìn)行緊急通知，后者根據(jù)收費(fèi)站、路段管控范圍等生成管控方案。

分析上述組合服務(wù)發(fā)現(xiàn)，部分服務(wù)之間需要傳輸大量數(shù)據(jù)，如圖1中事故判定的前提是需要路段流量計(jì)算、氣象監(jiān)測、路段攝像頭等服務(wù)操作提供的事故數(shù)據(jù)采集信息才能進(jìn)行事故計(jì)算等操作，因此在事故數(shù)據(jù)采集服務(wù)和事故處理服務(wù)之間會傳輸這些實(shí)時、大量數(shù)據(jù)。除了服務(wù)之間存在流程上的邏輯依賴關(guān)系，在部分服務(wù)之間存在頻繁的信息交互，如警車、救護(hù)車調(diào)度和查找并通知服務(wù)，如果查找指定的范圍內(nèi)救護(hù)車和警車不符合調(diào)度條件，則需要擴(kuò)大搜索范圍進(jìn)行二次通知，依次迭代下去，直至符合調(diào)度條件為止，因此在應(yīng)急車輛調(diào)度服務(wù)和警車調(diào)度服務(wù)、救護(hù)車調(diào)度服務(wù)之間存在較為頻繁的信息交互。如果將這些相互具有強(qiáng)依賴性的服務(wù)隨機(jī)部署在不同的節(jié)點(diǎn)或網(wǎng)絡(luò)環(huán)境上，大量數(shù)據(jù)傳輸時網(wǎng)絡(luò)距離或網(wǎng)絡(luò)開銷會直接影響組合服務(wù)的執(zhí)行效率，同時頻繁的信息交互會由于動態(tài)、開放環(huán)境下設(shè)備、網(wǎng)絡(luò)等的不確定性影響執(zhí)行結(jié)果。

在上述過程中，識別并發(fā)現(xiàn)服務(wù)之間存在的數(shù)據(jù)依賴及控制依賴關(guān)系成為要解決的核心問題，依據(jù)服務(wù)依賴關(guān)系實(shí)現(xiàn)組合服務(wù)的合理劃分與分布部署執(zhí)行，更好地支撐分布式環(huán)境下組合服務(wù)的高效、可靠執(zhí)行。由此本文提出一種基于已有組合服務(wù)構(gòu)建服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)并根據(jù)服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)識別服務(wù)依賴關(guān)系的方法。首先對組合服務(wù)進(jìn)行預(yù)處理，解析得到服務(wù)之間的前驅(qū)后繼關(guān)系及數(shù)據(jù)交互情況，利用有向圖構(gòu)建服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)，然后對服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行深度遍歷和挖掘，形成由數(shù)據(jù)依賴圖和控制依賴圖組合而成的服務(wù)依賴圖，依據(jù)服務(wù)依賴圖實(shí)現(xiàn)組合服務(wù)的劃分。方法原理如圖2所示。

3 服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)模型及構(gòu)建

3.1 服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)模型

定義1服務(wù)(AS)。指服務(wù)提供者與消費(fèi)者之間為共同創(chuàng)造價值而進(jìn)行的某種交互協(xié)作，往往表現(xiàn)為交互界面、功能實(shí)體等。它可以由軟件實(shí)現(xiàn)，也可以由人工或人機(jī)實(shí)現(xiàn)，可以是不可再分的原子服務(wù)，也可以是抽象服務(wù)。為簡化操作，本文暫時只考慮軟件定義的原子服務(wù)?？梢员硎緸榫旁M：

AS=

Type,Community,Operations>。

其中：Id是AS的唯一標(biāo)識符；Name是AS的名稱；Desc是AS的語義描述；Input是AS的輸入?yún)?shù)集合，Input(AS)={IP1,IP2,…,IPn}，其中IP代表其中的輸入?yún)?shù)；Output是AS的輸出參數(shù)集合，Output(AS)={OP1,OP2,…,OPn}，其中OP代表其中的輸出參數(shù)；Publisher是AS的提供商；Type是流程中AS的類型標(biāo)識，有start、middle、end等；Community是AS所屬社區(qū)；Operations是AS的執(zhí)行操作。

定義2服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)(SN)。記錄服務(wù)之間關(guān)聯(lián)關(guān)系的網(wǎng)絡(luò)。它可表示為一個有向圖。

SN=，

式中：V是有向圖的頂點(diǎn)集，V={AS1,AS2,…,ASn}，ASi∈AS，1≤i≤n；E是有向圖的邊集，E=V×V={(ASi,ASj,R) |ASi,ASj∈V，ASi→ASj(ASi和ASj存在某種關(guān)聯(lián)關(guān)系)，R是關(guān)系的類型，1≤i,j≤n}。其中，R∈{“RDD”,“RCD”}，當(dāng)R=“RDD”時，表示兩個服務(wù)之間具有數(shù)據(jù)依賴關(guān)系，當(dāng)R=“RCD”時，表示兩個服務(wù)之間具有控制依賴關(guān)系。

定義3服務(wù)組合(SC)。將多個服務(wù)組合在一起完成復(fù)雜的業(yè)務(wù)需求，采用BPMN 2.0規(guī)范[16]進(jìn)行描述。數(shù)學(xué)表達(dá)式采用類BNF范式[17]表示為：

SC::=X|ASs⊙ASm|ASs◇ASm|ASs?ASm

|ASs△ASm|ASs||cASm|ASs#ASm。

其中：X表示服務(wù)或者空服務(wù)；ASs⊙ASm，ASs◇ASm，ASs?ASm，ASs△ASm，ASs||cASm分表表示圖3所示Sequence、And-Join、Or-Join、And-Split、Or-Split五種控制結(jié)構(gòu)[18]。大部分復(fù)雜控制結(jié)構(gòu)都可以由這5種變遷組合構(gòu)成，ASs#ASm表示ASs和ASm之間存在數(shù)據(jù)流。

定義4數(shù)據(jù)依賴(RDD)。在服務(wù)組合執(zhí)行的過程中，如果兩個AS之間存在業(yè)務(wù)的數(shù)據(jù)交互，即存在服務(wù)ASs,ASm，使得Output(ASs)∩Input(ASm)≠?&&Q(Output(ASs),Input(ASm))>Y，則稱ASs,ASm之間存在數(shù)據(jù)依賴關(guān)系，記作RDD(ASs,ASm)。ASs稱作ASm的數(shù)據(jù)流前驅(qū)，ASm稱作ASs的數(shù)據(jù)流后繼。其中Y是閾值，Q(C1,C2)表示兩個集合的交集閾值函數(shù)，參數(shù)C代表集合。

定義5控制依賴(RCD)。在服務(wù)組合執(zhí)行的過程中，服務(wù)之間的執(zhí)行是有前后順序的，這是服務(wù)業(yè)務(wù)邏輯之間的依賴，稱為控制依賴。5種結(jié)構(gòu)下的控制依賴描述如下：

(1)Sequence結(jié)構(gòu)下，有ASs⊙ASm，表示服務(wù)ASs執(zhí)行后才能夠執(zhí)行ASm。此時ASs是ASm的控制前驅(qū)，ASm是ASs的控制后繼，則ASs和ASm之間存在控制依賴，記作RCD(ASs，ASm)。

(2)Or-Split結(jié)構(gòu)下，有ASs◇ASi，?ASi∈{AS1，AS2，…，ASn}，1≤i≤n，表示在服務(wù)ASs執(zhí)行后選擇執(zhí)行AS1，AS2，…，ASn中的其中一個服務(wù)。在此情況下，任意ASi要么不執(zhí)行，要么一定在ASs后執(zhí)行，則ASs和ASi之間存在控制依賴，記作RCD(ASs，ASi)。

(3)Or-Join結(jié)構(gòu)下，有ASi?ASm，?ASi∈{AS1，AS2，…，ASn}，1≤i≤n，表示在服務(wù)AS1，AS2，…，ASn中至少一個執(zhí)行完畢后才能夠執(zhí)行服務(wù)ASm。在此情況下，ASi和ASm之間存在控制依賴，記作RCD(ASs，ASi)。

(4)And-Split和And-Join結(jié)構(gòu)與前面類似，不再贅述。

3.2 服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建與更新

遍歷并解析已有組合服務(wù)得到包含的服務(wù)及其前驅(qū)后繼依賴關(guān)系，轉(zhuǎn)化成有向圖模型進(jìn)行描述與存儲，得到服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)。當(dāng)有新的組合服務(wù)加入時，需要識別并判斷服務(wù)節(jié)點(diǎn)、關(guān)系在已有服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)中是否存在并根據(jù)不同的策略更新合并。具體步驟如下：

步驟1數(shù)據(jù)預(yù)處理。讀取已有服務(wù)組合，根據(jù)前驅(qū)后繼將服務(wù)標(biāo)注type屬性，start、middle、end分別表示一個服務(wù)組合的執(zhí)行啟動服務(wù)、中間服務(wù)以及結(jié)束服務(wù)。

步驟2解析提取數(shù)據(jù)。對服務(wù)組合進(jìn)行解析得到包含的服務(wù)及其關(guān)系，篩選具有數(shù)據(jù)依賴或控制依賴關(guān)系的服務(wù)節(jié)點(diǎn)對，分別存儲為節(jié)點(diǎn)數(shù)據(jù)以及關(guān)系數(shù)據(jù)。

步驟3利用上述數(shù)據(jù)初始化構(gòu)建服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)。以前述“高速公路緊急事故處置”為例，建立的服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)如圖4所示。

步驟4當(dāng)有新的組合服務(wù)加入時，首先判斷服務(wù)節(jié)點(diǎn)及關(guān)系在已有服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)中是否存在，假設(shè)關(guān)聯(lián)網(wǎng)絡(luò)中存在服務(wù)節(jié)點(diǎn)及關(guān)系，ASs→ASm，RDD(ASs,ASm)&&RCD(ASs,ASm)，新加入的服務(wù)節(jié)點(diǎn)及關(guān)系是，AS1→AS2，RDD(AS1,AS2)&&RCD(AS1,AS2)，則具體更新策略如圖5所示。

(1)當(dāng)ASs=AS1，ASm≠AS2時，加入服務(wù)節(jié)點(diǎn)AS2以及關(guān)系RCD、RDD，更新后如圖5中①所示。

(2)當(dāng)ASs=AS2，ASm=AS1時，則說明兩個服務(wù)節(jié)點(diǎn)都存在，但是關(guān)系方向有變化，則節(jié)點(diǎn)不變，在兩個節(jié)點(diǎn)之間加入新的關(guān)系，如圖5中②所示。

(3)當(dāng)ASs≠AS1，ASm=AS2時，加入服務(wù)節(jié)點(diǎn)AS1以及關(guān)系RCD、RDD，更新后如圖5中③所示。

(4)當(dāng)ASs≠AS2，ASm=AS1時，加入服務(wù)節(jié)點(diǎn)AS2以及相應(yīng)的關(guān)系RCD、RDD，更新后如圖5中④所示。

(5)當(dāng)ASs=AS2，ASm≠AS1時，加入服務(wù)節(jié)點(diǎn)AS1以及相應(yīng)的關(guān)系RCD、RDD，更新后如圖5中⑤所示。

(6)當(dāng)ASs≠AS1，ASm≠AS2時，新建立服務(wù)節(jié)點(diǎn)AS1、AS2以及關(guān)系RCD、RDD，更新后如圖5中⑥所示。

(7)當(dāng)ASs=AS1，ASm=AS2時，則認(rèn)為已經(jīng)存在，不做變更。

若RCD、RDD只存在一種，則處理策略類似。

步驟5節(jié)點(diǎn)由于宕掉或者其他原因退出網(wǎng)絡(luò)，此時也要匹配節(jié)點(diǎn)以及節(jié)點(diǎn)周圍的關(guān)聯(lián)關(guān)系，一起退出網(wǎng)絡(luò)。

4 服務(wù)依賴關(guān)系識別

4.1 數(shù)據(jù)依賴圖

服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)中記錄了服務(wù)節(jié)點(diǎn)的類型屬性(start、middle、end)和服務(wù)之間的數(shù)據(jù)依賴關(guān)系，依據(jù)類型屬性及數(shù)據(jù)依賴關(guān)系對服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行遍歷，抽取相關(guān)服務(wù)節(jié)點(diǎn)及其關(guān)系得到數(shù)據(jù)依賴圖。數(shù)據(jù)依賴圖是服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)在數(shù)據(jù)依賴維度上的投影。在該過程中，使用深度優(yōu)先搜索遍歷所有數(shù)據(jù)依賴項(xiàng)，算法如下：

算法1服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)遍歷associatedNetworkDFS(Graph associatedNetwork, Type start, Type end，String Y)。

輸入：服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)associatedNetwork，啟動服務(wù)(start)，結(jié)束服務(wù)(end)，閾值Y;

輸出：數(shù)據(jù)依賴圖dataDependenceGraph。

1.if (d==associatedNetwork.Depth() && Node nextNode.type.equals(end){//d的初始值為1表示圖的深度

2. return dataDependGraph.put(nextNode，Y); //根據(jù)閾值返回強(qiáng)弱數(shù)據(jù)依賴圖

3. for (Node nextNode in start){//遍歷跟節(jié)點(diǎn)n相鄰的節(jié)點(diǎn)nextNode，

4. if (!visit[nextNode]){//未訪問過的節(jié)點(diǎn)才能繼續(xù)搜索

5. visit[nextNode]=true; //搜索過的節(jié)點(diǎn)設(shè)置成已訪問

6. if (DFS(nextNode, d+1)){ return true;}//如果搜索出有解

7.visit[nextNode]=false; //重新設(shè)置成未訪問

8. }

9. }

10. return ;

11. }

4.2 控制依賴圖

在實(shí)際環(huán)境中，服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)會出現(xiàn)分布不均勻的情況，表現(xiàn)為有向圖上的節(jié)點(diǎn)入度或出度從1～n分布，有些節(jié)點(diǎn)只存在單路徑。這些數(shù)據(jù)在關(guān)聯(lián)分析時對結(jié)果影響很小，但是對分析效率影響很大，因此提出一種社區(qū)發(fā)現(xiàn)與關(guān)聯(lián)規(guī)則挖掘組合方法。首先使用社區(qū)發(fā)現(xiàn)算法(Louvain)將服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)劃分成多個社區(qū)，每個社區(qū)內(nèi)形成一個服務(wù)網(wǎng)絡(luò)，去掉處于獨(dú)立狀態(tài)的節(jié)點(diǎn)，形成有向連通圖。然后在傳統(tǒng)FPGrowth算法基礎(chǔ)上進(jìn)行改進(jìn)，提出HFPGrowth算法對篩選后的服務(wù)社區(qū)進(jìn)行關(guān)聯(lián)規(guī)則分析，利用分析結(jié)果構(gòu)建控制依賴圖?？刂埔蕾噲D是服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)在控制關(guān)系維度上投影與分析的結(jié)果，能夠記錄服務(wù)之間存在的控制依賴關(guān)系。

4.2.1 社區(qū)發(fā)現(xiàn)算法-Louvain

Louvain算法基于模塊度(如式(1))進(jìn)行社區(qū)發(fā)現(xiàn)，該算法在效率和效果上均表現(xiàn)較好，并且能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)，其優(yōu)化的目標(biāo)是最大化整個圖屬性結(jié)構(gòu)(關(guān)聯(lián)網(wǎng)絡(luò))的模塊度。

(1)

其中：m為圖中邊的總數(shù)量，ki表示所有指向節(jié)點(diǎn)i的連邊權(quán)重之和，kj同理。Aij表示節(jié)點(diǎn)i，j之間的連邊權(quán)重。δ(u,v)判斷節(jié)點(diǎn)u和v是否在同一社區(qū)，算法主要步驟如下：

(1)將圖中的每個節(jié)點(diǎn)看作一個社區(qū)；

(2)對每個節(jié)點(diǎn)，依次嘗試將節(jié)點(diǎn)分配到其每個鄰居所在的社區(qū)，計(jì)算分配前與分配后的模塊度變化，并記錄分配后模塊度最大的那個點(diǎn)。選擇對應(yīng)模塊度最大的點(diǎn)，加入其所在社區(qū)；

(3)重復(fù)步驟(2)，直至每個節(jié)點(diǎn)的社區(qū)歸屬不再變化；

(4)壓縮每個社區(qū)，將其壓縮成一個新的節(jié)點(diǎn)，這時，邊的權(quán)重為兩個節(jié)點(diǎn)內(nèi)所有原始節(jié)點(diǎn)的邊權(quán)重之和；

(5)迭代上述步驟，直至圖中模塊度不再變化。

算法2社區(qū)發(fā)現(xiàn)算法graphLouvain(Graph associatedNetwork)。

輸入：服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)圖associatedNetwork;

輸出：劃分后服務(wù)社區(qū)CommunityGraph。

1.associatedNetwork.initSingletonClusters();//網(wǎng)絡(luò)初始化

2.nodeNumber=associatedNetwork.getNodeNumber();//獲取圖中節(jié)點(diǎn)的數(shù)量

3. while(localCommunity){ //當(dāng)局部社區(qū)的結(jié)構(gòu)不再發(fā)生變化

4. for i=1 to nodeNumber {//其中nodeNumber為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量

5. Cn=searchNeighbor(i).getCommunity; //獲取節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的社區(qū)屬性

6. △Q=calcModularityFunction(i,Cn); //計(jì)算節(jié)點(diǎn)i移入Cn之后模塊度增量

7.Cmax=maxModularityCommunity(△Q); // 計(jì)算使模塊度最大化的鄰居

8. Ci=getCommunity(i);

9.if(Ci !=Cmax){ Ci=Cmax;} //i所在社區(qū)Ci不同于最大值，修改為最大值

10. update Community(); //形成新的社區(qū)超點(diǎn)

11.restructuringNetwork(Ci); //重新構(gòu)造網(wǎng)絡(luò)

12. }

13.buildHierarchicalCommunityStructure();

14. Listcommunities ;

15. returnCommunityGraph.put(community);

16. }

4.2.2 關(guān)聯(lián)規(guī)則挖掘算法-HFPGrowth算法

數(shù)據(jù)的關(guān)聯(lián)分析能夠從大規(guī)模數(shù)據(jù)中分析并挖掘有價值的關(guān)聯(lián)性知識，主要通過關(guān)聯(lián)規(guī)則挖掘來實(shí)現(xiàn)，本文對傳統(tǒng)的FPGrowth算法進(jìn)行改進(jìn)，使其在面對大規(guī)模的服務(wù)組合環(huán)境下，在執(zhí)行效率和結(jié)果正確率上都有一定提升。

在傳統(tǒng)算法中，需要利用FP-Tree構(gòu)造算法生成一個包含完整頻繁項(xiàng)信息的FP樹，其中FP樹的頻繁項(xiàng)頭表中擁有ItemName(項(xiàng)名稱)、Count(到達(dá)節(jié)點(diǎn)子路徑數(shù))、NextLink(指針，指向FP樹中同名的第一個節(jié)點(diǎn))。在該過程中，首先構(gòu)造FP樹是無序的，導(dǎo)致后序遍歷出大量無序結(jié)果，這在服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)中是不允許的，因?yàn)榉?wù)之間存在依賴關(guān)系，即有業(yè)務(wù)邏輯順序。其次，在構(gòu)造FP樹的過程中，若新增節(jié)點(diǎn)在樹中要新啟一個分支，即沒有同父節(jié)點(diǎn)，則需要在項(xiàng)頭表中找到與該節(jié)點(diǎn)同ItemName的節(jié)點(diǎn)，遍歷其列表，直至最后一個同名節(jié)點(diǎn)的域，向最后追加此節(jié)點(diǎn)。這樣，每當(dāng)數(shù)據(jù)量較大時，每次都要遍歷到最后再追加，執(zhí)行效率會受影響。

針對上述問題，本文在FP樹的構(gòu)造節(jié)點(diǎn)提出一種優(yōu)化樹、表結(jié)構(gòu)的方法，具體如下：

(1)要絕對保持對事務(wù)集合中的服務(wù)的執(zhí)行順序，剔除非頻繁1項(xiàng)集后取消其對原始數(shù)據(jù)的排序操作。

(2)在原有的項(xiàng)頭表的基礎(chǔ)上添加一個新的屬性Hmark。用于記錄每一個數(shù)據(jù)項(xiàng)當(dāng)前的頭結(jié)點(diǎn)，通過對這種新的頻繁項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)，執(zhí)行insert_tree()操作后在項(xiàng)頭表Hmark前插入節(jié)點(diǎn)，并把Hmark指向最新插入的節(jié)點(diǎn)。這樣可以避免遍歷操作，減少FP樹的構(gòu)建時間。

優(yōu)化后的項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 項(xiàng)頭表數(shù)據(jù)結(jié)構(gòu)

算法3關(guān)聯(lián)規(guī)則挖掘算法HFPGrowth (List>SD , intminsup)。

輸入：原始事務(wù)集合SD，最小支持度minSup

輸出：控制依賴圖controlDependenceGraph

1. Collection freqMap=getFrequencyAndSup(SD); // 計(jì)算頻數(shù)以及支持度

2. Mapheaders=new HashMap(); // 構(gòu)建項(xiàng)頭表Head

3.TreeNode tree=new TreeNode("Null"); //構(gòu)建根為null的空樹

4. for(item in SD){ //向樹中插入節(jié)點(diǎn)

5. if(tree.traverse(p)){ //遍歷FPtree

6. count(N)++;，//如果樹中有N.itemName=p.itemName，N計(jì)數(shù)增加

7. }else{

8. Node node=new Node(N); //創(chuàng)建新節(jié)點(diǎn)

9. count(n)=1; //計(jì)數(shù)置為1

10. tree.add(node); //鏈接到樹中

11. headers.add(Hmark,node); //在與同名的頻繁項(xiàng)頭表，插入到Hmark前，并設(shè)置此節(jié)點(diǎn)為新的Hmark。

12. }

13. if(!p){insert_tree(p.next,tree)}//如果p非空繼續(xù)遞歸

14.}

15. Map, Integer>pattens=fpTree.getFrequentItems();

16. Listrules=fpTree.getAssociateRule();//對FP樹進(jìn)行關(guān)聯(lián)規(guī)則挖掘

17. returncontrolDependenceGraph.put(rules);//返回控制依賴圖

為了能夠更加準(zhǔn)確形象地表現(xiàn)服務(wù)之間的依賴關(guān)系，同時避免單一依賴關(guān)系的局限性，將4.1節(jié)中得到的數(shù)據(jù)依賴圖和4.2節(jié)中得到的控制依賴圖通過匹配不同節(jié)點(diǎn)、計(jì)算重疊節(jié)點(diǎn)和關(guān)系的方式進(jìn)行合并，形成服務(wù)依賴圖。

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

本文描述的方法使用Java、Spark與Python實(shí)現(xiàn)，圖數(shù)據(jù)庫采用GraphXR+Neo4j，源數(shù)據(jù)庫采用Mysql，網(wǎng)絡(luò)拓?fù)洳捎肕ATLAB完成。

為驗(yàn)證本文方法的有效性，設(shè)計(jì)了3個實(shí)驗(yàn)：實(shí)驗(yàn)一是功能驗(yàn)證，首先從ProgrammableWeb[注]https://www.programmableweb.com/。上爬取服務(wù)，利用MATLAB生成的網(wǎng)絡(luò)拓?fù)鋵⑦@些服務(wù)進(jìn)行映射，分析并提取數(shù)據(jù)，形成服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)。然后基于服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)，利用圖遍歷計(jì)算出數(shù)據(jù)依賴圖，利用Louvain+HFPGrowth組合算法完成控制依賴圖的獲取，構(gòu)建服務(wù)依賴圖，形成可視化展示。

實(shí)驗(yàn)二是算法的執(zhí)行時間驗(yàn)證，將HFPGrowth算法和傳統(tǒng)的Apriori、FPGrowth算法在同樣的社區(qū)服務(wù)網(wǎng)絡(luò)上執(zhí)行，對比執(zhí)行時間。

實(shí)驗(yàn)三是算法的結(jié)果驗(yàn)證，將Louvain+HFPGrowth組合算法與傳統(tǒng)的Apriori、FPGrowth算法基于原始的服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)圖上進(jìn)行實(shí)驗(yàn)，比對執(zhí)行結(jié)果。

5.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i5-5200U CPU @2.20 GHz 2.19 GHz.操作系統(tǒng)為Windows 10家庭版64位，8 GB內(nèi)存。實(shí)驗(yàn)工具為IntelliJ IDEA 2018.3.5、PyCharm 2018.2.3、Neo4j 3.5.16、Graph XRv2.2.1、Mysql 5.7以及MATLAB R2014a。

實(shí)驗(yàn)數(shù)據(jù)采用網(wǎng)絡(luò)爬取與隨機(jī)匹配相結(jié)合的方案，首先在ProgrammableWeb上爬取了600個RESTful API作為服務(wù)，在MATLAB上使用改進(jìn)的Salama網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法服務(wù)組合的網(wǎng)絡(luò)環(huán)境，構(gòu)造了102個服務(wù)組合，每個服務(wù)組合包含2-16個原子服務(wù)，將這些與Salama中的網(wǎng)絡(luò)進(jìn)行映射。每個服務(wù)都含有前述九元組的信息。

5.2 實(shí)驗(yàn)及結(jié)果分析

(1)實(shí)驗(yàn)一：功能驗(yàn)證

將構(gòu)造的102個服務(wù)組合節(jié)點(diǎn)和關(guān)系數(shù)據(jù)導(dǎo)出為CSV文件存儲。使用LoadCSV將上述節(jié)點(diǎn)和關(guān)系導(dǎo)入到Neo4j中，形成初始服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)，使用GraphXR進(jìn)行可視化，如圖6所示。首先使用深度優(yōu)先遍歷算法DFS對圖6進(jìn)行遍歷。獲得如圖7所示數(shù)據(jù)依賴圖，黃綠紅分別代表start、middle、end節(jié)點(diǎn)。藍(lán)色箭頭代表數(shù)據(jù)流的方向，兩端是擁有數(shù)據(jù)依賴關(guān)系的服務(wù)節(jié)點(diǎn)。然后使用Louvain算法對服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，結(jié)果如圖8所示。100個節(jié)點(diǎn)的服務(wù)網(wǎng)絡(luò)劃分為20個社區(qū)，并將每個服務(wù)所屬的社區(qū)號存儲回Community屬性中。最后就是對Louvain算法劃分出來的每個社區(qū)利用HFPGrowth算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘，得到控制依賴圖，合并數(shù)據(jù)依賴與控制依賴后的最終服務(wù)依賴圖如圖9所示。

(2)實(shí)驗(yàn)二：比較算法的執(zhí)行時間

在前述20個社區(qū)，分別使用HFPGrowth算法、Apriori算法、FPGrowth算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘，并比較算法執(zhí)行時間，選取支持度為4～9，這里的支持度考慮了總的數(shù)據(jù)量和實(shí)際數(shù)據(jù)參考的值，同時，每一種方法進(jìn)行10次實(shí)驗(yàn)，對10次實(shí)驗(yàn)結(jié)果的平均執(zhí)行時間進(jìn)行對比，結(jié)果如圖10所示，相比FPGrowth算法，改進(jìn)后的算法約有20%的運(yùn)行效率提升。

(3)實(shí)驗(yàn)三：比較算法結(jié)果

將Louvain+HFPGrowth組合算法、Apriori、FPGrowth三種算法在實(shí)驗(yàn)一構(gòu)造的服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)圖數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)，算法執(zhí)行結(jié)果如表2所示。在同樣的支持度下，Louvain+HFPGrowth的組合算法通過縮小范圍從而獲取符合服務(wù)依賴圖的有序的關(guān)聯(lián)規(guī)則項(xiàng)，有序的關(guān)聯(lián)規(guī)則在實(shí)際環(huán)境下更能真實(shí)的體現(xiàn)服務(wù)組合運(yùn)行過程中服務(wù)之間的執(zhí)行過程，而Apriori和FPGrowth算法則是獲得了很多無序等無用的關(guān)聯(lián)規(guī)則項(xiàng)。

表2 3種算法下的結(jié)果挖掘數(shù)量對比

6 結(jié)束語

服務(wù)依賴關(guān)系的挖掘分析是近幾年服務(wù)計(jì)算領(lǐng)域的研究熱點(diǎn)。本文提出一種基于服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)的服務(wù)依賴關(guān)系識別分析方法，首先利用有向圖刻畫服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)模型，探索了一種通過已有組合服務(wù)分析服務(wù)控制流和數(shù)據(jù)流并構(gòu)建服務(wù)關(guān)聯(lián)網(wǎng)絡(luò)的方法。利用圖遍歷算法、社區(qū)發(fā)現(xiàn)算法及改進(jìn)的HFPGrowth算法識別并抽取服務(wù)之間的數(shù)據(jù)依賴及控制依賴關(guān)系生成服務(wù)依賴圖，通過服務(wù)依賴圖實(shí)現(xiàn)服務(wù)依賴關(guān)系的識別。最后通過實(shí)驗(yàn)驗(yàn)證了方法的可行性和有效性，并通過與幾種經(jīng)典算法的對比分析驗(yàn)證方法的效率。

服務(wù)依賴關(guān)系不僅能夠支撐組合服務(wù)的劃分與分布部署執(zhí)行，還可以進(jìn)一步支撐組合服務(wù)的構(gòu)建、演化、以及組合服務(wù)的失效替換等。本文在這方面進(jìn)行了探索和嘗試。未來一方面擬結(jié)合服務(wù)鏈路執(zhí)行動態(tài)數(shù)據(jù)對服務(wù)依賴關(guān)系進(jìn)行修正與優(yōu)化，另一方面將與分布式引擎結(jié)合進(jìn)一步驗(yàn)證方法的有效性和執(zhí)行效率。