王雷春，李艷梅，周國玉

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

0 引言

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

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

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

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

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

1 時空相關理論

1.1 基本定義

1.1.1 時間相關

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

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

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

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

1.1.2 空間相關

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法描述

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

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

2.1.1 節(jié)點

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

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

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

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

2.1.2 匯聚中心

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

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

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

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

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

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

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

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

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

4）如果ζnode＝φ，轉到步驟1）；否則，轉到下一步；

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

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

3 實驗結果分析

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

根據文獻［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é)點失效而中斷的概率增大，為了獲得正確的查詢結果，算法需要反復重新執(zhí)行，帶來了大量的能量消耗.而STCAQ算法基于時空相關的預測查詢算法，在沒有節(jié)點有異常情況時，不需要向簇頭發(fā)送查詢處理數(shù)據，因而極大減少了網絡中的能量消耗.

圖1 算法能量消耗比較

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

圖2 算法查詢成功率和查詢質量比較

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

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

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

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

4 結論

提出一種基于時空相關的傳感器網絡匯聚查詢算法STCAQ.STCAQ依據網絡中節(jié)點采樣數(shù)據的時空相關性，分別提出基于時間相關的節(jié)點預測算法和基于空間相關的空間相關區(qū)域查詢算法.仿真實驗表明，與ESA算法相比，STCAQ在保持較高的查詢成功率和查詢質量的同時，減少網絡數(shù)據通信量，節(jié)省了網絡能量.下一步的工作是在真實的環(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］劉亮，秦小麟，鄭桂能，等.能量高效的無線傳感器網絡空間范圍查詢處理算法［J］.計算機學報，2010，34（5）：763-778.

［12］潘立強，李建中，駱吉洲.無線傳感器網絡中一種近似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.