物件追蹤應用在網格式無線感測器網路之研究

A Study on Object Tracking for Grid Wireless Sensor Networks

林昱成(Yu-Cheng Lin)

指導教授 ： 陳永隆

國立臺中科技大學/資訊與流通學院/資訊工程系碩士班/碩士(2012年)

摘要

在無線感測網路(WSNs)中，由於每個無線感測器的電量有限，所以如何有效的節省能量消耗，使得整體無線網路生命週期延長是一個重要的議題。本論文是在探討在一個網格式的無線感測器網路中，結合使用PEGASIS拓樸架構來減少路由的距離，再來結合IBCA覆蓋演算法來減少活動節點數，來降低整體無線感測器網路的能量消耗，因此我們提出兩種演算法來降低網路耗能PEGASIS with IBCA and Intra-grid PEGASIS with IBCA。一開始我們在形成PEGASIS架構之後，使用IBCA覆蓋演算法來判斷多餘節點，讓多餘節點進入休眠，減少能樣消耗;此外，我們提出Intra-grid PEGASIS with IBCA使用網格計算的方式，將無線感測網路劃分成數個網格，而相鄰的網格都可以互相通訊，之後我們將網格內的感測器節點使用PEGASIS的路由架構，建立intra-grid PEGASIS拓樸架構，接著使用IBCA覆蓋演算法找尋可休眠的節點，讓它進入休眠，節省電量。更進一步，在拓樸架構完成之後，我們探討當事件發生時，物件會隨機的移動，我們使用追蹤的機制追蹤移動物件的移動軌跡，找出物件將會出現位置，並且根據追蹤的結果，安排感測器節點的工作時間，給予物件將會出現的節點進入活動狀態，而物件不會出現的節點進入休眠狀態，降低整體無線感測器網路的活動節點數，有效的節省整體網路能量消耗。我們提出了一種混合式的追蹤模型，一開始使用Markov chain來預測每個網格物件將會出現的機率，之後在物件出現機率最大的網格內使用灰色理論來精確的預測出物件出現的位置，有效的減少預測的範圍，之後根據預測的結果安排各網格內感測器節點，降低追蹤失誤所花費的能量消耗，使延長無線感測網路生命週期。

關鍵字

無線感測網路 ； 網格 ； PEGASIS ； 物件追蹤

並列摘要

It is an important issue that how to decrease the energy consumption and prolong the lifetime of entire network in wireless sensor networks (WSNs). The sensor node which chosen to be cluster head consumes more energy than other sensor nodes. Hence, we propose two schemes which combine the PEGASIS topology architecture and intersection-based coverage algorithm (IBCA) to decrease the energy consumption. First of all, the system finds out the redundant sensor nodes to enter to sleep mode by means of IBCA. Then, it builds the PEGASIS topology architecture by active sensor nodes which are not chosen to enter to sleep mode by IBCA. Moreover, we propose the intra-Grid PEGASIS with IBCA to reduce the PEGASIS routing path distance. In intra-Grid PEGASIS with IBCA, the sensing area is divided into several network grids. And then the nodes within the network grid will be connected. Through a series of simulations, the performance of our novel schemes outperforms the performances of LEACH with PBCA in terms of energy consumption, number of alive nodes and sensing areas. Furthermore, we consider that when the target appears, we use the tracking models to predict the object moving path in a grid wireless sensor network. The system determines the sleep and wakeup schedules via tracking. It is efficiently to conserve the energy consumption. At first, the network is divided into several grids by using grid computing. Each neighbor grid can communicate with each other. And construct the intra-grid PEGASIS by each grid. Further, the sensors may be put into sleep mode by using the coverage algorithm. Hence, less sensor nodes are in wakeup mode and consume less energy. After the topology construction, the objects will move randomly. We propose a hybrid predictive model which combines grey theory and Markov chain to predict the object moving path. And the system determines the sleep and wakeup schedules for each sensor node. It will decrease the cost which arise from the tracking error and prolong the network lifetime.

並列關鍵字

grid ； PEGASIS ； IBCA ； target tracking ； Markov chain ； Grey theory ； prediction

參考文獻

[1] P. Kumarawadu, D. J. Dechene, M. Luccini, and A. Sauer, “Algorithms for Node Clustering in Wireless Sensor Networks: a Survey,” Proceedings of IEEE 4th ICIAFS, pp.295-300, Dec. 2008.

[2] A. Garg and R. Tamassia “A new minimum cost flow algorithm with applications to graph drawing,” Proc. the Symposium on Graph Drawing, pp. 201-216, London, UK, 1996.

[3] J. Burrell, T. Brooke, and R. Beckwith, “Vineyard Computing: Sensor Networks in Agricultural Production,” IEEE Pervasive Computing, vol. 3, no. 1, pp. 38-45, Jan.-May, 2004.

[6] M. J. Islam, M. M. Islam, and M. N. Islam, “A-sLEACH: An Advanced Solar Aware Leach Protocol for Energy Efficient Routing in Wireless Sensor Networks,” Proceedings of IEEE Sixth ICN, pp. 4-4, Apr. 2007.

[7] K. Pahlavan and A. Levesque, Wireless Information Networks. NewYork: Wiley, 1995.