傳感器網(wǎng)絡(luò)中基于抽樣的帶權(quán)近似Top—k查詢算法

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

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；抽樣算法；Top-k查詢

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

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

由于傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)通信范圍、計(jì)算處理、存儲(chǔ)容量和能量大小都非常有限，聚集查詢算法第一要?jiǎng)?wù)就要考慮節(jié)能，最大化網(wǎng)絡(luò)的壽命.節(jié)點(diǎn)能量耗盡而失效，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時(shí)發(fā)生變化，而且節(jié)點(diǎn)在發(fā)送數(shù)據(jù)丟包和通信連接失敗時(shí)，就會(huì)破壞生成的路由樹，在很多情況下，傳感器網(wǎng)絡(luò)無法得到用戶精確的查詢分析結(jié)果.近年來，許多學(xué)者提出了許多能在傳感器網(wǎng)絡(luò)中進(jìn)行近似查詢的算法，近似算法能減少節(jié)點(diǎn)數(shù)據(jù)的發(fā)送量，節(jié)約節(jié)點(diǎn)的能量，最大化提高網(wǎng)絡(luò)的壽命.

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

文獻(xiàn)[9]使用了一種概要查詢處理技術(shù).與其它查詢算法不同的是在查詢處理過程中只需要傳輸概要信息，而不需要傳感器節(jié)點(diǎn)的感知值，這種技術(shù)可以減少節(jié)點(diǎn)的能量開銷.文獻(xiàn)[10]利用傳感器網(wǎng)絡(luò)的時(shí)間和空間相關(guān)性原理進(jìn)行近似查詢處理，減少節(jié)點(diǎn)數(shù)據(jù)的發(fā)送，降低能量的消耗.

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

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)感知的數(shù)據(jù)具有時(shí)間和空間相關(guān)性，可以利用網(wǎng)絡(luò)的歷史查詢信息估算出一個(gè)抽樣閥值，在每個(gè)簇內(nèi)進(jìn)行抽樣過濾處理時(shí)，只有大于閥值的感知值才會(huì)被發(fā)送給簇頭節(jié)點(diǎn)，從而能夠減少節(jié)點(diǎn)不相關(guān)信息的發(fā)送，節(jié)約能源，提高網(wǎng)絡(luò)的壽命.

4 實(shí)驗(yàn)仿真及結(jié)果分析

在伯克利分校研究者研發(fā)的TAG[13]平臺(tái)上進(jìn)行實(shí)驗(yàn).仿真實(shí)驗(yàn)中的感知數(shù)據(jù)來自于Berkeley Intel實(shí)驗(yàn)室傳感器網(wǎng)絡(luò)監(jiān)測(cè)真實(shí)環(huán)境時(shí)得到的溫度數(shù)據(jù).

選取簡(jiǎn)單的Top-k抽樣近似算法和本文的基于抽樣帶權(quán)閥值過濾近似Top-k聚集查詢算法進(jìn)行對(duì)比實(shí)驗(yàn).

簡(jiǎn)單Top-k抽樣近似查詢算法由Sink節(jié)點(diǎn)隨機(jī)獨(dú)立地產(chǎn)生樣本大小為S的樣本，Sink節(jié)點(diǎn)將樣本S廣播到網(wǎng)絡(luò)中進(jìn)行抽樣，如果節(jié)點(diǎn)編號(hào)在抽樣樣本中，就將該節(jié)點(diǎn)的信息發(fā)送給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)收到數(shù)據(jù)后輸出前k個(gè)最大值作為Top-k查詢的近似結(jié)果.而帶權(quán)近似Top-k查詢抽樣算法只需抽樣本簇中少量數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，大大減少了數(shù)據(jù)的發(fā)送量，節(jié)省了網(wǎng)絡(luò)中節(jié)點(diǎn)的能量.圖1可以說明這種變化趨勢(shì).

選取簡(jiǎn)單Top-k簇內(nèi)抽樣近似查詢算法和本文帶權(quán)過濾簇內(nèi)抽樣算法在不同的網(wǎng)絡(luò)規(guī)模下應(yīng)當(dāng)選取樣本容量的大小關(guān)系如圖2所示.

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

給定k值進(jìn)行帶權(quán)近似Top-k查詢抽樣算法時(shí)，抽樣的樣本容量與用戶查詢的精度大小和網(wǎng)絡(luò)規(guī)模有著密切的關(guān)系，網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量越多，查詢精度要求越低，抽樣的樣本大小就越大，從圖3的實(shí)驗(yàn)結(jié)果可以知道這種變化趨勢(shì).

5 結(jié) 語

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

參考文獻(xiàn)

[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.