基于時空相關(guān)的傳感器網(wǎng)絡(luò)匯聚查詢算法

王雷春，李艷梅，周國玉

（湖北大學計算機與信息工程學院，湖北 武漢430062）

0 引言

傳感器網(wǎng)絡(luò)（wireless sensor networks，簡稱WSN）中節(jié)點的能量極其有限，網(wǎng)絡(luò)中的傳感器由于電源能量的原因經(jīng)常失效或廢棄.如何在網(wǎng)絡(luò)工作過程中節(jié)省能源，最大化網(wǎng)絡(luò)的生命周期，是傳感器網(wǎng)絡(luò)研究所面臨的重要挑戰(zhàn).

在傳感器網(wǎng)絡(luò)中，能量消耗的大部分來自網(wǎng)絡(luò)中數(shù)據(jù)傳輸.因此，減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量成為節(jié)省網(wǎng)絡(luò)能量、延長網(wǎng)絡(luò)生命的重要手段.其核心思想是通過網(wǎng)絡(luò)中節(jié)點和匯聚中心對網(wǎng)絡(luò)中的數(shù)據(jù)進行預處理，以減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，從而實現(xiàn)能量的有效利用.

文獻［1-2］中采用基于路線的數(shù)據(jù)收集算法處理K近鄰查詢，以獲得距離某位置最近的K個節(jié)點的感知數(shù)據(jù).Cheng等［3］利用采樣技術(shù)減少參與查詢處理的節(jié)點數(shù)目，通過設(shè)置合理的采樣概率保證查詢結(jié)果質(zhì)量滿足精度要求的同時盡量降低能耗.文獻［4-7］中研究了連續(xù)近似聚集查詢，利用節(jié)點感知數(shù)據(jù)具有時間相關(guān)性減少相似感知數(shù)據(jù)的發(fā)送.文獻［8］中利用節(jié)點感知數(shù)據(jù)具有時間相關(guān)特性，提出了一種自適應(yīng)設(shè)置節(jié)點誤差配額的算法，降低網(wǎng)絡(luò)中的數(shù)據(jù)通信量.文獻［9-10］中提出了采用多條數(shù)據(jù)收集路線的并行K近鄰查詢處理算法DIKNN和PCIKNN，利用多條路線并行執(zhí)行以減少時間延遲和能量消耗.文獻［11］中設(shè)計了一種利用節(jié)點冗余保證查詢處理過程魯棒性的算法ESA，避免了因節(jié)點失效而中斷，減少簇頭節(jié)點收集其鄰居節(jié)點感知數(shù)據(jù)的能耗.潘立強等［12］提出了一種近似Skyline查詢處理算法，在滿足用戶查詢需求的前提下最大化地節(jié)省能量.

上述算法在一定程度上減少了網(wǎng)絡(luò)中節(jié)點數(shù)據(jù)查詢的效率，降低了網(wǎng)絡(luò)中的能量消耗，但也存在不足.如文獻［4-8］中只考慮了節(jié)點感知數(shù)據(jù)具有的時間相關(guān)性，文獻［11］中則只考慮了節(jié)點和鄰居節(jié)點之間的數(shù)據(jù)空間相關(guān)性，因此數(shù)據(jù)查詢效率都不高.另外，這些算法大多來自于傳統(tǒng)數(shù)據(jù)查詢算法的改進，在處理器、存儲和通信能力方面要求較高，并不適合在資源、能量等方面嚴重受限的傳感器網(wǎng)絡(luò).

本文中提出一種基于時空相關(guān)的匯聚查詢算法STCAQ.STCAQ通過傳感器網(wǎng)絡(luò)中節(jié)點采樣數(shù)據(jù)的時空相關(guān)性，對節(jié)點和空間區(qū)域的數(shù)據(jù)進行匯聚查詢，以減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，提高網(wǎng)絡(luò)生命.STCAQ借鑒了上述文獻的優(yōu)點并進行了改進：1）當節(jié)點采樣數(shù)據(jù)實際值和預測值在規(guī)定范圍內(nèi)時，匯聚中心只保存節(jié)點的預測值；2）空間區(qū)域在某一時刻的查詢數(shù)據(jù)通過基于空間相關(guān)的判定算法求得.通過以上改進，STCAQ可以在極大地減少網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量的同時提高數(shù)據(jù)查詢成功率和查詢質(zhì)量.

1 時空相關(guān)理論

1.1 基本定義

1.1.1 時間相關(guān)

定義1 節(jié)點采樣數(shù)據(jù)時間相關(guān).在傳感器網(wǎng)絡(luò)中，同一節(jié)點在相近時間采樣數(shù)據(jù)所表現(xiàn)出來的相似性.

判定方法1 節(jié)點采樣數(shù)據(jù)時間相關(guān)判定.假定節(jié)點在連續(xù)時間范圍（t1，t2，…，tn）采樣數(shù)據(jù)為ψt＝（d1，d2，…，dn），在時刻tn＋1采樣數(shù)據(jù)為dn＋1，dθ為預先規(guī)定的閾值.如果

1）di和dj間相關(guān)（i，j∈｛1，2，…，n｝）；

2）｜dn＋1-di｜＜dθ（i＝1，2，…，n）；則dn＋1和ψ時間相關(guān).

1.1.2 空間相關(guān)

定義2 節(jié)點空間相關(guān).監(jiān)測同一區(qū)域不同節(jié)點采樣數(shù)據(jù)所表現(xiàn)出來的相似性.

定義3 空間讀向量.傳感器網(wǎng)絡(luò)中節(jié)點Ni的空間讀向量由一個滑動窗口Δt內(nèi)的一系列讀數(shù)組成.Ni的讀數(shù)可表示為

其中xi（t）表示節(jié)點Ni在t時刻的采樣數(shù)據(jù)值.

定義4 空間讀向量相似度.兩個節(jié)點空間讀向量之間的相似程度.

兩個節(jié)點和之間的空間讀向量相似度SNi，Nj表示為：

這里，vi（t）和vj（t）分別是節(jié)點Ni和Nj的空間讀向量，SNi，Nj∈［0，1］.

判定方法2 節(jié)點空間相關(guān)判定.兩個節(jié)點是空間相關(guān)的當且僅當SNi，Nj∈Sθ，其中Sθ是預先給定的空間讀向量相似度閾值.

1.2 基于時間相關(guān)的節(jié)點采樣數(shù)據(jù)預測 假定傳感器節(jié)點在連續(xù)時間范圍內(nèi)（t1，t2，…，tn）的采樣值為ψt＝（d1，d2，…，dn），在第tn＋1時刻的采樣值為dn＋1和ψt時間相關(guān)，則dn＋1可通過公式計算：

其中，α1，α2，…，αn為預測系數(shù)，其取值遵循時間相關(guān)規(guī)律，即離預測值越近的取值越大，反之越小.在本文中，考慮到節(jié)點采樣的頻率及其時間相關(guān)特點，α1，α2，…，αn取值為αi＝2i（i＝1，2，…，n）.

在STCAQ中，網(wǎng)絡(luò)中的每個節(jié)點和匯聚中心都按照上述公式對下一時刻的節(jié)點采樣值進行預測，但節(jié)點是根據(jù)該節(jié)點實際歷史采樣數(shù)據(jù)值對下一時刻的采樣值進行預測，匯聚中心根據(jù)保存在數(shù)據(jù)庫中的數(shù)據(jù)對下一時刻的采樣值進行預測.

1.3 基于空間相關(guān)的區(qū)域判定

定義5 空間相關(guān)區(qū)域.指定空間范圍內(nèi)任意兩個節(jié)點均空間相關(guān)的區(qū)域.

顯然，如果查詢區(qū)域不是空間相關(guān)區(qū)域，說明該查詢區(qū)域內(nèi)節(jié)點采樣值差異較大，查詢得到的結(jié)果不能反映該查詢區(qū)域的真實狀況，也是沒有意義的.因此，本文中所指的查詢區(qū)域均是空間相關(guān)區(qū)域.判定方法3（空間相關(guān)區(qū)域判定）假定指定空間區(qū)域有n個節(jié)點，如果該空間區(qū)域滿足下條件：

1）通過判定方法2確定在該空間區(qū)域范圍內(nèi)與節(jié)點Ni（i＝1，2，…，n）空間相關(guān)的節(jié)點集為ψNi；

2）ψ＝ψN1∩ψN2∩…∩ψNn；

3）ψ≠φ；（φ為空集）

判定該區(qū)域為空間相關(guān)區(qū)域.

如果通過上述判定方法得到的ψ是一空的節(jié)點集，說明選擇的查詢區(qū)域節(jié)點采樣數(shù)據(jù)差異較大，需要重新確定查詢區(qū)域的物理范圍.

定義6 空間相關(guān)區(qū)域質(zhì)心.空間相關(guān)區(qū)域質(zhì)心G（t，x，y，d）定義為該空間區(qū)域的重心.

假定一個空間相關(guān)區(qū)域包括n個節(jié)點，節(jié)點Ni的空間位置為（xi，yi），在時刻ti的采樣值為di，則空間相關(guān)區(qū)域質(zhì)心G（ti，xi，yi，di）可計算為：

2 算法描述

STCAQ包括兩部分：基于時間相關(guān)預測的節(jié)點采樣數(shù)據(jù)匯聚；基于空間相關(guān)的區(qū)域查詢.前者對傳感器網(wǎng)絡(luò)中的節(jié)點采樣數(shù)據(jù)進行基于時間相關(guān)的預測匯聚，并將結(jié)果保存在匯聚中心的數(shù)據(jù)庫中；后者用于查詢指定區(qū)域范圍的信息.

2.1 基于時間相關(guān)預測的節(jié)點采樣數(shù)據(jù)匯聚 基于時間相關(guān)預測的節(jié)點采樣數(shù)據(jù)匯聚由傳感器網(wǎng)絡(luò)中的節(jié)點和匯聚中心共同完成.詳細步驟描述如下：

2.1.1 節(jié)點

1）獲取節(jié)點N在時間范圍（t1，t2，…，tn）數(shù)據(jù)ψt＝（d1，d2，…，dn）；

2）按照公式（2）計算節(jié)點N在下一時刻tn＋1的數(shù)據(jù)預測值dp；

3）計算節(jié)點N在下一時刻tn＋1預測值dp和實際采樣值dr的差值d′；

4）如果d′大于預先規(guī)定的閾值dΔ，向匯聚中心發(fā)送dr；否則，不向匯聚中心發(fā)送.上述步驟在簇形成后在各個節(jié)點內(nèi)部反復執(zhí)行，直到新簇產(chǎn)生.

2.1.2 匯聚中心

1）獲取任一節(jié)點Ni在時間范圍（t1，t2，…，tn）數(shù)據(jù)ψt＝（d1，d2，…，dn）；

2）按照公式（2）計算節(jié)點N在下一時刻tn＋1的數(shù)據(jù)預測值dp；

3）將節(jié)點Ni在下一時刻tn＋1的數(shù)據(jù)預測值dp存入數(shù)據(jù)庫；

4）等待一定延時：如果接收到節(jié)點發(fā)送的實際采樣數(shù)據(jù)值dr，對數(shù)據(jù)庫中的節(jié)點在該時刻的預測值進行更新；否則，不更新.

匯聚中心反復執(zhí)行上述步驟，直到網(wǎng)絡(luò)生命終止.

2.2 基于空間相關(guān)的區(qū)域查詢 基于空間相關(guān)的區(qū)域查詢詳細步驟可描述如下：

1）指定要查詢區(qū)域Area的空間范圍和查詢時刻ti；

2）根據(jù)給定Area的范圍，查詢所有在Area區(qū)范圍的節(jié)點；

3）根據(jù)判定方法1），計算這個空間區(qū)域所有空間相關(guān)的節(jié)點集ζnode；

4）如果ζnode＝φ，轉(zhuǎn)到步驟1）；否則，轉(zhuǎn)到下一步；

5）按照公式3）計算Area的質(zhì)心G（ti，xi，yi，di），即為Area的查詢值.

指定空間區(qū)域查詢結(jié)果與空間區(qū)域的選擇有關(guān).空間區(qū)域中相關(guān)節(jié)點數(shù)越多，相關(guān)度越大，結(jié)果越精確；反之，結(jié)果越難反映空間區(qū)域的查詢結(jié)果.

3 實驗結(jié)果分析

為了評價算法的性能，在文獻［13］中的模擬器上實現(xiàn)了算法STCAQ和ESA［11］，并對兩種算法在能量消耗、查詢成功率和查詢質(zhì)量等方面的性能進行了比較.實驗的硬件環(huán)境為雙核Intel CPUP4（2×2.1 GHz），2 048MB內(nèi)存；軟件環(huán)境為Ubuntu操作系統(tǒng)、Eclipse開發(fā)工具.

根據(jù)文獻［14］，無線通信電路發(fā)送和接收1Byte的能量消耗公式為Et＝α＋γ×dn，Eγ＝β.其中α為通信發(fā)送電路消耗的能量，γ為傳輸放大器消耗的能量，d為傳

輸距離；n為路徑損失因子（path loss factor），β為通信接收電路消耗的能量.采用文獻［13］中的參數(shù)：α＝45nJ／bit，γ＝10pJ／bit／m2，β＝135nJ／bit，e＝2.其他參數(shù)如表1所示.

表1 實驗參數(shù)

3.1 能量消耗比較 圖1顯示了失效節(jié)點數(shù)目對能量消耗的影響.對于其他算法，隨著失效節(jié)點數(shù)目的增大，查詢處理過程因查詢節(jié)點失效而中斷的概率增大，為了獲得正確的查詢結(jié)果，算法需要反復重新執(zhí)行，帶來了大量的能量消耗.而STCAQ算法基于時空相關(guān)的預測查詢算法，在沒有節(jié)點有異常情況時，不需要向簇頭發(fā)送查詢處理數(shù)據(jù)，因而極大減少了網(wǎng)絡(luò)中的能量消耗.

圖1 算法能量消耗比較

3.2 查詢成功率和查詢質(zhì)量比較 圖2顯示了網(wǎng)絡(luò)失效節(jié)點數(shù)目對查詢成功率的影響.由圖2可知，隨著網(wǎng)絡(luò)中節(jié)點失效數(shù)目的增加，兩種算法的查詢成功率和查詢質(zhì)量均逐漸降低；與ESA算法相比，STCAQ算法的查詢成功率和查詢質(zhì)量下降較為緩慢.這是因為網(wǎng)絡(luò)中失效節(jié)點數(shù)的增加，影響了查詢的成功，導致查詢成功率和查詢質(zhì)量下降；而STCAQ算法的查詢區(qū)域基于空間相關(guān)，區(qū)域查詢的結(jié)果可由區(qū)域中空間相關(guān)的節(jié)點計算得到，受網(wǎng)絡(luò)中失效節(jié)點影響較小.

圖2 算法查詢成功率和查詢質(zhì)量比較

3.3 網(wǎng)絡(luò)數(shù)據(jù)傳輸量比較 圖3顯示了不同算法隨著網(wǎng)絡(luò)生命變化時的網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量.由圖可知，隨著網(wǎng)絡(luò)生命的減少，幾種算法的網(wǎng)絡(luò)數(shù)據(jù)傳輸量都在減少，而STCAQ算法減少最為緩慢.這是因為，隨著網(wǎng)絡(luò)生命減少，網(wǎng)絡(luò)中有效工作的節(jié)點數(shù)目減少，因而減少了查詢時網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量.STCAQ算法在正常情況下，是進行預測查詢，只在有異常情況時才進行數(shù)據(jù)傳輸，因而減少緩慢.

圖3 算法平均查詢時延比較

圖4 算法平均查詢時延比較

3.4 查詢時延比較 圖4顯示了網(wǎng)絡(luò)中活躍節(jié)點數(shù)目減少對算法查詢延時的影響.由圖4可知，隨著網(wǎng)絡(luò)中活躍節(jié)點減少，ESA算法的查詢延時也減少，STCAQ算法查詢延時基本不變.在ESA算法中，隨著網(wǎng)絡(luò)中活躍節(jié)點減少，節(jié)點處理和傳播的時延也減少，降低了算法的查詢時延.STCAQ算法在正常情況下是預測查詢，只在有異常情況時才進行數(shù)據(jù)傳輸，因而查詢時延變化較小.

4 結(jié)論

提出一種基于時空相關(guān)的傳感器網(wǎng)絡(luò)匯聚查詢算法STCAQ.STCAQ依據(jù)網(wǎng)絡(luò)中節(jié)點采樣數(shù)據(jù)的時空相關(guān)性，分別提出基于時間相關(guān)的節(jié)點預測算法和基于空間相關(guān)的空間相關(guān)區(qū)域查詢算法.仿真實驗表明，與ESA算法相比，STCAQ在保持較高的查詢成功率和查詢質(zhì)量的同時，減少網(wǎng)絡(luò)數(shù)據(jù)通信量，節(jié)省了網(wǎng)絡(luò)能量.下一步的工作是在真實的環(huán)境中實現(xiàn)STCAQ，進一步對其進行驗證和改進.

［1］Wu Shanhung，Chuang Kunta，Chen Chungmin，et al.Toward the optimal itinerary-based KNN query processing in mobile sensor networks［J］.IEEE Transact ions on Know ledge and Data Engineering，2008，20（12）：1655-1668.

［2］Fu Taoyang，Peng Wenchih，Lee Wangchien.Parallelizing itinerary-based KNN query processing in wireless sensor networks［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22（5）：711-729.

［3］Cheng Siyao，Li Jianzhong，Ren Qianqian，et al.Bernoulli sampling based（epsilon，delta）-approximate aggregation in larger-scale sensor networks［C］／／Proceedings of the 29th IEEE International Conference on Computer Communications.San Diego，2010：1181-1189.

［4］Jain N，Yal agandula P，Dahlin M，et al.STAR：Self-tuning aggregation for scalable monitoring［C］／／Proceedings of the 33rd International Conference on Very Large Data Bases，Vienna，2007：962-973.

［5］Tang Xueyan，Xu Jianliang.Adaptive data collect ion strategies for lifetime-constrained wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（6）：721-734.

［6］Tang Xueyan，Xu Jianliang.Optimizing lifetime for continuous data aggregation with precision guarantees in wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2008，16（4）：904-917.

［7］Chen Baichen，Liang Weifa，Zhou Rui，et al.Energy-efficient top k-query process in wireless sensor networks［C］／／Proceedings of the 19th ACM Conference on Information andKnowledge Management.Toronto，2010：329-338.

［8］Jain N，Yalagandula P，Michael Dahlin，et al.Self-tuning bandwidth-aware monitoring for dynamic data streams［A］.Proceedings of the 22nd International Conference on Data Engineering［C］／／IEEE Computer Society，Washington，2009：114-125.

［9］YAO Y X，TANG X Y，LIM E P.Localized monitoring of KNN queries in wireless sensor networks［J］.The Very Large Database Journal，2009，18（1）：99-117.

［10］WU S H，CHUANG K T，CHEN C M，et al.Toward the optimal itinerary-based KNN query processing in mobile sensor networks［J］.IEEE Transactions on Knowledge and Data Engineering，2008，20（12）：1655-1668.

［11］劉亮，秦小麟，鄭桂能，等.能量高效的無線傳感器網(wǎng)絡(luò)空間范圍查詢處理算法［J］.計算機學報，2010，34（5）：763-778.

［12］潘立強，李建中，駱吉洲.無線傳感器網(wǎng)絡(luò)中一種近似Skyline查詢處理算法［J］.軟件學報，2010，21（5）：1020-1030.

［13］COMAN A，SANDER J，NASCIMENTO M A.Adaptive processing of historical spatial range queries in peer-to-peer sensor networks［J］.Distributed and Parallel Databases，2007，22（2／3）：133-163.

［14］RAPPAPORT T.Wireless communications：principles and practice［M］.New Jersey：Prentice-Hall Press，1996.