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

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

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

?

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

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

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

提出一種適用于傳感器網(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ù)，更小的抽樣樣本，并能滿足任意精度要求.

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

近年來，隨著信息技術(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ò)的壽命.

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

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

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

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

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

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

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

定義2 對(duì)?ε>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)對(duì)是相關(guān)聯(lián)的.

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

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

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

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

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

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

ε,且ε≥0，相對(duì)誤差.

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

H(k)節(jié)點(diǎn)抽樣時(shí)的過濾閾值.

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

輸入

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

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

3) 樣本容量S.

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

算法詳細(xì)步驟如下所示：

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

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

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

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

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

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

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

3)若j∈Mi且節(jié)點(diǎn)j的感知信息滿足dj.v≥H(k)，則把節(jié)點(diǎn)j的感知信息傳送給簇頭節(jié)點(diǎn)，否則節(jié)點(diǎn)j不向簇頭節(jié)點(diǎn)傳送數(shù)據(jù)，最終簇頭節(jié)點(diǎn)會(huì)收集到該簇內(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é)點(diǎn)隨機(jī)獨(dú)立均勻地產(chǎn)生Si個(gè)屬于{Ri1,Ri2,...,RiRi}的節(jié)點(diǎn)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é)點(diǎn)發(fā)送所有權(quán)值的時(shí)間復(fù)雜度為O(n), 簇內(nèi)節(jié)點(diǎn)抽樣算法的時(shí)間復(fù)雜度為O(rRi),故最差時(shí)間復(fù)雜度為O(n2).

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ì).

Top-k的值

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

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

在(ε,δ)和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í)情況.

[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

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

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

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

TP212.9

A