一种策略冲突的消解方法

2015-12-11李鑫

湖北民族大学学报(自然科学版) 2015年2期

关键词：冲突

李　鑫

(重庆理工大学会计学学院，重庆 400050)

一种策略冲突的消解方法

李鑫

(重庆理工大学会计学学院，重庆 400050)

摘要：利用非单调逻辑编程技术，Chomicki等人提出了一种策略冲突消解方法.虽然该方法具有高效、可靠和良好的封装性等优点，但是它的应用域却受到限制.在Chomicki方法的基础上，首先定义了组合冲突，它比一般策略冲突涵义更广.其次，为消解该类冲突引入了一个优化解—最大行动接受集，并给出与之互补的最小行动取消集的重要特性.最后，利用基于稳定模型语义的权约束规则编程技术，建立消解组合冲突的逻辑程序.由于该程序始终拥有稳定模型，所以总是能够根据它的模型获得优化解.

关键词：冲突；权约束规则；最大行动接受集；最小行动取消集；稳定模型

随着ECA(event-condition-action)策略在计算机管理与控制中的广泛应用，如分布式系统管理、数据库系统管理、安全与访问控制、Web服务及其组合等，有关策略冲突的研究也愈来愈受到重视[1-3].

利用基于稳定模型语义的非单调逻辑编程技术[4-5](也被称为回答集编程技术[6])，Chomicki等人[3]提出一种消解PDL(policy description language)[7]策略冲突的方法.该方法具有以下优点：

1)易于实现PDL策略及其冲突消解的逻辑编程表示，且逻辑编程技术能够确保冲突消解的可靠性和有效性；

2)建立的冲突消解逻辑程序具有良好的层次性和独立性；

3)根据冲突消解逻辑程序的稳定模型，不但能够实现冲突消解而且还可以获得极大行动接受集.Chomicki等人选择PDL策略的原因是它比一般ECA策略更复杂且描述能力更强[7-8].

Chomicki方法并不能消解本文定义的特殊组合冲突.一方面，该方法的成功依赖于冲突消解逻辑程序语义模型的存在性；另一方面，当特殊组合冲突发生时，按照该方法构造的冲突消解逻辑程序不再拥有稳定模型.从而导致失败.其失败的根本原因是它采用了析取逻辑编程技术[5,9]，这点将在3.2节详细说明.

下文通过例1的冲突说明特殊组合冲突的普遍性.同时该例也用于阐述本文中的冲突消解方法.

例1在一个简单的会议室自动预定系统中，一方面，式(1)的PDL规则构成其策略.该规则规定当一个用户User的预定申请事件requestRes(User)发生时，为该用户执行预留会议室的行动procRes(User).另一方面，为消解冲突定义式(2)的行动约束(action constraint,ac)，以防止由于同时执行两个不同用户的procRes行动而导致的冲突.这里的冲突是由于同时发生了多个不同用户的预定申请事件，而且他们申请的是同一会议室而导致的.另外，假设会议室的预留时间重叠.

(1)

(2)

此例也是文献[3]中的例1.简洁起见，下文一律假设预定申请的是同一会议室，且申请事件同时发生.该例中，特殊组合冲突指由三个或三个以上不同用户申请导致的冲突.而由两个不同用户申请导致的冲突，也是Chomicki方法能够消解的，在本文归为一般组合冲突.

为克服Chomicki方法的局限性，本文提出一种利用基于稳定模型语义的权约束规则(weight constraint rule, WCR)编程技术[10-11]消解策略冲突的方法.在Chomicki方法基础上，首先定义了涵义更为宽泛的组合冲突，它不仅包含了一般组合冲突，更为重要的是，特殊组合冲突也是它的一个子类.然后，为冲突消解提出一个优化解概念，即最大行动接受集(largest action-acceptance set, LAAS)，并给出与它互补的最小行动取消集(smallest action-cancellation set,SACS)的重要性质.最后，在一个极大化处理过程的基础上，利用WCR编程技术建立组合冲突消解逻辑程序.由于该程序始终拥有稳定模型，所以总是能够获得LAASes.

1　背景知识

1.1　WCR编程简介

任意非单调逻辑程序是一个由形如式(3)的规则组成的有限集.其中，li(i∈{0,1，…,n})是一阶正(或负)文字，not是 “失败为否定” (negation-as-failure)操作符.通常称集合{l0,,l1,…,lk}和{lk+1,,lk+2,…,ln}分别为规则的头和体.由于不再象Prolog程序具有唯一的最小海布南模型[12]，所以非单调逻辑程序通常按照模型语义解释，即只有在一定的语义模型下，逻辑程序才具有明确的语义解释.由M.Gelfond和V.Lifschitz开创的稳定模型语义是至今为止被广为接受的一种非单调逻辑程序模型语义.经过二十年的发展，如今已经开发出多种实用的稳定模型语义编程系统，如DLV[13]、AnsProlog[14]等.

(3)

(4)

(5)

(6)

(7)

(8)

WCR编程技术是对基于稳定模型语义的非单调逻辑编程技术的一种扩展，SMODELS是它的实用编程系统.一个WCR的基本形式为“WC0←WC1,…,WCm”，其中，式(4)表示任意权约束WCi(i∈{0,1,…,m}).WCi的语义定义是，S|=WCi当且仅当z≤w(S,WCi)≤u，其中，S为任意原子谓词实例集，权值函数w(WCi,S)=∑ai∈Slai+∑bj∉Slbj，而且，上界u、下界z以及权值目前只能为自然数.关于基于稳定模型语义的WCR程序，需要注意以下两点：①它的模型不但符合稳定模型语义解释，而且还需要满足权约束上的权值约束；②WCR具有灵活多样的形式，除基本形式外，例如，式(5)的规则也是可行的.

当所有权值均为1时，WCR被称为基数约束规则(cardinality constraint rule,CCR)，基数约束可简化为式(6)的形式.除权值始终为1外，CCR的语义定义与WCR一样.WCR编程技术还提供分别形如式(7)和(8)的minimize和maximize优化语句，它们的权值计算与WCR一样.以上两个语句分别完成对程序最小和最大权值模型的搜索.

1.2　Chomicki方法

1.2.1策略Prolog程序.在文献[3]中，任意PDL策略P的语义是变换πP:Epochs(P)→ActionSet(P).其中，Epochs(P)是所有段事件集的集合，且一个段事件集是由发生在一个系统时间段中的所有基本事件实例(primitive event instance)组成的有限集；ActionSet(P)是一个是由所有完成填充的行动构成的集合，且它的一个元素被称为行动集.

(9)

(10)

设策略P对应于一段事件集E的实例为P(E).通过将P(E)中每个PDL规则实例“e1&…&elcauses a if C”，用式(9)的Horn(或definite)范式捕获，建立P对应于E的Prolog程序∏P.在式(9)中，exec和occ是原子谓词，条件C=t1θ1t1′，…，tmθ1tm′且任意比较谓词θi∈{=,≠,≤,≥}(i∈{1,2,…,m}).

至此得到，对于一段事件集E而言，任意行动a∈πP(E)当且仅当∏P∪OCC(E)|=exec(a)，其中，式(10)定义OCC(E).从而完成策略P的等价逻辑编程表示.

1.2.2冲突消解.Chomicki等人定义了形如“Nevera1，a2，…，amifC”的ac以捕获一类冲突.以上ac规定在条件C被满足的情况下，禁止同时执行m个行动a1，…，am，否则将导致冲突.AC是管理员定义的ac集合，且对应于一个段事件集E的AC实例为AC(E).

(11)

(12)

从以上介绍也可看出，冲突消解逻辑程序具有良好的层次性且各组成部分之间相互独立.

2　组合冲突

2.1　定义

称被一个ac(或aci)约束的行动个数为它的长度.显然，任意ac(或aci)的长度均大于1.

2)X中所有行动构成的集合等于A；

3)X中的任意aci的条件C被满足.

以上定义中，条件3排除了对aci的条件判断，这便于冲突组合的研究.而且，由于该类条件易于判断，所以条件3的要求是合理的.在下文中，用式(13)定义的CAC(E)表示对应于一段事件集E的cac集合.

(13)

2.2　Chomicki方法缺陷

在下文中，用EXEC(A)={exec(a)|a∈A}、BLOCK(A)={block(a)|a∈A}分别表示行动集A上的exec和block实例集.同时令U=OCC(E)∪EXEC(πP(E))∪BLOCK(πP(E)).

3　最大行动接受集

对于AC(E)中的单个aci，只需要取消被它约束的一个行动，不但能够满足该aci(即实现冲突消解)，而且还确保了行动接受集的极大性.但为满足AC(E)的一个子集或AC(E)本身，同时又要确保行动接受集的极大性，却是复杂的.

定义2对应于一段事件集E的行动全集始终是πP(E).设一个aci集合X⊆AC(E).如果一个行动集X⊂πP(E)同时满足：

1)πP(E)X满足X中的任意aci；

2)任意X′⊂X，πP(E)X′至少不能满足X中的一个aci.

则称X是X的一个极小行动取消集(minimal action-cancellation set, MACS)，记为ΔX.称πP(E)ΔX是与ΔX对应的 MAAS.显然，一个ΔX同与之对应的MAAS构成互补关系.一个MAAS等价于文献[3]中定义的繁琐的“P的极大AC监控行动取消(maximal action-cancellation AC-monitor of P)”.

假设ΔAC(E)∩A<|A|-k+1成立.由以上证明，易得πP(E)ΔAC(E)不能满足α，所以ΔAC(E)不是AC(E)的一个MACS.

命题1不但适合特殊组合冲突，同样适合一般组合冲突.

在实际应用中，往往要求被接受的行动愈多愈好.但是，由于一个MAAS并不一定是对应的AC(E)所有MAASes中基数最大的集合，所以依靠AC(E)的一个MAAS并不能确保被接受的行动最多.

由命题1可知，此时任意ΔAC(E)至少包含A1(或A2)的2个元素.在AC(E)的所有MAASes中，一方面，由于ΔAC(E)={a1,a2}在AC(E)所有的MACSes中基数最小，所以对应的MAAS(即{a3,a4,a5,a6})基数最大，从而确保了被接受的行动最多；另一方面，由于ΔAC(E)={a3,a4,a5,a6}的基数最大，所以对应的MAAS(即{a1,a2})拥有最小基数，从而被接受的行动最少.

定义3设一个aci集合X⊆AC(E).在X的所有MACSes中，基数最小的集合被称为X的一个SACS，记为ΞX.类似MAAS的定义，称πP(E)ΞX是与一个ΞX对应的LAAS.

显然，aci集X的一个SACS必然是它的一个MACS，但反之并不成立.这同样适合X的LAAS和MAAS.所以，SACS/LAAS是对MACS/MAAS的进一步优化.另外，X的SACS或LAAS并不是唯一的.

证明由命题1直接可得.

4　组合冲突消解

4.1　极大化

在利用WCR编程技术消解组合冲突之前，有必要剔出CAC(E)中的冗余元素.首先定义一个CAC(E)上的偏序关系≤.然后在此关系基础上，利用一个简单的极大化过程剔出CAC(E)中的冗余元素.

可获得如下关于偏序集〈CAC(E),≤〉的性质.

命题3设两个cacsαi,αj∈CAC(E)、Ξαj是αj的一个SACS.如果αi≤αj，则αi至少存在的一个SACS(Ξαi)，满足Ξαi⊆Ξαj.而且，如果αi=αj，则αi的一个SACS必然是αj的一个SACS，反之也成立.

基于偏序集〈CAC(E),≤〉，用于剔出CAC(E)中冗余元素的极大化过程为：

1)初始CACm(E)为∅.

2)如果CAC(E)≠∅，从〈CAC(E),≤〉中选择一个极大元素α，将之添加到CACm(E).然后删除〈CAC(E),≤〉中任何满足α′≤α的元素α′.

3)循环执行步骤2，直到CAC(E)=∅.

下文用CACm(E)取代CAC(E).

4.2　冲突消解逻辑程序

易得A1是AC(E)的一个SACS.

(14)

(15)

(16)

(17)

由于πP(E)=∅使得冲突消解没有必要，所以，下文中均假设πP(E)≠∅.

由以上定理证明也可知，式(14)可简化为论据(fact) “n-k+1≤{block(a1)，…，block(an)}≤n←”.需要说明的是，即使一个WCR程序拥有多个优化模型，如多个相同最小基数模型，但是当前的SMODELS只为用户提供其中的一个优化模型.

再根据定理2和定义3，得AM(E)是AC(E)的一个LAAS.

5　结语

析取逻辑编程技术使得Chomicki方法在消解组合冲突时并不可靠.而本文利用WCR编程技术不但完成冲突消解，特别是能够完成一种特殊冲突的消解，即组合冲突的消解，同时能够获得冲突的优化解.本文方法成功的根本原因是，WCR编程技术不仅提供了优化机制，更重要的是，其程序的稳定模型能够包含一个规则头中的多个原子谓词实例.

参考文献:

[1]Lupu E,Sloman M.Conflicts in Policy-Based Distributed Systems Management[J]. IEEE Transaction on Software Engineering，Nov/Dec，1999，25(6)：852-869.

[2]Turner K, Blair L.Policies and Conflicts in Call Control[J]. The International Journal of Computer and Telecommunications Networking，Elsevier，2006，51(2)：496-514.

[3]Chomicki J,Lobo J, Naqvi S. Conflict Resolution Using Logic Programming[J].IEEE Transactions on Knowledge and Data Engineering，Jan/Feb，2003，15(1)：244-249.

[4]Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming[M].The MIT Press: R. Kowalski, K. Bowen (eds.), In Proc the 5th International Conference on logic programming,1988：1070-1080.

[5]Gelfond M,Lifschitz V.Classical Negation in Logic Programs and Disjunctive Databases[J].New Generation Computing，1991，9(3/4)：365-386.

[6]Gelfond M, Leone N. Logic Programming and Knowledge Representation—The A-Prolog Perspective[J]. Artificial Intelligence，Elsevier，2002，138：3-38.

[7]Lobo J, Bhatia R, Naqvi S. A Policy Description Language[C]// In Proc the 16th National Conference on Artificial Intelligence (AAAI-99), July,1999：291-298.

[8]Son T C, Lobo J. Reasoning about Policies Using Logic Programs[C]//In Proc the AAAI Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, March,2001：210-216.

[9]Przymusinski T. Stable Semantics for Disjunctive Programs[J]. New Generation Computing，1991，9(3/4)：401-424.

[10]Niemelä I, Simons P， Soininen T. Stable Model Semantics of Weight Constraint Rules[C]// In Proc. the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, Texas，USA，Dec，1999：317-331.

[11]Simons P, Niemelä I, Soininen T. Extending and Implementing the Stable Model Semantics[J]. Artificial Intelligence，Elsevier，2002，138：181-234.

[12]Emden M, Kowalski R. The Semantics of Predicate Logic as a Programming Language[J]. Journal of ACM，1976，23(4)：733-742.

[13]Leone N, Pfeifer G, Faber W, et al. The DLV System for Knowledge Representation and Reasoning[J]. ACM Transactions on Computational Logic，2006，7(3)：499-562.

[14]Baral C. Knowledge Representation, Reasoning, and Declaring Problem Solving with Answer sets[M].Cambridge University Press，2003.

[15]Leone N, Rullo P, Scarcello F. Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation[J]. Information and Computation，1997，135(2)：69-112.

[16]Lifschitz V, Turner H. Splitting a Logic Program[C] / / In Proc the 11th International Conference on Logic Programming, 1994：23-37.

[17]卢开澄,卢华明.组合数学[M].3版.北京：清华大学出版社，2002.

责任编辑：时凌

A Method of Policy Conflict Resolution

LI Xin

(School of Accounting,Chongqing University of Technology,Chongqing 400050,China)

Abstract：By using the nonmonotonic logic programming technology, Chomicki et al. proposed an approach to resolve policy conflict. Although the approach is efficient, reliable, and has good encapsulation, its application domain is limited. On the base of Chomicki’s approach, we firstly define combination conflict that is more general than common policy conflict. Then, we introduce an optimal solution for combination conflict resolution, i.e., the largest action-acceptance set, and show the important property of the smallest action-cancellation set as the complement of the solution. Lastly, the logic program for combination conflict resolution is constructed by using weight constraint rule programming technology with the stable model semantics. Because the logic program always has at least one stable mode, it is reliable to obtain an optimal solution according to a stable model of this program.

Key words：conflict；weight constraint rule；largest action-acceptance set；smallest action-cancellation set；stable model

作者简介：郭黎(1978- )，女，博士，副教授，主要从事视频图像处理与识别信息显示的研究. 何恬(1988- )，女，硕士生，主要从事国土资源调查、评价与规划开发的研究;*:宋鄂平(1971- )，男，高级实验师，博士，主要从事林业、旅游、地质学的研究.

DOI:10.13501/j.cnki.42-1569/n.2015.06.028 10.13501/j.cnki.42-1569/n.2015.06.020

文章编号：1008-8423(2015)02-0230-05 1008-8423(2015)02-0193-04

通信作者

基金项目：教育部人文社会科学青年基金项目(12YJC630306). 国家自然科学基金项目(61263030,61463014)；湖北省自然科学基金资助项目(2014CFB612)；湖北民族学院博士启动基金(MY2014B018).

收稿日期：2015-03-31. 2014-12-01.

中图分类号：TP181；TP182

文献标志码：A