Title: Decentralized Random Walk-Based Data Collection in Networks,
Abstract: We analyze a decentralized random walk-based algorithm for data collection at
the sink in a multi-hop sensor network. Our algorithm, Random-Collect, which
involves data packets being passed to random neighbors in the network according
to a random walk mechanism, requires no configuration and incurs no routing
overhead. To analyze this method, we model the data generation process as
independent Bernoulli arrivals at the source nodes. We analyze both latency and
throughput in this setting, providing a theoretical lower bound for the
throughput and a theoretical upper bound for the latency. The main contribution
of our paper, however, is the throughput result: we present a general lower
bound on the throughput achieved by our data collection method in terms of the
underlying network parameters. In particular, we show that the rate at which
our algorithm can collect data depends on the spectral gap of the given random
walk's transition matrix and if the random walk is simple then it also depends
on the maximum and minimum degrees of the graph modeling the network. For
latency, we show that the time taken to collect data not only depends on the
worst-case hitting time of the given random walk but also depends on the data
arrival rate. In fact, our latency bound reflects the data rate-latency
trade-off i.e., in order to achieve a higher data rate we need to compromise on
latency and vice-versa. We also discuss some examples that demonstrate that our
lower bound on the data rate is optimal up to constant factors, i.e., there
exists a network topology and sink placement for which the maximum stable data
rate is just a constant factor above our lower bound.