Computer Science – Networking and Internet Architecture
Scientific paper
2011-04-13
Computer Science
Networking and Internet Architecture
Scientific paper
Consider a wireless network of n nodes represented by a graph G=(V, E) where an edge (i,j) models the fact that transmissions of i and j interfere with each other, i.e. simultaneous transmissions of i and j become unsuccessful. Hence it is required that at each time instance a set of non-interfering nodes (corresponding to an independent set in G) access the wireless medium. To utilize wireless resources efficiently, it is required to arbitrate the access of medium among interfering nodes properly. Moreover, to be of practical use, such a mechanism is required to be totally distributed as well as simple. As the main result of this paper, we provide such a medium access algorithm. It is randomized, totally distributed and simple: each node attempts to access medium at each time with probability that is a function of its local information. We establish efficiency of the algorithm by showing that the corresponding network Markov chain is positive recurrent as long as the demand imposed on the network can be supported by the wireless network (using any algorithm). In that sense, the proposed algorithm is optimal in terms of utilizing wireless resources. The algorithm is oblivious to the network graph structure, in contrast with the so-called `polynomial back-off' algorithm by Hastad-Leighton-Rogoff (STOC '87, SICOMP '96) that is established to be optimal for the complete graph and bipartite graphs (by Goldberg-MacKenzie (SODA '96, JCSS '99)).
Shah Devavrat
Shin Jinwoo
Tetali Prasad
No associations
LandOfFree
Efficient Distributed Medium Access 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 Efficient Distributed Medium Access, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Distributed Medium Access will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-217755