Title :
A Virtual Node-Based Tracking Algorithm for Mobile Networks
Author :
Nolte, Tina ; Lynch, Nancy
Author_Institution :
MIT CSAIL, Cambridge, MA
Abstract :
We introduce a virtual-node based mobile object tracking algorithm for mobile sensor networks, VINESTALK. The algorithm uses the virtual stationary automata programming layer, consisting of mobile clients, virtual timed machines distributed at known locations in the plane, called virtual stationary automata (VSAs), and a communication service connecting VSAs and mobile clients. VINESTALK maintains a data structure on top of an underlying hierarchical partitioning of the network. In a grid partitioning, operations to find a mobile object distance d away take O(d) time and communication to complete. Updates to the tracking structure after the object has moved a total of d distance take O{d*log network diameter) amortized time and communication to complete. The tracked object may relocate without waiting for VINESTALK to complete updates for prior moves, and while a find is in progress.
Keywords :
finite state machines; grid computing; mobile radio; tracking; virtual machines; virtual reality; VINESTALK; communication service; data structure; grid partitioning; mobile client; mobile object tracking; mobile sensor network; virtual node-based tracking; virtual stationary automata programming; virtual timed machine; Automata; Automatic programming; Clocks; Data structures; Joining processes; Mobile communication; Mobile computing; Partitioning algorithms; Ubiquitous computing; Wireless sensor networks; Sensor networks and ubiquitous computing; Technical areas: Algorithms and theory; Virtual nodes; Wireless and mobile; computing; distributed data structures.; hierarchical partitioning; sensor networks; tracking;
Conference_Titel :
Distributed Computing Systems, 2007. ICDCS '07. 27th International Conference on
Conference_Location :
Toronto, ON
Print_ISBN :
0-7695-2837-3
Electronic_ISBN :
1063-6927
DOI :
10.1109/ICDCS.2007.82
