林永松臺灣大學:資訊管理學研究所許宴毅Hsu, Yen-YiYen-YiHsu2010-05-052018-06-292010-05-052018-06-292009U0001-1408200922442700http://ntur.lib.ntu.edu.tw//handle/246246/179987近年來由於感測器的技術與無線通訊的蓬勃發展，使得無線感測網路(Wireless Sensor Networks)已經被廣泛的應用於各領域；但是在硬體上的限制與應用環境的影響，使得感測器在能源的消耗上有著高度的限制性，因此降低感測器於運作中所消耗之能源成了無線感測網路中最熱門的研究議題之一。篇論文研究的目的，是希望能夠在任意的網路拓墣中，能夠達到高效率節能(energy-efficient)的物體追蹤(object tracking)；物體追蹤有兩個主要的操作：更新與查詢，現有研究大多僅考慮更新成本，或者於第二階段以查詢成本做調整。本文希望以建立物體追蹤樹的方式，以最小化成本建立該樹，並於建立時同時考量更新成本與查詢成本，將此問題轉化成一個整數規劃問題，利用拉格蘭日鬆弛法，發展出一個啟發式法則的演算法，用以建立最小化成本之物體追蹤樹。In recent years, due to the rapid growth in sensor technology and wireless communication, Wireless Sensor Networks (WSNs) have been applied in various applications. Nevertheless, sensor nodes are highly energy-constrained, because of the limitation of hardware and the infeasibility of recharging the battery under a harsh environment. Therefore, energy consumption of sensor nodes becomes one of the popular issues. n this thesis, our purpose is to achieve energy-efficient object tracking for an arbitrary topology in WSNs. Object tracking typically contains two basic operations: update and query. Most research only considers the update cost during the design phase, or adjusts the structure by taking the query cost into consideration in the second round. We aim to construct an object tracking tree with minimum total cost including both the update and query costs. This problem is formulated as an integer programming problem. We use the Lagrangean relaxation method to find an optimal solution and to develop a heuristic algorithm for constructing an object tracking tree with minimum cost.論文摘要 IHESIS ABSTRACT IIIABLE OF CONTENTS VIST OF TABLES VIIIST OF FIGURES IXHAPTER 1 INTRODUCTION 1.1 Background 1.2 Motivation 3.3 Literature Survey 4.3.1 Object Tracking 4.3.2 Update Mechanism 8.3.3 Query Mechanism 12HAPTER 2 PROBLEM FORMULATION 15.1 Problem Description 15.2 Problem Notation 19.3 Problem Formulation 21.4 Varieties of the Model 23HAPTER 3 SOLUTION APPROACH 28.1 Introduction to Lagrange Relaxation Method 28.2 Lagrangean Relaxation (LR) 31.2.1 Subproblem 1 (related to decision variable ) 33.2.2 Subproblem 2 (related to decision variable ) 34.2.3 Subproblem 3 (related to decision variable ) 35.2.4 Subproblem 4 (constant part) 35.3 The Dual Problem and the Subgradient Method (IP) 36HAPTER 4 GETTING PRIMAL FEASIBLE SOLUTIONS 37.1 Lagrangean Relaxation Results 37.2 Getting Primal Feasible Solutions 37.3 Simple Algorithms 40HAPTER 5 COMPUTATIONAL EXPERIMENTS 41.1 Experiments Environment 41.2 Solution Qualitiy 42HAPTER 6 CONCLUSION AND FUTURE WORK 49.1 Conclusion 49.2 Future Work 50EFERENCES 51application/pdf1402738 bytesapplication/pdfen-US無線感測網路物體追蹤最佳化高效率節能拉格蘭日鬆弛法Wireless Sensor Networks (WSNs)Object TrackingOptimizationEnergy-EfficientLagrangean Relaxation (LR)http://ntur.lib.ntu.edu.tw/bitstream/246246/179987/1/ntu-98-R96725033-1.pdf