王雷春，李艷梅，周國(guó)玉

（湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，湖北 武漢430062）

0 引言

傳感器網(wǎng)絡(luò)（wireless sensor networks，簡(jiǎn)稱WSN）中節(jié)點(diǎn)的能量極其有限，網(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ò)能量、延長(zhǎng)網(wǎng)絡(luò)生命的重要手段.其核心思想是通過網(wǎng)絡(luò)中節(jié)點(diǎn)和匯聚中心對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)進(jìn)行預(yù)處理，以減少網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，從而實(shí)現(xiàn)能量的有效利用.

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

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

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

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

1.1 基本定義

1.1.1 時(shí)間相關(guān)

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

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

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

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

1.1.2 空間相關(guān)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

判定該區(qū)域?yàn)榭臻g相關(guān)區(qū)域.

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

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

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

2 算法描述

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

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

2.1.1 節(jié)點(diǎn)

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

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

3）計(jì)算節(jié)點(diǎn)N在下一時(shí)刻tn＋1預(yù)測(cè)值dp和實(shí)際采樣值dr的差值d′；

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

2.1.2 匯聚中心

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

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

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

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

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

2.2 基于空間相關(guān)的區(qū)域查詢 基于空間相關(guān)的區(qū)域查詢?cè)敿?xì)步驟可描述如下：

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

表1 實(shí)驗(yàn)參數(shù)

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

圖1 算法能量消耗比較

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

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

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

圖3 算法平均查詢時(shí)延比較

圖4 算法平均查詢時(shí)延比較

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

4 結(jié)論

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

［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］.計(jì)算機(jī)學(xué)報(bào)，2010，34（5）：763-778.

［12］潘立強(qiáng)，李建中，駱吉洲.無線傳感器網(wǎng)絡(luò)中一種近似Skyline查詢處理算法［J］.軟件學(xué)報(bào)，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.