在無線感測網路下建立最大生存時間之資料蒐集多叢樹

Abstract

在無線感測網路下，電源使用效率是個很重要的議題， 特別是在環境監控之類的應用下。 在這種環境下，資料蒐集是最基本的操作，每個感測器會感測環境， 並定期將資料回報給基地台。 樹狀結構的資料蒐集方法常常用來節省電力消耗，以達到延長感測器生存時間。 每個節點會選定一個母節點，並將資料傳送給母節點； 母節點負責從子節點蒐集資料並匯整，以減少不必要的傳輸。

在這篇論文中，我們研究如何在多個基地台下的無線感測網路中建立資料蒐集多叢樹。我們的目標是延長感測網路的生存時間，生存時間定義為感測網路起始後至第一個節點耗盡電力的期間。 這個問題已被證明為NP-complete，因此我們提出了分散式的演算法來有效率地建立資料蒐集多叢樹。為了延長感測網路生存時間，電量較多的節點應該負責支持較多的子節點。 基於這樣的概念，每個節點透過和鄰近節點交換訊息，藉此獲得局部資訊，再經過訊息交換後，每個節點可以透過鄰近節點表來決定母節點。 此外，我們的方法考慮到節點壞掉或者加入的情況；也針對電量快耗盡的節點進行調整，以達到延長生存時間的效果。 最後我們透過數個實驗來驗證方法，實驗結果也顯示我們的方法能有效率地建立資料蒐集多叢樹，並延長感測網路的生存時間。

In wireless sensor networks, energy effciency is a critical issue, especially for applica- tions such as environmental monitoring. Data gathering is the fundamental operation in these applications. It means that sensor nodes sense phenomena, and periodically report the sensed data to the base stations. In order to conserve energy max maximize sensor lifetime, a tree-based data aggregation is often used for collecting data from sensor nodes. Every node determines a parent node to transmit data while a parent node aggregates the data from child nodes to eliminate redundant transmission. In our work, we study the construction of a data aggregation forest where there are several base stations in a sensor network. We aim to prolong the network lifetime of a sensor network while the definition of network lifetime is the time until the first node depletes its energy. The problem is proven to be NP-complete. Hence, we propose a distributed algorithm which constructs a data aggregation forest effciently. To increase the network lifetime, the nodes with more energy should also keep more child nodes. Based on the concept, each node exchanges messages between its neighbor nodes to obtain local information. After the exchange, every node decides a parent node according to its neighbor table. Our solution includes procedure of route maintenance while there is node failure or addition. Moreover, forest adjustment is also adapted to consider the low energy nodes for prolonging the network lifetime. Finally, we evaluate our solution with numerical simulations. The results show that our algorithm can effciently construct a data aggregation forest which prolongs the network lifetime.