[發明專利]一種面向物聯網數據的分布式Top-k查詢方法

有效

• 申請號: 201510244016.1
• 申請日: 2015-05-14
• 公開（公告）號: CN104812015B
• 公開（公告）日: 2018-09-11
• 發明（設計）人: 鄔海琴;王良民;湯金娥;陳向益;周從華
• 申請（專利權）人: 江蘇大學
• 主分類號: H04W40/10
• 分類號: H04W40/10;H04W84/18
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

本發明公開一種面向物聯網數據的分布式Top?k查詢方法，包括以下步驟：(1)構建最優查詢樹，該步驟包括網絡骨干節點選取、連接節點選擇，以及每輪查詢各節點按ID號輪流擔任根節點三個過程；(2)基于最優查詢樹進行Top?k查詢，該步驟包括查詢初始化、數據更新值發送、sink節點top?k查詢三個過程。本發明在構建最優查詢樹時充分考慮節點度數、自身能量以及與鄰節點通信開銷，選擇能量代價小的作為支配節點，有效均衡節點能耗，進一步解決了傳統查詢樹根節點唯一帶來的其附近節點過早死亡的問題，大大延長物聯網的生命周期，且查詢算法中通過設置過濾值來抑制每輪無效更新值的發送，有效降低平均每輪的查詢能耗。

技術領域

本發明涉及物聯網數據處理技術，具體涉及一種面向物聯網數據的分布式Top-k查詢方法。

背景技術

物聯網是通過各種傳感器設備，將物品與網絡連接起來，進行信息交換與通信以及實現智能化識別、定位、跟蹤、監控和管理的一種網絡。作為物聯網感知層的重要組成部分，傳感器節點在信息獲取與處理過程中發揮了重大作用。

Top-k查詢作為物聯網查詢應用的重要內容，在多個領域已得到廣泛應用，如環境污染監測、動物保護及目標跟蹤等；用戶可根據自身需要查詢監測區域內前k個最大(或最小)感知值，如溫度、污染指數等，從而起到森林預警、判斷污染程度較高地區的作用，然而傳感器節點能量嚴格受限，因此設計高效的查詢算法對降低網絡能耗、延長傳感器節點壽命至關重要。

目前提出的分布式Top-k查詢方法大都是基于某種邏輯拓撲樹，按照拓撲樹進行數據匯聚查詢能減少大量通信開銷。如Wu等人基于最短路徑樹SPT提出的FILA算法，SPT以sink為根節點，其余節點均有到sink的最短路徑，但FILA算法忽略了各節點接收探測信息的能耗，與實際不符，每一輪查詢，若節點感知值沒有超出過濾范圍，則不向sink發送更新值，故查詢結果不準確。

為了滿足查詢準確性，Balijeet等提出了基于支配集樹DST的查詢算法EXTOK，該算法為每個節點設置過濾閾值來決定其下一輪是否向sink發送更新值，但其DST的構建主要選擇鄰節點多的作為支配節點，未考慮節點自身能量和與鄰節點通信開銷，當查詢次數、k值增大時，存在sink附近節點能耗不均，過早死亡的問題，且EXTOK算法中TM-node需每輪向sink發送更新值，導致一些值的無效發送。

湯等人基于層次索引樹提出了新穎的top-k查詢算法，同樣存在頭結點選取未考慮自身能量而過早死亡等問題。

發明內容

發明目的：本發明的目的在于解決現有技術存在的不足，提供一種面向物聯網數據的分布式Top-k查詢方法，本發明從構建邏輯拓撲樹和基于樹設計top-k查詢方法兩方面來提供一種能量均衡、高效的物聯網分布式數據Top-k查詢方法。

技術方案：本發明所述的一種面向物聯網數據的分布式Top-k查詢方法，包括以下步驟：

(1)構建最優查詢樹：

(11)網絡骨干節點選取，即網絡支配節點的選取，具體過程如下：

(111)節點狀態和能量信息的初始化，各節點初始均為未處理狀態，即flag＝0，并通過能量代價函數算得相應的能量代價值，該能量代價函數綜合考慮了節點度數、自身剩余能量以及與鄰節點通信開銷，是最后所得查詢結果更加精準；

(112)代價信息交換：各節點發送hello消息包和能量代價消息包，并與其鄰節點交換代價信息；

(113)節點狀態信息廣播：

(12)連通支配集構造；包括支配信息存儲和連接節點選擇；

(13)根節點選擇，即sink節點的選擇，包括以下步驟：

(131)在步驟(12)所得連通支配集基礎上，保留支配節點與其被支配節點之間的邊，其余邊均去除；