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

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

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

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

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

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

1.研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)于基站優(yōu)化，運(yùn)用了一個(gè)代價(jià)模型來評(píng)估查詢重寫的效益，該模型把傳輸成本作為性能指標(biāo)。在這個(gè)方案里，無線傳輸成本被認(rèn)為是查詢結(jié)果傳輸?shù)某杀荆驗(yàn)樗诔掷m(xù)查詢的成本中占據(jù)主體地位。因此，查詢成本可通過以下公式計(jì)算：

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

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

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

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

結(jié)論

雖然當(dāng)前對(duì)多查詢優(yōu)化的研究并不多，但是這將是未來一個(gè)新的研究方向。本文介紹了三種多查詢優(yōu)化技術(shù)，CACQ方法適用于數(shù)據(jù)流形式的查詢，在每個(gè)數(shù)據(jù)流上應(yīng)用一個(gè)本地查詢處理器；TTMQO結(jié)構(gòu)是一個(gè)兩層查詢優(yōu)化器，既適用于獲取型查詢，也適用于聚合查詢；最后一種多查詢優(yōu)化技術(shù)運(yùn)用了一個(gè)線性縮減算法有效地覺少了結(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ù)知識(shí)工程。