Improved bounds on information dissemination by manhattan random waypoint model

Aria Rezaei, Jie Gao, Jeff M. Phillips, Csaba D. Tóth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

With the popularity of portable wireless devices it is important to model and predict how information or contagions spread by natural human mobility – for understanding the spreading of deadly infectious diseases and for improving delay tolerant communication schemes. Formally, we model this problem by considering M moving agents, where each agent initially carries a distinct bit of information. When two agents are at the same location or in close proximity to one another, they share all their information with each other. We would like to know the time it takes until all bits of information reach all agents, called the flood time, and how it depends on the way agents move, the size and shape of the network and the number of agents moving in the network. We provide rigorous analysis for the Manhattan Random Waypoint model (which takes paths with minimum number of turns), a convenient model used previously to analyze mobile agents, and find that with high probability the flood time is bounded by ON log M⌈(N/M) log(NM)⌉, where M agents move on an N × N grid. In addition to extensive simulations, we use a data set of taxi trajectories to show that our method can successfully predict flood times in both experimental settings and the real world.

Original languageEnglish (US)
Title of host publication26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018
EditorsLi Xiong, Roberto Tamassia, Kashani Farnoush Banaei, Ralf Hartmut Guting, Erik Hoel
PublisherAssociation for Computing Machinery
Pages139-148
Number of pages10
ISBN (Electronic)9781450358897
DOIs
StatePublished - Nov 6 2018
Externally publishedYes
Event26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018 - Seattle, United States
Duration: Nov 6 2018Nov 9 2018

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Conference

Conference26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018
Country/TerritoryUnited States
CitySeattle
Period11/6/1811/9/18

All Science Journal Classification (ASJC) codes

  • Earth-Surface Processes
  • Computer Science Applications
  • Modeling and Simulation
  • Computer Graphics and Computer-Aided Design
  • Information Systems

Keywords

  • Information dissemination
  • Mobile agents
  • Mobile information systems

Fingerprint

Dive into the research topics of 'Improved bounds on information dissemination by manhattan random waypoint model'. Together they form a unique fingerprint.

Cite this