基于分簇的無線傳感器網(wǎng)絡Top-K 數(shù)據(jù)查詢算法

江 欣，李長庚

(中南大學 物理與電子學院，湖南 長沙410083)

0 引 言

隨著物聯(lián)網(wǎng)的發(fā)展，無線傳感器網(wǎng)絡被運用到社會活動中的方方面面，如醫(yī)療護理、森林火災和洪水監(jiān)測等［1］。數(shù)據(jù)查詢是無線傳感器網(wǎng)絡應用中的一個非常關鍵的應用，而Top－K 查詢是查詢應用中的一個重要內容［2］。無線傳感器網(wǎng)絡通過監(jiān)控范圍中最大的監(jiān)測參數(shù)(如，血壓、心率、溫度、土壤水分等參數(shù))，可以起到判斷人的身體指標、森林溫度預警和洪水監(jiān)測的作用。由于傳感器節(jié)點通常都是分布在無人看護的環(huán)境中，所以，減少傳感器網(wǎng)絡的整體能耗是研究者追求的目標，能量消耗越小，節(jié)點生命周期就越長。由于無線傳感器網(wǎng)絡中的能量消耗的絕大部分是通信能耗，因此，無線傳感器網(wǎng)絡的一個迫在眉睫的問題就是如何降低網(wǎng)絡的整體通信能耗。

為了節(jié)省通信量，TAG［3］算法采用對網(wǎng)內數(shù)據(jù)進行融合的思想減少數(shù)據(jù)的傳輸量，得到精確的查詢結果。TAG算法是把這個網(wǎng)絡看成一顆樹，這樣數(shù)據(jù)傳輸?shù)奶鴶?shù)是多跳，通信能耗相對比較大。FILA［4］算法是基于過濾的算法，此過濾算法雖減少了冗余數(shù)據(jù)的上傳，但當數(shù)據(jù)變化比較大時會產(chǎn)生很大的窗口更新代價，消耗能量較多。

針對TAG 與FILA 算法的不足，本文提出一種基于分簇的無線傳感器網(wǎng)絡Top－K 數(shù)據(jù)查詢算法，首先對網(wǎng)絡進行分簇［5～7］，每個簇選出一個簇頭節(jié)點，簇中其他節(jié)點將數(shù)據(jù)傳遞給簇頭節(jié)點，然后再傳給Sink 節(jié)點，這使得傳輸?shù)奶鴶?shù)在兩跳之內，減少了發(fā)送和接收能耗。在每個節(jié)點設置過濾器值，當數(shù)據(jù)不夠時利用探尋來補充數(shù)據(jù)，使得數(shù)據(jù)的傳輸次數(shù)減少，降低整體能耗。

1 網(wǎng)絡分簇

1.1 簇頭選舉

在算法的預處理階段，傳感器網(wǎng)絡中的節(jié)點先生成一個數(shù)，此數(shù)大于0 小于1，之后算出簇頭競爭的判定值Pc(r)，讓生成的數(shù)與判定值比較大小，如果數(shù)比判斷值Pc(r)小，則節(jié)點就是相對應簇的簇頭節(jié)點。Pc(r)的計算公式為

式中 Pc(r)為節(jié)點競爭簇頭的判定值，p 為網(wǎng)絡最初時已分簇的簇頭數(shù)目，Ei為i 傳感器節(jié)點的剩下的能量，E0為傳感器節(jié)點最開始的能量，n 為總的傳感器節(jié)點數(shù)，r 為輪數(shù)，Nch為目前傳感器節(jié)點當選成簇頭的數(shù)目。pEi/E0的比值可以作為選取簇頭的標準，剩下的能量越多，那么，變成簇頭的機會就會越大。分子中式子是作為“均衡因子”用來平衡簇頭數(shù)量，而分母中加入Nchmod(1/p)是為了規(guī)避由于相同節(jié)點經(jīng)常被選為簇頭節(jié)點而使得能量消耗過快造成節(jié)點過早死去。

1.2 簇頭數(shù)優(yōu)化機制

當網(wǎng)絡中簇頭選舉完成后，計算簇頭間的距離，設置一個距離閾值，避免簇頭與簇頭之間由于距離太近或者太遠引起分簇不勻，簇頭之間的距離不在閾值范圍內的就需重新選擇簇頭。簇頭距離閾值U 的確定依照下式［8］

式中 U 為傳感器網(wǎng)絡中最優(yōu)簇頭數(shù)目，N 為傳感器網(wǎng)絡中的傳感器節(jié)點總的數(shù)目，M 為傳感器網(wǎng)絡的范圍邊界的長度，dbs為每個簇中的簇頭到Sink 節(jié)點之間的長度，通過式(2)，如果已知N 與M 的大小，通過測量dbs就可以得到相應的閾值U 的區(qū)間，Eelec為接收電路能耗，且Eelec=50 nJ/bit，εfs為自由空間模型放大器能耗，且εfs=10 pJ/bit/m，εmp為多徑衰減模型的放大器能耗，且εmp=0.001 3 pJ/bit/m4。

1.3 成簇機制

當簇頭優(yōu)化完成之后，每個簇頭通過泛洪將信息廣播出去，此信息包含節(jié)點的ID 身份、節(jié)點剩下的能量和節(jié)點所在的位置，然后通知本簇中其他傳感器節(jié)點，本簇的簇頭節(jié)點已經(jīng)選舉完成，本簇中其余的傳感器節(jié)點在接收到本簇的簇頭發(fā)來的泛洪信息之后，算出一個成簇的權值WCL，WCL表達式如下

式中 WCL為傳感器節(jié)點成為簇的權值，ECH為此簇的簇頭節(jié)點剩下的能量，d(i，CH)為i 傳感器節(jié)點與其對應簇的簇頭節(jié)點的距離。通過式(3)分析，傳感器節(jié)點剩下能量越大、所在簇的簇頭節(jié)點ECH越大，而節(jié)點與簇頭的d(i，CH)減小時，那么，WCL會變大，節(jié)點成為該簇的節(jié)點機會增加，WCL通過分析傳感器節(jié)點剩下的能量和節(jié)點之間的距離，可以合理分簇。經(jīng)過算出成為不同簇的WCL，傳感器節(jié)點會選取WCL最大的簇成為其相應的簇，然后將節(jié)點的ID、位置和剩余的能量以信息的形式發(fā)送給簇頭表示愿意成為本簇成員，而簇頭節(jié)點在接收到相應簇的其他傳感器節(jié)點發(fā)來的信息之后表示分簇過程結束。

2 算法描述

設網(wǎng)絡中傳感器節(jié)點的過濾器的值為fn(T)=BT，n=1，2，…，N。

查詢過程中，在T 以后時刻，Sink 節(jié)點依照用戶提出的查詢要求Kt(q)，q=1，2，…，取其中最大的值作為本次用戶所需要查詢的KT值，即KT=max{Kt(q)，q=1，2，…}，并通過泛洪的方式向網(wǎng)絡中的節(jié)點發(fā)送目前所需要查詢的KT值。

網(wǎng)絡中節(jié)點收到泛洪信號之后，收集的感知數(shù)據(jù)不在時間區(qū)間t(t'－T≤t≤t'，其中，t'＞T)內的感知數(shù)據(jù)去掉，把標記已傳遞的記號的感知數(shù)據(jù)也去掉，同時將余下的其他數(shù)據(jù)排序，獲得最大的K 個值。然后將此K 個值與目前此節(jié)點的過濾器fn(t－1)對比，只向簇頭節(jié)點傳遞大于過濾器fn(t－1)的數(shù)據(jù)，同時將向簇頭節(jié)點傳輸?shù)臄?shù)據(jù)打上已傳遞記號。每個簇的簇頭節(jié)點在得到本簇中其他節(jié)點上傳的感知數(shù)據(jù)后，把本簇中其他節(jié)點的感知數(shù)據(jù)與簇頭節(jié)點本身采集到的感知數(shù)據(jù)進行排序，獲取滿足要求的最大的K 個值，然后把這滿足要求的K 個值發(fā)送給Sink 節(jié)點，供用戶進行數(shù)據(jù)查詢。

將Sink 節(jié)點收到所有簇頭節(jié)點發(fā)送過來的數(shù)據(jù)看作是一個數(shù)據(jù)集Wt，設此時Sink 節(jié)點所擁有的數(shù)據(jù)集Wt一共有M 個數(shù)據(jù)，通過排序之后大小順序為wt(1)≤wt(2)≤…≤wt(M)。如果比Bt－1大的數(shù)據(jù)的數(shù)量多于或者等于K，那么，就對最大的K 個數(shù)據(jù)進行網(wǎng)內存儲，供用戶快速查詢，然后進入設定過濾器值的階段。

如果所收集的數(shù)據(jù)集Wt中比Bt－1大的數(shù)據(jù)的數(shù)量小于K，則表示過濾器值設置偏高，使比Bt－1小的感知數(shù)據(jù)未發(fā)送過來，這需繼續(xù)探尋比Bt－1小的感知數(shù)據(jù)，補全Top－K數(shù)據(jù)，滿足查詢的要求。本簇中的節(jié)點在獲取Sink 節(jié)點的探尋的消息和條件后，將沒有標記已傳遞記號的，同時又比探尋條件的值大的感知數(shù)據(jù)繼續(xù)傳遞給簇頭節(jié)點，然后由簇頭節(jié)點上傳給Sink 節(jié)點。同時把已發(fā)送的感知數(shù)據(jù)標記已傳遞的記號，當Sink 節(jié)點獲取了滿足條件的K 個值后才停止探尋，然后才把這些數(shù)據(jù)進行網(wǎng)內存儲，供用戶查詢，接下來才進入設定過濾器值的階段。

在探尋階段之后，如果Sink 節(jié)點數(shù)據(jù)集的數(shù)據(jù)個數(shù)為M't，將收集到的感知數(shù)據(jù)排序，記wt(1)≤wt(2)≤…≤wt(M't)，通過上述的探尋過程可以確保M't大于或等于K。這時可設定一個新的Bt值作為預測值，用來判斷接下來的查詢能否成為有用Top－K 數(shù)據(jù)。為了減少感知數(shù)據(jù)的通信能耗，一般情況下Sink 節(jié)點不需要更新過濾器值，只在需要的情況下才去更新過濾器值。當上限值Bt大于上一時刻的Bt－1時，如果某個節(jié)點的數(shù)據(jù)超過了過濾器值時，那么表示該節(jié)點的過濾器值低了，需要將該節(jié)點過濾器設置新的Bt以阻止更多的冗余數(shù)據(jù)，當Bt小于或者等于Bt－1時，則某個節(jié)點的過濾器值可能超過Bt，而Bt是Top－K 結果與非Top－K 結果的分割點，這樣可能會造成Top－K 查詢結果的錯誤，此時應該將可能會出現(xiàn)的節(jié)點的過濾器值設置為Bt，保證Bt仍然是所有節(jié)點過濾器值的上限，保證Top－K結果的正確。最后，把所有需更新的傳感器節(jié)點的過濾器值fn(t)更新為Bt，同時把對應的過濾器值發(fā)送到其對應的節(jié)點當中去。

3 仿真結果與分析

對算法進行仿真參數(shù)如下:傳感器網(wǎng)絡在100 m×100 m的平面下，傳感器網(wǎng)路中傳感器節(jié)點的總數(shù)為100 個，將每個節(jié)點均勻分簇，一共分成10 個簇，每個簇10 個節(jié)點，所有節(jié)點固定就不再移動。網(wǎng)絡中所有傳感器節(jié)點的初始能量相同，且E0=0.5 J，不考慮丟包率和其他因素影響。設每個節(jié)點相隔15 s 記錄一個感知數(shù)據(jù)，傳感器可以存儲最近100 個時間點的感知數(shù)據(jù)，查詢中Kt的一個常數(shù)，以整個傳感器網(wǎng)絡中的所有傳感器節(jié)點發(fā)送和接收感知數(shù)據(jù)包的整體能耗作為Top－K 查詢的評價指標［8］。

簇中節(jié)點發(fā)送到相對應簇的簇頭節(jié)點的感知數(shù)據(jù)含有16 bits 的數(shù)據(jù)值和16 bits 的數(shù)據(jù)ID 身份，而數(shù)據(jù)ID 身份中又含有8 bits 的傳感器節(jié)點ID 身份和8 bits 的時間點?；景l(fā)送給簇頭節(jié)點的探尋包的大小是16 bits，發(fā)送給簇頭節(jié)點更新過濾器包是16 bits。為了與本文算法進行對比，同時仿真了FILA 與TAG 兩種算法并進行對比，如圖1所示。

圖1 網(wǎng)絡分成10 個簇整體能耗實驗結果Fig 1 Experimental results of overall energy consumption while networks is divided into 10 clusters

通過與FILA 和TAG 算法的網(wǎng)絡整體能耗相比的仿真實驗結果可以看出，當K 的取值比較小時，本文算法與FILA算法的網(wǎng)絡整體能耗相差比較小，但是隨著K 值取值越大，算法的網(wǎng)絡整體能耗都在增加，但FILA 算法的整體能耗增加幅度比較大，能耗也較多，本文算法的網(wǎng)絡整體能耗只是在平穩(wěn)的增加，而TAG 算法不管K 值取多大，網(wǎng)絡整體能耗都比較大。通過仿真實驗對比可以看出，運用本文算法的Top－K 數(shù)據(jù)查詢的網(wǎng)絡生命周期會更長。

4 結 論

本文所提出一種基于分簇的無線傳感器網(wǎng)絡的Top－K數(shù)據(jù)查詢算法，通過對無線傳感器網(wǎng)絡節(jié)點進行分簇實現(xiàn)數(shù)據(jù)的傳輸只需要1 跳或2 跳，減少數(shù)據(jù)的傳輸次數(shù)，達到減少通信損耗的目的，然后通過節(jié)點數(shù)據(jù)相互之間的關聯(lián)性對節(jié)點設置過濾器值以降低冗余數(shù)據(jù)的傳遞，通過探尋過程保證Top－K 數(shù)據(jù)查詢的正確性，達到降低無線傳感器網(wǎng)絡的整體能耗的目的，從而延長整個網(wǎng)絡的生命周期。

［1］ Sakai H，Iiyamab S，Tokoc K.Evaluation of water quality and pollution using multichannel sensors［J］.Sensors and Actuators B:Chemical，2000，66:1.

［2］ Silberstein A，Braynard R，Ellis C，et al.A sampling－based approach to optimizing top－k queries in sensor networks［C］∥Proceeding of 22nd International Conference on Data Engineering，USA:IEEE，2006:68.

［3］ Madden S，F(xiàn)ranklin M J，Hellerstein J M，el al.TAG:A tiny aggregation service for Ad Hoc sensor networks［C］∥Proceeding of the Fifth Symp on Operating Systems Design and Implementation，OSDI’02，USA:IEEE，2002:131－146.

［4］ Wu M，Xu J，Tang X，et al.Top－K monitoring in wireless sensor networks［J］.IEEE Trans on Knowledge and Data Engineering，2007，19:962－976.

［5］ Akcan H，Bronnimann H.A new deterministic data aggregation method for WSNs［J］.Signal Processing，2007，87(12):2965－2977.

［6］ 郭書城，盧 昱，許定根.基于分簇無線傳感器網(wǎng)絡的路由算法研究［J］.通信學報，2010，31(8):63－69.

［7］ 韓志杰.一種基于ARMA 的WSNs 非均衡分簇路由算法［J］.電子學報，2010，38(4):865－869.

［8］ Heinzelman W，Chandrakasan A，Balakrishman H.An application－specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.