EasiRCC：面向智能家居的規(guī)則匹配與沖突消除方法

黃曉輝 李 棟 石海龍 崔 莉

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190) 2(中國(guó)科學(xué)院大學(xué) 北京 100049)

EasiRCC：面向智能家居的規(guī)則匹配與沖突消除方法

黃曉輝1,2李 棟1石海龍1崔 莉1

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)

(huangxiaohui@ict.ac.cn)

在智能家居中，規(guī)則間的沖突問題會(huì)直接影響系統(tǒng)的穩(wěn)定性，針對(duì)智能家居的規(guī)則沖突問題，提出了一種新型的快速規(guī)則匹配和沖突消除方法EasiRCC.解決沖突問題，首先要解決規(guī)則的匹配問題，現(xiàn)有的規(guī)則匹配方法頻發(fā)重復(fù)匹配現(xiàn)象，造成了系統(tǒng)資源的浪費(fèi)，針對(duì)規(guī)則的重復(fù)匹配問題，提出了一種基于散列函數(shù)尋址方式的快速規(guī)則匹配算法EasiRMA，提高了規(guī)則匹配效率.其次要解決沖突的消除問題，現(xiàn)有的方法都是采用固定優(yōu)先級(jí)方法來消除沖突，但是卻增加了用戶制定規(guī)則的復(fù)雜度，因此提出了一種混合優(yōu)先級(jí)調(diào)度機(jī)制，使系統(tǒng)可以實(shí)時(shí)地自適應(yīng)調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí).實(shí)驗(yàn)結(jié)果顯示:EasiRCC的規(guī)則匹配效率不會(huì)隨著規(guī)則數(shù)的增多而變化，其時(shí)間復(fù)雜度為常數(shù)，而傳統(tǒng)的匹配方法為O(N)，并且在不影響用戶正常家居生活的前提下，能夠有效地消除規(guī)則沖突.

物聯(lián)網(wǎng)；智能家居；規(guī)則匹配；散列函數(shù)；沖突消除；混合優(yōu)先級(jí)

自1999年由麻省理工學(xué)院提出“物聯(lián)網(wǎng)(Internet of things, IOT)”的概念以來[1]，物聯(lián)網(wǎng)作為一個(gè)新興的信息技術(shù)領(lǐng)域，早已受到世界各國(guó)政府、學(xué)者以及企業(yè)的極大關(guān)注.智能家居(smart home, SH)是通過物聯(lián)網(wǎng)技術(shù)，將空調(diào)控制、安防監(jiān)控、照明系統(tǒng)、環(huán)境監(jiān)測(cè)等各種設(shè)備連接在一起，提供用戶全方位的家居信息交互功能[2].最初的智能家居，只是簡(jiǎn)單實(shí)現(xiàn)家居環(huán)境的溫度、濕度等生活環(huán)境相關(guān)參數(shù)的采集，然后根據(jù)采集到的數(shù)據(jù)再對(duì)家用電器進(jìn)行簡(jiǎn)單的控制功能.近年來，智能家居向著控制功能的網(wǎng)絡(luò)集中化管理方向發(fā)展，可根據(jù)不同的用戶需求實(shí)現(xiàn)家居環(huán)境的個(gè)性化和定制化服務(wù)功能，而這些服務(wù)的功能都是通過用戶設(shè)定的規(guī)則來實(shí)現(xiàn)，比如可以制定一條服務(wù)規(guī)則為“當(dāng)濕度低于60%時(shí)，打開加濕器”，當(dāng)室內(nèi)的濕度低于60%時(shí)，系統(tǒng)就會(huì)打開加濕器來增加室內(nèi)的濕度.

伴隨著智能家居行業(yè)的飛速發(fā)展，人們根據(jù)需求制定的服務(wù)規(guī)則越來越多.由于規(guī)則數(shù)量的增多，對(duì)于規(guī)則之間的相互關(guān)系用戶很難考慮周全，很容易發(fā)生規(guī)則之間的執(zhí)行沖突，影響整個(gè)家居系統(tǒng)的穩(wěn)定性，甚至威脅到人們的生命健康問題.比如規(guī)則1“當(dāng)檢測(cè)室內(nèi)溫度高于30℃時(shí)，打開空調(diào)降溫”，規(guī)則2“當(dāng)所有電器設(shè)備的功耗達(dá)到1.5 kW時(shí)，關(guān)閉空調(diào)”，當(dāng)室內(nèi)溫度高于30℃并且所有電氣設(shè)備功耗達(dá)到1.5 kW以上時(shí)，規(guī)則1和規(guī)則2同時(shí)執(zhí)行對(duì)空調(diào)的開和關(guān)動(dòng)作，就會(huì)引起沖突，影響系統(tǒng)穩(wěn)定性以及用戶自身的生活舒服感，所以，智能家居領(lǐng)域要得到更好的發(fā)展，解決規(guī)則沖突問題成了一個(gè)發(fā)展瓶頸.

現(xiàn)有的規(guī)則匹配和沖突消除機(jī)制很少是以智能家居為應(yīng)用背景的，而目前針對(duì)智能家居的研究工作都存在著共同的問題：

1) 規(guī)則匹配過程中重復(fù)匹配現(xiàn)象頻發(fā)，規(guī)則的匹配效率低，僅適用于規(guī)則較少的情況，規(guī)則數(shù)目增多會(huì)導(dǎo)致系統(tǒng)計(jì)算資源的浪費(fèi)；

2) 消除沖突的方法，多數(shù)都需要通過用戶給每個(gè)規(guī)則預(yù)設(shè)一個(gè)固定優(yōu)先級(jí)來避免沖突，系統(tǒng)不能自適應(yīng)地消除沖突，增加了用戶制定規(guī)則的復(fù)雜度.

針對(duì)智能家居中存在的規(guī)則匹配和沖突問題，本文提出了一種新型的快速規(guī)則匹配和消除的方法EasiRCC.該方法首先根據(jù)智能家居服務(wù)規(guī)則的特點(diǎn)，制定了規(guī)則描述方法，基于散列函數(shù)尋址方式直接將規(guī)則中的觸發(fā)條件匹配到相應(yīng)的規(guī)則，提高了規(guī)則的匹配效率.然后，結(jié)合不同類型的規(guī)則所具有的靜態(tài)優(yōu)先級(jí)，再根據(jù)規(guī)則的觸發(fā)方式動(dòng)態(tài)調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí)來消除規(guī)則間的沖突.

本文的貢獻(xiàn)主要集中在3個(gè)方面：

1) 提出了一種基于散列函數(shù)尋址方式的快速規(guī)則匹配算法EasiRMA，消除了規(guī)則的重復(fù)匹配現(xiàn)象，提高了規(guī)則的匹配效率;

2) 根據(jù)規(guī)則的類型和觸發(fā)方式，結(jié)合靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)，提出了一種混合優(yōu)先級(jí)調(diào)度機(jī)制，消除了控制規(guī)則之間的沖突;

3) 通過實(shí)驗(yàn)驗(yàn)證了EasiRCC的有效性.

1 相關(guān)工作

近年來，針對(duì)智能家居規(guī)則沖突問題的研究，大多都集中在規(guī)則的沖突檢測(cè)上，忽略了規(guī)則的匹配問題.沖突檢測(cè)是建立在規(guī)則成功匹配的基礎(chǔ)上，所以，首先要解決的是規(guī)則的匹配問題.目前，多數(shù)的研究工作都是采用順序匹配方法來實(shí)現(xiàn)規(guī)則的匹配，致使規(guī)則的重復(fù)匹配現(xiàn)象頻發(fā)，造成系統(tǒng)資源的浪費(fèi).

目前，常用的匹配算法有Rete,Leaps,Liner,Treat[3]，其中很多規(guī)則推理引擎都是基于Rete算法來進(jìn)行推理的，比如Drools,JBoss Rules[4]等.Rete算法的核心思想是：利用基于規(guī)則的系統(tǒng)具有時(shí)間冗余性和結(jié)構(gòu)相似性的特征，通過節(jié)點(diǎn)狀態(tài)的共享和保存這2種方式來提高匹配的效率[4].這種方法的缺點(diǎn)是：1)存在狀態(tài)重復(fù)保存的問題，占用較多空間并影響匹配的效率；2)處理大規(guī)模和實(shí)時(shí)變化的數(shù)據(jù)時(shí)效率較低，不適合應(yīng)用于實(shí)時(shí)性要求較高的智能家居場(chǎng)景中.文獻(xiàn)[5-8]中的研究工作，采用的是順序匹配的方法，在實(shí)現(xiàn)規(guī)則的匹配過程中，都是通過將觸發(fā)條件與規(guī)則庫(kù)中的每條規(guī)則進(jìn)行逐條匹配的方法來實(shí)現(xiàn)的，這種順序匹配方法進(jìn)行了多次的重復(fù)匹配，造成系統(tǒng)計(jì)算資源的浪費(fèi).假定規(guī)則庫(kù)中有N條規(guī)則，在最壞的情況下可能會(huì)造成N-1次無效匹配，匹配的時(shí)間復(fù)雜度為O(N).

規(guī)則匹配完成后，針對(duì)規(guī)則間存在的沖突問題，Munir等人[5]提出的一種針對(duì)智能家居的集成傳感資源和執(zhí)行資源的一種架構(gòu)——DepSys，為解決多應(yīng)用并發(fā)運(yùn)行引起的沖突問題，提供了一個(gè)通過處理一些相關(guān)依賴關(guān)系的規(guī)范、檢測(cè)、解決沖突的策略方案.Dixon等人[6]搭建了一個(gè)HomeOS虛擬PC操作平臺(tái)，家里的所有設(shè)備都作為外設(shè)(peripherals)連接到這個(gè)虛擬PC上，用戶可通過一個(gè)中央操作系統(tǒng)(centralized operating system)對(duì)這些設(shè)備上的數(shù)據(jù)信息進(jìn)行操作，為用戶提供一個(gè)應(yīng)用管理接口.但是，HomeOS并沒有考慮控制規(guī)則間的沖突檢測(cè)，只是通過賦予所有控制規(guī)則一個(gè)固定優(yōu)先級(jí)來消除沖突.Sun等人[7]提出了一種基于UTEA(user triggers environment actuators)的形式化規(guī)則模型的沖突檢測(cè)機(jī)制，首先將規(guī)則的相互關(guān)系定義為11種，并基于這些規(guī)則間的相互關(guān)系定義了5種規(guī)則沖突類型；然后將復(fù)雜規(guī)則分解成多個(gè)基本規(guī)則，并通過形式化規(guī)則模型來提取和分析這些基本規(guī)則間的相互關(guān)系；最后匹配規(guī)則間的相互關(guān)系，再通過規(guī)則沖突檢測(cè)算法判斷規(guī)則間屬于哪種沖突類型.上述文獻(xiàn)的工作，在規(guī)則匹配完成后，被激活的規(guī)則如果存在沖突，都是通過為每條規(guī)則預(yù)設(shè)一個(gè)固定優(yōu)先級(jí)來消除沖突，這就要求用戶在制定規(guī)則時(shí)需要為每條規(guī)則設(shè)定執(zhí)行順序，這無疑增加了規(guī)則制定過程的復(fù)雜度，給用戶帶來很大的不便.針對(duì)目前相關(guān)研究工作的這些不足，表明需要一種以智能家居為應(yīng)用背景的快速規(guī)則匹配方法和沖突消除機(jī)制.

2 EasiRCC概述

EasiRCC的結(jié)構(gòu)如圖1所示，主要包括規(guī)則匹配與沖突檢測(cè)模塊(rule-matching and conflict detection module)、沖突消除模塊(conflict resolution module)、規(guī)則處理網(wǎng)關(guān)(gateway)傳感器節(jié)點(diǎn)(sensor)和執(zhí)行設(shè)備(actuator).規(guī)則匹配與沖突檢測(cè)模塊負(fù)責(zé)匹配規(guī)則，并將激活的規(guī)則送入沖突檢測(cè)模塊，檢測(cè)到存在沖突的規(guī)則就列入沖突集中，等待沖突消除模塊進(jìn)行處理；沖突消除模塊用于消除沖突集中的規(guī)則沖突問題，當(dāng)接收到?jīng)_突集中的規(guī)則后，首先對(duì)規(guī)則進(jìn)行分類排序，然后通過混合優(yōu)先級(jí)調(diào)度模塊對(duì)規(guī)則進(jìn)行自適應(yīng)動(dòng)態(tài)調(diào)整執(zhí)行順序，再依次建立規(guī)則就緒隊(duì)列，并由網(wǎng)關(guān)按照隊(duì)列順序?qū)σ?guī)則進(jìn)行解析執(zhí)行；規(guī)則處理網(wǎng)關(guān)，是整個(gè)系統(tǒng)的信息服務(wù)中心，不僅用于將傳感器節(jié)點(diǎn)、執(zhí)行設(shè)備和匯聚節(jié)點(diǎn)組建的網(wǎng)絡(luò)接入到Internet，還負(fù)責(zé)實(shí)現(xiàn)規(guī)則匹配、沖突檢測(cè)、沖突消除以及規(guī)則的解析執(zhí)行[9].傳感器節(jié)點(diǎn)用于感知室內(nèi)的溫度、濕度、光照等數(shù)據(jù)信息，并通過無線網(wǎng)絡(luò)(ZigBee,Bluetooth,WiFi等無線近距離通信技術(shù)[10])傳輸至匯聚節(jié)點(diǎn)和網(wǎng)關(guān)進(jìn)行處理.執(zhí)行設(shè)備是直接作用于室內(nèi)物理環(huán)境的任務(wù)執(zhí)行設(shè)備，如空調(diào)、窗簾、燈、加濕器等家用電器或設(shè)備[11-12].

Fig. 1 Architecture diagram of EasiRCC圖1 EasiRCC系統(tǒng)結(jié)構(gòu)圖

EasiRCC的主要功能部分是規(guī)則匹配與沖突檢測(cè)模塊和沖突消除模塊.為了能夠在智能家居的網(wǎng)關(guān)設(shè)備上實(shí)現(xiàn)規(guī)則的快速匹配，我們?cè)谠撃K中實(shí)現(xiàn)了一種快速規(guī)則匹配算法EasiRMA，通過在規(guī)則觸發(fā)條件與規(guī)則集之間建立一一映射的對(duì)應(yīng)關(guān)系，可根據(jù)輸入的觸發(fā)條件信息數(shù)據(jù)直接定位尋址到相應(yīng)的規(guī)則，提高了規(guī)則的匹配效率.根據(jù)規(guī)則的匹配結(jié)果，就能夠判斷規(guī)則間是否存在沖突，本文目前僅是檢測(cè)執(zhí)行矛盾沖突.在沖突的消除機(jī)制上，結(jié)合靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)，通過一種混合優(yōu)先級(jí)調(diào)度機(jī)制自適應(yīng)調(diào)整規(guī)則執(zhí)行順序來消除沖突.

3 規(guī)則匹配與沖突檢測(cè)

3.1 規(guī)則的描述與分類

在智能家居中，提供的服務(wù)是由事先制定的規(guī)則來保證的，用戶可以通過增加和修改規(guī)則來實(shí)現(xiàn)所需要的服務(wù)[8].例如用戶制定了規(guī)則“室內(nèi)溫度高于28℃，打開空調(diào)降溫”，即室內(nèi)溫度高于28℃時(shí)，系統(tǒng)打開相應(yīng)的空調(diào)進(jìn)行降溫，使得室內(nèi)溫度降到28℃.一般家庭所制定的規(guī)則都是if/then形式，if后面是觸發(fā)動(dòng)作的條件，then后面是達(dá)到觸發(fā)條件后要執(zhí)行的動(dòng)作.我們所設(shè)定的規(guī)則表示形式中，if后面僅有一個(gè)條件部分，then后面也僅有一個(gè)執(zhí)行動(dòng)作.

規(guī)則的實(shí)現(xiàn)就是從對(duì)應(yīng)的傳感器中獲取特定的數(shù)據(jù)信息，并利用這些數(shù)據(jù)信息對(duì)執(zhí)行設(shè)備進(jìn)行預(yù)定的控制.為了更好地描述和管理規(guī)則，根據(jù)規(guī)則的實(shí)現(xiàn)過程，我們可以從規(guī)則屬性、運(yùn)行狀態(tài)、觸發(fā)條件以及執(zhí)行部分來定義規(guī)則.

定義1. 一條規(guī)則可表示為Rule={Rule_Au,Rule_Sta,Trigger_Con,Actuator}，其中Rule_Au,Rule_Sta,Trigger_Con,Actuator分別是規(guī)則屬性、規(guī)則狀態(tài)、觸發(fā)條件和執(zhí)行部分.

如表1中所示，規(guī)則屬性Rule_Au={Rule_ID,Rule_Typ,Rule_Pro}，其中，Rule_Pro設(shè)定了規(guī)則的優(yōu)先級(jí)，這個(gè)優(yōu)先級(jí)類似于超級(jí)用戶的權(quán)限；規(guī)則狀態(tài)Rule_Sta=0,1，表示規(guī)則是否被激活；觸發(fā)條件Trigger_Con={Trigger_Typ,Trigger_ID,Trigger_Value,Trigger_Value_Au}，假定溫度傳感器的ID=20，那么“溫度大于30℃”可表示為{1,20,30,1}；執(zhí)行部分Actuator={Actuator_ID,Actuator_Value}，假定空調(diào)的ID=10，那么“打開空調(diào)”可表示為{10,1}.例如一個(gè)規(guī)則為“當(dāng)室內(nèi)溫度大于30℃時(shí)，打開空調(diào)降溫”，我們?cè)O(shè)定規(guī)則ID=100，執(zhí)行優(yōu)先級(jí)為12，那么通過規(guī)則的描述定義，該規(guī)則可表示為Rule={100,1,12,0,1,20,30,1,10,1}.

Table 1 Parameter Description of Rule表1 規(guī)則表示參數(shù)描述

為了更全面、更方便地表達(dá)和管理各種不同的規(guī)則，我們把規(guī)則分為5種類型：健康監(jiān)護(hù)類(health supervision, HS)、安全控制類(security control, SC)、環(huán)境監(jiān)控類(environmental monitor, EM)、娛樂控制類(media control, MC)、能量管理類(power management, EM)，對(duì)應(yīng)的Rule_Typ值為000,001,010,011,100.健康監(jiān)護(hù)類規(guī)則，與用戶生命健康相關(guān)的規(guī)則都屬于這類規(guī)則；安全控制類規(guī)則，主要是涉及到生活環(huán)境安全相關(guān)的規(guī)則；環(huán)境監(jiān)控類規(guī)則，主要是負(fù)責(zé)監(jiān)控與溫度、濕度、光照等環(huán)境因素相關(guān)的規(guī)則；娛樂控制類規(guī)則，這類規(guī)則都是與娛樂相關(guān)的內(nèi)容；能量管理類規(guī)則，負(fù)責(zé)調(diào)節(jié)管理整個(gè)家居系統(tǒng)的能量消耗.

3.2 EasiRMA規(guī)則匹配算法

目前，由于智能家居中用戶設(shè)定的規(guī)則數(shù)目較少，如文獻(xiàn)[5-8]中都是采用順序規(guī)則匹配方法.順序規(guī)則匹配的原理是：讓觸發(fā)條件與規(guī)則隊(duì)列中的規(guī)則從最后一個(gè)往前逐個(gè)匹配，直到找到與觸發(fā)條件信息相同的規(guī)則為止.這種匹配方法的特點(diǎn)是:1)算法簡(jiǎn)單，易于實(shí)現(xiàn)；2)對(duì)規(guī)則存儲(chǔ)結(jié)構(gòu)無要求.

定義2. 給定一個(gè)規(guī)則集R={r1,r2,…,rn}，在得到一個(gè)觸發(fā)條件信息c后，c與規(guī)則集R中的n個(gè)規(guī)則的條件部分進(jìn)行匹配的期望次數(shù)為平均匹配長(zhǎng)度AML(average matching length).

由定義2可知，對(duì)n個(gè)規(guī)則進(jìn)行匹配時(shí)，平均匹配長(zhǎng)度為

(1)

(2)

在最壞的情況下，順序匹配需要匹配n次，即時(shí)間復(fù)雜度為O(n).

由上述可知，順序匹配最大的缺點(diǎn)是平均查找時(shí)間較長(zhǎng)、時(shí)間開銷大，只適用于規(guī)則數(shù)目很少的情況.但是，隨著智能家居的發(fā)展，用戶制定的規(guī)則數(shù)量很大時(shí)，匹配過程帶來的時(shí)間開銷將會(huì)影響系統(tǒng)的實(shí)時(shí)性.

為了在消除順序規(guī)則匹配過程中帶來的重復(fù)匹配現(xiàn)象，我們提出了EasiRMA快速規(guī)則匹配算法.其主要思想是利用散列函數(shù)在觸發(fā)條件key與規(guī)則集之間建立一一映射的對(duì)應(yīng)關(guān)系，根據(jù)得到的key通過散列函數(shù)計(jì)算Hash值，由Hash值可直接定位規(guī)則集中與之相對(duì)應(yīng)的規(guī)則，無需匹配規(guī)則集中的所有規(guī)則，提高了規(guī)則的匹配效率[12-13].

EasiRMA的匹配過程如圖2所示:

Fig. 2 Route chart of EasiRMA rule-matching圖2 EasiRMA規(guī)則匹配工作流程圖

key為時(shí)間或傳感器節(jié)點(diǎn)的數(shù)據(jù)關(guān)鍵字,經(jīng)過C分類后，若為時(shí)間數(shù)據(jù)，key=Trigger_Value，若為事件類型數(shù)據(jù)，即溫度、濕度等傳感器的數(shù)據(jù)，key包括Trigger_ID,Trigger_Value,Trigger_Value_Au.

(3)

key通過C分為time和event后，分別經(jīng)過散列函數(shù)RT(x)和RE(x)映射到Hash Rule Table1和Hash Rule Table2中，為減少規(guī)則匹配過程中發(fā)生沖突，Hash Rule Table1和Hash Rule Table2都采用線性直接尋址方法匹配規(guī)則，RT(x)和RE(x)散列函數(shù)：

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個(gè)元素空間，完全可以滿足1 d的時(shí)間設(shè)定需求.但是，也有可能在同一時(shí)間觸發(fā)多個(gè)規(guī)則，比如“8:00am拉開窗簾并打開窗戶”，針對(duì)這種多規(guī)則的匹配情況，我們采用地址鏈表(address linked list)法來實(shí)現(xiàn)同一時(shí)間下多個(gè)規(guī)則的匹配問題，即將同一時(shí)間下觸發(fā)的規(guī)則以表的形式存儲(chǔ)在其中.在Hash Rule Table2中，匹配方式與Hash Rule Table2相同，區(qū)別在于散列函數(shù)的選取上，遇到多規(guī)則匹配沖突時(shí)也是采用地址鏈表法.

EasiRMA偽代碼描述如算法1所示：

算法1. EasiRMA規(guī)則匹配算法.

輸入：Ri,key；

輸出：R.

① 初始化規(guī)則隊(duì)列RT[m]和RE[n]；

② For (每一個(gè)規(guī)則)

③ 根據(jù)規(guī)則Ri的類型計(jì)算Hash值RT(keyi)和RE(keyi),并分別存入RT[m]和RE[n]規(guī)則隊(duì)列中；

④ If 存在2個(gè)以上的RT(keyi)或RE(keyi)值相等采用地址鏈表法存儲(chǔ)這些規(guī)則；

⑤ End If

⑥ End For

⑦ 從傳感器數(shù)據(jù)和時(shí)間中得到key值；

⑧ IfC(key)==time

⑨ID=RT(keyi)；

⑩R=RT[ID],激活并輸出規(guī)則R；

3.3 沖突檢測(cè)

由3.2節(jié)中所述，由EasiRMA規(guī)則匹配算法得到規(guī)則激活集，其中的規(guī)則都是等待執(zhí)行的，但是并沒有檢測(cè)這些規(guī)則間是否存在沖突.目前，本文僅考慮規(guī)則的矛盾沖突.規(guī)則沖突檢測(cè)是建立在規(guī)則匹配的結(jié)果上進(jìn)行的，得到規(guī)則激活集后，通過檢測(cè)規(guī)則中Actuator_ID和Actuator_Value，對(duì)用執(zhí)行設(shè)備的標(biāo)識(shí)號(hào)和執(zhí)行設(shè)備的屬性值，檢測(cè)到激活集中具有相同Actuator_ID并且Actuator_Value相反的規(guī)則，則判斷為存在沖突，然后把這些規(guī)則存入到?jīng)_突集中，并交由沖突消除模塊做進(jìn)一步處理.

4 沖突消除方法設(shè)計(jì)

4.1 規(guī)則分類優(yōu)先級(jí)設(shè)置

由3.1節(jié)中可知，將規(guī)則分為5類：健康監(jiān)護(hù)類HS、安全控制類SC、環(huán)境監(jiān)測(cè)類EM、娛樂控制類MC、能量管理類PM，文獻(xiàn)[5-8]中的工作都是需要用戶為每個(gè)規(guī)則都設(shè)定一個(gè)固定優(yōu)先級(jí)，每個(gè)規(guī)則都按固定順序執(zhí)行，以避免沖突.本文中，我們通過選擇200名志愿者，要求每一位志愿者從5類規(guī)則中選擇自己比較感興趣的，或者認(rèn)為對(duì)家居生活比較重要的3類規(guī)則，并對(duì)最后的數(shù)據(jù)進(jìn)行了匯總.如圖3所示，按照興趣度以及重要性的排序?yàn)椋航】当O(jiān)護(hù)類>安全控制類>環(huán)境監(jiān)控類>娛樂控制類>能量管理類.通過這個(gè)排序，我們從高到低依次設(shè)定每一類型的優(yōu)先級(jí).

Fig. 3 Survey data of smart home’s applications圖3 智能家居應(yīng)用類型調(diào)查匯總

4.2 混合優(yōu)先級(jí)調(diào)度算法

由4.1節(jié)可知，5類規(guī)則都賦予每一類規(guī)則一個(gè)固定的優(yōu)先級(jí)，當(dāng)2個(gè)沖突的規(guī)則都屬于同一類規(guī)則時(shí)，它們的優(yōu)先級(jí)相同，無法用固定優(yōu)先級(jí)來避免沖突.針對(duì)同一類型規(guī)則間的沖突問題，文獻(xiàn)[5-7]采用事先設(shè)定每一類型內(nèi)的所有規(guī)則的執(zhí)行順序來避免沖突.我們提出了一種混合優(yōu)先級(jí)調(diào)度算法，針對(duì)同一類型內(nèi)的規(guī)則采用相應(yīng)的優(yōu)先級(jí)調(diào)度方法.

規(guī)則的條件觸發(fā)方式主要包括時(shí)間和事件觸發(fā)方式，如規(guī)則“在6:00pm—8:00pm時(shí)，打開室內(nèi)所有的照明燈”屬于時(shí)間觸發(fā)方式的規(guī)則，規(guī)則“當(dāng)室內(nèi)溫度高于28℃時(shí)，打開空調(diào)降溫”屬于事件觸發(fā)方式的規(guī)則.時(shí)間觸發(fā)方式的規(guī)則，都有固定的觸發(fā)時(shí)間以及執(zhí)行模式，而事件觸發(fā)方式的規(guī)則沒有固定的觸發(fā)時(shí)間，是由感知節(jié)點(diǎn)的數(shù)據(jù)信息來觸發(fā)的，比如溫度、濕度、光照等傳感器數(shù)據(jù)，實(shí)時(shí)性比時(shí)間觸發(fā)方式高，所以我們?cè)O(shè)定事件觸發(fā)方式的規(guī)則優(yōu)先級(jí)大于時(shí)間觸發(fā)方式的規(guī)則.對(duì)于這2種規(guī)則，應(yīng)該分別采用相應(yīng)的規(guī)則執(zhí)行優(yōu)先級(jí)調(diào)度算法，文獻(xiàn)[8]對(duì)所有的規(guī)則都采用預(yù)先設(shè)定固定優(yōu)先級(jí)來避免沖突，并沒有加以區(qū)別考慮.本文提出的混合優(yōu)先級(jí)調(diào)度算法，根據(jù)不同的觸發(fā)方式動(dòng)態(tài)調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí)，不需要為每條規(guī)則都設(shè)定優(yōu)先級(jí)，簡(jiǎn)化了規(guī)則的定義過程.

我們?cè)谝詴r(shí)間為觸發(fā)方式的規(guī)則中采用高響應(yīng)比優(yōu)先調(diào)度算法[14](highest response ratio next，HRRN).HRRN將響應(yīng)比Rp作為時(shí)間觸發(fā)方式規(guī)則的執(zhí)行優(yōu)先級(jí)，Rp的計(jì)算過程：

(6)

其中，n為規(guī)則沖突集中的規(guī)則數(shù)，t為每個(gè)規(guī)則之間切換的時(shí)間間隔，TSi(i∈n)為每個(gè)規(guī)則的執(zhí)行服務(wù)時(shí)間，TS0為當(dāng)前規(guī)則的執(zhí)行服務(wù)時(shí)間.

我們?cè)谝允录橛|發(fā)方式的規(guī)則中采用先來先服務(wù)算法[15](first come first service， FCFS).不同類型的兩條或更多規(guī)則進(jìn)入規(guī)則激活集模塊中，經(jīng)過規(guī)則沖突檢測(cè)模塊時(shí)，若存在沖突，并且屬于事件觸發(fā)方式的規(guī)則，采用FCFS算法來避免沖突.如圖4所示，激活的規(guī)則按照被激活的先后次序進(jìn)入規(guī)則激活隊(duì)列，排在隊(duì)首的規(guī)則最先執(zhí)行，隊(duì)尾的規(guī)則需要等待排在前面的規(guī)則執(zhí)行完畢才能獲得執(zhí)行權(quán)(token).

Fig. 4 Scheduling flow of FCFS圖4 FCFS規(guī)則調(diào)度流程

混合優(yōu)先級(jí)算法是建立在固定優(yōu)先級(jí)的基礎(chǔ)上，根據(jù)規(guī)則的觸發(fā)方式采用相應(yīng)的規(guī)則調(diào)度算法來消除沖突，保障家居設(shè)備的安全運(yùn)行.混合優(yōu)先級(jí)調(diào)度算法實(shí)現(xiàn)過程如圖5所示.當(dāng)激活的規(guī)則中存在沖突時(shí)，首先判斷規(guī)則是否屬于同一類型，如果不是同一類型，直接按照4.1節(jié)中定義的規(guī)則類型優(yōu)先級(jí)依次執(zhí)行規(guī)則，如果是同一類型，需要判斷規(guī)則的觸發(fā)方式，屬于時(shí)間觸發(fā)方式的規(guī)則，采用FCFS規(guī)則調(diào)度算法來消除沖突，屬于事件觸發(fā)方式的規(guī)則，采用HRRN規(guī)則調(diào)度算法來消除沖突.判斷規(guī)則的觸發(fā)方式時(shí)，有可能沖突的規(guī)則不是屬于同一種觸發(fā)方式的規(guī)則，那么還需要按照規(guī)則觸發(fā)方式對(duì)規(guī)則進(jìn)行分組，分組后事件觸發(fā)方式和時(shí)間觸發(fā)方式的規(guī)則分別通過FCFS,HRRN算法進(jìn)行分組排序，最后再根據(jù)事件觸發(fā)規(guī)則的優(yōu)先級(jí)大于時(shí)間觸發(fā)規(guī)則的優(yōu)先級(jí),R(event)>R(time),進(jìn)行統(tǒng)一排序，并依次執(zhí)行規(guī)則.

Fig. 5 Workflow of mixed-priority algorithm圖5 混合優(yōu)先級(jí)調(diào)度算法工作流程

5 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證EasiRCC的有效性和可行性，我們基于EZ6410網(wǎng)關(guān)設(shè)備[16]和EZ240感知節(jié)點(diǎn)[17-18]部署了實(shí)驗(yàn)驗(yàn)證平臺(tái)，如圖6所示.EZ6410主要由CPU、存儲(chǔ)模塊以及各種通信模塊組成，包括ARM(S3C6410)、FLASH(1 GB)、RS232接口、以太網(wǎng)接口(DM900A)、嵌入式WiFi模塊以及802.15.4模塊(CC2420).EZ240感知節(jié)點(diǎn)采用超低功耗的MSP430F1611作為MCU，具有48 KB的ROM和10 KB的RAM，集成高精度的SHT11光照傳感器和TSL2561溫濕度傳感器，采用符合802.15.4協(xié)議的CC2420射頻芯片作為數(shù)據(jù)通信模塊.

Fig. 6 Picture of real devices of experiment圖6 實(shí)驗(yàn)平臺(tái)實(shí)物圖

Fig. 7 Average computing time of EasiRMA圖7 EasiRMA的平均匹配時(shí)間開銷

5.1 EasiRMA規(guī)則匹配效率

文獻(xiàn)[7]中采用的順序規(guī)則匹配算法，我們已經(jīng)在3.2節(jié)中進(jìn)行了分析，順序規(guī)則匹配的時(shí)間復(fù)雜度為O(N)，N為智能家居系統(tǒng)中的規(guī)則數(shù)目.而我們提出的EasiRMA規(guī)則匹配算法，是在規(guī)則的觸發(fā)條件與規(guī)則之間建立一一映射的關(guān)系，根據(jù)輸入的觸發(fā)條件數(shù)據(jù)信息，直接尋址到規(guī)則的存儲(chǔ)地址，提高了規(guī)則的匹配效率.為了驗(yàn)證EasiRMA的有效性，我們?cè)贓Z6410中建立了一個(gè)規(guī)則庫(kù)，規(guī)則數(shù)目從50條增加到1 000條，順序規(guī)則匹配與EasiRMA規(guī)則匹配算法的平均匹配時(shí)間開銷如圖7所示.從圖7中我們可以看出，順序規(guī)則匹配算法隨著規(guī)則數(shù)目的增加，匹配過程所耗費(fèi)的時(shí)間也相應(yīng)地增加，算法所耗費(fèi)的時(shí)間總體呈線性增加，時(shí)間復(fù)雜度為O(N).EasiRMA算法隨著規(guī)則數(shù)目地增加，耗費(fèi)的匹配時(shí)間開銷基本沒有變化，算法的時(shí)間復(fù)雜度近似為一個(gè)常數(shù).由圖7所示，當(dāng)規(guī)則數(shù)目大于145時(shí)，EasiRMA的匹配效率高于順序規(guī)則匹配算法.

5.2 混合優(yōu)先級(jí)調(diào)度性能分析

規(guī)則間存在沖突時(shí)，文獻(xiàn)[5-8]中的工作都是要求用戶在制定規(guī)則時(shí)預(yù)先為每個(gè)規(guī)則設(shè)定一個(gè)固定優(yōu)先級(jí)來避免沖突.本文提出的混合優(yōu)先級(jí)調(diào)度算法，結(jié)合靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)，能夠自適應(yīng)地調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí).規(guī)定優(yōu)先級(jí)方法因?yàn)橐呀?jīng)為每個(gè)規(guī)則預(yù)設(shè)了一個(gè)固定優(yōu)先級(jí)，無需再經(jīng)過多余的計(jì)算，可直接通過固定優(yōu)先級(jí)消除沖突.但是，由我們提出的混合優(yōu)先級(jí)調(diào)度算法需要根據(jù)計(jì)算結(jié)果來自適應(yīng)地調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí)，與固定優(yōu)先級(jí)相比，混合優(yōu)先級(jí)調(diào)度算法計(jì)算開銷高于固定優(yōu)先級(jí).為了分析算法的計(jì)算時(shí)間開銷，結(jié)合文獻(xiàn)[5]關(guān)于規(guī)則和沖突數(shù)量的選擇，我們?cè)O(shè)定了2～40條存在沖突的規(guī)則，通過混合優(yōu)先級(jí)調(diào)度算法消除了沖突，消除沖突需要額外耗費(fèi)的計(jì)算時(shí)間如圖8所示：

Fig. 8 Time of conflict resolution of mixed-priority algorithm圖8 混合優(yōu)先級(jí)調(diào)度算法的沖突消除時(shí)間

從圖8可以看出，在消除沖突上的時(shí)間開銷上，隨著沖突規(guī)則數(shù)的增加，混合優(yōu)先級(jí)調(diào)度和固定優(yōu)先級(jí)調(diào)度算法都是呈增長(zhǎng)趨勢(shì)，后者的增長(zhǎng)速度高于前者.因?yàn)榛旌蟽?yōu)先級(jí)方法綜合考慮了沖突規(guī)則的執(zhí)行時(shí)間、等待時(shí)間以及激活的先后次序，而固定優(yōu)先級(jí)方法僅考慮了每個(gè)規(guī)則的執(zhí)行優(yōu)先級(jí)，所以，當(dāng)沖突的規(guī)則數(shù)越多，混合優(yōu)先級(jí)調(diào)度算法的優(yōu)勢(shì)更為明顯.由圖8可知，當(dāng)沖突的規(guī)則數(shù)達(dá)到30時(shí)，固定優(yōu)先級(jí)所耗費(fèi)時(shí)間為38 ms，混合優(yōu)先級(jí)所耗費(fèi)的時(shí)間僅為14 ms.

為了分析EasiRCC消除規(guī)則沖突的有效性，我們分別制定了不同數(shù)量的規(guī)則集，每個(gè)規(guī)則集都存在不同的沖突規(guī)則，表2中列出了規(guī)則集、存在的沖突規(guī)則數(shù)、沖突消除量以及沖突消除率.

Table 2 Results Summary of Conflict Resolution for EasiRCC表2 EasiRCC的沖突消除結(jié)果統(tǒng)計(jì)

從表2中可以看出，EasiRCC的沖突消除率在94.7%以上，規(guī)則集2,4,5的沖突消除率低于規(guī)則集1,3中的沖突消除率，主要是因?yàn)橐?guī)則集2,4,5通過HRRN調(diào)整執(zhí)行優(yōu)先級(jí)后，仍然存在優(yōu)先級(jí)相同的規(guī)則，我們對(duì)這些調(diào)整優(yōu)先級(jí)后仍然具有相同執(zhí)行優(yōu)先級(jí)的規(guī)則進(jìn)一步采用FCFS算法可消除沖突.目前，在智能家居領(lǐng)域中的規(guī)則沖突檢測(cè)和消除的方法主要有HomeOS[6],DepSys[5],UTEA[7],SPIDER[19],IRIS[20]等，EasiRCC與這些方法在沖突消除方面的性能對(duì)比如表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中，“√”表示該方法具備該項(xiàng)性能；“×”表示該方法不具備該項(xiàng)性能.HomeOS,DepSys,UTEA都能夠處理2個(gè)以上的規(guī)則沖突；而SPIDER,IRIS僅能處理2個(gè)規(guī)則沖突，不能處理3個(gè)以上的規(guī)則沖突.上述方法都是采用設(shè)定規(guī)則的執(zhí)行優(yōu)先級(jí)來消除沖突，在制定規(guī)則時(shí)需要用戶為每個(gè)規(guī)則預(yù)設(shè)一個(gè)固定的執(zhí)行優(yōu)先級(jí)，并且該優(yōu)先級(jí)無法再改變.本文提出的EasiRCC，不僅能同時(shí)處理多個(gè)規(guī)則沖突，而且無需用戶為每個(gè)規(guī)則設(shè)定執(zhí)行優(yōu)先級(jí)，降低了用戶制定規(guī)則的復(fù)雜度，使得系統(tǒng)能夠?qū)崟r(shí)地自適應(yīng)調(diào)整規(guī)規(guī)則的復(fù)雜度，使得系統(tǒng)能夠?qū)崟r(shí)地自適應(yīng)調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí)來消除規(guī)則間的沖突，保證系統(tǒng)的穩(wěn)定性和安全性.綜上所述，EasiRCC能夠有效地消除規(guī)則沖突.

6 總結(jié)與展望

本文在對(duì)智能家居的研究現(xiàn)狀以及未來的發(fā)展趨勢(shì)的基礎(chǔ)上，針對(duì)系統(tǒng)中頻發(fā)的規(guī)則重復(fù)匹配以及規(guī)則沖突的問題，提出了一種規(guī)則快速匹配與沖突消除方法EasiRCC.針對(duì)規(guī)則重復(fù)匹配的問題，EasiRCC提出了EasiRMA規(guī)則匹配算法，該算法在觸發(fā)條件與規(guī)則之間建立一一映射的方法，根據(jù)輸入的觸發(fā)數(shù)據(jù)信息可直接尋址到相應(yīng)的規(guī)則，消除了規(guī)則重復(fù)匹配的現(xiàn)象，提高了規(guī)則匹配的效率.而在消除規(guī)則沖突的問題上，之前的研究工作都是采用制定規(guī)則時(shí)預(yù)設(shè)規(guī)則的執(zhí)行優(yōu)先級(jí)來消除沖突，但是，隨著規(guī)則數(shù)目的增多，這種方法增加了規(guī)則制定的復(fù)雜度.而我們?cè)诒ＷC不影響用戶正常的家居生活的前提下，結(jié)合靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)，提出了一種混合優(yōu)先級(jí)調(diào)度機(jī)制，系統(tǒng)可以根據(jù)規(guī)則屬性實(shí)時(shí)的自適應(yīng)調(diào)整規(guī)則的執(zhí)行優(yōu)先級(jí)來消除沖突.

在消除規(guī)則沖突的問題上，本文僅針對(duì)規(guī)則的執(zhí)行矛盾沖突，即同時(shí)對(duì)家居設(shè)備進(jìn)行開或關(guān)的操作導(dǎo)致的執(zhí)行矛盾問題，并沒有考慮其他的沖突類型，比如環(huán)境互斥、規(guī)則依賴、冗余沖突等.所以，在未來的工作中，我們將設(shè)計(jì)一種新型的規(guī)則沖突檢測(cè)方法，然后結(jié)合EasiRCC綜合考慮如何更好地提高智能家居系統(tǒng)的穩(wěn)定性和安全性.

[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)(李海光. 基于規(guī)則引擎的智能家居系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京: 北京郵電大學(xué), 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)(顧小東, 高陽(yáng). Rete算法: 研究現(xiàn)狀與挑戰(zhàn)[J]. 計(jì)算機(jī)科學(xué), 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)(王栩凱. 智能家居系統(tǒng)規(guī)則沖突檢測(cè)機(jī)制的研究與實(shí)現(xiàn)[D]. 北京: 北京郵電大學(xué), 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)(崔莉, 鞠海玲, 苗勇, 等. 無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(劉強(qiáng), 崔莉, 陳海明. 物聯(lián)網(wǎng)關(guān)鍵技術(shù)與應(yīng)用[J]. 計(jì)算機(jī)科學(xué), 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函數(shù)的RFID安全認(rèn)證協(xié)議研究[J]. 計(jì)算機(jī)研究與發(fā)展, 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快速屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(趙澤, 劉強(qiáng), 李棟, 等. EasiTest: 多Radio異構(gòu)無線傳感器網(wǎng)絡(luò)測(cè)試平臺(tái)[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(趙澤, 尚鵬飛, 劉強(qiáng), 等. 無線傳感器網(wǎng)絡(luò)通信負(fù)載狀態(tài)識(shí)別方法的研究[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國(guó)家自然科學(xué)基金項(xiàng)目(61672498，61502461)；中國(guó)科學(xué)院計(jì)算技術(shù)研究所創(chuàng)新項(xiàng)目(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).