Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (7): 1893-1898.DOI: 10.11772/j.issn.1001-9081.2016.07.1893

Previous Articles     Next Articles

Distributed Rete algorithm in smart environment

WANG Chengliang1,2, WEN Xin2   

  1. 1. Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education (Chongqing University), Chongqing 400044, China;
    2. College of Computer Science, Chongqing University, Chongqing 400044, China
  • Received:2015-12-18 Revised:2016-03-16 Online:2016-07-10 Published:2016-07-14
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61004112), the Fundamental Research Funds for the Central Universities (CDJZR12180006).

智能环境下分布式Rete算法

汪成亮1,2, 温鑫2   

  1. 1. 信息物理社会可信服务计算教育部重点实验室(重庆大学), 重庆 400044;
    2. 重庆大学 计算机学院, 重庆 400044
  • 通讯作者: 温鑫
  • 作者简介:汪成亮(1975-),男,四川资阳人,教授,博士,CCF高级会员,主要研究方向:无线传感器网络、物联网、人工智能、复杂系统计算与控制;温鑫(1992-),男,江西宁都人,硕士研究生,主要研究方向:无线传感器网络、人工智能、物联网。
  • 基金资助:
    国家自然科学基金资助项目(61004112);中央高校基本科研基金资助项目(CDJZR12180006)。

Abstract: Concerning the problem that rule-based inference engine in smart environment needs to centralize data to sink node resulting in excessive data transmission in sensor network, a Minimum Transmission Cost of Rete Distribution Scheme algorithm (MCoRDS) based on Rete network cost model was proposed. Through the dependence statistics of sub-rule patterns in Rete Network on fact data, it was found that many sub-rule patterns could be reasoned nearby the source data collected sensor. Data transmission to sink node could be cut down and the data transmission of whole sensor network was decreased by distributing sub-rule patterns of Rete network into the sensor which firstly collected all the source data for it. Compared to centralized inference which places the Rete network in the sink node, 4 experiments were conducted. In the 4th experiment, total sensor network hops was reduced from 85000 to 8036, about 90.5% reduction, the other experiments had some reduction too. The experimental results show that MCoRDS has lower data transmission, especially in the case of large-scale rules and low frequency rule trigger.

Key words: smart environment, rule-based inference engine, sensor network, Rete algorithm, Rete distribution

摘要: 针对智能环境中基于Rete的规则推理引擎需要将数据集中到sink节点,导致传感器网络中数据传输量过大的问题,建立了Rete网络代价模型,并提出了最小传输代价的Rete分布的算法(MCoRDS)。该算法通过统计Rete网络中子模式对事实数据的依赖,发现大部分子模式在对应事实数据采集Sensor附近便具备了计算推理条件,故将Rete网络中的子模式规则分布到最早汇集其所需所有事实数据的Sensor中,即可避免事实数据进一步往sink节点的传输,从而大量减少传感器网络中的数据传输量。对比将Rete网络放置在sink节点的集中式推理进行了4组仿真实验。其中第4组实验,传感器网络总跳数由85000减至8036,减少约90.5%;其余组实验传输跳数也有一定的减少。实验结果表明,最小代价的Rete分布具有更小的数据传输量,在规则触发频率低、规则规模较大的情况下尤甚。

关键词: 智能环境, 规则推理引擎, 传感网络, Rete算法, Rete分布

CLC Number: