基于生物網(wǎng)絡(luò)的ｅ－ｓｅｒｖｉｃｅ自進(jìn)化組合方法研究

摘要：借鑒生物神經(jīng)內(nèi)分泌和免疫系統(tǒng)的自進(jìn)化突現(xiàn)機(jī)制，基于生物網(wǎng)絡(luò)的平臺(tái)提出了e－service突現(xiàn)的組合方法。生物實(shí)體(具有免疫行為的移動(dòng)agent)代理e－service，構(gòu)成為一個(gè)帶有條件米蘭機(jī)單元，e－service組合可以轉(zhuǎn)換為米蘭機(jī)演化過(guò)程。生物實(shí)體通過(guò)消息匹配和條件約束形成網(wǎng)絡(luò)，e－service組合是由突現(xiàn)形成的生物實(shí)體網(wǎng)絡(luò)提供；服務(wù)突現(xiàn)可以動(dòng)態(tài)調(diào)整其中的服務(wù)，自組織完成服務(wù)的動(dòng)態(tài)組合和管理等工作。仿真結(jié)果表明該方法具有對(duì)動(dòng)態(tài)環(huán)境變化的適應(yīng)性。

關(guān)鍵詞：生物網(wǎng)絡(luò); 突現(xiàn); 米蘭機(jī); 親合力

中圖分類號(hào)：TP18; TP39文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)04－0999－04

E－service是一種自描述、平臺(tái)無(wú)關(guān)的計(jì)算元素，正在受到廣泛的關(guān)注。它真正的潛力在于可以對(duì)簡(jiǎn)單服務(wù)進(jìn)行組合，但因?yàn)槠鋸?fù)雜性，存在著大量的更新、移動(dòng)等動(dòng)態(tài)變化及行為交互，多數(shù)已有的研究并沒(méi)有完全解決這個(gè)問(wèn)題[1]。語(yǔ)義，特別是本體的提出，為e－service的自動(dòng)發(fā)現(xiàn)、合成提供了一種新的思想。在語(yǔ)義服務(wù)的方式下，服務(wù)的發(fā)現(xiàn)、執(zhí)行和合成不需要由人來(lái)完成，而是可以由agent自動(dòng)完成用戶提出的復(fù)雜任務(wù)要求。

下一代互聯(lián)網(wǎng)和服務(wù)計(jì)算框架[1]研究指出：未來(lái)的服務(wù)存在著服務(wù)訪問(wèn)控制的分布性、自動(dòng)的控制策略、服務(wù)變化的自適應(yīng)、自進(jìn)化等主要特征。利用agent自主性設(shè)計(jì)符合這種特征的服務(wù)組合方法正在受到廣泛的重視[2]，但存在著agent的通信、協(xié)商、產(chǎn)生、消亡、遷移、穩(wěn)定性等問(wèn)題。對(duì)e－service組合如何實(shí)現(xiàn)新的管理框架是當(dāng)前要解決的問(wèn)題。

服務(wù)管理和組合的一個(gè)有益借鑒來(lái)自同為復(fù)雜巨系統(tǒng)的生物組織系統(tǒng)。通過(guò)細(xì)胞因子和受體組成生物網(wǎng)絡(luò)通用語(yǔ)言，免疫系統(tǒng)和神經(jīng)內(nèi)分泌系統(tǒng)構(gòu)成了自組織、自協(xié)作的分布服務(wù)網(wǎng)絡(luò)[3]。免疫系統(tǒng)通過(guò)免疫單元的合作形成免疫突現(xiàn)來(lái)清除外來(lái)抗原（即病原體），神經(jīng)內(nèi)分泌系統(tǒng)感知免疫變化，通過(guò)復(fù)雜的調(diào)節(jié)機(jī)制使系統(tǒng)達(dá)到一個(gè)穩(wěn)定、動(dòng)態(tài)平衡的狀態(tài)。突現(xiàn)是指生物個(gè)體遵循一組簡(jiǎn)單的行為規(guī)則，而一群個(gè)體組合則展示復(fù)雜的整體行為。生物突現(xiàn)表現(xiàn)出的重要特性有自組織、聚集現(xiàn)象和協(xié)作行為，它的許多特性可被用于Internet網(wǎng)絡(luò)服務(wù)與應(yīng)用。

受生物組織智能的突現(xiàn)機(jī)制啟發(fā)，本文給出e－service組合問(wèn)題的基于帶條件米蘭機(jī)的全局演化模型。在生物網(wǎng)絡(luò)計(jì)算框架[4~7]研究的基礎(chǔ)上，將生物實(shí)體（帶有生物功能設(shè)計(jì)的移動(dòng)agent）作為自動(dòng)機(jī)單元，通過(guò)消息匹配能力(這里稱為親合力，即由服務(wù)需求的匹配強(qiáng)度、服務(wù)質(zhì)量相對(duì)評(píng)定和服務(wù)信任因素組成的綜合評(píng)定值)和條件約束，建立滿足用戶要求的e－service組合演化過(guò)程，通過(guò)演化建立實(shí)體網(wǎng)絡(luò)，完成服務(wù)的組合。

仿真表明這種方法具有良好的性能和對(duì)環(huán)境的適應(yīng)性。

1E－service組合的米蘭機(jī)模型

E－service是一個(gè)有狀態(tài)的動(dòng)作序列，可以看做一個(gè)七元組：

B1=(U，Y，Q，s0i，δi，F(xiàn)i，QC)

其中：U是一系列e－service的輸入消息集合；Y是一系列e－service的輸出消息集合；Q是一系列e－service的有限狀態(tài)集（狀態(tài)表示e－service交互序列中的歷史記錄和條件判斷記錄）;s0i是起始狀態(tài)；δ1:Q×U×Y×QC→Q是一個(gè)轉(zhuǎn)移函數(shù)，即給定狀態(tài)根據(jù)輸入/輸出匹配和條件，F(xiàn)AS可以轉(zhuǎn)移到另一個(gè)狀態(tài)，U×Y是字母表；Fi∈Q是一系列服務(wù)的接收有限狀態(tài)集，即用戶能夠與e－service結(jié)束交互的狀態(tài)集；QC:Q×C是一系列條件集合。

在語(yǔ)義服務(wù)環(huán)境中，e－service信息描述采用OWL－S本體語(yǔ)言，服務(wù)的內(nèi)容由service profile類功能屬性和非功能屬性兩部分組成，實(shí)現(xiàn)了功能和屬性、質(zhì)量參數(shù)的描述。服務(wù)的組合可以轉(zhuǎn)換為語(yǔ)義支持下的e－service米蘭機(jī)演化過(guò)程。用戶的e－service請(qǐng)求可以描述為一個(gè)抽象OWL－S定義形式。OWL－S的過(guò)程模型包括sequence、split、split+join、choice、unordered、if－then－else、repeat－while和repeat－until結(jié)構(gòu)。這些結(jié)構(gòu)可以映射到自動(dòng)機(jī)的過(guò)程，即可以通過(guò)自動(dòng)機(jī)的演化滿足用戶的服務(wù)需求[8]。E－service的組合是一種基于消息的會(huì)話及匹配關(guān)聯(lián)的過(guò)程，服務(wù)組合是封閉的（組合的服務(wù)仍然是一個(gè)米蘭機(jī)），可以通過(guò)消息會(huì)話完成更高層次的組合。

2基于生物網(wǎng)絡(luò)平臺(tái)的e－service突現(xiàn)方法

在生物網(wǎng)絡(luò)平臺(tái)上[4~7]借鑒米蘭機(jī)的模型，生物實(shí)體（移動(dòng)agent)代理e－service， 可以描述為米蘭機(jī)。 每個(gè)生物實(shí)體有消息匹配接口，接口中含有e－service的相關(guān)信息，同時(shí)接收用戶服務(wù)請(qǐng)求進(jìn)行匹配。它通過(guò)特定演化規(guī)則完成e－service突現(xiàn)的組合方法，實(shí)現(xiàn)了自組織和自進(jìn)化的功能。按照這種方式，組合模式轉(zhuǎn)換為agent之間的匹配和動(dòng)態(tài)管理問(wèn)題。

2．1生物實(shí)體的結(jié)構(gòu)

生物實(shí)體是一種自治的移動(dòng)agent，用于代理e－service與完成突現(xiàn)應(yīng)用。生物實(shí)體由屬性、行為和功能組成，如圖1[6，7]所示。屬性描述關(guān)于生物實(shí)體的信息，包括全局標(biāo)志、代理服務(wù)狀態(tài)、能量、過(guò)程狀態(tài)和突現(xiàn)所屬標(biāo)志；行為實(shí)現(xiàn)相關(guān)操作，包括能量交換、生物（遷移、死亡、復(fù)制/再生等）、信息發(fā)布、數(shù)據(jù)接口操作；功能實(shí)現(xiàn)生物實(shí)體代理的服務(wù)運(yùn)算，包括與服務(wù)相關(guān)的處理操作。生物實(shí)體是網(wǎng)絡(luò)應(yīng)用中的最小組件，是一個(gè)能量驅(qū)動(dòng)的服務(wù)單元。它可以接收服務(wù)請(qǐng)求消息，通過(guò)消息匹配方法完成服務(wù)序列演化構(gòu)建。

生物網(wǎng)絡(luò)實(shí)體采用基于RMI－IIOP技術(shù)的生物網(wǎng)絡(luò)通信架構(gòu)來(lái)傳送具有生物實(shí)體語(yǔ)義的BNCL語(yǔ)言消息。重用FIPA ACL的部分通信動(dòng)作（request、agree、refuse、not－understand、inform、failure、query－ref、query－if）。根據(jù)生物網(wǎng)絡(luò)中服務(wù)內(nèi)容的需要，BNCL定義了一些新的通信動(dòng)作，如defray（支付能量給一個(gè)提供服務(wù)的生物實(shí)體）、advertise（向鄰近的實(shí)體通報(bào)自己的服務(wù)數(shù)據(jù)、實(shí)體提供的信息等，將實(shí)體加入到生存環(huán)境中）等。

2．2生物實(shí)體的消息匹配與算法 

生物實(shí)體代理e－service，它能觀察其他實(shí)體的輸入、輸出動(dòng)作(即接收到的消息)。在觀察的基礎(chǔ)上，根據(jù)用戶需求的描述，通過(guò)匹配算法驅(qū)動(dòng)其演化，構(gòu)造一個(gè)可接受的協(xié)作行為序列。對(duì)于實(shí)體間的消息匹配和規(guī)則，本文采用了多元綜合評(píng)估的方式，即對(duì)三個(gè)主要消息匹配的影響因素進(jìn)行綜合度量，根據(jù)親合力的強(qiáng)度，選擇親合力匹配最大的實(shí)體組成網(wǎng)絡(luò)。服務(wù)突現(xiàn)是一系列實(shí)體通過(guò)最強(qiáng)匹配演化組合的群體。親合力測(cè)量的影響因素（圖2）有服務(wù)消息的匹配強(qiáng)度、服務(wù)相對(duì)質(zhì)量和服務(wù)的信任關(guān)系度量。根據(jù)匹配強(qiáng)度的關(guān)系，服務(wù)突現(xiàn)可以調(diào)整生物實(shí)體，即實(shí)體的自然選擇。

消息匹配強(qiáng)度的計(jì)算是一個(gè)綜合評(píng)定指標(biāo)。下面給出三個(gè)影響參數(shù)值及親合力值的計(jì)算方法。

a）服務(wù)需求的匹配強(qiáng)度定義為代理的e－service匹配消息請(qǐng)求的能力，表示為MSWSbio－entity。設(shè)WS為實(shí)體代理的e－service，WM為上一個(gè)實(shí)體服務(wù)的輸出消息，其匹配能力MSWSbio－entity(WM，WS)的計(jì)算由WM和WS的接口概念匹配度決定。進(jìn)一步表示為WMWnM(C1，C2，…，Ci)和WSWS(C′1，C′2，C′3，…，C′j)。其中：Ci和C′j分別代表組成消息接口服務(wù)描述的相關(guān)概念。 

為了計(jì)算匹配能力，這里首先給出概念相似度[8]SM(C1，C2)的計(jì)算公式為

通過(guò)上述規(guī)范化處理，服務(wù)相對(duì)質(zhì)量Sbio－entity(si)被限定在[0，1]。其值越趨近1，說(shuō)明服務(wù)相對(duì)質(zhì)量越高。

c）服務(wù)信任的度量。基于信任的關(guān)系重構(gòu)是為下一次更加有效的搜索和突現(xiàn)作準(zhǔn)備。這種機(jī)制通過(guò)建立和改變生物服務(wù)實(shí)體之間的trust值來(lái)更新和加強(qiáng)親合力網(wǎng)絡(luò)。服務(wù)突現(xiàn)完成后，突現(xiàn)的使用者將返回一個(gè)支付(defray)消息，該消息包括一個(gè)協(xié)作記錄、一個(gè)表示用戶對(duì)請(qǐng)求命中的評(píng)價(jià)值R。R值可以是一個(gè)獎(jiǎng)勵(lì)，也可以是一個(gè)懲罰，它表示用戶對(duì)接收到的請(qǐng)求命中的偏愛(ài)程度。這個(gè)消息沿著開(kāi)始傳遞的路徑被傳播，它將調(diào)節(jié)被用來(lái)傳遞初始發(fā)現(xiàn)請(qǐng)求關(guān)系的trust值。作為獎(jiǎng)勵(lì)時(shí)，trust值增加;作為懲罰時(shí)，trust值減少。計(jì)算公式如下：

3仿真結(jié)果及性能分析

3．1仿真設(shè)計(jì)

E－service突現(xiàn)方法的仿真基于生物網(wǎng)絡(luò)平臺(tái)上進(jìn)行。生物網(wǎng)絡(luò)平臺(tái)設(shè)計(jì)了Java 編寫(xiě)的軟件接口、公用結(jié)構(gòu)體、仿真器，并支持即插即用和靈活的API操作，仿真對(duì)原平臺(tái)增加了服務(wù)數(shù)據(jù)接口處理和親合力計(jì)算功能，實(shí)現(xiàn)了e－service突現(xiàn)的仿真操作。由于沒(méi)有標(biāo)準(zhǔn)的測(cè)試數(shù)據(jù)集，本文采用隨機(jī)生成的e－service之間的消息匹配度數(shù)據(jù)集和服務(wù)質(zhì)量的數(shù)據(jù)集。同時(shí)為了簡(jiǎn)化運(yùn)算， 對(duì)trustij作如下規(guī)定: 沒(méi)有信任關(guān)系的備選服務(wù)，當(dāng)消息匹配強(qiáng)度Affbio－entity≥θ和Sbio－entity(sj)＞Sbio－entity(si)時(shí)，初值規(guī)定為1；否則為0。本文生成了包含1 000個(gè)不同資源的多數(shù)據(jù)集，隨機(jī)抽取了100、200、300、400、500個(gè)服務(wù)來(lái)評(píng)價(jià)方法性能，將生成的測(cè)試數(shù)據(jù)分配給生物實(shí)體，用來(lái)測(cè)試系統(tǒng)的突現(xiàn)服務(wù)特性。仿真主要討論這種自進(jìn)化方法的性能、自適應(yīng)性和抗毀性。

本仿真實(shí)驗(yàn)采用了Pentium 4處理器 （2．4 GHz和512 MB RAM）的計(jì)算機(jī)，實(shí)驗(yàn)設(shè)置具有432個(gè)（18×24）節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)。假設(shè)每個(gè)虛擬機(jī)的網(wǎng)絡(luò)節(jié)點(diǎn)上都運(yùn)行有仿真平臺(tái)，網(wǎng)絡(luò)平臺(tái)上的資源花費(fèi)能量相同。訪問(wèn)的服務(wù)請(qǐng)求頻率不隨時(shí)間變化，設(shè)定用戶的網(wǎng)絡(luò)服務(wù)需求是10次/s。系統(tǒng)設(shè)置為生物實(shí)體能量為10 000，節(jié)點(diǎn)時(shí)延遲為0．01 s，仿真時(shí)間為100 min。

仿真中對(duì)自進(jìn)化e－service突現(xiàn)性能的影響因素有多個(gè)方面，這里主要以消息匹配的親合力權(quán)重系數(shù)α(α=0，0．5，0．8，1)和閾值θ(θ=0．6，0．7，0．8，0．9，1．0)的變化來(lái)討論系統(tǒng)的性能和適應(yīng)性。評(píng)估主要是以下三個(gè)方面：服務(wù)突現(xiàn)的響應(yīng)時(shí)間、每次服務(wù)突現(xiàn)的跳數(shù)和自適應(yīng)值。實(shí)驗(yàn)重復(fù)了多次，最終結(jié)果為測(cè)量平均值。

3．2結(jié)果和分析

服務(wù)響應(yīng)時(shí)間和每次服務(wù)請(qǐng)求的跳數(shù)分別是e－service突現(xiàn)質(zhì)量、費(fèi)用評(píng)定的主要指標(biāo)。第一個(gè)實(shí)驗(yàn)仿真分析方法的適應(yīng)性。這里設(shè)置閾值θ＝0．8，生物實(shí)體為200個(gè)。為了對(duì)比突現(xiàn)方法的性能，特別設(shè)計(jì)了隨機(jī)非生物實(shí)體（不帶生物功能的移動(dòng)agent）的情況與α（α=0，0．5，0．8，1）的對(duì)比數(shù)據(jù)。由仿真結(jié)果（圖3）可以看出，非生物實(shí)體響應(yīng)時(shí)間參數(shù)的趨勢(shì)沒(méi)有變化。生物實(shí)體的相應(yīng)數(shù)據(jù)在最初數(shù)據(jù)較高，達(dá)到700 ms；在20 min以后，數(shù)據(jù)指標(biāo)開(kāi)始下降至300~400 ms。這是因?yàn)樯飳?shí)體在開(kāi)始階段要建立相應(yīng)的親合力關(guān)系，許多資源和時(shí)間浪費(fèi)在盲目的尋找上。 同時(shí)開(kāi)始時(shí)生物操作要存儲(chǔ)能量，進(jìn)行遷移、變異和交叉等生物操作以完成突現(xiàn)服務(wù)。隨著時(shí)間的推移，生物實(shí)體形成了關(guān)系的聚類， 很快響應(yīng)提供服務(wù)，費(fèi)用也變小了。同時(shí)可以看到，α為0．5，反應(yīng)時(shí)間最少。對(duì)服務(wù)突現(xiàn)跳數(shù)的數(shù)據(jù)分析也可得到同樣的結(jié)論。以上仿真實(shí)驗(yàn)結(jié)果表明，e－service突現(xiàn)模型自適應(yīng)、自進(jìn)化地滿足用戶的需求，生物實(shí)體關(guān)系網(wǎng)絡(luò)所構(gòu)建的e－service突現(xiàn)方法具有自適應(yīng)、自進(jìn)化等功能特點(diǎn)。

第二個(gè)仿真實(shí)驗(yàn)是服務(wù)突現(xiàn)的成功率隨θ和α的變化情況（表2）。仿真分別設(shè)置了α(α=0，0．5，0．8，1)和閾值(θ=0．6，0．7，0．8，0．9，1．0)。當(dāng)閾值較小時(shí)，α的變化對(duì)成功率影響很小；隨著閾值增加，α的變化影響變大， 系統(tǒng)的信任關(guān)系起到了很大作用。α為0時(shí)，系統(tǒng)擁有較高的成功率，但從前面的仿真數(shù)據(jù)可以看出，其費(fèi)用也較高。本實(shí)驗(yàn)數(shù)據(jù)表明，α的正確選擇加強(qiáng)了信任關(guān)系的反饋和調(diào)節(jié)，對(duì)系統(tǒng)的性能起到了提高的作用。

第三個(gè)仿真實(shí)驗(yàn)是考慮在服務(wù)計(jì)算環(huán)境中，服務(wù)和網(wǎng)絡(luò)很有可能變得不可靠(即不能發(fā)揮資源發(fā)現(xiàn)的作用)。本文仿真了這種環(huán)境下發(fā)現(xiàn)方法的自適應(yīng)性和抗毀性。本文選用了與圖3相同的仿真設(shè)置來(lái)進(jìn)行比較實(shí)驗(yàn)。在該實(shí)驗(yàn)信息服務(wù)中，筆者隨機(jī)選擇1%的信息服務(wù)生物實(shí)體和1%網(wǎng)絡(luò)節(jié)點(diǎn)并將它們?cè)O(shè)置為不可靠，設(shè)計(jì)了一個(gè)評(píng)估指標(biāo)自適應(yīng)性D(可靠和不可靠狀態(tài)情況下，響應(yīng)時(shí)間的相對(duì)值)來(lái)評(píng)估e－service突現(xiàn)方法的特性:

4結(jié)束語(yǔ)

E－service是一個(gè)正在迅速發(fā)展的研究領(lǐng)域，服務(wù)動(dòng)態(tài)管理復(fù)雜性的特點(diǎn)與生物系統(tǒng)相似。本文在研究生物智能的基礎(chǔ)上給出e－service組合問(wèn)題的基于帶條件米蘭機(jī)的全局演化模

型。借鑒突現(xiàn)機(jī)理，結(jié)合agent、e－service、語(yǔ)義的有關(guān)原理，設(shè)計(jì)

了面向e－service突現(xiàn)進(jìn)化的智能模型，利用生物實(shí)體消息匹配的親合力構(gòu)成關(guān)系網(wǎng)絡(luò)。仿真的良好特性顯示這種方法可以為下一代e－service動(dòng)態(tài)合成、自進(jìn)化適應(yīng)等設(shè)計(jì)提供一種新穎的研究途徑和思路。其進(jìn)一步的工作是擴(kuò)充e－service突現(xiàn)方法的功能模塊，完善智能管理調(diào)節(jié)設(shè)計(jì)，進(jìn)行更詳細(xì)的仿真設(shè)計(jì)，同時(shí)提高系統(tǒng)的并行效率和語(yǔ)義匹配效率，探討其在復(fù)雜系統(tǒng)中的應(yīng)用。

參考文獻(xiàn)：

[1]BULTAN T， FU Xiang， HULL R， et al. Conversation specification: a new approach to design and analysis of e－service composition[C]//Proc of the 12th International WWW Conference. Budapest， Hungary:[s.n.]， 2003:403－410.

[2]ZHUGE Hai. The future interconnection environment[J]. IEEE Computer， 2005，38(4):27－33.

[3]VARGAS P A， MOIOLI R， DeCASTRO L N， et al. Artificial homeostatic system: a novel approach advances in artificial life[C]//Proc of the 8th European Conference. Canterbury:[s.n.]， 2005:754－764.

[4]丁永生，任立紅.一種基于免疫突現(xiàn)計(jì)算的生物網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)[J].控制與決策，2003，18(2):185－189.

[5]GAO Lei， DING Yong－sheng， YING Hao. An adaptive social network－inspired approach to resource discovery for the complex grid systems[J]. Int J of General Systems， 2006，35(3):347－360.

[6]GAO Lei， DING Yong－sheng， REN Li－h(huán)ong. A novel ecological network－based computation platform as grid middleware system[J]. Int J Intelligent Systems， 2004，19(10):859－884.

[7]SUN Hong－bin， DING Yong－sheng， HAO Kuang－rong. Web service emergent system based on mechanism of bio－systemic intelligence[J]. Dynamics of Continuous Discrete and Impulsive Systems Series B: Applications Algorithms， 2006，13(s):6－10.

[8]BERARDI D， GIACOMO G D， LENZERINI M， et al. Synthesis of underspecified composite e－services based on automated reasoning[C]//Proc of the 2nd International Conference on Service Oriented Computing. New York: ACM Press， 2004:105－114.

[9]CARDOSO J， SHETH A. Semantic e－workflow composition[J]. Intelligent Information Systems， 2003，21(3):91－225.

[10]ZENG L Z， BENATALLAH B， NGU A H H， et al. QoS－aware middleware for services composition[J]. IEEE Trans on Software Engineering， 2004，30(5):311－327.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”