一种针对物联网智能系统的规则冲突检测方法
2023-03-27郭浩然冯俊辉
杨 波 郭浩然 冯俊辉 李 戈 金 芝
1(北京林业大学信息学院 北京 100083)
2(北方工业大学信息学院 北京 100144)
3(国家林业和草原局林业智能信息处理工程技术研究中心(北京林业大学)北京 100083)
4(北京大学计算机学院 北京 100871)
5(高可信软件技术教育部重点实验室(北京大学)北京 100871)
物联网指的是物体与物体之间的互联网络,它通过无线传感技术,利用传感器获取物体和环境的信息,实现物理设备之间、物理设备与网络之间信息传输与资源共享[1].一般来说,物联网系统架构中通过逻辑控制器来感知物理环境的状态并调度物理设备以提供想要的服务.将设备控制逻辑从控制器中分离出来,可以方便物联网系统的设计和支持系统的演化,从而减少物联网系统的开发和维护成本,提高物联网系统架构的灵活性.这种将设备逻辑控制从控制器中分离出来的物联网系统,在一定程度上可以认为是一种智能系统.
物联网系统架构中的核心逻辑控制器使用规则来控制业务逻辑,规则一般由2 部分构成:约束部分和动作部分.约束部分是物联网系统中的实体状态构成的条件,这些条件随着物联网系统规模的扩大而变得复杂.当约束部分包含的条件所组成的逻辑表达式成立时,触发规则的动作部分,从而改变物联网系统中某些实体的状态.而这些实体状态的改变,将触发物联网系统中的其他规则,从而导致物联网系统的状态发生新的变化.当物联网系统中实体的状态,不能使得所有规则约束部分的条件得到满足时,系统将产生规则间的冲突,从而使得物联网系统的运行出现问题.
图1 是典型的物联网系统架构,主要分为外部元素、网络层、控制系统3 部分.外部元素包括传感器和设备.传感器是信息流动的源头,可以采集温度、湿度、光强、压力等物理量;设备包括可编程的硬件,是信息流动的目的地.网络层完成信息传输,实现外部元素与控制系统的连接[2-3].控制系统完成物理设备的逻辑控制,是信息的加工处理部分.
Fig.1 Typical Internet of things system architecture图1 典型的物联网系统架构
图2 是使用规则推理作为控制系统核心的架构,它包括交互处理模块和规则推理模块,交互处理模块将环境和设备的状态数据格式化后传递到规则推理模块,并根据规则推理信息来控制设备状态.规则推理模块包括知识和推理引擎.知识是由逻辑构成的规则,当知识部署在推理机中,推理机可以根据知识,对输入的外部元素的状态数据进行逻辑推理[4].
Fig.2 Rule inference control system architecture图2 规则推理控制系统架构
在物联网系统中,规则调度流程大致是这样的:外部状态数据通过网络层传递进控制系统.交互处理模块将状态数据格式化后传递到规则推理模块.规则推理模块经过推理,输出控制信息传递到交互处理模块.交互处理模块根据控制信息生成设备控制命令,通过网络层发送到相应的控制设备.
在一些复杂的物联网运行的场景中,如果2 条或多条规则出现冲突,带来的后果是比较严重的,甚至是灾难性的.例如,智能会议室中投影仪开启或关闭的规则出现混乱,导致会议无法正常进行.无人驾驶的物联网系统,如果因为规则的冲突,导致传递给车辆的信息是错误的,导致无人驾驶车辆出现偏离正常行驶路线,甚至导致车毁人亡的灾难事件.
图3 表示2 种典型的物联网中的规则冲突案例.图3(a)中,用户编写2 条规则R1和R2,当环境温度为22°C 时,2 条规则都被触发.电暖气制热与空调制冷,对环境温度产生相反的影响,从而产生消极影响冲突.
Fig.3 Rule conflict cases图3 规则冲突案例
图3(b)中,用户编写3 条规则R3,R4和R5,当环境光强为2000 lm 时,3 条规则都被触发.受到规则R3和R4的影响,窗帘处于不断开关的状态,从而产生执行矛盾冲突.
图3(a)和图3(b)中所展示的规则间的冲突是由于现有的物联网规则冲突的分类还不够精细,使得已有的冲突检测方法不一定能检测到这2 种规则冲突,从而出现规则冲突漏检的问题.
针对物联网系统中存在的规则冲突的问题,一些学者对此展开研究.Shehara 等人[5]提出一种需求交互分类法,用于对软件系统中的需求交互进行分类和识别.文献[5]提出的分类法是一个4 层金字塔的形式,在第1 层定义6 个主要交互类别,在第2 层定义17 个交互子类别,在第3 层定义29 个交互类型,在第4 层定义29 个交互场景,每个交互场景都有一个相应的交互检测指南来描述如何检测交互.该文献还提出一种半形式化的冲突检测方法IRIS(identifying requirements interactions using semiformal)来识别需求冲突,成为形式化方法的重要基础.Hu 等人[6]通过分析智能家居系统的本体模型,实现知识重用和上下文语义建模,提出基于Web 语义的策略冲突检测方法SPIDER(semantic Web-based policy interaction detection with rules),来探测智能家庭服务中的规则冲突,为本体编辑工具Protégé[7]和规则引擎工具Jess[8]提供功能支持.然而IRIS 和SPIDER 这2 种方法在规则冲突分类时只考虑离散的系统状态.例如图3(a)所示的案例1,用户只考虑到设备开、关等的离散状态,不能得知温度这样连续状态的变化范围,从而出现规则冲突漏检现象.Sun 等人[9]在对智能家居现状的分析基础上,提出一种基于用户、触发器、环境实体和作动器(user,triggers,environment entities,and actuators,UTEA)的冲突检测方法,他们通过用户、触发器、环境实体和执行器的建模方法,探测智能家具系统的规则冲突,为连续的系统状态提供解决方法,并引入用户优先级的权限控制.方法UTEA 解决在智能家居中,规则增加所带来的规则冗余、冲突等问题.然而此方法需要依赖系统的初始状态,没有被触发的规则不被算法检测,导致检测的准确性下降.例如规则冲突案例2 中如果当环境光强初始为4000 lm,并且灯处于关闭状态时,3 条规则都没有被触发.此时UTEA 方法不能检测出规则冲突.
这些研究在解决物联网系统中的规则冲突问题上取得一定的效果,但是这些研究对规则冲突类型分析还不是很全面,并且检测的准确性有待提高.
为此,本文提出一种物联网系统的形式化规则冲突检测方法(formal rule conflict detection,FRCD).该方法首先利用形式化的方法将物联网中的规则及不同的规则冲突进行建模,同时考虑到连续的系统状态量.这样针对不同的规则冲突,对这些规则的形式化表达进行区分,并且不依赖于系统的初始状态,从而使得不同的规则冲突能够清楚地得到检测.然后,方法FRCD 能够对输入的物联网规则进行解析,得到规则的各种条件,基于解析的结果,对这些条件进行分解,这样可以帮助简化规则条件逻辑.最后,根据不同的规则冲突类型,检测出相应的冲突.
本文的主要贡献包括3 方面:
1)通过调研和分析已有的物联网系统的规则,将目前的物联网系统中的规则冲突细分为7类,分别是执行覆盖冲突、执行矛盾冲突、消极影响冲突、独占资源冲突、直接忽略依赖冲突、直接循环依赖冲突、间接循环依赖冲突.
2)基于对物联网系统的规则冲突分类,对不同的规则冲突进行形式化表示,使得冲突的检测能够自动化进行,且针对不同的规则冲突能够进行很好地区分,在一定程度上能提高规则冲突检测的准确性.
3)设计并实现规则冲突检测的原型系统,在2个物联网系统中进行实验验证.实验的结果表明,本文的方法FRCD 在物联网系统的规则冲突检测的F1值上,表现比其他3 种冲突检测方法更优秀.
1 相关工作
1.1 规则授权访问与规则完整性
Kim[10]针对由RIF[11]规则推理引起的授权问题,提出应用图标记算法,解决由规则推断引起的RDF[12]元组安全签名不一致的问题.Yu 等人[13]提出授权规则规范语言模型,解决同一个服务被授权模型里的规则同时接受和拒绝的问题.Fisler 等人[14]分析基于角色的规则访问控制策略,认为多终端决策图是一种可扩展的访问控制策略解决方法,是实现规则访问控制策略的验证方法.Abdullah 等人[15]提出一种形式化规则检查器,通过控制器安全策略,以确保控制器和执行器的行为安全性.Wang 等人[16]针对物联网安全审计日志分散在各个设备上,不能用于重建安全事务工作流的问题,提出一种以平台为中心的物联网集中审计方法,此方法对物联网应用程序和设备应用编程接口进行高效的自动化测试,以生成包括恶意行为在内的系统活动审计日志.Bu 等人[17]针对错误的设备控制对系统正确性产生影响的问题,提出一种端到端的线性混合自动机模型,用来协助非专业物联网用户进行规则可信检查,确保物联网系统可用性.Ma[18]认为基于规则图的方法,可以解决数据不一致性问题,并利用规则图来描述规则的层次结构,动态评估数据的一致性.Nandi[19]为了解决用户在编写规则触发部分经常犯错误的问题,开发一种静态技术,根据用户编写的动作,自动生成正确的规则触发条件.Abe 等人[20]为解决规则调用的数据缺失问题,抽取物联网描述符号来标准化规则,从而提高规则的质量.Yang 等人[21]通过Petri 网的形式验证规则系统,并推导出规则间的关联矩阵,解决规则的规范化和完整性的验证,避免基于规则的系统受到规则结构错误的影响.Wang 等人[22]提出一种计算执行可满足性的框架,用于发现规则内部的漏洞,但在实践中发现由于物联网平台的封闭性,这种模型的信息流很难获得.为了解决这个问题,文献[22]的作者基于自然语言处理开发用于推断规则信息流的算法.
1.2 规则冲突检测
Fang 和Lu[23]针对软件定义网络中的规则冲突问题,通过等量划分分区包级别的方法,解决软件定义网络中交换机流量条目产生的规则冲突.Cui 等人[24]针对基于软件定义网络的交换机中流规则产生的冲突导致网络功能失效的问题,设计一种基于事务的流规则冲突检测方法,这种方法可以隔离不同网络的流规则,以避免不同网络功能之间的干扰.Batisra等人[25]提出一种基于一阶逻辑的冲突检测方法,解决OpenFlow 网络中随着交换机和主机数量的增加,管理流变得复杂而出现的规则冲突.Magill 和Blum[26]针对规则可能源于不同的来源而产生的一致性问题,他们借鉴特征交互的经验,扩展无线传感技术,解决在无线传感器网络中不同来源的冲突规则导致一致性维护问题.Born 等人[27]通过扩展模型转换工具,解决基于规则的模型转换中发生的冲突和依赖.Jiang等人[28]针对一个大型自组织系统中子系统间具有利益和价值的冲突问题,使用逻辑形式化事件推演,使得每个子系统能够发现和解决其系统自身内部的规则冲突.Zhang 等人[29]通过计算概率描述节点状态作业的权重,得到逻辑推理规则的冲突度量.Diller 等人[30]提出一种从不一致的语言中提取语义的方法,并以正态性假设的形式扩展规则表达方式,解决规则中自然语言表达知识产生的冲突,然而他们没有考虑物联网系统中的规则冲突.Shehara 等人[5]提出一种需求交互分类法,用于对软件系统中的需求交互进行分类和识别,并提出一种半形式化的冲突检测方法(IRIS)来识别需求冲突,并且开发可以应用到特定领域的插件[31].Shah 等人[32]提出一种检测物联网系统中不完整规则的机制,同时考虑条件独立的触发条件引起的规则冲突,这种方法把规则看作使用基于事件的编程语言的程序,实现对规则不完整性和冲突的检测,然而能检测的冲突类型不够全面.李秀[33]基于知识图谱,对智能家居领域内的作动器进行隐式冲突检测,根据作动器功能进行自动分类,实现不限类型的作动器设备之间的隐式规则冲突检测.Lin 等人[34]通过设计规则的形式化模型,把这些规则定义为一个元组,包含触发器、执行器和状态,然后通过分类、组合的方法对规则进行处理,从而描述规则之间的冗余关系,消除和避免冗余的规则出现,提高系统执行效率.
本节所提的研究工作对规则冲突类型分析不全面,并且检测结果的准确性不高,造成规则冲突漏检和错检的问题.本文工作对这些形式化方法进行改进,针对物联网系统的规则冲突进行检测.
2 方 法
2.1 针对物联网系统的规则的形式化分析
为了更清楚地表达物联网系统中的规则,以及区分不同的规则冲突类型,本文针对物联网系统中的规则,给出相应的形式化结构.物联网规则涉及到控制主体、动作、触发条件、规则、符号5 个成分,具体结构如图4 所示.
Fig.4 Rule structure图4 规则结构
1)控制主体sub由标识id、主体类型type、占用标志mon、主体属性attribute、属性值value构成.其中type,attribute是字符串类型,mon={0,1},value为数值类型.
控制主体可表示为sub={id,type,mon,attribute,value}.
2)动作action由执行动作的控制主体sub、被动作影响的属性attribute、动作关系运算符op、操作的属性值value构成.其中op={<,=,>,≤,≥,≠}.
动作可表示为action={sub,attribute,op,value}.
动作的 集合表 示为actions={action(i)| 0 ≤i<n,n∈ N}.
3)触发条件condition由控制主体类型type、约束属性attribute、约束关系运算符op、约束属性值value构成.其中type表示引用上述规则成分中的控制主体sub里的元素type.
触发条件可表示为condition={type,attribute,op,value}.
触发条件的集合可以表示为conditions={condition(i)| 0 ≤i<n,n∈ N}.
4)规则rule由id标识、触发条件conditions、动作actions构成.
规则可表示为rule={id,conditions,actions}.
规则的 集合可 以表示为rules={rule(i)|0 ≤i<n,n∈ N} .
5)为了表达连续的系统状态,定义运算符#,将离散的系统状态数值value转化成区间范围.具体为:
其中value是一个数值,在添加符号#后,数值value与关系符op进行运算,将数值value转换成连续的区间范围;-∞代表负无穷,+∞代表正无穷,()是开区间,是 闭区间,(]是 开闭区间,[)是闭开区间.
通过以上规则结构表示,可以清晰地表达下面的规则交互关系.
2.2 规则的交互关系
规则间的冲突是由规则交互关系引起的,为了深入分析规则冲突类型,首先分析规则交互关系.2个规则的约束条件部分和动作部分的影响,称为规则的交互关系.通过对规则间存在的交互关系进行分析,总结出相容触发条件、控制同一非独占主体、控制同一独占主体、相同控制动作、相反控制动作、互斥影响值、规则Ri触发条件依赖规则Rj的动作、规则Ri触发条件依赖规则Rj的反向动作,8 种规则交互关系如表1 所示.
1)CC表示2 个规则可以在同一个系统场景中触发,称为相容触发条件;
2)SSS表示2 个规则控制同一个非独占类型主体,称为控制同一非独占主体;
Table 1 Rule Interaction表1 规则交互关系
3)SMS表示2 规则控制同一个独占类型主体,称为控制同一独占主体;
4)SA表示2 个规则拥有相同的控制动作,称为相同控制动作;
5)DA表示2 个规则拥有相反的控制动作,称为相反控制动作;
6)MV表示2 个规则对环境属性影响是互斥的,称为互斥影响值;
7)RC(Ri,Rj)表示规则Ri触发条件依赖规则Rj的动作,称为规则Ri触发条件依赖规则Rj的动作;
8)OR(Ri,Rj)表示规则Ri触发条件依赖规则Rj的反向动作,称为规则Ri触发条件依赖规则Rj的反向动作.
通过以上8 个规则交互关系的总结,为下面的规则冲突类型的形式化表达提供符号表示.
2.3 规则的冲突类型
由于规则之间存在交互关系,使得规则间产生冲突.为了更清晰地描述规则的冲突,本文通过调研和分析物联网系统中的规则交互关系,将目前的物联网系统中的规则冲突分为7类,分别是:执行覆盖冲突、执行矛盾冲突、消极影响冲突、独占资源冲突、直接忽略依赖冲突、直接循环依赖冲突、间接循环依赖冲突.
规则的冲突类型以及形式化表达如表2 所示.
Table 2 Rule Conflict Type表2 规则冲突类型
类规则冲突所表达的含义为:
1)一个规则的所有动作包含在另一个规则中,导致前一条规则是冗余的,称为执行覆盖冲突;
2)系统执行2 个规则的先后顺序不同,导致系统状态不同,称2 个规则互为执行矛盾冲突;
3)2 个规则的动作影响同一个属性,导致一个规则影响另一个规则的执行效率,称2 个规则互为消极影响冲突;
4)2 个规则调用同一个独占资源,称2 个规则互为独占资源冲突;
5)规则Rj的触发条件依赖规则Ri的相反动作,导致规则Rj永远不被触发,称规则Rj直接忽略依赖规则Ri;
6)规则Ri的触发条件依赖规则Rj的动作,规则Rj的触发条件依赖规则Ri的动作,导致系统进入死锁状态,称2 个规则互为直接循环依赖冲突;
7)多条规则间的触发条件、动作形成依赖环路,导致系统进入死锁状态,称这些规则互为间接循环依赖冲突.
表2 中的对称关系表示2 个规则调换表述顺序,表达的语义不变.非对称关系表示2 个规则调换表述顺序,表达的语义发生改变.例如规则Ri依赖规则Rj与规则Rj依赖规则Ri,调换规则表述顺序后,表达的语义不一样,属于非对称关系.
经过以上的规则冲突类型总结以及形式化定义,总结出物联网智能系统中规则冲突的特点,并且能对这些规则冲突进行区分,能够比较容易地对这些冲突进行检测.
2.4 基于形式化规则的冲突检测方法
规则冲突检测方法流程如图5 所示.该方法流程主要包括2 部分,分别是规则预处理和规则冲突计算.
Fig.5 The workflow of rule conflict detection method图5 规则冲突检测方法流程
规则冲突检测方法的输入是已有的规则库和待检测的规则,已有的规则库是指在进行规则冲突检测之前,就已经存在的规则集合;待检测的规则是指需要与已有规则库进行检测是否存在冲突的规则.
在进行规则检测前,需要对输入的规则库和待检测规则进行预处理.首先,需要将规则解析成粒度较小的规则元素,目的是将输入的规则解析成可以用作形式化表达的元素.随后进行规则分解,目的是将复杂的规则分解为只包含与逻辑关系的规则.规则预处理之后,得到分解之后的规则库与待检测的规则.接下来需要对规则冲突进行分析,通过规则交互关系分析和规则冲突检测,得到最终的规则冲突检测结果.
2.4.1 规则预处理
规则预处理包括规则解析和规则分解2 个步骤.
规则解析的目的是将输入的规则解析成可以形式化表达的元素.首先,待检测的规则和规则库里的规则输入到规则解析子模块;然后,根据物联网系统规则的形式化结构,将文本类型的规则解析成由id标识、触发条件conditions、动作actions构成的形式化元素;最后,分别输出规则元素库和规则元素.
规则分解是为了简化包含复杂逻辑的规则,这样可以便于后续的规则冲突检测.本文利用析取范式将规则进行分解.例如规则R1经过析取范式转化得到R2,R2可以表达为触发条件只包含“与”逻辑关系的2 个规则R3和R4.此过程将同时包含“与”“或”逻辑关系的规则R1,分解成为只包含“与”逻辑关系的规则R3和R4.
规则分解步骤首先输入规则元素库和规则元素;然后,经过上述析取范式分解;最后,输出分解之后的规则库与待检测的规则.
2.4.2 规则交互关系分析
规则交互关系分析是后续规则冲突检测的基础,对于任意2 个规则,它们之间的交互关系可以采用4 个步骤进行分析,首先,遍历2 个规则的约束部分和动作部分;其次,获取规则的形式化元素;然后,将形式化元素依据规则交互关系形式化表达,匹配出相应的规则交互关系;最后,输出2 个规则的交互关系.
规则交互关系分析如算法1 所示.算法1 输入规则Ri和Rj,输出规则关系re.算法1 的行②③分别遍历Ri和Rj的约束conditions部分和动作actions部分.行④~㉗获取规则的形式化元素,依据表1 定义的规则交互关系,设置规则关系变量re的标志位.行㉘输出存储2 个规则交互关系的变量re.最终计算出待检测规则与规则库所有规则的交互关系.规则交互关系名称用表1 中符号缩写表示,部分符号依赖于图4的规则结构.
算法1.规则交互关系分析算法.
2.4.3 规则冲突检测
获得规则间的交互关系之后,接下来对规则间的冲突进行检测.规则之间的冲突检测可以采用4 个步骤进行分析:首先,计算待检测规则与规则库里所有规则的依赖关系;其次,获取当前参与检测的2 个规则的交互关系;然后,匹配规则冲突类型;最后,输出规则冲突检测信息.
规则冲突检测如算法2 所示.为了简化表达,规则交互关系名称用表1 中符号缩写表示.算法2 输入规则库RDB和待检测规则Ri,输出规则冲突检测信息.算法2 的行②定义变量relyM,它是MAP 数据类型,它的键是规则id,它的值是当前规则所依赖的其他规则id组成的队列,用来存储规则间的依赖关系信息.行③~⑪遍历RDB里的所有规则,将此规则的id作为键,直接依赖的所有规则id作为值存到relyM变量中.行⑫~⑱遍历RDB中的规则Rj,其中Ri,Rj作为函数relation()的输入,得到Ri,Rj的关系re.re与relyM作为函数matchConflict()的输入,根据表2 的规则冲突类型来匹配规则冲突信息.最终计算出待探测规则与规则库里的规则是否有冲突,如果有冲突则输出具体冲突类型.其中行⑥~⑧调用算法1 的规则交互关系分析函数relation().
算法2.规则冲突检测算法.2.4.4 规则冲突检测实例
通过算法1 和算法2 的实现,可以在任何情况下检测到图3(a)和图3(b)中的规则冲突.
对于图3(a),2 条规则R1,R2经过规则预处理分别得到:
规则R1,R2通过规则交互关系分析,conditionR1中的room[Environment],temperature与conditionR2中的room[Environment],temperature相等但conditionR1中的“<25”与conditionR2中的“>20”不是包含关系,所以它们可以同时触发,使得ComCon字段取值为真;actionR1中 的temperature与actionR2中 的temperature相等,但是actionR1中的heater不等于conditionR2中的air_conditioner并且actionR1中的“>27”与actionR2中的“<15”没有交集,所以MutVal字段取值为真.这2 个规则经过规则冲突检测,符合消极影响冲突的形式化表达,输出的规则R1,R2具有消极影响冲突.
对于图3(b),2 条规则R3和R4经过规则预处理分别得到:
由于不需要分析规则R5,即可检测到规则冲突,所以R5不再描述.通过规则交互关系分析,conditionR3中的light[Light],isOn与conditionR4中 的light[Light],isOn相等,但conditionR3中的“=1”与conditionR4中的“=0”不是包含关系,所以它们可以同时触发,使得ComCon字段取 值为真;actionR3中 的curtain,isOn与actionR4中的curtain,isOn相等,所以字段SamShareSub取值为真;actionR3中的“=0”不等于conditionR4中的“=1”,使得字段DifAct取值为真.2 个规则经过规则冲突检测,符合执行矛盾冲突的形式化表达,输出规则R3,R4具有执行矛盾冲突.
上述的规则检测过程不依赖于真实环境,所以在任何环境下都可以检测到规则冲突.但本文所比较的3 种方法需要在特定的条件下才能检测出这2种规则冲突.
3 实验及结果分析
3.1 研究问题
为了验证所提出的方法的有效性,本文提出3 个研究问题:
问题1.与已有的冲突检测方法相比,本文的方法能检测的规则冲突类型是否更全面.
问题2.与已有的冲突检测方法相比,本文的方法检测结果效果是否更好.
问题3.进行方法自身的对比实验,通过删掉方法中的某一部分或某几个部分,来验证方法的有效性.
3.2 实验对象
本文的实验对象是2 个物联网系统,分别为智能会议室模拟系统和智能渔业模拟系统.这2 个系统的介绍及其中所包含的规则如表3 和表4 所示.
智能会议室模拟系统是利用物联网技术,通过规则控制会议室环境和多媒体设备的模拟系统,其中规则包括了20 条执行覆盖类型规则、22 条执行矛盾类型规则、24 条消极影响类型规则、28 条独占资源类型规则、26 条直接忽略依赖类型规则、32 条直接循环依赖类型规则、45 条间接循环依赖类型规则、91 条场景初始化规则.
Table 3 Introduction to Intelligent Conference Room System表3 智能会议室系统介绍
Table 4 Introduction to Intelligent Fishery System表4 智能渔业系统介绍
智能渔业模拟系统是利用物联网技术,通过规则控制船舶航行、鱼群捕捞的模拟系统,其中规则包括了22 条执行覆盖类型规则、26 条执行矛盾类型规则、20 条消极影响类型规则、24 条独占资源类型规则、28 条直接忽略依赖类型规则、30 条直接循环依赖类型规则、33 条间接循环依赖类型规则、86 条场景初始化规则.
3.3 实验环境及参数设置
实验的软件环境为Jdk 1.8,Maven 3.6,Intelli-JIDEA 2020.1,Drools 7.4.另外,本文对实验的数据进行处理,3 个实验都从规则库的每个类型中随机抽取80%的规则文件进行实验,为了避免规则冲突类型分布不均匀的问题.
3.4 评价指标
冲突检测不仅要报告出2 条规则是否有冲突,还要给出具体出现了哪种冲突.为此采用精确率(precision,P)、召回率(recall,R)和F1 值来作为实验的评估指标[35].
计算评价指标之前,首先需要计算多分类问题的混淆矩阵,混淆矩阵的每个元素cij(i,j∈ N)代表样本实际分类i,分类器判定分类j的计数;再计算实际属于i类型样本wi的二分混淆矩阵元素a,b,c,d;最后计算评价指标F1(wi).其中
实验中执行1 次规则冲突检测方法,将算法得出的规则冲突结果与真实规则冲突结果采用以上评估指标进行量化.
3.5 实验结果及分析
1)问题1.与已有的冲突检测方法相比,本文的方法能检测的规则冲突类型是否更全面.
为了探究本文的方法能检测的规则冲突类型是否更全面,将本文的方法FRCD 与现有的3 种规则冲突检测方法对比,实验结果如表5 所示.其中FRCD检测到7 种冲突,UTEA 检测到3 种冲突,SPIDER 检测到4 种冲突,IRIS 检测到3 种冲突.
Table 5 Detection Results of Different Types of Conflics by Four Methods表5 4 种方法对不同冲突类型的检测结果
SPIDER 支持直接循环依赖,但在本次实验中没有检测到.因为SPIDER 算法是在系统进入冲突状态才检测到冲突,但本实验的物联网系统执行了这2种类型规则,将进入死锁状态,导致系统崩溃,所以这种冲突检测方法不适用.
UTEA 支持直接循环依赖、间接循环依赖2 种类型的冲突检测,但在本次实验中没有检测到.因为UTEA 算法是在系统进入冲突状态才检测到冲突,但本实验的物联网系统执行了直接循环依赖和间接循环依赖这2 种类型规则,将进入死锁状态,导致系统崩溃,所以这2 种冲突检测方法不适用.
本文通过调研和分析已有的物联网系统的规则,依据规则间的环路结构总结出直接循环依赖冲突、间接循环依赖冲突.规则间冗余总结出执行覆盖冲突.规则的约束条件部分描述了系统资源状态,可以总结出独占资源冲突.规则的动作部分描述了系统执行状态可以总结出执行矛盾冲突、消极影响冲突、直接忽略依赖冲突.针对物联网系统规则的每个部分,FRCD 方法都进行了详细的冲突类型总结,因此可以得出结论,本文的方法能检测的规则冲突类型更全.
2)问题2.与已有的冲突检测方法相比,本文的方法检测结果的F1 值是否更高.
为了探究本文的方法检测结果的F1 值是否更高,将本文的方法FRCD 与现有的3 种规则冲突检测算法对比.
模拟智能会议室系统实验对比结果如表6 所示,FRCD 算法检测到7 种冲突,覆盖了所有冲突类型,它们的F1 指标均值为78.3%.UTEA 检测到3 种冲突:执行覆盖、执行矛盾、消极影响,它们的F1 指标均值为68.6%.SPIDER 检测到4 种冲突:执行覆盖、执行矛盾、消极影响、直接忽略依赖,它们的F1 指标均值为57.9%.IRIS 检测到3 种冲突:执行覆盖、执行矛盾、消极影响,它们的F1 指标均值为69.0%.在智能会议室系统上,FRCD 算法的检测效果超过了其他3 种算法.
Table 6 P,R and F1 Score Results Comparison of Intelligent Conference System for Different Methods表6 智能会议室系统不同方法的精确率、召回率和F1 值结果对比 %
模拟智能渔业系统实验对比结果如表7 所示,FRCD 算法检测到7 种冲突,覆盖了所有冲突类型,它们的F1 指标均值为90.9%.UTEA 检测到3 种冲突:执行覆盖、执行矛盾、消极影响,它们的F1 指标均值为87.1%.SPIDER 检测到4 种冲突:执行覆盖、执行矛盾、消极影响、直接忽略依赖,它们的F1 指标均值为63.1%.IRIS 检测到3 种冲突:执行覆盖、执行矛盾、消极影响,它们的F1 指标均值为77.5%.在智能渔业船舶系统上,FRCD 算法的检测效果超过了其他3 种算法.
Table 7 P,R and F1 Score Results Comparison of Intelligent Fisher System for Different Methods表7 智能渔业船舶系统不同方法的精确率、召回率和F1 值结果对比 %
本文进一步分析了FRCD 检测效果优于其他3种方法的原因.其中UTEA 需要初始化规则的场景,而FRCD 则不需要,这样可以避免为不充分的初始化场景制定而影响冲突检测效果.并且实现了直接循环依赖、间接循环依赖2 种冲突静态检测,避免系统因循环依赖的规则而进入死锁状态.
另外,FRCD 算法考虑了连续的系统变量,但是SPIDER 与IRIS 只考虑规则中离散的系统状态.在本文的实验案例对应的物联网系统中,存在连续的系统状态,因此对这些连续的系统状态检测是必要的.
实验分析可以得出,本文的方法检测结果的F1值更高.
3)问题3.通过逐渐删掉方法中的某一部分或某几个部分,来验证方法的有效性.
本文在模拟智能会议室系统上,通过逐一删掉表1 中定义的规则交互关系进行实验.其中RC(Ri,Rj)和OR(Ri,Rj)不参与删除,因为去掉其中任意一个会导致某种类型冲突不能检测.实验结果如表8 所示,FRCD 在所有类型冲突指标都是最高的.
Table 8 F1 Score Result Comparison of Reduce Rule Interaction for Different Methods表8 减少规则交互关系在不同方法F1 值结果对比 %
FRCD-CC代表去掉CC部分,它除了执行覆盖、执行矛盾、独占资源类型的评价指标不变,其他冲突类型指标都有所降低.因为CC用来推断2 条规则是否在同一个场景中触发,如果它取值为假,不会进入与其相关的冲突类型匹配,如果它取值为真,将进一步探测与其相关的冲突类型.去掉CC部分,相当于CC取值永远为真,导致某些规则检测错误.
FRCD-SSS代表去 掉SSS部 分,FRCD-SMS代 表去掉SMS部分,这2 个实验的检测指标都有所降低.因为这2 个实验没有考虑到设备是否可以被共享,一些涉及设备并发的规则冲突无法检测,导致冲突检测指标降低.
FRCD-SA代表去掉SA部分,FRCD-DA代表去掉DA部分,这2 个实验的检测指标,除了消极影响类型的评价指标不变,其他指标都有所降低.因为这2 个实验没有考虑规则全部的动作类型,SA和DA同时考虑才能构成规则动作的全集,它们只检测了一部分的动作类型,导致冲突检测指标降低.
FRCD-MV代表去掉MV部分,它的检测指标都有所降低.因为此实验没有考虑不同规则影响到同一个属性值而造成的冲突,导致冲突检测指标降低.
实验分析可以得出,本文的方法有必要考虑所有的规则交互关系部分.
4 总结
本文提出了一种针对物联网系统架构中的核心部件系统控制逻辑中规则的冲突检测方法.该方法首先对物联网系统的规则进行分析与归类,利用形式化的方法将物联网中的规则及不同的规则冲突进行建模.针对不同的规则冲突,它们的形式化表达有所不同,从而使得不同的规则冲突能够清楚地得到检测.然后,该方法能够对输入的物联网规则进行解析,得到规则的各种条件和动作,基于解析的结果,对这些条件进行分解,这样可以帮助简化规则条件逻辑.最后,根据不同的规则冲突类型,检测出相应的冲突.本文在2 个物联网系统中开展的实验,与已有的3 种物联网规则冲突检测方法进行对比,实验结果显示,本文方法的规则冲突检测效果,是这4 种方法中最好的.但是,本文提出的方法还存在完善的方面.例如,物联网规则冲突类型分析还不够全面,同时算法只能报告哪些规则间存在冲突,不能给出修改成正确规则的指导建议,还缺少了规则间冲突关系可视化展示,这些都是将来有待研究的工作.
作者贡献声明:杨波提出了算法思路、实验方案和修改论文;郭浩然负责完成实验并撰写论文;冯俊辉参与实验;李戈提出实验方案并修改论文;金芝提出指导意见并修改论文.