Trail: A distance-sensitive sensor network service for distributed object tracking

ABSTRACT

Distributed observation and control of mobile objects via static wireless sensors demands timely information in a distance-sensitive manner: Information about closer objects is required more often and more quickly than that of farther objects. In this article, we present a wireless sensor network protocol, Trail, that supports distance-sensitive tracking of mobile objects for in-network subscribers upon demand. Trail achieves a find time that is linear in the distance from a subscriber to an object, via a distributed data structure that is updated only locally when the object moves. Notably, Trail does not partition the network into a hierarchy of clusters and clusterheads, and as a result Trail has lower maintenance costs, is more locally fault tolerant, and it better utilizes the network in terms of load balancing and minimizing the size of the data structure needed for tracking. Moreover, Trail is reliable and energy efficient, despite the network dynamics that are typical of wireless sensor networks. Trail can be refined by tuning certain parameters, thereby yielding a family of protocols that are suited for different application settings such as rate of queries, rate of updates, and network size. We evaluate the performance of Trail by analysis, simulations in a 90 × 90 sensor network, and experiments on 105 Mica2 nodes in the context of a pursuer-evader control application.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Dahlia Malkhi, LLS: a locality aware location service for mobile ad hoc networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022643]
• 2: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 3: Anish Arora , Emre Ertin , Rajiv Ramnath , Mikhail Nesterenko , William Leal, Kansei: A High-Fidelity Sensing Testbed, IEEE Internet Computing, v.10 n.2, p.35-47, March 2006 [doi>10.1109/MIC.2006.37]
• 4: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 5: Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995 [doi>10.1145/210118.210132]
• 6: Sandip Bapat , Vinodkrishnan Kulathumani , Anish Arora, Analyzing the Yield of ExScal, a Large-Scale Wireless Sensor Network Experiment, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.53-62, November 06-09, 2005 [doi>10.1109/ICNP.2005.7]
• 7: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 8: Hui Cao , Emre Ertin , Vinodkrishnan Kulathumani , Mukundan Sridharan , Anish Arora, Differential games in large-scale sensor-actuator networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127792]
• 9: Demirbas, M., Arora, A., and Kulathumani, V. 2006. Glance: A light weight querying service for sensor networks. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS). 242--257.
• 10: Demirbas, M., Arora, A., Nolte, T., and Lynch, N. 2004. A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), 143--162.
• 11: S. Dolev , D. K. Pradham , J. K. Welch, Modified tree structure for location management in mobile environments, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2)-Volume, p.530, April 02-06, 1995
• 12: Funke, S., Guibas, L., Nguyen, A., and Wang, Y. 2006. Distance sensitive information brokerage in sensor networks. In Proceedings of the International Conference on Distrbuted Computing in Sensor Systems (DCOSS). Springer, 234--251.
• 13: Tian He , Sudha Krishnamurthy , Liqian Luo , Ting Yan , Lin Gu , Radu Stoleru , Gang Zhou , Qing Cao , Pascal Vicaire , John A. Stankovic , Tarek F. Abdelzaher , Jonathan Hui , Bruce Krogh, VigilNet: An integrated sensor network system for energy-efficient surveillance, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.1-38, February 2006 [doi>10.1145/1138127.1138128]
• 14: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 15: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 16: Kulathumani, V., Arora, A., Demirbas, M., and Sridharan, M. 2006. Trail: A distance sensitive wsn service for distributed object tracking. Tech. rep. OSU-CISRC-7/06-TR67, The Ohio State University.
• 17: Xin Liu , Qingfeng Huang , Ying Zhang, Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031510]
• 18: Chenyang Lu , Guoliang Xing , Octav Chipara , Chien-Liang Fok , Sangeeta Bhattacharya, A Spatiotemporal Query Service for Mobile Users in Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.381-390, June 06-10, 2005 [doi>10.1109/ICDCS.2005.7]
• 19: 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 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 20: Rik Sarkar , Xianjin Zhu , Jie Gao, Double rulings for information brokerage in sensor networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161122]
• 21: Shin, J., Guibas, L., and Zhao, F. 2003. A distributed algorithm for managing multi-target indentities in wireless ad hoc networks. In Proceedings of the International Workshop on Information processing in Sensor Networks (IPSN). 223--238.
• 22: Sinopoli, B., Sharp, C., Schenato, L., Schaffert, S., and Sastry, S. 2003. Distributed control applications within sensor networks. Proc. IEEE. 91, 1235--46.
• 23: Vanderbilt University. JProwler, discrete event simulator for wireless networks. http://www.isis.vanderbilt.edu/Projects/nest/jprowler/index.html.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
Distributed tracking, applications of sensor actuator networks, data storage and query, energy efficiency, fault tolerance, network protocol, scalability