Towards end-to-end routing for periodic mobile objects

Mobile objects can be equipped with hardware enabling them to collect data, as well as answer queries remotely and in real-time. For the latter, one needs to be able to effectively route queries from a base station to the queried object in an efficient way, i.e., with minimum energy-cost or minimum delay. A complicating factor is that in many domains the mobile objects may not form a single connected component at all times. In this paper we take advantage of periodically repeating movements to establish encounter patterns, where an encounter is defined as a time-period long enough so that sensors can communicate with each other. Possessing such encounter patterns, we show how to model the query routing problem as a shortest path problem in a graph with domain-oriented constraints, and we also present polynomial time algorithms to find the guaranteed minimal delay and minimal energy routes. Furthermore, our experiments show that the minimal energy routes found by our algorithm have a cost of less than 1% of the cost obtained when using a flooding-based protocol.