瞬變網路環境中的省電式資料管理

Abstract

資料管理系統在瞬變網路環境中(例如行動隨意網路、感知網路、以及車輛網路)往往扮演著重要的角色讓使用者可以藉由詢問來分析或理解現實生活所發生的現象。傳統資料庫中的詢問處理系統可能並不適用於瞬變網路環境，因為此網路的結構高度動態，並且每個節點的能力受限於電力、頻寬、以及運算能力等的限制。本論文探討如何在瞬變網路中有效地達成資料管理。我們從不同的觀點來切入詢問處理的議題，包括詢問處理的演算法、演算法之下的通訊協定、以及前兩者之間的交互影響關係。 K-Nearest Neighbors (KNN)詢問是一個資料管理中廣泛被討論的議題。在瞬變網路中(尤其是行動隨意網路)，如何節省節點的電力消耗是一個重要課題；然而，目前的KNN詢問處理演算法需要不同的索引結構，這些索引的建立以及維護往往需要耗費許多電力，並且導致過長的處理時間，因此這些KNN詢問處理演算法仍不易被實施於瞬變網路中。在第二章，我們提出了一個新的路程式詢問處理演算法：DIKNN。此演算法藉由結合詢問發散以及回覆收集，避免了建立以及維護索引所需要耗費的電力，因此相較於之前的演算法更適用於瞬變網路環境中。 在第三章，我們探討如何在媒體控制管理層節省電力。雖然Quorum-based Power Saving (QPS)通訊協定已經被廣泛的提出並用於隨意網路以增加節點的可用時間；然而，這些協定強制規定每一個節點必須都要用同一個長度的循環規則來作息。由於特定長度的循環規則會同時影響省電的程度以及資料接收的延遲時間，不同的節點往往希望能夠選擇最適合自己長度的循環規則。在現行的QPS通訊協定中循環規則的長度是固定或受限於某些特殊的值(例如質數)，這項限制大大影響了QPS通訊協定的彈性。我們增廣了傳統的Quorum System提出了Hyper Quorum System (HQS)的概念，使得每個節點都可以選擇任意長度的循環規則來作息以達到最適合的省電程度。 基於第二章以及第三章的結果，在第四章我們探討應用層中的詢問處理演算法以及媒體控制管理層中的QPS通訊協定如何交互影響。我們考慮了網路層且在行動隨意網路中相當普及的叢及通訊協定，提出了Asymmetric Cyclic Quorum (ACQ) system。ACQ考慮了媒體控制管理層以上層級的需求與特性，更進一步地節省每個節點的電力。在第五章，我們沿伸ACQ的概念，為車輛網路提出了DSRC-AA省電通訊協定。此通訊協定適用於高度動態並且對資料傳輸延遲容忍度極小的網路環境。 我們實作的模擬實驗顯示：DIKNN，ACQ/DSRC-AA，以及HQS分別可以在應用層、網路層、以及媒體控制管理層達到可觀的省電效果，並且提供可容許的延遲與正確性。

Data management system in transient networks, such as Mobile Ad hoc NETworks (MANETs), sensor networks, and vehicular networks, is essential to allow users to analyze/reason a physical phenomenon by issuing queries. Traditional query processing techniques used by the database systems may not be adequate for transient networks as in these networks, the topology of nodes (or stations) is highly dynamic; and the capability of each node is limited by energy, bandwidth, and computing power. In this dissertation, we study how to achieve energy efficient data management in transient networks. Our study covers different aspects of query processing, including the query processing algorithms, the underlying network protocols to execute the algorithms, and their interworking. The problem finding K-Nearest Neighbors (KNN) is one of the major topic in data management. In transient networks (especially mobile sensor networks), energy conservation should be done along with query processing. Current KNN algorithms require certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In Chapter 2, we propose a novel algorithm called Density-aware Itinerary KNN query processing (DIKNN) that is more suitable for transient networks. DIKNN avoids the cost of index maintenance by combining the query dissemination and response collection in an itinerary. In Chapter 3, we look down to MAC layer to study the energy conservation issue in transient networks. Although Quorum-based Power Saving (QPS) protocols have been proposed for ad hoc networks (e.g., IEEE 802.11 ad hoc mode) to increase energy efficiency and prolong the operational time of mobile stations, these protocols assign to each station a cycle pattern that specifies when the station should wake up (to transmit/receive data) and sleep (to save battery power). In all existing QPS protocols, the cycle length is either identical for all stations or is restricted to certain numbers (e.g. squares or primes). These restrictions on cycle length limit the practical use of QPS protocols in transient networks as each individual station may want to select a cycle length that is best suited for its own need (in terms of remaining battery power, tolerable packet delay, and drop ratio). We propose the notion of Hyper Quorum System (HQS)---a generalization of QPS that allows for arbitrary cycle lengths, and therefore tailorable energy conservation effect on each station. Based on the results in Chapters 2 and 3, in Chapter 4 we investigate how query processing algorithms at Application layer and energy conservation protocols at MAC layer can interwork with each other. We take in to account the clustering techniques at Network layer, which is common in Mobile Ad Hoc Networks (MANETs) to ensure the scalability and efficiency of various communication protocols, and propose an Asymmetric Cyclic Quorum (ACQ) system that is able to give further energy conservation by letting the MAC acknowledge the requirements from upper layers. In Chapter 5, we further extend the concept of ACQ to the vehicular networks and propose DSRC-AA that is suitable for highly dynamic networks requiring very short packet transmission delay. We conduct extensive simulations over our studies. Simulation results show that DIKNN, ACQ/DSRC-AA, and HQS can achieve significant improvement in energy conservation at Application, Network, and MAC layers respectively in handling queries while preserving user-tolerable latency and query result accuracy.