近年來, location-based services 的應用在無線感測網路上越來越受矚目. 在本論文, 在 LBS 的應用中, 我們關注的是在無線感測網路上對過去一段時間的物體位置所作的查詢. 這種查詢稱為historical spatio and temporal range query (HSTRQ). 由於物體會在無線感測網路中不斷地移動. 而且大部分儲存資料的機制用來處理 HSTRQ 會浪費大量的能源在更新或查詢物體的位置. 因此, 在本論文中, 我們提出 Single-Path Forwarding-Link Scheme (SPFL) 來管理物體的歷史位置. 因為物體每次移動皆具有 locality 的特性, SPFL 利用此特性在偵測到物體的 sensors 之間建立傳遞訊息的鏈結 (called forwarding link). 可減少大量傳遞更新訊息所需的通訊成本. 更進一步地, 我們提出 Multi-Path Forwarding-Link Scheme (MPFL) 解決 SPFL 查詢成本過高的問題. MPFL 的想法是在 forwarding link 上建立多條與 server 之間的鏈結 (called query-delivery path) 使得每個 query 可根據查詢時間選擇最少成本的路徑. 我們提出了一個分析模組來決定建立 query-delivery path 的時機, 避免浪費能源去建立不必要的 query-delivery path. 最後, 我們針對我們的方法實作了完整的實驗. 實驗結果顯示, SPFL 及 MPFL 在各種實驗設定下是較其他相關的方法有較好的效能.

Recently, location-based service (LBS) applications receive much attention in wireless sensor networks. In this thesis, we consider a query type in LBS applications that can query the historical locations of moving objects for a past period in wireless sensor networks, and such type of query is called {em historical spatio and temporal range query (HSTRQ)}. Since objects frequently move in a wireless sensor network, most of the data storage shemes deal with HSTRQ causing a lot of energy consumption on updating and querying object locations. Hence, in this thesis, we propose Single-Path Forwarding-Link Scheme (SPFL) to manage the historical object locations. Due to the locality property of the object movement, SPFL utilizes the property to create the communication links (called forwarding link) between the detecting sensor nodes, so that the movement cost can be greatly reduced. Moreover, we propose Multi-Path Forwarding-Link Scheme (MPFL) to solve the problem of excessively high query cost on SPFL. The idea of MPFL is to creat multiple links to the server (called query-delivery path), so that each query can choose the minimum cost path according to its query time. We then derive an analytical model to calculate the timing of creating new query-delivery path,
in order to avoid wasting energy to create unnecessary query-delivery paths. Finally, we conduct a complete set of experiments for the proposed schemes. The experimetal results show that SPFL and MPFL can save significant energy consumption in various environmental setting, and have more superior performance than other related strategies.

[1] Philo Juang, Hidekazu Oki, Yong Wang, Margaret Martonosi, Li-Shiuan Peh, Daniel Rubenstein, ”Energy efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet.”In Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS’02) 2002, pp.96-107.
[2] Feng Zhao and Jaewon Shin and James Reich, ”Information-driven dynamic sensor collaboration for tracking applications.”In Proceedings of IEEE Signal Processing Magazine 2002, pp.68-77.
[3] Benjamin Greenstein, Deborah Estrin, Ramesh Govindan, Sylvia Ratnasamy, Scott Shenker, ”DIFS: A Distributed Index for Features in Sensor Networks.”In Proceedings of First IEEE International Workshop on Sensor Network Protocols an Applications (SNPA ’03), Anchorage, Alaska, USA, May 11, 2003.
[4] W. Zhang, G. Cao, T.L. Porta, ”Data Dissemination with Ring-Based Index for Wireless Sensor Networks.”Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP’03), Atlanta, Georgia, USA, November 2003.
[5] H. T. Kung , D. Vlah, ”Efficient Location Tracking Using Sensor Networks.”Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, Louisiana, USA, March 2003.
[6] 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.
[7] Yingqi Xu, 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.
[8] Yingqi Xu, Julian Winter, Wang-Chien Lee, ”Prediction-based Strategies for Energy Saving in Object Tracking Sensor Networks.”Proceedings of IEEE International Conference on Mobile Data Management (MDM’04) , Berkeley, California, USA, January 2004, pp.346-357.
[9] Yingqi Xu, Julian Winter, 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.
[10] Rahul Gupta, Samir R. Das, ”Tracking Moving Targets in a Smart Sensor Network.”Proceedings of VTC Fall 2003 Symposium , Orlando,Florida, USA, October. 2003.
[11] Mohamed F. Mokbel, Walid G. Aref, Susanne E. Hambrusch, Sunil Prabhakar, ”Towards scalable location-aware services: requirements and research issues.”Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems(GIS’03) , New Orleans, Louisiana, USA, November 2003, pp.110-117.
[12] Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, WeiHong, ”TinyDB: an acquisitional query processing system for sensor networks.” Proceedings of ACM Trans. Database Syst. , 30(1), 2005, pp.122-173.
[13] Guanghui He, Rong Zheng, Indranil Gupta, Lui Sha, ”A framework for time indexing in sensor networks.” Proceedings of ACM Trans.on Sensor Network. , 1(1), 2005, pp.101-133.
[14] Anand Meka, Ambuj K. Singh ”DIST: a distributed spatio-temporal index structure for sensor networks.” Proceedings of the International Conference on Information and Knowledge Management(CIKM’05), Bremen, Germany, November 2005, pp. 139-146.
[15] Chih-Yu Lin, Wen-Chih Peng, Yu-Chee Tseng, ”Efficient In-Network Moving Object Tracking in Wireless Sensor Networks.” Proceedings of IEEE Transaction Mobile Computing, 5(8), 2006, pp.1044-1056.
[16] Jianliang Xu, Xueyan Tang, Wang-Chien Lee, ”A New Storage Scheme for Approximate Location Queries in Object-Tracking Sensor Networks.” Proceedings of IEEE Transaction Parallel Distributed System, 19(2), 2008, pp.262-275.
[17] Ing-Ray Chen, Tsong-Min Chen, Chiang Lee, ”Agent-Based Forwarding Strategies for Reducing Location Management Cost in Mobile Networks.” Proceedings of ICPADS, 1998, pp.266-273.
[18] Ravi Jain, Yi-Bing Lin ”An auxiliary user location strategy employing forwarding pointers to reduce network impacts of PCS.” Proceedings of Wireless Networks, 1(2), 1995 pp.197-210.
[19] Anand Meka, Ambuj K. Singh ”Distributed Spatial Clustering in Sensor Networks.” Proceedings of 10th International Conference on Extending Database Technology , Munich, Germany, Mar. 2006, pp. 980-1000.
[20] Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, 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.
[21] Xin Li, Young-Jin Kim, Ramesh Govindan, Wei Hong ”Multidimensional 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.
[22] Dieter Pfoser, Christian S. Jensen, Yannis Theodoridis ”Novel Approaches in Query Processing for Moving Object Trajectories.”Proceedings of 26th International Conference on Very Large Data Bases(VLDB) , Cairo, Egypt, Sep. 2000.
[23] Yufei Tao and Dimitris Papadias ”MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries.” Proceedings of 27th International Conference on Very Large Data Bases(VLDB) , Roma, Italy, Sep. 2001.
[24] V. Prasad Chakka, Adam Everspaugh, Jignesh M. Patel ”Indexing Large Trajectory Data Sets With SETI.” Proceedings of the First Biennial Conference on Innovative Data Systems Research , Asilomar, CA, Jan. 2003.