[發明專利]一種低存儲開銷的運行時遞推數據溯源方法

無效

• 申請號: 201310034449.5
• 申請日: 2013-01-30
• 公開（公告）號: CN103177184A
• 公開（公告）日: 2013-06-26
• 發明（設計）人: 李千目;謝新;戚湧;於東軍;侯君;朱長林
• 申請（專利權）人: 南京理工大學常熟研究院有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于數據溯源領域，特別是一種低存儲開銷的運行時遞推數據溯源方法。?

背景技術

近年來，基于傳感網的感知應用大量出現，并被廣泛地應用于工業控制、醫療護理、軍事監測、智能農業和危險源監測等領域。然而隨著傳感網技術的發展，傳感網的規模正變得越來越大。在傳感網數據的整個感、傳、知、控的演化過程中，每個階段的數據處理都具有一定的不確定性，隨著數據的傳播，各環節的不確定性不斷傳遞、放大，最終可能極大地影響感知結果的質量。?

數據起源記錄數據的出處及隨后所有的演化過程。數據溯源，又稱數據起源追蹤，是根據記錄的數據起源信息，查詢數據的源頭及產生過程的技術。數據溯源技術的出現使得傳感網感知應用能夠更好地進行質量跟蹤、故障診斷、可信異常原因分析、數據融合的起源追溯等不確定性分析。然而傳統的數據溯源方法漸漸無法應對大規模傳感網中的海量數據與低延遲的處理要求。?

發明內容

本發明的目的在于提供一種低存儲開銷的運行時遞推數據溯源方法，從而能以較低的存儲開銷完成數據的溯源工作。?

實現本發明目的的技術解決方案為：一種低存儲開銷的運行時遞推數據溯源方法，步驟如下：?

第一步，在數據處理系統部署時，記錄其粗粒度起源信息。粗粒度起源信息是指在數據處理系統運行過程中，不會反生變化的起源信息。

第二步，在數據處理系統運行過程中，記錄其細粒度起源信息。細粒度起源信息是指在數據處理系統運行過程中，會不停變化的起源信息。?

第三步，在數據處理系統中最后一個處理單元產生輸出數據元組時，對該輸出數據元組的起源信息進行遞推。遞推得到數據處理系統中第一個處理單元的觸發運行的時間范圍，并將該時間范圍與輸出數據元組一起進行持久存儲。?

第四步，溯源查詢時，根據存儲在輸出數據元組中的第一個處理單元的觸發運行的時間范圍，推算出數據處理系統輸入數據流中所有對待溯源輸出數據元組的產生有貢獻的輸入數據元組，即完成了數據溯源的過程。?

本發明與現有技術相比，其顯著優點：由于不需要對每個處理單元的起源信息進行存儲，因此本發明擁有更低的存儲開銷。?

下面結合附圖對本發明作進一步詳細描述。?

附圖說明

圖1是低存儲開銷的運行時遞推數據溯源方法的方法示意圖。?

具體實施方式

實施例：?

結合圖1，低存儲開銷的運行時遞推數據溯源方法的步驟如下：

第一步，在數據處理系統部署時，記錄其粗粒度起源信息。

需記錄的粗粒度起源信息主要包括：?

a）每個處理單元的計算窗口類型（基于元組數量計算或基于時間長度計算）；

b）每個處理單元的計算窗口大小（若基于元組數量計算，則窗口大小為元組數量；若基于時間長度計算，則窗口大小為時間長度）。

第二步，在數據處理系統運行過程中，記錄其細粒度起源信息。?

細粒度起源信息有一部分需要持久記錄，另一部分則只需進行臨時存儲即可。?

a）需要持久記錄的細粒度起源信息包括：?

系統輸入數據流中所有輸入數據元組的值及其進入數據處理系統的時間；

系統輸出數據流中所有輸出數據元組的值及其產生時間。

b）需要臨時存儲的細粒度起源信息包括：?

每個處理單元每次運行的觸發時間；

每個處理單元每次運行的處理延遲。

第三步，在數據處理系統中最后一個處理單元?產生輸出數據元組（，?）時，對該輸出數據元組的起源信息進行遞推。遞推公式如下：?

其中

在上述公式中，為處理單元的第一個輸出數據元組的產生時間，為該輸出數據元組產生時的處理延遲。為處理單元的最后一個輸出數據元組的產生時間，為該輸出數據元組產生時的處理延遲。為的計算窗口的時間長度，?為的計算窗口中元組的數量。表示的輸入數據流中進入處理單元的時間小于的個輸入數據元組的進入處理單元時間的集合。表示的輸入數據流中進入處理單元的時間介于和之間的輸入數據元組的進入處理單元時間的集合。

?[0019]?利用上述遞推公式，從的輸出元組產生時間的范圍依次遞推，最后得到的輸出元組產生時間的范圍?。根據的輸出元組產生時間范圍，得到的觸發運行的時間范圍，其中，將與輸出數據元組一起進行持久存儲。