TY - JOUR
T1 - On search and content availability in opportunistic networks
AU - Hyytiä, Esa
AU - Bayhan, Suzan
AU - Ott, Jörg
AU - Kangasharju, Jussi
N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - 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 consider a model where both the query and response follow the same or similar path. We formulate the problem of optimal search for 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. Moreover, we study different methods to a priori learn the availability of the content in the network based on passive observations (e.g., using regression and maximum-likelihood based estimates). Such information is highly valuable when defining the optimal search parameters. Finally, we investigate the principal factors affecting the optimal search strategy.
AB - 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 consider a model where both the query and response follow the same or similar path. We formulate the problem of optimal search for 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. Moreover, we study different methods to a priori learn the availability of the content in the network based on passive observations (e.g., using regression and maximum-likelihood based estimates). Such information is highly valuable when defining the optimal search parameters. Finally, we investigate the principal factors affecting the optimal search strategy.
KW - Availability estimation
KW - Dynamic programming
KW - Mobile cloud computing
KW - Mobile opportunistic networks
KW - Mobile search
UR - http://www.scopus.com/inward/record.url?scp=84949530242&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2015.09.011
DO - 10.1016/j.comcom.2015.09.011
M3 - Article
AN - SCOPUS:84949530242
SN - 0140-3664
VL - 73
SP - 118
EP - 131
JO - Computer Communications
JF - Computer Communications
ER -