Title: Coverage characteristics of self-repelling random walks in mobile ad-hoc networks,
Abstract: A self-repelling random walk of a token on a graph is one in which at each
step, the token moves to a neighbor that has been visited least often (with
ties broken randomly). The properties of self-repelling random walks have been
analyzed for two dimensional lattices and these walks have been shown to
exhibit a remarkable uniformity with which they visit nodes in a graph. In this
paper, we extend this analysis to self-repelling random walks on mobile
networks in which the underlying graph itself is temporally evolving. Using
network simulations in ns-3, we characterize the number of times each node is
visited from the start until all nodes have been visited at least once. We
evaluate under different mobility models and on networks ranging from 100 to
1000 nodes. Our results show that until about 85% coverage, duplicate visits
are very rare highlighting the efficiency with which a majority of nodes in the
network can be visited. Even at 100% coverage, the exploration overhead (the
ratio of number of steps to number of unique visited nodes) remains low and
under 2. Our analysis shows that self-repelling random walks are effective,
structure-free tools for data aggregation in mobile ad-hoc networks.