A formalized model for service compositions is established based on the Markov chain. It is called the Markov chain model. The model can be established by translating the definition specifications to the Markov chain when the definition specifications of composite services are given, or by analyzing the executing history data when the definition specifications of composite services are unknown. Different from most of other formalized models with the only function of verifying composite services' correctness, the Markov chain model for composite services have many uses, such as evaluating the trustiness of executing composite services, getting composite services executing costs, for example, response time, expenses, etc. The most important one is that most of application algorithms for the Markov chain model can effectively solve the polynomial complexity, while other formalized models' majority of problems, such as the verification problem,are NP-hard problems.%基于马尔可夫链建立了服务组合的形式化模型--马尔可夫链模型,此模型可以在已知组合服务定义规格的情况下由组合服务的定义规格转换得到,也可以在未知组合服务定义规格的情况下由组合服务的执行历史信息得到.不同于多数服务组合形式化模型仅有用于验证组合服务正确性的单一功能,组合服务的马尔可夫链模型具有多种用途,例如可以用来评估组合服务执行的可信性,可以用来获得组合服务的响应时间、花费等执行代价,最为重要的是马尔可夫链模型的多数应用算法是多项式时间复杂性的有效算法,而其它形式化模型的验证等问题多数是NP-hard问题.
展开▼
