Searching a needle in (linear) opportunistic networks

Esa Hyytiä, Suzan Bayhan, Jörg Ott, Jussi Kangasharju

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Citations (Scopus)

Abstract

Searching content in mobile opportunistic networks is a difficult problem due to the dynamically changing topology and intermittent connections. Moreover, due to the lack of global view of the network, it is arduous to determine whether the best response is discovered or search should be spread to other nodes. A node that has received a search query has to take two decisions: (i) whether to continue the search further or stop it at the current node (current search depth) and, independently of that, (ii) whether to send a response back or not. As each transmission and extra hop costs in terms of energy, bandwidth and time, a balance between the expected value of the response and the costs incurred must be sought. In order to better understand this inherent trade off, we assume a simplified setting where both the query and response follow the same path. We formulate the problem of optimal search for the following two cases: a node holds (i) exactly matching content with some probability, and (ii) some content partially matching the query. We design static search in which the search depth is set at query initiation, dynamic search in which search depth is determined locally during query forwarding, and learning dynamic search which leverages the observations to estimate suitability of content for the query. Additionally, we show how unreliable response paths affect the optimal search depth and the corresponding search performance. Finally, we investigate the principal factors affecting the optimal search strategy.

Original languageEnglish
Title of host publicationMSWiM 2014 - Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems
PublisherAssociation for Computing Machinery, Inc
Pages187-196
Number of pages10
ISBN (Electronic)9781450330305
DOIs
Publication statusPublished - 2014
Event17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM 2014 - Montreal, Canada
Duration: 21 Sep 201426 Sep 2014

Publication series

NameMSWiM 2014 - Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

Conference

Conference17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWiM 2014
Country/TerritoryCanada
CityMontreal
Period21/09/1426/09/14

Other keywords

  • Dynamic programming
  • Mobile cloud computing
  • Mobile opportunistic networks
  • Mobile search

Fingerprint

Dive into the research topics of 'Searching a needle in (linear) opportunistic networks'. Together they form a unique fingerprint.

Cite this