具資料集縮能力無線感測網路之低能耗與延遲排程演算法

Abstract

無線感測網路是由許多具有感應、計算以及無線通訊能力之感測器所組成的。由於無線感測網路通常是用隨機的方式來撒佈，故為能源即將耗盡的感測器充電是不可行的。因此，如何延長整個網路的系統壽命成為了無線感測網路相關研究中一項非常重要的議題。 本篇論文研究在感測器具有資料集縮能力之無線感測網路中，如該何路由並且排程所有感測器其活動之問題。我們針對了這個問題提出了一個數學模型。並且，更進一步地提出了一個能建立資料集縮樹以及排程無線感測網路中所有感測器其活動之演算法。藉由拉格蘭日鬆弛法，我們可以找到一個近似的最佳解並且驗證我們提出的演算法是否能達到低能耗、資料集縮能力以及保証所產生的延遲會在一個合理的範圍內。

Wireless sensor networks (WSNs) consist of a number of small nodes with sensing, computation, and wireless communication abilities. Because of the deployment of sensors would be typically in random fashion. It would not be feasible to recharge the batteries of a moribund sensor. Hence, how to prolong the lifetime becomes a principal issue in wireless sensor networks. In this thesis, we emphasize on a problem of routing and scheduling the activities of all sensors in a data-centric wireless sensor network. We propose a mathematical formulation to model this problem as an integer programming problem, where the objective function is to minimize the total energy consumption, including transmitting, receiving, idling and sleeping. By Lagrangean Relaxation method, we can find a near optimal solution out and verify whether the algorithm we proposed achieves energy efficiency, fulfils data aggregation, and ensures the latency within a reasonable range.