利用資料涵蓋觀念解決無線感測網路中之近似查詢處理

Abstract

在這篇論文當中，我們探討的議題是無線感測網路中的近似查詢處理。由於鄰近感測節點的讀數通常具有空間相關性，將這些讀數相近的感測節點聚集成多個叢集，並替每一個叢集選出一個r-node(即叢集代表點)來回答查詢能有效地節省網路的電力消耗。為了解決這個議題，我們提出了一個新的觀念，稱為資料涵蓋。我們首先定義資料涵蓋問題是選擇最少數目的r-node 來完整涵蓋整個網路。接著我們利用將集合涵蓋問題轉換到資料覆蓋問題證明出資料涵蓋問題是一個NP-complete 的問題。因此，我們提出了兩個誘導式演算法DCglobal 和DClocal來解決此問題。我們的第一個演算法DCglobal 是一個集中式的演算法。我們證明了經由DCglobal 得到的解和最佳解之間的誤差是有限的。在執行演算法DCglobal 時消耗的電力相當可觀，因此我們提出了另一個演算法DClocal。DClocal 為一分散式演算法，分別由網路中的各個感測節點執行以選出r-node。同樣的，我們也證明了經由DClocal 得到的解和最佳解之間的誤差是有限的。接著我們討論如何決定演算法DClocal 中所使用的參數的最適值。經由效能評估，我們發現演算法DClocal 比起DCglobal 的確消耗了較少的電力，並且經由和其他的演算法進行比較，演算法DClocal 在網路時間及電力消耗方面的效能都較為優異。因此我們可以歸納我們提出的演算法的確能夠有效地節省電力，並且針對使用者的查詢提供符合使用者所需之精確度的答案。

In this paper, we focus on the issue of approximate query processing in wireless sensor networks. Since there are usually spatial correlations between the readings of sensors in vicinity, it is energy-efficient to group these sensors into clusters and select one r-node, i.e. cluster-head, for each cluster to answer queries. We propose an innovative concept called data-coverage to address the problem. We prove that the data-covering problem which selects minimal number of r-nodes to fully data-cover the whole network is an NP-complete problem by reducing the set-covering problem to our data-covering problem. In order to solve the data-covering problem, we devise two heuristic algorithms DCglobal and DClocal. The first algorithm, DCglobal, is a centralized algorithm executed at the sink. The ratio between the number of r-nodes selected by DCglobal and that of the optimal solution is bounded. Since the energy consumption of DCglobal is extremely high, we devise another algorithm called DClocal. DClocal is a distributed algorithm executed by each sensor to locally select r-nodes. We prove that the ratio between the number of r-nodes selected by DClocal and that of the optimal solution is bounded. We then discuss the optimal value of the parameter used in DClocal. Through the experimental study, it can be seen that the energy consumption of DClocal is less than that of DCglobal. In addition, through comparing with other algorithms, the performance of DClocal is much better in terms of network lifetime and energy consumption. Thus, we conclude that our algorithms are energy-efficient and can provide the users the answers that satisfying their requirements for precision.