一种针对物联网智能系统的规则冲突检测方法_杨波.pdf

一种针对物联网智能系统的规则冲突检测方法杨波1,2,3郭浩然2冯俊辉2李戈4,5金芝4,51（北京林业大学信息学院北京100083）2（北方工业大学信息学院北京100144）3（国家林业和草原局林业智能信息处理工程技术研究中心（北京林业大学）北京100083）4（北京大学计算机学院北京100871）5（高可信软件技术教育部重点实验室（北京大学）北京100871）（）A Rule Conflict Detection Approach for Intelligent System of Internet of ThingsYangBo1,2,3,GuoHaoran2,FengJunhui2,LiGe4,5,andJinZhi4,51（School of Information Science&Technology,Beijing Forestry University,Beijing 100083）2（School of Information Science&Technology,North China University of Technology,Beijing 100144）3（Engineering Research Center for Forestry Oriented Intelligent Information Processing,National Forestry and Grassland Administration(Beijing Forestry University),Beijing 100083）4（School of Computer Science,Peking University,Beijing 100871）5（Key Laboratory of High Confidence Software Technologies(Peking University),Ministry of Education,Beijing 100871）AbstractThecoreoftheInternetofthings(IoT)systemarchitectureisthelogiccontroller.Thelogiccontrollerusesrulestocontrolthebusinesslogic,whichreducesthedevelopmentandmaintenancecostsoftheIoTsystemandimprovestheflexibilityoftheIoTdevices.AsthescaleoftheIoTsystemexpands,therelationshipbetweentherulesbecomescomplicated.Thismaycauseruleconflicts.Inresponsetothisproblem,someresearchershaveproposedsomedetectionmethodsforruleconflicts.However,theexistingruleconflictdetectionmethodsstillhavesomeproblems,suchasincompleteanalysisofruleconflicttypesandlowaccuracyofdetectionresults.Forthesereasons,aformalruleconflictdetection(FRCD)methodforthecontrollogicoftheIoTintelligentsystemisproposed.Thismethodformalizesthestructureofrules,anddefinesrulesasacombinationofcontrolsubjects,actions,triggerconditions,andsymbols.Thenaccordingtotheinfluenceoftherulesonthesystemandthestructuralcharacteristicsoftherules,7typesofruleconflictsaresummarized.Finally,analgorithmforruleconflictdetectionisdesigned,andthe detailed process of rule conflict detection is introduced.We carry out experiments on two IoT systems andcomparethemwiththreetypicalIoTruleconflictdetectionmethods.Thesethreemethodsaretheformalrulemodelconflict detection method based user,triggers,environment entities,and actuators(UTEA),semantic web-basedpolicyinteractiondetectionwithrules(SPIDER),identifyingrequirementsinteractionsusingsemiformal(IRIS).Theexperimentalresultsshowthattheformalruleconflictdetectionmethodinthispaperismoreeffective.Key wordsInternetofthings；intelligentsystem；ruleconflict；conflictdetection；ruleformalization收稿日期：2021-09-15；修回日期：2022-06-19基金项目：中 央 高 校 基 本 科 研 业 务 费 专 项 资 金（BLX202003）；国 家 自 然 科 学 基 金 项 目（62072007,62192733,61832009,62192730,61772078,61502011）；北京林业大学热点追踪项目（BLRD202124）ThisworkwassupportedbytheFundamentalResearchFundsfortheCentralUniversities(BLX202003),theNationalNaturalScienceFoundationofChina(62072007,62192733,61832009,62192730,61772078,61502011),and the Focus Tracking Project of Beijing Forestry University(BLRD202124).通信作者：金芝（）计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202110941JournalofComputerResearchandDevelopment60（3）：592605，2023摘要物联网系统架构的核心是逻辑控制器，逻辑控制器中使用规则控制业务逻辑，减少物联网系统的开发、维护成本，提高物联网设备的灵活性.但随着物联网系统的规模扩大，规则间的关系变得复杂，从而可能产生规则冲突.为避免规则发生冲突，一些研究者提出了规则冲突检测方法.但是，以往的规则冲突检测方法还存在规则冲突类型分析不全面、检测结果准确性较低的问题.为此提出一种针对物联网系统控制逻辑的形式化规则冲突检测方法(formalruleconflictdetection，FRCD).该方法首先形式化定义规则及规则冲突，其中将规则定义为控制主体、动作、触发条件、符号的组合；然后根据规则对系统的影响以及规则的结构特征，总结出 7 类规则冲突类型；最后设计规则冲突检测的算法，并介绍规则冲突检测的详细过程.在 2 个物联网系统上开展实验，与已有的 3 种典型的物联网规则冲突检测方法进行对比.这 3 种方法分别是基于用户、触发器、环境实体和作动器的冲突检测方法(user,triggers,environmententities,andactuators,UTEA)、基于 Web 语义的策略冲突检测方法(semanticWeb-basedpolicyinteractiondetectionwithrules,SPIDER)和半形式化的冲突检测方法(identifyingrequirementsinteractionsusingsemiformal,IRIS).实验结果显示，FRCD 规则冲突检测方法效果更好.关键词物联网；智能系统；规则冲突；冲突检测；规则形式化中图法分类号TP391物联网指的是物体与物体之间的互联网络，它通过无线传感技术，利用传感器获取物体和环境的信息，实现物理设备之间、物理设备与网络之间信息传输与资源共享1.一般来说，物联网系统架构中通过逻辑控制器来感知物理环境的状态并调度物理设备以提供想要的服务.将设备控制逻辑从控制器中分离出来，可以方便物联网系统的设计和支持系统的演化，从而减少物联网系统的开发和维护成本，提高物联网系统架构的灵活性.这种将设备逻辑控制从控制器中分离出来的物联网系统，在一定程度上可以认为是一种智能系统.物联网系统架构中的核心逻辑控制器使用规则来控制业务逻辑，规则一般由 2 部分构成:约束部分和动作部分.约束部分是物联网系统中的实体状态构成的条件，这些条件随着物联网系统规模的扩大而变得复杂.当约束部分包含的条件所组成的逻辑表达式成立时，触发规则的动作部分，从而改变物联网系统中某些实体的状态.而这些实体状态的改变，将触发物联网系统中的其他规则，从而导致物联网系统的状态发生新的变化.当物联网系统中实体的状态，不能使得所有规则约束部分的条件得到满足时，系统将产生规则间的冲突，从而使得物联网系统的运行出现问题.图 1 是典型的物联网系统架构，主要分为外部元素、网络层、控制系统 3 部分.外部元素包括传感器和设备.传感器是信息流动的源头，可以采集温度、湿度、光强、压力等物理量；设备包括可编程的硬件，是信息流动的目的地.网络层完成信息传输，实现外部元素与控制系统的连接2-3.控制系统完成物理设备的逻辑控制，是信息的加工处理部分.外部元素传感器设备网络层网络层控制命令控制系统状态数据Fig.1TypicalInternetofthingssystemarchitecture图1典型的物联网系统架构图 2 是使用规则推理作为控制系统核心的架构，它包括交互处理模块和规则推理模块，交互处理模块将环境和设备的状态数据格式化后传递到规则推理模块，并根据规则推理信息来控制设备状态.规则推理模块包括知识和推理引擎.知识是由逻辑构成控制系统交互处理模块控制信息格式化数据规则推理模块知识推理引擎Fig.2Ruleinferencecontrolsystemarchitecture图2规则推理控制系统架构杨波等：一种针对物联网智能系统的规则冲突检测方法593的规则，当知识部署在推理机中，推理机可以根据知识，对输入的外部元素的状态数据进行逻辑推理4.在物联网系统中，规则调度流程大致是这样的:外部状态数据通过网络层传递进控制系统.交互处理模块将状态数据格式化后传递到规则推理模块.规则推理模块经过推理，输出控制信息传递到交互处理模块.交互处理模块根据控制信息生成设备控制命令，通过网络层发送到相应的控制设备.在一些复杂的物联网运行的场景中，如果 2 条或多条规则出现冲突，带来的后果是比较严重的，甚至是灾难性的.例如，智能会议室中投影仪开启或关闭的规则出现混乱，导致会议无法正常进行.无人驾驶的物联网系统，如果因为规则的冲突，导致传递给车辆的信息是错误的，导致无人驾驶车辆出现偏离正常行驶路线，甚至导致车毁人亡的灾难事件.图 3 表示 2 种典型的物联网中的规则冲突案例.图 3（a）中，用户编写 2 条规则 R1和 R2，当环境温度为22C 时，2 条规则都被触发.电暖气制热与空调制冷，对环境温度产生相反的影响，从而产生消极影响冲突.R1:当温度小于25,打开电暖气升温到27R2:当温度大于20,开空调降温到15电暖器空调温度R3:当灯是开启的,关闭窗帘R4:当光线强度小于3 000lm,开灯R5:当灯是开启的,打开窗帘窗帘灯(a)规则冲突案例1(b)规则冲突案例2Fig.3Ruleconflictcases图3规则冲突案例图 3（b）中，用户编写 3 条规则 R3，R4和 R5，当环境光强为 2000lm 时，3 条规则都被触发.受到规则R3和 R4的影响，窗帘处于不断开关的状态，从而产生执行矛盾冲突.图 3（a）和图 3（b）中所展示的规则间的冲突是由于现有的物联网规则冲突的分类还不够精细，使得已有的冲突检测方法不一定能检测到这 2 种规则冲突，从而出现规则冲突漏检的问题.针对物联网系统中存在的规则冲突的问题，一些学者对此展开研究.Shehara 等人5提出一种需求交互分类法，用于对软件系统中的需求交互进行分类和识别.文献 5 提出的分类法是一个 4 层金字塔的形式，在第 1 层定义 6 个主要交互类别，在第 2 层定义 17 个交互子类别，在第 3 层定义 29 个交互类型，在第 4 层定义 29 个交互场景，每个交互场景都有一个相应的交互检测指南来描述如何检测交互.该文 献 还 提 出 一 种 半 形 式 化 的 冲 突 检 测 方法 IRIS（identifyingrequirementsinteractionsusingsemiformal）来识别需求冲突，成为形式化方法的重要基础.Hu 等人6通过分析智能家居系统的本体模型，实现知识重用和上下文语义建模，提出基于 Web 语义的策略冲突检测方法 SPIDER（semanticWeb-basedpolicyinteractiondetectionwithrules），来探测智能家庭服务中的规则冲突，为本体编辑工具 Protg7和规则引擎工具Jess8提供功能支持.然而 IRIS 和 SPIDER 这 2 种方法在规则冲突分类时只考虑离散的系统状态.例如图 3（a）所示的案例 1，用户只考虑到设备开、关等的离散状态，不能得知温度这样连续状态的变化范围，从而出现规则冲突漏检现象.Sun 等人9在对智能家居现状的分析基础上，提出一种基于用户、触发器、环境实体和作动器（user,triggers,environmententities,andactuators,UTEA）的冲突检测方法，他们通过用户、触发器、环境实体和执行器的建模方法，探测智能家具系统的规则冲突，为连续的系统状态提供解决方法，并引入用户优先级的权限控制.方法 UTEA 解决在智能家居中，规则增加所带来的规则冗余、冲突等问题.然而此方法需要依赖系统的初始状态，没有被触发的规则不被算法检测，导致检测的准确性下降.例如规则冲突案例 2 中如果当环境光强初始为 4000lm，并且灯处于关闭状态时，3 条规则都没有被触发.此时 UTEA 方法不能检测出规则冲突.这些研究在解决物联网系统中的规则冲突问题上取得一定的效果，但是这些研究对规则冲突类型分析还不是很全面，并且检测的准确性有待提高.为此，本文提出一种物联网系统的形式化规则冲突检测方法（formalruleconflictdetection，FRCD）.该方法首先利用形式化的方法将物联网中的规则及不同的规则冲突进行建模，同时考虑到连续的系统状态量.这样针对不同的规则冲突，对这些规则的形式化表达进行区分，并且不依赖于系统的初始状态，从而使得不同的规则冲突能够清楚地得到检测.然后，方法 FRCD 能够对输入的物联网规则进行解析，得到规则的各种条件，基于解析的结果，对这些条件594计算机研究与发展2023，60（3）进行分解，这样可以帮助简化规则条件逻辑.最后，根据不同的规则冲突类型，检测出相应的冲突.本文的主要贡献包括 3 方面：1）通过调研和分析已有的物联网系统的规则，将目前的物联网系统中的规则冲突细分为类，分别是执行覆盖冲突、执行矛盾冲突、消极影响冲突、独占资源冲突、直接忽略依赖冲突、直接循环依赖冲突、间接循环依赖冲突.2）基于对物联网系统的规则冲突分类，对不同的规则冲突进行形式化表示，使得冲突的检测能够自动化进行，且针对不同的规则冲突能够进行很好地区分，在一定程度上能提高规则冲突检测的准确性.3）设计并实现规则冲突检测的原型系统，在 2个物联网系统中进行实验验证.实验的结果表明，本文的方法 FRCD 在物联网系统的规则冲突检测的 F1值上，表现比其他 3 种冲突检测方法更优秀.1相关工作 1.1规则授权访问与规则完整性Kim10针对由 RIF11规则推理引起的授权问题，提出应用图标记算法，解决由规则推断引起的 RDF12元组安全签名不一致的问题.Yu 等人13提出授权规则规范语言模型，解决同一个服务被授权模型里的规则同时接受和拒绝的问题.Fisler 等人14分析基于角色的规则访问控制策略，认为多终端决策图是一种可扩展的访问控制策略解决方法，是实现规则访问控制策略的验证方法.Abdullah 等人15提出一种形式化规则检查器，通过控制器安全策略，以确保控制器和执行器的行为安全性.Wang 等人16针对物联网安全审计日志分散在各个设备上，不能用于重建安全事务工作流的问题，提出一种以平台为中心的物联网集中审计方法，此方法对物联网应用程序和设备应用编程接口进行高效的自动化测试，以生成包括恶意行为在内的系统活动审计日志.Bu 等人17针对错误的设备控制对系统正确性产生影响的问题，提出一种端到端的线性混合自动机模型，用来协助非专业物联网用户进行规则可信检查，确保物联网系统可用性.Ma18认为基于规则图的方法，可以解决数据不一致性问题，并利用规则图来描述规则的层次结构，动态评估数据的一致性.Nandi19为了解决用户在编写规则触发部分经常犯错误的问题，开发一种静态技术，根据用户编写的动作，自动生成正确的规则触发条件.Abe 等人20为解决规则调用的数据缺失问题，抽取物联网描述符号来标准化规则，从而提高规则的质量.Yang 等人21通过 Petri 网的形式验证规则系统，并推导出规则间的关联矩阵，解决规则的规范化和完整性的验证，避免基于规则的系统受到规则结构错误的影响.Wang 等人22提出一种计算执行可满足性的框架，用于发现规则内部的漏洞，但在实践中发现由于物联网平台的封闭性，这种模型的信息流很难获得.为了解决这个问题，文献 22的作者基于自然语言处理开发用于推断规则信息流的算法.1.2规则冲突检测Fang 和 Lu23针对软件定义网络中的规则冲突问题，通过等量划分分区包级别的方法，解决软件定义网络中交换机流量条目产生的规则冲突.Cui 等人24针对基于软件定义网络的交换机中流规则产生的冲突导致网络功能失效的问题，设计一种基于事务的流规则冲突检测方法，这种方法可以隔离不同网络的流规则，以避免不同网络功能之间的干扰.Batisra等人25提出一种基于一阶逻辑的冲突检测方法，解决 OpenFlow 网络中随着交换机和主机数量的增加，管理流变得复杂而出现的规则冲突.Magill 和 Blum26针对规则可能源于不同的来源而产生的一致性问题，他们借鉴特征交互的经验，扩展无线传感技术，解决在无线传感器网络中不同来源的冲突规则导致一致性维护问题.Born 等人27通过扩展模型转换工具，解决基于规则的模型转换中发生的冲突和依赖.Jiang等人28针对一个大型自组织系统中子系统间具有利益和价值的冲突问题，使用逻辑形式化事件推演，使得每个子系统能够发现和解决其系统自身内部的规则冲突.Zhang 等人29通过计算概率描述节点状态作业的权重，得到逻辑推理规则的冲突度量.Diller 等人30提出一种从不一致的语言中提取语义的方法，并以正态性假设的形式扩展规则表达方式，解决规则中自然语言表达知识产生的冲突，然而他们没有考虑物联网系统中的规则冲突.Shehara 等人5提出一种需求交互分类法，用于对软件系统中的需求交互进行分类和识别，并提出一种半形式化的冲突检测方法（IRIS）来识别需求冲突，并且开发可以应用到特定领域的插件31.Shah 等人32提出一种检测物联网系统中不完整规则的机制，同时考虑条件独立的触发条件引起的规则冲突，这种方法把规则看作使用基于事件的编程语言的程序，实现对规则不完整性和冲突的检测，然而能检测的冲突类型不够全面.李秀33基于知识图谱，对智能家居领域内的作动器杨波等：一种针对物联网智能系统的规则冲突检测方法595进行隐式冲突检测，根据作动器功能进行自动分类，实现不限类型的作动器设备之间的隐式规则冲突检测.Lin 等人34通过设计规则的形式化模型，把这些规则定义为一个元组，包含触发器、执行器和状态，然后通过分类、组合的方法对规则进行处理，从而描述规则之间的冗余关系，消除和避免冗余的规则出现，提高系统执行效率.本节所提的研究工作对规则冲突类型分析不全面，并且检测结果的准确性不高，造成规则冲突漏检和错检的问题.本文工作对这些形式化方法进行改进，针对物联网系统的规则冲突进行检测.2方法 2.1针对物联网系统的规则的形式化分析为了更清楚地表达物联网系统中的规则，以及区分不同的规则冲突类型，本文针对物联网系统中的规则，给出相应的形式化结构.物联网规则涉及到控制主体、动作、触发条件、规则、符号 5 个成分，具体结构如图 4 所示.subactioncondition-type-attribute-op-value-sub:sub-attribute-op-value-id-type-mon-attribute-valuerule-id-conditions:Condition1*-actions:Action1*Fig.4Rulestructure图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.N动作的集合表示为 actions=action（i）|0 in，n.3）触发条件 condition 由控制主体类型 type、约束属性 attribute、约束关系运算符 op、约束属性值value 构成.其中 type 表示引用上述规则成分中的控制主体 sub 里的元素 type.触发条件可表示为 condition=type，attribute，op，value.N触 发 条 件 的 集 合 可 以 表 示为 conditions=condition（i）|0 in，n.4）规则 rule 由 id 标识、触发条件 conditions、动作 actions 构成.规则可表示为 rule=id，conditions，actions.N规则的集合可以表示为 rules=rule（i）|0 i”，(,value),op=“”，value,+),op=“”，(,value,op=“”，(,value)(value,+),op=“”.其中 value 是一个数值，在添加符号#后，数值 value与关系符 op 进行运算，将数值 value 转换成连续的区间范围；代表负无穷，+代表正无穷，（）是开区间，是闭区间，（是开闭区间，）是闭开区间.通过以上规则结构表示，可以清晰地表达下面的规则交互关系.2.2规则的交互关系规则间的冲突是由规则交互关系引起的，为了深入分析规则冲突类型，首先分析规则交互关系.2个规则的约束条件部分和动作部分的影响，称为规则的交互关系.通过对规则间存在的交互关系进行分析，总结出相容触发条件、控制同一非独占主体、控制同一独占主体、相同控制动作、相反控制动作、互斥影响值、规则 Ri触发条件依赖规则 Rj的动作、规则 Ri触发条件依赖规则 Rj的反向动作，8 种规则交互关系如表 1 所示.1）CC 表示 2 个规则可以在同一个系统场景中触发，称为相容触发条件；2）SSS 表示 2 个规则控制同一个非独占类型主596计算机研究与发展2023，60（3）体，称为控制同一非独占主体；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规则的冲突类型由于规则之间存在交互关系，使得规则间产生冲突.为了更清晰地描述规则的冲突，本文通过调研和分析物联网系统中的规则交互关系，将目前的物联网系统中的规则冲突分为类，分别是:执行覆盖冲突、执行矛盾冲突、消极影响冲突、独占资源冲突、直接忽略依赖冲突、直接循环依赖冲突、间接循环依赖冲突.规则的冲突类型以及形式化表达如表 2 所示.Table 2Rule Conflict Type表 2 规则冲突类型冲突类型形式化表达关系执行覆盖冲突CCSSS SA非对称执行矛盾冲突CC SSS DA对称消极影响冲突CC MV对称独占资源冲突CC SMS对称直接忽略依赖冲突OR（Ri，Rj）非对称直接循环依赖冲突RC（Ri，Rj）RC（Rj，Ri）对称间接循环依赖冲突RC（t1，t2）RC（t2，t3）RC（ti1，Ri）RC（Ri，t1）对称类规则冲突所表达的含义为：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，调换规则表述顺序后，表达的语义不一样，属于非对称关系.经过以上的规则冲突类型总结以及形式化定义，总结出物联网智能系统中规则冲突的特点，并且能对这些规则冲突进行区分，能够比较容易地对这些冲突进行检测.Table 1Rule Interaction表 1 规则交互关系交互关系名称符号表示相容触发条件CC（ComCon）控制同一非独占主体SSS（SamShareSub）控制同一独占主体SMS（SamMonSub）相同控制动作SA（SamAct）相反控制动作DA（DifAct）互斥影响值MV（MutVal）规则 Ri触发条件依赖规则 Rj的动作RC（Ri，Rj）（RelyCon）规则 Ri触发条件依赖规则 Rj的反向动作OR（Ri，Rj）（OppRely）杨波等：一种针对物联网智能系统的规则冲突检测方法597 2.4基于形式化规则的冲突检测方法规则冲突检测方法流程如图 5 所示.该方法流程主要包括 2 部分，分别是规则预处理和规则冲突计算.规则预处理规则元素库规则元素规则分解规则解析待检测的规则待检测的规则规则库规则库规则冲突计算规则交互关系分析规则冲突检测规则交互关系规则冲突检测结果Fig.5Theworkflowofruleconflictdetectionmethod图5规则冲突检测方法流程规则冲突检测方法的输入是已有的规则库和待检测的规则，已有的规则库是指在进行规则冲突检测之前，就已经存在的规则集合；待检测的规则是指需要与已有规则库进行检测是否存在冲突的规则.在进行规则检测前，需要对输入的规则库和待检测规则进行预处理.首先，需要将规则解析成粒度较小的规则元素，目的是将输入的规则解析成可以用作形式化表达的元素.随后进行规则分解，目的是将复杂的规则分解为只包含与逻辑关系的规则.规则预处理之后，得到分解之后的规则库与待检测的规则.接下来需要对规则冲突进行分析，通过规则交互关系分析和规则冲突检测，得到最终的规则冲突检测结果.2.4.1规则预处理规则预处理包括规则解析和规则分解 2 个步骤.规则解析的目的是将输入的规则解析成可以形式化表达的元素.首先，待检测的规则和规则库里的规则输入到规则解析子模块；然后，根据物联网系统规则的形式化结构，将文本类型的规则解析成由 id标识、触发条件 conditions、动作 actions 构成的形式化元素；最后，分别输出规则元素库和规则元素.规则分解是为了简化包含复杂逻辑的规则，这样可以便于后续的规则冲突检测.本文利用析取范式将规则进行分解.例如规则 R1经过析取范式转化得到 R2，R2可以表达为触发条件只包含“与”逻辑关系的 2 个规则 R3和 R4.此过程将同时包含“与”“或”逻辑关系的规则 R1，分解成为只包含“与”逻辑关系的规则 R3和 R4.R1:(c1c2)c3 a1,a2,an.R2:(c1c3)(c2c3)a1,a2,an.R3:c1c3 a1,a2,an.R4:c2c3 a1,a2,an.规则分解步骤首先输入规则元素库和规则元素；然后，经过上述析取范式分解；最后，输出分解之后的规则库与待检测的规则.2.4.2规则交互关系分析规则交互关系分析是后续规则冲突检测的基础，对于任意 2 个规则，它们之间的交互关系可以采用 4 个步骤进行分析，首先，遍历 2 个规则的约束部分和动作部分；其次，获取规则的形式化元素；然后，将形式化元素依据规则交互关系形式化表达，匹配出相应的规则交互关系；最后，输出 2 个规则的交互关系.规则交互关系分析如算法 1 所示.算法 1 输入规则 Ri和 Rj，输出规则关系 re.算法 1 的行分别遍历 Ri和 Rj的约束 conditions 部分和动作 actions 部分.行获取规则的形式化元素，依据表 1 定义的规则交互关系，设置规则关系变量 re 的标志位.行输出存储 2 个规则交互关系的变量 re.最终计算出待检测规则与规则库所有规则的交互关系.规则交互关系名称用表 1 中符号缩写表示，部分符号依赖于图 4的规则结构.算法 1.规则交互关系分析算法.输入：规则 Ri，规则 Rj；输出：规则交互关系 re.relation（Ri，Rj）；for（AC Ri.conditions，AA Ri.actions）for（BC Rj.conditions,BA Rj.actions）if!（2 个规则条件部分 type 和attribute 相同 and 它们的598计算机研究与发展2023，60（3）op#value 没有交集）thenre.CC=1；endifif（2 个规则动作部分控制同一个suband 它们不是独占设备）thenre.SSS=1；elseif（2 个规则动作部分控制同一个 suband 它们是独占设备）thenre.SMS=1；endifendforif（2 个规则动作部分的 type 相同and 它们的 op#values 是包含关系）thenre.SA=1；endifif（2 个规则动作部分的 type 相同and 它们的 op#value 没有交集）thenre.DA=1；endifif（2 个规则的动作部分控制不同的suband 它们的 op#value 没有交集）thenre.MV=1；endifif（1 个规则的条件部分 value 另一个规则动作部分的 op#valueand条件部分和动作部分的 attribute 相同）thenre.RC=1；endifif（1 个规则条件部分的 value另一个规则动作部分的 op#value 的补集and条件部分和动作部分的attribute 相同）thenre.OR=1；endifendforretutnre.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.规则冲突检测算法.输入:规则库 RDB，规则 Ri；输出:冲突信息 conflictInfo.detect（Ri，RDB）；定义 MAP 类型变量 relyM；for（IA RDB）定义 Queue 类型变量relyQ；for（IB RDB）RAB=relation（IA，IB）；if（IA.idIB.idandRAB.RC）thenIB 存入 relyQ,Ri.id 作为键，relyQ作为值存入 relyM；endifendforendforfor（Rj RDB）re=relation（Ri，Rj）；conflictInfo=matchConflict（re，relyM）；if（conflictInfo）thenreturnconflictInfo；endifendforreturn“NoConflict”.杨波等：一种针对物联网智能系统的规则冲突检测方法5992.4.4规则冲突检测实例通过算法 1 和算法 2 的实现，可以在任何情况下检测到图 3（a）和图 3（b）中的规则冲突.对于图 3（a），2 条规则 R1，R2经过规则预处理分别得到：conditionR1=roomEnvironment,temperature,，27；conditionR2=roomEnvironment,temperature,，20；actionR2=air_conditioner，temperature，15.规则 R1，R2通过规则交互关系分析，conditionR1中的 roomEnvironment,temperature 与 conditionR2中的 roomEnvironment,temperatur