一種無線傳感網絡的可分解聚合查詢處理方法
2023-06-23 07:01:26
專利名稱：一種無線傳感網絡的可分解聚合查詢處理方法
技術領域：
本發明屬於計算機數據管理技術領域，具體涉及一種無線傳感網絡的可分解聚合查詢處理方法。
背景技術：
無線傳感網絡具有廣闊的應用前景，除將採集到的所有原始數據周期性送回基站之外，響應用戶的各種複雜數據查詢也是無線傳感網絡的重要功能。在收集數據和響應查詢的過程中，數據融合技術發揮了非常重要的作用，融合多節點數據所得出的結果能夠克服單點感知數據易受噪聲影響的缺點，有效控制誤差，同時數據融合技術能夠顯著降低通訊開銷，提高系統性能。將無線傳感網絡看作是一個資料庫，聚合查詢例如SUM (求和)、COUNT (計數)、AVG (均值)、MEDIAN (中位數)、MIN (最小值)和MAX (最大值)等是獲取統計結果的重要查詢，聚合查詢能夠克服單個感知數據的噪聲影響，提高準確性並給出全局性的結果。如何高效處理無線傳感網絡中的各種聚合查詢為數據融合技術提出來新的挑戰。無線傳感網絡的計算以及帶寬資源都極度有限，鏈路不穩定數據丟失頻繁，因此需要設計新的機制能夠在動態環境下克服數據丟失帶來的影響，同時在保證數據查詢結果準確率的前提下減少通信的開銷。聚合查詢包括很多具體類型，它們大致可以歸為兩類，可分解查詢(或者叫做非全局查詢)和不可分解查詢(或全局查詢)。可分解查詢，包括SUM、COUNT、MIN、MAX和AVG等，都具有可分解的特性。假設數據集記為S，則對於任意查詢Q，如果Q是可分解的，則存在一個函數f，使得對於所有的S=S1 U S2, Q(S) =f (Q(S1)1Q(S2))0如果不存在這樣的函數f,則查詢Q是不可分解的(全局的)。不可分解查詢包括分位數查詢(例如MEDIAN)，柱狀圖查詢等。本發明公開的技術主要針對可分解查詢，查詢的最終結果能夠從部分結果直接組合計算得出，比如求和查詢中只需把各個部分的數據求和即可獲得最終的結果。這種計算特性使得可分解查詢能夠分布式計算並且很方便的進行網內聚合操作，但是高效準確的獲得查詢結果需要應對無線鏈路帶來的數據包丟失問題和儘量減少傳輸開銷。TAG技術中提出網內聚合方法，即中間節點將自己採集到的數據和所有子節點收到的數據進行融合，然後融合後的結果僅適用一個數據包內發送至其父節點，和傳統方法相比，TAG大大減少了數據的發送數量。但是這種方法在數據包丟失的時候精度下降嚴重，例如一個數據包的丟失意味著以發送者為根的整個子樹上的數據全部丟失。Silberstein等研究人員提出的技術充分利用了網絡拓撲來解決最大最小值查詢問題，在保證查詢結果精度的前提下最小化通信開銷。為了克服數據包丟失帶來的影響，一個很有效的辦法是讓同一數據沿多條路由返回基站，這樣極大提高了到達概率，但這種情況下的網內聚合存在重複數據的問題，尤其對於求和、平均值等重複敏感的查詢。感知數據的不確定性和噪聲幹擾等問題，嚴重影響可分解查詢的準確性。移動均值是一種廣泛採用的統計方法，被用來消除不確定性和噪聲的影響。特別的，當我們發現一些可疑的感知數據的時候(例如查詢結果超過報警閾值)，在採取其它措施之前，我們可以提高採樣頻率持續進行查詢，並計算接下來一批查詢結果的均值，來確認當前的感知數據是否真的超過了閾值。但是移動均值仍然不能保證數據的準確性，因為無線傳感網絡數據傳輸可靠性低，丟包嚴重。同時，由於無線傳感網絡的節點能量限制，傳統查詢處理技術消耗大量能量。
發明內容
本發明旨在至少在一定程度上解決上述技術問題之一或至少提供一種有用的商業選擇。為此，本發明的一個目的在於提出一種開銷合理、準確性高的優點的無線傳感網絡的可分解聚合查詢處理方法。根據本發明實施例的無線傳感網絡的可分解聚合查詢處理方法，包括以下步驟S1.將多個無線傳感器的節點構建成樹狀拓撲結構；S2.用戶發出連續聚合查詢，所述連續聚合查詢通過所述樹狀拓撲結構被洪泛到所述傳感器網絡中；S3.採用多父節點方法並結合智能傳輸路徑選擇算法，計算每個所述節點的優選父節點，其中，計算得到的所述優選父節點的數目為多個；S4.數據通過所述樹形拓撲結構傳輸，所述節點在每一個周期採集一次對應的多個子節點的數據並聚合成單個結果，然後重新切分為部分值後發送給對應的多個優選父節點，通過多跳傳遞數據到達根節點連接的伺服器進行匯總查詢結果計算；以及
S5.傳輸過程中應用網內聚合直至根節點處，最終基站利用根節點接收到的所有數據計算最終的查詢結果。在本發明的一個實施例中，所述步驟S3進一步包括S31.計算所有可能父節點到子節點直接父節點的距離，根據所述距離將所述可能父節點投影到一條直線上；以及S32.子節點在生成樹上的直接父節點默認被選為第一個優選父節點，然後從子節點的其他可能父節點中均勻選出預定數量的優選父節點。在本發明的一個實施例中，還包括在所述節點內增加計數器，觀察並計算鏈路的接收率和丟失率，並利用所述接受率和丟失率對所述節點傳輸的數據進行概率補償。在本發明的一個實施例中，還包括在所述節點引入卡爾曼濾波器對觀察到的鏈路丟失率進行修正，以使得到真實鏈路丟失率的最優估計。本發明公開了一種無線傳感網絡的可分解聚合查詢處理方法，通過設計概率補償模型(PCM)和智能路徑選擇機制來解決鏈路丟包對查詢結果準確率的影響同時降低通訊開銷。本發明的優點在於第一，本發明提出的技術能夠持續獲得可分解聚合查詢結果。第二，本發明提出的技術通過概率補償能夠克服無線鏈路數據丟失帶來的負面影響，顯著提高查詢結果準確性。第三，本發明提出的智能路徑選擇技術顯著減少通訊開銷，並且提高結果的穩定性。本發明的附加方面和優點將在下面的描述中部分給出，部分將從下面的描述中變得明顯，或通過本發明的實踐了解到。
本發明的上述和/或附加的方面和優點從結合下面附圖對實施例的描述中將變得明顯和容易理解，其中圖1是本發明的無線傳感網絡的可分解聚合查詢處理方法的流程圖2是本發明的網絡拓撲構建示意圖；圖3是本發明的智能路徑選擇示意圖。
具體實施例方式下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的，旨在用於解釋本發明，而不能理解為對本發明的限制。在本發明的描述中，需要理解的是，術語「中心」、「縱向」、「橫向」、「長度」、「寬度」、「厚度」、「上」、「下」、「前」、「後」、「左」、「右」、「豎直」、「水平」、「頂」、「底」 「內」、「外」、「順時針」、「逆時針」等指示的方位或位置關係為基於附圖所示的方位或位置關係，僅是為了便於描述本發明和簡化描述，而不是指示或暗示所指的裝置或元件必須具有特定的方位、以特定的方位構造和操作，因此不能理解為對本發明的限制。此外，術語「第一」、「第二」僅用於描述目的，而不能理解為指示或暗示相對重要性或者隱含指明所指示的技術特徵的數量。由此，限定有「第一」、「第二」的特徵可以明示或者隱含地包括一個或者更多個該特徵。在本發明的描述中，「多個」的含義是兩個或兩個以上，除非另有明確具體的限定。在本發明中，除非另有明確的規定和限定，術語「安裝」、「相連」、「連接」、「固定」等術語應做廣義理解，例如，可以是固定連接，也可以是可拆卸連接，或一體地連接；可以是機械連接，也可以是電連接；可以是直接相連，也可以通過中間媒介間接相連，可以是兩個元件內部的連通。對於本領域的普通技術人員而言，可以根據具體情況理解上述術語在本發明中的具體含義。在本發明中，除非另有明確的規定和限定，第一特徵在第二特徵之「上」或之「下」可以包括第一和第二特徵直接接觸，也可以包括第一和第二特徵不是直接接觸而是通過它們之間的另外的特徵接觸。而且，第一特徵在第二特徵「之上」、「上方」和「上面」包括第一特徵在第二特徵正上方和斜上方，或僅僅表示第一特徵水平高度高於第二特徵。第一特徵在第二特徵「之下」、「下方」和「下面」包括第一特徵在第二特徵正下方和斜下方，或僅僅表示第一特徵水平高度小於第二特徵。如圖1，本發明實施例的無線傳感網絡的可分解聚合查詢處理方法包括以下步驟步驟S101.將多個無線傳感器的節點構建成樹狀拓撲結構。樹根是一個用戶指定的傳感器節點，該節點直接連接到伺服器。樹根節點廣播拓撲創建信息和查詢請求，並且整個路由樹上所有無線傳感器節點返回的數據都匯集到根節點。具體地，基本的拓撲構建方法如下根節點廣播初始拓撲創建信息，該信息包含樹根節點的ID和層號(根節點的層號為O)。收到此信息的任意中間節點緩存信息中的ID作為其父節點，並且將自己的層號設置為信息中的層號加I。然後，將信息中ID和層號替換為自己的ID和層號並廣播出去。拓撲創建信息以這種方式洪泛到整個網絡並在葉節點出停止。為了運行智能路徑選擇算法，本發明提出的技術對建立生成樹的過程做如下改進。使用一個序列號來作為節點ID，拓撲創建信息包含兩個部分，序列號和層號。子節點可以從創建信息中找出父節點的序列號，然後在這個序列號的末尾擴展一位數字。然後，子節點使用擴展後的序列號作為自己的序列號。該編號過程可以描述如下當一個中間節點收到父節點的創建信息時，它發送給父節點一個反饋，通過這種途徑父節點了解到子節點的信息。然後父節點為每個自節點都分配一個唯一的整數從O開始到子節點的總數量並通知所有子節點這個設置。分配的過程可以按照子節點反饋的順序或者它們的物理位置(如果可用)等。子節點將這個整數添加在收到創建信息中的序列號後面作為自己的序列號，並把包含自己新的序列號和加I後層號的信息再廣播出去。按照這個過程，每個節點將會擁有個反映其在拓撲中邏輯位置的序列號。如圖2所示，節點A分別設置它的三個子節點為O，I, 2。三個子節點將這個數字擴展到自己收到消息中的序列號(節點A的序列號)後面來得到自己的序列號，分別為〈020〉，〈021〉和〈022〉。事實上，序列號反映了節點到樹根的路徑。當至幡節點跳數增加的時候，序列號也會變得很長。但我們存儲序列號的空間是有限的，因此我們採用將序列號截斷並僅存儲最後幾位(臨近節點往往共享祖先節點，因此最後幾位可以區別它們)。這種情況下，序列號具有〈number, Lc>的形式,其中Lc (當前節點的層)表示該序列號最後的層號。步驟S102.用戶發出連續聚合查詢，連續聚合查詢通過樹狀拓撲結構被洪泛到傳感器網絡中。網絡拓撲建好後，用戶發出一個連續聚合查詢，例如AVG，即用戶希望周期性了解無線傳感器網絡中所有節點採樣的平均值。該查詢通過樹狀拓撲被洪泛到網絡中。在接下來的過程中，每個節點周期性對需要監測的參數進行採樣並將數據送回基站。步驟S103.採用多父節點方法並結合智能傳輸路徑選擇算法，計算每個節點的優選父節點，其中，計算得到的優選父節點的數目為多個。無線傳感器節點在每一個周期都採集到一個感知數據並將其發送給父節點(距離根節點更近)，通過多跳傳遞數據到達根節點連接的伺服器進行匯總查詢結果計算。中間結點聚合多個子節點數據上傳以節省通訊開銷。傳統TAG查詢技術使用單一路徑來進行傳輸，即每個節點將數據發給自己的一個父節點。而本發明提出的技術採用了多父節點的方法並結合智能路徑選擇算法，也就是子節點緩存多個上遊節點作為可能的父節點同時向每個父節點都發送部分值。在密度較高的網絡中，傳感器節點的通訊範圍內有很多可能的父節點。如果向所有的父節點都發送數據流量開銷很大，另外向過多的父節點發送部分值也會導致嚴重的鏈路共享問題，使得運算結果的方差增大。步驟S104.數據通過樹形拓撲結構傳輸，節點在每一個周期採集一次對應的多個子節點的數據並聚合成單個結果，然後重新切分為部分值後發送給對應的多個優選父節點，通過多跳傳遞數據到達根節點連接的伺服器進行匯總查詢結果計算。例如對於AVG查詢，需要把COUNT和SUM值放到一個數據包中〈count, sum〉。如果子節點有多個父節點，智能路徑選擇算法將會選擇其中一部分來發送數據。如果我們選擇3個上遊節點作為當前父節點,則部分值〈count/3, sum/3>將會被發送到每個父節點。步驟S105.傳輸過程中應用網內聚合直至根節點處，最終基站利用根節點接收到的所有數據計算最終的查詢結果。具體地，感知數據包通過網絡傳輸，傳輸過程中應用網內聚合，即中間節點將從所有子節點收到的數據聚合成單個結果，然後重新拆分為部分值轉發給自己選擇的那些父節點。最後，基站利用接收到的所有數據計算最終的查詢結果。
本發明公開了一種無線傳感網絡的可分解聚合查詢處理方法，通過設計概率補償模型(PCM)和智能路徑選擇機制來解決鏈路丟包對查詢結果準確率的影響同時降低通訊開銷。本發明的優點在於:第一，本發明提出的技術能夠持續獲得可分解聚合查詢結果。第二，本發明提出的技術通過概率補償能夠克服無線鏈路數據丟失帶來的負面影響，顯著提高查詢結果準確性。第三，本發明提出的智能路徑選擇技術顯著減少通訊開銷，並且提高結果的穩定性。在本發明的一個實施例中，步驟S3進一步包括:S31.計算所有可能父節點到子節點直接父節點的距離，根據距離將可能父節點投影到一條直線上；以及S32.子節點在生成樹上的直接父節點默認被選為第一個優選父節點，然後從子節點的其他可能父節點中均勻選出預定數量的優選父節點。具體地，可以分為以下兩個階段:第一階段，計算所有可能父節點到子節點直接父節點(生成樹創建時的父節點)的距離。這些距離反映了這些可能父節點的相對位置，根據它們的位置(在拓撲上從左至右)可以把這些可能父節點都投影到一條直線上。路徑選擇的目的是減少父節點數量和鏈路共享問題。因此本發明提出的技術嘗試在邏輯拓撲上選擇相互之間邏輯距離較遠的父節點，減少共享鏈路帶來的連續查詢結果在數據丟失的環境下方差較大的缺點。如前所述，節點的邏輯位置可以由它們的序列號來確定，因此節點間的邏輯距離能夠通過它們的序列號來計算。例如我們希望計算節點I (序列號〈NIL1-d+lNIL1-d+2...NILi, Li 和J (〈NJLj-d+lNJLj-d+2...NJLj, Lj>)之間的邏輯距離。令d代表序列號的長度，Li和Lj表示兩個節點的層號，NI和NJ是兩個序列(〈NIL1-d+lNIL1-d+2...NILi>和〈NJLj-d+lNJLj-d+2...NJLj>)。它們之間邏輯距離的定義如下:
max (Li—d+1lj—d+i)DISij =Σ(NIk — NJk) X S(max(li,lj)_k))
k=min (Li,Lj)其中DISij表示節點I到J的距離，S是父節點可有的子節點的最大子節點數。第二階段，從候選中選擇父節點。子節點在生成樹上的直接父節點默認被選為父節點。然後從其他候選中均勻選出期望數量的父節點，使得他們之間的距離最大。在圖3所示的實例中，節點C默認被選為父節點。接下來最左邊的節點A和最右邊的節點G (到C具有最大的絕對距離)被選為父節點。如果需要更多的父節點，繼續劃分A到C或者C到G的範圍為幾個等份同時將那些分界點附近的節點選為父節點。例如在選擇了 C，A，G之後還需要一個父節點，C和G重點附近的節點E將被選中。一旦父節點選擇完畢，它們將會緩存所有的子節點信息，並且接收在它們緩存列表中的子節點發來的數據包。在本發明的一個實施例中，還包括:在節點內增加計數器，觀察並計算鏈路的接收率和丟失率，並利用接受率和丟失率對節點傳輸的數據進行概率補償。具體地，由於無線鏈路的不穩定性，數據可能會丟失導致查詢結果的偏差，本發明提出概率補償技術來解決這一問題。首先需要對鏈路的數據丟失率進行估計。提出一種簡單高效的動態鏈路丟失率(L)估計算法。鏈路丟失率依賴於發送方發出的包數和接收方收到的包數之差。父節點統計收到包數並通知其子節點。收到包數記為N，發送的總包數為M，因此鏈路丟失率為L=(l -N/M)其中N/M是接收率。因為接收方給發送方的反饋頻率很低而且能夠利用捎帶的方式，因此這一方法帶來的開銷很小，僅是在節點內增加的計數器變量。因為最近時間段內觀察到的單個鏈路丟失率(L)不夠準確，本發明引入卡爾曼濾波器，利用觀察到的鏈路丟失率來得到真實鏈路丟失率的最優估計。本發明提出通過鏈路估計得到每一條傳輸鏈路的數據丟失率，然後依據該數據丟失率對傳輸的數據進行概率補償。子節點到當前幾個父節點的平均鏈路丟失率，記作L,補償後的部分值為〈count/c (1-L)，sum/c(1-L)>。在本發明的一個實施例中，還包括在節點引入卡爾曼濾波器對觀察到的鏈路丟失率進行修正，以使得到真實鏈路丟失率的最優估計。流程圖中或在此以其他方式描述的任何過程或方法描述可以被理解為，表示包括一個或更多個用於實現特定邏輯功能或過程的步驟的可執行指令的代碼的模塊、片段或部分，並且本發明的優選實施方式的範圍包括另外的實現，其中可以不按所示出或討論的順序，包括根據所涉及的功能按基本同時的方式或按相反的順序，來執行功能，這應被本發明的實施例所屬技術領域的技術人員所理解。在本說明書的描述中，參考術語「一個實施例」、「一些實施例」、「示例」、「具體示例」、或「一些示例」等的描述意指結合該實施例或示例描述的具體特徵、結構、材料或者特點包含於本發明的至少一個實施例或示例中。在本說明書中，對上述術語的示意性表述不一定指的是相同的實施例或示例。而且，描述的具體特徵、結構、材料或者特點可以在任何的一個或多個實施例或示例中以合適的方式結合。儘管上面已經示出和描述了本發明的實施例，可以理解的是，上述實施例是示例性的，不能理解為對本發明的限制，本領域的普通技術人員在不脫離本發明的原理和宗旨的情況下在本發明的範圍內可以對上述實施例進行變化、修改、替換和變型。
權利要求
1.一種無線傳感網絡的可分解聚合查詢處理方法，其特徵在於，包括以下步驟: 51.將多個無線傳感器的節點構建成樹狀拓撲結構； 52.用戶發出連續聚合查詢，所述連續聚合查詢通過所述樹狀拓撲結構被洪泛到所述傳感器網絡中； 53.採用多父節點方法並結合智能傳輸路徑選擇算法，計算每個所述節點的優選父節點，其中，計算得到的所述優選父節點的數目為多個； 54.數據通過所述樹形拓撲結構傳輸，所述節點在每一個周期採集一次對應的多個子節點的數據並聚合成單個結果，然後重新切分為部分值後發送給對應的多個優選父節點，通過多跳傳遞數據到達根節點連接的伺服器進行匯總查詢結果計算；以及 55.傳輸過程中應用網內聚合直至根節點處，最終基站利用根節點接收到的所有數據計算最終的查詢結果。
2.如權利要求1所述的無線傳感網絡的可分解聚合查詢處理方法，其特徵在於，所述步驟S3進一步包括: 531.計算所有可能父節點到子節點直接父節點的距離，根據所述距離將所述可能父節點投影到一條直線上；以及 532.子節點在生成樹上的直接父節點默認被選為第一個優選父節點，然後從子節點的其他可能父節點中均勻選出預定數量的優選父節點。
3.如權利要求1所述的無線傳感網絡的可分解聚合查詢處理方法，其特徵在於，還包括:在所述節點內增加計數器，觀察並計算鏈路的接收率和丟失率，並利用所述接受率和丟失率對所述節點傳輸的數據進行概率補償。
4.如權利要求1所述的無線傳感網絡的可分解聚合查詢處理方法，其特徵在於，還包括:在所述節點引入卡爾曼濾波器對觀察到的鏈路丟失率進行修正，以使得到真實鏈路丟失率的最優估計。
全文摘要
本發明提出一種無線傳感網絡的可分解聚合查詢處理方法，包括將多個無線傳感器的節點構建成樹狀拓撲結構；用戶發出連續聚合查詢；採用多父節點方法並結合智能傳輸路徑選擇算法，計算每個節點的優選父節點；數據通過樹形拓撲結構傳輸，節點在每一個周期採集一次對應的多個子節點的數據並聚合成單個結果，然後重新切分為部分值後發送給對應的多個優選父節點，通過多跳傳遞數據到達根節點連接的伺服器進行匯總查詢結果計算；以及傳輸過程中應用網內聚合直至根節點處，最終基站利用根節點接收到的所有數據計算最終的查詢結果。本發明能夠克服無線鏈路數據丟失帶來的負面影響，並且能夠顯著減少通訊開銷，並且提高結果的穩定性。
文檔編號H04W84/18GK103077251SQ20131003946
公開日2013年5月1日 申請日期2013年1月31日 優先權日2013年1月31日
發明者劉克彬, 劉雲浩 申請人:清華大學