Sharing Aggregate Computations for Processing Multiple Regional Queries in Sensor Networks

在無線感測網路中分享聚合式計算以處理多重區域性查詢

趙皎宏(Chiao-Hung Chao)

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2008年)

摘要

當感測器系統朝向大規模佈置與發展時，可以想見的，感測器系統的使用將面臨可擴充性的挑戰：如何同時服務多個感測器資料收集任務且能使感測器系統的使用效能不會有明顯的下降。我們認為在存在大量感測器資料收集任務的環境中，系統資源不足是根本的問題。但是我們發現，在實際應用中，多個感測器資料收集任務雖然彼此相異，如不同資料收集區域、不同資料選擇條件、不同的感測器感測週期，但是彼此間仍多有互相包含互相重疊的關係，因此若我們能找出多個感測器資料收集任務相重疊的部份並分享資料收集結果，將有助於提昇感測器系統資源的利用率。
舉例來說，假設城市中大規模地佈置了各式各樣的感測器系統，在這樣的環境下，不同的使用者將會下達不同的查詢，例如某使用者甲想要監控市區降雨的狀況，而使用者乙則想要監控與市區相鄰的山區降雨的狀況，因此在這個例子中，系統上便同時存在著兩個感測器資料收集任務。雖然這兩個資料收集任務各需求不同的區域及收集條件，但是這兩個感測資料收集任務中，有些部分是重疊在一起的，若我們能重複地利用該重疊區域所收集的資料，相信可大幅增加感測器系統利用的可擴充性。因此本研究將致力於盡可能的利用多個感測器資料收集任務中任務重疊範圍的部分，來降低整個感測器系統的總收集任務執行成本，以俾延長感測器系統的使用期限。

關鍵字

無線感測器

並列摘要

Sensor networks have received considerable attention in recent years, and are often employed in the applications where data are difficult or expensive to collect. One of the features for wireless sensor networks is resource limitations. Sensor nodes typically are limited in computing power, network bandwidth, storage capability, and energy supply. Resource conservation therefore becomes a major consideration when devising sensor applications.

With the continuous development of sensor network technology, we can imagine that in the near future the sensor network must be of a large scale and the service oriented applications. In such environment, hundreds of queries can be presented. Multi-query optimizations become important for efficient query processing. The previous multi-query optimization works only consider multiple aggregate queries with different predicates. In this thesis, we present techniques to extend the previous multi-query optimization strategies by further considering different query regions. We process the queries by considering the spatial relationship of all query regions. Strategies for exploiting the properties of overlapped regions to obtain a better solution are developed.

Moreover, extensive experiments are made to demonstrate the efficiency of the proposed optimization techniques.

並列關鍵字

sensor

參考文獻

[3] Niki Trigoni, Alexandre Guitton, and Antonios Skordylis. Routing and Processing Multiple Aggregate Queries in Sensor Networks. In Proc. of Intl. Conf. on Embedded Networked Sensor Systems, 2006

[4] Xiaoyan Yang, Hock Beng Lim, M. Tamer Ozsu, and Kian Lee Tan. In-Network Execution of Monitoring Queries in Sensor Networks. In Proc. of the ACM SIGMOD Conf. on Management of Data, 2007

[5] Adam Silbersten and Jun Yang. Many-to-Many Aggregation for Sensor Networks. In Proc. of the IEEE Conf. on Data Engineering, 2007

[7] Sailesh Krishnamurthy, Chung Wu, Michael J. Franklin. On-the-Fly Sharing for Streamed Aggregation. In Proc. of the ACM SIGMOD Conf. on Management of Data, 2006

[9] Samuel R. Madden, and Wei Hong. TinyDB: An Acquisitional Query Processing System for Sensor Neworks. In ACM Transactions on Database Systems.