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

(1．湖南大學 信息科學與工程學院，湖南 長沙 410082；2．湖南大學 電氣與信息工程學院，湖南 長沙 410082)

?

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

劉彩蘋1，蔡玉武1，毛建旭2*，龍亞輝1

(1．湖南大學 信息科學與工程學院，湖南 長沙 410082；2．湖南大學 電氣與信息工程學院，湖南 長沙 410082)

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

無線傳感器網(wǎng)絡；抽樣算法；Top-k查詢

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

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

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

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

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

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

1 帶權(quán)近似Top-k查詢定義

如果在網(wǎng)絡進行聚集查詢時，網(wǎng)絡是由N個節(jié)點組成，則把節(jié)點的集合記為I={1,2,3,…,N}.傳感器網(wǎng)絡存在一個能量和處理能力都強大的匯聚節(jié)點，根據(jù)路由算法以匯聚節(jié)點為根生成最小生成樹，在進行聚集查詢時匯聚節(jié)點會將用戶的請求分發(fā)給所有節(jié)點.在t時刻，網(wǎng)絡中各節(jié)點感知到的數(shù)據(jù)集合為Dt={d1,d2,…,dN},di={di.v,di.id,di.t}其中di.v是節(jié)點的物理感知值，di.id是標識節(jié)點的唯一ID，di.t是感知數(shù)據(jù)時的時間戳.

定義1k是自然數(shù)，且|I|≥k,在t時刻時，數(shù)據(jù)集合Dt的帶權(quán)Top-k集合記為W-Top(k,Dt),是I的一個真子集，同時W-Top(k,Dt)要符合以下要求：

1)W-Top(k,Dt)?I;

2)|W-Top(k,Dt)|=k．

3)對于?i∈W-Top(k,Dt),?j∈IW-Top(k,Dt)均滿足widi≥wjdj.

其中W={w1,w2,…,wN}是網(wǎng)絡中節(jié)點賦與相應的權(quán)值，wi≥1,1≤i≤N.

定義2 對?ε>0,Dt的近似W-Top(k,Dt)記為ε-W-Top(k)，其中,ε-W-Top(k)要符合以下要求：

1)ε-W-Top(k)?I；

2)|ε-W-Top(k)|=k；

證明 如果i∈top(k,X),j?top(k,X)，并且pX(i)>(1+ε).pX(j)，則稱(i,j)對是相關(guān)聯(lián)的.

在樣本S中，如果(i,j)對是相關(guān)聯(lián)的并且滿足pS(i)≤pS(j)，則(i,j)對是弱交換對，ε-W-Top(k,S)是Top(k,S)誤差為ε的近似值當且僅當在S中沒有弱交換對.

2 基于抽樣帶權(quán)近似過濾Top-k查詢處理

算法 基于抽樣的帶權(quán)近似過濾Top-k查詢處理算法所涉及參數(shù)定義如下所示：

Dt={d1,d2,…,dN},表示在t時刻，傳感器網(wǎng)絡中各節(jié)點感知到的數(shù)據(jù)集合，di={di.v,di.id,di.t}中di.v是節(jié)點的物理感知值，di.id是標識節(jié)點的唯一ID，di.t是感知數(shù)據(jù)時的時間戳.

W-Top(k,Dt),表示在t時刻時，數(shù)據(jù)集合Dt的帶權(quán)Top-k集合.

W={w1,w2,…,wN}表示由可信度賦與節(jié)點的權(quán)值，wi≥1,1≤i≤N.

ε,且ε≥0，相對誤差.

qi，表示第i個簇的抽樣概率，其中i=i,2,…,r.

H(k)節(jié)點抽樣時的過濾閾值.

基于抽樣的帶權(quán)閥值過濾近似Top-k聚集查詢算法如下：

輸入

1) Sink節(jié)點存有網(wǎng)絡中所有節(jié)點的權(quán)值，其中Wmax和Wmin為最大最小權(quán)值.

2)t時刻網(wǎng)絡中節(jié)點采集到的數(shù)據(jù)集合Dt={d1,d2,…,dn}.

3) 樣本容量S.

輸出 ε-W-Top(k)候選集

算法詳細步驟如下所示：

ⅰ)將節(jié)點的所有權(quán)值均保存在Sink節(jié)點上,Sink節(jié)點根據(jù)定理1計算出q1的概率值.并由(ε,δ)和以前查詢統(tǒng)計數(shù)據(jù)估算本次抽樣的樣本大小，記為S.

ⅱ)根據(jù)傳感器網(wǎng)絡中時間相關(guān)性原理，匯聚節(jié)點由ε-W-Top(k)的歷史查詢信息計算節(jié)點在抽樣時的過濾閾值H(k)來篩選數(shù)據(jù)以便減少網(wǎng)絡中數(shù)據(jù)的發(fā)送量.

式中W-Top(k)t-1表示抽樣算法返回t-1時刻ε-W-Top(k)集合排列時在集合中第k位的值，d的大小可以根據(jù)實際情況設(shè)置.

ⅲ)匯聚節(jié)點給第Ri個簇頭節(jié)點發(fā)送信息(q1,Wmax,Wmin,S,H(k)),1≤i≤r.第Ri個簇頭節(jié)點接收到匯聚節(jié)點發(fā)送過來的信息后就進行簇內(nèi)節(jié)點抽樣算法.

4)匯聚節(jié)點最終將會收到所有簇頭節(jié)點發(fā)送回來的信息ε-W-Top(k)候選集的子集.

3 簇內(nèi)抽樣帶權(quán)閥值過濾近似Top-k聚集

2)簇頭節(jié)點會根據(jù)抽樣概率qi計算第Ri個簇的樣本大小是S*qi，并記為Si.簇頭節(jié)點隨機獨立均勻地產(chǎn)生Si個屬于{Ri1,Ri2,…,RiRi}的節(jié)點ID集合，并且把ID集合為Mi.然后簇頭節(jié)點會將集合Mi及H(k)值傳送給該簇內(nèi)的所有節(jié)點.

3)若j∈Mi且節(jié)點j的感知信息滿足dj.v≥H(k)，則把節(jié)點j的感知信息傳送給簇頭節(jié)點，否則節(jié)點j不向簇頭節(jié)點傳送數(shù)據(jù)，最終簇頭節(jié)點會收集到該簇內(nèi)所有抽樣的數(shù)據(jù)ε-W-Top(k)-Subi.

由上面的分析可知，基于抽樣帶權(quán)閥值過濾近似Top-k聚集查詢算法如下：

The algorithm of ε-W-Top(k)

Input:W,S,Dt,ε,σ

Output:The set of ε-W-Top(k)

The sink get q1and H(k) by theorem 1 and history data

For any cluster headi,i=1,2,…r

{

Si←S*qi

//簇頭節(jié)點隨機獨立均勻地產(chǎn)生Si個屬于{Ri1,Ri2,...,RiRi}的節(jié)點ID集合

Mi←{Ri1,Ri2,...,RiRi}

j←0

while j<|Mi| do

if(dj.v≥H(k))

ε-W-Top(k)-Subi←dj.v

j←j+1

end while

}

return ε-W-Top(k)

節(jié)點發(fā)送所有權(quán)值的時間復雜度為O(n), 簇內(nèi)節(jié)點抽樣算法的時間復雜度為O(rRi),故最差時間復雜度為O(n2).

4 實驗仿真及結(jié)果分析

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

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

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

Top-k的值

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

網(wǎng)絡規(guī)模

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

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

不同誤差

5 結(jié) 語

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

[1] BARBAGLI B, BENCINI L,MAGRINI I,etal. 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,etal. 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,etal. 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,etal.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,etal.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.

Research on the Approximate Algorithm of Top-k Query Based on Weighted Sampling in Wireless Sensor Network

LIU Cai-ping1，CAI Yu-wu1, MAO Jian-xu2?,LONG Ya-hui1

(1. College of Computer Science and Electronic Engineering, Hunan Univ, Changsha ,Hunan 410082; 2. College of Electric and Information Engineering, Hunan Univ, Changsha,Hunan 410082)

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.

wireless sensor networks; sampling algorithm; Top-k query

1674-2974(2016)10-0134-05

2015-06-27

國家自然科學基金資助項目(61370096，61573134)，National Natural Science Foundation of China(61370096，61573134) ；國家科技支撐計劃資助項目(2015BAF13B00)；湖南省科技計劃資助項目(2012GK3158)

劉彩蘋(1978-)，女，湖南邵陽人，湖南大學講師，博士

?通訊聯(lián)系人，E-mail:maojianxu@hnu.edu.cn

TP212.9

A