Simple Random Walks on Radio Networks
In recent years, protocols that are based on the properties of random walks on graphs have found many applications in communication and information networks, such as wireless networks, peer-to-peer networks and the Web. For wireless networks (and other networks), graphs are actually not the correct model of the communication; instead hyper-graphs better capture the communication over a wireless shared channel. Motivated by this example, the authors study in this paper random walks on hyper-graphs. First, they formalize the random walk process on hyper-graphs and generalize key notions from random walks on graphs. They then give the novel definition of radio cover time, namely, the expected time of a random walk to be heard (as opposed to visit) by all nodes.