不確定數據PT-TopK查詢近似處理系統和方法
2023-05-05 00:49:01 1
不確定數據PT-TopK查詢近似處理系統和方法
【專利摘要】本發明公開一種面向水環境監測網絡的不確定數據PT-TopK查詢近似處理系統和方法，通過建立x-tuple規則元組的不確定元組模型，採用簇內和簇間兩個階段數據減枝與查詢處理方法，在不影響最終查詢結果的準確度情況下，減少數據通信開銷，解決面向水環境監測網絡系統的不確定數據查詢處理問題；減少數據傳輸量與網絡能耗，提高數據查詢結果的可信度，降低水環境監測網絡系統中數據管理的開發與部署成本。
【專利說明】不確定數據PT-TopK查詢近似處理系統和方法
【技術領域】
[0001]本發明涉及一種面向水環境監測網絡的不確定數據PT-TopK查詢近似處理系統和方法，屬於水環境監測網絡技術應用領域，主要應用於水環境監測網絡系統，通過建立x-tuple規則元組的不確定元組模型，採用簇內和簇間兩個階段數據減枝與查詢處理方法，在不影響最終查詢結果的準確度情況下，減少數據通信開銷，解決面向水環境監測網絡系統的不確定數據查詢處理問題。
【背景技術】
[0002]水環境監測是對地表水、地下水、大氣降水、水體沉降物、生物、水汙染等進行測量和分析評估，主要分為水量和水質監測兩大類，包括了水位、流量、水溫、降水、冰情、蒸發、汙染源和汙染物等監測內容。當前，水環境監測已發展成為自然水災害預測預報、汙染控制和治理，以及水環境規劃管理的重要技術支撐。近年來，我國已投入大量資金建立了各種監測點、監測站和監測網絡等基礎設施，形成了以測站一遙測通信網絡一中心站為主體的水環境監測體系。但是，仍然存在較難獲取自然條件惡劣和人員較難到達區域的水環境信息，以及無法對緊急或突發的水環境事件進行快速和動態監測的問題。目前，無線傳感器網絡技術已成為信息獲取技術的重要發展方向，並正在引起各研究和應用領域的廣泛關注，將無線傳感器網絡技術引入到水環境監測系統中，是解決前述問題的重要技術途徑。
[0003]在面向水環境監測網絡系統中，傳感器節點感知的數據普遍存在不確定性，主要原因有:(I)傳感器節點的監測精度不高，感知數據本身就不精確；(2)傳感器節點的能量是由電池提供的，由於電池能量的消耗，傳感器經常會失效或廢棄，因此會產生數據的缺失或不正確的信息。(3)在面向水環境監測網絡系統中，節點在感知數據時，受到風、雨、雷、霧等自然環境的影響，從而導致感知數據的不精確。(4)在網絡傳輸過程中，受到外界信號幹擾，也會導致數據不確定性。傳感數據的不確定性給水環境監測應用帶來巨大阻礙，使得信息不可信，用戶不能直接從中獲取有用信息。所以，在面向水環境監測網絡系統中，對不確定性數據的查詢處理也變得越來越重要。
[0004]目前，對不確定性數據的研究主要集中在兩類不確定性數據上，即屬性值不精確性和元組不存在性。屬性值不精確性是指若干元組及其模型已經被確定，單個屬性的不確定性是通過一個概率密度函數，或者其他統計參數來確定的。元組不存在性是指資料庫中的一個元組存在的概率，通常採用可能世界語義處理，使用生成規則，各元組的任一合法組合均構成一個可能世界實例(Possible Instance)。每個可能世界實例出現的概率值可以通過各個相關元組的取值概率計算得到。可能世界實例的數量是不確定性數據表中元組數量的指數倍，這是不確定性數據管理所面臨的最大難點。本發明解決在面向水環境監測網絡系統中，元組不存在性數據一類的不確定性數據處理。
[0005]在面向水環境監測網絡應用中，不確定數據Top-k查詢即是查詢監測範圍內的傳感器節點採集到的數據中k個最大值或最小值。在確定性應用中，Top-k排序是根據一些排序函數確定的。然而，在不確定應用中，不確定數據表中元組存在概率的因素使得Top-k查詢的估計變得非常複雜。不確定數據Top-k查詢的結果集，不僅僅依賴於其屬性值的大小，更對數據元組的存在性有著一定的要求。需要考慮兩個排序指標:一個是元組屬性值的排序；另一個是元組存在概率。因此，對不確定數據Top-k查詢處理需要充分考慮元組屬性值的排序和元組存在概率對Top-k查詢結果的影響。
[0006]目前,不確定數據Top-k查詢分為U-Topk、U-kRanks、PT-Topk和Pk-Topk查詢四類。U-Topk查詢和U-kRanks查詢對查詢結果的排列順序有著嚴格要求，Pk-Topk查詢對元組的Top-k概率順序也有著一定的要求。而PT-Topk查詢對結果順序沒有特定要求，但是對結果的可信度有一定的質量要求，對用戶而言，只有PT-Topk查詢才滿足對不確定數據Top-k查詢結果數據質量的要求。PT-Topk查詢要求其查詢元組在所有可能世界中成為Top-k的總概率大於p，排序在前k位的數據。因此，本發明解決在面向水環境監測網絡系統中，不確定數據PT-Topk查詢處理問題。
[0007]處理不確定數據PT-Topk查詢最直接的方法，即Nake算法，對所有可能世界，按照排序和概率關係求出查詢結果。然而，由於可能世界數量級非常大，因此Nawe算法是一個低效率算法。Soliman等人提出基於Poisson分布的PT-Topk查詢近似算法,此算法避免對所有可能世界數據進行查詢，可以高效獲得不確定元組Top-k概率，但是，此種算法只適合於集中式資料庫。在水環境監測傳感網絡中，由於網絡能量有限，將數據全部收集集中式處理方法必將消耗大量的網絡能量，縮短網絡生命周期。因此，基於Poisson分布的PT-Topk查詢近似算法不能直接應用到水環境監測傳感網絡的分布式資料庫中。
【發明內容】
[0008]發明目的:關於現有技術中存在的問題，本發明針對層次型水環境監測傳感網絡，提供一種面向水環境監測網絡的不確定數據PT-TopK查詢近似處理系統和方法，用於解決當前水環境監測網絡應用中，傳感 數據的不確定造成數據查詢結果不可用、傳輸數據量大、網絡能耗高的問題。將構建層次式的水環境監測網絡，採用簇內和簇間兩個階段數據查詢處理的分布式不確定數據PT-Topk查詢處理算法，實現高效的不確定數據PT-Topk查詢處理。
[0009]定義I不確定元組數據表T中有η條數據元組，元組\ (I < i < η)的值域為o=\M\m? [μ]是一個正實數域，取值概率為Pi，0表示為空，即不存在，不存在概率為
1-Pi0則稱此類數據元組為不確定元組。
[0010]定義2x-tuple規則元組不確定數據表T中有η個不確定元組，W表示T中所有不確定元組可構成的可能世界集合，w是一個可能世界實例，對於Vwer，V0 er,(I < i, j < η),如果存在h e w,而G ，則稱元組h和tj具有相同x-tuple關係,此類元組稱之為x-tuple規則元組，並使用τ表示。τ的存在概率為戶匕= 巧，不存在
的概率為作=0)=1-1,,^.。
[0011]本發明所定義的x-tuple規則元組皆來自相同數據源節點。傳感器節點每次感知數據時，可確定若干數據項，每個數據項都帶有確定概率，且所有數據項概率和小於等於I。每個數據項及其概率對應一個元組。相同節點同時產生的多個元組即為x-tuple規則元組。
[0012]定義3等級順序設不確定數據表T有由若干元組組成，即T = {t1； t2，. . .，tn}。若 T中所有元組的其在等級排序函數f上滿足fh)≥f(t2)≥…≥f(ti)≥≥f(t n)，則稱不確定數據表T是等級有序的，記為< ft2. . . < ftj < ftj. . . < ftn。
[0013]本發明方法採用降序順序排序，若存在f (tj = f (tp，則元組概率大者排名順序 更前。
[0014]定義4支配集給定元組t G T，T是不確定數據表，t』 G w，w是T上的一個可能世 界，t』能否成為可能世界w上的Top-k，取決於w中排序在t』之前的元組數量是否小於k。 因此，元組t的支配集可以表示為：
[0015]DSt = {t|t G T 八 t < ft' }(1)
[0016]定義5修剪上界存在一個有序不確定數據表T，T中有n個元組，hGT (l^i^n), ^為\支配集的概率和，給定數據查詢參數k和概率閾值p，當滿足Up k 和P滿足公式（2)時，\為不確定數據集T上的修剪上界（Pruning Upper Bound, PUB)。
[0017]
【權利要求】
1.一種不確定數據PT-TopK查詢近似處理系統，其特徵在於，包括監測節點端部分和用戶終端部分；用戶終端部分包括用戶交互接口、網絡初始化模塊、查詢任務啟動模塊和查詢結果返回接口 ；監測節點端部分包括簇內查詢處理模塊、簇間查詢處理模塊和基站節點查詢處理模塊； (1)監測節點端部分簇內查詢處理模塊:簇內成員節點接收從查詢啟動模塊傳輸的查詢任務，根據查詢參數概率閾值P和排序數k，在其不確定數據表上執行PT-Topk查詢；採用與其簇頭節點兩次數據交換策略，簇成員節點將本地不確定數據表上可能成為最終查詢結果的數據傳輸給簇頭節點，實現簇內數據修剪；簇間查詢處理模塊:由於不確定元組的存在概率大於等於不確定元組Top-k概率，對於排序比較低的不確定元組，即使其存在概率很大，最後得出的Top-k概率也可能會非常低，甚至不滿足概率閾值P的要求；因此，簇頭節點接收到所有簇內成員節點傳輸的數據，根據查詢參數概率閾值P和排序數k，簇頭節點與Sink基站節點通過行兩次數據交換，確定其可能成為最終查詢結果的數據傳輸給Sink基站節點，實現簇間減枝；基站節點查詢處理|旲塊:基站節點對數據表Tsink中的所有兀組按等級順序定義的降序順序排序，根據查詢任務的概率閾值P和排序數k，在不確定數據表Tsink上執行PT-Topk查詢，並將查詢結果數據進行封裝，返回給查詢結果返回接口。(2)用戶終端部分用戶交互接口:以圖形化界面的方式，接收用戶的查詢任務和查詢參數，並向查詢任務和參數轉發至查詢任務啟動模塊；網絡初始化模塊:利用TEEN網絡分簇算法構建層次式聚簇網絡拓撲結構，將整個網絡分成若干個簇，每個簇只有一個簇頭節點，並負責與基站節點進行通信，簇頭節點保存本簇內所有節點的信息；簇內節點之間可以相互通信，收集感知器感知的數據，保存在本地存儲器中；查詢任務啟動模塊:根據水環境監測任務需求，用戶發起查詢請求，解析查詢任務參數，確定查詢任務的發布方式，並對查詢數據進行封裝；查詢結果返回接口:接收查詢結果數據包，並根據封裝格式，進行解包，得到查詢結果以圖形化的方式展示給用戶。
2.一種不確定數據PT-TopK查詢近似處理方法，其特徵在於，包括以下步驟:1)建立水環境監測網絡的拓撲結構:水環境監測網絡採用層次式聚簇網絡拓撲結構，利用TEEN網絡分簇算法，將整個網絡分成若干個簇，每個簇只有一個簇頭節點，並負責與基站節點進行通信，簇頭節點保存本簇內所有節點的信息；簇內節點之間可以相互通信，收集感知器感知的數據，保存在本地存儲器中；2)每個簇內節點建立x-tuple規則元組的不確定元組模型:X-tUple規則元組由若干不確定元組構成，每個元組中都存在一個數據項，數據項是節點感知數據，並且每個數據項都有一個存在概率；x-tuple規則元組中所有數據項存在概率之和小於等於I ;3)簇內節點查詢處理:簇內節點接收到查詢請求,根據概率閾值P和排序數k在其不確定數據表上執行PT-Topk查詢，當滿足查詢算法終止執行條件時，將最後查詢到的不確定元組傳輸給簇首節點；簇首節點將收集到的所有不確定元組排序，找出排序最高的不確定元組作為硬閾值，並傳輸給簇內節點；簇內節點收到硬閾值，並將本地不確定數據表上大於此硬閾值的所有不確定元組傳輸給簇首節點；4)簇間節點查詢處理:簇首節點將收集到的所有不確定元組按降序排序，執行PT-Topk查詢處理算法，計算出查詢結果；將查詢結果分為兩類:受到影響查詢結果和不受影響查詢結果；查詢結果排序最低元組的感知數據項作為查詢結果下界，相應的可將查詢結果下界分為受到影響查詢結果下界和不受影響查詢結果下界；在基站，分別計算所有受到影響查詢結果下界的最小值和不受影響查詢結果下界的最大值；然後比較此最小值和最大值，並將其中較大者記為全局下界，並廣播全局下界給簇首節點，簇首節點將全局下界作為硬閾值，將感知數據項大於此硬閾值的不確定元組傳輸基站；5)基站節點查詢處理:基站將收集的不確定元組按降序排序，並執行PT-Topk查詢近似算法，得到最終查詢結果。採用數據包對查詢結果數據進行封裝，通過基站節點返回到用戶終端。
3.根據權利要求2所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟2)建立x-tuple規則元組 的不確定元組模型可定義為:x-tuple規則元組不確定數據表T中有η個不確定元組，W表示T中所有不確定元組可構成的可能世界集合，w是一個可能世界實例，對於VwgF，Vti eT，^tj ，(I≤i, j≤η),如果存在h e w,而G ，則稱元組h和tj具有相同x-tuple關係,此類元組稱之為x-tuple規則元組，並使用τ表示；τ的存在概率為屍O"式0) = Σρ巧，不存在的概率為Ρ0- 二=;x-tuple規則元組皆來自相同數據源節點；傳感器節點每次感知數據時，可確定若干數據項，每個數據項都帶有確定概率，且所有數據項概率和小於等於I ;每個數據項及其概率對應一個元組；相同節點同時產生的多個元組即為x-tuple規則元組。
4.根據權利要求2所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟3)進一步包含以下步驟:3.1)根據查詢任務的查詢結果可信度閾值P和排序數k，簇內成員節點對本地存儲的不確定數據表Tntxte的元組按等級順序定義，按降序順序排序；3.2)根據修剪上界定義，簇內節點計算本節點存儲的不確定數據表Tmde的局部修剪上界Lpub，並將結果Lpub傳送給其旗頭節點；3.3)簇頭節點接收到所有其簇內成員的不確定數據表Tntxie的局部修剪上界Lpub，選取排序第一的Lpiffi作為簇內全局修剪上界Gpiffi,即Gpub = MAX(Lpiffi)；3.4)簇頭節點將全局修剪上界Gpub發送給其簇內成員節點；3.5)簇內節點接收到修剪上界Gpub後，將其不確定數據表Τη(Λ中排序在Gpub之前的元組發送給其簇頭節點；3.6)簇頭節點接收到其簇內成員節點傳送的數據後，存儲在自身簇頭節點的不確定數據表Tduster中。
5.根據權利要求4所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟3.1)進一步包含等級順序定義:等級順序設不確定數據表T有由若干元組組成，即T = It1, t2,..., tn};若T中所有元組的其在等級排序函數f上滿足f (ti)≥f (t2)≥... f (ti)≥f (tj)...^f (tn)，則稱不確定數據表T是等級有序的，記為h < ft2...< ftj < ftj...< ftn ；採用降序順序排序，若存在f(ti) = f(t J，則元組概率大者排名順序更前。
6.根據權利要求4所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟3.2)進一步包含支配集和修剪上界定義:支配集給定元組t e T，T是不確定數據表，t』 e w，w是T上的一個可能世界，t』能否成為可能世界W上的Top-k,取決於W中排序在t』之前的元組數量是否小於k ;因此,元組t的支配集可以表示為:DSt = {t|teTAt<ft/ }；修剪上界存在一個有序不確定數據表T，T中有η個元組，^ e T (I ^ i ^ η),μ i為ti支配集的概率和，給定數據查詢參數k和概率閾值P,當滿足μ 1、k和P滿足
7.根據權利要求6所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟4)進一步包含以下步驟:4.1)根據充足集下界和必須集下界定義，簇頭節點在其不確定數據集Telustw上，計算Tcluster的必須集下界NLB和充足集下界SLB，並將計算結果發送給基站節點；4.2)基站節點接收到所有簇頭節點發送的必須集下界NLB和充足集下界SLB，確定最小的必須集下界Min(NLB)和最大的充足集下界Max(SLB)，並且基站節點將選擇兩者之間的較大者，即Max {Min (NLB)，Max (SLB)}作為全局下界GB ；4.3)基站節點將全局下界GB發送給所有簇頭節點；4.4)簇頭節點接收到GB值後，將其不確定數據集Tduste上排序高於GB的不確定數據元組傳送給基站節點；4.5)基站節點接收到所有簇頭節點發送的數據元組後，保存在基站的不確定數據表Tsink 中。
8.根據權利要求7所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟4.1)進一步包含充足集下界和必須集下界定義:充足集下界給定不確定數據表T，A是T上完全集CS(T)，A中有η個元組，\ e A，Vi, eA , Ii, jη,且tj關\ ;如果Ptqp1^A) > k-ρ成立,且存在t」< A,則稱元組為不確定數據表T上的充足集下界(Sufficient Set Lower Bound,簡稱SLB),可以表示為:ss(t) = {tit = ftslb u t k-p不成立,且存在t」< Ji,則稱元組為不確定數據表T上的必須集下界，可以表示為:NS ⑴={t 11 = ftnlb U t < ftnlb}。
9.根據權利要求8所述的不確定數據PT-TopK查詢近似處理方法，其特徵在於，所述步驟5)進一步包含以下步驟：.5. 1)基站節點對數據表Tsink中的所有元組按降序順序排序；.5. 2)基站節點根據查詢任務的概率閾值p和排序數k，在不確定數據表Tsink上執行 PT-Topk查詢，並將查詢結果返回給用戶終端；.5. 3)採用數據包對查詢結果數據進行封裝，通過基站節點返回到用戶終端。
【文檔編號】G06F17/30GK103593435SQ201310561183
【公開日】2014年2月19日 申請日期:2013年11月12日 優先權日:2013年11月12日
【發明者】毛鶯池, 王康, 王久龍, 朱瀝瀝, 接青 申請人:河海大學