無線感測網路之低能耗物體追蹤樹建置演算法

An Energy-Efficient Algorithm for Constructing Object Tracking Trees in Wireless Sensor Networks

許宴毅(Yen-Yi Hsu)

指導教授 ： 林永松

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

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

摘要

近年來由於感測器的技術與無線通訊的蓬勃發展，使得無線感測網路(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.
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.

並列關鍵字

Wireless Sensor Networks (WSNs) ； Object Tracking ； Optimization ； Energy-Efficient ； Lagrangean Relaxation (LR)

參考文獻

[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.

[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.