第２８卷第５期
２０１１年５月
計算機應用與軟體
ｍａｖ ２０１１
一種基於事件驅動的ｓｏａ故障疑似集選擇演算法
李晶朱敏
（華東師範大學計算中心
上海２０００６２）
摘要面向服務體系架構（ｓｏａ）的靈活性和動態性，使得監測和管理執行時服務行為成為效能保證的關鍵所在。依據貝葉斯
故障診斷網路提出了一種基於事件驅動的ｓｏａ故障疑似集選擇演算法，該演算法綜合貝葉斯敏感性分析技術以及ｋ－ｍｅｄｉａｎ模型，並加入故障標識集，根據具體的故障事件選擇對應的故障疑似集合。**實驗表明，該演算法具有較高
的故障疑似集查詢完整率。增加的故障標識集也有利於以後的**性分析。
關鍵詞故障診斷貝葉斯網路模型事件驅動
收集個體服務的狀態資訊，其中個體服務還可分為更加具體的
０ 引言
面向服務被認為是設計、實施和部署大規模服務**軟體
服務，並且具有自己的**。當錯誤被檢測到時，**將這些信
息傳送給
系統的重要技術之一。通過使用ｓｏａ，企業系統可以定義和執
行分布式、跨多重服務領域的服務…。ｓｏａ的靈活性和動態性，也使得對其執行時服務行為的監管，成為系統效能保證至關重要的一方面。乙個複雜的ｓｏａ系統中，乙個商業流程可能有上百個服務，而這些商業流程的例項又可能會同時執行。
如果蒐集和分析所有服務節點的執行時資料，會對執行時間產生很大的管理負擔。而蒐集太少的資料又會影響診斷結果的準確
性。針對這種情況，本文使用問責制框架作為綜合的ｓｏａ部署和管理方案的一部分，並改進ｙｕｅ ｚｈａｎｇ等人的ｅｃｓ（ｅｖｉ—
演算法 ，提出了綜合具體故障標識ｅ的故障疑似集選擇（ｆｓｓ）演算法，為故障診斷提供最優化的故障疑似集。
』圖１問責制框架系統架構
１ 問責制管理框架與貝葉斯網路模型
１．１問責制管理框架
本文選用問責制框架作為ｓｏａ中ｑｏｓ管理框架，其結構如圖１所示。問責制框架包括責任監管者與責任**，在服務流程部署的邏輯流中，觀察和報告執行時異常。服務**監視和
服務流程部署包括服務網路規劃、基於ｑｏｓ的服務選擇、
服務流程的執行和信譽網路的細化。問責制機制具體實現於服務流程的執行，通過幾個功能子步驟來達到問責制的目標。子
步驟包括**部署、故障疑似集選擇、貝葉斯網路診斷和業務網
收稿日期李晶（ｃｃｆ會員碩士主研領域：現代軟體技術。
ｌ８２絡恢復，流程如圖２所示。
計算機應用與軟體２０１１生
ｐｅ（ｕ，．ｓ）＝一
如果ｐ＝０，則即ｐｅ（ｕ，ｓ）測量了ｓ被ｕ分享的資訊量，如果知道 ，則ｓ的不確定性程度就會減小。ｐｅ（ｕ，ｊｓ）的值越小，ｕ包含了越多有關ｓ的資訊。如果ｓ和ｕ相互獨立，則ｕ不包含任何關於ｓ的資訊。
此時，原始的熵如果ｓ傳遞的所有資訊被ｕ共享，則知道ｕ就可以
ｉ７—＿，／
圖２服務流程部署
提供所有關於ｓ的必要資訊，在這種情況下
１．２貝葉斯網路
貝葉斯網路（ｂｎ）是一種概率網路，它是基於概率推理的圖形化網路 ｊ，在問責制框架中執行根源診斷的任務。ｅｔ前，貝葉斯網路在人工智慧領域已經是乙個很成熟的模型，通過有向
問題與模型
給定兩個點集ｃ和，，分別表示等待服務的城市集合和提供服務的裝置集合。求出ｆ的乙個子集．ｓ用於為ｃ提供服務，同時使得ｉｓｉ＜＝ｋ且ｃ中城市與ｓ中距離最近裝置的距離之和最小，這就是經典的ｋ－ｍｅｄｉａｎ問題 。在故障疑似集選擇演算法中，將按照以下的說明將故障疑似集選擇問題對映為ｋ－ｍｅｄｉ＇
ａｎ問題：
無環圖（ｄａｇ）進行不確定條件下的推理。在ｄａｇ中，節點代表隨機變數，每個變數都有乙個狀態互斥的有限集。連線結點的有向邊代表直接的因果關係，一旦服務之間的因果關係確定下來，乙個業務流就可以轉化為貝葉斯網路 ｊ。
如圖３所示，服務節點被抽取出來作為單獨的根變數節點（矩形節點），而輸出節點被表示為貝葉斯網路中單獨的變數節點（橢圓節點），這種轉換基於輸出節點與服務節點之間的因果關係。例如，輸出節點ｉ的狀態是由服務ｉ的所有繼承服務輸出狀態和服務ｉ本身執行的正確性決定的。在貝葉斯網路中，所有的輸出結點（橢
（１）每個輸出結點ｕ對應ｋ－ｍｅｄｉａｎ中的乙個裝置，如果根據制約條件最多能選出ｋ個輸出結點，則最多啟用ｋ個裝置。
（２）每個服務節點ｓ對應ｋ－ｍｅｄｉａｎ問題中的乙個城市。
（３）輸出結點對服務節點ｓ的ｐｏｓｔ熵值再加上服務節點本身紀錄的故障標識ｓｅ值的倒數（設標識ｅｍ對應的故障為ｆｍ），為ｋ－ｍｅｄｉａｎ中的城市與最近裝置之間的距離值。即：
圓結點）都是監管的候選。然而，如果蒐集所有輸出結點的所
有資訊，會使**在資訊蒐集過程中超荷負載，不能達到有效的開銷均衡，尤其是在分布式系統中，將會導致非常高的開銷。本文介紹的基於事件驅動的ｓｏａ故障疑似集選擇演算法，從所有服務的輸出集合中選擇乙個子集，為貝葉斯網路引擎提供開銷最平衡的診斷資料。
贏（２）
（４）將目標轉化為最小化ｋ－ｍｅｄｉａｎ問題中每個城市到最近的裝置之間距離和。
本文的演算法使用了文獻［７］中提出的ｋ－ｍｅｄｉａｎ區域性搜尋啟發式方法：
（１）ｓ一任意乙個可行解。
（２）ｗｈｉｌｅ存在乙個操作叩，使得一
南（３）返回ｓ。
此處ｓ＞０為一常量ｎ，＝ｌｆｌ是裝置集合的裝置總數，ｎ ＝ｉ
ｃｌ是城市集合的城市總數，ｐ（ｎｌ，ｎ ）是與ｎ，和ｎ 相關的多項式。ｃｏｓｔ（ｓ）表示計算解值的費用函式，ｏｐ（ｓ）是操作函式，在本
文中定義為一對一裝置交換。即從當前解｜ｓ中選擇乙個裝置ｓｓ，同時在ｆ－ｓ中選擇乙個裝置３∈ｆ－ｓ，然後把兩者分別交換
圖３業務流到貝葉斯網路轉換圖
放入對方集合，形成乙個新的當前解．ｓ 。。
２．３故障服務選擇演算法
２故障疑似集選擇演算法
２．１敏感性分析技術
為了決定如何選擇故障服務，必須決定哪些輸出節點對於服務操作節點的觀察最有資訊價值。ｂｎ理論中的敏感性分析技術 ］，可以用來測量每個服務的輸出節點對服務操作節點的
影響。ｙｕｅｚｈａｎｇ等人提出的ｅｃｓ演算法，直接將基於公式（１）得到
的ｐｏｓｔ熵作為ｋ－ｍｅｄｉａｎ模型中的距離值來選擇故障疑似集，忽略了對具體故障的歷史記錄，不能有效的利用之前的選擇結果，有可能使最後得到的故障疑似集丟失一些出現問題的服務。本文將轉化之後的貝葉斯網路加入與故障集ｆ對應的標識集ｅ，當故障事件發生時，為選中的對應服務ｓｆ新增標識，即
如果相同的故障事件發生在此節點上，則繼續增加相應的權重；進行ｋ－ｍｅｄｉａｎ選擇時，首先根據歷史故障集
定義ｐｅ（ｕ，ｓ）是輸出節點ｕ對服務操作節點．ｓ的ｐｏｓｔ熵，用來在ｂｎ敏感性分析中測量ｕ對ｓ的影響。ｐｅ（ｕ，ｓ）使用夏農互動資訊的定義，衡量在概率分布下一組互相排斥的狀態集合之間不確定性的程度。假設服務ｓ是一組互相排斥的狀態集合：
ｓ，ｓ，…，ｓ，輸出節點ｕ是一組互相排斥的狀態集合：「 ，「 一，「 。則ｐｅ（ｕ，ｓ）的定義是：
ｆ確定標識ｅ的值ｍ，然後計算權值公式（２），最後利用區域性搜尋啟發式方法選出最優故障疑似集。增加的故障標識集ｅ不僅有利於提高故障服務集選擇演算法的準確性，而且有利予以後的**性分析。
具體演算法如下：
（１）初始化為：ｆ＝ ，ｅ＝ ；
第５期李晶等：一種基於事件驅動的ｓｏａ故障疑似集選擇演算法ｌ８３
（２）根據故障ｆ ，如果嶽ｆ，則
圖５為當貝葉斯診斷停止時三種方法的診斷ｔ作量比較。
（３）對每個服務節點ｓ，迴圈計算式（１）和式（２）的值；（４）再進行以下迴圈：對於得到的ｄ（ｆｌ，值，利用區域性搜尋啟發式方法，得到輸出，則ｆｓ＝ｆｓｕｓ ，直至迴圈結束；
診斷工作量定義為檢查健康服務時所花費的工作量。如圖５所示，ｆｓｓ只比ｅｃｓ稍高了一些，但二者都遠低於ｒａｎｄｏｍ的工作量。綜合查詢完整性的比較，ｆｓｓ演算法在總體上優於ｅｃｓ和
（５）對中的每個輸出節點對應的服務節點ｓ，增加
ｓｅ 的權重值，ｓｅ ＋ ；
（６）輸出故障疑似服務集ｆｓ。
以後每次發生故障時，重複步驟（２）一（６）。
２．４演算法分析
與ｅｃｓ演算法相比，本演算法是在原迴圈中進行ｄ ｎ的計算，所以時間複雜度沒有變化，最複雜的情況下為（０（ｂｎｒ）＋０
（ⅳ２）），其中０（ｂｎｒ）是貝葉斯網路推理的複雜度，ⅳ是業務流中的服務總數。當包含數百個變數時，貝葉斯網路推理是易處
理的，因此本文中的故障疑似集選擇演算法對於真實世界中的應用也是可計算的。在空間上增加了故障集與標識集，對每個服務記錄故障標識，因為是簡單的整數型別，沒有增加空間複雜度。而且這樣的目的是提高故障疑似集選擇的完整性。
下節的**結果表明，相比之下這種策略更為有效。
３**實驗和分析
３．１**實驗
本文採用了與文獻［３］類似的**環境，即使用ｂｎｇｅｎｅｒａ—
ｔｏｒｊ
，隨機貝葉斯網路生成器，來產生乙個隨機的服務網路。
它能保證產生的網路均勻分布在被審查的圖空間。可以調節
接受一些約束，例如網路的大小，最大節點數和網路中的最大邊數，這些約束限制了網路的連線方式。在本文的**實驗中，做了適當的增強，增加了產生實際故障標識的故障個數，設定**環境中實際故障個數為１、２、４、６的比例分別為隨機產生的服務網路有３０—５０不等的節點，每個節點的最大輸入和輸出邊設定為２。在每一輪的測試中設定產生問題的服務為４—６個，共執行１００輪的測試。
本文對所有的服務分別執行ｆｓｓ、ｅｃｓ和隨機均勻選擇。
３．２結果分析
圖４為使用三種方法的診斷查詢完整率比較，完整率定義為檢測到的問題服務與所有的問題服務的比較。在網路大小為
３０、４０、５０的情況下，可以看出ｆｓｓ演算法比ｅｃｓ演算法和隨機檢測能檢測到更多的問題服務，查詢完整率分別是６３％、５８％和４０％（網路大小網路大小網路大小＝５０）。
圖４查詢完整率
圖５診斷工作量
４ 總結
本文提出了一種基於事件驅動的服務故障疑似集選擇算
法，收集業務流程的執行時資料和記錄具體的故障事件，通過貝葉斯推理和ｋ－ｍｅｄｉａｎ搜尋發現最有可能出現故障的服務集合。**實驗的結果表明，此演算法比ｅｃｓ演算法有著更高的查詢完整率，在以後的工作中，會進一步研究利用演算法中故障標識ｅ的歷史記錄所進行的**性分析。
參考文獻
一種基於影象處理的自動調焦系統
摘要 一種基於影象處理的自動調焦方法，應用該方法設計一種虹膜影象自動採集系統。該系統利用虹膜區域的平均對比度作為是否對焦準確的判據，並以此為反饋控制執行機構進行實時對焦。實驗證明該系統自動調焦精確，採集到的虹膜影象清晰，符合使用要求 並且調焦機構簡單，整個系統控制易於實現。關鍵詞 自動調焦圖象處理虹...
一種基於拓撲優化的機翼結構設計
作者 佟剛劉同飛鄧揚晨 中國科技縱橫 2013年第19期 摘要 介紹了拓撲優化和仿生學的特點，提出了一種利用msc patran建立機翼結構拓撲優化模型的步驟與方法，並通過對機翼結構拓撲優化和仿生學設計說明該方法的可行性和應用價值。關鍵詞 拓撲優化機翼結構仿生學設計有限元 msc patran ms...
一種基於RFID技術的金融押運業務綜合管理系統專利
專利號 201120257846 本實用新型公開了一種基於rfid技術的金融押運業務綜合管理系統，其特徵在於，所述系統包括射頻感應天線，物聯網門禁控制器，手持讀寫器，電子標籤，授權發卡器，計算機及其安裝的系統管理軟體。所述系統的工作原理是 首先將授權的人員或物品資訊輸入到計算機內，再通過授權發卡器將...