在感測網路中針對多個網路中彙整的查詢做最佳化來節省電量

Abstract

在無線感測網路的監測應用中，查詢常常是長時間執行在特定週期當中。由於每個查詢是單獨的被處理，當查詢的數目增加時無線感測網路所耗費的能量是可觀的。在這篇論文當中，我們探討在多個查詢間分享他們的中繼資料來降低整體耗費的訊息的方式中所具有的特性。分享自身資料的查詢被稱為骨幹。給定一些查詢，我們要決定可以使訊息傳輸數量降至最低的那些查詢當做骨幹。更精確的說，我們首先將選擇骨幹的問題以數學的形式做正規的描述並將他轉換成Max-cut的問題。具體來說，給定一些查詢，我們從它們衍生出一個圖，其上的每一點是代表一個查詢，而相對的邊以及權重則代表經由分享中繼資料可以節省多少數量的訊息。根據衍生出來的圖，我們設計一個經由觀察而設計的演算法SB（全名為Selecting Backbones）去在圖上切分來決定骨幹。為了評估演算法SB所得到的結果，我們設計了一個演算法OOB（全名為Obtaining Optimal Backbones）來得到最佳解。這些演算法的效能被相互比較，以及分析它們對環境參數的敏感度，如查詢的數量以及查詢資料來源的分布等等。由實驗結果可得知，藉由分享中繼資料，演算法SB大幅度降低了所需耗費的訊息數量，因此解省了可觀的能源。

In monitoring applications of wireless sensor networks, queries are typically long-running and executed over a specified period. Since each query is independently performed, wireless sensor networks consume a considerable amount of energy when the number of queries increases. In this paper, we explore the feature of sharing partial results of multiple queries so as to reduce the total number of messages incurred. Those queries sharing their partial results are referred to backbones. Given a set of queries, we shall determine backbones with the purpose of minimizing the total number of messages. Explicitly, we first formulate the problem of selecting backbones and transform this problem into Max-Cut problem. Specifically, given a set of queries, we derive a graph, where each vertex represents one query and the corresponding weight edge denotes the number of messages reduced by sharing the partial results. According to the graph derived, we develop a heuristic algorithm SB (standing for Selecting Backbones) to derive a cut in which both backbones and non-backbones are determined. In order to evaluate the solution quality obtained by algorithm SB and compare its resulting backbone set with the optimal one, we devise an algorithm OOB (standing for Obtaining Optimal Backbones) to obtain the optimal solution. Performance of these algorithms is comparatively analyzed and sensitivity analysis on several parameters, including the number of queries and the distribution of data sources for queries, is conducted. It is shown by our simulation results that by sharing the partial results, algorithm SB is able to significantly reduce the total number of messages, thereby saving a considerable amount of energy.