傳感器網絡中基于抽樣的帶權近似Top—k查詢算法

劉彩蘋+蔡玉武+毛建旭+龍亞輝

摘 要：提出一種適用于傳感器網絡的抽樣帶權閥值過濾近似Top-k聚集查詢算法.該近似算法會將無線傳感器網絡劃成幾個兩兩不相交的簇進行處理，在匯聚節點進行預處理以及在各個簇內進行抽樣過濾處理，在抽樣過程中給可靠而重要的節點賦上相應更大的權值，同時根據節點采集的信息具有時間相關特性，在簇內進行抽樣閥值過濾處理，每個簇頭節點都會接收到該簇內的Top-k候選子集，然后將每個簇的子集發送給Sink節點，該Sink節點將接收到能代表整網Top-k樣本候選集.仿真實驗結果顯示該算法只需發送少量的數據，更小的抽樣樣本，并能滿足任意精度要求.

關鍵詞：無線傳感器網絡；抽樣算法；Top-k查詢

中圖分類號：TP212.9 文獻標識碼：A

文章編號：1674-2974（2016）10-0134-05

Abstract：An approximate algorithm of Top-k query based on sampling and weight in wireless sensor network was presented. The algorithm divides the network into several disjoint clusters in the sink node and the nodes in cluster to take sampling process. In the process of sampling， greater weight for reliable and important sensor node is given. The sensor node sensing data has a time correlation， and sampling threshold filtering in the cluster. Each cluster head node receives a Top-k candidate subset of the cluster， and then sends the subset to the sink node. Finally， the sink node can receive a Top-k sample candidate that represents the whole network. Simulation experiments show that the algorithm only needs to send small data and smaller samples， and can satisfy arbitrary precision requirements.

Key words：wireless sensor networks； sampling algorithm； Top-k query

近年來，隨著信息技術的快速發展，物聯網時代已經悄悄向我們走來，無線傳感器網絡是物聯網技術中關鍵技術之一.該技術廣泛使用在現代化信息農業[1]、礦井智能化探測開采[2]和智能家居[3]等方面.傳感器網絡是由許多廉價的微型節點組織而成，可以在其監測范圍內經由路由算法自組織成一個網絡.用戶在網絡中會進行聚集查詢處理，而Top-k查詢是最常見的操作之一，具有非常大的實際意義，例如：用戶在進行空氣質量監測時，甲需要了解PM2.5值最大的k個值，乙需要了解空氣質量指數最大的k個值，有時甲和乙對查詢的精度標準和要求不一樣，需要設計出能適應不同用戶查詢精度的Top-k聚集查詢處理算法以便來滿足多用戶的實際應用需求.

由于傳感器網絡中的節點通信范圍、計算處理、存儲容量和能量大小都非常有限，聚集查詢算法第一要務就要考慮節能，最大化網絡的壽命.節點能量耗盡而失效，網絡拓撲結構隨時發生變化，而且節點在發送數據丟包和通信連接失敗時，就會破壞生成的路由樹，在很多情況下，傳感器網絡無法得到用戶精確的查詢分析結果.近年來，許多學者提出了許多能在傳感器網絡中進行近似查詢的算法，近似算法能減少節點數據的發送量，節約節點的能量，最大化提高網絡的壽命.

文獻[4]提出一種垂直數據處理的Top-k算法.算法的主要思想是生成路由樹，在路由樹中進行Top-k查詢，同時采用歷史數據進行處理.文獻[5]使用位圖壓縮機制減少節點間數據的發送量.節點能量和存儲空間，但是惡意節點利用桶的信息可以估計出查詢結果.文獻[6]提出了一種近似Top-k聚集查詢算法.該算法對傳感器節點感知的數據進行抽樣，并用線性模型得到滿足用戶精度要求的近似查詢結果.文獻[7]利用傳感器節點感知數據的時空相關性.該算法采用綜合樣本抽樣和數據壓縮技術進行聚集查詢.文獻[8]提出了連續k近鄰查詢算法.算法的核心思想是采用環查詢和變量維護技術減少節點數據的發送量.

文獻[9]使用了一種概要查詢處理技術.與其它查詢算法不同的是在查詢處理過程中只需要傳輸概要信息，而不需要傳感器節點的感知值，這種技術可以減少節點的能量開銷.文獻[10]利用傳感器網絡的時間和空間相關性原理進行近似查詢處理，減少節點數據的發送，降低能量的消耗.

實際上，節點在放置時往往出現分布不均勻的情況.目前的Top-k聚集查詢算法有時并不能反映監測區域真實情況，例如下面情況：在環境污染監測的區域，越靠近人類居住或者水源的區域越重要，可能這些區域的空氣質量指數并不是很高，但是它已經對人們的健康產生了影響，需要給用戶報警提示.還有傳感器網絡監測某一小區的噪聲大小，查詢者需要了解噪聲大小會影響居民最高的k個點，在監測范圍內，離居民比較近的點噪聲分貝值雖然不是最大的，但是它對居民的影響超出了遠處分貝值比它高的點.為了滿足實際的需要，可以對重要的區域增加權值的參數，擴大它的作用效果，從而更加能夠反映傳感器網絡監測區域的真實情況[11].

傳感器網絡節點感知的數據具有時間和空間相關性，可以利用網絡的歷史查詢信息估算出一個抽樣閥值，在每個簇內進行抽樣過濾處理時，只有大于閥值的感知值才會被發送給簇頭節點，從而能夠減少節點不相關信息的發送，節約能源，提高網絡的壽命.

4 實驗仿真及結果分析

在伯克利分校研究者研發的TAG[13]平臺上進行實驗.仿真實驗中的感知數據來自于Berkeley Intel實驗室傳感器網絡監測真實環境時得到的溫度數據.

選取簡單的Top-k抽樣近似算法和本文的基于抽樣帶權閥值過濾近似Top-k聚集查詢算法進行對比實驗.

簡單Top-k抽樣近似查詢算法由Sink節點隨機獨立地產生樣本大小為S的樣本，Sink節點將樣本S廣播到網絡中進行抽樣，如果節點編號在抽樣樣本中，就將該節點的信息發送給匯聚節點，匯聚節點收到數據后輸出前k個最大值作為Top-k查詢的近似結果.而帶權近似Top-k查詢抽樣算法只需抽樣本簇中少量數據發送給簇頭節點，大大減少了數據的發送量，節省了網絡中節點的能量.圖1可以說明這種變化趨勢.

選取簡單Top-k簇內抽樣近似查詢算法和本文帶權過濾簇內抽樣算法在不同的網絡規模下應當選取樣本容量的大小關系如圖2所示.

在（ε，δ）和k一定的條件下，簡單Top-k抽樣近似查詢算法進行查詢時隨機獨立地產生樣本大小為S的樣本.而抽樣帶權近似過濾Top-k查詢處理算法通過給定的（ε，δ）和歷史信息估計確定樣本的容量S，在查詢過程中根據權值確定查詢概率計算每個簇內的抽樣樣本以及依據歷史信息過濾抽樣的樣本值，得到能符合（ε，δ）精度的近似Top-k查詢數據.從圖2可以看出，在（ε，δ）和k確定的條件下，帶權近似Top-k查詢抽樣算法在同樣網絡規模大小下樣本容量比簡單Top-k抽樣近似查詢算法都要小.

給定k值進行帶權近似Top-k查詢抽樣算法時，抽樣的樣本容量與用戶查詢的精度大小和網絡規模有著密切的關系，網絡中節點的數量越多，查詢精度要求越低，抽樣的樣本大小就越大，從圖3的實驗結果可以知道這種變化趨勢.

5 結 語

本文提出一種適用于傳感器網絡的抽樣帶權閥值過濾近似Top-k聚集查詢算法.與其它Top-k查詢處理算法不同，本算法進行分簇抽樣處理，并根據實際情況給節點加入了權值參數，同時在每個簇內進行抽樣，根據歷史信息過濾掉不必要的數據，每個簇頭節點會將抽樣子集傳送給匯聚節點，最終匯聚節點收集到全網的滿足用戶查詢精度的Top-k集合.帶權近似Top-k查詢抽樣算法可以有效地減少節點不相關信息的發送，節約能量，提高網絡的生命周期.與普通抽樣算法相比，只需要更少的樣本容量即可，同時可以滿足不同用戶對查詢精度不同的請求.所以，帶權近似Top-k查詢抽樣算法適用于注重節約節點能量的無線傳感器網絡，同時能滿足多用戶的精度要求，以及Top-k查詢的近似結果可以反應傳感器網絡監測區域的真實情況.

參考文獻

[1] BARBAGLI B， BENCINI L，MAGRINI I， et al. A real-time traffic monitoring based on wireless sensor network technologies[C]//Proceedings of the 7th International Wireless Communications and Mobile Computing Conference. Istanbul，Turkey： IEEE Computer Society， 2011：820-825.

[2] ZHANG F， DISANTO W， REN J， et al. A novel cps system for evaluating a neuralmachine interface for artificial legs[C]//Proceedings of IEEE/ACM International Conference on Cyber-Physical Systems. Chicago， USA： IEEE Computer Society， 2011：67-76.

[3] BOCCA M，TOIVOLA J，ERIKSSON M， et al. Structural health monitoring in wireless sensor networks by the embedded goertzel algorithm[C]//Proceedings of IEEE/ACM International Conference on Cyber-Physical Systems.Chicago：IEEE Computer So.Ciety， 2011：206-214.

[4] CHU D， DESHPANDE A， M.HELLERSTEIN J M，et al.data collection in sensor networks using probabilistic models[C]//In Proceedings of the 22th International Conference on Data Eingineering. Georgia， USA：April 3-7，2006： 234-251.

[5] CAO Q， ABDELZAHER T， HE T， et al.Towards optimal sleep scheduling in sensor networks for rare event detection[C]//Proceedings of IPSN.CA，USA：IPSN， 2005： 20-27.

[6] KOUSHANFAR F， TAFT N， POTKONJAK M.Sleeping coordination for comprehensive sensing using isotonic regression and domatic partitions[C]//Proceedings of IEEE Infocom.Barcelona， Spain： 2006：45-58.

[7] LI J，LI Z.Data sampling control，compression and query in sensor[J] . International Journal of Sensor Networks，2014，2（1/2）：53-61.

[8] YAO Yu-xia ， TANG Xue-yan， LIM Ee-peng .Localized monitoring of knn queries in wireless sensor networks[J]. The VLDB Journal， 2014，18（1）：99-117.

[9] NASRIDINOV A，PARKY H.Optimal aggregator node selection in wireless sensor networks[C]//Proceedings of ICCA.Seoal， Korea：ICCA，2013， ASTL， 2013： 37-39.

[10]DELIGIANNAKIS A，PROCESSING Y K. Approximate aggregation queries in wireless senor networks[J]. Information Systems， 2013， 31（8）：770-792.

[11]BI Ran，LI Jian-zhong，CHENG Si-yao.Approximate Top-k query processing algorithm in wireless sensor networks[J].Journal on Communications，2011，32（8）：45-54.

[12]BEMSEIN S， BERNSTEIN R. Elements of statistics II： descriptive statistics[M].Newyork：USA McGraw-Hill， 2004.

[13]MADDEN S， FRANKLIN M J， HELLERSTEIN J M.TAG： a tiny aggregation service for Ad-Hoc sensor networks[C]//Symposium on Operating Systems Design and Implementation.Boston：MA，2002：131-146.