Asymptotics of query strategies over a sensor network

We consider the problem of a user querying for information over a sensor network, where the user does not have prior knowledge of the location of the information. We consider three information query strategies: (i) a source-only search, where the source (user) tries to locate the destination by initiating query which propagates as a continuous time random walk (Brownian motion); (ii) a source and receiver driven "sticky" search, where both the source and the destination send a query or an advertisement (both propagating as random walks), and these leave a "sticky" trail to aid in locating the destination; and (iii) where the destination information is spatially cached (i.e., repeated over space), and the source tries to locate any one of the caches. For a source-only search, we show that the probability that a query is unsuccessful decays as (log (t))-1. When both the source and the destination send queries or advertisements, we show that the probability that a query is unsuccessful decays as t-5/8. Further, faster polynomial decay rates can be achieved by using a finite number of queries or advertisements. Finally, when a spatially periodic cache is employed, we show that the probability that a query is unsuccessful decays no faster than t-1. Thus, we can match the decay rates of the source and the destination driven search with that of a spatial caching strategy by using an appropriate number of queries. This indicates that the appropriate strategy for querying over large sensor networks would be to use multiple queries and advertisements using the "sticky" search strategy.