請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43850完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林永松 | |
| dc.contributor.author | Yen-Yi Hsu | en |
| dc.contributor.author | 許宴毅 | zh_TW |
| dc.date.accessioned | 2021-06-15T02:30:31Z | - |
| dc.date.available | 2009-08-19 | |
| dc.date.copyright | 2009-08-19 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-08-15 | |
| dc.identifier.citation | [1] A.M. Geoffrion, “Lagrangean Relaxation and its Use in Integer Programming,” Mathematical Programming Study, vol. 2, pp. 82-114, 1974.
[2] B.H. Liu, W.C Ke, C.H. Tsai, and M.J. Tsai, “Constructing a Message-Pruning Tree with Minimum Cost for Tracking Moving Objects in Wireless Sensor Networks Is NP-Complete and an Enhanced Data Aggregation Structure,” IEEE Transactions on Computers, June 2008. [3] C.R. Lin and M. Gerla, “Adaptive clustering for mobile wireless networks,” IEEE Journal of Selected Areas in Communications, July 1997. [4] C.T. Lee, F.Y.S. Lin, and Y.F. Wen, “An Efficient Object Tracking Algorithm in Wireless Sensor Networks,” Proc. JCIS’06, 2006. [5] C.T. Lee and F.Y.S. Lin, “An Energy-Efficient Lagrangean Relaxation-based Object Tracking Algorithm in Wireless Sensor Networks,” 20th International Conference on Information Management (ICIM), 2009. [6] C.Y. Lin, W.C. Peng, and Y.C. Tseng, “Efficient In-Network Moving Object Tracking in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing, August 2006. [7] C.Y. Lin, Y.C. Tseng, T.H. Lai, and W.C. Peng, “Message-efficient In-network Location Management in a Multi-sink Wireless Sensor Network,” International Journal of Sensor Networks, 2008. [8] H. Yang and B. Sikdar, “A Protocol for Tracking Mobile Targets using Sensor Networks,” Proceedings of IEEE Workshop on Sensor Network Protocols and Application, 2003. [9] H.T. Kung and D. Vlah, “Efficient Location Tracking Using Sensor Networks,” Proceedings of 2003 IEEE Wireless Communications and Networking Conference (WCNC), 2003. [10] H.H. Yen, F.Y.S. Lin, and S.P. Lin, “An Energy-Efficient Data-Central Routing Algorithm in Wireless Sensor Networks,” Proc. IEEE ICC, 2005. [11] Henry Medeiros and Johnny Park, “Distributed Object Tracking Using a Cluster-Based Kalman Filter in Wireless Camera Networks,” IEEE Journal of Selected Topics in Signal Processing, 2008 [12] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, ”Wireless Sensor Networks: a Survey,” Elsevier Journal of Computer Networks, vol. 38, pp. 393-422, March 2002. [13] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, ”A Survey on Sensor Networks,” IEEE Communications Magazine, pp. 102-114, August 2002. [14] L.H. Yen and C.C. Yang, “Mobility Profiling Using Markov Chains for Tree-Based Object Tracking in Wireless Sensor Networks,” Proc. IEEE International Confonference on Sensor Networks, Ubiquitous, and Trustworthy Computing - vol 2 - Workshops, June 2006. [15] M.L. Fisher, “An Application Oriented Guide to Lagrangean Relaxation,” Interfaces, vol. 15, no. 2, pp. 10-21, April 1985. [16] M.L. Fisher, “The Lagrangian relaxation method for solving integer programming problems,” Management Science, vol. 27, no. 1, pp. 1-18, 1981. [17] J. Winter, Y. Xu, and W.C. Lee, “Prediction Based Strategies for Energy Saving in Object Tracking Sensor Networks,” Proceedings of IEEE International Conference on Mobile Data Management (MDM 04), Jan. 2004. [18] S. Banerjee and S. Khuller, “A clustering scheme for hierarchical control in multi-hop wireless networks,” Proceedings of IEEE INFOCOM, April 2001. [19] Y.F. Wen, F.Y.S. Lin and W.C. Kuo, 'A Tree-based Energy-efficient Algorithm for Data-Centric Wireless Sensor Networks,' Proc. IEEE AINA, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43850 | - |
| dc.description.abstract | 近年來由於感測器的技術與無線通訊的蓬勃發展，使得無線感測網路(Wireless Sensor Networks)已經被廣泛的應用於各領域；但是在硬體上的限制與應用環境的影響，使得感測器在能源的消耗上有著高度的限制性，因此降低感測器於運作中所消耗之能源成了無線感測網路中最熱門的研究議題之一。
本篇論文研究的目的，是希望能夠在任意的網路拓墣中，能夠達到高效率節能(energy-efficient)的物體追蹤(object tracking)；物體追蹤有兩個主要的操作：更新與查詢，現有研究大多僅考慮更新成本，或者於第二階段以查詢成本做調整。本文希望以建立物體追蹤樹的方式，以最小化成本建立該樹，並於建立時同時考量更新成本與查詢成本，將此問題轉化成一個整數規劃問題，利用拉格蘭日鬆弛法，發展出一個啟發式法則的演算法，用以建立最小化成本之物體追蹤樹。 | zh_TW |
| dc.description.abstract | 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.
In 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T02:30:31Z (GMT). No. of bitstreams: 1 ntu-98-R96725033-1.pdf: 1402738 bytes, checksum: 4d74bcbf48af5fda0dce8a52f54f28c9 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 論文摘要 I
THESIS ABSTRACT III TABLE OF CONTENTS V LIST OF TABLES VII LIST OF FIGURES IX CHAPTER 1 INTRODUCTION 1 1.1 Background 1 1.2 Motivation 3 1.3 Literature Survey 4 1.3.1 Object Tracking 4 1.3.2 Update Mechanism 8 1.3.3 Query Mechanism 12 CHAPTER 2 PROBLEM FORMULATION 15 2.1 Problem Description 15 2.2 Problem Notation 19 2.3 Problem Formulation 21 2.4 Varieties of the Model 23 CHAPTER 3 SOLUTION APPROACH 28 3.1 Introduction to Lagrange Relaxation Method 28 3.2 Lagrangean Relaxation (LR) 31 3.2.1 Subproblem 1 (related to decision variable ) 33 3.2.2 Subproblem 2 (related to decision variable ) 34 3.2.3 Subproblem 3 (related to decision variable ) 35 3.2.4 Subproblem 4 (constant part) 35 3.3 The Dual Problem and the Subgradient Method (IP) 36 CHAPTER 4 GETTING PRIMAL FEASIBLE SOLUTIONS 37 4.1 Lagrangean Relaxation Results 37 4.2 Getting Primal Feasible Solutions 37 4.3 Simple Algorithms 40 CHAPTER 5 COMPUTATIONAL EXPERIMENTS 41 5.1 Experiments Environment 41 5.2 Solution Qualitiy 42 CHAPTER 6 CONCLUSION AND FUTURE WORK 49 6.1 Conclusion 49 6.2 Future Work 50 REFERENCES 51 | |
| dc.language.iso | en | |
| dc.subject | 拉格蘭日鬆弛法 | zh_TW |
| dc.subject | 無線感測網路 | zh_TW |
| dc.subject | 物體追蹤 | zh_TW |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 高效率節能 | zh_TW |
| dc.subject | Optimization | en |
| dc.subject | Wireless Sensor Networks (WSNs) | en |
| dc.subject | Lagrangean Relaxation (LR) | en |
| dc.subject | Energy-Efficient | en |
| dc.subject | Object Tracking | en |
| dc.title | 無線感測網路之低能耗物體追蹤樹建置演算法 | zh_TW |
| dc.title | An Energy-Efficient Algorithm for Constructing Object Tracking Trees in Wireless Sensor Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 鐘嘉德,呂俊賢,林盈達,傅新彬 | |
| dc.subject.keyword | 無線感測網路,物體追蹤,最佳化,高效率節能,拉格蘭日鬆弛法, | zh_TW |
| dc.subject.keyword | Wireless Sensor Networks (WSNs),Object Tracking,Optimization,Energy-Efficient,Lagrangean Relaxation (LR), | en |
| dc.relation.page | 55 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-08-17 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 1.37 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。