基于分簇的無線傳感器網絡Top-K 數據查詢算法

江 欣，李長庚

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

0 引 言

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

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

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

1 網絡分簇

1.1 簇頭選舉

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

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

1.2 簇頭數優化機制

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

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

1.3 成簇機制

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

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

2 算法描述

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

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

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

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

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

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

3 仿真結果與分析

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

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

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

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

4 結 論

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

［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，Franklin 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］ 郭書城，盧 昱，許定根.基于分簇無線傳感器網絡的路由算法研究［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.