鄭州航空工業(yè)管理學(xué)院 程文靜

傳感器網(wǎng)絡(luò)中的多查詢優(yōu)化技術(shù)研究

鄭州航空工業(yè)管理學(xué)院 程文靜

對查詢技術(shù)的研究是傳感器網(wǎng)絡(luò)中的一個重要方面，而查詢優(yōu)化又是提高查詢效率的重要途徑之一。當前對查詢優(yōu)化的研究主要集中在單個查詢應(yīng)用上，對多查詢優(yōu)化的研究并不太多。本文介紹并對比了三種不同的多查詢優(yōu)化技術(shù)CACQ、TTMQO，它們各有特點，并適用于不同的應(yīng)用情境。

傳感器網(wǎng)絡(luò)；多查詢；優(yōu)化

1.研究背景

對傳感器網(wǎng)絡(luò)中的數(shù)據(jù)處理技術(shù)來說，TinyDB和Cougar是最有代表性的兩個系統(tǒng)。然而，它們都只能對單個查詢提供優(yōu)化處理，而針對多個查詢同時發(fā)出請求的狀況時，它們的處理方法是先在基站對每個查詢進行優(yōu)化處理，然后在查詢進入網(wǎng)絡(luò)的同時對相同的傳感器集進行一些批處理。此方法的弊端在于，這兩個系統(tǒng)無法通過共享不同的查詢產(chǎn)生的結(jié)果來分攤數(shù)據(jù)獲取、計算和通信的耗能。另外，運行多查詢會導(dǎo)致帶寬負荷，嚴重的話可能出現(xiàn)通信沖突的話而導(dǎo)致數(shù)據(jù)丟失。因此，對能量受限的傳感器網(wǎng)絡(luò)來說，在查詢處理中引入多查詢優(yōu)化技術(shù)是很必要的。然而，當前這方面的研究還比較少。在本文中，將討論并比較三種典型的多查詢優(yōu)化算法。

2.兩種多查詢優(yōu)化方法

2.1 持續(xù)的自適應(yīng)連續(xù)查詢（C A C Q）

CACQ[1]是一個用于本地查詢處理器的方案，適用于環(huán)境監(jiān)測的傳感器網(wǎng)絡(luò)中。它改進了傳統(tǒng)的連續(xù)查詢設(shè)計，在為查詢工作量的變化提供自適應(yīng)特性時執(zhí)行流處理方式。當一個連續(xù)查詢進入網(wǎng)絡(luò)時，首先在基站由全局查詢操作符對其進行分解，成為一系列子查詢。然后這些子查詢分別被在網(wǎng)內(nèi)廣播，到達相關(guān)的傳感器。在此，流數(shù)據(jù)的掃描、選擇和連接等操作依次被執(zhí)行，產(chǎn)生的部分結(jié)果返回全局查詢處理器。因為連續(xù)查詢方案的基本思想是使單個傳感器上多個相似的查詢共享本地的查詢操作符，所以查詢處理計劃中的常見部分將只被執(zhí)行一次。

CACQ的自適應(yīng)特性體現(xiàn)在當有新查詢產(chǎn)生時，傳感器會改變現(xiàn)有查詢的數(shù)據(jù)傳輸率，另外查詢操作符的執(zhí)行順序也可能改變。自適應(yīng)是通過整合Eddy操作符實現(xiàn)的，Eddy對正在運行的查詢計劃中的查詢操作符進行重新排序，從而實現(xiàn)持續(xù)的自適應(yīng)的查詢處理過程[2]。對于不含連接操作的多查詢，使用單個Eddy來路由所有當前運行的查詢包含的元組。根據(jù)關(guān)系表中對應(yīng)的屬性，多個選擇謂詞被分成若干組，然后對每一個屬性應(yīng)用分組過濾器得到經(jīng)過過濾的元組。考慮如下的三個查詢，它們基于Eddy的查詢結(jié)構(gòu)如圖1所示：

圖1 基于E d d y的持續(xù)查詢結(jié)構(gòu)[1]

三個查詢Q1，Q2和Q3被提交到源節(jié)點S。它們一共包括了在屬性a和b上的六個選擇謂詞s1到s6。Eddy模型對每一個謂詞運用一個過濾操作，即產(chǎn)生了兩個組{s1,s2,s3}和{s4,s5,s6}，當有一個帶有屬性a和b的元組s到達時，Eddy先把a傳給過濾組{s1,s2,s3}，把b傳給過濾組{s4,s5,s6}。在兩個組中分別執(zhí)行相應(yīng)的選擇操作，產(chǎn)生的中間結(jié)果會被傳遞給全局查詢處理器。由于在這種框架中，每個元組只被查看一次，因此，多查詢的執(zhí)行效率顯著提高。

當需要向系統(tǒng)中加入新的查詢Q4時，如果Q4是針對一個新的數(shù)據(jù)源的查詢，Eddy就會實例化一個新的查看器和一組針對Q4的新的過濾器。如果Q4查詢的數(shù)據(jù)仍然是來源于S，那么只需要在已分組的過濾器中的s.a和s.b上加上基于屬性a和b的新的選擇謂詞，或者為其他屬性實例化一個新的分組過濾器。

2.2 對聚集查詢的多查詢優(yōu)化

Trigoni 等人提出的多查詢優(yōu)化技術(shù)是第一個正式考慮傳感器網(wǎng)絡(luò)中的多查詢優(yōu)化的工作[3]。它主要針對空間聚集查詢，發(fā)展了結(jié)果共享和結(jié)果編碼兩項技術(shù)。結(jié)果共享用于多聚集查詢的處理，結(jié)果編碼用于減少查詢更新過程中產(chǎn)生的需要計算的數(shù)據(jù)量。這兩項技術(shù)都能顯著地降低求和、計數(shù)和求平均值這三類查詢的通信消耗。另外，還可以使用一種線性減少算法來降低不規(guī)律的數(shù)據(jù)更新的規(guī)模，使用一種接近最優(yōu)算法來最大程度地減少計算量。

整體來說，為了優(yōu)化聚集查詢，具有相同聚集操作符的查詢被分在一組，通過共享查詢處理過程來降低通信消耗。對長時間運行的查詢來說，每一個時間段被分為兩個步驟：查詢預(yù)處理和結(jié)果傳輸。在此方法中，查詢傳播的成本忽略不計，因為這和持續(xù)查詢過程中用來傳輸結(jié)果的能耗相比是微不足道的。

基于以上思想，此項多查詢優(yōu)化技術(shù)針對的是具有相同聚集操作符的多查詢。這些查詢將一個長方形區(qū)域中的傳感器讀數(shù)進行聚集處理，因此用它們在空間中所處的位置來自我標識。每一查詢被表示成一個含有k個屬性的矢量，其中k是網(wǎng)絡(luò)中的傳感器節(jié)點數(shù)量。為了使用這樣的表示，用戶需要了解網(wǎng)絡(luò)拓撲圖。地理位置上靠近又涉及相似查詢的傳感器被劃進同一類，組成一部分路由樹的分支，由此查詢結(jié)果的消息數(shù)量可以被更好的壓縮，從而有效地降低能耗。

2.3 兩層多查詢優(yōu)化

Xiang等人在[4]中提出了一個兩層多查詢優(yōu)化方案TTMQO。它支持數(shù)據(jù)聚集和數(shù)據(jù)獲取兩類查詢。TTMQO的第一層稱為基站優(yōu)化，它使用基于代價的方法，通過發(fā)掘源查詢中的相似性和減少冗余進行查詢重寫，優(yōu)化后的查詢被投入網(wǎng)絡(luò)；第二層稱為網(wǎng)內(nèi)優(yōu)化，利用無線信道的傳播特性傳輸結(jié)果，并通過恰當?shù)貙?shù)據(jù)獲取和通信安排時間進度來接受相關(guān)查詢的共性分享。

對于基站優(yōu)化，運用了一個代價模型來評估查詢重寫的效益，該模型把傳輸成本作為性能指標。在這個方案里，無線傳輸成本被認為是查詢結(jié)果傳輸?shù)某杀?，因為它在持續(xù)查詢的成本中占據(jù)主體地位。因此，查詢成本可通過以下公式計算：

對于網(wǎng)內(nèi)查詢優(yōu)化，重點在于對多個查詢在時間或空間指標上的結(jié)果共享。首先介紹基于時間的結(jié)果共享方法。對于兩個查詢q1和q2，它們唯一的區(qū)別在于取樣周期不同，它們的優(yōu)化步驟如下：如果q1的取樣周期長度能被q2的整除（4096ms和2048ms），那么q1和q2可以被整合成一個查詢，方式如前文所述，其中結(jié)果的共同部分能被共享。如果q1的取樣周期長度不能被q2的整除（如6144ms和4096ms），那么就無法構(gòu)造有效的合成查詢。然而，q1請求的數(shù)據(jù)中有一半也是q2請求的。

因此研究人員提出了一項對數(shù)據(jù)獲取和傳輸安排時間表的技術(shù)，以此提高兩個查詢的效率。每當一個新的查詢進入網(wǎng)絡(luò)，節(jié)點的時鐘被設(shè)置為所有查詢的時間周期的最大公約數(shù)。另外，一個新查詢的開始時間被設(shè)置為可被時間周期整除的數(shù)。雖然重置開始時間可能導(dǎo)致第一個周期的些許延遲，但是對于長時間持續(xù)查詢來說，沒有太大影響。這樣做的好處在于，能夠大量地節(jié)省能量和帶寬，因為具有相同周期的查詢會在每一周期中的同一時間點開始取樣。

除了基于時間的查詢優(yōu)化，還有基于空間的查詢優(yōu)化方法，其基本思想是使多個查詢共享傳輸。對于聚集查詢來說，一個節(jié)點會優(yōu)先選擇一個和它屬于同一查詢并具有許多滿足條件的數(shù)據(jù)的鄰居節(jié)點作為它的傳輸路徑上的父節(jié)點。由此，一條結(jié)果消息就能由多個不同查詢產(chǎn)生的相同的部分聚集結(jié)果產(chǎn)生。對于采集查詢來說，一個傳感節(jié)點能夠產(chǎn)生一條包含不同查詢所請求的所有屬性的消息。由于傳遞多個小消息比傳遞一個大消息的成本要高，因此消息共享是一個減少網(wǎng)絡(luò)通信量的有效辦法。

實驗結(jié)果表明在多查詢優(yōu)化中，兩層優(yōu)化明顯比單一運用基站優(yōu)化或者網(wǎng)內(nèi)優(yōu)化有效。在兩層結(jié)構(gòu)中，傳輸時間減少了18%，說明網(wǎng)絡(luò)帶寬和能量都被大量地減少了。

結(jié)論

雖然當前對多查詢優(yōu)化的研究并不多，但是這將是未來一個新的研究方向。本文介紹了三種多查詢優(yōu)化技術(shù)，CACQ方法適用于數(shù)據(jù)流形式的查詢，在每個數(shù)據(jù)流上應(yīng)用一個本地查詢處理器；TTMQO結(jié)構(gòu)是一個兩層查詢優(yōu)化器，既適用于獲取型查詢，也適用于聚合查詢；最后一種多查詢優(yōu)化技術(shù)運用了一個線性縮減算法有效地覺少了結(jié)果消息的數(shù)量，適用于基于區(qū)域的聚合查詢。

[1]S．Madden．Continuously adaptive continuous queries over streams． In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp． 49-60, June 2012．

[2]R．Avnur．Eddies：Continuously adaptive query processing．In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp． 261-272, May 2010．

[3]N．Trigoni．Multi-query optimization for sensor networks． In Proceedings of DCOSS,vol． 3560 of Lecture Notes in Computer Science, pp．307-321, 2015．

[4]S．Xiang．Two-tier multiple query optimization for sensor networks．In Proceedings of IEEE International Conference on Distributed Computing Systems, pp．39-47,June 2012．

程文靜（1983-），女，河南新鄉(xiāng)人，碩士，鄭州航空工業(yè)管理學(xué)院講師，研究方向：數(shù)據(jù)知識工程。