Optimal Encounter-Based Routing of Queries for Mobile Objects

• Author(s) / Creator(s)

  • Nascimento, Mario
  • Wang, Zhiyu
  • MacGregor, Mike

• Mobile objects can be equipped with sensors enabling them to collect data, as well as answer queries remotely and in real-time. For that, 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 and/or minimum delay. Complicating factors in many domains are that the objects in the network are mobile and that they may not form a single connected component at all times. In this paper we take advantage of periodically repeated encounters, 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 routing as an optimization problem in a graph with domain-oriented constraints. Further, we propose polynomial time algorithms to find the optimal and near-optimal routes to deliver the query from a source to one or more query object(s). We also show that the proposed model is flexible enough to support different assumptions about the nature of the encounters. Experimental results, using both real and synthetic datasets, show that our proposed approaches always find better routes with regard to delivery delay and energy cost comparing to other state-of-art protocols. | TRID-ID TR13-04

• Date created

  2013

• Subjects / Keywords

  • Periodicity
  • Regularity
  • Delay tolerant network
  • Routing
  • Mobility
  • Communication networks

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3RX93K7N

• License

  Attribution 3.0 International