一種針對物聯(lián)網(wǎng)智能系統(tǒng)的規(guī)則沖突檢測方法

楊 波 郭浩然 馮俊輝 李 戈 金 芝

1（北京林業(yè)大學(xué)信息學(xué)院 北京 100083）

2（北方工業(yè)大學(xué)信息學(xué)院 北京 100144）

3（國家林業(yè)和草原局林業(yè)智能信息處理工程技術(shù)研究中心（北京林業(yè)大學(xué)）北京 100083）

4（北京大學(xué)計算機學(xué)院 北京 100871）

5（高可信軟件技術(shù)教育部重點實驗室（北京大學(xué)）北京 100871）

物聯(lián)網(wǎng)指的是物體與物體之間的互聯(lián)網(wǎng)絡(luò)，它通過無線傳感技術(shù)，利用傳感器獲取物體和環(huán)境的信息，實現(xiàn)物理設(shè)備之間、物理設(shè)備與網(wǎng)絡(luò)之間信息傳輸與資源共享[1].一般來說，物聯(lián)網(wǎng)系統(tǒng)架構(gòu)中通過邏輯控制器來感知物理環(huán)境的狀態(tài)并調(diào)度物理設(shè)備以提供想要的服務(wù).將設(shè)備控制邏輯從控制器中分離出來，可以方便物聯(lián)網(wǎng)系統(tǒng)的設(shè)計和支持系統(tǒng)的演化，從而減少物聯(lián)網(wǎng)系統(tǒng)的開發(fā)和維護成本，提高物聯(lián)網(wǎng)系統(tǒng)架構(gòu)的靈活性.這種將設(shè)備邏輯控制從控制器中分離出來的物聯(lián)網(wǎng)系統(tǒng)，在一定程度上可以認為是一種智能系統(tǒng).

物聯(lián)網(wǎng)系統(tǒng)架構(gòu)中的核心邏輯控制器使用規(guī)則來控制業(yè)務(wù)邏輯，規(guī)則一般由2 部分構(gòu)成:約束部分和動作部分.約束部分是物聯(lián)網(wǎng)系統(tǒng)中的實體狀態(tài)構(gòu)成的條件，這些條件隨著物聯(lián)網(wǎng)系統(tǒng)規(guī)模的擴大而變得復(fù)雜.當(dāng)約束部分包含的條件所組成的邏輯表達式成立時，觸發(fā)規(guī)則的動作部分，從而改變物聯(lián)網(wǎng)系統(tǒng)中某些實體的狀態(tài).而這些實體狀態(tài)的改變，將觸發(fā)物聯(lián)網(wǎng)系統(tǒng)中的其他規(guī)則，從而導(dǎo)致物聯(lián)網(wǎng)系統(tǒng)的狀態(tài)發(fā)生新的變化.當(dāng)物聯(lián)網(wǎng)系統(tǒng)中實體的狀態(tài)，不能使得所有規(guī)則約束部分的條件得到滿足時，系統(tǒng)將產(chǎn)生規(guī)則間的沖突，從而使得物聯(lián)網(wǎng)系統(tǒng)的運行出現(xiàn)問題.

圖1 是典型的物聯(lián)網(wǎng)系統(tǒng)架構(gòu)，主要分為外部元素、網(wǎng)絡(luò)層、控制系統(tǒng)3 部分.外部元素包括傳感器和設(shè)備.傳感器是信息流動的源頭，可以采集溫度、濕度、光強、壓力等物理量；設(shè)備包括可編程的硬件，是信息流動的目的地.網(wǎng)絡(luò)層完成信息傳輸，實現(xiàn)外部元素與控制系統(tǒng)的連接[2-3].控制系統(tǒng)完成物理設(shè)備的邏輯控制，是信息的加工處理部分.

Fig.1 Typical Internet of things system architecture圖1 典型的物聯(lián)網(wǎng)系統(tǒng)架構(gòu)

圖2 是使用規(guī)則推理作為控制系統(tǒng)核心的架構(gòu)，它包括交互處理模塊和規(guī)則推理模塊，交互處理模塊將環(huán)境和設(shè)備的狀態(tài)數(shù)據(jù)格式化后傳遞到規(guī)則推理模塊，并根據(jù)規(guī)則推理信息來控制設(shè)備狀態(tài).規(guī)則推理模塊包括知識和推理引擎.知識是由邏輯構(gòu)成的規(guī)則，當(dāng)知識部署在推理機中，推理機可以根據(jù)知識，對輸入的外部元素的狀態(tài)數(shù)據(jù)進行邏輯推理[4].

Fig.2 Rule inference control system architecture圖2 規(guī)則推理控制系統(tǒng)架構(gòu)

在物聯(lián)網(wǎng)系統(tǒng)中，規(guī)則調(diào)度流程大致是這樣的:外部狀態(tài)數(shù)據(jù)通過網(wǎng)絡(luò)層傳遞進控制系統(tǒng).交互處理模塊將狀態(tài)數(shù)據(jù)格式化后傳遞到規(guī)則推理模塊.規(guī)則推理模塊經(jīng)過推理，輸出控制信息傳遞到交互處理模塊.交互處理模塊根據(jù)控制信息生成設(shè)備控制命令，通過網(wǎng)絡(luò)層發(fā)送到相應(yīng)的控制設(shè)備.

在一些復(fù)雜的物聯(lián)網(wǎng)運行的場景中，如果2 條或多條規(guī)則出現(xiàn)沖突，帶來的后果是比較嚴重的，甚至是災(zāi)難性的.例如，智能會議室中投影儀開啟或關(guān)閉的規(guī)則出現(xiàn)混亂，導(dǎo)致會議無法正常進行.無人駕駛的物聯(lián)網(wǎng)系統(tǒng)，如果因為規(guī)則的沖突，導(dǎo)致傳遞給車輛的信息是錯誤的，導(dǎo)致無人駕駛車輛出現(xiàn)偏離正常行駛路線，甚至導(dǎo)致車毀人亡的災(zāi)難事件.

圖3 表示2 種典型的物聯(lián)網(wǎng)中的規(guī)則沖突案例.圖3（a）中，用戶編寫2 條規(guī)則R1和R2，當(dāng)環(huán)境溫度為22°C 時，2 條規(guī)則都被觸發(fā).電暖氣制熱與空調(diào)制冷，對環(huán)境溫度產(chǎn)生相反的影響，從而產(chǎn)生消極影響沖突.

Fig.3 Rule conflict cases圖3 規(guī)則沖突案例

圖3（b）中，用戶編寫3 條規(guī)則R3，R4和R5，當(dāng)環(huán)境光強為2000 lm 時，3 條規(guī)則都被觸發(fā).受到規(guī)則R3和R4的影響，窗簾處于不斷開關(guān)的狀態(tài)，從而產(chǎn)生執(zhí)行矛盾沖突.

圖3（a）和圖3（b）中所展示的規(guī)則間的沖突是由于現(xiàn)有的物聯(lián)網(wǎng)規(guī)則沖突的分類還不夠精細，使得已有的沖突檢測方法不一定能檢測到這2 種規(guī)則沖突，從而出現(xiàn)規(guī)則沖突漏檢的問題.

針對物聯(lián)網(wǎng)系統(tǒng)中存在的規(guī)則沖突的問題，一些學(xué)者對此展開研究.Shehara 等人[5]提出一種需求交互分類法，用于對軟件系統(tǒng)中的需求交互進行分類和識別.文獻[5]提出的分類法是一個4 層金字塔的形式，在第1 層定義6 個主要交互類別，在第2 層定義17 個交互子類別，在第3 層定義29 個交互類型，在第4 層定義29 個交互場景，每個交互場景都有一個相應(yīng)的交互檢測指南來描述如何檢測交互.該文獻還提出一種半形式化的沖突檢測方法IRIS（identifying requirements interactions using semiformal）來識別需求沖突，成為形式化方法的重要基礎(chǔ).Hu 等人[6]通過分析智能家居系統(tǒng)的本體模型，實現(xiàn)知識重用和上下文語義建模，提出基于Web 語義的策略沖突檢測方法SPIDER（semantic Web-based policy interaction detection with rules），來探測智能家庭服務(wù)中的規(guī)則沖突，為本體編輯工具Protégé[7]和規(guī)則引擎工具Jess[8]提供功能支持.然而IRIS 和SPIDER 這2 種方法在規(guī)則沖突分類時只考慮離散的系統(tǒng)狀態(tài).例如圖3（a）所示的案例1，用戶只考慮到設(shè)備開、關(guān)等的離散狀態(tài)，不能得知溫度這樣連續(xù)狀態(tài)的變化范圍，從而出現(xiàn)規(guī)則沖突漏檢現(xiàn)象.Sun 等人[9]在對智能家居現(xiàn)狀的分析基礎(chǔ)上，提出一種基于用戶、觸發(fā)器、環(huán)境實體和作動器（user,triggers,environment entities,and actuators,UTEA）的沖突檢測方法，他們通過用戶、觸發(fā)器、環(huán)境實體和執(zhí)行器的建模方法，探測智能家具系統(tǒng)的規(guī)則沖突，為連續(xù)的系統(tǒng)狀態(tài)提供解決方法，并引入用戶優(yōu)先級的權(quán)限控制.方法UTEA 解決在智能家居中，規(guī)則增加所帶來的規(guī)則冗余、沖突等問題.然而此方法需要依賴系統(tǒng)的初始狀態(tài)，沒有被觸發(fā)的規(guī)則不被算法檢測，導(dǎo)致檢測的準確性下降.例如規(guī)則沖突案例2 中如果當(dāng)環(huán)境光強初始為4000 lm，并且燈處于關(guān)閉狀態(tài)時，3 條規(guī)則都沒有被觸發(fā).此時UTEA 方法不能檢測出規(guī)則沖突.

這些研究在解決物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則沖突問題上取得一定的效果，但是這些研究對規(guī)則沖突類型分析還不是很全面，并且檢測的準確性有待提高.

為此，本文提出一種物聯(lián)網(wǎng)系統(tǒng)的形式化規(guī)則沖突檢測方法（formal rule conflict detection，F(xiàn)RCD）.該方法首先利用形式化的方法將物聯(lián)網(wǎng)中的規(guī)則及不同的規(guī)則沖突進行建模，同時考慮到連續(xù)的系統(tǒng)狀態(tài)量.這樣針對不同的規(guī)則沖突，對這些規(guī)則的形式化表達進行區(qū)分，并且不依賴于系統(tǒng)的初始狀態(tài)，從而使得不同的規(guī)則沖突能夠清楚地得到檢測.然后，方法FRCD 能夠?qū)斎氲奈锫?lián)網(wǎng)規(guī)則進行解析，得到規(guī)則的各種條件，基于解析的結(jié)果，對這些條件進行分解，這樣可以幫助簡化規(guī)則條件邏輯.最后，根據(jù)不同的規(guī)則沖突類型，檢測出相應(yīng)的沖突.

本文的主要貢獻包括3 方面：

1）通過調(diào)研和分析已有的物聯(lián)網(wǎng)系統(tǒng)的規(guī)則，將目前的物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則沖突細分為7類，分別是執(zhí)行覆蓋沖突、執(zhí)行矛盾沖突、消極影響沖突、獨占資源沖突、直接忽略依賴沖突、直接循環(huán)依賴沖突、間接循環(huán)依賴沖突.

2）基于對物聯(lián)網(wǎng)系統(tǒng)的規(guī)則沖突分類，對不同的規(guī)則沖突進行形式化表示，使得沖突的檢測能夠自動化進行，且針對不同的規(guī)則沖突能夠進行很好地區(qū)分，在一定程度上能提高規(guī)則沖突檢測的準確性.

3）設(shè)計并實現(xiàn)規(guī)則沖突檢測的原型系統(tǒng)，在2個物聯(lián)網(wǎng)系統(tǒng)中進行實驗驗證.實驗的結(jié)果表明，本文的方法FRCD 在物聯(lián)網(wǎng)系統(tǒng)的規(guī)則沖突檢測的F1值上，表現(xiàn)比其他3 種沖突檢測方法更優(yōu)秀.

1 相關(guān)工作

1.1 規(guī)則授權(quán)訪問與規(guī)則完整性

Kim[10]針對由RIF[11]規(guī)則推理引起的授權(quán)問題，提出應(yīng)用圖標(biāo)記算法，解決由規(guī)則推斷引起的RDF[12]元組安全簽名不一致的問題.Yu 等人[13]提出授權(quán)規(guī)則規(guī)范語言模型，解決同一個服務(wù)被授權(quán)模型里的規(guī)則同時接受和拒絕的問題.Fisler 等人[14]分析基于角色的規(guī)則訪問控制策略，認為多終端決策圖是一種可擴展的訪問控制策略解決方法，是實現(xiàn)規(guī)則訪問控制策略的驗證方法.Abdullah 等人[15]提出一種形式化規(guī)則檢查器，通過控制器安全策略，以確?？刂破骱蛨?zhí)行器的行為安全性.Wang 等人[16]針對物聯(lián)網(wǎng)安全審計日志分散在各個設(shè)備上，不能用于重建安全事務(wù)工作流的問題，提出一種以平臺為中心的物聯(lián)網(wǎng)集中審計方法，此方法對物聯(lián)網(wǎng)應(yīng)用程序和設(shè)備應(yīng)用編程接口進行高效的自動化測試，以生成包括惡意行為在內(nèi)的系統(tǒng)活動審計日志.Bu 等人[17]針對錯誤的設(shè)備控制對系統(tǒng)正確性產(chǎn)生影響的問題，提出一種端到端的線性混合自動機模型，用來協(xié)助非專業(yè)物聯(lián)網(wǎng)用戶進行規(guī)則可信檢查，確保物聯(lián)網(wǎng)系統(tǒng)可用性.Ma[18]認為基于規(guī)則圖的方法，可以解決數(shù)據(jù)不一致性問題，并利用規(guī)則圖來描述規(guī)則的層次結(jié)構(gòu)，動態(tài)評估數(shù)據(jù)的一致性.Nandi[19]為了解決用戶在編寫規(guī)則觸發(fā)部分經(jīng)常犯錯誤的問題，開發(fā)一種靜態(tài)技術(shù)，根據(jù)用戶編寫的動作，自動生成正確的規(guī)則觸發(fā)條件.Abe 等人[20]為解決規(guī)則調(diào)用的數(shù)據(jù)缺失問題，抽取物聯(lián)網(wǎng)描述符號來標(biāo)準化規(guī)則，從而提高規(guī)則的質(zhì)量.Yang 等人[21]通過Petri 網(wǎng)的形式驗證規(guī)則系統(tǒng)，并推導(dǎo)出規(guī)則間的關(guān)聯(lián)矩陣，解決規(guī)則的規(guī)范化和完整性的驗證，避免基于規(guī)則的系統(tǒng)受到規(guī)則結(jié)構(gòu)錯誤的影響.Wang 等人[22]提出一種計算執(zhí)行可滿足性的框架，用于發(fā)現(xiàn)規(guī)則內(nèi)部的漏洞，但在實踐中發(fā)現(xiàn)由于物聯(lián)網(wǎng)平臺的封閉性，這種模型的信息流很難獲得.為了解決這個問題，文獻[22]的作者基于自然語言處理開發(fā)用于推斷規(guī)則信息流的算法.

1.2 規(guī)則沖突檢測

Fang 和Lu[23]針對軟件定義網(wǎng)絡(luò)中的規(guī)則沖突問題，通過等量劃分分區(qū)包級別的方法，解決軟件定義網(wǎng)絡(luò)中交換機流量條目產(chǎn)生的規(guī)則沖突.Cui 等人[24]針對基于軟件定義網(wǎng)絡(luò)的交換機中流規(guī)則產(chǎn)生的沖突導(dǎo)致網(wǎng)絡(luò)功能失效的問題，設(shè)計一種基于事務(wù)的流規(guī)則沖突檢測方法，這種方法可以隔離不同網(wǎng)絡(luò)的流規(guī)則，以避免不同網(wǎng)絡(luò)功能之間的干擾.Batisra等人[25]提出一種基于一階邏輯的沖突檢測方法，解決OpenFlow 網(wǎng)絡(luò)中隨著交換機和主機數(shù)量的增加，管理流變得復(fù)雜而出現(xiàn)的規(guī)則沖突.Magill 和Blum[26]針對規(guī)則可能源于不同的來源而產(chǎn)生的一致性問題，他們借鑒特征交互的經(jīng)驗，擴展無線傳感技術(shù)，解決在無線傳感器網(wǎng)絡(luò)中不同來源的沖突規(guī)則導(dǎo)致一致性維護問題.Born 等人[27]通過擴展模型轉(zhuǎn)換工具，解決基于規(guī)則的模型轉(zhuǎn)換中發(fā)生的沖突和依賴.Jiang等人[28]針對一個大型自組織系統(tǒng)中子系統(tǒng)間具有利益和價值的沖突問題，使用邏輯形式化事件推演，使得每個子系統(tǒng)能夠發(fā)現(xiàn)和解決其系統(tǒng)自身內(nèi)部的規(guī)則沖突.Zhang 等人[29]通過計算概率描述節(jié)點狀態(tài)作業(yè)的權(quán)重，得到邏輯推理規(guī)則的沖突度量.Diller 等人[30]提出一種從不一致的語言中提取語義的方法，并以正態(tài)性假設(shè)的形式擴展規(guī)則表達方式，解決規(guī)則中自然語言表達知識產(chǎn)生的沖突，然而他們沒有考慮物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則沖突.Shehara 等人[5]提出一種需求交互分類法，用于對軟件系統(tǒng)中的需求交互進行分類和識別，并提出一種半形式化的沖突檢測方法（IRIS）來識別需求沖突，并且開發(fā)可以應(yīng)用到特定領(lǐng)域的插件[31].Shah 等人[32]提出一種檢測物聯(lián)網(wǎng)系統(tǒng)中不完整規(guī)則的機制，同時考慮條件獨立的觸發(fā)條件引起的規(guī)則沖突，這種方法把規(guī)則看作使用基于事件的編程語言的程序，實現(xiàn)對規(guī)則不完整性和沖突的檢測，然而能檢測的沖突類型不夠全面.李秀[33]基于知識圖譜，對智能家居領(lǐng)域內(nèi)的作動器進行隱式?jīng)_突檢測，根據(jù)作動器功能進行自動分類，實現(xiàn)不限類型的作動器設(shè)備之間的隱式規(guī)則沖突檢測.Lin 等人[34]通過設(shè)計規(guī)則的形式化模型，把這些規(guī)則定義為一個元組，包含觸發(fā)器、執(zhí)行器和狀態(tài)，然后通過分類、組合的方法對規(guī)則進行處理，從而描述規(guī)則之間的冗余關(guān)系，消除和避免冗余的規(guī)則出現(xiàn)，提高系統(tǒng)執(zhí)行效率.

本節(jié)所提的研究工作對規(guī)則沖突類型分析不全面，并且檢測結(jié)果的準確性不高，造成規(guī)則沖突漏檢和錯檢的問題.本文工作對這些形式化方法進行改進，針對物聯(lián)網(wǎng)系統(tǒng)的規(guī)則沖突進行檢測.

2 方 法

2.1 針對物聯(lián)網(wǎng)系統(tǒng)的規(guī)則的形式化分析

為了更清楚地表達物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則，以及區(qū)分不同的規(guī)則沖突類型，本文針對物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則，給出相應(yīng)的形式化結(jié)構(gòu).物聯(lián)網(wǎng)規(guī)則涉及到控制主體、動作、觸發(fā)條件、規(guī)則、符號5 個成分，具體結(jié)構(gòu)如圖4 所示.

Fig.4 Rule structure圖4 規(guī)則結(jié)構(gòu)

1）控制主體sub由標(biāo)識id、主體類型type、占用標(biāo)志mon、主體屬性attribute、屬性值value構(gòu)成.其中type,attribute是字符串類型，mon={0，1}，value為數(shù)值類型.

控制主體可表示為sub={id，type，mon，attribute，value}.

2）動作action由執(zhí)行動作的控制主體sub、被動作影響的屬性attribute、動作關(guān)系運算符op、操作的屬性值value構(gòu)成.其中op={＜，=，＞，≤，≥，≠}.

動作可表示為action={sub，attribute，op，value}.

動作的 集合表 示為actions={action（i）| 0 ≤i＜n，n∈ N}.

3）觸發(fā)條件condition由控制主體類型type、約束屬性attribute、約束關(guān)系運算符op、約束屬性值value構(gòu)成.其中type表示引用上述規(guī)則成分中的控制主體sub里的元素type.

觸發(fā)條件可表示為condition={type，attribute，op，value}.

觸發(fā)條件的集合可以表示為conditions={condition（i）| 0 ≤i＜n，n∈ N}.

4）規(guī)則rule由id標(biāo)識、觸發(fā)條件conditions、動作actions構(gòu)成.

規(guī)則可表示為rule={id，conditions，actions}.

規(guī)則的 集合可 以表示為rules={rule（i）|0 ≤i＜n，n∈ N} .

5）為了表達連續(xù)的系統(tǒng)狀態(tài)，定義運算符#，將離散的系統(tǒng)狀態(tài)數(shù)值value轉(zhuǎn)化成區(qū)間范圍.具體為:

其中value是一個數(shù)值，在添加符號#后，數(shù)值value與關(guān)系符op進行運算，將數(shù)值value轉(zhuǎn)換成連續(xù)的區(qū)間范圍；-∞代表負無窮，+∞代表正無窮，（）是開區(qū)間，是 閉區(qū)間，（]是 開閉區(qū)間，[）是閉開區(qū)間.

通過以上規(guī)則結(jié)構(gòu)表示，可以清晰地表達下面的規(guī)則交互關(guān)系.

2.2 規(guī)則的交互關(guān)系

規(guī)則間的沖突是由規(guī)則交互關(guān)系引起的，為了深入分析規(guī)則沖突類型，首先分析規(guī)則交互關(guān)系.2個規(guī)則的約束條件部分和動作部分的影響，稱為規(guī)則的交互關(guān)系.通過對規(guī)則間存在的交互關(guān)系進行分析，總結(jié)出相容觸發(fā)條件、控制同一非獨占主體、控制同一獨占主體、相同控制動作、相反控制動作、互斥影響值、規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的動作、規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的反向動作，8 種規(guī)則交互關(guān)系如表1 所示.

1）CC表示2 個規(guī)則可以在同一個系統(tǒng)場景中觸發(fā)，稱為相容觸發(fā)條件；

2）SSS表示2 個規(guī)則控制同一個非獨占類型主體，稱為控制同一非獨占主體；

Table 1 Rule Interaction表1 規(guī)則交互關(guān)系

3）SMS表示2 規(guī)則控制同一個獨占類型主體，稱為控制同一獨占主體；

4）SA表示2 個規(guī)則擁有相同的控制動作，稱為相同控制動作；

5）DA表示2 個規(guī)則擁有相反的控制動作，稱為相反控制動作；

6）MV表示2 個規(guī)則對環(huán)境屬性影響是互斥的，稱為互斥影響值；

7）RC（Ri，Rj）表示規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的動作，稱為規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的動作；

8）OR（Ri，Rj）表示規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的反向動作，稱為規(guī)則Ri觸發(fā)條件依賴規(guī)則Rj的反向動作.

通過以上8 個規(guī)則交互關(guān)系的總結(jié)，為下面的規(guī)則沖突類型的形式化表達提供符號表示.

2.3 規(guī)則的沖突類型

由于規(guī)則之間存在交互關(guān)系，使得規(guī)則間產(chǎn)生沖突.為了更清晰地描述規(guī)則的沖突，本文通過調(diào)研和分析物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則交互關(guān)系，將目前的物聯(lián)網(wǎng)系統(tǒng)中的規(guī)則沖突分為7類，分別是:執(zhí)行覆蓋沖突、執(zhí)行矛盾沖突、消極影響沖突、獨占資源沖突、直接忽略依賴沖突、直接循環(huán)依賴沖突、間接循環(huán)依賴沖突.

規(guī)則的沖突類型以及形式化表達如表2 所示.

Table 2 Rule Conflict Type表2 規(guī)則沖突類型

類規(guī)則沖突所表達的含義為：

1）一個規(guī)則的所有動作包含在另一個規(guī)則中，導(dǎo)致前一條規(guī)則是冗余的，稱為執(zhí)行覆蓋沖突；

2）系統(tǒng)執(zhí)行2 個規(guī)則的先后順序不同，導(dǎo)致系統(tǒng)狀態(tài)不同，稱2 個規(guī)則互為執(zhí)行矛盾沖突；

3）2 個規(guī)則的動作影響同一個屬性，導(dǎo)致一個規(guī)則影響另一個規(guī)則的執(zhí)行效率，稱2 個規(guī)則互為消極影響沖突；

4）2 個規(guī)則調(diào)用同一個獨占資源，稱2 個規(guī)則互為獨占資源沖突；

5）規(guī)則Rj的觸發(fā)條件依賴規(guī)則Ri的相反動作，導(dǎo)致規(guī)則Rj永遠不被觸發(fā)，稱規(guī)則Rj直接忽略依賴規(guī)則Ri；

6）規(guī)則Ri的觸發(fā)條件依賴規(guī)則Rj的動作，規(guī)則Rj的觸發(fā)條件依賴規(guī)則Ri的動作，導(dǎo)致系統(tǒng)進入死鎖狀態(tài)，稱2 個規(guī)則互為直接循環(huán)依賴沖突；

7）多條規(guī)則間的觸發(fā)條件、動作形成依賴環(huán)路，導(dǎo)致系統(tǒng)進入死鎖狀態(tài)，稱這些規(guī)則互為間接循環(huán)依賴沖突.

表2 中的對稱關(guān)系表示2 個規(guī)則調(diào)換表述順序，表達的語義不變.非對稱關(guān)系表示2 個規(guī)則調(diào)換表述順序，表達的語義發(fā)生改變.例如規(guī)則Ri依賴規(guī)則Rj與規(guī)則Rj依賴規(guī)則Ri，調(diào)換規(guī)則表述順序后，表達的語義不一樣，屬于非對稱關(guān)系.

經(jīng)過以上的規(guī)則沖突類型總結(jié)以及形式化定義，總結(jié)出物聯(lián)網(wǎng)智能系統(tǒng)中規(guī)則沖突的特點，并且能對這些規(guī)則沖突進行區(qū)分，能夠比較容易地對這些沖突進行檢測.

2.4 基于形式化規(guī)則的沖突檢測方法

規(guī)則沖突檢測方法流程如圖5 所示.該方法流程主要包括2 部分，分別是規(guī)則預(yù)處理和規(guī)則沖突計算.

Fig.5 The workflow of rule conflict detection method圖5 規(guī)則沖突檢測方法流程

規(guī)則沖突檢測方法的輸入是已有的規(guī)則庫和待檢測的規(guī)則，已有的規(guī)則庫是指在進行規(guī)則沖突檢測之前，就已經(jīng)存在的規(guī)則集合；待檢測的規(guī)則是指需要與已有規(guī)則庫進行檢測是否存在沖突的規(guī)則.

在進行規(guī)則檢測前，需要對輸入的規(guī)則庫和待檢測規(guī)則進行預(yù)處理.首先，需要將規(guī)則解析成粒度較小的規(guī)則元素，目的是將輸入的規(guī)則解析成可以用作形式化表達的元素.隨后進行規(guī)則分解，目的是將復(fù)雜的規(guī)則分解為只包含與邏輯關(guān)系的規(guī)則.規(guī)則預(yù)處理之后，得到分解之后的規(guī)則庫與待檢測的規(guī)則.接下來需要對規(guī)則沖突進行分析，通過規(guī)則交互關(guān)系分析和規(guī)則沖突檢測，得到最終的規(guī)則沖突檢測結(jié)果.

2.4.1 規(guī)則預(yù)處理

規(guī)則預(yù)處理包括規(guī)則解析和規(guī)則分解2 個步驟.

規(guī)則解析的目的是將輸入的規(guī)則解析成可以形式化表達的元素.首先，待檢測的規(guī)則和規(guī)則庫里的規(guī)則輸入到規(guī)則解析子模塊；然后，根據(jù)物聯(lián)網(wǎng)系統(tǒng)規(guī)則的形式化結(jié)構(gòu)，將文本類型的規(guī)則解析成由id標(biāo)識、觸發(fā)條件conditions、動作actions構(gòu)成的形式化元素；最后，分別輸出規(guī)則元素庫和規(guī)則元素.

規(guī)則分解是為了簡化包含復(fù)雜邏輯的規(guī)則，這樣可以便于后續(xù)的規(guī)則沖突檢測.本文利用析取范式將規(guī)則進行分解.例如規(guī)則R1經(jīng)過析取范式轉(zhuǎn)化得到R2，R2可以表達為觸發(fā)條件只包含“與”邏輯關(guān)系的2 個規(guī)則R3和R4.此過程將同時包含“與”“或”邏輯關(guān)系的規(guī)則R1，分解成為只包含“與”邏輯關(guān)系的規(guī)則R3和R4.

規(guī)則分解步驟首先輸入規(guī)則元素庫和規(guī)則元素；然后，經(jīng)過上述析取范式分解；最后，輸出分解之后的規(guī)則庫與待檢測的規(guī)則.

2.4.2 規(guī)則交互關(guān)系分析

規(guī)則交互關(guān)系分析是后續(xù)規(guī)則沖突檢測的基礎(chǔ)，對于任意2 個規(guī)則，它們之間的交互關(guān)系可以采用4 個步驟進行分析，首先，遍歷2 個規(guī)則的約束部分和動作部分；其次，獲取規(guī)則的形式化元素；然后，將形式化元素依據(jù)規(guī)則交互關(guān)系形式化表達，匹配出相應(yīng)的規(guī)則交互關(guān)系；最后，輸出2 個規(guī)則的交互關(guān)系.

規(guī)則交互關(guān)系分析如算法1 所示.算法1 輸入規(guī)則Ri和Rj，輸出規(guī)則關(guān)系re.算法1 的行②③分別遍歷Ri和Rj的約束conditions部分和動作actions部分.行④～?獲取規(guī)則的形式化元素，依據(jù)表1 定義的規(guī)則交互關(guān)系，設(shè)置規(guī)則關(guān)系變量re的標(biāo)志位.行?輸出存儲2 個規(guī)則交互關(guān)系的變量re.最終計算出待檢測規(guī)則與規(guī)則庫所有規(guī)則的交互關(guān)系.規(guī)則交互關(guān)系名稱用表1 中符號縮寫表示，部分符號依賴于圖4的規(guī)則結(jié)構(gòu).

算法1.規(guī)則交互關(guān)系分析算法.

2.4.3 規(guī)則沖突檢測

獲得規(guī)則間的交互關(guān)系之后，接下來對規(guī)則間的沖突進行檢測.規(guī)則之間的沖突檢測可以采用4 個步驟進行分析：首先，計算待檢測規(guī)則與規(guī)則庫里所有規(guī)則的依賴關(guān)系；其次，獲取當(dāng)前參與檢測的2 個規(guī)則的交互關(guān)系；然后，匹配規(guī)則沖突類型；最后，輸出規(guī)則沖突檢測信息.

規(guī)則沖突檢測如算法2 所示.為了簡化表達，規(guī)則交互關(guān)系名稱用表1 中符號縮寫表示.算法2 輸入規(guī)則庫RDB和待檢測規(guī)則Ri，輸出規(guī)則沖突檢測信息.算法2 的行②定義變量relyM，它是MAP 數(shù)據(jù)類型，它的鍵是規(guī)則id，它的值是當(dāng)前規(guī)則所依賴的其他規(guī)則id組成的隊列，用來存儲規(guī)則間的依賴關(guān)系信息.行③～?遍歷RDB里的所有規(guī)則，將此規(guī)則的id作為鍵，直接依賴的所有規(guī)則id作為值存到relyM變量中.行?～?遍歷RDB中的規(guī)則Rj，其中Ri,Rj作為函數(shù)relation（）的輸入，得到Ri,Rj的關(guān)系re.re與relyM作為函數(shù)matchConflict（）的輸入，根據(jù)表2 的規(guī)則沖突類型來匹配規(guī)則沖突信息.最終計算出待探測規(guī)則與規(guī)則庫里的規(guī)則是否有沖突，如果有沖突則輸出具體沖突類型.其中行⑥～⑧調(diào)用算法1 的規(guī)則交互關(guān)系分析函數(shù)relation（）.

算法2.規(guī)則沖突檢測算法.2.4.4 規(guī)則沖突檢測實例

通過算法1 和算法2 的實現(xiàn)，可以在任何情況下檢測到圖3（a）和圖3（b）中的規(guī)則沖突.

對于圖3（a），2 條規(guī)則R1，R2經(jīng)過規(guī)則預(yù)處理分別得到：

規(guī)則R1，R2通過規(guī)則交互關(guān)系分析，conditionR1中的room[Environment],temperature與conditionR2中的room[Environment],temperature相等但conditionR1中的“＜25”與conditionR2中的“＞20”不是包含關(guān)系，所以它們可以同時觸發(fā)，使得ComCon字段取值為真；actionR1中 的temperature與actionR2中 的temperature相等，但是actionR1中的heater不等于conditionR2中的air_conditioner并且actionR1中的“＞27”與actionR2中的“＜15”沒有交集，所以MutVal字段取值為真.這2 個規(guī)則經(jīng)過規(guī)則沖突檢測，符合消極影響沖突的形式化表達，輸出的規(guī)則R1，R2具有消極影響沖突.

對于圖3（b），2 條規(guī)則R3和R4經(jīng)過規(guī)則預(yù)處理分別得到：

由于不需要分析規(guī)則R5，即可檢測到規(guī)則沖突，所以R5不再描述.通過規(guī)則交互關(guān)系分析，conditionR3中的light[Light],isOn與conditionR4中 的light[Light],isOn相等，但conditionR3中的“=1”與conditionR4中的“=0”不是包含關(guān)系，所以它們可以同時觸發(fā)，使得ComCon字段取 值為真；actionR3中 的curtain,isOn與actionR4中的curtain,isOn相等，所以字段SamShareSub取值為真；actionR3中的“=0”不等于conditionR4中的“=1”，使得字段DifAct取值為真.2 個規(guī)則經(jīng)過規(guī)則沖突檢測，符合執(zhí)行矛盾沖突的形式化表達，輸出規(guī)則R3，R4具有執(zhí)行矛盾沖突.

上述的規(guī)則檢測過程不依賴于真實環(huán)境，所以在任何環(huán)境下都可以檢測到規(guī)則沖突.但本文所比較的3 種方法需要在特定的條件下才能檢測出這2種規(guī)則沖突.

3 實驗及結(jié)果分析

3.1 研究問題

為了驗證所提出的方法的有效性，本文提出3 個研究問題：

問題1.與已有的沖突檢測方法相比，本文的方法能檢測的規(guī)則沖突類型是否更全面.

問題2.與已有的沖突檢測方法相比，本文的方法檢測結(jié)果效果是否更好.

問題3.進行方法自身的對比實驗，通過刪掉方法中的某一部分或某幾個部分，來驗證方法的有效性.

3.2 實驗對象

本文的實驗對象是2 個物聯(lián)網(wǎng)系統(tǒng)，分別為智能會議室模擬系統(tǒng)和智能漁業(yè)模擬系統(tǒng).這2 個系統(tǒng)的介紹及其中所包含的規(guī)則如表3 和表4 所示.

智能會議室模擬系統(tǒng)是利用物聯(lián)網(wǎng)技術(shù)，通過規(guī)則控制會議室環(huán)境和多媒體設(shè)備的模擬系統(tǒng)，其中規(guī)則包括了20 條執(zhí)行覆蓋類型規(guī)則、22 條執(zhí)行矛盾類型規(guī)則、24 條消極影響類型規(guī)則、28 條獨占資源類型規(guī)則、26 條直接忽略依賴類型規(guī)則、32 條直接循環(huán)依賴類型規(guī)則、45 條間接循環(huán)依賴類型規(guī)則、91 條場景初始化規(guī)則.

Table 3 Introduction to Intelligent Conference Room System表3 智能會議室系統(tǒng)介紹

Table 4 Introduction to Intelligent Fishery System表4 智能漁業(yè)系統(tǒng)介紹

智能漁業(yè)模擬系統(tǒng)是利用物聯(lián)網(wǎng)技術(shù)，通過規(guī)則控制船舶航行、魚群捕撈的模擬系統(tǒng)，其中規(guī)則包括了22 條執(zhí)行覆蓋類型規(guī)則、26 條執(zhí)行矛盾類型規(guī)則、20 條消極影響類型規(guī)則、24 條獨占資源類型規(guī)則、28 條直接忽略依賴類型規(guī)則、30 條直接循環(huán)依賴類型規(guī)則、33 條間接循環(huán)依賴類型規(guī)則、86 條場景初始化規(guī)則.

3.3 實驗環(huán)境及參數(shù)設(shè)置

實驗的軟件環(huán)境為Jdk 1.8,Maven 3.6,Intelli-JIDEA 2020.1,Drools 7.4.另外，本文對實驗的數(shù)據(jù)進行處理，3 個實驗都從規(guī)則庫的每個類型中隨機抽取80%的規(guī)則文件進行實驗，為了避免規(guī)則沖突類型分布不均勻的問題.

3.4 評價指標(biāo)

沖突檢測不僅要報告出2 條規(guī)則是否有沖突，還要給出具體出現(xiàn)了哪種沖突.為此采用精確率（precision，P）、召回率（recall，R）和F1 值來作為實驗的評估指標(biāo)[35].

計算評價指標(biāo)之前，首先需要計算多分類問題的混淆矩陣，混淆矩陣的每個元素cij（i，j∈ N）代表樣本實際分類i，分類器判定分類j的計數(shù)；再計算實際屬于i類型樣本wi的二分混淆矩陣元素a,b,c,d；最后計算評價指標(biāo)F1（wi）.其中

實驗中執(zhí)行1 次規(guī)則沖突檢測方法，將算法得出的規(guī)則沖突結(jié)果與真實規(guī)則沖突結(jié)果采用以上評估指標(biāo)進行量化.

3.5 實驗結(jié)果及分析

1）問題1.與已有的沖突檢測方法相比，本文的方法能檢測的規(guī)則沖突類型是否更全面.

為了探究本文的方法能檢測的規(guī)則沖突類型是否更全面，將本文的方法FRCD 與現(xiàn)有的3 種規(guī)則沖突檢測方法對比，實驗結(jié)果如表5 所示.其中FRCD檢測到7 種沖突，UTEA 檢測到3 種沖突，SPIDER 檢測到4 種沖突，IRIS 檢測到3 種沖突.

Table 5 Detection Results of Different Types of Conflics by Four Methods表5 4 種方法對不同沖突類型的檢測結(jié)果

SPIDER 支持直接循環(huán)依賴，但在本次實驗中沒有檢測到.因為SPIDER 算法是在系統(tǒng)進入沖突狀態(tài)才檢測到?jīng)_突，但本實驗的物聯(lián)網(wǎng)系統(tǒng)執(zhí)行了這2種類型規(guī)則，將進入死鎖狀態(tài)，導(dǎo)致系統(tǒng)崩潰，所以這種沖突檢測方法不適用.

UTEA 支持直接循環(huán)依賴、間接循環(huán)依賴2 種類型的沖突檢測，但在本次實驗中沒有檢測到.因為UTEA 算法是在系統(tǒng)進入沖突狀態(tài)才檢測到?jīng)_突，但本實驗的物聯(lián)網(wǎng)系統(tǒng)執(zhí)行了直接循環(huán)依賴和間接循環(huán)依賴這2 種類型規(guī)則，將進入死鎖狀態(tài)，導(dǎo)致系統(tǒng)崩潰，所以這2 種沖突檢測方法不適用.

本文通過調(diào)研和分析已有的物聯(lián)網(wǎng)系統(tǒng)的規(guī)則，依據(jù)規(guī)則間的環(huán)路結(jié)構(gòu)總結(jié)出直接循環(huán)依賴沖突、間接循環(huán)依賴沖突.規(guī)則間冗余總結(jié)出執(zhí)行覆蓋沖突.規(guī)則的約束條件部分描述了系統(tǒng)資源狀態(tài)，可以總結(jié)出獨占資源沖突.規(guī)則的動作部分描述了系統(tǒng)執(zhí)行狀態(tài)可以總結(jié)出執(zhí)行矛盾沖突、消極影響沖突、直接忽略依賴沖突.針對物聯(lián)網(wǎng)系統(tǒng)規(guī)則的每個部分，F(xiàn)RCD 方法都進行了詳細的沖突類型總結(jié)，因此可以得出結(jié)論，本文的方法能檢測的規(guī)則沖突類型更全.

2）問題2.與已有的沖突檢測方法相比，本文的方法檢測結(jié)果的F1 值是否更高.

為了探究本文的方法檢測結(jié)果的F1 值是否更高，將本文的方法FRCD 與現(xiàn)有的3 種規(guī)則沖突檢測算法對比.

模擬智能會議室系統(tǒng)實驗對比結(jié)果如表6 所示，F(xiàn)RCD 算法檢測到7 種沖突，覆蓋了所有沖突類型，它們的F1 指標(biāo)均值為78.3%.UTEA 檢測到3 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響，它們的F1 指標(biāo)均值為68.6%.SPIDER 檢測到4 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響、直接忽略依賴，它們的F1 指標(biāo)均值為57.9%.IRIS 檢測到3 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響，它們的F1 指標(biāo)均值為69.0%.在智能會議室系統(tǒng)上，F(xiàn)RCD 算法的檢測效果超過了其他3 種算法.

Table 6 P，R and F1 Score Results Comparison of Intelligent Conference System for Different Methods表6 智能會議室系統(tǒng)不同方法的精確率、召回率和F1 值結(jié)果對比 %

模擬智能漁業(yè)系統(tǒng)實驗對比結(jié)果如表7 所示，F(xiàn)RCD 算法檢測到7 種沖突，覆蓋了所有沖突類型，它們的F1 指標(biāo)均值為90.9%.UTEA 檢測到3 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響，它們的F1 指標(biāo)均值為87.1%.SPIDER 檢測到4 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響、直接忽略依賴，它們的F1 指標(biāo)均值為63.1%.IRIS 檢測到3 種沖突：執(zhí)行覆蓋、執(zhí)行矛盾、消極影響，它們的F1 指標(biāo)均值為77.5%.在智能漁業(yè)船舶系統(tǒng)上，F(xiàn)RCD 算法的檢測效果超過了其他3 種算法.

Table 7 P，R and F1 Score Results Comparison of Intelligent Fisher System for Different Methods表7 智能漁業(yè)船舶系統(tǒng)不同方法的精確率、召回率和F1 值結(jié)果對比 %

本文進一步分析了FRCD 檢測效果優(yōu)于其他3種方法的原因.其中UTEA 需要初始化規(guī)則的場景，而FRCD 則不需要，這樣可以避免為不充分的初始化場景制定而影響沖突檢測效果.并且實現(xiàn)了直接循環(huán)依賴、間接循環(huán)依賴2 種沖突靜態(tài)檢測，避免系統(tǒng)因循環(huán)依賴的規(guī)則而進入死鎖狀態(tài).

另外，F(xiàn)RCD 算法考慮了連續(xù)的系統(tǒng)變量，但是SPIDER 與IRIS 只考慮規(guī)則中離散的系統(tǒng)狀態(tài).在本文的實驗案例對應(yīng)的物聯(lián)網(wǎng)系統(tǒng)中，存在連續(xù)的系統(tǒng)狀態(tài)，因此對這些連續(xù)的系統(tǒng)狀態(tài)檢測是必要的.

實驗分析可以得出，本文的方法檢測結(jié)果的F1值更高.

3）問題3.通過逐漸刪掉方法中的某一部分或某幾個部分，來驗證方法的有效性.

本文在模擬智能會議室系統(tǒng)上，通過逐一刪掉表1 中定義的規(guī)則交互關(guān)系進行實驗.其中RC（Ri，Rj）和OR（Ri，Rj）不參與刪除，因為去掉其中任意一個會導(dǎo)致某種類型沖突不能檢測.實驗結(jié)果如表8 所示，F(xiàn)RCD 在所有類型沖突指標(biāo)都是最高的.

Table 8 F1 Score Result Comparison of Reduce Rule Interaction for Different Methods表8 減少規(guī)則交互關(guān)系在不同方法F1 值結(jié)果對比 %

FRCD-CC代表去掉CC部分，它除了執(zhí)行覆蓋、執(zhí)行矛盾、獨占資源類型的評價指標(biāo)不變，其他沖突類型指標(biāo)都有所降低.因為CC用來推斷2 條規(guī)則是否在同一個場景中觸發(fā)，如果它取值為假，不會進入與其相關(guān)的沖突類型匹配，如果它取值為真，將進一步探測與其相關(guān)的沖突類型.去掉CC部分，相當(dāng)于CC取值永遠為真，導(dǎo)致某些規(guī)則檢測錯誤.

FRCD-SSS代表去 掉SSS部 分，F(xiàn)RCD-SMS代 表去掉SMS部分，這2 個實驗的檢測指標(biāo)都有所降低.因為這2 個實驗沒有考慮到設(shè)備是否可以被共享，一些涉及設(shè)備并發(fā)的規(guī)則沖突無法檢測，導(dǎo)致沖突檢測指標(biāo)降低.

FRCD-SA代表去掉SA部分，F(xiàn)RCD-DA代表去掉DA部分，這2 個實驗的檢測指標(biāo)，除了消極影響類型的評價指標(biāo)不變，其他指標(biāo)都有所降低.因為這2 個實驗沒有考慮規(guī)則全部的動作類型，SA和DA同時考慮才能構(gòu)成規(guī)則動作的全集，它們只檢測了一部分的動作類型，導(dǎo)致沖突檢測指標(biāo)降低.

FRCD-MV代表去掉MV部分，它的檢測指標(biāo)都有所降低.因為此實驗沒有考慮不同規(guī)則影響到同一個屬性值而造成的沖突，導(dǎo)致沖突檢測指標(biāo)降低.

實驗分析可以得出，本文的方法有必要考慮所有的規(guī)則交互關(guān)系部分.

4 總結(jié)

本文提出了一種針對物聯(lián)網(wǎng)系統(tǒng)架構(gòu)中的核心部件系統(tǒng)控制邏輯中規(guī)則的沖突檢測方法.該方法首先對物聯(lián)網(wǎng)系統(tǒng)的規(guī)則進行分析與歸類，利用形式化的方法將物聯(lián)網(wǎng)中的規(guī)則及不同的規(guī)則沖突進行建模.針對不同的規(guī)則沖突，它們的形式化表達有所不同，從而使得不同的規(guī)則沖突能夠清楚地得到檢測.然后，該方法能夠?qū)斎氲奈锫?lián)網(wǎng)規(guī)則進行解析，得到規(guī)則的各種條件和動作，基于解析的結(jié)果，對這些條件進行分解，這樣可以幫助簡化規(guī)則條件邏輯.最后，根據(jù)不同的規(guī)則沖突類型，檢測出相應(yīng)的沖突.本文在2 個物聯(lián)網(wǎng)系統(tǒng)中開展的實驗，與已有的3 種物聯(lián)網(wǎng)規(guī)則沖突檢測方法進行對比，實驗結(jié)果顯示，本文方法的規(guī)則沖突檢測效果，是這4 種方法中最好的.但是，本文提出的方法還存在完善的方面.例如，物聯(lián)網(wǎng)規(guī)則沖突類型分析還不夠全面，同時算法只能報告哪些規(guī)則間存在沖突，不能給出修改成正確規(guī)則的指導(dǎo)建議，還缺少了規(guī)則間沖突關(guān)系可視化展示，這些都是將來有待研究的工作.

作者貢獻聲明：楊波提出了算法思路、實驗方案和修改論文；郭浩然負責(zé)完成實驗并撰寫論文；馮俊輝參與實驗；李戈提出實驗方案并修改論文；金芝提出指導(dǎo)意見并修改論文.