部分可觀測環境中的目標驅動服務導航機制

摘 要:遷移工作流的體系結構具有無中心性、動態性、松耦合等特征，如何在部分可觀測的環境下保證遷移工作流運行時不偏離全局目標是其中的技術難題之一。基于目標關聯度的決策思想，從對用戶的服務導航的角度對此問題進行了探討，提出一種部分可觀測環境下的目標驅動服務導航機制。該機制建立一種目標關聯策略描述規范，采用基于業務熟人推介的導航索實現方法，并給出一個目標驅動的服務導航算法。初步實踐表明，上述機制為開發遷移工作流平臺提供了有效支持。

關鍵詞:遷移工作流; 部分可觀測環境; 目標關聯; 業務熟人; 服務導航

中圖分類號:TP301文獻標志碼:A

文章編號:1001-3695(2009)09-3407-04

doi:10.3969/j.issn.1001-3695.2009.09.58

Goal-driven mechanism for services navigation in partially observe environments

WANG Tao1， WANG Rui1，2

(1. School of Information Management， Shandong Economic University， Jinan 250014， China; 2.School of Computer Science Technology， Shandong University， Jinan 250061， China)

Abstract:Migrating workflow has the non-center， dynamic， and loose coupling architecture. How to ensure the correctness of migrating workflows in the partially observe environment is one of the hard technique problems in this field. Based on the idea of goal relation， this paper proposed a goal-driven mechanism for services navigation to solve the problem from the aspect of service navigation. Firstly， proposed goal relation policy to express observable environments， secondly， gave a navigation cable formation based on business acquaintances and a goal-driven algorithm for services navigation. Some development examples show that this mechanism can support the development of the migrating workflows effectively.

Key words:migrating workflow; partially observe environment; goal relation; business acquaintances; services navigation

0 引言

遷移工作流(migrating workflow) 是近年來工作流管理研究的一個新方向[1， 2]，是在開放、異構動態環境下基于移動agent技術構造的具有松耦合特性的跨機構工作流系統。目前的研究[2， 3]是為移動agent內嵌顯式的業務過程說明，包含定義業務過程的活動、活動之間的轉移邏輯以及每一步活動所需要的資源和服務等，令移動agent清楚地知道每一步應該做什么和需要什么。然而，與傳統工作流運行環境不同，目前開放、動態的遷移工作流平臺具有如下特征:工作流管理系統的無中心性、運行環境的不完全可觀測性、工作位置節點的高度自治性、用戶實體需求的個性化和靈活性等，如何設計部分可觀測環境中移動agent的問題求解路徑不偏離全局目標成為當前的技術難點之一。

部分可觀測的遷移工作流環境中如果事先為移動agent編寫一個面向過程的工作流說明具有一定的局限性:a)工作流設計者在部分可觀測環境下預先知道完整的跨機構業務流程和所有參與機構的業務應用是不現實的;b)為移動agent預先定義嚴格步驟和控制邏輯，這將會使移動agent失去靈活性，難于應對工作流例外;c)工作流服務通常由多機構、跨地域的協作過程提供，考慮到機構自治與保護各自信息系統的原因，很難對多機構建立統一的工作流模型及中心化的工作流執行系統;d)用戶群體的開放性、多樣性以及環境的復雜性，使得工作流服務的開發不可能一蹴而就，應該具有在運行時刻動態調整以適應需求的能力。因此在部分可觀測的遷移工作流環境下，遷移工作流系統需要一種“主動”的機制來保障其可行性。

本文工作的主要切入點是從遷移工作流的基本元素“工作流服務”出發，使用關聯度分析的思想來探討此問題的解決途徑:在遷移工作流中的各個具有經常業務往來的工作位置組成業務熟人域的層次上，提出一種部分可觀測環境的目標驅動的服務導航機制(partially observable environment goal-driven mechanism for service navigation， POESN)。POESN以目標關聯為基礎進行決策，利用開放工作流環境中廣泛使用的協同概念及其相關技術，采用一種基于業務熟人推介的導航索形成機制，并通過一個目標驅動的服務導航算法促使導航主體為用戶推介滿足尋航目標的服務。

1 POESN: 部分可觀測環境中的目標驅動服務導航機制

本文所指的遷移工作流觀測環境是位于各工作位置的導航主體關于遷移工作流特定情形的描述信息。由于工作流的動態流程和需求變化過快，根據實際情況，導航主體只能對遷移工作流環境部分可觀測，主要包括工作流視圖和自己的業務熟人關系。導航主體通過分析其熟人協作者提供的業務目標是否與當前用戶的尋航目標有關聯關系是本文的工作基礎。對于工作流視圖中的工作流全局目標來說，由于不存在中心化的工作流管理引擎，每個導航主體的導航建議不能偏離工作流的目標，否則可能會對移動agent產生誤導。在給出目標驅動的服務導航機制之前，先來看一個遷移工作流系統實例:一個自助旅游服務系統。

如圖1所示，在遷移工作流環境中遷移實例(migrating instance)是指代表個人或機構遷移到工作位置(work place)執行工作流任務的移動agent。工作位置是指工作流參與機構，它由一個?？空痉掌骱腿舾蓚€與其相連的工作機網絡組成。?？空痉掌鳛檫w移實例提供運行時環境、運行時服務、工作流服務和導航服務。導航主體(navigation agent)位于工作位置上的停靠站服務器，根據部分可觀測的遷移工作流環境為遷移實例提供理性的行動建議。遷移實例不再需要預先攜帶完整的工作流程說明，它可以在工作進程中向工作位置提出尋航請求，然后依靠一個或多個導航主體提供的導航信息不斷地完善任務規劃，進而遷移到其他工作位置，最終完成其全部工作。導航主體的業務熟人(business acquaintance)是指導航主體了解其業務范圍和服務能力，并且建立了互相信任的業務關系的其他工作位置。導航主體的導航建議需要約束條件(constraints)加以限制。約束條件反映導航主體所提供導航建議時必須符合全局目標，用于約束和指導導航主體的導航行為。圖1 所示遷移實例是自助旅游的申請人;工作位置A是接受自助旅游申請的服務部門，其導航主體有三種類型的業務熟人域，即住宿業務熟人域、交通業務熟人域和保險業務熟人域。每類業務熟人域用于連接多個有相同目標范疇的工作位置。住宿、交通和保險的導航主體分別又有自己的業務熟人域。

首先，導航主體對能否接受尋航請求的判別主要從尋航目標ea.Sg與業務目標na.Bg的關聯性的角度進行。一個導航主體如果擁有的業務目標與尋航目標就有一定的關聯性，那么該導航主體就可以參與導航推介適合的工作位置。

定義1 目標關聯評價策略appraiseActivity，采用三個基于一階謂詞邏輯〈support， self-Confidence，relation〉，其中:

a)support，二元關系，用于評價業務熟人的業務目標na.Bg對尋航目標ea.Sg的支持程度，反映了這個關聯的有用性。

b)self-Confidence，二元關系，用于表達導航主體對其業務熟人na.Ba能力的確定程度，反映了這個關聯的確定性。

c)Relation，二元關系，用于表達熟人的業務目標na.Bg對實現尋航目標ea.Sg的關聯程度，是導航方案是否推介給用戶的重要標準。

d)目標關聯評價策略appraiseActivity

ea∈executeagent，na∈workPlace，

support(na.Bg，ea.Sg)self-Confidence(na，na.Ba)→relationt(na.Bg，ea.Sg)

根據目標關聯評價結果，導航主體可建立相應的導航索。導航索的準確性決定了服務導航的效果。在規劃導航索時，導航主體計算在其業務熟人關系范圍內各工作位置的服務目標與尋航目標的關聯度為輸入，故稱為基于業務熟人域的導航索形成機制，文獻[7]中對如何建立業務熟人域進行了一定的研究，本章將從導航主體的觀測角度進一步對業務熟人域進行分析。

定義2 業務熟人域(business acquaintance domain，BAD)是一個無向圖BAD=〈V，E〉。其中，V是導航主體的業務熟人域的節點集，每個節點表示一個工作位置的服務sBg.r。E是業務熟人域的邊集，滿足對任意的邊e(sBg.r11，s2Bg.r2)∈E表示服務s1、s2分別擔當業務目標Bg的不同角色r1、r2，且r1與r2之間有交互。本文假設一個服務在實現一個業務目標中只能擔任一個角色。

從業務熟人域的定義可知，工作位置中的一個服務可以充當企業熟人域中的不同節點，表示該服務可以擔當實現不同的業務目標的角色。此時，該服務提供的功能是不同的。另外，擔任同一業務目標的每個角色的服務可能有多個。本文稱參與業務目標Bg的這些服務構成了一個協作相對緊密的服務導航索。

定義3 實現業務目標Bg的服務導航索是業務熟人域BAD的一個子序列TBg =〈VBg，EBg〉。其中，EBgE是E中所有與業務目標Bg相關的邊構成的子集，VBgV是EBg中所有邊的頂點集合，即所有實現目標Bg的節點子集〈V1，V2，V3，…，Vn〉，其中V1出現在V2之前，V2出現在V3之前。

定義4 導航主體對于尋航目標Ng=(p1，p2，…，pn)和業務目標Bg=(p1， p2，…，pm) (pi為目標中所定義的屬性)進行觀測，以全局目標為約束，目標支持度為

s=same(Sg，Bg)/diff(Sg，Bg)-1(1)

其中:same(Sg，Bg)表示兩類目標中相同的屬性個數，diff(Sg，Bg)表示n+m個屬性中相異的屬性個數。

設定一個閾值S，對于目標關聯支持度大于S的均可視為導航主體的業務熟人的業務目標對尋航目標具有一定的支持性，由此得到一個與尋航目標相關的推薦信息集合ω。結合導航主體對推介的業務熟人的能力自信度，進行目標關聯度的計算式如下:

r2=∑ni=1∑mj=1(sij-scij)2/scij(2)

其中:sij是導航主體實際觀測到的業務目標對尋航目標的支持度;scij是導航主體關于其業務熟人能力自信度的計算，在文獻[4]中有詳細的論述。該公式配合觀測評估過程，能根據目標支持相關信息(觀測值s)，從當前的業務熟人域得到較為準確的與尋航目標有關聯關系的特定業務熟人。

2 目標驅動的服務導航算法

基于該目標關聯度公式，給出基于目標驅動的服務導航算法進行決策，由導航主體的智能模塊執行。算法分為兩個階段: 初始化階段和規劃階段。初始化階段為每個待選業務熟人分配一個能力自信度初值，其僅在系統部署的時候運行一次;規劃階段在每次接收到尋航請求時調用，以選擇關聯度最高的業務熟人參與導航索。該算法在最壞情況下的時間復雜度為O(n×m)(n為候選業務熟人的數量，m為尋航目標中的屬性個數)，但是一次調用成功率的提高可大大提高算法效率。關聯值的準確程度將決定一次調用成功率的高低，因此，算法的實際性能依賴于導航索形成和關聯度計算機制。第3章將通過應用實例分析上述導航索形成及服務導航算法在實際應用中的有效性。

1)Initialization stage

for each business acquaintance of navigation agent

construste(acquaintance domain);

//組織業務熟人建立候選熟人域

in the acquaintance domain

set index on sc descending; //按能力自信度降序排序

creat navigation_tree

2)Running stage

creat navigation_cable(1)

// 創建導航索，初始為1

wait until a navigation requirement Ng arrive;

(is_desired_state)=unsat;

do

{/*選取自信度最高的業務熟人進行分析，若多個候選者自信度相同則隨機選取一個*/

calculate support(Sg，Bg);

if (support(Sg，Bg)

//將小于支持度閾值的業務熟人移入失敗列表

remove the acquaintance to the fail_list;

//失敗列表中的業務熟人在當前服務導航中將不再被推介

else

{is_desired_ state=sat;

calculate relation(Sg，Bg);

// 計算目標關聯度

if (relation(Sg，Bg)

//檢測關聯度是否小于閾值

{update the self confidence;

//更新能力自信度

insert_cable(ba， navigation_cable) ;

//將滿足條件的業務熟人插入的導航索中

}

}while ((is_desired_ state)==unsat or (acquaintance domain !=fail_list));

if (is_desired_result=sat)

return (navigation_cable);

else

return (exception);

3 應用實例分析:一個自助旅游服務系統

基于POESN，本文實現了圖1的自助旅游服務系統中的服務導航功能。工作位置A是接受自助旅游申請的服務部門，其導航主體有12種類型的業務熟人域，即住宿業務熟人域、票務業務熟人域和保險業務熟人域等，每類業務熟人域用于連接多個有相同目標范疇的工作位置。住宿、交通和保險的導航主體分別又有自己的業務熟人域，總共包括50個服務。圖2記錄了當遷移工作流系統中業務服務增加，遷移實例通過其實現需求的時間變化規律。圖3記錄了當工作位置提供的服務達到30個時，隨著遷移實例需求數量的變化，遷移實例通過其實現全部需求的時間變化規律。

圖2顯示了遷移實例采用導航主體基于業務熟人域推薦的工作位置實現需求目標所花費的時間比其他兩種方法的時間少且比較穩定。這是因為自助旅游導航主體在業務熟人域范圍內尋找可以推薦給遷移實例的工作位置，與多個工作位置主體建立聯盟的方法相比，這種方法可以在更信任的基礎上在更小范圍內為用戶推薦服務，從而使遷移實例行動建議的時間減少，而直接在單個工作位置上發現適合的服務會隨著需求數量的增加而線性增長。

圖3顯示了當導航主體的業務熟人域達到一定狀態后，遷移實例采用推薦的工作位置實現需求目標所花費的時間比其他兩種方法的時間少且比較穩定。當業務需求目標達到5個以上，時間增長的幅度比較緩慢，并且之后的增長也趨于穩定。這是因為導航主體雖然在系統的運行初期基于業務熟人域的方法需要一定的學習時間，隨著業務需求目標的增長，與遷移實例交互過程獲得穩定的域拓撲結構;在業務熟人關系形成后，該機制可最大限度地提高一次推薦成功速度，從而提升系統性能。

自助旅游服務系統的相關數據驗證了POESN機制的有效性。該機制在系統的運行初期需要一定的學習時間以獲得業務熟人的對目標關聯度相關信息，在本例中，此段時間約為8～10次服務導航。在業務熟人關系形成后，該機制可最大限度地提高一次導航成功率，從而提升系統性能。服務工作位置的業務目標與導航目標的關聯度的形成與初始狀態無關，僅依于遷移工作流環境的變化，具有一定的通用性。

4 相關工作比較

相關工作涉及以下幾個方面:在工作流流程說明方面， Cichocki等人[5]研究不完善定義的工作流，依照過程邏輯與任務執行方法相分離的原則，假定遷移實例攜帶一個預先定義好的業務過程說明，而把任務執行方法留給基于broker的服務發現。本文通過工作位置上的導航主體為尋航的遷移實例提供的服務建議可以使遷移實例具備任務規劃層次上的主動性，在更大程度上支持智能主體的概念。在環境感知方面，Wynn等人[6]提出的“不變式”適配對大量動態、甚至不精確的數據的檢測、分析做了一定的工作。本文則主要在協同方式層次上，探討了一種基于業務熟人關系的環境觀測范圍，被推介的熟人仍然可以推介自己的熟人，并由此構成一個動態的業務熟人域，具有一定的通用性，可適用于部分可觀測的環境。在目標驅動研究方面，Browne等人[7]提出了一個簡單的目標分解模型，并給出了相關的數學處理方法;auto-configuration模型則能夠推薦一個適時的系統服務配置，其局限在于僅能利用肯定信息[8]。這些模型討論了分布式環境下目標驅動的計算技術，但在適用性、有效性、可操作性方面存在一定的局限性，不適用于遷移工作流軟件系統的開發。結合遷移工作流環境部分可觀測的特點，本文在相關工作[4， 9， 10]的基礎上給出了一套適用的基于目標關聯分析的導航索形成與決策技術，以此建立一種業務過程可部分定義的工作流方法。該方法支持遷移實例在業務熟人鏈(網)提供的工作位置上，攜帶不完善的業務過程定義首先啟動工作，然后通過學習工作流參與者提供的導航建議和面向工作流目標的決策，遷移到一個合適的工作位置上繼續就地利用工作流服務執行任務，直至全部流程結束。

5 結束語

POESN將傳統的顯式的工作流業務過程定義隱式地分布于導航建議中，在一定程度上解決了業務過程不完全定義的工作流出現工作流例外的問題。主要工作包括:a)基于一階謂詞邏輯給出了目標關聯分析策略的描述機制;b)給出一個有效的導航索形成機制和一個目標驅動的服務導航算法;c)通過具體的開發實例，初步驗證了POESN的有效性。POESN使得遷移工作流的服務導航有了相應的模型及方法支持，初步解決了在部分可觀測環境中遷移實例工作位置的導航問題。進一步的工作包括:如何高效準確地收集相關目標支持度信息;如何在導航之后確保業務熟人域在語義和功能上的正確性;將本文工作進一步應用于大型系統的開發等。

參考文獻:

[1]WANG Jia-cun， ROSCA D. Dynamic workflow modeling and verification[C]//Lecture Notes in Computer Science. Berlin:Springer， 2006:303-311.

[2]FENG Yu-hong， CAI Wen-tong， CAO Jian-nong. Dynamic partner identification in mobile agent-based distributed job workflow execution[J]. Journal of Parallel and Distributed Computing， 2007，67(11):1137-1154.

[3]武剛， 馮玉強， 劉春杰. 科技項目在線協同評審工作流系統設計與實現[J]. 計算機應用研究， 2007， 24(6):224-226.

[4]曾廣周， 楊公平， 王曉琳. 基于agent 能力自信度的任務分配問題研究[J]. 計算機學報， 2007，30(11): 1922-1929.

[5]CICHOCKI A， RUSINKIEWICZ M. Providing transactional properties for migrating workflows[J]. Mobile Networks and Applications， 2004， 9(5): 473-480.

[6]WYNN M T， AALST W M P van der， HOFSTEDEAHM T， et al. Verifying workflows with cancellation regions and OR-joins: an approach based on invariants[C]//Lecture Notes in Computer Science. Berlin: Springer， 2006:389-394.

[7]BROWNE E， SCHREFL M. A two tier， goal-driven workflow model for the healthcare domain[C]//Proc of the 5th International Confe-rence on Enterprise Information Systems. 2003:32-39.

[8]GILLMANN M， WEISSENFELS J， SHEGALOV G， et al. A goal-dri-ven auto-configuration tool for the distributed workflow management system mentorlite[J]. ACM SIGMOD Record， 2000， 29(2):595-601.

[9]WANG R， ZENG G. Active service in migrating workflow system[C]//Proc of the 3rd International Conference on Natural Computation. 2007: 249-253.

[10]曾廣周，黨妍. 基于移動計算范型的遷移工作流研究[J]. 計算機學報， 2003， 26(10): 1343-1349.