Introduction

In this work, we addressed the problem of providing "network middleware support" for tracking a mobile object in fault-prone wireless sensor networks. We assume the availability of an underlying service for detection and classification of a mobile object [5, 9, 6]. Our tracking service solution maintains a distributed indexing structure over the sensor network and provides a basis for higher level applications such as multiple target tracking [7, 8] and pursuer-evader applications [4].

We designed a local and fault-tolerant tracking service for sensor networks that enables any node in the network to initiate a request to find a mobile object. In addition, we introduced a hierarchy-based concept of fault-level local stabilization as well as a scheme for achieving such stabilization.

Our tracking service is local and scalable in the sense that a find operation that is invoked within physical distance d of the mobile object requires O(d) amount of work, or communication cost, to intercept the mobile object, and moves of the mobile object to a total of at most distance d away require O(d * log(network diameter)) amount of work to update the tracking structure. There is a tradeoff between the work required for find and move operations. For example, for a 2-D network, one extreme is the evader-centric tracking program (full information strategy) where a find operation costs O(1) and a move operation of distance d costs O(d*d). The other extreme is the pursuer-centric program (no information strategy) where a move operation is O(1) and a find operation of an object d away is O(d*d). In our work we optimize both operations using a partial information strategy.

Our tracking service, defined on a hierarchy, is fault-level local stabilizing: starting from an arbitrarily corrupted state the tracking structure satisfies its specification within work proportional to the highest corrupted level of the network and number of corruptions.

Overview of the Algorithm

We achieve scalability of our tracking service by maintaining tracking information with accuracy related to the distance from the mobile object [1]. Nearby nodes that are relatively cheap to update have more recent and accurate information about the object, whereas far away nodes that are relatively expensive to update have older and more approximate information.

Tracking structure: We assume a hierarchical partitioning service that partitions the sensor network into clusters based on radius. Our tracking structure is a path rooted at the topmost level of the hierarchy. Each process in the tracking path has at most one child, either at its level or one below it in the hierarchy, and the mobile object resides at the leaf of the tracking path. Each process in the path points to a process that is generally closer to the mobile object and has more recent information about the object. The figure is an example of such a tracking path implemented on top of a hierarchy of hexagonal clusters.

Find operation: A find operation invoked at some process i queries processes at increasingly higher levels of the clustering hierarchy until it encounters a process on the tracking path. Once the tracking path is found, the find operation follows it to its leaf to reach the mobile object. Our find operations are local: a find invoked at a process d away from the object requires O(d) amount of work to find the object.

Move operation: We implement move-triggered updates by means of two actions, grow and shrink. The grow action enables a new path to grow from a new evader location to increasingly higher levels of the clustering hierarchy and connect to the original path. The shrink action serves to clean branches deserted by the mobile object and climbs from the lowest level to higher levels. When a mobile object moves to d distance away, 0(d * log(network diameter)) work is required to update the tracking structure.

Fault-level local stabilization: In the presence of arbitrary state corruption of processes, grow and shrink actions re-establish the tracking path in a fault-level local manner through the use of process timers. Faults are propagated at most a constant number of levels in the network.

Progress

We have completed the algorithm, described above, that tracks a mobile object in the network and have proven that, under certain hierarchy assumptions and reasonable timing assumptions, the algorithm successfully enables a client process at a location initially at most distance d from a moving evader to reach the evader in O(d) time and work. Under these same assumptions we have proven that after a mobile object has moved a total of at most d distance the algorithm performs amortized work of up to O(d * # hierarchy levels) to complete updating the tracking structure.

We also proved that the algorithm has the property of fault-level local stabilization.

An extended abstract of this work was recently published in the 8th International Conference on Principles of Distributed Systems (OPODIS 2004)[2]. We have also developed complete proofs of correctness that were omitted in the extended abstract. The full version can be found at [3].

Future Work

A natural extension to this work is modifying the algorithm and tracking structure to accommodate tracking of multiple evaders by multiple pursuers. This presents a planning problem, as it is likely that the best algorithms for these situations will require coordination between pursuers. A solution to such a problem could be complicated by the occurrence of corruptions in the network.

It might be possible to loosen assumptions on evader movement that we made in this work. For example, it would be desirable to design an algorithm tolerant of evader "black-outs," times where no processes in the network detect the evader. Subject to restrictions on how long such black-outs may occur, it seems possible that the fault-tolerant algorithm here can be extended to cover such cases.

The clustering hierarchy used in this work might be difficult to ensure in practice. How might we provide these hierarchies? One solution might be to program our virtual node infrastructure to provide fault-tolerant clustering. Which portions of the hierarchy restrictions may be relaxed? Are there better alternatives to the clustering hierarchy that would allow design of equally fault-tolerant data structures to track a moving object?

Lastly, the scheme used here for accomplishing fault level local stabilization was very useful in containing faults in the network. How general is this scheme? What other hierarchy based solutions to problems could benefit from the self-stabilization tools employed in this work? Are there other kinds of natural local stabilization definitions with general means of accomplishing them?

Research Support

This project is supported by DARPA Air Force contract number FA9550-04-C-0084, DARPA Award number F33615-01-C-1896, NSF Award numbers CCR-0326277 and CCR-0121277, NSF-Texas Engineering Experiment Station grant 64961-CS, DARPA/AFOSR MURI Award F49620-02-1-0325 and MURI AFOSR Award Number SA2796PO 1-0000243658.

References

[1] Baruch Awerbuch and David Peleg. Online tracking of mobile users. In Journal of the Association for Computing Machinery, 42:1021-1058, 1995.

[2] Murat Demirbas, Tina Nolte, Anish Arora, and Nancy Lynch. A Hierarchy-based Fault-local Stabilizing Algorithm for Tracking in Sensor Networks. In 8th International Conference on Principles of Distributed Systems (OPODIS 2004), December 2004.

[3] Murat Demirbas, Tina Nolte, Anish Arora, and Nancy Lynch. STALK: A Self-Stabilizing Hierarchical Tracking Service for Sensor Networks. Technical Report OSU-CISRC-4/03-TR19, OSU, 2003.

[4] Leonidas J. Guibas. Sensing, tracking, and reasoning with relations. In IEEE Signal Processing Magazine, March 2002.

[5] Yu H. Hu, Dan Li, Kerry Wong, and Akbar Sayeed. Detection, classification and tracking of targets in distributed sensor networks. In IEEE Signal Processing Magazine, 19(2), March 2002.

[6] Jie Liu, Patrick Cheung, Feng Zhao, and Leonidas J. Guibas. A dual-space approach to tracking and sensor management in wireless sensor networks. In MOBICOM, pages 131-139, 2002.

[7] D. M. Reid. An algorithm for tracking multiple targets. In IEEE Transactions on Automatic Control, 1979.

[8] Jaewon Shin, Leonidas Guibas, and Feng Zhao. A distributed algorithm for managing multi-target identities in wireless ad-hocsensor networks. In Proceedings of 2nd International Workshop on Information Processing in Sensor Networks (IPSN), April 2003.

[9] Feng Zhao, Jaewon Shin, and James Reich. Information-driven dynamic sensor collaboration for tracking applications. In IEEE Signal Processing Magazine, March 2002.