Abstract
在許多應用中，匯點會定期的蒐集來自感測器的資料。因為這種資料蒐集的動作通常會持續許多回合，所以有效率的蒐集這些資料－也就是減少傳輸資料的所需的能量，是很重要的。在這類應用中，為了減少維護路由表所需的計算資源，樹通常會做為一種路由架構。在這篇論文中，我們會研究如何建構一個消耗最少能量的資料集結樹。此外，我們還研究了這個問題在無線感測網路出現中繼點的情形。我們證明了這兩個問題都是NP-complete，而且針對這兩個問題各自提出了O(1)的近似演算法。實驗證明了我們提出的方法在降低消耗能源上有很好的效果。