無線感應器網路系統生存時間最大化之高效能路由演算法

An Energy-efficient Routing Algorithm for the Maximization of System Lifetime in Wireless Sensor Networks

葉耿宏(Keng-Hung Yeh)

指導教授 ： 林永松

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

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

摘要

無線感應器網路是近年來相當熱門的研究主題。由於感應器技術的進步，促成了無線感應器網路快速蓬勃的發展。無線感應器網路可以被廣泛的使用在許多不同領域的應用上，例如：衛生醫療、軍事國防、環境偵測等等。雖然無線感應器網路能夠提供許多有價值的應用，但同時，

關鍵字

拉格蘭日鬆弛法 ； 高效能 ； 最佳化 ； 路由演算法 ； 數學規劃 ； 無線感應器網路

並列摘要

The wireless sensor network has become a popular research topic in recent years. Advances in sensor node technology have enabled the rapid development of wireless sensor networks that can be used in various application areas, such as healthcare, the military, and the environment. Although there are many invaluable applications for wireless sensor networks, there are also a lot of emerging problems and challenges that need to be solved, at the same time. The biggest problem is how to efficiently use energy resources to prolong the overall system lifetime of such highly energy-constrained wireless sensor networks.

Our solution to this problem is to design an energy-efficient routing algorithm. We use a mathematical programming technique to formulate the issue as a combinatorial optimization problem, where the objective function is to maximize the system lifetime. To make it more realistic, we modify the definition of the system lifetime by considering the coverage constraint and time-critical demand of some applications. We can then derive a better routing algorithm to obtain a maximal system lifetime of a sensor network that is much closer to the real environment.

Because the optimization problem itself is highly complicated and difficult, we use Lagrangean Relaxation method to solve it. Due to the method’s remarkable properties, we are able to solve this complicated optimization problem efficiently, and obtain an energy-efficient routing algorithm at the same time.

並列關鍵字

Wireless Sensor Network ； Lagrangean Relaxation ； Mathematical Programming ； Optimization ； Energy-efficient ； Routing Algorithm

參考文獻

[16] M. A. M. Vieira, D. C. da Silva Jr., C. N. Coelho. Jr. and J. M. da Mata, “Survey on wireless sensor network devices,” Proc. of ETFA '03, Vol. 1, pp. 537-544, Sept. 2003.

[2] M. Bhardwaj and A. P. Chandrakasan, “Bounding the lifetime of sensor networks via optimal role assignments,” Proc. of INFOCOM 2002, Vol. 3, pp. 1587-1596, June 2002.

[3] J. H. Chang and L. Tassiulas, “Energy conserving routing in wireless ad-hoc networks,” Proc. of INFOCOM 2000, Vol. 1, pp. 22-31, March 2000.

[4] E. J. Duarte-Melo and M. Liu, “Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks,” Proc. of GLOBECOM '02, Vol. 1, pp. 21-25, Nov. 2002.

[5] M. L. Fisher, “The Lagrangian relaxation method for solving integer programming problems”, Management Science, vol. 27, pp.1-18, 1981.