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

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

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

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

4（北京大學計算機學院 北京 100871）

5（高可信軟件技術教育部重點實驗室（北京大學）北京 100871）

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

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

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

Fig.1 Typical Internet of things system architecture圖1 典型的物聯網系統(tǒng)架構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

1.2 規(guī)則沖突檢測

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

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

2 方 法

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

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

Fig.4 Rule structure圖4 規(guī)則結構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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ī)則沖突類型的形式化表達提供符號表示.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.1 規(guī)則預處理

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

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

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

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

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

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

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

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

2.4.3 規(guī)則沖突檢測

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

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

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

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

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

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

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

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

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

3 實驗及結果分析

3.1 研究問題

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

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

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

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

3.2 實驗對象

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

智能會議室模擬系統(tǒng)是利用物聯網技術，通過規(guī)則控制會議室環(huán)境和多媒體設備的模擬系統(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)是利用物聯網技術，通過規(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)境及參數設置

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

3.4 評價指標

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

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

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

3.5 實驗結果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結

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

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