臺灣博碩士論文加值系統

近年來物體追蹤(Object Tracking)技術在無線感測網路(Wireless Sensor Network)的領域上被廣泛的應用到許多方面。而使用者想要在感測網路中觀察物體在某個區域裡的移動狀況勢必要在區域內佈滿許多的感測節點(Sensor Node)，並且讓感測節點之間透過無線相互溝通並傳輸彼此的位置資訊，藉以構成一個無線感測網路。在感測節點的幫助下使用者可隨時透過查詢得知物體所在的位置資訊或感測節點所收集的物體資料。然而物體在無線感測網路中，會不斷地移動使得整個無線感測網路頻繁的更新物體位置到管理節點，因而付出大量的通訊成本導致整個無線感測網路的壽命縮減 ，因此如何有效的減少通訊成本的花費也成了一個相當重要的議題。
在本論文中，我們提出遞轉變量策略(Variable Forwarding-Link Scheme , VFLS) 來動態的管理物體的位置。VFLS在新的感測節點偵測到物體後，便與舊的感測節點建立鏈結(Forwarding Link) 來傳遞訊息，而非直接做更新，如此可以減少物體移動時傳遞更新訊息所需的大量通訊成本。而使用者便可藉由Query-Delivery Path與Forwarding Link Path來查詢物體目前所在的位置。但隨著物體位置的不斷移動，其所建立的Forwarding Link Path會因為過長而使得查詢成本增加。為解決此問題，VFLS主要想法是在新的Forwarding Link建立前，透過演算法根據環境來計算出適當的重新註冊時機，使物體在各種不同的環境下能動態建立適當的Forwarding Link Path，進而避免浪費不必要的成本建立訊息鏈結。為了分析及證明遞轉變量策略的優劣，我們使用派翠網(Petri Net)針對該策略發展一個效能評估模型，並利用此模型分析在各種不同的環境下遞轉變量策略與傳統的使用方法以及目前廣泛使用的方法來互相比較，其結果顯示遞轉變量策略方法確實比其它方法較佳。

Object tracking technology in wireless sensor networks is widely applied in many applications in recent years. A lot of sensor nodes are deployed in an area for users to monitor the objects’ migrations. Sensor nodes communicate with each other through the wireless transmission to form a wireless sensor network. By monitoring objects in a wireless sensor network, users can always query the locations of objects and obtain the information collected by sensor nodes. However, moving objects will yield great location information, it would spend much cost to manage these locations. That will lead to reduce the life of a wireless sensor network. Therefore, it is an important issue to manage the moving object’s location efficiently in a wireless sensor network.
In this thesis, we propose a Variable Forwarding-Link Scheme (VFLS) to manage the location of the object. The main idea of VFLS is that design an algorithm to determine if builds a forwarding link or make a new delivery path dynamically. The length of a forwarding link is no more constant. For analyzing and proving the advantage and disadvantage of the Variable Forwarding-Link Scheme, we use Petri Nets to develop an evaluated model. Also, in a variety of different situations we compare the Variable Forwarding-Link Scheme with the most applied method and the traditional method, it shows that the Variable Forwarding-Link Scheme is better indeed.

摘　　要
ABSTRACT
致　　謝
目　　次
圖目錄
表目錄
第一章 前言
第二章 相關文獻
2.1物體追蹤感測網路
2.2 Date storage scheme
第三章 環境架構
3.1 Assumption
3.2 網路架構
第四章 遞轉變量策略方法(VFLS)
4.1 Query-Delivery Path建立
4.2 Forwarding Link建立
4.3重新註冊
4.4 使用者查詢處理
第五章 Stochastic Petri Net Package(SPNP)
5.1 物體的移動行為
5.2最新感測到物體節點的行為
5.3物體移動時造成Anchor與最小共同祖先的變化
5.4 Forwarding Link行為
5.5重新註冊行為
5.6 使用者查詢
第六章 效能評估
6.1成本計算
6.2實驗結果
6.2.1 Query Mobility Ratio(QMR)的變動對於VFLS效能影響
6.2.2階層的變化對於VFLS的效能影響
6.2.3 Query Rate 與Mobilty Rate不同比值對於VFLS的效能影響
第七章　結論
參考文獻

[1]Alan Mainwaring, Joseph Polastre, Robert Szewczyk and David Culler, "Wireless Sensor Networks for Habitat Monitoring," Proceedings of the first ACM International Workshop on Wireless Sensor Networks and Applications, 2002, pp. 88-97.
[2]Anand Meka and Ambuj K. Singh, "DIST: a distributed spatio-temporal index structure for sensor networks," Proceedings of the 2005 ACM CIKM international Conference on Information and Knowledge Management, Bremen, Germany, Nov 2005, pp.139-146.
[3]B. Karp and H.T. Kung, "GPSR: Greedy Perimeter Stateless Routing for Wireless Networks," Proceedings of The Sixth Annual International conference on Mobile computing and Networking, Massachusetts, Boston, August 2000.
[4]Chao-Chun Chen, Chiang Lee, and Yen-Liang Liu, "A Gossip-enabled Spatial Index for Moving Object Management over Wireless Sensor Networks," in Proceedings of the 4th International Conference on Mobile Ad-hoc and Sensor Networks (MSN'08), Wuhan, China, December 10-12, 2008, accepted and to appear. (EI)
[5]Chih-Yu Lin, Wen-Chih Peng and YU-Chee Tseng, "Efficient in-Network Moving Object Tracking in Wireless Sensor Networks," Proceedings of IEEE Trans. Mob. Computing, 5(8), 2006 pp.1044-1056
[6]Gianfranco Ciardo, Jogesh Muppala and Kishor Trivedi, "SPNP: Stochastic Petri Net Package," Proceedings of the Third International Workshop on Petri Nets and Performance Models, 1989.( PNPM89), Kyoto , Japan, 11-13 Dec 1989,pp.142 – 151
[7]Deborah Estrin, Ramesh Govindan, John Heidemann and Satish Kumar, "Next Century Challenges: Scalable Coordination in Sensor Networks," Proceedings of MOBICOMM 1999, 1999, pp.263-270.
[8]F. Zhao, J.Shin and J.Reich, "Information-driven dynamic sensor collaboration for tracking applications," In Proceedings of IEEE Signal Processing Magazine 2002, pp.68-77.
[9]Feng Yu, JunZhou Luo,Wei Li and La-Lin Jiang, "Formal Specification and Analysis of Intelligent Network Management System by Using Colored Petri Net," Networking, Architecture, and Storage, 2009. NAS 2009. IEEE International Conference on, hunan, 9-11 July 2009, pp.200 - 203
[10]Holger Karl, "Protocols and Architectures for Wireless Sensor Networks," John Wiley, 2005.
[11]H. T. Kung and D. Vlah, "Efficient Location Tracking Using Sensor Networks," Proceedings of The IEEE Wireless Communications and Networking Conference (WCNC), vol. 3, pp.1954-1964, 2003.
[12]Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam and Erdal Cayirci, "A survey on sensor networks," Communications Magazine, IEEE, Vol. 40, 2002, pp.102-114.
[13]Ing-Ray Chen and Baoshan Gu, "Quantitative Analysis of a Hybrid Replication with Forwarding Strategy for Efficient and Uniform Location Management in Mobile Wireless Networks," IEEE Transactions on Mobile Computing, Vol. 2, 2003, pp.3-15.
[14]Ing-Ray Chen, Tsong-Ming Chen and Chiang Lee, "Performance Evaluation of Forwarding Strategies for Location Management in Mobile Networks," The Computer Journal, Vol. 41, No. 4, 1998.
[15]Joseph Polastre, Robert Szewczyk, Cory Sharp and David Culler, "The Mote Revolution: Low Power Wireless Sensor Network Devices," Proceedings of Hot Chips 16: A Symposium on High Performance Chips. August 22-24, 2004.
[16]K.S. Trivedi, G. Ciardo and J. Muppala, "SPNP User's Manual Version 6.0," Dept. of Electrical Engineering Duke University, Durham, NC, 1999.
[17]Lingxi Li, Christoforos N. Hadjicostis, and Ramavarapu S. Sreenivas, "Designs of Bisimilar Petri Net Controllers With Fault Tolerance Capabilities," Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on,38(1), Jan. 2008,pp. 207 - 217.
[18]Philo Juang, Hidekazu Oki, Yong Wang, Margaret Martonosi, Li Shiuan Peh and Daniel Rubenstein, "Energy efficient computing for wildlife tracking: Design tradeoffs and early experiences with ze branet," In Proceedings of the Tenth International conference on Architectural Support for Programming Languages and Operating Systems, 2002, pp.96-107.
[19]Rahul Gupta and Samir R. Das, "Tracking Moving Targets in a Smart Sensor Network. " Proceedings of VTC Fall 2003 Symposium, Orlando, Florida, USA, October. 2003.
[20]Ravi Jain, Yi-Bing Lin, Charles N. Lo and Seshadri Mohan, "A Forwarding Strategy to Reduce Network Impacts of PCS," Proceedings of INFOCOM'95, Vol. 2, 1995, pp.481-489.
[21]Tony Spiteri Staines, "Intuitive Mapping of UML 2 Activity Diagrams into Fundamental Modeling Concept Petri Net Diagrams and Colored Petri Nets," Engineering of Computer Based Systems, 2008. ECBS 2008. 15th Annual IEEE International Conference and Workshop on the, Belfast, March 31 2008-April 4 2008,pp.191-200.
[22]Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan and Scott Shenker, "GHT: a geographic hash table for data-centric storage," Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications(WSNA), Atlanta, Georgia, Sep.2002, pp.78-87.
[23]Xin Li,Young-Jin Kim,Ramesh Govindan and Wei Hong, "Multi-dimensional range queries in sensor networks," Proceedings of the 1st international conference on Embedded Networked Sensor Systems.(SenSys), Los Angeles, California, USA, Nov.2003,pp.63-75.
[24]Yingqi Xu, Julian Winter and Wang-Chien Lee, "Prediction-based Strategies for Energy Saving in Object Tracking Sensor Networks," Proceedings of the 5th IEEE International Conference on Mobile Data Management (MDM’04), Berkeley, California, USA, January 2004, pp.346-357.
[25]Yingqi Xu, Julian Winter and Wang-Chien Lee, "Dual Prediction-based Reporting for Object Tracking Sensor Networks," Proceedings of First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous’04), Cambridge, Massachusetts USA, August 2004, pp.154-163.
[26]Yingqi Xu and Wang-Chien Lee, "On Localized Prediction for Power Efficient Object Tracking in Sensor Networks," Proceedings of 23rd International Conference on Distributed Computing Systems Workshops(ICDCSW’03), Providence, Rhode Island, USA, May 2003, pp.434- 439.