林永松臺灣大學：資訊管理學研究所葉耿宏Yeh, Keng-HungKeng-HungYeh2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/54270無線感應器網路是近年來相當熱門的研究主題。由於感應器技術的進步，促成了無線感應器網路快速蓬勃的發展。無線感應器網路可以被廣泛的使用在許多不同領域的應用上，例如：衛生醫療、軍事國防、環境偵測等等。雖然無線感應器網路能夠提供許多有價值的應用，但同時，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.謝詞 I 論文摘要 III THESIS ABSTRACT V Table of Contents VII List of Tables IX List of Figures X Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 7 1.3 Literature Survey 9 1.3.1 Routing in Wireless Sensor Networks 9 1.3.1.1 Flat Routing 9 1.3.1.2 Hierarchical Routing 11 1.3.2 Bounding System Lifetime 14 Chapter 2 Problem Formulation 17 2.1 Model 1 19 2.1.1 Problem Descriptions 19 2.1.2 Notations 21 2.2 Model 2 25 2.2.1 Problem Descriptions 25 2.2.2 Notations 27 Chapter 3 Solution Approaches 33 3.1 Lagrangean Relaxation Method 33 3.2 Model 1 36 3.2.1 Solution Approach 36 3.2.2 Lagrangean Relaxation 36 3.2.3 The Dual Problem and the Subgradient Method 40 3.3 Model 2 41 3.3.1 Solution Approach 41 3.3.2 Lagrangean Relaxation 41 3.3.3 The Dual Problem and the Subgradient Method 48 Chapter 4 Getting Primal Feasible Solutions 49 4.1 Heuristic for Model 1 50 4.1.1 Reroute Heuristic 50 4.2 Heuristic for Model 2 52 4.2.1 Reroute Heuristic 52 Chapter 5 Computational Experiments 55 5.1 Simple Algorithm for Model 1 (SA 1) 55 5.2 Simple Algorithm for Model 2 (SA 2) 56 5.3 Parameters and Scenarios of the Experiment 56 5.4 Experimental Results 60 5.4.1 Experimental Results for Model 1 60 5.4.2 Experimental Results for Model 2 62 5.4.3 Computation Time 64 5.5 Discussion of Results 65 Chapter 6 Summary and Future Work 67 6.1 Summary 67 6.2 Future Work 68 References 69528651 bytesapplication/pdfen-US拉格蘭日鬆弛法高效能最佳化路由演算法數學規劃無線感應器網路Wireless Sensor NetworkLagrangean RelaxationMathematical ProgrammingOptimizationEnergy-efficientRouting Algorithmotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54270/1/ntu-93-R91725017-1.pdf