應用於無線感測器網路物體追蹤之資料聚集結構與位置預測方法

An Enhanced Data Aggregation Structure and a Message-Efficient Location Prediction Method for Object Tracking in Wireless Sensor Networks

劉炳宏(Bing-Hong Liu)

指導教授 ： 石維寬 ； 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/博士(2008年)

摘要

無線感測器網路(wireless sensor networks)常被使用來監控及回報移動物體的位置。在本論文第一部分的研究中，我們研究了如何有效地在無線感測器網路中尋找及回報物體位置。由於感測器可以用來儲存資料，無線感測器網路可以被視為一個分散式的資料庫，因此可以讓我們去更新以及查詢此資料庫所儲存的物體位置。很多研究人員已經著手研究如何建立一個最低更新及查詢成本的訊息刪除樹的問題(the Minimum Cost Message-Pruning Tree problem)，使其可以有較低的更新及查詢物體的成本，然而此問題的複雜度仍然是未知的。在此研究中，我們證明了此問題是NP-complete，此外我們提出了一個新的資料聚集結構，也就是一個附有捷徑的訊息刪除樹。在第二部分的研究中，我們研究了如何在一個追蹤系統中有效地監控物體。在無線感測器網路中，感測器通常處於睡眠狀態以期延長網路的壽命。在無線感測器網路中的追蹤系統通常使用預測模組去預測物體的下一個位置，並活化適當的感測器以便繼續監控此物體。一旦預測失敗以致於不能追蹤此物體時，將會有額外的感測器被活化起來重新捕捉物體的位置。由此可知，一個較好的預測模組可以讓較少的感測器被活化，因此可以有效地減少能量的消耗。由於高斯馬可夫移動模組(Gauss-Markov mobility model)可以即時捕捉物體速度的相關性，所以此模組為描述物體移動軌跡最好模組中的ㄧ個。之前的研究使用自相關方法(autocorrelation technique)或是遞迴式最小平方估測法(recursive least square estimation technique)來估測高斯馬可夫參數，然而這些方法都需要大量的物體歷史移動資訊。由於使用這些方法時需要在感測器間傳遞大量的訊息，而且無線感測器通常是使用電池供電的，因此這些方法不適合應用於無線感測器網路的物體追蹤。在此我們利用最大概似法(maximum likelihood technique)開發一個應用於無線感測器網路中的高斯馬可夫參數估測方法(GMPE_MLH)。此方法僅需要較少訊息傳遞便可以估測出高斯馬可夫參數。

關鍵字

無線感測器網路 ； 物體追蹤 ； 資料聚集 ； 訊息刪除樹 ； 位置預測 ； 高斯馬可夫移動模組

並列摘要

Wireless sensor networks have often been used to monitor and report the locations of moving objects. In the first part of the dissertation, we investigate how to efficiently find and report the locations of moving objects within wireless sensor networks. Since sensors can be used for storage, a wireless sensor network can be considered a distributed database, enabling us to update and query the location information of moving objects. Many researchers have studied the problem of how to construct message-pruning trees that can update a database and query objects with minimum cost (the Minimum Cost Message-Pruning Tree problem). The trees are constructed in such a way that the total cost of updating the database and querying objects is kept as minimum as possible, while the hardness of the Minimum Cost Message-Pruning Tree problem remains unknown. Here, we show that the Minimum Cost Message-Pruning Tree problem is NP-complete. Besides, we propose a new data aggregation structure, a message-pruning tree with shortcuts, instead of the message-pruning tree. In the second part of the dissertation, we investigate how to efficiently monitor the objects in a tracking system. In a wireless sensor network, sensors are usually in the sleep state to prolong the network life. The tracking system in a wireless sensor network usually uses a prediction model to predict the next location of the object and activates the appropriate sensors to keep monitoring the object. Once the prediction fails to track the object, additional sensors are activated in order to recapture the lost object. Therefore, a better prediction model can significantly reduce power consumption because fewer redundant sensors will be activated. The Gauss-Markov mobility model is one of the best mobility models to describe object trajectory because it can capture the correlation of object velocity in time. Traditionally, Gauss-Markov parameters are estimated using autocorrelation technique or recursive least square estimation technique; either of these techniques, however, requires a large amount of historical movement information of the mobile object, which is not suitable for tracking objects in a wireless sensor network because they demand a considerable amount of message communication overhead between wireless sensors which are usually battery-powered. Here, we develop a Gauss-Markov parameter estimator for wireless sensor networks (GMPE_MLH) using a maximum likelihood technique. The GMPE_MLH estimates Gauss-Markov parameters with few requirements in terms of message communication overhead.

並列關鍵字

Wireless Sensor Network ； Object Tracking ； Data Aggregation ； Message-Pruning Tree ； Location Prediction ； Gauss-Markov Mobility Model

參考文獻

[1] F. Aurenhammer, “Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure,” ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, 1991.

[3] J.J. Caffery, “A New Approach to the Geometry of TOA Location,” IEEE VTC, pp. 1943–1949, 2000.

[5] C. Campos, D. Otero, and L.D. Moraes, “Realistic Individual Mobility Markovian Models for Mobile Ad Hoc Networks,” IEEE WCNC, pp. 1980–1985, 2004.

[6] W.P. Chen, J.C. Hou, and L. Sha, “Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks,” IEEE Trans. on Mobile Computing, vol. 3, no. 3, pp. 258–271, 2004.

[7] J.C. Chen, R.E. Hudson, and K. Yao, “Maximum-Likelihood Source Localization and Unknown Sensor Location Estimation for Wideband Signals in the Near-Field,” IEEE Trans. on Signal Processing, vol. 50, no. 8, pp. 1843–1854, 2002.