Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs)

Details Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs) Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs)

2009-07-09

arxiv.org/abs/0907.1678v1

Computer Science

Networking and Internet Architecture

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163518