EasiRCC：面向智能家居的规则匹配与冲突消除方法

黄晓辉 李 栋 石海龙 崔 莉

1(中国科学院计算技术研究所 北京 100190) 2(中国科学院大学 北京 100049)

EasiRCC：面向智能家居的规则匹配与冲突消除方法

黄晓辉1,2李 栋1石海龙1崔 莉1

1(中国科学院计算技术研究所 北京 100190)2(中国科学院大学 北京 100049)

(huangxiaohui@ict.ac.cn)

在智能家居中，规则间的冲突问题会直接影响系统的稳定性，针对智能家居的规则冲突问题，提出了一种新型的快速规则匹配和冲突消除方法EasiRCC.解决冲突问题，首先要解决规则的匹配问题，现有的规则匹配方法频发重复匹配现象，造成了系统资源的浪费，针对规则的重复匹配问题，提出了一种基于散列函数寻址方式的快速规则匹配算法EasiRMA，提高了规则匹配效率.其次要解决冲突的消除问题，现有的方法都是采用固定优先级方法来消除冲突，但是却增加了用户制定规则的复杂度，因此提出了一种混合优先级调度机制，使系统可以实时地自适应调整规则的执行优先级.实验结果显示:EasiRCC的规则匹配效率不会随着规则数的增多而变化，其时间复杂度为常数，而传统的匹配方法为O(N)，并且在不影响用户正常家居生活的前提下，能够有效地消除规则冲突.

物联网；智能家居；规则匹配；散列函数；冲突消除；混合优先级

自1999年由麻省理工学院提出“物联网(Internet of things, IOT)”的概念以来[1]，物联网作为一个新兴的信息技术领域，早已受到世界各国政府、学者以及企业的极大关注.智能家居(smart home, SH)是通过物联网技术，将空调控制、安防监控、照明系统、环境监测等各种设备连接在一起，提供用户全方位的家居信息交互功能[2].最初的智能家居，只是简单实现家居环境的温度、湿度等生活环境相关参数的采集，然后根据采集到的数据再对家用电器进行简单的控制功能.近年来，智能家居向着控制功能的网络集中化管理方向发展，可根据不同的用户需求实现家居环境的个性化和定制化服务功能，而这些服务的功能都是通过用户设定的规则来实现，比如可以制定一条服务规则为“当湿度低于60%时，打开加湿器”，当室内的湿度低于60%时，系统就会打开加湿器来增加室内的湿度.

伴随着智能家居行业的飞速发展，人们根据需求制定的服务规则越来越多.由于规则数量的增多，对于规则之间的相互关系用户很难考虑周全，很容易发生规则之间的执行冲突，影响整个家居系统的稳定性，甚至威胁到人们的生命健康问题.比如规则1“当检测室内温度高于30℃时，打开空调降温”，规则2“当所有电器设备的功耗达到1.5 kW时，关闭空调”，当室内温度高于30℃并且所有电气设备功耗达到1.5 kW以上时，规则1和规则2同时执行对空调的开和关动作，就会引起冲突，影响系统稳定性以及用户自身的生活舒服感，所以，智能家居领域要得到更好的发展，解决规则冲突问题成了一个发展瓶颈.

现有的规则匹配和冲突消除机制很少是以智能家居为应用背景的，而目前针对智能家居的研究工作都存在着共同的问题：

1) 规则匹配过程中重复匹配现象频发，规则的匹配效率低，仅适用于规则较少的情况，规则数目增多会导致系统计算资源的浪费；

2) 消除冲突的方法，多数都需要通过用户给每个规则预设一个固定优先级来避免冲突，系统不能自适应地消除冲突，增加了用户制定规则的复杂度.

针对智能家居中存在的规则匹配和冲突问题，本文提出了一种新型的快速规则匹配和消除的方法EasiRCC.该方法首先根据智能家居服务规则的特点，制定了规则描述方法，基于散列函数寻址方式直接将规则中的触发条件匹配到相应的规则，提高了规则的匹配效率.然后，结合不同类型的规则所具有的静态优先级，再根据规则的触发方式动态调整规则的执行优先级来消除规则间的冲突.

本文的贡献主要集中在3个方面：

1) 提出了一种基于散列函数寻址方式的快速规则匹配算法EasiRMA，消除了规则的重复匹配现象，提高了规则的匹配效率;

2) 根据规则的类型和触发方式，结合静态和动态优先级，提出了一种混合优先级调度机制，消除了控制规则之间的冲突;

3) 通过实验验证了EasiRCC的有效性.

1 相关工作

近年来，针对智能家居规则冲突问题的研究，大多都集中在规则的冲突检测上，忽略了规则的匹配问题.冲突检测是建立在规则成功匹配的基础上，所以，首先要解决的是规则的匹配问题.目前，多数的研究工作都是采用顺序匹配方法来实现规则的匹配，致使规则的重复匹配现象频发，造成系统资源的浪费.

目前，常用的匹配算法有Rete,Leaps,Liner,Treat[3]，其中很多规则推理引擎都是基于Rete算法来进行推理的，比如Drools,JBoss Rules[4]等.Rete算法的核心思想是：利用基于规则的系统具有时间冗余性和结构相似性的特征，通过节点状态的共享和保存这2种方式来提高匹配的效率[4].这种方法的缺点是：1)存在状态重复保存的问题，占用较多空间并影响匹配的效率；2)处理大规模和实时变化的数据时效率较低，不适合应用于实时性要求较高的智能家居场景中.文献[5-8]中的研究工作，采用的是顺序匹配的方法，在实现规则的匹配过程中，都是通过将触发条件与规则库中的每条规则进行逐条匹配的方法来实现的，这种顺序匹配方法进行了多次的重复匹配，造成系统计算资源的浪费.假定规则库中有N条规则，在最坏的情况下可能会造成N-1次无效匹配，匹配的时间复杂度为O(N).

规则匹配完成后，针对规则间存在的冲突问题，Munir等人[5]提出的一种针对智能家居的集成传感资源和执行资源的一种架构——DepSys，为解决多应用并发运行引起的冲突问题，提供了一个通过处理一些相关依赖关系的规范、检测、解决冲突的策略方案.Dixon等人[6]搭建了一个HomeOS虚拟PC操作平台，家里的所有设备都作为外设(peripherals)连接到这个虚拟PC上，用户可通过一个中央操作系统(centralized operating system)对这些设备上的数据信息进行操作，为用户提供一个应用管理接口.但是，HomeOS并没有考虑控制规则间的冲突检测，只是通过赋予所有控制规则一个固定优先级来消除冲突.Sun等人[7]提出了一种基于UTEA(user triggers environment actuators)的形式化规则模型的冲突检测机制，首先将规则的相互关系定义为11种，并基于这些规则间的相互关系定义了5种规则冲突类型；然后将复杂规则分解成多个基本规则，并通过形式化规则模型来提取和分析这些基本规则间的相互关系；最后匹配规则间的相互关系，再通过规则冲突检测算法判断规则间属于哪种冲突类型.上述文献的工作，在规则匹配完成后，被激活的规则如果存在冲突，都是通过为每条规则预设一个固定优先级来消除冲突，这就要求用户在制定规则时需要为每条规则设定执行顺序，这无疑增加了规则制定过程的复杂度，给用户带来很大的不便.针对目前相关研究工作的这些不足，表明需要一种以智能家居为应用背景的快速规则匹配方法和冲突消除机制.

2 EasiRCC概述

EasiRCC的结构如图1所示，主要包括规则匹配与冲突检测模块(rule-matching and conflict detection module)、冲突消除模块(conflict resolution module)、规则处理网关(gateway)传感器节点(sensor)和执行设备(actuator).规则匹配与冲突检测模块负责匹配规则，并将激活的规则送入冲突检测模块，检测到存在冲突的规则就列入冲突集中，等待冲突消除模块进行处理；冲突消除模块用于消除冲突集中的规则冲突问题，当接收到冲突集中的规则后，首先对规则进行分类排序，然后通过混合优先级调度模块对规则进行自适应动态调整执行顺序，再依次建立规则就绪队列，并由网关按照队列顺序对规则进行解析执行；规则处理网关，是整个系统的信息服务中心，不仅用于将传感器节点、执行设备和汇聚节点组建的网络接入到Internet，还负责实现规则匹配、冲突检测、冲突消除以及规则的解析执行[9].传感器节点用于感知室内的温度、湿度、光照等数据信息，并通过无线网络(ZigBee,Bluetooth,WiFi等无线近距离通信技术[10])传输至汇聚节点和网关进行处理.执行设备是直接作用于室内物理环境的任务执行设备，如空调、窗帘、灯、加湿器等家用电器或设备[11-12].

Fig. 1 Architecture diagram of EasiRCC图1 EasiRCC系统结构图

EasiRCC的主要功能部分是规则匹配与冲突检测模块和冲突消除模块.为了能够在智能家居的网关设备上实现规则的快速匹配，我们在该模块中实现了一种快速规则匹配算法EasiRMA，通过在规则触发条件与规则集之间建立一一映射的对应关系，可根据输入的触发条件信息数据直接定位寻址到相应的规则，提高了规则的匹配效率.根据规则的匹配结果，就能够判断规则间是否存在冲突，本文目前仅是检测执行矛盾冲突.在冲突的消除机制上，结合静态和动态优先级，通过一种混合优先级调度机制自适应调整规则执行顺序来消除冲突.

3 规则匹配与冲突检测

3.1 规则的描述与分类

在智能家居中，提供的服务是由事先制定的规则来保证的，用户可以通过增加和修改规则来实现所需要的服务[8].例如用户制定了规则“室内温度高于28℃，打开空调降温”，即室内温度高于28℃时，系统打开相应的空调进行降温，使得室内温度降到28℃.一般家庭所制定的规则都是if/then形式，if后面是触发动作的条件，then后面是达到触发条件后要执行的动作.我们所设定的规则表示形式中，if后面仅有一个条件部分，then后面也仅有一个执行动作.

规则的实现就是从对应的传感器中获取特定的数据信息，并利用这些数据信息对执行设备进行预定的控制.为了更好地描述和管理规则，根据规则的实现过程，我们可以从规则属性、运行状态、触发条件以及执行部分来定义规则.

定义1. 一条规则可表示为Rule={Rule_Au,Rule_Sta,Trigger_Con,Actuator}，其中Rule_Au,Rule_Sta,Trigger_Con,Actuator分别是规则属性、规则状态、触发条件和执行部分.

如表1中所示，规则属性Rule_Au={Rule_ID,Rule_Typ,Rule_Pro}，其中，Rule_Pro设定了规则的优先级，这个优先级类似于超级用户的权限；规则状态Rule_Sta=0,1，表示规则是否被激活；触发条件Trigger_Con={Trigger_Typ,Trigger_ID,Trigger_Value,Trigger_Value_Au}，假定温度传感器的ID=20，那么“温度大于30℃”可表示为{1,20,30,1}；执行部分Actuator={Actuator_ID,Actuator_Value}，假定空调的ID=10，那么“打开空调”可表示为{10,1}.例如一个规则为“当室内温度大于30℃时，打开空调降温”，我们设定规则ID=100，执行优先级为12，那么通过规则的描述定义，该规则可表示为Rule={100,1,12,0,1,20,30,1,10,1}.

Table 1 Parameter Description of Rule表1 规则表示参数描述

为了更全面、更方便地表达和管理各种不同的规则，我们把规则分为5种类型：健康监护类(health supervision, HS)、安全控制类(security control, SC)、环境监控类(environmental monitor, EM)、娱乐控制类(media control, MC)、能量管理类(power management, EM)，对应的Rule_Typ值为000,001,010,011,100.健康监护类规则，与用户生命健康相关的规则都属于这类规则；安全控制类规则，主要是涉及到生活环境安全相关的规则；环境监控类规则，主要是负责监控与温度、湿度、光照等环境因素相关的规则；娱乐控制类规则，这类规则都是与娱乐相关的内容；能量管理类规则，负责调节管理整个家居系统的能量消耗.

3.2 EasiRMA规则匹配算法

目前，由于智能家居中用户设定的规则数目较少，如文献[5-8]中都是采用顺序规则匹配方法.顺序规则匹配的原理是：让触发条件与规则队列中的规则从最后一个往前逐个匹配，直到找到与触发条件信息相同的规则为止.这种匹配方法的特点是:1)算法简单，易于实现；2)对规则存储结构无要求.

定义2. 给定一个规则集R={r1,r2,…,rn}，在得到一个触发条件信息c后，c与规则集R中的n个规则的条件部分进行匹配的期望次数为平均匹配长度AML(average matching length).

由定义2可知，对n个规则进行匹配时，平均匹配长度为

(1)

(2)

在最坏的情况下，顺序匹配需要匹配n次，即时间复杂度为O(n).

由上述可知，顺序匹配最大的缺点是平均查找时间较长、时间开销大，只适用于规则数目很少的情况.但是，随着智能家居的发展，用户制定的规则数量很大时，匹配过程带来的时间开销将会影响系统的实时性.

为了在消除顺序规则匹配过程中带来的重复匹配现象，我们提出了EasiRMA快速规则匹配算法.其主要思想是利用散列函数在触发条件key与规则集之间建立一一映射的对应关系，根据得到的key通过散列函数计算Hash值，由Hash值可直接定位规则集中与之相对应的规则，无需匹配规则集中的所有规则，提高了规则的匹配效率[12-13].

EasiRMA的匹配过程如图2所示:

Fig. 2 Route chart of EasiRMA rule-matching图2 EasiRMA规则匹配工作流程图

key为时间或传感器节点的数据关键字,经过C分类后，若为时间数据，key=Trigger_Value，若为事件类型数据，即温度、湿度等传感器的数据，key包括Trigger_ID,Trigger_Value,Trigger_Value_Au.

(3)

key通过C分为time和event后，分别经过散列函数RT(x)和RE(x)映射到Hash Rule Table1和Hash Rule Table2中，为减少规则匹配过程中发生冲突，Hash Rule Table1和Hash Rule Table2都采用线性直接寻址方法匹配规则，RT(x)和RE(x)散列函数：

RT(key)=key,key=time，

(4)

RE(key)=key,key=event.

(5)

在Hash Rule Table1中，由于key属于time类，并且在time仅精确到1 min，所以我们给Hash Rule Table1开放1 500个元素空间，完全可以满足1 d的时间设定需求.但是，也有可能在同一时间触发多个规则，比如“8:00am拉开窗帘并打开窗户”，针对这种多规则的匹配情况，我们采用地址链表(address linked list)法来实现同一时间下多个规则的匹配问题，即将同一时间下触发的规则以表的形式存储在其中.在Hash Rule Table2中，匹配方式与Hash Rule Table2相同，区别在于散列函数的选取上，遇到多规则匹配冲突时也是采用地址链表法.

EasiRMA伪代码描述如算法1所示：

算法1. EasiRMA规则匹配算法.

输入：Ri,key；

输出：R.

① 初始化规则队列RT[m]和RE[n]；

② For (每一个规则)

③ 根据规则Ri的类型计算Hash值RT(keyi)和RE(keyi),并分别存入RT[m]和RE[n]规则队列中；

④ If 存在2个以上的RT(keyi)或RE(keyi)值相等采用地址链表法存储这些规则；

⑤ End If

⑥ End For

⑦ 从传感器数据和时间中得到key值；

⑧ IfC(key)==time

⑨ID=RT(keyi)；

⑩R=RT[ID],激活并输出规则R；

3.3 冲突检测

由3.2节中所述，由EasiRMA规则匹配算法得到规则激活集，其中的规则都是等待执行的，但是并没有检测这些规则间是否存在冲突.目前，本文仅考虑规则的矛盾冲突.规则冲突检测是建立在规则匹配的结果上进行的，得到规则激活集后，通过检测规则中Actuator_ID和Actuator_Value，对用执行设备的标识号和执行设备的属性值，检测到激活集中具有相同Actuator_ID并且Actuator_Value相反的规则，则判断为存在冲突，然后把这些规则存入到冲突集中，并交由冲突消除模块做进一步处理.

4 冲突消除方法设计

4.1 规则分类优先级设置

由3.1节中可知，将规则分为5类：健康监护类HS、安全控制类SC、环境监测类EM、娱乐控制类MC、能量管理类PM，文献[5-8]中的工作都是需要用户为每个规则都设定一个固定优先级，每个规则都按固定顺序执行，以避免冲突.本文中，我们通过选择200名志愿者，要求每一位志愿者从5类规则中选择自己比较感兴趣的，或者认为对家居生活比较重要的3类规则，并对最后的数据进行了汇总.如图3所示，按照兴趣度以及重要性的排序为：健康监护类>安全控制类>环境监控类>娱乐控制类>能量管理类.通过这个排序，我们从高到低依次设定每一类型的优先级.

Fig. 3 Survey data of smart home’s applications图3 智能家居应用类型调查汇总

4.2 混合优先级调度算法

由4.1节可知，5类规则都赋予每一类规则一个固定的优先级，当2个冲突的规则都属于同一类规则时，它们的优先级相同，无法用固定优先级来避免冲突.针对同一类型规则间的冲突问题，文献[5-7]采用事先设定每一类型内的所有规则的执行顺序来避免冲突.我们提出了一种混合优先级调度算法，针对同一类型内的规则采用相应的优先级调度方法.

规则的条件触发方式主要包括时间和事件触发方式，如规则“在6:00pm—8:00pm时，打开室内所有的照明灯”属于时间触发方式的规则，规则“当室内温度高于28℃时，打开空调降温”属于事件触发方式的规则.时间触发方式的规则，都有固定的触发时间以及执行模式，而事件触发方式的规则没有固定的触发时间，是由感知节点的数据信息来触发的，比如温度、湿度、光照等传感器数据，实时性比时间触发方式高，所以我们设定事件触发方式的规则优先级大于时间触发方式的规则.对于这2种规则，应该分别采用相应的规则执行优先级调度算法，文献[8]对所有的规则都采用预先设定固定优先级来避免冲突，并没有加以区别考虑.本文提出的混合优先级调度算法，根据不同的触发方式动态调整规则的执行优先级，不需要为每条规则都设定优先级，简化了规则的定义过程.

我们在以时间为触发方式的规则中采用高响应比优先调度算法[14](highest response ratio next，HRRN).HRRN将响应比Rp作为时间触发方式规则的执行优先级，Rp的计算过程：

(6)

其中，n为规则冲突集中的规则数，t为每个规则之间切换的时间间隔，TSi(i∈n)为每个规则的执行服务时间，TS0为当前规则的执行服务时间.

我们在以事件为触发方式的规则中采用先来先服务算法[15](first come first service， FCFS).不同类型的两条或更多规则进入规则激活集模块中，经过规则冲突检测模块时，若存在冲突，并且属于事件触发方式的规则，采用FCFS算法来避免冲突.如图4所示，激活的规则按照被激活的先后次序进入规则激活队列，排在队首的规则最先执行，队尾的规则需要等待排在前面的规则执行完毕才能获得执行权(token).

Fig. 4 Scheduling flow of FCFS图4 FCFS规则调度流程

混合优先级算法是建立在固定优先级的基础上，根据规则的触发方式采用相应的规则调度算法来消除冲突，保障家居设备的安全运行.混合优先级调度算法实现过程如图5所示.当激活的规则中存在冲突时，首先判断规则是否属于同一类型，如果不是同一类型，直接按照4.1节中定义的规则类型优先级依次执行规则，如果是同一类型，需要判断规则的触发方式，属于时间触发方式的规则，采用FCFS规则调度算法来消除冲突，属于事件触发方式的规则，采用HRRN规则调度算法来消除冲突.判断规则的触发方式时，有可能冲突的规则不是属于同一种触发方式的规则，那么还需要按照规则触发方式对规则进行分组，分组后事件触发方式和时间触发方式的规则分别通过FCFS,HRRN算法进行分组排序，最后再根据事件触发规则的优先级大于时间触发规则的优先级,R(event)>R(time),进行统一排序，并依次执行规则.

Fig. 5 Workflow of mixed-priority algorithm图5 混合优先级调度算法工作流程

5 实验结果与分析

为了验证EasiRCC的有效性和可行性，我们基于EZ6410网关设备[16]和EZ240感知节点[17-18]部署了实验验证平台，如图6所示.EZ6410主要由CPU、存储模块以及各种通信模块组成，包括ARM(S3C6410)、FLASH(1 GB)、RS232接口、以太网接口(DM900A)、嵌入式WiFi模块以及802.15.4模块(CC2420).EZ240感知节点采用超低功耗的MSP430F1611作为MCU，具有48 KB的ROM和10 KB的RAM，集成高精度的SHT11光照传感器和TSL2561温湿度传感器，采用符合802.15.4协议的CC2420射频芯片作为数据通信模块.

Fig. 6 Picture of real devices of experiment图6 实验平台实物图

Fig. 7 Average computing time of EasiRMA图7 EasiRMA的平均匹配时间开销

5.1 EasiRMA规则匹配效率

文献[7]中采用的顺序规则匹配算法，我们已经在3.2节中进行了分析，顺序规则匹配的时间复杂度为O(N)，N为智能家居系统中的规则数目.而我们提出的EasiRMA规则匹配算法，是在规则的触发条件与规则之间建立一一映射的关系，根据输入的触发条件数据信息，直接寻址到规则的存储地址，提高了规则的匹配效率.为了验证EasiRMA的有效性，我们在EZ6410中建立了一个规则库，规则数目从50条增加到1 000条，顺序规则匹配与EasiRMA规则匹配算法的平均匹配时间开销如图7所示.从图7中我们可以看出，顺序规则匹配算法随着规则数目的增加，匹配过程所耗费的时间也相应地增加，算法所耗费的时间总体呈线性增加，时间复杂度为O(N).EasiRMA算法随着规则数目地增加，耗费的匹配时间开销基本没有变化，算法的时间复杂度近似为一个常数.由图7所示，当规则数目大于145时，EasiRMA的匹配效率高于顺序规则匹配算法.

5.2 混合优先级调度性能分析

规则间存在冲突时，文献[5-8]中的工作都是要求用户在制定规则时预先为每个规则设定一个固定优先级来避免冲突.本文提出的混合优先级调度算法，结合静态和动态优先级，能够自适应地调整规则的执行优先级.规定优先级方法因为已经为每个规则预设了一个固定优先级，无需再经过多余的计算，可直接通过固定优先级消除冲突.但是，由我们提出的混合优先级调度算法需要根据计算结果来自适应地调整规则的执行优先级，与固定优先级相比，混合优先级调度算法计算开销高于固定优先级.为了分析算法的计算时间开销，结合文献[5]关于规则和冲突数量的选择，我们设定了2～40条存在冲突的规则，通过混合优先级调度算法消除了冲突，消除冲突需要额外耗费的计算时间如图8所示：

Fig. 8 Time of conflict resolution of mixed-priority algorithm图8 混合优先级调度算法的冲突消除时间

从图8可以看出，在消除冲突上的时间开销上，随着冲突规则数的增加，混合优先级调度和固定优先级调度算法都是呈增长趋势，后者的增长速度高于前者.因为混合优先级方法综合考虑了冲突规则的执行时间、等待时间以及激活的先后次序，而固定优先级方法仅考虑了每个规则的执行优先级，所以，当冲突的规则数越多，混合优先级调度算法的优势更为明显.由图8可知，当冲突的规则数达到30时，固定优先级所耗费时间为38 ms，混合优先级所耗费的时间仅为14 ms.

为了分析EasiRCC消除规则冲突的有效性，我们分别制定了不同数量的规则集，每个规则集都存在不同的冲突规则，表2中列出了规则集、存在的冲突规则数、冲突消除量以及冲突消除率.

Table 2 Results Summary of Conflict Resolution for EasiRCC表2 EasiRCC的冲突消除结果统计

从表2中可以看出，EasiRCC的冲突消除率在94.7%以上，规则集2,4,5的冲突消除率低于规则集1,3中的冲突消除率，主要是因为规则集2,4,5通过HRRN调整执行优先级后，仍然存在优先级相同的规则，我们对这些调整优先级后仍然具有相同执行优先级的规则进一步采用FCFS算法可消除冲突.目前，在智能家居领域中的规则冲突检测和消除的方法主要有HomeOS[6],DepSys[5],UTEA[7],SPIDER[19],IRIS[20]等，EasiRCC与这些方法在冲突消除方面的性能对比如表3所示:

Table 3 Conflicts Resolution Comparison BetweenTraditional Method and EasiRCC

Notes: “√” represents that the method is available for the condition; “×” represents that the method is unavailable for the condition.

表3中，“√”表示该方法具备该项性能；“×”表示该方法不具备该项性能.HomeOS,DepSys,UTEA都能够处理2个以上的规则冲突；而SPIDER,IRIS仅能处理2个规则冲突，不能处理3个以上的规则冲突.上述方法都是采用设定规则的执行优先级来消除冲突，在制定规则时需要用户为每个规则预设一个固定的执行优先级，并且该优先级无法再改变.本文提出的EasiRCC，不仅能同时处理多个规则冲突，而且无需用户为每个规则设定执行优先级，降低了用户制定规则的复杂度，使得系统能够实时地自适应调整规规则的复杂度，使得系统能够实时地自适应调整规则的执行优先级来消除规则间的冲突，保证系统的稳定性和安全性.综上所述，EasiRCC能够有效地消除规则冲突.

6 总结与展望

本文在对智能家居的研究现状以及未来的发展趋势的基础上，针对系统中频发的规则重复匹配以及规则冲突的问题，提出了一种规则快速匹配与冲突消除方法EasiRCC.针对规则重复匹配的问题，EasiRCC提出了EasiRMA规则匹配算法，该算法在触发条件与规则之间建立一一映射的方法，根据输入的触发数据信息可直接寻址到相应的规则，消除了规则重复匹配的现象，提高了规则匹配的效率.而在消除规则冲突的问题上，之前的研究工作都是采用制定规则时预设规则的执行优先级来消除冲突，但是，随着规则数目的增多，这种方法增加了规则制定的复杂度.而我们在保证不影响用户正常的家居生活的前提下，结合静态和动态优先级，提出了一种混合优先级调度机制，系统可以根据规则属性实时的自适应调整规则的执行优先级来消除冲突.

在消除规则冲突的问题上，本文仅针对规则的执行矛盾冲突，即同时对家居设备进行开或关的操作导致的执行矛盾问题，并没有考虑其他的冲突类型，比如环境互斥、规则依赖、冗余冲突等.所以，在未来的工作中，我们将设计一种新型的规则冲突检测方法，然后结合EasiRCC综合考虑如何更好地提高智能家居系统的稳定性和安全性.

[1]Gershenfeld N, Cohen D. Internet 0: Interdevice internet-working end-to-end modulation for embedded networks[J]. IEEE Circuits & Devices, 2006, 22(3): 48-55

[2] Li Haiguang. Design and realization of smart home system based on rule engine[D]. Beijing: Beijing University of Posts and Telecommunications, 2015 (in Chinese)(李海光. 基于规则引擎的智能家居系统的设计与实现[D]. 北京: 北京邮电大学, 2015)

[3] Forgy C L. Rete: A fast algorithm for the many pattern/many object patternmatch problem[J]. Artifical Intelligence, 1982, 19(1): 17-37

[4] Gu Xiaodong, Gao Yang. Rete algorithm: Current issues and future challenges[J]. Computer Science, 2012, 39(11): 8-12 (in Chinese)(顾小东, 高阳. Rete算法: 研究现状与挑战[J]. 计算机科学, 2012, 39(11): 8-12)

[5] Munir S, Stankovic J. DepSys: Dependency aware integration of cyber-physical systems for smart homes[C] //Proc of ACM ICCPS’14. New York: ACM, 2014: 127-138

[6] Dixon C, Mahajan R, Agarwal S, et al. An operating system for the home[C] //Proc of the 9th USENIX Symp on Networked Systems Design and Implementation. New York: ACM, 2012: 25-40

[7] Sun Yan, Wang Xukai, Luo Hong, et al. Conflict detection scheme based on formal rule model for smart building systems[J]. IEEE Trans on Human Machine Systems, 2015, 45(2): 215-217

[8] Wang Xukai. Research and implementation on rules conflict detection in smart home system[D]. Beijing: Beijing University of Posts and Telecommunications, 2015 (in Chinese)(王栩凯. 智能家居系统规则冲突检测机制的研究与实现[D]. 北京: 北京邮电大学, 2015)

[9] Cui Li, Ju Hailing, Miao Yong, et al. Overview of wireless sensor network[J]. Journal of Computer Research and Development, 2005, 42(1): 163-174 (in Chinese)(崔莉, 鞠海玲, 苗勇, 等. 无线传感器网络研究进展[J]. 计算机研究与发展, 2005, 42(1): 163-174)

[10] Liu Qiang, Cui Li, Chen Haiming. Key technologies and application of Internet of things[J]. Computer Science, 2010, 37(6): 1-4 (in Chinese)(刘强, 崔莉, 陈海明. 物联网关键技术与应用[J]. 计算机科学, 2010, 37(6): 1-4)

[11] Zhao Ze, Yang Guanhua, Liu Qiang, el al. Implementation and application of a multi-radio wireless sensor networks testbed[C] //Proc of IEEE IET-WSS 2011. Piscataway, NJ: IEEE, 2009: 191-199

[12] Ding Zhenhua, Li Jintao, Feng Bo. Research on Hash-based RFID security authentication protocol[J]. Journal of Computer Research and Development, 2009, 46(4): 583-592 (in Chinese)(丁振华, 李锦涛, 冯波. 基于Hash函数的RFID安全认证协议研究[J]. 计算机研究与发展, 2009, 46(4): 583-592)

[13] Liu Yong, Xiong Rong, Chu Jian. Quick attribute reduction algorithm with Hash[J]. Chinese Journal of Computers, 2009, 32(8): 1493-1499 (in Chinese)(刘勇, 熊蓉, 褚健. Hash快速属性约简算法[J]. 计算机学报, 2009, 32(8): 1493-1499)

[14] Liu Hong, Xu Ningyi, Zhou Zucheng, et al. New HRRN in the bus arbitration of SOC design[C] //Proc of the 5th Int Conf on ASIC. Piscataway, NJ: IEEE, 2003, 1(1): 405-408

[15] Hofri M. DISK scheduling: FCFS vs SSTF revisited[J]. Communications of ACM, 1980, 23(11): 645-650

[16] Li Dong, Zhao Ze, Cui Li, et al. A cyber physical networking system for monitoring and cleaning up blue-green algae blooms with agile sensor and actuator control mechanism on Lake Tai[C] //Proc of the 1st Int Workshop on Cyber-Physical Networking Systems (CPNS’2011) in Conjunction with IEEE INFOCOM’2011. Piscataway, NJ: IEEE, 2011: 732-737

[17] Zhao Ze, Liu Qiang, Li Dong, et al. Easitest: Amulti-radio testbed for heterogeneous wireless sensor network[J]. Journal of Computer Research and Development, 2012, 49(3): 506-517 (in Chinese)(赵泽, 刘强, 李栋, 等. EasiTest: 多Radio异构无线传感器网络测试平台[J]. 计算机研究与发展, 2012, 49(3): 506-517)

[18] Zhao Ze, Shang Pengfei, Liu Qiang, et al. Identification of communication state for wireless sensor networks[J]. Journal of Computer Research and Development, 2014, 51(11): 2382-2392 (in Chinese)(赵泽, 尚鹏飞, 刘强, 等. 无线传感器网络通信负载状态识别方法的研究[J]. 计算机研究与发展, 2014, 51(11): 2382-2392)

[19] Hu Haibo, Yang Dan, Fu Li, et al. Semantic Web-based policy interaction detection method with rules in smart home for detecting interactions among user policies[J]. Institution of Engineering and Technology Communications, 2011, 5(17): 2451-2460

[20] Shehata M, Eberlein A, Fapojuwo A. A taxonomy for identifying requirement interactions in software systems[J]. Computer Networks, 2007, 51(2): 398-425

EasiRCC:AMethodofRule-MatchingandConflictResolutionforSmartHome

Huang Xiaohui1,2, Li Dong1, Shi Hailong1, and Cui Li1

1(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)

With the rapid development of the Internet of things, smart home based on Internet of things has gradually entered into family life of people. The user can accord to the requirement for personalized and customized service life. However, smart home systems appear conflicts between rules frequently, because the number of rules is becoming more and more. Therefore, this paper proposes EasiRCC, a new-type method of rapid rule-matching and conflict resolution. Resolving the conflict problem mainly focuses on rule-matching and conflict resolution. Firstly, for the problem of rule-matching, because repeating matching takes place in the existing methods frequently, we propose an algorithm named EasiRMA, which is used to fast match rule based on Hash function and raise the efficiency of rule-matching. Secondly, for the problem of conflict resolution, we come up with a scheduling mechanism of mixed-priority, which the system can adaptively adjust priority of rules, and resolve rule-conflict in time. Experimental results show that EasiRCC’s efficiency of rule-matching is not changing as the number of rules is increased, and its running time is constant, but the running time of traditional matching method isO(N), and EasiRCC can effectively resolve conflict in the condition that does not affect users’ normal household lives.

Internet of things; smart home; rule-matching; Hash function; conflict resolution; mixed-priority

2016-08-22；

2017-02-06

国家自然科学基金项目(61672498，61502461)；中国科学院计算技术研究所创新项目(20156010)

This work was supported by the National Natural Science Foundation of China (61672498, 61502461) and the Knowledge Innovation Program of Institute of Computing Technology, Chinese Academy of Sciences (20156010).

李栋(lidong@ict.ac.cn)

TP393

HuangXiaohui, born in 1987. PhD candidate. His main research interests include wireless sensor networks and Internet of things.

LiDong, born in 1979. PhD and associate professor. Member of CCF. His main research interests include sensor networks and Internet of things.

ShiHailong, born in 1984. PhD and assistant researcher. Member of CCF. His main research interests include Internet of things (shihailong@ict.ac.cn).

CuiLi, born in 1962. Professor and PhD supervisor. Senior member of CCF. Her main research interests include wireless sensor networks and Internet of things (lcui@ict.ac.cn).