無線傳感器網絡Top-k多查詢算法*

張曉琳，魏朋佩，唐文斌

(內蒙古科技大學信息工程學院，內蒙古包頭014010)

0 引 言

Top-k查詢技術是能夠提供給用戶最有用的一組數據的查詢處理技術，所以，在無線傳感器網絡中研究比較廣泛。Top-k查詢不難理解就是查找出按照某種要求獲得的最具有代表性的k個數據，然而獲得這些數據的最直接的方法就是遍歷整個網絡的節點。這個時候問題就顯現出來，當僅執行一次查詢的時候，遍歷所有的節點就會消耗很大的能量，一旦多個查詢請求同時發生，就會造成網絡的擁擠等諸多狀況，進而消耗更大的能量，縮短網絡的生命周期。本文針對Top-k多查詢問題進行研究。

1 無線傳感器網絡Top-k查詢

1.1 Top-k 查詢技術

Top-k查詢處理技術是無線傳感器網絡中研究比較廣泛的一種查詢處理技術，在無線傳感器網絡查詢中占有重要的地位。目前主要的Top-k查詢可以分為四類:

1)Top-k查詢基本方法，簡單描述就是首先將查詢Q以洪泛的方法傳送到整個傳感器網絡，然后從每個葉節點開始，由底向上進行數據融合。

2)基于閾值的Top-k查詢處理方法，原理是根據事先查詢的結果設定一個閾值，然后把閾值下發給各個節點，滿足條件的就返回給用戶，結果是經過比較得出的。

3)基于采樣的Top-k查詢處理方法，這種方法主要針對的是連續Top-k查詢問題。通過將查詢轉化為線性規劃問題來對傳輸到上層的節點個數進行優化。

4)基于歷史緩存數據的Top-k查詢處理方法，這種方法以一種基本的查詢在中繼節點產生的緩存數據為基礎，以此來減小后繼查詢產生的代價。

1.2 多查詢技術

文獻［1］提出的ACQUIRE協議適合于解決帶有多個子查詢的復雜查詢。每個收到查詢的節點利用自己的局部信息部分的回答該復雜查詢，節點保存的局部信息包括距離該節點一定跳數范圍內所有節點提供給它的信息。如果查詢得到完整回答，則將結果直接返回Sink節點;否則，當前節點需要選擇下一跳節點以繼續完成剩余的查詢，這種選擇可以隨機進行，也可以選擇一個能最大限度回答剩余查詢的節點。文獻［2］提出對傳感器網絡中的多查詢優化方法，主要包括兩部分:首先在Sink進行優化，對多查詢進行重寫，使公共操作只執行一次;其次是網絡內優化，利用無線信道廣播的特性進行有效的結果回收。

1.3 Top-k 多查詢技術

文獻［3］中提到的切片管理方法進行Top-k查詢在時間窗口上面的劃分。然后下面進行同一個時間窗口切片下的Top-k查詢優化，文獻［4，5，7］中針對多查詢處理提出了兩層的查詢優化架構:基站優化和網內優化。支持對查詢屬性相同但采樣頻率不同的多個查詢 ，其中基站優化的主要思想是使用函數 benef it計算2個查詢合并執行同獨立執行相比較的收益，根據代價模型來衡量能耗，如果2個查詢合并后benef it＞0，則選擇合并查詢:將2個查詢的謂詞條件、選擇屬性列表合并作為新查詢的謂詞條件和選擇屬性，而新查詢的采樣頻率采用原查詢采樣頻率的最大公約數，作者證明了只有當最大公約數等于其中一個查詢的采樣頻率時才適合合并。然而這幾篇文章在重寫查詢時都只考慮了查詢是否可以合并的問題，因此，如果多個查詢中存在不適合合并的請求就會徒勞無功。

根據上述內容和無線傳感器網絡中Top-k查詢本身的特點，針對Top-k多查詢處理提出一種Top-k多查詢算法。針對Top-k查詢應用的特點，對其根據查詢請求的約束條件進行分類，然后針對其中的單條件多查詢一類提出了ETOP算法，它是以單個Top-k查詢的網內處理為基礎，結合基站緩存結果的一種處理方法。ETOP算法不僅減少了傳輸信息量還快速準確地返回給用戶信息，而且，隨著查詢范圍的增加，算法性能變化較小。

2 Top-k多查詢算法

2.1 查詢預處理

下面在無線傳感器網絡中Top-k多查詢請求進入網絡之前進行預處理。根據約束條件的多少進行分類，只有一個約束條件的歸結為一類，有多個約束條件的歸結為一類。這樣一來，在同一個時間段內的進入基站的所有查詢都分成了兩類，就是單約束條件和多約束條件兩類多查詢。

2.2 ETOP 算法

對于單約束條件的多個Top-k查詢，采用一種網內查詢算法和基站緩存數據結合的方法。多個查詢請求的處理是建立在單個的基礎之上的，現有的網內查詢算法當中有TAG和FILA兩種。TAG［6］利用網內數據融合思想減少數據的傳送，得到精確的Top-k查詢結果。采用數據轉發樹方法，將查詢請求沿轉發樹分發到每一個節點，同時在數據沿轉發樹返回過程中，數據轉發節點對收到的數據(包括從子節點傳來的數據)進行聚合處理，只向其父節點發送前k個數據，自底向上，直到Sink節點得到k個數據(查詢結果)。FILA［3］的基礎方法就是用算法過濾器來抑制節點的更新，其中這些節點的數據不可能是Top-k查詢結果的一部分。FILA假設一種特殊的邏輯拓撲，其中根節點可以與節點們直接進行交互(single-hop)，這是非常不現實的。

根據以上文獻分析，針對Top-k多查詢的單約束條件提出一種算法，稱作ETOP算法。在ETOP算法當中，第一個步驟和TAG類似，當第一個查詢的結果出來后，把這個結果的最小值設定為一個閾值，分發到網絡的節點，假定這個值為a，此時網絡中的節點分為2種狀態模式。其間如果節點有更新，那么還會根據他們的模式把更新的值傳遞到基站。把后續查詢條件的最小限定值跟閾值a進行比較，然后進行相應的處理。

3 實驗與結果分析

ETOP算法是一種類似TAG算法的網內處理算法，由Java實現，實驗在Windows XP平臺，主頻2.0GHz奔騰4處理器和512 M內存的配置上進行，采用真實數據集Intel Berkeley Lab 54只傳感器所采集的4000000條數據進行實驗。

通過2個方面對算法進行評估，比較的對象是FILA算法，由于FILA的一些特征假設它具有懶惰的更新策略。一個節點的ID和相應的信息大小是2 byte，FILA的一個過濾器和ETOP算法中閾值a的大小分別為4，2 byte，并且傳輸的每條信息都有一個4 byte大小的包頭。在所有的實驗當中無線傳感器網絡的結構是多跳的。實驗用到的參數如表1所示。

表1 實驗中用的參數Tab 1 Parameter used in the experiment

傳輸消耗是用每一次的查詢當中一個節點的平均傳輸字節來衡量的。ETOP算法的傳輸消耗要明顯比FILA算法小。如圖1所示，隨著第一次查詢k值的增加，傳輸消耗是逐漸降低的，如圖2所示，隨著第一次查詢請求的查詢范圍的增加，消耗的能量有所增加，但是，消耗的能量仍舊在一個較低的水平。總之，ETOP算法相對于FILA算法在傳輸消耗的減少方面已經有了顯著提高。

圖1 傳輸消耗隨k值的變化Fig 1 Transmission cost vs change of k value

圖2 傳輸消耗隨ω值的變化Fig 2 Transmission cost vsωvalue

與此同時，每接收到1 bit都會有一個相應的能量消耗Erx;同樣每傳輸1 bit也會有一個能量消耗Etx。把傳輸的bit數和接收的bit數分別表示為Bt和Br，那么一個節點的能量消耗就表示為BtEtx+BrErx。

如圖3所示，在真實數據的實驗中，ETOP算法表現得更加出色，在能量消耗方面遠小于FILA算法。隨著節點接收與傳輸的比例的遞增，能量消耗的增長并不明顯。

4 結束語

從實驗結果中可以看出:這種類似TAG的 ETOP算法比原來的FILA算法從每個方面來說都有一定的提高。從而能夠更好更高效地執行多查詢處理請求，在快速返回給用戶信息的情況下，進一步減少了網絡的傳輸消耗和能量消耗，從而延長了網絡的生命周期。

圖3 能量消耗隨節點接收與傳輸比例的變化Fig 3 Energy cost change of node’s receiving and transmission ratio

［1］Sadagopan N，Krisnamacari B，Helmy A.Active query forwarding in sensor networks［J］.Journal of Ad Hoc Networks，2005，3(1):91－113.

［2］Xiang SL，Lim H B，Tan K L，et al.Two-tier multiple query optimization for sensor networks［C］∥Proceedings of International Conference on Distributed Computing Systems，2007:39－39.

［3］張 麗，賈 焰，鄒 鵬.一種數據流上的多Top-k查詢資源共享技術研究［J］.計算機研究與發展，2009，46(z1):343－347.

［4］Xiang S，Jim H，Tan K L.Impact of multi-query optimization in sensor networks［C］∥Proceedings of the 3rd Workshop on DMSN，New York，2006:7－12.

［5］Xiang S，Lim H B，Tan K L.Similarity-aware query allocation in sensor networks with multiple base stations［C］∥Proceedings of the 4th Workshop on DMSN，New York，2007:1－6.

［6］Madden S，Franklin M，Hellerstein J，et al.TAG:A tiny aggregation service for Ad Hoc sensor networks［C］∥Proceedings of the 5th Symp on Operating Systems Design and Implementation，Boston，2002:131－146.

［7］Zhang Rui，Shi Jing，Liu Yunzhong，et al.Verifiable fine-grained Top-k queries in tiered sensor networks［C］∥Proceeding of the 2010 IEEE Communications Society，San Diego，CA，INFOCOM，2010:1－9.