摘要：在普适计算环境中，由传感器收集到的情境信息刻画了物理世界的属性与特征，但情境信息之间有可能产生冲突。于是情境不一致性的检测成为重要的一个课题。本文首先分析了已有的基于事件间happen-before关系的并发事件侦测算法，其运用矢量时钟来判断区间是否重叠，从而侦测有无情境不一致发生。通过详细分析，该算法有三个缺陷：采用中央集中式结合的网络架构，中心检测节点数据流量过大；在网络中节点数量多的情况下，逻辑时钟数组使算法空间复杂度过高；算法检测精确度不高，一些冲突情况无法侦测到。
针对CEDA的缺陷，我们提出了快照时钟算法SCA。算法是依据逻辑时钟来判断区间的关系。SCA的网络舍弃了中心节点，使网络不再是中心集中式的。SCA中的每个进程不用维护时钟数组，只需单个时钟值。于是将时钟的空间复杂度由O(n)降低至O(1)，将每个事件的侦测时间复杂度由O(n2)降低至O(n)。SCA也能解决一些CEDA无法侦测的情况。
最后我们给出了SCA的实验验证与性能分析，无论是从实验还是理论方面分析，快照时钟算法都有良好且稳定的表现，适用于各种节点数，消息延迟时间不同和事件持续时间各异的情境感知应用。
关键字：普适计算 情境不一致性侦测 逻辑时钟 happen-before
Abstract：In pervasive computing environment, context collected by sensors is a piece of information that captures the characteristics of physical world. Since there are always conflicts among the contexts, the detection of context inconsistency becomes an important issue.
Firstly, we analyze the CEDA (Concurrent Events Detection for Asynchronous consistency checking algorithm), which is based on happen-before relationship. CEDA uses Vector Clock to check if two intervals overlap which means local events concurrent happen. The algorithm is limited by three problems. CEDA’s centralized network makes the clustering head overflow; CEDA suffers a large space complexity and message complexity when there are a great number of nodes in network; the accuracy of algorithm is low because it cannot find many other conflicts.
To this end, we propose the Snapshot Clock Algorithm (SCA). SCA also checks the relationship between two intervals by comparing the logical clock timestamp. However, SCA discards clustering head, and uses single clock value instead of the vector clock in SCA. Thus SCA is decentralized and has less complexity. SCA’s space complexity decreases from O(n) to O(1) and time complexity decreases from O(n2) to O(n). Moreover, SCA can find conflict situations which CEDA cannot.
At last, we conduct extensive experiments and theoretical analysis to further evaluate SCA. Both experiments and performance analysis show that SCA accurately detects context inconsistency in pervasive computing environment. SCA is desirable for different context-aware applications which vary in the number of nodes, the time of message delay and the duration of events.
Keywords：Pervasive Computing , Detection of Context Inconsistency,Logical Clock, Happen-before Relationship
