Finding Mobile Data: Efficiency vs. Location Inaccuracy

摘要

A token is hidden in one out of n boxes following some known probability distribution and then all the boxes are locked. The goal of a searcher is to find the token in at most D ≤ n rounds by opening as few boxes as possible, where in each round any set of boxes may be opened. We design and analyze strategies for a searcher who does not know the exact values of the probabilities associated with the locked boxes. Instead, the searcher might know only the complete order or a partial order of the probabilities, or ranges in which these probabilities fall. We show that with limited information the searcher can find the token without opening significantly more boxes compared to a searcher who has full knowledge. This problem is equivalent to finding mobile users (tokens) in cellular networks (boxes) and finding data (tokens) in sensor networks (boxes).