1Using Heterogeneity to Enhance Random Walk-based Queries

Abstract — We propose a push-pull mechanism to enhance the performance of random walk-based querying in heterogeneous sensor networks and analyze its performance. Using connections between random walks and electrical resistance, we obtain closed-form expressions and bounds of the querying cost for a linear topology, along with numerical solutions for more realistic topologies via Markov chain analysis of the time to absorption. We show that having even a small degree of heterogeneity can provide very significant improvements in query performance. Specifically, for linear topologies we prove that using a fraction 4/5k of uniformly-placed high-degree cluster-heads (where 2k is the degree of each such node), a query cost reduction of Θ(1−1/k2) can be obtained. Realistic two-dimensional topologies also show a similar trend — using about 10 % of the nodes as cluster-heads provides a query cost improvement between 30% and 70 % depending on the coverage of the high-degree nodes. I