Motivated by mobile sensor networks as in participatory sensing applications, we are interested in developing a practical, lightweight solution for routing in a mobile network. While greedy routing is robust to mobility, it may get stuck in a local minimum, which then requires non-trivial recovery methods. We find an embedding of the network such that greedy routing using the virtual coordinates guarantees delivery, thus eliminating the necessity of any recovery methods. Our contribution is to replace the in-network computation of the embedding by a preprocessing of the domain before network deployment and encode the map of network domain to virtual coordinate space by using a small number of parameters which can be preloaded to all sensor nodes. As a result, the map is only dependent on the network domain and is independent of the network connectivity. Each node can directly compute or update its virtual coordinates by applying the locally stored map on its geographical coordinates. This represents the first practical solution for using virtual coordinates for greedy routing in a sensor network and could be easily extended to the case of a mobile network. The paper describes algorithmic innovations as well as implementations on a real testbed.

With the recent development of localization and tracking systems for both indoor and outdoor settings, we consider the problem of analyzing and representing the huge amount of natural trajectories from human movements that we expect to gather in the near future. In this paper we argue the topological representation, which records how a target moves around the natural obstacles in the underlying environment, can be sufficiently descriptive for many applications and efficient enough for both storing, comparing and classifying these natural human trajectories. Technically, the representation uses the homotopy type of the trajectory. By using harmonic one-forms and Hodge decomposition, we pre-process the sensor network with a purely decentralized algorithm such that the homology class of a trajectory can be obtained by a simple integration along the trajectory. This supports real-time classification of trajectories up to the homology accuracy with minimum communication cost. We test the effectiveness of our approach by showing how to classify randomly generated trajectories in a multi-level arts museum layout as well as how to distinguish real world taxi trajectories in a large city.

Motivated by mobile sensor networks as in participatory sensing applications, we are interested in developing a practical, lightweight solution for routing in a mobile network. While greedy routing is robust to mobility, location errors and link dynamics, it may get stuck in a local minimum, which then requires non-trivial recovery methods. We follow the approach taken by Sarkar et. al. [24] to find an embedding of the network such that greedy routing using the virtual coordinates guarantees delivery, thus eliminating the necessity of any recovery methods. Our new contribution is to replace the in-network computation of the embedding by a preprocessing of the domain before network deployment and encode the map of network domain to virtual coordinate space by using a small number of parameters which can be pre-loaded to all sensor nodes. As a result, the map is only dependent on the network domain and is independent of the network connectivity. Each node can directly compute or update its virtual coordinates by applying the locally stored map on its geographical coordinates. This represents the first practical solution for using virtual coordinates for greedy routing in a sensor network and could be easily extended to the case of a mobile network. Being extremely light-weight, greedy routing on the virtual coordinates is shown to be very robust to mobility, link dynamics and non-unit disk graph connectivity models.

We study the problem of maintaining group communication between m mobile agents, tracked and helped by n static networked sensors. We develop algorithms to maintain a O(lg n)-approximation to the minimum Sterner tree of the mobile agents such that the maintenance message cost is on average O(lg n) per each hop an agent moves. The key idea is to extract a 'hierarchical well-separated tree (HST)' on the sensor nodes such that the tree distance approximates the sensor network hop distance by a factor of O(lg n). We then prove that maintaining the subtree of the mobile agents on the HST uses logarithmic messages per hop movement. With the HST we can also maintain O(lg n) approximate k-center for the mobile agents with the same message cost. Both the minimum Steiner tree and the k-center problems are NP-hard and our algorithms are the first efficient algorithms for maintaining approximate solutions in a distributed setting.

We study the problem of in-network processing and queries of trajectories of moving targets in a sensor network. The main idea is to exploit the spatial coherence of target trajectories for opportunistic information dissemination with no or small extra communication cost, as well as for efficient probabilistic queries searching for a given target signature in a real-time manner. Sensors near a moving target are waken up to record information about this target and take the communication opportunities to exchange their knowledge with preceding and descending sensor nodes along the trajectory. Thus a moving target's information is naturally detected, recorded, and disseminated along its trajectory, as well as the motion trajectories that enter the sensor field afterwards. We analyzed and through simulations tested the dissemination cost and query success rate for randomly generated data sets. Trajectories of reasonable length can be discovered by probabilistic in-network queries with high probability. Compared with the scheme without opportunistic dissemination, the in-network processing of trajectories, with modest cost on dissemination, allows substantially reduced query cost and delay.