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

doi:10.11959/j.issn.1000-0801.2016260

电信科学 ›› 2016, Vol. 32 ›› Issue (10): 101-109.doi: 10.11959/j.issn.1000-0801.2016260

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

翟治年¹,王巍橡¹,卢亚辉²,吴茗蔚¹,郑志军¹,余法红³

¹ 浙江科技学院信息与电子工程学院，浙江杭州310023
² 深圳大学计算机与软件学院，广东深圳518060
³ 嘉兴学院数理与信息工程学院，浙江嘉兴314001

出版日期:2016-10-15 发布日期:2017-04-27
基金资助:
浙江省教育厅科研基金资助项目;浙江省自然科学基金资助项目;国家自然科学基金资助项目

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

Zhinian ZHAI¹,Weixiang WANG¹,Yahui LU²,Mingwei WU¹,Zhijun ZHENG¹,Fahong YU³

¹ School of Information and Electronics Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China
² School of Computer and Software, Shenzhen University, Shenzhen 518060, China
² College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, China

Online:2016-10-15 Published:2017-04-27
Supported by:
Foundation Items: Zhejiang Provincial Education Department Research Foundation of China;Zhejiang Provincial Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

工作流可满足性（WS）研究一定访问控制策略下的资源分配问题，其计数问题有利于判断工作流对资源异常情况的顽健性。本文研究互斥约束下的WS计数问题，通过多项式计数归约为约束可满足性计数问题，将经典的回溯树分解方法用于#WS（≠）求解。实验表明，改进后的算法降低了执行时间，相对于现有#WS（≠）算法，提出的算法对低密度约束下的工作流具有一定的综合性能优势。

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

Abstract:

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.

Key words: workflow, authorization, constraint, resource allocation, satisfiability

翟治年,王巍橡,卢亚辉,吴茗蔚,郑志军,余法红. 基于回溯树分解的互斥约束工作流可满足性计数[J]. 电信科学, 2016, 32(10): 101-109.

Zhinian ZHAI,Weixiang WANG,Yahui LU,Mingwei WU,Zhijun ZHENG,Fahong YU. Counting workflow satisfiability with exclusion constraints based on backtracking tree-decomposition[J]. Telecommunications Science, 2016, 32(10): 101-109.

图/表 2

表1

表2

参考文献 18

[1]	WANG Q , LI N . Satisfiability and resiliency in workflow authorization systems[J]. ACM Transactions on Information and System Security, 2010,13(4): 747-759.
[2]	翟治年，王刚，郑志军，等. 基于可满足性计数的（≠,=）约束工作流顽健性验证[J]. 电子学报， 2015,43(11):2298-2234. ZHAI Z N , WANG G , ZHENG Z J , et al. Verification of（≠,=） constrained workflow robustness based on satisfiability counting[J]. Acta Electronica, 2015,43(11):2298-2234.
[3]	AHMED T , TRIPATHI A R . Security policies in distributed CSCW and workflow systems[J]. IEEE Transactions on Systems, Man,and Cybernetics Part A:Systems and Humans, 2010,40(6): 1220-1231.
[4]	BERTINO E , FERRARI E , ALTURI V . The specification and enforcement of authorization constraints in workflow management systems[J]. ACM Transactions on Information System Security, 1999,2(1): 65-104.
[5]	CRAMPTON J , KHAMBHAMMETTU H . Delegation and satisfiability in workflow systems[C]// 13th ACM Symposium on Access Control Models and Technologies, June 11,2008, Colorado, USA, New York:ACM Press, 2008: 31-40.
[6]	BASIN D , BURRI S J , KARJOTH G . Obstruction-free authorization enforcement: aligning security and business objectives[C]// The 24th ComputerSecurityFoundationsSymposium, June 27,2011, Cernay, France. New Jersey:IEEE Press, 2011: 99-113.
[7]	CRAMPTON J , GUTIN G , YEO A . On the parameterized complexi and Kernelization of the workflow satisfiability problem[J]. AC Transactions on Information and System Security, 2012,16(1): 1518-1527.
[8]	翟治年，卢亚辉，周武杰，等. 工作流可满足性（≠）计数的固定参数线性算法[J]. 计算机学报， 2016(39). ZHAI Z N , LU Y H , ZHOU W J , et al. Fixed-parameter linear algorithm for counting workflow satisfiability （≠）[J]. Chinese Journal of Computers, 2016(39).
[9]	JEGOU P , TERRIOUX C . Hybrid backtracking bounded by tree-decomposition of constraint networks[J]. Artificial Intelligence, 2003,146(1): 43-75.
[10]	ROBERTSON N , SEYMOUR P D , GRAPH MINORS . II. Algorithmic aspects of tree-width[J]. Journal of Algorithms, 1986,7(86): 309-322.
[11]	DECHTER R , PEARL J . Tree clustering for constraint networks[J]. Artificial Intelligence, 1989,38(4): 353-366.
[12]	BULATOV A A . The complexity of the counting constraint satisfaction problem[J]. Physical Review D Particles ＆ Fields, 1993,49(10): 5349-5363.
[13]	谷文祥，朱磊，黄平，等. 可满足问题中的模型计数[J]. 智能系统学报， 2012,7(1):33-39. GU W X , ZHU L , HUANG P , et al. The model counting of a satisfiability problem[J]. CAAI Transactions on Intelligent Systems, 2012,7(1):33-39.
[14]	ANGEL SMARK O , JONSSON P , LINUSSON S , et al. Determining the number of solutions to binary CSP instances[C]// 8th International Conference on Principles and Practice of Constraint Programming, September 9,2002, New York, USA. New Jersey:IEEE Press, 2002: 181-186.
[15]	ANGELSMARK O , JONSSON P . Improved algorithms for counting solutions in constraint satisfaction problems[J]. Lecture Notes in Computer Science, 2003(2833): 81-95.
[16]	DAHLL?F V , JONSSON P , WAHLSTR?M M . Counting models for 2SAT and 3SAT formulae[J]. Theoretical Computer Science, 2005,332(1-3): 265-291.
[17]	MARCIAL-ROMERO J R , LUNA G D I , HERNáNDEZ J A , et al. A parametric polynomial deterministic algorithm for #2SAT[M]. Advances in Artificial Intelligence and Soft Computing. New York:Springer International Publishing, 2015.
[18]	FAVIER A , GIVRY S D , JéGOU P . Exploiting problem structure for solution counting[C]// International Conference on Principles and Practice of Constraint Programming, September 20,2009, Lisbon, Portugal. New Jersey:IEEE Press, 2009: 335-343.

序号	实例配置	参考文献[2]		参考文献[8]		BTD			算法1
序号	实例配置	时间/s	空间/MB	时间/s	空间/MB	时间/s	空间/MB	时间/s	空间/MB	W+1
1	13_70_1-33_6	0.009 35	5 458	0.422	21	0.000 320	17	0.000 239	17	2.4
2	15_41_1-33_7	0.010 7	2 729	0.922	30	0.000 242	17	0.000 203	17	2.2
3	16_40_34-66_9	0.011 7	6 822	3.39	44	0.001 89	17	0.000 841	17	3.2
4	16_74_67-100_6	0.015 0	6 821	14.5	71	0.030 4	17	0.010 4	17	2.6
5	17_43_1-100_5	0.013 4	6 822	12.7	83	0.000 742	17	0.000 426	17	2
6	18_26_34-66_15	0.014 5	6 822	8.74	116	0.003 01	17	0.001 14	17	4.6
7	18_27_1-33_8	0.009 88	0	5.68	116	0.000 267	17	0.000 228	17	2.8
8	18_45_34-66_9	0.013 7	6 821	28.2	175	0.036 8	17	0.022 7	17	3.4
9	18_46_67-100_5	0.009 34	6 821	40.4	175	0.002 01	17	0.000 810	17	2
10	21_50_67-100_6	0.065 9	6 821	601	2011	0.006 59	17	0.002 22	17	2
11	21_73_1-100_8	1.07	6 822	822	2732	360+	14	360+	14	3.6
12	23_28_34-66_13	0.014 2	6 825	679	4777	0.128	18	0.214	18	6.2
13	27_39_34-66_8	0.278	6 824	∞	8 000+	0.143	18	0.241	18	4.4
14	27_50_1-33_7	0.012 3	6 824	∞	8 000+	0.008 26	17	0.002 74	17	5.4
15	28_43_1-100_7	6.08	6 824	∞	8 000+	2.50	19	4.82	19	4.4
16	29_38_67-100_7	∞	7 057+	∞	8 000+	360+	17	360+	17	3.6
17	30_29_1-100_15	1.79	7 339	∞	8 000+	1 098+	29	1 096+	29	12.4
18	30_35_34-66_13	∞	7 745+	∞	8 000+	1 444+	24	1 444+	24	9.8
19	30_73_67-100_8	∞	7 884+	∞	8 000+	1 133+	22	1 131+	22	5.4
20	30_74_1-33_7	0.002 47	7 388	∞	8 000+	0.017 0	17	0.006 52	17	3.2

算法1	ω	5	10	15	20	25	30	35
\|S\|=8,\|U\|=4	W+1	2	2	2.3	2	2.7	3.3	3.3
	\|X\|	1.3	2.7	5.7	4	7.3	10	10.3
	时间/s	0.000 338	0.000 211	0.000 314	0.000 249	0.000 601	0.000 738	0.001 43
\|S\|=12,\|U\|=5	W+1	2	2.3	2.7	3	4	6	5.7
	\|X\|	4.7	6.7	10.3	11.3	17.7	24.7	26.3
	时间/s	0.000 898	0.000 532	0.001 09	0.003 57	0.011 1	0.767	0.291
\|S\|=14,\|U\|=8	W+1	2	3.3	6	4.7	5	6.3	6.7
	\|X\|	3.3	13	15.3	21	19.3	30	32.3
	时间/s	0.000 937	0.034 6	14.4	175.0	32.4	1 009.5	19 772.0

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 18

相关文章 15

Metrics

推荐阅读 0

[1]	康宇, 刘雅琼, 赵彤雨, 寿国础. AI算法在车联网通信与计算中的应用综述[J]. 电信科学, 2023, 39(1): 1-19.
[2]	汪晗, 刁磊, 王梦玲, 荣欣, 李佳珉, 尤肖虎. 工业物联网中URLLC的关键问题分析[J]. 电信科学, 2022, 38(Z1): 77-92.
[3]	贺智敏, 林育哲, 程宇杰, 闫实. 基于无线感知辅助的车联网下行无线资源分配方法[J]. 电信科学, 2022, 38(9): 60-70.
[4]	邹璐珊, 黄晓雯, 杨敬民, 郑艺峰, 张光林, 张文杰. 移动边缘计算中资源分配和定价方法综述[J]. 电信科学, 2022, 38(3): 113-132.
[5]	绳韵, 许晨, 郑光远. 基于NOMA的超密集MEC网络任务卸载和资源分配方案[J]. 电信科学, 2022, 38(2): 35-46.
[6]	丁铖, 陈锦荣, 曹小冬, 王翊. 基于服务质量的层次化结构资源分配算法[J]. 电信科学, 2022, 38(1): 102-111.
[7]	王泽杰, 王潜心, 商天文. 基于北斗三号卫星非差多普勒观测信号的优化测速模型[J]. 电信科学, 2021, 37(12): 42-50.
[8]	余云河, 孙君. 机器类通信中集中式与分布式Q学习的资源分配算法研究[J]. 电信科学, 2021, 37(11): 41-50.
[9]	吴柳青,朱晓荣. 基于边-端协同的任务卸载资源分配联合优化算法[J]. 电信科学, 2020, 36(3): 42-52.
[10]	李凯,刘伟,罗贵阳,李静林. 以用户为中心的智能化网络运营服务方法[J]. 电信科学, 2020, 36(2): 101-108.
[11]	徐珉, 胡南, 李男. 5G非授权频段组网技术[J]. 电信科学, 2019, 35(7): 7-16.
[12]	包晓安,曹云棣,张娜,钱俊彦,曹建文. 基于格分布方差的多目标云工作流调度算法[J]. 电信科学, 2019, 35(2): 1-13.
[13]	贾海宇,陈佳,王铭鑫. 无线接入网络中网络功能虚拟化研究综述[J]. 电信科学, 2019, 35(1): 97-112.
[14]	易冰,陈永丽,赵瑞雪. 毫米波5G网络中D2D通信的资源分配方案[J]. 电信科学, 2019, 35(1): 138-146.
[15]	李学华,沈琛,姚媛媛. 基于跨层策略的60 GHz脉冲多用户通信系统性能分析[J]. 电信科学, 2018, 34(9): 70-77.