無線傳感器網(wǎng)絡Top-k多查詢算法*

張曉琳，魏朋佩，唐文斌

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

0 引 言

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

1 無線傳感器網(wǎng)絡Top-k查詢

1.1 Top-k 查詢技術

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

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

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

3)基于采樣的Top-k查詢處理方法，這種方法主要針對的是連續(xù)Top-k查詢問題。通過將查詢轉化為線性規(guī)劃問題來對傳輸?shù)缴蠈拥墓?jié)點個數(shù)進行優(yōu)化。

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

1.2 多查詢技術

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

1.3 Top-k 多查詢技術

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

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

2 Top-k多查詢算法

2.1 查詢預處理

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

2.2 ETOP 算法

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

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

3 實驗與結果分析

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

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

表1 實驗中用的參數(shù)Tab 1 Parameter used in the experiment

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

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

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

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

如圖3所示，在真實數(shù)據(jù)的實驗中，ETOP算法表現(xiàn)得更加出色，在能量消耗方面遠小于FILA算法。隨著節(jié)點接收與傳輸?shù)谋壤倪f增，能量消耗的增長并不明顯。

4 結束語

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

圖3 能量消耗隨節(jié)點接收與傳輸比例的變化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］張 麗，賈 焰，鄒 鵬.一種數(shù)據(jù)流上的多Top-k查詢資源共享技術研究［J］.計算機研究與發(fā)展，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，F(xiàn)ranklin 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.