基于回溯树分解的互斥约束工作流可满足性计数  

Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition

作　　者：翟治年[1] 王巍橡 卢亚辉[2] 吴茗蔚[1] 郑志军[1] 余法红[3] 

机构地区：[1]浙江科技学院信息与电子工程学院,浙江杭州310023 [2]深圳大学计算机与软件学院,广东深圳518060 [3]嘉兴学院数理与信息工程学院,浙江嘉兴314001

出　　处：《电信科学》2016年第10期101-109,共9页Telecommunications Science

基　　金：浙江省教育厅科研基金资助项目(No.Y201533771);浙江省自然科学基金资助项目(No.LY16F020027);国家自然科学基金资助项目(No.61302112)~~

摘　　要：工作流可满足性(WS)研究一定访问控制策略下的资源分配问题,其计数问题有利于判断工作流对资源异常情况的顽健性。本文研究互斥约束下的WS计数问题,通过多项式计数归约为约束可满足性计数问题,将经典的回溯树分解方法用于#WS(≠)求解。实验表明,改进后的算法降低了执行时间,相对于现有#WS(≠)算法,提出的算法对低密度约束下的工作流具有一定的综合性能优势。Workflow satisfiability（WS） concerns the issue of resource allocation under some access control policies.Counting all its solutions is advantaged to verify the robustness of a workflow to resource exceptions. The counting problem of WS with only exclusion constraints was addressed. The classic backtracking tree-decomposition method was employed to solve #WS（≠） via a polynomial-time counting reduction to a counting constraint satisfiability problem. Experiments show that, the proposed optimized algorithm declined in running time, and has well synthetical performance for workflows with low-density constraints compared to the existing #WS（≠） algorithms.

关 键 词：工作流 授权 约束 资源分配 可满足性 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]