传感器数据流复杂查询结果的数据起源跟踪方法

摘要

本发明公开了一种传感器数据流复杂查询结果的数据起源跟踪方法，包括以下步骤：步骤1、确定起源追踪查询滑动窗口大小；步骤2、对起源查询进行规范化描述；步骤3、对起源追踪查询的类别进行判断并设计相应算法；步骤4、设计起源追踪的框架；步骤5、对整个起源追踪算法进行实施，从而实现对传感器数据流复杂查询结果的数据起源的跟踪。突破现有传感器数据管理系统中无法支持复杂查询回溯的技术局限，将数据起源追踪概念首次引入传感器数据流上的复杂查询领域，为新型在线追踪应用提供可行的解决方案。

说明书

技术领域

本发明属于传感器数据仓库中冰山查询结果的逆向跟踪技术，特别是传感器数据流复杂查询结果的数据起源跟踪方法。

背景技术

新一代传感器和传感器(无线射频识别)技术为人们提供了强大的感知、理解并管理世界的能力，许多基于传感器的新应用迫切需要一种现有数据管理系统不具备的能力——追溯事件和查询结果的起源，即支持高层应用到低层数据反向查询的数据起源追踪能力。冰山查询在大量输入的数据元组上返回极少的查询结果，是传感器数据仓库上典型的、频繁应用的一类查询。由于冰山查询涉及到一个属性或属性集上的聚集函数，同时传感器数据具有不确定性、冗余性、蕴含时空性、需要在线响应等特点，数据来源可能不可访问或访问的代价高昂，因此追踪传感器冰山查询结果的数据起源信息非常困难，为数据库、传感器网络、复杂事件处理等研究领域提出了许多新的挑战。

数据的起源记载了对数据处理的整个历史，包括数据的起源和处理这些数据的所有后继过程，数据起源追踪(Data Lineage Tracing)，也可称为“数据起源追踪(Data Provenance Tracing)”，主要关注怎样从用户感兴趣的高层视图回溯到导出此视图的原始资源数据的问题。冰山查询的数据起源追踪是基于传感器技术的定位、追踪应用必需支持的功能，数据分析、数据质量检查等阶段会频繁地对冰山查询的结果进行回溯，其执行效率极大地影响传感器数据管理系统响应查询的能力，而这种功能在传统数据仓库中的地位是可有可无的。

数据起源的相关研究近几年吸引了数据集成、Web搜索、语义标注等领域学者的广泛关注。国外在数据仓库、E-science、质量追踪、保证数据可信性和再现性方面已经有一些数据起源的研究成果，而国内在数据起源方面的研究才刚刚开始。目前数据起源追踪主要有3种途径：查询求逆、标注和工作流日志。

(1)查询求逆是在起源追踪时通过对查询或者视图定义进行分析，求逆(执行逆查询)的结果就是数据的起源(Y.W.Cui，J.Widom，J.L.Wiener.Tracing theLineage of View Data in a Warehousing Environment.ACM Transactions onDatabase Systems，2000，25(2)：179-227)。由于它是在需要用到数据起源时才进行计算分析，因而又称为“lazy”方式。这种方式主要是在早期把数据起源用于视图维护和更新问题时提出来的。查询求逆计算方法的缺点在于，它不完全适用于复杂查询。因为现有的查询求逆研究中都是假设复杂查询满足一定的条件并且可以被规范化或者改写，但实际上并不是所有的查询都是如此，即使满足一定的条件，求出的数据起源有时也并不精确。

(2)将标注用于数据起源就是在标注中记录一些关于数据出处或者产生过程历史的信息(P Buneman，S Khanna，W C Tan.On Propagation of Deletions andAnnotations Through Views.In：Proc of the Int 1Conf on Management of Data(ACMSIGMOD/PODS)，2002.150-158)。由于这种方式是在一开始就让数据通过标注携带一些数据起源信息，因而又称为“eager”方式。关于标注的组织、管理等有一系列问题有待解决。Bhagwat等(D Bhagwat，L Chiticariu，W C Tan，G Vijayvargiya.An Annotation Management System for Relaional Databases.In：Proc of the Int′lConf on Very Large Data Base(VLDB)，2004.900-911)设计了一种基于关系的管理标注的数据模型，其中每个数据项(属性)都带有标注，当数据在转移的时候标注能够随着数据一起转移。这种存储模式的问题是冗余比较大，而且事实上要求修改关系模式，这在很多情况下是不可能的，并且只支持属性粒度上的标注。Buneman等(Peter Buneman，Adriane P.Chapman，James Cheney.ProvenanceManagement in Curated Databases SIGMOD 2006，June 27-29，2006，Chicago，Illinois，USA.)研究了可在数据库之间复制记录的通用数据起源技术，提出一种追踪用户行为的方法，浏览源数据库并将数据复制到curated数据库，用可查询的便利形式记录用户的行为。另外W7标注模式(Sudha Ram，Jun Hu，Regi ThomasGeorge.PROMS：A System for Harvesting and Managing Data Provenanc.)是目前具有一定的语义信息的先进标注模式，其结构比逆查询语句具有更大的灵活性。由于大多数现有的数据管理系统是没有存储标注的，因此首要问题就是如何创建或者获取标注。在有些系统中提供了相应的工具集帮助用户创建标注，但是从数据起源的角度来说，传感器数据流本身就蕴含了适于自动获取的时空信息，到目前为止，还没有人做过有关传感器数据起源自动标注和手动标注方面的研究。

(3)工作流日志是基于消息层次的对数据加工的记录。已有的研究认为工作流日志没有足够的语义信息，即使将它收集到，对于重塑工作流得到原始数据也很难，在实际的操作过程中工作流日志往往起到辅助作用，作为其他两种方式的补充。然而，正是这种辅助作用对传感器数据流连续处理的性质具有重要意义，工作流日志有助于采用有向图搜索、状态迁移等方法对数据起源实现有效地追溯，这也是现有研究成果中未曾考虑到的。

在国内，刘喜平等首次介绍了数据起源的概念、意义和发展(刘喜平，万常选.数据起源研究综述.科技广场.2005，1：47-52)；李亚子比较了几种常用的数据起源描述模型，提出由XML Schema描述逐渐发展到构建领域本体进而实现推理机制，是数据来源追踪的发展方向之一(李亚子.数据起源标注模式与描述模型.现代图书情报技术.2007，153(7)：10-13)。近几年国内仅在语义标注领域有一些研究成果，然而这些研究并不是为了解决起源追踪问题。与常规静态数据库上的起源追踪相比，传感器数据面临的起源追踪问题更为复杂、起源追踪查询代价更为高昂。传感器的大量部署，会导致如洪水般的标签信息涌入系统，必须解决传感器数据的喷涌问题。目前公认的方法是在传感器数据管理系统中设置数据连接器，包括传感器中间件、事件处理与内存数据cache。原始数据经过复杂中间处理过程，增加了追踪的难度。在考虑推导规则不确定性的前提下，使用起源跟踪发现适合物化的推导规则集，是传感器数据处理领域中一个令人感兴趣的未解难题(R.Derakhshan，M.E.Orlowska，Li Xue.RFID Data Management：Challenges andOpportunities.in Proceeding of IEEE International Conference on RFID 2007，26-28March 2007Page(s)：175-182)。

现有的起源追踪技术在应用到传感器数据流中存在以下四个问题：(1)已有的数据起源研究大多只是针对科学数据库，未考虑以数据流处理为特征的传感器数据起源追踪快速响应的需要，这使得现有的起源追踪方法很难直接应用到传感器数据管理，需要从创建新起源追踪模型的高度来解决传感器数据起源的追踪问题；(2)现有针对数据起源的研究都停留在变化相对缓慢的静态数据集定性分析与描述上，无法适应变化的传感器数据流；(3)逆反性并不是数据处理查询或函数的通常属性，如果不能精准确定数据项，即使找到了弱逆函数对应用的意义也不大。(4)为设计反函数或逆查询，需要预先理解数据处理的复杂过程，这就使得方案只能针对特定的应用，很难自动化。同时为逆查询或逆函数编码必须花费极大的努力，阻碍了这种技术的应用。

发明内容

本发明所解决的技术问题在于提供一种快速精确的传感器数据流复杂查询结果的数据起源跟踪方法。

实现本发明目的的技术解决方案为：一种传感器数据流复杂查询结果的数据起源跟踪方法，包括以下步骤：

步骤1、确定起源追踪查询滑动窗口大小；

步骤2、对起源查询进行规范化描述；

步骤3、对起源追踪查询的类别进行判断并设计相应算法；

步骤4、设计起源追踪的框架；

步骤5、对整个起源追踪算法进行实施，从而实现对传感器数据流复杂查询结果的数据起源的跟踪。

本发明与现有技术相比，其显著优点：(1)突破现有传感器数据管理中无法支持复杂查询回溯的技术局限，将数据起源追踪概念首次引入传感器数据流上的冰山查询领域，为新型在线追踪应用提供可行的解决方案。(2)以数据流在线处理的方式建立适应传感器数据不确定性、不完整性等特征的数据起源追踪模型；(3)根据不等概采样原理动态确定起源追踪查询窗口的大小，适应数据流变化；(4)基于流式处理的传感器数据起源追踪运算理论与起源追踪查询算法(涉及区域位置、距离、时间的逆选择、投影、并、交、聚集及连接运算)。本发明建立的计算模型针对快速变换的数据流，提出适用于包括已知处理逻辑和未知处理逻辑等不同情况的传感器数据流逆查询算法，可在线得出数据起源信息。(5)代价小，数据起源追踪结果集精确，伸缩性能好。

下面结合附图对本发明作进一步详细描述。

附图说明

图1为本发明的传感器数据流复杂查询结果的数据起源跟踪方法流程图。

图2为传感器数据流起源追踪含义示意图。

图3为流式传感器数据起源追踪系统框架图。

图4为传感器数据复杂查询导出数据流示例图。

图5为借助中间传感器导出数据流迭代计算起源图。

图6为不同起源追踪方法和起源追踪时间的关系图。

图7为三种起源追踪方法对传感器数据的起源追踪精度的对比图。

具体实施方式

结合图1，本发明的一种传感器数据流复杂查询结果的数据起源跟踪方法，包括以下步骤：

步骤1、确定起源追踪查询滑动窗口大小；具体包括以下步骤：

步骤11、对起源追踪查询滑动窗口进行定义，起源追踪查询窗口大小为w_i个间隙，W_i＝(t-w_i，t)，其中t表示当前时刻，设标签i出现在阅读器的有效范围，在窗口W_i期间阅读器在每个间隙以相同的概率p_i读取标签i；

步骤12、对起源追踪查询滑动窗口间隙进行读取概率为p_i的相互独立的Bernoulli试验；假设在W_i的所有间隙，标签i只出现在W_i的子集S_i，令p_i^avg表示在这些观测间隙上的平均经验读取率，$p_i^{\mathrm{avg}}=\mathrm{\Sigma t}\in S_i{p}_{i,t}/\left|S_i\right|,$其中p_i，t根据阅读器的标签列表信息计算得到，我们视S_i为二项采样，|S_i|为B(w，p_i^avg_i)的二项随机变量；

步骤13、选择合适的w_i从而确保以较高概率读到标签i，若在平滑窗口中间隙的个数w_i满足不等式则可以保证在窗口W_i中以大于1-δ的概率读取标签i，式中δ为期望的误差概率，从而确定起源追踪查询滑动窗口大小。

步骤2、对起源查询进行规范化描述；具体是在关系数据模型基础上，引入概率化元组，提供不确定性起源信息追踪的标准过程，并为用户提供声明性的连续查询语言接口。

步骤3、对起源追踪查询的类别进行判断并设计相应算法；具体包括以下步骤：

步骤31、根据是否已知起源查询对应的正向查询模式，和起源是否为标准关系模式，将起源追踪类型划分为四种类型，若已知正向查询为标准关系SPJ(选择、投影、连接)视图模式，则执行步骤32；若已知正向查询为标准关系ASPJ(聚集、选择、投影、连接)视图模式，则执行步骤33；若已知正向查询为非标准关系ASPJ视图模式，则执行步骤34；若未知正向查询模式且操作为非标准关系ASPJ视图模式，则执行步骤35；

步骤32、已知正向查询为标准关系SPJ视图模式起源追踪查询，将所有SPJ视图都转换成SPJ典型形式，使用基于典型形式的追踪查询计算指定元组的起源；

步骤33、已知正向查询为标准关系ASPJ视图模式起源追踪，以中间结果作为聚集元组与基本流之间的纽带，在需要的时候从基本流计算得出中间结果的相关部分，在数据仓库中将整个中间结果存储为物化辅助视图；

步骤34、已知正向查询为非标准关系ASPJ视图模式起源追踪查询，

将作用在传感器数据流的操作分为分散与合并两类，若每个输入数据项产生0个或多个相互独立的数据项，则视为分解操作，采用枚举输入数据项的方法确定输出项的起源；否则采用合并操作，即将合并操作细分为上下文无关合并和保留键值合并，以渐增的方式验证输入项的子集；

步骤35、未知正向查询模式且操作为非标准关系ASPJ视图模式，采用动态切片技术计算指定元组起源，设计未知操作定义的黑盒起源追踪方法。

步骤4、设计起源追踪的框架；具体包括以下步骤：

步骤41、对起源查询信息模型基本实体进行分类，将其分为数据流和查询，数据流由基本流与导出流两种类型组成：基本流来自系统之外的某一设备、传感器网络、或者一个服务；导出流来自于基本流或其它的导出流；

步骤42、设计分布式事件处理系统，该系统以中央服务方式接受查询请求，在多个分布式查询执行引擎上部署查询，并且在各自生命周期时间内执行查询；系统监控各个查询引擎上的负载，根据重用规则、查询和网络代价估计对查询进行优化，将收到的查询分布到有效的查询执行引擎；

步骤43、在步骤42的基础上，构建基于数据流模式的传感器数据起源查询框架，该框架包括起源的组织、存储策略、起源与数据的结合方式，以及起源的传播方式。

步骤5、对整个起源追踪算法进行实施，从而实现对传感器数据流复杂查询结果的数据起源的跟踪。

本发明提供了一种可以在滑动窗口传感器数据流中追溯事件和查询结果起源的技术和能有效审核传感器数据质量、验证事件响应过程、快速重组整合不同的数据源的一种细粒度传感器数据起源追踪方法。本发明主要针对实时流入系统的传感器数据来确定数据起源所在的滑动窗口大小、形式化起源查询、判断起源追踪查询的类别、实施起源追踪的框架及算法组成，具体为：

1、确定起源追踪查询滑动窗口大小

对于流入系统的传感器实时数据，为了计算经过复杂处理后得到的结果元组的起源信息，需要对输入数据流集(或在输入数据流集上定义的视图)执行传感器数据起源追踪方法。由于数据流潜在的无限性，不可能将所有的数据全部存储后才计算，因此必须确定合适的数据流窗口(滑动窗口)，大小适中的滑动窗口即保留了窗口中的采样样本的统计完备性，又降低了数据流的存储代价。根据不等概采样原理确定起源追踪查询依附的滑动窗口尺寸。

定义1.1，传感器数据流集ψ：由多条数据流S组成，滑动窗口中的S部分相当于关系数据模型中的表，元组t∈S，由多个属性值组成。

定义1.2，询问周期：是完成阅读器与周围所有标签的通信协议的一次迭代过程。

定义1.3，epoch(间隙)：是阅读器对所有其识别的标签进行跟踪的最小时间单位，由多个询问周期的结果共同组成，典型的间隙值是0.2-0.25秒。在每一个间隙，除了标签ID，阅读器同时也记录一些附加信息(诸如每个标签的询问响应次数，标签最后被读取的时刻等)，并将这些信息周期性传送给客户。

设起源追踪查询窗口大小为w_i个间隙，W_i＝(t-w_i，t)，设标签i出现在阅读器的有效范围，在窗口W_i期间阅读器在每个间隙以相同的概率p_i读取标签i，本发明视每个间隙为成功读取概率为p_i的相互独立的Bernoulli试验。这意味着窗口中标签i的被成功观测的个数是一个随机变量，服从参数为(w_i，p_i)的二项分布。假设在W_i的所有间隙，标签i只出现在W_i的子集S_i，令p_i^avg表示在这些观测间隙上的平均经验读取率，$p_i^{\mathrm{avg}}={\Sigma }_{t\in S_i}{p}_{i,t}/\left|S_i\right|,$其中p_i，t根据阅读器的标签列表信息计算得到，我们视S_i为二项采样，|S_i|为B(w，p_i^avg_i)的二项随机变量。根据标准概率理论，|Si|的期望和方差为$E\left[\right|S_i\left|\right]=w_i·p_i^{\mathrm{avg}},$$\mathrm{Var}\left[\right|S_i\left|\right]=w_i·p_i^{\mathrm{avg}}·(1-p_i^{\mathrm{avg}}).$

为了自适应调整每个标签窗口大小以及建立二项采样模型，首先考虑窗口尺寸w_i的大小，保证在窗口w_i中有足够的间隙可以观测到标签i(前提是标签位于阅读器的可读范围之内)，选择合适的w_i可以确保以较高概率读到标签i。

引理1.1，令p_i^avg表示在一个间隙中标签i的观测概率，若在平滑窗口中间隙的个数w_i满足不等式则可以保证在窗口W_i中以大于1-δ的概率读取标签i。

证明：由于对标签i的观测属于相互独立的Bernouli试验，在w_i个样本上希望标签i的读取概率为设此概率≤δ，两边取ln得$w_i\ln (1-p_i^{\mathrm{avg}})\le \ln \delta ,$根据不等式-x≥ln(1-x)其中x∈(0，1)，则如果$-w_i{p}_i^{\mathrm{avg}}\le \ln \delta$也能保证$w_i\ln (1-p_i^{\mathrm{avg}})\le \ln \delta$成立，即$w_i\ge \frac{\ln (1/\delta )}{p_i^{\mathrm{avg}}},$证毕。

也就是可以以高概率保证完备性。

2、传感器数据起源追踪语义的形式化描述

本发明同等看待数据的不确定性、数据起源过程与数据本身的重要性，在关系数据模型(关系数据模型能较好的描述时空对象的属性特征，但不能表示时空对象的时间和空间特征)基础上，引入概率化元组解决传感器数据的不确定性问题，提供起源追踪标准过程，融入数据流模式中时间滑窗的概念与技术，为用户提供声明性的连续查询语言接口。

定义2.1，possible-tuple(可能元组)：数据流中可能出现的元组，反应元组内容的不确定性。

定义2.2，existed-tuple(存在元组)：每个existed-tuple由一个或多个possible-tuple组成，代表实际的possible-tuple组合。

定义2.3，probalility(出现概率)：依附于possible-tuple和existed-tuple，代表出现当前取值的可能性。出现概率可通过统计一段时间某标签的读取率与间隙的比值计算，实质是平均读出率。

定义2.4，lineage(起源)：联系possible-tuple和导出此元组的possible-tuple。设λ为作用在ψ上的操作(若属于关系操作构造，λ表示视图定义，记为v)，如果存在λ^-1，$\forall I\subseteq \psi ,$λ^-1(λ(I))＝I，$\forall O\subseteq \psi ,$λ(λ^-1(O))＝O，其中I是输入集、O是输出项，称λ^-1为λ的逆操作，对于O中的任意元组t，称λ^-1(O)为t的起源。数据流上起源追踪含义如图2所示。

定义2.5，带有起源的数据流集ψ_L：一个ψ_L是三元组(R，D，λ^-1)序列，其中R是关系集，D是包含I(R)的符号集，且λ^-1是构建在D到2^D上的逆操作。I(R)包含二元组(i，j)，i代表existed-tuple，j代表其existed-tuple的索引。

ψ＝(R，D，λ^-1)是一个数据流集，设符号集$D_k\subseteq D,$ψ的可能的子集ψ_k可按如下方式获得：

1.如D(i，j)∈D_k，那么对于每个j≠j′，$D(i,j^{\prime })\notin D_k,$

2.$\forall D(i,j)\in D_k,$${\lambda }^{-1}\left(D(i,j)\right)\subseteq D_k$

3.如果对某existed-tuple，t_i不存在一个D(i，j)∈D_k，那么t_i是一个可能existed-tuple，且$\forall D(i,j)\in t_i,$λ^-1(D(i，j))＝φ，或${\lambda }^{-1}\left(D(i,j)\right)\subset ⃒S_k.$

条件1指同一existed-tuple中不同的possible-tuple是互斥的，在每种可能的实例中至多出现一次。条件2加强起源语义，如果possible-tuple在一个可能实例中出现，一定是导出的那个possible-tuple，此即意味着一个方向。

设计的传感器数据流起源追踪查询语言如下：

SELECT OriginStream_j.Attr

FROM OriginStream₁，…OriginStream_n

WHERE lineage(OriginStream₁，…OriginStream_n)

AND OtherPredication…

WINDOW Now-Size，[Confidence Factor]

其中OriginStream为起源数据流(或导出流)，Attr为流中的属性名，lineage为计算起源函数的通用函数(过程)，OtherPredication为其余标准SQL谓词，Now表示当前时刻，WINDOW子句定义了大小为Size的滑动窗口，可选项ConfidenceFactor代表起源信息的置信度因子。

3、数据流起源模型与起源追踪信息系统框架

设计了一种面向传感器冰山查询的数据流起源追踪模型，并构建了基于数据流模式的传感器数据起源查询框架，包括起源的组织、存储策略、起源与数据的耦合方式，以及起源的传播方式等。

起源查询信息模型基本实体包括数据流和查询，数据流由基本流与导出流两种类型组成：基本流来自于事件处理系统之外的某一设备、传感器网络、或者一个服务；导出流来自于基本流或其它的导出流，事件处理也会产生导出流。实体的起源信息分为两部分：在数据流和查询注册器件收集到的信息为静态起源，例如元信息是静态起源的一部分；在查询处理期间收集到的信息为动态起源，例如数据流流动速率的变化就是一种动态起源。

在起源追踪处理框架方面，本发明设计了一种分布式事件处理系统，以中央服务方式接受查询请求，在多个分布式查询执行引擎上部署查询，查询执行引擎在各自生命周期时间内被执行。系统监控查询引擎上的负载，按照分布式负载动态的需求产生新的查询执行引擎。查询计划根据重用规则、查询和网络代价估计对查询进行优化，将收到的查询分布到有效的查询执行引擎。流式传感器数据起源追踪系统框架图如图3所示。

资源管理负责维护系统的当前状态，与查询计算进行交互。起源追踪服务对系统中当前资源的变化保持追踪，同时提供GUI(Graphical User Interface)监控当前的查询、数据流和计算性资源。用户通过调用起源服务注册输入数据流和冰山查询。当提交新的查询时，系统产生导出流的注册。冰山查询注册之后，用户可以向起源数据集添加注释和元信息等附加信息。

4、传感器起源追踪理论与算法描述

针对不同类型的传感器数据流细粒度起源追踪，设计出适用于已知模式(标准关系操作)信息、未知模式信息的数据起源追踪方法、包括对由标准ASPJ(聚集、选择、投影、连接)等标准关系操作符组成的复杂查询、以及由非ASPJ标准关系操作符组成的复杂查询的不同数据流起源追踪算法。

4.1、已知标准关系操作的起源追踪

若已知对传感器数据的各种操作的定义，且操作属于标准的关系操作，采用如下方法计算起源。基本思想是使用基表上的关系查询来计算Select-Project-Join(SPJ)视图中某个元组的起源，应用查询到数据流S，返回特定视图v得到的元组t在S中的起源。

4.1.1、SPJ视图起源追踪查询

定义4.1，起源跟踪查询，ψ为数据流集，v是ψ上的视图，给定元组t∈v(ψ)，TQ_t，v为v和t的起源追踪查询，当前仅当TQ_t，v(ψ)＝v^-1_ψ(t)，其中v^-1_ψ(t)为t在ψ中根据v的起源，TQ_t，v与数据流实例ψ无关。类似地可以定义视图元组集T的追踪查询，记为TQ_T，v(ψ)。

所有SPJ视图都可以转换成关系代数转换序列的形式其中π_A、σ_C、S₁、分别指关于条件A的投影、关于条件c的选择、数据流、连接，称此形式为SPJ典型形式，SPJ的变换不会同影响视图元组的起源[CUI96]。因此，给定一个SPJ视图，首先将其转换为SPJ典型形式，使用基于典型形式的追踪查询计算指定元组的起源。下面引入用于SPJ视图的起源追踪查询的附加操作符。

定义4.2，分解操作符ω，设S为数据流，分解操作符ω将S分解成表序列，每个序列中的表是S向属性集$A_i\subseteq S(i=1..m)$的投影。

${\omega }_{A_1,...,A_m}\left(T\right)=<{\pi }_{A_1}\left(T\right),...,{\pi }_{A_m}\left(T\right)>$

定理4.1，设数据流集ψ包含基数据流S₁，...，S_m，为S上的SPJ视图。给定元组t∈V，在ψ中的起源可以采用如下作用在基数据流上的查询计算得出，给定元组集$T\subseteq V,$T的起源跟踪查询为

证明：设V₁＝σ_C(V₂)，V＝π_A(V₁)，可以证明若操作由多个步骤组成，那么最终结果元组的起源，可通过对查询树上的多级视图的进行逐级追踪获得，于是有

${v^{-1}}_{\Psi }\left(t\right)={{v_1}^{-1}}_{\Psi }\left({{{\pi }_A}^{-1}}_{V_1}\left(t\right)\right)$

$={{v_1}^{-1}}_{\Psi }\left({\sigma }_{A=t}\left(V_1\right)\right)$

$={{v_2}^{-1}}_{\Psi }\left({{{\sigma }_C}^{-1}}_{V_2}\left({\sigma }_{A=t}\left(V_1\right)\right)\right)$

$={{v_2}^{-1}}_{\Psi }\left({\sigma }_{A=t}\left(V_1\right)\right)$

$={\omega }_{S_1,...,S_m}\left({\sigma }_{A=t}\left(V_1\right)\right)$

4.1.2、ASPJ视图的起源追踪

尽管SPJ视图的起源追踪无需中间结果，但是如果未存储特定的中间结果，包含聚集的ASPJ视图是不可跟踪的，因为在含有聚集操作的视图中会新增一些由聚集函数计算得出的属性，而这些属性在基本流中根本就没有。因此必须以中间结果作为聚集元组与基本流之间的纽带。中间结果的相关部分可以在需要的时候从基本流计算得出，整个结果也可以在数据仓库中存储为物化辅助视图，下面的论述中假设所有的中间聚集结果有效。

(A)ASPJ规范化形式

与SPJ视图不同，ASPJ视图没有简单的规范化形式，因为在ASPJ视图的定义中，某些选择、投影、连接操作不能推到聚集操作之前(或之后)，这样会破坏关系操作的等价性。然而通过计算和合并某些SPJ操作，可以将任意ASPJ视图查询树转变为由操作符序列组成的形式，称这种序列为ASPJ段，即为ASPJ规范化形式。ASPJ段可能会省略一些操作符，尽管ASPJ规范化形式中除了最远的每个段必须包含一个操作符(否则此段不能与相邻的段合并)。当某一元操作符被省略时，我们假设存在一个相应的通用操作符取而代之。流S的通用聚集操作符为α_S，通用投影操作符为π_S，通用选择操作符为σ_S。

定义4.3，ASPJ规范化形式，设v为数据流集ψ上的ASPJ视图定义。

(1)v＝S，S为ψ中的基流，是ASPJ规范化形式。

(2)是ASPJ规范化形式，如果v_j是具有非平凡顶端聚集操作符的ASPJ规范化形式，j＝1..k。其中G，aggr(B)表示定义在属性B上的聚集函数

每次基于原始视图定义，通过对某个操作符进行追踪来确定任意视图的起源的方法需要存储或重新计算每个操作符的中间结果，代价高昂。将ASPJ视图定义转换为规范化形式，可以存储或重计算较少的中间结果，追踪每个段中所有的操作符。

(B)单层ASPJ视图的起源追踪查询

由上面ASPJ段定义的视图称为单层ASPJ视图，类似于SPJ视图，可以使用一个查询为单层ASPJ视图追踪元组的起源。

定理4.2，为单层ASPJ视图，给定元组t∈V，t在S₁，...，S_m上由v定义的起源，可采用如下作用于基流上的查询计算得出：

给定元组集$T\subseteq V,$T的起源跟踪查询为

证明：且V＝α_G，aggr(B)(V₁)

${v^{-1}}_{\Psi }\left(t\right)={{v_1}^{-1}}_{\Psi }\left({{{\alpha }_{G,\mathrm{aggr}\left(B\right)}}^{-1}}_{V_1}\left(t\right)\right)={{v_1}^{-1}}_{\Psi }\left({\sigma }_{G=t.G}\left(V_1\right)\right)$

(C)多级ASPJ视图起源追踪算法

给定通用的ASPJ视图定义，首先将视图转换成ASPJ规范化形式，并将其分割成ASPJ段的集合，为每个段定义一个中间视图，通过自顶向下的中间视图层级式递归追踪来追踪元组的起源。在每一层，使用单层ASPJ视图的追踪查询来计算当前追踪的元组在下一层的视图或基本流。

v是规范化形式的视图定义，元组t∈v(ψ)，过程TupleLineageTracing()根据ψ上的v计算元组t的起源。主过程算法StreamLineageTracing()计算元组集$T\subseteq V$的起源。设v＝v′(V₁，...，V_k)其中v′为单层ASPJ视图。V_j＝v_j(ψ)，j＝1..k作为基本流或中间视图是有效的。此过程首先在<V₁，...，V_k>中，根据定理4.2使用单层ASPJ视图查询TQ(T，v′，<V₁，...，V_m>)计算T的起源<V₁^*，...，V_k^*>。然后根据v_j(j＝1..k)的定义递归计算每个元组集合V_j^*的起源，将结果连接到视图元组集合，得到整个列表的起源。

procedure TupleLineageTracing(t；v；ψ)

in：欲追踪起源的元组t，视图定义v，数据流集ψ

out：数据流集ψ中元组t的起源(由v生成元组t)

1return(StreamLineageTracing({t}；v；ψ))；

procedure StreamLineageTracing(T；v；ψ)

in：欲跟踪的元组集合T，视图定义v，数据流集ψ

out：数据流集ψ中元组集T的起源(由v生成元组集T)

1 if v＝S∈ψ then return(<T>)；

2 //otherwise v＝v′(v₁，...，v_k)其中v′为单层ASPJ视图

3 <V₁^*，...，V_k^*>←TQ(T，v′，{V₁，...，V_k})；//V_j＝v_j()为中间视图或基本流，j＝1..k

4 D*←Φ；

5 for j←1 to k do

6 D*←D*·SteamLineageTracing(V_j^*；v_j；D)；

7 return(D*)；

4.2、非关系操作的起源追踪

对传感器数据流的许多操作不属于标准关系操作，无法将操作规范化为ASPJ标准形式，因此本发明专为传感器数据流的非关系操作设计了起源追踪方法。不失一般性，我们将作用在传感器数据流的操作分为分散与合并两类。

定义4.5，分解操作：每个输入数据项产生0个或相互独立的多个数据项：$\forall I,\lambda \left(I\right)=\underset{i\in I}{Y}\lambda \left(\right\{i\left\}\right).$由分解操作产生输出项o的起源定义为*(o，I)＝{i∈I|o∈T({i})}。

设计算法TraceDecompose(λ，O，I)跟踪由分解操作产生输出项集的起源，其中以输出项集作为参数，而不是用单个的输出项作为参数。

procedure TraceDecompose(λ，O*，I)

I*←Φ；

for each i∈I do

ifλ({i})∩O*≠Φ then I*←I*∪{i}；

return I*；

定义4.6，合并操作：λ(I)＝O＝{o₁，...o_n}，存在唯一的互不相交的划分I₁，...I_n λ(I_k)＝{o_k}成立k＝1..n，I₁，...I_n称为输入划分，且由操作λ得出的o_k的起源I_k为λ*(o_k，I)＝I_k

设计TraceAggregator(λ，O*，I)跟踪由分解操作产生的输出项集O*的起源，λ(I*)＝O*，I*是I的子集，其补集产生O中其余的项。方法是以渐增的方式验证I的子集，如发现某个子集I′使λ(I′)＝O*，而λ(I-I′)＝O-O*，则仅需验证的超集即可找到起源，显著加快工作效率。

procedure TraceAggregator(λ，O*，I)

L←按集合势大小排列I的子集序列；

for each I∈L

if λ(I*)＝O*then

if(I-I*)＝O-O*then break；

else L←按集合势大小排列I*的全部超集序列；

Return I*

经分析，数据流上的合并操作又可以进一步细分为上下文无关合并和保留键值合并。

定义4.7，上下文无关合并：任何两个输入数据项，或者属于相同的输入划分，或者总是不属于同一个划分。换句话说，上下文无关合并确定划分的方法是，任一输入项仅依赖自身的值，而不依赖其它输入项的值。

定义4.8，保留键值合并：在关系含义上设输入输出项每个项包含唯一的key值，为项i记做i.key，如果对任何输入集I及其划分I₁，...，I_n，对于输出λ(I)＝{o₁，...，o_n}，所有I_k的子集I′产生与输出项键值相同的唯一输出项，即${\forall I}^{\prime }\subseteq I_k,\lambda \left(I^{\prime }\right)=\left\{o_k^{\prime }\right\}$且o′_k.key＝o_k.key(k＝1..n)，称λ是保留键值合并。

定理4.3，保留键值合并是上下文无关合并。

证明：设λ为保留键值的合并，与i′，或者同属于相同输入划分，或者不属同一划分。

采用反证法，设λ不是上下文无关的合并，那么存在输入集I与I′和元组项i与i′

(1)当i与i′属于同一划分Ij时，设λ(I_j)＝o_j，根据保留键值合并的定义，λ({i})与λ({i′})产生的输出项具有相同的键值o_j.key。

(2)当i与i′属于不同的划分I_j和I_k，λ(I_j)＝o_j，λ(I_k)＝o_k，根据保留键值合并的定义，λ({i})产生带有键值o_k.key的项，λ({i′})产生带有键值o_j.key的项，所以o_j.key≠o_k.key，与保留键值合并的定义矛盾。

定理4.4，如果操作λ是一个带有逆转λ^-1的合并操作，那么对于所有λ(I)＝O的实例，经由λ生成的所有o∈O的起源为λ^-1({o})。

证明：由于λ为合并操作，根据定义4.6，λ(I)＝D＝{o₁，...，o_n}，I中存在一个唯一的划分I₁，...，I_n，满足λ(I_k)＝{o_k}，其中k＝1..n，且I_k是o_k的起源。根据定义2.4，λ^-1(λ(I))＝I，所以，$\forall o_k\in O,$λ^-1({o_k})＝λ^-1(λ(I_k))＝I_k。

注意实际上完整性不需要定理4.4支持，仅仅weak inverse需要，weak inverse要求λ^-1(λ(I))＝I必须成立，而λ(λ^-1(O))＝O不必成立。

根据定理4.4，如果可逆操作是合并操作，那么就可以使用逆操作来实现起源追踪，如果可逆操作是分解操作，就不能应用逆操作计算起源。通常逆转查询是求起源的最有效方式。

例1，列表合并，两个属性输入集，产生两个属性输出集，根据第一个属性对输入集分组，产生一个输出项，包含对第一个属性值的分组值。I＝{<1，a>，<1，c>，<2，b>，<2，g>，<2，h>}，输出O＝λ(I)＝{<1，“a，c”>，<2，“b，g，h”>}，λ的逆λ^-1输入数据项的第二个属性进行分隔产生多个项，即λ^-1(O))＝I。

若操作λ是合并操作，根据定理4.4，使用λ^-1执行数据项的起源追踪，例如给定输出项o＝{<2，“b，g，h”>}，o的起源为P^-1({o})＝{<2，b>，<2，g>，<2，h>}。

如果已知非关系操作的映射关系，则在计算输出项的起源时可以根据模式映射将输出项的起源限制在输入项集的子集中，这个子集可能很小，从而提升计算起源的效率。例如假设操作λ有反向模式映射，在查找输入项的起源的时候，可以首先查找输入项子集$I^{\prime }\subseteq \{i\in I|i.A=g(o.B)\},$然后使用TraceAggregator(λ，o，I′)枚举I′的每个子集，寻找o的起源$I*\subseteq I^{\prime }.$

4.3、未知操作定义的黑盒起源追踪方法。

当关系操作和非关系操作都无法得知操作的细节，即不存在逆操作的黑盒操作情况下，本发明采用动态切片技术计算指定元组起源。

动态切片是一种调试技术，可以在可执行语句中捕捉错误。近期研究表明动态切片技术对定位运行时软件错误十分有效，动态切片可以有效地分析未知操作[Xiangyu Zhang，Precise dynamic slicing algorithms，International Conference onSoftware Engineering，2003]。本发明采用roBDD[Randal E Bryant，Graph-basedalgorithms for boolean function manipulation，IEEE，1986]等专门技术着重处理数据依赖和控制依赖，传统的动态切片比较看重控制依赖，跟踪可执行语句集，辅助程序员调试，而起源计算跟踪与特定输出值相关联的输入集看重数据依赖。

定义4.9，动态切片技术：给定一个程序执行，执行点s_i的动态切片(表示语句s的第i条可执行实例)，是直接或间接受s_i执行影响的语句集合。

为识别相关语句集合，动态切片在语句执行之间捕捉经验依赖关系，依赖关系可分为两类：数据依赖和控制依赖。

定义4.10，数据依赖：语句执行实例s_i数据依赖于另一个语句执行实例t_j，当前仅当在t_j中定义的变量后来在s_i中被引用。

定义4.11，控制依赖：语句执行实例s_i控制依赖于t_j，当且仅当语句s_i是执行语句t_j分支时输出的结果。

采用动态切片技术起源计算输入项集合，这些输入项用于计算在特定执行点处的特定值。给定程序执行，执行点s_i处的值v的数据起源记为DL(v@s_i)，DL(v@s_i)是输入项集，这些输入项通过数据或控制依赖直接或间接参与到s_i处的值v的计算过程。使用DL(s_i)表示s_i左侧表达式的数据起源。

动态切片通常首先构建动态程序依赖图，其中描述了两个语句实例的数据/控制依赖关系，遍历此图寻找可到达的语句实例集。此方法的缺陷是构建依赖图的大小不容易估算。动态切片可以以一种迅速的(forward)方式计算，切片随着执行的进展连续产生并更新，而此方法减轻了空间问题，动态切片通常占用空间惊人，为更新切片，在执行的每一步不得不执行代价高昂的操作。由于本发明只是借用了程序调试的思想，目标是进行起源追踪，所以不必跟踪语句的执行，OUTPUT的起源集合仅包含INPUT[0]，然而，所有语句执行应该包含在OUTPUT的动态切片中，因为它们对OUTPUT的值都有着直接或间接的贡献。如果设计良好，起源追踪会比动态切片的效率更高。

10：x＝INPUT[0]；

20：x＝x+1；

30：OUTPUT＝x；

在程序执行期间数据起源如何计算。基本思想是与s_i的右侧变量相关输入元素集，是所有s_i数据或控制依赖的语句实例的相关输入集的并。换句话说，所有与某个s_i的操作符或者控制si执行的谓词相关的输入项，也与s_i相关。例如可执行语句s_i为：if t_j is true then d＝f(use₀，use₁，...，use_n)，用use₀，use₁，...，use_n为变量d赋值，则s_i控制依赖于t_j。

令DEF(x)为定义x的最后执行语句实例，use_x.t为数据use_x的固有时间戳，w_i为当前数据流合适的滑动窗口尺寸，数据起源的计算可用如下等式描述：

$\mathrm{DL}(\mathrm{dest}@s_i)=\left(\underset{\forall x}{Y}\mathrm{DL}\right({\mathrm{use}}_x@s_i)\cup \mathrm{DL}\left(t_j\right)$

$=\mathrm{DL}\left(\mathrm{tj}\right)\cup \left(\underset{\forall x.\mathrm{DEF}\left({\mathrm{use}}_x\right)\ne \phi }{Y}\mathrm{DL}({\mathrm{use}}_x@\mathrm{DEF}({\mathrm{use}}_x)\right)\cup$

$\left(\underset{\forall x.\mathrm{DEF}\left({\mathrm{use}}_x\right)\ne \phi }{Y}\right\{{\mathrm{use}}_x\left\}\right))\cup ({\mathrm{use}}_x.t\in [t-w_i,t\left]\right)$

由s_i定义的变量dest的起源集合，是t_j的起源集与由s_i定义的变量use_x的起源集的并。如果变量use_x预先定义了，DL(use_x@s_i)＝DL(use_x@DEF(use_x))，否则use_x被视为输入，DL(use_x@s_i)＝{use_x}。经分析对于起源追踪，数据依赖比控制依赖更关键。依据上述等式可以设计动态切片的递归过程SlicingTraceLineage(dest，s)计算起源追踪。

在前述理论及算法的基础上，传感器SLT主算法描述如下：

Algorithm传感器StreamsLineageTracing

Input：LineageQuery，Assistant Information//连续起源追踪查询、模式、加工辅助信息

Output：Lineage Information//指定数据项(集)起源信息

1 Do While not eof传感器Streams//当传感器数据流未停止

2  ComputingWindowSize(p^avg，δ)；//调整合适的滑动窗口大小

3  If the forward query schema is aware Then//已知正向查询模式信息

4    If operation is composed of relational operation Then//加工由关系操作组成吗？

5      StreamLineageTracing(T；v；ψ；p^avg；δ)；//调用标准逆ASPJ查询过程

6    Else//调用非关系逆查询过程

7      If operation is many-to-one relationship Then

8          TraceDecompose(λ，O*，I)；//调用分解反向跟踪过程

9      Else

10         TraceAggregator(λ，o，I′)//调用合并反向跟踪过程

11     EndIf

12  EndIf

13  SlicingTraceLineage(dest，s)//对加工程序动态切片，调用黑盒切片过程

14EndDo

下面结合实施例对本发明作进一步详细描述。

结合图1，实验环境以超高频(2.45GHz)有源标签及与之配套的阅读器、网格定位设备为主组成，epoch为2秒。其中网格定位设备分为5米、10米、25米等几个定位等级，实验室搭建了由20个网格定位器、5个阅读器、50张有源标签构成的实验环境。三角定位用的阅读器拟选购目前业内领先的UbiSense的高精度定位平台，其定位精度可达到30厘米，单位时间可发送的数据量更大，从而满足冰山查询性能测试的需求。数据服务器配置为2.0G duo core/1.0G/160M，传感器数据通过串口采集。

实施例一：考虑生产车间全程质量跟踪应用场景，在传送带上每道工序完成位置的附近，安装一系列带有检测传感器的传感器读写器，对经过的产品进行跟踪，系统得到监控流和操作流并进行了一系列的操作，最后借助传感器数据上的连续查询技术得到一个导出流(即审核流)。操作序列如图4所示。

监控数据流包含四个属性：阅读器号，位置号，时间戳，同时检测到的产品列表(由产品号与检测概率组成)，即Monitor(ReaderId，LocationId，MTimeStamp，Productid-list)，某时刻Monitor流的实际内容如表1所示。

表1传感器监控数据流Monitor实例

  ReaderId  LocationId  MTimeStamp  Productid-list(Tagid，probalility)  R1  L1  2008-6-11 11:51:12  (087，0.9)(098，0.2)(120，0.7)  R2  L1  2008-6-11 11:56:10  (089，0.9)(125，0.8)(087，0.9)  R3  L3  2008-6-11 12:01:00  (087，0.8)(120，0.8)

Product表包含六个属性：标签号、产品名称、类别、价格、重量、种类，即Product(Tagid，ProductName，Category，Price，Weight，Unit)如表2所示。

表2产品表Product实例

  Tagid  ProductName  Category  Price  Weight  Unit

  087  HP 6320  Computer  7000  2.8  Box  089  Rice  Food  100  50  Bag  120  IBM T63  Computer  13000  2  Box

操作序列中，λ₁对Monitor流的内容进行分割，让每个标签独占一行，符合关系数据库1NF，新增两列Tagid，Probalility；λ₂对Product表进行过滤，得到类别是“computer”的产品；λ₃连接Monitor流与Product表，保留LocationId，Tagid，ProductName，Probalility属性列，同时必须满足时间限制；λ₄对连接的结果按TigId属性进行分组汇总，计算每天检测到每种产品的平均概率，输出<TigId，ProductName，AverageProbalility>；λ₅选择平均概率大于0.85的产品名称。根据前面对操作的定义，λ₁、λ₂、λ₅属于一对多操作，λ₄、λ₅属于多对一操作。其中除λ₁以外，其它几个操作都可以由标准关系操作实现。

(1)对属于合并操作的单层视图进行起源追踪：λ₄依据TagId分组对Probalility进行平均聚集计算，产生5个输出元组，包含对平均识别概率的分组值。根据表1，简单以<TagId，AverageProbalility>表示元组，λ₄的输入I＝{<‘087’，0.8>，<‘087’，0.9>，<‘087’，0.9>，<‘089’，0.9>，<‘098’，0.2>，<‘120’，0.7>，<‘120’，0.8>，<‘125’，0.8>}，输出O＝λ₄(I)＝{<‘087’，0.867>，<‘089’，0.9>，<‘098’，0.2>，<‘120’，0.75>，<‘125’，0.8>}，λ₄的逆λ₄^-1对输入数据项的第二个属性进行分解产生多个项，即${\lambda }_4^{-1}\left(O\right))=I.$λ₄是合并操作，根据定理4.4，使用λ₄^-1执行数据项的起源追踪，例如给定输出项o＝{<‘120’，0.75>}，o的起源为

(2)对属于分解操作进行起源追踪：操作λ₁属于分解操作，对于输出o＝{<‘L1’，‘087’，‘HP 6320’，0.8>}采用过程TraceDecompose()，得到o对λ₁的起源为{<‘R1’，‘L1’，‘2008-6-11 11:51:12’，‘(087，0.9)(098，0.2)(120，0.7)’，<‘R2’，‘L1’，‘2008-6-11 11:56:10’，‘(089，0.9)(125，0.8)(087，0.9)’>}，而用其逆操作λ₁^-1得到的起源只是正确起源的子集。

(3)对多层视图进行起源追踪：设操作λ₅的一个输出为o＝{<‘087’，‘HP6320’>}，计算o对在起源Monitor数据流中的起源，即需要对多层数据流视图进行起源跟踪。因为λ₅消减了部分聚集后元组，所有在λ₄之后引入中间流暂存全部计算机类的聚集元组。采用(C)多级ASPJ视图起源追踪算法，分段计算上一层的起源，最终得到与(2)相同的结果，如图5所示。

为测试上面描述的所有算法，我们通过实验验证各种算法的性能。实验数据来自于实际测试环境，输入数据流为Monitor，输入表为Product。设由如下类SQL方式定义起源追踪查询，执行实验一：

SELECT*FROM AllComputer where；

SELECT Monitor.TagID，Product.ProductName

FROM Monitor，Product

WHERE lineage(Monitor，Product)AND Operation(P₁，P₂，P₃，P₄，P₅)

WINDOW Now-0

其中P₁...P₅代表五个操作，WINDOW子句中的0表示根据阅读率自适应调整窗口尺寸。这个查询需要追踪经历了五个操作的结果元组的起源，五个操作既有一对多类型的，又有多对一类型的，其中多对一类型又属于键值保留型。实验设计了三个计算此起源查询的方案，(1)由于后四个操作属于标准关系操作可以采用TupleLineageTracing过程快速计算P₂...P₅的起源，而P₁操作属于非标准操作，所以以TupleLineageTracing过程得到起源集作为输入，继续调用TraceDecompose过程计算最终起源集；(2)对操作P₂...P₅采用非关系TraceAggregator过程计算，给定转换图，一次跟踪一个操作，对操作P₁采用TraceDecompose过程跟踪其数据起源；(3)设视五个操作P₁...P₅为黑盒操作，直接调用SlicingTraceLineage过程。

反复实验10次，记录滑动窗口尺寸从50到300个元组变化，度量三种方案对单个元组的起源追踪时间，结果如图6所示，过程方案(1)的速度比其它两个方案运行的速度快许多，得知若已知操作信息，且操作完全由标准关系操作ASPJ组成，随着滑动窗口输入尺寸的增加，多层标准ASPJ视图的逆查询显著的降低了跟踪时间。而方案(3)适用于更加复杂操作的起源追踪。

实施例2：验证动态滑动窗口与静态固定滑动窗口的起源追踪相比可得到什么样的性能提升。我们选取现有的Cui逆查询方法[Y.W.Cui，J.Widom，J.L.Wiener.Tracing the Lineage of View Data in a Warehousing Environment.ACMTransactions on Database Systems，2000，25(2)：179-227]和Zhang切片追踪方法[M.Zhang，X.Zhang，X.Zhang，and S.Prabhakar.Tracing lineage beyond relationaloperators.Technical report，Purdue University，2007]和本专利所述方法进行比较。实验数据来自于TPC-D标准测试集。输入表为LineItem，Order，PartSupp，表的内容由标准dbgen程序生成，TPC-D缩放因子1.0代表整个数据仓库的大小为1GB。

实验二比较了这几种方法所获得指定元组起源的代价性能，图7是固定滑动窗口大小调用Cui方法和Zhang方法与自适应调整滑动窗口尺寸的本文提出方法的计算精度对比关系。由于这两种方法是针对静态数据集的，所以采用批量更新数据子集的方法与本文比较。反复实验了10次，每次为Cui方法和Zhang方法改变不同的输入数据项个数(相当于固定窗口大小)，计算精度定义为算法得出的起源元组数目与真实元组数目的比例。图7表明，和Cui方法与Zhang方法相比，本方法所获得的流失传感器数据起源的精度最高。这是因为，由于数据流的易失性，与传感器阅读器固有的读误差，起源元组的在原始数据流中的特征与在静态数据集中不同，人为指定的数据集没有考虑起源流动的问题，导致Cui方法与Zhang方法识别精度的降低。

类似上述实验方法，我们还模拟验证了三种计算传感器数据起源方法的时延、在不同类型的操作情况下的计算精度、内存耗用情况、吞吐率、以及稳定性等性能，所有实验表明，本方法在时延、适应传感器数据的不确定性以及起源追踪成功率等方面都表现出了良好的性能，并且本方法具有较快的计算速度，满足实时起源追踪的要求。