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

An Energy and Delay Efficient Scheduling Algorithm for Data-Centric Wireless Sensor Networks

王弘翕(Hung-Shi Wang)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.02991

摘要

無線感測網路是由許多具有感應、計算以及無線通訊能力之感測器所組成的。由於無線感測網路通常是用隨機的方式來撒佈，故為能源即將耗盡的感測器充電是不可行的。因此，如何延長整個網路的系統壽命成為了無線感測網路相關研究中一項非常重要的議題。

本篇論文研究在感測器具有資料集縮能力之無線感測網路中，如該何路由並且排程所有感測器其活動之問題。我們針對了這個問題提出了一個數學模型。並且，更進一步地提出了一個能建立資料集縮樹以及排程無線感測網路中所有感測器其活動之演算法。藉由拉格蘭日鬆弛法，我們可以找到一個近似的最佳解並且驗證我們提出的演算法是否能達到低能耗、資料集縮能力以及保証所產生的延遲會在一個合理的範圍內。

關鍵字

排程 ； 資料集縮,高效率節能 ； 低延遲 ； 資料中心路由 ； 最佳化 ； 拉格蘭日鬆弛法 ； 整數線性規劃 ； 無線感測網路

並列摘要

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.

並列關鍵字

Scheduling ； Data aggregation ； Energy-Efficient ； Delay-Efficient ； Data-centric Routing ； Optimization ； Lagrangean Relaxation Method ； Integer Linear Programming ； Wireless Sensor Network.

參考文獻

[4] T. Dam, and K. Langendoen, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks”, SenSys, 2003, Los Angeles, California.

[5] G. Lu, B. Krishnamachari, and C. Raghavendra, “Delay Efficient Sleep Scheduling in Wireless Sensor Networks”, in 21st Conference of the IEEE Computer and Communications Societies. (INFOCOM 2004)

[6] S. Begum, S. C. Wang, B. Krishnamachari, and A. Helmy, “Energy-efficient and low-latency scheduling technique for wireless sensor networks”, In 21st Conference of the IEEE Computer and Communications Societies. (INFOCOM 2004)

[7] M.L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems”, Management Science, Volume 27, Number 1, pp. 1-18, January 1981.

[8] M.L. Fisher, “An Application Oriented Guide to Lagrangian Relaxation”, Interfaces, Volume 15, Number 2, pp. 10-21, April 1985.