  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, we
study in this paper random walks on hyper-graphs. First, we formalize the
random walk process on hyper-graphs and generalize key notions from random
walks on graphs. We 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. We then provide some basic bounds on the radio cover, in particular, we
show that while on graphs the radio cover time is O(mn), in hyper-graphs it is
O(mnr) where n, m and r are the number of nodes, the number of edges and the
rank of the hyper-graph, respectively. In addition, we define radio hitting
times and give a polynomial algorithm to compute them. We conclude the paper
with results on specific hyper-graphs that model wireless networks in one and
two dimensions.
